前言：寻找写作灵感？中文期刊网用心挑选的马尔可夫相遇间隔预测拥塞控制策略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值的大小进行排队，进而得出了我们的排队策略。#p#分页标题#e#
3.丢弃策略
本文认为可以依据以下三点原则制定拥塞控制中比较好的丢弃策略。(1)已经成功交付到目的节点的报文应该优先从缓存中丢弃，这里我们讨论的路由协议不包含目的节点接受到报文后的ACK确认机制，所以携带报文的节点不知道该报文是否已经成功投递到目的节点。(2)虽然报文没有交付到目的节点，但是因为报文剩余的TTL较少，导致报文成功投递的可能性非常小，这样的报文也应该从缓存中丢弃掉。(3)虽然报文剩余的TTL较小，但是通过基于马尔可夫相遇时间间隔预测模型预测得到的携带该报文的节点与该报文中标识的目的节点的下一个相遇时间间隔很小，这样的报文可以暂时留下，有可能在很小的TTL内成功交付到目的节点。综上所述，报文是否丢弃的依据有以下三点：报文已经交付到目的节点的可能性，报文剩余TTL数，以及基于马尔可夫相遇时间间隔预测模型预测得到的状态值。由此可以得到拥塞控制策略中的丢弃策略。
本文认为路由协议中报文在容迟网络中被传递或复制的总次数最能反映报文已经成功交付到目的节点的可能性，报文传播到的节点的个数越多，说明报文蔓延范围越广，接触到目的节点的可能性也就越大。本文在报文的尾部加入一个字段N，用来准确地统计报文总共感染到的节点的个数，统计策略如下：每当节点之间相遇的时候，所有传递出去的报文在发送节点和接收节点上的N字段都加1，如果相遇的两个节点有相同的报文，但是报文在N字段上的数值不一样，就用数值大的报文替换掉数值小的报文，这样一段时间以后网络中多数报文的N字段可以反映报文感染到的节点的个数，记为M，统计流程如图2。报文的剩余TTL值记为T。报文基于马尔可夫相遇时间间隔预测模型预测得到的状态值记为P。则衡量报文是否应该丢弃的报文权值D表示如（9）式：（略）M值越小说明投递到目的节点的可能性越小，说明该报文越应该保留，剩余TTL值越大，T值越大说明该报文越应该保留，P值越大说明预测其与目的节点很快就能相遇，这样的报文也应该保留，所以优先丢弃掉D值小的报文是合理的。其中1C2C和3C是通过实验确定的比例因子，通过实验分析分别设为0.5,0.3和0.2。
4.拥塞控制策略CCSMP流程
1）拥塞检测：CCSMP的拥塞检测主要是进行简单的以下两个判断,其中LM为要接收的报文大小，L为接收节点的本地缓存剩余容量,A为接收节点本地缓存大小：(1)LM<L则没有发生拥塞，正常传输报文，然后将新到的报文和缓存中原有的报文重新执行排队策略。(2)LM>A则直接丢弃该报文。(3)A>LM≥L则发生了拥塞，进入到拥塞避免机制，进行报文的选择性丢弃。2.4.2拥塞避免(1)本地维护一张丢弃过的报文记录，当节点接收到要传输过来的报文时，优先对比报文记录如果在其中或者节点缓存中已经有这条报文则直接丢弃新到报文，否则转到步骤（2）。(2)执行2.3中的丢弃策略，对比缓存中已有的报文和新到的报文，计算每个报文的丢弃权值D，找出其中D值最小的报文，将其丢弃，如果丢弃这个报文之后缓存区仍然溢出，则找到D值其次小的进行丢弃，直到缓存区不再发生拥塞，转到步骤（3）。(3)将丢弃掉的报文放入丢弃报文记录中，并将剩余报文执行2.2节中的排队策略。
仿真结果与分析
本文使用THEONE模拟器对提出的基于马尔可夫相遇时间间隔预测的拥塞控制策略CCSMP进行仿真和性能评估。仿真的环境是THEONE中的默认地图：赫尔辛基城市地图，网络中共存在着100个节点，分为3组，共同模拟移动的车辆，移动速度为3-7米每秒，第一组车辆移动模型采用随机行走模型[18]，模拟一些没有明确目的的车辆，比例占总节点数的40%，第二组车辆的移动模型中加入了兴趣节点，设置的兴趣参数为0.8，使这组节点中的车辆有0.8的概率向特定地点移动，用来模拟那些有特定习惯的车辆，比例占总节点数的30%，第三组车辆的移动模型采用固定路径，移动模型为ONE模拟器中自带的MapRouteMovement，这组节点用来模拟公交线路上的公交车，比例占总节点数的30%。节点之间的通信接口采用蓝牙通信协议。具体的参数配置详见表1。同时为了说明CCSMP的适用性，在Epidemic，Sprayandwait两种路由协议中分别应用CCSMP，与DO和DF两种拥塞控制对比产生实验数据，相同场景下，分别更改缓存大小，传输速率（网络带宽），从以下四方面评估协议的性能:1.投递概率=成功投递到目的节点的报文数量/网络中产生的报文总数2.平均时延=消息到达目的节点的平均时间3.负载比率（开销比）=（利用连接成功传递包的次数-传递到目的节点的包的个数）/传递到目的节点的包的个数4.丢包率=TTL过期或者Buffer满了被丢弃的报文数/产生的报文总数
仿真结果与数据分析
在表1所设的环境参数下，所有节点执行Epidemic路由方法，将缓存大小依次改为5M，10M，15M，20M，25M，30M，分别测得本文提出的CCSMP，传统的DO以及DF三种拥塞控制策略下的投递成功率（见图4），网络平均时延（见图5），负载比率（见图6）以及丢包率（见图7）。其中负载比率能反映连接的使用效率，负载比率高说明更多的连接用来传递的数据包都没能成功传递到目的节点，连接的使用效用较低。负载比率低反而说明连接的有效使用率高。其中DO策略没有排队机制，采用的是丢弃策略首先丢弃缓存空间中剩余生命期（TTL）最小的报文。DF同样没有排队机制，采用的丢弃策略是首先丢弃缓存空间中排队时间最长的报文。从图4中数据得出随着缓存大小的不断增加，本文提出的基于马尔可夫相遇时间间隔预测的拥塞控制策略CCSMP的投递概率始终大于DO和DF两种控制策略下的投递成功率，这说明经过了CCSMP拥塞控制显著提高了Epidemic路由算法的投递成功率。图5中CCSMP的网络平均时延比另外两种控制策略低200s左右的时间，并且随着缓存大小的增加呈现一种稳定趋势，这说明CCSMP拥塞控制策略在增加投递成功率的同时也减小了网络时延。对比图6中3种拥塞控制策略的负载比率，负载比率高说明成功投递的报文占报文成功传递总次数的比率低，进一步说明无用的数据传输比较多，CCSMP的负载比率明显小于DO和DF，说明本文提出的拥塞控制策略从一定程度上也减少了网络开销，从图7中数据可以看出随着缓存大小的增加，丢包率显著降低，但是CCSMP的丢包率一直小于另外两种拥塞控制策略，平均小一个百分点左右。为了分析不同的传输速率是否会对文中提出的拥塞控制策略产生影响，实验采用120Kbps,250Kbps,380Kbps,510Kbps,640Kbps,770Kbps6种传输速度作仿真，同样是在相同的场景下对比CCSMP，DO，DF三种拥塞控制策略的投递成功率（图8），平均时延（图9）以及负载比率（图10），丢包率（图11）。从图8中数据经分析得出如下结论：随着传输速率的增加DF和DO两种策略的投递成功率趋于稳定，没有大幅度抖动，而CCSMP的投递成功率有些许上升，并且持续处于比较高的状态。图9中传输速率的变化同样没有严重影响拥塞控制策略下的网络时延，CCSMP的平均时延始终比其他两种控制策略小200s左右，说明该拥塞控制协议的平均时延受传输速率影响不大。从图10中可见当传输速率较小时，网络的负载比率与拥塞控制协议关系不大，但是随着传输速率的增长，CCSMP的负载比率明显小于DF和DO，说明文中提出的拥塞控制协议能够一定程度上减小网络负载,最后从图11中数据可以看出丢包率随着传输速率的增加明显增大，但是CCSMP相比于DF和DO两种拥塞控制策略丢包率较小。为了说明CCSMP并不局限于Epidemic路由策略，本文在完全相同的实验环境下，对sprayandwait路由协议下的3种拥塞控制策略同样进行了测试，考虑到sprayandwait对报文的副本数做了控制，从一定程度上预防了拥塞的发生，所以针对sprayandwait路由算法的缓存大小设置为2M，5M，8M和10M，报文初始副本数定义为6，测得投递成功率（图12），网络平均时延（见图13），负载比率（见图14）和丢包率（见图15）。从图12中数据可以看出，当缓存较小的时候CCSMP拥塞控制策略相比于DF和DO能够增加投递成功率，但当缓存增大到一定程度就不会再有明显的差别，这主要是因为这种情况下缓存大小足够承受初始报文为6的网络报文量，拥塞发生的较少。从图13中数据可以看出在缓存较少的情况下CCSMP有着更小的网络时延。图14和15中分析得出CCSMP与其他两种拥塞控制策略相比能在一定程度上减少负载比率和丢包率。为了在sprayandwait路由算法下分析不同的传输速率对文中提出的拥塞控制策略产生的影响，将缓存大小设置为5M，实验采用120Kbps,250Kbps,380Kbps,510Kbps,640Kbps,770Kbps6种传输速度作仿真，得到投递成功率（图16），平均时延（图17）以及负载比率（图18），丢包率（图19）。#p#分页标题#e#
根据图16中的数据，在节点本地只有5M缓存的情况下CCSMP表现出了更好的投递成功率，并且随着传输速率的提升投递成功率呈稳步上升趋势。在图17中CCSMP的平均时延远小于DF和DO两种拥塞控制策略。从图18的数据可以看出CCSMP的负载比率随着传输速度的变化没有大幅度波动，并且处于较低的状态，同样在图19中可以看出CCSMP在不同的传输速率下有着更小的丢包率。
结束语
本文提出了一种基于马尔可夫相遇时间间隔预测的拥塞控制策略CCSMP，该策略包括排队机制和丢弃机制两部分，并将马尔可夫模型应用到节点的相遇时间间隔的预测上，通过预测值结合报文复制或者传递的次数和剩余TTL值来计算报文的效用权值，通过这个权值可以决定缓存中的排队顺序和丢弃方式。为了验证工作的有效性，在THEONE平台上对Epidemic和Sprayandwait两种路由协议进行仿真，将CCSMP与DF和DO两种拥塞控制策略进行对比，仿真结果表明CCSMP能够明显的增加投递成功率，减小平均网络时延，并且在一定程度上减小了网络负载和丢包率。（本文图、表略）
本文作者：杨永建 王恩 杜占玮 单位：吉林大学 计算机科学与技术学院