小生境遗传算法在网络编码优化中的应用研究

doi:10.3969/j.issn.1000-3428.2015.08.054

计算机工程

小生境遗传算法在网络编码优化中的应用研究

徐光宪¹,吴巍¹,周佳²

(1.辽宁工程技术大学电子与信息工程学院,辽宁葫芦岛 125105; 2.阜新市第三职业专科学校,辽宁阜新 123000)

收稿日期:2014-08-26 出版日期:2015-08-15 发布日期:2015-08-15
作者简介:徐光宪(1977-),男,副教授、博士,主研方向:网络编码,信息处理;吴巍,硕士;周佳,讲师。
基金项目:
辽宁省高等学校杰出青年学者成长计划基金资助项目(LJQ2012029)。

Application Research on Niche Genetic Algorithm in Network Coding Optimization

XU Guangxian ¹,WU Wei ¹,ZHOU Jia ²

(1.School of Electronic and Information Engineering,Liaoning Technical University,Huludao 125105,China; 2.The 3rd Fuxin College of Technology,Fuxin 123000,China)

Received:2014-08-26 Online:2015-08-15 Published:2015-08-15

摘要/Abstract

摘要： 网络编码技术在提高网络吞吐量和传输效率等方面具有较大优势,但该技术需要在节点处进行额外编码操作,增加了编码开销。为通过减少编码边数量来降低编码开销,提出基于小生境遗传算法的网络编码优化算法。通过多目标优化方式来构造适应度函数,保证降低编码边数量的同时可以兼顾网络带宽利用率。该算法在小生境遗传操作中使用自适应交叉和变异概率,避免运算过程中的无效操作,提高了运算效率。实验结果表明,该算法可有效降低编码开销,与简单遗传算法相比,具有更好的收敛性,能够在更短的时间内得到更少的编码边。

关键词: 编码开销, 网络编码优化, 多播速率, 多目标优化, 小生境遗传算法, 网络带宽利用率

Abstract: Network coding technology has great advantages in improving network throughput and transmission efficiency.However,this technique requires additional coding operation and increases coding overhead.In order to reduce coding overhead by reducing the number of coding edges,this algorithm introduces a network coding optimization scheme based on multi-objective niche genetic algorithm.The algorithm uses multi-objective optimization to structure fitness function.By this way,it can reduce the number of encoding side,while taking the network bandwidth utilization into account.In addition,the algorithm uses adaptive crossover and mutation probability in the operation of niche genetic,to avoid the invalid operations and to improve operational efficiency.Experimental results show that this algorithm can reduce the coding overhead effectively.Compared with Simple Genetic Algorithm(SGA),this algorithm has better convergence and gets less coding side in a shorter time.

Key words: coding overhead, network coding optimization, multicast rate, multi-objective optimization, niche genetic algorithm, network bandwidth utilization rate

中图分类号:

TP301.6

徐光宪,吴巍,周佳. 小生境遗传算法在网络编码优化中的应用研究[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2015.08.054.

XU Guangxian,WU Wei,ZHOU Jia. Application Research on Niche Genetic Algorithm in Network Coding Optimization[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2015.08.054.

参考文献

参考文献［1］Ahlswede R,Cai Ning,Li S Y R,et al.Network Information Flow［J］.IEEE Transacions on Information Theory,2000,46(4):1204-1216. ［2］Cai Ning,Yeung R W.Secure Network Coding［C］//Proceedings of IEEE International Symposium on Information Theory.Washington D.C.,USA:IEEE Press,2002:323-340. ［3］邓亮,赵新,王新,等.基于遗传算法的网络编码优化［J］.软件学报,2009,20(8):2269-2279. ［4］Li S Y R,Yeung R W,Cai Ning.Linear Network Coding［J］.IEEE Transactions on Information Theory,2003,49(2):371-381. ［5］黄政,王新.网络编码中的优化问题研究［J］.软件学报,2009,20(5):1349-1361. ［6］Kim M,Ahn C W,Medard M.On Minimizing Network Coding Resources:An Evolutionary Approach［C］//Proceedings of the NetCod.Boston,USA:IEEE Press,2006. ［7］Kim M,Medard M,Aggarwal V.An Evolutionary Approaches to Minimizing Network Coding Resources［C］//Proceedings of IEEE INFOCOM’07.Anchorage,USA:IEEE Press,2007. ［8］郝琨.网络编码关键技术及其应用研究［D］.天津:天津大学,2010. ［9］郝琨,金志刚.一种最小化编码节点的网络编码优化方法［J］.电子与信息学报,2011,33(2):260-265. ［10］邵星,王汝传,黄海平,等.基于模拟退火遗传算法的网络编码优化研究［J］.南京邮电大学学报,2013,33(2):80-83. ［11］徐光宪,吴巍.混沌序列在安全网络编码算法中的应用研究［J］.计算机应用研究,2014,31(4):1212-1214. ［12］陈立山.网络编码的安全性分析与研究［D］.西安:西安电子科技大学,2010. ［13］涂雪珠.遗传算法在多目标优化中的应用［D］.福州:福州大学,2004. ［14］郑金华.多目标进化算法及其应用研究［M］.北京:科学出版社,2007. ［15］蒋昀晰.自适应小生境遗传算法的研究［D］.淮南:安徽理工大学,2008. ［16］黄聪明,陈湘秀.小生境遗传算法的改进［J］.北京理工大学学报,2004,24(8):675-678. 编辑顾逸斐

[1]	东熠, 刘景发, 刘文杰. 基于多目标蚁群算法的主题爬虫策略[J]. 计算机工程, 2020, 46(9): 274-282.
[2]	刘颖, 王聪, 苑迎, 蒋国佳, 刘珂祯, 王翠荣. 基于Pareto熵的多目标虚拟网络映射算法[J]. 计算机工程, 2020, 46(8): 153-159.
[3]	李智翔,李赟,褚衍杰. 基于改进平衡策略的多目标分解优化算法[J]. 计算机工程, 2019, 45(3): 155-161.
[4]	张煜培,赵知劲,郑仕链. 基于多目标遗传的频谱切换目标信道序列设计算法[J]. 计算机工程, 2019, 45(2): 122-128.
[5]	刘景发,李新,蒋盛益. 基于网页空间进化算法的暴雨灾害主题爬虫策略[J]. 计算机工程, 2019, 45(2): 184-190.
[6]	邵先成,蔡超,王厚军,李东武. 基于二型模糊集推理的优化航路规划方法[J]. 计算机工程, 2018, 44(3): 287-293.
[7]	王林,胡雪婷. 基于多决策属性的社会网络核心节点识别[J]. 计算机工程, 2018, 44(1): 206-210.
[8]	曹道通,李敬文,文飞. 图的Smarandachely邻点可区别边染色算法[J]. 计算机工程, 2017, 43(9): 228-233,239.
[9]	吴琼,曾庆鹏. 基于多目标烟花优化算法的正负量化关联规则挖掘[J]. 计算机工程, 2017, 43(6): 158-168.
[10]	刘璐,郑力明. 基于邻域和变异算子组合优化的MOEA/D算法 [J]. 计算机工程, 2017, 43(3): 232-240.
[11]	刘超,贺利军,朱光宇. 基于熵和隶属度函数的高维多目标优化问题求解[J]. 计算机工程, 2016, 42(6): 185-190,195.
[12]	吴响,张鉴,邓笋根,陆忠华,胡晓东. 并行飞机气动模拟工作台软件[J]. 计算机工程, 2016, 42(4): 31-36.
[13]	陶文华,刘洪涛. 基于差分进化与NSGA-Ⅱ的多目标优化算法[J]. 计算机工程, 2016, 42(11): 219-224.
[14]	李靖,乔蕊,刘志中. 结合对策论与多目标MILP的Web服务组合调度问题求解[J]. 计算机工程, 2016, 42(1): 11-17.
[15]	朱光宇,贺利军. 基于灰熵并行分析优化算法的多目标流水车间调度[J]. 计算机工程, 2015, 41(10): 165-170.

小生境遗传算法在网络编码优化中的应用研究

Application Research on Niche Genetic Algorithm in Network Coding Optimization

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 10