1. 引言
计算机网络上的各种业务,均呈现了统计自相似性(长相关性) [1] ,即网络流量的时间序列存在着突发性。各种具有突发特性的业务源呈现出的自相似特性显著影响到网络的传输性能和流量控制策略,例如对时延、丢包率、吞吐量等网络性能指标的 [2] 直接影响,正使得网络的设计、控制、分析和管理变得复杂。因而,只有对自相似流量下的网络性能进行正确地分析与评价,才能降低流量自相似性所带来的不利影响,使网络性能得到优化。网络流量统计分析、网络流量建模及网络性能评价作为计算机网络基础理论研究的前沿热点问题之一,也是现代通信网络规划与设计的基础。各种研究表明网络流量具有自相似的性质 [3] [4] ,在这种自相似的流量背景下传统的排队论分析结论就不再适用,而自相似现象普遍存在于局域网、广域网以及VBR (Variable Bit Rate)流量中,因而研究自相似长相关特性存在于各种类型的网络流量中,对实际数据通信量而言,自相似性与长相关性是两个等价的概念。而小波正是用于检测分析长相关特性有效的数学工具。
2. 相关内容介绍和原理
2.1. 单路复用网络模型的介绍
单路复用网络模型目前已经被广泛的应用于网络性能的分析,因此,研究人员用这种模型来分析缓冲区溢出概率,延时变化等等。这种模型或者用以排队理论对网络性能参数作解析分析推导或者用以模拟实验的手段研究性能变化性质,当无法解析性分析推导时后者就是主要的分析手段。
2.2. 长相关性介绍以及原理
2.2.1. 自相似过程的定义
对于一个广义的平稳随机过程
设
具有恒定均值
和有限方差
,其自相关系数是 [5] :
,自相关系数仅与k有关,网络业务实体数目在第k个单位时间内到达的称为
。用
表示一个缓变函数,即
,并且对所有的X > 0成立
,称满足上述条件的过程称为渐进自相似过程 [6] 。
定义1:广义平稳的离散随机过程
称为强渐进二阶自相似过程,并且具有自相似参数
,0 <
< 1,假如对于任意
自相关函数都满足
,C为常量。自相似函数H又称为Hurst参数,它是描述自相似性的唯一参数。短相关的时候0 < H < 1,不存在相关性的时候H = 1/2,长相关的时候1/2 < H < 1。由于网络流量是长相关的,因此范围是(1/2, 1),H越大,自相似程度越高。定义2:广义平稳的离散随机过程
称为强渐进二阶自相似过程,并且具有自相似参数
,0 <
< 1,
,分数自回归整合滑动平均过程是一个二阶自相似过程,0 < d < 1/2,自相似参数H = d + 1/2。在数学中,平稳随机过程(Stationary random process)或者严平稳随机过程(Strictly-sense stationary random process),又称狭义平稳过程,是在固定时间和位置的概率分布与所有时间和位置的概率分布相同的随机过程:即随机过程的统计特性不随时间的推移而变化。这样,数学期望和方差这些参数也不随时间和位置变化。平稳信号自相关函数的定义已给出,现讨论它的一些主要性质。性质1这一性质说明,自相关函数在处取得最大值,并且是非负的。代表了信号中直流分量的平均功率,代表了中交流分量的平均功率,因此,代表了的总的平均功率。性质2若是实信号,则,即为实偶函数;若复信号,则,即是埃尔密特对称的。性质3若是实信号,则,该结果说明,即使,是实的,也不是偶对称的。性质4性质5由这个自相关函数责成的矩阵是非负的。对自相关函数和互相关函数作Z变换,我们称为随机信号的自功率谱。功率谱反映了信号的功率在频域随频率
的分布,因此,又称功率谱密度。所以,表示信号在
至之间的平均功率。我们知道,随机信号在时问上是无限的,在样本上也是无穷多,因此随机信号的能量是无限的,它应是功率信号。功率信号不满足傅里叶变换的绝对可积条件,因此其傅里叶变换是不存在的。如确定性的正弦、余弦信号,其傅里叶变换也是不存在的,只是在引入
函数后才求得其傅里叶变换。因此,对随机信号的频域分析,不再简单的是频谱,而是功率谱。假定的功率是有限的,那么其功率谱密度的反变换必然存在。功率谱有如下的重要性质:性质1不论是实数的还是复数的,都是
的实函数,因此功率谱失去了相位信息。性质2对所有的
都是非负的。性质3若是实的,由于是偶对称的,那么仍是
的偶函数;性质4功率谱曲线在内的面积等于信号的均方值。在工程实际中所遇到的功率谱可分为三种:一种是平的谱,即白噪声谱;第二种是“线谱”,即由一个或多个正弦信号所组成的信号的功率谱;第三种介于二者之间,是既有峰点又有谷点的谱,这种谱称为“ARMA谱”。一个平稳的随机序列,如果其功率谱在的范围内始终为一常数,如,我们称该序列为白噪声序列,其自相关函数是在处的
函数。由自相关函数的定义,它说明白噪声序列在任意两个不同的时刻是不相关的,即,对所有的。若是高斯型的,那么它在任意两个不同的时刻又是相互独立的。这说明,白噪声序列是最随机的,也即由无法预测。“白噪声”的名称来源于牛顿,他指出,白光包含了所有频率的光波。以上讨论说明,白噪声是一种理想化的噪声模型,实际上并不存在。由于它是信号处理中最具有代表性的噪声信号,因此人们提出了很多近似产生白噪声的方法。本书所附光盘中的子程序random可用来产生不同均值和不同方差的“伪白噪”序列,它们既可服从均匀分布,也可服从高斯分布。
2.2.2. 自相似过程的性质
长相关性存在于各种类型的网络流量之中。如果
,则称平稳过程X具有长相关性,其中
是过程X的自相关函数,Mandelbrot将长相关性称为约瑟夫效应。由自相似过程的定义可知,由于0 <
< 1,
,因此自相似过程是长相关的。传统模型的自相关函数随着间隔呈指数方式衰减,即
,故
<
,因此是短相关的。实际上,严格的说,长相关性和自相似性不是完全等价的,前者指平稳序列的自相关函数的衰减特性,而后者主要是指离散或者是连续过程的有限分布的标度不变性。随机过程在这个研究中有重要应用。
2.2.3. 自相似过程的原理
设x为以宽平稳随机过程,其自相关函数
如果满足:
,式中常数
> 0,0.5 < H < 1,我们就称x具有长相关性。H称为Hurst参数,是衡量长相关性的度量。H = 0.5时表示短相关。上式中,自相关函数的频域形式:
,
,式中常数
> 0,这是长相关性在频域上的体现。自相似的物件是近乎或确实和它的一部分相似。若说一个曲线自我相似,即每部分的曲线有一小块和它相似。自我相似是分形的重要特质。在绘制同一幅图形的过程中,如果下一步产生的图形总是与上一步的图形相似,那么这种现象叫做自相似。这就是一幅自相似的图形。只要有足够细的笔,这种自相似的过程可以任意继续表现下去。
2.2.4. 小波分析的介绍和原理
小波分析系数
表示在时刻2k,频率
时的能量,
是母小波的中心频率,那么得到谱估计:
。
是尺度j时的小波系数个数,由此可见
是在频率v附近能量度量的估计。
,我们通过分析
随着尺度j的线性变换检测长相关性,并求得Hurst参数估计值。小波分析算法在工业的各个领域都有重要应用。小波分析(英语:wavelet analysis)或小波变换(英语:wavelet transform)是指用有限长或快速衰减的、称为“母小波” (mother wavelet)的振荡波形来表示信号。该波形被缩放和平移以匹配输入的信号。“小波”(英语:wavelet)一词由Morlet和Grossman在1980年代早期提出。他们用的是法语词ondelette,意思就是“小波”。后来在英语里,“onde”被改为“wave”而成了wavelet。小波变换分成两个大类:离散小波变换(DWT)和连续小波变换(CWT)。两者的主要区别在于,连续变换在所有可能的缩放和平移上操作,而离散变换采用所有缩放和平移值的特定子集。小波理论和几个其他课题相关。所有小波变换可以视为时域频域表示的形式,所以和调和分析相关。所有实际有用的“离散小波变换”使用包含有限冲激响应滤波器的滤波器段(filter band)。构成CWT的小波受海森堡的测不准原理制约,或者说,离散小波基可以在测不准原理的其他形式的情境中考虑。虽然跟短时距傅里叶变换一样能同时分析时间和频率,但是小波变换在高频的时间分辨率较好,在低频时则是频率分辨率较好,刚好符合我们对信号分析在高低频的分辨率要求,因为在低频时,例如频率从1 Hz变到2 Hz,频率差了一倍,所以频率的变化相较时间的变化是比较明显且重要的,然而在高频时,例如频率从1000 Hz变到1001 Hz,频率相较时间的变化不大,所以对时间分辨率的要求较高。通常来讲,DWT用于信号编码而CWT用于信号分析。所以,DWT通常用于工程和计算机科学,而CWT经常用于科学研究。小波变换现在被大量不同的应用领域采纳,有时甚至会取代了傅里叶变换的位置,在许多领域都有这样的转变。例如很多物理学的领域亦经历了这个转变,包括分子动力学,从头计算(ab initio calculations),天文物理学,密度矩阵局部化,地球物理学,光学,湍流,和量子力学。其他经历了这种变化的学科有图像处理,血压,心率和心电图分析,DNA分析,蛋白质分析,气象学,通用信号处理,语言识别,计算机图形学,和多分形分析。影像压缩,小波变换最常见的应用是用于影像压缩。和其他变换一样,小波变换可以用于原始影像(例如图像),然后将变换后的数据编码,得到有效的压缩。影像压缩通常可分为三大步骤,分别是变换(Transform)、量化(Quantization)和编码(Coding)。其中变换这个步骤是将原始资料变换成另一种表示法,可经由逆变换得到原始信号。变换的目的在于除去信号采样的相关性,也就是去除采样间的累赘。在对影像资料变换时,通常是将影像先分割成不重叠小区块,再对小区块进行单位变换,而单位变换是一种可逆的变换,其演算的核心为正交的基底函数。信号可以分为规则性信号与非规则性信号两类,所谓规则性信号即是信号中所有组成物是同时发生的;而非规则性信号其组成物并非是同时发生。对于规则的信号,理想且有效的变换方式是傅里叶变换。而适用于非规则性信号的工具就是小波变换。较为知名的影像压缩档案格式JPEG 2000就是采用小波的图像标准,算法细节请参考小波压缩。边缘侦测,小波变换亦常应用于影像的边缘侦测(edge detection),传统的影像边缘侦测采用二维差分运算子以侦测影像边缘,乃假设影像边缘上和边缘旁之影像灰阶值必然不同,当取微分时,在边缘上会呈现非常大梯度值,借由调整影像灰阶值的临界值参数可强化边缘,但二维小波变换则是一种效果较佳的影像边缘侦测方法,当取小波变换时,在影像边缘上亦会呈现非常大的梯度值。在电脑视觉或影像处理上经常使用动态轮廓或蛇行模式来侦测物体的边界或边缘。在物体纹路及表面瑕疵检测上亦有其应用,由于小波变换有局部性处理的能力,对于小区域之瑕疵能有效凸显,其频率特性使得在处理瑕疵上不易受环境影响。相对于频率域之变换方法,小波变换处理速度快,因不须事先经过训练与繁复的数学计算,使得小波变换在速度处理上获得不错效果,其具有多解析(Multi-resolution)与多尺度(Multi-scale)能力,使得在处理纹路瑕疵上不会产生方块效应。小波变换不会变动影像物体的相对位置,且保留纹路与瑕疵的空间关系与影像大小。音乐信号分析,小波变换亦可用在音乐信号上,像是乐器自动辨识的应用,第一种为先使用一维小波变换将声音信号分解为不同频率范围的各个频带,接着再对各个频带中撷取能量平均值以及能量标准差视为一维小波变换之特征向量。而第二种方法为先将声音信号转成频谱图并视为一张二维影像,对此频谱图做二维小波变换分解出各个频带,再对频带中撷取能量平均值和能量标准差作为二维小波的特征向量。最后,利用相邻近似法使用欧基里德距离来计算测试资料的特征向量和每一乐器的特征向量之距离,并取最小距离为辨识结果的乐器类别。而小波变换也常用在音乐信号的压缩,由于人耳对声音各频带是有其感知力的,故有些频带人无法听见,有些频带人耳特别灵敏。利用离散小波变换来将音乐信号做高低频切割多次,就可以将原信号分成许多子频带(sub-band),但传统离散小波变换计算架构,将波型分成高频与低频后,下一次的切割只对低频做切割,故没办法完全分割出与人耳感知频带相符合的子频带。于是更精细的计算架构被提出,称为离散小波包变换(discrete wavelet packet transform),原理就是音乐信号被分成高频信号后,会再做分割。一段音乐信号就可以被分割成更贴近人耳25个频带的信号,这样的分割法更优于一般傅里叶分析所使用的滤波器,从这些子频带中,找出能够被屏蔽的信号,滤除之后,就可以将原本音乐信号档案大小压缩了。在辨识音乐信号的乐谱上也有其应用,音乐信号由一个个音符组成,而每个音符以特定的节奏出现,通常是成群的谐音出现,若要分辨出一段信号最主要的频率为何,必须滤除其泛音才能判断,而由离散小波变换的多重分辨率分割就可以将泛音区隔在不同的子频带中,而且信号中的噪声也可以依同样方法被滤除。由于是要侦测transient 现象,基于要侦测什么样的信号就使用跟它很像的信号当作基底拆解它这个原则,故在选择小波基底时,就要选择较有突然剧烈变化的母小波,如此一来小波变换后的小波系数,能量就会聚集在原信号有剧烈变化之处了,由此方法可有效辨识音乐信号的音高(也就是频率)。遥测影像分析,连续小波变换常应用于遥测影像分析上,如海底地形之解析,利用具有分析非均匀信号的高维连续小波变换理论作为遥测影像的分析工具,从中求取影像波浪谱,再从影像波浪谱中反算出观测区域的水深值。传统的研究多将海洋遥测影像假设为均匀(homogeneous)的海面影像,并采用被分析影像为均匀性前提所发展出的方法进行谱变换,其分析所得之影像谱实际上为整个遥测影像波数谱的平均值。然而自然界的信号常存在有非均匀的特性,近岸海域的波浪亦不例外。为能从分析非均匀影像信号中分析得到合理且准确的水深信息,可引入非均匀信号分析理论——小波变换。如高维小波变换理论可应用在分析海洋遥测影像之研究,藉以从中计算出底床地形的信息,透过小波变换的非定常信号的解析能力,可将整张遥测影像分解为不同的子影像,每一块子影像区域的波场理论上具有一定程度之均匀性,再进而从各子影像中求解水深值,藉以描绘出观测海域的水深信息。生医信号分析,离散小波变换亦常应用在生医领域中,因为其具有较低的复杂度与较佳的时域–频域分析之特性,而被选择作为分析生医信号的方法。心电图(Electrocardiography)与脑波图(Electroencephalography)是两项常见的生医应用。在心电图方面,为了诊断心脏相关疾病,可使用离散小波变换去除原始信号中冗余的特征,并由重建的信号中侦测R-R区间。一般而言,病患之心电图时常需要全天候的观察与分析,因此资料量相当庞大,此时便需要很大的储存空间来储存这些资料,因此有必要将心电图之资料加以压缩,才可有效减少所需之储存设备成本。信号的压缩可分为无失真(lossless)压缩和失真(lossy)压缩两种,若是依传统医学观念,或许应该使用无失真压缩,才可避免因信息不完整而造成误诊等医疗疏失,但由于传送信息之网络带宽有限且资料庞大,因此使用失真(lossy)压缩以达到更大的压缩效率已成必然,在增大压缩效率的同时,亦可保证其重建信号之可靠度,以避免不必要的医疗疏失便是一重要课题,小波变换便可达到此项目标。而小波变换亦有去除不必要噪声之功用,以正确判读心电图,此方法称为小波系数临界法(wavelet coefficients thresholding),信号经小波变换后,噪声会成为较小的信号(low scale),因此将较小scale的信号去除,即可去除噪声,一般的做法为设立一临界值,将低于此临界值的信号舍弃,高于临界值的信号保留。而选择临界值的方式有两种,一种为硬式临界值(hard threshold),其临界值为一常数,不随输入信号改变而改变,此法优点为设计简单,但得到的结果并不理想,若改由不同输入信号形成不同临界值,则称为软式临界值,将经小波变换后每一频带之变异数(variance)开根号后形成标准差,而后以标准差当作参数作为临界值,此法产生之临界值会因输入信号长度的不同而改变。另一个小波变换在生医领域的应用则是应用在脑电图上,早期脑电图信号分析技术,普遍以傅里叶变换为主,近年来,小波变换技术逐渐被采用,其特性在对于未知信号的频率分布,在时间轴上可以得到很好的分辨率,适合应用于脑波的不稳定信号分析处理。再配合类神经网络非线性分辨能力,可有效分辨
波、
波。亦有一个应用是在于脑电图中正常的背景信号与不正常的尖峰信号之区分,患有癫痫的病人其不正常的尖峰信号其形状会类似一个凸起的尖峰,故此信号壳称为尖峰信号(spike),利用多重解析变换的小波变换(multi-resolution wavelet transform)可用来分析这类型态类似、但大小区间变异很大的癫痫信号。
3. 影响网络丢包的长相关性的因素
NS2产生自相似业务的原理:NS2提供了四种类型的流量产生器:1) EXPOO。2) POO:Pareto分布。(ON/OFF)产生通信量。3) CBR,以确定的速率产生流量。4) TrafficTrace,根据跟踪文件产生流量。POO_Traffic是包含在OTCL类Application/Traffic/Pareto中的一个流量发生器。它按照Pareto on/off分布产生流量。在on期,以固定的速率发送包,而在off期,没有包的发送。N个叠加的多个重尾的On/OFF源叠加可产生自相似业务流。N越大,自相似现象越发的明显。各个文件的位置:1) Application类:C++中Application类(~/ns/apps/app.h)。2) trafficGennerator抽象基类(~ns/tools/trafgeh.h)。3) POO_traffic (~ns/tools/pareto.cc)。4) CBR_Traffic (~ns/tools/cbr_traffic.cc) [7] 。本文据此配置POO_traffic的参数如下:
set traffic [new Application/Traffic/Pareto]
$traffic set packetSize_500
$traffic set burst_time_500 ms
$traffic set idle_time_500 ms
$traffic set rate_100k
$traffic set shape_1.5
其中burst_time_为平均On (突发)时间,idle_time_为平均Off (空闲)时间,rate_为突发期间包的发送速率,packetSize_为包大小,shape_为Pareto分布的形状参数 [8] 。N个Pareto On/Off [9] 流量生成器可以合成具有自相似特性的业务流。拓扑结构包括N个发送节点
,一个路由节点R和一个接收节点S。N + 1条链路:
到R的N条链路,带宽为1 MB,延迟10 ms、丢弃超出容量的包;R到S带宽为10 MB、延迟10 ms、丢弃超出容量的包。形状参数为1.4时候的流量速率 [10] 图如图1所示。流量速率值即纵轴是单位时间内的丢包数目,从图中可以看到流量的突发性变化。流量速率图如图1所示。
3.1. 叠加源个数N对长相关性的影响
根据上述实验的原理我们可以假设,N越大,自相似性越大,Hurst参数越大,丢包率越大。为此,做了四组实验,在形状参数为1.5的情况下,N的值分别为5,7,9,11,并且做出在N值为这些值的情况下的流量速率图,横轴代表时间,纵轴代表单位时间1 s内的包到达数。N值为5的情况下的速率图,N值为7的情况下的速率图,N值为8的情况下的速率图,N值为9的情况下的速率图(图2~5)。
通过观察上面四个图的线型和线型与横轴围成的面积我们可以发现,随着N值的增大,单位时间的包到达数也就是流量速率逐渐增大,自相似性越来越明显,Hurst参数越大,丢包率逐渐增大。由此我们可以得出结论,N越大,自相似性越大,Hurst参数越大,丢包率越大。
3.2. 形状参数对长相关性的影响
根据上述关系式我们可以假设,形状参数越小,Hurst越大,则自相似性越发的明显,丢包率越大。为此,做了四组实验,形状参数分别为1,1.4,1.5,2,在形状参数取得这些值的情况下的速率图。速率图的横轴表示时间,纵轴表示单位时间1 s内的包到达数。其中,
。通过观察上面的四个图的线型和线型与横轴围成的面积我们可以发现,随着形状参数的逐渐增大,自相似性逐渐减小,H减小,丢包率越小。由此可以得出结论,形状参数越大,长相关性越弱,H越小,丢包率越小。
3.3. Hurst参数对长相关性的影响
根据
这个关系式我们可以得出结论Hurst参数越大,自相似性越大,丢包率越大。具体的实验同3.1部分 [11] 。
3.4. 输出链路速度对长相关性影响
N = 5,形状参数为1.5。link = 10 MB。我们假设链路速度越大,长相关性减小,Hurst参数减小,丢包率越小。链路速度分别设置为5 MB,10 MB,15 MB,20 MB,在这些设置情况下的流量速率图如图 [12] 。通过观察上面的四个图的线型和线型与横轴围成的面积我们可以发现,随着输出链路速度的逐渐增大,自相似性逐渐减小,H减小,丢包率越小。由此可以得出结论,输出链路速度越大,长相关性越弱,H越小,丢包率越小。
4. 总结和展望
本文在cygwin + NS2的网络环境下首先介绍了单路复用网络模型和长相关性的原理。然后讨论了叠加源个数N,形状参数,Hurst参数,输出链路速度对长相关性的影响,以及进一步对丢包率的影响。最后得出结论,叠加源个数N越大,形状参数越小,Hurst参数越大,输出链路速度越小,长相关性越大,丢包率越大。下一步工作是将得出的输出链路速度对丢包率有影响这一结论应用到建立考虑网络丢包的视频质量无参评估模型中,输出链路速度由于对丢包率的影响将会作为建立模型的一个参数。
致谢
感谢善于学术的侯义斌导师的帮助。