容迟网络^{[ 1, 2]}泛指由于网络拓扑结构不断变化,导致端到端之间没有稳定链路甚至大部分时间处于中断状态的一类网络。2003年,Fall^{[ 3]}在国际会议SIGCOMM上提出了这一概念。传统的无线网络传输模式要求源节点和目的节点之间存在可靠的传输路径,然而容迟网络中由于节点的移动性和连接的间歇性导致传统的路由算法不再适合该网络环境,因此DTN中加入了新的协议层次捆绑层(bundle layer),在该层中引入了“存储—携带—转发^{[ 4]}”的思想和逐跳传输模式来实现节点间的通信,为应对容迟网络高延迟、易中断等带来的传输可靠性下降问题,引入了保管传递(CT)机制^{[ 5]},即除非TTL到期,否则一条保管传输的消息在没找到下一跳可靠传输节点前不能被删除,但是这样很可能会导致网络中存在大量报文副本进而造成拥塞现象。

本文提出了基于马尔可夫^{[ 6, 7]}相遇时间间隔预测的拥塞控制策略,该策略应用马尔可夫模型对携带报文的源节点和该报文的目的节点之间的相遇时间间隔序列进行预测,在预测出缓存的报文中哪一个最有可能最早遇到其目的节点之后,通过模型将这种可能性量化,进而通过量化值结合报文剩余TTL对其进行缓存排序,提出一种新的拥塞控制方法中的排队策略。根据报文在网络中已经复制或者传递的次数确定该报文已经交付到目的节点的可能性,根据剩余TTL值确定该报文未来可能交付到目的节点的可能性,再根据马尔可夫模型预测到的时间间隔即可确定报文下几跳到达目的节点的可能性,结合这三种可能性确定报文在缓存中的丢弃策略^{[ 8]},最后将排队策略和丢弃策略结合应用到节点缓存的管理中,即得到本文所述的基于马尔可夫相遇时间间隔预测的拥塞控制策略。

目前在容迟网络的研究领域中,更多的研究人员将重点放在路由算法的创新和改进上,很多研究者都会做出节点资源无限性的假设^{[ 9, 10]},而没有考虑实际中所发生的节点缓存拥塞现象。

现有的节点级拥塞控制方法主要有:①Drop Front(DF)^{[ 11]}:首先丢弃缓存空间中排队时间最长的报文;②Drop Last(DL):首先丢弃缓存空间中最新被接收到的报文;③Drop Oldest(DO)^{[ 12]}:首先丢弃缓存空间中剩余生命期(TTL)最小的报文;④Drop Youngest(DY):首先丢弃缓存空间中剩余生命期最大的报文。其中在一些特定场景中DF和DO表现出比较好的性能,这是由于其主要思想是丢弃已经在网络中存活比较久的报文,这些报文的剩余生命周期一般较短,投递到目的节点的可能性较小,因而可以将其丢弃而达到合理化利用资源的目的。

王贵竹等^{[ 13]}提出了容迟网络中基于报文质量的拥塞控制策略,主要是通过剩余TTL和报文已经复制的次数来计算报文质量,当节点缓存发生拥塞时优先丢弃质量较差的报文。John B等^{[ 14]}提出了Maxprop路由策略,将每个节点报文依据跳数多少分为两组,当节点缓存满而又要接收并存储新的报文时,就对这些报文按照其被递交的可能性逐个丢弃。刘期烈等^{[ 15]}在DTN中提出基于复制率的拥塞控制算法,把报文在网络中的复制次数与报文的生成时间做比值,得到复制率,通过丢弃缓存中复制率较低的报文达到缓存优化的效果。

以上对于容迟网络中拥塞控制的研究^{[ 16, 17]}都是考虑报文本身的一些性质,比如剩余TTL、复制的次数等,而没有考虑所携带报文的节点与报文上标有的目的节点相遇的可能情况,本文考虑执行路由算法时有可能存在以下两种情况:

(1)携带报文的节点很快就与该报文的目标节点相遇,但是该报文被排到了队尾,而导致没有将其发送成功。

(2)很快将要与目的节点相遇的报文虽然没有排到队尾,但是由于节点缓存发生拥塞,而导致将该报文丢弃。

这样的两种情况在实际的缓存拥塞控制策略中都是不可以接受的,为了改变这种现状,本文提出了基于马尔可夫相遇时间间隔预测的DTN拥塞控制策略,通过马尔可夫模型预测携带报文的节点与目的节点的相遇时间间隔,将预测得到的下一个时间间隔看成报文效用权值,并通过权值来确定缓存中的排队策略和丢弃策略。

本文使用THE ONE模拟器对提出的基于马尔可夫相遇时间间隔预测的拥塞控制策略CCSMP进行仿真和性能评估。仿真的环境是THE ONE中默认的赫尔辛基城市地图,网络中共存在100个节点,分为3组,共同模拟移动的车辆,移动速度为3~7 m/s,第一组车辆移动模型采用随机行走模型^{[ 18]},模拟一些没有明确目的的车辆,比例占总节点数的40%;第二组车辆的移动模型中加入了兴趣节点,设置的兴趣参数为0.8,使这组节点中的车辆有0.8的概率向特定地点移动,用来模拟那些有特定习惯的车辆,比例占总节点数的30%;第三组车辆的移动模型采用固定路径,移动模型为ONE模拟器中自带的MapRouteMovement,这组节点用来模拟公交线路上的公交车,比例占总节点数的30%。节点之间的通信接口采用蓝牙通信协议。具体的参数配置详见表1。

表1

Table 1

表1(Table 1)

表1 仿真参数列表 Table 1 List of simulation parameters 参数 值 仿真时间/s 5000 仿真区域大小/(m×m) 4000×4000 节点移动速度/(m·s-1) 3~7 停留时间/s 0~120 传输速度/(kbitp·s-1) 120,250,380,510,640,770 传输范围/m 50

表1 仿真参数列表 Table 1 List of simulation parameters

同时为了说明CCSMP的适用性,在Epidemic,Spray and wait两种路由协议中分别应用CCSMP,与DO和DF两种拥塞控制对比产生实验数据,相同场景下,分别更改缓存大小,传输速率(网络带宽),从以下4方面评估协议的性能:

(1)投递概率=成功投递到目的节点的报文数量/网络中产生的报文总数;

(2)平均时延=消息到达目的节点的平均时间;

(3)负载比率(开销比)=(利用连接成功传递包的次数-传递到目的节点的包的个数)/传递到目的节点的包的个数;

(4)丢包率=TTL(过期或者Buffer满了被丢弃的报文数/产生的报文总数)。

在表1所设的环境参数下,所有节点执行Epidemic路由方法,将缓存大小依次改为5、10、15、20、25、30 MB,分别测得本文提出的CCSMP,传统的DO以及DF三种拥塞控制策略下的投递成功率(见图3),网络平均时延(见图4),负载比率(见图5)以及丢包率(见图6)。其中负载比率能反映连接的使用效率,负载比率高说明更多的连接用来传递的数据包都没能成功传递到目的节点,连接的使用效用较低。负载比率低反而说明连接的有效使用率高。其中DO策略没有排队机制,采用的是丢弃策略,首先丢弃缓存空间中剩余生命期( TTL)最小的报文。DF同样没有排队机制,采用的丢弃策略是首先丢弃缓存空间中排队时间最长的报文。

图3

Fig.3

	Figure Option ViewDownloadNew Window
	图3 不同缓存下的投递成功率Fig.3 Delivery ratio of different cache

图4

Fig.4

	Figure Option ViewDownloadNew Window
	图4 不同缓存下的平均时延Fig.4 Delay of different cache

图5

Fig.5

	Figure Option ViewDownloadNew Window
	图5 不同缓存下的负载比率Fig.5 Overhead of different cache

图6

Fig.6

	Figure Option ViewDownloadNew Window
	图6 不同缓存下的丢包率Fig.6 Drop rate of different cache

从图3中数据得出随着缓存大小的不断增加,本文提出的基于马尔可夫相遇时间间隔预测的拥塞控制策略CCSMP的投递概率始终大于DO和DF两种控制策略下的投递成功率,这说明经过了CCSMP拥塞控制显著提高了Epidemic路由算法的投递成功率。图4中CCSMP的网络平均时延比另外两种控制策略低200 s左右的时间,并且随着缓存大小的增加呈现一种稳定趋势,这说明CCSMP拥塞控制策略在增加投递成功率的同时也减小了网络时延。对比图5中3种拥塞控制策略的负载比率,负载比率高说明成功投递的报文占报文成功传递总次数的比率低,进一步说明无用的数据传输比较多,CCSMP的负载比率明显小于DO和DF,说明本文提出的拥塞控制策略从一定程度上也减少了网络开销。从图6中数据可以看出:随着缓存大小的增加,丢包率显著降低,但是CCSMP的丢包率一直小于另外两种拥塞控制策略,平均小10%左右。

为了分析不同的传输速率是否会对文中提出的拥塞控制策略产生影响,实验采用120、250、380、510、640、770 kbit/s 6种传输速度作仿真,在相同的场景下对比CCSMP、DO、DF三种拥塞控制策略的投递成功率(见图7)、平均时延(见图8)以及负载比率(见图9)和丢包率(见图10)。

图7

Fig.7

	Figure Option ViewDownloadNew Window
	图7 不同传输速率下的投递成功率Fig.7 Delivery ratio of different transmit speed

图8

Fig.8

	Figure Option ViewDownloadNew Window
	图8 不同传输速率下的平均时延Fig.8 Delay of different transmit speed

图9

Fig.9

	Figure Option ViewDownloadNew Window
	图9 不同传输速率下的负载比率Fig.9 Overhead of different transmit speed

图10

Fig.10

	Figure Option ViewDownloadNew Window
	图10 不同传输速率下的丢包率Fig.10 Drop rate of different transmit speed

由图7可知,随着传输速率的增加DF和DO两种策略的投递成功率趋于稳定,没有大幅度抖动,而CCSMP的投递成功率有些许上升,并且持续处于比较高的状态。图8中传输速率的变化同样没有严重影响拥塞控制策略下的网络时延,CCSMP的平均时延始终比其他两种控制策略小200 s左右,说明该拥塞控制协议的平均时延受传输速率影响不大。从图9中可见当传输速率较小时,网络的负载比率与拥塞控制协议关系不大,但是随着传输速率的增长,CCSMP的负载比率明显小于DF和DO,说明文中提出的拥塞控制协议能够一定程度上减小网络负载,最后从图10中数据可以看出丢包率随着传输速率的增加明显增大,但是CCSMP相比于DF和DO两种拥塞控制策略丢包率较小。

为了说明CCSMP并不局限于Epidemic路由策略,本文在完全相同的实验环境下,对Spray and wait路由协议下的3种拥塞控制策略同样进行了测试,考虑到Sspray and wait对报文的副本数做了控制,从一定程度上预防了拥塞的发生,所以针对Spray and wait路由算法的缓存大小设置为2、5、8、10 M,报文初始副本数定义为6,测得投递成功率(见图11),网络平均时延(见图12),负载比率(见图13)和丢包率(见图14)。

图11

Fig.11

	Figure Option ViewDownloadNew Window
	图11 不同缓存下的投递成功率Fig.11 Delivery ratio of different cache

图12

Fig.12

	Figure Option ViewDownloadNew Window
	图12 不同缓存下的平均时延Fig.12 Delay of different cache

图13

Fig.13

	Figure Option ViewDownloadNew Window
	图13 不同缓存下的负载比率Fig.13 Overhead of different cache

图14

Fig.14

	Figure Option ViewDownloadNew Window
	图14 不同缓存下的丢包率Fig.14 Drop rate of different cache

从图11中数据可以看出,当缓存较小的时候CCSMP拥塞控制策略相比于DF和DO能够增加投递成功率,但当缓存增大到一定程度就不会再有明显的差别,这主要是因为这种情况下缓存大小足够承受初始报文为6的网络报文量,拥塞发生的较少。从图12中数据可以看出在缓存较少的情况下CCSMP有着更小的网络时延。分析图13和14可知CCSMP与其他两种拥塞控制策略相比能在一定程度上减少负载比率和丢包率。

为了在Spray and wait路由算法下分析不同的传输速率对文中提出的拥塞控制策略产生的影响,将缓存大小设置为5 MB,实验采用120、250、380、510、640、770 kbit/s 6种传输速度作仿真,得到投递成功率(见图15)、平均时延(见图16)以及负载比率(见图17)和丢包率(见图18)。

图15

Fig.15

	Figure Option ViewDownloadNew Window
	图15 不同传输速率下的投递成功率Fig.15 Delivery ratio of different transmit speed

图16

Fig.16

	Figure Option ViewDownloadNew Window
	图16 不同传输速率下的平均时延Fig.16 Delay of different transmit speed

图17

Fig.17

	Figure Option ViewDownloadNew Window
	图17 不同传输速率下的负载比率Fig.17 Overhead of different transmit speed

图18

Fig.18

	Figure Option ViewDownloadNew Window
	图18 不同传输速率下的丢包率Fig.18 Drop rate of different transmit speed

根据图15中的数据,在节点本地只有5 MB缓存的情况下CCSMP表现出了更好的投递成功率,并且随着传输速率的提升投递成功率呈稳步上升趋势。在图16中CCSMP的平均时延远小于DF和DO两种拥塞控制策略。从图17的数据可以看出CCSMP的负载比率随着传输速度的变化没有大幅度波动,并且处于较低的状态,同样在图18中可以看出CCSMP在不同的传输速率下有着更小的丢包率。

提出了一种基于马尔可夫相遇时间间隔预测的拥塞控制策略CCSMP,该策略包括排队机制和丢弃机制两部分,并将马尔可夫模型应用到节点的相遇时间间隔的预测上,通过预测值结合报文复制或者传递的次数和剩余 TTL值来计算报文的效用权值,通过这个权值可以决定缓存中的排队顺序和丢弃方式。为了验证工作的有效性,在THE ONE平台上对Epidemic和Spray and wait两种路由协议进行仿真,将CCSMP与DF和DO两种拥塞控制策略进行对比,仿真结果表明CCSMP能够明显地增加投递成功率,减小平均网络时延,并且在一定程度上减小了网络负载和丢包率。