Reliable ad hoc routing based on mobility prediction

Jian Tang, Guoliang Xue, Weiyi Zhang

Research output: Contribution to journalReview article

11 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)71-85
Number of pages15
JournalJournal of Combinatorial Optimization
Volume11
Issue number1
DOIs
StatePublished - Feb 1 2006
Externally publishedYes

Keywords

  • Mobile ad hoc network
  • Mobility prediction
  • QoS
  • Reliable ad hoc routing

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Reliable ad hoc routing based on mobility prediction'. Together they form a unique fingerprint.

Cite this