Reliable Ad Hoc Routing Based on Mobility Prediction |
| |
Authors: | Jian Tang Guoliang Xue Weiyi Zhang |
| |
Institution: | (1) Department of Computer Science and Engineering, Arizona State University, Tempe, AZ, 85287-8809 |
| |
Abstract: | Reliability is a very important issue in Mobile Ad hoc NETworks (MANETs). Shortest paths are usually used to route packets
in MANETs. However, a shortest path may fail quickly, because some of the wireless links along a shortest path may be broken
shortly after the path is established due to mobility of mobile nodes. Rediscovering routes may result in substantial data
loss and message exchange overhead. In this paper, we study reliable ad hoc routing in the urban environment. Specifically,
we formulate and study two optimization problems. In the minimum Cost Duration-bounded Path (CDP) 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 (DCP) routing problem, we seek a maximum duration source to destination path with cost no greater than a given threshold.
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 duration prediction table. We also present a heuristic algorithm for the DCP routing
problem. In addition, we show that the proposed prediction and routing schemes can be easily applied for designing reliable
ad hoc routing protocols. Simulation results show that our mobility prediction based routing algorithms lead to higher network
throughput and longer average path duration, compared with the shortest path routing.
This research was supported in part by ARO grant W911NF-04-1-0385 and NSF grant CCF-0431167. The information reported here
does not reflect the position or the policy of the federal government. |
| |
Keywords: | Reliable ad hoc routing Mobility prediction Mobile ad hoc network QoS |
本文献已被 SpringerLink 等数据库收录! |
|