Optimal distributed scheduling of real-time traffic with hard deadlines

Ning Lu, Bin Li, R. Srikant, Lei Ying

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

Abstract

In this paper, we consider optimal distributed scheduling of real-time traffic with hard deadlines in an ad hoc wireless network. Specifically, we assume the links share a common wireless channel and interference is represented by a conflict graph. Periodic single-hop traffic is considered where packets arrive at the beginning of each frame and need to be delivered by the end of the frame (otherwise, packets will be dropped). Each link is required to guarantee a maximum allowable packet dropping rate. We show that the real-time scheduling problem is combinatorial and tends to be intractable as the network size increases. To solve the real-time scheduling problem, we propose a frame-based carrier-sense multiple access (CSMA) algorithm which is shown to be asymptotically optimal. Moreover, it can be implemented in a distributed manner with low complexity. Simulation results also demonstrate the ability of our algorithm to meet the QoS requirements on deadlines.

Original languageEnglish (US)
Title of host publication2016 IEEE 55th Conference on Decision and Control, CDC 2016
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages4408-4413
Number of pages6
ISBN (Electronic)9781509018376
DOIs
StatePublished - Dec 27 2016
Event55th IEEE Conference on Decision and Control, CDC 2016 - Las Vegas, United States
Duration: Dec 12 2016Dec 14 2016

Publication series

Name2016 IEEE 55th Conference on Decision and Control, CDC 2016

Other

Other55th IEEE Conference on Decision and Control, CDC 2016
CountryUnited States
CityLas Vegas
Period12/12/1612/14/16

    Fingerprint

ASJC Scopus subject areas

  • Artificial Intelligence
  • Decision Sciences (miscellaneous)
  • Control and Optimization

Cite this

Lu, N., Li, B., Srikant, R., & Ying, L. (2016). Optimal distributed scheduling of real-time traffic with hard deadlines. In 2016 IEEE 55th Conference on Decision and Control, CDC 2016 (pp. 4408-4413). [7798938] (2016 IEEE 55th Conference on Decision and Control, CDC 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CDC.2016.7798938