無線傳感器網絡中ＤＶ－Ｈｏｐ節點定位改進算法研究

（1.重慶郵電大學 移動通信技術重點實驗室，重慶 400065； 2.重慶大學，重慶 400044）

摘 要：

介紹了無線傳感器網絡中DV-Hop算法的定位原理、誤差來源。針對DV-Hop算法在未知節點到信標節點距離計算中的不足，在分析信標節點間估計距離與真實距離誤差的基礎上，提出了改進算法。改進算法修正了網絡平均每跳距離與未知節點估計坐標的區域范圍。仿真結果表明，在相同的網絡環境下，改進算法的定位精度得到明顯提高。

關鍵詞：無線傳感器網絡； 距離矢量—跳段；定位精度

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2009)04-1272-04

Study for improved DV-Hop localization algorithm in WSN

LIN Jin-zhao1，2， LIU Hai-bo1， LI Guo-jun1， LIU Zhan-jun1

(1. Key Laboratory of Mobile Communications Technology， Chongqing University of Posts Telecommunications， Chongqing 400065， China; 2.Chongqing University， Chongqing 400044， China)

Abstract:

This paper introduced the localization principle and the error source of DV-Hop algorithm in the wireless sensor networks. To overcome the disadvantage of DV-Hop algorithm when it was used to compute the distance of unknown nodes and beacon nodes， worked out an improved algorithm which was based on analyzing the error between estimated distance and real distance of beacon nodes. The improved algorithm revised the average distance of each hop in networks and the area range of estimated coordinate of unknown nodes. Results of the simulation show that the improved algorithm has a better performance than the original algorithm in localization accuracy at the same network environment.

Key words：wireless sensor networks(WSN); DV-Hop; localization accuracy

0 引言

位置信息對傳感器網絡的監測活動至關重要，事件發生的位置和獲取信息的節點位置是傳感器節點監測消息中所包含的重要信息，沒有位置的監測消息毫無意義。傳感器節點的自身定位是根據少數已知位置的節點，按照某種定位機制確定自身的位置。無線傳感器網絡的自身定位系統和算法的性能直接影響其可用性，對于它們的評價主要有以下幾個標準[1]：

a）定位精度。這是定位技術的首要指標，一般用誤差值與節點無線射程的比例表示。例如，定位精度為30%表示定位誤差相當于節點無線射程的30%。

b)信標節點密度。網絡中已知自身位置的節點占節點總數的比例。一般信標節點的密度越大，定位精度越高，但定位的成本也就越大。

c)節點密度。因為節點密度會影響WSN的網絡連通度，在連通度大的網絡中，節點可以獲得更多的定位輔助信息。節點密度通常用網絡的平均連通度表示。

d）功耗。由于傳感器節點電池能量有限，在保證定位精度的前提下，與功耗密切相關的定位所需的計算量、通信開銷、存儲開銷、時間復雜性是一組關鍵性指標。

e)定位代價。包括時間、空間、成本等多種代價，主要是由定位算法決定節點的硬件設施。

根據定位機制，可將現有的無線傳感器網絡自身定位算法分為Range-based和range-free兩類[2]。前者需要通過測量節點間點到點的距離或角度信息；后者無須距離和角度信息，僅根據網絡連通性等信息實現節點的定位。Range-based定位機制對網絡的硬件設施提出了較高要求，這類算法在獲得相對精確定位結果時，都要產生大量計算和通信開銷。因此，range-free定位機制憑借其在成本、功耗方面的優勢，受到越來越多的關注[3]，如DV-Hop算法[4，5]、APIT[6]和MDS-MAP[7]算法等。

DV-Hop算法是目前應用最廣泛的定位算法之一，針對DV-Hop改進算法的研究，國內已取得了一些研究成果，如文獻[8~11]等。改進算法自身的缺陷性，如：定位精度提高不明顯；在提高定位精度的同時，增加了節點的通信開銷、計算量、能量消耗等。因此，就這些改進算法而言，仍存在被改進的可能。本文針對DV-Hop算法[4，5]在定位精度方面的不足，在綜合分析DV-Hop算法[4，5]及已有DV-Hop改進算法[8]優缺點的基礎上，提出了本文通過修正網絡平均每跳距離及未知節點估計坐標的區域范圍，以提高定位精度的改進方案。

1 算法描述

DV-Hop定位算法是一種基于距離矢量計算跳數的算法，其基本思想是將未知節點到信標節點之間的距離用平均每跳距離和兩者之間跳數的乘積表示，使用三邊定位法或最大似然估計法獲得未知節點位置信息。

1.1 DV-Hop算法

 DV-Hop算法的定位過程主要分為：

a）信息廣播與距離計算過程。在這一過程，主要有兩個信標節點廣播數據分組階段。第一階段：每個信標節點將其位置信息以數據分組的形式在網絡中廣播出去，分組的格式為{idi，xi，yi，hopsi}，其中包含了該信標節點的idi號、位置信息(xi，yi)以及跳數信息hopsi，初始化hopsi為0。接收到此分組的每個鄰居節點（可能是信標節點，也可能是未知節點）將hopsi改為hopsi+1，并將該分組信息以{idi，xi，yi，hopsi}的格式存儲到自己的數據表中（網絡中的每個節點都維持著這樣的一張數據表，用于記錄信標節點的信息），然后繼續向新的鄰居節點廣播。

當節點接收到一個idi號相同的數據分組時，便與自己數據表中相同idi號信息的hopsi比較。若新的跳數小于數據表中已存在的跳數，就用新的跳數更新數據表中的跳數信息；否則丟棄該數據分組，也不再進行轉發。

這樣以泛洪的形式在整個網絡中廣播每個信標節點的信息，使得每個未知節點統計出距離每個信標節點的最短跳數和坐標信息，同時信標節點也獲得距離其他所有信標節點的最短跳數和坐標信息。這樣信標節點i可利用式(1)計算平均每跳距離：

Ci=∑i≠j(xi-xj)2+(yi-yj)2/∑i≠jhopsij(1)

其中： j為信標節點i數據表中的其他信標節點； hopsij為信標節點 i和信標節點 j之間的跳數。

第二階段：每個信標節點將自己計算的平均每跳距離以數據分組的形式廣播至網絡中，其分組格式為{idi， Ci}。未知節點僅接收距離自己跳數最少的那個信標節點發送的分組信息，并把該數據分組中的平均每跳距離存入到自己的數據表中，然后繼續向其鄰居廣播該數據分組。 當遇到idi號重復的數據分組時便丟棄。這個策略確保了大多數未知節點從距離自己最近的信標節點接收到平均每跳距離值。未知節點接收到平均每跳距離后，根據自己數據表中記錄的跳數，計算到每個信標節點的距離，如圖1所示。



假設有信標節點i、j、k，信標節點i與j和k之間的實際距離已知，分別為dij和dik（其中：dij=(xi-xj)2+(yi-yj)2），跳數hij為3跳和hik為4跳，則信標節點i計算的平均每跳距離為

Ci=(dij+dik)/(hij+hik)=(dij+dik)/（3+4)

在圖1中，假設節點p為未知節點，可知信標節點i、j、k中的i與p之間的跳數最少，即距離p最近。因此，未知節點p從i處獲取平均每跳距離值，從而計算出它與信標節點i、j、k的距離分別為1×Ci，3×Ci，4×Ci。

b)定位與誤差分析過程。未知節點利用第二階段中計算出的到各個信標節點的距離，利用三邊測量法或多邊測量法的最大似然估計法(MLE)計算自身坐標。

誤差分析：在DV-Hop算法中，由于采用信標節點之間的平均每跳距離作為未知節點到信標節點的平均每跳距離，通過平均每跳距離與跳數的乘積來表示未知節點與信標節點之間的距離，即用跳段距離代替直線跳距離。然而在實際的網絡拓撲中，信標節點到未知節點往往不是直線路徑，使用DV-Hop算法會帶來較大的距離誤差[11]。

以圖1的拓撲為例，通過DV-Hop算法，未知節點p計算得到它到信標節點 k的距離為 4×Ci，但 p、 k間的實際距離為 dpk，以此計算距離解出的未知節點的坐標可能遠遠偏離真實坐標。因此，如何提高DV-Hop算法的定位精度，關鍵就在于這個距離的計算上。實驗表明[2，3]：DV-Hop定位算法比較適合信標節點分布均勻、各向同行、密集型的無線傳感器網絡。因為在這種情況下求得的平均每跳距離值才能更接近實際距離。

1.2 已有DV-Hop改進算法[8]

針對傳統DV-Hop算法的不足，文獻[8]中改進算法的區別主要體現在定位的第一個過程中的第二個信標節點廣播數據分組階段。在這個階段，每個信標節點將自己計算的平均每跳距離作為一個校正值廣播至網絡中。其廣播的數據分組格式為{idi，Ci}， Ci是第 i個信標節點計算的到其他所有信標節點的平均每跳距離。每個接收到此數據分組的節點將該信息添加到自己的數據表中，然后繼續向其鄰居廣播，重復idi號的信息分組將被丟棄。經過此階段的廣播后，所有節點（包括信標節點和未知節點）都已知所有信標節點計算的平均每跳距離Ci，然后再將所有的平均每跳距離相加取平均，得到整個網絡的平均每跳距離為

cc=∑Ci/n(2)

其中： Ci是第 i個信標節點計算的平均每跳距離; n為網絡中的信標節點總數。

此時，每個未知節點計算到自己數據表中的各個信標節點的估計距離為

di=cc×hopsi(3)

未知節點獲得到三個及以上的信標節點的估計距離之后，執行三邊定位法或最大似然估計法算出自己的估計位置。

2 本文改進算法

文獻[8~11]均為改進的DV-Hop算法。文獻[12]是基于DV-Hop和DV-Distance的改進差分定位算法。各文獻的改進思路不同。本文在重點分析文獻[8]的基礎上，針對文獻[8]中的不足，提出了本文的改進思路。在文獻[8]中，利用全網平均每跳距離 cc代替最近信標節點的平均每跳距離 Ci，使未知節點與各信標節點之間的估計距離更接近于它們之間的真實距離，從而使得改進算法的平均定位精度得到提高。但是不難發現，當用計算出的全網平均每跳距離 cc去計算信標節點兩兩之間的估計距離時，發現它們之間的估計距離與真實距離存在誤差。可見，即使是以文獻[8]中改進算法思路計算出的全網平均每跳距離 cc與真實的平均每跳距離之間仍然存在誤差。因此，如何進一步改進全網平均每跳距離 cc，就成為本文改進算法的出發點。

本文改進算法是在得到全網平均每跳距離的基礎上，通過分析每個信標節點的平均每跳距離誤差，以進一步修正先前得到的全網平均每跳距離，使全網平均每跳距離更接近于真實的平均每跳距離，從而提高定位精度。

信標節點 i的平均每跳距離誤差定義為

err_disi=[∑i≠j|dtrue-destimate|ij/hopsij]/ni(4)

其中:節點 j為信標節點 i數據表中的其他信標節點; hopsij為信標節點 i、 j之間的跳數; ni為信標節點 i數據表中其他信標節點總數;|dtrue-destimate|ij表示信標節點 i、 j之間實際距離與計算距離之差的絕對值。

dtrue=(xi-xj)2+(yi-yj)2，destimate=cc×hopsij）

本文改進算法主要從兩個方面來提高定位精度：

a）每個信標節點計算自己的平均每跳距離誤差，以修正全網平均每跳距離。

b）對解出的估計坐標超出網絡區域的未知節點進行坐標修正。

改進算法具體描述如下：

a）相比于原始DV-Hop算法和已有改進算法[8]，本文改進算法在定位的第一個過程中增加了一個信標節點廣播數據分組階段。前兩個數據分組廣播階段與已有改進算法[8]完全相同，通過前兩個階段得到全網的平均每跳距離，然后每個信標節點通過式（4）計算出各自的平均每跳距離誤差，并將該平均每跳距離誤差以數據分組的形式廣播到網絡中去（即改進算法中增加的第三個數據分組廣播階段）。數據分組的格式為{idi，err_disi}，err_disi是第i個信標節點計算的到其他所有信標節點的平均每跳距離誤差。每個接收到此數據分組的節點將該信息添加到自己的數據表中，然后繼續向其鄰居廣播，重復idi號的信息分組將被丟棄。經過此階段的廣播后，所有節點（包括信標節點和未知節點）都已知所有信標節點計算的平均每跳距離誤差，然后再將所有的平均每跳距離誤差相加取平均，得到整個網絡的平均每跳距離誤差：

c_err_dis=∑err_disi/n(5)

其中：n為網絡中的信標節點總數。

通過該新增加的階段，每個未知節點得到整個網絡的平均每跳距離誤差。由于已經在第二個數據分組廣播階段后，得到了整個網絡的平均每跳距離cc，修正得到新的網絡平均每跳距離為

new_cc=cc+k×c_err_dis(6)

其中： k為變量參數，-1≤k≤1，k的取值隨具體的網絡環境而定，k值的大小影響著定位精度。

此時，每個未知節點計算到自己數據表中的各個信標節點的估計距離為

 di=new_cc×hopsi(7)

當未知節點得到三個及以上的信標節點的估計距離之后，執行三邊定位法或最大似然估計法算出自己的估計位置。

b）就網絡而言，網絡都有一定的大小區域，盡管該區域的具體大小可能不明確，但大體上可以估計該網絡區域邊界的上下限，如{Sarea|xmin≤xarea≤xmax，ymin≤yarea≤ymax} 。其中：xarea為網絡區域在x軸上的分量;yarea為網絡區域在y軸上的分量。由于未知節點到每個信標節點的計算距離與實際距離存在誤差，造成解出的某些未知節點的估計坐標超出了網絡區域范圍，增大了平均定位誤差。在本文改進算法中，對解出的估計坐標超出網絡區域范圍的未知節點進行坐標修正。具體修正規則如下：通過改進算法的a）方面，得到了能定位的每個未知節點的估計坐標，若解出的未知節點p的x軸坐標分量xp＜xmin，則規定未知節點p的x軸坐標分量xp=xmin；若解出的xp＞xmax，則規定未知節點p的x軸坐標分量xp=xmax。同理，對于未知節點p的y軸坐標分量，也作如上的規定。通過該坐標修正，減小了估計坐標超出網絡區域的那些未知節點的定位誤差，從而減小了整個的平均定位誤差。

3 實驗仿真及結果分析

為了驗證本文改進算法的可行性和有效性，在VC 6.0上對DV-Hop算法、已有DV-Hop改進算法和本文改進算法進行了仿真實驗，并對仿真結果進行了對比分析。仿真的網絡環境為[0，500]×[0，500]，節點通信半徑為100，信標節點和未知節點均隨機產生，仿真結果數據來自500次仿真的平均值。算法的性能主要從定位誤差方面進行了評估，仿真結果如圖2~5所示。



圖2比較了式（6）中變量參數 k的不同取值對本文改進算法定位誤差的影響。從仿真結果可知：當節點總數和信標節點數均恒定的情況下，定位誤差取決于變量參數 k的值；當變量參數k的值為定值的情況下，定位誤差取決于網絡中的節點總數和信標節點數。

從六條仿真曲線可知： k的取值區間為（0 0.6）時，六種網絡環境下的定位精度都能取得較好的值，但各種網絡環境下的最佳定位精度對應的 k值是不同的，無法定義出變量參數 k的統一表達式，使各種網絡環境下的定位精度都達到最佳值，因此只能尋求使各種網絡環境下定位精度都達到較好值時對應的變量參數 k的統一表達式。

圖3的網絡環境為隨機分布200個節點，且節點總數保持不變，式（6）中的變量參數取值為 k=n/(N-n)（n為網絡中的信標節點數；N為節點總數），信標節點的取值為5、8、10、15、20、25、30、35、40時，三種算法定位誤差的比較情況。從仿真結果可知，在節點總數不變的情況下，三種定位算法的定位精度都隨信標節點的增加而提高。本文改進算法的定位精度比已有DV-Hop改進算法平均提高了1%~4%，比DV-Hop算法平均提高了5%~7%。

圖4的網絡環境為隨機選取20個信標節點，且保持不變，式（6）中的變量參數取值為k=n/(N-n)（n為網絡中的信標節點數；N為節點總數），節點總數的取值為80、100、150、200、250、300、350、400時，三種算法定位誤差的比較情況。從仿真結果可知，在信標節點數不變的情況下，三種定位算法的定位精度都隨節點總數的增加而提高。本文改進算法的定位精度比已有DV-Hop改進算法平均提高了2%~5%；在節點總數比較少時，比DV-Hop算法平均提高了13%~22%;在節點總數比較多時，比DV-Hop算法平均提高了4%~5%。

在節點通信半徑不變的情況下，節點總數決定了網絡平均連通度。圖5反映了本文改進算法在不同平均連通度的情況下，式（6）中的變量參數取值為k=n/（N-n）（n為網絡中的信標節點數；N為節點總數），信標節點取值為5、8、10、15、20、25、30、35、40時，定位誤差的比較情況。從仿真結果可知，四種平均連通度情況下的定位精度都隨信標節點數的增加而提高；在平均連通度較低的情況下，平均連通度提高較小的值，定位精度提高的幅度比較大，如圖中的10.4和12.5兩種值的情況。隨著平均連通度值的進一步提高， 定位精度提高的幅度會逐漸減少，最終使定位精度趨于穩定。

4 結束語

本文改進算法使全網平均每跳距離更接近于真實的平均每跳距離，并對估計坐標超出網絡區域的未知節點進行了坐標修正，從而提高了定位精度。在仿真實驗中，比較了多種網絡環境下的定位精度。從仿真結果看，無論在哪種網絡環境下，本文改進算法的定位精度都優于已有DV-Hop改進算法和傳統DV-Hop算法。但改進也存在不足之處：式（6）中變量參數的取值問題，較好的取值是提高定位精度的有效途徑，因此尋求變量參數的較優解是以后研究工作的重點；改進算法中增加了一個信標節點廣播數據分組階段，必然造成節點通信量和計算量的增加，從而增加了節點能量的消耗，如何使改進算法在提高定位精度的同時，最大程度地減小節點的能量消耗，也是以后研究工作的重點。

參考文獻：

[1]AKYIDIZ I F， SU W， SANKARASUBRAMANIAM Y ， et al. A survey on sensor networks[J]. IEEE Communications Magazine，2002，40(8):102-114.

[2]王福豹，史龍，任豐原. 無線傳感器網絡中的自身定位系統和算法[J]. 軟件學報，2003，16(5):857-868.

[3]史龍，王福豹，段渭軍，等. 無線傳感器網絡range-free自身定位機制與算法[J]. 計算機工程與應用，2004，40(23):127-130.

[4]NICULESCU D， NATH B. Ad-hoc positioning systems (APS)[C]//Proc of 2001 IEEE Global Telecommunications Conference.[S.l.]:IEEE Communications Society， 2001:2926-2931.

[5]NICULESCU D， NATH B. DV based positioning in Ad hoc networks[J]. Journal of Telecommunication Systems， 2003，22(1/4):267-280.

[6]HE Tian，HUANG Cheng-du， BLUM B M， et al. Range-free localization schemes in large scale networks[C] //Proc of the 9th Annual International Conference on Mobile Computing and Networking. San Diego:ACM Press，2003:81-95.

[7]SHANG Y， RUML W， ZHANG Y， et al. Localization from mere connectivity[C]//Proc of the 4th ACM Int’l Symp on Mobile Ad hoc Networking Computing. Annapolis: ACM Press， 2003:201-212.

[8]彭剛，曹元大，孫利民. 無線傳感器網絡節點定位機制的研究[J].計算機工程與應用，2004， 40(35):27-29，83.

[9]馬祖長，孫怡寧.無線傳感器網絡節點的定位算法[J].計算機工程，2004，30(7):13-14，48.

[10]廖先林，耿娜，石凱，等.無線傳感器網絡節點自身定位算法[J]. 東北大學學報:自然科學版，2007，28(6):801-804.

[11]張曉龍，解慧英，趙小建.無線傳感器網絡中一種改進的DV-Hop定位算法[J]. 計算機應用，2007，27(11):2672-2674.

[12]劉林，范平志. 一種降低定位誤差的無線傳感器網絡節點定位改進算法[J].電路與系統學報，2007，12(2):1-4.