Message passing in distributed wireless networks

In distributed wireless networks, nodes often do not know the topology (network size, connectivity and the channel gains) of the network. Thus, they cannot compute their own maximum transmission rate and appropriate transmission scheme. In this paper, we address the inter-related problems of learning the network and the associated best achievable rates. To make progress, we will focus on K-user deterministic interference networks. First, we propose a message passing algorithm which allows nodes to incrementally learn the network topology. In each round of message passing, nodes forward what they believe is the new information to their neighbors and thus the network topology information trickles via broadcasts. Next, we consider two special examples of Z-channel and double-Z interference network and determine the sum-rate points with incomplete network information at different nodes. We show that the sum-rate point can in fact be achieved with less than full information at all the nodes but in general, less network information implies reduced set of achievable rates. In order to analyze the performance of a double-Z interference network with limited information, we find the capacity region of a deterministic double-Z interference network with full information, which is of independent interest.