面向移动社交网络的群智计算关键技术研究

摘要

随着移动设备的普及和无线通信技术的快速发展，群智计算作为“互联网+”背景下的一种新兴的分布式问题解决模式，充分利用用户手持智能设备中内置的丰富传感器（GPS、加速计、摄像头、陀螺仪等）和越发强大的存储、计算能力，结合用户在社交网络中的亲密关系和移动规律，代替传统的大规模静态传感器网络解决一些机器或个人难以完成的问题，具有部署方便、灵活、节约资源等优势，在现实环境中拥有广阔的应用前景，也是智慧城市发展的重要组成部分。 本文从群智计算系统的关键步骤出发，关注移动社交网络中的群智计算在线激励机制、位置隐私保护、实时任务分配问题，设计对应的改进算法，以保证群智计算系统在相关的场景中能够高效高质的运行。本文完成的主要工作如下： 1、深入调研了群智计算的国内外研究现状及与其他学科的交叉背景，总结了目前研究中存在的问题和难点，确定本文的切入方向。介绍了群智计算相关理论基础，包括起源与应用、系统结构、关键步骤的基本原理，介绍了隐私保护基本算法及其在群智计算中的应用、移动社交网络的基本知识等，为后续研究的展开奠定基础。 2、提出了基于信誉控制的群智计算用户招募和激励机制。针对以城市Wifi信号监测为代表的用户主动型群智计算场景，研究该场景中的在线实时用户招募和激励问题，以在一定的预算和时间约束下最大化系统效益。在线场景中，用户随机到达和离开任务区域，充分考虑基于位置的计算任务覆盖度和个人贡献度进行建模，首先提出一种改进的多阶段反向拍卖算法，通过在线学习自适应调整每个阶段的密度阈值，动态选择最优用户集。之后，在每次交易结束后根据任务完成质量对用户的信誉进行评价和更新，并对违约一方实施惩罚。用户携带的实时信誉值反之被引入上述反向拍卖算法的效益函数定义中，以指导下个阶段的用户招募。理论分析和仿真结果证明，本文提出的激励机制满足计算有效性、个人合理性、平台收益性和真实性四项基本原则，并且能在一定的时间和预算约束下获得更好的效益。 3、提出了基于差分隐私保护的群智计算任务分配算法。针对以空间环境监测为代表的平台主动型群智计算任务场景，在平台获取用户位置并进行全局任务分配的过程中加入隐私保护策略。引入第三方可信机构，采用不同的隐私空间分解（Privacy Space Decomposition,PSD）算法对用户实时位置信息进行加扰，并将加扰后的统计结果传给众包平台，之后设计合理的贪心算法利用加扰信息进行任务分配，在保障任务分配成功率的基础上，实现任务分配效率与隐私保护效果的最佳均衡。真实和模拟数据的仿真结果均证明，基于差分隐私保护的任务分配算法能在只损失较小的任务分配效率的情况下有效保护用户隐私，而不同的差分隐私策略也具有不同的优缺点，如基于等高线PSD结构的任务分配算法对隐私预算相对不敏感，更适合应用于隐私保护要求较高的场景中。 4、提出了移动社交网络中基于相遇预测的群智计算在线任务分配算法。考虑搭载在移动社交网络中的群智计算模式，利用用户间的亲密关系和相遇规律进行任务的发布和数据回传，通过近距离通信实现大规模数据传输。在该场景下，提出了任务执行与用户相遇时间轴并行模型，同时考虑不同用户对任务的计算能力差异，设计了改进的最小化平均反馈时间和最小化最长反馈时间的在线任务分配算法。仿真结果表明，改进的模型更符合数据需求日益增大的多任务、多异质用户随机游走的复杂群智计算场景，可在相同的任务和用户规模下获得更好的时间增益，提高任务完成效率，在基于移动机会网络的群智计算系统中具有很强的实用和推广价值。

目录

第一个书签之前

摘 要

Abstract

插图目录

表格目录

绪论

研究背景及意义

国内外研究现状

群智计算激励机制国内外研究现状

群智计算任务分配国内外研究现状

群智计算隐私保护国内外研究现状

目前研究中主要存在的问题

本文研究内容和组织结构

群智计算相关技术理论基础

群智计算理论基础

群智计算的起源和应用

群智计算系统基本结构

群智计算激励机制拍卖模型理论基础

群智计算任务分配原则分析

隐私保护理论基础

隐私保护基本策略

群智计算隐私保护研究综述

群智计算中的差分隐私技术

移动社交网络理论基础

本章小结

基于信誉控制的群智计算用户招募和激励机制

引言

系统模型

基于信誉控制的激励机制算法设计

改进的多阶段反向拍卖算法

带惩罚期的信誉更新算法

算法性能与仿真结果分析

算法可行性和必要性证明

仿真结果与分析

本章小结

基于差分隐私保护的群智计算任务分配算法

引言

系统模型

基于差分隐私保护的任务分配算法设计

基于双层自适应网格PSD结构的任务分配算法

基于等高线PSD结构的任务分配算法

仿真参数设置与结果分析

本章小结

社交网络中基于相遇预测的群智计算任务分配算法

引言

系统模型

基于相遇预测的任务分配算法设计

算法步骤分析

最小化平均反馈时间的任务分配算法

最小化最长反馈时间的任务分配算法

仿真结果与分析

仿真参数设置

最小化平均反馈时间的任务分配算法仿真结果与分析

最小化最长反馈时间的任务分配算法仿真结果与分析

本章小结

总结与展望

本文工作总结

未来工作展望

致 谢

参考文献

作者简介(包括论文和成果清单)