Kai H , He H , Jun L . Quality-Aware Pricing for Mobile Crowdsensing[J]. IEEE/ACM Transactions on Networking, 2018:1-14.

简介

移动群智感知被认为是大规模城市数据收集的一种有前景的方法，但也带来了新的挑战性问题，如激励和质量控制。如何在群智感知系统中设置“正确”的价格的基本问题仍然存在。在本文中，我们研究了移动群体感知的质量感知定价问题，我们的目标是选择合适的发布价格来招募具有合适感知质量的一组参与者，以实现稳健的群体感知，同时最小化总预期支付。我们的问题是NP-hard的，并且与泊松二项分布（PBD）密切相关。为了解决我们的问题，我们首先发现PBD的一些新的子模块属性，然后提出一种新的“熨烫方法”，通过影响新发现的PBD属性将我们的问题从非子模块优化问题转化为子模块优化问题。最后，通过熨烫方法，提供了几种具有可证明的性能比的近似算法，并且还进行了广泛的数值实验以证明我们的方法的有效性。

介绍

随着手持设备（如智能手机）和嵌入其中的各种移动传感器的激增，人们越来越关注移动群智感知（MC）。我们最近目睹了MC系统在各个领域的蓬勃发展，例如医疗保健，环境监测，运输和人类活动检测。虽然MC被认为是一种有前途的感知数据收集方法，但移动群智感知也带来了一些独特的研究挑战。由于MC任务的参与者（或用户）必须付出大量人力物力用于感知活动，因此在激发参与者的行为的同时需要适当的经济补偿（即确保真实性）。此外，由于MC参与者在他们的传感设备和他们的感知行为通常是不专业的（导致低感知质量），从单个参与者获得的感知数据可能是嘈杂的甚至是无用的。这使得明智的MC任务所有者有必要选择具有合适感知质量的适当参与者以及引入感知冗余（即形成“人群”）以实现感知稳健性，这最终将使所有者从收集的数据中获得更高的利益。实际上，在数据采集和分布式计算的许多众包应用中强烈要求提高对传感鲁棒性的要求。

基于上述观察，感知任务所有者需要设计适当的激励机制以进行稳健的群体感知。实际上，即使没有考虑到感知质量问题，设计真实群众激励机制也是非常重要的。大多数先前的研究都是基于拍卖来解决这个问题，即所有者向用户征求密封投标，然后决定向每个用户付款。但是，由于用户可能不信任所有者并理解其真实成本的机制，因此实施此方法可能会很复杂。此外，密封投标可能导致对用户的异种支付（也就是“价格歧视”），这可能引起人们的不满。因此，一种更适用的方式可能是发布定价，即感知所有者向参与者宣布一个价格以进行众包活动，然后参与者根据自己的意愿选择加入活动或不加入。许多当前的商业众包系统采用了公布定价方法来激励参与。

尽管公布定价是当前的主流方法，但如何设定“正确”价格以招募具有合适质量（和成本）的人群的基本问题仍然存在。直观地说，如果公布的价格设定得太低，可能会有太少的参与者愿意加入这项任务，从而损害最终感知的稳健性。如果盲目地提高定价，那么所有者可能招募大量用户以实现感知稳健性，但是它会浪费资金在质量非常差的参与者上。 据我们所知，文献中从未研究过招聘成本与移动人群感知中的感知稳健性之间的这种权衡。

A.贡献

在本文中，我们提出了一种新的事前发布定价机制，以实现移动人群中的感知稳健性。我们的目标是选择适当的定价和一组候选参与者，以便最小化支付给参与者的总预期成本，同时招募的具有合适感知质量的参与者的数量大于预定的下限（ 在概率意义上）以保持所需的感知鲁棒性水平。我们将这个问题称为Posted Pricing for Robust Crowdsensing（PPRC） ，并提出了几种算法来解决它具有可证明的性能界限。

由于PBD经常出现在各种研究主题中，包括众包，多传感器融合，模式识别和计量经济学，我们对PBD子模块属性的发现可能有助于解决其中的相关优化问题。其次，我们对“熨烫方法”的想法可以为子模块优化提供新的视角，并且有可能将应用于非子模块优化问题转换为子模块优化问题的其他场景。

问题设置

在本节中，我们正式介绍了我们问题的假设和定义。为清楚起见，我们列出了经常使用的符号含义。假设我们有一个群众感知任务和一组有资格完成任务的n个参与者。每个参与者具有私人类型（q_i，c_i），其表示如果参与者将参与群体感觉任务，则将以成本c_i产生质量q_i的输出。在进行了大量关于众包的工作之后，我们考虑一个标准的贝叶斯环境，其中关于用户质量和成本的“贝叶斯”知识是可用的，即：每个用户类型（q_i，c_i）的联合概率分布对于众包任务所有者是已知的，但q_i和c_i的确切值是未知的。为了接近现实情况，考虑到用户的异构行为和感知能力可能遵循不同的分布函数，假设不同用户的类型是独立分布的。

由于用户通常在参与群智感知时将其感知成本货币化，我们假设有一组有限的候选价格，任务所有者可以从中选择发布给参与者的价格。如果用户的质量太低，他输出的数据可能只是噪音而对任务所有者来说是无用的（或者由于误导甚至是有害的）。我们将这样的用户称为“临时用户”，否则称为“普通用户”。基于这种观察，所有者将设置下限为任何用户的最低质量需求。为了保证传感数据的整体质量，有必要要求多个用户参与任务，以便通过融合多组数据来减少测量误差。因此，我们通过要求至少k个普通用户必须加入群智感知任务，群众感知任务被作为任务所有者的预定义需求来感测鲁棒性。

基于上述考虑，任务所有者可能盲目地向所有用户发布非常高的价格，招募大量参与者以实现稳健性，但这属于“过度支付”。 因此，一个更精明的任务所有者会仔细选择一组目标用户并为他们提供“足够”的发布价格，这样至少k个普通用户最终会加入任务（在概率意义上），而总数（预期）支付所选用户的费用最小化。

定义1：给定一组用户users{1,2，...，n}，一组公布的价格W = {w1，...，wσ}，阈值（k，θ）∈[n]×（0，1），集合P={(u_i，l, p_i，l)|i ∈ [n], l ∈ [σ]} 。鲁棒群体发布的定价（PPRC）问题是找到以下数学优化问题的最优解：

备注：PPRC问题的表述意味着我们只向一组目标用户（即X中的用户）发布价格，以便在质量约束下可以最小化总预期支付。

A.仔细研究问题

根据我们的问题公式，可以看出PPRC问题中出现的随机变量S_l（X）遵循泊松二项分布。 泊松二项分布是众所周知的独立伯努利试验之和的离散概率分布，其不一定是相同分布的，并且存在其p.m.f的精确表达式。更具体地说，如果我们使用Fⁱ_X来表示可以从X⊆[n]中选择的i个整数的所有子集的集合，我们得到以下等式：

如果我们将上述等式输入到定义1中的PPRC问题中，我们将得到非线性0-1整数规划问题，这通常很难解决。实际上，我们发现PPRC问题是NP-hard的。

定理一：PPRC问题是NP-hard的。

解决我们问题的另一个想法是看看ρl（·，k）是否是子模块，所以我们可以应用一些子模块优化技术。

熨烫方法

定理2：给定两组X，Y和两个整数a，b满足X⊆Y⊆[n]和0≤a≤b≤n且a≤| X |，我们得到

根据上述定理，我们现在更接近于解决我们的问题，因为我们已经证明lnρ_l（·，k）=lnΓ_l（·，k，n）是域{X|X ⊆ [n] ∧ |X| ≥ k}的子模块。 但是，我们仍然不能使用现有的子模块优化算法来解决我们的问题，因为：

（1）lnρ_l（X，k）是负的;

（2）lnρ_l（X，k）在| X |< k（ρ_l（X，k）=0）时没有定义。

因此，我们进一步设计了两个替代子模函数Ψ_l和φ_l，它们在2 ^[n]上定义，并且对于任何l∈[σ]与函数ρl对齐。 直观地，这些替代函数在不损害PPRC问题的最优解的最优性的情况下产生将非子模函数ρl“铁”化为子模函数的效果，因此使我们能够将PPRC问题转换为子模块优化问题。 我们称这种方法为“熨烫方法”，并将在下面详细描述。

A. PBD的一般代理函数

我们首先提出一个子模函数Ψ_l（如定理4所示），它作为任意PBD的一般代理函数，因此它也可以应用于其他相关的优化问题。函数Ψ_l不仅在2 ^[n]上是非负的和子模块的，而且还具有Ψ_l在{X：| X | 1}上达到其最小值的良好属性。当Γ_l（X，μ₁，μ₂）= 0，对于具有| X | 1的任意X，Ψ_l与Γ_l对齐。

定理4：给定任何l∈[σ]和任意两个整数μ₁，μ_2，满足0 1≤μ₂≤n，令δ_l= min {Γ_l（X，μ1，μ2）|X⊆[n]∧| X|≥μ₁}定义

如果α_l≥-2lnδ_l，那么我们就有了

1）Ψ_l（·，μ1，μ2）是非负和子模块函数在2 ^[n]上定义。

2）对于任何X₁，X₂⊆[n]，使得| X₁ | 1和| X₂ |≥μ₁，我们有Ψ_l（X₁，μ₁，μ₂）≤Ψ_l（X₂，μ₁，μ₂）

设（S1，S2,....,Sn）是满足p_s1,l ≤ p

由于定理4已经证明Ψ₁是在2 [n]上的子模块，可以看出[PPRC0]问题对于任何给定的l基本上都是“子模块覆盖”问题。

B. PPRC问题的进一步转变

虽然我们已经证明原始的[PPRC]问题可以转化为子模块覆盖问题[PPRC0]，但我们仍然无法用可证明的界限来解决它，因为解决子模块覆盖问题的现有技术通常需要额外的条件。据我们所知，Wan等人提出了解决非整数子模块覆盖问题的最佳性能（如我们的例子），但仅适用于某些特殊的子模块功能。我们引用其结果：

定理5：设F是在2^G上定义的非负单调子模块函数。如果F（∅）= 0，那么这样的F称为多面体函数。假设Yopt是子模块的最优解，覆盖问题和cst（Yopt）是Yopt的成本。假设Yopt是子模块覆盖问题的最优解决方案，而cst（Yopt）是Yopt的成本。如果F（Yopt）= F（G）≥cst（Yopt）并且贪婪算法总是选择x∈G\ X，使得当F（X）

注意，我们有G = [n]，并且[PPRC0]中的成本函数是模块化的。 然而，定理5要求F（Yopt）= F（G）≥opt和F（x | X）≥cst（x）以获得对数比。 为了应用定理5，我们基于Ψl为任何l∈[σ]设计新的代理函数φl，并证明函数φl满足定理5中所需的所有条件。之后我们得到定理6：

使用代理函数φl，我们可以进一步将[PPRC0]问题转换为以下[PPRC1]问题：

由于定理6证明函数φ_l满足定理5中所需的条件，我们可以基于定理5设计[PPRC1]的算法以实现可证明的近似比。但是，[PPRC1]需要知道opt_l（也是[PPRC0]的最佳解决方案），这是不易得知的。

近似算法

首先我们需要证明[PPRC1]是否等同于[PPRC]，我们找到以下定理：

定理7：给定任何l∈[σ]，如果[PPRC]和[PPRC1]不相等，那么我们可以在多项式时间内找到[PPRC]的最优解。

在定理5-7中，直接的方法是在贪婪算法中直接使用φ_l来求解[PPRC1]，如算法1所示。

对于每个l∈[σ]，算法1首先根据定理7尝试找到[PPRC1]的最优解 ，如果找不到最优解，它使用贪婪策略找到近似解（第7-11行）。 算法1输出的最终解决方案是寻找所有l∈[σ]的最小成本（第12-13行）。不幸的是，由于opt

因此，我们可以放弃φ_l并获得算法1所示的算法1等效算法2。

可以看出，算法2与第7-13行中的算法1不同，它首先将具有最小预期成本的k-1个用户添加到结果集中（第7行）。之后，该算法逐个添加用户，每次选择“增量贡献”与其成本的比率最大的用户（第9和12行）。有趣的是，当选择第k个用户时，该算法使用lnmin {ρl（X∪{x}，k），θ} +αl来计算增量贡献（第9行），其中αl可以被理解为k-1个的用户的估计贡献。使用定理5-7，我们可以很容易地得到：

定理8：算法2对PPRC问题的近似比最多为

接下来，我们分析算法2的时间复杂度。算法2的第3行中的排序过程在最坏的情况下花费O（n²）运行时间。在第7-13行的执行过程中，我们为每个i∈[k]维持ρ（X，i）的值。 当X在第7行初始化时，我们可以使用Eqn在O（n²）时间内计算所有i∈[k]的ρ（X，i）。第7-13行的总时间复杂度最多为O（n² + n（n + k））= O（n²）。 第3-15行的时间复杂度由第3行和第7-13行的时间复杂度决定，而第3-15行最多执行σ次。 因此，算法2的总时间复杂度最多为O（n²σ）。

双标准近似算法

在本节中，我们考虑质量约束（即等式（1））与PPRC中的总预期支付之间的权衡，并提出双标准近似算法来解决我们的问题。 我们在定义3中阐明了“双标准近似”的概念：

基于定义3，我们提出了PPRC的双标准近似算法，如算法3所示。

在算法3中，我们使用Ψ_l作为ρl（∀l∈[σ]）的替代函数，并使用贪婪搜索处代替算法1中的处理。然而，我们将贪婪搜索过程的停止规则从φ₁（X）l（X，k，n）1（在算法3的第9行中示出）。这种修正是因为PPRC的双标准近似解决方案中的宽松质量要求，并且参数η和ε1根据定义3和定理4中的Ψ

我们可以证明算法3的近似比，它由定理9表示。

定理9：对于任何ε∈（0，θ），算法3向PPRC问题输出

双标准近似解。

处理未知分布情况和多个任务

在本节中，我们概括了我们处理用户未知分布情况和多个同质群智感知任务的方法。 更具体地说，我们假设存在以在线方式获得的T个同质群智感知任务，并且从获得了针对不同任务的任何用户i∈[n]的感知质量和成本。 在这种情况下，我们的问题变成了“学习动态定价（LDP）”问题，其中任务所有者必须找到针对任何任务t∈[T]的PPRC问题的近似解（Xt，lt）， 观察和学习用户对过去处理的任务的行为（即任务1，...，t-1）。

当用户的分布未知时，任务所有者为任何任务t选择的元组（Xt，lt）可能违反PPRC问题中的质量约束（即，等式（1））。因此，我们引入惩罚函数Q（·）来模拟由于违反等式（1）而导致的任务所有者的损失，其中Q（·）可以是满足

的任何非递减函数.基于此惩罚函数，我们进一步定义PPRC问题的任何解（X，l）的总损失如下：

我们定义了定义4：

根据定义4，我们设计了算法4：

效用评估

我们进行了广泛的数值实验来评估算法的性能。我们的实验目的是证实我们的算法在不同参数设置（如θ，n和k）下的有效性。为了模拟用户在移动众包中的类型，我们生成各种二元分布，包括二进制正态分布，指数分布和均匀分布，作为用户质量和成本的先验知识，任何两个不同的用户的类型遵循不同的分布。将所有生成的分布截断为具有支持[0,1]×[0,1]，并且从（0,1）中随机采样生成每个双变量分布的相关系数，以模拟参与者质量之间的正相关性。在不失一般性的情况下，我们将γ= 0.1设置为任何用户的最低质量需求，并将W = {0.1,0.2，...，0.9}设置为候选价格的集合。

在我们的实验中，我们实现算法2，算法3和算法4用于比较，并且它们分别由我们的图中的“PRC”，“CAA”和“DP”表示。 BCAA中的输入参数ε设置为ε=θ/ 3。 我们还实现了EXACT算法作为基准，通过枚举[n]的所有子集找到PPRC问题的最优解。 由于BCAA和LDP都可以输出仅近似满足等式（1）的解，因此当违反PPRC问题中的等式（1）时，我们使用线性罚函数Q（x）= x来测量任务所有者的损失。 除非另有说明，否则我们在实验中将惩罚因子设置为50。 利用该惩罚函数，在我们的比较中使用等式（6）中定义的总损失L（X，l）作为度量。

由于EXACT具有指数时间复杂度，我们首先将PPRC，BCAA和LDP与图中大量人群的情况在图1-3进行比较，其中报告的数据是超过1000个数据集（1000个任务）的测试算法的平均总损失（ATL）。

在图1中，我们研究了实现的算法的性能如何受到用于控制所选用户质量的阈值的影响。最终我们得到结论，需要选择更多用户以满足更大θ的等式（1）。

在图2中，我们将人群的大小从1500缩放到3500，每个子图中增加200，并且k和θ的值也变化，可以看出PPRC优于其他算法。 此外，当n增加时，PPRC和BCAA输出的ATL都减少，这可以解释为当人群规模增加时用于选择用户的搜索空间扩大，因此可以发现具有较小成本的组满足质量需求。最后，可以看出LDP的ATL随着n增加，因为在LDP的“探索阶段”中发生的总损失随着人群规模而增加。

在图3中，我们通过在n，k和θ的不同设置下将惩罚因子从10缩放到100来研究所实现的算法的性能。 可以看出，所实现的算法的相对性能类似于图1中的相对性能，而与惩罚因子的变化无关。此外，图3显示，PPRC的ATL不受影响，而LDP和BCAA的ATL增加。这是因为LDP和BCAA都有可能输出违反约束条件（1）的解决方案，而PPRC则不会。

在图4中，我们将任务数量从100扩展到1000并测试PPRC和LDP的ATL，并且n，k，θ的值分别设置为500,100和0.2。可以看出，当T增加时，LDP的性能逐渐接近PPRC。

需要注意的是，EXACT或PPRC的总损失等于PPRC问题的优化函数的值（即，总预期成本），因为这两个算法的输出总是满足等式（1）。因此，我们比较EXACT和PPRC，以了解PPRC的解决方案输出的最优性。由于EXACT具有指数时间复杂度，我们必须在人群规模较小的情况下比较PPRC和EXACT，结果如图5所示。

在图5中，我们在k和θ的不同设置下缩放n的值。每个数据点是50多个数据集的模拟结果的平均值。从图5中可以看出，当n增加时，EXACT和PPRC的总成本降低。这可以通过类似于图2的原因来解释，即，具有较小成本的用户组可以在具有更多用户的更大搜索空间中找到。更重要的是，图5显示PPRC的性能非常接近于EXACT，而与n，k和θ的变化无关。这证实了我们的算法的有效性。

致谢

本文由南京大学软件学院2019级硕士吉品翻译转述。

閱讀更多 慕測科技 的文章

關鍵字: 分布式计算 设计 算法