摘要：无线Mesh网络节能问题十分重要。文章讨论的基于Quorum的节能机制对网络规模、节点密度、移动性和多跳等因素不敏感，非常适合无线Mesh网络。Quorum节能机制主要基于MANET网络环境设计。Quorum系统根据时钟同步的难易程度，可以应用于同步和异步两种工作模式。目前对Quorum节能系统的研究主要集中在能量效率优化和自适应系统方面。对于异步和同步两种模式的协同，基于Quorum机制的节能与功率控制、MAC路由结合的跨层设计，是值得尝试的课题。

无线Mesh网(WMN)[1]作为一种新型无线网络解决方案备受关注。WMN中节点的节能，特别是Mesh客户终端的节能十分重要。由于Mesh客户终端需要支持移动Ad Hoc方式组网，所以WMN实际上是移动Ad Hoc网(MANET)的一个超集。MANET下的节能机制可直接应用在WMN中，并对设计WMN的节能算法有重要参考价值。关于WMN/MANET的节能，已经有大量相关研究，主要方法分为3类：功率控制、功率感知路由和低功耗模式管理。本文介绍的方法属于低功耗模式管理。

传统的基于同步-周期休眠/唤醒的节能机制在WMN/MANET环境下遇到了很多困难，这主要是由于同步困难引起的。在大规模、高密度、多跳、移动性网络环境下，时钟同步的开销很大。一个极端的例子是两个各自同步的子网络，如果移动到一起，这两个网络会互相异步，造成网络分化。

文献[2]的作者首次应用分布式系统中的Quorum概念，开启了异步节能的新领域，经过几年的发展，基于Quorum机制的节能算法在MANET下取得了良好的效果。

1 基本原理

1.1 IEEE 802.11的节能模式

目前关于MANET的研究基本都基于IEEE 802.11，本文介绍的Quorum机制也首先应用在IEEE 802.11上。在Ad Hoc工作方式中，IEEE 802.11支持两种模式：活跃模式和节能模式(PSM)。IEEE 802.11假设所有节点的时钟通过定时同步功能(TSF)实现了完全同步。PSM的帧结构和一个数据传输的例子如图1所示。时间轴被划分为等间隔的信标间隔(BI)，BI开始有一个广播传输指示信息(ATIM)窗，ATIM窗的开始阶段，有一个Beacon窗(BW)，ATIM窗后为数据窗(DW)。

所有节点都周期性地在ATIM窗内保持活跃状态。ATIM窗通常占BI的20%。在ATIM开始的BW内，每个节点通过竞争发送信标(Beacon)。为了减少碰撞，每个节点在尝试发送Beacon前有0～2×(CWmin-1)个时隙的随机规避时间。发送完Beacon后，如果缓冲区有数据要发送，则通过竞争发送ATIM帧，收到ATIM帧的节点必须回复ATIM应答帧完成握手，并在ATIM窗结束后仍保持活跃，进行数据帧的发送和接收。如果在ATIM窗没有完成握手，则进入休眠模式，等待下一个BI的到来。

1.2 Quorum系统定义及表征参数

Quorum系统的数学定义为：

给定一个全集U={1……N }, Q ={Q 1,Q 2 ……Q q}，?坌Qi∈Q :Qi?哿U。

满足?坌Qi  ,Qj∈Q :Qi∩Qj≠Ф被称为Quorum系统。Qi被称为一个Quorum。

在分布式应用领域，人们已经设计了大量的Quorum系统，如Grid Quorum系统、Cyclic Quorum系统、Byzantine Quorum系统、Probabilistic Quorum系统。其中以Grid Quorum[3]系统最为直观。

Grid Quorum系统的数学定义为：

将U ={1……N }，N =n 2个元素排列在一个n×n的栅格上，选取任意一行和一列元素组成一个集合Qi，所有的Qi组成的集合就是Grid Quorum系统，Qi为Quorum。

一个n =4的Grid Quorum系统，其中：

Q 1 ={1,2,3,4,5,9,13}, Q 2 ={3,7,9,10,11,12,15},Q 1∩Q 2 ={3,9}。

针对不同的应用，Quorum系统有不同的表征参数，本文主要的Quorum系统特性表征参数有：Quorum的大小、Quorum元素个数、Quorum大小与U 大小的比例Quorum权重(QSR)、任意两个Quorum交集大小的最小值m等。

如Grid Quorum中Quorum的大小为2n -1，QSR为(2n -1)/n2 =(，Quorum交集大小的最小值m 则为2。

2 Quorum节能机制基本思想及应用模式

2.1 Quorum节能机制的基本思想

Quorum具有分布式特征，在WMN中的应用首先是移动性管理，如位置信息管理[4]等。

节能的本质要求是：尽可能无冲突地实现数据收发后休眠，并在需要数据收发时激活。

传统的节能机制是一种全局的时间调度：所有节点同步起来，在同一时间段醒来进行数据收发。Quorum节能机制的核心思想是采用一种分布式的方法，使节点的激活时隙成一种特定分布，保证互相之间时隙有交叠，且激活时隙占总时间的比例达到最小化。

2.2 Quorum节能机制的同步和异步工作模式

本文用来节能的Quorum系统中，Quorum中的元素是指一个时隙(如BI)；而活跃时隙的集合为该节点对应的Quorum。

根据这些时隙的开头是否对齐(也就是是否同步)，分为同步和异步工作模式。

Quorum节能的异步工作模式最引人注目。该模式下，节点不进行时钟同步，而是保持异步工作，由Quorum机制保证批次之间时间上有交叠。在大规模、高密度、移动、多跳的网络环境下，同步比较困难，开销很大，而异步的Quorum节能机制能保持良好性能。

在时隙同步较易实现的网络环境下，同步Quorum节能机制可以进一步优化能量效率。

3 异步模式Quorum节能机制

文献[2]首先提出了异步工作模式的Quorum节能机制，文献[5-6]分别对该异步模式下的Quorum节能机制进行了理论证明和仿真分析，文献[7]则提出了最优自适应调整Quorum大小和占空比的方法。

这些方法的基本思想是保留PSM模式的ATIM窗，同时选取部分时隙进行侦听，时隙选取方法遵循Quorum的原则。

3.1 异步Quorum系统的原理和能量最优化

以BI为基本时隙单元，多个BI组成Quorum间隔(QI)。属于Quorum元素中的BI称为Quorum信标间隔(QBI)，非Quorum的BI称为非Quorum信标间隔(NQBI)。NQBI由一个觉醒窗(AW)开始，AW类似于ATIM窗，节点处于活跃状态，如果没有数据传输则进入休眠状态。QBI由一个BW(BW≤AW)开始，其余时间为DW，整个QBI期间节点都处于活跃状态。

从图3可以看出，两个Quorum重叠的时隙越多，越可能早实现握手；同时QBI时，节点总处于活跃状态，需要消耗额外的电量，所以在保证前述握手条件下，需要尽可能减少QSR。

异步Quorum系统设计的目标是：

异步的两个节点能够在一个QI内实现握手；

处于活跃时期的时间与QI的比值(即占空比)最小。

所谓异步，就是要求两个节点的时隙可以有任意的偏差。

对于第1个目标，文献[5]证明了假设不存在碰撞和传输错误，满足“旋转闭合特性”的Quorum系统都可以保证在一个QI内，任意两个Quorum的BI处于对方的活跃期内，因此可以完成握手。

旋转闭合性的数学定义为：

一个U ={1……N }下的Quorum系统的Q 满足旋转封闭性，当且仅当满足条件?坌Qi , Qj∈Q，k∈{1……n}:Qi ∩rotate(Qj,k)≠Ф，其中：rotate(Qj,k)={(j +k)modn |j∈H }。

旋转闭合性实际上就是异步条件下的Quorum交集非空特性的数学翻译，包括Grid Quorum在内的很多Quorum系统都满足这一特性。图4就是一个异步Quorum握手过程，可以通过看到主机A的第1、5时隙的Beacon可以被主机B收到，同时主机B的7、12时隙的Beacon可以被主机A收到。

对于第2个目标，文献[5-6]证明了大小为N，具有最小交集个数m的异步Quorum系统的QSR的下界为：QSR≥   m /N。当m =1时，。

有一类Cyclic Quorum[8]系统满足这样的最优条件。Cyclic Quorum用差分集构造。

差分集的数学定义为：

一个Zn的子集D ={d1,d2……dk}被称为差分集，当且仅当，?坌е≠0(modn)，存在di ,dj∈D，使得di -dj =е(modn)。

Cyclic Quorum系统的数学定义为：

D ={d1,d2……dk}为Zn下的一个差分集，那么Q ={Q 1……Qn}是一个Cyclic Quorum系统，其中：Qi ={d 1+i,d 2+i……dk+i}(modn),i =0……n -1。

如D ={1,2,4}，U =Z 7。

                                                                                   [1] [2] [3]