一种基于无线传感网络的事件检测方法

摘要

本发明涉及一种基于无线传感网络的事件检测方法，它的过程为：(1)在事件监测区域均匀的布置相应的传感器节点，定义相邻节点间的权值函数，将节点的原始检测值，转化为邻居之间的权值，并保证节点之间检测值差距越大得到的权值越小；同时，满足一定条件的权值上传至sink节点。(2)sink节点根据传感器节点上传的信息还原出传感器网络的拓扑，补全所有节点的权值，形成完整的节点之间的权值网络；利用连通集合相邻关系得到初始的节点子集合S_in，T_in。(3)基于搜索树设计最大流算法，根据节点间的权值划分网络，将网络节点分成集合S_out和集合T_out，并保证划分开的权值和最小，即从节点检测值差距最大的地方划分开。根据最大流算法的输出结果直接找到事件边界。(4)根据上传权值时隐含的方向，进一步确定事件区域，即检测值大的节点所在区域是事件区域，其它区域为正常区域。

主权项

基于无线传感网络的事件检测方法，其特征是，具体步骤为：（1）把监测区域划分成若干个均匀的网格，节点处于每个网格的中心位置，即以节点的传感距离为半径画圆，其内接正方形的边长就是每个网格的边长；sink节点位于监测区域的任一位置；节点布置好后静止不动；（2）网络布置好后，所有N个传感器节点以泛洪方式将自身信息(ID_i,X_i,Y_i)上传给sink节点，其中i≤N，ID_i是节点i的编号，(X_i,Y_i)是节点i的位置坐标；Sink节点根据节点发来的信息还原出监测区域节点的布局情况；（3）定义权值函数并计算相邻节点间的权值；权值W(p,q)是节点p、q之间的权值，作为权值网络中边(p,q)的容量；要将传感器节点的原始检测值，转化成节点之间的权值，基于最大流最小割理论，权值函数要满足节点检测值差距越大，两节点之间的权值越小，故定义的权值函数为公式（1）：$W(p,q)=k*\exp \left(\frac{{-(I_p-I_q)}^2}{{\mathrm{c\delta }}^2}\right)*\frac{1}{\mathrm{dist}(p,q)}---\left(1\right)$其中，W(p,q)是节点p、q之间的权值，I_p是节点p的检测值，I_q是节点q的检测值，dist(p,q)是节点p、q之间的距离，δ是根据应用背景设置的某属性值的最大值，k、c是常数，引入参数k的目的是使权值为整数，参数c和δ的引入，一方面使参数容易调整，另一方面减少上传的信息量，每条边的初始剩余权值为该边的权值，即W_f(p,q)＝W(p,q)；当节点p的检测值时，才与其邻居交换一次信息，节点p与其邻居交换信息后，利用公式(1)计算权值W(p,q)；为节省能耗减少信息传输量，使处于正常区域不受事件影响的节点不上传数据，设置阈值根据实际应用环境设定，这里的阈值对检测精确度关联不大，只影响到数据传输量；（4）当权值低于另一阈值即时，则由p、q中检测值较大的节点将信息上传给sink节点；上传时隐含方向，即第一个节点的检测值高于第二个节点的检测值，使无线传感网络转化为有向的权值网络；（5）sink节点扫描形成的权值网络拓扑，得到初始的集合T_in和S_in，两集合的交集为空；（6）运行设计的最大流算法，把权值网络节点划分成集合T_out和S_out，并保证划分开的权值和最小，即得到事件的边界；所述步骤（6）中，最大流算法为：从集合S_in中随机选取一个节点作为源点s，从集合T_in中随机选取一个节点作为汇点t，分别以节点s、t为根建立搜索树，以节点s为根的树为S₀树，以节点t为根的树为T₀树；除节点s、t外，每个节点有3种属性，该节点所在的树、节点的类型以及节点的父节点；节点的类型也分为3种，活动节点、被动节点和自由节点；活动节点位于搜索树的外端，从与它相邻的自由节点中选取那些非饱和边所连接的节点为子节点；被动节点位于搜索树的内部，是活动节点被搜索所有邻居节点后转变的，不可再生长；自由节点不属于任何树，但可以被活动节点捕获；该算法包含三个方法：生长方法、扩增方法、收养方法：生长方法是树上的活动节点搜索与其相邻的、连接非饱和边的节点，并将满足条件的自由节点作为子节点；捕获的自由节点属于同一棵树并变为活动节点；若一个活动节点的所有邻居节点都被搜索变为该树的节点后，该活动节点变为被动节点；若活动节点的一个邻居节点属于另一棵树，且它们之间具有非饱和边时，一条增广路经P₀被发现，此方法结束；扩增方法是在增广路经P₀上增加网络流量，更新该路经上每条边的权值；首先在增广路经P₀上，寻找瓶颈边的剩余权值，即W_min＝min(W_f(p,q):(p,q)是路径P₀上的边)，网络流量增加W_min，更新路经P₀上任意两节点p、q的剩余权值为W_f(p,q)＝W_f(p,q)‑W_min；对于每条边(p,q)，初始的W_f(p,q)＝W(p,q)；然后，搜索增广路经P₀上的饱和边，要求饱和边的子节点成为孤儿节点，使孤儿节点在同一颗树上寻找新的父节点，进一步寻找新的增广路径；收养方法针对每个孤儿节点重新在同一棵树上寻找有效的父节点，且连接它们的边是非饱和的；若找到新的父节点，该孤儿节点留在该树上，否则成为自由节点；若孤儿节点成为自由节点，与它相邻的在同一棵搜索树上的具有非饱和边的邻居节点将成为活动节点；成为自由节点的孤儿节点的所有子节点将变为孤儿节点；当孤儿节点集合O中没有孤儿节点时，该方法结束；最大流算法循环依次调用这三个方法，当搜索树S₀和T₀不再生长，即寻找不到新的增广路径P₀时，网络流量最大；此时位于搜索树S₀上的所有节点属于S_out集合，网络中其余的节点属于T_out集合，两集合形成的边界即为事件边界，根据上传权值时隐含的方向，确定事件发生的区域，即检测值大的节点所在区域是事件区域；（7）根据上传权值时隐含的方向，进一步确定事件区域，即检测值大的节点所在区域是事件区域。