1. 引言
现今的网络性能分析与保障大多以排队论作为基础理论。通信中时延的可靠性与服务系统的缓存行为有着密切的关系,排队论通过将各个网络节点建模为排队系统,并且利用合适的数学模型描述网络中流通的数据流量和节点提供的传输策略,完成对特定场景中网络节点缓冲区数据流量处理过程的描述 [1] 。
在鞅论研究领域中,Doob提出的Doob不等式为其他研究团队进一步研究鞅论奠定了基础,为鞅理论的探索提供了更多的可能性。F. Ciucu、F. Poloczek以及他们的团队在基于鞅论的通信系统的研究中,实现了许多研究上的突破 [2] - [8] 。他们的团队在满足网络通信的QoS (Quality-of -Service)条件下,通过将排队过程中存在的不等关系和鞅论相结合,将这种理论应用在通信问题的研究之中,以实现更优化的解决方案。具体来说,他们以创新的方式,构建了到达过程和服务过程的鞅结构。并且将网络中流量的累计到达过程和交换机、路由器等提供的服务过程,建模成具有指数超鞅形式的表达式。通过利用鞅理论的性质,以开创性的方式将节点的缓存行为从鞅论的视角触发进行数学建模,并进一步分析了时延可靠性和QoS指标等性能界限。在文献 [9] 中,研究者对于异质到达流网络进行了探索。这种网络既包括蜂窝通信的接入点,也包括通过轨道侧接入的基站。研究者通过构建超鞅模型来研究该网络的端到端时延性能,并证明了使用鞅论分析通信时延对比传统方法具有紧致性。在文献 [10] 中,基于文献 [9] 的研究基础,研究者对节点的服务系统建立了马尔可夫决策过程模型,针对异质业务的时延QoS要求,提出了一种混合调度机制。该实验中,通过使用实测数据验证鞅论确实可以得到更紧致的时延界限。 [7] 、 [11] 和 [12] 的研究人员提出了一种通过适当的指数鞅构造来分析延迟违规概率的上界的方法。所得到的上界相对于现有技术提高了几个数量级 [7] 。 [12] 团队在计算卸载场景中扩展了鞅分析框架,以便可以精确评估延迟性能以指导资源分配和流量卸载。 [13] 提出了一种差异化的ALOHA (Additive Link On-line Hawaii system)随机接入算法,其中利用基于鞅的延迟违规概率约束来制定能效最大化问题。鞅过程是包容性的,可以通过鞅构造为各种随机过程提供模块化描述方法。同时,它支持我们对积压过程建模,即到达过程和服务过程之间的差异。关于鞅的紧密不等式结论也是准确的延迟分析的重要辅助,胡等人 [14] 针对具有马尔可夫调制到达和服务过程的多跳系统,通过鞅导出了延迟违规概率的严格界限。这个框架在 [15] 和 [16] 中也被采用。 [15] 通过考虑THz无线网络中分子吸收引起的复杂信道特性,分析了虚拟现实服务的端到端延迟可靠性。在 [16] 中,利用边缘计算场景下的两个功率级别分时ALOHA非正交多址接入方案,得到了端到端延迟的互补累积概率分布。
本文致力于研究网络时延性能分析的新理论,基于鞅论构建鞅框架下的统计型可靠性保障新方法,并开发新的算法。针对有时延可靠性要求的业务,提出单跳时延性能分析鞅框架。通过对突发到达流和服务过程进行鞅构造,得出时延违反概率和时延之间的关系。对突发到达流和服务过程分别进行了基于鞅论和基于有效带宽/容量理论的实验。仿真结果表明,对于突发到达流来说,采用鞅构造对比采用传统的有效带宽/容量理论而言得到的时延违反概率更加紧致。
2. 鞅理论基本定义
鞅(Martingale)的本质其实就是一种随机过程,它的特殊性质使它对比其他随机过程序列而言拥有独特的魔力。具体来说,满足以下属性的随机过程称为鞅:当前时刻为n,如果在此之前的信息是已知的,并作为条件,那么随机过程在n时刻的值等于在已知信息下n + 1时刻值的条件期望。可通过数学形式描述鞅:
若随机序列
,
则对任意n ≥ 0有:
则称
为离散鞅序列,简称鞅。为了便于理解鞅的性质,用打麻将做例子对其进行解释:
Xn表示为玩家在打到第n局时的本金;
表示在前n局中每一局的本金都已知,即在
已知的前提下,他在第n + 1局打麻将时的平均本金,则在符合鞅属性的打麻将的过程中,玩家会发现他的本金的总满足表达式
,这表示玩家在打麻将这一随机过程中,第n + 1次的平均本金与第n次的本金相等。换句话说,玩家无论如何利用第n时刻之前所获得的信息,在下一时刻所拥有本金的期望只能是Xn。这说明,具有鞅性质的麻将运动是一个公平竞技游戏。
此外,也可以通过鞅的构造来为随机过程构造他的鞅过程。
及
为两个随机序列。则对任意n ≥ 0有:
则称
是关于
的鞅,简称
为鞅。事实上,通过对随机过程进行鞅构造后再进行下一步处理在涉及鞅论的实验中更常用。
3. 鞅的构造
已有研究指出,在使用鞅方法时,首先要解决的是鞅的构造问题,这涉及到判断鞅理论在通信网络建模中的适应性。通过一系列的数学建模,可以得到更精确的排队系统性能概率界限。本研究旨在通过融合鞅论与排队论,探讨网络的统计型服务质量(QoS)保障问题,并旨在5G网络面临突发性流量业务时,推导出更严格的时延界限。在实际的求解过程中,关键在于构造排队过程中的鞅,并利用鞅的良好性质来分析排队模型。
3.1. 到达过程鞅的构造
对于通信网络中的QoS数据流,可以根据QoS指数映射到节点上。设在时隙n时,某一节点到达的数据包数量为a(n),则对于任意大于零的QoS指数θ,存在不小于零的鞅参量Ka(θ)和ha(θ),使得对应切片上流量到达的过程可以构造为鞅,即在该节点上有如下形式的到达鞅:
(1)
其中A(n)该节点上数据流量的累计到达过程,Ka和ha为到达鞅过程的鞅参量,它们的取值都与θ有关,节点上的鞅参量Ka的取值可以由下式确定:
(2)
即由该节点接收到随机到达流量数据包的指数平均求得。
3.2. MMOO (Markov Modulated on Off)到达过程鞅的构造
节点上的到达过程a(n)被建模成马尔可夫调制开关随机过程。节点上该数据业务要求的QoS指数为θ,则根据前面介绍鞅的性质,在时隙n时,节点上的到达过程可以构造成如下的超鞅形式:
(3)
鞅参量Ka(θ)和ha(θ)的取值也都根据节点中数据流量要求而依赖于QoS指数θ。对其做出指数列变换,定义矩阵Tθ为:
(4)
将节点中到达过程构造的鞅参量ha(θ)取值为矩阵Tθ的右特征向量,即最大特征值。Ka(θ)取值表达式由累计到达的指数一阶中心矩确定,表达式为:
(5)
3.3. 服务鞅的构造
在节点中,将排队系统服务过程S(n)构建为伯努利过程,也进一步构造出指数形式的鞅:
(6)
在(6)中,存在一个关于构造鞅过程的鞅参数Ks(θ)和一个函数hs(θ),参数Ks(θ)和hs(θ)。通常选取hs(θ) = 1,Ks(θ)的取值由指数变换平均值确定:
(7)
其中P为服务的概率,C为每次服务的数据包。
4. 基于鞅的时延违反概率上界
假设统计独立过程A(n)和S(n)满足到达鞅和服务鞅,定义:
(8)
ha和hs可以通过上一节求出,阈值H定义为:
(9)
直观上说,H是使瞬时到达x大于任意时刻服务过程y这一关系成立的ha(x)hs(y)的最小值。
E[ha(a0)]为选取的ha的期望,以到达过程为二元马尔可夫调制过程为例,用数学形式表示就是:
(10)
E[hs(s0)]的选取遵循同样的法则,由于通常hs = 1,所以通常E[hs(s0)] = 1。
有了(8),(9),(10),就可以推导出时延违反概率和时延之间的关系:
(11)
5. 仿真结果分析
下面对理论部分进行仿真
Figure 1. Simulation chart of time-delay boundary based on martingale and effective bandwidth/capacity theory
图1. 基于鞅论和有效带宽/容量理论的时延界限仿真图
图1中是分别是利用鞅论和有效带宽/容量理论进行仿真得到的结果,其中到达过程建模为MMOO过程,其转移概率矩阵为
(12)
其中0表示没有数据包到达,1表示有数据包到达并且每一个到达流都含有20个数据包。
服务过程建模为伯努利过程,其参数为
(13)
即有0.6的概率进行服务,每次可服务30个数据包。
从图1中可知,当时延界限确定时,鞅论得到的时延阈值更低,即对于突发到达流来说,鞅论对比有效带宽/容量理论可以获得更紧致的时延界。
下面讨论到达过程突发性对实验结果的影响。MMOO过程的平均到达速率为
。MMOO到达的突发性可以通过
来测量,即c2是方差系数。
Figure 2. Simulation graph of the two theoretical delay bounds for: Rav = 60, c2 = 0.2
图2. Rav = 60,c2 = 0.2时两种理论的时延界限仿真图
Figure 3. Simulation graph of the two theoretical delay bounds for: Rav = 60, c2 = 0.6
图3. Rav = 60,c2 = 0.6时两种理论的时延界限仿真图
图2、图3是在平均到达速率Rav相同的情况下,突发性不同的两个基于鞅论和基于有效带宽/容量理论的实验。两个实验的平均到达速率都是60个数据包,实验一的方差系数c2 = 0.2,实验二的方差系数c2 = 0.6,可以明显看出在平均到达数率相同时,到达过程的突发性越强(方差系数越大),鞅论等到得理论时延界限对比有效带宽/容量理论更紧致。
6. 结论
本文对鞅论及鞅的构造做了基本的介绍,并利用了鞅论和有效容量/有效带宽理论对节点接收到突发到达流的情况进行了理论仿真。实验结果表明,在面对突发业务时,鞅论对比有效容量/有效带宽理论得到的时延界更为紧致。