Amir Salman Avestimehr

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2008-128

October 2, 2008

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-128.pdf

In communications, the multiuser Gaussian channel model is commonly used to capture fundamental features of a wireless channel. Over the past couple of decades, study of multiuser Gaussian networks has been an active area of research for many scientists. However, due to the complexity of the Gaussian model, except for the simplest networks such as the one-to-many Gaussian broadcast channel and the many-to-one Gaussian multiple access channel, the capacity region of most Gaussian networks is still unknown. For example, even the capacity of a three node Gaussian relay network, in which a point to point communication is assisted by one helper (relay), has been open for more than 30 years.

To make further progress, we present a linear finite-field deterministic channel model which is analytically simpler than the Gaussian model but still captures two key wireless channels: broadcast and superposition. The noiseless nature of this model allows us to focus on the interaction between signals transmitted from different nodes of the network rather than background noise of the links.

Then, we consider a model for a wireless relay network with nodes connected by such deterministic channels, and present an exact characterization of the end-to-end capacity when there is a single source and a single destination and an arbitrary number of relay nodes. This result is a natural generalization of the celebrated max-flow min-cut theorem for wireline networks. We also characterize the multicast capacity of linear finite-field deterministic relay networks when one source is multicasting the same information to multiple destinations, with the help of arbitrary number of relays.

Next, we use the insights obtained from the analysis of the deterministic model and present an achievable rate for general Gaussian relay networks. We show that the achievable rate is within a constant number of bits from the information-theoretic cut-set upper bound on the capacity of these networks. This constant depends on the number of nodes in the network, but not the values of the channel gains. Therefore, we uniformly characterize the capacity of Gaussian relay networks within a constant number of bits, for all channel parameters. For example, we approximate the unknown capacity of the three node Gaussian relay channel within one bit/sec/Hz.

Finally, we illustrate that the proposed deterministic approach is a general tool and can be applied to other problems in wireless network information theory. In particular we demonstrate its application to make progress in two other problems: two-way relay channel and relaying with side information.

Advisors: David Tse

---

BibTeX citation:

@phdthesis{Avestimehr:EECS-2008-128,
    Author= {Avestimehr, Amir Salman},
    Title= {Wireless network information flow: a deterministic approach},
    School= {EECS Department, University of California, Berkeley},
    Year= {2008},
    Month= {Oct},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-128.html},
    Number= {UCB/EECS-2008-128},
    Abstract= {In communications, the multiuser Gaussian channel model is commonly used to capture fundamental features of a wireless channel. Over the past couple of decades, study of multiuser Gaussian networks has been an active area of research for many scientists. However, due to the complexity of the Gaussian model, except for the simplest networks such as the one-to-many Gaussian broadcast channel and the many-to-one Gaussian multiple access channel, the capacity region of most Gaussian networks is still unknown. For example, even the capacity of a three node Gaussian relay network, in which a point to point communication is assisted by one helper (relay), has been open for more than 30 years. 

To make further progress, we present a linear finite-field deterministic channel model which is analytically simpler than the Gaussian model but still captures two key wireless channels: broadcast and superposition. The noiseless nature of this model allows us to focus on the interaction between signals transmitted from different nodes of the network rather than background noise of the links. 

Then, we consider a model for a wireless relay network with nodes connected by such deterministic channels, and present an exact characterization of the end-to-end capacity when there is a single source and a single destination and an arbitrary number of relay nodes. This result is a natural generalization of the celebrated max-flow min-cut theorem for wireline networks. We also characterize the multicast capacity of linear finite-field deterministic relay networks when one source is multicasting the same information to multiple destinations, with the help of arbitrary number of relays. 

Next, we use the insights obtained from the analysis of the deterministic model and present an achievable rate for general Gaussian relay networks. We show that the achievable rate is within a constant number of bits from the information-theoretic cut-set upper bound on the capacity of these networks. This constant depends on the number of nodes in the network, but not the values of the channel gains. Therefore, we uniformly characterize the capacity of Gaussian relay networks within a constant number of bits, for all channel parameters. For example, we approximate the unknown capacity of the three node Gaussian relay channel within one bit/sec/Hz. 

Finally, we illustrate that the proposed deterministic approach is a general tool and can be applied to other problems in wireless network information theory. In particular we demonstrate its application to make progress in two other problems: two-way relay channel and relaying with side information.},
}

EndNote citation:

%0 Thesis
%A Avestimehr, Amir Salman 
%T Wireless network information flow: a deterministic approach
%I EECS Department, University of California, Berkeley
%D 2008
%8 October 2
%@ UCB/EECS-2008-128
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-128.html
%F Avestimehr:EECS-2008-128