（计算机应用技术专业论文）internet环境下遥操作机器人系统网络优化研究.pdf

华北电力人学硕十学位论文 摘要 本论文围绕i n t e r n e t 下遥操作机器人系统的网络优化进行研究，主要研究内 容为网络数据传输。首先，针对网络回路往返时延( r t t ) 的自相似性，提出基于 自适应滤波的r t t 预测算法；其次，通过r t t 预测算法设置t c p 协议的超时定时器， 改进t c p 协议；最后，根据遥操作机器人系统网络性能指标需求，在遥操作机器人 模拟控制系统中，模拟遥操作系统数据传输过程。在论文研究的各个阶段，通过n s 2 模拟验证相应研究内容的有效性。通过模拟实验及应用系统的验证，基于自适应滤 波的r t t 预测算法及在此基础上改进的t c p 协议有着良好的性能，从传输层角度上 为i n t e r n e t 下遥操作机器人系统的网络优化提供解决办法。 关键词：自适应滤波，r t t 预测，传输协议，网络优化，遥操作机器人系统 a b s t r a c t t h i sp a p e rc o n c e n t r a t e so nn e t w o r ko p t i m i z a t i o nf o ri n t e r n e t - b a s e dt e l e r o b o t i c s ， f o c u s i n go nt h ep h a s eo fd a t at r a n s m i s s i o n f i r s t ，a r o u s e db yt h es e l 仁s i m i l a r i t yo fr t t , w ep r o p o s ea na l g o r i t h mo fr o u n d t r i pt i m e ( r t t ) e s t i m a t i o nb a s e do na d a p t i v ef i l t e r i n g t h e n ，w ee m b e dt h ea l g o r i t h mi n t ot h ei m p l e m e n to ft i m e o u tt i m e ro ft c pt oi m p r o v ei t s p e r f o r m a n c e l a s t ，o nt h eb a s i so ft h en e t w o r ki n d i c a t o ro fi n t e r n e t - b a s e dt e l e r o b o t i c s ， w es i m u l a t et h ep r o c e s so fd a t at r a n s m i s s i o no fi n t e r n e t b a s e dt e l e r o b o t i c sb yo u r c o n t r o ls y s t e m d u r i n ga l lp h a s e so fo u rr e s e a r c h ，w ev a l i d a t et h ee f f e c t i v e n e s sb y s i m u l a t i o ne x p e r i m e n t s t h r o u g ht h es i m u l a t i o ne x p e r i m e n t sa n dt h er e a lc o n t r o ls y s t e m ， w ec a nd r a wac o n c l u s i o nt h a to u ra l g o r i t h ma n dt h ei m p r o v e dp r o t o c o ls h o wap e r f e c t p e r f o r m a n c e t h u s ，t h i sr e s e a r c hp r o v i d e sag o o ds o l u t i o nf o rn e t w o r ko p t i m i z a t i o no f i n t e r n e t b a s e dt e l e r o b o t i c sf r o mt h ea s p e c to ft r a n s m i s s i o nl a y e r n az h a o ( c o m p u t e r a p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f c h a n g a nl i u k e yw o r d s ：a d a p t i v ef i l t e r i n g ，t h ee s t i m a t i o no fr t t , t r a n s m i s s i o np r o t o c o l ，n e t w o r k o p t i m i z a t i o n ，i n t e r n e t - b a s e dt e l e r o b o t i c s i 华北电力大学硕十学位论文 目录 摘要i a b s t r a c t i 第一章引言1 1 1 问题的提出及研究意义1 1 2 国内外研究现状l 1 2 1 控制领域研究1 1 2 2 网络研究2 1 3 本文的研究内容及主要工作2 1 4 论文组织结构3 第二章网络数据传输时延及其预测方法研究4 2 1 网络时延构成及预测方法分析4 2 1 1 网络时延构成4 2 1 2 时延预测方法5 2 2 自适应滤波算法分析一8 2 2 1a f 算法模型9 2 2 2a f 算法与r 1 v r 预测1 2 2 3 基于自适应滤波算法的r 1 r t 预测模拟实验1 3 2 3 1 实验平台简介13 2 3 2 网络拓扑及实验环境1 4 2 3 3 实验分析及结论1 4 2 4 本章小结l7 第三章基于自适应滤波的新型传输协议研究1 8 3 1t c p 协议研究1 8 3 1 1 超时重传机制1 8 3 1 2 慢速启动及拥塞避让机制1 9 3 1 3 主要t c p 算法分析2 0 3 2 新型传输控制协议开发要点分析2 0 3 2 1 传输质量一2l 3 2 2 公平性2 1 3 2 3 有效性2 2 3 3 基于自适应滤波的数据传输协议实现2 3 华北电力火学硕十学位论文 3 3 1 自适应滤波算法2 3 3 3 2a f i h tt c p 协议2 4 3 3 3 丢包控制2 5 3 4 新型传输协议验证实验2 6 3 4 1 自适应滤波算法参数选定2 6 3 4 2 多点对多点2 6 3 4 3 单点对单点2 7 3 4 4 不同数据流争用带宽的情况2 8 3 5 本章小结2 9 第四章a f r t tt c p 协议在i n t e m e t 环境下遥操作机器人系统中的应用3 0 4 1 遥操作系统对于网络因素的需求分析3 0 4 2 系统设计及实现3 2 4 2 1 系统总体结构3 2 4 2 2 系统硬件构成3 2 4 2 3 系统实现关键技术3 3 4 2 4 系统软件实现3 4 4 3 简化模拟实验3 5 4 4 本章小结3 6 第五章总结及展望3 8 5 1 工作总结3 8 5 2 下一步工作3 9 参考文献4 0 致谢4 3 在学期间发表的学术论文和参加科研情况4 4 华北电力大学硕十学位论文 1 1 问题的提出及研究意义 第一章引言 数据传输是遥操作机器人系统的一个非常重要的组成部分，从通信领域来说， 分为无线和有线数据传输。随着i n t e m e t 的出现及广泛应用，通过i n t e m e t 进行数据 传输，实现远距离遥控机器人越来越成为一个重要研究方向。基于i n t e m e t 的遥操 作机器人系统，一方面得益于网络传输的显著优势，网络资源廉价、普及范围广、 所需硬件少；另一方面，i n t e m e t 上数据流具有多样性，遥操作机器人系统必需的实 时性特点所需要的高优先级必然不能达到。同时，i n t e m e t 本身固有的特点，引起了 遥操作控制过程中的随机时延及延迟抖动，遥操作机器人系统的可控性、稳定性及 透明度都受到负面影响。具体说来，问题的根源主要集中在网络时延和数据可靠性 两大问题上。其中，数据可靠性又与网络时延有着密不可分的关系。 目前，对于遥操作机器人系统网络时延问题应对策略的研究主要集中在控制理 论领域，如基于电路网络理论的无源控制法则、基于现代控制理论的控制算法和虚 拟现实技术的模型修正法等。其共同的特点是把网络看作一个不可知( 黑盒子) 和 不可控的对象，在控制领域寻找应对方法。但是，科学来讲，网络虽然具有相当显 著的不确定性，但它是一个可控、可预测的对象。因而，从网络体系本身出发，从 遥操作机器人系统与网络的互动需求出发，提出满足遥操作机器人系统需求的网络 优化和适应性方法，从而与控制领域的研究成果互补，通过跨学科的努力，从根本 上解决i n t e r n e t 环境下对遥操作机器人系统的影响和限制，缩短遥操作机器人系统 理论与实用化的距离，为遥操作机器人技术提供更加广阔的应用空间，成为一个迫 切需要解决的问题。 1 2 国内外研究现状 1 2 1 控制领域研究 在很长一段时间，关于遥操作机器人系统的网络时延问题集中在控制理论领 域，早在6 0 年代f e r r e l l 就指出时间延迟的存在会使远程机器人工作不稳定。这种 不稳定性可以从以下几个角度分析： 在古典控制论奈奎斯特稳定性分析中，将复平面上开环频率特性曲线不能包围 1 点作为系统稳定的条件，并进一步从工程角度出发，要求一个系统不但要做到稳 定，还应该有相当的稳定裕量才可使用。然而一个系统的参数的不确定性，控制模 1 华北电力大学硕七学位论文 型的不合理的简化，却会使系统在某些情况下失稳，网络机器人控制中典型的就是 延时的不确定性所带来的系统不稳定，所以对网络机器人控制问题的研究往往要考 虑系统的稳定性和鲁棒性( r o b u s t n e s s ) ，即“是否稳定”和“稳定裕量 。 从能量角度分析，遥操作系统要想保持稳定，其输入能量必须大于输出能量， 而通讯系统的存在会很容易的违反这一要求。 从负反馈角度分析：负反馈是实现控制的基本方法，但负反馈并不能保证系统 的稳定性，设计不好的负反馈系统的被控制量也会出现震荡的情况，即不稳定。一 个闭环系统如果其闭环增益大于一，其半个工作周期等于时间延迟值，则系统将处 于正反馈而非负反馈，此频率的能量将连续加入系统而导致系统的不稳定。 这些问题的应对策略有基于电路理论的无源控制法则、基于现代控制理论的控 制算法和虚拟现实技术的模型修正法等，这些方法策略的共同点是：把网络看作一 个不可知( 黑盒子) 和不可控的对象，在控制领域寻找应对方法。 1 2 。2 网络研究 基于i n t e r n e t 的遥操作机器人系统网络研究主要集中在网络数据传输时延、传 输方法、传输可靠性、网络结构这几个方面。其中，以网络时延研究及以此为基础 研究新型数据传输协议最为广泛，大体分为以下几个研究方向： ( 1 ) 研究时延特点，给出时延估测模型，并以此模型为基础研究整个遥操作 机器人系统的控制模型； ( 2 ) 大量实验测试，分析时延呈现出来的统计特性，预测其可能遵循的函数 规律； ( 3 ) 重点分析控制信息的传输特性，采用i 汀p l 玎c p 舢d p 等网络协议来解决 问题。 1 3 本文的研究内容及主要工作 通过目前遥操作机器人系统的发展现状可以发现，对于一般的遥操作机器人系 统，带宽虽然有限，但通常还是能够得到保证，所以时延也几乎是常数，基于i n t e m e t 的遥操作机器人系统则有所不同，其传输时延则是不断变化的。遥操作机器人系统 是时延敏感的，且实时性要求很高，因而i n t e m e t 提供的这些通信条件给遥操作系 统的开发带来很大困难，传输中的时延、时延抖动和不能保证的带宽将引发不稳定 的问题，如果不适当地进行控制就会导致系统性能极大下降。 基于上述问题，本文着重从网络传输层进行研究，对目前各种遥操作机器人系 统对网络各项性能指标的需求进行分析；重点分析网络时延的特点及其对网络数据 2 华北电力大学硕十学位论文 传输的特殊性；引入自动化控制领域的自适应滤波算法，建立网络时延预测分析模 型，分别针对点对点传输、集群数据传输两种情况进行网络模拟，验证自适应滤波 算法的有效性；嵌入自适应滤波算法，改进t c p 协议的i 汀t 更新算法，建立适应 于遥操作机器人系统实时性的新型传输协议；在n s 2 网络模拟环境下，使用新型传 输协议，建立网络拓扑图，模拟遥操作机器人系统的数据传输过程，验证新型协议 的有效性；开发应用系统，使用新型传输协议作为系统底层数据传输协议，从实用 系统角度验证协议的有效性。 1 4 论文组织结构 本文共分为五章，具体安排如下： 第一章引言部分，主要分析本论文课题的研究背景及研究意义，国内外对于 相关问题的研究情况，本论文研究内容及相关工作。 第二章基于自适应滤波的网络回路往返时延( 1 m ) 研究，分析当前网络时延 研究成果及相关方法，分析r t t 的统计特性；从其特性出发，提出基于自适应滤波 算法的r t t 预测算法模型；基于该模型建立实验拓扑结构，模拟两大数据传输场景， 分别验证自适应滤波算法的有效性。 第三章研究数据传输协议实现过程，分析t c p 协议内在三大机制：超时重传、 慢启动和拥塞避让，在此基础上，总结开发新型数据传输协议需要达到的要点；基 于上述模拟实验的有效结果及对协议的功能需求，对n s 2 中t c p 协议进行二次开 发，重新构造t c p 协议中超时重传定时器的定时方法。 第四章分析i n t e r n e t 环境下遥操作机器人系统对于网络因素的需求；介绍基于 a f r t tt c p 协议的遥操作机器人控制系统的实现细节；分析具体数据传输场景， 针对遥操作机器人系统的数据传输特点，模拟其数据包发送状况，通过改进的协议 进行数据报发送并跟踪，分析实验结果，验证改进后协议的有效性。 第五章总结及展望，对本文的研究工作进行总结，同时对将来的研究工作做 出展望。 3 华北电力大学硕士学位论文 第二章网络数据传输时延及其预测方法研究 2 1 网络时延构成及预测方法分析 2 1 1 网络时延构成 在基于i n t e r n e t 的遥操作机器人系统中，时延对于其数据传输质量有着至关重 要的作用。所谓链路往返时间r t t ( r o u n d t r i pt i m e ) ，是指从发送端发送数据开始， 到发送端收到来自接收端的确认( 接收端收到数据后便立即发送确认) ，总共经历 的时间长度，在计算机网络中它也是一个重要的性能指标。由源发送端产生的数据 包通过系列中间的节点寻径到目的，点对点时延就是包在到达目的之前的路径上 所经过的每一“跳 的时延总和。一般地，在互联网路径上的时延由以下几个部分 组成： 设总的时间延迟是t r ，t r = t c + t p + t d + t v ，其中： ( 1 ) 传播时延t c 。信号通过传输介质在两地问的物理传输时间是随着距离的 增大而增大的。在遥操作中，如果远端机器人工作地点是固定的，其时间延迟当然 就是固定的；如果远端机器人是移动机器人( 地面、太空或水下) ，但运动速度较 慢，则也可认为有固定延迟；随着移动机器人运动速度的加快，就要考虑延迟变化 情况下的遥操作了。在网络机器人中，路由选择的不同会使信息沿不同的线路传输， 从而导致信息传输时间的变化，不可预测、不可改变。所谓“网络机器人中时延的 不定性 主要产生于此处。 ( 2 ) 执行时延t p ，包括控制指令的解释、计算、执行时间，现场图像的处理 时间及仿真图像的运行时间等。 ( 3 ) 数据时延t d 。t d = ( d s + d r ) v l 。d s 、d r 是发送回收的数据总量， v l 是传输速率，与介质有关。这一项的存在表明数据传输量和带宽对远程作业非 常重要，减少传输量固然能减小时延，但远端所获取的现场信息就可能不足，但大 的数据量又会导致数据在链路瓶颈处排队时间过长或者队列过长，引起丢包，因此， 高效的数据压缩技术和良好的通讯通道有助与解决这一矛盾。 ( 4 ) 扰动时延t v 。主要指传输中不可预测的扰动，如信息丢失或信息次序的 混乱。 队列时延根据队列缓冲器的大小，网络信息流的密度( i n t e n s i t y ) 和特性会有 很大的差异。因此队列时延实质上决定了互联网上点对点时延的动态特性。 4 华北电力人学硕十学位论文 2 1 2 时延预测方法 到目前为止，涌现了大量关于互联网r t t 预测方法，从总体上大致可以分为两 类：主动式预测算法和被动式预测算法。 ( 1 ) 主动式预测算法 主动式预测算法，从数据包的发送端主动向网络中注入探测数据包并接收从接 收端返回的对探测数据包的反馈a c k s ，如图2 1 所示。r t t 的值就是数据包的发 送时间与反馈数据包的到达时间的差值。主动预测算法本身会影响网络的数据传输 过程，因为它向网络中注入了大量测试数据。 注入数据包 反馈数据包 图2 - i 主动测量示意图 一种常见的主动式i 盯预测定义为心1 ： r t r ( i ) = m i n rt ( p ( i ) ) - s r ( p ( i ) ) ，t o ) 在这项公式中，p 是包的有限序列集，p ( i ) 是p 中的第i 个包，s t 是一个单调增 函数，代表了发送数据包到接收端的时间，r t 是所有响应包的时间戳函数，r t t ( i ) 则表示第i 个探测包的r t t 值口1 。 ( 2 ) 被动式预测算法 被动式预测算法，将网络作为一个可控的对象，设定一个监测中心，随时观测 通过一条链路的网络数据包，并不主动向网络中注入数据。被动式预测算法一般在 网络中的某个关键节点实施，比如网管所在网络节点。在这种情况下则要分析网络 回路是否对称，因而有基于双向路径和单向路径的两类测算方法h 1 。 被动预测算法的主要出发点是研究l 玎t 的分布。目前常见的几类被动式预测算 法有： a ) s a 和s s 算法 j i a n g 和d o v r o l i s 提出两种以t c p 特定阶段为测量基础的方法哺1 。一种是在三 次握手阶段测量，称作s a 方法，适用于所有从发送端( c a l l e r ) 到接收端( c a l l e e ) 5 b ) 时钟潮量 图2 - 3 s s 测量方法示意图 上述方法是基于这样个先决条件：数据包的数量是可以预知的，同时，方法 华北电力人学硕十学位论文 的实现依赖于a c k 信号以及由a c k 信号出发的数据包传送过程。显然，这种方法 复杂不易实现。 出于上述考虑，b r y a nv e a la n dk a n gl i 提出了两种更加简单直接的方法阳】。 第一种方法是使一次会话过程的发送端和接收端数据包中都打上触发该数据 包发送的包的时间戳。在传统的方法里，发送端发送一个数据包到接收端，接收端 返回一个a c k ，发送端再根据这个a c k 信号发送数据。这个传输过程以发送端总 是有足够的等待发送的数据为前提。这样，a c k 数据包的序号由触发它的数据包的 序号决定，因此序号成为区别数据包的标志。但是，如果数据端不发送数据时，a c k 信号的序号就永远不变。如果测试点用t c p 时间戳代替序号来将相关数据包联系起 来将解决上述困境。当然，用时间戳的方式只是将数据包关联起来，而并不是计算 r 1 盯。发送端和接收端都打上最近收到的数据包的时间戳来处理丢包等问题。测试 点记录数据包的到达、反馈的时间来计算i 汀t 。时间戳方法实现细节如图2 4 所示。 图2 - 4 时间戳方法示意图 第二种方法利用了t c p 实现中的一种很重要的机制，即时钟机制 ( s e l f - c l o c k i n g ) ，这种机制使数据流呈现一种块分布状态，如图2 5 所示。 图2 - 5 通过s e l f - c l o c k i n g 确定r 1 t 7 置e叠历葛l皇p，z 华北电力大学硕十学位论文 这种方法并不需要捕获a c k 数据包，因此可以用在对称或非对称的网络结构 中。因为其内部的时钟控制，发送端每次接收到a c k 信号后都会发送更大数量的 数据，接收端接收到数据后又会发送相应数量的a c k 数据包。因此，两个迸发的 数据包流之间的时问可以大略认为等于一个网络回路时延。尽管数据包丢失、争用 带宽可能影响这段时间的大小或者造成多段时间的连续或分离，但是这种情况并不 是每次都会发生。文献 9 中给出了这种方法更为详尽的描述。 c ) 其它研究方法 基于神经网络的时延预测算法n 饥川。p a r l o s 提出了一种通过多步动态神经预报 器测量网络端到端时延及r 1 r t 预测，但是这种方法的影响是双向的n 训。庄亚俊等提 出基于具有动态记忆能力b p 网络的i 盯t 预测方法n 。 y o l a n d a 介绍了一种网络线体层照相技术，它不需要接收端同步，但是仍然受 到时间戳随机性的影响。该方法在标准的一个发端两个接收端的结构中，采用来自 s y n 和s y n a c k 包的测量来计算时延方差，同时该方法的一个重要制约因素是如 何在探测数量和探测速率之间寻找一个折衷点心，。 z h e nz h u 和a l b e r tm k c h e n g 将极值理论引入到i 汀t 的预测中。使用了两种 极值分析方法，分别是块极大值和阈值超过数。前者有助于计算返回级，后者则补 充了与确信度相关的最坏情况r t t 。极值理论成功模拟最坏情况下的i 汀t ，且可用 于其它网络时延预报埋。 除此之外，还有很多其他的关于i 汀t 预测的方法，在这里不再一一列举。 但是，我们发现上述方法都是从具体的数据传输过程来进行r 1 r t 预测( 比如依 靠s y n a c k 信号) ，而没有从宏观角度分析r t t 呈现的特性来进行预测。 2 2 自适应滤波算法分析 研究发现，网络传输过程具有明显的自相关性。自从发现了这一特性后，很多 学者开始研究自相关性对于网络性能所产生的影响。随着研究深入，逐渐发现网络 回路时延同样具有自相关性，并且决定了t c p 的性能。t c p 有两大机制决定其吞吐 量，分别是拥塞避让和慢速启动机制。i m 的自相关性对这两大机制有着至关重要 的影响。 在文献 1 2 中，b o r e l l a 和s i d h u 分析了1 2 个u d p 数据流，发现当将数据从时 白j 序列角度分析时，其存在明显的长相关性。数学上讲，实际传输的相关函数随滞 后时间按幂规律方式衰退，这种特性叫做长相关性。文中指出，网络上传输的数据 时具有迸发性的，也就是说网络终端用户会受到大量的波动性的时间延迟影响。后 续研究陆续指出，网络回路时延的长相关性随着网络负载增加而增加，并且与链路 的丢包率有着密切的关系。这些理论研究对于实时交互系统的设计实现有着很大的 8 华北电力大学硕十学位论文 启发作用。文献 1 3 中明确指出网络回路时延的自相关性是由数据包传输过程中的 排队时延引起的。 自相关是一个检查数据集随机性的通用工具，随机性可以通过取不同的时间间 隔来计算数据的自相关特性来确定。如果是不相关的，这种自相关值对于任何和所 有的时滞分割都应该接近于零。如果是相关的，那么一个或更多的自相关值应该很 明显地为非零值。给定一个时间序列而，x ：，h ，在时滞为1 ，2 ，n 时， 时滞t 的自相关函数可以定义为： c ( , - ) - - e , i 7 ( _ 一；) ( x m 一；) ! 。( 一；) 。，其中；是五，x z ，h 的平均值n 钔。 从图2 - 6 的自相关图可以看到，在图形中自相关从时滞为1 时以大约o 9 2 5 开 始，然后逐渐减少。这种模式显示r t t 时间序列不是不相关的，而是在相邻的和相 近的观测值之间线性相关n 鲥。 2 2 1a f 算法模型 图2 - 6r 1 广r 自相关图 a f 是本论文中对于自适应滤波的简称，全称为a d a p t i v ef i l t e r i n g 。所谓的自适 应滤波，就是利用前一时刻已获得滤波器参数等结果，自动地调节现时刻的滤波器 参数，以适应信号或噪声未知的或随时间变化的统计特性，从而实现最优滤波。自 适应滤波器可以不必要求预先知道信号和噪声的自相关函数，而且在滤波过程中信 号与噪声的自相关函数即使随时间变化它也能自动适应，自动调节到满足最小均方 差的要求。这些都是自适应滤波器的突出优点，因此近年来它被广泛的应用于各种 信号处理中引。 如图2 7 所示维纳滤波器输入输出关系中，输入信号x ( n ) = s ( n ) + v ( n ) ，其中s ( n ) 表示信号的真值，v ( n ) 表示噪声。其输出y ( n ) 等于s ( n ) 的估计值，用；( 以) 表示。维 纳滤波器是具有这样的h ( n ) 或h ( z ) 的滤波器，它能使s ( n ) 与；( 刀) 间的均方误差 研p 2 ( 以) 最小，即e e 2 ( 珂) 】_ 研( s 0 ) 一；( 九) ) 2 】= m i n ，从而达到最好地从噪声中提取信 9 华北电力大学硕士学位论文 号的目的，而自适应滤波器则能自动调节它的h ( n ) 值以满足上述最小均方误差的准 则。 x ( n ) 一h ( n ii + y ( n ) x ( n ) 叫h ( n ) 卜_ 斗y ( n ) 图2 7 维纳滤波器输入输出关系 应用横向结构的f i r 滤波器形式来实现自适应滤波是最常用的一种方法。如果 h ( n ) 长为n ，则从图2 7 可以得到： n - in 少( 刀) = h ( m ) x ( n - m ) = h ，x i m = oi = 1 ( 2 2 ) 这里扛m + 1 ，h f = h ( i 一1 ) ，x i = x ( n - i + 1 ) 。由此可见，输出y ( n ) 是n 个所有 过去各输入的线性加权之和，其加权系数就是 h ，) 。在自适应滤波器中这个加权系 数常用符号w 表示，所希望的输出常用d 表示，并为了书写简化，时间n 用下标j 表示，于是式( 2 2 ) 成为： y ，= w o x , j f = l ( 2 3 ) 由式( 2 3 ) 可见，自适应滤波器可看成是自适应线性组合器，如图2 8 所示。 x l j x 2 j x n j 式( 2 - 3 ) 的向量表示为： d j 图2 8 自适应滤波器示意图 y j = x t j w j = w ：xj 1 0 ( 2 4 ) 华北电力大学硕十学位论文 e j = d l y j = d j w jxl ( 2 5 ) 一般来讲，x l ，x 2 ，x 肿其可以是任意一组输入信号，并不一定要求当工i ，= x ， 时，x 2 = x ，i ，玛，= x 卜2 ，嘞= x j _ + i ，即并不一定要求其各勃是由同一信号 的不同延迟组成延时线抽头形式的所谓横向f i r 结构。但是这种横向f i r 结构是最 常用的一种自适应滤波器的结构形式。 自适应滤波器的要害在于按照p ，及各勤值，通过某种算法寻找研p ；】- m i n 时的各 ，从而可自动地调节各w j 值。在本文中采用的均方差算法是w i d r o w - h o f fl m s 算法。 w i d r o w - h o f f l m s 算法正是求最佳权矢量的一个简单和有效的递推方法，该算 法不需要求相关矩阵，也不涉及矩阵求逆，而是运用最优化的数学算法最陡下降法 ( s t e e p e s td e s c e n tm e t h o d ) 。按照这种方法，下一个权矢量+ l 等于现在的权矢量矿， 加一个正比于梯度v ，的负值的变化量，即 w | 娃= wj 一西i ( 2 6 ) 其中，p 是一个控制稳定性和收敛速度的参量，称之为收敛因子，v ，是方差的梯度， 即： 卟2 士( 苦，苦，苦 r 协7 ， 根据式( 2 - 5 ) ，式( 2 7 ) 可以表示为： 一 r 一1 r v = - 2 e l f ，x j j = 一2 e ，x 所以，式( 2 - 6 ) 可以表示为： w j n = w j 七2 1 e3 xi ( 2 8 ) ( 2 9 ) 式( 2 5 ) 与( 2 - 9 ) 合称为即称为w i d r o w - h o f f l m s 算法，该算法只需对其进 行式( 2 5 ) 与( 2 - 9 ) 中的二个乘法与二个加法运算，因此易于用实时系统实现。 11 华北电力人学硕士学位论文 关于收敛因子i i 的选取，有如下规则： _ 一1 0 一 兄一 ( 2 1 0 ) 即只有当肛大于零、小于自相关矩阵爰的最大特征值的倒数时，才有_ ，专o o ， i 一2 天】p 斗0 ，该算法爿可能收敛，并保持稳定。但是，因为自相关矩阵的本征 值通常是未知的，因此我们常采用的方法是： 2 2 2a f 算法与r t t 预测 百l 0 n r 研j ? 】 i - i ( 2 1 1 ) 正是由于r t t 呈现出明显的自相似性，而a f 算法模型在解决此类问题时具有 卓越的性能。因此，在i 玎t 预测算法中，采用a f 预测模型。在n + l 时刻，根据前 p 个r t t 的真实测量值，估算此刻的i 盯t 值。 i 汀t 预测算法核心步骤如下n ”： ( 1 ) 初始化：令以代表r t t 序列向量，也就是输入信号，睨代表自适应滤 波器的系数向量，这两个向量的维数均为p ，也就是说我们用前p 个l 汀t 值来预测 下一时刻的i 汀t 值。 ( 2 ) 计算n 时刻的i h t 预测值，以= 孵以。 ( 3 ) 计算n 时刻的i 玎t 预测值与真实值之间的误差：e n = r t t 。一r i t 。 ( 4 ) 根据误差巳更新自适应滤波器的系数向量： 睨+ 。= 睨一胛。= 睨+ 2 心。 ( 5 ) 根据更新的系数向量，预测n + l 时刻的r t t 值。 ( 6 ) 如此循环往复。 图2 - 9r t t 预测模型 1 2 华北电力大学硕+ 学位论文 预测模型如图2 - 9 所示。其中，a f , 、彳代表自适应滤波器，a f 2 是a f , 的完 全拷贝，二者具有一样的系数向量。彳e 是预测，a f , 用来做同步更新，是自适应滤 波器在更新系数之后完成的不同工作。 2 3 基于自适应滤波算法的r t t 预测模拟实验 2 3 1 实验平台简介 本论文实验是基于n s 2 网络仿真模拟器的。n s 2 是指n e t w o r ks i m u l a t o rv e r s i o n 2 ，是一种针对网络技术的源代码公开的、免费的软件模拟平台，研究人员使用它 可以很容易的进行网络技术的开发，而且发展到今天，它所包含的模块已经非常丰 富，几乎涉及到了网络技术的所有方面。所以，n s 成了目前学术界广泛使用的一 种网络模拟软件。 n s 2 是一种面向对象的网络仿真器，本质上是一个离散事件模拟器，由u c b e r k e l e y 开发而成。它本身有一个虚拟时钟，所有的仿真都由离散事件驱动的。目 前n s 2 可以用于仿真各种不同的i p 网，已经实现的一些仿真有：网络传输协议， 比如t c p 和u d p ；业务源流量产生器，比如f t p ，t e l n e t ，w e bc b r 和v b r ； 路由队列管理机制，比如d r o p t a i l ，r e d 和c b q ；路由算法，比如d i j k s t r a 等。 n s 2 也为进行局域网的仿真而实现了多播以及一些m a c 子层协议。可以看出，n s 2 为许多算法的验证提供了有效的验证平台。 n s 2 使用c + + 和o t c l 作为开发语言。n s 可以说是o t c l 的脚本解释器，它包含 仿真事件调度器、网络组件对象库以及网络构建模型库等。事件调度器计算仿真时 间，并且激活事件队列中的当前事件，执行一些相关的事件，网络组件通过传递分 组来相互通信，但这并不耗费仿真时间。所有需要花费仿真时间来处理分组的网络 组件都必须要使用事件调度器。它先为这个分组发出一个事件，然后等待这个事件 被调度回来之后，才能做下一步的处理工作。事件调度器的另一个用处就是计时。 当仿真完成以后，n s 将会产生一个或多个基于文本的跟踪文件。只要在t c l 脚本中加入一些简单的语句，这些文件中就会包含详细的跟踪信息。这些数据可以 用于下一步的分析处理，也可以使用n a m 将整个仿真过程展示出来。 一次仿真的步骤大致如下： ( 1 ) 丌始编写o t c l 脚本。首先配置模拟网络拓扑结构，此时可以确定链路的 基本特性，如延迟、带宽和丢失策略等。 ( 2 ) 建立协议代理，包括端设备的协议绑定和通信业务量模型的建立。 ( 3 ) 配置业务量模型的参数，从而确定网络上的业务量分布。 ( 4 ) 设置t r a c e 对象。n s 通过t r a c e 文件来保存整个模拟过程。仿真完后， 1 3 华北电力人学硕+ 学位论文 用户可以对t r a c e 文件进行分析研究。 ( 5 ) 编写其他的辅助过程，设定模拟结束时间，至此o t c l 脚本编写完成。 ( 6 ) 用n s 解释执行刚才编写的o t c l 脚本。 ( 7 ) 对t r a c e 文件进行分析，得出有用的数据。 ( 8 ) 调整配置拓扑结构和业务量模型，重新进行上述模拟过程。 2 3 2 网络拓扑及实验环境 采用最常用的n s 2 网络环境拓扑结构，即哑铃结构，如图2 1 0 所示。在发送 端和接收端之间有两个路由器，数据流在路由器端中转排队，争用两个路由间的链 路空间。 s e n d e r l s e n d e r 2 图2 1 0 实验拓扑结构 r e c e i v e r l r e c e i v e r 2 r e c e i v e r n 每个发送端与路由器、路由器与每个接收端之间的链路带宽都是1 0 m b p s ，路 由1 与路由2 之间的链路带宽是1 0 m b p s 。路由端队列最大长度是1 5 0 k b ，数据包 的大小均为1 k b 。 2 3 3 实验分析及结论 为了验证算法的鲁棒性，本论文设计了两中不同的测试方案。 ( 1 ) 单点对单点 在这一方案中，两个路由之间的时延是2 8 m s 。每条链路的时延在0 2 0 s 时间段 内为2 8 m s ，在2 0 4 0 s 时问段内变为3 3 m s ，在4 0 6 0 s 时间段内变为3 8 m s 。在6 0 s 时刻，实验完成。也就是说整个链路时延的变化有三个阶段，依次是1 6 8 m s 、1 8 8 m s 和2 0 8 m s 。 这个实验中，我们分别做个三个分量实验：基础实验、改变预测基数的实验和 改变预测系数向量的实验。实验结果如图2 1 l 所示。 1 4 华北电力大学硕士学位论文 ( a ) 基础实验 ( b ) 改变预测基数的实验 ( c ) 改变预测系数向量的实验 图2 - l l 点对点r 1 r t 预测实验 在基础实验中，“r t t m e a s u r e m e n t a l l 代表t c p 端维持的r t t 真实值， “s i mp r e d i c t ”代表预测值，右侧图是左侧图在20212s这一时间段内的放numl5 大。在本实验中，以和呢均是1 5 维向量，且预测系数向量分量值均为1 5 。从图 中可以看出，自适应滤波算法很好的跟踪了时延的迅速变化，在l s 内迅速达到稳定 状态。 在改变了预测基数的实验中，我们用1 5 维和3 0 维的时延稍作比较，发现基数 向量维数越大，跟踪的越精确，但是门槛值有待进一步考量，在本文后续内容中将 l5 华北电力人学硕十学位论文 进一步讨论。 在改变预测系数向量的实验中可以看出系数的选择对实验结果有明显影响，需 要找一个最优系数向量求解法则。 ( 2 ) 多点对多点 本实验方案中模拟了多个发送端与多个接收端经过同一路由链路、争用带宽的 情况。由于多个数据流争用带宽，会出现严重的排队及丢包现象，也就模拟了大流 量数据块发送的状态。 本实验中，分别有5 0 个数据发送端和5 0 个数据接收端，每条链路的时延均预 设为2 8 m s ，实验持续1 5 0 s 。实验结果如图2 1 2 所示。 图2 1 2 多点对多点i 汀t 预测实验 因为严重的排队及丢包，部分r t t 预测值远大于实际值，但是从实验图中可以 看出自适应滤波算法迅速跟踪了r t t 的急速变化。表2 1 对数据进行了详细分析。 表2 1 数据分析 数据包总数2 6 0 3 可接受的预测数据量2 4 2 3 不町接受的预测数据量1 6 8 接受率9 3 1 基于自适应滤波器的r 1 陌预测算法是以l 玎t 的统计特性为基础的，因此序列 中的旧i m 值对新的预测值有显著值，当数值发生极端变化时，预测值则必然与实 际值发生剧烈偏差，但由于其自适应性，滤波器又能很快调整系数、跟踪变化。由 于r 1 盯自相似性的必然存在性，我们的算法具有可以预见的良好性能。 1 6 。然后分析目 式测量，同时 相似性。网络 时延的自相似性对r t t 的预测、实时系统的设计有着重要的启发。 最后，基于网络时延具有的自相似性，本章引入自动化控制领域的自适应滤波 器，作为r 1 r t 预测算法的原型，在此基础上，引出r 1 r t 预测算法，并给出相应的 网络拓扑模型及实验，通过实验结果发现，作为一个类似机器学习模式的算法模型， 自适应滤波体现出了良好的性能，它能够迅速调整预测系数，跟踪r t t 变化。 1 7 华北电力大学硕士学位论文 第三章基于自适应滤波的新型传输协议研究 3 1t c p 协议研究 据统计，截止2 0 0 6 年，9 5 ( 截止2 0 0 0 年，该数据为7 0 ) 的互联网数据传 输都是由t c p 来完成的心1 引，也就是说，当今互联网的动态特性主要由t c p 协议及 其应用来决定，故在提出一个互联网的新型传输协议之前研究t c p 是很自然的。 t c p 提供可靠的运输层，它使用的方法之一就是确认从另一端收到的数据。但 数据和确认都有可能会丢失，t c p 通过在发送时设置一个定时器来解决这种问题。 如果当定时器溢出时还没有收到确认，它就重传该数据。对任何实现而言，关键之 处就在于超时和重传的策略，即怎样决定超时间隔和如何确定重传的频率。 t c p 超时与重传中最重要的部分就是对一个给定连接的往返时间( i 汀t ) 的测 量。由于路由器和网络流量均会变化，因此我们认为这个时间可能经常会发生变化， t c p 应该跟