参与式感知(participatory sensing)也称城市感知(urban sensing)，是人们利用集成了特定传感器的智能移动终端对人类社会状态信息(包括环境、交通、社会活动等)进行采集、分类、传输和分析，进而作出智能决策，为人类生活和社会活动提供服务^{[1, 2]}的一项新技术.

参与式感知应用通常需要传输大量的感知数据，因此对数据进行压缩进而缩减数据冗余是参与式感知技术中的关键内容.传统的数据压缩方法有信源编码、分布式压缩感知等，是根据当前信号内容相关性进行数据压缩的方法.分布式信源编码(distributed source coding,DSC)从信息论中的信源编码角度实现低复杂度、分布式的信息压缩^[3].压缩感知(compressed sensing,CS)是由Donoho^[4]提出的数据压缩算法.该算法指出，只要信号可以在某种基下稀疏表示，就可以在不丢失逼近原信号所需信息的情况下，用较少的观测数据对原始信号进行投影，然后通过求解最优化问题重构原始信号.Baron等^{[3, 5]}提出了分布式压缩感知(distributed compressed sensing，DCS)理论，该理论结合多信号的联合稀疏模型(joint sparsely model,JSM)和压缩感知理论提出了一种利用信号间以及信号内相关性来进行信号压缩编码的算法.

目前，国内外学者已经对参与式感知^{[6, 7]}及压缩感知在参与式感知系统中的应用^[2]进行了相关研究.移动设备的续航能力和网络资源受限问题一直是限制参与式感知系统发展的一个瓶颈.参与式感知系统中，节点在感知区域内按照一定规律分布，在节点较多的情况下，节点所传输的数据具有一定的冗余性；如何减少冗余信息的传输，降低系统资源消耗，成为参与式感知系统研究的一个主要问题.

本文主要研究参与式感知系统(participatory sensing system,PSS)中的数据采集算法，并提出一种基于压缩感知的数据采集算法(compressed sensing based data acquisition algorithm,CSDA).CSDA的主要创新是，在参与式感知节点较多的情况下，通过挖掘并应用节点间的社会关系对节点感知数据的数值进行估计，从而进一步减少压缩感知需要传输数据的数量，节约网络能量消耗.

CSDA主要分为数据发送和数据处理两部分：在数据发送端，簇头节点利用CSDA算法通过对原始数据的压缩感知随机采样，得到压缩后的采样数据并将其传输到数据处理端；数据处理端在采样数据的基础上利用节间点的社会关系对其他未传输数据进行估计，然后利用压缩感知的数据重构算法对处理后的数据进行重构，完成对原始数据的恢复.

PSS中的节点具有移动性，这些节点在同一空间中的不同时刻呈现不同的分布，而同一节点在不同时刻呈现出按一定规律移动的社会性.

在PSS中数据传输过程需要分簇路由协议等数据传输算法的支持.各分布节点将全部数据X传给簇头节点A，簇头节点A再根据压缩感知算法，对数据观测采样后将采样数据Y传输给Sink节点B，Sink节点B对数据进行重构.数据的采集过程需要根据地点进行划分，具体划分方法如定义1所述.

定义1 节点的活动范围可以划分为若干个事件区域(event area,EA)，并将EA划分为N个感知网格(sensing grid,SG).

如图 1所示，每个感知网格相当于一个信号源，SG的集合可表示为

则系统随机采集过程表述如下：

设系统采集数据周期数为D，每个周期内采集T次，t∈{1,2,…,T}表示采集时刻的序数.令 X _d为第d个周期N×T的数据矩阵，矩阵中的元素x_tn^d表示grid_n在周期d中第t时刻的原始数据值.

图 1(Figure 1)

Fig. 1

图1 事件区域与感知网格 Fig. 1 Event area and sensing grid

根据压缩感知算法理论可知，观测矩阵 Φ 一般选取高斯随机矩阵，其中高斯随机矩阵决定了在获得观测向量前，获取全部网络节点的数据.PSS中的节点多为私人设备，为了保证用户设备的电池使用寿命，可能无法将节点完全实时开放，因此本文采用置换矩阵(permutation matrix)作为观测矩阵，该矩阵可以在节点不需要传输数据时不激活该节点，从而节省节点能量.令列向量 x _n^d=[x_1n^d,x_2n^d,…,x_Tn^d]^T为网格grid_n在所有时刻的原始数据向量，Φ _n^d为grid_n的观测矩阵，Ψ为x _n^d的稀疏基并且满足 x _n^d= ΨΘ _n^d, Θ _n^d为 x _n^d 的稀疏向量， 则对于grid_n的观测过程如式(2)所示：

其中 Φ _n^d为T^*×T(T^* ＜T)的置换矩阵，所有SG的观测矩阵组成观测矩阵集合 Φ={Φ _n^d},n∈{1,2,…,N},d∈{1,2,…,D}，每个周期Sink节点为每个SG分配不同的观测矩阵.若令第d个周期的采样数据矩阵为 Y _d，则式(2)中列向量 y _n^d=[y_1n^d,y_2n^d,…,y_T^*n^d]^T表示网格grid_n在T^*个时刻的采样数据向量.

图 2为一个采样过程的示例，由于置换矩阵的特性，数据在传输到Sink节点后的时刻顺序是随机的，但其数据值不变.

图 2(Figure 2)

Fig. 2

图2 压缩感知随机观测过程示例 Fig. 2 Random observation process based on CS

在数据传输过程中，簇头节点通过社会关系减少了需要传输的数据量，并将采样后的数据发送给接收端，从而显著降低了网络负载.同时节点在传输数据时要记录所采集数据的节点信息和数据所属时刻，以便进行数据集的转换以及数据的重构.

CSDA在数据重构过程中利用了节点间的社会关系：在重构之前通过构建社会关系矩阵对感知数据集进行更新，使其数据量达到压缩感知重构的最小数据量要求.

在事件区域(EA)中，PSS中的节点在参与社会活动时所产生的移动轨迹可以反映节点的社会性质，其中移动轨迹相似的节点具有一定的社会关系.同时环境数据(如温度、湿度、PM2.5浓度等)具有空间相关性，在不考虑欺骗节点的情况下，节点在其移动轨迹上所采集的数据反映了节点移动轨迹的特性.节点所采集数据的相关性可以作为社会关系的量化标准.

这些数据间的相关性是节点活动轨迹相似度的直接反映，通过数据挖掘方法^[5]对历史数据分析计算可得到相关性的各项系数，从而利用这种相关性进行有效的数据重构.

不同时刻节点可能存在不同的社会关系，因此，本文将分别维护不同时刻的数据相关性系数(即节点的社会关系系数).某个时刻的数据相关性系数可以根据多个连续周期该时刻的节点采集数据的期望和方差来衡量.

方差越趋于0，节点间的社会关系系数越高，节点的关系越亲密；节点与自身的社会关系系数为0.两个节点的数据趋势如图 3a所示；两节点数据的差的分布如图 3b所示，其中虚线为数据差的期望，方差为0.4，可以认为两节点的社会关系协同性较高.方差过大的节点间社会关系系数较小，其数据相关性可忽略不计.设阈值λ，若社会关系系数大于λ，则令社会关系系数为∞，因此社会关系系数的正常取值范围为0到λ之间.

图 3(Figure 3)

Fig. 3

图3 社会关系协同性 Fig. 3 Social relationship cooperativity (a)—节点Ki,Kj的数据趋势； (b)—节点Ki,Kj数据差的分布.

在CSDA中，可以认为带有数据的SG的数量小于系统中节点的数量.在节点和SG足够多的情况下，节点的移动在各个时刻可以基本覆盖所有的SG，则通过数据估计可以满足压缩感知算法重构信息的最小要求.若在一个SG中出现多个节点，则传输信用度较高的节点的数据.

在周期d中，对于grid_n有T个时刻需要采集数据，传统的采集方法需要全部T个时刻的感知数据来获取感知区域的信息.而压缩感知 (CS)算法可能仅利用最少M(M ＜T)个时刻的数据即可恢复T个时刻的数据.本文提出的基于压缩感知的数据采集算法(CSDA)在收集T^* (T^* ＜M)个数据的情况下，利用节点的社会关系估算M－T^*个未传输数据时刻的节点感知数据，从而达到CS重构所需的最小数据量.未传输的M－T^*个数据利用节点社会关系加权估计得出.

假设在时刻t，与节点k具有社会关系的节点共有S个，则节点k与节点s的权重计算过程如式(3)所示.节点k的数据通过对S个节点数据加权平均获得.

压缩感知数据重构需要求解范数最小化问题^[4]，同时要用估算后的数据集对采样数据集和观测矩阵进行更新，以满足重构的需要.更新过程如下.

对于周期d中grid_n的感知数据 y _n^d=[y_1n^d,y_2n^d,…,y_T^*n^d]^T，若有L个数据可以经过数据估计得出，则更新后的感知数据可表示为$\hat y$ _n^d=[y_1n^d,y_2n^d,…,y_T^*n^d,y_(T^*+1)n^d,…,y_(T^*+L)n^d]^T，其中[y_(T^*+1)n^d,…,y_(T^*+L)n^d]^T为L个估计得出的数据，同时要在观测矩阵 Φ ^d_n的最后一行下面添加L行；若第l行的数据是t时刻经过计算得出的数据，则在 Φ _n^d添加的第l行中，第t列为1，其余元素为0，更新后的观测矩阵表示为 $\hat \Phi$ _n^d.更新过程如图 4所示，图中$\hat d$ 表示估计得出的数据.

图 4(Figure 4)

Fig. 4

图4 采样数据及观测矩阵更新过程 Fig. 4 Refresh process of sensing data and observation matrix

PSS需要Sink节点对每个SG的数据分别进行重构，对于网格grid_n，Sink节点通过1-范数最小化算法对 $\hat y$ _n^d进行精确重构：利用式 $\hat y$_n^d= $\hat \Phi$ _n^d ΨΘ _n^d，得到 $\hat x$ _n^d的稀疏表示 $\hat \Theta$ _n^d，然后根据式 Ψ$\hat \Theta$ _n^d= $\hat x$ _n^d，得到重构数据 $\hat x$_n^d.

为验证CSDA算法的性能，本文利用仿真实验生成移动路径及节点感知数据集，其中感知数据采用自由空间扩散模型(FSD)生成，利用随机漫步模型 (RWM)^[6]生成移动路径.压缩感知算法中，稀疏矩阵可以选择DCT矩阵、FFT矩阵或者小波变换矩阵.本文采用DCT矩阵作为稀疏矩阵，置换矩阵与DCT矩阵的约束等距性^{[4, 5]}为 μ (Φ,Ψ) ≈2.453，根据本文对压缩感知理论的介绍可知，可以对数据较精确地恢复. 本实验设置SG数量N=173，运行的周期数D=31，每个周期采集数据次数T=50，理论最大采集数据量为173×50=8650个.

同时，本实验利用前30次数据为已知数据集(也称训练集)，利用CSDA算法计算第31次的数据，并与模拟得出的第31次数据进行比较，观察算法效果.重构误差可以用两种数据的差的绝对值与模拟数据的比来表示，则误差小于给定重构误差的重构数据可视为其重构成功，重构成功率为重构成功的数据量与总数据量之比.

给定不同的重构误差，分析成功率达到95 % 时两个算法所需要的最少数据量，如图 5所示.

图 5(Figure 5)

Fig. 5

图5 不同重构误差下CSDA与CS算法的比较 Fig. 5 Comparison of CSDA and CS with different recovery errors

图 5表明，在满足重构成功率大于95 % 的情况下，CS算法所需要的数据量大于CSDA.而随着重构误差的扩大，两种算法的数据量差异缩小；重构误差越小，两种算法所需的数据量差异越大.

给定重构误差0.2，并取阈值λ分别为0.6，0.7，0.8，0.9进行仿真实验，结果如图 6所示.

图 6(Figure 6)

Fig. 6

图6 不同社会关系阈值重构成功率 Fig. 6 Success rate with different social relationship thresholds

图 6表明，λ越大，社会关系协同性越复杂，重构成功率达到95 % 以上需要传输数据的节点数越多，说明过于复杂的社会关系会导致节点估计的不准确；而在采集节点较少的情况下，λ越大重构准确率越高.本实验说明CSDA需要合理选择社会关系阈值才能具备良好的效果.

给定重构误差0.2，设置移动模型中的节点数量K分别为128，150，175，200，256，300进行仿真实验.对两种算法的重构成功率达到95 % 时所需要的最小数据量进行比较，结果见图 7，图 8.

图 7(Figure 7)

Fig. 7

图7 不同移动节点数的重构成功率 Fig. 7 Success rate with different number of mobile nodes

图 8(Figure 8)

Fig. 8

图8 达到95 % 重构成功率所需的节点数量 Fig. 8 The number of mobile nodes in 95 % success rate

图 7表明，模型中节点越多，算法效果越好，N=300时重构成功率达到95 % 以上需要的采集数据量为2250.这是因为CSDA在移动节点较多时可以减少传输的数据量；在节点较稀疏时，应用CSDA的效果并不明显.

图 8表明，在节点数小于SG数量时，需要传输全部节点的数据量来获得全部信息；而在节点数大于SG数量的情况下，节点数量越多，获得95 % 以上重构成功率时CSDA需要传输的数据量越少.CS算法所需传输的数据量没有明显变化，说明移动节点的增多使社会关系协同性发挥更大的作用.

本文提出了一种参与式系统中基于压缩感知的数据采集算法(CSDA).该算法将压缩感知算法与节点的社会关系结合起来，利用节点的社会关系，估计未被传输的节点感知数据，并对压缩感知重构算法进行了改进，减少了压缩感知算法在参与式感知系统中采集的数据量，进一步降低了网络的能量消耗.实验验证，相比传统压缩感知方法，CSDA只需传输较少的数据量就能达到理想的数据重构效果.