基于区域支配集的传感器覆盖算法优化

参考文献（Sheu et al.，2007）提出了一种局部协议，主要用于在异构传感器网络中寻找一组连通传感器节点，来覆盖所需区域。传感器节点的SR和CR可能不相同。对于某个传感器来说，如果SR＞CR，则它可能需要经过多跳才能到达其感知邻居。由于在实践中通常为CR＞SR，这种情形仅具有理论研究价值。协议包括3个阶段：邻居发现、自修剪和主动感知邻居发现。

每个传感器通过使用“问候”消息，收集与其感知邻居有关的信息（邻居发现）。节点信息包括节点ID、感知范围、位置和优先级。优先级既可能是剩余能量、感知范围，又可能是通信程度，还可能是几种指标的组合（假定节点的优先级是不同的）。需要注意的是，如果SR＞CR，则节点需要洪泛方案来学习其感知邻居。节点只有在该阶段需要进行消息交换。在其他两个阶段，每个节点在决策时，不需要与其他节点进行通信。

在自修剪阶段，每个节点决定是否处于激活状态。如果某个节点的感知区域未被其高优先级感知邻居的并集完全覆盖，则该节点决定处于激活状态。这一阶段之后，要求区域被主动感知节点完全覆盖。

在主动感知邻居发现阶段，每个感知节点A确定主动感知邻居。若干个感知邻居可能会覆盖节点A周长的同一部分。如果节点A的一部分周长被节点B所覆盖，且节点B在所有覆盖节点A周长的感知邻居中优先级最高，则节点A认为感知邻居B是激活的。

假定感知范围是优先级，且感知范围较大的节点具有较高的优先级值。在如图3-4所示的实例中，假定节点优先级次序为A＜B＜C＜D＜E＜F＜G。在自修剪阶段，由于节点A、B、D、E、F、G的感知区域未被高优先级邻居完全覆盖，因而这些节点决定处于激活状态。由于节点A的优先级比节点B低，因而节点B是主动的，而节点C是被动的，因为节点F和G的优先级都比节点C高。在主动感知邻居发现阶段，节点G的周边被其感知邻居分成若干个部分。由于S₁、S₄和S₅片段分别仅被节点A、D和F所覆盖，因而节点G将节点F视为主动感知邻居。由于S₂片段被节点A、B所覆盖，且节点B的优先级比节点A高，因而节点G将节点B视为主动感知邻居。同样，S₃片段被节点B和D所覆盖，但它也被节点E所覆盖，节点E的优先级比节点B和D都高。因此，节点G将节点E也视为主动感知邻居。(www.xing528.com)

图3-4 基于区域支配集的覆盖

需要注意的是，某个节点根据高优先级感知邻居的覆盖情况，决定处于被动状态，且一些邻居也决定处于被动状态。但是，在完成此项任务时，这些邻居也被视为高优先级覆盖邻居。对于被覆盖的每个块区域，这会形成一个高优先级感知邻居链，且优先级最高的邻居必须是主动的。因此，主动邻居集确实覆盖了原始区域。连通性是根据通往每个感知邻居（包括那些被认为是主动的邻居）初始构建的路径得出的。所提出的协议既可以应用于同步网络，又可以用于异步网络，因为只有邻居发现阶段进行了消息交换。在同步模式中，最初决策是通过采用交换“问候”消息做出的。最后，当网络动态发生变化时，可以对此进行局部和异步处理。