On capacity outer bounds for a simple family of wireless networks
Michelle Effros · 2010
This paper explores models for finding outer bounds on the capacities of a simple family of wireless networks. Each wireless network is comprised of a collection of independent, memoryless channels with no more than three nodes: one transmitter and two receivers in each broadcast channel, two transmitters and one receiver in each multiple access channel, and one transmitter and one receiver in each point-to-point channel. The approach taken applies prior network equivalence results for modeling the individual components in each network and then bounds the difference between the modeling network capacity and the capacity of the original network. For binary channels, the modeling network guarantees capacities within a constant multiplicative factor of the true network capacity for all possible demand types. The results for networks of Gaussian channels yield cuts across each channel within an additive constant of the optimal cut value. These constant gaps in cut values give additive bounds on the accuracy of capacities for demand types where cut-sets are tight. The bounding network capacity is also tight for some example networks where the gap between the capacity region and the traditional cut-set outer bounds can be made arbitrarily large.