節(jié)點RSSI比值跳數(shù)修正的DV-Hop算法

方旺盛， 雷高祥， 黃 輝

(江西理工大學 信息工程學院，江西 贛州 341000)

節(jié)點RSSI比值跳數(shù)修正的DV-Hop算法

方旺盛， 雷高祥， 黃 輝

(江西理工大學 信息工程學院，江西 贛州 341000)

針對傳統(tǒng)的DV-Hop定位算法在計算錨節(jié)點與待定位節(jié)點之間的平均跳距和跳數(shù)時所造成的大量誤差積累問題，提出一種基于接收信號強度指示(RSSI)比例修正的DV-Hop定位算法。在改進的算法中，根據(jù)不同平均跳距處的接收信號強度指示(RSSI)值，選取最大平均跳距、最小平均跳距處、通信半徑處的RSSI值，求出比例因子，再利用該比列因子求出加權(quán)系數(shù)來修正每一跳數(shù)，從而得到更加精確的跳數(shù)和平均跳距，提高定位精度。仿真實驗表明：該改進算法的定位精度優(yōu)于傳統(tǒng)算法。

無線傳感網(wǎng)絡(luò)； DV-Hop定位算法； 跳數(shù)； 接收信號強度指示(RSSI)比例因子； 加權(quán)系數(shù)

0 引 言

無線傳感器網(wǎng)絡(luò)(WSNs)按節(jié)點自定位算法[1]可分為Range-free的定位算法[2]和Range-based的定位算法兩類[3]。基于Range-free的方法有Centroid，DV-Hop，Amorphous，APIT等。其中，DV-Hop算法因定位精度相對較低的缺點，許多研究者提出了改進方法。劉凱、余君君等人[4]提出了對錨節(jié)點進行優(yōu)選和求解跳數(shù)加權(quán)系數(shù)，羅維等人[5]通過比較未知節(jié)點與錨節(jié)點之間的距離，對錨節(jié)點進行選取，并且對未知節(jié)點的坐標校正。

本文針對無線傳感器網(wǎng)絡(luò)DV-Hop算法，在計算未知節(jié)點到錨節(jié)點平均跳距和跳數(shù)時存在不足，提出一種基于接收信號強度指示(RSSI)比值跳數(shù)修正的改進算法，利用RSSI比值加權(quán)跳數(shù)值，使得跳數(shù)更加接近真實值。

1 經(jīng)典DV-Hop定位算法

經(jīng)典DV-Hop算法可分為以下幾個步驟：

1)獲取待定位節(jié)點與錨節(jié)點的最小跳數(shù)。

2)估算待定位節(jié)點和錨節(jié)點的距離。錨節(jié)點獲得其他錨節(jié)點的位置信息和最小跳數(shù)，利用式(1)估算平均每跳的距離

(1)

式中 (xi,yi),(xj,yj)為相應錨節(jié)點i,j的坐標值，hi為錨節(jié)點i,j的跳數(shù)值。

3)計算待定位節(jié)點到錨節(jié)點的距離。每個節(jié)點保證從最近的錨節(jié)點獲得平均跳距。網(wǎng)絡(luò)中未知節(jié)點k利用下式計算與信標節(jié)點i的距離為

dki=avgsizek×hki

(2)

4)采取Range-based的定位算法[6]計算待定位節(jié)點位置,如最大似然估計方法[7]。

2 最大似然估計法

(x1,y1),(x2,y2),…,(xn,yn)為錨節(jié)點坐標位置，(xi,yi)為待定位節(jié)點i的坐標位置，錨節(jié)點與待定位節(jié)點i的距離分別為d1,d2,…，dn，則待定位節(jié)點坐標為

(3)

轉(zhuǎn)換為線性方程組 ，解得

(4)

(5)

(6)

得未知節(jié)點坐標為

(7)

3 RSSI測距

根據(jù)對數(shù)—常態(tài)分布模型[8,9]可以計算出距離節(jié)點d處的平均接收功率PL(d)，則有下式

(8)

左右兩邊取對數(shù)

(9)

引入一均值為零的高斯分布ε[10]。

(10)

式中 距離d處的RSSI值為[PL(d)]dB，計量單位為dBm； n為路徑損耗系數(shù)，一般取2～4，PL(d0)為參考距離1m的處RSSI。圖1為RSSI值隨距離變化關(guān)系。

圖1 RSSI值隨距離變化關(guān)系Fig 1 Relationship between RSSI and distance

4 改進DV-Hop算法步驟與算法分析

4.1 改進算法步驟

1)錨節(jié)點廣播一個數(shù)據(jù)包，數(shù)據(jù)包中的信息有錨節(jié)點的坐標位置和初始值為0的跳數(shù)。網(wǎng)絡(luò)中的節(jié)點記錄和錨節(jié)點間的最小跳數(shù)，然后加1轉(zhuǎn)發(fā)到其鄰居節(jié)點。

2)根據(jù)所得到的最小跳數(shù)值和錨節(jié)的坐標，按照式(1)計算平均每跳距離。

3)根據(jù)步驟(2)求出的錨節(jié)點所對應的平均跳距，選取出最大的平均跳距。假設(shè)步驟(2)求出的所有信標節(jié)點對應的平均每跳距離分別為avgsize1,avgsize2,…,avgsizen。

其中,n表示信標節(jié)點的個數(shù),則根據(jù)式(11)和式(12)得到最大平均跳距和最小平均跳距，即

maxave=MAX[avgsize1,avgsize2，…，avgsizen]

(11)

minave=MIN[avgsize1,avgsize2，…，avgsizen]

(12)

再根據(jù)式(10)求出距離為maxave和minave處的RSSI值，設(shè)為RSSImaxave，RSSIminave。

4)重復步驟(1)，但是跳數(shù)字段按照式(13)來更新跳數(shù)信息，即

(13)

式中 RSSIi表示第i跳的RSSI值，RSSIratic表示最大平均跳距，最小平均跳距和通信半徑R處的平均接受信號強度值。

5)根據(jù)所更新的跳數(shù)，按照式(1)來求解平均每跳距離，此時的平均跳距為更新后的跳距。信標節(jié)點 所對應的平均跳距設(shè)為avgsizei。

6)利用式(13)更新后的跳數(shù)信息按式(1)計算出來的平均跳距，按照下式計算待定位節(jié)點到錨節(jié)點的距離L為

L=avgsizei×Hpcout

(14)

7)根據(jù)最大似然估計法計算待定位節(jié)點坐標[10]。

4.2 算法分析

假設(shè)電磁傳播方向一致，并且無線信號功率多為mW級別，極化后接收信號強度[11]轉(zhuǎn)換為負數(shù)的dBm。選取最大平均跳距maxave，最小平均跳距minave和半徑R處相應的RSSI值，分別設(shè)為RSSImaxave，RSSIminave,RSSIR。利用式(10)得到最大平均跳距處的RSSI值

(15)

同理,可求出最小平均跳距

(16)

R處的RSSI值

(17)

RSSI比值原理[12]如圖2。

圖2 RSSI比值原理圖Fig 2 Principle map of RSSI ratio

圖2中，OC的距離為最大平均跳距maxave，OE的距離為最小平均跳距minave,OA的距離為通信半徑R。求出比例因子RSSIratid為

RSSIratid=(RSSImaxave+RSSIminave+RSSIR)/3

(18)

利用比例因子構(gòu)造跳數(shù)加權(quán)系數(shù)

hwi=RSSIi/RSSIratid

(19)

式中RSSIi表示節(jié)點i的接收信號強度，RSSIratid表示節(jié)點在三個不同位置的接收信號強度的平均值。

2)若未知節(jié)點恰好在RSSIDIS處，此時的跳數(shù)為1。

5 算法仿真

本文利用Matlab仿真軟件對實驗進行仿真分析。仿真參數(shù)設(shè)置：在100 m×100 m正方形區(qū)域內(nèi)隨機部署200個節(jié)點，分別進行了50次仿真實驗，并且每個節(jié)點具有相同的通信半徑R。節(jié)點i的定位誤差定義為

(20)

式中 (xi,yi)為節(jié)點的實際坐標，(xjyj)為算法中估計出的坐標位置。所有待定位節(jié)點的平均定位誤差定義為

(21)

式中 N為未知節(jié)點的個數(shù)。定位精度定義為

a=μave/R

(22)

通過部分數(shù)據(jù)定量分析本文算法的定位誤差，表1列出了在通信半徑為R=50m，錨節(jié)點數(shù)為不同比例時，兩種定位算法的定位誤差。表2列出了在錨節(jié)點比例為10 %，

表1 定位誤差隨錨節(jié)點變化關(guān)系(R=50 m) Tab 1 Positioning error changes as anchor proportion(R=50 m)

通信半徑不同時，兩種算法的定位誤差。

表2 定位誤差隨通信半徑的變化關(guān)系Tab 2 Positioning error changes as communication radius

圖3表示在網(wǎng)絡(luò)節(jié)點總數(shù)不變，錨節(jié)點比例分別取5 %，10 %，15 %，20 %，25 %，30 %，經(jīng)典DV-Hop算法和改進算法的定位誤差。從圖中可以看出，隨著錨節(jié)點數(shù)的增加，定位誤差都相應減少了。當錨節(jié)點數(shù)達到25 %左右之后，定位誤差變化趨于平緩。當通信半徑r=50 m時，改進算法的定位誤差相對于原DV-Hop算法下降了22 %左右，定位精度較高，當R=60 m時，下降了25 %左右。

圖3 通信半徑R=50m和R=60m定位誤差率Fig 3 Positioning error rate while communication radius R=60 m and R=70 m

圖4表示通信半徑為30,35,…,65 m，錨節(jié)點數(shù)分別取10 %和15 %時，兩種算法的定位誤差。從圖中可以看出，當信標節(jié)點比例相同時，隨著節(jié)點通信半徑的增加，定位誤差都呈現(xiàn)下降的趨勢。當信標節(jié)點比例為10 %時，改進算法相對于原算法，定位誤差下降了25 %左右，當比例為15 %時，定位誤差下降了24 %左右，定位精度優(yōu)于原算法。

圖4 不同通信半徑的定位誤差比較Fig 4 Positioning error comparison of different communication radius

圖5表示在錨節(jié)點個數(shù)為15，通信半徑R=60 m時，兩種定位算法的定位誤差。由圖可知，改進算法能夠有效地提高定位精度。并且相對于經(jīng)典DV-Hop算法，定位精度提高了22 %左右，定位精度較高。

圖5 不同節(jié)點總數(shù)的誤差比較Fig 5 Error comparison of different node numbers

6 結(jié) 論

本文針對經(jīng)典DV-Hop算法較大的誤差積累問題，提出一種基于RSSI比值的改進算法，其主要原理是選取不同位置處的RSSI值，求解比例因子。利用節(jié)點的RSSI值求出跳數(shù)的加權(quán)系數(shù)，經(jīng)過加權(quán)處理后的跳數(shù)值更加接近真實值。仿真實驗表明:本文改進算法具有較好降低定位誤差的作用，定位精度優(yōu)于原DV-Hop算法。

[1] Chen H,Sezaki K,Deng P,et al.An improved DV-Hop localization algorithm for wireless sensor networks[C]∥Proceedings of the 3rd IEEE Conference on Industrial Electronics and Applications,ICIEA’08,2008:1557-1561.

[2] Caffery J．A new approach to the geometry of ToA location[C]∥Proc of IEEE Vehicular Technology Conference (VTC),2000：1943-1950．

[3] Niculescu D．Positioning in Ad Hoc sensor network[J].IEEE Network,2004，18(4)：24-29．

[4] 劉 凱，余君君，譚立雄．跳數(shù)加權(quán)DV-Hop定位算法[J]．傳感技術(shù)學報， 2012，25(11)：1539-1542．

[5] 羅 維，姜秀柱，盛蒙蒙．無線傳感器網(wǎng)絡(luò)選擇性DV-Hop定位算法[J]．傳感器與微系統(tǒng)，2012，31(3)：71-77．

[6] Gao G Q,Lei L.An improved node localization algorithm based

on DV-Hop in WSNs[C]∥Proceedings of IEEE International Conference on Advanced Computer Control,ICACC ’10,2010:321-324.

[7] Zhang D Y，Cui G D.An union node localization algorithm based on RSSI and DV-Hop for WSNs[C]∥2012 The Second International Conference on Instrumentation,Measurement,Computer,Communication and Control (IMCCC),IEEE,2012：1094-1098.

[8] 張愛清,葉新榮,胡海峰,等.基于RSSI 每跳分級和跳距修正的DV-Hop 改進算法[J].儀器儀表學報,2012,33(11):2552-2559.

[9] Zhang Zheng,Zhixun Rao.A weighted compensation of coordinate error localization algorithm based on RSSI[J].Journal of Chemical and Pharmaceutical Research,2014,6(6):448-454.

[10] Wang Y H,Zhang J,Nan W,et al.An improved DV-Hop localization algorithm for wireless sensor networks[C]∥International Conference on Intelligent Computation Technology and Automation,2011:576-579.

[11] Zhang W,Yang X,Song Q.DV-Hop localization algorithm based on RSSI correction[J].Journal of Software Engineering,2015,9(1):188-194.

[12] Wang S S,Yin J P,Cai J P,et al .Localization algorithm for wireless sensor networks based on RSSI[C]∥Computer Research and Development,2008:385-388.

雷高祥,通訊作者,E—mail：leigaoxiang1992@163.com。

DV-Hop algorithm for wireless sensor networks based on node RSSI ratio hops correction

FANG Wang-sheng, LEI Gao-xiang, HUANG Hui

(Faculty of Information Engineering, Jiangxi University of Science and Technology,Ganzhou 341000,China)

Aiming at error accumulation issue of traditional DV-Hop localization algorithm in calculating average hop distance and hops between anchor node and unknown node，present a DV-Hop localization algorithm based on RSSI ratio correction.In the improved algorithm,according to RSSI value of different average hop distance select the maximum and minimum average hop distance and communication radiusR,then obtain scale factor.Use it to obtain weighting factor and to correct each hop-count,so as to obtain more accurate hops and average hop distance.The simulation suggests that positioning precision of the proposed algorithm is prior to traditional algorithm.

WSNs; DV-Hop localization algorithm; hops; RSSI scale factor; weighting coefficient

10.13873/J.1000—9787(2016)07—0132—04

2015—10—19

TP 393

A

1000—9787(2016)07—0132—04

方旺盛(1963-)，男，江西上饒人，碩士研究生導師，主要研究方向為無線傳感器網(wǎng)絡(luò)，數(shù)字水印，基因表達式編程。