文章快速检索     高级检索
  浙江大学学报(工学版)  2018, Vol. 52 Issue (9): 1709-1716  DOI:10.3785/j.issn.1008-973X.2018.09.011
0

引用本文 [复制中英文]

王亮, 於志文, 郭斌, 熊菲. 基于移动社交网络的群智感知社群化任务分发[J]. 浙江大学学报(工学版), 2018, 52(9): 1709-1716.
dx.doi.org/10.3785/j.issn.1008-973X.2018.09.011
[复制中文]
WANG Liang, YU Zhi-wen, GUO Bin, XIONG Fei. Crowd sensing socialization task allocation based on mobile social network[J]. Journal of Zhejiang University(Engineering Science), 2018, 52(9): 1709-1716.
dx.doi.org/10.3785/j.issn.1008-973X.2018.09.011
[复制英文]

基金项目

国家“973”重点基础研究发展规划资助项目(2015CB352400);国家自然科学基金资助项目(61402360, 61373119);陕西省教育厅科学研究计划项目(16JK1509);陕西省自然科学基础研究计划资助项目(2018JQ6034)

作者简介

王亮(1984—),男,副教授,从事普适计算、群智感知研究.
orcid.org/0000-0002-5897-4401.
E-mail: liangwang0123@gmail.com.

通信联系人

於志文,男,教授,博导.
orcid.org/0000-0002-5023-5508.
E-mail: zhiwenyu@nwpu.edu.cn
.

文章历史

收稿日期:2017-11-04
基于移动社交网络的群智感知社群化任务分发
王亮1,2, 於志文1, 郭斌1, 熊菲3     
1. 西北工业大学 计算机学院, 陕西 西安 710072;
2. 西安科技大学 电气与控制工程学院, 陕西 西安 710054;
3. 北京交通大学 电子信息工程学院, 北京 100044
摘要: 针对传统的“平台—用户”移动群智感知任务分发方式在任务执行鲁棒性以及数据回收方面存在的缺陷与不足,以群智感知参与用户的群体社会属性为基础,提出一种“平台—社群—用户”的社群化任务分发方法. 基于参与用户时空移动特征分布的近似度计算对用户进行动态社群划分聚类,通过在社群中设置社群组织者与社群从属者角色,同时引入社交亲密度连接关系网络等模型,构建移动群智感知任务初次社群分发与二次用户选择的方法. 基于WTD公开数据集上的实验结果表明,与传统的任务分发方式相比,所提方法可可有效提升任务完成率,增强执行过程的鲁棒性,同时可减少任务分发次数、降低通信负载.
关键词: 群智感知    社群划分    任务分发    移动社交网络    
Crowd sensing socialization task allocation based on mobile social network
WANG Liang1,2 , YU Zhi-wen1 , GUO Bin1 , XIONG Fei3     
1. School of Computer Science and Engineering, Northwestern Polytechnical University, Xi'an 710072, China;
2. School of Electrical and Control Engineering, Xi`an University of Science and Technology, Xi'an 710054, China;
3. School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044, China
Abstract: A "platform-community-user" socialization task allocation approach was proposed by leveraging participant users' group social characteristics in view of the shortcomings of traditional "platform-user" mobile crowd sensing model. Firstly, a dynamic community division clustering was achieved based on the similarity of users' spatiotemporal mobility distribution. And then, via the roles of the community organizer and subordinate, a novel mobile crowd sensing task mechanism, i.e., primary community distribution and secondary user selection, was proposed by incorporating social intimacy connection network. The experimental results on public WTD data set show that, compared with the traditional task allocation method, the proposed method can effectively improve the task completion rate, enhance the robustness of the execution process, reduce the number of execution iteration and the communication overhead.
Key words: crowd sensing    community partition    task allocation    mobile social networks    

随着用户手持移动智能设备的日益普及以及无线通信网络技术的不断发展,通过移动用户有意识或无意识的协同参与,利用移动智能设备各种内置传感器(GPS、陀螺仪、麦克风、摄像头等)实现对物理世界的大规模状态感知与数据采集,催生了一种新的基于物联网的以人为中心的感知模式—移动群智感知(mobile crowd sensing,MCS)[1-3]. 移动群智感知将众包的理念与移动感知相结合,以参与用户作为“移动的传感器”,有效克服了传统无线传感网部署与维护成本高、覆盖有限、可扩展性差等显著问题. 目前,已经在环境监测(噪声水平、PM2.5浓度)、智能交通(交通流量监测、交通道路监测、寻找停车位)、公共安全等诸多领域进行了相关的应用,如Common Sense、Creek Watch、Ear-Phone等群智感知应用平台[4-6]. 同时,对这一新兴应用领域的研究引起了学术界的广泛关注.

现有的移动群智感知运行框架绝大多数是基于“平台-用户”的运行模式,即移动群智感知平台直接面向参与用户分发移动感知任务,参与用户执行感知任务并将感知数据(状态数据、文本数据、图像数据以及音视频数据等)上传至群智感知平台[1-3]. 针对移动群智感知任务分发(或是执行用户选择)这一具体问题,MCS平台以所发布任务的时间、空间、技能等属性需求与潜在参与用户群体在时空移动性、设备属性、历史声誉方面的多维度匹配为手段,以MCS分发任务量最大(或是任务期望完成概率值最大)与用户激励成本预算最小为优化目标选择任务的在线/离线分发方案[7-9]. 通过对上述传统型MCS任务分发模式的分析,发现以下问题。

1)该模式以感知任务的预期任务完成评估为导向,分发方案制定之后不再更改,缺乏对用户实际执行感知任务情况灵活有效的过程监督与适时干预. 一旦所构建的用户未来行为预测模型存在较大偏差,或是实际的任务执行场景产生显著变化,该模式就难以有效保障感知任务执行的鲁棒性,会造成任务完成率低下、结果数据质量粗糙等问题. 在现实应用场景中,参与用户行为的随机性与动态性将有可能进一步凸显并加剧这一问题.

2)针对1)所涉及的任务执行鲁棒性问题,在传统“平台—用户”的双层模式下,一旦预先所选定的用户由于自身原因(如:出行路线变更)拒绝执行所分派的感知任务[10-11],则平台有必要对所预先确定的分发方案进行在线修正,以重新选择新用户执行上述任务. 然而,考虑到普遍应用的单个用户最大执行任务数约束条件以及用户出于隐私保护的目的隐藏其实时空间位置信息的客观现实,MCS平台很难选择合适的替补用户完成对该任务的执行过程;在最坏情况下甚至有可能出现“平台分发—用户拒绝—平台分发—用户拒绝—···”的多次循环,从而造成大量的通信负载与计算资源的浪费.

3)对于群智感知应用平台而言,感知任务的分发是相关应用运行的先期过程,而感知结果数据的收集、分析、集成则是后期过程. 相较于先期过程,后期过程对于应用而言更加具有直接、显著的影响作用. 然而,现有的移动群智感知任务分发工作大多体现出“重分发、轻回收”的特点[12-15],即在任务分发方案的制定过程中只关注在所构建的用户行为模型下,如何将现有任务分发给合适的用户以实现任务的有效执行,而未考虑感知数据从用户端到平台端的回收过程. 换句话说,感知任务的分发或是用户选择方案的确定仅仅考虑了任务的执行,而未结合任务执行完成之后感知结果数据的回收情况. 这对于群智感知应用的正常运行明显是不够的. 在感知数据的收集中,通信负载是造成用户设备能耗过高、阻碍用户参与积极性、增加MCS应用运行成本等方面的主要因素. 目前,已有部分工作考虑到这一问题,提出利用用户在通话、浏览网页的过程并行进行数据的上传/下载,以降低用户的通信负担[8,16],这一模式可以在一定程度上缓解上述问题,然而对于较大数据集其效用依然有限. 根据感知数据规模的不同,考虑设计不同的感知数据上传方式:对于任务属性描述、感知状态数据这一类小数据可采用3G/4G 网络进行直接传输,而对于采集图像、音频以及视频等较大数据则采用移动社交网络的机会式短距离通信进行数据的上传,以降低数据回收的能耗.

为了构建移动群智感知任务执行过程鲁棒性更强、用户协作性更高,同时充分考虑后续感知数据结果回收影响性因素,本文提出构建面向移动社交网络的群智感知任务社群化分发方法,即充分利用群智感知参与用户的社会关系属性与移动社群结构,基于“平台—社群—用户”三层结构组织形式,建立参与用户社群行为发现、协作式感知任务执行、感知数据结果回收的综合性、层次化任务分发模式.

1 问题定义与方案概述 1. 1 问题定义

给定 $n$ 个移动群智感知参与用户集合 $W = \{ {w_1},{w_2},\,\cdots\, ,{w_n}\} $ ,任一用户的历史移动轨迹数据表示为 $R = < {l_j},{c_j},{d_j} > $ ,其中 ${l_j}$ 为时间戳 ${c_j}$ 所对应的空间位置, ${d_j}$ 为相应的日期信息.

移动群智感知平台接收任务发布者所发布的MCS任务集合 $T = \{ {t_1},{t_2},\cdots,{t_m}\} $ ,其中任务 ${t_i} = < {l_i},{c_i} > $ ,表示任务需要在指定的空间位置 ${l_i}$ 和时间间隔 ${c_i}$ 内完成感知任务 ${t_i}$ . 为了简化起见,对于任务的时间间隔属性,本文采用等粒度的时长为1 h的时间间隔划分,比如c=<8:00—9:00>,对于不同的应用场景该参数可以进行相应的调整. 对于任意给定的MCS任务集合T,任务分发问题的目标在于从潜在可用的参与用户集合 $W$ 中寻找一个最优的用户子集 ${W^*}$ ,以实现对T中所包含任务的最大化完成率与任务执行过程中最小化通信开销的目的。

1. 2 方案概述

考虑一个具体的MCS应用场景,在校园环境中需要寻找下午17:00—19:00期间使用率最低的某一个或几个教室,可用参与用户为在应用平台上注册且状态有效的全部用户. 为了实现精准化的任务分发过程,平台要求用户在不影响个人隐私的前提下提供有限日期的历史移动轨迹数据,作为平台分析用户内在移动行为规律的依据. 在移动社交网络环境下,社群化任务分发需要首先统计所有用户历史数据在给定时间间隔(17:00—19:00)内的移动行为特征 ${V}(w,l,t_{\rm s})$ (其中,w为用户,l为位置,ts为硬划分的时间段),进而以 $q$ 维特征矢量 ${V}$ (离散空间位置的个数)为基础进行不同参与用户的社群划分与聚类. 社群划分的结果反映的是不同用户在时空移动行为方面的相似性与差异性,同一社群内的用户可以理解为同一班级内学生,因为课表大致相同所以在移动行为上具有统计意义上的高度相似性. 经过时空行为划分之后的每一个社群在空间维度上,可将其看作是空间离散位置 $L = \{ {l_1},{l_2},\cdots,{l_q}\} $ 的一个完整划分,因为通过移动行为相似性计算,可以实现按照不同空间位置的偏好程度将不同的社群区分开来. 然而,需要注意的是,这种对空间的划分并非完全意义上的“硬划分”,而是“柔性划分”,即由于重叠社群现象的存在,同一个空间位置可能被划分到某几个不同的社群中. 在社群内部,按照移动活跃度计算值筛选出唯一的一个社群组织者作为所在社群的感知任务协调者与感知数据中继.

基于不同移动社群所表征的空间位置偏好,MCS平台将不同的空间感知任务初次分发给相应的社群(社群组织者). 社群组织者参照所在社群内部从属者对于相应空间位置的偏好程度、活跃程度以及与社群组织者之间的社交亲密度,以一种随机生成概率方式将任务二次分发给特定的用户进行感知任务的执行. 在任务执行过程中,若选定用户由于现实因素无法继续执行所分派的任务,则其可通知所在社群的组织者重新选择任务执行者,或是利用移动社交网络将该任务传递给高亲密度社交用户(好友)委派其代为执行感知任务. 在感知结果的回收过程中,利用移动社交网络的机会式通信方式,感知结果将由源节点(任务执行者)通过单跳或是多跳方式传递给社群组织者,再由社群组织者将结果进行初步统计发送给MCS平台. 整个方案的流程如下图1所示.

图 1 移动群智感知社群化任务分发流程图 Fig. 1 Flow of socialization task distribution in mobile crowd sensing
2 基于移动行为相似度的社群动态划分

定义:移动行为特征。移动行为特征反映用户在给定时间间隔内,在不同空间位置上的移动时空行为分布特征. 本文选择用户的空间出现频次与停留时间长度作为移动行为特征的刻画,具体的公式可表示为

$o({w_j},{l_i}) = \frac{{f({w_j},{l_i})}}{{f({w_j},l)}} \times \frac{{d({w_j},{l_i})}}{{d({w_j},l)}}.$ (1)

式中: $o({w_j},{l_i})$ 表示用户 ${w_j}$ 在空间位置 ${l_i}$ 上的移动行为特征, $f({w_j},{l_i})$ $f({w_j},l)$ 分别表示用户 ${w_j}$ ${l_i}$ 上的访问频次以及在所有空间位置 $l$ 上的访问频次, $d({w_j},{l_i})$ $d({w_j},l)$ 分别表示 ${w_j}$ ${l_i}$ 上的停留时长以及在所有空间位置 $l$ 上的停留时长. 用户 ${w_j}$ 在所有空间位置上的移动行为特征分布构成 $q$ 维矢量(离散空间位置规模为q):

${V}({w_j},l\,) = (o\,({w_j},{l_1}),o({w_j},{l_2}),\cdots,o({w_j},{l_q})).$

在移动用户社群划分过程中所使用的移动行为特征分布属于相对值计算. 换句话说特征分布刻画的是用户对不同空间位置的“偏好程度”. 在实际中,不同用户在空间位置上的时空分布绝对值是不同的,即 $f({w_j},{l_i})$ $d({w_j},{l_i})$ 具有显著的差异性,以此为基础,提出社群内用户移动活跃度的概念.

定义:移动活跃度。移动活跃度是相对于移动行为特征分布而言的,在本质上移动行为特征属于相对值,而移动活跃度属于绝对值. 定义移动活跃度为用户 ${w_j}$ 在不同空间位置上的累计访问频次与停留时长的乘积,表示为

$a({w_j},l) = \sum\limits_{i = 1}^q \,{f({w_j},{l_i})} \times \sum\limits_{i = 1}^q \,{d({w_j},{l_i})} .$ (2)

定义:移动时空社群。给定离散时间间隔 ${c_i}$ 以及用户集合 $W$ 的历史移动轨迹数据集 $R$ ,基于不同用户在时间间隔 ${c_i}$ 以及不同空间位置上的移动行为特征计算,将用户集合划分为有限个社群:

$P = \{ {p_1},{p_1},{p_2},\cdots,{p_k}\}. $

其中, ${p_i} = ({w_{i1}},{w_{i2}},\cdots,{w_{ix}})$ ${w_{ij}}$ 对应第 $i$ 个划分社群 ${p_i}$ ,且同一社群内的参与用户具有相似的移动行为特征分布,不同社群内的用户具有不同的移动行为特征分布.

下面将对移动时空社群的划分过程进行详细地阐述. 利用移动行为特征计算公式,可得出每一个参与用户对于不同空间位置的偏好特征值 $o({w_j},{l_i})$ ,逐一对用户 ${w_j}$ 在不同空间位置 ${l_i}$ ( $1 \leqslant i \leqslant q$ )计算特征值,并将所得到的偏好值以矩阵的形式表示为如下形式:

${M} = \left[ {\begin{array}{*{20}{c}} {{m_{11}}}&{{m_{12}}}& \ldots &{{m_{1q}}} \\ {{m_{21}}}&{{m_{22}}}& \ldots &{{m_{2q}}} \\ \vdots & \vdots & {} & \vdots \\ {{m_{n1}}}&{{m_{n2}}}& \ldots &{{m_{nq}}} \end{array}} \right].$ (3)

其中, ${m_{j,i}} = o({w_j},{l_i})$ . 对于矩阵 ${{M}}$ 的任意2行矢量进行基于余弦相似度的计算,具体公式如下:

$\cos {\theta _{j1,j2}} = \frac{{\displaystyle\sum\limits_{i = 1}^n \,{\left(o({w_{j1}},{l_i}) \times o({w_{j2}},{l_i})\right)} }}{{\sqrt {\displaystyle\sum\limits_{i = 1}^n \,{\left(o{{({w_{j1}},{l_i})}^2}\right)} } \times \sqrt {\displaystyle\sum\limits_{i = 1}^n \,{\left(o{{({w_{j2}},{l_i})}^2}\right)} } }}.$ (4)

其中, $\cos {\theta _{j1,j2}}$ 表示用户 ${w_{j1}}$ ${w_{j2}}$ 在所有空间位置上基于移动行为特征分布的相似度. 以该相似度值为基础,利用 $k$ 均值聚类算法对上述 $n$ 个参与用户进行社群划分,最终得到 $k$ 个不同的移动社群 $P $ . 如上所述,在每一个划分的移动社群 ${p_k}$ 中利用移动活跃度计算确定唯一的社群组织者作为与MCS平台的任务接收与数据上传的终端超级用户,同时作为所在社群内不同用户从属者之间的任务协调者. 对于所划分的社群在空间位置上的偏好映射,本文以社群内所有用户的空间偏好矢量值的平均值表征社群对空间位置的偏好,以间接达到利用社群对空间位置进行分组的目的. 即若社群结构为 ${p_k} = \{ {w_{i1}},{w_{i2}}, \,\cdots,\,{w_{ip}}\} $ ,则社群对空间位置的偏好 $\mu ({p_k},l)$ 表示为

$\begin{split} \mu ({p_k},l) =&\frac{1}{p}\sum\limits_{x = i1}^{ip} \,{{V}({w_x},l)}=\\&\frac{1}{p}\sum\limits_{x = i1}^{ip} \,{\left[ o({w_x},{l_1}),\,\cdots,\,o({w_x},{l_n})\right] }.\end{split} $ (5)
3 移动群智感知社群化任务分发 3. 1 概率性随机分发策略

通过对传统群智感知任务的分发流程分析可知,这一模式大多是建立在对用户未来行为的统计性认识的基础之上,进而以统计性概率值进行排序操作,按照从高到低的顺序依次选择相应的参与用户执行给定任务. 尽管基于历史数据所发掘的行为统计规律具有一定程度上的稳定性,不可忽视身处复杂社会环境下的移动用户其行为往往具有很大的随机性、突发性与不确定性,这些特征对于确定性的传统任务分发的稳健运行构成了潜在的威胁. 此外,移动群智感知中的用户组织结构松散与参与自发等特点又进一步强化了用户随机性行为对于群智感知平台运行的不利影响,使得移动群智感知平台的脆弱性进一步加深. 可以说,移动群智感知用户行为特征模式具有天然的不确定特征,而传统的任务分发模式其本质却为使用稳定的、确定性的计算方法去预测、匹配不确定的行为模式,这本身就是矛盾的. 为此,考虑使用不确定的分发机制以随机生成概率进行任务的分发.

3. 2 感知任务的初次分发

感知任务的初次分发指MCS平台根据给定任务的空间属性,以所划分社群对空间位置的偏好 $\mu ({p_k},l)$ 为依据将任务分派给特定社群(社群组织者). 按照上述概率性随机分发策略,对于给定MCS任务 ${t_i} = < {l_i},{c_i} > $ ,以时间间隔 ${c_i}$ 对所有可用参与用户进行动态社群划分过程,得到 $k$ 个划分结果 $P = \{ {p_1},{p_2},\cdots,{p_k}\} $ . 对于每个社群 ${p_x}$ 计算其相对于空间位置 ${l_i}$ 的偏好相对程度 ${\mu '}({p_x},{l_i})$

${\mu '}({p_x},\,{l_i}) = {\mu ({p_x},\,{l_i})}\left/{{\displaystyle\sum\limits_{x = 1}^k \;{\mu ({p_x},\,{l_i})} }}\right..$ (6)

按照 $k$ 个社群对于位置 ${l_i}$ 的偏好 ${\mu '}({p_x},{l_i})$ 以随机概率产生的方式确定任务执行的社群. 先将所有偏好值进行归一化处理,

$\sum\limits_{x = 1}^k \;{{\mu '}({p_x},\,{l_i})} = 1,$

依次将每个社群的偏好值进行[0, 1]区间排列,进而在[0, 1]区间生成随机数,若该随机数落在第 $x$ 个社群的偏好值范围内,则选择 ${p_x}$ 作为该任务的执行社群,同时将该任务分发给选定社群的组织者. 为了保障感知数据的真实性,本文采用通用的冗余采样方式,将同一任务独立分发给不同的 $g$ 个社群执行(独立重复上述过程 $g$ 次,若产生相同社群,则继续该过程直至产生不同的 $g$ 个社群为止),最后将 $g$ 个社群的感知结果进行组合验证产生最终结果.

3. 3 感知任务的二次分发

当平台将任务 $t$ 分发给社群 ${p_x}$ ,在社群内部社群组织者按照社群从属者用户对于给定任务空间的活跃度以及与其社交亲密度确定具体的任务执行者,其中活跃度保证所选择的具体任务执行者对于给定任务区域具有较高的访问概率,后者保证具体任务执行者在任务结果数据回收阶段有较大概率与组织者相遇. 需要注意的是,以社交亲密度确定具体的任务执行者,并非意味着社群组织者与执行者之间直接社交连接,有可能社群组织者与执行者通过若干个中间节点构成社交连接.

定义:社交亲密度。社交亲密度是量化移动社交网络环境中,不同参与用户基于时空维度上的共处现象而形成的一种亲近程度刻画,定义为

$\begin{split} \lambda ({w_x},w{}_y) = & \frac{{\displaystyle\sum\limits_{i = 1}^q \,{f({w_x},\,{l_i}) \cap f({w_y},\,{l_i})} }}{{\displaystyle\sum\limits_{i = 1}^q \,{f({w_x},\,{l_i})} + \displaystyle\sum\limits_{i = 1}^q \,{f({w_y},\,{l_i})} }} \times\\ &\frac{{\displaystyle\sum\limits_{i = 1}^q \,{d({w_x},\,{l_i}) \cap d({w_y},\,{l_i})} }}{{\displaystyle\sum\limits_{i = 1}^q \,{d({w_x},\,{l_i})} + \displaystyle\sum\limits_{i = 1}^q \,{d({w_y},\,{l_i})} }}.\end{split} $ (7)

式中: $\displaystyle\sum\limits_{i = 1}^q \,{f({w_x},\,{l_i}) \cap f({w_y},\,{l_i})} $ 表示用户 ${w_x}$ 与用户 ${w_y}$ 共处的频次, $\displaystyle\sum\limits_{i = 1}^q \,{d({w_x},\,{l_i}) \cap d({w_y},\,{l_i})} $ 表示用户 ${w_x}$ 与用户 ${w_y}$ 共处的时长. 相应地,具体的执行者适应度计算过程可表示为

$\varphi ({w_x},\,{t_i}) = \alpha \times a({w_x},\,{l_i}) + (1 - \alpha ) \times \lambda ({w_x},\,{w_y}).$ (8)

式中:参数 $\alpha $ 为对活跃度以及亲密度指标的折中加权,本文取 $\alpha $ =0.5; ${w_y}$ 为社群的组织者.

在群智感知任务执行阶段,若选定的执行者任务失败,执行者可选择其将信息告知社群组织者,由组织者重新在当前社群中(剔除该执行者),按照上述流程选择新的任务执行者;或是在移动社交网络中选择亲密度最高的用户进行任务信息传递,由该亲密度最高的用户替补完成感知任务,并将任务信息移交给该亲密度最高者所在的社群. 在数据回收阶段,任务执行者按照数据规模的大小选择3G/4G网络进行直接通信或是机会式短距离通信. 下面给出移动群智感知社群化任务分发算法.

算法1 移动群智感知社群化任务分发算法.

输入: $W = \{ {w_1},{w_2},\cdots,{w_n}\} $

$R = < {l_j},{c_j},{d_j} > $ $T = \{ {t_1},{t_2},\cdots,{t_m}\} $

输出:Optimal User Subset ${W^*}$

FOR EACH ${w_i} \in W$ DO

Compute Mobility Distribution ${{V}}({w_i},l)$

Compute Mobility Activeness $a({w_i},l)$

END FOR

Cluster Users $P = \{ {p_1},{p_2},\cdots,{p_k}\} $

First Allocate Tasks to Clusters Based on $\mu ({p_k},l)$

Determine User for Specific Tasks by fitness

4 实验结果及分析

本文将WTD公开数据集作为实验数据,该数据集记录了加州大学圣地亚哥分校校园内275个携带PDA(personal digital assistant)设备的用户与部署的AP间约11周的通信数据. 利用该数据集对所提出的面向移动社交网络的群智感知社群化任务分发方式进行性能验证. 由于WTD数据集中不同用户数据的稀疏性,本次实验选择其中140个AP节点作为空间位置,选取其中68个用户作为参与用户. 首先对移动社群行为特征分布以及基于亲密度的用户连接网络进行实验测试,其中参数 $k$ 取值为9,具体结果分别如图23所示,图2中的横轴与纵轴分别表示AP空间位置 $L$ 以及相应的参与用户 $W$ .

图 2 社群移动行为特征分布 Fig. 2 Community mobile behavior characteristic distribution
图 3 基于亲密度的社交连接网络 Fig. 3 Social connectivity network based on intimacy

分别对任务执行效果、任务分发次数以及任务回收能耗进行测试,随机产生100 ~ 400个移动群智感知任务,感知任务的空间位置随机从140个AP点选取,时间间隔从0:00—24:00随机选取. 相关参数的设置具如下:用户以概率0.3执行任务失败,以概率0.5社群组织者重新选择新的执行者,以概率值0.5通过社交网络传递任务;在传递任务的情况下,被传递者以其亲密度为概率值执行任务或是拒绝执行任务,在任务结果回收过程中,将通过直接网络数据传输能耗系数设置为1,将通过机会式网络进行数据传输能耗设置为0.4. 由于现有任务分发工作缺乏对于任务执行过程的干预,以传统任务分发模式为基础,构建基准算法(baseline algorithm),流程如下:基于用户的历史移动时空行为特征构建预测模型以预测其在未来某个时间段访问给定空间位置的概率,按照概率值的大小排序,选择 $g$ 个用户作为任务的执行者( $g = 3$ ),在任务的执行过程中若发生执行失败情况,则平台按照上述概率值排序依次选择新的用户作为感知任务执行者,对于同一任务若连续选择3次执行者均失败,则将该任务作为失效任务不再进行分发.

图4显示了随机分发策略与传统的排序分发策略的比较实验,以及任务执行失败后不同的干预策略实验,N为群智感知任务数,Z为任务完成率. 其中随机分发策略与传统的排序分发策略的比较实验中未对失败任务进行用户的替补重选,如果选定的用户在第2天相应的时间间隔未出现在任务指定的空间区域则意味着该分发任务执行失败。由图中可以看出,本文所提出的随机分发策略显著优于传统的排序分发策略,且分别在100~400个MCS任务情况下均性能稳定. 任务执行失败后不同的干预策略实验中所列举的3种策略分别为所提出的社群式分发—失败用户社群内替补、社群式分发—基于社交关系的亲密度用户传递、传统“平台—用户”的全部用户重新选取。由图中可见,社群式分发—基于社交关系的亲密度用户传递策略任务完成率最高,其次为社群式分发—失败用户社群内替补策略以及传统“平台—用户”的全部用户重新选取策略. 需要注意的是,由于WTD数据分布非常稀疏,极少数AP位置(图书馆、宿舍)集中了大量的位置数据,同时极少数超级活跃用户贡献了大量的数据,实验验证的任务完成率总体数值较低,但该值对于不同算法的性能评测无影响.

图 4 MCS 任务分发实验I Fig. 4 Task allocation experiment I in MCS

图5所示为任务执行失败干预实验下任务的分发次数统计结果,感知数据回收能耗仿真实验结果,其中B为任务分发次数,U为能耗统计,N为任务数. 失败干预实验下任务的分发次数统计结果显示社群式分发—基于社交关系的亲密度用户传递分发次数最少,依次是社群式分发—失败用户社群内替补、传统“平台—用户”的全部用户重新选取. 原因在于基于社交关系亲密度的用户传递分发具有较高的任务接收与执行率,在上述实验之外,同时进行模拟真实校园环境的问卷调查统计,通过对97名在校生的统计显示,约89.73%的受访者在接到关系亲密的好友任务请求时会接受并完成该任务,这一数据与WTD实验测试结果基本相符. 失败用户社群内替补优于传统“平台—用户”的全部用户重新选取的原因在于基于时空移动行为的动态社群划分将具有相近移动行为的用户进行聚类划分,因此可以在相对较小的可选用户范围内搜寻合适的用户进行替补执行. 感知数据回收能耗仿真实验结果显示失败用户社群内替补策略最优,依次为基于社交关系的亲密度用户传递分发、传统“平台—用户”的全部用户重新选取. 原因在于社群内替补策略最优在最大程度上利用机会式移动社交网进行短距离通信,因此能耗最少,而基于社交关系的亲密度用户传递分发次之,传统“平台—用户”的全部用户重新选取全部采用3G/4G通信方式进行数据上传/下载,其能耗最高.

图 5 MCS 任务分发实验 II Fig. 5 Task allocation experiment II in MCS

表1所示为图5中MCS执行失败干预实验的任务平均执行时间的对应结果. 结果显示:基于社交关系传递的分发策略任务执行效率最高,其次为社群内替补策略以及直接重发策略. 3种策略的任务平均执行时间大致为1.335、1.475、1.595 s,该结果与图5中的实验结果基本一致。

表 1 MCS任务平均执行时间 Table 1 Task’s average execution time in MCS s
5 结 语

本文针对现有移动群智感知任务分发平台在任务执行鲁棒性、过程监督与干预性以及感知结果数据的回收方面存在的不足与缺陷,提出了一种面向移动社会网络的群智感知社群化任务分发模式。考虑具体的移动群智感知应用场景,设计了相应的社群化任务分发的具体方法,包括时空限定条件下的参与用户动态社群划分,基于移动活跃度与社交网络亲密度的任务执行用户选择。对真实数据集的实验验证结果显示,本文所设计的社群式移动群智感知任务分发方法可有效克服上述不足,同时具有较强的适用性与有效性.

参考文献
[1]
GANTI R, YE F, LEI H. Mobile crowdsensing: current state and future challenges[J]. IEEE Communications Magazine, 2011, 49(11): 32-39. DOI:10.1109/MCOM.2011.6069707
[2]
NI J, ZHANG A, LIN X. Security, privacy, and fairness in fog-based vehicular crowdsensing[J]. IEEE Communications Magazine, 2017, 55(6): 146-152. DOI:10.1109/MCOM.2017.1600679
[3]
GUO B, YU Z, ZHOU X, ZHANG D. From participatory sensing to Mobile Crowd Sensing [C] // 2014 IEEE International Conference on Pervasive Computing and Communications Workshops. Budapest: IEEE, 2014: 593-598.
[4]
WAN J, LIU J, SHAO Z, et al. Mobile crowd sensing for traffic prediction in internet of vehicles[J]. Sensors, 2016, 16(1): 88. DOI:10.3390/s16010088
[5]
LUDWING T, REUTER C, SIEBIGTEROTH T, et al. Crowdmonitor: mobile crowd sensing for assessing physical and digital activities of citizens during emergencies [C] // Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems. Seoul: ACM, 2015: 4083-4092.
[6]
GUO B, CHEN H, YU Z, et al. Fliermeet: cross-space public information reposting with mobile crowd sensing[J]. IEEE Transactions on Mobile Computing, 2015, 14(10): 2020-2033. DOI:10.1109/TMC.2014.2385097
[7]
XIAO M, WU J, HUANG L, et al. Online task assignment for crowdsensing in predictable mobile social networks[J]. IEEE Transactions on Mobile Computing, 2017, 16(8): 2306-2320. DOI:10.1109/TMC.2016.2616473
[8]
XIONG H, ZHANG D, CHEN G, et al. icrowd: near-optimal task allocation for piggyback crowdsensing[J]. IEEE Transactions on Mobile Computing, 2016, 15(8): 2010-2022. DOI:10.1109/TMC.2015.2483505
[9]
ZHENG Z, WU F, GAO X, et al. A budget feasible incentive mechanism for weighted coverage maximization in mobile crowdsensing[J]. IEEE Transactions on Mobile Computing, 2017, 16(9): 2392-2407. DOI:10.1109/TMC.2016.2632721
[10]
ZHENG L, CHEN L. Maximizing acceptance in rejection-aware spatial crowdsourcing [C] // 2017 IEEE 33rd International Conference on Data Engineering (ICDE). San Diego: IEEE, 2017: 71-78.
[11]
PERSAUD A, OBRIEN S. Quality and acceptance of crowdsourced translation of web content[J]. International Journal of Technology and Human Interaction, 2017, 13(1): 100-115.
[12]
LIU Y, GUO B, WANG Y, et al. Taskme: multi-task allocation in mobile crowd sensing [C] // Proceedings of the 2016 ACM International Joint Conference on Pervasive and Ubiquitous Computing. Heidelberg: ACM, 2016: 403-414.
[13]
HE S, SHIN D, ZHANG J, et al. Near-optimal allocation algorithms for location-dependent tasks in crowdsensing[J]. IEEE Transactions on Vehicular Technology, 2017, 66(4): 3392-3405. DOI:10.1109/TVT.2016.2592541
[14]
WANG E, YANG Y, WU J, et al. An efficient prediction-based user recruitment for mobile crowdsensing[J]. IEEE Transactions on Mobile Computing, 2018, 17(1): 16-28. DOI:10.1109/TMC.2017.2702613
[15]
CHEUNG M, HOU F, HUANG J. Make a difference: diversity-driven social mobile crowdsensing [C] // 2017 IEEE International Conference on Computer Communications. Atlanta: IEEE, 2017: 1-9.
[16]
LANE N, CHOU Y, ZHOU L, et al. Piggyback crowdSensing: energy efficient crowdsourcing of mobile sensor data by exploiting smartphone app opportunities [C] // Proceedings of the 11th ACM Conference on Embedded Networked Sensor Systems. Roma: ACM, 2013: 1-14.