無線傳感器網(wǎng)絡(luò)DV-HOP定位算法的改進(jìn)*

李 輝，熊盛武，劉 毅，段鵬飛

(武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，武漢430070)

無線傳感器網(wǎng)絡(luò)［1－4］集傳感器技術(shù)、微機(jī)電系統(tǒng)技術(shù)、無線通信技術(shù)、嵌入式計(jì)算技術(shù)和分布式信息處理技術(shù)于一體，通過傳感器與外界交互，并完成數(shù)據(jù)采集、處理及通信等功能，廣泛應(yīng)用于環(huán)境、交通、軍事、航空、醫(yī)療衛(wèi)生等多方面。而對于大多數(shù)應(yīng)用來說，沒有時空標(biāo)識的數(shù)據(jù)用處有限，因此，節(jié)點(diǎn)的準(zhǔn)確定位在傳感器網(wǎng)絡(luò)的應(yīng)用中起關(guān)鍵作用［5］。

現(xiàn)有的定位算法大致可分為兩類:距離相關(guān)定位算法 (Range-based)［6］和距離無關(guān)定位算法(Range-free)［7］。距離相關(guān)定位算法通過測量距離角度等信息來進(jìn)行定位，對硬件要求較高且成本較高，這與無線傳感器網(wǎng)絡(luò)的硬件要求簡單和能量消耗受限不相適應(yīng).。而距離無關(guān)算法不需要使用測距技術(shù)，只利用節(jié)點(diǎn)間的估計(jì)距離來計(jì)算未知節(jié)點(diǎn)的位置，因此由于傳感器節(jié)點(diǎn)能源、成本、體積等因素的限制，距離無關(guān)定位算法具有更高的實(shí)用性。

文中首先描述DV-Hop定位算法的基本原理和誤差產(chǎn)生的原因，然后針對DV-Hop算法和目前已有的改進(jìn)算法的不足，提出了改進(jìn)的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法(IDV-Hop定位算法)，最后將IDV-Hop與傳統(tǒng)的DV-Hop算法和已有改進(jìn)算法進(jìn)行分析比較，仿真結(jié)果表明，本文提出的IDV-Hop定位算法進(jìn)一步提高了定位精度。

1 DV-Hop定位算法誤差分析

DV-Hop定位算法［8－9］是一種基于距離矢量計(jì)算跳數(shù)的算法，其基本思想是將未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)之間的距離用平均每跳距離和兩者之間跳數(shù)的乘積表示，使用三邊定位法或最大似然估計(jì)法獲得未知節(jié)點(diǎn)位置信息。

1.1 誤差分析

由DV-Hop定位算法的原理可知，該算法的主要誤差在于計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的估計(jì)距離時，是用跳數(shù)乘以平均每跳距離來表示，而當(dāng)網(wǎng)絡(luò)中的跳數(shù)大于或等于2跳時，未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)之間的實(shí)際距離與平均每跳距離所得的值存在較大的誤差，會使定位精度下降。

圖1 信標(biāo)節(jié)點(diǎn)與未知節(jié)點(diǎn)距離示意圖

信標(biāo)節(jié)點(diǎn)L1與未知節(jié)點(diǎn)A的實(shí)際距離(粗虛線)用跳數(shù)乘以平均每跳距離(細(xì)虛線)代替，此時，會產(chǎn)生較大誤差。因此，針對傳統(tǒng)DV-Hop算法的缺點(diǎn)，文獻(xiàn)［10］對算法的改進(jìn)主要是在第2階段，當(dāng)每個信標(biāo)節(jié)點(diǎn)計(jì)算出自已的平均每跳距離以后，將自已的平均每跳距離作為一個校正值廣播至網(wǎng)絡(luò)中。廣播的數(shù)據(jù)分組格式為{idi，Ci}，Ci是第i信標(biāo)節(jié)點(diǎn)計(jì)算出的平均每跳距離。每個接收到此數(shù)據(jù)分組的節(jié)點(diǎn)將該信息添加到自已的數(shù)據(jù)表中，然后繼續(xù)向其鄰居廣播，重復(fù)id的信息分組將被丟棄。經(jīng)過此階段的廣播后，所有節(jié)點(diǎn)都已知所有信標(biāo)節(jié)點(diǎn)的平均每跳距離，然后再將所有的平均每跳距離相加取平均，得到整個網(wǎng)絡(luò)的平均每跳距離為:

其中:Ci是第i個信標(biāo)節(jié)點(diǎn)計(jì)算的平均每跳距離;n為網(wǎng)絡(luò)中的信標(biāo)節(jié)點(diǎn)總數(shù)。

之后，每個未知節(jié)點(diǎn)計(jì)算到自已數(shù)據(jù)表中的各信標(biāo)節(jié)點(diǎn)的距離為:

2 IDV-Hop定位算法

在文獻(xiàn)［10］中，利用整個網(wǎng)絡(luò)信標(biāo)節(jié)點(diǎn)的平均每跳距離代替原始算法中最近信標(biāo)節(jié)點(diǎn)的平均每跳距離，從而使未知節(jié)點(diǎn)計(jì)算到各信標(biāo)節(jié)點(diǎn)之間的估計(jì)距離更接近實(shí)際距離，使得改進(jìn)算法的平均定位精度得到提高，但是所有未知節(jié)點(diǎn)都用一個全網(wǎng)平均每跳距離，這樣計(jì)算出的未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離與實(shí)際距離仍存在誤差。針對此問題，本文對未知節(jié)點(diǎn)計(jì)算到信標(biāo)節(jié)點(diǎn)距離時，所用到的平均每跳距離做了進(jìn)一步改進(jìn)。

2.1 前提假設(shè)

為了討論方便，本文做出如下假設(shè):

(1)每個傳感器節(jié)點(diǎn)有唯一的ID，傳感器節(jié)點(diǎn)被隨機(jī)部署;

(2)空間信號傳輸模型為理想的球體;

(3)所有傳感器節(jié)點(diǎn)都是一樣的，電量和計(jì)算能力有限;

(4)信標(biāo)節(jié)點(diǎn)能夠通過GPS接受裝置或其他手段［11－12］即時地獲取二維坐標(biāo)信息;

(5)所有傳感器節(jié)點(diǎn)和錨節(jié)點(diǎn)是時間同步的。

2.2 IDV-Hop定位算法描述

2.2.1 計(jì)算最小跳數(shù)

首先，所有信標(biāo)節(jié)點(diǎn)向網(wǎng)絡(luò)廣播消息，消息中包括表{Xi，Yi，HopCount}，信標(biāo)節(jié)點(diǎn)只與網(wǎng)絡(luò)中鄰近的節(jié)點(diǎn)交換信息。Xi，Yi是信標(biāo)節(jié)點(diǎn)的坐標(biāo)，HopCount是節(jié)點(diǎn)接收到廣播消息信標(biāo)節(jié)點(diǎn)的跳數(shù)，初始值設(shè)為0。當(dāng)某個節(jié)點(diǎn)接收到這個表的消息，將HopCount值加1后繼續(xù)向它的鄰居廣播(除了來源方向)，如果某節(jié)點(diǎn)接收到來自相同信標(biāo)節(jié)點(diǎn)的多個消息，則表明它到該信標(biāo)節(jié)點(diǎn)有多條路徑。此時，節(jié)點(diǎn)將保留含有最小跳數(shù)值的信標(biāo)，而忽略其他信標(biāo)，這就保證了所得到的跳數(shù)值是它到信標(biāo)節(jié)點(diǎn)的最短路徑。最終，經(jīng)過這個過程，只要整個網(wǎng)絡(luò)是連通圖，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)都能獲得各信標(biāo)節(jié)點(diǎn)的坐標(biāo)以及它到各信標(biāo)節(jié)點(diǎn)的最短距離，也就是跳數(shù)。

2.2.2 計(jì)算未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)的距離

按照DV-Hop算法中第二階段，每個信標(biāo)節(jié)點(diǎn)計(jì)算出自已的平均每跳距離，即校正值，然后未知節(jié)點(diǎn)首先按文獻(xiàn)［10］的方法計(jì)算出全網(wǎng)平均每跳距離Average(如式1所示)，之后得出信標(biāo)節(jié)點(diǎn)i的平均每跳距離誤差，如式(3):

其中，節(jié)點(diǎn)j為信標(biāo)節(jié)點(diǎn)i數(shù)據(jù)表中的其他信標(biāo)節(jié)點(diǎn);|dtrueij－destimatedij|表示信標(biāo)節(jié)點(diǎn) i、j之間實(shí)際距離與計(jì)算距離之差的絕對值;anchor_to_anchorij表示信標(biāo)節(jié)點(diǎn)i到信標(biāo)節(jié)點(diǎn)j的最小跳數(shù)

最終，信標(biāo)節(jié)點(diǎn)i的平均每跳距離，即校正值為:

其中，k為變量參數(shù)，k的取值根據(jù)具體的網(wǎng)絡(luò)環(huán)境而定。

這樣，各信標(biāo)節(jié)點(diǎn)將自已按式5計(jì)算出的平均每跳距離anchor(i)作為一個校正值廣播至網(wǎng)絡(luò)中，校正值采用可控洪泛法在網(wǎng)絡(luò)中傳播，這意味著未知節(jié)點(diǎn)僅接受獲得的第1個校正值，而丟棄所有后來者，這個策略確保了絕大多數(shù)未知節(jié)點(diǎn)可從最近的信標(biāo)節(jié)點(diǎn)接收校正值。

最終，每個未知節(jié)點(diǎn)計(jì)算到自已數(shù)據(jù)表中的各個信標(biāo)節(jié)點(diǎn)的估計(jì)距離為:

其中，anchor(i)為未知節(jié)點(diǎn)i獲得的最近的信標(biāo)節(jié)點(diǎn)校正值，hopij為未知節(jié)點(diǎn)i到信標(biāo)節(jié)點(diǎn)j的最小跳數(shù)。

2.2.3 計(jì)算未知節(jié)點(diǎn)坐標(biāo)

在傳統(tǒng)DV-Hop定位算法中，未知節(jié)點(diǎn)利用記錄3個以上到各個信標(biāo)節(jié)點(diǎn)的距離值，通過三邊測量法或極大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)的坐標(biāo)，而對于在其通信范圍內(nèi)少于3個信標(biāo)節(jié)點(diǎn)的未知節(jié)點(diǎn)沒有進(jìn)行處理，從而造成有些節(jié)點(diǎn)無法定位。在IDV-Hop定位算法中對出現(xiàn)的這些節(jié)點(diǎn)也進(jìn)行了處理，方法如下:

(1)當(dāng)k大于或等于3時，設(shè)某未知節(jié)點(diǎn)在其通信范圍內(nèi)可參考的信標(biāo)節(jié)點(diǎn)數(shù)為k，未知節(jié)點(diǎn)A通信范圍內(nèi)的信標(biāo)節(jié)點(diǎn)為P1、P2、P3…Pk，取離未知節(jié)點(diǎn)A最近的3個信標(biāo)節(jié)點(diǎn)P1、P2、P3。則:

①當(dāng)向量P1P2和向量P2P3的笛卡爾乘積為0時，說明3個信標(biāo)節(jié)點(diǎn)在同一直線，此時去掉信標(biāo)節(jié)點(diǎn)P1、P2、P3中離節(jié)點(diǎn)A最遠(yuǎn)的一個，重新選取除節(jié)點(diǎn)P1、P2、P3以外距離節(jié)點(diǎn) A較近的信標(biāo)節(jié)點(diǎn) P4，然后返回①中重新判斷，直到未知節(jié)點(diǎn)參考的3個信標(biāo)節(jié)點(diǎn)不在同一直線。

②當(dāng)向量P1P2和向量P2P3的笛卡爾乘積不為0時，利用二維定位算法中的最小二乘法來求出未知節(jié)點(diǎn)的近似坐標(biāo)，方法如下:設(shè)3個信標(biāo)節(jié)點(diǎn)坐標(biāo)P1(x1，y1)，P2(x2，y2)，P3(x3，y3)，未知節(jié)點(diǎn)離各錨節(jié)點(diǎn)的距離分別是 d1，d2，d3，建立方程組:

因?yàn)槲粗?jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的距離，避免不了和實(shí)際距離di有一定的誤差，設(shè)ξ是距離測量誤差，整理可得是 k－1維隨機(jī)誤差向量。由矩陣方程可得ξ=b－Ax，ξ越小，定位越準(zhǔn)確，利用最小二乘法原理可以求出待測節(jié)點(diǎn)坐標(biāo)的估計(jì)式:

(2)當(dāng)K等于2時，未知節(jié)點(diǎn)與兩個錨節(jié)點(diǎn)在一個平面上(設(shè)未知節(jié)點(diǎn)為P，兩個錨節(jié)點(diǎn)為N0，N1)，則分別以N0，N1為圓心，以N0P，N1P為半徑的兩圓相交，如果交于一點(diǎn)時，則為所求的P點(diǎn);如果交于兩點(diǎn)(x1，y1)和(x2，y2)，則取為P點(diǎn)。

2.3 算法分析

根據(jù)IDV-Hop算法的實(shí)現(xiàn)過程，對其通信開銷能耗進(jìn)行分析，結(jié)果如下:

算法采取可控的洪泛過程，每個節(jié)點(diǎn)只轉(zhuǎn)發(fā)相同的消息一次，每個錨節(jié)點(diǎn)共發(fā)3次消息，其中包括(1)錨節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播自身位置信息;(2)各錨節(jié)點(diǎn)將自已的平均每跳距離作為一個校正值廣播至網(wǎng)絡(luò);(3)各錨節(jié)點(diǎn)將自已修正后的校正值廣播至網(wǎng)絡(luò)中。這些消息被所有節(jié)點(diǎn)轉(zhuǎn)發(fā)一次，假設(shè)一共有m個錨節(jié)點(diǎn)，n個未知節(jié)點(diǎn)，則網(wǎng)內(nèi)的消息量為(3·m·n)packets。

3 實(shí)驗(yàn)仿真及分析

為了驗(yàn)證本文IDV-Hop定位算法的可行性和有效性，對算法進(jìn)行仿真實(shí)驗(yàn)，并將DV-Hop算法、已有改進(jìn)算法和本文IDV-Hop定位算法的仿真結(jié)果進(jìn)行了對比分析。

3.1 仿真環(huán)境和參數(shù)

實(shí)驗(yàn)在 MATLAB 2009 的環(huán)境下進(jìn)行［13－14］，網(wǎng)絡(luò)中共有300個傳感器節(jié)點(diǎn)隨機(jī)地布設(shè)在1 000 m×1 000 m的二維區(qū)域內(nèi)，錨節(jié)點(diǎn)比例為20%，采用隨機(jī)布撒的方式，所有節(jié)點(diǎn)的分布如圖2所示，此時網(wǎng)絡(luò)的平均連通度為31.893 3，網(wǎng)絡(luò)的鄰居信標(biāo)節(jié)點(diǎn)平均數(shù)目為6.553 3。在實(shí)驗(yàn)中，假定所有未知節(jié)點(diǎn)和錨節(jié)點(diǎn)的通信半徑為200 m，信道衰減指數(shù)為4，運(yùn)行50次。

圖2 節(jié)點(diǎn)隨機(jī)分布圖

3.2 性能分析與比較

圖3比較了改進(jìn)算法中變量k的不同取值對算法定位精度的影響。從圖可以看出，當(dāng)節(jié)點(diǎn)總數(shù)和信標(biāo)節(jié)點(diǎn)數(shù)均恒定的情況下，定位精度取決于變量參數(shù)k的值;當(dāng)變量參數(shù)k的值為定值的情況下，定位精度取決于網(wǎng)絡(luò)中信標(biāo)節(jié)點(diǎn)的比例。從三條曲線可以看出，k的取值區(qū)間為［0.5 0.9］時，定位精度較小，尤其是當(dāng)k取值在0.7左右。

圖3 不同k值對定位精度的影響

改進(jìn)后定位算法的定位結(jié)果如圖4所示，其中線段連接的是未知節(jié)點(diǎn)實(shí)際位置與估計(jì)位置，圓代表未知節(jié)點(diǎn)實(shí)際位置，線段越長表示估計(jì)出的未知節(jié)點(diǎn)誤差越大，從圖中整體可以看出，改進(jìn)后估計(jì)出的未知節(jié)點(diǎn)坐標(biāo)與實(shí)際位置誤差較小。

圖4 IDV-Hop定位算法中未知節(jié)點(diǎn)實(shí)際位置與估計(jì)位置

圖5出示了改進(jìn)后定位算法在節(jié)點(diǎn)數(shù)為300，信標(biāo)節(jié)點(diǎn)比例為20%，k值為0.7時，每個未知節(jié)點(diǎn)的定位精度，從圖中可以看出，大部分未知節(jié)點(diǎn)的定位精度都在30%以內(nèi)，部分未知節(jié)點(diǎn)的定位精度達(dá)到10%以內(nèi)。

圖5 IDV-Hop定位算法中各個未知節(jié)點(diǎn)的定位精度

將本文改進(jìn)算法中變量k取值為0.7，與原DVHop算法、已有改進(jìn)算法的定位精度進(jìn)行比較。圖6中網(wǎng)絡(luò)節(jié)點(diǎn)為300，信標(biāo)節(jié)點(diǎn)比例分別為5%、10%、15%、20%、25%、30%、35%時三種算法定位精度的比較情況，從仿真結(jié)果可知，在節(jié)點(diǎn)總數(shù)不變的情況下，三種定位算法的定位精度總體上都隨信標(biāo)節(jié)點(diǎn)的增加而提高，本文改進(jìn)算法的定位精度比已有DV-Hop改進(jìn)算法平均提高了3.6%，比DVHop算法平均提高了5.9%。

圖6 錨節(jié)點(diǎn)數(shù)量對定位誤差的影響

4 總結(jié)

節(jié)點(diǎn)定位在無線傳感器網(wǎng)絡(luò)的應(yīng)用中起著重要作用，文中對DV-Hop算法原理以及產(chǎn)生誤差的原因進(jìn)行了分析，并針對原算法以及已有改進(jìn)算法在未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)距離計(jì)算中的不足，對信標(biāo)節(jié)點(diǎn)的平均每跳距離做出了改進(jìn)，并消除了因拓?fù)浣Y(jié)構(gòu)而造成的不可定位節(jié)點(diǎn)，通過仿真實(shí)驗(yàn)結(jié)果可以看出，改進(jìn)后的算法優(yōu)于原算法和已有改進(jìn)算法，提高了定位精度。由于該算法仍需要布設(shè)一定數(shù)量的錨節(jié)點(diǎn)來計(jì)算校正值，雖然數(shù)量不大但增加了成本，下一步將致力于研究采用單個移動錨節(jié)點(diǎn)來對三維空間中未知節(jié)點(diǎn)進(jìn)行定位，使算法更加優(yōu)化。

［1］杜治高，錢德沛，劉鐵.無線傳感器網(wǎng)絡(luò)中的地址分配協(xié)議［J］.軟件學(xué)報，2009，20(10):2787－2798.

［2］王福豹，史龍，任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法［J］.軟件學(xué)報，2003，16(05):857－868.

［3］Arampatzis T，Lygeros J，Manesis S.A Survey of Applications of Wireless Sensors and Wireless Sensor Networks［C］//Proceedings of the IEEE International Symposium on Mediterrean Conference on Control and Automation，Limassol，Cyprus，2005:719－724.

［4］Demirkol I，Ersoy C，Alagoz F.MAC Protocols for Wireless Sensor Networks:A Survey［J］.IEEE Communications Magazine，2006，44(4):115－121.

［5］Jun Xiao，Hong Chen，Shi Zhang.Research of Range-Based Synergetic Localization Algorithm in Wireless Sensor Networks［C］//Chinese Control and Decision Conference 2008.Shandong.China:IEEE，2008:2040－2044.

［6］楊鳳，史浩山，朱靈波，等.一種基于測距的無線傳感器網(wǎng)絡(luò)智能定位算法［J］.傳感技術(shù)學(xué)報，2008，21(1):135－140.

［7］Basagni S，Carosi A，Melachrinoudis E，et al.Protocols and Model for Sink Mobility in Wireless Sensor Networks［J］.ACM SIGMOBILE Mobile Computing and Communications Review，2006(10):28－30.

［8］王新生，趙衍靜，李海濤.基于DV-Hop定位算法的改進(jìn)研究［J］.計(jì)算機(jī)科學(xué)，2011，38(02):76－78.

［9］劉少強(qiáng)，龐新苗，樊曉平，等.一種有效提高節(jié)點(diǎn)定位精度的改進(jìn) DV-Hop算法［J］.傳感技術(shù)學(xué)報，2010，23(8):1179－1183.

［10］彭剛，曹元大，孫利民.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位機(jī)制的研究［J］.計(jì)算機(jī)工程與應(yīng)用，2004，40(35):27－29，83.

［11］Shen X，Wang Z，Jiang P，et al.Connectivity and RSSI Based Localization Scheme for Wireless Sensor Networks［C］//2005 International Conference on Intelligent Computing，Lecture Notes on Computer Science.Vol.3645，p.578－587，Aug.2005.

［12］張品秀，黃操軍，喬相偉.基于自適應(yīng)擴(kuò)展Kalman濾波的SINS/GPS 深組合研究［J］.傳感技術(shù)學(xué)報，2010，23(3):408－412.

［13］張葛樣，李娜.MTLAB仿真技術(shù)與應(yīng)用［M］.北京:清華大學(xué)出版社，2003.

［14］邱曉林.基于MATLAB的動態(tài)模型與系統(tǒng)仿真工具［M］.西安:西安交通大學(xué)出版社.2003.