1 引言

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

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

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

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

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

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

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

在無線通信系統(tǒng)中，基站的數(shù)據(jù)吞吐能力意味著基站承載移動無線業(yè)務的能力。因此著重分析基站的數(shù)據(jù)吞吐能力，嘗試分析單位計算資源與其能夠處理的基帶數(shù)據(jù)量之間的關系，該分析將能夠為集中式蜂窩網(wǎng)架構下計算資源的分配提供實際的指導意義。

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

通過上述分析，可以將計算資源和業(yè)務帶寬聯(lián)系起來。因此，可以將對計算資源的需求轉化為對帶寬的需求。

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

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

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

其中Ccost為與任務數(shù)相關的計算開銷，單位為MIPS，那么定義為當前任務數(shù)下的“帶寬損耗”Breduce:

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

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

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

圖1 計算資源分配示意圖

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

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

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

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

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

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

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

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

3 計算資源分配算法設計與實現(xiàn)

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

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

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

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

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

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

通過上述分析發(fā)現(xiàn)FFD算法的主要問題是由于任務分配不均勻導致的算法效率低下。雖然FF算法未排序，從一定程度上避免了FFD算法的問題，但是由于是在線算法，無法擁有業(yè)務負載感知的能力，因此對于一些混合應用場景下一段周期內(nèi)大量大帶寬任務連續(xù)出現(xiàn)的問題，F(xiàn)F算法還是會有比較明顯的計算資源浪費問題，如在未來5G中以eMBB（增強型移動帶寬）應用為主的混合應用場景中。

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

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

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

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

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

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

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

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

4 實驗仿真與結果分析

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

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

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

仿真結果如下。

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

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

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

5 結束語

圖2 不同算法開啟計算單元數(shù)對比

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

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