基于跳數(shù)修正和改進粒子群優(yōu)化DV—Hop定位算法

熊歡 毛永毅

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

關鍵詞： DV?Hop定位； 錨節(jié)點； 最優(yōu)跳數(shù)； 平均跳距； 粒子群優(yōu)化； 跳數(shù)修正

中圖分類號： 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

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

1 DV?Hop算法相關理論

1.1 DV?Hop定位問題

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

熊 歡1， 毛永毅2

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

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

關鍵詞： DV?Hop定位； 錨節(jié)點； 最優(yōu)跳數(shù)； 平均跳距； 粒子群優(yōu)化； 跳數(shù)修正

中圖分類號： 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前兩步驟即通過跳數(shù)（Hops）與平均跳距（Hopsize）的乘積求解未知節(jié)點的坐標，即式（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）]的值，算法第三個步驟轉化為約束性優(yōu)化問題。函數(shù)[f（x，y）]取值最小時表示總的誤差最小，此時坐標[（x，y）]即為最優(yōu)解。

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

式中，m表示錨節(jié)點的數(shù)量。

1.2 算法定位誤差的分析

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

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

2 HPDV?Hop算法

2.1 錨節(jié)點間跳數(shù)的修正

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

[Hij=dijR] （4）

[Mij=hij-Hijhij] （5）

[λij=1-M2ij] （6）

式（7）用錨節(jié)點間的跳數(shù)調(diào)整因子來修正跳數(shù)：

[hij=λij×hij] （7）

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

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

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

[N=N4] （9）

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

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

2） [Ni=N] 表示此區(qū)域錨節(jié)點數(shù)目剛好，不需要刪除和增加。

3） [Ni

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

2.3 采用改進的粒子群算法優(yōu)化定位結果

2.3.1 粒子群算法原理

1995年，R.Eberthart博士和J.Kennedy博士經(jīng)過大量研究提出了粒子群[10]優(yōu)化（Particle Swarm Optimization，PSO）算法，其原理為：待定位區(qū)域里的每個粒子的速度和位置通過“位置+速度”不斷更新式（10）和式（11）。其中式（10）速度更新公式是與粒子初始速度（[vi]）、個體最優(yōu)值[（Pbest）]和全局最優(yōu)值[（Gbest）]有關的函數(shù)，粒子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]的均勻分布。

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

2.3.2 改進的粒子群優(yōu)化算法實現(xiàn)步驟

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

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

3） 以適用度函數(shù)為標準來更新兩個最優(yōu)值，即：

[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） 當達到迭代次數(shù)時，退出迭代。否則重新比較所有粒子的個體最優(yōu)值，釋放粒子群中和最優(yōu)解之間距離最大的粒子，然后繼續(xù)進行步驟2）。

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

3 仿真分析

3.1 仿真參數(shù)與環(huán)

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

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

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

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

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

4 結 語

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

r

參考文獻

[1] 謝濤.無線傳感器網(wǎng)絡中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] 劉少強，龐新苗，樊曉平，等.一種有效提高節(jié)點定位精度的改進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] 林金朝，陳曉冰，劉海波.基于平均跳距修正的無線傳感器網(wǎng)絡節(jié)點迭代定位算法[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] 劉鋒，張翰，楊驥.一種基于加權處理的無線傳感器網(wǎng)絡平均跳距離估計算法[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] 李新春，郭欣欣.基于最優(yōu)跳距和改進粒子群的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] 秦鵬程，顏文，解培中.基于區(qū)域劃分錨節(jié)點移動的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節(jié)點定位算法[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.