面向MTC應用的計算資源柔性分配

侯延昭　曹世偉　陶小峰

基于機器類通信（MTC）業務的速率需求和計算需求，研究了對移動通信網絡計算資源分配方法，給出了計算資源分配模型，提出了一種基于組合優化的計算資源分配算法來解決計算資源受限的問題。仿真結果表明提出的次優化算法與傳統的輪詢方式相比可以獲得約10%的增益。

機器類通信；軟基站；計算資源分配；組合優化

機器類通信（MTC）是指利用自動控制及網絡通信等技術，在沒有人為干預的情況下實現機器與機器之間自主數據通信與信息交互的一系列技術或技術組合的總稱[1]。它為不同類型的終端設備建立實時通信連接并進行數據傳輸提供了一種有效的途徑。據預測，截至2020年，MTC連接設備數將超過50億個，且應用場景和業務類型更加多元化和差異化[2]。這都給移動網絡在計算和處理方面帶來了較大的挑戰。另一方面，未來5G網絡將是一張多制式多場景共存的異構通信網絡，基于高性能通用處理器的軟基站（GPP-SBS）[3]擁有更強的可編程性、更小巧、更廉價，成為一種典型的基站類型，將廣泛部署于5G網絡中。GPP-SBS中所有的數字信號計算與處理均通過多核CPU（GPP）來實現，但其處理能力是有限的，尤其在面向大量MTC廣泛存在的移動網絡中，計算逐漸成為制約移動網絡性能的“瓶頸”。

在傳統的移動通信系統中，無線資源的管理主要指對時間、頻率、功率等的分配和調度[4-6]，并將計算資源納入資源管理的維度。因而通過對通信系統中的計算資源進行有效的分配和管理以降低計算資源對系統性能的約束變得愈發重要和迫切。目前，對于計算資源的管理在計算機網絡領域已有大量的研究，例如文獻[7-10]提出了虛擬資源在云計算中的分配。在文獻[7]中用混合整數規劃問題來描述最優云網絡映射問題并采用一種啟發式的方法來解決該問題。文獻[8]中列出了云計算中的多種資源分配算法，例如優化資源調度算法、基于市場的資源分配策略（RAS-M）、控制擁塞的公平資源分配等等。但在無線通信中對于計算資源管理的研究目前卻十分有限。文獻[11-13]提出了軟件定義無線電（SDR）平臺中的計算資源管理方案：文獻[11]中提出了一種基于處理能力和設備間互通能力的資源模型，并給出了信號處理過程與處理設備間的映射算法；文獻[12]中提出了一種根據成本函數和無線場景調整的動態映射算法。在文獻[11-13]中，計算資源的管理與分配都是基于不同通信標準的信號處理功能模塊進行的。然而隨著現代通信的發展，用戶業務種類越來越多，不同業務對于處理資源的需求也有很大的差別，面向業務導向的無線資源管理愈發重要。

本文提出了一種基于不同MTC業務特性的計算資源分配方案：通過對GPP-SBS中的計算資源與業務速率做出映射，并根據不同業務的速率對計算資源進行分配，以達到最大化計算資源利用率的目的。本文組織如下，第1部分給出了計算資源與數據速率的映射關系，建立了計算資源分配模型。第2部分給出了計算資源分配的數學表達并給出了基于組合數學的具體算法。第3部分給出了該算法的性能仿真分析，最后進行了總結。

1 計算資源建模

在本文所述的軟基站中，所有無線通信的數據處理均由高性能通用處理器（即多核CPU）完成。要對高性能通用處理器的計算資源（處理能力）進行合理的分配，首先需要找到計算能力與傳統通信的傳輸能力的映射關系。通常高性能通用處理器的計算資源或者計算能力用單位MIPS來衡量，而傳統通信的傳輸能力由單位Mb/s來度量。在本節中給出MIPS和Mb/s的映射關系，以便于我們根據不同的業務速率需求來分配計算資源。

在GPP-SBS中，對于不同的處理器，不同的通信系統原型及不同的處理算法與代碼，實際中MIPS與Mb/s的對應關系都是有所不同的。但是對于一個確定的軟基站系統，MIPS與Mb/s的映射是確定的。

MIPS與Mb/s的映射模型如圖1所示。假設軟基站（SBS）在[t1]時間內接收到[α]比特數據，并且完全處理這些數據用了[t2]時間并花費了[β]條指令。

這里，我們給出該模型所示映射的數學表達式：

[Mbps=αt1βt2×MIPS] （1）

計算資源塊（CRB）通過上式來定義。SBS總的計算處理能力是I MIPS，由式（1）可得總的計算資源時C Mb/s。若在SBS中有N條可調度分配的線程，每條線程定義為一個計算資源塊（CRB），則有N個CRB對應N條線程。

在本文中，計算資源的分配是基于不同業務的業務速率需求的。通過上文中的定義，GPP基于SBS中的計算資源分配可以描述為將N個CRB分配給M個業務。計算資源分配模型如圖2所示，其中，[ai]（Mb/s）是CRB的處理能力，[Rk]業務k的數據速率要求。

2 計算資源分配算法

計算資源分配的目的是滿足業務速率需求條件下最大化計算資源利用率。我們首先為單個業務分配計算資源的算法，進而給出了多業務的計算資源分配算法。

2.1 單業務的分配算法

首先，我們定義業務k的計算資源利用率為：

[ηk=Rkj=1Nkaj] （2）

其中：

[aj∈Ωk]（[j=1，2...，Nk]）

[j=1Nkaj≥Rk]

這里[Rk]（Mb/s）是業務k的數據速率，[ai]（Mb/s）是CRB j的處理能力，[Ωk]是分配給業務k的CRB集合，[Nk]是分配給業務k的CRB數目。

設Ω是所有可分配CRB的集合，Ωk是分配給業務k的CRB集合，使得[ηk]最大。為單個業務分配計算資源的問題可以用組合優化問題Q描述：

[Q=] （3）

其中：

[I={a1，a2，...，aN；Rk}]

[Ωk={ai|i=1，2，...，N}]

[Y={y=aj|j=1，2，...Nk；j=1Nkaj≥Rk}]

[F=ηk]

[opt=max]

這里I是問題Q的輸入數據集合；Ωk是可行解元素的集合；Y是可行解集合；F是所有可行解的目標函數；而opt表示問題Q是一個最大化問題。

上面的問題并不復雜，包含的離散數據并不多，通過組合優化中的全搜索方法可以獲得最優解[14-15]。算法描述如下：

算法一：為單個業務k分配CRB算法

2.2 多業務的次優化分配

上述算法描述了為單個業務分配計算資源。

當有M個業務同時到達時，我們需要全面的考慮M個業務來分配計算資源。首先我們定義為M個業務分配CRB的計算資源利用率。為M個業務分配CRB的計算資源利用率如下：

[η=k=1KRkk=1Ki=1Nkai] （4）

其中：

[ai∈Ωk]（[i=1，2，...，N]）

[i=1Nkai≥Rk]

這里[Rk]，k從1到K，是已獲得計算資源分配的業務。其次優化算法是最優化的算法的一種情況。由于CRB間的處理能力差別不大，所以次優解可以通過為M個業務的一種排列做分配來得到。與此同時，考慮到M個業務的優先級，我們只需要按照業務優先級的降序為業務分配CRB即可。

這里，集合[R={R1，R2，...，RM}]是M個業務按優先級排列的數據速率；[Ansk]是業務k的解集合。算法可描述如下：

算法二：M個業務的次優化算法

分配結束之后，未分配業務進入排隊序列并提升下一次分配的優先級別。

2.3 多業務的最優化分配

由于次優化算法是最優化算法的一種情況，所以我們可以在上文的次優化算法的基礎上用全搜索比較容易的得到最優解。

為了得到最優解，我們隊M個業務做全搜索。M個業務的所有排列數是M！。

我們需要順序的對M！種排列做M！次上文的次優化算法，然后比較所得到的M！個計算資源利用率，最大的利用率就對應最優解，其流程如圖3所示：

但是最優化算法的復雜度較高。當對M個業務做分配時，其算法復雜度是次優化算分的M！倍。例如，當僅對10個業務同時分配時，最優化算法的復雜度就是次優化算分的3 628 800倍了。可以看到在分配多業務時最優化算法的復雜度是十分高的。而且從第3章節的仿真可以看出次優化算法和最優化算法的性能差別并不大。

3 仿真結果

在本章節，我們對上文提出的算法做了數值仿真分析，重點是對次優化算法的仿真分析。接著我們通過仿真比較了次優化算法和無算法的CRB順序分配之間的計算資源利用率。我們仿真了M個業務同時到達而CRB數目不同情況下的計算資源利用率。具體參數如表1所示：

仿真結果如圖4和圖5所示。

圖4所示為基于最優化算法和次優化算法的計算資源利用率。當可用CRB數目為16到20時，最優化算法和次優化算法均由一個業務無可行解。可以看到當計算資源不足時計算資源的利用率是不穩定的。當CRB數目超過21后，所有的業務均由可行解。這種情況下，次優化算法的利用率穩定增加且越來越接近最優化算法，而且在計算資源充足的情況下分配算法的計算資源利用率接近100%。總的來說，最優化算法和次優化算法的計算資源利用率都達到比較高的值，并且二者之間的差別不大。

圖5所示為基于次優化算法和CRB順序分配的計算資源利用率比較。當CRB數目為16到20時次優化算法和CRB順序分配均由一個業務無可行解，但是CRB數目為21到22時，CRB順序分配任然有一個業務無可行解。且CRB順序分配的計算資源利用率在有新的業務被分配之前都是不變的。從圖5我們可見次優化算法對計算資源利用率的提升十分明顯。

4 結束語

本文提出了GPP-SBS下面向不同MTC業務需求的計算資源分配模型，給出了分配模型的數學表達式并提出了基于組合優化的計算資源分配算法，其中主要描述了具有較低復雜度的次優化算法。通過仿真和對比分析，次優化分配算法可以在較低的計算復雜度下達到高的計算資源利用率。

參考文獻

[1] 簡鑫， 曾孝平， 賈云健， 等. 機器類通信流量建模與過載控制 [J]. 通信學報， 2013，

34（9）：123-131

[2] 石華宇， 唐倫， 陳前斌. 3GPP R12 MTC終端功耗優化研究進展 [J]. 電訊技術， 2013，53（12）：1659-1666

[3] TAO X F， HOU Y H， HE H Y， WANG K D， XU Y Y. GPP-based soft base station designing and optimization （invited paper） [C]//Proceedings of the Communications and Networking in China （CHINACOM）， 2012 7th International ICST Conference on ， 8-10 Aug.， 2012： 49-53

[4] RHEE W， CIOFFI J M. Increase in capacity of multiuser OFDM system using dynamic subchannel allocation [C]//Proceedings of the Vehicular Technology Conference Proceedings， 2000. VTC 2000-Spring Tokyo. 2000 IEEE 51st， 2000，2：1085-1089

[5] SHEN Z K， ANDREWS J G.， EVANS B L. Adaptive resource allocation in multiuser OFDM systems with proportional rate constraints [J]. Wireless Communications， IEEE Transactions on， 2005，4（6）： 2726-2737

[6] GUAN N， ZHOU Y Q， TIAN L， SUN G， SHI J L. QoS guaranteed resource block allocation algorithm for LTE systems [C]//Proceedings of the Wireless and Mobile Computing， Networking and Communications （WiMob）， 2011 IEEE 7th International Conference on， 10-12 Oct.， 2011：307-312

[7] PAPAGIANNI C， LEIVADEAS A， PAPAVASSILIOU S， MAGLARIS V， CERVELLO-PASTOR C， MONJE A. On the optimal allocation of virtual resources in cloud computing networks [J]. Computers， IEEE Transactions on， 2013，62（6）： 1060-1071

[8] MOHAN N R.R， RAJ E B. Resource Allocation Techniques in Cloud Computing -- Research Challenges for Applications [C]//Proceedings of the Computational Intelligence and Communication Networks （CICN）， 2012 Fourth International Conference on， 3-5 Nov.， 2012：556-560

[9] WANG E D， WU N， LI X. QoS-Oriented Monitoring Model of Cloud Computing Resources Availability [C]//Proceedings of the Computational and Information Sciences （ICCIS）， 2013 Fifth International Conference on ， 21-23 June， 2013：1537-1540

[10] HE B， HEINZELMAN，W， JANSSEN C A， SHI J Y. Mobile computing - A green computing resource [C]//Proceedings of the Wireless Communications and Networking Conference （WCNC）， 2013 IEEE， 7-10 April， 2013：4451-4456

[11] MAROJEVIC V， REVES X， GELONCH A. Computing Resource Management for SDR Platforms [C]//Proceedings of the Personal， Indoor and Mobile Radio Communications， 2005. PIMRC 2005. IEEE 16th International Symposium on， 11-14 Sept.， 2005：685-689

[12] MAROJEVIC V， BALLESTE X R， GELONCH A. A Computing Resource Management Framework for Software-Defined Radios [J]. Computers， IEEE Transactions on， 2008，57（10）： 1399-1412

[13] WANG L， CHEN S. System Resource Allocation of TD-SCDMA Terminal Based on SDR Platforms [C]//Proceedings of the Wireless Communications Networking and Mobile Computing （WiCOM）， 2010 6th International Conference on， 23-25 Sept.， 2010：1-4

[14] DAVID P. Algorithm for Knapsack Problem [D]. Denmark： University of Copenhagen， 1995

[15] DAVID P. A Fast Algorithm for Strongly Correlated Knapsack Problem [J]. Discrete applied mathematics， 1998，89（1）：197-212