基于拍卖模型的移动群智感知网络激励机制

刘媛妮，李垚焬，李慧聪，李万林，张建辉，赵国锋,3

（1. 重庆邮电大学通信与信息工程学院，重庆 400065；2. 国家数字交换系统工程技术研究中心，河南 郑州 450002；3. 重庆市高校光通信与网络重点实验室，重庆 400065）

1 引言

移动群智感知[1]技术的出现，使人们可以利用大量的智能终端随时随地感知和获取周围环境信息。在感知数据的过程中，为提高用户参与感知任务的积极性，需要设计相应的激励机制[2]，使尽可能多的用户参与到感知活动中，保证感知任务按时按需完成。目前，移动群智感知的激励形式根据回报方式主要分为基于金钱式的激励形式和非金钱式的激励形式。基于金钱式的激励形式通过报酬支付的方式回报参与者的感知数据，非金钱式的激励形式主要包括娱乐游戏的激励[3-6]、信誉值的激励机制[7-8]、虚拟积分激励[9-11]等。针对这些激励形式，Reddy等[12]指出基于报酬支付的激励形式效果更好。基于博弈论的方法是报酬支付激励的主要方式，而拍卖机制则是其核心，如逆向拍卖、组合拍卖、多属性拍卖、全付拍卖、双向拍卖等。通常，设计一个合理的基于拍卖模型的激励机制需要考虑个体理性（individual rationality）、真实性（truthfulness）、社会福利（social welfare）、计算有效性（computation efficiency）等特性[13]。总之，激励形式研究如何对参与者进行各种形式的报酬激励、娱乐激励、精神激励、荣誉激励等，以满足参与者的心理需求，促使其加入感知任务中。

在群智感知中，激励机制的目标是激励尽可能多的参与者去执行感知任务，即提高参与率。从时间维度考虑，感知平台不仅希望参与者参与到感知任务中，还希望其能够在感知活动中保持参与的长期性。然而，由于参与者的自私性和不确定性，使基于拍卖模型的移动群智感知激励机制的设计面临一定的挑战。自私性在于，移动群智感知中的智能终端用户受限于设备自身的处理能力、存储空间、电池能量等，从而不愿意无偿地参与感知活动。不确定性在于，参与者的感知能力取决于感知设备的能力、主观的个人感受等因素，同时人的随机移动或突发状况会导致用户感知活动的中断，降低任务完成率。进一步地，感知平台通过招募新的感知用户来完成被中断的任务，这种方式将会造成平台支付成本的增加。为吸引更多的用户参与，大量的激励机制[14-19]被提出，然而大多数研究工作[17-19]都假设被选择执行任务的用户均能完成感知任务，即任务覆盖与任务完成为同等概念。针对因人的不确定性而导致的用户随机退出的情况，通过设计预防的激励机制促使用户在系统中呆得时间更久，较少考虑用户退出后具体的应对措施。

为了解决上述问题，本文提出了一种基于拍卖模型的移动群智感知网络激励机制。首先，为保证激励机制的真实性，尽可能提高用户在系统中的感知时间，提出了一种基于逆向拍卖的激励模型（IMRA, incentive mechanism based on reverse auction），在平台预算可行的前提下最大化用户效用，提高用户参与感知的积极性及任务覆盖率。进一步地，考虑到用户不确定性将会导致用户中途退出、降低任务完成率的问题，提出一种基于用户双向交互的激励机制（UBIM, users’ bidirectional-interaction incentive mechanism），使中途退出的用户可以将未完成的感知任务转售给新用户，尽可能在不增加平台成本的前提下提高任务完成率。本文的贡献主要包括以下几点。

1) 提出了一种基于逆向拍卖的激励模型IMRA。针对在赢标者选择过程中，满足一定覆盖条件下的用户选择是NP-hard问题的情况，提出了一种以任务为中心的赢标者选择算法，来提高用户效用和任务覆盖率，该算法的计算复杂度为多项式时间。在报酬支付阶段，采用基于临界价格的报酬支付算法，根据用户执行的任务采用按时间比例分享规则对用户进行任务奖励，激励用户在感知活动中的停留时间，并最大化用户效用。

2) 针对用户中途退出的情况，提出了基于用户双向交互的激励模型UBIM，通过设计动态双向拍卖过程，使临时退出的感知用户将未完成的感知任务转售给新的感知用户，并针对单周期内用户匹配问题，提出了基于二部图的用户匹配算法，在不增加平台成本的同时提高任务完成率。

3) 对本文提出的IMRA与文献[15]中的TRAC（truthful auction for location-aware collaborative sensing in mobile crowdsourcing）机制及文献[19]中的IMC-SS（incentive mechanism for crowdsourcing in the single-requester single-bid-model）机制分别就用户平均效用、任务覆盖率、任务完成率和平台效应 4个方面进行对比。进一步地，从任务完成率和平台成本这2个指标对UBIM机理模型的有效性进行了分析。实验结果表明，本文所提激励模型IMRA可以有效地提高用户参与感知的积极性和任务覆盖率，并且在用户中途退出的情况下，引入UBIM可以提高感知任务的完成率并降低感知平台的支付成本。

2 相关工作

为了提高用户的参与率，许多针对用户自私性的基于拍卖模型的激励机制被提出，然而，目前的激励机制更多地考虑如何使感知平台的效益最大化[20]（如任务的时空覆盖率、被完成的任务数量、平台的预算限制等）。文献[14]提出了一种用于多请求者MCS（mobile crowd sensing）系统的新型集成框架，该框架中的激励机制基于双重拍卖模型进行设置，更符合实际中常见的情况。文献[15]基于逆向竞拍框架设计激励机制TRAC 时，考虑任务与位置的相关性，用户根据自身所在的位置和感知范围，竞价多个感知任务，平台根据汇总的竞价来选择赢标者以最小化支付代价。文献[21]将数据收集者和中继用户的协作视为双用户合作博弈问题，提出了利用非对称纳什协商方案，激励用户进行感知数据的收集。文献[16]提出了一种单一的逆向组合的拍卖机制，该机制在拍卖过程中考虑了隐私泄露成本，激励用户以真实成本参与竞拍以保证激励机制的真实性。文献[22]提出了一种在线拍卖机制，在系统寿命中进行多轮拍卖，以优化整个系统生命周期内社会成本。Zhao等[23]考虑用户在到达时刻向平台提交竞价的场景，通过在每个时间周期内选择合适的用户子集达到在预算约束下最大化平台的效用。文献[24]为在一定的预算前提下鼓励用户完成一组二进制的标记工作，通过连续贝叶斯方法对收集的标记进行聚类，并且基于逆向竞拍模型设计激励机制，最终平台能在一定预算内实现较高的效用。Luo等[25]提出了一种用于多个合作任务的拍卖机制，在服务器获得目标价值的情况下最小化服务器的支付。文献[26]在平台预算的约束条件下最大多个任务的整体效益。这些研究以最大化平台效用为首要目的，但没有优先考虑参与者的效益，无法高效地激励参与者加入感知任务。从用户的角度出发，在预算可行的前提下以最大化用户效用为目标设计激励机制，会起到更好的激励作用。

针对用户不确定性，文献[27]中指出在参与式感知中，激励用户长期参与感知活动是至关重要的。该文献基于VCG(Vickrey-Clarke-Groves)竞拍模型设计激励机制在线选择用户，将参与者的报酬根据时间段分多次进行支付，实现了激励的长期性。文献[11]为了在满足最小化平台支付代价的同时保证较高的参与率，采用逆向拍卖机制选取出价最低的参与者作为赢家并支付，同时引入虚拟参与积分的概念，避免在竞价中屡次失败的参与者退出。文献[17]提出了2种激励模型，分别为以平台为中心的激励模型和以用户为中心的激励模型，前者通过计算唯一的斯塔克尔伯格均衡，最大化平台效用，用户仅依据时间因子进行计算；后者基于逆向拍卖模型设计机制Msensing，相比于前者，Msensing具有用户上报竞价的过程，用户具有一定的主动权。Zhang等[19]考虑多个用户竞标任务的情形，提出了 SS(single-requester single-bid)模型，在此模型的基础上提出了IMC-SS机制，该机制由工作组选择、赢标者选择和报酬支付这 3个阶段组成。Jaimes等[18]设计了基于多轮逆向竞拍的激励机制，鼓励用户参与需要连续和定期抽样的感知计划。该机制在选择用户时不仅考虑了用户的竞价也考虑了用户的地点，实验结果表明，该机制在实现最优预算利用率的同时确保感知区域被覆盖并保证每一轮竞拍有足够的用户。上述研究大都假设赢得任务的用户能完成任务并上传数据，激励机制的目标是促使用户在系统中的停留时间更长，并未对赢标者在执行任务的过程中退出感知任务的后续动作提出应对措施。在这种情况下，如果平台重新招募用户来继续执行未完成的感知任务，则需要为新招募的用户支付报酬，导致平台感知成本增加。

3 问题定义

本文所提方案的激励过程如图1所示。首先，利用基于逆向拍卖的激励模型IMRA提高用户效用及任务覆盖率，并通过设计合理的报酬支付方式，保证激励机制的真实性。进一步地，针对感知用户在执行任务过程中需要临时退出，感知平台招募新用户导致其支付成本增加的问题，本文提出基于用户交互的双向竞拍激励模型，使中途退出的用户可以将未完成的感知任务转售给新的感知用户，并在不增加平台成本的前提下保证任务的完成率。本框架只考虑两轮的感知用户招募，不再考虑UBIM过程中新用户继续退出的情况，即UBIM过程中感知任务的转售成功则代表该感知任务将会被完成。否则，UBIM过程将会由于第i轮中用户的退出而被触发第(i+1)轮的UBIM招募过程，在最坏情况下，该过程可能会被无限循环。考虑基于拍卖模型的移动群智感知网络中的感知平台需要从多个用户中选择用户集来满足感知任务的覆盖需求。设集合为群智感知平台发布的感知任务集，m为总任务数，τx∈Γ为任务集中每个单独的任务，设其开始时间为si，截止时间为di。设用户完成感知任务τx所需的时间为tx，任务τx的价值为Vx，并且dx-sx≥tx。定义U= {u1,u2,… ,un} 为对任务感兴趣的用户集，用户ui(i= 1 ,2,… ,n)上报的任务子集为Γi⊆Γ，用户竞价为bi，定义Bi=(Γi,bi)为用户ui的任务竞价对。参见文献[15,19]，本文给出以下定义。

图1 基于拍卖模型的移动群智感知网络激励机制框架

定义1 任务覆盖。若任务τx的赢标者数量numx≥ 1，则表示该任务被覆盖，numx= 1 代表有一人执行任务。

定义2 卖方用户。设为图1中UBIM阶段的卖方用户，即对IMRA阶段未被完成的任务感兴趣，愿意参与数据感知的用户。

定义3 买方用户。设为图1中UBIM阶段的买方用户，即在IMRA阶段中赢得感知任务但在执行任务的过程中临时退出感知的用户。

4 基于逆向拍卖的激励机制

4.1 IMRA过程问题描述

基于逆向拍卖的激励机制中群智感知平台与用户的互动过程如图2所示，具体步骤如下。

图2 群智感知平台与用户互动过程

表1 本文所用符号及其含义

2) 用户有休眠和投标这2种决策，用以决定是否参与感知任务。休眠指用户不参与感知任务，此处通过引入感知任务0，当用户选择感知任务0时，即为休眠，其效用为 0。决定投标的用户ui上报任务竞价对Bi=(Γi,bi)，其中，Γi(Γi⊆Γ)为用户上报的任务子集，bi为用户针对该任务子集上报的竞价，即用户ui的逆向竞拍价格。

4) 赢标者执行感知任务，提交感知数据至感知平台。

5) 感知平台根据赢标者ui的任务完成情况对其支付报酬pi。

用户ui的效用为其参与感知任务得到的报酬pi与其感知成本ci的差值，即

感知平台的效用为任务的总价值v(S)与所有赢标者的总报酬支付之间的差值，即

逆向拍卖的问题为，预算有限的前提下，最大化用户效用，其形式化描述和约束条件为

其中，B为平台的预算，且B≤v(S)。

由式(3)可知，基于逆向拍卖的激励机制需解决2个问题：1) 确定拍卖成功的用户，在最小化社会成本的同时最大化任务覆盖；2) 设计合理的报酬支付方法，激励用户按照其执行感知任务的真实估价进行竞价。

4.1.1 赢标者选择问题

定理1 赢标者选择问题为NP-hard问题。

证明为了证明此问题是NP-hard问题，首先介绍加权多任务集覆盖问题的概念，该问题已被Yang 等[28]证明为NP-hard问题。

加权多任务集覆盖问题的一个实例如下。设有n个子集Y= {Y1,Y2,… ,Yn}，其基本元素为E= {e1,e2,… ,em}，以及正整数K和m元组(w1,w2,… ,wm)。加权多任务集覆盖问题为判断是否存在一个包含了K个子集的集合，使每一个元素ex(ex⊆E)至少被覆盖的次数为wx。

用户选择问题可以转化为加权多任务集覆盖问题的一个实例，具体如下。任务集合Γ对应集合E，即任意τj∈Γ对应ej∈E。每一个子集Yi∈Y对应每一个用户ui∈U上报的任务集iΓ，任务集iΓ中包含的任务对应Yi中的基本元素。每一个元素ex被覆盖次数至少为wx，则对应为任务jτ至少被wj个用户覆盖。这说明加权多任务覆盖问题能在线性时间内归约到赢标者选择问题，即赢标者选择问题是NP-hard问题的。

证毕。

4.1.2 报酬支付问题

激励机制需要考虑用户执行过程的真实性，Myerson[29]证明了一个真实的拍卖机制必须满足 2个条件，分别选择规则是单调的和赢标者的奖励值是临界价格。单调性即如果用户以竞价bj成为赢标者，那么以仍能成为赢标者，其中代表非真实竞标价。临界价格指的是，如果竞标价bj高于临界价格pj，那么该竞标用户将不会成为赢标者。

因此，对于任意用户ui，令bi表示用户对感知成本的真实估价，则任务竞价对为用户的真实竞标，将该竞标策略下用户的效用表示为表示用户的非真实竞标，将该竞标策略下的用户效用表示为ui(Bi′)。

4.2 以任务为中心的赢标者选择算法

针对赢标者选择NP-hard问题，需要找到一种计算复杂度较低的解决方案。文献[30]指出，当参加同一感知任务的用户数量增加时，数据冗余所导致的边际递减效应会越发严重。因此，在感知任务价值一定的情况下，参与同一任务的用户越多，每个用户获得的报酬越少。本文结合感知数据收集存在边际递减效应的现象，假设每个任务由一人执行，在用户选择阶段，提出以任务为中心的赢标者选择算法，即对每一个任务，选择竞价与上报的任务总价值的比值最小的用户作为赢标者。

以任务为中心的赢标者选择算法的基本思路如下。当任务xτ的竞标者数量为1时，若该竞标者的竞标价bi与上报任务的总价值vi的比值小于 1，则其为任务xτ的赢标者；当任务xτ的竞标者数量大于1时，计算每个竞标者的竞标价bi与其竞标任务的总价值vi的比值并升序排列，如式(6)所示。选取比值最小且小于1的竞标者作为任务xτ的赢标者。

以任务为中心的赢标者选择算法的伪代码如算法1所示。

算法1 以任务为中心的赢标者选择算法

输入任务集Γ={τ1,τ2, …,τm}，任务价值集合V= {V1,V2,…,Vm}，用户任务竞价对

输出赢标集S，赢标集覆盖的任务集Γ′，以及任意xτΓ′′∈的竞标用户上报的竞价与其上报任务总价值的比值的最小值与最大值

初始化S←φ，Γ′′←φ；

1) 根据Bi=(Γi,bi)统计用户上报的任务集Γ′(Γ′⊆Γ) ，每一任务的竞标用户集合Uτx及竞标者数量ni

11)

4.3 基于临界价格的报酬支付算法

确定赢标集后，平台根据用户的任务完成情况对用户进行支付，分别考虑用户正常完成任务和用户中途退出这2种情况。为了保证激励的真实性并激励用户长时间参与，根据文献[29]中临界价格的概念，提出了一种基于临界价格的报酬支付算法。

考虑用户正常完成任务和用户中途退出这2种情况下的支付，在考虑用户竞价bi的同时根据用户执行的任务采用按时间比例分享规则对用户进行任务奖励Tτx。具体地，用户的支付函数为

其中，Γi′表示用户ui赢得的任务集合，τx∈Γi′，Tτx表示用户执行任务τx后得到的任务报酬。Tτx计算式如式(8)所示。

其中，tx表示完成任务τx所需要的时间，Δtx表示用户ui执行任务τx的时间。如果任务τx的竞标者仅有用户ui一人，且竞标成功，在计算Tτx时用代替式(8)中的。基于临界价格的报酬支付算法的伪代码如算法2所示。

算法2 基于临界价格的报酬支付算法

输入赢标集S，赢标集覆盖的任务集Γ′，以及任意xτΓ′′∈ 的竞标用户上报的竞价与其上报任务总价值的比值的最小值与最大值

输出报酬支付值pi

初始化pi← 0 ，Γ′′′←φ，Γ′表示被赢标者完成的任务集合；

4.4 理论分析

根据文献[24]所述，一个可行且有效的竞拍机制需满足计算有效、个体理性、预算平衡和真实性（即激励相容）4个特性，下面将对IMRA这4个特性进行理论分析。

引理1 IMRA是计算有效的。

证明算法1中的for循环（算法1中2)～16)）的时间复杂度为O(m)，算法 1中 9)的排序算法的时间复杂度为O(nlogn)，因此，算法1的时间复杂度为O(mnlogn), 即算法 1的时间复杂度为多项式时间。算法2中的第一个for循环（算法2中1)～7)）的时间复杂度为O(m)，第二个for循环（算法2中8)～12)）的时间复杂度为O(n)，因此，算法2的时间复杂度为O(n)，即算法2的时间复杂度为多项式时间。综上所述，IMRA的时间复杂度为多项式时间，即IMRA是计算有效的。

证毕。

引理2 IMRA是个体理性的。

证明若用户ui竞标失败，其则；若用户ui竞标成功，其则。综上，用户效用大于0，满足个体理性。证毕。

引理3 IMRA是预算平衡的。

证明算法 2中 13)～15)保证，当支付的报酬不大于完成任务的总价值时，才会启动任务，此时，平台效用大于或等于 0，否则任务启动失败，平台效用为0，因此该机制满足预算平衡。

证毕。

引理4 IMRA满足真实性。

证明分别从单调性和临界价格两方面证明。单调性：由于将从小到大进行排序，若用户成为赢标者，当用户以竞标时，由于不变，用户ui同样可成为赢标者。

临界价格：假设参与竞标任务xτ的用户数不小于2，用户ui以竞价bi成为赢标者，则其支付如果用户ui以大于pi的值作为竞标价，那么则因可得那么用户u将不能赢得任务τ，故ix若用户以大于pi的值作为竞标价将不会成为赢标者，因此，该机制满足激励相容特性。

证毕。

综上所述，IMRA满足计算有效、个体理性、预算平衡和真实性。

5 基于用户交互的双向竞拍机制

5.1 UBIM过程问题描述

基于用户交互的双向竞拍机制（UBIM）的交互过程如图3所示。该交互过程有3个交互主体，分别为买方用户卖方用户和感知平台，具体交互过程如下。首先，需要中途退出的买方用户即感知数据请求方在平台发布感知任务需求，卖方用户即感知数据提供方在得知具体的任务需求后，向感知平台提交感知计划。假设用户交易的总时间周期为T，即t= 1,2,3,…,T。每一个用户有其特定的感知类型为用户到达和离开的时间，并且假设用户的最大到达-离开时间间隔为I，称之为最大等待耐心。对于买方用户wi=bi，为买方用户对感知数据的竞价，表示不高于此价购买感知数据，对于卖方用户wj=sj，为卖方用户对感知数据的要价，表示不低于此价卖出感知数据。在每个时间周期t内，买方用户和卖方用户通过用户匹配策略进行匹配，确定赢标者。赢标买方用户将赢标卖方用户推荐给平台，卖方用户将感知数据发送给平台，完成感知任务后，赢标买方向将平台原先支付给买方用户的报酬支付给卖方用户，向赢标卖方支付报酬pi。因此，买方效用为卖方效用为

图3 基于用户交互的双向竞拍机制交互过程

5.2 基于双向拍卖的动态激励模型

双向拍卖机制的主要思想如下。假设总拍卖周期为T，即t= 1,2,3,…,T，在每个周期t内，分别将到达的买方用户和卖方用户加入集合B(t)和S(t)中。在拍卖阶段，通过设计匹配规则选择出赢标买方用户集BW(t)和赢标卖方用户集SW(t)。进一步地，为提高用户参与竞拍的积极性，对于未进入赢标集而其离开时间di＞t的用户可作为生存者进入下一周期，根据文献[31]，令SNTB(t)和SNTS(t)分别表示周期t内的买方生存者和卖方生存者，否则，未进赢标集的用户为失效者，不能再参与竞拍，将其加入集合h(t)内。

在用户交易的单个时间周期t内，对买方用户与卖方用户进行匹配，以最大化任务完成率为目标，该目标可表示为

约束条件为

其中，式(9)表示激励目标是完成尽可能多的感知任务，以提高任务完成率。若买方用户与卖方用户匹配成功，式(11)与式(12)分别表示在周期t内任意一个买方用户或卖方用户至多可与一个卖方用户或买方用户匹配成功。当时，表示欲中途退出的用户通过第二轮的招募将其感知任务成功转售给，即参与第一轮招募的感知用户退出后，其未完成的任务将由负责完成。此处不再考虑第二轮用户的退出导致任务无法被完成再进行第三轮甚至后续第N(N→∞)轮的新用户招募的无限循环的过程。因此，可以假设在第二

文献[32]证明，一种双向拍卖机制虽然不可能同时满足计算有效、个体理性、预算平衡和真实性这4个特性，但可以满足其中的部分属性，其中，个体理性、预算平衡和真实性3种属性是双向拍卖机制可信性和有效性的基本保证。此外，设计的机制需满足计算有效，即在单个时间周期内用户的匹配可在多项式时间内输出结果。

5.3 单周期内基于节点度和边权值的用户匹配算法

多用户匹配问题可以被看作二部图(V,E)的一对一匹配问题，其中，V表示买卖双方，E表示用户的竞标情况。若买方用户与卖方用户有边相连则表示卖方用户对买方所持有的任务进行了竞标。用户匹配问题可运用整数规划方法进行描述, 由于式(11)～式(13)的限制，式(9)可以简化为 0-1 规划问题。0-1规划问题已被证明为是NP完全问题[33]，因此，用户匹配问题为NP完全问题。

在基于节点度和边权值的用户匹配算法中，为保证较高的任务完成率，将买方节点按节点的度升序排列，节点度低的优先匹配。在匹配过程中，每条边有一个权值W=bi-sj，为使所有参与者效用总和最大，将权值最大且不小于0的边对应的用户作为赢标者。设B(t)与S(t)分别表示在周期t内到达的买方用户集和卖方用户集，|B(t)|和|S(t)|分别表示用户集B(t)中买方用户数和用户集S(t)中卖方用户数，BW(t)和SW(t)分别表示在周期t内的赢标买方用户集和赢标卖方用户集。基于节点度和边权值的用户匹配算法的伪代码如算法3所示。用户匹配成功后，为保证激励的真实性，在交易中，定义交易

算法3 基于节点度和边权值的用户匹配算法

输入B(t)，S(t)，V=B(t) ∪S(t)

输出BW(t)，SW(t)

5.4 双向激励机制理论分析

本节通过理论分析证明设计的动态激励机制满足个体理性，激励相容和计算有效。

引理5 本文提出的动态激励方法满足个体理性。

证明对于任意一个买方用户ub∈ub，若其没i有成为赢标者，其效用u(uib) = 0 ，若其被选为赢标者，其效用因此，对于任意一个买方其效用。综上所述，对于任意一个买方用户，本文提出的动态激励算法是个体理性的。

证毕。

引理6 本文的双向拍卖算法是激励相容的。

证明当且仅当以下条件被满足时，拍卖算法是激励相容的：1) 其任务分配方法是单调的；2) 每个竞拍成功的用户都得到了临界价格的报酬。

首先，证明其单调性：假设n(n≥ 2 )个卖方用户竞标买方用户ub的任务，在任务分配中，卖方用

i户赢得感知任务，若其以竞标，且因为bi不变，则卖方用户同样可赢得任务。

其次，证明每个赢标者都支付(得到)了临界价格：对于任意一个以竞价sj赢得任务的卖方用户对其支付若用户以大于p的值i作为竞价，那么有则由成为赢标者的基本条件bi≥sj可知用户将不会成为赢标者，因此，每个卖方用户都得到了临界价格。同理可证，每个买方都支付了临界价格。

证毕。

引理7 本文的双向拍卖算法是计算有效的。

证明算法3中1) 的排序算法时间复杂度为O(|B(t) |log|B(t) |)，for循环（算法 3中 2)～14)）的时间复杂度为O(|B(t) ||S(t) |log|S(t) |)，因此算法3的时间复杂度为O(|B(t) ||S(t) |log|S(t) |)。由算法3的时间复杂度的分析，可得出在线竞拍算法的时间复杂度为O(T|B(t) |(|B(t) |+|S(t) |log|S(t)|))。因此，动态激励方法可在多项式时间内输出结果。

证毕。

6 实验验证与分析

6.1 对比算法

为了验证本文所提IMRA机制的性能，将其分别与文献[15]中的TRAC（truthful auction for location-aware collaborative sensing in mobile crowdsourcing）机制及文献[19]中的 IMC-SS（incentive mechanism for crowdsourcing in the single-requester single-bid-model）机制进行对比。进一步地，通过实验对比，分别使用UBIM招募用户与使用IMRA机制时平台招募新用户下的任务完成率和平台成本这2个指标，来分析本文双向激励机制的有效性。

6.2 实验设置

具体实验场景为感知平台发布 100个感知任务，且移动群智感知系统中有500个用户对任务感兴趣，首先通过IMRA机制激励用户参与感知，然后对于赢标用户未完成的任务平台分别直接招募用户或采用UBIM机制招募用户参与。

为验证IMRA机制的有效性与可行性，根据文献[23,19]，设置感知任务的成本和价值均服从均匀分布。假设中途退出的用户数占总用户数的比例为p( 0 ≤p≤ 1) ，若用户中途退出，则定义其执行任务的时间与完成任务所需时间的比值服从（0,1）均匀分布。IMRA机制仿真参数设置如表2所示。

表2 IMRA机制仿真参数设置

进一步地，为了验证基于双向拍卖的动态激励机制的有效性和可行性，进行仿真实验，实验参数如表3所示。假设用户的等待耐心为I，拍卖总周期T=100，根据文献[15,22]，设置买卖双方的报价服从(0,5]均匀分布，单位时间内用户的到达次数服从泊松分布，到达率为λ，最大等待耐心与到达率的值分别设置为6和10[33]。在激励用户参与未被完成的任务时，分别对比了竞标用户数为{10, 20, 30,40, 50, 60, 70, 80, 90, 100}的仿真结果。

表3 UBIM机制仿真参数设置

6.3 评估指标

首先，对本文提出的IMRA机制与对比方法在用户平均效用、任务覆盖率、任务完成率和平台效用这4个方面进行比较，然后，对UBIM中提出的动态激励机制从系统效率和社会福利这2个方面进行评估。相关指标定义如下。

1) 用户平均效用：所有赢标者的总效用与赢标者数量的比值，即其中，|S|为赢标者的数量。

2) 任务覆盖率R：定义其中，cov表示被所有赢标者覆盖的任务数，m表示总任务数。

3) 任务完成率γ：所有赢标者完成的任务数com与总任务数m之比，即

4) 平台效用：评估激励方法预算是否可行的重要评估指标，可根据式(2)进行计算。

5) 系统效率μ：完成的请求任务数与请求任务总数之比，即其中 |BW|表示赢标买方的总数，α表示买方用户总数。

6)社会福利：所有参与者的效用之和，即

6.4 实验结果与分析

1) 用户平均效用

图4显示了IMRA和TRAC、IMC-SS的用户平均效用对比。在图4(a)中，对于IMRA而言，当任务数较少时，用户间较强的竞争使赢标者数量较少，任务支付集中在少数用户，因此，用户平均效用较高。随着任务数的增加，用户的选择更加广泛，竞争性降低使赢标用户数增加，而能被用户完成的任务的总价值趋于稳定，进而用户平均效用降低。在图4(b)中，随着用户数的增加，用户完成的任务数增加，总任务支付增加使用户平均效用随之上升。当用户数的增加使用户完成的任务数达到饱和时，用户的平均效用趋于平衡。相较于 TRAC和 IMC-SS而言，TRAC机制与IMC-SS机制的报酬支付只与其竞价和任务数相关，而IMRA中任务支付的累加效用使用户可得到相对较高的任务补偿，提高了用户参与感知任务的积极性。

2) 任务覆盖率

图5显示了3种激励机制下的任务覆盖率。从图5中可以看出，IMC-SS下的任务覆盖率略低于IMRA下的任务覆盖率，而当用户数接近或小于任务数时，TRAC下的任务覆盖率较低，其原因在于TRAC在赢标者选择阶段贪婪地选择竞价低、上报任务数多的用户，而在报酬支付阶段需找到能包含被支付用户任务集的用户。当TRAC在用户数接近或小于任务数时，很难找到满足条件的用户对赢标者进行支付，导致用户支付失败，进而出现任务覆盖率较低的现象。结合用户效用和任务覆盖情况，可得，相比TRAC和IMC-SS机制，IMRA下用户的积极性较高。

3) 任务完成率

图 6为感知任务完成率的对比。TRAC和IMC-SS这2种机制均假设任务覆盖即任务完成，因此，其任务完成率与其任务覆盖率变化趋势相同，而IMRA考虑用户的随机性导致用户在执行任务时中途退出，造成感知任务未被完成的情况。从图6(a)中可看出，当用户数为100时，随着任务数的增加，3种机制下的任务完成率均呈上升趋势，且当任务数为10～60时，IMRA下的任务完成率低于TRAC和IMC-SS下的任务完成率。在图6(b)中，当任务数为 100时，随着用户数的增加，TRAC和IMC-SS下的任务完成率都趋近于100%，而在考虑了用户执行任务过程中可能会中途退出的IMRA下，总有任务未被完成。由此可看出，用户的随机性对任务完成会产生影响。

4) 平台效用

图4 用户平均效用对比

图5 任务覆盖率

图7是群智感知平台效用的对比。从图7(a)中可以看出，在用户数固定时，IMRA和IMC-SS下的平台效用随着任务数的增加而增加，并且，相比于IMC-SS，IMRA平台效用较低，原因有2个：① 用户的中途退出使得任务未被完成，导致被完成的任务的总价值较低；② 此激励方法下用户的报酬支付较高。TRAC下，平台效用随着任务数的增加先增加后减少，主要原因在于其在用户数接近或小于任务数时，任务完成率较低。在图7(b)中，3种激励方法的平台效用为先增加后趋于稳定，是由于随着用户数的增长，任务完成率增加，当任务集饱和后，平台效用不再增加。

5) 系统效率

系统效率为匹配成功的买方用户数与总买方用户数之比，反映了感知任务完成率。从图8(a)可以看出，随着卖方用户数的增多，使更多的供给产生更多的选择，对于买方用户来说，可以满足更多的需求，导致更高的系统效率。最后，系统效率的增长速度减慢并趋于稳定，原因是当卖方用户数稳定时，大部分的买方用户已经完成了交易，额外的卖方用户对系统效率贡献较少。如图8(b)所示，当拍卖的买卖双方总数分别为50、100和150时，系统效率随着等待耐心的增加而增加，原因在于更高的等待耐心将促成更多的买方用户与卖方用户匹配成功。从图8(c)可以看出，系统效率随着到达率的增加而增加，这是因为更高的到达率将促成更多的竞价与要价匹配成功。

6) 社会福利

社会福利反映了经济效率。如图 9(a)所示，随着买方用户数或卖方用户数的增加，都会导致社会福利的增加，这是因为更多的用户会增加竞价与要价匹配成功的概率。从图 9(b)可以看出，当买卖双方总数分别为50、100和500时，社会福利随着等待耐心的增加而增加，这是因为更高的等待耐心将促成更多的竞价与要价匹配成功。如图 9(c)所示，社会福利随着到达率的增加而增加，原因在于随着到达率的增加将促成更多的竞价与要价匹配成功。

7) 未完成任务情况下不同方法的性能对比

图6 任务完成率对比

图7 平台效用对比

图8 系统效率对比

图9 社会福利对比

图10 未完成任务情况下不同方法的性能对比

由图10(a)可以看出，不论是通过IMRA机制还是通过UBIM机制激励，用户参与未被完成的感知任务，均能获得较高的任务完成率。图10(b)展示了采用2种不同的机制激励用户参与未被完成的任务下的平台成本，可以看出，对于IMRA机制，平台成本随着竞标用户数的增加而增加，相比之下，在UBIM机制下平台成本较低。

7 结束语

针对移动群智感知网络中用户参与感知活动时因自私性、不确定性而导致用户参与感知活动的积极性不高及用户中断感知活动的问题，本文提出基于拍卖模型的激励机制。首先，从用户的角度出发，以最大化用户效用为目的，提出了一种基于逆向拍卖的激励机制IMRA。在IMRA阶段中，提出多项式时间复杂度的用户选择算法，并采用按时间比例分享规则的报酬支付方法，在保证激励真实性的同时提高了用户效用。其次，针对用户中途退出的问题，提出基于用户交互的激励机制UBIM，通过买方用户和卖方用户之间的双向竞拍，使买方用户可以将未完成的感知任务转售给卖方用户，并提出了一种基于节点度和边权值的用户匹配算法，提高感知任务完成率和社会福利。最后，理论及实验分析表明，本文的激励机制有效地提高了用户平均效用和任务覆盖率，并且可以使平台在一定的成本预算约束的情况下获得较高的任务完成率。在未来的工作中，将会进一步探索各种不确定因素与用户退出的随机性之间的确定性关系模型，如探索电量不足导致用户退出的随机性将会服从何种分布，用户主观感知决策的变化导致退出的随机性将会服从何种分布等。另外，在仿真的过程中仅考虑了感知任务的成本、用户的报价为均匀分布情况下与其他方案的对比，后续将会引入正态分布和指数分布下的对比分析。