侯延昭　曹世偉　陶小峰

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

機器類通信；軟基站；計算資源分配；組合優(yōu)化

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

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

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

1 計算資源建模

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

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

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

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

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

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

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

2 計算資源分配算法

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

2.1 單業(yè)務的分配算法

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

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

其中：

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

[j=1Nkaj≥Rk]

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

設Ω是所有可分配CRB的集合，Ωk是分配給業(yè)務k的CRB集合，使得[ηk]最大。為單個業(yè)務分配計算資源的問題可以用組合優(yōu)化問題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的輸入數(shù)據(jù)集合；Ωk是可行解元素的集合；Y是可行解集合；F是所有可行解的目標函數(shù)；而opt表示問題Q是一個最大化問題。

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

算法一：為單個業(yè)務k分配CRB算法

2.2 多業(yè)務的次優(yōu)化分配

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

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

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

其中：

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

[i=1Nkai≥Rk]

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

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

算法二：M個業(yè)務的次優(yōu)化算法

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

2.3 多業(yè)務的最優(yōu)化分配

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

為了得到最優(yōu)解，我們隊M個業(yè)務做全搜索。M個業(yè)務的所有排列數(shù)是M！。

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

但是最優(yōu)化算法的復雜度較高。當對M個業(yè)務做分配時，其算法復雜度是次優(yōu)化算分的M！倍。例如，當僅對10個業(yè)務同時分配時，最優(yōu)化算法的復雜度就是次優(yōu)化算分的3 628 800倍了?？梢钥吹皆诜峙涠鄻I(yè)務時最優(yōu)化算法的復雜度是十分高的。而且從第3章節(jié)的仿真可以看出次優(yōu)化算法和最優(yōu)化算法的性能差別并不大。

3 仿真結果

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

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

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

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

4 結束語

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

參考文獻

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

34（9）：123-131

[2] 石華宇， 唐倫， 陳前斌. 3GPP R12 MTC終端功耗優(yōu)化研究進展 [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