Multi-Channel Subset Iteration with Minimal Loss in Available Capacity (MC-SIMLAC) Algorithm for Joint Forecasting-Scheduling in the Internet of Things

Abstract

The Massive Access Problem of the Internet of Things (IoT) refers to the problem of scheduling the uplink transmissions of a massive number of IoT devices in the coverage area of an IoT gateway. Joint Forecasting-Scheduling (JFS) is a recently developed methodology in which an IoT gateway forms predictions of the future uplink traffic generation pattern of each IoT device in its coverage area via machine learning algorithms and uses these predictions to schedule the uplink traffic of all of the IoT devices in advance. In this paper we develop a novel algorithm which we call “Multi-Channel Subset Iteration with Minimal Loss in Available Capacity” (MC-SIMLAC) for multi-channel joint forecasting-scheduling. Our multi-channel scheduling algorithm iterates over subsets of all of the bursts of IoT device traffic and selects channel-slot pairs by targeting the minimization of loss in total available capacity. In this regard our algorithm contrasts sharply with Multi-Channel Look Ahead Priority based on Average Load (MC-LAPAL) which is the best-performing heuristic that has been developed so far for multi-channel JFS. In the general case our algorithm outperforms MC-LAPAL especially when wireless links operate in the power-limited regime and the number of devices is large. For the special case of identical channels our algorithm achieves a performance that is closer than MC-LAPAL to that of the optimal scheduler. Furthermore we prove that the time complexity and the space complexity of MC-SIMLAC in the worst case are polynomial in each of the system parameters which indicates practical feasibility. These results pave the way to the widespread use of multi-channel joint forecasting-scheduling at IoT gateways in the near future. © 2022 Elsevier B.V. All rights reserved.