无线Mesh网中的Quorum节能机制相关技术

摘要：无线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。

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.