Optimal scheduling algorithms for ad hoc wireless networks

It is well known that the MaxWeight scheduling algorithm is throughput-optimal in wireless networks. However, its complexity is exponential in the number of links in an ad hoc network. In this work, we consider a greedy variant of the MaxWeight algorithm, called Longest Queue First (LQF). A synchronous version of LQF is known to be throughput-optimal under a topological condition called local pooling. Here we study an asynchronous version of LQF which is suitable for implementation in networks with variable packet sizes. We show that asynchronous LQF is also throughput-optimal under the local pooling condition.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Maguluri, Siva Theja

Contributors dc:contributor

• Hajek, Bruce
• Srikant, Rayadurgam

• Adhoc Networks
• Scheduling
• Wireless
• Lyapunov
• optimal

Statement dc:rights

• Copyright 2010 Siva Theja Maguluri

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/24097

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/24097