一种基于信息熵的压缩感知流量恢复算法

谢奇爱

(合肥学院计算机科学与技术系，合肥 230601)

在无线局域网络(WALN)中，无线接入点(无线AP)的均衡负载能有效解决数据流量过大、网络负荷过重等问题，其与网络当前的流量出入信息有关。如果流经网络的流量出入信息的粒度越小，那么调整负载均衡的效果就会越准确。因此在无线局域网中，对移动端用户的网络流量的分析与监控最为关键。在以往的流量监测研究中主要是使用一个提前定义的静态的监测频率而不考虑网络的突发情况，难免会出现高采样频率降低网络性能，同时造成带宽、存储空间等资源的浪费从而影响系统性能。如Manvi等人［1］提出了一种流量监测机制，该机制在网络节点通过使用移动代理来缓和其计算代价以采集网络流量信息。导致最终结果是用较高的流量采样频率换取了高的带宽资源浪费，同时，储存大量的流量信息也会占用很大的存储空间。基于以上的问题Adipat等人［2］又提出了一种动态地基于实时的网络带宽消耗和网络拥塞状况调整监测频率的机制。即当流量相对稳定时，网络流量监测频率就减小;当负载比较差的时候，为避免加重网络负载就降低网络监测频率;当流量变化较大时，网络监测频率就增加以达到检测网络的突发变化。该方法同样以消耗较大的存储空间为代价。本次研究以校园无线局域网为采样环境，根据网络流量在时间和空间上存在的行为特性，提出一种基于信息熵的压缩感知流量恢复算法，以更少的采样观测次数达到更好的恢复精度，从而调节网络负载均衡，提高网络性能。

1 相关技术

熵起初是从热物理学领域中引用的一个概念，它表示了信源所包含的信息的多少。随后应用在很多的领域里如数论、控制论、概率论、计算机网络等领域。将信息熵引入网络应用中形成的概念即网络信息熵(用H(s)表示)。用公式(1)定义，统计不同源IP在一时间段内出现次数 mi，以m表示数据包的总数量，则各 IP出现概率为mi/m［3］。

压缩感知即压缩采样是一个能对海量数据进行稀疏性处理的新兴的采样方法。它具有高效采样精确恢复的能力，其核心是将采样和压缩两者相结合，通过开发信息具有的稀疏性，以远小于Nyquist采样率的速率对信息进行压缩，并能在终端很好地恢复出原始信息。

图1是传统信号处理流程图，图2是压缩感知的信号处理流程图。

图1 传统信号处理流程图

众所周知，在压缩感知理论中最关键的研究点主要包括直接影响到信息恢复精度的信号恢复算法的设计以及算法计算过程的复杂度等。目前压缩感知信息恢复算法主要有3种:(1)凸优化算法;(2)贪婪算法;(3)以上2种的混合算法。从恢复算法的精度和计算过程的复杂度这2个指标来看以上3种算法各有优势。由于无线局域网用户的网络流量在时间和空间上具有相关性，以及无线网络流量数据所具有的成簇的稀疏特性，因此可以利用该特性对信号进行重构并获得更好的恢复结果，从而为压缩感知理论提供输入条件。

图2 压缩感知的信号处理流程图

2 算法设计

众所周知，矩阵奇异值分解是一种正向的思维方式:

研究文献［4］中提出一种可逆的奇异值分解方法。即只要式(2)中的X^为原始矩阵X的r秩的近似解，则:

实际中，不直接求原始矩阵的近似解X^，而是求其分解矩阵L和R中的最小秩目标函数等价转化后最小Frobenius范数目标函数:

取权重系数为1，且用X直接代替A(X)，则:

由于无线用户流量具有时间和空间的相关性，加入时间空间相关特征后得到:

式中:μ、β、Υ— 均是权重系数;

E—时间约束矩阵，在其矩阵上每一行的元

素值就是该矩阵的时间约束系数;

S— 空间约束矩阵，在其矩阵上每一行上的元素值都是该矩阵的空间约束系数;

‖SLRT‖F— 同一时隙内不同基站流量数据间的约束关系;

‖LRTET‖F—不同时隙内同一基站流量数据间的约束关系。

从式(7)可以看出‖SLRT‖F和‖LRTET‖F能反映无线用户原始网络流量数据中所具有的时间空间相关性特征。

3 实验结果分析

以校园无线局域网获取100 d的无线用户流量数据集，把原始矩阵变成度量矩阵，再结合算法求出其估计矩阵，并将估计矩阵与其原始矩阵进行对比。分析本算法与最近邻算法，发现本算法对流量恢复重构率高于最近邻算法(见图3)。

图3 不同算法的性能比较图

由图3可以看出，本次研究提出的算法随着测量矩阵完整性的降低，估测误差值稳定且较低，因此能可靠地恢复出无线用户丢失的流量，达到较好的流量恢复效果。

4 结语

在获得校园无线局域网大量真实数据的基础上，根据无线用户流量在时间空间上存在的一种相关性特征，提出一种基于信息熵的压缩感知流量恢复算法。本算法较其他传统算法而言有较高的恢复重构率，能较好地进行无线局域网的负载均衡处理，提高网络的性能。在后续工作中将根据流量变化的趋势特征，进一步研究基于压缩感知的流量预测方法，提高流量预测的精度，实现资源的高效利用和高效节能。

［1］ Manvi S S，Venkataram P.A Method of Network Monitoring by Mobile Agents［C］//Proctor of the International Conference Communication:Control and Signal Processing in the Next Millennium(CCSP-ZOOO)，2000:1-5.

［2］ Adipat B.Zhang DS.A Real-time Adaptive Traffic Monitoring Approach for Multimedia Content Delivery in Wireless Environment［C］//IEEE Systems，Man and Cybernetics Society.2003 IEEE International Conference on Systems，Man and Cybernetics Manchester:［s.n.］，2003:280-285.

［3］严承华，程晋，樊攀星.基于信息熵的网络流量信息结构特征研究［J］.技术研究，2014(3):28-32.

［4］ Roughan M，Zhang Y，Willinger W，et al.Spatio-temporal Compressive Sensing and Internet Traffic Matrices［J］.Networking，IEEE/ACM Transactions on，2012，20(3):662-676.

［5］王晓.压缩感知在无线通信网络数据釆集中的应用研究［D］.杭州:浙江大学信息学院，2011:15-19.