戴光麟，方　凱，戴國(guó)勇，徐　慧，毛科技

（浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州310023）

入侵軌跡建模與WSN柵欄覆蓋分段調(diào)度算法研究*

戴光麟，方凱，戴國(guó)勇，徐慧，毛科技*

（浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州310023）

無線傳感器網(wǎng)絡(luò)柵欄覆蓋在入侵檢測(cè)方面發(fā)揮著重要作用，如何調(diào)度柵欄并延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間已成為重點(diǎn)研究問題。在無線傳感器網(wǎng)絡(luò)中設(shè)計(jì)合理的調(diào)度算法，分時(shí)激活傳感器節(jié)點(diǎn)從而延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間是大多數(shù)研究的方向，然而僅僅通過分時(shí)調(diào)度傳感器節(jié)點(diǎn)已很難大幅度提高網(wǎng)絡(luò)的生存時(shí)間。因此設(shè)計(jì)了一種分時(shí)與分段相結(jié)合的無線傳感器網(wǎng)絡(luò)柵欄調(diào)度算法，該算法通過分析入侵目標(biāo)穿越傳感器網(wǎng)絡(luò)部署區(qū)域的行為特征，建立入侵目標(biāo)的軌跡模型，該模型在保證柵欄對(duì)入侵目標(biāo)具有較高檢測(cè)率的情況下預(yù)測(cè)入侵目標(biāo)可能穿越柵欄的區(qū)域并分段激活柵欄從而大大減少了傳感器節(jié)點(diǎn)的能量消耗。最后仿真實(shí)驗(yàn)驗(yàn)證了本文算法與傳統(tǒng)的分時(shí)調(diào)度算法相比能大幅度提高網(wǎng)絡(luò)的生存時(shí)間。

無線傳感器網(wǎng)絡(luò)；入侵目標(biāo)建模；調(diào)度算法；節(jié)能

EEACC：7230；6150Pdoi：10.3969/j.issn.1004-1699.2016.05.021

傳感器節(jié)點(diǎn)的能量受限，如何延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間是關(guān)鍵問題［1］。無線傳感器網(wǎng)絡(luò)柵欄覆蓋有著廣泛的用途，其主要作用是監(jiān)測(cè)試圖穿越部署區(qū)域的入侵目標(biāo)［2］。在生態(tài)方面，將柵欄部署在自然保護(hù)區(qū)邊界可防止外來物種入侵。在林業(yè)保護(hù)方面，將柵欄部署在森林火災(zāi)區(qū)域邊緣，可有動(dòng)態(tài)檢測(cè)火災(zāi)蔓延情況。在環(huán)保方面，將柵欄部署在工廠周圍檢測(cè)污染物質(zhì)的擴(kuò)散。

在軍事方面，可將柵欄部署在陣地前沿已監(jiān)測(cè)敵人的入侵等［3-5］。

目前無線傳感器網(wǎng)絡(luò)柵欄覆蓋研究已取得豐厚的成果，如Kumar等人首次提出了強(qiáng)K-barrier和弱K-barrier覆蓋的概念，并判斷部署區(qū)域是否被強(qiáng)K-barrier覆蓋［6］。Anwar Saipulla等人提出了利用權(quán)重有向圖的最大流算法求解靜態(tài)傳感器網(wǎng)絡(luò)中形成柵欄的數(shù)量［7］。在后續(xù)研究中又提出了line-based部署方式并使用最大流算法派遣移動(dòng)節(jié)點(diǎn)修補(bǔ)柵欄間隙使得所有節(jié)點(diǎn)移動(dòng)距離之和最?。?］。Tian J等人提出了二維K-柵欄覆蓋問題，并將部署區(qū)域劃分為子區(qū)域分別構(gòu)建柵欄的思想［9］。Chen J等人利用概率感知模型，以入侵者的速度為限制條件，將入侵監(jiān)測(cè)問題轉(zhuǎn)化為網(wǎng)絡(luò)最大流問題，并根據(jù)節(jié)點(diǎn)間距離和剩余能量，提出一種有界柵欄構(gòu)造方法［10］。

為了延長(zhǎng)柵欄生存時(shí)間，又提出很多柵欄調(diào)度算法，如Kumar等人研究了如何調(diào)度已經(jīng)構(gòu)建的柵欄形成強(qiáng)K-柵欄，使得柵欄中傳感器節(jié)點(diǎn)的能量被充分利用從而延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間，提出了Optimal Sleep-Wakeup算法，該算法的結(jié)果是柵欄生存時(shí)間的理想上界［11］。Mostafaei H等人又提出了基于自動(dòng)學(xué)習(xí)的LABC算法，并將該算法與Optimal Sleep-Wakeup進(jìn)行對(duì)比［12］。羅卿等人提出了基于概率感知模型的方法，并在此基礎(chǔ)上提出了一種柵欄覆蓋控制算法，該算法借助分治法構(gòu)造柵欄，并調(diào)度冗余節(jié)點(diǎn)達(dá)到延長(zhǎng)網(wǎng)絡(luò)壽命的目的［13］。然而這些算法并沒有考慮入侵者的軌跡特征，由于在實(shí)際監(jiān)測(cè)中，柵欄只有很短一段能檢測(cè)到入侵者，其余柵欄都處于激活盲等狀態(tài)，這會(huì)消耗大量的能量。

結(jié)合上述研究，本文提出了一種入侵模型預(yù)測(cè)下的WSN柵欄分段調(diào)度算法SSA（Segmented Scheduling Algorithm）。該方法通過分析入侵目標(biāo)的行為特性，建立入侵目標(biāo)的軌跡模型，預(yù)測(cè)入侵目標(biāo)可能會(huì)穿越柵欄的位置，并有針對(duì)性的開啟柵欄的某一段，以攔截的方式檢測(cè)入侵目標(biāo)。同時(shí)又分析了該方法的檢測(cè)率以及網(wǎng)絡(luò)生存時(shí)間。SSA算法通過犧牲較小的檢測(cè)率能大幅度提高傳感器網(wǎng)絡(luò)的生存時(shí)間。

1　入侵模型

當(dāng)入侵目標(biāo)帶有目的性的穿越某塊帶狀區(qū)域時(shí)，往往會(huì)選擇最短路徑或者接近最短路徑的軌跡進(jìn)行穿越。如在軍事上，入侵者想穿越陣地前沿的帶狀區(qū)域進(jìn)行偷襲，不會(huì)在陣地前沿的區(qū)域內(nèi)徘徊，最可能沿直線徑直穿越。以垂直帶狀區(qū)域的方向?yàn)榛鶞?zhǔn)，偏離該方向的角度表示入侵角度。因此入侵者選擇入侵角度的概率是不同的，入侵角度越小，被選擇的概率越大，對(duì)應(yīng)的穿越路徑越短，越有利于偷襲。入侵角度越大，穿越的路徑越長(zhǎng)，消耗的時(shí)間越多，不利于偷襲。假設(shè)穿越速度均勻，影響穿越某塊區(qū)域的最大因素是入侵的角度。但是在實(shí)際穿越某塊區(qū)域的過程中，入侵角度的選擇還要考慮環(huán)境因素的影響。

入侵者以一定角度x穿越已部署傳感器節(jié)點(diǎn)區(qū)域，如圖1所示，箭頭表示入侵的方向。角度x的絕對(duì)值|x|越大，被選擇作為入侵角的概率越低，|x|越小，被選擇作為入侵角的概率越高。基于上述分析對(duì)入侵目標(biāo)建立入侵模型，該模型綜合考慮了入侵目標(biāo)的穿越特性以及環(huán)境對(duì)入侵角選擇的影響。該模型的入侵角度服從f（x）分布，如式（2）所示。式（2）中s為常數(shù)，表達(dá)式如式（1）所示。該模型的建立是以實(shí)際入侵穿越的情況為依據(jù)，因此具有較高的真實(shí)性。

圖1　入侵角度圖

通過概率密度函數(shù)f（x）可求得入侵角度x∈（-α，α）的概率P，求解過程如式（3）、式（4）所示。在本文后續(xù)章節(jié)中概率f表示分段激活的柵欄對(duì)入侵目標(biāo)的檢測(cè)率。

式（1）、式（2）、式（4）中r為影響因子（環(huán)境對(duì)入侵的影響因素），且r＞0。當(dāng)入侵環(huán)境中障礙物較少時(shí)，r取值為r1，柵欄檢測(cè)率為P1（α）。當(dāng)入侵環(huán)境中障礙物較多時(shí)，r取值為r2，柵欄檢測(cè)率為P2（α）。此時(shí)r的取值r1＜r2，對(duì)應(yīng)的檢測(cè)率P1（α）＞P2（α）。

2　調(diào)度算法及性能分析

2.1SSA調(diào)度算法

入侵目標(biāo)穿越柵欄部署區(qū)域可能以直線的形式穿越也可能是非直線穿越，假設(shè)通過文獻(xiàn)［8，14-16］等方法已經(jīng)形成了n條強(qiáng)柵欄，柵欄間距離為d，柵欄長(zhǎng)度為L(zhǎng)，且d≤L，如圖2所示。本文以調(diào)度n條柵欄形成強(qiáng)2-柵欄為例，分析了直線穿越和非直線穿越情況下的柵欄生存時(shí)間和檢測(cè)率。

圖2　入侵路徑圖

假設(shè)每條柵欄都由n個(gè)傳感器節(jié)點(diǎn)均勻分布組成，節(jié)點(diǎn)間距離D=2R，其中R為傳感器節(jié)點(diǎn)感知半徑，每條柵欄都從1～n進(jìn)行編號(hào)，相同編號(hào)的傳感器節(jié)點(diǎn)橫坐標(biāo)相同。SSA調(diào)度算法首先將柵欄1中的傳感器節(jié)點(diǎn)全部激活，如果節(jié)點(diǎn)編號(hào)為s的傳感器節(jié)點(diǎn)檢測(cè)到有目標(biāo)入侵，則在滿足檢測(cè)率為P的情況下利用入侵模型計(jì)算出入侵角的范圍α，然后激活柵欄2中傳感器節(jié)點(diǎn)編號(hào)范圍為（s-dtanα/（2R），s+dtanα/（2R））的柵欄，該段柵欄長(zhǎng)度Ln=2dtanα。如圖3所示。當(dāng)柵欄1的能量耗盡，接著將柵欄2的傳感器節(jié)點(diǎn)全部開啟，柵欄3則分段式激活，以此類推，直到第m-1條柵欄的能量耗盡最后不能形成強(qiáng)2-柵欄為止，標(biāo)志著整個(gè)傳感器網(wǎng)絡(luò)最終死亡。本文算法通過分段激活的方式檢測(cè)入侵目標(biāo)，當(dāng)?shù)?條柵欄檢測(cè)到入侵目標(biāo)后，以感知到入侵目標(biāo)的節(jié)點(diǎn)作為入侵點(diǎn)，對(duì)其余條柵欄采取同樣的分段激活策略，如圖4所示，圖中箭頭表示入侵軌跡，圓點(diǎn)表示檢測(cè)到入侵目標(biāo)的傳感器節(jié)點(diǎn)。具體的SSA調(diào)度算法如表1所示。

圖3　柵欄分段激活圖

圖4　n-柵欄分段激活圖

表1　SSA調(diào)度算法

2.2網(wǎng)絡(luò)生存時(shí)間分析

利用SSA調(diào)度算法調(diào)度n條柵欄形成2-柵欄，假設(shè)每條柵欄有n個(gè)傳感器節(jié)點(diǎn)成，傳感器節(jié)點(diǎn)包含的能量為E，對(duì)應(yīng)的生存時(shí)間為t，感知半徑為F。傳感器處于激活狀態(tài)時(shí)單位時(shí)間內(nèi)消耗的能量為e。分析傳感器網(wǎng)絡(luò)總共的生存時(shí)間以柵欄1、2為例。當(dāng)入侵目標(biāo)被柵欄2檢測(cè)到的概率為F時(shí)，柵欄2中處于激活狀態(tài)的柵欄長(zhǎng)度為L(zhǎng)n，該段柵欄單位時(shí)間內(nèi)總共消耗的能量為eb1，如式（5）所示。柵欄1總共消耗的能量為eb2，如式（6）所示。因此柵欄1消耗的能量是柵欄2的u倍，如式（7）所示。由于傳感器節(jié)點(diǎn)能量與生存時(shí)間相對(duì)應(yīng)，所以柵欄2的生存時(shí)間是柵欄1的u倍。

基于上述分析，可以計(jì)算出擁有m條強(qiáng)柵欄的傳感器網(wǎng)絡(luò)調(diào)度形成強(qiáng)2-柵欄其生存時(shí)間為T，如式（8）所示，簡(jiǎn)化后如式（9）所示。

2.3非直線穿越的檢測(cè)率

利用公式（4）能方便的求出直線穿越柵欄部署區(qū)域的檢測(cè)率，然而實(shí)際入侵目標(biāo)并不一定沿直線穿越部署區(qū)域，因此本節(jié)研究當(dāng)入侵目標(biāo)以非直線穿越部署區(qū)域被柵欄2中激活的Ln段柵欄檢測(cè)到的概率。如果入侵目標(biāo)在相距為d的柵欄1和柵欄2之間有多次改變方向的行為，假設(shè)其改變方向的位置都在兩條柵欄的均勻分割線上，如圖5所示。以柵欄部署方向?yàn)閤軸方向，以入侵點(diǎn)為原點(diǎn)建立橫坐標(biāo)系。

假設(shè)入侵目標(biāo)在穿越部署區(qū)域過程中有z次改變方向（包括在柵欄1處的入侵方向），角度分別為α1、α2、α3…αz，且都滿足f（x）分布，則入侵目標(biāo)最后到達(dá)柵欄2的橫坐標(biāo)為y∈（-∞，+∞），如式（10）所示。

圖5　非直線穿越圖

由于z次改變方向是獨(dú)立同分布事件，因此入侵目標(biāo)被柵欄2中Ln段柵欄檢測(cè)到的概率服從g（y）z分布，如式（12）所示，式（11）中f（a1，a2，a1…az）為z次事件的聯(lián)合概率密度。所以入侵目標(biāo)被Ln段柵欄檢測(cè)到的概率Py如式（13）所示。由于概率密度函數(shù)f（x）比較復(fù)雜，本節(jié)只給出概率密度函數(shù)g（y）z的計(jì)算方法，并計(jì)算了z=1時(shí)的概率密度函數(shù)g（y）1，如式（14）所示。并以實(shí)驗(yàn)驗(yàn)證了入侵目標(biāo)以非直線穿越比直線穿越部署區(qū)域被Ln段柵欄檢測(cè)到的概率更高。

3　仿真實(shí)驗(yàn)

實(shí)驗(yàn)中設(shè)置柵欄長(zhǎng)度L=1 000 m，柵欄間距離d=150 m，α∈（0，π/2）。傳感器節(jié)點(diǎn)的能量為100 W，對(duì)應(yīng)的生存時(shí)間t=24×60×60×7 s（一周），實(shí)驗(yàn)中Ln段柵欄是被激活的一段柵欄，如圖3、圖5所示。通過以下實(shí)驗(yàn)驗(yàn)證本文調(diào)度算法的性能。

3.1檢測(cè)率

本次實(shí)驗(yàn)驗(yàn)證柵欄檢測(cè)率是否與理論推導(dǎo)相符合。當(dāng)柵欄1監(jiān)測(cè)到入侵目標(biāo)后，采取分段激活的策略，相應(yīng)的激活柵欄2中的Ln段柵欄用于監(jiān)測(cè)入侵目標(biāo)。實(shí)驗(yàn)中影響因子r=0.5，分別驗(yàn)證了入侵次數(shù)為50次、100次、300、次1 300次的情況，實(shí)驗(yàn)結(jié)果如圖6所示，橫坐標(biāo)為α，縱坐標(biāo)為檢測(cè)率P。

實(shí)驗(yàn)結(jié)果表明隨著實(shí)驗(yàn)次數(shù)的增加，實(shí)際的檢測(cè)率是漸漸趨向理論證明。入侵次數(shù)比較少時(shí)檢測(cè)率波動(dòng)比較大，當(dāng)num=1 300次時(shí)，檢測(cè)率的波動(dòng)非常小且與理論推導(dǎo)基本吻合。當(dāng)α趨近于π 2時(shí)，柵欄2的節(jié)點(diǎn)被全部激活，此時(shí)檢測(cè)率P=1，實(shí)驗(yàn)結(jié)果驗(yàn)證了入侵角服從（fx）分布的檢測(cè)率。

圖6　直線穿越檢測(cè)率圖

3.2影響因子

入侵目標(biāo)的入侵角度會(huì)受外界環(huán)境以及自身因素的影響，因此本文設(shè)計(jì)的入侵模型考慮了影響因子。本次實(shí)驗(yàn)驗(yàn)證影響因子對(duì)檢測(cè)率的影響。當(dāng)柵欄1監(jiān)測(cè)到入侵目標(biāo)后，采取分段激活的策略，相應(yīng)的激活柵欄2中的Ln段柵欄用于監(jiān)測(cè)入侵目標(biāo)。由于入侵模型的概率密度函數(shù)f（x）是拱形函數(shù)，因此影響因子r的取值不同會(huì)嚴(yán)重影響柵欄的檢測(cè)率。當(dāng)SSA分段調(diào)度算法在實(shí)際應(yīng)用中可根據(jù)入侵目標(biāo)的特性和環(huán)境因素估計(jì)合適的影響因子。實(shí)驗(yàn)中研究r分別為0.25、0.5、1.0、2.0時(shí)對(duì)檢測(cè)率的影響。

圖7　影響因子圖

實(shí)驗(yàn)結(jié)果如圖7所示，橫坐標(biāo)為α，縱坐標(biāo)為檢測(cè)率P，每次實(shí)驗(yàn)都有3 000個(gè)目標(biāo)穿越柵欄。實(shí)驗(yàn)結(jié)果表明r的值越小，被柵欄2中激活的柵欄檢測(cè)到的概率越高。

3.3能量消耗

當(dāng)入侵目標(biāo)試圖穿越柵欄部署區(qū)域時(shí)，根據(jù)SSA算法，首先會(huì)被全激活的柵欄1檢測(cè)到，然后才會(huì)被部分激活的柵欄2檢測(cè)到。本次實(shí)驗(yàn)研究全激活狀態(tài)的柵欄和部分激活狀態(tài)的柵欄的能量消耗。每次實(shí)驗(yàn)都有4 000個(gè)目標(biāo)穿越柵欄，影響因子r=0.5，柵欄2監(jiān)測(cè)一個(gè)入侵目標(biāo)處于激活狀態(tài)的時(shí)間維持180 s，然后才會(huì)將柵欄切換為睡眠狀態(tài)。實(shí)驗(yàn)結(jié)果如圖8所示，橫坐標(biāo)為α，縱坐標(biāo)為兩條柵欄消耗能量的倍數(shù)關(guān)系，Theory為理論分析的結(jié)果，由式（7）計(jì)算得到。Practice為實(shí)驗(yàn)得到的結(jié)果。

圖8　能耗關(guān)系圖

實(shí)驗(yàn)結(jié)果表明全激活狀態(tài)的柵欄在監(jiān)測(cè)入侵目標(biāo)過程中消耗的能量遠(yuǎn)遠(yuǎn)大于部分激活狀態(tài)的柵欄。從實(shí)驗(yàn)結(jié)果可以看出隨著α增大，柵欄實(shí)際消耗能量與理論分析一致。但是實(shí)際的結(jié)果并非平滑曲線且α比較小的時(shí)候與理論分析的結(jié)果存在較大差異，這是因?yàn)楫?dāng)α較小時(shí)，α即使在增加，但處于激活狀態(tài)的節(jié)點(diǎn)還是和α沒改變之前是同一個(gè)傳感器節(jié)點(diǎn)。α改變但處于激活狀態(tài)的節(jié)點(diǎn)數(shù)量不變，能量消耗也就不會(huì)變，所以會(huì)出現(xiàn)圖中的梯度下降的情況。

3.4生存時(shí)間

傳感器網(wǎng)絡(luò)的生存時(shí)間至關(guān)重要，本次實(shí)驗(yàn)研究SSA算法調(diào)度4條強(qiáng)柵欄形成強(qiáng)2-柵欄的網(wǎng)絡(luò)生存時(shí)間，并與文獻(xiàn)［11］最佳調(diào)度算法和文獻(xiàn)［17］隨機(jī)調(diào)度算法進(jìn)行對(duì)比。其中文獻(xiàn)［11］的最佳調(diào)度算法充分利用了傳感器節(jié)點(diǎn)的能量，已經(jīng)是傳感器網(wǎng)絡(luò)柵欄生存時(shí)間問題的上限。然而本文的方法通過犧牲較小的檢測(cè)率能大幅度提高柵欄的生存時(shí)間。在保證檢測(cè)率為90%的情況下與上述算法進(jìn)行對(duì)比，實(shí)驗(yàn)中影響因子r=0.5，實(shí)驗(yàn)結(jié)果如圖9所示，橫坐標(biāo)表示入侵的次數(shù)，縱坐標(biāo)表示生存時(shí)間。

圖9　生存時(shí)間圖

圖9中SSA Practice表示實(shí)驗(yàn)得到的結(jié)果，SSA Theory表示理論上的生存時(shí)間，可通過式（9）計(jì)算得到。實(shí)驗(yàn)結(jié)果表明在檢測(cè)率為90%的情況下，SSA算法的網(wǎng)絡(luò)生存時(shí)間遠(yuǎn)遠(yuǎn)大于最佳調(diào)度算法（Optimal Sleep-Wakeup）和隨機(jī)調(diào)度算法（RIS）。因此在很多不要求檢測(cè)率為100%的情況下使用SSA算法能大幅度延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間。

3.5非直線穿越情況下的檢測(cè)率

入侵目標(biāo)很大可能以非直線的形式穿越柵欄部署區(qū)域。本次實(shí)驗(yàn)研究曲線穿越情況下的柵欄檢測(cè)率。實(shí)驗(yàn)中入侵目標(biāo)多次在柵欄1和柵欄2之間改變?nèi)肭址较颍淖兎较虻拇螖?shù)分別為0、1、3、5、15，柵欄2中激活的長(zhǎng)度仍然為L(zhǎng)n，實(shí)驗(yàn)中影響因子r=0.5，實(shí)驗(yàn)結(jié)果如圖10所示，橫坐標(biāo)為α，縱坐標(biāo)為檢測(cè)率P，每次實(shí)驗(yàn)都有3 000個(gè)目標(biāo)穿越柵欄。

圖10　非直線穿越檢測(cè)率圖

實(shí)驗(yàn)中cdnum=0表示入侵目標(biāo)以直線形式穿越柵欄，實(shí)驗(yàn)結(jié)果表明入侵目標(biāo)在穿越柵欄過程中改變方向的次數(shù)越多則被柵欄2中激活段柵欄檢測(cè)到的概率越高。同時(shí)表明不管是沿直線還是非直線軌跡穿越柵欄部署區(qū)域，當(dāng)入侵角范圍屬于（-α，α）時(shí)，柵欄檢測(cè)率至少為P（α）。

4　總結(jié)

針對(duì)目前已提出的一些無線傳感器網(wǎng)絡(luò)柵欄調(diào)度算法并不能大幅度提高網(wǎng)絡(luò)生存時(shí)間問題，本文提出了SSA算法，該算法在保證檢測(cè)率的情況下分段激活并調(diào)度柵欄。與傳統(tǒng)算法不同的是SSA算法通過犧牲較小的檢測(cè)率能大幅度提高傳感器網(wǎng)絡(luò)的生存時(shí)間。但是該算法還是存在一定資源的浪費(fèi)，如最后的柵欄不能被充分利用，以及該算法不能用于要求檢測(cè)率為100%的場(chǎng)景中。后續(xù)工作將進(jìn)一步研究入侵目標(biāo)，建立更加完善的入侵模型，以此來提高柵欄的檢測(cè)率，并設(shè)計(jì)更合理的調(diào)度算法。

［1］陳立建，周雪，雷艷靜，等.一種基于功率控制的WSN自適應(yīng)能量高效傳輸模式研究［J］.傳感技術(shù)學(xué)報(bào)，2014，27（6）：835-841.

［2］任勇默，范興剛，車志聰，等.一種有向傳感器網(wǎng)絡(luò)柵欄覆蓋增強(qiáng)算法［J］.傳感技術(shù)學(xué)報(bào)，2015，28（7）：1051-1057.

［3］Chen A，Kumar S，Lai T H.Designing Localized Algorithms for Barrier Coverage［C］//Proceedings of the 13th Annual ACM Inter?national Conference on Mobile Computing and NetworkingACM，2007：63-74.

［4］班冬松，溫俊，蔣杰，等.移動(dòng)無線傳感器網(wǎng)絡(luò)k-柵欄覆蓋構(gòu)建算法［J］.Journal of Software，2011，22（9）：2089-2103.

［5］郭新明.高效無線傳感器網(wǎng)絡(luò)強(qiáng)k-柵欄覆蓋節(jié)能算法［J］.計(jì)算機(jī)應(yīng)用，2013，33（8）：2104-2107.

［6］Kumar S，Lai T H，Arora A.Barrier Coverage with Wireless Sen?sors［J］.Wireless Networks，2007，13（6）：284-298.

［7］Saipulla A，Westphal C，Liu B，et al.Barrier Coverage of Line-Based Deployed Wireless Sensor Networks［C］//INFOCOM 2009，IEEE.IEEE，2009：127-135.

［8］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.

［9］Tian J，Zhang W，Wang G，et al.2D k-barrier Duty-Cycle Schedul?ing for Intruder Detection in Wireless Sensor Networks［J］.Com?puter Communications，2014，43（5）：31-42.

［10］Chen J，Li J，Lai T H.Energy-Efficient Intrusion Detection with a Barrier of Probabilistic Sensors：Global and Local［J］.Wireless Communications IEEE Transactions on，2013，12（9）：4742-4755.

［11］Kumar S，Lai T H，Posner M E，et al.Optimal Sleep-Wakeup Algo?rithms for Barriers of Wireless Sensors［C］//Broadband Communi?cations，Networks and Systems，2007.BROADNETS 2007.Fourth International Conference on.IEEE，2007：327-336.

［12］Mostafaei H，Meybodi M R.An Energy Efficient Barrier Coverage Algorithm for Wireless Sensor Networks［J］.Wireless Personal Communications，2014，77（3）：2099-2115.

［13］羅卿，林亞平，王雷，等.傳感器網(wǎng)絡(luò)中基于數(shù)據(jù)融合的柵欄覆蓋控制研究［J］.電子與信息學(xué)報(bào)，2012，34（4）：825-831.

［14］Chen D Z，Gu Y，Li J，et al.Algorithms on Minimizing the Maxi?mum Sensor Movement for Barrier Coverage of a Linear Domain［J］.Discrete&Computational Geometry，2012，50（2）：374-408.

［15］Eftekhari M，Kranakis E，Krizanc D，et al.Distributed Algorithms for B Arrier Coverage Using Relocatable Sensors［J］.Proceedings of the Annual Acm Symposium on Principles of Distributed Com?puting，2013：383-392.

［16］He S，Gong X，Zhang J，et al.Barrier Coverage in Wireless Sensor Networks：From Lined-Based to Curve-Based Deployment［C］//IN?FOCOM，2013 Proceedings IEEEIEEE，2013：470-474.

［17］Kumar S，Lai T H，Balogh J.on-Coverage in a Mostly Sleeping Sensor Network［J］.ProcAcm Mobicom，2004，14（3）：277-29.

戴光麟（1979-），男，漢族，浙江工業(yè)大學(xué)計(jì)算機(jī)學(xué)院講師，博士研究生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)；

方凱（1992-），男，漢族，浙江工業(yè)大學(xué)計(jì)算機(jī)學(xué)院碩士研究生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)；

毛科技（1979-），男，漢族，浙江工業(yè)大學(xué)計(jì)算機(jī)學(xué)院副教授，博士，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、數(shù)據(jù)挖掘，maokeji@ zjut.edu.cn。

Segmented Scheduling Algorithm of Barrier Coverage in Wireless Sensor Networks Based OnIntrusion Model*

DAI Guanglin，F(xiàn)ANG kai，DAI Guoyong，XU Hui，MAO Keji*
（College of Computer Science and Technology，Zhejiang University of Technology，Hangzhou 310023，China）

Barrier coverage of Wireless Sensors Networks has played a vital role in intrusion detection.How to schedule the barriers and extend the network lifetime at last has become one of the key issues in this area.Most re?searches choose to focus on the point that how to design a reasonable scheduling algorithm in Wireless Sensor Sys?tem，which can extend the network lifetime by activating sensor nodes in a time-sharing system to some extent. However，only relying on the timed scheduling for sensor nodes can hardly extend the network lifetime sharply. Therefore，by combining time sharing with segmentation，we designed a scheduling algorithm of barrier in wireless sensor networks in this article.Based on the analysis to the behavior feature of intruders，the algorithm builds the re?lated trajectory model of intruders，predicts the area of barrier that intruders might traverse，and then activates barri?ers piecewise，which can not only reduce energy loss of sensor nodes greatly but ensure a higher detection rate of in?truders at the same time.The emulation experiment results finally proved our assumption that the algorithm combin?ing time sharing with segmentation can extend the network lifetime by a large margin，especially compared to the tra?ditional timed scheduling algorithm.

wsn；invasion target modeling；scheduling algorithm；energy saving

TP393

A

1004-1699（2016）05-0745-06

項(xiàng)目來源：國(guó)家自然科學(xué)基金項(xiàng)目（61379023）；浙江省自然科學(xué)基金項(xiàng)目（LQ12F02015）；浙江省公益性技術(shù)應(yīng)用研究計(jì)劃項(xiàng)目（2015C31066）；浙江省計(jì)算機(jī)科學(xué)與技術(shù)重中之重學(xué)科基金項(xiàng)目（ZC323014074）

2016-01-18修改日期：2016-02-22