Adhoc网络广播算法研究毕业论文.doc

学科分类号：_湖南人文科技学院本科生毕业论文论文题目：Ad Hoc网络广播算法研究(英文)：The Research on The Broadcasting Algorithm of Ad Hoc Network学生姓名：学号系 部：计算机科学技术系专业年级：计算机科学与技术 2007级指导教师：论文提交时间：2011-5-13湖南人文科技学院教务处制湖南人文科技学院原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 二O 年 月 日摘 要Ad Hoc网络是当前无线通信领域一种新兴网络技术，它从开始的军事应用正迅速渗透到相关的民用通信领域。Ad Hoc网络是一种自组织的无线多跳网络，其中各个节点可以自由移动，通过共享的无线信道进行通信，无需任何固定的信息基站。各个节点互为中继节点，这样可以与一些不在自身信号覆盖范围的节点进行通信。在这样的移动自组网络中，广播被频繁的用于路由发现、地址解析和许多其他网络服务中。还有在Ad Hoc中，通常两个信息节点通信要经过中间的一个或多个信息点的路由，也就是说这样一个广播可能会被许多节点转发以保证这两个节点的通信。由此可见，一个低效的广播算法会导致产生许多冗余的转发包，所以广播的效率对Ad Hoc的性能有着十分重要的意义。因此拥有高效率的广播算法是无线路由协议研究的关键和前提。本文在研究学习了许多前人提出的广播算法后，主要采取了从网络中节点转发概率着手研究。在网络中节点转发概率的研究中主要实现根据节点间的距离动态调整转发概率。改进以概率为基础的算法，参考转发节点间的距离，针对各种网络结构设置最佳的概率值。动态调整节点转发概率的实现为减少广播风暴对网络影响的目标提供了一种可靠有效的方案。 关键词：Ad Hoc 网络；概率算法广播；网络模拟AbstractAd Hoc network is the current wireless communication domains an emerging network technology，and it started with military applications are rapidly permeate relevant civil communications。Ad Hoc network is a self-organizing wireless multiple hops network which can move freely of each node， through sharing wireless channels for communication without any fixed information base station. Each node，such as relay node with some not own signal coverage to communicate the node。In such a mobile self-organizing networks，radio is frequently used in mute discovery，address analytic and many other network services。And in Ad Hoc，usually two info node communications to pass one or more information points among the routing，that is such a radio may be many nodes to ensure the two nodes forward the communication。Thus，an inefficient broadcasting algorithm can lead to many redundant forwarding bag，so the efficiency of Ad Hoc broadcast the performance is very important meaning。Therefore have a high efficiency of the algorithm is a routing protocols of the premises。this article in the study and learn a lot by the broadcasting algorithm，the main taken from a network node forwards the chance to study。In a network node forwards the probability of research on the implementation of the active node forwards the probability of adjustment。Improvements to the probability of an algorithm, reference node forwards the distance between，for various network topology set the best chance。The active node forwards the probability of the realization of the network broadcast to reduce the impact of the target provides a reliable and effective solution。Key words：Ad Hoc Network；Probability Algorithms Broadcasting；Simulation 目录摘 要IVAbstractV第1章 绪论71.1论文的研究背景和意义71.2 论文的主要工作81.3 论文的结构安排8第2章 Ad Hoc网络概述92.1 Ad Hoc网络的概念92.2 Ad Hoc 网络的历史及发展现状92.3 Ad Hoc 网络技术的应用102.4 Ad Hoc 网络与其他无线网络的比较12第3章 Ad Hoc 网络路由技术163.1 Ad Hoc 网络中的路由协议设计所面临的问题163.2 Ad Hoc路由协议分类163.3 Ad Hoc 网络中典型路由协议19第4章 Ad Hoc 网络广播254.1 Ad Hoc 网络中的广播及其特点254.2 Ad Hoc 网络中广播风暴264.3 现有应对Ad Hoc 网络广播风暴的机制294.4 各种机制的比较34第5章 对概率广播算法机制进行改进365.1提出问题365.2转播概率分析365.3基于距离的动态概率算法38结论43参考文献44致谢45第1章 绪论1.1论文的研究背景和意义在便携式设备的生产技术日趋成熟的今天，轻巧的手持设备(Handhelds ) 还有笔记本计算机(Notebooks )以及个人数字助理(Personal Digital Assistants) PDA等越来越流行，已经到了十分普及的境地。随时随地的进行自由通信的时代已经逐渐形成。无线移动网络技术呈现出空前快速发展的趋势。如今移动通信大多需要的手机(Mobile Phone) 也不再仅仅是一个语音通信的设备，手机上网功能也成为它的一个基本配置。例如手机这种移动通信网络就需要有预先建设好的基础设施(如基站)或接入点的支持才能实现，可是万一这些信息基站或接入点发生故障不能正常工作，或者移动节点(Mobile Node )离开基站的信号覆盖范围，那么这些移动节点就会失去通信能力。基于为了可以在没有固定基础设施的地域进行通信的目的，Ad Hoc网络技术作为一种新的网络技术应运而生。Ad Hoc网络与传统移动网络的一个根本区别就是它不需要有线基础设备的支持，通过移动主机自由的组网实现通信。在Ad Hoc网络中，每个节点不仅有发送接受信息的能力，还都有为数据分组选路由的路由能力，两个节点之间的数据分组是在中间节点的参与下，以跳的方式一跳接一跳的接力方式传送的。正是Ad Hoc网络所具有的这种无可比拟的易部署性和抗毁性，使得它在军事和民用两个领域凸显出了广阔的应用前景和发展空间。在军事领域，它可以用来支持战场的单兵通信、无人侦察、独立战斗队或舰艇编队以及联合作战的通信。在民用领域，它可以用作其他主要通信系统的补盲和灾后地区的通信快速恢复以及区域内无线移动会议等。广播算法的设计是Ad Hoc网络设计中的一个关键环节。要保持数据分组的可达性和网络一致性，然而传统的洪泛算法要求Ad Hoc网络中任意主机对于相同的广播信息都要精确转播一次。这种算法虽然可以简单的技术实现，但这样的结果是会产生大量的冗余转播，还要消耗大量宝贵的网络资源。尽管Ad Hoc网络路由逐步由主动式转变为按需驱动，使得路由信息只需要在必要时才计算出来，降低了额外负担，但是其路由的发现过程仍需要洪泛来实现。在大型规模的网络结构中使用一次洪泛，大量的广播冗余会导致严重的信息冲突和信道争用，致使广播风暴问题产生。因此寻求高效的广播算法对于Ad Hoc网络路由协议设计的优化以及Ad Hoc网络设计都有着十分重要的意义。1.2 论文的主要工作论文的主要任务是，通过学习前人已经提出的广播算法。包括概率型算法、基于计数器算法、基于距离算法、基于位置算法、基于角度算法和基于分簇算法，了解这些算法的基本原理和思想，深刻认识并对它们的优点和缺点比较。以考虑平衡网络中节点能量消耗、延长网络寿命，减少广播延迟和确保广播的可达性等方面为目的对这些算法进行分析。在基于概率型算法上进行改进，它根据Ad Hoc网络中节点间的距离动态的调整转发概率。新算法考虑到在不同网络结构的情况下，广播的最佳转发概率是不一样的，通过计算节点间距离动态调整转发概率，这样既保证了广播的可达性有减少转发广播的数目。1.3 论文的结构安排全文内容如下：第一章：绪论。如上所述，简要介绍了Ad Hoc网络的研究背景和意义，以及论文的主要工作和安排。第二章：Ad Hoc网络概述。这章内容包括Ad Hoc网络的概念和它的发展史及现状，还有Ad Hoc网络技术的应用，最后是Ad Hoc网络技术与其他几种无线网络技术的比较。第三章：Ad Hoc网络中的广播风暴问题。这章主要介绍Ad Hoc网络路由协议，Ad Hoc网络广播分暴的产生以及现有应对广播风暴的机制，还有各种机制的比较分析。第四章：Ad Hoc 网络广播。这章主要介绍Ad Hoc 网络广播风暴分析和现有抑制广播风暴的几种机制介绍、机制的性能比较。第五章：对现有算法的改进。对基于概率型算法的改进。第2章 Ad Hoc网络概述本章主要介绍Ad Hoc网络的基本概念、历史及发展现状，列举了Ad Hoc网络技术的应用，并将其与其他无线网络比较分析。2.1 Ad Hoc网络的概念Ad Hoc一词最初来源于拉丁语，它的意思是“ just for this ”，指特定的、特殊的、为特定问题而设计的解决方法。后来在1991年，IEEE802.11标准委员会采用“Ad Hoc网络”一词来描述这样一种特殊的对等式的无线移动网络。美国计算机协会(ACM)对Ad Hoc网络做了如下定义：” A mobile Ad Hoc network can be defined as a collection of nodes equipped with wireless receivers/transmitters which are free to move about arbitrarily ”。据此我们可以知道Ad Hoc 网络是由一群具有接收和发送信息并能自由移动的节点或路由设备所构成。它是没有有线基础设施所支持的移动自组网络，网络中的所有节点都是移动的主机，每个移动节点互相为彼此充当路由器进行数据的分组转发，从而不依赖任何固定的基础设施的控制。2.2 Ad Hoc 网络的历史及发展现状Ad Hoc网络的前身是分组无线网(Packet Radio Network)。对分组无线网的研究源于军事通信的需要，并已经持续了近20年。早在1972年，美国 DARPA(Defense Advanced Research Project Agency)就启动了分组无线网PRNET(Packet Radio Network)项目，研究分组无线网在战场环境下数据通信中的应用。项目完成之后，DAPRA又在1993年启动了高残存性自适应网络SURAN(Survivable Adaptive Network)项目。研究如何将PRNET的成果加以扩展，以支持更大规模的网络，还要开发能够适应战场快速变化环境下的自适应网络协议。在1994年的时候，DARPA启动了全球移动信息系统(GLOMO, Global Mobile Information Systems)项目。在分组无线网已有成果的基础上对能够满足军事应用需要的、可快速展开、高抗毁性的移动信息系统进行全面深入的研究，并一直持续至今。由于自组网可以广泛的应用于战场通信指挥与控制、警察与医疗部门的抢险救灾、传感器网络、课题教育等众多领域，其有着非常重要的战略意义。90年代中期，随着一些技术的公开，Ad Hoc 网络开始成为移动通信领域一个公开的研究热点。近年来，随着人们对个人通信需求的增长， Ad Hoc 网络的研究也是逐渐升温。90年代以来，移动Ad Hoc 网络的研究在世界范围内方心未艾，已经从无线通信领域中的一个小分支逐渐扩大到相对较独立的研究领域。 2.3 Ad Hoc 网络技术的应用由于Ad Hoc网络灵活性、抗毁性以及其他特殊性，即使是在传统网络系统比较成熟的今天它也存在相当大的应用空间。它适合被用于无法或不便预先铺设网络设施的场合、需快速自动组网的场合等。它的应用主要体现在以下几个方面：1、 军事应用 因Ad Hoc网络特有的无需架设网络设施和可快速展开以及抗毁性强等特点，它已成为军事运用数字人战场通信的首选技术。Ad Hoc网络技术也是美军战术互联网的核心技术。美军的近年来的数字电台和无线互联网控制器等主要通信装备都使用了Ad Hoc网络技术。还有在美国国防高级研究计划局主导的GLOMO计划及其子计划WING中都大量使用了Ad Hoc 网络技术。另外，分级的移动Ad Hoc 网络在未来还将应用在耗资40亿美元的“联合战术通信系统(JTRS)”中，该系统将未来战士、载人战车和机器人打造成一个密不可分的整体系统，把战场上的信息迅速传给每一个作战单元。根据Frost Sullivan公司05年6月发布的名为美国战士军用通信市场的研究报告中，美国战士军用通信市场2011年的销售总额将从05年的49亿美元提升至约57亿美元。预测国际(Forecast International)在03年的一份研究上表明，世界各国的国防部门计划将在未来十年的时间里投入约为111亿美元主要用于57种地面通信系统的开发、采购和维护。因此在以移动为主军事通信中， Ad Hoc 网络技术必将在军事通信领域大有作为。2、 紧急和临时场合应用 紧急和临时场合的应用主要是指在遭受了地震、水灾、强热带风暴等其他灾害的打击后，原有的固定的通信系统基础设施可能被摧毁或不能正常工作。这时对于抢险救灾来说就需要Ad Hoc 网络，这种不需要任何固定网络基础设施的预设又能迅速布设的自组织网络技术，来实现在抢险救灾过程中的重要信息的通信。其他类似的情况，如在处于边远或偏僻野外地区是，同样无法依赖固定或预设的网络设施进行通信。Ad Hoc 网络技术的独立组织网络能力和自组织等特点，是这些场合通信的最佳选择。3、 个人通信应用 家庭或个人局域网(PAN, Personal Area Network)是Ad Hoc网络技术的又一应用领域。它不仅可以用于实现PDA、手机、笔记本电脑等个人电子通信设备之间的移动通信，还可以用于个人局域网之间的多跳通信。蓝牙技术中的超网(Scatter net)就是一个典型的例子。4、 传感器网络应用 Ad Hoc 网络技术也应用于如今比较流行的传感器网络(WSN)。03年2月的美国的技术评论杂志Technology Review评出对人类未来生活影响深远的十大新兴技术，传感器网络名列第一。传感器网络可被广泛的应用于国防军事、医疗卫生、交通管理、制造业、抗险救灾、环境监测等领域，它的应用价值非凡。例如，Digital Sun公司就利用传感器网络技术发展了自动洒水系统。科学家们各个地方利用传感器网络开展生物监测项目研究。美国航空航天局还曾构想通过传感器网络检测来监视外星球表面状况，为人类得登陆做好准备，这些传感器网络节点通过火箭或者探路者进行散播。由于无线传感器所具有的广阔的市场前景，美国国防部远景计划研究局已经投资几千万美元，来帮助大学进行“智能尘埃”传感器技术的研究。如今WSN产业已经拥有基本的政策环境，得到各国政府的政策支持，也出现有大量的市场推动者。WSN的产业链由此已经基本成型，出现了一大批系统集成商、组件供应商、软件授权商和解决方案提供商，他们正在推动WSN产业从研发阶段向市场推广阶段转移。总而言之，WSN技术正在逐步成熟随着其研究的不断深入，相信其应用范围会越来越广。5、 与移动通信系统的结合 Ad Hoc网络还可以作为传统网络的一个补充与传统的移动通信系统相结合，利用移动主机的多跳转发能力扩大传统移动通信系统的覆盖面积、平衡相邻小区的业务、提高小区边缘的数据通信速率等。 在实际应用中，Ad Hoc网络不仅可单独组网实现局部的通信外，还可作为末端子网通过接入点连进其他的固定网络或移动通信网络，与Ad Hoc网络以外的其他网络的主机进行通信。因此，Ad Hoc网络也可为各种通信网络提供无线接入的功能。6、 无线网格网 无线网网格(WM ,Wireless Mesh)是Ad Hoc技术的简化版本，Ad Hoc网络仍然处于研究阶段，而WM网络已经取得了初步应用。这种技术比起传统的点对多模式来说具有诸如节能和易扩容等多优势，很多公司开始把WM技术应用于宽带网络接入，而且相关的无线路由器等产品也已经开始商用。如诺基亚公司推出的无线路由器就可以安装在屋顶上，至此可形成没有基站的网络，该产品目前已成功获得全球超过50多家运营商青睐，他们将借此建立起以用户为基础的高速无线网络。日本某市已成熟使用WM连接了13个小学、4个中学和18个市政建筑。美国的Sky Pilot公司表示将智能天线技术应用于WM网络，可使频谱再度利用。将来，Wireless Mesh在各方面领域的应用更是无可限量。2.4 Ad Hoc 网络与其他无线网络的比较1、 蜂窝系统蜂窝系统可以提供广阔的信号覆盖范围，并支持无线语音双通信，还可以较好的管理用户移动性。蜂窝系统的发展可以根据应用技术大致划分为三代。第一代是以FDMA1(Frequency Division Multiple Access)技术为标志的模拟蜂窝系统以及模拟无绳电话系统，我们称之为1G。如美国的AMPS系统。这种系统的主要缺点就是频谱利用率低，信令干扰话音业务质量。在模拟蜂窝系统中，语音按电路交换的形式在窄带宽信道上以频率调制的方式进行传输，系统对每个单元的控制放在了移动支持中心MSS(Mobile Support Station)或者基站BS(Base Station)上，MSS和基站作为固定网的一部分通过无线方式连接移动用户。第二代是以TDMA(Time Division Multiple Access)和CDMA(Code Division Multiple Access)技术为标志的数字蜂窝系统，即2G网络。如GSM(Global System For Mobile Communication)，和以DECT、PACS、CT2为代表的数字无绳电话系统。数字蜂窝系统在一定程度上提高了系统容量，但越区切换性能仍不完善，而且具有较高的误码率和较低的有效数据传输速率。国际电联在1985年提出了第三代(3G)蜂窝系统的概念FPLMTS(Future Public Land Mobile Telecommunications System)，在1999年改为IMT-2000(International Mobile Telecommunications-2000)标准。与前两代相比，第三代蜂窝系统的主要特征是可以提供更丰富多彩的移动多媒体业务，其传输速率在高速移动环境下支持144Kbps的传输速率，在步行慢速移动环境下支持384Kbps的信息传输，静止状态下更是高达2Mbps的速率，其设计目标就是为了提供比第二代系统拥有更大的系统容量、更好的通信质量、在全球范围内更好的实现无缝漫游、为用户提供包括话音、数据及多媒体等在内的多种业务，同时要与已有第二代系统的良好兼容性的新型移动通信系统。目前ITU接受的3G标准主要有以下三种：WCDMA，CDMA2000与TD-SCDMA。与Ad Hoc 网络相比较，蜂窝系统具有覆盖范围更广泛，通信的Q o S更有保障，更适合作为人口常住区的公共通信系统的优势。但蜂窝系统需要事先将覆盖区域划分为小区设立基站等基础设施的支持，组网受到地形限制，配置管理较为复杂。并适合山地、海洋、极地、战地等地域环境的通信。2、 无线局域网无线局域网WLAN(Wireless Local Area Network)是采用无线传输多媒体的计算机局域网10。它是由无线网卡、无线接入点AP(Access Point)、主机和有关设备所构成。无线局域网自身具有无需物理布线、可移动性强、组网灵活快捷、传输速度高、信号比较稳定等优点，通过布设足够的AP可覆盖一部分区域，用户可以在这些AP间实现无缝漫游。无线局域网第一个版本发表于1997年，其中定义了MAC(Media Access Control)层和物理层。物理层定义了工作在2.4GHz的ISM(Industrial，Scientific and Medical )频段上两种无线调频方式和一种红外传输方式，总数据传输速率设计为2Mbps。两个设备之间的通信可以通过自由连接的方式进行通信。也可以在基站的协调下进行。1999年WLAN添加上了两个补充的版本802.11a和802.11b。802.11a定义了一个在5GHz ISM频段上数据传输速率可达54Mbpse的物理层。802.11b定义了一个在2.4GHz ISM频段上数据传输速率可达到11Mbps的物理层，它们在性能、价格等各方面均超过Bluetooth蓝牙、HomeRF等技术，加之2.4GHz ISM频段为世界上绝大多数国家通用，使802.11b得到迄今为止最为广泛的应用。苹果公司把自己开发的802.11标准叫做Airport。1999年工业界成立了Wi-Fi联盟，致力解决符合802.11标准的产品生产和设备兼容性问题。由于有布设的无线局域网接入点的支持，现在在宾馆、机场、餐厅、书店、学校、医院等场所随时随地可以享受无线网络服务，WLAN可以看作是有线网络在无线领域的扩充。相比之下同时无线网络的，Ad Hoc 网络在应用程度上远不及WLAN技术的成熟。 3、 集群无线通信系统集群无线通信系统中多个用户可共用一组无线电信道，动态分配使用这些信道的专用移动通信系统，是一种最主要的专用移动通信系统。目前最新一代的数字集群系统的代表是爱立信公司的DACS系统，摩托罗拉公司的MIRS系统。它们的主要特点是相同频率、共用设施、共享覆盖区、共享通信业务等。因为是专用通信网络，它们的使用规模一般不大，多用于团体、部门的指挥调度通信。4、 对讲机系统对讲机系统是最简单的移动通信。在有限的无线传输距离内，通过使用相同电波频率，来实现互通话。对讲机系统主要用于语音通讯，是目前军队、公安部门普遍的通信手段。对讲机系统与移动自组网的最大区别在于对讲机不支持通信中继，因而受无线传输范围的限制。如果要扩大通信覆盖范围，就必须增大对讲机的无线传输距离，因而必须增加信号发射功率，这就不利于提高通讯设备的便携性。另一方面，扩大无线覆盖范围也会使得频率的空分复用率降低，使得本系统的容量和可用通信带宽下降。对讲机系统可视为仅支持语音通讯的简单单跳移动自组网，其使用的覆盖范围和数据传输速率都有非常有限。5、 卫星系统卫星系统主要有两类。同步轨道卫星系统是第一类，应用的有Inmarsat-B、Inmarsat-M、澳大利亚的MOBILE-SAT、北美的MSAT、Jet Propulsion Lab的PASS、欧洲的Olympus、美国的ACTS、日本的EST-VI卫星系统等。因为同步轨道高，传输路径长，信号时延和衰减都非常大，所以同步轨道卫星系统多用于船舶、飞机、车辆等大型的移动体。很少有个人业务的应用，事实上，同步轨道系统实现个人通信存在巨大的困难，其中最难的解决问题就是个人终端对卫星性能的要求太大。第二类卫星系统就是中低轨道的移动卫星系统。其具有代表性的是Motorola公司提出的IRDIUM系统和Loral公司于Qualcomm公司共同倡导发起的GLOBSLSTAR系统。IRDIUM系统有星际电路，具有星上处理和交换功能，覆盖全球范围，不仅可以提供电话业务，还可以提供传真、全球定位、无线定位以及全球寻呼业务。可是由于其个人终端价格和通信费用过高，IRDIUM公司已经于1999年申请破产保护，并与2000年终止业务。GLOBSLSTAR系统相对设计简单，没有星际电路和星上处理和交换功能，仅作为地面蜂窝系统的延伸，技术风险小，手机和通信费用现对低。但是该系统只可覆盖地球南北纬70度之间的范围，且地面多达150-200个，而且在战争和自然灾害时，其性能远不及只有12个地面站的IRISIUM系统安全。卫星通信的优点有：通信范围大，只要卫星发射的波束覆盖的范围均可进行通信，不易受陆地灾害影响，建设速度快，易于实现广播和多地址通信，电话和话务量可灵活调整，同一信道可用于不同方向和不同区域。缺点有：卫星信号到达有较大的延时，10GHz以上频带受降雨雪的影响大，卫星天线受太阳、噪声影响。6、 其他媒介通信系统无线通信的媒介除了电磁波外，还有红外线、激光等。红外通信时利用红外技术实现两点间的近距离保密通信和信息转发，它一般有红外发射和接受系统两部分组成。发射系统在对一个红外辐射源进行调制后发射红外信号，而接收系统用光学装置和红外探测器进行接收。红外通信工作波长为860nmp-920nm，工作频率高达3x1014Hz。其特点是：单色性强、小立体角内传播、保密性强、无干扰、信息容量大、结果简单，既可以在室内使用，也可以在野外使用。由于它具有良好的方向性，适用于国防边哨之间的报名通信。但在野外使用时它易受气候影响，红外射束易被尘埃、雨水等物质吸收。激光大气通信系统所用光源多为二氧化碳气体激光器、YAG固体激光器、He-Ne气体激光器等。其特点是：不挤占宝贵的无线电频率资源、电磁兼容性好、抗电磁干扰强、保密性好。激光大气通信系统在空间星际通信应用中潜力巨大，但是仍然存在受大气湍流干扰，有效通信距离短，带宽受限，适合全天候、高机动性和稳定可靠的光器件制作问题。第3章 Ad Hoc 网络路由技术虽然Ad Hoc网络路由算法不是本文的研究重点，但是作为Ad Hoc网络的一个重要内容，这里不得不提。同时Ad Hoc网络路由算法的问题是于自组移动网络广播算法内容是有重要联系的，因此本章节将详细介绍Ad Hoc网络路由技术的相关内容。本章首先介绍Ad Hoc 网络路由协议设计目标及其所面临的问题，之后介绍Ad Hoc网络路由协议的分类并对其中几种典型的路由协议进行介绍，最后对这几种路由协议进行定性比较。3.1 Ad Hoc 网络中的路由协议设计所面临的问题我们知道在自组织网络中，当节点移动时不再有固定基础设施或接入点来帮助其实现路由分组。网络中不再有缺省的路由，网络中的每个移动主机都要求具有独立查寻路由并转发数据分组的能力。对于自组网络需要为其专门设计研究新的路由协议算法。而设计满足Ad hoc网络环境下的路由协议所面临的困难主要有以下几点: (1)频繁变化的网络拓扑结构。这些变化主要体现在节点加入，离开网络和链路权值系数的变化以及节点的不断移动。当拓扑结构发生变化后，常规路由协议需要很长时间和较大的代价才能到达收敛状态。 (2)有限的带宽资源。Ad Hoc网络自身的传输媒介是依靠开放性的无线电波，网络本身提供的带宽有限以及信号之间的冲突和干扰，使移动节点可得到的有限的传输带宽远远小于理论上的最大带宽。 (3)单向的无线信道。由于无线收/发设备不同或周围环境对无线信道的影响，可能会造成单向的无线传输信道。 (4)受限的计算和存储能力以及受限的能源。这就要求路由协议尽可能简单，因而增加了路由协议的设计难度。3.2 Ad Hoc路由协议分类根据Ad Hoc 无线网络路由协议的特殊性，近年来提出了多种Ad Hoc 网络路由协议。IETF的MANET工作小组目前正专注于Ad Hoc 网络路由协议的研究提出了许多协议草案，如 TBRPF、OLSR、DSR等。根据这些路由协议的触发原理，大致可以分为主动式也叫表驱动式(Table Driven)路由协议、被动式也叫按需驱动(On Demand Driven)路由协议和混合式(Hybrid)路由协议三种。如图3.1所示。Ad Hoc网络路由协议主动路由协议被动路由协议混合路由协议DSDVOLSRZRPWRPDSRAODVTORA图3.1 Ad Hoc 网络路由协议分类3.2.1 主动路由协议主动式路由协议又称表驱动路由协议，每个节点维护一张包含到达网络中所有节点的路由信息的路由表，并根据网络拓扑的变化随时更新路由表，所以路由表可以准确地反映网络的拓扑结构。源节点一旦要发送报文，可以立即获得到达目的节点的路由，这类的路由协议通常是通过修改现有的有线路由协议来适应Ad hoc无线网络要求，如通过修改路由信息协议(RIP )得到目的节点序列距离矢量协议(DSDV)。因此这种路由协议的时延较小，但是协议需要大量的路由控制报文路由，协议的开销较大。特别是在网络规模比较大的情况下网络结构越加频繁，这样每个节点都要维护一张路由表就没什么意义，而且资源的浪费也是越加严重。常用的先验式路由协议有DSDV, LSR, WRP等。3.2.2 被动路由协议 被动式路由协议又称按需路由协议，是一种当有数据需要发送时才查找路由的路由选择方式。节点不需要维护及时准确的路由信息，当需要发送数据时才发起路由发现过程。与主动式路由协议相比，被动式路由协议的开销小，但是数据报传送的时延较大，不适合实时性的通信场合。另外，被动式路由协议在进行路由发现时普遍采用广播方式，这会导致许多控制信息重复地被传送，进而产生冗余、碰撞和竞争。常见的被动式路由协议有AODV, DSR, TORA。3.2.3 混合路由协议混合路由协议，Ad hoc无线网络中单纯采用主动式或被动式路由协议都不能完全解决路由问题，因此，许多学者提出了结合主动式和被动式路由协议优点的混合式路由协议，这种主动被动混合式的路由能使在网络一端新链路的产生对于本地是重大事件，而对另一端影响很小。也就是说，关于邻居的信息比遥远的目的地节点的信息更重要。每个节点必须记录区域半径内所有节点的信息。但是，实施混合式路由也面临着很多困难，如簇的选择和维护、主动式和被动式路由协议的合理选择以及网络工作的大流量等问题。典型的混合协议如ZRP协议。下面简单对比一下各类路由协议的优缺点，如表所示：表3.1 各类路由协议比较主动路由协议被动路由协议混合路由协议控制开销高移动越大开销越大中等是否要周期更新是否是路由时延小大一般可扩展性弱一般强耗电量高低中等拓扑变化适应性弱强一般带宽开销高低中等路由结构大多数是平面平面结构分级结构路由信息可靠性一直有效需要时有效部分一直有效，部分需要时有效由上表我们可以知道的是，主动路由协议在移动自主网络结构比较简单、规模较小的情况下有较好的性能，被动路由协议比表路由协议更适应网络的动态变化结构，而混合路由协议则是前两种路由协议各个性能的折中体现。3.3 Ad Hoc 网络中典型路由协议目前Ad Hoc 网络路由逐步由表驱动协议向按需路由协议以及混合路由协议转变，这样路由信息只在需要时才会计算出来，降低了额外负担，但是其路由发现过程通常任然运用洪泛实现。盲目的洪泛会导致严重的广播信息冗余，信道争抢和广播信号碰撞，从而就会产生后面将要提到的广播风暴问题。接下来就介绍几种流行的Ad Hoc路由协议。3.3.1 DSDV路由协议DSDV (Destination-Sequenced Distance-Vector Routing)路由协议是基于经典Bellman-Ford路由选择过程的改进型路由表算法。DSDV以路由信息协议为基础。它仅适用于双向链路，是Ad Hoc 路由协议发展比较早的一种。依据DSDV，网络中的每一个节点都保存有一个记录所有目的节点和到目的节点条数的路由表。表中的每一个条目都有一个由目的节点注明的序列号(Sequence Number)，序列号能帮助节点区分有效和过去的路由信息。标有更大序列号的路由信息总是被接受。如果两个更新分组有相同的序列号，则选择跳数最小的，以路由最优(最短)。路由表更新分组在全网内周期性的广播而使路由表保持连贯性。3.3.2 OLSR路由协议OLSG(Optimized Link State Routing)路由协议是由IETF MANET 工作组提出作为RFC标准化的一种基于多点中继(Multipoint Relays，MPR)概念的链路状态协议。它是从IPANEMA和PRIMA计划所发展出来的，协议中节点周期性的交换包括Hello分组和TC(Topology Control)分组在内的各种控制分组，进行分布式计算来建立网络拓扑。通过向邻居广播Hello消息和对收到的Hello消息的处理，完成链路和邻居侦测。在掌握链路和邻居信息的情况下，节点在自己邻居节点中选择一部分作为自己的MPR，节点自己则成为MS(MPR Selector)。在OLSR中MPR负责周期性的向网络散布TC分组、参与路由计算：而其他非