Multicast ad hoc routing through mobility-aware Steiner tree meshes with consistency across different mobility models

Abstract

We study the problem of reducing the data overhead of mesh-based multicast ad hoc routing protocols while maintaining high packet delivery ratios (PDR). Our proposed approach adaptively controls the redundancy added by the routing protocol to the minimal data overhead multicast mesh. We show that the problem of finding the minimal data overhead multicast mesh is NP-complete, and we offer a heuristic algorithm to approximate such a mesh. Based on the heuristic algorithm, we propose and evaluate several mesh construction algorithms. We show that the mobility-aware variant being able to control the reliability of the mesh depending upon the mobility of the network offers the best performance. Our simulation results show that our proposed approach offers similar PDRs than ODMRP at a much lower data overhead. In addition, the simulations show that our mobility metric provides consistent results across different mobility models.

Keywords:

• Steiner tree
• multicast ad hoc routing
• mobility aware

Acknowledgements

Part of this work has been funded by Spanish MCYT by means of the “Ramon y Cajal” work programme, the ICSI Call for Spanish Technologists and the SMART (MEC, TIN2005-07705-C02-02) project. The authors want to thank L. Subramanian and Scott Shenker for their comments and insight.

Notes

^¶Email: [email protected]

Additional information

Notes on contributors

Antonio F. Gomez-Skarmeta

¶ ¶Email: [email protected]