A Jaccard Factor-Based Heuristic for the Set k-Cover Problem in Wireless Sensor Networks

The applications of a wireless sensor network rely heavily on the network’s ability to function for an extended period. By separating the sensors into groups, each of which may keep an eye on the entire area of interest and be activated alternately, the system’s lifetime can be maximized. However, determining the most significant number of different sensor covers necessitates solving the NP-complete set k-cover issue. This work presents an improved greedy approach to the set k-cover problem based on the Jaccard Similarity Coefficient. The latter is a statistical method used to understand the similarity and diversity between sample sets. Moreover, the quality of the produced solution is improved by removing duplicate sensors for each set cover. The effectiveness of the proposed approach was compared to some greedy-based methods from the literature based on 1000 widely used benchmark instances. Computational results demonstrate its efficacy in producing high-quality solutions within acceptable computational time, especially when the problem scale increases