Localized protocols for ad hoc clustering and backbone formation: a performance comparison
Authors:
- M. MastrogiovanniMMM. Mastrogiovanni
- A. PanconesiAPA. Panconesi
- C. PetrioliCPC. Petrioli
- 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
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 11 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 NetworksMobile Networks and Applications, 2004
- Distributed construction of connected dominating set in wireless ad hoc networks2003
- Distributed clustering for ad hoc networks2003
- An efficient distributed algorithm for constructing small dominating setsDistributed Computing, 2002
- Virtual backbone generation and maintenance in ad hoc network mobility management2002
- 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 networks1999
- A new approach to the design and analysis of peer‐to‐peer mobile networksWireless Networks, 1999