作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (24): 65-69. doi: 10.3969/j.issn.1000-3428.2012.24.016

• 网络与通信 • 上一篇    下一篇

基于最小集合覆盖的网络连通性自动化测试

张 馨a,薛 质a,范 磊b   

  1. (上海交通大学 a. 电子信息与电气工程学院;b. 信息安全工程学院,上海 200240)
  • 收稿日期:2011-09-13 修回日期:2011-11-01 出版日期:2012-12-20 发布日期:2012-12-18
  • 作者简介:张 馨(1987-),女,硕士研究生,主研方向:网络性能测试;薛 质,教授、博士;范 磊,副教授、博士
  • 基金资助:

    国家“863”计划基金资助项目(2007AA01Z473)

Network Connectivity Automatic Test Based on Minimum Set Cover

ZHANG Xin a, XUE Zhi a, FAN Le ib   

  1. (a. School of Electronic Information and Electrical Engineering; b. School of Information Security Engineering, Shanghai Jiaotong University, Shanghai 200240, China)
  • Received:2011-09-13 Revised:2011-11-01 Online:2012-12-20 Published:2012-12-18

摘要: 网络规模的增长加大了分布式网络管理与测试的难度。为此,提出一种优化的全连通自动化测试用例集生成算法。在最小集合覆盖理论的基础上,引入空间因子参数,优先选取搜索空间中起点或终点被选取次数最多的测试路径进入解集,以减少测试点数。实验结果表明,该算法在空间因子为4的情况下,比贪心搜索算法减少约20%的测试点数,比GRASP算法缩短约99.9%的测试时间,具有较高的测试效率。

关键词: 网络连通性, 自动化测试, 测试用例生成, 最小集合覆盖, 贪心搜索算法, GRASP启发式算法

Abstract: The rapidly expanding network scale in recent years brings more and more severe challenges to the distributed network management and test area. In this paper, a new approach of full connectivity testing suite generation problem of distributed network is presented with the goal of increasing the test efficiency by introducing a space parameter based on Minimum Set Cover(MSC) theory. Experimental result shows that the proposed algorithm is more effective than other generation algorithms, about 20% less of test probes than Greedy Search Algorithm(GSA) algorithm and about 99.9% less of calculation time than GRASP algorithm when the space parameter is four.

Key words: network connectivity, automatic test, test suite generation, Minimum Set Cover(MSC), Greedy Search Algorithm(GSA), GRASP heuristic algorithm

中图分类号: