DV-HOP定位算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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