吳珍珍,方旺盛
(江西理工大學(xué) 信息工程學(xué)院,江西 贛州 341000)
WSN節(jié)點定位技術(shù)是WSN應(yīng)用于目標(biāo)監(jiān)測、目標(biāo)識別和目標(biāo)跟蹤的支撐技術(shù),其算法可分為基于非測距(Range- free)的算法和基于測距(Range-based)的算法[1],其中非測距DV-Hop算法因具有成本低、能耗小、算法實現(xiàn)簡單等特點而被廣泛應(yīng)用,但該算法也存在定位誤差較大的不足。
為了提高DV-Hop算法的定位精度,國內(nèi)學(xué)者對此引入群體智能算法進(jìn)行優(yōu)化。文獻(xiàn)[2]提出了一種改進(jìn)的粒子群優(yōu)化DV-Hop算法,從慣性權(quán)重的計算、粒子速度的更新等方面對粒子群算法進(jìn)行改進(jìn),提高算法的搜索速度,再采用改進(jìn)粒子群算法優(yōu)化節(jié)點的定位結(jié)果,降低了定位誤差。文獻(xiàn)[3]利用免疫系統(tǒng)里的調(diào)節(jié)機制來提高種群的多樣性,避免了過早陷入局部最優(yōu)解,優(yōu)化的DV-Hop算法提高了定位效果,但該算法未考慮粒子群算法的收斂速度問題。文獻(xiàn)[4]使用遺傳機制中的前攝估計縮小粒子搜索范圍,再用改進(jìn)粒子群算法以代替最小二乘法優(yōu)化了DV-Hop算法定位精度。本文根據(jù)免疫粒子群算法的特點,利用該算法來優(yōu)化DV-Hop定位算法求解未知節(jié)點的坐標(biāo)。
DV-Hop(Distance Vector-Hop)是一種非測距定位算法。該算法依賴于節(jié)點間的互相通信,具體定位算法由3個階段組成[5]:
第一階段:信標(biāo)節(jié)點通過全網(wǎng)泛洪廣播數(shù)據(jù)包,所有節(jié)點可以記錄下到每個信標(biāo)節(jié)點的最小跳數(shù)。
第二階段:估算從未知節(jié)點到信標(biāo)節(jié)點的跳距。
第三階段:利用三邊測量法或最小二乘法等計算未知節(jié)點坐標(biāo)[6]。
從DV-Hop的工作原理可知,其產(chǎn)生定位誤差的主要原因有跳數(shù)、平均每跳距離、定位的計算方法等。
(1)跳數(shù)信息不合理
WSN在定位時通過使用跳數(shù)信息計算節(jié)點之間的距離,而無線傳感器網(wǎng)絡(luò)中的節(jié)點大都是隨機分布,未知節(jié)點與錨節(jié)點之間并非都是直線距離,所以節(jié)點之間存在彎曲路徑,將會導(dǎo)致較大誤差。
(2)平均跳距的估計值不準(zhǔn)確
在DV-Hop定位算法中,節(jié)點間的距離計算是采用同一個平均距離的估計值乘以對應(yīng)的跳數(shù)來計算的,存在一定的定位誤差。
(3)定位的計算方法累計誤差
計算未知節(jié)點的坐標(biāo)時經(jīng)常采用三邊測量和極大似然估計法。三邊測量方法雖然降低了計算量,但其受限于第二階段的跳距估計。而在最大似然估計法求解過程中需要較多的浮點預(yù)算,計算開銷帶來的功耗不容忽視。
鑒于上述誤差分析,針對經(jīng)典DV-Hop定位算法在計算未知點坐標(biāo)上存在較大誤差,本文提出了一種免疫粒子群優(yōu)化的DV-Hop定位算法。
粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法是1995年由Kennedy和Eberhart提出的一種新型的隨機群體智能的進(jìn)化算法[7]。其原理為:在D維空間里有很多“粒子”,這些“粒子”通過“位置+速度”模型來更新自身的位置與速度,每個粒子不斷地搜索迭代,向最優(yōu)值位置不斷地靠近[8]。該算法存在以下缺點:(1)容易陷入局部極小值,導(dǎo)致得不到全局最優(yōu)解;(2)沒有充分的優(yōu)選機制,收斂速度較慢。本文為了提高粒子群算法的全局搜索能力,借鑒免疫算法的思想改進(jìn)PSO算法,當(dāng)PSO算法陷入局部最優(yōu)解時,通過免疫抗體的選擇、促進(jìn)和抑制機制產(chǎn)生新的粒子空間,使該算法跳出局部最優(yōu)值,避免“早熟”;另外生成的免疫記憶細(xì)胞可以加快收斂速度,確??焖偈諗坑谌肿顑?yōu)解。
(1)
(2)
式中,c1表示個體學(xué)習(xí)因子,c2表示全局學(xué)習(xí)因子,而r1和r2為(0,1)上均勻分布的隨機數(shù);ω為慣性權(quán)重,表示粒子運動的趨勢,對全局搜索和局部搜索起到平衡作用[9]。該系數(shù)按照公式(3)進(jìn)行更新。
(3)
免疫機制源于生物免疫系統(tǒng),其具體思路為將待優(yōu)化適應(yīng)度函數(shù)最優(yōu)解看作入侵生命體的抗原,而免疫系統(tǒng)產(chǎn)生的抗體即為候選解,將個體最優(yōu)解以免疫記憶形式保存于記憶細(xì)胞,提高收斂速度;根據(jù)免疫調(diào)節(jié)機制,選擇具有親和度高且濃度低的抗體進(jìn)化,而親和度低濃度高的抗體加以抑制[10];通過抗原抗體相互促進(jìn)抑制來維持抗體的多樣性,克服了粒子群算法在實際工程優(yōu)化計算中的早熟收斂現(xiàn)象,提高了算法的全局搜索效率。
(1)親和度
親和度[11]用來衡量抗原與抗體間的匹配程度,即所求的解與最優(yōu)解的接近程度,記為aff,計算公式如下:
(4)
其中,f(xi)為xi的適應(yīng)度函數(shù),η為(0,1)上的常數(shù)。由上式可以看出,當(dāng)f(xi)越小時,抗體的親和度越大,所求的解與最優(yōu)解就越逼近。
(2)濃度
濃度表示抗體與其相似的粒子在群體中所占的比例,反映種群多樣性的程度。假設(shè)存在i個抗體x1,x2…,xi,每個抗體按照親和度從小到大排序并分成m個等份區(qū)間,其中m=1,2,…,m。計算每個區(qū)間的抗體數(shù),記為sum(m),得到每個區(qū)間的濃度為sum(m)/m,將每個抗體的濃度定義為該抗體所在區(qū)間的濃度,記為D,則有:
(5)
由上式可知,同一個區(qū)間上的抗體濃度是相同的,這使得抗體濃度越高反而越受到抑制,而抗體濃度越低反而得到進(jìn)化的機會。
(3)選擇概率
選擇概率是指抗體在進(jìn)化過程中得到促進(jìn)發(fā)展的概率。假設(shè)基于親和度的選擇概率為Pa,而基于濃度的選擇概率為Pd,計算公式如下:
(6)
(7)
則抗體被選中的選擇概率P為:
P(xi)=αPa(xi)+(1-α)Pd(xi)
0<α,Pa,Pd<1
(8)
式中i=1,2,…,n;α為免疫協(xié)調(diào)因子,用來協(xié)調(diào)概率Pd和Pa的權(quán)重。從式(8)可以得知,濃度越高、親和力越低的抗體被選擇的概率越??;而濃度越低、親和力越高的抗體獲得進(jìn)化的概率越大。這樣既提高了抗體的親和度,又保證了粒子的多樣性,從而得到較大的解空間。
(4)適應(yīng)度函數(shù)
適應(yīng)度函數(shù)即目標(biāo)函數(shù),用來評價給出的候選解(抗體)的優(yōu)劣。計算公式如下:
(9)
其中,M(M≥3)為未知節(jié)點接收到的信標(biāo)節(jié)點的個數(shù);(x,y)和(xi,yi)分別表示粒子位置和第i個信標(biāo)節(jié)點的坐標(biāo);di為未知節(jié)點到信標(biāo)節(jié)點i的歐式距離。適應(yīng)度函數(shù)f(i)的極小值點則為最優(yōu)的定位坐標(biāo)。
本文算法優(yōu)化的DV-Hop算法步驟如下:
(1)初始化網(wǎng)絡(luò)區(qū)域、節(jié)點總數(shù)、粒子群相關(guān)參數(shù)。
(2)根據(jù)經(jīng)典DV-Hop算法的第一和第二階段獲得每個信標(biāo)節(jié)點和未知節(jié)點的最小跳數(shù)以及信標(biāo)節(jié)點i的平均跳距,計算跳段距離。
(3)初始化粒子群。初始化粒子位置X、粒子速度V、歷史局部最優(yōu)位置pbesti=Xi,計算種群的適應(yīng)度函數(shù)值,取該值的最小值為粒子群的全局最優(yōu)位置gbesti的初始值。
(4)免疫記憶。將粒子按親和度從小到大排序,取親和度較大的粒子存入免疫記憶細(xì)胞中。
(5)利用式(1)、式(2)分別更新粒子的飛行速度和位置,產(chǎn)生n個新的抗體,然后從免疫記憶細(xì)胞中抽取q個抗體,組成規(guī)模為n+q的抗體群。
(6)免疫替換,丟棄位置較差的粒子(抗體)。利用式(4)~(8)計算抗體的選擇概率,依據(jù)選擇概率從n+q個抗體中選擇出n個抗體,則選擇概率大的抗體將被選中,組成新的抗體群,從而實現(xiàn)抗體的多樣性,避免出現(xiàn)“早熟”。
(7)根據(jù)式(9)計算抗體的適應(yīng)度大小,比較所有粒子當(dāng)前的適應(yīng)度值F(Xi)和局部最優(yōu)位置適應(yīng)度值F(pbesti),若F(pbesti)>F(Xi),則更新pbest值;再用更新后局部最優(yōu)適應(yīng)函數(shù)值F(pbesti)與全局最優(yōu)位置的適應(yīng)函數(shù)F(gbesti)比較,若F(gbesti)>F(pbesti),則更新gbest值。
(8)若滿足終止條件,則輸出全局最優(yōu)解gbesti,適應(yīng)度函數(shù)F(gbesti)的極小值點即為未知節(jié)點的最終定位坐標(biāo)。否則返回步驟(4)。
為驗證本文算法的有效性,本文基于Windows 10操作系統(tǒng)的MATLAB 2014平臺進(jìn)行仿真實驗。本文試驗場景設(shè)置為100 m×100 m的二維正方形區(qū)域,假設(shè)所有WSN網(wǎng)絡(luò)節(jié)點的通信半徑都為R。
免疫粒子群算法的初始化參數(shù)如表1所示。
表1 仿真參數(shù)
(1)信標(biāo)節(jié)點比例對定位精度的影響
假設(shè)通信半徑為30 m、節(jié)點總數(shù)為100,圖1給出信標(biāo)節(jié)點比例對定位精度的影響關(guān)系圖。從圖中可以看出,3種定位算法的平均定位誤差都隨著信標(biāo)節(jié)點的比例增加而減小。當(dāng)信標(biāo)節(jié)點比例相同時,本文算法的平均定位誤差與DV-Hop以及PSO-DV-Hop定位算法比較降低了15.03%、4.86%。另外,本文算法平均定位誤差曲線更平滑,表明其穩(wěn)定性更好。
圖1 信標(biāo)節(jié)點比例與定位誤差關(guān)系圖
(2)通信半徑對定位精度的影響
假設(shè)節(jié)點總數(shù)為100時,信標(biāo)節(jié)點比例為10%,改變通信半徑進(jìn)行仿真,結(jié)果如圖2所示。從圖中可以看出,在通信半徑小于30 m時,3種定位算法的平均定位誤差都隨著通信半徑的增大而明顯減小,這是因為通信半徑的增大提高了未知節(jié)點與信標(biāo)節(jié)點的連通性,從而可以獲得更大范圍的信息交換來提高定位精度。但在通信半徑大于30 m時,平均定位誤差緩慢減小,趨于平滑,因此通信半徑并不是越大越好,通信半徑的增大也將提高通信開銷。另外,從3種算法對比可以看出,本文算法的定位誤差與經(jīng)典DV-Hop、PSO-DV-Hop定位算法相比,定位精度提高了13.27%、8.27%。
圖2 通信半徑與定位誤差關(guān)系圖
(3)節(jié)點總數(shù)對定位精度的影響
假設(shè)網(wǎng)絡(luò)節(jié)點的通信半徑為30 m時,信標(biāo)節(jié)點比例為10%,節(jié)點總數(shù)變化的仿真結(jié)果如圖3所示。從圖中可以看出,在通信半徑和信標(biāo)節(jié)點比例相同的情況下,節(jié)點的平均誤差隨著節(jié)點總數(shù)的增加而下降。隨著節(jié)點總數(shù)的變化,平均定位算法的變化幅度相對較大,這也反映了該算法的可擴展性有待進(jìn)一步提高。但是,本文算法定位精度明顯優(yōu)于傳統(tǒng)的DV-Hop算法和PSO-DV-Hop算法,平均定位誤差分別降低了10.85%、5.89%。
圖3 節(jié)點總數(shù)與定位誤差關(guān)系圖
本文闡述了典型DV-Hop定位算法的基本原理,分析了DV-Hop定位算法的誤差來源,并結(jié)合免疫粒子群優(yōu)化算法的特點,提出了一種免疫粒子群算法優(yōu)化的DV-Hop定位算法。在免疫粒子群算法中,通過調(diào)節(jié)機制使各適應(yīng)度的粒子維持一定濃度,保證群體的多樣性,克服粒子早熟,使得粒子快速收斂于全局最優(yōu)點,優(yōu)化待測節(jié)點位置坐標(biāo)。該算法在無需增加額外硬件設(shè)備的情況下,有效降低了定位誤差。但免疫粒子群算法的引入增加了算法復(fù)雜度,這將是下一步研究的重點。
參考文獻(xiàn)
[1] 錢志鴻, 孫大洋. 無線網(wǎng)絡(luò)定位綜述[J]. 計算機學(xué)報, 2016, 39(6): 1237-1256.
[2] 于泉, 孫順遠(yuǎn), 徐保國, 等. 基于改進(jìn)粒子群算法的無線傳感器網(wǎng)絡(luò)節(jié)點定位[J].計算機應(yīng)用, 2015, 35(6): 1519-1522.
[3] FEI J.Optimization of immune particleswarm algorithmand application on wireless sensornetworks[J]. Computer Modeling & New Technologies,2014,18(11):1443-15448.
[4] 高美鳳, 李鳳超. 遺傳粒子群優(yōu)化的 DV-Hop 定位算法[J]. 傳感技術(shù)學(xué)報, 2017, 30(7): 1083-1088.
[5] 王林,趙錦.一種基于誤差修正的改進(jìn)DV-Hop算法[J].計算機工程與應(yīng)用,2014,50(24): 109-112.
[6] TAO Q, ZHANG L. Enhancement of DV-Hop by weightedhopdistance[C]//Advanced Information Management, Communicates, Electronic and Automation Control Conference(IMCEC),2016 IEEE, 2016:1577-1580.
[7] 邴曉瑛,徐保國.基于改進(jìn)粒子群優(yōu)化的WSN定位算法[J]. 電子設(shè)計工程,2015,23(22): 143-146.
[8] 張超, 李擎, 王偉乾, 等. 基于自適應(yīng)搜索的免疫粒子群算法[J]. 工程科學(xué)學(xué)報, 2017, 39(1): 125-132.
[9] 張曉, 范虹, 張莉, 等. 融入免疫思想的改進(jìn)型粒子群優(yōu)化算法[J].陜西師范大學(xué)學(xué)報(自然科學(xué)版),2017,45(3): 17-23.
[10] Jiao Wei,Cheng Weimin,Zhang Mei,et al. A simpleand effective immune particle swarm optimization algorithm[C]// International Conference in Swarm Intelligence. Springer, Berlin,Heidelberg, 2012: 489-496.
[11] He Xingshi, Han Lin. A novel binary differential evolution algorithm based on artificial immune system [C]// Evolutionary Computation,IEEE,2007: 2267-2272.