相遇信息估算概率的机会网络路由协议

0 引言

机会网络是一种不需要在源节点和目标节点之间存在完整路径,利用节点移动带来的相遇机会实现通信的，具有时延和分裂可容忍的自组织网络。它是移动自组织网络的一种演化，其概念源于早期的延迟容忍网络(delay tolerant net⁃work，简称 DTN)，是延迟容忍网络的一个分支。机会网络中，节点之间不存在完整的路径，节点的通信机会是间断的，网络中通过存储-携带-转发模式传输信息实现节点间的通信，因此机会网络能在网络链路断开和分裂的情况下完成通信任务。这些特性，使得机会网络能满足恶劣条件下的通信需要，能应用于缺乏通信基础设施、网络环境恶劣的场景。比如，野生动物监控，偏远地区网络连接等。

1 相关研究

在机会网络中，由于节点移动不可预测、能量和存储受限等因素导致网络拓扑出现割裂，使源和目标节点位于不同的连通域，导致传统网路由协议无法有效运行，因此设计高效的路由转发协议成为机会网络中关键和研究的热点之一。近几年来，国内外研究人员提出了较多的路由协议，其中较经典的如传染转发(epidemic forward⁃ing)、Spray and wait、PROPHET。文献[6]根据转发策略的不同将目前的机会网络路由协议主要分为 4 类:基于冗余机制、基于效用机制、冗余效用混合机制和基于主动运动机制。

1.1 Epidemic Forwarding

传染转发通过洪泛的方式将消息转发给所有相遇的节点，以期望能有更多的节点参与消息的转发，最终以较高的成功传达率到达目的节点。其主要思想是2个相遇的节点交换对方没有的信息,节点将消息副本传递给它所遇到的节点。该协议中由于洪泛而使网络中存在大量的消息副本数，会大量消耗网络的资源，且扩展性差。

1.2 Spray and wait

Spray and wait 协议(以下简称SW)是一种基于受限洪泛的路由协议。该协议分为喷射(Spray)阶段和等待(Wait)阶段。在Spray阶段，源节点使用交换机制将部分报文扩散到邻居节点;Wait 阶段，若 Spray 阶段没有发现目的节点，那么包含报文的节点通过直接传输(direct deliv⁃ery)方式把报文传送到目的节点。该协议提供了 2 种转发策略，Binary 模式和非 Binary 模式。在Binary模式下k=L/2(L为消息的副本数)，即将一半的副本数交由中继节点转发。当携带数据包的节点中的转发副本数降为 1 时，节点转到Wait阶段，在此阶段下，节点采用和直接传输协议相同的策略等待与目标节点的相遇机会。

2 相遇信息估算概率的路由协议

在PROPHET和SW协议的基础上，本文提出一种基于相遇信息的路由协议 BPAS(based onprophet and spray and wait)，以节点间的相遇频率、网络连接时间和断连时间作为依据，计算节点的转发概率，将消息由概率值低的节点向概率值高的节点转发，并采用类似于SW中Binary模式(以下简称BSW)的消息复制方式作为转发策略，实现消息的多路径传输。

2.1 转发概率的计算

BPAS协议根据节点的转发概率表示相遇节点间消息转发的可达性，概率值越大，表明消息在节点间传输成功的可能性越大，概率值大的节点其接收消息的成功概率越大，将消息送达目的节点的机会相比要多于概率值低的节点。

2.1.1转发概率的计算

每个节点A记录与节点B在设定时间T内相遇的次数Count(a,b)、每次连接时间长度UT(a,b)和每次断开连接的时间长度DT(a,b)，计算它们的相遇频率，平均网络连接时间和平均断连时间，利用以上计算所得的三个值，通过公式(1)计算出节点到其他节点的转发概率值。

3 仿真和结果分析

3.1 仿真环境设置

为了评估BPAS协议的性能，本文使用机会网络模拟平台 the ONE[10]为仿真平台，并将BPAS与 Epidemic 、Prophet 和 SW 进行性能上的比较。选取的性能指标为：传输成功率(deliveryprobability)，通信开销率(overhead ratio)以及消息转发次数(relayed)。消息传输成功率为成功交付的消息数目与原始消息数目的比值;通信开销率的计算方法定义为：(消息复制总数-成功交付的消息数目)(/成功交付的消息数目);消息转发次数为网络中所有消息总共转发次数。

3.2 仿真性能对比

仿真实验测试了几种路由协议在不同节点密度下的传输成功率，它的计算方法为到达目标节点的数据包数量与源节点产生的数据包数量的比值。

消息传输成功率随着节点密度的增大而提高，从图1可以看出，BPAS的传输成功率要远大于Prophet协议和Epidemic协议，也要优于SW协议，这是因为相对于SW的盲目转发，BPAS协议在消息转发时总是沿着转发概率大的节点接近目标，所以有较高的消息传达率。随着节点的不断增多，Epidemic和Prophet协议中消息副本数增多，导致网络资源消耗过大，消息传输成功率随之降低;而BPAS协议中，节点增多，密度增大，在单位时间内，节点相遇的频率会增加，会使转发概率大的节点随之增多，因此消息的传输成功率也在逐渐增大。

4 结束语

本文提出了BPAS路由协议,是在prophet协议和spray and wait协议的基础上提出来的，是根据节点间的相遇频率、平均相遇的连通时长、平均断连时长作为参量计算选择下一跳转发节点的概率路由协议。仿真实验清楚地显示BPAS协议比 Epidemic、PROPHET 和 Spray and wait 协议具有更好的传输成功率，网络通信开销更低，消息总的转发次数更低。实验显示，随着节点的增多，BPAS协议中消息的传输成功率增多的幅度远大于通信开销率和消息总转发次数的幅度，说明该协议适用于节点密度较大的机会网络环境。