譚愛平，陳浩，吳伯橋

1.湖南大學信息科學與工程學院，長沙 410082

2.湖南工業(yè)職業(yè)技術學院，長沙 410208

基于BADV-Hop的傳感器節(jié)點定位方法

譚愛平1，2，陳浩1，吳伯橋1

1.湖南大學信息科學與工程學院，長沙 410082

2.湖南工業(yè)職業(yè)技術學院，長沙 410208

為了減少無線傳感器網(wǎng)絡節(jié)點的定位誤差，提出蝙蝠算法（BA）和DV-Hop算法相融合的傳感器節(jié)點定位方法（BA-DVHop）。在DVHop算法的第三階段，利用蝙蝠算法代替最小二乘法來計算未知節(jié)點的坐標，以降低定位誤差，對蝙蝠算法算法進行改進，避免算法陷入局部最優(yōu)，最后在Matlab 2012平臺上對算法性能進行仿真分析。相對于DV-Hop算法，BADV-Hop算法提高了傳感器的節(jié)點定位精度，具有較高的應用價值，仿真結果驗證了BA-DVHop的有效性。

無線傳感器網(wǎng)絡；蝙蝠優(yōu)化算法；節(jié)點定位；DV-Hop算法

1 引言

節(jié)點定位技術是無線傳感器網(wǎng)絡（Wireless Sensor Network，WSN）的關鍵技術，在軍事、環(huán)境監(jiān)測和醫(yī)療衛(wèi)生等領域有著廣泛的應用前景，因此提高傳感器節(jié)點精度成為WSN研究中的熱點[1]。

由于WSN具有巨大的應用價值，因此，國內外專家和學者對其展開了一系列的研究，當前傳感器節(jié)點定位算法分為：距離有關和距離無關的定位算法[2]。距離有關定位算法由于受到外界環(huán)境因素的干擾比較大，所以獲得的誤差較大，且成本高[3]；距離無關定位算法主要有質心算法、DV-Hop算法，這類定位算法無需額外硬件支持，功耗低，成為當前主要研究方向[4-5]。DV-Hop算法實現(xiàn)比較簡單，只需要少量的錨節(jié)點就可以實現(xiàn)對未知節(jié)點的定位，備受關注，但是精度有待提高[6]。為此，學者們提出一些改進的DV-Hop算法，如文獻[7]將RSSI策略引入到DV-Hop算法節(jié)點距離計算中，減小節(jié)點間誤差，提高定位精度；文獻[8]在DV-Hop算法中引入介質訪問機制來調節(jié)距離誤差；文獻[9]通過引入最佳調整因子對每個錨節(jié)點計算的距離進行修正，從而減小了平均跳距的計算誤差。采用遺傳算法、模擬退火算法、蛙跳算法、粒子群算法等群智能算法對DV-Hop算法的誤差進行校正，一定程度上提高了DV-Hop算法的定位精度[9-11]。蝙蝠算法（BA）是一種群智能優(yōu)化算法，在準確性和有效性方面相較其他算法有很大優(yōu)勢，且沒有許多參數(shù)要調整，為DV-Hop算法誤差校正提供了一種新的研究思路[12]。

為了減少無線傳感器網(wǎng)絡節(jié)點的定位誤差，提出一種改進蝙蝠算法（BA）和DV-Hop算法相融合的傳感器節(jié)點定位方法（BA-DVHop）。在DV-Hop算法的第三階段，利用蝙蝠算法代替最小二乘法來計算未知節(jié)點的坐標，并對蝙蝠算法進行改進避免算法陷入局部最優(yōu)，最后在Matlab 2012平臺上對算法性能進行仿真分析。仿真結果表明，BADV-hop定位算法在不同錨節(jié)點密度、不同通信半徑、不同節(jié)點數(shù)量以及定位精確度等方面表現(xiàn)出良好性能。

2 DV-Hop定位算法及誤差分析

2.1 DV-Hop定位算法工作步驟

第一階段：計算節(jié)點的最小跳數(shù)。信標節(jié)點向網(wǎng)絡發(fā)送一個廣播信號，鄰居節(jié)點接收到信號后，記錄信標節(jié)點的坐標信息，并保存每個信標節(jié)點的最小跳數(shù)，然后向其他的鄰居傳感器節(jié)點傳播，通過該方法，WSN網(wǎng)絡中全部節(jié)點可以得到信標節(jié)點的位置信息和與信標節(jié)點間的跳數(shù)。

第二階段：估算到信標節(jié)點的跳段距離。通過第一階段后，每個信標節(jié)點就可以得到其他信標節(jié)點的坐標值和跳數(shù)，然后通過式（1）計算平均每跳距離，同時將每跳平均距離廣播至網(wǎng)絡中，未知節(jié)點將平均每跳距離值與最小跳數(shù)值相乘，得到其與信標節(jié)點間的距離：

式中，hi是信標節(jié)點i和j之間的跳數(shù)，(xi，yi)、(xj，yj)是信標節(jié)點i，j的坐標。

第三階段：通過最大似然法計算自身位置。設P1(x1，y1)，P2(x2，y2)，…，Pn(xn，yn)表示n個信標節(jié)點的坐標位置，待定位節(jié)點位置為(x，y)，其與信標節(jié)點估計距離分別為d1，d2，…，dn-1，可以建立式（2）的方程：

第一個方程組減去第后一個方程后，得到：

用線性方程組表示為AL=b，其中：

在無線傳感器節(jié)點測距過程中，不可避免會產(chǎn)生一些隨機誤差，這樣線性方程組為AL+N=b，N為誤差向量，最小二乘法的求解方程為：

2.2 DV-Hop定位誤差分析

設信標節(jié)點(xi，yi)，i=1，2，…，n，與未知節(jié)點(x，y)的實際距離為ri，i=1，2，…，n，測距誤差為εi，那么|ri-di|＜εi，i=1，2，…，n。根據(jù)式（2）可知，(x，y)應該滿足如下約束條件：

由于式（5）代表可行解的區(qū)域，那么該區(qū)域一定存在最優(yōu)解，且當f(x，y)取最小值時，節(jié)點定位總誤差最小，此時的坐標(x，y)將為最優(yōu)值，這樣無線網(wǎng)絡傳感器節(jié)點定位問題轉化成一個約束優(yōu)化問題，然后采用BA算法進行求解，提高傳感器定位精度。

3 BADV-Hop算法的節(jié)點定位

3.1 改進的蝙蝠算法

2010年，有學者通過模擬蝙蝠回聲定位行為而提出的蝙蝠算法（BA），其在迭代尋優(yōu)方面相較其他群智能算法有很大優(yōu)勢。BA算法首先對所有蝙蝠的位置和速度隨機初始化，其中位置是待求解問題的潛在解，然后通過適應度函數(shù)評價群體，找出群體最優(yōu)個體（最優(yōu)解）；接著分別按式（9）更新個體的脈沖頻率、速度和位置：

式中，F(xiàn)i、Fmax和Fmin分別表示第i只蝙蝠在當前時刻發(fā)出的脈沖頻率、脈沖頻率的最大值和最小值，β∈[0，1]是一個服從均勻分布的隨機因子，x*為最優(yōu)蝙蝠位置。

據(jù)生物學知識，在初始階段蝙蝠脈沖頻度低且聲響大，有助于在大范圍內搜索目標，發(fā)現(xiàn)獵物后，逐漸使聲響變小并增加脈沖頻度以便精確掌握獵物的空間位置，因此聲響和脈沖頻度隨著運行進行而不斷地更新，公式如下：

其中，0＜α＜1，γ＞0，均為常量。

隨機飛動產(chǎn)生新解xi的公式為：

式中，ε∈[-1，1]是一個隨機變量；At是所有蝙幅在此步中平均聲音響度。

對BA算法原理進行分析可知，BA算法缺乏有效的變異機制，群體容易聚集于局部極值，導致早熟收斂，因此本文對其進行改進，并將其用于解決無線傳感網(wǎng)節(jié)點定位問題，以提高定位精度。具體改進如下：

（1）蝙蝠通過調整頻率Fi得到新的位置，在頻率公式（4）中，β∈[0，1]區(qū)間內均勻分布的隨機因子，其實質上是個體的變異操作，在一定的程度上使種群保持多樣性，β是變異因子，其值越大，對新構建的解貢獻越大；反之，值越小，對新構建的解貢獻越小，控制好β值能提高種群多樣性，避免早熟，從而提高算法的求精能力。因此本文采用動態(tài)自適應機制調整變異因子β，公式如下：

式中，fbest(i)是第i代最佳的適應度值；fworst(i)是第i代中最差的適應度值；(fbest(i)-fworst(i))/fbest(i)表示變異因子根據(jù)每代中最佳和最差適應度值完成自適應的調整。

（2）當rand＜Ri時，基本BA算法是通過隨機飛動產(chǎn)生新解xi，相關研究表明，位置移動機制對算法優(yōu)化精度、收斂速度有重要影響，基本BA算法中，蝙蝠移動后的位置目標函數(shù)值可能比原來的更差，因此，改進BA算法考慮以概率pa∈[0，1]拋棄最差的解，然后再用隨機飛動重新生成相同數(shù)量的新解。

（3）當基本BA算法進行了n次迭代，最小值無變化或者變化很小，算法可能陷入局部最優(yōu)，因此改進BA算法在n＞3且當前解的變化很小(＜1E-3)時，則考慮在當前解的基礎上以萊維隨機游動方式進行擾動，以擴大種群的搜索范圍，評價并保留較好的解。萊維飛行是一種特殊的隨機行走行為，體現(xiàn)出的是一類非高斯隨機過程，其平穩(wěn)增量服從Lévy穩(wěn)定分布，則有蝙蝠位置更新公式為：

3.2 適應值函數(shù)設計

蝙蝠算法在優(yōu)化的過程中，通過蝙蝠的適應度值來判斷蝙蝠所處位置的優(yōu)劣，蝙蝠算法種群中的每一個蝙蝠是未知節(jié)點的一個候選解，適應值函數(shù)計算公式為：

式中，m為錨節(jié)點的個數(shù)，ωi為未知節(jié)點與第i個錨節(jié)點測量距離的權重，其值與未知節(jié)點到錨節(jié)點的跳數(shù)hi成反比，hi由Dv-Hop算法的第一階段獲得，未知節(jié)點的估計距離是通過最小化適應度函數(shù)的目標值來決定的。

3.3 BADV-Hop算法的節(jié)點定位步驟

（1）在目標區(qū)域隨機部署節(jié)點，先運用Dv-Hop算法的第一、二階段定位方法，通過節(jié)點間相互通信，確保每個未知節(jié)點都接收并保存其到各錨節(jié)點的跳數(shù)hi和網(wǎng)絡跳距di。

（2）在目標區(qū)域內隨機初始化蝙蝠種群，種群中的每個蝙蝠都是當前未知節(jié)點位置的一個可行解，根據(jù)式（12）計算每個個體的適應值，保存群體最優(yōu)位置x*以及群體最優(yōu)值f(x*)。

（3）用式（7）調整搜索脈沖頻率Fi，并計算蝙蝠個體的飛行速度vi，更新蝙蝠的空間位置xi。

（4）產(chǎn)生隨機數(shù)rand，如果rand＞Ri，則接受新位置xi，否則，按發(fā)現(xiàn)概率pa丟棄差的個體，用式（11）產(chǎn)生新的位置替代丟棄的位置。

（5）如果(rand＞Ai)&&f(xi)＜f(x*)，則移動至更新后的位置，然后按式（10）更新脈沖頻度Ri和聲響Ai。

（6）判斷是否出現(xiàn)連續(xù)3次f(x*)變化量小于1E-3的現(xiàn)象，若是，則轉步驟（6），否則，轉步驟（8）。

（7）根據(jù)式（10）對蝙蝠位置進行萊維隨機擾動，評價并保留較好的解。

（8）判斷是否滿足結束條件（達到迭代次數(shù)或是預測精度），滿足則結束；否則，轉向步驟（3）。

（9）輸出全局最優(yōu)解對應的個體位置，即未知節(jié)點的位置估計坐標。

3.4 BADV-Hop算法的工作流程

借助于蝙蝠優(yōu)化算法較強的尋優(yōu)能力，首先在將DV-Hop算法未知節(jié)點坐標計算問題成果轉換為全局最優(yōu)化問題的基礎上，然后采用利用改進蝙蝠算法代替最小二乘法來計算未知節(jié)點的坐標，以期較好地解決求解未知節(jié)點坐標時誤差較大的問題，具體流程如圖1。

4 仿真實例

4.1 仿真環(huán)境

為了驗證BADV-Hop算法的有效性，在Matlab2012仿真平臺上，在相同網(wǎng)絡環(huán)境下選擇標準DV-Hop算法進行對比實驗，對不同錨節(jié)點密度、不同通信半徑、不同節(jié)點數(shù)量以及定位精確度等方面進行了比較。在100 m× 100 m的二維區(qū)域中隨機部署100個節(jié)點，節(jié)點的通信半徑為30 m，錨節(jié)點的比例為10%，參數(shù)設置為：蝙蝠種群大小m=100，搜索脈沖頻率范圍[0，100]，最大脈沖頻度r0=0.75，最大聲響A=0.20，音量衰減系數(shù)，脈沖頻度增加系數(shù)γ=0.05，所有結果為重復運行30次后取均值。采用平均定位誤差評價定位算法的優(yōu)劣，具體如下：

圖1 BADV-Hop算法的工作流程

4.2 結果與分析

4.2.1 BA算法改進前后的收斂性能對比

改進前后BA的收斂曲線如圖2所示。從圖2可知，相對于基本BA算法，改進后的BA算法收斂速度明顯加快，這主要是改進BA算法可以較好地保持種群多樣性，以萊維隨機游動方式進行擾動，擴大了種群搜索范圍，提升了求解效率，可以較好地滿足節(jié)點定位的實時性要求，并驗證本文對BA算法改進的有效性和可行性。

圖2 改進前后BA算法的收斂性能比較

4.2.2 定位誤差比較

DV-Hop算法、BADV-Hop算法的未知節(jié)點定位誤差如圖3所示。從圖3可知，BADV-Hop算法得到的90個未知節(jié)點的平均定位誤差相差不多，明顯小于DV-Hop算法的結果，而且BADV-Hop算法的節(jié)點坐標偏離平均定位誤差的幅度要明顯小于DV-Hop算法的結果，對比結果表明，BADV-Hop算法具有更好的穩(wěn)定性。

圖3 兩種算法定位的未知節(jié)點誤差

4.2.3 不同錨節(jié)點個數(shù)下的定位性能

圖4給出了2種算法定位性能隨錨節(jié)點個數(shù)變化的曲線，其中節(jié)點總數(shù)為120，R=22 m。從圖4可以看出，在相同錨節(jié)點比例下，相比于DV-Hop算法，BADVHop算法的平均定位誤差總是小于DV-Hop算法的定位誤差。

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

4.2.4 不同節(jié)點數(shù)下的定位性能

圖5為節(jié)點個數(shù)從20變化為60時，兩種定位算法的定位誤差。由圖5可知，相對于DV-Hop算法，BADVHop算法受到節(jié)點數(shù)量變化的影響相對較小，體現(xiàn)了很好的魯棒性。

圖5 節(jié)點密度對定位精度的影響

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

圖6為不同通信半徑對兩種算法定位性能的影響程度，其中錨節(jié)點比例為10%，節(jié)點個數(shù)為40。從圖6可以看出，在相同節(jié)點通信半徑下，相對于DV-Hop算法，BADV-Hop算法的定位精度提高了20%～40%，有效降低了傳感器的定位誤差。

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

4.2.6 定位結果比較

DV-Hop算法和BADV-Hop算法的定位結果如圖7所示。從圖7可知，BADV-Hop算法的定位誤差小于DV-Hop算法，且定位效果明顯得以提高。

圖7 兩種算法的定位結果對比

5 結束語

為了提高無線傳感器網(wǎng)絡定位精度，提出一種蝙蝠算法和DV-Hop算法相融合的節(jié)點定位方法，在DV-Hop的第三階段利用改進蝙蝠算法代替最小二乘法來計算未知節(jié)點的坐標，有效減少了平均跳距導致的定位誤差，仿真結果表明，相比于DV-Hop算法，BADV-Hop算法在定位精度與平均定位誤差方面具有明顯優(yōu)勢。在此基礎上，開展定位能耗、移動定位方面的改進將是下一步的研究重點。

[1]王福豹，史龍，任豐原.無線傳感器網(wǎng)絡中的自身定位系統(tǒng)和算法[J].軟件學報，2005，16（5）：857-868.

[2]Costa J A，Patwari N，Hero O.Distributed weighted multidimensional scaling for node localization in sensor networks[J].ACM Transactions on Sensor Networks，2006，2（1）：39-64.

[3]劉運杰，金明錄，崔承毅.基于RSSI的無線傳感器網(wǎng)絡修正加權定位算法[J].傳感技術學報，2009，23（5）：717-721.

[4]李輝，熊盛武，劉毅，等.無線傳感器網(wǎng)絡DV-Hop定位算法的改進[J].傳感技術學報，2011，24（12）：1782-1786.

[5]白進京，嚴新平.基于加權質心和DV-hop混合算法WSN定位方法研究[J].計算機應用研究，2009，26（6）：2248-2251.

[6]Cerpa A，Estrin D.ASCENT：adaptive self-configuring sensor networks topologies[J].IEEE Transactions on M obile Computing，2004，3（3）：272-285.

[7]Gao Y，Zhao W S，Jing C，et al.WSN node localization algorithm based on adaptive particle swarm optimization[J]. Applied Mechanics and Materials，2012，143：302-306.

[8]葉蓉，趙靈鍇.基于蟻群粒子群混合的無線傳感器網(wǎng)絡定位算法[J].計算機測量與控制，2011，19（3）：732-735.

[9]趙仕俊，孫美玲，唐懿芳.基于遺傳模擬退火算法的無線傳感器網(wǎng)絡定位算法[J].計算機應用與軟件，2009，26（10）：189-192.

[10]鄧力.基于遺傳算法WSN節(jié)點定位算法研究[J].計算機仿真，2011，28（9）：161-164.

[11]歐陽丹彤，何金勝，白洪濤.一種約束粒子群優(yōu)化的無線傳感網(wǎng)絡節(jié)點定位算法[J].計算機科學，2011，38（7）：46-50.

[12]Yang X S，Gandom i A H.Bat algorithm：a novel approach for global engineering optimization[J].Engineering Computations，2012，29（5）：464-483.

TAN Aiping1，2,CHEN Hao1,WU Boqiao1

1.School of Information Science and Engineering,Hunan University,Changsha 410082,China
2.Hunan Industry Polytechnic,Changsha 410208,China

In order to reduce node localization error of wireless sensor network, a novel sensor node localization method is proposed based on Bat Algorithm and the DV-Hop algorithm（BA-DVHop）. In the third stage of DVHop algorithm, bat algorithm is used to take place the least square method to calculate the unknown node in order to reduce the positioning error, and bat algorithm is improved to avoid falling into local optimum, finally, the simulation analysis is used to test performance on Matlab 2012 platform. Compared with DV-Hop algorithm, BADV-Hop algorithm can improve the localization accuracy of wireless sensor network and has high application value, so the simulation results have verified the effectiveness of BA-DVHop algorithm.

wireless sensor network;bat algorithm;node localization;DV-Hop algorithm

TAN Aip ing,CHEN Hao,WU Boqiao.Nodes localization Method of wireless sensor networks based on Bat-DVHop algorithm.Computer Engineering and Applications,2014,50（17）：125-129.

A

TP393

10.3778/j.issn.1002-8331.1403-0094

國家自然科學基金（No.61272190）。

譚愛平（1979—），男，網(wǎng)絡工程師，主研方向：網(wǎng)絡工程、網(wǎng)絡安全；陳浩（1977—），男，博士，副教授，主研方向：網(wǎng)絡安全和信息安全；吳伯橋（1979—），男，網(wǎng)絡規(guī)劃師，主研方向：網(wǎng)絡系統(tǒng)集成、網(wǎng)絡安全。E-mail：476957437@qq.com

2014-03-10

2014-04-25

1002-8331（2014）17-0125-05