| Abstract: | Toward the global optimality of the SET K-COVER problem in wireless sensor networks, we view each sensor node as a rational player and propose a time variant log-linear learning algorithm (TVLLA) that relies on local information only. By defining the local utility as the normalized area covered by one node alone, we formulate the problem as a spatial potential game. The resulting optimal Nash equilibria correspond to the optimal partition. Such equilibria are obtained by designing a time varying parameter that approaches infinity with time. Using inhomogeneous Markov chain theory, we prove that the TVLLA guarantees convergence to the optimal solution with probability 1. Comparison results against traditional methods demonstrate that the algorithm can also provide better near-optimal solutions in a reasonable computation time than the state-of-the-art. Our findings pave a new way to reach the global optimality of the SET K-COVER problem in a distributed manner as well as other potential games from the view of self-organized optimization. |
