
For FullText 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.

Maximum Multiflow in Wireless Network Coding
Jinyi ZHOU Shutao XIA Yong JIANG Haitao ZHENG Laizhong CUI
Publication
IEICE TRANSACTIONS on Communications
Vol.E96B
No.7
pp.17801790 Publication Date: 2013/07/01
Online ISSN: 17451345
DOI: 10.1587/transcom.E96.B.1780
Print ISSN: 09168516 Type of Manuscript: PAPER Category: Fundamental Theories for Communications Keyword: multihop wireless network, multicommodity flow problem, maximum throughput, network coding, algorithm,
Full Text: PDF>>
Summary:
In a multihop wireless network, wireless interference is a crucial factor in the maximum multiflow (MMF) problem, which studies the maximum throughput between multiple pairs of sources and sinks with a link schedule to support it. In this paper, we observe that network coding could help to decrease the impact of wireless interference, and thus propose a framework to study the MMF problem for multihop wireless networks with network coding. Firstly, a network model is established to describe the new conflict relations and schedulability modified by network coding. Next, we formulate the MMF problem to compute the maximum throughput of multiple unicast flows supported by the multihop wireless network with network coding, and show that its capacity region could be enlarged by performing network coding. Finally, we show that determining the capacity region of a multihop wireless network with network coding is an NPhard problem, and thus propose a greedy heuristic algorithm, called codingfirst collecting (CFC), to determine a capacity subregion of the network. We also show that finding an optimal hyperarc schedule to meet a given link demand function is NPhard, and propose a polynomial algorithm, called codingfirst scheduling (CFS), to find an approximate fractional hyperarc schedule in the multihop wireless network with network coding. A numerical analysis of a grid wireless network and a random wireless network is presented to demonstrate the efficiencies of the CFC algorithm and the CFS algorithm based on the framework.

