Many Internet of Things (IoT) devices are available on the market; the so-called Internet of Everything (IoE) is becoming a trend [1,2]^[1][2]. Thanks to the availability of low cost, high speed, and highly reliable 5G cellular networks, people can purchase IoT devices and utilize them as per their needs [3,4,5,6]^[3][4][5][6]. However, different types of IoT devices have different transmission frequencies and reporting rates. Various telecom operators provide various tariff plans for their IoT device services. In narrow band Internet of Things (NB-IoT), the uplink data are transmitted through a narrowband physical uplink shared channel (NPUSCH), with limited transmission resources. Using Release 15 as an example, in reality, the highest uplink transmission rate is less than 200 kbps [7^[7][8][9],8,9], and a large amount of flooded traffic at the same time will make NPUSCH very congested. Moreover, before a connection is established between user equipment (UE) and the evolved node-B or ’eNB’, a random-access procedure is required. After the random-access procedure is completed, all UE will need an appropriate uplink scheduling algorithm to transmit data to eNB with low latency in a power-saving mode (PSM). For this reason, wresearchers propose the persistent periodic uplink scheduling algorithm (PPUSA) to achieve energy-saving uplink scheduling.

With the use of the PPUSA algorithm, for UE, there can be a guarantee of uplink transmission periodically, without congestion in the uplink channel. The algorithm that is proposed in this paper will estimate the traffic demand of each type of UE to be uploaded to the base station based on the tariff flow and the data transmission characteristics of typical IoT devices. Generally speaking, the deployment of UE is carefully planned, so it will not transmit more than its subscribed traffic and will reserve a certain percentage of traffic for emergency use. The proposed PPUSA algorithm is designed to customize the upload schedule for the UE after taking into account the above considerations, which achieves power-saving and low-latency transmission and enables the entire NB-IoT system to cope with tens of thousands of uplink transmissions of IoT devices.

The novelty and contributions of this paper are summarized as follows. Firstly, this paper studies the e NB-IoT uplink scheduling for a massive number of IoT devices, which receives less attention in the literature. Secondly, this paper proposes a a novel uplink scheduling algorithm to solve the problem of transmitting messages with low latency in NB-IoT when there are many IoT devices, and each device demands that its sensing messages be transmitted in a periodic manner. In addition, each device may occasionally have emergency messages to send. Thirdly, the proposed novel scheduling mechanism guarantees that the device wakes up to transmit immediately in order to minimize transmission delay and power consumption. Finally, the proposed scheduling algorithm can support up to 600,000 IoT devices when the NB-IoT uplink utilization is 80%. In addition, it takes only one millisecond for the transmission of the emergency messages.

2. Background and Related Works

2.1. About NB-IoT

NB-IoT was proposed by 3GPP to support a wide range of cellular devices and services. NB-IoT standard is one of the mainstream low power wide area network (LPWAN) technologies. The primary focus of NB-IoT involves its indoor coverage, long battery life, low cost, low power consumption, high connection density, and high throughput characteristics. NB-IoT has the unique feature to co-exist with 2G GSM systems, as well as with 4G LTE systems. Three operation modes, namely the in-band operation mode, guard-band operation mode, and stand-alone operation mode, respectively, are present in NB-IoT systems. Similar to LTE, NB-IoT adopts orthogonal frequency division multiple access (OFDMA) technology for downlink transmission with 15 kHz sub-carrier spacing. In uplink transmission, NB-IoT utilizes single-carrier frequency division multiple access (SC-FDMA) technology with 15 and 3.75 kHz spacing to support single-tone (sub-carrier) and multi-tone transmissions, respectively ^[10]. Table 1 depicts the technical parameters for the NB-IoT standard ^[11].

2.2. Uplink Scheduling for NB-IoT

When the base station wants to schedule an uplink transmission of the user equipment (UE), the base station sends a downlink control information (DCI) to one of the NPDCCH search spaces monitored by the UE. In order to distinguish the UE, the system assigns different radio network temporary identifiers (RNTI) to different UE, and the base station uses these RNTIs to encode the CRC bits of the DCI. Therefore, only the UE that knows the corresponding RNTI can successfully decode, and after decoding, the relevant information about the uplink schedule can become available. There are many types of DCI, among which, the DCI-format-N0 is used for uplink scheduling [16,17]^[16][17]. For uplink data transmission, the UE needs a time gap of at least 8 milliseconds to switch from receiving the DCI mode to the transmission mode. This time gap, also called scheduling delay, is designed for the UE to decode DCI. After the UE completes the NPUSCH uplink transmission, a time gap of at least 3 milliseconds is required to allow the UE to switch from the transmission mode to the receiving DCI mode to receive the ACK/NACK, and monitor the next NPDCCH search space, as shown in Figure 5.

2.3. Literature Review of Uplink Scheduling

The NB-IoT system supports single-tone (3.75 kHz) transmission and multi-tone (15 kHz) transmission for uplink scheduling. NB-IoT can be deployed in-band, utilizing resource blocks within a regular LTE carrier, in the unused resource blocks within an LTE carrier’s guard-band, or standalone for deployments in a dedicated spectrum. However, wresearchers cannot directly apply the LTE uplink scheduling mechanism to NB-IoT because the LTE’s semi-persistent scheduling (SPS) ^[18] is dedicated to periodic data transmissions, such as voice over IP (VoIP) services. Therefore, the existing LTE SPS configuration is only for a single UE. Moreover, in ^[19], the authors propose a group-based uplink scheduling algorithm, where they group the devices first and then select a group leader in each group. Next, the base station determines which group transmits first according to the environment of each group leader. However, this approach only schedules a single device. In ^[20], the authors design a scheduler to arrange wireless resources for NB-IoT resource allocation. However, the scheduler is designed to comply with 3GPP Release 13 and cannot support single-tone and multi-tone transmissions. The work ^[21] proposes an adjustable uplink resource scheduling scheme, but the scheme only addresses scheduling for emergency needs and does not meet the NB-IoT specifications. In ^[22], the authors analyzed a single UE based on the queuing theory and used the analysis results to optimize the parameter configuration (such as retransmission times, scheduling delay) in NPRACH and NPDCCH. However, the work does not analyze NPUSCH. Other works in the literature can be divided into two categories: uplink scheduling for single-tone transmission [15,16,23]^[15][16][23] and uplink scheduling for multi-tone transmission [14,17,24]^[14][17][24]. This paper focuses on the second category. The main goal of this work is to schedule uplink transmission for as many UE as possible while maintaining a low transmission delay for emergency messages and high energy savings. To achieve this goal, weresearchers divide messages into periodic and emergency (referred to as “bursty” hereafter), and NB-IoT UE into three types, according to the time cycle of their periodic message reporting. Moreover, wethey also consider power saving mechanisms (PSM) and UE at the CE-level. In the literature, studies only schedule massive numbers of UE of the same type and do not consider the two crucial power saving mechanisms, namely PSM and eDRX, respectively. Table 2 displays the comparison of related works. In NB-IoT, the following channels and signals are used in uplink transmission ^[12]:

• Narrowband physical random access channel (NPRACH).
• Narrowband physical uplink shared channel (NPUSCH).
• Demodulation reference signal (DMRS).

Similarly, in NB-IoT, the following channels and signals are used in downlink transmissions ^[12]:

• Narrowband physical downlink shared channel (NPDSCH).
• Narrowband physical downlink control channel (NPDCCH).
• Narrowband reference signal (NRS).
• Narrowband primary synchronization signal (NPSS).
• Narrowband secondary synchronization signal (NSSS).
• Narrowband physical broadcast channel (NPBCH).

2.1.1. Frame Structure for NB-IoT

The frame structure of NB-IoT is depicted in Figure 1 and Figure 2. The highest level starts with a hyperframe cycle, where one hyperframe cycle consists of 1024 hyperframes and each hyperframe has 1024 frames [12,13]^[12][13]. One frame is composed of ten subframes, and each subframe is divided into two slots each of 0.5 ms, which is similar to traditional LTE systems. In the downlink and uplink transmission, NB-IoT supports a sub-carrier spacing of 15 kHz, for which each frame consists of twenty slots. For the uplink, NB-IoT supports an additional sub-carrier spacing of 3.75 kHz. To accommodate this sub-carrier spacing, each frame is directly divided into five slots, each of two milliseconds [12,13]^[12][13].

2.1.2. About Coverage Enhancement Level—CE Level

The 3GPP classifies coverage levels into three types, namely, CE Level 0, CE Level 1, and CE Level 2, respectively. There are certain differences in user equipment access and transmission mechanisms under these three coverage levels. The base station (BS) will divide the coverage into three levels based on the defined reference signal received power (RSRP) thresholds. Then the coverage is carried through the system information block-narrow band (SIB-NB). SIB-NB carries radio-resource control information to inform the user devices about the configuration of the NB-IoT physical random access channel (NPRACH) that contains three CE levels. The user’s device will find out which CE level it belongs to based on the measured RSRP and use the corresponding NPRACH configuration to carry out the random access procedure ^[14]. The coverage target of NB-IoT is ’maximum coupling loss’ (MCL) 164 dB. The coverage improvement is mainly achieved through repetition to ensure reliable connectivity in remote areas, basements, and other places with poor signal quality ^[10].

2.1.3. Power Saving Mechanism of NB-IoT

One of the main features of the 3GPP Release 14 of the NB-IoT is its long-term power-saving mode. Two different power saving mechanisms are defined for NB-IoT: (i) power saving mode (PSM) and (ii) extended discontinuous reception (eDRX). PSM was introduced in the 3GPP Release 12 ^[15]. Figure 3 shows the operating procedure of the PSM mode. Similarly, Figure 4 shows the operating procedure of the eDRX mode for the NB-IoT devices.

2.4. Some Advances in NB-IoT

In NB-IoT, the maximum level of power consumption happens during the active time; that is, during Tx and Rx. In Release 16, it is expected that the UE will transmit when radio resource control (RRC) is in an ideal mode through Msg3 (RRC connection request) without the use of access grant. It is possible for a UE in an RRC connection mode to transmit data without a grant or using the simplified ’control-less’ grant. Yet another development is made in reducing the signaling overhead in NB-IoT without compromising the quality of service. The aforementioned features reduce both power consumption and latency. Release 16 also proposed further studying the original signal waveforms, such as FDMA, which require less orthogonality with more relaxed timing advance (TA) when compared to single-carrier frequency-division multiple access (SC-FDMA) ^[12]. In ^[25], based on the concept of grant-free communications, the authors investigated the adaptive period of the industrial Internet of Things (IIoT), where only some of the devices were active at a given time slot. The authors proposed two new schemes, namely, periodic block orthogonal matching pursuit (PBOMP) and periodic block sparse Bayesian learning (PBSBL). Both schemes outperform the previous schemes in factors such as the success rate of user activity detection (UAD), bit error rate, and accuracy in period estimation and channel estimation ^[25].