问题、模型与假设的探讨

无线传感器网络（WSN）中的一个基本问题是传感器覆盖问题。传感器覆盖是在感兴趣区域内部署一组传感器节点用于监测和/或跟踪。通常情况下，传感器节点密集部署于WSN。为了延长网络的生命周期，传感器应当尽可能长地处于休眠状态。理想情况下，当真正需要传感器时，应当将其唤醒。但是，由于为了提供这些能力，需要增加硬件，因而这种理想状态基本上是不可能实现的。例如，参考文献（Gu and Stankovic，2004）引入了一种无线触发的硬件部件。由于兴趣事件通常包括能量，其能量可用于触发已增加的硬件部件，这反过来会引起系统由休眠模式向唤醒模式转变。但是，现有传感器没有安装这些硬件。在这些情况下，当传感器决定进入休眠模式时，它们对时钟进行设置，用于在预定时间唤醒传感器，而不管周围环境发生什么事件。无线传感器网络和无线传感器与执行器网络（WSAN）采用协同机制来调度唤醒和休眠期。

无论是感知硬件部件，还是通信硬件部件，都存在着唤醒和休眠期。通常情况下，需要部分节点处于激活状态（与特定硬件有关），以执行给定任务，而其他节点可以转入休眠状态，以节约能量。传感器网络和执行器网络都含有冗余节点，用于通信和/或感知，因为只需要一些节点执行流量转发、监测或服务功能。任务调度用于确定哪些节点应当处于激活状态，哪些节点可以转入休眠状态。周期性地对这些决策进行重估，该问题又称为占空比。可以将行为分为不同级别。传感器节点可以关闭感知和通信硬件，因而完全处于休眠模式。通常将完全覆盖给定区域的一组传感器称为网络的区域支配集，或称为网络的感知骨干网。通信骨干网一般建立在感知骨干网的基础之上。也就是说，一些传感器可能包含有源感知设备，但其发信机和收信机硬件是无源的。这些传感器的通信需求可以由其通信骨干网中的邻居（那些通信硬件处于工作状态的邻居）来满足。在前一章中，我们已经讨论了通信骨干网的构建技术。本章主要涉及传感器区域覆盖问题，类似地，针对执行器，我们可以考虑模拟执行器覆盖问题，主要研究决定需要哪些执行器来为其区域内的传感器提供服务，并支持其他执行器休眠或履行其他职责。当执行器网络是密集网络且存在冗余，或者执行器网络是否为密集网络，是否存在冗余时，就会出现此问题。

本章主要研究WSN和WSAN区域覆盖问题中唤醒或休眠方案的设计。在典型的区域覆盖问题中，通常将一组传感器撒布于给定区域内。每个传感器能够覆盖一个小区域，通常假定该区域为圆形，圆心位于传感器处。该问题用于发现连通的、仍然能够覆盖同一区域的传感器子集，使得这些传感器能够单独执行监测任务。

全覆盖、网络生命周期最大化和连通性是任何区域覆盖协议的关键要求。针对传感器区域覆盖问题，存在着许多问题陈述、假设、解决途径。本章主要研究区域覆盖问题，在该问题中，给定地理区域内的每个点至少应当被一个传感器所覆盖。区域覆盖协议的主要目标是实现传感器子集的全区域覆盖，且在子集中尽可能使用最少的传感器。

与感知半径（Sensing Radius，SR）有关的假设是变化的。在大多数论文中，对于所有传感器来说，通常假定节点的SR是固定的，且所有传感器的SR是相同的（Tian and Georganas，2002）。更为一般的情形是每个传感器的SR是固定的，但不相同。一些论文（Wu and Yang，2004）假定SR是可调的。

通过要求区域内的每个点实现多重覆盖，可以将区域覆盖问题进行推广。最为直接的推广情形是k-覆盖问题。如果区域内的每个点至少被k个不同传感器所覆盖，则称该区域是k-覆盖的。一种较为受限的推广情形是k层覆盖问题，它需要k个传感器不相交子集，使得这些k个子集中的每个子集能够提供单覆盖（完全覆盖区域）。k层覆盖也属于k-覆盖，但反过来不成立。在图3-1所示的实例中，中心在O处的阴影区域是一种2-覆盖，由于区域内的每个点至少被两个圆所覆盖。但是，我们无法找到两个不同的传感器子集，使得每个子集完全覆盖该区域。

通常情况下，可以将感知和通信建模为单位圆盘图（UDG），以及本章其余部分要用到的相应术语：感知半径（Sensing Radius，SR）和通信半径（Communica-tion Radius，CR）。在UDG模型中，传感器能够监测事件发生的位置，当且仅当该位置位于传感器的感知半径（SR）内。实际上，感知能力随着距离的增大而降低，这一点可用于物理层模型中。在该模型中，某事件的感知概率取决于传感器与事件发生位置之间的距离。如果两个节点在彼此的通信半径（CR）内，则称它们是通信邻居。感知邻居是两个对应感知区域重叠的节点。如果两个节点的感知区域是圆盘，且它们之间的距离小于其对应感知范围，则它们是感知邻居。(www.xing528.com)

图3-1 阴影区域为2-覆盖，但不是2层覆盖

传感器网络既可以在传感器节点之间采用时间同步技术进行工作，也可以不采用时间同步技术进行工作。在同步协议中，通过应用某些同步协议（Li and Rus，2004；Romer et al.，2005），所有传感器节点遵循一个公共时钟。传感器节点根据公共时钟，通过相互之间的协同完成任务调度。所有决策是通过多轮操作做出的。也就是说，可以同时唤醒所有节点，交换消息，然后确定哪些节点处于激活状态。ZigBee标准要求传感器节点是时间同步的。除了高效区域覆盖协议之外，同步特性为节能通信提供了诸多优点。

在异步协议中，传感器节点不遵循公共时钟。在某段时间内，每个节点根据自己的时钟，就节点处于激活状态还是处于休眠状态独立做出决策。可以在预定时间唤醒异步协议中的每个节点，并根据与当前处于激活状态的邻居交换消息，来决定是否需要激活它。

目前已经证实，寻找能够覆盖感兴趣区域的最少连通工作节点是NP难问题（Kumar et al.，2000；Gupta et al.，2003）。即使对于集中式算法来说，由于它是NP难问题，因而寻找局部算法来实现良好性能是一种更具挑战性的任务。