移動傳感器隨機事件捕獲*

劉解放,趙　斌,周　寧

(1.鹽城工學院信息工程學院,江蘇 鹽城 224051;2.北京工業大學計算機學院,北京 100022)

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

MS在入侵檢測中的應用吸引了很多研究者的關注。他們也獲得了一些關于MS性能的研究結果。文獻[6]給出在移動傳感網中影響覆蓋質量的參數——MS的數量、速度、速度模式和事件動態;并且假設入侵發生在檢測區的一個或多個固定點上,而不是發生在一個隨機點。文獻[7]研究了單個MS沿著圓形周長的入侵檢測。文獻[8]研究了單個MS沿著矩形周長的入侵檢測。

然而,前面提到的研究主要集中在感興趣區域具有特定的形狀,如圓曲線[7]或矩形[8],固定的形狀限制了模型的使用范圍。我們感興趣的是:當感興趣區域為任何形狀的閉環時,多個MS入侵檢測的性能;這里,閉環表示應用MS覆蓋感興趣區域的任何計劃路徑;它可以是一個二維區域或一組相互連接的路徑。因此,本文提到的入侵檢測在任何形狀的閉環內,模型可以為多個MS應用場景提供建模方法,如路徑規劃,目標搜索和巡查。它可以作為這些應用程序的一個性能分析工具。這里還有其他相關的工作[9-12]。

1　入侵捕獲分析

1.1　場景建模

這里研究的檢測區域是一個任何形狀的閉環,用C表示。C的長度為L。我們建立了一個擁有一個或多個MS的模型。用N表示C上的MS數量。在模型中,MS沿C以固定的速度V移動來檢測入侵。MS可以順時針或逆時針移動。由于模型在移動方向上具有通用性,因此假設每個MS將順時針移動。

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

假設入侵模型如下:

(1)入侵一個接一個的獨立發生。一個入侵隨機發生在C上某點,這意味著此點是一個隨機變量。而且,這個變量在C上服從均勻分布。

(2)一旦入侵發生在C上某點,它會停留此點上一個隨機的時間長度,然后消失。這個時間長度服從均值為1/μ的指數分布。

(3)定義發生在C上的入侵,當且僅當它發生在C上一點或發生后停留在該點。此外,在任何時間點t,模型中有兩種可能的狀態:狀態S1在t時刻沒有入侵發生,以及狀態S2在t時刻至少有一個入侵發生。因為我們假設入侵一個接一個發生,這將有兩種時間間隔:一種是S1沒有入侵發生的時間間隔,另一個是S2入侵發生的時間間隔。因此,S1和S2的時間間隔是交替的。我們假設S1和S2的持續時間長度是隨機的,且相互獨立的。S1的持續時間長度服從均值為1/λ的指數分布,則S2的時間長度服從均值為1/μ的指數分布。

(4)我們指定一個起始時間點作為即時零點。在該時刻,任何MS開始移動和入侵檢測。

入侵發生時,當它在任何一個MS的感測范圍內,稱為“捕獲”;否則稱為“漏捕”。

入侵捕獲可能存在兩種情況:一是入侵一出現,就被發現;二是開始入侵沒被發現,不過消失前被發現。

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

假設MS的感測范圍是半徑為r的圓形區域,但是,在以下的分析中,我們簡化圓形區域為曲線,長度為2r。簡化的目的是讓數學模型和解決方案更容易處理。事實上,當C非常大,r相對足夠小時,這是一個合理的近似。如果入侵發生的點與C上MS之間的距離小于r,MS可以感測到入侵的發生。

1.2　問題解決

基于上述假設,解決了以下問題。

(1)以恒定速度V移動的N個MS對入侵的漏捕概率是多少;

(2)N個MS從起始時間點到首次捕獲入侵所花費的平均時間。

1.3　數學推導

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

定理1:

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

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

(1)

(2)

現在考慮MS首次捕獲入侵所花費的時間,用Tcap表示。E(Tcap)表示Tcap的均值,也即MS首次捕獲入侵的平均時間。

然后,可得到:

類似單個MS在一個感興趣的圓形區域的感測場景的模型,可以推出下面引理。

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

2　評估

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

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

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

圖1　不同N的漏捕概率

圖2　不同V的漏捕概率

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

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

圖3　不同N的平均時間

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

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

當V增加時,平均時間降低。此外,還觀察到,當X軸V固定時,平均時間隨N的增加而降低。

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

圖4　不同V的平均時間

圖5　不同μ的平均時間

當μ增加時,平均時間降低。此外,還觀察到,當X軸μ固定時,平均時間隨N的增加而降低。

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

圖6　不同λ的平均時間

圖7　不同L的平均時間

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

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

當L增加時,平均時間增加。此外,還觀察到,當X軸L固定時,平均時間隨N的增加而降低。

讓λ=1個單位,μ=1個單位,L=1 000個單位和V=1個單位;通過增加MS探測區域的半徑r從0.1到10個單位,N分別為1、5和10個單位,比較了平均時間。如圖8所示。

圖8　不同r的平均時間

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

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

圖9　不同μ的平均時間

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

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

圖10　不同λ的平均時間

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

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

圖11　不同L的平均時間

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

讓λ=1個單位,μ=1個單位,L=1 000個單位;通過增加MS探測區域半徑r從0.1到10個單位,N分別為1和10個單位,V分別為0.1、1和2個單位,比較了平均時間。如圖12所示。

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

圖12　不同r的平均時間

3　結論

當一組周期性沿感興趣區域移動的MS用于入侵檢測時,我們假設這個感興趣區域是一個任何形狀的閉環的基礎上,構建了一個隨機檢測模型,最終

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

參考文獻:

[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]陳曉華,徐楨,芮立揚.純方位目標定位觀測器軌跡的快速優化算法[J].傳感技術學報,2009,22(5):669-674.

[4]賈思強,高翔,陸起涌.無線傳感器網絡中的分布式動態路徑規劃算法[J].傳感技術學報,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].軟件學報,2013,24(2):215-229.

[10]汪洋,林闖,李泉林,等.基于非合作博弈的無線網絡路由機制研究[J].計算機學報,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-),男,河南周口人,講師,碩士,主要研究方向為無線傳感器網絡、計算機網絡安全,ljf-it@163.com;

周寧(1972-),男,江蘇鹽城人,副教授,碩士,主要研究方向為無線傳感器網絡,計算機網絡,人工智能,ningzh@ycit.cn。