面向無線傳感器網絡節點定位的移動錨節點路徑規劃

牛龍生,張 瑞,郭瑛

(青島科技大學 信息科學技術學院,山東 青島 266061)

在無線傳感器網絡中,只有傳感器節點的位置已知,節點采集的數據才有意義[1]。然而,受限于傳感器節點的成本,為每一個節點配置GPS設備是不現實的[2]。通常,待定位的傳感器節點將少量配有GPS裝置、位置已知的錨節點視為參考節點[3],通過與錨節點間的通信估計或計算自身位置[4-5]。錨節點的成本高,部署位置對于定位精度影響較大,采用移動錨節點可以有效的降低部署的成本,提高定位精度。

按照錨節點的移動路徑不同,可分為基于靜態路徑的定位算法和基于動態路徑的定位算法[6]。在基于靜態路徑的算法中,錨節點循著靜態路徑對整個部署區域進行全局掃描。典型的靜態路徑包括SCAN[7]、HILBERT[7]、Z-Curve[8]、M-Curve[9]等。其中SCAN 路徑簡單但存在信標分布的共線性問題;HILBERT、Z-Curve、M-Curve解決了這個問題而增大了路徑長度。在實際環境中,傳感器節點部署不均勻,且分布受外力影響[10]。這時,錨節點無法避開空白區域,從而發送無效信標,消耗了能量。

移動錨節點動態路徑規劃的基本原理是利用網絡中局部鄰居信息來決定錨節點的下一步前進方向。FU等[11]基于人工勢場法,利用6個定向天線,選擇虛擬力最大的那個方向作為下一步的移動方向;WEI等[12]同樣使用虛擬力機制,設計了基于未知節點密度權重的改進虛擬力模型及回退方案,并討論了最優的移動步長。算法總是可以使每個未知節點周圍的三個信標節點呈正三角形分布,定位誤差較小;李洪峻等[13]利用圖論,將路徑規劃問題轉化為圖的遍歷問題,他們提出了一種寬度優先(BRF)算法和回溯貪心(BTG)算法,將通信范圍內的節點劃分為內部節點和邊緣節點,在生成樹的建立過程中只考慮邊緣節點,這減小了路徑長度但也導致部分內部節點無法定位;LI等[14]提出了一種啟發式運動策略和局部最小生成樹的優化技術,并進一步研究了多移動信標協作定位。這些算法都使用了生成樹的深度優先遍歷(depth-first traversal,DFT),回溯代價較大。李松生等[15]提出了一種動態選擇前進方向的策略,但定位率不高。ABDULLAH等[16]應用模糊邏輯,綜合考慮未知節點的RSSI、鄰居的數量,選出下一步的前進方向,而這對錨節點的計算能力有更高的要求。

基于邊界的方法[17-18]是機器人環境探索領域的一種重要方法,其中邊界指的是已知與未知區域的邊界。NAGALAJU等[19]首次在無線傳感器網絡中使用該方法進行區域探測和節點定位,是一種比較新的視角。受此影響,本工作首先設計了錨節點和傳感器節點之間的通信過程,并引入了兩種新的數據結構,邊緣點與探索點,不僅提高了定位率,而且避免了對生成樹的逐層回溯,提高了算法的效率。進而提出了一種動態、靜態路徑相結合的錨節點移動方案:錨節點采用正六邊形軌跡或菱形軌跡來覆蓋某一局部區域,這使得該局部區域內,節點接近完全定位;覆蓋完一個區域后根據局部鄰居信息動態選擇并移動到下一個覆蓋區域。相比靜態路徑,這種路徑因可以避開空白區域而更加靈活;相比傳統的動態路徑方案,這種路徑方案通過區域覆蓋定位局部子區域的大部分節點,也大大減少了對同一子區域的重復訪問,從而避免不必要的能量消耗。仿真結果表明本設計的路徑較短,基于這種路徑的定位算法定位率更高。

1 通信過程設計

錨節點和普通的傳感器節點存在功能、制作成本等方面的差異,因此可以有不同的通信范圍。能量優化是無線傳感器網絡研究中最重要的問題之一。有研究表明,使兩種節點的通信范圍保持一致可以建立雙向連接并節省能量[20]。因此在本工作的設計中,令錨節點和普通的傳感器節點通信范圍相同。

錨節點在其移動過程中發送包含自身當前位置的信標。當錨節點移動到一個新位置時,其通信范圍內的節點分為3類:未定位節點、新定位的節點、先前已定位節點。其中新定位節點指的是通過錨節點這次移動引入的新的位置信息而完成定位的那些節點;先前已定位節點指的是已經完成定位的節點,錨節點這次新的移動沒有改變它的已定位狀態;未定位節點指的是在錨節點這次移動后依然無法完成定位計算的節點。隨著錨節點的移動、定位的進行,每個節點都會由未定位狀態變成新定位狀態,之后再由新定位狀態變成先前已定位狀態。不同的狀態下傳感器節點需要處理的數據包也不盡相同。新定位的節點需要與其一跳鄰居以及錨節點通信:收集鄰居的信息,然后回復錨節點;先前定位的節點回復新定位的節點的詢問消息;而未定位的節點只與錨節點進行通信。

首先,網絡中所有節點經歷一個鄰居發現過程,每個傳感器節點廣播一條自身是否已被定位的消息,過程中傳感器節點廣播后只被動的接收信號,而不轉發。這樣每個傳感器節點都只獲得它的一跳鄰居信息。此信息包含了鄰居的數目以及某個鄰居是否已經完成定位。每個節點都維護一個“未定位鄰居列表”{unloc_nb_num,nb_id1,nb_id2,…},其中第一項是未定位鄰居的數量,后面的項是其鄰居的id集合。

隨著錨節點的移動并發出信標,引入了新的位置信息,一些未定位節點可以通過計算確定自身位置,這些節點的狀態變成了新定位狀態。每個新定位的節點會廣播一條消息,告知其所有的一跳鄰居節點自身已定位。對于這個新定位節點的每個一跳鄰居節點,在收到此消息后,把這個新定位的節點id從它們的未定位鄰居列表中刪除,并且相應的unloc_nb_num減1。如果這個鄰居節點為已定位狀態,則向新定位的節點回復最新的unloc_nb_num信息,否則不回復消息。

錨節點維護兩個列表,邊緣列表和探索列表。如果節點已定位,但其unloc_nb_num不為零,則稱之為邊緣點。這樣的節點組成了邊緣列表。探索列表記錄所有探索點,探索點存儲了未定位節點通信范圍內的一個信標發出點位置,用來標記那些還未定位、但曾經接收到至少一個信標的節點。邊緣點定義為{node_id,cal(x),cal(y),NFP(x),NFP(y),unloc_nb_num},探索點定義為{node_id,ref_beacon(x),ref_beacon(y)}。其中,cal(x)和cal(y)表示計算出的節點坐標,NFP主要用于推斷局部區域哪一側尚未訪問,將在2.2.3節介紹的過程中用到。ref_beacon是未定位節點接收到的第一個信標的信標發出點位置。

新定位節點向錨節點的回復消息定義為{node_id,cal(x),cal(y),unloc_nb_num,Map}。這里定義了一個鍵值映射,它的鍵是先前定位的鄰居節點的id,值是相應的未定位鄰居數unloc_nb_num。node_id表示新定位的節點id。在每個信標發送位置,錨節點需要停留一小段時間以接收新定位節點的回復消息。通過與新定位節點的這次通信,錨節點便可及時更新先前已定位節點的未定位鄰居數目信息,從而更新或移除(當unloc_nb_num變為0)一些邊緣點。每次移動后,錨節點會檢測新定位的節點是否存在于探索點列表中,存在則移除相應的探索點。通過上述通信過程,邊緣列表和探索列表都可以有效地更新,這樣就不會有過多的重復訪問。另外這兩個列表存儲的一些信息是避開DFT 中逐層回溯的關鍵。

一般來說,發送信號的能量消耗遠遠大于接收信號,所以這里主要考慮上述通信過程中每個節點發送信號的能量消耗。首先每個節點在鄰居發現階段都要經歷一次廣播。定位開始后,每個節點在第一次收到信標時回復錨節點;在新定位時廣播消息、向錨節點回復鄰居的信息;以及作為先前已定位節點向其新定位的鄰居節點回復消息。先前已定位狀態下回復新定位鄰居的次數與網絡的連通度有關。節點度[21]是衡量網絡連通度的重要指標,指的是網絡中節點的平均連接數,定義如下,

其中V_links指的是網絡中的總連接數,V_nodes指總的節點數。假設網絡的節點度為n,這樣,每個節點需要進行2次廣播和(n+2)次單播。

2 移動錨節點路徑規劃

2.1 定位方法

假設錨節點的通信范圍為R,則其發出的信標的覆蓋區域為一個圓,該圓以錨節點的當前位置為中心,R為半徑。對于定位問題,常用的方法是三邊測量法。在此方法中,節點通過3個非共線信標的坐標與到它們的距離計算自身位置,即

其中,(xi1,yi1),(xi2,yi2)和(xi3,yi3)是節點收到的3個信標的發出點坐標,d1,d2,d3是到它們的距離?！时硎静灰巹t信號傳輸引起的誤差。求解此線性方程組,即可得待定位節點的坐標。

2.2 移動路徑設計

2.2.1 初始覆蓋(Initialize)

李石堅等[22]指出,為了保證完全定位,錨節點所發出的各個信標的分布應滿足對部署區域達到三重覆蓋。即當錨節點沿某一路徑移動時,該路徑需要使得部署區域中任意點均至少可以接收到3個不同的信標數據包,這樣可以保證無論節點如何分布均可進行定位[22]。前面說明,信標的通信范圍在二維平面上是一個圓,那么部署區域的任意子區域都需要被至少3個圓覆蓋。圖1為三重覆蓋問題與初始覆蓋軌跡圖,對于中間的圓,所有子區域都被3個圓覆蓋,這樣這個圓就達到了三重覆蓋,處于這個圓內任何位置的節點均可被定位。

圖1 三重覆蓋問題與初始覆蓋軌跡Fig. 1 3-coverage problem and initial trajectory

圖1中,為保證中間圓的三重覆蓋,每個圓心都要作為一個信標發出點,連接所有圓心,便得到了初始覆蓋軌跡。顯然,這類正六邊形型軌跡的六邊形邊長為R。

2.2.2 步進(Step by step)

初始覆蓋后,位于這個初始覆蓋區域內的節點都被定位了,這樣產生了一批已定位節點。之后,錨節點將選擇向unloc_nb_num最大的已定位的一跳鄰居的方向移動,在該方向上,錨節點移動長度R,移動后的位置將作為下一個覆蓋區域的中心。圖2為步進圖,以圖2(a)為例,在圓1的初始覆蓋之后,它發現了當前覆蓋區域內有一個節點Q0,該節點unloc_nb_num最大。因此沿著的Q0方向,錨點移動到Q1,并且Q1被確定為下一覆蓋區域圓2的中心。

圖2 步進圖Fig. 2 Map of step

在圓2中,與圓1相交區域中的節點已被覆蓋和定位。為了覆蓋圓2的剩余區域,設計了菱形軌跡,菱形邊長也為R。在設計的路徑中,稱正六邊形的中心或菱形的起點為前進點,如圖2(a)中P7和Q1。上一個前進點、當前前進點及其在菱形中的對點三點共線。

與六邊形軌跡類似,菱形的每個頂點也都是一個信標發出點。顯然位于菱形內的所有節點都可以接收到3個信標并定位,而對于圓2中剩余的未覆蓋區域,可以通過結合前后兩個圓中的部分信標來進行定位。這樣,對于圓2也可以實現近似的完全定位。若某個節點收到的信標不足以完成定位,則第1節所述的通信過程保證了該節點附近的一個信標發出點一定在探索列表中,算法保證如果某個探索點對應的節點沒有定位,則該探索點在后面的過程一定會被訪問。

由第1節通信過程可以推出,錨節點在訪問第4個頂點后獲得的信息足以涵蓋所有對當前覆蓋范圍內已定位節點的更新,于是在這個信標發出點處錨節點便可以決定下一步移動方向了。這樣,錨節點可以直接從第4個頂點移動到新的前進點,而無需重訪菱形第一個頂點。以圖2(b)為例,錨節點可以從Q4移動到N1,無需通過Q1中轉。

只要當前覆蓋區域內存在一個unloc_nb_num不為零的已定位節點,本節所述的過程會重復執行下去。在每一步中,都會由當前覆蓋區域內的一個已定位節點確定方向,錨節點沿著該方向移動到下一個前進點,并開始新一步的菱形覆蓋。

2.2.3 跳轉(Jump)

在前進過程中,每一步選擇一個已定位鄰居節點來確定方向,而其他unloc_nb_num不為零的已定位節點則存儲在邊緣列表中。當當前覆蓋區域內沒有unloc_nb_num不為零的節點時,則從邊緣列表中選擇v最小的邊緣點。式(3)中定義了V。

其中Vdist_to_it表示錨節點的當前位置與邊緣點之間的距離,也就是說錨節點這時傾向于選擇未定位鄰居數目多而距離當前位置近的邊緣點。選擇完成后,錨節點將直接移動到所選邊緣點的位置(即(cal(x),cal(y)))并執行前一節的步進過程。這里,邊緣點定義中的NFP被視為上一個前進點的所在位置,用于判斷哪一側尚未訪問,以便計算出新菱形的四個頂點位置,然后可將該邊緣點從邊緣列表中刪除。

2.2.4 重置(Reset)

當錨節點的當前覆蓋范圍內沒有unloc_nb_num不為零的節點并且邊緣列表也為空時,如果探索列表不為空,將從探索列表中選擇(按照距離的遠近,類似2.2.3節dist_to_it)一個探索點。探索點存儲的是距離某個待定位節點最近的信標發出點位置。在這一步中,需要進行一次六邊形覆蓋過程。六邊形軌跡以ref_beacon為中心,可以確保該區域中所有節點完全定位?？梢娺@一步驟包含了探索點選擇過程以及在選定的探索點附近的六邊形覆蓋過程。

這個過程結束后,也從探索列表中刪除所選探索點,然后進入2.2.2節的步進過程。當錨節點的當前覆蓋范圍內沒有unloc_nb_num不為零的節點且邊緣列表與探索列表均為空時,算法結束。算法的偽代碼描述如下:

算法描述

在求解式(2)時,其中兩個信標之間相距太近會使計算誤差過大。為了提高定位精度,可以消除節點接收到的一些相距太近的信標。探索列表保證了每個節點總能接收至少3個合適的定位信標。

定理1對于一個連通的網絡,本算法可以保證完全定位。

證明(反證法)如果算法執行結束,還有一個節點未定位,根據連通性的定義,它一定有一個知道這一信息的鄰居,記為A。當錨節點對A進行定位時,A會將此信息發送給移動錨節點。A要么作為一個邊緣點加入邊緣列表,要么是下一步前進方向。對于前者,邊緣列表不為空,算法會繼續執行;對于后者,這時錨節點在A周圍進行菱形覆蓋,節點可能通過這次覆蓋直接完成定位,否則節點收到的第一個信標發出點位置會被添加到探索列表中,(只有該節點完成定位時,才能從探索列表中移出)探索列表不為空,算法也將繼續執行。在兩種情況下,都與原假設矛盾(即算法執行結束)。證畢。

3 仿真

3.1 設置

本節使用Matlab R2020a對本算法的表現進行驗證。若干個節點分布在1 000 m*1 000 m區域內,通信范圍R為150 m。假設距離的測量值遵循實際距離為平均值,實際距離的2%[23]為標準差的正態分布。節點的數量由網絡的節點度確定。

為方便表述,這里取2.2節4個步驟對應英文單詞的首字母作為本算法的名稱,即ISJR(Initialize,Step by step,Jump,Reset)。與基于靜態路徑的M-Curve[9]、基于虛擬力的VFMS[12]和基于啟發式運動的DREAMS[14]進行了比較。M-Curve使用靜態路徑,后兩種使用動態路徑。定位方法均采用三邊測量法。分別比較了這4種算法的定位率、平均定位誤差、路徑長度以及信標數量。其中定位率為算法結束后已定位節點的數目與總節點數目的比值。定位誤差定義為節點的估計位置與實際位置的歐幾里得距離。平均定位誤差為所有已定位節點的定位誤差的算術平均值。錨節點的路徑長度是指錨節點在整個定位過程中的總移動距離。信標數目指的是定位過程中錨節點需要發出信標的數量。因為在不同的節點度下,不同的算法定位率不同,這對路徑長度及信標節點的數目也造成影響。為部分抵消這種影響,路徑長度及信標節點的數目的仿真結果都除以對應算法的定位率作為該指標的最終值。

圖3 錨節點的生成路徑Fig. 3 Generated path of anchor

3.2 仿真結果與分析

3.2.1 定位率與平均定位誤差

本節比較了C型分布時的定位率與定位誤差,如圖4所示。M-Curve是靜態路徑,對區域進行全局掃描,因此總能夠定位區域內所有節點。ISJR 及另外兩種基于動態路徑的算法受到網絡連通性的影響,在節點度低時無法實現完全定位。

圖4 定位率與定位誤差Fig. 4 Localization ratios and localization errors

在節點度較低時,網絡不連通,包含多個連通的子網。由1.1節的通信過程可知,如果一個待定位節點到某個信標發出點的距離小于通信范圍,那么這個待定位節點就會作為未定位節點與錨節點進行通信,這個信標發出點的位置會作為一個探索點并存入探索列表。在定位一個子網時,可能另一個子網的某個傳感器節點與錨節點的某個信標發出點之間的距離小于通信范圍。這樣,在完成當前子網的定位過程后,探索列表不為空,算法將繼續執行,從而可進一步定位另一個連通的子網。結合定理1,ISJR確保至少可完全定位一個連通的子網,并且有機會通過某個探索點進一步發現另一個子網,因此在定位率方面多次運行的平均表現好于VFMS和DREAMS。

4種算法均采用三邊測量法進行定位計算,定位精度的差異主要源于信標發出點的分布。ISJR、M-Curve和VFMS 在定位誤差方面差距不大。VFMS總是可以使信標分布均勻,有最佳的定位精度,隨之而來的是該算法錨節點移動不夠靈活、路徑較長,這將在下一小節中展示。

3.2.2 路徑長度與信標數量

本節評估了在C 型分布和矩形分布時關于這兩個指標的各個算法的表現。圖5 為C 型與矩形分布時不同節點度下錨節點路徑長度,在C 型分布時,當節點度為5時,定位率較低,VFMS和DREAMS算法運行時的生成樹是一棵包含少數已定位節點的生成樹,樹的高度較低,除以定位率進行的修正不過是對這種短路徑的簡單加和,因而這時表現為路徑短,但這于該算法的實際效果并無意義;當節點度進一步增加時,這些算法定位率接近100%,這時VFMS和DREAMS生成樹變高,造成回溯的成本增加。ISJR 利用邊緣列表和探索列表存儲了需要回溯的節點位置,這部分是直線移動,相比DREAMS和VFMS的逐層回溯,有更高的效率、路徑也更短。M-Curve是靜態路徑,不能避開空白區域,在這種分布下表現不如ISJR和DREAMS。

圖5 C型與矩形分布時不同節點度下錨節點路徑長度Fig. 5 Path lengths under C-type and rectangle distribution

如果傳感器節點均勻分布在矩形區域,對整個區域進行全局掃描是合理且高效的,圖5(b)顯示了此時M-Curve路徑長度最短。矩形分布下這些算法的定位率都接近100%,路徑長度方面本工作算法表現優于VFMS 和DREAMS 而稍差于MCurve,長度約比M-Curve高15%?？梢哉f在傳感器節點矩形內均勻分布的場景,本工作提出的路徑方案提供的結果也是可接受的。

信標數目和錨節點的路徑長度基本上是呈正相關的。圖6顯示了這4種算法完成定位時錨節點所需要發送的信標數量。M-Curve是靜態路徑,在不同的網絡節點分布下需要發出的信標數目固定,路徑上也存在一些冗余信標。VFMS 回溯時需要重復發出信標,同時受網絡拓撲與節點度的影響明顯,有較大起伏,而總體上處于較高的水平。DREAMS采取啟發式移動的策略,需要不斷地發出信標試錯,同時也存在DFT 的回溯過程,因此信標數目較高。在這個指標上,本算法采取動態、靜態路徑相結合的路徑方案,所需的信標數目總能維持在一個較低的水平。

圖6 C型與矩形分布時不同節點度下的信標數目Fig. 6 Number of beacons under C-type and rectangle distribution

4 結語

提出了一種新的錨節點路徑規劃算法用于節點定位。首先設計了錨節點與待定位節點間的通信過程,并分析了通信負載。在定位過程中,錨節點每次前進的方向都是基于局部鄰居信息實時確定的,而對于某個局部區域,算法采用類菱形軌跡或正六邊形軌跡進行覆蓋,這使得一個局部區域中,大部分節點可以被定位,這樣盡可能地避免重復訪問同一區域。同時引入了邊緣點和探索點兩種數據結構,避免了DFT 的回溯,也提高了定位率。本工作的路徑方案是一個動態、靜態路徑相結合的方案:錨節點動態的從一個子區域移動到另一個子區域,這樣可以高效避開空白區域;在子區域內部的靜態路徑(菱形軌跡、六邊形軌跡)提升了算法的穩定性。在未來的工作中,將考慮在實際環境中驗證本工作的算法。