Multipath Routing in Wireless Ad Hoc Networks
Ad Hoc networks present a unique challenge to network services which require
quality-of-service (QoS) guarantees. Two well-known problems in ad hoc networks
are the lack of reliable packet delivery due to interference and movement of
nodes and limited node lifetime due to small battery size.
We propose a strategy for reliable packet transmission that uses path
diversification to tackle the two challenges of ad hoc networks. In path
diversification, each packet is decomposed into a number of smaller packets,
called segments, and the segments are deployed over multiple parallel
paths. To increase reliability, path diversification uses an erasure code to
generate extra parity segments for each packet. Destination can recover the
original packet when it receives a certain number of segments. We show that path
diversification allows us to provide guaranteed QoS in ad hoc networks, without
changing the existing routing or MAC layer protocols. At the same time, path
diversification performs load balancing in the network
and increases the lifetime of the network by distributing the cost of packet
transmissions among nodes from different paths.
The main objective of this research is to show that path diversification can
increase reliability in an ad hoc network. We address this issue in two steps.
First, we assume that no prior information about the performance metrics along
the paths is available. In such a case, the transmitter simply distributes data
uniformly over parallel paths. We call this case blind path diversification.
We show that blind path diversification outperforms single-path transmission.
Second, we assume that some performance metrics about the parallel paths are
available at the transmitter. These metrics are provided by a feedback from the
network to the source or by some form of probing initiated by the source. We
assume that the metrics are updated periodically. These metrics can be used to
optimally assign the segments into the available paths. For such a case, we will
discuss three different optimization problems: (1) Maximize reliability;
(2) Maximize efficiency subject to fixed reliability, and (3) Minimize energy
consumption. The source node uses the optimization algorithms associated with
P1-P3 to periodically change load on each path.
Further Reading:
[1] P. Djukic and S. Valaee, “Reliable Packet Transmission in Multipath Routed Wireless Networks”, accepted for publication in IEEE Trans. on Mobile Computing. [pdf]
[2] P. Djukic and S. Valaee, “Minimum Energy Fault Tolerant Sensor Networks”, in the proceedings of IEEE GLOBECOM Wireless Ad hoc and Sensor Networks Workshop, Dec 2004. [pdf]
[3] P. Djukic and S. Valaee, “Minimum Energy Reliable Multipath Ad Hoc Networks”, in the proceedings of 22nd Biennial Symposium in Communications, June 2004. [pdf]
[4] P. Djukic, "Optimum Resource Allocation in Multipath Ad Hoc Networks", MASc Thesis, University of Toronto, 2003. [pdf]