（通信与信息系统专业论文）稀疏ad+hoc网络中路由算法的研究.pdf

摘要 摘要 本论文的研究工作源于设计与开发d t n ( d e l a yt o l e r a n tn e t w o r k i n g ) 网络中 路由协议的预研项目，对现有d t n 网络中的路由技术进行研究和性能分析，为 传输层协议提供更好的路由支持。 在实际工作中，本论文以稀疏a dh o c 网络作为主要研究对象。叙述了稀疏 a dh o c 网络的应用背景和技术架构，分析了三种比较典型的稀疏a dh o c 路由协 议( e p i d e m i c 路由协议、p r o p h e t 路由协议和m e s s a g ef e r r y i n g 路由协议) 。在 稀疏a dh o c 网络中，路由协议性能与网络资源耗用量问始终处于矛盾的竞争关 系，如何对这一矛盾进行权衡取舍，是设计稀疏a dh o c 网络路由协议的重点和 难点。同时，针对不同的网络环境和网络应用，协议性能与资源耗用量的各项指 标的权重会有显著差异，如何因地制宜的使这一指标序列达到最优，也是设计稀 疏a dh o c 网络路由协议的另一个重点。 本论文重点研究了e p i d e m i c 路由协议的原理、实现与性能。e p i d e m i c 路由协 议在数据缓存不受限制的条件下，能够实现较高的数据到达率和较低的传输时延， 但是基于洪泛的协议实现也造成了较重的网络资源负担，如果数据缓存受限，会 对协议性能产生较大影响。针对e p i d e m i c 路由协议的这些特点和不足，本论文对 其进行了改进和优化，分别引入了到达通告机制与定位机制，在保证协议性能的 前提下减小了协议对网络资源的消耗。 本论文选用n s 2 网络仿真软件搭建仿真平台，并对e p i d e m i c 路由协议及其 改进协议进行了仿真和性能评估。n s 2 是个开放源代码的优秀仿真软件，它的 分裂式编程结构和基于节点的设计理念非常适合对a dh o c 网络协议进行仿真和 性能评估，同时它的开放性也给初级用户带来了巨大的困难和挑战。如何驾驭好 n s 2 这一仿真利器，完成从协议分析、分组管理、代码编译到场景设计、调试跟 踪、t r a c e 处理的一套完整仿真流程是本论文解决的又一个难点。同时在论文后期， 探讨了不同移动模型的选取对协议性能的影响，并对其进行了初步研究。 关键词：稀疏a dh o c 网络，z p i d e m i c 路由协议，请求定位，n s 2 网络仿真 a b s t r a c t t h er e s e a r c hw o r k si nt h i st h e s i so r i g i n a t ef r o mt h ep r e - r e s e a r c hp r o j e c to f d e s i g n i n ga n dd e v e l o p m e n t i n gd t nr o u t i n gp r o t o c o l s t oi n v e s t i g a t ea n de v a l u a t et h e e x i s t i n gd t nr o u t i n gt e c h n o l o g i e s ，a n ds u p p o r tt r a n s p o r tl a y e rp r o t o c o lw i t hb e t t e r r o u t i n gp r o t o c o l s i np r a c t i c a lw o r k ，w et a k es p a r s em o b i l ea dh o cn e t w o r k sa sm a j o rr e s e a r c h o b j e c t t h eb a c k g r o u n d a n d t e c h n o l o g yf r a m e w o r k o fs p a r s em o b i l ea dh o c n e t w o r k sa r ei n t r o d u c e d a n dt h r e et y p e so ft y p i c a lr o u t i n gp r o t o c o l s ( e p i d e m i c p r o t o c o l ，p r o p h e tp r o t o c o la n dm e s s a g ef e r r y i n gp r o t o c 0 1 ) a r ea n a l y z e d i ns p a r s e m o b i l ea dh o cn e t w o r k s ，r o u t i n gp e r f o r m a n c ea n dn e t w o r kr e s o u r c ec o n s u m p t i o n r e m a i n sc o m p e t i t i v er e l a t i o n s a n dh o wt oc o n d u c tt r a d e - o f f sf o rt h i sc o n t r a d i c t i o ni s t h em a i np o i n to fd e s i g n i n gr o u t i n gp r o t o c o l s a tt h es a m et i m e ，t h ew e i i g h to f p e r f o r m a n c e a n d c o n s u m p t i o nv a r y w i t hd i f f e r e n tn e t w o r ke n v i r o n m e n ta n d a p p l i c a t i o n s ，a n dh o w t om a k ev a r i e t i e so fp a r a m e t e r so p t i m i z e di sa n o t h e rp o i n t t h i st h e s i sf o c u s e so nt h e p r i n c i p l e ，i m p l e m e n t a t i o n a n dp e r f o r m a n c eo f e p i d e m i cr o u t i n gp r o t o c 0 1 e p i d e m i cr o u t i n gc a na c h i e v eh i g hd e l i v e r yr a t ea n dl o w t r a n s m i s s i o nl a t e n c yi fn o d eb u f f e rr e m a i n su n r e s t r i c t e d b u tb a s e do nf l o o d i n g p r o p e r t y , t h i sp r o t o c o la l s oc a u s e sh e a v yr e s o u r c eo v e r h e a d i no r d e rt oi m p r o v et h e p e r f o r m a n c ea n dr e s o u r c ec o n s u m p t i o no fe p i d e m i cr o u t i n g ，w ei n t r o d u c ed e l i v e r y a c k n o w l e d g e m e n ta n dq u e r yl o c a l i z a t i o nm e c h a n i s mt o i t t h es i m u l a t i o nr e s u l t s t e s t i f yt h ei m p r o v e m e n t o u rr e s e a r c hc h o o s e sn s 2a ss i m u l a t i o n p l a t f o r m n s 2i s a n o p e n s o u r c e s o f t w a r e ，a n di t sd e s i g na r c h i t e c t u r ei sv e r ys u i t a b l ef o rn o d e ss i m u l a t i o ni na dh o c n e t w o r k s ，w h i l ei t so p e n s o u r c ep r o p e r t yc h a l l e n g e sp r i m a r yu s e r s a tt h es a m et i m e ， w ew 圳e v a 】u a t ed i f f e r e n tm o b i l em o d e 】si no u rr e s e a r c h k e y w o r d s ：s p a r s em o b i l ea d - h o cn e t w o r k s ，e p i d e m i cr o u t i n gp r o t o c o l ，q u e r y l o c a l i z a t i o n n s 2n e t w o r ks i m u l a t i o n i i 缩略语表 a o d v c m u d a r p a d s r d t n d t n r g e p i e p i q l x f i f o f i m f g p s h c i m e p m a c m a p m f n i m f 0 s p f r i p s v t o r a v i n t w s n x e p i 缩略语表 a dh o c0 n d e m a n dd i s t a n c ev e c t o r c a r n e g i em e l l o nu n i v e r s i t y d e f e n s ea d v a n c e dr e s e a r c hp r o j e c t sa g e n c y d y n a m i cs o u r c er o u t i n g d e l a yt o l e r a n tn e t w o r k i n g d e l a yt o l e r a n tn e t w o r k i n gr e s e a r c hg r o u p e p i d e m i cr o u t i n gp r o t o c o l e p i d e m i cw i t hq u e r yl o c a l i z a t i o ne x t e n s i o n f i r s ti nf i r s to u t f e r r yi n i t i a t e dm e s s a g ef e r r y i n g g l o b a lp o s i t i o n i n gs y s t e m h o pc o u n t i n t e r n e tm a n e te n c a p s u l a t i o np r o t o c o l m e d i u ma c c e s sc o n t r o l m o b i l ea c c e s sp o i n t s m e s s a g ef e r r y i n g n o d ei n i t i a t e dm e s s a g ef e r r y i n g o p e n s h o r t e s tp a t hf i r s t r o u t i n gi n f o r m a t i o np r o t o c o l s u m m a r y v e c t o r t e m p o r a l l yo r d e r e dr o u t i n ga l g o r i t h m v i r t u a li n t e r n e tt e s t b e d w i r e l e s ss e n s o rn e t w o r k s e x t e n d e de p i d e m i cr o u t i n gp r o t o c 0 1 v i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：彳马互彝未固l 日期：渺。6 年，甩6 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 第一章绪论 1 1 引言 第一章绪论 随着人们对移动通信的需求越来越强，近年来，移动通信技术得到了飞速普 及和发展，新技术不断涌现。蜂窝移动通信系统在短短十几年间就完成了从第一 代到第二代和第二代半的跨越，并正在向第三代系统演进。此外，无线局域网 ( 1 e e e 8 0 2 1 1 和h i p e r l a n ) ，蓝牙( b l u e t o o t h ) ，家庭无线网( h o m e r f ) 等移动通 信新技术也纷纷涌现。这些技术使得人与人之间的通信更加方便快捷，也使人们 的生活变得更加丰富多彩。 我们通常提及的移动通信技术都是集中式的，但对于一些特殊的应用场合， 这种架构方式并不能胜任。比如，战场上部队的快速部署和推进，地震或水灾等 大型灾害后的营救，野外科考作业，以及临时性组织的大型会议等。这些场合的 通信不能依赖于任何预先部署的网络设施( 或者预先部署的设施已经因灾害损毁 而失去效用) ，而是需要一种能够临时快速自动组网的移动通信技术。作为移动通 信的一个重要分支，a dh o c 网络技术可以满足这些特殊场合的需要。 1 2a dh o c 网络及其特点 a dh o c 网络是一种特殊的无线移动通信网络。a dh o c 网络中所有节点的地位 平等，无需设置任何中心控制节点，具有很强的抗毁性。网络中的节点不仅具有 普通移动终端所需的功能，而且具有报文转发能力。当通信的源节点和目的节点 不在直接通信范围之内时，它们可以通过中间节点转发报文进行通信。有时节点 间的通信可能要经过多个中间节点的转发，即报文要经过多条( h o p ) 才能到达目 的地，这是a dh o c 与其它移动通信网络的最根本区别。a dh o c 网络的节点通过 分层的网络协议和分布式算法相互协调，实现网络的自动组织和运行。因此它又 被称为多跳无线网( m u l t i h o pw i r e l e s sn e t w o r k ) 、自组织网络( s e l f - o r g a n i z e d n e t w o r k ) 或无固定设施的网络( i n f r a s t r u c t u r e l e s sn e t w o r k ) 。 a dh o c 网络是由一组带有无线收发装置的移动终端组成的一个多跳动临时性 电子科技大学硕士学位论文 自治系统。网络中的移动终端具有路由和报文转发功能，可以通过无线连接构成 任意的网络拓扑。这种网络可以独立工作，也可以接入i n t e r n e t 或蜂窝无线网络。 在后一种情况中，a dh o c 网络通常是以末端子网的形式接入现有网络。考虑到带 宽和功率的限制，a dh o c 网络一般不适于作为中间承载网络。它只允许产生于或 目的地是网络内部节点的信息进出，而不让其它信息穿越本网络，从而大大减少 了与现有i n t e r n e t 互操作的路由开销。 a dh o c 网络中，每个移动终端兼备路由器和主机两种功能：作为主机，终端 需要运行面向用户的应用程序：作为路由器，终端需要运行相应的路由协议，根 据路由策略和路由表参与分组转发和路由维护工作。a dh o c 网络同时具备移动通 信网络和计算机网络的特点，可以看作是一种特殊的移动计算机网络。 综上所述，a dh o c 网络具有以下特点1 1 j ： 1 独立组网：网络的部署无需依赖于任何预先架设的网络设施，节点开机后 就可以快速、自动的组成一个独立的网络 2 分布式结构：a dh o c 网络采用分布式结构，任意节点的加入、离开或者故 障都不会影响整个网络的运行，和集中式网络相比具有很强的抗毁性 3 自组织：a dh o c 网络中所有节点通过分层的网络协议和分布式算法协调各 自的行为，分布式和自组织的特点使得可以实现快速自动组网 4 多跳路由：与普通网络中的多跳不同，a d h o c 网络中的多跳路由是由普通 节点共同协作完成的，而不是专门的路由设备 5 动态拓扑：a dh o c 网络中，移动终端间通过无线信道形成的网络拓扑随时 可能发生变化，而且变化的方式和速度都难以预测。在网络拓扑图中，这 些变化主要体现为节点和链路的数量及分布的变化。因此需要开发专门的 路由协议以适应动态拓扑网络的需要 6 特殊的无线信道特征：a dh o c 网络中，信道的空间复用度较高而报文的冲 突与节点所处的地理位置相关。此外，地形或发射功率等因素使得网络中 可能存在单向无线信道 7 移动终端的局限性：移动终端功率受限、内存较小、c p u 处理能力较低而 成本较高，给设计开发和应用推广带来了难度，因此如何高效的使用节点 电能和延长节点工作时间是一个十分突出的问题 第一章绪论 8 安全性：a dh o c 网络采用无线信道、有限电源、分布式控制等技术，更容 易受到被动窃听、主动入侵、拒绝服务等网络攻击。另外，a dh o c 网络由 节点自身充当路由器，不存在命名服务器和目录服务器等网络设施，也不 存在网络边界的概念。这就使得a dh o c 网络中的安全问题非常复杂，信 道加密、抗干扰、用户认证、密钥管理、访问控制和其它安全措施都需要 特别考虑 1 3a dh o c 网络的路由协议 目前在i n t e r n e t 中常用的内部网关路由协议主要有两种。一种是基于距离矢量 的路由协议( 如r i p 协议) 。在该协议中，每个路由器都维护一张距离向量表，表 中记录着本路由器到每个目的地的最佳路由( 通常最最短路由) 。通过与相邻路由 器交换距离信息来更新路由表的信息。该路由协议的路由算法采用的是 “b e l l m a n f o r d ”最短路由算法。另一种是基于链路状态的路由协议( 如o s p f 协 议) 。与距离矢量路由协议不同的是，在该协议中，所有路由器不必以分布方式计 算“最短路由”，而是通过可靠地发布链路状态分组来维护一张完整的网络拓扑结 构图，并按照该拓扑结构计算出至目的节点的最短路由。该协议采用的是d i j k s t r a 最短路径优先算法。 这两类协议都是针对固定网络而设计的，它们都需要周期性地交换信息来维 护网络正确的路由表或网络拓扑结构图。由于a dh o c 网络带宽有限、拓扑变化频 繁，这些传统的用于固定网络的路由协议不适用于a dh o c 网络，主要体现在以下 几个方面： 1 动态变化的网络拓扑结构。这些变化主要体现在节点加入、离开网络 以及链路权值系数的变化。而对于常规的有线网络，网络拓扑结构则 表现较为稳定，拓扑结构的变化通常是由于链路状态的变化( 如链路 拥塞，或是设备故障等) 所引起的。 2 周期性的广播拓扑信息会占用大量的无线信道资源，耗费电池能源， 将会严重降低系统的性能。尤其是在拓扑变化频繁的a dh o c 网络环境 中，可能当路由算法还未收敛时，网络的拓扑结构就又发生了变化。 3 单向的无线传输信道。在传统的网络路由协议中，通常认为节点间的 链路是对称的双向链路。而在a dh o c 网络中，由于无线收发设备不 电子科技大学硕士学位论文 同或周围环境对无线信道的影响，可能会造成单向的无线传输信道 正是由于以上的一些问题，如果直接将传统路由协议应用于a dh o c 网络，这 些周期性的控制信息将会占用大量的无线信道资源，降低系统效率。其中在r i p 中还会遇到无穷计数和临时环路等问题，算法收敛速度慢，使得传统的路由协议 在a dh o c 网络中不再适用。因此路由选择和路由协议成为当前a dh o c 网络研究 的一个重点问题。 1 3 1d s r 路由协议 d s r ( d y n a m i cs o u r c er o u t i n g ) 路由协议是一种基于源路由方式的按需路由 协议。在d s r 协议中，当发送者发送报文时，在数据分组头部携带到达目的节点 的路由信息，该路由信息由网络中的若干节点地址组成，源节点的数据分组就通 过这些节点的中继转发到达到达目的节点。与基于表驱动方式的路由协议不同的 是，在d s r 协议中，节点不需要实时维护网络的拓扑信息，因此在节点需要发送 数据时，如何能够知道到达目的节点的路由是d s r 路由协议需要解决的核心问题。 d s r 路由协议主要由路由发现和路由维护两部分组成。路由发现过程主要用 于帮助源节点获得到达目的节点的路由。当路由中的节点由于移动、关机等原因 无法保证到达目的节点时，当前的路由就不再有效了。d s r 协议通过路由维护过 程来监测当前路由的可用情况，当监测到路由故障时，将调用新的一轮路由发现 过程。同时为了提高系统性能，在d s r 协议中，还引入了一系列的优化技术，如 路由缓冲( r o u t ec a c h e ) 等【2 1 。 d s r 协议具有以下几个优点： 1 由于是一种按需路由，减少了路由维护的代价 2 路由缓冲技术可进一步减少路由发现的代价 3 由于采用了路由缓冲技术，会产生多径 4 支持非对称传输信道模式 d s r 协议也存在一些问题和不足： 1 由于采用源路由，每个数据分组的头部都要携带路由信息，增加了分 组长度 第一章绪论 2 路由发现的控制分组可能会遍及全网各节点，造成一定的网络负担 3 “路由响应风暴”( r o u t er e p l ys t o r m ) 问题。由于采用路由缓冲技术， 中间节点根据自己的缓冲路由，源节点会同时收到多个路由响应，造 成路由响应信息之问的竞争 4 ， 由于采用路由缓冲技术，失效的缓冲路由信息会“污染”其它节点 1 3 2t o r a 路由协议 t o r a ( t e m p o r a l l yo r d e r e dr o u t i n g a l g o r i t h m ) 路由协议是一种基于“链路反 转( 1 i n kr e v e r s a l ) ”算法的分布式路由协议。该协议支持多径、能够按需快速建立 路由。网络拓扑发生变化后的算法响应被尽量限制在局部进行，从而减小了网络 通信的开销。通常情况下，为了减小通信开销，寻找最优路径并不是t o r a 协议 实现时最重要的考虑因素。 t o r a 协议的路由实现过程被模型化为数据分组通过“管道”从“最高”的 节点“流到最低”节点。“管道”代表的就是网络中节点间的链路。通过路由 协议的计算，各个节点相对于目的节点都有一个相对“高度值”。如果节点a 和节 点b 之间的“管道”受阻( 比如无线链路不存在或者节点关机等) ，节点a 的“高 度值”就被置为比它的任何邻居节点的“高度值”都要大，则数据分组就不会从 其它节点“回流”到a 。 当个节点发现到达目的节点的路由失效时，它将目的节点的“高度值”置 为“本地最大值”，并发送一个u p d a t e 分组。如果一个节点不能在其邻居节点中 找到任何一个有限“高度值”的节点( 相对于目的节点来说) ，该节点就会重新发 送q u e r y 分组以寻找一条新路由。如果一个节点监测到了网络分割，则发送 c l e a r 分组来重置路由状态并将网络中的无效路由都清除掉【。 1 4 研究现状与主要任务 随着新型无线网络设备系统的出现，a dh o c 网络部署环境发生了巨大变化， 出现了具有稀疏特性的a dh o c 网络。很多无线网络尽管没有采用传统a dh o c 网 络的基本系统架构，但是其应用环境或者软硬件设计( 比如链路层协议、应用层 程序) 与其类似，比如w s n 网络( 无线传感器网络，w i r e l e s ss e n s o rn e t w o r k s ) 、 电子科技大学硕士学位论文 d t n 网络( d e l a y t o l e r a n tn e t w o r k i n g ) 等，其协议设计很多时候也参考了a dh o c 网络。对于很多具有稀疏特性，但是在应用环境或软硬件设计上和传统a dh o c 网 络具有相似性的无线网络，在本课题中我们通称为稀疏a dh o c 网络。在后面的章 节中，我们将对稀疏a dh o c 网络的特性做更进一步的叙述和分析。 对于传统的a dh o c 网络，一般假定从源端到目的端总是存在通路，即移动网 络中节点的无线通信范围足够大，这样在绝大部分时间内，网络中的任何一个节 点都至少和另一个节点连通( 彼此在对方的无线通信范围之内) ，从而保证现有 a dh o c 路由协议( d s r 、a o d v 、t o r a 等) 能够有效运作，在一定程度上实现 数据的实时、固定比特率传输。 然而，随着新型无线网络设备系统的出现( 比如，普通蓝牙b l u e t o o t h 网络的 覆盖距离只有1 0 一1 0 0 米，很多无线传感器网络的节点传输半径也比传统无线设 备小得多) 和a dh o c 网络部署环境的变化( 比如，将a dh o c 网络部署到更广阔 的野外、战场、科考、救灾环境中) ，上述普遍覆盖条件已经很难得到满足，同时， 研究者将a dh o c 网络应用到许多对实时性要求较低而对节点功耗较敏感的实际项 目中去，普遍覆盖条件是否满足也变得不再那么重要。鉴于这种新出现的a dh o c 网络中节点分布的稀疏性，我们将其称作稀疏a dh o c 网络( s p a r s em o b i l e a d h o c n e t w o r k s ，或者称作p a r t i a l l yc o n n e c t e da d h o cn e t w o r k s 、i n t e r m i t t e n t l yc o n n e c t e d a d h o cn e t w o r k s ) 。 稀疏a dh o c 网络的概念在本世纪初才提出。其应用环境越来越多的被研究者 发现并拓展开来，其它应用领域的研究者也越来越多的考虑将稀疏a dh o c 网络系 统和技术引入本领域。比如说，在微观上，无线传感器网络的研究和开发方兴未 艾；在宏观上，随着空间技术的发展和需要，星际间网络通信的研究也开始进入 人们的视野；很多社会学者在不发达的第三世界国家部署稀疏a dh o c 网络，帮助 当地居民实现最基本的互联网体验；生物学者在野生动物身上挂载无线通信设备 来研究其习性，很多时候只能依靠稀疏a dh o c 网络技术才能完成这种面向广阔地 域的研究工作。 与此同时，软硬件技术的发展在很大程度上使稀疏a dh o c 网络的部署成为可 能。比如极低功耗芯片设计理论和工艺技术的出现，以及针对这种硬件的需要开 发出来的编译环境和嵌入式操作系统，底功耗长距离无线电通信技术的发展也为 稀疏a dh o c 网络部署所必须。 第一章绪论 就目前而言，稀疏a d h o c 网络的研究处于起步阶段，其技术标准和规范还在 起草中，一些研究组织和项目开始建立起来，比如：i e t f 下属的i r t f 和d a r p a 联合建立的i p n r g 4 】( i n t e r p l a n e t a r yi n t e m e tr e s e a r c hg r o u p ) ，由i r l l f 资助建立的 d t n r g 5 l ( d e l a yt o l e r a n tn e t w o r k i n gr e s e a r c hg r o u p ) 等等。我们将在后面章节中 叙述几个典型的稀疏a dh o c 网络项目。 稀疏a dh o c 网络的研究目前在国内基本上还是空白。本课题主要对以下方面 进行了研究： 1 对稀疏a dh o c 网络进行了研究，详细领会了稀疏a dh o c 网络的定义、主 要特性以其典型应用 2 对稀疏a dh o c 网络中的路由问题进行了研究，叙述了目前较有影响的三 种稀疏a dh o c 路由协议，重点对e p i d e m i c 路由协议进行了原理和性能研 究，并针对其不足进行了改进和优化 3 利用n s 2 网络仿真软件对稀疏a dh o c 网络进行仿真，分别在不同的节点 运动模型中对e p i d e m i c 路由协议及其改进进行仿真研究和性能评估 1 5 论文章节安排 本文第一章首先叙述了a d h o c 网络的体系结构、特点和路由协议，叙述了稀 疏a dh o c 网络的研究背景、现状和主要任务。第二章阐述了稀疏a dh o c 网络的 主要特性、典型应用和三种较有影响的稀疏a dh o c 路由协议。第三章重点研究了 e p i d e m i c 路由的算法原理、协议实现及其改进优化。从第四章开始重点放在了仿 真方面，第四章叙述了n s 2 仿真系统，提出需要解决的主要技术难点并给出了解 决方案，详细描述了e p i d e m i c 路由协议仿真的实现和性能评估。第五章列出了仿 真结果并对其进行了分析。第六章对本文所做的工作进行了全面的总结和展望。 文章的最后是本文所引用的参考文献。 电子科技大学硕士学位论文 第二章稀疏a dh o c 网络及其路由算法浅析 2 1稀疏a d h o c 网络 对于传统的a dh o c 网络，一般假定从源端到目的端总是存在通路，即移动网 络中节点的无线通信范围足够大，这样在绝大部分时间内，网络中的任何一个节 点都至少和另一个节点连通( 彼此在对方的无线通信范围之内) ，从而保证现有 a dh o c 路由协议( d s r 、a o d v 、t o r a 等) 能够有效运作，在一定程度上实现 数据的实时、固定比特率传输。 然而，随着新型无线网络设备系统的出现( 比如，普通蓝牙b l u e t o o t h 网络的 覆盖距离只有1 0 - - 1 0 0 米，很多无线传感器网络的节点传输半径也比传统无线设 备小得多) 和a dh o c 网络部署环境的变化( 比如，将a dh o c 网络部署到更广阔 的野外、战场、科考、救灾环境中) ，上述普遍覆盖条件已经很难得到满足，同时， 研究者将a dh o c 网络应用到许多对实时陛要求较低而对节点功耗较敏感的实际项 目中去，普遍覆盖条件是否满足也变得不再那么重要。鉴于这种新出现的a dh o c 网络中节点分布的稀疏性，我们将其称作稀疏a dh o c 网络( s p a r s em o b i l e a d h o c n e t w o r k s i “，或者称作p a r t i a l l yc o n n e c t e da d h o cn e t w o r k s ”、i n t e r m i t t e n t l y c o n n e c t e d a d 。h o c n e t w o r k s ”，针对不同的命名，其研究重点也略有不同) 。 2 2 典型的稀疏a dh o c 网络应用项目 2 2 1 z e b r a n e t z e b r a n e t i 州i io 】是普林斯顿大学开发的用来跟踪野生动物( 该实验项目现阶段主 要以非洲野生斑马作为研究对象，故名为z e b r a n e t ) 生活习性的一套无线传感器 网络。z e b r a n e t 通过挂载在野生动物身上的小型传感器来跟踪其在极广阔地域上 的活动，涉及到固定和移动传感器的部署、管理和通信等方面问题。 为了使传感器网络系统能够有效运作，z e b r a n e t 的研究者开发出了高功效 ( e n e r g y - e f f i c i e n t ) 的无线节点。硬件上，z e b r a n e t 的无线节点集成了g p s ( g l o b a l p o s i t i o n i n gs y s t e m ) 卫星定位系统、嵌入式m c u 处理器单元、低功率无线收发器 第二章稀疏a dh o c 网络及其路由算法浅析 和非易失性( n o n v o l a t i l e ) f l a s hr o m ，依靠小型的太阳能电池提供能量。软件上， 搭载了轻量级嵌入式操作系统和具有存储一转发式路由( s t o r e a n d f o r w a r dr o u t i n g ) 功能的点对点( p e e r t o p e e r ) 无线通信协议，并针对模块化、小型化、自适应性和 可维护性设计进行了优化。考虑到跟踪对象活动的地域非常广阔而节点收发器的 功率很小，无线节点到基站的多跳通路存在的几率很小，所以z e b r a n e t 只能采用 单跳( h o p b y h o p ) 方式实现存储一转发式路由。 2 2 2d a t am u l e d a t am u l e i “】【1 2 】为解决一些稀疏a dh o c 网络的通信问题提供了新思路。在很 多无线传感器网络中，无线节点往往被用来进行环境监测等应用，节点相对固定 或者仅在较固定的区域内移动。这些节点周期性的进行数据采集并将数据通过多 跳无线通信传送到固定基站。考虑到无线节点资源受限( r e s o u r c ec o n s t r a i n e d ) 而 且数据通信是电能的主要消耗源，造成越靠近固定基站的节点消耗能量越多，而 且越靠近基站的节点损坏对整个网络通信的影响越大。d a t am u l e 项目中，研究者 设计了可以在全网范围内移动的基站，用来收集网络中节点的数据。这样就大大 提高了网络中节点的能量消耗均衡性和整个网络的健壮性。同时因为基站能在全 网范围内移动，即使在普遍覆盖条件难以满足的稀疏a dh o c 网络中，移动基站也 能够收集到全网数据，大大节省了每个节点的能量消耗。 d a t am u l e 网络中要解决的关键问题是移动基站的控制，这个问题可以从时间 域或者空间域两个方向上解决。如果在时间域中解决，需要设计好移动基站的运 行路线和速度，移动基站在设计好的路线上周期性重复运行，根据网络中的数据 拥塞情况和无线链路状况动态调整运行速度。通过算法设计，移动基站可以动态 调整自己的运行路线来实现数据传输的优化；而在无线节点的移动可以自主控制 的网络中，也可以为节点移动设计算法来配合移动基站，实现数据传输的最优化。 在本论文的后面部分，m e s s a g ef e r r y i n g 算法比较好的解决了上述问题。对于空间 域，可以将其模型化为一个线性规划问题，而且可以证明这是一个n p c o m p l e t e 问题【1 3 1 ，通过一些启发式算法也可以解决。 电子科技大学硕士学位论文 2 2 3d a k n e t 幽2 1d a k n e t 网络工作不惹图 d a k n e t l l 4 】为缺少基本通信设施的偏远地区提供了一种低成本的数据互联互通 方案。如左图所示，传统的长距离有线互联方案成本高而且功耗大，在d a k n e t 中， 各个村落之间的数据通信通过可移动接入设备( m a p ，m o b i l e a c c e s sp o i n t s ) 来实 现。每个村落有自己的内部网( i n t r a n e t ) 和一个公共的对外无线收发器( k i o s k ) ， m a p 上也集成了无线收发器，它被挂载在公共汽车、摩托车甚至自行车上。当进 入到一个村落的k i o s k 无线通信范围内时，m a p 和k i o s k 间就可以实现无线的 数据上传下载。m a p 往返于各个村落之间，这样就实现了各个村落间的互联互通。 当m a p 进入到和因特网相连的无线接入点通信范围内时，就可以实现d a k n e t 与 外界因特网的通信。 尽管d a k n e t 的通信是异步非实时的，但是它能以较低的成本、较高的可靠性 和带宽( 无线通信的高带宽和m a p 的大存储容量保证了这一点) 提供一些基本的 互联互通服务，比如数据文件的传输、电子邮件等。d a k n e t 为偏远贫困地区的网 络通信提供了一种可行的方案。 2 3 稀疏a dh o c 网络路由协议设计的关键问题 通过上面的典型项目分析可以看出，和传统a dh o c 网络相比，稀疏a dh o c 网络有四个特点： 1 节点的无线通信范围较传统节点小 第二章稀疏a dh o c 网络及其路由算法浅析 2 整个无线网络处于分割状态 3 数据传输具有随机性 4 异步传输的时延较大 因此，稀疏a dh o c 网络的路由协议需要考虑以下几个问题： 1 网络信息的不确定性： 数据的发送者对网络中其它节点的位置、移动、速度等信息知之甚少。因此 稀疏a d h o c 网络路由协议要解决的一个关键问题就是：当载有数据的节点进入另 一个可能的交换节点无线通信范围内时，数据是否转发应该遵循什么规则。比如 说：可以根据两节点最近进行通信的时间或者两节点移动的速度和方向来制定规 则。 2 网络资源的分配： 和传统的路由协议不同，在稀疏a d h o c 网络中的不同节点中，可能同时存在 一个数据的多个复本( c o p i e so f m e s s a g e ) ，而且路由协议的设计者们往往也希望看 到这一点，这样可以提高数据传输的到达率、减小传输时延。所以，在设计稀疏 a dh o c 中路由协议时，需要权衡好数据到达率最大化和资源消耗最小化之问的矛 盾。 3 协议的性能： 稀疏a dh o c 网络路由协议的性能可以用几个因素来评估：数据传输的平均时 延、网络系统中存储空间和通信带宽的平均消耗、数据从源端传送到目的端的平 均能耗等等。对于移动节点来说，最后一个评估因素尤为重要。从后续的协议分 析和仿真中可以看到，路由协议性能的各个评估因素相互制约影响( 由于资源受 限，这在稀疏a dh o c 网络中体现得尤为突出) ，如何权衡各个因素间的关系进行 协议设计、如何针对应用场合的特点进行协议选择是一个很重要的课题。 4 协议的安全性： 在a d h o c 网络中，数据从源端传送到目的端的路径往往是任意的。对于比较 敏感的信息和个人数据来说，需要路由协议提供一些保证数据可靠性、安全性和 真实性的机制。除了比较经典的加密算法，路由协议最好能记录数据在传输过程 中所经过的所有节点，这样上层应用程序可以籍此来判断数据是否经过了不被信 1 1 电子科技大学硕士学位论文 任的节点，网络中的可信任节点也可以通过数据上加载的记录信息来调整路由表、 剔除路由表中的不被信任节点。 2 4 典型的稀疏a dh o c 网络路由协议 2 4 1 e p i d e m i c 路由协议 以下三节将简要叙述目前研究得较多的三种稀疏a d h o c 网络路由协议，分别 是e p i d e m i c 、p r o p h e t 、m e s s a g ef e r r y i n g 。 e r ) i d e m i c 路由协议i7 】是第一个针对稀疏a dh o c 网络提出的路由协议。 e p i d e m i c 算法最初被用于解决大型异构网络中的数据库同步和数据复制问题1 1 5 】。 v a h d a t 和b e c k e r 将e p i d e m i c 算法的设计思想引入到a dh o c 网络的路由协议中。 每一个节点的缓存中保存要传送的数据( m e s s a g e s ) ，并为数据的集合建立名为s v ( s u m m a r yv e c t o r ) 的索引，当两个节点“接触”( 彼此进入对方的无线通信范围) 时交换彼此的s v 。交换s v 之后，节点根据对方的s v 遍历自己的s v ，并籍此来 判断自己的缓存中是否保存有对方的数据，而后节点向对方发送数据请求信息。 这种路由方式意味着：只要节点的缓存足够大，随着节点之间的不断“接触”，数 据会从源端开始像病毒( e p i d e m i c ) 那样传播到网络中的其它节点。 对于e p i d e m i c 协议，为了建立有全网意义的s v 索引，网络中的每一个传送 数据包含一个全局标志符( g l o b a l l y u n i q u e i d ) 。同时为了限制e p i d e m i c 协议对缓 存资源的快速消耗，传送数据还包含了一个h c 值( h o pc o u n t ，类似于i p 包中的 r r l 域) ，以此来限制数据在网络中能传送的最大跳数。如果h c 值设定为1 的数 据只能从源端直接传送到目的端而不能从任何其它节点中转。 e p i d e m i c 协议中网络资源的消耗在很大程度上受h c 值和节点缓存大小的制 约。理论上分析，h c 值和节点缓存越大，数据在网络中能够“传播”的范围也就 越大。 2 4 2p r o p h e t 路由协议 p r o p h e t ( p r o b a b i l i s t i cr o u t i n gp r o t o c o l