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

(河南牧業(yè)經(jīng)濟(jì)學(xué)院計(jì)算機(jī)系，河南鄭州 450044)

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

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

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

1 DV-Hop算法描述

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

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

2)每個(gè)錨節(jié)點(diǎn)根據(jù)所記錄的其他錨節(jié)點(diǎn)的坐標(biāo)信息和跳數(shù)，網(wǎng)絡(luò)平均跳距估算公式為

式中:hopSij為錨節(jié)點(diǎn)i和j之間的跳數(shù);(xi，yi)為錨節(jié)點(diǎn)坐標(biāo)。

錨節(jié)點(diǎn)計(jì)算平均跳距后，對(duì)整個(gè)網(wǎng)絡(luò)進(jìn)行廣播，未知節(jié)點(diǎn)收到平均跳距后，僅記錄第一個(gè)收到的數(shù)值，然后轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn);未知節(jié)點(diǎn)計(jì)算出平均跳距和跳數(shù)信息后，根據(jù)此數(shù)據(jù)估算出某個(gè)錨節(jié)點(diǎn)到未知節(jié)點(diǎn)i的距離，即

3)未知節(jié)點(diǎn)通過三邊法或多邊法計(jì)算未知節(jié)點(diǎn)的坐標(biāo)，式(2)中Li計(jì)算公式為

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

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

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

假設(shè)fn為未知節(jié)點(diǎn)到錨節(jié)點(diǎn)之間的測(cè)距誤差，則

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

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

2 改進(jìn)DV-Hop算法

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

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

1)雜草繁殖。隨機(jī)產(chǎn)生的雜草根據(jù)其繁殖能力(適應(yīng)度值)產(chǎn)生種子，即

式中:wi是種子個(gè)數(shù);f(xi)是雜草xi的適應(yīng)度值，xi(i=1，2，…，N)是D維雜草;fmin和fmax是當(dāng)前種群中所對(duì)應(yīng)的最小和最大適應(yīng)度值;smin和smax分別是一個(gè)雜草所能產(chǎn)生種子的最小和最大個(gè)數(shù)。

2)空間擴(kuò)散。在每個(gè)雜草的周圍，按式(10)計(jì)算的種子個(gè)數(shù)產(chǎn)生種子，其中種子服從N(0，σ)的正態(tài)分布，σ的計(jì)算公式為

式中:σinitial和σfinal是標(biāo)準(zhǔn)偏差的最初值和最終值;itermax是最大進(jìn)化代數(shù);iter是當(dāng)前進(jìn)化代數(shù);n為非線性調(diào)和因子，一般情況下n=3。

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

2.2 基于蜂群搜索機(jī)制的IWO算法

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

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

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

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

“著力解決問題最突出、矛盾最集中、群眾要求最緊迫的水利問題，增強(qiáng)民生水利保障能力，擴(kuò)大民生水利成果，使水利更好地惠澤民生，造福人民群眾。”水利部部長(zhǎng)陳雷的話語(yǔ)擲地有聲，在代表們心中產(chǎn)生強(qiáng)烈共鳴。

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

1)設(shè)置主要初始參數(shù);

2)隨機(jī)產(chǎn)生P個(gè)初始雜草位置，進(jìn)入循環(huán);

3)雜草根據(jù)式(10)計(jì)算繁殖種子個(gè)數(shù);

4)根據(jù)式(11)計(jì)算種子分布的標(biāo)準(zhǔn)差，并正態(tài)分布在雜草周圍;

5)根據(jù)式(9)計(jì)算適應(yīng)度值并存儲(chǔ)最優(yōu)解;

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

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

9)存儲(chǔ)此時(shí)的最優(yōu)解;

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

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

2.3 改進(jìn)DV－Hop算法的流程

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

3 實(shí)驗(yàn)結(jié)果及分析

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

圖1 BWDV-Hop算法流程

式中:m為錨節(jié)點(diǎn)個(gè)數(shù);nc為可定位節(jié)點(diǎn)的個(gè)數(shù);(xi，yi)為對(duì)未知節(jié)點(diǎn)的估計(jì)坐標(biāo)，(x'i，y'i)為其實(shí)際坐標(biāo)。

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

圖2 不同節(jié)點(diǎn)個(gè)數(shù)下的定位性能

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

圖3 不同錨節(jié)點(diǎn)個(gè)數(shù)下的定位性能

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

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

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

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

4 總結(jié)

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

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

:

［1］尚志軍，曾鵬，于海斌.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位問題［J］.計(jì)算機(jī)科學(xué)，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ī)傳感器網(wǎng)絡(luò)中的應(yīng)用研究［J］.電子與信息學(xué)報(bào)，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.