（计算机应用技术专业论文）基于ad+hoc网络的运动一致性模型研究.pdf

中南民族大学硕士学位论文 摘 要 ad hoc 网络是由一组通过无线链路连接的移动路由终端组成的自治系统，移 动终端具有路由功能，可以通过无线连接构成任意的网络拓扑，这种网络可以独 立工作，也可以与 internet 或更大规模的网络连接1。ad hoc 网络中，每个移动终 端兼备主机和路由器两种功能：作为主机，终端需要运行面向用户的应用程序； 作为路由器，终端需要运行相应的路由协议。移动终端所具有的动态拓扑结构、 能量受限等特点，对 ad hoc 网络的路由协议提出了严峻的技术挑战。 本文通过对 ad hoc 无线移动网络的分析，一方面阐述了节点运动性是 ad hoc 无线移动网络的显著特性，它与网络性能密切相关；另一方面也介绍了 rpgm(reference point group model)模型，它体现了一种运动一致性思想，实际上 也是一种以任务为中心的移动网络中节点与节点之间不会离得太远相对运动不会 太大的概念模型。本文正是基于这种运动一致性特点，来研究如何提高网络的性 能，探讨对大规模 ad hoc 网络路由协议 lanmar 的修改，旨在减少路由响应时 间，提高网络吞吐量和减少节点电池能耗，以便延长网络独立持续时间。 本文首先对现有协议性能进行了横向分析，选取合适协议应用于大规模无线 ad hoc 网络中作为簇内节点的平面路由协议，作为创新点，本文对运动一致性进 行了深入探讨，建立了利用 gps 技术加快簇内节点聚合的平面路由协议和以 lanmar 为簇间路由协议的完整 rpgm 模型，并采用 ns2 网络仿真工具搭建了 无线自组织网的仿真平台，在此平台的基础上完成了以 aodv 作为平面路由协议 和 lanmar 作为簇间路由的 mag-lanmar 协议，通过仿真，将改进后的路由 协议和原有的 aodv 协议进行性能比较，验证了在路由响应时间，路由负载，网 络平均吞吐量方面 maglanmar 的成功的提高了无线网络的性能，为进一步 实际开发分簇路由协议设计和规划提供了参考算法，模型和参考数据。 关键字：ad hoc；多跳；无中心结构；运动一致性；manet；lanmar；rpgm 中 南 民 族 大 学 硕 士 学 位 论 文 ii abstract a mobile ad hoc network (manet) is an autonomous system of mobile routers connected by wireless links. the routers, which have the routing functions, are free to move randomly and organize themselves arbitrarily. such a network may operate in a standalone fashion. or may be connected to the larger internet. every mobile routers in ad hoc network plays two kinds of roles, the first is host on which users applications run, the second is router that must have appropriate router functions. because of arbitrary topology and limitation of energy, the research of ad hoc focuses on routing protocols especially large scale mobile ad hoc network (manet) protocol. after an analysis of the ad hoc wireless network, there apparently is a feature that ad hoc network has node mobility. it has a direct relationship with the network performance. and a concept named rpmg(refercence point group model) is presented in this thesis that contains the node mobility thought, it is also a model that the nodes are not far from each other and the relative velocity is not so high. this thesis is trying to take the motion affinity character into the lanmar protocol so that to reduce routing required time, improve network throughputs and reduce node energy consumption. the first step is making a network performance comparison which is using the existing different ad hoc routing protocols, and then chooses a appropriate one to be a plane routing protocol. and second it makes a detailed discussion about motion affinity. as a new idea, the paper constructs a integrated rpgm model which is consisted of plane routing protocol using gps technology that makes a rapid nodes aggregation and lanmar protocol as a group-to-group routing mechanism. the model was implemented into the simulation software ns2, and the two parts of the model are aodv plane protocol and lanmar group-to-group routing protocol, namely mag-lanmar. after simulation of the new model we can see the results that the new protocol performance is better than the non-modified aodv protocol. it proved that the hypothesis is a proper one, and provides confirmed foundation and reference data for the following development of practical clustering protocol. key words：ad hoc；multi hop；non-infrastructure；motion affinity；manet； lanmar；rpgm 中南民族大学中南民族大学 学位论文原创性声明学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。 对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名： 日期： 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查 阅和借阅。 本人授权中南民族大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本 学位论文。 本学位论文属于 1、保密，在_年解密后适用本授权书。 2、不保密。 （请在以上相应方框内打“” ） 作者签名： 日期： 年 月 日 导师签名： 日期： 年 月 日 中南民族大学硕士学位论文 1 第 1 章 绪 论 1.1 移动网络的各种技术 按照网络拓扑结构来分，移动网络大体可以分为有中心节点的蜂窝式和无中 心节点的分布式网络。蜂窝式通信以某一地区的机站为服务代理，这一地区的所 有终端设备都与这个中心节点交互定位；分布式需要每个节点知道邻居节点的情 况，通过邻居节点的通信可以得到整个网络的拓扑结构。 按照接入系统的不同可分为移动通信系统，无线本地环路系统，无绳电话系 统，移动卫星接入系统，无线局域网。 移动通信系统：由第一代模拟制式到第二代数字制式，第三代以 cdma 技术 为基础的移动通信系统也即将商用，第四代移动通信系统目前正在试验中。 无线本地环路系统：有线固定电话用户以无线方式接入公用电话网称为无线 本地环路系统。此方式比较经济、扩容方便，特别适合远离城市的边远地区，gsm 标准，cdma、fdma、tdma 技术也应用在无线本地环路中。 无绳电话系统：是有固定电话终端的延伸，无绳电话系统的突出特点是灵活 方便。这类固定的无线终端可以同时带有几个无线子机，子机除和母机通话外， 子机之间还可以通信。一类工作频率一般在 45mhz，天线覆盖在 100 米左右。另 一类如 dect，phs 等标准的无声电话系统工作在 800mhz1.9ghz 之间。 移动卫星接入系统：通过同步卫星实现移动通信联网是一种理想的无线接入 方式，可以真正实现任何时间、任何地点、任何人的移动通信。这种系统通常需 要卫星运动在低轨道，并且需要较多的卫星，投资很大。卫星接入系统的最大特 点是利用卫星通信的多址传输方式。为全球用户提供大垮度、大范围、远距离的 漫游和机动灵活的移动通信服务，是陆地移动通信系统的扩展和延伸，在边远的 地区、山区、海岛、受灾区、远洋船只、远航飞机等通信方面具有独特的优势。 无线局域网：无线局域网（wirelesslan，简称 wlan3）是计算机网络与无 线通信技术相结合的产物。它不受电缆束缚，可移动，能解决因有线网布线困难 等因素带来的问题，而且具有组网灵活、扩容方便、与多种网络兼容、应用广泛 等优点。随着 ieee802.11e、802.16e 的提出，无线局域网的范围将会越来越大并 且移动终端的移动速度也会越来越快。 ad hoc 网络主要是基于无线局域网接入技术的扩展和提高，在网络层上增加 了特殊的路由协议，使在地域上相近的节点可以自适应自组织成网络进行通信。 基于 ad hoc 网络的运动一致性模型研究 2 1.2 ad hoc 网络的发展历史及简介 ad hoc 网络是一种没有有线基础设备支撑的自组织移动网络，网络中的节点 均由移动主机构成。ad hoc 网络最初应用在军事领域，它的研究起源于战场环境 下分组无线网络数据通信项目，这个项目由 darpa 资助，其后，又在 1983 年和 1994 年加入了抗毁性可适应网络 suran（survivable adaptive network）项目的研 究。由于无线通信和终端技术的发展，同时 ad hoc 网络也在民用环境下得到了发 展，如需要在没有有线基础设备的地区或搭建支撑设备很困难的地区进行临时通 信时，可以很方便地通过 ad hoc 网络实现。 在 ad hoc 网络中，当两个移动主机（图 1.1 主机 1 和主机 2）在彼此的通信覆 盖范围内时，他们可以直接通信。但由于移动主机的无线通信覆盖范围有限，如 果两个距离比较远的主机（图 1.1 主机 1 和主机 3）要进行通信，则需要通过它们 之间的移动主机 2 作为转发节点才能实现。因此对于 ad hoc 网络来说，每个主机 同时也是路由器，承担寻找更新路由和转发分组的工作。在 ad hoc 网络中，每个 主机的通信距离有限，因此一条路由大多由多跳组成，数据通过多个中间主机的 转发才能到达目的地。所以 ad hoc 网络也称为多跳无线网络。 ad hoc 网络可以看作无线通信和计算机网络的交叉。在 ad hoc 网络中，采用 计算机网络的分组交换机制。通讯主机一般是便携计算机，个人数字助理（pda） 等移动终端设备。ad hoc 网络不同于 internet 环境下的移动 ip 网络。在移动 ip 网 络中，移动主机可以通过有线固定网络，拨号线路和无线链路等方式接入网络， 而在 ad hoc 网络中只可能存在无线链路一种接入方式。 节点1 节点2 节点3 图 1.1 ad hoc 网络的主机通信方式 在移动 ip 网络中，移动主机通过相邻的基站等有线设备的支撑才能通信，在 中南民族大学硕士学位论文 3 基站与基站 （代理和代理） 之间均为有线网络， 仍然使用 internet 的传统路由协议。 而 ad hoc 网络中没有这些设备的支持。此外，在移动 ip 网络中移动主机不具有 路由功能，只是一个一般的通信终端而已。当移动主机从一个区移动到另一个区 时并不改变网络的拓扑结构， 而 ad hoc 网络中主机的移动将会导致网络拓扑结构 的改变。 1.3 ad hoc 网络特点 无线移动 ad hoc 网络(manet)是一种移动的、多跳的、自组织的系统14， 与传统有线的分组交换网相比，它具有以下几个主要特征： （1）动态的网络拓扑结构。网络中的主机（矣称节点）可以任意移动，因此 网络拓扑结构会随节点的运动随机的和迅速的改变，并且这个改变是不可预测的， 节点之间的链路有可能是双向链路，也有可能是单向链路； （2）受限和变化的链路带宽。由于拓扑动态变化导致每个节点转发的非自身 作为目的地的业务量随时间而变化，因此，与有线网络不同，它的链路容量表现 出时变特征； （3）能量有限。ad hoc 的节点大多数甚至所有都是使用电池供电的，因而， 在进行系统设计时，节能就成为一个非常重要的指标； （4）物理层安全有限。移动网络远比固定网络更易受到安全威胁。窃听，拒 绝服务等攻击应该考虑进来，由于不是以中心为结构的网络，信息不会集中在某 一节点，所以分散了信息安全的风险，这也是与固定网络不同的地方。 以上特点使得 ad hoc 网络在体系结构、网络组织、协议设计等方面都与普通 的蜂窝式移动通信网络与有线固定通信网络有着显著的区别，而且这些特点都极 大地增加了 ad hoc 网络协议设计的难度。在进行 ad hoc 网络协议设计时，一般 要求网络协议具有以下性质： 分布式运行，这是 ad hoc 路由协议的最重要的属性； 不存在环路，虽然 ttl 可以防止分组随意的在网络中无限转发，但是路由 协议应该尽量防止环路出现的可能，使网络具有更高的性能； 基于应用的工作方式。路由算法在应用的基础上根据数据传输的方式进行 调整，而不是在网络中假设一个均匀的传输量。如果能够智能地做到这一点，就 可以更有效地利用网络的能量和带宽，但是这样做的代价是增加了节点转发延时。 例如在网络流量中往往会出现某一热点地区，即大部分数据流量集中汇聚到某一 节点，这样会增加这一节点的能量消耗，也会增将节点的转发效率，为了避免这 样的情况发生只能避开这样的热点地区，所以重新计算的路由并不是最短路径， 但是最优的； 基于 ad hoc 网络的运动一致性模型研究 4 先验式的工作方式：在有的情况下，额外的等待时间使基于需求的工作方 式不能接受。如果带宽和能量资源允许，这些情况下的先验式的工作方式是必须 的，比如在建立初始路由表阶段。 （5）安全性：如果不在网络层和数据链路层增加一些安全防御措施，ad hoc 路由协议很容易受到各种形式的攻击。 在没有适当安全保护的无线 ad hoc 网络中， 很容易受到监听网络传输、重新传输、对分组头进行修改和重定向路由信息等攻 击。当这些安全问题在以中心结构的网络中关注的同时，要想在 ad hoc 的特殊传 输媒介中保持前者的安全等级无疑是非常困难的； （6） “睡眠”周期操作。由于要节约能源和其他一些需要等待的状态，ad hoc 中的节点需要停止传输或接受(即使接受需要能量)任意个时钟周期。 路由协议应能 够适应这样的睡眠周期而不会引起太大的不利结果。这种特性也许需要通过一个 标准的接口关闭有关链路层协议； （7）单向的链路支持。许多路由协议在设计的时候都作了双向链路的假设， 因此，在单向链路的时候不能正常工作，而且单向链路在无线网络中是会常常遇 到的。一般情况下，网络中存在许多双向链路，因而单向链路的使用就成为次要 的事情。然而，在一对单向链路(相反的方向)组成了两个 ad hoc 区域之间唯一的 双向的连接的情况下，使用单向链路的能力就变得有意义了。 在对 ad hoc 网络协议进行性能评估时，主要应考虑如下性能参量： （1）端到端数据吞吐量和延时。数据路由性能的统计量(例如，均值、方差、 分布)是很重要的。它们是路由方案有效性(路由方案完成工作的好坏)的量度，这 是从使用路由的其他外部方案的观点来测量的； （2）路由获取时间。是当有请求时需要建立路由所需的时间； （3）非顺序发送百分比。一种有关无连接的路由性能的外部测量，对传送层 (例如，优先顺序传送的 tcp)具有重要意义； （4）效率相关问题。如果数据路由的有效性是网络协议性能的外部量度，那 么效率则是网络协议有效性的内部量度。为了达到给定路由性能标准，两种不同 的网络协议可能会具有不同数量的路由开销，这依赖于它们内部的效率。协议效 率也可能不会直接影响数据路由性能。但是，如果控制和数据传输必须分享同一 信道而且信道容量又是有限的，那么，额外的控制消息流量就会影响到数据路由 性能。 同时我们必须考虑网络的环境对路由协议的影响，以下几个因素是经常变化 的： （1）网络规模：节点数量； （2）网络连接数：即每个节点的邻居节点数（节点的度数） ； （3）拓扑变化率：网络拓扑变化的快慢； 中南民族大学硕士学位论文 5 （4）链路带宽：链路的带宽 bits/s； （5）少量的单项链路：少量的单项链路对路由性能的影响； （6）业务模式：对多播和爆发式传输对路由协议的影响； （7）运动性：节点运动的模型的建立对研究路由协议有非常大的帮助。 1.4 ad hoc 关键技术及研究现状 ad hoc 网络是一种动态变化的并基于无线信道的自组织网络，其体系结构、 qos 保障和应用等问题比较复杂并难以实现。固定网络和蜂窝网络中使用的各种 协议和技术无法直接应用在 ad hoc 网络， 因此需要为 ad hoc 网络设计专门的协议 和技术，其关键技术主要包括一下方面： 物理层自适应技术：相对较低的能量消耗，克服无线媒体的传输损伤，自适 应功率控制，自适应干扰抵消，自适应速率控制； 信道接入技术：该技术控制节点如何接入无线信道，对 ad hoc 网络的性能起 着至关重要的作用。ad hoc 网络的无线信道是多跳共享的多点信道，所以不同于 普通网络的共享广播信道、点对点无线信道和蜂窝移动通信系统中由基站控制的 无线信道。此外，ad hoc 网络还存在隐藏节点，暴露节点和入侵节点等问题； 路由技术：大体可分为两种，先验式路由协议（proactive or tabledriven）和 按需路由协议（reactive on demand） 。先验式路由有：序号距离矢量协议 dsdv （destination-sequenced distance vector） 6，无线路由协议 wrp（wireless routing protocol）7，群首网关交换路由协议 cgsr。按需路由协议有：动态源路由协议 dsr(dynamic source routing)，按需驱动距离矢量路由协议 aodv(ad hoc on-demand vector routing)，临时路由需求协议 tora(temporally ordered routing algorithm)等。前种实时性好但浪费能量，后者实时性差，但节省能量。随着网络 规模的不断扩大节点增多，现有协议已经不再适应大规模的网络拓扑，解决这个 问题的主要方法就是采用适当的分簇算法结构分层的拓扑。 服务质量：应用层要提供自适应压缩技术和信源编码技术，网络层要提供的 qos 路由，链路层要提供资源预留策略。 安全问题： 同有线网络相比， 解决无线 ad hoc 网络存在安全问题面临许多新 的困难，首先，由于信息以无线方式传输，因此，信息偷听、欺骗和包头篡改更 容易。其次，由于无线 ad hoc 网络无固定通信设备支撑、无中心，节点之间的关 系对等且拓扑动态变化，这使得传统的基于身份认证和在线服务器的安全方案难 以实现。最后，新的路由协议的引入也会带来新的安全问题。 基于 ad hoc 网络的运动一致性模型研究 6 1.5 无线 ad hoc 网络的应用前景和论文的研究意义 ad hoc 网络的无需骨干网的支持，具有组网快速，抗毁能力强，无线 ad hoc 网络具有广阔的应用前景。 在军事领域里，单兵之间，单兵与上级指挥中心之间的战场态势信息交换和 其他信息的互连互通问题。以无线 ad hoc 网络为主的单兵通信系统不仅能顺利解 决以上问题，还能对陆、空领域的作战防御系统的完善起到关键作用； 在民用领域里，紧急搜索、救灾：当地震、洪水等自然灾害发生时，平时的 固定通信设施通常已被摧毁，由于条件的限制要重新建立这些固定通信设施不仅 耗时困难，有时甚至是不可能的。无线 ad hoc 网络不需架设固定通信设施，且组 网灵活、快捷，因此可作为救援小分队的通信网络，支持实时灾情报告、救援的 组织协调等。 临时展会会场：在各种学术交流会议、商务会议、和学校的班组讨论会中， 参加会议的成员携带便携式电脑参加会议已是很平常的事，他们通常要求实现彼 此的资源共享，并能通过外部网络处理一些紧急公务，查询商务信息（如股市行 情等） 。无线 ad hoc 网络能够很方便地满足这些要求。 无线家庭网络：无线 ad hoc 网络的产品可为用户建立无线家庭网络，可以把 所有的家电以无线的方式连接起来。从而方便交流，实现资源共享，在通过无 线 ad hoc 网络的网关设备接入 internet 后，还可实现对家电的远程操作、监控和管 理。 传感器网络：作为远程监控和信息收集的手段，传感器被大量使用，通过将 分布在一定范围内的传感器连接成无线 ad hoc 网络， 将极大地提高信息收集和处 理能力。 1.6 论文主要工作和组织安排 本文的主要工作是研究怎样将运动一致性和分簇路由技术融合在一起优化分 簇路由协议，具体包括： （1）研究平面路由协议，性能比较； （2）研究分簇路由协议算法； （3）研究系统模型，及 gps 技术； （4）修改仿真软件，建立和系统模型相近的仿真模型； （5）系统仿真和性能比较； 创新点： （1）开发基于运动一致性的分簇算法； 中南民族大学硕士学位论文 7 （2）将 gps 技术应用到分簇算法中加快群组聚合。 基于 ad hoc 网络的运动一致性模型研究 8 第 2 章 ad hoc 的路由技术 2.1 ad hoc 路由协议的特点 ad hoc 网络面临的挑战之一就是无线多跳路由， 目前 internet 中使用的路由协 议主要是基于距离矢量的路由协议和基于链路状态的路由协议。这两类协议都是 针对固定网络而设计的，它们都需要周期性地交换信息来维护网络正确的路由表 或网络拓扑结构图。多跳性的 ad hoc 网络的主要特征，要实现报文的多跳转发， 必须有路由协议的支持。而 ad hoc 网络使用带宽较窄的无线信道，且由于主机的 移动造成拓扑变化比较频繁；如果直接将传统路由协议应用于 ad hoc 网络中，这 些周期性的控制信息将会占用大量的无线信道资源，降低系统效率。因此，传统 的 internet 路由协议并不能适用于 ad hoc 网络，必须为它设计专门的路由协议。 ad hoc 网络的路由协议面临非常艰巨的技术挑战。 从无线信道带宽窄的角度来看， 路由协议在节点之间交互的信息应尽量少，以减少路由协议的开销，提高信道的 效率。而从另一方面看，与固定网络相比，由于节点的移动性，ad hoc 网络的拓 扑变化要频繁得多，为了能够尽快、尽量精确地反映网络拓扑地变化，就需要更 加频繁地在节点之间交互控制报文。这本身就是一对矛盾。因此设计一个在所有 情况下都普遍适用的 ad hoc 网络路由协议基本上是不大可能的。 ad hoc 路由协议主要的难点在于不断变化的节点而引起的网络路由拓扑的变 化，很难监视每个节点的运动和路由数据包，并且在网络规模不断扩大时尤为如 此。 2.1.1 节点结构 ad hoc 网络的节点不仅要具备普通移动终端的计算功能，还要具有报文转发 功能，即路由器的功能。按照功能来分可以将节点分为主机，路由器和电台。主 机完成人机接口，数据处理等应用；路由器部分完成维护网络拓扑结构和交换路 由信息；电台部分为信息传输提供无线信道接入支持。 2.1.2 网络结构 网络拓扑结构包含四种基本结构：中心式控制结构、分层中心式控制结构、 完全分布式控制结构和分层分布式控制结构8。 前两种结构主要依赖于中心节点选 择路由和实施流量控制。由于 ad hoc 网络节点都是可移动并且功能相同，故不太 适合于集中式控制结构。尤其在战场应用场合，集中式控制结构容易被发现和摧 毁。因此后两种分布式控制结构更适合于 ad hoc 网络的特点和要求。 中南民族大学硕士学位论文 9 图 2.1 完全分布式网络结构 完全分布式网络结构如图 2.1 示，这是一种最简单的网络拓扑结构，所有节点 在网络控制、路由选择和流量管理上是平等的，所以又可以成为对等式结构。这 种结构原则上不存在瓶颈，网络比较健壮。源节点和目的节点之间一般存在多条 路径，可以较好地实现负载平衡和选择优化的路由。此外，平面结构中节点的覆 盖范围小，相对安全。但在节点数目很多，特别式在节点大量移动的情况下，平 面结构网络具有的控制开销大，路由经常中断等缺点，并且很难实施集中式的网 络管理和控制。还有它的可扩展性较差，每个节点都需要知道到达其他所有节点 的路由。因此平面结构只用于小规模的 ad hoc 网络。 图 2.2 单频分级网络 在分级结构中，ad hoc 网络被划分为一到多个簇（cluster） 。每个簇由一个簇 头（cluster header）和多个簇成员（cluster member）组成。这些簇头形成高一级 的网络。在高一级网络中，又可以再分簇，形成更高一级的网络。在分级结构中， 簇头节点负责簇间数据的转发，它可以预先指定，也可以由节点使用算法选举产 生。根据不同的硬件配置，分级结构的网络又可分为单频分级和多频分级两种。 单频分级网络如图 2.2 所示，所有节点使用同一频率通信。为了实现簇头之间的通 信，要有网关节点的支持。簇头和网关节点形成高一级的网络，称为虚拟骨干网 络。在分簇结构中，网关是指同时位于两个簇头通信范围内的节点。 基于 ad hoc 网络的运动一致性模型研究 10 图 2.3 多频分级网络 而在多频分级网络中如图 2.3，不同级采用不同的通信频率。低级节点的通信 范围较小，而高级节点要覆盖较大的范围。高级的节点同时处于多个级中，使用 多个频率，用不同的频率实现不同级的通信。如图 2.3 所示的两级网络中簇头节点 有两个频率。频率 1 用于簇头与簇成员之间的通信。而频率 2 用于簇头之间的通 信。如果硬件支持的话，分级网络中的每个节点都可以成为簇头。这样就需要适 当的簇头选举算法，算法要根据网络拓扑的变化重新分簇或废除和选举簇头。 在分级结构中，簇成员的功能比较简单，不需要维护复杂的路由信息，这大 大减小了网络中路由控制信息的数量。因此具有很好的可扩展性，网络规模不受 限制。可以简单地通过增加簇的个数和网络的级数来增加网络的规模。簇头节点 要维护到达其他簇头的路由信息，它还要知道网络中所有节点与簇的所属关系。 由于簇头节点可以随时选举产生，分级结构也具有很强的抗毁性。但分级结构也 有它的缺点。首先，维护分级结构需要节点执行簇头选举算法，这增加了计算的 复杂性。其次，簇间的信息都要经过簇头寻路，不一定能使用最佳路由。例如在 不同簇中但互为邻居的节点，在平面结构中可以直接通信，但分簇后要通过两个 簇的簇头转交，这可能会增加报文的延时。再次，作为集中转发点的簇头可能会 成为网络的瓶颈。这可以通过减小簇的覆盖范围，从而降低簇中的报文流量来解 决。 2.2 现有路由协议分类 2.2.1 平面式的路由协议 平面式路由协议适用于节点运动不快，节点数量不多的 ad hoc 网络中，从路 由策略来分大体上有两种路由协议： 一种是表驱动路由协议（proactive or table driven） ，又称主动式或者先验式路 中南民族大学硕士学位论文 11 由协议。该路由协议试图维护网络中从各个节点到所有其余节点的最新路由信息， 所有路由信息保持一致。每个节点都维护一张或几张到网络中其他节点的路由信 息表。当网络拓扑结构发生变化时，节点通过交互信息来实时地维护网络路由信 息表。目前常见的有 perkins 在 1994 年提出的 dsdv 协议，无线路由协议 wrp， 群首网关交换路由协议 cgsr 等。 对于表驱动路由协议而言，实时性很好但在维护路由信息时由于是每个节点 都要参与，所以在网络规模较大，拓扑变化较快的环境中，大量的拓扑更新消息 占用过多的信道资源，使得系统效率下降。 另一种是按需路由协议（reactive or ondemand） ，与表驱动协议相比，在这 类协议中，节点平时并不实时地维护网络路由，只有在节点有数据要发送时，才 激活路由发现机制寻找到达目的地的路由。 图 2.4 按需路由协议过程 如图 2.4 所示，如果节点 6 要传输数据到节点 5，首先查找缓冲区里是否有到 节点 5 的路由，如果没有源节点广播路由请求报文到邻居节点，邻居节点如果不 是目的节点就会继续转发这个请求报文，直到中间节点有到目的节点的路由或者 目的节点收到这个请求报文，节点会选择返回路由或按照来时路由返回目的节点 的路由信息。比如，节点 5 会选择 4，3，1 节点返回，也会选择 4，3，2 节点返 回。 这类路由协议特点时平时不会周期性的产生路由维护信息，只有等到有业务 时才会启动路由更新机制。 现有的按需路由协议有： dsr （有源路由协议） ， aodv （按需驱动距离矢量路由协议） ，tora（临时路由需求协议） 。 2.2.2 层次式路由协议 在层次式路由模式下，网络中有两类节点：终节点（endpoint）和交换节点 （switches） 。终节点可以是报文传送的源或目的，只有交换节点具有路由功能。 终节点位于层次模型的最低层，通过检查无线通信链路质量，组成以交换节点为 中心的单元，交换节点又组成更高层次的簇（cluster） ，以此类推形成层次模型。 基于 ad hoc 网络的运动一致性模型研究 12 层次模型有两个研究方向：基于簇（cluster based）12和基于支配集（dominating setbased）13。 （1） 基于簇（clusterbased） 网络被划分为多个簇，每个簇有一个簇头，所有属于簇头通信范围的站点都 属于该簇。通常在 1 个簇中，只有簇头和簇中的其他节点联系。那些具有 2 个或 多个属于不同的邻居的节点被称为网关节点，用来连接不同的簇。这样网关节点 和簇头就形成了联通的支配集，由于节点的移动性，将会不断发生簇的分解、合 并和簇成员的变化，考虑到信息开销、收集和延迟，簇生成算法是非常关键的， 具体的路由过程是：当源节点有信息要发送时，先将报文传送给本区域的簇头， 再由簇头转发给网关，然后由网关传送给下一个簇头，直至目的节点的簇头，最 后由此簇头发送给目的站点。 （2） 基于支配集 基于支配集的路由算法的主要思想就是在 ad hoc 网络中找出形成最小连通支 配集的子网，子网中的每个节点叫做网关节点，由它来维护路由表，并且捕获全 网的拓扑结构，而在子网中的节点至少和子网中的 1 个节点是相连的，被成为非 网关节点见图 3。 路由过程为： 如果发送方不是网关节点，那么它将报文传送给它的支配网关节点（称为 源网关） ； 配网关节点将报文在由连通支配集生成的子图中进行转发； 最后报文到达相应的目的网关。如果该目的网关就是目的节点，路由过程 结束；否则该目的网关会将报文直接转发给目的节点。 分级结构的优点是网络可扩充性好，路由开销小；缺点是，需要一种复杂的 分簇算法，节点路由不一定是最优路由，簇头的任务较重，它要维护到达其他簇 头的路由，还要负责管理和协调簇内的节点，有可能成为网络的瓶颈。分簇算法 有可能对网络的性能有很大影响，本文的重点集中在分簇算法上。 中南民族大学硕士学位论文 13 第 3 章 路由协议性能分析 基于运动一致性模型的路由协议是分簇路由协议，分簇路由是一种分级路由， 簇（群组）与簇之间和簇内部可以有不同的路由协议支持。簇内路由是分簇路由 协议的基础，网络初始阶段的群组建立就是依靠平面路由协议完成，所以选取性 能良好的群内路由协议的设计分簇路由协议的基础。本章在现有常用的平面路由 协议中选取四个进行横向分析，找到一个合适的平面路由应用在分簇路由协议中。 3.1 ad hoc 路由协议分析指标 评价一个路由协议的有效性、公平性、全面性，一定的测量数据支撑是必不 可少的。同时，近一步优化路由协议的性能这些数据也是重要的依据。网络性能 体系非常庞杂，并且指标非常多，但总结起来主要集中在以下几个方面： 端到端吞吐量：单位时间内传送通过网络中给定的数据量； 路由请求的时间：即统计节点有数据需求发送到数据成功发送的时间，这主 要用于按需路由方式的 ad hoc 网络路由协议的性能评价； 路由协议的效率：即完成路由任务的控制信息与用户数据信息的比率。尤其 是在控制信息与数据信息共享同一信道的情况下，该性能将直接影响到整个系统 效率的高低； 包转发率：单位时间内转发的数据包的数量； 包损失：在一段时间内网络传输及处理中丢失或出错的信息包数； 包损失率：包损失与总包数的比率； 传输延时：数据分组在网络传输中的延时时间； 开销：控制数据分组占网络所有传送的分组的比例； 延时抖动（jitter） ：连续的数据分组传输延时的变化。 吞吐量还可以用来表明某种网络设备的处理能力，网络互连设备的吞吐量定 义为不丢失任何分组的情况下，该设备所能转发的最大速率。 还需注意，不同的路由协议在不同的网络环境中差异很大，就是相同的路由 协议在不同的网络环境中差异也很明显。 ad hoc 网络组网环境主要涉及的内容有： 网络的规模大小，即网络中节点个数的多少；网络的拓扑结构变化速度；节点的 移动速度；信道的传输带宽和单向信道的比率以及“休眠”节点的比率。 3.2 使用 ns2 模拟网路环境 基于 ad hoc 网络的运动一致性模型研究 14 3.2.1 ns2 简介 ns2 起源于早在 1989 年的 real 网络模拟器。在过去的几年里，ns2 发生了 实质性的演变。1995 年，ns2 的开发获得了 darpa 的支持，通 vint 项目，由 lbl、xerorx parc、ucb 和 usc/isi 合作进行。目前 ns2 的开发由 darpa 的 saman 项目和 nsf 的 conser 项目支持9。 ns2 在与 ns1 差别是： （1）ns2 重新定义了对象结构。ns1 中复杂的对象被分解为简单的组件，分 解后的对象具有更大的灵活性，可组织性和可扩展性。 （2）用 mit 的面向对象 tcl（otcl）代替了 tcl 作为模拟配置的接口。 （3）tcl 解释器的接口代码和主模拟器分离。ns1 的几乎所有功能的后向兼 容性，为 ns1 开发的 tcl 脚本通常可以在 ns2 上直接运行。 ns2 还在不断的发展，现在最新版本可以达到 2.29。 3.2.2 ns2 的原理和工作模式 首先，离散事件模拟。ns2 是一个离散事件模拟器。离散事件模拟，是几种 常用的系统模拟模型之一。简单地说，事件规定了系统状态的改变，状态的修改 仅在事件发生时进行。在一个网络模拟器中，典型的事件包括分组到达、时钟超 时等。模拟时钟的推进由事件发生的时间量确定。模拟处理过程的速率不直接对 应着实际时间。 ns2 的核心部分是一个离散事件模拟引擎。 ns2 中有一个 scheduler 类，负责记录当前时间，调度网络事件队列的事件，并提供函数产生新事件，指 定事件发生的时间。 其次，大量的可扩展的构建库。ns2 对网络系统中一些通用的实体已经进行 了建模，例如链路、队列、分组、节点等，并用对象来实现了这些实体的特性和 功能，ns2 的构件库所支持的网络类型包括广域网、局域网、移动通信网、卫星 通信网络等。 再次，分裂对象模型。ns2 的构件是用两种面向对象的语言编写的：c+和 otcl2021。otcl 是 mit 开发的面向对象的 tcl 语言。是一种灵活的、交互式的脚本 语言，用户通过 otcl 语言对构件对象（由 c+来实现）的对象进行组合和配置。 ns2 中的构件一般都是由相互关联的两个类来实现的，一个在 c+中，一个在 otcl 中。这种方式被称为分裂对象模型。构件的主要功能用 c+中实现，otcl 中的类则 主要提供 c+对象面向用户的接口。otcl 和 c+之间是通过叫做 tclcl 机制关联 起来的。 中南民族大学硕士学位论文 15 3.2.3 ns2 各组成部分 tclobject 在类层次结构中处于最高层21，所有其他主要的类都从它派生而来。 它有一个静态链表记录了用户创建的所有对象，每一个对象都有一个唯一的标识， 记录了每个对象所属的类名。使用这种公共基类的好处是各种对象可以存储在同 一个链表中，使用对象的函数知道如何处理对象和简单地进行强制类型转换以满 足自己的需要。 (1)调度器(scheduler) 调度器是仿真器的心脏，它记录当前时间，调度网络事件链表中的事件。它 有一个静态成员变量 instance，供所有的类访问同一个调度器，提供函数产生新事 件，指定事件发生的时间。 (2)事件和 tcp 分组(event sigma:计算数据包的平均值;random:产生均匀的或指数的随机数，如 随机早期探测算法。 3.3 ad hoc 路由协议性能分析 正如本章开头所述，本文首先对现有的路由协议做了定量的评估，使用了四 个不同的场景18分别对 dsdv，tora，aodv，dsr 路由协议性能进行分析。这 四个场景都是在面积为 500500m 中模拟，第一个场景是 30 个节点，运动速度最 大为 2m/s；第二个场景是 30 个节点，最大运动速度为 25m/s；第三个场景为 60 个节点， 最大运动速度为 2m/s； 最后一个场景为 60 个节点， 最大运动速度为 25m/s。 所有的节点运动轨迹都是随机运动。 3.3.1 路由协议简介 1、dsdv（destination-sequenced distance vector） 目的序列距离矢量路由 dsdv 是一种表驱动路由协议5，在 dsdv 中每个移 动节点维护一个路由表，表中的内容所列的是到每个可到达的目标节点的下一跳 路由。路由表表项包括目的节点，跳数和目的地序号，其中目的地序号由目的节 点分配，主要用于判别路由是否过时，并可防止路由环路的产生。每个节点周期 性地与临节点交换路由信息，当然也可以根据路由表地改变来触发路由更新。路 由表更新有两种方式：一种是全部更新（fulldump） ，即拓扑更新消息中将包括整 个路由表，主要应用于网络变化较快地情况；另一种方式是部分更新（incremental update） ，更新包含变化的路由部分。在 dsdv 中只使用序列号最高的路由，如果 两个路由具有相同的序列号， 那么将选择最优的路由 （跳数最短） 。 ns2 实现 dsdv 路由协议的具体策略为：一个没有找到路由的分组到达节点后首先被缓存，同时 节点发送路由查询消息，直接接收到来自接收端的路由响应消息。当缓存溢出时， 中南民族大学硕士学位论文 17 新来的分组将被丢弃。分组到达目的节点后将直接由地址解复用器（delux）送到 响应的端口，而后由端口将分组送到目的代理。 dsdv 对 bellmanford 路由算法进行了改进，dsdv 通过在路由接口附加序 号的方法解决了距离矢量路由中的环路问题。一个节点增加它的当前序号并把它 的增加到自身所产生的更新消息中，因此这个序号和距离信息一起进行传输，任 何没有下一跳节点而不能进入其目的节点接口的节点，需要增加这个序列号并在 这条路由的下一次广播中使用这个新的序列号。 2、tora( temporally ordered routing algorithm) 临时按序路由算法基于链路反转10, 在高度动态移动的网络环境中操作22。 它由源发起, 并且对任何期望的源目的端对提供多重路由。 关键的设计理念是将控 制信息控制在靠近拓扑变化的很少的一组节点范围内, 其技术关键在于如何将一 个面向非目的端的有向非循环图转变为面向目的端的有向非循环图，方法有 2 种: 完全反转和部分反转。因此, 节点需要维护关于邻近(一跳) 节点的路由信息。 tora 是一个多路径算法, 最适应于有高密度节点的网络。 tora 支持多路由, 支持组播。 tor