DV-Hop定位算法誤差分析與優化①

李敬兆, 孫 睿, 譚大禹(安徽理工大學 電氣與信息工程學院, 淮南 300)(安徽理工大學 計算機科學與工程學院, 淮南 300)

DV-Hop定位算法誤差分析與優化①

李敬兆1, 孫 睿2, 譚大禹21(安徽理工大學 電氣與信息工程學院, 淮南 232001)2(安徽理工大學 計算機科學與工程學院, 淮南 232001)

傳感器節點在森林、水下等復雜環境下進行數據采集時, 由于信號強度與信號傳輸速度受到障礙物或傳輸介質的干擾, 影響了基于信號信息的定位算法的測量精度. 同時考慮到節點的成本和節點的動態性, DV-Hop定位算法有較強的適用性和實用性. 分析了影響DV-Hop算法定位精度的因素, 并在此基礎上提出了一個度量節點離散程度的公式, 給出了一個該算法的優化方案, 仿真表明優化后的算法有更高的定位精度.

無線傳感器網絡; 定位; DV-Hop

傳感器節點采集數據時, 獲取節點信息是一項必不可少的重要環節. 例如在環境監測的應用中, 需要獲取采集節點的位置信息以便反映出該區域環境信息,又如在目標追蹤與監視的應用中, 其目的就是為了獲取該目標的位置信息. 另一方面, 利用傳感器節點的位置信息可以對路由進行優化, 根據節點傳回的位置信息構造出整個傳感器網絡的網絡拓撲, 從而加強對網絡的管理. 因此, 研究傳感器節點定位對傳感器的部署和監控都有著重要意義.

隨著無線傳感器網絡的發展, 關于定位的新算法和優化方案不斷涌現. 目前已有許多算法能夠解決無線傳感器網絡中的定位問題, 但每種算法都有各自的適用場景, 在定位算法的選擇上, 必須對具體需求做出權衡. 當傳感器在一些復雜環境下工作時, 傳播信號受到周圍不確定因素影響, 會產生反射、散射、衍射等現象, 同時信號強度的衰減速度也隨介質的改變而改變, 再加上障礙物的干擾, 這就使得依靠信號強度和信號傳輸速度的定位算法不能滿足實際需求. DV-Hop定位算法是一個基于非測距的經典算法, 有著實現簡單, 相對誤差較小等優點, 同時在節點成本與功耗方面, 相比于基于測距的定位算法有很大優勢.但由于該算法使用節點之間的平均跳距估算節點間的實際距離, 當節點分布不均勻時, 該算法的定位精度大大降低. 同時連通度較低的信標節點與三邊定位誤差也影響了定位精度. 本文對該算法進行改進, 通過仿真對算法有效性進行驗證.

1 DV-Hop定位算法與三邊定位

DV-Hop算法是由Dragos Niculescu等人提出的,其算法最大的特點就是無需依靠傳感器信號信息, 而是依靠路由跳數實現定位. 由于路由信息可從節點網絡層直接獲取, 該算法無需測距模塊從而降低了節點成本, 同時不依賴于傳感器信號信息, 從而有較高的自適應性. 該算法通過獲得信標節點這些先驗信息和未知節點到信標節點的最小跳數, 估算出未知節點的位置. 具體算法分為以下三個步驟:

1) 計算各個節點之間的最小跳數

首先每個信標節點將自身的位置信息以廣播的形式發送給周圍的節點, 其廣播的數據包中包含一個記錄跳數的字段記為h, 初始值為0. 接收到該信息的節點只保留到相同信標節點的最小跳數值, 并將該數值加1, 向周圍的鄰居節點繼續廣播. 通過節點不斷的廣播, 網絡中的所有節點都將記錄下該節點與每個信標之間所經過的最少節點個數, 即最小跳數. 未知節點u與信標節點s之間的最小跳數記為su,t.

2) 估算平均跳距

通過上一步驟節點的廣播, 每一個信標節點都可以獲取其它信標節點的位置信息以及它們之間的最小跳數, 基于以上兩個信息可估算出節點間進行通訊時每一跳所經過的實際距離, 記為HopSize. 計算平均跳距的公式如式(1)所示.

其中(xi,xj), (yi,yj)為信標節點i, j坐標, hi,j為信標節點i與j之間的最小跳數.

3) 計算未知節點位置

設du,s為估算的未知節點u到信標節點s的距離,計算公式如式(2)所示.

當未知節點得到周圍三個信標的距離信息后, 根據三邊定位原理即可計算出未知節點的實際方位. 三邊定位求解原理如圖1所示.

設信標節點A1, A2, A3的坐標分別為(xi,yi), 其中(i=1,2,3), 未知節點的坐標為(x,y), 未知節點與三個信標的距離分別為di( i=1,2,3), 那么存在以下關系, 如式(3)所示.

圖1 三邊定位求解圖

由上式可計算出未知節點的具體坐標, 從而實現對該節點的定位.

2 誤差分析

2.1 節點分布的均勻程度對定位精度的影響

DV-Hop算法由于依賴于跳數進行距離估算, 其對平均跳距的估算決定著定位的精度, 在一些節點分布均勻的情況下, DV-Hop具有良好的定位精度. 但是在實際運用中, 節點可能呈非均勻分布, 即某個區域內節點分布密集, 另外的區域內節點分布稀疏. 分析算法計算公式可知, 得出的平均跳距HopSize的值具有唯一性, 無法隨著節點分布的疏密而改變. 在節點分布密集的環境下, 計算得到的平均每跳距離相比于節點稀疏的環境的平均每跳距離較大, 這是因為節點越密集, 它們之間的通信路徑就越近似于一條直線,如圖2所示, 且計算得出的平均每跳距離近似于節點自身的通信半徑(平均每跳距離一定不大于通信半徑).

圖2 理想情況下的節點拓撲

節點A與節點B進行通信時, 針對該算法的最理想情況, 即存在節點C, 使得節點C與節點A和B的距離恰好等于節點的通信半徑. 該網絡拓撲情況下使用該算法計算得出的平均跳距就為通信半徑, 計算得出節點A與B的距離也與實際相等. 在節點分布稀疏區域, 節點A與B的通信可能經過若干個節點, 這將造成計算得出的平均每跳距離小于通信半徑, 所以全部節點都使用相同的平均跳距進行距離計算將影響定位精度.

2.2 連通度較低的信標節點對定位精度的影響

連通度較低的信標節點會造成定位誤差, 如圖3所示的網絡拓撲環境.

圖3 節點網絡拓撲圖

信標節點A, B, C, D與待定位節點U, 其余為普通節點, 由于地形或節點運動原因, 節點B與節點C之間存在障礙物, 造成信標節點C處于整個網絡邊緣.位于區域邊界的節點C只能接收到來自某一側的信息,使得該節點無法利用全面的信息進行定位計算. 如果使用信標節點A、B、C計算得到的平均每跳距離約為10m, 可觀察到, 實際情況中B與C的距離只是不到兩個通信距離, 而B與C之間的跳數達到了6跳, 使用該平均每跳距離計算A與B的距離為20 m. 這與真實距離相差了一倍, 若使用該平均跳距計算未知節點位置必然會造成較大誤差. 造成該影響的原因為信標節點C的連通度較低處于網絡邊緣, 信標節點C的通信半徑下僅有1個節點. 如果排除C節點, 使用信標節點A、B、D來估算平均每跳距離則誤差較小.

2.3 三邊定位計算公式對定位精度的影響

根據三邊定位原理可知, 節點定位時通過周圍三個信標節點的位置信息來計算自身位置, 所以選擇不同的信標計算得到的位置信息也不同. 一般情況下,對這三個信標節點的選擇采用就近原則, 即選擇距離未知節點最近的三個信標進行位置的計算, 這樣可以減少定位的誤差. 但實際情況下, 由平均跳距計算得出的節點間距離與實際距離存在偏差, 三邊定位求解圖中的三個圓的交匯處是一塊區域, 而不是一個點,如圖4所示.

圖4 三邊定位誤差分析

已知待定位節點到信標A, B, C的距離, 分別以信標位置為圓心, 這三個距離為半徑作圓, 形成圖4中的陰影區域. 與之對應, 對三邊定位方程組求解, 解的范圍(即未知節點的坐標)便在該陰影內. 這就導致只能判斷出未知節點在該區域中, 不能確定該節點的具體位置. 通過選擇周圍的信標節點參與計算, 采用最小二乘法求解可有效避免上述情況.

3 算法改進與仿真

在無線傳感器網絡中, 各個節點之間的距離與各個節點的平均距離之差反應著整個網絡中所有節點的離散程度, 離散程度越小則該區域中節點越均勻, 反之該區域中節點越離散. 借鑒方差對無線傳感器網絡中的節點離散程度進行度量.

設無線傳感器網絡中節點i與節點j之間的距離為di,j, 則一個邊長為w的方形區域內節點離散程度S計算公式如式(4)所示.

式中d表示各個節點之間的平均距離, n表示無線傳感器網絡中的節點個數.d的計算公式如式(5)所示.

使用Matlab對無線傳感器網絡中節點進行仿真,構造節點分布不均勻環境, 節點分布如圖5所示.

圖5 節點分布圖

對整個區域內和三個方形區域分別計算其離散程度, 通過50次仿真節點不均勻分布的情況, 得出各區域節點的離散程度如圖6所示.

圖6 各區域節點離散程度

由以上仿真數據可看出, 三個方形區域內節點的離散程度大體上比全體節點的離散程度低很多, 通過實驗數據匯總計算多次仿真各區域離散程度的平均值得到的結果如表1所示.

表1 各區域節點離散程度表

從表中數據可觀察到, 由于節點分布不均整體區域的離散程度值最大, 取該整體部分區域計算得到的平均離散程度值均小于整體區域的平均離散程度值,所以節點離散程度大的區域可通過區域劃分的方式劃分成多個節點分布相對均勻的區域.

因此, 在節點廣播階段, 通過控制數據包轉發次數, 進行局部定位將提高定位精度. 僅選取待定位節點周圍的節點進行計算, 忽略掉遠離待定位節點的節點, 因為待定位節點周圍的節點環境可以近似成均勻分布的節點環境, 同時節點的泛洪不會擴散至整個傳感器網絡, 節約了功耗和網絡負擔.

針對連通度低的信標情況, 在進行平均每跳距離計算時, 應盡量避開連通度較低的信標節點, 信標節點可首先通過廣播確定通信范圍內的鄰居節點個數,如果該個數極少則自身休眠不參與平均跳距地計算任務.

針對三邊定位誤差問題, 選用若干個鄰居信標對節點進行定位計算. 這若干信標坐標代入后組成的方程組使用最小二乘法進行求解. 設待定位節點坐標為(x,y), 周圍有k個鄰居信標, 坐標表示為(xi,yi)未知節點到信標的距離為d, 其中i=1, 2, 3, …, k. 代入兩

i

點距離公式后組成如式(6)所示的超定方程組.

方程組(7)可化簡成AX=b的形式, 利用最小二乘法可得X=(ATA)-1ATb , 從而解出未知節點坐標.

同時未知節點與某個信標節點距離越近, 該信標節點越能反映出未知節點周圍的網絡拓撲情況, 使用該信標節點計算的平均跳距越接近于實際情況下未知節點周圍節點的跳距.

基于以上分析, 其優化后的算法如下所示:

1) 待定位節點廣播自身信息.

待定位節點進行廣播, 在原有的廣播的信息中增加一個跳數上限T的字段, 防止該消息擴散至整個網絡. 這樣待定位節點周圍的信標節點都存有到該待定節點的最小跳數.

2) 確定信標.

接收到定位信息的信標節點, 通過廣播自身信息(報文跳數限制為1跳)獲取自身周圍節點個數, 并與自身設定的閾值K進行比較, 大于閾值則參與計算平均跳距, 否則不參與計算.

3) 估算未知節點廣播范圍內節點的平均每跳距離.

4) 計算待定位節點到各個信標的距離, 使用最小二乘法計算待定位節點坐標.

優化后的算法流程圖如圖7所示.

圖7 算法流程圖

為驗證優化后算法的有效性, 使用Matlab對該算法進行仿真實驗, 200個傳感器節點非均勻分布在100×100的矩形區域內, 其中信標節點占總節點數的30%, 節點的通信半徑設置為15, 低連通度信標的閾值判定設置為1, 對單個節點進行定位計算誤差后分析得出優化后算法的定位精度受廣播最大跳數T的變化而產生波動, 如圖8所示.

由圖中數據可觀察到相對誤差隨著最大跳數T的增大呈V字型走勢, 這是因為當T取較小的值時未知節點發送的數據包無法到達信標或者參與定位的節點過于稀少導致誤差較大, 隨著可傳輸跳數的增加, 參與定位的節點變多, 誤差降至最低, 當最大跳數繼續增大時, 由于節點的非均勻分布性導致了定位誤差增大, 在該環境下最大跳數設為3時, 定位誤差最小, 此時為最優最大跳數.

對該網絡拓撲環境中的所有節點進行定位仿真,通過調整最大跳數與低連通度信標的閾值后達到最優的定位效果, 如圖9所示.

圖9 定位效果圖

圖9 (a)為原算法定位效果圖, 圖9(b)為優化后的定位效果圖. 圖中圓標為未知節點的實際位置坐標,星標為信標節點的實際位置坐標, 連接圓標線段的另一端為算法定位位置坐標, 則每條線段長度代表了每個未知節點定位的誤差, 線段越長定位誤差越大. 圖9(b)線段明顯短于圖9(a)線段, 表明優化后的算法定位精度比原算法高.

針對非均勻分布的節點定位優化, 一些學者提出采用未知節點到各個信標的跳數對平均跳距進行加權處理的方法提高定位精度, 即與未知節點相距跳數越小的信標在計算時賦予更大的權值, 該方法在實際應用中也獲得了良好的定位效果, 本文對其相關算法進行仿真后得出如下數據.

圖10為三種算法在節點非均勻分布環境下的定位誤差與信標所占比例的關系圖, 隨著信標節點的增加, 所有算法的定位誤差均有下降趨勢, 優化后的兩個算法較原算法定位精度提高較為明顯, 以信標所占比例18%為例, 原算法相對誤差為45.8%, 加權DV-Hop算法為38. 7%, 本文算法為35. 1%.

圖10 信標比例與相對誤差關系圖

本文算法主要針對節點離散程度影響因素進行改進, 通過改變節點離散程度, 即調整節點分布情況,使用上述三種算法對節點進行定位, 計算得出節點定位的相對誤差如表2所示.

表2 不同離散程度下各定位算法的定位誤差(%)表

表中數據反映出各算法的定位誤差都隨節點離散程度的增加而增加, 加權算法和本文算法在節點離散程度增大的情況下均能抑制定位誤差的類指數式增長,本文算法的定位誤差在不同離散值下均小于其他兩種算法的定位誤差.

由于本文算法在定位中采取區域劃分的原則, 數據包只能擴散至節點周邊區域, 相比于傳統算法洪泛整個網絡的做法, 大大降低了節點的能耗和系統的通信開銷.

4 總結

本文首先介紹了DV-Hop定位算法, 分析了該算法在特定環境下影響定位誤差的因素, 并針對實際應用環境, 將原有的算法進行了改進, 提高了定位精度的同時也節約了網絡資源與系統開銷. 算法分析得到的數據和仿真實驗數據表明, 該算法在節點密集程度不同的環境下可保證較高的定位精度, 同時優化后的算法可根據實際應用環境調整最大跳數及低連通信標閾值達到最佳的定位效果, 具備可用性及適用性.

1 孫利民,李建中,陳渝.無線傳感器網絡.北京:清華大學出版社,2005.

2 黃俊杰,劉士興,干小宇,尹坤.基于節點密度的改進型DV-Hop算法.電子科技,2015,8:67–70.

3 王書聰.無線傳感器網絡分布式定位算法研究.計算機技術與發展,2008,11:62–65.

4 趙靈鍇,洪志全.基于無線傳感器網絡的DV-Hop定位算法的改進.計算機應用,2011,5:1189–1192.

5 張曉龍,解慧英,趙小建.無線傳感器網絡中一種改進的DV-Hop定位算法.計算機應用,2007,11:2672–2674.

6 余磊,余成波,祝松健,等.基于跳距修正加權DV-Hop的WSN定位算法.壓電與聲光,2013,6:899–902.

7 Doremami F, Javadi HHS, Farahi A. A new distributed weighted multidimensional scaling algorithm for localization in wireless sensor networks. International Journal of Computer Science & Engineering Survey, 2011, 2(1): 39–64.

8 Hu Y, Li X. An improvement of DV-Hop localization algorithm for wireless sensor networks. Telecommunication Systems, 2013, 53(1): 13–18.

9 Li S, Ding X, Yang T. Analysis of five typical localization algorithms for wireless sensor networks. Wireless Sensor Network, 2015, 7(4): 27–33.

Error Analysis and Improvement of DV-Hop Location Algorithm

LI Jing-Zhao1, SUN Rui2, TAN Da-Yu212(School of Electrical and Information Engineering, Anhui University of Science and Technology, Huainan 232001, China) (School of Computer Science and Engineering, Anhui University of Science and Technology, Huainan 232001, China)

When the sensor nodes collect data in the forest or water environment, the signal intensity and the signal transmission speed are affected by the obstacles or transmission media, which affects the measurement accuracy of localization algorithm based on the signal information. Taking into account the cost of nodes and the dynamic nature of nodes, DV-Hop positioning algorithm has excellent applicability and practicality. This paper analyses the factors influencing the accuracy of DV-Hop algorithm, proposes a formula for measuring the degree of uniformity of nodes, optimized the algorithm. The simulation results show that the optimized algorithm has higher positioning accuracy.

wireless sensor network(wsn); positioning; DV-Hop

國家自然科學基金(61170060);安徽省學術與技術帶頭人學術科研活動(2015D046);安徽省高等學校優秀拔尖人才資助項目(gxbjZD2016044)

2016-07-25;收到修改稿時間:2016-09-23

10.15888/j.cnki.csa.005738