0 引言

近年来，用户对移动性数据的要求进一步提高，而基于IEEE 802.16e技术的全球微波互联接入(Worldwide Interoperability for Microwave Access，WiMAX)能够为非视距范围内的移动终端提供高效无线连接，与其他接入技术相比^[1]，WiMAX具有投资少、传输速率高、不同种类数据传输、组网灵活、布置方便等一系列优点，受到了业界的积极响应和支持，但移动节点(Mobile Station, MS)主要依赖电池供电，同时也造成了巨大的能量消耗。面对巨大的能耗问题，WiMAX通信的节能技术已成为当前研究热点^[2]，能耗效率也成为评价WiMAX系统总体性能的重要指标。

据此IEEE 802.16e标准^[3]提出休眠机制用来节约MS的能量消耗。协议中定义了3种节能类型：节能类型Ⅰ、节能类型Ⅱ和节能类型Ⅲ。在节能类型Ⅰ和节能类型Ⅱ中，MS均有3种状态：睡眠状态、监听状态和清醒状态。不同之处在于节能类型Ⅱ的监听窗口能够处理一定量的数据包，而节能类型Ⅰ的监听窗口仅仅用来与基站(Base Station, BS)进行对话，它要处理数据必须切换到清醒状态。节能类型Ⅲ只有一个睡眠窗口，当它结束时，MS立即进入清醒状态。由IEEE 802.16e标准可知，节能类型Ⅰ适用于尽力而为(Best Effort, BE)和非实时可变速率(Not Real Time Variable Rate, NRT-VR)的业务，容许一定时延及其变化，实时性要求相对低。节能类型Ⅱ主要适用于非请求授予服务(Unsolicited Grant Service, UGS)和实时可变速率(Real Time Variable Rate, RT-VR)业务，对时延敏感。节能类型Ⅲ被推荐为多播连接和管理操作，如周期性寻呼等。

目前，如何调度激活实用的休眠类型，配置合理的休眠参数，建立合理的数学模型和实际模型，以及精辟的理论分析和完善的系统仿真成为研究热点。本文是基于IEEE 802.16e无线城域网中点对多点的无线信道共享模式，以下行传输为例进行研究，带宽以时隙来衡量，只讨论终端上存在BE和NRT-VR这两类非实时业务的情况。

1 相关工作

如何提高依靠电池供电的MS的能耗效率问题一直被广泛关注，其中包括对节能调度算法的研究，但这些算法集中在802.11及传感器网络中^[4-7]。

文献[8]研究在长期演进计划(Long Term Evolution, LTE)系统中通过创新非连续接收(Discontinuous Reception, DRX)机制保障终端功耗效率，通过设置不同的自适应配置准则以提高DRX能耗的效率，且不增加额外的信令开销；文献[9]针对LTE系统研究了不同频段和不同无线信道上数据传输与能耗的关系。通过基站对下行链路进行控制，进而实现终端的低功耗依然是当前研究的主要方法，文献[10]针对传统的基站调度算法只根据延迟、频谱效率等进行算法设计，提出了在多用户场景下考虑终端能耗的基站调度算法，并通过设计次优算法以配合非连续发送(Discontinuous Transmission, DTX)机制，进而实现终端与基站功耗协同降低功耗的目标。文献[11-12]则从下行的载波控制角度研究对终端能耗的影响，通过传输信道的调度与分配方面节约终端功耗，但这些节能机制与方法并不完全适用于802.16e网络，尤其是针对能耗效率要求较高的特殊应用场景，如隧道通信等。

目前，WiMAX网络中提高终端能耗效率的研究主要包括对休眠模式的分析、改进及休眠参数选择等，对休眠模式在实现过程中的参数设置提供了方法。文献[13]考虑在负载低的情况下，针对节能类型Ⅰ提出一种新颖的节能算法，此算法将二倍增长睡眠窗机制改为幂函数增长睡眠窗口机制，通过理论分析和仿真实验证明了提出的机制性能比线性增长睡眠窗口机制的性能要好。文献[14]利用SPA(Simple Packing Algorithm)模型来学习频谱感知的历史信息从而对下一时刻的信道状态进行预测，对下行链路子帧休眠模式进行了分析，但该算法窗口长度固定会导致一些空闲移动终端因得不到及时休眠而浪费能量这一不足。文献[15]提出了一种基于资源预留的WiMAX Mesh网络支持服务质量(Quality of Service, QoS)的微时隙动态分配算法，根据网络时隙状态动态调整休眠参数，但将时隙仅分为可用和不可用两种状态，使各个参数性能不能达到最佳。文献[16]率先研究了应用于802.16e网络的节能调度算法，是研究终端休眠并达到功耗效率提升的经典方法。该文提出了以虚拟突发方式为MS发送数据的调度思想，算法的基本思想如图 1所示。在每个虚拟突发开始时(一个虚拟突发为一组连续的时隙)，从处于清醒状态的MS中选择一个MS为主移动终端，其他所有处于清醒状态的MS均为次移动终端。在进行时隙分配时，主移动终端比次移动终端具有更高的优先级，即除了为保证次移动终端的服务质量而必须为其分配的时隙外，虚拟突发中的其他所有时隙均分配给主移动终端，因此，主移动终端基本上占用了一个虚拟突发的所有带宽资源，其数据得到了连续的发送。当前虚拟突发结束后，主移动终端进入休眠，选择一个新的主移动终端，开始新的虚拟突发。在不影响其他MS服务质量的前提下，为每个MS一次传输尽可能多的数据，使MS在一次传输后可以休眠较长的时间。该思想可以明显提高802.16e网络的能耗效率，但文献[16]基于该调度思想给出的最长虚拟突发优先(Longest Virtual Burst First, LVBF)算法不能有效避免MS的空闲状态，从而无法减少由于MS的空闲状态造成的能量浪费；未考虑实际环境中不同MS的信道质量差别，可能将时隙分配给信道质量差的MS，从而导致因传输错误而引起的空闲状态，增大了MS的能耗。

综合上述可看到，这些算法尚存在一些问题，影响了算法对能耗效率的实用性。主要表现在：

1) 由平均反应时延公式(1) 可知(这里F(t)为分布时间函数，P(τ)为能量消耗，MS醒来的时刻为({x_k, k≥0}，且x₀=0)^[17]，MS休眠就必然引起数据的时延；反之，如果要减少数据的时延，就必须减少休眠时间，则会增加MS能量消耗。

$ Dela{y_{{\rm{ave}}}} = \sum\limits_{K = 0}^\infty {{x_{k + 1}}\left[{F\left( {{x_{k + 1}}} \right)-F\left( {{x_k}} \right)} \right]} -P\left( \tau \right) $

(1)

LVBF算法没有权衡考虑不同网络设计对能量消耗和时延这两种性能的不同要求，LVBF只是单方面减少了MS的状态转换次数，并在一定程度上增加了MS的平均休眠时间，从而增加了数据的时延。

2) 次移动终端不能进入休眠，因此不能有效避免终端的空闲状态，从而无法减少由于空闲状态造成的能量浪费。虽然LVBF算法通过突发传输的方式在连续时隙内为主移动终端发送数据，但为保证所有MS的服务质量，LVBF算法不能像最优方法那样，在为某一MS传输数据的过程中，让其他MS处于休眠状态。而是在每个虚拟突发中，主移动终端和次移动终端均处于清醒状态。因为LVBF算法认为，次移动终端仅被保证最小的数据速率，不能进入休眠状态。然而，本文经过分析发现，在某些情况下，次移动终端是可以进入休眠的。LVBF算法未让满足休眠条件的次移动终端进入休眠，必将造成不必要的空闲时间，从而导致能量的浪费。

3) 未考虑不同MS的信道质量差别，使得传输错误增加，导致MS能耗增大。实际环境中，不同MS在相同时刻的信道质量可能不同。由于LVBF算法未考虑MS信道质量的差别，因此可能将时隙分配给信道质量较差的MS，从而引起传输错误，使发往MS的数据包丢失，增加了MS处于空闲状态的时间，浪费了MS的能量。

为解决以上问题，本文提出一种有效避免MS空闲状态的节能调度(Idle-state Avoidance and Virtual Burst, IAVB)算法。IAVB算法基于虚拟突发的思想，结合信道质量选择应获得连续传输时隙的MS，其他MS一旦符合休眠条件则进入休眠状态，在保证MS服务质量的前提下，避免了不必要的空闲时间。

2 系统模型与问题描述 2.1 系统模型

假设一个具有多时隙的WiMAX网络环境，可以用图G=(V, E)来表示，其中V代表节点集，E表示网络中有向边集合。其中，V={v₁, v₂, …, v_n, BS}表示系统中含有n个MS∈{v₁, v₂, …, v_n}节点和1个BS节点，有向链路集E={e₁, e₂, …, e_m}表示网络中有向边集合，e(v_i, v_j)∈E，当且仅当d(i, j)≤D，i为发送方，j为接收方，D为通信半径，表示节点i和j之间的欧氏距离。该系统工作于周期同步时隙模式，其中每个周期包含T个时隙。假设有K条正交的无线信道且每条信道的带宽是q_i，K(v_i)表示节点v_i的射频数量。该系统工作于周期同步时隙模式，每个时隙t=1, 2, …, T中每个(链路，信道)对是活动的，在不同时隙，将通信业务分配给活动的时序编号N={0, 1, …, T-1}中。P_w表示处于清醒状态的v_i在每个时隙上的平均能耗，P_rw表示v_i从休眠状态转换到清醒状态的平均能耗，P_wr表示v_i从清醒状态转化到休眠状态的能耗，P_r处于休眠状态时的能耗^[18-19]。

假设MS节点初始带宽请求Q={q₁, q₂, …, q_n}，可求得MS节点v_i的请求带宽为：

$ {\bar q_i} = {q_i} + \sum\limits_{j \in child\left( i \right)} {{q_i}} $

(2)

由带宽需求与正交频分复用(Orthogonal Frequency Division Multiplexing, OFDM)码元及传输速率的对应关系^[20]，各个链路在每帧中的时隙需求为：

$ {c_{e\left( {{v_i}, {v_j}} \right)}} = \left\lceil {{{\bar q}_i} \cdot {T_f}/{b_j}} \right\rceil + h $

(3)

其中：h为OFDM码元间的保护间隔，b_j表示各个OFDM码元中传输的比特数，T_f为帧持续时间。

当且仅当链路e(v_i, v_j)∈E在时隙t和信道k上是活动时^[21]，$f_{{v_i}, {v_j}}^{kt} = 1$；否则，$f_{{v_i}, {v_j}}^{kt} = 0$。

$\frac{1}{T}\sum\limits_{t = {\rm{1}}}^T {f_{{v_i}, {v_j}}^{kt}} $为链路e(v_i, v_j)在信道k上的利用率，$\frac{{{c_{e\left( {{v_i}, {v_j}} \right)}}}}{T}\sum\limits_{t = 1}^T {f_{{v_i}, {v_j}}^{kt}} $为有效时序的带宽可用率。为了实现这个链路，任何信道分配都必须符合各链路时隙数尽可能接近带宽请求值，并通过时隙复用获得最短的调度周期。

基于以上分析和假设可知，一个v_i的能耗由其处于清醒状态的时间、从休眠状态到清醒状态的转换次数、可用带宽决定，因此，v_i在一段时间T′内(T′足够长)的总能耗P_i可以表示为：

$ {P_i} = \frac{{{c_{e\left( {{v_i}, {v_j}} \right)}}}}{T}\sum\limits_{t = 1}^T {f_{{v_i}, {v_j}}^{kt}} \times \left( {{D_i}{P_w} + {L_i}{P_{rw}}} \right) $

(4)

其中：D_i是v_i在时间T内处于清醒状态的总时隙数，L_i表示v_i从休眠状态转化到清醒状态的次数。降低MS能耗的调度算法的目标是在保证每个MS服务质量的同时，最小化所有MS的平均能耗(在足够长的时间T′内)。

2.2 研究问题

本文以最小数据速率作为MS的服务质量要求，因此节能调度算法的目标可以形式化为：

$ \begin{array}{l} {\rm{min}}\frac{1}{n}\sum\limits_{i = 1}^n {{P_i}} \\ {\rm{s}}{\rm{.t}}{\rm{.}}\;\;r_i^t \ge r_i^{{\rm{min}}};i = {1, 2, \cdots, n} \\ {q_i} + \sum\limits_{j \in child\left( i \right)} {{q_i}} = {{\bar q}_i} \end{array} $

(5)

这里r_i^t为v_i在时隙t时的数据速率；为保证服务质量，v_i的最小数据速率要求为r_i^min。

很显然，为了最小化MS的平均能耗，最优的方法为：对于每个时隙，只有一个MS处于活动状态，并在连续的时隙内一次传输完该MS的所有数据，然后令该MS进入休眠。该方法可以最小化MS处于清醒状态的时间及状态转换次数，但不能满足式(5) 给出的约束条件，即不能满足所有MS的服务质量要求。因此，本文需要设计的调度算法，应在满足MS服务质量要求的同时降低能耗，而不是仅考虑如何最小化MS的能耗。

3 IAVB调度算法

针对上述讨论算法存在的问题，IAVB算法主要从以下3个方面进行解决：1) 引入空闲时间阈值的概念，根据空闲时间阈值给出终端的休眠条件，使满足休眠条件的终端及时进入休眠，避免了终端不必要的空闲状态；2) 结合信道质量状况选择主移动终端，从而减少了因传输错误导致的终端空闲状态；3) 完善虚拟突发的结束条件，避免因未正确结束虚拟突发而导致的终端空闲状态。

3.1 避免终端空闲状态

WiMAX网络中链路E与时隙N的映射关系可以使用矩阵I表示。若链路在时序中传输

$I\left[{e\left( {{v_i}, {v_j}} \right), t} \right] = \left\{ \begin{array}{l} 1, 若e\left( {{v_i}, {v_j}} \right)链路在时序t中传输\\ 0, 其他 \end{array} \right.$

(6)

由于MS处于空闲状态时是在浪费能量，因此，若MS能够在处于清醒状态时一直收发数据，一旦无数据传输则进入休眠状态，便可以避免处于空闲状态时的能耗；但由于MS在休眠状态与清醒状态之间转换也需要消耗能量，如果MS处于空闲状态的时间比较短，导致状态转换的能耗大于空闲状态的能耗，则MS不必进入休眠状态。因此，MS进入休眠状态的条件是MS预期处于空闲状态的能耗大于状态转换的能耗，即：

$ \sum\limits_{t = 0}^{T- 1} {I\left[{e\left( {{v_i}, {v_j}} \right), t} \right]} = {c_{e\left( {{v_i}, {v_j}} \right)}}, \forall e\left( {{v_i}, {v_j}} \right) \in E $

(7)

$ \sum\limits_{t = 0}^{T- 1} {I\left[{e\left( {{v_i}, {v_j}} \right), t} \right]} \ge \frac{{{P_{rw}}}}{{{P_r}}}, \forall e\left( {{v_i}, {v_j}} \right) \in E $

(8)

这里T_m=P_rw/P_r定义为空闲时间阈值。

综上，MS的休眠条件也可表达为：链路最终分配的时隙的预期时间大于T_m，同时还要使分配给MS链路的时隙数与其请求的相符。

若次移动终端处于空闲状态的预期时间大于T_m而不进入休眠，将造成不必要的能耗，因此，IAVB算法在每次为次移动终端分配时隙后均计算该终端预期处于空闲状态的时间，判断次移动终端是否需要进入休眠。以下将给出具体的判断方法。

为保证主移动终端获得当前虚拟突发中尽可能多的时隙，IAVB算法只有在次移动终端的数据速率降低到其最小数据速率要求时，才为该终端分配最小的资源单位。假设次移动终端为v_i，根据滑动窗口机制，可以计算出v_i在被分配1个时隙后获得的数据传输率r_i^t为：

$ r_i^{{\rm{min}}}\left( {{T_c}-{T_l}-1} \right)/\left( {{T_c}-{T_l}} \right) + b_i^t/\left( {{T_c} - {T_l}} \right) = r_i^t $

(9)

在操作周期为T_c时，休眠窗口长度为T_c-T_l，其中，T_l是监听窗口长度，它由RT-VR的最大速率设定, 基本要求是，在操作周期到达的所有实时业务数据包在监听窗口内都能发送给MS，b_i^t表示元中传输的比特数。设T_s代表一次时隙分配后次移动终端v_i处于空闲状态的预期时间，即v_i的数据速率降低到其最小数据速率r_i^min的时间。T_s的计算方法如下：

$ r_i^t\left( {1-{{{T_s}}\left/ {\vphantom {{{T_s}} {\left( {{T_c}-{T_l}} \right)}}} \right. {\left( {{T_c}-{T_l}} \right)}}} \right) = r_i^{{\rm{min}}} $

(10)

由式(10) 推导出：

$ {T_s} = {T_c}-{T_l}\left( {1-{{r_i^{{\rm{min}}}} \left/ {\vphantom {{r_i^{{\rm{min}}}} {r_i^t}}} \right. {r_i^t}}} \right) $

(11)

将式(9) 代入式(11)，得次移动终端v_i在一次时隙分配后处于空闲状态的预期时间为：

$ {T_s} = b_i^t\left( {{T_c}- {T_l}} \right)/\left[{r_i^{{\rm{min}}}\left( {{T_c}-{T_l}} \right) + b_i^t} \right] $

(12)

基于以上分析，次移动终端v_i进入休眠状态的条件为：

$ {T_s} > {T_m} $

(13)

若一个次移动终端v_i满足休眠条件而未进入休眠，所浪费的能量P可通过式(14) 计算：

$ \bar P = {T_s}.{P_r}-{P_{rw}} = \frac{{b_i^t\left( {{T_c}-{T_l}} \right){P_r}}}{{r_i^{{\rm{min}}}\left( {{T_c}-{T_l}} \right) + b_i^t}} - {P_{rw}} $

(14)

由于v_i满足休眠条件(13)，因此P大于0，证明MS满足休眠条件而未休眠将造成能量的浪费；而且，分析式(14) 可知，次移动终端的信道质量越好，最小数据速率要求越小，所浪费的能量就越多。

综上所述，若像LVBF算法那样，所有的次移动终端无论在什么情况下均处于清醒状态，必将造成能量的浪费。所以，IAVB算法每次为次移动终端分配完时隙后，均根据式(12) 计算其处于空闲状态的预期时间，若满足式(13) 定义的休眠条件，则使次移动终端进入休眠，因此，IAVB算法减少了终端处于空闲状态的时间，解决了LVBF算法中不必要的空闲状态造成的能量浪费问题，从而进一步降低了终端能耗。

3.2 结合信道质量选择主移动终端

在每个虚拟突发开始时，需要从处于清醒状态的MS中选择主移动终端。选择主移动终端的基本原则是该MS可以在最短的时间内达到休眠的最低速率要求r_i^max。通过3.1节的分析可知，只要MS预期处于空闲状态的时间大于T_m，便可以进入休眠，因此，可以休眠的最低速率要求r_i^max表示v_i在达到该速率后可以在T_m的时间内不必被分配时隙仍能保证服务质量，即v_i的数据速率在T_m后才降低到r_i^max，因此，r_i^max的计算方法如下：

$ \mathop r\nolimits_i^{{\rm{max}}} \left( {1-\frac{{{T_m}}}{{{T_c}-{T_l}}}} \right) = \mathop r\nolimits_i^{{\rm{min}}} \Rightarrow \mathop r\nolimits_i^{{\rm{max}}} = \frac{{{T_c}-{T_l}}}{{{T_c} - {T_l} - {T_m}}}\mathop r\nolimits_i^{{\rm{min}}} $

(15)

求在最短的时间内达到可以休眠的最低速率要求的MS，即求需要连续分配的时隙数最少便能达到该速率的MS。由式(3) 可计算出为获得r_i^max需要为v_i分配的时隙数$\mathop c\nolimits_{e\left( {{v_i}, {v_j}} \right)}^{{\rm{max}}} $：

$ \mathop c\nolimits_{e\left( {{v_i}, {v_j}} \right)}^{{\rm{max}}} = \left\lceil {\left( {\mathop r\nolimits_i^{{\rm{max}}}-\mathop r\nolimits_i^t } \right) \cdot {T_f}/b_i^t} \right\rceil + h $

(16)

由式(16) 可知，$\mathop c\nolimits_{e\left( {{v_i}, {v_j}} \right)}^{{\rm{max}}} $与$\left( {\mathop r\nolimits_i^{{\rm{max}}}-\mathop r\nolimits_i^t } \right)$、休眠窗口长度成正比，与b_i^t成反比。MS的当前速率与r_i^max的差值越小，信道质量越好，则$\mathop c\nolimits_{e\left( {{v_i}, {v_j}} \right)}^{{\rm{max}}} $就越小，它达到r_i^max的时间就越短，因此，要选择在最短的时间内达到其可以休眠的最低速率要求的MS，不仅要比较MS的当前速率与其可以休眠的最低速率要求的差值，而且要结合MS的信道质量来选择。因为在实际环境中，不同MS在相同时刻的信道质量可能不同，即使一个MS的当前速率与r_i^max的差值很小，若该MS的信道质量较差，则它达到r_i^max的时间也会较长。

基于以上分析，IAVB算法选择主移动终端v_k的策略可表示为：

$ {j^ * } = \mathop {{\rm{arg}}}\limits_{{\rm{ }}j \in E'} {\rm{min}}\left( {\left( {r_j^{{\rm{max}}}-r_j^t} \right)/b_j^t} \right) $

(17)

其中：E′代表在每个突发开始时处于清醒状态的MS的集合，j(j∈E′)为处于清醒状态的MS的索引。式(17) 描述的策略结合MS当前的信道质量状况，更准确地选择出可以在最短的时间内达到休眠最低速率要求的终端作为主移动终端，解决了上述讨论算法中未考虑终端信道质量的问题。由于选择了当前信道质量较好的MS进行数据传输，因此减少了传输错误，从而减少了因数据包丢失而导致的终端空闲时间，降低了终端能耗。

3.3 虚拟突发结束条件

IAVB算法完善了LVBF算法中结束虚拟突发的方法，避免了因未正确结束虚拟突发而导致的终端空闲状态。IAVB算法首先利用空闲率来决定虚拟突发何时结束。空闲率即一个虚拟突发中主移动终端的空闲时隙数与总时隙数的比率，用ξ表示。空闲率ξ代表主移动终端占有带宽资源的程度。ξ越小，表明主移动终端在虚拟突发中获得的资源越多，反之，表明主移动终端获得的资源越少。ξ随着次移动终端数量的增加而增大，因为每个次移动终端必须被分配时隙以保证其服务质量，因此，ξ是虚拟突发中次移动终端数量的递增函数，可等价表示为：$\xi = \sum\limits_{i \in {E_a}} {r_i^{{\rm{min}}}} /C$。其中，E_a是次移动终端的集合，C是总的信道容量(单位为b/s)。定义虚拟突发结束的标志为：

$\xi \ge \varepsilon $

(18)

其中，ε是系统参数，它决定如何在终端的业务平均时延和能耗效率之间作折中^[22]。

除式(18) 所定义的条件外，IAVB算法还针对实际系统中可能出现的两种特殊情况定义了额外的虚拟突发结束条件：1) 当ξ尚小于系统参数ε时，若主移动终端主动发起休眠请求，则当前虚拟突发结束；2) 当系统中MS数量较多，系统负载较重时，可能出现主移动终端获得的数据速率尚不满足其进入休眠状态的条件，就出现ξ≥ε的情况。此时不能立即结束该虚拟突发，而要等主移动终端达到可以休眠的数据速率后再结束当前突发；否则，主移动终端在虚拟突发结束后仍然不能进入休眠，而是处于空闲状态，造成了能量的浪费，因此，虚拟突发结束的必要条件为主移动终端的当前速率不小于其可以休眠的最低速率要求，即：

$ r_{{j^ * }}^t \ge r_{{j^ * }}^{{\rm{max}}} $

(19)

IAVB算法通过综合考虑式(18) 和式(19) 所定义的条件来决定是否结束一个虚拟突发，避免了因实际系统中的特殊情况而导致的终端空闲状态。

3.4 IAVB算法流程

在给出IAVB算法之前，最后需要说明的是：调度过程中，若同时有多个次移动终端需要被分配时隙以保证其服务质量，应将当前时隙分配给最急迫需要被分配带宽的次移动终端。本文用$\left( {r_i^t - r_i^{{\rm{min}}}} \right)/r_i^{{\rm{min}}}$代表v_i需要带宽的急迫程度。由于次移动终端在需要被分配时隙时满足$r_i^t \le r_i^{{\rm{min}}}$，因此$\left( {r_i^t - r_i^{{\rm{min}}}} \right)r_i^{{\rm{min}}}$为负。$\left( {r_i^t - r_i^{{\rm{min}}}} \right)/r_i^{{\rm{min}}}$越小，表示v_i需要带宽的急迫程度越高。IAVB算法选择急迫程度最高的次移动终端v_i^a为其分配带宽，可以表示为：

$ {i^a}{\rm{ = }}\mathop {{\rm{arg}}}\limits_{i \in E''} {\rm{min}}\left( {\left( {r_i^t{\rm{-}}\mathop r\nolimits_i^{{\rm{min}}} } \right)/\mathop r\nolimits_i^{{\rm{min}}} } \right) $

(20)

其中，E″={i:v_i是次移动终端且r_i^t≤r_i^min}。

基于以上讨论，给出IAVB调度算法的步骤如下：

1) 根据式(17) 选择主移动终端，开始一个虚拟突发。其他所有处于清醒状态的移动终端为次移动终端。

2) 若E″不为空，则根据式(20) 选择次移动终端v_i^a，将当前时隙分配给v_i^a；否则，将当前时隙分配给主移动终端。

3) 根据步骤2) 中的调度结果，更新所有终端上的数据传输速率。若次移动终端的当前速率大于它可以休眠的最低速率要求，则通知该终端进入休眠，休眠时间根据式(12) 计算；若一个处于休眠状态的终端的当前速率小于其最小数据速率要求，则唤醒该终端，将其加入集合E″。

4) 如果当前主移动终端主动发起休眠请求进入休眠状态，则转到步骤1) 开始一个新的虚拟突发，否则执行步骤5)。

5) 如果式(18) 与式(19) 中的条件同时满足，则结束当前虚拟突发，主移动终端进入休眠状态，请求的休眠时间根据式(12) 计算，并转到步骤1) 开始一个新的虚拟突发；否则执行步骤2) 开始当前虚拟突发中的下一个时隙的分配。

4 仿真实验与分析

本章将通过仿真方式验证和分析IAVB调度算法的性能及系统参数对算法性能的影响。仿真场景包括一个BS和可变数量的MS。信道衰变模型通过8状态的马尔可夫链来模拟^[23-24]。MS和BS间的每一个信道都对应一个马尔可夫过程，以控制信道的状态转移。v_i(i=1, 2, …, n)与BS之间的信道具有相同的马尔可夫链参数，即相同的传输概率矩阵。所有的信道均为独立同分布，即它们有相同的马尔可夫传输概率矩阵并彼此无关。系统总信道容量C为5 Mb/s。BS上产生满足泊松分布的数据业务，其平均速率为业务的最小数据速率加上网络层和MAC层的系统开销。数据业务的最小数据速率满足[10 kb/s，40 kb/s]的正态分布。由此可以看出，连续时间马尔可夫链能够很好地对独立同分布的WiMAX网络系统进行描述，建立系统通用性方程并给出了系统的一般性解法，通过数值仿真对系统的能耗、平均响应延迟、状态转换次数、次移动终端空闲时隙数以及空闲时间阈值对算法能耗效率影响等参数之间的关系。

4.1 IAVB算法的能耗效率

本实验IAVB、IEEE 802.16e标准和LVBF的初始睡眠窗口和最终睡眠窗口是2和32帧。本文利用平均能耗(Average Energy Consumption, AEC)来衡量能耗效率。

图 2给出IAVB算法、LVBF算法和IEEE 802.16e标准在系统中存在不同数量的MS情况下的能耗效率值(每次状态转换消耗50个时隙单位的能量，ε取0.01)。由仿真结果可以看出，IAVB算法、LVBF算法在节能方面明显优于IEEE 802.16e标准，IAVB比LVBF算法提高了15%左右。主要原因在于，IAVB算法通过使满足休眠条件的次移动终端及时进入休眠状态及结合信道质量选择主移动终端等方法，减少了终端处于空闲状态的时间，使得终端的空闲时间远小于LVBF算法中终端的空闲时间，从而减小了终端处于空闲状态时浪费的能量，提高了系统的能耗效率。

图 3显示的是3种算法对平均响应延迟的影响。IAVB的平均响应延迟均低于IEEE 802.16 e标准和LVBF算法。而且随着时间的增加IAVB响应延迟显著低于其他两种，更省电。IAVB和LVBF算法的剩余电池能量分别为8 824.4 s和9 020.5 s。在初始阶段IAVB的平均响应延迟低于IEEE 802.16e标准，而优于LVBF算法，但随着时间的增加延迟也会增加，这是因为IAVB和LVBF处理数据包要多于IEEE 802.16e标准，因此，减少睡眠时间间隔的结果以减少能源消耗。相比IEEE 802.16e和LVBF算法的6 995.8 s、7 151.5 s，IAVB的电池寿命已经扩展到7 590.3 s。

图 4给出IAVB算法与LVBF算法在完成2×10⁵个时隙的调度过程中所有终端的空闲时间之和(以时隙数衡量)。可以看出，IAVB算法中空闲时隙总数在1×10³到5×10³之间，而LVBF算法中空闲时隙总数在2×10⁴到2×10⁵之间，远远大于IAVB算法中的空闲时隙数。

IAVB算法中终端空闲时间的减少是以状态转换次数的增加为代价的。图 5给出IAVB算法与LVBF算法在完成2×10⁵个时隙的调度过程中所有终端的状态转换次数之和。由图 5可见，IAVB算法的状态转换次数平均为LVBF算法的两倍左右，但分析式(14) 可知，只要符合休眠条件，空闲时间减少所降低的能耗比状态转换次数增加而增大的能耗要多，所以总体来看，空闲时间减少还是带来了系统总能耗的降低。

图 6和图 7说明了空闲时间阈值对平均能耗和响应延迟的影响。IAVB的平均能耗优于LVBF和IEEE 802.16e标准协议是因为IAVB使用一个基于MS信道质量状况策略的自适应的空闲阈值，而LVBF只考虑剩余电池寿命来设置空闲阈值，IEEE 802.16e标准的空闲阈值固定只有10帧。与IEEE 802.16e标准协议比较IAVB和LVBF算法都具有较低的能源消耗，但随着时间增加3种算法收敛到相同的平均能耗。IAVB算法的能耗与LVBF算法的能耗之差越来越小，当T_m接近8 000时，IAVB算法的能耗降低到与LVBF算法的能耗基本相同。这是由于T_m越大，满足休眠条件的次移动终端的数量就越少；即使次移动终端满足休眠条件进入休眠，它所能节省的电量也减少(由于状态转换的耗电量增加)，因此T_m越大，IAVB算法相对LVBF算法的性能提高越小。

图 7中IAVB的平均响应延迟小于其他两种算法，这意味着IAVB调整其闲置阈值相适应信道质量可允许接收更多的数据包，从而只有很少的消息等待到下一个监听窗口，提高了信道的利用率。

4.2 IAVB算法对MS最小数据速率的保证

图 8显示了随着系统负载增加，IAVB算法对不同MS的最小数据速率要求的保证情况。仿真中选择了3个具有不同最小数据速率要求的MS为例进行实验。其中，v₁的最小数据速率要求为16 kb/s，v₂为24 kb/s，v₃为32 kb/s。从图 8可以看出，3个MS的数据速率始终大于其最小数据速率要求，并随着系统中MS总数量的增加而降低，将一直降低到接近其预定义的最小数据速率。这是由于IAVB算法会在每个时隙都检查是否有MS的服务质量要求没有满足，并尽可能快地为未满足服务质量要求的MS分配时隙，因此只要系统未超负荷，IAVB算法便可以保证MS的最小数据速率要求。

5 结语

针对IEEE 802.16e网络中移动节点因信道质量差别引起的时隙分配效率低、无法减少由于空闲状态造成的能量浪费和数据包丢失的服务质量差等问题，本文根据将空闲时间阈值和基于信道质量的状况选择主移动终端相结合的策略提出了一种基于信道质量均衡的避免终端空闲状态虚拟突发的节能调度算法。该算法有以下特点：任何信道分配都必须符合各链路时隙数尽可能接近带宽请求值，并通过时隙复用获得最短的调度周期；最小化MS的平均能耗，在它进入休眠之前连续的时隙内一次传输完该MS的所有数据；考虑了节点规模变大引起的节点间通信延迟问题，引入空闲时间阈值；完善虚拟突发的结束条件与信道质量选择主移动终端的动态负载相结合的平衡策略。实验将本文算法与IAVB和IEEE P802.16算法进行了对比分析，验证了本文算法对802.16e网络中MS的节能调度具有良好的性能，也增大了随机接入信道的用户容量，提高了WiMAX网络的资源利用率。下一步的工作将考虑终端上不同类型业务的服务质量要求来完善算法设计。