Game Theory Based Strategic Decision Making Of Participants In Participatory Sensing Systems

As the usage of smartphones with multiple embedded smart sensors and mobile computational ability is greatly expanded in our daily life [1], participatory sensing which leverages a large crowd of participants for collecting sensing data has gain more and more attention in reality. In participatory sensing systems, it is notable that whether to take part in collecting sensing data is decided by a participant itself, and it gets the monetary revenue as a payment. It is then important for participatory sensing systems to motivate as many participants as possible with limited budgets. Based on its own payoff, a participant makes a strategic decision that will directly affect the performance of the participatory sensing system and the quality of gathered sensing data. Thus, this thesis focuses on the strategic decision making of participants in participatory sensing systems.Based on the behavior model of participants and the congestion game in game theory, this thesis proposes a Sensing Process Participation(SPP) game, which is novel and different from the previous studies which focus on incentive mechanisms. In SPP game, each participant decides whether to participate in the sensing process or not,based on its own satisfaction state. It is clear that the more satis?ed participants, the better performance of the participatory sensing. The problem of solving the social optimum of SPP game is called the Sensing Process Participation problem. We ?rst rigorously prove that the SPP problem is NP-hard. We then propose a distributed Sensing Process Participation algorithm that will converge to a pure Nash equilibrium in polynomial time. Each participants will check its own satisfaction state and report the better response update to the platform independently, without exchanging information with others. We then prove two properties of the SPP game, including the ?nite improvement property and the price of anarchy. For the general cases that the demands of the participants are not too diverse, the social welfare of pure Nash equilibrium will approximate that of the social optimum.We conduct extensive simulations based on a participatory sensing system with numerous participants and multiple sensing processes. Simulation results show that our proposed sensing process participation algorithm will eventually converge to a pure Nash equilibrium. In general cases, most of the participants in participatory sensing systems will be satis?ed. Meanwhile the SPP algorithm scales well as the number of participants and sensing processes grows.