共 1 条
链路约束的分布式网络监测模型
被引：2
作者：
蔡志平
殷建平
刘湘辉
刘芳
吕绍和
机构：
[1] 国防科学技术大学计算机学院
来源：
关键词：
分布式监测;
链路约束;
集合覆盖问题;
NP难;
贪婪算法;
D O I：
暂无
中图分类号：
TP393.07 [];
学科分类号：
081201 ;
1201 ;
摘要：
分布式网络监测系统能够实时有效地收集网络性能数据,但收集过程受到链路延迟和路由跳数的约束.链路约束的分布式网络监测模型研究如何在链路约束下用最小的代价部署整个分布式网络监测系统;链路约束的演化网络监测模型研究在网络演化的情况下,如何用最小的更新代价重新部署监测系统使之满足链路约束.求取这两个模型的最优解的问题都是NP难的.通过指定权函数的形式,两个模型对应的最优化问题能够映射成带权的集合覆盖问题,采用贪婪策略能够得到近似比不超过lnn+1的近似算法,其中n是被监测节点的数目.通过仿真实验还讨论了如何选择恰当的链路延迟约束值.
引用
收藏
页码：601 / 606
页数：6
相关论文