位置相关众感任务的群组构建方法研究

With gradually maturing and prevalence of technologies such as Web 2.0, smartphones, Global Position System, and customized maps, a type of sensing system based on crowds of people becomes common practice, which is called Crowdsensing. The aim of crowdsensing is to monitor the significant events and states of the society or environment on the spot, by utilizing the users' and their portable devices' ability of moving, computing, communicating and sensing. Only the team that satisfies particular constraints can complete a crowdsensing task with high quality and low cost. This project will research the method of team formation under location constraints, in order to match users with tasks suitably, thus can achieve location-aware crowdsensing tasks efficiently. In detail, we will study: (1) team location constraint model, (2) user location prediction algorithm, and (3) optimum team searching strategy. The significance of this research is that with team location constraint model and user location prediction algorithm, the ideal team to perform a crowdsensing task can be found, therefore able to avoid users' choice anxiety, foresee and control the task quality, and reduce the wasting of resources. The results would provide theory and technology support for applications with national critical demands such as environment monitoring, disaster management, intelligent transportation, public security, health care, etc.

随着Web 2.0、智能手机、全球定位系统、可定制地图等技术的日趋成熟和流行，一种基于大众的感知系统蔚然兴起，被称为大众感知（众感)系统。众感系统的主要目的在于，利用大量而广泛的用户及其便携设备的移动、计算、通信和感知能力，实时实地监测社会或环境中具有重要意义的事件与状态。在众感系统中，只有满足特定约束的群组，才能高质量低代价地完成众感任务。本项目旨在研究位置约束下的群组构建方法，使得用户与任务合理匹配，从而高效完成位置相关众感任务。具体研究内容包括：（1）群组位置约束模型；（2）用户位置预测算法；（3）最优群组搜索策略。本研究意义在于通过群组位置约束模型和用户位置预测算法，找出可执行众感任务的理想群组，从而避免用户选择困扰，预知并控制任务质量，并减少资源浪费，为环境监测、灾难管理、智能交通、公共安全、健康卫生等国家重大战略需求的应用领域提供理论和技术支持。

众感（即群智感知）系统利用大量而广泛的用户及其便携设备的移动、计算、通信和感知能力，实时实地监测社会或环境中具有重要意义的事件与状态。在众感系统中，只有满足特定约束的群组，才能高质量低代价地完成众感任务。本项目旨在研究位置约束下的群组构建方法，使得用户与任务合理匹配，从而高效完成位置相关众感任务。本项目经过三年按计划的执行，已经达成该目标，建立了能够描述任务质量要求的群组位置约束模型，挖掘了用户移动规律并能预测其位置，设计实现了搜索满足约束的最优群组的策略。本项目的主要进展和取得的研究成果包括：1）建立了“t-时隙k-覆盖”群组位置约束模型，具有描述时间粒度、空间粒度和每点样本数量等约束的能力；2）建立了“本地影响力最大化”群组位置约束模型，具有描述群组人数、群组能力覆盖、受影响者数量及位置分布等约束的能力；3）提出了马尔可夫多跳用户位置预测算法，能以较高准确率预测用户未来一段时间内时时刻刻的位置，4）设计了基于贪心策略的最优群组搜索策略，以针对当问题规模变大而线性规划不可求解的情况；5）设计了基于模拟退火的最优群组搜索策略，克服了在不规则解空间中难以构造临近解和快速达到最远解的问题；6）实现了众感系统原型及若干应用实例，采集并分析了大量基于位置的社交网络数据。本项目成果价值在于，通过群组位置约束模型和用户位置预测算法，可以找到可执行众感任务的理想群组，从而避免用户选择困扰，预知并控制任务质量，并减少资源浪费，为环境监测、灾难管理、智能交通、公共安全、健康卫生等国家重大战略需求的应用领域提供了理论和技术支持。