（计算机应用技术专业论文）遗传算法在复制组播服务器选择中的应用研究.pdf

硕士学位论文 m a s t e r st h e s i s 捅要 组播服务器复制是一种改善组播服务性能、提高可扩展性的新技术。它 存在多个放置在网络不同位置并且提供同种服务的服务器，依据拓扑结构的 特点和当前网络负载状况，它们将分别为不同的客户群提供组播服务。很显 然，一旦引入多台服务器，就必然引起如下问题：为了达到网络整体收盏最 大化目标。将如何对客户端分组，将不同的子组分配给某台服务器；如何在 一个子组内建立组播树。这一问题属于复制组播服务器选择问题。它已被证 明是n p 问题。现有解决这一问题的算法，存在着适用范围窄或求解质量不 高的缺陷。针对这种状况，本文提出了基于遗传算法的复制组播服务器选择 算法g a r m s s ( g e n e t i ca l g o r i t h mb a s e d r e p l i c a t e d m u l t i c a s ts e r v e r s e l e c t i o n ) 。 本文首先将问题空间映射到染色体空间，即将合法的选择方式视为染色 体，并对其进行编码。我们设计了二级染色体编码方案。第一级编码表示服 务器分配方式，第二级编码表示各子组组播树。在第二级编码中，提出了随 机组播树生成算法d r m t ( d i j k s t r a - b a s e dr a n d o mm u l t i c a s tt r e e ) ，它利用 d i j k s t r a 算法和随机扰动生成丰富的子组组播树，满足遗传算法的要求；同时， 这一算法所生成的组播树都是合法的，避免了对非法编码的检查和修复，减 小了实现难度，加快了生成速度。对于生成的组播树，我们提出了以路由矩 阵进行存储的方法，这种方法既能表达丰富的信息，同时又具有矩阵操作简 单易行的特点。 针对求解目标，我们设计了整合的适应度函数。通过选取不同的参数， 它不仅可以体现平均接收速率或公平性的单个目标，还可同时表达多个目标， 扩大了算法的适用范围。g a r m s s 算法的选择操作采用最佳个体保存法， 交叉操作对第一级编码实行随机一点交叉，变异操作对第一级编码实行随机 一点变异，交叉和变异后代的第二级编码利用d r m t 算法重新生成。交叉、 变异操作的实质是对原有的服务器选择方式进行合法的重组，以期产生更好 的选择结果。 硕士学位论文 m a s t e r st h e s i s 为深入研究g a r m s s 算法的性能，本文通过大量实验将它与目前广泛 使用的最短路径法和最宽路径法进行了对比。实验分别比较了在稀疏网络和 密集网络中的各种配置下，三种算法对三组适应度参数的求解质量。实验结 果表明，g a r m s s 算法对优化目标的求解具有绝对优势，并且它在提供备 份路由、网络负载均衡等方面也有较好的表现。 关键词：组播服务器复制复制组播服务器选择组播树遗传算法编码 适应度 i i a b s t r a c t m u l t i c a s ts e w e r r e p l i c a t i o ni sa n o v e lt e c h n i q u ef o rm u l t i c a s tt oe n h a n c et h e p e r f o r m a n c ea n ds c a l a b i l i t y i t 、v o r k si nt h ew a y t h a tm u l t i p l es e r v e r sp r o v i d i n g t h es a _ r n es e r v i c ea td i f f e r e n tp o s i t i o n sd e l i v e ri n f o r m a t i o nt ot h ed i f f e r e n tc l i e n t s g r o u p ss i m u l t a n e o u s l ya c c o r d i n g t ot h en e t w o r kt o p o l o g ya n dl o a d s e r v e r s e l e c t i o ni st h ep r i m a r yi s s u eo fm u l f i c a s ts e r v e rr e p l i c a t i o n ，a n d i tl e a d st o d i f f e r e n tn e t w o r kp r o f i t n l i sp r o b l e mi sc o m p o s e do ft w op a r t s o n ei sc l i e n t s g r o u p i n g ，w h i c hr e f e r st ot h a tc l i e n t s s e r v e db yt h es a m es e r v e rb e l o n gt ot h e s a n l eg r o u p ；t h eo t h e ri st ob u i l dam u l t i c a s tt r e ef o re a c hg r o u p r e p l i c a t e d m u l t i c a s ts e r v e rs e l e c t i o nh a sb e e np r o v e dt ob en p - h a r d d u et ot h ec o m p l e x i t y , c u r r e n t a l g o r i t h m s a r ee i t h e ru s e di nf ln a r r o wc o n t e x to rh a r dt o g e t t h e s a t i s f a c t o r ys o l u t i o n t h i sp a p e rp r e s e m san e wa p p r o a c hu s i n gg e n e t i ca l g o r i t h mg a r m s s ( g e n e t i ca l g o r i t h m b a s e d r e p l i c a t e d m u l t i c a s ts e r v e r s e l e c t i o n ) t o h a n d l e r e p l i c a t e dm u l t i c a s t s e r v e rs e l e c t i o n at w o l e v e lc o d i n gs c h e m ei sd e v e l o p e dt o m a pt h ea p p l i c a t i o ns o l u t i o ns p a c ei n t o t h ec m o m o s o m es p a c e t h ef i r s tl e v e l c o d e r e p r e s e n t s s e r v e ra l l o c a t i o n a n dt h es e c o n dl e v e lc o d ee s t a b l i s h e s a m u l t i c a s tt r e ef o rc a & g r o u p an e w a l g o r i t h md r m t ( d i j k s l r a - b a s e dr a n d o m m u l t i c a s tt r e e ) u t i l i z i n gd i j k s t r aa l g o r i t h ma n dr a n d o md i s t u r b a n c ei sp r o p o s e d t oc r e a t ear a n d o mm u l t i c a s tt r e e d r m td o e sn o tn e e dt od e t e c ta n dr e p a i r i n v a l i dc o d e ；h e n c ei tf a c i l i t a t e st h ei m p l e m e n t a t i o na n da c c e l e r a t e s c r e a t i n g p r o c e s s t h em u l t i p l em u l t i c a s tt r e e si nd i f f e r e n tg r o u p sa r es t o r e di na s t r u c t u r e c a l l e d r o m i n gm a r x ”r o u t i n gm a t r i xp r o v i d e sac o n v e n i e n tm e a n st oe x t r a c t i n d i v i d u a lm u l t i c a s tt r e ea n d e x p r e s se d g e s h a r i n g i n f o r m a t i o n a ni n t e g r a t e df i t n e s sf u n c t i o ni sd e s i g n e dt oi n d i c a t eo p t i m i z e do b j e e t b y v a r i o u sf i t n e s sf u n c t i o np a r a m e t e r s ，i tc a l ld e n o t en o to n l ys i n n eo b j e c ts u c ha s a v e r a g er e c e i v i n g r a t eo rf a i r n e s sb u ta l s o m u l t i o b j e c t ，t h e r e f o r e i t g i v e s i i i 硕士学位论文 m a s t e r st h e s i s f l e x i b i l i t yt ot h ea l g o r i t h m e l i t i s tm o d e li su s e di ns e l e c t i o no p e r a t i o nt or e m a i n t h eb e s ts o l u t i o n t h ec r o s s o v e r o p e r a t i o ne x c h a n g e sp a r t i a lo f t h ef i r s tl e v e lc o d e a tt h er a n d o mc r o s sp o i n t t h em u t a t i o no p e r a t i o nr a n d o m l ys e l e c t sag e n ei nt h e f i r s tl e v e lc o d ea n d c h a n g e si ti n t oa n o t h e rg e n e b o t h c r o s s o v e ra n dm u t a t i o nu s e d r m t a l g o r i t h mt or e b u i l dm u l t i c a s tt r e e sf o ro f f s p r i n g c r o s s o v e ra n d m u t a t i o n t o g e t h e rp r o v i d e as e a r c h i n g c a p a b i l i t y t h a tr e s u l t si n i m p r o v e dq u a l i t y o f s o l u t i o n t h ee x t e n s i v es i m u l a t i o n si ns p a r s ea n dd e n s en e t w o r k sc l e a r l yd e m o n s t r a t e t h a tt h ep r o p o s e da l g o r i t h mo u t p e r f o r m st h eh e u r i s t i ca l g o r i t h m s ( s h o r t e s tp a t h a l g o r i t h ma n dw i d e s tp a t h a l g o r i t h m ) i nt h e s e n s e o fy i e l d i n g r a g h q u a l i t y s o l u t i o n s i na d d i t i o n ，i ta l s os h o w sb e t t e rp e r f o r m a n c ei n p r o v i d i n gb a c k u p r o u t i n ga n d l c a db a l a n c e k e y w o r d s ：m u l t i c a s ts e r v e rr e p l i c a t i o n ，r e p l i c a t e dm u l t i c a s ts e r v e r s e l e c t i o n ， m u l t i c a s tt r e e ，g e n e t i c a l g o r i t h m ，c o d i n g ，f i t n e s s 硕士学位论文 b , t a s t e r st h e s i s 郑重声明 本人的学位论文是在导师指导下独立撰写并完成的，学位论 文没有剽窃、抄袭、造假等违反学术道德、学术规范和侵权行为， 本人愿意承担由此产生的法律后果和法律责任，特此郑重声明。 签名： 剑左 时间：碰麴 硕士学位论文 m a s t e r st h e s i s 第1 章前言 本文力图利用遗传算法求解复制组播服务器选择问题。研究的主要目标 是：探讨遗传算法与复制组播服务器选择结合的具体途径，从而使遗传算法 成为解决这一网络技术问题的一种可行且有效的算法。 下面，我们将结合本文所研究问题的技术背景、研究现状，简要论述本 研究的意义，并对本文的主要研究内容、结构作初步介绍。 1 1 组播服务器复制的引入 作为一种具有前沿性的研究课题，对组播服务器复制的研究是由当前计 算机网络迅猛发展的现状所催生的。这一研究的目的，在于进一步开掘组播 服务的潜能，以应对急剧增长的网络业务。 众所周知，随着计算机网络的普及，以多媒体数据流为基本特征的种种 新型业务不断出现，如网络视频点播、网络游戏等。它们对网络服务质量有 着高带宽、实时性、抖动小等方面的严格要求。如不能满足上述技术要求， 这类业务的市场前景将受到严重影响。实际上，计算机产业界在为互联网的 高速发展感到欣喜的同时，已经感受到网络流量急剧增长这一现实的严重压 力。 多媒体数据流服务，尤其是多媒体视频流服务的出现，使得当前网络应 用背景与上个世纪七十年代设计t c p 口协议的基本假设有较大差异。在这种 情况下，甚至有人持一种悲观态度，认为利用目前的网络设施，无法从根本 上解决多用户、高带宽的多媒体服务。然而，无论从网络技术研究者还是从 设备提供商的角度来看，传统的基于t c p i p 协议的网络都不可能在短期内被 简单地抛弃。鉴于此，如何在现有t c p i p 协议网络上，通过局部改进，实现 多用户并发多媒体视频流服务一直是近年来网络研究者、电信运营商和设备 制造者关注的问题。 经过多年的讨论与实践，目前，以节省网络带宽资源为特征的组播 ( m u l t i c a s t ) 被认为是解决多用户并发视频流服务的一个有效方案。组播服 l 硕士学位论文 m a s t e r st h e s i s 务的核心思想是通过聚合方式，将来自多个客户端相同、重复占用网络资源 的请求合并成一个请求提交给服务器，减少来自客户端的总体请求数量【1 5 。 组播是一种多点投递方式。当一组主机需要通信时，它们协商选择一个共同 的组播地址，建立一棵组播树。若构造的组播树是源分布树( s o u r c e d i s t r i b u t i o nt r e e ) ，源端服务器是组播树的根结点，组播成员是组播树的叶子 结点。服务数据依次通过组播树的边和内部结点，最终从根结点传送到各个 叶子结点。由于组播树中的每一条链路上，对同一内容的数据只存在一份供 组播接收端共享的拷贝，因此节省了网络带宽。 然而，组播方案在实现节省网络资源目的的同时，通常也会带来相关问 题。例如，目前关于一个组播组服务速率的确定方法有多种策略，其中应用 最广泛的是采用单一服务速率，即该组播树中的瓶颈链路( 最小带宽链路) 带宽 6 。该方法可以成功地解决一些问题，但其缺点是比较明显的：当客户 端数量巨大时，采用该策略进行组的管理和成员信息维护，所带来的开销会 急剧增加；特别是，当组中成员的接入带宽相差甚远时，最大服务速率将被 接收能力最低的客户端所局限，这种现象相对具有较高带宽接收能力的客户 端是不公平的。正是由于单服务器组播存在上述问题，在组播网络中采用分 布式多服务器复制正逐渐成为组播网络应用发展的一个趋势 7 1 1 】。组播服务 器复制( m s r ，m u l t i c a s ts e r v e rr e p l i c a t i o n ) ，即是组播研究衍生出来的问题， 它将目前单服务器组播，推进为分布式多服务器组播。它的提出，旨在优化 一般性组播方案所提供的节省网络资源的模式，不仅进一步提高网络资源的 利用率，而且对公平性等方面的问题同样予以较为充分的注意。 多服务器复制的基本方法是：多个服务器定期交换信息，通过严格的同 步操作，保证服务器内存储的信息内容一致。依据网络拓扑结构的特点和当 前网络负载状况，它们将分别为不同地客户群提供服务。 一个大型组播网络如果采用了上述的服务器复制技术，就存在几个具体 问题需要研究：第一、网络中使用几个复制服务器最合适；第二、每个用户 如何选择最高效的服务器，其评价标准是什么；第三、整个网络服务的最大 收益的计算规则如何定义，以及如何达到全网络的最大收益；第四、组播服 务器在网络中如何分布将有利于达到网络最大收益等。 2 硕士学位论文 m a s t e r st h e s i s 组播服务器复制既是在大规模组播应用中的一个工程问题，同时也是关 于已有网络运营的最大收益问题。因此，针对该问题研究需要最优化计算的 理论分析支持，该问题的求解结果对网络服务提供商具有较大的工程指导价 值s 显然，在给定的网络环境中，复制组播服务器选择( r m s s ，r e p l i c a t e d m u l t i c a s ts e r v e rs e l e c t i o n ) 就成为采用多服务器组播提高网络服务效率、实 现网络收益最大化的核心问题。 1 2 复制组播服务器选择 在复制服务器组播中，每个客户端应该隶属于一个的组播子组，每个服 务器对一个子组内的用户进行组播。不同的客户端分组方式对于网络服务效 率及收益具有直接影响，因此就存在服务器选择问题。这一问题可以简要地 描述如下：如何选择合理的客户端分组方式，如何在每个子组中建立一棵组 播树，使得整个网络的收益最大。 以下用图1 1 所示的组播应用说明该问题。c o c 5 是组播服务的客户端， 它们分别采用应用广泛的网络接入技术：电话拨号、n i s d n 、a d s l 和以太 网等。若只有一个服务器s o 提供组播服务，全体客户端将都连接到s o 。由于 该组播组的瓶颈带宽是5 6 k b p s ( 由c o 所决定) ，因此最终各客户端的实际接 收速率都为5 6 k b p s 。该速率对c 0 而言确实达到了其理想速率，但其它用户 则没有充分利用自身设备的接入能力。 图1 1 组播服务器复制 若趴卯和j 2 三个服务器作为复制服务器莱同参与组播，以上问题则可 以得到改善。例如：构成三个组播子组：c o 和e l 由s o 提供服务；c 2 和c 3 由 j l 提供服务；c 4 和c 5 由毋提供服务，则c o c 5 的接收速率依次为5 6 k p b s 、 5 6 k p b s 、1 2 m b p s 、1 2 m b p s 、1 0 m b p s 和1 0 m b p s 。这样，从用户角度来看， 满足了享受高带宽的需求；从网络运营商来看，达到了更好地利用了网络资 源，提高收益的预定目标。也会存在其它的分组方案，同样可以提高网络效 率。 图1 1 示例的网络结构还比较简单，其具体表现是：路由器之间的连接 简单、任意服务器与客户端间仅存在一条路径。而现实的网络中，无论路由 器的数量还是拓扑结构都十分复杂，从而一个服务器到一个客户端可能有多 条路径，选择哪条路径收益晟大，也即在一个子组里建立一棵什么样的组播 树，这同样属于复制组播服务器选择问题所研究的范围。 目前对复制服务器选择的研究相对薄弱，并且主要是研究单播( u n j c a s t ) 环境中的选择问题 1 2 1 7 1 。复制组播环境中的服务器选择优化问题已被证明 是一个n p 问题 7 。由于n p 问题的不可计算性，目前尚没有一种针对该问 题的完美解决方案。现有的解决方案主要分为两类：一类是针对特殊拓扑结 构网络使用的专用算法【7 8 】，另一类是针对一般结构网络求出问题次优解的 启发式算法 7 1 1 。显然，这两类方法都还存在一定的局限性。专用算法由于 对网络拓扑结构的前提条件太严格，在工程中难以满足，使用该类算法的实 际可应用范围比较窄，不利于推广。而启发式算法的本身求解质量难以保证。 此外，n p 问题的搜索空间是随着问题规模的增大而急剧增长的。启发式算 法一般是串行算法，不利于并行搜索，难以迸一步提高求解速度和质量j 在 这种情况下，我们试图引入遗传算法来克服上述算法的局限。 1 3 遗传算法与复制组播服务器选择 遗传算法( g a ，g e n e t i ca l g o r i t h m ) 是h o l l a n d 教授在上个世纪七十年代 提出、发展起来的一种仿生计算方法 z 8 1 9 。遗传算法首先将应用问题的求 解空间映射到一个特定的染色体编码空间，然后通过对染色体的选择、杂交 硕士学位论文 m a s t e r st h e s i s 和变异操作来获取问题空间中的最优解或次优解。遗传算法通过染色体编码 技术和繁殖机制来求解优化问题，实践证明它具有不受搜索空间限制和固有 并行性的优点。目前遗传算法已被广泛地应用于求解组合优化、机器学习、 人工智能、自适应控制、人工神经网络训练等问题中 2 0 2 2 1 。 鉴于遗传算法在最优化求解领域的突出表现，它已经被广泛地应用到单 播或组播服务的i n t e r n e t 路由算法研究中 2 3 3 3 。从理论上说，该算法应当 能够应用于服务器选择优化问题的解决。然而，由于复制组播服务器选择优 化问题自身具有特殊的复杂性，尤其是如何在这一工程问题中实现遗传算法 例如建立复制组播服务器选择阻题解空间到染色体空间的映射方案等一 一具有较大的难度，我们尚未发现利用遗传算法解决复制组播服务器选择的 科研论文。 本文探讨了复制组播服务器选择的遗传算法实现g a r m s s ( g e n e t i c a l g o r i t h mb a s e dr e p l i c a t e dm u l t i c a s ts e r v e rs e l e c t i o n ) 。论文提出了一种从复 制组播服务器选择问题的解空间到染色体空间的映射方案；建立了服务器分 配和路由选择的量化评价标准( 适应度函数) ：实现了染色体选择、交叉、变 异操作，从而使遗传算法在最优化求解的功能在组播服务器选择中得以实现。 多组实验数据表明，利用遗传算法求解组播服务器选择问题一种可行且具有 较高求解质量的算法。与目前流行的两种启发式算法最短路径法和最宽路径 法相比，g a - r m s s 算法具有明显的优势，它能较好地优化各种网络收益目 标，此外它还能提供多个质量近似的备份路由方案以应对网络故障，以及实 现负载均衡的功能。在本研究中，网络的实际情况得到比较充分的重视，因 此这一研究成果本身具有较强的应用价值；同时，实现遗传算法最核心的环 节，即编码问题在本论文中得以解决，为本方案的实施提供了一种基础，在 此基础上，本方案其能够针对网络的具体情况进行调适，因此具有广阔的应 用前景。从理论研究的角度看，遗传算法在复制组播服务选择中的实现，对 相关领域的研究也具有参考意义。 硕士学位论文 m a s t e r st h e s i s 1 4 本文的结构与章节安排 围绕遗传算法在复制组播服务器选择问题中的实现，本文作如下章节安 排： 第二章给出问题的模型，讨论复制组播服务器选择的解空间到 g a r m s s 算法染色体空间的映射问题染色体编码。 第三章建立评价服务器分配和路由选择的适应度函数，设计o a r m s s 算法的选择、交叉、变异三种遗传操作。 第四章将g a r m s s 算法与最短路径法和最宽路径法的性能进行比较， 三种算法在多种网络环境配置下的实验结果表明g a r m s s 较高的求解质量 和鲁棒性。 第五章对本研究的创新与贡献进行总结，并指出将来应进一步深入的问 题。 6 硕士学位论文 m a s t e r st h e s i s 第2 章g a - r m s s 的染色体编码实现 遗传算法是模拟生物进化过程中的一种并行、随机、自适应最优化搜索 算法，具有对全局信息有效利用的能力，它只需搜索少数结构就能反映搜索 空间的大量区域。利用初始染色体群体的适应度信息，通过简单的选择、交 叉和变异操作，遗传算法能自动获取和积累有关搜索空间的知识，自适应地 控制搜索过程，不断地缩小搜索空间，从而得到问题的优化解，甚至最优解。 我们已知道，遗传算法主要是通过遗传操作对群体中具有某种结构形式 的个体( 染色体) 施加结构重组，从而不断搜索出优化的个体以逐渐逼近最 优解。由此可见，遗传算法不能直接处理问题空间的参数，必须把它们转换 成遗传空间由基因按一定结构组成的个体。这一转换操作就叫做编码。 编码是利用遗传算法求解r _ m s s 问题所面临的首要问题，它将p j ，i s s 的 一个合法的客户端分组及各子组的组播树表示成遗传空间的一条染色体。在 遗传算法的初始阶段，随机生成数量众多、形态丰富的染色体，为以后的遗 传操作提供基础。编码也是g a r m s s 中比较困难的一步，因为它既要能够 表示合法的解，又要能有利于生成多样的解。g a - k i v i s s 的染色体包含各子 组的组播树，因此也就包括树的编码，而树具有一些特殊性质，它的编码具 有相当的难度，已有的研究都没能很好地解决这个问题。 本章主要讨论g a - r m s s 的染色体编码问题，将复制组播服务器选择的 解空间映射到遗传算法的染色体空间，同时也提供树编码的有效方法。首先 我们将给出r m s s 问题的模型，它定义了合法的服务器选择解( 分组和组播 树) 以及解的质量评价指标，以便为编码和后文的遗传操作提供依据。 2 1 r m s s 问题的模型 通常将计算机网络描述为一个有向连通图g = ( k d ，其中矿= v o ，v l ， m 1 ) 代表网络中的结点集( 包括主机和路由器) ，e = e o ，e 1 ，e m 1 ) 为任意两 相邻结点间的通信链路集合，e k = ( v 。，功e e ，v ，和1 1 ，代表链路e 的始点和终 硕士学位论文 m a s t e r st h e s i s 点。考虑一个拥有h 个服务器s = s o ，s 卜，品一l 和m 个客户端c = c o ，c i ， 一l 的组播服务，s cnc cv o 客户端对服务器的分配对应函数妒：c s 。 用q ：= 刊妒( 0 ) = 毋) 表示分配给服务器s i 的客户端集。以s i 为根，建立组播 树乃=( e ) ( k v ，e e ，0 i n - 1 ) ，满足s ，且 ( v c j ) ( e ( c j ) = j ，一c ，k ) ，共有n 棵组播树。乃；( 曝奶) ( 喝k ，必e i ，妒( c ，) = s ，0 j m 一1 ) 代表在组播树正中从岛到c j 的 路径，p 巧为该路径上的结点集，e 弓为该路径上的边集。p ，= 厅1 0 e q f 代表 研到所分配客户端的路径集合 。 若 p ju p k = ( q ，码) u ( 睨，必) = ( 哆u 噬，留u 必) ，则up j = z 。定义 n e 另 组播子组s u b g i ； ，q 。乃，只) ( o 三isn 一1 ) ，该子组以s ，为服务器，o ，为客 户端，服务数据沿组播树正传递，毋到q ，中结点的路径构成_ 尸，。以上描述说 明了分组和子组组播树应满足的条件。 分组和子组组播树的建立完成之后，每个子组可按一定的速率进行组播 服务。若j i 的发送速率为马，0 的接收速率为0 ，则( v c ) ( 妒( c ，) = 斗0 = 墨) ， 即每个组播子组内各客户端的接收速率都相等，且等于相应服务器的发送速 率，因此届也称为组播子组s u b g 。的服务速率。服务速率越大越好，但它必 须受到链路带宽的限制。用矿表示正实数集合，延迟函数d e l a y ：e f 定义 了e 中每条边所代表的链路延迟：带宽函数b a n d w i d t h ：点i 矿定义了每条边 相应的链路带宽。n u m ( e j ) = ( f | 唧正 代表8 f 所在组播树的编号集。r m s s 需 要确定的每个组播子组的服务速率r ，满足以下限制条件： 对v e e ，艺r b a n d w i d t h ( e s ) ( 2 1 ) i e n u m ( e i ) 衡量一个服务器选择结果的优劣通常从两方面考虑：一、是否有利于网 络运营商，最大化收益：二、是否有利于用户，在尽量提高服务质量的同时 为每个的用户公平地服务。这两方面的考虑对应于r m s s 的两个优化目标： 组播客户端的平均接收速率和公平性。 8 平均接收速翠性能只定义为 e 2 去：o ( 2 2 ) p ，也可表示为 p 2 ；1 n , - ri f 2 。i ， ( 2 3 ) 其中q i 为选择服务器s 。的客户端数目。p ，越大，平均接收速率性能越高， 网络的整体利用率越大。若网络运营商采用按流量计费的原则，它的收益也 将最大。 若i 表示在没有其它用户时，o 的最大接收速率，也即q 的理想速率， 则公平性性能毋定义为 弓= 三m ： ( 2 4 ) j 一j 2 0 r 、 7 反映了。的接收速率接近理想速率的程度，丢越大，o 的接收速率越接近 00 它的理想速率。竹越大，客户端平均越接近各自的理想速率，分组方案越公 平。这种公平性被称为i n t e r - f a i r n e s s 3 4 1 。 求解平均接收速率或公平性最优的r m s s 问题已被证明是n p 问题。如 何为客户端合理分组、为各子组建立组播树( 即服务器到客户端的路径) 以 及确定各子组的服务速率，使平均接收速率和公平性达到最优，是r m s s 的 关键问题。本文试图采用遗传算法来实现上述优化目标。 图2 1 给出了一个网络拓扑结构图，给定问题的规模和数据，我们将以 此为例来讨论和实现g a r m s s 算法。图中包含2 个服务器，分别是s o ( v o ) 和s 1 ( v 1 ) ；7 个客户端，分别是c 0 c 6 ( v 8 y 1 4 ) 。为了方便起见，图中的一条边 代表了它两端结点间的两条方向相反的有向边，边上标注的二元组代表带宽 和时延，相应两条有向边的带宽和时延均相等。需要说明的是本文中的算法 并无对称网络的要求，所有的算法都是针对一般的有向图。 9 阻2 1 一个网络拓扑结构图 2 2g a - r m s s 的编码方法 g a r m s s 首先需要解决的问题是染色体编码。编码把一个p m i s s 问题 解空间映射到遗传算法解空间，每一条编码的染色体都代表一个合法的服务 器选择结果。编码的原则就是能够生成合法、多样的染色体，每一个可能的 染色体都有均等的生成机会，在这些有差异的染色体中搜索、进化，达到寻 优目的。有效的编码是利用遗传算法求解最关键的一步，编码方法也同时决 定了交叉和变异操作的方式和效率。 p d v s s 的一个解既要说明客户端的分组方式，也要说明服务器到客户端 的具体路由。在以往的算法中这两部分的求解同时进行，即一旦客户端选定 了服务器，服务器到客户端的路由也确定。例如最短路径法算法 7 】是为每个 客户端选择最近的服务器，选择同一服务器的客户端属于同一子组。当某个 服务器被选定，从该服务器到客户端的最短路径就是数据传送的路径。这种 分组和路由存在明显弊端：一个服务器分配方式只对应唯一的路由方案。然 而由于网络中间结点复杂的互连，即使是同样的服务器分配结果，也应存在 多种不同的路径到达客户端。未加比较地选择一条固定路径，很可能并不是 最优的一种方案，难以保证解的质量，缺乏灵活性。本文将服务器选择的两 个方面分开考虑：首先决定服务器的分配方式，再建立子组组播树、确定服 1 0 务器到客户端的路径。对应于这两个步骤，本文提出7 - - 级染色体编码方案。 第一级编码表示服务器的分配，它指出了客户端分组方式；第二级编码表示 各子组的组播树，它指出了服务器到达客户端的路由。这两级编码合在一起 构成一条完整的染色体，我们将依次讨论这两级编码的生成。 2 3 服务器分配( 第一级编码) 服务器的分配决定每个服务器组播的对象。一个服务器可以对应多个客 户端，一个客户端只能选择唯一的服务器，每个服务器要尽可能“公平”地 被选择。这里的公平不是指平均，不同的服务器可以拥有数目不同的客户端， 但每个服务器被选中的机会应当均等。不应存在对某个服务器格外“偏爱”， 使它拥有的客户端太多；也不应对某个服务器格外“抵触”，少选甚至不选。 我们从客户端的角度出发，由每个用户自由挑选服务器。 我们用一维定长数组表示服务器分配结果，数组的长度等于客户端的总 数目，数组下标对应客户端结点的编号1 ，数组中每一个元素的值表示该客户 端选择的服务器编号。初始化时，客户端选择的服务器编号在 o ，1 ，n 1 ) 中随机生成。图2 1 包含两个服务器s o 和s l ，选择的编号就是0 或1 。图2 2 给出了一个随机产生的分配结果。c o 、c 2 、c 3 和c 6 被分配给s o ，c l 、“和c 5 被分配给s 】，即q o 亍= c o ，q ，c 3 ，c 6 ，q l = c l ，臼，c 5 ) 。这种编码方式满足了分 配的要求：每个客户端都选择唯一的服务器，不会生成非法的分配结果。均 匀分布的随机选择使每个服务器被选中的机率相等。第一级编码的服务器分 配方式在满足了合法性的同时，也保证了个体的多样性。 从分配表可知，在九个服务器的情况下，每个客户端存在n 种可能的选 择，m 个客户端一共存在m ”个分配可能。在服务器数目增大时，搜索空间指 数级的增长使传统算法几乎不可能得到最优解，这是r m s s 的一大困难。第 一级编码能够生成每一个可能的分配结果，但遗传算法不会在所有的解空间 中搜索，它只是在足够多的解上施加自适应的搜索过程达到寻优目的，因此 本文中数组和矩阵的下标均从0 开始。 它是解决这类问题的有效方法。 对应客户靖编号： 服务器分配表： 互【! i j j 二【丑至 图2 2 一个服务器分配表 第一级编码表示简单直观，直接可以得到每个客户端对应的服务器，选 择同一服务器的客户端属于同一子组，解码方便。一个服务器分配表所需存 储空间也很小，若一个整数使用4 b ( 3 2 b i t ) 表示，第一级编码仅需4 r o b 存 储空间。在客户端数目一定的情况下，增加或减少服务器数目，第一级编码 的长度都保持不变，具有良好的可扩展性。在3 2 2 和3 2 3 节的讨论中可以 看到它也能方便地实现交叉和变异操作。 2 4 子组组播树的建立( 第二级编码) 第一级编码解决了服务器的分配，只完成了部分染色体，没有说明每个 子组的组播树如何建立，这部分工作将由第二级编码完成。在相同服务器分 配下，因中间路由结点的互连，可能存在多种组播树的建立方式，不同的组 播树会带来不同的服务性能，这进一步增长了搜索空间，是r m s s 的又一大 困难。 树的编码在遗传算法中是一个比较困难的问题 3 5 】，有效的编码必须具有 以下两个特点：第一、编码方案应能表示所有可能的树：第二、每编码只 应该表示一棵树。 树具备两条根本性质：连通性：树中的每一个结点都只有唯一的父 结点。第条性质也说明树中不包含回路。若一种编码方法产生的编码除树 以外，还有包含其它的非法解，那么它必须经过检验或修复才能保证合法性， 这给树的编码生成增加了难度。 我们认为合理、有效的编码应充分注意上述问题。 1 2 硕士学位论文 m a s t e r st h e s i s 已存在多种组播树的编码技术 2 3 3 2 1 ，其中代表性方案有以下三种。 文献 2 3 2 4 1 采用了n n ( 为网络结点数) 的一维二进制数组的编码机 制。对数组的每个元素随机取0 或1 ，当第i n + ，个元素为l 时，结点f 和结点，之间的边被选中。这种编码方式极有可能产生非连通图或者回路， 必须修复非法解使之合法，随后的交叉、变异操作的实现也因之更复杂，效 率较低。 文献【2 5 】首先计算出图中任意两个结点间的所有可能路径：再随机选择源 端到每个目的端的路径，并将这些路径叠加的结果做为组播树。这种编码只 保证了连通性，没有考虑回路。实际上，有时路径叠加的结果并不能称为“树”， 文中对这种非法解不做特殊处理，只依靠进化淘汰，不利于产生优秀解。另 外，该算法需要得到任意两个结点间的所有路径，时间复杂度为o ( ) ，对 于较大规模网络比较耗时，可扩展性较差。 文献 2 6 2 8 的组播树编码直接采用树型结构，省略了解码操作。组播树 的生成采用随机深度优先搜索算法。从源结点开始，随机地选择一个与之相 邻的结点，将两点相连；然后从该结点继续随机选择与其相邻的下一个结点， 在连接时要判断是否有回路，如有回路则重新选择结点，重复这个过程直至 搜索到所有的目的结点结束。这种随机的搜索没有指导原则，它可能因产生 回路需要回溯，而花费较长时间才能够找到一棵覆盖所有目的结点的树。 g a r m s s 染色体的第二级编码采用树型结构，直接表示出各子组的组播 树。我们提出了第二级编码的生成算法一一组播树生成算法d r m t ( d i j k s _ 讧a b a s e dr a n d o mm u l t i c a s tt r e e ) ，该算法可随机生成一棵组播树，不 会产生非法解，无需合法性检查，大大加快了组播树的生成速度。在讨论 d r m t 算法之前我们首先讨论图的化简问题，它可以减小求解组播树的问题 规模。在介绍完d r m t 算法之后我们还将提供一种多棵组播树存储方案 路由矩阵。 2 4 1 图的化简 每一个子组的组播树都应以该组的服务器为根，以该组的客户端为叶子 结点，并且它不应包含其它的叶子结点。因此我们在为每个子组求解组播树 1 3 硕士学位论文 m a s t e r st h e s i s 之前，首先对网络图进行预处理，删除在组播树中不应出现的结点，得到简 化后的图。对图的简化可以减小问题的规模，提高组播树的生成效率。 首先给出有关图的一些定义，其中某些定义在后文其它章节也将用到。 定义2 1 设g 2 ( k 毋是一个简单有向图，它有个结点y = 。o ”1 一，1 ， 则阶方阵州硼为9 的邻接矩阵，其中呀= 器裁? 籍接船， 邻接矩阵反映了图的连通信息，例如图2 。1 的邻接矩砗为 定义2 2 设g 2 ( k 司是一个简单有向图，它有个结点矿= v o ，v l ，v 1 ， 则n 阶方阵d = ( 嘞称为g 的延迟矩阵，其中 略= f 宇劬 为 延迟矩阵包含了图中每条边对应的链路延迟信息，例如图2 1 的延迟矩阵 d = 00u，0000000000u o000000，oo00000o000000loo00000 oooo00100000000 000000looonoooooooooloooooooooooou1000000000uo00100100000110000010011000 000u，1010u，0000u001101101000000 011010110000001 loollo000000000oou，loooooooooou00一，oooooooo000u j j 或接 接邻邻不 0 j 、 b _ 若若 8曲96埒田 87 8，6m69 3558m 657486