紀 杰，施偉斌

(上海理工大學 光電信息與計算機工程學院，上海 200093)

?

改進的無線傳感器網(wǎng)絡(luò)DV-Hop 節(jié)點定位算法

紀 杰，施偉斌

(上海理工大學 光電信息與計算機工程學院，上海 200093)

DV-Hop 算法是解決無線傳感器網(wǎng)絡(luò)節(jié)點定位問題的一種經(jīng)典算法。文中根據(jù)經(jīng)典的DV-Hop 算法提出了一種改進算法，通過引入更優(yōu)的誤差矯正和雙曲線定位算法，減少了經(jīng)典算法中多跳過程中積累的定位誤差。比較和分析了經(jīng)典DV-Hop 算法和改進后算法的仿真結(jié)果可以看出，改進后的DV-Hop 算法定位精度提高顯著，在給定條件下的定位誤差下降了約50%。

無線傳感器網(wǎng)絡(luò)；DV-Hop；誤差矯正；雙曲線定位算法

JI Jie, SHI Weibin

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology,Shanghai 200093,China)

無線傳感器網(wǎng)絡(luò)由大量無線傳感器節(jié)點組成，廣泛用于在軍事、醫(yī)療、商業(yè)、環(huán)境監(jiān)測等方面[1]，并成為計算機和通信領(lǐng)域的研究熱點。由于傳感器節(jié)點位置的隨機性，無線傳感器網(wǎng)絡(luò)的應用大多基于傳感器節(jié)點自我定位[2]。由于無線傳感網(wǎng)絡(luò)的應用受功耗、傳感器節(jié)點成本等方面的限制，因此對無線傳感網(wǎng)絡(luò)定位算法的研究很有必要。

現(xiàn)有的無線傳感器網(wǎng)絡(luò)節(jié)點定位算法可以分為Range-based 定位算法和Range-free定位算法，即基于測距技術(shù)的定位算法和無需測距的定位算法[3]。Range-based 定位算法測量點到點精確的距離值或角度信息，并使用幾何定位方法來定位未知節(jié)點，例如RSSI,TDOA,TOA 以及AOA。而Range-free 算法通過距離的估計值而非測量值來定位未知節(jié)點，例如質(zhì)心算法和DV-Hop 算法。與Range-based 算法相比，Range-free 方案硬件成本更低、功耗更小，因此受到更多的關(guān)注。本文主要研究無線傳感器網(wǎng)絡(luò)節(jié)點的Range-free算法。

1 DV-Hop 算法

DV-Hop算法主要通過距離矢量和跳數(shù)來估測未知節(jié)點到錨節(jié)點的距離，然后使用三邊或多邊測量法求出未知節(jié)點的位置信息。在未知節(jié)點的通信范圍內(nèi)，錨節(jié)點數(shù)目并不多，采用上述方法可以得到節(jié)點到其通信范圍外的多個錨節(jié)點的距離信息。

DV-Hop 算法主要由以下3個步驟組成[4]：

步驟1 所有錨節(jié)點向整個網(wǎng)絡(luò)以洪泛方式發(fā)送一個信標，信標中包含錨節(jié)點的位置信息以及初始化為1 的跳數(shù)信息。所有接收到信標的節(jié)點都只保留到每個錨節(jié)點的最少跳數(shù)。然后節(jié)點將此信標繼續(xù)向外擴展，跳數(shù)依次遞增。第一步完成后，網(wǎng)絡(luò)中所有的節(jié)點都得到到每個錨節(jié)點的相應的最少跳數(shù)；

步驟2 在完成第一步后，網(wǎng)絡(luò)中所有錨節(jié)點得到到其它所有錨節(jié)點的跳數(shù)信息，對此引入一個估計量，用于估計錨節(jié)點之間平均每跳距離，然后將此估計量洪泛到整個傳感器網(wǎng)絡(luò)。網(wǎng)絡(luò)中的未知節(jié)點接收到此估計量后，將此估計量和到錨節(jié)點的跳數(shù)之積作為未知節(jié)點到錨節(jié)點距離的估計量。錨節(jié)點i的平均每跳距離HopSize可以用下式估計

(1)

其中，(xi,yi)和(xj,yj)是錨節(jié)點i和錨節(jié)點j的坐標；hopij是錨節(jié)點i到錨節(jié)點j之間的跳數(shù)。

所有錨節(jié)點將其平均每跳距離HopSize廣播到整個網(wǎng)絡(luò)中，廣播的方式采用受控洪泛法。未知節(jié)點接收到平均每跳信息，但只存儲其接收到的第一個HopSize。同時，未知節(jié)點將接收到的HopSize 傳播到它們的相鄰節(jié)點。通過采用受控洪泛法可以基本保證大多數(shù)節(jié)點接收到的是到每個錨節(jié)點跳數(shù)最少的HopSize；

步驟3 當未知節(jié)點獲得到錨節(jié)點的3個或3個以上的距離信息時，使用三邊測量法或最大似然估計法來對未知節(jié)點的坐標進行估計。

設(shè)(xu,yu) 是未知節(jié)點u的坐標；(xi，yi) 是已知錨節(jié)點i的坐標；dui是它們之間的距離。由此可得

(2)

未知節(jié)點u的坐標可以通過下式求得

(3)

(4)

(5)

其中，P=(ATA)-1ATB。

2 改進的DV-Hop 算法

主要對DV-Hop 的第二步和第三步進行改進[3-5]。DV-Hop 算法的第二步中，每個錨節(jié)點在獲得了錨節(jié)點之間的平均每跳距離HopSize 后將其廣播到整個網(wǎng)絡(luò)作為矯正值。錨節(jié)點廣播的數(shù)據(jù)包形式為{id,HopSize}, 包含錨節(jié)點的序號及其平均每跳距離。網(wǎng)絡(luò)中的節(jié)點接收到此數(shù)據(jù)包后，將其添加到自己的存儲表中，并將其傳播給鄰居節(jié)點。第一步完成后，網(wǎng)絡(luò)中所有節(jié)點都獲得了各錨節(jié)點廣播的HopSize。改進的DV-Hop 算法通過求取n個錨節(jié)點的HopSize的平均值作為網(wǎng)絡(luò)中節(jié)點間平均每跳距離的估計值[6-8]，即

(6)

其中，n是錨節(jié)點的個數(shù)HopSize，通過式(1)可以求得。在第二步最后，未知節(jié)點到錨節(jié)點的距離可以用di來估計，即

di=Hops×HopSizeave

(7)

第三步，假設(shè)(x,y)是未知節(jié)點的坐標，(xi,yi) 是錨節(jié)點i的坐標，未知節(jié)點到錨節(jié)點之間的距離用di表示，顯然有

(8)

在DV-Hop 算法中，未知節(jié)點到錨節(jié)點之間的距離估計量id和錨節(jié)點的坐標一起用于未知節(jié)點的幾何定位方法中。在本文提出的改進DV-Hop 算法中，不再采取傳統(tǒng)的幾何定位方法，而采用一種二維雙曲線定位算法[9]。

根據(jù)式(8)繼續(xù)推導如下

(9)

即得到

(10)

Zc=[x,y，K]T

(11)

(12)

(13)

根據(jù)式(9)和式(10)得

(14)

未知節(jié)點的坐標(x，y)可表示為

(15)

3 算法仿真與結(jié)果分析

分別對經(jīng)典DV-Hop 算法和改進DV-Hop 算法進行仿真,仿真參數(shù)設(shè)置如表1 所示。

表1 仿真參數(shù)設(shè)置

仿真中，節(jié)點通過隨機數(shù)產(chǎn)生函數(shù)rand 在正方形區(qū)域內(nèi)隨機生成，經(jīng)典DV-Hop 算法的節(jié)點分布如圖1 所示。

對經(jīng)典DV-Hop 算法進行仿真后，得到的未知節(jié)點的定位誤差曲線如圖2 所示，經(jīng)典DV-Hop 算法未知節(jié)點的定位誤差最高可達約60%，且圍繞約40%上下波動。定位誤差相對較大。

改進DV-Hop 算法的節(jié)點分布如圖3 所示。對改進DV-Hop 算法進行仿真后，得到未知節(jié)點的定位誤差曲線如圖4 所示，改進DV-Hop 算法未知節(jié)點定位誤差最高可達到約30%，且圍繞約15%上下波動，定位誤差相對較小。

圖1 經(jīng)典DV-Hop算法的節(jié)點分布圖

圖2 經(jīng)典DV-Hop算法的未知節(jié)點定位誤差

為更加直觀地對比改進DV-Hop 算法與經(jīng)典DV-Hop 算法的定位精確度，分別對兩種算法進行了100 次獨立重復實驗，各得到未知節(jié)點定位誤差的100 組數(shù)據(jù)。通過求取每組數(shù)據(jù)中92 個未知節(jié)點定位誤差的算術(shù)平均值作為平均定位誤差率，可以得到兩種算法各100 個平均定位誤差率的數(shù)值。仿真結(jié)果如圖5 所示。

圖3 改進DV-Hop 算法的節(jié)點分布圖

圖4 改進算法未知節(jié)點的定位誤差

圖5 經(jīng)典DV-Hop 算法和改進DV-Hop 算法平均定位誤差率比較

如圖5所示，改進DV-Hop 算法明顯比經(jīng)典DV-Hop 算法誤差率小、定位精度高。因此采用改進DV-Hop 算法能明顯降低節(jié)點的平均定位誤差率。

4 結(jié)束語

本文提出了一種改進的DV-Hop 算法，可以大幅地提高經(jīng)典DV-Hop 算法的定位精度，而無需增加硬件系統(tǒng)的復雜度和成本。這是由于改進的DV-Hop 算法采用了更優(yōu)的誤差矯正和雙曲線定位算法，從而減少了經(jīng)典算法中多跳過程中積累的定位誤差。仿真結(jié)果證明了改進DV-Hop算法比原算法更具應用價值。在本文設(shè)定的 100 m×100 m范圍內(nèi)，改進DV-Hop 算法其定位平均誤差率約為0.3，而經(jīng)典DV-Hop 算法的定位平均誤差率約為0.6，可見改進DV-Hop 算法將經(jīng)典DV-Hop 算法的定位精度提高了約50%。

本文沒有考慮錨節(jié)點占總節(jié)點個數(shù)的比例、節(jié)點通信半徑、總節(jié)點個數(shù)、錨節(jié)點的分布等因素對未知節(jié)點定位誤差的影響。因此，以后的研究可以從上述幾方面進行。

[1] 史龍,王福豹,段渭軍,等.無線傳感器網(wǎng)絡(luò)Range-Free 自身定位機制與算法[J].計算機工程與應用,2004(6):11-13.

[2] 馬祖長,孫怡寧.無線傳感器網(wǎng)絡(luò)節(jié)點的定位算法[J].計算機工程,2004(6):23-25.

[3] Chen Hongyang, Kaoru Sezaki, Ping Deng, et al.An improved DV-Hop localization algorithm for wireless sensor networks [J]. Eiectronics Optics & Control, 2008(9):2232-2236.

[4] 張震,閆連山,劉江濤,等.基于DV-Hop 的無線傳感器網(wǎng)絡(luò)定位算法研究[J]. 傳感技術(shù)學報， 2011(8):1469-1472.

[5] Chen Xiao,Zhang Benliang.Improved DV-Hop node localization algorithm in wireless sensor networks[J].International Journal of Distributed Sensor Networks,2012(6):111-113.

[6] 劉乃安.無線局域網(wǎng)(WLAN)原理、技術(shù)與應用[M]. 西安：西安電子科技大學出版社,2004.

[7] 張攀東,閔娟娟. WLAN規(guī)劃和設(shè)計時需要考慮的問題[J].福建電腦, 2011(6): 76-77.

[8] 王振亞. WLAN優(yōu)化系統(tǒng)的設(shè)計與實現(xiàn)[D].武漢：華中師范大學,2014.

[9] 楊寧. WLAN規(guī)劃檢測優(yōu)化系統(tǒng)的設(shè)計與實現(xiàn)[J].計算機時代, 2013(9): 11-14.

Improved DV-Hop Node Localization Algorithm for Wireless Sensor Networks

The DV-Hop algorithm is a classical algorithm for node localization in wireless sensor networks. In this paper, an improved algorithm is proposed based on the classical DV-Hop algorithm to reduce the positioning error accumulated in the multi hop process by introducing a better error correction and the hyperbolic location algorithm. After comparing and analyzing the classical DV-Hop algorithm and the improved algorithm, the simulation results show that the improved DV-Hop algorithm can improve the positioning accuracy significantly, with the positioning error reduced by about 50% under the given conditions.

wireless sensor networks; DV-Hop; error correction; hyperbolic location algorithm

2016- 01- 06

全國大學生科技創(chuàng)新重點基金資助項目(201310252012)

紀杰(1992-)，男，碩士研究生。研究方向：通信技術(shù)等。

10.16180/j.cnki.issn1007-7820.2016.10.025

TN926

A

1007-7820(2016)10-086-04