Please use this identifier to cite or link to this item: https://doi.org/10.1109/JSAC.2008.080914
Title: Optimality and complexity of pure nash equilibria in the coverage game
Authors: Ai, X.
Srinivasan, V.
Tham, C.-K. 
Keywords: Coverage
Game theory
Wireless sensor networks
Issue Date: Sep-2008
Source: Ai, X.,Srinivasan, V.,Tham, C.-K. (2008-09). Optimality and complexity of pure nash equilibria in the coverage game. IEEE Journal on Selected Areas in Communications 26 (7) : 1170-1182. ScholarBank@NUS Repository. https://doi.org/10.1109/JSAC.2008.080914
Abstract: In this paper, we investigate the coverage problem in wireless sensor networks using a game theory method. We assume that nodes are randomly scattered in a sensor field and the goal is to partition these nodes into K sets. At any given time, nodes belonging to only one of these sets actively sense the field. A key challenge is to achieve this partition in a distributed manner with purely local information and yet provide near optimal coverage. We appropriately formulate this coverage problem as a coverage game and prove that the optimal solution is a pure Nash equilibrium. Then, we design synchronous and asynchronous algorithms, which converge to pure Nash equilibria. Moreover, we analyze the optimality and complexity of pure Nash equilibria in the coverage game. We prove that, the ratio between the optimal coverage and the worst case Nash equilibrium coverage, is upper bounded by 2 - 1/m+1 (m is the maximum number of nodes, which cover any point, in the Nash equilibrium solution s*). We prove that finding pure Nash equilibria in the general coverage game is PLS-complete, i.e. "as hard as that of finding a local optimum in any local search problem with efficient computable neighbors". Finally, via extensive simulations, we show that, the Nash equilibria coverage performance is very close to the optimal coverage and the convergence speed is sublinear. Even under the noisy environment, our algorithms can still converge to the pure Nash equilibria. © 2008 IEEE.
Source Title: IEEE Journal on Selected Areas in Communications
URI: http://scholarbank.nus.edu.sg/handle/10635/56948
ISSN: 07338716
DOI: 10.1109/JSAC.2008.080914
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

28
checked on Dec 5, 2017

WEB OF SCIENCETM
Citations

22
checked on Nov 2, 2017

Page view(s)

27
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.