（计算机应用技术专业论文）自相似网络传输与拥塞控制.pdf

摘要 摘要 网络性能是计算机用户普遍关心的问题，网络性能评价和改进一直是计算机 网络技术领域的研究热点之一。一方面，数据网络传输自相似特征的发现，打破 了原有的对数据流量短相关的基本假设，使得研究人员对网络性能评价领域的认 识发生了一次飞跃，即，传统的马尔科夫模型不能很好地描述数据网络传输；另 一方面，t c p 协议是目前互联网使用最普遍的第四层协议，在自相似网络传输背 景下，对t c p 效率的研究，特别是t c p 的拥塞控制，对于网络性能评价与改善 有重要意义。 针对上述问题，本文在数据网络的自相似性刻画与流量模型以及在此背景下 的网络拥塞控制进行了有益展开。首先，本文从自相似过程的数学性质出发引出 h u r s t 指数计算，对常用h u r s t 计算算法进行了总结，主要有方差时间图法、r s 分析法、周期图法、小波分析法、w h i t t l e 估计法、h o u s s a i n - j o h n 方法等。其次 分析了几种常用的自相似网络传输模型，o n o f f 模型，f b m f g n 、f a r i m a 模型 在拥塞控制方面，采用基于n s 2 的网络仿真平台的仿真研究方案。对于自 相似网络流，对比研究了以d r o p t a i l 和r e d 为代表的两类不同的队列管理机制 的网络吞吐量和数据包延迟等网络性能。接下来，着重于t c p 拥塞控制算法方 面，在仿真自相似网络流量的背景下，分析了r r t 、计时器粒度以及s l o w s t a r t t h r e s h o l d 等因素对t c p 效率的影响；最后根据自相似传输的长相关特征，基于 网络流量的预测对t c p 拥塞控制算法进行了改进，仿真表明，t c p 拥塞控制的 改进算法能增大t c p 的吞吐量，提高t c p 的效率。 关键词网络传输；自相似：h u r s t 指数：队列管理；拥塞控制 a b s t r a c t n e t w o r kp e r f o r m a n c ei sap r o b l e mw h i c hi sw i d e l yc a r e da b o u ta m o n gc o m p u t e r u s c l sa n dw o r k e r $ n e t w o r kp e r f o r m a n c ee v a l u a t i o ni so n eo ff o c u s e si nt h ef i e l do f c o m p u t e rn e t w o r k i n gr e s e a r c h o no n eh a n d ，t h ef i n d i n go fs e l f - s i m i l a rn e t w o r k t v d 伍ch a sm a d ec o r r u p t e dt h eb a s i ca s s u m p t i o no f 乜 a f f i ce n g i n e e r i n g ，i e t h en e t w o r k i r a 伍ci ss h o r t - r a n g ed e p e n d e d ，w h i c hm e a n st h em a r k o vm o d e li sn ol o n g e rs u i t a b l e f o rt h ep a c k e tn e t w o r kt r a f f i ca n di th a sc a u s e dar e v o l u t i o ni nt h ea r e ao fn e t w o r k p e r f o r m a n c e o nt h eo t h e rh a n d , t c pi st h em o s ti m p o r t a n tt r a n s p o r tp r o t o c o li nt o d a y a n df u t u r en e t w o r k , s ot h er e s e a r c ho ft c pp e r f o r m a n c eu n d e rt h ec o n t e x to f s e l f - s i m i l a r l l a 伍c ，e s p e c i a l l y t h e c o n g e s t i o nc o n t r o l ，i sb e c o m i n g o fc r u c i a l i m p o r t a n c et on e t w o r kp e r f o r m a n c ee v a l u a t i o n t od c a lw i t hs u c hq u e s t i o n s t h i st h e s i si n l r o d u c e s t h er e s e a r c hw o r ko nt h e s e l f - s i m i l a r i t yd e s c r i p t i o na n d 仃a 伍cm o d e la n dt h ec o n g e s t i o nc o n 仃o lw i t ht h e b a c k g r o u n do fs e l f - s i m i l a rn e t w o r kt r a l i i c f i r s t l y , m a t h e m a t i cc o n c e p to fs e l f - s i m i l a r p r o c e s si si n 灯o d u c e da n ds e v e r a lh u r s tp a r a m e t e rc o m p u t i n gm e t h o d sa r ed e r i v e d f r o mt h en a t u r eo fs e l f - s i m i l e rp r o c e s s ，i e ，v a r i a n c e t n n ep l o t ，r s ，p c r i o d g r a m ， w l l i 砌e ，w a v e l e t - m e t h o d a n dh o u s s a i n j o h n s e c o n d l y ，t h es e v e r a lc o m m o nu s e ds e l f - s i m i l a r 仃a 伍cm o d e l sa r ei n t r o d u c e da n d r e a l i z e d ，i e ，o n o f f , f b m f g n ，a n d 删m a 1 1 l c s em o d e l si si m p o r t a n tt o g e n e r a t er i g h tt r a 伍cp a t t e r ni nn e t w o r ks i m u l a t i o n f i n a l l t h ec o n g e s t i o na n a l y s i si sm a i n l yb a s e do nt h es i m u l a t i o nw i t ht h em o s t p o p u l a rs i m u l a t i o nt o o ln s 2 w i t ht h eb a c k g r o u n do f s e l f - s i m i l a rn e t w o r kt r a 伍c t c p p e r f o r m a n c ei sa n a l y z e di nd e t a i l ，c o v e t i n gd i f f e r e n tq u e u em e c h a n i s m s ，f a c t o r ss u c h a sr t r t u n e rg r a n u l a r i t y , s l o ws t a r tt h r e s h o l d , a n di m p r o v i n gt h ec o n g e s t i o nc o n t r o l a l g o r i t h ma c c o r d i n gt h et r a l i i cp r e d i c t i o n s i m u l a t i o n ss h o wt h a tt h et c p p e r f o r m a n c ec a nb ei m p r o v e dw i t ht h em o d i f i e dt c pc o n g e s t i o nc o n t r o la l g o r i t h m s k e y w o r d ss e l f - s i m i l a r i t y ；n e t w o r kt r a 伍c ；h u r s tp a r a m e t e r ；q u e u em e c h a n i s m ； c o n g e s t i o nc o n t r o l - m 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其他教育机构 的学位或而使用过的材料。与我一同工作的同志对本研究做的任何贡献均已在 论文中作了明确的说明并表示了谢意 签名：盗盒些日期：兰! ! ! ：! ：! ! 关于论文使用授权的说明 本文完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 日期；丝! ! ：! 兰 1 1 课题背景与研究意义 第1 章绪论 计算机网络已经渗透到社会生活的各个方面，正使人们的生活方式发生着深 刻的变化。计算机网络的应用也已经从早期的比较单一的功能如文件共享发展到 各式各样的服务，比如多媒体，交互式娱乐，电子商务以及各种商业应用。因此， 人们对计算机网络提供的服务也提出了越来越高的要求，比如带宽，延时，安全， 容错等。然而网络资源并不是无限的，如何使有限的网络资源满足人们的各种需 要，提高网络资源的利用率，是计算机网络性能评价主要目标【1 1 。 在2 0 世纪9 0 年代初期，b e l lc o r e 的研究人员对大量的以太网流量数据和 v b r 视频业务数据分析后发现，数据网络的流量行为与电话网络存在十分明显 的差异，即数据网络的流量具有统计上的自相似特性，而不遵从传统的马尔可夫 模型假设，这是计算机网络性能评价领域中的一个重大发现，这个发现导致了人 们对网络流量建模与性能评价的认识的根本变化【2 】。自从l c l a n d 等人的o nt h e s e l f - s i m i l a r n a t l 鹏o f e t h e r n e t 昀伍c 论文发表以来，世界各国的研究人员对现有网 络进行了大量的测量和分析，发现在局域网( l m 田【2 】，广域网( 【3 1 ，公共信道 网( c c s n s s 7 ) 4 ，综合服务数字f 目( i s d n ) t 卯，a t m 网络上v b r 视频1 6 1 ，无线局域 网【7 心，a d h o c 无线网i g l l l 剐等，自相似现象普遍存在。实验表明，网络流量的自 相似性使得传统的基于马尔可夫假设的流量模型和性能分析面l 临极大的困难。 自相似特征反映业务在所有时间尺度上的统计特性，突出地表现为突发没有 明确的长度，在所有的时间尺度上发生，无法将它们平滑掉，导致队列动态行为 预测的极不准确。经验表明，网络业务的自相似特性会对网络性能产生一些意想 不到的后果。例如，许多第一代a t m 交换机出现的溢出率大大高于预先估计， 缓冲区设计国小等问题，很大程度上是因为没有考虑流量自相似特征的影响。一 般认为，自相似传输由于具有很大的突发性，导致了网络更大的延迟和抖动，即 使在链路利用率很低的情况下也如此。 从内涵上讲，自相似过程是一类长相关过程 2 1 ，所谓长相关是指两点之间的 相关函数随着距离的增大按双曲线( 幂函数，多项式) 衰减到零。这个衰减速度比 短相关过程的指数函数衰减要慢的多。这就是说，过程的将来某个时刻的值与它 的过去时候的值是不独立的，换句话说，过程的历史值会决定将来值，因此考虑 利用长相关性对网络实施基于预测的流量控制。 流量控制【l o j 突出表现在网络中间节点的队列管理上，是实现拥塞有效控制的 中心环节之一。在网络发展初期，缓冲管理主要还是尾部丢弃机制，调度也以单 纯的先来先服务为主。这种流量控制机制的优点是实现非常简单，但是效果不好， 北京工业大学工学硕士学位论文 甚至存在某些缺陷。为了尽可能改善网络性能，在缓冲管理策略的选择方面，主 动的而非响应性的分组丢弃就是一种有效的手段，也被称为a q m ( 主动队列管理) 机制l 】【伦】，已成为近来端到端拥塞控制研究中的热点。网络传输的自相似特征 使得流量突发在大范围内存在，给网络拥塞控制带了极大的挑战，但是也因为自 相似传输的长相关特征，使得网络流量预测成为可能，也给拥塞控制提供了新方 法 1 2 国内外研究现状 1 2 1 数据网络传输的自相似特征与模型 基于泊松过程或者马尔可夫过程的网络流量建模有很长的历史。这一类过程 属于短范围相关过程( s r d ) 。这类模型基于泊松到达的假定，认为网络流量的突 发在短时间内发生，从长时间段来看，突发可以被平滑掉。对于由缓冲和服务组 成的系统而言，这种长期的平滑性意味着缓冲在短时间内被填满，在一个较长的 时间内被排空，因此网络中间节点( 如路由器，交换机) 拥有中等大小的缓冲空间即 可。此外，短相关过程流量模型具有确定的分析解，能够很好地描述传统的语音 网络( 比如电话网络) 数据到达行为。而这种模型也一直应用于数据网络的流量分 析【1 】 随着网络包测量技术的发展，使得测量每个数据包到达网关路由器的时间到 达了很高的精度。对这些测得的数据按不同的时间尺度进行分析发现，数据网络 的流量在很多时间尺度下都具有突发性，即是说，突发的持续时间没有一个本质 的长度，反过来说明在不同的时间尺度下( 从毫秒到分钟到小时) 都存在相似的流 量突发。这就与短相关流量模型相悖，短相关流量模型认为在大的时间尺度下流 量将被平滑。实验也表明根据短相关流量模型对数据网络的性能评价对网络资源 进行管理，结果要么过于乐观要么糟糕之极。 一般说来，网络性能评价方面的研究大致可以分为两类。第一类是基于测量 的研究。通过测量设备或一定的测量程序直接计算机网络测得各项性能指标或与 之密切相关的度量，然后有它们经过数据处理，提炼出相应的性能指标。这是最 直接也是最基本的方法，其他方法都是在此基础上发展而来。但基于测量研究的 也有很大的局限性，测量只能针对已经存在的系统进行，而且比较费时间。测量 的结果通常都有待加工处理。测量方法和测量方案是影响测量研究有效性的关 键。 另一类是模型研究。模型研究首先对待评价的对象抽象出一个模型，设置相 应的参数表征系统的性能指标从而进行研究。模型中参数的设置通常依赖于测量 研究而获得。与测量研究相比，模型研究的优点表现在不但可以对已有的系统进 行，而且可以对尚未存在的系统进行性能预测，这对于网络规划是非常重要的。 第1 章绪论 模型研究的关键在于建立的模型是否能有效反应实际情况。由于网络仿真工具的 功能越来越强大，模型研究因为其具备方便性，开销小，通用性好等优点被越来 越多的研究人员所采用。 要充分发挥模型研究的优点，就要尽可能让模型与真实网络环境相吻合。网 络流量模型是网络仿真研究中非常重要的方面，要评价一个网络的性能，比如吞 吐量，延迟，带宽等就必须产生与实际情况相符和的网络流量。 1 2 2 自相似数据网络传输的拥塞控制 早在1 9 8 6 年，v a nj a c o b s o n 就在l b l 和u c b 之间大学大约四百码的链路 上观察到拥塞崩溃的现象，应用得到的网络吞吐从3 2 k b p s 急剧下降到4 0 b p s ， 并且网络和协议都处于忙碌状态【】。通过捕获网络分组，发现由于网络负载陡然 增大，造成数据在网络中继或端接点的缓冲溢出，丢失的分组导致数据的重发， 进一步恶化网络拥塞。 拥塞产生的真正原因在于网络负载超过网络的处理能力。如果数据传送仅仅 发生在局域网内，那么拥塞现象是很少出现的。因为网络一般都在发送方和接受 方之间进行了流量控制。但是在广域网中，尽管发送方和接受方之间也进行了流 量控制，拥塞还是容易发生，而且这种拥塞往往都是网络内部拥塞，跟发送方和 接收方本身的处理能力无关。 既然网络拥塞是无法避免的，那么就必须采取积极的策略区控制和尽量避免 拥塞，把拥塞发生的可能性降至最低，即使在发生拥塞后也能恢复到正常状态， 同时拥塞控制要尽可能保持较高的网络效率。 网络传输的自相似特征使得流量突发在大范围内存在，给网络拥塞控制带了 极大的挑战，但是也因为自相似传输的长相关特征，使得网络流量预测成为可能， 也给拥塞控制提供了新方法。 1 3 本课题的主要研究内容 自相似网络传输的网络拥塞控制是一个同时具备很好的理论价值和实用价 值的研究课题。网络传输的自相似特征的发现使网络设计、分析、管理与控制等 各个方面都发生了根本的变化。研究人员对自相似的网络业务开展了大量的研 究，也得到了不少结论，并且这一工作仍然是目前网络流量工程领域研究的热点。 而拥塞控制的研究开始得就更早了，但主要是基于对网络传输短相关的传统认识 的研究。至于结合网络传输的自相似特征与基于网络中间节点的拥塞控制的研 究，在目前来说，还没有令人振奋的成果。 本文的主要研究内容是：网络传输自相似特征的识别以及自相似程度大小计 算，自相似业务模型，自相似传输背景下网络中间节点采用两种不同队列管理机 北京工业大学工学硕士学位论文 制对网络性能的影响，以及自相似传输背景下网络拥塞控制算法的改进。 第2 章自相似过程及其参数估计 第2 章自相似过程及其参数估计 2 1 自相似过程数学定义 设z = ( 置：f = o ，1 ，2 ) 是一个离散时间弱平稳随机过程1 4 1 ，即，其均值为 常数= 研置】，方差0 2 = 研( z 一) 2 】 。o ，并且自相关函数( 七) 仅与k 有关而 与t 无关，即 ( 七) = r ( 七) ；e 【( x ，一) ( x t + i 一) 】，e 【( j 。一) 2 】( 】 = 0 , 1 ，2 ，)( 2 1 ) 对柳= 1 ，2 3 设： 矽= ( l + w + + ) 肌- ，2 1 ；2 ， ( 2 2 ) 则聚合过程x ”) = ( x 7 ：，= 0 , 1 , 2 ，) 是一个新的平稳随机过程，其中r f l 称为聚合 粒度。其方差和自相关函数分别记为圪和，伽( | ) 。 如果当k - - o o ，有r ( _ j ) 寸k 呻，0 p l 有相同 的相关结构；且自相似指数h = 1 - ( 3 2 ) ；如果坍一m 时，r ( k ) - - ，则称 是渐进二阶自相似的( a s y m p t o t i c a l l ys e c o n d o r d e rs e l f - s i m i l a r ) 。 自相似过程主要有如下性质【1 5 】： ( 1 ) 方差慢衰减：聚合序列的方差衰减速度慢于聚合粒度的倒数的衰减速度，即当 m o o 时： v a r 趔” 一e l m 一“ ( 2 3 ) 其中c l 为常数，0 p 。 1 g h = l 一( 1 3 l 2 ) 。 ( 2 ) 长相关性：如果平稳随机过程 的自相关函数不可和，即乙= m 那么称 为长相关过程；如果二 k 一6o 1 3 1 ，有二= m ，因此自相似过程具有长相关特征。 ( 3 ) h u r s t 效应：自相似特征通过r s 统计量的对数图的斜率p ：，0 5 p ： l 来表征。 对样本均值p = e 蜀) ，样本方差s 2 ( 拧) = e ( 置一“) 2 给定的序列 五，以 ，自 相似指数h 由r i s 统计r ( n ) i s ( n ) 给出，其中 跗，= 一 窑c 五m s 一) - 血n ；| ；瞄m 0 ， s ( 胛) = e ( e d 2 ( 2 5 有 e 别引z 一删棚“ 其中c 为一正常数 ( 4 ) l f 噪声：频谱密度( 九；日) 在原点附近遵循幂指数法则，即： ，( 九；岛九，九 0 ( 2 7 ) 其中6 为正常数，且h = ( 1 - p ，) 2 。 2 2h u r s t 指数估计方法 h u r s t 指数，又称自相似参数，它是自相似程度的一个重要度量，是描述自 相似特性的唯一参数。更确切地说，h 是统计现象持续性的度量，是随机过程长 相关的一个度量，h 的取值范围是【o 5 ，l 】，h = 0 5 表示没有自相似，h 的值越接 近l ，持续性或长范围相关的程度就越大，过程的自相似程度越耐15 1 。本节从自 相似过程的性质出发，给出几种常用的h u r s t 指数计算方法。 2 2 1 方差时间描点法 本章第一节里，我们给出了自相似过程的数学性质，由性质( 1 ) ，对式( 2 3 ) 两边取对数，得到 三口g ( v 盯 雹帕 ) 专邛。l o g r a + l o g q ( 2 - 8 ) 可以看到自相似过程的方差时间点在对数平面上将落到一条斜率为一n 直线上， 并且h u r s t 指数h = l 一( 臣2 ) 。因此得到方差时间描点法求h u r s t 指数算法如下 1 2 9 1 8 1 ： ( 1 ) 对原始时间序列按粒度m 进行聚合：将原始时间序列x = ( 五：r = l ，2 ，n ) 分成不重叠的块x ( ”) = ( j 9 ：k = 1 ，2 ，n m ) ，每块大小为m ，并且计算每块的 均值露： 冠。= 土( j + j 乞+ l + + r h i ) ( 2 ) 计算x ( ”的样本方差哳( x 佃) ： v a r ( x ( _ ) = 万l 鬲n 备l m ( 冠一j ) 2 ，其中j = 万1 善n 墨 ( 3 ) 对不同的m ，重复( 1 ) ( 2 ) ，得到一系列( 砌蹦佃，r a ) 点对； ( 4 ) 对( 砌崩，脚) 分别求对数，并进行一元线性回归，回归曲线的斜率为届： 6 - 第2 章自相似过程及其参数估计 i i 屈= 2 h 一2 ，一1 a 0 要注意的细节：假设肌和都很大，并k m ，因此每个块很大，块数也很 多，使计算结果不致偏差太大；在第二步计算砌，( 石佃) 时，通常不将平方括号 展开，避免程序执行时因为精度损失导致哳( x 佃) 为负数。 2 2 2 l v s 分析法 由自相似过程的数学性质( 2 ) ，对式( 2 6 ) 作对数化处理，有 工啦【器卜蚍栅一，o s 叫“ 亿 可以看到自相似过程的g ( n ) l s ( n ) 的对数图将是一条斜率为h 的直线。因此r s 分析分析法计算h u r s t 指数步骤如下1 1 7 1 1 1 3 】： ( 1 ) 将序列x = 丑：七= l ，n 分成置个不重叠的块，每块大小为n = n k ，用 x 表示： x = 五：，= 1 ，k ) ( 2 ) 计算蜀的均值, i l 方差： 暑= ( 。砭“+ + 。) 玎； 跚2 嘲2 去荟( 耳扩z ) 2 ( 3 ) 计算尺( ，) ： 足( f ) ：m 旺f o ，窆( 蜀。，一冠) 1 一曲 o ，主( 五。，一暑) 1 l l jt t - 1j 计算e ( 器j ： e ( 器r 套等 ( 5 ) 增大拧，重复( 1 ) ，( 2 ) ，( 3 ) ，( 4 ) 得到点对集( e ( 月( 疗) s ( 功) ，以) ； ( 6 ) 对( 5 ) 用求得的点对求对数，并用一元线性回归曲线拟合，得到的直线的斜率 即为所求时间序列的自相似指数h 。 2 2 3 周期图法 由于长相关序列的功率谱密度函数在原点附近遵循幂指数法则，所以可以利 用周期图方法来计算长相关序列的参数。假设离散时间序列 x = x ( 力：n = o ，1 ， 均值为牙 自相关函数为，( 七) ，功率谱 苎奎三：! ! ：奎兰三兰2 圭兰竺肇圣! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! 厂( d = 万1 乙。m 一，( 七) c 。s ( 舰) ，当a 寸。时，功率谱有如下形式( 1 厂一n o i s e ) ： ，吼1 。2 ” ( 2 1 0 ) 其中g 和h 为常数，并且h ( 0 5 ，1 ) 。 定义 f ( 且) = f f ( o ) d o ( 2 11 ) 日 ( d = 等掣i m l 姒) 其中： 无= 2 9 i n ，= 击静叫2“2 赤j 善以咖埘i 芦( a ) 是区间( o ，棚上离散采样n 的平均周期酬2 。】i l 。l 。 m = 【巩2 t o 】，在一定的条件下【1 6 】，有： 当吉+ 等吡n - - + o 时 ! 业斗l ，( ) 将式( 2 1 0 ) 代入f ( 0 ) 定义，当钆寸0 ，有： f ( 。) r 甜。拈夏南吼2 。， g a 式( 2 1 5 ) 有： 氚o ) 赤吼2 。堋 和 ( 九) ( 0 ) 一卅当o g l 因此，对式( 2 1 8 ) 两边求对数，得到h 的估计值： 合1 。g 声( 巩) 芦( 缸) 拈卜面r 一 同样g 的估计值 a ：2 ( 1 一疗) ( 0 ) 妒川 ( 2 1 2 ) ( 2 1 3 ) ( 2 1 4 ) 对给定的a = 0 ，并设 ( 2 1 5 ) ( 2 1 6 ) r 2 1 7 ) ( 2 1 8 ) ( 2 1 9 ) ( 2 2 0 ) 至：耋! 望! ! 兰至墨茎：鍪竺兰 2 2 4 小波分析法 由自相似过程的长相关性质，即如果广义平稳过程z = 五9o 9 k 具有长相 关性质，则协方差函数l ( 七) 具有如下形式 扎( 七) c 7 k - ( 2 - 2 ) , k 斗 ( 2 2 1 ) 等价的频谱表达方式为： s p e c x ( v ) e l v 1 ”，y 寸0 ( 2 2 2 ) 其中c ，= 二。厂( 2 日一1 ) s i n ( x 一，) ，为伽玛函数。为介绍小波分析方法，下面 先介绍多分辨分析和离散小波变换 2 4 1 1 3 0 1 。 1 多分辨分析( m r a ) 和离散小波变换( d w t ) 一个多分辨分析( m u l t i r e s o l u t i o na n a l y s i s ，m r a ) 包含一个嵌套字空间的集 合 巧) 。：，且满足以下条件： a ) 逼近性：n 巧= o ，u y = r ( 皿) ，x 表示集合工的闭包； j e ；，t =f b ) 单调性：巧( 2 2 c ) 伸缩性：，( f ) f ( 2 t ) d ) r i e s z 基存在性：存在尺度函数平。( ，) ，使 q - k ) ，七z ) 构成空间v o 的 一个r i e s z 基。同理，尺度平移函数 甲肚( t ) = 2 - m 甲。( 2 7 ，一_ | ) ，i z 构成空间巧 的一个r i e s z 基。 对信号x 进行多分辨分析实际上是将z 连续投影到每个子空间巧获取近似 表示： a p p x ，( t ) = ( x ) o ) - e a x ( j ，七) 甲”( f ) c _ 2 3 ) 又巧c 巧峭是比q 配蚂- 更“粗糙”的近似表示，因此，m r a 的基本思想 就在于研究信号从粗近似表示到细近似表示时的信息损失，即细节d ) ( 小波 系数) 为相邻分辨率下的近似表示的差嘭o ) = q 船一( ，) 一a p p x ，( t ) m r a 表明 细节信号d 胎) 可以通过将信号x 投影到一系列的子空间( 小波空间) 获得； m r a 还表明可以从尺度函数p 。( r ) 导出小波函数g o ，使得 竹，i ( t ) = 2 - j 2 ( 2 t - k ) ，七z 构成空间的一个r i e s z 基 嘭( ，) = ( x ) ( f ) = 以【，d 盯。 ( 2 2 4 ) 多分辨分析实际上是通过不同分辨率下的细节信息和低分辨率下的近似表示一 起信号j ，即 x ( f ) = a p p x s ( t ) + d j ( t ) ( 2 2 5 ) = ( j ，j i ) + 以u ，k ) w j j ( f ) m r a 表明小波函数必须满足( t ) d t = 0 且其傅立叶变化遵循 陬( y h ，y 号0 其中n 为正整数，称为小波消失矩。 给定尺度函数和小波函数，离散小波变换( d i s c r e t ew a v e l e tt r a n s f o r m ， d w t ) 是一个映射r ( r ) 一，2 ( z ) ， z ( ，) 一 ( 以七) ，k e z ， d x ( j ，n - ，= l ，j , k e z 2 h u r s t 指数h 的小波估计方法 小波系数i 叱( _ ，k ) 1 2 表征信号x 在时刻2 j t 和频率2 叫v 0 处的能量，近似频谱 估计 一f f e e x ( 2 - j v o ) - l 。，e 。l 以u ，硝 ( 2 2 6 ) 其中丹，为在分辨率，下小波系数的个数一= 2 n ，n 为信号集的大小因此 j 面_ ( v ) 表征信号x 在频率v 附近给定带宽内的能量。实际上，如果z 为广义平 稳过程，那么有 e ( s ；砖( 2 ，v o ) ) = 扣e c x 0 0 2 7 1 ( 2 v ) j 2 咖 ( 2 2 7 ) 其中为小波函数的傅立叶变换考虑到长相关过程频谱表达式 掣勺( y ) c ，“，v - - + o 。有 e ( s p 唧( 2 叫v o ) l = 勺1 2 一叮。2 棚j 7 叫( t - 2 v ) i ( 力扣 ( 2 2 8 ) = s p e c x ( 2 叫v o ) ”“州( i - 2 h ) i p o 0 1 2 d v 从上式可以得到h u r s t 指数的计算方法： 陋p e c x ( 2 - = 上d 9 2 忙弘洲ij = ( 2 乱町+ ； ( 2 2 9 ) 其中；= l o g ：( c ，j 1 v i ( 1 2 聊i ( v ) 1 2 咖) ，假设积分j 1 v | ( 1 - 2 叫i ( v ) 1 2 西 m 。 对分辨率，五】之间进行一元加权线性回归，可以得到h 的估计值： 第2 章白相似过程及其参数估计 岔：三 2 壹邑觑一壹_ _ ，窆邑协1 鳓s,芝s,j-s,xks-s,+1 窆 。 一 1i j _ 卜h，l ( 2 3 0 ) 其中协2 击莩阮( _ ，七) 1 2 ，邑2 ( 疗l i l 2 2 ) 2 川 综上所述，h u r s t 参数小波估计法步骤如下： ( 1 ) 小波分解： 对时间序列进行离散小波变换得到小波系数以( ，； ( 2 ) 小波系数方差估计： 计算分辨率，下的能量伽r g y s 。去军i 以( ，七) 1 2 ( 3 ) 对数图分析： 对能量做对数处理乃= l 0 9 2 ( p n e r 秒j ) ( 4 ) 参数估计： 对( 乃，_ ，) 做一元加权线性回归，得到直线的斜率s 却忙，则n = ( s l o p e + 1 ) 2 。 2 2 5w h i t t l e1 古计法 w h i t t l e 估计法1 刀是在周期图基础上的定量估计法。如果己知随机过程 z ) 的功率谱密度为f ( x ，日) ，其中h 为需要估计的参数，令，( ”表示随机过程的功 率谱估计， 删= 丽l 陲nv 批1 2 ， 定义函数 q ( = 工f 。m i ( 7 ，0 h ) d 九。 ( 2 3 2 ) w h i t t l e 估计的结果为使q ( h 1 为最小的h 值。 w h i t t l e 估计的方差可以由式( 2 3 3 ) z 1 0 ： 冉。石 ( 产h 一 图2 - 1 为图形化的w h i t t l e 估计，从图中可以看出q ( h ) 的最小值在h = o 8 处，因 此h 的估计信约为0 8 。 北京工业大学工学硕士学位论文 图2 - 1自相似过程的w h i t t l e 估计 f i g u r e2 - 1w h i t t l ee s t i m a t o ro f s e l f - s i m i l a r i t y 与前几种图形化或半图形化估计法不同，w 1 1 i t t l e 估计法是量化的估计法，它不 仅可以定量地估计h 参数的值，而且可以估计出它的方差。w h i t t l e 估计法的缺 点是更大的运算量，并且需要预先知道随机过程的功率谱密度函数的形式。如果 功率谱密度函数形式不知道，w 1 1 i t t l e 估计就会严重偏移真实值。另外，w h i t t l e 估计法不能用来判断随机过程是否具有自相似性。因此实际运用中，先用图形化 方法判断随机过程具有自相似性，然后用w h i t t l e 估计法估计h 的值。 2 2 6h o u s s a i n - j o l m 方法 对于精确二阶自相似过程x = 五，以 ，其：自协方差函数 y ( 七) = e ( 置+ 。一e 墨+ 。) ( 置一e 一) ( 2 3 4 ) 方差为 盯2 = y ( o ) = e ( 五一瓯) 2 ( 2 3 5 ) 自相关函数 m ) = 等= 如+ 1 1 ”一2 1 k l t m + 卜1 1 2 ”) ，o 日 f ) t - at 斗0 0 ，1 0 ，0 5 日 1 ，其中 x n ( o ，1 ) ，有如下性质： ( 1 ) e 【( f ) 】= o ，陷“( f ) 】= f 2 8 ； ( 2 ) f b m 过程概率密度分布： 矗似，) 2 丽1 e 删” ( 3 4 ) ( 3 ) 具有平稳增量并且 e b n ( t ) o ) 】_ o ( 3 5 ) 踟【( f ) 一( s ) 】= | f - s 1 2 “ ( 3 6 ) 第3 章自相似网络传输模型 ( 4 ) 自相关系数 ( f ，s ) = 研o ) o ) 】= i 1 ( f 2 ”+ j 2 ”- i , - 4 2 ”) 对于聚合过程以( 讲) 不难验证： 研( 讲) 】_ e b x ( t ) 】 陆【( 讲) 】= 口2 ”陆【昂( f ) 】 r b h ( a t ，a s ) = a l hr 8 。 ，d 可见巩( 讲) 具有自相似性。 ( 3 7 ) ( 3 8 ) ( 3 9 ) ( 3 1 0 ) 征买际嘲络模拟中，要严生精确的f b m 序列是不可行的，因为需要大量c p u 时间。当前常用的近似f b m 序列生成算法是中点随机移位法( m d o mm i d p o i n t d i s p l a c e m e n t , r m d ) 口刀。假设我们要产生时间间隔【o ，r 】上的f b m 序列。r m d 算法的基本思想是：递归地划分间隔【o ，t 】，根据端点的值来产生中点的值，这 样生成的中点值的序列即为近似f b m 序列。如果x 是f b m 的，那么由端点z ( 和石 构造的中点值x ( 旦产生的中点偏移x ( 旦一半与整个间 隔【口，6 】上的增量x ( 6 ) 一z ( 口) 不相关。 在这里我们给出r m d 算法的迭代实现形式。区间【o ，1 】上指定h u r s t 指数h 的f b m 序列迭代形式为： 初始化：研o 】= 0 ；x 【1 】= g l 迭代1 ：x 1 2 ：掣+ 吗 迭代2 ：x 1 4 1 ：x 0 + _ x 一 1 2 + r 2 g s ； x 3 4 ：x 1 = 2 一+ x 1 + ，2 q 迭代3 ：x 1 s ：x o _ + - x 一1 4 + ，3 g ， x 3 8 ：x 1 4 i + x 一1 2 + ，3 g 6 x s s ：x 1 2 i + x 一 3 1 4 + ，3 g 7 ， x 7 8 ：x 3 4 _ = _ + 一x 1 + r 3 g s 其中g 为正态分布的随机变量，r 为缩放因子且，= 1 2 “，0 、 = 、= 、一、f = 等 a c t i o n s 由许多a w k 指令所构成，而a w k 的指令与c 语言中的指令非常类似。 1 0 指令：p r i n t o ，p f i n f f o ，g e t l i n e 等 流程控制指令：i f 0 e l s e ，w h i l e o 等 在a w k 程序的流程中，先判断p a t t e m 的结果，若为真( t r u e ) ，则执行相对应的 a c t i o n s ；若为假( f a l s e ) 贝l j 不执行相应的a c t i o n s ；若是处理过程没有p a t t e m , a w k 无条 件执行a c t i o n s a w k 工作流程：执行a w k 时，它会反复运行下列步骤： ( 1 ) 自动从指定的文件中读取一行数据记录 ( 2 ) 自动更新相关的内建变量值 ( 3 ) 逐次执行程序中所有的p a t t e r n a c t i o n s 指令 ( 4 ) 当执行完程序中所有的p a t t e m a e t i o n s 时，若文件中还有未读取 的记录则反复执行步骤( 1 ) 到( 4 ) 。 a w k 会自动重复上述四个步骤，所以程序员不需在程序中写循环。 北京工业大学工学硕士学位论文 4 1 4g n u p i o t 工具 g n u p l o t 是一个命令驱动的交互式绘图程序( c o m m a n d - d r i v e ni n t e r a c t i v e f u n c t i o np l o t t i n gp r o g r a m ) i x 刀。g n u p l o t 的功能是吧数据资料和数学函数转换成容 易观察的平面或立体的图形，帮助研究者进行数据分析。因此g n u p l o t 并不是一 般常见的美工绘图软件，它最适合的是在科学研究的过程中，帮助研究人员完成 数据资料绘制与理论模型比较等机械的工作，来加速研究的进行。 g n u p l o t 基本环境参数： 1 座标轴 坐标轴的绘图参数见表4 1 。 表4 - 1g n u p l o t 坐标轴绘图参数 功能绘图参数名称 标点设定 x t i c sv “c 网格设定鲥d 座标显示方式l o g s c a l e 显示范围设定 a u t o s c a l e ，x r a n g e ，y r a n g e 座标轴显示与否 x z e r o a x i s ，y z