考虑信誉更新的移动群智感知在线激励机制

杨 堤 李卓青 杨绿溪 徐琴珍

（东南大学信息科学与工程学院，南京，210096）

引 言

随着移动互联网技术和应用的迅速发展，移动智能终端得到广泛普及，移动智能终端设备的应用也更为广泛[1-3]。对于移动群智感知系统而言，用户参与感知任务伴随着隐私泄露的风险[4]，同时也会付出消耗资源的代价。因此，为补偿用户的付出，设计合理的激励机制是当前研究的一个热点[5]。早期的研究主要集中在对用户离线到达的场景建模研究[6]，Lee等对于离线场景的用户提出了基于反向拍卖的动态定价机制RADP[7]，之后又在RADP机制的基础上考虑了用户的虚拟信誉积分，设计了加入虚拟信誉分的RADP-VPC[8]的机制。在离线的场景下，有意愿参与感知任务的用户，统一将包含其报价等资料的信息提交给平台处理，平台在接受完所有用户信息之后，离线计算选择部分用户完成任务，并统一反馈选择结果[9]。离线场景下的移动群智感知应用也受到广泛关注。TruCentive[9]利用移动群智感知，激励用户参与获取城市停车位信息，Noisemap[10]是一款利用移动群智感知设计的测量城市噪声污染的软件，Livecompare[11]为商品比价设计了一个离线的激励机制系统。以上的理论和应用的成果都基于离线的场景，同时针对离线问题下的用户提交数据质量以及用户信誉的的研究，也有一定的研究。Albers等[12]提出了一种计算用户的信誉分值去衡量数据质量的方法；Huang等[13]针对移动群智感知问题提出了一种信誉系统；Wen等[14]提出了一种研究室内定位的质量驱动的激励机制QDA。然而对于实际情况来说，用户并不是集中到达统一提交资料，并且给予系统足够多的时间做出选择决策，而是随机在线到达的[15-17]。因此将用户到达建模成在线的场景更加符合现实情况。Zhao等[18,19]提出了一种用户随机到达的在线激励模型。该模型在任务预算有限的前提下，最大化平台端价值收益，并首次提出了多阶段采样竞拍算法(OMZ/OMG)，该算法下，平台需要及时给出是否选择用户的决断。但是现有的很多在线激励机制的设计[18,19]，忽略了对用户提交数据的质量的筛选考虑，导致任务发布方的价值收益不能达到实际预期。为此，本文考虑任务发布方对用户的信誉评分反馈以及用户提交数据的质量评判，并综合用户的历史和现实信誉情况，建立考虑信誉更新的移动群智感知在线激励机制，从系统建模、信誉评价机制以及考虑信誉更新的在线激励机制(Reputation-updated online mechanism,ROM)算法和仿真等方面进行阐述。

1 系统建模

移动群智感知系统，主要有3种角色：任务发布方，平台方和用户。任务发布方首先向平台方提交需要发布的一系列公开的异构感知任务Q={q1,q2,…,qm}，以及完成任务的总预算B和雇佣用户的截止时间T以及一些有关质量评分的要求。平台方接受到需要的采集任务信息之后，向广大用户发布感知任务以及用户需要提交的信息内容说明。对此次感知任务感兴趣的用户U={1,2,…,n}在线随机到达，并向平台方提交他们参与完成任务的资料信息[19]。用户通过无线网络或蜂窝网络与平台进行通信。

用户i若初次到达系统，则会赋予一个初始的信誉值ηi，平台唯一化记录用户i∈U的ID，如果用户宣称完成了任务，并通过算法筛选，被平台选择，平台方会接受任务发布方对用户提供数据质量的反馈，并以此为依据，在用户下一次登录系统竞标时更新其信誉值，作为参与完成任务的资料信息之一。若用户非首次参与，系统读取用户上一次参与选择后的信誉值，并按照更新法则进行更新，参与此次竞标。

平台所要求的用户i提交的参与任务资料是一个五元函数θi={ai,di,ci,vi,ηi}，这里ai∈{1,2,…,T}表示到达时间，di∈{1,2,…,T}表示离开时间，ci是完成一个感知任务真实的成本，vi表示用户i可以为任务发布方带来的价值，ηi为用户i当前的信誉值。用户参与感知任务以及平台选择用户子集的过程可以建模成一个在线的拍卖过程。用户决定参与此次任务之后，会向平台端提交参与任务的资料信息。接着，平台需要做一个在线的及时判断，决定是否雇佣该用户。如果该用户被选择，平台需要支付给用户的报酬pi，同时接受任务发布方反馈的用户提供数据质量打分，并根据上传数据的一些属性计算客观评价分值，综合考虑主客观的分值，以供下次更新信誉值。注意任务发布方有一个总的预算B作为可以支付给选择用户的最大报酬。任务发布方期望在给定的预算和得到一定数据质量保证的前提下，最大化从用户方得到的总价值，整个过程的信息流如图1所示。

用户在线到达参与竞标的过程可以看成是一场博弈，用户会有策略地提交他们的竞标资料去最大化可能得到的回报。当与任务发布方互动时，用户i真实的成本和到达、离开时间是非公开的，仅被用户本身所知。用户i只能有策略地操作自己的竞标价格以获得更高的效用，平台端基于用户的竞标资料通过激励算法选择获胜用户，并通过计算，给予获胜用户报酬pi。

图1 信息流示意图Fig.1 Schematic of information flow

2 信誉评价机制

对于平台方而言，存在选择用户的信誉值的阈值标准，对于初次参与感知任务的用户来说，将初始化的信誉值设定系统在当前时刻的信誉值的阈值η˜。设用户的信誉值η的取值是有上下界的，即η∈[0,ξ]，ξ为用户信誉值的上界，用户如果更新完信誉值之后信誉值为负数，认为该用户的信誉值为最小值0。φ(ηi,Rm)表示更新后用户的信誉值η*i，其中ηi为用户i当前的信誉值,Rm为用户上一次参与竞标后得到的基于数据质量的信誉综合评分。用户参与此次竞标的信誉值η*i=φ(ηi,Rm)的评定需要综合任务发布方对用户的打分反馈ζi和客观影响因素等（质量评分的要求）。假定质量评分要求由完成时间可靠性ωi和图片收集任务要求的图片大小可靠性ϑi共同决定，考虑主客观因素综合，采用分类分级赋值，建立信誉评价规则。表1中对有关信誉评价机制的符号进行说明。

表1 信誉评价机制符号说明Tab.1 Description of credit evaluation mechanism symbol

2.1 任务发布方打分ζi

ζi为任务发布方对用户完成质量的考量，其中ζi∈[0,1]，ζi越大表示任务发布方对用户的满意度越高。由任务发布方反馈的打分，作为综合评定的主观因素之一，考虑了任务发布方的主观反馈，对数据质量的把控上起到了主观选择的作用。在[0,1]中定义3个集合，其中打分分值落在[0,0.3)表示“低”用L代替；分值落在[0.3,0.7)表示“中”用M代替；分值落在[0.7,1]表示“高”用H代替。

2.2 完成任务时间的可靠性ωi

用户在参与任务之前会提交自己相关参与资料，由于考虑的是在线场景，所以资料中需包含用户的到达时间ai∈{1,2,…,T}和离开时间di∈{1,2,…,T}。时间的可靠性ωi定义为用户完成时间与任务发布方要求的总的完成时长的重叠时间的比值。该值越大，表明用户花费了相对更多的时间完成任务，因此可靠性相应的也应越大。定义客观的完成任务时间可靠性为

式中T表示整个过程的截止时间。显然ωi的取值范围在[0,1]。同样，将ωi的取值范围定义成3个集合建模，其中ωi∈ [0,0.3)表示“低”，用L代替；ωi∈[0.3,0.7)表示“中”，用 M 代替；ωi∈ [0.7,1]表示“高”，用H代替。

2.3 图像大小可靠性ϑi

针对一些具体的情况，例如收集图片的感知任务，了解收集图片的质量一个很重要的方面就是图像的大小以及像素等指标。假设任务要求上传的图片的大小为φi，将实际用户的上传图片的大小χi与要求的大小的距离占要求大小的比例表示为图片大小的可靠性

显然ϑi的取值范围在[0,1]。同样，将ϑi的取值范围定义成3个集合建模，其中ϑi∈[0,0.3)表示“低”，用L代替；ϑi∈ [0.3,0.7)表示“中”，用M代替；ϑi∈[0.7,1]表示“高”，用H代替。则计算更新的用户信誉分数Rm可使用式（3）所示规则，其中η˜为系统当前时间阶段的信誉阈值。

平台统计上述3方面的分数，并根据取值范围集合进行对应，统计L和H的个数，并根据规则计算信誉分数。用户带着自己的参与资料，参与平台的选择。每次用户到达平台，提交数据的时候，平台会根据上一次用户的信誉记录，更新用户的信誉值作为参与后续竞选的参数之一。其具体的更新规则如下

每当用户到达提交竞标资料，信誉值η*i作为竞标资料之一，提交给平台，若用户之前参与过竞标且被任务发布方选中，有相应信誉值更新情况，平台在竞标前根据更新法则计算用户新的信誉值η*i参与此次的竞标。若之前无参与提交资料过程，则信誉值设置为初始值η˜;若上一轮的竞标未获胜，信誉值维持不变。

3 算法描述

用户i在线的到达参与竞标，提交竞标资料θi={ai,di,ci,vi,ηi}，用户i参与竞标的竞标价格为bi，这里bi≥ci。平台需要在用户离开时间di之前，根据用户提供的竞标资料决定是否雇佣该用户。获胜者用户的集合表示为W，用V(W)表示任务发布方选择用户子集W的价值函数，则

图2 考虑信誉的在线激励机制系统流程图Fig.2 Flowchart of online incentive system considering credibility

对于任务发布方来说，希望在预算B限制的情况下，通过选取用户子集，尽可能获得最大的价值，即

为了实现在线处理用户的参与资料，参考秘书问题的多阶段选择的思想[20],设计了一种多阶段的采样-接受过程[21]。该机制动态的增加采样的容量，并且动态的为将来用户子集的选择学习效率密度阈值，效率密度阈值结合之前所述的信誉更新机制得出的信誉分，为平台选取用户提供了标准[19]。该算法需要满足：（1）计算有效性，即该算法要在多项式时间内完成；（2）个体合理性，即被选择的用户所得到的报酬大于等于其成本；（3）预算可行性，即支付给所有选择用户的总报酬要小于给定的预算B；（4）策略真实性,即保证如果用户谎报其参与资料的话他不会获得更多的报酬[22]。

3.1 效率密度阈值更新算法

为了给平台在选择用户时有提供一个统一的标准，在每一阶段开始的时候需要执行阈值更新算法。

算法的核心在于从采样集合中分析计算，在每个时间阶段开始的时候，根据算法1计算该阶段的密度阈值。平台将每个用户的效率值与计算得到的该阶段的密度阈值进行比较，作为选择用户子集的标准。对于平台方来说，目标是最大化能获得的价值，因此在选择用户时，倾向于选择有着更高效率值的用户。具体的效率阈值更新算法如下：

算法1效率阈值更新

输入：阶段-预算B'，采样集合S'，当前时间阶段Tk

输出：密度阈值ρ

在密度阈值算法中，输入的参数是任务发布方提交的预算B'，采样的集合S'，还有当前阶段的开始时间Tk定义用户的效率为效率越大越有可能被平台选中。本文假定每一个用户的效率均有上下边界，现实情况中也更加符合，同时也为了后续的属性证明。假设阈值更新算法依次选择效用值高的用户将用户集合放入ETK，在选择效用值高的用户需要满足预算受限的条件，即

本算法的根本目的是计算每一阶段的阈值，这里定义阈值为和每一阶段的平均效用值。

定义1如果按照效率进行排列的用户满足并且此场拍卖的预算为B，那么如果对于2个用户x和y，满足且那么

那么

由定义1可知，在阈值算法中，如果while循环在用户i处不再满足预算条件，则不需要再考虑其他效用值比用户i低的用户j。因为可以推断出

3.2 信誉值更新算法

信誉值的高低不仅是平台选择用户的重要标准之一，同时也应是用户获取报酬和平台获取价值的影响因素。信誉值的提高能够给用户带来更多的报酬收益的同时也为平台带来更多的价值收益。因此本模块将阐述信誉值与用户报酬以及平台收益之间的关联。

3.2.1 信誉值与用户报酬

更新用户信誉值之后，如果Rm＞0，则说明用户上一次有着优秀的信誉记录，各项指标基本完全符合系统的要求。则如果此次用户的效率值大于该阶段的阈值并且预算还没有用完，即用户符合被选中的所有条件，系统需要支付一定的报酬给用户，该用户理应得到比更加多的报酬，这里定义对于此类用户

式中g与信誉值成正比，比例系数为即义越大，下次用户参与竞拍时会获得越多的报酬。

3.2.2 信誉值与平台价值收益

与用户报酬类似，有着较高信誉的用户提供的数据，也有更大的可能为平台带来更多价值收益。即如果Rm＞0，用户个人的竞标资料中的vi根据信誉值重新衡量。定义

式中h与信誉值成正比，比例系数为即越大，下次用户参与竞拍时会给平台带来越多的价值。

3.2.3 信誉值阈值的更新

想要参与竞标的用户的信誉值更新后，将会与参与竞标选择的阈值进行比较，只有高于该阈值的用户才能继续参与竞标。由于本论文考虑的是用户可以多次参与竞标的情况，因此初次来到系统参与竞标的用户赋予的初始化信誉值为系统的信誉值阈值，当选中的集合中，重复来到的用户人数占用户总人数超过一半时，需要更新信誉值阈值，信誉值的阈值定义为选中集合中所有用户信誉值的平均值，即

3.3 ROM算法

前面介绍了计算效率阈值的方法，是为了在每个阶段开始的时候，计算密度阈值，指导平台选择用户的子集。首先，把时间T划分成l个时间段每一阶段以结尾。相应的，每一个阶段分配的预算是Bk=2-kB，其中Ti表示在该时刻之前用户到达的概率是2-k。对于每一个时间段Ti，按照上述的阈值更新算法计算效率阈值。具体的基于质量的在线激励算法如下：

算法2基于质量的在线激励算法

输入：阶段预算B，截止时间T

(1)(t,Tk,Bk,

(2)fort=1toTdo

(3)if用户i在t时刻到达 then

(4)O←O∪{i}

(5)for每一用户iinOdo

(6)if储存用户信誉值数据库存在更新记录

(7)ηi=

(8)ifRm＞0

(9)vi=max(vi+hvi,biQ)

(10)end

(11)elseηi和vi保持不变

(13)ifRm＞0

(14)pi←(1+g)

(15)else

(17)W←W∪{i}

(18)O←OW

(19)若有用户在时间t离开，从O中移除该用户，并将该用户加入采样集合S'

(20)ift=then

(21)ρ←效率阈值更新(Bk,Tk,S')

(22)Tk=2Tk,Bk=2Bk

(23)ifW集合中重复到达的用户占所有被选中用户比例≥0.5

在每一个阶段内，如果有用户到达，将其加入集合O中，这里，集合O中包含的用户是已经到达但是还没有被选择或者已经离开此次竞拍活动。并从数据库中读取是否存在此用户上次参与此次感知任务的信誉值更新数据。若有的话，将新的信誉值赋值给该用户之后再进行后续选择过程，并增加用户能够带来的价值vi为原来的(1+h)倍，该h值与用户的信誉值成正比，但由于前面有设定，用户的效率值是由上界的，所以用户能够带来的价值vi最大不能超过biQ。如果没有更新信誉值信息，则以之前不变的信誉值和价值参与选择过程。如果当前用户满足效率值高于阈值，并且目前平台总的花费没有超过预算B，同时用户的信誉值高于阈值η˜，则选择该用户，将其加入获胜者集合W,并给该用户支付报酬vi/ρ。如果上述3个条件中有一项没有满足的话，则该用户则会等待下一时刻的选择判断。如果当前时间等于则按照之前所述的阈值更新算法更新密度阈值。如果当前已经选择的用户，即集合W中的重复到达用户占所有被选中用户的比例≥0.5，则更新信誉值阈值为重复该过程，直到t=T。

4 仿真与分析

为了验证本文提出的考虑信誉更新的在线激励机制算法的性能，运用Eclipse的Java代码对提出的基于信誉更新的在线激励机ROM进行了仿真实验，并分别与离线情况下知晓所有用户信息的最优算法、在线情境下随机阈值选择用户的算法以及不考虑用户信誉的一般在线激励机制算法进行比较。

实验1验证算法的计算有效性

对计算有效性的测试实验是在Windows10系统上进行，处理器为Intel®Core™i7-6650U CPU@2.20 GHz 2.21 GHz，RAM为16.0 GB。为验证ROM算法的计算有效性，按表2所示的人数设定，每一组都随机生成了50个实例，并对这50个实例的运算时间取平均数来保证结果的可靠性。实验设定及结果如表2所示。运用同样的方法在预算变化的情况下，也同样对计算有效性进行了验证，实验结果记录于表3中。

综合表2、3的实验结果可见，ROM算法是符合计算有效性的。

表2 参与人数变化运行时间实验结果Tab.2 Running time with variation of the number of participants

表3 预算变化运行时间实验结果Tab.3 Running time with the change of budgets

实验2研究预算B与平台获得的总价值之间的关系。

设置截止时间T=50为,人数n=500,时间阶段l=4,用户的效率上下界分别为L=1,U=2,初始密度阈值为ε=0.9，初始信誉值阈值μ=0.5。对每一个用户i而言，设置在T内随机产生到达和离开时间。并设置用户可以在离开之后再次进入系统。ci服从均匀分布U[1,10]。平台模拟对已选择数据进行[0,1]的随机打分，用户的完成任务时间可靠性和图像大小可靠性也由收集数据的平台算出，综合考虑后计算出新的信誉值。此次模拟的预算取值范围是B∈[0,20000]。将本文提出的基于质量的在线激励机制与离线算法，随机选择算法以及不考虑质量的在线激励算法进行了仿真比较，结果如图3所示。

仿真结果说明，考虑了用户提交数据质量的ROM算法虽然较之于离线情况下最优的算法来说，在同样预算的情况下，获得的价值没有最大，但是较之于一般的在线激励机制来说，能获得更大的价值增益，而且随着预算的增加，价值的增益差距也越来越大，这是由于预算越大，能够选择的高质量用户响应比例也会提高。因此能够为平台带来更大的价值。

图3 预算与价值之间关系仿真结果Fig.3 Budget versus value

实验3研究到达人数n与平台获得的总价值之间的关系。

设置截止时间T=500 s,预算B=1600,时间阶段l=4，用户的效率上下界分别为L=1,U=2,初始密度阈值为ε=0.9，初始信誉值阈值μ=0.5。其余设置与实验一相同。此次模拟的参与人数的取值范围是n∈[0,600]。将ROM与最优的离线算法、随机选择算法以及不考虑质量的一般在线激励算法进行了仿真比较，结果如图4所示。

图4 用户数量与平台获得总价值关系仿真结果Fig.4 The number of users versus value

仿真结果说明，随着参与人数的增加，平台获得的总价值也是增加的。单位人数获得最大价值的是离线算法，本文提出的ROM算法因为对参与者的筛选更加严格，所以与一般的在线激励机制相比，单位人数获得的效益略低，不过在可接受范围之内。对保证平台的数据质量上的贡献大于此单位人数的获得价值。

5 结束语

结合任务发布方对用户的信誉评分反馈以及用户客观的时间可靠性和提供数据大小可靠性等因素，提出了用户信誉评价机制，综合考虑用户历史和现实信誉记录的更新机制，建立结合信誉更新模型，设计了基于信誉更新的在线激励算法，运用JAVA开发了仿真程序。仿真结果表明，该算法通过对用户信誉进行评分，提高了平台收集数据的质量，在一定程度上减少了平台的总花费，从而提高了平台工作的效率。