方旺盛，雷高祥

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

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

方旺盛*，雷高祥

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

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

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

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

1 DV-Hop算法及最大似然估計(jì)法

1.1 DV-Hop定位算法

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

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

②計(jì)算與信標(biāo)節(jié)點(diǎn)的估計(jì)距離

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

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

未知節(jié)點(diǎn)接收離自己最近的一個(gè)信標(biāo)節(jié)點(diǎn)的值作為自身的平均每跳距離值即：

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

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

然而，在實(shí)際的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中，信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)之間的路徑往往是折線［8］如圖1所示，使用DV-Hop算法會(huì)帶來(lái)很大的距離誤差，進(jìn)而引起定位誤差。

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

1.2 最大似然估計(jì)法

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

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

得未知節(jié)點(diǎn)坐標(biāo)為：

2 RSSI測(cè)距模型

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

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

3 本文算法步驟及分析

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

本文算法的具體步驟：

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

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

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

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

利用式（15）計(jì)算出來(lái)的平均跳距和式（12）更新后的跳數(shù)信息按照下式計(jì)算未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離D：

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

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

圖2 臨界比例原理圖

計(jì)算臨界比例方法如下公式：

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

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

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

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

4 算法仿真

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

式中，（xi，yi）為節(jié)點(diǎn)真實(shí)坐標(biāo)，（xj，yj）為估計(jì)坐標(biāo)位置，R為節(jié)點(diǎn)通信半徑。

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

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

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

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

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

當(dāng)R=70 m時(shí)，本文算法的定位誤差比原DVHop算法和文獻(xiàn)［1］改進(jìn)算法分別減少了19%和13%左右。

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

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

5 結(jié)論

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

［1］劉鋒，張翰，楊驥，等.一種基于加權(quán)處理的無(wú)線傳感器網(wǎng)絡(luò)平均跳距離估計(jì)算法［J］.電子與信息學(xué)報(bào)，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ī)傳感器網(wǎng)絡(luò)中的應(yīng)用研究［J］.電子與信息學(xué)報(bào)，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］石為人，賈傳江，梁煥煥.一種改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)DV-Hop定位算法［J］.傳感技術(shù)學(xué)報(bào)，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ìn)算法［J］.傳感技術(shù)學(xué)報(bào)，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-），男，教授，碩士研究生導(dǎo)師，主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)，數(shù)字水印，基因表達(dá)式編程等，fangwangsheng@163.com；

雷高祥（1992-），男，碩士研究生，研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)，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