2. 西安科技大学 电气与控制工程学院, 陕西 西安 710054;
3. 北京交通大学 电子信息工程学院, 北京 100044
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
随着用户手持移动智能设备的日益普及以及无线通信网络技术的不断发展,通过移动用户有意识或无意识的协同参与,利用移动智能设备各种内置传感器(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 问题定义给定
移动群智感知平台接收任务发布者所发布的MCS任务集合
考虑一个具体的MCS应用场景,在校园环境中需要寻找下午17:00—19:00期间使用率最低的某一个或几个教室,可用参与用户为在应用平台上注册且状态有效的全部用户. 为了实现精准化的任务分发过程,平台要求用户在不影响个人隐私的前提下提供有限日期的历史移动轨迹数据,作为平台分析用户内在移动行为规律的依据. 在移动社交网络环境下,社群化任务分发需要首先统计所有用户历史数据在给定时间间隔(17:00—19:00)内的移动行为特征
基于不同移动社群所表征的空间位置偏好,MCS平台将不同的空间感知任务初次分发给相应的社群(社群组织者). 社群组织者参照所在社群内部从属者对于相应空间位置的偏好程度、活跃程度以及与社群组织者之间的社交亲密度,以一种随机生成概率方式将任务二次分发给特定的用户进行感知任务的执行. 在任务执行过程中,若选定用户由于现实因素无法继续执行所分派的任务,则其可通知所在社群的组织者重新选择任务执行者,或是利用移动社交网络将该任务传递给高亲密度社交用户(好友)委派其代为执行感知任务. 在感知结果的回收过程中,利用移动社交网络的机会式通信方式,感知结果将由源节点(任务执行者)通过单跳或是多跳方式传递给社群组织者,再由社群组织者将结果进行初步统计发送给MCS平台. 整个方案的流程如下图1所示.
![]() |
图 1 移动群智感知社群化任务分发流程图 Fig. 1 Flow of socialization task distribution in mobile crowd sensing |
定义:移动行为特征。移动行为特征反映用户在给定时间间隔内,在不同空间位置上的移动时空行为分布特征. 本文选择用户的空间出现频次与停留时间长度作为移动行为特征的刻画,具体的公式可表示为
$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) |
式中:
${V}({w_j},l\,) = (o\,({w_j},{l_1}),o({w_j},{l_2}),\cdots,o({w_j},{l_q})).$ |
在移动用户社群划分过程中所使用的移动行为特征分布属于相对值计算. 换句话说特征分布刻画的是用户对不同空间位置的“偏好程度”. 在实际中,不同用户在空间位置上的时空分布绝对值是不同的,即
定义:移动活跃度。移动活跃度是相对于移动行为特征分布而言的,在本质上移动行为特征属于相对值,而移动活跃度属于绝对值. 定义移动活跃度为用户
$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) |
定义:移动时空社群。给定离散时间间隔
$P = \{ {p_1},{p_1},{p_2},\cdots,{p_k}\}. $ |
其中,
下面将对移动时空社群的划分过程进行详细地阐述. 利用移动行为特征计算公式,可得出每一个参与用户对于不同空间位置的偏好特征值
${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) |
其中,
$\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) |
其中,
$\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. 2 感知任务的初次分发感知任务的初次分发指MCS平台根据给定任务的空间属性,以所划分社群对空间位置的偏好
${\mu '}({p_x},\,{l_i}) = {\mu ({p_x},\,{l_i})}\left/{{\displaystyle\sum\limits_{x = 1}^k \;{\mu ({p_x},\,{l_i})} }}\right..$ | (6) |
按照
$\sum\limits_{x = 1}^k \;{{\mu '}({p_x},\,{l_i})} = 1,$ |
依次将每个社群的偏好值进行[0, 1]区间排列,进而在[0, 1]区间生成随机数,若该随机数落在第
当平台将任务
定义:社交亲密度。社交亲密度是量化移动社交网络环境中,不同参与用户基于时空维度上的共处现象而形成的一种亲近程度刻画,定义为
$\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) |
式中:
$\varphi ({w_x},\,{t_i}) = \alpha \times a({w_x},\,{l_i}) + (1 - \alpha ) \times \lambda ({w_x},\,{w_y}).$ | (8) |
式中:参数
在群智感知任务执行阶段,若选定的执行者任务失败,执行者可选择其将信息告知社群组织者,由组织者重新在当前社群中(剔除该执行者),按照上述流程选择新的任务执行者;或是在移动社交网络中选择亲密度最高的用户进行任务信息传递,由该亲密度最高的用户替补完成感知任务,并将任务信息移交给该亲密度最高者所在的社群. 在数据回收阶段,任务执行者按照数据规模的大小选择3G/4G网络进行直接通信或是机会式短距离通信. 下面给出移动群智感知社群化任务分发算法.
算法1 移动群智感知社群化任务分发算法.
输入:
输出:Optimal User Subset
FOR EACH
Compute Mobility Distribution
Compute Mobility Activeness
END FOR
Cluster Users
First Allocate Tasks to Clusters Based on
Determine User for Specific Tasks by fitness
4 实验结果及分析本文将WTD公开数据集作为实验数据,该数据集记录了加州大学圣地亚哥分校校园内275个携带PDA(personal digital assistant)设备的用户与部署的AP间约11周的通信数据. 利用该数据集对所提出的面向移动社交网络的群智感知社群化任务分发方式进行性能验证. 由于WTD数据集中不同用户数据的稀疏性,本次实验选择其中140个AP节点作为空间位置,选取其中68个用户作为参与用户. 首先对移动社群行为特征分布以及基于亲密度的用户连接网络进行实验测试,其中参数
![]() |
图 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),流程如下:基于用户的历史移动时空行为特征构建预测模型以预测其在未来某个时间段访问给定空间位置的概率,按照概率值的大小排序,选择
图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 |
本文针对现有移动群智感知任务分发平台在任务执行鲁棒性、过程监督与干预性以及感知结果数据的回收方面存在的不足与缺陷,提出了一种面向移动社会网络的群智感知社群化任务分发模式。考虑具体的移动群智感知应用场景,设计了相应的社群化任务分发的具体方法,包括时空限定条件下的参与用户动态社群划分,基于移动活跃度与社交网络亲密度的任务执行用户选择。对真实数据集的实验验证结果显示,本文所设计的社群式移动群智感知任务分发方法可有效克服上述不足,同时具有较强的适用性与有效性.
[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.
|