（模式识别与智能系统专业论文）一种改进型蚁群算法在组合优化问题中的应用.pdf

摘要 摘要 在计算机网络中，随着大量新兴多媒体实时业务的应用，以及i n l e m e t 上商业 化应用的飞速发展，网络对q o s ( q u a l i t yo f s e r v i c e ，服务质量) 需求增长，高效的 o o s 支持变得越来越重要。而路由机制是实现q o s 保证的关键之一，应将路由选 择和q o s 相关联。在多媒体通信等高速包交换计算机网络中，具有端到端时延及 时延抖动限制的q o s 组播路由问题属于组合优化问题，如何保证服务质量要求以 及实现多媒体数据的组播通信是多媒体通信发展的方向。 目前组播路由算法的研究大多都针对无约束组播路由问题和时延受限组播 路由问题，多采用启发式等方法。本论文研究如何将蚁群算法这一新型优化算法 应用到时延受限q o s 组播路由问题中。利用该算法的并行搜索特点，为解决q o s 组播路由问题寻找新的途径。本文主要研究工作如下： 首先对计算机网络的组播通信进行了综述。主要介绍组播引入的背景、特点、 组播技术，还叙述了q o s 的相关内容、研究现状、组播路由协议和应用。 然后展开了对蚁群算法的基本原理和模型实现的介绍，并阐述了蚁群算法的 特点等。在此基础上研究了如何将蚁群算法应用于q o s 组播路由问题中。端到端 的延迟和延迟抖动是两个较关键的性能参数。改进了原算法的路径选择策略并优 化信息素更新公式。仿真结果表明本文的改进蚁群算法比基本蚁群算法寻找最优 解的能力大大提高。 对蚁群算法进行了进一步的理论研究。通过实验分析了算法中几个关键参数 的选择。并且针对基本蚁群算法的主要缺陷，如收敛速度慢和易于陷入局部最优 等问题，系统地介绍了用于求解组合优化问题的几种改进蚁群算法。 蚁群算法在组合优化领域代表闯髭匾t s p ( t r a v e l i n gs a l c 锄锄p r o b i 锄，旅行推 销商问题) 中的应用，其收敛速度一直是人们关心的问题。针对蚁群算法的一些 不足，论文提出基于最小生成树的进化型蚁群算法。它利用了最小生成树与最优 路径之间的关系限制了蚂蚁在每一个城市的搜寻范围，进化了寻优策略，节省了 在不可能构成最优路径的路段上的计算时间，提高了运算速度，克服了传统蚁群 算法的计算时间长、精度低的缺点，使得蚁群算法的计算效率有了显著的提高。 并且在得出最优结果之后，进行局部优化和一定的修缮工作，以期能够寻找到更 优秀的解。 关键词：组播路由；s ；蚁群算法；生成树：组合优化问题；t s p a b s t 托i c t a b s t r a c t i i lm ec p m p u t e rn e t 、) v o r k s ，、i t l lal a 唱em m l b e ro f 印p l i c a t i o i l so fn e w m u l t i m e d i ar e a l - t i m e c o r 啪l l i l i c a t i o n s ，a n d t h e r a p i dd e v e l o p m e m o ft h e c o m m e r c i a l i z e d 印p l i c a t i o no fm ei m e m c ta n dt h ei n c r e 嬲eo fm en e e df o rq o so f 王t l t e m e t ，1 l i 曲e 衔c i e n c yq o st e c 王1 1 1 0 l o g yi sb e c o m i i l gm o r ea i l dm o r ei i n p o n 姐t a i l d t h er o u t i n gm e c h a n i s mi so n eo ft 1 1 ek e yf 缸o r st or e a l i z eq o s ，t h e r e f o r et h er o u t i n g c h o o s i n g 砒l dq o ss h o l l l db ec o n n e c t e d i i lt l l em u l t i m e d i ac o m m u m c a t i o n s 趾ds oo n h i g hs p e e dp a c k e t - s 谢t c h e dn e 柳o r k s ，t h ee n d - t o e n dd e l a ya n dd e l a yv a r i 砸o c o i l s t r a i n e dl e 鹊tc o s tm u l t i c a s tr o u t i n gp m b l e mi sac o m b i n a t o r i a lo p t i m i z a t i o n p m b i e m t h ed i r e c t i o no f m u l 恤n e d i ac o m m u n i c a t i o i l sd c v e l o p i n e n “sh o wt oe n s u r e 也eq u a l i 毋o f s e r v i c e ( q o s ) a n dt h e 瑚【u m c a s tc o m m u l l i c a t i o no f m u l 缸e d i ad a t a n o w a 出【y s ，m er e s e 盯c ho fm l l l t i c a s tr o u t i n ga l g o r i t h mi sm a i l l l ya i m i n ga tn o c o n s t r a j l l tm u l t i c a 5 tf o u t i n gp r o u 锄a 1 1 dd e l a y - c o n s 位d n e dm u l t i c a s tr o u t i n gp m b l e m ， a n dh e l l r i s t i ca l g o r i t l l m sa r em o s 廿yu s e d t l l i sp 印e rs t u d i e dh o wt oi m p l e m e n ta m c o i o n ya l g o r i t l l r n ( a c s ) - m i sn e wo p d m 础o na l g o r i t 岫- t od e l a y - c o n s 仃血e dq o s m u l t i c a s tr 0 埘n gp m b l e m ，a i l df i n dn e w 啪yt os o l v eq o sm l l l t i c 船tr o 诚n gp m b l e m w i 也血ep a r a l l e ls e a 础lo f t h i sa l g o d 妇_ 1 l n f i r s ti si n 如d u c t i o n w es u m m a r i z e 衄m u l t i c 韶tc 0 i 砌咖i c a n o n si nc o m d u t e r n e 咖r k s w ep r e s e mm eb a c k g r o 啪do fm i l l t i c a 瓯s p e c i a lf b a n 趾dt e c h n 0 i o g y w ea l s on a 删er e a l t e dc o n t e n to nq o sm u l t i c a s t ，血e p r e s e mr e s e a r c hs t a t l l s ， m u l 虹c a s tr o u t i i 唱p r o t o c o l 锄l di 忸唧1 i c 越o n t h e nw ei n 们d l l c e dt 1 1 eb a s i cp d n c i p l ea n dm o d e lr e a l i z a t i o no fa c s ，a n di 乜 c h a r a c 硎s t 主c s o n 血eb a s i so f t h a t ，血ep 印e rs n l d i e dh o wt oi l n p i c m e n t 也e “g o r i 也m i nq o si n u l t i c 船tm m i i l gp m b l e m e n d - t o - e n dd e l a ya n dd e l a yv a r i a l i o na r e k e y p e r f b n n a l l c ep 砒狮e t e r s mm en e wa l g o r i 恤r o u t e 跎l e c t i n gs 廿a t e g yw a s i l l l p r 0 v e da n d 血ei n f o m l a t i o nu p d a t ef 抽n l l l aw a s0 p t i 蚵z e d t h ee m u l a t i o nr e s 山t s s h o wm a t 诹t l l 让屺p a r a l l e ls e a r c h ，t h ea b i l 时o fa c st of i r m 也eb e s ts o l u t i o n i s s i g n i f i c 龇t l ye t l j l a n c e d t h ep a p e rf i l n h e rs t u d i e d 恤m e o r yo f a c s n e c h o o s i n go f s o m ek e yc h a p 雠 i nt h ea l g o 删mw a sa n a l y s e d 、i t l le x p e r h n e n t s a j m i n ga tt l l em a i nf l a w so ft l l e a 】g 鲥廿1 m ，s u c ha sl o wc o n v e r g e n c es p e e da n d1 0 c a l0 p t i n l i z a t i o n ，s o m ei i n p r o v e d a c st os o l v ec o m b i n 砒o r i a lp m b l e m s 、眦i 1 1 仃o d u c e d i n 也ei m p l e m e m a t i o no f a c s i n 血e 咖i c a 直c o m b i n a t o r i a lp r o b l e mt r a v e l i n g m 北京工业大学工学硕士学位论文 s a l e s m a i lp r o b l e m ( t s p ) ，t 1 1 ec o n v e r g e l l c es p e e dh a sa l w a y sb e e i lac o n c e i 舡m i n g a ts o l v i i l gt l l i sp m b l e m ，t l l ep a p e rp m p o s e da 虹n do fe v o l u t i o n a la c ab 鹤e do n m i i l i m 啪s p 删n g 船e u t i l i z 吨l er e l a t i o n s h i pb e t 、】l r e m em i l l i n n u ns p a n n i n g 仃e ea i l dt l l eb e s tr o u t et or e s 位c tt l l es e 盯c h j n gs c o p eo fe a c h 趾t ，( h en e w a l g o r i 协m i m p r o v e dt l l es 训n gs n 吼e g ) r 锄dc o n s e q u e n t i ys a v e dt l l ec o m p u t a 廿o n a lt i m eo n m ep a t l l sn l a tc a nn o tb eo n 出eb e s tr o u t e i ts i g 耐矗c a n n y 面p r o v 。d 出eb a s i ca c s b y a c c e l e r a t i i l g 也ec o n v e r g c es p e e da n de i l l l a i l c 证gt h ep r e c i s i o n t h es i m u l a t i o n p r o v e dm a tt 1 1 en e wa l g o r i 也mi m p r o v 锚b o mt l l ee 佑c i c n c y 髓dt 1 1 eq u a l i t yo fr e s u l t s t h es t 孤d a r da c au s e dt og e t k e yw o r dm u l t i c a s tr o u d n g ；q o s ；a c a ；s p a n n i n gt r c e ；c o m b i i l a t o r i a lo 州m i z a t i o n p r o b l 锄；t s p i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：尸莹 日期 关于论文使用授权的说明 本人完全了解j e 宝王业太堂有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：尹荜譬 导师签名；淋毒j 日期 第1 章绪论 1 1 引言 第1 章绪论 世界上第一台数字电子计算机自1 9 4 6 年问世以后，在最初1 0 年内，计算机 和通信没有什么关系。当时计算机以“计算中心”的服务模式工作。直到1 9 5 4 年，一种收发器的终端制造出来，人们才首次使用这种终端通过电话将数据发送 到远地的计算机。此后，计算机开始与通信结合，计算中心的服务模式逐渐让位 于计算机网络的服务模式。实践表明，计算机网络的产生与发展，对人类社会的 发展产生了深远的影响。 采用计算机网络通信，不仅大大提高通信线路的利用率，改善通信质量，而 且为实现全数字化、宽频带、多媒体信息的高速传输以及计算机、电视和电话的 三合一奠定了基础。这种相互连接的计算机信息网络，把距离和时间缩小到零， 通过计算机网把整个社会结构紧密结合在一起，将改变人们的生活、学习和工作 方式。 1 1 1 网络数据传输方式 网络数据传输主要有单播、组播和广播技术兰种方式： 单播( u n i c a s t ) 传输；在发送者和每一接收者之间实现点对点网络连接。如 果一台发送者同时给多个接收者传输相同的数据，也必须相应地复制多份相同的 数据包。如果有大量主机希望获得数据包的同一份拷贝时，将导致发送者负担沉 重、延迟长、网络拥塞，为保证一定的服务质量需要增加硬件和带宽。 广播( b r o a d c a s t ) 传输：是指在i p 子网内广播数据包，所有在子网内部的主 机都将收到这些数据包。广播意味着网络向子网每一个主机都投递一份数据包， 不论这些主机是否乐于接收该数据包。所以广播的主要缺点就是每个广播都要发 送数据至所有机器，消耗了所有机器上的资源，即使数据要被网络中大多数机器 所丢弃，使用范围非常小，只在本地子网内有效，通过路由器和交换机网络设备 控制广播传输。 组播( m l t i c a s t ) 传输：在发送者和每一接收者之间实现点对多点网络连接。 如果一台发送者同时给多个接收者传输相同的数据，也只需复制一份相同的数据 包。它提高了数据传送效率，减少了骨干网络出现拥塞的可能性。主要用于视频 会议等应用场合这种应用需要将一份数据同时发送给多个用户。而多播技术 会议等应用场合一这种应用需要将一份数据同时发送给多个用户。而多播技术 北京工业大学工学硕士学位论文 具有带宽利用率高、减轻主机路由器的负担、避免目的地址不明确所引起的麻 烦等优点，从而满足这种应用。 单播传送发送数据的多个拷贝，每个拷贝发送到一个接收者，主机轮流发送 数据的拷贝，网络分别将它们转发至每个接收者，主机一次只能发送至一个接收 者。而组播传送则只把发送数据的个拷贝发送到多个接收者，主机发送数据的 一个拷贝，可同时发送到多个接收者。网络在每个接收者的最后一个路由器或主 机复制它，在一个给定的网络上每一个包只传送一次。 1 1 2 组播技术引入的必要性 随着多媒体网络的不断发展，各种宽带网络应用层出不穷。视频会议、数据 和资源分发、网络音频应用、网络视频应用、多媒体远程教育等宽带应用都对现 有宽带多媒体网络的承载能力提出了挑战。采用单播技术构建的传统网络已经无 法满足新兴宽带网络应用在带宽和网络服务质量方面的要求，因为服务器必须为 每一个接收者提供一个相同内容的口报文拷贝，同时网络上也重复地传输相同 内容的报文，占用了大量资源。虽然口广播允许一个主机把一个口报文发送给 同一个网络的所有主机，但是由于不是所有的主机都需要这些报文，因而浪费了 网络资源随之而来的是网络延时、数据丢失等问题。在这种情况下组播应运而生， 它的出现解决了一个主机向特定的多个接收者发送消息的方法。组播网络中，即 使组播用户数量成倍增长，骨干网络中网路带宽也无需增加。简单来说，成百上 千的组播应用用户和一个组播应用用户消耗的骨干网带宽是一样的，从而最大限 度地解决目前宽带应用对带宽和网络服务质量的要求。 1 2 组播技术 1 2 1 简介 组播技术可形象地描述如下：假设一个企业分布于各地的子公司( 两个以上) 之间需要通过i n t e n l e t 进行实时的信息交换( 数据、声音、图像) ，他们的计算机 可能不属于同一个物理网络，甚至不属于同一自治系统，这种通信的特点是“多 点”式的。子公司发出的数据希望其它子公司都能收到，而总部发出的指示全体 子公司都应收到。这种多点通信方式为组内广播，即组播技术，也称为多播技术， 多目网关技术。 组播传输可在数据链路层和网络层实现，支持的媒体类型包括以太网、f d d i 和a t m 。大多数路由器提供商支持口组播，不支持d 组播的网络通过组播隧 第l 章绪论 道技术传输组播信息包。 组播首先要解决发送给谁的问题。按不同应用项目( 如体育、文艺、娱乐或 学习等) 进行分组，组成员要向组播路由器通过i g m p ( h e r l l dg r o u pm a n a g e i i l e n t p m t o c 0 1 ) 协议进行注册登记，用户主机发出请示，提出具体组播地址。口组播的 地址采用d 类i p 地址确定组播的组。在i n t 锄e t 的“小数点”表示法中，组播 地址范围是从2 2 4 0 o 0 到2 3 4 2 5 5 2 5 5 2 5 5 。为发送一份口组播数据包，发送者 要确定一个合适的组播地址，这个地址代表一个组。然后，组播数据通过普通的 i p 发送操作发送出去。 其次要解决的问题是如何接收组播信息。有时在同一网段中有多个组播组的 成员。对于信息的发送方来说相当简单，但接收方却十分复杂。为了能够正确地 接收感兴趣的组播信息数据包，主机上的应用首先要申请特定组播组的成员。这 种申请通过m t 锄e t 组管理协议( i g m p ) 传送到本网段上的路由器完成，如有必要， 相关的信息还可能要传送到发送方的路由器，这取决于使用的组播路由协议。这 一步完成，接受主机的网络接口卡开始侦听与新组播组地址相关的数据链路层组 播地址。路由器把发送方送来的组播数据包一跳一跳地发送到有接收者的网段上 的路由器，局域网路由器根据组播信息包中的组地址转换出与它相关的数据链路 层地址，并用这个地址建立数据链路层的报文。接收方的网络接口卡和网络驱动 程序侦听这个地址，收到该组播包后，将i p 层的组播数据包取出，传向上层 t c p 口协议堆栈，从而使数据适合用户的应用。 第三个问题是用户主机在注销对某个组的兴趣时如何通知组播路由器。如果 接收方使用的是i g m p v 2 ，会主动地通知路由器离开。但如果是i 佃v 1 主机，注 销就不会通知路由器，这时服务器要在一定时间后向本网段发出查询，接受主机 的应答，若无用户应答，路由器就认为不再有接收者，不会再向该网段上转发组 播信息。 第四个问题是组播信息的转发，要根据所使用的组播路由协议建立组播转发 树。根据该转发树进行组播信息的转发，当某个处于转发树中的路由器收到一个 组播信息后，对要转发的组播包进行拷贝和转发。如果路由器为最后一跳，组播 包就以广播的方式传送到该网段中各主机接收者。 1 2 2 组播的特点 与单播应用相比，使用组播技术分发信息常常能从本质上减少整个网络带宽 的需求，一个典型的例子就是音频与视频网。这些例子常用来说明组播的优点， 体现在以下几个方面。 北京工业大学工学硕士学位论文 ( 1 ) 带宽 对于音频与视频网来说，大量的用户经常要在大致相同的时间里访问相同的 信息，如果使用i p 单播，网络带宽的消耗就会里线性增长。由于典型的m p e g 一2 视频信息流需要大约l 5 m b i t s 的带宽用于流畅且逼真的影像传送，显然用m 组播来发送节目是一种明智的选择。因为重复数据流被单一传送所代替，从而使 得网络带宽得到了更有效的使用。 ( 2 ) 服务器负载 如果音频与视频网的网络运营商继续使用单播传送机制，随着用户的增长， 它将需要不断增加它的实时音频服务器的能力和数量以适应连接用户的增长。在 单播情况下，服务器必须为每一个收看节目的用户都发出各自的信息流。当连接 用户数目增加时，服务器负载也急剧增加。当服务器负载增加到一定程度，服务 器就不能再发出信息流。而如果运营商使用i p 组播来发布它们的节目，那么只 有单个实时数据流要成为连接所有用户的节目源头。用这种方式，运营商不需要 购买越来越多高性能的服务器以满足用户数目增长的需求。很明显，i p 组播提 供的主要优势在于通过大大减少需要转发和处理的数据量，从而降低了对所需服 务器的性能要求。 尽管在网络里使用口组播会带来许多好处，但是就像任何技术一样，这项 技术也有它的局限性和不如人意的地方。我们需要清楚地知道这些局限性，尤其 是如果正在开发新的使用坪组播的应用程序，更要弄清楚这些局限性以及会带 来的问题。组播的主要缺点包括不可靠的信息包传送、信息包复制。 ( 1 ) 不可靠的信息包传送 和i p 单播一样，i p 组播是天生不可靠的。只有在通过使用第4 层的 t c p ( 或者其他的更高层协议) 后，口单播数据流才被认为是可靠的。然而，由于 i p 组播假定一对多的通信方式，它不使用t c p 所固有的端到端的机制。口组 播信息包典型地使用用户数据报协议叫d p ) ，那是一种尽力而为的协议。这意味 着组播数据包有可能发生丢失、延迟、重复以及乱序到达的现象。组播应用不能 期望数据得到可靠的传送而应据此进行相应的设计。要么接受丢失，要么在应用 层或通过一种在u d p 之上可靠的组播协议进行某种程度的处理。可靠的组播仍 是一个有待研究的领域，期望在这一领域取得更大进展。 ( 2 ) 组播信息包的复制 单播和组播之间的关键差别是路由器主动地把组播信息包的拷贝发送到多 个接口。这增加了多个拷贝的组播信息包到达某一种接收点的可能性。设计优良 的i p 组播应用应该作好准备检测并处理随时到达的复制信息包。同时，当将 相同的内容传送给多个用户时，口组播虽然能明显地减少带宽要求，但要重点 4 第l 章绪论 注意的是，在一些情况下，在某些特定的点路由器的工作负载可能反而会加大。 当路由器把单个数据流复制成多个输出数据流以便将该数据送交给多个下游用 户时，这个复制过程就成为附加在路由器上的工作负载，它需要在整个网络中加 以考虑。如果一种路由器没有一个有效的复制机制，则当输出接口数很大时该路 由器负载将明显增加。例如，一些旧的组播转发代码执行程序要求路由器为每 一个附加输出接口复制组播信息包，这个过程需要从存储器分配新的信息包缓冲 区并且把原始的数据信息包拷贝到新的缓冲区以便转发到输出接口。如果输出接 口数目很大，这个复制过程对路由器上的c p u 和存储器资源是一个很大的负 担。要尽量实现零拷贝的转发，来降低对资源的要求。 1 3q o s 组播 1 3 1 定义 q o s 即服务质量( q u a l 时o f s e i c c ) ，指发送和接收信息的用户之间以及用户 与传输信息的服务网络之间关于信息传输的质量约定。o o s 包括用户要求和网络 服务提供者的行为两个方面。用户要求指用户在j m e r i l e t 网络上进行多媒体通信 时所要求的服务类型以及相应的传输性能和质量。用户最关心的是端到端的 q o s ，由于多媒体应用的自身特点，所以多媒体应用对口网0 0 s 的要求同时体 现在：丢包率、传送时延、时延抖动、网络带宽等方面。 1 3 2 多播机制中q o s 的必要性 在实际的网络中，使用多播机制，q o s 路由技术是必需的。在多播中，需要 消耗比最大努力的单播多得多的路由器资源。因此，多播的使用者应该比单播使 用者交更多的费用。然而，目前此方面的讨论还不多，也没有提出有效的协议。 可是，预支持多播的供应商迫切需要种合理的计费系统。对于多播通信而言，从 经济的角度看，提供一种用户选择一条较少费用的路径也是必需的。否则，多播 供应商可能会选择较高费用的路径，因而给用户带来不必要的费用。选择满足用 户q o s 要求的路径的方法是不可避免的。沿着满足q o s 要求的路径，通过信令的 方法( 也就是q o s 路由技术) 可以找到这样的路径。正如前面所述的，多播中除了 资源预留功能外，合并功能和复制功能也是必需的。加入一个未授权的接收者向 发送者发出一个q o s 请求。因为对路径上的路由器而言，要判断一个请求授权与 否比较困难，故而q o s 请求被执行。因此，从发送者到一个未授权接收者之间的 路径上，q o s 也被实现。 5 北京工业大学工学硕士学位论文 1 3 3 服务质量要求 多媒体应用对服务质量的要求可归纳为下述几个主要方面。 ( 1 ) 通信带宽 时间相关媒体对网络的通信带宽有最低要求。原理上，时间无关媒体对网络 带宽不应提出最低通信带宽要求，但是为了保证媒体流之间同步，多媒体中的时 间无关媒体也存在最低信带宽问题。例如，当电视上的字幕是独立于电视信号传 输的，那么字幕信息的传输必定有通信带宽的最低要求，否则字幕和电视信号的 同步就无法保证。 多媒体的数据速率是各个媒体流数据速率之和。多媒体的数据速率分平均速 率和峰值速率2 种。网络的通信带宽应达到或超过给定多媒体的数据速率。非压 缩媒体的传输要占用极大的通信带宽。因此，信息压缩是分布式多媒体系统的一 种关键技术。压缩媒体的带宽呈波峰状变化，对网络提出了最高通信带宽和最低 通信带宽的要求，因此，q o s 控制就成为分布式多媒体系统的一种非常复杂的技 术。 ( 2 ) 延时 不同多媒体应用对延时有不同的要求。对于视频点播系统，视频流从视频服 务器传送到用户的机顶盒，其延时的大小对用户观看节目没有多大影响。但是， 对于交互多媒体系统( 如视频会议和协同计算环境) ，延时是一项重要指标，延时 过大将影响交互效果。 网络延时由2 部分组成：第一部分为信号传播时间；第二部分为网络设备( 交 换机，路由器) 排队调度时间。信号传播延时是固定的、不可改变的，但排队调 度时间可通过服务质量控制来保证。延时要求一般以延时上界( 最大延时) 的形式 给出，网络通过服务质量控制保证媒体流的传输不超过延时上界。 ( 3 ) 延时抖动 延时抖动( j m 砷对时间相关媒体来说是一项极重要的传输性能参数。延时抖 动指媒体流各单元之间的时间差异。例如，数字声音采样间隔为1 2 5 1 l s ，通过网 络传输之后，如果它们之间的时间在1 1 0 1 4 0 u s 之间，那么延时抖动为1 5 l l s 。 延时抖动可在输出端设置缓冲器来消除，抖动越大，缓冲器要求越多。用这 种方法消除延时抖动将增加媒体流的端到端延时，因此，网络应通过服务质量控 制来最大可能的抑制延时抖动。 ( 4 ) 数据丢失率 相对于二进制数据传输来说，音频和视频对数据丢失率的要求比较低，话音 最大可按收的数据丢失率可达1 0 ，视频可达l o 。这就减轻了网络对差错控 制的要求。 第1 章绪论 1 ，3 4 研究现状 多媒体高速网络的研究开发近几年进展得异常迅速，q o s 问题的研究已经有 了一些基本成果，这些成果大量地反映在i e e ed 虾o c o m 每年的会议论文集和 1 1 1 t e n l e t 的i e t fr f c ( r e q u e s tf o rc o 衄e n t s ) 标准草案中。但是，目前q o s 的研究 开发在很多方面仍然是开放的，其主要问题有：( 1 ) 网络系统状态和链路带宽容 量变化的不确定性，传输通路端到端带宽预留缺乏有效的保证；( 2 ) q o s 选路、 资源预留和信息传输调度算法的复杂性，还不能适应高速信息传输处理时间的要 求；( 3 ) q o s 要求所导致的资源利用的无效性，不能充分利用网络资源提高网络 的吞吐量；( 4 ) q o s 控制方案基本上还是静态方案，缺乏有效的动态控制方案；( 5 ) 一些基本研究成果主要存在于理论中，还没有形成专利或技术产品。现存的网络 交换机或路由器还不能完全保证用户服务质量，缺乏简单而有效的控制方案和算 法的实现，传输管理与控制有待改进。在i n t c m e t 中，为了使p ( i t c r i l e t p r o t o c 0 1 ) 网络不仅能传输非实时的数据信息，而且还能传输实时的多媒体信息，国际上的 标准化组织，如i t u 、i e t f 等已开始起草并完成了一些用于口实时通信的标准， 如实时传输协议实时控制协议r t p 瓜t c p ( r c a l t i i n ep r o t o c 0 a 1 i t i m ec o n 仃o l p r o t o c 0 1 ) 、资源预留协议r s v p ( r e s o u r c er 鼯e n r a t i o np r o t o c 0 1 ) 等。这些协议和标准 对用户服务质量控制的研究提供了一定的基础，但还有很远的路要走。 q o s 控制主要包括信息传输的实时性和信息丢失的管理和控制等问题。在多 媒体网络中，不同用户可能有不同的传输要求。例如，视频和音频的传输有实时 的要求，超时的信息不能使用，但同时可以容忍某种程度的信息丢失；而数据的 传输则不容许信息的丢失，但传输的时延则不成问题。因此，要保证信息传输的 实时性和丢失的综合要求是多媒体网络传输控制的一个重要问题。 新开发的路由技术不再仅仅是为数据传输找到一条通道就行，还需要考虑所 选路径的传输容量和服务质量，即具有q o s 能力的路由算法，并且还得要分析 全网负荷，以平衡网络中各条通道的数据流量，此外，不论是对单播还是组播、 域内还是域问路由，都要求路由算法具有快速收敛性和高校的路由表查询技术。 具有q o s 和流量均衡能力的路由算法探索及相应的规范的制定将是未来的研究 热点之一。 北京工业大学工学硕士学位论文 1 4 组播路由协议 1 4 1 源基树协议与共享树协议 源基树协议采取为群组中的每一个组播源建立一棵组播树的策略。这种协议 能够为每个源端提供优化的组播树，同时有利于网络负载的平衡。但是，为群组的 每个源端分别建立组播树会使组播路由表的大小正比于互联网中的网络数与群 组数的乘积，所以这类协议的规模伸缩性( s c a l a b i l i t y ) 不好。源基树协议比较适 合于一点到多点的组播通信。 共享树( s h a r e dt r e e ) 也称为核基树( c o r eb a s e dt r e e ) ，其基本思想是尽可 能地让群组的所有源端共享同一个转发树。共享树协议建立一棵植根于被称为汇 聚点( r e n d e z v o u sp o i n t ) 的核心路由器( c o r er o u t e r ) 的树。这种策略的优点是 每个路由器无需存储( 源，组) 对的组播路由表，而是存储形如( 牢，组) 的表项，咏” 号表示任意源，因此存储开销只正比于群组数，故有较好的规模伸缩性。共享树算 法的问题在于通信量在汇聚点的集中导致瓶颈效应，同时若享树往往难以做到为 所有源节点提供最优路由。c b t 和简单组播等协议属于共享树类型的协议。p i i s m 严格讲属于混合型协议，因为它的主体是共享树协议，但是它也支持共享树 向最短路径树切换。 1 4 2 域间协议和域内协议 域间协议和域内协议是与协议层次化相关的两个概念。在广域网环境下，组 播的关键问题是提高协议的规模伸缩性( s c a l a b i l i t y ) 。最自然的解决规模问题 的有效方法是设计层次路由协议( h i e r a r c h i c a lr o u t i n gp r o t o c o l s ) 。层次路由 协议的基本思想是把节点划分成一些区域( 如管理域a d s ，或自治系统a s s ) ，每个 区域被赋予一个全局唯一标识，域内的拓扑结构对域外节点是透明的，即一个节 点仅知道它所在域的拓扑信息，对其它域的拓扑结构细节不了解。工作在域间的 组播协议( 即域问协议，i m 昏d o m a i nr 0 1 j t i l l gp m t o c 0 1 s ) 负责维护和传播域互联信 息。相对的域内协议( i n t r a - d o m a i nr o u t i n g p r o t o c 0 1 s ) 负责在一个区域内的组播。 p i m 、c b t 协议是单层的，而互联网事实上由多个自治系统构成，网络的异构性使 象p i m 、c b t 这类单层协议不能普遍部署，所以它们本质上属于域内协议。 1 4 3 协议无关协议与协议相关协议 协议无关的含义是指组播协议与标准单播选路协议共存的能力。例如，p i m 可以使用任何选路协议( 如r i p 或o s p f ) 来维护单播路由，它本身并不传播单播路 第1 章绪论 由，而是假设每个路由器已经运行着一个维护单播路由的常规选路协议。但是象 m o s p f 这样的组播路由协议，使用了o s p f 的拓扑数据库为每个源端产生一个组播 树。所以，m 0 s p f 是与单播路由协议o s p f 相关的。研究人员已经注意到这样一个更 广范围的问题：“组播路由如何从常规路由协议收集到的额外信息受益”。如何 处理组播协议与单播协议的关系，仍然是一个值得深入研究的课题。 1 4 4q o s 组播协议与非q 0 s 组播协议 根据协议是否支持q o s 特性，它们又可分为q o s 敏感的( q o ss e i l s m v e ) 和非 q o s 敏感( q o so b l i v i o u s ) 的。q o s 组播试图建立一棵从源端到成员节点的满足一定 q o s 请求的优化组播树。非q o s 组播则采用传统的i p 尽力而为( b e s te 怕r t ) 机制传输 组播数据。 1 5 组播的应用 由于组播能有效减少网络和主机开销，较单播和广播有其独特优越性，因此， 组播已经得到了广泛的应用。组播应用大致可以分为三类：点对多点应用，多点 对点应用和多点对多点应用。 1 5 1 点对多点应用 点对多点应用是指一个发送者，多个接收者的应用形式，这是最常见的组播 应用形式。典型的应用包括： 媒体广播：如演讲、演示、会议等按日程进行的事件。其传统媒体分发手段 通常采用电视和广播。这一类应用通常需要一个或多个恒定速率的数据流，当采 用多个数据流( 如语音和视频) 时，往往它们之间需要同步，并且相互之间有不同 的优先级。它们往往要求较高的带宽、较小的延时抖动，但是对绝对延时的要求 不是很高。 媒体推送：如新闻标题、天气变化、运动比分等一些非商业关键性的动态变 化的信息。它们要求的带宽较低、对延时也没有什么要求。 信息缓存：如网站信息、执行代码和其他基于文件的分布式复制或缓存更 新。它们对带宽的要求一般，对延时的要求也一般。 9 北京工业大学工学硕士学位论文 事件通知：如网络时间、组播会话日程、随机数字、密钥、配置更新、有效 范围的网络警报或其他有用信息。它们对带宽的需求有所不同，但是一般都比较 低，对延时的要求也一般。 状态监视：如股票价格、传感设备、安全系统、生产信息或其他实时信息。 这类带宽要求根据采样周期和精度有所不同，可能会有恒定速率带宽或突发带宽 要求，通常对带宽和延时的要求一般。 1 5 2 多点对多点应用 多点对多点应用是指多个发送者和多个接收者的应用形式。通常，每个接收 者可以接收多个发送者发送的数据，同时，每个发送者可以把数据发送给多个接 收者。典型应用包括： 多点会议：通常音视频和白板应用构成多点会议应用。在多点会议中，不 同的数据流拥有不同的优先级。传统的多点会议采用专门的多点控制单元来协调 和分配它们，采用组播可以直接由任何一个发送者向所有接收者发送，多点控制 单元用来控制当前发言权。这类应用对带宽和延时要求都比较高。 资源同步：如日程、目录、信息等分布数据库的同步。它们对带宽和延时的 要求一般。 并行处理：如分布式并行处理。它对带宽和延时的要求都比较高。 协同处理：如共享文档的编辑。它对带宽和延时的要求一般。 远程学习：这实际上是媒体广播应用加上对上行数据流( 允许学生向老师提 问) 的支持。它对带宽和延时的要求一般。 讨论组：类似于基于文本的多点会议，还可以提供一些模拟的表达。 分布式交互模拟( d i s ) ：它对带宽和时延的要求较高。 多人游戏：多人游戏是一种带讨论组能力的简单分布式交互模拟。它对带宽 和时延的要求都比较高。 j a ms e s s i o n ：这是一种音频编码共享应用。它对带宽和时延的要求都比较 高。 1 5 3 多点对点应用 多点对点应用是指多个发送者，一个接收者的应用形式。通常是双向请求晌 应应用，任何一端( 多点或点) 都有可能发起请求。典型应用包括： 资源查找：如服务定位，它要求的带宽较低，对时延的要求一般。 数据收集：它是点对多点应用中状态监视应用的反向过程。它可能由多个传 感设备把数据发回给一个数据收集主机。带宽要求根据采样周期和精度有所不 1 0 第l 章绪论 同，可能会有恒定速率带宽或突发带宽要求，通常这类应用对带宽和延时的要求 一般。 网络竟拍：拍卖者拍卖产品，而多个竟拍者把标价发回给拍卖者。 信息询问：询问者发送一个询问，所有被询问者返回应答。通常这对带宽的 要求较低，对延时不太敏感。 j u k eb o x ：如支持准点播( n c a r - o n d e m a n d ) 的音视频倒放。通常接收者采用 “带外的”协议机制( 如h t t p 、r t s p 、s 耵p ，也可以采用组播方式) 发送倒放请 求给一个调度队列。它对带宽的要求较高，对延时的要求一般。 1 6 本文研究内容 q o s 路由的任务就是在网络中寻找一条路由，满足用户对线路的带宽、延时、 延时抖动、费用的要求，即向用户提供端到端的服务质量保证。基于多个不相关 可加度量的q o s 路由问题是n p 完全问题，目前采用的方法多为启发式算法，如遗 传算法、模拟退火算法等，但是在q o s 路由问题上它们都有自身难以克服的缺陷， 要么太复杂，要么太费时。 2 0 世纪9 0 年代，意大利学者m d o r i g o ，v m a n i c z z o 等人通过模拟自然界蚂 蚁寻径的行为，提出了一种全新的启发式算法一一一蚁群算法( a 卫tc o l o n y a 1 9 0 r i 姗，a c a ) ，较强的鲁棒性、寻径过程的并行性以及易于与其他启发算法结 合的优越性，使得蚁群算法被广泛用于解决各种具有n p 难度的问题。本文提出了 一种基于蚁群算法并考虑多个路由限制的优化q o s 路由问题的方法。实验仿真表 明：该算法能有效地求解q o s 路由问题。 本论文共分为5 章： 第l 章是绪论，对计算机网络的组播通信进行了综述。主要介绍组播引入的 背景、特点、组播技术，还叙述了q o s 的相关内容、研究现状、组播路由协议和 应用。 第2 章主要介绍了蚁群算法的基本原理和模型实现，以及蚁群算法的特点等。 第3 章研究了如何将蚁群算法应用于o o s 组播路由问题中。端到端的延迟和 延迟抖动是两个较关键的性能参数。改进路径选择策略、优化信息素更新公式， 仿真结果表明利用蚂蚁算法的并行性寻找最优解的能力大大提高。 从第4 章开始对蚁群算法进行了进一步的理论研究。通过实验分析了算法中 几个关键参数的选择。并且针对基本蚁群算法的主要缺陷，如收敛速度慢和易于 陷入局部最优等问题，系统地介绍了用于求解组合优化问题的几种改进蚁群算 法。 北京工业大学工学硕士学位论文 蚁群算法在组合优化领域代表问题t s p ( t m v e l i i l gs a l 础a 1 1p m b l 锄，旅行推 销商问题) 中的应用。其收敛速度一直是人们关心的问题。针对蚁群算法的一些 不足，第5 章提出基于最小生成树的进化型蚁群算法。它利用了最小生成树与最 优路径之间的关系限制了蚂蚁在每一个城市的搜寻范围，进化了寻优策略，节省 了在不可能构成最优路径的路段上的计算时间，提高了运算速度，克服了以往蚁 群算法的计算时间长、精度低的缺点，使得蚁群算法有了显著的提高。 最后，对本文所作的工作作