一種改進(jìn)的粒子群優(yōu)化無線傳感器網(wǎng)絡(luò)定位算法*

張先超　劉興長

(后勤工程學(xué)院后勤信息與軍事物流工程系　重慶　401311)

?

一種改進(jìn)的粒子群優(yōu)化無線傳感器網(wǎng)絡(luò)定位算法*

張先超劉興長

(后勤工程學(xué)院后勤信息與軍事物流工程系重慶401311)

摘要實現(xiàn)節(jié)點的精確定位是無線傳感器網(wǎng)絡(luò)研究領(lǐng)域中一個重要方向。基于粒子群優(yōu)化的無線傳感器網(wǎng)絡(luò)定位算法與極大似然估計算法、最小二乘法等傳統(tǒng)算法相比,定位精度更高,但易陷入局部最優(yōu)。針對上述缺點,將一種帶有動態(tài)擾動項的改進(jìn)算法引入無線傳感器網(wǎng)絡(luò)定位,并在目標(biāo)函數(shù)中引入加權(quán)因子,以削弱測距誤差的影響。仿真結(jié)果表明,該算法可以加快收斂速度,提高定位精度。

關(guān)鍵詞無線傳感器網(wǎng)絡(luò); 粒子群優(yōu)化算法; 動態(tài)擾動項; 定位精度

Class NumberTP393

1引言

無線傳感器網(wǎng)絡(luò)是由隨機部署在目標(biāo)區(qū)域內(nèi)的數(shù)量巨大的離散傳感器節(jié)點組成,節(jié)點將采集到的信息以自組多跳的方式傳送到基站,從而實現(xiàn)了物理世界和人類社會之間的信息交換[1～2]。在實際應(yīng)用中,大多數(shù)情況下無線傳感器網(wǎng)絡(luò)獲取到的監(jiān)測信息必須附帶相應(yīng)的位置信息,否則,這些監(jiān)測信息將失去意義。無線傳感器網(wǎng)絡(luò)研究的一個重要內(nèi)容就是節(jié)點定位技術(shù),它是無線傳感器網(wǎng)絡(luò)的支撐技術(shù),并具有廣泛的應(yīng)用范圍[3～4]。研究提高定位精度的技術(shù)手段是當(dāng)前無線傳感器網(wǎng)絡(luò)的熱點[5～8]。

按是否需要節(jié)點間的距離信息分類,無線傳感器網(wǎng)絡(luò)的定位技術(shù)可分為兩類:一種是基于測距(rang-based)的技術(shù),另一種是無需測距(rang-free)的技術(shù)。在基于測距的定位技術(shù)中,角度定位(AOA)和三邊定位(Trilateration)是比較常規(guī)的定位方法[9]。在三邊定位中,極大似然估計、最小二乘法很容易受到測距誤差的影響,定位精度較低。隨著無線傳感器網(wǎng)絡(luò)定位技術(shù)研究的不斷深入,許多新的定位算法被不斷提出。目前,由于節(jié)點硬件資源的不斷豐富,處理器性能的不斷提高,將粒子群優(yōu)化算法、遺傳算法等智能算法應(yīng)用于節(jié)點定位已經(jīng)成為一個新的研究方向[10]。粒子群定位算法操作簡單、計算量較小,非常適合應(yīng)用于硬件資源有限的無線傳感器網(wǎng)絡(luò)。文獻(xiàn)[11～12]將粒子群優(yōu)化算法應(yīng)用于節(jié)點定位,通過迭代尋優(yōu)得到了優(yōu)于通過極大似然估計、最小二乘法計算得到的節(jié)點位置,提高了定位精度。但是,由于粒子群算法的全局尋優(yōu)能力不足,易陷入局部最優(yōu),會造成較大的定位誤差。因此,必須對粒子群算法進(jìn)行改進(jìn)以提高無線傳感器網(wǎng)絡(luò)定位精度。為了提高粒子群定位算法的定位精度,本文對粒子群算法的速度更新公式以及尋優(yōu)的目標(biāo)函數(shù)進(jìn)行改進(jìn),以提高粒子群算法的全局尋優(yōu)能力,且減小測距誤差對定位精度的影響。

2粒子群優(yōu)化算法

粒子群優(yōu)化算法(Particle Swarm Optimization,PSO)是一種基于集群智能(Swarm-Intelligence,SI)方法的計算技術(shù)[12]。該算法由美國學(xué)者Eberhart博士和Kennedy博士于1995年提出[13]。

假設(shè)在D維的搜索空間內(nèi),存在一個種群大小為M的粒子群。每個粒子在空間中的位置坐標(biāo)xi=(xi1,xi2,…,xid),搜索速度vi=(vi1,vi2,…,vid),搜索到的個體最優(yōu)位置為pi=(pi1,pi2,…,pid),搜索到的全局最優(yōu)位置為gb=(gb1,gb2,…,gbd),其中,i=1,2,…,M,d=1,2,…,D。粒子尋優(yōu)過程中的速度更新公式、位置更新公式及慣性權(quán)重計算公式如下

vk+1id= w·vkid+c1·r1·(pkid-xkid)

(1)

(2)

(3)

其中,c1、c2是學(xué)習(xí)因子,均為非負(fù)的常數(shù),常設(shè)c1=c2=2;r1和r2是介于[0,1]的隨機數(shù);w是慣性權(quán)重,用來平衡粒子的全局搜索能力和局部搜索能力,若w較小則有利于提高算法的局部搜索能力,若w較大則有利于提高算法的全局搜索能力;粒子的搜索速度vid∈[-vmax,vmax],vmax太大容易使粒子飛離最優(yōu)解,vmax太小容易使粒子陷入局部最優(yōu),粒子的搜索速度通常設(shè)為每維變換范圍的10%～20%;k為當(dāng)前迭代次數(shù);T為終止迭代次數(shù)。

3改進(jìn)的粒子群優(yōu)化算法

3.1迭代公式的改進(jìn)

針對粒子群算法后期易陷入局部最優(yōu)的缺陷,結(jié)合無線傳感器網(wǎng)絡(luò)硬件資源受限的實際情況,本文采用一種帶有動態(tài)擾動項的粒子群優(yōu)化算法(Particle Swarm Optimization Dynamic Disturbance Term,PSO-DDT)。該算法的速度更新公式變?yōu)槿缦?

vk+1id= w·vkid+c1·r1·(pkid-xkid)+c2·r2

(4)

rand()是[0,1]之間的隨機數(shù);t和h均是[0,1]之間的常數(shù),根據(jù)實驗情況設(shè)定。該算法在粒子速度更新公式中加入動態(tài)擾動項,在迭代前期粒子速度較大,動態(tài)擾動項對速度的影響可以忽略;隨著迭代次數(shù)k的增加,粒子速度減慢,擾動項的值增大,保證了粒子在迭代后期速度不為零,且隨機數(shù)rand()增強了擾動項的擾動性能,可以有效地使粒子跳出局部最優(yōu)。該算法僅在速度更新式(1)中添加一個動態(tài)擾動項,并未增加算法的復(fù)雜度,適合無線傳感器網(wǎng)絡(luò)的實際應(yīng)用。

3.2適應(yīng)度函數(shù)設(shè)定

適應(yīng)度函數(shù)即目標(biāo)函數(shù),用來判斷粒子的優(yōu)劣。粒子在尋優(yōu)過程中,通過比較適應(yīng)度函數(shù)值的大小來更新個體最優(yōu)位置和全局最優(yōu)位置。設(shè)100×100m的區(qū)域內(nèi)部署了M個位置已知的節(jié)點(錨節(jié)點),N個位置未知的節(jié)點(盲節(jié)點)。錨節(jié)點的坐標(biāo)為Ai(xi,yi)i=1,2,…,M,未知節(jié)點的坐標(biāo)為Nj(xj,yj),j=1,2,…,N,已知錨節(jié)點和未知節(jié)點的距離測量值di。因為通常情況下,測距誤差隨著測量距離的增加而增大[14],所以為了減少測距誤差對定位精度的影響,本文在適應(yīng)度函數(shù)中引入加權(quán)因子。設(shè)適應(yīng)度函數(shù)如下:

(5)

(6)

其中,λi為加權(quán)因子,0<λi<1;f為一常數(shù),0

3.3算法描述

無線傳感器網(wǎng)絡(luò)的錨節(jié)點相當(dāng)于該算法中的粒子,盲節(jié)點的坐標(biāo)即是粒子要搜索的位置,算法的具體實現(xiàn)流程如下。

1) 初始化粒子種群,種群大小為錨節(jié)點數(shù)目M。粒子的初始位置為各錨節(jié)點的位置,隨機設(shè)置粒子初速度。計算出各粒子的適應(yīng)度值,將適應(yīng)度值最小的粒子的位置設(shè)為全局最優(yōu)位置,將每個粒子的位置設(shè)為個體最優(yōu)位置。

2) 根據(jù)式(2)、式(4)更新每個粒子位置和速度。

3) 對于每個粒子,根據(jù)式(5)計算更新后的適應(yīng)度值,若更新后的適應(yīng)度值小于個體歷史最優(yōu)位置對應(yīng)的適應(yīng)度值,則將當(dāng)前的粒子位置設(shè)為個體最優(yōu)位置;將個體最優(yōu)位置的適應(yīng)度值與歷史全局最優(yōu)位置對應(yīng)的適應(yīng)度值比較,若個體最優(yōu)位置的適應(yīng)度值小于歷史全局最優(yōu)位置的適應(yīng)度值,則將該粒子位置設(shè)為全局最優(yōu)位置。

4) 檢查終止,若達(dá)到最大迭代次數(shù)kmax,或fitness<ε(ε為距離控制值),則停止迭代;否則轉(zhuǎn)到第2)步。

5) 輸出全局最優(yōu)位置和終止迭代次數(shù)。

4實驗仿真與分析

4.1仿真參數(shù)設(shè)定

在Matlab軟件上對算法進(jìn)行仿真實驗,獨立進(jìn)行20次實驗。各參數(shù)設(shè)置如下:c1=c2=2;最大迭代次數(shù)kmax=500;vmax=5m;慣性權(quán)重最大值wmax=0.9,最小值wmin=0.1;t=0.5,h=0.5;f=0.98。距離控制值ε根據(jù)平均測距誤差設(shè)定。設(shè)100m×100m的區(qū)域內(nèi)布置四個錨節(jié)點和一個盲節(jié)點,節(jié)點的通信半徑為30m。錨節(jié)點分別為A1(10,30),A2(20,35),A3(35,15),A4(25,30),盲節(jié)點N(x,y)的真實坐標(biāo)為(5,15),錨節(jié)點到盲節(jié)點的距離分別為d1,d2,d3,d4。

4.2結(jié)果分析

圖1分別繪出平均測距誤差0%時,初始狀態(tài)、迭代30次和60次以及迭代終止時粒子位置,粒子最后的位置即是無線傳感器網(wǎng)絡(luò)中盲節(jié)點的位置。

圖1　節(jié)點定位仿真圖

設(shè)距離控制值ε=2m,在平均測距誤差為0%時,PSO算法的終止迭代次數(shù)的均值為162次,PSO-DDT算法的終止迭代次數(shù)的均值為87次;在平均測距誤差為20%時,PSO算法的終止迭代次數(shù)的均值為321次,PSO-DDT算法的終止迭代次數(shù)的均值為216次。圖2繪出不同平均測距誤差情況下,最大迭代次數(shù)為500次,距離控制值ε=0m,兩種算法的適應(yīng)度函數(shù)衰減曲線。由圖可知,在平均測距誤差為0%和20%兩種情況下,當(dāng)k>50次時適應(yīng)度函數(shù)曲線衰減緩慢,PSO-DDT算法與PSO算法相比,其適應(yīng)度函數(shù)曲線的衰減更快。從仿真的結(jié)果可以得出,帶有動態(tài)擾動項的改進(jìn)粒子群算法可以克服粒子陷入局部最優(yōu),加快收斂速度。

圖2　算法的收斂曲線

在平均測距誤差不大的情況下,PSO-DDT算法與PSO算法都可以較為準(zhǔn)確地計算出未知節(jié)點的位置。平均測距誤差0%時,PSO算法和PSO-DDT算法計算出的盲節(jié)點N的坐標(biāo)均值分別是(5.0348,15.0120),(5.0234,15.0101)。但隨著誤差的增大,平均定位誤差也逐漸增大,當(dāng)平均測距誤差在25%時,PSO算法的平均定位誤差高達(dá)27%。由圖3可知,PSO-DDT算法與PSO算法相比,其定位精度有所提高,但平均測距誤差對兩種算法的定位精度影響均較大;在適應(yīng)度函數(shù)中引入加權(quán)因子λi后,在一定程度上抑制了壞測距的影響,可以降低平均定位誤差。

圖3　平均定位誤差與平均測距誤差的關(guān)系

5結(jié)語

為了克服粒子群優(yōu)化定位算法后期易陷入局部最優(yōu)的缺陷,本文采用一種帶有動態(tài)擾動項的改進(jìn)算法進(jìn)行節(jié)點定位。在設(shè)計適應(yīng)度函數(shù)時,考慮到測距誤差對定位精度的影響,在適應(yīng)度函數(shù)中引入加權(quán)因子以削弱測距誤差的影響。仿真表明,改進(jìn)算法能克服粒子早熟,易陷入局部最優(yōu)的缺點,加快了算法的收斂速度,同時提高了定位精度。但通過仿真實驗發(fā)現(xiàn),該算法只能在一定程度上削弱測距誤差對定位精度的影響。在實際情況中,各種測距手段均存在不同程度的誤差,下一步工作應(yīng)重點研究減少測距誤差的方法。

參 考 文 獻(xiàn)

[1] 崔莉,鞠海玲,苗勇.無線傳感器網(wǎng)絡(luò)研究進(jìn)展[J].計算機研究與發(fā)展,2005,42(1):163-174.

CUI Li, JU Hailing, MIAO Yong. Overview of Wireless Sensor Networks[J]. Journal of Computer Research and Development,2005,42(1):163-174.

[2] 劉雨.無線傳感器網(wǎng)絡(luò)中的信息處理[D].北京:北京郵電大學(xué),2006:1-2.

LIU Yu. The information processing in wireless sensor networks[D]. Beijing: Beijing University of Posts and Telecommunications,2006:1-2.

[3] 趙仕俊,唐懿芳.無線傳感器網(wǎng)絡(luò)[M].北京:科學(xué)出版社,2013:89-108.

ZHAO Shijun, TANG Yifang. Wireless sensor networks[M]. Beijng: Science Press,2013:89-108.

[4] 李曉維,徐勇軍,任豐源.無線傳感器網(wǎng)絡(luò)技術(shù)[M].北京:北京理工大學(xué)出版社,2007:191-199.

LI Xiaowei, XU Yongjun, REN Fengyuan. Techniques for wireless sensor networks[M]. Beijing: Beijing Institute of Technology Press,2007:191-199.

[5] Li F F, Luo F, Wang J X, et al. An effective self-adapting localization algorithm in wireless sensor networks[J]. Journal of Applied Mechanics and Materials,2011,58-60:1013-1017.

[6] Jian L R, Zheng Y, Liu Y H. Beyond triangle inequality: Sifting noisy and outlier distance measurements forlocalization[C]//Proc of IEEE INFOCOM 2010. San Diego: IEEE Press,2010:1-9.

[7] Kung H T, Lin C K, Lin T H, et al. Localization with snap-inducing shaped residuals: Coping with errors in measurement[C]//Proc of MobiCom 2009. Beijing: ACM Press,2009:333-344.

[8] Li Z, Trappe W, Zhang Y, et al. Robust statistical methods for securing wireless localization in sensor networks[C]//Proc of IPSN 2005. Los Angeles: IEEE Press,2005:91-98.

[9] NICULESC D, NATH B. Ad Hoc Positioning Systems(APS) Using AOA[J]. In: Proc. of the IEEE INFOCOM 2003,2003(3):1734-1743.

[10] 彭宇,王丹.無線傳感器網(wǎng)絡(luò)定位技術(shù)綜述[J].電子測量與儀器學(xué)報,2011,25(5):389-399.

PENG Yu, WANG Dan. A review: wirless sensor networks localization[J]. Journal of Electronic Measurement and Instrument,2011,25(5):389-399.

[11] 王曉樂,徐家品.基于粒子群優(yōu)化算法的WSNs節(jié)點定位研究[J].計算機應(yīng)用,2009,29(2):494-499.

WANG Xiaole, XU Jiapin. Research on node localization based on particle swarm optimization for WSNs[J]. Journal of Computer Applications,2009,29(2):494-499.

[12] 陳志奎,司威.傳感器網(wǎng)絡(luò)的粒子群優(yōu)化定位算法[J].通信技術(shù),2011,44(1):102-104.

CHEN Zhikui, SI Wei. Particle Swarm Optimization Localization Algorithm for Wireless Sensor Networks[J]. Communications Technology,2011,44(1):102-144.

[13] 高瑋,尹志喜.現(xiàn)代智能仿生算法及其應(yīng)用[M].北京:科學(xué)出版社,2011:178-190.

GAO Wei, YIN Zhixi. Modern bionic algorithm and its application[M]. Beijing: Science Press,2011:178-190.

[14] Wang Xi-huai, Li Jun-jun. Hybrid particle swarm optimization with simulated annealing[C]//Proc of Int Conf on Machine Learning and Cybernetics. Shanghai: IEEE,2004:2402-2405.

[15] Chen W, Mei T, Sun L, et al. Error analyzing for RSSI-based localization in wireless sensor networks[C]//Intelligent Control and Automation, 2008. WCICA 2008. 7th World Congress on. IEEE,2008:2701-2706.

An Improved Localization Method Based on Modified Particle Swarm Optimization for Wireless Sensor Networks

ZHANG XianchaoLIU Xingchang

(Department of Logistics Information & Logistics Engineering, Logistics Engineering University, Chongqing401311)

AbstractLocating nodes accurately is an important branch of wireless sensor networks researching. Algorithm of locating wireless sensor networks based on particle swarm optimization is more accurate comparing with those based on maximum likelihood estimation or/and least squares estimation, but locally optimal. Aiming to correct the defects mentioned above, a modified algorithm with a dynamic disturbance term is introduced to locate wireless sensor networks, also, weighting factors are led into the objective function to weaken the effect from range error. In light of the evidence, this algorithm could quicken convergence rate and improve position precision.

Key Wordswireless sensor networks, particle swarm optimization, dynamic disturbance term, position precision

* 收稿日期:2015年11月3日,修回日期:2015年12月26日

作者簡介:張先超,男,碩士研究生,研究方向:無線傳感器網(wǎng)絡(luò)節(jié)點定位技術(shù)。劉興長,男,博士,教授,碩士生導(dǎo)師,研究方向:無線傳感器網(wǎng)絡(luò)。

中圖分類號TP393

DOI:10.3969/j.issn.1672-9722.2016.05.016