The stochastic power multi-coverage problem

This paper studies the stochastic power multi-coverage problem: Given some users and base stations, as well as several possible scenarios and the probability of each scenario occurring, the users that need to be covered and the number of times of coverage for each user required in each scenario are known; different signal coverages are needed for the user sets in different scenarios; the power consumed by each base station in transmitting signal all satisfies the power equation, the objective of the stochastic power multi-coverage problem is to determine the type of transmitted signal and its coverage radius for each base station, to meet the coverage requirements for the users in all scenarios and minimize the total expected power consumption. This problem is a generalization of the minimum power coverage problem and has the characteristic of finite scenarios in two-stage stochastic optimization problems, closely related to classical optimization problems such as vertex cover and set cover. By using the "degree-weighted" function and the "layering" strategy from the vertex cover and the set cover problems, the weight of each disk in the problem instance are decomposed into a series of degree weights. The algorithm then proceeds by prioritizing the disks with smaller degree weights in each scenario, and this strategy is employed to design a polynomial-time approximation algorithm for solving the stochastic power multi-coverage problem.