Title: On network coding in wireless ad-hoc networks

Authors: Jingyao Zhang, Pingyi Fan

Addresses: Department of Electronic Engineering, Tsinghua University, Beijing, China. ' Department of Electronic Engineering, Tsinghua University, Beijing, China

Abstract: Network coding has been shown to be an effective way to achieve the maximum flow capacity of network. In this work, we will study this technique on wireless Ad-Hoc networks. To reduce the cost and complexity, we propose a modified Ford-Fulkerson algorithm to obtain the maximum flow and encoding nodes in a network. We also find a Conflict Phenomenon in undirected networks that cannot be solved by network coding. Furthermore, we will show that the maximum flow value from a source to a destination is approximately Poisson distributed, and the number of encoding nodes is close to geometric distribution.

Keywords: network coding; maximum-flow minimum-cut; Ford-Fulkerson algorithm; encoding nodes; multicast networks; ad-hoc networks; wireless networks; random graph; network flow capacity.

DOI: 10.1504/IJAHUC.2007.012415

International Journal of Ad Hoc and Ubiquitous Computing, 2007 Vol.2 No.3, pp.140 - 148

Published online: 12 Feb 2007 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article