群感知模式下的收益优化机制与算法研究

With the proliferation of hand-held mobile devices such as smart phones, using sensor-equipped mobile devices to fulfill sensing tasks (i.e., crowdsensing) has become a hot research topic recently. The paradigm of crowdsensing has a series of unique features, such as the lack of incentives for participation, the time-sensitivity, the uncertainty of sensing quality, as well as the heterogeneity, dynamics and sociality of the crowdsensing users. Facing the new challenges brought by these unique features, this project thoroughly studies the revenue optimization problem in crowdsensing to improve the sensing value gained by collecting crowdsensing data, leveraging related theories and techniques including combinatorial optimization, mechanism design and online machine learning. The detailed issues studied in this project include the truthful time-scheduling mechanism, the user recruitment algorithm under uncertainty, the algorithms for cooperative crowdsensing, the dynamic mechanisms for variable user groups, the crowdsensing algorithms based on mobile social networks, and the performance valuation of the proposed mechanisms and algorithms for crowdsensing. Through the study of this project, we will design a series of practical and efficient mechanisms and algorithms for revenue optimization in crowdsensing, which can provide significant theoretical and technical supports to improve the practicability and popularity of the crowdsensing paradigm.

随着智能手机等手持移动设备的普及，利用配备在移动设备中的传感器来执行感知任务（即群感知）已经成为当前的研究热点。群感知模式具有一系列独有特征，包括用户参与动因的贫乏性、群感知的时间敏感性、群感知数据质量的不确定性、群感知用户的异构性、动态性和社会性等。为此，本项目针对群感知模式的独有特征和新型挑战，利用组合优化、机制设计、在线机器学习等相关理论和技术，对如何优化群感知模式下的收益展开深入研究，从而提高通过收集群感知数据所获取的价值。研究内容包括诚实的群感知调度机制、不确定环境下的群感知用户招募算法、群感知模式下的协作感知算法、面向变化用户群体的动态群感知机制、基于移动社交网络的群感知算法，以及群感知模式下收益优化机制与算法的实验验证等。通过这一研究，本项目将设计出一系列高效实用的群感知模式下的收益优化机制和算法，能够为促进群感知模式的实用性和普及性提供有效的理论和技术支撑。

随着智能手机等手持移动设备的普及，利用配备在移动设备中的传感器来执行感知任务（即群感知）已经成为当前的研究热点。本项目针对群感知模式的独有特征和新型挑战，利用组合优化、机制设计、在线机器学习等相关理论和技术，设计出了一系列高效实用的群感知模式下的收益优化机制和算法，其中主要包括：1)针对用户的策略性和时空约束等特征，利用机制设计理论在离线和在线两种情况下均提出了群感知任务的分配与调度算法，在保证用户诚实性的同时，证明了所提算法的竞争比和近似比；2)针对用户行为的随机性和感知质量的不确定性，提出了质量敏感的定价和群感知用户招募算法，并基于所发现泊松二项分布的非平凡次模性质，证明了所提算法的近似比；3) 针对用户感知代价不确定、感知任务异构的特征，基于多臂匪徒理论提出了一种多任务情况下面向在线用户的动态定价算法，在具有预算约束的情况下证明了算法能够达到对数级的悔过；4) 针对群感知用户的社会性，提出了一种基于影响力最大化的群感知用户种子节点选取算法，能够通过在社交网络中自适应地选取种子节点来吸引更多的用户参与群感知活动；5)针对用户感知能力的异构性，提出了一种预算和感知能力约束下的群感知种子节点选取算法，并证明了所提算法能够以大概率达到双准则的近似比。大量实验结果表明，项目所提出的机制与算法在感知收益和时间效率等多项指标上显著优于已有算法。本项目的研究能够为促进群感知模式的实用性和普及性提供有效的理论和技术支撑，相关研究成果已经发表在包括IEEE/ACM Transactions on Networking、IEEE Transactions on Computers、PVLDB、IEEE ICDE、ACM MobiHoc在内的多种国际顶级期刊和会议上。在项目支持下，项目组目前已培养硕士研究生10余人，并多次获得研究生国家奖学金。