Wireless scheduling with deadline and power constraints

Yiqiu Liu, Xin Liu, Lei Ying, R. Srikant

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


This paper studies the problem of scheduling in a collocated wireless network under both deadline and power constraints. We consider a time-slotted system and assume time slots are grouped into frames such that each frame consists of T consecutive time slots. The channel condition of a link remains constant within each frame but varies from frame to frame. Packets with hard deadlines arrive at the transmitters at the beginning of each frame, and will be discarded if missing their deadlines, which are in the same frame. The deadlines can vary from frame to frame. Each link, say link l, is required to deliver at least pl fraction of packets on time with the average transmit power not exceeding βl. To guarantee both constraints, each link maintains two virtual queues, a deficit queue and a power queue, to keep track of the progresses of fulfilling these two constraints, respectively. A MaxWeight-type problem based on the virtual queues is first formulated in this paper for achieving throughput optimality. The computational complexity of solving the MaxWeight-type problem using exhaustive search is exponential in the frame size, which is prohibitive even for a small value of T. To overcome this difficulty, we propose a greedy algorithm, named PDMax (Power and Deadline constrained MaxWeight), with complexity O (LT log(LT)). PDMax schedules packets according to their deadlines and incremental weight gains to the objective of the MaxWeight problem which includes both deficit queues and power queues. The incremental weight gains are calculated by solving an optimal power control problem defined for a single link. We prove PDMax is throughput optimal. Our simulations further show that PDMax outperforms both Large-Deficit-First and greedy-MaxWeight in terms of both packet delivery ratio and average transmit power.

Original languageEnglish (US)
Title of host publication2018 52nd Annual Conference on Information Sciences and Systems, CISS 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781538605790
StatePublished - May 21 2018
Event52nd Annual Conference on Information Sciences and Systems, CISS 2018 - Princeton, United States
Duration: Mar 21 2018Mar 23 2018

Publication series

Name2018 52nd Annual Conference on Information Sciences and Systems, CISS 2018


Other52nd Annual Conference on Information Sciences and Systems, CISS 2018
Country/TerritoryUnited States


  • Deadline
  • Power
  • QoS
  • Wireless

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Networks and Communications
  • Information Systems


Dive into the research topics of 'Wireless scheduling with deadline and power constraints'. Together they form a unique fingerprint.

Cite this