A Clustering Scheme for Wireless Sensor Networks Based on Genetic Algorithm and Dominating Set

Abstract

The basic K-center problem is a fundamental facility location problem. Given n vertices with some distances, one wants to build k facilities in different vertices, so as to minimize the maximum distance from a vertex to its corresponding facility. This problem is known as the NP-hard problem, and grouping sensor nodes into a cluster is an important mechanism in large multi-hop wireless sensor networks for obtaining scalability, reducing energy consumption, and achieving better network performance. This study proposed a new method for solving the K-center problem based on the Genetic algorithm and dominating (GADO) set, and it is called the GADO method for wireless sensor network. An evaluation of the proposed GADO shows a decrease in the number of the centers compared to the well-known Farthest-first traversal method and dominating set only-based methods. Not only is the total distance from the centers to the sink node less than the other two algorithms, but the proposed GADO also diminishes the data delay and increases the lifetime of the centers.