## Files in this item

FilesDescriptionFormat

application/pdf

 Title: Fundamental limits of random access in wireless networks Author(s): Ghaderi Dehkordi, Javad Director of Research: Srikant, Rayadurgam Doctoral Committee Chair(s): Srikant, Rayadurgam Doctoral Committee Member(s): Hajek, Bruce; Nedich, Angelia; Shroff, Ness B.; Viswanath, Pramod Department / Program: Electrical & Computer Eng Discipline: Electrical & Computer Engr Degree Granting Institution: University of Illinois at Urbana-Champaign Degree: Ph.D. Genre: Dissertation Subject(s): Wireless Networks Distributed Algorithms Scheduling Stability Instability Markov Chains Mixing Time Fluid Limits Abstract: 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. Issue Date: 2013-08-22 URI: http://hdl.handle.net/2142/45341 Rights Information: Copyright 2013 Javad Ghaderi Dehkordi Date Available in IDEALS: 2013-08-22 Date Deposited: 2013-08