童宇行，黃 鵬，劉玉紅

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

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

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

1 DV-Hop定位算法

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

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

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

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

(1)

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

(2)

將上式變換可得

(3)

式(3)可化為

AX=B

(4)

其中，

則未知節(jié)點M的坐標

X=(ATA)-1ATB

(5)

2 改進的DV-Hop定位算法

2.1 跳數(shù)改進

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

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

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

(6)

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

(7)

則最終的平均跳距公式為

(8)

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

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

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

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

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為學習因子，作用是引導群體內(nèi)所有粒子不斷朝著自身歷史最優(yōu)值和群體歷史最優(yōu)值靠近。r1和r2為值域在[0，1]的相互獨立的隨機函數(shù)，t代表的是粒子群的迭代次數(shù)，選擇粒子群的最佳滿意解作為最最大迭代次數(shù)。

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

(11)

(12)

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

3 算法仿真與結果分析

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

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

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

3.2 仿真結果及分析

在計算平均定位誤差時，采用以下公式

(13)

圖1 網(wǎng)絡節(jié)點分布圖

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

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

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

圖3 定位精度與錨節(jié)點比例的關系

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

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

4 結束語

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

參考文獻

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

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

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

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

[5] 李輝,熊盛武,劉毅,等.無線傳感器網(wǎng)絡DV-HOP定位算法的改進[J].傳感技術學報,2011, 24(12):1782-1786.

[6] 李琳,趙可,林志貴,等.基于加權的三維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] 石為人,賈傳江,梁煥煥.一種改進的無線傳感器網(wǎng)絡DV-Hop定位算法[J].傳感技術學報,2011,24(1):83-87.

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

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

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

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

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