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

楊 祥，潘 瑋

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

0 引言

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

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

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

1 DV-Hop定位算法

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

1）距離矢量交換階段

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

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

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

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

3）位置估計(jì)階段

當(dāng)未知節(jié)點(diǎn)獲得與3個(gè)或3個(gè)以上信標(biāo)節(jié)點(diǎn)距離之后，就可執(zhí)行三邊測量或最大似然估計(jì)法定位。

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

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

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

其中，RSSIi為節(jié)點(diǎn)i的接收信號(hào)強(qiáng)度值，RSSIavg為該節(jié)點(diǎn)在平均跳距廣播階段最先接收到的信標(biāo)節(jié)點(diǎn)的平均信號(hào)強(qiáng)度值，具體如式（5）

其中，j為該信標(biāo)節(jié)點(diǎn)可以到達(dá)周圍的信標(biāo)節(jié)點(diǎn)個(gè)數(shù)，nj為該信標(biāo)節(jié)點(diǎn)到達(dá)周圍第j個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)。

算法具體詳細(xì)過程如下:

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

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

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

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

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

由以上各步驟，各未知節(jié)點(diǎn)可根據(jù)自身存儲(chǔ)信息表中的累計(jì)信號(hào)強(qiáng)度RSSI（m）、平均信號(hào)強(qiáng)度RSSIavg和平均跳距Hopsize方便地計(jì)算出到各個(gè)信標(biāo)節(jié)點(diǎn)的距離。

6）當(dāng)未知節(jié)點(diǎn)獲得與3個(gè)或3個(gè)以上信標(biāo)節(jié)點(diǎn)距離之后，就可執(zhí)行三邊測量或最大似然估計(jì)法定位。

3 仿真實(shí)驗(yàn)

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

其中，（xr，yr）為節(jié)點(diǎn)真實(shí)坐標(biāo)位置，（xe，ye）為估計(jì)坐標(biāo)位置，R為節(jié)點(diǎn)通信半徑。每種算法性能的仿真都是隨機(jī)進(jìn)行100次而得到的結(jié)果，如圖1，圖2所示。由于文獻(xiàn)［6］的WDV-Hop定位算法在通信半徑小于40 m的時(shí)候，定位改進(jìn)效果較差，甚至與原DV-Hop差不多，所以，取R大于40 m進(jìn)行仿真，仿真結(jié)果表明:本文改進(jìn)的算法定位誤差始終小于原DV-Hop和WDV-Hop定位算法，且隨著信標(biāo)節(jié)點(diǎn)比例的影響不是很大，定位誤差相對較穩(wěn)定，對比圖1和圖2可以發(fā)現(xiàn)，本文改進(jì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定位算法，與文獻(xiàn)［6］所提的改進(jìn)算法類似，都是直接利用RSSI進(jìn)行修正，增加的是有限的加法和除法，也無需信標(biāo)節(jié)點(diǎn)進(jìn)行重新廣播，增加的計(jì)算和通信開銷幾乎可以忽略不計(jì)，同時(shí)修正系數(shù)都是一個(gè)比值，所以，對環(huán)境適應(yīng)性較大［6］，但比起WDV-Hop定位算法，本文的定位誤差明顯占優(yōu)勢。相比文獻(xiàn)［4，5，7］及其他的一些基于DV-Hop改進(jìn)算法，本文的改進(jìn)算法在計(jì)算開銷、算法適應(yīng)性、定位覆蓋率等方面都有相對的優(yōu)勢，同時(shí)，該改進(jìn)算法也存在一些不足，如受節(jié)點(diǎn)接收的RSSI影響較大，需要在取得的RSSI值真實(shí)的反映節(jié)點(diǎn)間歐氏距離情況下才能保證算法的精度。

［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定位算法的改進(jìn)與仿真［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ìn)研究［J］．計(jì)算機(jī)科學(xué)，2009，38（2）:76 －90．

［6］ 周小波，喬鋼柱，曾建潮．無線傳感器網(wǎng)絡(luò)中基于RSSI的加權(quán)DV-Hop定位方法［J］．計(jì)算機(jī)工程與設(shè)計(jì)，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ù)與實(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．