A Low-Delay MAC for IoT Applications: Decentralized Optimal Scheduling of Queues without Explicit State Information Sharing
We consider a system of several collocated nodes sharing a time slotted wireless channel, and seek a MAC (medium access control) that (i) provides low mean delay, (ii) has distributed control (i.e., there is no central scheduler), and (iii) does not require explicit exchange of state information or control signals. The design of such MAC protocols must keep in mind the need for contention access at light traffic, and scheduled access in heavy traffic, leading to the long-standing interest in hybrid, adaptive MACs. Working in the discrete time setting, for the distributed MAC design, we consider a practical information structure where each node has local information and some common information obtained from overhearing. In this setting, "ZMAC" is an existing protocol that is hybrid and adaptive. We approach the problem via two steps (1) We show that it is sufficient for the policy to be "greedy" and "exhaustive". Limiting the policy to this class reduces the problem to obtaining a queue switching policy at queue emptiness instants. (2) Formulating the delay optimal scheduling as a POMDP (partially observed Markov decision process), we show that the optimal switching rule is Stochastic Largest Queue (SLQ). Using this theory as the basis, we then develop a practical distributed scheduler, QZMAC, which is also tunable. We implement QZMAC on standard off-the-shelf TelosB motes and also use simulations to compare QZMAC with the full-knowledge centralized scheduler, and with ZMAC. We use our implementation to study the impact of false detection while overhearing the common information, and the efficiency of QZMAC. Our simulation results show that the mean delay with QZMAC is close that of the full-knowledge centralized scheduler.
Code (0)
등록된 구현이 없습니다.
Tasks
FairnessSchedulingMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Jumping Fluid Models and Delay Stability of Max-Weight Dynamics under Heavy-Tailed Traffic
We say that a random variable is $light$-$tailed$ if moments of order $2+\epsilon$ are finite for some $\epsilon>0$; otherwise, we say that it is $heavy$-$tailed$. We study queueing networks that operate under the Max-We…
Open-Ended Question AnsweringSchedulingDesign and Scheduling of an AI-based Queueing System
To leverage prediction models to make optimal scheduling decisions in service systems, we must understand how predictive errors impact congestion due to externalities on the delay of other jobs. Motivated by applications…
Model SelectionPredictionSchedulingDynamic load balancing for cloud systems under heterogeneous setup delays
We consider a distributed cloud service deployed at a set of distinct server pools. Arriving jobs are classified into heterogeneous types, in accordance with their setup times which are differentiated at each of the pool…
Effective Multi-User Delay-Constrained Scheduling with Deep Recurrent Reinforcement Learning
Multi-user delay constrained scheduling is important in many real-world applications including wireless communication, live streaming, and cloud computing. Yet, it poses a critical challenge since the scheduler needs to …
Cloud ComputingDeep Reinforcement Learningreinforcement-learningReinforcement Learning (RL)+1DATS: Dispersive Stable Task Scheduling in Heterogeneous Fog Networks
Abstract—Fog computing has risen as a promising architecture for future Internet of Things (IoT), 5G and embedded artificial intelligence (AI) applications with stringent service delay requirements along the cloud to …
SchedulingSTS