Gradual cluster head election for high network connectivity in large-scale sensor networks

The large-scale deployment of high density wireless sensor networks (WSNs) necessitates efficient organization of the networks for high network connectivity and low orphan node ratio. The multi-hop clustering technique has proven to be an efficient one for self-organizing thousands of randomly deployed sensors in a huge area. In this paper, we propose new clustering algorithms with a set of parameters for clustering nodes in static ad hoc sensor networks. First, we present a gradual cluster head election algorithm (GCA) that gradually elects cluster heads according to the proximity to neighbor nodes and the residual energy level (E_r) at each clustering phase. In addition, we propose a gradual cluster head election algorithm with one-hop neighbor information (GCA-ON), which elects cluster heads based on E_r and the relative location information of sensor nodes such as the number of cluster heads in one-hop neighbor (N_CH-ON). Ideal distributions or capabilities of the sensor nodes are not assumed in the proposed algorithms. We evaluate the performance of the proposed algorithms in large-scale high density WSN environments. In view of network connectivity, our algorithms outperform the typical existing cluster head election algorithms.