基于粒子群優化的DV-Hop算法研究

楊秋菊

(宿州職業技術學院 計算機信息系，安徽 宿州 234101)

WSN(Wireless Sensor Networks)是一種新的計算方式，已然成為國內外研究焦點之一，無線傳感器網絡技術的快速發展離不開MEMS、SOC和無線通信和嵌入式技術。無線傳感器網絡是由部署在檢測區域內大量的微型傳感器節點以自組織和多跳的方式構成的無線網絡[1]。在無線傳感器眾多技術中最為關鍵的就是節點定位的準確性，沒有精確的定位信息，無線傳感器節點所監測到相關的數據信息就沒有意義[2]。

根據測距與否，定位方式可以分為Range-Based(測距)和Range-Free(非測距)。測距的定位技術的特點是定位精準，典型的方法有TOA、TDOA、RSSI和AOA等。非測距的定位方法是根據預估節點之間的大致距離來計算定位節點的位置，受環境影響比較小，但定位誤差較大。無論從效率方面還是從性價比方面來考量，無須測距的定位算法比基于測距的定位算法更具優勢，典型的算法有：DV-Hop、APIT、MDS-MAP和質心等。

Alkhayri提出聚類選擇法，采用新的選擇算子，優點是迭代次數降低了，可是收斂性也隨之變差了[3]；Mass-SanchezJ等提出針對基于粒子群的DV-Hop算法和傳統的DV-Hop算法相比較，通過對多種Range-Free定位技術進行評估得出基于PSO的DV-Hop算法，其定位更精確，但是容易造成局部最優的現象[4]；于泉等提出通過改變粒子速度和慣性權重進行改進粒子群算法，使未知節點進行節點坐標子定位，在提高后期算法的搜索速度同時增加了計算量[5]；卞國龍等提出基于PSO-BP傳感器定位改進，利用卡爾曼算法對信號強度值優化，旨在降低誤差和降噪，該算法在得到全局最優值的同時規避局部最優值，對完善神經網絡定位算法效果顯著[6]。DV-Hop算法定位誤差大而粒子群算法會出現局部最優現象，基于這兩點本文提出一種改進的算法，利用修正跳數重新分布靜態錨節點并按密度進行再次部署，用粒子適應度優化定位過程迭代，以提高定位的準確性。

1 DV-Hop算法

APS[7]是6種算法集合而成，它是由Dragos Niculescu和Bsdri Nath兩位美國學者研究而成，其設計原理是距離矢量路由和全球定位系統，其中DV-Hop算法是APS中用處最廣的一種算法。DV-Hop 算法的核心思想：首先，尋找最小跳數并計算矯正值；然后，二者進行相乘計算以預估信標節點和未知節點之間的距離。

1.1 DV-Hop定位算法步驟

DV-Hop定位分三步進行:

步驟一：計算未知節點與錨節點的跳數最小值[8]。首先，錨節點向區域內所有未知節點播報自己的數據信息，在錨節點攜帶的信息數據中包括初始值為0的跳數值hi、唯一標識編號ID和具體的位置坐標(xi,yi),格式如{id，xi,yi，hi}。然后，節點接收數據包后將跳數值增加1再播報給其鄰居節點，網絡區域中的所有節點都可以記錄錨節點的位置以及跳數。最后，通過節點對同一個錨節點的跳數值進行比較篩選，找出最小跳數值所在的信息包進行記錄，其他的跳數值較大的信息包將被摒棄。

步驟二：估算距離[9]。在區域中錨節點可以獲取未知節點的坐標值以及相隔路徑的最小跳數，可以根據公式1來計算平均跳距：

(1)

在公式(1)中，HopSizei代表i作為錨節點的平均跳距，錨節點i和j坐標的表示方法為(xi,yi) 和(xj,yj) ，hij(i和j不相等)為節點i與節點j之間的最小跳數。

隨后錨節點開始播報自己的平均跳距，當網絡區域內的其他未知節點得知后，通過計算只保留離自己最近的錨節點的平均跳距，再對錨節點間的平均跳距和最小跳數進行乘法計算從而計算得出每個錨節點和未知節點的距離如公式(2)所示：

dij=HopSizei*hij，

(2)

公式(2)中，HopSizei表示未知節點的平均跳距，dij表示未知節點j和錨節點i之間的距離，hij是二者之間的跳數最小值。

步驟三：計算未知節點位置。當確定三個節點的坐標值以及它們到達未知節點的距離時，想要得到未知節點的坐標可以通過三邊測量法、極大似然估計法或最小二乘法計算得出。

1.2 定位誤差分析

1.2.1 每跳距產生的誤差

圖1 單跳距示意圖

假設每個錨節點的通信輻射圓內都存在N個未知節點，未知節點和錨節點之間可以直接產生通信的距離都被認為是一個跳距，然而實際中因錨節點的自身拓撲結構不同會造成不同的未知節點到錨節點的單跳距離并不是相同的，所以就會導致因跳數誤差造成定位的誤差。如圖1所示，其中D為錨節點，A、B、C為未知節點。

1.2.2 節點隨機性產生誤差

節點的位置安排是隨機產生的，這樣會造成拓撲結構的不規則和節點不均衡分布性，有的大片區域錨節點相對比較少而小片區域反而錨節點比較多，故定位存在較大誤差。

2 粒子群算法

PSO[10]粒子群算法是Kennedy和Eberhart在1995年通過研究鳥類的群體遷徙和魚群的集聚的群體行為總結而成的基于群體智能的全局隨機搜索算法。其原理是：隨機粒子群中的每個粒子在每4次迭代中通過Pbest和Gbest兩個值來找到最佳結果。粒子的速度計算公式為公式(3)，粒子的位置計算公式為公式(4)。

vi(t+1)=w·vi(t)+c1·r1(Pbesti-xi(t))+c2·r2(Gbesti-xi(t))，

(3)

xi(t+1)=xi(t)+vi(t+1)，

(4)

在公式(3)(4)中： w表示慣性權重； c1， c2表示加速常數； r為[0， 1]區間內隨機數，i=1,2,3,…,n(群中粒子個數)；vi的最大值vmax，假設vmax小于vi則二者值相等。

粒子群算法的流程圖如圖2所示：

圖2 粒子群算法流程圖

3 改進的FPDV-Hop算法

3.1 修正錨點間跳數

DV-Hop算法中，平均跳距是實際距離除以跳數的值，所以跳數越多誤差越大，本文使用跳數因子修正跳數，規避誤差大的錨節點。公式(5)(6)(7)計算最佳跳數Hij、實際偏離值Mij和跳數調整因子λij，公式(8)利用跳數調整因子修正跳數。

(5)

(6)

(7)

(8)

在上述4個公式中：dij表示未知節點j和錨節點i之間的距離，hij(i和j不相等)為節點i與節點j之間的最小跳數，R表示節點通信半徑。

3.2 再次部署錨節點

平均分布、密度分布、間隔閾值分布是常見的錨節點的部署方式[11]，采用密度分布把區域平均分成6個部分，設區域內錨節點為N個，則Ni表示第i區域的錨節點總數，即公式(9)和公式(10)分別為目標區域的錨節點總數和每個區域的錨節點平均數。

N=N1+N2+N3+N4+N5+N6,

(9)

(10)

表1為通過對比錨節點總數值和平均值判斷是否有多余錨節點，公式(10)中如果產生余數則表示為M，M≠0時則分配M個節點至M個隨機生成的位置。

表1 錨節點與平均值比較關系

3.3 基于粒子群的優化算法FPDV-Hop

利用粒子群算法進行定位優化，假設最優位置為A點，那么局域內的所有粒子都按照“位置+速度”來不停更新，不斷接近A點，第i個粒子將同時受到3個因素影響不停地搜索迭代并且向A點移動。

本文提出的FPDV-Hop算法中通過公式11計算fitnessi[12](粒子適應度)來計算更新個體最優值Pbest和全局最優值Gbest，進而更新粒子群中的粒子速度和位置，通過判斷是否滿足迭代條件來決定是否結束迭代，不滿足的情況下再次對每個粒子的Pbest進行比較，釋放粒子群中最遠的粒子。

(11)

在上述公式中：xi,yi和xj,yj表示錨節點i和j坐標，m表示實際偏離值，dj表示未知節點j和錨節點之間的距離。

優化算法流程如圖3所示。

4 仿真分析

平均定位誤差[13]作為仿真實驗過程中衡量算法精準度的標準值，其計算公式為:

(12)

在公式(12)中，N是實驗區域中需要定位的節點總個數，R為輻射半徑，k為仿真次數，xi,yi和xki,ykj表示未知節點的真實坐標和估算坐標。

圖3 優化算法流程圖

圖4表明仿真實驗環境下，設置通信半徑分別取15、20、25、30、35、40，分別對DV-Hop算法、WSN改進DV-Hop定位算法[14]以及改進的FPDV-Hop算法進行平均誤差值的計算。總體而言，改進的FPDV-Hop算法相比較DV-Hop算法和WSN改進DV-Hop算法，平均定位誤差最小，通信半徑變大后致使節點路徑的選擇變少，這種情況下的整體性能優于其他兩種算法。

圖4表明仿真實驗環境下，錨節點數分別取10、20、30、40時本文算法和DV-hop算法、WSN改進DV-Hop算法比較，3種算法的定位效果隨著錨節點增長而增長。當錨節點取值在20時，DV-Hop算法平均定位誤差和WSN改進DV-Hop算法為0.277和0.239，改進的FPDV-Hop算法為0.171，并且整體性能表現較好。圖6表明總節點在[100，250]這個取值范圍內，每次遞加50進行仿真實驗，從圖中可以得知DV-Hop算法、WSN改進DV-Hop算法和FPDV-Hop的誤差都出現逐漸下降，當總節點數呈增加狀態時，改進算法的定位誤差最小。

圖4 通信半徑對誤差的影響

圖5 錨節點數對誤差的影響

圖6 總節點數目對誤差的影響

5 結語

針對傳統DV-Hop算法定位精準度偏低的問題，本文在引入PSO(均值粒子群算法)優化的基礎上提出了一種改進的算法FPDV-Hop。改進的算法，首先，通過跳數因子修正跳數并對錨節點按密度重新分配部署；其次，引入粒子群算法進行定位優化。在改進過程中使用粒子自適應度優化定位過程，通過對通信半徑、錨節點數和總節點數利用歸一化的平均定位誤差進行仿真分析，從結果可以看出改進的算法使無線傳感器網絡的定位精度得到了有效地提高。