WSN中一種流水式柵欄調(diào)度算法的研究*

戴光麟,楊志凱,周賢年,陳立建,毛科技

(浙江工業(yè)大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,杭州 310032)

無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Networks)被多個行業(yè)廣泛使用[1-2],在這當(dāng)中,無線傳感器網(wǎng)絡(luò)柵欄覆蓋大部分被應(yīng)用于入侵者檢測。如在環(huán)保方面,可檢測污染物的擴(kuò)散情況。在國防應(yīng)用中,可對越境者進(jìn)行自動化探測。在林業(yè)保護(hù)方面,可預(yù)警、并且對火災(zāi)蔓延情況進(jìn)行探測等[3-4],但同時,硬件設(shè)施方面對發(fā)展在很大程度上限制了傳感器節(jié)點的使用。因此通過軟件算法來延長傳感器網(wǎng)絡(luò)的生存時間成為了非常關(guān)鍵的研究問題。

為了延長柵欄的生存時間,目前主要通過研究三大塊方向來實現(xiàn)。在柵欄調(diào)度方面,如Kumar等人提出了Optimal Sleep-Wakeup調(diào)度算法,該算法通過分析柵欄的生存時間,組合成若干組k-柵欄,使得柵欄的能量被充分利用,從而達(dá)到k-柵欄生存時間最大化[5]。Kim K S等人提出了Duty-Cycle Scheme調(diào)度算法,該算法通過輪流調(diào)度多條柵欄,使得在保證一定監(jiān)測率的情況下延長了網(wǎng)絡(luò)的生存時間[6-7]。文獻(xiàn)[8-13]等都研究了在不同情況下的延長柵欄生存時間的方法。從柵欄的加強(qiáng)和修復(fù)方法來看,其主要原理是使死亡的柵欄重新工作。Anwar Saipulla等人提出一種二階段算法修補(bǔ)柵欄間隙法。第1階段,FIND-GAPS算法查找柵欄間隙,第2階段MEND-GAPS算法修復(fù)柵欄[14]。Xu B等人研究分析入侵的歷史數(shù)據(jù),分析得到柵欄中的易受攻擊點,然后通過移動節(jié)點來加強(qiáng)這些易受攻擊的位置的柵欄,從而防止因為某些節(jié)點能量消耗過多而導(dǎo)致柵欄提早死亡[15]。Park T等人提出了一種尋找柵欄瓶頸區(qū)域,并在瓶頸區(qū)域內(nèi)增加傳感器節(jié)點的算法,從而延長了傳感器網(wǎng)絡(luò)的生存時間[16]。

由于不同WSN柵欄應(yīng)用中對檢測率的需求不同,本文提出了一種流水式的柵欄調(diào)度算法FSA(Flow-style Scheduling Algorithm),首先將柵欄均勻分割為些許子?xùn)艡?將子?xùn)艡谘h(huán)激活,形成一種流水式工作狀態(tài),通過被激活狀態(tài)的子?xùn)艡趤頇z測試圖通過柵欄的入侵者。該算法在確保一定檢測率的情況下實現(xiàn)柵欄生存時間的大幅度提高。

1 流水式柵欄調(diào)度算法

首先描述下要實現(xiàn)本文算法所需要的一些條件,本文假設(shè)柵欄已經(jīng)由文獻(xiàn)[17]等柵欄構(gòu)建方法構(gòu)建完成,然后進(jìn)行算法描述。

1.1 相關(guān)條件

要實現(xiàn)本文算法的相關(guān)條件有四條:

條件1 傳感器網(wǎng)絡(luò)中節(jié)點同構(gòu),節(jié)點能量,感知半徑等都相同。且節(jié)點只有處于激活狀態(tài)時才會消耗能量,節(jié)點狀態(tài)切換消耗的能量忽略不計。

條件2 某條子?xùn)艡诒O(jiān)測到入侵者后可直接與Sink節(jié)點通訊,不需要經(jīng)過其他節(jié)點轉(zhuǎn)發(fā),且傳感器節(jié)點可獲取自身的位置信息(坐標(biāo))。

條件3 子?xùn)艡诓恍枰獠啃盘?直接通過節(jié)點內(nèi)部的定時器設(shè)置喚醒與休眠狀態(tài)的切換。

條件4 不考慮入侵者實際體積,將入侵者視為一個點。

1.2 調(diào)度算法

將柵欄分割,如圖1所示,將柵欄均勻分割為α條子?xùn)艡?。同一時刻只有唯一子?xùn)艡谔幱诠ぷ鳡顟B(tài),其他處于休眠狀態(tài)。

圖1 柵欄分割圖

激活Sub1子?xùn)艡?運行t時間后進(jìn)入休眠狀態(tài),當(dāng)Sub1進(jìn)入休眠狀態(tài)后,激活Sub2,同樣運行時間t后進(jìn)入休眠狀態(tài),然后按順序輪流調(diào)度,直到所有子?xùn)艡诙技せ罟ぷ饕淮?完成一次柵欄調(diào)度。最后按照上述方法開始新一輪的柵欄調(diào)度,直到所有子?xùn)艡谀芰亢谋M。

t=T/β

(1)

式中:中:β為常數(shù),T為節(jié)點總共運行的時間,當(dāng)完成β次調(diào)度后節(jié)點能量剛好耗盡。

L表示柵欄長度,將其均分為α段,每段長度為L/α,以其最左端傳感器節(jié)點為原點,建立一維坐標(biāo)系,如圖1,根據(jù)分割子?xùn)艡诘臄?shù)量、橫坐標(biāo)和柵欄的長度,給傳感器節(jié)點分配其所屬的子?xùn)艡诰幪?S1,S2,…,Sα)。由服務(wù)器控制子?xùn)艡诘难h(huán)激活調(diào)度,并且發(fā)送激活或休眠命令,進(jìn)而控制其工作狀態(tài)。

2 1-barrier 分析

本節(jié)分析柵欄在1-barrier流水式調(diào)度算法下的生存時間和檢測率。在3.1節(jié)中計算入侵者的平均通過時間。應(yīng)用平均通過時間計算出3.2節(jié)中的總體的檢測率。再計算出3.3節(jié)柵欄能延長的生存時間。

2.1 最短感知距離與平均通過時間

設(shè)入侵者通過感知區(qū)域的速度為v,且角度θ和位置x都為隨機(jī)。如圖2,傳感器節(jié)點位于0處。圖中d(θ,x)表示入侵者通過感知區(qū)域時的最短感知距離,le(θ,x)表示節(jié)點感知范圍內(nèi)通過路徑的長度。

圖2 通過路徑圖

由于θ∈[0,π]和x∈[-R,R]是相互獨立的隨機(jī)變量,且等概率,因此x的概率密度函數(shù)f(x)如式(2)所示,θ的概率密度函數(shù)g(θ)如式(3)所示。

(2)

式中:中:R表示節(jié)點感知半徑。

(3)

最短感知距離如式(4)所示。

d(θ,x)=|x|sinθ

(4)

式中:(4)中R為節(jié)點感知半徑,0≤θ≤π,-R≤x≤R。

計算d(θ,x)的平均值davg,如式(5)所示,計算可得davg的值如式(6)所示。

(5)

(6)

平均通過路徑長度如式(7)所示。

(7)

式中:R為節(jié)點感知半徑,0≤θ≤π,-R≤x≤R。

計算le(θ,x)的平均值leavg,如式(8)所示,通過泰勒級數(shù)可求得leavg的近似值如式(9)所示。

(8)

(9)

式中:R表示節(jié)點感知半徑。

通過leavg可計算入侵者的平均通過時間ct,如式(10)所示。

(10)

2.2 柵欄平均檢測率

文中研究柵欄在概率感知模型下的檢測率,概率感知模型如式(11)所示。

(11)

式中:d(i,j)為節(jié)點i與入侵者j之間的距離,m是個可調(diào)的參數(shù)。

入侵者被柵欄檢測到可分為二種情況:①在未被激活的柵欄處試圖通過,但子?xùn)艡谠谄渫ㄟ^感知范圍前被激活了。②直接被處于工作狀態(tài)的子?xùn)艡跈z測到。第1種情況如圖3所示。圖3(a)表示入侵者尚未被檢測到,圖3(b)表示入侵者被檢測到。

圖3 柵欄檢測圖

第1種情況的柵欄檢測率p1如式(12)所示。

(12)

式中:α表示子?xùn)艡诘臄?shù)量,davg如式(6)所示。

第2種情況的柵欄檢測率p2如式(13)所示。

(13)

綜上所述,p1、p2之和即為整條柵欄的平均檢測率P,如式(14)。

(14)

從式(14)可以看出當(dāng)α值越小時,表示子?xùn)艡诘臄?shù)量越少,其長度則越長,對應(yīng)檢測率越大。β越大時,T/β越小,表示子?xùn)艡跔顟B(tài)切換的越快,因此能監(jiān)測到入侵者的概率越大。

2.3 柵欄生存時間

如不分割子?xùn)艡?而是直接激活柵欄中所有節(jié)點,則柵欄的生存時間為T。分割時,當(dāng)消耗完所有子?xùn)艡诘哪芰亢?認(rèn)為該柵欄死亡。單個子?xùn)艡诩せ顮顟B(tài)的時間為T/β,則所有子?xùn)艡诙技せ罟ぷ饕淮涡枰獣r間為αT/β,柵欄的生存時間為αT。所以文中調(diào)度方法使得柵欄的生存時間延長了(α-1)T。

3 k-barrier分析

設(shè)在柵欄部署區(qū)域內(nèi)存在k條柵欄,k條柵欄同時進(jìn)行獨立的流水式柵欄調(diào)度。則入侵者通過k條柵欄的檢測率Pk如式(11)所示。

Pk=1-(1-P)k

(15)

式中:P表示一條柵欄在流水式調(diào)度算法下的檢測率,可由2.2節(jié)計算得到。

在保證k條柵欄檢測到入侵者的概率不小于Pth時,Pk≥Pth,則每條柵欄的檢測率P如式(16)所示。

(16)

同時調(diào)度k條柵欄時,若使用流水式調(diào)度算法,則k條柵欄的生存時間為αT。而按照傳統(tǒng)的柵欄調(diào)度方法,柵欄總共能生存的時間為kT。因此流水式調(diào)度算法比傳統(tǒng)的方法能延長k-柵欄的生存時間為(α-k)T。

4 仿真實驗

實驗中柵欄長度L=1 000 m,總共有k=4條柵欄。傳感器節(jié)點的最大生存時間t=24×60×60×7 s(一周),節(jié)點概率感知模型中m=0.07。實驗結(jié)果為200次實驗的平均結(jié)果,檢測率為4條柵欄總共的檢測率。

4.1 入侵軌跡平均長度

本次實驗驗證入侵者以某個節(jié)點為圓心,通過其感知區(qū)域的平均通過路徑長度leavg。實驗中入侵者以任意角度θ∈(0,π)通過一條柵欄,實驗結(jié)果如圖4所示。橫坐標(biāo)表示傳感器節(jié)點感知半徑,縱坐標(biāo)表示平均通過長度leavg。

圖4 通過路徑長度圖

實驗結(jié)果表明隨著感知半徑R的增大,平均通過路徑長度leavg呈線性增長,且文中2.1節(jié)計算的通過路徑平均長度與實驗結(jié)果符合。因為傳感器節(jié)點的感知半徑R增加,其感知范圍也增加,因此入侵者在傳感器節(jié)點感知范圍內(nèi)的通過路徑也會相應(yīng)的增加。

4.2 α、β對檢測率的影響

本次實驗n=4,節(jié)點感知半徑R=20 m,入侵者速度為1 m/s。T/β表示子?xùn)艡谔幱诩せ顮顟B(tài)的時間。α表示子?xùn)艡诘臄?shù)量,α越小子?xùn)艡谠缴?每條長度越長。α、β的取值在定義域(2.2節(jié))內(nèi)。本次實驗為采用流水式調(diào)度算法的4條柵欄同時對入侵者的檢測率,結(jié)果如圖5所示,橫坐標(biāo)為α,縱坐標(biāo)為檢測率Pk。

圖5 檢測率圖

實驗結(jié)果表明β越大,對入侵者的檢測率越高,這是由于當(dāng)β增大時,T/β減小,子?xùn)艡谔幱诩せ顮顟B(tài)的時間就縮短,對應(yīng)的狀態(tài)切換速度加快,檢測到入侵者的概率也就增大。與此同時,當(dāng)α增大,檢測率減小,這是由于α增大,子?xùn)艡诘拈L度縮短,導(dǎo)致柵欄的檢測率減小。當(dāng)α=7時,實驗中β的兩種取值都保證了柵欄對入侵者的檢測率大于90%。同時通過實驗驗證了文中的理論推導(dǎo)。

4.3 通過速度對檢測率影響

理論上入侵者的通過速度越快,柵欄檢測到的概率越低。本次實驗中α=4,節(jié)點感知半徑R=20 m,入侵者通過速度為1 m/s～7 m/s,以1 m/s遞增,實驗結(jié)果如圖6所示,橫坐標(biāo)表示通過速度,縱坐標(biāo)表示檢測率。

圖6 通過速度影響圖

從實驗結(jié)果可以發(fā)現(xiàn),檢測率隨著通過速度增加而減小,且隨著β增大而增大,這是由于β增大,子?xùn)艡谔幱诩せ畹臅r間會縮短,子?xùn)艡谡{(diào)度的速度加快,在入侵者通過速度一定的情況下檢測率更高。

4.4 柵欄生存時間

通過實驗,使用流水式柵欄調(diào)度算法(FSA)和傳統(tǒng)調(diào)度方法,驗證了條件當(dāng)檢測率在85%以上的時候,柵欄生存時間的差異。實驗中β=33 833,k=4,節(jié)點感知半徑R=20m,入侵者速度為1 m/s。結(jié)合4.2節(jié)的實驗,檢測率大于90%時α的取值分別為4、5、6、7、8、9、10。實驗結(jié)果如圖7所示,橫坐標(biāo)為α,縱坐標(biāo)為柵欄生存時間。

實驗顯示,在保證檢測率大于90%的同時,柵欄的生存時間隨著α增大而變長。且生存時間遠(yuǎn)遠(yuǎn)超過傳統(tǒng)的柵欄調(diào)度算法,為α/4倍。

圖7 柵欄生存時間圖

5 總結(jié)

本文提出了流水式柵欄調(diào)度算法(FSA),對延長柵欄生存時間非常有效。該算法通過將子?xùn)艡谳喠骷せ顏碓鲩L子?xùn)艡诘纳鏁r間,并且保證了一定的檢測率。除了滿足這兩項基本需求外,本算法并不是直接把所有柵欄同時激活,而是實施了柵欄內(nèi)部的子?xùn)艡谡{(diào)度,從而延長柵欄的生存時間。后續(xù)工作將進(jìn)一步研究在確保檢測率的情況下延長柵欄的生存時間。