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

鄒佳順　張永勝

(山東師范大學信息科學與工程學院　山東 濟南 250014) (山東省分布式計算機軟件新技術重點實驗室　山東 濟南 250014)

?

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

鄒佳順張永勝

(山東師范大學信息科學與工程學院山東 濟南 250014) (山東省分布式計算機軟件新技術重點實驗室山東 濟南 250014)

針對無線傳感器網絡非基于測距的DV-Hop定位算法中，錨節點與未知節點間平均跳距估計的不足，提出一種改進的DV-Hop算法。通過計時器來計算全網平均每跳處理時間與局部每跳處理時間的比值，并利用該比值通過加權平均的方式修正平均跳距。根據仿真實驗結果可知，改進算法減小了定位誤差，具有更高的定位精度。

無線傳感器網絡DV-Hop算法跳距計時器

0　引　言

無線傳感器網絡WSN(WirelessSensorNetwork)主要是用來監測部署區域的各種環境特性，傳感器節點以自組織方式構成的無線網絡方式進行通信[1]。但不知道相應位置信息的傳感數據往往是沒有任何意義的，因此對節點位置信息的定位操作顯得格外重要[2]。而傳統的定位方式如全球定位系統(GPS)、人工測量和標定等方法由于成本過高等原因而無法應用于WSN中[3]。

目前的WSN定位算法的研究基本是通過測量節點之間的距離信息或信息交換實現定位。根據定位方式的不同可以分為基于測距的定位算法和非基于測距的定位算法兩類。與前者相比，后者不需要額外的硬件支持成本較低，因此受到廣泛的關注。目前具有代表性的非基于測距定位算法主要有質心算法、凸規劃算法、DV-Hop算法及APIT算法等[4,5]。DV-Hop算法是為了克服直接三邊定位算法的缺點而提出的，該算法通過未知節點到錨節點的平均跳距與它們之間跳數的乘積表示兩者的距離，再用三邊定位算法或最大似然估計計算出未知節點的位置信息。該算法的缺點是，對于節點分布不均勻的WSN，節點定位誤差會明顯增大。針對該問題本文提出一種改進的DV-Hop算法，可大大提高定位精度。

1　相關工作

DV-Hop算法是目前應用最廣泛的定位算法之一，關于算法的改進性研究，國內也取得了一些研究成果。如文獻[6]提出了一種對DV-Hop算法的改進方案，通過對平均跳距采用加權處理的方式進行修正，提高定位的精度。文獻[7]根據多跳的校正值和錨節點的平均每跳距離誤差對未知節點與錨節點之間的距離做出修正。文獻[8]通過將鄰居節點間距離與連通性差異聯系起來，定義了一種新的鄰居距離估計方法，計算出更精確的鄰居距離。文獻[9]考慮使用多個錨節點估算的平均跳距離并且采用加權平均跳距代替傳統算法中的平均跳距。文獻[10]通過添加信息接收及參與定位的節點條件減少算法的定位誤差。文獻[11]根據無線信號在同種介質中傳播速度的不變性對平均跳距進行改進，提高定位精度。

傳統DV-Hop算法的不足之處在于，該算法比較適合錨節點分布均勻、密集型的WSN中,因為在這種情況下求得的每跳平均距離值才能更接近實際距離值[12]。而對于分布較隨機，密度差距較大的WSN，該算法產生的定位誤差則較大。

本文在文獻[11]相關研究的基礎上提出一種DV-Hop改進算法，綜合考慮所有錨節點的平均跳距，通過加權平均的方式計算未知節點附近的跳距，具有較高的定位精度。

2　DV-Hop定位算法

2.1DV-Hop定位算法步驟

WSN中的節點分為兩類，一類是通過人工布設或安裝GPS等定位設備獲得自己物理位置信息，稱為錨節點或信標節點。另一類是自身無法定位的節點稱為未知節點。DV-Hop定位算法可分為以下幾個步驟：

1) 利用矢量路由協議，錨節點廣播位置信息數據包，未知節點獲得距離所有錨節點最小的跳數信息。

2) 每個錨節點接收到其他錨節點傳來的位置和跳數信息后，估計全網的平均跳距如下式:

(1)

其中，(xi,yi)，(xj,yj)是錨節點i和j的坐標。hi是錨節點i和j之間的跳段數。錨節點將計算出的平均跳距廣播至全網，每個未知節點以第一個接收到的跳距信息為準，這樣基本可以保證每個未知節點以離它最近的錨節點計算出的平均跳距為準。

3) 未知節點(xk,yk)根據自身與錨節點之間跳數以及平均跳距計算自身到各錨節點之間的估計距離值。具體公式如下式:

di=Di×h(i,k)

(2)

4) 使用三邊測量法確定未知節點的位置。

2.2三邊測量法

圖1　三邊測量法示意圖

三邊測量法是一種基本的定位方法，圖1為三邊測量法的示意圖。

如圖1所示，未知節點D與三個錨節點A、B、C之間的距離分別為d1、d2、d3,A、B、C三點的坐標分別為(x1,y1)、(x2,y2)、(x3,y3)。假設未知節點D的坐標為(x,y)，則可以通過下列方程組式(3)求得D點的坐標信息。

(3)

根據式(3)可以算出未知節點D的位置(x,y)，當未知節點接收到超過3個錨節點的位置信息時，會計算出多個解，取平均值作為未知節點的位置。

3　DV-Hop算法的改進

3.1DV-Hop定位算法的缺陷

圖2是DV-Hop定位算法的示意圖。其中A、B、C節點是已知位置信息的錨節點，其余節點為未知節點。且AB之間的距離為30m，BC之間的距離為20m，AC之間的距離為40m。

圖2　DV-Hop定位算法示意圖

根據DV-Hop定位算法步驟2中的式(1)，錨節點A可計算平均跳距值為(30+40)/(3+4)，錨節點B可計算平均跳距值為(30+20)/(3+2)，錨節點C可計算平均跳距值為(20+40)/(2+4)。不同錨節點計算的校正值各不相同，定位誤差就是這樣產生的。通過分析可知，對于分布較均勻的節點，DV-Hop算法計算的跳數校正值能夠在一定程度上反應整體網絡的跳距，但當節點分布較隨機時出現的誤差往往會增大。

3.2DV-Hop定位算法的改進

本文設定一種計時數據包TimePacket用以測試路徑的傳送時間。數據包不含實際數據信息。在建立網絡拓撲結構時在未知節點與未知節點以及未知節點與錨節點之間傳送。

本文的改進DV-Hop算法步驟如下：

1) 錨節點廣播位置信息數據包，并且計時器開始計時，所有未知節點獲得距離各錨節點的最小跳數信息。

2) 錨節點收到其他錨節點傳來的廣播數據包后利用式(1)計算平均跳距，并立即返回帶自身標記的TimePacket數據包。

3) 錨節點收到其他錨節點傳來的TimePacket數據包時，分別記錄時間，并停止計時。并利用下式計算全網平均每跳處理時間t，t大于平均每跳的傳送時間，因為包括傳感器節點對數據的處理時間。各錨節點將平均跳距與t進行廣播。如錨節點i需將計算出的平均跳距Di與ti廣播至全網。

(4)

4) 未知節點接收到各錨節點傳來的平均跳距D及全網平均每跳處理時間t后向鄰節點廣播含有自身標記的TimePacket數據包，計時器開始計時。

5) 鄰節點接收到數據包后在該數據包中加入自身標記并返回數據包。

6) 未知節點收到鄰節點返回的數據包時停止計時器的計時，通過下式計算局部每跳處理時間T。不含自身標記的未知節點收到數據包后丟棄。

(5)

其中，該式的分子表示每個鄰節點處理并返回數據包所需時間之和；分母表示兩倍的鄰節點總數,n為其鄰節點的個數，可通過接收到的返回數據包進行確定。T與t所表示的都是平均每跳處理時間，但前者表示的是未知節點的局部信息，一個表示的是全網信息。因此可以通過式(6)在一定程度上表示未知節點附近的跳距與全網平均跳距之間的比例。

(6)

因此可以將W的值作為計算局部未知節點跳距的權值。其中Tj表示未知節點j的局部每跳處理時間。當T值明顯大于t值時，說明該節點附近平均每跳處理時間較長，在一定程度上表示該節點附近的跳距比全網平均跳距較大，反之則較小。

7) 根據每個錨節點計算的平均跳距和式(6)中提供的權值可通過下式計算未知節點的平均跳距為：

(7)

式中m表示所有錨節點的數目，未知節點通過對所有錨節點計算出的校正值進行加權平均，得出每個未知節點的跳距，并進一步求得未知節點到各錨節點之間的距離。

8) 通過三邊測量法確定未知節點的位置。

4　仿真實驗與分析

為驗證改進算法的性能，本文采用Matlab進行仿真。在100m×100m的網絡環境中進行實驗，分別控制傳感器節點個數從20到100進行變化，錨節點的比例按5%、10%、…、40%進行變化，節點通信半徑變化范圍為15m到40m，從平均定位誤差及節點平均剩余能量兩方面與傳統DV-Hop算法進行比較。其中節點的分布均符合二維隨機分布，每種情況在仿真實驗中運行100次，仿真結果取其平均值。

節點的定位誤差計算公式如下：

(8)

其中(xm,ym)是節點的實際位置，(xn,yn)為節點的估計位置，R為節點的通信半徑。在仿真實驗中，是以平均定位誤差作為比較的參數。平均定位誤差為網絡中所有未知節點的定位誤差之和與未知節點個數p的比值?？赏ㄟ^下式計算得出。

(9)

由于本文算法與文獻[11]使用的原理相同，都是利用無線信號在同種介質中傳播速度的不變性，以及發送數據包的形式進行計時，因此具有較強的可比性。本文在仿真實驗結果中也加入了與文獻[11]中算法性能的對比。

圖3為節點數目與平均定位誤差之間的關系，在實驗區域固定節點通信半徑為15m，錨節點比例固定為20%，節點數從20遞增變化到100。

圖3　節點數與平均定位誤差關系

由圖3中改進算法與標準算法的對比可以明顯地看出，在節點數目相同的情況下，本文的改進算法在平均定位誤差方面明顯優于標準算法，尤其是在節點稀疏的情況下，優勢更加明顯。在節點數目為30時，與標準算法相比，改進算法的平均定位誤差降低了約16%，就算是在節點比較密集時本文算法也有較高的定位精度。如節點數目為100時，定位誤差降低了約13%。與文獻[11]算法相比也具有一定的優勢。

圖4為錨節點比例與平均定位誤差之間的關系。在實驗區域固定節點通信半徑為15m，節點數目為100，逐漸遞增錨節點的比例。

圖4　錨節點比例與定位誤差的關系

由圖4中的對比可以看出，隨著錨節點的增加,三種算法的平均定位誤差都在呈遞減趨勢。本文中的改進算法比標準DV-Hop算法具有明顯的優勢。且本文的改進算法明顯優于標準算法，如在錨節點比例較少的5%時，改進算法的平均定位誤差降低了約14%，在錨節點比例較多的40%時也降低了大約10%。而與文獻[11]中的改進算法相比，定位誤差也具有大幅度降低。

圖5為節點通信半徑與平均定位誤差之間的關系，在實驗區域固定錨節點比例固定為20%，節點數目為100，節點通信半徑從15m遞增至40m。

圖5　節點通訊半徑與定位誤差的關系

根據圖5中三種算法的比較可知，本文改進算法明顯優于標準DV-Hop算法。在通信半徑為15m時，改進算法的平均定位誤差降低了約8%。在通信半徑為40m時降低了約7%。定位精度明顯高于文獻[11]中的定位算法。

此外本文還針對節點的剩余能量方面與標準算法進行了比較，對比結果如圖6所示。

圖6　節點平均剩余能量與時間的關系

圖6是在實驗區域中固定節點通信半徑為15m，錨節點比例固定為20%，節點數為100的環境下進行的，通過1.4Mbps的802.11MAC進行通信。通過對三種算法進行比較可知，本文的改進算法在節點能耗方面與標準DV-Hop算法相比具有一定的不足。主要是由于在定位操作中本文的改進算法需要消耗較大的能量。而與文獻[11]算法相比，能量消耗方面并未有較大的差距，但本文算法的定位精度卻遠遠高于文獻[11]中的定位算法。因此在實際使用時，可以根據實際情況對本文算法和標準DV-Hop算法進行選擇。對定位精度要求較高時可以采用本文算法，對能耗要求較高時可采用標準算法。

5　結　語

本文對無線傳感器網絡中的標準DV-Hop定位算法進行了簡單的介紹。針對DV-Hop算法定位時的缺陷提出了一種改進算法。在估計平均跳距時并不僅僅以最近的錨節點計算出的校正值為準，而是根據局部與全網每跳處理時間的比值對所有錨節點計算出的平均跳距進行加權平均。仿真實驗表明，改進算法具有較高的定位精度。但本文的改進算法也存在不足，由于傳輸數據量的增加，在能量消耗方面比標準算法略高，因此在定位時可根據實際需要對改進算法與標準算法的選擇進行權衡。

[1] 官小云,楊培會,劉珂.移動無線傳感器網絡定位研究[J].計算機應用與軟件,2014,31(4):138-140.

[2] 鄭遠,蔡宇,趙銳.一種兼顧性能與能耗的DV-Hop改進算法[J].計算機應用與軟件,2014,31(4):269-273.

[3] 周小波,喬鋼柱,曾建潮.無線傳感器網絡中基于RSSI的加權DV-HOP定位方法[J].計算機工程與應用,2011,47(14):109-111.

[4] 趙軍,裴慶祺,徐展琦.無線傳感器網絡近似三角形內點測試定位算法[J].計算機工程,2007,33(5):109-112.

[5]NIculescuD,NathB.DVbasedpositioninginadhocnetworks[J].JournalofTelecommunicationSystems,2003,22(1-4):267-280.

[6] 劉文遠,王恩爽,陳子軍.無線傳感器網絡中DV-Hop定位算法的改進[J].小型微型計算機系統,2011,32(6):1071-1074.

[7] 張佳,吳延海,石峰,等.基于DV-HOP的無線傳感器網絡定位算法[J].計算機應用,2010,30(2):323-326.

[8] 江禹生,陳躚,李萍.可信鄰居距離估計的DV-Hop校準算法[J].計算機應用,2013,33(11):3016-3018.

[9] 王新生,趙衍靜,李海濤.基于DV-Hop定位算法的改進研究[J].計算機科學,2011,38(2):78-90.

[10] 張靜,曹敦,傅明,等.DV-Hop算法定位誤差和覆蓋率的改進[J].計算機應用,2011,31(7):1944-1947.

[11] 趙靈鍇,洪志全.基于無線傳感器網絡的DV-Hop定位算法的改進[J].計算機應用,2011,31(5):1189-1192.

[12] 石為人,賈傳江,梁煥煥.一種改進的無線傳感器網絡DV-Hop定位算法[J].傳感技術學報,2011,24(1):83-87.

IMPROVEMENTOFDV-HOPLOCALISATIONALGORITHMINWIRELESSSENSORNETWORKS

ZouJiashunZhangYongsheng

(School of Information Science and Engineering,Shandong Normal University,Jinan 250014,Shandong,China) (Shandong Provincial Key Laboratory for Novel Distributed Computer Software Technology,Jinan 250014,Shandong,China)

Inrange-freebasedDV-Hoplocalisationalgorithminwirelesssensornetworks,theestimationofaveragehopdistancebetweenanchornodesandunknownnodeshasshortcomings.Tosolvetheproblem,thepaperproposesanimprovedDV-Hopalgorithm.Itcalculatestheratiobetweentheaverageprocessingtimeperhopinwholenetworkandtheprocessingtimeperhopinlocalnetworkbythetimer.Basedontheratio,itcorrectstheaveragehopdistancebymeansofweightedaverage.Accordingtotheresultofsimulationexperiment,theimprovedalgorithmreducesthepositioningerrorandhashigherpositioningaccuracy.

WirelesssensornetworksDV-HopalgorithmHopdistanceTimer

2014-09-15。山東省自然科學基金項目(ZR2011FM0 19)。鄒佳順，碩士生，主研領域：網絡安全，計算機網絡及網絡模型。張永勝，教授。

TP393.01

ADOI:10.3969/j.issn.1000-386x.2016.03.033