DV-HOP定位算法

1、無(wú)線傳感器網(wǎng)絡(luò)的定位技術(shù)主要內(nèi)容1 引言2 定位技術(shù)分類3 DV-HOP定位算法 4 性能指標(biāo)引言無(wú)線傳感器網(wǎng)絡(luò)： 指一種在監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)部署的傳感器節(jié)點(diǎn)通過(guò)無(wú)線通信方式形成的多跳、自組織的分布式網(wǎng)絡(luò)。定位技術(shù)的研究意義： 節(jié)點(diǎn)的感知數(shù)據(jù)必須與位置相結(jié)合，離開位置信息，感知數(shù)據(jù)是沒有意義的，如環(huán)境監(jiān)測(cè)、醫(yī)療、森林火災(zāi)監(jiān)控等。引言n當(dāng)前對(duì)節(jié)點(diǎn)定位問(wèn)題的研究一般都基于以下前提: (1) 網(wǎng)絡(luò)中有一定比例的節(jié)點(diǎn)位置己知或具有GPS定位功能，這些位置已知的節(jié)點(diǎn)可作為定位參考點(diǎn)。因?yàn)镚PS模塊價(jià)格昂貴、能量消耗大，而且受工作環(huán)境的限制，所以網(wǎng)絡(luò)中少數(shù)節(jié)點(diǎn)通過(guò)GPS定位。 (2)節(jié)點(diǎn)具有與鄰近節(jié)點(diǎn)通信的能

2、力。 (3)節(jié)點(diǎn)不具有自主移動(dòng)能力。主要內(nèi)容1 引言2 定位技術(shù)分類3 DV-HOP定位算法 4 性能指標(biāo)定位技術(shù)的分類 根據(jù)定位過(guò)程中是否需要測(cè)量實(shí)際節(jié)點(diǎn)間的距離，定位算法可分為基于測(cè)距(Range-Based)的定位算法和無(wú)需測(cè)距(Range-Free)的定位算法。需要測(cè)量相鄰節(jié)點(diǎn)間的絕對(duì)距離或方位絕對(duì)距離或方位，并利用節(jié)點(diǎn)間的實(shí)際距離實(shí)際距離來(lái)計(jì)算未知節(jié)點(diǎn)的位置。無(wú)需這些測(cè)量信息，而是根據(jù)網(wǎng)絡(luò)連通性網(wǎng)絡(luò)連通性等信息，利用節(jié)點(diǎn)間的估計(jì)估計(jì)距離距離計(jì)算節(jié)點(diǎn)位置。無(wú)需測(cè)距的定位基于測(cè)距的定位Range-Based & Range-Free特點(diǎn)比較定位精度相對(duì)較高，但對(duì)額外的硬件設(shè)施要求

3、也比較高成本低、功耗小、抗測(cè)量噪聲能力強(qiáng)、硬件設(shè)備簡(jiǎn)單無(wú)需測(cè)距技術(shù)的定位基于測(cè)距的定位基于測(cè)距的算法基于接收信號(hào)角度的定位 (AOA)基于信號(hào)傳播時(shí)間差定位（TDOA）基于接收信號(hào)強(qiáng)度的定位（RSSI）基于信號(hào)傳播時(shí)間的定位（TOA）基于測(cè)距的定位算法無(wú)需測(cè)距Amorphous 算法DV-HOP定位算法APIT質(zhì)心定位算法無(wú)需測(cè)距的定位算法集中式計(jì)算&分布式計(jì)算n根據(jù)在定位過(guò)程中是否把信息傳送到某個(gè)后臺(tái)中心或把信息傳送到某個(gè)后臺(tái)中心或服務(wù)器服務(wù)器進(jìn)行節(jié)點(diǎn)坐標(biāo)的計(jì)算把所需信息傳送到某個(gè)把所需信息傳送到某個(gè)中心節(jié)點(diǎn)中心節(jié)點(diǎn)(例如，一臺(tái)例如，一臺(tái)服務(wù)器服務(wù)器)，并在那里進(jìn)行節(jié)點(diǎn)定位計(jì)算的方式

4、指依賴節(jié)點(diǎn)間的信息依賴節(jié)點(diǎn)間的信息交換和協(xié)調(diào)交換和協(xié)調(diào)，由節(jié)點(diǎn)自行計(jì)算的定位方式。集中式計(jì)算分布式計(jì)算定位的基本方法三邊測(cè)量法三角測(cè)量法極大似然估計(jì)法Min-max算法三邊測(cè)量法n已知A、B、C三個(gè)節(jié)點(diǎn)的坐標(biāo)，以及它們到未知節(jié)點(diǎn)D的距離，確定節(jié)點(diǎn)D的坐標(biāo)。n若在測(cè)距過(guò)程中存在誤差，上述三個(gè)圓無(wú)法交于一點(diǎn)，用存在誤差的d1、d2、d3去解上述方程時(shí)便無(wú)法得到正確解。因此，在實(shí)際計(jì)算坐標(biāo)時(shí)，一般不采用上述解方程的方法，而采用極大似然估計(jì)或其他數(shù)值解法。三邊測(cè)量法缺點(diǎn)三角測(cè)量法n已知A、B、C三個(gè)節(jié)點(diǎn)的坐標(biāo)，節(jié)點(diǎn)D相對(duì)于節(jié)點(diǎn)A、B、C的角度，確定節(jié)點(diǎn)D的坐標(biāo)；n轉(zhuǎn)換為三邊測(cè)量法。極大似然估計(jì)法n已知

5、1、2、3等n個(gè)節(jié)點(diǎn)的坐標(biāo)，及它們到未知節(jié)點(diǎn)D到距離，確定節(jié)點(diǎn)D的坐標(biāo)；n最小均方差估計(jì)算法。極大似然估計(jì)法使用標(biāo)準(zhǔn)的最小二乘法可以得到未知節(jié)點(diǎn)的坐標(biāo)為使用標(biāo)準(zhǔn)的最小二乘法可以得到未知節(jié)點(diǎn)的坐標(biāo)為Min-max算法 Min-Max算法的基本思想是依據(jù)未知節(jié)點(diǎn)到各錨節(jié)點(diǎn)的距離測(cè)量值及其坐標(biāo)構(gòu)造若干個(gè)限制框(bounding-box)，即以錨節(jié)點(diǎn)為圓心，未知節(jié)點(diǎn)到該錨節(jié)點(diǎn)的距離測(cè)量值為半徑所構(gòu)成圓的外接正方形，正方行交叉區(qū)域的幾何中心即為未知節(jié)點(diǎn)的估計(jì)坐標(biāo)。如下圖所示，說(shuō)明了有3個(gè)錨節(jié)點(diǎn)估計(jì)距離時(shí)的工作原理，錨節(jié)點(diǎn)A（xi,yi)的限制框的4個(gè)頂點(diǎn)的計(jì)算如下式所示： 為未知節(jié)點(diǎn)M到錨節(jié)點(diǎn)A的測(cè)量距

6、離。Min-Max算法 這些限制框的交集通過(guò)下式計(jì)算。當(dāng)未知節(jié)點(diǎn)可利用的錨節(jié)點(diǎn)多于3個(gè)時(shí)，將其轉(zhuǎn)化為 組分別計(jì)算并取其平均值。3nC主要內(nèi)容1 引言2 定位技術(shù)分類3 DV-HOP定位算法 4 性能指標(biāo)DV-HOP算法 DV-HOP定位算法具有方法簡(jiǎn)單，定位精度較高的特點(diǎn)，它是利用距離矢量路由和GPS定位的思想提出的一系列分布式定位方法之一。指依賴節(jié)點(diǎn)間的信息依賴節(jié)點(diǎn)間的信息交換和協(xié)調(diào)交換和協(xié)調(diào)，由節(jié)點(diǎn)自行計(jì)算的定位方式。DV-HOP算法的3個(gè)階段n第第1階段階段：網(wǎng)絡(luò)中的各參考節(jié)點(diǎn)各參考節(jié)點(diǎn)通過(guò)典型的距離距離矢量交換協(xié)議矢量交換協(xié)議向鄰居節(jié)點(diǎn)廣播自身位置信息分組，使得網(wǎng)絡(luò)中的所有節(jié)點(diǎn)獲得距參

7、考節(jié)點(diǎn)的最小跳距參考節(jié)點(diǎn)的最小跳數(shù)信息數(shù)信息。 左圖是一個(gè)由9個(gè)節(jié)點(diǎn)組成的小型傳感器網(wǎng)絡(luò)。 L1 L2 L3 為三個(gè)參考節(jié)點(diǎn) 剩余的都為未知節(jié)點(diǎn)，對(duì)節(jié)點(diǎn)A定位DV-HOP算法的3個(gè)階段),(),(jjiiyxyxijdDiHs：為錨節(jié)點(diǎn)i與錨節(jié)點(diǎn)j的坐標(biāo)jh ：為錨節(jié)點(diǎn)i與錨節(jié)點(diǎn)j之間的實(shí)際距離 ：為錨節(jié)點(diǎn)i到錨節(jié)點(diǎn)j之間的跳數(shù) ：以錨節(jié)點(diǎn)i為基準(zhǔn)，計(jì)算出的平均每跳距離NiHsM ：錨節(jié)點(diǎn)總個(gè)數(shù)i：錨節(jié)點(diǎn)i的平均每跳距離的權(quán)值DV-HOP算法的3個(gè)階段-無(wú)偏估計(jì)準(zhǔn)則 第第2階段階段：每個(gè)參考節(jié)點(diǎn)利用其它參考節(jié)點(diǎn)的位置信息其它參考節(jié)點(diǎn)的位置信息和相隔最小跳數(shù)相隔最小跳數(shù)來(lái)計(jì)算平均每跳距離，并將其

8、作為一個(gè)校正值廣播至網(wǎng)絡(luò)中廣播至網(wǎng)絡(luò)中。當(dāng)接收到校正值后，節(jié)點(diǎn)根據(jù)跳數(shù)計(jì)算與參考節(jié)點(diǎn)之間的距離。平均每跳距離n當(dāng)獲得每個(gè)參考節(jié)點(diǎn)的平均每跳距離后，需要將其廣播至網(wǎng)絡(luò)中的其他節(jié)點(diǎn)。n未知節(jié)點(diǎn)接收到的平均每跳距離有兩種方法：方法1中未知節(jié)點(diǎn)僅記錄接收到的第1個(gè)平均每跳距離，并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)；方法2中未知節(jié)點(diǎn)記錄其到每個(gè)參考節(jié)點(diǎn)的不同的平均每跳距離。n方法1確保了絕大多數(shù)節(jié)點(diǎn)從最近的參考節(jié)點(diǎn)接收平均每跳距離值，也就是說(shuō)，在方法1中將從最近參考節(jié)點(diǎn)接收的平均每跳距離作為整個(gè)網(wǎng)絡(luò)的平均每跳距離。但由于網(wǎng)絡(luò)中節(jié)點(diǎn)分布的隨機(jī)性，需要盡可能多地利用網(wǎng)絡(luò)中的信息，采用方法2將具有比采用方法1更優(yōu)越的性能。平均每

9、跳距離Mkkiihh1歸一化處理得到權(quán)值MiDiDHsHsi1 通過(guò)這個(gè)加權(quán)過(guò)程，使得定位節(jié)點(diǎn)的平均每跳距離能從多個(gè)信標(biāo)節(jié)點(diǎn)的平均每跳距離中得到反映，使得定位節(jié)點(diǎn)的平均每跳距離更接近于網(wǎng)絡(luò)的實(shí)際平均每跳距離。DV-HOP算法的3個(gè)階段-最小均方誤差準(zhǔn)則 第第2階段階段：每個(gè)參考節(jié)點(diǎn)利用其它參考節(jié)點(diǎn)的位置信息其它參考節(jié)點(diǎn)的位置信息和相隔最小跳數(shù)相隔最小跳數(shù)來(lái)計(jì)算平均每跳距離，并將其作為一個(gè)校正值廣播至網(wǎng)絡(luò)中廣播至網(wǎng)絡(luò)中。當(dāng)接收到校正值后，節(jié)點(diǎn)根據(jù)跳數(shù)計(jì)算與參考節(jié)點(diǎn)之間的距離。NHSd222)52/()52(22212ddHSNNHSd213NHSd233DV-HOP算法的3個(gè)階段 第第3階段階段

10、：當(dāng)未知節(jié)點(diǎn)獲得與3個(gè)或更多參考節(jié)點(diǎn)的距離時(shí)，根據(jù)三邊測(cè)量法三邊測(cè)量法或極大似然估計(jì)法極大似然估計(jì)法來(lái)計(jì)算未知節(jié)點(diǎn)的位置。n分析分析：在通信范圍內(nèi)無(wú)論其相距多遠(yuǎn)，都將其跳數(shù)估計(jì)為一跳，而每跳的距離不同，用跳數(shù)乘以平均跳距來(lái)計(jì)算錨節(jié)點(diǎn)與未知節(jié)點(diǎn)的距離，必然偏離實(shí)際距離，造成節(jié)點(diǎn)定位出現(xiàn)較大的誤差。如圖2中的錨節(jié)點(diǎn)L1與錨節(jié)點(diǎn)L2之問(wèn)的最短路徑，其中每跳的長(zhǎng)度都不同，只有最后一跳的長(zhǎng)度接近于實(shí)際值，即節(jié)點(diǎn)的通信半徑。DV-HOP算法的改進(jìn)1-跳數(shù)修正DV-HOP算法的改進(jìn)1-跳數(shù)修正n定義1：兩錨節(jié)點(diǎn)i與j之間的實(shí)際距離與所有節(jié)點(diǎn)的通信半徑R之比定義為理想跳數(shù)，用Hij表示，即：Hij =dij/

11、R。n定義2：節(jié)點(diǎn)間實(shí)際跳數(shù)與理想跳數(shù)的相對(duì)誤差定義為偏離因子，用 表示，即：n定義3：假設(shè)錨節(jié)點(diǎn)i與j之間的實(shí)際跳數(shù)為 ，偏離因子為 ， 定義跳數(shù)修正系數(shù)為 其中n取正整數(shù)，仿真結(jié)果表明，n為2時(shí)，定位效果最佳。ijijijijijhopsHhops/ )(ijnijijw1ijhopsDV-HOP算法的改進(jìn)1-跳數(shù)修正n錨節(jié)點(diǎn)間的跳數(shù)：n未知節(jié)點(diǎn)計(jì)算距其最近錨節(jié)點(diǎn)的跳數(shù)n未知節(jié)點(diǎn)計(jì)算距其他錨節(jié)點(diǎn)的跳數(shù)未知節(jié)點(diǎn)計(jì)算距其最近錨節(jié)點(diǎn)的跳數(shù)DV-HOP算法的改進(jìn)1-跳數(shù)修正 為距離未知節(jié)點(diǎn)最近的錨節(jié)點(diǎn)i與其它錨節(jié)點(diǎn)偏離因子的平均值，該平均值充分利用了各個(gè)錨節(jié)點(diǎn)的跳數(shù)信息，更能反映節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)的特

12、性。由于未知節(jié)點(diǎn)p距離錨節(jié)點(diǎn)i最近，所以它與錨節(jié)點(diǎn)i的網(wǎng)絡(luò)特性更接近，因此用錨節(jié)點(diǎn)i的平均偏離因子近似代替未知節(jié)點(diǎn)p與錨節(jié)點(diǎn)i之間的跳數(shù)偏離因子，造成的跳數(shù)誤差更小。njiijnw) 1/(DV-HOP算法的改進(jìn)1-跳數(shù)修正未知節(jié)點(diǎn)計(jì)算距其他錨節(jié)點(diǎn)的跳數(shù) 在實(shí)際網(wǎng)絡(luò)中大多數(shù)未知節(jié)點(diǎn)到任兩錨節(jié)點(diǎn)的路徑會(huì)有部分重疊，因此用兩錨節(jié)點(diǎn)間的偏離因子更能體現(xiàn)未知節(jié)點(diǎn)距離其它錨節(jié)點(diǎn)跳數(shù)偏離程度。DV-HOP算法的改進(jìn)2-估計(jì)坐標(biāo)的迭代求精估計(jì)坐標(biāo)的迭代求精未知節(jié)點(diǎn)到各個(gè)參考節(jié)點(diǎn)的初步估計(jì)距離為未知節(jié)點(diǎn)到各個(gè)參考節(jié)點(diǎn)的初步估計(jì)距離為d1d2對(duì)（2）式在估計(jì)坐標(biāo)（x0,y0）處進(jìn)行泰勒展開，并忽略高階偏導(dǎo)數(shù)的影

13、響，得到（3）（1）（2） 將(3)代入(1)中，求解方程組，可得到坐標(biāo)修正步長(zhǎng)h,k。設(shè)定判斷條件：DV-HOP算法的改進(jìn)2-估計(jì)坐標(biāo)的迭代求精估計(jì)坐標(biāo)的迭代求精（4）若上式成立，則停止計(jì)算，否則取步長(zhǎng)為 ，即 代入式（3）重新計(jì)算，直到滿足式（4）的精度門限要求，最后迭代結(jié)果即為所求節(jié)點(diǎn)坐標(biāo)三維DV-HOP算法 主要是對(duì)傳統(tǒng)的DV-Hop算法的三維擴(kuò)展，并在其基礎(chǔ)上分別通過(guò)引入移動(dòng)代理、用均方誤差和歸一化加權(quán)處理平均每跳距離、判斷參與定位的信標(biāo)節(jié)點(diǎn)的有效性等方法分情況采用總體最小二乘法、平移坐標(biāo)法和畫圓法進(jìn)行定位。平移坐標(biāo)法 P1P2P3為選取的三個(gè)信標(biāo)節(jié)點(diǎn)，m為待定位的節(jié)點(diǎn)，對(duì)原三維坐標(biāo)

14、系進(jìn)行平移變換，使得P1為新坐標(biāo)系的坐標(biāo)原點(diǎn)，P1P2P3全在或近似在XY平面上。根據(jù)幾何知識(shí)可以得到m點(diǎn)的坐標(biāo)。畫圓法 用三邊測(cè)量法和極大似然估計(jì)法來(lái)計(jì)算待定位節(jié)點(diǎn)的坐標(biāo)需要三個(gè)或三個(gè)以上的錨節(jié)點(diǎn)位置信息。當(dāng)未知節(jié)點(diǎn)通信范圍內(nèi)的錨節(jié)點(diǎn)數(shù)為2或者通信范圍內(nèi)的任三個(gè)錨節(jié)點(diǎn)共線時(shí)，可采用畫圓法進(jìn)行定位。 未知節(jié)點(diǎn)與兩個(gè)錨節(jié)點(diǎn)在一個(gè)平面上，分別以錨節(jié)點(diǎn)為圓心，以它們到未知節(jié)點(diǎn)的距離為半徑畫圓。如果交與一點(diǎn)，則為所求點(diǎn)坐標(biāo)；若交與兩點(diǎn)，則取兩交點(diǎn)的中點(diǎn)為所求點(diǎn)坐標(biāo)。 二維或者三維空間都可以使用畫圓法，這樣可以減少不可定位的節(jié)點(diǎn)以及定位誤差。主要內(nèi)容1 引言2 定位技術(shù)分類3 DV-HOP定位算法 4 性能指標(biāo)性能指標(biāo)(1)定位精度 一般用誤差值與節(jié)點(diǎn)無(wú)線通信半徑的比值來(lái)表示傳感器節(jié)點(diǎn)的定位精度。定位精度只要不大于 40，就能夠滿足絕大多數(shù)應(yīng)用的要求。n定義平均定位誤差eerror為所有未知節(jié)點(diǎn)的估計(jì)值與實(shí)際值的差值的平均值：n定義歸一化平均定位誤差為平均定位誤差error與通信半徑R的比值：性能指標(biāo)(2) 節(jié)點(diǎn)密度 一般來(lái)說(shuō)，網(wǎng)絡(luò)中節(jié)點(diǎn)密度越大，定位精度越高。DV-Hop算法只能在節(jié)點(diǎn)分布比較密集的無(wú)線傳感器網(wǎng)絡(luò)中才能合理地估算平均每跳距離，然后才能較準(zhǔn)確地估算出節(jié)點(diǎn)的位置。(3) 錨節(jié)點(diǎn)密度 因?yàn)槿斯げ渴疱^節(jié)點(diǎn)