Distributed queue-length based algorithms for optimal end4o-end throughput allocation and stability in multi-hop random access networks

We consider a model of wireless network with random (slotted-Aloha-type) access and with multi-hop flow routes. The goal is to devise distributed strategies for optimal utility-based end-to-end throughput allocation and queueing stability. We consider a class of queue back-pressure random - Access algorithms (QBRA), where actual queue lengths of the flows (in each node's close neighborhood) are used to determine nodes' channel access probabilities. This is in contrast to previously proposed algorithms, which are purely optimization-based and oblivious of actual queues. QBRA is also substantially different from much studied "MaxWeight" type scheduling algorithms, also using back-pressurE. For the model with infinite backlog at each flow source, we show that QBRA, combined with simple congestion control local to each source, leads to optimal end-to-end throughput allocation, within the network saturation throughput region achievable by a random access. ( o end-to-end message passing is required.) This scheme generalizes for the case of additional, minimum flow rate constraints. For the model with stochastic exogenous arrivals, we show that QBRA ensures stability of the queues as long as nominal loads of the nodes are within the saturation throughput region. Simulation comparison of QBRA and (queue oblivious) optimization-based random access algorithms, shows that QBRA performs better in terms of end-to-end delays.