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

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.