張新蘋，王園園，田霖，郝樹良

?

基于業(yè)務(wù)類型的集中式接入網(wǎng)基站處理資源分配算法

張新蘋1,2，王園園2，田霖2，郝樹良1

（1. 重慶郵電大學(xué)，重慶 400065；2. 中國科學(xué)院計算技術(shù)研究所，北京 100190）

現(xiàn)有的資源分配算法研究主要面向數(shù)據(jù)中心和云計算環(huán)境展開，未能充分考慮基站處理資源的多樣性（CPU、內(nèi)存、網(wǎng)絡(luò)帶寬、FPGA、DSP）和業(yè)務(wù)種類的多樣性，不能直接應(yīng)用于集中式接入網(wǎng)架構(gòu)中。針對該問題，提出了基于業(yè)務(wù)類型的資源分配算法，首先采用Fisher分割方法，根據(jù)用戶業(yè)務(wù)類型對不同類型計算資源的需求，對業(yè)務(wù)進行分類，然后利用資源分配均衡策略分配基站處理資源。仿真結(jié)果表明，該算法有效地減少了開啟物理服務(wù)器的個數(shù)并提高了物理服務(wù)器的資源利用率，達到了綠色節(jié)能的目的。

集中式接入網(wǎng)；基站處理資源分配；用戶業(yè)務(wù)類型；Fisher分割方法；資源分配均衡策略

1 引言

近年來，蜂窩移動通信系統(tǒng)發(fā)展迅猛，網(wǎng)絡(luò)容量需求呈指數(shù)級增長[1,2]。傳統(tǒng)蜂窩移動通信系統(tǒng)采用大規(guī)模部署基站的方式提升地區(qū)覆蓋容量，各基站之間相對獨立，基站處理資源按照基站覆蓋區(qū)域內(nèi)用戶業(yè)務(wù)峰值容量部署，且資源獨占。這種組網(wǎng)架構(gòu)使得孤立的基站不能處理具有“潮汐效應(yīng)”的動態(tài)網(wǎng)絡(luò)負載，當負載降低時，基站處理資源的利用率就會明顯降低，資源浪費嚴重。為了解決傳統(tǒng)架構(gòu)的這些問題，業(yè)界提出了集中式接入網(wǎng)的概念和架構(gòu)，例如中國移動的C-RAN（centralized, cooperative, cloud RAN）[3]和中國科學(xué)院計算技術(shù)研究所（以下簡稱中科院計算所）的物理集中、邏輯分布的超級基站架構(gòu)[4]。在集中式接入網(wǎng)中，基站處理資源集中部署形成資源池，基于資源水平共享、統(tǒng)計復(fù)用，通過資源管控實現(xiàn)處理資源的動態(tài)分配[5-7]。然而集中統(tǒng)一地管理所有處理資源必然給系統(tǒng)管理和資源分配帶來新的挑戰(zhàn)。如何根據(jù)業(yè)務(wù)實際負載需求，對基站處理資源進行靈活的分配，提高基站處理資源的利用率，是集中式接入網(wǎng)架構(gòu)的一個重要研究點。

目前，大規(guī)模處理資源分配算法的研究主要集中在集中式數(shù)據(jù)中心、云計算中心等環(huán)境下。云計算資源調(diào)度通常以虛擬機為資源分配單位[8-10]，將虛擬機調(diào)度到一個或多個物理機上，研究的是虛擬機和物理機之間的映射關(guān)系。大量的研究將這種問題歸結(jié)為常見的裝箱問題[11-12]，求解目標是用盡可能少的物理資源來滿足所有虛擬機的資源需求。參考文獻[13-14]在CPU、內(nèi)存資源約束情況下建立模型，以提高資源利用率為目標，通過遺傳算法求解多約束優(yōu)化問題，獲得物理機和虛擬機的優(yōu)化映射方案。但是采用啟發(fā)式算法求的只是局部最優(yōu)解，時間復(fù)雜度較高，可擴展性和算法實時性不強。參考文獻[15-16]提出了基于業(yè)務(wù)量預(yù)測的資源分配算法。云服務(wù)提供商首先對云用戶的業(yè)務(wù)量進行預(yù)測，然后按照所預(yù)測的業(yè)務(wù)量為相應(yīng)的云用戶預(yù)先配置虛擬機資源，存在的不足是當突發(fā)業(yè)務(wù)到來時會出現(xiàn)預(yù)測業(yè)務(wù)量不準確的情況，這就會導(dǎo)致預(yù)先配置的虛擬機資源過大或過小，從而造成資源利用率較低或不滿足業(yè)務(wù)需求的問題。由于無線接入網(wǎng)所需的資源類型、處理的用戶業(yè)務(wù)類型等與云計算場景都有較大不同，因此云計算中的資源調(diào)度算法雖然具有一定的借鑒意義，但不能直接用于接入網(wǎng)中。在集中式接入網(wǎng)架構(gòu)下，基站處理資源分配算法主要考慮以下兩點：

? 集中式接入網(wǎng)的基站具備類型多樣的計算資源，包括CPU、內(nèi)存、網(wǎng)絡(luò)帶寬、FPGA、DSP等，其中CPU、內(nèi)存、網(wǎng)絡(luò)帶寬主要完成數(shù)據(jù)處理和傳輸；DSP、FPGA作為基帶處理的加速器，主要作用是快速地實現(xiàn)各種數(shù)字信號處理算法，滿足通信系統(tǒng)的實時性要求。

? 通信系統(tǒng)中用戶業(yè)務(wù)的多樣性決定了對資源的需求量不同[17]，如對于計算類業(yè)務(wù)（用戶數(shù)據(jù)處理），它們對計算資源的需求較高，而對于存儲類任務(wù)（下載音頻或視頻），它們對存儲和帶寬資源的需求較高。

針對以上兩點，本文提出了基于業(yè)務(wù)類型的基站處理資源分配算法（station processing resource allocation algorithm，SPRAA），主要思想是在集中式接入網(wǎng)架構(gòu)下進行基站處理資源分配時，根據(jù)用戶業(yè)務(wù)類型對不同類型計算資源的需求，將處理資源需求互補的不同業(yè)務(wù)組合到一起，按業(yè)務(wù)組進行處理資源的分配，有助于提高資源利用率。本文以減少物理服務(wù)器個數(shù)和提高資源利用率為目標對上述問題進行數(shù)學(xué)建模，通過Fisher業(yè)務(wù)分類和資源分配均衡策略來完成處理資源的靈活分配，達到提高資源利用率的目的。

2 處理資源分配算法的設(shè)計與實現(xiàn)

2.1 算法設(shè)計與實現(xiàn)

2.1.1 業(yè)務(wù)類型分類

在某一個時間窗內(nèi)到達的業(yè)務(wù)種類是多樣的，不同類型的業(yè)務(wù)，其數(shù)據(jù)處理對不同類型處理資源的需求量也會不同[18-19]。為了降低資源分配的復(fù)雜度，首先對到達的業(yè)務(wù)進行分類，分類標準是業(yè)務(wù)對基站處理資源（CPU、內(nèi)存、帶寬資源等）的需求大小。為了把業(yè)務(wù)分成類，同時使得業(yè)務(wù)分類結(jié)果更加精確，避免出現(xiàn)“步驟4 根據(jù)資源占重比求得業(yè)務(wù)類型”中業(yè)務(wù)類型不確定的情況，比如當各類資源占重比為（0.4，0.1，0.4，0.1）時，CPU和帶寬的占重比是相同的，確定業(yè)務(wù)類型時會出現(xiàn)分歧。考慮到業(yè)務(wù)分類結(jié)果的精確性，分類方法采取參考文獻[20]的Fisher最優(yōu)分割法，分類步驟如下。

步驟1 數(shù)據(jù)標準化

步驟2 計算極差矩陣

步驟3 最優(yōu)分割

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

根據(jù)用戶業(yè)務(wù)對基站處理資源（CPU、內(nèi)存、帶寬、DSP資源）需求的差異，在物理服務(wù)器上建立相應(yīng)的處理實體（processing entity，PE）處理用戶業(yè)務(wù)。為了實現(xiàn)業(yè)務(wù)處理的隔離和安全性，規(guī)定一個處理實體對應(yīng)一個業(yè)務(wù)處理。傳統(tǒng)的思路會根據(jù)處理資源（以CPU、內(nèi)存資源為例）需求來分配資源，如圖1(a)所示，其中大矩形表示一個物理服務(wù)器的CPU、內(nèi)存資源的總量，圖1(a)的服務(wù)器支撐了兩個對內(nèi)存需求較高的用戶業(yè)務(wù)，分別為PE1和PE2。圖1(a)中深色區(qū)域表示物理服務(wù)器所剩的可用處理資源，由圖1可見，此物理服務(wù)器還剩余大量的CPU資源，但內(nèi)存資源已經(jīng)不足，難以建立一個新的PE。如果有第3個用戶業(yè)務(wù)請求，在建立對應(yīng)的處理實體時需要再開啟另一個物理服務(wù)器，這樣就造成圖1(a)的物理服務(wù)器CPU資源的浪費，出現(xiàn)了資源分配不均衡的問題。

針對該問題，需要將分屬不同類的處理資源需求互補的PE配置在同一個物理服務(wù)器，充分利用CPU、內(nèi)存等資源，盡量減少物理服務(wù)器開啟的數(shù)量，如圖2(a)的物理服務(wù)器所示。本文以提高資源利用率為目標，根據(jù)Fisher分割法將某一周期內(nèi)的業(yè)務(wù)根據(jù)對不同類計算資源需求不同分類，考慮到5種業(yè)務(wù)類型，把分類數(shù)設(shè)置為5。定義資源均衡利用率指標體現(xiàn)多類計算資源的綜合利用情況，在資源分配過程中充分考慮了資源總量的約束和分配基站處理資源的順序，如圖2所示，用資源均衡利用率和各類資源占用率兩個指標來分配基站處理資源。相對于經(jīng)典算法首次適應(yīng)算法（first fit algorithm，F(xiàn)FA），F(xiàn)FA的主要思想是按順序查找物理服務(wù)器，將PE直接部署在滿足基站處理資源要求的物理服務(wù)器上，F(xiàn)FA下的物理服務(wù)器的資源使用情況如圖1所示，本文的算法更有優(yōu)勢。

圖2 SPRAA下物理服務(wù)器的資源利用情況

本文綜合考慮CPU、內(nèi)存、帶寬、DSP資源，設(shè)每個物理服務(wù)器的資源量相同，其中CPU總量為SC，內(nèi)存總量為SM，帶寬總量為SBW。DSP資源是以DSP芯片的形式呈現(xiàn)，用芯片數(shù)量SD=4來表示DSP資源總量。系統(tǒng)中共配置個服務(wù)器，用一個矩陣來描述物理服務(wù)器的資源配置情況：

本文通過以下兩個指標來衡量業(yè)務(wù)需求組合的優(yōu)越性。

表示為：

在某個周期內(nèi)，本文根據(jù)用戶業(yè)務(wù)對各類計算資源需求參數(shù)的不同，將業(yè)務(wù)請求分為=5類，業(yè)務(wù)類型由式（10）~式（14）來確定。在資源分配過程中盡量將不同業(yè)務(wù)需求的處理實體分配在同一個物理服務(wù)器，避免物理服務(wù)器出現(xiàn)嚴重的資源分配不均衡現(xiàn)象。在集中式接入網(wǎng)架構(gòu)下基于用戶業(yè)務(wù)的資源分配步驟如下。

步驟5 開啟一個新的物理服務(wù)器，將PE建立在此物理服務(wù)器上，轉(zhuǎn)至步驟6。

2.2 集中式接入網(wǎng)架構(gòu)下的基站處理資源管理架構(gòu)

3 仿真分析

本文通過在MATLAB2012a仿真驗證所提算法的性能。綜合考慮了物理服務(wù)器中的CPU、內(nèi)存、網(wǎng)絡(luò)帶寬、DSP資源，將基站處理實體分為=5類（CPU型、內(nèi)存型、帶寬型、DSP型和平衡型），并按上文給的資源分配算法進行處理資源的分配。為了驗證算法的有效性，本文與經(jīng)典算法FFA做比較。

在建立業(yè)務(wù)對應(yīng)的處理實體時，資源開銷主要包括兩部分：

（2）當多個處理實體加載到同一個物理服務(wù)器時，這些處理實體對應(yīng)的數(shù)據(jù)處理和控制相關(guān)進程會在物理服務(wù)器中調(diào)度執(zhí)行，這些調(diào)度本身也會產(chǎn)生處理資源開銷，比如多個處理實體進程切換時的進程激活，同一個處理實體內(nèi)部進程間調(diào)度，這些都會造成CPU資源的開銷。

本文主要考慮到業(yè)務(wù)本身對各類資源的需求，為了表征（2）對CPU資源的消耗，把CPU資源的重要參數(shù)設(shè)置得大一點。在仿真中，把CPU資源的重要參數(shù)設(shè)置為0.4，內(nèi)存、帶寬和DSP資源統(tǒng)一設(shè)置為0.2。

仿真參數(shù)設(shè)置見表1。

表1 仿真參數(shù)設(shè)置

圖5對比了所提算法和FFA的物理服務(wù)器開啟數(shù)目?？梢钥闯觯疚奶岢龅乃惴軠p少開啟物理服務(wù)器的個數(shù)，主要因為在資源分配過程中盡量將不同業(yè)務(wù)需求的處理實體配置在同一個物理服務(wù)器上，最大限度地利用CPU、內(nèi)存、網(wǎng)絡(luò)帶寬和DSP資源。

圖5 物理服務(wù)器開啟數(shù)目對比

4 結(jié)束語

本文在分析了集中式架構(gòu)下資源分配的研究現(xiàn)狀后，考慮到用戶業(yè)務(wù)類型對不同類型計算資源的需求，提出了一種基于業(yè)務(wù)類型的集中式接入網(wǎng)的基站處理資源分配算法。在資源分配過程中，將不同的處理資源需求互補的業(yè)務(wù)組合到一起，解決了物理服務(wù)器的資源分配不均衡的問題，仿真表明所提算法減少了開啟物理服務(wù)器的個數(shù)，同時提高了物理服務(wù)器的資源利用率。在下一步的研究中，若用戶某種業(yè)務(wù)突然增加，可能會造成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] 田霖, 翟國偉, 黃亮, 等. 基于集中式接入網(wǎng)架構(gòu)的異構(gòu)無線網(wǎng)絡(luò)資源管理技術(shù)研究[J]. 電信科學(xué), 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] 殷波, 張云勇, 房秉毅, 等. 面向成本優(yōu)化的云計算資源分配方法研究[J]. 電信科學(xué), 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] 吳清烈, 郭昱, 武忠. 云計算服務(wù)與大規(guī)模定制模式應(yīng)用[J].電信科學(xué), 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]. 計算機應(yīng)用, 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]. 計算機應(yīng)用研究, 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] 翟國偉. 超級基站架構(gòu)下協(xié)議處理資源分配和管理方法的研究[D]. 北京: 中國科學(xué)院大學(xué), 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關(guān)鍵技術(shù)與標準綜述[J]. 電信科學(xué), 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最優(yōu)分割法的聚類分析應(yīng)用[D]. 鄭州: 鄭州大學(xué), 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?），女，重慶郵電大學(xué)碩士生，主要研究方向為綠色無線通信系統(tǒng)、5G。

王園園（1986?），女，博士，中國科學(xué)院計算技術(shù)研究所助理研究員，主要研究方向為綠色無線通信系統(tǒng)、5G、無線接入網(wǎng)絡(luò)虛擬化等。

田霖（1980?），女，博士，中國科學(xué)院計算技術(shù)研究所副研究員，主要研究方向為綠色無線通信系統(tǒng)與無線資源管理技術(shù)。

郝樹良（1991?），男，重慶郵電大學(xué)碩士生，主要研究方向為5G新型多址接入技術(shù)。

2017?12?19；

2018?06?08

國家自然科學(xué)基金資助項目（No.61431001）

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