Timely Wireless Flows With General Traffic Patterns: Capacity Region and Scheduling Algorithms
Open Access
- 25 September 2017
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 25 (6), 3473-3486
- https://doi.org/10.1109/tnet.2017.2749513
Abstract
Most existing wireless networking solutions are best-effort and do not provide any delay guarantee required by important applications, such as mobile multimedia conferencing and real-time control of cyber-physical systems. Recently, Hou and Kumar provided a novel framework for analyzing and designing delay-guaranteed wireless networking solutions. While inspiring, their idle-time-based analysis applies only to flows with a special traffic pattern called the frame-synchronized setting. The problem remains largely open for general traffic patterns. This paper addresses this challenge by proposing a general framework that characterizes and achieves the complete delay-constrained capacity region with general traffic patterns in single-hop downlink access-point wireless networks. We first show that the timely wireless flow problem is fundamentally an infinite-horizon Markov decision process (MDP). Then, we judiciously combine different simplification methods to prove that the timely capacity region can be characterized by a finite-size convex polygon. This for the first time allows us to characterize the timely capacity region of wireless flows with general traffic patterns. We then design three scheduling policies to optimize network utility and/or support feasible timely throughput vectors for general traffic patterns. The first policy achieves the optimal network utility and supports any feasible timely throughput vector but suffers from the curse of dimensionality. The second and third policies are inspired by our MDP framework and are of much lower complexity. Simulation results show that both achieve near-optimal performance and outperform other existing alternatives.Keywords
Funding Information
- NSF (ECCS-1407603, CCF-1422997, CCF-1618475)
- National Basic Research Program of China (2013CB336700)
- University Grants Committee, Hong Kong Special Administrative Region, China (2150871)
- Innovation and Technology Committee, Hong Kong Special Administrative Region, China (14201014)
This publication has 24 references indexed in Scilit:
- Delay-constrained capacity for broadcast erasure channels: A linear-coding-based studyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2016
- Timely wireless flows with arbitrary traffic patterns: Capacity region and scheduling algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2016
- On the Capacity Requirement of Largest-Deficit-First for Scheduling Real-Time Traffic in Wireless NetworksPublished by Association for Computing Machinery (ACM) ,2015
- Video telephony for end-consumersPublished by Association for Computing Machinery (ACM) ,2012
- Q-CSMA: Queue-Length-Based CSMA/CA Algorithms for Achieving Maximum Throughput and Low Delay in Wireless NetworksIEEE/ACM Transactions on Networking, 2011
- Scheduling for Optimal Rate Allocation in Ad Hoc Networks With Heterogeneous Delay ConstraintsIEEE Journal on Selected Areas in Communications, 2011
- A Distributed CSMA Algorithm for Throughput and Utility Maximization in Wireless NetworksIEEE/ACM Transactions on Networking, 2009
- Markov Decision Processes with Multiple Long-Run Average ObjectivesLecture Notes in Computer Science, 2007
- Accuracy of state space collapse for earliest-deadline-first queuesThe Annals of Applied Probability, 2006
- Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networksIEEE Transactions on Automatic Control, 1992