移動(dòng)傳感器隨機(jī)事件捕獲*

劉解放,趙　斌,周　寧

(1.鹽城工學(xué)院信息工程學(xué)院,江蘇 鹽城 224051;2.北京工業(yè)大學(xué)計(jì)算機(jī)學(xué)院,北京 100022)

移動(dòng)傳感器MS(Mobile Sensor)作為實(shí)現(xiàn)無(wú)線傳感應(yīng)用的一種方法備受關(guān)注和研究。相比固定傳感器,若要覆蓋相同感興趣區(qū)域,由于MS的移動(dòng)性,則所需數(shù)量更少。這使得使用MS比使用固定的更經(jīng)濟(jì)。此外,固定傳感器部署上的改變比MS更昂貴。MS技術(shù)和低功耗的嵌入式系統(tǒng)的最新進(jìn)展已經(jīng)改善了傳感應(yīng)用中動(dòng)態(tài)檢測(cè)的可行性[1-4]。由于它們的移動(dòng)性,較少數(shù)量的MS可以覆蓋一個(gè)大的感知域[5]。由于MS能夠交換彼此的信息,只要相互的通信范圍有交叉,然后給MS合理地設(shè)計(jì)一個(gè)程序,就能提高網(wǎng)絡(luò)連接的可靠性,但是,由于一個(gè)MS覆蓋的瞬時(shí)區(qū)域與一個(gè)相同檢測(cè)類型的固定設(shè)備覆蓋的區(qū)域是一樣的。因此,如果缺乏合理的移動(dòng)軌跡設(shè)計(jì),MS可能無(wú)法獲得優(yōu)于固定檢測(cè)裝置的檢測(cè)質(zhì)量,尤其是高度動(dòng)態(tài)的感測(cè)區(qū)。

MS在入侵檢測(cè)中的應(yīng)用吸引了很多研究者的關(guān)注。他們也獲得了一些關(guān)于MS性能的研究結(jié)果。文獻(xiàn)[6]給出在移動(dòng)傳感網(wǎng)中影響覆蓋質(zhì)量的參數(shù)——MS的數(shù)量、速度、速度模式和事件動(dòng)態(tài);并且假設(shè)入侵發(fā)生在檢測(cè)區(qū)的一個(gè)或多個(gè)固定點(diǎn)上,而不是發(fā)生在一個(gè)隨機(jī)點(diǎn)。文獻(xiàn)[7]研究了單個(gè)MS沿著圓形周長(zhǎng)的入侵檢測(cè)。文獻(xiàn)[8]研究了單個(gè)MS沿著矩形周長(zhǎng)的入侵檢測(cè)。

然而,前面提到的研究主要集中在感興趣區(qū)域具有特定的形狀,如圓曲線[7]或矩形[8],固定的形狀限制了模型的使用范圍。我們感興趣的是:當(dāng)感興趣區(qū)域?yàn)槿魏涡螤畹拈]環(huán)時(shí),多個(gè)MS入侵檢測(cè)的性能;這里,閉環(huán)表示應(yīng)用MS覆蓋感興趣區(qū)域的任何計(jì)劃路徑;它可以是一個(gè)二維區(qū)域或一組相互連接的路徑。因此,本文提到的入侵檢測(cè)在任何形狀的閉環(huán)內(nèi),模型可以為多個(gè)MS應(yīng)用場(chǎng)景提供建模方法,如路徑規(guī)劃,目標(biāo)搜索和巡查。它可以作為這些應(yīng)用程序的一個(gè)性能分析工具。這里還有其他相關(guān)的工作[9-12]。

1　入侵捕獲分析

1.1　場(chǎng)景建模

這里研究的檢測(cè)區(qū)域是一個(gè)任何形狀的閉環(huán),用C表示。C的長(zhǎng)度為L(zhǎng)。我們建立了一個(gè)擁有一個(gè)或多個(gè)MS的模型。用N表示C上的MS數(shù)量。在模型中,MS沿C以固定的速度V移動(dòng)來(lái)檢測(cè)入侵。MS可以順時(shí)針或逆時(shí)針移動(dòng)。由于模型在移動(dòng)方向上具有通用性,因此假設(shè)每個(gè)MS將順時(shí)針移動(dòng)。

假設(shè)N個(gè)MS均勻地分布在C上,這意味著任意兩個(gè)相鄰的MS間的距離為L(zhǎng)/N。假設(shè)每個(gè)MS的感測(cè)半徑相同且為r。當(dāng)L/N≤2r時(shí),所有的MS感測(cè)范圍可全面覆蓋C,所有的入侵都肯定被捕獲。否則(當(dāng)L/N>2r),MS可能漏捕入侵。對(duì)于本文的目的,我們考慮的情況是L/N>2r。

假設(shè)入侵模型如下:

(1)入侵一個(gè)接一個(gè)的獨(dú)立發(fā)生。一個(gè)入侵隨機(jī)發(fā)生在C上某點(diǎn),這意味著此點(diǎn)是一個(gè)隨機(jī)變量。而且,這個(gè)變量在C上服從均勻分布。

(2)一旦入侵發(fā)生在C上某點(diǎn),它會(huì)停留此點(diǎn)上一個(gè)隨機(jī)的時(shí)間長(zhǎng)度,然后消失。這個(gè)時(shí)間長(zhǎng)度服從均值為1/μ的指數(shù)分布。

(3)定義發(fā)生在C上的入侵,當(dāng)且僅當(dāng)它發(fā)生在C上一點(diǎn)或發(fā)生后停留在該點(diǎn)。此外,在任何時(shí)間點(diǎn)t,模型中有兩種可能的狀態(tài):狀態(tài)S1在t時(shí)刻沒有入侵發(fā)生,以及狀態(tài)S2在t時(shí)刻至少有一個(gè)入侵發(fā)生。因?yàn)槲覀兗僭O(shè)入侵一個(gè)接一個(gè)發(fā)生,這將有兩種時(shí)間間隔:一種是S1沒有入侵發(fā)生的時(shí)間間隔,另一個(gè)是S2入侵發(fā)生的時(shí)間間隔。因此,S1和S2的時(shí)間間隔是交替的。我們假設(shè)S1和S2的持續(xù)時(shí)間長(zhǎng)度是隨機(jī)的,且相互獨(dú)立的。S1的持續(xù)時(shí)間長(zhǎng)度服從均值為1/λ的指數(shù)分布,則S2的時(shí)間長(zhǎng)度服從均值為1/μ的指數(shù)分布。

(4)我們指定一個(gè)起始時(shí)間點(diǎn)作為即時(shí)零點(diǎn)。在該時(shí)刻,任何MS開始移動(dòng)和入侵檢測(cè)。

入侵發(fā)生時(shí),當(dāng)它在任何一個(gè)MS的感測(cè)范圍內(nèi),稱為“捕獲”;否則稱為“漏捕”。

入侵捕獲可能存在兩種情況:一是入侵一出現(xiàn),就被發(fā)現(xiàn);二是開始入侵沒被發(fā)現(xiàn),不過(guò)消失前被發(fā)現(xiàn)。

我們用P[caputure]表示入侵捕獲概率,用P[loss]表示入侵漏捕概率。事實(shí)上,對(duì)于任何一對(duì)入侵i和j,它們漏捕概率是相等的。最后,我們用Pr[E]表示一個(gè)事件E發(fā)生的概率。

假設(shè)MS的感測(cè)范圍是半徑為r的圓形區(qū)域,但是,在以下的分析中,我們簡(jiǎn)化圓形區(qū)域?yàn)榍€,長(zhǎng)度為2r。簡(jiǎn)化的目的是讓數(shù)學(xué)模型和解決方案更容易處理。事實(shí)上,當(dāng)C非常大,r相對(duì)足夠小時(shí),這是一個(gè)合理的近似。如果入侵發(fā)生的點(diǎn)與C上MS之間的距離小于r,MS可以感測(cè)到入侵的發(fā)生。

1.2　問題解決

基于上述假設(shè),解決了以下問題。

(1)以恒定速度V移動(dòng)的N個(gè)MS對(duì)入侵的漏捕概率是多少;

(2)N個(gè)MS從起始時(shí)間點(diǎn)到首次捕獲入侵所花費(fèi)的平均時(shí)間。

1.3　數(shù)學(xué)推導(dǎo)

T10表示從起始時(shí)間點(diǎn)到首次入侵發(fā)生持續(xù)的時(shí)間。T10是均值為1/λ的指數(shù)分布函數(shù)。在首次入侵發(fā)生在t0時(shí)刻的條件下,首次入侵漏捕概率屬于一個(gè)條件概率,我們把它表示P[loss|t0]。首次入侵漏捕概率表示為P[loss]。第i個(gè)入侵漏捕的概率表示為Pi[loss]。第i個(gè)入侵發(fā)生在t0時(shí)刻的條件下,且漏捕的條件概率Pi[loss|t0],其中i是一個(gè)大于1的正整數(shù)。在定理1中我們將看到Pi[loss]=P[loss]。為了計(jì)算P[loss|t0],首先要計(jì)算在t0時(shí)刻首次入侵發(fā)生在C上某點(diǎn)j的條件下漏捕的條件概率,它的條件概率表示為P[loss|j,t0]。

定理1:

附錄中給出了定理1的證明。下面我們繼續(xù)解決問題2,它涉及首次入侵捕獲的平均時(shí)間。

我們可以把定理1應(yīng)用到第i個(gè)入侵的情況中,這里涉及首次入侵漏捕的概率。類似定理1中的推理,可以得到:

(1)

(2)

現(xiàn)在考慮MS首次捕獲入侵所花費(fèi)的時(shí)間,用Tcap表示。E(Tcap)表示Tcap的均值,也即MS首次捕獲入侵的平均時(shí)間。

然后,可得到:

類似單個(gè)MS在一個(gè)感興趣的圓形區(qū)域的感測(cè)場(chǎng)景的模型,可以推出下面引理。

附錄中給出了引理1的證明。由引理1得出后續(xù)的定理2;附件中也給出了定理2的證明。

2　評(píng)估

我們選擇r=5個(gè)單位,λ=1個(gè)單位,L=1 000個(gè)單位,和μ=1個(gè)單位;然后通過(guò)增加MS的個(gè)數(shù)N從0.5到40個(gè)單位,移動(dòng)速度V分別為0.5,5和50個(gè)單位,比較了漏捕概率(圖中記為L(zhǎng)oss Probability),它是N個(gè)MS漏捕入侵的概率。如圖1所示。

當(dāng)N增加時(shí),漏捕概率大幅降低。此外,還觀察到,當(dāng)X軸N固定時(shí),漏捕概率隨V的增加而降低。

然后讓r=5個(gè)單位,λ=1個(gè)單位,L=1 000個(gè)單位,和μ=1個(gè)單位;然后以增量為0.5個(gè)單位增加速度V從0.1到4.6個(gè)單位,MS的個(gè)數(shù)N分別為1,10和50個(gè)單位,比較了漏捕概率。如圖2所示。

圖1　不同N的漏捕概率

圖2　不同V的漏捕概率

當(dāng)V增加時(shí),漏捕概率大幅降低。此外,還觀察到,當(dāng)X軸V固定時(shí),漏捕概率隨N的增加而降低。

讓r=5個(gè)單位,λ=1個(gè)單位,L=1 000個(gè)單位,和μ=1個(gè)單位;通過(guò)增加MS的個(gè)數(shù)N從0.5到40個(gè)單位,移動(dòng)速度V分別為0.5,5和50個(gè)單位,比較N個(gè)MS從起始時(shí)間點(diǎn)到首次捕獲入侵需要的平均時(shí)間(圖中記為Delay)。如圖3所示。

圖3　不同N的平均時(shí)間

當(dāng)N增加時(shí),平均時(shí)間急劇下降。此外,還觀察到,當(dāng)X軸N固定時(shí),平均時(shí)間隨V的增加而降低。

讓r=5個(gè)單位,λ=1個(gè)單位,L=1 000個(gè)單位,和μ=1個(gè)單位;以增量為0.5個(gè)單位增加速度V從0.1到4.6個(gè)單位時(shí),MS的個(gè)數(shù)N分別為1,10和50個(gè)單位,比較了平均時(shí)間。如圖4所示。

當(dāng)V增加時(shí),平均時(shí)間降低。此外,還觀察到,當(dāng)X軸V固定時(shí),平均時(shí)間隨N的增加而降低。

讓r=5個(gè)單位,λ=1個(gè)單位,L=1 000個(gè)單位和V=1個(gè)單位;通過(guò)增加μ從0.1到2個(gè),N分別為1、5和10個(gè)單位,比較了平均時(shí)間。如圖5所示。

圖4　不同V的平均時(shí)間

圖5　不同μ的平均時(shí)間

當(dāng)μ增加時(shí),平均時(shí)間降低。此外,還觀察到,當(dāng)X軸μ固定時(shí),平均時(shí)間隨N的增加而降低。

讓r=5個(gè)單位,μ=1個(gè)單位,L=1 000個(gè)單位和V=1個(gè)單位;通過(guò)增加λ從0.1到5個(gè)單位,N分別為1、5和10個(gè)單位,比較了平均時(shí)間。如圖6所示。

圖6　不同λ的平均時(shí)間

圖7　不同L的平均時(shí)間

當(dāng)λ增加時(shí),平均時(shí)間急劇降低。此外,還可以觀察到,當(dāng)X軸λ固定時(shí),平均時(shí)間隨著N的增加而降低。

然后讓r=5個(gè)單位,μ=1個(gè)單位,V=1個(gè)單位和λ=1個(gè)單位;以增量為200個(gè)單位增加閉合曲線的長(zhǎng)度L從200到2000個(gè)單位,N分別為1、5和10個(gè)單位,比較了平均時(shí)間。如圖7所示。

當(dāng)L增加時(shí),平均時(shí)間增加。此外,還觀察到,當(dāng)X軸L固定時(shí),平均時(shí)間隨N的增加而降低。

讓?duì)?1個(gè)單位,μ=1個(gè)單位,L=1 000個(gè)單位和V=1個(gè)單位;通過(guò)增加MS探測(cè)區(qū)域的半徑r從0.1到10個(gè)單位,N分別為1、5和10個(gè)單位,比較了平均時(shí)間。如圖8所示。

圖8　不同r的平均時(shí)間

當(dāng)r增加時(shí),平均時(shí)間急劇降低。此外,還觀察到,當(dāng)X軸r固定時(shí),平均時(shí)間隨著N的增加而降低。

讓r=5個(gè)單位,λ=1個(gè)單位,L=1 000個(gè)單位;然后通過(guò)增加μ從0.1到2個(gè)單位,N分別為1和10個(gè)單位,V分別為0.1、1和10個(gè)單位,比較了平均時(shí)間。如圖9所示。

圖9　不同μ的平均時(shí)間

當(dāng)μ增加時(shí),平均時(shí)間降低。此外,還觀察到,當(dāng)X軸μ固定時(shí),平均時(shí)間隨N或V的增加而降低。

讓r=5個(gè)單位,μ=1個(gè)單位,L=1 000個(gè)單位;通過(guò)增加λ從0.1到5個(gè)單位,N分別為1和10個(gè)單位,V分別為0.1、1和10個(gè)單位,比較了平均時(shí)間。如圖10所示。

圖10　不同λ的平均時(shí)間

當(dāng)λ增加時(shí),平均時(shí)間急劇降低。此外,還觀察到,當(dāng)X軸λ固定時(shí),平均時(shí)間隨N或V的增加而降低。

讓r=5個(gè)單位,μ=1個(gè)單位,λ=1個(gè)單位;然后以增量為200個(gè)單位增加閉合曲線的長(zhǎng)度L從200到2 000個(gè)單位,N分別為1和10個(gè)單位,V分別為0.1、1和10個(gè)單位,比較了平均時(shí)間。如圖11所示。

圖11　不同L的平均時(shí)間

當(dāng)L增加時(shí),平均時(shí)間增加。此外,還觀察到,當(dāng)X軸L固定時(shí),平均時(shí)間隨N或V的增加而降低。

讓?duì)?1個(gè)單位,μ=1個(gè)單位,L=1 000個(gè)單位;通過(guò)增加MS探測(cè)區(qū)域半徑r從0.1到10個(gè)單位,N分別為1和10個(gè)單位,V分別為0.1、1和2個(gè)單位,比較了平均時(shí)間。如圖12所示。

當(dāng)r增加時(shí),平均時(shí)間先是急劇降低,然后趨于緩慢。此外,還觀察到,當(dāng)X軸r固定時(shí),平均時(shí)間隨N或V的增加而降低。

圖12　不同r的平均時(shí)間

3　結(jié)論

當(dāng)一組周期性沿感興趣區(qū)域移動(dòng)的MS用于入侵檢測(cè)時(shí),我們假設(shè)這個(gè)感興趣區(qū)域是一個(gè)任何形狀的閉環(huán)的基礎(chǔ)上,構(gòu)建了一個(gè)隨機(jī)檢測(cè)模型,最終

推導(dǎo)出任意入侵漏捕概率和MS首次捕獲入侵所需平均時(shí)間的一般表達(dá)式,并且基于表達(dá)式研究了它的性能,相比較其他基于固定形狀的感興趣區(qū)域研究的結(jié)論更具有通用性和實(shí)用性。研究結(jié)果表明:MS的平均移動(dòng)速度越大、入侵持續(xù)的時(shí)間越長(zhǎng)、MS的數(shù)量越多,檢測(cè)性能越好。

參考文獻(xiàn):

[1]Bergbreiter S,Pister K,Cotsbots.An off-the-Shelf Platform for Distributed Robotics[C]//Proc of the IROS’03,Las Vegas,USA,2003:1632-1637.

[2]Sibley G T,Rahimi M H,Sukhatme G S.Robomote:a Tiny Mobile Robot Platform for Large-Scale Ad-Hoc Sensor Networks[C]//Proc of the ICRA’02,Washington,USA,2002:1143-1148.

[3]陳曉華,徐楨,芮立揚(yáng).純方位目標(biāo)定位觀測(cè)器軌跡的快速優(yōu)化算法[J].傳感技術(shù)學(xué)報(bào),2009,22(5):669-674.

[4]賈思強(qiáng),高翔,陸起涌.無(wú)線傳感器網(wǎng)絡(luò)中的分布式動(dòng)態(tài)路徑規(guī)劃算法[J].傳感技術(shù)學(xué)報(bào),2013,26(5):695-700.

[5]James San.Jacinto Mountain Reserve[EB/OL].http://www.jamesreserve.edu,2013-7-11.

[6]Bisnik N,Abouzeid A,Isler V.Stochastic Event Capture Using Mobile Sensors Subject to a Quality Metric[C]//Proc of the MobiCom’06,Los Angeles,USA,2006:98-109.

[7]Liang X,Xiao Y.Stochastic Capturing Moving Intrusions by Mobile Sensors[C]//Proc of the MulGraB’09,Fujian,China,2009:14-16.

[8]Zhang J,Xiao Y,Liang X,et al.Stochastic Event Capturing with a Single Mobile Robot in Rectangular Perimeters[J].Telecom-munication Systems Journal,2013,52(4):2519-2532.

[9]劉唐,彭艦,楊進(jìn).異構(gòu)延遲容忍移動(dòng)傳感器網(wǎng)絡(luò)中基于轉(zhuǎn)發(fā)概率的數(shù)據(jù)傳輸[J].軟件學(xué)報(bào),2013,24(2):215-229.

[10]汪洋,林闖,李泉林,等.基于非合作博弈的無(wú)線網(wǎng)絡(luò)路由機(jī)制研究[J].計(jì)算機(jī)學(xué)報(bào),2009,32(1):55-69.

[11]Chinnappen-Rimer S,Gerhard P.Hancke.Actor Coordination Using Info-Gap Decision Theory in Wireless Sensor and Actor Networks[J].International Journal of Sensor Networks,2011,10(4):177-191.

[12]Zhang F,Dojen R,Coffey T.Comparative Performance and Energy Consumption Analysis of Different AES Implementations on a Wireless Sensor Network Node[J].International Journal of Sensor Networks,2011,10(4):192-201.

劉解放(1982-),男,河南周口人,講師,碩士,主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)、計(jì)算機(jī)網(wǎng)絡(luò)安全,ljf-it@163.com;

周寧(1972-),男,江蘇鹽城人,副教授,碩士,主要研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò),計(jì)算機(jī)網(wǎng)絡(luò),人工智能,ningzh@ycit.cn。