Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks
Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks
复制标题
DOI：
10.1109/infcom.2002.1019411
复制
发表时间：
2002-11
影响因子：
3.8
通讯作者：
P. Wan;K. Alzoubi;O. Frieder
中科院分区：
文献类型：
--
作者：
P. Wan;K. Alzoubi;O. Frieder
连接支配集（CDS）被提出作为无线自组织网络的虚拟骨干或骨干。文献中提出了三种求解最小CDS的分布式近似算法。在本文中，我们首先重新研究了它们的性能。这些算法都没有常数近似因子。因此，这些算法不能保证生成小尺寸的CDS。它们的消息复杂度可能高达O(n2)，它们的时间复杂度也可能高达O（n2）和O（n3）。然后，我们提出了自己的分布式算法，该算法优于现有算法。该算法的近似系数不超过8，时间复杂度为O(n)，消息复杂度为O（nlog n）。通过建立非平凡CDS的任何分布式算法的消息复杂度的Ω（nlog n）下界，我们的算法因此是消息最优的。
Connected dominating set (CDS) has been proposed as virtual backbone or spine of wireless ad hoc networks. Three distributed approximation algorithms have been proposed in the literature for minimum CDS. In this paper, we first reinvestigate their performances. None of these algorithms have constant approximation factors. Thus these algorithms cannot guarantee to generate a CDS of small size. Their message complexities can be as high as O(n2), and their time complexities may also be as large as O(n2) and O(n3). We then present our own distributed algorithm that outperforms the existing algorithms. This algorithm has an approximation factor of at most 8, O(n) time complexity and O(nlog n) message complexity. By establishing the Ω(nlog n) lower bound on the message complexity of any distributed algorithm for nontrivial CDS, our algorithm is thus message-optimal.