基于粒子群優(yōu)化的DV-Hop算法研究

楊秋菊

(宿州職業(yè)技術(shù)學(xué)院 計(jì)算機(jī)信息系，安徽 宿州 234101)

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

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

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

1 DV-Hop算法

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

1.1 DV-Hop定位算法步驟

DV-Hop定位分三步進(jìn)行:

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

步驟二：估算距離[9]。在區(qū)域中錨節(jié)點(diǎn)可以獲取未知節(jié)點(diǎn)的坐標(biāo)值以及相隔路徑的最小跳數(shù)，可以根據(jù)公式1來計(jì)算平均跳距：

(1)

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

隨后錨節(jié)點(diǎn)開始播報(bào)自己的平均跳距，當(dāng)網(wǎng)絡(luò)區(qū)域內(nèi)的其他未知節(jié)點(diǎn)得知后，通過計(jì)算只保留離自己最近的錨節(jié)點(diǎn)的平均跳距，再對錨節(jié)點(diǎn)間的平均跳距和最小跳數(shù)進(jìn)行乘法計(jì)算從而計(jì)算得出每個錨節(jié)點(diǎn)和未知節(jié)點(diǎn)的距離如公式(2)所示：

dij=HopSizei*hij，

(2)

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

步驟三：計(jì)算未知節(jié)點(diǎn)位置。當(dāng)確定三個節(jié)點(diǎn)的坐標(biāo)值以及它們到達(dá)未知節(jié)點(diǎn)的距離時，想要得到未知節(jié)點(diǎn)的坐標(biāo)可以通過三邊測量法、極大似然估計(jì)法或最小二乘法計(jì)算得出。

1.2 定位誤差分析

1.2.1 每跳距產(chǎn)生的誤差

圖1 單跳距示意圖

假設(shè)每個錨節(jié)點(diǎn)的通信輻射圓內(nèi)都存在N個未知節(jié)點(diǎn)，未知節(jié)點(diǎn)和錨節(jié)點(diǎn)之間可以直接產(chǎn)生通信的距離都被認(rèn)為是一個跳距，然而實(shí)際中因錨節(jié)點(diǎn)的自身拓?fù)浣Y(jié)構(gòu)不同會造成不同的未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的單跳距離并不是相同的，所以就會導(dǎo)致因跳數(shù)誤差造成定位的誤差。如圖1所示，其中D為錨節(jié)點(diǎn)，A、B、C為未知節(jié)點(diǎn)。

1.2.2 節(jié)點(diǎn)隨機(jī)性產(chǎn)生誤差

節(jié)點(diǎn)的位置安排是隨機(jī)產(chǎn)生的，這樣會造成拓?fù)浣Y(jié)構(gòu)的不規(guī)則和節(jié)點(diǎn)不均衡分布性，有的大片區(qū)域錨節(jié)點(diǎn)相對比較少而小片區(qū)域反而錨節(jié)點(diǎn)比較多，故定位存在較大誤差。

2 粒子群算法

PSO[10]粒子群算法是Kennedy和Eberhart在1995年通過研究鳥類的群體遷徙和魚群的集聚的群體行為總結(jié)而成的基于群體智能的全局隨機(jī)搜索算法。其原理是：隨機(jī)粒子群中的每個粒子在每4次迭代中通過Pbest和Gbest兩個值來找到最佳結(jié)果。粒子的速度計(jì)算公式為公式(3)，粒子的位置計(jì)算公式為公式(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表示慣性權(quán)重； c1， c2表示加速常數(shù)； r為[0， 1]區(qū)間內(nèi)隨機(jī)數(shù)，i=1,2,3,…,n(群中粒子個數(shù))；vi的最大值vmax，假設(shè)vmax小于vi則二者值相等。

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

圖2 粒子群算法流程圖

3 改進(jìn)的FPDV-Hop算法

3.1 修正錨點(diǎn)間跳數(shù)

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

(5)

(6)

(7)

(8)

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

3.2 再次部署錨節(jié)點(diǎn)

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

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

(9)

(10)

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

表1 錨節(jié)點(diǎn)與平均值比較關(guān)系

3.3 基于粒子群的優(yōu)化算法FPDV-Hop

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

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

(11)

在上述公式中：xi,yi和xj,yj表示錨節(jié)點(diǎn)i和j坐標(biāo)，m表示實(shí)際偏離值，dj表示未知節(jié)點(diǎn)j和錨節(jié)點(diǎn)之間的距離。

優(yōu)化算法流程如圖3所示。

4 仿真分析

平均定位誤差[13]作為仿真實(shí)驗(yàn)過程中衡量算法精準(zhǔn)度的標(biāo)準(zhǔn)值，其計(jì)算公式為:

(12)

在公式(12)中，N是實(shí)驗(yàn)區(qū)域中需要定位的節(jié)點(diǎn)總個數(shù)，R為輻射半徑，k為仿真次數(shù)，xi,yi和xki,ykj表示未知節(jié)點(diǎn)的真實(shí)坐標(biāo)和估算坐標(biāo)。

圖3 優(yōu)化算法流程圖

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

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

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

圖5 錨節(jié)點(diǎn)數(shù)對誤差的影響

圖6 總節(jié)點(diǎn)數(shù)目對誤差的影響

5 結(jié)語

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