基于用户关注度以及时间监督的任务分发

张 力1 张书奎1 刘 海2 张 洋1 陶 冶1 龙 浩1 于淳清1 祝启鼎1

1(苏州大学计算机科学与技术学院 江苏苏州 215006)

2(淮北师范大学计算机科学与技术学院 安徽淮北 235099)

(greenwuhu@126.com)

摘 要 在群智感知器网络中,如何在限定时间内完成发布者指定的感知任务,是移动群智感知任务分发面临的一个重要问题.针对该问题,为了使感知用户间密切协作,并及时将执行感知任务反馈给发送者,提出一种基于用户关注度与时间监督的任务分发(task distribution with user attention and time supervision, TDUATS)算法.该算法首先提出了用户间关注度,执行任务的起始监督、过程监督、完成监督等概念,然后通过分析执行感知任务的用户间关联关系,建立用户间关注度模型,对执行任务的过程进行监督,在此基础上对感知任务进行分发. 实验结果表明,该算法不仅可在限定时间内完成感知任务,而且还可以监督任务执行的过程;有利于发布者及时了解任务的执行情况,对提高任务执行的满意度起到了很好的促进作用; 同时,与对比算法相比较,也有较好的性能表现.

关键词 移动感知器网络;感知任务;用户关注度;时间监督;任务分发

自2006年,Howe[1]定义了“用电话方式通知不确定的一群人(通常称为工人)来完成通常个人难以完成的感知任务行为”以来,人们用“群智”来解决困难问题取得了非常好的效果.当前,智能设备中嵌入各种传感器是常见的事情,这些传感器可以帮助人们获取想要的信息.Wang等人[2]研究了群智感知中最常见的问题——任务分配.传统无线传感器网络中感知节点通常是功能专业的传感器,部署复杂,安装费用高.而群智感知中的感知节点利用工人高度自治的嵌入式智能设备.伴随无线技术应用不断提升,尤其是功能强大的5G技术普遍应用,可以充分利用“闲散”的功能强大的智能设备帮助人们解决复杂问题.

群智感知利用感知功能,相互之间协调合作,不仅可以完成短期的收集城市交通流量信息[3]、停车位检测[4],而且可以感知长期感知任务、危险山区地形检测[5]、空气质量监测[6]等,都能够非常好地完成感知任务.

Fig. 1 Location sensing task
图1 位置感知任务

图1显示,这些应用中的感知任务通常依据任务所在的位置进行分发,网络中的“悠闲”用户利用智能设备完成感知任务.该方式的核心是通过众包进行,任务的分发会考虑用户状态、环境信息、社会属性等.感知任务分发位置[7-9]和完成感知任务时间[10-11]是任务的最基本属性,挖掘感知任务位置的自身特征,更能体现对任务的本质揭示.一般来说用户间的稳定关系以及相互之间的依赖性,能更好地协作完成感知任务.感知用户间频繁接触,可使用户间形成良好的偏好关系.挖掘用户之间友好关系对任务分发的影响,可以提升任务分发的准确度.对感知任务完成时间已有部分研究,多数研究主要关注的是完成感知任务最小时间,如平均最小完成时间和完成感知任务的总时间最小.对任务执行过程,没有很好地监控,对于任务的完成情况影响很大.因此,本文从任务参与者之间的关系,以及任务完成感知过程中的时间监督,研究对感知任务的影响.

本文主要贡献包括3个方面:

1) 通过分析执行感知任务用户之间的关系,提出用户之间的单关注度、互关注度以及多关注度概念.

2) 根据完成感知任务的时间要求,提出感知任务完成过程时间监督定义,通过分析用户之间的关系以及时间监督对移动群智感知中感知任务分发的影响,将用户之间关系强弱和时间监督作为感知任务影响因素,提出用户关注度与时间监督的感知任务分发(task distribution with user attention and time supervision, TDUATS)算法.

3) 在真实数据集上进行了感知任务分发实验.结果表明,所提出的算法(TDUATS)从关注度和时间监督对感知任务分发的影响,以及随着感知任务数目增加任务分发成功率都有不同程度的提升.

1 相关工作

移动用户携带嵌入丰富智能的传感设备,将移动技术和群智感知结合起来,出现了许多创新的商业模式,使学术和工业界都备受关注.这些应用中需要考虑不同感知位置、完成感知任务的时间约束、移动成本和信誉等用户任务的选择问题.感知任务分配是NP难问题.怎样高效分发感知任务是群智感知中的研究热点问题,常见任务分发如图2所示.

Fig. 2 Sensing task distribution
图2 感知任务分发方式

当前,无线技术无处不在,基于移动通信的群智感知已经被广泛应用,用户在感知任务的位置时,移动轨迹信息容易暴露,使得用户感到非常不安全.Pournajaf等人[12]通过任务管理使参与感知用户间的敏感信息避免收到威胁,并应用于相关的群智感知中.Sherchan等人[13]为了减少发送数据量以及手机能量消耗,采用挖掘数据实现可扩展的数据收集.根据感知用户实时移动的位置信息,提供了一种有效的移动群智感知策略.Ma等人[14]为了提升推荐的成功率,通过研究用户之间的相关性,为没有标记和较少标记的用户添加标记,构建用户之间的标签矩阵,获取用户的标签权重,设计了用户之间的迭代兴趣机制.该机制是对没有标记或很少标记添加标签,这些用户是否可靠信任,难以保证推荐的满意度.Wang等人[15]通过对用户的感知区域和感知时间进行分割,划分为更小的区域和时间段.由感知用户覆盖区域,感知区域以及感知时间构建感知用户间的任务效用评价,结合感知用户移动模型,分析用户效用质量的模型理论,使感知用户任务效用质量最大化.对感知区域和感知时间进行了分割,增加了搜索的规模,却没有对划分的更小时间段进行更细致的监督.于瑞云等人[16]通过用户之间的接触时间和接触次数来衡量用户之间的关系强弱,如果用户之间接触时间越长,接触次数越多,则说明用户之间的关系越强,反之则反.通过用户之间的相关性构建用户位置预测模型.该模型采用2阶Markov模型,可能会导致搜索状态空间过大,搜索时间过长.杨金劳等人[17]根据用户之间的共有群信息,计算用户之间的相关性,以获取其他用户的偏好,为了减少用户的搜索过程和检索时间,提升推荐成功率,采用均值与最小痛苦策略融合修正满意平衡策略.而满意度修正采用最小痛苦策略,也就是最小评分策略,难以保证群组中的用户的满意度.文献[18]为了减少僵尸网络对移动互联网的入侵,研究了用户活动之间的相关性和人工免疫监测系统.创建tweet的签名和bot行为签名库,在Twitter,Facebook,YouTube等社交媒体上进行监测,获得不错的效果.该模型仅仅考虑用户的活动时间相关性,2个活动时间相同并不能保证其完成任务的质量.

有很多学者从不同角度研究感知过程消耗的时间对感知任务的影响.Xiao等人[19]根据用户在社会网络中的历史数据,预测用户的移动轨迹.任务的处理时间分为:用户与任务发起者的相遇时间、移动用户完成任务的执行时间和任务结果返回给任务发布者的时间.设计了完成所有任务的最小化最长完成时间任务分配算法.该算法中加入用户等待时间,等待时间可能很长,这样增大了任务的平均时间,也没能体现具体不同时间段对感知任务的影响.Lu等人[20]在传感器感应半径和相同的传输半径前提下,为了找到目标覆盖和数据收集的最大化,在目标区域覆盖密度有界的条件下,提出多项式时间常数因子近似算法.实现实时预测出租车目的地及乘客下车地点服务推荐的估算.Chen等人[21]利用2阶段法,由GPS轨迹数据降点聚类与城市空间候选活动区域匹配,提取行为细粒度时空模式,获取估算目的地和下一目的地推荐服务.Ma等人[22]以时间、容量和报酬为限制,匹配最佳出租车乘车共享接机.平衡乘车人付费和出租车行驶最小化距离来满足请求人的出租出行需求,为乘客和出租车设计了快速搜索算法.该算法仅讨论了距离最小化,却没有体现任务执行过程中乘客对任务执行过程的满意度.

对于有时间约束,与感知任务位置息息相关的分发任务,为了找到最佳任务参与者,He等人[23]设计了局部比率算法,使分配者的总奖励与局部比率逼近某个常数,基于议价理论设计定价机制,可以找到任务的最佳分配.To等人[24]为了实现降低众包数据收集成本和周转时间,在预算固定时间戳限制下,设计了超局部空间众包,可以提供细粒度感知数据,激励感知任务时空附近的工人积极参与感知活动.然而在时间戳内,任务执行的怎么样,能否满足发送者的请求,如果任务执行过程不满意,怎么调整等,这些都没有进行分析.为了提高出租车共享系统的性能,Li等人[25]采用自适应邻域搜索方法,进行固定样本、近似平均样本和顺序采样策略.结果显示采用固定样本可以提高出租车共享系统性能.可固定样本策略不够灵活,不能满足实时需求.Xiao等人[26]在移动群智感知协助活动中,利用截止日期敏感的概率协助,为移动群智感知任务招募用户,采用非线性编程约束和非平凡覆盖的形式化表示,在预期时间内持续招募更多用户算法,协作完成困难任务.

为了在一组骑乘车辆中找到最大持续时间和最大用户乘车的最低成本路线.Gschwind等人[27]在摊销固定时间算法中通过请求插入的可行性,使所提算法在路由选择方面优于对比算法.龙浩等人[28]研究了社区中移动节点之间的行为模式,计算节点之间的最小距离和社区融合度.该模型将用户合理地分配到不同的社区,通过计算感知任务和社区行为之间的匹配度,然后根据社区间匹配度分发感知任务.仿真实验显示,社区任务分发算法降低了任务完成时间.

目前感知任务研究主要集中于用户位置之间距离或感知任务时间花费等.基于位置的任务分发,常以感知任务为中心,选择感知任务位置空间关联较近的参与者,仅仅考虑位置远近,不能反映用户是否能够胜任要求完成的感知任务.对于感知任务时间问题,常考虑任务完成顺序以及完成任务所需时间最优化问题.而任务完成时间长短只是任务完成的时间限制,不能代表任务完成的好坏.

因此,感知任务的分发考虑感知用户之间的关联关系对任务分发成功的影响,以及在感知任务执行过程中用户之间的交互.为了深入考虑感知用户和感知任务时间对感知任务的影响,本文提出基于感知用户之间的关注度及感知任务时间监督等级,并分析其对感知任务分发的影响.

2 任务关注度分析

感知器网络中感知用户和接受者之间看上去没有联系,没有规律.如果能挖掘出参与者之间的内在联系,有利于感知任务的完成.任务的发布与接收,常常与参与者之间的关系紧密联系,找到最佳完成任务要求的接受者,则可以提升感知任务的完成效率.

2.1 用户之间的相关性

感知器网络中的用户有2种典型的行为:接收其他用户的任务请求和发布任务.

图3表示用户及任务之间相互关注,相互关注是用户和任务之间关联关系.感知器网络中用户与地理位置、用户行为、用户移动轨迹和专业知识等因素有关,因此用户所关注的感知任务就有所不同.共同关心某一类任务,说明这些用户之间对此类任务熟悉或可胜任类似的任务.如果能够胜任类似任务,说明他们具有完成这些任务的能力,感知用户之间相似程度会非常高.因此,我们从感知用户对任务的关注程度出发,探讨感知任务分发.

Fig. 3 Mutual attention among user tasks
图3 用户任务间的互关注联系

同一用户胜任多种任务关注度(one user to multi-tasks, OMT)记为O.某一用户能够完成多种类型的任务.图4中用户u1可以胜任2种任务.

Oi=Ntaski/Nui.

(1)

Oi表示第i个用户的OMT,Ntaski是完成第i个任务的次数,Nui为用户i完成所有任务的次数.

Fig. 4 Competent for multiple tasks of the same user
图4 同一用户胜任多种任务

多个用户完成同一任务关注度(multi-user to the same task, MUST)记为M.图5中用户u1和用户u2都可以胜任任务task1.说明用户u1和用户u2对任务task1的要求度有非常高的相似性.Mi表示第i个MUST.

Fig. 5 Multi-user sensing of the same task
图5 多用户感知同一任务

Mi=Ntaskiitaskij/Nui+uj.

(2)

Ntaskiitaskij是用户i和用户j完成第i个任务的次数,Nui+uj表示用户i和用户j完成所有任务的次数.

用户与任务之间相互关注(user and tasks focus on each other, USTF)记为U.图6表示用户u1接受感知任务task1,同时感知任务task1的发送者也能胜任用户u1发布的任务.两者之间能够互相帮助完成彼此的任务,说明他们之间有共同的“话题”,两者趣味相投,一定会尽力完成彼此要完成的任务.

Fig. 6 Inter user sensing task
图6 用户间感知任务

Ui表示第i个USTF,计算为

Ui=Ntaskitaskj/2Nui+uj.

(3)

Ntaskitaskj是完成彼此任务的次数,Nui+uj为用户i和用户j完成所有任务的次数.

感知用户之间的关联性体现为:感知用户间能够互相完成相同或类似的任务.对于将要发布的任务,有利于找到合适的用户.因此,我们挖掘出用户与感知任务之间的3种关系,建立用户之间的关联关系.

根据用户的轨迹数据,由轨迹数据寻找用户之间的关联关系,利用轨迹数据的关系,推测出用户完成感知任务的相似程度.我们用Xijk表示根据轨迹数据获取的用户关注度,Yijk表示预测值,那么用户之间的XijkYijk的相似度越高则说明用户间的相似行为越高,表示为

XijkYijk.

(4)

为了使Xijk-Yijk趋向于0,又因Xijk-Yijk有正负,同时为了计算方便,即使(Xijk-Yijk)2最小.

Zmin=(Xijk-Yijk)2+α(Oi+Mi+Ui)2.

(5)

式(5)中Zmin为(Xijk-Yijk)2的最小值,为了调节Zmin的最小值,需要加上(Oi+Mi+Ui)2Oi,Mi,Ui分别为用户第i个任务的OMT,MUST,USTF,α为调节因子(推导公式只考虑正值).

Zmin=(Xijk-Yijk)2+α(Oi+Mi+Ui)2,
0=2(Xijk-(Oi+Mi+Ui))Oi+
2α(Oi+Mi+Ui)Oi
0=Xijk-(Oi+Mi+Ui)+α(Oi+Mi+Ui),
Xijk-Mi-Ui+α(Mi+Ui)=Oi-αOi.

可以得到:

(6)

同理得到:

(7)

(8)

式(6)表示第i个任务的OMT关注度,是感知任务用户获取的轨迹数据关注度、同一任务关注度和用户任务间的互关注三者之间的度量关系,α是调节因子,本文中的α=0.6.式(7)、式(8)分别表示轨迹数据关注度OMT和USTF之间的度量关系、轨迹数据关注度OMT和MUST之间的度量关系.

2.2 时间监督

感知任务时间通常被用来衡量感知任务是否执行完成、完成所有感知任务时间最短、平均完成时间最小等问题,对感知过程没有具体化.

在某一段时间内,当感知任务刚被接受者接受时,希望发送任务的用户能把任务的具体要求说清楚,发送者与接受者之间就需要进行交互,是为了更好地完成发送者的任务.在感知任务执行的过程中,要对正在进行的任务完成情况向发送者汇报,沟通任务执行情况是否符合发送者的要求.如果任务完成情况与发送者有差距,则可以及时进行调整.在任务基本完成时,双方应及时进行交流,使发送者了解任务完成的近似结果,是否符合发送任务时的要求.这样可以对任务过程进行全程监督.

起始监督是接受者能否在要求的时间内接受感知任务.设任务开始执行时间为Ts,任务接受提前或推迟时间为Tad.如果参与者在任务有效时间内接受任务,即Ts-TadTsTs+Tad,那么起始监督就认为可以提高感知任务质量.如果不能在有效时间内执行任务,即Ts-Tad>TsTs>Ts+Tad,就会造成接受者对完成任务的不利影响.参与者接受任务的时间与发送者要求的时间差就形成不同程度的任务起始监督影响.

执行过程监督是在任务执行过程中,参与者与发布者进行相互监督,沟通任务完成情况以及任务的完成是否符合发送者的要求.根据任务的难易程度和计划时间长短,设定执行过程监督评价,如表1所示:

Table 1 Effect of Difficulty and Length of Execution on Sensing Tasks

表1 执行的难易和时间长度对感知任务的影响

执行时间任务难易困难容易Te>Te+TadQQTe

注:Q表示“合格”;E表示“优”.

Te为任务的实际执行时间,Tad为完成任务推迟或提前时间.

任务完成监督是对任务完成时间的约束,可以提前或推迟时间为Tad,但有限制范围.任务完成时间为Tf,如果参与者在任务有效时间内完成任务,即Tf-TadTfTf+Tad,那么任务完成监督认为接受者提供高质量感知任务,与起始监督相似.

知识库是模糊集合和模糊规则构成推理的一系列过程.任务的起始监督、执行过程监督和任务完成监督设置为参与者完成任务的模糊集合,由“优”“良”“合格”构成,分别用字母E,G,Q表示,发送者提供的数据质量模糊集合为“非常优”“优”“良”“合格”“不够好”构成,分别用字母VE,E,G,Q,NQ表示.因此,发送者与接受者的模糊集合分别表示为:

Z1表示起始监督;Z2表示执行过程监督;Z3表示完成监督;Z4表示任务提交数据质量.

Z1={E,G,Q},
Z2={E,G,Q},
Z3={E,G,Q},
Z4={VE,E,G,Q,NQ}.

根据模糊规则和模糊集描述任务完成情况,模糊规则基于专家知识系统或经验.模糊规则我们采用IF-AND-THEN形式,模糊规则的定义如表2所示:

Table 2 Fuzzy Rule Set for Sensing Task Quality Determination

表2 感知任务质量判定模糊规则集

编号IF起始监督AND执行过程监督AND完成监督THEN提交结果1EEEVE2EEGVE

续表2

编号IF起始监督AND执行过程监督AND完成监督THEN提交结果3EEQG4EGEVE5EGGG6EGQG7EQEVE8EQGG9EQQQ10GEEVE11GEGG12GEQG13GGEE14GGGE15GGQG16GQEG17GQGG18GQQQ19QEEE20QEGQ21QEQE22QGEQ23QGGG24QGQQ25QQEG26QQGQ27QQQNQ

注:VE,E,G,Q,NQ分别表示“非常优”“优”“良”“合格”“不够好”.

时间监督通过起始监督、执行过程监督、任务完成监督3方面判断接受者提交的任务完成情况,再由知识库判断接受者提交的完成任务情况.

3 感知任务模型

相关研究表明,影响感知任务分发原因很多,诸如感知任务平台利润、用户之间位置关系、参与感知任务用户数目等因素,但研究用户之间关系和时间监督对任务分发的影响不多.本文提出用户间互关注度和任务时间监督对感知任务进行分发研究.首先对感知任务与用户之间的关系建立模型;接着挖掘出用户之间相关性进行建模,用户之间相关性弱,则在感知过程中一般表现为完成感知任务不能令发布者满意或不愿意接受任务.由于感知任务时间是影响任务完成的主要因素之一,对任务完成过程怎样进行监督,提出时间监督衡量感知任务执行过程.感知任务是通过用户之间互关注度,再结合时间监督参与感知任务执行过程,让发布者选择适合自己要求的接受者.

3.1 感知任务分发

从图7中可以看出,在感知器网络中,感知用户利用携带的智能感知设备,既可以发布任务,也可以接受任务.感知中心分发感知任务,用户也可以积极参与感知任务.如果感知任务非常复杂,感知中心和发布任务者共同把任务分解,小任务分发给感知用户合作解决复杂任务.感知任务分发先比较关注度大小,选择关注度差值最小,因此感知任务分发总关注度之和最小.时间监督是先判断接受者是否能在允许的时间范围内完成感知任务,再考虑起始、执行过程和完成监督的模糊规则集,尽量选择是良好及以上的用户接受感知任务.从这个角度看,用户之间在感知任务过程中存在竞争.如果选中的感知用户的模糊集都是优等级,则说明时间监督非常切合发布用户的要求,感知任务时间也是最短的,但我们不是求具体时间之和最短.

Fig. 7 Task distribution process
图7 任务分发过程

3.2 TDUATS算法

在移动感知器网络中,任务的分发或参与者接受任务是随机的,从历史轨迹中发现参与者之间的某种关联关系,有助于感知任务的完成.在互联网中,彼此之间不信任是正常且合情合理.发布者和接受者之间如果存在联系或者彼此之间有过合作,那么再一次合作的意向就会增强.在合作过程中有互动,能够及时交流任务的执行情况,是否满足发布者的要求,有利于提升双方的合作,也能够提升任务分发的合理性以及准确性.

在感知任务分发过程中,提出的TDUATS算法挖掘用户之间的关注度,为感知任务找到适合自己需求的接受者,提升了感知用户接受感知任务的可能性,确保感知任务完成质量;引入时间监督,监督任务执行过程,用户之间可以及时沟通任务执行情况,及时调整策略达到分发任务用户的要求.具体算法描述见算法1.

算法1. 基于用户关注度和时间监督的感知任务分发算法.

输入:初始化用户与任务之间的互关注、时间监督;

输出:URS[n],TS[n],表示经过循环处理后,每个用户之间的互关注度和选中的感知任务时间监督.

① procedure TDUATS(URS,TS)

② 初始化URS,TS←0;

③ for (i=1;i<n;i++)

④ for (j=1;j<m;j++)

⑤ 计算用户之间关注度强度URS[i];

⑥ 比较接受者和发送者的关注度最小;

⑦ end for

⑧ end for

⑨ for (i=1;i<n;i++)

⑩ if (根据模糊规则判断用户时间监督)

TS[i]=模糊集合;

end if

end for

return URS[i],TS[i].

3.3 算法性能分析

TDUATS算法的时间复杂度为O(n2),空间复杂度为O(n),其中n,m分别代表发布任务的数目n和接受感知任务的用户数目m.

算法1中行③~⑧为循环的时间复杂度,由发送感知任务的数目和接受任务的参与者数目共同决定.行⑨~循环判断任务时间监督的时间复杂度为O(n).TDUATS算法中当发送者和接受者的数目都趋向n时,算法循环的次数为n2,TDUATS算法的时间复杂度为O(n2).

当发送任务数目和参与感知任务的用户数目都为n时,算法1中需要辅助存储的变量为用户的关注度,需要存储的辅助空间是URS[n]和TS[n].故算法的空间复杂度为O(n+n+O(URS[m])+O(TS[n])),所以总的空间复杂度为O(n).

4 实验分析

本实验主要是验证在移动感知器网络中,具有互关注的用户之间和任务时间监督对感知任务的分发影响.为了充分体现所提算法的优越性,在真实数据集中进行了实验仿真.

4.1 实验设计

首先采用麻省理工学院Reality Mining[29]提供的真实数据集对算法关注度进行验证.该数据集记录麻省理工学院教职工和学生携带的97个智能设备,包含约9个月的移动时间、接触联系、通话时长和移动地点等信息,约有100万条记录,实验选取了约50万条轨迹数据,因其部分设备有很多智能设备与其相连,而有的设备相连智能设备数量较少,两者数目差距较大,因此删减了部分数据.为了收集相同任务的数据,最终选取50个智能设备,验证实验结果.

实验采用Eclipse平台,开发语言为Java语言,在戴尔(DELL)台式机(i5-7400 8 GB 128GSSD+1T)上进行实验.实验结果集中删除了非常小或非常大的数据,如用户之间的关注度小于0.005或大于10的数据,将感知用户和任务编号,便于数据整理.

4.2 对比方法

在验证对比方法中,首先我们选取文献[19]的WF(water filing)算法,WF算法是移动感知网络中的典型任务分配算法,该算法思想是根据最早空闲用户优先的原则,也就是说感知任务是最先分配给已经完成任务空闲下来的用户.同时该算法是按照任务到达的顺序进行分配,不管任务的紧急程度及对任务完成时间的要求.另一个对比算法是文献[15]中的RU-AG算法,该算法是首先选择最大效用值的任务工人,然后为了任务工人都能够被选中,不以最小覆盖为条件选择最大效用值增加的任务工人,即被选择的最大效用值增大的任务工人的覆盖可能是最小也有可能不是最小.TDUATS算法是选择感知任务的互关注度和时间监督最相似的参与用户作为任务分发对象.

4.3 感知用户之间互关注影响比较

图8~10中的纵轴表示接受者与发送者关注度差值,横轴表示感知任务编号.

Fig. 8 OMT attention comparison
图8 OMT关注度比较

Fig. 9 MUST attention comparison
图9 MUST关注度比较

Fig.10 USTF attention comparison
图10 USTF关注度比较

图8可以观察出,TDUATS算法获得的接受者与发送者之间相似性很强,因为TDUATS算法的感知任务发布者和接受者之间的OMT差值最小.而WF,RU-AG算法的OMT值较大,WF选择最早空闲的参与者,不管其OMT值的大小,RU-AG选择最大OMT值的参与者.

图9显示,TDUATS算法的MUST关注度好于WF和RU-AG算法.说明感知任务发布者和接受者之间MUST相似度高于WF和RU-AG算法的MUST关注度.

图10可以看出算法的USTF关注度值都较小,WF和RU-AG算法的USTF值出现了较多负数,说明任务接受者和发送者之间关注度较弱,所以值较小.根据式(8),USTF值出现负数,是由于MUST和OMT值较大,因此发送者与接受者之间的关联关系较弱.

4.4 任务时间监督对执行任务的影响

为了验证感知任务数目对关注度和时间监督的影响,我们使用了ParticipAct数据集[30],该数据集是剑桥大学老师和学生携带移动设备在办公、会议和城市环境中的移动轨迹数据.我们使用了数据集中用户之间接触次数、接触时间、开始结束时间等相关信息.

图11~13显示的是感知任务数目增加对关注度影响,纵轴表示各个算法的关注度的和,横轴表示感知任务数目.时间监督中的推迟或提前时间Tad=120 s.

1) 关注度随感知任务数目变化的影响

图11中,每个感知任务的OMT关注度值是接受者与发送者的差.TDUATS算法是选择接受者和发送者之间关注度差值最小,因此得到的总和最小.RU-AG选择OMT值最大的参与者,因此总和最大.图11也显示随感知任务数目的递增,发送者和接受者之间的OMT差之和仍然最小.

Fig. 11 Influence of OMT attention on sensing task
图11 OMT关注度对感知任务影响

图12中,每个感知任务的MUST关注度值是接受者与发送者的差.WF算法是选择最早空闲的接受者接受感知任务,接受者和发送者之间的差值没办法保证总是最小,虽表现不错,但比TDUATS还要大一些.

Fig. 12 Influence of MUST attention on sensing task
图12 MUST关注度对感知任务影响

图13中,每个感知任务的USTF关注度值是接受者与发送者的差值.RU-AG算法的每个感知任务的USTF关注度值多数都是负值,一方面说明接受者和发布者直接关系不强,另一方面从式(8)可以看出发布者和接受者之间的OMT和MUST值较大.从实验获的数据也显示OMT值比MUST和USTF大,也就是说OMT关注度较强,说明了发送者和接受者之间关联性强.

Fig. 13 Influence of USTF attention on sensing task
图13 USTF关注度对感知任务影响

2) 起始监督随感知任务数目变化的影响

从图14可以看出,TDUATS算法在每个组中获得的起始监督的数据质量非常优和优的数目比WF,RU-AG算法要多.WF算法显示也不错,是因为WF算法是利用最早空闲工人来感知任务;RU-AG算法是选择最大的关注度,影响了感知任务的起始监督.TDUATS算法的良好和合格数目较少,是因为选取每组感知任务数目都是50,如果优及以上的数目多,良好和合格数目就可能不会比其他数目多,因为总数目是固定的.这也反过来说明TDUATS算法获得的优及以上等级数目较多.

Fig. 14 Influence of initial supervision on the number of sensing tasks
图14起始监督随感知任务数目变化影响

3) 执行过程监督随感知任务数目变化的影响

图15是感知任务的执行过程监督,剑桥大学[30]数据集中是没有感知任务过程时间,我们采用接触时间的比值来衡量.参与者的接触时间是参与者完成某个感知任务的时间与该参与者完成所有任务的比值.这个比值如果大于0.67,就认为该参与者的执行过程监督为优或非常优.从图15可以看出随感知任务数目增加,TDUATS算法根据关注度的相似程度,再选择时间监督相似,故表现得较好.WF算法根据其算法思想,在刚开始接受任务时,可以根据任务要求从空闲的参与者中快速选中接受者,所以在开始时表现得也还不错.良好和合格数目的变化情况同图14中的原因分析.

Fig. 15 Influence of execution process supervision on the number of sensing tasks
图15 执行过程监督随感知任务数目变化影响

4) 任务完成监督随感知任务数目变化的影响

图16是感知任务的完成监督,TDUATS算法是先通过选择关注度差最小的参与者,关注度越相似,越能说明它们可以很好地完成同一任务,完成任务的结束时间能够达到发送者的要求.在感知任务数目不多的情况下,TDUATS算法优势不明显,但随着感知任务数目的增加,表现为优和非常优的数目增加较明显.RU-AG算法选择的感知任务时间变化较大,所以在发布的感知任务数目较多时,能够选择适合的接受者会不够好.随着感知任务数目的增加,TDUATS算法完成监督的优及以上数目还是有优势的.WF算法变化不大,RU-AG算法变化较大,都是由算法思想决定的.对于良好和合格数目的变化趋势同图14中的分析.

Fig. 16 Influence of task completion supervision on the number of sensing tasks
图16 任务完成监督随感知任务数目变化影响

5 总结及未来研究

本文首先分析了感知器网络中的用户和任务之间的关联关系,构建任务和用户之间的模型,形成用户和感知任务之间的3种关注度:同一用户胜任多种任务、多个用户完成同一任务和用户间互关注.其次,讨论感知任务时间对感知任务的影响,对任务执行过程分为起始监督、执行过程监督和完成监督,实现感知任务时间对任务执行过程进行监督.最后利用所提用户关注度与时间监督算法对感知任务进行分发.

实验表明:对于感知用户动态分发感知任务,本文所提的TDUATS算法对比感知任务中典型的WF算法和RU-AG算法,虽出现部分感知任务不能被分发出去,但分发效率和精准度都有所提高.在OMT,MUST,USTF方面,TDUATS算法比WF算法分别提升约2.4%,4%,19%,比RU-AG算法分别提升约14.5%,9.3%,28.5%.从起始监督、执行过程监督以及任务完成监督方面分析,TDUATS算法在优和非常优方面比WF算法分别提升约6.5%,8.1%,7%,比RU-AG算法分别提升约21.9%,20.9%,10.3%.在将来的工作中,我们将对感知用户协作关系、感知用户和任务的关系、感知任务时间建模及更深入对任务执行过程的影响进行研究,以形式化的方法刻画它们之间的关系,以获得更好的性能.

如何提升感知任务完成情况、防止感知用户提交虚假数据、提高感知用户的积极性等情况在感知任务分发中受很多因素影响.参与感知任务的用户为了获得高的报酬,用户之间就会互相竞争获取更多感知任务的机会;另一方面,感知任务在更复杂的分布式环境中如何进行任务管理和分发,参与用户如何调度都将是我们继续研究的方向.

作者贡献声明:张力负责本论文思路的提出、算法实验和论文的撰写等事宜;张书奎负责论文算法讨论和整体质量把控;刘海、张洋在算法实验中提出优化;陶冶讨论算法思路,使算法不断完善;龙浩针对论文撰写提出一些建议,使论文不断完善;于淳清和祝启鼎在论文字句修改中提出建议.以上各位都积极参与论文构想、撰写、投稿、修改以及不断完善.

参考文献

[1]Howe J. The rise of crowdsourcing[J]. Wired Magazine, 2006, 14(6): 1-4

[2]Wang Jiangtao, Wang Leye, Wang Yasha, et al. Task allocation in mobile crowd sensing: State of the art and future opportunities[J]. IEEE Internet of Things Journal, 2018, 5(5): 3747-3757

[3]Antoni A, Marjanovi M, Pripuži K, et al. A mobile crowd sensing ecosystem enabled by CUPUS: Cloud-based publish/subscribe middleware for the Internet of things[J]. Future Generation Computer Systems, 2016, 56: 607-622

[4]Villanueva F J, Villa D, Santofimia M J, et al. Crowdsensing smart city parking monitoring[C] //Proc of the 2nd Word Forum on Internet of Things. Piscataway, NJ: IEEE, 2015: 751-756

[5]Kim K, Zabihi H, Kim H Y, et al. TrailSense: A crowdsensing system for detecting risky mountain trail segments with walking pattern analysis[J]. The ACM Interactive, Mobile, Wearable and Ubiquitous Technologies, 2017, 1(3): 31-65

[6]Boubrima A, Bechkit W, Rivano H. Optimal WSN deployment models for air pollution monitoring[J]. IEEE Transactions on Wireless Communications, 2017, 16(5): 2723-2735

[7]Yi Fei, Yu Zhiwen, Chen Huihui, et al. Cyberphysical-social collaborative sensing: From single space to crossspace[J]. Frontiers of Computer Science, 2018, 12(4): 609-622

[8]Feng Zhenni, Zhu Yanmin, Zhang Qian, et al. TRAC: Truthful auction for locationaware collaborative sensing in mobile crowdsourcing[C] //Proc of the Conf on Computer Communications. Piscataway, NJ: IEEE, 2014: 1231-1239

[9]Wang Leye, Wang Tianben, Yang Dingqi, et al. Location privacy-preserving task allocation for mobile crowdsensing with differential geo-obfuscation[C] //Proc of the 26th Int Conf on World Wide Web. New York: ACM, 2017: 627-636

[10]Cheung M H, Southwell R, Hou Fen, et al. Distributed time-sensitive task selection in mobile crowdsensing[C] //Proc of the 16th ACM Int Symp on Mobile Ad Hoc Networking Computing. New York: ACM, 2015: 157-166

[11]Wang Jiangtao, Wang Yasha, Zang Daqing, et al. Realtime and generic queue time estimation based on mobile crowdsensing[J]. Frontiers of Computer Science, 2017, 11(1): 49-60

[12]Pournajaf L, Garcia-Ulloa D A, Xiong Li, et al. Participant privacy in mobile crowd sensing task management: A survey of methods and challenges[J]. ACM SIGMOD Record, 2016, 44(4): 23-34

[13]Sherchan W, Jayaraman P P, Krishnaswamy S, et al.Using on-the-move mining for mobile crowdsensing[C] //Proc of the 13th IEEE Int Conf on Mobile Data Manage(MDM). Piscataway, NJ: IEEE, 2012: 115-124

[14]Ma Huifang, Jia Meihuizi, Lin Xianghong, et al. Tag correlation and user social relation based microblog recommendation[C] //Proc of the 2016 Int Joint Conf on Neural Networks. Piscataway, NJ: IEEE, 2016: 2424-2430

[15]Wang Jiangtao, Wang Yasha, Zhang Daqing, et al. Multi-task allocation in mobile crowd sensing with individual task quality assurance[J]. IEEE Transactions on Mobile Computing, 2018, 17(9): 2101-2113

[16]Yu Ruiyun, Xia Xingyou, Li Jie. Social-aware mobile user location prediction algorithm in participatory sensing systems[J].Chinese Journal of Computers, 2015, 38(2): 374-385 (in Chinese)(于瑞云, 夏兴有, 李婕. 参与式感知系统中基于社会关系的移动用户位置预测算法[J]. 计算机学报, 2015, 38(2): 374-385)

[17]Yang Jinlao, Liu Hongming. Group recommendation method based on improved matrix decomposition[J]. Machinery Design & Manufacture, 2020(4): 286-290 (in Chinese)(杨金劳, 刘虹明. 群组信息优化矩阵分解的群组推荐方法[J]. 机械设计与制造, 2020(4): 286-290)

[18]Al-Dayil R A, Dahshan M H. Detecting social media mobile botnets using user activity correlation and artificial immune system[C] //Proc of the 7th Int Conf on Information and Communication Systems. Piscataway, NJ: IEEE, 2016: 104-114

[19]Xiao Mingjun, Wu Jie, Huang Liusheng, et al. Online task assignment for crowdsensing in predictable mobile social networks[J]. IEEE Transactons on Mobile Computing, 2017, 16(8): 2306-2320

[20]Lu Zaixin, Li Weiwayne, Pan Miao. Maximum lifetime scheduling for target coverage and data collection in wireless sensor networks[J].IEEE Transactions on Vehicular Technology, 2015, 64(2): 714-727

[21]Chen Chao, Jiao Shuhai, Liu Weichen, et al. TripImputor: Realtime imputing taxi trip purpose leveraging multisourced urban data[J]. IEEE Transactions Intelligent Transportation Systems, 2018, 19(10): 3292-3304

[22]Ma Shuo, Zheng Yu, Wolfson O. Real-time city-scale taxi ridesharing[J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(7): 1782-1795

[23]He S, Shin D H, Zhang Junshan, et al. Toward optimal allocation of location dependent tasks in crowdsensing[C] //Proc of the 2014 IEEE Conf on Computer Communication. Piscataway, NJ: IEEE, 2014: 745-753

[24]To H, Fan L Y, Tran L, et al. Real-time task assignment in hyperlocal spatial crowdsourcing under budget constraints[C/OL] //Proc of the 2016 IEEE Int Conf on Pervasive Computing and Communications Workshops. Piscataway, NJ: IEEE, 2016[2021-03-07]. https://ieeexplore.ieee.org/document/7456507

[25]Li Baoxiang, Krushinsky D, Woensel T V, et al. The share-a-ride problem with stochastic travel times and stochastic delivery locations[J].Transportion Research Part C: Emerging Technologies, 2016, 67: 95-108

[26]Xiao Mingjun, Wu Jie, Huang He, et al. Deadline-sensitive user recruitment for mobile crowdsensing with probabilistic collaboration[C] //Proc of the 24th Int Conf Network Protocols. Los Alamitos, CA: IEEE Computer Society, 2016: 721-722

[27]Gschwind T, Drexl M. Adaptive large neighborhood search with a constant-time feasibility test for the diala-ride problem[J]. Transportation Science, 2019, 53(2): 480-491

[28]Long Hao, Zhang Shukui, Zhang Yang. Task distribution algorithm based on community in mobile crowd sensing[J]. Journal on Communications, 2019, 40(10): 42-53 (in Chinese)(龙浩, 张书奎, 张洋. 移动群智感知中基于社区的任务分发算法[J].通信学报, 2019, 40(10): 42-53)

[29]Eagle N S. Pentland A. Reality mining: Sensing complex social systems[J]. Personal and Ubiquitous Computing, 2006, 10(4): 255-268

[30]James S, Richard G, Jon C, et al. CRAWDAD Dataset Cambridge/Haggle(2009-05-29)[DB/OL]. (2009-05-29) [2021-03-07]. https://crawdad.org/cambridge/haggle/20090529

Task Distribution Based on User Attention and Time Supervision

Zhang Li1, Zhang Shukui1, Liu Hai2, Zhang Yang1, Tao Ye1, Long Hao1, Yu Chunqing1, and Zhu Qiding1

1(College of Computer Science and Technology, Soochow University, Suzhou, Jiangsu 215006)

2(School of Computer Science and Technology, Huaibei Normal University, Huaibei, Anhui 235099)

Abstract In the mobile crowd sensing network, how to complete the sensing task assigned by the publisher within a limited time is an important problem faced by the mobile crowd sensing task distribution. To solve this problem, we propose a task distribution algorithm TDUATS based on user attention and time supervision in order to make the sensing users cooperate closely and feed back the sensing tasks to the sender in time. In the algorithm, the concepts of user attention, initial supervision, process supervision and completion supervision are proposed at first, and then the relationship between users who perform sensing tasks is analyzed. In order to monitor the process of task execution, the attention model among users is established, and the sensing tasks are distributed on this basis.Two real-world mobility datasets experiments demonstrate that the our proposed algorithm can not only complete the sensing task within a limited time, but also supervise the process of task execution, which is conductive to the publisher to timely understand the execution of the task, and plays a good role in improving the satisfaction of task execution. At the same time, compared with the comparison algorithms, sender and publisher can understand the task execution process in time, effectively improving the satisfaction of both parties.

Key words mobile sensor network; sensing task; user attention; time supervision; task distribution

中图法分类号 TP391

收稿日期2020-07-20;

修回日期:2021-03-29

基金项目国家自然科学基金项目(62072321,61672370);预研基金项目(61403120402);江苏省六大人才高峰项目(2104-WLW-010);苏州市科技规划项目(SNG2020073, SS202023);江苏省高等学校自然科学项目(19KJB520061);江苏高校优势学科建设工程资助项目

This work was supported by the National Natural Science Foundation of China (62072321,61672370), the Advance Research Fund (61403120402), the Six Talent Peak Projects in Jiangsu Province ((2104-WLW-010), the Science and Technology Project of Suzhou of China (SNG2020073, SS202023), the Natural Science Research Project of Jiangsu Higher Education Institution (19KJB520061), and the Project of the Priority Academic Program Development of Jiangsu Higher Education Institutions.

通信作者张书奎(zhangsk@suda.edu.cn)

Zhang Li, born in 1980. PhD. His main research interests include mobile crowd sensing, mobile computing and distributing computing.

张 力,1980年生.博士.主要研究方向为移动群智感知、移动计算和分布式计算.

Zhang Shukui, born in 1966. PhD. Professor and PhD supervisor. His main research interests include ad hoc and wireless sensor networks, mobile computing, distributing computing, intelligent information processing, parallel and distributed systems.

张书奎,1966年生.博士,教授,博士生导师.主要研究方向为ad hoc和无线传感网络、移动计算、分布式计算、智能信息处理和并行分布式系统.

Liu Hai, born in 1985. Master. His main research interests include mobile computing, distributing computing, parallel and distributed systems.

刘 海,1985年生.硕士.主要研究方向为移动计算、分布式计算和并行分布式系统.

Zhang Yang, born in 1989. PhD candidate. His main research interests include IoT, information security, crowd sensing computing, intelligent information processing.

张 洋,1989年生.博士研究生.主要研究方向为物联网、信息安全、人群感知计算和智能信息处理.

Tao Ye, born in 1992. Master. His main research interests include mobile crowd sensing, distributing computing and wireless sensor networks.

陶 冶,1992年生.硕士.主要研究方向为移动群智感知、分布式计算和无线传感器网络.

Long Hao, born in 1985. PhD. His main research interests include mobile crowd sensing, privacy protection, distributing computing.

龙 浩,1985年生.博士.主要研究方向为移动群智感知、隐私保护和分布式计算.

Yu Chunqing, born in 1996. Master. His main research interests include mobile ad hoc network and game theory.

于纯清,1996年生.硕士.主要研究方向为移动自组织网络和博弈理论.

Zhu Qiding, born in 1996. Master. His main research interests include wireless sensor network and data fusion.

祝启鼎,1996年生.硕士.主要研究方向为无线传感器网络和数据融合.