基于方向決策的移動錨節點動態路徑規劃方法*

高美鳳,劉 洋

(江南大學輕工過程先進控制教育部重點實驗室,江蘇 無錫 214122)

無線傳感器網絡WSN(Wireless Sensor Network)是由部署在監測區域內的大量廉價微型傳感器節點組成,集監測、控制和無線通信技術為一體的網絡系統,具有大規模、自組織、動態性等特點[1]。節點定位技術是無線傳感器網絡的關鍵支撐技術之一[2]。對于無線傳感器網絡來說,事件發生的位置是傳感器節點監測信息中的重要組成部分,沒有位置信息的采集信息是沒有任何意義的[3]。

在現有的定位算法中,相對于固定錨節點的定位方法而言,基于移動錨節點的定位方法可以通過錨節點移動路徑的合理規劃,利用虛擬錨節點代替固定錨節點,降低了組網成本,克服了靜態錨節點定位的不足,但移動錨節點的路徑規劃對未知節點的覆蓋率和定位精度影響較大。

文獻[4]中提出了Scan、Hilbert、Double Scan等移動錨節點路徑規劃方法,Hilbert、Double Scan方法有效地解決了Scan路徑規劃方法的共線和定位區域內邊緣節點定位效率低等問題。文獻[5]提出的Z型路徑規劃方法,移動軌跡較短,能耗低,但是邊緣節點由于無法接收到足夠的錨節點信息而導致定位精度不高。以上這些方法屬于靜態路徑規劃方法,適用于未知節點均勻分布的規則區域內,但在未知節點分布不均且不連通的C型或Z型的網絡區域內,靜態路徑規劃方法顯然不夠靈活,錨節點不會隨著網絡中未知節點的分布情況而改變其運行軌跡,比如在空洞和節點密度極小的區域內移動廣播,增大了節點定位成本,并降低了定位效率。文獻[6]利用單個移動錨節點向網絡內最大覆蓋未定位節點區域移動,更好地適應了未知節點大規模隨機分布的網絡定位情況。文獻[7]提出了基于禁忌搜索的動態路徑規劃方法,移動錨節點在移動過程中與周邊節點進行交互動態選取移動方向。但是以上兩種規劃方法對于網絡不連通的不規則區域來說,移動錨節點只根據未知節點密度或禁忌集是無法獲取更優的移動方向,從而造成重復搜索,移動路徑冗長問題。文獻[8]提出了一種在未知節點分布不規則區域內移動錨節點動態路徑規劃方法,利用改進虛擬力的方法決策錨節點的下一步移動方向,克服了未知節點分布不均造成的路徑冗長問題,但是對未知節點的覆蓋率較低。為了進一步提高不規則區域內未知節點覆蓋率較低的問題,文獻[9]提出了一種MAHA(Max Average Hops based Algorithm)路徑規劃算法,采用一個移動節點攜帶4個輔助錨節點根據最大平均跳數進行方向決策,相比于上述路徑規劃方法,不僅提高了未知節點定位覆蓋率,還有效地降低了未知節點的定位誤差,但是該方法使網絡內移動錨節點廣播數據包的數量增加,增大了網絡的通信能耗。

針對以上問題,本文采用單個移動錨節點在節點分布不均且不連通的不規則區域內移動,設計了一種基于方向決策的移動錨節點動態路徑規劃方法CWDP(Dynamic Path Planning Based on Orientation Decision-Classed Weighted)。在該算法中,首先未知節點根據連通度閾值對自身進行分級處理;接著移動錨節點進入網絡區域后,根據通信范圍內未知節點的反饋信息,再利用分級權重系數實時決策下一目標的移動方向。最后仿真結果表明該方法能有效地提高未知節點的定位覆蓋率和降低定位誤差。

1 基于方向決策的移動錨節點動態路徑規劃方法

1.1 錨節點移動模型

為了能夠獲取不同方向的未知節點信息,移動錨節點采用3個定向接收天線[10]和一個全向發射天線,從而接收來自3個方向的節點信息。每個定向天線所能輻射的角度為120°。利用功率控制技術,使移動錨節點可以在更大范圍內廣播信息包。移動錨節點定向天線分配圖如圖1所示,其中移動錨節點的通信圓被3個定向天線平分成面積相等的扇形區域Ⅰ、Ⅱ和Ⅲ。

圖1 移動錨節點定向天線分配圖

1.2 節點分級機制

為了確定網絡內未知節點的分布情況,本文引入了分級機制,該機制的基本思想是:首先在移動錨節點未進入未知區域定位之前,區域內的未知節點需要相互通信以確定自身級別。設節點通信半徑為R,每一個節點記錄周圍通信范圍內的未知節點的id并計算各未知節點的連通度值。未知節點k的設定級別閾值公式為:

(1)

式中:p為節點k通信范圍內的鄰居節點個數,Cq為節點k鄰居節點q的連通度值。

其中,當未知節點i接收到移動錨節點廣播的 3個數據包后,則該節點的定位響應系數Ki=1,否則Ki=0。

1.3 節點分級權重系數

移動錨節點利用定向天線獲取各區域內未知節點的信息來為下一步移動方向做出決策,路徑方向選取主要依靠周邊未知節點的個數。為了確保移動錨節點向節點密度大的區域移動,不能僅僅依靠鄰居未知節點數量,需進一步考慮后續移動中未知節點的遍歷問題,使移動錨節點選取最優方向移動。在確定移動錨節點當前位置的節點密度同時,考慮到每一次移動后使其盡可能靠向連通度大的可繼續“發展”區域,更大限度的提高未知節點的定位覆蓋率,進而減小定位誤差。

移動錨節點對通信范圍內的未知節點進行區域辨別并記錄未知節點反饋的定位響應系數,計算各區域內節點分級權重系數,節點分級權重系數計算公式為:

(2)

未知節點需要3個虛擬錨節點進行自我定位,由于在一個圓的所有外切多邊形中,正多邊形的面積最小,所以虛擬錨節點構成正三角形時,未知節點的定位誤差最小。因此,移動錨節點在任意時刻以60度倍角進行方向選擇。當移動錨節點處于當前位置時,3個定向天線通過接收到的未知節點的響應個數,根據式(2)計算得到3個區域的節點分級權重系數wi(i=1,2,3),移動錨節點依據以下移動方向規則進行移動。

w1>w2且w2>w3,移動方向為60°;

w1=w2且w2>w3,移動方向為120°;

w2>w3且w2>w1,移動方向為180°;

w2=w3且w2>w1,移動方向為240°;

w3>w1且w3>w2,移動方向為300°;

w1=w3且w1>w2,移動方向為360°;

w1=w2=w3≠0,移動方向為隨機選擇方向。

1.4 移動路徑規劃方法步驟

Step 1 在分布不均且不連通的C型或Z型區域內,節點根據通信范圍內總鄰居節點的連通度平均值為閾值,利用式(1)進行自身分級處理;

Step 2 移動錨節點轉入定位模式,并廣播自身位置數據包。ID表示錨節點的依次移動位置序列號。S_CON代表功率控制器所處情況,通信半徑為R時,S_CON=1,即定位模式,移動步長為R;當移動錨節點處于空洞區,調節發射功率,通信半徑為2R時,S_CON=0,即搜索模式,移動步長為2R。POS_x和POS_y分別表示移動錨節點當前位置的經緯度值;

IDS_CONPOS_xPOS_y

Step 3 未知節點接收移動錨節點廣播的數據包,并將其進行存儲;

Step 4 未知節點接收到3個移動錨節點數據包后,進行自我定位,并向錨節點發送定位響應信息數據包K=1,且不再接收錨節點信息包;

Step 5 移動錨節點利用3個定向天線對節點進行區域辨別并記錄未知節點反饋的定位響應系數,利用式(2)計算各區域內節點分級權重系數,利用節點分級權重系數對下一步移動方向進行決策,按照 Step 8 執行。若分級權重系數均為0時,則按照Step 6或Step 7重新決策下一步移動方向,再執行Step 8;

Step 6 移動錨節點在運行過程中,為避免下一目標位置處于空洞或陷入已遍歷區域,設置一個后退鏈表,存儲方向決策階段具有次大分級權重系數的目標位置。當移動錨節點到達當前計算的位置后,發現該處為空洞或已遍歷區域,則查找后退鏈表,選擇最近的未遍歷位置作為新的移動目標,并刪除該位置[11]。可以不斷重復后退,直到跳出已經充分遍歷的區域;

Step 7 移動錨節點進入節點不連通區域,即通信范圍內接收不到未知節點信息,移動錨節點轉入搜索模式,調節功率控制器增大為兩倍的發射功率,若仍接收不到未知節點信息,則移動錨節點采取自救隨機移動;

Step 8 移動錨節點遍歷整個區域后,未完成定位的未知節點利用已定位未知節點進行二次定位。

2 仿真分析

為了驗證CWDP動態移動路徑規劃方法的性能,本文利用MATLAB仿真工具對其進行仿真,并與MAHA方法進行路徑性能的比較分析。

2.1 仿真實驗相關參數設置

本實驗中,設定傳感器網絡區域模型為100 m×100 m的C型和Z型不規則拓撲形狀,未知節點隨機分布,未知節點的數量為200個。考慮到無線傳感器網絡環境的復雜性,采用以下信號傳輸損耗模型[12]:

(3)

式中:PT表示發送信號的強度;PL(do)表示在單位距離do上的路徑損耗;η表示路徑衰減因子,其易受環境影響,一般取值范圍在2～4之間;d為未知節點到錨節點間的距離,一般情況下do取為1 m;Xσ表示正態隨機變量,標準差為σ。根據一般情況,仿真中選擇的參數設置為:PL(do)=55 dBm,PT=-5 dBm,η=4(室外開闊地),Xσ的均值為0且方差為5。為了保證實驗結果的可靠性,實驗結果是在50次獨立實驗得出的平均值。

圖3 Z型網絡下移動路徑

2.2 路徑仿真分析

對于CWDP動態移動路徑規劃方法,首先要判斷該方法是否適配C型和Z型網絡,這里設置節點的通信半徑R為10 m,仿真結果如圖2和圖3所示。

圖2 C型網絡下移動路徑

圖中三角形表示錨節點移動過程中廣播信息包的位置,實心圓代表錨節點移動后成功定位的未知節點,空心圓表示移動錨節點一次遍歷后,未能成功定位的未知節點。

通過仿真結果圖可以看出,本文所提出的動態移動路徑規劃方法CWDP可以對C型和Z型網絡內未知節點取得了良好的覆蓋效果。移動過程整體遵循等邊三角形的最優原理,確保未知節點盡可能地接收到3個移動錨節點廣播的定位信息包。有效地避免了無節點或極少未知節點分布區域的遍歷,節約了廣播通信及冗余移動帶來的多余能量損耗。

2.3 仿真對比分析

2.3.1 未知節點覆蓋率與通信半徑R的關系

如圖4所示,在C型或Z型區域內,隨著通信半徑的增加,CWDP和MAHA兩種方法的節點覆蓋率都逐漸遞增。在通信半徑為10 m時,C型區域內CWDP和MAHA的節點覆蓋率分別達到了98.40%和95.70%,Z型區域內CWDP和MAHA的節點覆蓋率分別為98.00%和89.90%。可見,CWDP的未知節點覆蓋率要明顯好于對比方法MAHA。這是由于CWDP方法中移動錨節點在進行方向決策時,可以進一步選取節點密度較大且一次移動后盡可能靠向連通度大的可繼續“發展”區域,對未知節點達到更好的覆蓋效果。另外路徑移動遵循三角形最優原理,極大地消除了虛擬錨節點的共線問題。所以,節點覆蓋率便隨之增加。

圖4 通信半徑對未知節點定位覆蓋率的影響

2.3.2 虛擬錨節點個數與通信半徑R的關系

表1中是C型和Z型區域內移動錨節點的廣播位置數,MAHA采用一個移動節點攜帶4個錨節點的移動模型,CWDP則采用一個移動錨節點,節約了硬件成本。在CWDP的移動步長和MAHA的移動步長相當時,CWDP減少了大約一半以上的虛擬錨節點個數,大幅度地降低了錨節點通信廣播所帶來的能耗,延長了網絡的生命周期。

表1 C型Z型區域內不同通信半徑下的錨節點廣播位置數

2.3.3 未知節點定位誤差與通信半徑R的關系

兩種移動路徑規劃方法均采用加權質心定位算法,在不同通信半徑的情況下,比較其平均定位誤差。

從圖5中可以發現,無論在C型和Z型網絡,隨著通信半徑的增大,兩種移動路徑規劃方法的平均定位誤差都在逐漸增大。因為兩種方法的移動步長均和通信半徑有關,通信半徑越大,定位區域內虛擬錨節點越少,導致平均定位誤差增大。以C型為例,CWDP的定位誤差在1.606 1 m到2.661 4 m間變化,MAHA的定位誤差在5.206 1 m到7.990 2 m間變化,CWDP的平均定位誤差要明顯低于MAHA的平均定位誤差。另外,CWDP的規劃方法的平均定位誤差曲線在兩種網絡區域內相近,并未受到不同拓撲結構分布的網絡影響。所以在CWDP移動路徑規劃下,移動錨節點對網絡內未知節點的定位效果更好。

圖5 通信半徑對未知節點平均定位誤差的影響

3 結束語

本文提出了一種基于方向決策的移動錨節點動態路徑規劃方法,利用網絡內的未知節點進行分級處理,移動錨節點根據通信范圍內未知節點的反饋信息,再利用分級權重系數實時決策下一目標的移動方向。仿真結果表明,所提出的方法有效地提高了網絡內未知節點的定位覆蓋率、降低了平均定位誤差,并節約了定位成本。但是本文只是對路徑規劃進行研究,沒有更深入的研究提高定位精度的算法,所以下一階段是對定位算法進一步研究。

參考文獻:

[1] 余木琪,鄧平. 一種基于CKF的無線傳感器網絡分布式定位算法[J]. 傳感技術學報,2015,28(7):1041-1045.

[2] 鮑可進,王偉. 一種單移動錨節點的無線傳感器網絡定位方法[J]. 計算機應用研究,2010,27(4):1452-1454.

[3] 劉震宇,王驥猛. 一種改進的基于定向天線的移動傳感器網絡定位算法[J]. 傳感技術學報,2017,30(3):456-462.

[4] Dimitrios Koutsonikolas,Saumitra M Das,Y Charlie Hu. Path Planning of Mobile Landmarks for Localization in Wireless Sensor Networks[J]. Computer Communications,2007(30):2577-2592.

[5] Javad Rezazadeh,Marjan Moradi,Abdul Samad Ismail,et al. Superior Path Planning Mechanism for Mobile Beacon-Assisted Localization in Wireless Sensor Networks[J]. IEEE Sensor Journal,2014,14(9):3052-3064.

[6] 劉亞輝,徐建波. 無線傳感器網絡節點定位的移動信標節點路徑規劃[J]. 傳感技術學報,2010,23(6):873-878.

[7] 殷文正,姜衛東,陶金. 基于禁忌搜索算法的AUV動態路徑規劃策略[J]. 南京大學學報(自然科學),2017,53(1):144-150.

[8] Feng Geng,Shengjun Xue. Mobile Beacon Node Path Scheme in Arbitrary Region for Wireless Sensor Networks[C]//2011 International Conference on Electronic and Mechanical Engineering and Information Technology. IEEE,2011:12-14.

[9] Yilun Yang,Linghua Zhang. Dynamic Path Planning of Mobile Beacon for Localization in Wireless Sensor Network[C]//2013 International Conference on Wireless Communications and Signal Processing. IEEE,2013:1-5.

[10] 付琴,劉克中,陳偉,等. 移動信標動態路徑規劃方法研究[J]. 武漢理工大學學報,2012,34(1):133-136.

[11] Wusong Wen,Lu Wang. Path Planning of Mobile Beacon for Localization Based on Distribution of Unknown Nodes[J]. Advanced Materials Research,2013,712-715:1933-1937.

[12] Alippi C,Vanini G. Wirsless Sensor Networks and Radio Localization:A Metrological Analysis of the MICA2 Received Signal Strength Indicator[C]//Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks. IEEE,2004:572-582.