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

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

?

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

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

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

步驟1 數(shù)據(jù)標(biāo)準(zhǔn)化

步驟2 計(jì)算極差矩陣

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

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

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

針對(duì)該問題，需要將分屬不同類的處理資源需求互補(bǔ)的PE配置在同一個(gè)物理服務(wù)器，充分利用CPU、內(nèi)存等資源，盡量減少物理服務(wù)器開啟的數(shù)量，如圖2(a)的物理服務(wù)器所示。本文以提高資源利用率為目標(biāo)，根據(jù)Fisher分割法將某一周期內(nèi)的業(yè)務(wù)根據(jù)對(duì)不同類計(jì)算資源需求不同分類，考慮到5種業(yè)務(wù)類型，把分類數(shù)設(shè)置為5。定義資源均衡利用率指標(biāo)體現(xiàn)多類計(jì)算資源的綜合利用情況，在資源分配過程中充分考慮了資源總量的約束和分配基站處理資源的順序，如圖2所示，用資源均衡利用率和各類資源占用率兩個(gè)指標(biāo)來分配基站處理資源。相對(duì)于經(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)勢(shì)。

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

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

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

表示為：

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

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

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

3 仿真分析

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

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

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

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

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

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

圖5對(duì)比了所提算法和FFA的物理服務(wù)器開啟數(shù)目?？梢钥闯?，本文提出的算法能減少開啟物理服務(wù)器的個(gè)數(shù)，主要因?yàn)樵谫Y源分配過程中盡量將不同業(yè)務(wù)需求的處理實(shí)體配置在同一個(gè)物理服務(wù)器上，最大限度地利用CPU、內(nèi)存、網(wǎng)絡(luò)帶寬和DSP資源。

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

4 結(jié)束語

本文在分析了集中式架構(gòu)下資源分配的研究現(xiàn)狀后，考慮到用戶業(yè)務(wù)類型對(duì)不同類型計(jì)算資源的需求，提出了一種基于業(yè)務(wù)類型的集中式接入網(wǎng)的基站處理資源分配算法。在資源分配過程中，將不同的處理資源需求互補(bǔ)的業(yè)務(wù)組合到一起，解決了物理服務(wù)器的資源分配不均衡的問題，仿真表明所提算法減少了開啟物理服務(wù)器的個(gè)數(shù)，同時(shí)提高了物理服務(wù)器的資源利用率。在下一步的研究中，若用戶某種業(yè)務(wù)突然增加，可能會(huì)造成PE的遷移，采用的遷移算法仍需要進(jìn)一步研究。

[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] 田霖, 翟國(guó)偉, 黃亮, 等. 基于集中式接入網(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] 殷波, 張?jiān)朴? 房秉毅, 等. 面向成本優(yōu)化的云計(jì)算資源分配方法研究[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] 吳清烈, 郭昱, 武忠. 云計(jì)算服務(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] 徐驍勇, 柯濤, 劉夢(mèng)娟, 等. 面向云平臺(tái)的資源分配策略研究[J]. 計(jì)算機(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ì)算中虛擬機(jī)資源分配算法[J]. 計(jì)算機(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)推進(jìn)組. 5G概念白皮書[R]. 2015.

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

[18] 翟國(guó)偉. 超級(jí)基站架構(gòu)下協(xié)議處理資源分配和管理方法的研究[D]. 北京: 中國(guó)科學(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] 王慶揚(yáng), 謝沛榮, 熊尚坤, 等. 5G關(guān)鍵技術(shù)與標(biāo)準(zhǔn)綜述[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é)碩士生，主要研究方向?yàn)榫G色無線通信系統(tǒng)、5G。

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

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

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

2017?12?19；

2018?06?08

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

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