无线传感器网络覆盖技术

1、无线传感器网络覆盖技术谭慧婷1 .覆盖技术理论基础覆盖问题是无线传感器网络配置首先要面对的基本问题，它 反映了一个无线传感器网络某区域被检测和跟踪的状况。现有的 研究结果，很多都是致力于解决传感器网络的部署和检测以及覆 盖与连接的关系等方面的问题。覆盖问题可以表述成不同的理论模型，甚至在平面几何里就 能找到相应的解决方案。即使简单地只从数学上来考虑，在部署 传感器节点的时候，我们必须知道怎样用相同的节点数覆盖尽可 能大的区域。为了对网络的覆盖问题先有一个初步的认识，这里我们提出 一个几何问题-艺术馆问题来理解。假设艺术馆的主人想在场馆内放置监视器来防止盗窃。假定 相机可以有360度的视角而且可

2、以极大速度旋转，相机可以监视 任何位置，视线不受影响。关于实现这个想法存在两个问题需要回答：首先就是到底需 要多少台相机；其次，这些相机应当放置在哪些地方才能保证馆 内每个点至少被一台相机监视到。一个简单的办法就是将多边形分成不重叠的三角形，每个 三角形里面放置一个相机。通过这个方法，我们可以得到最佳分 布应该如下图，放置两个相机相机足以覆盖整个艺术馆。我们可以知道无线传感器网络的覆盖问题在本职上和上面的 几何问题是一致的：需要知道是否某个区域被充分覆盖以及完全 处于监视之下。但我们也必须认识到，几何研究的结果为理解传感器覆盖问 题提供了一个理论背景，但这样的求解办法是无法直接应用到无 线传感

3、器网络。因为：1 .监视器可以看到无穷远的地方只要没有障碍物阻挡，但是 传感器节点存在最大感应范围；2 .无线传感器网路没有类似监视器之间固定的基础设施，其 拓扑结构可能随时变化。2 .覆盖的感知模型在讨论节点如何布置之前，需要先知道传感器节点的感知模型。目前主要是两种。a.布尔感知模型布尔感知模型是以一个节点为圆心，以感知距离为半径的圆形区 域，只有落在该圆形区域内的点才能被该节点覆盖，这种模型也被称 为0T模型。其数学表达式为_ j) W rPij - lO,d(i, j) > rb.概率感知模型概率感知模型中，目标被感知的概率不再是常数，而是由目标到 节点间距、节点物理特性等诸多因

4、素决定的变量。在节点i不存在邻居节点的前提下，节点i对检测区域内目标j 的感知概率有以下三种定义形式：Pij = e-'l,d(i J) W nPij = e- QW(i,j) -r>n < d(i,j) w r2O,d(i,j) > r21_ ；1，d(i,j) £ rPij - |1 + a d(i, O,d(i,j) > r其中d(i,j)为节点i到目标j之间的欧式距离，a和8是和 传感器物理特性有关的类型参数。%从以上的3种形式可以看出，任一点的覆盖概率是介于0和1 之间的数。如果节点i存在N个邻居节点，节点j落在和相邻节 点交登传感区域内，节

5、点j的感知概率便会受到节点i与相邻节 点共同影响。假设节点i与相邻节点感知区域的重叠区域为M,而且每个节 点对目标的感知是相互独立的，那么M中任意节点j的感知概率为NGj=i-(i-p)n(i-Pkj)k=l3 .覆盖算法分类a.节点部署方式分类按照无线传感器网络节点的不同配置方式(即节点否需要知道自 身位置信息)，可以将无线传感器网络的覆盖算法分为确定性覆盖、 随机覆盖两大类。(1)确定性覆盖这是已知节点位置的无线传感器网络要完成目标区域或目标点 的覆盖。(2)随机覆盖随机覆盖考虑在网络中传感器节点随机分布且位置未知的条件 下，完成对监测区域的覆盖任务。)b.覆盖目标分类根据无线传感器网络不

6、同的应用，覆盖需求通常不同。根据覆盖 目标不同，目前覆盖算法可以分为面覆盖、点覆盖及栅栏覆盖。(1)面覆盖目标是在大量冗余节点中寻找能覆盖同样区域大小并保证网络 连通的最小节点集合。(2)点覆盖覆盖一些离散的目标点，并使每一个目标点至少能被一个节点覆 盖。(3)栅栏覆盖目标是找出连接出发位置和离开位置的路径，使这样的路径能在 不同模型定义下提供对目标的不同传感质量。根据目标穿越网络时所用的不同模型，栅栏覆盖可以分为最坏 与最佳情况覆盖'以及'暴露覆盖最坏情况是指考察所有路径中不被传感器节点检测的概率最小 情况；最佳情况是指考察所有路径中被传感器节点检测的概率最大情 况；暴露穿越

7、同时考虑了目标暴露的时间因素和传感器节点对于目 标的感应强度的因素，反映了运动目标穿越网路区域的时间增加而感 应强度累加值增大的情况。4 .经典覆盖算法a.基于网格的覆盖定位传感器配置算法考虑传感器节点及目标点都采用网格形式配置，节点采用布尔覆 盖模型，并使用能量矢量来表示格点的覆盖。如右图，各格点都可至少被一个传感器节点覆盖，此时区域达到 了完全覆盖，例如格点位置8的能量矢量为(0,0,1,1,0,0)。当网络 资源受限无法达到格点完全覆盖时，需要根据配置代价上限进行相关 的节点布置。O传感器点 O格点基于网格的覆盖定位传感器配置算法设计了一种模拟退火算法 来最小化距离错误。首先假设每个格点

8、都配置有传感器，然后循环执行以下过程，试 图删除一个传感器节点，然后进行配置代价评价，如果评价不通过， 就将该节点移到另外一个随机选择的位置，然后再进行配置代价评 价。循环得到优化值同时保存新的配置节点情况。最后，改进算法停止执行的准则。在达到模拟退火算法的冷却温 度时，优化覆盖识别的网络配置方案也同时达到。b.分布式贪婪的连通传感器覆盖方法该算法属于连通性覆盖中的连通路径覆盖及确定性面点覆盖类 型。假设已选择的传感器节点集合为此选择与M有相交的传感区域 的节点称为候选节点。集中式算法初始节点随机选择构成M之后，在 所有从初始节点集合出发到候选节点的路径中选择一条可以覆盖更 多未覆盖子区域的路

9、径。将该路径经过的节点加入M,算法继续执行 到网络查询区域可以完全被更新后的M覆盖。如图所示为该贪婪算法执行的方式。在图A中，贪婪算法会选择 路径得到b,这是因为在所有备选路径中，C3和J组成的路经 P2可以覆盖更多子区域。C.轮换活跃/休眠节点的覆盖方法采用轮换活跃和休眠节点的覆盖协议可以有效延长网络生存时 间，该协议属于确定性和节能覆盖协议采用节点轮换工作机制，每个 周期由一个Self-Scheduling阶段和一个Working阶段组成。在第一个阶段，各节点首先向传感半径内邻居节点广播通告消 息，其中包括节点ID和位置。节点检查自身传感任务是否可以可由 邻居节点完成，可替代的节点返回一条

10、状态通告消息，之后进入休眠 状态，需要继续工作的节点执行传感任务。但是这种机制存在一个问题，如果邻居节点同时检查到自身的传 感任务可由对方完成，并同进入休眠状态，就会出现下图所示的盲点。节点。和f的整个传感区域都可以被相邻的邻居节点代替覆盖， 但如果。和f进入休眠状态，就出现了不能检测的阴影区域，即盲点。为了避免这种情况的发生，节点在第一个阶段检查之前执行一个 退避机制。每一个节点在随机产生的时间之后再检查工作。为了进一步避免盲点的出现，每个节点在进入休眠状态之前还将 等待一定的时间来监听邻居节点的状态更新。d.最坏情况覆盖方法最坏情况覆盖属于确定性网络路径/目标覆盖和栅栏覆盖类型， 算法考虑

11、如何对穿越网络的目标或其所在路径上的各店进行感应与 追踪，体现了一种网络覆盖性质。这里我们定义最大突破路径，分别使得路径上的点到周围传感器 的最小距离最大化。显然，这条路径代表了无线传感器网络最坏（不 被检测的概率最小）。文中分别采用计算几何中的Vornoi图与Delaunay三角形来完成 最大突破路径的构造和查找。其中，Vornoi图是由所有Delaunay三角形边上的垂直平分线 形成的，Delaunay三角形各顶点为网络的传感器节点，并满足子三 角形外接圆不包括其他节点，由于Vornoi图中的线段具有到最近的 传感器节点距离最大的性质，因此最大突破路径一定是由Vornoi图 中的线段组成。

12、5 .覆盖性能评价指标假设无线传感器网络布置在二维平面空间内，由移动、固定两种 无线传感器节点构成，各节点具有相同的测量范围、测量可信度和通 信半径。固定节点采用随机布置方式，通过全球定位系统获取自身位 置信息，并在网络中发布共享。a.无线传感器网络的覆盖指标由于节点布置的固有冗余性，网络覆盖评价采用了可靠度的概念，对一定区域，若在t时刻处于n个节点测量范围内，该区域综合可靠度表示为R©=i_n(iQ待测区域中所有综合可靠度大于测量可靠性要求的区域成为有 效测量区域。将有效测量区域面积占待测总面积的比例定义为覆盖指 标Cob.无线传感器网络的能耗指标无线信号在传播过程中随着传播距离增

13、加而发生衰减，采用自由 空间模型计算传播损耗如下：47ro式中，Lp为路径损耗，D为传播距离。假设无线传感器网络通信能耗模型为：运行发送器或者接收器的无线花费为E$ec=50nj/b ,发送放大 器容许放大倍率的无线花费为Eamp = 100pj/b o二维空间内，坐标分别为（Xi,yi）,（xj,yj）的无线传感器节点i,j, 通信时信号传播距离计算如下：J （修一勺）？ + （%万）若节点i向节点j发送长度为kb的数据包，则节点i能耗为:Etx(匕 d) = ETx-elec(k) + 为=_。7np(m d) =Eeleck + Eampkdj节点j接收此数据包传输所消耗的能耗是ERx (k) = ERx-eiec(k) = elec所消耗的总能量是Etj(k) = k(Eeiec + Ec1mpe1方)无线传感器网络的覆盖能效优化可以扩大无线传感器网络的有 效测量区域面积，从而提高网络整体测量性能。节点通信范围通常远 大于其感知范围，且储存能量有限，因此提高能效性成为无线传感器 网络测量的关键。无线传感器节点的通信能耗与测量和数据处理能耗 相比高许多，通信能耗的优化对提高无线传感器网络能效十分重要。6.总结覆盖问题是无线传感器网络