MAC for Machine Type Communications in Industrial IoT -- Part II: Scheduling and Numerical Results

In the second part of this paper, we develop a centralized packet transmission scheduling scheme to pair with the protocol designed in Part I and complete our medium access control (MAC) design for machine-type communications in the industrial internet of things. For the networking scenario, fine-grained scheduling that attends to each device becomes necessary, given stringent quality of service (QoS) requirements and diversified service types, but prohibitively complex for a large number of devices. To address this challenge, we propose a scheduling solution in two steps. First, we develop algorithms for device assignment based on the analytical results from Part I, when parameters of the proposed protocol are given. Then, we train a deep neural network for assisting in the determination of the protocol parameters. The two-step approach ensures the accuracy and granularity necessary for satisfying the QoS requirements and avoids excessive complexity from handling a large number of devices. Integrating the distributed coordination in the protocol design from Part I and the centralized scheduling from this part, the proposed MAC protocol achieves high performance, demonstrated through extensive simulations. For example, the results show that the proposed MAC can support 1000 devices under an aggregated traffic load of 3000 packets per second with a single channel and achieve<0.5ms average delay and<1% average collision probability among 50 high priority devices.


I. INTRODUCTION
Industrial internet of things (IIoT) demands design innovations in wireless communications to enhance the support for machine-type communications (MTC) [1]. Part I of this work introduces our medium access control (MAC) protocol for MTC in IIoT [2], which provides a potential to increase network capacity and improve quality of service (QoS) performance through increasing channel utilization efficiency. Meanwhile, how to utilize this potential to guarantee stringent QoS requirements in a dense network calls for further investigation. Specifically, given the proposed mini-slot based slot structure and a large number of devices, proper scheduling, i.e., determining the slot/cycle lengths and assigning the devices specific slots and mini-slots, has a significant impact on the MAC performance.
In our networking scenario, scheduling is for single-hop and uplink communications. Even in this limited scope, many research works exist in the literature, with a common focus on the trade-off between performance and signaling overhead. Early works include the development of semi-persistent scheduling for voice over IP in LTE [3], which aims to achieve a balance between system capacity and signaling overhead. For the wireless local area network (WLAN), Wang and Zhuang propose a token-based scheduling scheme, which achieves performance prioritization for different traffic types with a low overhead in a fully connected network [4]. Gamage et al. develop uplink scheduling for WLAN and cellular interworking to enable multi-homing voice and data services [5].
Despite the abundance of existing studies, scheduling in the setting of MTC and IIoT remains challenging. Ksentini et al. note the potentially overwhelming overhead in the uplink scheduling with a massive number of MTC connections and consider a simple round-robin scheduling algorithm for the case with no QoS requirements [6]. Lioumpas et al. recognize that schedulers designed for general cellular networks cannot be directly applied to MTC, due to a higher device density and a wider variety of QoS requirements, and propose a scheduling algorithm to prioritize devices with low delay tolerance [7]. However, the delay requirements considered therein is in the range from 10 milliseconds (ms) to 10 minutes, which can be too large for IIoT applications.
To handle a large number of devices, a popular strategy is to divide the devices into groups (or clusters) and schedule the devices based on the groups [8]. Si et al. propose a groupingbased algorithm that adjusts the service rate for each user group to provide statistical QoS guarantees, where the considered delay requirements are in the range from 20ms to 100ms [9]. Karadag et al. present semi-persistent scheduling for MTC in cellular networks, taking delay constraints of devices into account, where devices have periodic traffic arrivals [10]. Zhang et al. propose a random access scheme for MTC in cellular networks by grouping devices according to their delay requirements and applying access control for each group based on the group size, aggregated packet arrival rate, etc. [11]. Arouk et al. propose a group paging based scheduling for massive MTC access in cellular networks, where the key idea is to scatter the contention for channel access to improve performance in terms of delay, collision probability, and energy consumption [12]. The focuses of the last two works are on throughput maximization and energy consumption reduction, respectively, rather than supporting a stringent (e.g., ms level) delay requirement.
Given a high device density, diversified service types, and stringent QoS requirements, scheduling may need to be further fine-grained. Specifically, a scheduler may need to attend to the available information (e.g., packet arrival rate) or access strategy of each single device. Salodkar et al.
propose a learning-assisted scheduling scheme, in which each device uses reinforcement learning to determine a preferred transmission rate and a base station (BS) schedules the device with the highest rate [13]. Such a scheme can adapt to unknown packet arrival statistics. Chang et al.
propose device-level uplink scheduling schemes based on conflict-avoiding codes, in which each device is assigned a two-dimensional code matrix [14]. These schemes are applicable when multiple channels are available. In their recent work, Rodoplu et al. present proactive forecastingassisted scheduling to support massive access in the internet of things (IoT), which explores machine learning to predict the traffic of each device and reserve channel time accordingly [15].
The scheme improves network performance with low overhead. Yang et al. utilize a neural network to predict the number of IoT devices and Wi-Fi users, which facilitates dynamic scheduling and channel allocation for co-existing IoT and Wi-Fi communications [16].
In Part II of this work, our objective is to develop an effective scheduling scheme to pair with the proposed protocol in Part I. Different from the existing works, we focus on achieving QoS guarantee with very low delays. As a part of our MAC protocol, the scheduling scheme contributes to a customized link-layer solution to MTC in IIoT, supporting high device density, diversified service types, and stringent QoS targets. While we aim to maximize channel utilization efficiency through delicate distributed coordination in the MAC protocol in Part I, the focus in Part II is to develop a centralized analysis-based scheduling scheme. The scheduling scheme should achieve a desired balance in the QoS of different services or different QoS metrics for the same service. The integration of distributed coordination and centralized control is expected to strengthen the proposed MAC protocol.
With a large number of devices, finding a proper assignment for a centralized scheduler can be prohibitively complex. Scheduling for a dense network with hundreds or even thousands of devices can be beyond the reach of conventional approaches, when the packet arrival rate of each device may impact the protocol parameters and the QoS requirement of each device needs to be satisfied. This motivates us to exploit neural networks to assist scheduling. We propose to schedule in two steps, i.e., slot/mini-slot assignment and protocol parameter selection, and develop methods to reduce complexity in each step. The main contribution of this part is twofold: First, we develop algorithms to assign devices specific slots and mini-slots of the proposed protocol in Part I, when the protocol parameters are given. Based on the analytical results in Part I, the proposed algorithms sort devices of each type, estimate the impact of potential assignments for each device, and make assignments for the devices one by one. As a result, the assignments possess the due accuracy and granularity necessary for satisfying diverse and stringent QoS requirements; Second, to determine the protocol parameters, we exploit a deep neural network (DNN) to assist scheduling. The DNN is structured such that it can be used given any number of devices and learn the mapping from various combinations of device and packet arrival profiles and protocol parameter settings to the resulting scheduling performance.
We demonstrate that, after sufficient training, the DNN can learn the mapping. Then, given a specific device and packet arrival profile, the DNN can be used to compare different protocol parameter settings and determine proper parameters for the proposed MAC. In addition, we perform extensive simulations to demonstrate the properties of the proposed MAC protocol, the accuracy of the analysis in Part I, and the performance of the scheduling scheme developed in this part.
The rest of Part II is organized as follows. Section II describes the scheduling problem.
Section III investigates the device assignment. In Section IV, we exploit a DNN to determine protocol parameters. Section V present the numerical results, and Section VI concludes this work.  Fig. 1: An illustration of the scheduling problem. Different colors in the sub-blocks of a minislot correspond to different devices assigned that mini-slot, while dot-filled, solid-filled, and grid-filled patterns represent mini-slots assigned to HP, RP, and LP devices, respectively. The scheduling problem involves determining protocol parameters n m , r H , r R , and r L as well as assigning slots and mini-slots to all devices.

II. THE SCHEDULING PROBLEM
Our considered network scenario and proposed MAC protocol are given in Sections II and III of Part I, respectively [2]. To avoid redundancy, we refer readers to the aforementioned sections for the related information. According to the protocol description in Section III and performance analysis in Section IV in Part I of this paper, it is clear that the following factors have significant impact on the performance of the proposed MAC protocol: • The number of mini-slots in each slot, i.e., n m ; • The assignment cycles r H , r R , and r L , which serve as different frame lengths for different types of devices; • The device assignment, i.e., the allocation of devices to slots and mini-slots.
We refer to the problem of determining the above factors with the objective of satisfying QoS requirements as the packet transmission scheduling problem, which is illustrated in Fig. 1. The access point (AP) in the network is expected to have computing capability and conduct the scheduling.
Note that the scheduling problem may not be always feasible. Indeed, we cannot guarantee the satisfaction of arbitrary QoS requirements given an arbitrarily large set of devices with arbitrary packet arrival rates. Thus, the objective here is to investigate effective scheduling that can support as many devices as possible while satisfying their QoS requirements.
Given the sets of all devices D = {1, . . . , D}, high-priority (HP) devices D H , regular-priority (RP) devices D R , low-priority (LP) devices D L , and packet arrival rates {λ i }, i ∈ D, we attempt to accommodate all devices while satisfying the delay requirements δ H , δ R , and δ L and packet collision probability requirements ρ H , ρ R , and ρ L for the HP, RP, and LP devices, respectively.
Based on the protocol, the following constraints exist for the scheduling problem (see Section III-D of Part I): • The LP assignment cycle length r L is a multiple of the RP assignment cycle length r R , which in turn is a multiple of the HP assignment cycle length r H ; • A mini-slot should not accommodate more than one type of devices; • If mini-slot m of slot l, where l ≤ r H and m ≤ n m , is assigned to a subset of HP devices I H , then mini-slot m of slot l , for any l ∈ {r H + l, 2r H + l, . . . , r L − r H + l}, is also assigned to the same set of HP devices I H . If mini-slot m of slot l, where l ≤ r R and m ≤ n m , is assigned to a subset of RP devices I R , then mini-slot m of slot l , for any l ∈ {r R + l, 2r R + l, . . . , r L − r R + l}, is also assigned to the same set of RP devices I R .
Both cases are illustrated in Fig. 1.
To solve the scheduling problem, we first investigate the device assignment while assuming the protocol parameters n m , r H , r R , and r L are given. Then, we explore a DNN to assist determining these parameters. In both steps, we assume that mini-slot based carrier sensing (MsCS), synchronization carrier sensing (SyncCS), differentiated assignment cycles, and superimposed mini-slot assignment (SMsA) from Part I are all adopted in the proposed MAC protocol.

III. THE DEVICE ASSIGNMENT
In this section, we first discuss the impact of protocol parameters (n m , r H , r R , and r L ) and then investigate the device assignment problem.
A. Impact of n m Intuitively, increasing n m , subject to the conditions mentioned in the end of Section III-B of Part I, can support more devices via more mini-slots. However, increasing n m increases delay, and consequently packet collision probability, of all devices. Therefore, given the QoS requirements of devices, increasing n m may reduce the number of supported devices subject to the requirements.
B. Impact of r H , r R , and r L The delay requirements δ H , δ R , δ L place constraints on r H , r R , and r L , respectively. Consider HP devices for example. When there are n m mini-slots in each slot, an upper bound on the number of slots per HP assignment cycle, i.e., r H , is given by 1 where · is the floor function. The denominator is the length of a slot. The factor '2' in the numerator follows from the fact that the average gap between the beginning of an HP cycle and the arrival of an HP packet is equal to one half of an HP cycle.
Using (1), a relation between n m and r H can be obtained. If n m is large, r H should be small, and the HP devices will be "densely" packed into the r H slots. As a result, it can be challenging to satisfy the QoS requirements of HP devices. On the other hand, if n m is small so that r H can become large, more slots are available for HP devices in each frame. However, the transmission opportunity for RP and LP devices will decrease. Therefore, determining appropriate values for r H , r R , and r L is crucial but nontrivial.

C. Device Assignment
The assignment of slots and mini-slots to devices is a complex problem. Consider the case with buffer and SMsA. Even if n m , r H , r R , and r L are given, the device assignment is a combinatorial integer programming problem. Based on the analysis in Section IV-E of Part I, assigning any new device an occupied mini-slot can affect the delay and collision probability of all other devices assigned that mini-slot.
We propose a heuristic algorithm for device assignment, built on the analysis in Section IV of Part I, when n m , r H , r R , and r L are given. The analysis allows us to estimate the delay and collision probability of devices in a mini-slot after adding each new device to the mini-slot.
The proposed assignment algorithm tentatively assigns a device while estimating the resulting performance, with the target of satisfying the QoS requirements of all assigned devices in the process. The following settings are used in the assignment: • All devices assigned the same mini-slot have the same priority type; • The maximum packet collision probability among all devices assigned the same mini-slot is referred to as the collision probability for that mini-slot and denoted by q c m,l for mini-slot m of slot l; • Under the assumption that the impact of collision probability on the cycle length is negligible, the length of an LP cycle can be calculated by which is based on (12) in Part I of this paper. The parameter n s in (12) of Part I, i.e., the number of slots in a general frame, is replaced with r L in (2) since an LP cycle serves as a frame for LP devices. Note that the use of differentiated assignment cycles does not change the packet arrival rates. Based on the constraints mentioned in Section II, all devices should be scheduled at least once in an LP cycle, which leads to the summation over the packet arrival rates of all devices in the denominator of (2).
Letm l denote the minimum index among the mini-slots of slot l that have not been assigned to any device. For notation simplicity, we omit subscript l inm l whenm l and l both appear in the subscript (e.g., q ĉ m l ,l will be written as q ĉ m,l ). The length of the HP, RP, and LP assignment cycles are denoted by T H f , T R f , and T L f , respectively. The proposed assignment is given in Algorithms 1 and 2. Algorithm 1 is the core algorithm for assigning slots and mini-slots to a set of devices with the same priority for a given cycle length, while Algorithm 2 is the overall algorithm that calls Algorithm 1 to make assignments for all devices and all cycles.
In the two algorithms, variables n c i , Λ m,l , and Γ m,l denote the expected number of simultaneously transmitting packets given that device i is transmitting (which can be larger than 1 as a result of a nonzero collision probability), the aggregated packet arrival rate for all devices assigned mini-slot m of slot l, and the accumulated number of packet arrivals for all devices assigned mini-slots 1 to m of slot l in the corresponding cycle, respectively. Detailed description can be found in Appendix C of Part I and is omitted here for brevity.
The basic ideas of Algorithms 1 and 2 are given as follows. Algorithm 1 assigns mini-slots to devices, starting from the first mini-slot of every slot, and tracks the current mini-slot being assigned. It tentatively assigns a device the current mini-slot of all available slots, trying to find the best assignment based on the resulting delay and packet collision probability estimations. If the current mini-slot in none of the slots can accommodate the device by satisfying its collision Algorithm 1 Core Assignment Algorithm Quit with flag F = i; 5: Calculateq ĉ m,l for tentative assignment {m l , l}, ∀l ∈ S † , using either (3a) or (4a) withq c m,l replaced byq ĉ m,l , depending on whether device i is the first device assigned this mini-slot. 9: if min l∈S †q ĉ m,l > ρ † andm l = n m , ∀l ∈ S † then 10: Quit with N † a = i; 11: else if min l∈S †q ĉ m,l > ρ † and ∃l ∈ S † :m l < n m then 12: Update R † = {l ∈ S † |m l < n m }; 13: Updatem l =m l +1, calculate τm ,l , and go to Step 3; Update q ĉ m l ,l by setting q ĉ m l ,l =q ĉ m l ,l ; 18: Update n i , Λm l ,l , Γm l ,l using (3b) to (3d) or (4b) to (4d). 19: probability requirement, the algorithm moves to the next mini-slot. The procedure repeats until any of the following three conditions is satisfied: i) all devices are allocated, ii) there is no Output: Device assignment matrix A (size 2 × D), Assignment success flag F s .
Initialize: i = 1, q c m,l = 0, ∀m, l, n c j = 0, ∀j ∈ D, F s = 0; Set A R and A L to all-zero matrices with sizes 2 × D R and 2 × D L , respectively. 1: Calculate the LP Cycle length using (2). Calculate the RP and HP Cycle length using For each slot l ∈ R † and any l ∈ {r H + l, 2r H + l, . . . , r R − r H + l}, add l to R † and let Γm ,l equal Γm ,l . Then, calculate τm ,l , ∀l ∈ R † .

7:
Run Algorithm 1 with inputs {Γm ,l } ∀l and R † from Step 6, and any l ∈ {r R + l, 2r R + l, . . . , r L −r R +l}, add l to R † and let Γm ,l equal Γm ,l . Then, calculate τm ,l , ∀l ∈ R † . 10: Run Algorithm 1 with inputs {Γm ,l } ∀l and R † from Step 9, 11: In the core assignment algorithm (Algorithm 1), adding a device to a mini-slot has an impact on Λ m,l , Γ m,l , and q c m,l . Therefore, after assigning device i mini-slot m of slot l, these variables need to be updated for the mini-slot. If device i is the first device assigned mini-slot m of slot l, the following update applies:q c m,l = 0 (3a) wherex represents an updated value of x after assigning device i, and T † f is the corresponding (HP, RP, or LP) cycle length. If device i is not the first device assigned mini-slot m of slot l, the following update applies:q

IV. LEARNING-ASSISTED SCHEDULING
The proposed device assignment in the preceding section can be applied when the parameters n m , r H , r R , and r L are given. In this section, we propose learning-assisted scheduling to determine the values of these protocol parameters.
A. Motivation for learning-assisted scheduling Choosing proper values for those protocol parameters is challenging. First, the impact of protocol parameters n m , r H , r R , r L and the impact of device assignment are correlated. For example, knowledge of the slot/mini-slot assignment is required to analyze the impact of n m , while the assignment cannot be determined without knowing n m first. Second, the effects of n m , r H , r R , r L on the performance are mutually dependent. Consider n m and r H as an example.
Both n m and r H affect the delay of HP devices. The impact of adjusting r H depends on the value of n m , and the dependence is further affected by the device packet arrival rate profile. As a result, we cannot establish an analytical model for determining n m , r H , r R , and r L . On the other hand, using brutal force to choose their values is not viable due to the large number of diverse devices. There are usually too many candidate combinations of n m , r H , r R , and r L , and each combination requires a re-calculation of the device assignment using Algorithms 1 and 2.
As the assignment algorithm is based on calculating the delay and collision probability while assigning each device, the complexity of recalculating all assignment for all combinations can be very high. 3 Consequently, we use a learning-based method to capture the impact of n m , r H , r R , r L and determine their values. Specifically, we train a DNN to learn the mapping from the combination of device and packet arrival rate profiles and protocol parameter settings to the protocol performance.
A significant part of the training can be done offline to avoid a long training duration in an online setting caused by searching for and determining appropriate protocol parameters.

B. The Role of the DNN
We use a DNN to assist in determining the parameters of the proposed MAC protocol, as follows. First, for each device and packet arrival rate profile 4 , we try different combinations of n m , r H , r R , and r L , use the heuristic algorithm to obtain the assignment, and test the resulting performance using simulations. Then, the device and packet arrival rate profile, protocol parameter settings (n m , r H , r R , and r L ), and the resulting protocol performance (as label) are used to train and test the DNN.
The data generation, training, and testing are conducted offline. When the DNN is well-trained, we can imitate the mapping from a device and packet arrival rate profile and a protocol parameter setting to the protocol performance. Accordingly, we can determine the protocol parameters The DNN following the above-mentioned design is illustrated in Fig. 2. The DNN is implemented by Keras [19], a high-level neural network application programming interface using Tensorflow backend. The objective of the offline training is to find an appropriate θ value that minimizes the loss function L(θ) represented by the mean squared error (MSE) for regression.
Adam optimizer [20] is adopted to minimize the loss function iteratively, where the optimizer is set with learning rate α = 1e-3 and exponential decay rates β 1 = 0.9 and β 2 = 0.999.
The labels, i.e., the protocol performance under specific device and packet arrival rate profiles and the protocol parameter settings, are generated via simulations. Although we can generate the labels offline, a very large training set may not be practical as it could require overwhelmingly long simulations. Meanwhile, the simulation results also demonstrate randomness, due to the randomness in the packet arrival at each device. Given the limited training set with randomness in the labels, the problem of over-fitting can be severe. We can use random dropout to alleviate over-fitting and improve the robustness of the training model [21].
It is worth noting that our DNN does not directly output the best protocol parameters {n m , r H , r R , r L }.
An alternative design is to train a DNN that outputs the best {n m , r H , r R , r L }.  [23]. Using this mini-slot length, the overhead in each slot incurred by having n m mini-slot for channel sensing is 9 × 10 −6 × n m seconds. For example, consider a packet length of 50 bytes in the physical layer, and a data transmission rate of 3 Mb/s, which yields a data transmission duration of 133 µs. With 10 mini-slots in each slot, the overall length of mini-slots is 90µs in every 233µs.

A. Mini-slot Delay with MsCS, SyncCS, and SMsA
Via simulations, we evaluate the mini-slot delay 5

in the cases with and without SyncCS and
SMsA and compare the numerical results with the analytical results from Section IV of Part I.
We focus on different mini-slots of one target slot. The general settings in this subsection are as follows (unless stated otherwise): • n m and n s are set to 10 and 100, respectively;   • T m is set to 9µs. T x is 133µs, i.e., the duration of a 50-byte physical-layer packet transmitting at 3 Mb/s. Accordingly, T s in its full length is 223µs, i.e., 10 × 9µs + 133 µs; • Device i is assigned a mini-slot with smaller index than the mini-slot of device j if λ i < λ j ; • 20000 frames are simulated for each case.
Mini-slot delay with MsCS and with MsCS and SyncCS: Fig. 3 shows the results with only MsCS (i.e., no SyncCS or SMsA), with and without buffer, as well as the results with both MsCS and SyncCS, in the case with buffer, for Poisson packet arrivals. The overall delay includes both the base and the access delay. The packet arrival rate of each device is randomly generated based on a uniform distribution. Fig. 3(a) corresponds to a lower packet arrival rate, i.e., in the range between 0.2 and 1 packets per second per device, and Fig. 3(b)corresponds to a higher packet arrival rate, i.e., between 1 and 5 packets per second per device. The analytical results in respectively. It can be observed that: • The difference between the analytical and numerical results is small for all mini-slots in all cases; • The delay increases slowly with the mini-slot index for the first several mini-slots but faster for the last several mini-slots in the case of higher packet arrival rate; • The difference in delay with and without buffer is insignificant under lower packet arrival rate and significant under higher packet arrival rate; • Without SyncCS, the delay for the first mini-slot is around 11ms. For the last mini-slot, depending on the packet arrival rate, the delay ranges from 15ms in Fig. 3(a) to 125ms in Fig. 3(b), less than the average packet arrival interval in all cases; • With SyncCS, the delay is reduced by more than 50% for each mini-slot as compared with the case without SyncCS. In the case of a higher packet arrival rate in Fig. 3(b), the maximum delay decreases from about 125ms to around 35ms.
Overall, the numerical results demonstrate the accuracy of (3) and (6)  Mini-slot delay with MsCS and SMsA: In this simulation example with SMsA (but not SyncCS), each mini-slot accommodates 7 devices instead of one. Note that such mini-slot usage is not optimal and is only used for illustrating the impact of SMsA on the mini-slot delay. As the 10 mini-slots accommodate 70 devices in total, the slot is prone to overloading if the packet arrival rate is high. Therefore, we use low packet arrival rate in this example. Fig. 4 shows the case (a) without and (b) with buffer, respectively. Now that each mini-slot accommodates 7 devices, there are 7 numerical results on the delay for each mini-slot. The simulation results overlap in Fig. 4, suggesting that the delay for all 7 devices in any given mini-slot is almost identical. This is consistent with Theorem 3 in Section IV-E of Part I. Moreover, the simulation results match closely with the analytical results based on Appendix C of Part I.
Impact of mini-slot length and frame length: We use the same settings as in Fig. 4 with buffers, except for a change in the mini-slot length or the frame length. The mini-slot usage here is still not optimal and only for showing the impact of mini-slot and frame lengths. In Fig. 5(a), the mini-slot length reduces to 7µs from 9µs in Figs. 3 and 4. Comparing with Fig. 4(b), the impact of mini-slot length on the delay becomes evident. Accordingly, the performance of the proposed protocol can further improve if a reduction in the mini-slot length is feasible. In Fig. 5(b), the mini-slot length is back to 9µs, the packet arrival rate is multiplied by 5, and the frame length reduces to 5 slots from 100 slots. Comparing with Fig. 4(b), the impact of frame length on the delay and the necessity of differentiated assignment cycles become clear. The results indicate  that a very low delay is achievable if we keep the HP assignment cycle sufficiently short.

B. Performance of the Device Assignment Algorithms
We evaluate the performance of the device assignment, i.e., Algorithms 1 and 2 in Section III-C of Part II, given n m , r H , r R , and r L . In the evaluation, MsCS, SyncCS, SMsA, as well as differentiated assignment cycles are used, and a buffer is assumed at each device. Again, T m and T x are set as 9µs and 133µs, respectively.
We consider 1000 devices with mixed packet arrival patterns. Specifically, the number of HP, RP, and LP devices is 50, 450, and 500, respectively. A half of all the devices, selected randomly, have Poisson packet arrivals with rate randomly selected from the range between 1 packet per second per device and 5 packets per second per device. The remaining devices have periodic  packet arrivals. The arrival rate is randomly distributed in the same range (i.e., [1,5]), and a random component within ±5% of the packet arrival interval is added to each arrival instant for periodical packets. Each slot consists of 8 mini-slots (i.e., n m = 8), and each HP assignment cycle consists of 5 slots (i.e., r H = 5). Delay thresholds δ H , δ R , δ L are set to 1ms, 10ms, and 80ms, respectively, while the packet collision probability thresholds ρ H , ρ R , and ρ L are set to 1.5%, 6%, and 10%, respectively.
A simulation duration of 2000 seconds is used to test the performance of Algorithms 1 and 2.    A less number of mini-slots leads to both shorter slots, which reduce delay for all devices, and higher slot idle probabilities, which contribute to a further reduction in delay thanks to SyncCS.
Further, Fig. 6 shows the impact of assignment cycles on the performance. Specifically, via different settings of r R and r L in Fig. 6(a) and Fig. 6(b), the possibility of making a trade-off between collision and delay is shown. Moreover, Fig. 6(a) and Fig. 6(b) demonstrate how our proposed algorithms can adapt to the given protocol parameters. In Fig. 6(a), r L is larger and each LP device has to wait for a longer duration before having a transmission opportunity. As a result, the probability that an LP device has a packet to send in its assigned mini-slot can be high, and assigning two or more LP devices the same mini-slot in such case can yield a high collision probability. Therefore, the algorithms choose to assign each LP device an exclusive mini-slot. In comparison, r L is much smaller in Fig. 6(b), and thus the probability that an LP device has a packet to send in its assigned mini-slot is lower. Therefore, the algorithms allow LP devices to share a mini-slot at the cost of small collision probabilities.   In the simulation examples in this subsection, the number of mini-slots, n m , and the assignment cycles, r H , r R , and r L , are not optimized. Thus, the resulting performance is not necessarily optimal. However, the results shown in Fig. 6 illustrate the advantage of the proposed MAC protocol and the assignment algorithms, in terms of satisfying stringent QoS, prioritization, and flexibility. Particularly, while random access is known to have distinctive advantage for low data traffic in delay as compared with scheduled access, e.g., as discussed in [24], we demonstrate that appropriate scheduling, combined with well-designed access protocol, can also achieve very low delay in a high-density MTC network.

C. DNN-Assisted Scheduling
The structure parameters of our proposed DNN are given in Table I We adopt the R-squared score to measure the fitness of our trained model in the training data set. The R-squared score is calculated by When the score is close to 1, the trained model can generate predicted results with a reasonably small variance. The R-squared score of the proposed DNN is shown in Fig. 8(b), in which the score converges to a value close to 1 after 10 epochs.
We further validate the fitness of the trained DNN model with the data from the test set.
The comparison between the predicted performance metric values and the ground truth labels is presented in Table II. 7 It can be seen that the predicted results can match the ground truth labels in the test set with low MSE, and thus the proposed DNN is able to learn the mapping from the device and packet arrival profile and the protocol parameter settings to the resulting performance after sufficient training.

VI. CONCLUSION
In Part II of this paper, we customize scheduling for our proposed MAC protocol in Part I