|
MSRI Workshop: Mathematics of Relaying and Cooperation in Communication Networks
April 10-12, 2006
| Talk Abstracts |
| Monday, April 10
|
Edward van der Meulen, Leuven
Abstract:
I will first describe the historical context of the work I did
on the relay channel in the period 1965-1968. Then I will
present the main results of my 1968 Berkeley Ph.D. thesis and
my 1971 article in the Advances of Applied Probability. I will
put these early results in perspective with the more advanced
results obtained later by other authors. Next I will present
some results, obtained around 1990, on the deterministic relay
channel concerning capacity calculation and code
construction. I will conclude with a discussion of the almost
Gaussian degraded relay channel.
Slides [pdf]
|
Elza Erkip, Brooklyn Poly
Abstract:
In this talk, we first investigate the diversity-multiplexing tradeoff
for cooperative wireless networks. We study various network
configurations such as multiple relays, multiple source/destination
pairs, multiple antenna users, different user locations, as well as
the performance achievable by different relaying strategies. We are
particularly interested in whether the virtual multi-input
multi-output (MIMO) system created by cooperation mimics a physical
MIMO. We next show how the diversity-multiplexing tradeoff can be
utilized for efficient transmission of an analog source over a slowly
fading cooperative wireless channel. The performance metric is the
distortion exponent, which is the signal-to-noise exponent of the
average end-to-end distortion caused by compression and channel
errors. We discuss source and channel coding strategies that compress
the source signal in multiple layers and then transmit these layers
either successively in time or superimpose them for simultaneous
transmission. We also illustrate the benefits of unequal error
protection provided by cooperation.
Joint work with Deniz Gunduz and Melda Yuksel.
Slides [ppt]
|
Vahid Tarokh, Harvard
Abstract:
Elements/clusters of a sensor network operating on the same band
canoperate using three different paradigms: i) Competition: This is
information theoretically casted in the framework of interference
channels. ii) Collaboration: Silent transmitters/receivers can help
active transmitters/receivers in the transmission/reception of their
messages, but have to extract this message from the underlying
transmission or by other methods, and iii) Cognitive Radio Transmission:
Some devices extract the message of other transmitters from their
signals or by other methods, and use it tominimize interference
from/to their own transmitted signals. Competition has been
well-studied in the literature. Collaboration has been less studied and
Cognitive Radio Transmission has not been much studied. For the case of
collaboration, we demonstrate that most of the MIMO space-time gain can
also be achieved through collaborative communications with
single-antenna/multiple-antenna nodes when there is one receiving
agent. In particular, for the single antenna case, we consider
communication to take place between clusters of nearby nodes. We show
the existence of collaborative codes for communications for which the
intra-cluster negotiation penalty is in principle small and almost all
the diversity gain of traditional space-time codes may be realized. For
example, for a single transmitter node with two collaborators and one
receiver node, if the collaborators have as little as 10 dB pathloss
advantage over the receiver, the penalty for collaboration
over traditional space-time systems is negligible. For the cognitive
radio transmission, we consider a channel defined as an
n-transmitter, m-receiver interference channel in which sender i
obtains (causally or uncasually) the messages senders 1 through i-1
plan to transmit. The two sender, two receiver case is considered. In
this scenario, one user, a cognitive radio, obtains (genie assisted,or
causally) knowledge of the data to be transmitted by the other
user. The cognitive radio may then simultaneously transmit over the
same channel, as opposed to waiting for an idle channel as in a
traditional cognitive radio channel protocol. Dirty-paper coding and
ideas from achievable region constructions for the interference channel
are used, and an achievable region for the cognitive radio channel is
computed. It is shown that in the Gaussian case, the described
achievable region approaches the upper bounds provided by the 2x2
Gaussian MIMO broadcast channel, and an interference-free
channel. Finally, we demonstrate/discuss the implementation of these
ideas on an SDR platform.
This is a joint work with Natasha Devroye,
Patrick Mitran, Hideki Ochiai (Harvard) and John Chapin's Team (Vanu
Systems).
Slides [ppt]
|
Junshan Zhang, Arizona State
Abstract:
A sensory relay network consists of one source node, one destination
node and many relay nodes. We investigate the achievable rates and the
scaling laws of power- constrained sensory relay networks in the
wideband regime, assuming that relay nodes have no a priori knowledge
of channel state information.
We first study narrowband relay networks in the low SNR regime. We
examine the achievable rates in the joint asymptotic regime of the
number of relay nodes n, the channel coherence interval and the SNR
per link. We propose an information relaying scheme, namely
amplify-and-forward (AF) with network training, in which each relay
node carries out channel estimation and then uses AF relaying to relay
data. We provide an equivalent source-to-destination channel model,
and characterize the corresponding achievable rate. Our findings show
that when the transmission energy in each fading block is bounded
below, the achievable rate has the same scaling order as in coherent
relaying, thus enabling us to characterize the scaling law. We then
generalize the study to power-constrained wideband relay networks,
where frequency-selective fading is accounted for. Again, the focus is
on the achievable rates by using AF with network training for
information relaying. In particular, we examine the scaling behavior
of the achievable rates corresponding to two power allocation policies
applied at relay nodes, namely, a simple equal power allocation policy
and the optimal power allocation policy. We identify the conditions
under which the scaling law of the wideband relay networks can be
achieved by both power allocation policies. Somewhat surprising, our
findings indicate that these two power allocation policies result in
achievable rates of the same scaling order, and the scaling law can be
characterized under the condition that the energy per fading block per
subband is bounded below and that the bandwidth W is sub-linear in n.
We will also talk about our ongoing work on the tradeoff between
sensing and communications, and discuss cooperative routing in
multi-hop relay networks.
Slides [ppt]
|
Tony Ephremides, Maryland
Abstract:
In this presentation we are demonstrating two forms of user
cooperation that is happening at the MAC and the Routing Layer
respectively. One utilizes idle periods in a TDMA schedule-based
protocol that utilizes a relay and the other one is based on a
collaborative routing strategy in a sensor network deployed for event
detection. They both are somewhat different than usual forms of
cooperation that have been considered mostly at the physical layer,
but they have similar performance improvement results and indicate
that cooperation can be exploited in diverse , but always beneficial,
ways.
Slides [ppt]
|
Edmund Yeh, Yale
Abstract:
We give a model for cooperative communication in a parallel relay
network that includes the stochastic arrival of packets and queueing.
For this model we provide a throughput optimal network control policy
which stabilizes the network for any arrival rate in its stability
region. This policy is a generalization of maximum differential
backpressure policies which takes into account the potential cooperative
gains in the network. Generalizations of our model are discussed.
This is joint work with Randall Berry.
Slides [pdf]
|
David Tse, UC-Berkeley
Abstract:
In wireless fading channels, a primary benefit of
cooperative communication is to provide spatial diversity without the
need of multiple antennas at each of the nodes. In such a setting,
the performance limit is characterized by the outage capacity of
the underlying relay fading channel. We compute the outage capacity in
the low SNR regime and present a simple relaying scheme that achieves
it. The basic features of this scheme are: 1) analog amplify and
forward, 2) low duty cycle flashy transmission, and 3) non-coherent
energy combining at the destination.
This is joint work with Amir Salman Avestimehr.
Slides [ppt]
|
Venugopal V. Veeravalli
Abstract:
An orthogonal relay channel model is studied, where the
source transmits to the relay and destination in one channel, and the
relay transmits to the destination in an orthogonal channel. Separate
power constraints are assumed at the source and relay. The three links
are subject to fading, and the fading state information is assumed to
be known at both the transmitter and receiver. The source and relay
can hence allocate their power adaptively according to the
instantaneous channel state information. An achievable rate for this
model is derived, and is optimized over the power allocation at the
source and relay. This optimization is a max-min problem. A general
technique for solving this max-min problem is introduced and applied to
derive the optimal power allocation. The analysis is extended to the
joint optimization of power and channel resource (time and
bandwidth) allocations. In these scenarios, the maximum capacity of the
channel (optimized over all possible power and channel resource
allocations) is obtained for some special cases.
Joint work with Yingbin Liang
Slides [pdf]
|
Gregory Wornell
Abstract:
We consider the problem of multicast transmission (one source,
multiple destinations) in wireless networks, and develop a meaningful
notion of Shannon capacity in slow fading multipath-rich environments
when the number of nodes (network size) is large. We further show
that at any desired signal-to-noise ratio (SNR), capacity is achieved
via a simple two-phase cooperative network protocol. Finally, we
introduce the notion of a network ``scaling exponent'' to quantify the
rate of decay of error probability with network size as a function of
the targeted fraction of the capacity.
Joint work with Ashish Khisti and Uri Erez.
Slides [pdf]
|
| Tuesday, April 11
|
Abbas El Gamal, Stanford
Abstract:
Basic results on the capacity of discrete-memoryless relay channels
with and without delay are reviewed. These will include: the cut-set
bound, partial decode and forward coding, side-information coding, and
instantaneous coding. I will also review results on the capacity of
various AWGN relay channel models, including using linear relaying. I
will end my presentation with a discussion of possible directions for
future research.
Slides [pdf]
|
Urbashi Mitra, USC
Abstract:
There has been significant activity in answering information and
communication theoretic questions for wireless networks. A largely
ignored arena is that of underwater networks. Furthermore, while
there has been focus on establishing methods for point-to-point links
in underwater systems -- the underwater communications network has
been not been rigorously treated. Underwater communication channels
are characterized by very significant delay spreads (often on the
order of hundreds of symbols), very sparse multipath, transmission
distance dependent effective bandwidth, and high Doppler. In this
talk, we review several analyses and algorithm developments for the
underwater acoustic communication network. We show how the underwater
channel features impact designs for cooperative communication systems
and sensor networks where distributed space-time coding, equalization,
multihopping/relaying are considered.
Slides [pdf]
|
Sriram Vishwanath, UT-Austin
Abstract:
An achievable region for the discrete-memoryless multiple access
channel (DM-MAC) with correlated sources and feedback is characterized,
based ona modification of the Cover-El Gamal-Salehi approach for
DM-MAC without correlated sources. Two different sufficient conditions
for this region to be the optimal joint source-channel coding region
are provided alongw ith an example scenario where each condition holds.
The achievable region is subsequently generalized to the case of
discrete-memoryless interference networks with feedback. The special
case of Gaussian multiple with correlated sources and feedback is also
investigated, with a modified Schalkwijk-Kailath coding scheme used to
devise an achievableregion for the system.
Slides [ppt]
|
Liang-Liang Xie, Waterloo
Abstract:
A multi-relay scheme is developed for networks with multiple
sources. By this scheme, each source is sent to its destination via a
multi-relay route, and the multiple multi-relay routes from the
multiple sources can operate at the same time even if they intersect
with each other, in the same spirit of the code-division
multiple-access (CDMA). It is found that in the generalization to
multiple sources, the backward decoding achieves higher rates than the
sliding-window decoding. Potential applications of this scheme in
sensor networks are discussed, where capacity results in certain
scenarios are established.
Joint work with P.R. Kumar
Slides [ppt]
|
Helmut Boelcskei, ETH
Abstract:
We study large wireless networks and show that the fading nature of
the network leads to fundamentally new effects not present in the
Gupta-Kumar model. In particular, it is demonstrated that the network
can be made to "crystallize" in the large number of nodes limit. We
analyze the impact of protocols, cooperation between nodes and
processing at the individual nodes on the crystallization effect and
describe a framework for characterizing the rate at which the network
crystallizes.
Slides [pdf]
|
Randall Berry, Northwestern
Abstract:
In this talk we study wireless networks in which each
node may have its own traffic to send. While cooperation may
improve global performance, all users may not benefit from these gains
and so not have an incentive to cooperate. One approach for modeling
such issues is through cooperative game theory. We review some of the
the basic ideas of this theory and present some simple game-theoretic
models for cooperation and relaying in wireless networks.
Slides [pdf]
|
Babak Hassibi, Caltech
Abstract:
We will discuss some capacity results for two classes of wireless
networks. The first are wireless erasure networks where links are
possibly correlated erasure channels. Such models may be appropriate for
systems where communication is packet-based and where some form of error
correction is used to detect packet erasures. For problems with single
source and multiple destinations all requiring the same information, we
obtain an exact capacity result independent of the network topology. We
will discuss interpretations and implications of the result, as well as
connections to areas such as network coding.
The second are so-called random wireless networks where each link is a
fading channel drawn iid from a given distribution. Such models may be
appropriate for networks of small physical size where the strength of a
connection depends more on a random event (such as the existence of an
obstacle), rather than on the distance between the transmitter and
receiver. These networks are closely related to the classical Erdos
random graph, and we show achievable throughputs that scale almost
linearly in the number of nodes, a significant improvement over results
obtained from the geometric Gupta-Kumar models. We discuss scenarios
where such models may be reasonable, as well a multi-scale network model
where the fading coefficients are iid at a local scale and obey a
path-loss model at a global scale.
Slides [pdf]
|
| Wednesday, April 12, 12-2:30
|
Frans M.J. Willems, Eindhoven
Abstract:
We first discuss the capacity regions for various communication
situations in which one or both encoders for a multiple-access channel
crib from the other encoder and learn the channel input(s) (to be)
emitted by this encoder. Most of the achievability proofs for cribbing
encoders hinge upon the concept of backward decoding. Also the notion
of Shannon strategies seems to be of crucial importance. After having
reviewed these concepts we discuss a recent development related to
cribbing encoders that corresponds to the relay-channel without delay.
Slides [pdf]
|
Ashutosh Sabharwal, Rice
Abstract:
Most networks allow bi-directional communication, i.e., allowing
receivers to send messages back to the transmitters but with the
feedback link sharing the same bandwidth as the forward link. In this
talk, we will study multiple access channels with bi-directional
links and explore the role of receiver participation.
Slides [ppt]
|
Anders Host-Madsen, Hawaii
Abstract:
In this presentation we consider cooperative communications in the low
power regime. The low power regime can be defined as the limit where
the power spectral density of the transmitted signal goes to zero,
which can be achieved by either letting the bandwidth converge towards
infinity or letting the rate converge towards zero. There are a number
of advantages to communications in the low power regime: in a
non-cooperative channel the energy consumption (energy per bit) is
minimized in the low power regime, the communication is
interference-free, the modulation is simple, and the communication is
covert. In the cooperative channel, energy per bit is not necessarily
minimized in the low power regime, but it is close to the minimum, as
will be shown, and the other advantages remain. This makes low-power
communications ideal for applications like sensor networks. In the
presentation, we develop capacity for low power communications for a
number of channels. We also consider coding methods that are close to
capacity. In particular, we consider two block Markov coding schemes,
namely, multiplexed coding and superposition coding schemes. The
multiplexed coding using fully multiplexed (FMP) codes, which
outperforms the superposition coding theoretically, however,
is difficult to implement with practical error-correction codes. We
then introduce a partially multiplexed (PMP) coding scheme for the
coderate R < 1/2, and propose a PMP code design method using
irregular repeat accumulate (IRA) codes. The design method can be
extended to build the low-rate PMP codes using irregular repeat zigzag
Hadamard (IRZH) codes. The outage analysis shows that the cooperation
schemes provide significant gains over the non-cooperative MAC in
low-powerregime. Also, the PMP-IRZH coding performs only 0.5 dB away
from low-power outage capacity for multiplexed coding.
Joint work with Zigui
Yang (Hawaii), Guosen Yue (NEC Labs), and Xiaodong Wang (Columbia).
Slides [ppt]
|
Andrea Goldsmith, Stanford
Abstract:
We consider fundamental capacity limits in wireless networks where
nodes can cooperate in transmission and reception. We propose novel
cooperation techniques that approach the capacity bounds, including
virtual MIMO transmission, relaying, and conferencing. The optimal
cooperation strategy is cross-layer in nature and depends on the
network topology, the channel SNR, and the channel side information
available at the nodes. Extending cooperation ideas to multiuser
channels, multihop networks, and cooperative compression is also
discussed.
Slides [ppt]
|
Mehul Motani, Singapore
Abstract:
In this talk, we will discuss coding strategies for the general three-
node relay channel. We start with the well known achievability results
of Cover and El Gamal, which superimpose decode-and-forward (DF) and
compress-and-forward (CF). We then describe several new strategies
which also superimpose DF and CF, and make use of sequential and
simultaneous backward decoding. The rates with the simultaneous
backward decoding strategy are shown to contain those of Cover and El
Gamal.
Slides [pdf]
|
Behnaam Aazhang, Rice
Abstract:
We propose a scheme to implement half-duplex decode-and-forward
and estimate-and-forward relaying. We will first present an achievable
rate for the estimate-and-forward protocol in the context of
half-duplex relaying. Guided by the coding scheme for the achievable
rates, we propose a practically implementable scheme for
decode-and-forward and estimate-and-forward relaying. We introduce
several simplifications to facilitate implementation. We will also
present some simulation results on the performance of the codes in a
relay channel.
Joint work with Arnab Chakrabarti, Alexandre de Baynast, and Ashutosh Sabharwal.
Slides [ppt]
|
Massimo Franceschetti, UC-San Diego
Abstract:
It is well known that the throughput capacity of wireless networks
scales poorly as the network size increases and all nodes wish to
communicate simultaneously. In this talk we focus on the scenario when
a constant density of nodes is randomly scattered in an increasing
area and only two nodes wish to communicate at any given time, while
all others can be used as possible relays. Using a percolation
argument and a simple TDMA construction it is shown that in this case
any pair, among an arbitrarily large fraction of the nodes, can
maintain a constant bit-rate. On the other hand, an ergodic argument
shows that this fraction can never be one, irrespective of the nodes
cooperation strategies. Namely, there always exists a positive
fraction of poorly connected nodes, among any two of which the rate
must tend to zero as network size tends to infinity.
Stated informally, the conclusion is that in a wireless network it is not
possible to have full-connectivity (i.e. a non-vanishing rate among any pair
of nodes), but it is indeed possible to have almost-full connectivity (i.e. a
non-vanishing rate among almost any pair of nodes). The constant rate in
this latter case clearly depends on the fraction of connected nodes.
This is joint work with Olivier Dousse and Patrick Thiran.
Slides [ppt]
|
Piyush Gupta, Bell Labs
Abstract:
Recent efforts in analyzing the capacity of wireless networks
have focused on modeling the broadcast nature of the medium but
not interference. This is due to the challenging nature of studying the
latter -- for even simple network configurations, such as
the single-relay channel or the interference channel, the
capacity regions are not yet known. Thus we study a simplified
model, where the network operates over a finite field, but
which incorporates both the broadcast and interference aspects of
the medium, as well as allows for fading. For this model, we obtain an
upper bound on the single-source multicast capacity, and present a
network coding strategy that achieves rates arbitrarily close to the
upper bound under uniform i.i.d. fading. We further show that channel
fading in conjunction with network coding can lead to large gains in
the multicast capacity over no fading.
Joint work with Sandeep Bhadra and Sanjay Shakkottai (UT-Austin).
Slides [pdf]
|
Hesham El Gamal, Ohio State
Abstract:
We adopt a game theoretic approach for the analysis of wireless
channels where the users are modeled as rational and selfish players
interested in maximizing the utilities they obtain from the network.
In the fading multiple access channel, we first show that the sum-rate
optimal point on the boundary of the capacity region is the unique
Nash Equilibrium of the corresponding water-filling game. By
introducing the base-station as a player interested in maximizing a
weighted sum of the individual rates, we then propose a Stackelberg
formulation in which the base-station is the designated game leader.
We show that this formulation allows for achieving all the corner
points of the capacity region, in addition to the sum-rate optimal
point. Then we consider the cooperative multiple access channel, where
we show that non-cooperation is the only Nash Equilibrium. By
introducing a relay node designated as the leader of a Stackelberg
game, we show that cooperation emerges at the equilibrium point under
some typical operating scenarios. Finally, we establish similar
results for the interference channel.
Slides [ppt]
|
| |