STABILITY CONDITIONS FOR A DISCRETE-TIME DECENTRALISED MEDIUM ACCESS ALGORITHM

• 成果类型: Article
• 署名作者: Shneer, Seva; Stolyar, Alexander
• 署名单位: Heriot Watt University; University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/18-AAP1398
• 发表日期: 2018
• 页码: 3600-3628
• 关键词: queuing-networks; radio networks; systems; performance; Throughput; fairness

摘要

We consider a stochastic queueing system modelling the behaviour of a wireless network with nodes employing a discrete-time version of the standard decentralised medium access algorithm. The system is unsaturated-ach node receives an exogenous flow of packets at the rate of. packets per time slot. Each packet takes one slot to transmit, but neighbouring nodes cannot transmit simultaneously. The algorithm we study is standard in the following sense: a node with an empty queue does not compete for medium access; the access procedure by a node does not depend on its queue length as long as it is nonzero. Two system topologies are considered, with nodes arranged in a circle and in a line. We prove that, for either topology, the system is stochastically stable under the condition lambda < 2/5. This result is intuitive for the circle topology as the throughput each node receives in the saturated system (with infinite queues) is equal to the so-called parking constant, which is larger than 2/5. (This fact, however, does not help us to prove the result.) The result is not intuitive for the line topology as in the saturated system some nodes receive a throughput lower than 2/5.