Critical node identification is essential for Underwater Acoustic Sensor Networks (UASNs) to ensure network connectivity and reliability. Existing methods identify critical nodes by evaluating their contributions to network connectivity and node communication count. However, these methods identify critical nodes inaccurately due to neglecting the influence of packet collisions, leading to unreliable network. Packet collisions disrupt connected links and cause communication failures, resulting in unreliable network connectivity and improper communication count. To this end, we propose the Collision-Aware Critical Node Identification Algorithm (CCNIA), which accounts for the impact of packet collisions to improve the accuracy of critical node identification and enhance network reliability. CCNIA identifies critical nodes with high connectivity, large collision probability, and heavy network load, through building the three following interdependent models. Specifically, Topological Connectivity Model (TCM) evaluates link reachability by analyzing connectivity and density within a node's local network. Based on TCM, Collision Probability Model (CPM) further ensures packet reliability by quantifying the impact of packet collisions on critical node identification. Through CPM's reliable packet transmissions, Network Load Model (NLM) assesses network efficiency by analyzing node occurrence count within global end-to-end communication paths. Experiments show that CCNIA outperforms existing methods across diverse network configurations, enhancing network reliability in terms of packet delivery ratio, delay, and energy efficiency.

Increasing demands for versatile applications have spurred the rapid development of Unmanned Underwater Vehicle (UUV) networks. Nevertheless, multi-UUV movements exacerbates the spatial-temporal variability, leading to serious intermittent connectivity of underwater acoustic channel. Such phenomena challenge the identification of reliable paths for high-dynamic network routing. Existing routing protocols overlook the effects of UUV movements on forwarding path, typically selecting forwarders based solely on the current network state, which lead to instability in packet transmission. To address these challenges, we propose a Routing protocol based on Spatial-Temporal Graph model with Q-learning for multi-UUV networks (STGR), achieving high reliable and energy effective transmission. Specifically, a distributed Spatial-Temporal Graph model (STG) is proposed to depict the evolving variation characteristics (neighbor relationships, link quality, and connectivity duration) among underwater nodes over periodic intervals. Then we design a Q-learning-based forwarder selection algorithm integrated with STG to calculate reward function, ensuring adaptability to the ever-changing conditions. We have performed extensive simulations of STGR on the Aqua-Sim-tg platform and compared with the state-of-the-art routing protocols in terms of Packet Delivery Rate (PDR), latency, energy consumption and energy balance with different network settings. The results show that STGR yields 24.32 percent higher PDR on average than them in multi-UUV networks.