WSN巡邏式強柵欄調(diào)度算法研究*

毛科技,施偉元,楊志凱,周賢年,戴光麟,夏 明

(浙江工業(yè)大學計算機科學與技術(shù)學院,杭州 310023)

WSN巡邏式強柵欄調(diào)度算法研究*

毛科技,施偉元,楊志凱,周賢年,戴光麟,夏 明*

(浙江工業(yè)大學計算機科學與技術(shù)學院,杭州 310023)

無線傳感器網(wǎng)絡(luò)柵欄覆蓋研究已取得豐厚成果。提出一種巡邏式柵欄調(diào)度算法,該算法將柵欄均勻分為若干子?xùn)艡?依次輪流激活子?xùn)艡?激活的子?xùn)艡诠ぷ饕欢螘r間后進入休眠狀態(tài),然后下一條子?xùn)艡谟尚菝哌M入激活狀態(tài)。因此子?xùn)艡诘妮喠骷せ钚纬闪藮艡诘难策墵顟B(tài),當入侵者穿越柵欄時有很大概率會被巡邏子?xùn)艡跈z測到。在確保柵欄檢測率的情況下使得柵欄的生存時間得到大幅度延長。文中計算了在理論情況下的柵欄檢測率,最后通過實驗驗證了該算法的準確性和可靠性。

WSN;巡邏柵欄;生存時間;檢測率

無線傳感器網(wǎng)絡(luò)(WSN)被廣泛應(yīng)用于各個領(lǐng)域[1-2],其中無線傳感器網(wǎng)絡(luò)柵欄覆蓋主要應(yīng)用于入侵者檢測,將WSN柵欄部署在需要檢測區(qū)域,當入侵者試圖穿越柵欄時就會被檢測到。如在國防應(yīng)用中,將柵欄部署在邊境線可以探測非法越境者。在環(huán)保方面,將柵欄部署在污染源周圍可檢測污染物的擴散情況。在林業(yè)保護方面,將柵欄部署在森林火災(zāi)現(xiàn)場可檢測火災(zāi)蔓延情況等[3-4]。然而目前的電池技術(shù)使得傳感器節(jié)點的能量被很大程度的限制了。如何延長傳感器網(wǎng)絡(luò)的生存時間是關(guān)鍵問題。

為了延長WSN柵欄的生存時間,柵欄的加強算法、修復(fù)算法和調(diào)度算法成為重點研究問題。在柵欄加強和修復(fù)方面,如Anwar Saipulla[5]等人提出一種2階段算法修補柵欄間隙,使死亡的柵欄重新工作。第1階段,FIND-GAPS算法查找柵欄間隙,第2階段MEND-GAPS算法修復(fù)柵欄。Xu B[6]等人研究了入侵者的歷史數(shù)據(jù),分析柵欄中某些傳感器節(jié)點有較大的概率檢測到入侵者,然后將移動節(jié)點移動到這些易受攻擊的位置加強柵欄,從而防止因為某些節(jié)點能量消耗過多而導(dǎo)致柵欄提早死亡。Park T[7]等人提出了一種尋找柵欄瓶頸區(qū)域,并在瓶頸區(qū)域內(nèi)增加傳感器節(jié)點的算法,從而延長了傳感器網(wǎng)絡(luò)的生存時間。在柵欄調(diào)度方面的研究如Kumar[8]等人提出了Optimal Sleep-Wakeup調(diào)度算法,該算法通過分析柵欄的生存時間,組合成若干組k-柵欄,使得柵欄的能量被充分利用,從而達到k-柵欄生存時間最大化。Mostafaei H[9]等人提出了基于自動學習機的LABC算法,并將該算法與文獻[8]中提出的算法進行對比,證明該算法與文獻[8]中的算法趨于接近。Kim K S[10]等人提出了Duty-Cycle Scheme調(diào)度算法,該算法通過輪流調(diào)度多條柵欄,使得在保證一定檢測率的情況下延長了網(wǎng)絡(luò)的生存時間。Luo H[11]等人提出了CIBC調(diào)度算法,大大延長了網(wǎng)絡(luò)的生存時間。Kim D[12]等人提出了在靜態(tài)節(jié)點和移動節(jié)點混合下的柵欄生存時間最大化算法。文獻[13-18]等都研究了在不同情況下的延長柵欄生存時間的方法。

并非所有的WSN柵欄應(yīng)用中都需要100%的檢測率,因此本文提出了一種巡邏式的柵欄調(diào)度算法PSA(Patrol Scheduling Algorithm),該算法將柵欄均勻分割為若干子?xùn)艡?子?xùn)艡谘h(huán)激活,形成一種巡邏狀態(tài),入侵者試圖穿越柵欄時有很大概率會被巡邏柵欄檢測到。該算法在確保一定檢測率的情況下實現(xiàn)柵欄生存時間的大幅度提高。

1 巡邏式柵欄調(diào)度模型

本章節(jié)1.1小節(jié)介紹了柵欄調(diào)度模型的相關(guān)假設(shè),1.2小節(jié)具體介紹柵欄調(diào)度算法。本文假設(shè)柵欄已經(jīng)由文獻[19]等柵欄構(gòu)建算法構(gòu)建完成。

1.1 相關(guān)假設(shè)

假設(shè)1 柵欄中傳感器節(jié)點的能量,感知半徑都相同,且節(jié)點能量只有在激活狀態(tài)時才會消耗,處于激活狀態(tài)的節(jié)點能量消耗相同。

假設(shè)2 節(jié)點的感知模型是布爾模型,當入侵者進入節(jié)點感知范圍內(nèi)就可被節(jié)點檢測到。節(jié)點檢測到入侵者后可直接與Sink節(jié)點通訊,無需通過其他傳感器節(jié)點進行轉(zhuǎn)發(fā)。

假設(shè)3 柵欄的休眠和喚醒無需外部信號參與,柵欄形成后已經(jīng)在節(jié)點內(nèi)部設(shè)置相關(guān)key,利用key節(jié)點可主動進行休眠和喚醒,所以節(jié)點的狀態(tài)切換不消耗能量。

假設(shè)4 入侵者在穿越柵欄的過程中視為一個點,不考慮入侵者的實際體積,且入侵軌跡為任意角度的直線。

1.2 柵欄調(diào)度算法

巡邏式柵欄調(diào)度算法通過將一段整體的柵欄均勻分割為若干子?xùn)艡?在生存周期內(nèi)的任意時刻都有一條子?xùn)艡谔幱诩せ顮顟B(tài),且子?xùn)艡诘难h(huán)切換形成柵欄的巡邏狀態(tài)。如圖1所示。

圖1 柵欄分割圖

柵欄均勻分為α段,初始時刻柵欄處于休眠狀態(tài),隨機激活一條子?xùn)艡赟ubi,如圖1中i=2。子?xùn)艡赟ubi激活后運行t時間進入休眠狀態(tài),t如式(1)所示,同時子?xùn)艡赟ubi+1由休眠轉(zhuǎn)為激活狀態(tài)。當Subα由激活轉(zhuǎn)為休眠狀態(tài)時,Sub1由休眠轉(zhuǎn)為激活狀態(tài)。依次循環(huán)切換子?xùn)艡跔顟B(tài)直到節(jié)點能量耗盡。所有子?xùn)艡诙技せ钜淮蝿t完成一次巡邏。

(1)

式中:T為節(jié)點處于激活狀態(tài)總共能運行的時間,β表示巡邏次數(shù),當完成β次巡邏后節(jié)點能量剛好耗盡。

2 1-barrier分析

本小節(jié)分析1-barrier巡邏式調(diào)度算法的檢測率和柵欄生存時間。由于該檢測率與入侵者穿越柵欄的時間有關(guān),因此2.1小節(jié)計算穿越時間。2.2小節(jié)結(jié)合2.1小節(jié)的穿越時間計算柵欄總體的檢測率。2.3小節(jié)計算在確保一定檢測率的情況下柵欄延長的生存時間。

圖2 穿越路徑圖

2.1 入侵穿越時間

假設(shè)入侵者穿越感知區(qū)域的速度為v,且可能以任意角度θ和任意位置x穿越某個節(jié)點的感知區(qū)域,如圖2所示。

圖2中,le(θ,x)表示節(jié)點感知范圍內(nèi)穿越路徑的長度,如式(2)所示:

(2)

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

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

(3)

(4)

計算le(θ,x)的平均值leavg,如式(5)所示,利用泰勒級數(shù)可求得leavg的近似值如式(6)所示。

(5)

(6)

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

利用leavg可計算入侵者的平均穿越時間ct,如式(7)所示。

(7)

圖3 柵欄檢測圖

2.2 平均檢測率

入侵者被柵欄檢測到可分為2種情況:(1)入侵者被某條正處于激活狀態(tài)的子?xùn)艡跈z測到。(2)入侵者在休眠的柵欄處試圖穿越,但在入侵者離開感知范圍前休眠的子?xùn)艡诩せ盍?。?種情況如圖3所示。圖3(a)表示入侵者尚未被檢測到,圖3(b)表示入侵者被檢測到。

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

(8)

式中:α表示子?xùn)艡诘臄?shù)量。

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

通過將最危險剖面Ⅱ-Ⅱ?qū)隡IDAS/GTS中，并根據(jù)表1數(shù)據(jù)對各種材料屬性進行定義.模型為二維數(shù)值分析模型，尺寸大小為170 m×80 m，共劃分為8 864個單元，15 623個節(jié)點.分別設(shè)置樁界面接觸與錨索界面接觸來模擬抗滑樁與土體、預(yù)應(yīng)力錨索與土體的相互作用.同時將教學樓與幼兒園等建筑荷載等效為均布荷載作用在坡體上.最危險Ⅱ-Ⅱ剖面有限元網(wǎng)格模型如圖3所示.

(9)

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

(10)

從式(10)可以看出當α值越小時,表示柵欄被分割為子?xùn)艡诘臄?shù)量越少,則每條子?xùn)艡诘拈L度越長,對應(yīng)檢測率越大。β越大時,T/β越小,表示子?xùn)艡跔顟B(tài)切換的越快,巡邏速度越快,因此對應(yīng)的檢測率越大。

2.3 延長的生存時間

當所有子?xùn)艡谀芰慷枷耐旰?認為該柵欄死亡。子?xùn)艡诿看渭せ顮顟B(tài)持續(xù)的時間為T/β,則完成一次巡邏需要時間為(αT)/β,因此柵欄的生存時間為αT。如果不將柵欄分割為子?xùn)艡?而是全部激活柵欄中所有節(jié)點,則柵欄的生存時間為T。所以巡邏式柵欄的生存時間比整條柵欄都激活延長了(α-1)T。

2.4 柵欄復(fù)雜度

柵欄中的傳感器節(jié)點與遠程服務(wù)器可相互直接通訊,柵欄的長度為L,將柵欄分為α條子?xùn)艡?每條子?xùn)艡诘拈L度為L/α,假設(shè)以柵欄的最左端傳感器節(jié)點為原點,建立一維坐標系,如圖1所示,柵欄中每個傳感器節(jié)點向服務(wù)器報告自身的坐標信息,服務(wù)器根據(jù)傳感器節(jié)點的橫坐標、柵欄的長度和分割子?xùn)艡诘臄?shù)量,給傳感器節(jié)點分配其所屬的子?xùn)艡诰幪?編號為S1、S2、S3、…、Sα)。子?xùn)艡诘难h(huán)激活調(diào)度由服務(wù)器控制,服務(wù)器可向需要激活的子?xùn)艡谥械膫鞲衅鞴?jié)點發(fā)送激活或休眠命令、從而控制子?xùn)艡诘募せ钆c休眠。如當服務(wù)器需要激活子?xùn)艡赟ub1時,可向所屬子?xùn)艡诰幪枮镾1的傳感器節(jié)點發(fā)送激活命令,此時子?xùn)艡赟ub1中的傳感器節(jié)點都激活。綜上所述,在服務(wù)器端算法的復(fù)雜度非常低,僅為O(α)。

3 k-barrier分析

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

Pk=1-(1-P)k

(11)

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

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

(12)

巡邏式調(diào)度算法同時調(diào)度k條柵欄,則k條柵欄的生存時間為αT。而按照傳統(tǒng)的柵欄調(diào)度方法,如首先調(diào)度柵欄1,柵欄1所有的傳感器節(jié)點都處于激活狀態(tài),當柵欄1能量耗盡后再調(diào)度柵欄2,直到所有柵欄能量都耗盡。這種方法柵欄總共能生存的時間為kT。因此巡邏式調(diào)度算法比傳統(tǒng)的方法能延長k條柵欄的生存時間為(α-k)T。

4 仿真實驗

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

圖4 穿越路徑長度圖

4.1 入侵軌跡平均長度

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

實驗結(jié)果表明隨著感知半徑R的增大,平均穿越路徑長度leavg呈線性增長。且本文2.1小節(jié)計算的穿越路徑平均長度與實驗結(jié)果符合。

4.2α、β對檢測率的影響

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

圖5 檢測率圖

實驗結(jié)果表明β越大,對應(yīng)的檢測率越高,因為β越大,T/β越小,每條子?xùn)艡谔幱诩せ顮顟B(tài)的時間越短,對應(yīng)的巡邏速度越快,因此檢測到入侵者的概率越大。檢測率隨著α增大而減小,因為α越大,子?xùn)艡诘拈L度越小,因此柵欄的檢測率越小。同時實驗結(jié)果也表明了本文理論推導(dǎo)與實驗結(jié)果相符合。

圖6 穿越速度影響圖

4.3 穿越速度對檢測率影響

入侵者的穿越速度對本文算法有重要影響,理論上穿越速度越快,則柵欄檢測到入侵者的概率越低。本次實驗中α=4,節(jié)點感知半徑R=20m,入侵者穿越速度為1m/s～7m/s,以1m/s遞增,實驗結(jié)果如圖6所示,橫坐標表示穿越速度,縱坐標表示檢測率。

實驗結(jié)果表明隨著穿越速度增加,檢測率減小。而且檢測率隨著β增大而增大,因為β越大,在一次柵欄巡邏中子?xùn)艡谔幱诩せ畹臅r間越短,則子?xùn)艡诘难策壦俣仍娇?所以檢測率越大。

4.4 柵欄生存時間

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

圖7 柵欄生存時間圖

實驗中傳統(tǒng)的方法如第4小節(jié)介紹。實驗結(jié)果表明在保證檢測率大于90%的情況下,隨著α增大,柵欄的生存時間也越長。且本文的柵欄調(diào)度算法(PSA)的生存時間遠遠超過傳統(tǒng)的柵欄調(diào)度算法。

5 總結(jié)

無線傳感器網(wǎng)絡(luò)柵欄調(diào)度算法對延長柵欄生存時間至關(guān)重要。本文提出了巡邏式柵欄調(diào)度算法(PSA),該算法在保證一定檢測率的條件下輪流激活子?xùn)艡谶M行巡邏。與以往算法不同之處在于本文算法考慮了一條柵欄內(nèi)部的子?xùn)艡谡{(diào)度,沒有全部激活柵欄,從而達到延長柵欄生存時間的目的。但是本文算法還是有不足之處,比如當入侵者速度非?？鞎r,本文調(diào)度算法的檢測率將有所下降。后續(xù)工作將進一步研究傳感器節(jié)點在概率模型下的巡邏式柵欄調(diào)度算法的性能。

[1]ChenM,GonzalezS,VasilakosA.BodyAreaNetworks:ASurvey[J].MobileNetworksandApplications,2011,16(2):171-193.

[2]Liu L,Xia F,Wang Z,et al. Deployment Issues in Wireless Sensor Networks[J]. 2005,3794:239-248.

[3]Chen A,Kumar S,Lai T H. Designing Localized Algorithms for Barrier Coverage[C]//International Conference on Mobile Computing and Networking,MOBICOM 2007,Montréal,Québec,Canada,September. 2007:63-74.

[4]班冬松,溫俊,蔣杰,等. 移動無線傳感器網(wǎng)絡(luò)k-柵欄覆蓋構(gòu)建算法[J]. 軟件學報,2011,22(9):2089-2103.

[5]Saipulla A,Westphal C,Liu B,et al. Barrier Coverage with Line-Based Deployed Mobile Sensors[J]. Ad Hoc Networks,2013,11(4):1381-1391.

[6]Xu B,Zhu Y,Kim D,et al. Strengthening Barrier-Coverage of Static Sensor Network With Mobile Sensor Nodes[J]. Wireless Networks,2016,22(1):1-10.

[7]Park T,Shi H. Extending the Lifetime of Barrier Coverage by Adding Sensors to a Bottleneck Region[C]//2015 12th Annual IEEE Consumer Communications and Networking Conference(CCNC). IEEE,2015:537-542.

[8]Kumar S,Lai T H,Posner M E,et al. Optimal Sleep-Wakeup Algorithms for Barriers of Wireless Sensors[C]//International Conference on Broadband Communications,Networks and Systems,2007. Broadnets. DBLP,2007:327-336.

[9]Mostafaei H,Meybodi M R. An Energy Efficient Barrier Coverage Algorithm for Wireless Sensor Networks[J]. Wireless Personal Communications,2014,77(3):2099-2115.

[10]Kim K S,Jin G W. Maximizing the Lifetime of a Sensor Network with Barrier Coverage[M]//Green and Smart Technology with Sensor Applications. Springer Berlin Heidelberg,2012:347-354.

[11]Luo H,Du H,Kim D,et al. ImperfectionBetter Than Perfection:Beyond Optimal Lifetime Barrier Coverage in Wireless Sensor Networks[C]//International Conference on Mobile Ad-Hoc and Sensor Networks. IEEE Computer Society,2014:24-29.

[12]Kim D,Wang W,Son J,et al. Maximum Lifetime Combined Barrier-Coverage of Weak Static Sensors and Strong Mobile Sensors[J]. IEEE Transactions on Mobile Computing,2016.

[13]Kim H,Kim D,Li D,et al. Maximum Lifetime Dependable Barrier-Coverage in Wireless Sensor Networks[J]. Ad Hoc Networks,2016,36(P1):296-307.

[14]Cobb J A. Improving the Lifetime of Non-Penetrable Barrier Coverage in Sensor Networks[C]//IEEE,International Conference on Distributed Computing Systems Workshops. IEEE,2015:1-10.

[15]DeWitt J,Patt S,Shi H. Maximizing Continuous Barrier Coverage in Energy Harvesting Sensor Networks[C]//2014 IEEE International Conference on Communications(ICC). IEEE,2014:172-177.

[16]Yang H,Li D,Zhu Q,et al. Minimum Energy Costk-Barrier Coverage in Wireless Sensor Networks[C]//International Conference on Wireless Algorithms,Systems,and Applications. Springer-Verlag,2010:80-89.

[17]戴光麟,方凱,戴國勇,等. 入侵軌跡建模與WSN柵欄覆蓋分段調(diào)度算法研究[J]. 傳感技術(shù)學報,2016,29(5):745-750.

[18]毛科技,方凱,戴國勇,等. 基于改進蟻群算法的無線傳感器網(wǎng)絡(luò)柵欄覆蓋優(yōu)化研究[J]. 傳感技術(shù)學報,2015(7):1058-1065.

[19]He S,Gong X,Zhang J,et al. Barrier Coverage in Wireless Sensor Networks:From Lined-Based to Curve-Based Deployment[C]//INFOCOM,2013 Proceedings IEEE. IEEE,2013:470-474.

APatrol Strong Barrier Scheduling Algorithm in WSN*

MAOKeji,SHIWeiyuan,YANGZhikai,ZHOUXiannian,DAIGuanglin,XIAMing*

(College of Computer Science and Technology,Zhejiang University of Technology,Hangzhou 310023,China)

The research of barrier coverage of Wireless Sensors Networks has achieved rich results. We proposed a patrol barrier scheduling algorithm,in this algorithm the barrierwas divided into several sub-barriers,and took turns to be activated;the activated sub-barrier would enter a dormant state after working a period,and then the next sub-barrier by dormancy into the activated state. So the sub-barrier activation in turn form the fence patrol state,when the intruder through the fence would be a great probability patrol fence is detected. Under the condition of ensure the detection rate of barrier made barrier greatly prolong survival time. In this paper,we calculated the theory in the case of barrier detection rate,finally the veracity and reliability of the algorithm is verified by experiment.

WSN;patrol barrier;survival time;detection rate

毛科技(1979-)，男，漢族，浙江工業(yè)大學計算機科學與技術(shù)學院副教授，博士，主要研究方向為無線傳感器網(wǎng)絡(luò)、大數(shù)據(jù)分析，maokeji@zjut．edu．cn；施偉元(1994-)，男，漢族，浙江工業(yè)大學計算機科學與技術(shù)學院碩士研究生，主要研究方向為無線傳感器網(wǎng)絡(luò)、大數(shù)據(jù)分析，ftamsir@sina．com； 夏 明(1981-)，男，漢族，浙江工業(yè)大學計算機科學與技術(shù)學院副教授，博士，主要研究方向為物聯(lián)網(wǎng)、無線傳感器網(wǎng)絡(luò)，xiaming@zjut．edu．cn。

項目來源:國家自然科學基金項目(61401397,61379023);浙江省公益性技術(shù)應(yīng)用研究計劃項目(2015C31066)

2017-04-24 修改日期:2017-06-06

TP393

A

1004-1699(2017)08-1240-06

C:7230

10.3969/j.issn.1004-1699.2017.08.019