执行概率最大化的地理社会网络空间众包参与者招募方法

摘要

本发明提供了一种执行概率最大化的地理社会网络空间众包参与者招募方法，首先采用传播树结构来建模招募者和参与者之间的自主招募，在此基础上，建立任务执行概率计算方法，并利用多层次营销的业务策略设计一种新颖的激励机制，将研究的MTEP问题公式化为组合优化问题，并分析其NP‑hard和高维特性。本发明通过用户社交网络和构建MCS任务传播模型，综合考虑诸多因素建立任务接受度估计和任务奖励金机制，将研究的MTEP问题公式化为组合优化问题，并分析其NP‑hard和高维特性，使用两个真实世界的数据集进行了广泛的实验，验证了MTEPCC方法的实用性。

说明书

技术领域

本发明涉及移动群智感知领域，是一种移动群智感知(MCS)任务执行和移动众包参与者招募方法，尤其涉及地理社交网络中MCS的任务执行概率最大化(MTEP)问题的协同进化求解。

背景技术

随着无线通讯技术的发展，大量带有传感器的移动设备部署在各种生活场景中，移动群智感知技术(MCS)是通过群众的力量来获取动态环境感知信息的有效方法。MCS通常包括三个部分：任务发布者，任务参与者，MCS平台。首先，任务发布者在MCS平台公开发布一个基于位置的(LBS)传感任务，然后，任务参与者收到消息之后共同完成任务，并且获得一些奖励作为回报。

为了让MCS任务被顺利完成，如何招募任务参与者成为一个关键问题。通常情况下，MCS平台直接招募参与者去执行任务。最近出现一种新型招募模式，基于口口相传的MCS，即，MCS先招募有限数量的种子用户作为参与者，然后种子用户通过他们各自的社交关系(亲戚，同学，朋友)私下招募更多的任务执行者(用户)，来为整个MCS体系做出贡献。其中每个参与的用户都根据社交互动将MCS任务选择性地传播到更适合的相邻节点。收到任务邀请的被邀请者可以独立决定是否执行任务。它有以下几点优势：(1)牢固的社交关系会激励用户更加积极地参与MCS任务，提高完成度。(2)任务参与者会因为社交关系的压力更认真地执行任务，提高任务完成质量。(3)在熟人网络中，可以缓解隐私安全困扰问题。

然而，基于口口相传的MCS具有以下几点挑战：(1)基于口口相传的MCS任务传播模型的构建。由于基于口口相传的MCS任务有一定的感知质量要求和奖励预算，并且具有隐私安全性，用户不可能向所有人泛滥的发出邀请，现有的信息传播模型无法使用。(2)对于MCS平台来说，种子用户邀请的任务参与者越多，收到的奖励金也应该越多，必须相应地调整相关的激励机制。(3)从包括任务邀请者和被邀请者在内的参与人员的角度来看，应该聘请哪些社交邻居参与任务，以及哪些任务邀请会被接受。

发明内容

为了克服现有技术的不足，本发明提供一种执行概率最大化的地理社会网络空间众包参与者招募方法。本发明利用以下原理：随着无处不在的智能设备的快速发展和高质量无线通信的发展，移动众包以其协同合作完成大规模复杂任务的巨大潜力而受到越来越多的关注。移动众包的一个典型主题是参与者招募，其中MCS平台直接招募合适的人群参与者移动到指定位置来执行外包任务。最近已经出现了一种新的补充招募模式，即口口相传的移动众包，可以通过充分探索用户的签到记录和社交关系(即地理信息系统)来有效地提高招募效率并提高任务结果质量。因此，提出了一个新的问题，即地理社会网络中MCS的任务执行概率最大化(MTEP)，该问题力求搜索源用户的子集，在预先给定的激励预算下，以最大程度地提高所有被招募参与者的总体任务执行概率。为了描述整个地域社会网络中MCS任务传播过程的特征，首先采用传播树结构来建模招募者和参与者之间的自主招募。在此基础上，建立任务执行概率计算方法，并利用多层次营销的业务策略设计一种新颖的激励机制。将研究的MTEP问题公式化为组合优化问题，并分析其NP-hard和高维特性。基于合作-协同进化框架，提出了一种名为MTEPCC的分而治之的问题解决方法。

本发明解决其技术问题所采用的技术方案包括如下步骤：

步骤1：获取移动用户在社交媒体的历史签到数据，用户兴趣爱好数据以及用户之间的社交关系数据，移动众包任务数据；

步骤2：构建用户社交关系网络；

步骤3：根据用户与任务的距离和用户画像构建用户对任务的执行概率矩阵；

步骤4：构建MCS任务传播模型；

步骤5：由任务传播模型来构建任务执行概率期望；

步骤6：构建奖励金机制；

步骤7：构建基于地理社会网络中MCS的任务执行概率最大化(MTEP)问题；

步骤8：将问题分解，用协同进化的思想解决问题；

步骤9：基于MTEPCC算法找到最优解决方案。

所述步骤1中，移动用户包括时间戳

所述步骤2中，构建用户社交关系网络G＝{u,ε,w}，其中e

其中|N(u

所述步骤3中，构建用户的估计任务执行概率

首先，构建空间熟悉度SF(u

其中

然后，构建用户的兴趣画像

其中使用余弦相似度函数计算相似度；

综合上述两个因素，计算任务执行概率：

任务T对用户u

所述步骤4中，构建面向MCS任务传播模型。首先选择用户节点的一个子集作为源节点S，S∈U，然后，MCS任务通过源节点在整个地理社会网络G中并行传播，来招募新的用户；在传播过程中，每个参与者将有选择地执行MCS任务，一旦用户执行了任务，其直接和间接招募者都将获得额外的奖励。

首先，对于每个选定的源节点，利用树结构来表示传播范围。具体而言，它以每个源节点u为根，以一个广度优先搜索方式逐级扩展传播树TR

U

接下来，基于传播树，在将任务T扩散到后代节点u

其中e

沿着传播树

其中，

当选择了多个源节点时，它们各自的传播树可能会重叠，需要将结果做并集去除重复。因此，在多个源节点的情况下，例如

所述步骤5中，由步骤3得到的任务传播模型来构建任务执行概率期望。并非所有招募的参与者最终都会接受任务邀请并执行任务，他们将自主做出参与决策。对于每个源节点u

其中，U

所述步骤6中，构建激励机制；当一个用户执行了指定任务时，将获得基本激励R

其中f(·)表示具有独立变量Θ的函数，即

其中γ是一个常数，作用是控制f(·)的衰减，f(·)被视为softmax函数；

给定源节点S的子集，总激励金的期望计算如下：

其中，R

所述步骤7中，构建问题定义。在给定了MCS任务集T的情况下，从地理社会网络G＝(U,E,W)(即

所述步骤8中，问题分解是将没有依赖关系的自变量分到不同的子种群中，而将相互依赖的决策变量分到同一个子种群中，保证子种群之间的相互依赖性最小；问题分解的规则为：存在相互依赖关系的变量不能分开成多个子种群。自变量代表的就是不受其他变量影响的独立变量；如果两个决策变量在努力寻找最佳解决方案时不能独立地进行优化，存在相互依赖关系的变量不能独立优化，因为一个变量优化会影响另外一个变量，需要一起做优化，则相互影响，一个决策变量对应于每个有可能被选择作为源节点的移动用户。决策变量之间的相互依存关系只是在不同传播树上的重叠传播。因此，为了更好地分解问题，必须探索不同用户之间的传播树。将移动用户的集合U＝{u

所述步骤9中，初始化ms个子群体{θ

本发明的有益效果在于本发明为一种地理社会网络中考虑任务执行概率最大化的空间众包参与者招募方法，基于口口相传的移动众包招募模式，通过用户社交网络和构建MCS任务传播模型，综合考虑诸多因素建立任务接受度估计和任务奖励金机制。将研究的MTEP问题公式化为组合优化问题，并分析其NP-hard和高维特性。基于合作-协同进化框架，提出了一种名为MTEPCC的分而治之的问题解决方法。使用两个真实世界的数据集进行了广泛的实验，验证了MTEPCC方法的实用性。

附图说明

图1为本发明实例中地理社会网络中MCS任务执行概率最大化的MTEPCC算法流程图。

图2为MCS任务传播树模型。

图3为MTEP问题分解示意图。

具体实施方式

下面结合附图和实施例对本发明进一步说明。

以下结合附图，对本发明上述的和另外的技术特征和优点做详细的说明。

本发明共有3幅附图，请参阅图1所示，本发明的具体步骤如下：

步骤1：获取移动用户在社交媒体的历史签到数据，用户兴趣爱好数据，以及用户之间的社交关系数据，移动众包任务数据。移动用户的签到信息都会发布在社交媒体上，包括时间戳

步骤2：构建用户社交关系网络G＝{u,ε,w}，其中e

其中|N(u

步骤3：构建用户的估计任务执行概率

首先，构建空间熟悉度SF(u

然后，构建用户的兴趣画像

其中使用余弦相似度函数测量相似度。

综合上述两个因素，T对用户u

步骤4：构建面向MCS任务传播模型。对于每个选定的源节点，利用树结构来表示传播范围。找到TR

U

用户u

沿着传播树

其中，

步骤5：由任务传播模型来构建任务执行概率期望。已知招募的用户是

其中，U

步骤6：构建激励机制。每个招募人，例如

其中f(·)表示具有独立变量Θ的函数，即

其中γ是一个常数，其作用是控制f(·)的衰减。

给定源节点S的子集，总激励的期望可以计算如下：

其中，R

步骤7：构建问题定义。在给定了MCS任务集T的情况下，从地理社会网络G＝(U,E,W)(即

步骤8：将移动用户的集合U＝{u

步骤9：初始化ms个子种群{θ

本发明为一种地理社会网络中考虑任务执行概率最大化的空间众包参与者招募方法，基于口口相传的移动众包招募模式，通过用户社交网络和构建MCS任务传播模型，综合考虑诸多因素建立任务接受度估计和任务奖励金机制。将研究的MTEP问题公式化为组合优化问题，并分析其NP-hard和高维特性。基于合作-协同进化框架，提出了一种名为MTEPCC的分而治之的问题解决方法。

以上所述仅为本发明的较佳实施例，对于发明而言仅仅是说明性的，而非限制性的。本专业技术人员理解，在发明权利要求所限定的精神和范围内可对其进行许多改变、修改等，但都将落入本发明的保护范围内。