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
Y1 - 2005
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 -