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

Network Connectivity Automatic Test Based on Minimum Set Cover

作　　者：张馨[1] 薛质[1] 范磊[2] 

机构地区：[1]上海交通大学电子信息与电气工程学院,上海200240 [2]上海交通大学信息安全工程学院,上海200240

出　　处：《计算机工程》2012年第24期65-69,共5页Computer Engineering

基　　金：国家"863"计划基金资助项目(2007AA01Z473)

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

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]