（信号与信息处理专业论文）基于神经网络的自相似业务流预测研究.pdf

俸西， 扩肾， 独创性声明 j i i i if lii i ii r li i i i ii i x y 1713 4 6 2 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：塑二缉 日期： 2 矿年j 月弓j 目 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩l ： j 或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：壁垒鍪鎏 导师签名： 1 日期：2 0 卜 摘要 摘要 预测网络业务的行为在通信网络的接入管理和拥塞控制等方面有着重要的意 义。随着现代通信技术的高速发展，网络规模不断扩大，网络业务呈现多样性。 越加复杂的网络行为特征给网络流量建模和预测带来了新的挑战。近年来的许多 的研究表明，网络业务流量普遍存在着自相似性。自相似业务流对网络性能有着 不可忽视的影响。另一方面，业务的这种自相似性也暗示了网络流量具有可预测 的结构。网络流量预测传统方法是利用流量的统计特性建立数学模型。随着神经 网络研究的深入，一些学者也将其用于网络流量的建模和预测。 本文根据网络业务的自相似特征，利用神经网络进行自相似流量的预测和应 用研究。对神经网络的结构和学习算法进行了探索性研究，引入一种基于自适应 增益系数改进的学习算法。本论文的主要研究工作包括以下几个方面： 1 总结网络流量的自相似的特征、及其产生原因和对网络性能的影响。在分 析神经网络在网络流量预测方面研究的基础上，使用b p 和f i r 两种前向神经网络 作为自相似流量的预测模型。 2 研究神经元模型的结构和对信息的处理方式，在分析b p 和f i r 神经网络 标准学习算法基础上，引入一种基于自适应增益系数改进的方法。将改进算法用 于b p 和f i r 神经网络，推导参数的更新方式。在相同的网络结构和初始参数条件 下，分析改进算法对预测结果和均方误差收敛速度的影响。 3 应用b p 和f i r 神经网络进行自相似业务流量的预测。对于相同的网络流 量样本，通过比较不同结构的b p 和f i r 神经网络的预测结果确定用于预测的最优 结构。比较b p 、f i r 和w i e n e r 滤波器对自相似流量的预测结果，选择其中预测性 能最好的模型用作缓冲区动态分配的预测器。 4 根据预测结果动态地分配排队系统的缓冲区空间。在几种缓冲区分配方案 中，分析自相似程度对排队系统性能的影响，为进行缓冲区的动态分配提供依据。 在分析完全分害t j ( c p ) 和实时动态共享( r t d s ) 方案的基础上，提出基于预测的动态 共享( p b d s ) 方案。通过仿真比较三种不同方案对排队系统分组丢失率的影响，同 时分析各个方案对不同业务源的公平性。 关键词：自相似，流量预测，神经网络，增益系数，动态缓冲区分配 a b s t r a c t a b s t r a c t p r e d i c t i n g t h eb e h a v i o r o fn e t w o r kt r a f f i ci s v e r yi m p o r t a n tf o ra d m i s s i o n m a n a g e m e n ta n dc o n g e s t i o nc o n t r o li nt h ec o m m u n i c a t i o nn e t w o r k w i t ht h er a p i d d e v e l o p m e n to fm o d e m c o m m u n i c a t i o nt e c h n o l o g y , n e t w o r k sh a v eb e e ne x p a n d i n ga n d t h en e t w o r kt r a f f i ca p p e a r sd i v e r s i t y 1 1 1 ei n c r e a s i n g l yc o m p l e xb e h a v i o r a lc h a r a c t e r i s t i c o ft h en e t w o r kh a sb r o u g h tn e wc h a l l e n g e st ot h en e t w o r kt r a f f i cm o d e l i n ga n d f o r e c a s t i n g i nr e c e n ty e a r s ，ag r e a tn u m b e ro fs t u d i e s h a v es h o w nt h ec o m m o n e x i s t e n c eo fs e l f - s i m i l a r i t yi nn e t w o r kt r a f f i c 1 1 1 es e l f - s i m i l a rt r a f f i ch a sn e g l i g i b l e e f f e c t st on e t w o r kp e r f o r m a n c e o nt h eo t h e rh a n d , t h ef e a t u r eo fs e l f - s i m i l a r i t y i n d i c a t e st h a tt h e r ee x i s t sap r e d i c t i v es t r u c t u r eo ft h en e t w o r kt r a f f i c n et r a d i t i o n a l m e t h o d so fn e t w o r kt r a f f i c p r e d i c t i o na r et o b u i l dm a t h e m a t i c a lm o d e l su s i n gi t s s t a t i s t i c a lc h a r a c t e d s t i c s w i t ht h e d e e p e n i n go fr e s e a r c hi n n e u r a ln e t w o r k , s o m e s c h o l a r sa l s ou t i l i z en e u r a ln e t w o r kf o rt r a l 陆cm o d e l i n ga n df o r e c a s t i n g a c c o r d i n gt ot h es e l f - s i m i l a rc h a r a c t e r i s t i co fn e t w o r kt r a f f i c ，n e u r a ln e t w o r k sa r e a p p l i e dt os e l f - s i m i l a rt r a f f i cp r e d i c t i o na n di t sp r a c t i c a la p p l i c a t i o n a f t e re x p l o r a t o r y r e s e a r c h e sf o rt h es t r u c t u r ea n dl e a r n i n ga l g o r i t h mo fn e u r a ln e t w o r k , a na l g o r i t h m b a s e do na d a p t i v eg a i nc o e f f i c i e n ti s p r e s e n t e d n l em a i nr e s e a r c h w o r ko ft h i s d i s s e r t a t i o ni ss h o w na sf o l l o w s 1 n ec h a r a c t e r i s t i co fs e l f - s i m i l a rt r a f 五c ，a sw e l la st h ec a u s e so fs e l f - s i m i l a r t r a 伍ca n di t s i m p a c to nn e t w o r kp e r f o r m a n c ei s s u m m a r i z e d a r e ra n a l y z i n gt h e p r e d i c t i o nr e s e a r c h e so fs e l f - s i m i l a rt r a f f i cu s i n gn e u r a ln e t w o r k , t w ok i n d so ff e e d f o r w a r dn e u r a ln e t w o r k , w h i c ha r eb pa n df i rn e u r a ln e t w o r k , a r eu s e da sp r e d i c t i o n m o d e li nt h i sp a p e r 2 n l es t r u c t u r ea n di n f o r m a t i o np r o c e s s i n go fn e u r o nm o d e la r es t u d i e d a f t e r a n a l y z i n gt h es t a n d a r da l g o r i t h mo fb pa n df i r n e u r a ln e t w o r k , an e wm e t h o db a s e do n a d a p t i v eg a i nc o e f f i c i e n ti sp r e s e n t e d u t i l i z i n gi m p r o v e da l g o r i t h mi nb pa n df i r n e u r a ln e t w o r k s ，t h eu p d a t ef o r m so fp a r a m e t e r sa r ed e d u c e d u n d e rt h ec o n d i t i o no f s a m en e u r a ln e t w o r ks t r u c t u r ea n di n i t i a lp a r a m e t e r s ，t h ei n f l u e n c e so fp r o p o s e d a l g o r i t h mo nt h ep r e d i c t i o nr e s u l t sa n dt h ec o n v e r g e n c es p e e do fm e a ns q u a r ee r r o ra r e h a b s t r a c t a n a l y z e d 3 t h eb pa n df i rn e u r a ln e t w o r k sa r ea p p l i e df o rs e l f - s i m i l a rt r a f f i cp r e d i c t i o n f o rt h es a m es a m p l e so fr e a ln e t w o r kt r a 伍c ，t h eb e s ts t r u c t u r e so fb pa n d f i rn e u r a l n e t w o r k sf o rp r e d i c t i o na r ed e t e r m i n e db yc o m p a r i n gt h ep r e d i c t i o nr e s u l t so fd i f f e r e n t s t r u c t u r e s a f t e rc o m p a r i n gt h ep r e d i c t i o nr e s u l t so fb p , f i ra n dw i e n e rf i l t e rf o r s e l f - s i m i l a rt r a f f i c ，t h eo p t i m a lm o d e li su s e df o rp r e d i c t i o nt o o li nd y m m i cb u f f e r a l l o c a t i o n 4 a c c o r d i n gt ot h ep r e d i c t i o nr e s u l t s ，t h eb u f f e rs p a c ei sa l l o c a t e dd y n a m i c a l l y i ns e v e r a lb u f f e ra l l o c a t i o ns c h e m e s ，t h ea n a l y s i so fs e l f - s i m i l a r i t yo np e r f o r m a n c eo f q u e u i n gs y s t e m sp r o v i d e se v i d e n c ef o rt h ed y n a m i cb u f f e ra l l o c a t i o n b a s e do nt h e a n a l y s i so fc o m p l e t ep a r t i t i o n i n g ( c p ) s c h e m ea n dr e a l t i m ed y n a m i cs h a r i n g ( r t d s ) s c h e m e ，ap r e d i c t i o n - b a s e dd y n a m i cs h a r i n g ( p b d s ) s c h e m e i s p r o p o s e d t h e i n f l u e n c e so ft h r e ed i f f e r e n ts c h e m e so nt h ep a c k e tl o s sr a t eo faq u e u i n gs y s t e ma r e c o m p a r e di nt h es i m u l a t i o n i nt h es a m et i m e ，t h e f a i r n e s so ft h e s es c h e m e st oe a c h t r a f e cs o u r c ei sa n a l y z e d k e y w o r d s ：s e l f - s i m i l a r i t y , t r a 伍cp r e d i c t i o n , n e u r a ln e t w o r k s ，g a i nc o e f f i c i e n t , d y n a m i c b u f f e ra l l o c a t i o n i l l 目录 目录 第一章绪论1 1 1 课题背景。l 1 1 1 网络流量的自相似现象。1 1 1 2 自相似业务流产生的原因和影响3 1 2 神经网络用于自相似业务流预测的研究现状分析4 1 3 本文的研究任务及结构安排5 1 3 1 本文的研究任务5 1 3 2 本文的结构安排5 第二章网络业务流量的自相似性7 2 1 自相似的定义及数学描述7 2 1 1 严格自相似过程一7 2 1 2 二阶自相似过程8 2 1 3 渐近二阶自相似过程。9 2 2 自相似过程的性质1 0 2 3 自相似流量的生成方法11 2 4 自相似程度的检测方法1 3 2 5 本章小结15 第三章神经网络基本理论16 3 1 神经元模型1 6 3 2 神经网络结构及算法1 8 3 2 1b p 神经网络结构和学习算法。1 8 3 2 2f i r 神经网络结构和学习算法2 1 3 2 3 两种神经网络与w i e n e r 滤波器的关系2 4 3 3 应用神经网络进行网络流量预测的理论依据2 6 3 4 本章小结2 7 第四章基于自适应增益系数改进的神经网络学习算法。2 8 i v 目录 4 1 基于自适应增益系数改进算法的提出2 8 4 2 改进学习算法在b p 和f i r 神经网络中的推导3 0 4 2 1 改进学习算法在b p 神经网络中的推导3 0 4 2 2 改进学习算法在f i r 神经网络中的推导3 3 4 3 算法总结及复杂度分析3 5 4 4 本章小结3 7 第五章基于神经网络的自相似业务流预测一3 8 5 1 预测性能指标3 8 5 2 流量数据的预处理3 9 5 3 神经网络预测模型的建立4 0 5 3 1b p 神经网络结构选择4 1 5 3 2f i r 神经网络结构选择4 2 5 3 3w i e n e r 滤波器参数确定4 4 5 4 预测结果分析及比较4 5 5 4 1 改进学习算法和标准学习算法的比较4 5 5 4 2 不同预测模型的比较4 8 5 5 本章小结5 l 第六章基于预测的动态缓冲区分配5 3 6 1 排队系统及缓冲区分配5 3 6 2 仿真结果及分析：5 4 6 3 本章小结5 9 第七章结论一6 0 致谢6 2 参考文献6 3 攻硕期间取得的研究成果6 7 v 第一章绪论 第一章绪论 随着现代通信技术的高速发展，以语音、视频为主的宽带多媒体业务在i n t e m e t 互联网业务中的比重大大增加，第三代无线通信系统的广泛商用也将为用户提供 诸如在线电视、视频会议等多种多样的通信业务。同时，用户对网络服务质量的 要求也越来越高，但多种多样的网络业务使网络行为越来越复杂，对通信网络的 规划和设计带来了新的挑战。进行网络流量预测在网络资源管理有着重要应用， 许多学者在这方面进行了大量研究。本章首先介绍了通信网络中流量的自相似现 象及其对网络性能的影响，接着对神经网络在自相似流量预测方面的研究进行了 概述，最后给出课题的研究任务和本文的结构安排。 1 1 课题背景 1 1 1 网络流量的自相似现象 1 9 8 9 年至1 9 9 2 年间，l e l a n d 和w i l s o n 对b e l l e o r em o r r i s t o w n 研究与工程中 心多个以太网中传输的数据分组进行了精密的监测【l 】，每到达一个数据分组记录一 次。他们对收集到的l a n ( l o c a la r e an e t w o r k ) 业务中的许多数据分组在不同时间 尺度上的统计特征进行了分析，表明不同时间尺度聚合的实际网络业务表现出一 致的突发。l a n 业务的这种自相似或类似分形的特征不同于传统的电话业务，不 能用基于泊松或马尔可夫等短相关模型进行描述。传统的短相关模型中，突发在 较长时间尺度上的影响可以忽略，而自相似业务对网络性能的这种影响仍然存在。 自从l e l a n d 和w i l s o n 发现u 嫩业务具有自相似性以后，不少学者对其他很 多实际网络流量进行了研究分析。与l e l a n d 和w i l s o n 的研究类似，b f o w l e r l 2 j 等 人比较了不同时间尺度下实际测量到的网络流量和泊松模型产生的数据，其研究 结果如图1 1 所示，从图中可以看出基于泊松过程的业务流量只具有短相关性，在 时间尺度增加的情况下，单位时间内收到的数据包数量呈现出无关性1 3 j ；而实际网 络业务是长相关的，在大的时间尺度下仍具有相似的突发特性。其他有代表性的 研究有：19 9 5 年，v e t op a x s o n 和s a l l yf l o y d 收集的w a n ( w i d ea r e an e t w o r k ) 业 务数据1 4 1 ；2 0 0 2 年，j u n s h a nz h a n g 等人基于c d m a ( c o d ed i v i s i o nm u l t i p l ea c c e s s ) 电子科技大学硕士学位论文 系统产生的上行链路及下行链路的多址干扰数据1 5 1 ；2 0 0 8 年，k s m u n a s i n g h e l 6 1 收 集的包括u m t s ( u n i v e r s a lm o b i l et e l e c o m m u n i c a t i o n ss y s t e m ) 、c d m a 2 0 0 0 和 w i m a x ( w o r l d w i d ei n t e r o p e r a b i l i t yf o rm i c r o w a v ea c c e s s ) 等异构无线数据网的多媒 体数据；近来，一些研究指出w l a n ( w i r e l e s sl o c a la r e an e t w o r k ) v j 、a dh o c 网 络【8 】及w s n ( w i r e l e s ss e n s o rn e t w o r k ) 9 】等网络中传输的业务也具有自相似性。这些 研究结果表明，不论是局域网，还是广域网中的业务数据以及无线网络中的多媒 体业务都在不同的时间尺度上呈现出自相似性。 图1 1 不同时间尺度下实际网络流量与p o i s s o n 分布产生的数据比较 2 i-1i簧，霹_叠_t；r；要1，；，掰珂j鬟薯r。埘，量鞠哪盛_封 薯1错1罐1斟1广_&，0搿1，鬟i ，捌嗣1曩习融皇矗1j瑾嗣乎 第一章绪论 1 1 2 自相似业务流产生的原因和影响 人们对网络业务存在自相似现象的原因进行了大量研究，文献 1 0 】指出网络流 量的自相似性是网络协议、数据业务类型和用户状态等因素共同作用的结果，这 是从流量的物理形成意义上进行的解释。另外，许多研究从网络传输的文件长度 或传输时间的统计特性上进行了分析，这是从网络业务本身的结构特点进行的解 释。一般的观点分为两类，一种认为单一的业务流量本身具有自相似性，比如 v b r 【l 、m p e g 1 2 】视频；另一种则是认为网络中文件长度或者数据业务的传输活 动时间( 活动或空闲时f - - j ) g 务重尾分布【l 孓1 5 】，传输过程中多个文件或业务的叠加的 使流量具有自相似性，这种情况在异构网络不同业务的汇接点处最常发生。另外 也有人认为非重尾分布也能产生自相似业务流，比如对数正态分布【1 6 j 。总之，自 相似是各种网络中普遍存在的一种现象。 由于实际网络业务流量具有自相似性，传统的基于泊松到达的短相关模型对 网络排队性能等的分析与实际应用有很大的差异。网络流量的自相似性使网络性 能发生了改变，对网络性能的分析有重要影响，也成为网络性能分析中需要考虑 的重要因素。业务流量的自相似对网络性能的影响主要表现在以下几方面： 1 ) 基于传统短相关模型的排队论在大的时间尺度上忽略了业务突发的影响， 而自相似业务流即使在很长的时间尺度上突发对排队性能的分析仍然有很大影 响。因此，在多路复用器和交换机的设计中需要更大的缓冲区来减少包丢失，但 是缓冲区的增加也使数据包有更大的传输时延。在一定的带宽约束下，需要综合 考虑包丢失和排队时延的关系。 2 ) 当缓冲区容量达到一定大小后，增加缓冲区容量对数据包丢失率的影响将 会变小【l r l 。但是如果增加交换机或多路复用器的活动连接数量将导致包丢失率的 大大增加，因为复用后的业务流突发仍然存在。 3 )自相似业务流的长相关性使流量的突发现象有可能持续较长时间，大的突 发降流量低了链路资源的利用率。在通信量较小的时候造成带宽资源浪费，在通 信量突然增大时容易造成链路拥塞，甚至是通信设备瘫痪。 4 ) 网络业务自相似的另一个影响是使分配网络资源的动态分配遇到挑战。当 前许多网络的动态拥塞控制策略是根据当前网络流量实时进行资源分配的调整， 某些时刻网络业务会产生高突发流量，并且有可能持续较长时间，使得对当前流 量的测量难以适应流量的快速变化。所以，有必要根据未来的流量信息调整网络 的资源分配。 3 电子科技大学硕士学位论文 由此可见，网络业务的自相似性对网络的性能的影响比传统的仅具有短相关 特性的业务对排队性能的影响更大。网络流量的长相关性引起网络性能下降，使 网络性能的分析变得更加复杂。预测是利用自相似业务流的这种长相关结构，对 业务的未来行为做出预报，是网络流量研究的重要方面，对于网络性能分析及应 用研究有积极意义。 1 2 神经网络用于自相似业务流预测的研究现状分析 建立流量模型是研究网络流量性质和内在规律的常用方法，对网络设计和规 划等实际应用也有指导意义。对业务流的预测依赖于模型的类型和已知流量的历 史数据。传统的用于时间序列预测的a r 、a r m a 等模型只具有短相关性【l 引，不 能很好地描述自相似业务流的长相关性和高突发特性。文献【1 9 用 f a r i m a ( f r a c t i o n a la u t o r e g r e s s i v ei n t e g r a t e dm o v i n ga v e r a g e ) 模型拟合自相似业务 流，该模型可以同时刻画实际流量所具有的短相关性和长相关性。这些模型基于 已知时间序列的先验统计信息出发，得到模型参数，适用于统计特性不随时间改 变的平稳时间序列。 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，a n n ) ，也称神经网络，在一定误差 范围内能很好地完成许多复杂功能，被广泛地应用于制造、医疗、交通、计算机 及金融等行业。这个误差范围由神经网络结构、参数及应用场景决定。1 9 8 7 年， l a p e d e s 等人首先将神经网络应用于由计算机产生的时间序列仿真数据的学习和 预测【2 0 】。自此，神经网络开始应用于网络流量的预测。在自相似业务流的预测中， 神经网络通过对样本数据的训练学习，得到样本数据的内在规律，不需要对业务 数据的统计先验信息进行分析。另一方面，神经网络是一种非线性系统，能够很 好地描述实际网络业务中所具有的非线性和非平稳特性。 本文主要采用b p 和f i r 两种前向神经网络进行自相似业务流的预测和应用研 究。b p 神经网络( b a c kp r o p a g a t i o nn e u r a ln e t w o r k ) 是最广泛用的一种前向神经网 络，2 0 0 0 年，y u a n g 等人提出了利用b p 神经网络来解决无线a t m 网络中的带宽 分配问题【2 1 1 。文献【2 2 】用两个正切函数调节b p 神经网络的权值修正过程，并将这 种算法用于有线网络信号的预测。文献 2 3 】对b p 神经网络的激活函数的分子分母 分别作了系数调整，用改进后的网络预测了下一代网络i p v 6 的流量。文献 2 4 1 使 用遗传算法的b p 神经网络分析w s n 网络的异常样本，预测系统中出现的不正常 信号。 4 第一章绪论 f i r 神经网络是对b p 神经网络的一种改进形式，其结构和算法最早由e a w a n 提出1 2 5 1 ，并应用f i r 神经网络对时间序列的预测进行了详细的分析；文献【2 6 】讨论 了以太网网络流量的性质，并将f i r 神经网络用于网络流量的预测，指出w a n 提 出的算法对于自相似业务流有很好的预测性能。文献【2 7 】将f i r 神经网络求和方式 得到的净输入改成求积形式，应用这种网络进行了混沌时间序列预测的研究。 这些研究表明，b p 和f i r 神经网络是预测自相似业务的有效模型，而且对这 两种前向神经网络结构及算法的研究也说明神经网络是一种比较灵活的数学工 具，对其算法和应用的研究可以延伸到很多方面。 1 3 本文的研究任务及结构安排 1 3 1 本文的研究任务 在分析以上资料的基础上，充分理解网络流量的自相似性和b p 和f i r 两种前 向神经网络的结构特点和学习算法，本论文主要完成以下任务： 充分理解网络业务流量的自相似特征、及其产生原因和对网络性能的影响。 学习自相似业务流的特点及相关预测模型，重点掌握b p 和f i r 神经网络的结构特 点和学习算法。 分析神经元模型的结构和数学描述方式，引入一种基于自适应增益系数的改 进方法。将这种方法应用于b p 和f i r 神经网络，详细推导了基于自适应增益系数 的b p 和神经网络学习算法。 应用b p 和f i r 神经网络进行自相似业务流量的预测研究。在相同神经网络结 构和初始条件下使用两种不同算法，通过仿真比较改进学习算法和标准学习算法 对预测均方误差收敛速度的影响。使用相同学习算法，比较b p 和f i r 神经网络的 预测能力，同时对比w i e n e r 滤波器这种线性模型和神经网络的预测结果。 分析不同h 参数业务流对网络性能的影响，基于预测结果动态地分配缓冲区 空间。对比完全分害a j ( c p ) 和实时动态共享( r t d s ) 方案，分析基于预测的动态共享 ( p b d s ) 方案在减少排队系统分组丢失率中的优势。 1 3 2 本文的结构安排 第一章是绪论，介绍网络流量的自相似性及其产生原因和影响，总结自相似 业务流的预测研究现状，给出本文的研究任务。 电子科技大学硕士学位论文 第二章总结了自相似的数学定义及描述方式，研究自相似业务流生成方法、 流量自相似程度的检测方法。 第三章在介绍神经元模型及其对信息的处理方式，研究b p 和f i r 神经网络的 结构特点和学习算法。另外，分析神经网络的学习方式和利用前向神经网络进行 自相似业务预测的理论依据。 第四章在分析神经元模型和神经网络学习算法的基础上，提出基于自适应增 益系数的学习算法，对b p 和f i r 神经网络中参数的更新形式进行了推导。 第五章是本文的重点，使用b p 和f i r 两种神经网络对自相似业务流进行预测 研究。通过实验比较不同结构的神经网络的预测结果，选择最优结构作为预测模 型。对于确定结构的预测模型，通过仿真使用不同算法时均方误差的收敛速度及 预测结果的差别。另外，在使用相同学习算法时，比较不同模型对自相似业务的 预测能力。 第六章分析流量自相似程度对排队系统性能的影响，基于预测结果进行缓冲 区的动态分配，比较不同缓冲区分配方案对于排队系统分组丢失率的影响。 第七章是本文的总结。 6 第二章网络业务流量的自相似性 第二章网络业务流量的自相似性 自相似网络业务在不同的时间尺度上具有相似的突发特性，事物具有的这种 几何上的尺度不变性被称之为分形，这是自然界中许多事物普遍存在的一种性质。 分形最早由m a n d e l b r o t 在1 9 6 8 年提出，当时他从不同高度拍摄到海岸线，发现照 片中的曲线在不同程度上具有相似的形状。并且，他给出了分形的最初定义：事 物局部在一定程度上与其整体相似的形态称为分形。网络业务流量的这种尺度不 变的突发特性表现为，如果网络业务在前一时刻处于突发状态，那么在下一时刻 仍处于突发的概率将大于处于非突发的概率；如果网络业务前一时刻处于等待状 态，那么在下一时刻处于等待状态的概率将大于被服务的概率。本章对自相似的 定义、数学描述、自相似业务的生成和检测方法作了简单介绍，为进行流量的预 测提供基本的理论依据和相关方法。 2 1 自相似的定义及数学描述 网络业务流量自相似过程指的是流量统计特性不随时间尺度的改变而变化的 一类随机过程。自相似过程的定义主要是从其统计特征描述，以下是自相似随机 过程的数学定义和描述方法。 2 1 1 严格自相似过程 定义2 1 如果一个连续随机过程 x ( f ) ，t 灭) 满足如下条件：对于任意a 0 ， o 5 h 1 ，x ( a t ) 与a 月x ( t ) 的有限维分布相同，则称x ( f ) 是具有自相似参数日 的自相似过程。 以上是自相似随机过程的连续时间定义。其中参数是随机过程自相似程度 的度量，被称为h u r s t 指数。可以用日的值判断时间序列的相关程度，当h = 0 5 时， 时间序列是随机变化的，不可预测；当0 5 ，口 0 ，o 5 h 1 ，满足如下条件 e x ( a t ) 】= a e 【x ( r ) 】 ( 2 - 2 ) v a r x ( a t ) 】= a2 v a r x ( t ) 】( 2 3 ) c z ( a t ，a s ) = a 埘c x ( t ，s ) ( 2 - 4 ) 那么 x ( r ) ，t r ) 被称作参数是何的二阶自相似过程【1 6 1 。 以上关于二阶自相似过程的定义不一定是平稳的自相似随机过程。在网络流 量性质的研究中为了简化数学分析，一般假定其为二阶的平稳自相似随机过程， 更高阶的统计指标一般没有考虑。 定义2 4 设离散时间序列 x ( 拧) ，刀z ) 的均值p = e 【x ( 力) 】恒定不变，且具有 有限方差，其自相关函数表示为 r ( k ) = i e 【( e ( 刀) 一p ) ( e ( 聆+ j | ) 一p ) 】 k = 0 ，1 ，2 ， ( 2 5 ) 如果y ( 七) 只中是k 的函数，与时间指数刀无关，而且与其m 阶聚合序列x 柚有以 下关系成立 研x ( 拧) 】= e x 伽】( 2 6 ) 掰一卢v a r x ( n ) = v a r x 加】 ( 2 7 ) y ( 七) = y 伽( 霓)( 2 8 ) 8 第二章网络业务流量的自相似性 其中，y ”( 七) 是随机时间序列x ( ”) 的自相关函数，0 卢 1 ，h u r s t 参数 h = l 一卢2 。那么随机过程 x ( 刀) ，刀z ) 被称为是具有参数日的广义平稳二阶自 相似过程【捌。 广义平稳二阶自相似过程也被简称为平稳自相似过程，它的另外一种常用到 的定义形式如下 定义2 5 如果上述离散时间序列 x ( ，z ) ，刀z ) 的自相关函数r ( k ) 在七寸a o 时 有下式成立 ，( 七) 七一p l ( k )( 2 9 ) 其中，0 卢 0 0 时，y ( 七) c k ，其中c 为常数，0 卢 0 时 厂( 九) a 一1 。声 ( 2 - 1 6 ) 其中，卢= 2 2 h 。从( 2 1 6 ) 式得当a 一0 ，厂( 旯) 哼，即在a 接近o 时厂( 允) 将 无限接近正无穷。而短相关业务的谱密度厂( a ) 是有限的【3 0 1 。 4 ) h u r s t 现象p 1 1 。对于随机过程 x ( 以) ，刀n ) ，其均值和方差分别为p 和 s2 ( 刀) ，对于所有后= 1 ，2 ，n 令w ( k ) - 【z ( 1 ) + x ( 2 ) + + 彳( 七) 卜j j j l i ，定义重新 调制尺度权差 器= 型业幽堕型戋产盟巡幽( 2 - 1 7 ) 一= = - - _ _ - _ _ - _ - _ _ _ _ _ - - _ - - _ _ _ _ _ - _ _ _ - - _ _ _ i i _ _ - _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - i _ _ _ _ _ _ _ _ _ _ _ _ - _ - _ - _ _ - _ _ 一 s ( 厅)s ( 拧) l o 第二章网络业务流量的自相似性 h u r s t 在1 9 9 1 至1 9 9 5 年间发现自然界大多数收集到的时间序列重新调制尺度权差 的均值当h 一时满足研r ( 玎) s ( ”) 】翻，这里0 5 日 x ) 。吨 ( 2 1 8 ) 其中，c 是正常数，0 a o ) ，表示模型中第i 个数据源。每 一个o n o f f 源只有两种状态，在o n 状态时数据源以恒定的速率产生数据，对 应于用户的活动状态，这时x ( f ) = c 表示有数据产生，c 表示单个源的业务产生速 率；在o f f 状态时数据源处于空闲，这时x ( t ) = 0 不产生数据，对应于用户的空 闲状态。每个源的o n 状态持续时间独立同分布，o f f 状态的持续时间也是独立 1 2 第二章网络业务流量的自相似性 同分布的随机变量，但o n 和o f f 的持续时间不一定具有相同的分布，在本文中 o n 和o f f 的持续时间均采用p a r e t o 分布。假定有个这样的o n o f f 源叠加， 在时n t 链路中产生的数据包数为 尸( f ) = x ”( f ) ( 2 2 1 ) ，l l 可以证明当寸时，o n o f f 模型产生的流量数据是渐近自相似的。当 a = 1 4 时，使用1 0 0 个o n o f f 源叠加产生的长度为1 0 0 0 0 点的自相似业务流如 图2 2 所示。 图2 2o n o f f 模型产生的自相似业务流 2 4 自相似程度的检测方法 研究网络流量的自相似性，必须考虑其自相似程度对网络性能的影响。h u r s t 参数是描述序列自相似程度的唯一参数，其检测方法有许多种，比如方差时间法、 r s 方法、w h i t t l e 估计法、小波检测法和h i g u c h i 法【3 5 1 等，其中方差时间法和r s 方法是最常用的两种检测方法。方差时间法计算复杂度小，但在检测自相似程度 1 3 电子科技大学硕士学位论文 较高的业务流时往往不够精确，综合考虑检测的准确性和实现的难易程度，本文 采用r s 方法进行业务流量h 参数的检测。 以下介绍r s 检测方法。根据自相似过程的h u r s t 性质，当力一0 0 时重新调