徐 萍,何加銘,謝志軍,曾興斌
(寧波大學(xué)信息科學(xué)與工程學(xué)院,浙江寧波315211)
在構(gòu)建無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSNs)時(shí),覆蓋問(wèn)題是衡量網(wǎng)絡(luò)的QoS指標(biāo)之一,可以看作是傳感網(wǎng)絡(luò)在節(jié)點(diǎn)能量、計(jì)算處理能力等資源受限的情況下,通過(guò)放置節(jié)點(diǎn)和喚醒/休眠節(jié)點(diǎn)等手段,從而獲得更好的QoS。傳感器節(jié)點(diǎn)構(gòu)成的WSNs在無(wú)人監(jiān)管的情況下,通過(guò)傳感器節(jié)點(diǎn)之間的協(xié)同工作實(shí)現(xiàn)監(jiān)測(cè)和采集各種環(huán)境或監(jiān)測(cè)對(duì)象的相關(guān)信息,并將處理后的數(shù)據(jù)傳送給基站。除此之外,WSNs中通常節(jié)點(diǎn)布設(shè)密集,如果讓所有節(jié)點(diǎn)都工作,則會(huì)在數(shù)據(jù)收集時(shí)存在高度相關(guān)和冗余,甚至在傳送數(shù)據(jù)時(shí)發(fā)生沖突。移動(dòng)目標(biāo)監(jiān)測(cè)是WSNs的重要應(yīng)用之一[1]。
一種典型的移動(dòng)目標(biāo)監(jiān)測(cè)的調(diào)度策略是基于分簇策略的跟蹤算法[2,3]。假設(shè)WSNs是由特定或者隨機(jī)部署在監(jiān)測(cè)區(qū)域內(nèi)的簇首和普通節(jié)點(diǎn)組成,簇首負(fù)責(zé)接收處理節(jié)點(diǎn)發(fā)來(lái)的數(shù)據(jù),然后轉(zhuǎn)發(fā)給基站;普通節(jié)點(diǎn)負(fù)責(zé)感知數(shù)據(jù)。然而活躍節(jié)點(diǎn)數(shù)直接影響網(wǎng)絡(luò)能量的消耗。文獻(xiàn)[4]提出基于自適應(yīng)目標(biāo)跟蹤算法,利用最優(yōu)選擇機(jī)制和動(dòng)態(tài)分簇方式確定活躍節(jié)點(diǎn)。文獻(xiàn)[5]最大熵原理,先把部署在網(wǎng)絡(luò)中的靜態(tài)節(jié)點(diǎn)分簇,然后根據(jù)監(jiān)測(cè)環(huán)境的需要加入移動(dòng)節(jié)點(diǎn),從而降低網(wǎng)絡(luò)的不確定性,增加節(jié)點(diǎn)的可選擇性。文獻(xiàn)[6]利用節(jié)點(diǎn)的聯(lián)合概率探測(cè)模型,選擇探測(cè)概率大的節(jié)點(diǎn)作為任務(wù)節(jié)點(diǎn)。然而當(dāng)目標(biāo)在局部做重復(fù)運(yùn)動(dòng),或者更為復(fù)雜的運(yùn)動(dòng)時(shí),目標(biāo)在局部區(qū)域內(nèi)逗留的時(shí)間很長(zhǎng),這樣局部能量就會(huì)迅速消耗,最終導(dǎo)致對(duì)目標(biāo)漏檢。
本文根據(jù)以往節(jié)點(diǎn)的調(diào)度記錄和剩余能量、目標(biāo)軌跡以及回退機(jī)制來(lái)提高網(wǎng)絡(luò)覆蓋度和監(jiān)測(cè)概率,借助貪心算法優(yōu)化網(wǎng)絡(luò)資源分配,使之更好地完成對(duì)移動(dòng)目標(biāo)的監(jiān)測(cè)任務(wù)。在WSNs中,大量節(jié)點(diǎn)隨機(jī)分布在目標(biāo)區(qū)域內(nèi),受節(jié)點(diǎn)自身?xiàng)l件限制,若所有節(jié)點(diǎn)同時(shí)工作,不僅能量消耗過(guò)快,而且降低了網(wǎng)絡(luò)的使用壽命。本文研究如何通過(guò)模糊移動(dòng)軌跡[7]策略解決喚醒調(diào)度算法中某些節(jié)點(diǎn)過(guò)早死亡和移動(dòng)物體監(jiān)測(cè)過(guò)程中盲點(diǎn)問(wèn)題。主要研究包括:構(gòu)建基于隨機(jī)均勻分布節(jié)點(diǎn)模型,提出模糊移動(dòng)軌跡建立方案,提出一種基于模糊移動(dòng)軌跡策略的節(jié)點(diǎn)調(diào)度(move trajectory PEAS,M-PEAS)算法。實(shí)驗(yàn)證明:該算法提高了節(jié)點(diǎn)的監(jiān)測(cè)概率,降低了能耗。
采用輪換“活躍”和“休眠”節(jié)點(diǎn)的覆蓋控制協(xié)議可以有效延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間,每個(gè)周期由一個(gè)自調(diào)度階段和一個(gè)工作階段組成。在自調(diào)度階段:各節(jié)點(diǎn)首先向傳感半徑內(nèi)鄰居節(jié)點(diǎn)廣播通告消息,其中包括節(jié)點(diǎn)ID和位置。節(jié)點(diǎn)檢查自身傳感任務(wù)是否可由鄰居節(jié)點(diǎn)完成,可替代的節(jié)點(diǎn)返回一條狀態(tài)通告消息,之后進(jìn)入“休眠狀態(tài)”,需要繼續(xù)工作的節(jié)點(diǎn)執(zhí)行傳感任務(wù),在判斷節(jié)點(diǎn)是否可以休眠時(shí),如果相鄰節(jié)點(diǎn)同時(shí)檢查到自身的傳感任務(wù)可由對(duì)方完成并同時(shí)進(jìn)入“休眠狀態(tài)”,就會(huì)出現(xiàn)監(jiān)測(cè)的“盲點(diǎn)”[8]。
1)監(jiān)測(cè)概率
一般由于傳感器節(jié)點(diǎn)的理論或物理特性不同,應(yīng)用場(chǎng)景對(duì)監(jiān)測(cè)要求不同,對(duì)監(jiān)測(cè)性能要求不同。根據(jù)傳感模型得到監(jiān)測(cè)概率的分布,不同傳感器的傳感模型有所差異,但感知能力隨距離的增長(zhǎng)而降低的這一基本特點(diǎn)是保持不變的。PEAS算法節(jié)點(diǎn)密度公式
其中,λ為節(jié)點(diǎn)的監(jiān)測(cè)概率,ts為節(jié)點(diǎn)睡眠周期。傳感器節(jié)點(diǎn)s在q點(diǎn)的感知模型定義如下[9]
其中,dis(s,q)為節(jié)點(diǎn)s與q在二維空間上的歐氏距離,α>0為感知系數(shù),k=1,2為距離影響系數(shù)。根據(jù)感應(yīng)模型,可以得出節(jié)點(diǎn)s對(duì)q點(diǎn)的發(fā)現(xiàn)概率p(d)
其中,d=dis(s,q),r為感知半徑,R 為通信半徑,為保證節(jié)點(diǎn)間正常通信,設(shè)定R>2r。
2)模糊軌跡
設(shè)移動(dòng)目標(biāo)物體從節(jié)點(diǎn)A移動(dòng)到節(jié)點(diǎn)B的坐標(biāo)分別為A(x1,y1),B(x2,y2),根據(jù)兩節(jié)點(diǎn)之間的歐氏距離和監(jiān)測(cè)時(shí)間,得出移動(dòng)目標(biāo)的速度函數(shù)
方位角函數(shù)
其中,φab為A至B直線方向參考方向。當(dāng)運(yùn)動(dòng)物體從節(jié)點(diǎn)A移至節(jié)點(diǎn)B時(shí),節(jié)點(diǎn)B計(jì)算速度估計(jì)函數(shù)f(vB)和方位角估計(jì)函數(shù)f(Bφ)定義如下
其中,Δv,Δθ為速度和方位角的偏差量。
3)回退機(jī)制
節(jié)點(diǎn)在自調(diào)度階段檢查之前執(zhí)行一個(gè)回退機(jī)制:每個(gè)節(jié)點(diǎn)在一個(gè)隨機(jī)產(chǎn)生的Td時(shí)間之后再開(kāi)始檢查工作。在本文中Td時(shí)間根據(jù)物體移動(dòng)軌跡、速度、節(jié)點(diǎn)間距離決定。此外,回退時(shí)間還可以根據(jù)周圍節(jié)點(diǎn)密度而計(jì)算,這樣就可以有效地控制網(wǎng)絡(luò)“活躍”節(jié)點(diǎn)的密度,為了進(jìn)一步避免“盲點(diǎn)”的出現(xiàn),每個(gè)節(jié)點(diǎn)在進(jìn)入“休眠狀態(tài)”之前還將等待3 s時(shí)間來(lái)監(jiān)聽(tīng)鄰居節(jié)點(diǎn)的狀態(tài)更新。
4)模糊移動(dòng)軌跡的優(yōu)劣評(píng)價(jià)標(biāo)準(zhǔn)
模糊移動(dòng)軌跡的優(yōu)劣評(píng)價(jià)標(biāo)準(zhǔn):移動(dòng)目標(biāo)在運(yùn)動(dòng)的情況下,在傳感區(qū)域內(nèi)的時(shí)間越長(zhǎng),被監(jiān)測(cè)到的概率越大,對(duì)于目標(biāo)在監(jiān)測(cè)區(qū)域內(nèi)監(jiān)測(cè)量的計(jì)算,移動(dòng)目標(biāo)在監(jiān)測(cè)區(qū)域內(nèi)的責(zé)任感知節(jié)點(diǎn)有影響,第一,移動(dòng)目標(biāo)在區(qū)間[t1,t2]在二維軌跡上監(jiān)測(cè)量[10]為
式(7)表示目標(biāo)移動(dòng)過(guò)程中責(zé)任節(jié)點(diǎn)對(duì)其感知數(shù)量,即監(jiān)測(cè)量越大越好。模糊軌跡監(jiān)測(cè)的長(zhǎng)度與節(jié)點(diǎn)監(jiān)測(cè)狀態(tài)有關(guān);第二,目標(biāo)在移動(dòng)過(guò)程中被監(jiān)測(cè)的概率越大,漏檢的可能性減少。同時(shí)喚醒機(jī)制綜合考慮剩余能量,當(dāng)節(jié)點(diǎn)剩余能量為初始能量的1/3時(shí),節(jié)點(diǎn)自動(dòng)轉(zhuǎn)換成中繼節(jié)點(diǎn),只負(fù)責(zé)節(jié)點(diǎn)信息的傳遞工作,減少因節(jié)點(diǎn)失效而產(chǎn)生的盲點(diǎn)問(wèn)題。
M-PEAS節(jié)點(diǎn)調(diào)度策略是一種基于探測(cè)的節(jié)點(diǎn)密度控制協(xié)議PEAS的分布式控制算法,其中,運(yùn)動(dòng)物體模糊移動(dòng)軌跡、速度和方位角函數(shù)推算是此算法的關(guān)鍵。節(jié)點(diǎn)調(diào)度休眠規(guī)則包括2個(gè)方面:首先,檢查節(jié)點(diǎn)在各自責(zé)任區(qū)是否滿足保證區(qū)域覆蓋;其次,根據(jù)估計(jì)值設(shè)定節(jié)點(diǎn)喚醒函數(shù)。
1)模型的分解
運(yùn)動(dòng)物體從節(jié)點(diǎn)A運(yùn)動(dòng)至節(jié)點(diǎn)C,而B(niǎo),D,E,F(xiàn)是其鄰居節(jié)點(diǎn),如圖1所示,各節(jié)點(diǎn)具有相同的屬性,節(jié)點(diǎn)C根據(jù)節(jié)點(diǎn)A獲取物體移動(dòng)的速度、方位角、距離等信息推算運(yùn)動(dòng)物體本輪的軌跡,計(jì)算到達(dá)自身監(jiān)測(cè)區(qū)域概率和時(shí)間。由于各節(jié)點(diǎn)具有相同的時(shí)鐘,同時(shí)物體的運(yùn)動(dòng)具有很強(qiáng)的關(guān)聯(lián)性,在短時(shí)間內(nèi)其速度和方向不會(huì)發(fā)生太大的變化。節(jié)點(diǎn)C根據(jù)節(jié)點(diǎn)A的信息和兩點(diǎn)間的距離,確定速度估計(jì)函數(shù)F(v),方位角函數(shù)φ(θ),如圖2所示,定義與參考方向x軸方向的夾角為方位角。通過(guò)這2個(gè)函數(shù)推算物體的運(yùn)動(dòng)軌跡y,休眠節(jié)點(diǎn)根據(jù)信息確定到達(dá)本區(qū)域的概率,將此信息發(fā)送給鄰居節(jié)點(diǎn),通過(guò)比對(duì)接收到的信息分析數(shù)據(jù)。關(guān)聯(lián)度最小的節(jié)點(diǎn)采用休眠方式;若有幾個(gè)節(jié)點(diǎn)同時(shí)處于方位角之內(nèi),且監(jiān)測(cè)區(qū)域有重疊,根據(jù)節(jié)點(diǎn)的覆蓋范圍和節(jié)點(diǎn)的剩余能量綜合考慮節(jié)點(diǎn)的工作狀態(tài)。通常,設(shè)物體從節(jié)點(diǎn)A運(yùn)動(dòng)到節(jié)點(diǎn)B,根據(jù)RSSI技術(shù)獲得兩點(diǎn)的距離,估計(jì)速度函數(shù)計(jì)算物體到達(dá)上限時(shí)間令T為PEAS休眠節(jié)點(diǎn)喚醒周期,則,當(dāng)節(jié)點(diǎn)C收到節(jié)點(diǎn)A的感知信號(hào),經(jīng)過(guò)mT時(shí)間,節(jié)點(diǎn)C進(jìn)入節(jié)點(diǎn)監(jiān)聽(tīng)狀態(tài),并持續(xù)(m-n)T時(shí)間。
圖1 目標(biāo)物體移動(dòng)原理圖Fig 1 Mobile principle diagram of the target object
圖2 移動(dòng)目標(biāo)方位角示意圖Fig 2 Azimuth diagram of moving target
若多個(gè)目標(biāo)同時(shí)進(jìn)入節(jié)點(diǎn)監(jiān)測(cè)區(qū)域,建立分時(shí)隙偵聽(tīng),避免過(guò)多節(jié)點(diǎn)數(shù)據(jù)冗余,減少節(jié)點(diǎn)能量消耗。
2)模糊移動(dòng)軌跡分析
在傳感區(qū)域S內(nèi),起始節(jié)點(diǎn)Pt的坐標(biāo)為(0,0),已知終點(diǎn)S,節(jié)點(diǎn)A首先監(jiān)測(cè)到移動(dòng)目標(biāo)O,記錄其到達(dá)時(shí)間t1,根據(jù)式(5)、式(6)得出速度和方位角函數(shù)。已知鄰居節(jié)點(diǎn)位置信息,鄰居節(jié)點(diǎn)收到B發(fā)送的監(jiān)測(cè)信息,計(jì)算物體到達(dá)本監(jiān)測(cè)區(qū)域的時(shí)間和概率P(b)=P(d)×(1+p),其中,p是根據(jù)模糊移動(dòng)軌跡估算的預(yù)測(cè)概率[11]。同時(shí)將處理后的信息反饋給周邊鄰居節(jié)點(diǎn),鄰居節(jié)點(diǎn)接收到處理信息后通過(guò)比對(duì)自身監(jiān)測(cè)區(qū)域的概率、剩余能量、目前狀態(tài),決定自身的狀態(tài)(休眠狀態(tài)、監(jiān)聽(tīng)狀態(tài)、加強(qiáng)監(jiān)聽(tīng)狀態(tài))。為防止出現(xiàn)節(jié)點(diǎn)同時(shí)進(jìn)入休眠狀態(tài)而出現(xiàn)的盲點(diǎn)問(wèn)題,本策略采用節(jié)點(diǎn)回退機(jī)制,回退時(shí)間0~t,根據(jù)移動(dòng)目標(biāo)與節(jié)點(diǎn)本身距離而定,設(shè)定t等于距離,B,C,F(xiàn) 節(jié)點(diǎn)進(jìn)入覆蓋探測(cè)狀態(tài)的時(shí)間不同,避免了監(jiān)測(cè)重疊區(qū)域出現(xiàn)覆蓋漏洞的現(xiàn)象。
3)算法描述
輸入傳感器節(jié)點(diǎn)集 S={s1,s2,s3,…,sn},目標(biāo)監(jiān)測(cè)區(qū)域 A,移動(dòng)物體目標(biāo)集 L={l1,l2,l3…,lm},監(jiān)聽(tīng)節(jié)點(diǎn)集 Q={q1,q2,q3…,ql},休眠節(jié)點(diǎn)集 W={w1,w2,w3…,wn-l},輸出實(shí)現(xiàn)節(jié)點(diǎn)之間覆蓋監(jiān)測(cè)區(qū)域責(zé)任節(jié)點(diǎn)集G。
設(shè)WSNs的節(jié)點(diǎn)隨機(jī)均勻分布,節(jié)點(diǎn)密度服從式(1)分布,節(jié)點(diǎn)的感知半徑為r,物體在網(wǎng)絡(luò)內(nèi)的運(yùn)動(dòng)路徑長(zhǎng)度為L(zhǎng),責(zé)任節(jié)點(diǎn)的感知概率為Ps(i),物體經(jīng)過(guò)的責(zé)任節(jié)點(diǎn)數(shù)為N=(2rL+πr2)f(ts),被責(zé)任節(jié)點(diǎn)感知的節(jié)點(diǎn)數(shù)目,則漏檢概率為,采用模糊移動(dòng)軌跡策略,責(zé)任節(jié)點(diǎn)i對(duì)目標(biāo)的監(jiān)測(cè)感知數(shù):
1)當(dāng)物體恰好在監(jiān)聽(tīng)加強(qiáng)狀態(tài)時(shí)進(jìn)入感知區(qū)域,節(jié)點(diǎn)對(duì)物體采用加強(qiáng)監(jiān)聽(tīng)(此時(shí)的感知概率記為Pes)。
2)采用軌跡分析進(jìn)行檢測(cè),設(shè)節(jié)點(diǎn)對(duì)物體加強(qiáng)監(jiān)聽(tīng)的概率為Pe,物體被節(jié)點(diǎn)感知的數(shù)量滿足
由式(8)可知,若Nes>Ns,即采用模糊移動(dòng)軌跡策略失真率小于PEAS算法。
為了驗(yàn)證本算法的正確性和有效性,初始仿真場(chǎng)景和,下限 t2=相關(guān)參數(shù)設(shè)定如下:選用Matlab作為實(shí)驗(yàn)仿真平臺(tái),初始仿真場(chǎng)景與相關(guān)參數(shù)設(shè)定如下:平面100 m×100 m,1 000個(gè)節(jié)點(diǎn)隨機(jī)分布,r=5 m,R=15 m,λ =1,k=1,節(jié)點(diǎn)初始能量0.5 J,移動(dòng)目標(biāo)速度 v=1 m/s。
仿真1:比較同一場(chǎng)景下,M-PEAS,PEAS算法在網(wǎng)絡(luò)運(yùn)行期間剩余能量變化。
由于M-PEAS算法通過(guò)軌跡、節(jié)點(diǎn)剩余能量設(shè)計(jì)調(diào)度函數(shù),節(jié)點(diǎn)能耗更加均衡。從圖3中可以看出:M-PEAS和PEAS算法在網(wǎng)絡(luò)正常運(yùn)行的不同時(shí)間段的剩余能量百分比。節(jié)點(diǎn)能量隨著時(shí)間不斷地消耗,當(dāng)時(shí)間為130 s時(shí),PEAS算法能量由于某些節(jié)點(diǎn)持續(xù)工作導(dǎo)致節(jié)點(diǎn)失效,整體能量消耗過(guò)大,已經(jīng)小于整體能量的1/3,沒(méi)有很好地考慮能耗的均衡性,導(dǎo)致整個(gè)網(wǎng)絡(luò)過(guò)早處于癱瘓狀態(tài),造成很大的能量浪費(fèi)。
仿真2:選取同上的仿真平臺(tái),分別選取節(jié)點(diǎn)數(shù)100,200,300,400,500,600,700,800,900,1 000 等 10 組數(shù)據(jù)進(jìn)行100次仿真分析比對(duì),其他參數(shù)保持一致。結(jié)果如圖4所示。從中可以看出:在不同節(jié)點(diǎn)數(shù)覆蓋情況下,M-PEAS算法監(jiān)測(cè)概率高于PEAS算法,其原因是,WSNs節(jié)點(diǎn)在工作期間會(huì)出現(xiàn)一部分失效節(jié)點(diǎn),隨著節(jié)點(diǎn)工作變化,PEAS算法中的失效節(jié)點(diǎn)遠(yuǎn)大于M-PEAS算法,同時(shí),采用軌跡分析策略,責(zé)任節(jié)點(diǎn)對(duì)物體的監(jiān)測(cè)概率加強(qiáng)。所以,在具有相同的節(jié)點(diǎn)數(shù)時(shí),M-PEAS的監(jiān)測(cè)概率大于PEAS。
圖4 監(jiān)測(cè)概率對(duì)比圖Fig 4 Comparison diagram of monitoring probability
在WSNs中,節(jié)點(diǎn)覆蓋已成為WSNs研究的一個(gè)重要分支??紤]到節(jié)點(diǎn)自身能量有限,目標(biāo)運(yùn)動(dòng)的復(fù)雜性和隨機(jī)部署的不確定性,在本文中提出一種基于PEAS模糊移動(dòng)軌跡算法。首先,提出了模糊移動(dòng)軌跡策略,構(gòu)建軌跡算法,將節(jié)點(diǎn)調(diào)度問(wèn)題轉(zhuǎn)化成軌跡生成問(wèn)題;然后,基于模糊移動(dòng)軌跡建立節(jié)點(diǎn)調(diào)度函數(shù),仿真實(shí)驗(yàn)表明:此調(diào)度算法能很好解決節(jié)點(diǎn)能耗均衡問(wèn)題;最后,利用貪婪算法關(guān)聯(lián)其自身剩余能量對(duì)策略進(jìn)行優(yōu)化,證明該算法優(yōu)于PEAS算法,提高了網(wǎng)絡(luò)的監(jiān)測(cè)概率,降低了節(jié)點(diǎn)漏檢問(wèn)題,延長(zhǎng)了網(wǎng)絡(luò)生命周期。
[1]Gezici S,Tian Z,Giannakis G,et al.Localization via ultra-wideband radios:A look at positioning aspects for future sensor networks[J].IEEE Signal Processing Magazine,2005,22(4):70-84.
[2]Chen W P,Hou JC,Liu S.Dynamic clustering for acoustic target tracking in wireless sensor networks[J].IEEE Transactions on Mobile Computing,2004,3(3):258-271.
[3]Chuang SC.Survey on target tracking in wireless sensor networks[R].Beijing:Tsinghua University,2005.
[4]Phuong P,Sesh C.Stability and performance of wireless sensor networks during the tracking of dynamic targets[J].Lecture Notes in Electrical Engineering,2011,89:349-362.
[5]Kuang X H,F(xiàn)eng R,Shao H H.A lightweight target tracking scheme using wireless sensor networks[J].Measurement Science and Technology,2008,19:1-7.
[6]Wang X,Ma JJ,Wang S,et al.Distributed energy optimization for target tracking in wireless sensor networks[J].IEEE Transactions on Mobile Computing,2009,9(1):73-86.
[7]Chen A,Kumar S,Lai TH.Local barrier coverage in wireless sensor networks[J].IEEE Trans on Mobile Computing,2010,9(4):491-504.
[8]Adlakha S,Srivastava M.Critical density thresholds for coverage in wireless sensor networks[C]∥Proc of IEEE WCNC’2003,New Orleans,La,USA,2003:1615-1620.
[9]Zhang W Z,Li M L,Wu M Y.An algorithm for target traversing based on local voronoi diagram[J].Journal of Software,2007,18(5):1246-1253.
[10]Saipulla A,Westphal C,Liu B,et al.Barrier caverage of linebased deployed wireless sensor networks[C]∥Proc of the 28th IEEE Conf on Computer Communications,INFOCON 2009,Rio de Janeiro,2009:19-25.
[11]Wang B,Chua K C,Wang W,et al.Worst and best information exposure paths in wireless sensor networks[C]∥International Conference on Mobile Ad Hoc and Sensor Networks,MSN’05,2005:52-62.