基于改進(jìn)粒子群優(yōu)化的WSN定位算法

邴曉瑛，徐保國(guó)

（1.江南大學(xué)輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇無(wú)錫214122；2.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無(wú)錫214122）

基于改進(jìn)粒子群優(yōu)化的WSN定位算法

邴曉瑛1，徐保國(guó)2

（1.江南大學(xué)輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇無(wú)錫214122；2.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無(wú)錫214122）

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)中經(jīng)典DV-Hop定位算法第3階段利用多邊測(cè)量法計(jì)算未知節(jié)點(diǎn)位置存在較大誤差的問(wèn)題，提出了一種改進(jìn)的粒子群算法來(lái)優(yōu)化求解未知節(jié)點(diǎn)坐標(biāo)。應(yīng)用粒子群算法，引入自適應(yīng)慣性權(quán)重，并對(duì)粒子速度差分變異，繼續(xù)維持群體多樣性，保證前期搜索的速度和后期搜索的精度，減小陷入局部最優(yōu)的可能，尋得全局最優(yōu)未知節(jié)點(diǎn)坐標(biāo)。仿真結(jié)果表明，該算法在不增加網(wǎng)絡(luò)成本的前提下，有效的提高了傳感器節(jié)點(diǎn)的定位精度，拓寬了定位算法的應(yīng)用范圍。

無(wú)線傳感器網(wǎng)絡(luò)；DV-Hop定位；自適應(yīng)慣性權(quán)重；粒子群；差分變異

無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）現(xiàn)已廣泛應(yīng)用于很多領(lǐng)域，而傳感器節(jié)點(diǎn)的位置特別重要，是WSN應(yīng)用的基礎(chǔ)。現(xiàn)階段定位算法主要分為兩類，基于測(cè)距（Range-based）［1］的定位算法和基于非測(cè)距（Range-free）［2］的定位算法。其中DV-Hop［3］算法是典型的基于非測(cè)距的定位算法，該算法硬件成本較低、能耗較小，傳輸?shù)男盘?hào)受外界影響較小，并且能滿足大部分實(shí)際應(yīng)用對(duì)定位精度要求。

美國(guó)Rutgers University的Dragos Niculescu等利用GPS和距離矢量路由思想提出了DV-Hop算法［4］，定位精度較低。隨著社會(huì)的發(fā)展需要，對(duì)許多應(yīng)用的定位精度要求愈來(lái)愈高。許多學(xué)者對(duì)經(jīng)典的DV-Hop算法進(jìn)行了深入研究并改進(jìn)，文獻(xiàn)［5］利用粒子群算法改進(jìn)了經(jīng)典算法對(duì)未知節(jié)點(diǎn)坐標(biāo)的求解過(guò)程，校正了未知節(jié)點(diǎn)的位置，減小了定位誤差；文獻(xiàn)［6］采用差分進(jìn)化算法優(yōu)化適應(yīng)度函數(shù)，得到最優(yōu)解，減小了定位誤差；文獻(xiàn)［7～8］分別用遺傳算法、人工蜂群算法等尋求未知節(jié)點(diǎn)坐標(biāo)，使其更接近實(shí)際坐標(biāo)。

文中針對(duì)DV-Hop第3階段計(jì)算未知節(jié)點(diǎn)位置產(chǎn)生較大誤差的問(wèn)題，結(jié)合粒子群算法和差分進(jìn)化算法的特點(diǎn)，提出了一種帶動(dòng)態(tài)慣性權(quán)重，并利用差分進(jìn)化算法變異粒子群速度的速度差分變異粒子群算法——PD-DV-Hop。實(shí)驗(yàn)結(jié)果證明，PD-DV-Hop能有效的減小定位誤差，提高定位精度。

1　問(wèn)題分析

1.1DV-Hop定位算法

根據(jù)DV-Hop定位算法第一、二階段得到的未知節(jié)點(diǎn)D（x，y）與信標(biāo)節(jié)點(diǎn)（x1，y1），（x2，y2），…，（x2，yn）最小跳數(shù)與平均每跳距離，求得相應(yīng)節(jié)點(diǎn)間距離為d1，d2，…dn則

可表示為線性方程組AL+ε=b，ε為n-1維隨機(jī)誤差向量，其中L=（x，y）T，則最小二乘法求得方程的解為L(zhǎng)=（ATA）-1ATb。

1.2誤差分析

在經(jīng)典DV-Hop定位算法中，dn是由未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的估算平均跳距與最小跳數(shù)乘積等效替代，包含很大的誤差，因此根據(jù)最小二乘法求得的未知節(jié)點(diǎn)坐標(biāo)精度相對(duì)較低，為提高定位精度，我們將問(wèn)題轉(zhuǎn)化為優(yōu)化估算距離dn的問(wèn)題［9］。

設(shè)未知節(jié)點(diǎn)D（x，y）到信標(biāo)節(jié)點(diǎn)A1，A2，…，An的實(shí)際距離為r1，r2，…，rn，相應(yīng)的測(cè)距誤差為ε1，ε2，…，εn，應(yīng)滿足式（2）可轉(zhuǎn)換為

問(wèn)題可化解為求解

當(dāng)式（3）取得最小值時(shí)，未知節(jié)點(diǎn)的估計(jì)坐標(biāo)最接近真實(shí)坐標(biāo)，定位誤差最小，本文采用改進(jìn)粒子算法對(duì)式（3）進(jìn)行尋優(yōu)求解。

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

2.1粒子群算法

粒子群算法（Particle Swarm Optimization，PSO）是在鳥(niǎo)類捕食行為的基礎(chǔ)上，在1995年由Kennedy和Eberhart提出的一種群體智能優(yōu)化算法［10］。

假設(shè)D維搜索空間，粒子種群X=（X1，X2，…，Xn）數(shù)量為n，粒子速度和位置更新如下，

2.2DE算法

DE算法是對(duì)種群進(jìn)行并行進(jìn)化，是一種貪婪遺傳算法，具有保優(yōu)思想［11］。隨機(jī)產(chǎn)生初始種群后，進(jìn)行如下操作：

1）變異操作：

隨機(jī)數(shù)r1，r2r3∈（1，2，…，n），n為種群數(shù)量，F(xiàn)為交叉因子。

2）交叉操作：

隨機(jī)randb（j）∈［0，1］，randr（i）∈｛1，2，…D｝，交叉因子CR∈［0，1］。

3）選擇操作：

f（x）為適應(yīng)度函數(shù)。

DE算法原理非常簡(jiǎn)單，只有少量調(diào)整參數(shù)，魯棒性較強(qiáng)，全局搜索能力較好［12］。

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

粒子群算法調(diào)整參數(shù)少，結(jié)構(gòu)簡(jiǎn)單，但優(yōu)化過(guò)程中得到的最優(yōu)解被種群所有粒子共享，導(dǎo)致在某些特定位置容易發(fā)生粒子聚集現(xiàn)象，種群多樣性在算法進(jìn)化后期降低，易陷入局部最優(yōu)。

因此，本文引入自適應(yīng)慣性權(quán)重，并用差分進(jìn)化算法變異粒子速度，提出了一種改進(jìn)粒子群算法，既維持種群多樣性，又保證全局最優(yōu)解。

2.3.1自適應(yīng)慣性權(quán)重的改進(jìn)

式（4）中，粒子繼承先前速度的能力受慣性權(quán)重ω影響。ω越大，全局搜索能力越強(qiáng)；ω越小，局部搜索能力越強(qiáng)。標(biāo)準(zhǔn)粒子群算法中慣性權(quán)重ω不變，算法收斂速度較快，但易在進(jìn)化后期陷入局部最優(yōu)，本文采用下式動(dòng)態(tài)調(diào)整ω。

其中，ωmax，ωmin分別為ω初始值和最終值；k為當(dāng)前迭代次數(shù)；Tmax為最大迭代次數(shù)。

由式（11）可以看出，粒子群算法進(jìn)化前期ω變化較慢，取值較大，保證了全局搜索能力；后期ω變化較快，取值較小，提高了局部搜索能力。

2.3.2粒子群速度差分變異

綜合考慮PSO算法和DE算法的優(yōu)缺點(diǎn)，將差分變異的思想引入到PSO算法中，在PSO算法后期進(jìn)化停滯時(shí)，差分變異粒子速度。粒子的變異時(shí)機(jī)由粒子的進(jìn)化停滯步數(shù)t0確定，當(dāng)t0＞T0（停滯閾值）時(shí)，粒子速度開(kāi)始變異，并隨機(jī)改變差分向量振幅，繼續(xù)維持種群多樣性。對(duì)粒子速度差分變異操作如下：

其中：Fmax，F(xiàn)min∈［0，2］為變異因子F的上下邊界；k表示粒子的任一維度，以保證粒子至少有一個(gè)維度的速度發(fā)生了變異；r表示［0，1］間的隨機(jī)數(shù)；CR為粒子變異概率即變異交叉因子。vid，v1d，v2d為v中隨機(jī)選取的3個(gè)互不相同粒子的速度。

改進(jìn)的粒子群算法既保證了進(jìn)化前期的收斂速度，又提高了后期搜索準(zhǔn)確性，增強(qiáng)了算法鄰域搜索能力，有效的提升了算法進(jìn)化后期的尋優(yōu)速度和尋優(yōu)能力，保證全局最優(yōu)解的獲取。

2.4PD-DV-Hop算法設(shè)計(jì)

改進(jìn)粒子群算法通過(guò)對(duì)式（3）所示的適應(yīng)度函數(shù)進(jìn)行優(yōu)化，得到最優(yōu)解，具體實(shí)現(xiàn)過(guò)程如下：

1）初始化種群，規(guī)模為n；

2）計(jì)算粒子適應(yīng)度值f（x，y），找到并記錄Pi，Pg；

3）根據(jù)式（4）、（5）更新粒子位置和速度，比較更新前后的適應(yīng)度值，更新個(gè)體極值和群體極值；

4）當(dāng)粒子進(jìn)化停滯次數(shù)t0＜T0（閾值）時(shí)，執(zhí)行步驟3）；否則執(zhí)行步驟5）；

5）產(chǎn)生一個(gè)隨機(jī)數(shù)rand，若rand≤CR（交叉因子），根據(jù)式（8）、（9）更新粒子位置和速度；否則執(zhí)行步驟6）；

6）隨機(jī)選擇群體粒子的任一維度進(jìn)行變異交叉操作；

7）比較更新前后粒子適應(yīng)度值，更新個(gè)體極值和群體極值；

8）判斷當(dāng)前迭代次數(shù)t＜Tmax（最大迭代次數(shù)）是否成立，若成立，則執(zhí)行步驟5）；否則，輸出最優(yōu)解，結(jié)束。

3　仿真實(shí)驗(yàn)及結(jié)果分析

3.1仿真環(huán)境及參數(shù)設(shè)定

本文采用MATLAB仿真軟件實(shí)現(xiàn)傳感器節(jié)點(diǎn)定位算法。假設(shè)所有傳感器節(jié)點(diǎn)均勻隨機(jī)分布100 m×100 m在的正方形區(qū)域內(nèi)。

為了能更直觀的評(píng)價(jià)PD-DV-Hop算法的性能，將其分別與傳統(tǒng)的DV-Hop算法，PSO改進(jìn)的DV-Hop算法（PSODV-Hop），DE改進(jìn)的DV-Hop算法（DE-DV-Hop）進(jìn)行對(duì)比仿真實(shí)驗(yàn)，并比較分析實(shí)驗(yàn)數(shù)據(jù)。為確保結(jié)果的準(zhǔn)確性，在每種測(cè)試條件下，對(duì)上述4種算法分別進(jìn)行50次隨機(jī)分布測(cè)試，取算術(shù)平均值。定位算法性能評(píng)價(jià)標(biāo)準(zhǔn)為歸一化定位誤差，其計(jì)算公式為：

其中，（xir，yir），（xie，yie）代表第i個(gè)未知節(jié)點(diǎn)的實(shí)際坐標(biāo)和通過(guò)定位算法得出的估計(jì)坐標(biāo)，R為網(wǎng)絡(luò)通信半徑，N為未知節(jié)點(diǎn)總數(shù)。

3.2仿真結(jié)果分析

3.2.1信標(biāo)節(jié)點(diǎn)比例對(duì)定位精度的影響

圖2表示了節(jié)點(diǎn)總數(shù)N=100，通信半徑R=30 m，信標(biāo)節(jié)點(diǎn)比例在5%～30%變化時(shí)，4種算法的節(jié)點(diǎn)定位誤差圖。由圖可知，4種算法定位誤差與信標(biāo)節(jié)點(diǎn)比例整體上成反比。PDDV-Hop定位誤差在信標(biāo)節(jié)點(diǎn)各種比例下均小于其他3種算法，比傳統(tǒng)DV-Hop算法的平均定位誤差平均減少了約27%，比PSO-DV-Hop算法平均減少了約7%，比DE-DVHop算法平均減少了約5%。

3.2.2通信半徑對(duì)定位精度的影響

圖3表示了節(jié)點(diǎn)總數(shù)N=100，信標(biāo)節(jié)點(diǎn)數(shù)為30，通信半徑在15～40 m變化時(shí)，4種算法的節(jié)點(diǎn)定位誤差圖。由圖可知，在節(jié)點(diǎn)總數(shù)及信標(biāo)節(jié)點(diǎn)數(shù)一定的條件下，4種算法定位誤差與通信半徑整體上成反比。PD-DV-Hop定位誤差在各通信半徑下均小于其它3種算法，其平均誤差相較于傳統(tǒng)DVHop算法、PSO-DV-Hop算法、DE-DV-Hop算法分別減少了約18%、7%、6%。

圖1　信標(biāo)節(jié)點(diǎn)比例不同時(shí)的定位誤差Fig.1Localization error with different beacon node ratio

圖2　通信半徑不同時(shí)的定位誤差Fig.2Localization error with different communication radius

3.2.3節(jié)點(diǎn)總數(shù)對(duì)定位精度的影響

圖4表示了信標(biāo)節(jié)點(diǎn)數(shù)為30，通信半徑R=30 m，節(jié)點(diǎn)總數(shù)分別取100，150，200，250，300，350時(shí)，4種算法的節(jié)點(diǎn)定位誤差圖。由圖可知，在信標(biāo)節(jié)點(diǎn)和通信半徑一定的情況下，隨節(jié)點(diǎn)總數(shù)的增大，4種算法的定位誤差均逐漸減小。PDDV-Hop算法誤差均小于其它3種算法，其平均誤差相較于傳統(tǒng)DV-Hop算法、PSO-DV-Hop算法、DE-DV-Hop算法分別減少了約28%、5%、4%。

圖3　節(jié)點(diǎn)總數(shù)不同時(shí)的定位誤差Fig.3Localization error with different total number of nodes

4　結(jié)論

文中提出了一種帶自適應(yīng)慣性權(quán)重的速度差分變異粒子群（PD-DV-Hop）算法來(lái)優(yōu)化求解傳感器未知節(jié)點(diǎn)坐標(biāo)，較經(jīng)典DV-Hop定位算法很大程度上提高了定位精度。通過(guò)對(duì)慣性權(quán)重的動(dòng)態(tài)更新，以及對(duì)粒子速度的差分變異，有效的提高了種群的多樣性，保證了全局最優(yōu)。仿真實(shí)驗(yàn)結(jié)果表明，本文算法在不增加網(wǎng)絡(luò)通信成本的前提下，有效的提高了傳感器節(jié)點(diǎn)的定位精度。該算法是通過(guò)最小化與DV-Hop相關(guān)的適應(yīng)度函數(shù)來(lái)優(yōu)化定位算法，將改進(jìn)粒子群算法與其他定位算法結(jié)合也是未來(lái)的一個(gè)研究方向。

［1］Chu Yan-Ling，Jau-Rong Tzeng，Cheng Yung-Pin，Sun Min-Te.Density-Adaptive Range-free Localization in Large-Scale Sensor Networks［C］//Parallel Processing Workshops（ICPPW），2012 41st International Conference on，2012：488-495，1249-1250.

［2］Maung N A M.Kawai M.Experimental evaluations of RSS threshold-based optimized DV-Hop localization for wireless ad-hoc networks［J］.2014，50（17）：1246-1248.

［3］Gayan S.Dias D.Improved DV-Hop algorithm through anchor poition re-estimation［C］//Wireless and Mobile，2014 IEEE Asia Pacific Conference on.2014：126-131.

［4］Niculescu D，NATH B.DV Based Positioning in Ad Hoc Networks［C］//Telecommunication Systems，2003：22（1/2/3/4）：267-280.

［5］黃艷，臧傳治，于海斌.基于改進(jìn)粒子群優(yōu)化的無(wú)線傳感器網(wǎng)絡(luò)定位算法［J］.控制與決策，2012，27（1）：156-160.

［6］林雯，張烈平，王守峰.基于差分進(jìn)化算法的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方法研究［J］.計(jì)算機(jī)測(cè)量與控制，2013，21（7）：2023-2026.

［7］劉彥隆，呂顯朋，王相國(guó).混合遺傳算法在WSNs定位中的應(yīng)用［J］.傳感器與微系統(tǒng)，2014，33（2）：150-153.

［8］李牧東，熊偉，梁青.基于人工蜂群改進(jìn)算法的無(wú)線傳感器網(wǎng)絡(luò)定位算法［J］.傳感技術(shù)學(xué)報(bào)，2013，26（2）：241-245.

［9］周天綺，姜鳳茹.基于MPSO-DV-Hop的無(wú)線傳感器節(jié)點(diǎn)定位［J］.計(jì)算機(jī)工程與應(yīng)用，2013，49（23）：52-55.

［10］Zhao Yan-Huang，Qian Zhi-Hong，Shang Xiao-Hang.PSO localization algorithm for WSN nodes based on modifying average hop distances［J］.Tongxin Xuebao/Journal on Communications，2013，34（9）：105-114.

［11］Das S，Suganthan P N.Differential evolution：A survey of the state of the art［J］.IEEE Transactions on evolutionary computation.2011，15（1）：4-28.

［12］喬俊飛，付嗣鵬，韓紅桂.基于混合變異策略的改進(jìn)差分進(jìn)化算法及函數(shù)優(yōu)化［J］.控制工程，2013，20（5）：943-947.

Localization method based on modified particle swarm optimization for wireless sensor networks

BING Xiao-ying1，XU Bao-guo2
（1.Key Laboratory of Industrial Advanced Process Control for Light Industry，Ministry of Education，Jiangnan University，Wuxi 214122，China；2.School of Internet of Things Engineering，Jiangnan University，Wuxi 214122，China）

An improved particle swarm algorithm to optimize the unknown node coordinates is proposed in order to solve the problem that when using the traditional DV-Hop algorithm the third phase error is too large.Introducing the adaptive inertia weight and difference change particle velocity in order to maintain diversity of the population，and ensure the pre-search speed and late-search accuracy to avoid falling into local optima，find out the global optimal unknown node coordinates.The simulation experimental results showed that，the proposed algorithm possesses of higher location precision without extra cost，broaden the application scope of localization algorithm.

WSN；DV-Hop localization；adaptive inertia weight；PSO algorithm；differential mutation

TN92

A

1674－6236（2015）22-0143-04

2015-02-10稿件編號(hào)：201502089

國(guó)家自然科學(xué)基金面上項(xiàng)目（21276111）；國(guó)家自然科學(xué)基金青年基金（21206053）；浙江省自然科學(xué)基金重大專項(xiàng)（2011C12033）

邴曉瑛（1989—），女，山東青島人，碩士。研究方向：無(wú)線傳感器定位算法。