張 浩，呂 真，連衛(wèi)民，王 碩

(河南牧業(yè)經濟學院計算機系，河南鄭州 450044)

無線傳感器網絡(Wireless Sensor Network，WSN)作為一種全新的信息獲取和處理技術在眾多領域具有十分廣泛的應用前景［1］。同時無線傳感器網絡中的節(jié)點定位技術作為傳感器網絡眾多應用的前提具有重大的支撐作用［2］。無需測距的定位算法作為一種典型的定位算法，因其在成本、功耗及環(huán)境定位精度方面的較強優(yōu)勢，而在大型WSN中備受關注［3］。DV-Hop算法作為無需測距定位算法的典型代表而成為這一領域的研究熱點［4］。

眾多學者在對DV-Hop算法的研究中指出，為了滿足應用需求，需要進一步對該算法的定位精度進行提高。針對這一問題，文獻［5-8］提出了一些改進方法:文獻［5］將RSSI策略應用到在DV-Hop算法中計算節(jié)點間的距離上，利用減小節(jié)點間誤差來對算法的定位精度進行提高;文獻［6］通過在每步DV-Hop操作中引入介質訪問機制來調節(jié)距離誤差;文獻［7］通過利用人工蜂群算法替代三邊法計算未知節(jié)點的坐標改善了算法的定位性能;文獻［8］通過引入最佳調整因子對每個錨節(jié)點計算的距離進行修正從而減小了平均跳距的計算誤差。

本文受到文獻［7］的啟發(fā)，在詳細介紹DV-Hop算法原理的基礎上，通過對該算法產生誤差的主要原因進行分析，將對未知節(jié)點坐標的計算轉化為最優(yōu)化求解，同時，通過確定目標函數，成功地引入了改進后的入侵雜草優(yōu)化算法來計算未知節(jié)點坐標，使得錨節(jié)點與未知節(jié)點之間的距離誤差大大減小，從而有效地提高了算法的定位精度。

1 DV-Hop算法描述

DV-Hop算法的主體由3個步驟組成，具體如下:

1)每個錨節(jié)點向處于通信范圍內的鄰居節(jié)點發(fā)出廣播，通告其自身的位置信息。接收廣播的節(jié)點收到數據后記錄錨節(jié)點的最小跳數，同時對來自同一個錨節(jié)點的跳數信息中較大的進行忽略，然后將此跳數值加1后再向鄰居節(jié)點進行轉發(fā)。

2)每個錨節(jié)點根據所記錄的其他錨節(jié)點的坐標信息和跳數，網絡平均跳距估算公式為

式中:hopSij為錨節(jié)點i和j之間的跳數;(xi，yi)為錨節(jié)點坐標。

錨節(jié)點計算平均跳距后，對整個網絡進行廣播，未知節(jié)點收到平均跳距后，僅記錄第一個收到的數值，然后轉發(fā)給鄰居節(jié)點;未知節(jié)點計算出平均跳距和跳數信息后，根據此數據估算出某個錨節(jié)點到未知節(jié)點i的距離，即

3)未知節(jié)點通過三邊法或多邊法計算未知節(jié)點的坐標，式(2)中Li計算公式為

式中:(xi，yi)為該未知節(jié)點所記錄的錨節(jié)點的坐標;(x，y)為未知節(jié)點的坐標。通過整理后可以得到一個線性方程AX=b，其中

考慮到WSN中各種因素的影響，DV-Hop算法所測量的距離L必然存在較大誤差，因此求解未知節(jié)點坐標的線性方程應為

式中:ε為誤差向量。因此，對式(7)利用最小二乘法求解時由于誤差向量ε的影響，使計算出的節(jié)點位置會產生較大的誤差。針對這一問題，本文利用最優(yōu)化方法通過確定目標函數將上述問題轉化為最優(yōu)求解問題，以期減小節(jié)點坐標的計算誤差。

假設fn為未知節(jié)點到錨節(jié)點之間的測距誤差，則

當式(8)要求總誤差最小時，需取得最小值，且未知節(jié)點的解是最優(yōu)的。而此時的最優(yōu)解為坐標(x，y)滿足

然而利用傳統的數學方法求解上述方程存在不小的難度，而用來解決最優(yōu)化問題中比較有效的方法之一就是利用入侵雜草優(yōu)化算法［9］。綜上所述，本文令式(9)為IWO算法的目標函數，從而成功地將未知節(jié)點坐標求解問題轉化為非線性最優(yōu)化問題，實現未知節(jié)點坐標的精度計算。

2 改進DV-Hop算法

2.1 入侵雜草優(yōu)化算法

入侵雜草優(yōu)化(Invasive Weed Optimization，IWO)算法［9］是模擬自然界中雜草群在空間中擴散、生長、繁殖和生存競爭過程的進化尋優(yōu)算法，其中種群是所有雜草的集合，雜草為問題的可行解，種子是雜草產生的后代。IWO算法主要由3步組成:

1)雜草繁殖。隨機產生的雜草根據其繁殖能力(適應度值)產生種子，即

式中:wi是種子個數;f(xi)是雜草xi的適應度值，xi(i=1，2，…，N)是D維雜草;fmin和fmax是當前種群中所對應的最小和最大適應度值;smin和smax分別是一個雜草所能產生種子的最小和最大個數。

2)空間擴散。在每個雜草的周圍，按式(10)計算的種子個數產生種子，其中種子服從N(0，σ)的正態(tài)分布，σ的計算公式為

式中:σinitial和σfinal是標準偏差的最初值和最終值;itermax是最大進化代數;iter是當前進化代數;n為非線性調和因子，一般情況下n=3。

3)個體競爭生存。當種群規(guī)模大于最大種群規(guī)模P_Max后，種群中雜草和種子按適應度值大小進行排序，選取較好的前P_Max，淘汰其余個體。

2.2 基于蜂群搜索機制的IWO算法

在IWO算法的進化后期，隨著進化代數的逐漸增加，種群多樣性將逐漸降低，導致搜索空間縮小，從而使算法容易陷入局部最優(yōu)。但是該算法并沒有跳出局部最優(yōu)的策略，因而容易出現早熟的現象。

Karaboga于2003年提出的人工蜂群算法［10］是一種群集智能優(yōu)化算法。由于該算法的蜜源搜索方程針對蜂群的分工機制采用不同的搜索策略，因而其具有較強的探索能力，蜜源搜索方程為

式中:i，k={1，2，…，N}，且i≠k，j={1，2，…，D}。φi，j為［-1，1］之間的隨機數。從式(12)可以看出，新的候選解向種群中隨機的個體移動，因而具有較強的隨機性。然而該方程側重于提高算法的探索能力，而忽略了算法的開發(fā)能力，針對這一問題，文獻［11］結合粒子群算法的搜索方程，提出了全局最優(yōu)引導策略，即

式中:Pg，j為全局最優(yōu)解;ψi，j為［0，1.5］的隨機數。通過這一策略有效地平衡了蜂群算法的開發(fā)與探索能力。

“著力解決問題最突出、矛盾最集中、群眾要求最緊迫的水利問題，增強民生水利保障能力，擴大民生水利成果，使水利更好地惠澤民生，造福人民群眾?！彼坎块L陳雷的話語擲地有聲，在代表們心中產生強烈共鳴。

基于此，本文結合文獻［12］提出的全局引導蜜源搜索策略來改進IWO算法，對算法的探索能力進行提高，從而對算法中早熟現象進行避免，進一步改善IWO算法的全局尋優(yōu)能力，下面給出了結合蜂群搜索機制的IWO算法步驟:

1)設置主要初始參數;

2)隨機產生P個初始雜草位置，進入循環(huán);

3)雜草根據式(10)計算繁殖種子個數;

4)根據式(11)計算種子分布的標準差，并正態(tài)分布在雜草周圍;

5)根據式(9)計算適應度值并存儲最優(yōu)解;

6)種子根據式(13)搜索鄰近候選解;

7)計算新種子的適應度值，并選取更優(yōu)的種子;

9)存儲此時的最優(yōu)解;

10)循環(huán)次數加1;

11)滿足終止條件，達到最大循環(huán)次數。

2.3 改進DV－Hop算法的流程

本文借助于IWO算法較強的尋優(yōu)能力，在將DVHop算法未知節(jié)點坐標計算問題成果轉換為全局最優(yōu)化求解問題的基礎上，結合人工蜂群全局最優(yōu)引導策略，在對IWO算法進行改進以提高其收斂速度和搜索精度后，提出了基于人工蜂群搜索機制的IWO算法的DV-Hop改進算法，記為BWDV-Hop算法。以期較好地解決求解未知節(jié)點坐標時誤差較大的問題，圖1給出了算法的流程。

3 實驗結果及分析

為了驗證改進算法的有效性，仿真平臺均基于MATLAB實現，并對傳統DV-Hop算法、文獻［6］提出的ADVHop算法進行比較。設監(jiān)測區(qū)域為邊長等于100 m的方形區(qū)域;BIWO算法初始種群P為10，P_Max為30，迭代次數為30，σinitial=3，σfinal=0.000 1，smax=5，smin=0，搜索區(qū)間為［0，100］;ABC算法初始種群SN=10，循環(huán)次數為30，limit=10。分別仿真比較了本文算法和文獻［7］提出的ADV-Hop和標準DV-Hop算法中，在節(jié)點個數不同、錨節(jié)點個數不同及通信半徑條件不同時的定位精度，通過仿真分析得出不同條件下算法的定位性能。本文通過計算歸一化平均定位誤差作為評價指標［12］，試驗結果基于500次獨立仿真實驗，計算公式為

圖1 BWDV-Hop算法流程

式中:m為錨節(jié)點個數;nc為可定位節(jié)點的個數;(xi，yi)為對未知節(jié)點的估計坐標，(x'i，y'i)為其實際坐標。

圖2給出了3種DV-Hop算法歸一化平均定位誤差隨傳感器節(jié)點個數變化的曲線，其中錨節(jié)點比例為10%，節(jié)點通信半徑R=22 m。由圖2可以看出，在節(jié)點個數由60向240變化的過程中，3種算法的歸一化平均定位誤差均逐漸減小;另外BWDV-Hop的定位誤差明顯小于其他兩種算法的定位誤差，具體相比于DV-Hop和ADV-Hop算法分別減小了23.48%和13.53%。

圖2 不同節(jié)點個數下的定位性能

圖3給出了3種DV-Hop算法的定位性能隨錨節(jié)點個數變化的曲線，其中節(jié)點通信半徑R=22 m，節(jié)點總數為120。從圖3中可以發(fā)現，當錨節(jié)點個數不斷增多時，歸一化定位誤差對于三種算法來說均逐漸減小并趨于穩(wěn)定，相比于DV-Hop和ADV-Hop算法，BWDV-Hop算法的平均定位誤差分別減小了29.03%和19.43%。

圖3 不同錨節(jié)點個數下的定位性能

圖4為不同節(jié)點通信半徑對3種DV-Hop算法定位性能的影響程度，其中節(jié)點總數為120，錨節(jié)點數為12。從圖4中可以看出，隨著節(jié)點通信半徑的不斷增加，3種算法的歸一化平均定位誤差均逐漸減小，相比于DV-Hop和ADV-Hop算法，本文提出的BWDV-Hop算法在歸一化平均定位誤差方面分別平均減小了14.57%和22.8%。

圖4 不同通信半徑下的定位性能

圖5為傳統DV-Hop算法、ADV-Hop算法以及本文提出的BWDV-Hop算法在邊長為100 m的方形區(qū)域內的定位結果圖。從圖5可以看出，BWDV-Hop算法的定位誤差小于DV-Hop算法以及ADV-Hop算法，且定位效果明顯優(yōu)于其他兩種算法。

通過圖5的仿真結果計算得出，當100個節(jié)點隨機部署在邊長為100 m的方形區(qū)域內，未知節(jié)點個數為90，錨節(jié)點個數為10，節(jié)點通信半徑為20 m時，傳統DV-Hop的平均定位誤差為76.02%，ADV-Hop算法的平均定位誤差為52.28%，而本文改進算法BWDV-Hop算法的平均定位誤差為29.78%。

4 總結

圖5 3種算法定位算法比較圖

本文主要研究了無線傳感器網絡中，無需測距的DV-Hop定位算法。首先對DV-Hop算法的基本原理進行介紹，通過對算法原理的詳細分析，總結算法產生誤差的主要原因，在此基礎上將未知節(jié)點位置的計算問題轉化為全局最優(yōu)化求解問題，通過設置目標函數，成功地將改進的入侵雜草優(yōu)化算法引入到DV-Hop算法中。經仿真實驗，驗證了不同節(jié)點個數、錨節(jié)點個數及節(jié)點通信半徑下，與標準DV-Hop算法和ADV-Hop算法進行比較，在定位精度與平均定位誤差方面，本文改進算法具有明顯優(yōu)勢。

:

［1］尚志軍，曾鵬，于海斌.無線傳感器網絡節(jié)點定位問題［J］.計算機科學，2004，31(10):35-38.

［2］LEE S，KIM K.Determination of communication range for range-free multi-hop localization in wireless sensor networks［C］//Proc.Computer Communications and Networks.［S.l］:IEEE Press，2011:1095-2055.

［3］PERKINS C，ROYER E.Ad hoc on demand distance vector routing［J］.Mobile System and Applications，1999，24(3):59-81.

［4］NICULESCU D，NATH B.Ad hoc positioning system(APS)using AOA［C］//Proc.IEEE Computer and Communications Societies.San Francisco:IEEE Press，2003:1734-1743.

［5］ZHANG Dengyin，CUI Guodong.A union node localization algorithm based on RSSI and DV-Hop for WSNs［C］//Proc.Instrumentation，Measurement，Computer，Communication and Control(IMCCC).Harbin:［s.n.］，2012:1094-1098.

［6］GUI L Q，WEI A，VAL T.A range-free localization protocol for wireless sensor networks［C］//Proc.International Symposium on Wireless Communication System(ISWCS).Paris:IEEE Press，2012:496-500.

［7］LI Mudong，XIONG Wei，LIANG Qing.An improved ABC-based node localization algorithm for wireless sensor networks［C］//Proc.International Conference on Wireless Communications，Networking and Mobile Computing(WICOM).Shanghai:IEEE Press，2012:1-4.

［8］WOO H，LEE S.Range-free localization with isotropic distance scaling in wireless sensor networks［C］//Proc.International Conference on Information Networking(ICOIN).Bangkok:IEEE Press，2013:632-636.

［9］MEHRABIAN A R，LUCAS C.A novel numerical optimization algorithm inspired from weed colonization［J］.Ecological Informatics，2006(4):355-366.

［10］KARABOGA D，BASTURK B.On the performance of artificial bee colony(ABC)algorithm［J］.Applied Soft Computing，2008，8(1):687-697.

［11］嵇瑋瑋，劉中.DV-Hop定位算法在隨機傳感器網絡中的應用研究［J］.電子與信息學報，2008，30(4):970-974.

［12］ZHU G P，KWONG S.Gbest-guided artificial bee colony algorithm for numerical function optimization［J］.Applied Mathematics and Computation，2010，217(7):3166-3173.