Deterministic Network Model Revisited: An Algebraic Network Coding Approach

Details Deterministic Network Model Revisited: An Algebraic Network Coding Approach Deterministic Network Model Revisited: An Algebraic Network Coding Approach

2011-03-05

arxiv.org/abs/1103.0999v2

Computer Science

Information Theory

19 pages, 19 figures, submitted to Transactions on Information Theory (removed figures that were mistakenly included at the en

Scientific paper

The capacity of multiuser networks has been a long-standing problem in information theory. Recently, Avestimehr et al. have proposed a deterministic network model to approximate multiuser wireless networks. This model, known as the ADT network model, takes into account the broadcast nature of wireless medium and interference. We show that the ADT network model can be described within the algebraic network coding framework introduced by Koetter and Medard. We prove that the ADT network problem can be captured by a single matrix, and show that the min-cut of an ADT network is the rank of this matrix; thus, eliminating the need to optimize over exponential number of cuts between two nodes to compute the min-cut of an ADT network. We extend the capacity characterization for ADT networks to a more general set of connections, including single unicast/multicast connection and non-multicast connections such as multiple multicast, disjoint multicast, and two-level multicast. We also provide sufficiency conditions for achievability in ADT networks for any general connection set. In addition, we show that random linear network coding, a randomized distributed algorithm for network code construction, achieves the capacity for the connections listed above. Furthermore, we extend the ADT networks to those with random erasures and cycles (thus, allowing bi-directional links). In addition, we propose an efficient linear code construction for the deterministic wireless multicast relay network model. Avestimehr et al.'s proposed code construction is not guaranteed to be efficient and may potentially involve an infinite block length. Unlike several previous coding schemes, we do not attempt to find flows in the network. Instead, for a layered network, we maintain an invariant where it is required that at each stage of the code construction, certain sets of codewords are linearly independent.

Affiliated with

Also associated with

No associations

Rating

Deterministic Network Model Revisited: An Algebraic Network Coding Approach does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Deterministic Network Model Revisited: An Algebraic Network Coding Approach, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deterministic Network Model Revisited: An Algebraic Network Coding Approach will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-8590