基于跳數修正和改進粒子群優化DV—Hop定位算法

熊歡 毛永毅

摘 要： 針對傳統 DV?Hop算法在無線傳感器網絡中節點隨機分布對定位結果造成較大誤差的問題，提出一種基于跳數修正的粒子群優化的定位算法HPDV?Hop。此算法通過對錨節點廣播的跳數進行修正，讓隨機靜態分布的錨節點移動并按密度分布二次部署以及用改進的粒子群（PSO）算法對定位中的迭代過程進行優化，實現傳統DV?Hop定位算法的全面改進，以提高定位精度。仿真結果表明，改進的算法與傳統算法相比，定位精度和算法的穩定性有明顯提高。

關鍵詞： DV?Hop定位； 錨節點； 最優跳數； 平均跳距； 粒子群優化； 跳數修正

中圖分類號： TN711?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2018）18?0076?04

DV?Hop positioning algorithm based on hop count correction and

improved particle swarm optimization

XIONG Huan1， MAO Yongyi2

（1. School of Communications and Information Engineering， Xian University of Posts and Telecommunications， Xian 710061， China；

2. School of Electronic Information Engineering， Xian University of Posts and Telecommunications， Xian 710061， China）

Abstract： In allusion to the problem that nodes in wireless sensor network are randomly distributed in the traditional DV?Hop algorithm， causing big errors of positioning results， an HPDV?Hop positioning algorithm based on hop count correction and particle swarm optimization is proposed. In this algorithm， the hop count broadcast by anchor nodes is corrected to make the static randomly?distributed anchor nodes moved and deployed a second time according to density distribution， and the iterative process during the positioning is optimized by using the improved particle swarm optimization （PSO） algorithm， so as to realize overall improvement of the traditional DV?Hop positioning algorithm， and improve positioning accuracy. The simulation results show that in comparison with the traditional algorithm， the improved algorithm has an obvious improvement in positioning accuracy and stability.

Keywords： DV?Hop positioning； anchor node； optimal hop count； average hop distance； particle swarm optimization； hop count correction

無線傳感器網絡[1]（WSN）節點定位中非測距的定位算法[2]不用測量距離，只利用各節點間相互通信實現未知節點的定位，因此備受關注。DV?Hop[3?4]算法用跳段距離代替實際距離[5]來估算未知節點與錨節點的距離。該算法節點不需具有測距功能，但是，定位精度會隨網絡拓撲結構的不規則和算法本身的缺陷而迅速下降。因此近年來已經有許多改進的DV?Hop算法，改進思路圍繞平均跳距、最小跳數的修正和算法的迭代優化[6]三方面。本文針對節點隨機分布的網絡拓撲，對算法進行改進并通過仿真對改進方案的性能進行比較和驗證。

1 DV?Hop算法相關理論

1.1 DV?Hop定位問題

DV?Hop定位算法三個步驟[7?8]中基于跳數修正和改進粒子群優化DV-Hop定位算法

熊 歡1， 毛永毅2

（1.西安郵電大學 通信與信息工程學院， 陜西 西安 710061； 2.西安郵電大學 電子信息工程學院， 陜西 西安 710061）

摘 要： 針對傳統 DV?Hop算法在無線傳感器網絡中節點隨機分布對定位結果造成較大誤差的問題，提出一種基于跳數修正的粒子群優化的定位算法HPDV?Hop。此算法通過對錨節點廣播的跳數進行修正，讓隨機靜態分布的錨節點移動并按密度分布二次部署以及用改進的粒子群（PSO）算法對定位中的迭代過程進行優化，實現傳統DV?Hop定位算法的全面改進，以提高定位精度。仿真結果表明，改進的算法與傳統算法相比，定位精度和算法的穩定性有明顯提高。

關鍵詞： DV?Hop定位； 錨節點； 最優跳數； 平均跳距； 粒子群優化； 跳數修正

中圖分類號： TN711?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2018）18?0076?04

DV?Hop positioning algorithm based on hop count correction and

improved particle swarm optimization

XIONG Huan1， MAO Yongyi2

（1. School of Communications and Information Engineering， Xian University of Posts and Telecommunications， Xian 710061， China；

2. School of Electronic Information Engineering， Xian University of Posts and Telecommunications， Xian 710061， China）

Abstract： In allusion to the problem that nodes in wireless sensor network are randomly distributed in the traditional DV?Hop algorithm， causing big errors of positioning results， an HPDV?Hop positioning algorithm based on hop count correction and particle swarm optimization is proposed. In this algorithm， the hop count broadcast by anchor nodes is corrected to make the static randomly?distributed anchor nodes moved and deployed a second time according to density distribution， and the iterative process during the positioning is optimized by using the improved particle swarm optimization （PSO） algorithm， so as to realize overall improvement of the traditional DV?Hop positioning algorithm， and improve positioning accuracy. The simulation results show that in comparison with the traditional algorithm， the improved algorithm has an obvious improvement in positioning accuracy and stability.

Keywords： DV?Hop positioning； anchor node； optimal hop count； average hop distance； particle swarm optimization； hop count correction前兩步驟即通過跳數（Hops）與平均跳距（Hopsize）的乘積求解未知節點的坐標，即式（1）。通過距離公式得到式（2）。

[di=hopsi×hopsizei] （1）

[d21-δ21≤（x-x1）2+（y-y1）2≤d21+δ21d22-δ22≤（x-x2）2+（y-y2）2≤d22+δ22 ?d2n-δ2n≤（x-xn）2+（y-yn）2≤d2n+δ2n] （2）

式中，[δ1，δ2，…，δn]為距離估計誤差。

解不等式組求解[X（x，y）]的值，算法第三個步驟轉化為約束性優化問題。函數[f（x，y）]取值最小時表示總的誤差最小，此時坐標[（x，y）]即為最優解。

[f（x，y）=i=1m（x-xi）2+（y-yi）2-di] （3）

式中，m表示錨節點的數量。

1.2 算法定位誤差的分析

1） 一跳距離引起的誤差。未知節點X，Y都在錨節點A的通信輻射半徑的圓內，DV?Hop算法在定位時，未知節點X，Y到錨節點A都認為一跳距離，實際中未知節點X，Y到錨節點的距離是有偏差的。一跳距離示意圖如圖1所示。

2） 節點靜態部署帶來的誤差。無線傳感器網絡中的節點通常是隨機靜態部署在待定位區域中的，這種隨機靜態散布在待定位區域的部署方法會導致節點分布不均勻，網絡中節點靈活性低，當網絡中錨節點較少時，這種節點部署方式將會導致定位結果誤差較大。

2 HPDV?Hop算法

2.1 錨節點間跳數的修正

針對跳數對定位結果造成誤差的問題，引入最優跳數值（[Hij]）、真實偏離值（[Mij]）和跳數調整因子（[λij]）這3個參數來改進錨節點間跳數。3個參數定義式為：

[Hij=dijR] （4）

[Mij=hij-Hijhij] （5）

[λij=1-M2ij] （6）

式（7）用錨節點間的跳數調整因子來修正跳數：

[hij=λij×hij] （7）

2.2 “錨節點移動并按密度分布”思想二次部署錨節點

可移動錨節點的移動部署方式[9]有很多種，常用的有均勻分布、按密度分布和按間隔閾值分布。本文采用按密度的方法，把目標區域均勻分為4個子區域，假設目標區域錨節點總數為[N]，第i個區域錨節點數為[Ni]，則[Ni]滿足式（8），即每個子區域平均應分配的錨節點個數為式（9）：

[N=N1+N2+N3+N4] （8）

[N=N4] （9）

式（9）的余數記為M，比較每個子區域錨節點數[Ni]與式（9）計算出的每個子區域平均應分配錨節點數[N]的大小：

1） 若[Ni>N]，表示該區域錨節點數冗余，需刪除冗余的錨節點。方法是用兩點間距離公式依次求該區域任意兩個錨節點之間的距離，結果按從小到大進行排序，依次刪除距離最小的對應錨節點，直至該區域的錨節點個數為[N]結束。

2） [Ni=N] 表示此區域錨節點數目剛好，不需要刪除和增加。

3） [Ni

4） 當M[≠]0時，把M個錨節分配到隨機生成的M個對應位置。

2.3 采用改進的粒子群算法優化定位結果

2.3.1 粒子群算法原理

1995年，R.Eberthart博士和J.Kennedy博士經過大量研究提出了粒子群[10]優化（Particle Swarm Optimization，PSO）算法，其原理為：待定位區域里的每個粒子的速度和位置通過“位置+速度”不斷更新式（10）和式（11）。其中式（10）速度更新公式是與粒子初始速度（[vi]）、個體最優值[（Pbest）]和全局最優值[（Gbest）]有關的函數，粒子i運動的速度是這三個影響速度的和速度。[vit+1=w?vit+c1?r1Pbesti-xit+ c2?r2Gbest-xit] （10）

[xi（t+1）=xi（t）+vi（t+1）] （11）

式中：[w]為慣性權重；[c1]，[c2]為學習因子；[r1]，[r2]服從[0，1]的均勻分布。

用粒子群算法優化定位結果的過程如圖2所示，最優位置為P點，各粒子均按照“位置+速度”模型來更新位置和速度，不斷地靠近P，第i個粒子受到3個因素的共同影響不斷地搜索迭代向最優點P移動。

2.3.2 改進的粒子群優化算法實現步驟

1） 初始化粒子群，包括兩個最優值設初值，設初始速度。其中未知節點初值設置為全局最優解。

2） 利用式（12）計算每個粒子的適應度[11]。[fitnessi=1mj=1m（xi-xj）2+（yi-yj）2-dj] （12）

3） 以適用度函數為標準來更新兩個最優值，即：

[Pbestt+1=Xt+1， fitness（Xt+1）≤fitness（Pbest）Pbestt，fitness（Xt+1）>fitness（Pbest）] （13）

[Gbestt+1=Pbestt+1，fitness（Pbestt+1）≤fitness（Gbestt）Gbestt， fitness（Pbestt+1）>fitness（Gbestt）] （14）

4） 更新粒子位置和速度。

5） 當達到迭代次數時，退出迭代。否則重新比較所有粒子的個體最優值，釋放粒子群中和最優解之間距離最大的粒子，然后繼續進行步驟2）。

HPDV?Hop算法流程圖如圖3所示。

3 仿真分析

3.1 仿真參數與環

本文用歸一化的平均定位誤差[12]作為算法精度的衡量標準，計算式為：

[error=1NRKk=1Ki=1N（xi-xki）2+（yi-yki）2 ] （15）

1） 不同未知節點數量的情況。如圖4所示，通信半徑[R=]25 m，取總節點數的10%為錨節點數，圖中橫坐標節點總數在[100，350]區間變化時，3種算法的歸一化平均定位誤差都呈下降趨勢，節點數量大于200后，仿真曲線趨于平穩狀態，當橫坐標相同時，HPDV?Hop 算法定位誤差始終最小，且較這兩種算法分別平均減小16.69%和13.24%。

2） 不同通信半徑的情況。總節點數[M=]100，錨節點數[N=]20，通信半徑[R]分別取 15 m，20 m，25 m，30 m，35 m，40 m時，對半徑歸一化的平均定位誤差的結果如圖5所示。3種算法對半徑的歸一化的平均定位誤差都與通信半徑成反比，在通信半徑相同時，HPDV?Hop算法的歸一化平均定位誤差最小，而且相比其他兩種算法的定位算法分別平均減小16.31%和10.53%。

3） 不同錨節點數量。當[M]=100，[R=]25 m時，錨節點數[N]分別取為5，10，15，20，25，30，35，40時，3種算法的歸一化平均定位誤差隨錨節點數變化關系如圖6所示。由圖6曲線可知，在[N≥15]時，定位誤差變化較小曲線波動不大。

4 結 語

本文為了提高定位的準確率和定位精度提出了HPDV?Hop算法。通過定義3個參數修正了跳數，而且移動使有規則分布的錨節點增大了算法的靈活性。從仿真結果可以看出，本文算法明顯降低了無線傳感器網絡的定位誤差，使得定位算法的精度和穩定性都有所提高。因此對于節點隨機分布的無線傳感器網絡來說，該算法是一種更好的定位方案。

r

參考文獻

[1] 謝濤.無線傳感器網絡中DV?Hop算法的改進[D].重慶：西南大學，2012.

XIE Tao. Improved DV?Hop algorithm for wireless sensor network [D]. Chongqing： Southwest University， 2012.

[2] DELIN K A， JACKSON S P. Sensor web： a new instrument concept [C]// Proceedings of the SPIE. San Jose： SPIE， 2001： 1?9.

[3] 王新生，趙衍靜，李海濤.基于DV?Hop定位算法的改進研究[J].計算機科學，2011，38（2）：76?78.

WANG Xinsheng， ZHAO Yanjing， LI Haitao. Improved study based on DV?Hop localization algorithm [J]. Computer science， 2011， 38（2）： 76?78.

[4] 劉少強，龐新苗，樊曉平，等.一種有效提高節點定位精度的改進DV?Hop算法[J].傳感技術學報，2010，23（8）：1179?1183.

LIU Shaoqiang， PANG Xinmiao， FAN Xiaoping， et al. Improved DV?Hop algorithm for higher positioning accuracy [J]. Chinese journal of sensors and actuators， 2010， 23（8）： 1179?1183.

[5] GUO F， HU Y， XIU L， et al. A hierarchical P2P model and a data fusion method for network security situation awareness system [J]. Wuhan University journal of natural sciences， 2016， 21（2）： 126?132.

[6] KENNEDY J， EBERHART R C. Particle swarm optimization [C]// Proceedings of IEEE International Conference on Neural Networks. Perth： IEEE， 1995： 1942?1948.

[7] 涂巧玲，宋佳，胡濤.一種加權的DV?Hop定位改進算法[J].通信技術，2013，46（9）：58?60.

TU Qiaoling， SONG Jia， HU Tao. A weighted improved DV?Hop localization algorithm [J]. Communications technology， 2013， 46（9）： 58?60.

[8] 林金朝，陳曉冰，劉海波.基于平均跳距修正的無線傳感器網絡節點迭代定位算法[J].通信學報，2009，30（10）：107?113.

LIN Jinchao， CHEN Xiaobing， LIU Haibo. Iterative algorithm for locating nodes in WSN based on modifying average hopping distances [J]. Journal on communications， 2009， 30（10）： 107?113.

[9] 劉鋒，張翰，楊驥.一種基于加權處理的無線傳感器網絡平均跳距離估計算法[J].電子與信息學報，2008，30（5）：1222?1225.

LIU Feng， ZHANG Han， YANG Ji. An average one?hop distance estimation algorithm based on weighted disposal in wireless sensor network [J]. Journal of electronics & information technology， 2008， 30（5）： 1222?1225.

[10] 李新春，郭欣欣.基于最優跳距和改進粒子群的DV?Hop定位算法[J].計算機應用研究，2017，34（12）：3775?3778.

LI Xinchun， GUO Xinxin. DV?Hop localization algorithm based on best average hop distances and improved particle swarm [J]. Application research of computers， 2017， 34（12）： 3775?3778.

[11] 秦鵬程，顏文，解培中.基于區域劃分錨節點移動的DV?Hop定位算法：CN105848283A[P].2016?08?10.

QIN Pengcheng， YAN Wen， XIE Peizhong. DV?Hop （distance vector?hop） positioning method based on region partition anchor node movement： CN105848283A [P]. 2016?08?10.

[12] YANG X S， DEB S. Cuckoo search via lévy flights [C]// Proceedings of World Congress on Nature & Biologically Inspired Computing. Coimbatore： IEEE， 2010： 210?214.

[13] 王玉芳，毛永毅.一種基于改進布谷鳥算法的WSN節點定位算法[J].計算機應用研究，2017，34（11）：3412?3415.

WANG Yufang， MAO Yongyi. WSN node localization based on improved cuckoo search algorithm [J]. Application research of computers， 2017， 34（11）： 3412?3415.