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为
其中。我们观察到age贡献表示边界效应,其是有限的,概率为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至关重要。 在未来的工作中,值得将工作扩展到部分远程计算和多源 - 目的地对。