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

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

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

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

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

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

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

1 DV-Hop定位算法

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

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

(1)計算未知節(jié)點與每個信標節(jié)點的最小跳數(shù)

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

(2)計算未知節(jié)點與信標節(jié)點的實際跳段距離

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

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

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

(3)未知節(jié)點計算自身位置

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

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

圖1 DV-Hop算法示意圖

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

2 DV-Hop算法誤差分析

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

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

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

3 DV-Hop算法改進

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

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

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

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

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

4 仿真分析

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

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

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

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

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

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

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

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

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

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

(3)定位精度

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

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

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

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

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

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

5 結(jié)語

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

[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)絡主動分布節(jié)點定位算法[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]姚忠孝,俞立,董齊芬.基于移動信標的 DV-hop無線傳感網(wǎng)絡定位算法[J].傳感技術學報,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)絡中的自身定位系統(tǒng)和算法[J].軟件學報,2005,16(5)：858-868.