基于跳距與改進(jìn)粒子群算法的DV-Hop定位算法*

范時(shí)平，羅丹，劉艷林

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

基于跳距與改進(jìn)粒子群算法的DV-Hop定位算法*

范時(shí)平*，羅丹，劉艷林

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

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

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

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

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

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

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

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

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

1.1.1計(jì)算最小跳數(shù)

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

1.1.2平均跳距的計(jì)算

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

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

1.1.3未知節(jié)點(diǎn)的估計(jì)

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

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

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

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

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

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

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

圖1　兩信標(biāo)節(jié)點(diǎn)間部分拓?fù)潢P(guān)系

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

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

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

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

2.1改進(jìn)的平均跳距

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

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

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

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

其中，dij為信標(biāo)節(jié)點(diǎn)的實(shí)際距離，d?ij=avghopsizei· hopij為信標(biāo)節(jié)點(diǎn)i、j的估計(jì)距離。

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

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

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

②改進(jìn)的信標(biāo)節(jié)點(diǎn)i的平均每跳距離為信標(biāo)節(jié)點(diǎn)i與其余m-1個(gè)信標(biāo)節(jié)點(diǎn)的平均每跳距離的加權(quán)，即

2.2改進(jìn)的粒子群算法

粒子群優(yōu)化算法是由Eberhart和Kennedy博士提出的新型智能算法。粒子群優(yōu)化算法與其他智能算法相比，它具有簡(jiǎn)單，易實(shí)現(xiàn)以及較強(qiáng)的優(yōu)化能力。粒子群算法的數(shù)學(xué)描述如下：假設(shè)種群數(shù)為N，每個(gè)粒子i包括一個(gè)D維坐標(biāo)和速度向量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］上服從均勻分布的隨機(jī)數(shù)，r為約束因子，速度和位置更新如下式：

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

2.2.1權(quán)重的改進(jìn)

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

其中A=0.5·rand（）。

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

2.2.2改進(jìn)的位置更新

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

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

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

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

3　本文的算法步驟

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

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

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

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

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

⑥比較當(dāng)前位置與粒子歷史最優(yōu)位置的適應(yīng)度值的大小。若當(dā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　實(shí)驗(yàn)與仿真

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

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

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

圖3　未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的分布

4.2實(shí)驗(yàn)結(jié)果分析

4.2.1信標(biāo)節(jié)點(diǎn)對(duì)定位誤差影響

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

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

4.2.2通信半徑對(duì)定位誤差影響

假設(shè)信標(biāo)節(jié)點(diǎn)為20時(shí)，改變通信半徑的情況下，從圖中得到本文算法與其他3種算法相比具有更高的定位精度。如圖5所示，通信半徑在30 m以前，節(jié)點(diǎn)的定位誤差隨通信半徑的增加呈減小的趨勢(shì)。這是因?yàn)橥ㄐ虐霃皆酱?，?jié)點(diǎn)的連通度越大，計(jì)算的平均每跳距離越精確；在30 m到40 m之間呈現(xiàn)出平滑的趨勢(shì)；但當(dāng)通信半徑增加到40 m后，節(jié)點(diǎn)的定位誤差有微小的上升趨勢(shì)。這是因?yàn)橥ㄐ虐霃皆黾拥揭欢ǔ潭群笮艠?biāo)節(jié)點(diǎn)的平均每跳距離有更大的誤差，使定位精度下降。因此，通信半徑并不是越大越好?？傊?，本文提出的算法優(yōu)于其余三種定位算法。

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

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

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

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

5　結(jié)束語(yǔ)

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

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

［2］李曉維，徐勇軍，任豐原.無(wú)線傳感器網(wǎng)絡(luò)技術(shù)［M］.北京：北京理工大學(xué)，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ù)學(xué)報(bào)，2015，28（6）：883-887.

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

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

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

［12］曹欲曉，嚴(yán)奎，徐金寶.一種最優(yōu)錨節(jié)點(diǎn)集合上的兩重粒子群優(yōu)化DV-Hop定位算法［J］.傳感技術(shù)學(xué)報(bào)，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.

范時(shí)平（1970-），男，碩士，副教授，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)、嵌入式系統(tǒng)；

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

劉艷林（1990-），女，碩士，碩士研究生，主要研究方向?yàn)榇髷?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

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

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