Greedy Algorithms to Determine Stable Paths and Trees in Mobile Ad hoc Networks
Natarajan Meghanathan · InTech eBooks · 2008
In this chapter, we described algorithms OptPathTrans and OptTreeTrans to determine respectively the sequence of stable paths (Stable Mobile Path) and multicast trees (Stable Mobile Multicast Steiner Tree) over the duration of a MANET session. Performance study of the two algorithms, when the complete knowledge of future topology changes is available at the time of path/tree selection, illustrates a distinct tradeoff between path hop count and the number of path transitions, and the number of edges in the multicast Steiner tree and the number of multicast Steiner tree transitions. It is highly impossible to simultaneously achieve optimality in the above mentioned contrasting performance metrics for paths and trees. The sequence of stable paths and trees generated by the two algorithms under the ”Prediction with Uncertainty“ model are highly stable compared to their minimum mobile versions. Also, the hop count, the number of edges and the number of nodes in the stable paths and trees is not as high as that observed in the stable mobile paths and trees obtained when the algorithms are run with complete knowledge of the future topology changes. Note that the Dijkstra algorithm and the Kou et. al heuristic are merely used as a tool to find the appropriate stable communication structures. The optimal number of route and tree reconstructions does not depend on these underlying algorithms as we try to find the longest living route and tree in the mobile sub graph spanning a sequence of static graphs. But, the run-time complexity of the two algorithms depends on the underlying algorithm used to determine the Stable Mobile Path and the Stable Mobile Multicast Steiner Tree. Future work is on the following: (i) To develop distributed versions of OptPathTrans and OptTreeTrans by extending these algorithms respectively as unicast and multicast routing protocols, (ii) To study the performance of algorithms OptPathTrans and OptTreeTrans under other MANET mobility models like Random Walk, Random Direction and Gauss-Morkov models (Camp et. al., 2002) and (iii) To develop various location-update and mobility prediction mechanisms to gather and/or distribute knowledge of future topology changes.