Local greedy approximation for scheduling in multihop wireless networks

Changhee Joo, Ness B. Shroff

Research output: Contribution to journalArticlepeer-review

29 Citations (Scopus)


In recent years, there has been a significant amount of work done in developing low-complexity scheduling schemes to achieve high performance in multihop wireless networks. A centralized suboptimal scheduling policy, called Greedy Maximal Scheduling (GMS) is a good candidate because its empirically observed performance is close to optimal in a variety of network settings. However, its distributed realization requires high complexity, which becomes a major obstacle for practical implementation. In this paper, we develop simple distributed greedy algorithms for scheduling in multihop wireless networks. We reduce the complexity by relaxing the global ordering requirement of GMS, up to near zero. Simulation results show that the new algorithms approximate the performance of GMS, and outperform the state-of-the-art distributed scheduling policies.

Original languageEnglish
Article number5714691
Pages (from-to)414-426
Number of pages13
JournalIEEE Transactions on Mobile Computing
Issue number3
Publication statusPublished - 2012 Mar
Externally publishedYes

Bibliographical note

Funding Information:
This work was in part supported by US National Science Foundation projects CNS-0721236 and CNS-1012700, ARO MURI project W911NF-08-1-0238, and in part by the year of 2011 Research Fund of the UNIST (Ulsan National Institute of Science and Technology) and the Basic Science Research Program through the National Research Foundation of Korea (NRF), funded by the Ministry of Education, Science, and Technology (No. 2011-0008549). A preliminary version of this work was presented at ACM MobiHoc 2008 [1].


  • Wireless scheduling
  • distributed system
  • greedy algorithm

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Local greedy approximation for scheduling in multihop wireless networks'. Together they form a unique fingerprint.

Cite this