简 磊，龙建忠，杨雪梅

（1.四川大学锦江学院，四川 眉山 620860；2.四川大学 电子信息学院，四川 成都 610065）

0 引 言

机会网络作为容延迟网络的特例，依据节点间间歇性相遇传输消息[1]。由于节点间的间歇性相遇，实时建立从源节点至目的节点的直接路径是不切实际的，因此，机会网络常利用存储-携带-转发方式，并通过多跳路由传输消息。通常，节点先将消息存储于缓存区直到与目的节点相遇，然后再将消息转发[2]。

目前，研究人员已提出不同的机会路由。这些机会路由可划分为基于泛洪和基于效用的机会路由。文献[3]提出的PRoPHET协议属于后者。PRoPHET协议利用传递概率转发消息，而传递概率由相遇概率决定。

而基于泛洪机会路由并没有有差异性地对待每个相遇节点，只要相遇，就转发消息。基于泛洪机会路由可分为基于控制和无控制复制两类。文献[4]提出的Epidemic协议就是基于简单的贪婪复制协议，一旦相遇节点，就转发消息。当节点的缓存区域无限制时，Epidemic协议具有高的性能。此外，无限制的复制也会导致高的开销。为了解决消息开销和节点资源受限问题，研究人员提出多个控制复制协议，如Spray and Wait协议（SNW）[5]。SNW协议了解开销的问题，但仍然存在长时延问题。文献[6]提出Spray and Focus协议（SNF），其考虑了相遇时间，并通过跳数控制消息复制次数。

此外，研究人员也将机会路由与位置路由进行结合。如文献[7]提出车流感知数据传输方案（Traffic Aware Data Delivery，TADS），文献[8]提出自适应连接感知路由（Adaptive Connectivity Aware Routing，ACAR）。这些协议充分利用位置路由和机会路由的特性，发挥它们各自的优势。然而，这些协议并没有考虑到节点的缓存区域，限制了消息传递的流畅性。

为此，针对机会网络的路由协议，本文提出基于复制概率的机会网络路由协议（Replication Probability-based Routing for Opportunistic Networks，RP-ON）。RP-ON 协议利用复本数和跳数设置消息复制概率，一旦与节点相遇，就将复制概率的消息进行传输。同时，设置消息限除的效用函数，通过此函数控制缓存区域空间。实验结果表明，本文提出的RP-ON协议能够有效地控制消息传输时延，并提高了消息传递率。

1 系统模型

考虑基于Markov链模型[9]的机会网络，其由一系列的移动机会节点构成。节点一旦在通信范围内遭遇到其他节点，就试图转发消息。在转发消息过程中，发送节点或转发节点就将消息的复本存储到缓冲区，待遇到合适的节点，就向其传递复本，实现消息的传递。节点可以以直接方式或通过转发节点的多跳方式向目的节点传输消息。

此外，信道资源、存储空间和带宽受限。同时，假定节点的移动模型服从独立同分布。节点相遇概率服从指数分布，并且所有节点均为同构节点。

依据Markov链模型，可建立常微分方程：

式中：R′(t)表示节点携带消息的概率；λc表示两节点相遇的平均几率；r表示消息数；N为网络内节点数。

通过积分可求解式（1），并得到瞬时消息复本数rt：

依据文献[10]，可计算所有消息的消息传递概率：

式中TTL表示消息的新鲜度。

值得注意，节点最多只能拥有同一条消息的一个复本。因此，P(t)N的最大值为1。

对式（3）进行一阶微分，可得传递概率函数的一阶微分：

2 RP-ON

RP-ON协议利用消息信息，并结合复制概率，设置消息的复制秩值。一旦相遇节点，节点就将具有最高秩值的消息复制（传递）给另一个节点。而复制概率蕴含了复制数、消息跳数和消息缓冲时间3个参数。

2.1 复制控制策略

首先，依据式（2）可粗略计算节点复制单条消息的概率。网络内总的节点数等于中间节点数加上源节点和目的节点，即N=n+2。因此，假定复制单条消息的概率为Fp，定义如下：

式中：Hc表示消息已传输的跳数；Rc表示消息已复制的次数。

节点的缓存区域内可能保持多条消息的复本。因此，节点依据每条消息概率Fp，给消息设置权重。一旦节点遭遇了节点，节点就将概率Fp最大的消息转发至遭遇节点。

考虑到消息的时效性和网络开销，对消息的复制次数进行控制，即制订停止复制消息的条件。依据式（3）～式（5）可得停止复制条件Sr。如果概率Fp大于Sr，则停止复制。Sr的定义：

例如，当两个节点在彼此通信范围内，节点就复制概率Fp最大的消息。假定两条消息分别为m1和m2。先计算消息的Fp，然后再比较这两条消息的Fp，再选择概率Fp大的消息进行转发，整个伪代码如下：

2.2 退除策略

考虑到每个节点的缓存区域有限，因此，若缓存区域存满，就将缓存区域内的消息退除。为此，RP-ON协议引用新的退除策略，考虑机会网络的动态性。退除策略不仅融合了缓存时间，还融合了动态跳数和消息的复制数。

具体而言，RP-ON的限除策略Dp由两个部分构成：存储成本Sc(t)和传输成本Tc(t)。Sc(t)的定义如下：

式中TBUF表示节点队列缓存内的队列时间。

而传输成本Tc(t)的定义如下：

因此，限除策略Dp的定义为：

基于概率Fp的转发策略为：

3 系统仿真

3.1 仿真场景

为了更好地分析RP-ON性能，利用ONE仿真器[11-13]建立仿真平台。选择Finland地图作为仿真区域，仿真时间为12 h，具体的仿真参数如表1所示。每次实验独立重复50次，取平均值作为最终的实验数据。

表1 仿真参数Table 1 Simulation parameters

为了更充分地分析RP-ON协议性能，选择SAW路由协议作为参照。同时，考虑3种不同的退除策略。这3种策略分别为：

1）退除最大复制数的消息，记为MaRe（Maximum Replication）；

2）退除最大跳数消息，记为MaHo（Maximum Hop）；

3）退除最早到达消息，记为FIFO。

3.2 仿真结果及分析

3.2.1 端到端传输时延

消息传输时延随数据率的变化曲线如图1所示。从图1可知，RP-ON协议的传输时延远低于SAW协议。例如，当数据率为1 500 Kb/s时，与SAW-MaRe，SAWMaHo，SAW-FIFO相比，RP-ON协议的传输时延分别下降了52%，58%和46%。原因在于RP-ON协议能够依据局部信息有效地转发消息，降低了消息传输的时延。

3.2.2 吞吐量

本次实验分析了3个协议的吞吐量随数据率的变化曲线，实验数据如图2所示。从图2可知，RP-ON协议的吞吐量最高，均高于SAW-MaRe，SAW-MaHo，SAWFIFO。例如，当数据率为3 000 Kb/s时，RP-ON协议的吞吐量比MaRe，MaHo和FIFO分别提高了约26%，13%，33%。原因在于：SAW协议在退除消息时，只考虑单方面的因素，不利于消息的传输。

图1 端到端传输时延Fig.1 End-to-end transmission delay

图2 吞吐量Fig.2 Throughput

3.2.3 数据丢失率

最后，分析消息丢失率随数据率的变化曲线，如图3所示。

图3 数据包丢失率Fig.3 Data packet loss rate

从图3可知，RP-ON协议的消息丢失率最低，低于SAW-MaRe，SAW-MaHo，SAW-FIFO协议。具体而言，当数据率为2 500 Kb/s，RP-ON协议的消息丢失率比SAW-MaRe，SAW-MaHo，SAW-FIFO 协议分别降低了25%，10%，35%。

4 结 语

本文针对机会网络的消息传递问题，提出基于复制概率的机会网络路由协议RP-ON。RP-ON协议充分利用消息的局部参数设置消息复制概率，再依据概率传输消息。同时，通过复本数、跳数和缓存时间设置退除策略，进而提高消息传输率，并降低传输时延。实验结果表明，与SAW协议相比，提出的RP-ON协议降低了消息传输时延，并提高了吞吐量。