Foundations and Trends® in Networking > Vol 8 > Issue 3

Multihop Wireless Networks: A Unified Approach to Relaying and Interference Management

Ilan Shomorony, Cornell University, USA, is256@cornell.edu Salman Avestimehr, University of Southern California, USA, avestimehr@ee.usc.edu
 
Suggested Citation
Ilan Shomorony and Salman Avestimehr (2014), "Multihop Wireless Networks: A Unified Approach to Relaying and Interference Management", Foundations and Trends® in Networking: Vol. 8: No. 3, pp 149-280. http://dx.doi.org/10.1561/1300000044

Published: 03 Dec 2014
© 2014 I. Shomorony and S. Avestimehr
 
Subjects
Data networks,  Multiuser information theory,  Wireless Communications,  Modeling and Analysis: Ad Hoc Wireless Networks,  Modeling and Analysis: Cellular Networks,  Protocols and Cross-Layer Design,  Topology
 

Free Preview:

Article Help

Share

Download article
In this article:
1. Introduction
2. Problem Setting and a Motivating Example
3. Two-Unicast Wireless Networks
4. Multi-Unicast Wireless Networks
References

Abstract

Multi-hop communication paradigms are expected to play a central role in future wireless networks by enabling a higher spatial reuse of the spectrum. A major challenge in multi-hop multi-user (or multi-flow) wireless networks is that "interference management" and "relaying" are coupled with each other. In other words, wireless relay nodes must play a dual role: they serve as intermediate steps for multi-hop communication and as part of the mechanism that allows interference management schemes. Nonetheless, in the communications, networking and information theory literature, these two tasks have traditionally been addressed separately, and the fundamental principles of the "wireless networks of the future" are currently not well understood. In this monograph, we take a unified approach to relaying and interference management, and seek to develop tools to study the fundamentals of multi-hop multi-flow wireless networks. We first consider multi-hop two-flow – or two-unicast – wireless networks. In order to handle networks with an arbitrary number of hops and arbitrary interference patterns, we introduce the idea of network condensation, by which a network with an arbitrary number of layers is effectively reduced to a network with at most four layers. This is done by identifying key layers and letting the nodes in all other layers apply random linear coding to relay the messages. Only the nodes in the remaining key layers need to be "smart" and perform coupled relaying and interference management operations. In addition, we introduce the new notion of paths with manageable interference, which represents a first attempt at finding flow-like structures in multi-user wireless networks, and develop novel outer bounds that capture the interference structure of a given topology. These techniques yield a complete characterization of the degrees of freedom of two-unicast layered networks as a function of the network graph. Extending these results for general K-unicast networks is quite challenging. To make progress on this front, we focus on the K x K x K wireless network, a two-hop network consisting of K sources, K relays, and K destinations. This network represents a canonical example of a multi-hop multi-flow wireless network for which previously there was a large gap between known inner and outer bounds, even from a degrees-of-freedom perspective. We introduce a coding scheme called Aligned Network Diagonalization (AND) that couples relaying and interference management in a way that all interference experienced by the destinations is simultaneously neutralized. This proves that K x K x K wireless networks have K sum degrees of freedom and demonstrates the significant gains that can be obtained with a unified approach to relaying and interference management. Moreover, this automotically yields the optimal scheme and degrees-of-freedom characterization for layered K unicast networks with fully connected hops. We then describe ideas and preliminary results for K-unicast networks with general topologies. Besides discussing how the tools developed for two-unicast networks and for K x K x K networks can be extended to this general setting, we present a novel outer-bounding technique, which improves over the cut-set bound and can capture limitations imposed by the interference between different users. The new bound can be understood as computing the flow across multiple "nested cuts", as opposed to a single cut, as is the case in the classical cut-set bound. This technique allows us to establish a graph-theoretic notion of manageable interference in K x K x K wireless networks with arbitrary connectivity. Throughout the monograph, many extensions and future directions are addressed. At the end of each chapter, related work is also described and several open problems are presented. Important research directions such as accounting for the lack of global channel state information in large networks and reducing the complexity of relaying operations are discussed, and recent results along these lines are described.

DOI:10.1561/1300000044
ISBN: 978-1-60198-904-8
144 pp. $90.00
Buy book
 
ISBN: 978-1-60198-905-5
144 pp. $120.00
Buy E-book
Table of contents:
1. Introduction
2. Problem Setting and a Motivating Example
3. Two-Unicast Wireless Networks
4. Multi-Unicast Wireless Networks
References

Multihop Wireless Networks

In multi-hop wireless networks; that is, networks where messages must traverse multiple nodes before reaching their destination, wireless relay nodes must play a dual role: they serve as intermediate steps for relaying schemes and as part of the mechanism that allows interference management schemes.

Hence, relaying and interference management are two key aspects of communication in wireless networks. Both these aspects are introduced in a tutorial manner before going on to consider the combination of the two. In multi-hop multi-flow networks, the challenge is to combine the insights obtained in the study of single-hop multi-flow networks and multi-hop single-flow networks in order to design schemes that handle relaying and interference management simultaneously. This monograph discusses the gains that can be obtained by taking such a unified approach to relaying and interference management.

Multihop Wireless Networks: A Unified Approach to Relaying and Interference Management is of interest to students and researchers working on modern network systems.

 
NET-044