Source-linked AI summary
Q-CSMA: Queue-Length Based CSMA/CA Algorithms for Achieving Maximum Throughput and Low Delay in Wireless Networks
Jian Ni, Bo Tan, R. Srikant
TL;DR
The paper addresses the gap between throughput-optimal but delay-poor CSMA methods and low-delay heuristics that may sacrifice capacity. It proposes a discrete-time distributed Q-CSMA framework based on generalized Glauber dynamics, with collision-free scheduling and queue-length-dependent updates. The paper reports throughput-optimality while allowing delay-reduction mechanisms, including a hybrid with distributed GMS that achieves very good delay performance.
Problem
Existing CSMA methods can be throughput-optimal but may have poor delay and rely on idealized collision-free continuous-time assumptions, while GMS-like heuristics may achieve only part of capacity generally.
Method
The paper proposes a discrete-time distributed Q-CSMA algorithm based on generalized Glauber dynamics, where multiple links update during control slots to produce data-transmission schedules.
Results
Q-CSMA is provably throughput-optimal, and combining it with distributed GMS provides very good delay performance while retaining theoretical throughput-optimality.
Takeaways & Limitations
The framework supports collision-free distributed scheduling with delay-reduction mechanisms and addresses hidden and exposed terminal problems.
Abstract
from arXiv · showhide
Recently, it has been shown that CSMA-type random access algorithms can achieve the maximum possible throughput in ad hoc wireless networks. However, these algorithms assume an idealized continuous-time CSMA protocol where collisions can never occur. In addition, simulation results indicate that the delay performance of these algorithms can be quite bad. On the other hand, although some simple heuristics (such as distributed approximations of greedy maximal scheduling) can yield much better delay performance for a large set of arrival rates, they may only achieve a fraction of the capacity region in general. In this paper, we propose a discrete-time version of the CSMA algorithm. Central to our results is a discrete-time distributed randomized algorithm which is based on a generalization of the so-called Glauber dynamics from statistical physics, where multiple links are allowed to update their states in a single time slot. The algorithm generates collision-free transmission schedules while explicitly taking collisions into account during the control phase of the protocol, thus relaxing the perfect CSMA assumption. More importantly, the algorithm allows us to incorporate mechanisms which lead to very good delay performance while retaining the throughput-optimality property. It also resolves the hidden and exposed terminal problems associated with wireless networks.
I. INTRODUCTION
The paper targets wireless scheduling that combines maximum throughput, low delay, distributed operation, and low complexity despite interference and imperfect CSMA assumptions.
- Motivation: MWS is throughput-optimal but requires solving a complex combinatorial optimization problem each time slot.
- Motivation: GMS often offers good throughput and delay with low computational complexity, but may lose capacity and incur increasing decentralization overhead.
- Prior approaches: CSMA-type random access is distributed and practical, but prior continuous-time models assume zero sensing delay, no hidden terminals, and collision-free operation.
- Contribution: The paper designs a discrete-time CSMA algorithm based on generalized Glauber dynamics, allowing multiple links to update in one slot.
- Contribution: The formulation quantifies throughput loss using the control-slot/data-slot duration ratio and incorporates delay reduction while addressing hidden and exposed terminals.
- Paper organization: The paper develops a basic scheduling algorithm, Q-CSMA, and a hybrid Q-CSMA combining Q-CSMA with distributed GMS.
III. THE BASIC SCHEDULING ALGORITHM
The basic algorithm generates transmission schedules through randomized control decisions and preserves feasibility over time. Its schedule process is a discrete-time Markov chain with product-form stationary behavior under stated conditions.
- Algorithm: Each time slot has a control slot for selecting a feasible decision schedule and a data slot that uses the resulting collision-free transmission schedule.
- Algorithm: The network randomly selects a feasible decision schedule m(t), and selected links update using activation probabilities conditioned on conflicting links’ previous activity.
- Feasibility: The generated transmission schedule remains feasible whenever the previous transmission schedule and current decision schedule are feasible.
- Markov-chain analysis: Transmission schedules evolve as a discrete-time Markov chain, with transitions determined by state changes contained in a feasible decision schedule.
- Markov-chain analysis: If the possible decision schedules cover every link, the chain is irreducible and aperiodic.
- Stationary distribution: Under the same coverage condition, the chain is reversible and has the stated product-form stationary distribution.
A. Comments On Throughput-Optimality
Throughput-optimality follows by making activation probabilities depend appropriately on queue-length-based link weights, so high-weight schedules are favored in steady state.
- Throughput-optimality: Choosing activation probabilities as functions of queue lengths allows throughput-optimality arguments based on the product-form schedule distribution.
- Throughput-optimality: The steady-state probability of selecting a schedule is proportional to its weight, favoring schedules with larger weight.
- Throughput-optimality: Queue-weight functions can be chosen so the schedule chain converges faster than link-weight dynamics, under the stated time-scale-separation assumption.
- Throughput-optimality: With p_i = e^w_i(t)/(e^w_i(t)+1) and appropriate queue-length weight functions, the scheduling algorithm is throughput-optimal.
- Throughput-optimality: When queue lengths become sufficiently large, the chain selects sufficiently high-weight schedules with high probability, satisfying the throughput-optimality criterion.
IV. DISTRIBUTED IMPLEMENTATION: Q-CSMA
Q-CSMA is a distributed discrete-time implementation that uses randomized control mini-slots and carrier sensing to produce feasible schedules while retaining throughput-optimality. Its signaling overhead is constant in network size, with data-slot efficiency approaching full capacity when control overhead is small.
- Distributed implementation: Q-CSMA selects a feasible decision schedule through a distributed randomized procedure in control mini-slots, then determines data-slot states using carrier sensing and activation probabilities.Each link sends at most one INTENT message during the control slot.
- Collision handling: Colliding INTENT messages exclude the involved links, while collision-free messages include links in the decision schedule and silence their conflicting neighbors.This construction ensures that every generated transmission schedule is feasible.
- Throughput optimality: For W ≥2, Q-CSMA has a product-form stationary distribution and is throughput-optimal when activation probabilities use queue-length-based link weights.The activation probabilities are specified as pi = e^wi(t)/(e^wi(t)+1).
- Overhead and implementation: Q-CSMA's control overhead is constant and independent of network size, and its achievable capacity fraction D/(D+W) approaches full capacity when W ≪D.A modified procedure can also obtain the product-form distribution with W = 1.
- Node-level implementation: Node-level implementation uses carrier sensing and control/data transmissions to address hidden and exposed terminal problems.The paper provides implementation details based on sender and receiver nodes.
V. A LOW-DELAY HYBRID Q-CSMA ALGORITHM
Existing CSMA methods can be throughput-optimal but have poor delay, whereas GMS can provide good delay yet is centralized and not throughput-optimal in general. The paper therefore develops a distributed approximation of GMS as a component for combining these properties.
- Design objective: The paper designs a distributed scheduling algorithm intended to combine Q-CSMA's maximum throughput with GMS's low delay.This motivates a hybrid approach rather than relying exclusively on either algorithm.
- D-GMS: D-GMS approximates GMS by assigning smaller backoff times to links with larger queue lengths and adding collision resolution for equal queue lengths.The authors also use simulations to reduce D-GMS control overhead while retaining control when queues become large.
1. Link i selects a random backoff time
The hybrid algorithm first applies Q-CSMA to links above a weight threshold and then applies D-GMS to the remaining links. It uses staged control mini-slots and one-bit neighbor-activity memory to coordinate the two procedures.
- D-GMS procedure: A link that hears a neighboring RESV message becomes silent, while a link without such a message sends RESV and is scheduled if no collision occurs.Scheduled links transmit packets in the data slot.
- Control overhead: D-GMS uses W × B control mini-slots, while the hybrid procedure has overhead W0 + 1 + W1 × B per time slot.Links with empty queues remain silent throughout the time slot.
- Hybrid procedure: Hybrid Q-CSMA divides each control slot between Q-CSMA for links with weight greater than w0 and D-GMS for the remaining links.The two stages use W0 mini-slots and W1 × B mini-slots, respectively.
- Coordination: The transition mini-slot lets links not yet scheduled sense whether Q-CSMA activated a conflicting neighbor and record that information in their NA bit.Links already scheduled send RESV messages during this mini-slot.
- Thresholding: For increasing queue-based weights, the threshold comparison wi(t) ≷w0 is equivalent to comparing queue length qi(t) with q0 = f^-1(w0).The threshold therefore separates links according to queue length when wi(t) = fi(qi(t)).
A. Throughput-Optimality of Hybrid Q-CSMA Algorithm
The throughput analysis separates links handled by Q-CSMA from those handled by D-GMS and establishes a product-form distribution for the Q-CSMA portion. Under the stated activation probabilities and assumptions, the hybrid algorithm is throughput-optimal.
- Partitioning: The hybrid algorithm partitions links into L with wi(t) > w0 and Lc, scheduling L first so later scheduling of Lc does not affect Q-CSMA's operation.The neighboring-link NA bits do not record transmissions from Lc.
- Stationary distribution: For W0 ≥2, the transmission schedule restricted to L is a reversible discrete-time Markov chain with a product-form stationary distribution.The feasible schedules in this distribution are restricted to links in L.
- Throughput optimality: Assuming time-scale separation and choosing pi = e^wi(t)/(e^wi(t)+1), the hybrid Q-CSMA algorithm is throughput-optimal.The weights are appropriate functions of queue lengths.
- Proof strategy: The proof establishes throughput-optimality by showing that the hybrid algorithm satisfies the condition of Theorem 1.The argument uses the Q-CSMA portion's behavior when queue lengths are sufficiently large.
- Heuristic component: D-GMS can be replaced by another heuristic without losing throughput-optimality, although D-GMS is used because it approximates GMS and has performed well in prior simulations.GMS itself is not distributed, motivating the distributed approximation.
VI. SIMULATION RESULTS
The simulations compare centralized and distributed scheduling algorithms, including distributed maximal-scheduling variants and Q-CSMA-based methods.
- The evaluation includes MWS for small networks, centralized GMS, D-GMS, Q-CSMA, Hybrid Q-CSMA, and distributed maximal scheduling D-MS.D-MS is a synchronized slotted approximation of IEEE 802.11 DCF with RTS/CTS and a special case of D-GMS.
- D-MS is specified as a link-level algorithm operating at each time slot.
1. Link i selects a random backoff time
The 24-link grid experiments use distributed scheduling with fixed control overhead and compare queue-length behavior across traffic intensities.
- A. A 24-Link Grid Network: The grid experiment uses a 16-node, 24-link network with one-hop interference and per-link queues.Each link is represented in the topology, and each link maintains its own queue.
- A. A 24-Link Grid Network: Arrival rates are scaled by traffic intensity ρ, with ρ approaching 1 representing rates near the capacity-region boundary.The arrival vector is a convex combination of maximum-size maximal schedules.
- A. A 24-Link Grid Network: Each experiment averages 10 independent Bernoulli-arrival runs of 10^5 time slots, while MWS is omitted because of its high complexity.
- A. A 24-Link Grid Network: All distributed algorithms use 48 control mini-slots, with Q-CSMA using log(0.1q_i(t)) link weights and Hybrid Q-CSMA combining Q-CSMA with D-GMS.Hybrid Q-CSMA uses a queue-length threshold to switch between procedures.
- A. A 24-Link Grid Network: D-GMS and D-MS have lower queues at low-to-moderate traffic, but their queues blow up at high traffic; Hybrid Q-CSMA gives the best distributed delay performance.Hybrid Q-CSMA retains Q-CSMA stability under high traffic while reducing delay, although it approaches pure Q-CSMA as ρ →1.
- A. A 24-Link Grid Network: Centralized GMS has excellent delay performance but is not throughput-optimal in general.
B. A 9-Link Ring Network
The 9-link ring experiment constructs traffic inside the capacity region where GMS is unstable, then compares delay and queue stability across scheduling methods.
- B. A 9-Link Ring Network: Under two-hop interference, GMS achieves only 2/3 of the capacity region in the 9-link ring network.
- B. A 9-Link Ring Network: For the constructed traffic pattern, GMS has infinite queues for every ϵ > 0, even though the arrival rates lie inside the capacity region.
- B. A 9-Link Ring Network: The comparison averages 10 independent experiments of 10^5 time slots for each fixed ϵ, using the parameter settings from the earlier experiment.
- B. A 9-Link Ring Network: Q-CSMA and Hybrid Q-CSMA have lower delay than GMS, D-GMS for ϵ ≥0.03, and D-MS for ϵ ≥0.05.
- B. A 9-Link Ring Network: D-GMS and D-MS queue lengths grow linearly with runtime, whereas Q-CSMA and Hybrid Q-CSMA remain stable.
- VII. CONCLUSION: The paper concludes that combining CSMA with distributed GMS provides very good delay performance without affecting throughput-optimality.
APPENDIX
The node-based implementation uses carrier sensing and RTD/CTD exchanges to construct feasible schedules while addressing wireless-terminal interactions.
- A. Node-Based Implementation of Q-CSMA: Nodes determine neighborhood activity by sensing the channel during data and ACK transmission periods.
- A. Node-Based Implementation of Q-CSMA: A link’s conflict set includes links sharing a node or causing data or ACK collisions under simultaneous transmission.
- A. Node-Based Implementation of Q-CSMA: An INTENT message consists of an RTD/CTD exchange between a link’s sender and receiver, with separate control sub-mini-slots for distinguishing the messages.
- A. Node-Based Implementation of Q-CSMA: The node-based algorithm tracks sender and receiver availability, activity, and neighborhood sender/receiver signals while selecting one outgoing link and a random backoff time.
- A. Node-Based Implementation of Q-CSMA: A link enters the transmission schedule only after successful control exchange and transmits data with an ACK when selected.
- A. Node-Based Implementation of Q-CSMA: For window size W ≥2, the produced schedules are feasible and achieve the product-form distribution.
B. Elimination of Hidden and Exposed Terminal Problems
Q-CSMA uses synchronized RTD/CTD exchanges to produce collision-free decision schedules, eliminating hidden-terminal collisions. It also avoids unnecessary silencing from exposed terminals and removes associated modeling difficulties.
- Synchronized RTD/CTD exchanges ensure that only one link is selected when hidden terminals contend, so the decision and transmission schedules remain collision-free.If one sender’s CTD is not intended for the other, that other sender disables its participation; tied requests are resolved by withholding a CTD from one receiver.
- Q-CSMA eliminates the hidden terminal problem by starting from a collision-free transmission schedule and maintaining collision-free decision schedules.
- Unlike 802.11, Q-CSMA lets a sender ignore an RTD that would not interfere with its potential transmission, allowing both exposed links to be scheduled.
- The RTD/CTD mechanism eliminates efficiency losses and mathematical inconsistencies caused by hidden and exposed terminals in asynchronous RTS/CTS models.In particular, it avoids the difficulty of defining schedules consistent with both feasible-schedule and capacity-region definitions.