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

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

© 2014 I. Shomorony and S. Avestimehr

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

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

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.

1. Introduction

2. Problem Setting and a Motivating Example

3. Two-Unicast Wireless Networks

4. Multi-Unicast Wireless Networks

References

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.