The O-RAN architecture introduces unprecedented flexibility and openness into modern cellular networks, allowing mix-and-match of components from different vendors and the rapid deployment of innovative solutions across the RAN vertical. Despite its openness, some fundamental technical challenges associated with 5G/Next-G still remain in O-RAN. A well known example is joint optimization of Resource Block (RB) allocation, Modulation and Coding Scheme (MCS) selection, and Beamforming (BF) design. In this paper, we present Savitar—an O-RAN scheduler that jointly optimizes these components, with the objective of minimizing spectrum usage while meeting per-UE probabilistic data rate requirements. Following the multi-timescale design principle in O-RAN, we present three components (each at a different time scale) of Savitar that can be seamlessly integrated with O-RAN RICs: (i) hyperparameter tuning in the Non-Real-Time (Non-RT) RIC, (ii) parallel RB Group (RBG) allocation and MCS selection in the Near-RT RIC, and (iii) BF vector design in the RT Open Distributed Unit (O-DU). A unique design in these components is our handling of CSI uncertainty with limited data samples. Experimental results show that Savitar achieves competitive spectrum efficiency performance while meeting our design requirements (i.e., per-UE probabilistic data rate requirement and real-time requirement in O-DU).

The scarcity of spectrum and the proliferation of data-intensive applications in 5G/Next-G networks call for innovations of new techniques that are capable of offering UE-level data rate guarantee with minimum required spectrum usage. This is a challenging problem due to the complexity of mechanisms involved in the process, such as Resource Block (RB) allocation, modulation and coding scheme (MCS) selection, and MU-MIMO beamforming (BF) design. Further complicating the problem is the random, unknown nature of Channel State Information (CSI) and the errors involved in its estimation. In this paper, we present Rudra, which offers a comprehensive solution to these challenges. Rudra formulates the bandwidth minimization problem by incorporating probabilistic data rate guarantee through a chance constraint, which embeds RB allocation, MCS selection, and MU-MIMO BF mechanisms. The CSI uncertainty problem is addressed through a novel error-embedded (EE)-Wasserstein ambiguity set based on a small set of data samples. We show that the solution by Rudra meets our design objective and outperforms a modified state-of-the-art algorithm.

We study an Age-of-Information (AoI) scheduling problem where users can tolerate occasional violations of AoI for each source at the base station. Each user’s AoI is associated with a violation tolerance constraint. We are interested in determining whether a set of users, each with a given AoI deadline, a violation tolerance constraint, and a packet loss rate (due to channel condition) is schedulable, and if so, find a feasible scheduler. For this problem, we study two cases: 1) the stable tolerant case where the tolerance rate is higher than the packet loss rate for each source and 2) the unstable tolerant case where the tolerance rate is lower than the packet loss rate for at least one source. For the stable tolerant case, we design an algorithm called stable tolerant scheduler (STS), which can find a feasible scheduler for any network when the system load is no greater than$\ln 2$(roughly 70%). When the system load is between$\ln 2$and 1, we offer a necessary and sufficient condition for STS to find a feasible scheduler by solving an optimization problem. Likewise, for the unstable tolerance case, we develop a scheduler called unstable tolerant scheduler (UTS) and its corresponding schedulability conditions. Through extensive simulations, we show that STS and UTS match our theoretical results.

Age of Information (AoI) is a metric that can be used to measure the freshness of information. Since its inception, there have been active research efforts on designing scheduling algorithms to AoI-related problems. These problems vary in specific AoI-based objectives and network settings. For each problem, typically a custom-designed scheduler was developed. Instead of following the (custom-design) path, we envision and pursue a general framework that can be applied to design a wide range of schedulers to solve AoI-related problems. As a first step toward this vision, we present a general framework—Eywa, that can be applied to construct high-performance schedulers for a family of AoI-related optimization and decision problems, all sharing a common setting of an IoT data collection network. We show how to apply Eywa to solve three important problems: to minimize weighted sum of AoIs, to minimize bandwidth requirement under AoI constraints, and to determine the existence of feasible schedulers to satisfy AoI constraints. We show that for each problem, Eywa can either offer a stronger performance guarantee than the state-of-the-art algorithms or provide new (or general) results that are not available in the literature.

MU-MIMO beamforming is a key technology for 5G networks, relying on Channel State Information (CSI). However, in practice, the estimated CSI in reality is prone to uncertainty. Further, a MU-MIMO beamforming solution must be derived within a millisecond to be useful for real-time 5G applications. We present ReDBeam—a real-time data-driven beamforming solution for MU-MIMO using limited CSI data samples. The main novelties of ReDBeam are a parallel algorithm and an optimized GPU implementation. ReDBeam delivers a MU-MIMO beamforming solution within 1 millisecond to meet the probabilistic data rate requirements from the users, and minimize a base station’s power consumption. Through extensive experiments, we show that ReDBeam consistently meets the stringent 1-millisecond real-time requirement and is orders of magnitude faster than other state-of-the-art algorithms. ReDBeam conclusively demonstrates that MU-MIMO beamforming with data rate requirements can be achieved in real-time using only limited CSI data samples.

MU-MIMO beamforming is a key technology for 5G/NextG networks. In practice, MU-MIMO beamforming requires Channel State Information (CSI) and is prone to uncertainty. Furthermore, a beamforming solution must be derived within a millisecond (ms) to be useful for real-time (RT) 5G applications. We present ReDBeam-a RT data-driven beamforming solution for MU-MIMO using limited CSI data samples. The main contribution of ReDBeam is a parallel algorithm and an optimized GPU implementation. ReDBeam minimizes the base station (BS)'s power consumption while offering a probabilistic guarantee of users' data rates. It is purposefully designed to take advantage of the vast parallel processing capability in commercial off-the-shelf GPUs. Through extensive experiments, we show that ReDBeam can meet the 1 ms RT requirement and is orders of magnitude faster than other state-of-the-art algorithms for the same problem.

Supporting ultra reliable low-latency communication (URLLC) is an extremely challenging problem, due to the excessive requirements on reliability and latency. To date, few of the existing research efforts have successfully addressed the ultra reliability problem for URLLC. This article investigates this problem through the design of a URLLC scheduler for industrial automation under the open radio access network (O-RAN) architecture. We cast the URLLC data transmission problem as a resource scheduling problem, where a set of resource blocks (RBs) from a set of O-RAN radio units (O-RUs) must be allocated to a set of user equipments (UEs) for information transmission. The challenge is to find a scheduling solution in each mini-slot (sub millisecond time scale) based on dynamic channel conditions and satisfy the ultra reliability requirement (e.g., 99.9999%, or six-nine). We present Pistis—a novel scheduler design that fully utilizes the three control loops in O-RAN. Pistis exploits channel slow fading and PHY-layer properties to reduce the search space in its design of the near-real time (near-RT) component. It further leverages GPU parallel computing in its design of the real time (RT) component, which takes into account of fast fading in channel dynamics. We implement Pistis on commercial off-the-shelf hardware and demonstrate that Pistis is able to meet the six-nine reliability requirement for 4 O-RUs, 40 RBs, and 40 UEs within 0.5 ms.

Channel State Information (CSI) is a critical piece of information for MU-MIMO beamforming. However, CSI estimation errors are inevitable in practice. The random and uncertain nature of CSI estimation errors poses significant challenges to MU-MIMO beamforming. State-of-the-art works addressing such a CSI uncertainty can be categorized into model-based and data-driven works, both of which have limitations when providing a performance guarantee to the users. In contrast, this paper presents Limited Sample-based Beamforming (LSBF)—a novel approach to MU-MIMO beamforming that only uses a limited number of CSI data samples (without assuming any knowledge of channel distributions). Thanks to the use of CSI data samples, LSBF enjoys flexibility similar to data-driven approaches and can provide a theoretical guarantee to the users—a major strength of model-based approaches. To achieve both, LSBF employs chance-constrained programming (CCP) and utilizes the$\infty $-Wasserstein ambiguity set to bridge the unknown CSI distribution with limited CSI samples. Through problem decomposition and a novel bilevel formulation for each subproblem based on limited CSI data samples, LSBF solves each subproblem with a binary search and convex approximation. We show that LSBF significantly improves the network performance while providing a probabilistic data rate guarantee to the users.

Age of Information (AoI) is a metric that can be used to measure the freshness of information. Since its inception, there have been active research efforts on designing scheduling algorithms to various AoI-related optimization problems. For each problem, typically a custom-designed scheduler was developed. Instead of following the (custom-design) path, we pursue a general framework that can be applied to design a wide range of schedulers to solve AoI-related optimization problems. As a first step toward this vision, we present a general framework—Eywa, that can be applied to construct high-performance schedulers for a family of AoI-related optimization problems, all sharing a common setting of an IoT data collection network. We show how to apply Eywa to solve two important AoI-related problems: to minimize the weighted sum of AoIs and to minimize the bandwidth requirement under AoI constraints. We show that for each problem, Eywa can either offer a stronger performance guarantee than the state-of-the-art algorithms or provide new results that are not available in the literature.

Task offloading is a powerful tool in Mobile Edge Computing (MEC). However, in many practical scenarios, the number of required processing cycles of a task is unknown beforehand and only known until its completion. This poses a serious challenge in making offloading decisions as the number of processing cycles is a key parameter to determine whether a task’s deadline can be met. To cope with such processing uncertainty, we formulate a Chance-Constrained Program (CCP) that offers probabilistic guarantees to task deadlines. The goal is to minimize energy consumption for the users while meeting the probabilistic task deadlines. We assume that only the means and variances of the random processing cycles are available, without any knowledge of distribution functions. We employ a powerful tool called Exact Conic Reformulation (ECR) that reformulates probabilistic deadline constraints into deterministic ones. Subsequently, we design an online solution called EPD (Energy-minimized solution with Probabilistic Deadline guarantee) for periodic scheduling and schedule updates during run-time. We show that EPD can address the processing uncertainty with probabilistic deadline guarantees while minimizing the users’ energy consumption.

Degree-of-freedom (DoF)-based models have been proven to be highly successful in modeling and analysis of MIMO systems. Among existing DoF-based models, the number of DoFs used for interference cancellation (IC) is solely based on the number of interfering data streams. However, from both experimental and simulation results, we find that signal strengths of an interference link vary significantly in different directions in the eigenspace. In this paper, we exploit the difference in interference signal strengths in the eigenspace and perform IC with DoFs only on those directions with strong signals. To differentiate interference signal strengths on an interference link, we introduce a novel concept called “effective rank threshold.” Based on this threshold, DoFs are consumed only to cancel strong interferences in the eigenspace while weak interferences are treated as noise in throughput calculation. To better understand the benefits of this approach, we study a fundamental trade-off between network throughput and effective rank threshold for an MU-MIMO network. Our simulation results show that network throughput under optimal rank threshold is significantly higher than that under existing DoF IC models. To ensure the new DoF IC model is feasible at PHY layer, we propose an algorithm to set the weights for all nodes that can offer our desired DoF allocation.

Underlay coexistence is a spectrum efficient mechanism to roll out 5G picocells within a macrocell on the same spectrum. Due to a lack of cooperation between the primary users (PUs) in the macrocell and secondary users (SUs) in the picocells, it is impossible to have complete knowledge of channel conditions between them. Under such a circumstance, chance-constrained programming (CCP) has been shown to be an ideal optimization tool to address such a channel uncertainty. However, solutions to CCP are computationally intensive and cannot meet 5G’s timing requirement (125$\mu s$). To address this problem, we propose a novel scheduler called GPU-based Underlay Coexistence (GUC) with the goal of finding an approximate solution to CCP in real-time. The essence of GUC is to decompose the original optimization problem into a large number of small subproblems that are suitable for parallel computation on GPU platforms. By selecting a subset of promising subproblems and solving them in parallel with fast algorithms, we are able to leverage GPU parallel computing and develop a real-time solution. Through extensive experiments, we show that GUC meets the 125$\mu s$requirement while achieving 90% optimality on average.

Accurate estimation of Channel State Information (CSI) is essential to design MU-MIMO beamforming. However, errors in CSI estimation are inevitable in practice. State-of-the-art works model CSI as random variables and assume certain specific distributions or worst-case boundaries, both of which suffer performance issues when providing performance guarantees to the users. In contrast, this paper proposes a Data-Driven Beamforming (D2BF) that directly handles the available CSI data samples (without assuming any particular distributions). Specifically, we employ chance-constrained programming (CCP) to provide probabilistic data rate guarantees to the users and introduce ∞-Wasserstein ambiguity set to bridge the unknown CSI distribution with the available (limited) data samples. Through problem decomposition and a novel bilevel formulation for each subproblem, we show that each subproblem can be solved by binary search and convex approximation. We also validate that D2BF offers better performance than the state-of-the-art approach while meeting probabilistic data rate guarantees to the users.

5G NR is designed to operate over a broad range of frequency bands and support new applications with ultra-low latency requirements. To support its extremely diverse operating conditions, multiple OFDM numerologies have been defined in the 5G standards. Under these numerologies, it is necessary to perform scheduling with a time resolution of$\sim 100 \mathrm {\mu s}$. This requirement poses a new challenge beyond existing LTE and cannot be satisfied by any existing LTE schedulers. In this paper, we present the design of GPF+, which is a GPU-based proportional fair (PF) scheduler with timing performance under$100 \mathrm {\mu s}$. GPF+ is an improvement over our GPF in Huanget al.(2018). The key ideas include decomposing the original scheduling problem into a large number of small and independent sub-problems and selecting a subset of sub-problems from the most promising search space to fit into a GPU. By implementing GPF+ on an off-the-shelf NVIDIA Tesla V100 GPU, we show that GPF+ is able to achieve near-optimal PF performance with timing performance under$100 \mathrm {\mu s}$. GPF+ represents the fastest GPU-based PF scheduler that can meet the new real-time requirement in 5G NR.

Age of Information (AoI) is an application layer performance metric that quantifies the freshness of information. This paper investigates scheduling problems at network edge when there is an AoI requirement for each source node, which we call Maximum AoI Threshold (MAT). Specifically, we want to determine whether or not a vector of MATs corresponding to the source nodes is schedulable, and if so, find a feasible scheduler for it. For a small network, we present an optimal procedure calledCyclic Scheduler Detection(CSD) that can determine the schedulability with absolute certainty. For a large network where CSD is not applicable, we present a novel low-complexity procedure, calledFictitious Polynomial Mapping(FPM), and prove that FPM can find a feasible scheduler for any MAT vector when the load is under$\ln 2$. We use extensive numerical results to validate our theoretical results and show that the performance of FPM is significantly better than a state-of-the-art scheduling algorithm.

We study the problem of channel uncertainty on wireless transmissions from different users with mutual interference. Specifically, the channel gains from the transmitters to the receivers are available only through their mean and covariance rather than complete distributions. Our goal is to maximize the energy efficiency among all transmitter-receiver pairs while guaranteeing their capacity requirements. For this problem, we employ chance-constrained programming (CCP), which allows occasional violation of target capacity threshold as long as the probability of such violation is below a small tolerable constant (risk level). We propose a solution based on a novel reformulation technique that converts the original CCP into a deterministic optimization problem without relaxation errors. Then the deterministic optimization problem is approximated into a Geometric Program (GP) based on tight polynomial approximations, which can be solved optimally. We prove that our proposed solution achieves near-optimal performance with polynomial time complexity.

We study an Age of Information (AoI) scheduling problem where AoI for each source at the base station (BS) can tolerate occasional violations, which we define as a violation tolerance constraint. The problem is to determine whether a set of users with given AoI deadlines, tolerance rates, and packet loss rates (due to each source's channel condition) is schedulable, and if so find a feasible scheduler. We study two cases: (i) the stable tolerant case where the tolerance rate is higher than the packet loss rate for all sources; (ii) the unstable tolerant case where the tolerance rate is lower than the packet loss rate for at least one source. For stable tolerant case, we design an algorithm called stable tolerant scheduler (STS), which can find a feasible scheduler for any network when system load is no greater than ln 2. For unstable tolerance case, we develop unstable tolerant scheduler (UTS) and identify a schedulability condition for it. Through extensive simulations, we show that STS and UTS match our theoretical results.

Mobile Edge Computing (MEC) has emerged to be an integral component of 5G infrastructure due to its potential to speed up task processing and reduce energy consumption for mobile devices. However, a major technical challenge in making offloading decisions is that the number of required processing cycles of a task is usually unknown in advance. Due to this processing uncertainty, it is difficult to make offloading decisions while providing any guarantee on task deadlines. To address this challenge, we propose EPD---Energy-minimized solution with Probabilistic Deadline guarantee to task offloading problem. The mathematical foundation of EPD is Exact Conic Reformulation (ECR), which is a powerful tool that reformulates a probabilistic constraint for task deadline into a deterministic one. In the absence of distribution knowledge of processing cycles, we use the estimated mean and variance of processing cycles and exploit ECR to the fullest extent in the design of EPD. Simulation results show that EPD successfully guarantees the probabilistic deadlines while minimizing the energy consumption of mobile users, and can achieve significant improvement in energy saving when compared to a state-of-the-art approach.

The Age of Information (AoI) is a key metric to measure the freshness of information for IoT applications. Most of the existing analytical models for AoI are overly idealistic and do not capture state-of-the-art transmission technologies such as 5G as well as channel dynamics in both frequency and time domains. In this article, we present Kronos, a real-time 5G-compliant scheduler that minimizes AoI for IoT data collection. Kronos is designed to cope with highly dynamic channel conditions. Its main function is to perform RB allocation and to select the modulation and coding scheme for each source node based on channel conditions, with the objective of minimizing long-term AoI. To meet the stringent real-time requirement for 5G, we develop a GPU-based implementation of Kronos on commercial off-the-shelf Nvidia GPUs. Through extensive experimentation, we show that Kronos can find near-optimal solutions under submillisecond time scale. To the best of our knowledge, this is the first real-time AoI scheduler that is 5G compliant.

We consider an underlay coexistence scenario where secondary users (SUs) must keep their interference to the primary users (PUs) under control. However, the channel gains from the PUs to the SUs are uncertain due to a lack of cooperation between the PUs and the SUs. Under this circumstance, it is preferable to allow the interference threshold of each PU to be violated occasionally as long as such violation stays below a probability. In this article, we employ Chance-Constrained Programming (CCP) to exploit this idea of occasional interference threshold violation. We assume the uncertain channel gains are only known by their mean and covariance. These quantities are slow-changing and easy to estimate. Our main contribution is to introduce a novel and powerful mathematical tool called Exact Conic Reformulation (ECR), which reformulates the intractable chance constraints into tractable convex constraints. Further, ECR guarantees an equivalent reformulation from linear chance constraints into deterministic conic constraints without the limitations associated with Bernstein Approximation, on which our research community has been fixated on for years. Through extensive simulations, we show that our proposed solution offers a significant improvement over existing approaches in terms of performance and ability to handle channel correlations (where Bernstein Approximation is no longer applicable).

Age of Information (AoI) is an application layer performance metric that quantifies the freshness of information. This paper investigates scheduling problems at network edge when each source node has an AoI requirement (which we call Maximum AoI Threshold (MAT)). Specifically, we want to determine whether or not a vector of MATs for the source nodes is schedulable, and if so, find a feasible scheduler for it. For a small network, we present an optimal procedure called Cyclic Scheduler Detection (CSD) that can determine the schedulability with absolute certainty. For a large network where CSD is not applicable, we present a novel low-complexity procedure, called Fictitious Polynomial Mapping (FPM), and prove that FPM can find a feasible scheduler for any MAT vector when the load is under ln 2. We use extensive numerical results to validate our theoretical results and show that the performance of FPM is significantly better than a state-of-the-art scheduling algorithm.

This article investigates the dynamic multiplexing of enhanced mobile broadband (eMBB) and ultrareliable and low latency communications (URLLC) on the same channel in 5G NR. Due to significant difference in transmission time scale, URLLC employs a preemptive puncturing technique to multiplex its traffic onto eMBB traffic for transmission. The optimization problem to solve is to minimize the adverse impact of such preemptive puncturing on eMBB users. We present DEMUX - a model-free deep reinforcement learning (DRL)-based solution to this problem. The essence of DEMUX is to use deep function approximators (neural networks) to learn an optimal algorithm for determining the preemption solution in each eMBB transmission time interval (TTI). Our novel contributions in the design of DEMUX include the first use of the DRL method with a large and continuous action domain for resource scheduling in NR, a mechanism to ensure fast and stable learning convergence by exploiting the intrinsic properties of the problem, and a mechanism to obtain a feasible preemption solution from the unconstrained output of a neural network while minimizing loss of information. The experimental results show that DEMUX significantly outperforms state-of-the-art algorithms proposed in the 3GPP standards body and the literature.

Underlay coexistence is an effective mechanism to improve spectrum effïciency by having picocells coexist with macrocell on the same spectrum. Due to a lack of cooperation between the primary users (PUs) in the macrocell and secondary users (SUs) in the picocell, it is impossible to have complete knowledge of channel gains between them. Under such circumstance, chance-constrained programming (CCP) is shown to be the ideal optimization tool to address such uncertainty. However, solutions to CCP are computationally intensive and cannot meet 5G's timing requirement. To address this problem, we propose a novel scheduler called GUC (stands for GPU-based Underlay Coexistence) to find an approximate solution to CCP in real-time. The essence of GUC is to decompose the original optimization problem into a large number of small problems that are suitable for parallel computation on GPU platforms. Through extensive experiments, we show that GUC reduces the scheduling computation time by at least 10,000 times comparing to commercial solvers (on CPU) while achieving an average of 90% optimality.

Degree-of-Freedom (DoF) based models have been widely used to study MIMO networks. To cancel interference, the number of DoFs used in the state-of-the-art DoF models is solely based on the number of interfering data streams. However, by decomposing an interference into the eigenspace, we find that signal strengths varies significantly in different directions for the same interference link. In this paper, we exploited the difference in interference signal strength in the eigenspace and differentiate strong and weak interference signals via their singular values. By introducing a concept of effective rank threshold, we propose to use DoFs only to cancel strong interference in the eigenspace based on this threshold while treating weak interference signals as noise in throughput calculation. We explore a fundamental tradeoff between network throughput and effective rank threshold. Using simulation results on MU-MIMO networks, we show that network throughput under optimal rank threshold setting is significantly higher than that under existing DoF IC models. To ensure feasibility at the PHY layer, we present an algorithm that can find Tx and Rx weights at each node that can offer our desired DoF allocation.

Recently, a new metric, called Age of Information (AoI), has become popular to quantify the freshness of information collected at network edge. AoI research is still in its infancy and most prior efforts assume overly simplified models in their investigation. In this paper, we consider a more general model for AoI research that is closer to what happens in the real world. Specifically, we consider general and heterogeneous sampling behaviors among source nodes, varying sample size, and multiple data transmission units in each time slot. Under this much general setting, we develop new theoretical results (in terms of properties and performance bounds) and a new near-optimal low-complexity scheduling algorithm. Our results make a major advance of AoI research in terms of more realistic models.

In underlay coexistence, secondary users (SUs) attempt to keep their interference to the primary users (PUs) under a threshold. Due to the absence of cooperation from the PUs, there exists much uncertainty at the SUs in terms of channel state information (CSI). An effective approach to cope such uncertainty is to introduce occasional interference threshold violation by the SUs, as long as such occasional violation can be tolerated by the PUs. This paper exploits this idea through a chance constrained programming (CCP) formulation, where the knowledge of uncertain CSI is limited to only the first and second order statistics rather than its complete distribution information. Our main contribution is the introduction of a novel and powerful technique, called Exact Conic Reformulation (ECR), to reformulate the intractable chance constraints. ECR guarantees an equivalent reformulation for linear chance constraints into deterministic conic constraints and does not suffer from the limitations associated with the state-of-the-art approach -- Bernstein Approximation. Simulation results confirm that ECR offers significant performance improvement over Bernstein Approximation in uncorrelated channels and a competitive solution in correlated channels (where Bernstein Approximation is no longer applicable).

5G New Radio (NR) is designed to operate under a broad range of frequency bands and support new applications with ultra-low latency. To support its diverse operating conditions, a set of different OFDM numerologies has been defined in the standards body. Under this numerology, it is necessary to perform scheduling with a time resolution of ∼100 μs. This requirement poses a new challenge that does not exist in LTE and cannot be supported by any existing LTE schedulers. In this paper, we present the design of GPF -- a GPU-based proportional fair (PF) scheduler that can meet the ∼100 μs time requirement. The key ideas include decomposing the scheduling problem into a large number of small and independent sub-problems and selecting a subset of sub-problems from the most promising search space to fit into a GPU. By implementing GPF on an off-the-shelf Nvidia Quadro P6000 GPU, we show that GPF is able to achieve near-optimal performance while meeting the ∼100 $\mathrmμs time requirement. GPF represents the first successful design of a GPU-based PF scheduler that can meet the new time requirement in NR.