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

方旺盛，雷高祥

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

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

方旺盛*，雷高祥

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

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

無線傳感器網絡；DV-Hop定位算法；臨界RSSI；跳數；均衡系數；跳距重估

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

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

1.1 DV-Hop定位算法

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

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

②計算與信標節點的估計距離

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

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

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

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

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

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

圖1 節點之間的折線圖

1.2 最大似然估計法

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

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

得未知節點坐標為：

2 RSSI測距模型

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

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

3 本文算法步驟及分析

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

本文算法的具體步驟：

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

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

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

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

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

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

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

圖2 臨界比例原理圖

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

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

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

圖1中根據傳統DV-Hop算法計算跳數為3跳，若依據本文算法計算跳數為：

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

4 算法仿真

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

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

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

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

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

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

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

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

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

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

5 結論

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

［1］劉鋒，張翰，楊驥，等.一種基于加權處理的無線傳感器網絡平均跳距離估計算法［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定位算法在隨機傳感器網絡中的應用研究［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］石為人，賈傳江，梁煥煥.一種改進的無線傳感器網絡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］夏少波，朱曉麗，鄒建梅，等.基于跳數修正的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-），男，教授，碩士研究生導師，主要研究方向為無線傳感器網絡，數字水印，基因表達式編程等，fangwangsheng@163.com；

雷高祥（1992-），男，碩士研究生，研究方向為無線傳感器網絡，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