足球比分直播

基于改进蚁群算法的Ad+Hoc网络路由算法分析.pdf

返回
基于改进蚁群算法的Ad+Hoc网络路由算法分析.pdf_第1页
第1页 / 共53页
基于改进蚁群算法的Ad+Hoc网络路由算法分析.pdf_第2页
第2页 / 共53页
基于改进蚁群算法的Ad+Hoc网络路由算法分析.pdf_第3页
第3页 / 共53页
基于改进蚁群算法的Ad+Hoc网络路由算法分析.pdf_第4页
第4页 / 共53页
基于改进蚁群算法的Ad+Hoc网络路由算法分析.pdf_第5页
第5页 / 共53页
点击查看更多>>
资源描述:
ABSTRACTMobile Ad Hoc network is a multi-hop wireless network which ISself-organized,110 center,no base station to support.This network can work in thecondition of the node topology change greatly,and ale more widely used among thevarious fields.Each node of the ad hoe network Can act as a host or router,androuting technology is a critical problem in mobile ad hoe network·This paper reviews the current proposed researches which based on mobile adhoc network routing protocols,and elaborated on various routing protocols·Sincesome multipath selection protocol may be too focused on several particular optimalDaths therefore the 10ad is too focused on these paths,which is not benefit data缸aI】【smission.Tbo focused on several paths will result in delay increased and thenode packet delivery rate reduced.Therefore,a novel multipath muting protocolwllich based on AOMDV together with improved ant colony algorithmIACBAOMDVproposed in this paper.IACB-AOMDV algorithm using the antcolony algorithm’s characteristics of heuristic search path,and proposed the conceptof the node connection density factor.When the node density is relatively large,changing the path pheromone which connected to its neighbors adaptively,SOphetomone distribution is conducive to different neighbor path,it is in favor ofre山lce pam,s load balancing,and on the basis of the reliability of the node to find anumber of different paths.We Can use backup path in time when the main pathdisconnect,and it Can reduce the cost of rerouting discovery.AOMDV and IACB.AOMDV algorithms will be tested on the NS2,comparedtheir,s average end to end delay,packet delivery ratio and packet overhead.Theexperiment results show that IACBAOMDV algorithm have lower average end toend,lose packet ration and packet overhead,can improve the network perance·Key WordsAd Hoc network;AOMDV protocol;Ant Colony algorithm;NS2Ⅱ目录目 录第l章引言.11.1课题研究的背景及意义.11.1.1课题背景11.1.2研究的意义21.2国内外研究现状31.3本文的主要工作..41.4论文的组织结构..4第2章Ad Hoc网络概述及路由协议研究62.1 Ad Hoe网络概述.62.1.1 Ad Hoe网络定义62.1.2 Ad Hoc的主要特点72.1.3 Ad Hoe网络的应用82.1.4 Ad Hoe网络的研究方向一82.2 Ad Hoc网络路由协议分类.92.3 Ad Hoe网络多路径路由协议.132.3.1多路径路由协议分类132.3.2典型的多路径路由协议142.4本章小结17第3章蚁群算法概述1 83.1蚁群算法原理183.2蚁群算法的数学模型和实现步骤203.2.1蚁群算法的数学模型..203.2.2基本蚁群算法的实现步骤213.3典型的蚁群优化算法2l3.4蚁群算法应用243.5本章小结25目录第4章基于改进蚁群算法的AOMDV多路径路由算法。264.1 IACB.AOMDV算法思想264.1.1算法基本思想..264.1.2算法的描述..284.2 IACB.AOMDV算法设计..294.2.1节点连接密度因子..j..294.2.2路由节点选择概率.294.2.3自适应调整概率值.3 14.2.4算法的数据结构.324.3 IACB.AOMDV算法实现步骤..354.3.1多径路由发现过程.354.3.2路由维护过程.374.4本章小节37第5章IACB.AOMDV算法的仿真和性能分析385.1 NS2网络仿真模拟器385.1.1 NS的无线节点385.1.2 NS中的仿真步骤405.2仿真参数选择405.3性能评价指标.405.4仿真结果与分析415.5本章小结46第6章结论与展望486.1结论486.2进~步工作的方向48致谢.50参考文献.5 1攻读学位期间的研究成果.54IV第1章引言第1章引言1.1课题研究的背景及意义1.1.1课题背景近年来,人们对无线通信的要求越来越高,需求逐步地从传统的有固定基础设施的无线通信模式发展到无固基定基础设施的无线通信模式。蜂窝移动通信技术、无线局域网IEEE802.11、蓝牙技术Blue Tooth和家庭无线网HomeRF等移动通信新技术也纷纷涌现。在某些特殊场合下,如军事战场、偏远山区、旅途中的视频会议或极端恶劣情况下,往往没有固定的基础设施,这就需要无线移动网络技术的支持,因此移动Ad Hoc网络又称MANETMobile Ad HoeNetwork受到越来越多的受到关注llJ。在Ad Hoe网络中,移动节点既当主机又被当成路由器来使用,这样既节约了固定基站建设的成本,又方便了人们的通信。由于Ad Hoe网络存在拓扑变化频繁、带宽受限、安全性低等问题,因此为了提高网络中数据的传输质量,如何准确地寻找到从源节点到目的节点的路由是Ad Hoc网络通信的关键问题之一。蚁群算法是一种具有启发式搜索特性的仿生优化算法,是在研究真实的蚂蚁的群体觅食行为的基础上最早提出来的,并在实验中取得了良好的效果,因此这种新型的仿生优化算法也引起了越来越多的关注。蚁群算法具有能发现较好解、有较强的鲁棒性、易于与其它算法相结合等优点,并在近年来被广泛运用于组合优化、移动通信等不同的应用领域。因而将蚁群算法与移动Ad Hoc网络路由协议结合越来,能够充分地利用蚁群算法寻找路径时能发现较好解等优点,在网络中寻找到更优的路径以供进行数据的发送。而且两者的结合也能很好地解决网络拥塞以及找到的路径过于单一等问题,在路由发现的过程中,平衡各路径上的拥塞情况并找到多条有效的路由。第1章引言1.1.2研究的意义移动Ad Hoc网络有着很高的应用价值和重要的研究意义,在军事领域、野外科考、工业等领域都被十分广泛地运用。在军事或紧急情况下保持通信的正常已经成为了一个重要的研究方向,传统的需要基站的通信方式通常不能满足这些条件下的通信需求,因而使用移动Ad Hoe网络进行通信已经越来越引起人们的关注【l-2】。随着人们生活质量的提高,对日常通信也提出了更高的要求,移动Ad Hoe网络通信能更好地满足人们希望随时随地进行通信的需求。而移动Ad Hoc网络路由算法是移动Ad Hoe网络的关键技术之一,因此研究与移动Ad Hoc网络相关的路由算法、提高在无线通信下的网络服务质量具有重要的实际意义。基本蚁群算法也是近年来逐渐兴起的一种新的仿生算法,目前一些复杂的组合优化问题尚未很好地得到解决,而蚁群算法利用其内在的优点能够解决较复杂的组合优化问题,并在求解旅行商问题、车间作业调度问题、图像处理问题等诸多问题中都表现出了较好的性能,并且蚁群算法的某些性能表现还要比传统的遗传算法和模拟退火算法等仿生算法更优。蚁群算法也具有易于与其它算法相结合的优点,蚂蚁个体之间通过不断地信息交流,相互合作,利用蚁群算法的自适应特征,将负载均衡到多条路径,有利于找到更优解,提高网络的可靠性。因此,研究蚁群算法对寻找到高质量的网络路由也具有十分重要的现实意义。本文将蚁群算法与移动Ad Hoe网络中的按需多路径路由算法相结合,以解决单路径路由协议的局限性,按需进行路由发起查找,并且在一次路由发现过程中找到多条可用路由,即“一主一备”式路由,当主路由失效时,备用路由能及时替换主路由,从而尽量减少因路由发现而带来的开销。将蚁群算法应用于Ad Hoc网络能够进一步地提高网络路由算法的性能,从而提高网络的服务质量,降低延时,提高分组的接收率,并且能够使网络的负载均衡、避免较大的路由开销,并且寻找可靠性较高的节点作为下一跳节点,寻找多条较优路径来进行报文的发送。最终提高网络路由算法的性能,进而提高Ad Hoe网络的应用价值。2第1章引言1.2国内外研究现状最早将蚁群算法与有线网络路由相结合的算法是Schoonderwoerd R等人提出的ABC[¨JAnt.Based Contr01算法,在该算法中主要是利用蚂蚁的年龄来当信息素进行路径选择,然后加入噪声机制从而避免选择某一条路径过于单一和集中所带来的负载不均衡特性。由Di Caro和Dorigo M提出Antnet[5】算法是另一种蚁群与路由网络相结合的算法,在AntNet中随机释放到任一目的节点的蚂蚁,根据每个节点路由表中的概率值,选择下一节点。它有前向蚂蚁和后向蚂蚁,前向蚂蚁负责寻路并且存储路径及延时等信息,并加入到自己的栈中,后向蚂蚁负责更新信息素表即到目的节点的概率表,然后发送数据报文的时候根据信息素表来选择路径。AntHocNet[6】算法是一种按需多路径路由算法,在该算法中蚂蚁被发送出去对特定目的节点进行查找,并被转发到其所有的邻居节点。蚂蚁被分成前向蚂蚁和后向蚂蚁,其中前向蚂蚁进行路径的查找,每只前向蚂蚁记录所经过的路径的每一个节点,而后向蚂蚁更新路径的情况,包括所用时间,负载等。ARA[7】算法中也包含了前向蚂蚁和后向蚂蚁,前向蚂蚁负责寻路,并且为了减少控制报文的开销,由数据报文负责路由的维持,为了防止出现路由环路,当中间节点收到重复的数据包时会给该包标记上DUPLICATE ERROR并且重新发回给上一个节点。Ant.AODV[8J是结合了蚁群和AODV的算法,有一定数量的蚂蚁在网络中随机移动并且当蚂蚁到达一个节点后主动地更新它的路由表,这样当源节点需要发送数据时快速地查找到目的节点的路由,可以减少泛洪的次数,加快了数据的发送效率。在国内,朱尚n凋191等提出一种基于AntNet的多路径QoSQuality OfService路由算法,具有带宽和时延QoS约束的新规则进行节点选择,同时考虑了QoS约束和负载平衡问题,每个节点可以维持一张多路径信息的路由表,这样可以得到多路径。浙江大学的吕勇【10】等提出了一种自适应动态路fljADR算法,寻路蚂蚁利用再励学习机制进行信息素表的更新,该算法利用分布式的路由负载平衡算法,减少拥塞现象的出现。王合义【ll】等提出了一种基于蚁群优化的路由算法,利用探索蚂蚁按概率选择公式转移到下一跳邻居节点。该算法有效地利用了蚁群算法的自适应特性,平衡自组网的负载。孙艳歌【12】利用了遗传算法的快速全局搜索能力和蚁群算法的正反馈收敛机制,引入了遗传蚁群算法GAAC,该策略增强了搜索的多样性,避免过早陷入局部最优解,并且可以使收敛速度3第1章引言加快,易于找到全局最优解,算法用于找出满足QoS约束的路径。卢正鼎Il驯等提出了一种基于蚁群算法对动态路由问题,并提出理性的路由选择策略,动态地更新路由表项和节点状态信息,解决网络的负载均衡问题,以提高网络性能。2003年,丁建立【14】等人基于蚂蚁算法的蚂蚁圈模型和MMAS模型构造了自适应蚂蚁算法,通过在找到的最短路径上设置障碍物来模拟网络拥塞,从而找到从源节点到目的节点的多条最优路由序列,从而达到在实际应用中实时自适应地进行动态路由的效果。原萍【l 5】等提出将蚁群算法应用于Ad Hoc网络组播寻路中,可以减少组播问题中目标的延时,解决只能查找单目标这一局限性。冉敏【16】等人提出了一种基于蚁群系统的多约束Qos路由算法,并且用该算法来解决多约束Oos路由问题,通过对信息素的调整,以便能够寻找到满足多约束条件下要求的路径。1.3本文的主要工作本文的主要工作包括一、本文研究了Ad Hoc网络的基本内容,并且深入研究了Ad Hoc网络中的多种路由协议,并且分析了现有路由协议的优点和不足之处。二、深入学习了几种常见的路由协议,如AOMDV,AODV,DSR等。三、深入研究了蚁群算法的工作原理,并且研究了蚁群算法的工作机制。四、对蚁群算法进行改进,用改进后的蚁群算法结合按需路由协议AOMDV协议提出基于蚁群优化的Ad Hoc网络路由算法,在避免网络拥塞、寻找可靠的节点路由和提高网络服务质量等方面对原有算法进行优化。五、深入研究了网络仿真器NS2的工作原理,并且将改进后的新的路由协议IACB.AOMDV用NS2进行仿真实验,从平均端到端时延、分组接收率、路由开销等几个方面和AOMDV算法进行比较,验证了改进后的路由协议的有效性。1.4论文的组织结构本文共分为五章,具体结构如下第一章引言4第1章引言介绍了论文的研究背景以及研究的意义,并广泛阅读国内外相关文献,综述了国内外的研究现状以及本文的主要工作。第二章Ad Hoc网络概述及路由协议研究介绍了Ad Hoc网络的基本概念和原理。对路由协议进行分类,并研究了几种典型的路由协议。第三章蚁群算法的原理介绍了蚁群算法的研究现状,并且深入阐述了基本蚁群算法的原理,介绍了几种常见的蚁群算法。第四章基于蚁群算法的IACB.AOMDV算法对基本蚁群算法进行改进,并将改进后的算法运用到多路径按需路由算法AOMDV之中,优化AOMDV路由算法自适应寻找路由和启发式搜索的性能。第五章IACB.AOMDV算法的仿真和性能分析深入学习了网络仿真器NS2的工作原理,并在NS2中对IACB.AOMDV路由算法进行仿真,从平均端到端时延、分组接收率、路由开销等几个方面详细比较了IACB.AOMDV算法与AOMDV算法,表明IACB.AOMDV路由算法改进后的性能相比提高了。第六章总结与展望对全文的研究工作进行了总结,并对后续的研究进行了展望。5第2章Ad Hoc网络概述及路由协议研究第2章Ad Hoc网络概述及路由协议研究2.1 Ad Hoe网络概述2.1.1 Ad Hoc网络定义Ad Hoc网络的前身是分组无线网Packet Radio Network,PRNET。在1972年,美国DARPADefense Advanced Research Project Agency启动了分组无线网项目。PRNET项目完成之后,DARPA又在1983年启动了高残存性自适应网络SURvivable Adaptive Network,SURAN项目的研究,该项目研究如何将PRNET的成果加以扩展,以支持更大规模的网络,并且开发能够适应战场快速变化环境需要的自适应网络协议。Ad Hoc网络是指由一组带有无线收发装置的移动终端组成的一个多跳的临时性自治系统。网络中的移动终端具有路由和报文转发功能,可以通过无线连接构成任意的网络拓扑。这种网络可以独立工作,也可以接入Internet或蜂窝无线网络,Ad Hoc网络又称为移动Ad Hoc网络Mobile Ad Hoc Network,MANET[11。图2-1典型的Ad Hoc网络图2.1为一个典型的Ad Hoc网络。图中的虚线圆代表一个节点信号的可达范围,每个节点表示一个PDA或者移动电脑等移动设备。若有节点要与其通信6第2章Ad Hoc网络概述及路由协议研究范围以外的节点通信,则需要通过邻居节点,并且只能通过多跳进行通信连接,无法直接进行通信连接。如图2.1中,若节点E要与节点J进行通信,则需要经过节点C,F,H,从而形成ECFHJ的通信线路。2.1.2 Ad Hoe的主要特点Ad Hoc网络具有以下特点1无中心Ad Hoc网络中移动节点的地位均相同,没有严格的控制中心,并且每个节点都充当一个路由器或主机,节点之间通过相互合作来完成报文的发送。2自组织和多跳路由AdHoc网络可以根据数据的传输需要实现快速自动组网,与普通网络中的多跳不同,网络中通信的各个节点协同工作并且不需要基站的支持。由于节点发射功率的限制,节点的覆盖范围是有限的,当要与其覆盖范围之外的节点进行通信时,需要中间节点转发数据报文,即需要经过多跳。3动态网络拓扑Ad Hoc网络中,移动终端可能会以任意的速度和移动模式移动,并且可以随时关闭电台,加上无线发送装置的天线类型多种多样、无线信道间的相互干扰、发送功率的不同、地形和天气等综合因素的影响,移动终端通过无线信道形成的网络拓扑随时可能发生变化,因此形成的网络拓扑结构是动态变化的。4特殊的无线信道特征Ad Hoc网络采用无线传输技术,由于地形或发射功率等因素的影响使得网络中可能会存在单向无线信道。单向无线信道存在时两个节点主机之间只有一个能接收到对方的信号而另一个节点却不能接收到对方的信号。5移动终端的局限性移动终端的优点是携带方便、轻便灵巧,但也存在内存较小、CPU处理能力较低和成本较高等缺陷,并且移动节点一般依靠电池供电,因此如何高效地使用节点的电能以便延长节点的工作时间是一个十分突出的问题。6安全性差Ad Hoc网络是一种特殊的无线移动网络,由于采用无线信道、分布式控制等技术,因而它更容易受到被动窃听、主动入侵、拒绝服务、剥夺“睡眠”等网络攻击【l’17】。7
展开阅读全文
收藏
下载资源

加入会员免费下载





足球比分直播