高美鳳,劉 洋

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

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

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

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

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

1 基于方向決策的移動錨節(jié)點動態(tài)路徑規(guī)劃方法

1.1 錨節(jié)點移動模型

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

圖1 移動錨節(jié)點定向天線分配圖

1.2 節(jié)點分級機制

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

(1)

式中:p為節(jié)點k通信范圍內(nèi)的鄰居節(jié)點個數(shù),Cq為節(jié)點k鄰居節(jié)點q的連通度值。

其中,當(dāng)未知節(jié)點i接收到移動錨節(jié)點廣播的 3個數(shù)據(jù)包后,則該節(jié)點的定位響應(yīng)系數(shù)Ki=1,否則Ki=0。

1.3 節(jié)點分級權(quán)重系數(shù)

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

移動錨節(jié)點對通信范圍內(nèi)的未知節(jié)點進(jìn)行區(qū)域辨別并記錄未知節(jié)點反饋的定位響應(yīng)系數(shù),計算各區(qū)域內(nèi)節(jié)點分級權(quán)重系數(shù),節(jié)點分級權(quán)重系數(shù)計算公式為:

(2)

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

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 移動路徑規(guī)劃方法步驟

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

Step 2 移動錨節(jié)點轉(zhuǎn)入定位模式,并廣播自身位置數(shù)據(jù)包。ID表示錨節(jié)點的依次移動位置序列號。S_CON代表功率控制器所處情況,通信半徑為R時,S_CON=1,即定位模式,移動步長為R;當(dāng)移動錨節(jié)點處于空洞區(qū),調(diào)節(jié)發(fā)射功率,通信半徑為2R時,S_CON=0,即搜索模式,移動步長為2R。POS_x和POS_y分別表示移動錨節(jié)點當(dāng)前位置的經(jīng)緯度值;

IDS_CONPOS_xPOS_y

Step 3 未知節(jié)點接收移動錨節(jié)點廣播的數(shù)據(jù)包,并將其進(jìn)行存儲;

Step 4 未知節(jié)點接收到3個移動錨節(jié)點數(shù)據(jù)包后,進(jìn)行自我定位,并向錨節(jié)點發(fā)送定位響應(yīng)信息數(shù)據(jù)包K=1,且不再接收錨節(jié)點信息包;

Step 5 移動錨節(jié)點利用3個定向天線對節(jié)點進(jìn)行區(qū)域辨別并記錄未知節(jié)點反饋的定位響應(yīng)系數(shù),利用式(2)計算各區(qū)域內(nèi)節(jié)點分級權(quán)重系數(shù),利用節(jié)點分級權(quán)重系數(shù)對下一步移動方向進(jìn)行決策,按照 Step 8 執(zhí)行。若分級權(quán)重系數(shù)均為0時,則按照Step 6或Step 7重新決策下一步移動方向,再執(zhí)行Step 8;

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

Step 7 移動錨節(jié)點進(jìn)入節(jié)點不連通區(qū)域,即通信范圍內(nèi)接收不到未知節(jié)點信息,移動錨節(jié)點轉(zhuǎn)入搜索模式,調(diào)節(jié)功率控制器增大為兩倍的發(fā)射功率,若仍接收不到未知節(jié)點信息,則移動錨節(jié)點采取自救隨機移動;

Step 8 移動錨節(jié)點遍歷整個區(qū)域后,未完成定位的未知節(jié)點利用已定位未知節(jié)點進(jìn)行二次定位。

2 仿真分析

為了驗證CWDP動態(tài)移動路徑規(guī)劃方法的性能,本文利用MATLAB仿真工具對其進(jìn)行仿真,并與MAHA方法進(jìn)行路徑性能的比較分析。

2.1 仿真實驗相關(guān)參數(shù)設(shè)置

本實驗中,設(shè)定傳感器網(wǎng)絡(luò)區(qū)域模型為100 m×100 m的C型和Z型不規(guī)則拓?fù)湫螤?未知節(jié)點隨機分布,未知節(jié)點的數(shù)量為200個?？紤]到無線傳感器網(wǎng)絡(luò)環(huán)境的復(fù)雜性,采用以下信號傳輸損耗模型[12]:

(3)

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

圖3 Z型網(wǎng)絡(luò)下移動路徑

2.2 路徑仿真分析

對于CWDP動態(tài)移動路徑規(guī)劃方法,首先要判斷該方法是否適配C型和Z型網(wǎng)絡(luò),這里設(shè)置節(jié)點的通信半徑R為10 m,仿真結(jié)果如圖2和圖3所示。

圖2 C型網(wǎng)絡(luò)下移動路徑

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

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

2.3 仿真對比分析

2.3.1 未知節(jié)點覆蓋率與通信半徑R的關(guān)系

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

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

2.3.2 虛擬錨節(jié)點個數(shù)與通信半徑R的關(guān)系

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

表1 C型Z型區(qū)域內(nèi)不同通信半徑下的錨節(jié)點廣播位置數(shù)

2.3.3 未知節(jié)點定位誤差與通信半徑R的關(guān)系

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

從圖5中可以發(fā)現(xiàn),無論在C型和Z型網(wǎng)絡(luò),隨著通信半徑的增大,兩種移動路徑規(guī)劃方法的平均定位誤差都在逐漸增大。因為兩種方法的移動步長均和通信半徑有關(guān),通信半徑越大,定位區(qū)域內(nèi)虛擬錨節(jié)點越少,導(dǎo)致平均定位誤差增大。以C型為例,CWDP的定位誤差在1.606 1 m到2.661 4 m間變化,MAHA的定位誤差在5.206 1 m到7.990 2 m間變化,CWDP的平均定位誤差要明顯低于MAHA的平均定位誤差。另外,CWDP的規(guī)劃方法的平均定位誤差曲線在兩種網(wǎng)絡(luò)區(qū)域內(nèi)相近,并未受到不同拓?fù)浣Y(jié)構(gòu)分布的網(wǎng)絡(luò)影響。所以在CWDP移動路徑規(guī)劃下,移動錨節(jié)點對網(wǎng)絡(luò)內(nèi)未知節(jié)點的定位效果更好。

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

3 結(jié)束語

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

參考文獻(xiàn):

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

[2] 鮑可進(jìn),王偉. 一種單移動錨節(jié)點的無線傳感器網(wǎng)絡(luò)定位方法[J]. 計算機應(yīng)用研究,2010,27(4):1452-1454.

[3] 劉震宇,王驥猛. 一種改進(jìn)的基于定向天線的移動傳感器網(wǎng)絡(luò)定位算法[J]. 傳感技術(shù)學(xué)報,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] 劉亞輝,徐建波. 無線傳感器網(wǎng)絡(luò)節(jié)點定位的移動信標(biāo)節(jié)點路徑規(guī)劃[J]. 傳感技術(shù)學(xué)報,2010,23(6):873-878.

[7] 殷文正,姜衛(wèi)東,陶金. 基于禁忌搜索算法的AUV動態(tài)路徑規(guī)劃策略[J]. 南京大學(xué)學(xué)報(自然科學(xué)),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] 付琴,劉克中,陳偉,等. 移動信標(biāo)動態(tài)路徑規(guī)劃方法研究[J]. 武漢理工大學(xué)學(xué)報,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.