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 SHEN

doi:10.1587/transinf.2013THP0015

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 SHEN

Full Text Views

0

Share
Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E97-D No.10 pp.2632-2640

Publication Date: 2014/10/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2013THP0015

Type of Manuscript: Special Section PAPER (Special Section on Frontiers of Internet of Things)

Category

Authors

Bo LIU
  Southeast University
Junzhou LUO
  Southeast University
Feng SHAN
  Southeast University
Wei LI
  Southeast University
Jiahui JIN
  Southeast University
Xiaojun SHEN
  University of Missouri

Keyword

disjoint path, multi-routing, multi-hop, heuristic algorithm

Cite this

Copy

Bo LIU, Junzhou LUO, Feng SHAN, Wei LI, Jiahui JIN, Xiaojun SHEN, "On Finding Maximum Disjoint Paths for Many-to-One Routing in Wireless Multi-Hop Network" in IEICE TRANSACTIONS on Information, vol. E97-D, no. 10, pp. 2632-2640, October 2014, doi: 10.1587/transinf.2013THP0015.
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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.2013THP0015/_p

Copy

@ARTICLE{e97-d_10_2632,
author={Bo LIU, Junzhou LUO, Feng SHAN, Wei LI, Jiahui JIN, Xiaojun SHEN, },
journal={IEICE TRANSACTIONS on Information},
title={On Finding Maximum Disjoint Paths for Many-to-One Routing in Wireless Multi-Hop Network},
year={2014},
volume={E97-D},
number={10},
pages={2632-2640},
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.},
keywords={},
doi={10.1587/transinf.2013THP0015},
ISSN={1745-1361},
month={October},}

Copy

TY - JOUR
TI - On Finding Maximum Disjoint Paths for Many-to-One Routing in Wireless Multi-Hop Network
T2 - IEICE TRANSACTIONS on Information
SP - 2632
EP - 2640
AU - Bo LIU
AU - Junzhou LUO
AU - Feng SHAN
AU - Wei LI
AU - Jiahui JIN
AU - Xiaojun SHEN
PY - 2014
DO - 10.1587/transinf.2013THP0015
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E97-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 2014
AB - 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.
ER -