Premium
Graph‐based optimal asynchronous scheduling in large propagation delay underwater acoustic sensor networks
Author(s) -
M. Mridula K.,
Ameer P. M.
Publication year - 2020
Publication title -
international journal of communication systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.344
H-Index - 49
eISSN - 1099-1131
pISSN - 1074-5351
DOI - 10.1002/dac.4412
Subject(s) - computer science , asynchronous communication , scheduling (production processes) , job shop scheduling , dynamic priority scheduling , distributed computing , fair share scheduling , mathematical optimization , round robin scheduling , travelling salesman problem , schedule , algorithm , computer network , mathematics , operating system
Summary Optimal scheduling is essential to minimize the time wastage and maximize throughput in high propagation delay networks such as in underwater and satellite communication. Understanding the drawbacks of synchronous scheduling, this paper addresses an asynchronous optimal scheduling problem to minimize the time wastage during the transmission. The proposed scheduling problem is analyzed in both broadcast and non‐broadcast networks, which is highly applicable in high propagation delay networks. In broadcast networks, the proposed scheduling method reduces to a graph‐theoretic model that is shown to be equivalent to the classic algorithmic asymmetric traveling salesman problem (TSP) which is NP‐Hard. Although it is NP‐Hard, the TSP is well‐investigated with many available methods to find the best solution for up to tens of thousands of nodes. In non‐broadcast networks, the optimal solution to the scheduling problem considers the possibility of parallel transmission, which is optimized using graph coloring algorithm. The groups obtained through graph coloring are solved using Asymmetric Traveling Salesman algorithm to obtain the optimal schedule. The proposed method efficiently solves the scheduling problem for networks of practical size.