集中式蜂窩網(wǎng)架構(gòu)下計(jì)算資源分配算法研究*

1 引言

隨著移動(dòng)通信技術(shù)的迅速發(fā)展，人們對(duì)移動(dòng)數(shù)據(jù)的需求呈指數(shù)增長(zhǎng)[1]，現(xiàn)有移動(dòng)通信系統(tǒng)中通常采用的大規(guī)?；竞?jiǎn)單物理疊加的部署方式將不再適用。一方面，根據(jù)移動(dòng)運(yùn)營(yíng)商的運(yùn)營(yíng)報(bào)告顯示，移動(dòng)運(yùn)營(yíng)商花費(fèi)在基站運(yùn)營(yíng)維護(hù)的成本高達(dá)50%以上[2]，如果繼續(xù)部署大量的基站將會(huì)加劇維護(hù)成本。另一方面，傳統(tǒng)基站的組網(wǎng)架構(gòu)無(wú)法解決如“潮汐效應(yīng)”這樣的問(wèn)題，造成資源浪費(fèi)較為嚴(yán)重。因此，為了解決傳統(tǒng)架構(gòu)的上述問(wèn)題，業(yè)界提出了集中式蜂窩接入網(wǎng)的概念和架構(gòu)，如中國(guó)移動(dòng)C-RAN[2]，中科院計(jì)算技術(shù)研究所超級(jí)基站[3]架構(gòu)。集中式蜂窩接入網(wǎng)中，通過(guò)集中式部署的計(jì)算資源池為移動(dòng)用戶業(yè)務(wù)提供計(jì)算資源需求，因此，如何對(duì)集中式的計(jì)算資源進(jìn)行高效的動(dòng)態(tài)分配是當(dāng)前研究的重點(diǎn)。

目前，大規(guī)模集中式的處理資源的分配算法研究主要集中在計(jì)算機(jī)領(lǐng)域云計(jì)算環(huán)境下。在云計(jì)算領(lǐng)域中，大量的研究將處理資源的分配歸納為虛擬機(jī)的放置問(wèn)題[4][5]，并引入裝箱問(wèn)題的建模方式對(duì)其進(jìn)行求解。由于并未結(jié)合通信接入網(wǎng)的特點(diǎn)如用戶，業(yè)務(wù)等，因此不具有典型的參考意義。

針對(duì)上述問(wèn)題，本文將結(jié)合移動(dòng)通信接入網(wǎng)特性，對(duì)基于通用處理器的集中式蜂窩網(wǎng)架構(gòu)下的計(jì)算資源分配算法進(jìn)行研究。

在傳統(tǒng)蜂窩網(wǎng)系統(tǒng)中，會(huì)為基帶數(shù)據(jù)的處理提供專用的處理單元，如DSP，F(xiàn)PGA等專用芯片。而在未來(lái)基于通用平臺(tái)集中式蜂窩網(wǎng)架構(gòu)下，提倡將基帶數(shù)據(jù)的處理轉(zhuǎn)移到通用平臺(tái)上，以提升架構(gòu)的靈活性，在提供計(jì)算資源來(lái)處理峰值負(fù)載的同時(shí)，滿足通信時(shí)延的要求。

在現(xiàn)有通用平臺(tái)集中式蜂窩網(wǎng)架構(gòu)下關(guān)于計(jì)算資源分配的研究中，通用處理器用于處理基帶數(shù)據(jù)的計(jì)算資源需求并沒(méi)有給出一個(gè)明確的定義。因此本文較為深入的分析了通用處理器處理基帶數(shù)據(jù)的計(jì)算資源需求，并嘗試給出需求模型，基于該模型研究了計(jì)算資源分配的算法，最后給出了算法的仿真結(jié)果。

2 系統(tǒng)模型與問(wèn)題定義

已有研究結(jié)果顯示，在通用平臺(tái)下利用軟基站處理基帶數(shù)據(jù)的負(fù)載（負(fù)載定義為通用處理器處理LTE每子幀所用的時(shí)間，該時(shí)間滿足LTE通信時(shí)延要求）很好的近似為調(diào)制編碼階數(shù)MCS和信道資源PRB的線性函數(shù)[6]。對(duì)于通用計(jì)算單元來(lái)說(shuō)，計(jì)算單元的負(fù)載可以描述為該任務(wù)在該計(jì)算單元上的計(jì)算資源需求，通常為MIPS（Million Instructions Per Second）。

在無(wú)線通信系統(tǒng)中，基站的數(shù)據(jù)吞吐能力意味著基站承載移動(dòng)無(wú)線業(yè)務(wù)的能力。因此著重分析基站的數(shù)據(jù)吞吐能力，嘗試分析單位計(jì)算資源與其能夠處理的基帶數(shù)據(jù)量之間的關(guān)系，該分析將能夠?yàn)榧惺椒涓C網(wǎng)架構(gòu)下計(jì)算資源的分配提供實(shí)際的指導(dǎo)意義。

通過(guò)分析無(wú)線通信相關(guān)知識(shí)，在一定的基站載波帶寬和調(diào)制方式下，某個(gè)業(yè)務(wù)所需數(shù)據(jù)帶寬（Mbps）由PRB和MCS所決定。

通過(guò)上述分析，可以將計(jì)算資源和業(yè)務(wù)帶寬聯(lián)系起來(lái)。因此，可以將對(duì)計(jì)算資源的需求轉(zhuǎn)化為對(duì)帶寬的需求。

假設(shè)如下情況：在理想的信道環(huán)境下，某個(gè)軟基站內(nèi)只有一個(gè)用戶在做持續(xù)穩(wěn)定的業(yè)務(wù)，每個(gè)LTE子幀內(nèi)MCS和PRB均固定并穩(wěn)定在較高的值，因此由于MCS和PRB一定，那么單位時(shí)間內(nèi)的數(shù)據(jù)吞吐帶寬即為一定的，假設(shè)為b（Mbps），并且計(jì)算單元處理此用戶的業(yè)務(wù)數(shù)據(jù)所需的計(jì)算資源也一定，假設(shè)為c（MIPS），通過(guò)上述描述，可以描述出計(jì)算資源MIPS到數(shù)據(jù)帶寬Mbps的映射關(guān)系。映射關(guān)系定義如下：

上式中μ即為當(dāng)前平臺(tái)下的計(jì)算資源MIPS到數(shù)據(jù)帶寬Mbps之間的映射系數(shù)，單位為。通過(guò)該映射系數(shù)可以估算出當(dāng)前平臺(tái)下單一處理單元的極限數(shù)據(jù)帶寬的處理能力。假設(shè)當(dāng)前平臺(tái)下計(jì)算單元能力為C（MIPS），并且計(jì)算單元配置的物理帶寬足夠大，如果不考慮開(kāi)銷，那么其所能處理的業(yè)務(wù)數(shù)據(jù)帶寬極限為（Mbps）。

當(dāng)多用戶的任務(wù)分散在通用平臺(tái)上更細(xì)粒度的調(diào)度單位，如CPU核或線程，那么就需要考慮到系統(tǒng)在多用戶任務(wù)間進(jìn)行上下文切換和控制上的計(jì)算開(kāi)銷。通過(guò)分析通用平臺(tái)下實(shí)時(shí)操作系統(tǒng)常用任務(wù)調(diào)度算法，發(fā)現(xiàn)其復(fù)雜度為O(n2)[7][8]，如果繼續(xù)考慮到通信實(shí)時(shí)性較高的要求，那么多用戶時(shí)任務(wù)調(diào)度的開(kāi)銷就不能忽略，假設(shè)任務(wù)調(diào)度的計(jì)算開(kāi)銷與復(fù)雜度成正比，則計(jì)算開(kāi)銷與用戶數(shù)滿足下式：

其中Ccost為與任務(wù)數(shù)相關(guān)的計(jì)算開(kāi)銷，單位為MIPS，那么定義為當(dāng)前任務(wù)數(shù)下的“帶寬損耗”Breduce:

基于上述幾點(diǎn)的分析，結(jié)合集中式蜂窩網(wǎng)系統(tǒng)的特點(diǎn)，對(duì)基帶池計(jì)算資源分配問(wèn)題進(jìn)行建模。

本章假設(shè)當(dāng)前的集中式蜂窩網(wǎng)系統(tǒng)依托于前述通用平臺(tái)下，基帶數(shù)據(jù)均由實(shí)時(shí)性和可靠性經(jīng)過(guò)優(yōu)化得到保證的通用平臺(tái)上運(yùn)行的軟基站來(lái)進(jìn)行處理。在當(dāng)前集中式架構(gòu)中，對(duì)所有的計(jì)算資源是進(jìn)行統(tǒng)一調(diào)度的，稱之為計(jì)算資源管控。

假設(shè)一個(gè)接入網(wǎng)計(jì)算資源池內(nèi)配置有N個(gè)計(jì)算單元實(shí)體PU。每個(gè)計(jì)算單元實(shí)體的軟硬件配置相同，CPU核數(shù)為T，因此基帶數(shù)據(jù)帶寬處理上限也相同，均為B。某段時(shí)間內(nèi)有M個(gè)用戶進(jìn)行移動(dòng)業(yè)務(wù)，每個(gè)用戶的業(yè)務(wù)需求的帶寬為。計(jì)算資源的分配示意圖如圖1所示：

圖1 計(jì)算資源分配示意圖

本文考慮如何根據(jù)用戶業(yè)務(wù)帶寬需求，動(dòng)態(tài)地分配計(jì)算資源，為此，進(jìn)一步做如下假設(shè)：

①每個(gè)用戶業(yè)務(wù)的處理需求被視為一個(gè)處理任務(wù)并且僅能在系統(tǒng)中某一個(gè)計(jì)算單元上獲得；

②每個(gè)計(jì)算單元可以同時(shí)處理多個(gè)用戶的業(yè)務(wù)處理需求，但是需要考慮多用戶業(yè)務(wù)時(shí)計(jì)算開(kāi)銷帶來(lái)的“帶寬損耗“，其定義見(jiàn)公式（3）；每個(gè)計(jì)算單元實(shí)體PUi上承載的用戶業(yè)務(wù)帶寬總和為Bi，可以表示為

每個(gè)計(jì)算單元上已承載的業(yè)務(wù)數(shù)為由于無(wú)線通信中通信時(shí)延和可靠性的要求，在某一個(gè)統(tǒng)一調(diào)度周期內(nèi)，單一業(yè)務(wù)的處理需求需要獨(dú)占一個(gè)CPU核以滿足通信低時(shí)延高可靠的保證，假設(shè)PUi上的業(yè)務(wù)數(shù)為Si，可以表示為：

其中，xj如公式（5）所示。

根據(jù)上述系統(tǒng)模型，本文將重點(diǎn)研究如何根據(jù)系統(tǒng)中業(yè)務(wù)帶寬負(fù)載需求，在保證不同用戶業(yè)務(wù)帶寬需求的情況下，通過(guò)動(dòng)態(tài)分配計(jì)算資源，最小化系統(tǒng)實(shí)際開(kāi)啟計(jì)算單元數(shù)量。實(shí)際開(kāi)啟計(jì)算單元數(shù)量最小可以表示為目標(biāo)函數(shù)：

其中，（7-1）表示如果計(jì)算單元上承載了業(yè)務(wù)即表示該計(jì)算單元為開(kāi)啟狀態(tài)，（7-2）表示每個(gè)計(jì)算單元實(shí)體PUi上承載的用戶業(yè)務(wù)帶寬總和Bi與多用戶計(jì)算開(kāi)銷帶來(lái)的“帶寬損耗”之和不超過(guò)B，（7-3）表示計(jì)算單元實(shí)體PUi上承載的用戶業(yè)務(wù)帶寬總和Bi，（7-4）表示計(jì)算單元實(shí)體PUi上的“帶寬損耗”（7-5）表示計(jì)算單元實(shí)體上承載的任務(wù)數(shù)，（7-6）表示每個(gè)計(jì)算單元上同時(shí)承載的業(yè)務(wù)數(shù)不超過(guò)計(jì)算單元核數(shù)，（7-7）表示任務(wù)bj是否在計(jì)算單元實(shí)體PUi，若是，則xj為1，否則為0。

通過(guò)分析問(wèn)題（7）可以歸結(jié)為帶約束的一維裝箱問(wèn)題，約束在于裝箱時(shí)需要考慮到箱子的容量會(huì)受到已裝箱任務(wù)數(shù)量的“損耗”影響以及箱子中可裝任務(wù)數(shù)量的上限，對(duì)于上述問(wèn)題的最優(yōu)解可通過(guò)遍歷所有的資源分配組合來(lái)得到，但是遍歷所有組合的方法的復(fù)雜度隨著問(wèn)題規(guī)模的增加而指數(shù)上升，無(wú)法在多項(xiàng)式時(shí)間內(nèi)獲得最優(yōu)解，此即為NP-Hard問(wèn)題[9]。針對(duì)此問(wèn)題，通常通過(guò)采取相應(yīng)的啟發(fā)式算法來(lái)獲得問(wèn)題的近似最優(yōu)解。

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

3.1 經(jīng)典裝箱算法分析

對(duì)于傳統(tǒng)裝箱問(wèn)題會(huì)采用首次適應(yīng)算法（First Fit）來(lái)求解，算法原理是根據(jù)當(dāng)前目標(biāo)大小從已開(kāi)啟箱子中選擇滿足目標(biāo)大小的第一個(gè)箱子放入，若沒(méi)有滿足的箱子則新開(kāi)啟一個(gè)箱子放入。首次適應(yīng)算法是在線算法（即隨著裝箱任務(wù)的到來(lái)立即進(jìn)行裝箱），相對(duì)于離線算法（即等到任務(wù)全部到來(lái)再統(tǒng)一進(jìn)行裝）會(huì)有性能上的損失，因此在適合離線算法的場(chǎng)景下通常會(huì)采用離線算法，如降序首次適應(yīng)算法（FFD, First Fit Decreasing）。FFD算法首先將目標(biāo)物按照降序進(jìn)行重排列后再按照首次適應(yīng)算法進(jìn)行裝箱。

FFD算法本質(zhì)思想是將帶寬需求較大的任務(wù)盡量?jī)?yōu)先分配，并且在算法分配的后半段，此階段任務(wù)帶寬需求相對(duì)較小，通過(guò)帶寬需求較小的任務(wù)來(lái)逐漸填充前半段由于大帶寬任務(wù)的聚集帶來(lái)的計(jì)算單元上的碎片化空間。

上述兩種算法是針對(duì)于傳統(tǒng)無(wú)約束的一維裝箱問(wèn)題的近似最優(yōu)解法，并且FFD的算法性能要優(yōu)于FF。但是通過(guò)分析上述算法和模型，不難發(fā)現(xiàn)，F(xiàn)FD的算法性能是要低于FF算法的，主要原因是因?yàn)榈诙?jié)所提到的約束問(wèn)題，計(jì)算單元上的開(kāi)銷和任務(wù)上限的影響。FFD算法將任務(wù)排序后，前半段較大帶寬任務(wù)占滿計(jì)算單元容量，但是并未達(dá)到任務(wù)上限，后半段剩下大量較小帶寬的任務(wù)只能開(kāi)啟新計(jì)算單元，此時(shí)任務(wù)上限達(dá)到而實(shí)際計(jì)算資源負(fù)載卻很低，因此實(shí)際占用計(jì)算單元會(huì)更多。

由于任務(wù)數(shù)量和帶寬容量受限的影響，F(xiàn)FD算法的離線排序優(yōu)點(diǎn)反而在本應(yīng)用場(chǎng)景下成了性能損失的缺點(diǎn)。

3.2 基于業(yè)務(wù)負(fù)載均衡（SLB，Service Load Balance）的分配算法

通過(guò)上述分析發(fā)現(xiàn)FFD算法的主要問(wèn)題是由于任務(wù)分配不均勻?qū)е碌乃惴ㄐ实拖隆ｋm然FF算法未排序，從一定程度上避免了FFD算法的問(wèn)題，但是由于是在線算法，無(wú)法擁有業(yè)務(wù)負(fù)載感知的能力，因此對(duì)于一些混合應(yīng)用場(chǎng)景下一段周期內(nèi)大量大帶寬任務(wù)連續(xù)出現(xiàn)的問(wèn)題，F(xiàn)F算法還是會(huì)有比較明顯的計(jì)算資源浪費(fèi)問(wèn)題，如在未來(lái)5G中以eMBB（增強(qiáng)型移動(dòng)帶寬）應(yīng)用為主的混合應(yīng)用場(chǎng)景中。

為了解決上述問(wèn)題，受到負(fù)載均衡思想[10]的啟發(fā)，本節(jié)提出了基于業(yè)務(wù)負(fù)載均衡的分配算法，該算法結(jié)合了交叉算法[11]（簡(jiǎn)稱CF算法）和FFD算法，算法思想主要是盡量將業(yè)務(wù)均勻分配到已開(kāi)啟的計(jì)算單元上并同時(shí)保持計(jì)算單元盡量被占滿。

算法具體執(zhí)行步驟如下：

①計(jì)算任務(wù)集合b中所有任務(wù)所需帶寬總和Ball和任務(wù)數(shù)Sall；

（3）從集合Pα中選擇前Ni個(gè)計(jì)算單元組成第i次分配集合Pβ,i，并將這些計(jì)算單元從未分配任務(wù)計(jì)算資源集合Pα中刪除，對(duì)待分配任務(wù)集合b進(jìn)行降序排列，并且將集合b分裂成個(gè)子集合，分別為b1,…,bt。

（4）對(duì)Pβ,i中E個(gè)計(jì)算單元Pβ,i,e執(zhí)行如下步驟：

（5）對(duì)每一個(gè)子集合bx中剩余的任務(wù)，在計(jì)算資源集合Pβ,i中進(jìn)行FFD算法的分配過(guò)程，直到Pβ,i中無(wú)計(jì)算單元能繼續(xù)承載bx中任何一個(gè)剩余任務(wù)，將Pβ,i合并到已分配任務(wù)計(jì)算資源集合Pβ。

（6）對(duì)仍然剩余任務(wù)的子集合合并成待分配任務(wù)集合b，如果集合b中任務(wù)帶寬總和，則對(duì)集合b在未分配任務(wù)計(jì)算資源集合Pα中進(jìn)行降序首次適應(yīng)算法的分配過(guò)程，直到所有任務(wù)的帶寬需求得到滿足；否則，對(duì)集合b執(zhí)行步驟2到步驟6的迭代過(guò)程。

上述算法的分配過(guò)程實(shí)際是每次選取一個(gè)最大不飽和計(jì)算資源集合，然后通過(guò)CF算法將任務(wù)較為均勻的分配在該集合中每個(gè)計(jì)算單元上，避免將連續(xù)的大帶寬任務(wù)或小帶寬任務(wù)集中分配在同一個(gè)計(jì)算單元上，后續(xù)利用FFD算法對(duì)該計(jì)算資源集合進(jìn)行填充，重復(fù)此過(guò)程直至所有任務(wù)被分配完畢。

4 實(shí)驗(yàn)仿真與結(jié)果分析

本節(jié)對(duì)第三節(jié)所提算法進(jìn)行實(shí)驗(yàn)仿真，聯(lián)合比較與分析，對(duì)算法性能進(jìn)行了評(píng)估。

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

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

仿真結(jié)果如下。

從圖2中可以看出，在均勻隨機(jī)分布的任務(wù)到來(lái)順序下，F(xiàn)F算法和SLB算法性能幾乎相同，而FFD算法性能較差，如圖中所示，符合前述結(jié)論。

由于FF算法是在線算法，無(wú)法控制業(yè)務(wù)到來(lái)的順序，因此在任務(wù)順序滿足均勻隨機(jī)分布時(shí)擁有接近最優(yōu)的性能表現(xiàn)，但是當(dāng)

任務(wù)到來(lái)的順序在某一分配算法周期內(nèi)有序階段較多時(shí)，其性能下降較為明顯。如圖3中所示，在某一周期內(nèi)有序任務(wù)越來(lái)越多時(shí)其算法結(jié)果表現(xiàn)越來(lái)越差，最差時(shí)為該周期內(nèi)任務(wù)全局升序有序，即該算法的性能下界。由于SLB算法具有業(yè)務(wù)負(fù)載感知能力，因此與任務(wù)到來(lái)順序無(wú)關(guān)，對(duì)于同一任務(wù)序列，不管其中任務(wù)到來(lái)順序如何，其總能獲得近似最優(yōu)性能表現(xiàn)。

5 結(jié)束語(yǔ)

圖2 不同算法開(kāi)啟計(jì)算單元數(shù)對(duì)比

圖3 FF算法與SLB算法性能比較

本文對(duì)集中式蜂窩網(wǎng)架構(gòu)下計(jì)算資源的分配問(wèn)題展開(kāi)研究，首先給出了計(jì)算資源到通信業(yè)務(wù)帶寬的一種映射關(guān)系，并基于此提出了集中式蜂窩網(wǎng)架構(gòu)下計(jì)算資源的分配模型及基于業(yè)務(wù)負(fù)載均衡的計(jì)算資源分配算法。系統(tǒng)仿真表明，本文提出的算法在多種任務(wù)場(chǎng)景下均能取得近似最優(yōu)解。