Abstract: The probe deployment of distributed network monitor must be tradeoff between cost and coverage. A new approach to network monitor’s deployment based on genetic algorithm is presented with the goal of minimizing the number of network monitors subjected to link coverage and message coverage. The genetic algorithm based on edge coding is preferred to traditional genetic algorithm. The simulation indicates that the performance of the algorithm is better than the greedy algorithm.

Key words: Network performance monitor, Set coverage, Greedy algorithm, Genetic algorithm

摘要： 对于分布式网络性能的监测，监测探针的部署必须在代价和覆盖范围之间进行权衡。该文以最小化监测探针数目为目标，在链路覆盖和消息覆盖约束条件下，讨论了一种基于遗传算法的网络性能监测探针部署方法，并且在传统遗传算法的基础上提出了使用基于边编码的遗传算法解决监测探针的部署问题。实验表明基于遗传算法及其改进算法的监测探针部署方法比贪婪算法具有更好的性能。

关键词: 网络性能监测, 集合覆盖, 贪婪算法, 遗传算法