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

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.