白 偉,李鳳英,鄭海洋,劉亞紅,馮海林
(1.寧夏師范大學 數(shù)學與計算機科學學院,寧夏 固原 756000;2.西安電子科技大學 理學院,陜西 西安 710071)
基于BADV-Hop的無線傳感器網(wǎng)絡節(jié)點定位方法*
白 偉1,李鳳英1,鄭海洋1,劉亞紅2,馮海林2
(1.寧夏師范大學 數(shù)學與計算機科學學院,寧夏 固原 756000;2.西安電子科技大學 理學院,陜西 西安 710071)
針對無線傳感器網(wǎng)絡(WSNs)節(jié)點的定位誤差較大的問題,提出一種蝙蝠算法(BA)和DV-Hop算法融合(BADV-Hop)的定位算法。首先測量未知節(jié)點與錨節(jié)點之間的距離,然后采用DV-Hop算法初步確定未知節(jié)點的坐標,再采用BA校正DV-Hop算法的定位誤差,最后在Matlab 2012平臺上對算法性能進行仿真分析。實驗結(jié)果表明:相對于DV-Hop算法,BADV-Hop算法提高了傳感器的節(jié)點定位精度。
無線傳感器網(wǎng)絡;DV-Hop算法;節(jié)點定位;蝙蝠算法
節(jié)點的位置信息是無線傳感器網(wǎng)絡(wireless sensor networks,WSNs)成功應用前提和基礎,其可以完成網(wǎng)絡拓撲自管理、提高節(jié)點間路由效率等,因此,傳感器節(jié)點定位一直是WSNs研究中的重點和難點[1]。
目前,WSNs定位算法分為兩類:基于測距(range-based)的定位算法和免測距(range-free)定位算法[2]。Range-based定位算法首先利用計算節(jié)點間的距離,然后根據(jù)三邊(三角、多邊)測量法確定未知節(jié)點的位置,其需額外硬件設備來測量節(jié)點間距離,成本高和能耗大,對WSNs生存時間產(chǎn)生不利影響[3];Range-free定位算法根據(jù)節(jié)點間的通信估計出節(jié)點間距離,再確定未知節(jié)點的位置,主要有質(zhì)心定位算法、DV-Hop算法、APIT算法,該類算法功耗小、成本低,引起了人們的廣泛關(guān)注[4~7]。其中,DV-Hop算法應用最為廣泛,在DV-Hop算法的基礎上,一些學者提出采用群智能算法對DV-Hop算法進行改進,如粒子群算法、遺傳算法等,以提高了WSNs的節(jié)點定位精度[8,9]。但是這些算法存在著易陷入局部最優(yōu)、縮小搜索空間等問題,影響WSNs的傳感器節(jié)點定位精度[10]。
蝙蝠算法(bat algorithm,BA)是一種通過模擬蝙蝠回聲定位行為的新型群智能算法,相對于其他算法,其在迭代尋優(yōu)方面具有很大優(yōu)勢,且需要調(diào)整參數(shù)較少[11]。為了減少WSNs節(jié)點的定位誤差,以獲得更加理想的傳感器節(jié)點定位結(jié)果,本文提出一種基于BA校正DV-Hop(BADV-Hop)算法的傳感器節(jié)點定位方法,并在Matlab 2012平臺上對算法性能進行仿真分析。仿真結(jié)果表明:在相同條件下,BADV-Hop算法提高了傳感器節(jié)點的定位精度,具有定的實用價值。
1.1 DV-Hop算法
Nieuleseu等人提出了DV-Hop傳感器節(jié)點定位算法,具有無需測量距離、硬件要求低等特點,其定位步驟具體如下:
1)計算未知節(jié)點和錨節(jié)點之間的最小跳數(shù)。
2)計算未知錨節(jié)點之間每跳的平均距離:當每個錨節(jié)點都得到了其與其他錨節(jié)點間的最小跳數(shù)時,整個網(wǎng)絡中的平均每跳距離計算公式為
(1)
式中 (xi,yi)和(xj,yj)代表節(jié)點i和j的坐標信息;hopij代表節(jié)點i和j之間的最小跳數(shù)。節(jié)點就可以計算出其自身和錨節(jié)點之間的距離[8]。
3)計算每一個未知節(jié)點的位置坐標:設P1(x1,y1),P2(x2,y2),…,Pn(xn,yn)表示n個錨節(jié)點的坐標位置,待定位節(jié)點位置為(x,y),其與錨節(jié)點估計距離分別為d1,d2,…,dn-1,可以建立式(2)的方程
(2)
在WSNs節(jié)點測距過程中,不可避免會產(chǎn)生一些隨機誤差,這樣線性方程組[8]為AL+N=b,N為誤差向量,求解方程為
L=(ATA)-1ATb.
(3)
設錨節(jié)點i與未知節(jié)點的實際距離為ri,測距誤差為εi,那么,未知節(jié)點的坐標(x,y)應該滿足一定約束條件,求解(x,y),使得
(4)
由式(4)可知,節(jié)點位置一定存在于該區(qū)域中,而且當f(x,y)取最小值時,節(jié)點定位總誤差最小,此時的坐標(x,y)將為未知節(jié)點位置的最優(yōu)值,因此,WSNs的節(jié)點定位問題轉(zhuǎn)化成一個約束優(yōu)化問題,然后采用BA進行求解,以提高傳感器定位精度。
1.2 BA
BA是一種劍橋大學的Yang XinShe 受到微型蝙蝠的回聲定位行為方式與目標函數(shù)優(yōu)化關(guān)聯(lián)性啟發(fā)的群智能優(yōu)化算法。
1.2.1 虛擬蝙蝠的運動
fi=fmin+(fmax-fmin)β,
(5)
(6)
(7)
對于局部搜索,一旦在當前最優(yōu)解中選中了一個解,那么,每只蝙蝠按照隨機游走法則產(chǎn)生局部新解
xnew=xold+εAt,
(8)
式中ε∈[-1,1]為一個隨機數(shù);At=〈At〉為所有蝙蝠在同一個時間段的平均音量。
1.2.2 音量和脈沖發(fā)生率
根據(jù)蝙蝠的生物學機理,在搜尋獵物的過程中,蝙蝠在初始階段發(fā)出的超聲波脈沖音強大而頻率低,以利于在更廣泛的空間內(nèi)進行搜索;當發(fā)現(xiàn)獵物后,脈沖音強逐漸減小同時脈沖發(fā)射次數(shù)增加,以精確掌握獵物的空間位置。音強和脈沖發(fā)生率的更新公式
(9)
為了驗證BA的收斂速度、尋優(yōu)精度優(yōu)于粒子群優(yōu)化(PSO)算法、遺傳算法(GA)等,采用2個標準測試函數(shù)進行對比實驗,測試函數(shù)如下
(10)
(11)
從圖1可知,相對于PSO,GA,BA經(jīng)過更小的迭代次數(shù)就可以找到達到函數(shù)的最優(yōu)解,對比結(jié)果驗證了本文采用BA的合理性和有效性。
圖1 BA算法與其它算法的性能比較Fig 1 Performance comparison of BA and other algorithms
2.1 編碼設計
由于WSNs節(jié)點定點定位目標就要求尋找一個與實際位置誤差最小的位置,因此,可以認為每一個蝙蝠位置對應未知節(jié)點的一個可行解。
2.2 適應值函數(shù)設計
蝙蝠通過適應度值不斷調(diào)整自己的飛行方向,本文的適應值函數(shù)定義為
(12)
式中wi為未知節(jié)點與第i個錨節(jié)點距離的權(quán)重;m為錨節(jié)點的個數(shù)。
2.3 BADV-Hop算法的工作流程
首先在將DV-Hop算法的未知節(jié)點定位誤差轉(zhuǎn)換為一個全局最優(yōu)化問題,然后采用BA校正DV-Hop算法的定位誤差,以獲得更加理想的傳感器節(jié)點定位結(jié)果。具體流程如圖2所示。
圖2 BADV-Hop算法的工作流程Fig 2 Working process of BADV-Hop algorithm
3.1 仿真環(huán)境
為了驗證BADV-Hop算法的傳感器節(jié)點定位性能,在Windows XP系統(tǒng),AMD Athlon (tm) II X2 250處理器,3.00 GHz 3.25 G內(nèi)存平臺上,采用仿真軟件為Matlab 2012進行仿真實驗。同時在相同網(wǎng)絡環(huán)境下選擇標準DV-Hop算法進行對比實驗,對不同錨節(jié)點密度、不同通信半徑、測距誤差等方面進行了比較,采用平均定位誤差評價定位算法性能,其定義如下
(13)
3.2 結(jié)果與分析
3.2.1 定位誤差比較
DV-Hop算法、BADV-Hop算法的未知節(jié)點定位誤差如圖3所示。從圖3可知,BADV-Hop算法的定位誤差變化相當平穩(wěn),而DV-Hop算法的定位誤差變化十分劇烈,而且定位誤差相差較大,對比結(jié)果表明:BADV-Hop算法通過BA對DV-Hop算法進行優(yōu)化后,定位結(jié)果得到一定的改善。
圖3 DV-Hop算法和BADV-Hop算法的定位誤差變化曲線Fig 3 Positioning error change curves of DV-Hop algorithm and BADV-Hop algorithm
3.2.2 錨節(jié)點個數(shù)對定位性能的影響
不同錨節(jié)點個數(shù)條件下,2種算法的定位誤差變化曲線如圖4所示,從圖4可知,在相同錨節(jié)點比例下,相比于DV-Hop算法,BADV-Hop算法的平均定位誤差減少了7.23 %左右,結(jié)果表明:BADV-Hop算法能夠在較小的錨節(jié)點密度下,完成更精確的定位。
圖4 不同錨節(jié)點個數(shù)下的定位性能Fig 4 Positioning performance of different anchor nodes
3.2.3 通信半徑下對定位結(jié)果的影響
不同通信半徑對定位性能的影響程度如圖5所示,可以看出:在相同通信半徑條件下,相對于DV-Hop算法,BADV-Hop算法的定位精度得到大幅度提高,有效降低了WSNs的節(jié)點定位誤差。
圖5 不同通信半徑下的定位性能Fig 5 Positioning performance of different communication radius
為了提高WSNs定位精度,提出一種BA和DV-Hop算法相融合的BADV-Hop節(jié)點定位算法,該算法采用BA校正DV-Hop算法的定位誤差,仿真結(jié)果表明:相比于DV-Hop算法,BADV-Hop算法獲得更優(yōu)的節(jié)點定位結(jié)果,優(yōu)勢十分明顯,在WSNs中具有廣泛的應用前景。
[1] 王福豹,史 龍,任豐原.無線傳感器網(wǎng)絡中的自身定位系統(tǒng)和算法[J].軟件學報,2005,16(5): 857-868.
[2] 趙仕俊,孫美玲,唐懿芳.基于遺傳模擬退火算法的無線傳感器網(wǎng)絡定位算法[J].計算機應用與軟件,2009,26(10):189-192.
[3] 孫澤宇,魏 巍.一種改進無線傳感器網(wǎng)絡定位算法的研究[J].計算機仿真,2010,27(9): 125-127.
[4] Langendoen K,Reijers N.Distributed localization in wireless sensor networks: A quantitative comparison[J].Computer Networks,2013,43(4): 499-518.
[5] Geng Y,He J,Pahlavan K.Modeling the effect of human body on TOA based indoor human tracking[J].International Journal of Wireless Information Networks,2014,20(4):306-317.
[6] Patwari N,Hero A,Perkins M,et al.Relative location estimation in wireless sensor networks [J].IEEE Transactions on Signal Processing,2013,51(8): 2137-2148.
[7] 李 輝,熊盛武,劉 毅,等.無線傳感器網(wǎng)絡DV-Hop定位算法的改進[J].傳感技術(shù)學報,2011,24(12): 1782-1786.
[8] 毛科技,趙小敏,何文秀,等.WSNs中基于區(qū)域劃分的半自動DV-Hop定位算法[J].計算機科學,2012,39(3): 39-42.
[9] 葉 蓉,趙靈鍇.基于蟻群粒子群混合的無線傳感器網(wǎng)絡定位算法[J].計算機測量與控制,2011,19(3): 732-735.
[10] 陳星舟,廖明宏,林建華.基于粒子群優(yōu)化的無線傳感器網(wǎng)絡節(jié)點定位改進[J].計算機應用,2010,30(7):1736-1739.
[11] Yang X S,Gandomi A H.Bat algorithm:A novel approach for global engineering optimization[J].Engineering Computations,2012,29(5): 464-483.
Node localization method of WSNs based on BADV-Hop*
BAI Wei1, LI Feng-ying1, ZHENG Hai-yang1, LIU Ya-hong2, FENG Hai-lin2
(1.College of Mathematics and Computer Science,Ningxia Normal University,Guyuan 756000,China;2.School of Science,Xidian University,Xi’an 710071,China)
Aiming at problem of big error of node localization of wireless sensor networks(WSNs),propose a localization algorithm which is the fusion of bat algorithm (BA) and DV-Hop algorithm (BADV-Hop).Firstly,distance between unknown node and anchor node is measured,and then the coordinate of unknown nodes is determined by using DV-Hop algorithm,then BA is used to correct localization error of DV-Hop algorithm,finally,simulation analysis is carried out on algorithm characteristics on Matlab 2012 platform.Results show that compared with DV-Hop algorithm,BADV-Hop algorithm can improve localization precision of node.
wireless sensor networks(WSNs); DV-Hop algorithm; node localization; bat algorithm(BA)
10.13873/J.1000—9787(2014)10—0118—03
2014—07—10
國家自然科學基金資助項目(71271165,60874085)
TP 393
A
1000—9787(2014)10—0118—03
白 偉(1983-),男,寧夏中寧人,碩士,講師,主要研究領域為傳感網(wǎng)節(jié)點定位、信道盲估計和自組織網(wǎng)絡。