A new hybrid algorithm integrating genetic algorithm with Tabu search to solve imbalanced k-coverage problem in directional sensor networks

The target coverage problem is considered as one of the major issues in directional sensor networks (DSNs), which is caused by the nature of these networks, including their limited angle of view. Due to the fault tolerance characteristic of some coverage applications, the target coverage is required to be performed using multiple sensors. This challenge is discussed in the literature under the title of k-coverage problem. Under certain conditions, the number of sensors may suffer some changes due to various factors such as power depletion of the sensors, sensors' malfunctioning, and harshness of the environment. This can result in unavailability of adequate sensors for providing k-coverage for all targets. The network suffering from such problem is referred to as under-provisioned network. This paper was aimed at studying such networks by adopting the network conditions to the real environments. To solve this problem, the present paper proposes a hybrid model integrating the genetic algorithm (GA) and Tabu search (TS). The proposed algorithm generally aimed to identify a subset of sensors with appropriate working directions in order to provide a balanced coverage for all the targets available in the network. In order to evaluate the performance of the algorithm several experiments were conducted and the results have been compared with greedy and learning automat-abased algorithms. . The results of the experiments show the superiority of the algorithm.

Automated summary

The target coverage problem in directional sensor networks is a major challenge due to their limited angle of view. Multiple sensors are required for coverage, but changes in sensor availability due to various factors can result in an under-provisioned network. This paper proposes a hybrid model that integrates a genetic algorithm (GA) and Tabu search (TS) to identify a subset of sensors with appropriate working directions for balanced coverage. Experimental results demonstrate the superiority of the algorithm compared to greedy and learning automat-based algorithms.