Guaranteed on-demand discovery of node-disjoint paths in ad hoc networks

In recent years, the low cost and abundance of WLAN products has led to the deployment of self-configuring multihop ad hoc networks. Multipath routing has been increasingly studied to improve network reliability and throughput. However, no existing work guarantees discovery of node-disjoint paths when they exist, which limits their applicability in real networks. This paper presents a theoretical framework that establishes the equivalence between multipath discovery and flow network assignment. This equivalence is used to guarantee the on-demand discovery of an arbitrary number of node-disjoint paths between a pair of nodes as long as they exist. We also present an example protocol that integrates the theoretical framework with the Dynamic Source Routing (DSR) protocol to find two node-disjoint paths, which can be easily extended to finding k node-disjoint paths. Analysis of the example protocol demonstrates a good tradeoff between complexity and capability, particularly when compared with existing on-demand multipath routing protocols. Our simulation data shows the effectiveness of the discovered paths.