陳玲君

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

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

　　關(guān)鍵詞：DV-Hop算法;定位精度；估計誤差

　　中圖分類號：TP393文獻(xiàn)標(biāo)識碼：ADOI： 10.19358/j.issn.1674-7720.2016.24.020

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

0引言

　　如何能夠在無線傳感網(wǎng)中進(jìn)行節(jié)點定位一直都是研究的熱點,目前大多數(shù)的研究都是基于通過錨節(jié)點來計算相關(guān)未知節(jié)點的定位研究［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ìn)行校正,并利用該算法進(jìn)行求解。文獻(xiàn)［5］從兩個方面提出改進(jìn):一是基于節(jié)點的通信半徑對節(jié)點間的跳數(shù)進(jìn)行修正;二是借助信標(biāo)節(jié)點間的估計距離與實際距離的偏差對平均每跳的跳距進(jìn)行修正,仿真實驗取得了比較好的效果。文獻(xiàn)［67］提出將加權(quán)運用到無線傳感網(wǎng)的節(jié)點定位中,取得了比較好的效果。文獻(xiàn)［89］提出采用其他的人工智能算法求解無線傳感網(wǎng)中的節(jié)點定位算法,取得了一定的效果。

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

1基本算法描述

　　1.1DV-Hop算法

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

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

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

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

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

　　Li=Si×HopSize(2)

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

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

　　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),其速度和位置更新方式為:

　　vk+1id=ωkid+c1r1(pid－xk+1id)+c2r2(pgd－xkid)(6)

　　xk+1id=xkid+vk+1id(7)

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

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

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

　　2.1粒子之間的平均距離

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

　　式中,m表示種群中的粒子的數(shù)目,D表示空間的維數(shù),Lmax表示粒子群空間的半徑,pij表示第i個粒子在第j維空間變量,pj是所有粒子在第j維空間變量中的平均值。

　　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)行迭代的時候?qū)蓚€因子進(jìn)行高速變異,對最優(yōu)因子采用公式(9)進(jìn)行變異,這樣有利于在局部最優(yōu)解的附近的范圍內(nèi)提高搜索精度,對惰性因子跟蹤的粒子按照公式(10)進(jìn)行變異,這樣有利于擴大種群的范圍,持續(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ù)的更新如下:

　　w(t)=wmin+wT×t(11)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4仿真實驗

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

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

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

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

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

5結(jié)論

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

參考文獻(xiàn)

　?。?］ 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.

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

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

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

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

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

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

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

　?。?0］ LIU F, LIU G Z.Markov chain analysis and the convergence speed of genetic algorithms［J］.Systems Engineering Journal,1998, 13(4): 79 85

　?。?1］ Xue Wentao, Wu Xiaobei, Xu Zhiliang. An immune network algorithm based on double mutation operators［J］. Controland Decision,2008,23(12):1417 1422.