Game theoretic approaches to cooperation in wireless networks

Abstract

In this thesis, we use game theoretical approaches to study several cooperation issues in wireless networks.

Firstly, we investigate the coverage problem in wireless sensor networks. We assume that nodes are randomly scattered in a 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 formulate this coverage problem as a coverage game and prove that the optimal solution is a pure Nash equilibrium. We then design synchronous and asynchronous algorithms, which converge to the pure Nash equilibrium. Moreover, we analyze the optimality and complexity of the pure Nash equilibrium in the coverage game, and validate the theoretical results through extensive simulations.

Next, we investigate the WiFi sharing problem in wireless community networks (WCNs). WCNs, where users share wireless bandwidth, has attracted 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 implement firmware modifications to existing routers. We propose a solution which does not require such sophisticated hardware and only requires users to install a client software in their PCs. While this 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. 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.

Finally, we study the fairness problem in credit-based WiFi sharing community. Under credit system, users obtain no more service than they share. Some users, located in unpopular areas accumulate few credits and are unable to access other networks when they roam. Meanwhile, other users located in hot-spots, accumulate extra credits, which they have no way to spend. A priority pricing based WiFi sharing solution (¿PP-WiSh¿), which is also a pure client software solution, is provided to solve this problem. PP-WiSh allows users located in popular areas to spend the excess credits they accumulate for better service and also helps users located in unpopular areas to accumulate extra credits which they can utilize when roaming. We formulate the priority pricing WiFi sharing problem as a distributed optimization problem and theoretically analyze the equilibrium pricing solution of users in the community. Moreover, we prove that all the users with rational and intelligent behaviors will converge to this equilibrium and we demonstrate the convergence and performance improvements through experiments using real world trace data.