基于距離優化和改進粒子群的節點定位算法

張 溪，毛永毅，徐 萍

(1.西安郵電大學 電子工程學院，陜西 西安 710061；2.火箭軍工程大學 理學院，陜西 西安 710025)

0 引 言

在無線傳感器網絡定位技術的兩大分類中，基于測距的定位算法需要額外的硬件支持才能獲取所需信息，而無需測距的定位算法依賴于網絡間的連通和跳數值信息，其設備簡單、功耗低、效率高[1-3]。

DV-Hop算法作為一種易實現的典型無需測距算法被廣泛應用于無線傳感網絡定位中[4]，對于該算法定位精度不高這一問題，學者們不斷探索并嘗試改進。文獻[5]用高斯牛頓法替代定位階段的最小二乘法，減少誤差傳播。文獻[6]利用跳距誤差和估計距離誤差的加權平均值去修正平均跳距，并引入改進粒子群算法計算未知節點坐標。文獻[7]中對來自多個錨節點的跳數值進行加權操作用于平均跳距離的估計。文獻[8]使用節點間最小跳數值和錨節點的位置信息，通過細菌覓食優化算法計算平均距離，使跳距誤差盡可能小。

各類改進算法的側重點在于減小估計距離誤差和盡可能避免定位階段誤差的累積。因此，本文算法通過對節點間距離的優化和改進的自適應粒子群算法對DV-Hop算法進行改進，仿真結果表明，本文DPDV-Hop算法較原始DV-Hop算法和文獻[6]中的BDV-Hop算法在定位精度方面有更優異的表現。

1 DPDV-Hop算法

1.1 估計距離優化

節點間估計距離是由平均跳距與跳數值的乘積所決定的，因此平均跳距的誤差將直接影響估計距離的精確度。為了能使估計距離的誤差減小，利用錨節點間單跳平均誤差對平均跳距進行修正，使之接近真實值。估計距離的最終結果與平均跳距的選取方式存在一定關系，接收網通范圍內所有錨節點平均跳距并參與運算的策略，能考慮全局信息使估計距離得以優化。

1.1.1 平均跳距修正

(1)

(2)

(3)

錨節點i的單跳平均誤差可由式(4)計算得出，其中n為錨節點個數

(4)

(5)

1.1.2 多錨節點平均跳距估計距離

在估計節點間距離階段，DV-Hop算法中待求未知節點根據就近原則只接收錨節點傳遞過來的第一個平均跳距信息。然而網絡分布是具有隨機性的，數據的單一選擇不可避免的增加了偶然性，以至于影響后期定位。盡可能多地使用網絡中信息即求到哪一點的估計距離用該點的平均跳距，不僅能考慮到全局信息而且在一定程度上降低了偶然性，使定位精度有所改善。

圖1 網絡拓撲結構

各節點平均跳距

HopSizeA=(25+20)/(3+4)≈6.428 mHopSizeB=(25+42)/(3+5)≈8.375 mHopSizeC=(20+42)/(4+5)≈6.888 m

使用各節點平均跳距通過不同策略估算節點間距離，結果見表1。

表1 節點間實際距離與估計距離

觀察表1發現，提出策略能使估計距離更接近真實值。

1.2 改進的粒子群算法MI-PSO

1.2.1 粒子群優化算法

粒子群優化(particle swarm optimization，PSO)算法被Kennedy和Eberhart提出[9]。作為一種基于人口的元啟發式搜索算法，它模擬了鳥類和魚類在尋找食物方面的協作行為[10]。PSO算法中的每個人(即粒子)表示優化問題的潛在解決方案，而食物源的位置就是全局最優解。每個粒子相互獨立并隨機的尋找食物，它們之間還彼此協作和共享信息，通過不斷地搜索尋求問題的最優解。

若目標搜索空間為D維，初始粒子數量為N，則粒子位置矢量可表示為Si=(si1,si2,…siN)，i=1,2,…,N， 粒子速度矢量可表示為Vi=(vi1,vi2,…viD)。 第i顆粒子現階段所處的最優位置可表示為pi=(pi1,pi2,…,piN)， 整個種群的最優位置可表示為pg=(pg1,pg2,…,pgN)。 在每一輪的更新中，粒子對比這兩個極值來改變自己的位置和速度，如式(6)所示

(6)

式中：k為粒子當前迭代次數；ω為慣性權重；c1、c2為加速度常數；r1、r2為(0，1)內的隨機常數。

1.2.2 基于成功率PS的自適應慣性權重策略

通常式(6)中的慣性權重ω為一常數，ω越大則越利于全局尋優值，ω越小則越利于局部尋優值。為兼顧全局和局部尋優，提出自適應慣性權重策略。

實現自適應權重策略的重要之處在于每次迭代完成時需合理評估群體的位置。而本文提出的粒子成功率PS能表現群體現狀，較高的PS值表示粒子向最佳解決方案靠近，并處于收斂狀態，而較低的PS值意味著粒子在沒有很大改進的情況下徘徊于最佳解決方案附近。因此，將粒子的成功率PS用于自適應地更新速度能有效提升收斂速度。使用粒子面向最佳解決方案的成功計數SC來確定PS的值。若當前迭代的適應度小于前一次迭代的適應度，則將SC值設置為1，否則將其設置為0，如式(7)所示

(7)

將所有的SC計數累加求和并由式(8)計算出成功率PS，其中N表示粒子數量

(8)

自適應慣性權重因子ω的設置如式(9)所示，粒子根據百分比形式的成功率自適應地更新慣性權重

ω=(ωmax-ωmin)×PS+ωmin

(9)

慣性權重(ωminωmax)的范圍被設為[0，1]。因為PS為成功率，它的值總是在0～1之間，這就使慣性重量在可接受范圍內。

1.2.3 變異算子參與運算策略

在PSO算法的執行過程中，粒子總是向最優解靠攏。若這一最優解為局部最優解，隨著粒子的逐漸聚集，粒子便難以趨近于全局最優解，導致過早收斂即早熟現象[11]。

(10)

1.2.4 適應度函數設置

盡管在文章1.1節對節點間估計距離有所優化，但其誤差并沒有完全消除，考慮到估計距離所攜帶的誤差，得到式(11)，其中εi,i=1,2,…n表示距離誤差

(11)

(12)

通過多次迭代使fitness(x,y)的值最小，以提升定位精度。

2 DPDV-Hop算法流程

步驟1 錨節點利用洪泛機制向全網廣播自身信息，根據錨節點所獲取的位置信息和最小跳數值計算平均跳距。

步驟4 若粒子si的變異概率Pc>rand(0～1)， 則執行步驟5，否則執行步驟6。

步驟6 比較更新后各粒子本次與上次的適應度值，由式(7)、式(8)計算成功率PS并帶入式(9)中更新權重ω。記錄本次迭代的個體最優位置pi和歷史最優位置pg。

步驟7 將步驟6計算出的權重帶入式(6)，用于對速度和位置的更新。

重復步驟4～步驟7直到達到最大迭代次數，輸出最優適應度值及對應的粒子位置。

3 仿真實驗

為了驗證改進算法的性能，在Windows7的MATLAB R2014a環境下進行仿真實驗。將擁有相同通信半徑的100個節點隨機分布在邊長為100 m的二維方形區域內，如圖2所示，其中○代表未知節點，*代表錨節點。初始化粒子個數N為30，最大迭代次數itmax為100。

圖2 節點分布

采用歸一化相對誤差作為性能評價指標，如式(13)所示

(13)

式中：(xr,yr)表示未知節點的真實坐標，(xi,yi)表示未知節點的估計坐標，R表示節點的通信半徑，N表示未知節點數。

就DPDV-Hop算法本身而言，在對距離優化的同時也利用I-PSO算法替代了定位階段的最大似然估計法。為了驗證這兩方面的改進均對定位精度的提升有所幫助，對DPDV-Hop算法分步仿真。當錨節點數占未知節點數量的20%，通信半徑逐漸增加時，觀察每個改進點在上述實驗環境和初始條件下的定位表現。

圖3表示錨節點數為20，分步加入距離優化和I-PSO算法后，通信半徑從20 m～50 m的平均定位誤差曲線。觀察發現，通信半徑從20 m～40 m這一階段3條曲線整體呈下降趨勢，這是由于網絡連通度提升所導致的，而在半徑大于40 m后表現出的上升趨勢，是由于過大的通信半徑使平均跳距誤差增大帶來的影響。因此，不必一味要求過大的通信半徑，應合理選取。且這兩個方面改進均降低了算法的定位誤差，在加入I-PSO算法后的效果尤為明顯，故DPDV-Hop算法是可行的。

圖3 通信半徑不同時平均定位誤差曲線

圖4 錨節點數不同時平均定位誤差曲線

為了驗證DPDV-Hop算法的優越性，在不同錨節點數、通信半徑下，對DV-Hop算法、文獻[6]中的BDV-Hop算法與本文DPDV-Hop算法分別進行仿真，對比結果給予分析。

(1)不同錨節點數

圖4表示節點通信半徑為30 m，錨節點數從5-30時3種算法的平均定位誤差曲線。觀察發現，3種算法的誤差曲線隨錨節點的增加而降低，在錨節點數小于20時下降尤為明顯，之后趨于平穩。這是由于錨節點密度的增大使其之間的跳數減小，這就有效減小了因高跳數所帶來的誤差累積，減少了距離誤差。經計算，DPDV-Hop算法的平均定位誤差比BDV-Hop算法和DV-Hop算法分別相對減少了39.97%和13.58%。

(2)不同通信半徑

圖5表示錨節點數占總節點數20%情況下，通信半徑從20 m～50 m時3種算法的平均定位誤差曲線。觀察發現，當通信半徑小于40 m時3種算法的曲線均處于下降趨勢，大于40 m后又緩慢上升，導致此現象的原因與圖3所分析的原因一致。且從圖5中可明顯看出，DPDV-Hop算法在任何通信半徑下的定位表現均優于與之對比的2種算法。經計算，不同通信半徑下DPDV-Hop算法的平均定位誤差比DV-Hop算法和BDV-Hop算法分別相對減少了40.56%和14.74%。

圖5 通信半徑不同時平均定位誤差曲線

4 結束語

本文算法利用單跳平均誤差修正了平均跳距，采用多錨節點平均跳距估計節點間距離，使估計距離得以優化。利用粒子成功率PS動態調節粒子群優化算法的慣性權重ω，加速收斂。產生變異算子并擇優處理，避免早熟現象。用I-PSO算法的自適應迭代尋替代最大似然估計算法，降低了距離誤差對最終定位的影響。仿真結果表明，本文算法在不增加硬件開銷的基礎上，提升了定位精度，適合在實際中應用。