A Balanced Parallel Clustering Protocol for Wireless Sensor Networks Using K-Means Techniques

For wireless sensor networks (WSNs), it is a challenging task how to schedule the energy resource to extend the network lifetime due to the fact that WSNs are usually powered by limited and non-rechargeable battery. A clustering scheme is helpful in reducing the energy consumption by aggregating data at intermediate sensor nodes. In this paper, we propose a balanced parallel k-means based clustering protocol; we term it BPK-means protocol. In this new protocol, we use k-means algorithm to cluster the sensor nodes, the cluster-heads are then selected in terms of two factors, they are a) the distance from node to cluster-center, and b) the residual energy. BPK-means only requires local communications: each tentative cluster-head only communicates with their topologically neighboring nodes and other tentative cluster-heads when achieving a distributed clustering scheme. The algorithm thus has the attractive feature of parallel computations. Moreover, BPK-means further balances the clusters to improve intra-cluster communication consumptions. We present the algorithm of this new protocol, analyze its computing properties, and validate the algorithm by simulations. Both theoretical analyses and simulation results demonstrate that BPK-means can achieve better load-balance and less energy consumptions when compared with LEACH. In addition, the BPK-means protocol is able to distribute energy dissipation evenly among the sensor nodes, which then prolong the system lifetime for the networks significantly.