extfieldsofstudy:
Computer Science
Engineering

text:
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


extfieldsofstudy:
Computer Science
Medicine

text:
Discrete Two-Step Cross-Modal Hashing through the Exploitation of Pairwise Relations

The cross-modal hashing method can map heterogeneous multimodal data into a compact binary code that preserves semantic similarity, which can significantly enhance the convenience of cross-modal retrieval. However, the currently available supervised cross-modal hashing methods generally only factorize the label matrix and do not fully exploit the supervised information. Furthermore, these methods often only use one-directional mapping, which results in an unstable hash learning process. To address these problems, we propose a new supervised cross-modal hash learning method called Discrete Two-step Cross-modal Hashing (DTCH) through the exploitation of pairwise relations. Specifically, this method fully exploits the pairwise similarity relations contained in the supervision information: for the label matrix, the hash learning process is stabilized by combining matrix factorization and label regression; for the pairwise similarity matrix, a semirelaxed and semidiscrete strategy is adopted to potentially reduce the cumulative quantization errors while improving the retrieval efficiency and accuracy. The approach further combines an exploration of fine-grained features in the objective function with a novel out-of-sample extension strategy to enable the implicit preservation of consistency between the different modal distributions of samples and the pairwise similarity relations. The superiority of our method was verified through extensive experiments using two widely used datasets.

Introduction
With the development of Internet technology in recent years, a large quantity of multimodal data obtained from video, audio, image, text, and other sources are being disseminated rapidly across social networks. A common requirement in real scenarios is cross-modal retrieval, e.g., retrieving corresponding images or videos through text descriptions. Owing to the heterogeneity of multimodal data, cross-modal retrieval tasks must, unlike traditional retrieval tasks, bridge the semantic gap and acquire common and unified expressions. At the same time, the rapidly growing mass of data has increased the time and space costs of retrieval to serve users who generally expect to be able to quickly obtain information related to their retrieval targets.
Owing to its high retrieval efficiency and low space cost, cross-modal hashing has become one of the primary methods in the field of cross-modal retrieval [1]. Crossmodal hash learning attempts to convert multimodal data into a set of short binary codes (called hash codes) in Hamming space while preserving the original sample relations and then to learn a set of mapping functions from the specific modality to the sample hash code. e binary code of the common space and the mapping from the specific modality to the common space can be used to achieve crossmodal retrieval. As the similarities between hash codes are calculated as Hamming distances, the XOR operation can be implemented on hardware to significantly improve retrieval efficiency. Furthermore, the storage cost is reduced because the hash code length is relatively short. e existing cross-modal hashing approaches can be roughly divided into unsupervised and supervised methods. Unsupervised methods learn hash functions by exploiting the sample relations between and within modalities, which often have low accuracies. Supervised methods attempt to exploit the supervision information contained in labels and use the common semantic information in these labels to guide the learning of the hash code, thereby improving its quality. However, most existing supervised methods do not fully exploit the supervision information [2,3]. For example, Xu et al. [4] used label matrix regression alone and ignored the similarity relations between samples. Furthermore, the one-directional regression used by supervised methods is not conducive to the full exploitation of supervision information and will also cause the hash learning process to be unstable. erefore, in this paper we propose a new supervised cross-modal hashing method that combines label matrix factorization and hash code regression to achieve bidirectional mapping. In addition, a dual supervision approach is adopted to embed the label and pairwise similarity matrices into the hash learning process to further exploit the pairwise relations between modalities.
Another important problem in hash learning is the integer optimization problem caused by binary constraints. e introduction of the pairwise similarity matrix has made the optimization of the objective function more complicated. Currently available methods generally adopt a relaxation strategy in which the binary constraint is abandoned; instead, the real value is optimized and the thresholding method is then used to obtain a solution. However, this method will cause cumulative quantization errors. In this work, we propose a semirelaxed, semidiscrete strategy to minimize quantization errors and improve retrieval accuracy while ensuring the smooth optimization of the objective function. Furthermore, inspired by the concept of heterogeneous modal feature fusion under the bilinear model [5], we propose a simple mapping learning to fuse multimodal data to obtain more fine-grained high-order features, which are used in combination with the proposed out-of-sample extension strategy to implicitly preserve the similarity relations between samples.
In summary, the contributions of this study are as follows: (i) A new cross-modal supervised hashing framework using dual supervision information is designed to exploit the pairwise relations between samples. Furthermore, a semirelaxed and semidiscrete strategy is adopted to exploit the pairwise similarity matrix to reduce cumulative quantization errors. (ii) A new out-of-sample extension strategy with two novel optimization strategies is developed. By combining this strategy with the fine-grained features, the consistency between the different sample modal distributions and the pairwise similarity relations can be effectively preserved. (iii) Experiments were conducted on two widely used retrieval datasets to verify the effectiveness and superiority of the proposed method.
e remainder of the article is organized as follows. Section 2 briefly reviews some related works. Section 3 gives the details of DTCH. Section 4 presents the experimental results and discussions, followed by the conclusion in Section 5.

Related Work
e currently available cross-modal hashing methods can be primarily divided into linear model-based [6][7][8] and deep model-based [9][10][11][12] methods. Although some recently proposed methods based on deep models have improved retrieval performance, such approaches generally exhibit high time and space complexities and have poor interpretabilities. By contrast, linear models are more applicable to real scenarios owing to their high retrieval efficiencies and strong interpretabilities. e existing linear cross-modal retrieval methods can be further divided into two main categories: unsupervised crossmodal hashing [13][14][15] and supervised cross-modal hashing [16][17][18][19].
e unsupervised cross-modal hashing methods primarily learn hash functions by mining sample feature information to obtain relations between and within sample modalities. For example, Sun et al. [13] extended the traditional spectral hashing approach to the multimodal field by minimizing the Hamming distances between sample pairs. Intermedia hashing [14] learns hash codes by maintaining the semantic consistencies between and within modalities. Zhou et al. [15] proposed a latent semantic sparse hashing method in which matrix factorization and sparse coding are combined to discover a common Hamming space.
In contrast to the unsupervised learning methods, the supervised cross-modal hashing methods use label information and pairwise similarity information to improve hash code quality. Zhang et al. [16] used the pairwise similarity matrices generated from labels to learn hash codes and then attempted to use these hash codes to reconstruct the matrices with the goal of maximizing the semantic correlations of the hash codes. Xu et al. [4] extended supervised discrete hashing (SDH) [20] to the cross-modal field and used the label matrix regression method to directly learn hash codes. However, SDH adopts the bitwise learning strategy to generate binary codes, making it time-consuming. Chen et al. [17] proposed a scalable cross-modal hashing method in which matrix factorization is applied to the cross-modal field. Generally speaking, the retrieval accuracies of supervised learning methods are significantly higher than those of unsupervised methods owing to the exploitation of label information. In general, these methods are restricted by their weak representation ability. To obtain satisfactory accuracy, longer code lengths are often required, leading to greater storage and query costs.

Proposed Method
In this section, we introduce our method in detail in terms of its use of notation, binary code learning, optimization, outof-sample extension, and time complexity. e framework is shown in Figure 1.
with N sample pairs, we use v i ∈ R d to represent the eigen vector of the image modality in the i-th sample pair and t i ∈ R d to represent the eigen vector of the text modality in the i-th sample pair, where d and f are the corresponding eigen dimensions. Correspondingly, V ∈ R d×N and T ∈ R f×N represent the visual modal feature and the text modal matrices, respectively. In addition, Y is used to represent the sample label matrix, where y i � y ic ∈ 0, 1 { } C represents the label vector corresponding to the i th sample, where C represents the number of classes. If the current sample x i belongs to the c th class, then y ic � 1, where c � 1, . . . , C; otherwise, y ic � 0. At the same time, the label matrix Y is used to construct the pairwise similarity matrix S ∈ − 1, +1 { } N×N . If the sample pair i and j are similar, then S i,j � 1; otherwise, S i,j � − 1.

Binary Code Learning.
e goal of cross-modal hashing is to map heterogeneous multimodal data onto compact binary codes while preserving the semantic similarity of the original space. Intuitively, multimodal data describe the same entity and, therefore, their high-level semantics should be consistent.
is paper proposes a new cross-modal hashing framework that fully exploits the pairwise relations of samples contained in the label and pairwise similarity matrices to learn a unified binary code.
Inspired by Multimodal Discriminative Binary Embedding (MDBE) [21], we attempted to use matrix factorization to explore the semantic information implicit in the label matrix. is process can be formalized as follows: where B ∈ − 1, 1 { } N×L is the binary semantic representation learned from the label matrix, i.e., the hash code, and M is the auxiliary matrix. To avoid singular solutions, we add the L 2 -norm regularization term to M. In addition, by regressing the label matrix to the hash code, the label matrix can be embedded into the learning of the binary code as follows: where W is the linear mapping matrix. In addition to further exploration of the semantic information in the label matrix, equation (2) can be used to stabilize the hash learning process. e full exploitation of the label matrix can reduce the semantic gap caused by modal heterogeneity to the greatest extent possible, making it more likely that the hash code expresses high-level semantics beyond the specific modal. In other words, the label information is not restricted by the specific modality and the hash code learned from label information should be a more advanced representation that can cross the semantic gap. Additional important supervision information for the supervised hash learning method is obtained from the pairwise similarity matrix. A common approach to constructing the pairwise similarity matrix for the cross-modal supervised hashing method is to reconstruct the sample label matrix. If two sample pairs share one or more labels, they are considered similar, and vice versa. As the inner product of the hash code between two samples corresponds to the distance between the samples, it can be used as a measure of the similarity relation between the samples. erefore, the inner product of the hash code is used to fit the pairwise similarity matrix to ensure that the learned hash code maintains the similarity relations of the original space as much as possible, which is consistent with the original intention of cross-modal hash learning. is process can be modeled as follows: where B ∈ − 1, 1 { } N×L is the binary semantic representation learned from the label matrix, i.e., the hash code, and L  Computational Intelligence and Neuroscience denotes the length of hash code. Clearly, equation (3) is a nonconvex optimization problem that is difficult to solve. Many existing methods have adopted a complete relaxation strategy involving the removal of the discrete constraint on the hash code. However, this approach will produce accumulated quantization errors that seriously affect the accuracy of hash retrieval. To solve this problem, we adopt a semidiscrete, semirelaxed strategy in which the real value information in equation (2) is used to replace the hash matrix B in equation (3). In this manner, the rich semantic information in the real value can be fully exploited without destroying the discrete constraints on the hash code. is process can be formalized as follows: According to the bilinear model [5], high-order features obtained through the fusion of heterogeneous features can better characterize an original sample. Inspired by this idea, the proposed approach fuses data obtained from different modalities. It is worth noting that because different modal data exist in different feature spaces, there will be semantic gaps between them. erefore, a simple feature mapping must be learned prior to fusion to aid in the feature space transformation, that is, VPT T . Further, by combining this formulation with equation (4), this fine-grained feature can be embedded into hash learning as follows: where V and T are features of different modalities and P is the linear projection. is equation reinforces the learning of hash codes using the fine-grained features VPT T and improves the quality of the hash codes. At the same time, it can be applied in conjunction with the out-of-sample extension strategy to produce learned hash codes for different modal samples that preserve the pairwise similarity relations as much as possible, as will be introduced in detail in Section 3.4. In summary, by combining equations (1), (2), (4), and (5), the final objective function can be obtained as follows: where α, β, c, and λ are tradeoff parameters. (6) is evidently still a difficultto-solve nonconvex optimization problem for variables W, B, M, and P. However, solving for a single variable while fixing the other variables remains a relatively straightforward process. erefore, we propose an alternating iteration strategy for optimization with the goal of achieving global optimization through local optimization. Each optimization step is introduced as follows:

Optimization. Equation
Step 1: first, the optimization process of the mapping M is introduced. By fixing the remaining three variables, equation (6) can be simplified to By taking the derivative of equation (7) with respect to M and setting it equal to zero, we obtain By solving the above equation, the closed-form (analytical) solution of M can be obtained as follows: Step 2: fix the three variables M, B, and P, and optimize the mapping W. In this case, the objective function can be simplified to

Computational Intelligence and Neuroscience
By taking the derivative of equation (10) with respect to W and setting it equal to zero, we obtain e closed-form solution of W is Step 3: optimize variable B. By fixing the remaining variables, we obtain As B contains binary constraints, equation (13) is still an integer optimization problem. Here, we introduce two approaches to optimizing B. e first optimization scheme uses discrete proximal linearized minimization (DPLM) [22]. After reconstruction and simplification, B can be solved through a simple symbolic function: where B j is the solution of B after the j th iteration, μ is a hyperparameter, and ▽L(B) is expressed as follows: e second optimization scheme for B adopts the discrete cyclic coordinate descent (DCC) approach [20]. Although equation (13) is an integer optimization problem, the DCC algorithm can still be employed to solve its discrete solution iteratively and bit by bit. As ‖B‖ 2 � L * N, equation (13) can be rewritten as where Q � YM T + αYW T + βSYW T + cVPT T YW T . According to the DCC algorithm, we define b as the l-th column of matrix B, l � 1, . . . , L, and B ′ as matrix B excluding b. Analogously, we define q as the l-th column of matrix Q. We then define m as the l-th column of matrix M and M ′ as matrix M excluding m. Finally, we define H � WY T , h as the l-th column of matrix H, and H ′ as matrix H excluding h. Equation (16) can then be rewritten as By taking the derivative, the analytical solution of b can be obtained as follows: where sgn(·) represents the symbolic function.
Step 4: fix the remaining variables and optimize mapping P. In this case, the objective function is By taking the derivative and setting it equal to zero, we obtain e closed-form solution of P is

Out-of-Sample Extension.
In this section, we introduce the out-of-sample extension strategy. As shown in equation (6), DTCH is a two-step hashing method. After the offline training is completed, a mapping from features to hash codes Computational Intelligence and Neuroscience 5 must also be learned to query the samples. As mentioned above, we propose a new out-of-sample extension strategy that, when combined with the objective function, can help ensure that the learned modality-specific out-of-sample mappings P V and P T preserve the similarity in the original space. Specifically, this strategy can be formalized as follows: where the solution of the out-of-sample extension mapping for the visual modality can be expressed as By taking the derivative with respect to P V , we obtain e solution of the out-of-sample extension mapping for the text modality can be expressed as By taking the derivative with respect to P T , we obtain

Time Complexity.
In the training process, we need to update the projection M, W, P, P V , and P T and the unified binary code matrix B. e time complexity for learning M, W, and P, P V , and P T are O(2f 2 N + 2d 2 N + LdN + LfN), respectively. In this study, we adopt two approaches to optimize B. Specifically, solving equations (15) and (18) requires O(NL 2 + LdN + LfN) and O(LdCN 2 + LfCN 2 ), respectively. As N is usually much larger than C and L, the training time complexity of the proposed method with DCC and DPLM can be simplified as where T is the number of iterations.

Experiments
To verify the effectiveness of the proposed method, we conducted extensive experiments using two widely used datasets. In the following section, the three aspects of each dataset (their modalities and class information) experimental settings, and experimental analyses and results are introduced in detail.

Dataset.
To verify the effectiveness and superiority of the proposed method, we conducted extensive experiments using two widely used large-scale cross-modal retrieval datasets: MIR-Flickr [23] and NUS-WIDE [24].
e MIR-Flickr dataset contains 25,000 images in 24 classes, with each image forming an image-text pair with a corresponding text description. In this study, 15,902 sample pairs were selected as the training set, 836 sample pairs were selected as the test set, and the union of these sets was used as the retrieval set. Specifically, the image modality was represented by a 150-dimensional edge histogram, the text modality was represented by a 500-dimensional word vector, and the class information was represented by a 24-dimensional semantic label. e NUS-WIDE dataset contains 269,648 images and corresponding text descriptions from the Internet and includes 81 classes. In this study, the 10 most frequent classes and their 17,000 corresponding samples were selected for training, 994 samples were selected for testing, and 50,000 samples were selected for retrieval. Specifically, the image modality was represented by a 500-dimensional SIFT bag-of visual words vector [25], the text modality was represented by a 1,000-dimensional bag-of-words vector, and the class information was represented by a 10-dimensional semantic label.
For a fair comparison, the hyperparameters of all baseline methods were initialized according to the approaches used in the original papers; for all methods, including DTCH, the average performance over five runs was used for comparison. e following parameter settings were used for the method proposed in this paper: α � 2, β � 10 − 7 , c � 10 − 7 , λ � 10 − 4 , μ � 0.05, and σ � 10 − 7 . As the proposed method is based on a linear model, a deep model was not used as its baseline method. Moreover, all examinations are led on a computer with an Intel Core i7-6700 3.40 GHz 4 processor and 32 GB RAM under the programming climate of MATLAB R2019b.
To compare the performance of the methods, we tested each on two cross-modal retrieval tasks: (1) Img2Text, involving the retrieval of texts using images; and (2) Text2Img, involving the retrieval of images using texts. e average precision (AP) and mean average precision (mAP) were used as metrics. AP represents the average precision of tobe-retrieved samples as follows: where D is the number of correlated samples among K retrieved samples and σ(r) indicates whether the r th example is correlated with a retrieved sample. mAP was obtained by sorting the AP values of the samples and then taking the average as follows: where Z represents the number of samples to be retrieved.

Experimental Results and Analyses.
In this section, we provide a brief analysis of the experimental results.   DCC and DPLM, respectively, for solution optimization. It is seen from Table 1 that Ours-2 achieved the best performance under various code lengths on both datasets, indicating that the proposed method was able to reduce the semantic gap to a certain extent and improve the cross-modal retrieval performance. Ours-1 also obtained convincing results; in performing the Text2Img task in particular, its performance was significantly improved relative to the previous methods. On the NUS-WIDE dataset, however, the performance of Ours-1 was slightly worse than that of SCARTCH, particularly at relatively short code lengths. One possible reason for this result is that Ours-1 was trapped in local optima while using DCC optimization. In addition, its insufficient performance on the Img2Text task alone indicates that its characterization ability on the image modality is slightly lacking. us, in subsequent work it will be useful to enhance the image modal expression ability of the proposed method. Figure 2 shows a line chart plotting the average Preci-sion@K indicator as a function of code length for each method in performing each task. Without loss of generality, the value of K was selected to be 50. It is seen from the results that Ours-1 and Ours-2 achieved optimal performance at nearly all code lengths. Furthermore, DTCH was able to achieve convincing results even when the code length was relatively short. Figure 3 shows a line chart plotting the average Precision@K indicator as a function of K for each method in performing each task. In this case, the code length was fixed at 32. It is seen that the proposed method outperformed all of the comparison methods, particularly at relatively small K values, and achieved significantly higher average precision values than the other methods.

Conclusion
In this paper, we proposed a supervised cross-modal hashing method called DTCH. is method simultaneously embeds a label matrix and a pairwise similarity matrix into hash learning and fully exploits the pairwise relations between samples for each label using the dual supervision approach. Specifically, to exploit the sample label matrix, the proposed method combines matrix factorization and label regression. e bidirectional mapping approach not only fully exploits the semantic information but also stabilizes the hash learning process. To exploit the pairwise similarity matrix, we adopt a semirelaxed, semidiscrete method to avoid the original nonconvex optimization problem; this also alleviates the significant cumulative quantization error that can arise from directly removing the binary constraint. We additionally designed a new out-of-sample extension strategy that is combined with the objective function's fused fine-grained features as a method for carrying out the objective function. In this manner, the consistency between the different modal distributions of samples and the pairwise similarity relations is effectively preserved. Extensive experiments carried out using two datasets verified the excellent performance and efficiency of DTCH. Furthermore, embedding deep learning in the DTCH framework as the nonlinear embedding technique slows original method. In  Computational Intelligence and Neuroscience future, we plan to investigate how to effectively and efficiently combine them.

Data Availability
e research data used to support the findings of this study are included within the article.

Conflicts of Interest
e authors declare that they have no conflicts of interest.