群智感知中面向移动群体的参与者选择优化模型

蒋伟进 吕斯健 陈晓红

(1.湖南工商大学计算机与信息工程学院,湖南长沙 410205;2.新零售虚拟现实技术湖南省重点实验室,湖南长沙 410205)

1 引言

群智协同计算作为当前的研究热点之一,与多个学科领域都有所交叉.在这其中,移动群智感知作为协同计算、普适计算的前期数据获取步骤,更是已经成为了普适计算领域的首要研究问题.在移动群智感知(sparse mobile crowdsensing)[1]过程中,其主要依赖当前大量用户所拥有的智能手机、智能手表等智能设备上的多元传感器来完成针对大规模数据[2]的群智感知任务,例如交通情况检测、自然气候以及植物生长状态的收集等等.因此,一个通用的移动群智感知方法对于感知的实现、数据的收集就显得尤为重要.在当前已有的系统平台中,例如e-Bird、CrowdFlower,即使是在这些用户量较大的群智计算平台中,也依然是由数据需求者发布任务要求,用户自行在平台上选择任务的模式.依然无法做到平台根据任务属性以及用户行为[3]自主进行任务分配.

在城市基础设施中,可以发现地铁轨道交通网络作为一种已经规划好的城市覆盖资源,其建立的目的就是为了实现对城市市区热点地区范围的覆盖,并且地铁还是大多数市民的首选出行通勤方式.完整的城区覆盖面积以及长期大量的客流都恰好可以满足移动群智感知、群智计算的硬性需求.并且地铁Wi-Fi的覆盖以及地铁服务人群的出行规律性,也可以满足任务分发的速率、时间需求以及任务分发准确度的保证.Liu[4]等人通过了对部分站台停留乘客的手机使用情况以及轨迹跟踪,实现了针对市区内的城市交通监测.在相同或邻近地铁车厢中的乘客,大多可以在一段时间内维持一个持续且稳定的接触时间[5],使得任务信息可以在该车厢内用户之间进行传输.并且用户节点之间的接触时间也可以通过不同站点之间的已知的停留间隔进行预测.这些特点使得基于地铁交通的移动群智感知任务分发模型具有相比传统机会网络[6]分发模型更高的分发率和传输质量.地铁站点任务分配示例见图1.

图1 地铁站点任务分配示例Fig.1 Example of task assignment at a subway station

本文针对这两个用户选择的相关优化因素,分别提出:以参与者个数为约束,将用户激励成本(移动距离)作为优化目标的OCTDM(optimize cost task distribution model)算法;以用户激励成本(移动距离)为约束,将参与任务用户数量作为优化目标的ONPTDM(optimize number of people task distribution model)算法.并且通过长沙市地铁运营数据集、酒店数据集对设计的两种参与者选择算法进行试验评估,通过对用户移动距离、参与者数量等实验结果的比对,选择出在不同情况下代价最低的算法.

2 相关工作

人工智能技术的迅速发展催使大数据需求的日益增长,移动群智感知作为一种更为高效全面的数据收集方式[7],可以以多种方式实现大部分多源、异构数据的主动收集.Wei等人[8]对群体智能这一概念进行了深入的说明,并对其中的相关技术、工作流程、数据分析做出了较为详细的介绍.Pietro等人[9]认为群智协同计算这一全新的计算模式是为了更好的通过结合协同计算和人工智能[10]技术,解决群智资源的有效管理和协同利用这一问题而诞生的,通过利用各种形式的群体智能来实现问题的求解.在这其中,多任务的被动分发问题也可以看作是用户、参与者集合的主动选择问题,即如何通过现有资源(任务与参与者的时空位置、用户历史任务完成情况、参与者之间的社交关系等),找出各组任务中最为适合的参与者集合.所以当前移动群智感知的任务分发方式大致可以分为:基于用户社交关系的任务分发方法和基于任务时空位置的任务分发方法两种.

在移动群智感知参与者的选择问题中,参与者对任务的熟悉情况、参与者集合之间的社交关系以及距离都会对任务的分发进度、完成质量、完成速度造成一定的影响.例如:将某类任务继续分发给熟悉或曾经完成此类任务质量较高的参与者,任务的完成质量会比随机分发给对此类任务不熟悉的参与者更高.若任务分发给一个相互熟悉的团体,完成任务时的参与者集合内的信息沟通效率会更高,完成任务的过程也会对团队产生社交激励的作用.Hosseini等人[11]对众包的四个基本概念进行了解释,包括参与者,众包,众包任务以及众包平台.Xiong等人[12]针对移动群智感知中的隐私保护措施进行了分析,提出了一种基于布隆过滤器的用户联盟匹配隐私保护方案.Gionis等人[13]在群智感知任务分发过程中,提出了通过在现有社交网络关系的对任务参与者进行查询,在其中建立密集连通子图寻找社交关系权重较大的、符合任务完成条件的参与者集合.并且本方法除了对在线社交关系进行了查询,还考虑了参与者之间的时空位置关系,曾经参与任务状态等信息.使得寻找到的团体在关系密切的基础上,地理位置距离也相对较近,或在任务完成范围内.

综上,当前大多数感知任务分发方法都是基于部分社交或时空位置的约束条件和激励方式所实现的.对于多任务分发的方法和研究依然较少,对于任务分配过程中的具体任务信息、任务所属区域、任务分发时间等影响因素[14]依然考虑较少.为此,本文在现有城市地铁轨道交通的基础上,提出了面向乘客扩散的多任务动态分发方法对参与者选择问题进行优化.并基于这一问题提出两种具有不同侧重点的优化约束算法,以期相比传统算法,进一步的优化用户移动距离,最小化完成任务需要的参与者数量,降低系统激励成本.

3 参与者选择方法

参与者选择优化模型主要由感知任务的收集、任务的分发以及任务的执行3个部分组成.

3.1 群智感知的需求

在移动群智感知平台中,数据收集者所发布的任务大概可以分为两种,一种是时间期限比较宽泛,时效性没那么强,大致在一周两周内完成都可以,例如查看某地点的商家是否还存在,查看某地区植物生长状况是否需要修剪.对于这种任务,参与者只需要方便时,路过任务地点顺便完成任务即可.这类感知任务群智平台在接收到后可在系统压力较小时进行参与者的选择以及任务的分发,对应的任务激励代价和系统资源消耗都较小.另一类任务会有较短的时间限制,具有所需感知的任务数据具有一定的时效性,过了一段时间数据的价值会急剧下降,变为无用数据.所以需要系统立即在时限内对感知任务进行分发,对参与者进行选择.例如时效性较高的路面交通状况,危机险情的一线情况等.并且在事件发生时,这类任务的数据需求可能在短时间内大量涌现,所以可能会出现系统可调配参与者供不应求的需求场景.所以在此引入多任务[15]分发机制就可以适当减缓系统和参与者压力,当系统出现用户资源不足时,系统可根据任务的紧急程度、通过根据任务属性位置分析相似任务、参与者之间的关系属性,对任务和参与者进行一定的组合分发.将类似任务打包合并分发处理,以达到降低系统任务分发压力的效果.

3.2 参与者的选择

在基于地铁的多任务分发方法中,分发系统主要包括用户节点和列车车厢,在每个站点,乘客会进入到列车车厢这一个封闭的载体中.任务信息将通过列车Wi-Fi或者用户手机的蓝牙进行传输,在这个封闭区间中任务可以进行稳定持续的传输分发.当到达站点时,用户节点都有可能离开、加入也有可能保持不变,从这个角度看列车内节点又是一个动态分发的过程.

3.2.1 移动群体中的参与者选择

首先,当群智感知系统收到数据需求者的感知任务后,会根据所有感知目标的时空位置分布,对其中同类的任务通过密度聚类算法以划分范围内站点间距为大小限制进行聚类划分.每个同类任务区域都将产生一个任务聚类中心.其次,系统将会根据每一地铁站点和聚类中心的距离,为其分配最近的任务子区域,以到达通过市区地铁轨道交通[16]对任务区域进行覆盖的目的.并且预测每一用户节点的可能下车站点,在车厢内为其分发该下车站点附近的任务子区域的相关任务集合.最后,系统将会依此进行多任务分发,通过车厢内的移动Wi-Fi或者用户之间的蓝牙进行传输扩散,如图2.

图2 多任务分发方法Fig.2 Multi-task distribution method

由于公共交通线路的固定性和稳定性,公共交通的出行方式成为了人们日常通勤的首要选择,并且由于通勤目的地和出发地的固定性,使得在工作日公交系统中存在规律性的用户出行线路[17-18].所以,用户节点的下车位置则可以通过乘客的历史出行乘车记录进行预测推断,以预测可信度作为选择参与者的依据.地铁乘客的日常出行规划路径[19]都是主要集中在几个习惯性站点或路线,并且和时间节日都具有一定的相关性.所以只需要对参与者的部分历史出行记录进行分析,以预测可信度作为权重,即可对用户可能的下车站点进行覆盖.例如:可对用户在一段时间内的出行情况进行分析,例如早上、下午、反复出行的周期性路线和站点.通过机器学习等手段均可对此进行分析预测,并且准确度十分高.当用户出行与先前预测模型不符的出行情况时,可通过地铁进出站记录,以及GPS记录出行轨迹.并且地铁运营站点停留时间十分稳定且精确,通过将用户的出行模型预测规律,与地铁运营时间相结合,即可精确的对用户下车时间、地点、车厢接触停留时间进行预测跟踪.

3.2.2 群体区域的聚类划分

在传统的移动群体感知中,通常采用的划分方法是根据目标地图的经纬度对目标区域进行光栅化,即用相互垂直的经纬线将任务感知区域划分为若干正方形.当用户出现在其中某个划分区域中时,则该区域被用户所覆盖.这种无差别地区域划分虽然简单易行,并且可以覆盖整个移动感知区域,但不能反映区域与任务分布的关系.通常任务的完成类别、数量和时间限制通常都是不同,这些都与区域的内部特征有关,而传统的无差别网格划分方法很难做到.不同的是,基于密度的聚类方法可以在所需要查找的全部数据中找到不同类型和大小的聚类.在聚类过程中,将先发现密度比较高的数据,然后将这些数据绘制为一个统一的整体一个聚类,在这里密度聚类可以对同类任务在地图上的分布情况作出较好的聚类划分,生成不同大小合适的的任务区域.

在此基础上,本文提出了一种基于移动感知类别的区域划分方法.本方法从聚类的角度出发,根据任务类别的特征属性和类别的时空位置,对同一类任务在区域内得到进行聚类得出任务聚类区域的中心点.根据任务请求者给出的具体感知任务来确定感知目标类别,数据需求者在发布任务时需要进行任务类别的选择,以此确定与之相应的感知对象.

3.2.3 任务参与者的选择

在感知平台中,为了更好的优化平台任务处理能力,起到激励用户的作用.同时,当出现应急任务时,希望系统可以在一定时间内尽可能完成多的任务.用户的主要激励由两部分组成:其中第1部分是每个任务发布时就分配好的固定基本收入,第2部分是动态激励收入,用户在完成任务时的移动距离越大,该部分激励收入也就越多.所以,该问题的优化目标是最小化用户的数量和用户为完成任务时所需要移动的距离.基于此问题,本文提出两种参与者选择算法:以用户激励成本(移动距离)为优化目标的OCTDM(optimize cost task distribution model)算法;以参与任务用户数量作为优化目标的ONPTDM(optimize number of people task distribution model)算法.

3.3 感知任务的执行

当在地铁中群智感知用户收到所预测的下车站点的感知任务时,若不符合下车位置可重新手动选择站点,符合可直接接受任务组合.用户在相关地铁站点下车后,可直接自行前往或跟随系统分配的导航路径前往任务点进行感知任务.参与者可直接通过智能手机进行感知、计算、上传等操作.在不同的任务之中可能会具有不同的感知方式要求,例如视频、拍照、录音、情况说明选择等等.同时感知任务完成的质量也将影响到参与者的激励以及日后的感知信用.所以参与者在完成感知任务时可对同一任务进行多角度多方面的采集以保证数据的全面、多样、真实性、可靠性.用户完成采集后数据将会在移动终端进行预处理操作,提取出感知任务相关的有效信息,并通过移动数据或者Wi-Fi进行数据上传.

3.4 感知任务实例

通过一个实际的任务例子,说明基于地铁的多任务分发方法的一些功能:长沙国庆节当天在橘子洲头有烟花表演,吸引了大量的外地游客以及本地居民的观赏,欣赏烟花的同时也造成了橘子洲附近人流量的急剧飙升,造成道路瘫痪、地铁严重拥堵等情况.巨大的人流也引起了事故发生概率的增加.针对这一紧急情况,实时人流的监控,各路口、地铁口中的拥堵运行情况等信息对于人流的疏导来说就显得尤为重要.并且这一系列任务对时间的要求也极高,同时获取的数据量也是越大越有利于人流走势的分析.任务的发布者希望参与者可通过手机或视频的方式,加上定位信息记录当前各处的人流状况.希望在2小时内持续的可以收到相关任务的信息,并且每个人都是移动的,可以同时采集多处位置的情况,完成多个任务.为保证数据的多样真实性,且数据不需过于冗余,所以每条街道记录4次足以满足感知覆盖的需求.所以,为了降低平台的激励成本,参与者选择方法将会始终不断刷新任务完成的覆盖面积,不断更新参与者的选择集合至感知未被覆盖的区域.以此保证最小化参与者的移动距离,以降低系统的激励成本.

4 参与者选择优化模型

4.1 群体区域聚类划分模型

密度聚类过程如下图3,当设定eps为R,MinPts为2时,图片中的点都是浅黄色的点.选择其中一个点作为算法的入口点,然后绿色点是被选中的入口.将EPS范围设置为图中圆的半径R,最小值为2.

图3 密度聚类过程Fig.3 Density clustering process

这里以绿点为中心,以eps为半径画圆.可以发现这个圆(小于或等于半径)中有两个粉色点(边点),并且点的数量不小于MinPts(2大于等于2),因此它们成为一个簇.圆中的其他点标记为粉色(边点).这样,递归之后,将得到一个大型集群.在图中,绿色是中心点,粉色是边缘点.如果仍有一些点未处理,请选择其中的另一个点以开始生成新簇.算法过程是一样的.当算法执行完成时,可能有一个既不是边缘点也不是中心点的点,例如图中的紫色点就是这样的噪音.

如果一个点P是从一个点P到达的,那么点Q就是从点P直接到达的密度.如果一个点Q是从一个点P通过一个特定的跳跃到达的,那么点Q就是从点P到达的密度.如果点Q是从点P密度到达的,从点Q密度可以到达点P,点P和Q被称为密度连接.上面提到的“跳跃”是指通过的箭头的数量,并且只能沿着箭头的方向前进.

任务分发模型首先根据任务地理位置分布,利用密度聚类算法对任务进行子区域划分,并利用最短路径算法[20]计算各地铁站台点距离最近的任务子区域聚类中心,进行任务分配.

密度聚类的效果与聚类过程中部分参数的设置相关,部分密度聚类相关参数说明如下:

密度聚类为感知任务中的同类任务集合

核心对象:若γj至少包含MinPts个样本,即|N ∈(γi)|≥MinPts,则γj是子任务集合.

4.2 聚类区域覆盖模型

设感知平台对用户i预测的可能下车站点集合为S(s1,s2,···,sm),分别对用户在每个可能站点sj利用OCTDM 算法和ONPTDM算法进行多任务分发,得出该参与者在站点sj的感知任务集合Ti(t1,t2,···,tn),所需要传输的任务ri的大小为w(ti),用户在地铁系统中通过Wi-Fi进行传输的时间为q(q=φ∗w(ti)),其中φ为地铁系统Wi-Fi系统进行任务传输的传输速率.由于用户在车厢内停留时间有限,所以需要限制qi在上车下车站点之间的停留时间内.记用户停留时间为Qi.在此情况下,用户i在地铁中可以通过地铁系统进行任务分发的任务数量为Ni(Ni=Qi/qi),即用户i在目的站点下车后可最大任务执行量为Ni条.

定理1站点覆盖.若在某一子区域范围内,存在地铁站点,则称该地铁站点实现了对本子区域的的覆盖.对于某一地铁站点si ∈S和子区域cj ∈C而言,子区域被覆盖情况需要满足式(3).

根据以上定义可知,某条地铁线路S对感知任务的子区域覆盖情况可以用G(S,cj)来表示,如式(4).

并且,对于用户i下车站点预测问题,首先用记录地铁乘客上车站点位置,用表示预测得出的地铁乘客可能的下车站点位置.在模型中,BS为地铁线路S中Si站点处的实际上车地铁乘客数量,所以BS需要在地铁实际到达站点s时才可得出.

4.3 多任务动态分发算法

由上述模型描述可知,本任务动态分发方法是一个同时具有两个优化目标[21]的NP难问题.无法通过普通算法在多项式时间内找到在所有解中的最优解,只能通过随机搜索、贪心等方法对最优解进行不断逼近.所以本文选择在以其一目标作为约束的条件下,分别针对另一优化目标进行优化.以参与者个数作为约束,以用户激励成本(移动距离)为优化目标的OCTDM算法;以及以用户激励成本(移动距离)作为参与者选择约束,以参与任务用户数量作为优化目标的ONPTDM算法.

4.3.1 最小化用户数量的ONPTDM算法

ONPTDM算法是一个将参与者人数最小化作为首要优化目标的算法.算法的主要思路是先进行任务的选择,再在此基础上进行参与者的选择.对于任务的选择,系统会对候选任务以所需要的人数进行降序排序,不断将需要人数最多的任务加入任务集合.此方法可以保证在任务选择过程中不会出现孤立任务,不会出现无法被选择到的任务.可以避免传统研究所用的随机选择算法中某些任务一直无法被选中的情况.然后将此任务集合分配至距离该任务集合最近的参与者,并且该参与者拥有足够的时间完成该任务集.

在本多任务动态分发方法中,需要用户同时参与多个任务,即用户的位置会根据不同任务位置分布不同而不断变化.由于用户位置的不断变化,若无法预测用户位置变化的变化轨迹,则很难继续对下一个任务做出选择.但由于系统已知所需感知的任务的地理位置分布,所以系统可以根据任务位置的分布进行组合.确定合适的参与者,选出用户在时间限制内可以完成的最大任务集合.同时,为了对移动距离进行最小化,算法会对任务集合周边的参与者进行筛选,选择出一个距离感知地点距离最短的用户参与任务.本算法选择出的参与者集合通过了对各参与者执行任务集的优化.当出现紧急事件,用户数量不足时,可以达到最小化所需用户数量的目的,实现了系统基础成本的最小化.

4.3.2 最小化用户移动距离的OCTDM算法

在最小化用户数量的ONPTDM算法中,因为无需遍历所有用户,只需要从任务集的角度出发,所以可以大大减少计算量.但同样因为未考虑全部用户,所以并不能做到针对每个用户的任务集合分配最优化.因此为了提升用户的整体性能降低激励成本,OCTDM算法从用户的角度出发进行任务集合的分配.本算法基于贪心算法的思想,在为用户分配感知任务过程中,每次都分配距离用户当前地理位置最近的任务.算法不断获取当前局部最优解,使得最终解不断逼近最优解,能够以较短的距离完成任务.所以从所拥有任务集合中数量最多的用户开始选择,直到任务集覆盖全部任务.

5 实验评估

5.1 实验数据

地铁的运营线路信息可以反映该地铁系统对城区的覆盖程度,地铁站点的主要分布区域,以此推断地铁系统对感知任务范围的有效覆盖,如表1.

表1 地铁系统路线分布Table 1 Route distribution of metro system

各线路的运营时间信息可以用于用户停留时间的分析,通过上下车站点可以得出在列车内停留的时间,从而得出可用的任务传输时间,如表2.

表2 线路运营时间Table 2 Line operating time

通过对地铁系统的历史客运流量的分析,最高客流的分析,可以得出用户的大体出行规律以及出行的历史变化趋势,并据此预测未来出行走势,使得多任务分发方法可以跟随出行流量的变化进行优化,如表3.

表3 历史客运流量Table 3 Historical passenger traffic

并且根据各线路各列车在不同期间不同的列车数量,结合运营间隔,可以得出车辆每小时的最大运载量,如表4.

表4 列车数量Table 4 Number of trains

根据表1可知,长沙轨道交通运营线路共3条,共设车站46座、换乘站1个,运营里程68.71千米.

以上地铁系统运营相关特征,结合用户相关出行数据,即可对地铁上的乘客行为进行模拟.TaxiSet是一个根据2011年4月到6月北京29000辆出租车[22]的载客记录建立的乘客出行模拟平台,可以通过该平台生成所需要的不同时间段的用户出行记录.每一条出行记录中包括本次出行的出发点、目的地、出发时间等参数,结合高德地图API可以得出通过市区地铁出行所需要乘坐的地铁路线.这样就得出了所需的地铁乘客出行记录.

并假设在实验中每个感知任务需要3个参与者完成,并且在完成过程中可能需要使用拍照、视频、文字等记录方式,所以本文假设每个人完成每个任务的时间为5分钟.为便于计算下地铁后参与者的移动距离和时间,本问题假设用户下地铁后统一通过步行移动以80米每秒的速度前往感知任务地点.

5.2 评价指标

本文针对该问题提出的基于地铁交通的多任务动态分发方法主要从两个角度设计了一下两个算法来实现,分别是以参与者个数为约束,用户激励成本(移动距离)为优化目标的OCTDM(optimize cost task distribution model)算法和以用户激励成本(移动距离)作为参与者选择约束,以参与任务用户数量作为优化目标的ONPTDM(optimize number of people task distribution model)算法.两种方法分别从两个不同的优化目的出发,对整体感知任务的参与者选择问题进行优化,因此选择过程、选择结果、结果的优劣都会有所不同.所以需要通过实验分析从多个角度场景对比两个算法选出的参与者集的性能优劣.在本文的该问题中,参与者集合的优劣可以通过两个参数进行比较:参与者的人数、完成任务的总移动距离.因此,两个算法的优劣可以通过他们在不同情况场景下选择出的用户集合的总人数、平均每人任务数、总移动距离进行评判.对结果有所影响的外界因素又可以总结为:总任务个数、候选用户人数、任务分布情况、任务发布时间、任务紧急程度(任务限制时间)等等.

对于该感知任务的用户总移动距离,由于任务数量固定,所以假设任务所属地理位置也是确定的.由于需要完成的总任务是一定的,所以参与者人数越少,每个参与者所需要移动的距离就越大,本文的分发中同样希望用户集的总移动距离是最短的,但此时参与者人数与总移动距离呈反比关系,所以在本文中利用参与者总人数与任务总移动距离的乘积对两者进行综合评判,该乘积越小系统总绩效越好.所以本文中通过实验比对两种算法在不同应用场景下的人数、人平均任务数、总距离以及总距离和人数的乘积,来选择出在不同情况下两种算法中最优的解集合.

在实际的群智感知任务中,能够对任务完成质量造成影响的相关相关因素有很多,本实验的主要目的是通过对算法的各影响因素进行观察,分析出主要的影响因素,达到在实际任务发布时可以提前考虑这些影响因素选择出最佳的算法进行参与者选择.可能对算法选择出的参与者集合造成影响的因素有总任务个数、候选用户人数、任务分布情况、任务发布时间、任务限制时间等等.例如当其他条件一定的情况下,待完成感知任务不同的分布,较为集中或较为分散的的任务情况下,较为分散的任务分布中所需要选出的参与者人数更多,总移动距离也更长.所以对于分散式任务来说,系统可能需要更多的基础激励和动态激励吸引用户完成任务,保证任务完成质量.对于不同的任务发布时间,白天相对于晚上可以用更少的用户人数就可以完成相同数量的任务,且用户总移动距离更短.所以可以让系统尽量在白天进行感知任务的分发.

5.3 实验结果

5.3.1 任务区域划分

任务动态分发算法首先将根据地铁在市区内的分布情况以及具体任务集的地理位置,通过密度聚类对任务以划分范围内站点间距为限制进行子区域划分.由于部分任务位置过于偏僻和稀疏,本文截取了以五一广场为中心17 km范围内的任务目标,密度聚类过程中聚类半径1 km(eps=0.01),聚类范围内最少任务节点数为20(min samples=20).对任务的主要分布区域和地铁分布进行结合,绘制任务分布聚类图,如图4所示.分发系统将对地铁周边的任务区域进行多任务分发,东北处离地铁较远的区域采取移动网络形式进行分发.

图4 密度聚类过程Fig.4 Density clustering process

5.3.2 任务个数的影响

由于不同的任务数量将会对任务的分布、参与者的选择、算法的分发过程造成影响.所以本实验首先将对参与者选择算法中的总任务个数的影响进行分析,将同时对四种算法进行比对分析.并利用参与者人数、人平均任务数、总距离、以及总距离和人数的乘积对算法结果进行评价.

从图5(a)中可以看出随着待分配任务数量的增加,无论是ONPTDM算法还是OCTDM算法,为了完成任务都需要选择出更多的参与者用于任务的完成.并且任务数量越多,人数增加的速度越来越快.可以发现OCTDM算法较Greedy Algorithm选择出的参与者平均人数减少了16.5%;以最小化参与者为优化目标的ONPTDM则较Greedy Algorithm减少了22.1%的用户数量;Li等人在2019年提出的Benefit算法主要优化目标为最大化用户获利,所以在改善系统基础成本方面表现并不突出,仅较Greedy Algorithm降低了5.82%的基础成本.

表5 不同算法需要的参与者人数Table 5 Number of participants for different tasks

图5 待分配任务数的影响Fig.5 The impact of the number of tasks to be allocated

在图5(b)中随着待分配任务数量的增加,多任务分发系统为每个任务参与者所分配到的任务先增高再降低.可以推测是因为随着需要完成任务数量的增加任务的分布也越来越分散,每个用户所分配到的任务地理位置也越分散,所以在一定时间内每个用户可以完成的任务更少.Greedy Algorithm的人均任务数可以达到4.42个,OCTDM算法平均每人完成任务数可以达到5.46个.而以最小化用户数量为优化目标的ONPTDM算法可以达到每人5.89个的任务分配效果.Benefit算法较Greedy Algorithm算法提高了8.15%的人均任务数.

在最小化系统成本过程中,当在需要完成的任务数量一定时,所选的人数与总移动距离为反比关系.若希望可以同时对两个因素进行权衡,则从图5(d)中两者的乘积可以看出OCTDM算法可以拥有更低的乘积系数,任务分发系统拥有更低的总代价.OCTDM的平均可达到25.98,ONPTDM可以达到28.47.LCPSA相比Greedy Algorithm,提升39.26%的性能.

所以图5(a)(c)中可以看出,在应急情况下出现用户量不足时,ONPTDM算法可以利用最少的参与者数量保证任务的完成;当任务不需要紧急完成,优先考虑感知系统总成本最小时,OCTDM算法可以对系统的激励成本和固定成本进行最小化,达到最小化总成本的目的.

表6 不同算法的参与者与距离乘积情况Table 6 Participants and distance of different tasks

6 结论与展望

本文主要针对短视频时代移动群智感知存在的问题,移动群智感知任务的视频化程度越来越高,在传统研究中常利用机会网络和移动网络激励任务的分发和数据的收集,但机会网络中节点移动的不可控性,以及视频任务内容传输的高代价性都使得这些方法的实用性大大降低.针对此问题,利用社会移动群体规律性的自主聚集、活动范围大等特点,提出一种面向社会移动群体的群智感知参与者选择优化模型.利用密度聚类算法根据同类任务的位置进行划分得出聚类中心,实现任务子区域所属地铁站点的划分.包括基于用户激励成本的参与者优化算法和基于用户数量的参与者优化算法.仿真结果表明,与同类算法相比可以消耗更低的系统资源选择出参与者数量更少的任务分发方案.