HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Localized Minimum Spanning Tree Based Multicast Routing with Energy-Efficient Guaranteed Delivery in Ad Hoc and Sensor Networks

Abstract : We present a minimum spanning tree based energy aware multicast protocol (MSTEAM), which is a localized geographic multicast routing scheme designed for ad hoc and sensor networks. It uses locally-built minimum spanning trees (MST) as an efficient approximation of the optimal multicasting backbone. Using a MST is highly relevant in the context of dynamic wireless networks since its computation has a low time complexity (O(n log n)). Moreover, our protocol is fully localized and requires nodes to gather information only on 1-hop neighbors, which is common assumption in existing work. In MSTEAM, a message split occurs when the MST over the current node and the set of destinations has multiple edges originated at the current node. Destinations spanned by each of these edges are grouped together, and for each of these subsets the best neighbor is selected as the next hop. This selection is based on a cost over progress metric, where the progress is approximated by subtracting the weight of the MST over a given neighbor and the subset of destinations to the weight of the MST over the current node and the subset of destinations. Since such greedy localized scheme may lead the message to a void area (i.e., there is no neighbor providing positive progress toward the destinations), we also propose a completely new multicast generalization of the well-know face recovery mechanism. We provide a theoretical analysis proving that MSTEAM is loop-free and always achieves delivery of the multicast message, as long as a path exists between the source node and the destinations. Our experimental results demonstrate that MSTEAM is highly energy-efficient, outperforms the best existing localized multicast scheme and is almost as efficient as a centralized scheme in high densities.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, June 12, 2007 - 10:00:46 AM
Last modification on : Wednesday, February 23, 2022 - 11:58:02 AM
Long-term archiving on: : Tuesday, September 21, 2010 - 12:41:25 PM


Files produced by the author(s)


  • HAL Id : inria-00153816, version 2



Hannes Frey, François Ingelrest, David Simplot-Ryl. Localized Minimum Spanning Tree Based Multicast Routing with Energy-Efficient Guaranteed Delivery in Ad Hoc and Sensor Networks. [Technical Report] RT-0337, INRIA. 2007. ⟨inria-00153816v2⟩



Record views


Files downloads