Design and stochastic modeling of distributed, dynamic, randomized clustering protocols in wireless sensor networks

In this paper, we propose a novel single hop-clustering scheme called step wise adaptive clustering hierarchy (SWATCH). SWATCH relieves the CH number variability problem by employing stepwise CH selection in two stages. It is a dynamic and straightforward scheme as LEACH. However, instead of selecting all CHs in one step, SWATCH splits the selection phase into an initial selection stage and an add-on selection stage. The initial selection is similar to LEACH. However, if the number of CHs in the initial selection is below a pre-determined target, the add-on selection will be invoked and will continue until an acceptable number of CHs have been selected. As a result, the number of CHs selected in each round tends to congregate in a narrow range around the optimal value. In order to evaluate the performance of SWATCH, we develop a hierarchical Markov chain model to track the behavior of the system. Numerical results verify our design objective in that the number of selected CHs highly conforms to the optimal value. Based on the results, an optimal number of CHs are greatly reduced the communication energy.