CDMA2000 1x EV-DO中的分组调度算法

    为提高移动分组数据传输能力，Qualcomm公司提出了CDMA2000 1x EV-DO技术，在和话音业务不同的单独载波上提供高速分组数据业务。针对数据业务上下链路的不对称性，CDMA2000 1x EV-DO采用了高阶调制、动态速率控制、快速小区选择和时分调度等技术，使前向链路数据速率最大可达2.4 Mb/s。服务扇区的所有数据用户均以时分复用的方式共享唯一的数据业务信道。接入终端(AT)通过测量前向导频信道的质量估计当前的信道质量，决定向哪个扇区传送数据及最大支持的数据速率，并通过反向信道将数据速率控制(DRC)报给接入网(AN)，AN按照一定的调度规则将时隙分配给不同的用户。由于每个时隙只有一个用户在接受服务，AN使用其全部发射功率给用户发送信息。CDMA2000 1x EV-DO系统不再需要前向功率控制技术，取代的是采用速率控制技术。

      对于CDMA2000 1x EV-DO系统，核心任务就是解决如何更好地支持分组数据业务，满足高速分组数据业务的服务质量(QoS)要求，其中尤为关键的是通过调度算法来提高平均业务速率和系统的整体稳定性。为最大化吞吐量，调度器必须选择具有最高载干比(C/I)或最佳DRC的用户传输数据，但这可能造成距离服务AN最近的AT产生信道资源垄断。因此CDMA2000 1x EV-DO的调度算法将起到非常重要的作用。调度算法需要充分考虑各用户分组排队等候的情况、信道条件及其变化状况等[1—4]。

1 分组调度器模型
      分组调度要解决的基本问题为：当多个分组业务流等待接受服务时，必须确定合理的服务规则，安排流的服务顺序和服务时间，以满足各个业务流的QoS要求。QoS性能参数包括分组时延、延时抖动、吞吐量和分组丢失率等参数。无线分组调度器的典型结构如图1所示。

      无线分组调度算法的性能主要包含以下几个方面：

      (1)高效的链路利用率：算法必须有效利用无线信道，在业务流处于差错信道时就不为该业务流分配时隙。

      (2)时延上限：对于时延敏感性业务流，要确保时延不能超过某一阈值。

      (3)公平性：算法要能保证资源在所有业务流中公平分配。应该在无差错信道条件下的业务流间提供短期公平性，在差错信道条件下的业务流间提供长期公平性。

      (4)吞吐量：算法能够确保系统短期的吞吐量和长期的吞吐量。

      (5)实现复杂度：算法复杂度要低。这在高速通信时尤为重要。

      (6)平滑的服务质量下降：当超前业务流放弃服务时要确保服务能够平滑下降。

2 典型的分组调度算法
      在无线资源管理调度算法的研究中，需要考虑的两个重要因素是吞吐量和公平性。在满足用户QoS情况下，利用信道的时变特性，使信道条件好的用户获得更多的传输数据，来获得多用户分集，以提高系统的吞吐量。这种算法的极端代表是最大C/I算法。

      最大C/I算法就是在选择传输用户时，只选择C/I值最大的用户，即让信道条件好的用户一直在传，等其信道变差时，再让其他信道变好的用户传，这样就充分利用了多用户分集的效果。如果在时刻t 有K个用户同时请求传输数据，此刻每个用户的C/I值为Ak(t )，则最大C/I调度算法选中的用户为  j 表示第j 个用户。最大C/I 算法中的吞吐量值是吞吐量的极限值。但因为在移动通信中，每个用户所处的位置不同，其所接收的信号强度就不同。最大C/I算法更多地照顾了离基站较近的移动台，使它们得到了更多的传输机会，而使处于小区边缘的用户的C/I较低。按照这种调度算法，小区边缘的用户将得不到服务机会，甚至出现所谓“饿死现象”，从占有系统资源的角度来看，这种调度算法是最不公平的。

      公平性原则是考虑所有请求传输的用户均享有一定的服务机会。最理想的情况是所有用户享有相同的服务机会，这样的调度算法最公平，如轮循算法。这种算法循环地调用每个用户，就被调度上的概率而言，对K个用户，每个用户的概率p(k )都等于1/K，也就是说每个用户以相同的概率占有可分配的时隙和功率。因此，从占有时隙和功率资源的角度来说，这种调度算法是最公平的。每次调度时，与最大C/I算法相同，也不考虑各用户以前被调度的情况。可以说这两种调度算法都是无记忆的。这里所提到的公平性问题都是在基站以时分方式选择移动台时调度机会的公平问题。
好的调度算法，应该兼顾吞吐量和公平性，得到一个比较好的折衷方案。

3 CDMA2000 1x EV-DO分组调度算法的研究
      在无线通信系统中，由于不同用户有不同速率，一个基站内所有用户速率总和往往会超过基站拥有频带所能传输的信道容量，因此必须要有调度器在基站内根据要求判断该业务的类型，以便分配信道资源给不同的用户。

      对于CDMA2000 1x EV-DO系统，前向链路以全功率发射，其控制信道和不同用户的业务信道先进行码分复用然后再进行时分复用，因此是以时分系统模型来分析。本文主要介绍CDMA2000 1x EV-DO系统中3种代表性调度算法：正比公平算法(PFS)、速率受限的最大C/I算法和加权公平排队-正比公平(WFQ-PF)联合算法。

3.1 正比公平算法
      为了做好吞吐量和公平性的折衷，Qualcomm公司提出了一种称为正比公平的调度算法。其原理如下：
      在时刻t，移动台k的平均传输速率用Rk(t )(k =1,2......k)表示，其请求传输的速率用Dk(t )表示，则被选中的用户为：

      如某一用户此刻没有数据要传输，则Dk (t )=0。这里的平均传输速率Rk(t )按式(1)更新：
Rk(t +Δt )=(1-1/Tc )Rk(t )+1/Tc×Bk (t )     (1)

      式中的Tc 是时间常数，表示滑动时间窗口的长度，实际上反映了一个用户对接收不到数据传输的忍受能力，较长的Tc 将允许等待较长的时间直到该用户的信道质量变好，这有利于系统吞吐量的提高，但可能带来附加的延迟。式中的Bk (t )是用户k 当前传输速率。

      实际计算时，把时间都折算成时隙，平均速率的更新都是每时隙一次。如果在上一时隙用户k 没有被调度上，则：

i 表示第i 个时隙。
如果在上一时隙用户k 被调度上，则：

      可以看出，如果移动台信道条件较好，其请求传输的速率Dk(t )也较高，就会使其优先权提高。如果一个用户因为信道条件较差，特别是由于其处于小区边缘，C/I长时间较低，得不到传输机会，则其平均吞吐量就会减小。这同样会使其优先权提高，获得传输机会。

3.2 速率受限的最大C/I算法
      正比公平算法并不是一种最佳的折衷方案，就公平性本身而言，保证每个用户的吞吐量达到一个最低限制也是很有必要的。否则，尽管达到了公平性准则的要求，但仍有部分用户只能得到很少的服务，使其满足不了最低需要。另外，既然要满足公平性，那么对信道好的用户的吞吐量也不能没有任何限制。在满足最小和最大吞吐量限制的前提下，可以利用最大C/I算法来使系统吞吐量尽量最大。正是基于上面的思想，文献[5]提出了一种新的调度算法，称作速率受限调度算法。设传输速率的上限为R th_max，下限为R th_min，平均速率为Rk(t ){k =1,2......K}，优先权指标函数为pk(t )∈[0,+∞]，则该算法可表示为：

      这里的+∞实际是代表优先权最高。设每个扇区的K个数据用户组成的集合为U ={1,2,L,K }，若?坌j∈U,pk(t )<+∞，则被选中用户为：k =arg max {pj(t )}。

      若?埚j∈U，使得pk(t )=+∞，则由所有满足此条件的j 组成高优先权用户集合H ={j |pj (t )=+∞,j∈U  }，此时将从集合H 中随机选择一个用户。这里的平均速率的更新方法同正比公平算法。

3.3 WFQ-PF联合算法
      WFQ是著名的有线公平调度系统。WFQ在节点对来源于多个服务器的分组数据流提供公平服务。正比公平(PF)调度器没考虑业务的QoS。通常，调度器处于媒体访问控制(MAC)层，但信道调度器忽略在MAC层调度的分组。文献[6]针对CDMA2000 1x EV-DO的动态速率调度提出了一种新的无线公平算法WFQ-PF。WFQ算法使QoS服务成为可能，PF算法利用了信道条件。
WFQ不能直接应用到无线系统中，因为无线信道是不稳定的，所以需要可以补偿信道不稳定性的算法。

      流公平排队(FFQ)算法被称为有线系统中最公平算法。在FFQ算法中，分组被作为流来看待，这意味着大小是无限的。WFQ模仿FFQ，尽管分组不是流但具有颗粒性。WFQ的优先级被定义为F (i,k,t )，其中F (i,k,t )=max{F (i,k-1,t ),R(t)}+P (i,k,t )/ri， P (i,k,t )表示时刻t 到达，优先级加权为ri的第i个连接第K个分组的大小。函数R(t )将真实时间转换为虚拟时间。真实时间与虚拟时间的关系为：dR /dt =C / ，其中，C 是平均信道容量，B(t )表示t 时刻累积流的集合。

      当分组到达AN时，分组被放到缓冲器中，这些累积分组将在WFQ-PF调度器(WFQ-PF调度器基本框图如图2所示)进行优先级排序后发送。WFQ-PF工作机制如下：

      (1)WFQ算法作为QoS调度器，模仿累积分组排序进行公平服务。

      (2)PF算法作为信道调度器，从累积分组中选择发送候选集(TCS)分组。信道调度器检查累积分组的信道优先级是否在TCS中。定义TCS (t )={i∶n_prioi (t )≥γ}，这里n_prioi (t )是用户i 在t 时刻由max_prioi (t )归一化的优先级，而且max_prioi (t )=maxprioi (t )，门限γ与TCS中的分组数有关。

      (3)控制器参考WFQ、PF和信用量来决定被服务的分组。信用量t 指示超前或滞后的分组数量。如果分组在WFQ优先级排序，称为及时服务；依据信道条件，在WFQ排序之前被服务的分组称为超前服务；在WFQ排序之后被服务的分组称为滞后服务。

      超前服务信用量是正数，而滞后服务信用量是负数。信用量为0意味着及时服务。控制器工作方式为：(a)当时刻t，WFQ优先级为最高，信用量为0的分组在TCS中，它将被服务。如果信道数据速率条件支持分组的部分服务(这意味着当前分组不能在一个时隙内完成服务)，信用量增加剩余分组大小种类的数量。如果数据速率条件支持超过一个分组大小种类，且那个用户的缓冲中有任意多的分组，信用量减少剩余服务分组大小种类的数量。(b)最高WFQ优先级分组的信用量增加它的分组大小种类的数量，然后服务TCS中AT请求的前向速率与用户的平均前向速率的比值(DRC/R)最高的分组，考虑方式(a)中分组信道条件减少被服务分组的信用量。如果没有滞后服务，那么服务TCS用户中DRC/R最高的为超前服务分组。

4 结束语
      正比公平调度算法既考虑了用户的信道环境(由DRC反映)，又考虑了每个用户的平均传输速率R(t )，在吞吐量和公平性之间获得了很好的均衡。它能充分利用短期的信道变化来增加系统容量，并且维持较长一段时间的业务的公平等级，是一种算法简单实用的调度方案。但是该算法没有考虑分组延迟，也不是流量最优的，因此不能满足多种用户的QoS保证等。

      速率受限的最大C/I算法可以满足公平性准则，具有比正比公平算法更高的平均吞吐量。通过选取不同的门限值，可方便地在吞吐量和公平性之间获得很好的折衷。

      WFQ-PF联合算法，结合了WFQ和PF两个算法的优点。PF算法可以获得较高的吞吐量，WFQ算法可以满足QoS需求并获得好的公平性，两个算法联合具有良好的综合性能，但算法较复杂。

5 参考文献
[1] 3GPP2 CS0024-0 v4.0. CDMA2000 High Rate Packet Data Air Interface[S].2004.
[2] Jalali A, Padovani R, Pankaj R. Data Throughput of CDMA-HDR a High Efficiency—High Data Personal Communication Wireless System[A].Proceedings of IEEE Vehicular Technology Conference (VTC-Spring´ 2000),Vol 3[C]. Tokyo (Japan), 2000. Piscataway (NJ,USA): IEEE,2000.1854-1858.
[3] Lu S, Nandagopal T, Bharghavan V. A Wireless Fair Service Algorithm for Packet Cellular Networks[A]. Proceeding of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM´98)[C]. Dallas(TX,USA),1998.New York (NY,USA): ACM Press.10-20.
[4] 颜泽栋. WCDMA 系统中分组调度算法及呼叫控制信令的研究与实现[D]. 南京: 东南大学, 2005.
[5] 杨大成. CDMA2000 1x 移动通信系统[M]. 北京:机械工业出版社, 2003.
[6] Rhee J H, Kim T H, Kim D K. A Wireless Fair Scheduling Algorithm for 1x EV-DO System[A].Proceedings of the IEEE Vehicular Technology Conference (VTC-Fall´2001), Vol 2[C].Atlantic City(NJ,USA), 2001.Piscataway (NJ,USA): IEEE,2001.743-746.

收稿日期：2005-09-29

[摘要] 移动通信系统需要更好地支持分组数据业务，并满足高速分组数据业务的服务质量要求。这可以通过采用好的调度算法提高平均业务速率和系统整体稳定性实现。针对CDMA2000 1x EV-DO系统的有代表性的调度算法有3种：正比公平算法、速率受限的最大载干比算法、加权公平排队-正比公平(WFQ-PF)联合算法。正比公平调度算法是一种算法简单实用的调度方案，但不能满足用户的服务质量保证；速率受限的最大载干比算法具有比正比公平算法更高的平均吞吐量，可方便地在吞吐量和公平性之间获得很好的折衷；WFQ-PF联合算法具有良好的综合性能，但算法较复杂。

[关键词] CDMA2000 1x EV-DO系统；调度算法；无线分组

[Abstract] Mobile communications systems are required to support packet data services and guarantee the QoS of high-speed packet data services. This could be realized by adopting good scheduling algorithms to improve the average service rate and the whole stability of the system. There are three typical scheduling algorithms for CDMA2000 1x EV-DO system: the proportional fairness scheduling algorithm, rate limited max C/I algorithm and Weighted Fair Queuing-Proportional Fair (WFQ-PF) algorithm. The proportional fairness scheduling algorithm is a simple and utility algorithm, but cannot guarantee the QoS for customers. The rate limited max C/I algorithm supports a higher average throughput than the proportional fairness algorithm. Therefore, using it, the compromise between throughput and fairness can be easily obtained. The WFQ-PF algorithm has a good general performance, but is too complex.

[Keywords] CDMA2000 1x EV-DO system; scheduling algorithm; wireless packet