一种混合传感网中基于最少空洞数栅栏的栅栏修补方法

摘要

本发明公开了一种混合传感网中基于最少空洞数栅栏的栅栏修补方法，利用部分可移动性节点修补部分空洞，使监控区域形成一条强栅栏覆盖，实现监控区域的防卫作用。本修补方法利用图论思想，在横跨整个监控区域中寻找空洞数最少的栅栏作为空洞修补对象，从而减少移动节点数；其次，利用空洞与移动节点间的匹配，寻找使移动节点移动距离最短的空洞-移动节点匹配方案，进而降低移动节点在移动过程中消耗的能量，延长网络生存时间。

主权项

一种混合传感网中基于最少空洞数栅栏的栅栏修补方法，其特征在于，该方法包括在混合传感网中查找最少空洞数栅栏：在监测区域中引入两个代表区域边界的虚拟节点φ₀和φ₁，假设φ₀表示监测区域最左侧，即(x＝0)，φ₁表示监测区域的最右侧，即(x＝L)；构造一个有向图G(V，E)，在有向图G中，V包括了所有的传感器节点；每两个节点间连线e_ij都有一个权重ω(e_ij)，该权重值表示节点v_i和节点v_j之间空洞个数，边集E的具体构造方式如下：对于所有传感器节点，不包括表示边界的两个虚拟节点，权值ω(e_ij)可表示如下：$\omega \left(e_{\mathrm{ij}}\right)=\left\{\begin{array}{c}\left[\frac{\mathrm{dist}(v_i,v_j-2R_s)}{2R_s}\right]+1,\mathrm{dist}(v_i,v_j)>2R_s\\ 0,\mathrm{otherwise}\end{array}\right.$其中，dist(v_i,v_j)表示节点v_i与v_j的距离，有当ω(e)＝0时，即这两节点间没有覆盖空洞；将两个虚拟节点φ₀和φ₁加入到前面的二分图G(V,E)中，构造一个新的二分图，其中V'＝V∪φ₀∪φ₁；对于v_i∈V,1≤i≤N，有$\left\{\begin{array}{c}\mathrm{dist}({\phi }_0,v_i)=x_i\\ \mathrm{dist}({\phi }_1,v_i)=L-x_i\end{array}\right.$对于虚拟节点权重ω(e_ij)可表示如下：$\omega \left(e_{\mathrm{ij}}\right)=\left\{\begin{array}{c}\left[\frac{\mathrm{dist}({\phi }_j,v_i)-R_s}{2R_s}\right],\mathrm{dist}({\phi }_j,v_i)>R_s\\ 0,\mathrm{otherwise}\end{array}\right.$根据以上公式确定任意两节点间存在的空洞数，即完成了二分图G'(V',E')的初始化过程；由于任意两节点连线上的权值表示的是两节点间的空洞数，那么寻找最少空洞数栅栏转化为寻找监测区域最左侧φ₀到最右侧φ₁间的最短路径，这里说的最短即权值最小，因此我们将图论中求最短路径引入，查找最少空洞数栅栏，图论中最短路径算法得到的最短路径即所寻找的最少空洞数栅栏。