|
For Full-Text PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
|
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
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E97-D
No.10
pp.2632-2640 Publication Date: 2014/10/01 Online ISSN: 1745-1361
DOI: 10.1587/transinf.2013THP0015 Type of Manuscript: Special Section PAPER (Special Section on Frontiers of Internet of Things) Category: Keyword: disjoint path, multi-routing, multi-hop, heuristic algorithm,
Full Text: PDF>>
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.
|
|