（通信与信息系统专业论文）分形高斯噪声hurst参数估计的实验评价.pdf

华东师范大学硕士毕业论文 分形高斯噪声h u r s t 参数估计的实验评价 论文摘要 网络业务量是网络测量、网络行为学、网络接入控制、网络性能分析等研究 方向的关键部分。随着包括计算机通信网络的高速发展，以及新的应用如视频点 播技术( v i d e oo nd e m a n d ，v o d ) ，网络电话( v o i c eo v e ri n t e m e tp r o t o c o l ，v o i p ) 的出现，网络的突发业务流量急剧增加，网络的业务量特性也呈现出与传统的业 务量模型极为不同的性质，给网络业务量特性的研究和分析带来了新的挑战，同 时也为网络业务量特性的研究开辟了新领域。由于自相似模型能够更加真实地描 述网络传输的特性，因此通过生成具有自相似性的流量的仿真研究是网络业务量 研究的一个重要方面。 本文第一章介绍了课题的背景以及国内外对自相似流量的研究现状；第二章 介绍了传统网络业务模型中较为典型的网络流量模型、自相似、长相关的数学定 义以及常见的自相似业务模型。在第三章中给出了自相似业务量产生算法的分类 以及各类较为突出的几种算法的详细说明及其实现。在第四章，论文对现有的比 较经典的h u r s t 参数估计算法做出了实验评价。首先检验了各种算法识别自相似 序列的能力；其次从准确性、一致性、运算复杂度以及运算时间对这些算法做出 了综合的比较；最后讨论了周期信号、高斯随机信号以及序列的相关结构对各种 算法的影响。第五章在m a t l a b 的g u i d e 平台上开发了f g n 随机数据仿真与 h u r s t 参数估计系统，这样做有利于我们今后更快、更方便的生成f g n 序列以及 估计h u r s t 参数。， 本文的主要贡献有：( 1 ) 在m a t l a b 环境下对几种f g n 序列生成算法进行 了仿真与分析；( 2 ) 对h u r s t 参数估计的八种方法进行了系统的比较，通过对它们 的精确度、计算复杂度以及一致性进行了比较；( 3 ) 对影响h u r s t 参数估计的一些 因素进行了深入的研究，能够更快、更准确的估计h u r s t 参数；( 4 ) 在m a t l a b 的g u i d e 平台上开发了f g n 随机数据生成和h u r s t 参数估计系统。 关键词：长相关；自相似：网络流量；分数阶高斯噪声；h u r s t 参数估计 华东师范大学硕士毕业论文分形高斯噪声h u r s t 参数估计的实验评价 a bs t r a c t a n a l y s i st ot h en e t w o r kt r a f 矗c i ss t i l lt h ek e yf i e l dr e l a t i n gt on e t w o r k m e a s u r e m e n t ，n e t w o r kd y n a m i c s ，c a l la d m i s s i o nc o n t r o l ，a n dn e t w o r kp e r f o r m a n c e a n a l y s i s w i t ht h er a p i dd e v e l o p m e n to fc o m m u n i c a t i o nn e t w o r k s ，t h ep o p u l a r i z a t i o n o fn e t w o r ka n dv a r i o u sn e wa p p l i c a t i o n sm a k en e t w o r k 仃a 佑ci n c r e a s i n gr a p i d l ys u c h a sv i d e eo nd e m a n d ( v o d ) a n dv o i c eo v e ri n t e r a c tp r o t o e o l ( v o l p ) e t c 。t h u s ， n e t w o r kt r a f f i cc o m e st os h o wp r o p e r t i e sd i f f e r i n gf r o mt h et m d i t i o n a ln e t w o r kt r a f f i c ， s u c ha sp o i s s o nm o d e l a c c o r d i n g l y , n e we h a l l e n g eh a sb e e nb r o u g h tt ot h ea n a l y s i s a n ds t u d yo ft h ew i r e da n dw i r e l e s sn e t w o r kt r a 伍c a tt h es a i n et i m e n e wf i e l d sh a v e a l s ob e e ni n t r o d u c e dw h i c hw i l la b s o r bs w a r mo fa t t e n t i o na n di n v e s t i g a t o r s o n eo f t h ee r i e c t i v em e t h o d sf o rs t u d y i n gs e l f - s i m i l a rt r a f f i ci st ob u i l dm o d e l st h a tc o u l d d e s c r i b en e t w o r kc h a r a c t e r sm o r er e a l i t y , a n db ea p p l i e dt os i m u l a t i o nr e s e a r c h i nc h a p t e r1 w ei n t r o d u c er e s e a r c hb a c k g r o u n do fs e l f - s i m i l a rt r a f f i ca n dt h e s t a t u sa th o m ea n da b r o a d i nc h a p t e r2 ，f i r s t ，t h et r a d i t i o l m lt y p i c a lt r a 伍cm o d e l s h a v eb e e ni n t r o d u c e d s e c o n d ，t h em a t h e m a t i c a lm e a n i n go ft h es e l f - s i m i l a r i t ya n d l o n g - r a n g ed e p e n d e n c eh a sb e e np r o v i d e d c h a p t e r3p r e s e n t ss e v e r a lc o m m o nf g n r a n d o md a t ag e n e r a t i o na l g o r i t h m s s e v e r a la l g o r i t h m sf o rt h es i m u l a t i o na n da n a l y s i s i i lm a t l 蛆e n v i r o n m e n ta r ea l s o g i v e n i nc h a p t e r4 w eg i v ee x p e d r n e n t a l e v a l u a t i o n so n8c o m m o n l yu s e dm e t h o d so ft h eh u r s tp a r a m e t e r f i r s t l y , w ee x a m i n e t h ea b i l i t yo ft h e s em e t h o d st od i s t i n g u i s hs e l f - s i m i l a rs e r i e s t h e n ，w ee l a b o r a t et h e e v a l u a t i o nm e t h o d so fa c c u r a c y c o n s i s t e n c ya n dt h eo p e r a t i o ns p e e d f i n a l l y , w e d i s c u s st h ei n f l u e n c ef a c t o r so fe s t i m a t i o n ，s u c ha sp e r i o d i c i t ys i g n a l s ，g a u s s i a n s t o c h a s t i cs i g n a l sa n dr e l a t i o n a ls t r u c t u r e i nc h a p t e r5 t h ef g nr a n d o md a t a g e n e r a t i o na n de s t i m a t i o no ft h eh u r s tp a r a m e t e rs y s t e mi sg e n e r a t e di nt h em a t l a b g u i d ed e v e l o p m e n tp l a t f o r m t i l i sw i l lh e l pu si nt h eg e n e r a t i o ns t o r a g ea n d s t a t i s t i c a la n a l y s i so ff g nr a n d o md a t aa n de s t i m a t i o nh u r s tp a r a m e t e r mm a i nc o n t r i b u t i o n so ft h i sp a p e l a r e ：( 1 ) s e v e r a la l g o r i t h m sf o rt h e s i m u l a t i o na n da n a l y s i si nm a t l a be n v i r o n m e n ta r eg i v e n ；( 2 ) e x p e r i m e n t a l e v a l u a t i o no ft h eh u r s tp a r a m e t e re s t i m a t i o n ；( 3 ) w el u c u b r a t et h ef a c t o r so fi n f l u e n c e i ne s t i m a t i o nh u r s tp a r a m e t e r ；( 4 ) w eh a v eg i v e nas y s t e mo ff g nd a t ag e n e r a t i o n a n dh u r s tp a r a m e t e re s t i m a t i o n k e y w o r d s ：l o n g - r a n g ed e p e n d e n c e ；s e l f - s i m i l a r i t y ；n e t w o r kt r a f f i c ；f r a c t i o n a l g a u s s i a nn o i s e ；h u r s tp a r a m e t e re s t i m a t i o n 1 1 学位论文独创性声明 本人所呈交的学位论文是我在导师的指- 导- f 进行的研究工作及取得的研究成果据我所 知，除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过的研究成果 对本文的研究做出重要贡献的个人和集体，均已在文中作了明确说明并表示谢意 作者签名：象查硷 日期：捌：堑 学位论文授权使用声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆被查阅。有权将学位论文的内容编入有关数据库进 行检索有权将学位论文的标题和摘要汇编出版。保密的学位论文在 解密后适用本规定。 学位论文作者签名：薜妊玲 导师签名： 铆 日期：垄兰丝：笪：兰 华东师范大学硕士毕业论文 第一章绪论 第一章绪论 1 1 课题的背景和意义 目前，i n t e m e t 规模的不断增大，业务种类的不断增加已给人们的生活和工 作带来了巨大的利益和影响。经过2 0 多年的发展，i n t e m e t 已经在全球取得巨大 的成功。然而，当今的计算机网络仍然存在许多技术上的难题与挑战，同时新的 问题也不断出现。网络流的自相似、长相关性己成为国内外研究的热点问题之一。 m a n d e l b r o t 于1 9 7 5 年在研究海岸线等曲线时发现海岸线具有分形结构，并 对分形给出了一个形象的定义 1 】：其组成部分以某种方式与整体相似的形态 ( s h a p e ) 叫做分形。分形描述了自然界中很广泛的一类物质的基本特性：局部 与局部、局部与整体在形态、功能、信息、时间与空间等方面具有某种意义上的 自相似性，这种几何规律性，也称之为标度不变性( s c a l ei n v a r i a n e e ) 。这种分形 结构也被称为是自相似性。这一发现引起了不同领域的研究者的注意，他们发现 在现实世界中，大量的自然和社会现象所产生的时间序列也具有与海岸线相同的 特性自相似性，即这些时间序列是统计自相似、渐进自相似或随机自相似的。 而这种自相似模型与传统的马尔科夫模型( m a r k o v ) 不相符合。从数学角度上 来看，这些时间序列在大的时间滞后上仍具有较强的相关性，即长相关特性 ( l o n g r a n g ed e p e n d e n c e ，l r d ) 或自相似性( s e l f - s i m i l a r i t y ) 。 从1 9 8 9 年到1 9 9 3 年，经过3 年多的时间，w i l s o n 等【2 5 采集b e l lc o r em o r r i s r d 中心的以太网中的业务流的数百万个数据包，通过对这些实际业务数据的分 析，他们发现网络业务所表现的统计自相似性完全不同于传统的业务模型，而是 具有自相似性和长相关性。网络业务中的自相似性主要表现为突发存在于多个时 间尺度上，而且具有相同的统计特征，这与传统理论的方式突发可以经统计 平均而加以平滑是互相矛盾的。 这个发现揭示了网络业务的真实特性，标志着网络业务建模和性能分析研究 进入一个全新阶段。该小组的研究论文“o nt h es e l f - s i m i l a rn a t u r eo fe t h e m e t t r a f f i c 被认为是近十年来网路业务建模和性能分析领域的先驱性研究成果之一 【3 】，先后荣获了由i e e ec o m m u n i c a t i o ns o c i e t y 颁发的1 9 9 4 年w r b e n n e t t 奖 和1 9 9 6 年i e e ew r qb a k e r 奖。 随后几年里各国研究人员对采集自大量不同现在计算机网络环境的业务流 量做出了崭新的研究，这些研究充分的证明了实际网络业务流量的自相似性。其 中主要包括：广域网w a n 业务( p a x s o n 等【6 】) ；信令系统7 号协议( s s 7 ) 业务 ( d u f f y 7 】) ：a t m 网络中传输视频会议业务( h e y m a n 等 8 】) ；w w w 业务 华东师范大学硕士毕业论文 第一章绪论 ( c r o v e l l a 等 9 ) 以及可变比特率v b r 视频服务( b e r n a 等 1 0 】) 。这些结果均 表明实际网络业务流具有长相关性。于是大量的证据显示实际网络中的数据流量 与传统的方式不相符，而是长相关、自相似的，这给原有模型基础上设计的一些 协议、策略带来了新的挑战。长相关性的发现打破了原有网络流量是短相关 ( s h o r t r a n g ed e p e n d e n c e s r d ) 的基础性假设，自然会区别于原来假设的不同特 征( 如流量特征、排队特征) 与操作方法( 缓存大小的选取、拥塞控制策略) 。例如， 传统模型的缓存中队列大小分布是指数分布，而用了长相关的分形模型后，队列 大小分布是双曲线分布。这就打破了使用泊松通信量假设进行直接的排队分析就 足以描述所有网络通信量的幻想，发起了对数据通信性能的重新研究。对网络通 信量自相似性模型及其性能评价的研究是目前计算机网络理论和技术领域面临 的重要挑战之一，也是学术界关注的热点，在重要的国际会议和期刊上不断发表 最新研究结果。由于自相似业务下网络性能与传统模型的结论有较大差异，使得 自相似业务下的网络管理、拥塞控制、业务监管、协议设计、a t m 交换机设计 等问题需要深入进行。 网络流量长相关性和自相似性的研究过程中，分数阶高斯噪声( f r a c t a l g a u s s i a nn o i s e ，f g n ) 是一个重要的模型【3 ，6 ，9 ，1 1 ，1 2 ，1 8 ，2 2 ，3 1 ，3 3 ，3 4 ，它可以通 过少量参数的设置，就可以作为业务量模型合成仿真数据，便于网络性能和控制 的研究。 h u r s t 参数日是描述网络业务长相关的重要参数，若o 5 h 1 ，则序列具 有长相关性，否则，序列不具备l r d 特性。对于f g n 序列的h u r s t 参数估计已 有很多算法，虽然这些算法在理论上都能够准确的估计f g n 序列的日值，但是 在实际应用中，不同算法估计结果差异较大。因此，了解算法的性能以及算法的 影响因素是很重要的。 1 2 国内外的研究现状 尽管f g n 序列比较容易描述，但是由于没有直接或简洁的数学公式来表达， 它们并不容易产生。由于运算量的限制，实际上要产生精确的f g n 轨迹是不可 行的。但在f g n 的仿真算法中，其总的发展趋势是不变的，那就是朝着低复杂 度和高精确度的方向发展。在这个领域，p a x s o n ( 1 9 9 7 年) 【1 1 】、l e d e s m a 和l i u ( 2 0 0 0 年) 【1 2 、l i 和c k ( 2 0 0 3 年) 1 3 1 、p u r c z y n s k i 和w l o d a r s k i ( 2 0 0 6 年) 【1 4 】以及m i n gl i e 3 1 】提出的算法都是有影响的。 对f g n 序列，h 是一个至关重要参数，它既是自相似的度量，也是长相关 的度量。所以，日参数的估计对这类时间序列的应用非常重要。具有代表性的算 法有绝对值法【1 5 】、聚合方差法 1 6 】、r s 法【1 7 ，1 8 】、周期图法 1 9 1 、w h i t t l e 法【2 0 】、 2 华东师范大学硕士毕业论文 第一章绪论 相关函数回归法【2 1 】、小波法 2 2 ，2 3 ，2 4 】以及希尔伯特- 黄变换法 2 5 】。绝对值法、 聚合方差法和r s 法都属于时域估计方法，这几种方法都是直接对数据进行处 理，作出分析曲线，用最t j , - 乘法估计值；周期图法和w h i t t l e 法属于频域估 计方法，它是利用数据的功率谱密度在频域上进行估计；小波法的核心是多分辨 分析，它通过小波基的伸缩变换研究信号各个尺度层次上的影像，它可以实现信 号的时频局部化，同时观察时域和频域的变化。 1 3 本论文的主要成果 本文是作者追踪国际上f g n 序列的产生和h u r s t 参数估计的最新研究成果 并对这些成果进行分析比较并加以改进的若干工作。f g n 模型是一种快速、有 效的自相似网络业务模型，本文对f g n 模型进行了深入的研究，并用计算机进 行了仿真合成以及参数估计。 本文以研究f g n 模型的仿真和h u r s t 参数估计的性能分析为目的，通过系 统地学习具有自相似特性的计算机网络业务建模的基本理论，并在查阅了大量资 料的基础上，建立一个f g n 序列的产生和h u r s t 参数估计系统。 自相似性对网络性能具有一定的影响，因此自相似性的f g n 序列生成以及 自相似参数估计的算法比较在研究过程中就变得十分必要。本文中我们探讨了自 相似f g n 序列的几种生成算法，h u t s t 参数的估计算法，估计算法的比较以及影 响算法准确性的因素等问题。本论文的主要成果有： ( 1 ) 对几种常见的f g n 随机数据生成算法进行了研究，并在m a t l a b 环境下对这些生成算法进行了仿真与分析； ( 2 ) 对几种常见的h u r s t 参数估计算法进行了研究并在m a t l a b 环境下 实现； ( 3 ) 对于h u r s t 参数估计算法的准确性、一致性、计算复杂度等进行了系 统的分析与比较，并且讨论了周期信号、高斯白噪声信号以及序列相 关性对参数估计的影响； ( 4 ) 在m a t l a b 的g u i d e 平台上开发了f g n 随机数据生成以及h u r s t 参数估计系统，这样做有利于今后更快速、方便的生成及分析f g n 序列。 1 4 本文结构 本文第2 章给出了自相似过程的数学描述，介绍了传统网络业务模型的特 点。第3 章介绍了自相似流量生成算法的研究及实现。第4 章介绍了h u r s t 参数 华东师范大学硕士毕业论文 第一章绪论 估计算法并给出了系统的分析和比较，探讨了影响估计结果的因素。第5 章介绍 了m a t l a b 的g u i d e 开发环境以及系统实现。各章之间的联系与本文的结构 如图1 1 所示。 第1 章 绪论 第2 章 自相似过程的 描述 f g n 瓣卜_ | 一 生成算法卜 及实现l 一 第4 章 h u r s t 参数估 计算法分析 图1 1 全文结构框图 第5 章 f g n 生成及分 析系统 4 华东师范大学硕士毕业论文第二章自相似过程的描述 第二章自相似过程的描述 自相似随机过程理论是研究自相似业务的重要理论基础。自从多年前人们提 出了网络流量具有自相似性，在以后的研究中人们又相继对网络流量的长相关性 进行了更加深入的研究。对流量特性的分析是研究新一代网络设计、通信协议和 流量控制的基础，同时也是发现网络异常、故障、安全攻击的重要手段和有效方 法，这些都为网络流量特性的分析与研究提供了新的契机。但是，真实的互联网 运行机制和行为特性错综复杂，同时带宽拥塞、网络不稳定、异常流量、网络攻 击、木马入侵、下载等因素也给网络流量的特性分析带来很大困难。实际上，网 络业务流量数据的特性反映了网络业务间的相互作用和影响，研究人员就可以根 据网络流量的变化规律来发现网络瓶颈，预测流量趋势和优化网络配置，进一步 评价网络性能和提高网络资源的利用率。因此，对网络流量特性的分析是现代网 络研究中要解决的主要问题之一。本章共分为三个部分，第一部分较为详细的介 绍了自相似和长相关过程的定义、特性与相关概念；第二部分介绍了传统的网络 流量模型；第三部分介绍了自相似业务流量模型。 2 1 自相似过程和长相关过程 2 1 1 长相关过程 长相关过程( l r d ) 常常与自相似随机过程或随机分形联系在一起。当自相 关特指一个连续时间过程或者离散时间过程的有限维分布的尺度行为时，l r d 是平稳时间队列自相关函数的长尾行为。h u r s t 参数( 邡是用来度量长相关性的； 日值越大，时间信号越具有长相关特性。 通常我们假设时间序列通过一个比较大的时间尺度后是不相关的。但是，在 实际的时间序列中，我们发现即使通过一个较大的尺度，时间序列仍然具有一定 的相关性，即有长相关性。 自相似过程是统计学家m a n d e l b r o t 和他的同伴于1 9 6 0 年末和1 9 7 0 年初提 出来的。直观地说，自相似过程就是指在不同尺度上的图形都具有统计相似性。 一个随机过程通常可以用表示为时间的函数 x ( f ) ，t r ) ，其中r 代表时间， 丁代表时间域。如果r 是可数的，则被称为是离散时间过程，它可以表示为 x 。 ； 如果是f 是不可数的，则被称为是连续时间过程。状态矢量空间中包含了随机变 量坂力的所有可能值，它既可以是离散的( 可数的状态) ，也可以是连续的。 如果一个随机过程x = i x , ：r = 0 ，l ，2 ，l ，满足： ( 1 ) 所有的 疋 都有相同的均值和相同的有限方差矿； 华东师范大学硕士毕业论文第二章自相似过程的描述 ( 2 ) c o v ( x t ，) 是独立于时间，而仅仅与时间间隔k 有关的量。 那么这一过程被称为是协方差( 或二阶、宽) 平稳过程。 其自相关函数定义如下： ，( 七) ：鱼墼型 仃 令e = 置，则 七i l 厂m1 哳( e ) = 仃2i 所+ 2 ( m - k ) r ( k ) i ( 2 1 ) 其中蠢= 哳。 短相关过程和长相关过程是能够被严格区分开来的。如果一个过程满足下述 条件： ( 1 ) ：。r ( k ) o o ( 2 ) 对于大的m ，有蠢一( 3 - z ( 3 ) 对于大的m ，有砉哳( z ) 盯2 肌q 则这一过程是短相关的。马尔科夫链和有限阶自回归移动平均过程都满足短 相关特性。 与此相对的是，当一个过程过程满足以下三个条件时，它们就会表现出长相 关特性： ( 1 ) ：。，( 七) 一 ( 2 ) 历吒- - ) a o a sm 专 ( 3 ) 对于大的聊，有砉哆( e ) 仃2 聊叫2 。2 棚 对于短相关，日= 0 5 ；对于长相关，0 5 何 0 和0 0a n d0 5 h 1 ( 2 ) 自相关函数呈双曲线衰减，慢于指数衰减，意味着具有不可和的自相关函数 e t ，( 七) - 0 0 ( l g d ) ，以及 ( 3 ) 当频率趋近于零时，谱密度朋) 是无限增大的，例如， 9 华东师范大学硕士毕业论文第二章自相似过程的描述 ( 旯) 口五一( 2 h 一1 嬲五 0a n d0 5 h 1( 2 1 2 ) 从( 2 1 2 ) 式中可以看出，具有长相关特性的过程，其谱密度是按双曲线形式 衰减，而不像短相关过程那样，按指数的形式衰减，因此，其衰减较慢，表现出 重尾分布( h e a v yt a i l e d ) 。 通过研究绝对矩的性质来分析自相似性的。考虑下式： 伽c 口，= e l x 【册r = e l 去喜y c f ) i 一 如果x 是白相似，那么”( | 9 ) 与m 矿一伊( 1 9 ) 是成比例的。例如l o g 埘( 1 9 ) 与 l o g m 呈线性关系 l o g 2 ( m ) ( | 9 ) = 伊( , 9 ) l o g m + k ( s )( 2 1 3 ) 此外，指数9 ( 1 9 ) 与| 9 呈线性关系。事实上，可以表示为： 伊( 1 9 ) = ( 日一1 ) 1 9( 2 1 4 ) 因此，自相似也可以简单的定义为阶矩呈( 2 1 3 ) 式的比例关系，其中够( - 9 ) 满 足( 2 1 4 ) 式。 2 1 3 自相似过程的性质 1 、长相关性 如果：。，( 七) - 0 0 ，则称平稳过程x 具有长相关性，其中，( d 是过程x 的自 相关函数，m a n d e l b r o t ( 美籍法国数学家，是分形理论的创始人) 将长相关性称 为约瑟夫效应( j o s e p he f f e c t ) 。由自相似定义可知，如果o 5 h i ，厂( 句可近似 表达为以叩( c 为大于o 的常数，= 2 2 h ) ，且具有不可和性，所以自相似过 程是长相关的。长相关性意味着距离较远的数据相关性不可忽略不及，而传统模 型的自相关函数随间隔呈指数衰减，l i pr ( k ) = p * , o p l ，导致：，( 七) o 5 时，h u m 效应表明样本中 极端值的持续时期应比较长，即所谓的持续性( p e r s i s t e n c e ) 。如果这种极端值持 续时期理解为网络业务的突发性，则h 可以用来描述业务突发性的强度。而且， 自相似性使得这种突发性不会因聚集而被平滑掉，即突发性呈现嵌套特点。 3 、方差衰减慢 若对所有的聊= l ，2 ，3 ，均有 ，册( 七) = ，( 七) k - p , 0 1 ，k 一( 2 2 0 ) 即x 为精确二阶自相似过程( e x a c t l ys e c o n d - o r d e rs e l f - s i m i l a rp r o c e s s ) ，则上 式等价于 v a r ( x _ ) 一r n - p , 加一( 2 2 1 ) l l s 一吣i - 、 l、 华东师范大学硕士毕业论文 第二章自相似过程的描述 其中a 是独立于m 的正常数，的取值范围为0 l ，这说明对于自相似 过程，其聚集过程方差的衰减速度要比分段长度m 的倒数慢。而对于传统的短 相关过程，可以证明 v a r ( x 哪) 一b m - i , m _ o o ( 2 2 2 ) 其中b 是独立于m 的正常数。即通常用于分析分组数据传输的随机过程的 方差是以与l m 成比例的速率减小的。 方差随着过程聚集而缓慢衰减，表明自相似过程的波动程度。 4 、谱密度具有幂指数特性 在频域上考虑自相似过程时，由于它的持续性，低频处的频谱密度非常大， 表现为在频率a 的零点附近谱密度函数触) 服从幂指数函数，即 f c a ) 一力- r ，元斗0( 2 2 3 ) 其中0 ， 1 ，允= 1 一，0 l 。因此从谱分析的角度来看，长相关性意味 着当频率a 趋近于0 时，其频谱密度将趋于正无穷( 即l 矿噪声) 。而对短相关特 性而言。在频率五的零点附近，谱密度删是一个有限正数。 数学上，自相似过程具有以下的特性： ( 1 ) 样本均值方差的下降速度比样本尺寸倒数的速度慢很多，在下面的公式 中可以很明显的看出此性质v a r ( 必历) ) a 2 m - p ，当m o o ，且0 卢 1 时。 ( 2 ) 自相关函数呈双曲衰减，而非指数衰减，这表明自相关函数的不可和性， 即长相关性。 ( 3 ) 谱密度火) 遵守指数定律，并且接近( 1 f 噪声) ，其f ( a ) 口五，当五一c o ， 且0 ) ， o o 时 为非衰减的。这与传统的包采样业务过程不同，它的据聚合过程义州当m 专o o 时 趋近于白噪声，即其自相关函数符合下述条件，伽专0 ；当mjo o ，且k 芝1 。 自相似参数又称为h u r s t 参数，是自相似程度的重要度量值，是描述自相似 特征的唯一参数。确切地说，是统计现象的持续性( p e r s i s t e n c e ) 的度量，是随 机过程的长相关程度的一种度量。对于有个不同物理意义的取值范围，0 月 0 5 表示短相关：厅= 0 5 表示不相关；o 5 h 1 为长相关。在实际应用中主要是 通过对参数h 的估值来判定随机时间序列是否具有长相关特性。h 的取值范围 为0 5 圩 1 。越大，过程自相似程度越高，实际网络业务是长相关的。= 0 5 ， 表明流量具备长相关特性；h = 1 ，表明流量具有完全相同的特性：在0 5 到1 之间，日值越大，表明其长相关特性越强。 1 2 华东师范大学硕士毕业论文 第二章自相似过程的描述 2 2 传统网络流量模型 1 9 9 4 年，l e l a n d 和t a q q u 等人发表的文章【3 】通过对以太网上数据的分析， 第一次提出了以太网流量应该以自相似模型来进行有效度量的理论。随后，1 9 9 5 年，p a x s o n 和f l o y d 发表的文章【6 】再一次对传统的网络流量模型提出了挑战。 传统的业务量模型指的是在网络的自相似模型出现之前所普遍采用的模型。 其与自相似模型的根本区别在于模型的短相关性。如传统网络设计中采用了泊松 过程( p o i s s o np r o c e s s ) 、复合泊松过程( c o m p o u n dp o i s s o np r o c e s s ) 、马可夫调制的 泊松过程( m a r k o vm o d u l a t e dp o i s s o np r o c e s s ，m m p p ) 、自动回归模型、自动回归 积分移动平均模型等作为网络的业务模型。这些模型产生的业务，通常在时域仅 具有短相关性，随着时间分辨率的降低，即时间尺度变大，网络流量将趋于一个 恒定值，即流量的突发性得到缓和。以下对这些模型作简单介绍。 2 2 1 马尔可夫模型 马尔科夫过程( m a r k o vp r o c e s s ) 是由俄国著名数学家马尔科夫( 1 8 5 6 - - 1 9 2 2 ) 首 先建立并介绍的。马尔科夫过程包含了一个随机变量集 蜀 ，当过程的下一个状 态1 只依赖于过程的当前状态焉，而与过程以往的状态没有相关性( 无记忆 性) 的时候，我们就称这一个随机变量集组成了一个马尔可夫链。 如果马尔可夫链的状态转移可以发生在任何时间点，则我们称其为连续时间 马尔科夫链；如果马尔可夫链的状态转移只能发生在离散的时间点上，则称为离 散时间马尔可夫链。在离散时间马尔科夫链中，系统停留在同一状态的时间服从 几何分布；在连续时间马尔可夫链中，系统在同一状态的停留时间服从指数分布。 对于马尔科夫过程的扩展和引申还有半马尔科夫过程，隐藏状态马尔科夫过程， 马尔科夫调制过程，马尔科夫更新过程等等。 马尔可夫业务量模型由于模型的解析解的复杂度随着模型参数的增加而增 加以及模型的无记忆性，因此只适用于模型参数较小的系统分析和短程相关的业 务量建模，比如电话网的建模常常借助于马尔科夫业务量模型。 2 2 2 泊松模型 以前人们进行网络研究主要使用的工具就是泊松模型。泊松模型的核心思想 就是网络事件如数据包到达，连接达到是独立分布的，并且它们只与一个单一的 速率参数有关。所谓泊松模型就是指时间序列间隔是离散的，呈指数分布白勺，即 f ( x ) = l e ，并且时间序列到达也是服从指数分布的【5 】，即 华东师范大学硕士毕业论文第二章自相似过程的描述 p 【( ) 一( f ) 】= q = e - a t 等 ( 2 2 4 ) 泊松过程的成立需要三个假设前提：到达的时间序列之间要保持独立分布； 时间到达的大小和时间分布要满足指数分布：交互线路传输等于每个方向的流量 的总和。 2 2 3 回归模型 回归模型包括自回归模型( a r ) 和自回归滑动平均模型( a r m a ) 等等。p 阶自 回归模型a r p ) 的形式如下： ： = 破1 + 晚薯2 + + 砟p + q ( 2 2 5 ) 其中效是相关随即变量，仍是实数，岛是白噪声。如果岛是方差为萨盯的高 斯白噪声，那么勋是正态分布的随机变量，定义一个b 为延迟算子，则： a x , = 一l ，矽) = l 一磊( b ) 一如( b ) 一九( b ) ( 2 2 6 ) 则a 脚) 过程可以表示为 矿( b ) = q( 2 2 7 ) 如果妒) 的根在单位园外，则x t 是平稳过程。其自相关函数为 ，：= 磊，；一l + 噍一2 + 呜- 3 + + 妒p ，：一p ( 2 2 8 ) 尽管a r 模型易于进行参数估计，产生递归序列，但由于其自相关函数以指 数形式衰减，所以仍然只能刻画短相关的时间序列，不适用于比指数衰减慢的自 相关函数结构的网络流量。 自回归滑动平均模型a r m a ( p ，9 ) 如下； 五= 稿薯一l + 欢2 + + 砟t p + q 一岛q 一1 一岛q 一2 一一e q c , 一叮 ( 2 2 9 ) 它等价于： ( b ) = 口( 召) q( 2 3 0 ) 其中9 ( 固为自回归项，8 t 为随机扰动，耿丑) 为滑动平均项。其自相关函数与 a r ( p ) l 拘自相关函数结构相同。a r m a ( p ，g ) 模型只适合刻画短相关的流量，而不 适合于自相似流量的长相关性的刻画。 2 2 4 流体流模型 流体流模型是一种物理意义较为明确的业务量模型，它来源于自然界中水流 的运动规律。自然界中的水流由于受水源，季节，天气，地形等因素的影向会产 生流速的变化，时而平缓甚至枯竭，时而充盈甚至饱和。在网络业务量模型中， 1 4 华东师范大学硕士毕业论文第二章自相似过程的描述 流体流模型常常和o n o f f 模型结合在一起形成o n o f f 流体流模型。当系统 处于o n 状态时，以一定的速率发送数据流：当系统处于o f f 状态时，数据流 停止发送。用流体流刻画o n o f f 过程，模型的处理对象集中于数据流而不是单 个的数据包或者信元( 删，模型状态转移的条件是流速的变化而不是类似于马 尔科夫过程的分组到达。通过这种流体流处理，大大降低了模型的复杂度和运算 量，提高了模型的实用性。 常用的流体流模型还有吉尔伯特一埃利奥特可变流体流模型，马尔科夫调制 流体流模型等等，他们常用来对流媒体或者可变比特速率( v b r ) 数据进行建模。 2 3 自相似网络流量模型 自相似业务模型按模型产生方式分为物理模型和统计模型。物理模型是根据 物理意义建模，如o n o f f 模型；统计模型是统计特性方面入手建立模型，如 f g n 、f a r i m a 等模型。 按照模型产生业务的分形特征，可以将模型分为单分形模型与多重分形模 型。目前应用中使用较多的是单分形模型，如o n o f f 、f g n 、f a r i m a 等。多 重分形由于其建模比较复杂，而且多重分形的分析方法有待进一步发展，所以这 类模型应用不广泛。下面着重介绍分形布朗运动和分形高斯噪声模型的原理和实 现。 2 3 1 分形布朗运动 一、布朗运动 1 8 2 7 年，英国植物学家r b r o w n 发现，悬浮在液体或者气体中的微粒由于连 续的受到周围分子的碰撞而不停顿的作不规则的运动，人们把这种现象称为布朗 运动。1 9 0 5 年，a e i n s t e i n 指出，不管运动在表面上如何不规则，这些粒子的移 动是可以用概率规律来分析的。到了1 9 2 3 年，美国数学家n w i e n e r 开始把布朗 运动作为随机过程来研究，而且很快f 1 3 l e v y 等数学家将之作了很大的发展。 w i e n e r 和l e v y 如下定义布朗运动： 定义2 3 1 布朗运动b ( 0 是这样一种运动，它的初始位置b ( 0 ) = 0 ，其后