基于业务类型的集中式接入网基站处理资源分配算法

张新苹，王园园，田霖，郝树良



基于业务类型的集中式接入网基站处理资源分配算法

张新苹1,2，王园园2，田霖2，郝树良1

（1. 重庆邮电大学，重庆 400065；2. 中国科学院计算技术研究所，北京 100190）

现有的资源分配算法研究主要面向数据中心和云计算环境展开，未能充分考虑基站处理资源的多样性（CPU、内存、网络带宽、FPGA、DSP）和业务种类的多样性，不能直接应用于集中式接入网架构中。针对该问题，提出了基于业务类型的资源分配算法，首先采用Fisher分割方法，根据用户业务类型对不同类型计算资源的需求，对业务进行分类，然后利用资源分配均衡策略分配基站处理资源。仿真结果表明，该算法有效地减少了开启物理服务器的个数并提高了物理服务器的资源利用率，达到了绿色节能的目的。

集中式接入网；基站处理资源分配；用户业务类型；Fisher分割方法；资源分配均衡策略

1 引言

近年来，蜂窝移动通信系统发展迅猛，网络容量需求呈指数级增长[1,2]。传统蜂窝移动通信系统采用大规模部署基站的方式提升地区覆盖容量，各基站之间相对独立，基站处理资源按照基站覆盖区域内用户业务峰值容量部署，且资源独占。这种组网架构使得孤立的基站不能处理具有“潮汐效应”的动态网络负载，当负载降低时，基站处理资源的利用率就会明显降低，资源浪费严重。为了解决传统架构的这些问题，业界提出了集中式接入网的概念和架构，例如中国移动的C-RAN（centralized, cooperative, cloud RAN）[3]和中国科学院计算技术研究所（以下简称中科院计算所）的物理集中、逻辑分布的超级基站架构[4]。在集中式接入网中，基站处理资源集中部署形成资源池，基于资源水平共享、统计复用，通过资源管控实现处理资源的动态分配[5-7]。然而集中统一地管理所有处理资源必然给系统管理和资源分配带来新的挑战。如何根据业务实际负载需求，对基站处理资源进行灵活的分配，提高基站处理资源的利用率，是集中式接入网架构的一个重要研究点。

目前，大规模处理资源分配算法的研究主要集中在集中式数据中心、云计算中心等环境下。云计算资源调度通常以虚拟机为资源分配单位[8-10]，将虚拟机调度到一个或多个物理机上，研究的是虚拟机和物理机之间的映射关系。大量的研究将这种问题归结为常见的装箱问题[11-12]，求解目标是用尽可能少的物理资源来满足所有虚拟机的资源需求。参考文献[13-14]在CPU、内存资源约束情况下建立模型，以提高资源利用率为目标，通过遗传算法求解多约束优化问题，获得物理机和虚拟机的优化映射方案。但是采用启发式算法求的只是局部最优解，时间复杂度较高，可扩展性和算法实时性不强。参考文献[15-16]提出了基于业务量预测的资源分配算法。云服务提供商首先对云用户的业务量进行预测，然后按照所预测的业务量为相应的云用户预先配置虚拟机资源，存在的不足是当突发业务到来时会出现预测业务量不准确的情况，这就会导致预先配置的虚拟机资源过大或过小，从而造成资源利用率较低或不满足业务需求的问题。由于无线接入网所需的资源类型、处理的用户业务类型等与云计算场景都有较大不同，因此云计算中的资源调度算法虽然具有一定的借鉴意义，但不能直接用于接入网中。在集中式接入网架构下，基站处理资源分配算法主要考虑以下两点：

• 集中式接入网的基站具备类型多样的计算资源，包括CPU、内存、网络带宽、FPGA、DSP等，其中CPU、内存、网络带宽主要完成数据处理和传输；DSP、FPGA作为基带处理的加速器，主要作用是快速地实现各种数字信号处理算法，满足通信系统的实时性要求。

• 通信系统中用户业务的多样性决定了对资源的需求量不同[17]，如对于计算类业务（用户数据处理），它们对计算资源的需求较高，而对于存储类任务（下载音频或视频），它们对存储和带宽资源的需求较高。

针对以上两点，本文提出了基于业务类型的基站处理资源分配算法（station processing resource allocation algorithm，SPRAA），主要思想是在集中式接入网架构下进行基站处理资源分配时，根据用户业务类型对不同类型计算资源的需求，将处理资源需求互补的不同业务组合到一起，按业务组进行处理资源的分配，有助于提高资源利用率。本文以减少物理服务器个数和提高资源利用率为目标对上述问题进行数学建模，通过Fisher业务分类和资源分配均衡策略来完成处理资源的灵活分配，达到提高资源利用率的目的。

2 处理资源分配算法的设计与实现

2.1 算法设计与实现

2.1.1 业务类型分类

在某一个时间窗内到达的业务种类是多样的，不同类型的业务，其数据处理对不同类型处理资源的需求量也会不同[18-19]。为了降低资源分配的复杂度，首先对到达的业务进行分类，分类标准是业务对基站处理资源（CPU、内存、带宽资源等）的需求大小。为了把业务分成类，同时使得业务分类结果更加精确，避免出现“步骤4 根据资源占重比求得业务类型”中业务类型不确定的情况，比如当各类资源占重比为（0.4，0.1，0.4，0.1）时，CPU和带宽的占重比是相同的，确定业务类型时会出现分歧。考虑到业务分类结果的精确性，分类方法采取参考文献[20]的Fisher最优分割法，分类步骤如下。

步骤1 数据标准化

步骤2 计算极差矩阵

步骤3 最优分割

2.1.2 资源分配均衡模型及分析

根据用户业务对基站处理资源（CPU、内存、带宽、DSP资源）需求的差异，在物理服务器上建立相应的处理实体（processing entity，PE）处理用户业务。为了实现业务处理的隔离和安全性，规定一个处理实体对应一个业务处理。传统的思路会根据处理资源（以CPU、内存资源为例）需求来分配资源，如图1(a)所示，其中大矩形表示一个物理服务器的CPU、内存资源的总量，图1(a)的服务器支撑了两个对内存需求较高的用户业务，分别为PE1和PE2。图1(a)中深色区域表示物理服务器所剩的可用处理资源，由图1可见，此物理服务器还剩余大量的CPU资源，但内存资源已经不足，难以建立一个新的PE。如果有第3个用户业务请求，在建立对应的处理实体时需要再开启另一个物理服务器，这样就造成图1(a)的物理服务器CPU资源的浪费，出现了资源分配不均衡的问题。

针对该问题，需要将分属不同类的处理资源需求互补的PE配置在同一个物理服务器，充分利用CPU、内存等资源，尽量减少物理服务器开启的数量，如图2(a)的物理服务器所示。本文以提高资源利用率为目标，根据Fisher分割法将某一周期内的业务根据对不同类计算资源需求不同分类，考虑到5种业务类型，把分类数设置为5。定义资源均衡利用率指标体现多类计算资源的综合利用情况，在资源分配过程中充分考虑了资源总量的约束和分配基站处理资源的顺序，如图2所示，用资源均衡利用率和各类资源占用率两个指标来分配基站处理资源。相对于经典算法首次适应算法（first fit algorithm，FFA），FFA的主要思想是按顺序查找物理服务器，将PE直接部署在满足基站处理资源要求的物理服务器上，FFA下的物理服务器的资源使用情况如图1所示，本文的算法更有优势。

图2 SPRAA下物理服务器的资源利用情况

本文综合考虑CPU、内存、带宽、DSP资源，设每个物理服务器的资源量相同，其中CPU总量为SC，内存总量为SM，带宽总量为SBW。DSP资源是以DSP芯片的形式呈现，用芯片数量SD=4来表示DSP资源总量。系统中共配置个服务器，用一个矩阵来描述物理服务器的资源配置情况：

本文通过以下两个指标来衡量业务需求组合的优越性。

表示为：

在某个周期内，本文根据用户业务对各类计算资源需求参数的不同，将业务请求分为=5类，业务类型由式（10）~式（14）来确定。在资源分配过程中尽量将不同业务需求的处理实体分配在同一个物理服务器，避免物理服务器出现严重的资源分配不均衡现象。在集中式接入网架构下基于用户业务的资源分配步骤如下。

步骤5 开启一个新的物理服务器，将PE建立在此物理服务器上，转至步骤6。

2.2 集中式接入网架构下的基站处理资源管理架构

3 仿真分析

本文通过在MATLAB2012a仿真验证所提算法的性能。综合考虑了物理服务器中的CPU、内存、网络带宽、DSP资源，将基站处理实体分为=5类（CPU型、内存型、带宽型、DSP型和平衡型），并按上文给的资源分配算法进行处理资源的分配。为了验证算法的有效性，本文与经典算法FFA做比较。

在建立业务对应的处理实体时，资源开销主要包括两部分：

（2）当多个处理实体加载到同一个物理服务器时，这些处理实体对应的数据处理和控制相关进程会在物理服务器中调度执行，这些调度本身也会产生处理资源开销，比如多个处理实体进程切换时的进程激活，同一个处理实体内部进程间调度，这些都会造成CPU资源的开销。

本文主要考虑到业务本身对各类资源的需求，为了表征（2）对CPU资源的消耗，把CPU资源的重要参数设置得大一点。在仿真中，把CPU资源的重要参数设置为0.4，内存、带宽和DSP资源统一设置为0.2。

仿真参数设置见表1。

表1 仿真参数设置

图5对比了所提算法和FFA的物理服务器开启数目。可以看出，本文提出的算法能减少开启物理服务器的个数，主要因为在资源分配过程中尽量将不同业务需求的处理实体配置在同一个物理服务器上，最大限度地利用CPU、内存、网络带宽和DSP资源。

图5 物理服务器开启数目对比

4 结束语

本文在分析了集中式架构下资源分配的研究现状后，考虑到用户业务类型对不同类型计算资源的需求，提出了一种基于业务类型的集中式接入网的基站处理资源分配算法。在资源分配过程中，将不同的处理资源需求互补的业务组合到一起，解决了物理服务器的资源分配不均衡的问题，仿真表明所提算法减少了开启物理服务器的个数，同时提高了物理服务器的资源利用率。在下一步的研究中，若用户某种业务突然增加，可能会造成PE的迁移，采用的迁移算法仍需要进一步研究。

[1] LIU L, ZHOU Y Q, TIAN L, et al. Load aware joint CoMP clustering and inter-cell resource scheduling in heterogeneous ultra dense cellular networks[J]. IEEE Transactions on Vehicular Technology, Early Access, 2017, 99(11): 1-14.

[2] ZHOU Y Q, LIU H, PAN Z, et al. Cooperative multicast with location aware distributed mobile relay selection: performance analysis and optimized design[J]. IEEE Transactions on Vehicular Technology, 2017, 66(3): 8291-8302.

[3] China Mobile. C-RAN: the road towards green RAN[R]. 2015.

[4] QIAN M, WANG Y, ZHOUY, et al. A super base station based centralized network architecture for 5G mobile communication systems [J]. Digital Communications & Networks, 2015, 1(2): 152-159.

[5] HUANG L, ZHOU Y. Coverage optimization for femtocell clusters using particle swarm optimization[C]//2012 IEEE International Conference on Communications, June 10-15, 2012, Ottawa, ON, Canada. Piscataway: IEEE Press, 2012: 612-615.

[6] 田霖, 翟国伟, 黄亮, 等. 基于集中式接入网架构的异构无线网络资源管理技术研究[J]. 电信科学, 2013, 29(6): 25-27.

TIAN L, ZHAI G W, HUANG L, et al. Research on key technologies of heterogeneous wireless network resource management based on centralized radio access network architecture[J]. Telecommunications Science, 2013, 29(6): 25-27.

[7] ZHAI G W, TIAN L, ZHOU Y Q, et al. Load diversity based optimal processing resource allocation for super base stations in centralized radio access networks[J]. Science China Information Sciences, 2014, 57(4): 1-12.

[8] MELL P, GRANCE T. The NIST definition of cloud computing(draft)[R]. 2013.

[9] 殷波, 张云勇, 房秉毅, 等. 面向成本优化的云计算资源分配方法研究[J]. 电信科学, 2014, 30(11): 22-26, 32.

YIN B, ZHANG Y Y, FANG B Y, et al. Cloud resource allocation method based on elastic resource adjustment[J]. Telecommunications Science, 2014, 30(11): 22-26, 32.

[10] 吴清烈, 郭昱, 武忠. 云计算服务与大规模定制模式应用[J].电信科学, 2010, 26(9): 74-78.

WU Q L, GUO Y, WU Z. Study on cloud computing services and mass customization applications[J]. Telecommunications Science, 2010, 26(9): 74-78.

[11] 徐骁勇, 柯涛, 刘梦娟, 等. 面向云平台的资源分配策略研究[J]. 计算机应用, 2013, 33(20): 299-307.

XU X Y, KE T, LIU M J, et al. Research on resource allocation strategies in cloud computing[J]. Journal of Computer Applications, 2013, 33(20): 299-307.

[12] 陈小娇, 陈世平, 方芳. 云计算中虚拟机资源分配算法[J]. 计算机应用研究, 2014, 31(9): 2585-2616.

CHEN X J, CHEN S P, FANG F. Research on virtual machine resource allocation algorithm in cloud computing[J]. Journal of Computer Applications Research, 2014, 31(9): 2585-2616.

[13] LU J. Improved genetic algorithm-based resource scheduling strategy in cloud computing[C]//2016 International Conference on Smart City and Systems Engineering, Nov 25-26, 2016, Changsha, China. Piscataway: IEEE Press, 2016: 230-234.

[14] WANG S, GU H, WU G. A new approach to multi-objective virtual machine placement in virtualized data center[C]//IEEE Eighth International Conference on Networking, Architecture and Storage, July 17-19, 2013, Xi’an, China. Piscataway: IEEE Press, 2013: 331-335.

[15] CHEN N S, FANG X P. A cloud computing resource scheduling scheme based on estimation of distribution algorithm[C]//The 2014 2nd International Conference on Systems and Information, Nov 15-17, 2014, Shanghai, China. Piscataway: IEEE Press, 2014: 304-308.

[16] GHRIBI C, HADJI M, ZEGHLACHE D. Energy efficient VM scheduling for cloud data centers: exact allocation and migration algorithms[C]//2013 IEEE/ACM 13th International Symposium on Cluster, Cloud, and Grid Computing, May 13-16, 2013, Delft, the Netherlands. Piscataway: IEEE Press, 2013: 671-678.

[17] IMT-2020(5G)推进组. 5G概念白皮书[R]. 2015.

IMT-2020(5G) Propulsion Group. 5G white paper [R]. 2015.

[18] 翟国伟. 超级基站架构下协议处理资源分配和管理方法的研究[D]. 北京: 中国科学院大学, 2016.

ZHAI G W. Research on protocol processing resource allocation and management in super BS architecture [D]. Beijing: University of Chinese Academy of Sciences, 2016.

[19] 王庆扬, 谢沛荣, 熊尚坤, 等. 5G关键技术与标准综述[J]. 电信科学, 2017, 33(11): 112-122.

WANG Q Y, XIE P R, XIONG S K, et al. Key technology and standardization progress for 5G[J]. Telecommunications Science, 2017, 33(11): 112-122.

[20] 武琳琳. 基于Fisher最优分割法的聚类分析应用[D]. 郑州: 郑州大学, 2013.

WU L L. Cluster analysis based on the method of Fisher optimal division[D]. Zhengzhou: Zhengzhou University, 2013.

Service aware base station processing resource allocation for centralized radio access network

ZHANG Xinping1,2, WANG Yuanyuan2, TIAN Lin2, HAO Shuliang1

1. Chongqing University of Posts and Telecommunications, Chongqing 400065, China 2. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China

Current research on resource allocation algorithms mainly focuses on data centers, and cloud computing environments. These resource allocation algorithms did not consider the diversity of processing resources (CPU, memory, network bandwidth, FPGA, DSP) and the diversity of service types in the centralized base station, resulting in the low processing resource utilization. In order to solve this problem, a service oriented base station processing resource allocation algorithm was proposed. Firstly, the Fisher partition method was used to classify the base station’s processing resource requirements according to the user’s service request. Then, the resource allocation balancing strategy was used to allocate the base station processing resources. Experimental results show that the algorithm is effective to reduce the number of physical servers and improves the resource utilization of the servers, realizing energy conservation and communications.

centralized radio access network, base station processing resource allocation, user service type, Fisher partition method, resource allocation balancing strategy

TP393

A

10.11959/j.issn.1000−0801.2018202

张新苹（1992−），女，重庆邮电大学硕士生，主要研究方向为绿色无线通信系统、5G。

王园园（1986−），女，博士，中国科学院计算技术研究所助理研究员，主要研究方向为绿色无线通信系统、5G、无线接入网络虚拟化等。

田霖（1980−），女，博士，中国科学院计算技术研究所副研究员，主要研究方向为绿色无线通信系统与无线资源管理技术。

郝树良（1991−），男，重庆邮电大学硕士生，主要研究方向为5G新型多址接入技术。

2017−12−19；

2018−06−08

国家自然科学基金资助项目（No.61431001）

The National Natural Science Foundation of China (No.61431001)