TD-HSUPA系统中一种多目标分组调度方法

摘要

本发明公开一种TD-HSUPA的调度方法，涉及无线通信领域。网络端在收到调度信息(SI)之后，在绝对许可信道(E-AGCH)上使用多目标的方法进行资源指派的过程中，根据多个目标(载干比，公平性和信道优先级因子)计算出总的优先级，再按照总优先级的大小进行资源分配。同时本发明TD-HSUPA的调度方法在网络端运用遗传算法，不断的对总优先级的权值进行调整和优化，这样既同时考虑了系统的吞吐量和公平性，又可以根据不同的信道条件，对优先级算法的权值进行调整，使系统达到更加优化的运营。

说明书

技术领域

本发明涉及第三代移动通信技术，特别涉及时分同步码分多址系统(TD-SCDMA)的高速上行分组接入(TD-HSUPA)中的资源调度的实现方法。

背景技术

调度问题实际上是最优化问题，即在给定设计指标和参数的允许取值范围内，确定一组独立的设计参数，使系统达到最大技术性能。系统性能的优劣通常用一个关于设计参数的函数来描述，该函数称为“目标函数”，待定的参数称为“优化变量”，而参数范围和未包含在目标函数中的一些设计指标即构成优化变量的“约束条件”。寻求系统的最佳性能，通常就是最小化或最大化目标函数。对于通信工程中的调度问题，一种比较普遍的最优化的方法是基于效用函数(Utility Function)的规划方法。每一个用户都用一条效用曲线(即效用函数)来描述系统资源分配的效用值。典型的调度方法有三个。

1.Max C/I调度方法

Max C/I调度方法首先对所有待服务移动台依据其接收信号C/I预测值进行排序，然后按照从大到小的顺序进行资源分配。该算法中，具有较低C/I值的流只有等待所有C/I值大于它的流的数据都发送完毕，才能获得发送机会。而C/I最大的流将一直占用信道，直到其队列的数据发送完毕，或出现C/I值更大的流。这样小区边缘的用户就有可能出现“饿死现象”，因此该算法的公平性很差。

2.轮询调度算法

公平地为所有UE分配资源，循环调用每个用户，给予不同用户相同的优先级，实现了用户之间的最佳公平性。但是，这样使得整个系统的吞吐量非常低，不能有效的对系统资源进行利用。

3.正比公平算法

正比公平算法是在吞吐量和公平性二者之间取得权衡折中。在正比公平分组调度算法中，每个用户被分配一个相应的优先级。在任意时刻，小区中优先级最大的用户接受服务。其优先级计算公式为：这里，(C/I)_i(t)指第i个用户在t时刻的载干比，而R_i(t)指该用户的平均传输速率。显然，当一个用户连续通信的时候，其平均速率变大，而使得该用户的优先级变小，无法再获得服务。如果用户的信道条件较好，则该用户的优先级提高；如果用户因为信道条件较差，特别是由于它处于小区边缘，C/I长时间较低，得不到传输机会，则其平均传输速率就会减小，这同样会使其优先级提高并获得传输机会。因而，此种方法实现了使系统吞吐量最大化与尽可能保持各用户之间公平性的折中。我们可以看到无线领域内的调度算法不可能只是单纯的使一项参数达到最好，它总是要以牺牲公平性或者吞吐量为代价。而传统的单一目标的优化，是无法使系统达到最佳运营。因此，就有了引入多目标决策的必要性。

在考虑单目标最优化问题时，只要比较任意两个解对应的目标函数值后，就能确定目标的优劣(目标值相等除外)。而在多目标最优化的情况下，需要对多个目标进行好坏的判断，例如既要考虑整个系统的吞吐量，让载干比高的信号多传数据，又要考虑整个系统的公平性，不能使小区边缘的用户因长时间等待而出现“饿死”的情况，还要尽可能的提高每一个用户的满意度，以提高整个系统的QoS。

发明内容

本发明针对现有技术使用传统的单一目标优化，无法使系统达到最佳状态的问题，提出一种TD-HSUPA资源调度方法，即一种基于遗传算法的多目标调度方法。

终端发起增强随机上行(E-RUCCH)过程，在此过程中向Node B上报调度信息SI；Node B收到SI后，周期性向无线网络控制器RNC上报调度算法的优先级权值以及调度信息、系统吞吐量和系统公平因子，网络端根据SI中载干比f₁(x)、公平性因子f₂(x)、信道的优先级因子f₃(x)通过加权的多目标算法在增强型专用信道调度的绝对许可信道上根据系统总优先级F(x)进行资源指派，实现多目标分组调度。RNC根据调度信息利用遗传算法调整权值，并下发给node B，node B根据终端的等级、业务的优先级以及终端缓存状况通过加权的多目标算法在增强型专用信道(E-DCH)调度的绝对许可信道(E-AGCH)上根据优先级进行资源指派。

根据干扰程度确定载干比f₁(x)，采用轮询算法调用公式计算系统公平性因子，将SI中上传的最高优先级的逻辑信道ID标识(HLID)和最高逻辑优先级信道的缓存状态(HLBS)相乘得到信道的优先级因子f₃(x)，调用公式：F(x)＝λ₁α₁f₁(x)+λ₂α₂f₂(x)+λ₃α₃f₃(x)确定系统总优先级，其中，λ_i为权值，λ_i满足∑λ_i＝1，a_i为单位调节系数。

RNC将Node B上传的权值作为初始向量集合，计算其适应度，根据适应度对诸向量进行选择，交换，变异等遗传操作，剔除适应度低的向量，留下适应度高的向量，作为新的权值。在上述适应度计算时，根据系统吞吐量f′₁(x)、系统公平因子f₂(x)、所有用户最高逻辑优先级信道的缓存状态的平均值f₃′(x)，调用公式：计算向量的适应度。

本发明提出的TD-HSUPA资源调度方法，网络端在进行资源分配的时候，对多个目标进行了综合考虑，既考虑了系统的整体吞吐量，又考虑了系统的公平性。网络端在进行资源分配的时候，还考虑了各逻辑信道的优先级和数据量的大小，在无线资源紧张，网络不能完全满足终端所有逻辑信道上传数据的需要时，在按照优先级高的逻辑信道优先发送的原则的同时也兼顾了优先级低的逻辑信道数据被调用的机会。这样，本发明最大限度地避免了多种业务并发场景中由于某些业务逻辑信道优先级比较低而长时间得不到调度，最后导致了业务失败的情形。从而改善了TD-HSUPA的服务质量。同时，本发明提出的TD-HSUPA资源调度方法加入了RNC的后台控制，使得整个调度方法非常的灵活，它可以根据不同的信道情况，不断的调整调度算法的权值，以满足当前的网络环境，使系统达到更加优化的运营。此外，本发明的技术方案的实现非常简单。

附图说明

图1是TD-HSUPA资源调度过程示意图

图2是本发明TD-HSUPA资源调度过程示意图

图3是本发明RNC控制权值的示意图

图4是本发明遗传算法的示意图

具体实施方式

对于TD-SCDMA系统而言，基站(Node B)的每一次调度的运算时间都很短，而多目标算法往往过于复杂。本发明针对现有技术使用传统的单一目标优化，无法使系统达到最佳状态的问题，可采用较简单的加权法计算出调度的优先级，根据优先级进行调度，基于遗传算法实施多目标调度方法。具体为：

终端发起增强随机上行(E-RUCCH)过程，在此过程中向Node B上报调度信息SI；Node B周期性的向RNC上报调度算法的优先级权值以及调度信息、系统吞吐量和系统公平因子，RNC根据调度信息利用遗传算法调整权值，并下发给node B，node B根据信道的载干比f₁(x)、系统公平性因子f₂(x)、信道的优先级因子f₃(x)通过加权的多目标算法在增强型专用信道(E-DCH)调度的绝对许可信道(E-AGCH)上根据优先级公式F(x)＝λ₁α₁f₁(x)+λ₂α₂f₂(x)+λ₃α₃f₃(x)确定系统信道传输优先级，由此进行资源指派。

终端收到E-AGCH上指派的资源信息后，根据网络通过E-AGCH所授权的无线资源，进行增强传输信道格式组合(E-TFC)的选择，在增强型物理上行信道(E-PUCH)上发送E-PUCH信息；网络端在E-AGCH指定的资源上接收E-PUCH信息，如果解读正确，则在E-DCH传输信道的混合自动重传请求(HARQ)确认指示信道(E-HICH)上反馈确认信息(ACK)给终端，否则反馈非确认信息(NACK)给终端；重复上述过程，在E-PUCH物理信道上发送多个MAC-a PDU直到使用完网络所指派的无限资源或发送完所有数据。

如图1所示是TD-HSUPA资源调度过程示意图。以简单的加权法进行举例说明，加权法是通过目标函数的线性聚合将多目标转换成单目标。由无线网络控制器(RNC)根据当前的系统吞吐量、系统公平性和调度信息SI，用遗传算法调整加权法的权值。具体步骤为：

1.终端在需要发起上行数据传输的时候，没有获得网络资源传输许可，终端首先发起增强随机上行(E-RUCCH)过程，在此过程中上报调度信息SI，SI可以承载的信息如表1，包括：服务小区和(同频)邻小区路损信息，终端净空功率，全部调度E-DCH缓存状态，最高逻辑优先级信道的缓存状态，最高优先级的逻辑信道ID标识，E-DCH无线网络临时标识。

表1：

  成员  内容  SNPL(5bit)  服务小区和(同频)邻小区路损信息  UPH(5bit)  终端净空功率  TEBS(5bit)  全部调度E-DCH缓存状态

  HLBS(4bit)  最高逻辑优先级信道的缓存状态  HLID(4bit)  最高优先级的逻辑信道ID标识  E-RNTI(16bit)  E-DCH无线网络临时标识

2.网络端收到来自终端的SI信息之后，根据信道的载干比f₁(x)、系统公平性因子f₂(x)、信道的优先级因子f₃(x)，通过加权的多目标算法在增强型专用信道(E-DCH)调度的绝对许可信道(E-AGCH)上进行资源指派，并每隔一段时间向RNC上报调度信息、总的吞吐量和公平性因子，RNC通过上报的信息用遗传算法调整加权的权值。可采用如下方法实现资源指派：

Node B根据干扰程度确定信道的载干比f₁(x)、系统公平性因子f₂(x)、信道的优先级因子f₃(x)计算系统调度系统总的优先级，并在E-AGCH上进行资源指派。

确定载干比f₁(x)。网络端在收到终端发来的SI之后，提取SI上传的服务小区和同频邻小区路损信息(SNPL)，根据SNPL计算载干比，SNPL表示同频的邻小区的信号对服务小区的干扰程度(即路损关系表示)。终端上报的SNPL有两种类型：

类型1：上报服务小区路损和所有同频邻小区路损的关系。关系式如下：

$\phi =\frac{1}{\underset{n=1}{\overset{N}{\Sigma }}\frac{L_{\mathrm{serv}}}{L_n}}$

类型2：上报最小的同频邻小区路损和服务小区路损关系。其关系式如下：

$\phi =\frac{\underset{n=1···N}{\min }\left(L_n\right)}{L_{\mathrm{serv}}}$

其中，L_serv为服务小区的路损，L_n为同频临小区的路损。

载干比与SNPL的倒数成比例，根据公式：计算Node B的载干比。如采用方式2确定载干比$f_1\left(x\right)=\frac{1}{\mathrm{SNPL}}=\frac{L_{\mathrm{serv}}}{\underset{n=1···N}{\min }\left(L_n\right)}.$

确定公平性因子f₂(x)，可采用轮询算法确定公平性因子。轮询算法保证以均等的机会为系统中的所有用户分配相同数量的资源，即以一定的时间间隔循环调度每个用户，公平性因子f₂(x)为等待时间T的函数，调用公式计算公平性因子，其中，T为等待时间。j＝1...K为系统中的用户数，T_j(t)表示第j个用户的等待时间。

确定优先级因子f₃(x)。将SI中上传的最高优先级的逻辑信道ID标识(HLID)和最高逻辑优先级信道的缓存状态(HLBS)相乘得到信道的优先级因子f₃(x)，优先传输优先级因子高的逻辑信道中的数据。

为了各个信道的缓存不堆积数据，也为了使低优先级的数据得到一定的传输，而不至于“饿死”，该因子的添加是有必要的。SI中上传的最高优先级的逻辑信道ID标识(HLID)和最高逻辑优先级信道的缓存状态(HLBS)表明了终端的缓存(buffer)中现有的最高逻辑优先级和该优先级信道中的数据待传量，根据公式计算

f₃(x)：f₃(x)＝HLID*HLBS

其中，信道优先级越高，其HLID值越大。优先级高的逻辑信道里的数据就会先传，而优先级低的逻辑信道里的数据就会堆积起来，这样其HLBS就会增大，同样也会使f₃(x)的值增大，实现传输。

系统根据载干比f₁(x)、公平性因子f₂(x)、信道的优先级因子f₃(x)确定系统信道传输优先级：F(x)＝λ₁α₁f₁(x)+λ₂α₂f₂(x)+λ₃α₃f₃(x)，实现对资源的调配。

其中，λ_i为权值，通常可正交化使λ_i满足∑λ_i＝1，a_i为单位调节系数，由于每个f_i(x)的单位都不一样，用a_i调整各个f_i(x)，使其单位统一，这样在相加时某一项因子的作用不会过于明显。λ_i为权值，满足λ₁+λ₂+λ₃＝1，网络端按照F(x)的大小分配资源，F(x)越大，优先级越高。可采用遗传算法计算新权值λ₁、λ₂、λ₃，并下发给Node B。具体步骤如下：Node B每隔一段时间向RNC上报信息(包括SI，系统的吞吐量，系统的公平因子)，RNC使用遗传算法计算新权值λ₁、λ₂、λ₃，并下发给Node B(可以在多个调度周期完成)。

求解上述不同权值的优化问题后输出一组最优解(多目标的求解方法有线性加权法、分层序列法、目标规划法等，本方案采用线性加权法结合遗传算法进行求解)，所有的权值都取正值，而每隔100个调度周期(或者更多)。

本发明利用遗传算法(GA)，使用当前适应度最高的假设的后代替代群体的某个部分。把信道中每一个可能的编解码作为一个向量，称为一个染色体，向量的每一个元素为基因。所有染色体(向量)组成群体。并按预定的目标函数对每个向量进行评价，根据遗传算法采用选择、交换、变异步骤，给出一个适应度的值。

RNC将Node B上传的权值作为初始向量(染色体)集合，计算其适应度，根据适应度对诸向量(染色体)进行选择，交换，变异等遗传操作，剔除适应度低的向量(染色体)，留下适应度高的向量(染色体)。

选择：从所有向量中根据适应度值遵循概率选择，剔除适应度低的向量。由于新群体的成员是上一代群体的优秀者，因而在总体上优于上一代。RNC通过GA这样反复迭代，直到满足预定的优化标准；将适应度作为其权值，权值大的被选中的概率也大。它与各染色体适应度成比例，某一向量被选中的概率为：

$P_c=\frac{f\left(x_c\right)}{\mathrm{\Sigma f}\left(x_i\right)}$

式中x_i为种群中第i个向量对应的数字串，f(x_i)是第i个向量的适应度值，∑f(x_i)是种群中所有向量的适应度值之和。这样，适应度高的个体被选中的概率较大；而适应度低的个体在多次选择后被淘汰。

交换：将匹配集中的相关向量中右半部分(或左半部分)元素进行交换。在自定义群体中任选两个相关向量，将两个相关向量的交换点右边部分(或左边部分)相互交换，可得到两个新的向量。

例如：

S1＝100101

S2＝010111

选择S1与S2的左边3位进行交叉，则有

S1＝010101

S2＝100111

变异：根据变异概率对向量中的元素进行转换，获得新的向量。由于各种偶然因素引起的基因突变，以很小的概率随机的改变遗传基因的值(将0变成1，或将1变成0)。通过变异操作可以使搜索能在尽可能大的空间中进行，获得质量较高的优化解答。一般采用0.05～0.2之间的值作为变异的概率。

通过交换和变异方法可以获得的新向量。

本发明的遗传算法采取最优保存策略，即向量集合中只保留最高适应度的向量，以下举例进行说明。

首先，RNC将node B上报的权值λ₁，λ₂，λ₃作为初始向量集合；根据系统初始吞吐量f′₁(x)、系统公平因子f₂(x)、所有用户的最高逻辑优先级信道的缓存状态(HLBS)的平均值f₃′(x)，调用公式：计算初始向量的适应度，其中，满足λ₁+λ₂+λ₃＝1。

对向量进行选择，交叉，变异(变异率为0.1)等遗传操作，得到新一代的向量，根据上面公式计算新的向量的适应度；

比较新旧向量的适应度，并留下适应度最高的向量作为最优的向量λ′₁，λ′₂，λ₃′。

重复上述步骤，当F(x)的值达到一个稳定值后，则将保留下来的向量作为最优向量下发给Node B。

由上式可知当f_i(x)的值减小的时候，其对应的λ_i值越大，F(x)的值越容易增大。这样增加了调度时该种目标的重要性，例如，当系统的公平性变好的时候，则f₂(x)变大，经过调整，λ₂的值就会减小，而λ₁，λ₃的值就会变大，在调度计算优先级的时候，公平性的影响力就会下降，而其它三种因素的影响力就会上升。

Node B在得到RNC下发的新的权值信息后，改变原有的权值，并且在绝对授权信道(E-AGCH)物理信道主要用于承载网络指派终端的物理资源信息，E-AGCH物理信道可以携带的信息如表2。

表2

  成员  内容  PRRI(5bit)  功率资源相关信息  CRRI(5bit)  码道资源相关信息  TRRI(5bit)  时隙资源相关信息  RDI(3bit)  资源持续因子

  ECSN(3bit)  E-AGCH的传输序号  EI(2bit)  E-HICH指示  ENI(3bit)  E-UCCH的个数

3.终端收到E-AGCH上的信息之后，根据网络通过E-AGCH所授权的无线资源，进行增强传输信道格式组合(E-TFC)的选择过程，确定发送数据的逻辑信道集合，确定物理资源可以支持的传输块大小，从已经确定的逻辑信道集合中生成满足传输块大小的最大的逻辑信道MAC-a PDU。根据E-TFC选择的结果，将选取的逻辑信道的数据组装成媒体接入控制层的上行增强协议数据单元(简称MAC-a PDU)格式，在增强型物理上行信道(E-PUCH)上发送。并且在MAC-a PDU中不定期地上报SI信息。该SI信息主要用于网络进行下一次E-AGCH调度时参考。网络在E-AGCH指定的资源上接收E-PUCH信息，如果解读正确，则在E-DCH传输信道的混合自动重传请求(HARQ)确认指示信道(E-HICH)上反馈确认信息(ACK)给终端，否则反馈非确认信息(NACK)给终端。在E-PUCH物理信道上反复发送多个MAC-a PDU直到使用完网络所指派的无限资源或发送完所有数据。

为使本发明的目的，技术方案和优点更加清楚，下面结合附图对本发明作进一步详细的描述。

图2是本发明TD-HSUPA资源调度过程示意图，包括如下步骤：

(1)终端发起E-RUCCH过程，上报SI信息给网络；

(2)Node B按照上报的SI信息，分别计算多个目标：

(201)计算信道的载干比；

(202)计算系统的公平因子；

(203)调用公式：f₃(x)＝HLID*HLBS计算信道的优先级因子；

(3)由载干比，公平因子和信道的优先级因子，调用公式：

F(x)＝λ₁α₁f₁(x)+λ₂α₂f₂(x)+λ₃α₃f₃(x)计算总的优先级因子，作为资源分配的优先级；

(4)Node B根据优先级F(x)在E-AGCH上进行资源分配，优先级大的信道先分配；

(5)终端根据E-AGCH的指示，进行数据的上传。

图3是确定RNC权值的示意图。

(1)在TD-HSUPA资源调度的同时，Node B上传多目标算法的权值和网络信息给RNC；

(2)RNC根据上传的数据，采用遗传算法计算新的权值，其步骤具体流程图参见图4：

(201)将上传的权值作为初始染色体(向量)，并调用公式：$F^{\prime }\left(x\right)=\frac{{\lambda }_1{\alpha }_1}{f_1\left(x\right)}+\frac{{\lambda }_2{\alpha }_2}{f_2\left(x\right)}+\frac{{\lambda }_3{\alpha }_3}{f_3\left(x\right)}$计算其适应度；

(202)对染色体(向量)进行编码；

(203)对编码以后的染色体进行选择，交换、变异，使之生成新的染色体；

(204)计算新染色体的适应度；

(205)比较与原染色体的适应度，保留适应度高的染色体，然后重复(203)～(205)步骤；

(206)当新染色体的适应度小于原染色体的适应度时，进行计数；大于时，计数清零。当计数到100次时停止GA算法，返回此时的染色体值；

(3)RNC将新计算所得的权值发给Node B。

以上所述仅为本发明的优选实施例，并不用于限制本发明，显然，其它技术人员可以对本发明进行各种改动和变型。因此可以理解，根据本发明的具体实施方式只是其示范作用，并不用于限制本发明的保护范围。