（计算机应用技术专业论文）ad+hoc网络拥塞控制的研究.pdf

a dh o e 网络拥塞控制的研究 摘要 随着无线通信的飞速发展和大量移动终端设备的广泛使用，人们在移动计算 领域应用的需求与日俱增，这都极大的促进了a dh o c 网络技术的迅速推广和普 及。a dh o c 网络是由一组无线终端组成的无基础设施、无集中管理机制的网络。 网络中的所有节点自组织、自管理。 a dh o e 网络具有部署简便、适应性强等优点，但这也正是其局限性所在： 阿络拓扑可随时变化降低了性能、无线信道带宽有限且干扰严重、电池供电能量 有限、缺乏基础设施网络难以管理。目前对a dh o e 网络的研究主要致力于解决 以上不足，包括：路由协议、服务质量q o s 、能耗、节点移动性管理和安全问题 等。 目前的t c p 协议把数据包丢失或延迟增大归因于网络拥塞，当a dh o e 网络 中的节点移动导致了无线信道的断开，使网络拓扑发生改变，正在使用中的路由 失效，数据包发生超时和丢失，就会引发t c p 协议的拥塞控制机制。这将大大 降低t c p 的吞吐量，引起网络性能的下降。另外目前提出的a dh o e 路由协议没 有考虑节点的拥塞状况，不能将数据流量比较均匀的分布于整个网络，在现有路 由失效时，不能及时通告源节点，以便迅速做出响应。 本论文详细深入的分析了a dh o c 网络的体系结构和特点，以及拥塞导致的 性能问题，从端到端和中间结点两个方面着手解决拥塞问题。 本文为端节点提出了一种新的路由协议c c b r ，它将节点的拥塞程度作为路 由选择的影响因素，有效减少了a dh o c 网络中发生拥塞的可能性，并提高了t c p 协议的效率。针对中间节点提出了一种简便的显式通告拥塞控制算法e n c c ，在 中间结点感知到可能发生拥塞时，生成消息报文，通告源节点控制流量。同时 改进了中间节点的主动队列管理机制。 n s 2 是网络技术研究人员广泛使用的模拟工具，实践已经证明其结果的可 靠性和可参照性。本文使用n s 2 对新提出的路由协议进行了验证，结果表明在 减轻t c p 数据流的拥塞方面较传统的路由协议有了明显提高。 关键字：a dh o c ，拥塞控制，队列管理，路由协议 复旦大学硕士学位论文 a dh o c 网络拥塞控制的研究 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fw i r e l e s sc o m m u n i c a t i o na n dw i l d l yu s eo fm o b i l e t e r m i n a l s ，p e o p l e sn e e di nm o b i l ec o m p u t i n ga r eg r o w i n gd a yb yd a y a l lo fa b o v e m a k ea dh o en e t w o r kp o p u l a r a dh o en e t w o r ki sm a d eu po fas e to fw i r e l e s sm o b i l e t e r m i n a l s ，w i t h o u ta n yi n f r a s t r u c t u r ea n dc e n t r a lm a n a g e m e n tm e c h a n i s m a l ln o d e s a r ea u t o n o m o u sa n ds e l f - m a n a g e m e n t a dh o en e t w o r kh a ss u c hm e r i t sa se a s yt od e p l o ya n dw i d e l ya d a p t e d ，w h e r e a s i t sl i m i t sl i ei nt h e m h e x i b l en e t w o r kt o p o l o g yd e g r a d e sp e r f o r m a n c e ，w i r e l e s s c h a n n e lh a san a l t o wb a n d - w i d t ha n ds t r o n gi n t e r f e r e n c e s , b a t t e r y se n e r g yj sv e r y l i m i t e d ，a n dn e t w o r ki sh a r dt oh a n d l ew i t h o u ti n f r a s t r u c t u r e c u r r e n tr e s e a r c hm a i n l y f o c u so nr o u t i n gp r o t o c o l s ，q u a l i t yo fs e r v i c e ，e n e r g yc o n s u m i n g n o d e s m o b i l i t y m a n a g e m e n ta n ds e c u r i t y t c pp r o t o c o la t t r i b u t e sp a c k e t s l o s to rl a t e n c yt on e t w o r kc o n g e s t i o n w h e n s o m en o d ei na dh o cn e t w o r km o v e st ob r e a kt h ew i r e l e s sc h a n n e l ，c h a n g et o p o l o g y a n dr o u t ei nu s eb e c o m ei n v a l i dt h ec o n g e s t i o nc o n t r o lm e c h a n i s mw i l lb ea c t i v a t e d t h u sm a k e st h et h r o u g h p u td r o ps h a r p l y t i l ln o w , a dh o cm u t i n gp r o t o c o l sp m p o s e d f a i lt oc o n s i d e rt h en o d e s c o n g e s t i o ns t a t es ot h e yc a n n o td i s t r i b u t ed a t af l o we q u a l l y i n t ot h ew h o l en e t w o r ka n dw h e nc u r r e n tr o u t ei si n v a l i dt h e yc a n n o ti n f o r mt h e s o u r c en o d et or e a c ti nt i m e t h i sa r t i c l ea n a l y z e st h ea r c h i t e c t u r ea n dc h a r a c t e r i s t i c so fa dh o ei nd e t a i l ，a n d t r i e st os e t t l et h ec o n g e s t i o np r o b l e mi nt w ow a y s ：e n d t o - e n da n di n t e r m e d i a t en o d e s t h i sa r t i c l ep r o p o s e dan e wr o u t i n gp r o t o c o lc c b rw h i c hc o n s i d e r sn o d e s c o n g e s t i o ns t a t ew h e nb u i l d i n ga n ds e l e c t i n gr o u t e s i th e l p st or e d u c et h ep r o b a b i l i t y o fc o n g e s t i o ni na dh o ea n di m p r o v et h ep e r f o r m a n c eo ft c et h i sa r t i c l ea l s o p r o p o s e dan e wa l g o r i t h mc a l l e de n c c w h e ni n t e r m e d i a t en o d e ss e n s e sc o n g e s t i o n w i l lh a p p e nt h e yg e n e r a t en o t i f i c a t i o np a c k e t st oi n f o r mt h es o u r c et oc o n t r o li t sd a t a f l o w a l s o ，t h ea c t i v eq u e u em a n a g e m e n tm e c h a n i s mi sw e l lr e v i s e di nt h i sa r t i c l e n s 一2i saw i d e l yu s e ds i m u l a t et 0 0 1 i t sr e f i a b i l i t yh a sb e e np r o v e di nm a n y e x p e r i m e n t s i nt h i sa r t i c l e ，t h en e w l yp r o p o s e dm u t i n ga l g o r i t h mi sv e r i f i e du s i n g n s 一2 s h o w st h a tc c b re x c e l sc u r r e n tr o u t i n gp r o t o c o l si nr e d u c i n gt c p c o n g e s t i o n k e yw o r d s ：a dh o c ，c o n g e s t i o nc o n t r o l ，q u e u em a n a g e m e n t ，r o u t i n gp r o t o c o l s 复旦大学硕士学位论文 a dh o c 两络中拥塞控制的研究 第一章论文简介 1 1问题的提出和本文的贡献 a dh o c 无线网络因其不需要预先架设基础设施、易于灵活部署、有着广泛 的应用场合等优点，近年来得到了越来越广泛的研究，应用领域也在逐渐扩展。 a dh o c 网络是由无线移动设备作为节点组成的网络，所有节点的功能都是 相似的，实行分布式管理，网络中不存在集中式的管理机制，这增大了管理的难 度。因为每个移动节点的信号覆盖范围有限，对不能够直接通信的节点，数据转 发功能由其它节点完成。a dh o c 网络中的节点可以随意运动，造成网络拓扑的 随时变化和路由的改变，这将影响到已经建立好的数据连接。 网络拥塞是严重影响网络性能、导致服务质量q o s ( q u a l i t yo fs e r v i c e ) 下降的主要因素之一，以前的研究工作主要针对有线网络环境的拥塞问题，并取 得了丰富的成果。a dh o c 网络同样存在拥塞问题，而且由于a dh o c 网络无线信 道带宽小、相邻节点之间存在干扰、节点的路由能力远不如路由器、节点能量有 限、拓扑随时发生变化等不利因素，使得拥塞发生的可能性增大，发生拥塞后的 处理更加困难。而且随着借助于语音、视频等手段的实时通信应用逐渐增多，数 据流量增长很快，这也在一定程度上加重了拥塞问题。 一般来说，解决拥塞问题可以从几个方面着手：基于端到端、基于中间结点、 基于路由协议。到目前为止，人们提出了上百种a dh o e 路由算法，大多数算法 偏向于解决某一方面的问题，如节能、低延迟等，在拥塞避免和拥塞控制方面也 出现了一些方案。但在以上机制如何更好的结合和协作方面还有许多问题有待解 决。 本文对传统有线网络的拥塞控制机制进行了研究和借鉴，并深入分析了a d h o c 网络的特性，然后在此基础上提出了一种显式通告拥塞控制算法e n c c ( e x p l i c i tn o t i f i c a t i o nc o n g e s t i o nc o n t r 0 1 ) ，利用端节点和中间节点之间 的协作解决拥塞问题。同时提出了一种基于拥塞控制的路由协议c c b r ( c o n g e s t i o nc o n t r o lb a s e dr o u t i n gp r o t o c 0 1 ) ，在为数据包进行路由选择的 阶段，考虑每条路由的拥塞状况，优先选用节点负载较小、拥塞较轻的路由，旨 在减少网络拥塞的发生和降低数据包发送的端到端延迟，并对其在拥塞避免方面 的效果进行了仿真实验，验证了其在a dh o c 网络中减轻拥塞发生的有效性。 多种机制相结合是解决拥塞问题的最有效途径，本文的工作在这方面进行了 探索，并取得了一些成果。 a dh o c 网络中拥塞控制的研究 1 2文章的内容结构 本文共分为六章。 第二章论述了a dh o e 网络的体系结构和应用，以及存在的拥塞问题。 第三章阐述并分析比较了现有的拥塞理论和拥塞控制机制，作为下文展开研 究的基础。 第四章详细阐述了显式通告拥塞控制算法e n c c 的思想和实现过程。 第五章论述了当前有代表性的a dh o c 网络路由协议，并作了深入的分析比 较，指出现有的路由协议对拥塞避免的影响和不足，进而对提出的基于拥塞控制 的路由算法c c b r 进行详细阐述，对算法的设计思想、实现过程、相关问题进行 了讨论和分析。然后使用n s 一2 模拟工具进行了实验验证，并把试验结果与已知 的有代表性的a dh o c 路由协议进行了性能方面的对比。 第六章总结了全文的工作，并对工作的不足和了今后研究的方向做出了展 望。 a dh o e 网络中拥塞控制的研究 第二章a dh o c 网络的拥塞问题 2 1a d h o c 网络概况 2 1 1a dh o c 网络的历史 a dh o e 技术最早起源于2 0 世纪7 0 年代的美国军事领域，它是在美国国防 部资助研究的战场环境中的无线分组数据网项目中产生的一种新型的网络构架 技术。随着移动通信和移动终端技术的不断发展，a dh o c 技术不但在军事领域 中得到了充分的应用，而且也开始在民用移动通信中得到了应用，尤其是在一些 特殊的环境中，例如所在的地区没有可以利用的固定设备或者由于某种因素的限 制不能使用已有的网络通信基础设施时，用户之间的信息交流以及协作就需要利 用a dh o c 技术完成通信网络的快速部署，满足用户对移动数据通信的需求。 a dh o c 技术涉及o s l ( o p e ns y s t e mi n t e r c o n n e c t i o n ) 分层模型中的每一 个层次。人们已经在媒质接入问题、路由问题、组播路由问题、电能管理问题、 q o s 问题、安全问题、传输层问题等方面发布了相关的研究成果。在众多的难题 中，a d h o c 网络的路由问题尤其关键，i e t f ( i n t e r n e te n g i n e e r i n gt a s kf o r c e ) 已经成立了m a n e t ( m o b i l ea dh o cn e t w o r k i n g ) 工作组集中从事a dh o c 网络 单播路由协议及其性能评定的研究，现已发布了一些路由草案，i e t f 下一步还 将就如何实现多播路由以及q o s 等问题展开讨论。在a dh o c 网络技术中，无线 移动a dh o c 网络一m a n e t 是下一代移动通信系统解决方案中最有发展潜力的。 2 1 2a dh o c 网络的应用 a dh o c 网络在军事通讯、防汛抗洪等应急通讯、商业应用等领域有着广泛 的应用前景 1 ，总结如下： ( 1 ) 军事应用：军事应用是a dh o c 网络技术的主要应用领域。因其特有的 无须架设网络设施、可快速展开、抗毁性强等特点，是数字化战场通信的首选技 术。a dh o c 网络技术已经成为美军战术互联网的核心技术。美军的近期数字电 台和无线互联网控制器等主要通信装备都使用了a dh o c 网络技术。 ( 2 ) 传感器网络：传感器网络是a dh o c 网络技术的另一大应用领域。分散 的传感器组成a dh o c 网络，可以实现传感器之间与控制中心之间的通信，这在 爆炸残留物监测、野外管道智能控制等领域有广阔的应用前景。 ( 3 ) 临时和紧急场合：在发生地震、火灾、水灾的场合，固定的通信设施 a dh o c 网络中拥塞控制的研究 可能无法正常工作。h dh o c 网络技术的独立组网能力和自组织的特点是这些场 合通信的最佳选择。 ( 4 ) 个人通信：综合各种可能的网络技术来实现任何人在任何时间、任何 地点与任何人进行任何种类的信息交换，即实现个人通讯是a dh o c 网络技术的 另一领域。 ( 5 ) 商业教育应用：为展览会、会议或交易会建立通讯系统、建立虚拟连 接等。 ( 6 ) 作为终端接入网：a dh o c 网络与蜂窝移动通讯系统的覆盖范围，均衡 相邻小区的应用、提高小区边缘的数据速率等。 2 2a dh o c 网络的体系结构 2 2 1 协议层次结构 a dh o c 网络的协议层次结构可以和0 s i 模型相互对照： 物理层完成无线信号编码译码、发送和接收等工作： 数据链路层控制对共享无线信道的访问以及对逻辑链路的控制，所以数据链 路层又分为m a c ( o r 质访问控制) 层和l l c ( 逻辑链路控制) 层。 网络层是a dh o c 技术的重点，也是它与其它现有网络的主要区别所在。i p v 4 协议、i p v 6 协议或其它网络层协议提供网络层数据服务。网络层的单目标路由 协议维护路由表，使其与当前的a dh o c 网络拓扑结构一致。多目标路由协议提 供群组通信的底层支持；网际互联支持a d h o c 网络中与其它现有网络互联，o o s 支持提供有保证的o o s 服务，路由安全提供对路由协议的安全保障。 传输层主要完成端到端通信连接的建立，目前一般的做法是对有线网中的传 输层协议t c p u d p 进行改造，使它们适应无线环境； a dh o c 的高层主要包括建立在h dh o c 技术之上的无线应用以及接入移动通 信核心网的各种应用 2 3 。 a db o a 鼹络中拥塞控制的研究 应用层 w a pi n t e r a c t 移动通信 表示层 ，。 w i 托i c s st c p ，u d p 会话层 ? 夕卅 t a b l e - d r l v e n r o u t i n go n - d e m a n dr o u t i n g 其他 传输层 d s d vw r pc g s r s t a ra o d vd s rt o r as s r 网络层 i e e e8 0 2 2 实时l l c m a c a实时，7 c s m a 虻dp a m a sf a m am a r c hc a t a其他 m a c a w m a c 链路层 ，- 一。一。 蓝牙 h i i r l a n i e e e8 0 2 1 i 系列 实时物理层 物理层 ( f b s s )( 0 f d m )( f h s s o f d m d s s s ) 图2 - 1 a dh o c 网络的分层结构 2 2 2 网络组织结构 a dh o c 网络节点一般有两种逻辑组织结构： 平面结构( 图2 2 ) 和分级结 构( 图2 3 ) 。 2 图2 - 2 a dh o c 网络的平面结构 在平面结构中，所有节点的地位平等，所以又被称为对等式结构。而分级结 构中，网络被划分为簇( c l u s t e r ) ，每个簇由一个簇头( c l u s t e rh e a d e r ) 和多 个簇成员( c l u s t e rm e m b e r ) 组成，这些簇头形成了较高一级的网络，在高一 级网络中，又可以分簇，再次形成更高一级的网络，直至最高级。分级结构中， 簇头节点负责簇间数据的转发。 a dh o c 网络中拥塞控制的研究 图2 - 3 a dh o c 网络的簇状结构 比如当簇l 中的节点a 要与簇2 中的节点b 通信时，节点a 先把数据发 送给簇i 的簇头；簇1 的簇头分析发现b 在簇2 中，把数据转发给簇2 的簇 头( 可能要经过其它簇头的转发) ：簇2 的簇头收到数据后，发现b 是自己簇的 成员，把数据发送给b 。 根据不同的硬件配置，分级结构又可以分为单频分级和多频分级两种。 单频分级网络中只使用一个通信频率，所有节点都用这个频率通信。为了实 现簇头之间的通信，要有网关节点( 同时属于两个簇的节点) 的支持。簇头和网 关形成了高一级的网络，称为虚拟骨干。 多频率分级网络中，不同级别的网络使采用不同的通信频率。低级的节点的 通信范围较小，而高级的节点需要覆盖更大的范围。高级的节点同时处于多个级 中，有多个频率，用不同的频率实现与不同级节点的通信。例如在两级网络中， 簇头节点有两个频率。一个频率用于簇头与簇成员的通信，而另一个频率用于簇 头之间的通信。 网络比较简单，无需任何的结构维护过程。源节点和目的节点之间一般存在 多条路由，可以使用多条路由实现负载分流，也可以为不同类型的应用选择合适 的路由。平面结构的网络中所有节点是对等的，承担的任务基本相同，原则上不 存在瓶颈，所以比较健壮。平面结构中节点的覆盖范围比较小，相对比较安全。 平面结构的最大缺点是网络规模有限。在平面结构中，每一个节点都需要知 道到达其它所有节点的路由。由于节点的移动性，维护这些动态变化的路由信息 需要大量的控制消息。网络规模越大，路由维护的开销就越大。当网络增大到一 定规模时，大部分的带宽可能会被路由协议消耗掉。所以平面式结构网络的可扩 充性较差。 分级结构的最大优点是可扩充性好，网络规模不受限制。必要时可以通过增 a dh o e 网络中拥塞控制的研究 加簇的个数或级数来增大网络的容量。分级结构中，簇成员节点的功能比较简单， 基本上不需要维护路由，这大大减少了网络中路由控制信息的数量。簇头节点需 要维护到达其它簇头的路由，还要掌握所有节点与簇的从属关系。但总的来说， 在相同网络规模的条件下路由开销要比平面结构的小。如果簇内通信的信息量占 较大比例时，各簇可以互不干扰地进行通信，系统的吞吐量显然要比平面结构的 要高。 2 但是分级结构也存在一些缺点： 首先，维护分级结构需要较复杂的簇头选举算法。 其次，簇间的信息交换都要经过簇头中转，实际上不一定每次都能用到最佳 路由。例如在不同簇中但互为邻居的节点，在平面结构中可以直接通信，但分簇 后要通过两个簇的簇头转发。 分级结构要比平面结构有优势。第一，分级结构有较好的可扩展性。第二， 分级结构通过路由信息局部化减少了开销，提高了系统的吞吐量。分级结构使路 由信息局部化，簇内节点无须知道其它簇的拓扑结构，一个簇的拓扑变化不会被 其它簇感知，这减小了路由控制报文的开销。第三，分级结构中节点的定位要比 平面结构简单得多。在平面结构中，想知道一个节点的位置，需要在全网中执行 广播式的查询操作。而在分级结构中，簇头知道自己簇成员的位置，只要查询簇 头就可以得到节点的位置信息。第四，分级结构可通过移动性管理来实现序列寻 址。按照节点与簇的关系为节点分配逻辑序列地址，由簇头充当位置管理服务器， 就可以简单地实现节点定位和寻址。第五，分级结构是无中心和有中心模式的混 合体，可以结合两种模式的技术优势。虽然采用分级结构后有了逻辑上的控制中 心簇头，但是簇头和簇成员的角色是动态变化的，节点仍是自动组网的。分 级后网络被分成了相对独立的簇，每个簇都有控制中心。基于有中心的t d m a 、 c d m a 、轮询等技术都可以在分级的网络中使用。基于有中心控制的路由、移动性 管理、网络管理技术也可以移植到a dh o c 网络中来。随着对a dh o c 网络中o o s 要求的提高，采用基于有控制中心的技术可能是更好的选择。所以今后a dh o e 网 络逐渐呈现出分级化的趋势。 2 3a dh o e 网络的拥塞问题 a dh o c 网络是一种无中心的网络，这与传统的蜂窝移动通信系统不同。没 有集中的中心管理机制掌握所有节点的位置、路由、移动性等信息。无中心的结 构需要网络中的节点通过运行分布式算法( 信道接入、路由管理等) 来协调它们 的行为。 h dh o c 网络使用无线通信技术，具有无线通信系统信道质量低、带宽有限、 a dh o e 网络中拥塞控制的研究 节点通信距离有限等特点。在设计适用于a dh o c 网络的协议时，要充分考虑这 些限制。 有线或固定无线网络的带宽资源相对来说比较丰富，协议设计的原则是要尽 量增加通信对端交互的信息量通信对端交互的信息量，减少主机的计算量。而 a dh o c 网络的带宽非常有限，所以协议设计的原则是尽量减少通信对端交互的 信息量，而可以适当增加主机的计算量。这个原则在a dh o c 网络的信道接入控 制、路由等协议的设计中有非常明显的体现。 多跳( m u l t i h o p ) 是a dh o c 网络的一个显著特点。由于节点的信号覆盖 范围有限，h dh o c 网络中的节点不一定都在其它所有节点的直接通信覆盖范围 之内。当节点间并非直接可达时，需要由中间节点进行数据转发才能实现通信， 即从源节点到目的节点是多跳的。网络中的每个节点都具备转发报文的能力，所 以要有适当的路由协议来建立和维护路由信息。 a dh o c 网络的多跳特性对信道接入协议的影响很大。传统的基于共享广播 信道的接入技术( a l o h a 、c s m a 等) 只能在一跳共享的信道( 一个节点发送， 可以覆盖所有节点) 上使用，而a dh o c 网络的信道不是一跳共享的，所以a dh o c 网络的信道接入协议要充分考虑多跳带来的隐藏终端、暴露终端和公平性等问 题。 h dh o c 网络中节点的移动是随意的，节点的移动造成网络的拓扑结构不断 变化，这使得接入协议和路由协议都面临着新的问题。接入协议要能够了解到节 点移动造成的链路断开和建立，并把这些信息通知路由协议。路由协议要根据链 路状态的变化对路由表进行修改。传统的基于固定网络的路由协议显然不能直接 用于拓扑变化频繁的a dh o c 网络。h dh o c 网络路由协议是研究的重点之一。 节点的移动性也给传输层带来了新的问题。无线通信系统中t c p 的性能一 直是一个热门的研究课题，因为无线信道的高误码率特点会显著降低t c p 的性 能。a dh o c 网络中，节点的移动性也会影响t c p 的性能。 通过以上分析可以得出，与其它通信网络相比，a dh o c 网络具有以下特征： 3 ( 1 ) 网络的自组织性：a dh o c 网络可以在任何时刻任何地方构建，而不需要 现有的信息基础网络设施的支持，形成一个自由移动的通信网络。 ( 2 ) 动态网络的拓扑结构：从网络的网络层来看，a dh o c 网络中，移动用户 可以以任意的速度和任意方式在网中移动，加上无线发送装置发送功率的变化、 无线信道间的相互干扰因素、地形因素等的影响，节点间通过无线信道形成的网 络拓扑结构随时都会发生变化。 ( 3 ) 有限的无线传输带宽：无线信道本身的物理特性使a dh o c 网络的网络 a dh o c 网络中拥塞控制的研究 带宽相对有线方式要低得多，另外还要考虑无线信道竞争时所产生的信号衰落、 碰撞、阻塞、噪声干扰等因素，这使得实际带宽要小得多。 ( 4 ) 移动终端功能有限：a dh o c 网络中的移动用户终端内存小、c p u 处理能 力低、所带电源有限。这都使得a dh o c 网络的设计更加困难。 ( 5 ) 安全性差：a dh o c 网络是一种无线方式的分布式结构，所以更加容易被 窃听、入侵、网络攻击和拒绝服务等。 ( 6 ) 分布式控制：a dh o c 网络中的移动节点都兼有独立路由和主机功能，不 存在类似于基站的网络中心控制点，节点地位平等，采用分布式控制方式，增强 了网络健壮性。 ( 7 ) 网络可扩展性差：由于采用t c p i p 协议中的子网技术使得i n t e r n e t 具 有网络的可扩展性，而a dh o c 网络动态变化的拓扑结构使得子网技术所带来的 网络可扩展性得不到体现。 ( 8 ) 单向无线信道的存在。 ( 9 ) 生存时间短：组网通常是由于某个特定原因而临时创建的，使用结束后， 网络环境将会自动消失。a dh o c 网络的生存时间相对于固定网络而言是短暂的。 ( 1 0 ) 高误码率：无线信道通信质量低，误码率高，因此无线网络中传输的分 组经常由于损坏而被丢弃。 t c p 协议是当前i n t e r n e t 主机之间使用的提供可靠的传输服务的传输层协 议，它具备拥塞控制机制，保证了在大规模网络上所能提供的服务质量。随着无 线网络应用的迅速发展，i n t e r n e t 上传统的技术已无法适应无线网络环境。t c p 协议在无线网络环境中如何有效地提高性能已经成为当前无线技术领域重要的 研究课题。 拥塞是一种持续过载的网络状态，发生拥塞时意味着用户对网络资源( 包括 链路带宽，存储空间和处理器处理能力等) 的需求超过了其固有的容量。也就是 说，拥塞发生在经由网络传输的分组数量开始接近网络的处理能力时 4 。图2 4 显示了拥塞于网络的吞吐量和延迟的关系。 a dh o e 网络中拥塞控制的研究 吞 吐 量 图2 - 4 拥塞与吞吐量和延迟的关系 当网络负载较小时，通信量远在网络容量之下，吞吐量的增长和负载基本呈 线性关系，而延迟的增长较为缓慢。当网络负载越过膝点( k n e e ) 之后，吞吐量增 长变得缓慢，延迟增长加快，网络开始丢包，这时网络进入了一个中等的拥塞状 态。在这个区域，网络继续传送负载，延迟也在增长。当些节点经历着中等的 拥塞时，其它节点则可能已经存在严重的拥塞，以至于必须丢弃部分数据包。当 网络上的数据量继续增加，越过崖点( c l i f f ) 之后，吞吐量会急剧下降接近零， 延迟则趋近于无穷。拥塞控制机制的目的就是在网络接近于拥塞崩溃点c l i f f 时能尽快检测到，并采取措施减小网络负载，使网络恢复到正常状态，保持在 c l i f f 点左侧运行。 拥塞发生后如果不加以控制，往往会导致恶性循环。如果路由器没有空闲的 缓冲区空间，它将会丢弃今后到达的分组。而丢弃分组会引起发送端因为超时重 传该分组，这在网络拥塞严重时可能要重传多次，这样就进一步加重了拥塞，使 数据包的延迟进一步增加。在数据流量非常高的情况下，网络完全瘫痪，几乎没 有分组能够到达目的节点。般情况下，i p 网络在每个节点( 路由器或其它设 备) ，每一个传输信道上都有一个分组队列。如果分组到达和排队( 流入) 的速 度大于分组能够被转发( 流出) 的速率，队列长度就不断的增长，分组经历的延 迟就变得越来越大。当接收分组排队链路的利用率超过8 0 时，队列的长度的增 长速率就需要加以注意。继续增长的队列意味着分组将经历的延迟增长，同时队 列在不久的将来会发生溢出，造成大量数据包被丢弃。 一般来说，拥塞产生的直接原因主要有以下三点 5 ，6 ： ( 1 ) 缓冲空间有限：当输入的数据流量大于输出的数据流量时，在输出端口 就会发生排队现象。如果路由器( 或路由节点) 没有足够的缓冲空间，数据包就 会被丢弃，对突发数据流来说，这种现象更为严重。增加存储空间在某种程度上 可以缓解这一矛盾，但如果路由器的缓存空间无限大的话，拥塞情况不会消除， 盯 一 鼍j1i：一 一 一 h l1ljlllj一0罐 卜 a dh o c 网络中拥塞控制的研究 而只会变得更严重。因为这会大大增加部分数据包在路由器缓冲队列里的等待时 间，在网络情况好转，被继续转发到下一跳时，这些数据包已经超时，源端认为 它们己经被丢弃而重传，但这些数据包还会继续向下一跳路由器转发，从而造成 网络资源的浪费。 ( 2 ) 网络带宽容量有限：路由器可以连接不同类型、带宽的网络，当高带宽 网络向低带宽网络全速输数据时也会产生拥塞。根据香农公式，任何信道带宽最 大值( 信道容量) c = b l o g 。( i + s n ) ( b 为信道带宽，s 为信源的平均功率，n 为信道自噪声的平均功率) 。所有信源发送的速率r 必须小于或等于信道容量c 。 如果r 大于c ，则在理论上不可能做到无差错传输，所以会在低带宽网络出口处 形成带宽瓶颈，当其容量不能满足输入的所有带宽要求时，网络就会在此处发生 拥塞。 ( 3 ) 处理器能力有限：如果路由器的处理器在执行缓存排队，调度数据包转 发等功能时，处理速度跟不上数据流量输入速度，也会产生拥塞。同样，低带宽 链路对高速处理器也会产生拥塞。 在通信网络中，拥塞是影响数据传输效率，造成延迟、性能抖动等q o s 指标 下降和带宽、缓存等网络资源利用率降低的关键因素，如何更好的预防和控制拥 塞对于提高网络性能具有重要的意义。 因为移动节点在数据转发方面的处理能力远远低于路由器，所以a dh o c 网 络比有线网络更容易受到拥塞的影响导致网络性能下降。 性 能 l叫悖e f 、 图2 - 5 网络拥塞导致性能下降 传统的拥塞控制机制基于两个基本假设：一是t c p 协议认为网络拥塞是导致 数据丢失的唯一原因；二是t c p 协议认为网络中的节点( 路由器) 不对拥塞采取 任何干预措施，对网络情况的判断基于根据应答报文做出的推断。 传统的t c p 协议认为：由传输引起的数据包损坏和丢失的概率很小，一般小 于1 。而无线信道通信质量低，误码率高，因此无线网络中传输的分组经常由 于损坏而被丢弃。然而这种分组丢失都会被t c p 协议归因于网络的某处发生了拥 a dh o e 网络中拥塞控制的研究 塞，从而启动拥塞避免机制。这种做法使得发送方( 源端) 发送分组的速率急剧 下降，并要重新经历一个慢启动阶段。实际上这个时候需要的却是超时之后立即 重传没有被确认的分组。 由于a dh o c 网络的拓扑结构处于不断的动态变化之中，t c p 性能受此影响 很大，虽然到目前为止在o o s 路由方面已经做了大量的工作，但多数情况下，当 前的路由协议仍需要重新花费较多的时间计算路由。如果重新计算路由所耗费的 时间使重传定时器超时，则源端t c p 协议将启动拥塞控制机制。但在此时源端 t c p 协议应该采取的正确措施是在新的路由被计算出来之后，能够立刻开始传送 那些因为路由失效而丢失的分组，并不是等待接收到多个重复的a c k 后再重新开 始慢启动。 具有分级结构的a dh o c 网络重新分簇也会导致在这段时间内源端和接收端 的连接断裂，从而引发源端进行流量控制。但与路由失效情况不同的是，这是任 何路由算法都无法解决的，只能依靠传输层协议来改进。 当接收端收到乱序的分组时，会产生重复的a c k 。在a dh o e 网络中，当新 的路由计算好之后，中间节点有可能继续把缓存中存放的分组发送给接收端a 另 乡 当同时使用多条路由传输时也会产生乱序分组。这无疑会产生很多重复的 a c k 。这造成t c p 协议对网络状况的错误判断。 为了使t c p 协议能够区分是否因为网络拥塞造成的丢包，可以通过不同协议 层间的通告信息来解决。对于因为数据包破坏或路由断裂造成的延迟，只需快速 重传受影响的数据包即可。 a dh o e 网络中拥塞控制的研究 第三章传统的拥塞控制机制 一般来说，解决网络拥塞问题可以从两个方面着手：基于端系统、基于中间 节点。换个角度，这也可以看作是在t c p i p 协议族的不同层次上实旅的机制。 基于端系统的策略利用t c p 协议( 传输层) 的滑动窗口管理机制达到流量控制的 目的，中间结点( 负责数据包转发，如路由器) 根据i p 协议( 网络层) 信息， 执行排队算法和数据包丢弃策略。排队算法决定哪些数据包可以进行传输迸而分 配到相应的输出带宽数据包，丢弃策略则决定哪些包可获得路由器缓存空间。 网络拥塞控制的主要目标是控制进入网络的数据流量、保证通信子网不会被 源端发送的数据流淹没、合理地使用关键资源。网络拥塞控制的基本模式是端系 统负责响应拥塞，而路由器负责监测网络拥塞，拥塞信号被源端系统感知，进而 调节进入网络的数据流量。 在t c p i p 拥塞控制系统中i p 拥塞控制算法主要作为t c p 拥塞控制的支持 手段其主要的功能在于检测拥塞信息并及时反馈到t c p 源端，t c p 源端根据收到 的拥塞反馈信息动态的调整发送速率。两种机制的相互作用如图3 - 1 所示： 图3 - 1 两种机制的相互作用 3 1基于端到端的拥塞控制机制 3 1 1 拥塞控制机制的发展 t c p i p 协议族是目前i n t e r n e t 上的主流协议，因此t c p 基于窗口的拥塞控 制受到了广泛的关注和研究。 早期的t c p 实现只是使用累积确认、超时重传和后退n 帧等机制，对于网络 拥塞几乎没有什么控制。拥塞控制的研究开始于8 0 年代中期，1 9 8 4 年，n a g l e 首次指出了复杂i p 网络中存在的拥塞问题，特别是在由路由器连接的带宽容量 差异较大的网络之间，容易发生拥塞崩溃现象，但在当时并没有引起足够的重视。 1 9 8 8 年，j a c o b s e n 在t c p 中增加了拥塞控制算法，即t c pt a h o e 。提出了著名 流量拉翩拥塞通告 a dh o c 网络中拥塞控制的研究 的“慢启动”、“拥塞避免”、“快速重传”算法 7 ，1 9 9 0 年，改进的t c pr e n o 版本增加了“快速恢复”，避免了网络拥塞不够严重时采用慢启动面造成大幅度 减小发送窗口尺寸的现象。上述四个算法是目前i n t e r n e t 上通常使用的端到端 拥塞控制机制。当源端的t c p 协议推断网络出现拥塞时，通过调节发送窗口的大 小，限制数据流量。t c p 拥塞控制机制有效地避免了拥塞崩溃现象的发生。另外 还存在些t c pr e n o 的改进版本如n e wr e n o 8 、s a c k 9 等，t c pr e n o 是目前 i n t e r n e t 上广泛使用的版本。 在当前的有线t c p i p 网络中，拥塞控制的大多都是由端系统来完成的，而 路由器在通告和控制拥塞方面不发挥任何作用。传统的路由器使用“先进先出” ( f i r s ti nf i r s to u t ，f i f o 也可称为“先来先服务”) 的分组调度算法实现 缓存队列调度，使用“弃尾”的数据包丢弃算法实现缓冲队列管理，在发生拥塞 时，路由器缓冲区溢出，从而路由器丢弃队列尾部和最后到达的数据包。 f i f o 是目前i n t e r n e t 上使用最广泛的对数据包排队和丢弃的方式，路由器 对拥塞现象不作任何干预。这样仅仅依靠端到端的拥塞控制很难满足诸如q o s 这样复杂的应用需求。 端到端的t c p 拥塞控制采用基于滑动窗口的机制，目的是降低丢包率，减少 数据包的重传次数，减小数据包发送的端到端延迟，提高网络性能，平衡网络中 数据流量的分布，减少瓶颈的产生。 3 1 2 传统的拥塞控制机制 t c p 拥塞控制通过调节滑动窗口大小来达到控制流量的目的，为了管理滑动 窗口，引入的参数介绍如下： 发送窗口( w i n ) ：源端每次实际发送数据时的窗口大小； 拥塞窗口( c o n g e s t i o nw i n d o w ，c w n d ) ：源端下一次能够发送的数据包的数 量。 通告窗口( a d v e r t i s e dw i n d o w ，a w i n ) ：接收端建议源端预设的发送窗口大 ，j 、。 慢启动阈值( s s t h r e s h ) ：慢启动阶段和拥塞避免阶段的分界点，初始值大 小通常设置为6 4 kb y t e s 或a w i n 的大小。 往返时间( r o u n d t r i pt i m e ，r t t ) ：一个t c p 数据包从源端发送开始，一 直到接收到接收端确认为止的时间间隔。 重传定时器( r e t r a n s m i s s i o nt i m eo u t ，r t o ) ：一个t c p 数据包从源端发 送到失效的时间间隔。t c p 协议用此来判断数据包是否丢失。值通常被设置为 2 r t t 或5 r t t 。 a dh o c 网络中拥塞控制的研究 t c p 拥塞控制通常主要由以下四个部分组成： ( 1 ) 慢启动阶段 慢启动阶段目的是防止新建立的连接时，在不了解网络状态的情况下，在短 时间内向网络发送过多的数据包。 当建立新的t c p 连接时，c w n d 被初始化为一个数据包大小( 缺省为5 1 2 b y t e s ) 。源端按c w n d 大小发送数据，每收到一个a c k 确认，c w n d 就增加一个数 据包发送量。这样因为每次发送的数据包的a c k 都会在1 r t t 内到达，因此c w n d 在每一个r t t 内加倍一次，呈指数增长。源端向网络中发送的数据量将会急剧增 加。 ( 2 ) 拥塞避免阶段 当c w n d 大于s s t h r e s h 时，t c p 进入拥塞避免阶段。发送端在每收到一个a c k 后只增加1 c w n d 个数据包，所以在拥塞避免阶段，c w n d 的增长是线性的。发送 端对最近未确认的数据包维持一个重传定时器，每收到一个新的a c k ，重传定时 器的r t o 就重新设定。当源端发现a c k 超时时，即推断网