On Finding Maximum Disjoint Paths for Many-to-One Routing in Wireless Multi-Hop Network

Bo Liu, Junzhou Luo, Feng Shan, Wei Li, Jiahui Jin, Xiaojun ShenIEICE 2014 · DOI

Abstract

Provisioning multiple paths can improve fault tolerance and transport capability of multi-routing in wireless networks. Disjoint paths can improve the diversity of paths and further reduce the risk of simultaneous link failure and network congestion. In this paper we first address a many-to-one disjoint-path problem (MOND) for multi-path routing in a multi-hop wireless network. The objective of this problem is to maximize the minimum number of disjoint paths of every source to the destination. We prove that it is NP-hard to obtain k disjoint paths for every source when k ≥ 3. To solve this problem efficiently, we propose a heuristic algorithm called TOMAN based on network flow theory. Experimental results demonstrate that it outperforms three related algorithms.
BibTeX
@inproceedings{liu2014finding,
  author = {Bo Liu and Junzhou Luo and Feng Shan and Wei Li and Jiahui Jin and Xiaojun Shen},
  title = {{On Finding Maximum Disjoint Paths for Many-to-One Routing in Wireless Multi-Hop Network}},
  booktitle = {IEICE},
  year = {2014},
  doi = {10.1587/transinf.2013thp0015},
}
Figure