鄒佳順　張永勝

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

?

無線傳感器網(wǎng)絡(luò)中關(guān)于DV-Hop定位算法的改進

鄒佳順張永勝

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

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

無線傳感器網(wǎng)絡(luò)DV-Hop算法跳距計時器

0　引　言

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

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

1　相關(guān)工作

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

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

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

2　DV-Hop定位算法

2.1DV-Hop定位算法步驟

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

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

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

(1)

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

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

di=Di×h(i,k)

(2)

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

2.2三邊測量法

圖1　三邊測量法示意圖

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

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

(3)

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

3　DV-Hop算法的改進

3.1DV-Hop定位算法的缺陷

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

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

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

3.2DV-Hop定位算法的改進

本文設(shè)定一種計時數(shù)據(jù)包TimePacket用以測試路徑的傳送時間。數(shù)據(jù)包不含實際數(shù)據(jù)信息。在建立網(wǎng)絡(luò)拓撲結(jié)構(gòu)時在未知節(jié)點與未知節(jié)點以及未知節(jié)點與錨節(jié)點之間傳送。

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

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

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

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

(4)

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

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

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

(5)

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

(6)

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

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

(7)

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

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

4　仿真實驗與分析

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

節(jié)點的定位誤差計算公式如下：

(8)

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

(9)

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

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

圖3　節(jié)點數(shù)與平均定位誤差關(guān)系

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

圖4為錨節(jié)點比例與平均定位誤差之間的關(guān)系。在實驗區(qū)域固定節(jié)點通信半徑為15m，節(jié)點數(shù)目為100，逐漸遞增錨節(jié)點的比例。

圖4　錨節(jié)點比例與定位誤差的關(guān)系

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

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

圖5　節(jié)點通訊半徑與定位誤差的關(guān)系

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

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

圖6　節(jié)點平均剩余能量與時間的關(guān)系

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

5　結(jié)　語

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

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

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

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

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

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

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

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

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

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

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

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

[12] 石為人,賈傳江,梁煥煥.一種改進的無線傳感器網(wǎng)絡(luò)DV-Hop定位算法[J].傳感技術(shù)學報,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)。鄒佳順，碩士生，主研領(lǐng)域：網(wǎng)絡(luò)安全，計算機網(wǎng)絡(luò)及網(wǎng)絡(luò)模型。張永勝，教授。

TP393.01

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