一種環境感知的仿真服務調度模型

張學軍，閆光輝，胡曉輝

?

一種環境感知的仿真服務調度模型

張學軍，閆光輝，胡曉輝

(蘭州交通大學電子與信息工程學院，蘭州 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