Q-CSMA: Queue-Length Based CSMA/CA Algorithms for Achieving Maximum Throughput and Low Delay in Wireless Networks
arXiv:0901.2333 · doi:10.1109/TNET.2011.2177101
Abstract
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.
arXiv comment12 pages
Cited by in corpus (19)
- Distributed Throughput-optimal Scheduling in Ad Hoc Wireless Networks
- Massive MIMO CSI Feedback using Channel Prediction: How to Avoid Machine Learning at UE?
- Explicit back-off rates for achieving target throughputs in CSMA/CA networks
- A Learning-based Distributed Algorithm for Scheduling in Multi-hop Wireless Networks
- Hybrid Scheduling in Heterogeneous Half- and Full-Duplex Wireless Networks
- Leveraging Physical Layer Capabilites: Distributed Scheduling in Interference Networks with Local Views
- Wireless Power Transfer and Data Collection in Wireless Sensor Networks
- Distributed Policy Learning Based Random Access for Diversified QoS Requirements
- Efficient CSMA using Regional Free Energy Approximations
- Throughput-optimal Scheduling in Multi-hop Wireless Networks without Per-flow Information
- Closed-Form Whittle's Index-Enabled Random Access for Timely Status Update
- Improving Multiresource Job Scheduling with Markovian Service Rate Policies
- Technique Report: Scheduling Flows with Multiple Service Frequency Constraints
- Exploiting the Past to Reduce Delay in CSMA Scheduling: A High-order Markov Chain Approach
- A Common Information-Based Multiple Access Protocol Achieving Full Throughput and Linear Delay
- Throughput Optimal Random Medium Access Control for Relay Networks with Time-Varying Channels
- Energy Efficient and Throughput Optimal CSMA Scheme
- Free Energy Approximations for CSMA networks
- Exploiting Social Tie Structure for Cooperative Wireless Networking: A Social Group Utility Maximization Framework