Wireless network information flow

Suppose we want to send information from a source to a destination over a wireless network. There might be (relay) nodes in the network that are able to listen to the transmission and help with the communication. A fundamental question is how to instantiate such cooperative communications. Furthermore, how can we characterize optimal cooperation strategies? In order to architect such cooperation, we can utilize the inherent property of wireless networks, which is that nodes communicate over a shared medium. The consequence (in direct contrast to wired networks) of this is that transmissions are broadcast, and they interfere with each other at a receiver. The fundamental challenge is to model and utilize these complex interactions for co-operative information flow. One strategy is to attempt to create point-to-point links by either scheduling the transmission or ignoring the interference. One can show that such strategies can incur significant losses in terms of communication efficiency (rates, energy, etc.). Since the signals transmitted contain messages and are not noise, one could potentially utilize these interactions to set up cooperation between the wireless nodes to aid the information flow. A fundamental question is how to do so in general relay networks.

We have developed linear deterministic models that capture these interactions and show that for such models, one can obtain an information-theoretic max-flow min-cut result, in analogy to the classic wireline Ford-Fulkerson result. We have extended these ideas to general deterministic functions and showed achievable rates for such networks with broadcasting at the transmitters and interference at the receivers. In particular we show that if the optimizing distribution for the information-theoretic cut-set bound is a product distribution, then we have a complete characterization of the achievable rates for such networks. For linear deterministic finite-field models this is indeed the case, and for such cases we have a generalization of of the max-flow, min-cut theorem. This result applies to arbitrary networks, which could also have cycles.

Using the insights from the deterministic analysis, we develop approximate characterizations for noisy Gaussian networks. We show that the achievable rate, for single unicast or multicast (single source, multiple destinations interested in complete source message), 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 topology of 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. This result applies to arbitrary Gaussian relay networks.

In order to show the approximate max-flow min-cut characterization for Gaussian networks, we developed a new relaying strategy called quantize-map-forward (QMF). None of the previously known strategies are approximate optimality for multicasting over general networks. The QMF is a simple and robust scheme that quantizes the received signal and maps it forward directly to the transmit signal, to succintly summarize the received signal. The relaying strategy is therefore (almost) oblivious to the network topology and channel conditions. The QMF strategy uses the insights from the deterministic framework and is philosophically the network coding technique generalized to noisy wireless networks.

There are subtle but critical differences between the QMF strategy, with the natural extension of compress-forward to networks for the following reasons. The compress-forward scheme quantizes the received signal and then mapped the digital bin index onto the transmit sequence. This means that we need to make choices on the binning rates at each relay node. However, the QMF scheme directly maps the the quantized sequence to the transmit sequence, and therefore does not make such choices on the binning rates. In fact this gives the scheme a `universality' property, which allows the same relay operation to work for multiple destinations (multicast) and network situations (compound networks); a property that could fail to hold if specific choices of binning rates were made. Moreover, our scheme unlike the classical compress-forward scheme, does not require the quantized values at the relays to be reconstructed at the destination, while it is attempting to decode the transmitted message. These are the essential differences between our scheme and the traditional compress-forward, or the natural network generalization of it.

We have also extended this approach to multi-source multicast, where many sources are to be received at multiple receivers, where all sources are required.


  1. Download: fto_cod.pdf 
    In this paper we examine the value of feedback that comes from overhearing, without dedicated feedback resources. We focus on a simple model for this purpose: a deterministic two-hop interference channel, where feedback comes from overhearing the forward-links. A new aspect brought by this setup is the dual-role of the relay signal. While the relay signal needs to convey the source message to its corresponding destination, it can also provide a feedback signal which can potentially increase the capacity of the first hop. We derive inner and outer bounds on the sum capacity which match for a large range of the parameter values. Our results identify the parameter ranges where overhearing can provide non-negative capacity gain and can even achieve the performance with dedicated-feedback resources. The results also provide insights into which transmissions are most useful to overhear.
  2. Download: quilt.pdf 
    Physical layer cooperation of a source with a relay can significantly boost the performance of a wireless connection. However, the best practical relaying scheme can vary depending on the relative strengths of the channels that connect the source, relay and destination. This paper proposes and evaluates QUILT, a system for physical-layer relaying that seamlessly adapts to the underlying network configuration to achieve competitive or better performance as compared to the best current approaches. QUILT combines on-demand, opportunistic use of Decode-Forward (DF) or Quantize-Map-Forward (QMF) followed by interleaving at the relay, with hybrid decoding at the destination that extracts information from received frames even if these are not decodable. We theoretically quantify how our design choices for QUILT affect the system performance. We also deploy QUILT on the WarpLab software radio platform, and show through over-the-air experiments up to 5 times FER improvement over the next best cooperative protocol.
  3. Download: lattice_qmf.pdf 
    Recently, a new relaying strategy, quantize-map-and-forward (QMF) scheme, has been demonstrated to approximately achieve (within an additive constant number of bits) the Gaussian relay network capacity, universally, i.e., for arbitrary topologies, channel gains, and SNRs. This was established using Gaussian codebooks for transmission and random mappings at the relays. In this paper, we develop structured lattice codes that implement the QMF strategy. The main result of this paper is that such structured lattice codes can approximately achieve the Gaussian relay network capacity universally, again within an additive constant. In addition, we establish a similar result for half-duplex networks, where we demonstrate that one can approximately achieve the capacity using fixed transmit-receive (TX-RX) schedules for the relays with no transmit power optimization across the different TX-RX states of the network.
  4. Abstract:
    We present the design and experimental evaluation of a wireless system that exploits relaying in the context of WiFi. We opt for WiFi given its popularity and wide spread use for a number of applications, such as smart homes. Our testbed consists of three nodes, a source, a relay and a destination, that operate using the physical layer procedures of IEEE802.11. We deploy three main competing strategies that have been proposed for relaying, Decode-and-Forward (DF), Amplify-and-Forward (AF) and Quantize-Map-Forward (QMF). QMF is the most recently introduced of the three, and although it was shown in theory to approximately achieve the capacity of arbitrary wireless networks, its performance in practice had not been evaluated. We present in this work experimental results---to the best of our knowledge, the first ones---that compare QMF, AF and DF in a realistic indoor setting. We find that QMF is a competitive scheme to the other two, offering in some cases up to 12% throughput benefits and up to 60% improvement in frame error-rates over the next best scheme.
  5. Download: dynamic_qmf.pdf 
    The value of relay nodes to enhance the error performance versus rate trade-off in wireless networks has been studied extensively. However, wireless nodes currently are constrained to only transmit or receive at a given frequency, i.e., half-duplex constraint. The diversity-multiplexing tradeoff (DMT) for half-duplex networks are less understood. In the special cases where the DMT is currently known, such as the relay channel and the line network, it is achieved by either dynamic decoding or a quantize-map-forward (QMF) strategy with a fixed half-duplex schedule. The main question we investigate in this paper is whether these two strategies are sufficient to achieve the DMT of half-duplex wireless networks or we need new strategies for general setups. We propose a generalization of the two existing schemes through a dynamic QMF strategy and show that in a parallel relay channel it outperforms both earlier schemes. We also establish the DMT for the relay channel with multiple relays and multiple antennas in some special cases.
  6. Download: graph_qmf.pdf 
    We present a structured Quantize-Map-and-Forward (QMF) scheme for cooperative communication over wireless networks, that employs LDPC ensembles for the node operations and message-passing algorithms for decoding. We demonstrate through extensive simulation results over the full-duplex parallel relay network, that our scheme, with no transmit channel state information, offers a robust performance over fading channels and achieves the full diversity order of our network at moderate SNRs.
  7. Abstract:
    In this paper we study two-stage Gaussian relay-interference networks where there are weak cross-links, causing the networks to behave like a chain of Z Gaussian channels. Our main result is an approximate characterization of the capacity region for such networks. We propose a new interference management scheme, termed interference neutralization, which is implemented using structured lattice codes. This scheme allows for over-the-air interference removal, without the transmitters having complete access the interfering signals.
  8. Abstract:
    This paper approximately resolves the information flow over wireless (Gaussian) relay networks to within a constant number of bits. It introduced the linear deterministic model and established a max-flow min-cut result for linear deterministic networks. The insights from the deterministic approach led to the approximate max-flow min-cut characterization for noisy Gaussian networks, through the introduction of a new relaying strategy called quantize-map-forward (QMF).
  9. Download: md_itw10.pdf 
    We study the problem where there is a single adversarial node which injects signals to disrupt this communication in a parallel relay network. Like the source, it can only influence the destination through the relays. We develop an approximate characterization of the reliable transmission rate in the presence of such an adversary. A deterministic version of the same problem is solved exactly, yielding insights which are used in the approximate characterization.
  10. Download: od_isit10.pdf on Arxiv 
    An approximate max-flow min-cut result for arbitrary wireless relay network was recently established using Gaussian codebooks for transmission and random mappings at the relays. In this paper, we show that the approximation result can be established by using lattices for transmission and quantization along with structured mappings at the relays. This also extended the original scalar quantizer analysis to vector quantizers and obtained a slightly better approximation constant.
  11. Note: Invited paper surveying our results on wireless relay network secrecy.
    Download: pdtizs10.pdf 
  12. Download: pdtisit10.pdf 
    In this paper we consider information-theoretically secure communication between two special nodes (“source” and “destination”) in a memoryless network with authenticated relays, where the secrecy is with respect to a class of eavesdroppers. We develop achievable secrecy rates when authenticated relays also help increase secrecy rate by inserting noise into the network.
  13. Abstract:
    Lossless transmission of a set of correlated sources over a deterministic relay network is considered for two traffic requirements. In distributed multicast, the set of sources are to be delivered to a set of destinations. The source exchange requires all the nodes with access to sources to be able to reconstruct all other sources observed at other nodes. We develop achievable regions and outer bounds for both these situations. For linear deterministic networks, these bounds coincide, yielding a characterization.
  14. Abstract:
    In this paper we consider secret communication between two special nodes (“source” and “destination”) in a wireless network with authenticated relays: the message communicated to the destination is to be kept information-theoretically (unconditionally) secret from any eavesdropper within a class. Since the transmissions are broadcast and interfere with each other, complex signal interactions occur. We develop cooperative schemes which utilize these interactions in wireless communication over networks with arbitrary topology, and give provable unconditional secrecy guarantees.
  15. Download: sdfpitw09.pdf 
    Abstract—We consider the two message set problem, where a source broadcasts a common message W1 to an arbitrary set of receivers U and a private message W2 to a subset of the receivers P !U . Transmissions occur over linear deterministic channels. For the case where at most two receivers do not require the private message, we give an exact characterization of the capacity region, where achievability is through linear coding.
  16. S. Mohajer, S. N. Diggavi, C. Fragouli, and D. Tse, "Capacity of Deterministic Z-Chain Relay-Interference Network," in Proc. IEEE Information Theory Workshop (ITW), Volos, Greece, 2009, pp. 331-335.
  17. S. Mohajer and S. N. Diggavi, "Deterministic approach to wireless network error correction," in Proc. IEEE Information Theory Workshop (ITW), Volos, Greece, 2009, pp. 5-9.
  18. S. Mohajer, S. N. Diggavi, and D. Tse, "Approximate Capacity of a Class of Gaussian Relay-Interference Networks," in Proc. IEEE International Symposium on Information Theory (ISIT), Seoul, Korea, 2009, pp. 31-35.
  19. Download: pdt_icc09.pdf 
    We introduce the interference-multiple-access channel, which is a discrete memoryless channel with two transmitters and two receivers, similar to the interference channel. One receiver is required to decode the information encoded at one transmitter, the other receiver is required to decode the messages from both transmitters. We provide an inner bound on the capacity region of this channel, as well as an outer bound for a special class of such channels. For this class, we also quantify the gap between inner and outer bound and show that the bounds match for a semi-deterministic channel, providing a complete characterization. For the Gaussian case, we show that the gap is at most 1 bit, yielding an approximate characterization.
  20. Download: pdtita09final.pdf 
    This paper studies the idea of noise insertion by authenticated relays through friendly jamming. We develop the secrecy rate achievable in arbitrary (deterministic) networks when there are relays actively helping secrecy.
  21. Download: pdt_allerton08.pdf 
    We study a line network with an eavesdropper having access to the relay transmission. We assume that there could also be a public feedback channel from the destination. We develop achievable strategies to achieve certain rate-equivocation pairs.
  22. S. Mohajer, S. N. Diggavi, C. Fragouli, and D. Tse, "Transmission techniques for relay-interference networks," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2008, pp. 464-474.
  23. A. Sabharwal and S. N. Diggavi, "Compound Gaussian multiple access channels with noisy feedback," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2008, pp. 887-894.
  24. S. Avestimehr, S. N. Diggavi, and D N C. Tse, "Approximate characterization of capacity in Gaussian relay networks," in Proc. IEEE International Wireless Communications and Mobile Computing Conference (IWCMC), Crete, Greece, 2008, pp. 56-61.
  25. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "Approximate Capacity of Gaussian Relay Networks," in Proc. IEEE International Symposium on Information Theory (ISIT), Toronto, Canada, 2008, pp. 474-478.
  26. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "Information flow over compound wireless relay networks," in Proc. IEEE Zurich Seminar on Communications (IZS), Zurich, Switzerland, 2008, p. 92.
  27. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "Wireless network information flow," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2007.
  28. Download: degmsgsetbc07.pdf 
    In this paper we study the nested (degraded) message set problem, where user i requires messages W_1, . . . ,W_i. We study this for a MIMO linear deterministic broadcast channel model, which is motivated by some recent successes in using such models to obtain insights into approximate characterizations for the Gaussian relay and interference channels. We establish the complete solution for the K = 3 user nested message problem for the MIMO linear deterministic broadcast channel. We also establish some extremal points for the general K-user case, where there are only two messages of interest.
  29. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "A Deterministic Approach to Wireless Relay Networks," in Proc. Proceedings of Allerton Conference on Communication, Control, and Computing, Illinois, 2007.
  30. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "A deterministic model for wireless relay networks and its capacity," in Proc. IEEE Information Theory Workshop (ITW) Bergen, Norway, 2007, pp. 6-11.