Greedy Game Algorithms for Solving SET <inline-formula> <tex-math notation="LaTeX">$K$ </tex-math></inline-formula>-Cover Problem in HWSNs

Abstract

Coverage is a fundamental problem in heterogeneous wireless sensor networks (HWSNs). Lifetime of the HWSNs is another important problem in this area. The K-Cover problem can solve both the coverage and lifetime issues. Especially, the lifetime of HWSNs can be prolonged by solving the SET K-Cover problem through partitioning the sensors into K sets. However, the SET K-Cover problem has not been widely researched in HWSNs. Hence, we introduce three kinds of simple pure distributed algorithms named greedy game algorithms (GGAs) based on game theory for solving the SET K-Cover problem in this paper, in which we consider the SET K-Cover problem as a multi-stage game process. The sensors in HWSNs are considered as the players, the cover sets chosen by N sensors as strategies, and the sensing area alone as the payoff function for each sensor. During the game process, each sensor wants to selfishly choose one of the K-covers at each iteration, with which it can maximize its payoff value. After the game process, the best strategies all the players have chosen constitute the Nash Equilibrium. Finally, extensive experiments have been conducted to show the superiority in coverage, convergence, robustness, and network design of the proposed GGAs comparing with other existing algorithms.

Keywords

• Greedy game algorithms (GGAs)
• K-Cover%22%2C%22default_operator%22%3A%22AND%22%7D%7D%7D"> SET <italic xmlns:ali="http://www.niso.org/schemas/ali/1.0/" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">K</italic>-Cover
• heterogeneous wireless sensor networks (HWSNs)
• Nash equilibrium