Utility-maximizing Stochastic Control In Mobile Crowd Sensing Systems

As a new compelling paradigm for large-scale sensing data collection and sharing, mobile crowd sensing harnesses the data collection capability of individual smartphones, underpinning a variety of valuable knowledge discovery, environment monitoring and decision making applications. However, it costs a smartphone nonnegligible resources(e.g., energy, CPU, and bandwidth) as it performs sensing tasks and reports sensing data to the system. A smartphone is driven by a battery, and the computing power is typically limited. Utilizing smartphones without limitation will lead to a lower participation of them, which is not good for the sustainability of the system. Therefore, it is a central issue for a mobile crowd sensing system to maximize the utility with the constraints of resource consumption at each smartphone. However,it is particularly challenging because of the randomness of the system. Thus, this thesis focuses on utility-maximizing stochastic control in mobile crowd sensing systems.This thesis can be divided into two topics. The first topic focuses on maximizing the utility of sensing data collection at a given cost of resource consumption at each smartphone. It is particularly challenging. On the one hand, the utility of sensing data from a smartphone is usually dependent on its context which is random and varies over time. On the other hand, because of the marginal effect, the sensing decision of a smartphone is also dependent on decisions of other smartphones. We propose a distributed algorithm for maximizing the utility of sensing data collection when the smartphone cost is constrained. The design of the algorithm is inspired by Lyapunov optimization techniques and distributed correlated scheduling. It does not require any priori knowledge of smartphone contexts in the future, and hence sensing decisions can be made by individual smartphone. Rigorous theoretical analysis show that the proposed algorithm can achieve a time average utility that is within O(1/V) of the theoretical optimum.The second topic considers a more complicated problem of maximizing the profit of a crowd sensing platform which receives sensing requests from various subscribers and completes the requests by leveraging sensing time of participating smartphones.The profit of the platform equals the total charges of sensing request minus the payments to smartphones. It is of great challenge to the maximal profit for the platform, because of stochastic arrivals of sensing requests, dynamic participation of smartphones, and high complexity in allocating requests to smartphones. In response to the challenges, we propose an optimal online control framework which can effciently utilize the limited sensing time on each smartphone. Based on the stochastic Lyapunov optimization techniques combined with the idea of weight perturbation, our control framework makes online control decisions including sensing requests admission and dispatching control, sensing time purchasing control and sensing time allocation control, without requiring any knowledge of the future patterns. Rigorous mathematical analysis and comprehensive simulation results show that our control framework can achieve a time averaged profit that is arbitrarily close to the optimum, while still maintaining strong system stability.