A Time Variant Log-Linear Learning Approach to the SET K-COVER Problem in Wireless Sensor Networks
将传感器节点视为理性玩家，提出一种仅依赖局部信息的时变对数线性学习算法，通过空间势博弈建模，证明算法能以概率1收敛到全局最优解，并在合理时间内优于现有方法。
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.