计算机科学与技术

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

展开
  • 1. 山东大学 计算机科学与技术学院,山东 济南 250101; 2. 山东省轻工集体经济科技信息研究所,山东 济南 250014
张瑞华( 1969-) ,女,博士,副教授,主要从事无线传感器网络研究.

收稿日期: 2015-07-10

  修回日期: 2015-09-17

  网络出版日期: 2015-12-09

基金资助

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

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

Expand
  • 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
张瑞华( 1969-) ,女,博士,副教授,主要从事无线传感器网络研究.

Received date: 2015-07-10

  Revised date: 2015-09-17

  Online published: 2015-12-09

Supported by

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

摘要

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

本文引用格式

张瑞华 程合友 梁宇 . 基于最大流最小割算法的事件检测方案[J]. 华南理工大学学报(自然科学版), 2016 , 44(1) : 139 -144 . DOI: 10.3969/j.issn.1000-565X.2016.01.020

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.
文章导航

/