Iterative Tabu Search Algorithm For The Minimum Connected Dominating Set Problem

In the wireless sensor network, due to the lack of a network infrastructure, the sensor nodes communicate with each other in the form of broadcast, which can easily cause broadcast storms and other issues. In order to improve the utilization of network bandwidth and save energy consumption, a connected dominating set has always been established in the wireless sensor network as a virtual backbone network. However, finding the Minimum Connected Dominating Set(MCDS) as a global optimization problem has been proved to be an NP-hard problem, so an ever increasing number of scholars have carried out extensive and in-depth research in MCDS problem.In this paper, we proposes a heuristic algorithm called RSN-TS which combines set partitioning and tabu search for solving the MCDS problem in static wireless sensor networks. With the idea of set partitioning, we put the sensor nodes in different sets. Through exchanging nodes between different sets with fast incremental evaluation technology, RSN-TS algorithm can obtain an approximate minimum connected dominating set or solve the MCDS problem completely.By testing on international public data sets and comparing with the exact algorithm, heuristic algorithm proposed by other scholars, we found out that the RSN-TS algorithm is efficient for solving the minimum connected dominating set problem. In addition, the paper also analyzes some critical components such as fast incremental evaluation technology, perturbation mechanism and tabu search procedure, which influence the performance of RSN-TS algorithm.