一种面向Epidemic路由算法的节点缓存释放的延迟容忍网络拥塞避免方法

摘要

本发明属于延迟容忍网络领域，主要涉及一种面向Epidemic路由算法的节点缓存释放的延迟容忍网络拥塞避免方法。本发明包括：采用DTN节点缓存阈值设置方法对网络中节点的缓存设置存储阈值；采用DTN消息阈值设置方法对节点缓存中的消息设置消息转发跳数阈值和消息转发副本数阈值；判断网络中的任意两个节点是否正在相遇等。本发明通过对网络中消息设置消息转发跳数阈值和消息转发副本数阈值，使得当节点缓存达到存储阈值时，通过删除消息的跳数和消息的副本数达到阈值的消息，从而可以有效的控制网络中消息副本数，实现网络拥塞避免。

说明书

技术领域

本发明属于延迟容忍网络领域，主要涉及一种面向Epidemic路由算法的节点缓存释放的延迟容忍网络拥塞避免方法。

背景技术

DTN是一种新型网络，代表了未来移动通信领域发展方向之一，主要应用于星际网络、乡村网络、战地网络等。DTN具有链路间断连接特性，并且消息在传递过程中会经历长时间或者不确定的时延。DTN中通常不存在端到端的连接，从而使得面向连接的端到端传输协议不适用于此种网络。由于DTN具有高延迟性、间断连接性、拓扑易变性、节点资源有限等特点。为了克服这些网络限制，能够保证消息传输的到达率，DTN使用传输层提供的服务，以跳到跳的托管机制，采用“存储-携带-转发”这种方式对消息进行传输。然而DTN具有高延迟性、间断连接性、拓扑易变性、节点资源有限等特点，这就导致了托管节点有可能需要长时间保存接收到的消息，来应对可能出现的网络延迟和中断，直到收到下一跳托管节点的确认信息或者消息被成功传递至目的节点。如果托管节点不能及时转发其收到的消息，网络又有大量的消息需要及时转发，那么网络就会最终耗尽托管节点的存储资源，造成网络拥塞。

Epidemic路由算法是DTN网络中最重要的路由算法之一，许多路由算法都可以视为是在此算法基础上的一种改进。Epidemic路由算法是Vahdat等人提出的，其主要思想是网络中当2个节点相遇时交换对方没有的消息，经过足够多的消息交换后，理论上每个非孤立的节点都将收到所有的消息，从而实现消息的传输。在Epidemic算法中，每个消息都有一个全局唯一的标识，每个节点中保存一个概要向量，用来记录节点中携带的消息。当2个节点相遇时，彼此首先交换概要向量，从而获知对方所携带的消息情况，然后双方仅传送对方没有的消息。在设计Epidemic路由算法时主要有3个目标，分别是最大的传输成功率、最小的传输延迟和最小的网络资源消耗。Epidemic路由算法本质上是一种无限制泛洪算法，从理论上讲该算法能最大化消息传输的成功率，最小化传输延迟。但在很多数场景中，由于过度泛洪会导致路由算法的性能显著下降。

DTN中的拥塞是指DTN中节点间复制转发消息使得DTN中消息的副本数过多，从而导致了DTN性能的降低。而网络资源的占用与分布不均的网络流量是产生网络拥塞的主要原因。如果合理分配网络有限的资源、控制网络流量，可有效地保证畅通网络流量和维持网络的性能平稳，而DTN拥塞避免要求既能使DTN性能得到一定保障、又能最大化DTN吞吐量。但是拥塞避免对延迟容忍网络的投递率和延迟等网络性能的影响重大，因此，研究DTN拥塞避免对于DTN在实际中的应用尤为重要。

针对以上分析，本发明针对DTN网络中Epidemic路由算法，提出了一种面向Epidemic路由算法的节点缓存释放的延迟容忍网络拥塞避免方法。该方法的主要思想是：对网络中节点的缓存空间设置存储阈值，并且对节点中的消息设置消息转发跳数阈值和消息转发副本数阈值，当节点已使用的缓存空间达到存储阈值时，通过删除节点中转发跳数已经达到消息转发跳数阈值、转发副本数达到消息副本数阈值的消息，来释放节点缓存空间。若此时能够有效的释放节点空间则不做进一步的拥塞避免操作。否则，对节点中的消息采进行优先级的划分，将优先级最低的消息的TTL减半，使节点的缓存空间尽快被释放，从而实现网络中拥塞现象的避免。

发明内容

本发明的目的是提出一种面向Epidemic路由算法的节点缓存释放的延迟容忍网络拥塞避免方法。

本发明的目的是这样实现的：

(1)采用DTN节点缓存阈值设置方法对网络中节点的缓存设置存储阈值；

(2)采用DTN消息阈值设置方法对节点缓存中的消息设置消息转发跳数阈值和消息转发副本数阈值；

(3)判断网络中的任意两个节点是否正在相遇；

(4)如果存在两个节点正在相遇，若两节点含有相同的消息，则把共同的消息的跳数和消息的转发副本数更新为两个节点中消息的跳数和转发副本数的最大值，否则执行步骤(6)；

(5)采用DTNE路由算法进行消息转发；

(6)判断节点缓存是否达到存储阈值；如果是，则执行步骤(7)；否则，返回步骤(3)；

(7)判断节点缓存中是否有消息的转发跳数或转发副本数达到消息转发跳数阈值或消息转发副本数阈值；如果是，则执行步骤(8)；否则，执行步骤(9)；

(8)节点删除消息的转发跳数达到转发跳数阈值的消息以及消息的转发副本数达到消息转发副本数阈值的消息；

(9)判断此时节点的输入消息量是否大于输出消息量；如果是，则执行步骤(10)；否则，执行步骤(12)；

(10)采用DTN消息优先级划分方法对网络中每一个节点的消息进行优先级的划分；

(11)将三级消息的TTL减半；

(12)结束；

在所述步骤(1)所述的DTN节点缓存阈值设置方法包括：对于网络的任意节点I，节点I的存储阈值为α＝0.8×M，其中M为节点I的缓存大小；

在步骤(2)中所述的DTN消息阈值设置方法包括：对于网络中的任意消息q其转发跳数阈值设置为16，消息q的转发副本数阈值设置为5；

在步骤(6)中所述的DTNE路由算法包括：对于网络中任意两个节点U和V相遇，将节点U中所拥有的消息而节点V中没有的消息p(i)，p(i)的转发跳数和转发副本数分别为J(i)和C(i)，且J(i)和C(i)均小于其阈值，转发给节点V，节点U中的消息p(i)的转发跳数J(i)+1，转发副本数为C(i)+1，节点V中消息p(i)的转发跳数为J(i)+1，转发副本数C(i)；若节点U中消息p(i)的转发跳数或转发副本数达到阈值，节点V不是消息p(i)的目的节点时，则不将消息p(i)复制给节点V；

在步骤(10)中所述的DTN消息优先级划分方法还包括：对于任意消息q，通过判断q的Pr的大小来设置优先级，其中Si为消息q的长度，Max代表网络中最大消息的长度、Ju为消息q已经经历的跳数；其中，0≤Ju≤16；Co为消息q的已经复制的副本数；其中，0≤Co≤5；并且α+β+γ＝1；当时，此消息为一级消息；当时，此消息为二级消息；当时，此消息为三级消息；其中一级优先级最高，三级优先级最低。

本发明的有益效果在于：

本发明的主要优点：(1)通过对网络中的节点设置存储阈值，使得节点在未达到拥塞时就进行缓存释放，从而实现节点拥塞现象的避免。(2)通过对网络中消息设置消息转发跳数阈值和消息转发副本数阈值，使得当节点缓存达到存储阈值时，通过删除消息的跳数和消息的副本数达到阈值的消息，从而可以有效的控制网络中消息副本数，实现网络拥塞避免。(3)当节点缓存空间的使用情况达到存储阈值时，通过删除消息的跳数和消息的副本数达到阈值的消息来释放缓存空间。然后判断此时节点的输入消息量和输出消息量的大小，当输入消息量大于输出消息量时，通过对节点中消息进行优先级的划分，将优先级最低的消息的TTL减半，从而可以尽快释放节点缓存空间，达到网络中拥塞现象避免的目的。

附图说明

图1一种面向Epidemic路由算法的节点缓存释放的延迟容忍网络拥塞避免方法的流程图；

图2一种面向Epidemic路由算法的节点缓存释放的延迟容忍网络拥塞避免方法具体实施的框架图；

图3一种面向Epidemic路由算法的节点缓存释放的延迟容忍网络拥塞避免方法俩节点相遇实例图。

具体实施方式

下面结合附图对本发明做进一步描述：

该方法的主要思想是：首先对网络中节点的缓存空间设置存储阈值，并且对节点中的消息设置消息转发跳数阈值和消息转发副本数阈值，当节点已使用的缓存空间达到节点缓存空间的存储阈值时，通过删除节点中转发跳数已经到达消息转发跳数阈值、转发副本数达到消息副本数阈值的消息，来释放节点缓存空间。然后通过此时节点的输入消息量和输出消息量来判断是否进行进一步的拥塞避免操作，若此时节点中输出消息量大于输入消息量则不做进一步的拥塞避免操作(这里的输入消息量指的是节点正在接受的消息的长度；输出消息量指的是正在删除的消息的大小，正在删除的消息包括：达到消息转发跳数阈值的消息、达到消息转发副本数阈值的消息、TTL等于0的消息)。否则，对节点中的消息采用DTN消息优先级划分方法进行优先级的划分，将优先级最低的消息的TTL减半，使节点的缓存空间尽快被释放，从而实现网络中拥塞现象的避免。

本发明是这样实现的：

步骤一：采用DTN节点缓存阈值设置方法对网络中节点的缓存设置存储阈值。

步骤二：采用DTN消息阈值设置方法对节点缓存中的消息设置消息转发跳数阈值和消息转发副本数阈值。

步骤三：判断网络中的任意两个节点是否正在相遇。

步骤四：如果存在两个节点正在相遇，若两节点含有相同的消息，则把共同的消息的跳数和消息的转发副本数更新为两个节点中消息的跳数和转发副本数的最大值，否则执行步骤六。

步骤五：采用DTNE路由算法进行消息转发。

步骤六：判断节点缓存是否达到存储阈值。如果是，则执行步骤七；否则，返回步骤三。

步骤七:判断节点缓存中是否有消息的转发跳数或转发副本数达到消息转发跳数阈值或消息转发副本数阈值。如果是，则执行步骤八；否则，执行步骤九。

步骤八：节点删除消息的转发跳数达到转发跳数阈值的消息以及消息的转发副本数达到消息转发副本数阈值的消息。

步骤九：判断此时节点的输入消息量是否大于输出消息量。如果是，则执行步骤十；否则，执行步骤十二。

步骤十：采用DTN消息优先级划分方法对网络中每一个节点的消息进行优先级的划分。

步骤十一：将三级消息的TTL减半。

步骤十二：结束。

在步骤一种所提到的DTN节点缓存阈值设置方法还包括：对于网络的任意节点I，节点I的存储阈值为α＝0.8×M，其中M为节点I的缓存大小。

在步骤二中所提到的DTN消息阈值设置方法还包括：对于网络中的任意消息q其转发跳数阈值设置为16，消息q的转发副本数阈值设置为5。

在步骤六中所提到的DTNE路由算法还包括：对于网络中任意两个节点U和V相遇，将节点U中所拥有的消息而节点V中没有的消息p(i)(p(i)的转发跳数和转发副本数分别为J(i)和C(i)，且J(i)和C(i)均小于其阈值)转发给节点V，此时节点U中的消息p(i)的转发跳数J(i)+1，转发副本数为C(i)+1，节点V中消息p(i)的转发跳数为J(i)+1，转发副本数C(i)。若节点U中消息p(i)的转发跳数或转发副本数达到阈值，节点V不是消息p(i)的目的节点时，则不将消息p(i)复制给节点V。

在步骤十中所提到的DTN消息优先级划分方法还包括：对于任意消息q，通过判断q的Pr的大小来设置优先级，其中(Si为消息q的长度，Max代表网络中最大消息的长度、Ju为消息q已经经历的跳数。其中，0≤Ju≤16。Co为消息q的已经复制的副本数。其中，0≤Co≤5。并且α+β+γ＝1)。当时，此消息为一级消息；当时，此消息为二级消息；当时，此消息为三级消息。其中一级优先级最高，三级优先级最低。

本发明的主要优点：(1)通过对网络中的节点设置存储阈值，使得节点在未达到拥塞时就进行缓存释放，从而实现节点拥塞现象的避免。(2)通过对网络中消息设置消息转发跳数阈值和消息转发副本数阈值，使得当节点缓存达到存储阈值时，通过删除消息的跳数和消息的副本数达到阈值的消息，从而可以有效的控制网络中消息副本数，实现网络拥塞避免。(3)当节点缓存空间的使用情况达到存储阈值时，通过删除消息的跳数和消息的副本数达到阈值的消息来释放缓存空间。然后判断此时节点的输入消息量和输出消息量的大小，当输入消息量大于输出消息量时，通过对节点中消息进行优先级的划分，将优先级最低的消息的TTL减半，从而可以尽快释放节点缓存空间，达到网络中拥塞现象避免的目的。

以图2所示为例，假设网络中有30个节点。其中节点的编号为1-30，网络中节点所携带的消息如图所示，以1号节点为例，1号节点所携带的消息为p1、p2、p3。首先由DTN节点缓存阈值设置方法设置网络中所有节点的存储阈值，以1号节点为例，假设1号节点的缓存空间大小为100M，则一号节点的存储阈值为80M。然后设置网络中消息转发跳数和转发副本数阈值，在本例中，将消息转发跳数阈值设置为16，将消息转发的副本数阈值设置为5。

判断网络中任意两个节点是否相遇，在本例中假设15号节点和16号节点相遇(如图3)，此时15号节点携带消息为p10、p11、p12，16号节点携带的消息为p8、p9、p10。将两个节点中相同的消息的转发跳数和转发副本数更新为二者中的最大数，假设15号节点的消息p10的转发跳数和转发副本数为7和3,16号节点的消息p10的转发跳数和转发副本数为6和2，此时则将16号节点的消息p10的转发跳数和转发副本数更新为7和3。

通过DTNE路由算法对相遇的两个节点之间进行数据转发。在此例中假设15号节点和16号节点相遇，由于15号节点没有16号节点中的消息p8、p9(假设消息p8的转发跳数为4、转发副本数为3，消息p9的转发跳数为7、转发副本数为3)。当消息p8和p9转发给15号节点后，16号节点中消息p8的转发跳数为5、转发副本数为4，p9的转发跳数为8、转发副本数为4，此时15号节点中消息p8的转发跳数为5、转发副本数为3，p9的转发跳数为8、转发副本数为3，同理，15号节点将消息p11和p12转发给16号节点。

判断进行消息转发后的节点的缓存空间是否达到了其存储阈值，在本实例中，需要判断15号节点和16号节点的缓存空间是否达到了其存储阈值，以15号节点为例，假设15号节点的缓存空间为200M，则其存储阈值为160M，如果此时15号节点所使用的缓存空间的大小达到了160M，则判断节点中是否有消息的转发跳数达到了转发跳数阈值或消息的转发副本数达到了转发副本数阈值，如果有，则删除相应的消息，然后判断此时节点的输入消息量和输出消息量来判断是否进行进一步的拥塞避免操作；否则直接判断此时节点的输入消息量和输出消息量来判断是否进行进一步的拥塞避免操作。在本实例中，由于15号节点没有转发跳数达到了转发跳数阈值或消息的转发副本数达到了转发副本数阈值的消息，则直接判断此时节点的输入消息量和输出消息量来判断是否进行进一步的拥塞避免操作，假设此时15号节点中消息的输出量为50M，输入量30，则不做进一步的拥塞避免操作。否则，采用DTN消息优先级划分方法对每个节点中的消息进行优先级的划分，此时每个节点中的消息被划分为一级消息、二级消息、三级消息。其中一级消息的优先级最高，三级消息的优先级最低，然后将节点中的三级消息的TTL减半，假设在15号节点中消息p8和消息p9的消息为一级消息，消息p10和消息p11为二级消息，消息p12为三级消息，则将消息p12的TTL减半。

本发明的主要优点：(1)通过对网络中的节点设置存储阈值，使得节点在未达到拥塞时就进行缓存释放，从而实现节点拥塞现象的避免。(2)通过对网络中消息设置消息转发跳数阈值和消息转发副本数阈值，使得当节点缓存达到存储阈值时，通过删除消息的跳数和消息的副本数达到阈值的消息，从而可以有效的控制网络中消息副本数，实现网络拥塞避免。(3)当节点缓存空间的使用情况达到存储阈值时，通过删除消息的跳数和消息的副本数达到阈值的消息来释放缓存空间。然后判断此时节点的输入消息量和输出消息量的大小，当输入消息量大于输出消息量时，通过对节点中消息进行优先级的划分，将优先级最低的消息的TTL减半，从而可以尽快释放节点缓存空间，达到网络中拥塞现象避免的目的。