第7章 節(jié)點(diǎn)定位

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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