無線傳感器網絡中Dv-Hop定位算法的改進

金 純，葉 誠，韓志斌，韓 剛，周曉軍

(1.重慶郵電大學通信與信息工程學院，重慶400065;2.重慶金甌科技發展有限責任公司，重慶400041;3.重慶廣通實業發展有限責任公司，重慶400039;4.重慶市旭鼎科技有限公司，重慶400065)

0 引言

無線傳感器網絡是由大量無線傳感器節點以Ad-Hoc的組網方式構成的無線網絡，其目的是感知、采集和處理其覆蓋區域中感知對象的信息［1-2］。無線傳感器網絡具有較高的應用前景，現已廣泛應用于軍事、環境、醫療等領域［3-4］。定位技術是無線傳感器網絡中多種應用的基礎，隨著無線傳感器網絡的蓬勃發展，與其息息相關的定位技術受到了人們較大的關注。

在無線傳感器網絡中，最簡單的定位方法是采用GPS定位系統，在傳感器節點內安裝GPS接收機，通過GPS接收機與衛星的通信，實現GPS接收機的定位功能。但是在實際應用中，無線傳感器網絡要求節點價格低廉，功耗和體積小，在這種限制下，通常只會將GPS接收機安裝于少數傳感器節點，這些傳感器節點稱為錨節點。無線傳感器網絡中的定位算法就是未知節點借助這些錨節點的坐標信息來實現節點自身的定位［2］。無線傳感器網絡中的定位算法分類標準有很多，使用較多的是依據是否需要測量節點間距離或角度等信息來分類，依照這種劃分，可以把定位算法分為基于距離的定位［5］和與距離無關的定位［6］。基于距離的定位機制一般定位精度相對較高，對節點的硬件通常也提出了較高要求，基于距離定位機制常用測距方法有RSSI(received signal strength indicator)、TOA(time of arrival)、TDOA(time difference on arrival)、AOA(angle of arrival)。與距離無關的定位機制無需實際測量節點間的絕對距離或方位，對節點硬件的要求低，使得節點成本更適合于大規模網絡。與距離無關的定位算法主要有質心算法、Dv-Hop算法、APIT算法、MDS-MAP算法等，現有技術中通常使用的是Dv-Hop(distance vector-hop)算法。近幾年，國內外學者主要圍繞上述經典算法，提出了許多的改進算法，進一步提高定位性能，使傳感器網絡能更好的應用于實際。本文主要是針對Dv-Hop算法的不足提出改進，并借助仿真工具加以驗證，得出了較優的性能。

1 Dv-Hop算法

Niculescu等人提出的Dv-Hop算法主要是利用典型的距離路由協議，得到所有節點之間的最小跳數，然后根據錨節點間的最小跳數估算平均每跳距離，再利用未知節點和錨節點的最小跳數與估算的平均每跳距離乘積代替未知節點與錨節點間的距離，最后利用三邊測量法或最小二乘法求未知節點的坐標，完成定位。

1.1 Dv-Hop算法的定位過程

Dv-Hop定位算法主要可以分為以下3個階段:

(1)計算未知節點與錨節點的最小跳數。

借助典型的距離矢量交換協議，錨節點向鄰居節點廣播自身位置的信息分組，其中包括跳數字段，初始化為0，接收節點記錄到每個錨節點的最小跳數，忽略來自同一錨節點的較大跳數的信息分組，將跳數加1再轉發給它的鄰居節點。通過這種方式使網絡中所有節點獲得它到其他節點的最小跳數。

(2)計算未知節點到錨節點間的距離。

錨節點根據第一階段獲得到其他錨節點間的最小跳數跟位置信息，利用式 (1)，可以獲得平均每跳距離

式 中:(xi，yi)，(xj，yj)——錨 節 點 i 和 j 的 坐 標，HopSizei——錨節點i的平均每跳距離。然后錨節點將這個平均每跳距離利用帶有生存限制的分組廣播至網絡中，使得離它較近的未知節點獲得相應的HopSizei，利用式 (2)就可以計算出未知節點到距離較近的幾個錨節點距離

式中:i——錨節點，j——未知節點，hopij—— i和 j的最小跳數。

(3)計算出未知節點的坐標，完成定位。

通過第2階段得到的未知節點到錨節點的距離，再利用極大似然估計法求出未知節點坐標。

假設未知節點的坐標為(x，y)，錨節點i的坐標為(xi，yi)(i=1，2，…，n)，未知節點與錨節點間的距離 di(i=1，2，…，n)由式 (3)計算出

對于式 (3)從第一個方程開始分別減去最后一個方程，可得

式 (4)的線性表達式為

X可以由式 (6)求出。

其中

1.2 Dv-Hop算法的誤差分析

無線傳感器網絡中，節點隨機分布，各節點之間的距離長短不一，節點密度分布也稀疏不同。而Dv-Hop算法中利用錨節點間計算得出的平均每跳距離，來代替網絡中未知節點到錨節點間的每跳距離，用其乘以跳數得出的值來作為未知節點到錨節點間的距離，顯然計算出的距離將會與真實距離存在較大的誤差，這種誤差是算法機制所帶來的，需要采取某些措施來減小定位誤差，提高定位精度。而未知節點與錨節點之間誤差的大小通常與估算的平均每跳值、未知節點到錨節點跳數多少等有關。一方面，跳數越多，未知節點與錨節點之間路徑偏離兩點直線連線的可能性越大，計算出的未知節點與錨節點距離與真實距離誤差越大。另一方面，用原本不精確的平均跳距乘以跳數得到的估算距離將隨跳數的增加，誤差也會累計增加。總的來說，在絕大多數情況下，未知節點與錨節點之間估算誤差的大小會隨著跳數的增加而增大。

2 Dv-Hop算法的改進

2.1 RRSI測距技術

RSSI是接收到信號強度大小的指示器，是一種利用信號的衰減來推測距離的測距技術［7］

式 (7)是目前使用較多的一種理論模型，Pr(d)是距離發射處d米接受到的信號功率，Pr(d0)是距離發射處d0米接收到的信號功率，n是路徑衰減因子，Xσ是均值為0、標準差為σ的高斯分布，實際計算中，d0通常取1米，Pr(d0)也取1米處的信號強度。而在目前常用的TI公司芯片CC2430中，有以下關系成立

借助于以上公式，可以得出如下公式

其中A=Pr(1)+RSSI_OFFEST。系數A跟n可以通過采集數據，進行擬合來得到，這樣就可以根據RSSI算出對應的距離d。文獻［7］對基于RSSI的測距進行了分析，其結論表明，在15米以內，RSSI測距有較高的精度。在15米以內用RSSI測距獲得的數據比原算法估算的數據更精確。

2.2 改進后的Dv-Hop算法

目前，已有很多學者和研究人員提出對Dv-Hop算法的改進策略［8-10］。文獻［8］中將錨節點分成圓形或者半圓形后再進行定位。文獻［9］中采用未知節點附近多個錨節點的加權平均跳距代替原算法中的平均跳距減少了跳距帶來的定位誤差。文獻［10］針對錨節點與未知節點之間的估計距離做出了修正，該修正值由多跳的校正者和錨節點平均每跳距離誤差所組成，由此提高定位精度。大部分改進都是針對Dv-Hop算法中第一二階段所進行的，通過修正未知節點與錨節點之間的距離，提高定位精度。

在算法第三階段中，用最小二乘法式 (3)計算時，每個方程都將減去最后一個方程，可見最后一個方程中估算的距離dn與真實距離之間誤差的大小將對計算出的未知節點坐標有很大的影響，如果最后的一組數據誤差很大，前面的(n－1)組數據再怎么精確，也會讓算出的結果跟真實位置之間存在很大的誤差。因此，本文的改進思路是基于選取一組誤差最小的數據構建第n個方程。

基于以上研究，本文做出如下改進:

(1)RSSI在15米以內，有較高的精確度，當未知節點與錨節點在15米以內時候采用RSSI算得的距離比原算法估算的距離誤差更小。因此，錨節點發起廣播信息時，在一跳范圍內的未知節點將根據RSSI計算它們之間的距離，如果計算出的值在15米以內，將直接用這個值作為它們之間的估算距離。

(2)對未知節點于錨節點之間的估算距離n(i=1，2，…，n)進行排序，選擇它們之間距離，最小的一組數據，來構建式 (3)中第n個方程。

3 仿真與分析

為了驗證改進后算法的性能，使用了matlab對Dv-Hop算法和改進后的Dv-Hop算法性能進行了仿真對比，并對結果進行了分析。

假設某未知節點實際坐標為 (xr，yr)，估計坐標為(xe，ye)，通信半徑為R。

絕對定位誤差定義為

相對定位誤差定義為

3.1 同一場景下，兩算法性能對比

為了最直觀的比較兩種算法的性能，在同一網絡場景下用兩種算法定位，分別給出了每個點在每種算法下的絕對誤差。如圖1所示，是在100*100的網絡環境下進行仿真實驗，節點總數200個，錨節點20，通信半徑R為15。

從圖1可看出改進后的Dv-Hop算法絕大部分節點絕對定位誤差比原算法小，而且改進后算法的方差也比原算法小。相對于原算法，改進后的Dv-Hop算法能有效的提高定位性能。

圖1 兩種算法下誤差對比

3.2 不同通信半徑下，算法性能對比

為了更全面的分析、評價改進后算法的性能。將節點通信半徑依次改變，比較算法在不同通信半徑下的性能。

圖2所示，也是在100*100的網絡環境下進行仿真實驗，節點總數200個，錨節點20，但通信半徑R由15依次累加，每個數據都是程序獨立運行500次后取的平均值。為了更好分析引入RSSI的作用，特意也將改進算法中引入RSSI的相關部分剔除作為一種新的算法對比，稱之為不完整改進算法以示區別。

從圖2中可以看出，不完整改進算法在通信半徑較小時候相對原算法能較大幅度的提高定位精度，但在R超過65后，不完整改進算法已不能提高算法性能。這是因為R較小時候，算法的平均每跳距離也較小，待定位節點一跳范圍內錨節點很少，甚至沒有，此時選擇離待定節點最近的錨節點，能保證未知節點與錨節點之間估算誤差較小。然而隨著R的增大，網絡平均每跳距離變大，待定節點一跳范圍內錨節點越來越多，因為一跳內的錨節點到待定節點的估計距離都由網絡平均每跳距離決定，此時只有距離跟網絡平均每跳距離數值越接近誤差才會越小，顯而易見再選擇離待定位節點較近的點已不能保證它們誤差最小，算法的性能亦不能得到提高。

圖2 不同通信半徑下算法性能比較

改進后的Dv-Hop算法，在引入較高精確度的RSSI測距，一跳范圍15米以內的點，其距離將不再依靠網絡平均每跳距離估算，直接RSSI測量，在用二乘法定位中采用此組數據構建第n個方程，對半徑的改變并沒有那么敏感。在R較小時候，改進算法雖然跟不完整改進算法差距不大，但隨著R的增加，改進算法性能提高較為明顯。

3.3 不同錨節點個數，算法性能對比

依舊在100*100的網絡環境下進行仿真實驗，節點總數200個，通信半徑為20，改變網絡中錨節點的個數，仿真算法在不同數目錨節點下的性能。

圖3所示仿真結果，隨著錨節點數目的提高，原算法和改進算法的性能都得到很大的提高。當錨節點達到一定比例，再提高錨節點數目，算法性能提高較緩慢，但改進后的Dv-Hop算法性能始終優于原算法。

圖3 不同錨節點數目下算法性能比較

4 結束語

國內外學者針對Dv-Hop算法的不足提出了許多改進算法，基本上都是圍繞如何減小節點間的估算距離誤差做出改進，但是卻很少有人關注到這種誤差對最后使用最小二乘法定位的影響。本文正是為了減小這種影響而提出的改進算法，通過借助RSSI測距，排序等手段對算法做出改進，減小節點估算距離誤差對最后定位的影響。仿真實驗證明，改進后的算法在沒有增加計算量和額外硬件的情況下，相對于原算法，顯著提高了定位性能。

［1］KIM S，KO JG，YOON J，et al.Multiple-objective metric for placing multiple base station in wireless sensor network［C］//Proceeding of the 2rd International Symposium on Wireless Pervasive Computing.Korea，2007:627-631.

［2］Jennifer Yick，Biswannath Mukherjee，Dipak Ghosal.Wireless sensor network survey ［J］.Computer Networks，2008，52(12):2292-2230.

［3］Mizugaki K，Fujiwara R，Nakagawa T，et al.Accurate wireless location/communication system with 22-cm error using UWB-IR［C］//Radio and Wireless Symposium.Washington，DC:IEEE，2007:455-458.

［4］Guoqiang MaoBaris，Fidan Localization.Algorithms and strategies for wireless sensor networks［M］.Information Science Reference，Release Date，2009.

［5］XIAO Jun，REN Lirong，TAN Jingdong.Research of TDOA based self-localization approach in wireless sensor network［C］//International Conference on Intelligent Robots and Systems.China，2006:2035-2040.

［6］LI M，LIU Y H.Rendered path:Range-free localization in anisotropic sensor networks with holes［J］.IEEE/ACM Transactions on Networking，2010，18(1):320-332.

［7］FANG Zheng，ZHAO Zhan.Ranging analysis based on RSSI［J］.Chinese Journal of Sensors and Actuators，2007，22(11):2526-2530(in Chinese).［方震，趙湛.基于RSSI測距分析 ［J］.傳感技術學報，2007，22(11):2526-2530.］

［8］Yassine F，Safa h.A hybrid Dv-Hop for localization in large scale wireless sensor network［C］//Proceeding of the 6th International Conference on Mobile Technology，Application and Systems.New York:ACM，2009:1-6.

［9］WAN Xinsheng，ZHAO Yanjing，LI Haitao.Research on improvement of algorithm Dv-Hop ［J］.Computer Science，2011，38(2):76-78(in Chinese).［王新生，趙衍靜，李海濤.基于Dv-Hop算法的改進研究 ［J］.計算機科學，2011，38(2):76-78.］

［10］ZHANG Jia，WU Yanhai，SHI Feng，et al.Positioning algorithm based on Dv-Hop wireless sensor net work［J］.Computer Application，2010，30(2):323-326(in Chinese).［張佳，吳延海，石峰，等.基于Dv-Hop無線傳感器網絡定位算法［J］.計算機應用，2010，30(2):323-326.］