分布式虛擬環境中動態延遲的本地滯后方法

劉家學 王 浩 耿 宏

(中國民航大學電子信息與自動化學院 天津 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 結 語

一致性控制是分布式虛擬環境運行的基礎和關鍵，仿真結果表明動態延遲的本地滯后方法能夠滿足一致性控制的需求，且提供良好的操作實時性。此外，對于節點間延遲時間的過濾，本文采用了刪除二叉搜索樹中最大值的方法。下一步工作將具體分析如何在保證操作實時性的同時，更精確地過濾延遲時間。