Constructing Longest Lifetime Route in Mobile Ad-hoc Networks

A mobile ad hoc network (MANET) is an autonomous system consisting of mobile hosts connected by wireless links. Every host can move in any direction at any speed and time. This leads to a dynamic topology as hosts move constantly. MANET broadcast messages to each hosts, the transmission of one host can be heard by all hosts in its communication range. If two hosts are not located in each other’s transmission range, intermediate relay hosts must be employed as bridges to build communication paths. This is the multihop characteristic of the mobile ad hoc network, for which routing decisions must be made for far-away hosts to communicate. Node mobility causes links between nodes to break frequently, thus terminating the lifetime of the routes containing those links. An alternative route has to be discovered once a link is detected as broken, incurring extra route discovery overhead and packet latency. Traditionally route discovery has been done using flooding based approaches, which sometimes leads to broadcast storm problem. In this paper, we study the problem of how to construct a route with the longest lifetime for any given one-to-one communication request as a solution to link breakage in MANET. An algorithm is proposed with time complexity of O(m+ nlog n) , where n is the number of the nodes and m is the number of the links. The proposed algorithm complexity is similar to that of the Dijkstra algorithm implemented using Fibonacci heap.