Bounding the Power Rate Function of Wireless Ad hoc Networks

Given a wireless ad hoc network and an end-to-end traffic pattern, the power rate function refers to the minimum total power required to support different throughput under a simplified layered model of wireless networks. A critical notion of the layered model is the supported (realizable) capacity graphs, which describe possible bit-rate provisions on the links by the physical and link layers. Under the layered model, the problem of finding the power rate function can be transformed into finding the minimum-power supported capacity graph that can provide a given throughput. We introduce a usage conflict graph to represent the conflicts among different uses of the wireless medium. Testing the realizability of a given capacity graph can be transformed into finding the (vertex) chromatic number, i.e., the minimum number of colors required in a proper vertex-coloring, of the associated usage conflict graph. Based on an upper bound of the chromatic number, we propose a linear program that outputs an upper bound of the power rate function. A lower bound of the chromatic number is the clique number. We propose a systematic way of identifying cliques based on a geometric analysis of the space sharing among active links. This leads to another linear program, which yields a lower bound of the power rate function. We further apply greedy vertex-coloring to fine tune the bounds. Simulations results demonstrate that the obtained bounds are tight in the low power and low rate regime.