基于最大流最小割算法的事件检测方案*

张瑞华　程合友　梁宇

(1.山东大学 计算机科学与技术学院， 山东 济南 250101； 2.山东省轻工集体经济科技信息研究所， 山东 济南 250014)



基于最大流最小割算法的事件检测方案*

张瑞华1程合友2梁宇1

(1.山东大学 计算机科学与技术学院， 山东 济南 250101； 2.山东省轻工集体经济科技信息研究所， 山东 济南 250014)

摘要：文中把最大流最小割算法应用于无线传感网络的事件检测中,针对边沿陡峭的事件，设计事件区域检测算法(G-Cut).该算法首先将相邻节点的传感数据转化为权值，形成流网络；利用最大流最小割算法切割流网络，获得事件边界；再根据上传信息隐含的方向，确定事件区域.以野外火灾为例进行仿真实验，结果表明：文中算法事件检测准确度高，节点计算量低；针对多事件区域，在不增加节点计算量和通信量的情况下，仍可保证其检测准确度.

关键词：无线传感网络；最大流最小割算法；事件检测；Boykov新算法；多事件区域

基于上述问题，文中首次把最大流最小割算法应用于无线传感网络的事件检测中,针对边沿陡峭的事件，设计事件区域检测算法G-Cut，该算法将传感节点的传感数据转化为邻居之间的权值，形成节点之间的权值网络；利用连通集合相邻关系得到最大流最小割算法的初始输入集合Si、Ti，进而形成流网络；采用最大流最小割算法根据节点间的权值划分流网络，将网络节点分成集合So和集合To，得到事件边界，并根据上传信息时隐含的方向确定事件区域.

1事件检测算法

事件检测算法(G-Cut)执行过程如图1所示.图中ωi表示相连两节点的权值.

图1　算法实现过程Fig.1　Procedures for realizing the algorithm

1.1　权值函数定义

为减少信息传输量，当节点p的传感数据Ip>∂0时，才与其邻居交换信息.其中，∂0是有事件发生时节点读数的阈值，用户可根据实际应用环境预先设定.节点获得邻居信息后，根据式(1)计算自己与邻居之间的权值Wp,q，该权值的定义类似文献[14]的式(7)，即图像分割时确定像素点差距的函数.

(1)

式中,Wp,q是节点p和q之间的权值,κ、C是放大系数,δ是给定的待测环境变量的最大值,Iq是节点q的传感数据,dist(p,q)是节点p、q之间的欧式距离.

计算得到的权值作为最终形成的流网络相应边上的容量.为了利用最大流最小割算法将网络从邻居节点传感数据差距最大处分开，设计权值函数时，需要保证节点之间传感数据差距越大得到的权值越小，系数κ的存在使计算的权值是整数.

1.2　权值网络的形成

(1)网络初始化.在监测区域均匀布置传感节点后，所有节点泛洪将自身信息(Ni,Xi,Yi)上传给sink，Ni是节点i的ID号，(Xi,Yi)是节点i的坐标.sink节点根据接收的信息还原出监测区域内节点布局情况，如图1(a)所示.随后网络进入监测状态.

(2)节点信息处理.针对边沿陡峭的事件，在事件区域内部或无事件发生的区域，相邻节点传感数据相差不大，其权值相对较大；在事件边界两侧相邻节点传感数据变化最大，其权值相对较小.因此，为减少上传信息量，节点只上传较小的权值，即当Wp,q<∂时，p、 q中传感数据较大的节点将信息上传给sink，如式(2)所示.∂是根据应用环境设置的上传界限.∂值的设置对检测结果没有影响，只影响上传权值的节点数量，与通信量有关.

(2)

上传信息隐含方向的好处是多事件发生时，sink节点仍可以根据节点上传的信息确定区域方向，避免二义性.

节点信息上传后，在sink节点处形成不完整的权值网络，如图1(b)所示.

(3)sink信息处理.sink节点根据上传信息决策事件的发生.若没有收到上传信息，则没有事件发生；否则有事件发生.若有事件发生按以下步骤处理：

① sink根据节点上传的信息(Np,Nq,Wp,q)得到最初的并不完整的节点权值网络拓扑，如图1(b)所示.

② sink将不完整的权值网络拓扑中邻居之间没有权值的边补充权值，得到完整的权值网络拓扑，如图1(c)所示.因为基于最大流最小割划分网络的原理是切割边的权值最小，由前面的论述可知，没有上传权值的区域不会是事件边界，也不是要切割的边，所以要使权值尽可能地大，以免影响算法效果.

1.3　权值网络转化为流网络

初始化Ti、Si集合.sink扫描生成权值网络拓扑，进行最大流最小割算法初始化.因为最大流最小割算法的输入为初始的源节点集合Si、汇节点集合Ti，因此，必须根据上传信息，确定这两个集合的初始值.该算法的伪代码如下所示.

算法1 initialize()—sink初始化集合Ti,Si.

/***寻找所有的连通区域***/

扫描生成的权值网络,为屏蔽上传权值的差异，对于所有的邻居节点i和j

ifWi,j=∞ then

else

endif

∀ nodei∈A1

节点j加入集合A1;

else

节点j加入集合B1;

end if

A1节点所覆盖的区域是第1个连通区域.

重复上述步骤,直到发现所有的连通区域A1,A2，…，Ak

/***寻找所有的相连集合对***/

∀ nodei∈Ai

if ∃ nodej∈Aj&& nodeiandj是邻居 then

Ai、Aj是相连集合对;

end if

/*** 初始化集合Si,Ti***/

∀相连集合对(Ai,Aj)

扫描集合对所有节点i,j，i∈Ai&&j∈Aj&& 节点i、j是邻居

ifWi,j是节点i上传 then

初始化Si=Ai，Ti=Aj;

else

初始化Si=Aj，Ti=Ai;

end if

在该算法中，若只有一个事件区域，找到两个连通集合；若有k个事件区域，则找到k+1个连通集合.如图1(c)所示，其中外围16个节点属于Ti集合，内层9个节点属于Si集合.

任意选择两个节点t、s，令t∈Ti,s∈Si，即形成从s到t的流网络，直接调用新最大流最小割算法.

1.4　确定事件区域

调用新最大流最小割算法.输出结果如图1(d)所示.此时可以找到事件边界.根据上传信息时隐含的方向确定事件区域.

最大流最小割算法是图像分割中应用比较成熟的方法.几种常用的最大流最小割算法有：Ford-Fulkerson 算法、预流推进算法和Boykov的新算法[14].通过比较，选用Boykov的新算法作为文中G-Cut的基础算法.

2仿真实验

2.1　实验环境部署

本实验用Visual Studio 2010 编程模拟仿真，用MATLAB生成图表，在400 m×400 m的监测区域内均匀布置2 500个节点.利用Manolakos等[15]提出并由Manatakis等经真实火灾实验验证正确的野外火灾的一个着火点的温度场模型，推算出野外火灾事件区域温度场模型(见图2)，并依照此模型为传感器节点赋初始温度值.从图2的模型可以看出，等距离火灾温度变化最大处位于火灾边界，故野外火灾属于边沿陡峭事件.图中D表示火灾事件中心到外围的距离.

图2　二维野外火灾事件区域模型Fig.2　Two-dimensional wildfire event region model

2.2　实验参数设置

由权值计算公式(1)可知，传感器部署以后，dist(p,q)已知.δ是火灾温度最大值，根据火灾模型取δ=800 ℃，令κ=1 000.

2.2.1参数C的确定

当事件区域是以(197 m,193 m)为圆心，半径为128 m的圆时，取∂=800，根据W的变化关系，取不同的参数C得到不同结果，如表1所示.

图3　不同C的权值W的变化趋势Fig.3　Function of W under different C

表1不同参数C下的测试结果

Table 1　Test results corresponding to different parameter C

检测准确度计算方法是算法检测正确的节点数除以实际事件区域节点数.此事件区域实际节点数为1 263，利用此算法，当C=0.01时，算法检测到的事件节点数为1 217，算法正确检测的事件节点数为1 191，其算法检测准确率为94.30%.

由图3可见，对于不同的C值，权值变化速度不同，仿真环境d<200，当C=0.01时包含整个权值变化过程.由表1可以看出，在一定错误范围内，C=0.01时，检测准确率更高.相应地，当d<700范围内时，取C=0.1时包含整个权值变化过程.实际应用时根据不同密度取不同的参数，可使结果更加准确，C的确定与节点部署密度、当地具体气候等条件有关，应根据具体情况取合理值.根据仿真实验部署环境，本实验取C=0.01.

2.2.2参数∂的确定

对于参数∂，当权值W<∂时上传.∂的取值影响通信量，对正确率影响不大.表2 示出了∂对通信量和正确率的影响.

表2不同参数∂下的测试结果

Table 2　Test results corresponding to different parameter ∂

由表2可以看出，上传节点个数随∂的增大而增加.这是由于∂增大，可上传的权值数量随之增加，检测的准确率也略有增加.因此在实际应用中，可以根据使用者对误差的容忍程度选择合适的∂值，从而节约能量.

2.3　实验结果

2.3.1单事件区域

当事件区域为圆形区域,其半径为128 m，圆心在(197 m,193 m)，且∂0=50，∂=800，δ=800，C=0.01时，检测结果与火灾事件的相符度，仿真结果如图4所示,图中X、Y分别为坐标.

图4中，“*”区域是失判区域，即算法没有检测到的真实事件区域，“+”区域是误判区域，即算法检测错误的区域，“小方框”区域是算法检测正确的区域.从图中可以看出所得到的仿真结果与原始事件区域略有偏差.之所以会产生一定的误差是由于本算法基于最大流最小割，其工作原理是根据节点间权值切割网络，理论上切割的区域应为火灾边界温度变化最快的点连接而成的区域，而实际实施过程中，节点为离散分布，仅用两点间的权值模拟火灾温度变化趋势，所得结果可能为温度变化最快点附近ξ范围内某一点，因此实际结果会与理论分析有一定误差.

图4　单事件的仿真结果Fig.4　Simulation results of a single event region

2.3.2多事件区域

本算法对于多个事件区域，可在不增加计算量的前提下，避免二义性，保证准确性.当事件区域为两个半径为64 m时圆心分别在(117 m,113 m)和(293 m,290 m)的圆形区域，且设置相同的参数时，其仿真结果如图5所示.

图5中，“*”区域是失判区域，“+”是误判区域，“小方框”是算法检测正确的区域.因为该算法利用连通集合相邻关系得到初始化集合T、S时，无论几个事件区域，事件内部的节点都已经包含在S或T内，调用新最大流最小割算法可找到事件边界.再利用上传信息时隐含的传感数据大小关系，可以判定T和S究竟哪个是事件区域，因此，本算法对于多个事件区域，仍可以在不增加计算量的前提下保证准确性.

图5　多事件的仿真结果Fig.5　Simulation results of a multi-event region

2.2.3检测准确度

取不同的事件区域大小，经50次统计平均，检测准确度分别为：86.4%(Iso-Map)、92.6%(G-Cut)、94.1%(TinyDB).本算法G-Cut的准确度在TinyDB[11]和Iso-Map[12]算法之间.因为TinyDB算法上传所有节点的信息，只在形成等值线图时有一些误差；Iso-Map算法上传关键点的信息，误差相对较大；本算法G-Cut上传事件边界一定宽度范围内邻居间的权值，在权值网络划分时会有一定偏差.

2.2.4通信量

在保证准确性的前提下，本算法G-Cut的通信量介于TinyDB和Iso-Map算法之间，其通信量α与归一化节点密度β之间的关系如图6所示.因为TinyDB是上传所有信息，所以随着节点密度增加，通信量增大.Iso-Map上传关键点的信息，因此通信量不随节点密度增加而增大.文中的G-Cut算法上传边界一定宽度范围内的权值，因此会比TinyDB通信量少，但比Iso-Map多，且随节点密度增加而增大.

图6　通信量与节点密度的关系Fig.6　Relationship between the communication traffic amount and the density of nodes

3结论

针对某类边沿陡峭的事件检测，文中设计了一种基于最大流最小割算法的事件检测方案.基于野外火灾模型的仿真实验表明，最大流最小割算法用于检测无线传感网络事件时，与基于等值线图的事件检测算法相比检测准确度高，通信量略有增加；可直接找到事件边界再根据上传信息时隐含的方向判定事件区域，不需要模式匹配，解决了事件模型不易确定的难题；用于多事件区域时仍可保证其准确性，且不需要增加计算量.

参考文献:

[1]CHEN Dan,LIU Zhixin,WANG Lizhe.Natural disaster monitoring with wireless sensor networks：a case study of data-intensive applications upon low-cost scalable systems [J].Mobile Networks and Applications,2013,18(5)：651-663.

[2]BENKHELIFA Imane,NOUALI-TABOUDJEMAT Nadia,MOUSSAOUI Samira.Disaster management projects using wireless sensor networks：an overview [C]∥ Proceedings of the 28th International Conference on Advanced Information Networking and Applications Workshops.Victoria：IEEE,2014：605-610.

[3]XU Guobao,SHEN Weiming,WANG Xianbin.Applications of wireless sensor networks in marine environment monitoring：a survey [J].Sensors,2014,14(9):16932-16954.

[4]MARCHENKO Nikolaj,ANDRE Torsten,BRANDNER Guenther.An experimental study of selective cooperative relaying in industrial wireless sensor networks [J]. IEEE Transactions on Industrial Informatics,2014,10(3)：1806-1816.

[5]ZHENG Yujiao,CAO Nianxia,THAKSHILA Wimalajeewa.Compressive sensing based probabilistic sensor management for target tracking in wireless sensor networks [J].IEEE Transactions on Signal Processing,2015,63(22)：6049-6060.

[6]ZHANG Fan,CHEN Jiming,LI Hongbin,et al.Distributed active sensor scheduling for target tracking in ultrasonic sensor networks [J].Mobile Networks and Applications,2012,17(5)：582-593.

[7]曹冬磊，曹建农，金蓓弘.一种无线传感器网络中事件区域检测的容错算法 [J].计算机学报，2007,30(10)：1770-1776.

CAO Dong-Lei,CAO Jian-nong,JIN Bei-hong.A fault-tolerant algorithm for event region detection in wireless sensor networks [J].Chinese Journal of Computers,2007,30(10)：1770-1776.

[8]徐小龙,耿卫建,杨庚,等.高效容错的无线传感网事件及其边界检测算法 [J].计算机研究与发展,2014,51(5):997-1008.

XU Xiao-long,GENG Wei-jian,YANG Geng，et al.An efficient fault-tolerant event and event boundary detection algorithm for wireless sensor networks [J].Journal of Computer Research and Development,2014,51(5):997-1008.

[9]郑志平，胡圣波，舒恒.一种无线传感网络中的时空事件检测方法 [J].计算机仿真,2010,27(8):114-117.

ZHENG Zhi-ping,HU Sheng-bo,SHU Heng.A spatio tanporal event detection approach for wireless sensor network [J].Computer Simulation,2010,27(8):114-117.

[10]石胜飞,张伟,李建中.一种基于模式匹配与相关性分析的事件检测算法 [J].计算机研究与发展,2014,51(8):1871-1879.

SHI Sheng-fei,ZHANG Wei,LI Jian-zhong.A complex event detection algorithm based on correlation analysis [J].Journal of Computer Research and Development,2014,51(8):1871-1879.

[11]JOSEPH M Hellerstein,WEI Hong,SAMUEL Madden,et al.Beyond average：toward sophisticated sensing with queries [C]∥Proceedings of IEEE/ACM Information Processing in Sensor Networks(IPSN).Palo Alto：IEEE/ACM,2003:1-16.

[12]LI Mo,LIU Yunhao.Iso-Map：energy efficient contour mapping in wireless sensor networks [J].IEEE Transactions on Knowledge and Data Engineering,2010,22(5)：699-710.

[13]DRAGANA Bajovic,BRUNO Sinopoli,JOAO Xavier.Sensor selection for event detection in wireless sensor networks [J].IEEE Transactions on Signal Processing,2011,59(10)：4938-4953.

[14]BOYKOV Yuri,FUNKA-LEA Gareth.Graph cuts and efficient N-D image segmentation [J].International Journal of Computer Vision,2006,70(2):109-131.

[15]MANOLAKOS E S,MANATAKIS D V,XANTHOPOULOS G.Temperature field modeling and simulation of wireless sensor network behavior during a spreading wildfire [C]∥Proceedings of the 16th European Signal Processing Conference.Lausanne：IEEE,2008:1-5.

责任编辑：牛晓光

Event Detection Scheme Based on Max-Flow/Min-Cut Algorithm

ZHANGRui-hua1CHENGHe-you2LIANGYu1

(1. School of Computer Science and Technology, Shandong University, Jinan 250101, Shandong, China；

2. Shandong Light Industry Collective Economy Science and Technology Information Institute, Jinan 250014, Shandong, China)

Abstract:In this paper, the max-flow/min-cut algorithm is applied to the event detection in wireless sensor networks, and an event detection algorithm (G-Cut) is proposed for boundary-abrupt events. In the algorithm, firstly, the sensing data of adjacent nodes are transformed into weight values, and thus a flow network is formed. Then, the event boundary is obtained by using the max-flow/min-cut algorithm to cut the flow network. Finally, the event area is determined according to the direction implied in upload information. Simulation results on wildfire events show that the proposed algorithm achieves a high accuracy of event detection with a small computation amount of nodes, and for multi-event regions, it can guarantee the detection accuracy without increasing the computation amount and traffic of nodes.

Key words:wireless sensor networks; max-flow/min-cut algorithm; event detection; Boykov new algorithm; multi-event region

doi：10.3969/j.issn.1000-565X.2016.01.020

中图分类号：TP393

作者简介：张瑞华(1969-)，女，博士，副教授，主要从事无线传感器网络研究.E-mail：ruihua_zhang@sdu.edu.cn

*基金项目：国家自然科学基金资助项目(61202015)；国家"863"计划项目(2013AA013202)

收稿日期：2015-07-15

文章编号：1000-565X(2016)01- 0139- 06

Foundation items： Supported by the National Natural Science Foundation of China(61202015)and the National High-tech R&D Program of China(863 Program)(2013AA013202)