DV-Hop定位算法誤差分析與優(yōu)化①

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

DV-Hop定位算法誤差分析與優(yōu)化①

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

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

無線傳感器網(wǎng)絡; 定位; DV-Hop

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

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

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

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

1) 計算各個節(jié)點之間的最小跳數(shù)

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

2) 估算平均跳距

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

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

3) 計算未知節(jié)點位置

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

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

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

圖1 三邊定位求解圖

由上式可計算出未知節(jié)點的具體坐標, 從而實現(xiàn)對該節(jié)點的定位.

2 誤差分析

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

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

圖2 理想情況下的節(jié)點拓撲

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

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

連通度較低的信標節(jié)點會造成定位誤差, 如圖3所示的網(wǎng)絡拓撲環(huán)境.

圖3 節(jié)點網(wǎng)絡拓撲圖

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

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

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

圖4 三邊定位誤差分析

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

3 算法改進與仿真

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

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

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

使用Matlab對無線傳感器網(wǎng)絡中節(jié)點進行仿真,構造節(jié)點分布不均勻環(huán)境, 節(jié)點分布如圖5所示.

圖5 節(jié)點分布圖

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

圖6 各區(qū)域節(jié)點離散程度

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

表1 各區(qū)域節(jié)點離散程度表

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

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

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

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

i

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

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

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

基于以上分析, 其優(yōu)化后的算法如下所示:

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

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

2) 確定信標.

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

3) 估算未知節(jié)點廣播范圍內(nèi)節(jié)點的平均每跳距離.

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

優(yōu)化后的算法流程圖如圖7所示.

圖7 算法流程圖

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

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

對該網(wǎng)絡拓撲環(huán)境中的所有節(jié)點進行定位仿真,通過調(diào)整最大跳數(shù)與低連通度信標的閾值后達到最優(yōu)的定位效果, 如圖9所示.

圖9 定位效果圖

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

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

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

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

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

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

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

由于本文算法在定位中采取區(qū)域劃分的原則, 數(shù)據(jù)包只能擴散至節(jié)點周邊區(qū)域, 相比于傳統(tǒng)算法洪泛整個網(wǎng)絡的做法, 大大降低了節(jié)點的能耗和系統(tǒng)的通信開銷.

4 總結

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

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

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

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

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

5 張曉龍,解慧英,趙小建.無線傳感器網(wǎng)絡中一種改進的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);安徽省高等學校優(yōu)秀拔尖人才資助項目(gxbjZD2016044)

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

10.15888/j.cnki.csa.005738