A Survey of Approximation Algorithms for the Power Cover Problem

Wireless sensor networks (WSNs) have attracted significant attention due to their widespread applications in various fields such as environmental monitoring, agriculture, intelligent transportation, and healthcare. In these networks, the power cost of a sensor node is closely related to the radius of its coverage area, following a nonlinear relationship where power increases as the coverage radius grows according to an attenuation factor. This means that increasing the coverage radius of a sensor leads to a corresponding increase in its power cost. Consequently, minimizing the total power cost of the network while all clients are served has become a crucial research topic. The power cover problem focuses on adjusting the power levels of sensors to serve all clients while minimizing the total power cost. This survey focuses on the power cover problem and its related variants in WSNs. Specifically, it introduces nonlinear integer programming formulations for the power cover problem and its related variants, all within the specified sensor setting. It also provides a comprehensive overview of the power cover problem and its variants under both specified and unspecified sensor settings, summarizes existing results and approximation algorithms, and outlines potential directions for future research.