张瑞华　程合友　梁宇

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



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

张瑞华1程合友2梁宇1

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

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

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

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

1事……