Low Complexity Scheduling in Wireless Networks

Scheduling complexity is an important bottleneck in the efficient design and controlof wireless networks. Owing to the high computational complexity of throughputoptimallink schedulers, low-complexity schedulers such as Greedy Maximal Scheduling(GMS)that often yield good throughput performance have received significantattention in the recent past, with the performance of GMS having been characterizedusing the Local Pooling Factor (LPF) of a network graph.Unlike optimal scheduling however, the insights and performance guarantees of lowcomplexity scheduling policies are restricted to specific network models and do notgeneralize easily. In this dissertation, motivated by a desire to understand cross-layerproperties of greedy link scheduling, we develop and analyze low complexity greedyschedulers for wireless networks under various physical layer scenarios. One suchscenario incorporates developments in multi-user information theory. Informationtheoretic Broadcast Channels (BC) and Multiple Access Channels (MAC) enable asingle node to transmit data simultaneously to multiple nodes, and multiple nodesto transmit data simultaneously to a single node respectively. For wireless networkscontaining nodes with BC and MAC capabilities, we develop a greedy schedulingpolicy and show that the performance of our algorithm can be characterized usingthe associated parameter, the multiuser local pooling factor. We use the multiuserlocal pooling factor to demonstrate the improvement in throughput performance someexamples of network graphs with BCs and MACs. We also identify cross-layer design issues governing the performance of greedy algorithms in such wireless networks.While previous work on link scheduling has extensively focused on wireless networkswith static link rates, we also investigate the performance of greedy schedulersin wireless networks with fading channels. We show that the performance of a greedyscheduler in wireless networks with fading channels can be characterized using theLPF of an associated static network graph. Finally, we motivate the LPF as a crosslayer parameter, by proposing an energy efficient joint greedy scheduling and powercontrol policy for wireless networks with average power constraints.Thus, the central theme of the dissertation is that by adopting an appropriatechoice of algorithm and cross-layer design, the performance guarantees of greedyalgorithms can be extended to network models that capture a wide variety of physicallayer scenarios.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

doctoral

Discipline thesis:degree_discipline

Electrical and Computer Engineering

Grantor dc:publisher

The Ohio State University

Year dc:date

2013

Author dc:creator

• Sridharan, Arun

Contributors dc:contributor

• Koksal, Can Emre

• Engineering
• Electrical Engineering

Statement dc:rights

• unrestricted
• This thesis or dissertation is protected by copyright: all rights reserved. It may not be copied or redistributed beyond the terms of applicable copyright laws.

Language dc:language

English

Repository record dc:identifier

http://rave.ohiolink.edu/etdc/view?acc_num=osu1366072589

OAI identifier oai:identifier

oai:etd.ohiolink.edu:osu1366072589