被动测试中观察者放置问题

On the Problem of How to Place the Observers in Passive Testing

在被动测试中如何放置观察者使得放置的数目最少并且能监视整个网络的运行情况是一个很有实际应用价值的问题·先证明了该问题是一个NP完全问题;接着讨论了在网络拓扑是树的特殊情形下该问题的解,并给出了针对树结构的一个线性时间算法;然后在一个已有的近似比为2的算法基础上给出了一个改进算法并证明了其近似比为2-O(1),最后用实验来验证了改进算法的有效性,指明了进一步的研究方向·

The problem of how to place the observers in passive testing while assuring they can monitor all the behavior of a network and the number of them is the smallest is an interesting and useful problem. First, this problem is proved to be an NP-complete problem. Then a special case in which the topology of network is a tree is discussed and a linear time algorithm for it is presented. Based on the thought of tree topology an improved approximate algorithm is proposed and the approximate proportion of the improved algotithm is 2-O（ 1 ） . Finally, a simulating experiment is conducted to illustrate the effectiveness of the improved algorithm and future extensions are discussed.