基于模擬退火的加權DV-Hop的WSN定位算法

張治華，張玲華

(1.南京郵電大學 通信與信息工程學院，江蘇 南京 210003；2.江蘇省通信與網絡技術工程研究中心，江蘇 南京 210003)

0 引 言

無線傳感器網絡[1]是目前一個比較新興的研究領域，研究其最基本的需求就是獲取采集數據的節點位置信息。一般對于無準確位置信息的監測信息是沒有任何利用價值的。在無線傳感器網絡中，需要獲取無線傳感網中傳感器節點的位置信息，只有獲取節點的具體位置，才能通過節點信息分析采取何種決策方式。所以說獲取傳感器節點的位置信息具有重要意義。綜上所述，傳感器網絡節點定位技術是當今國內外研究的熱點和重點[2]。

無線傳感網絡中的定位算法主要分為兩種，一種是基于測距的定位算法(range-base),另一種是距離無關的(range-free)的定位算法[3]。前者主要是通過測量節點之間點到點的距離以及角度信息來計算節點位置，主要包括基于接受信號強度算法(RSSI)[4]、基于到達時間定位算法(TOA)[5]、基于到達時間差定位算法(TDOA)和基于到達角度算法(AOA)等[6]。這類算法雖然精度較高，但是對于硬件要求也高，而且受限于測距技術。后者是利用節點間的估計距離計算未知節點的位置，所以無需通過額外的硬件測量節點間的距離等信息。常用的與距離無關的定位技術有DV-Hop、質心算法[7]、Amorphous、APIT[8]等，這類算法成本和功耗都較低，應用也更加廣泛。

DV-Hop算法[9]是目前無線傳感網中應用最廣泛的定位算法之一，針對原有算法的不足，提出了一種基于加權的平均每跳跳距的DV-Hop算法，通過未知節點對每個信標節點估計的平均每跳跳距進行歸一化加權處理，對于距離未知節點較近的信標節點賦予大的權值。雖然改進后的加權DV-Hop定位算法相比傳統定位算法的定位精度有所提高，但不是特別明顯。為了進一步提高DV-Hop算法的定位精度，文中提出了模擬退火的加權DV-Hop算法。

1 經典DV-Hop算法描述

經典DV-Hop定位算法是基于距離矢量計算跳數的算法，具體步驟如下所述。

1.1 計算未知節點與每個信標節點的最小跳數

首先信標節點會向整個網絡廣播自身位置信息。信標節點的鄰居節點會記錄下廣播的信息，其中包括跳數信息，初始化為0。鄰節點會篩選同一信標節點的最小跳數信息并記錄，然后將其加1傳播到網絡中。保證網絡中所有節點記錄下到信標節點的最小跳數。

1.2 計算未知節點與每個信標節點的估計距離

經過上一步節點信息的路由洪泛，由式1計算平均每跳距離。

(1)

其中，(xi,yi),(xj,yj)為信標節點i,j的坐標；hi為信標節點i與j之間的跳數：HopSize為平均跳距。

1.3 計算未知節點的自身位置

通過式2計算未知節點u到信標節點的估計距離du,i：

du,i=HopSize·hu,i

(2)

其中，hu,i為最小跳數。

當未知節點得到3個或者更多節點之間的距離后，再通過三邊測量法[9]或者極大似然法等數學方法計算未知節點的坐標。

1.4 算法的誤差分析

在DV-Hop定位算法中，用未知節點到信標節點的最小跳數乘以平均跳距來計算未知節點到信標節點的距離。

如圖1所示，設A1、A2和A3為信標節點，U1、U2、U3、U4、U5和U為未知節點。其中A1到A2的實際距離為40 m，A2到A3的距離為25 m，U到A1、A2、A3的實際距離分別為50 m、20 m、50 m。針對未知節點U，信標節點A2與U的最小跳數為2，屬于局部最小跳數，因此U從A2獲取平均跳距。根據式1可得：Hopsize=(40+25)/(2+4)=10.8,那么U到A1、A2和A3的估計距離分別是10.8×3=32.4、10.8×2=21.6、10.8×3=32.4。由此可以看出，用A2估算平均跳距求U到其他信標節點估計距離的誤差非常大，導致最終未知節點定位的誤差也很大。

圖1 誤差分析

2 WDV-Hop算法

由上文誤差分析可知，由于A2和A3實際距離很近，只是略大于通信半徑，然而A2和A3跳距不止兩跳而是達到四跳，導致用A2估計平均跳距產生的誤差很大。針對誤差分析可以引入加權系數[10]。在該算法中，用Wi表示不同信標節點加權系數，通過式3確定：

(3)

其中，ni表示未知節點到信標節點i的跳數。然后根據式4計算未知節點的加權平均跳距[11]：

(4)

將加權平均跳距代入式2，求出未知節點到信標節點的估計距離，最后通過三邊測量法或者極大似然估計法求出未知節點的坐標。

WDV-Hop算法主要是對傳統DV-Hop算法的第二步進行改進，通過修正平均每跳跳距來提高定位精度，對第三步計算未知節點位置并未涉及。雖然對平均每跳跳距進行加權修正，但是平均每跳跳距誤差還是依然存在。由于最小二乘法對測距敏感，WDV-Hop算法的平均每跳跳距誤差對節點的定位精度產生較大的影響。

3 模擬退火加權DV-Hop算法

在傳統的DV-Hop和加權DV-Hop算法中，通常采用最小二乘法對未知節點的坐標進行估計，但基于最小二乘法對測距誤差比較敏感，導致由于測距誤差偏大而使得定位過程中的定位準確度降低。故應用模擬退火算法加強局部搜索最優解，提高定位算法精度。

模擬退火算法[12-14](simulated annealing，SA)是目前應用比較廣泛，基于蒙特卡洛迭代的隨機尋優方法。

模擬退火加權DV-Hop算法的核心思想如下：

(1)通過加權DV-Hop算法由式4求出HopSizeavg，然后將其帶入式2求出未知節點U到信標節點的距離。

(2)選取合適的目標函數。該定位算法中建立合適的目標函數是非常關鍵的。

圖2 節點定位示意圖

如圖2所示，設A1，A2，…，An為信標節點，節點坐標分別為(x1,y1),(x2,y2),…,(xn,yn)。U為未知節點，坐標為(x,y)，未知節點到信標節點的估計距離分別是d1,d2,…,dn。根據兩點間的距離公式可得：

(5)

令：

(6)

則目標函數為：

(7)

(4)設置初試溫度T0。

(5)設置循環計算器的初始值K=0。

(6)通過對當前解的最優點做一個隨機變動來產生一個新的最優點，計算其目標函數S2。然后令目標函數的增量Δ=S2-S1。

(7)根據Metropolis準則：

(8)

如果Δ<0，則接受新產生的解作為當前的最優解；如果Δ≥0，以概率e-Δ/T接受新產生的解作為當前的最優解。

(8)如果k小于終止迭代步數，k=k+1，然后轉向步驟6，否則轉向步驟9。

(9)如果溫度T未到達冷卻狀態，令T=T×α，α為降溫系數，取值范圍為0到1，并轉向步驟5；如果溫度達到冷卻狀態，輸出當前的解即為最優解，結束算法。

4 仿真與分析

為評價提出的模擬退火加權DV-Hop算法性能，基于Matlab仿真平臺對其進行仿真。實驗設置如下：100個節點隨機散布在100 m×100 m區域內，為使在不同條件下的分析直觀化，將平均定位誤差定義為[15]：

(9)

4.1 基于信標節點個數的分析

圖3為信標節點個數與算法定位誤差[16]的關系圖，其中dv為傳統的DV-Hop算法，wdv為加權DV-Hop算法，wdvth為模擬退火加權DV-Hop算法。由圖可知，固定其他條件，當增加網絡中信標節點的數量，三種算法的定位誤差都呈現逐漸下降的趨勢。主要因為當信標節點的數目增加，用于節點定位的信息也增加，平均誤差也隨之減小。在相同條件下，模擬退火加權DV-Hop算法的平均誤差下降趨勢比其他兩

圖3 信標節點個數-平均定位誤差

種算法要明顯很多。所以在低密度信標節點網絡中，文中提出的算法優于傳統DV-Hop和加權DV-Hop。

4.2 通信半徑對平均定位誤差的影響

圖4為通信半徑與平均定位誤差的關系圖，固定信標節點的個數為10，其他條件不變。通過改變節點的通信半徑R來比較算法的性能。當R增大時，三種算法的平均定位誤差都會減小。這主要是因為增加通信半徑使得網絡的連通度[17]提高。連通度表明在一個網絡中，能夠與一個節點直接進行通信的節點的平均個數。由圖可知，在相同條件下，文中改進的算法相比其他兩種算法下降趨勢更加明顯。在圖4中，在橫軸上隨機取一點，即傳輸半徑不變，wdvth算法的定位誤差在三種算法中最小，所以該算法能夠有效地節約節點的能量消耗。

圖4 通信半徑-平均定位誤差

4.3 基于總節點數量的分析

圖5是通過改變節點的總數來考察對算法對平均定位誤差的影響。在仿真過程中，信標節點、通信半徑等條件固定不變，將節點的總數從100開始逐漸增加。由圖可知，節點總數的變化對算法的平均定位誤差也是有影響的，三種算法的節點平均定位誤差會隨著節點總數的增加而下降。增加節點總數，同時不改變整個網絡的區域大小，相當于提高了網絡中的節點密度，使得網絡的連通度得到提升。雖然三種算法的平均定位誤差都下降，但是相比其他兩種算法模擬退火加權DV-Hop算法的定位精度明顯高于其他兩種算法。

圖5 總節點個數-平均定位誤差

5 結束語

文中首先對傳統定位算法的平均跳距進行了加權修正，更加準確地對平均每跳進行估計，減少誤差對后續節點定位的影響。然后針對最大似然估計定位抗干擾性較弱，引入模擬退火算法對未知節點的坐標進行最優搜索。該算法在提高定位精度上具有明顯的優勢，能夠有效降低由測距誤差造成的對定位精度的影響。在信標節點密度較低時，該算法也能有較高的定位精度，同時能夠有效地利用網絡中的通信量，減少節點的能量消耗，具有較高的實用價值。

參考文獻：

[1] YICK J,MUKHERJEE B,GHOSAL D.Wireless sensor network survey[J].Computer Networks,2008,52(12):2292-2330.

[2] MAO Guoqiang,FIDAN B,ANDERSON B D O.Wireless sensor network localization techniques[J].Computer Networks,2007,51(10):2529-2553.

[3] HE Tian,HUANG Chengdu,BLUM B M,et al.Range-free localization schemes for large scale sensor networks[C]//Proceedings of the 9th annual international conference on mobile computing and networking.San Diego:ACM,2003:81-95.

[4] 李再煜.RSSI定位原理的研究與實現[J].無線電工程,2013,43(7):8-10.

[5] 姜志鵬,陳正宇,劉 影,等.TOA定位算法非線性優化問題研究[J].傳感技術學報,2015,28(11):1716-1719.

[6] 鄒艷玲,程愛華.超寬帶室內環境下的TDOA/AOA定位系統[J].微計算機信息,2008,24(33):164-166.

[7] ZHANG Bingjiao,JI Minning,SHAN Lianhai.A weighted centroid localization algorithm based on DV-Hop for wireless sensor network[C]//2012 8th international conference on wireless communications,networking and mobile computing.Shanghai,China:IEEE,2012:1-5.

[8] 熊志廣,石為人,許 磊,等.基于加權處理的三邊測量定位算法[J].計算機工程與應用,2010,46(22):99-102.

[9] NICULESCU D,NATH B.DV based positioning in Ad Hoc networks[J].Telecommunication Systems,2003,22(1-4):267-280．

[10] 周杭霞,崔 晨,葉佳駿.一種基于加權處理和誤差修的DV-Hop定位算法研究[J].傳感技術學報,2014,27(12):1699-1703.

[11] 李 琳,趙 可,林志貴,等.基于加權的三維DV-Hop定位算法[J].控制工程,2015,22(4):761-764.

[12] 李玉增,張雪凡,施惠昌,等.模擬退火算法在無線傳感器網絡定位中的應用[J].通信技術,2009,42(1):211-213.

[13] 傅文淵,凌朝東.布朗運動模擬退火算法[J].計算機學報,2014,37(6):1301-1308.

[14] 蔣惠波,劉 彬,袁衛華.基于Metropolis準則的自適應隨機搜索算法研究[J].中國西部科技,2015,14(3):17-19.

[15] 張新榮,熊偉麗,徐保國.采用RSSI模型的無線傳感器網絡協作定位算法[J]. 電子測量與儀器學報,2016,30(7):1008-1015.

[16] WANG Yun,WANG Xiaodong,WANG Demin,et al.Range-free localization using expected hop progress in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2009,20(10):1540-1552.

[17] 孫小軍,劉三陽,王志強.求解網絡連通度問題的新算法[J].計算機工程與應用,2009,45(34):82-84.