Providing fault-tolerant Ad hoc routing service in adversarial environments

Yuan Xue, Klara Nahrstedt

Research output: Contribution to journalReview articlepeer-review


Most existing designs of ad hoc networks are based on the assumption of non-adversarial environments, where each node in the network is cooperative and well-behaved. When misbehaving nodes exist in the network, the performance of current routing protocols degrades significantly. Since ad hoc networks, consisting of autonomous nodes, are open and distributed in nature, maintaining a fault-free network environment is extremely difficult and expensive. In this paper, we propose a new routing service named best-effort fault-tolerant routing (BFTR). The design goal of BFTR is to provide packet routing service with high delivery ratio and low overhead in presence of misbehaving nodes. Instead of judging whether a path is good or bad, i.e., whether it contains any misbehaving node, BFTR evaluates the routing feasibility of a path by its end-to-end performance (e.g. packet delivery ratio and delay). By continuously observing the routing performance, BFTR dynamically routes packets via the most feasible path. BFTR provides an efficient and uniform solution for a broad range of node misbehaviors with very few security assumptions. The BFTR algorithm is evaluated through both analysis and extensive simulations. The results show that BFTR greatly improves the ad hoc routing performance in the presence of misbehaving nodes.

Original languageEnglish (US)
Pages (from-to)367-388
Number of pages22
JournalWireless Personal Communications
Issue number3-4 SPEC.ISS.
StatePublished - Jun 2004


  • Ad hoc networks
  • Misbehaving node
  • Routing protocol

ASJC Scopus subject areas

  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Providing fault-tolerant Ad hoc routing service in adversarial environments'. Together they form a unique fingerprint.

Cite this