WSN中一種流水式柵欄調度算法的研究*

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

(浙江工業大學計算機科學與技術學院,杭州 310032)

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

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

由于不同WSN柵欄應用中對檢測率的需求不同,本文提出了一種流水式的柵欄調度算法FSA(Flow-style Scheduling Algorithm),首先將柵欄均勻分割為些許子柵欄,將子柵欄循環激活,形成一種流水式工作狀態,通過被激活狀態的子柵欄來檢測試圖通過柵欄的入侵者。該算法在確保一定檢測率的情況下實現柵欄生存時間的大幅度提高。

1 流水式柵欄調度算法

首先描述下要實現本文算法所需要的一些條件,本文假設柵欄已經由文獻[17]等柵欄構建方法構建完成,然后進行算法描述。

1.1 相關條件

要實現本文算法的相關條件有四條:

條件1 傳感器網絡中節點同構,節點能量,感知半徑等都相同。且節點只有處于激活狀態時才會消耗能量,節點狀態切換消耗的能量忽略不計。

條件2 某條子柵欄監測到入侵者后可直接與Sink節點通訊,不需要經過其他節點轉發,且傳感器節點可獲取自身的位置信息(坐標)。

條件3 子柵欄不需要外部信號,直接通過節點內部的定時器設置喚醒與休眠狀態的切換。

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

1.2 調度算法

將柵欄分割,如圖1所示,將柵欄均勻分割為α條子柵欄。同一時刻只有唯一子柵欄處于工作狀態,其他處于休眠狀態。

圖1 柵欄分割圖

激活Sub1子柵欄,運行t時間后進入休眠狀態,當Sub1進入休眠狀態后,激活Sub2,同樣運行時間t后進入休眠狀態,然后按順序輪流調度,直到所有子柵欄都激活工作一次,完成一次柵欄調度。最后按照上述方法開始新一輪的柵欄調度,直到所有子柵欄能量耗盡。

t=T/β

(1)

式中:中:β為常數,T為節點總共運行的時間,當完成β次調度后節點能量剛好耗盡。

L表示柵欄長度,將其均分為α段,每段長度為L/α,以其最左端傳感器節點為原點,建立一維坐標系,如圖1,根據分割子柵欄的數量、橫坐標和柵欄的長度,給傳感器節點分配其所屬的子柵欄編號(S1,S2,…,Sα)。由服務器控制子柵欄的循環激活調度,并且發送激活或休眠命令,進而控制其工作狀態。

2 1-barrier 分析

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

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

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

圖2 通過路徑圖

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

(2)

式中:中:R表示節點感知半徑。

(3)

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

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

(4)

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

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

(5)

(6)

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

(7)

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

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

(8)

(9)

式中:R表示節點感知半徑。

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

(10)

2.2 柵欄平均檢測率

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

(11)

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

入侵者被柵欄檢測到可分為二種情況:①在未被激活的柵欄處試圖通過,但子柵欄在其通過感知范圍前被激活了。②直接被處于工作狀態的子柵欄檢測到。第1種情況如圖3所示。圖3(a)表示入侵者尚未被檢測到,圖3(b)表示入侵者被檢測到。

圖3 柵欄檢測圖

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

(12)

式中:α表示子柵欄的數量,davg如式(6)所示。

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

(13)

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

(14)

從式(14)可以看出當α值越小時,表示子柵欄的數量越少,其長度則越長,對應檢測率越大。β越大時,T/β越小,表示子柵欄狀態切換的越快,因此能監測到入侵者的概率越大。

2.3 柵欄生存時間

如不分割子柵欄,而是直接激活柵欄中所有節點,則柵欄的生存時間為T。分割時,當消耗完所有子柵欄的能量后,認為該柵欄死亡。單個子柵欄激活狀態的時間為T/β,則所有子柵欄都激活工作一次需要時間為αT/β,柵欄的生存時間為αT。所以文中調度方法使得柵欄的生存時間延長了(α-1)T。

3 k-barrier分析

設在柵欄部署區域內存在k條柵欄,k條柵欄同時進行獨立的流水式柵欄調度。則入侵者通過k條柵欄的檢測率Pk如式(11)所示。

Pk=1-(1-P)k

(15)

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

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

(16)

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

4 仿真實驗

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

4.1 入侵軌跡平均長度

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

圖4 通過路徑長度圖

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

4.2 α、β對檢測率的影響

本次實驗n=4,節點感知半徑R=20 m,入侵者速度為1 m/s。T/β表示子柵欄處于激活狀態的時間。α表示子柵欄的數量,α越小子柵欄越少,每條長度越長。α、β的取值在定義域(2.2節)內。本次實驗為采用流水式調度算法的4條柵欄同時對入侵者的檢測率,結果如圖5所示,橫坐標為α,縱坐標為檢測率Pk。

圖5 檢測率圖

實驗結果表明β越大,對入侵者的檢測率越高,這是由于當β增大時,T/β減小,子柵欄處于激活狀態的時間就縮短,對應的狀態切換速度加快,檢測到入侵者的概率也就增大。與此同時,當α增大,檢測率減小,這是由于α增大,子柵欄的長度縮短,導致柵欄的檢測率減小。當α=7時,實驗中β的兩種取值都保證了柵欄對入侵者的檢測率大于90%。同時通過實驗驗證了文中的理論推導。

4.3 通過速度對檢測率影響

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

圖6 通過速度影響圖

從實驗結果可以發現,檢測率隨著通過速度增加而減小,且隨著β增大而增大,這是由于β增大,子柵欄處于激活的時間會縮短,子柵欄調度的速度加快,在入侵者通過速度一定的情況下檢測率更高。

4.4 柵欄生存時間

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

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

圖7 柵欄生存時間圖

5 總結

本文提出了流水式柵欄調度算法(FSA),對延長柵欄生存時間非常有效。該算法通過將子柵欄輪流激活來增長子柵欄的生存時間,并且保證了一定的檢測率。除了滿足這兩項基本需求外,本算法并不是直接把所有柵欄同時激活,而是實施了柵欄內部的子柵欄調度,從而延長柵欄的生存時間。后續工作將進一步研究在確保檢測率的情況下延長柵欄的生存時間。