無(wú)線傳感器網(wǎng)絡(luò)中的DV―HOP定位改進(jìn)算法
摘要:DV-Hop算法是無(wú)線傳感器網(wǎng)絡(luò)中一種典型的基于非測(cè)距的定位算法。針對(duì)DV-Hop存在的定位精度低的缺陷,本文提出了改進(jìn)的算法。該算法中的平均跳距利用全網(wǎng)平均跳距與單個(gè)錨節(jié)點(diǎn)估計(jì)的平均跳距的均值來(lái)修正,并且根據(jù)連通度不同,選取最優(yōu)的3個(gè)錨節(jié)點(diǎn)進(jìn)行三邊定位計(jì)算。
關(guān)鍵詞:無(wú)線傳感器網(wǎng)絡(luò);DV—Hop算法;平均跳距;連通度的不同;三邊定位;定位精度
引言
無(wú)線傳感器網(wǎng)絡(luò)是由大量隨機(jī)分布的傳感器節(jié)點(diǎn)組成,是一種分布式的、自組織的網(wǎng)絡(luò)。其關(guān)鍵技術(shù)包括:網(wǎng)絡(luò)拓?fù)淇刂?、?jié)點(diǎn)定位、時(shí)鐘同步、數(shù)據(jù)融合、路由協(xié)議等。而節(jié)點(diǎn)定位問(wèn)題則是無(wú)線傳感器網(wǎng)絡(luò)中的一個(gè)最為基本和重要的問(wèn)題。目前,無(wú)線傳感器網(wǎng)絡(luò)定位算法可以分為基于測(cè)距和基于非測(cè)距的定位算法。基于測(cè)距定位常用的測(cè)量方法有TOA、TDOA、AOA、RSSI,盡管這些技術(shù)相對(duì)精度高,但是對(duì)硬件要求很高?;诜菧y(cè)距定位常用的測(cè)量方法有:DV-Hop、質(zhì)心、APIT、MDS—MAP。
DV—Hop為典型的基于非測(cè)距定位,其對(duì)硬件要求低,實(shí)現(xiàn)簡(jiǎn)單。它的不足之處在于計(jì)算平均跳距及定位坐標(biāo)時(shí)會(huì)產(chǎn)生誤差。因此針對(duì)DV—Hop算法的缺陷,提出了一系列的改進(jìn)算法,參考文獻(xiàn)對(duì)原始算法中的平均跳距進(jìn)行改進(jìn),使用多個(gè)錨節(jié)點(diǎn)估算平均距離并且采用歸一化加權(quán)的平均跳距。參考文獻(xiàn)提出了基于幾何學(xué)的定位算法,利用幾何學(xué)中的斜率方法來(lái)判斷錨節(jié)點(diǎn)間的位置關(guān)系,從中選取最優(yōu)的錨節(jié)點(diǎn)序列,從而更精確地確定未知節(jié)點(diǎn)。參考文獻(xiàn)引入共線度的概念,利用共線度參數(shù),動(dòng)態(tài)地調(diào)節(jié)未知節(jié)點(diǎn)可以收集的鄰居錨節(jié)點(diǎn)的距離閾值,挑選網(wǎng)絡(luò)中好的錨節(jié)點(diǎn)組進(jìn)行位置估計(jì),最后再用加權(quán)估計(jì)機(jī)制來(lái)得到最終的節(jié)點(diǎn)位置估計(jì)。這些方法都在一定程度上提高了定位精度。
本文針對(duì)DV—Hop算法中計(jì)算平均跳距和三邊定位兩方面存在的定位誤差,提出了改進(jìn)的算法。首先利用全網(wǎng)平均跳距來(lái)糾正單個(gè)錨節(jié)點(diǎn)的平均跳距,然后在最后計(jì)算三邊定位時(shí),利用節(jié)點(diǎn)間連通度的不同,選擇最優(yōu)組合的3個(gè)錨節(jié)點(diǎn)來(lái)參與定位,進(jìn)一步提高定位精度。
1 DV—Hop算法介紹
美國(guó)路特葛斯大學(xué)的Dragos Niculescu等人利用距離矢量路由和GPS定位原理提出一系列分布式定位算法,合稱APS,DV—Hop算法就是其中的一種。
DV—Hop分為3個(gè)步驟實(shí)現(xiàn):
①錨節(jié)點(diǎn)i廣播自身的位置信息IDi。初始跳數(shù)0,每發(fā)送一個(gè)節(jié)點(diǎn)信息,跳數(shù)就加1,然后轉(zhuǎn)發(fā),直到網(wǎng)絡(luò)中所有的節(jié)點(diǎn)都收到錨節(jié)點(diǎn)的信息包。如果節(jié)點(diǎn)收到同一個(gè)錨節(jié)點(diǎn)不同的跳數(shù)信息,只取最小的跳數(shù)信息。
②當(dāng)錨節(jié)點(diǎn)i接收到其他錨節(jié)點(diǎn)的位置和最小跳數(shù)信息后,就可以計(jì)算出平均每跳距離(Average Hop Distance,AHD)的計(jì)算公式:
其中,(xi,yi)、(xj,yj)分別為錨節(jié)點(diǎn)i、j的坐標(biāo);hij為兩個(gè)錨節(jié)點(diǎn)之間的跳數(shù)。未知節(jié)點(diǎn)只接收離它最近的錨節(jié)點(diǎn)的AHDi,hopi為未知節(jié)點(diǎn)離最近錨節(jié)點(diǎn)的跳數(shù),再根據(jù)跳數(shù)信息,即可算得未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離P:
P=AHDi×hopi (2)
③當(dāng)未知節(jié)點(diǎn)獲得3個(gè)或者更多的錨節(jié)點(diǎn)信息時(shí),可以利用三邊定位或者最大似然相似求出未知節(jié)點(diǎn)的位置。(x,y)為未知節(jié)點(diǎn)的坐標(biāo),(xi,yi)為已知錨節(jié)點(diǎn)的坐標(biāo)。根據(jù)式(2)即可算出未知節(jié)點(diǎn)的坐標(biāo):
2 改進(jìn)后的DV—Hop算法
本文主要對(duì)DV—Hop算法里的第2步和第3步進(jìn)行改進(jìn),第1步與原算法相同。原算法中,在第2步計(jì)算平均跳距的時(shí)候,未知節(jié)點(diǎn)接收來(lái)自最近的錨節(jié)點(diǎn)的平均跳距。但是由于網(wǎng)絡(luò)節(jié)點(diǎn)分布的不均勻性,導(dǎo)致單個(gè)錨節(jié)點(diǎn)計(jì)算的平均跳距存在著一定的誤差,因此本文引入全網(wǎng)平均跳距與單個(gè)錨節(jié)點(diǎn)平均跳距的均值來(lái)修正原算法中的平均跳距。在第3步中,錨節(jié)點(diǎn)的位置信息對(duì)定位精度影響很大,本文利用節(jié)點(diǎn)間連通度的不同,選取最優(yōu)的3個(gè)錨節(jié)點(diǎn),以減小定位誤差。
2.1 平均跳距的改進(jìn)
將全網(wǎng)平均跳距與單個(gè)錨節(jié)點(diǎn)估算出來(lái)的AHDi取平均來(lái)代替經(jīng)典算法中的平均跳距,這樣未知節(jié)點(diǎn)既有全網(wǎng)的估算信息,也具有離它最近的錨節(jié)點(diǎn)的估算平均跳距AHDi的局部信息。全網(wǎng)平均跳距公式為:
其中,n為網(wǎng)絡(luò)中的錨節(jié)點(diǎn)的個(gè)數(shù)。
修正后的平均跳距AHD公式為:
AHD=(AHDall+AHDi)/2 (5)
2.2 基于選擇性的3個(gè)錨節(jié)點(diǎn)
基于選擇性的錨節(jié)點(diǎn)的定位算法利用連通度的不同,在三邊節(jié)點(diǎn)定位時(shí),選擇最優(yōu)的3個(gè)錨節(jié)點(diǎn)定位,使其定位誤差最小。節(jié)點(diǎn)分布圖如圖1所示。未知節(jié)點(diǎn)N1利用三邊定位時(shí)可以用不同的3個(gè)錨節(jié)點(diǎn)組(P1,P2,P3)、(P1,P2,P4)、(P2,P3,P4)、(P1,P3,P4)來(lái)定位。而用最大似然估計(jì)計(jì)算時(shí),則選用(P1,P2,P3,P4)來(lái)定位,這樣不同的錨節(jié)點(diǎn)組肯定會(huì)產(chǎn)生不同的定位位置。
2.2.1 基本規(guī)則
用未知節(jié)點(diǎn)與每個(gè)錨節(jié)點(diǎn)的最小跳數(shù)來(lái)定義連通度,用數(shù)組來(lái)表示。比如N1到所有錨節(jié)點(diǎn)的連通度為[1,1,2,5]。這樣圖1中的所有的未知節(jié)點(diǎn)的連通度可以用數(shù)組表示,如表1所列。
用未知節(jié)點(diǎn)之間連通度差的絕對(duì)值的和來(lái)定義連通度的不同,比如N1與N2之間連通度的不同為|1—2|+|1—1|+|2—1|+|5—4|=3。這樣可以計(jì)算N1到其他所有未知節(jié)點(diǎn)的連通度的不同,如表2所列。
由表2可以得出,N2、N3到N1連通度不同為3、4,而N4、N5到N1連通度不同為9、11。說(shuō)明N1離N2、N3更近。這一點(diǎn)也可以從圖1中看出。
2.2.2 確定最優(yōu)的3個(gè)錨節(jié)點(diǎn)
選擇性錨節(jié)點(diǎn)的節(jié)點(diǎn)分布圖如圖2所示。未知節(jié)點(diǎn)Nx代表未知節(jié)點(diǎn)的實(shí)際位置,N(i,j,k)為根據(jù)3個(gè)錨節(jié)點(diǎn)組合所估算的位置,R為節(jié)點(diǎn)的通信半徑,An是離N(i,j,k)最近的錨節(jié)點(diǎn),Am為通信范圍R之外的任意錨節(jié)點(diǎn)。
An的位置情況有3種:在0.5R的通信范圍內(nèi);在0.5R~R的通信范圍內(nèi);在R通信范圍之外。這樣計(jì)算AHD(i,j,k),m就有3種可能:
其中,AHD(i,j,k),m為根據(jù)3個(gè)錨節(jié)點(diǎn)組合所估算的位置節(jié)點(diǎn)與錨節(jié)點(diǎn)Am之間的平均跳距,AHDn,m為錨節(jié)點(diǎn)An與錨節(jié)點(diǎn)Am之間的平均跳距,AHDm為錨節(jié)點(diǎn)Am的平均跳距。
N(i,j,k)與錨節(jié)點(diǎn)Am之間的距離P(i,j,k),m可以計(jì)算出來(lái),那么就可以算出N(i,j,k)與錨節(jié)點(diǎn)Am之間的跳數(shù)hop(i,j,k),m,公式為:
假設(shè)一共有n個(gè)錨節(jié)點(diǎn),這樣N(i,j,k)與Nx計(jì)算出來(lái)的連通度的不同可以表示為
Nx選出最小的連通度不同的節(jié)點(diǎn)是最為靠近Nx的節(jié)點(diǎn)(即定位的誤差最小)。
3 算法仿真實(shí)驗(yàn)
為了驗(yàn)證算法理論的可行性,在100 m×100 m的區(qū)域中,對(duì)提出的改進(jìn)的DV—Hop算法用Matlab7.0進(jìn)行實(shí)驗(yàn)仿真,將實(shí)驗(yàn)結(jié)果與原DV—Hop算法和參考文獻(xiàn)的算法進(jìn)行對(duì)比分析。仿真數(shù)據(jù)隨機(jī)運(yùn)行50次,最后取平均值。
3.1 測(cè)距誤差
測(cè)距誤差是指節(jié)點(diǎn)間的估算距離與實(shí)際距離的差值。在100 m×100 m的區(qū)域中,隨機(jī)分布100個(gè)節(jié)點(diǎn)進(jìn)行仿真實(shí)驗(yàn),其中有一部分部署的是錨節(jié)點(diǎn),是能夠獲知自身位置信息的節(jié)點(diǎn),且錨節(jié)點(diǎn)和未知節(jié)點(diǎn)具有相同的通信半徑。通過(guò)設(shè)置不同的錨節(jié)點(diǎn)比例和節(jié)點(diǎn)通信半徑,比較改進(jìn)的算法與原DV—Hop算法對(duì)測(cè)距誤差的影響。圖3為通信半徑為10 m時(shí)的測(cè)距誤差,圖4為通信半徑為20 m時(shí)的測(cè)距誤差。
在同等條件下,改進(jìn)的測(cè)距誤差始終是低于原DV—Hop算法的,且不同的通信半徑對(duì)測(cè)距誤差也會(huì)產(chǎn)生不同的結(jié)果。圖3中,通信半徑為10 m,改進(jìn)后的算法平均測(cè)距誤差比原算法降低1.45 m;圖4中,通信半徑為20m,改進(jìn)后的算法平均測(cè)距誤差比原算法降低1.67 m。這是因?yàn)殡S著通信半徑的變化,會(huì)對(duì)節(jié)點(diǎn)間的跳數(shù)和平均跳距產(chǎn)生影響。由于本文改進(jìn)后的算法是用全網(wǎng)的平均跳距代替單個(gè)節(jié)點(diǎn)的平均跳距,這樣使得對(duì)平均跳距的估計(jì)更為準(zhǔn)確,估算距離也就越準(zhǔn)確,越接近實(shí)際的距離。
3.2 定位誤差
定位誤差(Localization Error,LE)是指通過(guò)定位算法測(cè)量估計(jì)的坐標(biāo)與實(shí)際坐標(biāo)之間的差值,用這種差值除以節(jié)點(diǎn)的通信半徑,就是定位誤差率。計(jì)算方法如下:
其中,(x,y)為未知節(jié)點(diǎn)的實(shí)際坐標(biāo),(xi,yi)為定位算法所估計(jì)出來(lái)的坐標(biāo);R為節(jié)點(diǎn)的通信半徑。
圖5和圖6是節(jié)點(diǎn)總數(shù)分別為100和300、節(jié)點(diǎn)通信半徑為10 m時(shí),本文改進(jìn)算法、DV—Hop算法和參考文獻(xiàn)中的算法三者在錨節(jié)點(diǎn)比例不同時(shí)的定位誤差比較結(jié)果。從兩幅圖中可以看出,在相同的半徑和錨節(jié)點(diǎn)的環(huán)境下,改進(jìn)算法的定位誤差率要低于DV—Hop算法和參考文獻(xiàn)中的算法。但是在錨節(jié)點(diǎn)比例較低的情況下,節(jié)點(diǎn)的定位誤差較大。這是因?yàn)殄^節(jié)點(diǎn)較少時(shí),未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離變遠(yuǎn),導(dǎo)致計(jì)算平均距離時(shí)會(huì)產(chǎn)生很大的誤差。因此隨著錨節(jié)點(diǎn)比例的增加,能夠有效地減小定位誤差。
圖5中,當(dāng)錨節(jié)點(diǎn)的比例為30%時(shí),DV—Hop的定位誤差率為43.25%,參考文獻(xiàn)算法的定位誤差率為33.37%,而本文改進(jìn)算法的定位誤差率為28.34%。圖6中,當(dāng)錨節(jié)點(diǎn)的比例為30%時(shí),DV—Hop的定位誤差率為26.89%,參考文獻(xiàn)算法的定位誤差率為14.95%,而本文改進(jìn)算法的定位誤差率為10.21%。由此說(shuō)明,本文的改進(jìn)算法要優(yōu)于其他兩種算法。這是因?yàn)樵趨⒖嘉墨I(xiàn)中,只考慮了平均跳距一個(gè)因素對(duì)定位誤差的影響,而本文改進(jìn)算法則是從平均跳距的改進(jìn)和利用連通度的不同選取錨節(jié)點(diǎn)兩個(gè)方面考慮,使其定位誤差進(jìn)一步地減小。
結(jié)語(yǔ)
本文首先介紹了DV—Hop算法的基本思想,針對(duì)經(jīng)典的DV—Hop算法中存在的定位精度不高的缺陷,提出了兩點(diǎn)改進(jìn):
單個(gè)錨節(jié)點(diǎn)所估計(jì)的平均跳距來(lái)代替全網(wǎng)的平均跳距,會(huì)產(chǎn)生很大的誤差,因此平均跳距利用全網(wǎng)平均跳距與單個(gè)錨節(jié)點(diǎn)估計(jì)的平均跳距的均值來(lái)修正;
根據(jù)連通度的不同選擇最優(yōu)的三個(gè)錨節(jié)點(diǎn)進(jìn)行三邊定位計(jì)算,以提高定位精度。
仿真實(shí)驗(yàn)數(shù)據(jù)表明,改進(jìn)后的算法降低了測(cè)距誤差,與參考文獻(xiàn)等提出的算法比較,定位誤差率進(jìn)一步降低,從而提高定位精度。且在改進(jìn)的過(guò)程中,沒(méi)有添加硬件成本。
評(píng)論