TY - GEN
T1 - Optimal distributed scheduling of real-time traffic with hard deadlines
AU - Lu, Ning
AU - Li, Bin
AU - Srikant, R.
AU - Ying, Lei
N1 - Publisher Copyright:
© 2016 IEEE.
PY - 2016/12/27
Y1 - 2016/12/27
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85010715479&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85010715479&partnerID=8YFLogxK
U2 - 10.1109/CDC.2016.7798938
DO - 10.1109/CDC.2016.7798938
M3 - Conference contribution
AN - SCOPUS:85010715479
T3 - 2016 IEEE 55th Conference on Decision and Control, CDC 2016
SP - 4408
EP - 4413
BT - 2016 IEEE 55th Conference on Decision and Control, CDC 2016
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 55th IEEE Conference on Decision and Control, CDC 2016
Y2 - 12 December 2016 through 14 December 2016
ER -