IEICE TRANSACTIONS on Information
On Finding Maximum Disjoint Paths for Many-to-One Routing in Wireless Multi-Hop Network
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
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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://global.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 -
English
