面向MTC应用的计算资源柔性分配

侯延昭　曹世伟　陶小峰

基于机器类通信（MTC）业务的速率需求和计算需求，研究了对移动通信网络计算资源分配方法，给出了计算资源分配模型，提出了一种基于组合优化的计算资源分配算法来解决计算资源受限的问题。仿真结果表明提出的次优化算法与传统的轮询方式相比可以获得约10%的增益。

机器类通信；软基站；计算资源分配；组合优化

机器类通信（MTC）是指利用自动控制及网络通信等技术，在没有人为干预的情况下实现机器与机器之间自主数据通信与信息交互的一系列技术或技术组合的总称[1]。它为不同类型的终端设备建立实时通信连接并进行数据传输提供了一种有效的途径。据预测，截至2020年，MTC连接设备数将超过50亿个，且应用场景和业务类型更加多元化和差异化[2]。这都给移动网络在计算和处理方面带来了较大的挑战。另一方面，未来5G网络将是一张多制式多场景共存的异构通信网络，基于高性能通用处理器的软基站（GPP-SBS）[3]拥有更强的可编程性、更小巧、更廉价，成为一种典型的基站类型，将广泛部署于5G网络中。GPP-SBS中所有的数字信号计算与处理均通过多核CPU（GPP）来实现，但其处理能力是有限的，尤其在面向大量MTC广泛存在的移动网络中，计算逐渐成为制约移动网络性能的“瓶颈”。

在传统的移动通信系统中，无线资源的管理主要指对时间、频率、功率等的分配和调度[4-6]，并将计算资源纳入资源管理的维度。因而通过对通信系统中的计算资源进行有效的分配和管理以降低计算资源对系统性能的约束变得愈发重要和迫切。目前，对于计算资源的管理在计算机网络领域已有大量的研究，例如文献[7-10]提出了虚拟资源在云计算中的分配。在文献[7]中用混合整数规划问题来描述最优云网络映射问题并采用一种启发式的方法来解决该问题。文献[8]中列出了云计算中的多种资源分配算法，例如优化资源调度算法、基于市场的资源分配策略（RAS-M）、控制拥塞的公平资源分配等等。但在无线通信中对于计算资源管理的研究目前却十分有限。文献[11-13]提出了软件定义无线电（SDR）平台中的计算资源管理方案：文献[11]中提出了一种基于处理能力和设备间互通能力的资源模型，并给出了信号处理过程与处理设备间的映射算法；文献[12]中提出了一种根据成本函数和无线场景调整的动态映射算法。在文献[11-13]中，计算资源的管理与分配都是基于不同通信标准的信号处理功能模块进行的。然而随着现代通信的发展，用户业务种类越来越多，不同业务对于处理资源的需求也有很大的差别，面向业务导向的无线资源管理愈发重要。

本文提出了一种基于不同MTC业务特性的计算资源分配方案：通过对GPP-SBS中的计算资源与业务速率做出映射，并根据不同业务的速率对计算资源进行分配，以达到最大化计算资源利用率的目的。本文组织如下，第1部分给出了计算资源与数据速率的映射关系，建立了计算资源分配模型。第2部分给出了计算资源分配的数学表达并给出了基于组合数学的具体算法。第3部分给出了该算法的性能仿真分析，最后进行了总结。

1 计算资源建模

在本文所述的软基站中，所有无线通信的数据处理均由高性能通用处理器（即多核CPU）完成。要对高性能通用处理器的计算资源（处理能力）进行合理的分配，首先需要找到计算能力与传统通信的传输能力的映射关系。通常高性能通用处理器的计算资源或者计算能力用单位MIPS来衡量，而传统通信的传输能力由单位Mb/s来度量。在本节中给出MIPS和Mb/s的映射关系，以便于我们根据不同的业务速率需求来分配计算资源。

在GPP-SBS中，对于不同的处理器，不同的通信系统原型及不同的处理算法与代码，实际中MIPS与Mb/s的对应关系都是有所不同的。但是对于一个确定的软基站系统，MIPS与Mb/s的映射是确定的。

MIPS与Mb/s的映射模型如图1所示。假设软基站（SBS）在[t1]时间内接收到[α]比特数据，并且完全处理这些数据用了[t2]时间并花费了[β]条指令。

这里，我们给出该模型所示映射的数学表达式：

[Mbps=αt1βt2×MIPS] （1）

计算资源块（CRB）通过上式来定义。SBS总的计算处理能力是I MIPS，由式（1）可得总的计算资源时C Mb/s。若在SBS中有N条可调度分配的线程，每条线程定义为一个计算资源块（CRB），则有N个CRB对应N条线程。

在本文中，计算资源的分配是基于不同业务的业务速率需求的。通过上文中的定义，GPP基于SBS中的计算资源分配可以描述为将N个CRB分配给M个业务。计算资源分配模型如图2所示，其中，[ai]（Mb/s）是CRB的处理能力，[Rk]业务k的数据速率要求。

2 计算资源分配算法

计算资源分配的目的是满足业务速率需求条件下最大化计算资源利用率。我们首先为单个业务分配计算资源的算法，进而给出了多业务的计算资源分配算法。

2.1 单业务的分配算法

首先，我们定义业务k的计算资源利用率为：

[ηk=Rkj=1Nkaj] （2）

其中：

[aj∈Ωk]（[j=1，2...，Nk]）

[j=1Nkaj≥Rk]

这里[Rk]（Mb/s）是业务k的数据速率，[ai]（Mb/s）是CRB j的处理能力，[Ωk]是分配给业务k的CRB集合，[Nk]是分配给业务k的CRB数目。

设Ω是所有可分配CRB的集合，Ωk是分配给业务k的CRB集合，使得[ηk]最大。为单个业务分配计算资源的问题可以用组合优化问题Q描述：

[Q=] （3）

其中：

[I={a1，a2，...，aN；Rk}]

[Ωk={ai|i=1，2，...，N}]

[Y={y=aj|j=1，2，...Nk；j=1Nkaj≥Rk}]

[F=ηk]

[opt=max]

这里I是问题Q的输入数据集合；Ωk是可行解元素的集合；Y是可行解集合；F是所有可行解的目标函数；而opt表示问题Q是一个最大化问题。

上面的问题并不复杂，包含的离散数据并不多，通过组合优化中的全搜索方法可以获得最优解[14-15]。算法描述如下：

算法一：为单个业务k分配CRB算法

2.2 多业务的次优化分配

上述算法描述了为单个业务分配计算资源。

当有M个业务同时到达时，我们需要全面的考虑M个业务来分配计算资源。首先我们定义为M个业务分配CRB的计算资源利用率。为M个业务分配CRB的计算资源利用率如下：

[η=k=1KRkk=1Ki=1Nkai] （4）

其中：

[ai∈Ωk]（[i=1，2，...，N]）

[i=1Nkai≥Rk]

这里[Rk]，k从1到K，是已获得计算资源分配的业务。其次优化算法是最优化的算法的一种情况。由于CRB间的处理能力差别不大，所以次优解可以通过为M个业务的一种排列做分配来得到。与此同时，考虑到M个业务的优先级，我们只需要按照业务优先级的降序为业务分配CRB即可。

这里，集合[R={R1，R2，...，RM}]是M个业务按优先级排列的数据速率；[Ansk]是业务k的解集合。算法可描述如下：

算法二：M个业务的次优化算法

分配结束之后，未分配业务进入排队序列并提升下一次分配的优先级别。

2.3 多业务的最优化分配

由于次优化算法是最优化算法的一种情况，所以我们可以在上文的次优化算法的基础上用全搜索比较容易的得到最优解。

为了得到最优解，我们队M个业务做全搜索。M个业务的所有排列数是M！。

我们需要顺序的对M！种排列做M！次上文的次优化算法，然后比较所得到的M！个计算资源利用率，最大的利用率就对应最优解，其流程如图3所示：

但是最优化算法的复杂度较高。当对M个业务做分配时，其算法复杂度是次优化算分的M！倍。例如，当仅对10个业务同时分配时，最优化算法的复杂度就是次优化算分的3 628 800倍了。可以看到在分配多业务时最优化算法的复杂度是十分高的。而且从第3章节的仿真可以看出次优化算法和最优化算法的性能差别并不大。

3 仿真结果

在本章节，我们对上文提出的算法做了数值仿真分析，重点是对次优化算法的仿真分析。接着我们通过仿真比较了次优化算法和无算法的CRB顺序分配之间的计算资源利用率。我们仿真了M个业务同时到达而CRB数目不同情况下的计算资源利用率。具体参数如表1所示：

仿真结果如图4和图5所示。

图4所示为基于最优化算法和次优化算法的计算资源利用率。当可用CRB数目为16到20时，最优化算法和次优化算法均由一个业务无可行解。可以看到当计算资源不足时计算资源的利用率是不稳定的。当CRB数目超过21后，所有的业务均由可行解。这种情况下，次优化算法的利用率稳定增加且越来越接近最优化算法，而且在计算资源充足的情况下分配算法的计算资源利用率接近100%。总的来说，最优化算法和次优化算法的计算资源利用率都达到比较高的值，并且二者之间的差别不大。

图5所示为基于次优化算法和CRB顺序分配的计算资源利用率比较。当CRB数目为16到20时次优化算法和CRB顺序分配均由一个业务无可行解，但是CRB数目为21到22时，CRB顺序分配任然有一个业务无可行解。且CRB顺序分配的计算资源利用率在有新的业务被分配之前都是不变的。从图5我们可见次优化算法对计算资源利用率的提升十分明显。

4 结束语

本文提出了GPP-SBS下面向不同MTC业务需求的计算资源分配模型，给出了分配模型的数学表达式并提出了基于组合优化的计算资源分配算法，其中主要描述了具有较低复杂度的次优化算法。通过仿真和对比分析，次优化分配算法可以在较低的计算复杂度下达到高的计算资源利用率。

参考文献

[1] 简鑫， 曾孝平， 贾云健， 等. 机器类通信流量建模与过载控制 [J]. 通信学报， 2013，

34（9）：123-131

[2] 石华宇， 唐伦， 陈前斌. 3GPP R12 MTC终端功耗优化研究进展 [J]. 电讯技术， 2013，53（12）：1659-1666

[3] TAO X F， HOU Y H， HE H Y， WANG K D， XU Y Y. GPP-based soft base station designing and optimization （invited paper） [C]//Proceedings of the Communications and Networking in China （CHINACOM）， 2012 7th International ICST Conference on ， 8-10 Aug.， 2012： 49-53

[4] RHEE W， CIOFFI J M. Increase in capacity of multiuser OFDM system using dynamic subchannel allocation [C]//Proceedings of the Vehicular Technology Conference Proceedings， 2000. VTC 2000-Spring Tokyo. 2000 IEEE 51st， 2000，2：1085-1089

[5] SHEN Z K， ANDREWS J G.， EVANS B L. Adaptive resource allocation in multiuser OFDM systems with proportional rate constraints [J]. Wireless Communications， IEEE Transactions on， 2005，4（6）： 2726-2737

[6] GUAN N， ZHOU Y Q， TIAN L， SUN G， SHI J L. QoS guaranteed resource block allocation algorithm for LTE systems [C]//Proceedings of the Wireless and Mobile Computing， Networking and Communications （WiMob）， 2011 IEEE 7th International Conference on， 10-12 Oct.， 2011：307-312

[7] PAPAGIANNI C， LEIVADEAS A， PAPAVASSILIOU S， MAGLARIS V， CERVELLO-PASTOR C， MONJE A. On the optimal allocation of virtual resources in cloud computing networks [J]. Computers， IEEE Transactions on， 2013，62（6）： 1060-1071

[8] MOHAN N R.R， RAJ E B. Resource Allocation Techniques in Cloud Computing -- Research Challenges for Applications [C]//Proceedings of the Computational Intelligence and Communication Networks （CICN）， 2012 Fourth International Conference on， 3-5 Nov.， 2012：556-560

[9] WANG E D， WU N， LI X. QoS-Oriented Monitoring Model of Cloud Computing Resources Availability [C]//Proceedings of the Computational and Information Sciences （ICCIS）， 2013 Fifth International Conference on ， 21-23 June， 2013：1537-1540

[10] HE B， HEINZELMAN，W， JANSSEN C A， SHI J Y. Mobile computing - A green computing resource [C]//Proceedings of the Wireless Communications and Networking Conference （WCNC）， 2013 IEEE， 7-10 April， 2013：4451-4456

[11] MAROJEVIC V， REVES X， GELONCH A. Computing Resource Management for SDR Platforms [C]//Proceedings of the Personal， Indoor and Mobile Radio Communications， 2005. PIMRC 2005. IEEE 16th International Symposium on， 11-14 Sept.， 2005：685-689

[12] MAROJEVIC V， BALLESTE X R， GELONCH A. A Computing Resource Management Framework for Software-Defined Radios [J]. Computers， IEEE Transactions on， 2008，57（10）： 1399-1412

[13] WANG L， CHEN S. System Resource Allocation of TD-SCDMA Terminal Based on SDR Platforms [C]//Proceedings of the Wireless Communications Networking and Mobile Computing （WiCOM）， 2010 6th International Conference on， 23-25 Sept.， 2010：1-4

[14] DAVID P. Algorithm for Knapsack Problem [D]. Denmark： University of Copenhagen， 1995

[15] DAVID P. A Fast Algorithm for Strongly Correlated Knapsack Problem [J]. Discrete applied mathematics， 1998，89（1）：197-212