一个新的分布式最小连通支配集近似算法
彭伟;卢锡城
【期刊名称】《计算机学报》 【年(卷),期】2001(024)003
【摘要】在计算机网络中广泛使用广播来解决一些网络问题，设计有效的广播算法是一项重要的课题.文中提出了一种分布地计算网络最小连通支配集的近似算法并给出了它的正确性证明.它只需要网络节点具有局部的网络状态信息，可伸缩性强.通过此算法可以在网络中自动形成一个虚拟骨干网，从而可为网络中的广播和路由操作提供一个有效的通信基础.模拟结果表明，文中提出的算法求得的连通支配集小，能较好地应用于一般网络以及移动自组网络中.%Broadcast is widely used to resolve many network problems incomputer 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
一个新的分布式最小连通支配集近似算法
