任克強(qiáng),廖美焱

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

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

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

任克強(qiáng)*,廖美焱

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

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

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

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

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

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

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

1.1 DV-Hop算法

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

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

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

(1)

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

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

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

Dis(i,j)=hij×HopSizej

(2)

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

最后利用三邊測(cè)量法或者極大似然估計(jì)法估計(jì)未知節(jié)點(diǎn)的坐標(biāo)。

1.2 算法誤差分析

圖1中分布著兩個(gè)信標(biāo)節(jié)點(diǎn)S和D以及若干個(gè)未知節(jié)點(diǎn)。

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

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

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

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

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

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

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

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

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

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

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

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

因此,在網(wǎng)絡(luò)節(jié)點(diǎn)密度較低或者網(wǎng)絡(luò)拓?fù)浞植疾灰?guī)則時(shí),采用DV-hop算法或全網(wǎng)絡(luò)平均算法是不可取的,誤差會(huì)很大。此外,文獻(xiàn)[16]的分析表明隨著未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)跳數(shù)的增加,未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的估計(jì)距離誤差將會(huì)逐漸增加。

2 改進(jìn)策略

2.1 跳數(shù)分類策略

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

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

(3)

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

HCC策略共由3個(gè)階段組成:

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

(4)

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

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

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

(5)

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

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

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

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

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

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

(6)

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

S4:計(jì)算節(jié)點(diǎn)到各信標(biāo)節(jié)點(diǎn)的距離:

Disij=HopCoutij×hopCoutij

(7)

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

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

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

(8)

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

(9)

(10)

(11)

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

(12)

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

(13)

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

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

(14)

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

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

(15)

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

(16)

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

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

(17)

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

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

3 實(shí)驗(yàn)仿真與分析

為了測(cè)試本文改進(jìn)策略的效果,采用MATLAB對(duì)DV-Hop算法、文獻(xiàn)[15]算法以及本文算法進(jìn)行仿真實(shí)驗(yàn),并以平均相對(duì)誤差為標(biāo)準(zhǔn)對(duì)仿真結(jié)果進(jìn)行分析評(píng)價(jià):

(18)

實(shí)驗(yàn)場(chǎng)景為100 m×100 m的矩形區(qū)域,仿真實(shí)驗(yàn)分成三組,每組的實(shí)驗(yàn)結(jié)果為分別仿真100次的平均值;通信半徑為R,考慮到真實(shí)的通信半徑并不是標(biāo)準(zhǔn)的圓,允許每個(gè)節(jié)點(diǎn)的R有0～10%的誤差波動(dòng)。

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

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

圖6 網(wǎng)絡(luò)信標(biāo)節(jié)點(diǎn)密度對(duì)定位誤差影響

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

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

圖7 節(jié)點(diǎn)通信半徑對(duì)定位誤差影響

5 結(jié)論

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

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

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

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

[2] 黃亮,王福豹,段渭軍,等. 基于距離重構(gòu)的無(wú)線傳感器網(wǎng)絡(luò)多維定標(biāo)定位算法[J]. 傳感技術(shù)學(xué)報(bào),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]. 江西理工大學(xué)學(xué)報(bào),2015,36(5):80-84.

[5] 錢志鴻,王義君. 面向物聯(lián)網(wǎng)的無(wú)線傳感器網(wǎng)絡(luò)綜述[J]. 電子與信息學(xué)報(bào),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ì)點(diǎn)彈簧模型的無(wú)線傳感器網(wǎng)絡(luò)非測(cè)距定位算法[J]. 傳感技術(shù)學(xué)報(bào),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] 湯文亮,周琳穎. 基于三角形外接圓覆蓋的改進(jìn)APIT定位算法[J]. 傳感技術(shù)學(xué)報(bào),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]. 電子與信息學(xué)報(bào),2015,37(10):2418-2423.

[13] 黃以華,趙汝威,陳小若. 一種具有階段優(yōu)勢(shì)的無(wú)錨點(diǎn)定位算法[J]. 電子學(xué)報(bào),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

任克強(qiáng)(1959-),男,教授,碩士研究生導(dǎo)師,主要研究方向?yàn)閳D像與視頻處理、無(wú)線傳感器網(wǎng)絡(luò)、信息隱藏,jxrenkeqiang@163.com;

廖美焱(1993-),男,碩士研究生,主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)。