馬淑麗，趙建平

(曲阜師范大學(xué) 物理工程學(xué)院,山東 曲阜 273165 )

WSN中基于最佳指數(shù)的加權(quán)DV-Hop算法*

馬淑麗，趙建平

(曲阜師范大學(xué) 物理工程學(xué)院,山東 曲阜 273165 )

DV-Hop算法是一種低成本、低定位精度的無需測距定位算法，在粗精度定位中應(yīng)用廣泛。為提高DV-Hop算法定位精度，從減小錨節(jié)點(diǎn)的平均每一跳距離誤差和減小未知節(jié)點(diǎn)平均每一跳校正值誤差兩方面考慮。首先，用最佳指數(shù)值下的公式計(jì)算錨節(jié)點(diǎn)平均每一跳距離。然后，將未知節(jié)點(diǎn)的校正值加權(quán)處理，使所有的錨節(jié)點(diǎn)根據(jù)與未知節(jié)點(diǎn)距離的遠(yuǎn)近影響校正值的大小。MATLAB實(shí)驗(yàn)證明，改進(jìn)的基于最佳指數(shù)值下的加權(quán)DV-Hop算法比DV-Hop算法、加權(quán)DV-Hop、最佳指數(shù)值下DV-Hop算法定位精度分別提高2%左右、1.65%左右、1.15%左右，同時(shí)不會(huì)增加網(wǎng)絡(luò)硬件成本。

無線傳感器網(wǎng)絡(luò);節(jié)點(diǎn)定位;加權(quán)DV-Hop算法;最小均方差

0 引 言

近幾年來，國內(nèi)無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)的應(yīng)用越來越廣泛[1]，其關(guān)鍵技術(shù)的研究也越來越受到重視。WSN關(guān)鍵技術(shù)包括節(jié)點(diǎn)定位技術(shù)、路由協(xié)議技術(shù)、時(shí)間同步、信息融合等[2]，而這些關(guān)鍵技術(shù)成為限制WSN發(fā)展的瓶頸。WSN中有大量微型低成本的傳感器節(jié)點(diǎn)，在一些環(huán)境惡劣或無人值守的應(yīng)用中，節(jié)點(diǎn)一般由飛機(jī)散落或?qū)椛⑸?，?jié)點(diǎn)負(fù)責(zé)采集并將信息發(fā)送出去[3]。然而，如果不知道節(jié)點(diǎn)的位置，那么采集的信息毫無意義[4]。

由于成本原因，節(jié)點(diǎn)中只有少數(shù)裝有GPS[5]，其它節(jié)點(diǎn)只能靠定位技術(shù)計(jì)算坐標(biāo)。無需測距的定位算法由于成本低、簡單等原因應(yīng)用較廣[6]，其中DV-Hop算法是眾多學(xué)者一直在研究并改進(jìn)突破的熱點(diǎn)算法之一。本文結(jié)合其他文獻(xiàn)改進(jìn)DV-Hop算法。

1 DV-Hop算法概述

DV-Hop定位算法是由美國羅格斯大學(xué)(Rutgers University)Dragos Niculescu等人提出的6種分布式定位算法之一[7]。

DV-Hop定位算法只是利用節(jié)點(diǎn)間的傳輸跳數(shù)值信息和錨節(jié)點(diǎn)的坐標(biāo)值進(jìn)行未知節(jié)點(diǎn)的坐標(biāo)計(jì)算。假設(shè)網(wǎng)絡(luò)中：所有節(jié)點(diǎn)都可以進(jìn)行雙通信，通信過程無障礙，每個(gè)節(jié)點(diǎn)都有自己的通信范圍即通信半徑，自帶GPS 導(dǎo)航設(shè)備的錨節(jié)點(diǎn)有n個(gè)。

DV-Hop算法步驟[8-10]：

第一步：錨節(jié)點(diǎn)向網(wǎng)絡(luò)廣播信息，包括自身位置信息、初始跳數(shù)值、節(jié)點(diǎn)編號(hào)等。路由方式為泛洪方式。設(shè)定一個(gè)較大的跳數(shù)值閾值，轉(zhuǎn)播過程中如果跳數(shù)值超過閾值則轉(zhuǎn)發(fā)停止。接收節(jié)點(diǎn)接到信息后，比較接收跳數(shù)值的大小，如果比自己保留的跳數(shù)值大則拋棄信息，如果較小則保留信息，并將跳數(shù)值加1轉(zhuǎn)發(fā)出去。

第二步：錨節(jié)點(diǎn)根據(jù)第一步得知的其它錨節(jié)點(diǎn)位置信息等，計(jì)算自己的平均每一跳距離。

(1)

錨節(jié)點(diǎn)i到其他錨節(jié)點(diǎn)的平均每一跳距離是dHopi。錨節(jié)點(diǎn)i、j間的最小跳數(shù)是hij。

第三步：錨節(jié)點(diǎn)再次向網(wǎng)絡(luò)廣播信息，包括自己的平均每一跳距離信息、節(jié)點(diǎn)編號(hào)。未知節(jié)點(diǎn)就近原則只接收一個(gè)錨節(jié)點(diǎn)的信息，并將其作為自己計(jì)算平均每一跳距離時(shí)的校正值。假設(shè)未知節(jié)點(diǎn)l的校正值為dHopp(即錨節(jié)點(diǎn)p為向該未知節(jié)點(diǎn)第一個(gè)送達(dá)信息)，未知節(jié)點(diǎn)l與錨節(jié)點(diǎn)j間的跳數(shù)為hlj。未知節(jié)點(diǎn)估算自己與其它錨節(jié)點(diǎn)間的距離如下式。

dlj=dHopp×hlj

(2)

第四步：未知節(jié)點(diǎn)得到所有錨節(jié)點(diǎn)間的估算距離后，用三邊測量法、極大似然法等計(jì)算自身坐標(biāo)。假設(shè)未知節(jié)點(diǎn)坐標(biāo)(x,y)，未知節(jié)點(diǎn)與錨節(jié)點(diǎn)i間的估算距離di。

極大似然估計(jì)法：

(3)

AX=b

(4)

(5)

(6)

(7)

算法的性能指標(biāo)用定位精度判定，定位精度值越小定位精度越高，如式(8):

(8)

網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)為N，節(jié)點(diǎn)通信半徑R，節(jié)點(diǎn)i真實(shí)坐標(biāo)與估算坐標(biāo)分別為(x0i,y0i)、(xi,yi)。

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

文獻(xiàn)[11]提出根據(jù)信號(hào)的強(qiáng)弱對(duì)跳數(shù)值加權(quán)，修正值為0.5或1的DV-Hop改進(jìn)算法。文獻(xiàn)[12]提出對(duì)錨節(jié)點(diǎn)的平均每一跳距離進(jìn)行加權(quán)，提出基于加權(quán)系數(shù)矩陣的DV-Hop改進(jìn)算法。文獻(xiàn)[13-14]等也基于加權(quán)的DV-Hop算法研究了一系列的改進(jìn)算法。加權(quán)的DV-Hop算法比DV-Hop算法提高了定位精度。文獻(xiàn)[15]提出改進(jìn)錨節(jié)點(diǎn)平均每一跳距離的DV-Hop算法，在最小均方差準(zhǔn)則下提出最佳指數(shù)值概念，也提高了DV-Hop算法定位精度。

由于節(jié)點(diǎn)在網(wǎng)絡(luò)中隨機(jī)部署，節(jié)點(diǎn)間的距離不一致，有的距離大有的距離小，而在DV-Hop算法中，計(jì)算節(jié)點(diǎn)間跳數(shù)值時(shí)，在通信半徑R范圍內(nèi)的節(jié)點(diǎn)全記為1，這樣距離較大和距離較小的節(jié)點(diǎn)間的跳數(shù)值可能會(huì)相同。最后會(huì)導(dǎo)致錨節(jié)點(diǎn)用式(1)計(jì)算自己平均每一跳距離時(shí)與實(shí)際平均每一跳距離間的誤差很大?？紤]減小錨節(jié)點(diǎn)平均每一跳距離誤差，文獻(xiàn)[15]利用最小均方差準(zhǔn)則，提出的改進(jìn)公式：

(9)

根據(jù)多次仿真實(shí)驗(yàn)，將改進(jìn)的算法定位精度最高時(shí)的α值，作為最佳指數(shù)值。

在DV-Hop算法第三步中，未知節(jié)點(diǎn)只是利用離自己最近的錨節(jié)點(diǎn)，將其平均每一跳距離作為校正值，然后用式(2)求該未知節(jié)點(diǎn)與所有錨節(jié)點(diǎn)間的估算距離。這樣會(huì)導(dǎo)致錨節(jié)點(diǎn)利用率低、估算距離誤差大。文獻(xiàn)[12,14]等考慮充分利用所有錨節(jié)點(diǎn)，根據(jù)錨節(jié)點(diǎn)與未知節(jié)點(diǎn)的遠(yuǎn)近(依據(jù)跳數(shù)值大小判定)，對(duì)每個(gè)錨節(jié)點(diǎn)的平均每一跳距離乘以一個(gè)加權(quán)系數(shù)。這個(gè)系數(shù)根據(jù)所有錨節(jié)點(diǎn)與未知節(jié)點(diǎn)節(jié)點(diǎn)間的跳數(shù)值確定。然后，將每個(gè)錨節(jié)點(diǎn)加權(quán)處理后的平均每一跳距離求和。最后，將該和代入式(2)求未知節(jié)點(diǎn)與每個(gè)錨節(jié)點(diǎn)間的估算距離。

本文將上述改進(jìn)的方法結(jié)合，提出基于最佳指數(shù)值下的加權(quán)DV-Hop改進(jìn)算法。并驗(yàn)證可以進(jìn)一步提高定位精度。本文改進(jìn)算法：

假如共有n個(gè)錨節(jié)點(diǎn)，求未知節(jié)點(diǎn)i到所有錨節(jié)點(diǎn)的估算距離時(shí)，錨節(jié)點(diǎn)j的加權(quán)系數(shù)Mji為：

(10)

錨節(jié)點(diǎn)j加權(quán)處理后的平均每一跳距離為：

MDji=Mji×dHopj

(11)

此處的dHopj由式(9)計(jì)算。未知節(jié)點(diǎn)i的校正值為：

(12)

未知節(jié)點(diǎn)i與錨節(jié)點(diǎn)f(f取1～n)的估算距離為：

dif=MJi×hif

(13)

3 實(shí)驗(yàn)仿真

將仿真環(huán)境建立在100 m×100 m的正方形區(qū)域，將100個(gè)節(jié)點(diǎn)隨機(jī)部署在網(wǎng)絡(luò)，錨節(jié)點(diǎn)覆蓋率取9%～32%，通信半徑取22～45 m。

3.1 不同通信半徑下多種算法對(duì)比

錨節(jié)點(diǎn)覆蓋率取9%，仿真不同通信半徑下多種改進(jìn)的DV-Hop定位算法和本文改進(jìn)的DV-Hop算法。

首先，求加權(quán)DV-Hop算法下的最佳指數(shù)值。在不同的通信半徑下，將α取不同的值，仿真改進(jìn)的算法。由于節(jié)點(diǎn)分布的隨機(jī)性，將程序循環(huán)100次取平均值。

如圖1所示，在相同通信半徑下，隨著指數(shù)值增大，定位精度先提高后降低。在通信半徑22、23、24、…、32 m，分別對(duì)應(yīng)有最佳的指數(shù)，使定位精度最高。由圖1可知，最佳指數(shù)值分別為1.99、1.99、1.99、1.98、1.97、…、1.97。

圖1 不同通信半徑下求最佳指數(shù)值

然后，將最佳指數(shù)值代入式(9)得錨節(jié)點(diǎn)平均每一跳距離，然后代入式(11)，開始進(jìn)行最佳指數(shù)值下的加權(quán)DV-Hop定位。為了便于與文獻(xiàn)[15]對(duì)比，也求出文獻(xiàn)[15]改進(jìn)算法下的最佳指數(shù)。將本文算法與文獻(xiàn)[12]加權(quán)DV-Hop算法、文獻(xiàn)[15]最佳指數(shù)值DV-Hop算法、DV-Hop算法對(duì)比仿真，如圖2所示。

圖2 不同通信半徑下4種算法對(duì)比

在不同的通信半徑下，本文改進(jìn)的最佳指數(shù)加權(quán)DV-Hop算法都比其它算法明顯的占優(yōu)勢。隨著通信半徑的增大4種算法定位精度都降低。通信半徑34米時(shí)，本文改進(jìn)的算法比DV-Hop算法、文獻(xiàn)[12]加權(quán)DV-Hop算法、文獻(xiàn)[15]最佳指數(shù)DV-Hop算法分別提高定位精度2.05%、1.65%、1.12%。

3.2 不同錨節(jié)點(diǎn)覆蓋率下多種算法對(duì)比

通信半徑取34 m，仿真不同錨節(jié)點(diǎn)覆蓋率下多種改進(jìn)的DV-Hop定位算法和本文改進(jìn)的DV-Hop算法。

在不同的錨節(jié)點(diǎn)覆蓋率下，將α取不同的值，求加權(quán)DV-Hop算法下的最佳指數(shù)值。將程序循環(huán)100次取平均值。如圖2所示，在不同的錨節(jié)點(diǎn)覆蓋率下，分別對(duì)應(yīng)有最佳的指數(shù)，使定位精度最高。最佳指數(shù)值分別為1.95、1.94、1.94、1.93、1.94、1.93、1.93、…、1.92。

圖2 不同錨節(jié)點(diǎn)覆蓋率下求最佳指數(shù)值

將本文算法與文獻(xiàn)[15]最佳指數(shù)值DV-Hop算法、DV-Hop算法對(duì)比仿真，如圖3所示。

圖3 不同錨節(jié)點(diǎn)覆蓋率下3種算法對(duì)比

在不同的錨節(jié)點(diǎn)覆蓋率下，本文改進(jìn)的最佳指數(shù)加權(quán)DV-Hop算法比其它算法占優(yōu)勢。錨節(jié)點(diǎn)覆蓋率28%時(shí)，本文算法定位精度達(dá)到最高，為0.241%。錨節(jié)點(diǎn)覆蓋率14%時(shí)，本文改進(jìn)的算法比DV-Hop算法、文獻(xiàn)[15]最佳指數(shù)DV-Hop算法分別提高定位精度2.8%、1.2%。

3.3 不同錨節(jié)點(diǎn)覆蓋率和不同通信半徑對(duì)比

在不同的錨節(jié)點(diǎn)覆蓋率和不同的通信半徑下，對(duì)比本文算法和DV-Hop算法，如圖4所示。本文算法定位精度總體比DV-Hop算法高2%左右。

圖4

以上實(shí)驗(yàn)結(jié)果說明，可以將最佳指數(shù)值下求平均每一跳距離的式(9)應(yīng)用到加權(quán)求未知節(jié)點(diǎn)校正值的式(12)里，這樣改進(jìn)的DV-Hop算法能提高定位精度，同時(shí)不會(huì)增加節(jié)點(diǎn)硬件成本和節(jié)點(diǎn)泛洪次數(shù)。

4 結(jié) 語

本文結(jié)合文獻(xiàn)[12]和文獻(xiàn)[15]改進(jìn)DV-Hop算法。用文獻(xiàn)[15]提出的最佳指數(shù)值下的公式求錨節(jié)點(diǎn)平均每一跳距離，然后根據(jù)文獻(xiàn)[12]提出的加權(quán)DV-Hop算法，將平均每一跳距離乘以加權(quán)系數(shù)，該系數(shù)使離未知節(jié)點(diǎn)較近的錨節(jié)點(diǎn)能較大的影響未知節(jié)點(diǎn)的定位。MATLAB仿真實(shí)驗(yàn)，找出不同條件下的最佳指數(shù)值，然后帶入本文算法，發(fā)現(xiàn)本文改進(jìn)的算法比文獻(xiàn)[12]、文獻(xiàn)[15]提出的改進(jìn)算法更占優(yōu)勢。在相同定位條件下，本文算法能提高2%左右定位精度。下一步研究，改進(jìn)基于多通信半徑的DV-Hop算法。

[1] 陳瑜,張鐵民,孫道宗等.基于無線傳感器網(wǎng)絡(luò)的設(shè)施農(nóng)業(yè)車輛定位系統(tǒng)設(shè)計(jì)與試驗(yàn)[J].農(nóng)業(yè)工程學(xué)報(bào),2015, 31(10):190-197. CHEN Yu, ZHANG Tie-min, SUN Dao-zong, et al. Design and Experiment of Locating System for Facilities Agricultural Vehicle based on Wireless Sensor Network[J].Transactions of the Chinese Society of Agricultural Engineering(Transactions of the CSAE),2015,31(10):190-197.

[2] 許毅.無線傳感器網(wǎng)絡(luò)原理及方法[M].北京:清華大學(xué)出版社,2012:53. XU Yi.Principles and Methods of Wireless Sensor Networks[M].Beijing:Tsinghua University press, 2012:53.

[3] 李建奇,孔玲爽,王輔文等.基于無線傳感器網(wǎng)絡(luò)的葡萄栽培環(huán)境監(jiān)測系統(tǒng)[J].排灌機(jī)械工程學(xué)報(bào),2014,32 (07):637-644. LI Jian-qi, KONG Ling-shuang, WANG Fu-wen, et al. Wireless Sensor Network based Viticulture Environmental Monitoring System[J].Journal of Drainage and Irrigation Machinery Engineering (JDIME).2014,32(07):637-644.

[4] 周明偉.無線傳感器網(wǎng)絡(luò)的安全定位研究[D].無錫：江南大學(xué),2014. ZHOU Ming-wei. Research on Security Location of Wireless Sensor Networks[D].WuXi：Jiangnan University,2014.

[5] 朱敏,劉昊霖,張志宏等.一種基于DV-Hop改進(jìn)的無線傳感器網(wǎng)絡(luò)定位算法[J].四川大學(xué)學(xué)報(bào):工程科學(xué)版,2012,44(01):93-98. ZHU Min, LIU Hao-Lin, ZHANC Zhi-hong, et al. An Improved Localization Algorithm based on DV-HOP in WSN[J].Journal of Sichuan University(Engineering Science Edition),2012,44(01):93-98.

[6] 高翔.無線傳感器網(wǎng)絡(luò)低功耗路由與節(jié)點(diǎn)目標(biāo)跟蹤定位研究[D].西安：西安電子科技大學(xué),2011. GAO Xiang. Research on Energy-Efficient Routing Protocols and Target Tracking in Wireless Sensor Networks[D]. Xi'an：Xi'an Electronic and Science University,2011.

[7] 陳敏，王擘，李軍華.無線傳感器網(wǎng)絡(luò)原理與實(shí)踐[M].北京：化學(xué)工業(yè)出版社，2011. CHEN Min, WANG Bo, LI Jun-hua. Wireless Sensor Network Theory and Practice [M]. Beijing: Chemical Industry Press, 2011.

[8] Gayan S,Dias D.Improved Dv-Hop Algorithm Through Anchor Position Re-Estimation[C]. Wireless and Mobile, 2014 IEEE Asia Pacific Conference on. (Aug 2014)126-131.

[9] CHANG Xiao-hui, LUO Xiong. An Improved Self-Localization Algorithm for Ad hoc Network based on Extreme Learning Machine[C].Intelligent Control and Automation (WCICA),2014 11th World Congress on.IEEE,2014,564-569.

[10] HU Juan, JIANG Min-lan. An Improved Node Localization Algorithm in Wireless Sensor Network [C].Advanced Research and Technology in Industry Applications (WARTIA),2014 IEEE Workshop on, Sept2014,398-401.

[11] 倪海燕,應(yīng)祥岳,簡家文.無線傳感器網(wǎng)絡(luò)中基于DV-Hop的一種改進(jìn)算法[J].工業(yè)控制計(jì)算機(jī),2008,21 (12):43-45. NI Hai-yan, YING Xiang-yue, JIAN Jia-wen.An Improved Algorithm based on DV-Hop in Wireless Sensor Networks[J]. Industrial Control Computer, 2008, 21 (12):43-45.

[12] 馮江,朱強(qiáng),吳春春.改進(jìn)的DV-Hop定位算法研究[J].計(jì)算機(jī)工程,2012,38(19):74-81. FENG Jiang, ZHU Qiang, WU Chun-chun. Research on Improved DV-Hop Localization Algorithm[J]. Computer Engineering,2012,38(19):74-81.

[13] 魏全瑞,劉俊,韓九強(qiáng).改進(jìn)的無線傳感器網(wǎng)絡(luò)無偏距離估計(jì)與節(jié)點(diǎn)定位算法[J].西安交通大學(xué)學(xué)報(bào),2014, 48(06):1-6. WEI Quan-rui, LIU Jun, HAN Jiu-qiang. An Improved DV-Hop Node Localization Algorithm based on Unbiased Estimation for Wireless Sensor Networks [J].Journal of Xi’an Jiaotong University,2014,48(06):1-6.

[14] 蔣馥珍.基DV-HOP的無線傳感器網(wǎng)絡(luò)定位算法研究[D].太原：太原理工大學(xué),2011. JIANF Fu-zhen. Research on Location Algorithm Based on DV-Hop in WSN[D]. Taiyuan ：Taiyuan University of Technology,2011.

[15] 馬淑麗,趙建平.無線傳感器網(wǎng)絡(luò)中DV-Hop定位算法的改進(jìn)[J].通信技術(shù),2015,48(07):840-844. MA Shu-li,ZHAO Jian-ping. The Improvement of DV-Hop Algorithm in Wireless Sensor Networks[J]. Communications Technology, 2015, 48(07):840-844.

Weighted DV-HopAlgorithm based on Optimal Index in WSN

MA Shu-li，ZHAO Jian-ping

(College of Physics Engineering, Qufu Normal University, Qufu Shandon 273165, China )

DV-Hop algorithm, as a range-free localization algorithm with low cost, low positioning accuracy, is widely used in coarse-precision positioning. In order to improve the location accuracy of DV-Hop algorithm, two aspects should be considered, i.e.,to decrease average hop distance error of anchor node and to reduce average hop correction value error of unknown node. Firstly, the average hop distance of anchor node is calculated by formula with the best index value. Then, the correction value of unknown node is weighted, so that all the anchor nodes could be corrected in accordance with the distance from unknown node. MATLAB results indicate that the location accuracy of the modified weighted DV-Hop algorithm based on optimal index is improved approximately 2%, 1.65% and 1.15% respectively as compared with that of DV-Hop algorithm, weighted DV-Hop and DV-Hop algorithm with optimal index value, and meanwhile with no increase of the network hardware cost.

wireless sensor network; node localization; weighted DV-Hop; least mean square error

10.3969/j.issn.1002-0802.2015.10.010

2015-05-17；

2015-09-03 Received date:2015-05-17；Revised date：2015-09-03

國家自然科學(xué)基金(No.11302118)；山東省自然科學(xué)基金(No.ZR2014FM011)；山東省高等學(xué)?？萍加?jì)劃項(xiàng)目(No.J12LN08)

Foundation Item:National Natural Science Foundation of China(No.11302118); National Natural Science Foundation of Shandong Province(No. ZR2014FM011);Supported by the Science and Technology Project of Higher Education of Shandong Province(No.J12LN08)

TP393

A

1002-0802(2015)10-1147-05

馬淑麗(1989—)，女，碩士研究生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、無線通信技術(shù)；

趙建平(1964—)，男，教授，主要研究方向?yàn)闊o線通信技術(shù)。