A k-Means-Based Formation Algorithm for the Delay-Aware Data Collection Network Structure

A wireless sensor network (WSN) consists of a large number of wireless sensor nodes that collect information from their sensing terrain. Wireless sensor nodes are, in general, battery-powered devices with limited processing and transmission power. Therefore, the lifetime of WSNs heavily depends on their energy efficiency. Multiple-cluster 2-hop (MC2H) network structure is commonly used in WSNs to reduce energy consumption due to long-range communications. However, networks with the MC2H network structure are commonly associated with long data collection processes. The delay-aware data collection network structure (DADCNS) is proposed to shorten the duration of data collection processes without sacrificing network lifetime. In this paper, a k-means-based formation algorithm for the DADCNS, namely DADCNS-RK, is proposed. The proposed algorithm can organize a network into the DADCNS, while minimizing the total communication distance among connected sensor nodes by performing k-means clustering recursively. Simulation results show that, when comparing with other DADCNSs formed by different algorithms, the proposed algorithm can reduce the total communication distances of networks significantly.