Efficient clusterhead rotation via domatic partition in self-organizing sensor networks

摘要

Nodes in wireless sensor networks (WSN) are deployed in an unattended environment with non re-chargeable batteries. Thus, energy efficiency becomes a major design goals in WSNs. Clustering becomes an effective technique for optimization energy in various applications like data gathering. Although aggregation aware clustering addresses lifetime and scalability goals, but suffers from excessive energy overhead at cluster head nodes. Load balancing in existing clustering schemes often use rotation of cluster head roles among all nodes in order to prevent any single node from complete energy exhaustion. We considered important aspects of energy and time overhead in rotation of the cluster head roles in various node clustering algorithms with goals to further prolong the network lifetime by minimizing the energy overheads in rotation setup. The problem of cluster head rotation is abstracted as the graph theoretic problem of domatic partitioning, which is also NP-complete. The dense deployment and unattended nature rules out the possibility of manual or external control in existing domatic partition (DP) techniques to be used for WSNs. To our knowledge, no self-organizing technique exists for domatic partitioning. We developed a distributed self-organizing one-domatic partitioning scheme with approximation factor of at least 1/16 for unit-disk-graphs (UDGs). In this work, we demonstrate that the benefits of self-organization is achieved without sacrificing the quality of domatic partitioning. We demonstrated through simulations that our self-organizing DP without sacrificing on the size of DP achieves self-organization capability which is able to reduce time and energy overheads of cluster head rotation resulting to an improved network lifetime compared to the existing clustering protocols for sensor networks.