无线Mesh网中的Quorum节能机制

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

关键词：节能；Quorum机制；异步；同步；无线Mesh网

Abstract:Energy conservation is a quite important issue for wireless Mesh networks. The Quorum energy conserving mechanism, discussed in this article, is quite suitable to wireless Mesh networks because it is insensitive to network scale, node density, mobility and multi-hop. Originally designed for the Mobile Ad Hoc Network (MANET) environment, the Quorum mechanism can work in two modes: synchronous and asynchronous, subject to the difficulty of clock synchronization. Currently, the research on Quorum energy conserving systems focuses on energy efficiency optimization and adaptive system. As to other issues, such as the collaboration between synchronous and asynchronous working modes, and the cross-layer design for integrating Quorum mechanism-based energy conservation with power control and Media Access Control (MAC) routing, there is much research to do.

Key words:energy conserving; Quorum mechanism; asynchronous; synchronous; wireless Mesh network

无线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系统如图2所示，其中：

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系统帧结构示意图。

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

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

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

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

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

###NextPage### 对于第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。

3.2 自适应Quorum系统

前面的Quorum系统，每个Quorum的大小是一样的，每个Quorum的QSR也是一样的，这样的Quorum系统称为对称的Quorum系统。在WMN/MANET的应用中，节点的业务流量可能是突发的，需要系统能够根据流量进行自适应调整；不同节点的供电方式和电池剩余电量也不一样，希望采用的节能策略也可以自适应调整。这就需要设计不同大小和不同QSR的Quorum系统，即非对称Quorum系统，成为第3个目标。

不同大小的Grid Quorum自然就可以构成非对称的Quorum系统，如图5所示，大小分别为：N =32和N =42的2个Quorum，组成的Quorum系统仍满足“旋转闭合特性”。

文献[5]一开始就构造了一类自适应的Extended Torus Quorum系统。文献[6]也注意到了这个问题，但构造最佳的非对称Quorum可能是一个非决定性多项式时间-完全(NPC)问题，属最难解的一类问题。这实际上是一个误解，因为第3个目标实际上只要求提供满足异步特性的Quorum表，而不需要动态计算Quorum。而根据查表选择Quorum系统，复杂度是线性的。文献[7]就利用文献[8]的Cyclic Quorum和查表的方法，构造了最优自适应Quorum系统——AAPM，可以动态调整Quorum大小和QSR，并具有第2个目标要求的最优特性。

3.3 异步Quorum节能系统的性能

异步Quorum节能系统(AQEC)的性能比较方式分为：与原有同步系统的比较、能量最优Quorum节能系统(OAQEC)与非最优系统的比较以及各种应用环境下Quorum系统的适应能力的比较。文献[5-7]对这些进行了仿真，仿真区域分别为：1 500×300 m2和1 000×100 m2的环境，节点采用IEEE 802.11 Ad Hoc方式组网，节点的传输距离为250 m，节点数为50，都是多跳的Ad Hoc环境。

(1)不使用节能模式与PSM节能模式的比较

文献[6]仿真证实了在移动的多跳Ad Hoc环境下，PSM模式下的丢包率在50%以上，根本不能很好地工作。OAQEC比不使用任何节能机制的系统能节省80%以上的能量。如文献[5]中，在分布50个节点的移动性测试中，无节能的系统在120 s时已无存活节点，而OAQEC在360 s时仍然有80%的存活节点。

(2) OAQEC与普通AQEC系统比较

OAQEC是理论上能量最优的，文献[5，7]可以证实。

(3) 各种网络环境下的性能比较

文献[5-6]的仿真中都显示：在AQEC节能系统随着网络规模、节点密度的增长时，系统性能的下降也是线性的，当节点以10 m/s左右的速度移动时，系统性能变化不明显。这样就证实了AQEC可以应用于WMN环境中。

文献[6]还仿真了无线传感器网络下OAQEC的性能，结果表明OAQEC比经典的S-MAC[9]系统性能有很大的提高，比如在S-MAC有50%以上的丢包率时，OAQEC的丢包率仍然保持在5%以内。

对于网络业务流量的变化，自适应的AQEC(AAQEC)具有很突出的性能，文献[7]的仿真表明，AAQEC能比AQEC节省20%的能量。

4 同步模式Quorum节能机制

4.1 同步模式Quorum节能系统

由图4可以看出，AQEC在所有的BI都有活跃期，这点类似于PSM模式。当时隙同步可以实现的时候，应用同步模式可以进一步节约能量。

基于模糊控制同步Quorum节能(SQEC)系统与AQEC的最大区别体现在帧结构上。图6为同步Quorum系统的帧结构图，节点只需要在QBI中保持BW活跃，其他时间都可以维持在休眠状态。这样就能节省更多的能量。从数学上来看，同步Quorum是Quorum系统的同步应用，因此两者可以使用同样的Quorum系统。

关于SQEC的研究主要在自适应调整方面，实际上这些策略也可以用在异步模式下。

在文献[10]的自适应同步Quorum节能(ASQEC)协议中，首先根据仿真确定了不同流量下最优的Quorum大小，然后在数据传输过程中检测网络流量，相应调整Quorum的大小。

由于文献[10]中的方法中采用了固定的阈值调整Quorum的大小，在实际应用中受到限制，文献[11]提出模糊控制同步Quorum节能(FSQEC)协议，引入模糊控制的方法，将历史数据包的延迟和排队等待传输数据包长作为输入参数，根据模糊控制的理论制订出调整策略。

值得一提的是在文献[10]中为了减少时延，当节点收到数据包之后的所有的时隙都保持BW活跃，直到数据包传送完成。这从本质上也是一种动态调整，即临时增加Quorum系统的元素。

4.2 同步Quorum节能系统的性能

由于SQEC工作于同步状态，性能比较主要是针对与其他同步方式的节能系统：如PSM、DPSM[12]。文献[10]中对ASQEC与PSM、DPSM[12]，文献[11]中对FSQEC与ASQEC、DPSM、PSM的性能进行了仿真比较。两者都采用了一个200 m2的区域，节点采用IEEE 802.11 Ad Hoc方式组网，且不移动，节点通信距离为300 m，节点密度分别为50个和30个，因此是一个单跳的Ad Hoc环境。Quorum系统采用Grid Quorum。

仿真结果表明，即使在时钟良好同步的单跳Ad Hoc网络环境下，ASQEC和FSQEC比PSM、DPSM都能节省更多的能量，同时延迟与他们相当。如在恒定速率数据源，20%节点存活条件下，FSQEC的存活时间比DPSM、PSM和无节能模式分别多50%、20%和15%。而在突发数据源时，这一数据分别为：100%、40%和10%。

可以注意到在突发数据源的情形下，SQEC与DPSM的性能差异不明显，而FSQEC则有明显的性能优势。这是因为FSQEC不仅利用了历史信息，同时还利用了未来要发送的数据信息。

值得指出的是两者都没有采用最优Quorum系统，因此性能还有优化的空间。

5 结束语

文献[2,5-7,10-11]中的Quorum节能机制提供了一种新的节能策略；工作于同步模式下则可以获得优于已有方式(如PSM、DPSM)的性能；而工作于异步模式下，在多跳、移动、大规模、高密度的网络中，能节省超过80%的能量。配合自适应调整策略，则可以在各种模式的数据源下，保持良好性能。

Quorum节能机制的本质是减少了不必要的数据同步，同时在局部时间/空间区域内保证必要的同步，本质上是一种“时间域”分布式的方法。由于WMN的分布式特征，Quorum机制在WMN中也有很大的应用潜力。

目前的Quorum节能机制主要基于MANET网络环境设计，Quorum系统根据时钟同步的难易程度，可以应用于同步和异步两种工作模式。而在WMN中，存在MANET子网移入和移出Mesh路由器覆盖范围的情形，如何利用Mesh路由器不需要节能的特性，在各种环境下进行模式切换，是一个需要解决的问题。

目前对Quorum节能系统的研究主要集中在能量效率优化和自适应系统方面。而在需要服务质量保证(QoS)的条件下，基于Quorum机制的节能与功率控制、MAC路由结合的跨层设计，是一个值得尝试的课题。

6 参考文献

[1] AKYILDIZ I F, WANG Xudong, WANG Weilin. Wireless mesh networks: a survey [J]. Elsevier Computer Networks, 2005, 47(4): 445-487.

[2] TSENG Y C, HSU C S, HSIEH T Y. Power-saving protocols for IEEE 802.11—based multi-hop ad hoc networks [C]// Proceedings of Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM'02):Vol1,Jun 23-27, 2002, New York, NY, USA. Piscataway, NJ,USA:IEEE,2002:200-209.

[3] MAEKAWA M. An algorithm for mutual exclusion in decentralized systems [J]. ACM Transactions on Computer Systems,1985,3(2):145-159.

[4] HAAS Z J, LIANG B. Ad Hoc mobility management with uniform quorum systems [J]. IEEE/ACM Transactions on Networking,1999,7(2):228-240.

[5] JIANG J R, TSENG Y C, HSU C S, et al. Quorum-based asynchronous power-saving protocols for IEEE 802.11 Ad Hoc networks [J]. Mobile Networks and Applications, 2005,10(1):169-181.

[6] ZHENG R, HOU J C, SHA L. Optimal block design for asynchronous wake-Up schedules and its applications in multihop wireless networks [J]. IEEE Transactions on Mobile Computing, 2006,5(9):1228-1241.

[7] CHOU Z T. Optimal adaptive power management protocols for asynchronous wireless Ad Hoc networks [C]// Proceedings of Wireless Communications and Networking Conference(WCNC'07), Mar 11-15,2007,Kowloon,China. New York,NY,USA:IEEE, 2007:61-65.

[8] LUK W S, WONG T T. Two new quorum based algorithms for distributed mutual exclusion [C]//Proceedings of the 17th International Conference on Distributed Computing System, Mar 27-30,1997,Baltimore,MD,USA.Piscataway,NJ,USA: IEEE,1997: 100-106.

[9] YE W, HEIDEMANN J, ESTRIN D. An energy-efficient MAC protocol for wireless sensor networks [C]//Proceedings of Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM'02):Vol3,Jun 23-27, 2002, New York, NY, USA. Piscataway, NJ,USA:IEEE,2002:1567-1576.

[10] CHAO C M, SHEU J P, CHOU I C. An adaptive quorum-based energy conserving protocol for IEEE 802.11 ad hoc networks [J]. Transactions on Mobile Computing, 2006,5(5):560-570.

[11] CHAO C M, LIN X H. A Fuzzy control quorum-based energy conserving protocol for IEEE 802.11 Ad Hoc networks [C]// Proceedings of Wireless Communications and Networking Conference(WCNC'07), Mar 11-15,2007,Kowloon,China. New York,NY, USA:IEEE, 2007:2178-2183.

[12] JUNG E S, VAIDYA N H. An energy efficient MAC protocol for wireless LANs [C]// Proceedings of Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM'02):Vol 3,Jun 23-27, 2002, New York, NY, USA. Piscataway, NJ,USA:IEEE,2002: 1756-1764.

作者简介：

刘天喜，北京大学信息科学技术学院在读博士研究生，主要研究方向为近距离无线通信系统、无线医疗监护系统和新型生理信号传感器。 唐孝通，北京大学信息科学技术学院在读博士研究生，主要研究方向为无线通信、网络流量自相似特征等。 焦秉立，北京大学信息科学技术学院教授、博士生导师，目前主要研究方向为CDMA、OFDM和B3G/4G无线通信系统。已发表论文30余篇、获得专利5项。