Schedule Generation Using Knowledge Base for Contention-Free Medium Access in IoT Networks

Timely delivery of data in safety-critical as well as real-time Internet of Things (IoT) applications is important. Contention-based medium access control (MAC) protocol stacks make channel access delay non-deterministic. Since both contention-based and contention-free MAC protocols are currently in use in various standards, a solution that is agnostic to protocol stack is explored in this paper. Finding a minimum makespan conflict-free schedule can be reduced to graph coloring problem which is known to be NP-complete. This problem becomes challenging in IoT networks since the devices are resource limited. This paper presents a method for short makespan conflict-free schedule search that can be implemented on resource limited IoT nodes with no dependency on a solver package. Experimental results from simulation and a proof-of-concept testbed are presented.