贾超鹏　孙学梅　万文杰

(天津工业大学计算机科学与软件学院　天津 300387)

0　引　言

随着科技的发展，各种移动设备大量涌现在人们日常生活中，如智能手机、平板电脑和可穿戴设备等。移动设备的普及催生了移动群智感知网络，移动群智感知[1]是一种新的感知模式，它结合了众包思想和移动感知，具有人的感知判断能力和移动设备本身的感知能力进行数据收集和信息服务。相较于传统的传感器网络，移动群智感知具有部署灵活、感知数据多元异构、覆盖范围广泛均匀等诸多优点，这使其成为学术界的研究热点[2]。

然而，有些障碍严重阻碍了人们参与到移动群智感知实验任务中，例如额外的流量、电量使用，这会给用户带来更多的消耗，这也是移动群智感知用户普遍关心的问题。所以，设计合理的数据上传机制和激励机制减少在整个任务中的流量补偿预算是十分重要的问题。

目前国内外关于移动群智感知网络激励机制已开展一部分研究工作，如文献[4]提出一种 基于质量驱动的竞价激励机制QDA，该机制的特点是以用户的感知数据质量表示用户效用值，而不是传统的使用感知时间来表示。文献[5] 针对协作性任务，以斯塔克伯格博弈为基础设计激励框架来模拟服务器和用户之间的相互作用，参考用户的成本和任务类型等信息提出四种激励机制来激励用户。文献[6]提出一种综合的群智感知激励框架，包括逆向拍卖、游戏化验证和信誉度更新三部分内容，最大化用户、服务器和任务发布者三者之间的利益。文献[7]提出一种名为TGBA的团购型激励机制，拍卖过程分为服务器与任务发布者竞拍和服务器与感知用户竞拍两个竞拍阶段。文献[8]提出两种节约型在线激励机制Frugal-OMZ和Frugal-OMG，并证明其分别在零“到达-离开”间隔模型和一般间隔模型下满足计算效率、个人理性和真实性。此类激励机制的研究中多数存在一个问题，那就是群智感知系统在向用户提供激励报酬或者用户向系统提出报酬估价时多是在任务完成之前就预估出一个价格，此价格很可能会导致一些任务的特殊分配，感知任务执行过程中数据的收集可能会造成影响。

以上是对群智感知网络激励机制的部分研究，近期研究者针对原来激励机制的不足提出一些新的方法。文献[9]基于机会传输提出一种名为ecoSense的群智感知数据上传机制，该机制直接从用户的流量分析其在感知任务中的消耗而不是使用预估值，并通过节省流量花费的方式激励用户。其核心是将用户分为流量可无限使用的包月用户和现用现付用户两种类型，在数据上传阶段通过包月用户代传数据来节省任务的整体花费。

但是文献[9]存在一些不足之处。首先，它所针对的参与用户是国外用户，其资费方案是不限流量和现用现付两种类型，这显然不符合国内情况；其次，它补偿用户流量的定价方案是依据运营商的流量定价方案，若感知任务数据量较大时将产生巨额的费用，原方案在预算控制方面略显不足；最后，它在激励用户方面仅单一地采用现金返还的方式补偿用户参与任务所花费的流量，对用户参与协作传输并无激励措施，这无疑会影响感知数据的收集。

通过对ecoSense机制的研究和分析，我们设计了C-ecoSense(ecoSense for Chinese User)数据上传机制。首先，调查国内运营商的流量资费情况，根据用户历史感知数据量和移动轨迹预测下个阶段的数据量和移动轨迹，将用户分为两种类型：包月型用户和非包月型用户，初步拟定两种类型用户的流量补偿方案；然后，为用户设计POR(User’s Points by Opportunistic Relays)积分激励机制和PIM(Positivity Incentive Mechanism)积极性激励机制；最后，使用机会传输[3]策略进行数据上传。

综上所述，本文做出以下贡献：

(1) 首次依据国内移动互联网运营商的流量资费，融合机会传输和移动群智感知网络数据上传机制减少任务发布者总的流量补偿预算；

(2) 在已有研究的基础上设计并实现了C-ecoSense数据收集机制，并设计了POR和PIM激励机制激励用户完成感知任务；

(3) 通过仿真实验证明，C-ecoSense机制与传统数据收集和ecoSense机制相比在预算控制和用户激励方面都具有较好的表现。

1　C-ecoSense机制

主要介绍C-ecoSense机制的总体内容，主要包括：问题描述和C-ecoSense机制详述。

1.1　问题描述

在现实场景中有很多群智感知任务并不是实时任务，这类任务不需要立即上传感知数据可在数据收集和上传之间存在一定的延迟，我们称此类任务为延迟上传的群智感知任务，C-ecoSense机制可应用在此类任务中。延迟上传的详细定义如下。

定义1延迟上传如图1所示，在[T0,T1]时刻用户手机采集产生数据，该数据可以在[T1,T1+Td]内上传，在延迟上传周期内结束。如果仍有一些参与者的数据依旧没有成功上传至服务器，那这些用户将被强制使用移动网络上传数据，从而确保所有的感知数据能够在允许的延迟时间Td内传至服务器。

图1　感知周期和延迟上传周期

在群智感知实验中C-ecoSense机制的主要目的是减少任务发布者对用户的流量补偿费用，从而激励用户。在正式将问题公式化之前我们先介绍几个关键概念。

定义2用户类型通过分析国内运营商的流量资费情况以及用户的移动轨迹预测，我们将用户划分包月和非包月两种类型。包月用户指拥有流量套餐且在其移动模式中经常可以使用免费Wi-Fi的用户；非包月用户指使用流量较少且移动模式中可使用的免费网关较少的用户。所有用户为U，P(U) → [UD,UN],这里UD∪UN=U且UD∩UN=Φ。

定义3免费事件免费事件指的是非包月用户遇到的免费Wi-Fi或者包月用户,这类事件可以帮助非包月用户上传感知数据并且不用花费自己的流量。

定义4上传决策当一个拥有感知数据Ri(时间t产生)的非包月用户Ni，在时间按t*(t*∈[t,t+Td])遇到免费事件e，C-ecoSense将做一个决策决定数据Ri是否需要上传或者向中继者传输。我们用D(Ni,Ri,t*,e,t,Td)→{true,false}表示这个决策功能。

所谓上传策略就是上传决策的具体实施措施，我们使用了两种上传策略：OneRelay[9]策略和UpEnd[9]策略。OneRelay策略是指NDW用户在延迟上传阶段将自己的数据通过Wi-Fi自行上传或者传递给DW用户让其代为上传，注意在使用OneRelay传输策略时数据在用户之间最多中转一次。UpEnd策略是指在延迟上传阶段结束时，为了确保用户所收集到的数据完成上传，客户端会强制将用户已整理的数据全部上传。这部分不是该课题的研究重点，因此我们引用了文献[9]的上传策略。

在延迟上传的群智感知任务中，对所有感知用户U针对不同的流量资费方案和移动轨迹，我们需要一个为用户设计的上传决策Q，和一个用户划分函数P，这样就可以最小化群智感知组织者在一个任务周期中对参与用户的流量补偿。

本文主要用到的符号如表1所示。

表1　主要符号

1.2　C-ecoSense机制详述

现在我们简单描述C-ecoSense在群智感知任务中的工作流程。如图2所示，在任务开始时，用户划分部分将用户划分为包月和非包月两种类型，随后进行数据收集，在数据延迟上传阶段用户使用机会传输策略进行数据上传，在任务执行过程中使用对应的激励机制对用户进行激励。C-ecoSense机制的核心思想是通过包月用户帮助非包月用户上传数据来达到节省费用的目的，因为随着感知数据量的增大，补偿非包月用户的费用会相对较多，而包月用户的协作会使这部分费用大大减少。

图2　C-ecoSense机制框架

C-ecoSense机制主要包括三个关键模块：用户划分、激励机制和上传决策。其中上传决策部分已在问题描述部分介绍，这里不再赘述。以下内容将详细介绍用户划分和激励机制设计两部分。

1.2.1用户划分

用户划分是C-ecoSense机制可以完整运行的关键，影响用户类型的因素有流量补偿定价方案、感知数据量和移动轨迹。其中未来的感知数据量和移动轨迹我们无法直接获得，我们使用这两类数据的预测值作为划分因子。具体用户划分流程如图3所示。

图3　用户划分框架

C-ecoSense机制针对的群智感知任务按收集的数据量分为定量感知任务和非定量感知任务，我们用公式(1)表示用户i在周期j中的感知数据量。其中k表示访问位置的次数，li,j表示访问位置所获取的单位数据量。

(1)

本文中的移动轨迹指的是用户在其移动模式中所触发免费时间的概率。移动轨迹的预测并不是我们研究的重点，我们使用的预测方法是一种基于泊松分布的预测方法，这种方法已经研究得十分成熟，如文献[10]，完全可以满足我们的实验需求。移动轨迹预测如下式所示：

(2)

对于不同类型的用户我们采用了不同的的流量补偿方案，对于包月用户来说，我们补偿其部分包月套餐费用，若其流量超标且是用于感知任务，则我们额外补偿其超出流量的费用。补偿方案如公式所示：

RefundD=M×PriceD+d×PriceN

(3)

对于非包月用户我们补偿其用于感知任务的全部流量费用，补偿方案如下式所示：

RefundN=Dl,j×(1-Pi,j)×PriceN

(4)

综上所述，我们得出总流量预算模型如下式所示：

(5)

为了最小化总费用Refund，若单纯的改变模型中的数据很可能产生一系列NP困难问题，我们采用一种遗传算法进行寻优，得出最优划分。算法1是基于遗传算法的划分算法的伪代码。

算法1基于遗传算法的用户划分算法

输入：Refund：适应度函数；U：所有用户

输出：UD和UN用户划分、Refund

1： B ← bivector(U)

2： N(population)← B

3： i ← 0

4： while i < itermaxdo

5： K ← keepbest(N)

6： C ← crossover(N)

7： M ← mutation(N)

8： N ← {K,C,M}

9： i ← i + 1

10：end while

11：UD，UN←U

其中，第1行是将U设置为双矢量，0表示非包月用户，1表示包月用户；第2行将B种群的每个用户随机初始化为0或1；第5行获得使Refund适应度函数获得最小值的划分；第6～8行进行交叉变异，一直循环至迭代次数结束，本文中实验均迭代50次。

1.2.2激励机制设计

(1) POR激励机制C-ecoSense机制之所以能够节省总流量支出，是因为其利用机会传输技术使用户之间进行协作传输。对于包月用户来说，帮助其他用户上传数据就意味着需要消耗自己的终端资源。虽然原方案中会对用户进行流量补偿，但是这部分补偿是固定的，不论用户是否协作都能收到补偿，显而易见，更多的用户会选择拒绝代传他人数据，这无疑将会影响整个机制的运行，进而影响感知数据的收集。

我们提出的POR激励机制是一种基于积分的激励机制，用户每代传一份数据，会相应的增加积分，用户可以使用积分兑换各种奖励(如流量、现金或其他虚拟货币等)。具体的积分模型如下式所示：

Ii,j=Ui,j-1

(6)

式中：Ii,j表示用户i在第j周期中的积分，Ui,j表示用户i在第j周期中总共上传的感知数据份数，减1表示去除自己的那一份数据，即帮助其他人上传的数据份数。

(2) PIM激励机制在延迟上传的群智感知任务中，用户可以利用延迟时间进行数据传输，选择自己上传或者由他人代传，这也是C-ecoSense机制可以完美运行的一个先决条件，若所有用户都将数据。但是这也存在一些缺点，若所有用户都在延迟阶段的最后时刻上传数据，将会为服务器带来巨大的压力，而服务器的升级和维护会耗费大量的资金。

为了激励用户尽量提前数据的上传时间，我们提出了PIM上传积极性激励机制。上传积极性的衡量公式如下：

(7)

式中：PTi,j表示用户i在第j个周期中的上传积极性，ti,j表示用户i在第j个周期的延迟上传周期上传数据的具体时间。显然ti,j越小则对应的积极性越高，积极性越高则获得的奖励越多，我们用式(8)表示该奖励。

PIMi,j=N×PTi,j

(8)

2　实验及结果评估

2.1　仿真实验环境

仿真实验的语言环境是Windows XP系统下的Python2.7，包括DEAP[11](Distributed Evolutionary Algorithms in Python)、SciPy科学计算、Matplotlib科学绘图等组件。本文中的仿真实验使用的数据集是SWIM[12]模拟数据集，从中提取48个具有完整数据的对象作为仿真对象对C-ecoSense机制进行有效评估。

我们调查了国内移动、联通和电信三大运营商的使用最多的流量定价方案，如表2所示。由于这些资费标准对实验数据的整体走势并不会造成很大的影响，我们的仿真实验仅采中国联通的资费标准来制定用户的流量补偿方案。由于套餐内容涉及通话、短信和来电显示等内容，所以我们实验中一律将对包月用户的补偿基本标准定为30元/月。

表2　三大运营商流量资费表

2.2　结果评估

我们采用了以下两种方案与C-ecoSense机制进行对比：

1) 直接分配方案这种方案是仅根据用户的感知数据量直接的将他们定义为包月类型或者非包月类型。与该方案对比证明我们机制的节省效率。

2) 理想化C-ecoSense方案该方案不做移动性预测，直接将他们上个月的移动踪迹用在算法中得到用户划分。该方案是为了证明我们所选用预测方法具有足够好的性能。

2.2.1定量的感知数据

在该实验中我们假定感知任务每个周期所需要收集的数据量是一定的，我们实验了数据量在1 000 KB～6 000 KB/周期下的流量费用，实验结果如图4所示。与直接分配方案比较C-ecoSense可以节约40%～56%的费用，我们发现在数据量为3 500 KB/周期时候，相比直接分配方案节约效果最为显著，因为此时直接分配方案将所有的用户都定义为了包月类型。与理想化C-ecoSense方案比较仅多了1%～9%费用，说明生态感知已经具有了很好的性能。可能可以设计出更好的移动性预测方法，但是这往往需要更高的精度，这对于节省预算方面并不见得很有意义。

图4　定量感知数据补偿预算

2.2.2非定量感知数据

非定量感知任务实验中需考虑式(1)中c=0和c≠0两种情况。当c=0时，假设用户仅上传自己访问位置的感知数据；当c≠0时，假设用户除了上传感知数据外还上传一些其他数据，如活动日志数据，实验中这部分数据定为500 KB。实验结果如图5和图6所示，描述了分别把每个基站的数据量单位元k的范围设在100～1 200 KB/基站的流量补偿预算。与上述定量感知数据和直接使用网络方案对比的一样，这种情况下生态感知可以节省42%～56%(c=0)、40%～56%(c=500 KB)的资费。与理想化C-ecoSense对比，C-ecoSense的耗费多了1%～11%(c=0)、1%～12%(c=500 KB)，这为引入更精确的移动预测的方法提出了改进的范围。

图5　非定量感知数据补偿(c=0)

图6　非定量感知数据补偿(c=500)

2.2.3PIM激励机制

实验结果如图7所示，描述了48个用户在PIM激励机制下的上传积极性，从实验结果可知，在该激励机制下，用户普遍会选择在延迟上传时间的38%～60%之间上传数据，显然没有用户在延迟时间结束时上传数据，38%～60%这段缓冲区可大大减少服务器数据收集的压力。

图7　PIM激励机制

2.2.4POR激励机制

在该实验中，我们测试了当每周期感知数据数据量为4 000 KB和6 000 KB时用户在一个月内所获得POR奖励的情况。实验结果如图8所示，双柱状图中可以看到当数据量为4 000 KB/周期时，48名用户中仅有1号、21号22号三名用户获得奖励，数据量为6 000 KB/周期时，1～5号、21～25号、41号和43～45号共14名用户获得奖励，显然在数据量较小时用户多会自行上传。这说明在数据量较小时补偿流量并不会消耗过多，用户多选择自己上传，随着数据量的增加用户获得的POR奖励增多，证明用户之间的机会传输增多，C-ecoSense机制的作用也就越明显。

图8　POR激励机制

3　结　语

本文针对ecoSense群智感知数据上传机制的不足提出了基于C-ecoSense数据上传机制。该机制将用户划分类型并通过POR和PIM激励模型用户进行激励，且在预算控制和用户激励方面都有很好的表现。

在未来的工作中，我们将进一步完善该机制，用户的电量消耗也是影响用于参与群智感知任务的一个重要因素，对于节省电量仍是群智感知研究的重点，我们将在此方面继续研究。

[1] 张宁,苏华,孙学梅,等.基于信誉模型的群智感知网络用户参与激励机制[J].计算机应用与软件,2017,34(5):119-122,152.

[2] 吴垚,曾菊儒,彭辉,等.群智感知激励机制研究综述[J].软件学报,2016,27(8):2025-2047.

[3] 熊永平,刘伟,刘卓华.机会群智感知网络关键技术[J].中兴通讯技术,2015,21(6):19-22.

[4] 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.

[5] Luo S,Sun Y,Ji Y,et al.Stackelberg Game Based Incentive Mechanisms for Multiple Collaborative Tasks in Mobile Crowdsourcing[J].Mobile Networks and Applications,2016,21(3):506-522.

[6] Dai W,Wang Y,Jin Q,et al.An Integrated Incentive Framework for Mobile Crowdsourced Sensing[J].Tsinghua Science and Technology,2016,21(2):146-156.

[7] Huang L,Zhu Y,Yu J,et al.Group Buying Based Incentive Mechanism for Mobile Crowd Sensing[C]//IEEE International Conference on Sensing,Communication,and NETWORKING.IEEE,2016:1-9.

[8] Zhao D,Ma H,Liu L.Frugal Online Incentive Mechanisms for Mobile Crowd Sensing[J].IEEE Transactions on Vehicular Technology,2017,66(4):3319-3330.

[9] Wang L,Zhang D,Xiong H,et al.ecoSense:Minimize Participants’ Total 3G Data Cost in Mobile Crowdsensing Using Opportunistic Relays[J].IEEE Transactions on Systems Man & Cybernetics Systems,2017,47(6):965-978.

[10] Chon Y,Shin H,Talipov E,et al.Evaluating mobility models for temporal prediction with high-granularity mobility data[C]//Pervasive Computing and Communications (PerCom),2012 IEEE International Conference on.IEEE,2012:206-212.

[11] De Rainville F M,Fortin F A,Gardner M A,et al.DEAP:A Python framework for Evolutionary Algorithms[C]//GECCO’12 Proceedings of the 14th annual conference companion on Genetic and evolutionary computation.Philadelphia,Pennsylvania,USA—July 07-11,2012:85-92.

[12] Kosta S,Mei A,Stefa J.Large-Scale Synthetic Social Mobile Networks with SWIM[J].IEEE Transactions on Mobile Computing,2014,13(1):116-129.