Wireless Network Coding with Local Network Views

"If we know more, we can achieve more." This adage also applies to communication networks, where more information about the network state translates into higher sum rates. In this talk, we formalize and investigate this increase of sum-rate with increased knowledge of the network state. In particular, we focus on the case that each source-destination pair has enough information to perform optimally when other pairs do not interfere, however beyond that they only know the connectivity of the network (i.e., not the channel gains). We investigate the information-theoretic limits of communication with such limited knowledge at the nodes (called 1-local view). We develop a novel transmission strategy that solely relies on 1-local view at the nodes and incorporates three different techniques: (1) per layer interference avoidance, (2) repetition coding to allow overhearing of the interference, and (3) network coding to allow interference neutralization. We show that our proposed scheme can provide a significant throughput gain compared with the conventional interference avoidance strategies. Furthermore, we show that our strategy maximizes the achievable normalized sum-rate for some classes of networks, hence, characterizing the normalized sum-capacity of those networks with 1-local view. This work is in collaboration with Alireza Vahid, Vaneet Aggarwal, and Ashu Sabharwal.