紀(jì) 杰，施偉斌

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

?

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

紀(jì) 杰，施偉斌

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

DV-Hop 算法是解決無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位問題的一種經(jīng)典算法。文中根據(jù)經(jīng)典的DV-Hop 算法提出了一種改進(jìn)算法，通過引入更優(yōu)的誤差矯正和雙曲線定位算法，減少了經(jīng)典算法中多跳過程中積累的定位誤差。比較和分析了經(jīng)典DV-Hop 算法和改進(jìn)后算法的仿真結(jié)果可以看出，改進(jìn)后的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é)點(diǎn)組成，廣泛用于在軍事、醫(yī)療、商業(yè)、環(huán)境監(jiān)測(cè)等方面[1]，并成為計(jì)算機(jī)和通信領(lǐng)域的研究熱點(diǎn)。由于傳感器節(jié)點(diǎn)位置的隨機(jī)性，無線傳感器網(wǎng)絡(luò)的應(yīng)用大多基于傳感器節(jié)點(diǎn)自我定位[2]。由于無線傳感網(wǎng)絡(luò)的應(yīng)用受功耗、傳感器節(jié)點(diǎn)成本等方面的限制，因此對(duì)無線傳感網(wǎng)絡(luò)定位算法的研究很有必要。

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

1 DV-Hop 算法

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

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

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

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

(1)

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

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

步驟3 當(dāng)未知節(jié)點(diǎn)獲得到錨節(jié)點(diǎn)的3個(gè)或3個(gè)以上的距離信息時(shí)，使用三邊測(cè)量法或最大似然估計(jì)法來對(duì)未知節(jié)點(diǎn)的坐標(biāo)進(jìn)行估計(jì)。

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

(2)

未知節(jié)點(diǎn)u的坐標(biāo)可以通過下式求得

(3)

(4)

(5)

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

2 改進(jìn)的DV-Hop 算法

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

(6)

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

di=Hops×HopSizeave

(7)

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

(8)

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

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

(9)

即得到

(10)

Zc=[x,y，K]T

(11)

(12)

(13)

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

(14)

未知節(jié)點(diǎn)的坐標(biāo)(x，y)可表示為

(15)

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

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

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

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

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

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

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

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

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

圖3 改進(jìn)DV-Hop 算法的節(jié)點(diǎn)分布圖

圖4 改進(jìn)算法未知節(jié)點(diǎn)的定位誤差

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

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

4 結(jié)束語

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

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

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

[2] 馬祖長(zhǎng),孫怡寧.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位算法[J].計(jì)算機(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ù)學(xué)報(bào)， 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ù)與應(yīng)用[M]. 西安：西安電子科技大學(xué)出版社,2004.

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

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

[9] 楊寧. WLAN規(guī)劃?rùn)z測(cè)優(yōu)化系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)時(shí)代, 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

全國(guó)大學(xué)生科技創(chuàng)新重點(diǎn)基金資助項(xiàng)目(201310252012)

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

10.16180/j.cnki.issn1007-7820.2016.10.025

TN926

A

1007-7820(2016)10-086-04