Missing Data Prediction Based on Kronecker Compressing Sensing in Multivariable Time Series
-
摘要:
针对现有算法在预测多变量时间序列中的缺失数据时不适用或只适用于缺失数据较少的情况，该文提出一种基于克罗内克压缩感知的缺失数据预测算法。首先，利用多变量时间序列的时域平滑特性和序列之间的潜在相关性从时空两个方面设计了稀疏表示基，从而将缺失数据预测问题建模成稀疏向量恢复问题。模型求解部分，根据缺失数据的位置特点设计了适合当前应用场景且与稀疏表示基相关性低的观测矩阵。接着，从稀疏表示向量是否足够稀疏和感知矩阵是否满足有限等距特性两个方面验证了模型的性能。最后，仿真结果表明，所提算法在数据缺失严重的情况下具有良好的性能。
Abstract:In view of the problem that the existing methods are not applicable or are only feasible to the case where only a low ratio of data are missing in multivariable time series, a missing data prediction algorithm is proposed based on Kronecker Compressed Sensing (KCS) theory. Firstly, the sparse representation basis is designed to largely utilize both the temporal smoothness characteristic of time series and potential correlation between multiple time series. In this way, the missing data prediction problem is modeled into the problem of sparse vector recovery. In the solution part of the model, according to the location of missing data, the measurement matrix is designed suitable for the current application scenario and low correlation with the sparse representation basis. Then, the validity of the model is verified from two aspects: Whether the sparse representation vector is sufficiently sparse and the sensing matrix satisfies the restricted isometry property. Simulation results show that the proposed algorithm has good performance in the case where a high ratio of data are missing.
-
1. 引言
随着大数据和5G技术的快速发展，数据安全变得越来越重要，而保障数据安全的最好方式之一是运用密码学对数据进行加密处理。在密码学应用中，无论是密码算法中密钥的生成或是密码协议中特定变量的随机初始化，都需要用到真随机数源。真随机数在统计学上具有随机性，包括时间上的独立性和空间上的均匀性，还具有不可重复性和不可预测性[1-3]。随机数主要应用于密码算法协处理器中的密钥、身份认证和数字签名等，这些都需要真随机数发生器输出的随机系列具有熵源高，功耗低，面积小等特点[4,5]。
目前用于产生随机数的硬件实现方法：(1)离散时间混沌的方法[6,7]；(2)采用相位抖动的方法[8]；(3)采用SRAM的方法[9]；(4)热噪声的方法[10]。
方法(1)所产生的随机数本质上是伪随机数，是通过数学算法实现的，不是真随机数；方法(2)利用相位抖动或振荡器的漂移作为随机源，但靠这一点不能达到足够的随机性能；方法(3)产生的随机数性能与工艺相关性很大，随机性能不能保证；方法(4)利用热噪声是由大量自由电子运动产生的，其统计特性服从高斯分布，产生的随机数性能好。
本文通过对一种低功耗高噪声源真随机数发生器的研究，设计了一种新型的低频时钟电路，可以把电阻热噪声放大100倍以上，从而减少低频时钟电路的带宽和电阻值，使电路的面积和功耗减少，并且使低频时钟的jitter到达58.2 ns。随机数输出满足AIS31真随机数熵源测试要求，且通过了国密2安全测试。
2. 真随机数电路结构
真随机数电路结构如图1所示，电路由低频时钟、高频时钟、触发器、后处理等电路构成[11-13]。在真随机数电路设计过程中，通常要求低频时钟的抖动标准差(jitter)在高振荡器周期的10～20倍之间，以提高真随机数发生器的抗干扰能力以及输出序列的随机性能，低频时钟的jitter值与随机数的随机性能正相关。要使低频时钟的jitter值变大，一般情况下，会增大低频时钟的噪声电阻和噪声带宽，增大噪声电阻会增加电路面积，噪声带宽会增大电路的功耗，故低频时钟的jitter值与电路的面积和功耗相互制约；高频时钟频率输出频率也会影响随机数的随机性能，比如低频时钟的抖动标准差为20 ns，根据通常要求慢振荡器抖动标准差在高振荡器周期的10～20倍之间，以15倍计算，则要求高速时钟输出频率为0.75 GHz，这样会大大增加高频时钟的功耗，为了减少功耗，增大低频时钟的jitter值是必然要求，此时又要增大电路的面积和功耗[14]。设计随机数会在面积和功耗与输出序列的随机性之间进行折中。
3. 新型低频时钟设计
3.1 低频时钟原理和jitter理论分析
低频时钟带有抖动的慢振荡器(clkslow)，电路如图2所示。低频时钟模块包括跨阻放大器、跨导放大器、迟滞比较器、电荷泵、基准电压VREF等电路。
电路使能开启后，偏置电路开始提供偏置电压和电流。当SCLK_OUT为高电平时，电荷泵放电使跨导放大器正端电压下降，跨导放大器输出电流降低，输出的电流通过跨阻放大器转换为电压，当跨阻放大器输出电压到达低阈值-VTL, SCLK_OUT变为低电平；当SCLK_OUT为低电平时，电荷泵冲电使跨导放大器正端电压上升，跨导放大器输出电流增大，输出的电流通过跨阻放大器转换为电压，当跨阻放大器输出电压到达低阈值+VTL，SCLK_OUT变为高电平，这样就可以得到低频时钟输出信号SCLK_OUT。跨阻放大器输出信号是一个在迟滞比较器高低阈值间来回摆动的三角波；电阻R1和R2上的热噪声经过运放放大后叠加在三角波上，得到SCLK_OUT 的时钟沿抖动与热噪声一样，满足正态分布。
跨阻放大器输出的三角波信号如图3所示，其中S是运放输出三角波的斜率，Tcl是慢时钟信号的周期。可以得到
Tcl=t1+t2 (1) 其中t1和t2是随噪声电压而独立随机变化的。同时可得
V(t)=−VTL+S⋅t+Vn(t) (2) S·t是三角波的电压，V(t)是输出电压随时间变化的函数，Vn(t)是放大后的电阻热噪声，可以推出
t1=(VTH+VTL−Vn(t))/S (3) 因为Vn(t)的平均值为0，那么
E{Tcl}=2(VTH+VTL)/S (4) σ{Tcl}=√2σ{Vn}/S (5) 其中E{Tcl}是clkslow的平均周期，σ{Tcl}和σ{Vn}分别是clkslow 的jitter和放大后噪声电压的标准差。由上式可知，σ{Tcl}与σ{Vn}成正比，与S成反比。σ{Vn}和S这两个值都是与电路的某些参数相关的，可以得到
S=±(Ich⋅A1)/C (6) A1=GmI1IR3 (7) Ich是电荷泵充放电电流，A1是电荷泵的输出信号到跨阻放大器的输出信号之间增益，即信号增益。Gm是跨导放大器的跨导，I是跨导放大器的输出电流，I1是流过电阻R3的电流，R3是跨阻放大器的增益，C是电荷泵到地的电容。
σ{Vn}=√(4kT⋅Bw⋅2Rno⋅A22) (8) Rno是噪声电阻，A2是噪声电压增益，Bw是噪声带宽(保守计算时可用主极点频率代替)。
由式(4)、式(6)可得低频时钟周期公式
E{Tcl}=2(VTH+VTL)⋅CIchA1 (9) 从式(9)可知，低频时钟频率与比较器的迟滞范围VTH+VTL、电容C、信号增益A1、电荷泵充放电电流Ich相关，如果低频时钟频率确定，其相应的参数也会确定。
由式(5)、式(6)、式(8)可得低频时钟jitter的σ{Tcl}的具体公式
σ{Tcl}=√2×√4kTBW⋅2Rno⋅A2⋅CIchA1 (10) 3.2 跨阻放大器的设计
从图2可知，噪声电阻在跨阻放大器的两端，噪声是通过跨阻放大器放大的，跨阻放大器的带宽即噪声带宽。从式(10)可知，σ{Tcl}值和噪声电阻Rno、噪声带宽Bw、噪声电压增益A2、迟滞范围VTH+VTL、电容C、信号增益A1、电荷泵充放电电流Ich相关，当低频时钟确定之后，其参数迟滞范围VTH+VTL、电容C、信号增益A1、电荷泵充放电电流Ich会跟着确定，要改变σ{Tcl}值，只有噪声电阻Rno、噪声带宽Bw、噪声电压增益A2可以改变，这3个参数都和跨阻放大器相关，故跨阻放大器的设计是本文的关键。
在图2有跨阻放大器的原理图，电流信号通过电阻R3转换成电压信号，跨阻放大器的闭环增益为R3，噪声电阻为R1, R2，电流信号Iin分成两路，一路通过R3转换成电压信号，一路通过电阻R4。
根据跨阻放大器的原理图求噪声电压增益，噪声电阻R1的噪声电压
vn2=4kT⋅Bw⋅R1 (11) 噪声电流
in2=4kT⋅Bw⋅R1R42 (12) 噪声电流加载在Iin信号上，通过R3进行放大，即输出噪声电压为
vnout2=4kT⋅Bw⋅R1R42R32 (13) 跨阻放大器放大后噪声电压的标准差
σ{Vnout}=√4kT⋅Bw⋅2Rno⋅R3R4 (14) 即噪声电压增益
A2=R3R4 (15) 在这里噪声电压增益可以取100～200倍之间，这样可以在噪声电阻和噪声带宽在比较小的情况下，得到比较大的噪声电压标准差，即可以设计出比较大的低频时钟jitter，增大随机数的性能，并且可以减少功耗和面积。
图4是普通的电压放大器放大电阻噪声运原理图，这种结构信号增益和噪声增益相同，根据式(10)可知，要增大低频时钟jitter，必须增大噪声电阻和噪声带宽，这样会使电路面积和功耗大大增加。
表1为这两种结构下低频时钟jitter为60 ns，时钟频率为2 MHz下，需要的噪声电阻值和功耗。
表 1 两种结构下噪声电阻值和功耗指标 噪声电阻值
(Ω)信号增益A1(倍) 信号增益A2(倍) 噪声带宽(MHz) 功耗(mW) 跨阻放大器结构 64 k 1 100 1 0.081 电压放大器结构 2 M 5 5 80 0.220 通过对两种结构的比较可知，新结构用较小的功耗和面积实现了较大的低频时钟jitter。
3.3 低频时钟仿真
本文在设计真随机数产生器时，使输出吞吐率范围为1.38～3.34 Mbit/s，典型值为2.13 Mbit/s。
表2为低频时钟输出频率对应的σ{Tcl}仿真结果，从表1中可知，σ{Tcl}的典型值为58.2 ns，功耗为74 uA。
表 2 低频时钟频率仿真结果指标 仿真结果 MIN TYP MAX 输出频率(MHz) 1.38 2.13 3.34 Jitter(σ{Tcl})(ns) 77.89 58.2 40 功耗(mW) 0.055 0.081 0.110 图5 为低频时钟频率在2.13 MHz时的jitter的分布情况；图6是对jitter值的分布情况做正态分布处理，从图6中可知低频时钟的jitter值服从正态分布，标准差σ{Tcl}值为58.2 ns。
4. 低功耗高频时钟设计
在上面的章节中可知时钟jitter值比较大，其值为58.2 ns，这样就可以减少高频时钟频率，从而减少功耗。
为了提高真随机数发生器的抗干扰能力以及输出序列的随机性能，快时钟振荡器的周期是慢振荡器jitter的1/20-1/10。取高频时钟的周期是σ{Tcl}的1/15，快时钟振荡器的周期为3.88 ns，时钟频率为257 MHz，这样可以减少高频时钟的功耗。
由于高频时钟的输出中心频率要达到257 MHz，本文中高频时钟的电路采取环路振荡器的结构，晶体管M1控制环路的总电流，用来减少功耗，为保证在PVT变化时输出高频时钟的占空比为50%，环振的输出信号需经过一个高速二分频电路。二分频电路采取高速二分频电路(TSPC)的结构。
高频时钟的仿真结果表3，其时钟频率的中心频率为250 MHz，占空比为50.28%。
表 3 高频时钟频率仿真结果仿真 HOSC频率 MIN TYP MAX 频率(GHz) 0.186 0.25 0.313 功耗(mW) 0.017 0.024 0.035 占空比(%) 50.09 50.28 50.43 5. 整体版图设计和测试
本文设计的真随机数发生器电路采用SMIC 40 nm CMOS工艺，核心电路版图面积小于0.00789 mm2，图7为整体电路的版图设计，分为低频时钟模块、高频时钟模块、基准电压模块。
基于噪声放大的真随机数发生器整体电路测试结果为输出时钟频率为2.4 MHz左右，功耗为0.11 mW，实现了低成本低功耗真随机数的设计，输出的随机系列通过了AIS31测试，并且过了国密2安全检测。
表4是流片测试结果和文献调研中参考的国外相关真随机数发生器的性能参数的对比和具体参考文献，本文的结果在最后一行。表的最后一列是归一化参数S的结果比较，参数S的定义为
表 4 几种不同TRNG 性能比较S=面积×功耗速度×1000 (16) 如表4所示，利用相位抖动原理产生的随机数虽然面积和功耗都较低，但是其随机数的速度较慢，因此其应用场景会受限。在很多实际应用场景中，对随机数的速度都有要求，本文所设计的随机数主要运用在高速安全芯片和主控芯片中，因此随机数的速度至上要达到1 MHz以上，速度太慢，会影响芯片的性能。
6. 结束语
本文设计基于电阻热噪声振荡器的真随机数产生器，电路包括了低频时钟电路、高频时钟电路、D触发器等模块。设计了一种新型的低频时钟电路，可以把电阻热噪声放大100倍以上，从而减少低频时钟电路的带宽和电阻值，使电路的面积和功耗减少。该电路结构可以保证获得较大的周期抖动从而减少电路的面积和功耗。在本设计中使低频时钟的jitter到达58.2 ns，从而减少高频时钟频率，进一步减少功耗，最终使整体电路功耗为0.11 mW，面积为0.00789 mm2。低频时钟输出噪声符合白噪声分布，随机性较好，随机数输出结果满足AIS31随机性测试，并且过了国密2安全检测。
本文设计的随机数在面积和功耗方面有了很大的提升，可以应用在信息安全、计算随机模拟、数字系统内置的检测性能和电子商务系统等领域。
-
表 1 多变量时间序列
数据源 t1 t2 t3 t4 ⋯ tK s1 0.2 ? ? 0.3 1.9 s2 ? 0.4 0.5 ? ? s3 ? 0.7 ? 0.6 ? s4 0.8 ? ? ? 2.1 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ sN ? 0.1 1.2 1.3 ? 
下载: 导出CSV
表 2 稀疏表示基稀疏性能比较
n 100 200 300 500 MOTES_1 0.9897 0.9952 0.9973 0.9992 MOTES_2 0.7428 0.8731 0.9301 0.9786 GSA_1 0.9687 0.9995 0.9998 0.9999 GSA_2 0.5227 0.6841 0.9018 0.9721 SST_1 0.8759 0.9429 0.9722 0.9935 SST_2 0.7390 0.8785 0.9393 0.9849
下载: 导出CSV
表 3 稀疏表示基和观测矩阵非相关性的大小
NK 2000 3000 4000 6000 8000 I(ψR,φKCS1) 1998 2995 3997 5996 7993 I(ψR,φKCS2) 1998 2999 4000 5999 8000 I(ψE,φKCS1) 1999 2996 3997 5999 7995 I(ψE,φKCS2) 1999 2999 3999 6000 8000 I(ψC,φKCS1) 1997 2996 3997 5995 7995 I(ψC,φKCS2) 1998 2999 3998 5999 7998
下载: 导出CSV
表 4 各方法在不同数据缺失率下的性能比较
数据缺失率(%) 20 50 80 90 95 MOTES KCS-GAMP-SBL 0.0266 0.0356 0.0840 0.1101 0.1509 TDMF 0.0287 0.0871 0.1962 0.2604 0.3684 SI 0.0862 0.1604 1.0172 1.7662 3.5204 RNN 0.0392 0.0951 0.8875 0.9174 1.0529 KPPCA 0.0278 0.0608 0.1826 0.2769 0.4516 GSA KCS-GAMP-SBL 0.0357 0.0460 0.1985 0.2769 0.3304 TDMF 0.0548 0.1278 0.3557 0.4764 0.5688 SI 0.0935 0.1455 0.8348 2.9442 4.6315 RNN 0.0526 0.0945 1.0858 1.1639 1.7984 KPPCA 0.0498 0.1012 0.3892 0.4879 0.5872 SST KCS-GAMP-SBL 0.0181 0.0327 0.0956 0.1225 0.1767 TDMF 0.0242 0.0544 0.1788 0.2374 0.2961 SI 0.0485 0.0851 0.7451 1.3802 2.0596 RNN 0.0262 0.0488 0.3417 0.5896 1.0421 KPPCA 0.0226 0.0644 0.1736 0.2705 0.2909
下载: 导出CSV
表 5 不同算法平均运行时间(ART)的比较(s)
SI RNN KPPCA TDMF KCS-GAMP-SBL MOTES 0.7350 3.1832 11.5781 8.4362 3.0802 GSA 1.5361 7.0320 24.8685 20.4093 15.8633 SST 0.7216 2.5216 10.8683 8.9381 2.9032
下载: 导出CSV
表 6 稀疏表示基的选择对算法均方根误差(RMSE)的影响
数据缺失率(%) 20 50 80 90 95 MOTES_1 0.0266 0.0356 0.0930 0.1201 0.1509 MOTES_2 0.0312 0.0422 0.1151 0.1387 0.1954 GSA_1 0.0357 0.0460 0.1985 0.2769 0.3304 GSA_2 0.0412 0.0681 0.2313 0.3343 0.4068 SST_1 0.0181 0.0327 0.0996 0.1275 0.1767 SST_2 0.0199 0.0340 0.1265 0.1534 0.2463
下载: 导出CSV
-
SOWMYA R and SUNEETHA K R. Data mining with big data[C]. International Conference on Intelligent Systems and Control, Coimbatore, India, 2017: 246–250. doi: 10.1109/ISCO.2017.7855990. JAQUES N, TAYLOR S, SANO A, et al. Multimodal autoencoder: A deep learning approach to filling in missing sensor data and enabling better mood prediction[C]. International Conference on Affective Computing & Intelligent Interaction, San Antonio, USA, 2017: 202–208. doi: 10.1109/ACII.2017.8273601. BALOUJI E, SALOR Q, and ERMIS M. Exponential smoothing of multiple reference frame components with GPUs for real-time detection of time-varying harmonics and interharmonics of EAF currents[C]. IEEE Industry Applications Society Meeting, Cincinatti, USA, 2017: 1–8. doi: 10.1109/IAS.2017.8101815. KOZERA R and WILKOLAZKA M. Natural spline interpolation and exponential parameterization for length estimation of curves[C]. International Conference of Numerical Analysis & Applied Mathematics, Rhodes, Greece, 2017: 1–140. LAO Wenchao, WANG Ying, CHEN Peng, et al. Time series forecasting via weighted combination of trend and seasonality respectively with linearly declining increments and multiple sine functions[C]. International Joint Conference on Neural Networks, Beijing, China, 2014: 832–837. doi: 10.1109/IJCNN.2014.6889609. LIPPI M, BERTINI M, and FRASCONI P. Short-term traffic flow forecasting: An experimental comparison of time-series analysis and supervised learning[J]. IEEE Transactions on Intelligent, Transportation, System, 2013, 14(2): 871–882 doi: 10.1109/TITS.2013.2247040 STRAUMAN A S, BIANCHI F M, and MIKALSEN K Ø. Classification of postoperative surgical site infections from blood measurements with missing data using recurrent neural networks[C]. International Conference on Biomedical & Health Informatics, Las Vegas, USA, 2018: 307–310. doi: 10.1109/BHI.2018.8333430. LI Li, LI Yuebiao, and LI Zhiheng. Efficient missing data imputing for traffic flow by considering temporal and spatial dependence[J]. Transportation Research Part C, 2013, 34(9): 108–120. LI Yuebiao, LI Zhiheng, LI Li, et al. Comparison on PPCA, KPPCA and MPPCA based missing data imputing for traffic flow[C]. Proceedings of IEEE Conference on Intelligent Transportation System, Wuhan, China, 2013: 1535–1540. SHI Weiwei, ZHU Yongxin, and HUANG Tian. Effective prediction of missing data on apache spark over multivariable time series[J]. IEEE Transactions on Big Data, 2018 doi: 10.1109/TBDATA.2017.2719703 HADI A and WAHIDAH I. Delay estimation using compressive sensing on WSN IEEE 802.15.4[C]. International Conference on Control, Electronics, Renewable Energy and Communications, Bandung, Indonesia, 2017: 192–197. doi: 10.1109/ICCEREC.2016.7814975. DUARTEAND M F and BARANIUK R G. Kronecker compressive sensing[J]. IEEE Transactions on Image Processing, 2012, 21(2): 494–504 doi: 10.1109/TIP.2011.2165289 ZHOU Haifei, TAN Liangsheng, GE Fei, et al. Traffic matrix estimation: Advanced-Tomogravity method based on a precise gravity model[J]. International Journal of Communication Systems, 2015, 28(10): 1709–1728 doi: 10.1002/dac.2787 CHEN S S, DONOHO D L, and SAUNDERS M A. Atomic decomposition by basis pursuit[J]. SIAM Review, 2001, 43(1): 129–159 doi: 10.1137/S003614450037906X TROPP J A and GILBERT A C. Signal recovery from random measurements via orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2007, 53(12): 4655–4666 doi: 10.1109/TIT.2007.909108 CHARTRAND R and YIN W. Iteratively reweighted algorithms for compressive sensing[C]. IEEE International Conference on Acoustics, Speech and Signal Processing, Las Vegas, NV, USA, 2008: 3869–3872. doi: 10.1109/ICASSP.2008.4518498. AL-SHOUKAIRI M, SCHNITER P, and RAO B D. A GAMP based low complexity sparse Bayesian learning algorithm[J]. IEEE Transactions on Signal Processing, 2018, 66(2): 294–308 doi: 10.1109/TSP.2017.2764855 SAMUEL M. Intel lab data[OL]. http://db.csail.mit.edu, 2016. FONOLLOSA J, SHEIK S, HUERTA R, et al. Reservoir computing compensates slow response of chemo sensor arrays exposed to fast varying gas concentrations in continuous monitoring[J]. Sensors & Actuators B Chemical, 2015, 215: 618–629. Tropical Atmosphere Ocean. NOAA/Pacific Marine Environmental Laboratory[OL]. http://www.pmel.noaa.gov/tao/proj_over/proj_over.html, 2016. WU Xiaopei and LIU Mingyan. In-situ soil moisture sensing: Measurement scheduling and estimation using compressive sensing[C]. ACM/IEEE, International Conference on Information Processing in Sensor Networks, Beijing, China, 2012: 1–11. doi: 10.1109/IPSN.2012.6920949. 期刊类型引用(4)
1. 王鹏，邹彬，刘金枝，周丹阳. 基于Xilinx型FPGA系统单粒子效应评估方法研究. 电子学报. 2022(11): 2716-2721 . 
百度学术2. 蔡阳阳，陶伟，郭刚，魏敬和. CAN控制器单粒子效应测试系统的研制. 中国电子科学研究院学报. 2019(04): 387-392 . 百度学术3. 王鹏，芦浩，刘金枝，薛茜男，金志威. 基于协同进化的航空高度单粒子翻转故障生成方法研究. 现代电子技术. 2019(16): 112-116+121 . 百度学术4. 陈晓娟，陈东阳，吴洁. CMOS反相器低频噪声模型及可靠性表征研究. 电子学报. 2016(11): 2646-2652 . 百度学术其他类型引用(5)
-
下载:
百度学术
计量
- 文章访问数: 2181
- HTML全文浏览量: 894
- PDF下载量: 82
- 被引次数: 9
下载:
