基于SVM 机器学习的仿真网格资源调度模型

徐晓明

(1.南京大学 商学院，江苏 南京210008;2.江苏省机关事务管理局 住房资金管理中心，江苏 南京210008)

高层体系结构(high level architecture，HLA)专注于仿真应用层的交互和重用，但缺乏对底层模型和资源的规范。管理资源机制的缺失使仿真应用在资源共享和协同方面存在局限性，特别是在资源出现故障或负载失衡的情况下会使整个仿真系统瘫痪。网格的资源动态共享、协同工作和开放的标准为仿真资源的使用和管理带来了新思维(如应用运行、容错、资源管理、资源发现和使用、仿真监控等)。欧洲的CrossGrid 项目首先将网格技术与仿真结合［1］，提出利用网格服务构建基于HLA 的仿真应用。美国的NEES 将测试设施、数据、计算资源和用户连接起来，实现仿真仪器和设备的共享。文献［2］提出基于网格的分布式仿真框架。文献［3］基于HLA 和OGSA 提出了新的仿真网格框架。国内航天二院、清华大学和北京航空航天大学进行了仿真网格关键技术研究，如文献［4］提出了仿真网格概念和体系结构，并基于航天重大型号研制中的迫切需求进行了基于网格的仿真应用开发和研究，部署和构造了多学科虚拟样机协同仿真和大规模体系攻防对抗协同仿真应用。国防科技大学在基于网格的仿真框架、基于网格的仿真任务管理和调度、应用开发等方面也进行了深入的研究［5－6］。

从国内外研究可知，仿真网格作为专用网格的相关关键技术，包括仿真资源管理和调度研究，已取得一些成果［7］，但从机器学习的角度对仿真网格资源进行调度的研究尚不多见。笔者用扩展的WSDL 描述仿真网格资源特有的属性，建立集中－分布式仿真资源管理模型，在分析分布交互仿真任务特定需求的基础上，提出了一种基于机器学习的仿真资源调度模型，并对其中的关键部分进行了详细的阐述。

1 网格资源调度相关工作

1.1 网格资源管理模型

网格资源管理模型是网格资源调度的基础。目前网格资源管理模型最具代表性的有层次模型和市场/经济模型［8］。层次模型是将资源管理系统分成若干功能层，较高层次的服务利用较低层次服务提供的功能。层次模型又分为集中式结构、分布式结构和混合式结构。集中式结构中资源由全局管理器统一管理;分布式结构由对等的管理器独立管理，管理器之间可进行相互作用;混合式结构综合了上述两者，在管理域内由一个管理器管理，而在总体上则由全局管理器管理各个管理器。市场/经济模型是根据市场上的经济原则协调资源的管理、发现和交易，该模型是在层次模型的基础上发展起来的，其目标是建立一个理想的资源提供和使用的机制，从而使资源的使用率最大化，为构建可持续发展的网格计算环境提供了一种有意义的思路。

在上述两种管理模型的基础上，国内外学者又提出了一些具有参考意义的资源管理模型。如由客户和抽象所有者组成的抽象所有者模型，文献［9］中提出了一种兼顾内部结构和对外接口的通用网格资源管理系统抽象模型。在行业网格的研究中也提出了一些具有领域特征的网格资源管理模型，如文献［10］针对制造网格中资源的异构性、分布性以及用户提交加工产品的复杂性、多样性提出了制造网格资源管理模型。

1.2 网格资源调度模型和算法

资源调度是根据任务和资源的特性采用不同的算法将任务映射到相应的资源上的执行过程。传统的资源调度方法大多使用最优化理论集中求解资源调度问题，而市场/经济模型应用经济学原理进行网格资源调度，该模型主要由3 个部分组成:用户资源请求代理利用中间件服务连接用户和网格资源，完成作业控制代理、作业调度、网格信息浏览、贸易管理和分配代理;市场中间件完成资源的分配和管理、认证和安全服务、网格信息服务与交易模板等功能;域资源管理完成包括资源管理和贸易服务。在此基础上国内外学者提出了基于代理的调度、效用驱动的调度和基于QoS 的调度等模型［11］。

目前的网格调度算法主要是基于图论、启发式、整数规划等方法的调度，如先来先服务(first come first serve，FCFS)、直接用户分配(user－directed assignment，UDA)、机会负载均衡(opportunistic load balancing，OLB)、Min－min 、Max－min、贪心(Greedy)和快速贪心(Fast Greedy)算法等类多项式算法［12］。另外MARTINO［13］、SONG［14］和林剑柠等［15］采用遗传算法来求解网格计算任务调度问题;XU 等［16］提出了基于蚁群算法的网格任务调度问题求解;季一木等提出的基于粒子群的网格任务调度算法［17］都取得了较好的效果。WANG 等提出了一种通用的网格任务调度算法基本上综合了以上大部分算法［18］。

以上调度模型和方法均根据不同启发信息或约束条件在可用资源范围内查找最佳资源，但这些人为设计的启发信息或约束条件具有一些局限性，资源查找可能陷入局部最优，导致算法失效或性能不稳;这些算法在处理大样本时，没有考虑资源的局部特性和应用领域特性的区分度，调度性能受到影响，不适合仿真任务的要求;这些方法着重考虑了网格资源的有效分配，但没有考虑分布交互仿真任务之间的协同和时间约束下的强交互性;它们都不具备自学习能力，每次执行调度都要处理所有资源，并不能充分利用以前的调度经验进行智能化调度，而一些智能的/具有学习能力的调度模型和算法主要着眼于Agent 之间的学习，并不具有自学习能力。当前具有自学习能力的资源调度模型和算法尚不多见，查新结论和权威搜索引擎还没有发现这方面的文献。

2 仿真网格资源管理系统

2.1 仿真网格资源及其描述

由于仿真资源的复杂性和多样性，仿真资源包括从仿真中间件、仿真模型、仿真工具、仿真数据、仿真应用、仿真运行控制、仿真评估、仿真仪器到仿真人力资源在内的各种软件资源和硬件资源。不同类型的仿真资源之间存在很大的差异，具有不同的属性信息，包括静态信息和动态信息。静态信息表示资源的功能、结构特征及其他固有信息，而动态信息是实时变化的，如资源的工作状态、可靠性、交互性等。

为了支持采用支持向量机进行资源的分类，使调度算法具有学习能力，笔者为仿真网格资源描述定义了统一的可扩展的Schema，用以描述仿真网格资源的特征。仿真资源的静态信息包括资源标识、资源类型、功能描述、参数列表、使用约束、应用领域、版权信息、操作系统类型和版本、CPU 类型和数量、CPU 频率、内存容量、磁盘容量、网络带宽、需要的节点体系结构、最小计算性能、最低网络带宽、需要的仿真联邦成员类型和数量、期望的开始时间/期望的结束时间、仿真任务的优先级、时间限制、需要的物理内存等;仿真资源的动态信息包括网络实时带宽、负载、资源状态标记、服务质量和当前等待任务信息等。

分布交互仿真只有在所有节点的计算任务和通信任务都完成后，一个仿真步长的任务才结束。因此必须同时占用所有资源，且资源之间必须没有冲突。同时占有大量资源在松散管理的网格环境中会面临巨大挑战，一个有效的方法是进行资源预留，因此在仿真资源的描述中要求明确描述资源状态，资源状态有占用、可用、预留和实效4种，其迁移关系如图1 所示。

该Schema 可以根据不同的需求进行裁剪，同时根据不同类别的资源描述需求，还可以增加扩展信息以描述这些资源特有的属性。扩展信息由各类资源提供者自行定义，自由分类时也可作为分类依据的组成部分。

图1 仿真网格资源状态变迁图

2.2 网格资源管理模型

当前的网格资源管理系统各有优缺点:集中式的资源管理有利于维护最新的资源信息，实现全局最优的资源调度决策，但其可靠性低，集中管理节点会成为瓶颈;分布式资源管理的可扩展性和容错性较好，但资源管理节点间的协同需求不能很好地适应分布交互仿真的协同和交互要求;而集中－分布式资源管理具有以上两者的优点。作为专业网格的仿真网格，笔者采用了集中－分布式的资源管理模型，以便在支持本地管理策略的同时又便于进行全局调度，即域内采用集中式组织，域间采用分布式组织，这样可使管理域关系对等，即使某些管理域出现故障也不妨碍资源调度的进行。这种方式更适合分布交互仿真的要求，分布的资源管理域使用户总能在通信能力范围内找到一个或多个有资源调度能力的资源管理节点。

3 仿真网格资源调度模型

3.1 分布交互仿真调度分析

分布交互仿真的运行模式和通信模式等内在特点决定了仿真网格的资源调度属于一种特殊的形式，与其他网格调度系统相比具有以下特性:

(1)资源协同分配。基于HLA 的仿真系统是分布式的，需要同时占用所有资源才能运行，只有所有节点的计算任务和通信任务完成后时序才能推进，其中任何一个资源性能下降或故障都会使整个系统运行受阻，因此在资源调度时必须采用良好的协同分配策略，而基于资源状态信息的资源预留是其中一个重要组成部分;

(2)调度目标是全局优化。一个循环的仿真任务包括数据接收、任务计算和数据分发3 个过程，这3 个过程是在仿真时间步长的严格限制下进行的。其中任何一个节点的延迟都会影响整个系统的延迟，因此整个仿真系统的计算和通信时间取决于时间开销最长的节点。其调度目标不是单个或部分成员时间最优，而是整个联邦时间最优，且联邦时间只要小于仿真推进步长的时间即可。因此调度的目的是尽量使所有节点的数据接收时间、计算时间和数据分发时间之和小于仿真时间推进步长或在非固定时间步长的情况下使整个联邦的时间步长最小;

(3)仿真成员间的通信需求。在仿真资源调度中，不仅要考虑计算任务的需求，还要满足通信需求。HLA 仿真与传统的分布式计算和网格计算中的通信机制有本质的区别，对网络通信具有较高的要求。在一般的分布式计算中，通信是根据特定应用设计的，只适用于一个或一类应用;而分布交互仿真符合HLA 的中间件HLA，具有自己的通信和交互机制。因此调度时需要特别重视RTI 自由及其通信性能;

(4)容错和任务迁移。如上所述，仿真中单点故障会影响系统性能，甚至导致整个系统运行受阻，因此当单点性能下降或故障时，必须进行快速的迁移;

(5)仿真资源种类和数量繁多使调度模型和算法的性能面临巨大的挑战。

3.2 基于机器学习的仿真网格资源调度模型

根据以上介绍的仿真资源描述及管理模型，基于机器学习算法提出了仿真网格资源调度模型，如图2 所示。对应于集中－分布式的资源管理模型，调度模型也是集中分布式的。其中每个资源管理域的管理节点具有调度能力，称为调度代理;整个仿真网格中有一个全局的调度代理。仿真用户向全局调度代理发出资源请求，由代理完成对请求资源的识别，先在本地资源中寻找匹配的资源，若无匹配资源再向其他管理域中的代理发出请求。

图2 仿真网格调度模型图

在该调度模型中资源的查找和匹配过程是基于网格资源自动分类的，即在同类资源中进行最佳资源的搜索。笔者采用支持向量机(SVM)和增量SVM 技术进行资源自动分类:资源管理节点用域内资源信息作为样本训练SVM 分类决策函数，为每个资源标记类别;由于仿真网格的服务样本数量大，且有较强动态性，笔者对新增资源采用增量技术，考虑其对旧决策函数的影响，更新决策函数和资源标记，这样进行的快速学习既能节省存储空间又能节省计算时间。对用户请求的资源确定类标记后即可在域内同类资源中匹配，避免了在域内查找所有资源，提高了调度的效率。

3.3 具有学习能力的仿真网格资源调度过程

仿真网格资源调度模型的执行过程可用图3表示。在该模型中所有的可用资源都虚拟化成仿真网格资源(simulation grid resource，SGR)，首先由仿真网格中功能较强大的代理节点解析SGR进行分类训练，当有新的网格资源注册到网格中时执行增量训练。遵循相同分类标准的训练结果可以通过协同分发进行公布，从而在整个仿真网格系统中共享。当用户有资源调度需求时，将请求发送给调度代理，代理进行请求资源的识别和可用资源的识别，利用前期对网格资源分类的结果进行预计算，找到可用资源。调度结果返回请求者后将任务部署到候选资源上。

图3 仿真网格资源的调度过程

3.4 基于SVM 的仿真网格资源分类

基于SVM 的SGR 分类是该调度模型的基础，其实质是以SGR 为训练样本，训练出SVM 分类决策函数，训练过程如下:

(1)SGR 信息收集。符合Schema 的SGR 注册到信息服务中后，调度模块从信息服务收集这些资源的信息;

(2)信息格式转换。采用统一Schema 的SGR 描述文件(WSDL 文件)的格式不能用作SVM 样本，必须首先将WSDL 文件映射为向量。在统一Schema 约束下，将WSDL 转换成多维向量，就可以方便地实现描述文件中各元素到向量各维属性的映射;

(3)特征提取。直接从WSDL 映射得到的向量样本包含一些与训练SVM 无关的信息，为了提高训练效率，必须提取与训练目标相关的特征;

(4)SVM 训练。SVM 训练由资源管理节点请求，训练得到的分类决策函数用于资源的分类和查找;

(5)增量SVM 训练。由于仿真网格环境的动态性，一次分类是不够的，但如果每次都用SVM 训练中的方法进行重新分类，计算和存储代价较高，因此采用增量学习技术完成新资源加入后分类器的更新。这就需要对新增样本单独做一次训练得到一个SVM，而整个过程对全部样本只做一次违背KKT 条件的验证，判断支持向量集是否会发生变化。由于多类问题可以转化为多个二类问题，这里使用以二类问题描述SGR 增量训练算法的思想。

设原样本集A，由其训练得到的初始SVM 分类器为Γ0，Γ0的支持向量集为Asυ，B 为新增样本，增量学习算法为:

(1)检验B 中是否有样本违背Γa的KKT 条件，若没有则算法停止，分类器和支持向量集保持不变;否则根据检验结果，将B 分为BV和BS。BV为违背Γa的KKT 条件的样本集合，它们将导致Asυ的改变;BS为满足Γa的KKT 条件的样本集合，舍弃;

(2)用B 训练一个SVM 分类Γb，Bsυ表示Γb的支持向量集;

(3)检验A 中是否有样本违背Γb的KKT 条件，若没有则停止，Γb为增量学习结果，否则A 被分为AV和AS。AV为违背Γb的KKT 条件的样本集合，将导致Bsυ的改变;AS为满足Γb的KKT 条件的样本集合，舍弃;

(4)令U=Asυ∪Bsυ∪BV∪AV，用U 训练得到新的SVM 分类器为增量学习结果。

基于这个训练结果就可以对网格内的资源进行分类标记并实现高效的调度。

4 结论

笔者针对仿真网格资源的特质，定义了统一的Schema 描述SGR，采用扩展的WSDL 描述仿真网格资源特有的属性，以利于应用机器学习算法进行资源调度;建立了符合仿真任务调度特殊需求的集中－分布式仿真资源管理模型。在分析分布交互仿真任务特有需求的基础上，提出了一种基于机器学习的仿真资源调度模型。该模型基于资源描述提取资源的特征量，采用支持向量机SVM 和增量SVM 技术对其进行分类，调度代理在分类训练结果的基础上进行调度。实验表明，该调度模型可以更好地获得各分布交互仿真成员整体最优的调度结果。

［1］ BUBAK M，MALAWSKI M，ZAJAC K.Towards the cross grid architecture［R］. Berlin Herdelberg:Arpinger－Verlag，LNCS 2474，2002.

［2］ XIE Y，TEO Y M，CAI W T，et al.Service provisioning for HLA－based distributed simulation on the grid［C］//Proceedings of the Workshop on Principles of Advanced and Distributed Simulation(PADS’05).［S.l.］:［s.n］，2005:1054－1062.

［3］ KATARZYNA R，MARIAN B，MACIEJ M，et al. A framework for HAL－based interactice simulations on the grid［J］. The Society for Modeling and Simulation International，2005，81(1):67－76.

［4］ LI B，CHAI X D，ZHU W H，et al.Supporting environment technology of simulation based acquisition［J］.Journal of System Simulation，2004，16(2):181－185.

［5］ 魏洪涛.基于网格计算的仿真任务管理与调度方法研究［D］.长沙:国防科学技术大学图书馆，2005.

［6］ 刘云生.大规模分布式仿真系统容错关键技术研究［D］.长沙:国防科学技术大学图书馆，2006.

［7］ 张传富.仿真网格资源管理系统关键技术研究［D］.长沙:国防科学技术大学图书馆，2006.

［8］ BUYYA R. Economic based distributed resource management and scheduling for grid computing［DB/OL］.［2013－02－19］. http://www. buyya. com /thesis/thesis.pdf.

［9］ JIA M F，DONG W Q，GUI X L，et al.Models for grid resource management systems［J］. 微电子学与计算机，2003(3):36－40.

［10］LIU L L，YU T，CAO H W，et al.Research on resource management and scheduling system in manufacturing grid［J］.机械科学与技术，2004(10):1230－1233.

［11］LI B F，CHEN Q，GAO C S.The research on resource allocation in computational grid［J］.Computer Applications and Software，2008(1):109－111.

［12］王树鹏，云晓春，余翔湛. 基于生存性和Makespan的多目标任务调度算法研究［J］. 通信学报，2006，27(2):42－49.

［13］ MARTINO D V.Sub optimal scheduling in a grid using genetic algorithms［C］//Parallel and Distributed Processing Symposium.［S.l.］:［s.n.］，2003:22－26.

［14］ SONG S，HWANG K，KWOK Y K. Risk－resilient heuristics and genetic algorithms for security－assured grid job scheduling［C］// Computers，IEEE Trcmsactions.［S.l.］:［s.n.］，2006:703－719.

［15］林剑柠，吴慧中.基于遗传算法的网格资源调度算法［J］.计算机研究与发展，2004，14(12):2195－2199.

［16］XU Z H，HOU X D，SUN J Z.Ant algorithm－based task scheduling in grid computing［C］//Electrical and Computer Engineering. ［S.l.］:［s.n.］，2003:1107－1110.

［17］季一木，王汝传.基于粒子群的网格任务调度算法研究［J］.通信学报，2007，28(10):60－66.

［18］WANG T，ZHOU X S，LIU Q R，et al. OD:a general resource scheduling algorithm for computational grid［C］//Computer and Computational Sciences.［S.l.］:［s.n.］，2006:644－647.