楊秋菊

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

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

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

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

1 DV-Hop算法

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

1.1 DV-Hop定位算法步驟

DV-Hop定位分三步進行:

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

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

(1)

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

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

dij=HopSizei*hij，

(2)

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

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

1.2 定位誤差分析

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

圖1 單跳距示意圖

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

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

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

2 粒子群算法

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

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

圖2 粒子群算法流程圖

3 改進的FPDV-Hop算法

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

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

(5)

(6)

(7)

(8)

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

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

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

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

(9)

(10)

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

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

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

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

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

(11)

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

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

4 仿真分析

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

(12)

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

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

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

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

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

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

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

5 結(jié)語

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