Abstract
In distributed wireless networks, nodes often do not have access to complete network information (e.g. network topology, channel gains, etc.). As a result, they have to execute their transmission and reception strategies with partial information about the network, in a distributed fashion. Thus, the key question is how good are the distributed decisions in comparison to the optimal decisions based on full network knowledge. In this paper, we formalize the concept of partial-information sum-capacity by defining normalized sum-capacity, which is defined as the maximum achievable fraction of full-information sum-capacity with a given amount of partial information. We then examine four deterministic networks, multiple access, multiuser Z-channel chain, one-to-many and many-to-one interference channel, and characterize the normalized sum-capacity. For each network, two cases of partial network information are analyzed: (a) each transmitter only knows the channel gains to its receiver, and (b) transmitters knows the channel gains of all links which are no more than two hops away. Quite interestingly, we show that in all eight cases (4 networks × 2 forms of partial information), the normalized sum-capacity is achieved by scheduling subnetworks for which there exist a universally optimal distributed strategy with the available partial information. Furthermore, we show that while actual sum-capacity is not known in all cases, normalized sum-capacity can be in fact be exactly characterized.