改進(jìn)的無線傳感器網(wǎng)絡(luò)DV-Hop節(jié)點(diǎn)定位算法

童宇行，黃 鵬，劉玉紅

(蘭州交通大學(xué) 電子與信息工程學(xué)院，甘肅 蘭州 730070)

無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)是由大量安放在監(jiān)測區(qū)域內(nèi)的無線傳感器節(jié)點(diǎn)組成[1]。具有低成本、體積小、傳輸距離遠(yuǎn)等優(yōu)勢(shì)，廣泛應(yīng)用于軍事、醫(yī)療環(huán)境監(jiān)測等方面[2]。

在無線傳感器網(wǎng)絡(luò)的應(yīng)用中，傳感器節(jié)點(diǎn)的位置信息至關(guān)重要，無論是環(huán)境監(jiān)測、地震實(shí)時(shí)監(jiān)控或者礦井危險(xiǎn)監(jiān)測等應(yīng)用場合都需要傳感器節(jié)點(diǎn)提供精確的位置信息[3]。無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法根據(jù)是否測量節(jié)點(diǎn)間距可以分為兩大類：基于測距(Range-Based)的定位技術(shù)和無需測距(Range-Free)的定位技術(shù)[4]。測距技術(shù)有RSSI、TOA、TDOA[5]等，無需測距的定位算法有質(zhì)心算法、APIT算法、DV-Hop算法和凸規(guī)劃算法等[5]。本文在文獻(xiàn)[6]的基礎(chǔ)上，利用粒子群(PSO,Particle Swarm Optimization)優(yōu)化算法對(duì)定位結(jié)果進(jìn)行優(yōu)化處理，以得到良好的定位精度。

1 DV-Hop定位算法

DV-Hop算法[7]的基本原理是距離向量路由機(jī)制[8]，主要通過距離矢量和跳數(shù)信息來估測未知節(jié)點(diǎn)到錨節(jié)點(diǎn)的距離。

DV-Hop算法主要由以下3個(gè)步驟組成[9]：

(1)網(wǎng)絡(luò)中所有的錨節(jié)點(diǎn)以洪泛的方式將自身的位置信息以及跳數(shù)信息傳播給相鄰節(jié)點(diǎn)，其中跳數(shù)信息初始值為0。接收節(jié)點(diǎn)只保留到每個(gè)錨節(jié)點(diǎn)的最小跳數(shù)，忽略同一個(gè)錨節(jié)點(diǎn)發(fā)送的較大的跳數(shù)信息。然后將跳數(shù)值加1并繼續(xù)轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)，最終整個(gè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)都能保留自身到每個(gè)錨節(jié)點(diǎn)的最小跳數(shù)；

(2)每個(gè)錨節(jié)點(diǎn)記錄了其他錨節(jié)點(diǎn)的位置信息和跳數(shù)信息后，此時(shí)可以利用式(1)來估算錨節(jié)點(diǎn)之間的平均每跳距離，然后將此平均跳距廣播到整個(gè)網(wǎng)絡(luò)。網(wǎng)絡(luò)中未知節(jié)點(diǎn)接收到該信息后，將其與到各錨節(jié)點(diǎn)的跳數(shù)的乘積作為未知節(jié)點(diǎn)到各錨節(jié)點(diǎn)距離的估算量[10]。最后，錨節(jié)點(diǎn)將計(jì)算得到的HopSizei用帶有生存周期的字段已洪泛的方式廣播到整個(gè)網(wǎng)絡(luò)中。

(1)

(3)使用最小二乘法計(jì)算未知節(jié)點(diǎn)坐標(biāo)[11]。對(duì)于未知節(jié)點(diǎn)M，根據(jù)第一階段和第二階段所得可計(jì)算出其與n個(gè)錨節(jié)點(diǎn)的距離分別為(d1，d2，d3，…，dn)，最后根據(jù)坐標(biāo)關(guān)系可得到方程組

(2)

將上式變換可得

(3)

式(3)可化為

AX=B

(4)

其中，

則未知節(jié)點(diǎn)M的坐標(biāo)

X=(ATA)-1ATB

(5)

2 改進(jìn)的DV-Hop定位算法

2.1 跳數(shù)改進(jìn)

本文的改進(jìn)算法主要是針對(duì)DV-Hop算法中的第一階段和第三階段，主要從以下幾方面進(jìn)行改進(jìn)：

(1)跳數(shù)改進(jìn)。在第一階段中設(shè)置一個(gè)最小跳數(shù)閥值TN。設(shè)定TN為某一閥值，m為節(jié)點(diǎn)間的測得的最小跳數(shù)，如果m>TN，則m=TN；如果m≥TN，則跳數(shù)保持不變。引入最小跳數(shù)閥值能有效的減小節(jié)點(diǎn)在以泛洪方式廣播位置信息時(shí)數(shù)據(jù)沖突所帶來的誤差[12]；

(2)修正錨節(jié)點(diǎn)平均跳距。原始的DV-Hop算法計(jì)算平均跳距的方法是利用距離未知節(jié)點(diǎn)最近的錨節(jié)點(diǎn)位置信息[13]，其他錨節(jié)點(diǎn)對(duì)于未知節(jié)點(diǎn)定位結(jié)果的影響就被忽略了。因此對(duì)所有錨節(jié)點(diǎn)的平均跳距進(jìn)行加權(quán)處理，其中加權(quán)系數(shù)與未知節(jié)點(diǎn)到該錨節(jié)點(diǎn)的跳數(shù)成反比。已知節(jié)點(diǎn)i的權(quán)值計(jì)算如式(6)所示，其中Ni表示最小跳數(shù)，n表示發(fā)送跳數(shù)信息的錨節(jié)點(diǎn)的個(gè)數(shù)；

(6)

(3)校正誤差：假設(shè)兩錨節(jié)點(diǎn)i和j，兩錨節(jié)點(diǎn)之間的最小跳數(shù)記為hij，兩錨節(jié)點(diǎn)之間的真實(shí)距離記為drij，計(jì)算距離記為deij，校正誤差值記為errij，則有

(7)

則最終的平均跳距公式為

(8)

式中，C為計(jì)算所得的平均跳距；Ci為估算步長。

2.2 粒子群算法優(yōu)化定位結(jié)果

粒子群優(yōu)化算法[14]對(duì)復(fù)雜的鳥類遷徙過程進(jìn)行了模擬還原。鳥類遷徙飛行時(shí)所經(jīng)過的空間可以看作是所解決問題的一個(gè)解空間，而鳥群中所有的個(gè)體都可看作是該解空間中的一個(gè)粒子，在飛行過程中，鳥群間會(huì)互相傳遞位置信息并達(dá)成共識(shí)，全體都按照最佳位置前進(jìn)，引導(dǎo)它們聚集，粒子會(huì)根據(jù)自身歷史最優(yōu)位置以及種群歷史最優(yōu)位置來進(jìn)行速度和方向的不斷改變，最終實(shí)現(xiàn)對(duì)最優(yōu)值的逼近[15]。

本文將網(wǎng)絡(luò)中所有錨節(jié)點(diǎn)看作是種群中的粒子，在二維平面上定位粒子坐標(biāo)，定義xi=(xi1,xi2)T為粒子的位置向量；vi=(vi1,vi2)T為粒子的速度向量；pi=(pi1,pi2)T為粒子i自身所經(jīng)過的歷史最優(yōu)位置向量；pg=(pg1,pg2)T為種群所有粒子截止目前的歷史最優(yōu)值，則種群中每個(gè)粒子位置和速度的更新公式為

vi2(t+1)=vi2(t)+c1r1(pi2(t)-xi2(t))+c2r2(pg2(t)-xi2(t))

(9)

vi2(t+1)=xi2(t)+vi2(t+1)

(10)

式中，c1和c2為學(xué)習(xí)因子，作用是引導(dǎo)群體內(nèi)所有粒子不斷朝著自身歷史最優(yōu)值和群體歷史最優(yōu)值靠近。r1和r2為值域在[0，1]的相互獨(dú)立的隨機(jī)函數(shù)，t代表的是粒子群的迭代次數(shù)，選擇粒子群的最佳滿意解作為最最大迭代次數(shù)。

為使計(jì)算得到的節(jié)點(diǎn)坐標(biāo)更加精確，粒子的適應(yīng)度值最小，引入了粒子的目標(biāo)函數(shù)。由未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離可得到以下非線性方程組

(11)

(12)

式中，di代表的是未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的估計(jì)距離，目標(biāo)函數(shù)F的零極小值點(diǎn)即為所求未知節(jié)點(diǎn)的坐標(biāo)。

3 算法仿真與結(jié)果分析

為了驗(yàn)證本文提出的改進(jìn)算法的可行性，對(duì)傳統(tǒng)的DV-Hop算法、文獻(xiàn)[6]的改進(jìn)算法和本文提出的改進(jìn)算法的仿真結(jié)果進(jìn)行對(duì)比分析。

3.1 仿真環(huán)境以及參數(shù)設(shè)置

仿真實(shí)驗(yàn)在Matlab R2014a的環(huán)境下進(jìn)行，仿真分析的網(wǎng)絡(luò)模型標(biāo)準(zhǔn)參數(shù)設(shè)置如下：在100 m×100 m的正方形區(qū)域隨機(jī)生成100個(gè)節(jié)點(diǎn)，在節(jié)點(diǎn)總數(shù)保持不變的情況下，為消除隨機(jī)性產(chǎn)生的誤差，所得仿真結(jié)果均為同樣的條件下實(shí)驗(yàn)仿真100次所得結(jié)果的平均值。

3.2 仿真結(jié)果及分析

在計(jì)算平均定位誤差時(shí)，采用以下公式

(13)

圖1 網(wǎng)絡(luò)節(jié)點(diǎn)分布圖

對(duì)于不同的跳數(shù)閥值，仿真結(jié)果如圖2所示，由圖可知，最小跳數(shù)閥值TN取5時(shí)，能使平均定位誤差達(dá)到最小。

圖2 最小跳數(shù)閥值對(duì)定位精度的影響

圖3是在仿真網(wǎng)絡(luò)中總節(jié)點(diǎn)數(shù)保持不變的情況下，錨節(jié)點(diǎn)比例分別為5%、10%、15%、20%、25%、30%、35%、40%的情況下，傳統(tǒng)DV-Hop算法、傳統(tǒng)DV-Hop算法以及本文改進(jìn)算法的仿真結(jié)果對(duì)比。從圖3可以看出，3種算法的平均定位誤差大致上都是隨著錨節(jié)點(diǎn)比例的增大而減小，在錨節(jié)點(diǎn)比例大到一定時(shí)，定位平均誤差趨于平穩(wěn)。本文改進(jìn)算法的定位誤差相比傳統(tǒng)DV-Hop算法誤差減小了約20%，比文獻(xiàn)[6]算法的平均誤差減小約15% 。

圖3 定位精度與錨節(jié)點(diǎn)比例的關(guān)系

圖4是在保持錨節(jié)點(diǎn)比例一定時(shí)，不同的節(jié)點(diǎn)通信半徑對(duì)于最終定位誤差的影響。當(dāng)錨節(jié)點(diǎn)比例保持不變時(shí)，節(jié)點(diǎn)通信半徑分別為10 m，15 m，20 m，25 m，30 m，35 m，40 m，45 m，50 m。3種算法隨著節(jié)點(diǎn)通信半徑的增大，平均定位誤差呈拋物線形狀，當(dāng)節(jié)點(diǎn)通信半徑達(dá)到約35 m時(shí)平均定位誤差最小。

圖4 定位精度與節(jié)點(diǎn)通信半徑的關(guān)系

4 結(jié)束語

本文針對(duì)傳統(tǒng)算法和已有改進(jìn)算法的不足之處，提出了一種改進(jìn)的DV-Hop定位算法，仿真結(jié)果表明，改進(jìn)算法有效減小了定位誤差，提高了定位精度。采用粒子群算法對(duì)定位結(jié)果進(jìn)行優(yōu)化，為了得到不錯(cuò)的定位精度，算法迭代次數(shù)要達(dá)到35次以上。下一步將致力于研究如何在減小算法的迭代次數(shù)、加快收斂速度的同時(shí)，保持一個(gè)較好的定位精度。

參考文獻(xiàn)

[1] 史龍,王福豹,段渭軍,等.無線傳感器網(wǎng)絡(luò)Range-Free自身定位機(jī)制與算法[J].計(jì)算機(jī)工程與應(yīng)用,2004,40(23):127-130.

[2] 紀(jì)杰,施偉斌.改進(jìn)的無線傳感器網(wǎng)絡(luò)DV-Hop節(jié)點(diǎn)定位算法[J].電子科技,2016,29(10):86-88.

[3] 衛(wèi)開夏,田金鵬,王克謙.無線傳感器網(wǎng)絡(luò)DV-Hop定位改進(jìn)算法[J].傳感技術(shù)學(xué)報(bào),2010, 23(12):1820-1824.

[4] 彭宇,王丹.無線傳感器網(wǎng)絡(luò)定位技術(shù)綜述[J].電子測量與儀器學(xué)報(bào),2011,25(5):389-399.

[5] 李輝,熊盛武,劉毅,等.無線傳感器網(wǎng)絡(luò)DV-HOP定位算法的改進(jìn)[J].傳感技術(shù)學(xué)報(bào),2011, 24(12):1782-1786.

[6] 李琳,趙可,林志貴,等.基于加權(quán)的三維DV-Hop定位算法[J].控制工程,2015,22(4):761-764.

[7] Rahman A U,Alharby A,Hasbullah H,et al.Corona based deployment strategies in wireless sensor network[J].Journal of Network & Computer Applications,2016,64(C):176-193.

[8] Chen K,Wang Z,Lin M,et al.An improved DV-Hop localization algorithm for wireless sensor networks[J].Chinese Journal of Sensors & Actuators,2011,9(6):2232-2236.

[9] Hill K M,Gioia G,Tota V V.Structure and kinematics in dense free-surface granular flow[J]. Physical Review Letters,2003,91(6):064302-064308.

[10] 石為人,賈傳江,梁煥煥.一種改進(jìn)的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法[J].傳感技術(shù)學(xué)報(bào),2011,24(1):83-87.

[11] 劉士興,黃俊杰,劉宏銀,等.基于多通信半徑的加權(quán)DV-Hop定位算法[J].傳感技術(shù)學(xué)報(bào),2015(6):883-887.

[12] 溫江濤,范學(xué)敏,吳希軍.基于RSSI跳數(shù)修正的DV-Hop改進(jìn)算法[J].傳感技術(shù)學(xué)報(bào), 2014(1):113-117.

[13] 李明,石為人.異構(gòu)傳感器網(wǎng)絡(luò)成本最優(yōu)節(jié)點(diǎn)部署機(jī)制[J].重慶大學(xué)學(xué)報(bào),2012, 35(2):55-59.

[14] 楊維,李歧強(qiáng).粒子群優(yōu)化算法綜述[J].中國工程科學(xué),2004,6(5):87-94.

[15] 李月.基于DV-Hop的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法研究[D].長春:吉林大學(xué),2016.