一个新的分布式最小连通支配集近似算法

在计算机网络中广泛使用广播来解决一些网络问题，设计有效的广播算法是一项重要的课题。文中提出一种分布地计算网络最小连通支配集的近似算法并给出了它的正确性证明。它只需要网络节点具有局部的网络状态信息，可伸缩性强。通过此算法可以在网络中自动形成一个虚拟骨干网，从而可为网络中的广播和路由操作提供一个有效的通信基础。模拟结果表明，文中提出的算法求得的连通支配集小，能较好地应用于一般网络以及移动自组网络中。

A Novel Distributed Approximation Algorithm for Minimum Connected Dominating Set

Broadcast is widely used to resolve many network problems in computer networks. It is not only an important communication pattern in many applications, but also a fundamental operation in many on demand routing protocols for mobile ad hoc networks (MANETs). Flooding is an intuitive way for broadcasting. However, it can lead to the broadcast storm problem in MANETs. It is an important subject to design new efficient broadcast algorithms. Generally, the broadcast problem can be reduced to the minimum spanning tree problem in wired networks. However, with the assumption of omni directional antennae, the broadcast problem should be reduced to the minimum connected dominating set (MCDS) problem in wireless networks. As the MCDS problem is NP complete, a new distributed approximation algorithm is proposed in this paper. Then its correctness is proved theoretically. In the algorithm, nodes determine their status in a distributed way in accordance with several rules. Only local network state information is required in the computation executed by each node so that the algorithm can be scaled to large networks. The dominating nodes selected from the network nodes will rebroadcast non duplicated messages in broadcasting. Simulations are conducted to determine the performance of the algorithm. The simulation results show that the size of the resultant connected dominating set is small and the proposed algorithm outperforms two previous distributed broadcast algorithms. The algorithm can be utilized to form a virtual backbone in a network automatically. It provides an effective communication foundation for broadcast and routing operations in mobile ad hoc networks.