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