雷高祥， 黃輝，　方旺盛

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

基于RSSI值跳數(shù)修正和跳距加權(quán)處理的DV-HOP算法

雷高祥， 黃輝，方旺盛

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

針對(duì)傳統(tǒng)DV-Hop定位算法在計(jì)算節(jié)點(diǎn)間的跳數(shù)和平均跳距存在的誤差，提出了一種基于RSSI值跳數(shù)修正和跳距加權(quán)修正的DV-HOP算法.首先，采取節(jié)點(diǎn)RSSI比值修正跳數(shù)；然后選擇距離未知節(jié)點(diǎn)最近的3個(gè)錨節(jié)點(diǎn)，并利用修正后的跳數(shù)求加權(quán)系數(shù)對(duì)平均跳距進(jìn)行加權(quán)修正.仿真結(jié)果表明：在相同的網(wǎng)絡(luò)環(huán)境下，該算法沒有增加其他硬件開銷，并且定位誤差相對(duì)于傳統(tǒng)DV-Hop算法有一定減少.

無線傳感器網(wǎng)絡(luò)；DV-Hop定位算法；RSSI值；跳數(shù)；加權(quán)系數(shù)

0　引言

隨著相關(guān)技術(shù)的發(fā)展，無線傳感器網(wǎng)絡(luò)定位技術(shù)已被廣泛運(yùn)用，目前已有的無線傳感器網(wǎng)絡(luò)定位算法可分為源定位算法、節(jié)點(diǎn)自定位算法和地圖匹配算法.其中源定位算法包括基于測(cè)距和基于非測(cè)距的定位算法.常見的基于測(cè)距定位算法包括到達(dá)時(shí)間、到達(dá)時(shí)間差、到達(dá)角、接收信號(hào)強(qiáng)度指示等，基于非測(cè)距的定位算法包括DV-Hop算法、質(zhì)心算法、Amorphous算法、APIT、MDS-MAP等.經(jīng)典DV-Hop算法通過跳段距離而不是直線距離來估計(jì)未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離，然而在實(shí)際情況下，未知節(jié)點(diǎn)與錨節(jié)點(diǎn)相互之間的連接是折線，直接利用跳段距離必然會(huì)造成大量的誤差積累.楊祥等［1］提出了一種基于RSSI比值修正的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法，通過將RSSI作為節(jié)點(diǎn)間歐氏距離的比值來修正每一跳的距離.張愛清等［2］提出了一種基于RSSI每跳分級(jí)和跳距修正的DV-Hop算法，該算法將每一條細(xì)化分級(jí)，利用最小均方誤差準(zhǔn)則處理平均跳距，有效降低了定位誤差，提高了定位精度，Deng等通過對(duì)經(jīng)典DVHop算法的改進(jìn)［3］，采用加權(quán)平均來計(jì)算平均跳距來提高定位精度.本文在DV-Hop算法的跳數(shù)過程中引入了RSSI比值，并且利用加權(quán)系數(shù)對(duì)跳距加權(quán)，使得跳數(shù)和平均跳數(shù)更加接近真實(shí)值.

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

1.1DV-Hop定位算法

由Niculescu和Nath提出的DV-Hop算法［4］可分為3個(gè)步驟：

1）待定位節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的最小跳數(shù)的獲取.每一個(gè)信標(biāo)節(jié)點(diǎn)廣播包含自身位置信息和跳數(shù)字段的分組，跳數(shù)初始值為0.其他節(jié)點(diǎn)記錄其接收到的每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，忽略來自同一信標(biāo)節(jié)點(diǎn)較大跳數(shù)的分組，并將跳數(shù)字段加1轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn).這樣網(wǎng)絡(luò)中所有節(jié)點(diǎn)都能獲得與信標(biāo)節(jié)點(diǎn)之間的最小跳數(shù).

2）估算待定位節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)間的距離.根據(jù)在第一階段中得到的其他信標(biāo)節(jié)點(diǎn)的位置信息和最小跳數(shù)，按照下式（1）估計(jì)每跳的平均距離：

式（1）中（xi-xj），（yi-yj）表示相應(yīng)信標(biāo)節(jié)點(diǎn)i，j的坐標(biāo)值，hi表示信標(biāo)節(jié)點(diǎn)i，j的跳數(shù)值.

待定位節(jié)點(diǎn)得到最近信標(biāo)的跳距值：

式（2）中AVG是待定位節(jié)點(diǎn)的平均跳距，avgi是距離待定位節(jié)點(diǎn)最近的信標(biāo)節(jié)點(diǎn)平均跳距.待定位節(jié)點(diǎn)接收到每跳距離并根據(jù)其到信標(biāo)節(jié)點(diǎn)的最小跳數(shù)來估算其到各信標(biāo)節(jié)點(diǎn)的距離如公式（3）：

3）利用基于測(cè)距的定位算法［5-6］計(jì)算待定位節(jié)點(diǎn)位置.如根據(jù)最大似然估計(jì)方法計(jì)算其坐標(biāo)［7］.

在實(shí)際情況下，網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)如圖1所示，未知節(jié)點(diǎn)B到信標(biāo)節(jié)點(diǎn)A的跳數(shù)并不是理想的跳數(shù)，A到B的實(shí)際路徑為A→C→B，這樣如果利用跳段距離就會(huì)引起大量的誤差積累，定位誤差也會(huì)隨之增大.

圖1　網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

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è)距模型

常見的無線信號(hào)傳播路徑損耗模型［8］有：對(duì)數(shù)距離路徑損耗模型、Hata模型、對(duì)數(shù)-常態(tài)分布模型、自由空間傳播模型，本文采用最常用的是對(duì)數(shù)-常態(tài)分布模型［9］.提出基于臨界RSSI比例加權(quán)系數(shù)處理跳數(shù)，選取距離為d0參考距離，當(dāng)距離為d時(shí)，可以預(yù)測(cè)此時(shí)節(jié)點(diǎn)的平均接收功率PL（d），兩者關(guān)系如下式：

兩邊取對(duì)數(shù)得：

為使測(cè)量值更接近真實(shí)值，引入一均值為零的高斯分布ε［10］.

其中，［PL（d）］dB距離 d處的接收信號(hào)強(qiáng)度，計(jì)量單位為dBm；n表示路徑損耗因子，一般取2～4，文中取n=4.PL（d0）為發(fā)射端參考距離1 m的處RSSI，即為發(fā)射功率.RSSI值隨距離變化關(guān)系如圖2所示.

圖2　RSSI值隨距離變化關(guān)系

3　算法分析及步驟

3.1算法分析

3.1.1RSSI比值

考慮到無線信號(hào)功率多為mw級(jí)別，極化后接受信號(hào)強(qiáng)度［11］轉(zhuǎn)化為負(fù)數(shù)的dbm.本文算法將R處相應(yīng)的RSSI值做為比例因子RSSIR.利用式（12）得到：

RSSI比值原理如圖3所示：

圖3　臨界比例原理圖

計(jì)算RSSI比值如式（13）：

當(dāng)hi=1時(shí)，說明節(jié)點(diǎn)半徑R處，即在類似圖3中的A點(diǎn)處，即跳數(shù)為1.

當(dāng)hi＜1時(shí)，說明節(jié)點(diǎn)在通信范圍內(nèi)部，即在類似圖3中的B點(diǎn)處，即跳數(shù)小于1.

圖1中根據(jù)傳統(tǒng)DV-Hop算法計(jì)算跳數(shù)為2跳，通過本文算法加權(quán)后的跳數(shù)為：

得到的跳數(shù)值更加接近節(jié)點(diǎn)實(shí)際情況下的跳數(shù).

3.1.2跳距加權(quán)

對(duì)跳距的加權(quán)處理主要包括以下步驟：首先，選取距離待定位節(jié)點(diǎn)最近的3個(gè)信標(biāo)節(jié)點(diǎn)，然后，計(jì)算加權(quán)系數(shù)，最后用加權(quán)系數(shù)處理每個(gè)信標(biāo)節(jié)點(diǎn)相應(yīng)的平均跳距.

假設(shè)未知節(jié)點(diǎn)共收到m個(gè)信標(biāo)節(jié)點(diǎn)的信息，從這m個(gè)信標(biāo)節(jié)點(diǎn)中取出距離未知節(jié)點(diǎn)最近的3個(gè)信標(biāo)節(jié)點(diǎn)，判斷這3個(gè)相應(yīng)信標(biāo)節(jié)點(diǎn)的跳距的大小，并將系數(shù)較小的賦給跳距較大進(jìn)行修正，將系數(shù)較大的賦給跳距較小的進(jìn)行修正.假如3個(gè)最近的信標(biāo)節(jié)點(diǎn)ID為q1，q2，q3，相應(yīng)的跳距為L(zhǎng)1，L2，L3跳數(shù)為m1，m2，m3.加權(quán)系數(shù)［12-13］計(jì)算如式（14）：

對(duì)平均跳距賦以加權(quán)系數(shù)，得到最終跳距值A(chǔ) vgi為:

其中，Li（i=1，2，3）為離待定位節(jié)點(diǎn)最近的信標(biāo)節(jié)點(diǎn)的平均跳距，mi（i=1，2，3）待定位節(jié)點(diǎn)到相應(yīng)最近信標(biāo)節(jié)點(diǎn)的跳數(shù).

3.2算法步驟

1）所有的信標(biāo)節(jié)點(diǎn)發(fā)送一個(gè)包含自身信息的數(shù)據(jù)包，包括節(jié)點(diǎn)ID，坐標(biāo)信息，跳數(shù)；第i跳接收數(shù)據(jù)包時(shí)接收信號(hào)強(qiáng)度值RSSIi，距離為R時(shí)的接收信號(hào)強(qiáng)度值RSSIR.利用公式（16）更新跳數(shù)，其中hati表示最新跳數(shù)：

然后通過典型的距離矢量交換協(xié)議，使網(wǎng)絡(luò)中所有節(jié)點(diǎn)得到距離每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)值，同時(shí)將更新后的信息轉(zhuǎn)發(fā)給其鄰居節(jié)點(diǎn)［12］.

2）信標(biāo)節(jié)點(diǎn)根據(jù)第一步得到的位置信息和最小跳數(shù)后，利用傳統(tǒng)DV-Hop求解平均跳距的方法求解平均每跳距離.

3）根據(jù)最大似然估計(jì)方法計(jì)算其坐標(biāo).

4　算法仿真

本文利用MATLAB仿真軟件對(duì)實(shí)驗(yàn)進(jìn)行仿真分析.仿真環(huán)境設(shè)置為：在100 m×100 m正方形區(qū)域內(nèi)隨機(jī)部署100個(gè)未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn)，信標(biāo)節(jié)點(diǎn)在隨機(jī)部署的節(jié)點(diǎn)中選取相應(yīng)的參考坐標(biāo)進(jìn)行仿真實(shí)驗(yàn)，每個(gè)節(jié)點(diǎn)具有相同的通信半徑為R.并且在不同的通信半徑與信標(biāo)節(jié)點(diǎn)比例的情況下對(duì)文中算法性能進(jìn)行仿真分析，分別進(jìn)行了50次仿真實(shí)驗(yàn)，并取平均值最為實(shí)驗(yàn)結(jié)果.節(jié)點(diǎn)間的測(cè)距暫不考慮測(cè)量誤差對(duì)定位的影響 （假設(shè)噪聲值為零，測(cè)量值即為真實(shí)距離）.在室外空曠環(huán)境下，電磁傳播各向一致，采用的shadowing模型，損耗指數(shù)n=4，參考距離d0=1m選取RSSI值.相對(duì)定位誤差￡和定位精度?:

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

下面通過部分?jǐn)?shù)據(jù)，定量分析文中算法的定位誤差，表1列出了在通信半徑為R=60m，錨節(jié)點(diǎn)數(shù)取5%，10%，15%，20%，25%時(shí)，兩種定位算法的定位誤差變化數(shù)據(jù).表2列出了在錨節(jié)點(diǎn)比例為5%，通信半徑R取50 m，55 m，60m，65 m時(shí)，二種算法的定位誤差變化數(shù)據(jù).

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

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

如圖4所示為網(wǎng)絡(luò)的總節(jié)點(diǎn)數(shù)和通信半徑不變，信標(biāo)節(jié)點(diǎn)比例分別取5%，10%，15%，20%，25%時(shí)，兩種算法在通信半徑R=60 m和R=70m兩種情況下的誤差比較.由圖4所示可知：隨著信標(biāo)節(jié)點(diǎn)數(shù)目的增加，兩種算法的定位誤差也隨之下降，當(dāng)節(jié)點(diǎn)數(shù)達(dá)到一定比例時(shí)，定位誤差率區(qū)域平緩，并且改進(jìn)算法定位誤差相對(duì)于原DV-Hop算法有一定優(yōu)勢(shì).說明并不是錨節(jié)點(diǎn)數(shù)越多，誤差就越小.當(dāng)R=60 m時(shí)，與原DV-Hop相比，文中算法的定位誤差減少了17%左右.當(dāng)R=70 m時(shí)，相對(duì)于傳統(tǒng)算法，文中算法的定位誤差減少了15%左右.

如圖5所示為信標(biāo)節(jié)點(diǎn)比例相同，節(jié)點(diǎn)通信半徑不同時(shí)，兩種算法的定位誤差比較結(jié)果.由圖5所示可知：當(dāng)信標(biāo)節(jié)點(diǎn)比例相同時(shí)，隨著通信半徑的增加，兩種算法的定位誤差也隨之下降，當(dāng)通信半徑在60m左右時(shí)，兩種算法的定位誤差偏差較大，半徑達(dá)到一定大小時(shí)，定位誤差趨于平緩，通信半徑越大，定位誤差不一定越小.

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

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

5　結(jié)論

文中對(duì)DV-Hop定位算法的跳數(shù)采取RSSI比值修正，以減少計(jì)算跳數(shù)帶來的誤差，經(jīng)過節(jié)點(diǎn)RSSI值與臨界RSSI比例修正后的跳數(shù)計(jì)算誤差有一定減少.并且使用加權(quán)系數(shù)處理跳距，使得跳距更加接近真實(shí)值.最后用MATLAB進(jìn)行仿真實(shí)驗(yàn).仿真結(jié)果表明在通信開銷不變情況下文中所提出的改進(jìn)算法與原算法相比定位誤差有相對(duì)的減少.

［1］楊祥，潘瑋.基于RSSI比值修正的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法［J］.傳感器與微系統(tǒng)，2013（7）:126-128，135.

［2］張愛清，葉新榮，胡海峰等.基于RSSI每跳分級(jí)和跳距修正的 DV-HOP改進(jìn)算法 ［J］.儀器儀表學(xué)報(bào)，2012，11:2552-2559.

［3］Zhang D Y，Liu F.Improvement of DV-Hop localization algorithms in wireless Sensor networks［J］.Instrumentation& Measurement，Sensor Network and Automation（IMSNA），2012，2: 567-569.

［4］Niculeseu D，Nath B.DV-based positioning in Ad Hoc networks［J］. Journal of Telecommunication Systems，2003，22（1）：267-280．

［5］周小波，喬鋼柱，曾建潮．無線傳感器網(wǎng)絡(luò)中基于RSSI的加權(quán)DV-Hop定位方法［J］．計(jì)算機(jī)工程與設(shè)計(jì)，2011，47（14）：109-111．

［6］石為人，賈傳江，梁煥煥．一種改進(jìn)的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法［J］．傳感技術(shù)學(xué)報(bào)，2011，24（1）：83-87．

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

［8］Guo Z，Min L，Li H，et al.Improved DV-Hop localization algorithm based on RSSIvalue and hop correction［M］.Advances in Wireless Sensor Networks.Springer Berlin Heidelberg，2013:97-102.

［9］Zhang D Y，Cui G D.A union node localization algorithm based onRSSIandDV-HopforWSNs［C］//Instrumentation，Measurement，Computer，Communication and Control（IMCCC），2012 Second International Conference on 2012 IEEE，2012，12: 1094-1098.

［10］Cao J，Chen M.The Research of DV-HOP Positioning Algorithm Based on RSSICalibration［C］//Applied Mechanics and Materials，2014，610:882-887.

［11］Fang Z，Zhao Z，Geng D，et al.RSSI variability characterization and calibrationmethod in wireless sensor network［C］//Information and Automation（ICIA），2010 IEEE International Conference on. IEEE，2010:1532-1537.

［12］Lin ZG，Zhao L，Li L，et al.An improved DV-HOP on weighted anddistributedcalculationmethod［C］//AdvancedMaterials Research，2013，787:1044-1049.

［13］Zhang Z，Rao Z X.A weighted compensation of coordinate error localization algorithm based on RSSI［J］.Journal of Chemical and Pharmaceutical Research，2014，6（6）:448-454.

A DV-HOP algorithm based on RSSI hop count correction and hop distance weighted processing

LEI Gaoxiang，HUANG Hui，F(xiàn)ANG Wangsheng
（School of Information Engineering，JiangxiUniversity of Science and Technology，Ganzhou 341000，China）

To reduce the errors in calculating the hop count and average hop distance between nodes by the traditional DV-Hop localization algorithm，this paper presents a DV-HOP algorithm based on the ratio between node RSSI and the critical RSSI hop count correction and hop distance weighted revaluation.Firstly，the correction hops are attained by taking the ratio between node RSSI and the critical RSSI corrected hops；then three nearestanchor nodes to the unknown node are chosen，and the average hop distance is corrected by using the weighting coefficient，which is attained through the corrected hop count.The simulation results show that in the same network environment，compared with the traditional DV-Hop algorithm，the proposed algorithm requires only node communication chips with RSSI indicator，without additional hardware expenses，thus effectively reducing the location error.

wireless sensor networks；DV-Hop localization algorithm；RSSI ratio；hop count；weighting coefficient

TP398

A

2095-3046（2015）05-0080-05

10.13265/j.cnki.jxlgdxxb.2015.05.014

2015-05-11

雷高祥（1992-），男，碩士研究生，主要從事無線傳感器網(wǎng)絡(luò)等方面的研究，E-mail:leigaoxiang1992@163.com.

方旺盛（1963-），男，教授，主要從事無線傳感器網(wǎng)絡(luò)，數(shù)字水印等方面的研究，E-mail:fangwangsheng@163.com.