陳玲君

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

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

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

　　中圖分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：ADOI： 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.

0引言

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

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

1基本算法描述

　　1.1DV-Hop算法

　　DVHop節(jié)點(diǎn)定位算法只需要包含少量的錨節(jié)點(diǎn),通過(guò)定位算法來(lái)確定未知節(jié)點(diǎn)的位置,它具有不需要通過(guò)具體測(cè)量距離、硬件要求低等優(yōu)點(diǎn),特別適合在硬件條件有限的無(wú)線傳感網(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)會(huì)根據(jù)其他錨節(jié)點(diǎn)的坐標(biāo)信息和跳數(shù)估算網(wǎng)絡(luò)平均跳距距離,采用公式(1)表示。

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

　　錨節(jié)點(diǎn)將平均跳距發(fā)送到整個(gè)網(wǎng)絡(luò)后,未知節(jié)點(diǎn)僅記錄所收到的第一個(gè)平均跳距,通過(guò)公式(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)所示的方程。

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

　　L=(ATA)－1ATb(5)

　　1.2粒子群算法

　　粒子群算法是一種模擬鳥群在覓食過(guò)程中的遷徙的一種群集行為的算法,假設(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］之間的隨機(jī)數(shù),k為迭代次數(shù),ω為慣性權(quán)值。

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

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

　　2.1粒子之間的平均距離

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

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

　　2.2雙變異因子

　　本文基于對(duì)文獻(xiàn)［11］的研究，結(jié)合遺傳算法的變異概念，提出了雙變異因子來(lái)對(duì)目標(biāo)粒子進(jìn)行跟隨,雙變異因子由最優(yōu)因子Ybest和惰性因子Yworst組成,前者主要用來(lái)跟隨每次迭代中的適應(yīng)度函數(shù)值最優(yōu)的粒子,后者主要是用來(lái)跟隨每次迭代中適應(yīng)度函數(shù)值最差的粒子。當(dāng)進(jìn)行迭代的時(shí)候?qū)蓚€(gè)因子進(jìn)行高速變異,對(duì)最優(yōu)因子采用公式(9)進(jìn)行變異,這樣有利于在局部最優(yōu)解的附近的范圍內(nèi)提高搜索精度,對(duì)惰性因子跟蹤的粒子按照公式(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,通過(guò)權(quán)重因子的調(diào)整來(lái)降低粒子在全局和局部最優(yōu)中調(diào)節(jié)粒子的速度,從而保證粒子能夠獲得最優(yōu)解。

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

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

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

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

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

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

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,測(cè)距誤差為εi,那么|ri－di|<εi,i=1,2,…，n。根據(jù)式(2)可知,(x,y)應(yīng)該滿足如下約束條件：

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

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

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

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

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

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

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

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

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

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

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

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

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

　　為了說(shuō)明本文算法在節(jié)點(diǎn)定位中具有的有效性,本文選擇在MATLAB2010平臺(tái)上進(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ī)分布在邊長(zhǎng)為100 m的區(qū)域中,錨節(jié)點(diǎn)和未知節(jié)點(diǎn)的坐標(biāo)位置隨機(jī)產(chǎn)生。將DVHop算法和本文算法在錨節(jié)點(diǎn)數(shù)量和測(cè)距誤差兩個(gè)方面進(jìn)行對(duì)比。

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

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

　　4.2測(cè)距誤差下的定位性能比較

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

5結(jié)論

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

參考文獻(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.

　?。?］ 魏玉宏,田杰,高志強(qiáng).基于混合粒子群優(yōu)化的DVHop定位算法［J］.計(jì)算機(jī)測(cè)量與控制,2015,23(12):42144216.

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

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

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

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

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

　?。?］ 江濤.基于混合人工蜂群策略的改進(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

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