短相遇接触时间网络环境中的时延容忍网络路由方案

王 超

(南阳理工学院 计算机与软件学院，河南 南阳 473004)

1 引 言

稀疏的移动自组织网络是时延容忍传输的典型网络环境，它不依赖固定基础设施，网络节点可以自由组织，可进行多跳通信.换言之，时延容忍网络(Delay-tolerant Network，DTN)是一种特殊的稀疏移动自组织网络，无法建立从源节点到目的节点整条路径，具有稀疏连通、高分割率和间歇式连通特点[1].上述特点对传感器节点间的端到端通信路径提出了挑战，所以为处理DTN移动节点的稀疏连接，通常采用存储-转发方案.即传感器节点先临时存储消息，直至遇到合适的下一跳节点再转发该消息.因此，选择合适的下一跳节点成为DTN路由的重点和热点问题[2，3].面向DTN的路由协议研究受到国内外专家学者的广泛关注，但是大多数DTN路由协议均是建立在有足够相遇接触时间(Contact Duration Time，CDT)的假设条件下，即假定在单一相遇机会内即可一次性传输全部缓冲消息.然而，在DTN真实环境中的研究结果表明相遇接触时间通常很短[4，5].基于这一事实，真实环境下的DTN路由必须处理两个关键问题：1)转发节点的选择.即需要寻找一个合适的转发节点，该节点需与目的节点有足够长的相遇接触时间，主要作用是提高消息的传输成功率；2)消息转发策略.由于不是所有消息都能在一次相遇接触机会内完成传输，所以合理安排消息转发是非常重要的.

为解决DTN在短接触时间下的路由问题，给出一种短相遇接触时间网络环境中的时延容忍网络路由方案(routing scheme for delay tolerant network in Short Contact Duration Time network environment，SCDT).所给方案的基本思想主要是：首先，计算一跳传递概率和两跳传递概率.主要是利用相遇接触时间、相遇频率以及消息尺寸等网络信息来计算传递概率.其中，一跳传递概率是指将所携带的信息直接传递给目的节点；两跳传递概率是指当前携带消息的节点利用相遇节点作为中间转发节点向目的节点传输消息的概率.由于两跳传递概率的主要目的是为了降低传输成本，也即通过减少传输成本提高DTN网络带宽利用率，所以若是一个节点能够遇到比当前相遇节点更合适的转发节点，那么其应携带消息直至相遇到该节点.然后，依据所计算的概率在当前接触节点和过去接触节点中选择下一跳转发节点.仿真数据分析结果表明：所给SCDT路由方案能够有效提高消息传递率、降低时延和路由成本.

2 约束条件

约束条件1.假定网络中所有传感器节点均有存储缓冲功能，且DTN网络为有限转发带宽.当任一传感器节点在通信半径内与其他节点相遇，则该传感器节点即能向所相遇到的这些节点转发消息.假定节点的相遇接触时间较短，且相遇接触时间远短于相遇间隔时间，其中相遇间隔时间是指节点平均每隔多长时间相遇一次，也即相遇频率的倒数.

约束条件2.所给SCDT方案服从单复本模型，即指网络内的消息在任何时刻的复本最多仅有一条.假定所需传输的消息尺寸相同且无分割，若相遇接触时间大于或等于消息尺寸与可能带宽的比值，则表明消息被成功转发，否则消息需在下次相遇机会重传.

约束条件3.所需传输的每条消息均包含一个有限时效(Time-To-Live，TTL)值，一旦当消息的TTL值失效，则即丢弃此消息.此外，相遇接触时间和相遇间隔时间均服从指数分布，其参数分别为λ和θ.不同的两个节点间具有不同的相遇频率和相遇接触时间.同时采用仿真软件Cabspotting trace[6]进行系统仿真实验来评估所给SCDT方案的性能.

3 计算传递概率

传递概率是指节点所携带的消息到达目的节点的可能性，与携带消息节点的当前位置和目的节点的通信半径有关.文献[7]根据Random Waypoint运动模型，给出了任意时刻节点i的传递概率，如式(1)所示：

(1)

式中：d表示节点当前位置到目的节点的距离，R表示目的节点通信半径.当R/d≥1时，节点i当前位置位于目的节点的通信范围内，此时传输概率为1；当R/d<1时，节点i当前位置位于目的节点的通信范围之外，此时传输概率为R/d.节点主要根据其当前位置更新节点传递概率.所给SCDT路由方案在基于短相遇接触时间情况下首先推导出直接一跳传递概率和两跳传递概率.

3.1 直接一跳传递概率

令Yk为第k个相遇接触时间的随机变量，Hi为成功传输消息i所需的机遇接触时间，其定义如式(2)所示.当Yk≥Hi表示消息i在第k次相遇机会成功传输，否则消息i需在下一个相遇机会内重传.

Hi=ωi/B

(2)

式中：ωi为消息i的尺寸，B为两传感器节点间的通信带宽.

令Xk为第k个相遇间隔时间的随机变量.所给SCDT路由方案假定第k个相遇接触时间的随机变量Xk远远大于第k个相遇间隔时间的随机变量Yk，即Xk≫Yk，也即假定相遇接触时间极短，远小于发生下一次相遇的时间间隔.

假定携带当前消息i的传感器节点是s，而消息i所要到达的目的节点是d.那么消息i直至第n次相遇才成功传输至目的节点的概率Pi(n)，如式(3)所示：

(3)

因Xk和Yk均独立，则式(3)可变换成式(4)：

(4)

下面通过对Pi(n)中的3项分别进行分析来计算式(4)：

(5)

(6)

(1-exp(-θs，dHi))…(1-exp(-θs，dHi))=

(1-exp(-θs，dHi))n-1

(7)

exp(-θs，dHi)

(8)

把上述式(6)-式(8)代入式(3)，则可得：

(1-exp(-θs，dHi))n-1×exp(-θs，dHi)

(9)

最后，消息i被成功传输的概率Pi，如式(10)所示：

(10)

3.2 两跳传递概率

两跳传递概率是指由携带当前消息i的传感器节点s通过中间节点ϑ间接传输至目的节点d，如图1所示.

图1 两跳传递模型Fig.1 Two-hop transfer model

为计算两跳传递概率，传感器节点s需计算两个关键数据：1)需要计算传感器节点s与中间节点相遇所消耗的时间.需要注意的是，与传感器节点s相遇的中间节点必须是之前相遇过的，对于之前与传感器节点s从未相遇过的节点，则无法计算出这一时间;2)需要计算中间节点与目的节点间的相遇率.这一数据的计算需通过网络全局状态信息交互，所以各传感器节点需保存与其相遇节点的清单，具体的清单保存格式如式(11)所示：

(11)

式中：inter-contactrateλij为传感器节点i和j间的相遇率，timestamp为传感器节点i和j相遇率更新的时刻.

把中间节点融入传递概率的计算，则须相应的修改式(3)，应不仅包含节点s和中间节点ϑ的相遇接触时间和相遇间隔时间，同时也要包含中间节点ϑ和目的节点d的相遇接触时间和相遇间隔时间.假定节点s经过n次相遇把消息i传输到中间节点ϑ，然后从ϑ又经过m次相遇把消息i传输到目的节点d.因此，节点s通过中间节点ϑ把消息i传输到目的节点d时没有过期的概率如式(12)所示：

(12)

然后根据逐项积分理论[9]计算式(12)，如式(13)所示：

(13)

式中：N=2，β1=λs，ϑ，β=λϑ，d，a1=n，a2=m.

节点s经过n-1次相遇把消息i传输到中间节点ϑ以及中间节点ϑ经过m-1次相遇把消息i传输到目的节点d失败的传递概率计算如式(14)所示：

(1-exp(-θs，ϑHi))n-1·(1-exp(-θs，dHi))m-1

(14)

节点s经过n次相遇把消息i传输到中间节点ϑ以及中间节点ϑ经过m次相遇把消息i传输到目的节点d成功的传递概率计算如式(15)所示：

=exp(-θs，ϑHi-θϑ，dHi)

(15)

根据式(13)-式(15)，则能计算出节点s经过n次相遇把消息i传输到中间节点ϑ，然后中间节点ϑ经过m次相遇把消息i传输到目的节点d成功的传递概率Pi(n，m)，如式(16)所示：

Pi(n，m)=A·(1-exp(-θs，ϑHi)n-1)(1-exp(-θϑ，dHi))m-1

·exp(-θs，ϑHi-θϑ，dHi)

(16)

因此，节点s把消息i经过两跳成功传输到目的节点d的概率Pi如式(17)所示：

(17)

4 选择下一跳路由

所给SCDT路由方案的关键步骤主要是如何选择下一跳转发节点.假定与源节点(携带消息节点)s相遇的节点集为V={ϑ1，ϑ2，…，ϑn}，但该节点集不包含目的节点，即ϑi≠d.若节点集包含目的节点，则表明源节点s已与目的节点d相遇，直接就能向其转发所携带的消息.首先，交互节点的相遇节点集，然后根据式(10)分别单独计算源节点s和邻居节点ϑi的一跳传输概率，并记为Ps和Pϑi，最后每个ϑi向s传递其各自一跳传输概率Pϑi.

然后，令Pϑ=max(Pϑ1，Pϑ2，…，Pϑk)，同时s应判断Ps是否大于Pϑ.若存在Ps>Pϑ，则表明源节点s不转发所携带的消息，而是将消息存到缓存区；若存在Ps

图2 消息转发流程Fig.2 Message forwarding process

最后，令Pr=max(Pr1，Pr2，…，Prm).若存在Pϑ>Pr，那么源节点s即可把其所携带的消息转发到具有最大传输概率Pϑ的当前邻居节点ϑ，接着ϑ利用相同的策略把消息传输到目的节点d.

综上，源节点s选择下一跳转发节点F*的策略主要是从当前的一跳邻居节点和当前未相遇但之前相遇过的二跳邻居节点中寻找转发概率最大的节点.整个消息转发流程如图2所示.

图3 消息转发示例Fig.3 Example of message forwarding

图3的消息转发示例演示了下一跳转发消息的过程.节点s先计算一跳传递概率Ps，然后计算出当前一跳邻居节点传递概率Pϑ1.若存在Ps≥Pϑ1，那么就再计算二跳传递概率Pr1.取Pϑ1=max(Ps，Pr1，Pϑ1)，节点ϑ1即为下一跳转发节点.

5 仿真性能分析

所给SCDT路由方案采用ONE 1.5.1[10]机会网络仿真器进行仿真，并采用Cabspotting trace进行性能评估，其中Cabspotting包括533辆出租车的跟踪文件.假定每个节点都有一定的缓冲容量，且在缓冲区初始存储了5条尺寸为2MB的消息，全部消息均有相同的TTL值.每次仿真独立重复20次，取平均值作最终的仿真结果.

为更好地评估所给SCDT路由方案性能，采用Epidemic[11]、PROPHET[12]、MEED[13]与BubbleRap[14]4种路由方案作为参照，主要比较消息传递率、平均时延与路由成本性能.其中消息传递率指成功传输的消息数与总消息数之比；平均时延指消息从源节点传输到目的节点所需的平均时间；路由成本指消息传输到目的节点被转发的次数.

5.1 消息传递率

图4给出了随着消息时效变化，所给SCDT路由方案Epidemic、PROPHET、MEED和BubbleRap方案的消息传递率比较.由图4可以看出，Epidemic路由方案的消息传递率最高，但这种高传递率是以较高的网络资源为代价.当消息时效为14天时，所给SCDT路由方案的平均消息传递率是74%，分别比PROPHET、MEED与BubbleRap路由方案的平均消息传递率提高了10%、12%与13%.所给SCDT路由方案具有较高的消息传递率，主要是因为所给SCDT路由方案通过计算一跳传递概率和二跳传递概率，然后选择传输概率最大的节点作为下一跳转发节点，从而获得了较高的消息传递率.

图4 消息传递率随TTL增加的变化情况Fig.4 Change of message delivery rate with the increase of TTL

5.2 平均时延

图5给出了随着消息时效变化，所给SCDT路由方案Epidemic、PROPHET、MEED与BubbleRap方案的平均时延比较.由图5可以看出，Epidemic路由方案的平均时延最低，这主要是由于Epidemic路由方案采用泛洪策略决策路由，使得其建立路由的时间大为缩短.尽管所给SCDT路由方案的平均时延高于Epidemic路由方案的平均时延，然而与PROPHET、MEED和BubbleRap路由方案相比，其平均时延分别降低了5%、10%与12%.所给SCDT路由方案之所以有较高的平均时延，这主要是因为所给SCDT路由方案考虑了DTN网络节点相遇接触时间短的实际情况，通过计算源节点的相遇节点集合中消息的传递概率，在相遇节点集合中选择最大传递概率的节点转发消息，优化了转发节点选择的方案，有效降低了消息传输的平均时延.

图5 平均时延随TTL增加的变化情况Fig.5 Change of average time delay with the increase of TTL

5.3 路由成本

图6给出了随着消息时效变化，所给SCDT路由方案Epidemic、PROPHET、MEED与BubbleRap方案的路由成本比较.由图6可以看出，Epidemic路由方案具有最高的路由成本，同时结合图4与图5可以发现Epidemic路由方案是以高路由成本为代价来换取低时延与高消息传递率.而且由图6也可以看出，所给SCDT路由方案具有最低的路由成本，与PROPHET、MEED和BubbleRap路由方案相比，其路由成本分别下降了14%、19%与23%.所给SCDT路由方案之所以有较低的路由成本，这主要是因为所给SCDT路由方案通过计算当前和之前相遇节点的传递概率，并据此优化转发节点选择的方案，有效减少了消息被转发的次数，从而降低了路由成本.

图6 平均路由成本随TTL增加的变化情况Fig.6 Change of average routing cost with the increase of TTL

根据图4-图6的仿真结果，可以看出所给SCDT路由方案在消息传递率、平均时延与路由成本方面的性能均较好.虽然所给SCDT路由方案的消息传递率与平均时延性能劣于Epidemic路由方案，然而其能够比Epidemic路由方案更有效地控制路由成本，而与PROPHET、MEED与BubbleRap路由方案相比，所给SCDT路由方案不仅具有较低的路由成本，同时具有高消息传递率与低平均时延.

6 结 语

针对时延容忍网络在真实环境中的相遇接触时间通常很短这一事实，文中给出了一种短相遇接触时间网络环境中的时延容忍网络路由方案.所给路由方案利用相遇接触时间、相遇频率以及消息尺寸等网络信息首先计算一跳传递概率和两跳传递概率，然后根据推导出的传递概率选择下一跳转发节点.仿真性能分析表明，所给SCDT路由方案能够在保持较低的路由成本下，有效提高时延容忍网络路由的消息传递率，同时具有较低的平均时延.因此，所给SCDT路由方案能够较好地应用于真实的延容忍网络路由中，具有较好地实际应用价值.下一步的研究工作主要是打算在幂次分布、对数正态分布和超指数分布推导出选择转发节点的规则公式，并结合缓冲区管理策略优化路由方案.