Introduction
In modern cellular networks, the primary metric of user experience has shifted from simple packet-level throughput to the successful completion of "flows"—entire files or video segments—before a strict deadline. For applications like video streaming or file pre-caching, partially downloaded data is often useless if the buffer empties before the flow completes. This creates a fundamental challenge known as the Urgency-Diversity Tradeoff. A base station must decide whether to serve users with the best current channel conditions to maximize total throughput (multi-user diversity) or prioritize users whose deadlines are imminent, even if their signal is currently weak (urgency).
Traditional scheduling policies like Proportional Fair ignore deadlines entirely, while classic real-time algorithms like Earliest Deadline First (EDF) ignore the volatile nature of wireless channels. This paper introduces the $L^2HPR$ (Less-Laxity-Higher-Possible-Rate) policy to bridge this gap, providing a framework that balances channel efficiency with flow-level dynamics.
The $L^2HPR$ Policy and Heuristics
The core innovation of this work is the use of Expected Laxity as a scheduling metric. Expected laxity is defined as the time remaining until a user's deadline minus the time required to finish their task, assuming they were granted the full channel capacity.
Theoretical Foundation
The $L^2HPR$ policy is designed for an idealized system where the capacity region is a polymatroid. It operates by sorting active users by their expected laxity and allocating higher data rates to those with lower laxity (higher urgency). The authors prove that $L^2HPR$ is asymptotically optimal for underloaded systems, meaning that as time slot lengths approach zero, it performs as well as an "offline" policy with perfect future knowledge.
Practical Implementation
To address real-world constraints like discrete time slots and varying channel states, the authors propose several heuristic variants:
- L-MaxWeight, L-Exp, and L-Log: These map laxity to urgency weights using polynomial, exponential, and logarithmic functions, respectively.
- Admission Control: The framework incorporates a threshold ($\delta$). If a user's laxity drops below this threshold, the system identifies them as likely to fail and stops allocating resources to them. This prevents "wasting" bandwidth on lost causes, ensuring other users can still meet their deadlines.
Performance Evaluation
The proposed policies were evaluated using numerical simulations of Rayleigh fading channels and an FTP traffic model (truncated lognormal distribution, mean 2MB). The study compared $L^2HPR$ and its heuristics against standard greedy policies like Max C/I and deadline-only policies like EDF and Least-Laxity-First (LLF).
Schedulability and Reliability
A key finding is the superior "schedulability" of laxity-based approaches. In scenarios with both identical deadlines and stationary Poisson arrivals, $L^2HPR$ consistently scheduled more sets of users than any other policy.
As shown in Figure 2, $L^2HPR$ (red bars) significantly outperforms the greedy Max C/I policy, especially when deadlines are tight (low $D$ or low stretch factor $\xi$). In many cases, it was the only policy capable of finding a feasible schedule for the given realizations.
Deadline Violation Probability
The policies also demonstrated a marked reduction in the probability of deadline violations ($P_{viol}$). While channel-oblivious policies like LLF and EDF performed poorly due to their tendency to waste bandwidth on users with poor channel states, the laxity-based heuristics maintained high reliability.
Figure 5 illustrates that $L^2HPR$ (dashed red line) achieves the lowest violation probability across all tested parameters. In stationary arrival systems, the proposed policies reduced $P_{viol}$ to approximately 25% of the levels seen with the standard Max C/I policy. The heuristics L-MaxWeight and L-Exp proved particularly robust, outperforming greedy approaches that require significantly more "slack" time to achieve comparable reliability.
Conclusion
$L^2HPR$ provides a theoretically grounded and practically effective solution for wireless scheduling with flow-level deadlines. By using expected laxity to navigate the urgency-diversity tradeoff, the policy maximizes both network efficiency and user satisfaction. Future work remains in optimizing performance for intentionally overloaded systems and exploring "soft deadlines" where partial utility can be derived from incomplete flows.
Summary updated