مسیریابی مطمئن در تلفن همراه برای شبکه مبتنی بر پیش بینی تغییر پذیری 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 durationbounded path, using the information provided in the duration 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. INTRODUCTION The Mobile Ad hoc NETwork (MANET) is different from traditional wireless networks in many ways. One of the basic differences is that a MANET is a multihop wireless network, i.e., a routing path is composed of a number of intermediate mobile nodes and wireless links connecting them. Since nodes can move at any Research supported in part by ARO grant W911NF-04-1-0385, NSF grants CCF-0431167 and a seed grant from CEINT. The information reported here does not reflect the position or the policy of the federal government. time, wireless links are prone to be broken. Any link break along an established routing path will lead to a path failure. A shortest path may fail sooner than another path connecting a given source and destination pair. Frequent routing discovery is costly and inefficient. Moreover, shortest path routing can not support many Quality of Service (QoS) connection requests when the path duration is a requirement. For example, a video stream could be required to be transferred from node s to node t without any interruption for 100 seconds in a multimedia application. Instead of shortest paths, more durable paths or paths with duration guarantees are preferred to be used for routing packets. Originally, the MANET is proposed for military applications in the battlefield. However, future MANETs could be deployed in various environments. the city-wide MANET begins to attract research attentions recently ([1]) because of its application potential. Different from movements in the battlefield, movements in the city are highly restricted by roadways, i.e., the following movement rules must be obeyed: a vehicle or person can only move along roads, turn or stay at intersections. In addition, the driving speed of a vehicle on a specific road segment cannot exceed its prescribed speed limit. A similar mobility pattern is described in the Manhattan mobility model ([1]). Therefore, it is possible for us to make a relatively accurate prediction for mobility of mobile nodes, which will give a good insight for finding reliable routing paths. In this paper, we consider a MANET in the urban environment. As mentioned before, we are interested in QoS connection requests with duration requirements. In addition, we are also interested in finding a path whose duration is as long as possible but whose cost is as low as possible. We formulate two optimization problems for reliable routing in MANETs. They are the Minimum Cost DurationBounded Path (MCDBP) routing problem and the Maximum Duration Cost-Bounded Path (MDCBP) routing problem. We introduce the waypoint graph to model the 0-7803-8815-1/04/$20.00 ©۲۰۰۴ IEEE 466 city map and present a prediction algorithm to compute a duration table for the given waypoint graph. Each entry in the table gives the worst-case duration of a corresponding wireless link, i.e., at least how long it can last. Based on the prediction table, we present an algorithm to solve the (MCDBP) problem optimally and a heuristic algorithm for the (MDCBP) problem. The rest of this paper is organized as follows. We discuss related work in Section II. We formally define our problems and some notations in Section III. We describe our prediction and routing algorithms in Section IV. We present our simulation results in Section V. We conclude the paper in Section VI.