無線傳感器網絡中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)

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

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

0引言

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

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

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

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

1.1DV-Hop算法

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

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

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

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

(1)

AX=b

(2)

(3)

(4)

(5)

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

1.2相關概念

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

(6)

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

(7)

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

(8)

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

2DV-Hop定位算法的改進與應用環境

2.1DV-Hop算法的改進

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

(9)

從而得出：

(10)

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

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

圖1　網絡結構

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

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

(11)

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

(12)

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

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

(13)

2.2應用環境

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

圖2　文獻[13]節點分布環境

圖3　文獻[2]節點分布環境

3仿真結果分析

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

在邊長100 m的正方形區域，按文獻[2]節點分布環境布置100個節點，其中16個錨節點，通信半徑取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算法對比。由于節點分布隨機性，仿真100次取平均值，如圖4所示。

圖4兩種算法對比

從圖4得出，錨節點覆蓋率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求不同錨節點覆蓋率的最佳指數值

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

圖5　兩種算法對比

從圖5得出，通信半徑43 m時，本文算法在不同的錨節點覆蓋率下對應不同的最佳指數值。錨節點覆蓋率為8%、10%、12%、14%、15%、16%時最佳指數值分別為1.95、1.93、1.93、1.93、1.92、1.92。在上述6個錨節點覆蓋率下取最佳指數值時,本文算法比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]環境中的應用

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

圖6　本文算法在兩種環境下對比

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

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

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

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

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

4結語

本文利用最小均方差準則改進文獻[9]提出的DV-Hop(A)算法，修改指數值，提出最佳指數值概念。在不同的通信半徑及錨節點覆蓋率下分別取最佳的指數值時，本文算法可以提高節點定位精度2%左右，又結合文獻[13]提出的錨節點均勻分布環境，進一步提高定位精度6%左右。隨著通信半徑增大，本文算法比文獻[9]DV-Hop(A)算法更能提升節點定位精度。錨節點覆蓋率為16%時，提出的節點定位方法比一般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]周正.無線傳感器網絡的節點自定位技術[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]譚志,張卉.基于節點間覆蓋關系的改進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]吳玉成,李江雯.基于最優節點通信半徑的改進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]申鉉京,李成岳,王碩.基于最優錨節點的無線傳感器網絡節點定位算法[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]鄭吉平,張永平,趙國安. 基于節點間連通性差異的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]宮娜娜,武海艷.傳感器網絡節點分布均勻性與定位性能的關系[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中節點定位方法的改進[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)；山東省高等學校科技計劃項目資助(No.J12LN08)

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

doi:10.3969/j.issn.1002-0802.2015.07.018