A TABU SEARCH ALGORITHM FOR CLUSTER BUILDING IN WIRELESS SENSOR NETWORKS

Abstract

The main challenge in wireless sensor network deployment pertains to optimizing energy consumption when collecting data from sensor nodes. This paper proposes a new centralized clustering method for a data collection mechanism in wireless sensor networks, which is based on network energy maps and Quality-of-Service (QoS) requirements. The clustering problem is modelled as a hypergraph partitioning and its resolution is based on a tabu search heuristic. Our approach defines moves using largest size cliques in a feasibility cluster graph. Compared to other methods (CPLEX-based method, distributed method, simulated annealing-based method), the results show that our tabu search-based approach returns high-quality solutions in terms of cluster cost and execution time. As a result, this approach is suitable for handling network extensibility in a satisfactory manner. The study specifies a new centralized clustering mechanism equipped with energy maps and constrained by Quality-of-Service (QoS) requirements. Such a clustering mechanism is used to collect data in sensor networks. The first original aspect of this investigation consists of adding these constraints to the clustering mechanism that helps the data collection algorithm in order to reduce energy consumption and provide applications with the information required without burdening them with unnecessary data.