面向无线链路边缘计算的信息峰值年龄分布

摘要

信息年龄（AoI）是许多物联网（IoT）应用中的关键指标，其中传感器通过发送尽可能新鲜的更新来持续监测环境。边缘计算方案的发展使监控过程更接近传感器，从而减少了通信延迟，但必须考虑边缘节点的处理时间。此外，从时效性角度进行可靠的系统设计需要了解峰值AoI（PAoI）的完整分布，以便获得罕见但极具破坏性事件的发生概率。在本研究中，我们将此类系统的通信与计算时延建模为两个串联的先到先服务（FCFS）队列，并解析推导出 M/M/1 – M/D/1和 M/M/1 –M/M/1串联结构下PAoI的完整分布，这些模型可代表多种现实场景。

索引词

信息年龄，信息峰值年龄，边缘计算，排队网络。

一、引言

TRADITIONAL 通信网络将分组时延作为衡量传输延迟要求的唯一性能指标。然而，许多物联网应用需要将某个过程的实时状态更新从生成点传输到远程目的地[1]。传感器网络、车载网络及其他跟踪系统以及工业控制便是此类更新过程的示例。对于这些情况，信息年龄是一个新颖的概念，通过量化接收器处信息的新鲜度，更好地表示时效性要求[2]。基本而言，信息年龄计算的是在任意给定时刻，最新接收到的更新在其生成之后所经过的时间，即目的地接收到的最后一个数据包有多旧。另一种与年龄相关的度量是峰值信息年龄，即最大每次更新的信息年龄值，即下一个数据包被目的地接收时，上一个数据包的年龄。与其他通信系统性能指标类似，当关注最坏情况分析（例如系统需求位于分布尾部）时，峰值信息年龄比平均年龄更具参考价值。举例来说，峰值信息年龄可用于限制网络控制系统的延迟，确保接收器能够掌握发射器状态的最新情况。

边缘计算是一种在对信息年龄敏感的物联网应用中日益受到关注的技术，因为将传感器读数传输到集中式云需要过多时间，并增加不确定性，而在生成数据的传感器附近处理接收的数据可以减少通信延迟以及监控或控制过程可获得的信息的整体年龄[3]。信息新鲜度将成为5G之后及第六代移动通信中的关键参数之一，支持通信、计算、控制、定位与传感（3CLS）服务[4]：这些应用需要联合的感知、计算和通信资源。特别是远程医疗、农业、制造工厂和机器人技术中的服务需要严格的控制性能保证，这只有通过精心设计通信系统才能实现。此外，信息年龄（AoI）和峰值信息年龄（PAoI）通常是控制系统相关的时序度量，因为它们代表了控制器观测到的系统状态与控制动作执行时真实状态之间的时间差。由于这些服务要求高可靠性，仅分析平均年龄是不够的：其分布的尾部也是一个非常重要的参数，因为它直接影响控制系统故障的风险，而这一风险对于关键应用必须限制在极低水平。在这些融合通信与计算的边缘应用中，必须同时考虑两者对信息年龄的贡献。限制处理后信息的年龄是一个关键要求，这可能会影响物联网节点选择本地计算还是基于边缘的计算[5]。当考虑多个源、不同的分组生成行为以及有限的通信能力时，该问题变得更加复杂[6]。

串联队列（特别是最少2个节点的情况）是此类场景的自然建模选择，因为第一个系统表示通信链路，而第二个系统表示具备计算能力的边缘节点及其任务队列。图1显示了一个示例：传感器处的通信缓冲区和边缘节点上的任务队列。

如果具备计算能力的边缘节点上的负载是时不变的，而通信由于动态信道变化和随机接入等原因则较难预测，那么M/M/1 – M/D/1串联队列是一个合适的模型。如果我们假设采用具有完美多包接收（MPR）的ALOHA系统[7]，其中数据包不会因碰撞而丢失，仅会因信道错误而丢失，则 M/M/1队列是信道的合适模型。该模型适用于基于超窄带（UNB）传输的物联网系统，例如 SigFox[9]。另一方面，在文献中计算时间通常被建模为数据大小的线性函数[10],，相同大小的更新具有恒定且确定性的服务时间，因此可由 M/D/1队列表示。另一种方法是将计算负载也视为随时间变化，导致随机计算时间，并用具有不同服务速率[11]的 M/M/1队列来表示这两个系统。

图2中绘制了一个AoI动态的示例：信息年龄随时间线性增长，然后在新更新到达时立即下降。显然，由于每个到达目的地的数据包都已通过中间节点，因此目的地处的年龄永远不会低于中间节点处的年龄，但两者之间的动态关系并不简单，这也正是本研究工作的动机所在。我们分析了具有独立服务时间的两个系统串联队列中峰值信息年龄（PAoI）的分布，其中每个无限队列遵循先来先服务（FCFS）策略。我们考虑了 M/M/1 – M/D/1串联和 M/M/1 –M/M/1两种情况，涵盖了常见的通信中继以及通信与计算结合的场景。我们的目标是推导出具有任意分组生成和服务速率的系统的PAoI完整概率密度函数（PDF），使系统设计者能够使用PAoI阈值定义可靠性要求，并推导出满足这些要求所需的网络规格。

尽管我们的分析动机源于物联网边缘计算，但我们注意到还有其他对年龄敏感的应用可以使用本文的相同模型和结果。例如，串联队列可以用于建模中继网络，其中数据包通过发射器和接收器之间一个或多个带缓冲的中间节点进行传输，以克服两个端点之间的物理距离。一个很好的例子是卫星中继，它通过另一颗卫星连接地面和卫星（或反之）。在这种情况下，链路具有高度不可预测性，并取决于不同的例如定位抖动[12]和上层大气条件等因素。如果不同链路的服务（传输）时间相互独立，则可以用服务器表示连续链路传输的串联队列来描述此类系统。区块链是另一个将信息年龄作为实时验证交易关键指标的应用，特别是在将分布式账本与物联网应用[13]结合使用时。由于节点需要传输信息并被验证，因此串联模型是对通信与计算时间 [14]的有效抽象。

本文的贡献可以总结为以下几点： 推导了串联的 M/M/1和 M/D/1队列的PAoI完整 PDF，这对于物联网边缘计算场景具有重要意义； 对两个M/M/1队列的串联执行相同的推导，这在具有两条独立链路的基于中继的通信中具有相关性； 基于解析公式对两个系统进行设计考虑，以作为系统优化的基础。

本文的结构如下。第三节详细介绍了系统模型以及计算信息年龄的流程。第五节针对 M/M/1 – M/M/1串联结构，基于模型进行了计算，而第四节则对 M/M/1 – M/D/1串联结构进行了同样的计算。数值结果在第六节中给出，第七节对全文进行了总结。1

II. 相关工作

在[3]和[15]中可以找到物联网中边缘计算的概述。在5G系统背景下，边缘范式中延迟问题的初步研究方法是理解其支持超可靠低延迟通信（URLLC）的潜力[16]– [18]。信息年龄在边缘计算应用中的重要性首次在[5],中被识别，尽管仅计算了平均信息年龄。同一作者在[19]中提出了一种联合传输与计算调度以满足截止时间。另一个研究领域是利用机器学习，特别是深度学习技术，充分发挥物联网边缘计算的潜力，并支持更广泛的应用场景[20],[21]。

信息年龄（AoI）是网络中一个相对较新的度量指标，但由于其与多种应用的相关性而获得了广泛认可。大多数理论结果针对的是采用先来先服务（FCFS）策略的单节点简单排队系统。然而，一些近期的研究开始关注串联队列中的年龄问题，甚至考虑了后到先服务（LCFS）等不同策略[22]。某些物联网场景也被建模为具有多个源的串联 M/M/1, M/D/1或 D/M/1队列，因为传感器读数首先被预处理，然后传输到服务器[23]。在这种情况下，每个队列遵循FCFS规则，但作者仅推导了平均峰值年龄（PAoI）。另一种可能是队列替换，即队列中仅保留每个源的最新更新，从而显著减小队列大小：在此情况下，被替换的数据包不会进入队列，而是被完全丢弃，相较于简单的LCFS（无论是否具有抢占机制），这减少了信道使用。此时，队列被建模为一个 M/M/1/2，当新数据包到达时，它将取代排队中的数据包的位置。关于此类系统的初步结果在[24],中给出，而单个源和多个源的平均信息年龄和平均峰值年龄（PAoI）分别在[25]和[26]中计算。在[27],中分析了抢占对此类模型平均信息年龄的影响，而[28]推导了具有抢占机制和不同到达过程的两个串联队列的平均信息年龄。另一项工作[29]推导了服务时间服从相位型分布的抢占式队列中峰值信息年龄（ PAoI）的完整分布，该分布可用于表示多个跳段的情况。多跳网络中具有数据包抢占机制的信息年龄（AoI）概率密度函数（PDF）已在[30]中推导得出。另一项研究 [31]探讨了单个源通过多个跳段向多个接收器进行更新的多播网络，推导了该情境下的平均年龄。另一项近期工作考虑了一种场景，即未在截止时间内被接收的数据包将被丢弃，并推导了该情况下的平均峰值年龄（PAoI）[32]。

这些工作中的一些涉及多跳排队网络，而我们的串联模型正是其中的一个特例，但它们都假设存在某种形式的抢占机制。在具有抢占机制的系统中，信息年龄（AoI）和峰值年龄（PAoI）的计算要简单得多，尤其是在 M/M/1队列系统中，但这并不能涵盖所有相关用例：根据控制或监控应用的具体需求，抢占可能不可行或不理想。例如，远程医疗应用可能仍受益于接收到过时样本。据我们所知，本研究是首个针对非抢占式串联网络推导出年龄完整概率密度函数（PDF）的工作，适用于上述应用场景。另一个例子是卫星中继场景，其中进入串联系统的流量来自设备聚合，因此每一次单独的更新都具有重要意义。

其他研究工作则集中于更实际的模型，考虑物理层和介质访问问题对信息年龄的影响。在[33],中，采用了一种考虑衰落无线信道及重传的模型，用于计算单跳链路上的PAoI分布，以及一种近期的实际信息年龄度量一项针对公共网络的研究普遍证实了理论模型的现实性 [34]。其他研究计算了载波侦听多路访问（CSMA）[35],、 ALOHA[36]和时隙ALOHA[37]网络中的平均信息年龄，考虑了不同介质访问策略对信息年龄的影响。如果采样和更新过程均可控，则可以联合优化这两个过程，即同时优化传感器的读取时刻和更新传输[38]：这两个操作的成本是决定系统整体信息年龄的关键因素[39]。

我们的模型的一个推广形式对于诸如卫星中继等应用具有相关性，即包含任意数量的 M/M/1系统、发送器和接收器的多跳网络：在这种情况下，抢占式服务器的信息年龄矩生成函数已在[40]中推导出。其他调度策略会使问题更加复杂：针对先来先服务准则以及其他面向信息年龄的队列优先级机制，平均信息年龄的紧界已在[41]中推导得出。

推导信息年龄的完整分布对于面向可靠性的应用可能至关重要，但在现有文献中仍largely未被探索：尽管关于推导信息年龄分布一阶矩的研究较为广泛，但解析推导完整概率密度函数（PDF）的复杂性仍然是一个巨大的障碍。最近的一项工作[42]利用切诺夫界来推导在确定性到达条件下两个串联队列的信息年龄分位数函数的上界，但据我们所知，完整的PAoI分布仅在简单的排队系统中被推导出来[33]。另一种实现可靠性的有趣方法是直接考虑信息年龄过程：在[43],中，作者使用极值理论推导了在具有调度传输的实际信道环境下峰值信息年龄的互补累积分布函数（CDF）。[44]提出将破产风险（一种经济学概念）作为增强现实中新鲜可靠信息的度量指标，具体而言，利用PAoI的CDF来求解单节点系统中最大破产严重性峰值信息年龄的概率。另一种可靠性方法并未推导信息年龄的完整分布，而是采用对其尾部分布的平均度量，如[45]所示：作者将风险最小化问题建模为马尔可夫决策过程（MDP），优化有界风险下的信息年龄。有关信息年龄文献的更全面概述，我们推荐读者参考[46]。

III. 系统模型

我们考虑一个由两个连续队列组成的串联系统，其中第一个系统为 M/M/1。数据包由速率为 λ的泊松过程在第一个系统中生成，并进入第一个队列，该队列的服务时间为速率为 μ 1的指数分布。当一个数据包离开第一个系统后，它将进入第二个系统，其服务时间为常数 D或速率为 μ 2 的指数随机变量。图1展示了该串联系统的简单示意图。两个队列均为无限容量，且对数据包内容不敏感：不存在更新的抢占机制，即当同一源的新更新到达时，旧的数据包不会从队列中被移除。如引言中所述，我们假设两个系统的服务时间是相互独立的。这一假设对于边缘计算系统而言是合理的，因为通信和处理通常是独立的，但在中继网络中并不总是成立；因此需要仔细验证。然而，即使服务时间是独立的，等待时间却并非如此，因为第二个系统的队列依赖于第一个系统的输出。在下文中，我们使用紧凑符号pX|Y(x|y)表示条件概率 p[X= x|Y= y]。概率密度函数用小写 p表示，累积分布函数用大写 P表示。

在串联队列中，分组生成时间对应于第一队列的到达时间，而接收时刻则是第二队列的离开时间。我们定义第 i个数据包的总系统时间为Ti：当一个数据包被接收时，信息年龄等于Ti，即它被目的地接收的时间 ri与生成时间 gi之间的差值。峰值信息年龄（见图2）是信息年龄的最大值，也就是在新更新到达之前的瞬间的信息年龄。如果我们用Yi= gi − gi−1表示到达间隔时间，则峰值信息年龄为
$$
Δi= ri − gi−1= ri − gi+ gi − gi−1= Ti+ Yi. (1)
$$
如果数据包 i在数据包 i −1之后立即到达，则它很可能需要在队列中等待，直到后者离开系统：系统时间 Ti取决于到达间隔时间 Yi。随后，可通过条件系统时间概率pTi |Yi(ti|yi)计算峰值信息年龄 τi的PDF，记为 pΔi( τi)：
$$
pΔi( τi)= ∫
τ i
0
pYi( yi)pTi |Yi( τi − yi|yi)dyi. (2)
$$
然后我们需要计算pTi |Yi(ti|yi)。对于串联中的每个系统 j= 1,2，系统时间T i, j定义为等待时间 Wi, j和服务时间 Si, j之和。我们还定义了系统 j的到达间隔时间Y i, j。对于 j= 1，有Y i,1 = Y i；而对于 j= 2：
$$
Y i,2 = gi + T i,1 −(gi − 1 + T i − 1,1) = Y i +T i,1 −Ti − 1,1 .(3)
$$
由于第一个队列是 M/M/1，根据赖希[47]利用伯克定理[48]的证明，并在稳态下考虑每个系统中的数据包 i−1，两个队列的系统时间相互独立。如果我们考虑系统 j处于稳态，即不以 Y i − 1, j 为条件，则系统时间T i − 1, j服从参数为 αj= μj − λ的指数分布。然而，Yi和 Ti的值是相关的，因此在计算峰值信息年龄时必须考虑这一事实。接下来，我们给出峰值信息年龄各组成部分的条件概率密度函数，随后将其结合到推导中。首先，我们定义扩展等待时间Ωi,j为前一个数据包的系统时间与系统中到达间隔时间之差，即Ωi,j= Ti−1,j − Yi,j。我们将Ωi,j称为扩展等待时间的原因是Wi,j=[Ωi,j]+，其中[x]+在 x为正时等于 x，在 x为负时等于0。根据Ωi,j的定义，我们有：
$$
Yi,2= Yi+(Wi,1+ Si,1)− Ti−1,1 = Si,1+ Wi,1 −Ωi,1
= Si,1+[−Ωi,1]+. (4)
$$
因为Wi,1 − Ωi,1=[Ωi,1]+ − Ωi,1=[−Ωi,1]+。在接下来的段落中，我们推导所分析的两种系统类型的扩展等待时间的概率密度函数。图3展示了一个数据包在串联队列中可能的传输路径，突出了扩展等待时间的含义：在第一个系统中，当第i个数据包被排队时，它对应于等待时间；而在第二个系统中，由于数据包无需排队并立即进入服务，其负值对应于第i个数据包从第二个系统离开到第i+1个数据包到达该系统之间的时间。当 W= 0时，会出现负的扩展等待时间，因为第i+1个数据包在第i个数据包离开系统之后才到达。一般情况下，我们有Ωi,2= Ti−1,2 − Yi,2，且第i个数据包的系统时间为T i−1,2 = Wi−1,2 + D，而我们知道到达间隔时间为Y i,2= Si,1+[−Ωi,1] +。

定理1 ：到达率为 λ、服务时间为 D的 M/D/1队列的等待时间的累积分布函数为:
$$
P W(w)=(1 − λD)
Dw ∑
k=0
(−λ(w − kD)) k e λ ( w − kD )
k!
.(5)
$$
证明 : 参见厄朗的推导[49]。

推论1 ：我们可以通过对(5)中的累积分布函数求导来得到排队时间概率密度函数：
$$
pW(w)=(1 − λD)(λeλw+
Dw ∑
k=1
(−λ)k(w − kD)k−1
k!
×eλ(w−kD)(k+ λ(w − kD))) ∀w> 0;
pW(0)= 1 − λD. (6)
$$
等待时间的累积分布函数存在不连续性，因为等待时间恰好为0的概率是 1 − λD，这对应于数据包发现系统为空并立即进入服务的概率。

推论2 ：由于 M/D/1系统中的服务时间是恒定的，我们得到系统内总时间的累积分布函数:
$$
PT(t)= PW(t − D)u(t − D). (7)
$$
推论3 ：在给定Si,1和Ωi,1的条件下，Ωi的 ,2为:
$$
pΩi,2|Si,1,Ωi,1(ωi,2|si,1, ωi,1) = p(Wi−1,2= ωi,2 − si,1 −[−ωi,1]+ − D)
= pW(ωi,2+ si,1+[−ωi,1]+ − D). (8)
$$
图4清楚地展示了这一点：当Ωi,1为负时，扩展排队时间Ωi,2对应于Si,1+Wi−1,2+D −Ωi,1；而当Ωi,1为正时，数据包 i在数据包 i−1离开第一个系统后立即开始服务，此时有Ωi,2= Si,1+ Wi−1,2+ D。等待时间在 M/D/1系统中是解析推导得出的，尽管在等待时间非常大且处于高负载[50]的情况下可能会产生数值问题。如果应用需要计算非常大的等待时间且涉及 λD 1，我们建议采用相关文献中数值更稳定的方法。

定理2 ：在M/M/1- M/M/1串联队列中，扩展等待时间的概率密度函数由:给出
$$
pΩi, j |Yi, j (ωi,j|yi,j) = α j e −α j(ωi, j +yi, j)u(ωi,j + yi,j) ,(9)
$$
其中 u(·)是阶跃函数。

证明 ： 根据关于 M/M/1队列的已知结果，系统的系统时间的概率密度函数为T i−1, j，第一个中继处的到达间隔时间 ,1服从速率为 λ的指数分布，而在后续系统中由Y i, 2= S i 1 +[−Ωi,1] + ,给出。

推论4 ：我们可以将(9)与Y i,2的定义结合起来得到：
$$
pΩi, 2 |Si, 1 ,Ω i, 1(ωi,2|si,1 , ω i,1)= α 1 e − α 1( ω i, 2 +s i, 1[− ω i, 1]
+ )
×u(ωi,2 + s i,1 +[−ωi,1] + ).
(10)
$$
为了计算双系统情况下峰值信息年龄（PAoI）的精确概率密度函数（PDF）(j ∈ 1,2)，我们区分每个节点处的空闲与繁忙系统，即根据数据包 i到达时各系统状态对PDF进行条件划分，并针对四种可能组合分别进行计算。情况 A定义为Ωi,1 > 0 ∧ Ω i,2 > 0，而在情况 B中，我们有Ωi,1 >

面向无线链路边缘计算的信息峰值年龄分布

IV. M/M/1 – M/D/1串联系统的 PAoI分布

首先，我们分析一个 M/M/1和一个 M/D/1系统的串联， 使用来自(6)的等待时间的概率密度函数。

定义2 ：辅助函数 θ(M, β)，我们将在后续推导中使用该函数以使符号表示更加简洁，其定义为：
$$
θ(M, β)
= ∫ M 0
pW(w)eβwdw ∀β= 0, β= −λ
=(1 − λD)[
M D ∑
k=1
M
∫
kD
(−λ)k(w − kD))k−1
k!
×eλ(w−kD)+βw(k+ λ(w − kD))dw+
M ∫0 λe(λ+β)wdw]
= λ(1 − λD) λ+ β( M D ∑ k=1[βλk−1eβkD (λ+ β)k − λkeλ(M−kD)+βM
×((kD − M)k k!
+
k−1
∑
j=0
β(kD − M)j λ(λ+ β)k−jj!)]
+e(λ+β)M −1). (12)
$$
如果 β= 0，则该积分的结果就是等待时间的累积分布函数，即 θ(M,0)= P W(M)。如果 β= −λ，我们有:
$$
θ(M,−λ)= ∫
M
0
pW(w)e βw dw
=(1 − λD)(
M D ∑
k=1
M
∫
kD
(−λ) k (w − kD)) k− 1 e − λkD
k!
×(k+ λ(w − kD))dw+ λM)
=(1 − λD)(λM+ e βkD (−λ) k
×((M − kD) k
k!
+ λ(M − kD) k+1 (k+ 1)!)). (13)
$$

如果考虑一个简单的 M/D/1队列（即非串联），则很容易推导出PAoI的分布，因为我们有
$$
Δi= D+ max(Yi, Ti−1). (14)
$$
因此，当 Yi和 Ti−1都小于 τ − D时，峰值信息年龄低于 τ， 我们可以将累积分布函数写为：
$$
PΔ(τ)= ∫ τ−D 0
PW(τ −2D)λe−λydy =(1 − eλ(T−τ))PW(τ −2D)u(τ −2D).(15)
$$
在串联系统中情况更为复杂，其中一个M/M/1队列向 M/D/1队列提供输入。得益于伯克定理[48],，我们可以认为对于数据包 i−1，两个系统均处于稳态，区分出与第三节和图4中所述相同的四种情况 A‐D。

A. 数据包在两个系统中均被排队

我们首先考虑在情况 A下PAoI的条件累积分布函数，其中第 i个数据包在两个系统中都被排队（即Ωi,1> 0∧Ωi,2> 0）。一个数据包处于情况 A的概率由两个同时发生的事件决定： 第一，数据包 i到达时必须发现第一个系统繁忙，这等价于 Ti−1,1> Yi；第二，当该数据包到达第二个系统时，第二个系统也必须处于繁忙状态，因此有Ti−1,1+Wi−1,2+Si−1,2> Yi+ Si,1：
$$
p(A) = p(Ω1> 0)p(Ω2> 0|Ω1> 0) = p(Yi< Ti−1,1, Si,1< Ti−1,1 − Yi+ Wi−1,2+ D)
=
∞
∫
0
t 1
∫
0 py1(y1)pT1(t1)dy1dt1 ∞
∫
0
PS1(w+ D)pW(w)dw
= ρ1(1 −(1 − λD)e −μ1 D − e −μ1 D lim
M→∞ θ(M,−μ1))
= ρ 1(1 −(1 − λD)e − μ 1 D(1+ λ(e μ 1 D −1)
α 1 eμ1 D+ λ))) .(16)
$$
A情况下峰值信息年龄的条件分布为：
$$
pΔi |Ti − 1 , 1 ,A(τ|t1)= pW(τ − t 1 −2D) p(A)
×PSi (τ − D − t 1)PY i (t1)
=(1 − e − λt 1 )(1 − e − μ 1( τ − t 1 − D )) p(A)
×pW(τ − t 1 −2D)u(τ − t 1 −2D).
(17)
$$
我们需要单独考虑 w= 0的情况，因为累积分布函数在此处存在不连续性。现在，我们可以通过代入 pW(w)并应用全概率定律来解除该分布的条件限制：
$$
pΔ|A(τ)
=
τ−2D ∫0 pΔi|Ti−1,1,A(τ|t1)α1 e−α1t1dt1
+α1(1 − λD)e−α1(τ−2D)(1 − e−λ(τ−2D) − e−μ1D)
=
τ−2D ∫0 α1 p(A)(e α1(w−τ+2D) − eμ1(w−τ+2D)
−e−μ1 D−α1(τ−2D)−λw+ e−μ1(τ−D))pW(w)dw
+α1(1 − λD) p(A) (1 − e−λt)(1 − e−μ1(τ−t−D))e−α1(τ−2D).
(18)
$$
然后，我们可以将引理2中定义的辅助函数代入(18)，得到在情况{v3}下峰值信息年龄的PDF：
$$
pΔ|A(τ)=
α1 p(A)( e−α1(τ+2D)θ(τ −2D, α1)+ e−μ1D
(− e−μ1(τ−3D)θ(τ −2D, μ1) −e−α1(τ−2D)θ(τ −2D,−λ)
+e−μ1(τ−2D)(PW(τ −2D)−(1 − λD))).
(19)
$$

B. 数据包仅在第一个系统中排队

我们现在考虑情况 B，其中在第一个系统存在排队，但在第二个系统不存在排队。这等价于声明Ti−1,1> Yi,1 ∧Ωi−1,2+ D ≤ Si,1。因此，我们得到情况 B的以下概率：
$$
p(B) = p(Ω1> 0)p(Ω2 ≤ 0|Ω1> 0) = p(Yi< Ti−1,1, Si,1 ≥ Ti−1,1 − Yi+ Wi−1,2+ D)
=
∞
∫
0
t 1
∫
0 py1(y1)pT1(t1)dy1dt1 ∞
∫
0
(1 − PS1(w+ D))pW(w)dw
= ρ1e −μ1 D((1 − λD)+ lim M→∞ θ(M,−μ1))
=(1 − λD)ρ1 e −μ 1 D(1+ λ(e μ 1 D −1)
α 1 eμ1 D+ λ) . (20)
$$
此情况下的峰值信息年龄由Ti − 1,1 + S i,1 + D给出。此情况下其条件概率密度函数为：
$$
pΔ|Ti − 1 , 1 ,B(τ|t1)= pS1(τ − t 1 − D) p(B)
×PY 1(t1)PW(τ − t 1 −2D) =
μ 1 e − μ 1( τ − t 1 − D )
p(B)
×PW(τ − t 1 −2D)(1 − e − λt 1 ).(21)
$$
我们现在可以对这个概率进行无条件化，以得到情况 B下峰值信息年龄的PDF：
$$
pΔ|B(τ)
= ∫ τ−D PW(s1 − D) p(B) α1 e−α1(τ−s1−D)
×μ1 e−μ1 s1(1 − e−λ(τ−s1−D))dx
= α1 μ1
p(B)e −α1(τ−D)−λD
×(∫ τ−2D 0 PW(w)e−λwdw −∫ τ−2D 0 PW(w)dw)
= α1(1 − λD)
ρ1 p(B) e−α1(τ−D)−λD
τ−2D D ∑ k=0[e−λ(τ−2D)
−
k+1
∑
j=0
(−λ)j(τ −(k+ 2)D)je−λkD
j! ]. (22)
$$

C. 数据包仅在第二个系统中排队

然后我们考虑情况 C，即在第一个系统中没有排队，但数据包在第二个系统中被排队。这等价于声明Ti−1,1 ≤ Yi,1 ∧ Ωi−1,2+ D>Si,1 − Ωi,1。因此，我们得到情况 C的以下概率：
$$
p(C)= p(Ω1 ≤ 0, Ω2> 0) = p(Yi ≥ Ti−1,1, Si,1< Ti−1,1 − Yi+ Wi−1,2+ D) =
∞ ∫0 y1 ∫0 py1(y1)pT1(t1)
×
∞
∫
max(0,y1−t1−D)
PS1(w+ t1+ D − y1)
×pW(w)dwdt1 dy1= λD −p(A). (23)
$$
此情况下的峰值信息年龄由Ti−1,1+ Ωi−1,2+2D给出。由于已知处于情况 C，因此有：
$$
pΔ|Yi, 1 ,Ω i − 1 , 2 ,C(τ|y1, w) = PS1(τ − y1 − D)PY 1(y1) p(C) ×pT(τ −2D − w)u(y1+ w+ 2D − τ) =
α1(1 − e −μ1(τ−y1 −D))e α 1(w−τ+2D)u(y1+ w+ 2D − τ) p(C) .
(24)
$$
我们现在可以通过应用全概率定律，将该概率对Y i,1取消条件化：
$$
pΔ|Ωi − 1 , 2 ,C(τ|w) =
τ − D
∫
τ − 2D − w
λe − λ y 1α 1 e α 1( w − τ+2D )
p(C) dy1
×(1 − e − μ 1( τ − y 1 − D ) ) =
e μ 1( D − τ ) (α1 e μ 1( w+D ) − μ 1 e α 1( w+D )+ λ) p(C) . (25)
$$
现在，我们可以再次对Ti−1,i取消条件，得到在情况 D下峰值信息年龄的PDF：
$$
pΔ|C(τ)
=
τ−2D ∫0 pΔ|Ωi−1,2,C(τ|w)pW(w)dw +1 − λD p(C) pΔ|Ωi−1,2,C(τ|0)
= e−μ1(τ−D)
p(C) (α1e μ1Dθ
−μ1e α1Dθ(τ −2D, α1)+ λPW(τ −2D))
+(1 − λD)e−μ1(τ−2D)
p(C) (α1 − μ1e −λD+ λe−μ1D).
(26)
$$

D. 数据包未在任一系统中排队

最后，我们考虑情况 D，即两个系统均无排队。这相当于说明Ti−1,1 ≤Yi,1 ∧ Ωi−1,2+ D ≤ Si,1 − Ωi,1。因此，我们得到情况 D的以下概率：
$$
p(D)= p(Ω1 ≤ 0, Ω2 ≤ 0) = p(Yi ≥ Ti−1,1, Si,1 ≥ Ti−1,1 − Yi+ Wi−1,2+ D) =
∞ ∫0 y1 ∫0 py1(y1)pT1(t1)
∞
∫
max(y1−t1−D,0)
(1 − PS1(w+ t1+ D − y1))
×pW(w)dwdt1 dy1=(1 − λD)−p(B). (27)
$$
此情况下的峰值信息年龄由Yi,1+ Si,1+ D给出。由于已知处于情况 D，可应用贝叶斯定理得到：
$$
pΔ|D,Y i, 1 ,T i − 1 , 1(τ|y1, t1)
= pS1(τ − y1 − D)PY 1(y1) p(D) ×PW(τ − t1 −2D)u(y1 − t1) =
μ1 e −μ1(τ−y1 −D)P W(τ − t1 −2D)u(y1 − t1) p(D) .(28)
$$
我们现在可以通过应用全概率定律，将此概率对Y i,1取消条件化：
$$
pΔ|D,T i − 1 , 1(τ|t1)
= ∫
τ − D
t
μ 1 e − μ 1( τ − y 1 − D )λe − λ y 1
p(D)
×PW(τ − t 1 −2D)u(y1 − t 1) dy1
=
λμ 1
α 1 p(D) P W(τ − t 1 −2D)e − μ 1( τ − D ) (e α 1( τ − D ) − e α 1 t 1 ).
(29)
$$
我们现在可以再次对Ti−1,i取消条件，得到情况 D下峰值信息年龄的PDF：
$$
pΔ|D(τ)= ∫ τ−2D λμ1
p(D)PW(τ − t1 −2D)e−μ1(τ−D)
×(eα1(τ−D−t1) −1)dt1 = λμ1
p(D)e −μ1(τ−D)(eα1 D∫ τ−2D 0
PW(w)eα1 wdw
−∫ τ−2D 0 PW(w)dw)
= μ1λ(1 − λD) p(D) e−μ1(τ−D)
τ−2D D ∑ k=0[λ1 − eα1(k+1)D
+
k
∑ j=0( (τ −(k+ 2)D)j j!((−λ)j−1eλ(τ−(k+2)D)
−
λk(−1)jeμ1(τ−(k+2)D)
μk−j+1 1 ))]. (30)
$$
根据定义1中四种情况的前述结果，可得到整体的峰值信息年龄概率密度函数。

V. PAOI DISTRIBUTION FOR THE M/M/1 – M/M/1 TANDEM

我们现在考虑 M/M/1 – M/M/1串联结构，它表示具有随机计算时间的边缘计算系统或通信中继系统。为了计算（11），我们像在上一节中那样，将计算分为4种情况。

A. 数据包在两个系统中均被排队

我们首先考虑情况 A，其中数据包 i发现两个系统都处于繁忙状态，即在每个系统中，第 i个数据包在第i −1个数据包离开之前到达。在这种情况下，Ωi,1>0 ∧Ωi,2> 0。由于Ωi, j的条件概率密度函数已在(10)中给出，并且我们知道Yi,1与Ti−1,1相互独立，同样Si,1与 T i−1,2也相互独立，因此该情况的概率 p(A)为：
$$
p(A) = p(Ω1> 0)p(Ω2> 0|Ω1> 0) =
∞
∫
0
pT1(t1)
t 1
∫
0
py1(y1) dy1 dt 1
∞
∫
0
pT2(t2)
t 2
∫
0
pS1(s1) ds 1 dt 2
=
λ μ 1 + α 2
. (31)
$$
我们从系统时间在Ω1、 Ω 2和 S 1上的条件分布开始，因此 S 2 是唯一剩下的随机变量。以下，在可能的情况下省略数据包的索引 i以简化符号：
$$
pT|Ω1 ,Ω 2 , S 1 ,A(t|ω1 , ω 2 , s 1) = μ 2 e − μ 2( t − ω 1 − s 1 − ω 2)
×u(t − ω 1 − ω 2 − s 1) . (32)
$$
我们现在使用全概率定律，先对 Ω2取消条件，然后对 S1取消条件：
$$
pT|Ω1,A(t|ω1) =
t−ω1 ∫0 pS1(s1)
t−s1−ω1 ∫0
pΩ2|Ω1,S1(ω2|ω1, s1) 1 − PΩ2|Ω1,S1(0|ω1, s1)
×pT|Ω1,Ω2,S1,Adω2ds1
=α2μ2(α2+ μ1)eα2(tω1)(α1+ λeμ1(tω1)−μ1eλ(tω1))
λα1μ1
.
(33)
$$
我们知道处于情况 A意味着我们有Ω1> 0：第一积分中的分母是该事件发生的概率，我们需要将其考虑在内以得到正确的条件概率。然后我们对Y1取条件，并对 Ω1取消条件化：
$$
pT|Y1,A(t|y1) =
t ∫0 pT|Ω1,A(t|ω1) pΩ1|Y1(ω1|y1) 1 − PΩ1|Y1(0|y1) dω1
= μ2α2 e−α1 y1 λp(A)(α1(e−α1t − e−α2t) (μ2 − μ1) +λe−α1t(1 − e−μ2t)
μ2
−
μ1(e−α1t − e−μ2t) μ2 − α1).(34)
$$
我们现在可以推导出系统时间 T的概率密度函数：
$$
pT|A(t)
= ∫
∞
0 pY1(y1)pT|Y1,A(t|y1)dy1
=
μ2α2 μ1 p(A)( α1(e−α1t − e−α2t) (μ2 − μ1)
+ λe−α1t(1 − e−μ2t)
μ2
− μ1(e −α1t − e−μ2t) μ2 − α1).(35)
$$
最后，我们得到由 T+ Y 1给出的峰值信息年龄的概率密度函数：
$$
pΔ|A(τ)= ∫
τ
0 pT|Y1 ,A(t|τ − t)pY1(τ − t)dt
=
μ1+ α2 λ(α2μ1μ2(e −μ1 τ − e −μ2 τ )
(μ2 − μ1)(μ2 − α1)
−λe − μ 1 τ (1 − e − α 2 τ
)
+
α 1 α 2 μ 2(e − μ 1 τ − e − α 2 τ )
(μ2 − μ 1)( μ 1 − α 2) +
α 1 μ 1 μ 2(e − α 1 τ − e − μ τ )
(μ2 − μ 1)(μ2 − α (36)
$$

B. 数据包仅在第一个系统中排队

我们现在考虑情况 B，即当数据包 i 到达时，第一个系统繁忙而第二个系统空闲，也就是说第i个数据包未在第二个系统中排队。我们有Ωi,1>0 ∧ Ωi,2 ≤ 0，且该情况发生的概率为 p(B)：
$$
p(B) = p(Ω1> 0)p(Ω2 ≤ 0|Ω1> 0) =
∞ ∫0 t1 ∫0 py1(y1)pT1(t1)dy1dt1 ∞ ∫0 ∞ t∫2 pS1(s1)pT2(t2)ds1dt2
=
λα2
μ1(μ1+ α2)
. (37)
$$
在这种情况下，系统时间概率密度函数与Ω2无关，因此我们只需给出条件概率密度函数：
$$
pT|Ω1,S1,B(t|ω1, s1)= μ2e −μ2(t−ω1−s1)(1 − e−α2s1)
×u(t − ω1 − s1). (38)
$$
对于情况 A，我们对 Y1进行条件化，并对 S1和Ω1取消条件化：
$$
pT|Y1,B(t|y1)
= μ1(μ1+ α2)e −α1(y1+t)
α2 (1 − e−μ2t
−
α2μ2(1 − e(α1−μ2)t) (μ2 − μ1)(μ2 − α1) + α1μ2(1 − e−λt) λ(μ2 − μ1)).(39)
$$
由该结果，我们推导出情况 B下系统时间 T 的条件概率密度函数：
$$
pT|B(t)
= λe−α1t p(B)(1 − e−μ2t
+α1μ2(1 − e−λt) λ(μ2 − μ1)
− α2μ2(1 − e−(μ2−α1)t) (μ2 − μ1)(μ2 − α1)).
(40)
$$
我们现在可以找到情况 B下PAoI的无条件PDF：
$$
pΔ|B(τ)=
μ 1
p(B) (e − α 1 τ − e − μ 1 τ )− λμ 1 e − μ 1 τ (1 − e − α 2 τ )
α 2p(B) +
α 1 μ 1 μ 2(e − α 1 τ −(1+ λτ)e − μ 1 τ )
λ(μ2 − μ 1)p(B) +
μ 1 μ 2 α 2((e − μ 1 τ − e − α 1 τ )(μ2 − μ 1) + λ(e − μ 1 τ − e − μ 2 τ ))
(μ2 − μ 1) 2 (μ2 − α 1)p(B) . (41)
$$

C. 数据包仅在第二个系统中排队

然后我们可以考虑情况 C，其中第 i个数据包在第一个系统中没有经历任何排队，即Ω1 ≤ 0，但在第二个系统中存在排队，即 Ω2 > 0。数据包经历情况 C 的概率由以下公式给出：
$$
p(C)= p(Ω1 ≤ 0, Ω2> 0) =
∞
∫
0
y1
∫
0
∞
∫
0
py1(y1)pT1(t1)pS1(s1)
∞
∫ s 1 − t 1 + y 1
pT2(t2)dt 2 ds 1 dt 1 dy1
=
λ μ 2(μ1 + α 2)
. (42)
$$
系统时间的条件概率密度函数为：
$$
pT|Ω1 ,Ω 2 , S 1 ,C( t|ω1 , ω 2 , s 1) = μ 2 e − μ 2( t − s 1 − ω 2)u(t − s 1 − ω 2) .
(43)
$$
与情况 A相同，我们对 Y1进行条件化，并对 Ω2、 S1和Ω1取消条件化：
$$
pT|Y1,C(t|y1)= μ2α2e−α2t(e−α1y1 − e−α2y1) λ(μ2 − μ1)p(C)
×(α1 − μ1e−λt+ λe−μ1t). (44)
$$
我们现在可以找到系统延迟的概率密度函数：
$$
pT|C(t)= α2e−α2t(α1 − μ1e−λt+ λe−μ1t)
μ1 p(C) . (45)
$$
峰值信息年龄的条件概率密度函数为：
$$
pΔ|C(τ) =
μ2 α1α2(e−μ1τ − e−α2τ)
α2 − μ1
+λe−μ1τ − μ1α2(e−μ1τ − e−μ2τ)
μ2 − μ1
−
α1α2(e−α2τ − e−μ2τ)
λ
−λe−(μ1+α2)τ+ α2μ1τ e −μ2τ− λα2e −μ2τ(1 − e−α1τ)
α1 ).
(46)
$$

D. 数据包未在任一系统中排队

最后，我们考察情况 D，在这种情况下数据包不经历排队，即Ωi,1 ≤ 0 ∧Ωi,2 ≤ 0。该情况发生的概率为 p(D)：
$$
p(D)= p(Ω1 ≤ 0, Ω2 ≤ 0)
= α1μ2(μ1+ α2))− λμ1
μ1μ2(μ1+ α2)
. (47)
$$
由于系统时间概率与Ω2无关，因此可以直接给出条件系统时间概率密度函数为：
$$
pT|Ω1,S1,D(t|ω1, s1)= μ1μ2e −μ2(t−s1)(1 − e−α2(s1 −ω1))
α1
×u(t − s1). (48)
$$
然后我们对Y1进行条件化，并对 S1和 Ω1取消条件化：
$$
pT|Y1 ,D(t|y1) =
μ1μ2 (μ2 − μ1)(p(D) e −μ1 t (1 − e −α1y1)
−e −μ 2 t (1 − e −α 2y1)+ e −(μ2 +α 1)t(e −α 1y1 − e −α 2y1)).
(49)
$$
系统时间的概率密度函数为：
$$
pT|D(t)= μ2(μ1 − λ)e−μ1t − μ1(μ2 − λ)e−μ2t
λ(μ2 − μ1)p(D)
+λe−(μ2+α1)t
p(D) . (50)
$$
我们现在可以求出情况 D下峰值信息年龄的PDF：
$$
pΔ|D(τ)
= μ1μ2λ p(D)(τ(e−μ2τ − e−μ1τ) μ2 − μ1
+α1e −μ2τ − α2e −μ1τ
α1α2(μ2 − μ1)
+(e−λτ+ e−(μ1+α2)τ) α1α2).
(51)
$$
至于 M/M/1 – M/D/1系统，总概率密度函数由定理 1给出。

E. 服务速率相等情况下的峰值信息年龄

在本小节中，我们考虑一种特殊情况，即峰值信息年龄概率密度函数的通用公式不确定， μ1= μ2=μ。我们遵循与常规推导相同的步骤。本文未推导通用公式不确定的其他情况，μ1= α2和 μ2= α1。

在情况 A中，即对于Ω1> 0 ∧ Ω2> 0，我们有:
$$
p(A)= λ μ+ α .
(52)
$$
按照一般情况下的相同步骤，我们得到：
$$
pΔ|A(τ)=
e−μτ p(A)( μ(eλτ −1)+ λ(e −ατ − eλτ) +μα(α+ μ)(1−eλτ)+ μαλτ(αeλτ+ μ)
λ2 ).
(53)
$$
情况 B（即 Ω1> 0 ∧ Ω2 ≤ 0）的概率为：
$$
p(B)= λα
μ(μ+ α)
. (54)
$$
峰值信息年龄的条件概率密度函数为：
$$
pΔ|B(τ)=
μe −μτ p(B)(α 2 (e λτ −1)
λ2
− λ(1 − e −ατ )
α
− μ(αλτ 2+(α − λ)τ)
2λ ). (55)
$$
在这种情况下，由于系统完全对称且两个队列均为 M/M/1， 因此该系统也是时间可逆的，使得情况 B等同于情况 C 的逆过程。处于情况 C的概率，即Ω1 ≤ 0 ∧Ω2> 0，以及峰值信息年龄的条件概率密度函数与情况 B中相同：
$$
p(C)= p(B)pΔ|C(τ)= pΔ|B(τ). (56)
$$
最后，我们考察情况 D，其中两个系统都是自由的：
$$
p(D)= α(μ+ α)− λ
μ(μ+ α)
. (57)
$$
然后我们得到峰值信息年龄的条件概率密度函数：
$$
pΔ|D(τ)= μ2λe−μτ(2cosh(ατ) − α2τ2 −2) α2 p(D) . (58)
$$
与一般情况一样，总体峰值信息年龄由定理1给出。

VI. 仿真结果

我们将分析结果与蒙特卡洛仿真进行了比较，传输了 N= 107个数据包，并计算每个数据包的系统延迟和峰值信息年龄。在每次仿真的初始阶段，我们丢弃了 N0= 1000个数据包，以确保系统已达到稳态。我们还根据数据包在每个系统中经历的排队情况将其分为四种情况。由于PAoI分布的推导未引入任何近似，仿真结果应与理论曲线完全吻合。该蒙特卡洛仿真由单次实验组成，所有数据包依次传输。仿真参数列于表II中，并用于所有图表，除非另有说明。

A. M/M/1– M/D/1 串联

我们首先考虑第一个队列为M/M/1、第二个队列为 M/D/1的串联结构。需要注意的是，在接下来的所有图中，仿真结果与理论推导的曲线相吻合，表明了我们计算的正确性。

尽管未显示，系统时间表现出预期的行为：当数据包在两个队列中都被排队时，总系统时间Ti最高；而当两个系统都空闲时，总系统时间Ti最低。然而，峰值信息年龄PAoI呈现出不同的趋势。虽然系统时间随流量负载单调增加，但峰值信息年龄PAoI是系统时间和到达间隔时间的组合：在一端，当系统流量非常低时，PAoI主要由到达间隔时间决定；而在另一端，则主要由系统时间决定。因此，最小化PAoI的最佳设置位于中间某个位置，是在两者之间取得平衡的结果。

年龄的两个成因。此外，确定性服务能够减少不确定性，尤其是在流量较高且排队是导致老化的主要原因时。

图5显示了四种情况下的峰值信息年龄的累积分布函数。值得注意的是，峰值信息年龄从不小于 2D，因为即使在第一个系统中数据包被瞬时处理，仍然会产生最小延迟：一旦第i个数据包生成，由于 M/D/1队列的存在，它至少需要时间 D才能通过系统；即使下一个数据包 i紧随其后生成，也需要额外的 D时间被边缘节点服务，从而导致最小信息年龄为 2D。在情况 C下，峰值信息年龄要小得多，即数据包仅在 M/D/1系统处排队，因为该队列通常较短，并且保证在有限时间内清空。情况 A和 B表现出差得多的性能，原因在于第一个系统的服务速率较低（D= 0.8对应速率为1.25）以及其指数系统时间分布。如果数据包在两个系统中均不排队（情况 D），则峰值信息年龄主要由两个数据包之间的到达间隔时间决定，导致更高的信息年龄。

我们还可以将峰值信息年龄（PAoI）视为生成和服务速率的函数：图6展示了不同 λ值下的PAoI累积分布函数。我们可以观察到，当 λ 接近0.5时，PAoI最低，因为高流量负载会增加排队时间，而较低的负载则由于更长的到达间隔时间而导致PAoI增加。

0.5时，PAoI最低，因为高流量负载会增加排队时间，而较低的负载则由于更长的到达间隔时间导致PAoI增加。

图7展示了当两个系统的服务速率互换时的情况。在图中，我们比较了两对曲线（橙色和青色，紫色和黑色）：橙色和紫色虚线对应第二个节点更快的系统，青色实线和黑色点线则以 M/D/1队列为瓶颈。由于 M/D/1队列中的系统时间很少非常大（需要非常大的队列才显著，因为所有数据包具有相同的服务时间），而M/M/1队列具有指数系统时间分布，更常出现较大的值，因此将瓶颈置于 M/D/1系统上会导致在最坏情况下（即较大的百分位数）峰值信息年龄更低，但代价是在有利情况下的峰值信息年龄更差。橙色线与黑色线之间的差异大于青色线与紫色线之间的差异，因为两条链路速率差异越大，瓶颈的影响就越显著。至于子情况分析，蒙特卡洛仿真得到的系统时间和峰值信息年龄与解析曲线完全吻合。如图9

![图9](图9. 对于不同 D值，使用最优 λ的 M/M/1