一种基于干扰感知的网络编码意识路由
摘要：针对编码机会对数据流传输相对集中的要求，而数据流集中可能会造成传输干扰增大的问题，提出一种新的考虑干扰感知的编码意识路由判据ecxwi，结合一定的路由发现、路由维护机制，形成一种新的编码意识路由算法carwi，该算法综合考虑了编码机会以及无线传输干扰等因素。仿真证明，并与采用最短路径路由的网络编码机会路由传输机制cope相比，carwi在网络吞吐量、端到端时延指标上有更优的表现。
关键词：无线ad hoc网络；网络编码；编码意识；干扰；
中图分类号：tp393 文献标识码：a 文章编号：1009-3044（2013）04-0726-05
network coding-aware routing based on the
interference-aware
tao yang， zhao jun-nan，
（chongqing university of posts and telecommunications，
chongqing 400065， china）
abstract： for the transmission of data stream required by
network coding is relatively concentrated， there may cause
the increasing interferences，a new routing metric ecxwi is
proposed in this paper. combined with the route discovery and
the route maintenance mechanism， a new coding-aware routing
algorithm carwi is also proposed. simulation shows that compared with network coding opportunities routing
・ ｌ２ ・ Ｃｏｍｐｕｔｅｒ Ｅｒａ Ｎｏ．１ ２０１ １
改进算子的遗传算法在ＱｏＳ多播路由优化上的应用
胡永刚，谷媛
（华北电力大学研究生院，河北保定０７１０００）
摘要：针对ＱｏＳ多播路由问题提出了一种改进遗传算子的遗传算法，通过设计多样性维持机制的选择算子、与代数相
关的交叉算子和与个体适应度相关的变异算子，有效地解决了传统遗传算法应用于多播路由优化时的旱熟收敛问题。
实验结果显示，在随机网络中，该算法所获得的解与最优解的相对误差不超过１．０％，算法的收敛速度和寻优能力明显优
于传统遗传算法。
关键词：ＱｏＳ；多播路由；遗传算法；遗传算子
Ａｐｐｌｉｃａｔｉｏｎ ｏｆ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ ｗｉｔｈ Ｉｍｐｒｏｖｅｄ Ｏｐｅｒａｔｏｒｓ
ｉｎ Ｑ０Ｓ Ｍｕｉｔｉｃａｓｔ Ｒｏｕｔｉｎｇ Ｏｐｔｉｍｉｚａｔｉｏｎ
ＨＵ Ｙｏｎｇ—ｇａｎｇ，ＧＵ Ｙｕａｎ
（Ｇｒａｄｕａｔｅ Ｃｏｌｌｅｇｅ，Ｎｏｒｔｈ Ｃｈｉｎａ Ｅｌｅｃｔｒｉｃ Ｐｏｗｅｒ Ｕｎｉｖｅｒｓｉｔｙ，Ｂａｏｄｉｎｇ，Ｈｅｂｅｉ ０７１０００，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｆｏｒ ＱｏＳ ｍｕｌｔｉｃａｓｔ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ，ａ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｉｍｐｒｏｖｅｄ ｇｅｎｅｔｉｃ ｏｐｅｒａｔｏｒｓ ｉｓ ｄｅｓｉｇｎｅｄ．Ｂｙ ｄｅｓｉｇｎｉｎｇ ｔｈｅ ｓｅｌｅｃｔｉｏｎ ｏｐｅｒａｔｏｒ ｗｉｔｈ ｄｉｖｅｒｓｉｔｙ ｍａｉｎｔａｉｎｉｎｇ ｍｅｃｈａｎｉｓｍ，ｔｈｅ ｃｒｏｓｓｏｖｅｒ ｏｐｅｒａｔｏｒ ｒｅｌａｔｅｄ ｔｏ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｇｅｎｅｒａｔｉｏｎｓ ａｎｄ ｔｈｅ ｍｕｔａｔｉｏｎ ｏｐｅｒａｔｏｒ ｄｅｐｅｎｄｉｎｇ ｏｎ ｆｉｔｎｅｓｓ ｖａｌｕｅ，ｔｈｅ ａｌｇｏｒｉｔｈｍ ｈａｓ ｅｆｆｅｃｔｉｖｅｌｙ ｓｏｌｖｅｄ ｔｈｅ ｐｒｅｍａｔｕｒｅ ｃｏｎｖｅｒｇｅｎｃｅ ｐｒｏｂｌｅｍ ｉｎ ｍｕｌｔｉｃａｓｔ
第３６卷
ＶｏＬ３６ 第５期
Ｎｏ。ｓ 计算机工程
Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ２０１０年３月
Ｍａｒｃｈ ２０１０
・网络与通信・ 文章编号：１０００－＿．３４２８（２０１０）０５—０ｌ０６＿＿＿０３ 文献标识码：Ａ 中圈分类号ｔ ＴＰ３０１．６
ＤＮＡ遗传算法的ＱｏＳ多播路由优化
唐天兵 ，申文杰 ，韦凌云
（１．广西大学计算机与电子信息学院，南宁５３０００４；２．北京邮电大学自动化学院，北京１００８７６）
■要：针对网络中的ＱｏＳ多播路由问题，提出一种基于ＤＮＡ的混合遗传算法，以遗传算法为框架，采用ＤＮＡ编码方式，对交叉算子
和变异算子进行改进，同时把小生境技术和模拟退火融入框架中，使小生境中的个体独立进行模拟退火操作，达到维护种群多样性和增强
局部搜索能力的目的。实验结果验证了该算法的有效性。
关黼：多播路由；遗传算法；ＤＮＡ计算；小生境；模拟退火
ＱｏＳ Ｍｕｌｔｉｃａｓｔ Ｒｏｕｔｉｎｇ Ｏｐｔｉｍｉｚａｔｉｏｎ ｆｏｒ ＤＮＡ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ
ＴＡＮＧ Ｔｉａｎ—ｂｉｎｇ ，ＳＨＥＮ Ｗｅｎ－ｊｉｅ ，ＷＥＩ Ｌｉｎｇ—ｙｕｎ
（１．Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ，Ｅｌｅｃｔｒｏｎｉｃｓ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ，Ｇｕａｎｇｘｉ Ｕｎｉｖｅｒｓｉｔｙ，Ｎａｎｎｉｎｇ ５３０００４；
２．Ｓｃｈｏｏｌ ｏｆＡｕｔｏｍａｔｉｏｎ，Ｂｅｉｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆＰｏｓｔｓ ａｎｄ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｂｅｉｊｉｎｇ １００８７６）
［Ａｂｓｔｒａｅｔｌ Ａ ｈｙｂｒｉｄ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ（ＧＡ）ｂａｓｅｄ ｏｎ ＤＮＡ ｉｓ ｐｒｏｐｏｓｅｄ ｆｏｒ ｔｈｅ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｍｕｌｔｉｃａｓｔ ｒｏｕｔｉｎｇ ｗｉｔｈ Ｑｕａｌｉｔｙ ｏｆ Ｓｅｒｖｉｃｅ（ＱｏＳ）
ｃｏｎｓｔｒａｉｎｔ．Ｂａｓｅｄ ｏｎ ｔｈｅ ｆｒａｍｅｗｏｒｋ ｏｆ ＧＡ ｗｉｔｈ ＤＮＡ ｃｏｄｉｎｇ ａｎｄ ｉｍｐｒｏｖｅｄ ｃｒｏｓｓｏｖｅｒ ａｎｄ ｍｕｔａｔｉｏｎ ｏｐｅｒａｔｏｒｓ，ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｉｓ ａｌｓｏ ｃｏｍｂｉｎｅｄ ｗｉｔｈ ｉｍｐｒｏｖｅｄ ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ ａｎｄ ｎｉｃｈｅ ｏｐｅｒａｔｉｏｎ ｔｏ ｍａｋｅ ｔｈｅ ｉｎｄｉｖｉｄｕａｌｓ ｏｆ ａ ｎｉｃｈｅ ｅｎｆｏｒｃｅ ｓｉｍｕｌａｔｅｄ ａｎｎｅａｌｉｎｇ ｏｐｅｒａｔｉｏｎ ｉｎｄｅｐｅｎｄｅｎｔｌｙ ａｎｄ ｔｏ ｋｅｅｐ ｔｈｅ ｄｉｖｅｒｓｉｔｙ ｏｆ ｐｏｐｕｌａｔｉｏｎ，ａｎｄ ｆｕｒｔｈｅｒ ｔｏ ｉｍｐｒｏｖｅ ｓｅａｒｃｈ ｃａｐａｂｉｌｉｔｙ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ａｎｄ ｃｏｎｖｅｒｇｅｎｃｅ ｒａｔｅ．Ｅｘｐｅｒｉｍｅｎｔａｌ
１４４ ２００７，４３（２７） Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用
基于量子遗传算法的ＱｏＳ多播路由算法
董武世，柯宗武，陈年生
ＤＯＮＧ Ｗｕ－ｓｈｉ，ＫＥ Ｚｏｎｇ－ｗｕ，ＣＨＥＮ Ｎｉａｎ－ｓｈｅｎｇ
湖北师范学院计算机科学系，湖北黄石４３５００２
Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，Ｈｕｂｅｉ Ｎｏｄａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｈｕａｎｇｓｈｉ，Ｈｕｂｅｉ ４３５００２，Ｃｈｉｎａ
Ｅ—ｍａｉｌ：ｈｓｃｈｅｎｎｓ＠１６３．ｃｏｎ
ＤＯＮＧ Ｗｕ－ｓｈｉ，ＫＥ Ｚｏｎｇ－ｗｕ，ＣＨＥＮ Ｎｉａｎ－ｓｈｅｎｇ．ＱｏＳ ｍｕｌｔｉｃａｓｔ ｒｏｕｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ＱＧＡ．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ
ａｎｄ Ａｐｐｆｉｃａｔｉｏｎｓ，２ＯＯ７，４３（２７）：１４４—１４７．
Ａｂｓｔｒａｃｔ：Ｔｈｅ ｋｅｙ ｐｒｏｂｌｅｍ ｏｆ ＱｏＳ ｍｕｌｔｉｃａｓｔ ｒｏｕｔｉｎｇ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｉｓ ｔｏ ｂｕｉｌｄ ＱｏＳ ｃｏｎｓｔｒａｉｎｅｄ ｍｕｈｉｃａｓｔ ｔｒｅｅ．Ｔｈｉｓ ｉｓ ｔｈｅ
ｍｏｓｔ ｎｏｔｅｄ ｐｒｏｂｌｅｍ ｉｎ ｃｏｍｐｕｔｅｒ ｎｅｔｗｏｒｋｓ ａｓ ｃｏｎｓｔｒａｉｎｅｄ ｍｉｎｉｍｕｍ Ｓｔｅｉｎｅｒ ｔｒｅｅ ｐｒｏｂｌｅｍ，ｗｈｉｃｈ ｈａｓ ａｌｓｏ ｂｅｅｎ ｓｈｏｗｎ ａｓ ＮＰ—ｃｏｎ—
ｐｌｅｔｅ．Ｑｕａｎｔｕｍ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｉｓ ａ ｎｅｗ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｑｕａｎｔｕｍ ｔｈｅｏｒｙ．Ａ ｍｕｌｔｉｃａｓｔ ｒｏｕｔｉｎｇ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ
ｗｉｔｈ ＱｏＳ ｃｏｎｓｔｒａｉｎｔｓ ｂａｓｅｄ ｏｎ Ｑｕａｎｔｕｍ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ（ＱｏＳＭＲ－ＱＧＡ）ｉｓ ｐｒｏｐｏｓｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ，ａｎｄ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｒｏｕｔｉｎｇ
