胡江坤，付 晶，冉松山，唐宏成

(重慶機(jī)場集團(tuán)有限公司 航務(wù)管理部，重慶 401120)

一種改進(jìn)型WSN DV-Hop定位算法

胡江坤，付 晶，冉松山，唐宏成

(重慶機(jī)場集團(tuán)有限公司 航務(wù)管理部，重慶 401120)

針對無線傳感器網(wǎng)絡(luò)中DV-Hop定位精度較低，且定位精度完全依賴于未知節(jié)點到對應(yīng)錨節(jié)點的跳數(shù)以及平均跳距的測量精度這一問題，提出一種改進(jìn)型DV-Hop算法。通過仿真實驗表明，在節(jié)點個數(shù)、通信半徑、以及錨節(jié)點率一定時，該算法的平均定位誤差比DV-Hop的平均定位誤差分別減小25%，19%和22%。

無線傳感器網(wǎng)絡(luò)；測量精度；定位誤差；DV-Hop

AbstractAccording to the lower localization accuracy of DV-Hop algorithm in WSN, as well as, itslocalization accuracy based on the distance between unknown nodes and anchor nodes, and the measure-ment precision of average jump distance, this paper presents an improved DV-Hop algorithm.The simula-tion results show that:when nodes numbers、communication radius and anchor nodes rates are under givenconditions，average positioning error of the improved algorithm has been reduced 25%,19% and 22% res-pectively.

Keywordswireless sensor networks;measurement precision;localization;DV-Hop

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)是由大量靜止的或移動的傳感器節(jié)點以自組織和多跳的方式構(gòu)成的無線網(wǎng)絡(luò)，其目的是協(xié)作地感知、采集、處理和傳輸網(wǎng)絡(luò)覆蓋地理區(qū)域內(nèi)感知對象的監(jiān)測信息，并報告給用戶[1]。

在無線傳感器網(wǎng)絡(luò)中，節(jié)點的定位至關(guān)重要，GPS是目前應(yīng)用最廣的定位服務(wù)，但受到成本、功耗、擴(kuò)展性等問題的限制，甚至在某些場合根本無法實現(xiàn)。目前最主要的節(jié)點定位方法是利用少量已知節(jié)點，通過節(jié)點定位算法獲得未知節(jié)點的信息。因此需要采用一定的定位機(jī)制與算法來獲得未知節(jié)點的信息。研究者已經(jīng)提出了多種算法解決WSN定位問題，主要分為測距定位和非測距定位兩種方法[2]，基于測距的定位算法通過測量節(jié)點間點到點的距離或角度信息，使用三邊測量、三角測量或極大似然估計法計算未知節(jié)點位置。基于測距的定位算法常用的測距技術(shù)有接收信號強(qiáng)度指示器(Received Signal Strength Indicator，RSSI)[3]、到達(dá)時間(Time of Advent，TOA)[4]、到達(dá)時間差(Time Difference of Arrival，TDOA)[5]、到達(dá)角(Angle of Arrival，AOA)[6]。與距離無關(guān)的定位算法利用網(wǎng)絡(luò)的連通性進(jìn)行定位，成本和功耗相對較小，且無需額外的硬件支持，因此受到較大的關(guān)注[7]。

1 DV-Hop定位算法

DV-Hop(Distance Vector-Hop, DV-Hop)算法是Niculescu和Nath等人提出的[12-15]，基本思想分為3個步驟。

步驟1錨節(jié)點在全網(wǎng)中廣播自己的位置數(shù)據(jù)包，格式為

{(xi,yi),idi,hopsi}

(1)

其中，(xi,yi)是錨節(jié)點i的位置坐標(biāo)；idi是錨節(jié)點i的標(biāo)識號，hopsi為跳數(shù)值，將其初始化為0，每個接收到此數(shù)據(jù)包的節(jié)點將此數(shù)據(jù)記錄到自身的數(shù)據(jù)表中然后將其跳數(shù)值加1后轉(zhuǎn)發(fā)給其鄰居節(jié)點。當(dāng)接收節(jié)點接收到相同id號的數(shù)據(jù)包時就將跳數(shù)值與自身數(shù)據(jù)表中存放的跳數(shù)值比較，如果較小則代替原表中的數(shù)據(jù)，否則丟棄該數(shù)據(jù)包，并且也不轉(zhuǎn)發(fā)。最后，通過網(wǎng)絡(luò)洪泛法，記錄全網(wǎng)中的所有節(jié)點到對應(yīng)錨節(jié)點的最小跳數(shù)值。

步驟2計算各個錨節(jié)點的平均每跳的距離。通過步驟1計算出各個錨節(jié)點到其它錨節(jié)點的跳數(shù)值和位置信息，再通過式(2)估算其平均每跳的距離

(2)

式中，(xi,yi)和(xj,yj)分別是錨節(jié)點i和j的坐標(biāo)；hops(i,j)為錨節(jié)點i與j之間的最小跳數(shù)值。將HopSizei作為一個校正值通過可控洪泛法廣播至網(wǎng)絡(luò)中，而每個待定位節(jié)點僅接收獲得的第一個校正值。待定位節(jié)點(xk,yk)到錨節(jié)點i的距離用該錨節(jié)點平均每跳的距離與到該錨節(jié)點的跳數(shù)的乘積表示，如式(3)所示

d(i,k)=HopSizei×hops(i,k)

(3)

步驟3當(dāng)待定位節(jié)點獲得3個或更多的錨節(jié)點的距離后，則執(zhí)行三邊測量定位法或極大似然估計法進(jìn)行定位。

由于DV-Hop[8]節(jié)點定位法對錨節(jié)點的比例要求不高，且定位精度較高，算法比較簡單，所以成為了一種與距離無關(guān)的經(jīng)典的的定位算法。

目前，有學(xué)者對該算法進(jìn)行了改進(jìn)，如文獻(xiàn)[9]提出了利用無線信號在同種介質(zhì)中的傳播速度不變性，用計時器來測量信息在錨節(jié)點間的傳送時間以及錨節(jié)點與未知節(jié)點間的傳送時間，并利用該時間比例來修正未知節(jié)點的估計距離；文獻(xiàn)[10]提出了一種基于RSSI的DV-Hop加權(quán)算法，該算法利用節(jié)點接收錨節(jié)點位置信息時的信號強(qiáng)度對鄰居節(jié)點間跳數(shù)進(jìn)行加權(quán)處理，將節(jié)點間的跳數(shù)與距離相關(guān)聯(lián)；文獻(xiàn)[11]利用最小均方誤差對平均跳距進(jìn)行改進(jìn)，并考慮到傳感器節(jié)點通常部署在非平面應(yīng)用場景，通過補(bǔ)償系數(shù)來校正未知節(jié)點到錨節(jié)點之間的距離，提出一種基于補(bǔ)償系數(shù)的定位算法。這些方法在一定程度上能夠提高定位精度，但是為了提高定位精度和定位覆蓋率，還需還需對DV-Hop算法進(jìn)行改進(jìn)。

2 改進(jìn)型DV-Hop定位算法

本文主要從以下兩方面進(jìn)行算法的改進(jìn)：

(1)通過極大似然估計法估計錨節(jié)點間的平均每跳距離值。首先假設(shè)錨節(jié)點i通過經(jīng)典的距離矢量交換協(xié)議獲得了n個錨節(jié)點的位置信息和跳數(shù)信息。再假設(shè)錨節(jié)點i和錨節(jié)點j之間測量距離Dij服從正態(tài)分布

N(cihopsij,σ2)

(4)

其概率密度函數(shù)為式(5)所示

(5)

其中，ci是錨節(jié)點i的平均每跳距離；hopsij是錨節(jié)點i和錨節(jié)點j之間的跳數(shù)，而實際距離di1,di2,…,din,即為一個樣本值，其中

(6)

建立MLE法的似然函數(shù)

(7)

對式(7)兩邊同時取對數(shù)可得

(8)

以ci為變量，對式(8)兩邊同時求導(dǎo)得

(9)

令導(dǎo)數(shù)等于0得

(10)

假設(shè)網(wǎng)絡(luò)中共有m個錨節(jié)點，則網(wǎng)絡(luò)的平均每跳距離c如下

(11)

最后將網(wǎng)絡(luò)平均每跳距離c廣播出去；

(2)通過引入一種空數(shù)據(jù)包Empty Packet，沒有實際的數(shù)據(jù)信息。在無線傳感器網(wǎng)絡(luò)路由拓?fù)湟呀?jīng)建立好的情況下，用來在各個節(jié)點之間傳送以計算路徑之間的通信時間，然后利用此時間信息來校正節(jié)點間的跳數(shù)值。

步驟1錨節(jié)點廣播自己的位置信息數(shù)據(jù)包，同時開始啟動定時器。此位置信息數(shù)據(jù)包格式如式(12)所示

{(xi,yi),idi,hopsi}

(12)

每個錨節(jié)點在收到其他錨節(jié)點的位置信息后記錄到自身的數(shù)據(jù)表中然后返回帶自身標(biāo)識的Empty Packet;

步驟2當(dāng)某錨節(jié)點收到返回的Empty Packet后停止計時，此時計時器便會得到兩個錨節(jié)點之間的數(shù)據(jù)包來回傳送時間T(i,j)，計算兩個錨節(jié)點之間單程數(shù)據(jù)包的純傳送時間t(i,j)如式(13)所示

(13)

其中，Δt為傳感器節(jié)點從接收到完成發(fā)送數(shù)據(jù)包所需時間，不同類型的傳感器節(jié)點該值不同但都是固定的。計算兩錨節(jié)點之間的平均每跳的傳送時間值Δt(i,j)為

(14)

步驟3假設(shè)錨節(jié)點i收到n個錨節(jié)點的位置信息和時間信息，則計算平均每跳距離值ci和平均每跳傳送時間值Δti如下

(15)

然后將ci廣播出去。當(dāng)每個錨節(jié)點收到其他錨節(jié)點的平均每跳距離值后計算網(wǎng)絡(luò)平均每跳距離值c如式(11)所示；

步驟4未知節(jié)點發(fā)送一個包含自身標(biāo)識號的請求定位信息包，同時啟動定時器。錨節(jié)點收到請求定位信息后發(fā)送數(shù)據(jù)包為

{(xi,yi),idi,c,Δti,hopsi}

(16)

步驟5未知節(jié)點收到錨節(jié)點發(fā)送的上述數(shù)據(jù)包后停止定時器并記錄傳送時間T(i,k)，然后計算自己到錨節(jié)點單程數(shù)據(jù)包的純傳送時間，如未知節(jié)點k到錨節(jié)點i的單程數(shù)據(jù)包純傳送時間為t(i,k)

(17)

步驟6計算未知節(jié)點k到錨節(jié)點i的跳數(shù)值h(i,k)

(18)

計算未知節(jié)點k到錨節(jié)點i的距離d(i,k)

d(i,k)=h(i,k)×c

(19)

步驟7如果未知節(jié)點得到了3個及其以上的距離值后，再通過極大似然估計法或者三邊測量法計算未知節(jié)點的位置信息。

3 仿真分析

為驗證本文的改進(jìn)算法對DV-Hop算法在對未知節(jié)點進(jìn)行定位時各方面性能的改進(jìn)，使用Matlab進(jìn)行仿真。在一個100 m×100 m的正方形區(qū)域內(nèi)隨機(jī)部署了若干節(jié)點進(jìn)行驗證。初始節(jié)點的隨機(jī)分布如圖1所示。

圖1 初始節(jié)點隨機(jī)分布

定理1平均定位誤差。平均定位誤差是指所有未知節(jié)點的定位誤差之和與未知節(jié)點個數(shù)的比值，如下

(20)

圖2為節(jié)點個數(shù)與平均定位誤差之間的關(guān)系。在固定大小的實驗平面區(qū)域內(nèi)通過改變節(jié)點總數(shù)來改變平均網(wǎng)絡(luò)節(jié)點密度。其中節(jié)點通信半徑R=15 m，錨節(jié)點比例為10%，節(jié)點數(shù)從150遞增到400。由圖2可知，改進(jìn)型DV-Hop算法平均定位誤差比DV-Hop算法平均定位誤差減小了約25%。

圖2 節(jié)點個數(shù)與定位誤差

圖3 通信半徑與定位誤差

圖3為節(jié)點通信半徑與節(jié)點平均定位誤差之間的關(guān)系。其中節(jié)點數(shù)為400，錨節(jié)點數(shù)為40。當(dāng)節(jié)點通信半徑由15 m遞增到50 m時，改進(jìn)型DV-Hop算法平均定位誤差比DV-Hop算法平均定位誤差減小了約19%。

圖4為錨節(jié)點比率與平均定位誤差之間的關(guān)系。其中節(jié)點個數(shù)為400，通信半徑為R=15 m，錨節(jié)點比率從5%遞增到40%，由圖4可知，改進(jìn)型DV-Hop算法平均定位誤差比DV-Hop算法平均定位誤差減小了約22%。

圖4 錨節(jié)點比率與定位誤差

4 結(jié)束語

本文提出了一種基于標(biāo)準(zhǔn)的DV-Hop算法的改進(jìn)算法，仿真實驗表明，該改進(jìn)算法有效提高了未知節(jié)點的定位精度。改進(jìn)后算法也有不足之處，在用計數(shù)器計算信息在節(jié)點之間傳輸時，通信數(shù)據(jù)量增大，導(dǎo)致節(jié)點能量消耗增大。

[1] Mizugaki K,Fujiwara R,Nakagawa T,et al.Accurate wireless location system with 22-cm error using UWB-IR[C].Washington,DC:Radio and Wireless Symposium,2007.

[2] 張愛清,葉新榮,胡海峰,等.基于每跳分級和跳距修正的改進(jìn)算法[J].儀器儀表學(xué)報,2012,11(33):2552-2556.

[3] Hart A,Hopper A,Steggles P.The anatomy of a context aware application[J].Wireless Network, 2011(1):1-16.

[4] Chen Xiao,Zhang Benliang.Improved DV-Hop node locali-

zation algorithm in wireless sensor networks[J].Intetnational Jorunal of Distributed Sensor Networks,2012,10(6):111-113.

[5] Girod L,Bychovskiy V,Elson J,et al.Locating tiny sensors in time and space:a case study[C].Germany:IEEE I-CCD,2002.

[6] Girod L,Estrin D.Robust range estimation using acoustic and multimodal sensing[C].Hawaii:Proc of the IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS01),2001.

[7] 李彥,田亮.一種結(jié)合輔助估距錨點的改進(jìn)型算法[J].南京郵電大學(xué)學(xué)報:自然科學(xué)版,2016, 36(5):120-126.

[8] 紀(jì)杰,施偉斌.改進(jìn)的無線傳感器網(wǎng)絡(luò)DV-Hop節(jié)點定位算法[J].電子科技,2016,29(10):86-88.

[9] 趙靈鍇,洪志全.基于無線傳感器網(wǎng)絡(luò)的-定位算法的改進(jìn)[J].計算機(jī)應(yīng)用,2011,31(5):1189-1192.

[10] 周小波,喬鋼柱,曾建潮.無線傳感器網(wǎng)絡(luò)中基于的加權(quán)定位方法[J].計算機(jī)工程與應(yīng)用,2011,4(14):109-115.

[11] 朱青青,楊玉斌,劉娜,等.無線傳感器網(wǎng)絡(luò)中基于一致性的安全定位方法[J].計算機(jī)工程,2016,10(42):151-157.

[12] Niculescu D,Nath B.DV based positioning in Ad hoc networks[J].Journal of Telecommunication Systems,2003,22(174): 267-280.

[13] 韓震,肖鐵軍.基于跳數(shù)修正的DV-Hop改進(jìn)算法[J].電子科技,2015,28(1):158-163.

[14] 劉彩霞,黃延磊.中抵御蟲洞攻擊的改進(jìn)的算法研究[J].傳感技術(shù)學(xué)報,2011,24(10):1473-1478.

[15] 李志遠(yuǎn).無線傳感器網(wǎng)絡(luò)中DV-Hop算法研究[D].南京:南京理工大學(xué),2010.

An Improved Algorithm for the DV-Hop Localization of Wireless Sensor Network

HU Jiangkun,FU Jing,RAN Songsan,TANG Hongcheng

(Navigation Department,Chongqing Airport Group Co.,Ltd.,Chongqing 401120,China)

TN926

A

1007-7820(2017)10-119-04

2016- 12- 12

胡江坤(1988-)，男，碩士研究生。研究方向：民用航空通信導(dǎo)航技術(shù)。付晶(1986-)，男，碩士研究生。研究方向：民用航空通信導(dǎo)航技術(shù)。

10.16180/j.cnki.issn1007-7820.2017.10.032