通信专业硕士研究生开题报告-基于遗传蚁群算法的多路径路由研究.docx

1目 录一 课题的来源及意义1二国内外研究现状2三本课题研究内容33.1简单相关路径多路路由算法概述33.2 基于蚁群算法的路由研究与改进43.2.1 蚁群算法基本模型43.2.2 蚁群算法数学模型63.3基于遗传算法的路由研究与改进7四、预期成果8五、课题的可行性评估8六、总体进度安排9七、参考文献913一 课题的来源及意义无线通信技术的迅速发展，使得人们对移动通信的需求越来越强烈，人们通过配有无线接口的便携式计算机或个人数字助理（pda）来实现移动中的通信，目前的移动通信往往需要有固定基础设施的支持才能实现，例如全球通信系统（gsm）。但是当遇到医疗抢险、抗洪救灾以及军事战场等特殊紧急环境的时候，传统的无线网络就不可用了1。为了能够在没有固定基础设施的地方进行通信，一种被称作ad hoc(mobile ad hoc networks)网络的技术应运而生。移动ad hoc网络是一种新的移动无线网络系统，它不需任何固定基站设施，节点之间的通信可借助于其他的移动节点形成多跳通信完成2。由于该网络组网快速、灵活，抗毁性强，使用方便而且应用范围广泛，因此是当前网络和通信技术领域的研究热点之一。从研究内容看，ad hoc的网络层协议是研究的难点和重点，而路由算法又是网络层协议的核心技术问题3-4。adhoc网络作为一种新的组网方式，具有以下特点5。1.网络的独立性adhoc网络相对常规通信网络而言，最大的区别就是可以在任何时刻、任何地点不需要硬件基础网络设施的支持，快速构建起一个移动通信网络。它的建立不依赖于现有的网络通信设施，具有一定的独立性。adhoc网络的这种特点很适合灾难救助、偏远地区通信等应用。2.动态变化的网络拓扑结构在adhoc网络中，移动主机可以在网中随意移动。主机的移动会导致主机之间的链路增加或消失，主机之间的关系不断发生变化。在自组网中，主机可能同时还是路由器，因此，移动会使网络拓扑结构不断发生变化，而且变化的方式和速度都是不可预测的。对于常规网络而言，网络拓扑结构则相对较为稳定。3.有限的无线通信带宽在adhoc网络中没有有线基础设施的支持，因此，主机之间的通信均通过无线传输来完成。由于无线信道本身的物理特性，它提供的网络带宽相对有线信道要低得多。除此以外，考虑到竞争共享无线信道产生的碰撞、信号衰减、噪音干扰等多种因素，移动终端可得到的实际带宽远远小于理论中的最大带宽值。4.有限的主机能源在adhoc网络中，主机均是一些移动设备，如pda、便携计算机或掌上电脑。由于主机可能处在不停的移动状态下，主机的能源主要由电池提供，因此adhoc网络有能源有限的特点。5.网络的分布式特性在adhoc网络中没有中心控制节点，主机通过分布式协议互联。一旦网络的某个或某些节点发生故障，其余的节点仍然能够正常工作。6.生存周期短adhoc网络主要用于临时的通信需求，相对与有线网络，它的生存时间一般比较短。由于ad hoc网络无线信道的时变性大，信道带宽受限，节点的电源容量有限，拓扑结构不稳定，网络中没有固定基站或中心节点。这使得传统网络的路由算法和安全机制并不适用于ad hoc网络。ad hoc网络这些独有的特点使传统网络的路由算法不适用于ad hoc网络，而理想的ad hoc网络路由算法必须具有以下特点6-7：(l)分布式操作(2)提供无环路由 (3)维护多条路由(4)提供节能策略(5)提供安全机制 (6)支持单向链路 (7)提供qos保障 (8)支持组播功能。本文在参考了大量参考文献后，拟对ad hoc网络平面式多路径路由算法进行研究，并根据ad hoc网络路由的特点，利用蚁群算法和遗传算法对现有的平面式多路径路由算法进行优化，从而提出两种适合于ad hoc网络的多路径路由算法。二国内外研究现状ad hoc网络路由算法按路由发现方式可分为表驱动路由(table driven protocols)、按需驱动路由(on-demand driven protocols)和混合协议。表驱动路由协议又称为主动式路由协议、先应式路由协议，是一种基于路由表的路由协议。典型的按表驱动路由协议有dsdv8、fsr9 、olsr10。按需路由协议也称为反应式路由协议、源启动按需路由协议。典型的按需驱动路由有aodv11-12、adra13 、dsr14-15 、tora16、abr17-18协议。按需驱动路由协议不需周期性地进行路由更新，仅当源节点有通信需要又没有去往目的节点的路由时，才洪泛一个路由请求分组来创建路由，从而可降低先应式路由协议中不必要的路由查找开销，提高网络的吞吐量和带宽利用率。 按需路由协议按建立的路径数目可分为单路径路由和多路径路由，多路径路由指在源节点和目的节点之间允许建立多条路径的路由机制。典型的多路径路由协议有msr19、bsr20、aomdv21。多路径路由可以减少路由发现启动的次数，降低网络延迟，提高网络流通量和安全性能，有利于进行负载平衡，更好的支持qos（服务质量）要求22。文献23-24从理论上证明了按需多路径拥有较长的路径存活时间和更可靠的路由信息，而且拥有良好的性能，并能减少部分拥塞。而在多路径路由算法的研究中，利用智能算法进行路径搜索和优化是当前研究的热点，其中蚁群算法和遗传算法因其智能性和全局性的优点，很适合解决大规模网络路由优化问题。利用蚁群算法和遗传算法解决路由问题受到了广泛关注并已取得了一定的研究成果。如将蚁群算法和aodv协议结合的ant-aodv协议26-27, 基于源路由的ara28算法，基于请求/响应按需单路由算法的adra29算法以及amqr30算法等。综上所述，基于智能算法的多路径路由算法作为ad hoc网络的最具潜力的技术方案，受到了广泛关注，并已取得了一定的研究成果。但是，如何在减少路由查找的寻路开销，缩短路由寻找时间的同时又保证搜索到最优路径的概率是本研究领域仍然未能圆满解决的主要问题之一。为解决上述问题，本文分别将蚁群算法和遗传算法引入按需路由的搜索过程，从而加快算法收敛速度，减少寻路开销，并且通过同时多径的方式发送数据，以达到平衡网络负载，防止产生拥塞的目的。三本课题研究内容本课题借鉴简单相关多路径算法并融入蚁群算法和遗传算法的思想，从而提出两种适用于ad hoc网络的多路径路由算法，并在实验室已有的仿真软件上对所建立的路由算法进行仿真研究。3.1简单相关路径多路路由算法概述31简单相关多路路由算法的基本思想就是所建立的所有替换路径都靠近主路径，更进一步讲就是替换路径上的节点要么就是主路径上的节点，要么是主路径上节点的邻节点。其基本原理可归纳如下。源节点泛洪路由请求报文rreq。收到rreq的节点在确认本节点既不是目的节点，又没有发送过该rreq的条件下，计算本节点与发送给它rreq的上游节点链路之间的代价，将其写入rreq的cost域后转发此rreq。目的节点根据规定时间内接收到的所有rreq报文提取出网络拓扑信息，构建简单相关多路径路由。由上述原理可知，现有简单相关多路径算法采用洪泛方式建立路由，所以存在以下问题。（1）建立路由需要的时间长，且易产生泛洪，从而导致拥塞的产生。（2）简单相关多路径的多条路径是从目的节点在规定时间内接受到的多条路由内产生的，在这段时间内不一定能寻到最优路径。 （3）算法没有规定在特定网络约束条件下对路由进行优化的机制。 3.2 基于蚁群算法的路由研究与改进蚁群算法是最新发展的一种模拟昆虫王国中蚂蚁群体智能行为的仿生优化算法32,它具有较强的鲁棒性，优良的分布计算机制，易于与其他方法相结合等优点33-34，其思想来源于自然界中蚁群寻找食物过程的观察。 在觅食过程中,蚂蚁在它所经过的路径上会释放出与路径长度有关的信息素35-36, 路径越长，释放的信息量越小。后来的蚂蚁能感知信息素的存在及其浓度, 以此指导自己的运动方向,并倾向于朝着信息素浓度高的方向移动。于是, 蚂蚁的集体行为便表现出一种信息正反馈倾向。3.2.1 蚁群算法基本模型设网络中有四个节点a,b,c,d。要实现ab间的通信，由于通信距离或时延方面的限制，ab不能直接进行通信。必须通过节点c或d。这样ab通信有2条通信的支路acb和adb。acb支路的长度小于adb支路的长度，如图3-1所示。图3-1假设在节点a,b各有两只蚂蚁,蚂蚁1和2由节点a向节点b行进,同时蚂蚁3和4由节点b向节点a行进。在初始情况下,由于各个支路上没有任何信息素的痕迹存在,所以蚂蚁选择两条支路的概率是均等的;于是蚂蚁1和2将分别沿着支路acb和adb向节点b行进,同样,蚂蚁3和4也将沿着支路bca和bda向着节点a行进。假设蚂蚁行进的速度近似相同,一段时间之后蚂蚁2和蚂蚁4经过支路acb分别到达节点b和a,而蚂蚁1和3却还在支路adb的途中,如图3-2所示。图3-2在蚂蚁行进的过程中,每个蚂蚁均留下了同样数量信息素的痕迹。这时支路acb上留下的信息素痕迹浓度要高于支路adb上的信息素浓度;此后若再有蚂蚁到达节点a和b时,由于受到信息素痕迹的诱导,它们选择支路acb的概率就会较大,反过来又不断地增加支路acb上的信息素痕迹浓度,形成正反馈;与此同时,遗留在支路adb上信息素的痕迹还会因不断挥发而进一步减弱。这样,选择走支路acb的蚂蚁会越来越多,而选择走adb的蚂蚁就越来越少,最后呈现较强的信息素痕迹的那些支路便会形成一条从蚁穴到食物源的最短路径。3.2.2 蚁群算法数学模型 基本蚂蚁算法数学模型如下37-40：表示在t时刻蚂蚁由城市i转移到城市j的状态转移概率, 公式(1)式中,tablek表示蚂蚁下一步允许选择的城市为信息启发因子,表示轨迹的相对重要性,反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用,其值越大,则该蚂蚁越倾向于选择其它蚂蚁经过的路径,蚂蚁之间的协作性越强。为期望启发式因子,表示能见度的相对重要性,反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度,其值越大,则该状态转移概率越接近于贪心规则。ij为启发函数,其表达式如下：ij=1/d(i,j)式中, d(i,j)表示相邻两个城市之间的距离,对蚂蚁k而言, d(i,j)越小,则ij越大,也就越大,为了避免残留信息素过多引起残留信息淹没启发信息,在每只蚂蚁走完一步或者完成对所有个城市的遍历即一个循环结束后,要对残留信息进行更新处理,由此,t+n时刻在路径上的信息量可按如下规则进行调整：ij（t+n）=(1-) ij(t）+ij(t)公式（2）ijt=k=1mijk(t) 公式(3)式中,表示信息素挥发系数,则1-表示信息素残留因子,为了防止信息素的无限积累, 的取值范围为0,1 ,ij表示本次循环中第k只蚂蚁在本次循环中留在路径上的信息量。根据信息素更新策略的不同，有三种不同的基本蚂蚁算法模型，即ant-cycle模型、ant-quantity模型及ant-density模型，其差别在于ij(t)的不同。本算法根据具体问题采用了ant-quantity模型。本文结合具体的路由要求设计了适合于本算法的蚁群模型，针对时延问题进行了优化，使算法能够在最短的时间内寻找到传输时间最短的路由。并且给蚂蚁设定年龄域，限定无用的前向蚂蚁在网络中传输，节省了路由查找开销同时能防止拥塞的产生。3.3基于遗传算法的路由研究与改进遗传算法是由美国的johnholland教授于1975年首先提出的一类仿生型优化算法41，具有大范围快速全局搜索能力。与自然界相似，遗传算法对求解问题的本身一无所知。遗传算法是从代表问题可能潜在解集的种群开始的，而种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现(即基因型)是某种基因组合，它决定了个体形状的外部表现。因此，在一开始需要实现从表现型到基因型的映射即编码工作。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代(generation)演化产生出越来越好的近似解。在每一代进化过程中，根据问题域中个体适应度大小来挑选(selection)个体，借助于自然遗传学的遗传算子(genetieoperators)进行组合交叉(erossover)和变异（mutation)，产生出代表新解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码(decoding)，可以作为问题近似最优解，这就是遗传算法基本思想42。遗传算法应用于路由问题需要确定以下要素：（1）编码规则：需要针对具体的物理模型提出合适的编码方法；（2）创建初始群体：即确定路径解集；（3）确定适应度函数：即确定路由是根据那些参数的优化并确定参数的权重；（4）确定遗传算子：即确定选择、交叉、变异的方法。将传统遗传算法直接应用于路由选择存在以下问题：（1）、传统的0-1编码不能很好的反应实际物理模型。（2）、简单的初始种群形成方法和交叉、变异操作容易产生非法路径。（3）、通用的遗传算法在解决qos问题时具有单一约束上的困难。对于以上几点现有的文献已有很好的解决。如问题（1）可以采用可变长度编码方案解决；问题（2）可采用去环路的方案解决；问题（3）也已有大量的文献进行了研究。但在已有的遗传算法应用于路由的文献中，选择，交叉，变异的过程都是采用按概率随机选择的方法，这种方法具有多样性好和全局性好的优点，但针对具体的路由问题具有以下缺点：1.每次迭代前需要遍历所有父代个体，并计算每条染色体的概率，增加了算法复杂度；2.按概率随机性选择会存在统计误差，导致一些本来优秀的染色体丢失。由于本算法仅需要保存最优的几条路径，对多样性要求不高，针对路由问题，解集多样化固然重要，但减小路由开销和缩短路由寻找时间才是最重要的，基于以上原因，本文拟对基本遗传算法进行改进，提出一种确定性按比例遗传算法，即按比例确定参与遗传算子操作的个体。确定性选择既保留了传统遗传算法可产生多样化解集的优点，又能保证算法可以以最快速度收敛到最优，同时减小了算法的复杂度，具有易实施的优点。本文将改进的遗传算法应用到简单相关多路径中，在目的节点搜索到路径解集后，利用遗传算法进行优化，通过选择、交叉、变异的过程实现在不需要增加任何寻路开销的前提下对路径优化的目的。四、预期成果1.对ad hoc网络的特点，信道特性进行研究，分析适用于ad hoc网络的路由算法的特点。2.分析简单相关多路径算法的优缺点，将蚁群算法引入简单相关多路径算法，从而提高简单相关多路径算法的路由寻找速度，提出一种适用于ad hoc网络的多路径算法。3.将遗传-蚁群算法引入简单相关多路径算法，从而得到一种适用于ad hoc网络的搜索性能更佳的路由选择算法。4.应用仿真软件对所提出的两种算法进行仿真研究。从理论上得出算法的可行性和优越性。 五、课题的可行性评估ad hoc网络在未来几年有着极其诱人的前景和潜在的巨大市场。国内外均有大量相关资料可供查阅，这些研究为迄今为止的ad hoc路由技术开发和系统设计提供了必要的参考依据和理论指导，也为本研究提供了丰富的基础数据。现在，蚂蚁算法和遗传算法受到广泛关注，作为一种新兴的仿生学算法由于其良好的并行性对解决np-完全问题起到了良好的效果。并在车间作业调度问题，聚类分析、车辆路径问题等方面取得了一系列成果。尤其蚂蚁算法在网络路由问题方面的研究与本课题学科领域相近，可为本课题在方法论和技术路线上提供指导。迄今为止，课题研究人一直从事蚂蚁算法，遗传算法以及ad hoc网络路由的学习研究，对蚂蚁算法，遗传算法和ad hoc网络有较为全面的掌握，知识上有较为充分的储备。此外，本课题着重研究的内容已取得阶段性的成果，为课题的完成打下了基础。本课题研究主要在实验室完成。实验室师兄师姐已经从事过路由算法及蚂蚁算法的研究，可以在我的课题研究中给予适当的帮助。综上所述，本课题已具备了比较充分的理论基础和仿真验证，已打下较为扎实的基础，预计可以成功实现。六、总体进度安排2009.7-2009.10 相关知识积累，包括ad hoc网络，蚂蚁算法，遗传算法的学习。2009.11-2010.2 设计基于蚁群算法的ad hoc网络路由选择算法。2010.3-2010.5 完善基于蚁群算法的ad hoc网络路由选择算法，利用仿真软件进行仿真，证实其理论可行。2010.6-2010.10 设计基于遗传-蚁群算法的ad hoc网络路由选择算法2010.11-2010.12 完善基于遗传-蚁群算法的ad hoc网络路由选择算法，利用仿真软件进行仿真，证实其理论可行2011.1-2011.3 完成论文写作。七、参考文献1 炊昆，梁雪.ad hoc网络技术综述.计算机与网络，2008：578-5792 ram ramanathan, jason redi. a brief overview of mobile ad hoc networks: challenges and directions j. ieee communications magazine 50th anni-versary commemorative issue, 2002, 40 (5): 20-23.3 程林,陈福生. 无线 ad hoc 网络路由协议的分析比较j. 计算机工程与应用,2004, 40(22):143-149.4 全武,宋瀚涛等. ad hoc 无线网络及其路由选择协议j. 计算机应用, 2002,22(6):26-31.5 于毅宏等著.无线移动自组织网。北京：人民邮电出版社。2005.6 李浩君，邱飞岳，王丽萍.无线网络中由协议研究与展望j.中国有线电视，2004(9)7 tanx，lee h w.slotted aloha protocols for data packet transmissions over wide band satellite system with a large number of small lvoice and data users.proeessing of ieee commnications computers and signal，pacifierim，1989，l(2):487-490.8 perkins ce，bhagwat p. highly dynamic destination-sequenced distance-vector routing(dsdv) for mobile computers. in:proeeedings of sigcomm 4.newyork:acm press，1994：234244.9 g pei，m.gerla and t.w.chen.fisheye state routing: a routing scheme for ad hocwireless networksa. proceedings of the ieee intemational conference on communications(icc)c，new orieans，la，june2000：70-74.10 t.clausen and p.jacquet.optimized link state routing protocol for ad hoc networksiaieee inmicc，pakistan，2001：62-68.11 c. e. perkins, e.m. royer. ad hoc on-demand distance vector routingc./ proeeedings of the 2nd ieee workshop on mobile computing systems and applieations(wmcsa,99).new orleans,la,february 1999: 90-100.12 perkins ce，royer em. ad hoc on demand distance vector ceeding of ieee work-shop on mobile computing systems and applications(wmcsa)，new orleans，1999(6):90-10013 zheng xiangquan, guo wei, liu renting. an ant-based distributed routing algorithm for ad-hoc networks international conference on communicationsc./ circuits and systems, 2004 (icccas 2004). 2004: 412 -417.14 jolmson db，maltz da，hu yc.the dynamic source routing protocol for mobile adhoc networks(dsr).ietf draft-ietf-manet-dsr-10.txt，2004. 15 d. b. johnson. dynamic source routing in ad hocwireless networks mobile computing，kluwer academic publisher，1995，5:153-18l16 v.park and m.s. corson. temporally-ordered routing algorithm(tora).intemetdraft; november 2000.17 c-ktoh.associativity-based routingfor ad-hoc mobile networks.wireless personal communications joumal，1997，4(2):103-139.18 c.k.toh.”a novel distributed routing protocol to support ad-hoc mobile computing”，proceedings of 15th ieee annual intemational phoenix conference on computers and colnlnunications，arizona，usa，1996：450-456.19 ja. nasipuri and s.r. das，on-demand multipath routing for mobile ad hoc networks，proceedins of ieee international conferenceon computer communication and networks korea.1999(7):64-7020 volera.a，seah，w.k.g，rao，backup source routing multipath routing in mobile ad hoc networks. proceeding of the ieee infocom，newyork，2003(3):34-50.21 zhenqiangye，srikanthv. krishnamurthy，a framework for reliable routing in mobile adhoc nceedings of the ieee infocom.austin，2003(10):12-30.22 陈跃全,郭晓峰,曾庆凯等.ad hoc移动网络多路径研究.计算机科学，2005，32(6). 23 nasipuria,dassr.on-demand multipath routing for mobile ad hoc networksc, computer communicationsand networks conference new orelans:ieeepress, 1999:64-70.24 johansonp,larssont,hedmann,eta. lscenario based performance analysis of routing protocols for mobile ad hoc networksc,proceeding of the acm,ieee international conferenceon mobile computing and networking. sanan-tonio:ieee press,1999:195-206.25 marco dorigo, thomas sttzle. ant colony optimization m.massachusettes: mit press, 2004.26 s marwaha, c k tham, d srinavasan. mobile agents based routing protocol for mobile ad hoc networks a. in ieee grobal telecommunications conference (globecom02) c. taipei, taiwan, 2002-11.27 s marwaha, c k tham, d srinavasan. a novel routing protocol using mobile agents and reactive route discovery for ad-hoc wireless networks, towards network superiority a. proceedings of ieee international conference on networks 2002(icon 2002) c. 2002-08.28 mesut gunes, udo sorges, imed bouazizi. ara-the ant-colony based routing algorithm for manets a. in international conference on parallel processing workshops (iccpw02) c. vancouver, b.c., canada, 2002-08. 79-85.29 xiangquan zheng, wei guo, renting liu. an ant-based distributed routing algorithm for ad-hoc networks international conference on communications, circuits and systems a. 2004 (icccas 2004) c. 2004-06, 1: 412 -417.30 lianggui liu, guangzeng feng. a novel ant colony based qos-aware routing algorithm for manets. icnc 2005,lncs 3612:457-466.31 杨鹏. 基于移动 ad hoc 网络的多路路由算法j. 计算机工程与应用, 2008, 44(7): 119-121.32 colorni a,dorigo m,maniezzo v.distributed optimization by ant colonies.proceedings of the 1st european confe