A Tabu Search Algorithm for Cluster Building in Wireless Sensor Networks |
| |
Authors: | El Rhazi Abdelmorhit Pierre Samuel |
| |
Affiliation: | Ecole Polytechnique de Montréal, Montréal; |
| |
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 modeled 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. |
| |
Keywords: | |
|
|