一种环境感知的仿真服务调度模型

张学军，闫光辉，胡晓辉



一种环境感知的仿真服务调度模型

张学军，闫光辉，胡晓辉

(兰州交通大学电子与信息工程学院，兰州 730070)

针对传统分布式仿真框架HLA/RTI中动态调度负载平衡较差、执行可靠性较低的问题，提出一种基于环境感知的仿真服务调度模型C3SM。C3SM模型包含总体结构、调度策略和服务部署。总体结构规定各个模块的功能与交互接口，调度策略采用改进的蚁群算法进行仿真服务的动态调度，服务部署采用重叠覆盖部署策略以保证较好的服务可用性和较低的资源消耗。仿真实验结果表明，与传统分布式仿真框架HLA/RTI相比，C3SM模型通过实时获取执行环境的上下文信息，能够获得较优的负载平衡度，且重叠覆盖的仿真服务部署策略使得仿真运行系统的可靠性明显提高。

环境感知；高层体系结构；分布式仿真；Web 服务；蚁群算法；仿真服务调度

1 概述

随着计算机与信息技术的飞速发展，计算机仿真技术在智能交通、航空航天、生物、通信等领域得到了广泛的应用和研究。由于计算机仿真所涉及的问题越来越复杂，仅靠单个仿真系统已无法满足实际仿真需求。目前多种智能手持设备快速发展，具备了较强的计算能和通信能力，可以将多种手持设备与传统的服务器或PC一起构成一个分布式、异构的智能仿真建模和运行环境。

高层体系结构(High Level Architecture, HLA)是分布式仿真领域的一个软件架构标准，它解决了仿真应用之间可交互性和模型在不同领域重用性的关键问题[1]。但是，HLA在应用中存在许多不足：(1)由于存在多个运行时基础设施(Runtime Infrastructure, RTI)厂商，不同厂商的RTI基于特定的计算机平台与编程语言，互操作性和跨平台能力有限；(2)RTI在运行时会受到防火墙的限制，使仿真任务无法正常运行；(3)RTI对系统的容错性支持不足，单一联邦的失效会导致整个仿真任务的失败。

Web服务(Web service)是一种面向服务的分布式计算模式，具有良好的平台异构性和语言独立性特点，可以与其他分布式计算技术相结合，且其请求和响应不受防火墙限制。因此，可以考虑将Web 服务和HLA进行结合，克服HLA的不足，进而构建一个具备一定冗余度的可靠分布式仿真系统。

目前的仿真研究主要集中在体系结构方面，对仿真任务的动态调度、执行的可靠性研究较少。本文根据Web服务与传统RTI仿真的特点，提出一种基于环境感知的仿真服务调度模型(Context-aware Simulation Service Scheduling Model, C3SM)。C3SM模型首先在仿真任务的执行节点上部署监控代理实时获取各节点和仿真服务的当前状态，然后让调度器按照指定的调度策略将用户的仿真请求分发到各个执行节点上，并对出现故障的执行节点及时使用副本节点代替。整个过程对仿真客户端是透明的，这样可有效提高仿真任务的执行效率与可靠性，降低仿真客户端的编程复杂度。

2 相关工作

文献[2]基于网格服务提出了层次化动态负载平衡系统，该系统可以在HLA仿真执行过程中重新分配各种资源，有效提高了仿真任务执行性能。文献[3]把运行全过程分为运行前后的调度准备、运行过程的基于MOM的管理和对系统的负载监控及调度，实现了对仿真运行全过程的管理。文献[4]从节约网络带宽、优化资源配置和负载平衡、支持离线服务的应用需求入手，提出了基于移动Agent和上下文感知技术的仿真服务迁移机制，实现了对仿真服务迁移全生命周期的管理。

文献[5]分析了HLA在协同仿真应用方面的限制，将Web service与基于HLA的仿真系统集成，使用Web service封装异构资源，并通过原型系统验证了该方法的可行性。文献[6]将Web service引入到HLA仿真应用中，提出了基于Web service的HLA仿真框架。

文献[7]针对仿真执行可靠性问题，在HLA的框架下，实现了一个动态复制管理层。该层以透明的方式支持对软件副本的执行，提高了仿真系统的响应速度。文献[8]则从HLA仿真的可信性角度出发，将确认、验证和授权分为 3个层次论述每个层次的作用。

文献[9]提出了多代理的数据收集系统，采用层次化的数据管理机制，使得对仿真运行的分析与快速的数据收集相互独立，提高了已有数据收集机制的性能，为增强仿真模型的可重用性和互操作性提供了支持。

3 仿真服务动态调度模型

已有的HLA仿真系统在执行过程中很少考虑系统的可靠性与负载平衡，各联邦成员采用静态绑定的发布/订购模式进行交互，这在较大规模的仿真应用执行过程中可能会出现难以预料的后果，某一联邦成员的故障会导致整个系统的执行失败。联邦成员的唯一性导致仿真运行时各联邦成员的有效性不能得到保证。

为此，本文提出基于环境感知的仿真服务动态调度模型C3SM，将仿真中涉及到的联邦都封装为Web service，通过在仿真客户端调用所需的仿真服务组件便可以实现仿真任务的高效、可靠执行。

3.1 C3SM的总体结构

C3SM的总体结构如图1所示。

图1 仿真服务动态调度模型总体结构

为准确描述模型，引入如下定义：

定义1(仿真服务) 将仿真所需的各种属性和功能通过Web service封装，并能通过标准互联网协议访问的组件。

定义2(服务节点) 部署了所需仿真服务的节点(物理机、虚拟机)。

定义3(监控代理) 部署于服务节点上，用于监测服务节点状态(是否工作、性能指标、负载等)的软件传感器。

定义4(服务状态资源库) 用于记录各服务节点状态和各仿真服务访问接口信息的数据库。

定义5(仿真客户端) 通过调用各仿真服务，执行仿真任务的运行实体。

C3SM模型的总体结构由仿真客户端、仿真服务动态调度器、服务状态资源库、仿真调度策略库和服务节点组成。每个服务节点上均部署有监控代理，可以监测服务节点的性能指标、负载状态和仿真服务可用性等数据，同时定期会对部署于该节点的仿真服务进行可用性测试，按设定的周期将服务节点及仿真服务的当前状态写入服务状态资源库，供仿真服务动态调度器在调度仿真服务时使用。仿真客户端是执行仿真任务的运行实体，在编码阶段可以采用多种编程语言，如JAVA、C++、C#等。用户不需要预先指定仿真服务的访问点，而在运行阶段由调度器动态选择最优的服务节点与仿真服务，保证仿真任务执行的效率与可靠性。仿真客户端可运行于多种平台下，如Windows PC、Linux服务器、Android移动设备等，这样可以在仿真任务中加入多种参与者，提高仿真执行的多样性。

3.2 C3SM模型的调度方法

在分布式仿真框架HLA/RTI中加入Web service调用模式，可使各仿真联邦之间的数据交互穿透防火墙的限制，扩大仿真任务的规模。但这种模式没有考虑到Web service的故障问题[5]，若仿真任务调用的Web service不能正常提供服务，则会使仿真任务执行失败，在规模较大的情况下，发生故障的概率会更高。针对这一问题，基于环境感知的仿真服务调度模型C3SM在各服务节点上部署有相同仿真服务的多个副本以便在其他服务节点或者仿真服务出现故障时仍可继续提供有效的仿真服务。仿真客户端不是和仿真服务直接通信，而是通过仿真代理进行间接通信，具体的通信流程如图2所示。

图2 C3SM模型的动态调度流程

用户在仿真客户端进行编码时，不需要直接指定仿真服务的绝对地址，但需要采用约定的服务描述方法，而目前尚无统一的描述标准。在本文实现的原型系统中，用户首先向仿真服务动态调度器发送一个描述仿真服务的请求，调度器接收到仿真服务请求后，查询仿真服务状态资源库和调度策略库，根据调度策略与各仿真服务的当前状态，选择最优的仿真服务并获取该服务的绝对地址，然后发送简单对象访问协议(Simple Object Access Protocol, SOAP)服务请求。获得SOAP响应后，将运行结果返回给仿真客户端。若仿真服务在执行过程中失效，则调度器重新选择可用的仿真服务，重复上述过程。

在调度过程中，调度策略库的作用非常重要。调度器需要在调度策略的指导下选择满足仿真请求的最优仿真服务。为此，本文设计了基于批模式和改进蚁群算法的仿真服务动态调度策略，作为仿真调度策略库的默认策略。在C3SM模型中，仿真任务由多个仿真客户端协同执行，各仿真客户端之间的时间推进由统一的同步点推进模块来管理。这样在仿真服务调度过程中就不需要考虑仿真服务之间的依赖关系，而采用独立仿真服务调度方法。经典的独立网格任务调度方法有Min-Min算法[10]和Max-Min算 法[11]。但是，Min-Min算法优先考虑短任务，会导致长任务出现饥饿状态。Max-Min算法则与Min-Min相反，导致短任务出现饥饿。在规模较大的仿真服务调度中，负载失衡和任务饥饿是不允许的。本文根据大规模仿真服务调度的特点，将接收到的多个仿真服务请求进行缓冲批量处理，采用固定时间间隔策略或固定仿真服务请求数策略，当达到调度触发点后，使用改进后的蚁群算法进行仿真服务的动态调度。

蚁群算法[12]经过多年的发展，已成功地应用在组合优化中。仿真服务请求的批模式动态调度是一个组合优化问题，因此可以使用改进的蚁群算法进行求解。

在蚁群算法调度开始时，需要设置各仿真服务的初始信息素，每只蚂蚁代表调度集合中的一个仿真服务请求，携带该请求所需的计算负载、通信负载以及优先级，以系统达到负载平衡为优化目标。通过各仿真服务信息素的动态变化，使得蚂蚁不断选择最佳的仿真服务，最终达到负载均衡。算法描述如下：

(1)初始化各仿真节点的信息素，为每个仿真服务请求分配一个蚂蚁，负责将该请求运送到合适的仿真服务上，首先将蚂蚁随机分配到仿真节点上。

(2)每只蚂蚁根据如下的概率选择仿真节点：

(3)蚂蚁在选择仿真节点后，会在该仿真节点上留下一定量的信息素，表示如下：

假设蚂蚁数量为，当所有蚂蚁都选择完仿真节点后，仿真节点的信息素增量为：

标准差为：

转步骤(2)，进行下一次迭代计算。

表1 参数hi更新规则

3.3 C3SM模型的可靠性

在基于环境感知的仿真服务调度模型C3SM中，驻留在各仿真节点上的监控代理定期获取仿真节点的状态信息，并通过规定的接口对仿真服务进行可用性测试，将仿真节点及各仿真服务的状态录入仿真服务资源库，以便调度器能够及时获得系统的状态信息。C3SM模型的可靠性与仿真服务的部署策略有关，在本文中，定义了3种仿真服务部署策略，具体如表2所示。

表2 仿真服务部署策略

图3 仿真服务重叠覆盖部署策略

若采用划分覆盖部署策略，则各仿真服务组只有一个驻留节点，个仿真节点上驻留有个互不相交的仿真服务组，则此时仿真服务组的可用性为：

若采用全覆盖部署策略，则所有的仿真服务构成一个仿真服务组，共有-1个备用副本，此时仿真服务组的可用性为：

由式(8)~式(10)可见，采用全覆盖具有最佳的服务可用性，但对仿真节点的资源消耗较大，且没有充分利用各仿真节点的特点；划分覆盖使得仿真服务组没有冗余备份，对服务节点的资源消耗最小，但如果某一仿真节点出现故障，则驻留在该节点上的仿真服务组就不能继续提供服务，仿真客户端的相关服务请求也不能获得响应，因此该部署策略具有较差的服务可用性；重叠覆盖则吸取了上述2种部署策略的优势，具有较好的服务可用性以及较低的资源消耗，当设定=0.1时，c=1、c=20、c=30的服务可用率如图4所示。

由图4可见，在重叠覆盖策略下，当=1时，即退化为全覆盖策略，若仿真节点足够多(>80)，则重叠覆盖策略可以获得逼近于全覆盖策略的仿真服务可用率，从而在降低对仿真节点资源消耗的前提下，提供可靠的仿真服务。

4 仿真实验与分析

通过虚拟机集群来验证仿真服务调度模型，在3台物理机上运行15台虚拟机，各虚拟机上运行监控代理，将监控数据存入状态数据库，各仿真客户端将仿真服务请求送往调度器并获得仿真结果。本文定义负载平衡度(Load Balance Degree, LBD)为各仿真节点实际负载的标准差，使用LBD来衡量基于环境感知的仿真服务调度模型C3SM中改进蚁群算法与经典批模式调度算法的性能。

4.1 实验场景与参数设置

设定20个仿真客户端，分为A、B方，两方互为攻击目标。初始时，A、B方的仿真客户端均申请加入仿真任务组，待所有客户端均成功加入后，执行仿真任务，各客户端通过使用Web service来进行仿真模拟，直到一方的所有仿真客户端均退出执行。本文使用Web service实现基本的仿真运行管理，各仿真客户端通过仿真服务调度器来获得服务执行结果，进而决定操作流程。表3给出了实验中的参数设置。

表3 实验参数设置

在表3中，表示每个参数取值的固定值，表示每个参数取值的最小阈值，表示每个参数取值的最大阈值，表示每个参数迭代的步长。

4.2 C3SM模型的调度算法负载平衡度比较

基于环境感知的仿真服务调度模型C3SM在监控各仿真节点负载与服务可用性的基础上，使用修改的蚁群算法来获得最佳的仿真服务映射列表，从而使得系统各仿真节点的负载达到平衡。实验对比了经典批模式调度算法与基于环境感知的仿真服务调度模型C3SM调度算法在负载平衡度方面的差异，如图5所示。

图5 不同调度算法的负载平衡度比较

从图5可以看出，随着调度(时间)的进行，经典的批模式调度算法Min-Min和Max-Min的负载平衡度波动较大，而C3SM模型调度算法的负载平衡度则逐渐趋于平衡。这是因为C3SM模型引入了监控代理来动态获取系统的实时运行状况，且通过调度结果的反馈来优化后续的调度过程，从而使得整个系统的负载随着调度的进行逐渐趋于平衡；而经典的批模式调度算法则不具备这种机制，因此在负载平衡度方面的性能较差，整个系统的负载平衡度呈波动 状态。

4.3 C3SM模型的执行可靠性比较

将功能相同的Web仿真应用改写为HLA/RTI规范的仿真程序。在运行中发现，由于联邦成员和RTI之间通过RID文件指定的网络地址和端口进行通信，且各联邦成员需要依赖其他成员的正常运行，因此任意联邦成员的失效均会导致整个仿真任务的执行失败。而基于环境感知的仿真服务调度模型C3SM由于使用具备副本的仿真服务，且调度器通过心跳信息可以发现出现故障的仿真，从而避开失效节点，提高了仿真运行的可靠性。实验模拟了节点失效率对基于环境感知的仿真服务调度模型C3SM和分布式仿真框架HLA/RTI的影响，具体如图6所示。

图6 节点失效率对仿真服务执行的影响

从图6可以看出，基于环境感知的仿真服务调度模型C3SM可以平滑节点失效对系统可靠性的影响，随着节点失效率的增加，仿真服务的执行成功率很缓慢的下降，且能维持在较高的水平；而分布式仿真框架HLA/RTI则不具备此能力，随着节点失效率的增加，仿真服务的执行成功率急速下降到一个很低的水平，明显降低了系统的可靠性，使得仿真系统无法正常运行。

5 结束语

针对分布式仿真技术框架HLA/RTI在动态调度和执行可靠性方面存在的问题，本文提出了一种基于环境上下文感知的仿真服务调度模型C3SM。C3SM模型使用Web service负责仿真服务的封装和仿真运行的管理，利用监控代理感知运行环境信息，并采用改进的蚁群算法调度仿真请求，获得了较优的负载平衡度和较高的系统可靠性。下一步主要考虑完善Web service仿真运行管理的功能，提高仿真系统的运行效率。

[1] 彭 勇, 蔡 楹, 钟荣华, 等. 多核环境下面向仿真组件的HLA成员并行框架[J]. 软件学报, 2012, 23(8): 2188-2206.

[2] Boukerche A, de Grande R E. Dynamic Load Balancing Using Grid Services for HLA-based Simulations on Large-scale DistributedSystems[C]//Proc. of the 13th IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications. Singapore: IEEE Press, 2009: 175-183.

[3] 张 柯, 邱晓刚. 基于HLA的分布仿真系统运行全过程管理[J]. 计算机仿真, 2005, 22(4): 158-161.

[4] 唐 震, 李伯虎, 柴旭东, 等. 普适化仿真网格中仿真服务迁移技术的研究[J]. 系统仿真学报, 2009, 21(12): 3631- 3636.

[5] Zhang Heming, Wang Hongwei, Chen D. Integrating Web Services Technology to HLA-based Multidisciplinary Collaborative Simulation System for Complex Product Development[C]//Proc. of the 12th International Conference on Computer Supported Cooperative Work in Design. Xi’an, China: [s. n.], 2008: 420-426.

[6] Zhu Hengye, Li Guangyao, Zheng Liping. Introducing Web Services in HLA-based Simulation Application[C]//Proc. of the 7th World Congress on Intelligent Control and Automation. Chongqing, China: [s. n.], 2008: 1677-1682.

[7] Quaglia F. Enhancing the Performance of HLA-based Simu- lation Systems via Software Diversity and Active Replica- tion[C]//Proc. of the 20th International Symposium on Parallel and Distributed Processing. Rhodes, Greece: IEEE Press, 2006: 1-8.

[8] Tang Jianbing, Zha Yabing, Huang Xiaohui. Research on Cre- dibility of HLA Warfare Simulation[C]//Proc. of International Conference on Computational Intelligence and Software Engineering. Wuhan, China: [s. n.], 2009: 1-4.

[9] Song Hengjie, Shen Zhiqi, Miao Chunyan, et al. The Multi- Agent Data Collection in HLA-based Simulation System[C]// Proc. of the 21st International Workshop on Principles of Advanced and Distributed Simulation. San Diego, USA: IEEE Press, 2007: 61-69.

[10] He Xiaoshan, Sun Xiaohe, von Laszewski G. QoS Guided Min- Min Heuristic for Grid Task Scheduling[J]. Journal of Computer Science and Technology, 2003,18(4): 442-451.

[11] Freund R F, Gherrity M, Ambrosius S, et al. Scheduling Resources in Multi-user, Heterogeneous, Computing Environments with SmartNet[C]//Proc. of the 7th Hetero- geneous Computing Workshop.Orlando, USA: ACM Press, 1998: 184-199.

[12] Dorigo M, Maniezzo V. Colorni A. The Ant System: Optimization by a Colony of Co-operating Agents[J]. IEEE Transactions on Systems, Man and Cybernetics, 1996, 26(1): 29-41.

编辑 任吉慧

A Context-aware Simulation Service Scheduling Model

ZHANG Xue-jun, YAN Guang-hui, HU Xiao-hui

(School of Electronics and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)

In order to address the problem of traditional distribution simulation framework HLA/RTI with respect to poor load balancing performance in service dynamic scheduling and low reliability of service execution, this paper proposes a Context-aware Simulation Service Scheduling Model(C3SM), which includes general framework, scheduling strategy and service deployment. The framework provides the functions and interaction interfaces of each module. For the scheduling scheme, a modified ant colony algorithm is used to achieve optimum load balancing and system reliability. Moreover, the overlapped coverage deployment strategy is adopted to obtain the high service availability and low resource consumption in the service deployment. Experiments are carried out on performance comparisons between the traditional HLA/RTI and C3SM in the scheduling strategy and the reliability of service performing, the results show that C3SM can obtain good load balance with the real-time context information of the execution environment, and the overlapped coverage simulation service deployment scheme greatly improves the reliability of the simulation execution system.

context-aware; High Level Architecture(HLA); distributed simulation; Web service; ant colony algorithm; simulation service scheduling

1000-3428(2014)03-0093-06

A

TP391.9

国家自然科学基金资助项目(61163009, 61163010)。

张学军(1977－)，男，讲师、博士研究生，主研方向：服务计算，服务仿真；闫光辉、胡晓辉，教授。

2013-05-29

2013-07-21 E-mail：zxjly1_new@163.com

10.3969/j.issn.1000-3428.2014.03.019