移动传感器随机事件捕获*

刘解放,赵　斌,周　宁

(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。