Fundamental limits of random access in wireless networks

Random access schemes are simple and inherently distributed, yet could provide the striking capability to match the optimal throughput performance (maximum stability region) of centralized scheduling mechanisms. The throughput optimality however has been established for activation rules that are relatively sluggish, and may yield excessive queues and delays. More aggressive/persistent access schemes have the potential to improve the delay performance, but it is not clear if they can offer any universal throughput optimality guarantees. In this thesis, we identify a fundamental limit on the aggressiveness of nodes, beyond which instability is bound to occur in a broad class of networks. We will mainly consider adapting transmission lengths by considering a weight for each node as a function of its queue size. The larger the weight, the longer the node will hold on to the channel once it starts a transmission. We first show that it is sufficient for weights to behave as logarithmic functions of the queue sizes, divided by an arbitrarily slowly increasing function. This result indicates that the maximum-stability guarantees are preserved for weights that are essentially logarithmic for all practical queue sizes, although asymptotically the weight must grow slower than any logarithmic function of the queue size. We then demonstrate instability for weights that grow faster than logarithmic functions of queue sizes in networks with sufficiently many nodes. Our stability and instability results hence imply that the ``near-logarithmic growth condition'' on the weights is a fundamental limit on the aggressiveness of nodes to ensure maximum stability in any general topology. We will conduct simulation experiments to illustrate and validate the analytical results. Finally, we will combine the random access scheme with window-based flow control mechanisms to provide maximum throughput and Quality-of-Service in multihop wireless networks with dynamic flows.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2013

Author dc:creator

• Ghaderi Dehkordi, Javad

Contributors dc:contributor

• Srikant, Rayadurgam
• Hajek, Bruce
• Nedich, Angelia
• Shroff, Ness B.
• Viswanath, Pramod

• Wireless Networks
• Distributed Algorithms
• Scheduling
• Stability
• Instability
• Markov Chains
• Mixing Time
• Fluid Limits

Statement dc:rights

• Copyright 2013 Javad Ghaderi Dehkordi

Language dc:language

en

Handle dc:identifier

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

OAI identifier oai:identifier

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