基于群體智能改進無線傳感器網絡定位算法

靳春景，董雪瑩

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

基于群體智能改進無線傳感器網絡定位算法

靳春景1，董雪瑩2

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

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

無線傳感器網絡；DV-Hop定位算法；鳥群算法；平均每跳距

0 引言

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

1 DV-Hop算法的誤差源頭

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

(1)無線傳感器網絡中節點最小跳數計算。

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

(1)

其中，信標節點k的位置用(xk,yk)表示，第l個信標節點的位置用(xl,yl)表示。hopkl為信標節點k與信標節點l之間的跳數。

待定位節點m接收離自己最近信標節點的平均跳距，并利用步驟(1)得到的距錨節點的跳數來計算距信標節點的長度：

Dmn=hopsize×hopmn

(2)

其中，Dmn是待定位節點m離自身最近信標節點n的距離，hopsize是平均每跳距離的大小，它表示待定位節點m與最靠近它信標節點n平均每跳距離的大小。hopmn為待定節點m到信標節點n的跳數。

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

經典的DV-Hop算法比較容易實現節點位置的計算，并且花費成本相對比較少，但定位精度就差強人意了。這主要是由平均每跳距離有誤差造成的。

圖1 跳數誤差來源示意圖

DV-Hop算法中的跳數求解中，經常把在一跳范圍內的節點都當做一跳。A節點與B節點都在一跳范圍里，所以P節點把到節點A和到節點B的距離都記成一跳。但從圖1中，這一跳的距離明顯不等，故是誤差的源頭。

圖2 節點距離誤差示意圖

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

2 DV-Hop算法的改進

2.1 線性糾正跳數

本節利用電磁場與電磁波理論中一個常見的理論，即信號的強度與信號傳播距離成負相關的理論。在無線傳感器中加入一個功能模塊，利用這個模塊計算接收的信號強度。用設定線性的閾值對節點接收的跳數問題進行糾正。具體步驟如下：

(1)設定閾值為S0。

(2)設節點i到節點j的跳數為hopij，節點i接收到節點j的信號強度用Sij表示。

圖3 跳數糾正示意圖

2.2 鳥群算法的DV-Hop

2.2.1鳥群算法簡介

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

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

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

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

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

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

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

(3)

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

(4)

(5)

N2=a2×

(6)

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

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

(7)

(8)

式(7)、(8)中rand(0,1)是服從標準正態分布中的隨機數；FP為乞食者隨機選擇跟在一個生產者身后祈求食物事件發生的概率，FP的值為小于1的正數。

本文構建的數學模型采用最小均方誤差準則，并且考慮到經典的DV-Hop算法利用最小二乘法計算出來的位置坐標不可避免存在誤差，因此利用鳥群算法進行求解。

假定已知節點的實際坐標信息。錨節點n與未知節點m之間的距離可用下式計算：

(9)

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

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

(10)

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

2.2.2BSADV-Hop算法流程

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

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

(2)設置公示板。公示板值的大小設置為 besty。公示板作用是當每次進行迭代時，記載每次的適應度函數的最優值，并廣播線性糾正后的跳數。

(3)迭代尋優。利用BSADV-Hop算法進行節點定位，每次迭代定位過程中利用式(10)得到適應度函數G(x,y)的最優值。

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

(5)判斷是否滿足終止條件。如果滿足終止條件就輸出最優解和待定節點的坐標。反之進行迭代次數增1的操作并且回到步驟(3)繼續對種群進行優化和迭代計算。

3 算法仿真

本文仿真工具為MATLAB2012a。假設在邊長為100 m的正方形區域隨機將傳感器節點進行拋撒。

本文對節點的定位精度的性能使用平均定位誤差Erroravg來評判。Erroravg表示待定位的未知節點的自身真實位置與經BSADV-Hop算法后坐標之間的差值。

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

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

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

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

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

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

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

圖6 不同信標節點數量與定位誤差的關系

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

圖7 不同節點總數量的誤差率比較

4 結論

本文對經典的DV-Hop算法的不完善之處進行了分析討論，對其缺點進行改進和完善，提出了BSADV-Hop算法。在求優化模型時，采用鳥群算法進行求解，并利用BSADV-Hop算法代替最小二乘法，降低計算誤差。通過實驗驗證，本文的BSADV-Hop算法比 PSODV-Hop算法在最優解搜索能力上表現得更好。在不同的實驗條件和不同的變量條件下，分析了BSADV-Hop算法、PSODV-Hop算法和經典的DV-Hop算法的定位精度和定位的開銷，得出本文提出的BSADV-Hop算法優于PSODV-Hop算法和經典的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值跳數修正和跳距加權處理的DV-HOP算法[J]. 江西理工大學學報,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]. 計算機工程與應用, 2016,52(4):79-83.

[5] 周林, 張厚望. 無線傳感器網絡中基于DV-Hop節點定位算法的研究[J]. 計算機應用與軟件,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] 崔坤利, 郎朗, 陳孟元,等. 配電網中基于分簇定位的WSN節點故障定位研究[J]. 傳感技術學報, 2017,30(1):146-151.

[8] 李新春, 李蘇晨, 王曉明. 基于粒子群優化的DV-Hop定位算法研究[J]. 測控技術, 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].微型機與應用，2017,36(23)：62-65.

2017-06-15)

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

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