基于BADV-Hop的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方法*

白 偉，李鳳英，鄭海洋，劉亞紅，馮海林

(1.寧夏師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，寧夏 固原 756000;2.西安電子科技大學(xué) 理學(xué)院，陜西 西安 710071)

基于BADV-Hop的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方法*

白 偉1，李鳳英1，鄭海洋1，劉亞紅2，馮海林2

(1.寧夏師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，寧夏 固原 756000;2.西安電子科技大學(xué) 理學(xué)院，陜西 西安 710071)

針對(duì)無線傳感器網(wǎng)絡(luò)(WSNs)節(jié)點(diǎn)的定位誤差較大的問題，提出一種蝙蝠算法(BA)和DV-Hop算法融合(BADV-Hop)的定位算法。首先測(cè)量未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離，然后采用DV-Hop算法初步確定未知節(jié)點(diǎn)的坐標(biāo)，再采用BA校正DV-Hop算法的定位誤差，最后在Matlab 2012平臺(tái)上對(duì)算法性能進(jìn)行仿真分析。實(shí)驗(yàn)結(jié)果表明:相對(duì)于DV-Hop算法，BADV-Hop算法提高了傳感器的節(jié)點(diǎn)定位精度。

無線傳感器網(wǎng)絡(luò)；DV-Hop算法；節(jié)點(diǎn)定位；蝙蝠算法

0 引 言

節(jié)點(diǎn)的位置信息是無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)成功應(yīng)用前提和基礎(chǔ)，其可以完成網(wǎng)絡(luò)拓?fù)渥怨芾?、提高?jié)點(diǎn)間路由效率等，因此,傳感器節(jié)點(diǎn)定位一直是WSNs研究中的重點(diǎn)和難點(diǎn)[1]。

目前,WSNs定位算法分為兩類：基于測(cè)距(range-based)的定位算法和免測(cè)距(range-free)定位算法[2]。Range-based定位算法首先利用計(jì)算節(jié)點(diǎn)間的距離，然后根據(jù)三邊(三角、多邊)測(cè)量法確定未知節(jié)點(diǎn)的位置，其需額外硬件設(shè)備來測(cè)量節(jié)點(diǎn)間距離，成本高和能耗大，對(duì)WSNs生存時(shí)間產(chǎn)生不利影響[3]；Range-free定位算法根據(jù)節(jié)點(diǎn)間的通信估計(jì)出節(jié)點(diǎn)間距離，再確定未知節(jié)點(diǎn)的位置，主要有質(zhì)心定位算法、DV-Hop算法、APIT算法，該類算法功耗小、成本低，引起了人們的廣泛關(guān)注[4～7]。其中,DV-Hop算法應(yīng)用最為廣泛，在DV-Hop算法的基礎(chǔ)上，一些學(xué)者提出采用群智能算法對(duì)DV-Hop算法進(jìn)行改進(jìn)，如粒子群算法、遺傳算法等，以提高了WSNs的節(jié)點(diǎn)定位精度[8,9]。但是這些算法存在著易陷入局部最優(yōu)、縮小搜索空間等問題，影響WSNs的傳感器節(jié)點(diǎn)定位精度[10]。

蝙蝠算法(bat algorithm，BA)是一種通過模擬蝙蝠回聲定位行為的新型群智能算法，相對(duì)于其他算法，其在迭代尋優(yōu)方面具有很大優(yōu)勢(shì)，且需要調(diào)整參數(shù)較少[11]。為了減少WSNs節(jié)點(diǎn)的定位誤差，以獲得更加理想的傳感器節(jié)點(diǎn)定位結(jié)果，本文提出一種基于BA校正DV-Hop(BADV-Hop)算法的傳感器節(jié)點(diǎn)定位方法，并在Matlab 2012平臺(tái)上對(duì)算法性能進(jìn)行仿真分析。仿真結(jié)果表明：在相同條件下，BADV-Hop算法提高了傳感器節(jié)點(diǎn)的定位精度，具有定的實(shí)用價(jià)值。

1 DV-Hop算法和BA

1.1 DV-Hop算法

Nieuleseu等人提出了DV-Hop傳感器節(jié)點(diǎn)定位算法，具有無需測(cè)量距離、硬件要求低等特點(diǎn)，其定位步驟具體如下：

1)計(jì)算未知節(jié)點(diǎn)和錨節(jié)點(diǎn)之間的最小跳數(shù)。

2)計(jì)算未知錨節(jié)點(diǎn)之間每跳的平均距離：當(dāng)每個(gè)錨節(jié)點(diǎn)都得到了其與其他錨節(jié)點(diǎn)間的最小跳數(shù)時(shí)，整個(gè)網(wǎng)絡(luò)中的平均每跳距離計(jì)算公式為

(1)

式中 (xi,yi)和(xj,yj)代表節(jié)點(diǎn)i和j的坐標(biāo)信息；hopij代表節(jié)點(diǎn)i和j之間的最小跳數(shù)。節(jié)點(diǎn)就可以計(jì)算出其自身和錨節(jié)點(diǎn)之間的距離[8]。

3)計(jì)算每一個(gè)未知節(jié)點(diǎn)的位置坐標(biāo):設(shè)P1(x1,y1),P2(x2,y2),…,Pn(xn,yn)表示n個(gè)錨節(jié)點(diǎn)的坐標(biāo)位置，待定位節(jié)點(diǎn)位置為(x,y)，其與錨節(jié)點(diǎn)估計(jì)距離分別為d1,d2,…,dn-1，可以建立式(2)的方程

(2)

在WSNs節(jié)點(diǎn)測(cè)距過程中，不可避免會(huì)產(chǎn)生一些隨機(jī)誤差，這樣線性方程組[8]為AL+N=b，N為誤差向量，求解方程為

L=(ATA)-1ATb.

(3)

設(shè)錨節(jié)點(diǎn)i與未知節(jié)點(diǎn)的實(shí)際距離為ri，測(cè)距誤差為εi,那么,未知節(jié)點(diǎn)的坐標(biāo)(x,y)應(yīng)該滿足一定約束條件，求解(x,y)，使得

(4)

由式(4)可知，節(jié)點(diǎn)位置一定存在于該區(qū)域中，而且當(dāng)f(x,y)取最小值時(shí)，節(jié)點(diǎn)定位總誤差最小，此時(shí)的坐標(biāo)(x,y)將為未知節(jié)點(diǎn)位置的最優(yōu)值，因此,WSNs的節(jié)點(diǎn)定位問題轉(zhuǎn)化成一個(gè)約束優(yōu)化問題，然后采用BA進(jìn)行求解，以提高傳感器定位精度。

1.2 BA

BA是一種劍橋大學(xué)的Yang XinShe 受到微型蝙蝠的回聲定位行為方式與目標(biāo)函數(shù)優(yōu)化關(guān)聯(lián)性啟發(fā)的群智能優(yōu)化算法。

1.2.1 虛擬蝙蝠的運(yùn)動(dòng)

fi=fmin+(fmax-fmin)β,

(5)

(6)

(7)

對(duì)于局部搜索，一旦在當(dāng)前最優(yōu)解中選中了一個(gè)解，那么，每只蝙蝠按照隨機(jī)游走法則產(chǎn)生局部新解

xnew=xold+εAt,

(8)

式中ε∈[-1,1]為一個(gè)隨機(jī)數(shù)；At=〈At〉為所有蝙蝠在同一個(gè)時(shí)間段的平均音量。

1.2.2 音量和脈沖發(fā)生率

根據(jù)蝙蝠的生物學(xué)機(jī)理，在搜尋獵物的過程中，蝙蝠在初始階段發(fā)出的超聲波脈沖音強(qiáng)大而頻率低，以利于在更廣泛的空間內(nèi)進(jìn)行搜索；當(dāng)發(fā)現(xiàn)獵物后，脈沖音強(qiáng)逐漸減小同時(shí)脈沖發(fā)射次數(shù)增加，以精確掌握獵物的空間位置。音強(qiáng)和脈沖發(fā)生率的更新公式

(9)

為了驗(yàn)證BA的收斂速度、尋優(yōu)精度優(yōu)于粒子群優(yōu)化(PSO)算法、遺傳算法(GA)等，采用2個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行對(duì)比實(shí)驗(yàn)，測(cè)試函數(shù)如下

(10)

(11)

從圖1可知，相對(duì)于PSO,GA，BA經(jīng)過更小的迭代次數(shù)就可以找到達(dá)到函數(shù)的最優(yōu)解，對(duì)比結(jié)果驗(yàn)證了本文采用BA的合理性和有效性。

圖1 BA算法與其它算法的性能比較Fig 1 Performance comparison of BA and other algorithms

2 BADV-Hop節(jié)點(diǎn)定位精度提高方法

2.1 編碼設(shè)計(jì)

由于WSNs節(jié)點(diǎn)定點(diǎn)定位目標(biāo)就要求尋找一個(gè)與實(shí)際位置誤差最小的位置，因此,可以認(rèn)為每一個(gè)蝙蝠位置對(duì)應(yīng)未知節(jié)點(diǎn)的一個(gè)可行解。

2.2 適應(yīng)值函數(shù)設(shè)計(jì)

蝙蝠通過適應(yīng)度值不斷調(diào)整自己的飛行方向，本文的適應(yīng)值函數(shù)定義為

(12)

式中wi為未知節(jié)點(diǎn)與第i個(gè)錨節(jié)點(diǎn)距離的權(quán)重；m為錨節(jié)點(diǎn)的個(gè)數(shù)。

2.3 BADV-Hop算法的工作流程

首先在將DV-Hop算法的未知節(jié)點(diǎn)定位誤差轉(zhuǎn)換為一個(gè)全局最優(yōu)化問題，然后采用BA校正DV-Hop算法的定位誤差，以獲得更加理想的傳感器節(jié)點(diǎn)定位結(jié)果。具體流程如圖2所示。

圖2 BADV-Hop算法的工作流程Fig 2 Working process of BADV-Hop algorithm

3 仿真實(shí)驗(yàn)

3.1 仿真環(huán)境

為了驗(yàn)證BADV-Hop算法的傳感器節(jié)點(diǎn)定位性能，在Windows XP系統(tǒng)，AMD Athlon (tm) II X2 250處理器，3.00 GHz 3.25 G內(nèi)存平臺(tái)上，采用仿真軟件為Matlab 2012進(jìn)行仿真實(shí)驗(yàn)。同時(shí)在相同網(wǎng)絡(luò)環(huán)境下選擇標(biāo)準(zhǔn)DV-Hop算法進(jìn)行對(duì)比實(shí)驗(yàn)，對(duì)不同錨節(jié)點(diǎn)密度、不同通信半徑、測(cè)距誤差等方面進(jìn)行了比較，采用平均定位誤差評(píng)價(jià)定位算法性能，其定義如下

(13)

3.2 結(jié)果與分析

3.2.1 定位誤差比較

DV-Hop算法、BADV-Hop算法的未知節(jié)點(diǎn)定位誤差如圖3所示。從圖3可知，BADV-Hop算法的定位誤差變化相當(dāng)平穩(wěn)，而DV-Hop算法的定位誤差變化十分劇烈，而且定位誤差相差較大，對(duì)比結(jié)果表明:BADV-Hop算法通過BA對(duì)DV-Hop算法進(jìn)行優(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é)點(diǎn)個(gè)數(shù)對(duì)定位性能的影響

不同錨節(jié)點(diǎn)個(gè)數(shù)條件下，2種算法的定位誤差變化曲線如圖4所示，從圖4可知，在相同錨節(jié)點(diǎn)比例下，相比于DV-Hop算法，BADV-Hop算法的平均定位誤差減少了7.23 %左右，結(jié)果表明：BADV-Hop算法能夠在較小的錨節(jié)點(diǎn)密度下，完成更精確的定位。

圖4 不同錨節(jié)點(diǎn)個(gè)數(shù)下的定位性能Fig 4 Positioning performance of different anchor nodes

3.2.3 通信半徑下對(duì)定位結(jié)果的影響

不同通信半徑對(duì)定位性能的影響程度如圖5所示，可以看出：在相同通信半徑條件下，相對(duì)于DV-Hop算法，BADV-Hop算法的定位精度得到大幅度提高，有效降低了WSNs的節(jié)點(diǎn)定位誤差。

圖5 不同通信半徑下的定位性能Fig 5 Positioning performance of different communication radius

4 結(jié)束語

為了提高WSNs定位精度，提出一種BA和DV-Hop算法相融合的BADV-Hop節(jié)點(diǎn)定位算法，該算法采用BA校正DV-Hop算法的定位誤差，仿真結(jié)果表明:相比于DV-Hop算法，BADV-Hop算法獲得更優(yōu)的節(jié)點(diǎn)定位結(jié)果，優(yōu)勢(shì)十分明顯，在WSNs中具有廣泛的應(yīng)用前景。

[1] 王福豹,史 龍,任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報(bào),2005,16(5): 857-868.

[2] 趙仕俊,孫美玲,唐懿芳.基于遺傳模擬退火算法的無線傳感器網(wǎng)絡(luò)定位算法[J].計(jì)算機(jī)應(yīng)用與軟件,2009,26(10):189-192.

[3] 孫澤宇,魏 巍.一種改進(jìn)無線傳感器網(wǎng)絡(luò)定位算法的研究[J].計(jì)算機(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)絡(luò)DV-Hop定位算法的改進(jìn)[J].傳感技術(shù)學(xué)報(bào),2011,24(12): 1782-1786.

[8] 毛科技,趙小敏,何文秀,等.WSNs中基于區(qū)域劃分的半自動(dòng)DV-Hop定位算法[J].計(jì)算機(jī)科學(xué),2012,39(3): 39-42.

[9] 葉 蓉,趙靈鍇.基于蟻群粒子群混合的無線傳感器網(wǎng)絡(luò)定位算法[J].計(jì)算機(jī)測(cè)量與控制,2011,19(3): 732-735.

[10] 陳星舟,廖明宏,林建華.基于粒子群優(yōu)化的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位改進(jìn)[J].計(jì)算機(jī)應(yīng)用,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

國(guó)家自然科學(xué)基金資助項(xiàng)目(71271165,60874085)

TP 393

A

1000—9787(2014)10—0118—03

白 偉(1983-)，男，寧夏中寧人，碩士，講師，主要研究領(lǐng)域?yàn)閭鞲芯W(wǎng)節(jié)點(diǎn)定位、信道盲估計(jì)和自組織網(wǎng)絡(luò)。