We consider an energy harvesting sensor transmit- ting latency-sensitive data over a fading channel. We aim to find the optimal transmission scheduling policy that minimizes the packet queuing delay given the available harvested energy. We formulate the problem as a Markov decision process (MDP) over a state-space spanned by the transmitter's buffer, battery, and channel states, and analyze the structural properties of the resulting optimal value function, which quantifies the long-run performance of the optimal scheduling policy. We show that the optimal value function (i) is non- decreasing and has increasing differences in the queue backlog; (ii) is non-increasing and has increasing differences in the battery state; and (iii) is submodular in the buffer and battery states. Our numerical results confirm these properties and demonstrate that the optimal scheduling policy outperforms a so-called greedy policy in terms of sensor outages, buffer overflows, energy efficiency, and queuing delay.
more »
« less
Deep Reinforcement Learning for Delay-Sensitive LTE Downlink Scheduling
We consider an LTE downlink scheduling system where a base station allocates resource blocks (RBs) to users running delay-sensitive applications. We aim to find a scheduling policy that minimizes the queuing delay experienced by the users. We formulate this problem as a Markov Decision Process (MDP) that integrates the channel quality indicator (CQI) of each user in each RB, and queue status of each user. To solve this complex problem involving high dimensional state and action spaces, we propose a Deep Reinforcement Learning based scheduling framework that utilizes the Deep Deterministic Policy Gradient (DDPG) algorithm to minimize the queuing delay experienced by the users. Our extensive experiments demonstrate that our approach outperforms state-of-the-art benchmarks in terms of average throughput, queuing delay, and fairness, achieving up to 55% lower queuing delay than the best benchmark.
more »
« less
- PAR ID:
- 10253848
- Date Published:
- Journal Name:
- 2020 IEEE 31st Annual International Symposium on Personal, Indoor and Mobile Radio Communications
- Page Range / eLocation ID:
- 1 to 6
- Subject(s) / Keyword(s):
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
With an increase in the number of users and the variety of applications with diverse quality of service (QoS) requirements, a more sophisticated radio resource scheduling (RRS) method is needed in 5G networks compared to previous generations. To address this challenge, a growing body of research formulates the RRS problem as a Markov decision process (MDP) and aims to solve it using deep reinforcement learning (DRL). In this dissertation, we first provide a review of existing DRL-based 5G radio resource schedulers, with emphasis on schedulers that aim to minimize the average user delay and follow a fine-grained approach, i.e., use DRL to directly allocate resource blocks (RBs) to user equipments (UEs). Then, we discuss ways to improve upon this early-stage research and identify some open problems that must be solved to make DRL a viable solution to the downlink scheduling problem in 5G networks. The success of any DRL-based approach depends on several factors, including how well the reward signal frames the end goal and how well it assesses progress in reaching that goal. In practice, designing a reward signal is often an informal trial-and-error search for a signal that produces the desired results. Despite the fact that the reward function is a critical component of an MDP, currently there is no systematic study comparing how different reward functions affect network performance. To this end, we first carry out a comparative study of the delay and overflow performance of several reward functions that aim to minimize sum-delay experienced by users in a single-carrier multi-user downlink scheduling scenario where each user has a finite buffer. Through extensive simulations under different traffic and channel conditions, we identify a reward function that can achieve near optimal delay with up to 55 − 67% fewer packet drops than the other investigated options, and does not require any tuning. We then carry out a similar study in a more common multi-carrier multi-user scheduling scenario where each user has an infinite buffer (i.e., there are no packet overflows). With the help of simulations, we draw important conclusions regarding reward design and show that the reward designs under consideration outperform the benchmark rule-based scheduler. Depending on how RBs are scheduled, there are two approaches to RRS. In the first approach, RBs are scheduled jointly. In the second approach, RBs are scheduled sequentially. The sequential approach reduces the computational complexity of the problem by reducing the action space. Thus, we convert the joint scheduling problem into a sequential scheduling problem and show how the optimal value function for the joint scheduling problem is decomposed after converting it to a sequential scheduling problem. With the help of extensive simulations under different traffic and channel conditions, we show that the sequential RRS schedulers not only reduce the computational complexity of the problem, but also perform better than the joint RRS schedulers.more » « less
-
With the wide adoption of deep neural network (DNN) models for various applications, enterprises, and cloud providers have built deep learning clusters and increasingly deployed specialized accelerators, such as GPUs and TPUs, for DNN training jobs. To arbitrate cluster resources among multi-user jobs, existing schedulers fall short, either lacking fine-grained heterogeneity awareness or hardly generalizable to various scheduling policies. To fill this gap, we propose a novel design of a task-level heterogeneity-aware scheduler, Hadar, based on an online optimization framework that can express other scheduling algorithms. Hadar leverages the performance traits of DNN jobs on a heterogeneous cluster, characterizes the task-level performance heterogeneity in the optimization problem, and makes scheduling decisions across both spatial and temporal dimensions. The primal-dual framework is employed, with our design of a dual subroutine, to solve the optimization problem and guide the scheduling design. Extensive trace-driven simulations with representative DNN models have been conducted to demonstrate that Hadar improves the average job completion time (JCT) by 3× over an Apache YARN-based resource manager used in production. Moreover, Hadar outperforms Gavel[1], the state-of-the-art heterogeneity-aware scheduler, by 2.5× for the average JCT, and shortens the queuing delay by 13% and improve FTF (Finish-Time-Fairness) by 1.5%.more » « less
-
null (Ed.)Abstract: Radio access network (RAN) in 5G is expected to satisfy the stringent delay requirements of a variety of applications. The packet scheduler plays an important role by allocating spectrum resources to user equipments (UEs) at each transmit time interval (TTI). In this paper, we show that optimal scheduling is a challenging combinatorial optimization problem, which is hard to solve within the channel coherence time with conventional optimization methods. Rule-based scheduling methods, on the other hand, are hard to adapt to the time-varying wireless channel conditions and various data request patterns of UEs. Recently, integrating artificial intelligence (AI) into wireless networks has drawn great interest from both academia and industry. In this paper, we incorporate deep reinforcement learning (DRL) into the design of cellular packet scheduling. A delay-aware cell traffic scheduling algorithm is developed to map the observed system state to scheduling decision. Due to the huge state space, a recurrent neural network (RNN) is utilized to approximate the optimal action-policy function. Different from conventional rule-based scheduling methods, the proposed scheme can learn from the interactions with the environment and adaptively choosing the best scheduling decision at each TTI. Simulation results show that the DRL-based packet scheduling can achieve the lowest average delay compared with several conventional approaches. Meanwhile, the UEs' average queue lengths can also be significantly reduced. The developed method also exhibits great potential in real-time scheduling in delay-sensitive scenarios.more » « less
-
Event driven applications are often built with message queuing systems that provide no temporal upper bound on message delivery. However, many modern event driven applications, like a system inferring traffic conditions and generating recommendations to road users based on sensor data, are latency sensitive. Traditional message queuing systems use static load assignment algorithms that guarantee event ordering while mostly ignoring a temporal upper bound on message delivery. Another class of message queuing systems use stateless operators which deliver messages (events) quickly but pass the burden of stream state management to user applications. Synchronous communication patterns, on the other hand, provide an upper bound for message delivery while ensuring message ordering but unnecessarily bind limited resources reducing efficiency. In this paper we explore load balancing choices in asynchronous systems and their impact on queuing delay. We then propose a load balancing framework, SMALOPS, for event driven applications with dynamically changing load and quick message delivery requirements. Our experiments confirm that with smarter load balancing, the \mathbf9 9 % ile response times for events can be improved by as much as 73 %, compared to traditional message queuing systems. SMALOPS introduces the following:•A load balancing algorithm that can significantly reduce queuing delay in message delivery systems.•Mechanisms enabling consumers to recover stream state when either the message delivery system does not support stateful operators or the state has been split by moving streams between operators.more » « less
An official website of the United States government

