{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/14629"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/14629","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"On the throughput efficiency of greedy maximal scheduling in wireless ad hoc networks","abstract":"Due to its low complexity, Greedy Maximal Scheduling (GMS), also known as Longest Queue First (LQF), has been studied extensively for wireless networks. However, GMS can result in degraded throughput performance in general wireless networks. In this thesis, we derive performance bounds of GMS for wireless networks under the general k-hop interference model. In particular, we prove that GMS achieves 100% throughput in all networks with eight nodes or less, under the two-hop interference model. Further, the obtained performance bounds improve upon previous results for larger networks up to a certain size. We also provide a simple proof to show that GMS can be implemented using only local neighborhood information in networks of any size.","abstract_html":"Due to its low complexity, Greedy Maximal Scheduling (GMS), also known as Longest Queue First (LQF), has been studied extensively for wireless networks. However, GMS can result in degraded throughput performance in general wireless networks. In this thesis, we derive performance bounds of GMS for wireless networks under the general k-hop interference model. In particular, we prove that GMS achieves 100% throughput in all networks with eight nodes or less, under the two-hop interference model. Further, the obtained performance bounds improve upon previous results for larger networks up to a certain size. We also provide a simple proof to show that GMS can be implemented using only local neighborhood information in networks of any size.","abstract_has_math":false,"creators":["Leconte, Mathieu"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Srikant, Rayadurgam"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010-01-06T16:20:06Z","date_published":"2010-01-06T16:20:06Z","updated_at":"2026-07-22T22:25:07Z","subjects":["Greedy Maximal Scheduling","Longest Queue First","wireless network","throughput optimality","throughput efficiency"],"languages":["en"],"rights":["Copyright 2009 Mathieu Leconte"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/14629","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Srikant, Rayadurgam"]},{"key":"dc:creator","label":"Author","values":["Leconte, Mathieu"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2010-01-06T16:20:06Z","2009-12"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Greedy Maximal Scheduling","Longest Queue First","wireless network","throughput optimality","throughput efficiency"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2009 Mathieu Leconte"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/14629"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Due to its low complexity, Greedy Maximal Scheduling (GMS), also known as Longest Queue First (LQF), has been studied extensively for wireless networks. However, GMS can result in degraded throughput performance in general wireless networks. In this thesis, we derive performance bounds of GMS for wireless networks under the general k-hop interference model. In particular, we prove that GMS achieves 100% throughput in all networks with eight nodes or less, under the two-hop interference model. Further, the obtained performance bounds improve upon previous results for larger networks up to a certain size. We also provide a simple proof to show that GMS can be implemented using only local neighborhood information in networks of any size.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2009-11-18T14:46:40Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Leconte_Mathieu.pdf: 253137 bytes, checksum: adaa8355ecea700ed754d19d51136c67 (MD5)","Made available in DSpace on 2010-01-06T16:20:06Z (GMT). No. of bitstreams: 2 license.txt: 4065 bytes, checksum: 8a903a05156264e0f4f982cc5bc4fcaa (MD5) Leconte_Mathieu.pdf: 253137 bytes, checksum: adaa8355ecea700ed754d19d51136c67 (MD5)"]},{"key":"dc:title","label":"Title","values":["On the throughput efficiency of greedy maximal scheduling in wireless ad hoc networks"]}]}],"canonical_facts":{"dc:contributor":["Srikant, Rayadurgam"],"dc:creator":["Leconte, Mathieu"],"dc:date":["2010-01-06T16:20:06Z","2009-12"],"dc:description":["Due to its low complexity, Greedy Maximal Scheduling (GMS), also known as Longest Queue First (LQF), has been studied extensively for wireless networks. However, GMS can result in degraded throughput performance in general wireless networks. In this thesis, we derive performance bounds of GMS for wireless networks under the general k-hop interference model. In particular, we prove that GMS achieves 100% throughput in all networks with eight nodes or less, under the two-hop interference model. Further, the obtained performance bounds improve upon previous results for larger networks up to a certain size. We also provide a simple proof to show that GMS can be implemented using only local neighborhood information in networks of any size.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2009-11-18T14:46:40Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Leconte_Mathieu.pdf: 253137 bytes, checksum: adaa8355ecea700ed754d19d51136c67 (MD5)","Made available in DSpace on 2010-01-06T16:20:06Z (GMT). No. of bitstreams: 2 license.txt: 4065 bytes, checksum: 8a903a05156264e0f4f982cc5bc4fcaa (MD5) Leconte_Mathieu.pdf: 253137 bytes, checksum: adaa8355ecea700ed754d19d51136c67 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/14629"],"dc:language":["en"],"dc:rights":["Copyright 2009 Mathieu Leconte"],"dc:subject":["Greedy Maximal Scheduling","Longest Queue First","wireless network","throughput optimality","throughput efficiency"],"dc:title":["On the throughput efficiency of greedy maximal scheduling in wireless ad hoc networks"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:07Z"}