邴曉瑛，徐保國

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

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

邴曉瑛1，徐保國2

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

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

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

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

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

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

1　問題分析

1.1DV-Hop定位算法

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

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

1.2誤差分析

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

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

問題可化解為求解

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

2　基于改進粒子群的DV-Hop定位算法

2.1粒子群算法

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

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

2.2DE算法

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

1）變異操作：

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

2）交叉操作：

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

3）選擇操作：

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

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

2.3粒子群算法改進

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

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

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

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

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

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

2.3.2粒子群速度差分變異

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

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

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

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

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

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

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

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

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

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

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

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

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

3　仿真實驗及結(jié)果分析

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

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

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

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

3.2仿真結(jié)果分析

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

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

3.2.2通信半徑對定位精度的影響

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

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

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

3.2.3節(jié)點總數(shù)對定位精度的影響

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

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

4　結(jié)論

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

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

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

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

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

［9］周天綺，姜鳳茹.基于MPSO-DV-Hop的無線傳感器節(jié)點定位［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］喬俊飛，付嗣鵬，韓紅桂.基于混合變異策略的改進差分進化算法及函數(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稿件編號：201502089

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

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