基于跳數(shù)分類的改進DV-Hop節(jié)點定位算法

任克強,廖美焱

(江西理工大學信息工程學院,江西 贛州 341000)

2017-03-28修改日期2017-06-07

基于跳數(shù)分類的改進DV-Hop節(jié)點定位算法

任克強*,廖美焱

(江西理工大學信息工程學院,江西 贛州 341000)

在傳統(tǒng)DV-Hop節(jié)點定位算法中,不同的網(wǎng)絡(luò)節(jié)點密度使得節(jié)點之間不同跳數(shù)的平均每跳距離差異較大,跳數(shù)越多誤差越大。為了減小平均每跳距離差異對節(jié)點定位精度的影響,提出一種DV-Hop改進算法。改進算法首先提出跳數(shù)分類的策略對網(wǎng)絡(luò)中不同的跳數(shù)進行分類,以減小不同跳數(shù)之間平均每跳距離差異的影響,提高節(jié)點的定位精度;然后對加權(quán)最小二乘估計進行改進,采用改進的權(quán)系數(shù)取值策略來適應累積誤差的非線性變化,從而更好地控制不同跳數(shù)在最小二乘估計中的權(quán)重,以減小因跳數(shù)增加而產(chǎn)生的累積誤差,進一步提高節(jié)點的定位精度。實驗結(jié)果表明,改進算法可以有效地減小平均每跳距離差異以及高跳數(shù)對節(jié)點定位的影響,節(jié)點定位性能顯著優(yōu)于傳統(tǒng)DV-Hop節(jié)點定位算法,相較于對比文獻也有一定的提升,并且對不同的網(wǎng)絡(luò)節(jié)點密度具有更好的適應性。

無線傳感器網(wǎng)絡(luò);節(jié)點定位;DV-Hop算法;跳數(shù)分類;加權(quán)最小二乘估計

計算機和傳感器技術(shù)的迅速發(fā)展使得無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)獲得了廣泛應用和關(guān)注。WSN是由許多能量有限、低成本和低功耗的傳感器節(jié)點通過自組織多跳形成的網(wǎng)絡(luò)系統(tǒng)。每個傳感器節(jié)點都配備了傳感元件、數(shù)據(jù)處理單元、無線接收發(fā)器模塊和電源模塊,具有信息采集、數(shù)據(jù)處理和通信的能力,但是這種計算和通信能力是有限的[1]。在WSN中,對每個傳感器節(jié)點進行定位十分重要,如果傳感器采集的數(shù)據(jù)沒有空間和時間的協(xié)調(diào),那么采集的數(shù)據(jù)將沒有價值[2]。

WSN的定位技術(shù)根據(jù)測距方式可以分為基于測距(range-based)的定位和非測距(range-free)的定位兩大類[3-4]。其中,基于測距的方案需要有精確測量兩相鄰節(jié)點間的絕對距離或者方位的有關(guān)設(shè)備,導致基于測距的方案對硬件設(shè)備要求較高,但是定位的精度相對非測距要高。基于測距的定位算法主要包括:TOA、TDOA、AOA和RSSI等[5-6]。在非測距的方案中,存在兩種節(jié)點,一種是位置已知的信標節(jié)點(anchors nodes),另外一種是未知節(jié)點(unknown nodes),非測距主要是利用已知節(jié)點估計未知節(jié)點的位置。因而,非測距方案不需要額外設(shè)備,適合在大規(guī)模的傳感器網(wǎng)絡(luò)中部署,其最大缺點就是誤差較大。典型的非測距定位算法主要有:Centroid[7]、DV-Hop[8]、Amorphous[9]以及APIT[10]等。

DV-Hop算法是一種典型的基于跳數(shù)的非測距定位算法,協(xié)議簡單且方案易部署,受到了廣泛的關(guān)注與研究,但其定位性能不理想。在DV-Hop算法的基礎(chǔ)上,許多學者提出了改進算法。文獻[11]對算法的改進集中在計算每跳距離,提出對全網(wǎng)絡(luò)信標節(jié)點的平均每跳距離相加求平均,得到全網(wǎng)絡(luò)的平均每跳距離,并用2-D雙曲線(hyperbolic)代替最大相似(maximum likelihood)估計未知節(jié)點坐標,取得了一定的效果,但該算法在網(wǎng)絡(luò)密度較低時誤差較大。文獻[12]提出一種基于誤差距離加權(quán)與跳數(shù)算法選擇的遺傳優(yōu)化DV-Hop定位算法,該算法以距未知節(jié)點越近越重要為原則,對信標節(jié)點進行挑選并優(yōu)化,從而減小定位誤差。文獻[13]將跳數(shù)進行量化,并將通信半徑長度量化為多跳,最后采用自適應質(zhì)點彈簧優(yōu)化算法優(yōu)化節(jié)點坐標,提高了定位精度,但該算法需要額外測距技術(shù)獲得距離信息,增加了部署成本。文獻[14]提出基于SFLA(shuffled frog leaping algorithm)和PSO(particle swarm optimization)的定位算法,SFLA用來計算平均每跳距離,PSO用來計算未知節(jié)點坐標,取得了較高的定位精度。文獻[15]主要針對DV-Hop算法的第3步進行了改進,使其具有更小的校正因子,并通過加權(quán)最小二乘估計未知節(jié)點坐標,算法性能比DV-Hop算法有較大提升。上述算法均不同程度的改善和提升了DV-Hop算法的性能,但這些算法只是利用節(jié)點的聯(lián)通度或跳數(shù)信息進行定位,并未考慮到網(wǎng)絡(luò)節(jié)點密度的改變對節(jié)點之間不同跳數(shù)的平均每跳距離的影響。因此,本文提出一種跳數(shù)分類與改進加權(quán)最小二乘估計相結(jié)合的DV-Hop改進算法,以減小網(wǎng)絡(luò)密度變化和累積誤差對節(jié)點定位的影響,提高DV-Hop算法的定位性能。

1 DV-Hop算法及其誤差分析

1.1 DV-Hop算法

在DV-Hop算法的距離向量定位機制中,節(jié)點主要是利用節(jié)點之間的信息交換來對自身的位置進行估計,主要包括下述3個步驟:

①所有信標節(jié)點先創(chuàng)建一個初始化的信息分組表{xi,yi,hi},其中包括自身坐標{xi,yi}和初始跳數(shù)hi=1,并向鄰居節(jié)點廣播自身信息分組;由于節(jié)點發(fā)射功率的限制,只有位于節(jié)點傳播范圍內(nèi)的鄰居節(jié)點(neighbor node)才能接收到該數(shù)據(jù)包。鄰居節(jié)點接收到這些數(shù)據(jù)包后,如果該數(shù)據(jù)包是來自同一信標節(jié)點的跳數(shù)較大的信息分組,則拋棄該數(shù)據(jù)包,否則將其記錄下來,再將信息分組表內(nèi)的hi加1后轉(zhuǎn)發(fā)。

②通過步驟1中節(jié)點之間的信息分組表交換,所有網(wǎng)絡(luò)當中的未知節(jié)點都可以知曉自身到信標節(jié)點的最小跳數(shù)和信標節(jié)點的信息,如坐標和編號。相應的,信標節(jié)點之間也獲得了彼此之間的最小跳數(shù)和坐標信息。然后,信標節(jié)點可計算出自己到其他信標節(jié)點的平均每跳距離:

(1)

式中:{xi,yi}和{xj,yj}分別表示信標節(jié)點i和j的坐標,hj表示信標節(jié)點i與j之間的最小跳數(shù)。

信標節(jié)點計算出平均每跳距離HopSizei后,將各自的平均每跳距離廣播給鄰居節(jié)點。未知節(jié)點通過第2次的信息交換可獲知離自己最近信標節(jié)點的平均每跳距離。

③未知節(jié)點獲得離自己最近信標節(jié)點的平均每跳距離后,根據(jù)式(2)計算到各信標節(jié)點的距離Dis(i,j):

Dis(i,j)=hij×HopSizej

(2)

式中:hij表示未知節(jié)點i到信標節(jié)點j的最小跳數(shù),HopSizej表示離未知節(jié)點i最近信標節(jié)點的平均每跳距離。

最后利用三邊測量法或者極大似然估計法估計未知節(jié)點的坐標。

1.2 算法誤差分析

圖1中分布著兩個信標節(jié)點S和D以及若干個未知節(jié)點。

圖1 節(jié)點分布示意圖

從圖1中可以得出以下兩個結(jié)論:

①DV-Hop算法計算出的平均每跳距離HopSizei必小于等于實際的平均每跳距離。該結(jié)論是顯然的,由于兩點間的直線距離最短,采用多跳所走過的路徑必然大于等于直線間的距離。

②在兩個固定距離的信標節(jié)點之間,跳數(shù)越多,單跳距離越小。例如:節(jié)點S到節(jié)點D可以通過S→a→b→c→D,也可以通過S→d→e→D,顯然兩種多跳方式所計算的平均每跳距離不相等。

DV-Hop的主要思想是未知節(jié)點利用信標節(jié)點所計算出的平均每跳距離來估計自己到信標節(jié)點的距離,這種估計是采用折線去估計直線距離,但是這個折線距離并不等于真實的折線距離,它比真實的折線距離要小,這對估算直線距離是有利的,結(jié)論1說明了這一點。結(jié)論2主要說明了網(wǎng)絡(luò)節(jié)點密度的差異容易導致不同跳數(shù)所計算的平均跳距差異很大。因此,在網(wǎng)絡(luò)拓撲結(jié)構(gòu)分布不規(guī)則的情況下,采用式(1)或者文獻[11]全網(wǎng)絡(luò)平均算法的誤差會很大。

圖2 不同跳數(shù)的平均每跳距離

為了更深入的研究不同跳數(shù)所計算的平均每跳距離的變化規(guī)律,本文做了如下仿真實驗:在500 m×500 m的區(qū)域內(nèi)分別隨機分布100、150和250個節(jié)點,其中信標節(jié)點40個,通信半徑R=80 m,分別分類計算信標節(jié)點之間不同跳數(shù)的平均每跳距離,實驗結(jié)果如圖2所示。

從圖2中可以看出平均每跳距離隨網(wǎng)絡(luò)節(jié)點密度的3個變化規(guī)律:

①信標節(jié)點之間不同跳數(shù)計算出來的平均每跳距離差異較大。

②從橫坐標看,3種不同節(jié)點分布密度呈現(xiàn)出3種不同的變化規(guī)律,當網(wǎng)絡(luò)節(jié)點個數(shù)為250時,隨著跳數(shù)的增加,平均每跳距離呈現(xiàn)逐漸上升,最后趨于平穩(wěn);當網(wǎng)絡(luò)節(jié)點個數(shù)為150個時,隨著跳數(shù)的增加,平均每跳距離先呈現(xiàn)出上升,最后呈現(xiàn)出下降的趨勢;當網(wǎng)絡(luò)節(jié)點個數(shù)為100個時,隨著跳數(shù)的增加,平均每跳距離逐漸下降。

③從縱坐標看,當跳數(shù)固定時,隨著網(wǎng)絡(luò)節(jié)點數(shù)的減少,平均每跳距離逐漸減小。

上述3組實驗分別代表著3種節(jié)點密度,250代表節(jié)點密度較高,150代表節(jié)點密度中等,100代表節(jié)點密度較低。當網(wǎng)絡(luò)中節(jié)點密度較高時,節(jié)點分布較為均勻,隨著跳數(shù)的增加,平均每跳距離趨于平穩(wěn);當網(wǎng)絡(luò)中節(jié)點密度較低時,節(jié)點分布不規(guī)則,在相同距離的兩信標節(jié)點中間,容易出現(xiàn)較為曲折的折線,導致跳數(shù)的增加,從而平均每跳距離減小。

因此,在網(wǎng)絡(luò)節(jié)點密度較低或者網(wǎng)絡(luò)拓撲分布不規(guī)則時,采用DV-hop算法或全網(wǎng)絡(luò)平均算法是不可取的,誤差會很大。此外,文獻[16]的分析表明隨著未知節(jié)點到信標節(jié)點跳數(shù)的增加,未知節(jié)點到信標節(jié)點的估計距離誤差將會逐漸增加。

2 改進策略

2.1 跳數(shù)分類策略

根據(jù)上述誤差分析,在網(wǎng)絡(luò)拓撲結(jié)構(gòu)不規(guī)則時,不同跳數(shù)所計算出的平均每跳距離差別較大,而且這種差別會隨著網(wǎng)絡(luò)節(jié)點密度的不同而不同。因此本文提出一種跳數(shù)分類HCC(Hop Counts Classification)的改進策略,以減小不同跳數(shù)之間平均每跳距離的差異,提高節(jié)點的定位精度。

設(shè)網(wǎng)絡(luò)中有n個節(jié)點,其中有m個信標節(jié)點,信標節(jié)點之間的歐氏距離為:

(3)

式中:{xi,yi}和{xj,yj}分別表示信標節(jié)點i和j的坐標。

HCC策略共由3個階段組成:

①節(jié)點初始化。數(shù)據(jù)包先從信標節(jié)點進行廣播。每一個信標節(jié)點向鄰居節(jié)點廣播一個初始化信息Info=[(Bi,xi,yi),HopCouti],其中Bi表示信標節(jié)點編號,{xi,yi}表示信標節(jié)點Bi的坐標,HopCouti表示跳數(shù)(初始化為1)。由于節(jié)點發(fā)射功率的限制,只有位于節(jié)點傳播范圍內(nèi)的節(jié)點才能接收到該數(shù)據(jù)包,即與信標節(jié)點之間為一跳的節(jié)點都可以接收到該數(shù)據(jù)包。節(jié)點接收到數(shù)據(jù)包之后,判斷該數(shù)據(jù)包是否來自同一信標節(jié)點的跳數(shù)較高的信息分組,如果是則拋棄該數(shù)據(jù)包;否則,更新自身的數(shù)據(jù),并將更新的數(shù)據(jù)包轉(zhuǎn)發(fā)。新轉(zhuǎn)發(fā)的數(shù)據(jù)包含有信標節(jié)點信息和更新的數(shù)據(jù):

(4)

圖3 數(shù)據(jù)包處理偽代碼

②信標節(jié)點跳數(shù)分類。當所有節(jié)點獲知自身到信標節(jié)點的最小跳數(shù)之后,所有信標節(jié)點將自身的最小跳數(shù)集合seti發(fā)送到匯聚節(jié)點,匯聚節(jié)點對所有信標節(jié)點的最小跳數(shù)集合進行跳數(shù)分類。

dperhop(c)=fc(set1,set2,…,setm)

(5)

跳數(shù)分類過程如圖4所示,x1,x2,…,xm-1,xm分別表示m個信標節(jié)點的最小跳數(shù)集合,在這些集合當中,都含有該信標節(jié)點i與其余信標節(jié)點之間最小跳數(shù)。然后通過分類器函數(shù)fc可以得到一個h維的向量y,向量y中的每個值分別代表不同跳數(shù)的平均每跳距離。h的值取決于它們之間的最高跳數(shù)。

圖4 跳數(shù)分類示意圖

分類器函數(shù)fc的映射過程描述如下:

S1:輸入m個信標節(jié)點的跳數(shù)集合set1,set2,…,setm,setm內(nèi)包含了信標節(jié)點Bm與其余信標節(jié)點的最小跳數(shù)集合hopm1,hopm2,…,hopmm-1。

S2:對集合內(nèi)的所有數(shù)據(jù)進行分類處理,輸出h個最小跳數(shù)相同的集合Bhop1,Bhop2,…,Bhoph。例如,信標節(jié)點B2到B4為3跳,B1到B5也為3跳,則將信標節(jié)點之間最小跳數(shù)為3跳的組成一個集合Bhop3。

S3:計算不同跳數(shù)之間的平均每跳距離:

(6)

式中:M表示集合Bhopc里面的信標節(jié)點對數(shù),disij表示集合內(nèi)信標節(jié)點之間的距離,dperhop(c)表示跳數(shù)為c跳的平均每跳距離。

S4:計算節(jié)點到各信標節(jié)點的距離:

Disij=HopCoutij×hopCoutij

(7)

③未知節(jié)點坐標估計。為減小誤差積累對定位的影響,本文采用改進的加權(quán)最小二乘估計對未知節(jié)點的坐標進行估計。

2.2 加權(quán)最小二乘估計的改進

設(shè)網(wǎng)絡(luò)中信標節(jié)點的坐標分別為(x1,y1),(x2,y2),…,(xn,yn),待估算未知節(jié)點的坐標為(x,y),待估算未知節(jié)點到信標節(jié)點i的估計距離為di(i=1,2,…,n),則可得如下方程組:

(8)

將式(8)方程組的前(n-1)個方程分別減去第n個方程可以得到AX=b形式的矩陣,其中,A與b為n-1維觀測值,X是未知參數(shù):

(9)

(10)

(11)

min(b-AX)T(b-AX)

(12)

對X求偏導數(shù),并令其等于零,可求得X的估計值:

(13)

由文獻[16]的分析可知,隨著未知節(jié)點到信標節(jié)點跳數(shù)的增加,誤差逐漸增加(拓撲是隨機分布的,隨著跳數(shù)增加,各種不確定性因素增多),也就是說誤差向量e中的每一個誤差可信度會隨著跳數(shù)的增加而減小。為了減少這種累積誤差,可采用加權(quán)最小二乘估計代替最小二乘估計:

min[W(b-AX)]T[W(b-AX)]

(14)

式中:W表示權(quán)系數(shù),W是一個維數(shù)為n-1的對角矩陣。

對X求偏導,并另其等于零,可求得X的加權(quán)估計值:

(15)

對于權(quán)系數(shù)W,文獻[15]采用跳數(shù)的倒數(shù)作為權(quán)系數(shù)的取值:

(16)

式中:Wp,i表示未知節(jié)點p對于信標節(jié)點i的權(quán)系數(shù);hp,i表示未知節(jié)點p到信標節(jié)點i的最小跳數(shù)。

文獻[15]權(quán)系數(shù)取值的基本思路是:未知節(jié)點p到信標節(jié)點i的跳數(shù)越多,所對應的權(quán)越小。這種權(quán)系數(shù)的取值策略有效地減少了累積誤差,提高了定位精度;但累積誤差增加與跳數(shù)增加之間的關(guān)系不是線性的,該權(quán)系數(shù)取值策略沒有考慮累積誤差增加的非線性特點,其權(quán)系數(shù)取值不是根據(jù)累積誤差的非線性變化而自適應的確定,不能適應累積誤差的非線性變化。因此,為了進一步減少累積誤差,本文對權(quán)系數(shù)的取值進行了改進:

(17)

本文的權(quán)系數(shù)取值策略既考慮了跳數(shù)增加導致累積誤差非線性逐漸增加的因素,又利用了跳數(shù)分類得到的一跳平均距離均方誤差最小的特點。表1給出了節(jié)點總數(shù)為500個、信標節(jié)點占15%和通信半徑R=70 m時,信標節(jié)點之間不同跳數(shù)的均方誤差,可以看出:一跳的均方誤差最小;均方誤差隨著跳數(shù)的增加而逐漸增加,但增加的幅度不是線性的。

表1 不同跳數(shù)的均方誤差

3 實驗仿真與分析

為了測試本文改進策略的效果,采用MATLAB對DV-Hop算法、文獻[15]算法以及本文算法進行仿真實驗,并以平均相對誤差為標準對仿真結(jié)果進行分析評價:

(18)

實驗場景為100 m×100 m的矩形區(qū)域,仿真實驗分成三組,每組的實驗結(jié)果為分別仿真100次的平均值;通信半徑為R,考慮到真實的通信半徑并不是標準的圓,允許每個節(jié)點的R有0～10%的誤差波動。

圖5是網(wǎng)絡(luò)節(jié)點個數(shù)從200到500變化對定位誤差影響的實驗結(jié)果曲線,其中節(jié)點總數(shù)的10%為信標節(jié)點,通信半徑R=15 m?？梢钥闯?隨著網(wǎng)絡(luò)中節(jié)點總數(shù)的增加,DV-Hop算法、文獻[15]算法以及本文算法的相對定位誤差都逐漸下降。當節(jié)點從200個增加到500個時,DV-Hop算法的相對定位誤差為33%,文獻[15]算法的相對定位誤差為21%,文獻[15]算法比DV-Hop算法的相對定位誤差減小了12%;本文算法的相對定位誤差為20%,進一步減小了定位誤差,說明本文算法的定位精度比DV-Hop算法有了大幅的提高,比文獻[15]的定位精度也有一定的提升。圖5的實驗結(jié)果曲線表明增加網(wǎng)絡(luò)中的節(jié)點個數(shù)可以較為有效的降低定位誤差,這是因為節(jié)點總數(shù)增加,網(wǎng)絡(luò)節(jié)點密度隨之增加,在節(jié)點的通信半徑內(nèi),將會出現(xiàn)更多的鄰居節(jié)點,使得網(wǎng)絡(luò)拓撲更加規(guī)則,而網(wǎng)絡(luò)拓撲越規(guī)則,誤差的積累會越小,從而使得定位誤差減小。

圖5 網(wǎng)絡(luò)節(jié)點個數(shù)對定位誤差影響

圖6 網(wǎng)絡(luò)信標節(jié)點密度對定位誤差影響

圖6是網(wǎng)絡(luò)信標節(jié)點密度的變化對定位誤差影響的實驗結(jié)果曲線,網(wǎng)絡(luò)中總共包含有節(jié)點300個,信標節(jié)點比例從5%到35%變化,通信半徑R=15 m。當網(wǎng)絡(luò)中信標節(jié)點比例由5%增加到10%時,3種算法的相對定位誤差曲線均下降明顯;當網(wǎng)絡(luò)中信標節(jié)點比例由10%增加到30%時,3種算法的相對定位誤差曲線下降較為緩慢;當網(wǎng)絡(luò)中信標節(jié)點比例大于30%時,隨著信標節(jié)點密度增加,3種算法的相對定位誤差趨于平穩(wěn),信標節(jié)點密度不再對定位誤差產(chǎn)生較大影響。同時也可以看到,本文算法的相對定位誤差比DV-Hop算法減小了很多;除了信標節(jié)點比例在5%到7.5%的小范圍內(nèi),本文算法的相對定位誤差比文獻[15]算法略微大一點外,其他信標節(jié)點比例的相對定位誤差均比文獻[15]算法要小,說明本文算法的定位性能優(yōu)于文獻[15]算法;這是由于本文的跳數(shù)分類策略使得不同跳數(shù)的平均每跳距離更加精確,并且本文的權(quán)系數(shù)取值策略進一步減小了累積誤差。

圖7是通信半徑R從15 m到45 m變化對定位誤差影響的實驗結(jié)果曲線,其中節(jié)點總數(shù)為300個,信標節(jié)點比例為10%。當網(wǎng)絡(luò)節(jié)點密度一定時,較小的節(jié)點通信半徑所對應的相對定位誤差較大,因為節(jié)點通信半徑較小時,容易導致網(wǎng)絡(luò)的拓撲分布不均;但隨著節(jié)點通信半徑的增加,位于節(jié)點通信半徑內(nèi)的節(jié)點將增多,從而降低網(wǎng)絡(luò)拓撲的分布不均,而拓撲更加規(guī)則必然會使得定位精度提高。從圖7可以看出,當通信半徑R=15 m時,DV-Hop算法的相對定位誤差為41%,文獻[15]算法的相對定位誤差為26%,本文算法的相對定位誤差為24%,說明本文算法的定位性能優(yōu)于DV-Hop算法和文獻[15]算法。從圖7曲線可以看出,DV-Hop算法、文獻[15]算法和本文算法的相對定位誤差隨著節(jié)點通信半徑增加而逐漸下降;但是當節(jié)點通信半徑增加到30 m左右時,隨著通信半徑的增加,3種定位算法的相對定位誤差都趨于平穩(wěn),即當節(jié)點的通信半徑增加到一定值時,節(jié)點定位誤差受節(jié)點通信半徑的影響逐漸減低。這是因為當節(jié)點的通信半徑增大時,位于節(jié)點通信范圍內(nèi)的節(jié)點會增多,進而使得網(wǎng)絡(luò)拓撲更加規(guī)則;但節(jié)點的通信半徑增加到一定的值后,對節(jié)點的路徑選擇已經(jīng)沒有多大的影響,所以定位誤差曲線趨于平穩(wěn)。

圖7 節(jié)點通信半徑對定位誤差影響

5 結(jié)論

①針對傳統(tǒng)DV-Hop節(jié)點定位算法中平均每跳距離差異對節(jié)點定位精度影響的問題,提出一種跳數(shù)分類的策略,該策略將WSN中不同的跳數(shù)進行分類,并基于跳數(shù)分類來計算不同跳數(shù)之間的平均每跳距離,有效地提升了節(jié)點定位算法對不同網(wǎng)絡(luò)節(jié)點密度的適應性以及節(jié)點定位的精度。

②為了減小隨跳數(shù)增加而非線性增加的累積誤差,提出一種改進的加權(quán)最小二乘估計權(quán)系數(shù)取值策略,該策略可以更好的適應累積誤差的非線性變化,從而根據(jù)WSN中的跳數(shù)來自適應地調(diào)整不同跳數(shù)在最小二乘估計中的權(quán)重,有效地減小了因跳數(shù)增加而產(chǎn)生的累積誤差,進一步提高了節(jié)點的定位精度。

③在不同節(jié)點總數(shù)、不同信標節(jié)點密度以及不同通信半徑的算法仿真對比實驗中,本文改進算法均表現(xiàn)出比傳統(tǒng)DV-Hop節(jié)點定位算法更優(yōu)異的性能,比相關(guān)對比文獻中定位算法的性能也有一定的提升,從而表明本文的改進策略可以有效提升DV-Hop節(jié)點定位算法的性能。如何進一步地降低不同跳數(shù)的平均每跳距離差異和累積誤差對節(jié)點定位精度的影響是后續(xù)要重點研究的工作。

[1] 洪鋒,褚紅偉,金宗科,等. 無線傳感器網(wǎng)絡(luò)應用系統(tǒng)最新進展綜述[J]. 計算機研究與發(fā)展,2010,47(s2):81-87.

[2] 黃亮,王福豹,段渭軍,等. 基于距離重構(gòu)的無線傳感器網(wǎng)絡(luò)多維定標定位算法[J]. 傳感技術(shù)學報,2013,26(9):1284-1287.

[3] Halder S,Ghosal A. A Survey on Mobile Anchor Assisted Localization Techniques in Wireless Sensor Networks[J]. Wireless Networks,2016,22(7):2317-2336.

[4] 雷高祥,黃輝,方旺盛. 基于RSSI值跳數(shù)修正和跳距加權(quán)處理的DV-HOP算法[J]. 江西理工大學學報,2015,36(5):80-84.

[5] 錢志鴻,王義君. 面向物聯(lián)網(wǎng)的無線傳感器網(wǎng)絡(luò)綜述[J]. 電子與信息學報,2013,35(1):215-227.

[6] Mao G,Fidan B,Anderson B D O. Wireless Sensor Network Localization Techniques[J]. Computer Networks,2007,51(10):2529-2553.

[7] 楊友華,孫麗華,向滿天. 基于質(zhì)點彈簧模型的無線傳感器網(wǎng)絡(luò)非測距定位算法[J]. 傳感技術(shù)學報,2015,28(6):914-919.

[8] Niculescu D,Nath B. DV Based Positioning in Ad Hoc Networks[J]. Telecommunication Systems,2003,22(1-4):267-280.

[9] Zhao L Z,Wen X B,Li D. Amorphous Localization Algorithm Based on BP Artificial Neural Network[M]. Taylor and Francis,Inc,2015.

[10] 湯文亮,周琳穎. 基于三角形外接圓覆蓋的改進APIT定位算法[J]. 傳感技術(shù)學報,2015,28(1):121-125.

[11] Song G,Tam D. Two Novel DV-Hop Localization Algorithms for Randomly Deployed Wireless Sensor Networks[M]. Taylor and Francis,Inc.,2015.

[12] 程超,錢志鴻,付彩欣,等. 一種基于誤差距離加權(quán)與跳段算法選擇的遺傳優(yōu)化DV-Hop定位算法[J]. 電子與信息學報,2015,37(10):2418-2423.

[13] 黃以華,趙汝威,陳小若. 一種具有階段優(yōu)勢的無錨點定位算法[J]. 電子學報,2015,43(12):2536-2541.

[14] S Ren W,Zhao C. A Localization Algorithm Based on SFLA and PSO for Wireless Sensor Network[J]. Information Technology Journal,2013,12(3):502-505.

[15] Kumar S,Lobiyal D K. An Advanced DV-Hop Localization Algorithm for Wireless Sensor Networks[J]. Wireless Personal Communications,2013,71(2):1365-1385.

[16] Gui L,Val T,Wei A,et al. Improvement of Range-Free Localization Technology by a Novel DV-Hop Protocol in Wireless Sensor Networks[J]. Ad Hoc Networks,2015,24:55-73.

ImprovedDV-HopNodeLocalizationAlgorithmBasedonHopCountClassification

RENKeqiang*,LIAOMeiyan

(School of Information Engineering,Jiangxi University of Science and Technology,Ganzhou Jiangxi 341000,China)

The different network node densities made larger difference among average single-hop distance of different hop count values in traditional DV-Hop node localization algorithm,and the error increased with the increase of the hop count value. An improved DV-Hop algorithm was proposed to reduce the influence of the average single-hop distance difference on the node localization accuracy. Firstly,the strategy of hop count classification was proposed to classify the different hop counts in the network,so as to reduce the difference of average single-hop distance between different hop counts,and to enhance the accuracy of node localization. Then,by using the strategy of the improved weight coefficient,the weighted least squares estimation was improved to adapt to the nonlinear variation of the cumulative error,which could better control the weight of the different hop counts in the least squares estimation,and further enhance the accuracy of node localization. The experimental results show that the improved algorithm can effectively reduce the influence of the average single-hop distance difference and the large hop count value on the node localization,its node localization performance is obviously superior to traditional DV-Hop node localization algorithm,compared with comparative literature also has a certain improvement,and it has better adaptability to different network node densities.

wireless sensor network;node localization;DV-Hop algorithm;hop count classification;weighted least squares estimation

TP393

A

1004-1699(2017)10-1565-07

10.3969/j.issn.1004-1699.2017.10.019

任克強(1959-),男,教授,碩士研究生導師,主要研究方向為圖像與視頻處理、無線傳感器網(wǎng)絡(luò)、信息隱藏,jxrenkeqiang@163.com;

廖美焱(1993-),男,碩士研究生,主要研究方向為無線傳感器網(wǎng)絡(luò)。