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