一種新的無線傳感器網(wǎng)絡(luò)DV-Hop算法

張 品，孫 巖

(杭州電子科技大學通信工程學院， 杭州310037)

近幾十年來，隨著通信技術(shù)、嵌入式計算機技術(shù)、微處理技術(shù)和傳感器技術(shù)的飛速發(fā)展與日益成熟，無線傳感器網(wǎng)絡(luò)(WSNs)在無線通信和數(shù)字電子技術(shù)的促進下迅速發(fā)展，由于具有感知能力、通信能力和計算能力，所以開始受到廣泛的關(guān)注。在大多數(shù)應用場景下，沒有傳感器的位置信息而只感知數(shù)據(jù)是沒有意義的，只有結(jié)合了位置信息傳感器獲取的數(shù)據(jù)才有實際的意義[2]。另外，了解傳感器的節(jié)點位置信息還可以提高路由效率，例如設(shè)計基于節(jié)點位置信息的路由算法以提高路由效率[3-4]，因此，實現(xiàn)節(jié)點的自身定位對WSNs有著重要的意義。

到目前為止，已經(jīng)提出了許多的傳感器網(wǎng)絡(luò)節(jié)點定位算法，這些算法大部分都假設(shè)網(wǎng)絡(luò)中包含一小部分的錨節(jié)點，所謂的錨節(jié)點就是可以通過GPS定位設(shè)備[5]或者其他硬件設(shè)備來獲取自身位置信息的節(jié)點。而其他不知道自己的位置信息的節(jié)點被稱作是未知節(jié)點。錨節(jié)點可以協(xié)助未知節(jié)點來進行位置定位。當一個未知節(jié)點知道三個或者三個以上的錨節(jié)點的位置信息時，它就可以通過三邊定位來確定自己的位置。

在WSNs中，根據(jù)在定位過程中是否測量節(jié)點間的距離，可以將定位算法分為兩大類：range-based算法[6](基于測距的算法)和range-free算法[7](無需測距的算法)。Range-based定位算法需要測量節(jié)點間的絕對距離或角度信息來進行定位，其中測距技術(shù)包括：信號到達時間(time of arrival， TOA)、信號到達角度(angle of arrival， AOA)[6]、信號 到達時間差(time difference on arrival， TDOA)[8]、信 號 強 度(received signal strength indicator， RSSI)等[9]。此類算法對硬件要求較高，需額外的硬件支持。但其中RSSI(基于信號強度的測距)對硬件要求較低，是一種廉價而有效地測距解決方案。Range-free定位算法不需要測量節(jié)點間的距離和方位，對硬件要求簡單，但定位誤差較大，不過可以滿足大部分不需要定位精度很高的場合。典型的Range-free算法包括：DV-hop算法、質(zhì)心算法、MDP-MAP算法及APIT算法等。

1 DV-Hop定位算法的描述

DV-hop算法[10]是為了克服直接三邊定位算法的缺點提出的，它有效的避免了對節(jié)點的直接測量，由美國路特葛斯大學的Niculescu等人提出的。該算法的核心思想是：將未知節(jié)點到錨節(jié)點的距離用傳感器網(wǎng)絡(luò)的每跳平均距離和兩者之間的距離的乘積表示，然后再用三角計算理論獲得未知節(jié)點的位置信息。該算法要解決的問題有2：第1，要計算出未知節(jié)點到錨節(jié)點的跳數(shù)；第2，要計算出每跳平均距離。未知節(jié)點到錨節(jié)點的距離由它們之間的跳數(shù)乘以每跳平均距離得到。

DV-hop算法的步驟有三個階段組成：

第1階段采用防洪廣播的形式廣播信息，錨節(jié)點在網(wǎng)絡(luò)中廣播一個消息，該消息包含了該信標的標識id，位置坐標以及跳數(shù)Hops，初始化Hops為0，接收到此數(shù)據(jù)的每個節(jié)點將Hops+1并記錄到一張表格中，然后繼續(xù)向新的鄰居節(jié)點廣播。當節(jié)點接收到一個相同的id數(shù)據(jù)包時便與表中相同id的數(shù)據(jù)包的Hops相比較，若新的跳數(shù)小于表中已存在的跳數(shù)，就用新的跳數(shù)更新表中的跳數(shù)信息，否則丟棄該數(shù)據(jù)包，也不再進行轉(zhuǎn)發(fā)。這樣以泛洪的形式在整個網(wǎng)絡(luò)中廣播每個錨節(jié)點的信息，這樣錨節(jié)點獲得了其他所有的錨節(jié)點的坐標及跳數(shù)，未知節(jié)點也知道了其與錨節(jié)點的跳數(shù)，這樣就由每一個錨節(jié)點的每跳平均距離可以由此節(jié)點到其他的錨節(jié)點的總的距離之和除以總的跳數(shù)之和得到。

第2階段求得每個未知節(jié)點到錨節(jié)點的距離，每個節(jié)點到錨節(jié)點的距離可以由每跳平均距離乘以此未知節(jié)點到錨節(jié)點的跳數(shù)得到。

第3階段進行三角計算獲得節(jié)點的位置坐標。

2 DV-Hop算法的不足之處

DV-hop算法可以獲得未知節(jié)點無線射程覆蓋范圍以外的錨節(jié)點的距離，并不需要測量節(jié)點之間的實際距離，但用每跳平均距離計算出未知節(jié)點與錨節(jié)點的距離是有誤差的，對于那些和錨節(jié)點相距只有一跳的未知節(jié)點來說，它也需要用每跳平均距離來計算，這樣誤差將非常的大。例如，如圖1所示。

圖1 某一種節(jié)點分布情況(應用傳統(tǒng)DV-Hop算法)

在圖中L1， L2， L3均是錨節(jié)點， A是需要定位的未知節(jié)點。三個錨節(jié)點知道它們相互之間的距離，分別如圖所示為30， 30和40。 A與L1之間的距離是15，跳數(shù)是1。 A到L2和到L3的跳數(shù)都是3。假設(shè)每一條邊的長度為10。

由DV-hop算法可知， L1， L2， L3的計算如下所示：

L1： (30+30)/(4+4)=7.5；

L2： (30+40)/(4+6)=7；

L3： (30+40)/(4+6)=7

在錨節(jié)點計算完每跳平均距離之后，錨節(jié)點就將這個值在網(wǎng)絡(luò)中廣播，未知節(jié)點就將它第一個接收到的值作為每跳平均距離，在此例中L1， L2， L3將分別廣播它們計算出的值7.5， 7和7。由于節(jié)點A與L1的距離只有一跳，所以節(jié)點A將7.5作為每跳平均距離，然后節(jié)點A就計算它與其他三個錨節(jié)點的距離，與L1的距離為7.5，與L2、L3的距離都為7.5?3=22.5。接下來用三角計算獲得節(jié)點A的坐標。

3 算法的改進——新的DV-Hop算法

A與L1的實際距離為15，用DV-hop算法估算出來的距離卻為 7.5， 這樣定位誤差就達到了200%。因此在最后用三角計算獲得的節(jié)點A的實際位置坐標的誤差將會很大。節(jié)點A與錨節(jié)點L1之間的距離在一跳之內(nèi)， 可以很容易的獲得，但用DV-hop卻用曲線平均來計算它們之間的距離，因此增大了誤差。所以在本文中介紹了一種新的基于RSSI的DV-hop節(jié)點定位算法，名字叫做RDV-hop算法，這種算法同時運用了DV-hop算法和RSSI技術(shù)，改善了未知節(jié)點定位的誤差減小了用DV-hop算法在錨節(jié)點附近的未知節(jié)點定位的誤差。例如，如圖2所示。

圖2 新的DV-Hop算法

在圖2中，我們假設(shè)L1， L2和L3均為錨節(jié)點，節(jié)點M為需要定位的未知節(jié)點。三個錨節(jié)點的實際距離分別為15， 30， 30。假設(shè)每條邊的長度為10。用DV-hop算法三個錨節(jié)點將分別計算每跳平均距離：

L1： (15+30)/(2+4)=7.5；

L2： (15+30)/(2+4)=7.5；

L3： (30+30)/(4+4)=7.5

同時所有的錨節(jié)點產(chǎn)生并在網(wǎng)絡(luò)中廣播RSSI數(shù)據(jù)包，任何一個接收到RSSI數(shù)據(jù)報的節(jié)點都可以計算出它與此錨節(jié)點的距離。在圖2 中，節(jié)點M距L1、L2都只有一條的距離，所以節(jié)點M可以直接獲得從L1、L2發(fā)出的RSSI數(shù)據(jù)包，從而計算出它與L1、L2的距離(假設(shè)為10)。節(jié)點M所得到的錨節(jié)點的信息少于三個，然后用DV-hop算法計算節(jié)點M與其他錨節(jié)點的距離，節(jié)點M計算出它與L3的距離是7.5×3=22.5。最后節(jié)點M就可以用三邊定位來計算自己的坐標了。

4 仿真

200個節(jié)點隨機的分布在10 000 m×10 000 m的區(qū)域內(nèi)，如圖3所示每個節(jié)點的無線覆蓋范圍設(shè)為1 500 m。錨節(jié)點以適當?shù)谋壤植荚谄渲小?/p>

圖3 200個節(jié)點隨機分布

我們將未知節(jié)點的實際位置與估算出的位置坐標的誤差作為衡量兩種算法的標準，如圖4 ～圖7所示為在不同的錨節(jié)點比例下的DV-hop算法與改進后的RDV-hop算法之間定位誤差的比較，圖4中的下邊的一條曲線表示新算法的定位誤差曲線，而圖4中上邊的曲線則表示老的DV-hop算法的定位誤差曲線。圖4 ～圖7分別表示了在錨節(jié)點的比例為5%， 10 %， 15%和20%的情況下兩種算法定位誤差的比較，圖中上邊的曲線均表示老的DV-hop算法的定位誤差曲線，而下邊的曲線則表示新算法的定位誤差曲線。

圖4 錨節(jié)點的比例為5 %

圖5 錨節(jié)點的比例為10 %

圖6 錨節(jié)點的比例為15 %

圖7 錨節(jié)點的比例為20 %

如圖4 ～圖7所示，我們可以看出新的DV-hop算法在不同的錨節(jié)點比例的情況下的定位誤差都要好于老的DV-hop算法。另外在圖中可以看到，隨著錨節(jié)點的增加可以用RSSI來計算距離的鄰居節(jié)點越來越多，所以隨著錨節(jié)點的增加算法的精確度有所提高。

5 結(jié)論

定位成本和定位的精確度是衡量定位算法好壞的兩個重要標準。本文介紹了一種新的定位算法，這種定位算法將DV-hop算法與RSSI結(jié)合起來，用RSSI的優(yōu)點來改善DV-hop算法，提高了DV-hop算法的精確度。用這種新的算法在計算那些與錨節(jié)點只有一跳距離的未知節(jié)點時用RSSI來替代DV-hop算法，此時定位誤差明顯減小。仿真實驗已表明此種方法的正確性。但是這種算法有局限性，只有在那些與錨節(jié)點只有一跳距離的未知節(jié)點的定位誤差可以減小，如何改善整個網(wǎng)絡(luò)所有的未知節(jié)點的定位誤差還需進一步的研究。

[ 1] Akyildiz F， SuW， Sandarasurbramaniam Y， et al.Wireless Sensor Networks：a Survey[ J] .Computer Networks Journal， 2002，38(4)：393-422.

[ 2] 王焱欣，王培康.一種無線傳感器網(wǎng)絡(luò)定位算法的分析和改進[ D] .中國科技大學， 2007.

[ 3] 王珊珊，殷建平，蔡志平，等.基于RSSI的無線傳感器網(wǎng)絡(luò)的節(jié)點自身定位算法[ D] .國防科技大學， 2008.

[ 4] 陳浩.無線傳感器網(wǎng)絡(luò)路由協(xié)議的研究[ D] .吉林大學碩士學位論文， 30-35.

[ 5] 孫利民，李建中，等.無線傳感器網(wǎng)絡(luò)[ M] .北京：清華大學出版社， 2005.

[ 6] Bahl P， Padmanabhan V N.RADAR：An In-building RF-based User Location and Tracking System[ C] //Proc.of IEEE INFOCOM， March， 2000.

[ 7]He T， Huang C， Blum B M， et al.Range-free Localization Schemes in Large Scale Sensor Networks[ C] //Proceedings of ACM MobiCom.Canada， 2003.

[ 8] Harter A， Hopper A， Steggles P， et al.The Anatomy of a Context-a Ware Application[ J] .Proc.Of MOBICON， 1999.

[ 9] Tian S， Zhang X， Liu P， etal.A RSSI-based DV-hop A lgorithms for Wireless Sensor Networks[ C] //W ireless Communications，Network and Mobile Computing， 2007.China：Hefei， 2007：2555-2558.

[ 10] Niculescu D， Nath B.Ad Hoc Positioning System(APS)Using AOA[ C] //Proceedings of IEEE IN FOCOM.Sarrfransisco， 2003.