基于城市轨道交通的群智感知任务分发方法

蒋伟进 吕斯健 刘跃华 陈君鹏 张婉清

①(湖南工商大学计算机与信息工程学院 长沙 410205)

②(湖南工商大学大数据与互联网创新研究院 长沙 410205)

1 引言

任务分配作为移动群智感知中的关键环节之一，分配的合理性将成为任务完成质量和代价的决定因素之一。为了降低任务分发对移动数据网络的依赖，以降低用户参与者在接收任务时的流量费用代价[1]，以及降低基础移动网络质量对系统任务分发的影响。许多研究者都会将弱网络传输的机会网络(opportunistic networks)[2]引入任务分发模型中，即利用参与者在随机移动过程中的机会接触，通过弱连接进行任务分发以及数据的传输，例如蓝牙、Wi-Fi局域网等。但是考虑到当前感知任务类型的多样性，任务信息内容通常含有视频、音频等资料。传统机会网络传输的随机不可靠性以及较低的传输速率，通常无法较好地满足复杂任务的分发质量需求。首先在现有的大多数研究中，大都是在忽略所传输的任务信息大小的前提下进行的，没有也无法对节点之间的接触时间、距离进行考虑和衡量。然而随着技术的发展，图片、视频等媒体信息早已融入人们的互联网生活，任务信息中同样如此。在现有技术中机会网络进行短距离接触传输时大多通过蓝牙等低功耗低速率传输手段，当面对传输视频、图片等较大数据时需要保持较长的接触时间才能保证传输质量。然而在实际情况中，机会网络节点的接触时间是难以估计的。即使部分研究已经开始将其作为必要条件之一，但是依然没有提出较好的估计算法。

在任务分发过程中参与者[3]的选择同样也是移动群智感知的核心问题之一，参与者的选择对任务分发的效率、数据收集的质量、感知数据的全面性都有着关键性的影响。在当前的研究中，也有许多学者对这一问题进行了深入的研究。如Ca等人研究了在参与者人数固定的情况下，如何最大化群智感知面积。但是目前大多数的研究依然都只是基于单个群智感知任务进行协同分配，而在实际情况中，通常会在同一时间段内出现大量相近的群智任务需要完成处理[4]。首先大多移动群智任务之间会具有一定的相似性，如时间或空间上可一同完成；其次单个用户同时完成多个感知任务也可大大提高用户在完成任务时的主观能动性[5]，比传统的任务激励方式效果更好；并且为用户分配地理位置较为相近的一组任务，也是一种群智协同资源利用效率的提高。

在这一问题中，参与者人数、移动距离等都是多任务[6]分发算法需要优化的目标。但是在现有的研究中，大多数都是针对单个目标进行优化分析的，然而在大多数情况下同时考虑多个影响因素进行参与者的选择可以实现更好的任务分发。

为此，本文充分利用了地铁交通市区覆盖面广、人口流动性大、用户节点接触时间稳定且可控可预测[7]等优势，通过地铁轨道交通这种现成的基础设施实现了移动群智感知任务的分发。在感知任务分发过程中，先在系统中对数据需求者给出的同类任务进行密度聚类(density-based methods)。然后根据各聚类中心与现有地铁站点的距离，为每个子任务区域分配[8]所属的地铁站点，达到使用城市地铁轨道交通实现对感知任务区域就近覆盖的目的。然后，通过多任务动态分发方法实现感知任务子区域内的任务并行分发。针对任务分发的两个主要优化因素：一是用户的激励成本，一般激励策略中动态激励主要与用户为完成任务所移动的距离成正相关；二是所选择用户节点的数量，需要的用户数量越少服务器所需要付出的基础代价也越低。本文分别提出了基于激励成本的任务分发模型(Incentive Cost Task Distribution Model,ICTDM)和基于用户数量的任务分发模型(User Number Task Distribution Model,UNTDM)。

2 相关工作

移动群智感知与传统群智协同计算的不同之处在于其移动性，传统群智计算通常会将单个个体无法独立处理的任务划分为多个部分分别处理，这些任务通常与地理位置没有太多的关联。移动群智感知为了充分发挥其移动性，大多任务都是直接或间接与地理位置相关联。所以与基于用户社交关系的参与者集合选择方法不同，在移动群智感知中参与者将以地理位置信息作为首要的选择条件[9]，其次才考虑其他和任务完成质量相关的优化因素。Zhang等人[10]认为在移动群智感知中可以通过利用参与者的位置信息，对参与者进行游戏竞赛激励以达到效用最大化的效果。Zhang等人[11]通过从感知区域覆盖质量的角度对分布式人群最佳覆盖推导，利用子模型中的优化属性提出一种基于贪心思想的时间复杂度近似于O(n)的随机游动算法。Zhang等人[12]提出了一种在满足限定时空覆盖率的情况下，通过最小化参与者人数来最小化总系统群智成本的方法。该方法将首先通过分析备选参与者的历史任务完成情况以及移动轨迹，分析预测未来用户的移动轨迹，并通过此预测在满足任务完成最小覆盖率的限制下，最小化参与者人数。因每位参与者都有系统所分配的固定激励成本，所以人数越少系统所需要付出的固定激励成本越少。同时对于每位用户的动态激励成本，系统需要通过历史移动轨迹预测未来移动轨迹已到达最小化任务移动距离的目的，该方法同时对用户数量和任务移动距离进行最小化操作，以达到最小化系统总激励成本(固定成本和动态激励成本)的目的。

在移动群智感知的参与者选择中，以上大多数研究都是基于单个用户在一定时间内完成某一个具体的感知任务。与此相比，若参与者可以同时接受多个位置相关相近的任务，一次一起完成，无论对于平台还是对于参与者来说都是可以极大地提高任务完成分发效率的。同时还可以增加用户所得到的奖励，提高用户完成任务的主观积极性，起到激励作用。Alswailim等人[13]提出了一种对参与者进行评估的信誉系统(Reputation System to Evaluate Participants,RSEP)，通过对参与者的共享进行分组，过滤出在贡献方面具有较高的准确性的参与者。在这一方面，Guo等人[14]分别基于感知任务的所需时间、用户移动轨迹、用户机会网络传输概率等因素，对移动群智感知任务执行节点的选择与分配进行了研究。分别提出了两种基于任务完成路线优先和基于任务优先的参与者选择算法。Karaliopoulos等人[15]在INFOCOM会议上提出了基于贪心思想的启发式算法，其通过在机会网络中利用贪心的启发式算法对任务传输延时进行最小化，以达到感知任务的收益最大化的目的。Li等人[16]提出一种基于服务意识的多任务分配策略，其同时考虑了任务难度、历史、感知能力和积极性等方面对参与者进行服务收益最大化的任务分发。

3 数据感知任务分发方法

3.1 任务地理位置划分方法

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

计算时将感知任务的分布区域记为A,A的实际范围是根据任务发布者所发布的任务分布位置所确定的。假设各类移动感知任务γi在地图上的位置坐标为(xi,yi)，所以在地图上同类任务γi的集合可以表示为L={(xi,yi)。任务分发时使用密度聚类进行任务子区域划分，对全部移动群智感知任务区域中的同类感知任务进行聚类划分，得到各聚类子区域的划分以及子区域的聚类中心，各子区域记为C={c1,c2,...,cm}。对于某一区域ci而言，记子区域核心点为oi=。由此可得在当前任务集合中，本类任务的核心点集合为O=。

3.2 轨道交通覆盖模型

在子区域覆盖模型中，平台任务将会先利用宽带网络传输至地铁分发网络中，模型相关符号见表1。每辆列车中都拥有全部需要分发的任务，在平台中任务子区域已通过最短路径算法分配至指定站点。地铁分发系统会对上车用户的历史出行情况进行分析，通过参与者的历史出行记录预测本次出行可能的下车站点，根据预测可信度对参与者分配的任务进行选择。根据上车下车站点即可计算在列车内停留时间，可以得知在站点间隔时间内可完成传输的总任务大小，并为其分配属于指定站点任务子区域的任务内容。相比传统的通过机会网络传输任务模式，任务分配更完整，任务传输成功率更高。

表1 模型相关符号表

对于列车内的动态分发过程，记站点s在任务聚类区域ci内 进行分配的感知任务数量为则地铁线路S在该类型任务的聚类区域上ci中进行分配的感知任务数量为，所以该聚类区域占整个地铁线路的比例为

基于式(1)的定义，本文利用各地铁站点中各乘客所接收到感知任务位于全部任务的比例，以及全部区域A内的所有聚类分区的任务比例和感知任务的相关性对算法的实际分发效果进行表示，见式(2)。并且任务的分配过程需要满足由传输速度和乘客停留时间所决定的时间限制，如式(3)。为了保障能收集到更多的数据，算法优先将感知任务分发给尽可能多的节点，所以地铁线路中所包含的任务集合需要满足式(4)

3.3 众包任务分发模型

多任务动态分发方法的主要优化目标是在最小化系统成本的情况下，从待选择用户中选择出可在感知任务时间约束条件下完成任务的参与者集合。在当前研究中，感知系统的主要成本来自任务的传输成本以及系统对用户完成任务的激励成本。在本系统中任务通过地铁系统的Wi-Fi内网进行传输，无需消耗移动数据流量所以无需考虑。在系统中用户的激励成本中分为两部分，分别是任务的固定成本和用户完成任务过程所产生的动态激励成本。固定成本在任务发布者发布之初就随着任务的难度、时间等相关因素进行了设置。系统的动态激励成本主要与用户完成任务过程中所花费的代价相关。在目前研究中主要以用户移动距离作为评判标准。

可知在任务不变的情况下，系统所花费的总成本主要与用户的移动距离相关。同样调用较少的参与者可以减少系统需要发放的固定成本，降低系统管理参与者的成本，提高单个参与者的激励收益，促进用户完成任务。

假设在移动群智感知系统中具有n个待完成的任务T={t1,t2,...,ti,...,tn}。为保证感知结果的普适性和准确性，通常对于每个任务都需要由ri个人完成。并且通过录像、录音、文字等方式对感知对象进行数据的收集。在本研究中，假设完成每个任务需要时间为hmin。假设感知系统中有m个可选参与者U={u1,u2,...,uj,...,um}，并且要求用户所分配的任务需要在Hh内完成，并且设参与者的移动速度是vm/min。使用U Ti={ui1,ui2,ui3,...}表示任务集合ti被分配到的用户集合，完成任务集合T全部任务的用户集合可以用P={p1,p2,p3,...}(P=UT1∪UT2∪...∪UTn)表示。各参与者被分配到的uj任务集是T Uj={tj1,tj2,tj3,...}，完成这些任务所需要移动的总距离是D(TUj)。

多任务动态参与者选择模型的优化目标分为两方面：一个是对系统全部任务的移动距离进行最小化式(5)，因为系统动态激励与用户移动距离的相关性，所以当系统对参与者移动距离进行最小化时，可以实现全局动态激励成本的最小化；另一个是对用户的总人数进行最小化式(6)，当出现紧急情况感知平台突发大量群智感知需求时，需要对用户实现最大化的利用。发挥多任务动态分发方法的特性，为每个用户进行任务的最大化分配，使得用户完成任务可以获得更多的报酬，实现平台与用户的双赢。

为保证平台信用检测机制的良好运行，实现任务完成质量的把控。任务需要进行冗余分发，以提高任务完成率、确定感知准确度。所以任务ti需要ri个人完成，如式(7)。对于时间限制较高的任务，需要在H h内完成，如式(8)。通常完成任务所需要花费的时间分为两部分，用户移动到任务地点所花费的时间和用户在任务地点完成任务的时间

由于该问题不是普通的单目标优化问题，本问题的主要优化目标有两个：分别是用户的数量和完成系统分配任务需要移动的距离。并且各优化目标范围较大，这是一个典型的NP难问题。

在多目标优化问题中，由于存在多个优化目标，所以可能存在优化目标之间造成冲突或者无法比较的问题，不一定存在同时满足所有优化目标的最优解。所以本文针对此问题的优化目标有两个，一个是尽可能缩短参与为完成任务的移动距离，另一个是对选择的参与人数进行最小化。因此，本文将以其中一个因素作为限制，在此限制上对另一因素进行优化求解。

4 实验评估

4.1 目标数据

本文主要针对长沙市地铁轨道交通情况的数据进行实验分析，获取了长沙市内的3条地铁线路以及1条磁悬浮快线的实际客运数据。主要包括各运营线路分布情况、各线路运营时间、历史客运流量、沿途站点信息、线路班车信息、线路市区覆盖情况、实际运营里程等相关信息。

地铁的运营线路信息可以反映该地铁系统对城区的覆盖程度和地铁站点的主要分布区域，以此推断地铁系统对感知任务范围的有效覆盖。各线路的运营时间信息可以用于用户停留时间的分析，通过上下车站点可以得出在列车内停留时间，从而得出可用的任务传输时间。

对于地铁乘客的实际出行行为，本文使用由长沙市轨道交通运营公司提供的地铁IC卡脱敏数据进行分析，源数据字段格式如表2，经过刷卡数据的初步分析，发现原始数据中存在与本研究无关的数据以及无效数据，经清洗后抽样取出本实验所需的5个字段，包括卡号、进站站点、进站时间、出站站点和出站时间，作为实验中乘客扩散的基础数据。

表2 智能卡数据格式

对于感知任务，将以长沙市酒店实际情况信息作为感知目标，其中包括酒店的位置、门面外观、前台外观、线下实际报价表等等。因此酒店的位置分布就是本次移动群智感知的任务分布范围。酒店数据通过美团网获取了1120家酒店信息，其中包括酒店在线上公布的图片、位置、价格、名称、类别。

4.2 实验评价指标

在该问题中，对于不同任务分发方法选择出的参与者集合。本文通过4个参数对算法进行比较：参与者的人数、人均任务数量、完成任务总移动距离以及距离和人数的乘积。算法的影响因素包括：总任务个数、候选用户人数、任务分布情况、任务发布时间、任务紧急程度等。通过以上多个场景进行实验分析，对比算法选出参与者集的性能优劣。

为了更好地对提出的两种算法性能进行分析比较，本文在现有的移动群智感知任务分发算法中，选择了同类算法Heuristics和SBAMA(Service Benefit Aware Multi-task Assignment)进行比较。Heuristics算法是Karaliopoulos等人[15]在INFOCOM会议上提出的基于贪心思想的启发式算法。其通过在机会网络中利用贪心的启发式算法对任务传输延时进行最小化，以达到感知任务的收益进行最大化的目的的算法。而SBAMA算法是Li等人[16]在2019年提出的一种基于服务意识的多任务分配策略。其同时考虑了任务难度、历史、感知能力和积极性等方面对参与者进行服务收益最大化的任务分发。对于仿真模型的相关场景参数，各算法统一进行设置，如表3。

表3 模型参数设置

由于已有文献研究场景与本文的差异，为了保证对比的合理性和有效性，我们将这两种的主要参与者选择策略应用到本文的实验场景中。分别对比了本文提出的ICTDM,UNTDM,Heuristics以及SBAMA算法在不同影响因素(总任务个数、候选用户人数、任务发布时间、任务限制时间)下的可用性。利用算法选择出的参与者人数、移动总距离以及两者的乘积对算法的综合性能作出评定。

4.3 实验数据结果

(1)任务区域划分

多任务动态分发算法首先将根据地铁在市区内的分布情况以及具体任务集的地理位置，通过密度聚类对任务以划分范围内站点间距为限制进行子区域划分。对任务的主要分布区域和地铁分布进行结合，绘制任务分布聚类图，如图1所示。分发系统将对地铁周边的任务区域进行多任务分发，东北处离地铁较远的区域采取移动网络形式进行分发。

图1 任务子区域分布

(2)算法实际运行效率

评价一个算法的好坏除了实现效果、选择结果以外还应包括算法的实际运行时间。因为过长的运行时间会增加用户等待时间，占用过多的计算资源导致算法的实用性大大降低。本实验的运行环境如表4。

表4 实验软硬件环境

从图2可得出，ICTDM的平均运行时间为1.96 s；UNTDM的平均运行时间为1.09 s；Heuristics算法的平均运行时间为1.47 s；SBAMA则为2.28 s。可知ICTDM和SBAMA算法的运行时间远远大于UNTDM和 Heuristics算法。从算法的时间复杂度和算法原理可推测可能由于前两种算法需要考虑因素过多，每次算法迭代都需要遍历所有候选者并对用户周围的任务进行筛选。而UNTDM算法只需要从任务集中进行选择，并将任务集合分配给用户即可。在通常场景下，待选择用户数量远远大于待分发任务数量，所以从用户角度进行处理的算法时间复杂度会有所提高。所以虽然ICTDM的系统成本较低，但在考虑时间要求、性能较高的应用场景时，UNTDM可以带来较好的使用效果。

图2 任务数量与算法运行时间

(3)分发时间的影响

对于任务分发算法，重要的影响因素除了任务数量，还包括任务分发时间段。在不同时间段对任务的分发由于用户状态的差异，可能会选择出差异较大的参与者集合，造成不同的任务分发方案。例如分别在工作日和周末进行任务分发时，周末的用户数量、用户灵活度、参与程度都会更高，两个时间段的用户特征具有较大的差异。所以本次实验将对任务的分发时间段对用户选择的影响进行研究，并对周末与工作日两种算法的多个评定因素进行对比。根据任务的不同，将参数N修改为300进行实验。

从图3(a)和图3(c)可得出，4个算法在工作日选出的平均参与者人数为160.63人，周末为194.90人，工作日时的参与者数量较周末减少了21.33%。移动距离相比周末缩短了25.77%。在执行相同任务的情况下，可以看出工作日进行任务分发选出的参与者数量较少、人均分配到的任务数量较多，系统的总移动距离也较小。根据上述实验可得出ICTDM和UNTDM算法的区别与联系如表5。

表5 算法应用场景对比

在图3(d)中，同时考虑用户数量和系统完成任务的自动移动距离，可以发现在工作日时系统所选择出的参与者集合性能更优。所以在工作日时，感知系统应该适当加大任务的基础奖励和动态奖励，以保证感知任务的稳定完成。

图3 任务分发时间的影响

5 结论与展望

本文主要研究了移动群智感知的任务分发方法，提出了一种基于地铁乘客的多任务动态分发方法。在该方法中构建了基于地铁系统的任务扩散模型，并分析了针对不同优化目标的多任务分发问题。提出两种具有一定约束限制的动态任务分发算法：以参与者个数作为最低约束，将用户总移动距离作为优化目标的ICTDM算法；以用户总移动距离作为最低约束，将参与任务用户数量作为优化目标的UNTDM算法。并通过长沙市的用户出行和酒店数据集对两种算法和传统算法的多个影响因素进行评估。实验结果表明：ICTDM算法可以为感知系统带来比传统算法更低的激励成本和基础成本；UNTDM算法则可以在较短的时间内利用较低的系统资源，对应急情况人员不足时的感知任务进行合理分配，保证感知质量。并得出相比在周末进行任务分发，在工作日进行感知任务的分发可以具有更小的用户数量和用户移动距离。

文章的重点集中在地铁乘客的基础上，进行任务分发时参与者和移动距离的最优化。未考虑到每个参与者对不同任务的不同性，没有为每个用户分发其最适合的任务。下一步工作中将结合每个用户节点的差异性和具体任务类别进行针对性的任务分发。以达到增加任务的适应性，提高任务的完成质量和效率的目的。