Improved Bounds on the Throughput Efficiency of Greedy Maximal Scheduling in Wireless Networks

Author

Leconte, Mathieu ; Ni, Jian ; Srikant, R.

Author_Institution

Technicolor, INRIA, Paris, France

Volume

19

Issue

3

fYear

2011

fDate

6/1/2011 12:00:00 AM

Firstpage

709

Lastpage

720

Abstract

In this paper, we derive new bounds on the throughput efficiency of Greedy Maximal Scheduling (GMS) for wireless networks of arbitrary topology under the general k -hop interference model. These results improve the known bounds for networks with up to 26 nodes under the 2-hop interference model. We also prove that GMS is throughput-optimal in small networks. In particular, we show that GMS achieves 100% throughput in networks with up to eight nodes under the 2-hop interference model. Furthermore, we provide a simple proof to show that GMS can be implemented using only local neighborhood information in networks of any size.

Keywords

radio networks; radiofrequency interference; scheduling; 2-hop interference model; arbitrary topology; greedy maximal scheduling; k-hop interference model; local neighborhood information; small networks; throughput efficiency; wireless networks; Computational modeling; Interference; Numerical models; Schedules; Scheduling algorithm; Throughput; Wireless networks; Greedy Maximal Scheduling (GMS); Longest Queue First (LQF); throughput optimality; wireless networks;

fLanguage

English

Journal_Title

Networking, IEEE/ACM Transactions on

Publisher

ieee

ISSN

1063-6692

Type

jour

DOI

10.1109/TNET.2010.2089534

Filename

5635377