基于蚁群算法的轨道交通集群调度算法研究
|
摘要
负载均衡调度是轨道交通集群系统的一大核心功能,海量任务的实时、高效、均衡调度对轨道交通系统的可靠运行起着至关重要的作用。由于轨道交通集群系统的历史原因,各个子系统的实时负载情况无法获取。文中在分析现有的负载均衡调度算法的基础上,提出了一种基于蚁群算法的面向轨道交通异构集群的负载均衡动态调度算法,以信息素浓度作为各个节点负载程度的依据,从而实现动态型的负载均衡调度。仿真结果表明,在轨道交通领域,基于蚁群算法的负载均衡调度算法比遗传算法、Min-Min算法、Max-Min算法具有更高的任务吞吐量。
Load balancing scheduling is a core function of the rail transit cluster dispatching system( RTCDS). Massively real-time,efficient and balanced scheduling of mass tasks plays a crucial role in the reliable operation of the rail transit system. Due to the historical reasons of the RTCDS,the real-time load of each subsystem cannot be obtained. On the basis of comparing with the existing load balancing scheduling algorithms,this paper proposes a load balancing scheduling algorithm of RTCDS based on the heuristic ant colony algorithm. The algorithm uses the pheromone concentration as the basis of the load degree of each node,so as to achieve dynamic load balancing scheduling. Simulation results show that in the field of rail transit,the load balancing scheduling algorithm based on ant colony algorithm has higher task throughput than the genetic algorithm,Min-Min algorithm and Max-Min algorithm.
Load balancing scheduling is a core function of the rail transit cluster dispatching system( RTCDS). Massively real-time,efficient and balanced scheduling of mass tasks plays a crucial role in the reliable operation of the rail transit system. Due to the historical reasons of the RTCDS,the real-time load of each subsystem cannot be obtained. On the basis of comparing with the existing load balancing scheduling algorithms,this paper proposes a load balancing scheduling algorithm of RTCDS based on the heuristic ant colony algorithm. The algorithm uses the pheromone concentration as the basis of the load degree of each node,so as to achieve dynamic load balancing scheduling. Simulation results show that in the field of rail transit,the load balancing scheduling algorithm based on ant colony algorithm has higher task throughput than the genetic algorithm,Min-Min algorithm and Max-Min algorithm.
引文
[1]陈东伐.城市轨道交通通信集中告警系统的方案设计[J].城市轨道交通研究,2011,14(8):51-53.CHEN Dongfa.Design of centralized alarm system on rail transit communication[J].Urban Mass Transit,2011,14(8):51-53.(in Chinese)
[2]师雪霖,徐恪.云虚拟机资源分配的效用最大化模型[J].计算机学报,2013,36(2):252-262.SHI Xuelin,XU Ke.Utility maximization model of virtual machine scheduling in cloud environment[J].Chinese Journal of Computers,2013,36(2):252-262.(in Chinese)
[3]CHANG Y I,CHEN H L,LI S N,et al.A dynamic Hashing approach to supporting load balance in P2P systems[C]∥International Conference on Distributed Computing Systems Workshops.2008:429-434.
[4]PATEL G,MEHTA R,BHOI U.Enhanced load balanced Min-Min algorithm for static meta task scheduling in cloud computing[J].Procedia Computer Science,2015,57:545-553.
[5]MAO Y,CHEN X,LI X.Max-Min task scheduling algorithm for load balance in cloud computing[C]∥Proceedings of International Conference on Computer Science and Information Technology.2014:457-465.
[6]MALLIKARJUNA B,KRISHNA P V.OLB:a nature inspired approach for load balancing in cloud computing[J].Cybernetics&Information Technologies,2015,15(4):138-148.
[7]SHEIKH S,NAGARAJU A.A comparative study of task scheduling and load balancing techniques with MCT using ETC on computational grids[J].Indian Journal of Science&Technology,2017,10(32):1-14.
[8]MAHESWARAN M,ALI S,SIEGEL H J,et al.Dynamic mapping of a class of independent tasks onto heterogeneous computing systems[J].Journal of Parallel and Distributed Computing,1999,59(2):107-131.
[9]DUTTA D,JOSHI R C.A genetic-algorithm approach to cost-based multi-QoS job scheduling in cloud computing environment[C]∥International Conference&Workshop on Emerging Trends in Technology.2011:422-427.
[10]KESHANCHI B,SOURI A,NAVIMIPOUR N J.An improved genetic algorithm for task scheduling in the cloud environments using the priority queues:formal verification,simulation,and statistical testing[J].Journal of Systems and Software,2017,124:1-21.
[11]GAO Y,GUAN H,QI Z,et al.A multi-objective ant colony system algorithm for virtual machine placement in cloud computing[J].Journal of Computer&System Sciences,2013,79(8):1230-1242.
[12]LI K,XU G,ZHAO G,et al.Cloud task scheduling based on load balancing ant colony optimization[C]∥Chinagrid Conference(China Grid).2011:3-9.
[13]MAVROVOUNIOTIS M,MULLER F M,YANG S.Ant colony optimization with local search for dynamic traveling salesman problems[J].IEEE Transactions on Cybernetics,2016,47(7):1743-1756.
[14]DORIGO M,MANIEZZO V,COLORNI A.Ant system:optimization by a colony of cooperating agents[J].IEEETransactions on Systems,Man,and Cybernetics,Part B:Cybernetics,1996,26(1):29-41.
[2]师雪霖,徐恪.云虚拟机资源分配的效用最大化模型[J].计算机学报,2013,36(2):252-262.SHI Xuelin,XU Ke.Utility maximization model of virtual machine scheduling in cloud environment[J].Chinese Journal of Computers,2013,36(2):252-262.(in Chinese)
[3]CHANG Y I,CHEN H L,LI S N,et al.A dynamic Hashing approach to supporting load balance in P2P systems[C]∥International Conference on Distributed Computing Systems Workshops.2008:429-434.
[4]PATEL G,MEHTA R,BHOI U.Enhanced load balanced Min-Min algorithm for static meta task scheduling in cloud computing[J].Procedia Computer Science,2015,57:545-553.
[5]MAO Y,CHEN X,LI X.Max-Min task scheduling algorithm for load balance in cloud computing[C]∥Proceedings of International Conference on Computer Science and Information Technology.2014:457-465.
[6]MALLIKARJUNA B,KRISHNA P V.OLB:a nature inspired approach for load balancing in cloud computing[J].Cybernetics&Information Technologies,2015,15(4):138-148.
[7]SHEIKH S,NAGARAJU A.A comparative study of task scheduling and load balancing techniques with MCT using ETC on computational grids[J].Indian Journal of Science&Technology,2017,10(32):1-14.
[8]MAHESWARAN M,ALI S,SIEGEL H J,et al.Dynamic mapping of a class of independent tasks onto heterogeneous computing systems[J].Journal of Parallel and Distributed Computing,1999,59(2):107-131.
[9]DUTTA D,JOSHI R C.A genetic-algorithm approach to cost-based multi-QoS job scheduling in cloud computing environment[C]∥International Conference&Workshop on Emerging Trends in Technology.2011:422-427.
[10]KESHANCHI B,SOURI A,NAVIMIPOUR N J.An improved genetic algorithm for task scheduling in the cloud environments using the priority queues:formal verification,simulation,and statistical testing[J].Journal of Systems and Software,2017,124:1-21.
[11]GAO Y,GUAN H,QI Z,et al.A multi-objective ant colony system algorithm for virtual machine placement in cloud computing[J].Journal of Computer&System Sciences,2013,79(8):1230-1242.
[12]LI K,XU G,ZHAO G,et al.Cloud task scheduling based on load balancing ant colony optimization[C]∥Chinagrid Conference(China Grid).2011:3-9.
[13]MAVROVOUNIOTIS M,MULLER F M,YANG S.Ant colony optimization with local search for dynamic traveling salesman problems[J].IEEE Transactions on Cybernetics,2016,47(7):1743-1756.
[14]DORIGO M,MANIEZZO V,COLORNI A.Ant system:optimization by a colony of cooperating agents[J].IEEETransactions on Systems,Man,and Cybernetics,Part B:Cybernetics,1996,26(1):29-41.