With the rich set of embedded sensors installed in smartphones, we are witnessing the emergence of many innovative commercial mobile crowdsensing applications, which combine the power of mobile technology with crowdsourcing to effectively collect time-sensitive and location-dependent information. Motivated by these real-world applications, we consider the distributed task selection problem for heterogeneous users with different initial locations, destinations, costs, speeds, and reputation levels. We design a Bayesian asynchronous task selection (BATS) algorithm to help the users plan their task selections based on the incomplete information of the task popularity statistics. We prove its convergence and characterize the computation time for the users' updates. As a performance benchmark, we consider the ideal case that the service provider centrally allocates the tasks to the users for social surplus maximization. We show that it is an NP-hard problem and propose a greedy centralized algorithm with a lower complexity as the benchmark performance. Simulation results suggest that the BATS scheme achieves the highest Jain's fairness index and coverage, while yielding a user payoff similar to that with the greedy centralized benchmark. Finally, we evaluate the schemes based on some real-world movement time and distance data from Google Maps.

Intelligent network selection plays an important role in achieving an effective data offloading in the integrated cellular and Wi-Fi networks. However, previously proposed network selection schemes mainly focused on offloading as much data traffic to Wi-Fi as possible, without systematically considering the Wi-Fi network congestion and the ping-pong effect, both of which may lead to a poor overall user quality of experience. Thus, in this paper, we study a more practical network selection problem by considering both the impacts of the network congestion and switching penalties. More specifically, we formulate the users' interactions as a Bayesian network selection game (NSG) under the incomplete information of the users' mobilities. We prove that it is a Bayesian potential game and show the existence of a pure Bayesian-Nash equilibrium that can be easily reached. We then propose a distributed network selection (DNS) algorithm based on the network congestion statistics obtained from the operator. Furthermore, we show that computing the optimal centralized network allocation is an NP-hard problem, which further justifies our distributed approach. Simulation results show that the DNS algorithm achieves the highest user utility and a good fairness among users, as compared with the on-the-spot offloading and cellular-only benchmark schemes.

With the rich set of embedded sensors installed in smartphones and the large number of mobile users, we witness the emergence of many innovative commercial mobile crowdsensing applications that combine the power of mobile technology with crowdsourcing to deliver time-sensitive and location-dependent information to their customers. Motivated by these real-world applications, we consider the task selection problem for heterogeneous users with different initial locations, movement costs, movement speeds, and reputation levels. Computing the social surplus maximization task allocation turns out to be an NP-hard problem. Hence we focus on the distributed case, and propose an asynchronous and distributed task selection (ADTS) algorithm to help the users plan their task selections on their own. We prove the convergence of the algorithm, and further characterize the computation time for users' updates in the algorithm. Simulation results suggest that the ADTS scheme achieves the highest Jain's fairness index and coverage comparing with several benchmark algorithms, while yielding similar user payoff to a greedy centralized benchmark. Finally, we illustrate how mobile users coordinate under the ADTS scheme based on some practical movement time data derived from Google Maps.

Today's wireless networks are increasingly crowded with an explosion of wireless users, who have greater and more diverse quality of service (QoS) demands than ever before. However, the amount of spectrum that can be used to satisfy these demands remains finite. This leads to a great challenge for wireless users to effectively share the spectrum to achieve their QoS requirements. This paper presents a game theoretic model for spectrum sharing, where users seek to satisfy their QoS demands in a distributed fashion. Our spectrum sharing model is quite general, because we allow different wireless channels to provide different QoS, depending upon their channel conditions and how many users are trying to access them. Also, users can be highly heterogeneous, with different QoS demands, depending upon their activities, hardware capabilities, and technology choices. Under such a general setting, we show that it is NP hard to find a spectrum allocation which satisfies the maximum number of users' QoS requirements in a centralized fashion. We also show that allowing users to self-organize through distributed channel selections is a viable alternative to the centralized optimization, because better response updating is guaranteed to reach a pure Nash equilibria in polynomial time. By bounding the price of anarchy, we demonstrate that the worst case pure Nash equilibrium can be close to optimal, when users and channels are not very heterogenous. We also extend our model by considering the frequency spatial reuse, and consider the user interactions as a game upon a graph where players only contend with their neighbors. We prove that better response updating is still guaranteed to reach a pure Nash equilibrium in this more general spatial QoS satisfaction game.

Today's wireless networks are facing tremendous growth and many applications have more demanding quality of service (QoS) requirements than ever before. However, there is only a finite amount of wireless resources (such as spectrum) that can be used to satisfy these demanding requirements. We present a general QoS satisfaction game framework for modeling the issue of distributed spectrum sharing to meet QoS requirements. Our study is motivated by the observation that finding globally optimal spectrum sharing solutions with QoS guarantees is NP hard. We show that the QoS satisfaction game has the finite improvement property, and the users can self-organize into a pure Nash equilibrium in polynomial time. By bounding the price of anarchy, we demonstrate that the worst case pure Nash equilibrium can be close to the global optimal solution when users' QoS demands are not too diverse.

Cognitive radio gives users the ability to switch channels and make use of dynamic spectrum opportunities. However, switching channels takes time, and may affect the quality of a user's transmission. When a cognitive radio user's channel becomes unavailable, sometimes it may be better waiting until its current channel becomes available again. Motivated by the recent FCC ruling on TV white space, we consider the scenario where cognitive radio users are given the foreknowledge of channel availabilities. Using this information, each user must decide when and how to switch channels. The users wish to exploit spectrum opportunities, but they must take account of the cost of switching channels and the congestion that comes from sharing channels with one another. We model the scenario as a game which, as we show, is equivalent to a network congestion game in the literature after proper and non-trivial transformations. This allows us to design a protocol which the users can apply to find Nash equilibria in a distributed manner. We further evaluate how the performance of the proposed schemes depends on switching cost using real channel availability measurements.

In this paper, we introduce and analyze the properties of a class of games, the atomic congestion games on graphs (ACGGs), which is a generalization of the classical congestion games. In particular, an ACGG captures the spatial information that is often ignored in a classical congestion game. This is useful in many networking problems, e.g., wireless networks where interference among the users heavily depends on the spatial information. In an ACGG, a player's payoff for using a resource is a function of the number of players who interact with it and use the same resource. Such spatial information can be captured by a graph. We study fundamental properties of the ACGGs: under what conditions these games possess a pure strategy Nash equilibrium (PNE), or the finite improvement property (FIP), which is sufficient for the existence of a PNE. We show that a PNE may not exist in general, but that it does exist in many important special cases including tree, loop, or regular bipartite networks. The FIP holds for important special cases including systems with two resources or identical payoff functions for each resource. Finally, we present two wireless network applications of ACGGs: power control and channel contention under IEEE 802.11.