Title: Efficient connectivity analysis in underwater wireless sensor networks: a polynomial-time solution for the connectivity between nodes

Authors: Youssef N. Altherwy

Addresses: Department of Information Systems, College of Computer Engineering and Science, Prince Sattam bin Abdulaziz University, Alkharj, 11942, Saudi Arabia

Abstract: Underwater wireless sensor networks (UWSNs) are a focus of research due to challenges in the unpredictable underwater environment. This study delves into connectivity among sensor nodes, particularly the likelihood of communication between nodes adrift with water currents, termed the two nodes connectivity (2Nodes connectivity) problem. Highlighting the computational complexity (2Nodes connectivity is #P-hard), we propose an innovative polynomial-time approximation algorithm, namely the 2Nodes connectivity algorithm. The algorithm yields precise connectivity outcomes for graphs composed of node-disjoint paths and serves as a lower bound solution for graphs where node-disjoint paths can be extracted. Through simulations in realistic UWSN scenarios, our algorithm demonstrates remarkable efficiency, making it an optimal choice for time-sensitive UWSN applications. Our research contributes both theoretical understanding and a practical algorithmic solution, addressing critical communication challenges in UWSNs.

Keywords: underwater wireless sensor network; UWSN; connectivity; approximation algorithm; node-disjoint paths.

DOI: 10.1504/IJSNET.2024.142711

International Journal of Sensor Networks, 2024 Vol.46 No.4, pp.205 - 217

Received: 29 Nov 2023
Accepted: 01 May 2024
Published online: 18 Nov 2024 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article