（通信与信息系统专业论文）manet中基于归一化距离的稳定路由算法研究.pdf

摘要 移动自组网是没有中心基础设施的情况下，移动终端为了相互通 信而组成自治的多跳无线网络。由于节点可以任意移动，由此导致传 输路径的频繁断裂，并带来大量的重路由操作，极大的降低了网络性 能。针对链路的稳定性，提出了一种新的预测概念，通过对网络链路 稳定性的预测来寻找最稳定路由。 本文首先总结了现有的移动自组网路由算法，分析了现有基于预 测的路由协议，并比较了它们的不足与缺点。接着本文提出一种新的 概念一归一化距离，将自由空间无线信号的传播理论应用到现实空间， 把现实环境中各种不利于信号传播的衰减损耗同化到空间距离这个参 数上，从而移动节点间在现实空间的通信可以转化为在自由空间的通 信。结合重新定义的链路生存时间与归一化距离，将直接通信节点间 的归一化距离与链路稳定性结合起来，提出一种新的基于归一化距离 的稳定路由算法，选择一条最稳定路径，并通过模拟结果说明了该算 法能有效地改进路由的稳定性，减少链路断裂个数，提高数据传送率， 改善网络性能。 关键宇：移动自组网，归一化距离，移动预测，链路稳定性 a b s t r a c t m a n e ta r es e l f - o r g a n i z i n ga n dn of i x e di n f r a s t r u c t u r e t h el o g i c a l l i n kb e t w e e nt w om o b i l en o d e sp o s s i b l yc o n s i s t so fm u l t i h o pp h y s i c a l l i n k s t h em o b i l i t yl e a d st oh i g hf r e q u e n c yo fr e r o u t i n go p e r a t i o na n d w a s t et o om u c hn e t w o r kr e s o u r c e s ，s os e v e r e l ya f f e c tt h ep e r f o r m a n c eo f m o b i l ea dh o cn e t w o r k s t h i sp a p e rm a i n l yi n t r o d u c e so n ek i n do fn e w c o n c e p t i o nb a s e dp r e d i c t i o n ，w h i c hs e e k sas t a b l er o u t ei nt h en e t w o r kb y p r e d i c t i o nt h es t a b i l i t yo fp h y s i c a ll i n k s i nt h i sp a p e r , a tf i r s tw es u m m a r i z et h ep r e s e n tr o u t i n gp r o t o c o l so f m a n e t , a n da n a l y s i st h ed i f f e r e n tp r o t o c o lb a s e do np r e d i c t i o n i ti s p r e s e n t e dt h a tt h ec o n c e p to fn o r m a l i z i n g d i s t a n c ea n dt h ea p p r o a c hh o w t o c o m p u t e t h e n o r m a l i z i n g d i s t a n c e b e t w e e nt w oc o m m u n i c a t i o n t e r m i n a l s t h et h e o r yo fr a d i o w a v ep r o p a g a t i o ni nf r e es p a c ei sa p p l i e dt o r e a l i t ys p a c e t h e nw en o r m a l i z ea l lt h ed i s a d v a n t a g ef a c t o r s ，w h i c ha r e u l l a g e a n da t t e n u a t i o nf r o mr a d i o w a v ep r o p a g a t i o n ，t ot h ef a c t o ro f d i s t a n c e w h e nt h ed i s a d v a n t a g ef a c t o r sa r en o r m a l i z e dt ot h ef a c t o r d i s t a n c e ，w ec a l lt h i n kt h er e a l i t ys p a c ea saf r e es p a c e c o m b i n i n gl i n k s t a b i l i t y a n dn o r m a l i z i n g - d i s t a n c e ，an e ws t e a d yr o u t i n ga l g o r i t h mi s p r e s e n t e dt oc h o o s et h es t e a d i e s tr o u t e t h es i m u l a t i o nr e s u l t ss h o wt h a t n e wr o u t i n ga l g o r i t h mc a nr e d u c et h en u m b e ro fb r o k e nt i m e so ft h e t r a n s m i s s i o np a t ha n dt h en u m b e ro fl o s tp a c k e t s t h ep r o t o c o lg e t sb e t t e r p e r f o r m a n c ea n di m p r o v e st h en e t w o r kp e r f o r m a n c eb yr e d u c i n gt h e i n f l u e n c eo nr o u t i n gb e c a u s eo f t h em o b i l i t yi nm a n e t k e yw o r d s ：m o b i l ea dh o cn e t w o r k s ，n o r m a l i z i n g - d i s t a n c e ，m o b i l i t y p r e d i c t i o n ，r o u t i n gs t a b i l i t y i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：叠型型牢日期：j 出月兰驷 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文； 学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名： 导师签名越弛期：丛年月坦曰 硕：f 二学位论文第一章绪 论 第一章绪论 移动自组网( m a n e t ：m o b i l ea dh o en e t w o r k ) 是由一组带有无线收发装置的 移动终端临时组成的一种多跳无线网络。它不存在固定的网络基础设施，能够快 速展开，网络中的每个节点可以自由移动，地位相等。同时节点既充当主机又兼 备路由器的功能，根据路由策略为其他节点转发分组和参与路由维护。因此，移 动自组网具有建立方便快捷，灵活，不受网络基础设施的制约等特点，在需要固 定网络设施支持的通信网络遭破坏后，这种分布式控制和无中心的网络结构由于 具有较好的鲁棒性与抗毁能力，它能够维持剩余通信能力，确保重要的通信指挥 畅通，因而可以适用于在通信基础设施很少或没有通信基础设施的地方，现存的 基础设施很昂贵或不方便使用的地方，例如学生使用笔记本电脑进行交互式的讲 座时，商家在会议当中共享信息时，战士在战场上通信或者需要依靠信息获得地 形状况| l ；j 时，以及当洪水或地震后的紧急灾难援救人员共同协作等需要建立l 临时 通信网络的环境中，具有广泛的应用前景，近年来移动自组网已成为计算机网络 研究的热点之一。 1 1 移动自组网概述 1 1 1 移动自组网简介 移动自组网的前身是分组无线网( p a c k e tr a d i on e t w o r k ) ”j 。早在1 9 7 2 年，美 国d a r p a 就启动了分组无线网项目p r n e t ，研究在战场环境下利用分组无线网 进行数据通信。在此之后，d a r p a 于1 9 8 3 年启动了高残存性自适应网络项目 s u r a n ( s u r v i v a b l ea d a p t i v en e t w o r k ) 1 4 i ，研究如何将p r n e t 的研究成果加以扩 展，以支持更大规模的网络。1 9 9 4 年，d a r p a 又启动了全球移动信息系统 g l o m o ( g l o b l em o b i l ei n f o r m a t i o ns y s t e m s ) 项目 5 1 ，旨在对能够满足军事应用需要 的、可快速展开、高抗毁性的移动信息系统进行全面深入研究。成立于1 9 9 1 年5 月的i e e e 8 0 2 1 1 标准委员会【6 1 采用了“a dh o c 网络词来描述这种特殊的自组 织对等式多跳移动通信网络，a dh o c 网络就此诞生。i e t f 也将a dh o c 网络称为 m a n e t 7 1 。 a dh o e 的意思是“f o rt h i s ”引申为“f o rt h i sp u r p o s eo n l y ”，即“为某种目的设置 的，特别的”意思，即a dh o c 网络是一种有特殊用途的网络。a dh o c 网络是由一 组带有无线收发装置的移动终端组成的一个多跳临时性自治系统1 7 l ，移动终端具 有路由功能，可以通过无线连接构成任意的网络拓扑，这种网络可以独立工作， 也可以与i n t e r n e t 或蜂窝无线网络连接。在后一种情况中，a dh o c 网络通常是以 硕士学位论文第一章绪论 末端子网的形式接入现有网络。考虑到带宽和功率的限制，m a n e t 一般不适于 作为中间传输网络，它只允许产生于或目的地是网络内部节点的信息进出，而不 让其它信息穿越本网络，从而大大减少与现存i n t e m e t 互操作的路由开销【8 j 。a d h o c 网络中，每个移动终端兼备路由器和主机两种功能：作为主机，终端需要运 行面向用户的应用程序；作为路由器，终端需要运行相应的路由协议，根据路由 策略和路由表参与分组转发和路由维护工作。在a d h o c 网络中，节点间的路由通 常由多个网段( 跳) 组成，由于终端的无线传输范围有限，两个无法直接通信的终 端节点往往要通过多个中间节点的转发来实现通信。所以，它又被称为多跳无线 网、自组织网络、无固定设施的网络或对等网络。a dh o c 网络同时具备移动通信 和计算机网络的特点，可以看作是一种特殊类型的移动计算机通信网络。 1 1 2 移动自组网的特点 与其它传统通信网络相比，a d h o c 网络具有以下显著特点： 1 无中心和自组织性 a dh o c 网络中没有绝对的控制中心，所有节点的地位平等，网络中的节点通 过分布式算法来协调彼此的行为，无需人工干预和任何其它预置的网络设施，可 以在任何时刻任何地方快速展开并自动组网。由于网络的分布式特征、节点的冗 余性和不存在单点故障点，使得网络的健壮性和抗毁性很好。 2 自动配置 自动配置是a dh o c 网络的基本特征，节点必须检测其它节点以及它们可以提 供的服务。由于网络动态变化，自动配置过程需要确保网络能够正常工作，这涉 及到连接i n t e m e t 的网关节点的更换，簇头的更新等。在网络形成阶段，节点可 以就网络拓扑进行协商( 星形、环形、点到点、点到多点、平面和分级) ，这依赖 于网络的类型、底层的无线技术和应用的需求。 3 动态变化的网络拓扑 a dh o c 网络中，移动终端能够以任意速度和任意方式在网中移动，加上无线 发送装置的天线类型多种多样、发送功率的变化、无线信道间的互相干扰、地形 和天气等综合因素的影响，移动终端间通过无线信道形成的网络拓扑随时可能发 生变化，而且变化的方式和速度都难以预测。 4 受限的无线传输带宽 a dh o c 网络采用无线传输技术作为底层通信手段，由于无线信道本身的物理 特性，它所能提供的网络带宽相对有线信道要低得多。此外，考虑到竞争共享无 线信道产生的冲突、信号衰减、噪音和信道之间干扰等多种因素，移动终端得到 的实际带宽远远小于理论上的最大带宽。 硕：i ：学位论文 第一章绪论 5 移动终端的局限性 a dh o c 网络中， 移动终端具有携带方便、轻便灵巧等好处，但是也存在固 有缺陷，例如能源受限、内存较小、c p u 性能较低等，从而给应用程序设计开发 带来一定的难度，同时屏幕等外设较小，不利于开展功能较复杂的业务。 6 安全性较差 a dh o c 网络是一种特殊的无线移动网络，由于采用无线信道、能源受限、分 布式控制等技术，网络本身比固定网络更容易遭受各种安全的威胁，无线通信的 广播本质使其更容易受到窃听、通信量分析、篡改等攻击；移动节点漫游中可能 被俘获，使自组网面临来自内部叛变节点的攻击等。加之没有基础设施的支持， 没有可信任的认证中心来提供密钥管理和身份认证等服务，传统的安全机制在移 动a dh o c 网络中难以实现。 7 网络的可扩展性不强 在目前i n t e r n e t 环境下，可以采用子网、无级域问路由( c i d r ) 和变长子网掩 码( v l s m ) 等技术，增强了i n t e m e t 的可扩展性。但是动态变化的拓扑结构使得具 有不同子网地址的移动终端可能同时处于一个a dh o c 网络中，因而子网技术所带 来的可扩展性无法应用在a dh o c 网络环境中。 8 多跳路由 由于节点发射功率的限制，节点的覆盖范围有限。当它要与其覆盖范围之外 的节点进行通信时，需要中间节点的转发。此外，a d h o c 网络中的多跳路由是由 普通节点协作完成的，而不是由专用的路由设备( 如路由器) 完成的。 9 存在单向的无线信道 a dh o c 网络采用无线信道通信，由于地形环境或发射功率等因素影响可能产 生单向无线信道。 1 0 特殊的信道共享方式 传统的共享广播式信道是一跳共享的。而在a dh o c 网络中，广播信道是多跳 共享的，一个节点的发送，只有其一跳相邻节点可以听到。 1 1 供电问题突出 考虑到成本和易于携带，节点不能配备太多数量的发送接收器，并且节点一 般依靠电池供电。因此如何节省节点电源、延长工作时间是个突出问题。 1 1 3 移动自组网的应用 移动自组网的许多优良特性为它在民用和军事通信领域占据一席之地提供了 有利的依据。首先，网络的自组性提供了廉价而且快速部署网络的可能。其次， 多跳和中间节点的转发特性可以在不降低网络覆盖范围的条件下减少每个终端的 硕士学位论文第一章绪论 发射范围，从而降低设计天线和相关发射接收部件的难度，也降低了设备的功耗， 从而为移动终端的小型化、低功耗提供了可能。从共享无线信道的角度来看，a d h o c 网络降低了信号冲突的几率，提高了信道利用率。从对使用者的保护来看， 高功率的无线电波产生的电磁辐射对用户的身体健康也有影响。另外，网络的鲁 棒性、抗毁性满足了某些特定应用需求。它的应用场合可以归纳为以下几类： 1 军事应用 军事应用是a dh o e 网络技术的主要应用领域。因其特有的无需架设网络设 施、可快速展开、抗毁性强等特点，它是数字化战场通信的首选技术，并已经成 为战术互联网的核心技术。为了满足信息战和数字化战场的需要，美军研制了大 量的无线网络设备，用于单兵、车载、指挥所等不同的场合，并大量装备部队。 美军的近期数字电台n t d r 和无线互联网控制器【9 】等通信装备都使用了a dh o c 网络技术。 2 传感器网络 传感器网络是a dh o c 网络技术应用的另一大领域。对于很多应用场合来 说传感器网络只能使用无线通信技术，并且传感器的发射功率很小。分散的传感 器通过a dh o c 网络技术组成一个网络，可以实现传感器之间和与控制中心之间的 通信。这种网络具有非常广阔的应用前景。 3 紧急和突发场合 在发生了地震、水灾、火灾或遭受其它灾难后，固定的通信网络设施都可能 无法正常工作。此时a dh o c 网络能够在这些恶劣和特殊的环境下提供通信支持， 对抢险和救灾工作具有重要意义。此外当刑警或消防队员紧急执行任务时，可以 通过a dh o e 网络来保障通信指挥的j i l 哽n 进行。 4 偏远野外地区 当处于边远或野外地区时，无法依赖固定或预设的网络设施进行通信。a dh o c 网络技术具有单独组网能力和自组织特点，是这些场合通信的最佳选择。 5 临时场合 a dh o c 网络的快速、简单组网能力使得它可以用于临时场合的通信。比如会 议、庆典、展览等场合，可以免去布线和部署网络设备的工作。 6 动态场合和分布式系统 通过无线连接远端的设备、传感节点和激励器，a dh o c 网络可以方便地用于 分布式控制，特别适合于调度和协调远端设备的工作，减少分布式控制系统的维 护和重配置成本。a dh o c 无线网络还可以用于在自动高速公路系统( a h s ) 中协调 和控制车辆j ，对工业处理过程进行远程控制等。 7 个人通信 硕士学位论文 第一章绪论 个人局域网( p a n ) 是a dh o c 网络技术的又一应用领域，用于实现p d a 、手机、 掌上电脑等个人电子通信设备之间的通信，并可以构建虚拟教室和讨论组等崭新 的移动对等应用( m p 2 p ) 。考虑到电磁波的辐射问题，个人局域网通信设备的无线 发射功率应尽量小，这样a dh o e 网络的多跳通信能力将再次展现它的独特优势。 8 商业应用 组建家庭无线网络、无线数据网络、移动医疗监护系统和无线设备网络，开 展移动和可携带计算以及无所不在的通信业务等。 9 其它应用 考虑到a dh o c 网络具有很多优良特性，它的应用领域还有很多，这需要我们 进一步去挖掘。比如它可以用来扩展现有蜂窝移动通信系统的覆盖范围【1 2 1 ，实现 地铁和隧道等场合的无线覆盖，实现汽车和飞机等交通工具之间的通信，用于辅 助教学和构建未来的移动无线城域网和自组织广域网等。 1 2 研究内容、目的和意义 移动自组网由于其节点运动的随意性，导致其拓扑结构的易变性，而拓扑结 构的易变性则使得通信链路随时都可能断裂，因此路由链路的稳定性问题，对网 络的整体性能具有很重要影响。路由的稳定性差会增加路由发起次数，增加路由 维持开销，增加网络负载，消耗本来有限的电池能量，使整个移动自组网的网络 性能大大降低。而对于路由稳定性问题的解决，可以使移动自组网的网络性能得 到提高，同时可以提高网络中能源利用的效率。同时为了适应复杂多变的网络通 信环境，使得稳定链路能够在现实多衰减多损耗多干扰的通信环境下还能维持稳 定，我们需要找出一种新的稳定路由算法。 本文为了找出一种新的适应现实通信环境下的稳定路由算法，提出一种新的 概念归化距离，并在归一化距离的基础上结合自组网移动节点的特性，通过对 链路稳定性的预测，找出一条稳定路径，以提高网络性能，减少链路断裂次数。 1 3 论文结构 论文全文共有五章，每章的内容安排如下： 第一章绪论。这一章主要介绍了移动自组网的概念、特点以及研究意义与目 的。 第二章移动自组网路由协议。总结和分析了现有移动自组网路由协议以及稳 定路由算法的预测方法。 硕士学位论文第一章绪论 第三章移动自组网中归一化距离的研究。提出了一种新的针对直接通信的移 动终端间距离的衡量概念归一化距离，并提出其原理以及数学上的计算。 第四章基于归一化距离的稳定路由算法。将归一化距离与稳定路由预测结合 起来，提出了一种基于归一化距离的稳定路由算法，并对其模拟结果进行了分析。 模拟结果显示，该路由算法在链路断裂数目、丢失数据包数目以及数据包到达率 等方面都有较大的改善，减少了网络拓扑结构的变化对于路由的影响，提高了网 络运行性能。 第五章总结与进一步的研究。对论文工作进行了总结，并提出了下一步的研 究工作。 硕士学位论文 第二章移动自纽网路由协议 第二章移动自组网路由协议 在设计移动自组网的自组织路由算法之前，我们应当首先考察一下当前已 经成为标准或者正在研究的各种路由算法的特点与优点，尤其是与本课题有较 大相似之处的移动自组织网络m a n e t 的路由算法。经过分析和对比，我们可 以从中吸取有益的经验和思路，再结合移动互联网体系结构的特点和要求，才 能设计出我们所需要的自组织路由算法。 2 1 移动自组网路由协议研究现状 2 1 1 移动自组网路由协议分类 目前，移动自组网中路由协议的最常见分类方式是基于路由发现策略的角 度，将路由协议按驱动方式分为表驱动路由协议、按需驱动路由协议和层次型 路由协议【1 4 , 3 6 , 3 9 1 三种。 1 表驱动路由协议。 表驱动路由协议也称为主动路由协议或者先验式路由协议。其原理是每个 节点维护一张包含到达节点路由信息的路由表。源节点一旦需要发送报文，可 以立即获得到达目的节点的路由。当网络拓扑发生变化时，更新路由表信息， 并把这个更新消息传遍整个网络。目前常用的表驱动路由协议主要有d s d v 、 w r p 、g s r 等。 d s d v ( d e s t i n a t i o ns e q u e n c e dd i s t a n c ev e c t o r ) 是一种平面结构的先应式 路由算法，是传统距离向量算法的一种改进。它在每条路由信息中加入由目的 节点产生的序列号，以避免路由环。为了避免路由振荡，d s d v 延迟广播可能的 不稳定路由，每个节点周期性广播它当前的路由表，包含对应于每个目的节点 的距离和所知的最大序列号。该广播消息还包含发送者自身的序列号，每广播 一次就自动加一。每个收到该广播报文的节点将报文中的对应各目的节点的序 列号与自身路由表中相应表项比较，如果报文中的序列号较高，则更新自己的 路由表，将发送者指定为下一跳，并将距离增加一跳。如果序列号相等但距离 较小，则接收节点也要更新自己的路由表。当一个节点发现链路失败，它将所 有通过该链路的目的路由的距离设为无穷并将其序列号加一。由于更新了序列 号，因此这一消息会传播到整个网络，这样所有这些目的路由指向的目的节点 都有效的与此节点断开，直到有新的序列号产生。 w r p ( w i r e l e s sr o u t i n gp r o t o c 0 1 ) 协议中，每一个节点必须维护四个表：路由 表、距离表、链路状态表和消息重传列表。节点都通过这些保存着所有邻近节 硕：t 学位论文第二章移动自组嘲路由协议 点与该节点的连接状态。节点通过距离和倒数第二跳信息来进行寻路。如果一 个节点没有消息需要发送，它必须定期发送h e l l o 消息以声明其存在。在该协议 中，因为每个节点存储着与所有邻近节点的连接信息，因此可以使所建立的路 径相对优化。但是网络中维护了更多的信息，当拓扑变化导致节点间连接变化 时，更新网络中的信息所需要的开销也就更大。 g s r ( g l o b a ls t a t er o u t i n g ) 1 6 】它是传统的链路状态协议的改进。传统的链路 状态协议中各节点每当连接发生改变时会向其他所有的节点发送链路状态信 息，g s r 则是通过周期性的交换有序的数据来散播链路状态信息，而并非传统 的泛滥方式，大大减少了散播链路状态信息的费用。 在g s r 中每个节点周期性向其邻居节点广播全部的拓扑表，拓扑表中包含 了该节点最近访问过的本地链接和当前的整个网络拓扑的链路状态信息。表中 每一项都标记上序列号，当且仅当节点收到具有更大的序列号的对应表项时， 对应于某个目的节点的链路状态被更新。 基于拓扑表中完整的网络拓扑信息。节点可以使用任意的最短路径算法计 算最优路由表。路由表中包含由该节点到达目的节点的路由的下一跳信息。g s r 采用了d i i k s t r a 算法的改进算法来实现路由表的计算。 在无线环境中信道获取是非常重要的参数，因此较少频率交换大的拓扑表 比起广播链路状态信息的泛滥方式来说效率更高。同时这种交换方式还可以保 证路由控制对网络资源的消耗不会随节点移动的快慢而改变。然而新的链接信 息没有散播开来的时候，数据只能被丢弃掉，这个散播的过程有可能需要好几 个交换周期。 2 按需驱动路由协议。 按需路由协议又称为随选型路由协议或者反应式路由协议，是专门针对 m a n e t 环境提出来的。与表驱动路由协议相反，该类协议并不事先生成路由， 而是仅在源节点需要时才这样做。因此，路由表信息是按需建立的，它可能仅 仅是整个拓扑结构信息的一部分。按需路由一般包括两个阶段，路由发现和路 由维护。该类型中各路由协议的差别表现在发现路由的过程、取得和维护信息 的方法、传输数据的方式。主要包括a o d v 、d s r 、s s r 、t o r a 和a b r 等协 议。 a o d v ( a dh o co n d e m a n dd i s t a n c ev e c t o rr o u t i n g ) 1 7 , 1 8 1 协议在建立路由的 方式上对d s d v 进行了改进。在路由过程中，中间节点不需维护路由信息或参 与路由表交换。在路由发现阶段，当节点需要发送信息而又没有目的节点的有 效路由时，启动一个路由发现过程，向网络广播一个r r e q 分组。a o d v 允许中 问节点响应耻也o 。发现路由后，中间节点或目的节点以单播的方式向源节点发 硕士学位论文第二章移动自组网路由坍议 送一个r r e p 分组，r r e p 沿着刚建立的逆向路径传输。因此，a o d v 不支持单 向链路。在路由维护阶段，当源节点得到链路中断消息后重启路由发现过程。 a o d v 的显著特点是引入了组播路由协议扩展，并通过序列号的方式解决了无 限计数问题。但与w r p 相似，它需要定期地发送h e l l o 报文，造成了一定的额 外开销。 d s r ( d y n a m i cs o u r c er o u t i n g ) 1 9 , 2 0 】协议基于源路由概念，数据分组头部必须 包含完整的路由信息，因此和a o d v 协议一样，中间节点可以响应a r e q ，但 不需要维护路由信息。与a o d v 不同的是，d s r 支持单向链路，并且在路由发 现的中继a a e q 阶段，中间节点需要将自己的地址加入到请求分组中，然后转 发。它的缺点是每个数据分组都携带了路径信息，造成协议开销较大，降低了 带宽利用率。 a b r l 2 1 1 ( a s s o c i a t i v i t y b a s e dr o u t i n g ) 协议的设计主要考虑到了移动自组织网 络动态拓扑的特点，引进了能表征链接持久性和传输质量的相关性稳定度 ( a s s o c i a t i v i t ys t a b i l i t y ) 概念。a b r 通过向相邻节点间定期产生信标( b e a c o n ) 来表 示自己的存在。当一个节点收到邻近节点发送过来的信标时，本节点就会对相 关性表( a s s o c i a t i v i t yt a b l e ) 进行更新。 对于相邻的每一个节点相关性表中都有其相关性计数，表示着该节点相对 于本节点的稳定程度。这个相关性计数为路由选择中路由的稳定度提供了一个 重要的参考。该路由协议把所选路径的稳定性考虑在内，在一定程度上避免了 路由在传输过程中发生中断，选择的路由持久性较好，质量也较高；同时由于 节点运算量比较大，源节点需要等待比较长的时间。 3 层次型路由协议 针对网络所采用的逻辑拓扑结构形式，路由协议又可以分为平面型( f l a t ) 和 层次型( h i e r a r c h i c a l ) 。前面阐述的表驱动路d j 协议和按需路由协议都属于平面型 的路由协议；而层次型路由协议则混合了表驱动路由协议和按需路由协议的优 点，因此又被称为混合型路由协议。在平面型路由协议中，所有节点功能都是 对等的；而在层次型路由协议中，层次指的是一个“群”( “c l u s t e r ”) 或“区”( “z o n e ”) ， 它们由若干个节点组成，在层次内的节点问采用表驱动路由算法，在各层次间 采用按需路由算法。 c g s r f c l u s t e r h e a dg a t e w a ys w i t c hr o u t i n g ) 协议是在d s d v 协议基础上融合 分层次的思想设计的。协议采用l c c ( l e a s tc l u s t e rc h a n g e ) 算法，把移动自组织 网络划分成若干个簇，每一个簇中有一个“簇首”( c l u s t e r h e a d ) ，而同时位于多个 簇的节点被称为网关。每个节点维护两种数据结构：路由表和簇成员表。节点 使用d s d v 协议，周期性地与同簇内的邻居节点交换簇成员表，更新表信息。 硕士学位论文第二章移动自组网路由协议 当一个节点要通信时，数据包首先传递给自己所在簇的簇首，然后通过网关到 达另外一个簇首，以此种方法穿过中间的分簇，到达目的节点所在簇的簇首， 然后再转发给目的节点。c g s r 通过分簇，大大减少了维护路由表所需要的信息 量。另外，采用这种路由的网络有比较好的扩展性，但其缺点是算法相对复杂， 需要一定的执行代价。 z r p ( z o n er o u t i n gp r o t o c 0 1 ) ”j 协议巧妙地结合了表驱动和按需路由协议 的优点。网络内的所有节点都有一个以自己为中心的虚拟区，区内的节点数与 设定的区半径有关。在区内使用表驱动路由算法，中心节点使用区内路由协议 i a r p 维持一个到区内其他成员的路由表，对区外节点的路由使用按需路由算法， 利用区间路由协议i e r p 建立临时的路由。z r p 的性能依赖于区域半径参数值。 区域半径应根据网络特征( 例如节点密度、节点速度等) 来确定 2 1 2 移动自组网所面临的主要问题 目前，移动自组织网络路由协议的研究还存在许多待解决的问题，包括以 下几个方面： 1 q o s 路由：由于移动性、信道时变性和可靠性问题，q o s 要求很难得到 满足。 2 安全性：无线信道易受到非法主机的窃听和攻击，目前，基于安全的路 由是个难点，还没有很好的解决这个问题。 3 基于能源的路由：由于m a n e t 采用电池供电，能源受限，因此设计基 于能源的路由，可以延长节点或网络的生存期，现在己经有不少研究者在从事 这方面的研究工作，但是基于能源消耗的路由算法依旧是研究的重点之一。 2 2 移动自组网基于预测的路由算法 移动自组网中的每一个节点都可以任意移动，这种移动性使得网络的拓扑结 构不断发生变化，使链路频繁发生断裂，从而导致路由失效。为了减少网络拓扑结 构的变化带来的重路由操作，寻找一条最为稳定的路径就成了关键，而路径的 稳定性依赖于组成这一路径的所有链路的稳定性，所以为了确定路径的稳定性， 首先要确定各个链路的稳定性。如何利用节点现有的运动信息预测节点在将来 某个时刻的运动状况就成了预测路由稳定性的关键。 对于路由稳定性，已有研究者做了大量工作，一般通过预测机制来建立稳 定路由。其中主要有以下三种： ( 1 ) 基于移动预测的路由协议【2 4 ，2 5 j 0 , 4 0 ； 硕士学位论文 第二章移动自组网路由协议 ( 2 ) 基于位置预测路由协议【2 6 郐1 ； ( 3 ) 基于接收功率预测的路由协议 2 7 , 2 9 1 。 然而，这些协议都有不足，没有考虑实际通信环境下的各种衰减和损耗， 对于两通信端点的距离通过其他途径获得，如通信端点位置信息的确定基本上 是通过g p s ( g l o b a lp o s i t i o ns y s t e m ) 之类的系统来定位。这种通信节点间的物理 距离与考虑了实际通信环境下各种衰减和损耗下信号的传播距离是不一致的， 从而出现两个节点间的物理距离大于节点发射半径而实际不能通信的情况。 文献 2 4 ，2 5 1 中节点坐标、运动速度以及运动方向是通过g p s 获得的。如文 献 2 6 1 ，它提出节点位置信息获得时通过g p s 或者其他手段获得，但是没有说 明怎么获得，只是假设可以清楚得到节点位置信息。对以上四种预测方案，相 对前三种来说，第四种预测方案中提出的基于接收功率预测路由协议，不用通 过不确定的位爱判断方法来获得位置信息，而通过接收功率的大小与接收功率 阀值进行比较判断是否链路稳定。文献 2 7 1 以链路状态分析为基础，在路由发现 时候尽可能保证新发现路由的可靠性；若节点接收信号强度小于危险阀值，则 启动链路状态分析模块预测链路失效时间，如果预测结果小于反应时间，就提 前进行路由维护，这里反应时间是指发送路由警告和发起新的路由发现过程所 需要的时间，而危险阀值是指节点接收信号强度达到危险阀值时链路的失效时 间等于反应时间时接收信号的强度。文献 2 8 】根据两种简化空间电波传送公式和 得到的接收功率来获得距离位置信息判断链路的稳定性，如果接收信号强度测 定由于邻居节点的快要移动出信号接收的范围，则节点以更高的传输信号强度 发送数据包以维持链路的生存，同时在链路断裂前发出路由恢复以寻找新的稳 定路由。 文献【2 9 】根据得到的几个接收不同端点发送的信号强度大小来获取链路是 否稳定的信息。但是以上几种基于接收功率的方法也存在一些不足。要么对端 点运动状态进行了理想的假设，或者所得距离位置信息给造成可以通信的假象 ( 当利用某种手段计算出实际距离后，由于通信环境的损耗、衰减，其实际可通 信距离与自由空间情况下的可通信距离有一定的减小，如果两端点距离恰好大 于实际环境下的可能通信距离而小于自由空间环境下的可通信距离，节点就会 可以通信，但是实际上接收信号已经小于接收门限) 。而这对于路由的稳定性非 常不利，所以要使路由稳定，还需要进一步的改进。 本文就是通过对直接通信节点间距离进行归一化处理，以消除这种由于非 自由空间情况下，信号衰减、损耗和各种噪声所带来的实际通信距离上的缩短 而造成的路由断裂的情况。 颂士学位论文第二章移动自组网路由协议 2 3 小结 本章对移动自组网的路由协议进行了分类与总结，并分析了现有移动自组 网路由协议所面临的问题，并对基于预测的稳定路由算法进行分析与总结，提 出了需要改进的地方。 硕= i ：学位论文 第三章移动自组网中归一化距离研究 第三章移动自组网中归一化距离研究 目前，对移动自组网中的有关研究主要针对自由空间这一理想环境，其节点 间距离的计算方法主要有以下几种： ( 1 ) 通过卫星定位系统确定两通信节点坐标位置，然后根据坐标位置变化信 息计算出两通信节点的距离1 2 4 j 1 , 3 2 】。 ( 2 ) 通过其他辅助措施得到两通信节点的具体位置，移动速度大小以及方向， 根据移动速度计算未来两通信节点的距离，预测节点保持连接的时间f 3 4 , 3 5 】。 ( 3 ) 通过接收、发送功率的比较，根据损耗衰减空间的近似信号传播公式 d ：析五石i 萨i i 丽计算出通信节点的距离p 7 ，2 9 】。 前面两种方法的基础都是要得到下一步通信节点间的距离，只是对于得到距 离的方法各不相同，但是都要增加额外的辅助设备，如：g p s 等，增加了m a n e t 的成本与能源消耗。此外，由于上面提出的方法，通常都是在理想状态，即自由 空间下的通信，并没有考虑当无线信号在现实通信环境下各种损耗与衰减，信号 的损耗与衰减将大大消耗m a n e t 有限的能源，严重地影响信号传播的稳定性和 m a n e t 路由的可靠性与稳定性 3 8 1 。 图3 - 1 两节点通信距离示意图 在m a n e t 中，若a 、b 为无线移动自组网中的两个通信节点，其中他们通信的 有效距离，即节点信号覆盖半径都为r ；a ，b 通信节点的实际距离为d ( d r 的地方接收信号。而在考虑了损耗衰 减的现实空间下d a b 为d p 2 p ( n o d e ，r r e q ) ； 计算路径稳定性。 i f ( ! r o u t i n g a a o d v c h e c k s e e n r o u t e e x i s t ) 如果没有接收过这个请求包 i f f n o d e 一 n o d e a d d r = r r e q _ d e s t a d d r ) ，如果是目的节点 r o u t i n g a a o d v l n s e r t r o u t e t a b l e ( n o d e ，r r e q ) ； 建立路由表 r o u t i n g a a o d v l n i t i a t e r r e p ( n o d e ，r r e p ) ； ，目的节点返回一个r r e p e l s e 如果不是目的节点 r o u t i n g a a o d v l n s e r t r o u t e t a b l e ( n o d e ，r r e q ) ； 硕士学位论文 第四章摧于归一化距离的稳定路由算法 接收新的r r e q ，将r r e q 放入表中 i f ( t t l 0 ) 如果生存期大于零 r o u t i n g a a o d v f o r w a r d r r e q ( n o d e ，r i 迮q ，t t l ) ； h 向邻居节点广播这个包 e l s e 否则丢弃这个包 g l o m o _ m s g f r e e ( n o d e ，r r e q ) ； ) ) e l s e 如果是重复包 i f ( r r e q 一 p n o d e a d d r = r r e q - d e s t a d d r ) 如果是目的节点 r o u t i n g a a o d v u p d a t e r o u t e t a b l e ( n o d e ，r r e q ) ； 贝, t 更新路由表 r o u t i n g a a o d v l n i t i a t e r r e p ( n o d e ，r r e p ) ； 返回一个r r e p ) e l s e 如果不是目的节点 r o u t i n g a a o d v u u p d a t e r o u t e t a b l e ( n o d e ，r r e q ) ； 更新路由表 i f ( t t l o ) ，如果生存时间大于零 r o u t i n g a a o d v f o r w a r d r r e q ( n o d e ，r r e q ，t t l ) ； i i i 甸令i 居节点广播这个包 硕士学位论文第四章基于归一化距离的稳定路由算法 e l s e 否则丢弃这个包 g l o m o _ m s g f r e e ( n o d e ，r r e q ) ； ) 当目的节点返回源节点一个r r e p 之后，接收到r r e p 的节点进行处理，处 理过程如下( 详细算法见算法2 ) ： 如果接收到的节点是中间节点，并且没有接收过r r e p 的话，就修改自己的 路由表，并激活这一条路径，同时向路径的上游节点转发这个r r e p ；如果是接 收过的重复包，则比较两条路径的稳定性，如果这一路径的稳定性更高的话，则 修改自身的路由表，激活这一路经并向上游节点转发，否则就抛弃这个r r e p 。 如果是源节点接收到r r e p ，处理过程跟中间节点一样，但是不转发这个包 了。 算法2 ：r r e p 的处理算法如下， r o u t i n g a a o d v h a n d l e r e p l y ( n o d e ，r r e p , s r c a d d r , d e s t a d d r ) r r e p 接收包的处理过程 i f ( r r e p - s r c a d d f n o d e - n o d e a d d r ) 如果是源节点接收r r e p i f ( ! r o u t i n g a a o d v c h e c k r o u t e e x i s t ) 第一次接收r r e p 包 r o u t i n g a a o d v l n s e r t r o u t e t a b l e ( n o d e ，r r e p ) ； 建立新路由表 r o u t i n