Localized protocols for ad hoc clustering and backbone formation: a performance comparison
- 6 March 2006
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 17 (4), 292-306
- https://doi.org/10.1109/tpds.2006.52
Abstract
This paper concerns the comparative performance evaluation of protocols for clustering and backbone formation in ad hoc networks characterized by a large number of resource-constrained nodes. Our aim is twofold: we provide the first simulation-based detailed investigation of techniques for clustering and backbone formation that are among the most representative of this area of ad hoc research. Second, we delve into the nature of the selected protocols to assess the effects of the "degree of localization" on their operations, i.e., how being able to execute the protocol based only on local information affects the overall protocol performance. Extensive ns2-based simulation results show that highly localized protocols are rewarded with good performance with respect to all metrics of interest which include protocol duration, energy consumption, message overhead, route length, and backbone size.Keywords
This publication has 9 references indexed in Scilit:
- Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletonsJournal of Computer and System Sciences, 2005
- An extended localized algorithm for connected dominating set formation in ad hoc wireless networksIEEE Transactions on Parallel and Distributed Systems, 2004
- Distributed construction of connected dominating set in wireless ad hoc networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Distributed clustering for ad hoc networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- An efficient distributed algorithm for constructing small dominating setsDistributed Computing, 2002
- Virtual backbone generation and maintenance in ad hoc network mobility managementPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Dominating sets and neighbor elimination-based broadcasting algorithms in wireless networksIEEE Transactions on Parallel and Distributed Systems, 2002
- On calculating connected dominating set for efficient routing in ad hoc wireless networksPublished by Association for Computing Machinery (ACM) ,1999
- A new approach to the design and analysis of peer‐to‐peer mobile networksWireless Networks, 1999