WSN雜交粒子群優(yōu)化定位改進算法

唐 弢，趙月新，郭 巖，胡福芳

(1. 黑龍江工程學院 電氣與信息工程學院，黑龍江 哈爾濱 150050； 2. 哈爾濱云珀科技有限公司，黑龍江 哈爾濱 150000)

定位是無線傳感器網(wǎng)絡(WSN)中不可缺少的組成部分。定位服務不但可以提供事件發(fā)生地的位置信息，而且對于WSN部署以后的其他技術(如路由等)也具有推動作用[1]。目前的定位技術通常分為兩類：測距和非測距技術，相對來說測距技術以其定位精度的明顯優(yōu)勢得到了更多的青睞，其中，基于RSSI的定位方法更能夠滿足WSN節(jié)點能力的限制要求，因而得到了廣泛的應用[2]。

基于RSSI技術中，PSO定位算法及其改進算法以其高精度的特點成為近年來研究熱點[3]，其中，最主要的有混合PSO[4]、協(xié)同PSO[5]、耗散PSO[6]及雜交PSO[7]等。大多數(shù)的改進算法都是在PSO的基礎上重新選擇或者加入某些參數(shù)，亦或是算法策略上的改進?；旌螾SO定位算法引入了淘汰機制，使其收斂速度(定位時間)大幅度提高，然而該算法基于局部最優(yōu)的方式，一旦陷入則無法跳出。協(xié)同PSO選擇了多個子種群同時進行搜索，該算法可以有效避免混合PSO的局部最優(yōu)問題，然而多個群會導致計算量過大，無法滿足WSN節(jié)能的要求[8]。雜交PSO利用雜交方式通過父代粒子產生子代粒子，兩者數(shù)量相同，并且能夠利用擾動因子，避免全局最優(yōu)和早熟現(xiàn)象的發(fā)生，同時相比于其他改進算法具有良好的定位精度和收斂性[9]。因而，利用雜交PSO算法在WSN對未知節(jié)點進行定位相對廣泛。然而，雜交PSO定位算法仍然存在計算量大、定位時間長等問題。

1 WSN雜交粒子群優(yōu)化定位改進算法

雜交粒子群優(yōu)化定位改進算法流程如圖1所示。

1.1 選擇機制

如圖1所示，每個粒子計算適應值并更新個體極值pBesti和全局極值gBest[10]

pBesti(k+1)=

(1)

f[gBest(k+1)]=

min{f[pBesti(k+1)]},i=1,2,…，N.

(2)

更新后需要判定是否終止， 若不滿足終止條件則需進行選擇操作。如圖1所示，選擇機制的原理就是通過引入粒子集中度gath(k)和粒子平穩(wěn)度smth(k)兩個概念，判定是否進行交叉和變異。粒子集中度gath(k)和粒子平穩(wěn)度smth(k)分別定義為

(3)

(4)

式中：M為種群數(shù)量；S為平穩(wěn)階數(shù)；C為任意常數(shù)。通過計算可知，粒子集中度gath(k)和粒子平穩(wěn)度smth(k)的范圍均為gath(k)∈[0,1]，smth(k)∈[0,1]。

當集中度gath(k)趨近于1時，表示在k時刻，粒子的分布相對集中，此時定義不需要進行交叉操作；反之gath(k)趨近于0時，則需要進行交叉操作。

當平穩(wěn)度smth(k)趨于1時，表示k時刻粒子以相對較低(趨于0)的速度運動，在此情況下陷入局部最優(yōu)解的可能性加大，因而需要進行變異操作跳出局部最優(yōu)解；反之smth(k)趨近于0時，則不需要進行變異操作。

定義某數(shù)值α,β作為閾值來判定是否進行交叉和變異操作，其中,α，β∈ [0,1]，具體數(shù)值可以在試驗中通過經驗測定得到。

因而，選擇機制可以描述為

1.2 交叉與變異

交叉與變異的方法與雜交PSO相同，算法原理如圖2所示[11]。

假設p1(xid)/p2(xid)、p1(v)/p2(v)和ch1(xid)/ch2(xid)、ch1(v)/ch2(v)分別為父代和子代粒子的位置、速度。

交叉過程可以用公式表示為

(5)

(6)

式中：ri為在[0,1]區(qū)間內均勻分布的隨機數(shù)。

變異過程的實施目的是為了跳出局部最優(yōu)解，即在傳統(tǒng)PSO中加入擾動因子，從而避免PSO的停滯現(xiàn)象。

(7)

式中：[L,R]為參數(shù)變化范圍；α，γ∈[0,1]且隨機分布。

交叉變異的特點及優(yōu)勢主要體現(xiàn)在：子代粒子可以最大限度地保留父代粒子的優(yōu)點，且數(shù)量與父代粒子數(shù)量相同，因而隨著迭代次數(shù)的增加，粒子的相似度不斷增大；加入擾動因子后可以有效地避免早熟現(xiàn)象及后期相似度增大所帶來的局部最優(yōu)問題。

將粒子集中度gath(k)和粒子平穩(wěn)度smth(k)應用于交叉和變異過程中以后，可以通過計算和預判精準控制何時實施交叉，何時實施變異，這大大地提高算法收斂性和定位時間。通過多次試驗可以看出，一般交叉操作發(fā)生在迭代初期，而變異操作發(fā)生在迭代后期。

1.3 排隊機制

在傳統(tǒng)PSO中，每一個粒子以各自的適應度函數(shù)判斷目前位置是否為最優(yōu)位置。適應度函數(shù)為

(8)

為了獲得更優(yōu)良的子代粒子(子代粒子可以保留父代粒子的遺傳性)，在算法中引入排隊機制。將父代粒子的適應值進行排隊，選取最優(yōu)的一部分作為父代，再以交叉概率pc進行雜交，從而保證雜交過程的目的性和方向性。具體實施時間節(jié)點如圖1所示。

2 算法仿真

2.1 仿真環(huán)境

仿真環(huán)境為空曠的方形場地，其邊長為50 m×50 m。在方形網(wǎng)絡中，設置未知節(jié)點20個，錨節(jié)點(自身位置已知，且能主動定位)5個，節(jié)點通信半徑為70 m，即節(jié)點可以覆蓋整個方形區(qū)域。每個節(jié)點都具有RSSI裝置，其測距誤差為0～30% ，節(jié)點發(fā)射功率0.25 mw，發(fā)射頻率2.4 GHz。錨節(jié)點及未知節(jié)點均隨機分布，每一次仿真的結果是20個未知節(jié)點中可定位節(jié)點的平均值。

PSO算法的種群數(shù)量為50個，學習因子c1=c2=2，慣性常數(shù)ω采用線性遞減法，且ω∈[0.4,1.0]，即選擇由1.0到0.4的線性遞減模型。迭代終止條件滿足精度10-6或者達到最大迭代次數(shù)Tmax=100。

2.2 仿真結果和分析

2.2.1 定位效果

通過仿真，IHPSO定位效果如圖3所示。

(a)迭代過程

(b)最終效果(n=2.5，N=40，Tmax=100)圖3 IHPSO定位效果

圖3(a)為對區(qū)域中的某一節(jié)點定位過程的動態(tài)迭代效果，圖3(b)為對區(qū)域中所有節(jié)點實施算法后的定位效果。從圖3(a)可以看到，IHPSO在迭代過程中，估計節(jié)點位置始終朝著節(jié)點的實際位置逼近，隨著迭代次數(shù)的不斷增大，估計節(jié)點位置與實際節(jié)點位置之間的距離越來越小。圖3(b)是連續(xù)仿真10次以后的平均定位結果。通過IHPSO算法實施，對區(qū)域內20個節(jié)點中的16個能夠有效定位，且定位誤差為6.47%，即平均誤差距離為3.2 m。

2.2.2 定位誤差

本文通過改進雜交PSO算法，達到降低定位誤差的目的。將errorL定義為定位誤差，errorL是估測節(jié)點坐標與真實坐標的距離，與測量范圍邊長的相對值，記作errorL。

在IHPSO算法中，通過調整路徑損耗指數(shù)n、種群數(shù)量N和迭代次數(shù)T等指定參數(shù)，對IHPSO算法進行多次實驗，并與傳統(tǒng)PSO、雜交PSO算法進行對比，從而達到降低errorL的目的。仿真結果如圖4所示。

圖4 路徑損耗指數(shù)n對定位誤差的影響

從仿真中可以看到：首先，在路徑損耗增大的情況下，相應的定位誤差errorL也隨之增大，這符合定位的一般規(guī)律；另一方面本文提出的IHPSO算法無論是對比傳統(tǒng)PSO還是雜交PSO，在n=2～6時，errorL均有所改善，特別是n值較大時，改善更為明顯。

對算法進行多次仿真(連續(xù)10次仿真求平均值)，對比縱向結果可以看到：當路徑損耗系數(shù)變化時，雜交PSO優(yōu)于傳統(tǒng)PSO的定位誤差，平均降低5.44%；而在雜交PSO基礎上改進的IHPSO算法相比于雜交PSO的定位誤差errorL平均降低了6.9%；與傳統(tǒng)PSO相比則優(yōu)勢更為明顯，平均定位誤差降低了12.9%。

另外，當路徑損耗逐漸增大時， IHPSO對errorL穩(wěn)定度的改善更為明顯，在10次重復性實驗中，當n=5時，PSO、雜交PSO及IHPSO的方差(定位誤差偏離度)分別為180.9、169.5及74.36；當n=6時分別為386.5、428.2及190.4。

綜上所述，IHPSO算法在定位誤差及定位的穩(wěn)定度上，相對于原有的PSO及雜交PSO都有所改善，且隨著路徑損耗的增大，改善更為明顯。另外，除路徑損耗指數(shù)外，種群數(shù)量、迭代次數(shù)等均會對仿真結果造成一定的影響，這里不再贅述。

2.2.3 定位時間

定位時間是評價算法的重要指標之一，一般來說定位時間越少，更適用于無線傳感器網(wǎng)絡，算法的應用范圍也就越廣。3種算法對定位時間的仿真如圖5所示。

圖5 3種算法n與t

圖5反映了路徑損耗與定位時間的關系?？梢钥闯觯s交PSO的定位時間明顯高于傳統(tǒng)PSO，而由于加入了排隊機制和選擇機制，IHPSO的定位時間雖略高于傳統(tǒng)PSO，但相比于雜交PSO有大幅度的降低。此外，定位時間還與最大迭代時間、種群數(shù)量有關，顯然，當N，Tmax增加時，定位時間將大幅增大。將3種算法橫向比較：當n=2，N=50，Tmax=100時，QJ-CMPS平均定位時間0.3 s，HPSO 0.9 s，IHPSO一次定位時間降低了66.7%。

3 結束語

本文將選擇機制和排隊機制引入雜交PSO中，提出一種WSN雜交粒子群優(yōu)化定位改進算法(IHPSO)，該算法可以計算和控制發(fā)生變異和交叉的時間，有效利用子代與父代之間的遺傳性快速收斂，并且能夠通過加入擾動粒子避免早熟現(xiàn)象的發(fā)生。實驗證明，該算法可以有效地提高傳統(tǒng)PSO和雜交PSO算法的定位精度和定位時間。