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

杨堤; 李卓青; 杨绿溪; 徐琴珍; Yang Di Li Zhuoqing Yang Lyuxi Xu Qinzhen

网刊加载中。。。

使用Chrome浏览器效果最佳，继续浏览，你可能不会看到最佳的展示效果，

确定继续浏览么?

复制成功，请在其他浏览器进行阅读

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

杨堤
李卓青
杨绿溪
徐琴珍

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

中图分类号： TP391

发布日期：2019-10-17

DOI：10.16337/j.1004-9037.2019.05.004

摘要

激励更多用户参与感知任务并提供高质量数据是移动群智感知研究的热点问题之一。针对在线到达的激励机制场景中，参与用户提供数据的质量以及其信誉值没有得到足够重视等问题，本文提出用户在线参与感知任务的信誉评价方法并构建其信誉评价模型。综合考虑用户历史和现实的信誉记录，建立信誉更新算法模型，设计基于信誉更新的多阶段在线激励机制(Reputation⁃updated online mechanism,ROM)。仿真结果表明，该算法能够帮助平台获得更好的效用，提高收集数据的质量从而提高雇佣效率。

关键词

移动群智感知; 在线激励机制; 信誉更新算法

引言

随着移动互联网技术和应用的迅速发展，移动智能终端得到广泛普及，移动智能终端设备的应用也更为广泛^[

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

1 系统建模

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

19]。用户通过无线网络或蜂窝网络与平台进行通信。

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

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

图1 信息流示意图

Fig.1 Schematic of information flow

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

2 信誉评价机制

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

表1 信誉评价机制符号说明

Tab.1 Description of credit evaluation mechanism symbol

符号	符号说明	符号	符号说明	符号	符号说明	符号	符号说明
$η$	信誉值	$ξ$	信誉值上界	$η_{i}$	用户i当前信誉值	$ζ_{i}$	任务发布方打分
$\tilde{η}$	初始化信誉值	$η_{i}^{*}$	更新的信誉值	$R_{m}$	上次竞标得到的综合评分
$ω_{i}$	时间可靠性	$ϑ_{i}$	图像大小可靠性	$μ$	用户信誉值初始值

2.1　任务发布方打分 $ζ_{i}$

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

2.2　完成任务时间的可靠性 $ω_{i}$

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

$ω_{i} = \frac{d_{i} - a_{i}}{T}$

（1）

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

2.3　图像大小可靠性 $ϑ_{i}$

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

$ϑ_{i} = \frac{|χ_{i} - φ_{i}|}{φ_{i}}$

（2）

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

$R_{m} = \{\begin{array}{l} - \tilde{η} \begin{matrix} L 个数为 3 \end{matrix} \\ - 0.6 \tilde{η} \begin{matrix} L 个数为 2, H 个数为 0 \end{matrix} \\ + 0.6 \tilde{η} \begin{matrix} H 个数为 3 \end{matrix} \\ + 0.4 \tilde{η} \begin{matrix} H 个数为 2, L 个数为 0 \end{matrix} \\ 0 \begin{matrix} 其他 \end{matrix} \end{array}$

（3）

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

$η_{i}^{*} = ϕ (η_{i}, R_{m}) = \{\begin{array}{l} η_{i} + R_{m} \begin{matrix} \begin{matrix} 之前有过质量记录未更新, 且此次被选中资料 \end{matrix} \end{matrix} \\ η_{i} \begin{matrix} \begin{matrix} \end{matrix} & 之前没有质量记录未更新, 且此次被选中资料 \end{matrix} \\ η_{i} \begin{matrix} \begin{matrix} \end{matrix} & 之前没有质量记录未更新, 且此次未选中资料 \end{matrix} \\ \tilde{η} \begin{matrix} 初次参与资料提交初始值 \end{matrix} \end{array}$

（4）

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

假定信誉值阈值的初始值为信誉值最大值的一半 $μ = \frac{ε}{2}$ 。整个信誉更新机制的流程图如图2所示。

图2 考虑信誉的在线激励机制系统流程图

Fig.2 Flowchart of online incentive system considering credibility

3 算法描述

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

$V (W) = \sum_{i \in W} v_{i}$

（5）

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

$m a x V (W) \begin{matrix} s . t . \end{matrix} \begin{matrix} \sum_{i \in W} p_{i} \leq B \end{matrix}$

（6）

为了实现在线处理用户的参与资料，参考秘书问题的多阶段选择的思想^[

20],设计了一种多阶段的采样⁃接受过程^{[参考文献 21
查找原文}21]。该机制动态的增加采样的容量，并且动态的为将来用户子集的选择学习效率密度阈值，效率密度阈值结合之前所述的信誉更新机制得出的信誉分，为平台选取用户提供了标准^{[参考文献 19
查找原文}19]。该算法需要满足：（1）计算有效性，即该算法要在多项式时间内完成；（2）个体合理性，即被选择的用户所得到的报酬大于等于其成本；（3）预算可行性，即支付给所有选择用户的总报酬要小于给定的预算

$B$ ；（4）策略真实性,即保证如果用户谎报其参与资料的话他不会获得更多的报酬^{[参考文献 22
查找原文}22]。

3.1　效率密度阈值更新算法

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

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

算法1 效率阈值更新

输入：阶段⁃预算 $B'$ ，采样集合 $S'$ ，当前时间阶段 $T^{k}$

输出：密度阈值 $ρ$

(1)　 $E^{T_{k}} \leftarrow ϕ$

while $E^{T_{k}} \neq S'$

(2) $i \leftarrow a r g m a x_{j \in S' \ E^{T_{k}}} (v_{i} / b_{i})$

(3) if $b_{i} \leq (\frac{\frac{2 U}{L} v_{i}}{\sum_{j \in E^{T_{k}}} v_{j} + v_{i}}) B$ then

(4) $E^{T_{k}} \leftarrow E^{T_{k}} ⋃ \{i\}$

(5) else break

(6) return $ε (\frac{\sum_{i \in E^{T_{k}}} v_{i}}{\sum_{i \in E^{T_{k}}} b_{i}}) {(\frac{Q}{P})}^{l - k}$

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

$b_{i} \leq \frac{2 U}{L} \cdot \frac{v_{i}}{\sum_{j \in E^{T_{k}}} v_{j} + v_{i}} B$

（7）

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

定义1 如果按照效率进行排列的用户满足 $\frac{v_{1}}{b_{1}} \geq \frac{v_{2}}{b_{1}} \geq \dots \geq \frac{v_{l}}{b_{l}}$ 并且此场拍卖的预算为 $B$ ，那么如果对于2个用户 $x$ 和 $y$ ，满足 $\frac{v_{x}}{b_{x}} \geq \frac{v_{y}}{b_{y}}$ ，且 $b_{y} \leq \frac{2 U}{L} \cdot \frac{v_{y}}{\sum_{j \in y} v_{j} + v_{y}} B$ ，那么 $b_{x} \leq \frac{2 U}{L} \cdot \frac{v_{x}}{\sum_{j \in x} v_{j} + v_{x}} B$ 。

证明：因为 $\frac{v_{x}}{b_{x}} \geq \frac{v_{y}}{b_{y}}$ ，所以 $b_{x} \leq \frac{v_{x}}{v_{y}} b_{y}$ 成立。

那么

$b_{x} \leq \frac{v_{x}}{v_{y}} b_{y} \leq \frac{v_{x}}{v_{y}} \cdot \frac{2 U}{L} \cdot \frac{v_{y}}{\sum_{j < y} v_{j} + v_{y}} B \leq \frac{2 U}{L} \cdot \frac{v_{x}}{\sum_{j < y} v_{j} + v_{y}} B \leq \frac{2 U}{L} \cdot \frac{v_{x}}{\sum_{j < x} v_{j} + v_{x}} B$

（8）

由定义1可知，在阈值算法中，如果while循环在用户 $i$ 处不再满足预算条件，则不需要再考虑其他效用值比用户 $i$ 低的用户 $j$ 。因为 $\frac{v_{i}}{b_{i}} \geq \frac{v_{j}}{b_{j}}$ ，可以推断出 $b_{j} \geq \frac{2 U}{L} \cdot \frac{v_{j}}{\sum_{k < j} v_{k} + v_{j}} B$ 。

3.2　信誉值更新算法

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

3.2.1　信誉值与用户报酬

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

$p_{i} = (1 + g) \frac{v_{i}}{ρ}$

（9）

式中 $g$ 与信誉值成正比，比例系数为 $\frac{1}{κ}$ ，即义 $g = \frac{R_{m}}{κ}$ ， $R_{m}$ 越大，下次用户参与竞拍时会获得越多的报酬。

3.2.2　信誉值与平台价值收益

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

$v_{i}^{*} = (1 + h) v_{i}$

（10）

式中 $h$ 与信誉值成正比，比例系数为 $\frac{1}{κ}$ ，即 $h = \frac{R_{m}}{κ}$ 。 $R_{m}$ 越大，下次用户参与竞拍时会给平台带来越多的价值。

3.2.3　信誉值阈值的更新

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

$\tilde{η} = \frac{\sum_{i \in S} η_{_{i}}^{}}{|S|}$

（11）

3.3　ROM算法

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

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

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

(1) $(t, T^{k}, B^{k}, S', ρ, \tilde{η}, W, O) \leftarrow (1, 2^{- 1} T, 2^{- l} B, \emptyset, ε, μ, \emptyset, \emptyset)$

(2) for $t = 1$ to $T$ do

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

(4) $O \leftarrow O \cup {i}$

(5) for 每一用户 $i$ in $O$ do

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

(7) $η_{i} = η_{i}^{*}$

(8) if $R_{m} > 0$

(9) $v_{i} = m a x (v_{i} + h v_{i}, b_{i} Q)$

(10) end

(11) else $η_{i}$ 和 $v_{i}$ 保持不变

(12) if $\frac{v_{i}}{b_{i}} \geq ρ$ && $\frac{v_{i}}{ρ} \leq B^{k} - \sum_{j \in S} p_{j}$ && $η_{i} \geq μ$ then

(13) if $R_{m} > 0$

(14) $p_{i} \leftarrow (1 + g) \frac{v_{i}}{ρ}$

(15) else

(16) $p_{i} \leftarrow \frac{v_{i}}{ρ}$

(17) $W \leftarrow W \cup {i}$

(18) $O \leftarrow O \ W$

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

(20) if $t = ⌊T^{k}⌋$ then

(21) $ρ \leftarrow$ 效率阈值更新 $(B^{k}, T^{k}, S')$

(22) $T^{k} = 2 T^{k}$ , $B^{k} = 2 B^{k}$

(23) if $W$ 集合中重复到达的用户占所有被选中用户比例 $\geq$ 0.5

(24) $\tilde{η} = \frac{\sum_{i \in S} η_{_{i}}^{}}{|S|}$

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

Tab.2 Running time with variation of the number of participants

参与人数n	100	200	300	400	500
运行时间/ms	1.02	2.05	3.20	5.02	6.03

表3 预算变化运行时间实验结果

Tab.3 Running time with the change of budgets

预算B	1 000	2 000	3 000	4 000	5 000
运行时间/ms	0.87	1.38	2.93	4.01	6.01

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

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

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

图3 预算与价值之间关系仿真结果

Fig.3 Budget versus value

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

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

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

图4 用户数量与平台获得总价值关系仿真结果

Fig.4 The number of users versus value

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

5 结束语

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

参考文献

Guo B, Yu Z, Zhou X, et al. From participatory sensing to mobile crowd sensing[C]// IEEE International Conference on Pervasive Computing and Communications Workshops. [S.l.]: IEEE, 2014: 593⁃598.

Ganti R K, Ye F, Lei H. Mobile crowdsensing: Current state and future challenges[J]. IEEE Commun Mag, 2011, 49(11): 32⁃39.

Guo Bin, Chen Chao, Zhang Daqing, et al. Mobile crowd sensing and computing:When participatory sensing meets participatory social media[J]. Communications Magazine IEEE, 2016, 54(2): 131⁃137.

Li Q, Cao G. Providing privacy⁃aware incentives for mobile sensing[C]// IEEE PerCom. [S.l.]: IEEE, 2013: 76⁃84.

Jaimes L, Vergara⁃Laurens I, Raij A. A survey of incentive techniques for mobile crowd sensing[J]. IEEE Internet Things J, 2(5): 370⁃380.

Yang D, Xue G, Fang X, Tang J. Crowdsourcing to smartphones:Incentive mechanism design for mobile phone sensing[C]// Proceedings of the 18th Annual International Conference on Mobile computing and networking. Istanbul, Turkey: [s.n.], 2012: 173⁃184.

Lee J S, Hoh B. Sell your experiences: A market mechanism based incentive for participatory sensing[C]// Proc IEEE PerCom. [S.l.]: IEEE, 2010: 60⁃68.

Lee J S, Hoh B. Dynamic pricing incentive for participatory sensing[J]. Pervasive Mobile Comput, 2010, 6(6): 693⁃708.

Hoh B. TruCentive: A game⁃theoretic incentive platform for trustworthy mobile crowdsourcing parking services[C]// Proc IEEE ITSC. [S.l.]: IEEE, 2012: 160⁃166.

Schweizer I, Christian M, Julien G, et al. Noisemap: Multi-tier incentive mechanisms for participative urban sensing[C]// Proceedings of the Third International Workshop on Sensing Applications on Mobile Phones. New York: [s.n.], 2012: 145⁃149.

Deng L, Cox L P. LiveCompare: Grocery bargain hunting through participatory sensing[C]// Proc ACM HotMobile.[S.l.]: ACM, 2009: 4⁃6

Albers A, Krontiris I, Sonehara N, et al. Coupons as monetary incentives in participatory sensing[C]// Conference on e⁃Business, e⁃Services and e⁃Society. Trondheim, Norway: [s.n.], 2013: 226⁃237.

Huang K L, Kanhere S S, Hu W. On the need for a reputation system in mobile phone based sensing[J]. Ad Hoc Netw, 2014, 12: 130⁃149.

Wen Y, Shi J, Zhang Q, et al. Quality⁃driven auction⁃based incentive mechanism for mobile crowd sensing[J]. IEEE Transactions on Vehicular Technology, 2015, 64(9): 4203⁃4214.

Singer Y, Mittal M. Pricing mechanisms for crowdsourcing markets[C]// Proceedings of the 22nd International Conference on World Wide Web. Rio de Janeiro, Brazil: [s.n.], 2013: 1157⁃1166.

Singla A, Krause A. Truthful incentives in crowdsourcing tasks using regret minimization mechanisms[C]// Proceedings of the 22nd International Conference on World Wide Web. Rio de Janeiro, Brazil: [s.n.], 2013: 167⁃1178.

Badanidiyuru A, Kleinberg R, Singer Y. Learning on a budget: Posted price mechanisms for online procurement[C]// Proc ACM EC.[S.l.]: ACM,2012: 128⁃145.

Zhao D, Li X Y, Ma H. How to crowdsource tasks truthfully without sacrificing utility: Online incentive mechanisms with budget constraint[C]// IEEE INFOCOM 2014—IEEE Conference on Computer Communications. Toronto, Canada: IEEE, 2014:1213⁃1221.

Zhao D, Li X Y, Ma H. Budget‑feasible online incentive mechanisms for crowdsourcing tasks truthfully[J]. IEEE/ACM Transactions on Networking, 2016, 24(2): 647⁃661.

Babaioff M, Immorlica N, Kempe D, et al. Online auctions and generalized secretary problems[J]. ACM SIGecom Exchanges,2008,7(2): 1⁃11.

Babaioff M, Immorlica N, Kempe D, et al. Online auctions and generalized secretary problems[J]. ACM SIGecom Exchanges,2008, 7(2): 1⁃11.

Bateni M, Hajiaghayi M, Zadimoghaddam M. Submodular secretary problem and extensions[C]// International Workshop on Randomization and Approximation Techniques in Computer Science. Berkeley, CA, USA: [s.n.], 2013: 39⁃52.

您是本站第访问者

通信地址：南京市御道街29号南京航空航天大学(明故宫校区)

邮编：210016 传真：025-84892742

电话：025-84892742 E-mail：sjcj@nuaa.edu.cn

技术支持：北京勤云科技发展有限公司

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

摘要

关键词

引 言

1 系统建模

2 信誉评价机制

2.1 任务发布方打分ζi<math id="M45"><msub><mrow><mi>ζ</mi></mrow><mrow><mi>i</mi></mrow></msub></math>

2.2 完成任务时间的可靠性ωi<math id="M53"><msub><mrow><mi>ω</mi></mrow><mrow><mi>i</mi></mrow></msub></math>

2.3 图像大小可靠性ϑi<math id="M65"><msub><mrow><mi>ϑ</mi></mrow><mrow><mi>i</mi></mrow></msub></math>

3 算法描述

3.1 效率密度阈值更新算法

(1) ETk←ϕ<math id="M99"><msup><mrow><mi>E</mi></mrow><mrow><msub><mrow><mi>T</mi></mrow><mrow><mi>k</mi></mrow></msub></mrow></msup><mo>←</mo><mi>ϕ</mi></math>

3.2 信誉值更新算法

3.2.1 信誉值与用户报酬

3.2.2 信誉值与平台价值收益

3.2.3 信誉值阈值的更新

3.3 ROM算法