Wireless link scheduling via parallel genetic algorithm. (15th December 2021) - Saad, Mohamed; El‐Moursy, Ali; Alfawaz, Oruba; Alnajjar, Khawla; Abdallah, Saeed
Abstract: With the advent of fifth generation (5G) systems and the Internet‐of‐Things (IoT), the number of interconnected wireless devices is increasing significantly. Protocols that allow these deceives to interconnect peer‐to‐peer through wireless links are becoming of interest. The major challenge is the inevitable interference among the simultaneously activated wireless links. Given a set of wireless links, this article addresses the non‐deterministic polynomial‐time (NP) hard problem of selecting the maximum subset of links that can be simultaneously activated at their respective signal‐to‐interference‐plus‐noise‐ratio (SINR) targets. The contribution of this article is two‐fold. First, we introduce a new genetic algorithm (GA) constraint‐handling mechanism, and prove analytically that finding optimal link schedules is guaranteed. Second, we develop a novel parallelized GA to solve the problem. Through serial algorithm analysis, we utilize data decomposition as well as exploratory decomposition in order to achieve significant running time speedup, which scales well with problem size. Our numerical results for openMP parallelization illustrate 6.5 × and 5.4 × reduction in computation time as compared to the serial versions of the GA and hybrid genetic algorithm (HGA), respectively. Moreover, the parallelization of the GA and HGA result in a speedup of 10.4 × and 5.4 ×, respectively, using master‐slave multithreading.