Maximum Multiflow in Wireless Network Coding

Jinyi ZHOU; Shutao XIA; Yong JIANG; Haitao ZHENG; Laizhong CUI

doi:10.1587/transcom.E96.B.1780

Maximum Multiflow in Wireless Network Coding

Jinyi ZHOU, Shutao XIA, Yong JIANG, Haitao ZHENG, Laizhong CUI

Full Text Views

0

Cite this

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

Publication: IEICE TRANSACTIONS on Communications Vol.E96-B No.7 pp.1780-1790

Publication Date: 2013/07/01

Publicized

Online ISSN: 1745-1345

DOI: 10.1587/transcom.E96.B.1780

Type of Manuscript: PAPER

Category: Fundamental Theories for Communications

Authors

Jinyi ZHOU
  Tsinghua University
Shutao XIA
  Tsinghua University
Yong JIANG
  Tsinghua University
Haitao ZHENG
  Tsinghua University
Laizhong CUI
  Shenzhen University

Keyword

multihop wireless network, multi-commodity flow problem, maximum throughput, network coding, algorithm

Cite this

Copy

Jinyi ZHOU, Shutao XIA, Yong JIANG, Haitao ZHENG, Laizhong CUI, "Maximum Multiflow in Wireless Network Coding" in IEICE TRANSACTIONS on Communications, vol. E96-B, no. 7, pp. 1780-1790, July 2013, doi: 10.1587/transcom.E96.B.1780.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.E96.B.1780/_p

Copy

@ARTICLE{e96-b_7_1780,
author={Jinyi ZHOU, Shutao XIA, Yong JIANG, Haitao ZHENG, Laizhong CUI, },
journal={IEICE TRANSACTIONS on Communications},
title={Maximum Multiflow in Wireless Network Coding},
year={2013},
volume={E96-B},
number={7},
pages={1780-1790},
abstract={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.},
keywords={},
doi={10.1587/transcom.E96.B.1780},
ISSN={1745-1345},
month={July},}

Copy

TY - JOUR
TI - Maximum Multiflow in Wireless Network Coding
T2 - IEICE TRANSACTIONS on Communications
SP - 1780
EP - 1790
AU - Jinyi ZHOU
AU - Shutao XIA
AU - Yong JIANG
AU - Haitao ZHENG
AU - Laizhong CUI
PY - 2013
DO - 10.1587/transcom.E96.B.1780
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E96-B
IS - 7
JA - IEICE TRANSACTIONS on Communications
Y1 - July 2013
AB - 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.
ER -