Page 29 - 网络电信2018年5月刊上

解 决 方 案

一种5G网络低时延资源调度算法

1,2
1,2
1,2
1,2
1,2
王琛 , 汤红波 , 游伟 , 王晓雷 , 袁泉
1．国家数字交换系统工程技术研究中心；
2．移动互联网安全技术国家工程实验室

摘要：针对现有资源调度算法难以满足5G低时延业务需求的现状，提出了一种基于联合遗传和禁忌搜索算法的
资源调度（GATS）算法。首先利用整数线性规划建立了虚拟链路的动态带宽分配策略，然后在传统柔性车间调度模
型的基础上引入了数据流量在虚拟链路中的传输时延，建立了相应的5G网络资源调度模型。为了求解这一调度模
型，设计了采用联合遗传和禁忌搜索算法的启发式调度算法，该算法通过在遗传算法寻优过程中引入禁忌搜索，平
衡全局搜索和局部搜索能力，有效解决了遗传算法早熟的问题，而且能够获得更好的调度方案。仿真实验表明，与
GA-BA算法相比，GATS算法将服务完成时间减少了17%，满足了5G低时延业务的需求，进而提高了用户体验和移动运
营商的收益。
关键词：5G；网络功能虚拟化；调度；带宽分配；遗传算法；禁忌搜索

5G移动通信网将是一个全方位服务、多技术融合的网 创新[6]。在网络虚拟化下，资源分配分为3个阶段：服务功能
络，通过信息通信技术的演进和创新，来满足未来用户多 链的构建、服务功能链的映射和虚拟网络功能调度。虚拟网络
样化的业务需求[1]。以软件定义网络（software defined 功能调度做为NFV环境下资源分配的第3个阶段，主要解决在给
network，SDN）和网络功能虚拟化（network function 定相应的计算资源约束和虚拟网络功能执行顺序的基础上，为
virtualization，NFV）为代表的网络新技术将成为5G网络的关 多个服务功能链中的每个虚拟网络功能在虚拟机中选择相应的
键技术[2]。NFV使网络资源分配更加灵活，实现了异构的网络 实例化时间，从而达到最小化完成所有网络服务总时间的目的
架构和服务的聚合[3]。在传统的网络架构中，网络功能通过昂 [7]。
贵的硬件中间件来实现，当移动网络运营商部署新业务时，需 IMT-2020将增强移动宽带、海量机器通信和高可靠低时延
要大量的资本支出和运营支出。而在NFV环境下，网络功能通过 通信做为5G的主要应用场景[8]。为了使移动终端完美支持交
实例化在商用服务器上的虚拟机（virtual machine，VM）中的 互式游戏、3D虚拟现实等在线交互应用，5G提出了毫秒级时延
软件化的虚拟网络功能（virtual network function，VNF）来 和10Gbit/s峰值速率的要求[9]。因此，设计高效的虚拟网络
实现，网络服务则是由多个虚拟网络功能以一定的依赖关系构 功能调度方法是将NFV应用在5G当中的关键问题之一。目前仅有
成服务功能链（service function chaining，SFC）来完成。 少量的文献研究了虚拟网络功能调度问题。文献[10]将虚拟网
移动网络运营商通过NFV技术能够有效的减少资本支出和运营支 络功能调度问题定义为柔性车间调度问题（flexible job shop
出，为用户提供先进和灵活的网络服务[4]。而SDN作为一种新 problem，FJSP），然而未提出多项式时间内的解决方案，而且
型的网络架构，能够控制数据流通过相应的网络功能以执行相 在其调度模型里仅考虑了虚拟网络功能的处理时延。文献[11]
应的策略，实现灵活的网络管理[5]。SDN和NFV的结合为虚拟 提出了NFV环境下具有较低复杂度的多资源数据包调度算法，
网络功能的协调控制和调度提供了有效的架构，促进了网络的 该算法考虑了数据包队列的特性，然而未考虑服务功能链的特

50 网络电信 二零一八年五月