靳春景，董雪瑩

(1.江西理工大學(xué) 信息工程學(xué)院，江西 贛州 341000; 2.南京郵電大學(xué) 光電工程學(xué)院，江蘇 南京 210023)

基于群體智能改進(jìn)無線傳感器網(wǎng)絡(luò)定位算法

靳春景1，董雪瑩2

(1.江西理工大學(xué) 信息工程學(xué)院，江西 贛州 341000; 2.南京郵電大學(xué) 光電工程學(xué)院，江蘇 南京 210023)

對經(jīng)典DV-Hop算法誤差比較大的現(xiàn)象進(jìn)行討論。對DV-Hop算法進(jìn)行改進(jìn)，提出BSADV-Hop算法。該算法分為兩大部分，第一部分對跳數(shù)計算方法進(jìn)行改進(jìn)；第二部分對平均每跳距離進(jìn)行尋優(yōu)。在這過程中采用一種群體智能算法——鳥群算法最終降低平均每跳距離導(dǎo)致的誤差。仿真實驗結(jié)果證明，與經(jīng)典DV-Hop和PSODV-Hop相比，該算法能更準(zhǔn)確地計算節(jié)點(diǎn)平均跳距，定位精度得以提高，并且體現(xiàn)出較好的穩(wěn)定性和可行性。

無線傳感器網(wǎng)絡(luò)；DV-Hop定位算法；鳥群算法；平均每跳距

0 引言

無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)定位算法按不同的標(biāo)準(zhǔn)可分為多種。在WSN中根據(jù)測距可將算法分兩種：基于測距定位算法和基于非測距定位算法?；跍y距的算法需要采用測量途徑得到距離信息，其中有以TOA[1]、TDOA以及RSSI為代表的定位技術(shù)?；跍y距的算法有兩點(diǎn)不足之處：(1)測距結(jié)果易受環(huán)境影響；(2)一般的測距過程中需要增加其他設(shè)備，這些設(shè)備需要花費(fèi)額外的能量用于通信。而以Centroid算法、DV-Hop算法[2]為代表的定位算法通常采用連通性定位，對硬件設(shè)備沒有其他的額外要求，在WSN定位過程花費(fèi)成本比較低。因此適合在大規(guī)模的傳感器網(wǎng)絡(luò)中應(yīng)用。

1 DV-Hop算法的誤差源頭

DV-Hop算法可分三個主要步驟[3]。

(1)無線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)最小跳數(shù)計算。

(2)錨節(jié)點(diǎn)獲取自身真實的位置。用公式(1)[4]計算平均每跳距離，信標(biāo)節(jié)點(diǎn)k的平均每跳距離為:

(1)

其中，信標(biāo)節(jié)點(diǎn)k的位置用(xk,yk)表示，第l個信標(biāo)節(jié)點(diǎn)的位置用(xl,yl)表示。hopkl為信標(biāo)節(jié)點(diǎn)k與信標(biāo)節(jié)點(diǎn)l之間的跳數(shù)。

待定位節(jié)點(diǎn)m接收離自己最近信標(biāo)節(jié)點(diǎn)的平均跳距，并利用步驟(1)得到的距錨節(jié)點(diǎn)的跳數(shù)來計算距信標(biāo)節(jié)點(diǎn)的長度：

Dmn=hopsize×hopmn

(2)

其中，Dmn是待定位節(jié)點(diǎn)m離自身最近信標(biāo)節(jié)點(diǎn)n的距離，hopsize是平均每跳距離的大小，它表示待定位節(jié)點(diǎn)m與最靠近它信標(biāo)節(jié)點(diǎn)n平均每跳距離的大小。hopmn為待定節(jié)點(diǎn)m到信標(biāo)節(jié)點(diǎn)n的跳數(shù)。

(3)通常用最小二乘法來計算待定節(jié)點(diǎn)位置。

經(jīng)典的DV-Hop算法比較容易實現(xiàn)節(jié)點(diǎn)位置的計算，并且花費(fèi)成本相對比較少，但定位精度就差強(qiáng)人意了。這主要是由平均每跳距離有誤差造成的。

圖1 跳數(shù)誤差來源示意圖

DV-Hop算法中的跳數(shù)求解中，經(jīng)常把在一跳范圍內(nèi)的節(jié)點(diǎn)都當(dāng)做一跳。A節(jié)點(diǎn)與B節(jié)點(diǎn)都在一跳范圍里，所以P節(jié)點(diǎn)把到節(jié)點(diǎn)A和到節(jié)點(diǎn)B的距離都記成一跳。但從圖1中，這一跳的距離明顯不等，故是誤差的源頭。

圖2 節(jié)點(diǎn)距離誤差示意圖

經(jīng)典的DV-Hop算法在求解信標(biāo)節(jié)點(diǎn)平均每跳距離時，經(jīng)常錯誤地把曲線的距離代替直線的距離進(jìn)行計算。如圖2所示，節(jié)點(diǎn)A到節(jié)點(diǎn)D的距離d顯然不等于d1+d2+d3。這樣就對定位精度產(chǎn)生影響。

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

2.1 線性糾正跳數(shù)

本節(jié)利用電磁場與電磁波理論中一個常見的理論，即信號的強(qiáng)度與信號傳播距離成負(fù)相關(guān)的理論。在無線傳感器中加入一個功能模塊，利用這個模塊計算接收的信號強(qiáng)度。用設(shè)定線性的閾值對節(jié)點(diǎn)接收的跳數(shù)問題進(jìn)行糾正。具體步驟如下：

(1)設(shè)定閾值為S0。

(2)設(shè)節(jié)點(diǎn)i到節(jié)點(diǎn)j的跳數(shù)為hopij，節(jié)點(diǎn)i接收到節(jié)點(diǎn)j的信號強(qiáng)度用Sij表示。

圖3 跳數(shù)糾正示意圖

2.2 鳥群算法的DV-Hop

2.2.1鳥群算法簡介

鳥群算法[6]是一種來自大自然的隨機(jī)搜索群體智能的尋優(yōu)方法。將鳥群行為特性抽象成如下規(guī)則進(jìn)行描述：

(1) 選擇覓食行為或選擇保持放哨行為由鳥本身隨機(jī)決定。

(2) 若選擇覓食行為，則該鳥承擔(dān)起尋找最佳覓食位置并對位置信息進(jìn)行時刻記錄更新，并且還要及時地廣播該信息到整個鳥群中。

(3) 若選擇不去覓食則保持放哨行為。整個鳥群的每只鳥均試圖競爭性地飛向整個鳥群的中間，鳥群的鳥飛往中心的可能性的大小是由自身擁有糧食多少決定的。

(4) 鳥群周期性遷徙。鳥群之間共享食物信息，鳥群中食物生產(chǎn)者具有超高的捕食本領(lǐng)，而乞食者則相反，其捕食本領(lǐng)為最差的。鳥的身份隨飛往的區(qū)域而改變。

(5) 第一批發(fā)現(xiàn)食物的鳥稱之為整個鳥群的生產(chǎn)者，乞食者隨機(jī)選擇跟在一個生產(chǎn)者身后祈求食物。隨機(jī)選擇哪一個是由規(guī)則(1)決定。當(dāng)在(0, 1)之間隨機(jī)生成的隨機(jī)數(shù)大于常數(shù)P時，鳥就選擇覓食行為，否則保持放哨行為。

規(guī)則(2)中每一只鳥進(jìn)行覓食的行為都是依據(jù)自己的經(jīng)驗，該經(jīng)驗可由下式進(jìn)行模擬：

(3)

對于規(guī)則(3)，鳥競爭性飛往種群中央，這種行為用下式表示：

(4)

(5)

N2=a2×

(6)

表達(dá)式中，ε是在[1，S]隨機(jī)取整,規(guī)定ε與h不同，其中S是種群數(shù)量的多少；a1、a2是[0,2]之間常數(shù)；pFith表示第h只鳥適應(yīng)度值；sumFit代表所有鳥適應(yīng)度總和。ε為無窮小的常數(shù)，其作用保證發(fā)生分割。averagek表示種群適應(yīng)度平均值。

鳥群周期性遷徙可以躲避天敵，增加捕食的機(jī)會。假定遷徙的周期為FT，在整個鳥群中利用上述的規(guī)則(4)篩選生產(chǎn)者和乞食者。這兩種行為特征可利用下式進(jìn)行表征。

(7)

(8)

式(7)、(8)中rand(0,1)是服從標(biāo)準(zhǔn)正態(tài)分布中的隨機(jī)數(shù)；FP為乞食者隨機(jī)選擇跟在一個生產(chǎn)者身后祈求食物事件發(fā)生的概率，F(xiàn)P的值為小于1的正數(shù)。

本文構(gòu)建的數(shù)學(xué)模型采用最小均方誤差準(zhǔn)則，并且考慮到經(jīng)典的DV-Hop算法利用最小二乘法計算出來的位置坐標(biāo)不可避免存在誤差，因此利用鳥群算法進(jìn)行求解。

假定已知節(jié)點(diǎn)的實際坐標(biāo)信息。錨節(jié)點(diǎn)n與未知節(jié)點(diǎn)m之間的距離可用下式計算：

(9)

本文利用糾正后比較精確的跳數(shù)與利用式(1)求得的平均每跳距離相乘即可求得錨節(jié)點(diǎn)n與未知節(jié)點(diǎn)m之間的距離，即:

將未知節(jié)點(diǎn)與最近相鄰的信標(biāo)節(jié)點(diǎn)間的真實距離與測量計算得到距離的均方誤差設(shè)定成目標(biāo)函數(shù)G(x,y)。則目標(biāo)函數(shù)可以寫成如下形式：

(10)

其中w是待定位區(qū)域中信標(biāo)節(jié)點(diǎn)的數(shù)量，用(xm,ym)表示一個待定位的未知節(jié)點(diǎn)。而信標(biāo)節(jié)點(diǎn)用(xn,yn)表示。通過上述方法將求待定節(jié)點(diǎn)的坐標(biāo)轉(zhuǎn)化成一個求最優(yōu)的過程，通過多次的迭代計算從而求得目標(biāo)函數(shù)的最優(yōu)解，最終求解得精確度高的待定位節(jié)點(diǎn)坐標(biāo)信息。兩個坐標(biāo)節(jié)點(diǎn)之間的誤差即為定位誤差。通過上述過程，本文將鳥群最優(yōu)化問題轉(zhuǎn)化為求最小值的問題。

2.2.2BSADV-Hop算法流程

鳥群算法中，每一只鳥作為生產(chǎn)者的概率都是由自身的適應(yīng)度決定的。因此，利用鳥群算法求平均每跳距離的hopesizei，結(jié)合鳥群算法中鳥群行為簡化的規(guī)則，本文算法流程如下：

(1)初始化種群N。在待定位網(wǎng)絡(luò)中隨機(jī)進(jìn)行種群的分布。種群的大小設(shè)置為N，對BSA算法相關(guān)變量的參數(shù)大小進(jìn)行合理的設(shè)置，假設(shè)算法的參數(shù)做如下設(shè)置:C1=C2=1.5,C=S=1,FQ=5。

(2)設(shè)置公示板。公示板值的大小設(shè)置為 besty。公示板作用是當(dāng)每次進(jìn)行迭代時，記載每次的適應(yīng)度函數(shù)的最優(yōu)值，并廣播線性糾正后的跳數(shù)。

(3)迭代尋優(yōu)。利用BSADV-Hop算法進(jìn)行節(jié)點(diǎn)定位，每次迭代定位過程中利用式(10)得到適應(yīng)度函數(shù)G(x,y)的最優(yōu)值。

(4)計算新種群的適應(yīng)度值。

(5)判斷是否滿足終止條件。如果滿足終止條件就輸出最優(yōu)解和待定節(jié)點(diǎn)的坐標(biāo)。反之進(jìn)行迭代次數(shù)增1的操作并且回到步驟(3)繼續(xù)對種群進(jìn)行優(yōu)化和迭代計算。

3 算法仿真

本文仿真工具為MATLAB2012a。假設(shè)在邊長為100 m的正方形區(qū)域隨機(jī)將傳感器節(jié)點(diǎn)進(jìn)行拋撒。

本文對節(jié)點(diǎn)的定位精度的性能使用平均定位誤差Erroravg來評判。Erroravg表示待定位的未知節(jié)點(diǎn)的自身真實位置與經(jīng)BSADV-Hop算法后坐標(biāo)之間的差值。

評價定位誤差公式[7]如下：

本文設(shè)定PSODV-Hop[8]的參數(shù)為：C1=C2=1.5，慣性因子ωmax=1.2，ωmin=0.1;兩種算法的種群大小為200；迭代數(shù)為45。進(jìn)行實驗結(jié)果的對比分析。

從圖4可知，本文BSADV-Hop算法只需經(jīng)歷18次的迭代計算即可獲得很高的定位精度，而PSODV-Hop算法要得到相同的定位精度，其迭代的次數(shù)是BSADV-Hop的1.5倍。因此可以說本文的BSADV-Hop算法的收斂速度更快。

圖4 不同定位算法收斂速度比較

圖5中只把節(jié)點(diǎn)通信半徑作為自變量進(jìn)行分析比較。由圖可知，在這個實驗過程中保持節(jié)點(diǎn)的總數(shù)和錨節(jié)點(diǎn)數(shù)量不變，算法的定位精度整體上與通信半徑成負(fù)相關(guān)。從圖中易看出，在同等的半徑時，在節(jié)點(diǎn)的定位精度方面BSADV-Hop比PSODV-Hop和傳統(tǒng)的DV-Hop算法都高。

圖5 不同通信半徑的定位誤差比較

圖6表示，保持待定位區(qū)域總的節(jié)點(diǎn)數(shù)目不變，分別取5，10，15，…，40個錨節(jié)點(diǎn)，對算法定位的精度進(jìn)行分析。從圖中易得到，錨節(jié)點(diǎn)的個數(shù)與算法的定位優(yōu)劣成正相關(guān)。在同等的通信半徑下，比較三個算法的定位精度。經(jīng)典的DV-Hop算法比本文提出的算法定位精度低23%左右。PSODV-Hop算法也比本文的算法低。圖中可以得到低6%。本文的算法引入鳥群算法來優(yōu)化平均每跳距離，這樣降低了平均每跳距離引起的誤差。并且本文引入的鳥群算法，其最優(yōu)解搜索能力比較強(qiáng)，這樣本文提出算法可以較好地提高節(jié)點(diǎn)的定位精度。

圖6 不同信標(biāo)節(jié)點(diǎn)數(shù)量與定位誤差的關(guān)系

圖7表示在待定位的區(qū)域中，隨機(jī)進(jìn)行節(jié)點(diǎn)的部署。在實驗的過程中節(jié)點(diǎn)的通信半徑和錨節(jié)點(diǎn)的數(shù)量始終保持不變。本實驗過程中只改變節(jié)點(diǎn)的數(shù)量來進(jìn)行三個定位算法的精度比較。易從圖中得到，在定位精度方面，本文的算法優(yōu)于PSODV-Hop和經(jīng)典的DV-Hop算法，并且分別相對于它們提高了8%左右和30%左右。因此，可以得出本文提出的算法，在相同的節(jié)點(diǎn)數(shù)量條件下定位精度是最優(yōu)的。

圖7 不同節(jié)點(diǎn)總數(shù)量的誤差率比較

4 結(jié)論

本文對經(jīng)典的DV-Hop算法的不完善之處進(jìn)行了分析討論，對其缺點(diǎn)進(jìn)行改進(jìn)和完善，提出了BSADV-Hop算法。在求優(yōu)化模型時，采用鳥群算法進(jìn)行求解，并利用BSADV-Hop算法代替最小二乘法，降低計算誤差。通過實驗驗證，本文的BSADV-Hop算法比 PSODV-Hop算法在最優(yōu)解搜索能力上表現(xiàn)得更好。在不同的實驗條件和不同的變量條件下，分析了BSADV-Hop算法、PSODV-Hop算法和經(jīng)典的DV-Hop算法的定位精度和定位的開銷，得出本文提出的BSADV-Hop算法優(yōu)于PSODV-Hop算法和經(jīng)典的DV-Hop算法。

[1] KANG Y, WANG J. A high-precision TOA-based positioning algorithm without the restriction of strict time synchronization for wireless systems[J]. International Conference on Signal Processing. IEEE, 2017,64(2):70-74.

[2] 方旺盛，雷高祥，黃輝. 基于RSSI值跳數(shù)修正和跳距加權(quán)處理的DV-HOP算法[J]. 江西理工大學(xué)學(xué)報,2015,36(5):80-84.

[3] MEHRABI M, TAHERI H, TAGHDIRI P. An improved DV-Hop localization algorithm based on evolutionary algorithms[J]. Telecommunication Systems, 2017, 64(3):1-9.

[4] 劉玉珍, 王兆鋒. 基于DV-HOP改進(jìn)的無線傳感器網(wǎng)絡(luò)定位算法[J]. 計算機(jī)工程與應(yīng)用, 2016,52(4):79-83.

[5] 周林, 張厚望. 無線傳感器網(wǎng)絡(luò)中基于DV-Hop節(jié)點(diǎn)定位算法的研究[J]. 計算機(jī)應(yīng)用與軟件,2015,32(11):92-96.

[6] MENG X B, GAO X Z, LU L, et al. A new bio-inspired optimisation algorithm: Bird swarm algorithm[J]. Journal of Experimental & Theoretical Artificial Intelligence, 2015,25(2):1-5.

[7] 崔坤利, 郎朗, 陳孟元,等. 配電網(wǎng)中基于分簇定位的WSN節(jié)點(diǎn)故障定位研究[J]. 傳感技術(shù)學(xué)報, 2017,30(1):146-151.

[8] 李新春, 李蘇晨, 王曉明. 基于粒子群優(yōu)化的DV-Hop定位算法研究[J]. 測控技術(shù), 2017, 36(1):84-87.

Improved localization algorithm for wireless sensor networks based on swarm intelligence

Jin Chunjing1, Dong Xueying2

(1. School of Information Engineering,Jiangxi University of Science and Technology, Ganzhou 341000, China;2. School of Opto-electronics Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210023, China)

In this paper, the error of DV-Hop algorithm is discussed. The DV-Hop algorithm is improved and BSADV-Hop algorithm is proposed. This algorithm is divided into two parts. In the first part, the hop count method is improved. The second part is to optimize the average hop distance. In this process, a biologically inspired algorithm called bird swarm algorithm is used to minimize the error caused by the average hop distance. Simulation results show that compared with DV-Hop and PSODV-Hop, the average hop distance of nodes can be calculated more accurately, and the positioning accuracy can be improved. Moreover, the proposed algorithm shows good stability and feasibility.

WSN; DV-Hop location algorithm; BSA; the average distance per hop

TP393

A

10.19358/j.issn.1674- 7720.2017.23.018

靳春景，董雪瑩.基于群體智能改進(jìn)無線傳感器網(wǎng)絡(luò)定位算法[J].微型機(jī)與應(yīng)用，2017,36(23)：62-65.

2017-06-15)

靳春景(1990-)，通信作者，男，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡(luò)定位。 E-mail:jincj2011@163.com。

董雪瑩(1991-)，女，碩士研究生，主要研究方向：無線傳感器網(wǎng)絡(luò)。