一種新的無線傳感器網絡DV-Hop算法

張 品，孫 巖

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

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

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

在WSNs中，根據(jù)在定位過程中是否測量節(jié)點間的距離，可以將定位算法分為兩大類：range-based算法[6](基于測距的算法)和range-free算法[7](無需測距的算法)。Range-based定位算法需要測量節(jié)點間的絕對距離或角度信息來進行定位，其中測距技術包括：信號到達時間(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算法、質心算法、MDP-MAP算法及APIT算法等。

1 DV-Hop定位算法的描述

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

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

第1階段采用防洪廣播的形式廣播信息，錨節(jié)點在網絡中廣播一個消息，該消息包含了該信標的標識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ù)包，也不再進行轉發(fā)。這樣以泛洪的形式在整個網絡中廣播每個錨節(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。假設每一條邊的長度為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é)點就將這個值在網絡中廣播，未知節(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之間的距離在一跳之內， 可以很容易的獲得，但用DV-hop卻用曲線平均來計算它們之間的距離，因此增大了誤差。所以在本文中介紹了一種新的基于RSSI的DV-hop節(jié)點定位算法，名字叫做RDV-hop算法，這種算法同時運用了DV-hop算法和RSSI技術，改善了未知節(jié)點定位的誤差減小了用DV-hop算法在錨節(jié)點附近的未知節(jié)點定位的誤差。例如，如圖2所示。

圖2 新的DV-Hop算法

在圖2中，我們假設L1， L2和L3均為錨節(jié)點，節(jié)點M為需要定位的未知節(jié)點。三個錨節(jié)點的實際距離分別為15， 30， 30。假設每條邊的長度為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é)點產生并在網絡中廣播RSSI數(shù)據(jù)包，任何一個接收到RSSI數(shù)據(jù)報的節(jié)點都可以計算出它與此錨節(jié)點的距離。在圖2 中，節(jié)點M距L1、L2都只有一條的距離，所以節(jié)點M可以直接獲得從L1、L2發(fā)出的RSSI數(shù)據(jù)包，從而計算出它與L1、L2的距離(假設為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ū)域內，如圖3所示每個節(jié)點的無線覆蓋范圍設為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 結論

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

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

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

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

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

[ 5] 孫利民，李建中，等.無線傳感器網絡[ 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.