A novel channel assignment method using Tabu Search based on graph theory in Wireless Sensor Networks

Wireless sensor networks are suffering from serious frequency interferences. In this paper, we propose a channel assignment algorithm based on graph theory in wireless sensor networks. The channel assignment problem is equivalent to the generalized graph-coloring problem; we first model the conflict graph for channel assignment with the goal of global optimization minimizing the total interferences to wireless sensor network. We further present a metaheuristic Wireless Sensor Networks Tabu Search (WSN-TS) algorithm to address the NP-completeness of the channel assignment problem. To judge the quality of the effect obtained from WSN-TS, we utilize the interference temperature as the termination criterion on the numbers of iteration needed for a solution in optimizing global network. Results from a simulation experiment reveal that the novel algorithm can effectively solve the channel assignment problem.