马尔可夫相遇间隔预测拥塞控制策略CCSMP

相关工作

目前在容迟网络的研究领域中，更多的研究人员将重点放在路由算法的创新和改进上，很多研究者都会做出节点资源无限性的假设[9,10]，而没有考虑实际中所发生的节点缓存拥塞现象。现有的节点级拥塞控制方法主要有：(1)DropFront（DF）[11]：首先丢弃缓存空间中排队时间最长的报文。(2)DropLast（DL）：首先丢弃缓存空间中最新被接收到的报文(3)DropOldest（DO）[12]：首先丢弃缓存空间中剩余生命期（TTL）最小的报文。(4)DropYoungest（DY）：首先丢弃缓存空间中剩余生命期最大的报文。其中在一些特定场景中DF和DO表现出比较好的性能，这是由于其主要思想是丢弃已经在网络中存活比较久的报文，这些报文的剩余生命周期一般较短，投递到目的节点的可能性较小因而可以将其丢弃而达到合理化利用资源的目的。

在文献[13]中，王贵竹等人提出了容迟网络中基于报文质量的拥塞控制策略，主要是通过剩余TTL和报文已经复制的次数来计算报文质量，当节点缓存发生拥塞时优先丢弃质量较差的报文。在文献[14]中JohnBurgess等人提出了Maxprop路由策略，将每个节点报文依据跳数多少分为两组，当节点缓存满而又要接收并存储新的报文时，就对这些报文按照其被递交的可能性逐个丢弃；刘期烈等人在DTN中提出基于复制率的拥塞控制算法[15]，把报文在网络中的复制次数与报文的生成时间做比值，得到复制率，通过丢弃缓存中复制率较低的报文达到缓存优化的效果。以上对于容迟网络中拥塞控制的研究[16,17]都是考虑报文本身的一些性质，比如剩余TTL，复制的次数等等，而没有考虑所携带报文的节点与报文上标有的目的节点相遇的可能情况，文中考虑执行路由算法时有可能存在以下两种情况：1.携带报文的节点很快就与该报文的目标节点相遇，但是该报文被排到了队尾，而导致没有将其发送成功。2.很快将要与目的节点相遇的报文虽然没有排到队尾，但是由于节点缓存发生拥塞，而导致将该报文丢弃。这样的两种情况在实际的缓存拥塞控制策略中都是不可以接受的，为了改变这种现状，本文提出了基于马尔可夫相遇时间间隔预测的DTN拥塞控制策略，通过马尔可夫模型预测携带报文的节点与目的节点的相遇时间间隔，将预测得到的下一个时间间隔看成报文效用权值，并通过权值来确定缓存中的排队策略和丢弃策略。

基于马尔可夫相遇时间间隔预测的拥塞控制策略CCSMP

1.基于马尔可夫相遇时间间隔预测模型

在某些含有兴趣节点的场景中，比如校园网络中学生经常出现在教学楼，食堂和宿舍，这些节点间的相遇并不是偶然的，或者说节点之间相遇的时间间隔存在着一种内在规律，因此他们可以通过马尔可夫模型统计以往的时间间隔序列来预测下一个时间间隔的大致范围，这样就能够尽可能准确的找到缓存中有可能最早交付的报文。文中为了将节点间的相遇时间间隔量化，以便用于马尔可夫模型中进行预测，进而在本文的实验环境中测试了所有节点之间相遇时间间隔的分布(图1)。从图1中数据可以看出节点间的时间间隔主要分布在0-2000秒之间，而文中需要根据时间间隔来预测节点间未来的相遇能力，较长的间隔时间对预测不会带来很大的帮助，基于上述考虑主要对1000秒以内的时间间隔做预测，故在马尔可夫模型中将两个节点相遇的时间间隔记为随机变量X，且序列iX满足一种时间离散状态离散的马尔可夫链[14]，取网络中的两个节点，全程记录两个节点的时间间隔序列iX，并且将iX按照给定范围不失一般性地划分为10种状态。当0＜iX?100时记为状态10，当100＜iX?200时记为状态9，当200＜iX?300时记为状态8，当300＜iX?400时记为状态7，当400＜iX?500时记为状态6，当500＜iX?600时记为状态5，当600＜iX?700时记为状态4，当700＜iX?800时记为状态3，当800＜iX?900时记为状态2,当900＜iX时记为状态1，故任意两个节点的相遇情况都可以通过一个由1-10组成的状态序列ia表示。本文所提出的基于马尔可夫相遇时间间隔预测模型可以表示为(S，P，K)，其中S是系统所有可能的状态所组成的非空的状态集，本文即为iX划分出的10种状态(1-10)。P为状态转移矩阵，见（3）式，其中ijijiPnum/num，表示两个节点最近一次相遇时间间隔为i并且下一次相遇时间间隔为j的概率，其中ijnum表示前一次相遇时间间隔为i下一次相遇时间间隔为j的次数，inum表示相遇时间间隔i一共出现的次数。K为当前状态矩阵（1行N列），表示为（4）式，如果当前的相遇时间间隔为k，则K中第k列的数值为1，其他列的数值为0。本文认为一些节点之间的相遇时间间隔并不是随机选取的，下一次的相遇时间间隔与最近一次的相遇时间间隔有关，而与之前的相遇情况无关，故根据马尔可夫链的性质：（略）式中iT表示第i次相遇的时间，iX表示第i次与第i+1次相遇间隔时间，ia表示相遇时间间隔所在的状态，区间为[1,10]。iX由每个节点统计，并且以的形式存储于本地数组中。则源节点A与任意节点iB相遇时，首先更新彼此的相遇时间间隔序列，然后查看iB与目的节点的相遇间隔的历史序列，通过历史序列建立状态转移矩阵P，通过历史序列的最后一个状态确定当前状态矩阵K(1×N)，用状态矩阵K乘以状态转移矩阵P，即得预测的下一个相遇时间间隔状态矩阵pK(1×N)（5）。pK中最大的数值所对应的列，即为预测得到的下一个时间间隔的权值。转移矩阵中ijP表示由状态i转移到状态j的概率，由于当进入状态i之后，或者保留在状态i或者进入另外一个状态，故有（6）式。假设某点和目的节点的相遇时间间隔序列为2,1,3,2,4,5,4,1,3,2,6,7,9,8,5,10,7，则状态转移矩阵如（7）式。在（4）中当前状态为7，则对应的K(0000001000)，通过（5）式得到KKP(0000000010)p故预测下一个时间间隔的权值为9。

2.排队策略

在拥塞控制策略中提出排队策略是因为DTN中默认的传输模式是从队首开始逐条报文传送，而容迟网络中节点之间的连接间歇性很强，很有可能在有限的相遇时间内无法传输完所有需要传输的报文，进而导致最应该投递给相遇节点的报文因为排到了队尾或者队尾附近而没有成功传输。本文排队策略的制定主要从以下两方面来考虑：第一方面，一些具有以下特性的报文应该排在缓冲区的队首：携带该报文的节点有可能很快与该报文的目的节点相遇，因为这样的报文有可能直接投递成功。第二方面，具有较大的剩余TTL值的报文应该排在队首，因为这样的报文一般复制次数比较少，网络传染程度比较小，所以应该优先投递，而剩余TTL较少的报文投递成功的可能性较小，因此排在队尾附近。综上所述，提出了基于效用权值进行排队的控制策略，而效用权值W的计算如（8）式（略）。式中lTTL是指报文的剩余TTL，aTTL是指报文初始化的TTL值，而pK则是基于马尔可夫相遇时间间隔预测模型中携带该报文的节点与报文标识的目的节点相遇时间间隔的状态值，如（5）式。则P值越大证明预测的相遇时间间隔越小，该报文越应该排于队首，值越大证明该报文复制的比率越小，这样的报文也应该优先传送。综上所述W值越大说明该报文的效用值越高，所以根据W值的大小进行排队，进而得出了我们的排队策略。