移动群智感知中基于用户偏好的参与者选择

苏 华, 吴倩倩

(天津工业大学 计算机科学与技术学院，天津 300387)

随着移动设备的不断发展，移动群智感知网络也越来越受到重视.移动群智感知网络是一种新的模式，它利用无处不在的智能手机来感知、收集和分析数据，规模超出了以往[1].移动群智感知网络不同于传统的商业众包系统.任务发布者将任务提交给移动群智感知网络平台，并告知平台完成任务的报酬，用户携带智能设备执行任务.任务发布者需要确定用户提供的数据是否真实有效[2].

移动设备，例如手机、智能手环等设备，这些智能设备内置各种传感器，如温度计、麦克风和相机等，不同的传感器具有不同的功能.因此人们可以通过移动设备对数据进行收集和感知，不需要重新安装收集数据的软件或工具.移动群智感知网络已经在许多领域得到了成功的应用[3].例如，它可以记录个体的身体指标，进行医疗保健[4]，还可以检测环境，例如噪音污染[5]，道路交通状况[6]，停车系统[7]和犯罪情况[8].主要流程是个人或团体将所需的任务描述信息发送到移动群智感知网络服务器.在这里，希望获得数据的个人或团体称为任务发布者，服务器称为平台.平台从任务发布者获得一个任务，然后将任务分解成若干个子任务.同时，平台选择部分携带移动智能设备的用户进行数据采集.用户定期将收集到的数据反馈给平台，平台整理收集到的数据并将其返回给任务发布者.平台获得奖励，并向用户支付一定数额的报酬.

移动群智感知网络可以方便快捷地采集数据，节省人力、时间，给生活带来极大的方便，但也面临着一些问题.很多问题导致用户的积极性不高，没有足够的用户参与到任务中，有时用户提供的数据质量很差，导致任务无法进行.

因此，如何选择合适的用户是当前移动群智感知网络中最重要的问题.用户的参与是移动群智感知网络的基础.用户提供良好的数据是移动群智感知网络正常运行的保障.

1 相关工作

Peng[9]等人提出了一种激励机制来解决感知数据质量不均匀的问题.他们将数据质量纳入移动群智感知网络激励机制的设计中.为了激励用户有效地感知数据，提出了根据用户的表现来奖励用户.Wang等人[10]通过改进两阶段拍卖算法，考虑根据历史信誉来选择参与者，提出了TATP算法，证明其想法的可行性.L·Jaimes[11]等人提出了一种基于反向拍卖的激励机制，允许工人对任务进行投标，从而在提高质量的同时节约成本.这些机制只考虑了用户的信誉，如果用户失信，将永远被拒绝.

Wang等人[12]提出了保证覆盖的参与者选择.该方法在保证任务覆盖率的前提下，预测用户移动轨迹，通过预测结果将任务分配给用户，从而得到任务分配的最优解.然而，随着任务数量的增加，感知数据的质量无法得到保证.Yang[13]等人提出了一种新的信用价值计算方法.该方法不同于以往的信用价值计算方法.考虑了直接信誉和间接信誉.直接信誉是平台对用户历史行为的衡量，间接信誉是其他用户对用户的评价.根据计算出的信誉值，将用户分为几个等级:高度信任、值得信任和不值得信任.平台选择适当级别的参与者参与任务.Zhang[14]等人提出了一个Crowdemployer系统，该系统满足了最小覆盖条件，同时最小化支付给参与者的金额.招募参与者时，获取每个用户的历史信息，预测用户的运动轨迹和运动限制区域.Zhang[15]等人添加了一个Fog计算框架，根据参与者的位置、社交行为和设备的电池寿命来作为评估是否选择他们的因素.他们考虑了用户的参与意愿，但忽略了数据的可信度.

目前的工作是根据质量和覆盖面以及节省预算来选择参与者，其中一些是根据用户历史信息更新的，这需要长期的沟通.并且仅通过信誉值属性来选择参与者，一旦信誉值不符合条件，就会被拒绝，从而减少参与者的数量.因此，提出了一种信誉值与用户偏好相结合的方法.信誉值根据历史信息进行更新，用户偏好是用户自身的兴趣特征.

2 系统模型

任务发布者向平台发布任务，并承诺给予一定报酬.用集合R表示任务集，R={R1,R2,R3,…,Rn}.用集合U表示用户集，U={U1,U2,U3,…,UN}.对于任务Rj，平台根据历史感知任务经验确定任务预算Bj，若用户Ui想参与感知任务Rj，将对该任务投标Bi,j，将投标报价发送到平台.平台从投标用户中选择合适的用户参与任务.用户Ui完成感知任务的时间为感知时间ti,j，用户Ui对平台的贡献值为Vi,j.收集数据会消耗精力、流量等成本，即用户花费为Ci,j，用户花费与感知时间和单位时间内感知任务的花费有关.

Ci,j=τ*ti,j

(1)

其中:τ是单位时间内感知任务的花费.平台对完成任务的用户支付报酬Pi,j，用户的报酬受到总任务预算和个人感知时间的影响.

(2)

其中:Tj是被选中的用户完成感知任务的总时间.用户获得的利润为Ei,j.

(3)

完成感知任务后平台获得的报酬为Ej

(4)

其中:Wj是被选中的参与感知任务的用户集，且Wj⊆U.

感知任务的数据质量受到用户偏好与用户信誉值共同的影响，在其他文献中，没有考虑用户偏好这一因素.如果用户对将要感知的数据感兴趣，他可能更愿意参与感知任务，用户对任务的偏好程度会影响平台对用户的选择.因此，使用用户对任务的感兴趣概率衡量用户偏好.

集合X(Rj)表示任务Rj属性，假设任务Rj有K个属性，用X(Rj)={A,B,C,…,K}表示.X(Ui)表示用户偏好的属性，假设有k个，X(Ui)={a,b,c,…,k}.因此，通过计算两者之间的相似比得到用户Ui对任务Rj的感兴趣概率.见图1.

图1 参与者感兴趣的概率

感兴趣概率为：

(5)

平台为每个任务设置了感兴趣阈值Pin，即用户对任务感兴趣的概率大于兴趣阈值，用户被选中的可能性越大，反之亦然.用户兴趣得分为INCi.

INCi=

(6)

用户Ui参与任务Rj，其信誉值为TRi,j，根据历史感知信息更新当前信用值，其公式如下:

(7)

TRi,m是用户Ui参与任务Rm时的信誉值，假设用户在参与Rj任务之前参与了j个任务，每个任务都有相应的信誉值.距离当前任务感知时间不同对当前任务的信誉值有不同程度的影响，βm是时间衰减系数，表示历史信息对当前信誉值的影响是逐渐减弱的.时间衰减系数定义为：

(8)

TRj是平台为任务指定的信誉阈值，这是用户需要满足的信用要求.如果用户的信用低于阈值，则参与者之前提供的数据可能不准确，导致质量下降.用户被选中的概率低.用户的信用评分为TRCi

(9)

平台计算兴趣分数和信用分数后，计算用户的选择分数SCi.

(10)

最后，平台根据给定的分数阈值SC选择合适的用户参与任务.

3 算法设计

移动群智感知网络中，每个用户都有自己的特定的信誉值,感兴趣事件的特性.选择一组用户,让用户的投标报价小于平台给定的预算,并选择高信誉值和高兴趣值的用户.请求参与任务的每个用户,其信誉值是确定的,而相同信誉值的用户,根据感兴趣概率, 感兴趣概率越高,其信誉越高.

因此，UTSA算法如算法1所示.

算法1 update two-stage

auction of participant

selection(UTSA)

Input:

set of usersU,

set of tasksR,

budgetB,

Score thresholdSC

Output:

The winner setWj

i⟸1；Wj⟸φ；Pj⟸0；

The first stage

fori

Pin(Ui,Rj)⟸calculate the interest percentage

INCi⟸calculate the interest score

TRCi⟸calculate the trust score

SCi⟸calculate the select score

ifSCi≥SCthen

Wj⟸Wj∪{i}

Pi,j⟸calculate the reward

Pj⟸Pj+Pi,j

B⟸B-Pi,j

end if

end for

The second stage

fori

Pin(Ui,Rj)⟸calculate the interest percentage

INCi⟸calculate the interest score

TRCi⟸calculate the trust score

SCi⟸calculate the select score

Pi,j⟸calculate the reward of user i

ifSCi≥SC；Pj+Pi,j≤Bthen

Wj⟸Wj∪(i)

end if

end for

在算法1中，在第一阶段，给定一部分预算B′，部分预算的计算方法参考文献[9]

(11)

第一阶段是确定参与者的投标价格是否小于部分预算B′.若满足，则计算参与者的兴趣概率，兴趣得分.根据历史信息来更新参与者的信誉值，计算参与者的信誉得分，最终得到参与者的选择得分.当选择得分大于给定的阈值时用户被选中的.循环执行，直到部分预算耗尽.

第二阶段，首先，第一阶段支付给参与者的总金额是第二阶段的启动预算，根据选择分数选择合适的参与者.被选中的参与者将加入获胜者集合.最终被选中的用户是两个阶段被选择的并集.

在原始的TATP算法[9]中，TATP是一种改进的基于信任和隐私敏感性的两阶段拍卖算法.TATP算法考虑了用户的历史声誉，采用两阶段拍卖算法，设定用户的信用值、执行任务的时间、隐私，只有满足条件的用户才会被选中.但是，算法只考虑信用值来提高用户提供的数据的质量，一旦用户一次不可信，将永远被拒绝.UTSA算法增加了用户信誉值评分的原则.同时，通过比较参与者的兴趣特征与任务特征，形成用户的兴趣得分，作为用户偏好，并将两者结合，最终得到用户的选择得分.

4 实验设计

在提出一个有质量保证的解决方案之后，检查其在真实环境中的性能.针对任务分配问题，提出了基于两阶段拍卖算法的UTSA(Update Two-stage Auction)算法，考虑了用户的偏好、信誉值等因素.为了证明算法的有效性，比较了其与TATP算法在一系列感知任务中的性能.

4.1 参数设置

为了在实际环境中测试所提出的方法，设置了一些参数.对于每个用户，都有一些固定的参数，即用户的信用值，用户的兴趣属性.

在Python实验环境中模拟个用户.在每次实验之前，在[40，100]随机选择用户的信誉值，各用户兴趣特征与任务特征的匹配程度服从均匀分布，通过改变参数设置，得到了不同的实验结果.

为了量化提出的用户偏好，研究了几种不同类型的任务特征.如图2所示，行表示不同类型的事件，列表示不同的属性.行和列的交集指示此类型的任务是否具有此属性.事件的属性由0和1表示.0表示此类型的任务不具有此属性，1表示具有此属性的任务.例如，交通事故需要使用距离传感器，光传感器、环境温度传感器、相机、压力传感器等特征.

对于每个用户，都有感兴趣的任务类型.对用户偏好的类型进行了量化.选择了若干用户和若干类型来代表用户偏好.如图3所示，例如，用户1对具有温度传感器、光传感器、距离传感器、GPS等类型的事件感兴趣.该用户对雪灾事故任务感兴趣的概率0.375.用户5参与雪灾事故的概率为0.286.对于相同的任务，需要计算每个用户感兴趣的概率.

图3 参与者的偏好类型

4.2 实验结果

对于TATP算法和提出的UTSA算法，当平台的给定预算为50时，剩余预算随时间的变化如图4所示.

图4 预算为50时，剩余预算随时间的示意图

在其他条件相同的情况下，当总预算为100时，剩余预算随时间变化如图5所示.

图5 预算为100时，剩余预算随时间的示意图

如图4、5所示，x轴表示时间，y轴表示预算.通过对比实验可以看出，虽然UTSA算法和TATP算法在前期的预算相差不大.然而，随着时间的推移，UTSA算法选择的参与者在同一时间点上消耗的预算明显少于TATP算法.当TATP算法的预算用完后，UTSA算法仍然为后续的任务留有大量的预算.这是因为UTSA算法是基于两个因素来选择参与者，而TATP算法只考虑了信誉值，一旦参与者的信誉值不符合条件，就会被设置为不值得信任，永远被拒绝.在完成相同数量任务的情况下，UTSA算法不仅保证了质量，而且节省了预算.

进一步比较了两种算法完成的任务数，实验结果如图6所示.

图6 完成相同任务消耗预算示意图

x轴表示完成的任务数量，y轴表示预算.从实验结果可以看出，对于相同数量的任务，TATP算法比UTSA算法消耗了更大的预算.在开始阶段，两种算法消耗相同的预算来完成相同数量的任务.随着时间的推移，TATP算法需要消耗更多的预算来完成相同数量的任务.对于相同的预算，TATP算法只能完成少量的任务，即在预算耗尽之前只能完成部分任务.UTSA算法有足够的预算来执行剩余任务.因此，UTSA算法可以在保证质量的同时，选择合适的参与者以相同的预算完成更多的任务.

5 结 语

本文通过分析现有移动群智感知网络中参与者选择方法的不足，提出了一种基于用户偏好的参与者选择方法.将参与者的个人偏好与任务的特征相结合，设置用户偏好属性.同时结合可信度模型，使平台在选择参与者时综合考虑两个因素.本文目标是在选择参与者时，让尽可能多的用户参与到他们感兴趣的事件中来.在Python的实验环境中，将TATP算法与UTSA算法进行比较，通过修改参数设置，证明了算法的可行性.与现有的参与者选择机制相比，该机制确保了数据质量和节省预算.