An Exchange Market Approach for Mobile Crowdsensing

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

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.