机会网络中基于最短路径的路由协议的稳定性研究

王菲，吴比，姜胜明

（上海海事大学信息工程学院，上海 201306）

0 引言

机会网络（OppNets,Opportunistic Networks）是一种特殊的移动自组织网络[1]，其源于移动自组织网络（MANETs）[2]与延迟容忍网络（DTN）[3]。但与移动自组织网络不同的是，机会网络不要求源节点与目的节点存在完整的端到端的链路，而是通过节点移动带来的相遇实现信息的传送。即在整个过程中节点通过“存储-携带-转发”[4]方式进行通信。

机会网络虽然能实现极端环境下不存在端到端链路的通信，但是与传统的通信相比，机会网络存在着低传输成功率、低安全性、高路由开销以及高传输时延等缺点,为了解决低传输成功率以及高传输时延的问题。一种基于洪泛的传染病路由协议[5]应用于机会网络。该协议能充分利用节点相遇带来的机会性，解决高传输率等问题，然而由于过渡的洪泛使得网络中的消息冗余过多，网络资源消耗过大。甚至会产生数据安全隐患。

现有的研究要不强调传输的成功率，要不减少网络的资源消耗。但是在既保证传输成功率又能降低网络开销获得很好的进展；其次节点的稀疏，移动性将如何影响网络的收包率及稳定性并没有被研究。

本文通过对上述问题的分析，首先，提出了在保证传输成功率的前提下降低了网络开销的路由协议，本文把该协议命名为EPIDEMIC；其次，将该协议在EX⁃ata仿真平台上编程实现；最后，在仿真平台上通过改变节点的密度以及节点的移动速度来模拟机会网络，并探究在不同的节点密度与移动速度的环境下该协议与无线自组织网络协议DSR的收包率以及稳定性情况。

1 相关工作

目前，基于机会网络的研究，主要有以下典型的路由协议。

Direct Delivery[6]路由协议，该协议是基于转发策略的协议，是一种最为简单直接的路由协议，只有当目的节点在源节点的辐射范围之内，数据分组才会被交付。该算法的特点是无路由开销，但是对于机会网络而言，由于源节点与目的节点之间不存在固定的链路，源节点要经过很长时间才能把数据交付，因此，该协议的传输率较低。

EPIDEMIC[7]路由协议也是基于转发的路由协议。该协议有点类似于传染病，在该路由协议下，节点会抓住每次相遇的机会。相遇的两个节点会互相传递它们的没有数据分组。可想而知，经过一段时间后网络中将存在大量的数据分组节点的缓存空间也会被大量地占用。虽然该协议能实现最大化的数据交换成功率，但是网络开销过大，信息的利用率较低。

Spray and Wait[8]路由协议是Direct Delivery路由协议的基础上进行了该进。该协议分为两个阶段Spray和Wait阶段。Spray阶段：源节点为其每个数据分组生成L个数据分组副本，这些数据分组通过“喷洒”的方式传递给邻居节点，每个邻居节点在收到该分组后再进行数据的传递，重复上面的过程，此方法有点类似于Epidemic路由协议。Wait阶段：假如在Spray阶段数据分组没有到达目的节点，那存储了数据分组的节点只能采用Direct Delivery方式进行消息的交付。该算法缩短了消息的传播时间，但是网络开销同样很大。

DSR路由协议主要特征是在消息发送之前，源节点已经知道到达目的节点路径。为了节省路由发现的开销，每个节点都拥有一个路由缓存区。机会网络中路径一般是不存在的，当源节点发送消息时，而目的节点不在其路由表内，便要开启路由发现机制，动态地寻找一条路径。DSR只采用源路由和路由缓冲区，而不需要专门的环路检测机制，同时每个节点在在路由发现过程中已经建立自己的路由缓冲区。

通过相关工作的分析及研究，本文将设计一种能灵活应用于机会网络，并且能改善相关工作遗留下的问题。最后将该协议与DSR路由协议进行比较。

2 机会网络中最快路径协议设计

2.1 协议的基本思想

在机会网络中，消息的传递需要依靠节点的移动来完成，所以要充分地抓住节点相遇的机会来传递消息。

如图1所示，以节点2作为源节点，节点7作为目的节点。寻找一条从节点2到节7的最快路径，首先，节点2通过洪泛的方式向周围节点发送消息（p21代表节点2向节点1发送的消息），节点1与节点4最先收到消息，然后又以同样的方式广播出去。但是需遵循以下几点:

①反方向不接受消息（节点2向节点1发送消息，对于同样的消息节点1向节点2发送时，节点2不接收）。

②节点只接受和记录最先到达的消息（节点4只接收了节点2发来的消息而节点1转发来的同种消息节点4是不接收的。

通过这种方式能找到一种最快的方式到达目的节点。

图1 协议的基本思想

2.2 协议的具体实现过程

（1）数据包的发送

数据包的格式如图2所示，其携带的信息包括源地址、目的地址、消息号、消息类型、生存期。

图2 数据包格式

①源地址与目的地址各占2个字节。

②消息号占4个字节，每个节点按序增加数据包的序号，用于表示是第几个数据。

③消息类型0代表数据包，非0代表确认包。

源节点在发送数据包时首先先给要发送的数据包进行标号，然后通过洪泛的方式将数据包发送出去。邻居节点收到该数据包时，首先，通过查找消息号来判断该数据包有没被接收过，假如该数据包接收过就拒绝接收。假如没有接收过，就立马把该消息广播出去。通过这种方式将消息发送给目的节点。

（2）确认包的发送

确认包分为两个类型。一种是由目的节点发送的确认包ACK，另一种是由非目的节点发送的确认包NULL_ACK，两者在结构上是一致的，不同在于消息类型。其结构如图3所示。

图3 确认包的格式

①源地址与目的地址：应答包的源地址与目的地址分别取当前节点的地址和数据包的地址。

②消息号：节点每收到一个探测包消息号就+1。

③消息类型：1代表连通应打包，2代表非连通应打包。

④确认号：取对应探测包的消息号。例如，探测包的消息号为2，那么确认包的确认号就为2。

当目的节点收到数据包时，就会判断是不是第一次收到该数据包，假如是第一次收到该数据包就发送一个连通的确认包，确认包的消息号+1，确认号为该数据包的标号，假如目的节点不是第一次收到该数据包，就不回复确认包。由于机会网络中链路存在多变性与间歇性，所以消息不一定能发送到目的节点。当中间节点收到数据包时，就会开启侦听模式，假如在时间T内该数据包没有被转发（时间T的取值是发送数据包的间隔），就会向源节点发送一个非连通确认包。

3 协议的收包率与稳定性比较

3.1 仿真环境

（1）仿真工具

本文采用了EXata仿真平台，该平台网络层次划分清楚并且提供了可视化的界面来搭建仿真场景。

（2）参数设置

机会网络的收包率与稳定性与节点的密度，移动速度密不可分。考虑到这点原因，本文的移动模型均采用随机停留点移动模型RWP（Random WayPoint）,如表1所示。其中，为了模拟真实场景，停留时间设置为0妙，节点的速度区间为0-100m/s，节点的移动精度为1m。

如表2所示，为节点的物理层设计，下列的值均为默认值，传输功率，接收灵敏度决定了节点的传输距离。

表1 移动模型设置

表2 物理层设置（取自EXata物理层参数设置）

为了使对比结果具有说服性，我们对包的大小、发包的频率及时间也有要求。包的大小为512bit，发包的时间间隔为3.9ms,发包起始时间为1s，结束时间为30s.这样能保证网络的带宽达到1MB。根据这个发包的数量是7346个。表3是CRB的设置。

表3 CBR参数设置

（3）场景设置

实验中分别在1500m×1500m的平面内放了2-15个节点共14个场景。并且在每个场景下节点的移动速度从0m/s增长到100m/s，区间为5m/s。共21种情况。仿真时长均为30s。为了避免冗余，本文只去了一张仿真场景图。如图4所示，所有的场景都是以1为源节点，2为目的节点。

图4 10个节点场景图（取自EXata场景图）

3.2 仿真分析

（1）节点密度与收包数、收包稳定性的关系

图5，横轴为节点的数目，纵轴为在节点数一定的情况下不同的移动模型下收到的数据包的平均值。（例如，节点数目为5的场景下，分别测出速度为0m/s、5m/s、10m/s...100m/s目的节点收包的数目，在把这些收到的数据包个数加起来做平均值。）

图5 节点密度与收到数据包平均值的关系图

通过实验可以发现，节点密度越高，收到的数据包会增多，不过节点密度对DSR路由协议的影响会很大。总体来说，EPIDEMIC路由协议的收到的数据包比DSR协议多。

图6所示，横轴为节点个数，纵轴为在节点数一定的情况下不同的速度移动的模型下收到数据包的方差。

由图可知，DSR在节点少的时候方差较小，稳定性不错，但当节点多了稳定性就差了。而EPIDEMIC方差一直很稳定，随着节点的增加方差在减少，稳定性在增加。

（2）节点的移动速度与收包数、收包稳定性的关系如图7所示，横轴为节点的移动速度，纵轴为在速度一定的情况下在不同的节点密度收到的数据包的平均值。（例如，速度为60m/s，分别把该速度下的节点为2-15所收到的数据包求平均值。）

图6 节点密度与收到数据包的方差关系图

图7 节点移速与收到数据包平均值关系图

从图中可以发现DSR收到的数据包呈现一种波状图，而且当速度增加时，收到的数据包反而在减少，而EPIDEMIC随着节点速度的增长，收到的数据包越来越多。

如图8所示，横轴为节点的移动速度，纵轴为在速度一定的情况下不同的节点密度下收到数据包的方差。

图8 节点移速与收到数据包的方差关系图

由图可知EPIDEMIC的稳定性比DSR的稳定性好。随着速度的增长EPIDEMIC的方差几乎达到0。

（3）低节点密度、高节点移动速度与收包数，收包稳定性的关系

我们为了使机会网络特性更加明显，选取了节点数为2-10，节点的移动速度为60m/s-100m/s的那部分实验数据。分别重复了以上的数据处理方法。

由图9可知，EPIDEMIC的收到的数据包明显多于DSR收到的数据包个数，但是随着节点数的增加，收到的数据包个数没有明显增加。

由图10所示，EPIDEMIC收到数据包的方差明显小于DSR路由协议。说明在节点数较少的情况下EP⁃IDEMIC路由协议比DSR路由协议稳定。

由图11所示，在移动速度较高的情况下，EPI⁃DEMIC收到的数据包多余DSR，随着速度的增加，EPI⁃DEMIC收到的数据包较多。

由图12所示，在较高移动速度下，EPIDEMIC路由算法的稳定性较好，而DSR路由算法方差呈现一种波形，说明稳定性较差。

4 结语

本文主要对机会网络中自编协议与无线自组织网络DSR路由协议在收包数和收包稳定性两方面进行比较，发现自编协议能更好地适应机会网络中节点密度稀少，节点移动频繁的情况。而DSR协议对节点密度有较高的要求，而且在节点密度较高的情况下，随着速度的增长，DSR收到数据包的量反而在减少。总体而言，自编协议在保持较高收包数的同时，而且能保持信息在网络中稳定的传输。

图9 节点个数与收到数据包的平均值关系图

图10 节点密度与收到数据包方差关系图

图11 节点移速与收到数据包平均值的关系图

图12 节点移速与收到数据包的方差关系图