环境信息监控中基于压缩感知的移动众包成本控制研究

高丽萍，姚 祯，高 丽，陈庆奎

1(上海理工大学 光电信息与计算机工程学院，上海 200093) 2(上海理工大学 图书馆， 上海 200093)

1 引 言

移动众包作为一种新兴的范式，可以高效、全面地收集各类数据.移动众包中包含三类对象，分别是任务发布者，众包平台以及任务参与者.当发布者发布一个任务后，众包平台将根据任务信息挑选合适的参与者授予任务.参与者在接受任务后，通过持有的智能设备对指定地点进行采样，将采样数据上传至众包平台换取报酬.学者们从任务分配[1]、隐私保护[2]、激励机制[3]等方面对众包模式展开了研究，大大扩展了其应用场景.在移动众包出现之前，传统的环境信息监控问题主要使用固定的传感器进行数据的收集，这带来了两大问题.一方面，部分区域不适合安装传感器，影响了数据信息的完整度.另一方面，大量传感器的安装与维护费用会造成高昂的成本问题.而在移动众包模式下，众包平台通过雇佣参与者进行采样，能够轻易获得完整的数据信息，同时，相比于传感器的安装与维护成本，众包任务的雇佣成本更低.基于以上两点，学者们开发了一系列应用[4-6]，通过手机的定位信息与上传的数据实现了噪声污染监控与环境信息收集.

在移动众包中，需要收集足够数量的数据才能保证任务完成的质量，因此，充足的参与者数量与足够的任务预算是有必要的.参与者往往被任务报酬所激励，在报酬丰富的条件下，参与者数量可以得到保证，实际的应用中也证明了这点.例如，基于众包的交通监控应用WAZE迄今为止已拥有超过5000万用户.因此，任务预算是现阶段限制移动众包性能表现的主要瓶颈.针对移动众包中的成本控制问题，学者们从设备电量损耗[7]，数据传输成本[8]，采样点数量[9]等各个角度展开了研究.其中，基于压缩感知技术减少采样点数量的方法在成本控制方面效果最为显著.应用压缩感知的前提是需要处理的数据在某个低维空间必须是稀疏的.现有研究表明[10-15]，诸如温度、湿度、空气质量等环境信息是适用于压缩感知的.因此，本文将基于压缩感知技术，通过采样少量的采样点恢复出全部的数据，从而达到成本控制的目的.在压缩感知的数据恢复中，当任务质量要求相同时，采样点中蕴含的信息越多，所需要的采样点数量越少.因此，一个高性能的采样点选择算法更有利于成本控制.另外，尽管大多数参与者都会认真完成任务，但是难免存在一些投机取巧的参与者，通过伪造数据换取任务报酬.伪造的数据不仅掩盖了其对应采样区域的真实数据，更会破坏数据之间的内在联系，对恢复算法造成干扰，进而影响数据恢复的质量.为了保证任务完成质量，众包平台将不得不对更多采样点进行采样，造成成本的浪费.

本文针对环境信息监控中的移动众包成本问题，使用压缩感知技术进行成本控制，主要贡献如下：

·本文提出了一种基于经验的采样点选择算法EBCS(Experience Based Cell Selection)，挑选蕴含信息更多的采样点进行采样，在保证任务质量的前提下减少了所需采样点的数量.

·本文提出了一种改进的k-means算法IK(Improved K-means)，有效地检测出参与者提交的伪造数据，避免了伪造数据影响数据恢复的质量从而不得不对更多采样点进行采样的情况.

·本文基于模拟的温度数据进行了实验，证明了EBCS算法能够有效减少所需采样点的数量，IK算法能够以极高的准确率识别出伪造数据，本文的方法在成本控制方面有良好的表现.

2 相关工作

在移动众包领域，针对成本控制问题，目前主流的研究方向有3种[16].

1)控制参与者设备的能源损耗.文献[17]使用背驮式方法传输数据，数据只有在参与者使用其它应用时才会进行传输，从而节约了总体的能源损耗.文献[18]在背驮式方法传输数据的基础上，使用改进的模拟退火算法进行预测，挑选出使用应用频率高的参与者分配任务，在节省能源的同时保证数据的及时性.然而对于环境信息监控问题，这种方法能够节约的成本太少，又存在数据不能及时上传至众包平台的风险，因此并不适用.

2)控制数据传输的成本.文献[19]提出了一种ecoSense机制，将参与者分为两类，一类参与者的流量套餐为无限流量套餐，另一类为按使用量付费.按使用量付费的参与者将自身采集到的数据通过蓝牙传输给无限流量套餐的参与者，再由其传输给众包平台，从而达到节省流量资费的目的.类似的，文献[20]允许参与者持有数据，直到其找到WiFi节点，再通过WiFi将数据上传至众包平台.这种方式适用于数据量大且对实时性要求不高的场景，同样不适用于环境信息监控问题.

3)控制采样点数量.2015年，L.Xu等人[21]首次将压缩感知与众包结合，通过少量的采样点恢复出了所需的数据，其在成本控制方面具有良好的表现的同时能够保证数据的及时性，因此，本文采用压缩感知技术进行成本控制研究.

在压缩感知中，一个高性能的采样点算法能够有效减少雇佣成本.文献[13，21]采用随机算法进行采样点选择，这种方法虽然有效且易于实现，但容易选择包含信息较少的采样点进行采样，导致数据恢复所需的采样点数量大大增加.文献[22]使用LDPC(Low Density Parity Check)矩阵进行采样，相比于随机采样在采样点数量相同时具有更好的表现.但这种方法需要在采样前确定相应的采样点数量，以此生成对应的LDPC矩阵.相比较于逐个采样直到满足任务质量要求，使用LDPC矩阵进行采样，为了保证任务质量，往往会在任务开始时便采样大量的采样点，造成过采样的情况，不利于成本控制.文献[23]提出一种QBC(Query-By-Committee)算法，通过多种恢复算法对现有采样数据进行数据恢复，选择未采样点中对应恢复结果数据向量中方差最大的点进行采样.这种方法选择的是目前掌握信息最少的采样点，而非包含信息最多的采样点.这种方法选择的采样点，往往不能对其周围采样点的数据推测提供帮助，因此不能最大化减少数据恢复所需要的采样点数量.另外，现有的工作中都没有考虑参与者提交伪造数据以换取报酬的情况.伪造的数据会破坏数据内部联系，形成噪声，造成恢复质量下降.为了抵消噪声的影响，众包平台将不得不采样更多区域来获得更多信息，造成了成本的浪费.综合考虑现有研究的优缺点，针对环境信息监控问题，本文在使用压缩感知的基础上，提出了EBCS算法和IK算法来减少所需采样点的数量并检测伪造数据，以达到最大化的成本控制.

3 问题阐述

本节首先介绍了定义与假设，随后对本文要解决的问题进行了详细的描述.

3.1 定义

定义1.全采样矩阵.对于一个包含m个采样点和n个周期的移动众包任务，我们用Fm×n来表示它的全采样矩阵.F[i，j]表示第j个周期第i个单元格的真实数据.

定义2.采样矩阵.我们用Bm×n表示采样矩阵，其矩阵元素为0或1.若B[i，j]为1，则需要对第j个周期第i个单元格进行采样，若B[i，j]为0，则第j个周期第i个单元格的采样数据由数据恢复获得.

定义3.采样结果矩阵.我们用采样结果矩阵Sm×n存储采样获得的数据，它的计算公式如公式(1)所示：

S=F∘ B

(1)

其中，∘ 表示两个矩阵元素的乘积.

定义4.(e，p)质量.对于一个持续n个周期的移动众包任务，当它满足下式时则符合(e，p)质量要求.

|{ek≤e，1≤k≤n} |≥n×p

(2)

其中，e表示每个周期中数据恢复允许的最大误差，p为一个概率，表示至少有n×p个周期数据恢复的误差要小于等于e.由于在实际应用中，无法预知真实环境的数据，因而无法保证所有周期的数据恢复误差都必定小于e，本文将p设定为一个较大的值(比如0.9或0.95)，并使用基于留一法的贝叶斯推断来保证实际应用下的恢复质量.

3.2 假设

为了问题的简化，本文做了如下假设.

假设1.目标采样区域有足够多的参与者能够参与众包任务.因此，在每个采样周期，任意目标单元格，存在足够多的候选参与者能够接受众包任务对该单元格进行采样.

假设1在现实生活中是能够实现的.比如，基于众包的交通监控应用WAZE迄今为止已拥有超过5000万用户，即使对于城市规模的环境信息监控问题，5000万的潜在参与者也是绰绰有余的.假设1的存在使得我们无需考虑参与者的运动轨迹，起到了简化问题的作用.

假设2.每个接受任务的参与者都能够在规定时间内提交任务.

在现实生活中，出于任务报酬与自身信誉等因素，绝大多数参与者都能够按时完成任务.因此，假设2是合理的.

由于假设1与假设2都能够在现实生活中实现，因此本文提出的成本控制方法能够应用于真实环境下.

3.3 问题描述

min rp=r×m×n

(3)

(4)

解决该问题的关键是尽可能低的采样率，本文通过EBCS算法筛选出蕴含信息更多的采样点，通过IK算法检测伪造数据，从而保证众包任务的低采样率.

4 移动众包任务流程

本文中一个众包任务的流程如图1所示.

图1 众包任务的工作流程Fig.1 Workflow of a crowdsourcing task

如图1所示，众包平台在接收到一个任务后，首先根据采样矩阵生成模块产生一个目标采样点并雇佣参与者进行采样.参与者上传任务数据后，众包平台通过伪造数据检测模块筛选出真实有效的数据，并基于这些数据进行数据恢复.众包平台将不断重复上述过程直到任务质量满足(e，p)质量要求.在实际应用中，为了避免任务超时，可以根据历史经验一次性采样足够数量的点，再逐个采样直到达到任务质量要求.接下来详细介绍采样矩阵生成模块、伪造数据检测模块以及数据恢复模块.

4.1 采样矩阵生成模块

采样矩阵生成模块的作用是确定需要采样的区域.单个采样点蕴含的信息越多，那么为了满足任务质量要求而需要的总体采样点数目则越少，因此，一个高性能的采样点选择算法是有必要的.随机采样算法是学者们普遍使用的采样点选择算法，它简单有效，但不能识别出采样点蕴含信息的多少.本文提出一种基于经验的采样点选择算法EBCS，通过历史任务采样情况筛选出蕴含信息更多的采样点，并在此范围内使用随机采样算法进行采样，具体过程如算法1所示.

算法1. EBCS Algorithm

输入：history sampling points Dhand parameter α

输出：sampling points dp

1.initialize experience pool Deas Ø，its max size as eps，score of each point as 0 and sampling range sr as α+eln(1-α)-|Dh|/eps

2.if|Dh|>eps

3. put latest eps history data in De

4.else：

5. De=Dh

6.end if

7.for(int i=0；i

8. for(int j=i+1；j

9. A=De[i]，B=De[j]，C=A∩B

10. A=A-C，B=B-C

11. increase the score of points by one in the smaller set of A and B

12. end for

13.end for

14.select points with top sr score as d and initialize dpas Ø

15.randomly select a point sp from d via-greedy algorithm and push sp into dpuntil satisfy the(e，p)-quality

16.update Dh

17.return dp

如算法1所示，本文将一个周期中满足任务质量要求所需的采样点序列作为一次经验，存入经验池中.当历史经验较多时，选取最新的经验用来训练.初始化所有采样点的得分为0，从经验池中两两配对选择一组经验，去除两者中重复的采样点，若其中一个采样点序列中剩下的点较少，说明其单个采样点蕴含的信息更多，将对应采样点的分数加一.最后，挑选得分最高的sr个采样点生成集合d，以的概率从d中随机选择下一个采样点，以1-的概率从d以外的点中随机选择下一个采样点，不断重复直到满足(e，p)质量要求.概率使得算法能够避免局部最优解并且及时对外界信息的变化作出反应.sr的更新公式为α+eln(1-α)-Dh.size/eps，随着历史经验增多，sr将逐渐收敛于α.文献[24]基于Seneor-Scope数据集进行了实验，在满足质量要求的前提下，遍历了各种采样点可能的组合，发现只有30%的采样点被选择的次数超过了10次，即目标区域大部分信息都包含在30%的采样点中.因此，本文在实验中将α设为30%.

4.2 伪造数据检测模块

在众包任务中，一些投机取巧的参与者会伪造任务数据以骗取报酬.伪造的数据会破坏数据内部的联系，造成恢复质量的下降.为了达成任务质量要求，众包平台将不得不采样更多的点以获得足够的信息，造成了成本的浪费.k-means聚类算法通过将样本集合划分为多个簇，能有效地筛选出伪造数据.给定样本集D={x1，x2，…，xm}，簇划分C={C1，C2，…，Cm}，聚类的目标为最小化平方误差E，如公式(5)所示[25]：

(5)

聚类数k与初始聚类中心的选择是影响k-means算法表现的主要因素.本文基于检测伪造数据的应用场景，提出一种改进的k-means算法IK，如算法2所示.

算法2. IK Algorithm

输入：sampling data set D，max difference diff of sampling data in last cycle

输出：fake data set Df

1.initialize Dpas D，Dras Ø，Dtas Ø，low as min data of D，high as max data of D and mid as median of D

2.while true：

3. cluster Dpvia k-means with cluster center low，mid，get the cluster set Cland define the bigger sub set as Cnl

4. if max difference of Cnl>diff

5. push Cnlinto Dt

6. else

7. push Cnlinto Dr

8. end if

9. cluster Dpvia k-means with cluster center mid，high and repeat the operations

10. cluster Dpvia k-means with cluster center low，mid，high and repeat the operations

11. if |Dr|=0

12. Dp=Ø

13. push the points in the biggest sub set of Dtinto Dp

14. Dt=Ø

15. else

16 select the biggest sub set of Dras Dn

17. return D-Dn

18. end if

19.end while

在检测伪造数据的应用场景下，数据集可能的聚类结果有3种.第1种情况，所有的伪造数据都小于真实数据，那么聚类数为2，初始聚类中心为数据集中的最小值和中位数.第2种情况，所有的伪造数据都大于真实数据，那么初始聚类数为2，聚类中心为数据集的最大值和中位数.第3种情况，伪造数据部分小于真实数据，部分大于真实数据，那么聚类数为3，初始聚类中心为数据集的最小值，中位数及最大值.IK算法针对这3种情况分别通过k-means进行聚类，选择其中较大的子集，若其数据的最大差值大于上一周期采样数据的最大差值，则存入Dt，否则存入Dr.若Dr不为空，选择其中最大的子集作为最终的真实数据集合，否则选择Dt中的最大子集继续迭代聚类.若当前周期为第一个周期，可根据历史任务的采样数据决定合适的最大差值diff.

4.3 数据恢复模块

(6)

(7)

(8)

(9)

在实际问题中，F通常是接近低秩而非完全低秩，且采样数据通常会包含噪声，因此难以找到完全满足等式(9)的L和R，为此我们使用拉格朗日算子来放松约束条件：

(10)

其中，λ是秩最小化和精度之间的平衡参数.

5 实 验

5.1 数据集

本文使用Sensor-Scope数据集[28]中EPFL校园的温度数据作为实验数据.该数据集包含97个传感器连续7天的数据，每个周期为1小时，本文选取其中40个周期的温度数据作为实验数据集.

5.2 对比算法

5.2.1 采样点选择算法

Random：每次在未采样的点中随机选择一个点进行采样.

QBC：基于已经采样的数据，通过不同的恢复算法对未采样的采样点数据进行恢复.对于每一个未采样点，基于不同恢复算法得到的数据，计算其方差，选择未采样点中对应方差最大的点作为下一个采样点.

5.2.2 伪造数据检测算法

ND：生产与科学实验中很多随机变量的概率分布都可以近似地用正态分布来描述，因此预设众包任务数据符合正态分布.基于上一周期的采样数据，计算得到均值μ和标准差σ，将数值在(μ-3σ，μ+3σ)范围中的采样数据认定为真实数据.

CS：给定m个采样数据，对于每个数值，基于其他m-1个数据使用压缩感知进行数据恢复，若恢复得到的值与采样得到的值误差较大，则判定为伪造数据.

5.3 实验结果

为了避免偶然性，所有实验数据均是取10次运行结果的平均值.

图2 不同采样点对应的平均误差Fig.2 Mean error corresponding to different sampling points

本文首先对采样矩阵生成模块进行实验，结果如图2所示.在采样点相同时，本文提出的EBCS算法对应的平均误差最小，这是因为EBCS算法从蕴含信息较多的采样点中选取下一个采样点，这些采样点的数据不仅能补全自身对应采样区域信息的缺失，更有助于推测周围未采样区域的数据.随机算法表现最差，这是因为它不能识别采样点包含信息的多少，容易选择所含信息量极少的点进行采样.QBC算法每次选择目前掌握信息最少的采样点，保证了每次采样都能提供一定数量的信息，因此表现优于随机算法.但QBC算法选择的采样点并不一定有利于周围未采样区域数据的推测，因此表现不如EBCS算法.

图3 检测正确的数据数量Fig.3 Number of correct detection

图4 检测错误的数据数量Fig.4 Number of error detection

然后本文对伪造数据检测模块进行了实验，结果如图3和图4所示.图3展示了不同算法在不同采样点下能够正确检测出的伪造数据数量，图4展示了不同算法在不同采样点下误把真实数据判断为伪造数据的数量.本文提出的IK算法能够检测出最多的伪造数据，同时保持非常低的误判率，表现优于其他算法.ND算法虽然误判率更低于IK算法，但其正确检测出的伪造数据较少.这是因为一方面，众包任务数据并不完全符合正态分布，另一方面，ND算法是基于上一周期的采样数据计算均值与标准差的，数据分布较之当前周期可能有所变化.AIBWP算法在检测率与误判率方面都略微逊色与IK算法，这是因为AIBWP算法是根据密度与评价函数来确定初始聚类中心和聚类数的.当真实数据分布不太均匀时，AIBWP算法倾向于把真实数据聚类为多个簇或是把部分真实数据与部分伪造数据聚类为一个簇.对于每一个数据，CS算法基于其它的采样数据进行数据恢复，得到当前数据的理论值，因此能够检测出大多数伪造数据.但伪造数据会对恢复算法造成干扰，因而CS算法有较高的误判率.

6 总结与展望

本文提出一种基于经验的采样点选择算法EBCS，通过历史经验进行训练后能够选取蕴含信息更多的采样点进行采样，相比较于常用的随机采样算法和QBC采样算法，在相同任务质量要求下，所需要的采样点数更少，从而有效减少了众包任务成本.另外，本文基于检测伪造数据的应用场景提出了一种改进的k-means算法IK，能够有效检测出伪造数据的同时保有较低的误判率，避免了伪造数据对数据恢复造成的负面影响.

未来的工作将聚焦于EBCS算法的改进上.首先探索提升EBCS算法的最佳性能，进一步减少所需要的采样点数量.其次将改进EBCS算法的训练过程，减少其达到最佳性能所需要的历史经验数量.