Distributed construction of connected dominating set in wireless ad hoc networks
Proceedings - IEEE INFOCOM - Tập 3 - Trang 1597-1604 vol.3
Tóm tắt
The connected dominating set (CDS) has been proposed as the virtual backbone or spine of a wireless ad hoc network. Three distributed approximation algorithms have been proposed in the literature for minimum CDS. We first reinvestigate their performances. None of these algorithms have constant approximation factors. Thus these algorithms can not guarantee to generate a CDS of small size. Their message complexities can be as high as O(n/sup 2/), and their time complexities may also be as large as O(n/sup 2/) and O(n/sup 3/). 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(n log n) message complexity. By establishing the /spl Omega/(n log n) lower bound on the message complexity of any distributed algorithm for nontrivial CDS, our algorithm is thus message-optimal.
Từ khóa
#Intelligent networks #Ad hoc networks #Mobile ad hoc networks #Spine #Distributed algorithms #Network topology #Approximation algorithms #Computer networks #Computational efficiency #Land mobile radio cellular systemsTài liệu tham khảo
chen, 1999, Clustering and routing in wireless ad hoc networks
burns, 1980, A formal model for message passing systems
sivakumar, 0, An improved spine-based infrastructure for routing in ad hoc networks, IEEE Symposium on Computers and Communications '98 Athens Greece June 1998
bharghavan, 0, Routing in ad hoc networks using minimum connected dominating sets, International Conference on Communications'97 Montreal Canada June 1997
10.1109/ICCCN.1997.623288
10.1016/0012-365X(90)90358-O
cidon, 0, Propagation and leader election in multihop broadcast environment, 12th International Symposium on Distributed Computing (DISC98) September 1998 Greece, 104
10.1287/moor.4.3.233
10.1109/49.622910
10.1007/BF01200845
10.1109/71.980024
10.1145/313239.313261