An energy-efficient K-hop clustering framework for wireless sensor networks

Many applications in wireless sensor networks (WSNs) benefit significantly from organizing nodes into groups, called clusters, because data aggregation and data filtering applied in each cluster can greatly help to reduce traffic. The size of a cluster is measured by the hop distance from the farthest node to the cluster head. Rather than 1-hop clustering, K-hop clustering is preferred by many energy-constrained applications. However, existing solutions fail to distribute clusters evenly across the sensing field, which may lead to unbalanced energy consumption and network inefficiency. Moreover, they incur high communication overhead. We propose an Evenly Distributed Clustering (EDC) algorithm. Constrained by the maximum cluster size K, EDC distributes clusters uniformly, and minimizes the number of clusters. By introducing a relative synchronization technique, EDC converges fast with low communication overhead. It also helps to improve the successful transmission rate from nodes to their cluster heads. The simulation results indicate that EDC outperforms other existing algorithms. © Springer-Verlag Berlin Heidelberg 2007.