侯延昭　曹世偉　陶小峰

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

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

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

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

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

1 計算資源建模

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

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

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

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

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

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

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

2 計算資源分配算法

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

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

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

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

其中：

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

[j=1Nkaj≥Rk]

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

設(shè)Ω是所有可分配CRB的集合，Ωk是分配給業(yè)務(wù)k的CRB集合，使得[ηk]最大。為單個業(yè)務(wù)分配計算資源的問題可以用組合優(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是一個最大化問題。

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

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

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

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

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

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

其中：

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

[i=1Nkai≥Rk]

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

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

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

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

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

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

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

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

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

3 仿真結(jié)果

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

仿真結(jié)果如圖4和圖5所示。

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

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

4 結(jié)束語

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

參考文獻

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

34（9）：123-131

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