The distributed network monitoring model with bounded delay constraints
Xianghui Liu, Yin Jian-ping, Xicheng Lu, Cai Zhi-ping, Zhai Jian-min · Wuhan University Journal of Natural Sciences · 2004
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 ln m +1, where is the number of monitoring nodes. At last we extend our modal with more constraint of bounded delay variation.