Abstract
Several centralized and distributed algorithms have been recently proposed to maximize the multicast lifetime for directional communications in wireless ad-hoc networks. Their performance has been studied by simulations; however, their theoretical performance in terms of approximation ratio is still unknown. In this paper, we use the graph theoretic approach, by the first time, to derive the upper bound of the approximation ratio in an analytical expression for these algorithms. We have also discovered that these upper bounds are finite numbers. Based on this analysis and some key observations, we present a new distributed constant-factor approximation algorithm in order to achieve a higher performance. This effort is validated by our simulation studies.
Original language | English |
---|---|
Title of host publication | MobiHoc'07 |
Subtitle of host publication | Proceedings of the Eighth ACM International Symposium on Mobile Ad Hoc Networking and Computing |
Pages | 190-198 |
Number of pages | 9 |
DOIs | |
Publication status | Published - 1 Dec 2007 |
Externally published | Yes |
Event | MobiHoc'07: 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing - Montreal, QC, Canada Duration: 9 Sept 2007 → 14 Sept 2007 |
Conference
Conference | MobiHoc'07: 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing |
---|---|
Country/Territory | Canada |
City | Montreal, QC |
Period | 9/09/07 → 14/09/07 |
Keywords
- Approximation algorithm
- Directional antenna
- Maximum-lifetime routing
- Multicast tree
- Wireless ad hoc networks
ASJC Scopus subject areas
- Software
- Hardware and Architecture
- Computer Networks and Communications