Wireless scheduling with deadline and power constraints

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

Research output: Contribution to journalArticlepeer-review


This paper studies the scheduling problem in a co-located wireless network under both the deadline and power constraints. We consider a frame-based time-slotted system. 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. Each of the links is associated with a quality of service (QoS) constraint and an average transmit power constraint. A MaxWeight-type problem is formulated for achieving throughput optimality. The computational complexity of solving the MaxWeight-type problem using the exhaustive search is exponential even for a single-link system. To overcome this difficulty, we propose a greedy algorithm, named PDMax (Power and Deadline constrained MaxWeight), with complexity O(nlog(n)). PDMax schedules packets according to their deadlines and incremental weight gains to the objective of the MaxWeight-type problem. We prove that PDMax is throughput optimal. Our simulations further show that PDMax outperforms both the Largest-Debt-First and the greedy-MaxWeight algorithms in terms of average packet delivery ratio and average transmit power.

Original languageEnglish (US)
Article number102166
JournalPerformance Evaluation
StatePublished - Mar 2021


  • Deadline
  • Power
  • Quality of service
  • Wireless

ASJC Scopus subject areas

  • Software
  • Modeling and Simulation
  • Hardware and Architecture
  • Computer Networks and Communications


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

Cite this