改進(jìn)生物地理學(xué)優(yōu)化算法的無線傳感器節(jié)點定位

馬世歡，張亞楠

改進(jìn)生物地理學(xué)優(yōu)化算法的無線傳感器節(jié)點定位

馬世歡，張亞楠

節(jié)點定位是無線傳感器網(wǎng)絡(luò)的應(yīng)用基礎(chǔ)，針對DV-Hop算法定位誤差的缺陷和提高節(jié)點的定位精度，提出一種生物地理學(xué)優(yōu)化算法的無線傳感器節(jié)點定位方法。首先，對標(biāo)準(zhǔn)生物地理學(xué)優(yōu)化算法進(jìn)行改進(jìn)，提高其全局搜索能力，然后，利用改進(jìn)生物地理學(xué)代替DV-Hop算法第三階段的最小二乘算法，對節(jié)點定位結(jié)果進(jìn)行優(yōu)化，最后，在Matlab 2012平臺上對算法的定位性能進(jìn)行仿真分析。仿真結(jié)果表明，相對于DV-Hop算法，其算法提高了節(jié)點的定位精度，大幅度降低了節(jié)點的定位誤差，具有更高的實際應(yīng)用價值。

無線傳感器網(wǎng)絡(luò)；節(jié)點定位；生物地理學(xué)優(yōu)化算法；平均跳距

0 引言

隨著無線技術(shù)和通信技術(shù)的發(fā)展，無線傳感器網(wǎng)絡(luò)（wireless sensor network，WSN）應(yīng)運(yùn)而生，其廣泛應(yīng)用于國防軍事、搶險救災(zāi)、環(huán)境監(jiān)測、預(yù)防控制、倉庫管理、維護(hù)秩序等領(lǐng)域[1]。在實際應(yīng)用中，沒有位置消息的數(shù)據(jù)沒有什么任何價值，因此對節(jié)點進(jìn)行高精度的定位已經(jīng)成為當(dāng)前無線傳感器網(wǎng)絡(luò)研究中的重點[2]。

針對無線傳感器網(wǎng)絡(luò)節(jié)點定位問題，國內(nèi)外許多研究團(tuán)隊和研究機(jī)構(gòu)進(jìn)行了廣泛、深入研究，提出了許多有效的傳感器節(jié)點定位算法。現(xiàn)階段節(jié)點定位算法主要分為兩類：基于測距（Range-based）[3]和基于非測距（Range-free）[4]。測距算法主要包括：接收信號強(qiáng)度、到達(dá)時間和到達(dá)角度等[5-7]，它們受環(huán)境因素影響較大，定位結(jié)果不穩(wěn)定，而且定位結(jié)果與測距設(shè)備直接相關(guān)，定位成本高，魯棒性差，定位精度低[8]。非測距算法主要通過少量錨節(jié)點對未知節(jié)點實現(xiàn)定位，定位成本低，其中DV-Hop算法作為最具代表的非測距算法，在無線傳感器定位中得到了廣泛應(yīng)用[9]。但是基本DV-Hop算法存在受網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)影響大，定位誤差大，精度低等不足，為此，許多學(xué)者對DV-Hop算法的工作原理進(jìn)行了分析，對其不足進(jìn)行了相應(yīng)改進(jìn)，如文獻(xiàn)[10]對錨節(jié)點每一跳距的計算方式進(jìn)行了改進(jìn)，減小了平均跳距的計算誤差，提高了節(jié)點的定位精度；文獻(xiàn)[11]將未知節(jié)點看作虛擬錨節(jié)點，提高了錨節(jié)點的密度，但其存在累計誤差比較大的缺陷；文獻(xiàn)[12]在計算平均每跳距的基礎(chǔ)上，采用如粒子群、遺傳算法等對未知節(jié)點的定位結(jié)果進(jìn)行了優(yōu)化，定位結(jié)果得到了改善。生物地理學(xué)優(yōu)化（biogeography-based optimization，BBO）算法是一種新的群智能算法，相對于其它群智能算法，BBO算法具有簡單、調(diào)節(jié)參數(shù)少等優(yōu)點，成功應(yīng)用于優(yōu)化問題求解中[13]。

為了改善無線傳感器節(jié)點的定位效果，針對DV-Hop算法的不足，提出一種BBO算法優(yōu)化DV-Hop的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法（BBO-DVHop），并通過仿真實驗對算法的性能進(jìn)行測試和分析。

1 生物地理學(xué)優(yōu)化算法

1.1 標(biāo)準(zhǔn)BBO算法

2008年，Simon等提出了生物地理學(xué)（BBO）算法，其模擬自然界的種群相鄰個體遷移和特別個體的突變過程對信息進(jìn)行更新，從而找到問題的全局最優(yōu)解[14]。

1.1.1 遷移率

設(shè)第s個棲息地物種數(shù)量為s，那么物種遷入和遷出率計算公式（1）：

式中，λ和μ分別為遷入率和遷出率；I和E分別表示最大遷入率和遷出率。

1.1.2 突變率

根據(jù)物種數(shù)量s、概率Ps對特征變量進(jìn)行突變，突變概率函數(shù)的計算公式（2）：

式中，Mmax為最大突變率；Pmax=arg(max(Ps))，s=1,2,…,n，Ps計算化式為公式（3）：

1.2 生物地理學(xué)優(yōu)化算法的改進(jìn)

BBO算法存后期收斂速度慢、易陷入局部最優(yōu)等不足，為此，本文對BBO算法進(jìn)行相應(yīng)的改進(jìn)，以提高其全局搜索能力。

（1） BBO算法采用線性遷移模型計算遷入率λ和遷出率 μ，導(dǎo)致算法的收斂速度比較慢，為此，采用余弦遷移模型替代線性遷移模型，具體如公式（4）：

（2）首先根據(jù)λi選擇需要遷入的棲息地Xi，確定Xi后，根據(jù)μj選擇需要遷出的棲息地Xj；然后從Xj中隨機(jī)地選擇SIV替代Xi中相應(yīng)的SIV，最后對遷移算子進(jìn)行加權(quán)，那么遷移算子變?yōu)楣剑?）：

式中，α是隨機(jī)數(shù)。

2 BBO-DVHop算法

2.1 DV-Hop算法

（1）計算未知節(jié)點與錨節(jié)點的最小跳數(shù)。在無線傳感器網(wǎng)絡(luò)，每個錨節(jié)點廣播自身分組信息：{(ID,(x,y),hop)給鄰居節(jié)點，且hop=0；當(dāng)未知節(jié)點接收到一個錨節(jié)點的分組信息后就保存該錨節(jié)點的最小跳數(shù)，并將 hop=hop+1轉(zhuǎn)發(fā)給鄰居節(jié)點，若該分組信息來自同一錨節(jié)點，則忽略，這樣全部節(jié)點可以保存任一錨節(jié)點間的最小跳數(shù)。

（2）估算未知節(jié)點的平均每跳距離。設(shè)錨節(jié)點i,j的坐標(biāo)分別為(xi,yi)，(xj,yj)，i與j之間的最小跳段數(shù)為hopj，任一錨節(jié)點的平均跳距計算公式為公式（6）：

未知節(jié)點接收、保存錨節(jié)點在網(wǎng)絡(luò)中廣播的自身平均每跳距離，且僅保存其接收到的第1個數(shù)值，繼續(xù)轉(zhuǎn)發(fā)該跳距，以保證盡可能多的未知節(jié)點保存平均跳距是從離其最近的錨節(jié)點處獲得[15]。

（3）計算未知節(jié)點位置。設(shè)與未知節(jié)點 D(x,y)可以直接通信的錨節(jié)點為：并假設(shè)步驟（2）中計算未知節(jié)點 D(x,y)與相應(yīng)錨節(jié)點距離分別為d1,d2,···dn，那么如公式（7）：

可表示為線性方程組AL+ε=b，ε為機(jī)誤差向量，

采用最小二乘算法求得方程的解為公式（8）：

2.2 DV-Hop算法存在的不足

在DV-Hop定位算法中，選擇具有最小折點的幾個跳段為未知節(jié)點與錨節(jié)點之間的直線段，那么該折線段中各點越接近共線，誤差越小。由于網(wǎng)絡(luò)中節(jié)點隨機(jī)分布，共線概率較低，誤差必然存在。dn是由未知節(jié)點到錨節(jié)點的估算平均跳距與最小跳數(shù)乘積等效替代，包含很大的誤差，向量b的每個元素均包含測量距離dn，而dn卻包含很大的誤差，因此根據(jù)式(8)求得的未知節(jié)點坐標(biāo)精度相對較低，為提高定位精度，將問題轉(zhuǎn)化為優(yōu)化估算距離dn的問題。

設(shè)未知節(jié)點 D(x,y)到錨節(jié)點 A1,A2,L ,An的實際距離為 r1,r2,L,rn，相應(yīng)的測距誤差為 ε1,ε2,L ,εn，應(yīng)滿足式(7)可轉(zhuǎn)換為公式（9）：

當(dāng)式（10）取得最小值時，未知節(jié)點的估計坐標(biāo)最接近真實坐標(biāo)，定位誤差最小，本文采用生物地理學(xué)優(yōu)化算法對式（10）進(jìn)行求解，以提高節(jié)點定位精度。

2.3 BBO對定位結(jié)果的優(yōu)化步驟

為了進(jìn)一步提高無線傳感器節(jié)點定位精度，利用 BBO算法的全局搜索能力，對DV-Hop算法定位結(jié)果進(jìn)行優(yōu)化，具體步驟如下：

（1）設(shè)未知節(jié)點D(x,y)與其相鄰的錨節(jié)點數(shù)為num。

（2）根據(jù)式（7）計算 num個相鄰錨節(jié)點的坐標(biāo)值以及與未知節(jié)點D(x,y)的距離，建立式（9）的約束條件。

（3）初始化BBO算法的相關(guān)參數(shù)，并隨機(jī)初始化適宜度向量xi，i=1,2,…,NP，每個向量對應(yīng)未知節(jié)點D(x,y)位置的可行解。

（4）根據(jù)適應(yīng)度函數(shù)計算棲息地i的適應(yīng)度值，并計算棲息地i對應(yīng)的物種數(shù)量si、遷入率λ和遷出率μi，i=1,2,…,NP，適應(yīng)度函數(shù)定義如公式（11）：

（5）對棲息地的SIV進(jìn)行調(diào)整，并重新計算棲息地的適應(yīng)度值。

（6）更新概率 Ps和突變率，并重新計算棲息地的適應(yīng)度值。

（7）如果滿足終止束條件，保存最優(yōu)的適宜度向量，反之，則返回步驟(4)繼續(xù)優(yōu)化。

（8）根據(jù)最優(yōu)適宜度向量得到未知節(jié)點D(x,y)的位置。

3 仿真實驗

3.1 仿真參數(shù)

為了驗證BBO-DVHop算法的有效性，在Matlab 2012平臺選擇DV-Hop算法進(jìn)行對比仿真實驗。采用平均定位誤差(error)作為定位結(jié)果評價標(biāo)準(zhǔn)，error計算公式為公式（12）：

表1 仿真實驗參數(shù)

3.2 結(jié)果與分析

3.2.1 測距誤差對定位結(jié)果影響

當(dāng)在節(jié)點的測距誤差發(fā)生變化的情況下，DV-Hop、BBO-DVHop算法的平均定位誤差變化曲線如圖1所示：

圖1 測距誤差對定位結(jié)果的影響

從圖 1可以看出，隨著測距誤差的增加，DV-Hop、BBO-DVHop的平均定位誤差隨之增加，這主要由于定位誤差不斷的累計影響了未知節(jié)點的定位精度。BBO-DVHop算法由于采用BBO算法對DVHop算法的定位結(jié)果進(jìn)行優(yōu)化，可以較好地抑制節(jié)點測距誤差累計的干擾，因此，在相同測距誤差條件下，BBO-DVHop算法的定位精度要高于PSO-DVHop算法，從而對測距誤差具有更好的魯棒性。

3.2.2 錨節(jié)點數(shù)對定位結(jié)果影響

錨節(jié)點數(shù)量為5～40的情況下，DV-Hop、BBO-DVHop的平均定位誤差仿真結(jié)果如圖2所示：

圖2 不同數(shù)量錨節(jié)點的平均定位誤差比較

從圖2可知，隨著錨節(jié)點的增加，DV-Hop、BBO-DVHop的平均定位誤差下降，這主要是由于錨節(jié)點數(shù)的增加，節(jié)點的平均定位精度相應(yīng)提高。當(dāng)錨節(jié)點數(shù)量相同時，BBO-DVHop算法的平均定位誤差小于DV-Hop算法，當(dāng)錨節(jié)點數(shù)量大于20后，BBO-DVHop算法的優(yōu)勢更加明顯，對比結(jié)果表明，BBO-DVHop提高了節(jié)點的定位精度，在相同定位精度要求，可以大幅度減少錨節(jié)點的數(shù)量，有效降低了節(jié)點的定位成本。

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

不同通信半徑條件，可以選擇鄰居節(jié)點數(shù)是不相同的，當(dāng)節(jié)點的通信半徑發(fā)生變化時，DV-Hop、BBO-DVHop的平均定位誤差仿真結(jié)果如圖3：

圖3 不同通信半徑的平均定位誤差對比

從圖3可以明顯看出，隨著通信半徑的增大，DV-Hop，BBO-DVHop算法的定位誤差不斷減小，這主要是由于隨著通信半徑的增加，節(jié)點獲得鄰居錨節(jié)點的概率增加，定位的精度得以提高，同時，在相同通信半徑條件下，BBO-DVHop的定位誤差小于DV-Hop算法，具有一定的優(yōu)勢。

4 總結(jié)

針對傳感器節(jié)點定位問題，在分析DV-Hop算法存在的不足基礎(chǔ)上，提出一種BBO算法優(yōu)化DV-Hop定位結(jié)果的感器節(jié)點定位算法，并針對標(biāo)準(zhǔn)BBO算法存在的不足進(jìn)行了改進(jìn)，最后采用仿真對比實驗對算法的定位精度、平均定位速度進(jìn)行了分析，仿真實驗結(jié)果表明，相比于DV-Hop算法以及其它改進(jìn)DV-Hop算法，BBO-DVHop提高了傳感器節(jié)點的定位精度，降低了定位計算過程中的復(fù)雜度，是一種簡單、實用的無線傳感器節(jié)點定位方法。

[1]王汝傳,孫麗娟.無線傳感器網(wǎng)絡(luò)技術(shù)及其應(yīng)用[M]. 北京:人民郵電出版社,2011.

[2]孫利民,李建中,陳瑜,等.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2005: 135-155.

[3]Garg V, Jhamb M. A Review of wireless sensor network on localization techniques [J]. International Journal of Engineering Trends and Technology,2013, 4(4): 1049-1053.

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

[5]Bulusu N, Heidemann J, Estrin D. GPS-less low cost out door localization for very small devices [J]. IEEE Personal Communication, 2000, 7(5):28-34.

[6]安文秀, 趙菊敏, 李燈熬. 基于Amorphous的無線傳感器網(wǎng)絡(luò)定位算法研究[J].傳感器與微系統(tǒng) 2013, 32(2): 33-35.

[7]王珊珊,殷建平.求解無線傳感器網(wǎng)絡(luò)定位問題的線性規(guī)劃算法[J].計算機(jī)研究與發(fā)展2009,46(5): 705-712.

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

[9]衣曉,王梓有,薛興亮.一種基于次錨節(jié)點的無線傳感器網(wǎng)絡(luò)質(zhì)心定位算法[J].計算機(jī)應(yīng)用與軟件,2013, 30(6):116–120.

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

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

[12]Zhao Yan Huang, Qian Zhi Hong, Shang Xiao Hang. PSO localization algorithm for WSN nodes based on modifying average hop distances [J].Journal on Communications, 2013, 34(9):105-114.

[13]趙吉,付毅,梅娟.基于粒子群算法的改進(jìn) DV-Hop定位算法[J].計算應(yīng)用與軟件, 2012,29(12):69-72.

[14]高凱歌, 鄭向偉. 基于中值遷移和柯西變異的生物地理學(xué)優(yōu)化算法[J].計算機(jī)工程與設(shè)計,2013,34(4): 1292-1295.

[15]李輝,熊盛武,劉毅,等.無線傳感器網(wǎng)絡(luò) DV-Hop定位算法的改進(jìn)[J].傳感技術(shù)學(xué)報,2011,24(12): 1782-1786.

Node Localization Based on DV-Hop Optimizing by Improved Biogeography-based Optimization Algorithm

Ma Shihuan, Zhang Yanan
(Department of Computer Engineering, Henan Polytechnic Institute, NanYang 473000, China)

Node localization is a basic application of wireless sensor network. Aiming at the defects of DV-Hop algorithm of positioning error and the improvements of node positioning accuracy, this paper proposes a node localization algorithm of wireless sensor with biogeography-based optimization. Firstly, the standard biogeography-based optimization algorithm is improved to obtain a better ability to do global search, and then replace the less squares algorithm in the third step of DV-Hop with the improved biogeography-based optimization to improve the results of node localization. Finally, simulate and analyze the localization performance of this algorithm on the Matlab 2012 platform. The simulation results show that, compared with DV-Hop algorithm, the proposed algorithm improves the localization accuracy of nodes and reduces the positioning error greatly. It has higher value for practical application.

Wireless Sensor Networks; Node Localization; Biogeography-based Optimization Algorithm; Average Hop Distance

TP311

A

2014.04.23）

1007-757X(2015)05-0050-04

馬世歡（1976-），男，河南南陽人，河南工業(yè)職業(yè)技術(shù)學(xué)院，計算機(jī)工程系，講師，碩士，研究方向：軟件技術(shù)，南陽，473000張亞楠（1985-），女，河南南陽人，河南工業(yè)職業(yè)技術(shù)學(xué)院，計算機(jī)工程系，講師，碩士，研究方向：計算機(jī)應(yīng)用，南陽，473000