傅彬

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

       摘要：針對無線傳感網(wǎng)中的節(jié)點定位問題,采用RSSI測距技術(shù)測量未知節(jié)點之間的距離,并采用粒子群算法進行優(yōu)化,針對粒子群算法的不足,首先通過引入動態(tài)擾動因子和懲罰函數(shù)提高算法的性能,其次采用距離誤差修正和修正定位誤差模型來優(yōu)化節(jié)點定位的效果。通過仿真實驗將所提算法與基本粒子群算法進行比較,結(jié)果表明所提算法在算法的收斂性能和定位精度上取得了比較好的效果,提高了節(jié)點的定位效果。

　　關(guān)鍵詞：無線傳感網(wǎng)；動態(tài)擾動因子；懲罰函數(shù)

　　中圖分類號：TP393文獻標識碼：ADOI： 10.19358/j.issn.1674-7720.2017.08.020

　　引用格式：傅彬.一種改進的粒子群算法在WSN中的定位研究［J］.微型機與應用，2017,36（8）：63-66.

0引言

　　無線傳感網(wǎng)中的節(jié)點定位是衡量無線傳感網(wǎng)絡(luò)數(shù)據(jù)傳輸效率高低的一個重要標準［1］。節(jié)點定位不但受到自然界中客觀條件的影響,還容易受到來自自身節(jié)點傳輸信號強弱、傳輸距離以及節(jié)點能量等條件的限制,因此如何進行節(jié)點定位的優(yōu)化一直都是學者們不斷研究的方向。國內(nèi)外學者從不同的角度對節(jié)點定位提出了自己的研究方向。文獻［2］提出一種基于小波支持向量機(WSVM)的定位算法,取得了比較好的定位效果;文獻［3］從全網(wǎng)平均每跳距離角度出發(fā),分析每個信標節(jié)點的平均每跳距離誤差,有效地提高了節(jié)點定位精度;文獻［4］提出一種基于接收信號強度指示測距的蒙特卡羅盒定位算法;文獻［5］提出采用人工蜂群算法來修正最小二乘定位誤差的傳感器節(jié)點定位算法,該算法能夠有效地提高無線傳感器節(jié)點的定位精度;文獻［6］提出了一種改進粒子群算法與DVHop的融合算法。

　　本文在以上研究的基礎(chǔ)上,采用粒子群算法對使用RSSI測距技術(shù)的節(jié)點之間的距離進行優(yōu)化,通過對粒子群算法采用動態(tài)擾動因子、懲罰函數(shù)、誤差修正和修正定位模型等方法提高算法的性能,提高算法定位的效果。

1接收信號強度(RSSI)

　　在真實的無線傳感網(wǎng)中，硬件設(shè)備是非常重要的必備工具，其優(yōu)點是設(shè)計簡單，缺點是處理能力有限,因此需要布置大量的傳感器。而RSSI測距技術(shù)不需要復雜的硬件設(shè)備,它僅僅依靠節(jié)點發(fā)射信號的功率與接收信號功率之間的差值來初步估算兩點之間的損耗,并轉(zhuǎn)換為兩個節(jié)點之間的距離,計算公式模型如下:

　　PR(d)=PtGtGrλ2/16π2d2L(1)

　　式中,PR(d)表示接收節(jié)點與發(fā)射節(jié)點相距d的功率,Pt為發(fā)射節(jié)點的功率,Gt、Gr分別為發(fā)射節(jié)點和接收節(jié)點的增益,L為損耗定量,d為距離,λ為波長。

　　理論研究中，無線傳感網(wǎng)中的節(jié)點定位模型都是在假設(shè)一定理論條件成立的情況下建立的,但在實際情況中,無線傳感網(wǎng)絡(luò)可能受到來自自然界中的溫度、濕度、障礙物等影響,網(wǎng)絡(luò)中傳輸?shù)男盘柨隙〞艿讲煌潭鹊挠绊?因此采用RSSI測量獲得的節(jié)點的估計距離和真實距離具有一定的差距。因此如何降低誤差成為了研究的主要方向。

2改進的粒子群算法

　　2.1粒子群算法簡述

　　在一個D維的搜索空間中,種群由M個粒子組成,其中第i個粒子的位置為Xi=［xi1,xi2,…xiD］,飛行速度為Vi=［vi1,vi2,…，viD］,設(shè)定Pi是第i個粒子當前搜索的個體最佳位置,Pi=［pi1,pi2,…，pID］；Pg為當前搜索到的全局最優(yōu)位置,Pg=［pg1,pg2,…，pgD］,因此粒子的位置和速度的調(diào)整方向如下:

　　Vk+1id=ωVkid+c1r1(Pid－Xkid)+c2r2(Pgd－Xkid)(2)

　　Xk+1id=Xkid+Vk+1id(3)

　　式中的k為迭代次數(shù)；r1和r2是0~1之間的隨機數(shù),用來保持種群具有的多樣性；ω為慣性權(quán)重值；c1和c2是學習因子,用來掌握粒子個體的最優(yōu)位置以及整個粒子群中的全局最優(yōu)位置,合理地調(diào)節(jié)算法,提高算法的收斂速度。在粒子群算法中，對每一個粒子的個體來說,個體最優(yōu)解Pi和粒子全局最優(yōu)解Pg的更新如下:

　　Pk+1i=Xk+1i,f(Xk+1i)≤f(Pki)

　　Pki,其他 (4)

　　f(Pg)=min［f(Pi)］(5)

　　2.2改進的粒子群算法

　　文獻［7］證明粒子群算法在進化過程中與粒子的速度沒有直接的關(guān)系,因此將粒子群優(yōu)化算法的位置更新簡化為如下形式:

　　Xk+1id=ωVkid+c1r1(Pid－Xkid)+c2r2(Pgd－Xkid)(6)

　　2.2.1引入動態(tài)擾動因子

　　公式(6)雖然進行了簡化,但仍然可以發(fā)現(xiàn)該算法具有收斂速度快、容易陷入局部最優(yōu)解的可能。為了解決這個問題,首先引入擾動因子概念,當個體的最優(yōu)解和全局最優(yōu)解停滯的時候,使用擾動因子對其進行擾動,使得算法遠離當前搜索區(qū)域,向其他區(qū)域擴散。因此擾動因子設(shè)置如下:

　　rt0>T03=1,t0≤T0

　　U(0,1),t0>T0 (7)

　　rtg>Tg4=1,tg≤Tg

　　U(0,1),tg>Tg(8)

　　式中,t0和tg分別表示個體最優(yōu)解和全局最優(yōu)解的停滯次數(shù),而T0和Tg分別對應個體最優(yōu)解和全局最優(yōu)解的停滯的閾值。

　　從以上分析中發(fā)現(xiàn)，當t0>T0,tg>Tg的時候,算法停滯,當算法再次執(zhí)行的時候只有在局部獲得最優(yōu)值后才可以執(zhí)行,從而可以對當前個體極值和全局極值進行擾動,因此算法必須停滯T0或者Tg步之后才能進行下一次迭代運算。雖然設(shè)置了擾動因子，但存在兩個問題：一個問題是加速了節(jié)點定位過程中節(jié)點產(chǎn)生的額外消耗,從而降低傳感器的壽命；另一個問題是擾動因子有可能讓算法從一個局部最優(yōu)收斂到另一個局部最優(yōu),這樣降低了算法的時間效率和空間效率。因此為了避免以上出現(xiàn)的問題,針對式(7)和式(8)提出了動態(tài)擾動因子的概念,如下:

　　式中,rand1()是一個(0,1)之間的隨機數(shù),rand2()是一個(1, kmax)之間的隨機數(shù),k為當前迭代次數(shù),kmax為最大迭代次數(shù)。因此公式(6)的變化如下:

　　Xk+1id=ωVkid+c1r1(d1Pid－Xkid)+c2r2(d2Pgd－Xkid)(11)

　　2.2.2懲罰函數(shù)

　　粒子群算法的最優(yōu)解的確定是算法的關(guān)鍵,而可行解都需要加上一定的約束條件,為了盡可能地縮小最優(yōu)解的搜索范圍,避免算法進行不相關(guān)的盲目搜索,降低算法搜索時間,需要將粒子產(chǎn)生最優(yōu)解問題轉(zhuǎn)換為無約束的優(yōu)化問題。當粒子滿足約束條件的時候,懲罰值會很??；反之,則會很大。對于不滿足約束條件的粒子賦予數(shù)值較大的懲罰函數(shù)數(shù)值,這樣可以有效地降低目標函數(shù),后續(xù)的粒子就會遠離無解的區(qū)域。

　　粒子群算法中的粒子最優(yōu)解獲得是在一定約束條件下使得某個度量值達到最小。記f為表示問題的目標函數(shù),A為可行解,gi(x)為約束域,得到:

　　minf(x),x∈A

　　A={x|gi(x)≥0,i=1,2,…，m}(12)

　　將公式(12)中的不等式約束轉(zhuǎn)換為等式約束問題:

　　minf(x),x∈A

　　s.t.min(0,gi(x))=0(13)

　　設(shè)p(x)=∑mi=1［min(0,gi(x))］2,因此將式(13)轉(zhuǎn)換為無約束函數(shù)：

　　F(x,M)=f(x)+Mp(x)=f(x)+M∑mi=1［min(0,gi(x))］2(14)

　　式(14)中,F(x,M)為懲罰函數(shù),當F(x,M)的最優(yōu)解逼近約束問題最優(yōu)解的時候,可行解的約束條件gi(x)的值必須達到很小,反之則很大,因此懲罰項Mp(x)對于非可行解進行了懲罰,這樣能夠有效地保證約束問題可以轉(zhuǎn)化為非約束優(yōu)化問題。

3改進的粒子群算法的定位優(yōu)化

　　3.1距離誤差修正

　　根據(jù)2.2.2節(jié)描述,在總結(jié)了無線傳感網(wǎng)的能量消耗后,應該最大限度地降低未知節(jié)點的可行解的范圍,進而降低未知節(jié)點所在區(qū)域限制,從而可能加快算法達到最優(yōu),引入文獻［8］中的修正系數(shù)來進行限定。首先,通過RSSI技術(shù)得到未知節(jié)點X(x,y)到錨節(jié)點之間的距離為d1,d2,…，dm,其次,從這些錨節(jié)點中選取三個錨節(jié)點作為參考節(jié)點來計算一個未知節(jié)點的距離。

　　(x－xa)2+(y－ya)2=d2a

　　(x－xb)2+(y－yb)2=d2b

　　(x－xc)2+(y－yc)2=d2c(15)

　　通過公式得到未知節(jié)點的估算位置為X(x′,y′)。最后,將估算節(jié)點的位置X(x′,y′)到m個錨節(jié)點之間的距離為d′1,d′2,…,d′m。計算出未知節(jié)點的前后估算位置到錨節(jié)點的之間的誤差作為修正系數(shù),即:

　　λ=|d′1,d′2,…,d′m－d1,d2,…,dm|d1,d2,…,dm/m(16)

　　因此得到的定位模型的約束條件為:

　　(1－λ)di≤(x－xi)2+(y－yi)2≤(1+λ)di(17)

　　3.2構(gòu)造約束定位模型

　　目標函數(shù)為:

　　f(x)=min(∑mi=1|(x－xi)2+(y－yi)2－di|)(18)

　　根據(jù)公式(17)得到兩個約束條件為:

　　g1(x)=(x－xi)2+(y－yi)2－(1－λ)di≥0

　　g2(x)=(1+λ)di－(x－xi)2+(y－yi)2≥0(19)

　　因此構(gòu)造后懲罰函數(shù)為:

　　F(X,M)=f(X)+M∑mi=1|g1(x)+g2(x)|(20)

4仿真實驗

　　4.1實驗環(huán)境

　　為了進一步說明本文算法具有的有效性,實驗對象選擇在100 m×100 m的區(qū)域內(nèi)進行,設(shè)定節(jié)點的通信半徑為25 m,錨節(jié)點隨機進行分布,進行200次迭代實驗,硬件配置為：CPU為酷睿i3,內(nèi)存為4 GB DDR3,硬盤為500 GB,軟件環(huán)境選擇Windows 7,仿真平臺選擇MATLAB 2010。將本文算法與基本的粒子群算法進行對比,從算法的收斂性能和定位精度上進行分析。設(shè)定種群規(guī)模為20,兩個學習因子的值都是2,慣性權(quán)重值在(0,1)之間變換。引入文獻［9］中的定位誤差和定位均方差：Ave=E(x－x0)2+(y－y0)2,Mse=E［(x－x0)2+(y－y0)2］。其中(x,y)和(x0,y0)分別為未知節(jié)點的估計位置和真實位置。

　　4.2算法的收斂性比較

　　兩種定位算法的收斂性比較如圖1所示。從圖中發(fā)現(xiàn),本文算法與基本粒子群算法相比收斂速度更快,定位函數(shù)值更快。本文算法當?shù)螖?shù)為90的時候,算法基本收斂,而基本粒子群算法迭代次數(shù)為130次才收斂,因此算法的效率提高了30.76%。究其原因是在本文算法中進一步簡化了算法粒子的速度項，這樣降低了由于算法的速度引起算法收斂的問題，通過動態(tài)擾動因子和懲罰函數(shù)，有效降低算法的局部收斂可能性，使得算法能夠以更快的速度獲得全局最優(yōu)解。

　　兩種算法誤差比較如表1所示。由表1看出,在測距誤差不斷變大的情況下,本算法的定位誤差遠遠小于基本粒子群算法,這主要是因為距離誤差的修正使得算法縮小了可行解的搜索范圍,使得算法定位更加精確,同時動態(tài)擾動算子解決了算法的局部收斂,避免了算法過早產(chǎn)生最優(yōu)解,最終使得算法能夠找到最優(yōu)解。

　　4.3平均定位誤差比較

　　兩種算法的平均定位誤差比較如圖2所示。從圖中發(fā)現(xiàn),當測距誤差所占的比例逐漸增大的時候,兩種算法的平均定位誤差都在呈現(xiàn)上升的趨勢。另外，在同一個測距誤差比例的條件下,本文算法的平均定位誤差要明顯小于基本粒子群算法,并且測距誤差所占比例不斷地增大的時候,兩者之間的定位誤差也在增大,這說明從整體上本文算法都要小于基本粒子群算法,說明了本文算法定位精度較高。圖中曲線的平緩度從另一個側(cè)面說明了本文算法的定位精度波動較小。這主要是因為通過粒子的位置去控制算法的進化過程,導致了算法在后期的運算過程中收斂速度變慢，特別是動態(tài)擾動因子的引入，進一步防止了算法的局部收斂,有效地提高了算法性能,減少了找到節(jié)點位置的時間,距離誤差修正系數(shù)的引入,保證了可行解產(chǎn)生的區(qū)域,降低了搜索消耗的時間,更加準確地找到節(jié)點的位置。

　　4.4定位均方差比較

　　兩種算法的定位均方差比較如圖3所示。從圖中發(fā)現(xiàn),當測距誤差比例逐漸增大的時候,兩種算法的定位均誤差都在不斷地增加。兩種算法的曲線都比較平緩,在相同的測距誤差比例下,本文定位算法誤差都要小于基本粒子群算法。伴隨著定位誤差值的不斷增大,本文均方誤差

　　增長速度減慢,說明算法定位穩(wěn)定性很高。這主要是因為避免了速度選項所帶來的影響,采用位置來控制算法的進化,距離誤差修正系數(shù)的引入限定了算法的搜索范圍,使得算法更加穩(wěn)定。

　　5結(jié)論

　　如何能夠降低節(jié)點定位帶來的誤差是無線傳感網(wǎng)中研究的主要方向,本文使用傳統(tǒng)的RSSI測距技術(shù)來獲得未知節(jié)點的位置,并采用改進后的粒子群算法對未知節(jié)點的位置進行優(yōu)化,取得了比較好的效果。通過仿真實驗說明本文的算法優(yōu)于基本的粒子群算法的定位,算法效果明顯。

參考文獻

　?。?］ 葉阿勇,馬建峰,裴慶祺.無線傳感器網(wǎng)絡(luò)節(jié)點定位安全研究進展［J］.通信學報,2009,30(S1):74-84.

　　［2］ 梁娟,吳媛.采用WSVM的三維無線傳感器網(wǎng)絡(luò)節(jié)點定位［J］.華僑大學學報(自然科學版),2016,37(1):79-83.

　?。?］ 宋西軍，吳梅梅.一種改進的DVHop無線傳感器網(wǎng)絡(luò)節(jié)點定位算法研究［J］.科技通報,2016,32(7):143-145.

　　［4］ 武曉琳,單志龍,曹樹林.基于接收信號強度指示測距的蒙特卡羅盒移動節(jié)點定位算法［J］.計算機應用,2015,34(4):916-920.

　?。?］ 程麗玲.基于ABCLS的傳感器節(jié)點定位算法［J］.計算機應用與軟件,2015,32(5):258-261.

　?。?］ 于泉,孫順遠,徐保國.基于改進粒子群算法的無線傳感器網(wǎng)絡(luò)節(jié)點定位［J］.計算機應用,2015,35(6):1519-1522.

　　［7］ 胡旺,李志蜀.一種更簡單而高效的粒子群優(yōu)化算法［J］.軟件學報,2007,18(4): 861868.

　?。?］ 石瑩.基于粒子群的無線傳感器網(wǎng)絡(luò)定位技術(shù)的研究［D］.哈爾濱:哈爾濱工程大學,2010.

　　［9］ GEETHA V, PRANESH V, KALLAPURB. Clustering in wireless sensor networks: performance comparison of LEACH & LEACHC protocols using NS2［J］. Procedia Technology, 2012（4）: 163-170.