Real-Time Flow Scheduling in Industrial 5G New Radio

I. INTRODUCTION

Industrial Internet-of-Things (IIoT) is expected to significantly improve the efficiency and performance of industrial networks across a wide range of industrial applications. Many of these industrial applications (e.g., use cases specified by 3GPP [1] including mobile operation panels and remote surgery) are mission-and safety-critical, with stringent timing and reliability requirements on the communication fabric to exchange information among various devices [2].

IIoT tends to use wireless networks for communication since they enable more flexible network configurations and reduce cabling costs compared to their wired counterparts (e.g., industrial Ethernet [3] and Time-Sensitive Networking [4]). However, existing industrial wireless solutions (e.g., ISA100.11, WirelessHART, and 6TiSCH [5]- [8]) are mainly used in the context of low-power and low-speed wireless sensor and actuator networks. To support high-speed real-time wireless communication, IEEE 802.11-based protocols (e.g., Wi-Fi 6 [9]) have received growing attention in industrial applications due to their low deployment cost. However, 802.11-based protocols operate in unlicensed spectrum and may suffer severe and unexpected interference from other coexisting networks.

The industrial connectivity landscape is changing with the emergence of 5G New Radio (NR) cellular networks [10]. The deployment of 5G NR in industrial applications, also termed private 5G networks in 3GPP, has attracted significant interest due to its capabilities of providing ultra-high-speed communication (multi-Gbps peak rates), wide coverage, ultralow latency, and massive connectivity. Furthermore, the private 5G deployment options also provide complete control to configure every aspect of the network (e.g., schedule, resource allocation) without involving mobile network operators [2].

To achieve ultra high-speed real-time communication, several enabling technologies are supported in industrial 5G NR. For example, orthogonal frequency division multiple access (OFDMA) is utilized in 5G NR for both uplink (UL) and downlink (DL) to achieve deterministic transmissions [11]. Compared to 4G LTE networks, 5G NR adopts fewer OFDM symbols per transmission time interval (TTI) and shortens the OFDM symbols via a wider subcarrier spacing to reduce latency. MU-MIMO (multi-user multiple-input-multiple-output) is another core technology for 5G NR to significantly increase network throughput [12] by allowing a base station gNB to harvest the spatial diversity and transmit signals to multiple user equipment (UEs) on the same frequency band simultaneously. In addition, 5G NR provides robust modulation and coding schemes (MCS) which determines the user's data rate on individual frequency bands according to the per-band channel quality indicator (CQI), namely subband CQI report.

Although 5G NR provides much flexibility and has tremendous potential, it brings high complexity due to the large design space of the flow scheduler at the gNB to meet the real-time requirements of industrial data flows. Specifically, the scheduler needs to i) allocate resource blocks (RBs) in the frequency domain to multiple users appropriately; ii) determine the number of data streams that can be transmitted by each user simultaneously in the spatial domain based on their transmission interference; and iii) choose the MCS index for each user ensuring that the selected MCS index is identical across all RBs allocated to this user [13]. Therefore, the realtime flow scheduling problem in 5G NR couples together RB allocation, data stream number determination, and MCS index selection in order to satisfy the timing requirements of industrial data flows, making the problem extremely challenging.

Time-frequency scheduling for real-time flows in traditional industrial wireless networks has been well studied [14]- [18]. In 5G networks, many recent works studied resource schedul- ing problems with objectives to optimize network throughput (e.g., [19]- [22]) or AoI (Age of Information, e.g., [23]- [25]). In light of improving the real-time performance of 5G networks, [26], [27] provide hard performance guarantees through formal response time analysis for 5G network slicing. However, these works adopt over-simplified resource models; and the proposed analyses only apply to fixed-priority scheduling, which leads to low schedulability performance as revealed in our experimental results. Some recent works [28]- [30] study 5G configured grant (CG) scheduling aiming at providing real-time guarantees for time-critical traffic. However, CG scheduling is only applied to 5G UL transmissions and suffers from extremely low flexibility. To the best of our knowledge, this paper is the first work that studies time-frequency-space DL scheduling in industrial 5G NR, which features per-flow real-time schedulability guarantee. Specifically, we make the following contributions.

• We leverage a real-world 5G RAN testbed to benchmark the DL throughput and explore the impact of MCS index selection on the network performance.

• We formulate the real-time flow scheduling problem in industrial 5G NR considering the featured 5G techniques, e.g., MU-MIMO and MCS selection based on subband CQI report.

• We introduce a two-phase scheduling framework, 5G-TPS, to construct a feasible schedule with deadline guarantees for all the flows. Upon any dynamic channel condition changes, 5G-TPS enables online schedule adjustment for affected flows to meet their timing requirements.

• We evaluate the performance of 5G-TPS through a case study and extensive experiments by comparing it with an SMTbased exact solution and many other state-of-the-art methods. The results demonstrate superior performance of 5G-TPS in terms of schedulability ratio, in both stable and dynamic channel conditions.

II. MOTIVATIONAL EXPERIMENTS

In traditional industrial wireless networks, considerable research has been conducted on channel allocation in the frequency domain and flow scheduling in the time domain (e.g., [31]- [33]). However, the MCS index selection in 5G NR scheduling remains an area that lacks comprehensive understanding [34], [35], particularly regarding its impact on the network performance.

In 5G NR, MCS determines the number of bits per symbol that can be modulated and coded on the transmission channel between UE and the gNB. Higher MCS indices generally correspond to higher channel efficiency and higher data rates, but they may also be associated with higher packet error rates, as more aggressive modulation schemes are more susceptible to noise and interference. In order to understand the impact of the selected MCS index on the performance of 5G NR, we constructed a real-world 5G RAN testbed using OpenAirInterface (OAI) [36], a widely adopted open-source project which provides 3GPP-compliant implementations of gNB and UE, and benchmarked the downlink (DL) throughput of the OAI-based 5G RAN for different MCS index values and connectivity settings.

1) Connectivity Settings:

To thoroughly study the impact of the MCS index on network throughput, we conduct experiments in three different connection modes as shown in Fig. 1(b). In the RFSim mode, the OAI gNB transmits the I/Q samples to the UE over a radio channel simulator, namely RF simulator, via Ethernet without using the RF boards (i.e., USRP B210). In the over-the-air (OTA) mode, omnidirectional antennas are connected to the RF boards to transmit signals.

In the SMA cable mode, the two USRP B210 devices are directly connected using Sub-Miniature version A (SMA) cables instead of antennas.

We further enrich the throughput measurements by varying the noise power levels in the RFSim mode and the signal level in the SMA cable mode since noise power level could further impact the network channel quality. Specifically, in the RFSim mode, in addition to the default perfect channel, we enable channel modeling and set the noise power to -1dBm, -5dBm, and -10dBm at the UE side. In the SMA cable mode, we configure different reduced amplitude levels (30dB, 40dB and 50dB) of the incoming signal at the UE side by connecting two 10dB attenuators and one 30dB attenuator in series.

B. Measurement Results

Fig. 1(c) summarizes the throughput results as a function of the MCS index under various connectivity settings. Intuitively, one would expect the throughput to increase monotonically with higher MCS indices, as higher modulation schemes and coding rates typically result in higher data rates and channel efficiency. However, upon observation, it is apparent that only the results of RFSim with default channel and SMA cable connection with the 50dB attenuator meet this expectation. All other results show fluctuations as the MCS indices increase.

For example, in the RFSim mode, when an extremely high level of noise (-1dBm) is added to the simulated channel, the network throughput is very low (<80 Kbits/sec, values enlarged by 10 times for improved visibility in Fig. 1(c)). The data also show significant fluctuation when the MCS indices are small (from 0 to 9). When we further increase the MCS index, the throughput directly drops to 0 (values omitted in Fig. 1(c)) due to extremely high packet loss rate. A similar trend can be observed in all the other curves, but the occurrences of fluctuation vary, and the throughput fluctuation is delayed under better channel conditions.

Observation 1. Only in the case of a high-quality channel the throughput monotonically increases with the increase of MCS index. Under worsening channel conditions, the throughput can decrease with higher MCS indices, and significant fluctuations may occur.

The fluctuation in throughput with increased MCS index is mainly caused by the following reason. The communication channel between the UE and the gNB is composed of a set of subbands, and the channel quality may vary across these subbands. However, according to the PHY specification of 5G NR [13], the UE must select and use the same MCS index on all the allocated subbands. When the MCS index is increased, the UE may fail to decode the received signals on subbands with poor channel quality, resulting in decreased throughput. However, on subbands with good channel quality, the UE can achieve higher data rates, leading to improved throughput. These opposite trends in throughput changes on different subbands result in overall throughput fluctuations across the entire bandwidth as the MCS index increases.

Regarding Observation 1, there are two points worth noting. First, the OTA mode measurement on our testbed is conducted in a line-of-sight (LOS) indoor lab environment with no moving objects nor significant interference/noise sources (see Fig. 1(a)), and the throughput results show fluctuation when MCS index is larger than 9. When considering industrial 5G RAN networks which are typically deployed in much harsher environments, the channel quality can be much worse and the fluctuation in network performance can be more significant for different MCS indices.

Secondly, in our testbed, the gNB is connected with only one UE which has access to the entire network bandwidth resource. The gNB only needs to determine the MCS index used by the UE to achieve better performance, e.g., higher throughput. However, if multiple UEs are connected to the RAN network, it becomes more challenging to determine the proper MCS index for each UE, given that the bandwidth is shared by all the UEs and the subband allocation for each UE also needs to be determined. Therefore, based on the experimental results and the above discussion, we make the following statement to motivate our work.

1) OFDMA Resource Grid:

In OFDMA-based 5G NR, as shown in Fig. 2, network resource is organized as a resource grid that spans in both time and frequency domains. In the time domain, time is equally slotted into transmission time intervals (TTIs) each of which consists of 14 OFDM symbols [37]. In the frequency domain, bandwidth of the operating channel is divided into a number of uniform subbands, and each subband is denoted as a resource block (RB). That is, within each TTI, there is a set of RBs B + = {b|b ∈ [1, 2, . . . , B]} that can be allocated to the UEs for transmissions, where B represents the total number of RBs in the frequency domain. 2) Traffic Model: Communication in industrial applications is typically characterised by two attributes, periodicity and determinism, which together specify periodic traffic flows with stringent timing requirements [1]. To simplify the notation, we assume that each UE u i ∈ U (i ∈ [1, N]) receives one transmission flow, denoted as f i ∈ F (i ∈ [1, N]), from the gNB periodically 1 . Each f i is associated with a tuple P i , D i , C i . P i and D i denote the period and deadline of f i (in unit of TTIs), respectively, and we assume D i ≤ P i . C i denotes the payload size (in bits) which is the amount of information carried in each instance of f i . The k-th instance of flow f i is referred to as packet p i,k . Its release time and absolute deadline are denoted as r i,k and d i,k , respectively.

3) MCS Model: The objective of the real-time flow scheduling problem in 5G NR is to allocate RBs to individual flows in the flow set F while satisfying their timing requirements. A number of 5G specific issues must be considered in formulating the scheduling problem. Besides RB allocation, the scheduler also needs to select a proper MCS for each UE in each TTI [13]. As discussed in Section II, a larger MCS index generally leads to a higher UE data rate. However, the maximum data rate that can be achieved on one RB depends on the channel condition between UE and gNB. If the channel condition on this RB is poor but a high MCS is used, data may not be successfully received by the UE.

Channel conditions can vary in both time (across different TTIs, i.e., time-selective fading) and frequency (across different RBs, i.e., frequency-selective fading). Variation of channel condition in the time domain is mainly determined by motion effects, e.g., UEs installed on moving objects and obstacles moving between UEs and the gNB [38]. The channel condition is reported from individual UEs to the gNB through the CQI either periodically or aperiodically which is configured by the Radio Resource Control (RRC) message(s). In the frequency domain, channel attenuation, which suffers from severe fading effects (e.g., reflective obstacles such as machines), is nonnegligible. Therefore, the channel condition between each UE and the gNB varies on different RBs in the frequency domain.

We denote M = {0, 2, . . . , 28} as the set of 29 available MCS indices defined in [13]. Let q b i be the maximum MCS index that can be used by UE u i on RB b ∈ B + so that i , the data can be successfully transmitted and the achievable data rate is c(m). Otherwise, i.e., m > q b i , the transmission fails with data rate being 0 [13]foot_1 . That is,

According to the 5G NR PHY specification [13], although each UE can be allocated with multiple RBs in one TTI, it must select and use the same MCS index on all the allocated RBs. For example, suppose there are 4 RBs in the frequency domain (i.e., B = 4) and the channel conditions (i.e., q b i ) on the 4 RBs for two UEs u 1 and u 2 are shown in Fig. 3. If we select MCS m = 1 for u 1 , then data carried on RB 1 , RB 2 and RB 4 can be successfully transmitted, and the total data rate is 3 × 8 = 24. If we select a higher MCS m = 3, a higher data rate can be achieved on RB 2 and RB 4 , i.e., 2 × 18 = 36. However, a higher MCS index is not always leading to a higher data rate, according to the measurement results in our motivational experiments. For instance, setting a higher MCS m = 2 for u 2 leads to a lower data rate 14 compared to data rate 24 that can be achieved by setting m = 1.

4) MU-MIMO:

In 5G NR, MU-MIMO [41] is supported to improve the spectral efficiency by spatially multiplexing multiple UEs. That is, the gNB communicates with multiple UEs on the same RB within one TTI. For example, in Fig. 2, UEs u 1 and u 2 are simultaneously transmitted on RB 10 within TTIs [3,7]. On each RB b ∈ B + , the scheduler selects a set of UEs for MIMO transmission, where

scheduled by the gNB for UE u i in TTI t. Further, each UE u i can simultaneously transmit multiple data streams (also called "layers" in specification [42]) on each RB in one TTI. For example, in Fig. 2, 6 data streams are transmitted by u 3 on RB 1 and RB 2 in each TTI within TTIs [1,10].

To reduce the control signaling overhead and signal processing complexity, 5G NR requires that each UE must have the same number of data streams across all RBs allocated to it in each TTI. Let y i (t) be the number of data streams transmitted by user u i in TTI t. If the number of antennas for each UE is M R , we have y i (t) ≤ M R . Similarly, the total number of data streams on each RB b for MIMO transmissions cannot exceed the number of antennas at the gNB, M T , i.e., ui∈U

In a practical MU-MIMO system, propagation channels among different UEs are spatially correlated and the theoretical multi-antenna gains cannot always be obtained. Channel correlations can generate interference among UEs due to the channel fading of multipath propagation between the gNB and UEs with diverse spatial transmission directions. To ensure the transmission performance of MU-MIMO, the scheduler needs to perform user selection to avoid data streams from the UEs with high interference to be transmitted on the same RB which may deteriorate the achievable data rate [43]. In this paper, we use w(u i , u j ) ∈ {0, 1} to denote whether two UEs u i and u j can transmit on the same RB simultaneously according to their interference level, where w(u i , u j ) = 0 indicates that u i and u j cannot transmit simultaneously 3 . We assume that w(u i , u j ) for each pair of UEs, which can be derived by existing work (e.g. [21]), is known at the gNB. We denote θ i as the achievable data rate flag for user u i in a MU-MIMO system, where θ i captures the impact on the data rate of u i from other UEs that simultaneously transmit on the same RB.

if there exists u j transmitting on the same RB with u i and w(u i , u j ) = 0, 1 otherwise.

(3)

Transmitted data amount. The total amount of data transmitted to u i in t across all its allocated RBs, denoted as R i (t), can be calculated by

• y i (t) • θ i , where m i (t) denotes the selected MCS index for u i in t. Then, the total amount of data transmitted to UE

Definition 1 (Schedule). A schedule specifies the following resource allocation decisions for each UE u i in each TTI t.

• The RBs allocated to u i , i.e., {s b i (t)|b ∈ B + }; • The selected MCS index for u i , i.e., m i (t);

• The number of data streams transmitted to u i , i.e., y i (t).

Given the definition of a schedule, we aim to solve the following real-time flow scheduling problem in 5G NR.

Problem P: Given the UE set U, flow set F, the modulation and coding rate c(m) on any RB, the maximum MCS index q b i usable by UE u i on any RB b, and the interference information w(u i , u j ) between UEs, determine a feasible schedule (if exists) that satisfies the deadlines of all the packets released by the flows in F.

In the following sections, we outline our 5G NR scheduling framework. We first assume a stable channel condition within each hyperperiod H (i.e., the least common multiple of all the flow periods), where q b i for each UE is updated once every H TTIs. We then extend the system model and scheduling method to account for dynamic channel conditions, where q b i for each UE is updated when the channel condition changes.

IV. OVERALL SCHEDULING FRAMEWORK

Problem P is NP-hard and this can be proved by reducing the set packing problem [44] to a special case of the SISO (single-input-single-output) version of Problem P. The details of the proof is omitted here due to the space limit.

The solution space of Problem P is also extremely large. Specifically, the gNB needs to allocate B RBs among N UEs and assign each UE an optimal MCS (among 29 possible indices) in each TTI. On each RB b, the number of possible combinations of simultaneously transmitted flows equals to

possibilities in the solution space. Given the complexity and the large solution space of Problem P, we design a two-phase scheduling framework, named 5G-TPS, to judiciously reduce the search space following a set of insights. The key principle of 5G-TPS is to maximize the channel efficiency for all the UEs such that all the flows can meet their timing requirements.

At the highest level, we adopt a channel condition aware approach to generate a schedule for all the flows f i ∈ F. Specifically, when the network channel condition is stable within each hyperperiod, we apply the same RB allocation to each flow in all its scheduled TTIs. This approach has one distinct advantage. That is, it reduces the overhead for communicating Downlink Control Information (DCI). Note that, individual RB allocations across different TTIs require multiple DCI messages each of which specifies one RB allocation with individual TTI information and the selected MCS index. This incurs large control resource overhead which, in turn, reduces the amount of network resources allocated to PDSCH (Physical Downlink Shared Channel) for transmitting actual data. On the other hand, if an RB allocation is 'satisfactory' to all the flows in F in one TTI, it is not necessary to make any adjustment on the RB allocations in other TTIs when the maximum usable MCS index q b i for each UE is not changed (Theorem 1 below demonstrates this observation). Therefore, using the same RB allocation for each flow in all its scheduled TTIs is sufficient.

Based on the general approach outlined above, in Phase 1 of 5G-TPS, we aim to find a feasible RB allocation across all the TTIs in the hyperperiod to satisfy all the flows' deadlines. If Phase 1 fails, i.e., an RB allocation satisfying the deadlines of all the flows cannot be found, Phase 2 is activated to adjust the RB allocations based on the output of Phase 1. Specifically, the redundant RBs allocated to certain flows in the unused TTIs together with some unallocated RBs will be judiciously assigned to the unschedulable flows to meet their deadlines.

If the channel condition changes within each hyperperiod in the form of q b i update from each affected UE, we perform schedule adjustment among different flows, in terms of MCS index re-selection and RB allocation adjustments. Details of the schedule adjustment will be discussed in Section VII.

V. RB ALLOCATION IN PHASE 1 OF 5G-TPS

In this section, we describe Phase 1 of 5G-TPS by focusing on two questions: i) what is a feasible RB allocation that is satisfactory to all the flows? and ii) how to find such a feasible RB allocation? Before answering these two questions, we first determine the setting on the number of data streams for each UE u i (i.e., y i (t)) in the spatial domain.

In MU-MIMO 5G NR, each UE is equipped with M R antennas and can receive at most M R concurrent data streams on each RB. Thus, a larger data rate can be achieved by each flow f i ∈ F on each RB if multiple data streams are configured by its corresponding UE u i . Then, more data of packet p i,k can be transmitted within each TTI and the transmission of p i,k can complete earlier. In addition, more data streams configured for each flow leads to less number of UEs simultaneously receiving in each TTI, since the total number of data streams from all the flows cannot exceed the number of antennas equipped on the gNB (i.e., M T ). This results in less transmission interference among different UEs caused by channel correlation and thus a higher channel efficiency can be achieved. Based on the above observations, we fix y i (t) = M R for each f i in 5G-TPS 4 .

Lemma 1. If M R data streams are transmitted by u i in each TTI and the amount of transmitted data per data stream is larger than or equal to

Ci Di•MR , flow f i is schedulable, i.e., satisfies the deadline. 4 For many 5G commercial products, the number of antennas equipped on the gNB is an integral multiple of the number of antennas on UE, e.g., 64×64 MIMO supported by Nokia AirScale and 4 × 4 MIMO supported by Quectel RM510Q. Therefore, we argue that M T mod M R = 0, and setting y j (t) = M R does not result in any resource waste due to the insufficient number of available data streams, which is less than M R .

The proof of Lemma 1 is straightforward and thus omitted. According to Lemma 1, an RB allocation for flow f i , denoted as B i ⊆ B + , is defined as feasible if the total amount of data transmitted on RBs b ∈ B i in one TTI is larger than or equal to Proof Sketch. According to Lemma 1, Constraint 1 guarantees that each flow f i is schedulable with allocated RBs in B i . Constraint 2 guarantees that no transmission interference occurs between any two UEs. Constraint 3 satisfies the limit on the number of antennas equipped on the gNB (i.e., Eq. ( 2)).

To find a feasible RB allocation Θ for F (i.e., answering the second question in Phase 1 design), we first determine a feasible RB allocation candidate set for each flow f i , denoted as {B * i } (i.e., each B i ∈ {B * i } satisfies Constraint 1). We then formulate an RB allocation selection problem to select one RB allocation B i for each flow f i from its candidate set {B * i } such that Constraints 2&3 in Theorem 1 are satisfied. Below we elaborate these two steps.

B. RB Allocation Candidate Set Generation

Over the entire network bandwidth, there exists a large number of RB allocations for each flow (e.g.,

if all RB allocations are feasible) satisfying Constraint 1, creating an extensive search space for the RB allocation selection problem. To improve the search efficiency, we aim to generate a small RB allocation candidate set {B * i } for each f i , and only include in it the most promising RB allocations (instead of solving in one shot the RB allocation selection problem based on all feasible RB allocations of each flow).

Generating {B * i } out of all feasible RB allocations is a challenging task. To tackle this, we explore the relationship between two critical factors: i) the number of RBs allocated to each flow and ii) the achievable data rate of each flow. The number of RBs allocated to a flow impacts the available RB allocations for other flows in F since the limited number of RBs over the entire bandwidth are shared by all the flows. On the other hand, the achievable data rate of each flow determines its own schedulability. According to Lemma 1, the feasible RB allocations must have achievable data rate larger than or equal to Ci Di•MR . Furthermore, higher data rates for each UE u i at a given number of RBs are more desirable since each packet of f i can transmit the required C i amount of data using less TTIs where the RBs within the unused TTIs can be utilized by other flows to complete their data transmissions in Phase 2. Thus, we introduce the highest data rate function for each flow to aid us identify the flow's feasible RB allocations.

Definition 2 (Highest data rate function β i (x)). β i (x) is the highest data rate that can be achieved by f i per data stream if x number of RBs in B + are allocated to f i .

Obtaining β i (x) is to find x RBs with the 'best' channel conditions such that flow f i can achieve the highest data rate. β i (x) can be calculated by traversing the maximum usable MCS index q b i on all the RBs b ∈ B + in a descending order, and storing the highest data rate achieved using each MCS index q b i . This process ends until we find at least x RBs with the maximum usable MCS index equal to the current q b i value. For example, Fig. 4 shows β i (x) for flow f i on a network with 8 RBs. When calculating β i (4), it starts from q b i = 3, and only three RBs are with the maximum usable MCS index equal to 3, thus the achievable data rate is 3 × 18 = 54. We proceed with q b i = 2, and 6 RBs (larger than 4) are with the maximum usable MCS index larger than or equal to 2 where the achievable data rate is 4 × 14 = 56. Thus, we have β i (4) = 56.

As depicted in Fig. 4, all the RB allocations resulting β i (x) ≥ Ci Di•MR (x ≤ B) can form an RB allocation candidate set {B * i } for flow f i . However, the size of this set is still large due to two reasons: i) large networks may have a significant number of RBs (i.e., a large B), and ii) each β i (x) value can correspond to multiple RB allocations. For example, in Fig. 4, β i (2) = 36 and there exist three RB allocations with α i ({3, 5}) = α i ({3, 8}) = α i ({5, 8}) = 36, where α i (B) denotes the highest achievable data rate with RB allocation B.

Therefore, we outline our findings through several important lemmas below, which provide guidelines on reducing the set of considered feasible RB allocations, i.e., generating the RB allocation candidate set {B * i } for each flow f i . Lemma 2. The highest data rate function β i (x) is segmented by piecewise linear functions of x, denoted as where c(ζ j ) denotes the achievable data rate under MCS index ζ j . For any two linear segments β i,j (x) and

Proof Sketch. When the number of RBs having a larger usable MCS ζ j is greater than the current value x, ζ j can be selected as the MCS index and β i (x) increases with the same increment c(ζ j ). When x is greater than the number of RBs having ζ j , a smaller MCS index ζ h has to be selected and the slope of

Lemma 2 indicates that when x increases, if β i (x) transfers to another linear function, the maximum usable MCS index to achieve β i (x) decreases. This leads to a set of RBs on each of which flow f i transmits under a MCS index lower than q b i . For example, in Fig. 4, β

Proof. Since x and x j follow a same linear function, according to Lemma 2,

Thus, for any RB allocation B such that α i (B ) = c(q bj i ) • x , there exist x > x j RBs with the maximum usable MCS higher than or equal to q bj i . Then, we can have an RB allocation B o ⊂ B by selecting arbitrary x j RBs in B such that

Lemma 3 indicates that any RB allocation resulting in β i (x ) is a superset of an RB allocation resulting in β i (x j ), if x and x j (x > x j ) follow a same linear function. Then, if all the RB allocations resulting in β i (x j ) cannot satisfy Constraint 2 in the RB allocation selection process, the RB allocations resulting in β i (x ) cannot either. This motivates us to only consider the minimum value of x within a linear function of β i (x) that satisfies Constraint 1. For instance, in Fig. 4, the set of considered number of allocated RBs is further reduced from x ∈ {2, 3} to x = 2.

Based on Lemma 2&3, we can determine the RB allocation candidate set {B * i } for each flow f i as follow. RB allocation candidate set determination. We determine the number of RBs allocated to flow f i , denoted as x * i , as the minimum x satisfying β i (x) ≥ Ci Di•MR , and any RB allocation B resulting α i (B) = β i (x * i ) is included in the RB allocation candidate set {B * i }. For example, in Fig. 4,

B. Phase 2 Overview

In Phase 2, we use the remaining RBs to generate a feasible schedule for each unschedulable flow where F 1 is the set of flows feasibly scheduled in Phase 1. Specifically, for f j we determine the RB allocation and MCS index in the frequency domain, the scheduled TTIs in the time domain, and the number of data streams in the spatial domain.

In the time domain, we schedule each packet of f j in a consecutive set of TTIs to reduce control overhead, given that each DCI message only carries 4 bits for the time domain resource assignment (the start TTI index and the number of TTIs) according to 3GPP [46]. In the spatial domain, we follow the setting of y j = M R to reduce the transmission interference among UEs and improve the channel efficiency.

Thus, in Phase 2, we assign each packet p j,k of flow f j ∈ F 2 with a feasible schedule specifying RB allocation B j and TTI duration, denoted as S j,k = [t j,k , t j,k + T j ), where t j,k and T j are the start TTI and length of the consecutive TTIs, respectively. That is, all the packets released by f j share the same {B j , T j } configuration with individual start TTIs t j,k . Theorem 2 below specifies the schedulability of flow set F 2 . The proof is omitted due to the similarity to that of Theorem 1.

Theorem 2. If the schedule of each flow f j ∈ F 2 , denoted as {B j , S j } where S j = {S j,k|k=1,2,... }, satisfies the following constraints, flow set F 2 is schedulable. Constraint 4. For any packet p j,k , t j,k ≥ r j,k , t j,k + T j ≤ r j,k + D j , and α(B j ) • T j ≥ Ci MR . Constraint 5. If B j shares a common RB in a TTI with any B i (f i ∈ F), w(u i , u j ) = 1. Constraint 6. For any RB b ∈ B j and TTI in S j,k , the number of flows share the same RB is not larger than M T /M R .

To summarize, since both the RB allocation in the frequency domain and the TTI configuration in the time domain are considered for flows in Phase 2, we generate the schedule for each flow f j ∈ F 2 in an iterative fashion to avoid combinatorial explosion among RB allocations for all the flows in different TTIs. In each iteration, given the set of remaining RBs within TTIs [1, H], we i) determine {B j , S j } for flow f j with the highest utilization (i.e., C j /P j ) in F 2 since f j typically requires more RBs in each TTI than the other flows, and ii) update the set of remaining RBs.

C. Feasible Schedule Generation

In this section, we describe how to generate the feasible schedule {B j , S j } for flow f j using the remaining RBs. We first give the problem formulation. Problem P2. Given the set of remaining RBs, the specification of flow f j , determine a feasible schedule {B j , S j } satisfying all the constraints in Theorem 2.

A feasible schedule {B j , S j } specifies a 'rectangle' with |B j | RBs in the frequency domain 6 and T j TTIs in the time domain. According to Theorem 2, we need to guarantee two requirements: (i) the rectangle must exist within the period of each packet p j,k , and (ii) the amount of data transmitted in the rectangle must be larger than or equal to C j .

To satisfy requirement (i), we traverse the set of remaining RBs usable by all the packets of f j and identify the common RBs (i.e., RBs in the same relative TTIs in the period of each packet, see Fig. 6(a) and Fig. 6(b)). For requirement (ii), generating a feasible schedule satisfying Constraint 4 is equivalent to finding a rectangle of area C j , where the length equals to T j and the height equals to c(m)•|B j | (see Fig. 6(c)). Since the data rate of individual RBs is different, the width of the rectangle is not only determined by the number of RBs, |B j |, but also the set of allocated RBs and the corresponding MCS index. This problem with non-identical RBs is a variation of the largest empty rectangle problem where many efficient algorithms can be applied, e.g., [47], [48].

If a feasible schedule can be generated for each flow f j ∈ F 2 , Problem P is solved, i.e., all the flows in F are schedulable. Note that, 5G-TPS aims to generate a schedule for flow set F in an efficient and effective manner. For this reason, some solutions of Problem P may be pruned from the search space (e.g., some other RB allocations leading to higher β i (x) with a larger x in Phase 1). Therefore, our solution only provides a sufficient schedulability condition for flow set F.

VII. DYNAMIC SCHEDULE ADJUSTMENT

In industrial 5G NR, the channel condition between a UE and the gNB can vary over time caused by moving obstacles, multipath propagation and interference from other devices, etc. In this section, we generalize the system model to consider channel dynamics and present a dynamic schedule adjustment method based on the two-phase design of 5G-TPS.

As shown in Fig. 7, when the network channel condition is stable, the feasible schedule of each UE is carried out through the DCI messages on PDCCH (Physical Downlink Control Channel). Upon any channel condition change being measured by UE u e , it sends an updated CQI report to the gNB on PUCCH (Physical Uplink Control Channel) to specify the new q b e values on certain RBs b ∈ B + . To respond to the channel condition change, the gNB adjusts the schedule(s) for u e and other UEs if needed, and transmits the updated schedule via the subsequent DCI messages.

The gNB may receive multiple updated CQI reports from different UEs within a short time interval. In this case, the gNB just recomputes the schedules for all the affected UEs. Therefore, we follow an event-triggered mechanism to perform schedule adjustment at the gNB, when the channel condition changes for a particular UE u e , with the aim to satisfy the timing requirements of all the flows. The schedule adjustment problem can be defined as follows. Problem P3. Given the updated set {q b e |(b ∈ B + )} for UE u e , the schedule of each flow f i ∈ F, determine the schedule adjustment to meet the deadlines of all the flows f i ∈ F.

The channel condition change of u e can be classified into three cases. Case 1: ∀b ∈ B e , a b,m e = c(m). In this case, the maximum usable MCS q b e on each allocated RB b is still larger than or equal to the selected MCS m. That is, the achieved data rate on B e of flow f e in each scheduled TTI still satisfies the data rate requirement according to Lemma 1. Thus, the gNB does not need to adjust the schedule for flow f e . In this case, the maximum usable MCS q b e on certain allocated RB(s) b is smaller than MCS m, and the achieved data rate on each of these RB(s) drops to 0 according to the MCS model. However, another MCS index m can be used to achieve a data rate higher than or equal to the requirement, i.e., α(B e ) ≥ Ce Te•MR . Thus, the gNB only updates the MCS index for u e . Case 3: α(B e ) < Ce Te•MR . In this case, the amount of data that can be transmitted by each packet of f e is less than its payload size according to its current schedule, thus the schedule needs to be adjusted.

To handle Case 3, we leverage the remaining RBs to schedule f e using Phase 2. i.e., solving Problem P2. If using the remaining RBs cannot satisfy the timing requirement of f e for the channel condition change, we re-generate the schedule for all the flows f i ∈ F using Phase 1 and Phase 2 7 . If Phase 1 and Phase 2 fail, we deem that flow f e is unschedulable after channel condition change.

A. Case Study

Setup. We perform a case study using the specifications of the mobile operation panel use case provided by 3GPP (Table A.2.4.1A-1 in [1]). The use case consists of four applications: 1) Emergency Stop (ES) for connectivity availability, 2) Safety (S) data stream, 3) Visualization of Control (VC), and 4) Haptic Feedback (HF) data stream. The flow specifications and UE locations are provided in Fig. 8. We consider a 20 MHz bandwidth network consisting of 100 RBs. The average q b i of each UE is configured according to the path loss effect based on its distance to the gNB. We set M T = 8 and M R = 4.

We let the network run for 40s, i.e., 1000 hyperperiods. In the first 500 hyperperiods, we apply a stable channel condition where q b i for each UE is randomly updated once every H TTIs. In the rest 500 hyperperiods, we assume dynamic channel conditions, where q b i for each flow is frequently changed every two packets. Fig. 8(a) summarizes the latency experienced by all the packets released from individual applications. Results. In the stable channel condition, although the packets from a same application may have different latency, they can always be transmitted within their deadlines. In the dynamic channel condition, the latency distribution of each flow is more scattered since more schedule adjustments are performed for each flow. On the other hand, flow S encounters a fraction of deadline misses (188 packets out of 80000 packets, denoted as ∞), which happens when a feasible schedule cannot be generated for flow S. However, most of the packets from all the applications still meet their deadlines.

B. Experiment Setup

To evaluate the performance of 5G-TPS under various network settings, we generate a large number of random synthetic flow sets. To speed up the simulation which involves many network nodes, we do not perform computational PHY processing of the air interface but focus on the MAC layer scheduler evaluation. 2) Metrics: We use Schedulability Ratio (SR) as the metric for performance evaluation under the stable channel condition setting. SR is defined as the ratio of feasible flow sets to all the generated flow sets. In the dynamic channel condition, we use the number of Deadline Missed flows (DM) to evaluate the performance of 5G-TPS in schedule adjustment.

3) Compared Methods: We compare the performance of 5G-TPS with the following scheduling methods. SMT: The Satisfiability Modulo Theory-based exact solution (the SMT specifications are omitted due to page limit). MUST: A 5G NR scheduler aiming at maximizing the number of packets delivered within the deadlines [49]. MUST relies on a greedy approach to assigning the most urgent packets with RBs of the highest data rate. CA: A channel condition-aware response time analysis for 5G networks under fixed-priority scheduling [26]. CA is based on an over-simplified resource model where the entire bandwidth is treated as one single RB. A generalized version considering multiple RBs, denoted as CA-Ext, is also implementedfoot_7 . RR, MT, and PF: The built-in flow schedulers (i.e., roundrobin, maximum CQI, and proportional fair) in OAI 5G [50].

DRR and PQ: Two extended flow schedulers (i.e., deficit RR and priority queue) based on the built-in schedulers [51].

1) Stable Channel Condition:

In the first set of experiments, we compare the SRs of all the methods by varying the normalized utilization U * under stable channel conditions. Due to the runtime limitation suffered by the SMT-based solution, we make the performance comparison under two network settings: (1) an extremely small scale network with 3 UEs, 8 RBs, M R = 2 and M T = 4, and (2) a more practical large scale network with N = 25, B = 50, M R = 4 and M T = 16. Further, we set a 3000s timeout limit for the SMT approach in large scale networks to prevent it from spending a long time for finding a result.

Small scale networks. Fig. 9(a) shows the SR as a function of U * in small scale networks. Each point represents the average value of 5000 trials. The results show that the SRs of all the methods decrease with the increasing of U * and SMT dominates others as an exact solution. The SR gap between SMT and 5G-TPS is small (4.63% on average) which validates the effectiveness of 5G-TPS. On the other hand, 5G-TPS significantly outperforms most of the other methods (e.g., 15.44% higher than DRR on average) and shows almost the same SR with MUST (0.79% lower on average). However, MUST degrades significantly when the network scales to the normal size (i.e., N = 25, B = 50 as shown in the next section). The SR of CA is very low (only 8.84% on average) while the extended version CA-Ext shows a much higher SR (38.32% on average). This demonstrates the limitation of the over-simplified resource model used in [26].

Large scale networks. Fig 9(b) shows the SR as a function of U * in large scale networks. We can see that the SRs of SMT, PF, MT, PQ and CA drop significantly compared to those in the small scale networks (17.97% lower on average), and the SRs of CA-Ext, RR and DRR drop slightly (3.66% lower on average). The degradation of SMT is mainly because it fails in most cases under the timeout limit. For example, when U * = 0.6 and SR = 0%, only 7.3% flow sets are determined by SMT as unschedulable while all other failures are caused by timeout. The SR drops of the other methods demonstrate that they cannot properly perform resource allocation for many UEs, even with more available network resources.

On the other hand, the SRs of 5G-TPS and MUST increase, where the SR increase of 5G-TPS (18.36% higher on average) is much larger than that of MUST (9.84% higher on average). This demonstrates that 5G-TPS can better utilize the network resources to accommodate a large amount of real-time flows.

2) Dynamic Channel Condition: In the second set of experiments, we evaluate all the methods in large scale networks with dynamic channel conditions. We randomly generate one flow set with U * = 0.4 and run continuously for 200 hyperperiods. q b i of each UE u i is randomly updated once within each hyperperiod. In this experiment we do not evaluate SMT and CA because the high overhead of SMT hinders it from being applied for on-line schedule adjustment and the performance of CA is dominated by CA-Ext according to the results in the previous experiments.

Fig. 9(c) shows the DM distributions of all the methods and the result of each method represents the DM statistics in one hyperperiod. We can observe that all the methods suffer from deadline misses for certain flows. However, 5G-TPS outperforms all the others in terms of much lower DM where only one flow misses its deadline in one hyperperiod (i.e., the outlier 1). MUST satisfies the deadlines of most flows with an average DM of 0.47 where at most 3 flows miss their deadlines in one hyperperiod. However, MUST results missing deadline flows in 66 hyperperiods. The other methods suffer from higher DMs, especially for MT, PF and PQ, where flows miss their deadlines in all the hyperperiods.

3) Runtime: Since 5G-TPS may rerun both Phase 1 and Phase 2 online in response to channel condition changes, we evaluate the runtime of 5G-TPS to validate its online adoption. Our primary focus is on comparing the runtime trends across different methods, rather than the absolute runtime values since our experiments are conducted in Python on a single-core processor which is not comparable to the performance of commercial gNBs (e.g., Atom P5900 with up to 24 cores in Nokia AirScale Radios). In addition, SMT suffers from extremely high runtime (e.g., > 2 hours when N > 5 or B > 10), and thus cannot be used for runtime reconfiguration. Such high overhead also hindered us from including SMT in the comparison. Fig. 10 presents the average runtime of each method, with N and B as variables.

From the results, we can observe a linear increase in the runtime of most methods with the increases of N and B. However, the runtime of MUST experiences an explosive growth with the increase of N , possibly due to its per-TTI and packet-based scheduling design. In contrast, 5G-TPS consumes less time compared to MUST (38.12% lower on average) and the built-in scheduler PF (57.29% lower on average), demonstrating its efficiency.

A. Ultra-Reliable Low-Latency Communications

Supporting ultra-reliable low-latency communications (URLLC) traffic is one of the key revolutionary novelties of 5G NR. URLLC targets ensuring extremely low latency in the order of 1ms and providing high reliability of 99.999% for flows with timing requirements. Some existing works on URLLC focus on the lower layer functionality (e.g., designing new robust MCSs [52]- [54], HARQ enhancement [55], [56] and power management [57]- [59], etc.). On the other hand, many recent works study the scheduling problems for URLLC in 5G NR which can be classified into two categories.

In the first category, the problems of joint scheduling for coexisting URLLC and enhanced mobile broadband (eMBB) traffic (e.g., web, video) are widely studied [60]- [62]. However, all these works mainly focus on maximizing the performance of eMBB traffic in the presence of sparse URLLC traffic. They all assume that the timing requirements of URLLC traffic can be satisfied by immediately scheduling them upon arrival and preempting the ongoing eMBB traffic. They do not consider massive URLLC scenarios where a large number of URLLC flows contend for the network resource.

In the second category, several scheduling algorithms and resource allocation methods based on Proportional Fair (PF) are proposed for URLLC traffic [23], [63]- [65]. However, all of these works do not address whether flows can be delivered before their deadlines. Alternatively, some approaches have been proposed to satisfy the timing requirements of URLLC traffic [49], [66], [67]. In [67] and [66], the authors simplify the scheduling problem by considering either Frequency Division Multiple Access (FDMA), which is inefficient in the time domain, or Time Division Multiple Access (TDMA), which is inefficient in the frequency domain. Instead, [49] considers OFDMA-based 5G networks, similar to our work. However, they simply ignore the data rate impact of MCS selection on different RBs and do not consider MIMO networks.