基于蚁群算法的+Ad+Hoc+网络+QoS+组播路由研究5814.pdf

《基于蚁群算法的+Ad+Hoc+网络+QoS+组播路由研究5814.pdf》由会员分享，可在线阅读，更多相关《基于蚁群算法的+Ad+Hoc+网络+QoS+组播路由研究5814.pdf（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、分类号：_ 密 级：_：_ 单位代码：_ 硕士学位论文 论文题目：基于蚁群算法的 Ad Hoc 网络 QoS 组播路由研究 学 号：_ 作 者：_ 专 业 名 称：_ 2011 年 06 月 17 日 李浩磊 公开 1 0 1 2 7 计算机应用技术 200802053 TP393 内蒙古科技大学硕士学位论文 论文题目：作者：_ 指 导 教 师：单位：协助指导教师：单位：单位：论文提交日期：2011 年 06 月 17 日 学位授予单位：内 蒙 古 科 技 大 学 谭跃生 教授 内蒙古科技大学 基于蚁群算法的 Ad Hoc 网络 QoS 组播路由研究 李浩磊 基于蚁群算法的 Ad Hoc 网络

2、 QoS 组播路由研究 Research on Ad Hoc Network QOS Multicast Routing Based on Ant Colony Algorithm 研 究 生 姓 名：李浩磊 指导教师姓名：谭跃生 内蒙古科技大学信息工程 学院 包头 014010，中国 Candidate：LiHao-lei Supervisor：TanYue-sheng School of InformationEngineering Inner Mongolia University of Science and Technology Baotou 014010，P.R.CHINA 独 创

3、 性 说 明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得内蒙古科技大学或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。签名：_ 日期：_ 关于论文使用授权的说明 本人完全了解内蒙古科技大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。（保密的论文在解密后应遵循此规定）签名

4、：_ 导师签名：_ 日期：_ 内蒙古科技大学硕士学位论文 I 摘 要 移动 Ad Hoc 网络（MANET）具有独立组建网络、无中心以及网络拓扑结构动态变化、带宽和能源受限等特点。作为一种特殊形式的移动计算机网络，可广泛应用于战场指挥、临时会议、灾难救助及其它各种军事和民用领域，有着广阔的应用前景1。多媒体业务的引入对于 Ad Hoc 网络提出了 QoS 组播路由的需求。QoS 组播是在满足带宽、延迟、丢包率等多个 QoS 约束条件下进行的组播 2。现有Ad Hoc 网络QoS 组播路由协议多为确定性路由，对网络拓扑结构的动态变化适应性差。如何在移动自组织网络中实现有效的组播和 QoS 保障是

5、一项十分困难和具有挑战性的工作。蚁群算法是一种从自然界中的社会性昆虫的特性受到启发，发展而来的一种智能搜索算法。由于分布式的计算、单个智能体实现简单、支持多路径的特性，蚁群算法很适合用于Ad Hoc 网络路由3。本文首先对移动 Ad Hoc 网络进行了分析，研究了移动 Ad Hoc 网络的特点、发展趋势及多播必要性，分析了目前提出的几种多播路由协议，在深入研究蚁群算法的基础上，根据移动 Ad Hoc 网络的特性，对蚁群算法做了有益的改进，并将改进后的蚁群算法应用在 Ad Hoc 网络 QoS 组播路由的建立和维护过程中，提出了一种基于蚁群算法的 Ad Hoc 网络 QoS 组播路由协议。NS-

6、2 仿真结果证明，该协议能依链路质量有效选择路径，创建和维护组播树，达到低时延、平衡流量的目的。同时通过对蚂蚁收集到的网络信息对概率路由表进行调整，使路由选择实现分布式全局优化，有效地缓解了 Ad Hoc 网络的拥塞问题和路由开销过大等问题。关键词：Ad Hoc 网络；服务质量；组播路由；蚁群算法 内蒙古科技大学硕士学位论文 II Abstract Mobile Ad Hoc network(MANET)has the characteristics of Construction of the independent network,decentralization,dynamic chan

7、ges in network topology,limited bandwidth and energy,etc.Ad Hoc networks,as a special form of mobile computer networks,will have been widely used in the future,which can be deployed in battle field,temporary meeting,disaster rescue and other civil or military environments.The introduction of multime

8、dia services proposed QoS multicast routing needs for Ad Hoc network.The QoS multicast is the special multicast which should guarantee some QoS constrains such as bandwidth,delay and packet loss rate,et.Most of existent Ad Hoc network QoS multicast routing protocols use determinate routing,which has

9、 poor adaptability to dynamic changes of network topology.More require that the multicasting routing in Ad Hoc networks to support QoS,which is challenging.Ant colony algorithm is a kind of intelligence heuristic approach that inspired from social insects in nature.Ant colony algorithms support dist

10、ributed computing and multi-path,the agents are also easy to implement.So ant colony algorithms just meet the need of mobile Ad Hoc network routing.This paper first analyses the mobile Ad Hoc network,research the characteristics,trends of the mobile Ad Hoc network and multicast necessity of the pres

11、ent several multicast routing protocols,through deep research of the basic ant algorithm,according to the nature of Ad Hoc network.The improved ant colony algorithm is applied in the establishment and maintenance of network multicast routing process.A new Ad Hoc network QoS multicast routing protoco

12、l based on ant colony algorithm is proposed in this paper.NS-2 Simulation results show that the protocol can effectively choose the path according to link quality,create and maintain the multicast tree,thus achieving the aims of low latency、balanced flow At the same time,the algorithm adaptively adj

13、usts the probability routing table by using the networks information of the ants collected and achieves globally optimizing,it provides a new method to improve the congestion problem and heavy overheads problem.Key words:Ad Hoc network;QoS;multicast routing;ant colony algorithm 内蒙古科技大学硕士学位论文 -1-目 录

14、摘 要.I Abstract.II 引 言.-1-1 绪论.-2-1.1 课题的研究背景及意义.-2-1.1.1 课题的研究背景.-2-1.1.2 论文选题的目的及意义.-3-1.2 国内外研究现状.-4-1.3 论文研究的内容.-4-1.4 本论文实现的功能.-4-1.5 论文的结构安排.-5-2 移动Ad Hoc 网络及组播路由技术.-7-2.1 移动Ad Hoc 网络概述.-7-2.1.1 移动 Ad Hoc 网络的定义.-7-2.1.2 移动 Ad Hoc 网络的体系结构.-7-2.1.3 移动 Ad Hoc 网络的协议栈结构.-8-2.1.4 移动 Ad Hoc 网络的特点.-9-2

15、.2 移动Ad Hoc 网络组播路由技术.-10-2.2.1 组播的概念.-10-2.2.2 移动 Ad Hoc 网络组播路由的设计要求.-10-2.2.3 典型的移动 Ad Hoc 网络组播路由协议分析.-10-2.2.4 典型协议的分析总结.-12-3 移动Ad Hoc 网络的QoS 保障及QoS 路由.-13-3.1 移动Ad Hoc 网络的QoS 保障.-13-3.1.1 移动 Ad Hoc 网络中支持 QoS 面临的挑战.-13-3.1.2 移动 Ad Hoc 网络QoS 体系结构.-14-3.2 移动Ad Hoc 网络的QoS 路由.-14-3.2.1 移动 Ad Hoc 网络的Q

16、oS 路由概述.-14-3.2.2 移动 Ad Hoc 网络中实施 QoS 路由的策略.-15-内蒙古科技大学硕士学位论文 -2-3.2.3 移动 Ad Hoc 网络的典型 QoS 路由协议.-15-4 蚂蚁算法及其改进.-17-4.1 蚁群算法简介.-17-4.2 蚁群算法的基本原理.-17-4.3 蚁群算法应用于移动 Ad Hoc 网络的优势.-18-4.4 蚁群算法的应用改进.-18-4.4.1 蚁群算法的改进方案.-18-4.4.2 改进后的蚁群算法.-19-5 基于蚁群算法的 Ad Hoc 网络 QoS 组播路由协议.-21-5.1 ABQMRA 的基本思想.-21-5.2 数据结构

17、.-21-5.2.1 节点维护的数据结构.-21-5.2.2 网络中的控制报文.-22-5.3 ABQMRA 的工作机制.-23-5.3.1 组播路由发现过程.-23-5.3.2 组播路由维护过程.-25-5.3.3 组播数据发送过程.-25-6 仿真试验及性能分析.-26-6.1 NS2 网络仿真.-26-6.1.1 NS2 仿真原理.-26-6.1.2 NS2 中的无线网络.-26-6.1.3 NS2 中仿真实验的方法和步骤.-28-6.2 性能参数.-28-6.3 仿真环境.-29-6.4 仿真结果分析.-29-结 论.-32-参 考 文 献.-33-在学研究成果.-37-致 谢.-38

18、-内蒙古科技大学硕士学位论文 -1-引 言 最近几年，移动 Ad Hoc 网络迅速成为计算机界关注的热门话题之一，Ad Hoc 网络以其组网快速、灵活的特点在军用和民用领域有着广阔的应用和发展前景。组播(Multicast)是一种面向群组的数据传播方式，当网络中有多台主机需要同时接收同一数据报文时，出于对网络带宽及发送端负载等诸多因素的考虑，组播成为了一种最佳解决方案。近年来随着多媒体应用的普及和 Ad Hoc 网络在军用及民用领域的应用不断扩大，Ad Hoc 网络对 QoS 的支持显得越来越重要。但是在 Ad Hoc 网络中，由于网络拓扑变化频繁导致获取和维护节点间的链路状态信息比较困难，网

19、络节点随机移动、内存和主机能源受限制等都会使在移动 Ad Hoc 网络中提供 QoS 路由比较困难，特别是当网络规模较大时，这些问题更为复杂。因此 Ad Hoc 网络中的 QoS 保障将面临许多不同于传统网络的新问题和新挑战。蚁群算法是由 M.Dorigo 等学者在真实蚂蚁觅食行为的启发下提出的一种具有高度创新性的元启发式算法。蚂蚁在它所经过的路径上留下一种挥发性分泌物称为信息素(Pheromone)。蚂蚁能够感知信息素的强弱，并倾向于选择信息素强度高的路径。信息素强度高的路径又会吸引更多的蚂蚁，从而形成一种正反馈机制。蚂蚁个体之间通过感知信息素的强度实现间接交流最终达到发现蚁穴与食物之间的最

20、优路径。近年来，研究人员已经提出了一些用于解决多约束 QoS 组播路由问题的算法。国内外许多学者利用蚁群算法、遗传算法等启发式智能算法来解决多约束 QoS 组播路由问题，并且取得了一定的成果。各算法都有各自的优缺点及适用的网络环境，其中蚁群优化算法以其健壮性、并行性、灵活性、分布式智能优化等特点，得到了广泛应用。本文主要对蚁群算法在移动 Ad Hoc 网络 QoS 组播路由领域的应用进行了深入研究,针对移动Ad Hoc 网络的特点,利用新的蚂蚁行动规则和信息素更新方案,有效地改善了收敛性和避免了过早的局部收敛;根据改进后的蚁群算法提出了一种基于蚁群算法的 Ad Hoc 网络QoS 组播路由算法

21、.并在 NS-2 仿真平台上进行了仿真实现和性能分析。内蒙古科技大学硕士学位论文 -2-1绪论 1.1 课题的研究背景及意义 1.1.1 课题的研究背景 随着信息科技的迅猛发展，人们已不再满足于传统的语音通信服务。更多的提供多媒体应用的通信服务进入到人们的生活。第三代移动通信系统、移动 IP、无线 WIFI 技术、无线 WIMAX 技术等就是很好的例子，这些移动通讯技术使人们的沟通变得更加方便快捷 4。传统意义的移动通信技术一般要基于预先架设的网络基础设施才能够运行5,6。但对于某些组网方式有特殊要求的场合，比如，军事无线通讯网络的快速构建，灾后营救，野外科考等，这些场合要求组网简单、速度快，

22、抗毁性强，传统的蜂窝移动通信系统显得力不从心。移动 Ad Hoc 网络以其组网快速、灵活等特点能够很好地满足这些特殊场合的需求，有着广阔的应用和发展前景7。移动 Ad Hoc 网络由一组带有无线通信收发装置的移动终端节点组成，网络中每个终端可以收发数据并可自由移动、地位相等。它是一个临时、多跳、无中心网络，不需要现有基础网络设施的支持，可以在任何时候、任何地点快速组建8。组播(Multicast)是一种面向群组的数据传播方式，当网络中有多台主机需要同时接收同一数据报文时，出于对网络带宽及发送端负载等诸多因素的考虑，组播成为了一种最佳解决方案。当网络中有一台以上的主机需要同时接收相同数据报文时，

23、如果采用单播对数据进行转发，那么源端主机必须完成相同的报文的复制。在源主机要复制产生多个相同的数据报文，之后再逐一将多个数据报单播到目的端，对于一些延迟敏感度较高的数据，这将是无法容忍的。其次，发送端主机要完成大量同一数据报文的复制，这对于发送端主机是一个非常大的开销。如果采用组播技术，源主机只需要发送一个报文，由组播成员节点完成报文的复制转发就可以使每个组播接收节点收到源主机发送的报文。QoS 技术的核心是为网络上不同的应用需求提供不同的服务质量。近年来随着多媒体应用的普及和 Ad Hoc 网络在军用及民用领域的应用不断扩大，Ad Hoc 网络对 QoS的支持显得越来越重要。但是在 Ad H

24、oc 网络中，由于网络拓扑变化频繁导致获取和维护节点间的链路状态信息比较困难，网络节点随机移动、内存和主机能源受限制等都会使在移动Ad Hoc 网络中提供QoS 路由比较困难，特别是当网络规模较大时，这些问题内蒙古科技大学硕士学位论文 -3-更为复杂。因此 Ad Hoc 网络中的 QoS 保障将面临许多不同于传统网络的新问题和新挑战。由于移动 Ad Hoc 网络动态多变的特性，使得传统 Internet 中采用的综合业务模型和区分服务模型等等在 Ad Hoc 网络中不再适用。在移动 Ad Hoc 网络中，节点的移动及周围环境的变化对链路的状态影响较大，尤其是在大规模的网络中，带宽、时延、时延抖

25、动等链路参数很难及时获取和更新维护。组播路由算法对移动 Ad Hoc 网络组播应用的 QoS 保障起到了至关重要的作用。在以往的研究中，多个 QoS 参数的组播路由问题已经被证明是一个 NP 完全问题，当网络规模扩大时，组播路由问题将更为复杂。随着人们对网络服务质量要求的不断提高，研究新的基于多约束的 QoS 组播路由算法，具有十分重要的意义9。蚁群算法10,11是由 M.Dorigo 等学者在真实蚂蚁觅食行为的启发下提出的一种具有高度创新性的元启发式算法。蚂蚁在它所经过的路径上留下一种挥发性分泌物称为信息素(Pheromone)。在网络寻路的过程中，人工蚂蚁通过感知信息素的强弱实现间接通信以

26、及时准确地了解网络拓扑结构的变化，算法采用分布式控制方式，能够以较快的速度收敛于最优路径。基于蚁群算法在网络路由领域的优良表现，越来越多的人开始研究网络路由方面的蚁群算法应用12。本课题在深入研究蚁群算法的基础上，将改进后的蚁群算法应用于 Ad Hoc 网络QoS 组播路由的建立和维护过程中，就 Ad Hoc 网络中的 QoS 组播作进一步研究。1.1.2 论文选题的目的及意义 移动 Ad Hoc 网络13是指一组具有无线收发功能的移动节点组成的一个多跳的临时性的自治系统。移动 Ad Hoc 网络没有进行路径选择的设备，网络中的节点既是数据的发送端、接收端，同时也是转发数据包的路由器。它无需任

27、何固定接入点，信息数据的传播全部通过无线网络各移动节点之间接力的方式来实现。通常移动 Ad Hoc 网络应用于无线访问接入点难以建立或者无线访问接入点建造开销较高的场合。例如在战场上由于敌方对通讯设施的打击导致盟军之间的通信很难借助于固定访问接入点来实现。随着无线通讯技术的突飞猛进，特别是人们对个人通信提出更加多样化的需求，人们希望通过快速组网的方式进行移动通讯的愿望变得更加迫切。在移动 Ad Hoc 网络中，链路能够提供的带宽有限，节点的频繁移动将使链路状态信息很难及时获取，无线信道自身的特性等诸多因素使得移动 Ad Hoc 网络面临比有线网更大的QoS 难题14。本文主要对蚁群算法在移动

28、Ad Hoc 网络 QoS 组播路由领域的应用进行了深入研究,针对移动 Ad Hoc 网络的特点,对蚁群算法进行了有益的改进，根据改进后的蚁群算法提内蒙古科技大学硕士学位论文 -4-出了一种基于蚁群算法的 Ad Hoc 网络 QoS 组播路由算法.并在 NS-2 仿真平台上进行了仿真实现和性能分析,实验证明,本文所提出 ABQMRA 协议在发现最短路径的同时充分考虑节点间的链路状态，提供能够满足 QoS 参数的路径进行组播数据传输，协议对节点移动性有较高的适应能力。这对于在移动 Ad Hoc 网络中提供满足一定服务质量的组播服务具有实际意义 1.2 国内外研究现状 目前，国内外学者对各种网络环

29、境中的 QoS 保障做了大量的研究工作，并在这方面取得了不少的研究成果。近年来，国内外许多学者利用神经网络、蚁群算法、遗传算法等启发式智能算法来解决多约束 QoS 组播路由问题，并且取得了一定的成果15,16。各算法都有各自的优缺点及适用的网络环境，其中蚁群优化算法以其健壮性、并行性、灵活性、分布式智能优化等特点，在网络路由方面取得的优异表现，得到了广泛应用17,18。但蚁群算法在进行大规模优化时，也有其自身的缺陷。如何对蚁群算法进行改进以适应移动 Ad Hoc 网络环境，用于解决移动 Ad Hoc 网络多约束 QoS 组播路由问题是一个值得研究的课题。1.3 论文研究的内容 本文的研究内容主

30、要包括以下四个方面：(1)综合分析了移动 Ad Hoc 网络的特点，深入研究现有移动 Ad Hoc 网络组播路由技术。(2)全面探讨了 Ad Hoc 网络的 QoS 保障问题，特别对已提出的 Ad Hoc 网络 QoS路由协议进行了较深入的研究和比较。(3)深入研究蚂蚁算法基本原理，结合了移动 Ad Hoc 网络网络特征，对蚂蚁算法进行了改进。(4)提出了一种基于蚁群算法的 Ad Hoc 网络 QoS 组播路由算法.并在 NS-2 仿真平台上进行了仿真实现和性能分析。1.4 本论文实现的功能(1)对蚁群算法在移动 Ad Hoc 网络 QoS 组播路由领域的应用进行了深入研究,针对移动Ad Ho

31、c 网络的特点,利用新的蚂蚁行动规则和信息素更新方案,有效地改善了算法的收敛性和避免算法过早的陷入局部收敛。内蒙古科技大学硕士学位论文 -5-(2)提出了一种基于蚁群算法的 Ad Hoc 网络 QoS 组播路由算法.并在 NS-2 仿真平台上进行了仿真实现和性能分析,实验证明,本文所提出 ABQMRA 协议在发现最短路径的同时充分考虑节点间的链路状态，提供能够满足 QoS 参数的路径进行组播数据传输，协议对节点移动性有较高的适应能力。1.5 论文的结构安排 本论文分为六章，内容安排如下：第一章：绪论。本章主要介绍了本论文所研究内容的背景及意义，移动 Ad Hoc 网络 QoS 多播路由协议的研

32、究现状，以及本文的研究目的和主要内容。第二章：移动 Ad Hoc 网络及组播路由技术 本章首先介绍了移动 Ad Hoc 网络的定义及体系结构；接着简单分析了移动 Ad Hoc网络组播路由的设计要求；然后着重分析了几种典型组播路由协议的基本原理；最后对现有的典型组播路由协议进行了分析总结。第三章 移动 Ad Hoc 网络的QoS 保障及 QoS 路由 本章主要叙述了移动 Ad Hoc 网络的 QoS 问题，分析了 QoS 的需求，实现 QoS 所面临的挑战，移动 Ad Hoc 网络的 QoS 体系结构；接着介绍移动 Ad Hoc 网络中实施QoS 路由的策略，最后介绍现有典型的 QoS 组播路由

33、协议。第四章 蚂蚁算法及其改进 本章主要介绍了蚁群算法并对其进行了改进。首先对基本蚁群算法的原理、特点等进行了阐述；接着介绍了蚁群算法在移动 Ad Hoc 网络中应用的优点；然后重点描述了针对移动Ad Hoc 网络环境的特点对蚁群算法的改进。第五章 基于蚁群算法的 Ad Hoc 网络 QoS 组播路由协议 本章主要描述了本文所提出的基于蚁群算法的移动 Ad Hoc 网络 QoS 组播路由算法。首先介绍了 ABQMRA 协议的基本思想；然后对其数据结构及工作机制进行了详细的描述。内蒙古科技大学硕士学位论文 -6-第六章 仿真实验及性能分析 本章对 NS2 网络仿真软件进行了介绍，之后利用 NS2

34、 仿真软件对 MAODV 和ABQMRA 协议在同一网络环境下进行仿真实验，通过考查分组投递率、端到端平均时延、归一化路由开销来验证ABQMRA 协议的良好表现。内蒙古科技大学硕士学位论文 -7-2 移动Ad Hoc网络及组播路由技术 2.1 移动Ad Hoc网络概述 2.1.1 移动 Ad Hoc 网络的定义 移动 Ad Hoc 网络也被称为 MANET 网络19。它区别于传统有基站无线网络，它是由一组带有无线收发功能的移动终端组成的一个多跳、无中心、临时性自治系统，节点间的通信不依赖于预先架设的固定基础设施20,21。移动终端同时具有路由功能，可以通过无线连接构成任意的网络拓扑22,23。

35、2.1.2 移动 Ad Hoc 网络的体系结构 网络的各层及其协议的集合，称为网络的体系结构，它是网络及其部件都应完成的功能的精确定义24。由于移动Ad Hoc 网络通常应用于无线访问接入点难以建立或者无线访问接入点建造开销较高的场合，因此它常将网络的控制功能分散到网络中的多个节点或全部节点以有效地避免单点失效；并且当网络拓扑发生变化时，移动节点可以自动获取局部网络的拓扑信息，根据度量值动态计算出最佳数据传输路径，从而实现网络的控制和快速建立。体系结构定义了网络中各组件的作用及其功能。体系结构的定义对于网络的规划和整体的性能起着至关重要的作用。体系结构包括:(1)节点结构 由于移动Ad Hoc

36、 网络的节点不仅要接收数据还要进行数据的转发，因此它必须同时具备普通移动终端和路由器的双重角色。节点通常包括主机、路由器和电台三部分。其中主机能够提供面向用户的服务，这其中包括运行面向用户的应用程序、用户信息操作等;路由器主要负责获取网络环境和链路状态信息，完成数据报文转发的功能;电台部分则提供无线信道的接入，实现无线传输。(2)网络结构 由于在某些特殊场合，例如战场环境下，如果将整个网络的控制管理功能集中于网络中的一个或几个节点，容易导致中心节点成为影响整体网络性能的瓶颈，因此，集中式控制式的网络结构并不适合应用于移动 Ad Hoc 网络。正是出于对以上原因的考虑，移动Ad Hoc 网络一般

37、采用平面结构和分级结构。在平面结构中，网络中每一个节点对于其他节点都是平等的，没有父亲节点，也没有孩子节点，不存在从属关系。内蒙古科技大学硕士学位论文 -8-而分级结构中，网络通过运行相应的分簇算法将网络被划分为多个自治域，这此域以被称为簇。簇中节点有两种类型：簇头节点和簇成员节点。一个簇头节点和一个以上（包含一个）簇成员节点组成一个簇结构。在分级结构中，如果信息需要从一个簇转发到另一个簇，则这类信息的转发由簇头节点来完成。簇头节点可以人为设定，也可以通过运行相应的簇头选举算法来产生。簇头节点统治它的自治域，相对于自治域内的簇成员节点来说，簇头节点是它们的父亲节点。多个簇头节点形成了更高一级的

38、网络。而在簇头节点组成的网络中，又可以分簇，这样形成分级结构。由于分组网络是由多个簇结构组成，每个簇就是一个自治系统，我们可以通过增加簇的个数来扩在网络的规模。当我们需要使网络的深度增加时，我们可以通过增加网络的级数来增大网络的规模。因此，分级网络结构具有非常强的扩充性，这种结构适合于网络规模较大的应用场合。自治域间的路由信息需要由簇头节点来维护，簇头节点还要知道其自治域内的所有簇成员。当簇头节点由于链路状态等原因导致失效时，分级网络结构可以通过运行相应的簇头选举算法选举产生出新的簇头节点，因此，分级结构也具有很强的健壮性。2.1.3 移动 Ad Hoc 网络的协议栈结构 根据移动 Ad Ho

39、c 网络特点，参照 OSI/RM 的经典 7 层协议模型和 TCP/IP 体系结构，可以将移动Ad Hoc 网络的协议栈结构分为5 层25,26，如图 2.1 所示:图2.1 移动Ad Hoc 网络的体系结构 在这个协议栈结构中，物理层负责频率的选择、无线信号的检测、信号发送和接收等。数据链路层的 MAC 子层控制移动节点对共享无线信道的访问。逻辑链路控制子层负责数据帧的检测、流量控制等。网络层主要完成邻居发现、分组的转发和网络互连等功能。路由协议的作用是通过路由机制和路由表发现和维护满足某一个或某几个度量值的路由，用于数据报文的转发。路由协议包括单播路由协议和多播路由协议，此外，当某些业务对

40、实时性有特殊要求时，可采用虚电路方式来完成数据报文的传输;传输层向应用层 传输层 网络层 链路层 物理层 内蒙古科技大学硕士学位论文 -9-应用层提供可靠的端到端服务，Ad Hoc 网络的传输层协议包括 TCP 和 UDP 以及适用于无线环境的其他特定的传输层协议。应用层协议提供面向用户的协同应用服务27。移动Ad Hoc 网络主要用于军事战场、灾后营救等固定基础设施无法架设的临时应用场合。在不同的应用场合下，网络的拓扑变化频繁程度、无线信道的带宽以及网络的规模不尽相同。因此，设计 Ad Hoc 网络的体系结构应根据具体的应用场合和向用户提供服务的服务质量。2.1.4 移动 Ad Hoc 网络

41、的特点 移动Ad Hoc 网络主要具有以下特点28：(l)独立组网 节点开机后通过运行相应的路由协议无需人工干预即可快速构建一个独立网络。(2)无中心 移动Ad Hoc 网络采用非集中控制的无中心结构，每一个节点对于邻节点都是对等的。这一特点使得移动Ad Hoc 网络具有很强的抗毁性。(3)自组织 在移动Ad Hoc 网络中，所有节点通过分布式算法而无需人工干预自动快速构建网络。(4)多跳路由 由于节点的覆盖范围有限，当要与其覆盖范围之外的节点进行通信时，需要中间节点的转发，即要经过多跳。(5)动态拓扑 在移动Ad Hoc 网络中，移动终端能够以任意方式进行移动。拓扑结构的变化受发送功率、天气

42、和地形等综合因素的影响。(6)无线信道 移动Ad Hoc 网络采用无线信道进行数据传输。无线信道具有信号衰减快、暴露终端、隐藏终端、信道噪声大等特点，并且信道质量受外界环境影响较大。(7)移动终端的局限性 由于移动终端必须能够便于携带，轻便灵巧，因此节点一般依靠电池供电。能源有限。(8)安全性差 由于采用无线信道传输数据，且节点一般是便携式设备，终端能源有限。它更容易遭到窃听和黑客发起的拒绝服务攻击。与有线网络相比，它的安全性更差。内蒙古科技大学硕士学位论文 -10-2.2 移动Ad Hoc网络组播路由技术 2.2.1 组播的概念 组播(Multicast)，也称“多播”，是一种允许发送者一次

43、发送相同的数据包到多个接收者的网络技术。发送者把数据包发送到特定组播组，而只有属于该组播组的地址才能接收到数据包29。2.2.2 移动 Ad Hoc 网络组播路由的设计要求 移动Ad Hoc 网络组播路由设计的具体要求如下30：(1)功能性要求：移动 Ad Hoc 网络中节点的移动不受限制，移动节点需要对组播组进行动态维护。(2)健壮性要求：与传统的移动通信网络相比，Ad Hoc 网络拓扑变化频繁，移动节点必须能够以较快的速度获取网络拓扑信息进行路由，同时还要避免路由环路的发生。(3)可扩展性要求：应避免全局的洪泛，使用简单的层次形成方法等。(4)QoS(Quality of Service)

44、要求：QoS 要求针对不同的业务需求，尽量提供最优的服务。(5)可靠性要求：移动 Ad Hoc 网络组播数据分组的传输应具有一定的可靠性，避免由于路由失效导致的分组丢失。2.2.3 典型的移动 Ad Hoc 网络组播路由协议分析 移动Ad Hoc 网络固有资源的限制和结点移动性使得多播路由协议的设计尤其具有挑战性。目前各国研究人员已提出了多种移动 Ad Hoc 网络多播路由协议，根据路由产生方法不同把它们分为三类31,32：基于树的多播路由协议、基于网格的多播路由协议、混合多播路由协议。基于树的多播路由协议 (1)MAODV(Multicast Ad Hoc On-Demand Distanc

45、e Vector)33路由协议直接来源于单播 AODV34,35协议，属于按需路由协议。它采用共享树来进行数据的转发，组头节点负责转发树的建立和维护。组头节点是组播组成员，一般来说 是转发树的根节点。节点采用发送广播包的方式进行寻路从而实现路由发现。协议通过监听链路状态实现路由的维护，MAODV 采用两种机制来判断链路是否连通：一是通过发送通告消息，节点之间通过发送通告消息和数据的传输来判断邻节点是否连通；二是监听机制，相邻节点通过监听对方的发送行为来判断链路是否连通36。如果转发树由于链路的消失需要重建，内蒙古科技大学硕士学位论文 -11-则由转发树的下游节点发起链路修复。当中断链路维护失败

46、后，MAODV 协议判断转发树是否出现了分枝，若出现分枝，则需要进行转发树分枝的合并，合并操作由转发树的头节点来发起。MAODV 通过周期性的发送 Hello 消息来维护节点间的链路状态，通过广播路径询问报文来发起路由发现，这一切都会增加协议开销。(2)AMRIS(Ad Hoc Multicast Routing Protocol Utilizing Increasing ID Numbers)37协议有一个全网络的核心节点，通过“id-number”来维护一个以核心节点为中心的节点间的层次关系，并基于这种层次关系来确定建立和维护组播树的方向，AMRIS 正是利用这种层次关系实现为全网提供组播

47、路由服务。AMRIS 的组播树根节点是离核心节点最近的节点，因而可能造成组播的流量集中在核心节点周围的区域，造成网络的拥塞。(3)ADMR 38协议采用源节点为根的转发树，由源节点及中间节点的数据驱动组播树的建立和维护。ADMR 具有较小的维护开销和较高的传递效率。基于网格的多播路由协议 (1)ODMRP(On-Demand Multicast Routing Protocol)39是一种按需组播路由协议。所谓按需是指只有当组播的源节点有数据需要发送时，才会发起组播路径发现过程、建立和维护转发结构。ODMRP 通过在全网洪泛路由查找消息建立路由信息，这些路由信息构成以源节点为源节点为根的最短路

48、径树，接收到路由查找消息的成员节点响应路由查找消息，沿着之前建立的反向最短路径树传递到源节点，所有在反向最短路径树上的中间节点成为组播组的转发节点，这些最短路径相互交错构成一个网状结构。ODMRP 组播数据由转发节点在网状结构中以洪泛的形式进行转发，这种转发方式最大的优点是提高组播数据的转发成功率40,41。(2)NSMP(Neighbor-Supporting Multicast Protocol)42,43是一个类似于 ODMRP 的组播路由协议，它采取的策略是将网状转发结构的建立和维护分开进行。源节点加入到组播组时发起建立网状结构的过程，这个过程实际上和 ODMRP 建立网状结构的过程相

49、同。已经加入到组播组的节点采用局部维护的策略来进行转发结构的维护，源节点利用网络已有的组播转发状态，维护过程以洪泛的形式将发送的协议消息限制在一定范围内。在建立网状结构的过程中，邻节点监听组播成员、转发成员发出的协议消息以确定身份。通过引入局部维护策略，NSMP 仅在小范围内发送维护消息，从而有效降低了维护转发结构的成本。它还采用全局洪泛机制来防止局部维护失效。混合多播路由协议 (1)MCRDAR(Multicast Core Extraction Distributed Ad Hoc Routing)44采用网状结构作为底层基础结构，因此当底层基础结构中的某些链路中断时无需重构基础。底层基础

50、结构建立后，在其上建立了一个隐含的基于路由的转发树，这种转发机制提高了效率的同时，避免了由于某条链路的中断而不断地重建转发路径，有效地降低了路由开销。内蒙古科技大学硕士学位论文 -12-(2)AMRoute45采用单播隧道技术建立转发树，转发树只包含成员节点。逻辑链路的构成依靠成员节点之间的单播连接建立，组播数据封装在单播数据包中分发，并且只在成员节点间进行复制。AMRoute 采用叠加网的思路分两个主要步骤建立组播转发树：首先，在成员节点之间建立网状结构，之后根据路径选择策略在网状结构中建立链路和维护组播树。2.2.4 典型协议的分析总结 多播路由协议设计的基本思想是将多播数据分组以最高的效