分布式虚拟环境中动态延迟的本地滞后方法

2019-09-13 03:37:46刘家学
计算机应用与软件 2019年9期
关键词:延迟时间实时性一致性

刘家学 王 浩 耿 宏

(中国民航大学电子信息与自动化学院 天津 300300)

0 引 言

分布式虚拟环境[1](Distributed Virtual Environment,DVE)提供一个共享的虚拟世界,通过网络将位于不同地理位置的多个用户相连接,用户之间可以共享信息产生交互,为某一共同目标进行协同仿真。

DVE通常采用复制式结构[2],其中每个用户使用的计算机都可以看作一个节点,节点中存有整个虚拟环境的副本,任意节点的用户进行操作后,该操作不仅会对本地副本的状态造成影响,还会通过网络传给其他节点并执行。实际运行中,网络传输的延迟具有随机性,且不可避免,这会导致各节点执行操作的时间和顺序不同,从而使副本状态发生不一致。同时,延迟也会导致操作在异地节点上的实时响应时间变长,影响用户交互的真实感。因此,必须解决DVE中的一致性与实时性问题。

锁同步[3](LockStep)算法将DVE的时钟划分为若干周期并阻塞各节点时钟的推进,只有全部节点都执行了操作且副本达到相同的状态后才允许进入下一时钟周期。虽能保证一致性,但操作的实时性很差,无法适用于频繁交互的系统。在DR(Dead Reckoning)算法[4-5]中,各节点利用相同的DR模型预测DVE的状态,同时接收来自其他节点的实际状态,当本地节点的预测值和实际值的误差超过一定范围时就用实际值更新本地状态。虽然该方法中用户操作的响应时间很短,但使用过程中会出现大量短时间的不一致,需要不断进行回滚。文献[6]采用了延迟一致性控制方法,该方法不延迟本地操作处理过程,而是将异地操作延迟一定的时间,虽能保证操作的实时性,但会因各节点执行操作顺序的混乱而导致不一致。

针对上述问题,本文采用本地滞后的方法,延迟操作在各节点的执行时间,并通过周期性地更新本地滞后时间来实现动态调整响应时间,保证了DVE中用户的实时交互。

1 本地滞后的原理和模型

1.1 本地滞后的原理

本地滞后的原理是用户在本地节点触发一个操作后,该操作不会被立即执行,而是延迟一段时间再执行[7-8],这段延迟的时间被称为本地滞后时间。在延迟的过程中,本地节点会将该操作传递到其他节点,以本地滞后时间抵消传输时间,从而达到所有节点同时执行操作的效果,如图1所示。

图1 本地滞后的原理

1.2 分布虚拟环境的状态模型

在DVE中,各节点独立运行位于本地的虚拟环境副本,通过互相传递操作自行更新本地副本的状态,这种更新的独立性很容易造成各节点的状态不一致,因此引入有限状态机(Finite-state machine,FSM)的模型来保证状态更新的一致性。

有限状态机,又称有限状态自动机,是一种具有离散输入输出的数学模型,可以表示有限个状态之间的相互转移[9-10]。一个系统的有限状态机可以表示为一个五元组M=(S,X,Y,λ,μ),S={s0,s1,…,sn}是状态集合,X={x0,x1,…,xn}是输入集合,Y={y0,y1,…,yn}是输出集合,λ:S×X→S是状态转移函数,μ:S×X→Y是输出转移函数。其中λ和μ也可用时序关系表示为:s(t+1)=λ(s(t),x(t)),y(t)=μ(s(t),x(t))。

在DVE的各个节点的状态S一致的情况下,如图2所示,只要输入的x(t)和节点的状态s(t)是确定的,那么在函数λ和μ的作用下,系统的下一状态s(t+1)和输出y(t)就是确定的。

图2 有限状态机的模型

2 动态延迟的本地滞后方法

2.1 动态延迟的方法描述

为了保证一致性的同时还能应对网络传输中的延迟波动,本文提出了一种动态延迟的本地滞后方法。根据网络状况调节本地滞后时间,该方法由以下几个阶段进行控制。

(1) 初始化阶段。通过NTP协议[11-12]对DVE中的各节点进行时钟同步,保证各节点具有相同的时间戳。根据当前的操作实时性需求设定一个合适的本地滞后时间值,在DVE运行的初期,各节点按此时间延迟本地操作。

(2) 操作发送阶段。对于操作的触发节点,先不执行触发的操作,而是将操作发送给其他节点,发送时,要在操作的数据结构中加入操作的触发时间。发送后,根据本地滞后时间设定操作在本地的执行时间。

(3) 操作接收阶段。对于操作的接收节点,首先记录操作的接收时间,并由收到的操作数据结构中的触发时间计算出两节点间网络传输的延迟时间。然后利用操作的触发时间和此时的本地滞后时间计算出该操作在当前节点的执行时间,通过比较操作的执行时间与接收时间来确定此操作是否已经超时。如未超时,则按照计算出的执行时间执行该操作;如已超时,则立即执行此操作或进行回滚[13-14]。

(4) 本地滞后时间的动态调整阶段。将DVE的运行过程划分为若干调整周期,记录每个周期内节点间的传输延迟,调整周期结束后,用本周期记录的传输延迟来估算下一周期的本地滞后时间。

上述方法中,操作的发送、接收和本地滞后时间的动态调整是最重要的环节,下面详细阐述这三方面内容。下文中,用有向图G=(N,D)代表整个DVE,N={n1,n2,…,nn}表示DVE中所有仿真节点的集合,D={d11,d12,…,d1n,…,dnn}表示节点间的传输延迟时间,D中任意一个dij代表节点ni与nj间的传输延迟。用O代表系统中所有操作的集合,对于给定操作oi∈O,Tt(ni,oi)表示操作oi在ni节点上的触发时间,Te(ni,oi)表示操作oi在ni节点上的执行时间,Tr(ni,oi)表示ni节点接收到操作oi的时间,Tlag表示系统的本地滞后时间。

2.2 操作发送阶段

对于DVE中的节点nj,用户触发操作oi后要先将oi发送给其他节点。发送时,需在oi的数据结构中加入操作触发的时间Tt(nj,oi)。发送后,将操作在本地滞后一段时间后再执行,由本地滞后时间Tlag可计算出操作oi在本地节点的执行时间为Te(nj,oi)=Tt(nj,oi)+Tlag。

2.3 操作接收阶段

根据DVE中当前运行的调整周期确定此时的本地滞后时间Tlag。在此周期内,节点ni在收到节点nj传来的oi后,首先记录该操作的接收时间Tr(ni,oi),然后从oi的数据结构中解析出操作的触发时间Tt(nj,oi)。两节点间网络传输的延迟时间dij=Tr(ni,oi)-Tt(nj,oi),操作oi在节点ni上的执行时间Te(ni,oi)=Tt(nj,oi)+Tlag。当Te(ni,oi)≥Tr(ni,oi)时,说明未超过执行时间,此操作及时到达,可按照Te(ni,oi)照常执行;当Te(ni,oi)

图3 操作接收流程

采用上述方法进行操作的收发时,对于任意一个操作oi,该操作都是在触发时间Tt(nj,oi)的基础上,在本地节点nj上滞后了Tlag后执行的。操作oi在其他节点上也是以Tt(nj,oi)为基准,延迟了Tlag才执行的。因此,DVE中所有的未超时操作的执行时间的都是相同的,保证了一致性。

网络中传输的延迟是存在波动的,如果Tlag一直保持不变,当节点间传输延迟变大时,会出现频繁的操作超时现象;当延迟变小时,如不及时调小Tlag,会影响操作的实时性。因此,需要实现本地滞后时间的动态延迟。

2.4 本地滞后时间的动态延迟

本地滞后时间的动态延迟主要有两个过程:节点间延迟时间dij的存储和本地滞后时间Tlag的更新。为满足DVE中操作实时性要求,采用基于二叉搜索树的数据结构对dij进行快速存储和读取[15]。

每个调整周期开始时,DVE创建一棵二叉搜索树,树的根节点取值为上一周期的Tlag。然后从根节点开始,将计算所得的dij插入到该树中,如果新插入的值比当前节点的值大,则插入到该节点的右子树,否则插入到左子树。为了后续的查找功能,节点要记录其右子树包含的全部节点数量的计数值R,每往右子树插入一个值就在该节点累加一次计数值。如图4所示,该二叉搜索树记录了9个节点间的延迟信息,每个节点左侧的值代表dij,其中是右侧的值代表R。

图4 存储延迟信息的二叉搜索树

在每个调整周期结束时,需要更新本地滞后时间Tlag。为保证DVE中各节点不出现超时情况,需使用二叉搜索树中最大的dij作为下一调整周期中各个节点的Tlag。网络传输中延迟的波动可能会造成延迟时间远大于正常的延迟时间的情况,为去除这些数值的影响,需要对二叉搜索树中的值进行过滤,去除掉其中最大的M个值。由于树中的节点总数Ntotal是一定的,令m=Ntotal-M,在二叉搜索树中第m大的值即为所需要的Tlag。

可以利用在二叉搜索树中保存的计数值R在树中查找第m大的值。二叉搜索树中每个节点的左子树中的值都小于该节点的值,而右子树中的值都大于该节点的值,所以对于节点ni,在以ni为根节点的二叉搜索树中,ni的值是第R+1大的。因此,只需从根节点出发,将m与R+1进行比较:若mR+1,说明要找的值比此节点的值小,则需要到以左子树为根节点的树中找第m-(R+1)大的节点;若m=R+1,说明要找的值就是此节点的值。查找次数小于等于该二叉搜索树的层数。上述过程伪代码如算法1所示。

算法1 查找二叉搜索树中最大值伪代码FindNthMax(bsTree,m)1:ifn<(GetChildCount(bsTree->root)+1)2: thenreturnFindNthMax(bstress->root->rightsubtree,m)//在节点的右子树中查找第m大的值3: elseifm>(GetChildCount(bstress->root)+1)4: thenreturnFindNthMax(bstress->root->leftsubtree,m-(GetChildCount(bstress->root))+1)//在节点左子树中查找第m-(R+1)大的值5: else6: returnGetDelayNumber(bstress->root)//当前节点为所求值

3 实验仿真

为验证动态延迟的本地滞后方法的可行性与性能,本文通过自主研发的分布式虚拟维修系统对该方法进行评估。分布式虚拟维修系统可以提供一个分布式虚拟维修环境,使多个用户组成小组,协同完成A320飞机的维护训练任务。在系统中,用户能在飞机各区域内完成对机载设备组件的操作、测试和拆装等训练。

DVE中一致性控制的效果可以用操作的一致性和实时性来进行评估。操作的一致性可以通过一致度来表示,操作的实时性可通过响应时间来表示,下面给出操作的一致度和响应时间的定义。

定义2操作的响应时间:操作oi的触发时间为Tt(ni,oi),操作oi在本地节点ni上的执行时间为Te(ni,oi),则操作oi的响应时间为Te(ni,oi)-Tt(ni,oi)。

实验仿真模拟10个节点在随机变化的网络传输延迟中进行虚拟维修操作。DVE中每1秒进行一次本地滞后时间的调整,设置初始滞后时间为120 ms。模拟网络的传输延迟随时间变化的情况如图5所示。

图5 网络传输的延迟时间变化

在DVE的一致性控制中分别采用LockStep方法(LS)、延迟一致性的本地滞后方法(DC)和本文中动态延迟的本地滞后方法(DD)对一致性和实时性进行评估,结果如图6和图7所示。

图6 操作的一致度比较

图7 操作的响应时间比较

在图6和图7中,横坐标表示时间,纵坐标分别表示一致度和响应时间。 可以看出LockStep方法的操作一致度一直保持为1,但其响应时间受网络传输延迟影响程度高,在延迟较高时,响应时间基本高于150 ms,实时性差。该方法通过阻塞各节点的时钟推进保证了一致度,但时钟的阻塞破坏了操作的实时性,成为了该方法在面对大量、快速的实时交互需求时的瓶颈。延迟一致性的控制方法不延迟操作在本地的执行时间,因此操作的响应性基本保持为0 ms,具有优秀的实时性,但这也导致操作在各节点执行顺序不同,具有较差的一致性,操作一致度最低时仅为0.6。动态延迟的本地滞后方法在网络延迟稳定时一致度基本保持为1,有较高的操作一致度,在传输延迟突然增大时会出现不一致现象,一致度会下降到0.8,但随后也能较快上升到1,恢复一致性。在实时性方面,该方法的响应时间小于LockStep方法,并且在传输延迟剧烈变化的情况下也能稳定在50~150 ms之间,满足DVE中用户交互的需求。

上述实验说明了动态延迟的本地滞后方法改善了现有一致性控制方法的不足,在复杂网络状况下,不仅保证了一致性,还具有一定的操作实时性。

4 结 语

一致性控制是分布式虚拟环境运行的基础和关键,仿真结果表明动态延迟的本地滞后方法能够满足一致性控制的需求,且提供良好的操作实时性。此外,对于节点间延迟时间的过滤,本文采用了删除二叉搜索树中最大值的方法。下一步工作将具体分析如何在保证操作实时性的同时,更精确地过滤延迟时间。

猜你喜欢
延迟时间实时性一致性
关注减污降碳协同的一致性和整体性
公民与法治(2022年5期)2022-07-29 00:47:28
注重教、学、评一致性 提高一轮复习效率
IOl-master 700和Pentacam测量Kappa角一致性分析
基于规则实时性的端云动态分配方法研究
高技术通讯(2021年3期)2021-06-09 06:57:24
二氧化碳对乙烷燃烧着火延迟时间的影响
煤气与热力(2021年3期)2021-06-09 06:16:22
LTE 系统下行链路FDRX 节能机制研究
基于分层COX模型的跟驰反应延迟时间生存分析
基于虚拟局域网的智能变电站通信网络实时性仿真
航空电子AFDX与AVB传输实时性抗干扰对比
延迟时间对气辅注射成型气体穿透行为影响的数值模拟和实验研究
中国塑料(2016年8期)2016-06-27 06:35:02