IEEEEnergy consumption is a critical issue in the design of wireless underwater sensor networks (WUSNs). Data transfer in the harsh underwater channel requires higher transmission powers compared to an equivalent terrestrial-based network to achieve the same range. However, battery-operated underwater sensor nodes are energy-constrained and require that they transmit with low power to conserve power. Clustering is a technique for partitioning wireless networks into groups where a local base station (cluster head) is only one hop away. Due to the proximity to the cluster head, sensor nodes can lower their transmitting power, thereby improving the network energy efficiency. This paper describes the implementation of a new clustering algorithm to prolong the lifetime of WUSNs. We propose a new protocol called distance- and energy-constrained k-means clustering scheme (DEKCS) for cluster head selection. A potential cluster head is selected based on its position in the cluster and based on its residual battery level. We dynamically update the residual energy thresholds set for potential cluster heads to ensure that the network fully runs out of energy before it becomes disconnected. Also, we leverage the elbow method to dynamically select the optimal number of clusters according to the network size, thereby making the network scalable. Our evaluations show that the proposed scheme outperforms the conventional low-energy adaptive clustering hierarchy (LEACH) protocol by over 90% and an optimised version of LEACH based on k-means clustering by 42%.