基于转发概率的时延容忍网络路由

薄 珏, 乔 林, 王丹妮, 黄 峰, 许小洁

(1.国网辽宁省电力有限公司信息通信分公司，辽宁 沈阳 110000;2. 国网信通亿力科技有限责任公司，福建 厦门 350003; 3. 厦门大学，福建 厦门 361005)

0 引 言

建立节点间端到端的路由是时延容忍网络(Delay-tolerant Networks, DTNs)的关键[1-2]。DTNs具有间歇式连通、网络分割严重等特点。这些特点给DTNs的数据传输提出了挑战。为此, 路由成为DTNs的研究热点[3-4]。

存储-转发是DTNs常采用的路由策略。当目前没有连通链路时, 数据包携带节点先存储数据, 直到遇见合适的转发节点, 才将数据传输至该节点。然而, 在实际环境下，节点的相遇时间甚短，相遇的时间可能不足于数据的交换。

研究表明[4-5]，DTNs内节点的相遇时间短。短的相遇时间给数据传输提出了挑战。短的相遇时间难以在单一相遇机会内完成数据的传输，需要多次相遇才能完成数据传输。

由于DTNs的链路连通时间短，静态的路由算法无法应用于DNTs网络。在基于DTNs路由环境下，必须解决两个问题：依据节点的相遇时间择优选择转发节点，尽量选择相遇时间长的节点作为数据转发节点。例如，王鹏[6]提出基于时间聚合图的DTN网络最短时延路由算法，该算法通过链路的连通时间计算最短路径。并利用深度优先算法搜索最短时延路由。

其次，尽可能单次接触完成数据传输。若单次不行，需通过多次接触完成数据的传输, 并需解决拥塞问题[7], 例如，钟陈陈提出基于增强型PROPHET路由的DTN拥塞控制算法，该算法通过控制节点的缓存空间，降低算法的拥塞。因此，需要制定有效的数据转发策略。

考虑到DNTs节点相遇的机会性，本文引用统计理论计算邻居节点的接触概率。通过网络拓扑信息，相遇频率、数据包尺寸，估计节点相遇概率。传统的路由算法只计算一跳邻居节点的概率，并没有考虑两跳邻居节点的相遇概率。

计算两跳邻居节点的概率目的在于维护路由。当一跳邻居节点范围内没有合适的转发节点，就从二跳邻居节点范围内选择转发节点。避免重新计算路由，减少成本，有利于数据的传输。

为此，面向DTNs网络，提出一种基于转发概率的DTNs路由(Forwarding-probability DTN Routing, FPDR)。FPDR路由扩大选择转发节点的范围，从一跳和两跳的邻居节点范围内择优节点，提高数据包传递率。仿真结果表明，提出的FPDR路由有效地提高了数据包传递率。

1 网络模型

由于DTNs网络的链路时间短，每个节点采用存储-转发策略。因此，假定每个节点具有缓存区。当节点暂找不到转发节点，就缓存数据，直到遇到合适的节点，才转发数据。

考虑到网络开销，FPDR路由引用单复本数据模型。即只允许网络内只有一个数据复本。若节点的相遇时间不小于数据尺寸与可获取带宽的比值，就认为在此次相遇机会内完成数据的传输。若不能完成数据传输，则另寻其他机会完成数据传输。

同时，每个网络内传输的数据都具有时效性。当数据的时效过期，此数据就无效。此外，令节点相遇时间和相遇周期服从指数分布，且相应的参数为β和t。为了表述简单，增强可读性，引用如表1所示的标识号。

表1 标识符

2 FPDR路由

FPDR路由先计算节点相遇概率，然后，再计算节点相遇概率转发数据包。为此，先推导相遇概率，然后再执行数据路由策略。

2.1 一跳邻居节点传递概率

假定节点si携带了当前数据Data。Data的目的节点是sd。假定数据Data经过m次相遇接触才能成功转发至目的节点sd：

(1)

(2)

(3)

(4)

(5)

(6)

最终，可通过将式(4-6)代入式(1)可得一跳邻居的数据转发概率：

(7)

2.2 两跳邻居节点传递概率

上一节推导了一跳邻居节点的数据传递概率。FPDR路由欲从两跳邻居节点中选择数据转发节点。因此，本节推导两跳邻居节点的数据转发概率。

图1 两跳传递模型

为了能正确地推导两跳邻居节点的相遇概率，每个节点保存与邻居节点相遇的概率。为此，每个节点保存四元组信息〈si,sx,ηix,Tix〉。其中sx表示节点si的邻居节点。ηix表示节点si与节点sx相遇概率。而Tix表示时间戳。

节点si先计算与中间节点sx相遇所消耗时间，进而计算相遇概率。据此，对式(1)进行修改。使其包含节点si与节点sx相遇概率、中间节点sx与目的节点sd的相遇概率。假定节点si通过第n次接触才将数据Data传输至中间节点sx。中间节点再经过m次接触才能将数据传输至目的节点sd。

首先，先计算数据Data在到达目的节点sd前，数据Data未过期的概率：

(8)

再利用逐项积分，对式(8)进行处理：

(9)

其中N=2,β1=λs,ϑ、β=λϑ,d、a1=n和a2=m。令A表示式(9)中的积分项。再推导节点si在n-1前未能将数据Data传输至中间节点sx的概率和中间节点sx在m-1次接触未能将数据Data传输至目的节点sd的概率：

(10)

最后，数据Data在节点s与中间节点ϑ的n次相遇以及中间节点ϑ与目的节点d的m次相遇时，被成功传输的概率：

(-θϑ,dHData)=exp(-θs,ϑHData-θϑ,dHData)

(11)

最后，推导节点si将数据Data传输至目的节点sd的概率：

(12)

最终，依据式(10-12)计算节点si将数据Data成功传输至目的节点sd的概率：

(13)

2.3 数据传输策略

图2 消息转发流程

数据传输的整个流程如图2所示。首先，每个节点先向邻居节点传输自己的邻居节点集。然后，数据携带节点si先依式(7)计算一跳邻居节点的数据传输概率，邻居节点再向邻居节点传输自己的一跳邻居概率，且令Ps和Pϑi分别表示这两个概率。

然后，再从邻居节点中选择具有最大转发概率Pϑ的节点，同时，判断Ps与Pϑ的大小。若满足Ps>Pυ，则数据携带节点si就不转发数据Data。反之，若不满足，数据携带节点si就从二跳邻居节点寻找最优节点，并计算式(13)计算概率。若未能寻找到合适的转发节点，数据携带节点si就存储该数据。

3 性能分析

3.1 仿真环境

为了更发地分析FPDR路由性能，通过ONE 1.5.1软件[9]建立仿真平台。引用沈阳出租车的行迹文件，由交通部提供出租车的移动数据。将出租车作为节点。每个节点最多能缓存5个数据，每个数据尺寸为1 MB。

同时，选用文献的[8]提出的染路由(Epidemic Routing, EPR)、文献[9]提出的概率路由(Probabilistic Routing, PBR)、文献[10]提出的基于社会网络转发的路由(Social-based Forwarding Routing, SFR)作为参照。并对比分析它们的数据包传递率、数据端到端传输时延以及数据被传输的次数这三个性能。

3.2 数据分析

3.2.1实验一

本次实验分析数据包的传递率。图3显示了数据包传递率随数据的有效时期的变化情况。

图3 数据传递率

从图3可知，数据的有效期越高，数据包传递率越高。原因在于：数据的有效期越高，数据包的生存时间越长，留给传输数据的时间越多，这有利于数据包的传递。反之，若数据有效期越短，数据包的生存时间也越短。数据还未成功传输至目的节点，数据可能就失效。

此外，从图3可知，EPR路由的数据包传递率最高，原因在于：EPR路由引用传染思想传递数据。该策略是以网络资源为代价，提高数据包传递率。尽管FPDR路由的数据包传递率低于EPR路由，但是其高于PBR、SFR路由。这说明FPDR路由利用通过推导数据传输概率，择优选择转发节点，能够提高数据包传递率。

3.2.2实验二

本次实验分析FPDR的数据传输的端到端传输时延，如图4所示。

图4 端到端传输时延

从图4可知，EPR路由具有最低时延。这与EPR路由策略相关。该路由策略引用泛洪策略传递数据，能够使数据包快速地传输至目的节点。因此，EPR路由的时延最低。

此外，相比于PBR、SFR路由，提出的FPDR路由的端到端传输时延得到有效地控制，且分别比PBR和SFR路由下降了约5%和12%。

3.2.3实验三

本次实验分析每个数据包转发的平均次数。平均转发的次数越少，数据传输效率越高。图5分析了FPDR路由、EPR路由、PBR和SFR路由的每条数据包的转发次数。

图5 数据包转发的次数

从图5可知，EPR路由的数据包转发次数最高。原因在于：EPR路由是通过泛洪策略转发数据包，产生了大量的冗余数据包。尽管EPR路由的数据包传递率高(图3)、传输时延低(图4)，但是EPR路由的网络开销大。在节点密集环境，也容易形成泛洪风暴。

此外，相比于PBR和SFR路由外，FPDR路由转发次数最低，且分别比PRB和SFR路由下降了约23%和14%。

4 结 语

针对DTNs的数据传输问题，提出基于转发概率的时延容忍网络路由FPDR。FPDR路由通过计算相邻节点间的相遇时间，推导数据转发概率，并依据转发概率择优选择转发节点，再建立稳定路由。仿真结果表明，提出的FPDR路由能够有效地提高数据包传递率，并减少转发次数。