基于跳距與改進粒子群算法的DV-Hop定位算法*

2016-10-21 11:32:06范時平羅丹劉艷林

傳感技術學報 2016年9期

范時平，羅丹，劉艷林

（重慶郵電大學通信與信息工程學院，重慶400065）

范時平*，羅丹，劉艷林

（重慶郵電大學通信與信息工程學院，重慶400065）

針對DV-Hop定位算法定位精度不高的問題，提出一種帶改進的權重平均每跳距離與改進的粒子群算法以改進經典DV-Hop算法。一方面，提出跳距誤差與估計距離誤差的加權平均值，修正原始的平均每跳距離。另一方面，采用分段的指數、對數遞減權重改進粒子群的權重；同時，結合人工魚群位置更新的優點來改進粒子群算法的位置更新。用改進的粒子群算法求解未知節點坐標，以提高定位精度。實驗仿真表明，該算法的定位精度和穩定性與其他算法相比有明顯的改善。

無線傳感器網絡；Distance Vector-Hop Algorithm；改進的粒子群算法；平均每跳距離

EEACC：7230doi：10.3969/j.issn.1004-1699.2016.09.020

無線傳感器網絡是由大量廉價、小體積、能量及通信能力有限的無線傳感器節點以自組織方式組成的網絡，已被廣泛應用于國家防衛、環境監測、目標跟蹤定位、生產安全等領域［1］。節點定位技術是無線傳感器網絡應用的基礎和關鍵技術之一，具體體現在無線傳感器網絡主要工作是在指定區域執行各種監測任務，位置信息對傳感器網絡的監測至關重要，事件發生位置或者獲取信息節點位置是傳感器節點監測消息中包含的重要信息，位置信息的準確性直接影響傳感器節點采集數據的有效性［2］。因此，只獲取節點監測的數據而不知該節點的位置信息是毫無意義。

目前，無線傳感器網絡定位算法［3-6］分為基于距離（Range-based）定位算法和基于距離無關（Rangefree）定位算法。基于距離的定位精度相對于無需測距定位精度高但需要額外的硬件設施，成本高，不適合大規模網絡；無需測距定位算法，其精度相對低，但無需測距定位具有低能耗，通信開銷小、無需硬件設施支撐以及成本低等優勢，因此無需測距定位更適合大規模網絡以及未來的發展。

DV-Hop定位算法目前仍然處于研究階段，現已有大量文獻對其進行研究。文獻［7］提出采用加權思想計算未知節點的平均每跳距離，能夠提高DV-Hop定位算法的精度；文獻［8］采用網絡中信標節點的最小與最大的平均每跳距離作為所有未知節點的平均每跳距離，實驗結果表明能提高精度。其次，由于最小二乘求解未知節點坐標存在誤差，文獻［9-11］提出在DV-Hop算法的未知節點求解坐標階段利用改進的粒子群算法代替傳統的最小二乘法估計未知節點坐標；文獻［12］提出首先采用離散粒子群算法選出一組最優的信標節點，然后再采用粒子群算法求解未知節點坐標，雖然采用此方法能提高精度，但是網絡節點密度過大。在上述文獻中，它們都是分別從第二階段和第三階段改進DV-Hop算法，而文獻［13］中指出DV-Hop定位算法中的信標節點的平均每跳距離具有較大的誤差，而定位需要依賴于平均每跳距離。針對現有的不足，本文將從兩方面進行研究，首先對平均跳段距離優化，其次采用改進的粒子群算法求解未知節點的坐標。

1　DV-Hop定位算法及其誤差分析

1.1經典DV-Hop算法介紹

1.1.1計算最小跳數

信標節點向其他節點廣播初始化跳數為0以及其他信息（位置信息），其他節點記錄同一信標節點最小跳數信息并將跳數加一后轉發給其他節點，最后求得每個信標節點到未知節點的最小跳數。

1.1.2平均跳距的計算

經過第一階段后，整個網絡知道信標節點與信標節點和未知節點之間的最小跳數，網絡中信標節點的平均每跳距離按下式計算：

其中，n為信標節點的個數，（xi，yi）、（xj，yj）分別為信標節點i、j的坐標，hopij為信標節i、j之間的跳數。

1.1.3未知節點的估計

假設未知節點k的坐標為（xk，yk）和信標節點i的坐標為（xi，yi），未知節點k到信標節點i間的距離采用式（2）計算

網絡中所有未知節點到信標節點的距離采用式（2）計算。

傳統的DV-Hop定位算法利用最小二乘法估計未知節點坐標，如下式：

上式利用前n-1項分別減去第n項可轉化最小平方差估計未知節點坐標

1.2DV-Hop定位算法誤差分析

影響無線傳感器網絡定位精度較低的原因很多，但主要原因有節點非均勻分布、DV-Hop定位算法自身因素。本文分別從以下幾個方面進行分析：

（1）無線傳感器網絡中的節點一般由飛機拋灑節點，網絡中的節點通常呈非均勻分布。因此，網絡中平均每跳距離有較大的差異。其次，傳統的DV-Hop算法利用信標節點間的直線距離和跳數計算平均跳距，但信標節點間的最小跳數經過的距離是折線。如圖1所示：假設節點通信半徑為15 m，信標節點A、B之間真實距離為22 m而在DV-Hop算法中平均每跳距離利用式（1）計算，計算得到的平均每跳距離約為7.33 m，但實際平均每跳距離約為9.33 m，所以傳統的DV-Hop算法計算的平均每跳距離會產生很大的誤差。

圖1　兩信標節點間部分拓撲關系

（2）傳統的DV-Hop算法直接利用第二階段計算的平均跳距作為未知節點到信標節點的每跳距離，這樣計算的未知節點到信標節點的距離會產生極大誤差，若不對第二階段的平均每跳距離誤差處理必會對后面的計算產生影響；同時，由于最小二乘法本身存在計算誤差，未知節點的估計位置會受累計誤差的影響，導致傳統DV-Hop定位精度不高。

針對上述存在的問題提出改進，首先利用加權的思想改進平均每跳距離。其次，最小二乘法計算本身存在誤差以及無效信標的存在，在估計未知節點坐標時利用改進的粒子群算法代替最小二乘求解未知節點坐標。

2　本文的優化算法

本文對信標節點的平均每跳距離和粒子群算法進行優化，因此，分別從這兩方面提出改進。

2.1改進的平均跳距

DV-Hop的主要誤差是由平均每跳距離引起，本文引入平均每跳距離均方加權誤差的思想對信標節點平均每跳距離進行優化。具體步驟如下：

第1步假設網絡中有n個信標節點，計算所有信標節點的平均每跳距離，并記為avg，則有

第2步利用信標節點i的平均每跳距離與所有信標節點的平均每跳距離之差計算誤差Di1，如下式：

第3步由于節點間的估計距離利用式（2）計算得到，容易產生累積誤差。因此，節點間的估計距離也是評判信標節點平均每跳距離是否精確的另一標準。利用信標節點i、j間的實際距離與其估計距離間的平均每跳距離誤差Di2下式計算：

其中，dij為信標節點的實際距離，d?ij=avghopsizei· hopij為信標節點i、j的估計距離。

第4步綜合考慮信標節點i的平均每跳距離誤差，得到自身平均每跳距離誤差系數，并把此誤差系數作為其余信標節點計算平均每跳距離的權值，權值計算表達式為：

第5步重新估算信標節點i的平均每跳距離avginew，由于均方誤差差越小，則真實度越高，相應的權值越大。本文提出采用帶加權值方法優化信標節點i的平均每跳距離。計算信標節點i的平均每跳距離方案如下：

①信標節點i、j兩節點間的平均每跳距離為avghopsizeij即：

②改進的信標節點i的平均每跳距離為信標節點i與其余m-1個信標節點的平均每跳距離的加權，即

2.2改進的粒子群算法

粒子群優化算法是由Eberhart和Kennedy博士提出的新型智能算法。粒子群優化算法與其他智能算法相比，它具有簡單，易實現以及較強的優化能力。粒子群算法的數學描述如下：假設種群數為N，每個粒子i包括一個D維坐標和速度向量Xi=（xi1，xi2，…，xiD），Vi=（vi1，vi2，…，viD）；ω為慣性權重，粒子i的歷史最優位置pbesti=（pbesti1，pbesti2，…，pbestiD），全局歷史最優位置gbesti=（gbesi1，gbesi2，…，gbesiD）；c1、c2加速因子（一般取2），r1、r2為在［0，1］上服從均勻分布的隨機數，r為約束因子，速度和位置更新如下式：

雖然粒子群優化算法具有較強的全局搜索能力，且初期收斂較快，但在后期由于粒子的速度減小慢，導致位置變化慢，所以粒子群容易陷入早熟和收斂慢等問題，這樣粒子就難以跳出局部最優解。針對此問題分別優化粒子群的慣性權重和變異步長，以給后期搜索時提供多樣化的解空間。

2.2.1權重的改進

慣性權值會影響粒子的全局搜索能力與局部搜索能力之間的平衡，即使用較大的慣性權值，算法具有較強的全局搜索能力，較小的權值有利于局部搜索能力和加速算法的收斂。根據上述思想，本文提出采用指數遞減與隨機對數遞減分段的慣性權值。這樣做的好處在于，搜索初期具有較大的權重可以得到較大的解空間，采用此方法可以使得到的粒子具有多樣性；在搜索中后期，利用隨機對數遞減慣性權值不僅有利于加快算法收斂速度，而且更有利于增大局部解的多樣性，在一定程度上使粒子跳出局部解，從而提高粒子群算法的效率和精度。k為當前迭代次數，K為總的迭代次數，設ωmax=0.9，ωmin=0.4，如圖2所示，k小于60時，采用遞減的指數權重；k大于60時，采用隨機對數遞減權重。

其中A=0.5·rand（）。

圖2　權重與迭代次數圖

2.2.2改進的位置更新

在后期為了使算法更快速有效達到收斂，跳出局部解。人工魚群算法中魚群覓食、聚群、追尾階段等行為中的位置更新具有較大的隨機性［14］，因此可以增加解的多樣性，并跳出局部解等優點。因此，本文采用人工魚群的位置更新進行改進粒子群的位置更新。改進粒子的位置更新采用下式計算：

其中r′=1+0.3·rand（）

2.2.3適應度函數

其中M大于等于3，為未知節點選用信標節點的數目；Xi為信標節點的坐標；X0選用粒子群算法中的全局最優解；di為未知節點與信標節點i計算的距離。

3　本文的算法步驟

①初始化相關參數。包括：網絡區域大小、網絡中的節點數、節點跳數。

②利用DV-Hop算法的第一、二階段獲得每個信標節點與未知節點的最小跳數和信標節點i的平均每跳距離。

③利用改進的平均每跳距離的方法重新計算信標節點的平均每跳距離，即根據式（5）～式（10）計算avginew，代替原始的平均每跳距離avghopsizei。

④初始化種群。初始化粒子i的位置Xi=（xi1，xi2，…，xiD）與速度Vi=（vi1，vi2，…，viD），自身歷史最優位置pbesti=Xi，根據式（15），計算種群的適應度函數值，全局最優gbesti為初始種群的最有位置，并初始化k=0。

⑤令k=k+1。根據式（11）～式（14）更新粒子的速度和位置。

⑥比較當前位置與粒子歷史最優位置的適應度值的大小。若當前位置粒子的適應度值比粒子歷史最優位置適應度值，則更新粒子歷史最優位置；否則，保持粒子歷史最優位置。

⑦比較粒子歷史最優位置與全局最優位置的適應度值的大小。若粒子歷史最優位置的適應度值比全局最優位置的適應度值大，則更新粒子的全局最優位置；否則，保持粒子的全局最優位置。

⑧若滿足終止條件，則輸出全局最優解。否則重復執行步驟⑤～步驟⑦。

4　實驗與仿真

4.1實驗環境和參數設置

在Windows7的MATLAB2010平臺下進行仿真模擬實驗。將100個傳感器節點，隨機部署在100 m×100 m的網絡中，未知節點和信標節點分布如圖3所示。假設所有傳感器網絡節點具有相同的通信半徑R。為了證明本文算法BDV-Hop更具有優越性，選擇經典DV-Hop定位算法、文獻［8］中的IDV-Hop以及文獻［10］中的IPSO-DVHop算法進行實驗對比，粒子種群數最大為30，最大迭代次數100，粒子最大速度為4 m/s。每個未知節點的定位誤差公式

其中（xai，yai）是未知節點的真實坐標，（xi，yi）是未知節點的估計坐標，全網的定位性能估計采用歸一化的相對誤差公式計算，n為未知節點的個數，

圖3　未知節點與信標節點的分布

4.2實驗結果分析

4.2.1信標節點對定位誤差影響

假設通信半徑為30 m時，改變信標節點數目對定位性能進行仿真。本文算法與經典DV-Hop定位算法、IDV-Hop以及IPSO-DVHop進行對比，相應得到平均定位誤差與信標節點數關系如圖4所示。從圖中得到定位誤差隨信標節點數目增加而減小，這是由于信標節點增加不但提高了跳距估計的準確性，而且降低了未知節點與信標節點之間因跳數過多而帶來的積累誤差。當信標節點數小于20時，定位誤差受信標節點數目影響較大，信標數目大于20時，定位誤差受信標數目影響較小，有趨于平穩狀態。本文采用的算法分別比DV-Hop、IDV-Hop以及IPSO-DVHop的定位精度大約提高13.4%、8.2%、5.3%，且它的平均定位誤差曲線更平滑，表明其穩定性更好。

圖4　定位誤差與信標節點關系

4.2.2通信半徑對定位誤差影響

假設信標節點為20時，改變通信半徑的情況下，從圖中得到本文算法與其他3種算法相比具有更高的定位精度。如圖5所示，通信半徑在30 m以前，節點的定位誤差隨通信半徑的增加呈減小的趨勢。這是因為通信半徑越大，節點的連通度越大，計算的平均每跳距離越精確；在30 m到40 m之間呈現出平滑的趨勢；但當通信半徑增加到40 m后，節點的定位誤差有微小的上升趨勢。這是因為通信半徑增加到一定程度后信標節點的平均每跳距離有更大的誤差，使定位精度下降。因此，通信半徑并不是越大越好。總之，本文提出的算法優于其余三種定位算法。

圖5　定位誤差與通信半徑的關系

4.2.3定位穩定性分析

在網絡區域為100 m×100 m的區域內，部署100個傳感器節點，其中信標節點為20個，并固定通信半徑為30 m。分別對經典DV-Hop定位算法、IDV-Hop、IPSO-DVHop以及本文算法進行20次仿真，得到平均歸一化誤差。從中得出本文采用的改進方法比其余3種算法的平均歸一化誤差與方差都要小，其穩定性更好。

表1　定位算法的平均歸一化誤差與方差

5　結束語

本文通過介紹傳統DV-Hop算法，并分析其主要誤差來源，針對此誤差提出采用平均每跳距離誤差加權方法修正信標節點的平均每跳距離，并結合改進的粒子群算法求解未知節點坐標，以綜合提高定位精度，通過MATLAB仿真實驗，并得出實驗結果。實驗結果表明，在固定通信半徑，改變信標節點數目的情況下，定位誤差隨信標節點數目增大而減小且本文的算法優于其他三種算法；在通信半徑可變的情況，也得出了相應的結論。由此可知，本文的算法能提高定位精度。但是，采用粒子群算法增加了計算復雜，使網絡計算開銷增大。因此，高精度低復雜度的算法待進一步研究。

［1］彭宇，王丹.無線傳感器網絡定位技術綜述［J］.電子測量與儀器學報，2011，25（5）：389-399.

［2］李曉維，徐勇軍，任豐原.無線傳感器網絡技術［M］.北京：北京理工大學，2007：191-194.

［3］Rudafshani M，Datta S.Localization in Wireless Sensor Networks［C］//Information Processing in Sensor Networks，2007.IPSN 2007.6th International Symposium on.IEEE，2007：51-60.

［4］劉士興，黃俊杰，劉宏銀，等.基于多通信半徑的加權DV-Hop定位算法［J］.傳感技術學報，2015，28（6）：883-887.

［5］程秀芝，朱達榮，張申，等.基于RSSI差分校正的最小二乘-擬牛頓定位算法［J］.傳感技術學報，2014，27（1）：123-127.

［6］Han G，Xu H，Duong T Q，et al.Localization Algorithms of Wire?less Sensor Networks：A Survey［J］.Telecommunication Systems，2013，52（4）：2419-2436.

［7］Fu C，Qian Z，Ji G，et al.An Improved DV-Hop Localization Algo?rithm in Wireless Sensor Network［C］//Information Technology and Applications（ITA），2013 International Conference on.IEEE，2013：13-16.

［8］Hadir A，Zine-Dine K，Bakhouya M，et al.An Improved DV-Hop Localization Algorithm for Wireless Sensor Networks［C］//Next Generation Networks and Services（NGNS），2014 Fifth Interna?tional Conference on.IEEE，2014：330-334.

［9］劉志坤，劉忠，唐小明.基于改進型粒子群優化的節點自定位算法［J］.中南大學學報（自然科學版），2012，43（4）：1371-1376.

［10］裴祥，李巧君.基于改進粒子群優化算法的無線傳感器網絡定位［J］.計算機與現代化，2015（7）：81-84.

［11］王亞子，楊建輝.改進粒子群算法的無線傳感器網絡節點定位［J］.計算機工程與應用，2014，50（18）：99-102.

［12］曹欲曉，嚴奎，徐金寶.一種最優錨節點集合上的兩重粒子群優化DV-Hop定位算法［J］.傳感技術學報，2015，28（3）：424-429.

［13］Zine-Dine K，Hadir A，Madani A，et al.Comparative Study of Lo?calization Algorithms Performance in Wireless Sensors Network［J］.International Journal of Research in Engineering&Ad?vanced Technology，2014：1-9.

［14］Neshat M，Sepidnam G，Sargolzaei M，et al.Artificial Fish Swarm Algorithm：A Survey of the State-of-the-Art，Hybridization，Combi?natorial and Indicative Applications［J］.Artificial Intelligence Re?view，2014，42（4）：965-997.

范時平（1970-），男，碩士，副教授，主要研究方向為無線傳感器網絡、嵌入式系統；

羅丹（1991-），女，碩士研究生，主要研究方向為無線傳感器網絡，1097342405@qq.com；

劉艷林（1990-），女，碩士，碩士研究生，主要研究方向為大數據。

DV-Hop Localization Algorithm Based on Hop-Size and Improvement Particle Swarm Optimization*

FAN Shiping*，LUO Dan，LIU Yanlin
（College of Communication and Information Engineering，Chongqing University of Posts and Telecommunication，Chongqing 400065，China）

In order to solve DV-Hop low localization accuracy，a novel localization method based on modified weighted average hop-size and improved particle swarm optimization algorithm is proposed.On the one hand，weighted average both hop-size error and estimated distance error modify initial average hop-size.On the other hand，index and logarithmic decrement of piecewise function improve inertia weight of PSO.Furthermore，combin?ing with localization update of Atificial Fish Swarm Algorithm improve PSO’s localization update.Then，improved algorithm estimate unknown node coordination.The experiment shows localization accuracy and stability of the method is greatly improved.

wireless sensors networks（WSN）；DV-Hop Algorithm；improved particle swarm optimization algorithm（PSO）average hop-size