Abstract
Greedy Maximal Matching (GMM) is an important scheduling scheme for multi-hop wireless networks. It is computationally simple, and has often been numerically shown to achieve throughput that is close to optimal. However, to date the performance limits of GMM have not been well understood. In particular, although a lower bound on its performance has been well known, this bound has been empirically found to be quite loose. In this paper, we focus on the well-established node-exclusive interference model and provide new analytical results that characterize the performance of GMM through a topological notion called the local-pooling factor. We show that for a given network graph with single-hop traffic, 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 estimate the local-pooling factor for arbitrary network graphs under the node-exclusive interference model and show that the efficiency ratio of GMM is no smaller than d* /2d* - 1 in a network topology of maximum node-degree d*. Using these results, we identify specific network topologies for which the efficiency ratio of GMM is strictly less than 1. We also extend the results to the more general scenario with multi-hop traffic, and show that GMM can achieve similar efficiency ratios when a flow-regulator is used at each hop.
Original language | English |
---|---|
Article number | 5308440 |
Pages (from-to) | 2734-2744 |
Number of pages | 11 |
Journal | IEEE Transactions on Automatic Control |
Volume | 54 |
Issue number | 12 |
DOIs | |
Publication status | Published - 2009 Dec |
Externally published | Yes |
Bibliographical note
Funding Information:Manuscript received August 14, 2008; revised April 03, 2009. First published November 03, 2009; current version published December 09, 2009. This paper was presented in part at the IEEE CDC’07 .This work was supported in part by ARO MURI Awards W911NF-07-10376 (SA08-03) and W911NF-08-1-0238, and NSF Awards CNS-0626703, CNS-0721236, ANI-0207728, and CCF-0635202, USA, and in part by IT Scholarship Program supervised by IITA and MIC, Korea. Recommended by Associate Editor S. Mascolo.
Keywords
- Efficiency ratio
- Greedy maximal matching (GMM)
- Local-pooling factor
- Wireless scheduling
ASJC Scopus subject areas
- Control and Systems Engineering
- Computer Science Applications
- Electrical and Electronic Engineering