免疫粒子群優化的DV-Hop定位算法

吳珍珍，方旺盛

(江西理工大學 信息工程學院，江西 贛州 341000)

0 引言

WSN節點定位技術是WSN應用于目標監測、目標識別和目標跟蹤的支撐技術，其算法可分為基于非測距(Range- free)的算法和基于測距(Range-based)的算法[1]，其中非測距DV-Hop算法因具有成本低、能耗小、算法實現簡單等特點而被廣泛應用，但該算法也存在定位誤差較大的不足。

為了提高DV-Hop算法的定位精度，國內學者對此引入群體智能算法進行優化。文獻[2]提出了一種改進的粒子群優化DV-Hop算法，從慣性權重的計算、粒子速度的更新等方面對粒子群算法進行改進，提高算法的搜索速度，再采用改進粒子群算法優化節點的定位結果，降低了定位誤差。文獻[3]利用免疫系統里的調節機制來提高種群的多樣性，避免了過早陷入局部最優解，優化的DV-Hop算法提高了定位效果，但該算法未考慮粒子群算法的收斂速度問題。文獻[4]使用遺傳機制中的前攝估計縮小粒子搜索范圍，再用改進粒子群算法以代替最小二乘法優化了DV-Hop算法定位精度。本文根據免疫粒子群算法的特點，利用該算法來優化DV-Hop定位算法求解未知節點的坐標。

1 DV-Hop定位算法

1.1 基本原理

DV-Hop(Distance Vector-Hop)是一種非測距定位算法。該算法依賴于節點間的互相通信，具體定位算法由3個階段組成[5]：

第一階段：信標節點通過全網泛洪廣播數據包，所有節點可以記錄下到每個信標節點的最小跳數。

第二階段：估算從未知節點到信標節點的跳距。

第三階段：利用三邊測量法或最小二乘法等計算未知節點坐標[6]。

1.2 定位誤差的分析

從DV-Hop的工作原理可知，其產生定位誤差的主要原因有跳數、平均每跳距離、定位的計算方法等。

(1)跳數信息不合理

WSN在定位時通過使用跳數信息計算節點之間的距離，而無線傳感器網絡中的節點大都是隨機分布，未知節點與錨節點之間并非都是直線距離，所以節點之間存在彎曲路徑，將會導致較大誤差。

(2)平均跳距的估計值不準確

在DV-Hop定位算法中，節點間的距離計算是采用同一個平均距離的估計值乘以對應的跳數來計算的，存在一定的定位誤差。

(3)定位的計算方法累計誤差

計算未知節點的坐標時經常采用三邊測量和極大似然估計法。三邊測量方法雖然降低了計算量，但其受限于第二階段的跳距估計。而在最大似然估計法求解過程中需要較多的浮點預算，計算開銷帶來的功耗不容忽視。

2 免疫粒子群優化的DV-Hop定位算法

鑒于上述誤差分析，針對經典DV-Hop定位算法在計算未知點坐標上存在較大誤差，本文提出了一種免疫粒子群優化的DV-Hop定位算法。

2.1 粒子群算法進化模型

粒子群優化(Particle Swarm Optimization,PSO)算法是1995年由Kennedy和Eberhart提出的一種新型的隨機群體智能的進化算法[7]。其原理為：在D維空間里有很多“粒子”，這些“粒子”通過“位置+速度”模型來更新自身的位置與速度，每個粒子不斷地搜索迭代，向最優值位置不斷地靠近[8]。該算法存在以下缺點：(1)容易陷入局部極小值，導致得不到全局最優解；(2)沒有充分的優選機制，收斂速度較慢。本文為了提高粒子群算法的全局搜索能力，借鑒免疫算法的思想改進PSO算法，當PSO算法陷入局部最優解時，通過免疫抗體的選擇、促進和抑制機制產生新的粒子空間，使該算法跳出局部最優值，避免“早熟”；另外生成的免疫記憶細胞可以加快收斂速度，確保快速收斂于全局最優解。

(1)

(2)

式中，c1表示個體學習因子，c2表示全局學習因子，而r1和r2為(0,1)上均勻分布的隨機數；ω為慣性權重，表示粒子運動的趨勢，對全局搜索和局部搜索起到平衡作用[9]。該系數按照公式(3)進行更新。

(3)

2.2 免疫機制

免疫機制源于生物免疫系統，其具體思路為將待優化適應度函數最優解看作入侵生命體的抗原，而免疫系統產生的抗體即為候選解，將個體最優解以免疫記憶形式保存于記憶細胞，提高收斂速度；根據免疫調節機制，選擇具有親和度高且濃度低的抗體進化，而親和度低濃度高的抗體加以抑制[10]；通過抗原抗體相互促進抑制來維持抗體的多樣性，克服了粒子群算法在實際工程優化計算中的早熟收斂現象，提高了算法的全局搜索效率。

(1)親和度

親和度[11]用來衡量抗原與抗體間的匹配程度，即所求的解與最優解的接近程度，記為aff，計算公式如下：

(4)

其中，f(xi)為xi的適應度函數，η為(0,1)上的常數。由上式可以看出，當f(xi)越小時，抗體的親和度越大，所求的解與最優解就越逼近。

(2)濃度

濃度表示抗體與其相似的粒子在群體中所占的比例，反映種群多樣性的程度。假設存在i個抗體x1,x2…,xi，每個抗體按照親和度從小到大排序并分成m個等份區間，其中m=1,2,…，m。計算每個區間的抗體數，記為sum(m)，得到每個區間的濃度為sum(m)/m，將每個抗體的濃度定義為該抗體所在區間的濃度，記為D，則有：

(5)

由上式可知，同一個區間上的抗體濃度是相同的，這使得抗體濃度越高反而越受到抑制，而抗體濃度越低反而得到進化的機會。

(3)選擇概率

選擇概率是指抗體在進化過程中得到促進發展的概率。假設基于親和度的選擇概率為Pa，而基于濃度的選擇概率為Pd，計算公式如下：

(6)

(7)

則抗體被選中的選擇概率P為：

P(xi)=αPa(xi)+(1-α)Pd(xi)

0<α,Pa,Pd<1

(8)

式中i=1,2,…,n；α為免疫協調因子，用來協調概率Pd和Pa的權重。從式(8)可以得知，濃度越高、親和力越低的抗體被選擇的概率越小；而濃度越低、親和力越高的抗體獲得進化的概率越大。這樣既提高了抗體的親和度，又保證了粒子的多樣性，從而得到較大的解空間。

(4)適應度函數

適應度函數即目標函數，用來評價給出的候選解(抗體)的優劣。計算公式如下：

(9)

其中，M(M≥3)為未知節點接收到的信標節點的個數；(x,y)和(xi,yi)分別表示粒子位置和第i個信標節點的坐標；di為未知節點到信標節點i的歐式距離。適應度函數f(i)的極小值點則為最優的定位坐標。

3 免疫粒子群優化的DV-Hop定位算法步驟

本文算法優化的DV-Hop算法步驟如下：

(1)初始化網絡區域、節點總數、粒子群相關參數。

(2)根據經典DV-Hop算法的第一和第二階段獲得每個信標節點和未知節點的最小跳數以及信標節點i的平均跳距，計算跳段距離。

(3)初始化粒子群。初始化粒子位置X、粒子速度V、歷史局部最優位置pbesti=Xi，計算種群的適應度函數值，取該值的最小值為粒子群的全局最優位置gbesti的初始值。

(4)免疫記憶。將粒子按親和度從小到大排序,取親和度較大的粒子存入免疫記憶細胞中。

(5)利用式(1)、式(2)分別更新粒子的飛行速度和位置，產生n個新的抗體，然后從免疫記憶細胞中抽取q個抗體，組成規模為n+q的抗體群。

(6)免疫替換，丟棄位置較差的粒子(抗體)。利用式(4)～(8)計算抗體的選擇概率，依據選擇概率從n+q個抗體中選擇出n個抗體，則選擇概率大的抗體將被選中，組成新的抗體群，從而實現抗體的多樣性，避免出現“早熟”。

(7)根據式(9)計算抗體的適應度大小，比較所有粒子當前的適應度值F(Xi)和局部最優位置適應度值F(pbesti)，若F(pbesti)>F(Xi)，則更新pbest值;再用更新后局部最優適應函數值F(pbesti)與全局最優位置的適應函數F(gbesti)比較，若F(gbesti)>F(pbesti)，則更新gbest值。

(8)若滿足終止條件，則輸出全局最優解gbesti，適應度函數F(gbesti)的極小值點即為未知節點的最終定位坐標。否則返回步驟(4)。

4 實驗與仿真

4.1 實驗環境和參數設置

為驗證本文算法的有效性，本文基于Windows 10操作系統的MATLAB 2014平臺進行仿真實驗。本文試驗場景設置為100 m×100 m的二維正方形區域，假設所有WSN網絡節點的通信半徑都為R。

免疫粒子群算法的初始化參數如表1所示。

表1 仿真參數

4.2 仿真分析

(1)信標節點比例對定位精度的影響

假設通信半徑為30 m、節點總數為100，圖1給出信標節點比例對定位精度的影響關系圖。從圖中可以看出，3種定位算法的平均定位誤差都隨著信標節點的比例增加而減小。當信標節點比例相同時，本文算法的平均定位誤差與DV-Hop以及PSO-DV-Hop定位算法比較降低了15.03%、4.86%。另外，本文算法平均定位誤差曲線更平滑，表明其穩定性更好。

圖1 信標節點比例與定位誤差關系圖

(2)通信半徑對定位精度的影響

假設節點總數為100時，信標節點比例為10%，改變通信半徑進行仿真，結果如圖2所示。從圖中可以看出，在通信半徑小于30 m時，3種定位算法的平均定位誤差都隨著通信半徑的增大而明顯減小，這是因為通信半徑的增大提高了未知節點與信標節點的連通性，從而可以獲得更大范圍的信息交換來提高定位精度。但在通信半徑大于30 m時，平均定位誤差緩慢減小，趨于平滑，因此通信半徑并不是越大越好，通信半徑的增大也將提高通信開銷。另外，從3種算法對比可以看出，本文算法的定位誤差與經典DV-Hop、PSO-DV-Hop定位算法相比，定位精度提高了13.27%、8.27%。

圖2 通信半徑與定位誤差關系圖

(3)節點總數對定位精度的影響

假設網絡節點的通信半徑為30 m時，信標節點比例為10%，節點總數變化的仿真結果如圖3所示。從圖中可以看出，在通信半徑和信標節點比例相同的情況下，節點的平均誤差隨著節點總數的增加而下降。隨著節點總數的變化，平均定位算法的變化幅度相對較大，這也反映了該算法的可擴展性有待進一步提高。但是，本文算法定位精度明顯優于傳統的DV-Hop算法和PSO-DV-Hop算法，平均定位誤差分別降低了10.85%、5.89%。

圖3 節點總數與定位誤差關系圖

5 結論

本文闡述了典型DV-Hop定位算法的基本原理，分析了DV-Hop定位算法的誤差來源，并結合免疫粒子群優化算法的特點，提出了一種免疫粒子群算法優化的DV-Hop定位算法。在免疫粒子群算法中，通過調節機制使各適應度的粒子維持一定濃度，保證群體的多樣性，克服粒子早熟，使得粒子快速收斂于全局最優點，優化待測節點位置坐標。該算法在無需增加額外硬件設備的情況下，有效降低了定位誤差。但免疫粒子群算法的引入增加了算法復雜度，這將是下一步研究的重點。

參考文獻

[1] 錢志鴻, 孫大洋. 無線網絡定位綜述[J]. 計算機學報, 2016, 39(6): 1237-1256.

[2] 于泉, 孫順遠, 徐保國, 等. 基于改進粒子群算法的無線傳感器網絡節點定位[J].計算機應用, 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] 高美鳳, 李鳳超. 遺傳粒子群優化的 DV-Hop 定位算法[J]. 傳感技術學報, 2017, 30(7): 1083-1088.

[5] 王林,趙錦.一種基于誤差修正的改進DV-Hop算法[J].計算機工程與應用,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] 邴曉瑛,徐保國.基于改進粒子群優化的WSN定位算法[J]. 電子設計工程,2015，23(22): 143-146.

[8] 張超, 李擎, 王偉乾, 等. 基于自適應搜索的免疫粒子群算法[J]. 工程科學學報, 2017, 39(1): 125-132.

[9] 張曉, 范虹, 張莉, 等. 融入免疫思想的改進型粒子群優化算法[J].陜西師范大學學報(自然科學版),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.