摘要
针对现有资源调度算法难以满足5G低时延业务需求的现状,提出了一种基于联合遗传和禁忌搜索算法的资源调度(GATS)算法。首先利用整数线性规划建立了虚拟链路的动态带宽分配策略,然后在传统柔性车间调度模型的基础上引入了数据流量在虚拟链路中的传输时延,建立了相应的5G网络资源调度模型。为了求解这一调度模型,设计了采用联合遗传和禁忌搜索算法的启发式调度算法,该算法通过在遗传算法寻优过程中引入禁忌搜索,平衡全局搜索和局部搜索能力,有效解决了遗传算法早熟的问题,而且能够获得更好的调度方案。仿真实验表明,与GA-BA算法相比,GATS算法将服务完成时间减少了17%,不仅满足了5G低时延业务的需求,而且提高了用户体验和移动运营商的收益。
A resource scheduling algorithm based on hybrid genetic algorithm and tabu search(named GATS)is proposed to solve the problem that the existing schedule methods are difficult to meet the requirement of the mobile communication with low latency.First,a dynamic bandwidth allocation policy of virtual links is established using an integer linear programming.Then,the transmission delay of data traffic in virtual links is introduced based on a traditional flexible job shop scheduling model,and the corresponding resource scheduling model for 5G is established.Owing to the complexity of the scheduling problem,the resource scheduling algorithm based on hybrid genetic algorithm and tabu search is developed for solving the problem efficiently.The algorithm introduces tabu search in optimization process of the genetic algorithm to balance capabilities of global and local searches,solves the problem of premature convergence of the genetic algorithm,and obtains better scheduling solutions.Simulation results show that the GATS algorithm outperforms the GA-BA algorithm in reducing the scheduling makespan by 17%,and caters to 5G service with stringent delay requirements,thereby increases users’experience and operators’revenues.
作者
王琛
汤红波
游伟
王晓雷
袁泉
WANG Chen;TANG Hongbo;YOU Wei;WANG Xiaolei;YUAN Quan(National Digital Switching System Engineering and Technological Research Center,Zhengzhou 450002,China;National Engineering Laboratory for Mobile Network Security,Beijing 100876 China)
出处
《西安交通大学学报》
EI
CAS
CSCD
北大核心
2018年第4期117-124,共8页
Journal of Xi'an Jiaotong University
基金
国家自然科学基金资助项目(61521003)
国家重点基础研究发展规划资助项目(2016YFB0801605)
关键词
5G网络
网络功能虚拟化
调度
带宽分配
遗传算法
禁忌搜索
5G network
network function virtualization
scheduling
bandwidth allocation
genetic algorithm
tabu search