A Synchronous Potential Game Optimization to the Sensor Coverage Problem of Distributed System

The sensor coverage problem is a typical combinatorial optimization problem, which is favored by researchers due to its wide practical applications. This article studies the sensor coverage problem, where each sensor has communication, sensing, and computing capabilities to collaboratively cover a certain area. First, we treat each sensor as a player, and establish a potential game for the sensor coverage problem, where the global objective is presented by the potential objective, and individual's utility is designed as a wonderful life utility. Second, we prove that under the established potential game, a Nash equilibrium can guarantee at least 50% optimality. Third, we design a synchronous game learning (SGL) distributed algorithm, where each player has a memory length$m$. Fourth, we prove that our designed SGL algorithm can guarantee that strategies of all sensors converge to a Nash equilibrium, and analyze its complexity. Finally, we demonstrate the effectiveness and superiority of our designed SGL algorithm by comparing with the existing representative optimization algorithms via numerical simulations. In addition, we also find that by employing our designed SGL algorithm, a tradeoff between solution quality and runtime could be achieved via adjusting players' memory length.