Wireless community networks, where users share wireless bandwidth is attracting tremendous interest from academia and industry. Companies such as FON have been successful in attracting large communities of users. However, solutions such as FON either require users to buy specialized FON routers or firmware modifications to existing routers. In this paper we propose a solution which requires no such sophisticated hardware. An alternative is to provide a solution which requires users to download a client software on to their PCs. While the solution appears simple it raises several issues of incentivizing users to share their bandwidth and also issues of preventing users from cheating behaviors which give them an unfair advantage. In this paper, we propose a system and solution which (i) requires only software downloads on PCs, (ii) is robust to tampering of the software, and intermittent monitoring of an access point by the owner, (iii) a credit based mechanism whereby users earn credits for sharing bandwidth and punishment and pricing mechanism whereby users are charged at a higher price whenever they are caught misbehaving. By making simple but plausible assumptions about user behavior, we show via analysis and extensive simulations that the system converges to a Pareto optimal Nash equilibrium. We further validate our system model, by running trace driven simulations on real world data. We believe that the solution provided by Wi-Sh is an attractive and more credible alternative to solutions such as FON.

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.