基于遗传算法的计算机通信网优化设计

第３４卷　

Ｖｏ１．３４　第１Ｏ期　

Ｎｏ．Ｊ　计算机工程　

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　２００８年５月　

Ｍａｙ　２００８　

・人工智能及识别技术・　文章缩号，１００１）－－－３４２８（２００８）１０－－－０２０７－－０３　文献标识码，Ａ　中圈分类号，ＴＰ３９３　

基于免疫遗传算法的ＱｏＳ选播路由　

向羹橙，乐晓波，唐贤瑛　

（长沙理工大学计算机与通信工程学院，长沙４１００７６）　

摘要：将免疫算法与传统遗传算法相结合，既保留了原算法较强的全局搜索能力，又避免了局部搜索性能差和早熟现象。在提出改进算　

法的基础上，对带时延约束的ＱｏＳ选播路由问题作了深入研究，并经过实验分析证明，该算法提高收敛速度接近１８％，而且具有更高的　搜索精度和更可靠的稳定性等特点。　

关健诃：免疫遗传算法；ＱｏＳ路由问题；选播路由　

ＱｏＳ　Ａｎｙｃａｓｔ　Ｒｏｕｔｉｎｇ　Ｂａｓｅｄ　ｏｎ　Ｉｍｍｕｎｅ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　

ＸＩＡＮＧ　Ｙｕｎ－ｓｏｎｇ，ＹＵＥ　Ｘｉａｏ－ｂｏ，ＴＡＮＧ　Ｘｉａｎ－ｙｉｎｇ　

（Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｃｏｍｍｕｎｉｃａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｃｈａｎｇｓｈａ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ　４１００７６）　

［Ａｂｓｔｒａｃｔｉ　Ｔｈｉｓ　ｐａｐｅｒ　ｃｏｍｂｉｎｅｓ　ｔｈｅ　ｉｍｍｕｎｅ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｔｈｅ　ｔｒａｄｉｔｉｏｎａｌ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ａｎｄ　ｉｔ　ｒｅｓｅｒｖｅｓ　ｏｒｉｇｉｎａｌ　ａｌｇｏｒｉｔｈｍ　ｓｕｐｅｒｉｏｒ　ｓｅａｒｃｈ　ａｂｉｌｉｔｙ　ｆｏｒ　ｇｌｏｂａｌ　ｓｅａｒｃｈ　ａｎｄ　ａｖｏｉｄｓ　ｐｏｏｒ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｌｏｃａｌ　ｓｅａｒｃｈ　ａｎｄ　ｐｒｅｃｏｃｉｏｕｓ　ｐｈｅｎｏｍｅｎｏｎ．Ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ，ｔｈｅ　ｐｒｏｂｌｅｍ　ｏｆ　ｄｅｌａｙ—ｃｏｎｓｔｒａｉｎｅｄ　ＱｏＳ　ａｎｙｃａｓｔ　ｒｏｕｔｉｎｇ　ｉｓ　ｌｕｂｒｉｃａｔｅｄ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔａｌ　ａｎａｌｙｓｉｓ　ｃｅｒｔｉｆｉｃａｔｅ　ｔｈａｔ　ｔｈｅ　ｉｍｐｒｏｖｅｄ　ａｌｇｏｒｉｔｈｍ　ｈａｓ　ｅｎｈａｎｃｅｄ　１　８％ｒａｔｅ　ｏｆ　

第４８卷第３期　２０１０年５月　吉林大学学报（理学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｊｉｌｉｎ　Ｕｎｉｖｅｒｓｉｔｙ（Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　Ｖｏ１．４８　Ｎｏ．３　Ｍａｖ　２０１０　

一种基于遗传算法的无线传感器　

网络路由算法　

张重毅　，刘彦斌　，于繁华　，刘大有　

（１．吉林大学计算机科学与技术学院，长春１３００１２；２．长春师范学院计算机科学与技术学院，长春１３００３２）　

摘要：针对传感器节点在能量储备、计算能力、通信能力方面制约性强等１＇４题，采用进化算　

法理论，提出一种适用于无线传感器网络的移动Ａｇｅｎｔ路由选择算法．该算法能为移动Ａｇｅｎｔ　

探测具有最小能耗的路径，同时保证信息收集的完整性．实验结果表明，该算法自适应性强，　可减少传感器节点的能量消耗，满足无线传感器网络在实际应用中对移动Ａｇｅｎｔ路由算法的　

需求．　关键词：无线传感器网络（ＷＳＮｓ）；移动Ａｇｅｎｔ；路由问题；遗传算法　

中图分类号：ＴＰ３９　文献标志码：Ａ　文章编号：１６７１－５４８９（２０１０）０３－０４３３－０６　

Ａ　Ｓｏｌｕｔｉｏｎ　ｏｆ　Ｒｏｕｔｉｎｇ　Ｐｒｏｂｌｅｍ　Ｂａｓｅｄ　ｏｎ　Ｇｅｎｅｒａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍ　

ｉｎ　Ｗｉｒｅｌｅｓｓ　Ｓｅｎｓｏｒ　Ｎｅｔｗｏｒｋｓ　

ＺＨＡＮＧ　Ｚｈｏｎｇ＇ｙｉ。ｒ，ＬＩＵ　Ｙａｎ—ｂｉｎ　，ＹＵ　Ｆａｎ．ｈｕａ　，ＬＩＵ　Ｄａ－ｙｏｕ　（１．Ｃｏｌｌｅｇｅ　ｏｆＣｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｊｉｌｉｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｃｈｕｎ　１３００１２，Ｃｈｉｎａ；　２．Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｃｈｕｎ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｍｉｔｙ，Ｃｈａｎｇｃｈｕｎ　１３００３２，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：Ｔｈｅ　ａｕｔｈｏｒｓ　ａｎａｌｙｚｅｄ　ｔｈｅ　ｃｏｎｓｔｒａｉｎｔ　ｃｏｎｄｉｔｉｏｎｓ　ａｎｄ　ｔｈｅ　ｏｂｊｅｃｔｉｖｅ　ｆｕｎｃｔｉｏｎ　ｏｆ　ｔｈｅ　ｍｏｂｉｌｅ　Ａｇｅｎｔ　ｒｏｕｔｉｎｇ　ｐｒｏｂｌｅｍ　ｉｎ　ＷＳＮｓ．Ｗｅ　ｅｍｐｌｏｙｅｄ　ｔｈｅ　ｔｈｅｏｒｙ　ｏｆ　ｅｖｏｌｕｔｉｏｎａｒｙ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｐｒｏｐｏｓｅ　ａ　ｎｅｗ　ｍｅｔｈｏｄ　ｏｆ　ｇｅｎｅｔｉｃ　

第２７卷　

２００７年１２月　计算机应用　

Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　Ｖｏ１．２７　

Ｄｅｃ．２ｏｏ７　

文章编号：１００１—９０８１（２００７）ｓ２—０１９７—０２　

基于遗传算法的星载计算机可靠性冗余优化研究　

马秀娟　，牛进鹏　，赵国良　

（１．哈尔滨工程大学信息科学与工程学院，哈尔滨１５０００１；　

２．哈尔滨工业大学（威海）信息科学与工程学院，山东威海２６４２Ｏ９）　

（ｎｉｕｊｉｎｐｅｎｇ４２０＠ｙａｈｏｏ．ｃｏｍ．ｃｎ）　

摘要：针对小卫星系统可靠度函数非线性的特点，建立其可靠性冗余优化模型并提出一种基于　

遗传算法的冗余优化方法。通过对不同遗传算法的仿真过程和结果的对比分析，并对特定计算步骤　

加以改进，找到了最佳计算方案。仿真结果表明，该算法应用于星载计算机系统冗余优化中具有可行　

性和高效性。　

关键词：遗传算法；星载计算机；可靠性　

中图分类号：ＴＰ３０１．６　文献标志码：Ａ　

０　引言　

小卫星的特点是重量轻、体积小、成本低、研发周期短和　

发射灵活。在现代通信技术和局部战争中小卫星以其自身独　

特的优势越来越受到人们的关注。为了提高小卫星的可靠　性，一般采用冗余技术，由于体积、重量、费用的苛刻要求使得　

各个单元的冗余优化特别重要。系统的可靠度函数具有非线　

性的特点，经典的可靠性冗余优化分析方法在实际中很难应　

用。遗传算法…是仿造自然选择的遗传基本法则，具有适应　

性强，易于操作和全局搜索的特点，在很多领域已得到广泛应　用。　本文以某小卫星为蓝本，利用遗传算法对其进行可靠性　冗余优化研究，在Ｍａｔｌａｂ仿真结果对比分析的基础上找到最　

优的计算方法。　

ｌ　目标函数的建立　

某小卫星的基本原理　２　如图１所示。它由６个基本模块　

组成，采用星上现场网络技术，各个单元都是一个相对独立的　模块。由于每个模块失效都会使整个小卫星失效，所以小卫星　

可靠性模型可近似等价于各个子系统之间串联，如图２所示。　

Ａ　星上网　

ＣＮ４３－１２５８／ＴＰ　ＩＳＳＮ　１００７—１３０Ｘ　计算机工程与科学　

ＣＯＭＰＵＴＥＲ　ＥＮＧＩＮＥＥＲＩＮＧ＆ＳＣＩＥＮＣＥ　２００７年第２９卷第９期　

Ｖｏ１．２９，Ｎｏ．９，２００７　

文章编号：１００７－１３０Ｘ（２００７）０９－００９１—０３　

求解传感器网络生存时间　

最大化问题的遗传算法编码设计’　

Ｇｅｎｅｔｉｃ　Ｃｏｄｉｎｇ　Ｄｅｓｉｇｎ　ｏｆ　ｔｈｅ　Ｌｉｆｅｔｉｍｅ　

Ｍａｘｉｍｉｚａｔｉｏｎ　Ｐｒｏｂｌｅｍ　ｏｆ　Ｓｅｎｓｏｒ　Ｎｅｔｗｏｒｋｓ　

潘晏涛，朱培栋　

ＰＡＮＹａｎ－ｔａｏ，ＺＩｔＵＰｅ￣ｄｏｎｇ　（国防科技大学计算机学院，湖南长沙４１００７３）　

（Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｎａｔｉｏｎａｌ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｄｅｆｅｎｓｅ　Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ　４１００７３，Ｃｈｉｎａ）　

摘要：求解传感器网络最大生存时间是设计高性能路由协议和拓扑控制协议的理论基础，在实践上有很重要的意　

义。目前主要通过近似算法求解，而且没有考虑到接收功耗。本文对生存时问优化问题进行了形式化描述，给出了最佳传　

输方案和最大生存时间的定义，从遗传算法角度给出了求解该问题的两个编码方案并进行了比较。　

Ａｂｓｔｒａｃｔ：Ｉｔ　ｉｓ　ａ　ｔｈｅｏｒｅｔｉｃａｌ　ｂａｓｉｓ　ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｌｉｆｅｔｉｍｅ　ｍａｘｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍ　ｏｆ　ｄｅｓｉｇｎｉｎｇ　ｅｎｅｒｇｙ－ｅｆｆｉｃｉｅｎｔ　ｒｏｕｔｉｎｇ　ｏｒ　ｔｏ—　

ｐｏｌｏｇｙ　ｃｏｎｔｒｏｌ　ｐｒｏｔｏｃｏｌｓ．Ｍａｎｙ　ａｐｐｒｏａｃｈｅｓ　ｆｏｃｕｓ　ｏｎ　ｔｈｉｓ　ｐｒｏｂｌｅｍ　ａｎｄ　ｈｅｕｒｉｓｔｉｃ　ａｌｇｏｒｉｔｈｍｓ　ａｒｅ　ｐｒｏｐｏｓｅｄ　ｗｈｅｒｅ　ｔｈｅ　ｅｎｅｒｇｙ　ｃｏｎｓｕｍｅｄ　ｂｙ　ｒｅｃｅｉｖｉｎｇ　ｄａｔａ　ｉｓ　ｎｏｔ　ｃｏｎｓｉｄｅｒｅｄ．Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ｗｅ　ｄｅｆｉｎｅ　ｔｈｅ　ｔｒａｆｆｉｃ　ｐｌａｎｎｉｎｇ　ａｎｄ　ｉｔｓ　ｃｏｒｒｅｓｐｏｎｄｉｎｇ　ｌｉｆｅｔｉｍｅ　ｏｆ