Performance Limits of Greedy Maximal Matching in Multi-Hop Wireless Networks
In this paper, the authors characterize the performance limits of an important class of scheduling schemes, called Greedy Maximal Matching (GMM), for multi-hop wireless networks. For simplicity, they 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.