DOI: 10.3969/j.issn.1673-4785.
,
,
2. College of Information and Electrical Engineering, Hebei University of Engineering, Handan 056038, China
随着软件产品规模的不断发展扩大，软件测试技术成为一个重要的研究热点，测试技术是保障软件质量和性能的重要手段[1]。本文采用分布式自动化测试，即分布式的采集，集中化的分析管理，共享的数据资源，不但能够自动进行回归测试，而且还具有多平台测试功能。
在分布式自动化测试平台中，测试任务调度算法是其重要的组成部分，测试任务调度算法是实现测试任务最优化划分的方案，调度算法的优劣直接影响了测试平台完成测试任务的效率[2]。本文采用基于动态优先权的蚁群算法，蚁群算法具有较强的鲁棒性，易于与其他方法结合，基于动态优先权的蚁群算法能够缩短测试任务总执行时间和平均执行时间，从而合理利用测试资源，提高测试效率。
本文通过利用GridSim仿真模拟器对任务调度模块中使用的基于动态优先权蚁群算法进行仿真模拟，通过仿真实验验证了该算法具有良好的性能。
1 分布式自动化测试平台概述 1.1 分布式自动化测试的描述分布式测试是指通过网络，把分布于不同地理位置、独立完成指定测试功能的计算机连接起来，以达到测试资源共享、分散操作、集中管理、协同工作、负载均衡、测试过程监控等目的的计算机网络测试。分布式测试具有网络化、分布性、开放性、实时性、动态性等特点。具有容错能力强、可靠性高、安全性好等优点。
自动化测试就是使用软件工具代替手工进行的一系列测试动作，从而减少手工测试的工作量或者执行人力无法有效执行的测试，以达到保证软件质量，缩短测试周期的效果。K.Stobie和M.Bergman提出了用缩写“SEARCH”来描述测试自动化的组成部分，即设置、执行、分析、报告、清理和帮助，大型的自动化测试依赖于复杂的框架来保证测试产生格式统一的测试报告，自动化测试基础设施图如图1所示[3]。
|
| 图 1 自动化测试基础设施 Fig. 1 Automation test infrastructure |
分布式自动化测试平台可以满足多个产品的测试需求，要求是多任务及多功能的，在执行测试策略时，被测对象任务可以灵活搭配，在保证软件质量的前提下，缩短了维护及修改测试脚本所用的时间，缩短测试周期，提高测试效率，降低软件开发成本。
1.2 分布式自动化测试平台的框架自动化测试系统是一个面向数据驱动和信息的系统，分布式的自动化测试框架模型主要包含3个子系统：用户接口子系统、状态机处理子系统、后台测试子系统[4-5]。测试子系统的结构图如图2所示。
|
| 图 2 子系统结构图 Fig. 2 Subsystem structure |
本文主要介绍状态机子系统，此子系统由状态改变，事件处理、时间处理、套件执行控制等模块组成，主要负责测试任务的调度及状态管理等工作，使测试平台对于时间、任务、资源的安排灵活，从而更好地提高测试效率。状态机子系统的控制流程图如图3所示。
|
| 图 3 状态机子系统的控制流程图 Fig. 3 Control flow chart of state machine system |
分布式自动化测试平台包含了测试任务的执行、调度、测试结果及报告分析功能。本文针对任务调度功能，系统支持任意的测试项目组合及时间调度，通过系统中的Job完成，即同一时间测试不同的项目及在用户设置的时间段内完成测试项目，帮助用户在任意时间运行测试脚本。
2 蚁群算法的任务调度蚁群算法(ant colony optimization,ACO)是由M.Dorigo于1992年在博士论文中提出的，通过正反馈、分布式协作来寻找最优路径[6-8]。针对分布式自动化测试平台中的状态机子系统中的任务调度问题，使用基于动态优先权的蚁群算法，能够得到较短的总任务执行时间和平均任务执行时间。本文对蚁群算法的选择搜索策略应用了动态优先权，进一步增加了蚁群算法的搜索能力。
2.1 蚁群算法模型蚁群算法是根据路径上的信息素浓度，以某种概率来选取下一步的路径，通过信息素调整解的选取，从而得到问题的全局最优解。
蚁群算法在求路径最优解的过程中引入变量τij(t)、Δτij、Δτijk、pijk，其中1≤i,j≤n,1≤k≤m，n表示城市数，m表示人工蚂蚁个数。蚂蚁完成一次循环，相应边上的信息素浓度，τij(t+1)=ρτij(t)+Δτij，又$$\Delta {\tau _{ij}} = \sum\limits_{k = 1}^m {\Delta \tau _{ij}^k} $$。根据Δτijk的取值定义Δτijk为
| $\Delta \tau _{ij}^k = \left\{ \begin{gathered} \frac{Q}{{{C_{ij}}}},第k{\text{只蚂蚁在}}(t,t + 1){\text{间过边}}\left( {i,j} \right) \hfill \\ 0,{\text{其他}} \hfill \\ \end{gathered} \right.$ | (1) |
式中：τij(t)为t时刻边(i,j)上的信息素浓度；Δτij为当前时间段新增加的信息素浓度；Δτijk为第k只蚂蚁在时间t~t+1之间，边(i,j)增加的信息素浓度；ρ为信息素浓度的权重；Q为路径搜索后，释放的信息素总量；Cij为路径所需费用，连接顶点Vi、Vj的权；选择路径(i,j)概率定义，即第k只蚂蚁当前时刻在顶点Vi，下一步选择顶点Vj，得：
| $p_{ij}^k\left( t \right) = \left\{ \begin{gathered} \frac{{{{[{\tau _{ij}}(t)]}^a} \times {{[{\eta _{ij}}(t)]}^\beta }}}{{\sum {_l{{[{\tau _{ij}}(t)]}^a} \times {{[{\eta _{il}}(t)]}^\beta }} }},ifj \in l \hfill \\ 0,其他 \hfill \\ \end{gathered} \right.$ | (2) |
又${\eta _{ij}} = \frac{1}{{{C_{ij}}}}$，pijk(t)为t时刻路径选择的概率；α为控制信息素浓度的相对重要性(α≥0)；β为路径长度的相对重要性(β≥0)；l为t+1时刻可以选择的路径集合。
2.2 基于动态优先权的蚁群调度算法本文在分布式自动化测试平台的测试任务调度模块中，应用基于动态优先权的蚁群调度算法，即选择高优先权的测试任务，优先权高的任务先执行。通过蚁群算法搜索任务调度最优解时，考虑任务的最大等待时间、空闲时间和任务的权重值，从而使任务的调度达到最优，减少有价值任务的等待时间和任务的执行时间。
在任务的调度过程中，给定一组任务S，在任务S中选取n个任务列表T为集群{1,2,…,n}及搜索所有任务的总时间Cij(1≤i,j≤n,i≠j)，m个虚拟机M集群{1,2,…,m}，任何任务可以在任一台虚拟机上执行，在每次调度过程中，等待执行的任务数赋值n，空闲虚拟机数赋值m。
用户通过系统接口提交测试任务，在测试任务中引入变量τij(t)(τij>0的整数)表示在空闲时间和等待时间(Ii,Wj)范围中t时刻的任务数。Ii为在持续时间和截止时间之间的当前空闲时间；Wj为提交任务时的持续时间和当前空闲时间之间的等待时间。当蚁群调度算法搜索完成一次循环时，相应时刻上的任务数为τij(t+n)=wτij(t)+(1－w)Δτij，即等于上一时刻的任务数加上当前时间段新增加的任务数。w表示动态优先权中的权重。又$\Delta {\tau _{ij}} = \sum\limits_{k = 1}^m {\Delta \tau _{ij}^k} $，即Δτijk是第k个虚拟机上在时间段(Ii,Wj)完成的任务数比例。得：r
| $\Delta \tau _{ij}^k = \left\{ \begin{gathered} \frac{Q}{{{C_{ij}}}},第k{\text{个虚拟机上任务数}} \hfill \\ 0,{\text{其他}} \hfill \\ \end{gathered} \right.$ | (3) |
式中：Q是一个常量，表示一次搜索完成后，完成的任务数总量。从而体现在一次搜索完成后，任务数的完成量在各个虚拟机上任务数的分配，即：
| $\sum {\Delta \tau _{ij}^k = \frac{{\sum Q }}{{{C_{ij}}}}} = Q$ | (4) |
从而得出第k个虚拟机上搜索一次完成任务所需执行时间的概率：
| ${p_{ij}}\left( k \right) = \left\{ \begin{gathered} \frac{{{{[{\tau _{ij}}(k)]}^a} \times {{[\frac{1}{{{C_{ij}}}}(k)]}^\beta }}}{{\sum {_l{{[{\tau _{ij}}(k)]}^a} \times {{[\frac{1}{{{C_{il}}}}(k)]}^\beta }} }},ifj \in l \hfill \\ 0,其他 \hfill \\ \end{gathered} \right.$ | (5) |
在任务测试的调度过程中，任务的等待时间变量Wkj和空闲时间变量Iki之间有一定的联系，即Iki>0，Wk-1,j+1=0，两者之间的关系是建立在过程时间变量ρi(k)的基础上。过程时间变量是决策变量xki和n个任务的完成时间概率的乘积之和，即：
| ${p_i}(k) = \sum\limits_{i = 1}^n {{x_{ki}}{p_{ij}}} $ | (6) |
完成任务总的空闲时间为
| ${I_{ni}} = \sum\limits_{i = 1}^{m - 1} {{p_i}} (l) + \sum\limits_{j = 1}^{n - 1} {{W_{mj}}} $ | (7) |
由此得出测试任务优先权的计算公式：
| $p = \frac{{{W_{mj}} + {I_{ni}}}}{{{I_{ni}}}} + \pi w$ | (8) |
任务的权重可由相应时刻的任务数求得：
| $w = \frac{{{\tau _{ij}}(t + n) - \Delta {\tau _{ij}}}}{{{\tau _{ij}} - \Delta {\tau _{ij}}}}$ | (9) |
式中：P为任务的优先级；Wmj为任务的等待时间；Ini为任务的空闲时间；w为任务的权重；π为引进的参数。
在调度过程中的任务队列中，1) 如果当n>m时，根据优先权的公式，算出所有任务的优先权。按优先权顺序，将前m个任务分配给m各虚拟机。将任务T1到Tm从队列中删除，将虚拟机M1到Mm从列表中删除。2)n≤m时，释放多余处理机，将虚拟机Mi分配给任务Tj，并在测试任务执行完之后立即释放对应的处理机。
通过对蚁群算法应用动态优先权，从而提高了测试调度任务中的执行时间效率，将蚁群算法中的选择搜索最优解的过程通过动态优先权中的等待时间和空闲时间来确定了任务的优先级，增加了任务搜索的效率，减小了任务的执行时间，从而使分布式自动化测试中任务的调度效率达到最佳。
3 算法仿真结果与实验测试分析本文采用网格计算机仿真工具开发包GridSim 对基于动态优先权的蚁群算法进行任务调度测试分析，将仿真测试结果与基本的蚁群算法调度结果进行对比，并且对冲击值进行了比较。
在基于动态优先权的蚁群调度算法中，各参数设置为：α=1，β=2，w=0.7，Q=1，n=100，m=100，本文的任务数为10，20，…，100，分别采用基本蚁群算法和基于动态优先权的蚁群算法进行测试任务的调度。算法的执行时间对比情况如图4所示：
|
| 图 4 实验结果 Fig. 4 Experimental resules |
为了评估调度算法的优越性，引进冲击值来比较基本蚁群算法和本文的基于动态优先权蚁群算法的冲击值效率。给定每个任务i，vi为它的值，T_finishi为截止时间，T_submiti为过程时间。即
| $HitValue = \sum\limits_{i = 1}^n {\frac{{{v_i}}}{{\sqrt {T\_{\text{finis}}{{\text{h}}_i} - {\text{submi}}{{\text{t}}_i}} }}} $ | (10) |
从而得到两者的冲击值的比较曲线如图5所示。
|
| 图 5 动态优先权的蚁群算法和基本蚁群算法冲击值的比较曲线 Fig. 5 comparison curve between Hit value of ant colony algorithm based on dynamic priority and ant colony algorithm |
由仿真实验结果发现，基于动态优先权的蚁群算法优于基本的蚁群算法，随着任务数的增多，这种优势更加明显。因为基于动态优先权的蚁群算法随着任务调度规模的逐渐增加，使得求解效率得到迅速提高。通过执行时间的比较可以得出，基于动态优先权的蚁群调度算法解决了前期搜索低下的缺陷和具有求解精度高的双重优势，从而提高了任务调度的执行效率，并且在优先权下对任务数所对应的冲击值得到了提高，从而使测试调度任务更加优化和有效。
4 结束语本文在分布式自动化测试平台中的任务调度模块中应用了基于动态优先权的蚁群调度算法，通过分析基本蚁群调度算法的模型，在动态优先权的蚁群调度算法中任务调度策略和执行时间上都得到了大大的提高。由仿真实验结果可知，在大规模的任务调度下，基于动态优先权的蚁群调度策略明显优于基本的蚁群调度算法，任务的执行时间减少，冲击值的利用率更高。通过本算法使测试任务调度模块的执行效率更高。
| [1] | MYERS G J, BADGETT T, SANDLER C. The art of software testing. 3rd ed. Wiley[M]. 2012 : 24 -29. |
| [2] | PINEDO M L. Scheduling: theory, algorithms, and systems. 4th ed. Springer[M]. 2012 : 391 -392. |
| [3] | PAGE A, JOHNSTON K, ROLLISON B. How we test software at Microsoft. Microsoft Press[M]. 2008 : 216 -218. |
| [4] | GU Wenquan, HUANG Chang. Distributed automatic test system research[C]//Proceedings of Computer Science and Network Technology. Harbin, China, 2011: 1834-1836. |
| [5] | CHAN T. Distributed automatic test pattern generation[C]//Proceedings of ASIC Conference and Exhibit. Rochester, NY, 1992: 698-702. |
| [6] | LESSING L, DUMITRESCU I. A new version of ant system for subset problem[C]//Proceedings of the Evolutionary Computation Congress. Washington, DC, USA, 1999:21-25. |
| [7] | 方甲永, 肖明清, 谢娟. 基于遗传蚁群算法的并行测试任务调度与资源配置[J]. 测试技术学报,2009, 23 (4) : 343 –349. FANG Jiayong, XIAO Mingqing, XIE Juan. Parallel test tasks scheduling and resources configuration based on GA-ACA[J]. Journal of Test And Measurement Technology,2009, 23 (4) : 343 –349. |
| [8] | 邓见光, 袁华强, 赵跃龙. 一种基于遗传—蚁群算法的网格任务调度策略[J]. 计算机应用研究,2011, 28 (12) : 4485 –4488. DENG Jianguang, YUAN Huaqiang, ZHAO Yuelong. Grid task scheduling strategy based on genetic-ant algorithm[J]. Application Research of Computers,2011, 28 (12) : 4485 –4488. |