论文阅读笔记|移动群智感知任务优化分发——基于移动模式匹配视角

2018 年 6 月 22 日 FCS

点击蓝字

关注我们

今天，FCS给大家分享一篇智慧城市与城市计算专栏论文——《Mobile crowd sensing task optimal allocation:a mobility pattern matching perspective（移动群智感知任务优化分发——基于移动模式匹配视角）》的读者给我们带来的论文阅读笔记。如果您也同样对这篇论文感兴趣，或者也想把您阅读我们期刊论文的感受分享给更多的小伙伴，欢迎在文后留言或者与我们联系。

原文信息：

Mobile crowd sensing task optimal allocation: a mobility pattern matching perspective

Frontiers of Computer Science,2018,12(2):231-244

Liang WANG, Zhiwen YU, Bin GUO, Fei YI, Fei XIONG

移动群智感知

移动群智感知（Modile CrowdSensing，简称MCS）是指通过利用嵌入在手机等设备中的传感器在人们移动过程中收集周围数据，这一技术随着大量嵌入传感器的移动设备的应用而得到了前所未有的发展。但如何确定执行收集任务的人选是一个关键性问题，这其中既要保证数据的可靠性，同时还要尽可能地控制成本。举个例子来说明这个问题：

如图1所示，现在有三个用户和五个任务，这五个任务分布在不同的空间里，假设不久会通过和，那么我们给他分配和是比较合理的，而实际上，把分配给从本质上来讲也是一个局部最优解，符合最近优先策略。但如果我们给他分配，他就必须调整原来的路线，很明显附近的红色虚线是他额外需要走的路线，这样他的任务成本就会提升，相应的任务发布方的成本预算也会提高，这是我们不希望看到的。因此，在分配感知任务时我们需要考虑收集者的移动模式。

表征移动模式

在现实生活中，人们的移动行为在某种程度上通常会表现出一种重复性规律，通过观察用户的移动记录，就可以统计和提取出每个人的移动规律。

建立重复性移动模型

首先定义一些概念来阐述移动规律性。观察用户移动轨迹的时间间隔被定义为观察周期P，它被划分为许多不重叠的周期，长度为，用户可能并不会在每个周期都出现，我们只需要考虑用户出现的周期，并将其称为有效周期，进一步，我们使用支持度来表示每个行为在所有有效周期中出现的周期数量。这样我们得到了如下的形式化定义：

如果一个行为在个时间周期中在用户原有的数据集内出现的次数不低于用户指定的阈值，那么它就是一个重复性移动模式。移动模式被定义为的形式，表示用户从地点移动到地点，这种行为在用户的个有效的时间周期中重复了sup次。

重复性移动模式的发现

对于每一个用户，我们首先建立一个包含其移动规律性的移动子空间Ω，然后对N个不重叠周期进行多次扫描，识别出该用户频繁访问的热点位置，这样，1长度的重复模式就记录好了，例如。然后，在上一轮中发现的移动模式被用来生成新的候选重复模式。通过和一个给定的最小支持度阈值minsup进行比较，我们可以确定哪一个候选重复模式是真正的移动模式。当一次遍历结束后没有移动模式，或者不能生成新的候选重复模式时，整个发现过程结束。

有了移动模式之后需要进行的就是基于模式匹配的任务分配了。

基于模式匹配的MCS任务分配

问题描述

移动用户被定义为集合，需要完成的感知任务被定义为集合，其中表示任务的地理位置是，发布时间是。

根据发现的用户移动模式，MCS平台希望把任务分配给合适的用户，目标是最小化感知成本和最大化数据质量。在该优化问题中同时存在着两个限制条件：用户的能力有限，需要给每个用户限制一个最大工作量，为了简化问题，在本文中设定为常数g；为了保证数据可靠性，对于每个任务收集不止一个样本，在本文中，我们假设每一份任务需要收集个独立测量结果来确保感知质量。

对于移动用户，假设分配给他的感知任务为，报酬为，收集到的数据质量被定义为任务覆盖度，也就是用户访问的概率，对于用户而言，分配的任务的覆盖度被定义为，等于移动模式的支持度sup。

这样，问题就可以被公式化地定义如下：

问题转换

根据经济学中的规模效应，如果用户被分配的任务越多，那么每个任务的成本则会相应地下降，换句话说，这相当于要实现和移动模式匹配更长的任务序列分配，但是规模过大也有可能导致信息失真，因为长移动模式相比较于短移动模式的重复率要低，这将体现在支持度这个指标上。我们可以将原来的优化目标转换为另一种形式：

其中，和分别表示分配给用户的感知任务和他的重复性移动模式之间的匹配长度和匹配支持度。

最优化任务分配方案

（1）分配方案结构

对于一个给定的MCS感知任务集合，我们采用一个矩阵结构来记录和更新任务分配方案。

其中，行数代表了参与方用户的数量，列数代表了要被分配的任务数量。如果

，

意味着任务

被分配给了用户

；否则反之。第i行的元素总和代表了分配给用户

的任务量（

），第j列的元素总和代表了任务

的独立测量数（

）。通过这种计算，很容易验证上述优化目标的约束条件是否得到满足。

（2）任务分配流程

本文提出了基于贪心的迭代算法来导出期望的解决方案。在每一轮分配迭代中，首先选择任务的一个子集

，其中每一个任务都只有一个独立的测量。然后，在发现的重复性移动模式中搜寻和

中的任务序列相匹配的模式，如果

中的任务被一个模式部分或者全部地匹配，那么我们就说可以被这种模式匹配，在和mp中共享的元素数量被认为是匹配长度matlg。对于一个给定的任务集，可能会有多个移动模式和其匹配，但它们的匹配长度和支持度是不同的，为了在这两个指标中做出一个权衡，本文提出了四种策略选出一个评估值最大的模式，该模式所对应的用户将会被分配给共享的相应任务。中在这一轮迭代中没有被分配出去的任务将会返回到原始的任务集T中。与此同时，被分配出去的任务的独立测量数将会减一，如果任务的独立测量数变成0，我们就把从T中剔除。对于参与方用户而言，如果任务被分配给了用户，我们就把矩阵ATU中的项置为1。如果用户被分配的任务量达到了上界g，他的移动模式将会从候选模式集中剔除。重复这个分配过程直到任务集T中不存在任务。整个任务分配流程如图2所示。

（3）任务分配策略

基于匹配长度（）和支持度（）这两个指标，如何比较不同匹配模式对于任务集的合适度是任务分配框架的关键问题，本文设计了不同的评估策略来指导任务分配过程。

①匹配长度优先（MLP）

匹配长度（matlg）优先，matlg值更大的模式的匹配程度将会更高，换句话说，这种策略只考虑最小化感知成本预算这个目标，不考虑任务覆盖度指数。

②匹配度优先（MDP）

这种策略和MLP截然相反。这种策略的关注点放在了覆盖度指数上，因此一个有着更大匹配支持度（matdg）的模式将更有可能被使用。

③综合考虑-1（IU1）

这种策略会同时考虑两种优化目标，我们将覆盖度作为一个预先确定的阈值来优化感知成本目标。对于任何两个匹配模式而言，任何一个的matdg值如果小于阈值∂就会被排除。如果这两个候选模式的支持值都大于∂，那么有着更大匹配长度（matlg）的就模式将会被选为最终分配方案。

④综合考虑-2（IU2）

和上一种策略相似，这种策略也综合考虑两个优化目标，它使用matlg*matdg这个优化指标，有着最大的matlg*matdg值的候选模式将被选为最终分配方案。

实验效果

数据集

本文使用由UCSD的研究人员发布的公开WTD数据集作为实验数据集。由于数据集的分布比较稀疏，通过对于数据的过滤得到了一个包含124个接入点和68个用户的真实数据集。为了在一个更大规模数据集上更加全面地验证我们提出的方案，我们根据实际数据拟合出了一套模拟数据集，又额外增加了100个虚拟移动用户，即有168个用户，并且相关的接入点也增加到了284。

实验结果

本文从更改感知任务数、更改最大工作量、任务分配效率、任务完成比率四个角度分别对上述四种策略进行了比较和评估。在每个用户平均分配的任务数上MLP最优，而在每个任务的平均覆盖度上MDP最优，IU1和IU2介于上述二者之间。在任务分配效率上MLP最优，因为它采用的是最长模式匹配策略，在每一轮迭代中可以给一个用户分配尽可能多的任务。而在任务完成率上，MDP表现最佳，因为对于移动预测的准确性将会直接影响任务的完成度，其他更为详细的实验结果，请参考原文。

长按识别二维码，阅读文章详情

总结

本文在MCS任务分配问题上提出了参考用户移动模式的假设，将用户移动模式和分配任务序列进行匹配，在数据可靠性和成本可控性两个指标的权衡上提出了四种策略，并通过具体实验证明了其方案的有效性。

注：本文为该读者的阅读笔记，未经原论文作者和FCS期刊审读。仅供广大读者参考。

了解原论文内容，请点击下方链接：

FCS 12(2) 智慧城市与城市计算专栏 | 移动群智感知任务优化分发——基于移动模式匹配视角

Frontiers of Computer Science

期刊封面_icon.jpg Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社出版、SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，双月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为李未院士，执行主编为熊璋教授和周志华教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”。