Performance limits of greedy maximal matching in multi-hop wireless networks

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 sigma-local pooling. We then define the local-pooling factor on a graph, as the supremum of all sigma such that the graph satisfies sigma-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.