University of Southern California WiDeS - Wireless Devices and Systems Group The USC Andrew and Erna Viterbi School of Engineering USC




In cellular communications, a mobile station (MS) usually communicates directly with a base station (BS). Thus, even when there are multiple MSs in the cell, they all use a "single-hop" strategy, sending the data directly to the destination. The MSs thus compete for resources (spectrum).

In multi-hop networks, devices send their data via a number of "helpers" (relay nodes) to the destination; this use of relays enables a number of performance improvements.  Energy efficiency can be improved since the distances over which each node must transmit are often reduced significantly.  Improved robustness to fading and failure of individual nodes results from the increased number of possible transmission paths connecting source and destination.
The most basic form of relaying consists of routing information along a single path.  Data packets are passed from one node to the next in a manner akin to a bucket brigade.  More sophisticated methods that require tighter synchronization between nodes at the physical and media access control (MAC) layer can lead to much larger performance gains.

At a high level multihop relaying can be broken down into two distinct sub-problems.  The first is the design of physical and MAC layer techniques for relaying information from one set of nodes to the next. The second is routing, i.e., identifying which of the available nodes should participate in the transmission and what system resources (time, energy, bandwidth) should be allocated to each.  These two sub-problems are connected, and we consider both of them in our research.

The Basic Building Block

The basic building block of a coperative communication system is shown in the figure below.

It consists of a transmitter, a number of parallel relays, and a destination. Transmission of the information occurs in two phases: in phase 1, the transmitter broadcasts the information to the relay nodes. An important concept here is the "broadcast advantage", i.e., the notion that when the TX sends information to one relay, the other relays can overhear that transmission without requiring the receiver to "invest" additional energy. In phase 2, the relay nodes cooperate in some form to send the information to the destination. The form of cooperation depends on the amount of channel state information (CSI) that the relays have available:

FULL CSI: if the relays know amplitude and phase of the channels to the destination, they can perform distributed beamforming (also known as maximum ratio transmission) to the destination. All relays adjust their phases in such a way that the contributions from the relays superimpose constructively at the destination. The method requires a high degree of synchronization between the relays.

AMPLITUDE-ONLY CSI: in this case, the relay with the strongest channel transmits, while all other relays remain silent.

NO CSI: Two schemes have become popular for this case: (i) distributed space-time coding, where the different relays are sending out space-time encoded versions of the same signal. This method requires symbol-level synchronization. (ii) Each relay encodes the signal using a different "rateless code" (Fountain code), which essentially allows the receiver to accumulate the bits (mutual information) it gets from the various relays. The process can be envisioned as the receiver being a big bucket, and the relays being Fountains spewing water into it. The receiver does not care where the water is coming from; as soon as it is full (enough mutual information is accumulated), data reception is successfully concluded, and the information from the source can be decoded.

Our research has concentrated on the the cases of Full CSI, and No-CSI with Fountain codes.


Routing in Cooperative Networks

A key problem in cooperative communications is finding the best route between a source and its destination(s). In the case of simple multi-hop networks (the "fire bucket brigade" forwarding), optimal routing is well-established (shortest-path routing), but when the "basic building blocks" use different forms of collaboration, like mutual information accumulation, new routing methods need to be found.

Our most recent work revolves around the routing problem in networks using mutual-information accumulation (Fountain codes) as the physical layer. We have shown that the problem can be broken down into two parts that can be solved iteratively: (i) for a fixed route, the optimal resource allocation (i.e., which node in the route should transmit when, and for how long, in order to forward the information to the destination) can be formulated as a Linear Program (LP), which can be solved very efficiently, (ii) improving upon a route, based on the solution to the corresponding resource allocation LP (if the linear program allocates zero resources to a node, this is an indication that the route and/or decoding sequence needs to be changed.

However, this does not guarantee that we converge to the optimal route, since finding the best route turns out to be NP-hard (i.e., all possible routes have to be computed, and then the best is picked) - a computational effort that is not acceptable in practical networks. But in many cases, approximate solutions yielding near-optimal performance can be found by starting with initial routes based on good heuristics.

An interesting extension of this problem is "multicasting", where the information should reach multiple nodes. The question then is: which route should be chosen so that within a certain (guaranteed) time the packet reaches its destination?

Routing of Multiple Simultaneous Packets Streams

Optimum routing of a single packet has been well explored in wireless ad-hoc network based on Bellman-Ford or Dijkstra algorithm with certain restrictions, and practical routing systems such as Optimized Link State Routing and Destination-Sequenced Distance Vector routing are in widespread use.

However, simultaneous routing of multiple packet streams intended for multiple receivers (multiple commodities) is much more difficult, as different commodities are competing for the limited resources. While traditional routing algorithms still can be used with some ad-hoc modifications, designing optimum routes and resource allocations becomes much more difficult. This particularly holds true when it is not desirable and/or possible to have precise information about the packet arrivals and channel states at a central node that can design the optimal routes.

The most promsing approach to solve these problems is the class of stochastic routing algorithms. In particular, the backpressure algorithm establishes a metric for each commodity on each available link that takes into account the differential of the queue lengths (number of packets of a particular commodity in a node) as well as the channel state of a link. The packet with the largest metric will be transmitted. Thus, backpressure algorithm achieves routing without ever designing an explicit route, and without requiring centralized information. Furthermore, based on these considerations and taking broadcast effect into account, Diversity Backpressure algorithm (DIVBAR) was developed and shown to be throughput optimal in stochastic networks with certain transmission scheme assumptions, most notably that any packet not correctly received by a node has to be completly retransmitted.

The efficiency of retransmission can be greatly enhanced by Mutual Information Accumulation (MIA), where receiving nodes shore and accumulate the partial information of packets that cannot be decoded at the previous transmission attempts. The decoding of later transmission attempts can be facilitated by the accumulated partial information in the sense that the receiver can decode the packet as long as the total amount of accumulated partial information at the receiver exceeds the entropy of the packet.

In our group, the algorithms combining DIVBAR and MIA have been proposed and analyzed. There are two versions: DIVBAR-MIA, where all received partial information of a packet is retained by the nodes in the network until the packet reaches it's destination; DIVBAR-RMIA ("R" stands for "Renewal"), where all receiving nodes clear out the partial information whenever the corresponding packet is firstly decoded by at least one reciving node, not necessarily the destination. We have proved and simulated that both algorithms can achieve larger throughput limits than the regular DIVBAR algorithm, as is shown in the following figure:

Network Timing/Synchronization

Synchronization is fundamental to many aspects of life and nature. In communication, the word 'synchronization' is well understood and has been handled well as an interesting research problem for decades. However, more interesting and challenging problems that continue to puzzle researchers are also found in other areas of science. The following text is quoted form the preface of the scintillating book, 'Sync', Steven H. Strogatz, 2003, to give an introduction to the broadness and the importance of synchrony.

"At the heart of the universe is steady, insistent beat: the sound of cycles in sync. It pervades nature at every scale from nucleus to cosmos. Every night along the tidal rivers of Malaysia, thousands of fireflies congregate in the mangroves and flash in unison, without any leader or cue from the environment. Trillions of electrons march in lockstep in a superconductor, enabling electricity to flow through it with zero resistance. In the solar system, gravitational synchrony can eject huge boulder out of the asteroid belt and toward Earth...." "Even our bodies are symphonies of rhythm, kept alive by the relentless, coordinated firing of thousands of pacemaker cells in our hearts...."

Watch firefilies in synchrony in the video

At first sight synchronization/timing may look like a problem that has been solved, for instance the internet, a network of millions of synchronized devices. However, the problem is challenging and still unsolved when it comes to synchronizing a large network of nodes and when the following conditions are set: 1. The node's required timing (synchronization) accuracy is comparable to the propagation delays   2. The network is ad-hoc   3. No centralized control is feasible; timing should be performed in a distributed fashion.

The particular problem wa are working on now is to create a timing virtual network for distributed sensing applications. We expect to achieve timing accuracies many orders better than the current achievables limits.


Under Constructions


Book Chapters:

A. F. Molisch, N. B. Mehta, and S. Draper, “Cooperative Communications for Reliability”, in I. Guvenc, S. Gezici, Z. Sahinoglu, and U. Kozat,  “Reliable Communications for Short-Range Wireless Systems”, Cambridge University Press (2011).

Journal Papers

S. C. Draper, L. Liu, A. F. Molisch, and J. Yedidia, “Cooperative Routing for Wireless Networks using Mutual-Information Accumulation”, IEEE Trans. Information Theory, 57, 5151 – 5162 (2011).

R. Yim, N. B. Mehta, and A. F. Molisch, “Fast Multiple Access Selection Through Variable Power Transmissions”, IEEE Trans. Wireless Comm., 8, 1962-1973 (2009).

R. Yim, N.B. Mehta, A. F. Molisch, and J. Zhang, “Dual Power Multiple Access with Multipacket Reception using Local CSI ”, IEEE Trans. Wireless Comm., 8, 4078-4088 (2009).

C. Wang, H. Chen, Q. Yin, A. Feng, and A. F. Molisch, “Multi-User Two-Way Relay Networks with Distributed Beamforming”, IEEE Trans. Wireless Comm. 10, 3460 – 3471 (2011).


Conference Papers