On the Complexity of Wireless Multicast Optimization

This letter considers a class of utility optimization problems in wireless networks. Under a set of physical layer assumptions, we show that the impact of physical and data-link layer configurations to the upper layers in a wireless network can be characterized using a configuration graph, which is similar to a wireline network topology graph. Network layer utility optimization can consequently be carried out via iterations that optimize network layer algorithms over the configuration graph and incrementally revise physical, data-link layer configurations to improve the configuration graph. For a class of wireless multicast networks with network coding, we show that the number of point-to-multipoint links involved in network utility optimization is only polynomial, as opposed to exponential, in the number of nodes.