用于容延网络的多路传送路由方法

摘要

本发明公开了一种用于容延网络的多路传送路由方法，其实施步骤如下：源节点产生报文并以源节点为中心向周边的相邻节点扩散传播，在网络中的多个中间节点中生成冗余报文拷贝，各持有冗余报文拷贝的中间节点分别将其持有的报文拷贝向目的节点传输，目的节点收到最先达到的报文拷贝后通知其他节点清除网络中的冗余报文拷贝。本发明具有报文传输可靠性高、报文传送效率高、抗毁性能好、方法智能高效、高报文传送比、低平均延迟、低网络开销比、网络资源利用高的优点，能够满足容延网络的实际需求。

权利要求

1.一种用于容延网络的多路传送路由方法，其特征在于它包括如下步骤：源节点产生报文并以源节点为中心向周边的相邻节点扩散传播，在网络中的多个中间节点中生成冗余报文拷贝，各持有冗余报文拷贝的中间节点分别将其持有的报文拷贝向目的节点传输，目的节点收到最先达到的报文拷贝后通知其他节点清除网络中的冗余报文拷贝。

2.根据权利要求1所述的用于容延网络的多路传送路由方法，其特征在于：所述源节点在产生报文时一并产生初始数量的该报文的转发令牌，每个接收到该报文和转发令牌的节点向其从未接收过该报文的相邻节点扩散传播报文，并在扩散传播时发送报文和它持有一半数量的转发令牌，当某个节点收到报文且仅持有一个该报文的转发令牌时，该节点即为持有一个冗余报文拷贝的中间节点。

3.根据权利要求2所述的用于容延网络的多路传送路由方法，其特征在于：所述源节点产生转发令牌的初始数量为网络总节点数的1/3。

4.根据权利要求1、2或3所述的用于容延网络的多路传送路由方法，其特征在于：所述中间节点在向目的节点传输报文拷贝时，采用动态迪杰斯特拉算法查找目标节点并进行传送，其中动态迪杰斯特拉算法的权值函数的表达式为：t″

其中，∫x＝t c(e.x)dx表示在t～t″时间间隔内可以经由边e移动的数据大小，c(e，x)表示链路e的容量，m指需要转发报文的大小，Q(e，t，s)表示当前节点经边e连接的下一跳节点s缓冲内排队等待转发数据的总大小，t代表计算最短路径的时间，d(e，t′)表示边e在t′时刻的传播延时。

5.根据权利要求1、2或3所述的用于容延网络的多路传送路由方法，其特征在于：目的节点收到最先达到的报文拷贝后，向邻近节点发送清除冗余报文拷贝消息，收到清除冗余报文拷贝消息的节点将此消息转发至网络中其他相邻节点，且如果节点缓存中存在相应的报文拷贝则进行删除。

6.根据权利要求4所述的用于容延网络的多路传送路由方法，其特征在于：目的节点收到最先达到的报文拷贝后，向邻近节点发送清除冗余报文拷贝消息，收到清除冗余报文拷贝消息的节点将此消息转发至网络中其他相邻节点，且如果节点缓存中存在相应的报文拷贝则进行删除。

7.根据权利要求1、2或3所述的用于容延网络的多路传送路由方法，其特征在于：目的节点收到最先达到的报文拷贝后，向一个专用节点发送待删除冗余报文拷贝的信息，所述专用节点根据各个节点发送的消息生成一个待删除冗余报文拷贝列表，各个节点定期读取专用节点上的待删除冗余报文拷贝列表，如果节点缓存中存在相应的报文拷贝则进行删除。

8.根据权利要求4所述的用于容延网络的多路传送路由方法，其特征在于：目的节点收到最先达到的报文拷贝后，向一个专用节点发送待删除冗余报文拷贝的信息，所述专用节点根据各个节点发送的消息生成一个待删除冗余报文拷贝列表，各个节点定期读取专用节点上的待删除冗余报文拷贝列表，如果节点缓存中存在相应的报文拷贝则进行删除。

说明书

用于容延网络的多路传送路由方法

技术领域

[0001] 本发明涉及网络通信领域，具体涉及一种用于容延网络的多路传送路由方法。

背景技术

[0002] 因特网技术的发展和应用已经为人类生活带来了极大的便利。但是由于各类因素的限制，在某些地区，例如不发达国家和地区、地球南北两极、乃至地球外层空间，在某些情况下，例如地震、海啸、火灾、恐怖袭击、军事对抗等突发情况下，网络通信往往表现为链路频繁断开，节点不规则运动，信息传输延时大、误码率高，现有因特网技术无法良好工作。而起源于行星际研究的容延网络(DTN，Delay Tolerant Networks)在信息传输高延迟、高误码率，通信链路频繁断开的环境下却能良好工作，因此，容延网络的研究得到越来越多研究团体和学者的关注，而路由是影响网络实际应用部署的重要问题，此容延网络的路由问题研究已经逐步深入。

[0003] 从拷贝使用和网络知识使用的角度来分，可将容延网络路由方法切分为四类：基于多拷贝洪泛的，基于网络知识的，基于编码技术的，混合型的，但是目前这些路由方法都是针对节点运动和网络拓扑变化没有任何规律的无线网络、传感器网络而展开的。基于多拷贝洪泛方法是通过在网络中各节点问任意地洪泛报文而达到将报文送达目的节点的，它最大的优势在于不需要网络信息，不需要路由表维护，能够在毫无规律可循的网络中转发报文，在增大报文传送比的前提下降低平均延迟，但它会带来巨大的网络资源浪费；基于网络知识的方法是部分地使用了可获取的网络信息，来取得网络开销和资源占用之间的性能平衡，网络知识可以是位置信息，也可以是统计信息，还可以利用周期性或规律性的连接时序信息，在此基础上，选择适当的权值或设置恰当的指标参数，计算转发路径并据此路由转发数据，这类方法减少了带宽和存储开销，灵活性比较强，具有一定的智能性，更接近传统的路由方法，但对于容延网络来说，精确的网络信息的获取和维护都比较困难，因此本方法只能运用于特定类型的网络；基于编码技术的方法是利用了编码技术，在转发之前对报文进行特殊处理，组成一组编码块，目的端只需接收到编码块的一部分，即可利用解码技术进行恢复，擦除编码和网络编码方案已经被研究，这类方法以在减少资源成本的同时，保持了多重拷贝的益处，有益于在网络性能较差时进行通信，但增加了报文路由转发的复杂性；混合型路由方法综合了以上方法的益处，既充分利用洪泛方法的快速性，又充分利用可知的网络知识，以此达到最理想的效果。而针对在现实世界中广泛存在的规律性较强的网络，如公车网络、空间网络等，由于其连接时序周期性强，网络的时序需要提前预知，而对于容延网络来说，精确的网络信息的获取和维护都比较困难，因此混合路由法同样也并不适合容延网络。

发明内容

[0004] 本发明针对上述现有技术的缺点，提供一种报文传输可靠性高、报文传送效率高、抗毁性能好、方法智能高效、高报文传送比、低平均延迟、低网络开销比、网络资源利用高的优点的用于容延网络的多路传送路由方法。

[0005] 为了解决上述技术问题，本发明采用的技术方案为：一种用于时序可知容延网络的多路传送抗毁路由方法，它包括如下步骤：源节点产生报文并以源节点为中心向周边的相邻节点扩散传播，在网络中的多个中间节点中生成冗余报文拷贝，各持有冗余报文拷贝的中间节点分别将其持有的报文拷贝向目的节点传输，目的节点收到最先达到的报文拷贝后通知其他节点清除网络中的冗余报文拷贝。

[0006] 作为本发明的进一步改进：

[0007] 所述源节点在产生报文时一并产生初始数量的该报文的转发令牌，每个节点在向其从未接收过该报文的相邻节点扩散传播报文，并在扩散传播时发送报文和它持有一半数量的转发令牌，当某个节点收到报文且仅持有一个该报文的转发令牌时，该节点即为持有一个冗余报文拷贝的中间节点；所述源节点产生转发令牌的初始数量为网络总节点数的1/3；

[0008] 所述中间节点在向目的节点传输报文拷贝时，采用动态迪杰斯特拉算法查找目标节点并进行传送，其中动态迪杰斯特拉算法的权值函数的表达式为：

[0009]

[0010] 其中， 表示在t～t″时间间隔内可以经由边e移动的数据大小，c(e，x)表示链路e的容量，m指需要转发报文的大小，Q(e，t，s)表示当前节点经边e连接的下一跳节点s缓冲内排队等待转发数据的总大小，d(e，t′)表示边e在t′时刻的传播延时，t代表计算最短路径的时间；

[0011] 目的节点收到最先达到的报文拷贝后，向邻近节点发送清除冗余报文拷贝消息，收到清除冗余报文拷贝消息的节点将此消息转发至网络中其他相邻节点，且如果节点缓存中存在相应的报文拷贝则进行删除；或者，目的节点收到最先达到的报文拷贝后，向一个专用节点发送待删除冗余报文拷贝的信息，所述专用节点根据各个节点发送的消息生成一个待删除冗余报文拷贝列表，各个节点定期读取专用节点上的待删除冗余报文拷贝列表，如果节点缓存中存在相应的报文拷贝则进行删除。

[0012] 本发明具有下述优点：本发明通过先将报文在网络中扩散生成多份地域上分散分布的冗余报文拷贝，然后并行向目的节点传送，大大增强了网络应对单个报文传输失败的传输能力，大大提高了报文传输的可靠性，抗毁性能好，方法智能高效，能满足容延网络的实际需求，具有高报文传送比、低平均延迟、低网络开销比的优点。在扩散过程中利用转发令牌逐级减半的方法，网络资源省损耗低、拷贝分发速度快；在寻找发送至目的节点的路径时，采用动态迪加斯特拉算法，方法快速而又高效；在报文到达目的节点后，清除整个网络的多余的冗余报文拷贝，因此可以将网络资源快速回收，减少了带宽的浪费，报文传送效率高。

附图说明

[0013] 图1为本发明的用于容延网络的多路传送路由方法的实施流程图；

[0014] 图2为本发明实施例的逐跳减半扩散生成冗余报文拷贝的流程示意图；

[0015] 图3是本发明实施例的报文的扩散转发示意图；

[0016] 图4是本发明实施例中中间节点传输报文拷贝的流程示意图；

[0017] 图5是本发明实施例中的清除多余的冗余报文拷贝的流程示意图。

具体实施方式

[0018] 如图1所示，本发明的用于容延网络的多路传送路由方法，其实施步骤如下：源节点产生报文并以源节点为中心向周边的相邻节点扩散传播，在网络中的多个中间节点中生成冗余报文拷贝，各持有冗余报文拷贝的中间节点分别将其持有的报文拷贝向目的节点传输，目的节点收到最先达到的报文拷贝后通知其他节点清除网络中的冗余报文拷贝。

[0019] 如图2所示，本实施例中采用转发令牌作为节点扩散生成冗余报文拷贝的凭据：持有报文和至少两个转发令牌的节点只允许将报文向其从未接收过该报文的相邻节点扩散报文拷贝；只有持有报文和一个令牌的节点才可以将其持有的报文拷贝向目标节点传输。在本实施例中，网络中的每个节点有一个缓存来存储数据，为了提高效率，注入网络中的每一个报文都有一个全局标识符，各个网络节点则以该标识符作为键值，为缓存中的所有生成、存储、中继转发的报文建立一张哈希索引表。同时，节点还维护一个一维比特数组(Summary Vector，SV)，用来标识哈希表每个中每一项的“有”或“无”，当两个节点产生通信机会时，它们将交换SV信息，如果当前节点中存在待扩散报文的SV记录，则拒绝接收该待扩散报文，否则接收该待扩散报文，并向其相邻节点继续扩散转发该待扩散报文，在发送完成后，分别更新自己的SV信息。源节点在产生报文的时候一并产生该报文的转发令牌，转发令牌是作为报文的一个基本属性而存在，然后源节点向其相邻节点转发报文和持有数量一半的转发令牌，每个接收到该报文和转发令牌的节点向其从未接收过该报文的相邻节点扩散传播报文时发送报文和它持有一半数量的转发令牌，从源节点向周边不断扩散传播。
转发令牌的数量依据网络节点数量指定，如果令牌数量过多，则可能会导致报文尚处于逐跳减半扩散传播阶段时即会达到目标节点，从而造成网络利用率过低；如果令牌数量过少，则报文拷贝可能尚未通过逐跳减半扩散到网络中，可能达不到容延网络的可靠性需求，在本实施例中，每个报文的转发令牌初始数量为节点总数量的1/3，这样就既不会由于报文拷贝数量过多而对网络资源造成的不必要的损耗，同时又可以较好地提高报文成功转发的比率。

[0020] 在本实施例中，源节点1中初始转发令牌的数量为8，如图3所示。

[0021] 1)源节点1持有报文和8个转发令牌，源节点1将报文和4个转发令牌转发给相邻的节点2和节点4，节点2和节点4均持有4个转发令牌；

[0022] 2)节点4将报文和2个转发令牌转发给节点7，节点7持有2个转发令牌，节点7除节点4以外没有其他相邻节点，此处的扩散转发终止。节点2将报文和2个转发令牌转发给节点3和节点6，节点3和节点6持有2个转发令牌，节点6除节点2以外没有其他相邻节点，此处的扩散转发终止；

[0023] 3)节点3将报文和1个转发令牌转发给节点5，节点5持有1个转发令牌，成为持有1个转发令牌的中间节点，节点5立即开始向目标节点传输冗余报文拷贝。

[0024] 如图4所示，持有一个转发令牌的中间节点根据动态迪加斯特拉(dijkstra)算法计算将其持有报文传输至目标节点的延迟最低的路径：中间节点首先轮询队列信息库、连接信息库，为报文计算各个传输至各相邻节点的转发延迟时间，然后找出延迟最低的相邻节点，添加到最小延时顶点集，逐次向目的节点延伸，最终根据最小延时顶点集找出通向目的节点的延迟最低路径，然后沿着该路径发出报文。

[0025] 在时序可知的容延网络中，网络内节点的运动具有一定的规律性或可预测性，动态的网络拓扑可认为由一个个静态拓扑映射组成，容延网络在某一足够小的时间段内，网络拓扑可以认为是静止的，节点间连接产生或断开的时间、通信链路的带宽、节点存储能力等问题皆可直接或间接计算获得，但这种可知并不是绝对精确的，在某些情况下，可能遇到偶然性的失败。中间节点需要存储网络的连接信息，该信息主要是通过转换网络中节点的运动轨迹、通信参数等信息，获得任一时刻网络中各节点的位置及能够产生的连接信息，相当于绘制网络拓扑图，该信息通过在网络内洪泛链路状态信息而更新；另外，节点需要存储各节点上缓冲队列大小、占用情况等信息，在节点产生通信机会时，通过发送响应报文及时更新。

[0026] 因此本发明中将延迟分为队列延迟、传输延迟和传播延迟，动态迪加斯特拉(dijkstra)算法中计算最低延迟路径的权值延迟函数为：

[0027] w(e，t)＝t′(e，t，m，s)-t+d(e，t′)

[0028] 其中，e代表转发报文的边，即一个可用的通信链路。t′(e，t，m，s)代表经过边e与当前节点连接的节点s上，排队等待转发的报文数据可以被注入到网络中进行转发的最早时间；t代表计算代价，d(e，t′)是边e在t′时刻的传播延迟。

[0029] 其中t′(e，t，m，s)包含队列延迟、传输延迟，可以表示为：

[0030]

[0031] 其中， 表示在时间t～t″间隔内可以经由边移动的数据大小，c(e，x)表示边e容量，其大小随时间变化；m指需要转发报文的大小；Q(e，t，s)指与当前节点经边e连接的下一跳节点s上，缓冲内排队等待转发数据的总大小，Q(e，t，s)函数仅和一跳内邻近节点缓冲的使用情况有关，其计算公式为：

[0032]

[0033] 因此，动态迪杰斯特拉算法的权值函数的表达式为：

[0034]

[0035] 在中间节点获得相应的最优路径路由表后，中间节点即可根据路由表信息将报文拷贝在网络中逐跳转发，直至报文拷贝被转发到目的节点为止。在该中间节点向目标节点传送报文的时候，该报文的多个冗余报文拷贝独立在网络中被其他的中间节点向目标节点传送。

[0036] 如图5所示，在报文拷贝被送达目的节点后，为了避免其它冗余拷贝造成大量的网络资源耗费，目的节点在收到第一份报文拷贝后，立即向其它节点发送确认删除确认信息(DeleteAcknowledge，简称D-ACK)。考虑到D-ACK消息占用的信息空间比较小，可在网络中洪泛，该记录表以单独的报文发送，或者附加于其他的报文上。

[0037] 在本实施例中，中间节点收到D-ACK消息以后，首先将检查该节点的SV记录内有无该报文拷贝，如果缓存中存在该报文拷贝，则将清除缓存中的此报文拷贝信息，然后继续利用自身可用连接向其它节点转发D-ACK消息；否则将直接利用自身可用连接向其它相邻节点转发D-ACK消息，直至D-ACK消息被洪泛式转发到整个网络中，从而将该D-ACK消息对应的冗余报文拷贝从整个网络中被清除。

[0038] 此外，网络中可以设立通信能力较强、覆盖范围较大的服务器或网关来作为专用的节点，各节点每隔一段时间向进入通信范围的服务器或网关节点发送一个专门的报文，该报文将列出从上一次与服务器或网络节点通信到目前时间，它认为可以在网络中清除的拷贝信息，服务器或网关节点将对收到的同类信息进行整理，定期在网络中洪泛一个清除信息列表，通知的时间间隔可根据网络实际，合理地设定。

[0039] 此外，在向相邻节点扩散传播生成冗余报文拷贝时，也可以采用跃点计算器来控制冗余报文拷贝的生成：源节点产生报文是初始化该报文的附带跃点计数器，每个节点向从未接收该报文的相邻节点转发报文和该报文的附带跃点计数器，每经过一个节点跃点计数器则自动递增或者递减，当跃点计数器达到一个指定数字时，节点成为持有冗余报文拷贝的中间节点，并立即开始将该报文向目标节点传输。