基于改进贪婪算法的测量节点选择优化方法

未来应用场景对名字解析系统有着确定性时延保障的需求，如何有效选择测量节点，为确定时延名字解析提供支撑是本文着力解决的问题。本文将网络测量节点部署问题映射成为最小点覆盖问题，并基于传统的贪婪算法提出一种面向网络测量节点选取的改进贪婪算法，从优化贪婪算法迭代周期和针对实际场景特点改进排序算法2个方面进行优化。实验结果表明，基于改进贪婪算法的求解方式比传统贪婪算法的求解方式，平均耗时减少了90%以上。

Measurement Node Selecting Method Based on Improved Greedy Algorithm

In the future application scenarios, there is a need of deterministic delay guarantee for the name resolution system. How to effectively select measurement nodes and provide support for exact delay name resolution is the problem this article focuses on. This paper maps the network measurement scheduling deployment problem to the minimum vertex cover problem and proposes an improved greedy algorithm which mainly optimizes the greedy algorithm iteration cycle and improves the sorting algorithm in certain scenarios. The experimental results show that the improved greedy algorithm is more than 900% faster than traditional greedy algorithm.