TY - GEN

T1 - Bounding the power rate function of wireless ad hoc networks

AU - Wu, Yunnan

AU - Zhang, Qian

AU - Zhu, Wenwu

AU - Kung, Sun Yuan

PY - 2005/10/10

Y1 - 2005/10/10

N2 - 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 layered model of wireless networks. A critical notion of the layered model is the realizable graphs, which describe possible bit-rate supplies on the links by the physical and medium access layers. Under the layered model, the problem of finding the power rate function can be transformed into finding the minimum-power realizable 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 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.

AB - 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 layered model of wireless networks. A critical notion of the layered model is the realizable graphs, which describe possible bit-rate supplies on the links by the physical and medium access layers. Under the layered model, the problem of finding the power rate function can be transformed into finding the minimum-power realizable 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 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.

UR - http://www.scopus.com/inward/record.url?scp=25844496226&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=25844496226&partnerID=8YFLogxK

U2 - 10.1109/INFCOM.2005.1497925

DO - 10.1109/INFCOM.2005.1497925

M3 - Conference contribution

AN - SCOPUS:25844496226

SN - 0780389689

T3 - Proceedings - IEEE INFOCOM

SP - 584

EP - 595

BT - Proceedings - IEEE INFOCOM 2005. The Conference on Computer Communications - 24th Annual Joint Conference of the IEEE Computer and Communications Societies

A2 - Makki, K.

A2 - Knightly, E.

T2 - IEEE INFOCOM 2005

Y2 - 13 March 2005 through 17 March 2005

ER -