无线传感器网络中的骨干网：保障网络生命周期和运行效率

骨干网是节点和服务节点的一个子集，这些节点能够执行指定任务，而服务节点不在骨干网中。这样，构建骨干网取决于要执行的任务。本章主要研究用于节点间通信的骨干网。下一章将讨论用于传感器区域覆盖的骨干网。

骨干网确切的定义取决于骨干网担负的任务或特定理想特性。在无线传感器网络中，骨干网是激活传感器集合，而其他传感器处于休眠状态（决定激活哪些传感器通常称为任务调度问题）。网络的骨干网通常要求是连通的，这样骨干节点能够进行通信，以完成指定任务。例如，Ad Hoc网络中的连通骨干节点能够执行高效路由和广播。使用无线传感器网络中的骨干网不仅能够延长网络的生命周期，而且还能提高网络运行效率。例如，传感器网络中的典型广播方案通常是基于洪泛的，即每个节点重传其接收到的广播消息。只有连通骨干网节点在骨干网广播中重传消息。通过骨干网进行广播可以避免大量无用重传，尤其是对于密集网络来说。骨干网通常用于改善路由过程。源节点向骨干节点转发消息。然后路由继续在骨干节点中进行，直到消息由骨干节点转发到目标节点。

目前，构建骨干网基本上有三种知名方法：基于网格划分的骨干网（Xu et al.，2001）、基于簇的骨干网（Lin and Gerla，1997）和基于连通支配集（Connect-ed Dominating Set，CDS）的骨干网（Guha and Khuller，1998）。在基于网格划分的骨干网中，网络区域被划分为多个网格，选择每个网格中的某个节点作为骨干节点。需要合理确定网格尺寸，以保证骨干网处于连通状态。在基于簇的骨干网中，节点被分成多个簇，然后选择每个簇中的某个节点作为簇头（Cluster Head，CH）。网络中的任一节点要么是簇头，要么是簇头的某个邻居。要确保簇头处于连接状态，需要用到其他节点。第1章中引入了连通支配集（CDS）的概念，我们将在本章后面部分进行详细讨论。

在构建某些基于簇和基于连通支配集的骨干网时，需要用到一个重要概念——极大独立集（Maximal Independent Set，MIS）。一个独立集就是图中的顶点集，且图中没有两个顶点是相邻的。极大独立集是一种独立集，它不是任何其他独立集的子集。最大的MIS称为最大独立集。(www.xing528.com)

独立集问题等同于团问题，因为图G中的一个独立集是G补图的一个团。因此，寻找最大独立集等价于寻找最大团，这是一个著名的NP完全问题。但是，通过逐一增加顶点直至无顶点可增，可以在多项式时间内找到一个MIS。

骨干网构建算法通常可用于单位圆盘图（UDG），该图假定所有节点具有相同的传输范围。在本章中，我们首先分别讨论传感器网络和执行器网络。因为每种网络都可以建模为UDG。然后，在2.8节中，我们讨论传感器与执行器网络的联合骨干网。文献对节点具有可调传输范围的骨干网概念进行了研究，但由于缺乏对这些概念的有效性的认识，因而本章不再讨论。因此，本章大多数节假定节点具有固定的传输半径（2.10节和2.8节在讨论传感器和执行器的异构网络时例外）。