一种测量节点放置和探测路径规划的启发式方法

摘要

本发明公开了一种测量节点放置和探测路径规划的启发式方法，用于解决网络链路时延测量时的测量节点放置和探测路径规划问题，所述方法包括：将原网络拓扑中的网络链路和网络节点分别映射到二部图中的链路节点和网络节点，从而得到原网络拓扑的辅助二部图，进而得到拓展的辅助二部图，以将测量节点放置和探测路径规划问题转化为最大流最小费用问题；在拓展的辅助二部图上，通过改进的标号算法得到最大流初始解，然后不断地尝试删除部分网络节点，并将流经该网络节点的流迁移到其它网络节点，以最小化测量节点数，使得该NP‑hard问题能够在较短的时间内进行求解。