基于遗传模拟退火算法的多约束QOS组播路由优化算法

第24卷第12期 2007年12月 计算机应用与软件 ComputerApplic砒ionsandS0“ware V01．24No．12 Dec．2007 基于遗传模拟退火算法的多约束QOS组播路由优化算法 屈志毅文雪飞范志明 苏振明 (兰州大学信息科学与工程学院甘肃兰州7300∞) 摘要 组播路由问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 在计算机网络中是著名的Steiner树问题．是NP完全问题。通过考虑组播通信服务质量需求与网络资源 约束，研究了基于服务质量的组播路由选择算法问题，首次提出了一个基干遣传算法和模拟退火算法的多约柬组播路由优化算法， 该算法在满足带宽、延时、延时抖动及包丢失率约束条件下寻找代价最小的组播树。 关键词 QOs组播路由遗传算法模拟退火算法 AN0PTlMIZATIONALGORITHMFORMULTIPLECoNSTRAINED QOSMULTICASTROUTINGBASED0NGENETIC ANDSIMULATEDANNEAUNGALG0础THM QuzhiyiWenXuefeiFanzhimi“gSuzhenming (血n：抽uD眦哪蚵scb“0，l，扣m咖n＆曲n弹。树踟一椰一昭，k，曲帆刀0000，‰“，凸z加) Abstr丑ct1hemulticastmuti“gpmblemjncomputerne№rksisals0kno椰∞thef砌ousSteirlertre。PmbIemwhichh黯shnwnt0be HP·c饿nplek．cd晡d嘶ngQ晶地qui他Ⅱknls蚰dne咻0Tkre吼I咒ccon蛳nt鲁，aQos．b觞edm山ica暑tmningal窜诫吐蚰iBdeBi伊ed阻d洒甲le． mented，A“0pt；mizationa190d山mformuhiplecotl吕“ncdQ0smultica吼Tou廿ngb舳edonGeneticandsimulatedAnnealiIlgAlgorid衄i8pres。 蚰ted．whichc蛐constmctamultica针routingtreethatmeetstIleI瑚1q”iremenb．1hcalgodthmcan6ndthele粕t-∞虬multica虬i119treewi廿l thebandwidt}l，delayji廿erandpackedlo暑s-constrained． KeywordsQOsMullic聃t唧ni“gGeneticalgodthmsimulatedannealingalgodthm O引言 近年来，随着网络通信技术的发展及Intemet的普及，视频 点播、远程教育等多媒体应用越来越广泛，对刚络的服务质量提 出了许多新的要求，如何建立一种良好的数据转发机制或通信 策略就显得尤为重要。为了寻求数据的组播路径，简单地点对 点路由算法已经不能满足要求，需要针对组播的特点设计专门 的组播路由算法，找到满足业务的QOs要求的源节点到目的节 点的传输路径。目前，遗传算法在多约束Q0s纽播路由问题的 研究有一些成果”1．但是传统的遗传算法存在容易过早收敛以 及在进化后期搜索效率低两个严重的缺点。本文针对多约束 QOs组播路由的特点，提出了遗传模拟退火算法(以下简称GA- sA)，并和遗传算法进行性能比较。 1 多约束Qos组播路由的网络模型及数学描述 在实现组播树通信时，要给定一个信息和若干信息接收点， 如何确定从信息源到信息接收点的最好路径，即为组播树问题。 设Ⅳ(y，E) 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示网络，其中y为网络节点集，每个节点表示主机 或路由器；E为双向链路集，E中的边为连接网络节点的通信链 路。假设s为组播源节点，肘为组播目的节点集．则有，EP，肘 ‘{r一{51}。 · 定义1 V。ey，定义四个非负函数，分别为延时函数D。 (n)：y_+R+，延时抖动函数，．(n)：¨R+，费用函数c．(n)：y —墉+和包丢失率函数P(n)：P一尺+。网络结点特性由四元组 (D．，^，c．，P)描述。 V。e￡，定义四个非负函数．分别为延时函数巩(e)：E-， 尺+，延时抖动函数厶(e)：E叶R+，费用函数c2(e)：￡一÷尺+和带 宽函数日(e)：B—帽+。网络链路特性由四元组(见，^，c：．丑)描 述。 其中，R+表示正实数集。 定义2对于多约束Q0s组播路由问题，定义延时函数D (·)E冠+，延时抖动函数，(·)E矗．，包丢失率函数P(-)E 尺+，带宽函数曰(·)ER．和费用函数c(·)∈R+，寻找一棵由 5和_jI，组成的组播树r(s，肼)应满足以下关系： (1)延时约束： D(^(叫))=∑D．(n)+∑Dz(e)≤皿⋯n●，” ⋯n1．JJ (2)延时抖动约束： J(P，(5，t))=∑，。(n)+∑上(e)≤^⋯“’，” ⋯n’，” (3)包丢失率约束： 收稿日期：2005一IJ一27。屈志毅．教授，主研领域：模式识别．网络 安全。 万方数据 第12期 屈志毅等：基于遗传模拟退火算法的多约束Qos组播路由优化算法 183 P(Pr(叫))=1-兀．(1-P(n))≤凡 (4)带宽约束： 曰(一(5，f))=皿n(口(e)eE鼻(5．1)}≤成 (5)费用约束： 在所有满足(1)一(4)条件的组播树中，c(P，(1，t))最小。 其中，Pr(s，t)为r(s，_；If)上源点s到终点t的路由路径，＆ 是带宽约束，皿，^和A分别是组播终点l的延时、延时抖动和 包丢失率约束。 2基于遗传模拟退火多约束Q0s组播路由的 算法设计 GAsA的基本思想：将遗传算法与模拟退火算法相结合掏 成一种混合优化算法。遗传算法的局部搜索能力较差，但把握 搜索过程总体的能力较强；而横拟退火算法具有较强的局部搜 索能力，并能使搜索过程避免陷入局部最优解，但它却对整个搜 索空间的了解不多，不便于使搜索过程进人最有希望的搜索区 域，从而使得模拟退火算法的运算效率不高。本文将模拟退火 算法作为一种演化操作嵌入到遗传算法中，对遗传算于实施改 进，并根据算法的进化成熟度对个体进行模拟退火。改进的 GAsA工作流程如图l所示，如果连续Ⅳ代演化解没有改进，则 对最优个体实施模拟退火。以脱离可能陷人的局部最优解。 田l改进的cAsA的工作流程 2．1组播路由问题的编码和初始种群 编码是应用此算法时要解决的首要问题，在很大程度上决 定了遗传进化运算的效率。文献[3]采用了一维二进制编码机 制，这种编码模式使得算法编码、解码过程复杂、算法教率很低。 为克服编码操作带来的负面影响，所设计的算法．其染色体结构 就采用树型结构，每条染色体就代表一棵组播树，这样就可以用 树的任何一种数据结构来描述算法中染色体的结构．既减少了 编码空间，也省略了解码操作。设网络中有m个(m=lMI)节 点有组播要求，每个目的节m。点的路径集合设为f={一，砰， ⋯，只，⋯群l，其中只为目的节点m。的第J条路径，＆为组播源 节点，和组播目的节点m。之间的路径数，则从每个，j中选中 的路径组合可表示一棵组播树。遗传算法的染色体可由长度为 册的整数队列组成，染色体的基因是组播源节点s和组播目的 节点玑之问的路径数。采用此编码法随机产生初始种群。 2．2适应度函数 适应度函数是遗传算法用来判断个体好坏的衡量尺度。适 应度函数能反应被选个体的性能：性能好(满足延时约束且费 用较小)的个体适应度大，性能差(不满足延时约束或费用较 大)的个体适应度小。该算法中组播树代价和越小，其适应度 应越高，据此，适应度函数定义为： ^7’2——j：——iij；：而。{。ll矿‘。‘’’一日’+ 口H≯(J(·)一^)+7rI口(P(·)一P。)} 其中，廿(x)是惩罚函数，当个体满足延时约束时，即满足公式 (1)时，其值为1，否则值域属于(O，1)。其它情况同上。惩罚函 数值大小决定惩罚的程度，在实验中可选择其值为O．5；“是正 实系数．“，口，7分别为延时、延时抖动和包丢失率惩罚函数的正 加权系数。在计算代价和时，如果遇到经过相同的链路时，为避 免重复计算则淡链路代价只计算一次即可。 2．3交叉操作 交叉是把两个父个体的部分结构加以重组而生成新个体的 操作，使搜索能力得以提高，在本文交叉操作采用相同链路继承 的思想。随机抽取两个父代个体T，，疋，依照下述的交叉规则 以概率l交叉产生一新子女个体，该过程重复_】v一册次(其中， m为最佳个体数)。交叉规则：选择父母中相同链路，并将其直 接遗传到子女，形成零散子树。接下来就是连接零散子树彤成 组播树。如果中选的父母个体全不满足延时约束．用子树间的 “最短延时路径”连接；如果中选的父母个体至少有一个满足延 时约束，则用子树问的“最短费用路径”隹接。被连接完毕的两 子树作为一棵新子树继续参加后面的连接操作。重复该过程， 直到组成一棵组播树。显然，运用该连接策略组成的组播树不 会形成环路。 2．4变异操作 变异操作保证了遗传算法的有教性，使遗传算法具有随机 搜索能力．同时使得遗传算法保持种群的多样性，以防止出现非 成熟收敛。交叉完成后，新的子女个体以概率Pm进行变异．据 实验，变异概率pmE(0．咖，0．05)效果较好，算法能很快跳出 局部最优解并向全局最优解转化。变异规则：从新子女个体中， 随机选择一些中间结点(非组播源点和终点)，删除连接这些结 点的路径形成零散子树．然后依照交叉操作相类似的连接方法 连接各零散子树。 2．5个体模拟退火操作 经过交叉和变异运算后，由两个父代个体L和疋生成两 个子代c1和c2．对由父代个体和子代个体所组成的两个个体 组五和c．、疋和q，以概率户接受个体为下一群体中的个体， 以概率(1一p)接受子代个体为下一代群体中的个体，其中： 肚i鬲1+“pI半I ^和上分别为父代个体和子代个体所对应的目标函数值． 温度?由随着算法进程递减其值的控制参数担当。 2．6选择／复制操作 选择目的是从个体的解集中选出优良个体作为父代繁殖下 一代解集．形成交配池。选择操作采用赌轮法¨1和最优保留策 略相结合方法。在群体中选取优胜的个体，淘汰劣质的个体的 操作称作选择。根据染色体适应度值的大小选择适应性更强的 染色体生成群的种群。因此适应度值越大，被选中的概率就 万方数据 184 计算机应用与软件 2007卑 2．7算法停止准则 若经过若干代运算后，仍没有满足用户给定阈值的规则．则 结束，输出结果。 3仿真实验及 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 网络拓扑模型如图2所示，图中节点和边的参数按定义1 表示。分别应用GAsA和sA对其进行仿真实验和比较，主要验 证算法的收敛性和收敛过程等重要评价因素．进一步验证GA— s^的有效性和可用性。根据定义2，在仿真实验中，假定血= 80，功=36，且=16．A=0．002。 图2网络拓扑结构 如图3所示，GAsA能够很决地从局部优化解中摆脱，使用 上面的遗传运算能快速有效地完成全局优化解。图4所示为 GAsA能够在有限的遗传代数内得到晟优解。从以上对比可以 看出．采用cAsA比传统sA所选路由在收敛性和代价方面都更 具有优势。 厚：i图 图3㈣与sA请求成功率比较图4 cAs^与s^代价比较 相对于文献[3]，本算法采用树编码机制，克服了二进制编 码解码效率低，算法搜索空间大的缺点。同时，克服了文献[4] 算法容易陷于不成熟收敛．算法精度低的缺点。且本算法的交 叉操作无环，文献[4]的交叉操作容易形成回路，须采取相应措 施消除回路，这无疑增加了算法计算的时间复杂度。 4结论 本文首次提出采用遗传算法和模拟退火算法解决多约束 Q0s组播路由问题，通过实验证明，两种算法的结合，有利于丰 富优化过程中的搜索行为，增强全局和局部意义下的搜索能力 和效率．极大地发挥了遗传算法的全局搜索能力和模拟退火算 法的局部搜索能力，克服遗传算法局部搜索能力差及其早熟现 象和模拟退火算法全局搜索能力差、效率不高的问题。 参考文献 【l】c帅M．che“gRwGemtlc^】90ith吣口埘E“母neen“gDes研[M]． N删York：JohnWn。y＆SoIIB．1996． [2]sd锄aHF，R能懈Ds．vimotisY．Evdumj蛐dmulfic喊吼lll幄d． 印dtll啦如r嘲l·limcom加unicmi叽0nh1出一Bpcedn“work日[J]． IEEEJs^C，】997，15(3)：332—345 。 [3]Fxi肌g·LJ帅zhou，wJicyi，cGu蚰qunQosR蚰tin曲a5ed0n辨net— icm90ithm[J]c0“p咖rc蛳municmi帅s．1999，22(9)：13舛 一】399． [4]Ravikum甜cP．R刮n嘲hB由pai鼬Ir咖ba5dd山y—bound耐酬In* nirIg蛔mummdiane～orks[J]co呷uterco㈣ic帅om．1998，2l (2)：126—132． [5]王征应．石冰心，赵尔敦．Q0s组播路由的启发式遗传算法．电子学 报．2001(2)，253—256． (上接第73页) ·减少了管理服务器的通信压力，管理服务器只用管理网 络型读卡器的机号，而不用管理它的IP地址。 3．2嵌入式以太网通信服务器在“家校通”中工作原理 网络型读卡器是由网络通和读卡器组成．网络通有自己的 IP地址，读卡器有自己的机号．嵌入式以太网通信服务器也有 自己的IP地址和机号。如图4所示。 图4工作示意图 当读卡器有数据时，会通过网络传送到嵌入通信服务器，嵌 入通信服务器收到数据后，提取网络通的地址和读卡器的机号， 做成一个动态的lP地址和机号对应表。当Pc机有数据给通信 服务器时，提取数据中的机号，查找IP地址和机号对应表．然后 按照查到的IP地址发送数据给读卡器，这样就完成了读卡器和 Pc机之间的通信。 4结论 本文提出了嵌入式以太网通信服务器并对其进行研究实 现，事实表明嵌入式以太阿通信服务器作为终端设备的一个接 口，作用显著，减少了线路的成本，增加了数据在以太网上的传 输鼍，提高了工作效率，具有广泛的应用前景。 参考文献 [1]谭海，史应文，陈俊杰，肖可伟嵌入式关键技术及其实现．太原理 工大学学报．2003(5)：594—596． (2]孙占辉．Mcs巧1单片机原理与应用北京：清华大学出版社，1998： 100一101 [3]马忠梅．籍顺心，张凯．等单片机的c语言应用程序设计[M]．修 订版北京：北京航空航天大学出版社．2001． 【4]潘仕彬，何铮用于单片机的以太网网关——网络通[J]．单片机 与嵌^式系统应用，2002(3)． [5]丁展Vc网络通信编程[M]．北京：人民邮电出版社，1996：158—160． [6]谢君．唐章利．周维，李尚柏基于usB的飞机飞行参数传输系统 设计．微计算机信息，2006，2(2)：159一161 [7]葛永明．嵌人式系统以太网接口的{殳计[J]．电子技术应用，20∞(3)． [8]黎明Webchip智能Inlcn”I网络接口芯片及其应用f引武汉力源 电子股份有限公司，2000． 万方数据 基于遗传模拟退火算法的多约束QOS组播路由优化算法 作者： 屈志毅， 文雪飞， 范志明， 苏振明， Qu Zhiyi， Wen Xuefei， Fan Zhiming， Su Zhenming 作者单位： 兰州大学信息科学与工程学院,甘肃,兰州,730000 刊名： 计算机应用与软件 英文刊名： COMPUTER APPLICATIONS AND SOFTWARE 年，卷(期)： 2007,24(12) 被引用次数： 1次 参考文献(5条) 1.王征应;石冰心;赵尔敦 QoS组播路由的启发式遗传算法[期刊论文]-电子学报 2001(02) 2.Ravikumar C P;Rajneesh Bajpai Source-based delay-bounded multicasting in multimedia networks[外文 期刊] 1998(02) 3.F Xiang;L Junzhou;W Jieyi;G Guanqun QoS Routing based on genetic algorithm[外文期刊] 1999(09) 4.Salama H F;Reeves D S;Viniotis Y Evaluation of multicast routing algorithms for real-time communication on high-speed networks[外文期刊] 1997(03) 5.Gen M;Cheng R W Genetic Algorithms and Engineering Design 1996 引证文献(1条) 1.楚栋.宫兴致.程梁.余飞鸿 基于遗传退火算法的多层薄膜厚度测量[期刊论文]-光电工程 2010(2) 本文链接：http://d.g.wanfangdata.com.cn/Periodical_jsjyyyrj200712070.aspx