熊歡 毛永毅

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

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

中圖分類(lèi)號(hào)： TN711?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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ú)線(xiàn)傳感器網(wǎng)絡(luò)[1]（WSN）節(jié)點(diǎn)定位中非測(cè)距的定位算法[2]不用測(cè)量距離，只利用各節(jié)點(diǎn)間相互通信實(shí)現(xiàn)未知節(jié)點(diǎn)的定位，因此備受關(guān)注。DV?Hop[3?4]算法用跳段距離代替實(shí)際距離[5]來(lái)估算未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離。該算法節(jié)點(diǎn)不需具有測(cè)距功能，但是，定位精度會(huì)隨網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的不規(guī)則和算法本身的缺陷而迅速下降。因此近年來(lái)已經(jīng)有許多改進(jìn)的DV?Hop算法，改進(jìn)思路圍繞平均跳距、最小跳數(shù)的修正和算法的迭代優(yōu)化[6]三方面。本文針對(duì)節(jié)點(diǎn)隨機(jī)分布的網(wǎng)絡(luò)拓?fù)洌瑢?duì)算法進(jìn)行改進(jìn)并通過(guò)仿真對(duì)改進(jìn)方案的性能進(jìn)行比較和驗(yàn)證。

1 DV?Hop算法相關(guān)理論

1.1 DV?Hop定位問(wèn)題

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

熊 歡1， 毛永毅2

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

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

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

中圖分類(lèi)號(hào)： TN711?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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前兩步驟即通過(guò)跳數(shù)（Hops）與平均跳距（Hopsize）的乘積求解未知節(jié)點(diǎn)的坐標(biāo)，即式（1）。通過(guò)距離公式得到式（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]為距離估計(jì)誤差。

解不等式組求解[X（x，y）]的值，算法第三個(gè)步驟轉(zhuǎn)化為約束性?xún)?yōu)化問(wèn)題。函數(shù)[f（x，y）]取值最小時(shí)表示總的誤差最小，此時(shí)坐標(biāo)[（x，y）]即為最優(yōu)解。

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

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

1.2 算法定位誤差的分析

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

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

2 HPDV?Hop算法

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

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

[Hij=dijR] （4）

[Mij=hij-Hijhij] （5）

[λij=1-M2ij] （6）

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

[hij=λij×hij] （7）

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

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

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

[N=N4] （9）

式（9）的余數(shù)記為M，比較每個(gè)子區(qū)域錨節(jié)點(diǎn)數(shù)[Ni]與式（9）計(jì)算出的每個(gè)子區(qū)域平均應(yīng)分配錨節(jié)點(diǎn)數(shù)[N]的大?。?/p>

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

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

3） [Ni

4） 當(dāng)M[≠]0時(shí)，把M個(gè)錨節(jié)分配到隨機(jī)生成的M個(gè)對(duì)應(yīng)位置。

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

2.3.1 粒子群算法原理

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

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

式中：[w]為慣性權(quán)重；[c1]，[c2]為學(xué)習(xí)因子；[r1]，[r2]服從[0，1]的均勻分布。

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

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

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

2） 利用式（12）計(jì)算每個(gè)粒子的適應(yīng)度[11]。[fitnessi=1mj=1m（xi-xj）2+（yi-yj）2-dj] （12）

3） 以適用度函數(shù)為標(biāo)準(zhǔn)來(lái)更新兩個(gè)最優(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） 當(dāng)達(dá)到迭代次數(shù)時(shí)，退出迭代。否則重新比較所有粒子的個(gè)體最優(yōu)值，釋放粒子群中和最優(yōu)解之間距離最大的粒子，然后繼續(xù)進(jìn)行步驟2）。

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

3 仿真分析

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

本文用歸一化的平均定位誤差[12]作為算法精度的衡量標(biāo)準(zhǔn)，計(jì)算式為：

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

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

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

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

4 結(jié) 語(yǔ)

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

r

參考文獻(xiàn)

[1] 謝濤.無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中DV?Hop算法的改進(jìn)[D].重慶：西南大學(xué)，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ìn)研究[J].計(jì)算機(jī)科學(xué)，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] 劉少?gòu)?qiáng)，龐新苗，樊曉平，等.一種有效提高節(jié)點(diǎn)定位精度的改進(jìn)DV?Hop算法[J].傳感技術(shù)學(xué)報(bào)，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] 涂巧玲，宋佳，胡濤.一種加權(quán)的DV?Hop定位改進(jìn)算法[J].通信技術(shù)，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ú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)迭代定位算法[J].通信學(xué)報(bào)，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] 劉鋒，張翰，楊驥.一種基于加權(quán)處理的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)平均跳距離估計(jì)算法[J].電子與信息學(xué)報(bào)，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)跳距和改進(jìn)粒子群的DV?Hop定位算法[J].計(jì)算機(jī)應(yīng)用研究，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é)點(diǎn)移動(dòng)的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] 王玉芳，毛永毅.一種基于改進(jìn)布谷鳥(niǎo)算法的WSN節(jié)點(diǎn)定位算法[J].計(jì)算機(jī)應(yīng)用研究，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.