Reliable routing in mobile ad hoc networks based on mobility prediction

Abstract — Reliability is a major issue in mobile ad hoc routing. Shortest paths are usually used to route packets in Mobile Ad hoc NETworks (MANETs). However, a shortest path may fail quickly, because some of the wireless links on the shortest path may be broken shortly after the path is established due to mobility of mobile nodes. Rediscovering routes can result in substantial data loss and communication overheads. In this paper, we consider a MANET in the urban environment. We formulate and study two optimization problems related to reliable routing in MANETs. In the Minimum Cost Duration-Bounded Path (MCDBP) routing problem, we seek a minimum cost source to destination path with duration no less than a given threshold. In the Maximum Duration Cost-Bounded Path (MDCBP) routing problem, we seek a maximum duration source to destination path with cost no greater than a given constraint. We use a waypoint graph to model the working area of a MANET and present an offline algorithm to compute a duration prediction table for the given waypoint graph. An entry in the duration prediction table contains the guaranteed worst-case duration of the corresponding wireless link. We then present an efficient algorithm which computes a minimum cost duration-bounded path, using the information provided in the dura-tion prediction table. We also present a heuristic algorithm for the MDCBP routing problem. Our simulation results show that our mobility prediction based routing algorithms lead to better network throughput and longer average path duration, compared with the shortest path algorithm. I