论文部分内容阅读
分布式网络监测系统能够实时有效地收集网络性能数据，但收集过程受到链路延迟和路由跳数的约束．链路约束的分布式网络监测模型研究如何在链路约束下用最小的代价部署整个分布式网络监测系统；链路约束的演化网络监测模型研究在网络演化的情况下，如何用最小的更新代价重新部署监测系统使之满足链路约束．求取这两个模型的最优解的问题都是NP难的．通过指定权函数的形式，两个模型对应的最优化问题能够映射成带权的集合覆盖问题，采用贪婪策略能够得到近似比不超过ln n＋1的近似算法，其中n是被监测节点的数目．通过仿真实验还讨论了如何选择