|
Overview
Motivation
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
Observation
Wireless
ad hoc networks are inherently highly redundant networks. Fault-free paths can
be found for end-to-end delivery, even misbehaving nodes exist inside the
network. Yet current ad hoc routing protocols can not effectively utilize such
path to route packets, as shown in the following figure.
Fault-Tolerant Routing Problem
Based
on this observation, we investigate the problem of fault-tolerant
routing in ad hoc networks. The basic idea is to explore the redundancy
of ad hoc networks via routing. The goal is to maximally maintain the
routing performance (high packet delivery ratio, low delay) in the presence of
misbehaving nodes. The challenge is to balance the routing performance with
its overhead.
Assumption
We make
the following assumptions
1.
Nodes may exhibit Byzantine faulty behavior in routing and forwarding, but
there are no denial of service attack to the MAC and physical layer.
2.
Source and destination nodes of the end-to-end data delivery, which requires
fault-tolerant routing service, are both well-behaved nodes. And they have
priori trust relationship.
Problem Formulation
We
formulated two fault-tolerant routing problems
 Assured fault-tolerant routing
Best-effort fault-tolerant routing
|
