TD-HSUPA的自适应调度算法

李方伟，王可，朱江，陈善学

（重庆邮电大学 移动通信重点实验室，重庆 400065）

1 引言

随着数据业务的急剧增加，要求系统提供更高的传输速率和更小的传输时延，3GPP提出了HSUPA系统的概念[1]。对于TD-HSUPA而言，主要增加了基于Node B的快速调度和混合自动重传请求(HARQ, hybrid automatic repeat request)技术。在 TD-HSUPA系统中提供了更多的多媒体业务，如视频电话、移动电视、游戏、电子商务、VoIP和FTP等。多样化的业务使网络变得更加复杂、多变，这样对于如何在复杂、多变的网络环境下保证不同业务的服务质量(QoS, quality of service)[2～4]就有了更高的要求。

在3GPP协议中根据用户端到端的QoS要求定义了4种基本业务类型：会话类业务、流类业务、交互类业务和后台类业务。对于传统的调度算法[5]，只是注重吞吐量与公平性的调节，如最大载干比算法、轮询算法和正比公平算法，它们不能保证实时业务对时延(会话类和流类)的要求，而M_LWDF算法和 EXP算法虽然可以较好地解决实时业务 QoS的保证，但是都不能对变化的网络进行调整。本文提出了一种自适应的调度算法，根据不同的网络环境对调度的参数进行微调，以更好地保证各业务的QoS。

2 TD-HSUPA调度过程

TD-HSUPA调度过程[6,7]如图1所示。

当UE有资源要传输但又没有获得授权时，UE通过E-DCH随机接入上行控制信道(E-RUCCH，E-DCH random access uplink control channel)发送调度信息(SI,scheduling information)给Node B。SI如下。

最高优先级逻辑信道的 ID(HLID, highest priority logical channel ID)：4 bit，在HSUPA中不同的业务映射不同的优先级的逻辑信道，以提高QoS。

图1 TD-HSUPA调度过程

最高优先级逻辑信道的缓存状态(HLBS, highest priority logical channel buffer status)：4bit，最高优先级逻辑信道的缓存大小占总缓存大小的比例。

总缓存状态(TEBS, total E-DCH buffer status)：5bit。

UE 净空功率(UPH,UE power headroom)：5bit，UE发送功率与其最大发送功率之比。

服务小区与临小区的路损(SNPL, serving and neighbor cell path loss)：5 bit，服务小区与同频临小区的接收信号码功率(RSCP, received signal code power)，有2种定义方式。

式(1)、式(2)中的Lserv表示服务小区路损，Ln表示同频临小区路损。

Node B根据接收到的调度请求，综合考虑RoT[8](rise over thermal)、功率控制和SI因素，进行资源分配，Node B不能精确得到UE缓存状态与其所有业务的信息，所以 Node B不直接决定 UE传输块大小，而是通过对UE的功率、时隙和码道资源的限制进行调度。在 E-DCH绝对授权信道(E-AGCH, E-DCH absolute grant channel)上进行授权，授权信息如下。

功率资源相关信息(PRRI, power resource related information)：5 bit，E-DCH 物理上行信道(E-PUCH, E-DCH physical uplink channel)上的期望接收功率与参考值Pe-base的比值。

时隙资源相关信息(TRRI, timeslot resource related information)：5 bit，最多对应5个时隙。

码道资源相关信息(CRRI, code resource related information)：5bit，终端可使用的码字只能在给定的32种中取一种。

资源持续因子(RDI)：3bit，指示资源持续时间，为可选项。

E-HICH指示(EI)：2bit，给出在下一个调度周期时，使用哪一个E-DCH HARQ指示信道(E-HICH,E-DCH hybrid ARQ indicator channel)传输确认信息。

E-DCH 上行控制信道的个数(ENI)：3 bit，E-DCH上行控制信道(E-UCCH)的个数，系统最多有8个E-UCCH。

UE将一直保持着对E-AGCH的监控，如果没有接收到授权，UE将重新发送SI。而在接收到授权后，UE根据Node B的授权信息，进行E-TFC选择。然后根据E-TFC选择结果组装MAC-e PDU，在上行物理信道(E-PUCH, E-DCH physical uplink channel)上发送给 Node B，并且 UE周期性地向Node B上报SI。

Node B在E-HICH上向UE返回ACK/NACK信息。

3 一种自适应的调度算法

在3GPP R99中，UE传输速率的调度由RNC控制，UE可用的最高传输速率在传输信道建立时由RNC确定。但是，RNC无法根据小区负载和UE的信道状况变化灵活控制 UE的传输速率。而在HSUPA中，为了更好、更灵活地控制UE的传输速率，RNC将调度工作下放到Node B进行。

在WCDMA系统中使用的是FDD模式，由于多了E-DCH相对授权信道(E-RGCH，E-DCH relative grant channel)来辅助下传功率授权信息，Node B通过控制 E-DCH专用物理数据信道(E-DPDCH,E-DCH dedicated physical data channel)的最大功率比来控制UE的调度。

而在TD-SCDMA系统中使用的是TDD模式，Node B不能直接决定UE传输块大小，而是通过对UE的功率、时隙和码道资源的限制来控制UE的最大传输速率。Node B根据UE上报的SI、RoT等情况，通过调度算法来决定是否允许UE的调度请求。本文重点对调度算法进行研究，提出了一种新的自适应调度算法。

传统的调度算法主要有最大C/I算法、轮询算法和正比公平算法。

最大C/I算法始终选择信道条件最好的用户传输数据，这就使得系统的总体吞吐量达到最大，但是这种算法多数用户有可能得不到系统服务，公平性最差。

轮询算法不考虑信道情况，循环地调度每个用户，因此这种算法是最公平的，但是如果被调度到的用户信道条件差，就无法高速传输数据，所以这种算法的吞吐量是比较差的。

正比公平算法是目前所广泛采用的调度算法，它既考虑了用户信道条件，还考虑了公平性，达到了系统吞吐量最大化和用户公平性之间的一个折衷。其优先级计算式为

其中，(C/I)i(t)指第i个用户在t时刻的载干比；而Ri(t)指该用户的平均传输速率。可以看出当用户连续被调度时Ri(t)上升，使得优先级pi(t)下降。

但上述调度算法都无法适用于对时延要求高的业务，所以又提出了M_LWDF算法和EXP算法，这2种算法考虑了用户排队队列的时延情况，能够满足实时业务对时延的要求。

M_LWDF算法的优先级表示为

其中，αi为时延相关约束因子；wi(t)为对头时延；ri(t)表示用户传输速率；Ri(t)表示用户平均传输速率。

EXP算法的优先级表示为

上述算法虽然可以较好地满足实时业务对时延的要求，但是，对于非实时业务来说过于复杂，本文提出了一种自适应调度算法，其调度过程如图2所示。

该算法的优先级表示为

其中，αi为系数，用于调整ri(t)、Ri(t)和ch_pi(t)的大小，使得在加权时某一项因子的作用不会过于明显；λi为权值，满足λ1+λ2+λ3=1，λi越大，其对应的因子在计算pi(t)时的贡献也越大；ri(t)表示用户传输速率；Ri(t)表示用户平均传输速率；ch_pi(t)表示业务的优先级，ch_pi(t) =Rwi(t)HLBS，其中，当业务为实时业务时，R为1，否则为0，HLBS表示最高优先级逻辑信道的缓存大小占总缓存大小的比例。

图2 自适应调度过程

由于 TD-HSUPA是根据不同的业务来映射不同优先级的逻辑信道，业务分为：会话类、流类、交互类和后台类。它们对时延的要求依次降低，会话类和流类业务被定义为实时业务，交互类和后台类被定义为非实时业务。

同时，网络端也根据不同网络情况，用遗传算法[9,10]对λi进行调整。其具体步骤如图3所示。

2) 以现有和过去的权值λi作为初始种群，而不是随机生成初始种群，以提高计算的精确度和效率。

3) 进行二进制编码。

4) 计算初始种群的适应度，并找出适应度最高的染色体：

其中，βi为系数，作用同αi。

5) 进行选择运算，选出适应度高的染色体作为交叉运算的父体：

6) 进行交叉运算，交换2个父体的部分值得到新的个体，如父体s1=100101，s2=010111，则在交换后s1’=010101，s2’=100111。

7) 以0.01的变异率进行变异运算，即将0变为1，1变为0，得到新的染色体。

8) 计算所有的新染色体的适应度，找出适应度最高和最低的染色体，用原有最优染色体替换新的最差染色体，同时比较新的与原有的最优染色体，若优于原有最优染色体的适应度，则替代其值，若差于则进行计数。

9) 重复步骤 5)～8)，本文算法中最优个体参与了交换运算，如果计数值过小，就容易使其解逼近第二峰，由于该算法对计算时间要求不高，可以通过增加迭代次数来增加变异发生的概率，从而找到最优解[11]，本文在计数超过100时结束遗传算法。

10) 调整权值λi。

图3 遗传算法

4 仿真结果

本文使用Opnet对M_LWDF算法和自适应算法进行了仿真，比较了它们的吞吐量和公平性。仿真参数如表1所示。

表1 仿真参数

图4显示了2种算法的系统吞吐量随用户数量的变化情况。可以看出在用户数不多的时候，由于系统对公平性要求不高，本文算法增加了权值λ1(其值与吞吐量成正比)的值，减小了λ2(其值与公平性成正比)的值，使得吞吐量优于M-LWDF算法；而在用户很多的时候，由于系统对公平性要求加大，该算法减小了λ1的值，增加了λ2的值，虽然在吞吐量上进行了一定的牺牲，但是提高了公平性，保证各用户的QoS。

图4 吞吐量比较

公平性准则是用各用户吞吐量归一化分布函数（CDF, cumulative distribution function）曲线来表示，如果用户k的吞吐量为Tout(k)，相对于所有用户平均吞吐量的归一化吞吐量为

公平性准则由表2的3个点表示。

表2 CDF准则

该准则实质上是限制了低吞吐量用户占总用户数的比例，如低于0.1 倍吞吐量的用户数不能超过总用户数的10%。

图5显示了2种算法的系统公平性的比较。可以看出在有大量用户同时接入的时候，本文算法对吞吐量做了一定的牺牲，所以系统公平性在总体上要优于M-LWDF算法。

图5 公平性比较

图6为用户数从8个增加到12个时，权值λi的变化情况。可以看出本文算法有很好的适应性，能够根据不同的网络环境改变权值λi，以达到最优化的调度。

图6 权值λi的改变

5 结束语

调度算法对于整个 TD-HSUPA系统来说是一个很重要的环节，但是传统的调度算法不是没有考虑实时业务的QoS，就是在复杂、多变的无线网络环境不能很好地进行资源分配。

本文针对TD-HSUPA系统，提出了一种自适应调度算法，算法综合考虑了吞吐量和公平性，以及业务的优先级，并通过遗传算法在后台调整加权权值，使其可以很好地适用于复杂、多变的无线网络环境中。该算法的复杂度并不高，因为遗传算法是在后台运算，不直接参与计算，并没有增加算法的复杂度。仿真结果表明，该算法能够更灵活地运用于调度环节。

[1] 常永宇. TD-HSPA移动通信技术[M]. 北京: 人民邮电出版社,2008.CHANG Y Y. TD-HSPA Technology for Mobile Communications[M].Beijing: Posts & Telecom Press,2008.

[2] 王民. 移动网络多媒体业务 QoS保障关键技术的研究[D]. 北京:北京邮电大学, 2006.WANG M. Studies on QoS Guarantee Technologies for Multimedia Services in the Wireless Networks[D]. Beijing: Beijing University of Posts and Telecommunications, 2006.

[3] 冯光升, 王慧强, 马春光等. 面向认知网络的用户QoS动态自配置方法[J]. 通信学报, 2010, 31(3):133-140.FENG G S, WANG H Q, MA C G,et al. Dynamic self-configuration of user QoS oriented to cognitive network[J]. Journal on Communications, 2010, 31(3): 133-140.

[4] 3GPP TR 25.851 V4.0.0: RAB Quality of Service Renegotiation over Iu[S]. 2001.

[5] 宋舰, 李乐民. 无线网络中的分组调度算法[J]. 通信学报, 2003,24(3): 42-48.SONG J, LI L M. Packet scheduling algorithms in wireless networks[J]. Journal on Communications, 2003, 24(3):42-48.

[6] 李佩英, 段红光. TD-SCDMA HSUP系统中E-TFC选择的研究[J].重庆邮电大学学报(自然科学版), 2009,21(1):6-9.LI P Y, DUAN H G. Research of E-TFC selection in HSUPA TDSCDMA system[J]. Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition), 2009,21(1): 6-9

[7] 3GPP TR 25.827: 1.28 Mcps TDD Enhanced Uplink, Physical Layer Aspects[S]. 2009.

[8] 游思晴, 张京, 王亚峰等. TD-SCDMA HSUPA基于系统RoT调度的干扰控制策略[J]. 电子与信息学报, 2008, 30(11): 2561-2564.YOU S Q, ZHANG J, WANG Y F, YANG D C. A novel intercell interference control based on scheduling for TD-SCDMA HSUPA[J].Journal of Electronics & Information Technology, 2008,30(11):2561-2564.

[9] 戴晓晖, 李敏强, 寇纪淞. 遗传算法的性能分析研究[J]. 软件学报,2001, 12(5): 742-750.DAI X H, LI M Q, KOU J S. Study on the performance analysis of genetic algorithms[J]. Journal of Software, 2001, 12(5): 742-750.

[10] YU Y, HUANG H. An ensemble approach to intrusion detection based on improved multi-objective genetic algorithm[J]. Journal of Software,2007,18(6):1369-1378.

[11] 何琳, 王科俊, 李国斌等. 最有保留遗传算法及其收敛性分析[J].控制与决策, 2000, 15(1):63-66.HE L, WANG K J, LI G B,et al. Elitist preserved genetic algorithm and its convergence analysis[J]. Control and Decision, 2000,15(1):63-66.

[12] 3GPP TS 25.105: Base Station (BS) Radio Transmission and Reception (TDD)[S]. 2010.

[13] 3GPP TS 25.123: Requirements for Support of Radio Resource Management (TDD)[S]. 2010.

[14] 3GPP TS25.101: User Equipment (UE) Radio Transmission and Reception[S]. 2010.

[15] 3GPP TR 25.863: Uplink Transmit Diversity for High Speed Packet Access (HSPA) [S]. 2010.