基于節(jié)點RSSI值與臨界RSSI比例的跳數(shù)修正和跳距重估的DV-HOP算法

方旺盛，雷高祥

（江西理工大學信息工程學院，江西贛州341000）

基于節(jié)點RSSI值與臨界RSSI比例的跳數(shù)修正和跳距重估的DV-HOP算法

方旺盛*，雷高祥

（江西理工大學信息工程學院，江西贛州341000）

為了減少傳統(tǒng)DV-Hop定位算法對未知節(jié)點定位時產(chǎn)生的較大誤差，提出了一種基于節(jié)點RSSI值與臨界RSSI比例跳數(shù)修正和跳距重估的DV-HOP算法。首先，采取節(jié)點RSSI值與臨界RSSI比例來修正跳數(shù)，得到修正后的跳數(shù)；然后利用修正后的跳數(shù)求解跳距均衡系數(shù)對平均跳距進行窮盡三角組合加權修正，得到修正后的跳距；最后，將修正后跳距與通信半徑進行比較，偏差最大和最小的跳距不參與計算，再求剩余跳距值的均值得到平均每跳距離。仿真結果表明：在相同的網(wǎng)絡環(huán)境下，與經(jīng)典的DV-Hop算法相比，文中算法僅需要節(jié)點通信芯片具有RSSI指示功能，并不需要其它額外的硬件，有效降低了定位誤差；與其他DV-Hop修正算法相比，該算法同樣也具有降低定位誤差的優(yōu)勢。

無線傳感器網(wǎng)絡；DV-Hop定位算法；臨界RSSI；跳數(shù)；均衡系數(shù)；跳距重估

現(xiàn)今，多種無線傳感器網(wǎng)絡定位算法被廣泛應用。無線傳感器網(wǎng)絡按定位算法分為基于測距的定位算法和基于非測距的定位算法，幾種常見的測量技術包括到達時間、到達時間差、到達角、接收信號強度指示等?；诜菧y距的定位算法包括DV-Hop算法，質心算法，Amorphous算法，APIT，MDS-MAP等等。在現(xiàn)有技術中，通常使用的是DV-Hop算法。針對DV-Hop算法的不足，有必要對DV-Hop算法提出改進算法。劉鋒，張翰，楊驥等提出一種加權處理的無線傳感器網(wǎng)絡平均跳距離估計算法［1］來提高定位精度，Wanli Zhang，Xiaoying Yang等提出了一種用RSSI值加權跳數(shù)［2］，用全網(wǎng)的平均跳距代替每一個信標節(jié)點的平均跳距來提高定位精度，Deng yi，Zhang，and Liu Feng等通過對經(jīng)典DV-Hop算法的改進［3］，采用加權平均來計算平均跳距來提高定位精度，嵇瑋瑋等人［4］提出了利用了最小均方法求平均每跳距離和采用不同參考節(jié)點平均跳距來計算未知節(jié)點到錨節(jié)點之間距離的方案。上述算法中，大部分是對傳統(tǒng)DV-Hop算法的跳數(shù)和跳距計算方法的改進，但定位誤差的減少不太明顯。目前對這類算法最主要的改進是對節(jié)點在全局位置進行估計時的估計算法來進行改進。本文在DV-Hop算法的跳數(shù)計算和平均跳距地選取過程中引入了臨界RSSI比，均衡系數(shù)和跳距重估，使得跳數(shù)和平均跳數(shù)更加接近真實值。

1 DV-Hop算法及最大似然估計法

1.1 DV-Hop定位算法

經(jīng)典DV-Hop算法［5-6］的定位過程可分為3個階段：

①采用典型的距離矢量路由交換協(xié)議，通過節(jié)點之間的信息交換，使網(wǎng)絡中所有的節(jié)點獲得與信標節(jié)點間的最小跳數(shù)。

②計算與信標節(jié)點的估計距離

信標節(jié)點根據(jù)在第一階段中記錄的其他導標節(jié)點的位置信息和相應的跳數(shù)，按照式（1）估計每跳的平均距離，并將其作為一個跳距校正值廣播至網(wǎng)絡中：

式中(xi,yi),(xj,yj)是信標節(jié)點i，j的坐標，hi是信標節(jié)點i，j的最小跳數(shù)。

未知節(jié)點接收離自己最近的一個信標節(jié)點的值作為自身的平均每跳距離值即：

式中AVG是未知節(jié)點平均每跳距離值，avgi是離未知節(jié)點最近的信標節(jié)點估計的平均每跳距離值。然后，算出到各信標節(jié)點的距離，公式如下：

③最后根據(jù)最大似然估計方法計算其坐標［6-7］。

然而，在實際的網(wǎng)絡拓撲結構中，信標節(jié)點和未知節(jié)點之間的路徑往往是折線［8］如圖1所示，使用DV-Hop算法會帶來很大的距離誤差，進而引起定位誤差。

圖1 節(jié)點之間的折線圖

1.2 最大似然估計法

(x1,y1),(x2,y2)…(xn,yn)為信標節(jié)點坐標，它們到未知節(jié)點（x，y）的距離分別為d1,d2,…dn，則未知節(jié)點坐標的計算公式為：

將上式看作線性方程組BX=b，解得：

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

2 RSSI測距模型

本文提出基于臨界RSSI比例加權系數(shù)處理跳數(shù)［8］，利用RSSI的測距屏蔽耗散模型［9-10］，屏蔽模型的路徑損耗模型原理使用了一個接近中心的距離d0為參考，對距離為d的平均接收功率PL（d）進行預測，兩者比值關系如下式：

考慮信號功率的損耗，經(jīng)研究測量，無線信號路徑損耗功率是對數(shù)正態(tài)隨機變量［11］，為使測量值更接近真實值，在此引入一均值為零的高斯分布e。

3 本文算法步驟及分析

考慮到無線信號功率多為mW級別，極化后接收信號強度轉化為負數(shù)的dBm，并且通信半徑為R的節(jié)點1跳理想距離為R，本文算法將R處相應的RSSI值做為臨界值RSSthreshold。其計算方法利用式（10）得到：

本文算法的具體步驟：

①每個信標節(jié)點廣播一個數(shù)據(jù)包，基本信息有信標節(jié)點的標號ID；相應ID號信標節(jié)點的坐標（x，y）；初始值為0的跳數(shù)Hcot；第i跳接收數(shù)據(jù)包時接收信號強度值RSSIi，距離為R時的RSSI臨界值RSSthrehold，然后信標節(jié)點以一定功率將數(shù)據(jù)包向周圍節(jié)點廣播出去。其它節(jié)點收到鄰居節(jié)點發(fā)送的數(shù)據(jù)包后用接收到的數(shù)據(jù)包中RSSI值利用式（10）、式（11）求出臨界比例系數(shù)hi，再根據(jù)數(shù)據(jù)包中的按照式（12）更新跳數(shù)，同時將更新后的信息轉發(fā)給其鄰居節(jié)點

②對已求出的每個信標節(jié)點的平均跳距，利用三角重組加權處理［12-13］每個信標節(jié)點的平均跳距。信標節(jié)點i估計的平均跳距記為Li，未知節(jié)點距離錨節(jié)點的跳數(shù)記為mi。假設未知節(jié)點共收到m個信標節(jié)點的信息，并記為q1,q2,q3,q4,…,qm，從這m個信標節(jié)點中取出3個作為一組，判斷以它們?yōu)轫旤c的相應信標節(jié)點的跳距的大小，并給跳距較大的給以較小的系數(shù)修正，跳距較小的給以較大的系數(shù)修正［14］。假如選擇了q1,q2,q3三個信標節(jié)點，相應的跳距為 L1,L2,L3，未知節(jié)點距離他們相應的跳數(shù)為m1,m2,m3。均衡系數(shù)計算如式（13）

利用均衡系數(shù)處理后的平均跳距Avg1為：

按同樣的方法選擇三個信標節(jié)點，直至窮盡所有信標節(jié)點的三角組合，總共有種，并且可以得到相應的平均跳距為將得到的平均跳距與通信半經(jīng)R作差比較，偏差最大和最小的跳距不參與計算，即選除以下兩種情況MAX[Avg1,Avg2,…Avg3],MIN[Avg1,Avg2,…Avg3], 最終得到平均跳距為：

利用式（15）計算出來的平均跳距和式（12）更新后的跳數(shù)信息按照下式計算未知節(jié)點到信標節(jié)點的距離D：

③未知節(jié)點坐標的求解，采用經(jīng)典DV-Hop最大似然估計法定位。

臨界RSSI比例原理如圖2所示。

圖2 臨界比例原理圖

計算臨界比例方法如下公式：

當hi=1時，說明節(jié)點在通信半徑邊緣處，即在類似圖2中的A點處，此時的跳數(shù)為1。

當hi＜1時，說明節(jié)點在距離小于通信半徑R處，即在類似圖2中的B點處，跳數(shù)小于1。

圖1中根據(jù)傳統(tǒng)DV-Hop算法計算跳數(shù)為3跳，若依據(jù)本文算法計算跳數(shù)為：

得到的跳數(shù)值始終比經(jīng)典DV-Hop算法要小，減小了跳數(shù)計算誤差，這樣就使得計算的跳距更加接近實際跳距值。

4 算法仿真

本文利用MATLAB仿真軟件對實驗進行仿真分析。仿真環(huán)境在100 m×100 m區(qū)域內隨機產(chǎn)生未知節(jié)點，節(jié)點總數(shù)為100個，在不同的通信半徑與信標節(jié)點比例的條件下進行了定位性能分析，分別進行了50次仿真實驗，并取平均值作為實驗結果。相對定位誤差和定位精度?

式中，（xi，yi）為節(jié)點真實坐標，（xj，yj）為估計坐標位置，R為節(jié)點通信半徑。

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

表1 定位誤差（100%）隨錨節(jié)點變化關系（R=60 m）

表2 定位誤差（100%）隨通信半徑的變化關系

圖3表示網(wǎng)絡節(jié)點總數(shù)固定，信標節(jié)點比例分別取5%，7%，9%，11%，13%，15%，20%，通信半徑R=60 m和R=70 m情況下，經(jīng)典DV-Hop，文獻［1］改進算法和本文算法的定位仿真比較。由圖3可知：本文提出的改進算法定位誤差始終小于原DV-Hop和文獻［1］算法，并且隨著信標節(jié)點比例的增加，定位誤差呈現(xiàn)下降的趨勢，當錨節(jié)點達到了一定數(shù)量時趨于平緩。并不是錨節(jié)點數(shù)越多，誤差就越小。當R=60 m時，與原DV-Hop相比，本文算法的定位誤差減少了20.7%左右，與文獻［1］相比，定位誤差減少了8%左右。

圖3 通信半徑R=60 m和R=70 m相對定位誤差

當R=70 m時，本文算法的定位誤差比原DVHop算法和文獻［1］改進算法分別減少了19%和13%左右。

圖4表示當錨節(jié)點比例相同，節(jié)點通信半徑不同時的定位誤差比較。由圖可知：當錨節(jié)點比例相同時，三種算法隨著通信半徑的增加，定位誤差也隨之下降，當半徑為60 m左右與原算法和文獻［1］偏差較大，誤差減少效果明顯，通信半徑達到一定范圍時誤差波動不大，說明并不是通信半徑越大越好。

圖4 不同通信半徑的定位誤差比較圖

5 結論

本文對DV-Hop定位算法的跳數(shù)和平均跳距分別采取節(jié)點RSSI值與臨界RSSI的比例修正和跳距重估修正，經(jīng)過節(jié)點RSSI值與臨界RSSI比例修正后的跳數(shù)計算誤差有一定減少，并且本文算法對跳距的重估，使得跳距更接近于真實值。最后用MATLAB進行仿真實驗。仿真結果表明在通信開銷不變情況下本文所提出的改進算法與原算法相比定位誤差有相對的減少，并且與文獻［1］算法相比定位誤差也有所減少。

［1］劉鋒，張翰，楊驥，等.一種基于加權處理的無線傳感器網(wǎng)絡平均跳距離估計算法［J］.電子與信息學報，2008，30（5）：1222-1225.

［2］Zhang W，Yang X，Song Q.DV-Hop Localization Algorithm Based on RSSI Correction［J］.Journal of Software Engineering，2015，9（1）：188-194.

［3］Deng yi，Zhang，Liu Feng.Improvement of DV-Hop Localization Algorithms in Wireless Sensor Networks［J］.Instrumentation& Measurement，Sensor Network and Automation（IMSNA），2012（2）：567-569.

［4］嵇瑋瑋，劉中.DV-Hop定位算法在隨機傳感器網(wǎng)絡中的應用研究［J］.電子與信息學報，2008，30（4）：970-974.

［5］Niculeseu D，Nath B.DV-Based Positioning in Ad Hoc Networks［J］.Journal of Telecommunication Systems，2003，22（1/4）：267-280.

［6］石為人，賈傳江，梁煥煥.一種改進的無線傳感器網(wǎng)絡DV-Hop定位算法［J］.傳感技術學報，2011，24（1）：83-87.

［7］Xie Chuan.Research on Improved DV-HOP Localization Algorithm Based on Weighted Least Square Method［J］.Knowledge Acquisition and Modeling Workshop，2008，IEEE International Symposium，2008，12（21-22）：773-776

［8］夏少波，朱曉麗，鄒建梅，等.基于跳數(shù)修正的DV-Hop改進算法［J］.傳感技術學報，2015，28（5）：757-762.

［9］Cao J，Chen M.The Research of DV-HOP Positioning Algorithm Based on RSSI Calibration［J］.TELKOMNIKA Indonesian Journal of Electrical Engineering，2014，12（10）：7452-7458.

［10］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

［11］Zhang D Y，Cui G D.A Union Node LocalizationAlgorithm Based on RSSI and DV-Hop for WSNs［C］//Instrumentation，Measurement，Computer，Communication and Control（IMCCC），2012 Second International Conference on 2012 IEEE，2012，12：1094-1098.

［12］Lin Z G，Zhao L，Li L，et al.An Improved DV-HOP on Weighted and Distributed Calculation Method［J］.Advanced Materials Research，2013，787：1044-1049.

［13］Jang-Ping Sheu，Pei-Chun Chen，Chih-Shun Hsu.A Distributed Localization Scheme for Wireless Sensor Networks with Improved Grid-Scan and Vector-Based Refinement［J］.IEEE Transactions on Mobile Computing，2008，7（9）：1110-1123

［14］Cheng H Q，Wang H，Wang H K.An Improved Centroid Localization Algorithm Based on Weighted Average in WSN［C］//Proceedings of the 3rd International Conference on Electronics Computer Technology（ICECT’11），2011，4：258-262.

方旺盛（1963-），男，教授，碩士研究生導師，主要研究方向為無線傳感器網(wǎng)絡，數(shù)字水印，基因表達式編程等，fangwangsheng@163.com；

雷高祥（1992-），男，碩士研究生，研究方向為無線傳感器網(wǎng)絡，1210122486@qq.com。

A DV-HOP Algorithm Based on the Ratio between Node RSSI and the Critical RSSI Hop Correction and Hop Distance Revaluation

FANG Wangsheng*，LEI Gaoxiang
（Faculty of Information Engineering，Jiangxi University of Science and technology，Ganzhou Jiangxi 341000，China）

Traditional DV-Hop algorithm can cause greater positioning errors，To overcome such problem，this paper presents a improved algorithm which based on the ratio between node RSSI and the critical RSSI hop count correction and hop distance revaluation.Firstly，we take the ratio of node RSSI and the critical RSSI to modify hops，and the correction hops will be attained；then the average hop distance will be corrected through weighted combination of triangle.Finally，compared the hop distance with communication radius，the maximum and minimum hop distance will not be applied to calculate，According to the above，we will get the average distance per hop by calculating the average value among the remaining jump distance.The simulation results show that under the same network environment，compared with the classic DV-Hop algorithm，this proposed algorithm requires only node communication chips with RSSI indicator and does not require additional hardware overhead，can effectively reduce the location error；compared with other DV-Hop correction algorithm，this algorithm also has the advantage of reducing the location error.

wireless sensor networks；DV-Hop localization algorithm；critical RSSI；equilibrium coefficient；hop distance revaluation

TP393

A

1004-1699（2015）08-1244-05

??6150P

10.3969/j.issn.1004-1699.2015.08.024

2015-04-21 修改日期：2015-05-27