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

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

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

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

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

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

1.1 選擇機(jī)制

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

pBesti(k+1)=

(1)

f[gBest(k+1)]=

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

(2)

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

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

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

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

因而，選擇機(jī)制可以描述為

1.2 交叉與變異

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

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

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

(5)

(6)

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

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

(7)

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

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

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

1.3 排隊機(jī)制

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

(8)

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

2 算法仿真

2.1 仿真環(huán)境

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

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

2.2 仿真結(jié)果和分析

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次以后的平均定位結(jié)果。通過IHPSO算法實施，對區(qū)域內(nèi)20個節(jié)點中的16個能夠有效定位，且定位誤差為6.47%，即平均誤差距離為3.2 m。

2.2.2 定位誤差

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

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

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

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

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

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

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

2.2.3 定位時間

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

圖5 3種算法n與t

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

3 結(jié)束語

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