一種改進的粒子群優化無線傳感器網絡定位算法*

張先超　劉興長

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

?

一種改進的粒子群優化無線傳感器網絡定位算法*

張先超劉興長

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

摘要實現節點的精確定位是無線傳感器網絡研究領域中一個重要方向。基于粒子群優化的無線傳感器網絡定位算法與極大似然估計算法、最小二乘法等傳統算法相比,定位精度更高,但易陷入局部最優。針對上述缺點,將一種帶有動態擾動項的改進算法引入無線傳感器網絡定位,并在目標函數中引入加權因子,以削弱測距誤差的影響。仿真結果表明,該算法可以加快收斂速度,提高定位精度。

關鍵詞無線傳感器網絡; 粒子群優化算法; 動態擾動項; 定位精度

Class NumberTP393

1引言

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

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

2粒子群優化算法

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

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

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

(1)

(2)

(3)

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

3改進的粒子群優化算法

3.1迭代公式的改進

針對粒子群算法后期易陷入局部最優的缺陷,結合無線傳感器網絡硬件資源受限的實際情況,本文采用一種帶有動態擾動項的粒子群優化算法(Particle Swarm Optimization Dynamic Disturbance Term,PSO-DDT)。該算法的速度更新公式變為如下:

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

(4)

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

3.2適應度函數設定

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

(5)

(6)

其中,λi為加權因子,0<λi<1;f為一常數,0

3.3算法描述

無線傳感器網絡的錨節點相當于該算法中的粒子,盲節點的坐標即是粒子要搜索的位置,算法的具體實現流程如下。

1) 初始化粒子種群,種群大小為錨節點數目M。粒子的初始位置為各錨節點的位置,隨機設置粒子初速度。計算出各粒子的適應度值,將適應度值最小的粒子的位置設為全局最優位置,將每個粒子的位置設為個體最優位置。

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

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

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

5) 輸出全局最優位置和終止迭代次數。

4實驗仿真與分析

4.1仿真參數設定

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

4.2結果分析

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

圖1　節點定位仿真圖

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

圖2　算法的收斂曲線

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

圖3　平均定位誤差與平均測距誤差的關系

5結語

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

參 考 文 獻

[1] 崔莉,鞠海玲,苗勇.無線傳感器網絡研究進展[J].計算機研究與發展,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] 劉雨.無線傳感器網絡中的信息處理[D].北京:北京郵電大學,2006:1-2.

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

[3] 趙仕俊,唐懿芳.無線傳感器網絡[M].北京:科學出版社,2013:89-108.

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

[4] 李曉維,徐勇軍,任豐源.無線傳感器網絡技術[M].北京:北京理工大學出版社,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] 彭宇,王丹.無線傳感器網絡定位技術綜述[J].電子測量與儀器學報,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] 王曉樂,徐家品.基于粒子群優化算法的WSNs節點定位研究[J].計算機應用,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] 陳志奎,司威.傳感器網絡的粒子群優化定位算法[J].通信技術,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] 高瑋,尹志喜.現代智能仿生算法及其應用[M].北京:科學出版社,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日

作者簡介:張先超,男,碩士研究生,研究方向:無線傳感器網絡節點定位技術。劉興長,男,博士,教授,碩士生導師,研究方向:無線傳感器網絡。

中圖分類號TP393

DOI:10.3969/j.issn.1672-9722.2016.05.016