無線傳感器網(wǎng)絡(luò)節(jié)點定位技術(shù)的重要課題。根本概念描述節(jié)點n〕和未知節(jié)點〔n。通常將自身位置的節(jié)GPS定位設(shè)備〔或北斗衛(wèi)星導(dǎo)航系統(tǒng)2-1所示。UUUUUUB UUUBUUUUUUUUUBUBUUU2-1無線傳感器網(wǎng)絡(luò)中信標節(jié)點和未知節(jié)點Figure2-1Beaconnodesandunknownnodesofwirelesssensornetwork2-14個信標節(jié)點和數(shù)量眾多的未知節(jié)點組成。U來表示，未知節(jié)點通過四周的信標節(jié)點或已實現(xiàn)自身定位的未知節(jié)點通過肯定的算法來實現(xiàn)自身定位。下面是無線傳感器網(wǎng)絡(luò)中一些常用術(shù)語：〔rs通信的節(jié)點；跳數(shù)〔pt：需要的最小跳段總數(shù)；連通度〔y：一個節(jié)點擁有的鄰居節(jié)點數(shù)目；〔pe和；接收信號傳播時間差(TimeDifferenceofArrival，TDOA)：信號的傳輸速度所造成的時間差；接收信號傳播時間eof：信號在兩個不同節(jié)點之間傳播所需要的時間；信號返回時間〔dpeoft，：信號從一個節(jié)點傳到另一個節(jié)點后又返回來的時間；Arrival，AOA)：節(jié)點自身軸線相對于其接收到的信號之間的角度；線信號到達傳感器節(jié)點后的強弱值。節(jié)點定位技術(shù)性能評價標準通常狀況下有以下幾個指標來衡量：l〔通常為坐標〕與其真實位置之間的接近程度，它是衡量傳百分比。〔egofnWSN掩蓋大范圍的節(jié)點定位才有意義。節(jié)點密度〔ey：節(jié)點密度就是指的播撒的傳WSN中針對不同的定位算法所需要節(jié)點密度也ofBeaconNode：信標節(jié)點密度是指信標節(jié)點在整個WSN中所占的比例。信標節(jié)點具有自身定位功的凹凸。容錯性和自適應(yīng)性〔tedy：所t，精準地說是容故障，而并非容錯誤〔r。自適應(yīng)性可以看作是一個能依據(jù)環(huán)境變化能夠智作在最優(yōu)狀態(tài)。安全性指的是指系統(tǒng)對合法用戶的響應(yīng)及對非法懇求WSN通常工作在物理環(huán)境較性。rnWSN能夠以較小的能耗和高效的能量利用率來實現(xiàn)安全定位是當前爭論的所面臨首要的問題[23]。代價與本錢〔tdn：定位算法的代價應(yīng)使定位系統(tǒng)的代價最小，如定位所需的計算量、通信量、存儲空間等。器網(wǎng)絡(luò)的設(shè)計過程中要結(jié)合實際狀況綜合考慮。傳感器網(wǎng)絡(luò)節(jié)點定位算法在定位的實現(xiàn)過程中有很多算法，依據(jù)不同的標準有不同的分類方法。最常見的分類是：基于測距的(Range-Based)定位算法和距離無關(guān)的(Range-Free)離時，然后才能計算出未知節(jié)點坐標信息，這樣的定位方法就可以稱為Range-Based的定位算法。反之，其它的算法無需測量節(jié)點之間的距離值就稱之Range-FreeRange-BasedRange-Free的定位低本錢等應(yīng)用領(lǐng)域。Range-Free的定位算法實現(xiàn)起來比較簡潔，計算量也較小，但并不能實現(xiàn)高精度的定位，是一種粗精度的算法?；跍y距的定位算法TOATDOAAOA、RSSI等常用的測距技術(shù)來測量各個未知節(jié)點到信標節(jié)點確實定距離值，這個階〔計算坐標〕階段，即利用測距階NameExtrahardwareTOAYEffectivedistanceshortInterferencerejectionweakerDistance-measuringerrorsmallerTDOAYshortestweaksmallestAOAYNameExtrahardwareTOAYEffectivedistanceshortInterferencerejectionweakerDistance-measuringerrorsmallerTDOAYshortestweaksmallestAOAYshortestweaksmallest〔一〕測距階段算法分析：TOA是依據(jù)信號的傳播時間計算被測節(jié)點之間的距離。TOA算法雖然定位TDOATOA的根底上所形成的節(jié)點和放射節(jié)點之間的距離值。AOATriangulation來進展定位運算。在AOA算法中，未知節(jié)點首先能很差，不能夠滿足現(xiàn)實生活中較多電磁干擾的環(huán)境中使用。RSSI是利用信道衰減模型，依據(jù)所接收到的信號的強弱來實現(xiàn)節(jié)點的定位這就極大的降低了定位精度[24-25]。PDOA是通過測量接收信號相位差，求出信號傳播的來回時間，然后計算信號來回的距離。NFER是通過近場電場和磁場的相位差來測量距離的。2-1對以上六種基于測距定位算法進展了比較。2-1Table2-1Comparisonofdistance-basedlocationalgorithm〔二〕定位階段算法分析：Trilateration[26]是通過三個坐標的信標節(jié)點以及這三個信標節(jié)點到未知A、B、C的坐標分別為(x,y、1 1(x,y2

、(xy3

Dd、d、d1 2 3

D的坐標設(shè)為(x,y)?？梢缘玫揭韵路匠蹋篸2(xx 1

)2(yy1

)2 d2(xx)2(yy )2 2 2 2 2d32

xx)23

(yy)23〔2-1〕依據(jù)上式可得未知節(jié)點D的坐標方程為：x

x)

y)1x2x2

d2

〔2-2〕 1 3

1 3 1 3

3 3 12 y 2(x x2

2(y2

y)3

1

3

1

3

3

d21RSSIRSSINlongstrongbigPDOAYlongstrongbigNFERNshortweaksmallMultilateration是三個以上信標節(jié)點的坐標信息以及信標節(jié)點到這個未〔t〔MeanSquareError〕等求出未知節(jié)點的坐標信息。Triangulation是通過未知節(jié)點的接收器天線陣列來測量出周邊信標節(jié)點所發(fā)出信號的入射角信息，利用所得到的角度信息和信標節(jié)點的坐標信息，依據(jù)Trilateration算出未知節(jié)點的坐標。MaximumLikelihoodMethod[27]2-2所示。112nD342-2最大似然估量法Figure2-2MaximumLikelihoodMethodn個信標節(jié)點的坐標為：(x,y1 1

、(xy、2 2(x,y3

)，…(x,yn n

)。它們到未知節(jié)點Dd、d、d1 2 3

d，假nD的坐標為(x,y)。那么存在如下公式：(xx)2(yy)2d 1 1 1(xx)2(yy)2dn n n從第一個方程開頭分別減去最終一個方程可得：

〔2-3〕

x)xy

2y

y)yd

2d21

1 n 1

1 n 1 nx 2x22(x x)xy2 y22(y y)yd 2d2n n n n n〔2-4〕 〔2-4〕可表示為：AXbAX、b如下面〔2-5〕到〔2-7〕所示：2(x

x)

2(y

y)n1n1nA2(xn1

x)n

2(yn1

y)n

〔2-5〕x2x

2y2y2d

2d2 1 n 1 n n 1 b x 2x2y2 y2d2d 2n1 n n1 n n n1

〔2-6〕xXy 〔2-7〕利用最大似然估量法或最小二乘法可得D的坐標為：^X(ATA)1ATb^〔2-8〕基于無需測距的定位算法基于測距的定位算法雖然能夠?qū)崿F(xiàn)準確定位，但往往也對硬件要求較高，導(dǎo)測距的定位算法主要有：DV-HOP算法、質(zhì)心算法、Amorphous算法、APIT算MDS-MAP算法等。下面分別介紹這幾種方法：〔Centroid〕質(zhì)量中心簡稱質(zhì)心d想點。平均值即為質(zhì)心坐標。質(zhì)心定位算法是UniversityofSouthernCalifornia的NirupamaBulusu等提出的，該算法適用于室外節(jié)點密度較高狀況下的定位，它實現(xiàn)對節(jié)點的定位。其根本思想是：未知ID的信息來確定其所在的區(qū)域，依據(jù)其接收到的信標節(jié)點的ID及位置信息計算所在Centroid的定位精度。2-3所示。AA1AA26(x,y)AA35A42-3Figure2-3DiagramofCentroidPrincipleA

(xy、(x,y2

、(xy3

、(xy4

1 2、(xy5

3、(x6

6 1 1y，則區(qū)域的質(zhì)心為：612(x,y)(xx12

xx3

xx5 6,

yy1

yy3

yy5 6)6

〔2-9〕Amorphous實現(xiàn)起來比較簡潔連通度；二是定位過程中需要較高的節(jié)點密度。〔APIT〕APIT定位算法在實現(xiàn)過程中未知節(jié)點首先通過收集鄰居節(jié)點的節(jié)點標識符、位置信息、放射信號功率的大小等信息來確定該節(jié)點是否位于不同的信標節(jié)點所組成的三角形內(nèi)，然后統(tǒng)計包含未知節(jié)點的三角形區(qū)域，并把這些三角形區(qū)域的交集構(gòu)成一個多邊形，這個多邊形根本上確定了未知節(jié)點所在的區(qū)域并縮小了未知節(jié)點所在的范圍，最終計算這個多邊形區(qū)域的質(zhì)心，并將質(zhì)心作為未知節(jié)點的位置，這樣就實現(xiàn)了未知節(jié)點的定位。APIT2-4所示。AAA3A42SAA51AnA62-4APIT算法示意圖Figure2-4DiagramofAPITPrinciple2-4A、A

、AA中隨1 2 3 n2-4中，未知節(jié)點分別選取AAA

、AAA

、AAA…AAA

并測試自身1 2 3

2 3

3 4

1 2 n是否位于這三個信標節(jié)點所組成的三角形中，推斷完成后也就確定了這些三角形的穿插區(qū)域〔如圖中的陰影局部〕所組成的多邊形，然后計算這個多邊形的S，并把質(zhì)心S的坐標作為該未知節(jié)點的坐標。APIT定位算法利用電磁波衰落模型，相對于別的定位算法有著更高的定位精度，對節(jié)點密度要求也低，APIT定位算法的通信量小且適用于電磁波不規(guī)章的模型，能夠在大多數(shù)場合應(yīng)用。凸規(guī)劃定位算法凸規(guī)劃定位算法(ConvexOptimization)展性不好，信號傳輸和處理比較麻煩，不能夠敏捷使用。凸規(guī)劃定位算法的根本2-5〔如圖中陰影區(qū)域外的矩形區(qū)域出該矩形區(qū)域的質(zhì)心并把它作為未知節(jié)點的坐標，以此來實現(xiàn)節(jié)點定位。2-5Figure2-5DiagramofConvexOptimizationPrincipleMDS-MAP定位算法MDS-MAPUniversityofMissouri-ColumbiaYiShang等提出來的。該算法屬于集中式定位算法，它是利用節(jié)點間的連通信息通過Dijkstra或Floyd算法生成節(jié)點間距矩陣，然后利用多維尺度分析技術(shù)來獲得節(jié)點間的位置信息。MDS-MAP定位算法的實現(xiàn)主要分為以下三個步驟：首先從全局角度動身生依據(jù)給出的節(jié)點間的連通信息，如具備測距力量〔ShortestPathAlgorithm〕粗略地估量每對節(jié)點間的距離，生成節(jié)點間距矩陣。23維相對坐標系統(tǒng)，該坐標為相對坐標。進展轉(zhuǎn)換，使之成為確定坐標系統(tǒng)。MDS-MAP定位算法基于多維尺度分析技術(shù)來進展節(jié)點定位，該算法對網(wǎng)絡(luò)的定位結(jié)果。MDS-MAP中將未知節(jié)點的相對坐標轉(zhuǎn)換為確定坐標一般至少需要3個信標節(jié)點進展關(guān)心大。2-2對以上六種無需測距定位算法進展了比較。2-2名稱類別網(wǎng)絡(luò)信標節(jié)是否需信標節(jié)定位節(jié)點密 點密度 要額外名稱類別網(wǎng)絡(luò)信標節(jié)是否