On the optimal randomized clustering in distributed sensor networks

Cluster-based data gathering is widely used in wireless sensor networks, primarily to overcome scalability issues. While clustering is not the most efficient means of gathering data, many clustering algorithms have attempted to provide energy efficiency as well. In this paper, we first demonstrate that the general problem of optimal clustering with arbitrary cluster-head selection is NP-hard. Next, we focus on randomized clustering in which sensor nodes form clusters in a distributed manner using a probabilistic cluster-head selection process. In order to find tractable and efficient solutions, we develop a mathematical framework that carefully captures the interplay between clustering and data correlation in the network. We further generalize this model to allow heterogeneous-sized clusters in different regions of the network. According to this model, we observe that clusters tend to become larger further from the sink. We also present simulation results to quantify the energy savings of joint clustering and compression. The results demonstrate that: (1) optimal selection of cluster sizes with respect to the correlation among sensor data has a significant impact on energy consumption of the network and (2) while non-uniform clustering slightly improves the energy efficiency of the network, simple uniform clustering is remarkably efficient and provides comparable results for energy savings.