第7章 節(jié)點定位

1、7.1節(jié)點定位概述無線傳感器網(wǎng)絡(luò)中的節(jié)點定位主要是指對位置信息未知的節(jié)點進行一個相對位置或者絕對位置的標定與獲知，基本方法是根據(jù)少數(shù)已知位置的節(jié)點，按照某種算法計算出位置信息的過程。7.1節(jié)點定位概述節(jié)點定位可以分為兩種：一種是確定自己在系統(tǒng)中的位置信息，即節(jié)點自身定位；另一種是確定目標節(jié)點在系統(tǒng)中的位置信息，即目標定位。7.1節(jié)點定位概述在無線傳感器節(jié)點的定位過程中，沒有最優(yōu)的定位算法，只有最適合具體應(yīng)用的算法，因此在設(shè)計定位算法的時候，需要根據(jù)具體應(yīng)用的特點進行特定的優(yōu)化。一般情況下，在設(shè)計無線傳感器網(wǎng)絡(luò)的節(jié)點定位算法時需要考慮如下傳感器網(wǎng)絡(luò)的特性：7.1節(jié)點定位概述1.自組織性2.容錯性

2、3.分布計算4.能量高效7.2節(jié)點定位的分類（1）基于測距的定位方法。在基于測距的定位方法中，首先要計算出節(jié)點之間的距離，然后再實現(xiàn)定位。常用的測距技術(shù)主要有RSSI、TOA、TDOA和AOA等。（2）無需測距的定位方法。由于測距的定位方法在應(yīng)用中會產(chǎn)生較大的能耗與成本，因而，人們更多采用的是無需測距的定位方法。如質(zhì)心法、DV-Hop法和APIT法等等。1.基于測距和無需測距的定位方法7.2節(jié)點定位的分類（1）基于測距的定位方法。在基于測距的定位方法中，首先要計算出節(jié)點之間的距離，然后再實現(xiàn)定位。常用的測距技術(shù)主要有RSSI、TOA、TDOA和AOA等。（2）無需測距的定位方法。由于測距的定位

3、方法在應(yīng)用中會產(chǎn)生較大的能耗與成本，因而，人們更多采用的是無需測距的定位方法。如質(zhì)心法、DV-Hop法和APIT法等等。1.基于測距和無需測距的定位方法7.2節(jié)點定位的分類集中式定位方法需要一個中心節(jié)點負責(zé)定位所有的未知節(jié)點。在分布式節(jié)點定位方法中，節(jié)點根據(jù)本地的局部信息進行定位，這種方法具有很好的容錯性，同時符合無線傳感器的網(wǎng)絡(luò)的分布式特點，因而在研究中被廣泛應(yīng)用。2.基于集中式和分布式的定位方法7.2節(jié)點定位的分類有參考節(jié)點的為絕對定位法，無參考節(jié)點的為相對定位法。絕對定位中節(jié)點位置唯一，受節(jié)點的移動性影響小，應(yīng)用較為廣泛。相對定位無需信標節(jié)點，對系統(tǒng)硬件的要求低，成本低，可以滿足一定的應(yīng)

4、用需求。3.基于絕對定位和相對定位的的定位方法。7.3節(jié)點定位的基本術(shù)語7.3節(jié)點定位的基本術(shù)語1.信標節(jié)點：有時也稱作錨點，指通過其他方式預(yù)先獲得坐標位置的節(jié)點。網(wǎng)絡(luò)中相應(yīng)的其余節(jié)點稱為未知節(jié)點或非錨點。2.測距（Ranging）：指兩個相互通信的節(jié)點通過測量方式來估計出彼此之間的距離與角度。7.3節(jié)點定位的基本術(shù)語3.鄰居節(jié)點（Neighbor Nodes）：傳感器節(jié)點通信半徑范圍內(nèi)，無需經(jīng)過其他節(jié)點就能夠直接與之通信的節(jié)點，統(tǒng)稱為鄰居節(jié)點。4.跳數(shù)（Hop Count）：兩個要實現(xiàn)通信的節(jié)點之間信息轉(zhuǎn)發(fā)所需的跳段總數(shù)。7.3節(jié)點定位的基本術(shù)語5.跳段距離（Hop Distance）：兩個

5、要實現(xiàn)通信的節(jié)點之間的跳段距離的總和。6.連通度（Connectivity）：一個節(jié)點擁有的鄰居節(jié)點的數(shù)目。7.3節(jié)點定位的基本術(shù)語7.到達角度（Angle Of Arrival，AOA）：節(jié)點接收到的信號相對于自身軸線的角度。8.到達時間（Time Of Arrival）：信號從一個節(jié)點傳播到另一個節(jié)點所需要的時間。7.3節(jié)點定位的基本術(shù)語9.接收信號傳播時間差（Time Difference Of Arrival，TDOA）：信號在傳輸過程中，同時發(fā)出的兩種不同頻率的信號到達同一目的地時由于不同的傳輸速度造成的時間差。10.接收信號強度指示（Received Signal Strength

6、 Indicator，RSSI）：節(jié)點接收到的無線信號的強度大小。7.3節(jié)點定位的基本術(shù)語11.視線關(guān)系（Line Of Sight，LOS）：如果傳感器網(wǎng)絡(luò)的兩個節(jié)點之間沒有障礙物，能夠?qū)崿F(xiàn)直接通信，則稱兩個節(jié)點間存在視線關(guān)系。12.非視線關(guān)系（Non Line Of Sight）：傳感器網(wǎng)絡(luò)的兩個節(jié)點之間存在障礙物，影響了他們直接的無線通信。7.4節(jié)點定位的技術(shù)指標定位精度是指節(jié)點位置信息與其真實位置之間的接近程度。定位精度是定位系統(tǒng)中最重要的指標，精度越高，技術(shù)要求越嚴格，成本也會越高。1.定位精度7.4節(jié)點定位的技術(shù)指標定位覆蓋是指定位系統(tǒng)中，能夠?qū)崿F(xiàn)定位的未知節(jié)點的數(shù)目占整個未知節(jié)點

7、數(shù)目的比例。在無線傳感器網(wǎng)絡(luò)中，只有大范圍的節(jié)點都能被定位，定位算法才是有效的。定位覆蓋范圍與定位精度是一對相互矛盾的性能指標。覆蓋范圍越大，提供的精度就越低，很難實現(xiàn)大范圍的高精度定位。2.定位覆蓋7.4節(jié)點定位的技術(shù)指標刷新速度是指提供位置信息的頻率。對于導(dǎo)航類型的定位算法，在物體移動的過程中，如果位置信息的刷新速率較慢，則會出現(xiàn)位置信息滯留的現(xiàn)象，導(dǎo)致導(dǎo)航失誤等問題的發(fā)生。因此，刷新速率影響了定位系統(tǒng)的精度。3.刷新速度7.4節(jié)點定位的技術(shù)指標由于傳感器被隨機部署到目標監(jiān)測區(qū)域，需要長時間使用，如果傳感器耗能過快，則會導(dǎo)致定位失敗。因此，定位技術(shù)是否能夠滿足低功耗是衡量定位性能的一項重要

8、指標。4.功耗7.4節(jié)點定位的技術(shù)指標定位算法的復(fù)雜程度也會對定位服務(wù)產(chǎn)生一定的影響，因此，定位技術(shù)必須簡單高效，快速收斂。5.算法復(fù)雜度7.4節(jié)點定位的技術(shù)指標系統(tǒng)的安全性是保護自己不受外部影響和攻擊的能力。由于傳感器可能被放到惡劣的環(huán)境當(dāng)中，這時需要無線傳感網(wǎng)絡(luò)的定位系統(tǒng)具有一定的保護能力，使系統(tǒng)不會因為環(huán)境的影響或者人為的破壞而影響到整個系統(tǒng)的定位功能。6.安全性7.5基于測距的節(jié)點定位基于測距的節(jié)點定位分為兩個階段，第一階段是測距階段，利用常用的測距技術(shù)來計算出未知節(jié)點與信標節(jié)點的絕對距離值，常用的測距技術(shù)有TOA、TDOA和RSSI方法等；第二階段是定位，確定坐標階段，即利用第一階段

9、計算出來的距離確定未知節(jié)點的坐標，常用的方法有：三邊定位、極大似然估計定位和Min-Max方法等。7.5基于測距的節(jié)點定位1.TOA測距通常采用傳播速度v較慢的物理信號，如超聲波來測量時間。這種方法要求節(jié)點間保持精確的時間同步，時間測量上較小的誤差可能導(dǎo)致較大的誤差結(jié)果，對傳感器節(jié)點的硬件和功耗提出了較高的要求。7.5.1測距階段vTTd)(017.5基于測距的節(jié)點定位2.TDOA測距通常采用無線射頻信號和超聲波信號，其中，接收節(jié)點記錄的兩種信號到達時間分別為T1和T2，已知無線射頻信號和超聲波信號的傳播速度為c1和c2。7.5.1測距階段)(12TTkd)/(2121cccck7.5基于測距

10、的節(jié)點定位3.RSSI測距當(dāng)無線信號在大氣中傳播時，由于各種因素的干擾，信號強度會隨著距離的增大而衰減，這表明在信號強度變化與傳播距離之間存在某種數(shù)學(xué)關(guān)系，利用這種關(guān)系建立起的數(shù)學(xué)模型就可以求出發(fā)射節(jié)點和接收節(jié)點之間的距離。7.5.1測距階段XddndPLdPL00lg10)()(7.5基于測距的節(jié)點定位1.三邊定位法7.5.2定位階段7.5基于測距的節(jié)點定位1.三邊定位法7.5.2定位階段222222222CCCBBBAAAdyyxxdyyxxdyyxx)()()()(21)()()()(21222222222222222222222222CBCACBCAACCACACBBCCBCACACB

11、CACBCABCCBCACAACCACACAxxyyyyxxddyyxxxxddyyxxxxyxxyyyyxxddyyxxyyddyyxxyyx7.5基于測距的節(jié)點定位2.多邊極大似然估計法7.5.2定位階段7.5基于測距的節(jié)點定位2.多邊極大似然估計法7.5.2定位階段222222222212121)()()()()()(nnndyyxxdyyxxdyyxx7.5基于測距的節(jié)點定位2.多邊極大似然估計法從第一個方程開始分別減去最后一個方程可得如下線性方程：7.5.2定位階段221122112212222222222222112211221)(2)(2)(2)(2)(2)(2nnnnnnnnn

12、nnnnnnnnnnnddyyyyyxxxxxddyyyyyxxxxxddyyyyyxxxxx7.5基于測距的節(jié)點定位2.多邊極大似然估計法可以簡化為矩陣相乘的方式：AX=b，其中使用極大似然估計方法可以得到節(jié)點D的坐標為：7.5.2定位階段)( 2)( 2)( 2)( 21111nnnnnnyyxxyyxxA212221221212221221nnnnnnnnnddyyxxddyyxxbyxXbAAAXTT1)(7.5基于測距的節(jié)點定位3.Min-max定位方法Min-max定位是根據(jù)若干錨點位置和到未知節(jié)點的測距值，創(chuàng)建多個正方形邊界框，所有邊界框的交集為一矩形，取其矩形的質(zhì)心作為未知節(jié)點

13、的坐標。7.5.2定位階段7.5基于測距的節(jié)點定位3.Min-max定位方法7.5.2定位階段2)min()max(2)min()max(iiiiiiiidydyydxdxx7.6無需測距的節(jié)點定位1.算法介紹多邊形的幾何中心稱為質(zhì)心。在質(zhì)心算法中，錨節(jié)點周期性地向鄰近節(jié)點廣播錨節(jié)點分組，錨節(jié)點分組中包含錨節(jié)點的標識號和位置信息，當(dāng)未知節(jié)點接受到來自不同的錨節(jié)點的信標分組數(shù)量超過某一個門限k或接收一定時間后，就確定自身位置為這些錨節(jié)點所組成的多邊形質(zhì)心。7.6.1質(zhì)心算法66fedcbafedcbayyyyyyxxxxxxyx，7.6無需測距的節(jié)點定位2.算法分析7.6.1質(zhì)心算法7.6無需測

14、距的節(jié)點定位2.算法分析質(zhì)心的精度依賴于錨節(jié)點分布的密度和分布情況。雖然增加錨節(jié)點數(shù)量可以改進定位精度，但需要更多的節(jié)點間通信，這將極大地增加節(jié)點能量的消耗。此外，如果在未知節(jié)點周圍用于定位的錨節(jié)點以未知節(jié)點為中心分布很均勻的話，定位精度會得到提高。相反分布不均勻?qū)⒅苯訉?dǎo)致定位精度下降。7.6.1質(zhì)心算法7.6無需測距的節(jié)點定位3.質(zhì)心算法的優(yōu)缺點質(zhì)心定位算法最大的優(yōu)點是它非常簡單，計算量小，完全基于網(wǎng)絡(luò)的連通性；缺點是需要較多的錨節(jié)點，誤差相對較高。7.6.1質(zhì)心算法7.6無需測距的節(jié)點定位1.算法介紹DV-Hop（Distance Vector Hop）算法，即基于距離向量跳數(shù)的定位方法。

15、該算法借鑒了經(jīng)典的距離向量路由算法。定位過程一共分為三個階段。7.6.2 DV-Hop定位7.6無需測距的節(jié)點定位1.算法介紹（1）計算未知節(jié)點與每個信標節(jié)點的最小跳數(shù)。這個階段使用經(jīng)典的距離向量交換協(xié)議，每個節(jié)點維護一個表，記錄到信標節(jié)點的坐標和跳數(shù)。每個信標節(jié)點發(fā)送一個廣播分組，該分組包含自身的位置信息和跳段數(shù)，跳段數(shù)初始化為0。節(jié)點收到信標節(jié)點的廣播分組后，檢驗該分組跳段數(shù)是否小于本節(jié)點表內(nèi)的存儲值，如果是，則更新該表，然后跳段數(shù)加1并廣播該分組，否則丟棄該分組。最終所有的未知節(jié)點均能獲得所有信標節(jié)點的最小跳數(shù)。7.6.2 DV-Hop定位7.6無需測距的節(jié)點定位1.算法介紹（2）計算未

16、知節(jié)點與信標節(jié)點的距離每個信標節(jié)點根據(jù)自身表中記錄的其他信標節(jié)點的坐標信息和跳數(shù)，按照公式（7-10）計算平均跳段距離ci。為了確保絕大多數(shù)節(jié)點可以從最近的信標節(jié)點接收平均跳段距離，把計算出來的平均跳段距離利用可控洪泛法進行廣播，每個節(jié)點均接收第一個跳段的距離，忽略后來到達的節(jié)點。最后未知節(jié)點便可以計算出自己到達相應(yīng)信標節(jié)點的距離（平均跳段距離*跳數(shù)）。7.6.2 DV-Hop定位ijjijjijiihyyxxc22)()(7.6無需測距的節(jié)點定位1.算法介紹（3）計算未知節(jié)點的坐標經(jīng)過前兩個階段，現(xiàn)在已知信標節(jié)點L1、L2與L3之間的距離和跳數(shù)，如圖7-9所示。假設(shè)L2計算得到平均跳段距離為

17、（40+80）/（2+5）=17.14。假設(shè)節(jié)點A從節(jié)點L2獲得平均跳段距離，則它與信標節(jié)點L1、L2、L3的距離分別為317.14、217.14、317.14。7.6.2 DV-Hop定位7.6無需測距的節(jié)點定位2.算法分析（1）DV-Hop定位方法與基于測距定位方法具有相似之處，就是都需要獲得未知節(jié)點到錨節(jié)點的距離，基于測距的定位方法得到的是精確距離，而DV-Hop定位方法使用平均跳段距離估算距離，存在一定的誤差。7.6.2 DV-Hop定位7.6無需測距的節(jié)點定位2.算法分析（2）基于測距的定位方法在計算距離時依靠測量無線電波信號，這就限定了未知節(jié)點只能獲得自己射頻覆蓋范圍內(nèi)的錨節(jié)點的距

18、離，而DV-Hop定位方法依靠的是網(wǎng)絡(luò)連通性和網(wǎng)絡(luò)拓撲結(jié)構(gòu)，這樣就可以獲得更多的有用數(shù)據(jù)，提高定位精度。7.6.2 DV-Hop定位7.6無需測距的節(jié)點定位2.算法分析（3）由于DV-Hop定位方法在定位過程中兩次洪泛，能量開銷比較大。（4）該算法主要用于節(jié)點稀疏的網(wǎng)絡(luò)中對未知節(jié)點定位的場合。（5）總得來說，DV-Hop定位方法對硬件要求比較低，實現(xiàn)起來比較簡單。7.6.2 DV-Hop定位7.6無需測距的節(jié)點定位1.算法介紹APIT（Approximate Point-in-Triangulation Test）稱為近似三角形內(nèi)點測試法，屬于距離無關(guān)、區(qū)域相關(guān)的定位策略。該算法實現(xiàn)簡單、定位成本低、傳感器節(jié)點功耗小、定位精度高，因而得到廣泛應(yīng)用。7.6.3 APIT定位7.6無需測距的節(jié)點定位1.算法介紹它的基本思路是從未知節(jié)點周圍的錨節(jié)點中任意選取三個，組合成一個三角形，判斷該點是否位于該三