Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Localized Minimum Spanning Tree Based Multicast Routing with Energy-Efficient Guaranteed Delivery in Ad Hoc and Sensor Networks
 
Loading...
Thumbnail Image
conference paper

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

Frey, Hannes
•
Ingelrest, François  
•
Simplot-Ryl, David
2008
The 9th IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WOWMOM 2008)
The 9th IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WOWMOM 2008)

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 an 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 replication 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-known 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 energy-efficient, outperforms the best existing localized multicast scheme and is almost as efficient as a centralized scheme in high densities.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

2008-wowmom.pdf

Access type

openaccess

Size

340.9 KB

Format

Adobe PDF

Checksum (MD5)

0f437932988f28eac857f24fefed9c29

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés