基于混合聚类的覆盖网络组播服务节点选择模型.pdf

第3 6 卷第6 期 2 0 0 7 年1 1 月 中国矿业大学学报 J o u r n a lo fC h i n aU n i v e r s i t yo fM i n i n g T e c h n o l o g y V o I f3 6N o ．6 N O V ．2 0 0 7 文章编号1 0 0 0 1 9 6 4 2 0 0 7 0 6 0 8 2 6 0 7 基于混合聚类的覆盖网络组播服务节点选择模型 程德强，钱建生，赵亮 中国矿业大学信息与电气工程学院．江苏徐州2 2 1 1 1 6 摘要通过分析当前覆盖网络特点，以分层覆盖网络为基础构建特定源组播树，实现对组播服务 节点M s N s 的管理，并提出一种基于K M e d o i d s 和遗传算法的模型，用于网络中M S N s 的选择． 结果表明，该模型有效克服了待统K M e d o i d s 算法模型对初始中。选值敏感的问题和早熟收敛 现象使其针对覆盖网络组播服务节点的选择性能明显优于K M e d o i d s 选择模型，平均收敛速 度也提高近3 0 ％． 关键词K M e d o i d s ；遗传算法；覆盖网络；混舍聚类 中国分类号T N9 1 9 ．8文献标示码A AS e l e c t i o nM o d e lf o rM u l t i c a s tS e r v i c eN o d e sB a s e d o nH y b r i dC l u s t e r i n g C H E N GD e q i a n g ，Q I A NJ i a n s h e n g ，Z H A OL i a n g S c h o o lo fI n f o r m a t i o na n dE l e c t r i c a lE n g i n e e r i n g ，C h i n aU n i v e r s i t yo fM i m n g ＆T e c h n o l o g y X u z h o u ，J i a n g s u2 2 1 1 1 6 C h i n a A b s t r a c t O nt h eb a s i so fa n a l y s i n go v e r l a yn e t w o r k ，as o u r c e - s p e c i f i e dm u l t i c a s tt r e ew i t hh i e r a r e h ys t r u c t u r eW f l Sc o n s t r u c t e dt om a n a g et h em u l t i e a s ts e r v i c en o d e sb a s e do nN I C En e t w o r k ．B a s e do nt h ea l g o r i t h m so fK M e d o i d sa n dg e n e t i c s ，ah y b r i dK M e d o i d sg e n e t i cm o d e l H K G M w a sp r o p o s e dt oc h o o s em u l t i c a s ts e r v i c en o d e s M S N s f r o mn e t w o r kn o d e s ．T h e r e s u l t ss h o wt h a tH K G Mn o to n l ya v o i d sc o n v e r g i n gt ol o c a lm i n i m u mv a l u e ，b u ta l s oi sr o b u s t t Oi n i t i a l i z a t i o n ．T h ep e r f o r m a n c e so fs e l e c t i n gM S N s ，H K G Mi ss u p e r i o rt OK M e d o i d s ．a n d t h ea v e r a g ec o n v e r g e n ta p e e di n c r e a s e sa b o u t3 0 ％． K e yw o r d s K M e d o i d s ；g e n e t i ca l g o r i t h m ；o v e r l a yn e t w o r k ；h y b r i dc l u s t e r i n g 对于实时流媒体的传输，覆盖组播网络[ ” o v e r l a ym u l t i c a s tn e t w o r k ，0 M N 在现有“单播路 由转发和尽力传输”的网络架构基础上，利用网络 中的计算机资源，构建有终端计算机 终端节点 构 成的虚拟网络结构 应用层网络 ，屏蔽了物理网络 的拓扑细节，克服了I P 层组播需要阿络中的路由 器的支持、可扩展性、网络管理等屏障o ] ．当前， O M N 主要有基于对等主机和基于代理服务器2 种．基于对等主机的O M N 每个组成员节点都是平 等的，本身即作为接收者，又同时发送数据，自组织 成控制网络和数据转发树．基于代理服务器的 O M N 通过在网络的某些位置部署应用层代理节 点 p r o x yh o s t ，P H 或专用服务器 d e d i c a t e d s e r v e r ，D S 来实现数据的转发组播，是一种基于 固定节点配置的覆盖式组播技术，与对等型方案相 比，具有更高的稳定性口“] ． 与Y O I D [ 4 ] ，H M T P [ 5 3 等覆盖网络协议相比， N I C E [ 3 3 采用特定源树 s o u r c } s p e c i f i e dt r e e 的方 收稿日期2 0 0 7 0 1 1 7 基金项目国隶自然科学基金项目 7 0 5 3 3 0 5 0 作者简介程德强 1 9 7 9 一 ，男- 河南省洛阳市 ．博士研究生，从事覆盖网络、视频可靠传辅控制方面的研究 E ．口日u 1d 哪a n g c h “g 1 6 9 ．e o m n l ；0 5 1 6 8 3 5 9 9 8 2 5 万方数据 第6 期程德强等基于混台聚类的覆盖网络组播服务节点选择模型 8 2 7 式管理网络组播节点，进行大容量数据转发时，其 链路压力最均衡”] ．而大容量的实时视频流媒体的 传输，对组播通道的稳定性要求非常高，并且要求 网络负载均衡，基于此种考虑．本文利用N I C E 结 构进行网络节点的管理，构建基于固定节点配置的 分层 h i e r a r c h ys t r u c t u r e 特定源组播树，如图1 所示．所有网络节点属于最底层L o ，节点根据相互 之间的相似度形成多个簇，并在簇中选取中心节点 簇头 ，簇头形成层L 。，然后根据L 。各节点的相似 性形成多个簇，相应的簇头构成工z ，重复以上步 骤，最终形成由全部节点组成的分层的组播基础结 构 a p p l i c a t i o nl e v e lm u l t i c a s ti n f r a s t r u c t u r e ，A L - M I ，如图2 所示．各个簇头担负主干数据流的转 发，构成了基于特定源分发组播树．簇头代表的各 个簇把网络节点划分为各个组播岛“3 M u l t i c a s t I s l a n d ，M I ，组播岛的中心即是各个簇头，称之为 组播服务节点 M u h i c a a tS e r v i c eN o d e s ，M S N s ． 覆盖网络中，组播转发树的建立要尽可能的减少网 络延时，同时保证网络负载的均衡，其中M S N s 的 选取非常重要．因此，本文主要解决的问题，就是结 合视频图像传输的特点构建选择模型，进行M S N s 的全局摄优选取．对于实时的流媒体视频数据，其 最后一跳 叶节点与L o 层M S N s 的连接 对视频 的接收质量影响很大，为简化起见，本文只考虑L 0 层M S N s 的选取问题． 么 芏乡b 龃播服务节点M S N s 一单插通道 - 网络节点 0 蛆播岛M I 图1 分层覆盖网络节点组织关系 F i g ．1 R e l a t i o n 曲i po fn o d e si nh i e r a r c h yO M N 图2 覆盖网络分层组播树 F i g ．2L a y e r e dm u h i e a s tt r e ei nO M N l 相关的研究 对于组播服务节点的选择，可以归结K 中心 节点选择问题，国际上对于网络中心节点的选择可 以归纳为2 个方面的研究1 在中心节点已知的 情况下，新加人节点对中心节点的选择问题C 79 ] ； 2 在中心节点未知的情况下，根据服务特点。进行 节点相似度的定义，进行中心节点的识别与选择． C A M E R O N o ”利用高速矢量量子化理论在C D N 网络中进行转发服务器的选取和放置． C H A D H A 口“研究了通过网络节点相互间的知识 学习和推理完成在M A N E T s 网络中服务节点的 放置问题．V L E E S C H A U W E R c ”1 采用线性规划， 研究了网络游戏中的服务器放置和优化问题． Q I N ””在覆盖网络中，利用D i j k s t r a 算法生成组 播树，并通过G A 算法进行优化，从而实现组播树 转发中心节点的选择． 在N I C E 覆盖网络结构中，B A N E R J E E [ 3 ] 建 议用聚类的思路进行覆盖网络组播岛转发节点的 选择，但在文中未对聚类的方法进一步阐述．以此 为基础，本文依据K M e d o i d s 算法对孤立点具有 很好的健壮性的特点o “，结合遗传算法的高效率 全局优化能力，设计基于K M e d o i d s 和遗传算法 的模型 h y b r i d K M e d o i d s g e n e t i cm o d e l ， H K G M ，进行组播服务节点M S N s 的选取和组播 岛划分，达到构建基于固定节点配置的分层组播覆 盖网络的目的．并且，针对视频传输对延时和节点 的处理能力要求高的特点，模型的设计以M S N s 的度 d e g r e e 和物理链路延时R T T 为节点特征属 性，进行M S N s 的选取，使分层覆盖网络进行实时 视频流转发时，网络负载均衡，并且视频传输的网 络延时最小．国际上利用K - M e d o i d s 和遗传算法 实现混合聚类应用于覆盖网络组播岛划M S N s 选 取非常少见，但在其他领域已有应用．S H E N G 口” 采用混和聚类算法H K A 完成了基因数据识别和 划分．在国内，厍向阳“”完成了基于障碍物约束的 空问数据聚类和划分．叶苗群口”通过对网络中 W e b 日志的识别完成W e b 用户行为的分析． 2M S N s 选择模型设计 21 问题的描述 组播覆盖网络中组播岛的划分和M S N s 的选 取采用聚类分析来实现，其目的是根据节点的度和 传输延时，将网络划分为若干组播岛，并选择出簇 头 M S N s ，使在一个组播岛中的对象距离对应 M S N s 最近，而不同M S N s 间的距离最远“”． 设覆盖网络中有n 个网络节点组成样本集，每 个样本节点有m 个属性，若令z ，为网络节点的m 维特征向量，则V , 1 7 dc R 棚使z ， z 1 ，，z 卸，⋯， 蚕 万方数据 中国矿业大学学报 第3 6 卷 z ， ’，因此网络节点特征属性矩阵可表示为 X ⋯ Z l ” ⋯Z 2 “ ● ⋯Z 瑚 一{ z i 耐。， 1 式中z d 为样本j 的第i 个特征属性值，i ∈{ l ，2 ， ⋯，m ，J ∈{ 1 。2 ，⋯，”} ．由于各特征属性值存在量 纲和数量级的差异，为了消除相互影响，利用极差 正规化方法对其进行归一化处理，则网络节点特征 属性均匀映射到空间R ⋯ E o ，1 ] ⋯上，其映射 关系如下 z “～“一美，㈣ 式中z ～为特征属性矩阵第i 个特征属性的最大 值，z 一。为第i 个特征属性的最小值；由式 2 的映 射关系可得到特征属性矩阵x 的归一化矩阵 S 一 1 1 卸2 S 2 1 S Z Z ● ● S m l 5 m 2 知为z 。归一化处理过样本属性值，即网络节 点j 的第i 个特征属性归一化值，z 。∈[ o ，1 ] ，且 i ∈{ 1 ，2 ，⋯，m } ，j ∈{ 1 ，2 ，⋯，月 ． 在覆盖组播网络中，根据各节点对接收的视频 图像实时性要求和节点对视频信号处理能力的不 同。节点属性权向量为 w 一 w l ，m ，⋯，∞。 c j P ，∑W 。一1 ． 4 i l 22 K - M e s 选择模型 该模型将m 维网络节点特征向量x ，划分为c 个组 组播岛 ，使得组播岛内网络节点的相似度 最高，即各节点到对应M S N s 的距离 目标函数 达到最小．考虑到节点矢量中各属性值对划分结果 的影响不同，节点样本j 与组播岛 的中心特征矢 量 M S N s 的相似度采用广义欧式权距离的平方 表示，即 d Ⅲ 0 w 。 封一仉 02 一∑[ ∞， 略一口 ] 2 ． 5 i 1 样本≈一 5 l j ．％，⋯，s 忡 ’，』∈ 1 ，2 ，⋯，n ， h 一 s 。 ，s 。，⋯，s _ 7 ，h ∈{ 1 ，2 ．．，c 为组播岛h 的M S N s 中心矢量．同时为了反映了网络节点样 本s ，与第 个M S N s 中心n 的差异程度，根据} 近邻法则，引入网络节点的隶属度矩阵u ，即 f 1 巩，一r a i n { d H ， ““2 、o d * ≠m i n { d “ ， 1 ≤ ≤f ，1 ≤J ≤n ，≈≠j ． 6 由于一个网络节点只能属于一个M S N s ，则 “i ∈M 。 网络节点划分空间 M h 一{ “∈F “1V h ，V j ，“_ ∈{ 0 ，1 ； fⅣ V J ，∑U h ／一1 ；V ，0 ∑“Ⅳ n } ． 7 1，一1 因此，由式 5 和式 6 ，目标函数可定义为 f月 J u 一∑∑0 ”； s j h | | 2 一 1 ，一1 fm ∑∑“～∑[ ”。 如一。m r ， 8 式中t 饥是组播岛中M S N s 的矢量，即对应组播岛 中所有矢量的均值 n 2 j H ≈s I “ O h 一2 } ，1 ≤ ≤c ． 9 二“H J 2 I K M e a n s 模型选择M S N s 流程如下 1 从所有样本节点中，随机选择女个节点，对 M S N s 进行初始化，并确定阈值和最大迭代次数． 2 根据式 6 和最近邻法则确定隶属度矩阵 U ． ．3 根据式 8 计算目标函数，如果其值小于阈 值，或达到最大迭代次数，停止运行并输出结果．否 则，继续． 4 根据式 9 修正聚类M S N s 位置，转向第2 步． K M e a n s 选择模型具有算法简单且收敛速度 快的特点““，但采用节点均值 质心 作为聚类中 心 M S N s ，是一个抽象点，不是具体的节点；除此 之外，K M e a n s 算法对孤立点非常敏感m ] ．而K M e d o i d s 选择模型采用实际节点作为聚类中心，可 有效地解决以上问题．K - M e d o i d s 模型选择M S N s 流程如下 1 从所有样本节点中，随机选择 个节点，对 M S N s 进行初始化，并确定阈值和最大迭代次数． 2 根据式 6 和最近邻法则确定隶属度矩阵 U ． 3 根据式 8 计算目标函数，如果其值小于阈 值，或达到最大迭代次数，停止运行并输出结果．否 则，继续． 4 随机在组播岛内选择非M S N s 节点代替 M S N s ，转向第2 步． 但是，K M e d o i d s 选择模型和K M e a n s 选择 模型都采用基于目标函数的算法，通常采用梯度法 札‰；‰ 万方数据 第6 期程德强等；基于混合聚类的覆盖网络组播服务节点选择模型 求解极值，其搜索方向沿着能量减小的方向进行， 使得算法很容易陷入局部极值，并且算法也存在对 初始中心选择敏感的问题C 1 4 , t 8 ] ． 2 ．3 H K G M 选择模型 遗传算法通过模拟自然进化过程搜索最优解， 其显著特点是隐含并行性和对全局信息的搜索能 力，是一种高效率的随机全局优化搜索算法．本文 利用遗传算法的全局高效搜索能力解决K M e d o i d s 选择模型对初始中心敏感问题，同时，针对标 准遗传算法的早熟收敛现象““2 1 ] ，根据覆盖网络 M S N s 的特点，引入基因差异控制和变异精英控制 策略，对遗传算法中的交叉和变异算子进行修正， 限制适应度差的个体生成，在缩小搜索空间、加快 收敛速度的同时，提高算法的全局寻优能力． 2 ．3 ．1 编码 编码的对象是组播岛中心M S N s ．若需对Ⅳ 个样本节点划分到c 个组播岛中，则在样本中随机 选择”组对象，每组c 个点，代裘c 个组播岛中心 M S N ，并进行实数编码。则第i 个个体可用y 。 讪1 ，让∥”，_ 。 ∈R 州‘表示，其中％∈{ 码l l ≤ ％≤N ，1 ≤i ≤n ，1 ≤j ≤c } 代表第i 个个体中 第J 个组播岛对应的M S N ，因此，构成了n f 维 的初始搜索空间．此种编码方法避免使用特殊的交 叉操作和变异操作，同时也克服了样本数目多时， 二进制编码时搜索空问巨大的缺点”⋯． 2 ．3 ．2 产生初始种群 在网络节点中，随机选择n 个个体组成初始种 群，每个个体代表一组聚类中心，即一组M S N s ．初 始种群中个体数目太小，易失去多样性；如果太大， 则达到最优时的时间消耗过大．经验表明D6 ] 种群 个体数目应大于3 0 ，不必高于7 5 ．记y 。 f 一 { _ ，- ￡ ，口口 f ，⋯，口。 f 表示第t 代进化群体中的 第i 个个体，则第t 代进化群体可表示为v ￡ 一 { V - f ，V z f ，⋯，V 。 f 7 ．随机产生F O ，N ] 区间 的整数逐个填充n 个个体的基因链，由于产生的随 机数服从均匀分布，因此，初始种群遍历整个解空 间，能充分反映优化问题解的性态口“． 2 ．3 ．3 适应度选择 组播岛中的对象偏离M S N s 的距离最小，根 据式 8 ，以类内平方误差和 W G S S 为聚类目标 函数，目标函数越小。则聚类质量越好，相应的个体 适应度越高．令J 表示第k 个个体的目标函数， 定义其适应度为 ， 女 一1 ／ 1 J ． 1 0 2 ．3 ．4 遗传操作 1 选择算子 选择算子采用赌轮法获取，即根据个体的适应 度在当前种群全部个体适应度之和中所占比例，进 行个体的选择，则第i 个个体的选择概率为 p V ， ， i ／≥， i 一1 ，2 ，⋯，月 ． 1 1 。k - - I 2 交叉算子 为了维护群体多样性，避免算法的过早收敛， 采用近邻配对原则对个体实现交叉，此种交叉方法 可避免较优模式过快的扩散，而且还符台基因算法 细粒度并行模型的要求，易于获得较大的并行 度”“．由于在覆盖网络中，对组播岛中心节点 M S N 采用实数编码时，每个基因代表一个M S N ， 基因长度有限，因此本文采用整体算术交叉o “相 互交换两个配对个体的基因． 若个体p V 。 P 。 m 为变异 概率 ，采用单点变异，即随机选择其某一位基因 进行非一致性突变，并把参与变异的分量作随机扰 动，这个扰动在进化初期变化范围较大，随着进化 代数的增加扰动变化范围逐渐减小，以此加强进化 后期的局部搜索能力，即 。 c h i l d i j p a r e n t i j 8 ， 1 4 式中8 一口* 。] ，口为 - - 6 ，6 区间的均匀分布随 机变量，A l ／t ，K 为正整数，t 为迭代次数，[ * ] 表示取整数． 4 基因差异控制 群体中每个个体代表一组组播岛中心，在交叉 和变异过程中，可能出现一个个体中同一基因重复 万方数据 中国矿业大学学报第3 6 卷 出现的现象．但是，在O M N 中，M S N s 是一组彼此 不同的网络节点，不可能出现含有相同基因的个 体，因此，采用基因差异控制，完成对交叉和变异过 程中，限制具有相同基因的不良个体的产生．个体 基因差异控制步骤如下a ．对于第t 代的第i 个个 体V ； ￡ { 口n f ，口；2 ￡ ，⋯，口。 ￡ ，若Vu 。， 。。 m ≠“ ，m n ，使。。一≈。，可判断个体中出现 重复基因；b ．随机产生[ 一1 0 ，1 0 3 区间随机整数d ， 利用。。一”。 d 修正个体重复基因，修正后的基 因％应满足2 个条件．a ．‰在实数编码的基因有 效取值范围内，即0 v 。 N ．b ．修正后的‰不 能和现有个体中的其他基因相同，若存在相同基 因，重新执行基因差异控制操作． 5 变异精英控制策略 H K G M 选择模型的遗传操作中，选择高交叉 概率对个体进行整体算术交叉，加快新个体产生的 速度，保证群体多样性．为了增强算法的局部搜索 能力，选择高变异率进行个体单点非一致性变异， 传统的全种群变异策略认为变异概率P 。不能太 大““”’2 “，否则高频度的变异将使遗传算法趋于 纯粹的随机搜索． 本研究在变异操作中，采用变异精英控制策 略，如果变异后的个体产生退化现象，即适应度减 少，则取消此次变异，保留父个体；否则，进行变异， 以此来实现对种群内不良个体的高概率变异，不会 破坏优良个体，因此，即使变异概率很大，也可以保 证解的收敛性．同时在变异中引入随机扰动，并使 扰动范围随进化代数减小，进一步提高进化后期的 局部搜索精度． 25 模型终止准则 当进化代数达到最大进化代数G 或者结果没 有明显改进时，即t G 或IJ ￡ 一J 卜一1 l e e 为小正整数 时，算法终止，其中J ￡ 如式 8 定 义． 3 仿真实验 取每组网络节点样本集包括1 5 0 个网络样本 节点，即n 一1 5 0 ．通过n 阶对称方阵A 一{ a d } 。 表示节点间的网络链路R T T 传输延迟，根据网络 节点的特点，则方阵元素哪满足一下特点 艇a l j 篇篙iC m j ， ，, 0 Ⅲ， 【蛳一％一 i j ， 式中d ，，表示i 节点到J 节点的R T T 延迟，反映当 前端到端网络传输质量，为不失一般性，各节点间 R T T 延迟随机生成，为服从[ 1 ，4 0 0 ] 的均匀分布的 自然数． d e g r e e 。为节点i 的度，表示i 节点的视频数据 处理能力，为服从[ 1 ，5 ] 的均匀分布的自然数．当 d e g r e e ，一1 时，表示i 节点处理能力最强；当 d e g r e e ．一5 时，表示i 节点处理能力最弱．根据式 2 分别对节点问的延迟和节点的度进行归一化 处理，消除不同量纲对聚类划分的影响．令毗和 ”z 分别为网络链路延迟和节点的视频数据处理能 力权值，则根据式 5 节点J 与节点h 的距离可定 义为 d s ，，％ 一““[ w } Ⅱ W ；d e g r e e ] ， 式中‰满足式 6 约束． 随机生成1 0 组网络节点样本集，每组1 5 0 个 节点．对于每组样本集，随机生成初始种群，其种群 个体数目为3 0 ，每个个体中有5 个基因，即5 个组 播服务节点．利用V C 6 ．0 实现仿真算法，并编 译计算得到实验结果。算法运行硬件平台为I B M T h i n k P a dR 6 0 ，1 ．8 G H z 主频，5 1 2 M 内存．通过第 1 次实验，利用H K G M 选择模型和K M e d o i d s 选 择模型进行组播服务节点M S N s 的选取，并根据 式 8 ，以W G S S 为聚类目标函数，达到稳定最优 解时，目标函数越小，则M S N s 选择性能越好，即 聚类质量越高．2 种选择模型针对1 0 组网络节点 样本集，选择出最优解时的最小目标函数如图3 所 示，其中J ⋯表示最优解对应的目标函数，S 为网 络节点样本集．图4 为收敛速度比较，其中，为收敛 到最优解时的迭代次数． S 图3H K G M 和KM e d o i d s 模型对M S N s 选择性能比较 F i g ．3 P e r f o r m a n c ec o m p a r i s o no fs e l e c t i n gM S N s b e t w e e n H K G Ma n dK M e d o i d sf o rd a t aS e t s 8 0 7 0 6 0 、5 0 4 0 3 0 2 0 S 图4H K G M 和K M e d o i d s 选择模型收敛速度比较 F i g ．4R e l a t i o n s h i po ft h ec o n v e r g e n ts p e e d sb e t w e e n H K G Ma n dK M e d o i d s 万方数据 第6 期程德强等；基于混合聚类的覆盖网络组播服务节点选择模型 由图3 可知，对于不同的数据集，H K G M 选择 模型对最优M S N s 的选择能力明显强于K - M e d o i d s 选择模型，并且由图4 可看出H K G M 选择 模型收敛到最优M S N s 的速度快于K M e d o i d s 选 择模型． 第2 次实验中，对于同一组样本集，分别利用 H K G M 选择模型和K M e d o i d s 选择模型进行1 0 次实验，进行最优M S N s 选择．保证每次H K G M 选择模型的初始种群不同，并且保证每次K M e d o i d s 选择模型的初始中心节点不同，每次实验进 行1 0 0 次迭代，得到最优M S N s ，其对应目标函数 如图5 所示，其中J 。。表示最优解对应的目标函 数，n 为实验次数． 1 4 1 2 I O { 8 6 4 2 O2 4 6 81 0 图5 对于同一数据集H K G M 和K M e d o i d s 选择模型性能比较 F i g ．5 P e r f o r m a n c ec o m p a r i s o no fs e l e c t i n gM S N s b e t w e e n H K G Ma n dK M e d o i d sf o rad a t as e t 通过图5 的比较发现，在初始种群改变的情况 下，H K G M 选择模型通过M S N s 的选择，都能收 敛到一个相对稳定的全局最优值．而K M e d o i d s 选择模型，选择不同的初始中心，达到最大迭代次 数时，其最优目标函数起伏很大，这主要是因为， K M e d o i d s 选择模型存在对初始中心敏感的问题， 并且容易陷入局部极值，这与理论分析也一致． 4结论 1 H K G M 选择模型，克服了传统K M e d o i d s 选择模型对初始中心的敏感问题． 2 在个体进化过程中，引入基因差异控制和 变异精英控制策略，对基本遗传算法改进，加强了 H K G M 选择模型对样本空间局部搜索能力．并避 免了早熟收敛． 3 与K M e d o i d s 相比较，其平均收敛速度提 高近3 0 ％． 致谢t 本文得到中国矿业大学青年科研基金项目 F 2 0 0 4 2 3 资助。特此致谢 参考文献 [ 1 ] Y E O C K ，L E E BS ．E R MH ．As u r v e yo fa p p l i e a t i o nl e v e lm u h i c a s tt e c h n i q u e s [ J ] ．C o m p u t e rC o m m u n i c a t i o n s ，2 0 0 4 ，2 7 1 5 1 5 4 7 1 5 6 8 ． [ 2 ] D I O TC ，L E V I N EB ，L Y I ，E SJ ，e ta 1 ．D e p l o y m e n t i s s u e sf o rt h eI Pm u l t i c a s ts e r v i c ea n da r c h i t e c t u r e [ 刀．I E E EN e t w o r k 。2 0 0 0 ．1 4 1 7 8 8 8 ． [ 3 ]B A N E R J E Es ，B H A T T A C H A R J E EB ，K O M M A R E D D YC ．S e a l a b l ea p p l i c a t i o nl a y e rm u l t i c a s t [ c ] ／／A C MS I G C O M M ．P i t t s b u r g h A C MP r e s s ， 2 0 0 2 2 0 5 2 1 7 ． [ 4 ] F R A N C I SP ．Y o i d e x t e n d i n gt h er n u l t i c a s ti n t e r n e t a r c h i t e c t u r e [ E B ／O L ] ． 2 0 0 0 0 9 2 3 ．h t t p ／／w w w ． a c i r i ．o r g ． [ 5 ]Z H A N GB e i - c h u a n ，J A M I NS ，Z H A N GL i - x i a ． H o s tm u l t i c a s t af r a m e w o r kf o rd e l i v e r i n gm u l t i c a s t t oe n du s e r s [ c ] ／／I E E EI N F O C O M2 0 0 2 ．N e w Y o r k I E E EP r e s s ，2 0 0 2 1 3 6 6 一1 3 7 5 ， [ 6 ] 沈波，张宏科．刘云．覆盖网络组措压力与深长 度的性能评价模型口] ．系统仿真学报。2 0 0 5 ，1 7 f5 1 1 0 7 一1 1 1 0 ． S H E NB o ，Z H A N GH o n g - k e ，L I UY u n ．P e r f o r m a n c ee v a l u a t i o nm o d e l sf o rs t r e s sa n ds t r e t c ho fo v e r l a yn e t w o r km u l t i c a s t [ J ] ．C h i n e s eJ o u r n a lo fS y s t e m S i m u l a t i o n ，2 0 0 5 ，1 7 5 1 1 0 7 1 0 ． [ 7 ] A G R A W A LA ．C A S A N O V AH ．C l u s t e r i n gh o s t si n P 2 Pa n dg l o b a lc o m p u t i n gp l a t f o r m s [ c ] ／／P r o c e e d i n g so ft h e3 “I E E E ／A C MC C G r j d ．T o k y o I E E E C o m p u t e rS o c i e t y ，2 0 0 3 3 6 7 3 7 3 ． [ 8 ] B A K I R A SsA p p r o x i m a t es e r v e rs e l e c t i o na l g o r i t h m si nc o n t e n td i s t r i b u t i o nn e t w o r k s [ c ] ／／P r o c e e d i n g so f2 0 0 5I E E EI n t e r n a t i o n a lC o n f e r e n c eo n C o m m u n i c a t i o n s ．S e o u l I E E EP r e s s ，2 0 0 5 { 1 4 9 0 - 1 4 9 4 ． [ 9 ] P R A S A DV e n t a k e s h a ，S H A N K A RR ，J A M A D A G N IHN ，e ta 1 ．S e r v e ra l l o c a t i o na l g o r i t h m sf o rV 0 l P c o n f e r e n c i n g [ c ] ／／P r o c e e d i n g so ft h eF i r s tI n t e r n a t l o n a lC o n f e r e n c eO nD i s t r i b u t e dF r a m e w o r k sf o r M u l t i m e d i aA p p l i c a t i o n s ．B e s a n c o n ；I E E EC o m p u t e r S o c i e t y ，2 0 0 5 5 4 6 1 ． [ 1 0 ] C A M E R O NC ．L O WS H ，W E IDX ．As e r v e ra l l o c a t i o na n dp l a c e m e n ta l g o r i t h mf o rc o n t e n td i s t r i b u t i o n [ c ] ／／p r o c e e d i n g so ft h e2 0 0 2I n f o r m a t i o n T h e o r yW o r k s h o p ．B a n g a l o r e ；I E E EP r e s s ．2 0 0 2 2 6 2 8 ． [ 1 1 ] C H A D H AR ，P O Y L I