Multispanners for Robust Routing in Mobile Ad Hoc Networks

K.M. Alzoubi and M.S. Ayyash (USA)


connected dominating set, sparse spanner, multispanner, multipath, robustness.


A sparse spanner is of fundamental importance for rout ing in mobile ad hoc networks (MANETs). However, rout ing based on a single spanner is unreliable in MANETs. This is due to frequent and unpredictable topology changes and path failures. A single path renders a lack of reliabil ity and inefficient use of bandwidth. Reliability and band width issues are key factors for any robust routing scheme. Therefore, this paper presents a novel solution to address these robustness aspects by using multiple paths between each source and destination. In this paper, we extend an existing work on designing a cluster-based sparse spanner for MANETs with constant topological and geometric dila tion, and in linear time and linear messages. First, we pro vide multiple paths between adjacent clusters in the span ner. Then, we propose a technique to create multi-spanners with low routes overlapping.

Important Links:

Go Back