Underwater wireless sensor networks (UWSNs) enable various oceanic applications which require effective packet transmission. In this case, sparse node distribution, imbalance in terms of overall energy consumption between the different sensor nodes, dynamic network topology, and inappropriate selection of relay nodes cause void holes. Addressing this problem, we present a relay-based void hole prevention and repair (ReVOHPR) protocol by multiple autonomous underwater vehicles (AUVs) for UWSN. ReVOHPR is a global solution that implements different phases of operations that act mutually in order to efficiently reduce and identify void holes and trap relay nodes to avoid it. ReVOHPR adopts the following operations as ocean depth (levels)-based equal cluster formation, dynamic sleep scheduling, virtual graph-based routing, and relay-assisted void hole repair. For energy-efficient cluster forming, entropy-based eligibility ranking (E2R) is presented, which elects stable cluster heads (CHs). Then, dynamic sleep scheduling is implemented by the dynamic kernel Kalman filter (DK2F) algorithm in which sleep and active modes are based on the node’s current status. Intercluster routing is performed by maximum matching nodes that are selected by dual criteria, and also the data are transmitted to AUV. Finally, void holes are detected and repaired by the bicriteria mayfly optimization (BiCMO) algorithm. The BiCMO focuses on reducing the number of holes and data packet loss and maximizes the quality of service (QoS) and energy efficiency of the network. This protocol is timely dealing with node failures in packet transmission via multihop routing. Simulation is implemented by the NS3 (AquaSim module) simulator that evaluates the performance in the network according to the following metrics: average energy consumption, delay, packet delivery rate, and throughput. The simulation results of the proposed REVOHPR protocol comparing to the previous protocols allowed to conclude that the REVOHPR has considerable advantages. Due to the development of a new protocol with a set of phases for data transmission, energy consumption minimization, and void hole avoidance and mitigation in UWSN, the number of active nodes rate increases with the improvement in overall QoS.