基于改進式貪婪算法的5G網絡切片動態資源調度策略

陳強，劉彩霞，李凌書

?

基于改進式貪婪算法的5G網絡切片動態資源調度策略

陳強1,2，劉彩霞1,2，李凌書1,2

（1. 國家數字交換系統工程技術研究中心，河南 鄭州 450002； 2. 移動互聯網安全技術國家工程實驗室，北京 100876）

為了解決移動通信網絡中資源利用率和用戶體驗質量的瓶頸問題，5G引入網絡切片來應對用戶的巨大資源需求。提出了一種基于改進式貪婪算法的網絡切片動態資源調度策略，在切片調度和用戶調度階段，設計了一種兩層模型，即切片?用戶模型，并且結合改進式貪婪算法，使服務權重值最大的切片和優先級最高的用戶組合，完成相應的服務。該方法是將全局資源最優問題簡化為規模更小的子問題，通過每一次切片和用戶的最佳組合，從而使整個系統的資源和用戶的體驗質量達到最優。Matlab的仿真結果表明，基于改進式貪婪算法的網絡切片動態資源調度策略在系統剩余資源利用率、系統達到平均的QoE水平、系統吞吐量等方面都顯優于現行的資源調度策略，能夠更好地滿足用戶的需求。

網絡切片；切片權重值；用戶優先級；動態資源調度；改進式貪婪算法

1 引言

隨著移動通信技術的快速發展，人們對高質量服務的需求不斷增長，未來5G移動通信技術主要包括更高的數據流量業務、用戶體驗速率、海量終端連接以及更低時延等[1]。網絡資源的管理也就成為一個更具有挑戰性的任務，為了提高網絡的性能，需要合理設計資源調度策略。在系統和網絡功能、用戶體驗、安全等各個方面，不一樣的應用場景都有不同的需求，若用同一個網絡提供服務，一定會造成網絡更加凌亂和緩慢，加大網絡運維的復雜性，提高網絡運營成本，也難以實現使用網絡時需要的極限性能要求。在這種情況下，網絡切片作為一種在網絡資源管理中引入靈活性的有效方法，獲得了日益增強的重要性。網絡切片通過提供滿足系統中啟用片所必需的網絡資源引入網絡資源的靈活性和更高的利用率[2]。其最突出的特點是網絡資源的虛擬化，它允許人們以靈活、動態的方式共享相同的物理資源，以便有效利用現有資源[3]。現行的網絡切片調度策略主要從2方面考慮。

一是從用戶角度，每個用戶在通信過程中可以對應看成是一種服務，盡可能滿足用戶的體驗質量（QoE）和服務質量（QoS）是整個移動網絡發展的最終目標[4]。蜂窩數據網絡中的集中式聯合功率和接納控制機制在文獻[5]中已經被提出。為了在整個網絡中最大限度地承載用戶，Monemi等[5]開發了一種接納優先級較高用戶的機制。在這種情況下，優先級只在用戶處考慮，目的是盡可能滿足QoE值最大，在切片處卻沒有考慮本身的服務權重問題。在未來網絡切片的無線資源管理中，運營商最主要考慮的一個方面是無線資源如何分配給不同的切片以滿足這些用戶的多樣化需求。

二是從網絡切片角度，不同切片對應的服務能力和服務類型也是有差別的。首要考慮網絡層連接接納的控制實體所需的QoS水平，目的是根據控制決策、資源分配的任務為每一個用戶提供相應所需要的切片服務，旨在最大限度地提高體驗質量和服務質量，從而達到一個全局的切片資源最優的狀態[6]。Kamel等[7]提出了一種用于長期演進（LTE）系統的無線網絡虛擬化技術，可以有效地將帶寬資源分配給不同的服務提供者，以最大限度地利用資源。類似地，Shimojo等[8]提出了一種有效地將服務分組和網絡切片創建調節機制合并自動化的算法，以提高復用增益和資源使用效率。然而，該算法沒有考慮不同片之間的優先級以及用戶之間的優先級。Parsaeefard等[9]提出了一種基于信道狀態信息調整最小切片需求的迭代片配置算法，但沒有考慮網絡的全局資源利用率和層間和片內優先級。在文獻[10]中，一個下行的網絡資源分配的機制被提出，但是這個機制不考慮動態修改QoE來為移動用戶的體驗增加網絡容量和資源利用。

由于當前的切片調度無法很好地解決資源最優化的問題，只是盲目滿足用戶的QoS最大而調度資源，使整個調度過程造成很多網絡資源浪費[11]。5G現行的網絡切片服務處于單一的滿足一個或者幾個用戶的服務，而不能做到動態地均勻網絡資源[12]，不能很好地兼顧切片和用戶的配對過程，應該通過考慮它們所屬切片的優先級以及它們所需服務的優先級來管理公共網絡資源。本文提出了一種基于改進式貪婪算法的動態資源調度策略（IGADS, improved greedy algorithm dynamic resource scheduling）。在切片和用戶的配對過程中，設計了一個2層結構，利用改進式貪婪算法，在切片調度層實時地計算切片的剩余資源，不斷比較切片服務權重，同時在用戶調度層將用戶進行優先級排隊，實現權重最大的切片為優先級最高的用戶進行服務，使子過程達到最優，進而使整個系統達到資源最優，最大程度地節約網絡資源，提高了整個系統的動態靈活性。

2 新型切片調度模型與問題描述

為了更好地滿足用戶的服務質量和體驗質量最佳，使整體系統的資源分配最優，本文將這種基于改進式貪婪算法的切片調度模型分為2層結構：切片?用戶調度層。其中，調度模型2層結構如圖1所示。

圖1 調度模型兩層結構示意

2.1 虛擬網絡層

虛擬網絡層是位于物理網絡層之上的網絡切片中比較重要的一部分，在切片的資源調度過程中也起著至關重要的作用，主要是根據切片控制層發出的指令決定具體要分配多少虛擬資源給網絡切片，同時虛擬網絡層中的CPNF（控制層網絡功能）負責分配用戶的臨時ID和網絡切片類型ID（Nes-ID）[13]。在分配網絡資源時，虛擬網絡層主要根據信道情況的好壞實時調整策略。圖2是虛擬網絡層動態資源分配與現行的靜態資源分配的對比，可以明顯看出虛擬網絡層最主要的優勢在于可以節省大量的網絡資源，提高網絡資源利用率。

圖2 靜態資源分配與IGADS動態資源分配的對比

2.2 切片調度層

2.2.1 調度層的工作原理

切片調度層是連接虛擬網絡層和用戶調度層的紐帶，目的是從虛擬網絡層接收相應的資源同時將合適的切片調度給相應的用戶，是IGADS模型中最重要的一環。切片調度層根據切片自身的SLA（服務等級協議）保證資源配比，即整個調度過程是在滿足SLA的前提下進行的。在整個調度過程中，帶寬資源分配的最小傳輸單位是資源塊，其數目是與帶寬相對應的[14]。

(4)

2.2.3 切片控制器

切片控制器主要負責接收虛擬網絡層分配的資源，同時計算每個切片的權重值并按照權重大小將切片進行優先級排序，最后將切片與用戶配對完成對應服務。切片控制器最重要的功能是切片選擇功能模塊（SSF），SSF根據用戶的訂閱信息、用戶的使用類型、業務類型和用戶的能力，通過為用戶選擇合適的切片來處理用戶的初始附著請求和新會話建立的請求。在附著過程中，SSF將用戶與一個默認切片或用戶特定類型切片相關聯，然后將初始附加請求轉發到所選擇的網絡切片，并由所選擇的網絡切片進行處理[15]。在每一個TTI內，切片都會從虛擬網絡層接收到對應的網絡資源，同時也會在切片控制器的調度下與用戶進行配對并對用戶進行服務，消耗相應的網絡資源，所以每個切片的權重值是在不斷改變的，這也就是切片控制器要完成的最重要的任務之一，在滿足用戶QoE的同時，使IGADS系統資源利用率能達到最大。切片控制器的具體功能邏輯如圖3所示。其中，W為切片的權重值。

圖3 切片控制器功能邏輯

2.3 用戶調度層

3 算法描述

3.1 新型切片調度模型的實現

現有的5G調度策略都是運營商為網絡切片分配固定的資源以滿足其最低要求，根據比例公平調度算法計算出切片的優先級，按優先級從高到低的順序給網絡切片內的用戶分配資源，而沒有考慮用戶的需求優先級因素，用戶只能被動地接受切片提供的服務，無法保證用戶獲得最大的體驗質量。有些用戶可能需要高帶寬服務，卻可能被分配一個資源容量很小的切片，造成服務的中斷。本文提出的基于改進式貪婪算法的網絡切片資源動態調度策略中，目的就是讓切片和用戶達到一個最佳的組合，使用戶的QoE最大，同時使整個資源達到最優。這就要求虛擬網絡層、切片調度層、用戶調度層同時合作，保證IGADS系統能達到預期的效果。虛擬網絡層需要合理地將資源分配給運營商，分配太多則造成資源浪費，分配太少則運營商無法根據SLA創建出相應的功能切片來滿足用戶的需求[17]。而且虛擬資源調度器的CPNF功能必須判斷出服務運營商要創建實時業務的切片還是非實時業務的切片，這關系到分配帶寬資源塊的先后順序，是非常關鍵的一步，若判斷出是實時業務，則需要提前分配資源塊，以滿足實時業務所要占據的帶寬資源塊，同時也使切片的權重增大，并兼顧用戶調度。切片控制器的SSF功能主要是根據切片的權重進行調度切片，權重大的認為在這個功能上該切片可以為用戶提供更好的服務。本文滿足的前提條件是網絡切片具有相同的服務功能且來自不同的服務運營商，所以切片權重值成為衡量切片服務功能能力的一個重要指標，也是切片和用戶組合的一個重要參考指標，權重值大的切片盡量給優先級高的用戶服務，這樣才能使用戶的服務質量最佳，也能使整個系統的資源達到最優[18]。切片控制器要不斷計算更新切片的權重值，使每一個TTI內都要將切片按照權重值的大小排好隊，等待為不同優先級的用戶提供服務。用戶調度器根據用戶的臨時ID和Nes-ID收集用戶的信息，同時動態地更新用戶的優先級，完成切片與用戶的配對組合，這樣整個系統就可以達到真正的動態調度資源。其中，IGADS邏輯結構如圖4所示。

圖4 IGADS邏輯結構

3.2 基于改進式貪婪算法的切片資源動態調度策略

表1 主要參數符號定義

輸出 IGADS與現行資源調度策略對比關系

4) If the resource is real-time

16) end

17) else repeat process 8)

18) Check weight order and calculate the weight of the other slice

27) end

28) else repeat the process 18)

29) Check priority order again

30) Choose the slice with the max weight serve the user with the max priority

32) end

33) end

34) end

4 實驗結果及分析

4.1 實驗環境

為對提出的新型模型性能進行分析，仿真實驗使用配置為4 GB內存，64位Win7操作系統，Intel core2T9550處理器的計算機進行上述評估，使用Matlab進行編程，實驗中物理網絡及虛擬網絡拓撲都采用GT-ITM工具隨機生成。Matlab進行模擬切片資源分配及系統所能達到的用戶QoE大小問題的模型。通過對改進前和改進后的2個模型的對比，觀察剩余帶寬資源塊數量及所達到用戶QoE大小，從而說明新型架構在動態資源調度上的優勢。表2[12]列舉出實驗所需要的各項參數。

表2 仿真實驗的主要參數

本實驗中仿真時間設為10 s，傳輸時間間隔設置為0.1 s，如前面所描述的那樣，切片在得到資源分配之后進行權重排序，權重最大的切片為優先級最高的用戶進行服務，觀察整個系統的帶寬資源塊剩余量，及不同的策略下用戶所達到的QoE的滿意程度。

4.2 性能分析

圖5是某一用戶在10 s（100個時間間隔）內資源的使用情況，對比靜態資源調度策略和動態資源調度策略，可以清楚地顯示出兩者的優劣，靜態資源調度是固定地分配資源塊，在一段時間內不管實際的需求怎樣，分配的資源塊數都是不變的，在實際需求中，有時造成資源的極大浪費，有時造成資源的需求不足；而本文中的動態資源調度策略則是先預分配2 000個資源塊，其余的根據實際的需求變化進行調整，由于是權重最大的切片給用戶提供服務，所以可以提供的資源都比用戶此時刻的資源大，相比靜態資源調度，極大地提高了資源利用率，節省了資源。

圖5 2種資源調度策略和實際需求變化對比

圖6顯示了2種策略下系統的剩余資源百分率，從仿真的結果來看，隨著用戶數的增加，剩余資源利用率是在不斷減小的，而且在開始用戶數比較少的情況下，現有的5G調度策略和IGADS調度策略并無太大差別，但是當用戶數達到20個的時候，現行的資源調度策略剩余資源百分率僅為10%，但是IGADS的資源利用率可以達到20%，而后隨著用戶數量增加，IGADS剩余資源利用率也是明顯高于現行5G調度策略的，前者比后者平均高5%左右，當用戶數為80個的時候，系統的資源被消耗殆盡，兩者的剩余資源百分率趨于近似，整個仿真說明IGADS策略優化整合了系統的資源，在性能上確實有很大提高。

圖6 2種策略下系統的剩余資源百分率

圖7顯示了2種策略下達到的平均QoE水平情況，隨著用戶數不斷增加，2種策略能達到平均QoE水平均越來越差，說明無論哪種系統策略，用戶數的增加都會使用戶的體驗質量降低。但是從兩者的對比來看，IGADS調度策略明顯優于現有的5G調度策略。在開始用戶數為10個時，兩者的平均QoE水平差距不是很大；當用戶數達到30個時，IGADS策略的平均QoE水平已經比現行的策略高0.04左右；在用戶數為100個時，IGADS策略的平均QoE水平可以達到0.7，而現行的5G調度策略只能達到0.62，遠遠高于現行5G調度策略，而且隨著用戶數的增多，這種優勢越來越明顯，說明IGADS策略確實提高了用戶的體驗質量和服務質量。

圖7 2種策略下達到的平均QoE水平

圖8顯示了2種策略下系統的吞吐量，從仿真結果來看，IGADS調度策略的系統平均吞吐能力明顯高于當前策略下的系統平均吞吐能力，當用戶數達到60個時，IGADS策略的吞吐量比現行的5G調度策略高2 500 kbit/s，達到整個過程的最大值，隨著系統資源的消耗，兩者的吞吐量差值逐漸減小，但IGADS策略的吞吐量也遠超過現行5G調度策略，很好地解釋了圖7的仿真結果，較高的平均吞吐能力是用戶體驗質量和服務質量的保證，體現了IGADS策略的巨大優勢。

圖8 2種策略下系統吞吐量

圖9 用戶優先級與用戶等待時間、系統資源塊數量關系

5 結束語

隨著現行5G網絡切片的廣泛應用，切片的資源調度必將成為亟待解決的問題之一。通過對目前網絡切片資源調度策略的分析，考慮到擁有相同服務類型的切片有不同的權值，本文提出了一種基于改進式貪婪算法的網絡切片資源調度策略（IGADS），不斷計算切片的服務權值和用戶的優先級，動態地控制切片和用戶的配對關系，使整體達到一種資源最優的狀態，節約了大量的網絡資源，同時也能更好地提高用戶的服務質量和體驗質量。理論分析和實驗結果都表明，本文提出的基于改進式貪婪算法的新型資源調度策略確實在平均吞吐能力和用戶的QoE滿意度方面都有很大優勢。

[1] ZHAO G F, CHEN J, HAN Y B, et al. Prospective network techniques for 5G mobile communication: a survey[J]. Journal of Chongqing University of Posts and Telecommunications, 2015 , 27 (4) :441-452

[2] ANDREWS J G, BUZZI S, WAN C, et al. What will 5G be[J]. IEEE Journal on Selected Areas in Communications, 2014, 32(6):1065-1082.

[3] EINSIEDLER H J, GAVRAS A, SELLSTEDT P, et al. System design for 5G converged networks[C]//European Conference on Networks and Communications. 2015.

[4] YOUSAF F Z, GRAMAGLIA M, FRIDERIKOS V, et al. Network slicing with flexible mobility and QoS/QoE support for 5G Networks[C]//IEEE International Conference on Communications Workshops. 2017.

[5] MONEMI M, RASTI M, HOSSAIN E. On low-complexity SINR feasibility checking and joint power and admission control in prioritized multitier cellular networks under co-channel deployment[J]. IEEE Transactions on Wireless Communications, 2016, 15(3): 2421-2434.

[6] JUMBA V, PARSAEEFARD S, DERAKHSHANI M, et al. Energy-efficient robust resource provisioning in virtualized wireless networks[C]//IEEE International Conference on Ubiquitous Wireless Broadband. 2015:1-5.

[7] KAMEL M I, LONG B L, GIRARD A. LTE wireless network virtualization: dynamic slicing via flexible scheduling[C]//Vehicular Technology Conference. 2014:1-5.

[8] SHIMOJO T, SAMA M R, KHAN A, et al. Cost-efficient method for managing network slices in a multi-service 5G core network[C]//Integrated Network and Service Management. 2017: 1121-1126.

[9] PARSAEEFARD S, JUMBA V, DERAKHSHANI M, et al. Joint resource provisioning and admission control in wireless virtualized networks[C]//Wireless Communications and Networking Conference. 2015: 2020-2025.

[10] REJEB S B, NASSER N, TABBANE S. Admission control strategies and QoS evaluation based on mobility in LTE[C]//IEEE Globecom Workshops. 2014: 4883-4888.

[11] ABDELHAMID A, KRISHNAMURTHY P, TIPPER D. Resource allocation for heterogeneous traffic in LTE virtual networks[C]// IEEE International Conference on Mobile Data Management. 2015:173-178.

[12] DIGHRIRI M, ALFOUDI A S D, LEE G M, et al. Data traffic model in machine to machine communications over 5G network slicing[C]//International Conference on Developments in Esystems Engineering. 2017: 239-244.

[13] LI L, CHEN J, CUI H, et al. Resource scheduling virtualization in service-oriented future Internet architecture[J]. The Journal of China Universities of Posts and Telecommunications, 2015, 22(4): 92-100.

[14] GIATSIOS D, CHOUMAS K, FLEGKAS P, et al. SDN implementation of slicing and fast failover in 5G transport networks[C]// European Conference on Networks and Communications. 2017:1-6.

[15] SAMA M R, BEKER S, KIESS W, et al. Service-based slice selection function for 5G[C]//Global Communications Conference. 2017:1-6.

[16] ROST P, MANNWEILER C, MICHALOPOULOS D S, et al. Network slicing to enable scalability and flexibility in 5G mobile networks[J]. IEEE Communications Magazine, 2017, 55(5):72-79.

[17] ANNUNZIATO A. 5G vision: NGMN-5G initiative[C]//IEEE Vehicular Technology Conference. 2015:1-5.

[18] BANCHS A, BREITBACH M, COSTA X, et al. A novel radio multiservice adaptive network architecture for 5G networks[C]// IEEE Vehicular Technology Conference. 2015:1-5.

Dynamic resource scheduling strategy for 5G network slicing based on improved greedy algorithm

CHEN Qiang1,2, LIU Caixia1,2, LI Lingshu1,2

1. National Digital Switching System Engineering and Technological R&D Center, Zhengzhou 450002, China 2. National Engineering Laboratory for Mobile Network Security, Beijing 100876, China

Dealing with the problem of network resource utilization and the user experience, the network slicing as a novel technology is adopted in 5G. A dynamic resource scheduling strategy for 5G network slicing based on improved greedy algorithm was proposed. In the process of slice scheduling and user scheduling, a two layer slice-user model combined with the improved greedy algorithm was proposed, which ensured the slices with maximum service weight and the highest priority users combined together to complete corresponding services. The global resource optimal problem was transformed into a smaller sub problem by means of the optimal combination of each slice and every user, which improved the network resource utilization and the user experience in the meantime. The Matlab simulation results show that compared with existing algorithms, the proposed method could effective improve the system remaining resource utilization, system average QoE level and system throughput.

network slicing, slicing weight value, user priority, dynamic resource scheduling, improved greedy algorithm

TN929.5

A

10.11959/j.issn.2096-109x.2018057

陳強（1993-），男，遼寧本溪人，國家數字交換系統工程技術研究中心碩士生，主要研究方向為新一代移動通信。

劉彩霞（1974-），女，山東煙臺人，國家數字交換系統工程技術研究中心副教授，主要研究方向為移動通信網絡、新型網絡體系結構。

李凌書（1992-），男，湖北恩施人，國家數字交換系統工程技術研究中心博士生，主要研究方向為新型網絡體系結構、網絡空間安全。

2018-05-17；

2018-06-28

陳強，1428917764@qq.com

國家高技術研究發展計劃（“863”計劃）基金資助項目（No.2014AA01A701）；國家自然科學基金資助項目（No.61521003）；科技部支撐計劃基金資助項目（No.2014BAH30B01）

The National High Technology Research and Development Program of China (863 Program) (No.2014AA01A701), The National Natural Science Foundation of China (No.61521003), Ministry of Science and Technology Support Plan (No.2014BAH30B01)