無線傳感器網絡中DV-Hop定位算法的改進*

馬淑麗，趙建平

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

?

無線傳感器網絡中DV-Hop定位算法的改進*

馬淑麗，趙建平

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

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

摘要：無線傳感器網絡中基于無需測距的節(jié)點定位算法定位精度不高，一般應用在粗精度定位中。為了提高基于無需測距的DV-Hop算法定位精度，利用最小均方差準則改進算法，通過修改指數值精化平均每一跳距離，提出不同通信半徑、不同錨節(jié)點覆蓋率下的最佳指數值概念，并應用在一種錨節(jié)點均勻分布環(huán)境中，進一步提高定位精度。MTLAB仿真結果表明，在最佳指數值下，改進的算法在不同錨節(jié)點覆蓋率、不同通信半徑下能提高定位精度，同時不會增加節(jié)點能量消耗與硬件成本。

關鍵詞：無線傳感器網絡;節(jié)點定位;DV-Hop;最小均方差；節(jié)點分布

0引言

無線傳感器網絡(Wireless Sensor Network，WSN)由大量傳感器節(jié)點組成，可執(zhí)行目標識別、環(huán)境監(jiān)測、信息采集、定位跟蹤等任務。應用范圍廣泛，可應用在需要測量各種物理量(如溫度、濕度、輻射、酸度、振動等)的軍事、礦山井下定位、農業(yè)、環(huán)境監(jiān)測等領域。無線傳感器網絡的關鍵技術有節(jié)點定位、路由協(xié)議、安全保密[1]等。節(jié)點定位的算法實現主要有兩類[2]：一類是高成本、高定位精度的基于測距的算法；另一類是使用低成本、低定位精度的無需測距的定位算法。無需測距算法廣泛應用在粗精度定位的應用中[3]。

節(jié)點定位的研究主要考慮定位精度、網絡成本、節(jié)點能量消耗、計算量等。定位精度在一般粗精度定位應用中達到0.4以下即可滿足應用[3]。網絡成本主要考慮物理區(qū)域中節(jié)點總數、錨節(jié)點覆蓋率。錨節(jié)點因裝有導航設備成本一般比普通節(jié)點高兩個數量級[4]，所以應用中錨節(jié)點所占比例一般控制在15%左右。節(jié)點由單獨電源供電，能量消耗受泛洪次數、通信半徑、傳輸數據量等影響。節(jié)點電量耗盡后死亡，整個網絡生命周期下降。另外，網絡連通度過大也會增加網絡成本或節(jié)點能耗。

現有的文獻一般只考慮提高定位精度、降低計算量等方面，其他方面沒有充分考慮。如文獻[5]利用節(jié)點間的覆蓋率改進算法，提高了定位精度，但是通信半徑和網絡中節(jié)點數取值過大，使網絡連通度達到308，定位精度在0.4以上，不能滿足一般的實際應用。文獻[6]設定的仿真環(huán)境中節(jié)點密度較大，增加了網絡成本。文獻[7]節(jié)點通信半徑取值過高，網絡連通度達到201，會影響網絡成本與節(jié)點能量消耗。文獻[8]中設定錨節(jié)點覆蓋率從10%到90%，成本過高，不符合實際應用。文獻[9]提出的 DV-Hop(A)算法用最小均方誤差準則來計算平均每跳距離，提高了定位精度，但是其網絡連通度最高達113.1，錨節(jié)點覆蓋率從30%到90%，很不合理。本文充分考慮并確保節(jié)點定位精度0.4以下、錨節(jié)點覆蓋率16%以內、節(jié)點通信半徑43 m以下、網絡連通度控制在58以下,在不增加硬件設備和節(jié)點能量消耗下，改進算法，提高了定位精度，并應用在一種均勻的錨節(jié)點分布環(huán)境，使定位精度進一步提高。

1典型DV-Hop定位算法概述

1.1DV-Hop算法

DV-Hop定位算法由美國羅格斯大學(Rutgers University)Dragos Niculescu等人提出。DV-Hop算法利用多跳錨節(jié)點信息定位。當未知節(jié)點獲得與至少3個錨節(jié)點的距離時，可用三邊測量法、極大似然法等求出節(jié)點坐標。

假設前提：在無線傳感器網絡區(qū)域內，有少數自帶導航裝置或自身位置信息已知的錨節(jié)點(有的文獻稱為信標節(jié)點)，有大量未知節(jié)點隨機分布。每個節(jié)點都有自己的編號和相同的通信半徑，可以與其通信半徑內的其他節(jié)點實現雙通信。

定位過程：首先錨節(jié)點以泛洪的方式向網絡廣播自身位置信息和初始跳數值0，節(jié)點接收到信息后將跳數值加1并轉播出去。轉播過程中，節(jié)點只保留與其他節(jié)點間的最小跳數值。根據錨節(jié)點間的跳數與實際距離可得到每個錨節(jié)點的平均每跳距離。利用跳數乘以錨節(jié)點的平均每跳距離得到未知節(jié)點與錨節(jié)點的估算距離，其過程有兩種方法：一般方法是，未知節(jié)點只接收離自己最近的錨節(jié)點的平均每跳距離并作為計算與所有錨節(jié)點估算距離時的平均每跳距離。另一種方法是，文獻[9]提出的計算未知節(jié)點與錨節(jié)點的距離時采用相應的錨節(jié)點的平均每跳距離。經試驗發(fā)現后一種方法對提升定位精度沒有多大意義，本文采用前一種方法。

得到未知節(jié)點與錨節(jié)點的估算距離后，用極大似然法計算節(jié)點坐標過程：

(1)

AX=b

(2)

(3)

(4)

(5)

式中，di是未知節(jié)點與錨節(jié)點i間的估算距離，x，y是未知節(jié)點真實坐標值，xi，yi是錨節(jié)點i坐標值，n是錨節(jié)點個數。

1.2相關概念

節(jié)點定位算法中，絕對誤差指未知節(jié)點i的定位坐標(xi,yi)與實際坐標(x0i,y0i)的距離，一般作為節(jié)點i的定位誤差，計算如式(6)：

(6)

定位精度指網絡中全部節(jié)點(N個)的平均定位誤差與節(jié)點通信半徑R的比率，值越小定位精度越高，計算如式(7)：

(7)

二維網絡連通度C由網絡區(qū)域邊長L、網絡中節(jié)點總數N，節(jié)點通信半徑R決定，計算如式(8):

(8)

錨節(jié)點覆蓋率指網絡中錨節(jié)點個數占全部節(jié)點的比率。

2DV-Hop定位算法的改進與應用環(huán)境

2.1DV-Hop算法的改進

DV-Hop算法根據無偏估計準則計算平均每跳距離，需滿足下式：

(9)

從而得出：

(10)

式中，dHopi是錨節(jié)點i到其他錨節(jié)點的平均每一跳距離。dij是錨節(jié)點i、j間的距離。hij是錨節(jié)點i、j間的最小跳數。xi，yi是錨節(jié)點i坐標值，xj，yj是錨節(jié)點j坐標值。

如圖1所示，網絡中分布著 A、B、C三個錨節(jié)點，其他為未知節(jié)點。

圖1　網絡結構

則由式(10)得：dHopA=(d1+d2)/(2+6)，從圖1看出，計算的錨節(jié)點A的平均每跳距離要小于實際平均每跳距離，計算誤差較大。

文獻[9]提出DV-Hop(A)算法，基于最小均方誤差準則計算平均每跳距離，滿足下式：

(11)

式中，m為錨節(jié)點個數，對函數f求關于的dHopi偏導并取零，得到最小均方誤差下的平均每跳距離公式：

(12)

由式(12)得：dHopA=(2d1+6d2)/(22+62)，文獻[9]在式(12)中分母hij的指數取為2，經仿真其提出的改進算法能在較小的通信半徑范圍下提高節(jié)點定位精度，缺點是當通信半徑增大時提高的定位精度下降。

本文改進式(12)中分母hij的指數，精化錨節(jié)點i的平均每一跳距離dHopi，如式(13)。將指數值α取為1.9到2.0之間的數，提出在不同錨節(jié)點覆蓋率和不同通信半徑下各自對應最佳指數值。經仿真發(fā)現指數值α取1.9～2.0的最佳指數值時，定位精度比文獻[9]提出的DV-Hop(A)算法高。通信半徑增大時，本文算法仍能明顯的提升定位精度。

(13)

2.2應用環(huán)境

許多文獻，如文獻[2]采用節(jié)點隨機均勻分布環(huán)境。文獻[10-13]分別提出了4種錨節(jié)點均勻分布環(huán)境，提高了DV-Hop算法定位精度，其中文獻[13]分布環(huán)境提高的定位精度最高。本文采用文獻[13]提出的環(huán)境：將正方形區(qū)域劃分為16個大小相同的小正方形，每個小正方形幾何中心放置1個錨節(jié)點，其他未知節(jié)點隨機分布，如圖2所示。文獻[2]隨機均勻分布的仿真環(huán)境如圖3所示。

圖2　文獻[13]節(jié)點分布環(huán)境

圖3　文獻[2]節(jié)點分布環(huán)境

3仿真結果分析

3.1求不同通信半徑的最佳指數值

在邊長100 m的正方形區(qū)域，按文獻[2]節(jié)點分布環(huán)境布置100個節(jié)點，其中16個錨節(jié)點，通信半徑取28、31、34、37、40、43 m，α取1.90、1.91、1.92、1.93、1.94、1.95、1.96、1.97、1.98、1.99、2.00。將本文算法與DV-Hop算法對比。由于節(jié)點分布隨機性，仿真100次取平均值，如圖4所示。

圖4兩種算法對比

從圖4得出，錨節(jié)點覆蓋率16%時，本文算法在不同的通信半徑下對應不同的最佳指數值。通信半徑為28、31、34、37、40、43 m時最佳指數值分別為1.97、1.96、1.95、1.94、1.93、1.92。在上述6個通信半徑下取最佳指數值時本文算法比DV-Hop(A)算法定位精度分別提高1.27%、1.27%、1.33%、1.88%、1.96%、1.87%，比DV-Hop算法分別提高1.92%、1.86%、1.93%、2.5%、2.54%、2.42%。隨著通信半徑增大，本文算法比DV-Hop(A)算法更能明顯的提升定位精度。

3.2求不同錨節(jié)點覆蓋率的最佳指數值

將錨節(jié)點覆蓋率取8%、10%、12%、14%、15%、16%，通信半徑取43 m。仿真100次，如圖5所示。

圖5　兩種算法對比

從圖5得出，通信半徑43 m時，本文算法在不同的錨節(jié)點覆蓋率下對應不同的最佳指數值。錨節(jié)點覆蓋率為8%、10%、12%、14%、15%、16%時最佳指數值分別為1.95、1.93、1.93、1.93、1.92、1.92。在上述6個錨節(jié)點覆蓋率下取最佳指數值時,本文算法比DV-Hop(A)算法定位精度分別提高0.5%、0.92%、1.13%、1.38%、1.79%、1.71%，比DV-Hop算法分別提高0.99%、1.39%、1.59%、1.96%、2.39%、2.28%。

3.3本文算法在文獻[13]環(huán)境中的應用

在區(qū)域內按照文獻[13]提出的節(jié)點分布環(huán)境，放置16個錨節(jié)點和84個未知節(jié)點。通信半徑取28、30、32、34、36、38、40、42 m，α值取1.90、1.92、1.94、1.96、1.98。分別在文獻[2、13]隨機分布環(huán)境下仿真本文算法。運行100次，如圖6所示。

圖6　本文算法在兩種環(huán)境下對比

圖6中，8個通信半徑分別取其對應的最佳指數值時，本文算法在文獻[13]環(huán)境下比在文獻[2]隨機分布環(huán)境下定位精度分別提高4.93%、2.95%、2.19%、3.24%、1.64%、2.55%、2.99%、2.78%。說明本文算法在文獻[13]環(huán)境下應用,更能提高定位精度，缺點是節(jié)點的布置增加了人力負擔。

3.4三種算法分別在文獻[2、13]環(huán)境下的對比

錨節(jié)點覆蓋率取16%，通信半徑取26、28、30、32、34、36、38、40、42、43 m。本文算法取在兩種環(huán)境中相應通信半徑下的最佳指數值，與DV-Hop算法、DV-Hop(A)算法分別在文獻[2、13]隨機分布環(huán)境下仿真。運行100次，如圖7所示。

圖7兩種環(huán)境下DV-Hop、DV-Hop(A)、本文算法對比

由圖7得，本文算法在相同的環(huán)境下比DV-Hop算法、DV-Hop(A)算法定位精度高。通信半徑為26、34 m時，本文算法在文獻[13]環(huán)境定位精度比DV-Hop算法在文獻[2]隨機分布環(huán)境下分別提高6.57%、5.96%，比DV-Hop(A)定位法分別提高5.97%、5.38%。

4結語

本文利用最小均方差準則改進文獻[9]提出的DV-Hop(A)算法，修改指數值，提出最佳指數值概念。在不同的通信半徑及錨節(jié)點覆蓋率下分別取最佳的指數值時，本文算法可以提高節(jié)點定位精度2%左右，又結合文獻[13]提出的錨節(jié)點均勻分布環(huán)境，進一步提高定位精度6%左右。隨著通信半徑增大，本文算法比文獻[9]DV-Hop(A)算法更能提升節(jié)點定位精度。錨節(jié)點覆蓋率為16%時，提出的節(jié)點定位方法比一般DV-Hop定位方法提高定位精度6%左右，比DV-Hop(A)方法提高5%左右。下一步將進一步改進算法提高定位精度。

參考文獻：

[1](德)達爾吉,(美)玻爾拉伯爾.無線傳感器網絡基礎理與實踐[M].孫利民等譯.清華大學出版社，2014.

(Germany) Dargie W,(America) Poellabaure C. The Wireless Sensor Network Basic Theory and Practice [M]. SUN M L Translation. Tsinghua University Press, 2014.

[2]林金朝,李小玲,劉海波.無線傳感器網絡DV-Hop算法改進與性能[J].重慶大學學報,2010,33(02):127-132.

LIN Jin-chao, LI Xiao-ling, LIU Hai-bo. Improvement and Performances of DV-Hop Localization Algorithm in Wireless Sensor Networks[J].Journal of Chongqing University,2010,33(02):127-132.

[3]周正.無線傳感器網絡的節(jié)點自定位技術[J].中興通信技術，2005,11(04):51-56.

ZHOU Zheng. Self-Localization Technologies for Wireless Sensor Network Nodes[J].ZTE Communications, 2005, 11 (04): 51-56.

[4]姚向華,楊新宇，易勁剛等.無線傳感器網絡原理與應用[M].北京：高等教育出版社，2012.

YAO Xiang-hua, YANG Xin-yu, YI Jin-gang, et al. Wireless Sensor Network Principle and Application [M]. Beijing: Higher Education Press, 2012.

[5]譚志,張卉.基于節(jié)點間覆蓋關系的改進DV-Hop算法[J]. 北京郵電大學學報, 2014, 37(01):35-38.

TAN Zhi, ZHANG Hui. Improved DV-Hop Localization Algorithm based on Coverage of Nodes[J]. Journal of Beijing University of Posts and Telecommunications,2014,37 (01):35-38.

[6]吳玉成,李江雯.基于最優(yōu)節(jié)點通信半徑的改進DV-Hop定位算法[J]. 華南理工大學學報:自然科學版,2012,40(06):37-42.

WU Yu-cheng, LI Jiang-wen.Improved DV-Hop Localization Algorithm based on Optimal Communication Radius of Nodes [J].Journal of South China University of Technology (Natural Science Edition),2012,40 (06):37-42.

[7]申鉉京,李成岳,王碩.基于最優(yōu)錨節(jié)點的無線傳感器網絡節(jié)點定位算法[J].吉林大學學報:工學版,2011,41 (S1):208-214.

SHEN Xuan-jing, LI Cheng-yue, WANG Shuo. Localization Algorithm based on Optimal Nodes for Wireless Sensor Networks[J]. Journal of Jilin University (Engineering and Technology Edition),2011,41 (S1):208-214.

[8]鄭吉平,張永平,趙國安. 基于節(jié)點間連通性差異的DV-Hop定位算法[J].北京郵電大學學報,2012,35 (06):44-49.

ZHENG Ji-ping, ZHANG Yong-ping, ZHAO Guo-an. A Novel DV-Hop Localization Algorithm based on the Connectivity Differences of Sensor Nodes[J]. Journal of Beijing University of Posts and Telecommunications,2012, 35 (06 ):44-49.

[9]嵇瑋瑋,劉中.DV-Hop定位算法在隨機傳感器網絡中的應用研究[J].電子與信息學報，2008，30(04):970-974.

JI Wei-wei,LIU Zhong.Study on the Application of DV-Hop Localization Algorithms to Random Sensor Networks[J]. Journal of Electronics & Information Technology, 2008，30(4):970-974.

[10]宮娜娜,武海艷.傳感器網絡節(jié)點分布均勻性與定位性能的關系[J].電子測量技術，2014，37(12):80-85.

GONG Na-na,WU Hai-yang. The Relationship Between the Sensor Network Node Distribution Uniformity and Positioning Performance[J]. Electronic Measurement Technology,2014,37(12):80-85.

[11]黃炎炎,陳向東,倪進權等.改進的DV-HOP無線傳感器網絡定位算法[J].通信技術,2014, 47(07): 765-769.

HUANG Yan-yan,CHEN Xiang-dong,NI Jin-quan,et al. An Improved DV-Hop Localization Algorithm for Wireless Sensor Networks[J]. Communications Technology, 2014, 47(7):765-769.

[12]ZHENG You-si, WAN Lei, SUN Zhi,et al.A Long Range DV-Hop Localization Algorithm with Placement Strategy in Wireless Sensor Networks[C] // Wireless Communications, Networking and Mobile Computing,2008. WiCOM'08.4thInternational Conference on.[s.l.]: IEEE, 2008: 1-5.

[13]馬淑麗,趙建平,張炳婷.WSN中節(jié)點定位方法的改進[J].通信技術,2015,48(04):453-457.

MA Shu-li,ZHAO Jian-ping,ZHANG Bing-ting. Improvement of Node Locating Algorithm in WSN[J].Communications Technology, 2015, 48(04):453-457.

馬淑麗(1989—)，女，碩士研究生，主要研究方向為無線傳感器網絡、無線通信技術；

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

Improvement of DV-HOP Algorithm in Wireless Sensor Networks

MA Shu-li，ZHAO Jian-ping

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

Abstract：The range-free node localization algorithm, for its not so high positioning accuracy in the wireless sensor network, and is usually applied in coarse-precision positioning. In order to improve the precision of range-free DV-Hop positioning algorithm, the least mean square error criterion method is used to modify the index for refining the value of average hop distance. Thus the concept of optimal index under different communication radius and different anchor nodes number is proposed, and by combining with a uniform distribution of anchor nodes, the positioning accuracy is further improved. Simulation with MTLAB indicates that, with the optimal value of index, the algorithm could improve the location accuracy in different anchor nodes coverage rates and in the different communication radius, without any increase of node energy consumption and hardware cost.

Key words：wireless sensor network; node location; DV-Hop; least mean square error criterion; nodes distribution

作者簡介：

中圖分類號：TP393

文獻標志碼：A

文章編號：1002-0802(2015)07-0840-05

基金項目：國家自然科學基金資助項目(No.11302118)；山東省高等學?？萍加媱濏椖抠Y助(No.J12LN08)

收稿日期：修回日期：2015-05-10Received date:2015-02-09；Revised date：2015-05-10

doi:10.3969/j.issn.1002-0802.2015.07.018