Maximum Multiflow in Wireless Network Coding

Jinyi ZHOU
Shutao XIA
Haitao ZHENG
Laizhong CUI

IEICE TRANSACTIONS on Communications   Vol.E96-B    No.7    pp.1780-1790
Publication Date: 2013/07/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E96.B.1780
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Fundamental Theories for Communications
multihop wireless network,  multi-commodity flow problem,  maximum throughput,  network coding,  algorithm,  

Full Text: PDF>>
Buy this Article

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 NP-hard problem, and thus propose a greedy heuristic algorithm, called coding-first 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 NP-hard, and propose a polynomial algorithm, called coding-first 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.