基于跳數分類的改進DV-Hop節點定位算法

任克強,廖美焱

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

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

基于跳數分類的改進DV-Hop節點定位算法

任克強*,廖美焱

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

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

無線傳感器網絡;節點定位;DV-Hop算法;跳數分類;加權最小二乘估計

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

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

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

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

1.1 DV-Hop算法

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

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

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

(1)

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

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

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

Dis(i,j)=hij×HopSizej

(2)

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

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

1.2 算法誤差分析

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

圖1 節點分布示意圖

從圖1中可以得出以下兩個結論:

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

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

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

圖2 不同跳數的平均每跳距離

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

從圖2中可以看出平均每跳距離隨網絡節點密度的3個變化規律:

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

②從橫坐標看,3種不同節點分布密度呈現出3種不同的變化規律,當網絡節點個數為250時,隨著跳數的增加,平均每跳距離呈現逐漸上升,最后趨于平穩;當網絡節點個數為150個時,隨著跳數的增加,平均每跳距離先呈現出上升,最后呈現出下降的趨勢;當網絡節點個數為100個時,隨著跳數的增加,平均每跳距離逐漸下降。

③從縱坐標看,當跳數固定時,隨著網絡節點數的減少,平均每跳距離逐漸減小。

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

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

2 改進策略

2.1 跳數分類策略

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

設網絡中有n個節點,其中有m個信標節點,信標節點之間的歐氏距離為:

(3)

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

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

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

(4)

圖3 數據包處理偽代碼

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

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

(5)

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

圖4 跳數分類示意圖

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

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

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

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

(6)

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

S4:計算節點到各信標節點的距離:

Disij=HopCoutij×hopCoutij

(7)

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

2.2 加權最小二乘估計的改進

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

(8)

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

(9)

(10)

(11)

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

(12)

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

(13)

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

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

(14)

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

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

(15)

對于權系數W,文獻[15]采用跳數的倒數作為權系數的取值:

(16)

式中:Wp,i表示未知節點p對于信標節點i的權系數;hp,i表示未知節點p到信標節點i的最小跳數。

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

(17)

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

表1 不同跳數的均方誤差

3 實驗仿真與分析

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

(18)

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

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

圖5 網絡節點個數對定位誤差影響

圖6 網絡信標節點密度對定位誤差影響

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

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

圖7 節點通信半徑對定位誤差影響

5 結論

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

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

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

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

[2] 黃亮,王福豹,段渭軍,等. 基于距離重構的無線傳感器網絡多維定標定位算法[J]. 傳感技術學報,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值跳數修正和跳距加權處理的DV-HOP算法[J]. 江西理工大學學報,2015,36(5):80-84.

[5] 錢志鴻,王義君. 面向物聯網的無線傳感器網絡綜述[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] 楊友華,孫麗華,向滿天. 基于質點彈簧模型的無線傳感器網絡非測距定位算法[J]. 傳感技術學報,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]. 傳感技術學報,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] 程超,錢志鴻,付彩欣,等. 一種基于誤差距離加權與跳段算法選擇的遺傳優化DV-Hop定位算法[J]. 電子與信息學報,2015,37(10):2418-2423.

[13] 黃以華,趙汝威,陳小若. 一種具有階段優勢的無錨點定位算法[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-),男,教授,碩士研究生導師,主要研究方向為圖像與視頻處理、無線傳感器網絡、信息隱藏,jxrenkeqiang@163.com;

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