面向协同感知的任务分配方法

来源:用户上传      作者:

　　摘要：为维护社会公共安全，当出现违法案件时，公安部门需尽快获取案件发展的实时信息。目前实时获取信息的渠道主要有两种：一是利用部署在城市热点地区大量监控摄像头进行追踪，二是利用普通民众携带的各类智能设备获取信息。因此提出一个面向协同感知的任务分配方法，利用监控摄像头与行人通过协同感知覆盖特定区域道路网络。首先根据实验区域内道路网络拓扑结构研究任务重要程度，提出任务优先级计算方法，用以区分不同任务优先级;其次提出参与者可信度计算方法，该方法以物理距离为基准，通过引入空间距离衰减指数函数计算行人执行某项待选任务的意愿值，再与任务优先级结合，计算行人可信度;最后提出双向选择多轮任务分配（McTA）算法并利用真实数据集进行实验测试。结果表明，该方法在数据集中完成率达95%以上.
　　关键词：协同感知;贪心算法;任务分配;双向选择
　　DOI： 10. 11907/rjdk.192815
　　开放科学（资源服务）标识码（OSID）：
　　中图分类号：TP301
　　文献标识码：A
　　文章编号：1672-7800（ 2020）004-0014-O（
　　Collaborative Awareness Oriented Task Allocation Method
　　YIN Hou-chun. CUI He-Iei. YU Zhi-wen. WANG Liang， GUO Bin（School of CompuLer Scie. nce . lVorthweste. rn Pohiechnical Un ive. rsity . Xi ' an 710129. Ch.ina ）Abstract：ln order to maintain the public security， when there are illegal cases， the public security department needs to obtain the re-al-time inf'orruation of the case development as soon as possible. For this purpose， two major approaches are usually adopted. One is touse a surveillance network consisting of a large nuruber of' surveillance cameras deploy ed in urban hotspots; the other is to use varioussmart devices carried by people to obtain information. Here we propose a task allocation scheme for collaborative sensing. The methodaims to make the cameras and pedestrian to jointly cover the road network of the target area. We first calculate the importance value ofeach task. which can be used for prioritizing a bunch of tasks. Then we propose a method to evaluate the credibility of participants.This method is based on Euclidean distance ，，-hile involving a spatial distance attenuation function to compute the pedestrians' ，，-illing-ness and comhining with the task priority. Lastly， we propose mutual-choice task allocation （McTA） algorithm. The extensive evalua-tion on real dataset demonstrates that the proposed scheme can achieve over 95% task allocation rate.Key Words ： collaborative awareness ; greedy algorithm ; task allocation ; mutual choice
　　O 列言
　　近年來，得益于智能感知与普适计算等技术的发展，广泛应用于网络融合的协同感知技术成为研究热点。随着嵌入式设备、无线传感网络、物联网、智能移动终端的快速发展，具有集成感知、计算和通信能力的普适智能感知系统逐渐融人社会日常生活，智能感知获取数据的能力显著增强。
　　使用单一感知设备获取的感知能力有限，例如只使用预先部署的摄像机监控系统监控范围有限，监控位置固定，存在视觉死角。近年来，各类智能设备尤其是智能手机的普及使普通民众可以实时分享地理位置、周围环境等各类信息。将移动传感器网络与公共安全部门已有的摄像头监控系统相结合，实现协同感知，可弥补单一摄像头监控系统缺陷，得到更加可靠和全面的数据。设计科学合理的协同感知方法不仅可尽量降低感知代价，还可提高感知效率与感知系统整体性能，因此进行协同感知算法设计和改进意义重大。
　　随着监控摄像头技术的成熟，大部分城市均建有以摄像头为感知终端的监控系统，实现了对城市区域最大程度的覆盖监控。监控位置一般分布在人流量和车流量较大的道路交叉口和重要路段，监控系统可将监控范围内的实时情况上传到公安部门，确保公安人员及时掌握城市各区域最新动态，及时发现并处理公共安全问题。强大的监控网络为治理交通、治安等问题提供了有力的技术支持，合理的监控系统优化策略不仅可降低监控系统维护和运营成本，还可加大监控技术支持力度，大幅提高公共安全部门案件侦破效率。截至2019年6月，我国手机网民规模达8.47亿，上半年共计新增网民2598万人，网民中使用手机上网的人群占比达99.1%[1]-。近年来，处理器性能不断加强，智能手机迎来极大革新。可测量加速度的传感器、陀螺仪传感器、重力传感器、方向传感器等越来越多的复杂传感器成为智能手机标配。这些传感器让每一位携带手机的个体均可成为具备较强感知能力的终端，因此可将大量携带智能终端的个体组成协同感知网络，对特定目标进行观察、追踪等活动。 　　基于以上背景，本文提出一种基于贪心算法的面向协同感知的双向选择多轮任务分配（ Mutual-choice Task Allo-cation.McTA）算法。该算法将道路摄像头与携带智能终端的行人作为候选者，实现两种候选者协同感知，根据待分配任务节点特点及影响因素提出任务优先级计算方法，再根据不同种类感知节点特点，设计固定候选者及移动候选者可信度计算方法，最后根据任务优先级与候选者可信度得到任务分配最优解，从而有效分配任务。McTA任务分配方法加图1昕示.
　　1 相关工作
　　面向协同感知的任务分配方法主要涉及任务区域覆盖、固定或移动节点的任务分配。
　　1.1 任务覆盖
　　在任务分配中，需候选者集合对任务集合所在监控区域进行有效覆盖。现有相关研究聚焦于指定区域内的完全覆盖和最大范围覆盖两方面。文献[2]提出PCS任务分配模型，候选者可通过人群携带的智能手机等终端通话记录计算节点重要性，从而选择尽可能少的参与节点实现对监控区域最大程度覆盖，时间成本降到最低;文献[3]提出一种通过改进贪心算法计算基于最小顶点覆盖的最优摄像头部署方法，可保证覆盖城市的每一条道路;文献[4]和文献[5]介绍了若干不同种类的摄像头对任务节点进行最大程度覆盖监控的模型，摄像头对任务覆盖分为几何覆盖“1、拓扑覆盖[7]和过渡拓扑覆盖[8-9]等不同类型，文献[10]研究背景是公安部门通过监控系统追踪抓捕嫌疑人，为优化监控网络部署，该研究提出一种基于路网覆盖的城市监控摄像网络方法。
　　目前协同感知主要研究方向是对多种传感器进行合理布置、协同与管理，从而提高感知系统整体可靠性与效率。文献[II]针对传感器网络协同覆盖及动态调度问题，研究目标区域覆盖率及对特定目标的覆盖;文献[12-13]根据各类传感器特点，研究各类传感器感知范围，采用相应传感器部署方案对传感器网络进行整体管理和控制，实现区域最大程度覆盖;文献[14-15]研究感知节点之间的任务传递，实现了目标连续跟踪。
　　現有研究通过优化单一种类的传感器部署方式实现任务区域覆盖。对于感知网络来说，单一种类的传感器网络感知能力存在局限，例如只使用道路摄像头监控网络进行任务覆盖时，在监控范围外存在视觉死角。只由行人组成的感知网络也存在缺陷，如由于激励不够、代价过高导致任务无人执行等问题。因此，本文提出基于摄像头感知网络与行人感知网络的协同感知方法，以弥补单一种类传感器网络存在的缺陷，优化任务分配方案，从而最小化任务执行成本。
　　1.2任务分配
　　协同感知系统可实现对资源最大限度的配置和有效利用，更好地服务用户。任务分配算法性能对协同感知系统有直接影响，为得到最优的任务分配结果，协同感知系统需在任务端和候选者端两个角度进行权衡，优化任务分配。目前面向协同感知的任务分配算法主要存在两种形式：任务发布端分配方法、候选者端领取任务方法。
　　1.2.1 任务端发布
　　该方法从任务端角度出发考虑任务分配，首要指标是尽可能多地分配任务，即最大化任务分配数量。
　　如果一个任务点位于候选者较少或者没有的区域，则该任务最终被分配给候选者的概率较小;如果一个任务节点位于候选者十分密集的区域，则有多种分配方式。可通过定义任务节点度的方式给候选者分配较少区域内的任务。以更高的优先级，将该类问题转化为最小费用最大流问题16-17。先找出实现最大流的若干种解决方案，再从中挑选费用最小的方案。该算法使位于候选者稀疏区域的任务得到分配的可能性更大，但目前无法证明该算法可使被分配任务数达到最大。
　　在进行单个任务分配时，假如不考虑时间限制，且被选中的候选者均可靠地完成任务，则可将任务分配问题转化为二分图匹配问题[18]。。通常采用Ford-Fulkerson算法解决该类问题。但文献[18]采用贪心算法，所以得到的只能是近似最优解，而且没有考虑候选者执行任务的主观意愿，即使将任务分配给候选者，仍有可能存在候选者不去完成任务的情况，且该方法必须事先规定候选者能完成任务的最大数量，实际操作难度较大。
　　1.2.2候选者端领取任务
　　分支限界算法可用来寻找最优任务分配的方案，完整的解空间包括所有待分配任务的任何可能组合。文献[19]提出了启发式剪枝策略。如果一种潜在解决方案包含的所有任务数量低于当前已找到的局部最优解，则可排除该解决方案分支。但为了简化问题，所有T作者只能在固定大小的矩形区域内活动，这样的限制条件无法应用在实际生活中。
　　近似最优解的思想也可以应用于任务分配，比如按照任务过期时间进行任务排序，每次考虑过期时间最短的任务，如果将其加入到当前任务调度序列中，在满足任务过期时间限制的约束下，工作者若可到达该任务区域，则将该任务加入当前任务调度序列[19]。近似解算法优点是运算效率高，可用于大规模应用场景中。但该算法很容易被单个不合理的任务分配影响，导致最终分配结果不稳定，出现不合理的分配结果。
　　1.2.3 单任务与多任务分配
　　任务分配算法研究大多聚焦于单个任务，常见做法是从所有候选者中选择最佳候选者完成任务。通常涉及的约束条件包括最大限度降低能耗、降低激励候选者成本、扩大感知范围、提高感知质量等。文献[20]研究了一个招募框架，该框架以获取数据量最大的空间覆盖范围为约束条件选择最优候选者;文献[21]在选择可最大化完成任务的候选者中，考虑了候选者携带的智能手机电量消耗;文献[22]提出一种用于位置相关感知任务的最优任务分配方案，目标是最大化奖励，同时将每个候选者最长容忍时间作为约束;文献[23]提出一种涉及任务时间、移动成本、用户信誉等的分布式算法，供用户选择任务。该分布式解决方案实现了与集中式解决方案相当的性能;文献[24]设计了一个在线任务分配机制处理任务和参与者动态出现的移动群智感知场景;文献[25]设计了可信的调度机制，用于离线和在线时选择适当的参与者;文献[26]提m-种名为CrowdLet的在线任务分配策略，可通过招募请求者概率性遇到的合适的工作者，白行组织其进行任务群体感知活动。 　　目前，多任务分配问题研究较少。文献[27]研究了移动社交网络中的任务分配问题，其中作为请求者的移动用户可能有多个任务需要移动社交网络中其他用户提供帮助;然而，当另一个用户在其附近时，请求者只能收集数据再分配任务，时间成本较大。本文为请求者设计离线和在线任务方案，通过考虑其他用户移动模式，使所有任务完成时间尽可能缩短。针对待分配的任务集合，本文设计任务优先级计算方法，使重要任务可优先分配;根据候选者可信度计算方法，通过考虑候选者执行某项任务的主观意愿最小化候选者移动距离，从而缩短任务完成时间;基于双向选择机制与多轮分配方法，通过任务端与候选者端多次相互选择确定合适的任务与候选者，最终得到任务分配最优结果。
　　2 McTA算法架构
　　本部分主要介绍面向协同感知的双向选择多轮任务分配（McTA）算法。将城市监控系统中的摄像头作为固定候选者，将携带智能终端的行人作为移动候选者对任务集合进行分配，从而提出任务优先级计算方法、固定候选者可信度计算方法、移动候选者意愿值及可信度计算方法、双向选择机制和多轮分配方法。
　　2.1 任务优先级计算方法
　　为解决任务分配问题，需计算不同任务优先级、分配任务先后顺序。由于本文任务集合对应路网节点集合，所以首先考虑设置约束条件，计算路网节点优先级。影响路网节点重要程度的因素较多，如1个连接两条道路的路网节点与1个连接四条边的十字路网节点重要程度不同，找到类似影响因素作为约束条件即可区分不同任务点重要程度，从而计算出任务点优先级，确定任务分配顺序。
　　在一般网络结构中，不同节点重要程度和影响力是不同的。考虑到路网拓扑结构，对区域进行覆盖时，有3个主要因素影响任务重要程度，如表l所示。
　　2.1.1道路数量
　　图G=（V，E）代表由点和边组成的道路网络，其中V是图G中顶点集合，E是图G中边的集合。1个道路网络中的节点存在3种情况，即它连接的边数只能是两条、三条和四条，如图2所示。
　　在这种情况下，定义 为节点 连接的边的集合，若從节点i到其它任意节点？有一条边，则 ，否则 O;定义 为节点连接边数目，即一个节点一共连接了几
　　尹厚淳，崔禾磊，於志文，等：面向协同感知的任务分配方法条边，它体现了一个节点在路网中与周围节点的交互能力，对计算不同节点的重要程度有很重要的作用。因此在一个道路网络中，节点连接边数量S（i）可定义为：
　　如图2所示，S（i）可能的值为2、3、4。为了量化该类特征，本文定义节点连接边权重系数Edgeimp=0.25，则基于连接边数量的节点权重计算公式可定义为：
　　2.1.2道路等级
　　单以节点连接道路的数量衡量任务点优先级在一些场景下是不够的，如在图3中，同样连接3条边的两个节点由于连接的道路等级不同，实际上两种节点重要程度也不同，左图明显比右图节点更重要。
　　因此，影响优先级的另一个因素是节点连接的道路等级。参考文献[29]提出一种空间加权重要度模型，其中将道路类型分为高速路、普通主路、普通次路及支路，并赋予不同的权重值Rw，如表2所示。
　　本文提出基于道路等级的节点权重计算公式，定义为：
　　其中Rw为单条道路权重，RwSum为理论上连接所有道路集合的最大权重之和，如图4所示，节点imp2=0.7。
　　2.1.3道路长度
　　除道路数量、道路等级外，影响任务点优先级的第3个重要因素是节点连接的道路长度，通常认为道路长度越长，这条道路重要程度越高。因此本文定义基于道路长度的优先级计算公式，以计算节点优先级。
　　dis是节点连接的道路长度，Imax和Imln分别是实验区域内最长道路长度和最短道路长度，而RoadNum是该节点连接边数量。
　　综合以上影响任务节点优先级的3种主要因素，经过调整参数比例进行实验，本文定义影响任务节点优先级的3种因素以1：2：1的比例分配计算得到的效果最优，3部分之和为任务点最终优先级。
　　该方法将道路网络中节点连接边数、道路等级及每条道路长度作为主要影响因素，从网络拓扑结构角度计算节点优先级。
　　根据式（5）计算每个节点优先级后，在任务集合中按照优先级大小从高到低对任务点进行排序。
　　2.2 固定候选者可信度计算方法
　　协同感知指利用固定候选者（摄像头）及移动候选者（行人）对任务所在区域进行覆盖，设计任务分配算法，为待分配任务部署最好的候选者集合。但是摄像头和行人的特性不同，如摄像头位置固定，而行人对任务的选择带有主观意愿。因此本文定义可信度以量化候选者执行任务的可能性。
　　摄像头可信度主要衡量指标是摄像头监控范围，即摄像头监控范围内包含的任务点，摄像头对任务点的覆盖有两种形式：直接监控路网节点或监控节点连接的道路。由于摄像头安放位置是固定的，且通过监控系统可实现照射范围内24小时监控，如果可把任务分配给合适的摄像头，无论是从移动距离还是能量消耗来说，均比选取移动候选者的成本小很多，所以应优先考虑将任务分配给符合条件的摄像头，剩下不能由摄像头完成的追踪任务再交由移动候选者完成。
　　摄像头与任务点之间的距离直接决定摄像头能否对任务点进行有效监控，通常路口摄像头监控范围为lOOm。本文将摄像头与监控任务点的距离定义为摄像头可信度，采用欧式距离计算。
　　p为摄像头可信度，根据p的大小从高到低排序，并设置距离阈值为lOOm，距离小于lOOm且可信度最高的摄像头即为执行监控任务的最佳固定候选者。将计算好的待分配任务点与最佳固定候选者对应存放，当进行任务分配时，优先将任务分配给对应的固定候选者。
　　摄像头监控任务集合计算流程为：①获取同一区域内路网集合，得到路网节点经纬度。根据节点经纬度与摄像头位置经纬度计算两者之间的距离;②判断距离是否小于规定阈值，若小于阈值，则认为该摄像头可监控到该任务点，将距离作为可信度，并把该摄像头放入任务点对应的固定候选者集合中;若大于阈值，则认为距离太远，无法监控;③对于每一个任务点，将其对应固定候选者集合按照可信度大小从高到低排序，选取可信度最高的固定候选者与任务点一一对应。 　　2.3移动候选者可信度计算方法
　　由固定候选者完成的任务被分配完成后，剩下的任务考虑用移动候选者完成。在引入移动候选者任务分配时，候选者接收到任务信息后未必会执行任务，所以在移动候选者任务点可信度计算方法设计中需充分考虑候选者主观意愿。
　　2.3.1 移动候选者意愿值与可信度
　　研究人员尝试通过建立多种数学模型模拟距离对另一因素衰减的影响。本文参照文献[29]采用的距离衰减函数模型，定义表示候选者执行任务的意愿值will。根据任务经纬度及候选者所在位置的经纬度，采用公式（6）欧式距离计算某一时刻移动候选者到任务节点的距离d。由于移动候选者执行任务时需在一定时间t内以一定速度v行走到任务点，所以定义候选者在时间和速度限制下的阈值距离D计算公式为：
　　当候选者距离任务点的距离d小于阈值距离D时，通常认为候选者有一定概率会执行该任务;反之，当候选者距离任务节点的距离d大于阈值距离D时，则认为候选者无法完成该任务，即移动候选者对该任务节点的可信度为0。为刻画移动候选者执行某任务的意愿，本文定义符合空间距离衰减函数公式的移动候选者意愿值公式为：
　　当移动候选者与任务点距离小于阈值距离时，候选者执行该任务的意愿值符合空间距离衰减函数，其中）L为空间距离衰减系数。当距离d大于阈值距离时，候选者意愿值为0，即认为不能完成该任务。由该模型可看出，候选者距离任务点越近，执行该任务的意愿值越大;距离任务点越远，执行该任务意愿值越小。
　　综上所述，本文提出移动候选者对任务的可信度计算公式，以计算移动候选者执行任务的可信度。
　　2.3.2 双向选择与多轮分配
　　在移动候选者任务分配中，为得到任务分配最优候选者解的集合以确定移动候选者主观意愿，本文设计一种双向选择机制。在现实任务分配中，移动候选者通常倾向于选择执行可信度最高的任务，而移动候选者可信度包含影响行人选择的两个因素：①任务优先级。优先级越高，行人越倾向于选择该任务;②行人意愿值，即距离任务的远近。距离越近，行人越倾向于选择该任务。出于对移动候选者主观意愿的考虑，本文把任务分配划分成为两部分，从两个不同角度完成分配。
　　（1）候选者角度。对于每一个移动候选者，首先遍历待分配任务的集合，计算该候选者执行每个任务的可信度，并与每个任务形成对应。根据可信度大小由高到低对尚未分配的任务集合进行排序，找出此时该候选者最希望领取的任务，即可信度最大节点。由此可得到移动候选者集合与待分配任务集合的多对一映射关系，如图5所示。
　　（2）待分配任务角度。对于每个待分配的任务，由于选择固定候选者即摄像头的花费最小，所以优先考虑有无对应的摄像头。若找到，则将该任务分配给摄像头;若没有合适的固定候选者，则选择移动候选者。因为此时一个任务可能对应零到多个候选者，所以需根据对应候选者与该任务之间可信度大小从高到低对每个任务对应的候选者集合进行排序，选取可信度最大的候选者。由此得到候选者集合与待分配任务集合一对一映射关系，如图6所示。
　　最终得到的候选者集合与待分配任务集合的一对一映射，即为经过双向选择机制得出的移动候选者任务分配近似最优解。双向选择机制存在1个问题，即有的任务原本存在可执行者，但在双向选择过程中，由于可信度不是最高的，而双向选择机制只会选取可信度最高的任务与候选者相匹配，从而导致其它本可以执行的任务被抛弃，降低了任务完成数量及效率。因此本文设计一个多轮分配方法，即当可信度最高的任务完成后，将其从待分配任务集合中删除，再将完成任务的移动候选者添回至候选者集合，对剩下的任务进行新一轮任务分配，依此类推，直到所有可执行任务均被分配。
　　2.4 面向协同感知的任务分配方法
　　为了最大化任务完成数量，本文提出面向协同感知的双向选择多轮任务分配方法-McTA算法。
　　在McTA算法中，对于待分配任务集合T中的每个待分配任务Ti，通常在道路路口节点对任务Ti进行监控，所以可将路口节点集合作为待分配任务點集合，找出执行任务的最佳候选者。
　　对于任务 ，首先利用任务优先级计算方法计算其优先级，并按照优先级高低对任务进行降序排序;其次，进行固定候选者任务分配（摄像头执行任务的花费相对较低，所以优先采用摄像头），找到每个摄像头可监控到的任务点，再计算移动候选者到达每个任务点的意愿值，根据意愿值与任务优先级计算每一个移动候选者执行每一个任务的可信度;最后对可信度排序，选择可信度最大的移动候选者与任务点一一对应。
　　在任务分配阶段，对于待分配任务集合中的每个任务，首先寻找是否有距离最近且可监控该任务的固定候选者，若存在，则将该任务分配给对应摄像头。遍历待分配任务集合后，将可由固定候选者执行的任务分配完毕，仅余应由移动候选者执行的待分配任务。对于每个任务，找到所有在该任务范围内的移动候选者，并根据可信度再次排序，选取可信度最高的移动候选者执行该任务。再次遍历待分配任务集合后，第一轮任务分配结束，接着，将已执行的任务从待分配任务集合中删除，并将所有移动候选者重新加入到候选者集合中，再进行新一轮任务分配，并重复上一轮任务分配的操作，以此类推，直到所有可分配的任务均被完成，最终输出执行结果。
　　算法具体流程如下所示。
　　输入：任务集合Task，同定候选者集合C（摄像头），移动候选者集合W（行人）
　　输出：完成任务集合T’，T作者集合W'
　　1.FOR each x∈Task
　　2.计算任务集合Task中任务T.的优先级Pr
　　3.ENDFOR
　　4.根据优先级Pr对任务T 排序
　　5.FOR each x∈C
　　6.建立与C.对应的集合TC存放C。可以监控到的任务点 　　7.FOR each x∈T
　　8. 统汁C中每个摄像头C。可监控到的任务点T.
　　9. TC←T.
　　10.ENDFOR
　　11.ENDFOR
　　12.FOR each x∈W
　　13.计算行人W 的意愿值
　　14.建立集合B存放行人执行任务T：的可信度B。
　　15.FOR each x∈Task
　　16.计算行人执行任务的可信度B.
　　17.B←B，
　　18.ENDFOR
　　19.对B内元素排序，选取可信度最大的任务Tmax与W;对应
　　20.ENDFOR
　　21.While T中有可完成任务Do
　　22.从任务集合Task中选取任务T.
　　23.IF Ti有对应摄像头，则跳转至23
　　24.FOR each x∈W
　　25.找到所有可执行该任务的候选者W。存放在集合TW，排序
　　26. ENDFOR
　　27.选取可信度最大的候选者W。
　　28.W←W-W：W’←W。
　　29.T←T-TiT’←T。
　　30.End
　　31.IFT<上一轮任务剩余数量
　　32.初始化W，增加被删掉的所有候选者，返回到21，执行新一轮任务分配
　　3 实验评估
　　本部分主要介绍在若干特定区域内进行的实验，并对实验结果进行评估。通过与基线方法进行对比，对任务分配方法在覆盖率、成本、运行时间等方面进行性能评价。
　　3.1 实验数据采集与预处理
　　本文实验选取成都市区路网数据作为待分配任务集，选取成都市区内道路摄像头分布位置数据作为固定候选者数据集，选取成都市区内行人签到数据作为移动候选者数据集。
　　首先，将整个成都路网划分为多个小实验区域，在路网数据集中找出边界区域经纬度，以确定实验数据所在区域。实验区域经度范围为30.3346。-30.9255。;纬度范围为103.740 5。-104.432 7。。根据实验区域范围，将成都市区划分成网格，每个网格就是1个实验区域，区域ID从1开始依次编号，按区域划分实验区域后，在若干区域内进行实验。
　　3.2任务优先级计算方法性能分析
　　为了更好地体现任务优先级计算方法区分不同任务的效果，本文首先选取任务数量适中、任务种类较多、特点全面的编号776区域数据集进行实验。该区域内共有48个任务点、16个摄像头、1633个行人。对于区域内的48个任务，采用优先级计算模型计算任务优先级，优先级数据处理结果如表3所示（截取其中15条数据），最后将所有48个任务按优先级从高到低排序。
　　为评价优先级计算模型性能，本文引入基线方法与之对比，基线方法按路口连接道路数量计算任务优先级，即该方法优先级共有3种情况：连接二、三、四条道路的节点优先级分别为2、3、4。衡量本文优先级计算方法与基线方法计算优先级差别的指标计算公式为：
　　β代表单个任务优先级在总优先级中的占比，占比越高，说明该节点越重要。
　　如图8所示，选取776区域的15条数据与基线方法进行比较。可以看出只考虑任务点连接道路数量的基线方法与考虑了3种因素的本文方法计算出的优先级结果差别较大。基线方法由于优先级计算方式单一，不同任务点的优先级都比较接近，离散程度不高;而本文采用的优先级计算模型由于加入了影响任务点重要程度的不同因素，使不同任务点优先级计算结果离散程度大幅提高，考虑道路数量、等级、长度可更好地区别不同任务点之间的差异。与传统基线方法相比，本文方法使不同任务点基于优先级的区分度更高。
　　例如在图7中利用基线方法计算任务点2和任务点14的B值，均为0.1，但数据集中任务点2连接了两条高速路和两条普通主路，而任务点4连接了一条高速路、两条普通主路和一条支路，显然任务点2应该比任务点4的优先级更高，采用本文优先級计算模型可很好地反映该点;再比如任务点5与任务点6均连接了3条道路，在普通基线方法中两个任务优先级仍是一样的，但是由于任务点5相比于任务点6连接的道路等级更高、距离更长，所以优先级更高，这在本文优先级计算模型中也得到了体现。从图7可以看出，本文方法与基线方法对实验中每个任务点优先级结果差异均较大，但总体走势一致，说明本文方法对其优先级刻画效果更好。
　　综上所述，本文提出的任务优先级计算模型更全面地考虑到了影响任务优先级的诸多因素，使优先级计算方法多样化，有效体现了不同节点之间的差异，其性能优于普通基线方法。
　　3.3 任务分配算法性能分析
　　3.3.1 两种候选者任务分配
　　对于776区域的48个任务，将其中20个任务分配给固定候选者，26个任务分配给移动候选者，还有两个任务处于候选者死角，无法完成。鉴于城市监控摄像头可实施24小时监控，可认为分配给摄像头的20个任务在监控范围内，因此将其完全分配给相应摄像头。将任务点与合适的摄像头对应起来，当进行任务分配时，若有该任务的映射，则将任务分配给对应摄像头。剩下任务则由行人完成。
　　剩下的26个任务处于摄像头监控范围之外，所以需调用行人对其进行监控。由于1个任务可以分配给多个候选者，所以根据移动候选者可信度选择执行任务的最佳候选者，本文将任务分配给可信度最大的候选者。
　　3.3.2 移动候选者数量对算法的影响
　　为了研究不同候选者数量对McTA任务分配算法的影响，本文把随候选者数量变化的任务分配数量、任务分配执行轮次、算法运行时间及任务完成率等作为评价指标。随机选取若干区域，将这些区域的移动候选者数量分别设置为200、400、600、800、1 000、1 200、1 400、1 600。 　　在任务分配过程中，候选者数量对实验结果的影响较大。候选者越多，任务分配的选择越多，任务被执行的可能性越大;候选者越少，任务分配的选择越少，任务不被执行的可能性随之增大。在若干不同实验区域，任务完成数量随候选者人数的变化如图9所示。
　　由图9可以看出，第一轮可分配的任务数量随候选者数量的增加有明显增加趋势。在图10显示的分配结果中，任务分配的最终未分配任务数目随候选者数目的增加而减少，说明候选者人数越多，任务完成效果越好。但是由于777区域任务数目较少，未分配任务数目虽有下降但不明显。665、666、779区域任务数量较多，因而趋势十分明显，尤其是在候选者人数从200增加至800的区间里，任务分配效果变化较快。这说明区域内待分配任务数目越多，算法执行效果越好，而且区域内可执行任务的候选者人数越多，McTA任务分配算法效果越好。
　　由于McTA算法是双向选择的多轮次任务分配方法，故需明确移动候选者数目变化对McTA算法执行任务分配轮次的影响。实验结果如图11所示，从中可以看出，候选者数目越多，McTA算法执行的轮次越少，任务分配完成时间越短。对于779和666区域，由于这两个区域内任务节点数相对于其它区域较多，候选者越多，单次分配过程中执行的任务数量就越多，所以任务分配总轮次越少。对于任务节点数量越多的区域，McTA算法越能体现其显著效果。而对于777区域，由于只有48个任务节点，故McTA算法分配效果随候选者人数的变化不明显。综上所述，McTA算法更适合应用于任务数量规模较大的任务分配问题。
　　候选者数目变化还可能影响任务分配算法整体运行时间。如图12所示，在选定的5个区域内，候选者人数越多，McTA任务分配算法运行时间越长。可以看出在候选者人数相同的情况下，编号779实验区域算法执行时间长度明显长于其它区域，这是因为779区域内任务节点数相对较多，由此可见任务节点数量影响运行时间。
　　3.4任务分配效果
　　在整个城市道路网络中，每个区域均各有特点，例如有的区域任务少，候选者多;有的区域任务多，候选者少。为验证McTA算法在不同区域进行任务分配的性能，定义任务分配完成率为：
　　在区域集合中随机选取若干实验区域进行任务分配，其任务分配完成率如图13所示。可以看出当区域内候选者数量较少时，任务完成率较低，有的区域完成率仅为60%-70%，原因是候选者少，但是待分配任务多。当候选者增加到一定数量时，例如1 200名以上时，任务数量对完成率的影响程度大幅降低，这些区域内任务分配完成率达到90%以上。说明当区域内候选者足够多时，McTA算法可完成大部分待分配任务。
　　5 结语
　　首先，本文设计了任务优先级计算方法。该方法根据任务节点的不同特点量化任务重要程度，体现了不同节点之间的差异，可有效地计算不同节点优先级;然后采用欧式距离计算固定候选者可信度，利用空间距离衰减指数函数计算移动候选者执行某项任务的意愿值，再根据意愿值与任务优先级确定候选者其可信度;最后，提出任务节点与候选者的双向选择机制以及多轮分配方法，最大限度地优化分配结果。实验结果表明，在本文数据集内，该算法可有效地对任务进行分配，当候选者达到一定数量时可保证任务分配完成率保持在95%以上，其性能優于普通任务分配方法。
　　下一步将针对监控摄像头任务分配问题，重点改进可信度计算方法。本文方法从距离尺度上衡量摄像头能否监控到特定目标，实际生活中环境更加复杂，下一步研究将考虑更多影响摄像头可信度的潜在因素。而行人可信度受多种因素影响，例如不同社会身份的行人（如公司职员或失业人员）对分配任务的执行概率不同，仅从阈值距离的角度对其可信度进行评估的作法相对简单，未来将加入更多影响因素，使该方法更贴近实际。
　　本文实验将整个路网按网格划分成若干实验区域，在单个实验区域内进行实验。在实际生活中，虽然网格划分是不存在的，但不同实验区域内的节点同样存在很多联系，采用网格划分会使某些可以去执行其它区域任务的候选者被限制在一个特定区域内，从而忽略掉其它可能的更优解。因此为去除网格模型带来的不利影响，更细粒度地设计跨网格任务分配方法，下一步将研究不同实验区域节点、候选者等之间的联系，从而更好地提高任务分配完成率及算法效率。
　　参考文献
　　[1] 中国互联网络信息中心 .中国互联网络发展状 ，X统计- [EB/OL ] .http ： //w，n， .cnnic .net.cn/hlwfz） j/hlwxzbg/ssbg/20 1 9 10/P020 1 91025506904765613.pdf
　　[2] ZHANC D. XIONC H. WANC L. et al. CrowdRecruiter： selecting
　　[3]魏浩，陈华锋，陈军，基于路径覆盖的城市监控摄像网络优化部署方法 [J]. 计算机工程 ， 2016， 42（ 5） ： 269-274.
　　[4] MAVRINAC A. CHEN X. Modeling coverage in camera networks： asurvey [Jl. International journal of computer vision ， 2013 . 101 （1 ） ：205-226.
　　[5] MARIhrAKIS D， DLiDEK G. Topology inference for a vision-based sensor netwnrk [ C ] . Conference on Computer & Rohot Vision . 2005 ：121-128.
　　[6]ERDEM L M. SCLAROFF S. Automated camera layout to satisfytask-specific and floor plan-specific. coverage requirements [J] . Com-puter Vision &. Image Understanding， 2006 ， 103（ 3 ） ： 156-169. 　　[7]MAVRINAC A ， CHEN X， TEPE K. An automatic calibration methr）dfor stereo-based 3D distributed smart camera networksFJl. ComputerVision and Image Understanding， 2010， 1 14（ 8） ： 952-962.
　　[8]SONC B . KAMAL A T. SOTO C . et al. Tracking and acti，'ity recr，gni-tion through consensus in distributed camera networks [Jl. IEEETransactions on Image Proc：essing ， 2010， 19（ 10） ： 2564-2579.
　　[9]ELLIS T， BLACK J， XU M. et al. A distrihuted multi camera surveil-lance system[M ]. New York ： Springer， 2005.
　　[10]PHAM O C， LAPEYRONNIE A. BALDRY C. et al. Audio-.'ide。surveillance system for public transportation [ C ] .
　　International Con-ference on Image Processing Theory Tools & Applications， 2010：47-53.
　　[ll]LANr G L. MA Z M， SUN S S. Coverage problem of wireless sensornetworks [ C ] . China-Japan ConfPrence on Discrete Geometry ， 2005 ： 88-100.
　　[12]FANC C . LO" C P. Redundant coverage in wireless sensor networks[C]. IEEE International Conference on Communications. 2007：3535-3540.
　　[13] GHOSH A. DAS S K. Coverage and connectivity issues in wirelesssensnr networks： a survey EJl. Perrasive & Mobile Computing，2008， 4（3） ：303-334.
　　[14]CHAKRABARTY K. IYENGAR S S， 01 H， et al. Grid corerage forsurveillance and target location in distributed sensor networks [Jl.IEEE Transac.tions on Computers ， 2003 ， 51 （ 12） ： 1448-1453.
　　[15]WANG X， YANC Y T. k-variable morement-assisted sensor deploy-ment hased on virtual thornh grid in wireless sensor networks [C].Proceedings of the Second IEEE international conference onSelf-Managed Netwnrks . Svstems . and Services . 2006 ： 173-183.
　　[16]KAZEMI L， SHAHABI C . CHEN L. CeoTruCrowd ： trustworthy que-rv answering with spatial crowdsnurcing [ C ] . ACM Sigspatial Inter-national Conference on Advances in Cengraphic Information Sys-tems . 2013 ： 314 ～ 323.
　　[17]CEThrET H. Minimum cost maximum flow prohlem[D]. Addis Aba-ba ： Addis Ahaba University， 2017.
　　[18]KAZEMI L， SHAHABI C. GeoCro.vd ： enahling query answering withspatial c.rowdsourcing [ C] . International Conference on Advances inCeographic Information Systems ， 2012 ： 1 89-198.
　　[19]DENG D X. SHAHABI C. DEMIRYUREK U. et al. Task selectionin spatial crowdsourcing from worker' s perspective [J]. Geoinfor-matica. 2016. 20（ 3） ：529-568.
　　[20] REDDY S. ESTRINr D. SRIVASTAVA M. Recruitment frameworkfor participatr，ry sensing data collections [C]. Helsinki ： PervasiveComputing ， Internatir，nal Conference . 2010. 　　[21]CARDONE G， FOSCHINI L. BELLAVISTA P. et al. Fostering par-ticipation in smart cities： a geo-social crowdsensing platform [Jl.IEEE Cnmmu nications Magazine ， 2013 . 51 （ 6） ： 1 12-1 19.
　　[22]HE S， SHIN D H. ZHANC J， et al. Toward optimal allocation of lo-cation dependent tasks in crowdsensing [C]. IEEE Conference onComputer Communications ， 2014 ： 745-753.
　　[23] CHEUNG M H，SOUTHWELl R， HOU F. et al. DistributedTime-Sensiti.'e Task Selection in Mobile Cro，，'dsensing [C ] . Prr）ceed-ings of the 16th ACM International Symposium nn Mnbile Ad Hochretworking and Computing， 2015 ： 157-166.
　　[24] TONG Y. SHE J， DING B， et al. Online mohile micro-task alloca-tion in spatial crowdsourcing[ C ] . 2016 IEEE 32nd International Con-ference on Data EngineeriW ， 2016 ： 49-60.
　　[25]HAN K. ZHANC C. LLO J， et al. Truthful scheduling mechanismsfor powering mobile crowdsensing [J]. IEEE Transactions on Com-puters， 2016， 65（ I ） ： 294-307.
　　[26]PL L. CHEN X. XU J. et al. Crowdlet： optimal wnrker recruitmentfor self-organized mobile crowdsr，urcing [ C ] . The IEEE Internation-al Conference on Computer Communications . 2016 ： 1-9.
　　[27]XIAO M. WL J. HUANG L， et al. Multi-task assignment for crowd-sensing in mohile social networks [ Cl. IEEE Conference on Comput-er Communications ， 2015 ： 2227-2235.
　　[28]DEhrG D X. SHAHABI C. ZHL L H. Task matc.hing and schedulingfor multiple wnrkers in spatial crnwdsourcing Fcl. Prr）ceedings ofthe 23rd SICSPATIAL International Conference on Advances in Cen-graphic Information Systems， 2015 ： 1-10.
　　[29]WAN Nr. ZHAN F B. CAI Z. A spatialb- weighted degree model fornetwork vulnerahility anab'sis [J] . Ceo-Spatial Infnrmation Science ，2011. 14（ 4） ： 274-281.
　　[30]SEVTSLK A. Location and agglonieration： the distrihution of retailand food husinesses in dense urban enx'ironments FJl. Journal ofPlanning Education and Research， 2014， 34（ 4） ： 374-393.
　　收稿日期：2020-04-28
　　作者简介：尹厚淳（1997-），男，西北工业大学计算机学院硕士研究生，研究方向為普适计算、移动群智感知;崔禾磊（1987-），男，博士，
　　西北工业大学计算机学院副教授，研究领域为云计算安全、多媒体安全;於志文（1977-），男，博士，CCF高级会员，西北工业大学计算机学院教授、博士生导师，研究方向为普适计算、社会感知计算、人机交互;王亮（1984-），男，博士，CCF会员，西北工业大学计算机学院副教授，研究方向为移动群智感知、城市计算;郭斌（1980-），男，博士，CCF高级会员，西北工业大学计算机学院教授、博士生导师，研究方向为移动群智感知、大数据智能。
转载注明来源:https://www.xzbu.com/8/view-15247562.htm