TY - GEN
T1 - Performance limits of greedy maximal matching in multi-hop wireless networks
AU - Joo, Changhee
AU - Lin, Xiaojun
AU - Shroff, Ness B.
PY - 2007
Y1 - 2007
N2 - In this paper, we characterize the performance limits of an important class of scheduling schemes, called Greedy Maximal Matching (GMM), for multi-hop wireless networks. For simplicity, we focus on the well-established node-exclusive interference model, although many of the stated results can be readily extended to more general interference models. The study of the performance of GMM is intriguing because although a lower bound on its performance is well known, empirical observations suggest that this bound is quite loose, and that the performance of GMM is often close to optimal. In fact, recent results have shown that GMM achieves optimal performance under certain conditions. In this paper, we provide new analytic results that characterize the performance of GMM through the topological properties of the underlying graphs. To that end, we generalize a recently developed topological notion called the local pooling condition to a far weaker condition called the σ-local pooling. We then define the local-pooling factor on a graph, as the supremum of all σ such that the graph satisfies σ-local pooling. We show that for a given graph, the efficiency ratio of GMM (i.e., the worst-case ratio of the throughput of GMM to that of the optimal) is equal to its local-pooling factor. Further, we provide results on how to estimate the local-pooling factor for arbitrary graphs and show that the efficiency ratio of GMM is no smaller than d* /(2d* - 1) in a network topology of maximum node-degree d*. We also identify a specific network topology for which the efficiency ratio of GMM is strictly less than 1.
AB - In this paper, we characterize the performance limits of an important class of scheduling schemes, called Greedy Maximal Matching (GMM), for multi-hop wireless networks. For simplicity, we focus on the well-established node-exclusive interference model, although many of the stated results can be readily extended to more general interference models. The study of the performance of GMM is intriguing because although a lower bound on its performance is well known, empirical observations suggest that this bound is quite loose, and that the performance of GMM is often close to optimal. In fact, recent results have shown that GMM achieves optimal performance under certain conditions. In this paper, we provide new analytic results that characterize the performance of GMM through the topological properties of the underlying graphs. To that end, we generalize a recently developed topological notion called the local pooling condition to a far weaker condition called the σ-local pooling. We then define the local-pooling factor on a graph, as the supremum of all σ such that the graph satisfies σ-local pooling. We show that for a given graph, the efficiency ratio of GMM (i.e., the worst-case ratio of the throughput of GMM to that of the optimal) is equal to its local-pooling factor. Further, we provide results on how to estimate the local-pooling factor for arbitrary graphs and show that the efficiency ratio of GMM is no smaller than d* /(2d* - 1) in a network topology of maximum node-degree d*. We also identify a specific network topology for which the efficiency ratio of GMM is strictly less than 1.
UR - http://www.scopus.com/inward/record.url?scp=62749192182&partnerID=8YFLogxK
U2 - 10.1109/CDC.2007.4434334
DO - 10.1109/CDC.2007.4434334
M3 - Conference contribution
AN - SCOPUS:62749192182
SN - 1424414989
SN - 9781424414987
T3 - Proceedings of the IEEE Conference on Decision and Control
SP - 1128
EP - 1133
BT - Proceedings of the 46th IEEE Conference on Decision and Control 2007, CDC
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 46th IEEE Conference on Decision and Control 2007, CDC
Y2 - 12 December 2007 through 14 December 2007
ER -