An Exchange Market Approach for Mobile Crowdsensing

包括智能手机和平板电脑在内的小型便携式移动设备正变得非常普遍。这些口袋大小的小工具有一套嵌入式传感器，可以提供丰富的环境和人类社会的传感数据，从而为开展众感提供了很大的机会。该项目的一个主要目标是开发一个具有公平定价和任务分配的移动众测框架。一个关键的挑战是，参与移动众测的各方，包括移动用户、任务所有者和平台，存在利益冲突：1)移动用户的目标是实现执行传感任务的利润最大化；2)任务所有者努力让他们的传感任务以高质量的传感执行，成本尽可能小；3)该平台希望实现社会福利最大化。基于交换经济理论的最新进展，该项目将解决这一挑战，以取得适当的平衡，并使它们协同工作。该项目是探索工程、经济和运筹学相互作用的创新研究的一个很好的例子。这将为智能健康、智慧城市等大规模移动传感应用开辟新的思路，造福整个社会。该项目的另一项主要任务是将研究与教育活动相结合。吸引交换经济理论，该项目采用“瓦尔拉斯均衡”的概念作为总体指标，其中存在移动用户的价格向量和任务所有者的分配，这样分配是帕累托最优的，市场得到清理（即，所有感知任务都被执行）。在有约束的联合定价和任务调度的共同主题下，本项目围绕设计能够实现瓦尔拉斯均衡的算法，用于感知任务可分或不可分的两种情况。推力1通过战略议价方法研究具有可分传感任务的众测联合定价和任务分配。首先将研究瓦尔拉斯均衡的存在性，并将集中方案用作基准。然后，基于多方议价理论，设计了移动用户和任务所有者相互协商定价和分配的去中心化算法，并对议价博弈输出收敛到瓦尔拉斯均衡进行了深入研究。推力II将致力于具有不可分割传感任务的众传感的联合定价和分配。在这个更复杂的环境中，一个挑战是可能不存在瓦尔拉斯均衡。鉴于此，组合瓦尔拉斯均衡（瓦尔拉斯均衡的一种松弛）的概念将被应用于表征“最优状态”。由于这种放松可能会产生一些效率低下的问题，我们将采用以政府为基础的方法，以接近最优社会福利和个人收入的比率来量化相应的表现。此外，将开发分散的解决方案来实现组合瓦尔拉斯均衡。

Small-sized portable mobile devices, including smartphones and tablet computers, are becoming extremely prevailing. These pocket-sized gadgets have a set of embedded sensors and can provide abundant sensing data about the environment and human society, thus offering great opportunities to carry out crowdsensing. One primary objective of this project is to develop a mobile crowdsensing framework with fair pricing and task allocation. A key challenge is that different parties involved in mobile crowdsensing, including mobile users, task owners, and the platform, have conflicting interests: 1) mobile users aim to maximize the profit for performing sensing tasks; 2) task owners strive to get their sensing tasks performed with high quality of sensing, at a cost as small as possible; and 3) the platform would desire social welfare maximization. Based on recent advances in Exchange Economy theory, this project will tackle this challenge to strike a right balance and enable them to work in concert. This project serves as an excellent example for exploring innovative research on the interplay among engineering, economics and operation research. It will spur a new line of thinking for large-scale mobile sensing in applications including smart health and smart city, benefiting the society at large. Another major task of this project is to integrate research into educational activities.Appealing to Exchange Economy theory, this project employs the notion of "Walrasian Equilibrium" as the overall metric, at which there exists a price vector for mobile users and an allocation for task owners, such that the allocation is Pareto optimal and the market gets cleared (i.e., all sensing tasks are performed). Under the common theme of joint pricing and task scheduling with constraints, this project is centered around devising algorithms that can achieve a Walrasian Equilibrium, for both cases where sensing tasks are either divisible or indivisible. Thrust I studies joint pricing and task allocation for crowdsensing with divisible sensing tasks, via a strategic bargaining approach. The existence of a Walrasian Equilibrium will be investigated first, together with a centralized scheme used as a benchmark. Then, based on multi-lateral bargaining theory, decentralized algorithms will be devised where mobile users and task owners negotiate with each other to determine the pricing and allocation, and the convergence of the bargaining game output to a Walrasian Equilibrium will be investigated thoroughly. Thrust II will be devoted to joint pricing and allocation for crowdsensing with indivisible sensing tasks. One challenge in this more sophisticated setting is that there may not exist a Walrasian Equilibrium. In light of this, the notion of Combinatorial Walrasian Equilibrium (a relaxation of Walrasian Equilibrium) will be applied to characterize an "optimal state." Since this relaxation may give rise to some inefficiency issues, the Tatonnement based approach will be taken to quantify the corresponding performance, in terms of the ratios to approximate the optimal social welfare and individual revenue. Further, decentralized solutions will be developed to achieve a Combinatorial Walrasian Equilibrium.