【论文阅读】Real-Time Status: How Often Should One Update?

1,844 阅读11分钟

Real-Time Status: How Often Should One Update?

Age-of-Information for Computation-Intensive Messages in Mobile Edge Computing

移动边缘计算中计算密集型消息的信息实时性

摘要

状态更新场景中,信息年龄(AoI)是测量信息实时性的一个新颖的指标。实时应用需要及时将状态更新信息传输给目的节点,但是一些应用的状态信息是嵌入在包中的,在数据处理之前都不会展示出来,这是计算代价很大并且很浪费时间。

考虑两种方案:

  • 用户自己的本地计算
  • 将计算任务卸载到边缘服务器

两种计算方式统一到一个两个节点的串联队列模型。采用零等待规则,即一旦前一个消息离开第一个节点,则第一个节点立即禅城一条新消息。第二个节点可以看做是一个FCFS的M/M/1排队模型

仿真结果表明,当远程计算速率足够大时,远程计算远优于本地计算,并且存在最佳传输速率,因此远程计算在最大范围内优于本地计算。

I. 介绍

为了精准管理,保持数据的新鲜度是十分重要的。数据的新鲜度定义为在进行最后更新之后所经过的时间。

重要的是所需要的更新的数据不仅仅需要传输给控制器,并且在有用的消息暴露之前需要对数据进行预处理。但是由于本地处理器的有限计算能力,这可能是计算代价高昂且是耗时的。边缘移动计算(MEC)的引入解决了这一问题,不仅提供了充足的计算资源,还缩短了响应时间。

AoI在目的节点测量数据的新鲜度。根据现有的研究,AoI取决于数据包产生的频率和数据传输和队列所产生的延迟。

本文研究两种模式:本地计算和远程计算。远程计算的计算过程遵循FCFS规则,两种计算方式统一到一个两个节点的串联队列模型。在远程计算中,假设传输时间和计算时间都是指数分布的,队列长度也是无限的。那么,计算过程可以看做是一个FCFS的M/M/1排队模型。在模型中我们取远程和本地计算的平均AoI。

根据表现,发现该区域的特点是远程计算优于本地计算的AoI。研究数据包大小、CPU周期的需求量、数据率和边缘服务器计算能力对平均AoI的影响。根据结果,远程计算所需CPU周期量减少,边缘服务器计算能力增加,则AoI减少。仅考虑远程计算中数据包大小和数据率的影响,存在一个最优的数据包大小和最优的数据率,使得平均AoI最小。

在本地计算中,远程计算所需CPU周期量减少,则AoI减少。但数据包大小和数据率对AoI并无影响。在所需CPU周期更多,或边缘服务器的计算能力更优,以及适当的数据包大小和数据速率的时候,远程计算优于本地计算。

II. 模型和公式

状态监测和控制系统如图1所示。

A. 本地计算和远程计算模型

本地计算(图1a):在本地进行计算密集型数据的计算,将结果发送到目的节点。

远程计算(图1b):将计算密集数据包传送给边缘服务器进行远程计算。

将零等待规则应用于本地计算的计算过程和远程计算的传输过程中。

对于本地计算而言,只有最后一个包完全被自身计算,才会产生一个新的状态包。队列延迟完全根据零等待原则估计。由于处理过的数据远小于原始数据,因此相比起计算时间,传输时间可以忽略。

对远程计算而言,最后一个状态包发送出去,才会产生并传输一个新的状态更新包。发送排队延迟为零,应用FCFS的原则,因此数据包需要排队等待处理。

B. 统一模型

两个模型可以统一为一个梁节点串联模型。如图2.对远程计算,C1是传输通道,C2是边缘服务器,M1是发送队列,M2是等待处理的计算队列。而本地计算可以被看所是一个特例C2的服务率无穷大的,C1是本地计算服务器,M1是计算队列(根据零等待原则,该队列为空)。M2也是空。

AoI被定义为

t是当前时间戳,u(t)是数据产生时间。在FCFS的规则下,目的节点AoI(△(t))的变化如图3所示。

(以下来自参考文献Real-Time Status: How Often Should One Update?的推理)

在t=0时开始观察,队列为空△(0)=△0。第一个状态更新产生在t1,以此类推。

在没有任何更新的情况下,监视器的age会随时间线性增加,并在收到更新时重置为较小的值。 更新i在ti时刻产生,并在t'i时刻完成计算被终点接收。在t'i时刻,终点的age△(t'i)重置为Ti=t'i-ti。

age Ti也是更新分组i的系统时间,并且是分组在队列中等待的时间与其在服务中花费的时间的总和。因此,age函数△(t)表现出图2中所示的锯齿图案。

状态更新的时间平均age是图2中锯齿函数下的区域,其通过观察的时间间隔归一化。在一个区间(0,τ),平均age是

为了简化说明,观察间隔的长度选择为τ= t'n,如图2所示。 我们将由(1)中的积分定义的区域分解为不相交的几何部分的总和。从t=0开始,区域可以看做是多边形区域Q1、梯形Qi(i>1),长度为Tn(tn,t'n)的三角形区域等的拼接。

在N(T)= max{n|tn<=T}表示T时间之前的到达次数。该分解使得

从图2看,Qi的面积为ti-1到ti'为边长的等腰三角形减去ti到ti'为边长的等腰三角形。定义

为了生成更新i-1和i之间经过的时间,于是Qi的计算定义为

当更新的生成可以表示为随机到达的过程时,Xi是更新i到达的时间间隔。 将(4)代入(2)中,重新排列产生时间平均age为

其中\tilde{Q}=\tilde{Q}_1+T_{n}^{2}/2。我们观察到age贡献\tilde{Q}表示边界效应,其是有限的,概率为1。因此(5)的第一项会随着T的增加消失。使

是状态更新数据包生成的稳态速率。我们假设极限存在并且有限。当N(T)→无穷时,(5)剩下的求和项是是一个样本平均值,将收敛到其相应的随机平均值。平均状态的更新age为

其中E[.]为期望操作符,X和T是随机变量分别对应于更新数据包的到达间隔时间和系统时间。

我们注意到,(7)中的平均更新age在服务系统的遍历性的弱假设下成立。 此外,(7)是广泛类别的服务系统的一般结果,其中更新分组FCFS处理。 例如,状态更新流与其他分组流共享服务设施时,(7)将需要排队。 但是,对age△的评估可能具有挑战性。 特别地,X是随机变量,其描述了生成更新分组与其之前分组产生的时间之间的间隔,而T是同一个分组在系统中的运行时间。 变量X和T是相关的。 大的到达间隔时间X允许队列为空,产生较小的等待时间并且通常是小的系统时间T.也就是说,X和T倾向于负相关并且这使得E [TX]的评估复杂化。

接下来,我们将找到最小化FCFS队列标准排队系统的年龄和服务器利用率。 我们从M/M/1系统开始。 (M/M/1排队模型)是一种单一伺服器的排队模型,到达人数是泊松过程(Poisson process 在两个互斥(不重叠)的区间内所发生的事件的数目是互相独立的随机变量。),服务时间是指数分布(exponentially distributed 指数分布(也称为负指数分布)是描述泊松过程中的事件之间的时间的概率分布,即事件以恒定平均速率连续且独立地发生的过程),只有一部伺服器(server) 队列长度无限制,可加入队列的人数为无限)

IV. M/M/1 FCFS

此模型中,出生率(即加入队列的速率)λ在各状态中均相同,死亡率(即完成服务离开队列的速率)μ亦在各状态中相同(除了状态0,因其不可能有人离开队列)

我们认为FCFS M/M/1系统具有到达率λ和服务率μ。 也就是说,生成更新分组并作为速率λ泊松过程提交给系统,因此状态更新到达间隔时间Xi是独立且相同分布的(iid 如果这些随机变量服从同一分布,并且互相独立,那么这些随机变量是独立同分布,泊松分布E(X)=λ D(X)=λ X指数分布 E(X)=1/λ D(X)=1/λ)指数随机变量,其中E [X] = 1 /λ。 此外,服务时间是iid指数,平均服务时间为1/μ。 我们将计算系统的age,然后找到最小化平均age的服务器利用率=λ/μ

对于固定服务率μ,我们可以最小化相对于到达率λ的平均年龄△,或者等效地,提供的负载ρ=λ/μ。 区分(17)关于ρ并设置为0,我们得到最优利用率ρ满足等式ρ^ 4-2ρ^ 3 +ρ^2-2ρ+ 1 = 0,因此ρ = 0.53。 服务器空闲= 47%的时间。 通过选择一个λ来实现最佳年龄,该服务器使服务器偏向忙而不是闲置。 在最佳利用率ρ时,系统中的平均分组数是ρ =(1-ρ*)= 1.13。

请注意,如果我们想要最大化吞吐量,我们希ρ望接近1,吞吐量是每秒传送到监视器的数据包数。 如果我们想要最小化数据包延迟,即最小化数据包的系统时间,我们希望ρ接近0。

V. M/D/1 FCFS

在某些系统中,服务设施表示随机到达状态更新的聚合器,其中更新分组是固定长度并且分组处理时间是确定性的。 例如,这可以描述医疗机构,其中患者的心率更新由中央监测器收集。 在假设患者的这种信息的产生是独立且相同的分布的情况下,医疗中心的总流量可以被建模为速率λ的泊松过程。 因此,该系统可以被抽象为M/D/1系统。

在第i个状态更新包在ti时到达M2,由于零等待,ti也是C1进行第i+1个状态更新数据包处理的开始,C1以u1的服务率进行服务。将t'i作为第i个数据包在C2上的服务终止时间,C2以u2为服务率。目的节点的新鲜度在C2中没有服务完成而线性增加,否则迅速减少到较小的值,即更新目的地的处理状态。假设两个服务时间是独立的并且具有指数分布的相同分布。

经过处理状态数据包的平均新鲜度是图3中的函数△(t),按时间间隔归一化。时间间隔为(0,τ)的平均AoI为

VII. 结论

在本文中,我们考虑使用两种方案的MEC中计算密集型消息的AoI,一种是本地计算,另一种是远程计算。 导出了用于本地计算和远程计算的封闭形式的平均AoI,并给出了远程计算优于本地计算的区域。 数值结果表明,存在最优传输速率,因此远程计算在最大范围内优于本地计算。 远程计算更有可能以更大的远程计算速率胜过本地计算。 我们可以看到,采用MEC对于获得计算密集型数据的最佳AoI至关重要。 在未来的工作中,值得将工作扩展到部分远程计算和多源 - 目的地对。