WSN中基于最佳指數的加權DV-Hop算法*

馬淑麗，趙建平

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

WSN中基于最佳指數的加權DV-Hop算法*

馬淑麗，趙建平

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

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

無線傳感器網絡;節點定位;加權DV-Hop算法;最小均方差

0 引 言

近幾年來，國內無線傳感器網絡(Wireless Sensor Network，WSN)的應用越來越廣泛[1]，其關鍵技術的研究也越來越受到重視。WSN關鍵技術包括節點定位技術、路由協議技術、時間同步、信息融合等[2]，而這些關鍵技術成為限制WSN發展的瓶頸。WSN中有大量微型低成本的傳感器節點，在一些環境惡劣或無人值守的應用中，節點一般由飛機散落或導彈散射，節點負責采集并將信息發送出去[3]。然而，如果不知道節點的位置，那么采集的信息毫無意義[4]。

由于成本原因，節點中只有少數裝有GPS[5]，其它節點只能靠定位技術計算坐標。無需測距的定位算法由于成本低、簡單等原因應用較廣[6]，其中DV-Hop算法是眾多學者一直在研究并改進突破的熱點算法之一。本文結合其他文獻改進DV-Hop算法。

1 DV-Hop算法概述

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

DV-Hop定位算法只是利用節點間的傳輸跳數值信息和錨節點的坐標值進行未知節點的坐標計算。假設網絡中：所有節點都可以進行雙通信，通信過程無障礙，每個節點都有自己的通信范圍即通信半徑，自帶GPS 導航設備的錨節點有n個。

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

第一步：錨節點向網絡廣播信息，包括自身位置信息、初始跳數值、節點編號等。路由方式為泛洪方式。設定一個較大的跳數值閾值，轉播過程中如果跳數值超過閾值則轉發停止。接收節點接到信息后，比較接收跳數值的大小，如果比自己保留的跳數值大則拋棄信息，如果較小則保留信息，并將跳數值加1轉發出去。

第二步：錨節點根據第一步得知的其它錨節點位置信息等，計算自己的平均每一跳距離。

(1)

錨節點i到其他錨節點的平均每一跳距離是dHopi。錨節點i、j間的最小跳數是hij。

第三步：錨節點再次向網絡廣播信息，包括自己的平均每一跳距離信息、節點編號。未知節點就近原則只接收一個錨節點的信息，并將其作為自己計算平均每一跳距離時的校正值。假設未知節點l的校正值為dHopp(即錨節點p為向該未知節點第一個送達信息)，未知節點l與錨節點j間的跳數為hlj。未知節點估算自己與其它錨節點間的距離如下式。

dlj=dHopp×hlj

(2)

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

極大似然估計法：

(3)

AX=b

(4)

(5)

(6)

(7)

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

(8)

網絡中節點個數為N，節點通信半徑R，節點i真實坐標與估算坐標分別為(x0i,y0i)、(xi,yi)。

2 改進的DV-Hop定位算法

文獻[11]提出根據信號的強弱對跳數值加權，修正值為0.5或1的DV-Hop改進算法。文獻[12]提出對錨節點的平均每一跳距離進行加權，提出基于加權系數矩陣的DV-Hop改進算法。文獻[13-14]等也基于加權的DV-Hop算法研究了一系列的改進算法。加權的DV-Hop算法比DV-Hop算法提高了定位精度。文獻[15]提出改進錨節點平均每一跳距離的DV-Hop算法，在最小均方差準則下提出最佳指數值概念，也提高了DV-Hop算法定位精度。

由于節點在網絡中隨機部署，節點間的距離不一致，有的距離大有的距離小，而在DV-Hop算法中，計算節點間跳數值時，在通信半徑R范圍內的節點全記為1，這樣距離較大和距離較小的節點間的跳數值可能會相同。最后會導致錨節點用式(1)計算自己平均每一跳距離時與實際平均每一跳距離間的誤差很大。考慮減小錨節點平均每一跳距離誤差，文獻[15]利用最小均方差準則，提出的改進公式：

(9)

根據多次仿真實驗，將改進的算法定位精度最高時的α值，作為最佳指數值。

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

本文將上述改進的方法結合，提出基于最佳指數值下的加權DV-Hop改進算法。并驗證可以進一步提高定位精度。本文改進算法：

假如共有n個錨節點，求未知節點i到所有錨節點的估算距離時，錨節點j的加權系數Mji為：

(10)

錨節點j加權處理后的平均每一跳距離為：

MDji=Mji×dHopj

(11)

此處的dHopj由式(9)計算。未知節點i的校正值為：

(12)

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

dif=MJi×hif

(13)

3 實驗仿真

將仿真環境建立在100 m×100 m的正方形區域，將100個節點隨機部署在網絡，錨節點覆蓋率取9%～32%，通信半徑取22～45 m。

3.1 不同通信半徑下多種算法對比

錨節點覆蓋率取9%，仿真不同通信半徑下多種改進的DV-Hop定位算法和本文改進的DV-Hop算法。

首先，求加權DV-Hop算法下的最佳指數值。在不同的通信半徑下，將α取不同的值，仿真改進的算法。由于節點分布的隨機性，將程序循環100次取平均值。

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

圖1 不同通信半徑下求最佳指數值

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

圖2 不同通信半徑下4種算法對比

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

3.2 不同錨節點覆蓋率下多種算法對比

通信半徑取34 m，仿真不同錨節點覆蓋率下多種改進的DV-Hop定位算法和本文改進的DV-Hop算法。

在不同的錨節點覆蓋率下，將α取不同的值，求加權DV-Hop算法下的最佳指數值。將程序循環100次取平均值。如圖2所示，在不同的錨節點覆蓋率下，分別對應有最佳的指數，使定位精度最高。最佳指數值分別為1.95、1.94、1.94、1.93、1.94、1.93、1.93、…、1.92。

圖2 不同錨節點覆蓋率下求最佳指數值

將本文算法與文獻[15]最佳指數值DV-Hop算法、DV-Hop算法對比仿真，如圖3所示。

圖3 不同錨節點覆蓋率下3種算法對比

在不同的錨節點覆蓋率下，本文改進的最佳指數加權DV-Hop算法比其它算法占優勢。錨節點覆蓋率28%時，本文算法定位精度達到最高，為0.241%。錨節點覆蓋率14%時，本文改進的算法比DV-Hop算法、文獻[15]最佳指數DV-Hop算法分別提高定位精度2.8%、1.2%。

3.3 不同錨節點覆蓋率和不同通信半徑對比

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

圖4

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

4 結 語

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

[1] 陳瑜,張鐵民,孫道宗等.基于無線傳感器網絡的設施農業車輛定位系統設計與試驗[J].農業工程學報,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] 許毅.無線傳感器網絡原理及方法[M].北京:清華大學出版社,2012:53. XU Yi.Principles and Methods of Wireless Sensor Networks[M].Beijing:Tsinghua University press, 2012:53.

[3] 李建奇,孔玲爽,王輔文等.基于無線傳感器網絡的葡萄栽培環境監測系統[J].排灌機械工程學報,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] 周明偉.無線傳感器網絡的安全定位研究[D].無錫：江南大學,2014. ZHOU Ming-wei. Research on Security Location of Wireless Sensor Networks[D].WuXi：Jiangnan University,2014.

[5] 朱敏,劉昊霖,張志宏等.一種基于DV-Hop改進的無線傳感器網絡定位算法[J].四川大學學報:工程科學版,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] 高翔.無線傳感器網絡低功耗路由與節點目標跟蹤定位研究[D].西安：西安電子科技大學,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] 陳敏，王擘，李軍華.無線傳感器網絡原理與實踐[M].北京：化學工業出版社，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] 倪海燕,應祥岳,簡家文.無線傳感器網絡中基于DV-Hop的一種改進算法[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] 馮江,朱強,吳春春.改進的DV-Hop定位算法研究[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] 魏全瑞,劉俊,韓九強.改進的無線傳感器網絡無偏距離估計與節點定位算法[J].西安交通大學學報,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的無線傳感器網絡定位算法研究[D].太原：太原理工大學,2011. JIANF Fu-zhen. Research on Location Algorithm Based on DV-Hop in WSN[D]. Taiyuan ：Taiyuan University of Technology,2011.

[15] 馬淑麗,趙建平.無線傳感器網絡中DV-Hop定位算法的改進[J].通信技術,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

國家自然科學基金(No.11302118)；山東省自然科學基金(No.ZR2014FM011)；山東省高等學校科技計劃項目(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—)，女，碩士研究生，主要研究方向為無線傳感器網絡、無線通信技術；

趙建平(1964—)，男，教授，主要研究方向為無線通信技術。