We address the problem of optimizing a distributed monitoring system and the goal of the optimization is to reduce the cost of deployment of the monitoring infrastructure by identifying a minimum aggregating set subje...We address the problem of optimizing a distributed monitoring system and the goal of the optimization is to reduce the cost of deployment of the monitoring infrastructure by identifying a minimum aggregating set subject to delay constraint on the aggregating path. We show that this problem is NP-hard and propose approximation algorithm proving the approximation ratio with lnm+1, where is the number of monitoring nodes. At last we extend our modal with more constraint of bounded delay variation. Key words network - distributed monitoring - delay constraint - NP-hard CLC number TP 393 Foundation item: Supported by the National Natural Science Foundation of China (60373023)Biography: LIU Xiang-hui(1973-), male, Ph. D. candidate, research direction: algorithm complexity analysis, QoS in Internet.展开更多
文摘We address the problem of optimizing a distributed monitoring system and the goal of the optimization is to reduce the cost of deployment of the monitoring infrastructure by identifying a minimum aggregating set subject to delay constraint on the aggregating path. We show that this problem is NP-hard and propose approximation algorithm proving the approximation ratio with lnm+1, where is the number of monitoring nodes. At last we extend our modal with more constraint of bounded delay variation. Key words network - distributed monitoring - delay constraint - NP-hard CLC number TP 393 Foundation item: Supported by the National Natural Science Foundation of China (60373023)Biography: LIU Xiang-hui(1973-), male, Ph. D. candidate, research direction: algorithm complexity analysis, QoS in Internet.
