This paper proposes a new model for wireless relay networks referred to as '1-2-1 network', where two nodes can communicate only if they point 'beams' at each other, otherwise no signal can be exchanged or interference can be generated. This model is motivated by millimeter wave communications where, due to the high path loss, a link between two nodes can exist only if beamforming gain at both sides is established, while in the absence of beamforming gain the signal is received well below the thermal noise floor. The main contributions in this paper include: (a) the development of a constant gap approximation for the unicast and multicast capacities of the proposed network model, i.e., a characterization of the network unicast and multicast capacities to within an additive gap, which only depends on the number of nodes and is independent of the channel coefficients and operating SNR; and (b) the design of algorithms that run in polynomial time in the number of nodes and compute the approximate unicast and multicast capacities, as well as their corresponding optimal beam scheduling strategies. These results are derived both for full-duplex and half-duplex modes of operation at the relays: while in full-duplex the transmit and receive beams at a relay can be simultaneously active, in half-duplex only one can be active at each point in time. The relation between the approximate multicast capacity and minimum unicast capacity is explored in full-duplex 1-2-1 networks and shown to be dependent on the network structure and the number of destinations, unlike in classical wireless (i.e., without 1-2-1 constraints) full-duplex networks. Finally, network simplification results are proved for the 1-2-1 network model by exploiting the structure of the linear program that represents the approximate capacity.
Bibliographical noteFunding Information:
Manuscript received October 23, 2019; revised October 5, 2020; accepted October 18, 2020. Date of publication October 29, 2020; date of current version January 21, 2021. This work was supported in part by the National Science Foundation (NSF) under Award 1514531 and Award 1824568 and in part by the University of California Office of the President (UCOP) UC-NL under Grant LFR-18-548554. The work of Giuseppe Caire was supported by the ERC Advanced Grant—CARENET under Grant 789190. This article was presented in part at the 2018 and 2019 IEEE International Symposium on Information Theory. (Corresponding author: Yahya H. Ezzeldin.) Yahya H. Ezzeldin and Christina Fragouli are with the Electrical and Computer Engineering Department, University of California at Los Angeles, Los Angeles, CA 90095 USA (e-mail: email@example.com; firstname.lastname@example.org).
- approximate capacity
- efficient beam scheduling
- mmWave scheduling
- Multi-hop mmWave networks
- perfect matching polytopes
- polynomial separation oracles