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

Arif Kerem Dayı¹, Volkan Rodoplu², Mert Nakip³, Buse Pehlivan²⁺, and Cüneyt Güzeliş²

¹Harvard University, Massachusetts, USA
keremdayi@college.harvard.edu

²Department of Electrical and Electronics Engineering, Yaşar University, Izmir, Turkey
volkan.rodoplu@yasar.edu.tr, buse.phlv@gmail.com, cuneyt.guzelis@yasar.edu.tr

³Polish Academy of Sciences, Gliwice, Poland
mnakip@iitis.pl

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.

Keywords: Internet of Things (IoT), machine learning (ML), scheduling, Medium Access Control (MAC) protocol

+: Corresponding author: Buse Pehlivan
Department of Electrical and Electronics Engineering, Yas ̧ar University, 35100, Izmir, Turkey, Tel: +90 (232) 570 82

Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications (JoWUA)
Vol. 13, No. 2, pp. 68-95, June 2022 [pdf]

Received: November 17, 2021; Accepted: February 17, 2022; Published: June 30, 2022

DOI: 10.22667/JOWUA.2022.06.30.068