基于改進(jìn)的粒子群算法在WSN節(jié)點(diǎn)定位中的研究*

陳玲君

(紹興職業(yè)技術(shù)學(xué)院,浙江 紹興 312000)

基于改進(jìn)的粒子群算法在WSN節(jié)點(diǎn)定位中的研究*

陳玲君

(紹興職業(yè)技術(shù)學(xué)院,浙江 紹興 312000)

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

DV-Hop算法;定位精度；估計(jì)誤差

0 引言

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

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

1 基本算法描述

1.1 DV-Hop算法

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

(1)錨節(jié)點(diǎn)在通信網(wǎng)絡(luò)范圍內(nèi)向鄰居節(jié)點(diǎn)發(fā)送自己的位置信息。接收節(jié)點(diǎn)記錄該節(jié)點(diǎn)到每個(gè)錨節(jié)點(diǎn)之間的最小跳數(shù),同時(shí)刪除同一個(gè)錨節(jié)點(diǎn)發(fā)送的最大跳數(shù)信息,然后跳數(shù)值加1，繼續(xù)轉(zhuǎn)發(fā)個(gè)下一個(gè)鄰居節(jié)點(diǎn)。

(2)每一個(gè)錨節(jié)點(diǎn)會根據(jù)其他錨節(jié)點(diǎn)的坐標(biāo)信息和跳數(shù)估算網(wǎng)絡(luò)平均跳距距離,采用公式(1)表示。

(1)

式中,hopSij表示錨節(jié)點(diǎn)i和j之間的跳數(shù)。

錨節(jié)點(diǎn)將平均跳距發(fā)送到整個(gè)網(wǎng)絡(luò)后,未知節(jié)點(diǎn)僅記錄所收到的第一個(gè)平均跳距,通過公式(2)估算未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離:

Li=Si×HopSize

(2)

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

(3)

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

(4)

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

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

L=(ATA)-1ATb

(5)

1.2 粒子群算法

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

(6)

(7)

式中,c1和c2分別為加速系數(shù),r1和r2為[0,1]之間的隨機(jī)數(shù),k為迭代次數(shù),ω為慣性權(quán)值。

粒子群算法具有算法結(jié)構(gòu)簡單、容易實(shí)現(xiàn)等優(yōu)點(diǎn),缺點(diǎn)是算法粒子容易發(fā)生早熟,易陷入局部最優(yōu)。為了能夠更好地實(shí)現(xiàn)粒子群算法在DV-Hop中的定位，本文對粒子群算法進(jìn)行優(yōu)化,使得優(yōu)化后的粒子群算法能夠解決粒子群算法陷入局部最優(yōu)的缺陷,為節(jié)點(diǎn)定位提供理論支持。

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

2.1 粒子之間的平均距離

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

(8)

2.2 雙變異因子

本文基于對文獻(xiàn)[11]的研究，結(jié)合遺傳算法的變異概念，提出了雙變異因子來對目標(biāo)粒子進(jìn)行跟隨,雙變異因子由最優(yōu)因子Ybest和惰性因子Yworst組成,前者主要用來跟隨每次迭代中的適應(yīng)度函數(shù)值最優(yōu)的粒子,后者主要是用來跟隨每次迭代中適應(yīng)度函數(shù)值最差的粒子。當(dāng)進(jìn)行迭代的時(shí)候?qū)蓚€(gè)因子進(jìn)行高速變異,對最優(yōu)因子采用公式(9)進(jìn)行變異,這樣有利于在局部最優(yōu)解的附近的范圍內(nèi)提高搜索精度,對惰性因子跟蹤的粒子按照公式(10)進(jìn)行變異,這樣有利于擴(kuò)大種群的范圍,持續(xù)更新種群的“生命力”。

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

(9)

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

(10)

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

2.3 權(quán)重因子的設(shè)置

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

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

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

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

(12)

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

權(quán)重系數(shù)通過線性遞減策略改進(jìn)后,算法的性能已經(jīng)有了很大的提高,但由于線性遞減策略自身的特性導(dǎo)致算法容易陷入局部最優(yōu),因此采用非線性策略來解決局部最優(yōu)解:

(13)

3 基于改進(jìn)的粒子群算法在節(jié)點(diǎn)定位中的研究

3.1 節(jié)點(diǎn)定位誤差分析

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

(14)

求解(x,y)使得

(15)

式中如果f(x,y)的值最小,則未知節(jié)點(diǎn)的解與真實(shí)值之間的偏差就最小,而此時(shí)的坐標(biāo)(x,y)為最優(yōu)解,即滿足下式的未知節(jié)點(diǎn)坐標(biāo)。

fitness(x,y)

(16)

式(16)是一個(gè)非線性最優(yōu)化問題,因此將它作為粒子群的目標(biāo)函數(shù),通過改進(jìn)的粒子群算法來提高整個(gè)粒子群之間的信息交流能力,求出最優(yōu)解,從而實(shí)現(xiàn)未知節(jié)點(diǎn)坐標(biāo)的計(jì)算。

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

(1)通過分析,將無線傳感網(wǎng)中的節(jié)點(diǎn)定位問題轉(zhuǎn)換為非線性優(yōu)化問題。

(2)設(shè)置粒子群算法的相關(guān)參數(shù) 。

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

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

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

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

(7)每個(gè)粒子位置與所在子群的歷史最位置 Pkg進(jìn)行比較,選擇出種群的最優(yōu)位置Pkg。

(8)當(dāng)次數(shù)達(dá)到最大迭代次數(shù),算法循環(huán)截止,計(jì)算每個(gè)子群的最優(yōu)位置對應(yīng)的適應(yīng)度值,選取整個(gè)子群對應(yīng)的最優(yōu)位置為pg=min(P1g,P2g,…，Pkg,…，PNg)；否則轉(zhuǎn)至步驟(4)繼續(xù)迭代。

(9)輸出pg對應(yīng)粒子的坐標(biāo)作為待定位的傳感器定點(diǎn)坐標(biāo)。

4 仿真實(shí)驗(yàn)

為了說明本文算法在節(jié)點(diǎn)定位中具有的有效性,本文選擇在MATLAB2010平臺上進(jìn)行仿真實(shí)驗(yàn)。選擇計(jì)算機(jī)硬件配置為:酷睿i3 CPU,4GB DDR3內(nèi)存,500 GB硬盤;軟件環(huán)境為Windows Xp。選取250個(gè)節(jié)點(diǎn)隨機(jī)分布在邊長為100 m的區(qū)域中,錨節(jié)點(diǎn)和未知節(jié)點(diǎn)的坐標(biāo)位置隨機(jī)產(chǎn)生。將DV-Hop算法和本文算法在錨節(jié)點(diǎn)數(shù)量和測距誤差兩個(gè)方面進(jìn)行對比。

4.1 錨節(jié)點(diǎn)數(shù)量下的比較

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

圖1 粒子群算法與本文算法的在錨節(jié)點(diǎn)定位誤差變化曲線

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

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

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

5 結(jié)論

本文分析WSN中基于DV-Hop定位算法精度低的原因,提出一種基于粒子群的DV-Hop算法，通過對粒子群算法的改進(jìn),使得算法的性能得到提高。將改進(jìn)后的算法運(yùn)用到了節(jié)點(diǎn)定位中，仿真實(shí)驗(yàn)結(jié)果表明,相比于DV-Hop 算法,本文算法在定位精度方面具有明顯優(yōu)勢,是一種簡單實(shí)用的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位方法。

[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] 魏玉宏,田杰,高志強(qiáng).基于混合粒子群優(yōu)化的DV-Hop定位算法[J].計(jì)算機(jī)測量與控制,2015,23(12):4214-4216.

[4] 歐陽丹彤,何金勝,白洪濤.一種約束粒子群優(yōu)化的無線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位算法[J].計(jì)算機(jī)科學(xué),2011,38(7):46-50.

[5] 夏少波.無線傳感器網(wǎng)絡(luò)DV-Hop定位算法的改進(jìn)[J].計(jì)算機(jī)應(yīng)用,2015,35(2):340-344.

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

[7] 周彥,文寶,李建勛.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)近點(diǎn)加權(quán)質(zhì)心定位方法[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(1):87-89.

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

[9] 江濤.基于混合人工蜂群策略的改進(jìn)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

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

2016-07-29)

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