（计算机应用技术专业论文）基于邻居信息的稀疏移动自组网路由协议研究.pdf

摘要 稀疏移动自组网的部分概念米源于早期的延迟容忍网络d t n ( d e l a yt o l e r a n tn e t w o r k ) 研究。随着移动白组网应用领域的扩展，很 多应用领域都无法建立全连通网络，导致传统的移动白组网的路由协 议无法正常运行。稀疏移动自组网的路由协议能为位于不同连通域的 节点提供数据通信，因此能够更好满足非全连通网络的应用需求。 在稀疏移动自组网中，设计稀疏移动自组网路由协议的重点和难 点是如何权衡路由协议性能与网络资源耗用量。现有的稀疏移动自组 网的路由协议假定：源节点与目的节点之间总不存在通路，某些节点 按照预定路径移动传输数据，节点的缓存很大等等，在资源受限的稀 疏移动白组网中，上述条件不总是成立。为了减少这些限制，本文首 先针对e p i d e m i c 协议中无效通信过程与到达目的节点的数据分组继 续在网络中存在并扩散等不足提出了一个改进协议，改进后的协议称 为e e p i ( e x t e n d e p i d e m i c ) ，e e p i 协议能够在保证数据到达率的前 提下，减少网络资源的消耗。接着本文提出了一个基于e e p i 与 n c r a o d v 路由协议的混合式路由协议n c r e p i d e m i c ，n c r a o d v 是一个基于邻居信息的稳定路径选择路由协议。在n c r e p i d e m i c 协 议中，源节点与目的节点位于同一连通域时，以n c r a o d v 协议的 方式工作；而源节点与目的节点位于f a d d ( e p i d a t a p a c k e t ) ； 2 0 硕士学位论文 第三章改进的e p i d e m i c 路由协议 将索引号存入到m a p 容器中 t h e d a t a l n d e x t a b l e t h e d a t a p a c k e t l d - - t h e d a t a l n d e x ； 通过索引号取出数组中的分组 e p i p k t = ( e p i 木) t h e d a t a a r r a y - g e t ( t h e d a t a l n d e x ) ； t h e d a t a l n d e x t a b l e 为节点的数据与数据在数组中的位置提供了一一对应的 关系。通过数据的标识符可以得到数据在数组中的位置，这样可以随机的访问缓 存中的数据。c a r r a y 存储的是对象的指针而不是对象本身。c a r r a y 数组与普通数 组功能一样，但c a r r a y 数组能够动态增大。 2 链路通告与发送s v 在e e p i 路由协议中，节点产生的数据，不是立即发送出去，而是先将数据 存入本节点的缓存中，当有新的邻居节点进入本节点的通信范围之内，才与该节 点进行数据通信。当节点a 发现新的邻居节点b 以后，首先检查节点a 的缓存 中是否有允许复制位为t r u e 的数据，若无则取消本次数据通信过程，若有依次进 行如下操作： 1 ) 检测邻居节点表n e i g h b o r s 中是否有节点b ，若无，插入节点b ；若有， 则检查邻居节点链表的a g e 字段，若与当前时间的差值高于时间t ，则更新a g e 字段后向上层发送请求，否则更新a g e 字段后取消此次操作； 2 ) 节点a 根据自己缓存中数组即时计算s v ：i h a v e s u m m s i z e ，并将数 组i h a v e s u m m s i z e 封装到q u e r y 分组中发送给节点b 。 s v 的计算方法如下： i f ( ! r e a c h d s t c o u n t ( t e m p e p i m s g l d ) ) 判断数据分组是否到达目的节点 r e a c h d s t 是m a p 容器，存储到达目的节点的数据分组i d i n tt h e e p i l d ；数据分组i d t h e e p i l d 2 e m s g - g e t m s g l d ( ) ； m e s s a g e - s e t a v a i l ( c o u n t q u e r y , t h e e p i l d ) ； ) 3 接收s v 与发送数据请求 当节点b 接收到a 发送的q u e r y 分组以后，依次进行如下操作： 将q u e r y 分组中封装的i h a v e s u m m s i z e 与自己缓存的数组中保存的分 组进行比较，步骤如下： i h a v e i = m s g 一 g e t a v a i l ( i ) ； i f ( ! t h e d a t a l n d e x t a b l e c o u n t ( i h a v e i ) ) 2 1 硕士学位论文 第三章改进的e p i d e m i c 路由协议 m e s s a g e - s e t l w a n t ( i w a n t i n t e g e r , i h a v e i ) ； ) 首先从q u e r y 分组中得到节点a 中缓存的分组，并将其标识符保存到i h a v e 数组中：然后循环判断某分组是否在节点b 的缓存中，若不在，则将某分组的 标识符保存到i w a n t s u m m s i z e 中。 节点b 将数据请求数组i w a n t s u m m s i z e 封装到数据请求分组u p d a t e 中 发送给a 。 4 接收数据请求与数据发送 节点a 接收到b 发送的请求分组u p d a t e 以后，依次进行如下操作： 1 ) 如果该u p d a t e 分组的目的端地址( d s t ) 不等于节点a 地址，说明该 分组并不是发送给节点a 的，则取消此次操作； 2 ) 如果该u p d a t e 分组的发送端地址等于上次收到的u p d a t e 分组发送 节点的地址，说明a 收到了重复的数据请求分组，则取消此次操作； 3 ) 节点a 根据u p d a t e 分组中封装的数据请求分组i w a n t s u m m s l z e ， 将b 需要的数据从数组t h e d a t a a r r a y 中提取出来，并封装成e p l 分组发送给b 。 5 接收数据与本地更新 节点b 收到a 发送的数据后，依次进行如下操作： 1 ) 如果该e p l 分组的目的节点就是b ，说明e p l 分组正确的从源节点传送 到了目的节点，将数据传递给上层协议，并将数据保存到t h e d a t a a r r a y 中，并更 新本节点的t h e d a t a i n d e x t a b l e ； 2 ) 如果该e p l 分组的目的节点是b ，但是该分组原来已经被b 接收过，则 丢弃该分组； 3 ) 如果该分组的源节点是b ，说明该分组可能是环回( l o o p ) 数据，则丢 弃该分组。 如果该分组不满足上述三种可能，说明该分组的目的节点不是b ，但需要b 进行存储转发，则更新t h e d a t a a r r a y 与t h e d a t a l n d e x t a b l e ，等待该分组被转发。 e e p i 路由协议没有从本质上改变e p i d e m i c 路由协议的实现方式，而且随着 稀疏移动自组网的网络环境的扩展，在节点比较密集的稀疏移动自组网场景中， 源节点与目的节点位于同一连通域几率较大。为此，本文下一章提出了一种基于 邻居信息的稀疏移动自组网混合式路由协议。 2o m n e t + + 网络仿真软件 用于移动自组网的网络仿真软件有很多种，如在d a r p a ( t h ed e f e n s e a 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 ，美国国防部高级研究计划局) 支持的v i n t 硕士学位论文 第三章改进的e p i d e m i c 路由协议 ( v i r t u a li n t e r n e tt e s t b e d ) 项目上发展出来的多协议网络仿真平台n s 2 ；业界著 名的网络仿真软件o p n e tm o d e l e r 等。本文使用o m n e t + + 仿真软件【3 7 】作为网 络仿真平台。 3 2 1 仿真软件简介 o m n e t + + 是一款面向对象的离散事件网络模拟器，可以实现的功能如下： 1 无线电通信网络信道模拟 2 协议模拟 3 模拟队列网络 4 模拟多处理器和其他分布式硬件系统 5 确认硬件结构 6 测定复杂软件系统多方面的性能 7 模拟其他的任何一种合适的离散事件系统 o m n e t + + 模拟器包括一些分层次的嵌入式模型，嵌入式模型的深度是无限 的，即允许用户在模拟环境中绘制实际系统的逻辑结构。各模块通过信息的传输 进行通信，其信息可以包括任意复杂的数据结构，各模块均可以通过门或者线路 直接发送信息给目的节点或者也可以通过预先的路径进行传输。 各个模块可以有自己的参数集，参数集可以被用于定制模块行为，或者可以 用于确定模拟拓扑图的参数。模拟网络最底层的模块可以嵌入行为，这些模块被 称为基本模块，它可以利用模拟器的库函数在c + + 进行编程。 o m n e t + + 模拟器可以在根据不同的目的来改变用户接口：调试、实例和批 量执行。高级用户的接口可以把模块透明的交给用户，即允许控制模拟器执行以 及可以通过改变模块中的变量对象来干涉模拟器的执行，这在开发调试模拟器 工程师非常有用的，用户接口也促进了模块工作的实现。 o m n e t + + 模拟器的接口和工具都非常轻便，可以在w i n d o w s 和各种u n i x 操作系统下利用c + + 进行编译。o m n e t + + 还支持分布式并行仿真，o m n e t + + 可以利用多种机制来进行用于几个并联的分布式模拟器之间的通信仿真，比如 m p i 和指定的通道。这种并行仿真算法可以很容易的进行扩展，也很容易加入新 的模块。各个模块不需要特定的结构来并行运行，这只是一个配置的问题。 o m n e t + + 甚至还可以被用于并行模拟仿真算法的多层次描述，因为模拟器可以 在g u i 下并行运行，这种g u i 为运行过程提供了详细的反馈。 3 2 20 m n e t + + 的无线移动网络仿真 本文利用o m n e t + + 网络仿真平台中支持无线和节点移动的m o b i l i t y 硕士学位论文 第三章改进的e p i d e m i c 路由协议 f r a m e w o r k 来对移动自组网中的各种路由协议进行仿真。m o b i l i t yf r a m e w o r k 的 核心框架对节点的运动、动态链接管理和无线信道模型提供了支持，另外 m o b i l i t yf r a m e w o r k 的核心框架提供了可以扩展的基本模块。因此可以很容易的 在m o b i l i t yf r a m e w o r k 下仿真本文的路由协议。 1 创建一个新的模块 在o m n e t + + 中，模块分为简单模块与复杂模块，复杂模块是由简单模块组 成的。每一个简单模块中包含三个文件：n e d 文件、h 文件与c c 文件。例如要 在基本模块m a c 的基础上创建一个新的模块( m y m a c l a y e r ) ，m y m a c l a y e r 模块继承了m a c 模块的行为与特征。基本模块m a c 的各个文件中包含了实现 各种功能的基本框架以及为实现这些功能定义的一些参数，只需要修改和增加 m y m a c l a y e r 所需要的功能或增加一些参数，就能实现m y m a c l a y e r 所需要的 功能。另外m a c 的各个文件中以注释的形式给出了重要的提示，警告和建议， 以便更好的理解。 在m a c 的n e d 文件中已经包含了在m y m a c l a y e r 中所需要的主要的g a t e 和参数。当然可以根据需要添加g a t e 与参数。 在m y m a c l a y e r 的c c 文件中包含了实现各项功能的框架。首先需要做的事 情是寻找和替换模板中在h 文件中定义的类的名字。其中也包含了 d e f i n em o d u l e ( ) 的宏，但是如果没有使用自己所定义n e d 文件，需要所用 d e f i n em o d u l el i k e ( ) 宏代替。 2 节点的移动模型 移动节点可以在一个三维的拓扑中运动，然而实际上第三维( z 轴) 并没有 被使用。这样移动节点就总是在一个z = 0 的二维平面中运动，它的三维坐标( x ， y ，z = o ) 随着它的运动不断的调整。有两种方法引发移动节点的运动。在第一 种方法中，指定节点的起始位置和终止位置。这种位置指令通常放在一个i i l i 中； 第二种方法是使节点随机运动。不论使用何种方式使节点运动，都需要在创建移 动节点之前定义移动节点的移动范卧引。 在本文的仿真中，主要使用r a n d o mw a y p o i n t 节点运动模型。对于该模型中 的节点，开始时在仿真区域( s i m u l a t i o na r e a ) 中某位置停留一段时间( p a u s et i m e ) ， 而后节点随机选择一个特定目的位置和速度，并以该的速度向该位置匀速运动。 到达目的位置后，节点停留p a u s et i m e 长的时间，并重新随机选择目的位置和速 度继续运动。在r a n d o mw a y p o i n t 模型中，所有节点的初始位置在仿真区域内随 机分布，初始位置和节点的运动情况没有任何相关性【3 8 4 0 1 。 o m n e r 卜+ 仿真软件中没有专门运动模块，需要从o m n e t + + 的官方网站中 下载一个m o b i l i t y f w 2 0 p 3 的软件包。在本文的仿真中，使用m o b i l i t y f w 2 0 p 3 硕士学位论文 第三章改进的e p i d e m i c 路由协议 软件包中的c o n s t s p e e d m o b i l i t y 模块来实现节点的运动特性。 3 配置文件 在配置文件中，定义了稀疏移动自组网的名称、输出文件的名称，另外设 置了各类运行参数( 比如，网络运行时间、网络场景的长度和宽度、节点运动的 速度方向以及更新周期等) ，也可以为各个模块设置参数( 当然，可以在模块 的n e d 文件中设置参数的值，但在配置文件中设置，方便日后修改) 。配制文件 一般 g e n e r a l 、 c m d e n v t k e n v 和 p a r a m e t e r s - - 部分组成，每个部分包含一 些属性。 3 3 仿真分析 1 性能指标与仿真环境 仿真结果处理和协议性能评估是衡量稀疏移动自组网路由协议性能的重要 步骤。仿真完成后会生成s c a 文件，它包含有极大量的数据，根据用户的需要记 录了仿真过程中的任何一个细节。 在本文的仿真中，主要对以下性能参数进行评估【6 , 2 0 , 4 1 1 ： 1 ) 到达率( d e l i v e r yr a t e ) ：从源节点成功传送到目的节点的数据占所有仿真 数据的比率。到达率是衡量稀疏移动自组网路由协议性能最重要的指标。 到达率= 望崖篱喾嵩毫警。 公誊c s 一， 2 ) 时延( l a t e n c y ) ：数据从源节点成功传送到目的节点的时间，分别对平 均时延和最大时延进行了统计分析。和传统移动自组网不同，稀疏移动自组网路 由协议的传输时延往往较大，成为影响协议性能的一个重要“瓶颈”，是衡量协 议性能的一个非常敏感的指标。公式( 3 2 ) 中t 。表示数据产生的时间，t d 表 示数据到达目的节点的时间。 时延：i 1 乙t = n 巧一e n 气q 。 公式( 3 - 2 ) 3 ) 跳数( h o p s ) ：数据从源节点成功传送到目的节点所经过的跳数。 为了方便协议仿真和性能的评估比较，本文的无线业务模型为： 1 ) 选择5 0 个节点中的4 5 个作为数据源节点，仿真中数据总量为1 9 8 0 。 2 ) 每隔1 秒钟向网络中注入1 个数据，所以数据注入的总时间为1 9 8 0 秒。 3 ) 默认情况下，每个节点拥有可以容纳2 0 0 0 个数据的缓存，本文仿真中， 对节点的缓存大小进行了限制。 本文假定稀疏移动自组网是同构的，即网络中所有节点的通信半径一致，所 2 5 硕士学位论文 第三章改进的e p i d e m i c 路由协议 有移动节点移动模型为r a n d o mw a y p o i n t 。为了测试并评估路由协议的性能，本 文在o m n e t + + 模拟平台上构建了一个稀疏移动自组网的场景。仿真中网络环境 基本参数的选取和以往经典的移动自组网路由协议研究论文类似( 除非特别说 明) 9 1 。本文的网络场景参数如表3 1 所示。 表3 - 1 网络场景参数 参数值 仿真场景大小( m ) 仿真时间( s ) 节点数量 节点的通信半径( m ) 节点的移动速率( m s ) 发送的数据量 节点初始位置 移动场景模型 数据长度 1 0 0 0 x 1 0 0 0 2 0 0 0 s 5 0 5 0 5 1 9 8 0 随机 r a n d o mw a y p o i n t 1 k b 2 e e p i 路由协议仿真 本仿真的目的主要有两个：对e e p i 路由协议的性能进行全面评估；对资源 受限制时e e p i 路由协议的性能进行全面评估。 表3 2 资源不受限时不同无线覆盖范围下e e p i 路由协议的性能 硕士学位论文第三章改进的e p i d e m i c 路由协议 从表3 - 2 的仿真数据中可以看出，随着无线覆盖距离的减小，在保证了较高 到达率的前提下，e e p i 路由协议的平均时延和最大时延急剧增大。说明e e p i 路由协议的高到达率是在牺牲了数据传输实时性的情况下实现的。从表中数据还 可以看出，数据从源节点成功传送到目的所经过的平均跳数和最大跳数随着无线 覆盖距离的减小而增大。 为了对资源受限时e e p i 路由协议的性能进行评估比较，设定数据分组的 t t l 值最大为5 ，在缓存大小分别为2 0 0 0 、1 0 0 0 、5 0 0 、2 0 0 、1 5 0 、5 0 、2 0 、1 0 时的e e p i 路由协议进行了仿真。表3 3 是仿真结果。 从表3 3 的仿真数据中可以看出，即使在缓存大小为总数据分组的7 5 时 ( 缓存大小为1 5 0 ) ，e e p i 路由协议依然能够保持较好的性能，反映出e e p i 路 由协议能够在保证数据到达率的前提下，较少的消耗无线网络的资源。当缓存大 小为5 0 、2 0 、1 0 时，到达率出现了相当明显的下降。 3 e e p i 与e p i d e m i c 路由协议比较 本仿真的目的是对e e p i 、e p i d e m i c 路由协议在不同缓存大小值下的性能进 行全面评估。 1 0 0 8 0 长 褂6 0 艘 器4 0 瓤 2 0 o 匿面叵至函 一队、一 队 j 屋 5 0 02 0 01 5 01 0 05 02 01 0 缓存大小 图3 - 1e - e p i 与e p i d e m i c 路由协议不同缓存下的数据到达率 2 7 硕士学位论文第三章改进的e p i d e m i c 路由协议 捌 g z 较 1 弗 匡蓟豆巫 形 ，- j 皆别 江 5 0 02 0 01 5 01 0 05 02 01 0 缓存大小 图3 - 2e e p i 与e p i d e m i c 路由协议不同缓存下的平均时延 从图3 1 的仿真数据可以看出，随着无线节点缓存大小值的减小，e e p i 与 e p i d e m i c 路由协议的数据到达率降低。当节点缓存较大时，三种协议的都有较高 的数据到达率，这是因为节点缓存越大，意味着在节点“接触 过程中所交换的 数据分组越多，从而成功传送到目的节点的数据分组也越多。当缓存大小为5 0 、 2 0 、1 0 时，两种协议的数据到达率下降得较快。e e p i 路由协议在缓存大小为 1 0 时，数据达到率还能达到7 0 左右，而e p i d e m i c 路由协议只有4 0 左右。这 是因为e e p i 路由协议减少了无用分组占用缓存的概率。通过以上分析可知，在 较低缓存下，使用e e p i 路由协议的性能较好。 从图3 2 的仿真数据可以看出，随着无线节点缓存大小值的减小，e e p i 与 e p i d e m i c 路由协议的平均时延增加。从图中可以看出，e e p i 与e p i d e m i c 协议相 同缓存下的平均时延基本上差不多，这是因为e e p i 没有从本质上改变e p i d e m i c 路由协议的实现方式，数据分组仍然以“存储转发的方式在全网范围内广播。 3 4 本章小结 在本章中，首先针对e p i d e m i c 路由协议中存在的无效通信过程与到达目的 节点的数据分组继续在网络中存在并扩散等不足，提出了一个改进路由协议 e e p i 。接着介绍了o m n e t + + 网络仿真软件，在分析了性能指标之后，首先对 e e p i 协议在资源不受限与资源受限条件下的性能进行了对分析，接着对e e p i 与e p i d e m i c 路由协议在不同缓存下的性能进行了仿真。结果表明，e e p i 路由协 o o o o o 0 o o o o o 加均坞坞惦m心挖u m 硕士学位论文 第三章改进的e p i d e m i c 路由协议 议能够在保证数据到达率的前提下，减少网络资源的消耗。在下一阶段工作中， 将考虑在节点比较密集的稀疏移动自组网网络环境中的路由协议。 硕士学位论文第四章基于邻居信息的混合式路由协议研究 第四章基于邻居信息的混合式路由协议研究 现有的大部分稀疏移动自组网无基站路由协议是基于广播的，第三章提出的 e e p i 路由协议适用于节点分布比较稀疏的网络环境，当节点分布比较密集时， 源节点与目的节点位于同一连通域的概率变大，路由协议的性能不佳。为此，本 章提出了n c r e p i d e m i c 混合式路由协议，该协议在同一连通域内利用节点的邻 居信息寻找稳定路径，在连通域间利用e e p i 路由协议实现数据的传输。 4 1 邻居信息 邻居信息是一个无线网络节点有多少个邻居节点以及哪些节点是其邻居节 点的信息。在移动自组网中，很多研究领域都用到邻居信息，如拓扑控制、路由 协议，广播协议等，在这些研究领域中邻居信息都是至关重要的。在拓扑控制中， 节点根据邻居信息调整自身的传输功率，保持合适的邻居个数，以此获取良好的 网络连通性并有效的降低网络能量开销以及降低网络干扰。对于路由协议来说， 几乎所有主动路由协议( p r o a c t i v er o u t i n ga l g o r i t h m s ，路由前计算路由) 以及部 分被动路由协议( r e a c t i v er o u t i n ga l g o r i t h m s ，路由时进行计算) 都依赖于邻居信 息以发现路由并检测路由状态。在消息广播中，邻居信息通常被用于建立最小生 成树以便进行高效的广播【4 2 1 。 在移动自组网中，为了获取邻居信息，每个节点通常需要周期性的向它的一 跳邻居节点广播h e l l o 分组。通过这种方式，每个节点可以周期性的从邻居节点 收到h e l l o 分组的应答信息，从而获取最新的邻居信息。尽管这种周期性的广播 并非任何上层算法( 如拓扑控制算法、路由算法等) 中必须执行的步骤，然而节 点的邻居信息却是这些算法执行的依据。因此，为了获取邻居信息，绝大部分网 络都必须执行这种广播，从而这也成为网络资源开销的一个重要方面。所以，如 何降低这种能耗并确保邻居信息的准确性、及时性就具有了非常重要的现实意 义。 4 1 1 邻居信息发现方法分类 邻居发现一个典型的实现是利用固定周期的广播模式，称之为f p s n d ( f i x e d p e r i o ds c h e m ef o rn e i g h b o rd i s c o v e r y ) 。然而，f p s n d 有其内在的缺陷，并且这 种缺陷主要来自于它固定的周期设置。在f p s n d 中，两个参数，即发送h e l l o 分组的周期以及邻居过期时长( 节点邻居信息表中的邻居节点在多长时间内，如 3 0 硕士学位论文第四章基于邻居信息的混合式路由协议研究 果没有收到该邻居节点的h e l l o 分组的应答消息，就认为其已经不在本节点的通 信范围之内) ，在很大程度上影响到邻居发现的准确性。然而，恰恰是这两个参 数却很难被确定。对f p s n d 来说，一个较长的h e l l o 周期意味着节点可能无法 快速及时的发现新到达的邻居，而一个较短的周期意味着将有可能导致不必要的 h e l l o 分组，从而浪费节点能量与网络带宽。与h e l l o 周期类似，不合理的设置 邻居过期时长将导致不准确的邻居信息。事实上，这两个参数至少应是节点传输 半径与节点动态分布的函数，而后者又会受到节点移动的影响。因此，这两个参 数应随着网络状态的变化而变化，静态的预先设置在移动自组网中通常会导致信 息的不准确或者网络能量的浪费。这在非均匀分布网络或混合网络移动模式下 ( 网络中节点按照不同的移动模式，如r a n d o mw a y p o i n t ( r w p ) 、r e f e r e n c e p o i n t g r o u pm o b i l i t y ( r p g m ) 等模式移动) 尤其明显。在这种情况下，一个静态的 设置不可能同时适用于两种或多种网络模式。因此如何动态的设置h e l l o 周期以 及邻居过期时长成为一个关键性问题【4 2 1 。 关于邻居发现方面的研究大致可以分为两类【4 2 】： 第一类将邻居的发现过程分为几个时间段，在每个时间段中节点处于不同的 状态，并且不同状态的能耗也是不同的。这一类的研究主要集中在如何合理安排 不同状态的时长，以最小的能耗快速的获取邻居信息：第二类研究忽略了上述提 到的节点状态，而主要关注节点应在何时发送h e l l o 消息，如何利用其它信息来 提高邻居发现的准确率并降低能量开销等。 第一类的重要例子包括【4 3 】和 4 4 。在文献 4 3 中，作者提出了一组协议，称 为“b i r t h d a yp r o t o c o l s 。在协议中，每个固定的时长被分割为相等的n 个s l o t ， 当任意一个s l o t 到达时，每个节点以不同的概率进入以下几个状态之一，即传输 状态、监听状态或低能耗状态。这样，在任意一个s l o t 中，对于一组互为邻居的 节点，若是一个节点在传输消息，而其余一到多个节点在监听，则这些监听者将 获取发送节点的邻居信息。合理的分配进入不同状态的概率，即能使得每个节点 获取准确的邻居信息。文献【4 4 介绍的邻居发现过程同样包括三个状态，即 i n q u i r y ，i n q u i r ys c a n 以及d o z e 状态。作者分析了在限制能耗情况下要求最大化 响应速度时，以及给定响应速度情况下要求最小化能耗时，节点处于三个状态的 平均时长。文献【4 6 基于马尔科夫模型，提供了一个分析框架，用于估计在限制 最大能耗情况下邻居能被成功发现的最大概率。 在第二大类中，所有的邻居发现方法都基于固定的h e l l o 周期，也即都是 f p s n d 。文献 4 5 提出了t b r p f ( t o p o l o g yd i s s e m i n a t i o nb a s e do nr e v e r s e p a t h f o r w a r d i n g ) 的邻居发现方法( t n d ) 。在t n d 中，h e l l o 分组仅仅包含那些一 跳邻居中链路状态发生变化的邻居信息，以此尽可能减小h e l l o 分组的大小。文 硕十学位论文第四章基于邻居信息的混合式路由协议研究 献 4 6 提出了邻居交换协议n x p ( n e i g h b o re x c h a n g ep r o t o c 0 1 ) 。n x p 采用两种 不同的分组，即h e l l o 分组包含完全的一跳邻居信息，而k e e p a l i v e 分组只包含 一个消息序列号。不像t n d 那样h e l l o 分组必须定时的发送，在n x p 中，只要 m a c 层最近有用户数据发送，并且网络中没有特殊事件要求发送h e l l o 分组， n x p 将不发送协议分组。注意，n x p 利用了用户数据，但它并没有超出固定间 隔发送消息的范畴。与n x p 类似，文献 4 7 提出了节点可以通过获取h e l l o 分组 和f l o o d e d 分组包获取邻居信息。 4 1 2 邻居信息发现方法原理 1 基本原理 在文献 4 2 中，假设每个节点的移动速度随机分布于 o ，v 】。因此，对于任意 一对节点，它们的相对速度w 分布于 o ，2 v 。同时，在时间间隔t 内，两个节点 的相对移动距离d = w x t 不可能超过2 v t ，也即 d = w f 2 所公式( 4 1 ) 如果移动节点a 的传输半径为r ，在t o 时刻，它最远的邻居b 离开a 的距 离为r ，则节点b 能够离开a 的传输区域的最小时长t 可以表示为【4 2 】 f ：r - r 公式( 4 - 2 4 - 2 )f = 公氏l j 2 矿 其中，v 是a 和b 的最大速率。因此，为了使得最远节点b 能够及时检测 到节点a 和b 的链路是否断裂，节点a 可以在时刻t 0 + t 后发送一个h e l l o 分组。 但是，在时刻t 0 + t 前的发送任何h e l l o 分组都是不必要的，因为t 0 时刻，b 是a 最远的邻居，在时刻t o + t ，只有节点b 有可能离开a 的辐射范围。因此，对于 节点a ，何时发送h e l l o 分组可以根据传输半径r 以及邻居节点的布局来决定。 然而，以下几个方面需要引起注意【4 2 j ： 首先，如果节点a 具有两个或多个邻居，并且它们离开a 的距离大致相等， 此时，为每个邻居发送一次h e l l o 分组对节点a 来说能量开销较大，也是比较浪 费的。因此，对于多个距离相近的邻居可以充分利用同二个h e l l o 分组。 其次，由于移动场景中，两个节点按照相反方向同时以最大速率移动的概率 事实上是非常低的，因此上面讨论的方法实际上过于严格。较低的估计节点之间 的相对速度将会增长h e l l o 间隔t ，从而减少h e l l o 分组的发送。所以，应该从概 率的角度设置相对速度w ，而不应采用2 v 。 第三个方面是关于如何设置邻居过期时长。正如上文已经说明的，该参数的 设置直接影响邻居发现的结果，也是非常重要的。该参数的设置与h e l l o 间隔t 3 2 硕士学位论文第四章基于邻居信息的混合式路由协议研究 关系密切。 最后一个方面是如何发现新到达的邻居。本文讨论的基本原理主要涉及如何 有效的检测链路的断裂。 在基本原理的讨论中，用2 v 估计h e l l o 间隔t 。但正如已经说明的，在绝大 多数情况下，节点之间的相对速率远远小于2 v 。因此，把v 看作节点之间相对 速率的均值，并用它替代公式( 4 2 ) 中的2 v 。通过这种方式，事实上是将节点 之间相对速率的随机性体现在了估算中。值得注意的是，平均来说，这种替代将 h e l l o 分组减少了一半，同时邻居发现的准确度却并不会受到很大影响。这是因 为从统计来看，节点之间的相对速率主要分布在 o ，v 】。文献 4 2 中，h e l l o 间隔 的计算如公式( 4 3 ) 所示。 尺一厂 21 厂 2 新到达邻居的发现 当节点b 进入节点a 的通信范围， 公式( 4 3 ) a 能通过两种途径发现邻居节点b 。首 先，b 广播h e l l o 分组到其邻居节点，而该分组被a 收到。这样，a 可以发现它 有一新邻居b ；其次，a 广播h e l l o 分组到其邻居节点，当该分组被b 收到时， b 发现a 是它的新邻居节点，因此立即回复h e l l o 分组应答分组。所有节点接收 到h e l l o 分组应答分组时，将该分组当作普通h e l l o 分组处理，但是不用再做任 何的回复。这样，当a 收到b 的h e l l o 分组应答分组后，a 明确它有了一个新邻 居b 。 上述的第一个发现机会由新到达的节点b 触发。注意每个节点至少每隔t 发送一个h e l l o 或者h e l l o 应答分组，因此，新邻居被发现所需的最长时间不超 过t 。而当新到达的节点，如b 的外围有邻居时，由于b 的h e l l o 消息使得这个 发现过程被大大缩短。另一方面，由a 触发的发现过程也将很大程度上缩短b 被发现的时延。文献 4 2 】中，使用的是第二种发现途径。 4 1 3 邻居信息发现方法实现 文献【4 2 中，定义两个分组，即h e l l o 与h e l l or e p l y 。两个分组都仅包含一 个序列号，消息的类型通过序列号的正负区别。小于0 的序列号表示该消息为 h e l l or e p l y ，序列号的绝对值表示消息在发送节点中的顺序。 硕士学位论文第四章基于邻居信息的混合式路由协议研究 分组的标识符 邻居节点所处的区域 什么时间该节点被认为不可达 h e l l or e p l y 分组中序列号的绝对值 每个节点维护一张邻居信息表，用于保存邻居信息。在文献 4 2 的网络模型 中，每个节点具有相同的传输半径，因而具有相同的区域划分。对于同一个区域， 不同的节点定义相同的t o 。每个节点需要两个事件，称为h e l l o t i m e r 和 n e i g h b o r t i m e r 。n e i g h b o r t i m e r 每次运行时( 定时周期应小于等于t o ) ，遍历整个 邻居信息表，查看是否某个记录的e x p i r a t i o n 小于当前时间，若是，则删除该记 录，因为这意味着该记录对应的邻居节点过期了，被认为是不可达的。当遍历完 整个表格后，n e i g h b o r t i m e r 可以获得现有邻居节点中最外围邻居所处的区域。 为了减少h e l l o 分组的广播，n e i g h b o r t i m e r 仅当处于以下情况之一时才发 送分组。第一种情况当前事件序列中没有分组，并且上次的发送时间与当前的安 排时间之间至少间隔t o 秒；第二种情况当前有一个需发送的分组，但是该分组的 时间是在当前的安排时间之后至少t o 秒。注意在第二情况下，已有的安排将被取 消，这是因为新老安排之间的间隔大于t o ，n e i g h b o r t i m e r 定时器将在原有安排 的分组被发送前再次运行。这两个条件意味着在t o 时间间隔内不会有两次分组的 发送。当节点接收到h e l l o 分组时，它首先检查是否发送者在它的邻居信息表中。 如在，它将比较表中的s e qn u m b e r 和分组中的s e qn u m b e r 。如果分组中的序列 号更大，并重新填写表中的l o c a t i o n ，e x p i r a t i o n 以及s e qn u m b e r 。如果h e l l o 分组来自于新邻居，则该节点需要计算相关值并在表格中插入新的记录，然后马 上广播h e l l o 应答分组。当节点接收到h e l l o 应答分组，即使它来自于新邻居， 也不必回复。 以上是对移动自组网中邻居信息的一些研究。在本文中，收集邻居信息的方 法属于邻居发现方法的第二大类。本文对邻居信息发现方法进行了一些修改，在 网络模型中，节点的移动速度是匀速的，设置为5 m s ，h e l l o 分组的格式、邻居 信息表的设置等与文献 4 2 的不一致。下面首先介绍一下在混合式路由协议中用 到的邻居信息( 邻居变化率) 收集、计算方法。 4 1 4 邻居变化率 文献 4 8 1 中假设移动区域内随机分布n 个节点，每个节点具有唯一标识，节 一 t t 堋 t m m 讹 m m 兰 硕士学位论文第四章基于邻居信息的混合式路由协议研究 点间通过无线多跳方式组网通信。移动自组网的t 时刻拓扑图可用有向图 g ( t ) = “e ( t ) 表示，其中：v = 1 ，2 ，n ) 表示节点集合；e ( t ) = e l ，e 2 ，e m ) 表示 t 时刻无线链路集合。如果节点i 可以感知到节点j 发送的信号，则节点i j 之间 存在有向边e ( i j ) ，节点j 是节点i 的邻居。节点i 的所有邻居节点构成节点i 的 邻居集。 节点i 的邻居变化率定义如下：设t 1 时刻节点i 的邻居集为s it 1 ，t 2 时刻 邻居集为s it 2 ，t 2 t l = t ，则 n c r f ：翌：! ! q 翌：! 兰 s it l us t 2 公式( 4 - 4 ) n c r j 反映了与节点i 相关的无线链路的通断变化。n c r i 越大，表明节点i 局部 拓扑越稳定；n c r i 越小，表明节点i 局部拓扑变化越剧烈。在节点i 移动且周围 节点静止、节点i 静止且周围节点移动的极端情况下，n c r i 值都比较小。 文献 4 8 】中节点通过周期性广播h e l l o 分组获得局部拓扑连接信息，从中提 取节点的邻居变化率n c r i 。文献 4 9 指出：i e e e 8 0 2 1 1 m a c 协议的一跳单播分 组投递率为9 9 8 ；一跳广播分组投递率仅为9 2 6 。因此，设计节点邻居变化 率检测机制时，应考虑m a c 层不可靠广播分组传输的影响。具体机制包括【4 8 j ： 1 局部拓扑连接获取：每隔h e l l o 周期( h e l l oi n t e r v a l ) ，节点检查上个h e l l o 周期是否发送过广播分组。如果没有发送，则广播一个t t l = 1 的h e l l o 分组。 节点通过收听邻居节点发送的广播分组检测局部拓扑连接，维护邻居集。如果 在过去的a l l o wh e l l o * h e l l oi n t e r v a l 内，节点没有收到某个邻居的任何广播分组 ( 包括h e l l o 分组) ，节点认为与该邻居连接已经中断，把该节点从邻居信息表 中删除。 2 节点邻居变化率计算：修正邻居变化率的邻居集统计方法，通过延长邻 居集观察周期，减小h e l l o 广播分组m a c 层不可靠传输对邻居变化率的影响。 设s it l 为 t l - a l l o wh e l l o * t , t 1 时间段内所有出现过的邻居节点，s it 2 为【t 2 - a l l o wh e l l o * t , t 2 时间段内所有出现过的邻居节点，t 2 - t l = t ，t = h e l l oi n t e r v a l 。 n c r i 计算如公式( 4 4 ) 。m a c 层广播分组的不可靠传输和节点移动是h e l l o 分组丢失的两个主要原因。上述原因直接影响a l l o wh e l l o 参数设置，进而影响 节点邻居变化率计算值和路由性能。如果a l l o wh e l l o 参数设置得太小，将无法 减小m a c 层广播消息不可靠传输的影响；如果a l l o wh e l l o 参数设置得太大， 则又无法及时反映因节点移动导致节点局部拓扑的变化。文献 4 8 】采用仿真方 法，通过比对不同a l l o wh e l l o 参数值对应的路由性能来确定最佳a l l o wh e l l o 参 数值。当a l l o wh e l l o = 3 时，路由性能最优。 3 5 硕士学位论文第四章基于邻居信息的混合式路由协议研究 4 2n c r - e pid e mic 混合式路由协议 4 2 1 混合式协议的提出 稀疏移动自组网的应用领域还在不断的发展中，在许多新的应用领域中，现 有路由协议不能很好的工作。 1 e e p i 路由协议没有从本质上改变e p i d e m i c 协议的实现方式，数据仍然 以类似于病毒的“接触一传染 方式在整个网络中传播，因此对协议性能的提 升和对网络负担的减轻是比较有限的。 2 应用环境方面：传统的稀疏移动自组网路由协议中总是假定数据发送方 在任何时候对网络中其它节点的信息都知之甚少，不知道接收方的当前位置和 应该如何选路；假定源节点与目的节点之间总不存在通路。但是在某些应用环 境中，网络虽然分为不同的连通域，但在连通域内数据通信的几率比较大。传 统的稀疏移动自组网路由协议在这些应用场景中不能很好的工作。 3 邻居信息方面：稀疏移动自组网中基于上文消息的路由协议，利用的邻 居信息是某一时刻的节点密度，没有很好的比较不同时刻节点密度的差异，不 能很准确的寻找稳定路径。而在稀疏移动自组网中，由于整个网络划分为不同 的连通域，数据传输时延大，因此为位于同一连通域的源节点与目的节点寻找 一条稳定路径能减少因为路径中断而产生的传输时延。在n c r - a o d v 路由协议 中