1、基于鄰節點空間順序序列優化的DV-Hop定位算法鐘進發許力葉阿勇(福建師范大學網絡安全與密碼技術重點實驗室福建福州 350007摘要:針對典型的DV-Hop定位算法中未知節點在計算與信標節點間距離時估算的不足,在DV-Hop算法的基礎上提出了一種優化定位精度的算法。考慮并分析了未知節點與信標節點的路徑中相鄰三個節點的通信邊組成的夾角對計算距離的影響,提出了一種基于“鄰節點空間順序”序列標號法計算夾角的方案,實驗仿真驗證了該優化定位算法的有效性和可行性。關鍵詞:無線傳感器網絡;節點定位;DV-Hop;鄰節點空間順序序列An Improved DV-Hop Localization Algorit

2、hm Based on the Ordered Neighboring Nodes in SpaceZHONG Jin-Fa, XU Li, YE A-Yong(Key Laboratory of Network Security and Cryptology, Fujian Normal University, Fuzhou 350007, China Abstract:The precision of DV-Hop localization algorithm is not good enough when it is used to compute the distance value

3、between unknown nodes and beacon nodes. To overcome its disadvantage, a precision improvedalgorithm based on DV-Hop is proposed. The three neighboring nodes in the route of the unknown node tothe beacon node are analyzed, and an improced DV-Hop Location Algorithm based on the OrderedNeighboring Node

4、s in Space is proposed. Simulation proves that the improved algorithm is effective andfeasible.Keywords: wireless sensor networks; localization; DV-hop; ordered neighboring nodes in space1 引言對大多數的無線傳感器網絡應用而言,不知道傳感器節點位置而感知的數據是沒有意義的。現有無線傳感器網絡節點自身定位方法主要有:基于測距的定位方法和無需測距的定位方法。基于測距的定位方法通過節點配備額外測量設備測量節點間點到

5、點的距離或角度信息,利用三邊測量或最大似然估計定位法來計算出未知節點的位置信息,常用的測距方法有TOA1, TDOA2,RSSI3和AOA4等;無需測距的定位方法則僅根據網絡的連通性和信標節點的位置信息實現相對精確的定位功能,典型的方法有質心算法、DV-Hop5,DV- distance5,凸規劃算法6、APIT和MDS- MAP算法7 等。在精度允許的情況下,無需測距的定位方法,更適合低成本、低功耗的無線傳感器網絡。DV-Hop算法是目前研究和應用最為廣泛的無需測距定位算法之一,但其在計算未知節點和信標節點間的距離時估算較粗糙,使其定位精度受到較大影響。本文針對DV-Hop算法的這一不足,考

6、慮未知節點到信標節點路徑中相鄰三個節點組成的夾角對求解未知節點到信標節點距離的影響8,提出了一種優化定位精度的方案。2 DV-Hop定位算法DV-Hop算法由以下3個階段組成:網絡中的節點獲取自身與每個信標節點的最基金項目:福建省科技計劃(2008F5020;福建省教育廳重點項目(JA07030;福建省自然科學基金(2008J0014收稿時間:2009-06-08小跳數。這一階段利用典型的距離矢量交換協議來獲取網絡中的所有節點到每個信標節點的最小跳數及傳播過程中經過的路徑系列。 各信標節點計算平均單跳距離校正值。 每個信標節點根據第階段中記錄的其他信標節點的位置信息和相距跳數,利用 (1 式估

7、算平均單跳距離校正值。其中,( i x ,i y , (j x ,j y 是信標節點i, j 的坐標, j h 是信標節點i 與j( j i 之間的跳數。然后,信標節點將計算的校正值廣播至網絡中。未知節點接收到校正值后, 根據記錄的跳數, 計算到每個信標節點的距離。(1 利用三邊測量法或極大似然估計法計算自身位置。未知節點利用第階段中記錄的3個或更多信標節點的距離,利用三邊測量法或極大似然估計法計算自身坐標。 圖1 DV-hop定位算法示圖如圖1所示,已知信標節點2L 與1L , 3L 之間的距離和跳數。2L計算得到校正值 (40+75/(2+5=16.42,假設未知節點A 從獲得校正值,則它

8、與3個信標節點之間的距離分別為1D =3×16.42,2D =2×16.42, 3D =3×16.42, 節點A 的位置便可以使用三邊測量法確定。3 基于鄰節點空間順序序列優化的DV-Hop 定位算法3.1 DV-Hop 算法的誤差分析在DV-Hop 算法中,計算未知節點與信標節點之間的距離是通過采用該節點收到的最近信標節點的校正值和未知節點與信標節點間的最小跳數的乘積來表示的。這樣粗糙的估算會使DV-Hop 算法僅在各向同性的密集網絡中,校正值才能較合理地估算。因為,在實際網絡拓撲中,未知節點與信標節點間的路徑往往不是直線的。圖2 DV-Hop 定位 圖3 余弦

9、定理解三誤差示圖 角形第三邊如圖2所示,設節點L 為信標節點,A 、B 、C 為未知節點,設信標節點L 的平均單跳校正值為10m ,未知節點C 從L 處獲得校正值后應用DV-Hop 算法計算到信標節點L 的距離應該是3×10m 。然而,節點C 和節點L 間的路徑并非直線,使得這一估算的距離遠大于它們間的實際距離。 3.2 DV-Hop 算法的優化方案在圖3中,若已知AB 、BC 的長度分別為|AB|、|BC|,又知道它們間的夾角ABC ,則AC 的精確長度為:(2圖4 局部網絡拓撲圖同理,在無線傳感器網絡中,如圖4所示,節點L 為信標節點,節點A 、B 、C 均為未知節點,且A 、C

10、 均為B 的一跳鄰節點。在平面網絡拓撲圖中,由于DV-Hop 算法利用典型的距離矢量交換協議,且未知節點只接收到每個信標節點的最小跳數,這就使信標L 到B 的路徑中經過的節點B 的鄰節點滿足在空間位i ji ji jHopSize h=|AC置上與L 有最短的歐氏距離,圖4中B 的鄰節點A 滿 足此條件。假設信標節點L 到未知節點C 的路徑中經過節點A 和B ,在節點L 到C 的鏈路中,稱節點A 為B 的前驅節點,節點B 為C 的前驅節點。若節點B 的位置信息已經通過計算獲得,即|LB|的距離已經獲得,又因為節點B 是C 的一跳鄰節點,所以BC 的距離|BC|以平均跳距估算。若此時再獲取角LB

11、C 的值,便可以利用(2式計算|LC|。雖然無法直接計算或獲得角LBC 的值,但我們可以利用節點C 與其前驅節點B 的邊BC 及B 與其鄰節點A 組成的邊AB 組成的角ABC 近似代替角LBC ,而角ABC 可以利用節點B 的鄰節點個數及其鄰節點序列(如順時針或逆時針序列來間接估算。在無線傳感器網絡中,若兩個節點互為鄰節點且它們的鄰居列表里相同的元素越多,則在一定程度上反映這兩個節點在位置上應該是越靠近。節點B 的鄰節點個數是容易獲得的,而節點B 的鄰節點序列我們采用“鄰節點空間順序”標號法來實現。平面網絡節點N 實現“鄰節點空間順序”標號法有以下四個步驟組成:步驟1: N 節點創建鄰節點集n

12、eighbor S 及創建各鄰節點發過來的鄰居列表中除去不在neighbor S 中的節點集i n SL 。步驟2: 取出neighbor S 中的第一個元素加入雙向鏈表List 中,并在neighbor S 中刪除加入了List 的元素。步驟 3: 若neighbor S 已經為空則完成步驟3,進入步驟4,否則進入; 若List 的鏈表尾節點i 對應的i n SL 表中還有未加入List 的元素,則進行加入List 鏈表尾操作,否則進入;重復; 若List 的鏈表頭節點j 對應的j n SL 表中還有未加入List 的元素,則進行加入List 鏈表頭操作,否則進入;重復; 進行插入操作,返回

13、到。其中加入List 鏈表尾(頭操作為:在List 的鏈表尾(頭元素節點對應的i n SL 表中未加入List 的元素里選取一個元素,要求該元素節點對應的j n SL 里的元素與List 的鏈表尾(頭元素節點對應的i n SL 的相同元素個數最多,并把其加入List 鏈表尾(頭,并在neighbor S 中刪除該元素;插入操作為:若List 鏈表尾和鏈表頭元素對應的i n SL 中的元素都已經加入List ,neighbor S 仍不為空,則該元素的i n SL 中一定存在兩個節點互為鄰節點且它們在空間順序上是位于該元素的兩端,所以把該元素插入這對互為鄰節點元素在List 中的位置,并在nei

14、ghbor S 刪除該元素。步驟4: 從List 的一端到另一端的元素系列進行順序標號。當List 的鏈表尾(或鏈表頭元素節點對應的i n SL 表中未加入List 的元素里有兩個以上的元素分別對應的j n SL 里的元素與List 的鏈表尾(或鏈表頭元素節點對應的i n SL 的相同元素個數相等時,此算法也可能存在局部排序誤差。如圖4所示,節點A 和節點C 之間的節點數目可以間接反映出角ABC 的大小。假設節點B 有n 個鄰節點,在B 的所有鄰節點中節點A 和B 的空間順序標號分別是i 和j ,則: (3節點隨機放置的網絡中,節點的網絡密度越大即每個節點的鄰節點數越多,在其周圍節點的分布均勻

15、的概率也就越大,即角ABC 也就越逼近 的值。3.3 優化后算法的定位過程優化后的定位過程分以下三個階段: 網絡中的節點獲取自身與信標節點的最小跳數及每個節點自己的鄰居列表。信標節點向其鄰節點廣播自身位置信息及路徑序列。其中自身位置信息包括跳數字段,初始化為0,路徑序列包括自身節點ID 。接收節點記錄到每個信標節點的最小跳數,忽略來自同一個信標節點的較大跳數的分組,然后將跳數加1,將自身節點ID 加入到相應的路徑序列中,轉發給鄰節點。每個節點在收集到自己的所有鄰節點ID 后創建自己的鄰居列表neighbor S 。 信標節點計算平均單跳距離校正值。 每個信標節點根據第階段中記錄的其他信標節點的

16、位置信息和相距跳數,利用式(1估算校正值。然后,信標節點將計算的校正值廣播至網絡中, 未知節點僅記錄接收到的第一個校正值,并轉發給其鄰居節點。 計算未知節點與信標節點間的距離并計算自身位置。1 節點從步驟中得到的所有鄰居列表信息實現“鄰節點空間順序”標號法對鄰節點進行標號;|2j i n ×|2j i ABC n× 2 對于未知節點,如圖4所示的節點C ,在節點L 到節點C 的路徑中C 的前驅節點B 的距離已經通過步驟計算獲得,設為1D ;節點C 到B 的距離采用該節點獲得的最近信標節點的平均每跳跳距表示,設為correction D ;節點L 到C 的路徑中節點A 是B

17、的前驅節點,并通過節點B 的鄰節點個數n 和B 的鄰節點空間順序標號(設節點A 、C 在B 的鄰節點空間順序標號為i 和j,通過(3式估算出角ABC 的值;則通過(4式估算出節點L 到C 的距離LC D 。(4 3 利用三邊測量法或極大似然估計法計算自身位置。4 仿真實驗結果及分析 為了驗證本文提出的優化算法的有效性和可用性,將該算法與DV-Hop 定位算法進行了在定位誤差上的比較,每個實驗場景都執行10次并對得到的結果取平均值。在本實驗中,在固定大小的實驗平面區域內通過改變節點的數量來改變平均網絡節點密度;定位誤差定義為未知節點經定位算法的估算坐標位置與其實際坐標位置間的距離與節點的通信半徑

18、值的比值,假設未知節點經定位算法的估算坐標位置為(e x ,e y ,其實際坐標位置為(i x ,i y ,節點的通信半徑值知節點的定位誤差為。 圖5是在500×500的平面區域內,網絡節點隨機放置,節點的通信半徑為=100,信標節點的比例占10%的條件下不同平均網絡節點密度的實驗結果。優化后的定位算法在不同平均網絡節點密度的情況下定位精度比典型的DV-Hop 定位算法均有不同程度的提高,在一定程度上驗證了本文提出的優化策略的有效性。圖6是在500×500的平面區域內,200個網絡節點隨機放置,節點的通信半徑為=100,通過改變信標節點的個數來改變信標節點比例的實驗結果。從

19、實驗數據可以看出在信標節點比例小的情況下,優化后的定位算法在精度上的優勢更為明顯。圖5 網絡節點密度對誤差的影響圖6 信標節點比例對誤差的影響5 結語本文針對典型的DV-Hop 定位算法基礎上提出了一種優化定位精度的算法,并設計了一種 “鄰節點空間順序標號法”計算夾角的方案。在實驗仿真中進一步驗證了該優化定位算法的有效性和可行性,特別是信標比例較低的情況下,從未知節點定位的精度角度看,優化后的算法比典型的DV-Hop 算法優勢更加明顯。然而,節點在獲取鄰節點的鄰居列表過程中在一定程度上增加了通信代價,而且有可能產生一定的誤差;節點為了計算更加精確的距離過程中增加了一部分計算量。因此,如何使誤差

20、最小化并最大化地減小計算、通信量方面是進一步要做的工作。LC D I參考文獻1 Haretr A, Hopper A, Steggles P, Ward A, Webster P. The anatomy of a context-aware application. Proc. of the 5th Annual ACM/IEEE Intl Conf. on Mobile Computing and Networking. Seattle: ACM Press, 1999,59-68.2 Girod L, Estrin D. Robust range estimation using aco

21、ustic and multimodal sensing. Proc. of the IEEE/ RSJ Intl Conf. on Intelligent Robots and Systems (IROS 01. Vol.3, Maui: IEEE Robotics and Auto- mation Society, 2001.1312-1320.3 Girod L, Bychovskiy V, Elson J, Estrin D. Locating tiny sensors in time and space: A case study. Werner B, ed. Proc. of th

22、e 2002 IEEE Intl Conf. on Computer Design: VLSI in Computers and Processors. Freiburg: IEEE Computer Society, 2002.214-219.4 Priyantha NB, Miu AKL, Balakrishnan H, Teller S. The cricket compass for context-aware mobile appli-(上接第85頁反銳化掩模法的ROI提取計算時間更短,更易于計算機編程實現。(a 原始圖像(b ROI提取結果圖3 ROI提取結果4 結語本文重點研究了

23、乳腺X射線影像中感興趣區域的提取。在對圖像進行基本的背景分割后,通過區域擴張算法進行乳腺區域的提取,具有較高的準確率,從而降低了ROI分析的計算量,為后續的ROI分析提供了良好的前提條件。最后采用改進的反銳化掩模法進cations. Proc. of the 7th Annual Intl Conf. on Mobile Computing and Networking. Rome: ACM Press, 2001. 1-14.5 Niculescu D, Nath B. DV based positioning in ad hoc networks. Journal of Telecommunication Systems, 2003:22(1/4:267-280.6 Doherty L, Pister KSJ, Ghaoui