基于RSSI比值修正的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法*

楊 祥，潘 瑋

（1．武漢理工大學(xué) 信息工程學(xué)院，湖北 武漢 430070;2．桂林理工大學(xué)信息科學(xué)與工程學(xué)院，廣西桂林 541004;3．桂林理工大學(xué)博文管理學(xué)院，廣西桂林 541006;4．桂林理工大學(xué)機械與控制工程學(xué)院，廣西桂林 541004）

0 引言

無線傳感器網(wǎng)絡(luò)通過向目標區(qū)域隨機拋灑大量的微小網(wǎng)絡(luò)節(jié)點，借助于節(jié)點內(nèi)置的形式多樣的傳感器感知所在周邊環(huán)境中各種各樣的物理信號。它的應(yīng)用范圍極廣［1，2］，只要涉及到有監(jiān)控存在的地方，無線傳感器網(wǎng)絡(luò)技術(shù)都可展現(xiàn)它的優(yōu)勢，是繼因特網(wǎng)之后，又一次對人類生產(chǎn)生活方式產(chǎn)生重大影響的技術(shù)之一。

一般情況下，沒有位置信息的監(jiān)測數(shù)據(jù)往往是沒有任何意義的。例如:軍事中，在目標區(qū)域內(nèi)監(jiān)測到敵軍浸入，但是沒有位置信息無法判斷具體的入侵地點，從而不能采取相應(yīng)的應(yīng)對措施，實現(xiàn)精確的定位對無線傳感器網(wǎng)絡(luò)的協(xié)議特別是基于地理信息路由的設(shè)計、數(shù)據(jù)融合、目標跟蹤等方面都具有非常重要的意義。目前為止，研究人員已提出許多無線傳感器網(wǎng)絡(luò)節(jié)點定位算法，無需測距定位算法由于其硬件要求、網(wǎng)絡(luò)部署成本、能耗等方面的優(yōu)勢，相對來說更適合于無線傳感器網(wǎng)絡(luò)。其中，DV-Hop定位算法簡單、覆蓋度高和可行性好等特點，使得成為了一種經(jīng)濟適用型定位方法。它的主要缺點是定位精度不是很高，因此，對算法作出改進成為了一個研究熱點［3］。

DV-Hop定位算法的第二階段在計算未知節(jié)點平均每跳距離時，所利用的是距離自己最近的信標節(jié)點的平均每跳距離來計算。但是信標節(jié)點的平均每跳距離是通過到除本節(jié)點外所有其他信標節(jié)點的路徑與最小跳數(shù)之比，所以得到的是全網(wǎng)絡(luò)范圍內(nèi)的平均每跳距離，與該信標節(jié)點附近的網(wǎng)絡(luò)分布密度有一定的差別。同時，僅僅利用跳數(shù)來估測距離，定位限制條件不夠充分，不能區(qū)分具有相同跳數(shù)的節(jié)點距離，從而造成較大的定位誤差。針對此問題，許多學(xué)者提出了改進算法，如 Wu Huarui［4］，王新生等人［5］提出把未知節(jié)點附近全部信標節(jié)點的平均每跳距離信息取平均來作為未知節(jié)點的平均每跳距離，但是不能解決相鄰節(jié)點之間距離分布不均引起的每跳估算誤差;周小波等人［6］提出WDV-Hop定位算法，該算法利用第一跳的RSSI作為基準值來修正之后的跳數(shù)，算法也無需進行RSSI測距，計算量適中，算法適應(yīng)性較好，改進的精度適中。羅維等人［7］提出一種SDV-Hop改進算法，該算法選擇距離較近的信標節(jié)點進行定位，同時利用信標節(jié)點來校正未知節(jié)點的估計坐標，但是，該改進算法會減小定位覆蓋率，同時也是在增加一定的計算開銷作為代價。

針對各種改進算法，本文提出一種距離修正算法，在算法中引入RSSI測距技術(shù)來輔助定位，但是，它又不需要基于RSSI進行距離計算，只是利用了RSSI作為距離的比征，對每一跳的距離進行修正，從而提高定位精度，幾乎不需要增加計算和通信開銷。

1 DV-Hop定位算法

DV-Hop算法［8，9］的基本思想是網(wǎng)絡(luò)中各個節(jié)點通過典型的距離矢量交換協(xié)議，獲得到各信標節(jié)點的最小跳數(shù)。各個信標節(jié)點獲得其他信標節(jié)點位置和到它們之間的跳段距離后計算網(wǎng)絡(luò)平均每跳距離，然后未知節(jié)點到信標節(jié)點的最小跳數(shù)乘以平均每跳距離得到位置節(jié)點到信標節(jié)點的距離估測。最后，當未知節(jié)點獲得距3個或者3個以上信標節(jié)點的距離之后，利用三邊測量法進行自身定位。DVHop定位算法主要分為以下3個階段:

1）距離矢量交換階段

每個信標節(jié)點向網(wǎng)絡(luò)廣播一個數(shù)據(jù)包{（xi，yi），Hopnum}，（xi，yi）表示信標節(jié)點的坐標位置，Hopnum為位置節(jié)點到信標節(jié)點的跳數(shù)，初始化為0。每個接收到該數(shù)據(jù)包的鄰居節(jié)點保存該數(shù)據(jù)包，同時將數(shù)據(jù)包中跳數(shù)加1，同時比較來自相同信標節(jié)點的不同跳數(shù)信息，丟棄跳數(shù)大的數(shù)據(jù)包，保存跳數(shù)小的，保證未知節(jié)點到信標節(jié)點的跳數(shù)最小。接著再向自己的鄰居節(jié)點廣播，直到網(wǎng)絡(luò)中所有節(jié)點都獲得與之相鄰信標節(jié)點的位置信息和相應(yīng)的跳數(shù)值。

2）平均跳距估算和廣播階段

每個信標節(jié)點收集到其他信標節(jié)點的位置和跳數(shù)信息后，進行該信標節(jié)點的網(wǎng)絡(luò)平均跳距Hopsizei估算，信標節(jié)點i的平均每跳估算公式如式（1）所示

其中，（xi，yi）為第j個信標節(jié)點位置坐標，Hopnumj為第j個信標節(jié)點到第i個信標節(jié)點的跳數(shù)。信標節(jié)點將計算得到的Hopsizei在網(wǎng)絡(luò)中進行廣播，每個未知節(jié)點僅接收獲得的第一個校正值，丟棄所有后來接收到的值。未知節(jié)點再根據(jù)跳數(shù)信息依照式（2）來計算得到信標節(jié)點的距離d

3）位置估計階段

當未知節(jié)點獲得與3個或3個以上信標節(jié)點距離之后，就可執(zhí)行三邊測量或最大似然估計法定位。

2 基于RSSI比值修正距離估計定位算法

本文提出的基于RSSI比值修正的距離估算算法，從RSSI的測距耗散模型出發(fā)，根據(jù)RSSI理論路徑耗散函數(shù)［6，10］

其中，PL（d）為經(jīng)過距離d后的路徑損耗，dBm;d0為從發(fā)射端附近測量的一個參考距離;n為路徑損耗指數(shù)。從式（3）可以得出路徑耗散值與距離呈反比的關(guān)系。考慮到節(jié)點的接收信號強度可以從無線節(jié)點芯片的寄存器直接讀取，所以，可以充分利用這一點來修正DV-Hop計算所得的節(jié)點之間每一跳的距離，該方法無需經(jīng)過復(fù)雜的RSSI距離轉(zhuǎn)換，直接利用的是每一節(jié)點讀取的RSSI值來構(gòu)造修正系數(shù)εi

其中，RSSIi為節(jié)點i的接收信號強度值，RSSIavg為該節(jié)點在平均跳距廣播階段最先接收到的信標節(jié)點的平均信號強度值，具體如式（5）

其中，j為該信標節(jié)點可以到達周圍的信標節(jié)點個數(shù)，nj為該信標節(jié)點到達周圍第j個信標節(jié)點的最小跳數(shù)。

算法具體詳細過程如下:

1）每個信標節(jié)點產(chǎn)生一個數(shù)據(jù)包{ID，（x，y），Hopnum，RSSIi，RSSI（i）}，ID為信標節(jié)點的編號，每個傳感器節(jié)點都有唯一ID號;（x，y）為該ID號的信標節(jié)點位置坐標;Hopnum為跳數(shù)，初值為0;RSSIi為第i跳節(jié)點接收該數(shù)據(jù)包的信號強度，初值為0;RSSI（i）為第i跳為止全部節(jié)點的接收信號強度的累積，信標節(jié)點以固定功率向周圍廣播數(shù)據(jù)包。

2）直接鄰居節(jié)點接收到數(shù)據(jù)包后將跳數(shù)Hopnum加1，將RSSIi置為其接收數(shù)據(jù)包時的接收信號強度，RSSI（i）置為第i跳為止節(jié)點的接收信號強度之和，其中，i=Hopnum。最后，得到該節(jié)點的數(shù)據(jù)包信息為{ID，（x，y），1，RSSIi，RSSI（1）}，其中，RSSI（1）=RSSI1+RSSI0=RSSI1。

3）接收到信標節(jié)點發(fā)送數(shù)據(jù)包的鄰居節(jié)點以固定功率繼續(xù)向其鄰居節(jié)點發(fā)送數(shù)據(jù)包，接收到數(shù)據(jù)包的鄰居節(jié)點將所得的數(shù)據(jù)包信息變?yōu)閧ID，（x，y），2，RSSI2，RSSI（2）}，其中，RSSI（2）=RSSI2+RSSI1+RSSI0，當同一個節(jié)點先后接收到來自同一個ID號的數(shù)據(jù)包，則判斷該數(shù)據(jù)包中的跳數(shù)與自己已存的同一個ID號的數(shù)據(jù)包中的跳數(shù)值，如果大于或等于已存跳數(shù)，則丟棄新接收的數(shù)據(jù)包;否則，替換。

4）重復(fù)步驟（3），直到經(jīng)過n跳到達另一信標節(jié)點，該數(shù)據(jù)包最后得到的信息為{ID，（x，y），n，RSSIn，RSSI（n）}，其中，RSSI（n）=RSSIn+RSSIn－1+… +RSSI0。最后按照DV-Hop原算法計算信標節(jié)點的平均每跳距離Hopsize，同時根據(jù)式（5）計算平均接收信號強度值RSSIavg。然后，同DVHop方式一樣廣播Hopsize和RSSIavg。

5）計算距離d:首先建立每跳修正系數(shù)，用每一跳的RSSIi與RSSIavg相除，作為該跳跳距的修正系數(shù)εi，如式（5）所示。根據(jù)每跳修正系數(shù)，計算距信標節(jié)點為m跳的未知節(jié)點與信標節(jié)點距離

由以上各步驟，各未知節(jié)點可根據(jù)自身存儲信息表中的累計信號強度RSSI（m）、平均信號強度RSSIavg和平均跳距Hopsize方便地計算出到各個信標節(jié)點的距離。

6）當未知節(jié)點獲得與3個或3個以上信標節(jié)點距離之后，就可執(zhí)行三邊測量或最大似然估計法定位。

3 仿真實驗

由于基于RSSI比值修正距離估算算法涉及到每個節(jié)點的接收信號強度RSSI，而RSSI是通過讀取傳感器節(jié)點中特定的寄存器得到的，而通過仿真軟件無法得到RSSI。考慮到引入RSSI比值理論上主要是利用RSSI來比征距離，所以，使用任意兩節(jié)點間的歐氏距離ED來代替節(jié)點的RSSI。仿真參數(shù)設(shè)置為在網(wǎng)絡(luò)范圍100 m×100 m區(qū)域內(nèi)隨機產(chǎn)生100個網(wǎng)絡(luò)節(jié)點。下面分別討論原DV-Hop定位算法，文獻［6］提出的WDV-Hop定位算法和本文改進算法3種定位算法的網(wǎng)絡(luò)節(jié)點平均相對當定位誤差隨信標節(jié)點比例和通信半徑的影響，其中，相對定位誤差σ定義為

其中，（xr，yr）為節(jié)點真實坐標位置，（xe，ye）為估計坐標位置，R為節(jié)點通信半徑。每種算法性能的仿真都是隨機進行100次而得到的結(jié)果，如圖1，圖2所示。由于文獻［6］的WDV-Hop定位算法在通信半徑小于40 m的時候，定位改進效果較差，甚至與原DV-Hop差不多，所以，取R大于40 m進行仿真，仿真結(jié)果表明:本文改進的算法定位誤差始終小于原DV-Hop和WDV-Hop定位算法，且隨著信標節(jié)點比例的影響不是很大，定位誤差相對較穩(wěn)定，對比圖1和圖2可以發(fā)現(xiàn)，本文改進算法隨著通信半徑的增加，定位誤差也隨之下降。

圖1 通信半徑R=40m相對定位誤差比對圖Fig 1 Relative localization error comparison chart with R=40 m

圖2 通信半徑R=50 m相對定位誤差比對圖Fig 2 Relative position error comparison chart with R=50 m

4 結(jié)論

本文的基于RSSI比值修正的DV-Hop定位算法，與文獻［6］所提的改進算法類似，都是直接利用RSSI進行修正，增加的是有限的加法和除法，也無需信標節(jié)點進行重新廣播，增加的計算和通信開銷幾乎可以忽略不計，同時修正系數(shù)都是一個比值，所以，對環(huán)境適應(yīng)性較大［6］，但比起WDV-Hop定位算法，本文的定位誤差明顯占優(yōu)勢。相比文獻［4，5，7］及其他的一些基于DV-Hop改進算法，本文的改進算法在計算開銷、算法適應(yīng)性、定位覆蓋率等方面都有相對的優(yōu)勢，同時，該改進算法也存在一些不足，如受節(jié)點接收的RSSI影響較大，需要在取得的RSSI值真實的反映節(jié)點間歐氏距離情況下才能保證算法的精度。

［1］ Alemdar H，Ersoy C．Wireless sensor networks for healthcare:A survey［J］．Computer Networks，2010，54:2688 －2700．

［2］ Othmana M F，Shazali K．Wireless sensor network applications:A study in environment monitoring system［J］．Procedia Engineering，2012，41:1204 －1210．

［3］ 劉曉春．無線傳感器網(wǎng)絡(luò)DV-Hop定位算法的改進與仿真［D］．重慶:重慶交通大學(xué)，2011:13－15．

［4］ Wu Huarui，Gao Ronghua．An improved method of DV-Hop localization algorithm［J］．Journal of Computational Information Systems，2011，7（7）:2293 －2298．

［5］ 王新生，趙衍靜，李海濤．基于DV-Hop定位算法的改進研究［J］．計算機科學(xué)，2009，38（2）:76 －90．

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

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

［8］ Niculescu D，Nath B．DV-based positioning in Ad Hoc networks［J］．Telecommunication Systems，2003，22（1）:268 －275．

［9］ 于宏毅，李 鷗，張效義，等．無線傳感器網(wǎng)絡(luò)理論、技術(shù)與實現(xiàn)［M］．北京:國防工業(yè)出版社，2010:260－266．

［10］ Shen Xingfa，Wang Zhi，Jiang Peng．Connectivity and RSSI-based localization scheme for wireless sensor networks［C］∥International Conference on Intelligent Computing，2005:578 －587．