Application-Level Scheduling With Probabilistic Deadline Constraints

作者：Wu, Huasen^*; Lin, Xiaojun; Liu, Xin; Zhang, Youguang

来源：IEEE/ACM Transactions on Networking, 2016, 24(3): 1504-1517.

DOI：10.1109/TNET.2015.2416256

• Asymptotically optimal policies
• deadline constraints
• wireless scheduling

Opportunistic scheduling of delay-tolerant traffic has been shown to substantially improve spectrum efficiency. To encourage users to adopt delay-tolerant scheduling for capacity-improvement, it is critical to provide guarantees in terms of completion time. In this paper, we study application-level scheduling with deadline constraints, where the deadline is pre-specified by users/applications and is associated with a deadline violation probability. To address the exponentially-high complexity due to temporally-varying channel conditions and deadline constraints, we develop a novel asymptotic approach that exploits the largeness of the network to our advantage. Specifically, we identify a lower bound on the deadline violation probability, and propose simple policies that achieve the lower bound in the large-system regime. The results in this paper thus provide a rigorous analytical framework to develop and analyze policies for application-level scheduling under very general settings of channel models and deadline requirements. Further, based on the asymptotic approach, we propose the notion of Application-Level Effective Capacity region, i.e., the throughput region that can be supported subject to deadline constraints, which allows us to quantify the potential gain of application-level scheduling. Simulation results show that application-level scheduling can improve the system capacity significantly while guaranteeing the deadline constraints.

• 出版日期2016-6
• 单位北京航空航天大学