傅彬
(紹興職業技術學院,浙江 紹興 312000)
摘要：針對無線傳感網中的節點定位問題,采用RSSI測距技術測量未知節點之間的距離,并采用粒子群算法進行優化,針對粒子群算法的不足,首先通過引入動態擾動因子和懲罰函數提高算法的性能,其次采用距離誤差修正和修正定位誤差模型來優化節點定位的效果。通過仿真實驗將所提算法與基本粒子群算法進行比較,結果表明所提算法在算法的收斂性能和定位精度上取得了比較好的效果,提高了節點的定位效果。
關鍵詞：無線傳感網；動態擾動因子；懲罰函數
中圖分類號：TP393文獻標識碼：ADOI： 10.19358/j.issn.1674-7720.2017.08.020
引用格式：傅彬.一種改進的粒子群算法在WSN中的定位研究［J］.微型機與應用，2017,36（8）：63-66.
0引言
無線傳感網中的節點定位是衡量無線傳感網絡數據傳輸效率高低的一個重要標準［1］。節點定位不但受到自然界中客觀條件的影響,還容易受到來自自身節點傳輸信號強弱、傳輸距離以及節點能量等條件的限制,因此如何進行節點定位的優化一直都是學者們不斷研究的方向。國內外學者從不同的角度對節點定位提出了自己的研究方向。文獻［2］提出一種基于小波支持向量機(WSVM)的定位算法,取得了比較好的定位效果;文獻［3］從全網平均每跳距離角度出發,分析每個信標節點的平均每跳距離誤差,有效地提高了節點定位精度;文獻［4］提出一種基于接收信號強度指示測距的蒙特卡羅盒定位算法;文獻［5］提出采用人工蜂群算法來修正最小二乘定位誤差的傳感器節點定位算法,該算法能夠有效地提高無線傳感器節點的定位精度;文獻［6］提出了一種改進粒子群算法與DVHop的融合算法。
本文在以上研究的基礎上,采用粒子群算法對使用RSSI測距技術的節點之間的距離進行優化,通過對粒子群算法采用動態擾動因子、懲罰函數、誤差修正和修正定位模型等方法提高算法的性能,提高算法定位的效果。
1接收信號強度(RSSI)
在真實的無線傳感網中，硬件設備是非常重要的必備工具，其優點是設計簡單，缺點是處理能力有限,因此需要布置大量的傳感器。而RSSI測距技術不需要復雜的硬件設備,它僅僅依靠節點發射信號的功率與接收信號功率之間的差值來初步估算兩點之間的損耗,并轉換為兩個節點之間的距離,計算公式模型如下:
PR(d)=PtGtGrλ2/16π2d2L(1)
式中,PR(d)表示接收節點與發射節點相距d的功率,Pt為發射節點的功率,Gt、Gr分別為發射節點和接收節點的增益,L為損耗定量,d為距離,λ為波長。
理論研究中，無線傳感網中的節點定位模型都是在假設一定理論條件成立的情況下建立的,但在實際情況中,無線傳感網絡可能受到來自自然界中的溫度、濕度、障礙物等影響,網絡中傳輸的信號肯定會受到不同程度的影響,因此采用RSSI測量獲得的節點的估計距離和真實距離具有一定的差距。因此如何降低誤差成為了研究的主要方向。
2改進的粒子群算法
2.1粒子群算法簡述
在一個D維的搜索空間中,種群由M個粒子組成,其中第i個粒子的位置為Xi=［xi1,xi2,…xiD］,飛行速度為Vi=［vi1,vi2,…，viD］,設定Pi是第i個粒子當前搜索的個體最佳位置,Pi=［pi1,pi2,…，pID］；Pg為當前搜索到的全局最優位置,Pg=［pg1,pg2,…，pgD］,因此粒子的位置和速度的調整方向如下:
Vk+1id=ωVkid+c1r1(Pid－Xkid)+c2r2(Pgd－Xkid)(2)
Xk+1id=Xkid+Vk+1id(3)
式中的k為迭代次數；r1和r2是0~1之間的隨機數,用來保持種群具有的多樣性；ω為慣性權重值；c1和c2是學習因子,用來掌握粒子個體的最優位置以及整個粒子群中的全局最優位置,合理地調節算法,提高算法的收斂速度。在粒子群算法中，對每一個粒子的個體來說,個體最優解Pi和粒子全局最優解Pg的更新如下:
Pk+1i=Xk+1i,f(Xk+1i)≤f(Pki)
Pki,其他 (4)
f(Pg)=min［f(Pi)］(5)
2.2改進的粒子群算法
文獻［7］證明粒子群算法在進化過程中與粒子的速度沒有直接的關系,因此將粒子群優化算法的位置更新簡化為如下形式:
Xk+1id=ωVkid+c1r1(Pid－Xkid)+c2r2(Pgd－Xkid)(6)
2.2.1引入動態擾動因子
公式(6)雖然進行了簡化,但仍然可以發現該算法具有收斂速度快、容易陷入局部最優解的可能。為了解決這個問題,首先引入擾動因子概念,當個體的最優解和全局最優解停滯的時候,使用擾動因子對其進行擾動,使得算法遠離當前搜索區域,向其他區域擴散。因此擾動因子設置如下:
rt0>T03=1,t0≤T0
U(0,1),t0>T0 (7)
rtg>Tg4=1,tg≤Tg
U(0,1),tg>Tg(8)
式中,t0和tg分別表示個體最優解和全局最優解的停滯次數,而T0和Tg分別對應個體最優解和全局最優解的停滯的閾值。
從以上分析中發現，當t0>T0,tg>Tg的時候,算法停滯,當算法再次執行的時候只有在局部獲得最優值后才可以執行,從而可以對當前個體極值和全局極值進行擾動,因此算法必須停滯T0或者Tg步之后才能進行下一次迭代運算。雖然設置了擾動因子，但存在兩個問題：一個問題是加速了節點定位過程中節點產生的額外消耗,從而降低傳感器的壽命；另一個問題是擾動因子有可能讓算法從一個局部最優收斂到另一個局部最優,這樣降低了算法的時間效率和空間效率。因此為了避免以上出現的問題,針對式(7)和式(8)提出了動態擾動因子的概念,如下:
式中,rand1()是一個(0,1)之間的隨機數,rand2()是一個(1, kmax)之間的隨機數,k為當前迭代次數,kmax為最大迭代次數。因此公式(6)的變化如下:
Xk+1id=ωVkid+c1r1(d1Pid－Xkid)+c2r2(d2Pgd－Xkid)(11)
2.2.2懲罰函數
粒子群算法的最優解的確定是算法的關鍵,而可行解都需要加上一定的約束條件,為了盡可能地縮小最優解的搜索范圍,避免算法進行不相關的盲目搜索,降低算法搜索時間,需要將粒子產生最優解問題轉換為無約束的優化問題。當粒子滿足約束條件的時候,懲罰值會很??；反之,則會很大。對于不滿足約束條件的粒子賦予數值較大的懲罰函數數值,這樣可以有效地降低目標函數,后續的粒子就會遠離無解的區域。
粒子群算法中的粒子最優解獲得是在一定約束條件下使得某個度量值達到最小。記f為表示問題的目標函數,A為可行解,gi(x)為約束域,得到:
minf(x),x∈A
A={x|gi(x)≥0,i=1,2,…，m}(12)
將公式(12)中的不等式約束轉換為等式約束問題:
minf(x),x∈A
s.t.min(0,gi(x))=0(13)
設p(x)=∑mi=1［min(0,gi(x))］2,因此將式(13)轉換為無約束函數：
F(x,M)=f(x)+Mp(x)=f(x)+M∑mi=1［min(0,gi(x))］2(14)
式(14)中,F(x,M)為懲罰函數,當F(x,M)的最優解逼近約束問題最優解的時候,可行解的約束條件gi(x)的值必須達到很小,反之則很大,因此懲罰項Mp(x)對于非可行解進行了懲罰,這樣能夠有效地保證約束問題可以轉化為非約束優化問題。
3改進的粒子群算法的定位優化
3.1距離誤差修正
根據2.2.2節描述,在總結了無線傳感網的能量消耗后,應該最大限度地降低未知節點的可行解的范圍,進而降低未知節點所在區域限制,從而可能加快算法達到最優,引入文獻［8］中的修正系數來進行限定。首先,通過RSSI技術得到未知節點X(x,y)到錨節點之間的距離為d1,d2,…，dm,其次,從這些錨節點中選取三個錨節點作為參考節點來計算一個未知節點的距離。
(x－xa)2+(y－ya)2=d2a
(x－xb)2+(y－yb)2=d2b
(x－xc)2+(y－yc)2=d2c(15)
通過公式得到未知節點的估算位置為X(x′,y′)。最后,將估算節點的位置X(x′,y′)到m個錨節點之間的距離為d′1,d′2,…,d′m。計算出未知節點的前后估算位置到錨節點的之間的誤差作為修正系數,即:
λ=|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構造約束定位模型
目標函數為:
f(x)=min(∑mi=1|(x－xi)2+(y－yi)2－di|)(18)
根據公式(17)得到兩個約束條件為:
g1(x)=(x－xi)2+(y－yi)2－(1－λ)di≥0
g2(x)=(1+λ)di－(x－xi)2+(y－yi)2≥0(19)
因此構造后懲罰函數為:
F(X,M)=f(X)+M∑mi=1|g1(x)+g2(x)|(20)
4仿真實驗
4.1實驗環境
為了進一步說明本文算法具有的有效性,實驗對象選擇在100 m×100 m的區域內進行,設定節點的通信半徑為25 m,錨節點隨機進行分布,進行200次迭代實驗,硬件配置為：CPU為酷睿i3,內存為4 GB DDR3,硬盤為500 GB,軟件環境選擇Windows 7,仿真平臺選擇MATLAB 2010。將本文算法與基本的粒子群算法進行對比,從算法的收斂性能和定位精度上進行分析。設定種群規模為20,兩個學習因子的值都是2,慣性權重值在(0,1)之間變換。引入文獻［9］中的定位誤差和定位均方差：Ave=E(x－x0)2+(y－y0)2,Mse=E［(x－x0)2+(y－y0)2］。其中(x,y)和(x0,y0)分別為未知節點的估計位置和真實位置。
4.2算法的收斂性比較
兩種定位算法的收斂性比較如圖1所示。從圖中發現,本文算法與基本粒子群算法相比收斂速度更快,定位函數值更快。本文算法當迭代次數為90的時候,算法基本收斂,而基本粒子群算法迭代次數為130次才收斂,因此算法的效率提高了30.76%。究其原因是在本文算法中進一步簡化了算法粒子的速度項，這樣降低了由于算法的速度引起算法收斂的問題，通過動態擾動因子和懲罰函數，有效降低算法的局部收斂可能性，使得算法能夠以更快的速度獲得全局最優解。
兩種算法誤差比較如表1所示。由表1看出,在測距誤差不斷變大的情況下,本算法的定位誤差遠遠小于基本粒子群算法,這主要是因為距離誤差的修正使得算法縮小了可行解的搜索范圍,使得算法定位更加精確,同時動態擾動算子解決了算法的局部收斂,避免了算法過早產生最優解,最終使得算法能夠找到最優解。
4.3平均定位誤差比較
兩種算法的平均定位誤差比較如圖2所示。從圖中發現,當測距誤差所占的比例逐漸增大的時候,兩種算法的平均定位誤差都在呈現上升的趨勢。另外，在同一個測距誤差比例的條件下,本文算法的平均定位誤差要明顯小于基本粒子群算法,并且測距誤差所占比例不斷地增大的時候,兩者之間的定位誤差也在增大,這說明從整體上本文算法都要小于基本粒子群算法,說明了本文算法定位精度較高。圖中曲線的平緩度從另一個側面說明了本文算法的定位精度波動較小。這主要是因為通過粒子的位置去控制算法的進化過程,導致了算法在后期的運算過程中收斂速度變慢，特別是動態擾動因子的引入，進一步防止了算法的局部收斂,有效地提高了算法性能,減少了找到節點位置的時間,距離誤差修正系數的引入,保證了可行解產生的區域,降低了搜索消耗的時間,更加準確地找到節點的位置。
4.4定位均方差比較
兩種算法的定位均方差比較如圖3所示。從圖中發現,當測距誤差比例逐漸增大的時候,兩種算法的定位均誤差都在不斷地增加。兩種算法的曲線都比較平緩,在相同的測距誤差比例下,本文定位算法誤差都要小于基本粒子群算法。伴隨著定位誤差值的不斷增大,本文均方誤差
增長速度減慢,說明算法定位穩定性很高。這主要是因為避免了速度選項所帶來的影響,采用位置來控制算法的進化,距離誤差修正系數的引入限定了算法的搜索范圍,使得算法更加穩定。
5結論
如何能夠降低節點定位帶來的誤差是無線傳感網中研究的主要方向,本文使用傳統的RSSI測距技術來獲得未知節點的位置,并采用改進后的粒子群算法對未知節點的位置進行優化,取得了比較好的效果。通過仿真實驗說明本文的算法優于基本的粒子群算法的定位,算法效果明顯。
參考文獻
［1］ 葉阿勇,馬建峰,裴慶祺.無線傳感器網絡節點定位安全研究進展［J］.通信學報,2009,30(S1):74-84.
?。?］ 梁娟,吳媛.采用WSVM的三維無線傳感器網絡節點定位［J］.華僑大學學報(自然科學版),2016,37(1):79-83.
?。?］ 宋西軍，吳梅梅.一種改進的DVHop無線傳感器網絡節點定位算法研究［J］.科技通報,2016,32(7):143-145.
?。?］ 武曉琳,單志龍,曹樹林.基于接收信號強度指示測距的蒙特卡羅盒移動節點定位算法［J］.計算機應用,2015,34(4):916-920.
?。?］ 程麗玲.基于ABCLS的傳感器節點定位算法［J］.計算機應用與軟件,2015,32(5):258-261.
［6］ 于泉,孫順遠,徐保國.基于改進粒子群算法的無線傳感器網絡節點定位［J］.計算機應用,2015,35(6):1519-1522.
?。?］ 胡旺,李志蜀.一種更簡單而高效的粒子群優化算法［J］.軟件學報,2007,18(4): 861868.
［8］ 石瑩.基于粒子群的無線傳感器網絡定位技術的研究［D］.哈爾濱:哈爾濱工程大學,2010.
?。?］ GEETHA V, PRANESH V, KALLAPURB. Clustering in wireless sensor networks: performance comparison of LEACH & LEACHC protocols using NS2［J］. Procedia Technology, 2012（4）: 163-170.