（通信与信息系统专业论文）多目标最优化选播路由算法.pdf

摘要 摘要 随着i n t e m e t 商业化应用的飞速发展和多媒体应用的不断增长，网络服务需求 对网络服务容量提出了更高的要求。为了增强服务的可用性、改善网络的流量分 布，通常的做法是在网络中复制服务器。选播就是一种支持分布式服务器复制的 服务，i p v 6 已经正式将选播服务定义为一种标准的通信服务。随着选播服务应用 的不断发展，人们对选播路由算法提出了更多更高的要求。本文在总结、分析前 人研究的基础上，围绕选播路山问题，对多目标最优化选播路由、区分服务模型、 遗传算法等多个方面进行研究，提出了一些新方法和新思路。 首先，选播路由的实际应用涉及到路由选择和服务器选择两个方面，而且往 往很难仅凭单项指标来衡量选播路由的优劣。为了比较全面地评价选播路由，必 须考虑多项指标，因此选播服务在本质上是多目标最优化问题。奉文在分析了传 统的单目标最优化选播路由算法存在问题的基础上，提出了多目标最优化的选播 路由算法，可以同时对多个最优化选播目标进行优化，使选播能满足更多应用的 需求。 第二，在商业化的互联网中，如何为用户提供不同等级的服务质量，如何提 高网络资源利用率、优化网络配置等问题是选播服务必须面对的问题。本文在分 析和对比两种常见的q o s 服务模型综合服务模型和区分服务模型的基础上， 考虑到在实际的应用中，服务数据服务质量比请求数据服务质量更加重要的特点， 采用下行数据的服务质量作为最优化目标函数，上行数据的服务质量作为约束条 件的方法，提出了基于区分服务模型的多目标最优化选播路由算法。可以根据网 络服务提供商与用户签订的服务协议，为用户提供不同等级的满足要求的服务质 量。 第三，针对上面所提出的两种多目标最优化模型，研究了如何利用遗传算法 来求解多目标无约束最优化选播路由和多目标多约束最优化选播路由。根据网络 拓扑性质，解决了遗传算法中编码方式、初始化种群选择方法、约束处理、适应 度函数、交叉策略、变异规则、修复函数等关键问题。为了使仿真环境能够尽量 的接近真实的网络环境，本文采用w a x m a n 和t r a n s i t s t u b 两种网络拓扑模型进行 仿真实验。验证了算法是快速收敛的，能够快速有效地找到选播路，并能在两种 网络拓扑模型环境下为用户提供不同等级满足要求的服务质量，有效地提高了网 摘要 络资源利用率，平衡了网络负载，减少了网络拥塞。 关键词：选播，多目标最优化，非支配排序遗传算法，区分服务，俄罗斯玩 偶模型 a b s n a c t a b s t r a c t w i t ht h eq u i c kd e v e l o p m e n to fi n t e m e tu s e di nt h eb u s i n e s s ，a n dm p i dg r o w t ho f m u l t i m e d i aa p p l i c a t i o n ，n e t w o r ks e r v i c er e q u i r e m e n t se x c e e dt h ec a p a b i l i t i e so ft h e n e t w o r k ，w h i c hc a u s e sag r e a ti n f l u e n c eo na p p l i c a t i o no fq u a l i t yo fs e r v i c e i no r d e rt o e n h a n c et h es e r v i c eu s a b i l i t ya n di m p r o v en e t w o r kf l o wd i s t r i b u t i o n ，w e u s u a f l y d u p l i c a t es e l v e r si nt h en e t w o r k a n y c a s ts e r v i c ei san e w s e r v i c em o d e lw h i c hs u p p o r t s d i s t r i b u t e dd u p l i c a t i o n w i t ht h ec o n t i n u a la p p l i c a t i o no fa n y c a s ts e r v i c e ，p e o p l er e q u i r e m o r ea n dh i 曲e rr e q u i r e m e n ta b o u tt h ea n y c a s tr o u t i n ga l g o r i t h m i nt h ep a p e r , w e d i s c u s st h em u l t i - o b j e c t i v eo p t i m i z a t i o na n y e a s tr o u t i n ga l g o r i t h m ，t h em o d e lo f d i f f e r e n t i a t e ds e r v i c ea n dg e n e t i ca l g o r i t h mb a s e do nt h ep r e d e c e s s o r s a tl a s t ，w ew i l l p r o p o s es o m en e wm e t h o d sa n di d e a s f i r s t l y , t a k i n gi n t oa c c o u n tt h ep r a c t i c a la p p l i c a t i o ni nt h ea n y c a s ts e r v i c e s ，a n y c a s t i n v o l v e st h es e l e c t i o no fr o u t i n ga n ds e r v e s i ti sd i f f i c u l tt oe v a l u a t et h e a n y c a s tr o u t i n g a l g o r i t h mw i t hs i n g l eo b j e c t i o n s oa n y c a s ti sam u l t i - o b j e c t i v eo p t i m i z a t i o np r o b l e mi n i t se s s e n c ea n a l y s i so ft h et r a d i t i o n a ls i n g l eo b j e c t i v eo p t i m i z a t i o na n y c a s tr o u t i n g m g o r i t h mp r o b l e m s w ep r o p o s e dm u l t i - o n e c t j v eo p t i m i z a t i o na n y c a s tr o u t i n g m g o f i t h m sa c c o r d i n gt oi n c r e a s et h et a r g e tf u n c t i o no ft h ew a y i tc a l lo p t i m i z ea n u m b e ro fo n e c t ss y n c h r o n o u s l yw h i c hm a k e sa n y e a s ts a t i s f ym o r ea p p l i c a t i o n s e c o n d l y , a i m i n ga tt h ei m p r o v i n g o ft h er a t i oo fi n t e r a c tr e s o u r c ea n do p t i m i z a t i o n o fi n t e m e ts c h e m e ，w ep r o p o s em u l t i o n e e t i v eo p t i m i z a t i o na n y c a s tr o u t i n ga l g o r i t h m b a s e do nt h ed i f f e r e n t i a t e ds e r v i c e ，w h i c hc a l lp r o v i d ed i f f e r e n tq u a l i t yt r a n s m i s s i o n s e r v i c e sf o rd i f f e r e n tu s e r s t h em o d e la d o p t st h em e t h o dt h a tt h ed i r e c t i o no fs e r v i c e d a t ai su s e dt ot h eo b j e c t i v ef u n c t i o na n dt h ed i r e c t i o no fr e q u e s ti su s e dt ot h er e s t r i c t e d c o n d i t i o n t h em o d e lc a np r o v i d ed i f f e r e n ts e r v i c et od i f f e r e n tc l a s su s e r sa c c o r d i n gt o t h ea g r e e m e n t ，w h i c hs i g n e db yu s e r sa n dt h ei n t e r a c ts e r v i c ep r o v i d e r t h es i m u l a t i o n r e s u l t ss h o wt h a tt h em e t h o d 啪b a l a n t et h en e t w o r kl o a da n dr e d u c et h en e t w o r k c o n g e s t i o ne f f e c t i v e l y t h i r d l y , a i m i n ga tt h ea b o v et w om o d e l s ，w es t u d yh o w t ou s et h eg e n e t i ca l g o r i t h m s o l v et h e m a c c o r d i n gt ot h ec h a r a c t e ro fn e t w o r kt o p o l o g y , w ep r o p o s eo u rc o d i n g i m o d e ，s e l e c t i o nm e t h o d ，c l - o s s o v e r ，m u t a t i o n w ed oo u rs i m u l a t i o no nt w ot o p o l o g i e s m o d e l s ：w a x m a na n dt r a n s i t s t u b t h es i m u l a t i o nr e s u l ts h o w st h a tt h em e t h o dc a l l f i n da n y c a s tr o u t eq u i c k l ya n de f f e c t i v e l y i ta l s os h o w st h a tt h em o d e lc a np r o v i d e d i f f e r e n ts e r v i c et od i f f e r e n tc l a s su s e r s ，b a l a n c et h en e t w o r kl o a da n dr e d u c et h e n e t w o r kc o n g e s t i o ne f f e c t i v e l y k e yw o r d s ：a n y c a s t ，m u l t i o b j e c t i v eo p t i m i z a t i o n ，n o n d o m i n a t e ds o r t i n gg e n e t i c a l g o r i t h m ，d i f f e r e n t i a t e ds e r v i c e ，r u s s i a nd o l lm o d e l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我同工作的同志对本研究所做韵任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：窒l 列日期：加诏年r 月拥 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名： 童j 塑导师签名：驾垫! 型 日期：厕年，月冶b 第一章绪论 1 1 研究背景和意义 第一章绪论 随着计算机网络的迅速发展，各种类型的应用层出不穷。譬如镜像服务器、 域名服务、镜像网站、移动i p 、网络视频会议、网络音频视频广播、多媒体远程 教育、远程会诊等的应用越来越广泛，这些应用导致网络服务需求已超过了网络 的服务容量。虽然其不影响在一些传统的网络服务如电子邮件、文件下载等方面 的应用，但对一些实时服务如视频会议、l p 电话等产生了严重影响。 为了增强服务的可用性和改善网络的流量分配，通常的做法是在网络中复制 服务器，复制服务器技术主要有本地复制和分布式复制两类。这样对网络用户提 出的服务要求，可以通过其中任意一个服务器来提供服务。现在网络上的服务， 如w w w 的“m i r r o r ”站点、s o c k 服务器等都属于此类结构。为研究此类网络通 讯，近年来，人们提出，“选播”的通讯模式。在r f c1 5 4 6 【l j 中，已经提出了选 播( a n y c a s t ) 的概念。相对传统的单播【2 】、多播【2 】和广播等通信模式，选播是一种新 的网络服务通信模式，已经被i p v 6 定义为标准的通信服务。选播服务是指从一台 主机向一组目的主机中的任何一台，最好是仅仅一台主机传送数据，这组目的主 机用一个选播地址表示。例如，多个w w w 镜像服务器可以共享一个选播地址， 为了得到所需要的信息r 如天气预报、股票数据、视频下载等) ，用户可以通过选搔 服务机制获得这些服务器中“最近”的一个提供服务。选播对于改善网络和服务 器的负载平衡、简化某些网络应用有着广泛的前景。例如：支持分布式的复制服 务器、选择“最优”的服务、更有效地支持组播通信树的建立；电子商务、全球 信息网等更容易在全局上实现；移动评节点更方便获得就近服务而不需要注册、 更换代理等。事实上，随着网络应用的快速发展，所有这些分布式的电子商务、 移动通信等高效、方便、快捷的服务足人们所迫切需求的，而选播恰恰可以更好 地提供这些服务。 选播路由算法就是根据实际应用的要求，确定路由选择的最优化目标和所满 足的约束条件，并最终确定满足最优化目标和约束的最终解。而现在对选播路由 算法的研究大多都是单目标无约束或单目标多约束的。例如，将链路利用率、最 短路径、最小跳数、时延等其中的一个作为最优化目标函数，其余的需求部分或 电子科技大学硕士学位论文 全部转化为约束条件或无约束。而这样找到地选播路并不一定能够提供快速、有 效的服务，并不能满足实际应用的要求，因此需要通过不断变换目标函数和约束 条件多次测试来选择可行路。在选播路由问题中，往往很难仅凭单项指标来衡量 选播路的好坏，为了比较全面地评价某个选播路由的优劣，必须考虑多项指标， 而这些指标又常常是互相冲突的。在这种情形下的优化问题比单目标情形要复杂 得多。现在对多目标最优化选播路由算法的研究才刚刚起步，现在的处理方式大 多是采用线性加权法。根据用户对各个目标的喜好程度，对各个目标加上不同的 权系数，最后就将多目标转化成单目标的问题。显然，如果用户对各个目标的偏 好十分明确清晰而足以给出这种完全有序关系，则这样的做法是有效的。然而， 多目标规划问题的难点之一就在于由于问题本身的复杂性，各个偏好信息往往不 是十分明确的，这样就为目标权值的确定带来了困难。这就是本文将要讨论的多 目标最优化选播路由算法问题。 服务器负载在目前已经商业化的互联网条件下，为用户提供高质量的网络服 务并不意味着所有参数都最优化，而是指网络服务提供商根据与用户签订的服务 协议提供满足要求的传输服务。现在，如何为用户提供不同的q o s 服务质量是互 联网络面临的一个重要问题。目前，互联网工程任务组( m a - f t h ei n t e r a c t e n g i n e e r i n gt a s kf o r c e l 已经建议了多种服务模型和各种机制，如区分业务模型 ( d i f f s e r v ) i ”、综合服务模型( i n t e r s e r v ) 【4 j 等，以满足网络业务的q o s 需求。在实 现这些服务机制时，首先要在进行通信的双方之间找到条可行的路径，然后才 能在网络资源满足要求的路径上进行资源预留、接纳控制或按流标签转发数据流 等。因此，q o s 路由被认为是保证网络服务质量的个不可缺少的路由技术。重 要的是，q o s 路由能够对业务的多种月务需求提供弹性支持，通过提高整个网络 吞吐量达到网络资源的有效利用，并且通过路由优化达到网络负载均衡的目的。 显然，路由算法在q o s 路由优化中起到了关键的作用。 选播服务在网络中的应用越来越广泛，这就对选播路由算法提出了更高的要 求，包括：( 1 ) 如何满足用户多个指标的需求，即如何设计多目标的最优化选播路 由模型；( 2 ) 如何设计合理有效的选播路由算法来求解多目标最优化选播模型：( 3 ) 如何在不同价格水平上为用户提供具有不同性能参数的传输服务。这不仅意味着 满足不断提高的用户通信要求，而且意味着最大限度地利用网络资源，降低服务 成本。 本课题研究目的是为将来选播通信服务实旌具体应用奠定基础。选播通信服 务的研究对于我国计算机网络技术和其他相关领域的发展具有重要的意义，我们 第一章绪论 追踪世界上网络研究的前沿领域，开展这一领域的研究工作将具有一定的理论价 值和广泛的应用前景。 1 2 选播路由算法的分类 根据选播路由算法的研究现状，本文把选播路由算法按以下三种分类方法进 行分类： 1 ，2 1 从o s i 网络结构模型分类 从o s i 网络结构模型，选播技术目前主要有两个发展方向：一个是在应用层 利用选播概念，通过管理手段实现选播服务、优化网络应用；另一个是在网络层 利用选播路由技术实现选播服务、提高网络通信的效率和鲁棒性。 夺应用层选播 应用层选播是通过一些引导机制为客户提供访问选播服务提供者的方法，而 这些机制并不需要在i n t e r n e t 中增加新的构成或服务，例如不需要改变底层协议、 不涉及路由器的修改、不需要路由系统提供支持等。应用层选播主要研究在当前 使用的路由算法和协议处理策略不变的情况下，在i n t e m e t 中如何实现选播路由服 务。现在应用层的常见做法有三种：用户在每次连接服务器之前逐个测试、目录 服务器和d n s 。显然用户在每次连接服务器之前逐个测试的做法需要用户等待很 长时间。目录服务器的实现方式是目录服务器定期为潜在的用户检测而用户连接 服务器前向目录服务器查询。显然，用户必须首先知道“目录服务器”的位置， 而且每个用户区域内必须有这样的“目录服务器”，每次探测都直接由选播服务器 参与，这样显然是很不方便的。d n s 的多个服务器由一个域名标识，选播服务器 定期探测到潜在用户的距离，并发送给d n s 服务器，用户在解析时获得一个最优 的服务器。这样做同样存在着以下问题：用户需要知道d n s 服务器的位置、每次 探测都直接由选播服务器参与、每次用户访问都必须解析域名。总的来说应用层 选播服务的不足有：n 1 可扩展性差，这是因为应用层选播是通过修改d i g s 实现的， 因此每增加一个相同服务的服务器就要浪费掉一个m 地址，并且要修改d n s 中存 放的内容；( 2 ) 在通信中用户需要知道d n s 服务器的位置；( 3 ) 在网络连接之前d n s 的映射信息就要存在；( 4 ) 每次访问都必须解析域名：( 5 ) 无法判断指定服务器的可 用性。 电子科技大学硕上学位论文 夺网络层选播 选播的初衷是支持分布式复制服务器，在网络上实现负载甲衡。但是处在应 用层的选播无法及时了解网络的动态变化，难以实施进一步的应用。网络层选播 只要求为提供相同服务的一组服务器分配同一个选播地址，由路由控制系统完成 对服务器的查找、定位。由于对服务器的选择完全在网络层完成，不需要用户参 预，也不需要增加新的功能服务器( 如分布式控制器) 。因此，人们开始致力于网络 层选播的研究，主要解决如何为提供服务的主机分配选播地址和对选播数据包进 行正确的转发。在网络层处理选播，有以下一些优点：( 1 ) 用户连接服务器前，不 用进行距离探测，也不用向任何做选择的服务器查询：f 2 ) 选播服务器只定期报告 其状态，不太参与到用户距离的探测；( 3 ) 探测距离过程的开销比应用层小。但其 也同样存在一些问题：( 1 ) 必须分配i p 地址空间；( 2 ) 使用选播寻址需要路由支持； ( 3 ) n 务器选择由网络来做，用户没有参与的可能；( 4 ) 无连接服务；( 5 ) n 络层处理 服务器吞吐率、负载之类的应用层路由指标比较难。针对这些问题，在i p v 6 网络 中已绎x g - j 立的得到解决：( 1 ) l p v 6 已经为选播分配了地址空间：( 2 ) 由于i p v 6 的接纳， 选播已经被路由器厂商逐步接受；( 3 ) 在大多数情况下，用户不参与是一种方便： ( 4 ) 无连接服务可以通过i p 源路由轻松解决；( 5 ) n 络层可以通过选播服务器向路由 器的活动报告，使口选播在一定程度上考虑了这些指标。 而网络层选播的实现在很大程度上取决于对路由的选择，因此，路由算法对 选播通信的实现显得尤为重要，目前针对网络层选播的研究才t 日* j n 起步。 1 2 2 按最优化目标分类 根据最优化目标，可以将选播路由算法分为曲类：单目标选播最优化和多目 标选播最优化。所谓最优化目标是一个尽量争取达到的目标，而目标达到的程度 体现了算法的效率，但最优化目标不是一种硬性指标，目标达到的程度并不影响 算法的可行性。例如，我们以代价作为单一目标，算法求出代价为3 0 的选播路要 明显优于代价为1 0 0 的选播路。 审单目标选播最优化 单目标最优化问题是指仅含有一个目标的最优化问题，其是以牺牲其它代价 为基础来完成此单一目标的最优化，例如把链路利用率、最短路径、最小跳数、 时延等其中一个作为目标函数，其余的需求部分转化为约束条件。根据有无约束 条件，又将单目标最优化选播路由算法分为无约束单目标最优化选播路由算法和 第一章绪论 有约束单目标最优化选播路由算法。所谓约束一种必须严格执行的条件，不满足 约束条件的选播路是无效的。但约束条件通常是达到就好，没有必要很苛刻。比 如，都达到约束条件的时延为3 0 m s 和5 0 m s 的选播路，都是可取的，并不能说时 延为3 0 m s 的选播路优于时延为5 0 m s 的选播路，或者说时延为5 0 m s 的选播路优 于时延为3 0 m s 的选播路。 现在对选播路由算法研究多是单目标的，这样找到的选播路并不一定能够提 供快速、有效的服务，并不一定能满足实际应用的要求，因此需要通过不断变换 目标函数和约束条件多次测试来选择可行路，这样往往需要更大的代价。 夺多目标选播最优化 在选播路由问题中，往往很难仅凭单项指标来衡量选播路的好坏，为了比较 全面地评价某个选播路由的优劣，必须考虑多项指标。多目标最优化指的是含有 多个目标规划的最优化问题。而这几个目标又常常是互相冲突的，在这种情形下 的优化问题比单目标情形要复杂得多，是一个n p 完全问题削。现在对多目标最优 化选播路由算法的研究才刚刚起步，现在的处理方式多是采用线性加权法。根据 用户对各个目标的喜好程度，对各个目标加上不同的权系数，最后就将多目标转 化成单目标的问题。显然，如果用户对各个目标的偏好十分明确清晰而足以给出 这种完全有序关系，则这样的做法是有效的。然而，多目标规划问题的难点之一 就在于由于问题本身的复杂性，各个偏好信息往往不是十分明确的。 1 2 3 按处理模型的算法分类 根据处理模型的算法，可以将选播路由算法分为：启发式算法和遗传算法。 夺启发式算法 启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最 好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径， 提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价 可以有不同的效果。我们先看看估价是如何表示的。启发中的估价是用估价函数 表示的，如： ，加) - g 加) + h ( n )( 1 - 1 ) 其中，o ) 是节点n 的估价函数，9 0 ) 实在状态空间中从初始节点到n 节点的 电子科技大学硕士学位沦文 实际代价， 0 ) 是从n 到目标节点最佳路径的估计代价。在这里主要是 似) 体现 了搜索的启发信息，因为g ( n ) 是已知的。如果说详细点，9 0 ) 代表了搜索的广度 的优先趋势。 启发式算法对模型处理通常先根据约束条件，删除掉不满足条件的链路，而在 实际的需求。对多目标模型的处理，通常是加权处理，这一类问题通常是n p 完全 问题，当网络规模很大时，一般启发式算法只能找到局部最优解，难以找到全局 最优解。 夺遗传算法 遗传算法1 6 1 是模拟生物进化过程的一种并行优化算法，使用于复杂而庞大的搜 索空间中寻找最优解或次优解。遗传算法在搜索过程中，算法自身自动获取和积 累有关搜索空间的知识，自适应地控制搜索过程，不断地缩小搜索过程，从而得 到最优解。遗传算法具有简单、通用、鲁棒性强、并行搜索、群体寻优的特点， 已广泛应用于各种具有n p 复杂性的问题中。 s c h a f f e r 于1 9 8 4 年将遗传算法引入多目标领域，自从1 9 9 0 年以来，其已经成 为多目标优化技术的研究热点。遗传算法是一种群体搜索方法，它可以在一个进 化代中获得多个p a r e t o 优化解。在1 9 9 3 年之后涌现了许多多目标遗传算法，在这 些算法的基础上，有许多具体的工程领域应用成功的实例和对原有算法的改进性 工作。利用多目标遗传算法求解非劣解集是晟近几年新出现的一种求解思路，目 前还处在研究中，但是初步的计算结果非常令人振奋。 1 3 研究现状 选播路由选择的最终e l 标是要在满足应用需求的条件下，使用最少最合理的 网络资源，最大限度的优化网络资源配置。它直接关系到网络效率、网络流量分 配、传输延迟和吞吐量等通信网络的主要技术性能指标。可以说网络最终能提供 什么品质的选播服务，能在多大程度上满足用户的选播服务需求，在很大程度上 取决于路由算法的设计。路由算法对选播通信的实现显得尤为重要，目前针对网 络层选播的研究才刚刚起步。 我们根据前面章节中对选播路由算法的分类，分网络层选播路由算法和应用 层选播路由算法两部分来讨论现有的选播路由算法： 夺网络层选播路由算法 第一章绪论 y a m a m o m 等i7 1 n 提出了种基于r t f ( r o u n dt r i p 啊m c ) 的选播服务器选择策 略。用户的响应时间包括服务器的处理时延和网络的传送时延( 等于请求时延和应 答时延之和1 ，因此路由选择一台服务器不仅需要考虑服务器的负载，同时也要考 虑网络负载情况。他们根据路由器标准的r t t ，提出了一种合理的服务器选择策 略。其方法简单实用，其性能优于单纯的服务器负载策略算法和网络负载算法。 此外，它不要考虑所有的服务响应，其只需处理第一个响应服务器。可以通过第 一个响应，计算出选播组中“最近”的一个服务器。但其算法没有考虑实际应用 中的q o s 服务请求。 w a n gj i m l x i n 【9 】提出了一种选播的o o s 路由算法，首先从链路状态图中去掉不 满足带宽要求的链路，然后用修剪后的图进行路径选择。延迟用跳数来近似估算， 而在多条可行路径中，使用与跳数相关的概率进行选择。这种方式在一定程度上 平衡了链路流量而对于q o s ，实际 并没有过多的保证。例如如果采用固定带宽， 则算法的静态性使其不能真正满足q o s 的动态要求如果用可用带宽，这种动态变 化的带宽参数使维护一张满足带宽要求的全局图开销非常大，而且也很难实现。 文献【1 q 提出一种分布式选播路由街议，该协议包含路由表建奇和数据包转发 两个子协议。路由表建立协议增强了路径选择过程中路由器的有序性，从而避免 路由环的出现。数据转发协议为了平衡网络流，采用一种用于多路选择的加权随 机选择方法。而该方法要占用更多的路由器的存储单元。 d o n gx u 和w e i j i aj i a 在文献f 1 1 1 中利用分布式的接入控制方法，讨论了基 于多个q o s 要求的选播路由问题。提出和分析了一种分布式选播路由协议，该协 议包含路由表建立和数据包转发两个子协议。路由表建立协议增强了路径选择过 程中路由器的有序性，从而避免路由环的出现。数据转发协议为了平衡网络流， 采用一种用于多路选择的加权随机选择方法。仿真结果表明其性能接近考虑了动 态状态信息的网络路由算法，其代价确大大的降低。但文献 1 1 只考虑三个方面的 q o s 要求：路由距离、本地接入记录和可用带宽，没有考虑更多的不同方面的应 用，比如准确性、安全性和不同的服务质量，不能为用户提供不同的服务质量和 安全的服务质量。而且其是通过加权法把多个目标化成了单目标，其实际上也可 以看成单目标问题。 文献【1 2 1 中，提出了一种基于网络层的多目标最优化选播路由算法，最优化的 目标为：虽小化传输时延、最大化可用带宽( 或称最小化带宽利用率) 、快速服务器 响应( 或称为服务器负载) 。因为很难找到同时满足3 个条件的路径，所以对3 个目 标进行了折中处理。通过分析，对每个目标进行线性加权处理，将多目标最优问 电子科技大学硕士学位论文 题，转化成了单目标最优化问题。合成公式以传输时延为主，带宽的利用会增加 链路传输时延，所以其用可用带宽计算出的已用带宽比率来修正延迟值。同样服 务器负载增加也会导致服务时间增加，所以其也被用来修正延迟。并提出了一种 启发式算法a r m m 。其可以有效的找到选播路，可为选播数据报请求的服务数据 提供更好的资源保证。但其做法仍然采用启发式的线性加权法来处理其多目标模 型，仍然存在上面所说的启发式算法的弊端。 文献1 1 3 1 考虑到路由器上的负载处理和计算机网络上的处理单元，提出了负载 平衡的路由选播算法，但对最短延迟路由只提出了一种近似的解决方法。文献1 1 4 1 研究了如何在对当前使用的路由算法和协议处理策略影响不大的情况下在i n t e r n e t 中实现选播路由服务，并设计和实现了用于在i n t e r a c t 的i b mo l y m p i cw e b 站点的 负载分布的基于网络层的选播服务。 夺应用层选播路由算法 c h e n 和m a 0 1 1 5 研究了如何在i p v 6 环境下，如何实现应用层选播服务。首先， 作者提出了p p t ( p r e d i c t e dt r a n s f e r t i m e ) 模型，然后计算出从发送选播服务请求到 收到服务“文件”所需要的总时间。在实际中，用户希望最近的一个复制服务器 为自己提供服务，而在同一个子网中的服务器一般比不同子网中的服务器更能提 供更好的服务。因此，通过给不同服务器赋予不同的权值，来实现对不同服务器 的选择概率。但是，在实际应用中，客户端和服务器端一般是不在同一个子网中 的，特别是在i n t e r n e t 网络环境中。 w u 1 6 1 和他的同事将应用层选播模型应用到视频传送中，例如i n t e r n e t 中的视 频点播。验证了应用层选播服务适应于网络中的视频点播服务，其为视频点播在 i n t e m e t 中占据主导地位打下了良好的开端。文献f 1 7 1 提出了种基于应用层的支 持服务器复制的选播通信方法，并且提出了基于使用选播裁决器的选播域名到多 个口地址映射的实现方法。文献1 1 8 1 提出了一种映射客户端选播请求至“最佳” 分布复制服务器的优化算法，其是基于经济模型和排队理论的应用层选播算法。 针对上面讨论，可知，现有的选播路由算法大多存在以下问题：算法大部分 都忽略了负载均衡的要求，而且还存在以下问题： ( 1 ) 部分选播路由算法在构建选播路由模型的时候，只有一个最优化目标，例 如链路利用率或者最短路径等，其余的需求部分转化为约束条件，这样导 致可能找不到一条满足约束的路。就是找到一条选播路，也很有可能不能 很好地反应用户的实际需求，导致需多次不断调整目标函数和约束条件才 8 第一章绪论 能找到满足用户需求的选播路。 ( 2 ) 有些选播路由算法虽然确立了多个最优化目标，但是采用传统方法求解， 即把多个最优化目标转化为一个最优化目标，这样很大程度_ 卜依赖于预先 定义的用户参数，而且最后求出的最优解只有个，通常不得不多次运算， 求出多个最优解再进行比较选择。其实质还是单目标最优化的选播路由算 法。 f 在目前已经商业化的互联网中，没有考虑根据网络服务提供商与用户签订 的服务协议，为用户提供不同等级的满足要求的服务质量。基本的网络提 供机制是：从具体的商业服务策略出发，在不同的价格水平上提供不同性 能参数的参数服务。 f 4 )没能考虑如何平衡网络中的负载，优化网络配置。现在一般的选播路由算 法会因网络中有一些服务请求过多，导致某些链路网络拥塞，而其相邻部 分却有大量链路资源闲置。 1 4 研究内容和研究成果 通过以上讨论，确定本文的研究思路为：针对单目标最优化选播路由算法所 存在的问题，提出了多目标最优化的选播路由模型，并利用遗传算法来求解多目 标模型；在此基础上考虑如何为用户提供不同等级的服务质量，如何平衡网络中 的负载，提出了基丁二区分服务模型的多目标最优化选播路由算法。 本文主要研究内容和研究成果包括： 夺对现有的选播路由算法进行系统的分析分类 分析现有的选播路由算法，按o s i 网络结构模型、最优化目标和处理模型的 算法三种方式进行了划分，并讨论在三种分类方式下现有的选播服务的处理方法 和存在的弊端。然后讨论了选播路由算法的研究现状，分析了现有的选播路由算 法所存在的问题。 夺建立多目标的选播路由算法 分析单目标最优化选播路由算法所存在的问题和用户需求，建立了多目标最 优化的选播路由模型，给出了求解此多目标最优化选播路由模型的算法n s g a - i i ， 并验证了n s g a - 1 i 算法是可以有效的找到选播路，而且其算法是收敛的。 电子科技人学硕士学位论文 夺遗传算法n s g a - 的应用 通过对近年所应用得的多种遗传算法进行分析比较，选用n s g a i i 作为求解 多目标最优化选播模型的算法，以求获得收敛性较好分布均匀的解。针对网络模 型的实际情况，将算法和数学模型结合实现，得到较好结果。并解决了算法中的 编码方式、初始化种群选择、适应度函数、交叉策略、变异规则、修复函数，以 及算法的收敛性问题。 夺提出r 基于r d m 模型的多目标最优化选播路由算法 为了给用户提供不同等级的服务质量，平衡网络中的负载，提出了以r d m 带 宽分配模型为基础，的多目标最优化选播模型。此多目标保证各个等级服务的基 础上，确保关键性的服务。同样，利用n s g a 1 1 算法来求解此多目标模型，并将 求解出的选播路于传统的路由算法b s p 和w s p 在w a x m a n 和t r a n s i t s t u b 两种网 络拓扑模型上进行了比较，证明算法是有效的。 夺规划多目标模型时采用r 逆向链路信息 考虑在一般的选播服务请求中，服务数据比请求数据更加重要，而且在一条 链路中，两个方向上的可用带宽和双向流量是不相同的等凼素。在构建多目标模 型时，考虑到上面的因素，将请求数据作为约束，而将服务数据作为最优化的目 标。 夺利用w a x m a n 和t r a n s i t s t u b 网络拓扑模型进行仿真 因为现在路由算法的仿真所利用的网络拓扑模型多是w a x m a n 模型，而 w a x m a n 模型有自身的缺点，并不能真实的反映真实的网络模型。本文利用新的模 型如t r a n s i t s t u b 模型，更能反映真实的网络拓扑。 1 5 论文结构 本文的结构安排如下： 第一章作为整个论文的绪论，分析论文的研究背景和研究意义，并对现有 的选播路由算法进行分析分类，讨论了现有路由算法存在的问题。然后，阐述了 本论文的研究内容和研究成果；最后简述论文的总体结构。 第二章介绍了关于多目标最优化路由算法的基本概念和多目标最优化中各 第一章绪论 种解的基本含义，为求解多目标最优问题打下基础。然后重点介绍了传统求解多 目标问题常用的方法，线性加权法，并给出了两种确定权系数的方法：老手法和a 方法。最后给出了求解多目标最优化问题的遗传算法。 第三章根据分析的单目标最优化选播路由算法所存在的问题和用户需求，建 立多目标最优化的选播路由模型，结合所建立的模型，给出了求解此模型的 n s g a - 1 i 。根据网络拓扑性质，提出了遗传算法的编码方式、初始化种群选择方 案、适应度函数、交叉策略、变异规则、修复函数等问题。然后通过仿真实验， 在w a x m a n 和t r a n s i t s t u b 两种网络拓扑模型下，验证了n s g a i i 算法是收敛的， 并且能够有效地找到选播路。 第四章重点讨论了如何有效地为用户提供不同等级的服务质量，平衡网络 中的负载。根据对比分析，提出了以r d m 带宽分配模型为基础的多目标最优化选 播模型。同样，利用n s g a - i i 算法来求解此多目标模型，并将求解出的选播路于 传统的路由算法b s p 和w s p 在w a x m a n 和t r a n s i t s t u b 两种网络拓扑模型上进行 了仿真比较，可以证明我们的算法是有效的。 第五章总结本文所做的工作和工作展望。 1 1 电子科技大学硕士学位论文 第二章多目标最优化理论 早在1 9 世纪末，法国经济学家p a r e t o 就从政治经济学的角度提出了多目标最 优化的思想。但是，多目标最优化的真正兴旺发达时期，并且正式作为一个数学 分支进行系统地研究，是在2 0 世纪七十年代以后的事情。从1 9 7 2 年开始，以多 目标决策命名的国家学术会议已召开了十多次。到现在为止，多目标最优化不仅 在理论上取得很多重要成果，一套平行于单目标最优化的理沧正在形成和日臻完 善，而且在应用上其范围也越来越广泛，多目标决策作为一个工具在解决工程技 术、经济管理、军事和系统工程等众多方面的问题也越来越显示出它的强大生命 力。 2 1 多目标优化的基本概念 多目标数学最优化问题【1 9 j 的数学模型可以写成如下标准形式 y 一“如 o ) ，2 0 ) ，0 ) 】r ( 2 1 ) 5 0 岛o 。s 0 ( i = 1 ，2 ，一，m ) 其中x = k ，r 彤，pz2 。符号v m j n 表示对向量形式的p 个目标 【，1 0 ) ，- ，丘o ) 】7 求最小。为方便起见，记 ，0 理 ，1 旺) ，一，丘o ) r ( 2 - 2 、 o n x l & 0 ) s0 ，i = 1 ，m ， ( 2 - 3 ) 则得到多目标最优化模型( 记为v m p ) 的向量形式： 名d 一 协 x l 第二章多目标晟优化理论 2 2 多目标最优化问题各种解的定义 多目标( 向量) 最优化问题与通常的单目标( 数值) 最优化问题的一个本质不同点 是，问题中的目标是一个向量函数。为要比较这些向量函数值的“大小”，首 先需要引进向量空间中向量间的比较关系，即“序”的关系。 定义2 - 1 设口= h ，- - ，) 7 ，b = ，屯) 7 是1 7 1 维欧氏空间r 8 中的两个向量。 ( 1 ) 若a 。= 岛o = 1 ，m ) ，则称向量n 等于向量b ，记作n = b 。 ( 2 ) 若q 乜( f = 1 ，m ) ，则称向量n 小于等于向量b ，记作ae b 或b a 。 ( 3 ) 若廿is 岛o = 1 ，m ) ，并且其中至少有一个是严格不等式，则称向量口小 于向量b ，记作a 0 ， 称a 为正向量；若a e 0 ，称a 为正定向量。 定义2 - 2 设量d = 扛i g 。0 ) 0 , i = l ，卅) ，若对任意的工d 均有 f ，( z ) f ( i ) ，= 1 ，p ( 2 - 5 ) 则称i 为最优化问题的绝对最优解。 对于多目标最优化问题的解，绝对意义的最优解实际并不存在 对多目标最优化问题的解给出新的定义。 定义2