作 者:刘天喜 唐孝通 焦秉立
如Grid Quorum中Quorum的大小为2n -1,QSR为(2n -1)/n2 =(,Quorum交集大小的最小值m 则为2。
2 Quorum节能机制基本思想及应用模式
2.1Quorum节能机制的基本思想
Quorum具有分布式特征,在WMN中的应用首先是移动性管理,如位置信息管理[4]等。
节能的本质要求是:尽可能无冲突地实现数据收发后休眠,并在需要数据收发时激活。
传统的节能机制是一种全局的时间调度:所有节点同步起来,在同一时间段醒来进行数据收发。Quorum节能机制的核心思想是采用一种分布式的方法,使节点的激活时隙成一种特定分布,保证互相之间时隙有交叠,且激活时隙占总时间的比例达到最小化。
2.2Quorum节能机制的同步和异步工作模式
本文用来节能的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系统帧结构示意图。
![](http://www.cww.net.cn/upLoadFile/2008/5/23/2008523101018621.gif)
从图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收到。
![](http://www.cww.net.cn/upLoadFile/2008/5/23/2008523101018360.gif)
对于第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)。
CyclicQuorum系统的数学定义为:
D={d1,d2……dk}为Zn下的一个差分集,那么Q={Q1……Qn}是一个Cyclic Quorum系统,其中:Qi ={d 1+i,d 2+i……dk+i}(modn),i =0……n -1。
如D={1,2,4},U=Z7。
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系统仍满足“旋转闭合特性”。
![](http://www.cww.net.cn/upLoadFile/2008/5/23/2008523101018371.gif)
文献[5]一开始就构造了一类自适应的Extended Torus Quorum系统。文献[6]也注意到了这个问题,但构造最佳的非对称Quorum可能是一个非决定性多项式时间-完全(NPC)问题,属最难解的一类问题。这实际上是一个误解,因为第3个目标实际上只要求提供满足异步特性的Quorum表,而不需要动态计算Quorum。而根据查表选择Quorum系统,复杂度是线性的。文献[7]就利用文献[8]的Cyclic Quorum和查表的方法,构造了最优自适应Quorum系统——AAPM,可以动态调整Quorum大小和QSR,并具有第2个目标要求的最优特性。