無線傳感器網(wǎng)絡(luò)DV-Hop定位改進(jìn)算法*

衛(wèi)開夏,田金鵬,王克謙

1.徐州師范大學(xué)計(jì)算機(jī)學(xué)院,江蘇徐州 221116;2.上海大學(xué) 通信與信息工程學(xué)院,上海 200072;3.信陽供電公司,河南 信陽 464000

無線傳感器網(wǎng)絡(luò) (Wireless Sensor Networks)是當(dāng)前在國際上備受關(guān)注的、涉及多學(xué)科高度交叉、知識高度集成的前沿?zé)狳c(diǎn)研究領(lǐng)域[1]。對于傳感器網(wǎng)絡(luò)來說,傳感器節(jié)點(diǎn)的位置信息至關(guān)重要,事件發(fā)生的位置或獲取信息的節(jié)點(diǎn)位置是傳感器節(jié)點(diǎn)監(jiān)測消息中所包含的重要信息,沒有位置信息的監(jiān)測數(shù)據(jù)往往毫無意義。因受成本、功耗、擴(kuò)展性等問題的限制,為每個傳感器安裝 GPS模塊等這些傳統(tǒng)定位手段并不實(shí)際,甚至在某些場合可能根本無法實(shí)現(xiàn),而且 GPS定位在定位精度、實(shí)時性方面有時并不能滿足特定的需求,因此針對具體的定位需求,必須采用一定的算法機(jī)制來實(shí)現(xiàn)傳感器節(jié)點(diǎn)的定位。

無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)按定位過程中是否需要測距信息,可分為無需測距的定位方法和基于測距技術(shù)的定位方法。近年來,關(guān)于傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)研究成為無線傳感網(wǎng)絡(luò)技術(shù)的一重要研究熱點(diǎn)并取得大量的研究成果。其中,具有代表性算法研究成果有：凸規(guī)劃算法[2]及其改進(jìn)算法[3],APS算法[4-7]、Cooperative Ranging[8]、AHLos[9]算 法、n-Hop Multilateration Primitive[10]算法 、MDS-MAP[11]算法等。

無需測距的定位方法被認(rèn)為是一類具有好的成本效益的解決方案。在無需測距定位方法中,DVHop(Distance Vector-Hop)節(jié)點(diǎn)定位方法由于對信標(biāo)節(jié)點(diǎn)比例要求較少,定位精度較高,目前已成為一種經(jīng)典的無需測距定位方法[12]。

DV-Hop定位方法的主要思想是引入最短路徑算法到信標(biāo)節(jié)點(diǎn)的選擇過程中,從而在未知節(jié)點(diǎn)的位置估計(jì)過程中可以有效利用多跳信標(biāo)節(jié)點(diǎn)的位置信息,這種方法可以大大減少實(shí)現(xiàn)網(wǎng)絡(luò)定位所需信標(biāo)節(jié)點(diǎn)的比例(密度),從而大大降低網(wǎng)絡(luò)的布置成本。

本文就 DV-Hop算法的誤差成因進(jìn)行了分析,在 DV-Hop定位算法優(yōu)點(diǎn)的基礎(chǔ)上,針對該算法只適用于各向同性網(wǎng)絡(luò)的不足,對 DV-Hop算法進(jìn)行局部優(yōu)化,使得改進(jìn)后的 DV-Hop算法減少了數(shù)據(jù)包發(fā)送量,提高了定位精度,并且對于不規(guī)則形狀的節(jié)點(diǎn)分布具有較強(qiáng)的適應(yīng)性。

1 DV-Hop定位算法

DV-Hop定位算法是 APS算法系列中使用最為廣泛的定位方法,其定位過程不依賴于測距方法,利用多跳信標(biāo)節(jié)點(diǎn)信息來參與節(jié)點(diǎn)定位,定位覆蓋率較大。DV-Hop算法非常類似于傳統(tǒng)網(wǎng)絡(luò)中的距離向量路由機(jī)制,在該定位機(jī)制中,未知節(jié)點(diǎn)首先計(jì)算與信標(biāo)節(jié)點(diǎn)的最小跳數(shù),然后估算平均每跳距離,利用最小跳數(shù)乘以平均每跳距離,估算得到未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的距離,再利用三邊測量法或極大似然估計(jì)法計(jì)算未知節(jié)點(diǎn)的坐標(biāo)。

DV-Hop定位算法可以分為以下 3個階段：

(1)計(jì)算未知節(jié)點(diǎn)與每個信標(biāo)節(jié)點(diǎn)的最小跳數(shù)

信標(biāo)節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播自身位置信息的分組,其中包括跳數(shù)字段,初始化為 0。接收節(jié)點(diǎn)記錄具有到每個信標(biāo)節(jié)點(diǎn)的最小跳數(shù),忽略來自同一個信標(biāo)節(jié)點(diǎn)的較大跳數(shù)的分組。然后將跳數(shù)值加 1,并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)。通過這個方法網(wǎng)絡(luò)中的所有節(jié)點(diǎn)能夠記錄下到每個信標(biāo)節(jié)點(diǎn)的最小跳數(shù)。

(2)計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的實(shí)際跳段距離

每個信標(biāo)節(jié)點(diǎn)根據(jù)第 1階段中記錄的其他信標(biāo)節(jié)點(diǎn)的位置信息和相距跳數(shù),利用式(1)估算平均每跳的實(shí)際距離,

其中,(xi,yi)、(xj,yj)是信標(biāo)節(jié)點(diǎn) i、j的坐標(biāo) ,hj是信標(biāo)節(jié)點(diǎn) i與 j(i≠j)之間的跳段數(shù)。

然后,信標(biāo)節(jié)點(diǎn)將計(jì)算的每跳平均距離用帶有生存期的字段的分組廣播到網(wǎng)絡(luò)中,未知節(jié)點(diǎn)僅記錄接收到的第 1個每跳平均距離,并轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)。這個策略可以確保絕大多數(shù)未知節(jié)點(diǎn)從最近的信標(biāo)節(jié)點(diǎn)接收每跳平均距離。未知節(jié)點(diǎn)接收到平均每跳距離后,根據(jù)記錄的跳數(shù),計(jì)算到每個信標(biāo)節(jié)點(diǎn)之間的距離。

(3)未知節(jié)點(diǎn)計(jì)算自身位置

未知節(jié)點(diǎn)利用第 2階段中記錄的到各個信標(biāo)節(jié)點(diǎn)的跳段距離,利用三邊測量法或極大似然估計(jì)法計(jì)算出自身坐標(biāo)。

如圖 1所示,經(jīng)過第 1和第 2階段,能夠計(jì)算出信標(biāo)節(jié)點(diǎn) L1與 L2、L3之間的距離和跳數(shù)。信標(biāo)節(jié)點(diǎn) L2計(jì)算得到校正值(即每跳平均距離)為(40+75)/(2+5)=16.42。假設(shè)未知節(jié)點(diǎn) A從 L2獲得校正值,則它與 3個信標(biāo)節(jié)點(diǎn)之間的距離分別為L1：3×16.42,L2：2×16.42,L3：3×16.42,最后可利用三邊測量法確定節(jié)點(diǎn) A的位置。

圖1 DV-Hop算法示意圖

DV-Hop算法采用平均每跳距離來估算實(shí)際距離,對節(jié)點(diǎn)的硬件要求低,實(shí)現(xiàn)簡單。其缺點(diǎn)是利用跳段距離代替直線距離,存在一定的誤差。

2 DV-Hop算法誤差分析

在 DV-Hop定位算法中,算法的第 1階段,由于傳感器節(jié)點(diǎn)隨機(jī)分布和廣播分組過程中可能存在沖突等因素,節(jié)點(diǎn)得到的到信標(biāo)節(jié)點(diǎn)的最小跳數(shù)存在有一定偏差,且跳數(shù)越多,偏差越大。

在信標(biāo)節(jié)點(diǎn)采用式(1)估算平均每跳距離時,所利用的是除本節(jié)點(diǎn)外所有其他信標(biāo)節(jié)點(diǎn),所以得到的是全網(wǎng)絡(luò)范圍內(nèi)的平均每跳距離,不能反映本信標(biāo)節(jié)點(diǎn)局部范圍內(nèi)的網(wǎng)絡(luò)密度分布情況。因此,采用該方法得出的平均每跳距離在密度均勻的各向同性網(wǎng)絡(luò)中影響不大,但在密度不均勻的各向異性網(wǎng)絡(luò)中,就會造成較大的誤差。

在 DV-Hop算法的第 3階段,未知節(jié)點(diǎn)利用了到所有信標(biāo)節(jié)點(diǎn)的距離信息,而據(jù)前面的分析,未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的最小跳數(shù)可能有偏差,跳數(shù)越多,偏差越大,且第 2階段得出的平均每跳距離也只是對實(shí)際距離的一種估算,不可避免會存在著誤差,這樣信標(biāo)節(jié)點(diǎn)距未知節(jié)點(diǎn)跳數(shù)越多,二者之間的跳段距離估算誤差就越大,利用較遠(yuǎn)信標(biāo)節(jié)點(diǎn)的距離信息參與位置計(jì)算,反而可能降低了定位結(jié)果的精確度。

3 DV-Hop算法改進(jìn)

根據(jù)上面的分析,本文對 DV-Hop算法加以改進(jìn),改進(jìn)后的方法計(jì)算過程仍與原 DV-Hop算法大致相同,下面僅對改進(jìn)之處加以說明。

在 DV-Hop算法的第 1階段,信標(biāo)節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播自身位置信息的分組時,該分組加上生存期字段 n,其它節(jié)點(diǎn)在轉(zhuǎn)發(fā)該廣播包時,首先檢測生存期字段,如果 n大于 1,則 n=n-1,轉(zhuǎn)發(fā)廣播包;如果 n不大于 1,則不再轉(zhuǎn)發(fā)該廣播包,以保證該分組僅在 n跳范圍內(nèi)廣播。這樣每個節(jié)點(diǎn)僅收到 n跳范圍內(nèi)信標(biāo)節(jié)點(diǎn)信息,降低了原 DV-Hop算法全網(wǎng)洪泛造成的高通信開銷、高分組沖突概率。

在 DV-Hop算法的第 2階段,利用式(1)估算平均每跳實(shí)際距離時,信標(biāo)節(jié)點(diǎn) j取自該節(jié)點(diǎn) n跳范圍內(nèi)跳數(shù)最少的 m個信標(biāo)節(jié)點(diǎn)。這樣處理保證估算的平均每跳實(shí)際距離更符合該節(jié)點(diǎn)附近的節(jié)點(diǎn)分布,提高了距離估計(jì)精確度,并使該方法適用于各向異性網(wǎng)絡(luò)。

最后,在未知節(jié)點(diǎn)利用極大似然估計(jì)法計(jì)算自身坐標(biāo)時,由于信標(biāo)距離該未知節(jié)點(diǎn)跳段越近,二者之間的距離估計(jì)越精確(概率意義上),所以這里只取跳段距離最近的 l個節(jié)點(diǎn)進(jìn)行極大似然估計(jì)法運(yùn)算。這樣,既提高了定位精確度,又降低了節(jié)點(diǎn)的計(jì)算開銷。

參數(shù) n、m、l的取值要綜合考慮信標(biāo)節(jié)點(diǎn)比例、網(wǎng)絡(luò)的連通度、傳感器節(jié)點(diǎn)分布等因素。一般情況下,n要保證絕大部分未知一個節(jié)點(diǎn)能收到 3個以上的信標(biāo)節(jié)點(diǎn)分組,而 m、l取 4～6即可取得相對高的精確度。

4 仿真分析

為了評估所提出的改進(jìn)算法的可用性和有效性,作者利用 Matlab7.0對 DV-Hop算法及本文提出的改進(jìn)算法(Improved DV-Hop,IDV-Hop)進(jìn)行了實(shí)驗(yàn)仿真,并對相關(guān)實(shí)驗(yàn)結(jié)果進(jìn)行分析。

仿真分析的網(wǎng)絡(luò)模型的標(biāo)準(zhǔn)參數(shù)如下：設(shè)定節(jié)點(diǎn)射頻通信距離是 10個長度單位,網(wǎng)絡(luò)規(guī)模為 400個節(jié)點(diǎn),均勻隨機(jī)分布在邊長為 100個長度單位的正方形中(這時的平均連通度為 11左右),其中信標(biāo)節(jié)點(diǎn)比例為 5%。在相同的網(wǎng)絡(luò)場景下,通過改變總節(jié)點(diǎn)數(shù)來改變網(wǎng)絡(luò)的連通度,從而實(shí)現(xiàn)相同網(wǎng)絡(luò)場景下不同網(wǎng)絡(luò)連通度的仿真實(shí)驗(yàn)條件。為消除隨機(jī)性產(chǎn)生的誤差,所得仿真結(jié)果均為同樣參數(shù)下仿真 100次所得結(jié)果的平均值。

(1)可定位節(jié)點(diǎn)比例

可定位節(jié)點(diǎn)比例(也稱算法覆蓋率)是指通過定位算法成功實(shí)現(xiàn)位置估計(jì)的未知節(jié)點(diǎn)數(shù)量占網(wǎng)絡(luò)中所有未知節(jié)點(diǎn)數(shù)量的百分比。通過仿真結(jié)果(圖2,IDV-Hop算法中 n取值為 3)

圖2 可定位節(jié)點(diǎn)比例

可以看出,兩種算法的可定位節(jié)點(diǎn)比例均和網(wǎng)絡(luò)的平均連通度、信標(biāo)節(jié)點(diǎn)比例、算法中分組廣播的生存期字段的取值都有關(guān)系;在同樣的參數(shù)條件下,IDV-Hop算法的可定位節(jié)點(diǎn)比例和 DV-Hop算法相比要低若干個百分點(diǎn),這是因?yàn)樵谒惴ǖ?1階段,可控洪泛使得部分未知節(jié)點(diǎn)收到的信標(biāo)節(jié)點(diǎn)小于 3而不能實(shí)施第 3階段的定位運(yùn)算。

(2)數(shù)據(jù)包發(fā)送量

圖3 數(shù)據(jù)包發(fā)送量

圖3為網(wǎng)絡(luò)連通度為 9和 12時時,DV-Hop算法與 IDV-Hop算法在數(shù)據(jù)包發(fā)送量上的比較,其中橫坐標(biāo)表示信標(biāo)節(jié)點(diǎn)所占的比例,分組廣播的生存期字段均取 3,IDV-Hop算法中的 n取值為 3。從圖中可以看出,網(wǎng)絡(luò)的數(shù)據(jù)通信量隨信標(biāo)節(jié)點(diǎn)比例和網(wǎng)絡(luò)連通度的增加而增加。而在同樣的網(wǎng)絡(luò)參數(shù)下,IDV-Hop算法的數(shù)據(jù)通信量遠(yuǎn)小于 DV-Hop算法(不到原通信量的 20%),這主要是由于在算法的第 1階段,IDV-Hop采用的部分洪泛代替了 DV-Hop算法全網(wǎng)范圍洪泛的緣故。

另外,IDV-Hop算法的數(shù)據(jù)通信量與還與 n的選擇有關(guān),當(dāng)n較小時,該算法限制洪泛跳數(shù)范圍內(nèi)小,所需的數(shù)據(jù)通信量就小,但 n值也不是越小越好,如前面分析,較小的 n值會降低算法的可定位節(jié)點(diǎn)比例。

(3)定位精度

定位誤差(Localization Error,LE)指的是通過定位算法得到的未知節(jié)點(diǎn)的估算位置與實(shí)際位置的偏差,這種偏差可以用兩者之間的歐氏距離除以節(jié)點(diǎn)的通信半徑來衡量,如式(2)所示。顯然,定位誤差的大小能最直接說明算法的有效性。

其中(xea,yea)為未知節(jié)點(diǎn)的估算位置,(xa,ya)為未知節(jié)點(diǎn)的實(shí)際位置,R為節(jié)點(diǎn)的通信半徑。

圖4給出了傳感器節(jié)點(diǎn)均勻分布時,DV-Hop算法和 IDV-Hop算法定位精度比較結(jié)果?？梢钥闯?在各向同性網(wǎng)絡(luò)中,在相同的網(wǎng)絡(luò)連通度和信標(biāo)節(jié)點(diǎn)比例下,改進(jìn)后的算法比原算法定位精度均有所提高,特別是在大于 6%時,IDV-Hop算法的定位精度隨著信標(biāo)節(jié)點(diǎn)比例升高而迅速提高,而原 DVHop算法提高并不明顯,這是由于信標(biāo)節(jié)點(diǎn)比例越高,IDV-Hop算法越有機(jī)會采用距離估計(jì)精確度較高的鄰近信標(biāo)節(jié)點(diǎn)進(jìn)行定位運(yùn)算,從而提高了定位精度,驗(yàn)證前面對 DV-Hop算法的分析。

圖4 節(jié)點(diǎn)均勻分布時的定位精度

圖5為傳感器節(jié)點(diǎn)非均勻分布時(節(jié)點(diǎn)分布從左到右逐漸由疏變密),DV-Hop算法和 IDV-Hop算法定位精度結(jié)果。與圖 4相比,DV-Hop算法定位精度大幅下降,而 IDV-Hop算法僅稍有下降。在同樣的網(wǎng)絡(luò)參數(shù)下,IDV-Hop算法的定位精度比 DV-Hop算法提高了大約 20%,可見,改進(jìn)后的算法更適用于各向異性網(wǎng)絡(luò)。

圖5 節(jié)點(diǎn)不均勻分布時的定位精度

5 結(jié)語

本文分析了 DV-Hop算法只適用于各向同性網(wǎng)絡(luò)的原因,對 DV-Hop算法進(jìn)行局部性優(yōu)化,給出了無線傳感器網(wǎng)絡(luò)無需測距 DV-Hop定位的改進(jìn)算法。仿真結(jié)果表明,改進(jìn)后的算法可定位節(jié)點(diǎn)比例略有下降,但提高了定位精度,特別是節(jié)點(diǎn)非均勻分布時的定位精度,減少了數(shù)據(jù)包發(fā)送量,因此更適用于在實(shí)際項(xiàng)目中應(yīng)用。

[1]Akyildiz I,Su W,Sankarasubramaniam Y,et al.A Survey on Sensor Networks[J].IEEE Communications Magazine,2002,40(8)：102-114.

[2]Doherty L,Pister K SJ,Ghaoui L E.Convex Position Estimation in Wireless Sensor Networks[C]//IEEE INFOCOM2001 Anchorage Alaska,2001：1655-1663.

[3]陳迅,唐紅雨,涂時亮.無線傳感器網(wǎng)絡(luò)主動分布節(jié)點(diǎn)定位算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2008,29(7)：1664-1667.

[4]Niculescu D,Nath B.Ad Hoc Positioning System(APS)[C]//Proc.of the IEEE INFOCOM 2003.IEEE Computer and Communications Societies,2003：1734-1743.

[5]Niculescu D,Nath B.Localized Positioning in Ad Hoc Networks[C]//1stIEEE Int'l Workshop on Sensor Network Protocols and Applications.Anchorage,A laska,2003：42-50.

[6]Niculescu D,Nath B.DV Based Position in Ad Hoc Networks[J].Journal of Telecommunication System,2005,22(4)：267-280.

[7]姚忠孝,俞立,董齊芬.基于移動信標(biāo)的 DV-hop無線傳感網(wǎng)絡(luò)定位算法[J].傳感技術(shù)學(xué)報(bào),2009,22(10)：1504-1507.

[8]Savarese C,Rabaey JM,Beutel J.Locationing in Distributed Ad-Hoc Wireless Sensor Network[C]//Proc.of the 2001 IEEE Int'l Conf.on Acoustics,Speech,and Signal.IEEE Signal Processing Society,2001：2037-2040.

[9]Savvides A,Han C-C,Srivastava MB.Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors[C]//Proc.of the 7th Annual Int'l Conf.on Mobile Computing and Networking.ACM Press,2001：166-179.

[10]Avvides A,Park H,Srivastava MB.The Bitsand Flops of the NHop Multilateration Primitive for Node Localization Problems[C]//Proc.of the 1st ACM Int'l Workshop on Wireless Sensor Networksand Applications.ACM Press,2002：112-121.

[11]Shang Y,Rum lW,Zhang Y,etal.Localization From Mere Connectivity[C]//Proc.of the 4th ACM Int'l Symp.on Mobile Ad Hoc Networking＆ Computing.Annapolis.ACM Press,2003：201-212.

[12]王福豹,史龍,任豐原.無線傳感網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報(bào),2005,16(5)：858-868.