无线传感器网络覆盖问题

Huang和Tseng提出了一种基于传感器数目的多项式时间算法，将覆盖问题抽象表述为一个决策问题，并验证了一个传感器配置是否提供了k阶覆盖。该算法的目标就是确定无线传感器网络服务区域中的每个点是否至少被k个传感器节点监视覆盖。传感器的感应范围可以是单位圆，也可是非单位圆。这种算法可方便地用到传感器网络的分布式协议当中，每个节点只需收集本地信息做出自己的决策。另外，该算法不需确定每个位置的覆盖，而是尽量看每个传感器感应范围的周界是如何被覆盖的，这样最大的优点就是得到了多项式时间的算法，降低了算法的计算复杂度，即O(nd log d)，其中n为传感器节点数目，d为和一个传感器感应范围交叉的最大传感器数目。只要传感器的周界被充分覆盖，则整个区域就能够被充分覆盖。因此这种算法适合于下面几种无线传感器网络应用，包括定位应用、要求较强的环境监测功能的应用场合及要求严格的容错功能的传感器网络应用。文献[16]通过与节点数相关的多项式有效算法解决了二维平面的无线传感器网络的覆盖问题。文献和文献最大的不同就是将无线传感器网络的节点感应区域建模成一个球体(不一定是相同的半径)，并将覆盖问题推广到三维空间来解决，最终得到了可行的多项式求解算法。

Gupta在参考文献[18]中提出的算法是通过选择连接的传感器节点路径来得到最大化的网络覆盖效果。该算法同时属于连接性覆盖中的连接路径覆盖及确定性区域／点覆盖类型。当基站或汇聚中心向无线传感器网络发送一个感应区域查询消息时，连接传感器覆盖的目标是选择最小的连接传感器节点集合并充分覆盖无线传感器网络区域。Gupta分别给出了集中与分布式两种贪婪算法。假设已选择的传感器节点集为M，剩余与M有相交传感区域的传感器节点称为候选节点。集中式算法初始节点随机选择构成M集合之后，在所有从初始节点集合出发到候选节点的路径中选择一条可以覆盖更多未覆盖子区域的路径，并将该路径经过的节点加入M。该算法一直执行到网络查询区域可以完全被更新后的M覆盖为止。如图2-10所示为该贪婪算法执行的方式，在如图2-10(a)所示中，贪婪算法会选择路径P2，得到如图2-10(b)所示，这是由于在所有备选路径中选择B3和B4组成的路径P2可以覆盖更多未覆盖子区域。

该连接传感器网络覆盖的贪婪算法的主要思想是：首先从M中最新加入的候选节点开始执行，在一定范围内广播候选路径查找消息，收到候选路径查找消息的节点判断自身是否为候选节点，如果是，则以单播方式返回发起者一个候选路径响应消息。发起者选择可以最大化增加覆盖区域的候选路径，更新各参数，算法继续执行，直到网络查询区域可完全被更新后的M所覆盖。该算法的优点主要有以下几点。

① 节点传感区域模型可以是任意凸形区域，更加符合实际环境。

② 可以灵活地选择使用集中式或分布式方式来实现。

③在保证网络覆盖的同时，考虑了网络的连接性，算法周期执行降低了网络通信代价，并可以延长网络的寿命。

该算法主要缺点是：

① 虽然同时考虑了连通性与网络的覆盖性，但不能保证查询返回结果的精度。

② 没有考虑实际无线信道中出现的干扰和消息丢失情况。

通常，将无线传感器网络的覆盖和部署配置分为确定性覆盖和不确定性覆盖(或叫随机覆盖)两种，而每种覆盖又分为点覆盖和区域覆盖两种方式。这里仅给出确定性覆盖和部署配置的一种基于贪婪算法的点覆盖算法，其他类型的覆盖和配置算法(如Voronoi图表搜索算法)请读者参考文献[20～22]。

一种基于点覆盖的贪婪无线传感器部署和配置算法伪代码如下；

除了上面介绍的无线传感器网络配置和覆盖控制算法以外，对于覆盖问题的计算，还来自于这样一些实际的应用，如野外动植物或环境监测。假定节点感知距离半径为R′，并且各个节点工作相互独立，共同完成监控面积为A的区域，问究竟要布置多少个节点才能以要求的覆盖概率(覆盖率)实现对该区域的监控?

先不考虑节点位于边界区而造成节点覆盖面积减小，因每个节点感知和监控整个区域的概率为，令每个节点覆盖率为P(A)=p，由于各个节点独立覆盖，则M个节点的覆盖率为，如果给定了传感器感知距离半径R′，则要满足给定覆盖率P要求所需的最少节点数为。如考虑边界节点影响，存在部分区域A′落在区域A外面，则所需节点数为：

这里仅给出了无线传感器网络覆盖设计的一个参考界，而实际情况存在一定的差异，为保持相应的连接性，可取实际传感器节点数略大于理论值。

综上所述，可以得出无线传感器网络覆盖的一般准则：如已知传感器节点的通信距离，可以通过文献[24]提出的方法得知所需配置的节点数，然后选择适当的感知覆盖半径；同样如已确定传感器感知覆盖半径，可先计算出布置的节点数，然后选择合适的通信距离或调整控制传感器节点功率大小；如通信距离和感知覆盖半径都确定的情况下，只有增加或减少节点数来满足给定的最低连接可靠性和成本设计要求。

最近，国内也有学者对无线传感器网络的覆盖控制问题进行了全面的研究，详细分类总结了近年来提出的各种覆盖控制问题的思想和有代表性的研究成果，着重分析了一些典型的无线传感器网络覆盖控制算法与协议，最后进行了各种算法的比较，探讨了目前无线传感器网络覆盖控制亟待解决的问题，并给出了一些最新的仿真研究成果。如图2-11所示给出了一个无线传感器网络覆盖算法和协议分类。