A wireless network consists of a set of nodes which want to communicate to one another with the help of relay nodes, where all the transmissions occur over a shared wireless medium. A fundamental aspect of wireless communication is its broadcast nature and consequently (multiple
access) interference between simultaneously transmitting nodes. This is in direct contrast to wired networks where communication links do not interact leading to information flows over graphs. Therefore, information flow over a wireless network is challenging due to these complex interactions. A traditional way to handle these interactions is to attempt to create point-to-point links by either scheduling the transmissions or ignoring the interference. In this tutorial we will review recent developments which model and utilize these interactions in order to significantly increase the overall information flow rates, in contrast to avoiding interactions.
We will first develop deterministic models for the wireless interactions that capture the main properties of the wireless network. Using such a model, we study the unicast and multicast information flow over a wireless network. For such models, we will develop an information-theoretic max-flow min-cut result, in analogy to the classic wireline Ford-Fulkerson result. Using the insights from the deterministic analysis, we develop approximate characterizations for noisy wireless 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 wireless relay networks within a constant number of bits, for all channel parameters. This result applies to arbitrary relay networks, with any number of nodes and cycles in the network. We will develop several implications of these techniques and results.