BPEC:An Energy-Aware Distributed Clustering Algorithm in WSNs

The large-scale deployment of wireless sensor networks and the need for data aggregation necessitate efficient organization of the network topology for the purpose of balancing the load and prolonging the network lifetime. Clustering has proved to be an effective approach for organizing the network into a connected hierarchy. In this paper, a distributed energy saving clustering algorithm BPEC is proposed. Cluster-heads are elected by two probabilities. The primary probability is based on the ratio between the average residual energy of neighbor nodes and the node itself residual energy. The subsidiary probability is the node’s degree. By using BPEC algorithm, the complexity of the entire network broadcasting is O(n), and the complexity of the entire network computing is O(1). It is proved that the cluster head set C by BPEC clustering algorithm is the dominating set of wireless sensor networks G(V,E). It is derived theoretically that the cluster head number of set C has a clear upper and lower bounds. The cluster head set generated by BPEC is proved to be a maximum independent set, which can cover all network nodes. Simulation experiments show that when the network has higher communication coverage density, analysis results and experimental results are very close, which shows that the cluster number of BPEC clustering algorithm is identical to the theoretical value.