On joint coding and combinatorial optimization in communication networks
Traditionally, information flows in communication networks are treated as commodity flows. Network coding is a new technique that allows nodes to manipulate the information content arbitrarily inside the network. Essentially, it raises a new joint coding and routing optimization question that needs to be addressed by exploiting both information theory and network combinatorics. This work focuses on the joint coding/routing optimization for throughput, energy consumption, and robustness of wired and wireless networks.
We study three sub-problems within this general setup: minimize communication cost of collecting correlated data through a network at a sink; maximize the throughput of multi-pair independent unicast traffic in wireless networks; and maximize the data utility in random, unreliable wireless data collection networks. For the correlated data gathering problem, we introduce an original concept called distance entropy that characterizes the spatial distribution of information at networked sources and shows that it is a meaningful metric as the tight lower bound of the minimum communication cost for collecting the sources at a single sink. We also propose a practical coding/routing algorithm called Hierarchical Difference Broadcasting (HDB) that achieves an order optimal performance yet simple to implement. For the second multi-pair unicast problem, we characterize the throughput capacity order and show coding combined with wireless broadcasting provides no order difference improvement. We also derive tighter bounds for the constant factor. For the third problem, we model the scheduling problem into a Multi-Armed Bandit (MAB) problem and derive the optimal solution using Gittins Indices.
0723: Information systems
0984: Computer science