范時平，羅丹，劉艷林

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

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

范時平*，羅丹，劉艷林

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

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

無線傳感器網(wǎng)絡(luò)；Distance Vector-Hop Algorithm；改進的粒子群算法；平均每跳距離

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

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

目前，無線傳感器網(wǎng)絡(luò)定位算法［3-6］分為基于距離（Range-based）定位算法和基于距離無關(guān)（Rangefree）定位算法?；诰嚯x的定位精度相對于無需測距定位精度高但需要額外的硬件設(shè)施，成本高，不適合大規(guī)模網(wǎng)絡(luò)；無需測距定位算法，其精度相對低，但無需測距定位具有低能耗，通信開銷小、無需硬件設(shè)施支撐以及成本低等優(yōu)勢，因此無需測距定位更適合大規(guī)模網(wǎng)絡(luò)以及未來的發(fā)展。

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

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

1.1經(jīng)典DV-Hop算法介紹

1.1.1計算最小跳數(shù)

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

1.1.2平均跳距的計算

經(jīng)過第一階段后，整個網(wǎng)絡(luò)知道信標節(jié)點與信標節(jié)點和未知節(jié)點之間的最小跳數(shù)，網(wǎng)絡(luò)中信標節(jié)點的平均每跳距離按下式計算：

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

1.1.3未知節(jié)點的估計

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

網(wǎng)絡(luò)中所有未知節(jié)點到信標節(jié)點的距離采用式（2）計算。

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

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

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

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

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

圖1　兩信標節(jié)點間部分拓撲關(guān)系

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

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

2　本文的優(yōu)化算法

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

2.1改進的平均跳距

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

第1步假設(shè)網(wǎng)絡(luò)中有n個信標節(jié)點，計算所有信標節(jié)點的平均每跳距離，并記為avg，則有

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

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

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

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

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

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

②改進的信標節(jié)點i的平均每跳距離為信標節(jié)點i與其余m-1個信標節(jié)點的平均每跳距離的加權(quán)，即

2.2改進的粒子群算法

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

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

2.2.1權(quán)重的改進

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

其中A=0.5·rand（）。

圖2　權(quán)重與迭代次數(shù)圖

2.2.2改進的位置更新

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

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

2.2.3適應(yīng)度函數(shù)

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

3　本文的算法步驟

①初始化相關(guān)參數(shù)。包括：網(wǎng)絡(luò)區(qū)域大小、網(wǎng)絡(luò)中的節(jié)點數(shù)、節(jié)點跳數(shù)。

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

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

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

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

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

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

⑧若滿足終止條件，則輸出全局最優(yōu)解。否則重復(fù)執(zhí)行步驟⑤～步驟⑦。

4　實驗與仿真

4.1實驗環(huán)境和參數(shù)設(shè)置

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

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

圖3　未知節(jié)點與信標節(jié)點的分布

4.2實驗結(jié)果分析

4.2.1信標節(jié)點對定位誤差影響

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

圖4　定位誤差與信標節(jié)點關(guān)系

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

假設(shè)信標節(jié)點為20時，改變通信半徑的情況下，從圖中得到本文算法與其他3種算法相比具有更高的定位精度。如圖5所示，通信半徑在30 m以前，節(jié)點的定位誤差隨通信半徑的增加呈減小的趨勢。這是因為通信半徑越大，節(jié)點的連通度越大，計算的平均每跳距離越精確；在30 m到40 m之間呈現(xiàn)出平滑的趨勢；但當通信半徑增加到40 m后，節(jié)點的定位誤差有微小的上升趨勢。這是因為通信半徑增加到一定程度后信標節(jié)點的平均每跳距離有更大的誤差，使定位精度下降。因此，通信半徑并不是越大越好?？傊疚奶岢龅乃惴▋?yōu)于其余三種定位算法。

圖5　定位誤差與通信半徑的關(guān)系

4.2.3定位穩(wěn)定性分析

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

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

5　結(jié)束語

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

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

［2］李曉維，徐勇軍，任豐原.無線傳感器網(wǎng)絡(luò)技術(shù)［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］劉士興，黃俊杰，劉宏銀，等.基于多通信半徑的加權(quán)DV-Hop定位算法［J］.傳感技術(shù)學報，2015，28（6）：883-887.

［5］程秀芝，朱達榮，張申，等.基于RSSI差分校正的最小二乘-擬牛頓定位算法［J］.傳感技術(shù)學報，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］劉志坤，劉忠，唐小明.基于改進型粒子群優(yōu)化的節(jié)點自定位算法［J］.中南大學學報（自然科學版），2012，43（4）：1371-1376.

［10］裴祥，李巧君.基于改進粒子群優(yōu)化算法的無線傳感器網(wǎng)絡(luò)定位［J］.計算機與現(xiàn)代化，2015（7）：81-84.

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

［12］曹欲曉，嚴奎，徐金寶.一種最優(yōu)錨節(jié)點集合上的兩重粒子群優(yōu)化DV-Hop定位算法［J］.傳感技術(shù)學報，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-），男，碩士，副教授，主要研究方向為無線傳感器網(wǎng)絡(luò)、嵌入式系統(tǒng)；

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

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

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

TP393

A

1004-1699（2016）09-1410-06

項目來源：基于物聯(lián)網(wǎng)技術(shù)的呼吸、脈搏異變及跌落的實時監(jiān)測與報警的關(guān)鍵技術(shù)研究項目（61171190）

2016-03-14修改日期：2016-04-07