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

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

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

CLC Number: 

• TP393