基于改进式贪婪算法的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)