基于改進的粒子群算法在WSN節點定位中的研究*

陳玲君

(紹興職業技術學院,浙江 紹興 312000)

基于改進的粒子群算法在WSN節點定位中的研究*

陳玲君

(紹興職業技術學院,浙江 紹興 312000)

如何能夠減小無線傳感中的節點定位誤差一直都是研究的熱點。提出一種基于改進的粒子群優化算法以修正DV-Hop誤差的傳感器節點定位方法,通過分析粒子間距離、雙變異因子和權重設置改進了粒子群算法,改進后的粒子群算法減少了未知節點與錨節點間距離的估計誤差。仿真實驗表明，相對于DV-HOP算法,本文的算法可以有效地提高傳感器節點定位精度。

DV-Hop算法;定位精度；估計誤差

0 引言

如何能夠在無線傳感網中進行節點定位一直都是研究的熱點,目前大多數的研究都是基于通過錨節點來計算相關未知節點的定位研究[1-2]。國內外學者對此進行了不斷深入的研究。DV-Hop是一種應用最廣泛的免測距方法,針對其定位精度較低的問題,許多學者對其進行了改進。文獻[3-4]利用改進的粒子群優化算法對DV-Hop算法的位置估計進行校正,并利用該算法進行求解。文獻[5]從兩個方面提出改進:一是基于節點的通信半徑對節點間的跳數進行修正;二是借助信標節點間的估計距離與實際距離的偏差對平均每跳的跳距進行修正,仿真實驗取得了比較好的效果。文獻[6-7]提出將加權運用到無線傳感網的節點定位中,取得了比較好的效果。文獻[8-9]提出采用其他的人工智能算法求解無線傳感網中的節點定位算法,取得了一定的效果。

為了能夠更好地提高節點定位的效果,本文首先描述了基本的定位算法,其次對粒子群算法進行了改進,分析了節點定位誤差的原因,采用改進的粒子群算法對DV-Hop算法定位誤差進行修正,最后通過仿真說明本文改進算法取得的效果。

1 基本算法描述

1.1 DV-Hop算法

DV-Hop節點定位算法只需要包含少量的錨節點,通過定位算法來確定未知節點的位置,它具有不需要通過具體測量距離、硬件要求低等優點,特別適合在硬件條件有限的無線傳感網中的應用,具體的算法步驟如下:

(1)錨節點在通信網絡范圍內向鄰居節點發送自己的位置信息。接收節點記錄該節點到每個錨節點之間的最小跳數,同時刪除同一個錨節點發送的最大跳數信息,然后跳數值加1，繼續轉發個下一個鄰居節點。

(2)每一個錨節點會根據其他錨節點的坐標信息和跳數估算網絡平均跳距距離,采用公式(1)表示。

(1)

式中,hopSij表示錨節點i和j之間的跳數。

錨節點將平均跳距發送到整個網絡后,未知節點僅記錄所收到的第一個平均跳距,通過公式(2)估算未知節點與錨節點的距離:

Li=Si×HopSize

(2)

(3)設P1(x1,y1),P2(x2,y2),…,Pn(xn,yn)表示n個錨節點的坐標位置,待定位節點D的位置為(x,y),其與錨節點的估計距離分別為d1,d2,…,dn，可以建立式(3)所示的方程。

(3)

每一個方程減去最后一個方程,得到如下公式:

(4)

使用線性方程組表示AL=b:

在實際的測距過程中,會產生一些不確定誤差,因此線性方程組應該將誤差考慮進去,變成AL+N=b,N為隨機誤差向量,通過最小二乘法得到的解為:

L=(ATA)-1ATb

(5)

1.2 粒子群算法

粒子群算法是一種模擬鳥群在覓食過程中的遷徙的一種群集行為的算法,假設在d維的空間搜索,粒子i的速度和位置分別為vi=(vi1,vi2,…,vid)和xi=(xi1,xi2,…,xid)粒子i自身的歷史最優位置為pi=(pi1,pi2,…,pid),種群歷史的最優位置為pg=(pg1,pg2,…，pgd),其速度和位置更新方式為:

(6)

(7)

式中,c1和c2分別為加速系數,r1和r2為[0,1]之間的隨機數,k為迭代次數,ω為慣性權值。

粒子群算法具有算法結構簡單、容易實現等優點,缺點是算法粒子容易發生早熟,易陷入局部最優。為了能夠更好地實現粒子群算法在DV-Hop中的定位，本文對粒子群算法進行優化,使得優化后的粒子群算法能夠解決粒子群算法陷入局部最優的缺陷,為節點定位提供理論支持。

2 改進的粒子群算法

2.1 粒子之間的平均距離

根據文獻[10]研究發現,粒子群算法的早熟收斂問題與種群的多樣性密切相關,粒子群算法在后期的執行過程中,整個過種群多樣性會逐步收斂,種群的多樣性也在不斷地喪失。本文采用粒子間的平均距離來衡量種群的多樣性,如下:

(8)

2.2 雙變異因子

本文基于對文獻[11]的研究，結合遺傳算法的變異概念，提出了雙變異因子來對目標粒子進行跟隨,雙變異因子由最優因子Ybest和惰性因子Yworst組成,前者主要用來跟隨每次迭代中的適應度函數值最優的粒子,后者主要是用來跟隨每次迭代中適應度函數值最差的粒子。當進行迭代的時候對兩個因子進行高速變異,對最優因子采用公式(9)進行變異,這樣有利于在局部最優解的附近的范圍內提高搜索精度,對惰性因子跟蹤的粒子按照公式(10)進行變異,這樣有利于擴大種群的范圍,持續更新種群的“生命力”。

Yworsti+1=Yworsti(1+0.621*random)

(9)

Ybesti+1=Ybesti(1+0.5*random)

(10)

其中,random∈Gauss(0,1)。

2.3 權重因子的設置

為了保證粒子群算法具有很好的收斂性,本文提出了在粒子速度上引入權重因子w,通過權重因子的調整來降低粒子在全局和局部最優中調節粒子的速度,從而保證粒子能夠獲得最優解。

(1)全局解-線性微分策略

在粒子群算法中,伴隨著迭代次數的不斷增加,粒子的速度會呈現不同的變化,本文采用典型的線性遞減策略,權重系數根據迭代次數的更新如下:

(11)式中,wmin表示權值系數的最小值,T為最大迭代次數,t為當前迭代次數。通過使用比較大的慣性權重能夠快速定位最優解,伴隨著算法的迭代次數不斷增大,粒子的速度逐漸減慢,收斂速度加快,算法性能提高,但在算法的初始階段,會隨著慣性權值的減少,搜索能力逐漸變弱,因此局部搜索能力變強,促使算法陷入局部最優。為了避免這種情況的發生,使用如下微分遞減的策略來進行慣性權重的更新:

(12)

(2)局部解-非線性策略

權重系數通過線性遞減策略改進后,算法的性能已經有了很大的提高,但由于線性遞減策略自身的特性導致算法容易陷入局部最優,因此采用非線性策略來解決局部最優解:

(13)

3 基于改進的粒子群算法在節點定位中的研究

3.1 節點定位誤差分析

設錨節點(xi,yi)(i=1,2,…,n)與未知節點(x,y)的實際距離為ri,i=1,2,…,n,測距誤差為εi,那么|ri-di|<εi,i=1,2,…，n。根據式(2)可知,(x,y)應該滿足如下約束條件：

(14)

求解(x,y)使得

(15)

式中如果f(x,y)的值最小,則未知節點的解與真實值之間的偏差就最小,而此時的坐標(x,y)為最優解,即滿足下式的未知節點坐標。

fitness(x,y)

(16)

式(16)是一個非線性最優化問題,因此將它作為粒子群的目標函數,通過改進的粒子群算法來提高整個粒子群之間的信息交流能力,求出最優解,從而實現未知節點坐標的計算。

3.2 粒子群算法的修正誤差的步驟

(1)通過分析,將無線傳感網中的節點定位問題轉換為非線性優化問題。

(2)設置粒子群算法的相關參數 。

(3)計算每一個粒子的速度和位置,并根據式(15)計算其適應度值,將適應度最大的對應的粒子的位置保存pi中,將子群體的最優位置保存到Pkg(表示第 k個子群的最優位置)中。

(4)根據式(8)計算當前粒子群的粒子之間的平均距離averagedistance,根據公式(9)和(10)對粒子進行變異。

(5)根據公式(10)和公式(11)計算權重,從而代入式(6)和(7)進行計算。

(6)每個粒子位置與自身的歷史最優位置pi對比,選擇出最優的粒子位置。

(7)每個粒子位置與所在子群的歷史最位置 Pkg進行比較,選擇出種群的最優位置Pkg。

(8)當次數達到最大迭代次數,算法循環截止,計算每個子群的最優位置對應的適應度值,選取整個子群對應的最優位置為pg=min(P1g,P2g,…，Pkg,…，PNg)；否則轉至步驟(4)繼續迭代。

(9)輸出pg對應粒子的坐標作為待定位的傳感器定點坐標。

4 仿真實驗

為了說明本文算法在節點定位中具有的有效性,本文選擇在MATLAB2010平臺上進行仿真實驗。選擇計算機硬件配置為:酷睿i3 CPU,4GB DDR3內存,500 GB硬盤;軟件環境為Windows Xp。選取250個節點隨機分布在邊長為100 m的區域中,錨節點和未知節點的坐標位置隨機產生。將DV-Hop算法和本文算法在錨節點數量和測距誤差兩個方面進行對比。

4.1 錨節點數量下的比較

設定錨節點所占的比例不超過10%,即不超過25, DV-Hop算法和本文算法錨節點數量與定位誤差變化曲線如圖1所示。從圖1可知,伴隨著錨節點個數的不斷增大,兩種算法的平均定位誤差均逐漸減小,本文算法的定位誤差明顯小于 DV-Hop算法的定位誤差,減少了19.17%。

圖1 粒子群算法與本文算法的在錨節點定位誤差變化曲線

4.2 測距誤差下的定位性能比較

在實際的定位中測距誤差是無法避免的,DV-Hop 算法和本文算法定位誤差變化和測距誤差的關系曲線如圖2所示。從圖2可知,隨著測距誤差的不斷增多,兩種算法的定位誤差逐漸增大,相對于Dv-Hop算法而言,本文算法的定位誤差分別減少了9.25%。

圖2 粒子群算法與本文算法的測距誤差變化曲線

5 結論

本文分析WSN中基于DV-Hop定位算法精度低的原因,提出一種基于粒子群的DV-Hop算法，通過對粒子群算法的改進,使得算法的性能得到提高。將改進后的算法運用到了節點定位中，仿真實驗結果表明,相比于DV-Hop 算法,本文算法在定位精度方面具有明顯優勢,是一種簡單實用的無線傳感器網絡節點定位方法。

[1] Li Mo,Liu Yunhao. Rendeved path: range-free localization in anisotropic sensornetworks with holes[J].IEEE/ACM Transactions on Networking,2010,18(1):320-332.

[2] LAZOS L,POOVENDRAN R.High-resolution robust localization for wireless sensor networks[J].IEEE Journal on Selected Areas in Communications,2006,24(2):233-246.

[3] 魏玉宏,田杰,高志強.基于混合粒子群優化的DV-Hop定位算法[J].計算機測量與控制,2015,23(12):4214-4216.

[4] 歐陽丹彤,何金勝,白洪濤.一種約束粒子群優化的無線傳感網絡節點定位算法[J].計算機科學,2011,38(7):46-50.

[5] 夏少波.無線傳感器網絡DV-Hop定位算法的改進[J].計算機應用,2015,35(2):340-344.

[6] 周杭霞,崔晨,葉佳駿.一種基于加權處理和誤差修的DV-Hop定位算法研究[J].傳感技術學報,2014,27(12):1699-1703.

[7] 周彥,文寶,李建勛.無線傳感器網絡節點近點加權質心定位方法[J].計算機工程與應用,2012,48(1):87-89.

[8] 程超,錢志鴻,付彩欣.一種基于誤差距離加權與跳段算法選擇的遺傳優化DV-Hop定位算法[J].電子與信息學報,2015,37(10):2418-2422.

[9] 江濤.基于混合人工蜂群策略的改進DV-Hop定位算法[J],電子器件,2014,37(5):912-915.

[10] LIU F, LIU G Z.Markov chain analysis and the convergence speed of genetic algorithms[J].Systems Engineering Journal,1998, 13(4): 79-85

[11] Xue Wentao, Wu Xiaobei, Xu Zhiliang. An immune network algorithm based on double mutation operators[J]. Controland Decision,2008,23(12):1417-1422.

Research of improved particle swarm algorithm in WSN node positioning

Chen Lingjun

(Shaoxing Vocational & Technical College,Shaoxing 312000, China)

How to reduce errors of positioning nodes in wireless sensing has always been the research hotspot. This paper proposes an improved particle swarm optimization algorithm to modify the DV-Hop error sensor node positioning methods, and improve the particle swarm algorithm through analyzing distance between particles, double mutation factors and weight setting. The improved particle swarm algorithm can reduce the estimated errors between unknown nodes and anchors, and simulation experiment shows that compared with DV-HOP algorithm, algorithm in this paper can effectively improve the efficiency of sensors in positioning nodes.

DV-Hop algorithm; positioning efficiency; estimated errors

浙江省教育廳科研課題(Y201534905)

TP393

A

10.19358/j.issn.1674- 7720.2016.24.020

陳玲君. 基于改進的粒子群算法在WSN節點定位中的研究[J].微型機與應用，2016,35(24)：70-72，76.

2016-07-29)

陳玲君(1983-),女,碩士,講師,主要研究方向：智能控制。