劉家學 王 浩 耿 宏

(中國民航大學電子信息與自動化學院 天津 300300)

0 引 言

分布式虛擬環(huán)境[1](Distributed Virtual Environment，DVE)提供一個共享的虛擬世界，通過網(wǎng)絡(luò)將位于不同地理位置的多個用戶相連接，用戶之間可以共享信息產(chǎn)生交互，為某一共同目標進行協(xié)同仿真。

DVE通常采用復(fù)制式結(jié)構(gòu)[2]，其中每個用戶使用的計算機都可以看作一個節(jié)點，節(jié)點中存有整個虛擬環(huán)境的副本，任意節(jié)點的用戶進行操作后，該操作不僅會對本地副本的狀態(tài)造成影響，還會通過網(wǎng)絡(luò)傳給其他節(jié)點并執(zhí)行。實際運行中，網(wǎng)絡(luò)傳輸?shù)难舆t具有隨機性，且不可避免，這會導致各節(jié)點執(zhí)行操作的時間和順序不同，從而使副本狀態(tài)發(fā)生不一致。同時，延遲也會導致操作在異地節(jié)點上的實時響應(yīng)時間變長，影響用戶交互的真實感。因此，必須解決DVE中的一致性與實時性問題。

鎖同步[3](LockStep)算法將DVE的時鐘劃分為若干周期并阻塞各節(jié)點時鐘的推進，只有全部節(jié)點都執(zhí)行了操作且副本達到相同的狀態(tài)后才允許進入下一時鐘周期。雖能保證一致性，但操作的實時性很差，無法適用于頻繁交互的系統(tǒng)。在DR(Dead Reckoning)算法[4-5]中，各節(jié)點利用相同的DR模型預(yù)測DVE的狀態(tài)，同時接收來自其他節(jié)點的實際狀態(tài)，當本地節(jié)點的預(yù)測值和實際值的誤差超過一定范圍時就用實際值更新本地狀態(tài)。雖然該方法中用戶操作的響應(yīng)時間很短，但使用過程中會出現(xiàn)大量短時間的不一致，需要不斷進行回滾。文獻[6]采用了延遲一致性控制方法，該方法不延遲本地操作處理過程，而是將異地操作延遲一定的時間，雖能保證操作的實時性，但會因各節(jié)點執(zhí)行操作順序的混亂而導致不一致。

針對上述問題，本文采用本地滯后的方法，延遲操作在各節(jié)點的執(zhí)行時間，并通過周期性地更新本地滯后時間來實現(xiàn)動態(tài)調(diào)整響應(yīng)時間，保證了DVE中用戶的實時交互。

1 本地滯后的原理和模型

1.1 本地滯后的原理

本地滯后的原理是用戶在本地節(jié)點觸發(fā)一個操作后，該操作不會被立即執(zhí)行，而是延遲一段時間再執(zhí)行[7-8]，這段延遲的時間被稱為本地滯后時間。在延遲的過程中，本地節(jié)點會將該操作傳遞到其他節(jié)點，以本地滯后時間抵消傳輸時間，從而達到所有節(jié)點同時執(zhí)行操作的效果，如圖1所示。

圖1 本地滯后的原理

1.2 分布虛擬環(huán)境的狀態(tài)模型

在DVE中，各節(jié)點獨立運行位于本地的虛擬環(huán)境副本，通過互相傳遞操作自行更新本地副本的狀態(tài)，這種更新的獨立性很容易造成各節(jié)點的狀態(tài)不一致，因此引入有限狀態(tài)機(Finite-state machine，F(xiàn)SM)的模型來保證狀態(tài)更新的一致性。

有限狀態(tài)機，又稱有限狀態(tài)自動機，是一種具有離散輸入輸出的數(shù)學模型，可以表示有限個狀態(tài)之間的相互轉(zhuǎn)移[9-10]。一個系統(tǒng)的有限狀態(tài)機可以表示為一個五元組M=(S,X,Y,λ,μ)，S={s0,s1,…,sn}是狀態(tài)集合，X={x0,x1,…,xn}是輸入集合，Y={y0,y1,…,yn}是輸出集合，λ:S×X→S是狀態(tài)轉(zhuǎn)移函數(shù)，μ:S×X→Y是輸出轉(zhuǎn)移函數(shù)。其中λ和μ也可用時序關(guān)系表示為：s(t+1)=λ(s(t),x(t))，y(t)=μ(s(t),x(t))。

在DVE的各個節(jié)點的狀態(tài)S一致的情況下，如圖2所示，只要輸入的x(t)和節(jié)點的狀態(tài)s(t)是確定的，那么在函數(shù)λ和μ的作用下，系統(tǒng)的下一狀態(tài)s(t+1)和輸出y(t)就是確定的。

圖2 有限狀態(tài)機的模型

2 動態(tài)延遲的本地滯后方法

2.1 動態(tài)延遲的方法描述

為了保證一致性的同時還能應(yīng)對網(wǎng)絡(luò)傳輸中的延遲波動，本文提出了一種動態(tài)延遲的本地滯后方法。根據(jù)網(wǎng)絡(luò)狀況調(diào)節(jié)本地滯后時間，該方法由以下幾個階段進行控制。

(1) 初始化階段。通過NTP協(xié)議[11-12]對DVE中的各節(jié)點進行時鐘同步，保證各節(jié)點具有相同的時間戳。根據(jù)當前的操作實時性需求設(shè)定一個合適的本地滯后時間值，在DVE運行的初期，各節(jié)點按此時間延遲本地操作。

(2) 操作發(fā)送階段。對于操作的觸發(fā)節(jié)點，先不執(zhí)行觸發(fā)的操作，而是將操作發(fā)送給其他節(jié)點，發(fā)送時，要在操作的數(shù)據(jù)結(jié)構(gòu)中加入操作的觸發(fā)時間。發(fā)送后，根據(jù)本地滯后時間設(shè)定操作在本地的執(zhí)行時間。

(3) 操作接收階段。對于操作的接收節(jié)點，首先記錄操作的接收時間，并由收到的操作數(shù)據(jù)結(jié)構(gòu)中的觸發(fā)時間計算出兩節(jié)點間網(wǎng)絡(luò)傳輸?shù)难舆t時間。然后利用操作的觸發(fā)時間和此時的本地滯后時間計算出該操作在當前節(jié)點的執(zhí)行時間，通過比較操作的執(zhí)行時間與接收時間來確定此操作是否已經(jīng)超時。如未超時，則按照計算出的執(zhí)行時間執(zhí)行該操作；如已超時，則立即執(zhí)行此操作或進行回滾[13-14]。

(4) 本地滯后時間的動態(tài)調(diào)整階段。將DVE的運行過程劃分為若干調(diào)整周期，記錄每個周期內(nèi)節(jié)點間的傳輸延遲，調(diào)整周期結(jié)束后，用本周期記錄的傳輸延遲來估算下一周期的本地滯后時間。

上述方法中，操作的發(fā)送、接收和本地滯后時間的動態(tài)調(diào)整是最重要的環(huán)節(jié)，下面詳細闡述這三方面內(nèi)容。下文中，用有向圖G=(N,D)代表整個DVE，N={n1,n2,…,nn}表示DVE中所有仿真節(jié)點的集合，D={d11,d12,…,d1n,…,dnn}表示節(jié)點間的傳輸延遲時間，D中任意一個dij代表節(jié)點ni與nj間的傳輸延遲。用O代表系統(tǒng)中所有操作的集合，對于給定操作oi∈O，Tt(ni,oi)表示操作oi在ni節(jié)點上的觸發(fā)時間，Te(ni,oi)表示操作oi在ni節(jié)點上的執(zhí)行時間，Tr(ni,oi)表示ni節(jié)點接收到操作oi的時間，Tlag表示系統(tǒng)的本地滯后時間。

2.2 操作發(fā)送階段

對于DVE中的節(jié)點nj，用戶觸發(fā)操作oi后要先將oi發(fā)送給其他節(jié)點。發(fā)送時，需在oi的數(shù)據(jù)結(jié)構(gòu)中加入操作觸發(fā)的時間Tt(nj,oi)。發(fā)送后，將操作在本地滯后一段時間后再執(zhí)行，由本地滯后時間Tlag可計算出操作oi在本地節(jié)點的執(zhí)行時間為Te(nj,oi)=Tt(nj,oi)+Tlag。

2.3 操作接收階段

根據(jù)DVE中當前運行的調(diào)整周期確定此時的本地滯后時間Tlag。在此周期內(nèi)，節(jié)點ni在收到節(jié)點nj傳來的oi后，首先記錄該操作的接收時間Tr(ni,oi)，然后從oi的數(shù)據(jù)結(jié)構(gòu)中解析出操作的觸發(fā)時間Tt(nj,oi)。兩節(jié)點間網(wǎng)絡(luò)傳輸?shù)难舆t時間dij=Tr(ni,oi)-Tt(nj,oi)，操作oi在節(jié)點ni上的執(zhí)行時間Te(ni,oi)=Tt(nj,oi)+Tlag。當Te(ni,oi)≥Tr(ni,oi)時，說明未超過執(zhí)行時間，此操作及時到達，可按照Te(ni,oi)照常執(zhí)行；當Te(ni,oi)

圖3 操作接收流程

采用上述方法進行操作的收發(fā)時，對于任意一個操作oi，該操作都是在觸發(fā)時間Tt(nj,oi)的基礎(chǔ)上，在本地節(jié)點nj上滯后了Tlag后執(zhí)行的。操作oi在其他節(jié)點上也是以Tt(nj,oi)為基準，延遲了Tlag才執(zhí)行的。因此，DVE中所有的未超時操作的執(zhí)行時間的都是相同的，保證了一致性。

網(wǎng)絡(luò)中傳輸?shù)难舆t是存在波動的，如果Tlag一直保持不變，當節(jié)點間傳輸延遲變大時，會出現(xiàn)頻繁的操作超時現(xiàn)象；當延遲變小時，如不及時調(diào)小Tlag，會影響操作的實時性。因此，需要實現(xiàn)本地滯后時間的動態(tài)延遲。

2.4 本地滯后時間的動態(tài)延遲

本地滯后時間的動態(tài)延遲主要有兩個過程：節(jié)點間延遲時間dij的存儲和本地滯后時間Tlag的更新。為滿足DVE中操作實時性要求，采用基于二叉搜索樹的數(shù)據(jù)結(jié)構(gòu)對dij進行快速存儲和讀取[15]。

每個調(diào)整周期開始時，DVE創(chuàng)建一棵二叉搜索樹，樹的根節(jié)點取值為上一周期的Tlag。然后從根節(jié)點開始，將計算所得的dij插入到該樹中，如果新插入的值比當前節(jié)點的值大，則插入到該節(jié)點的右子樹，否則插入到左子樹。為了后續(xù)的查找功能，節(jié)點要記錄其右子樹包含的全部節(jié)點數(shù)量的計數(shù)值R，每往右子樹插入一個值就在該節(jié)點累加一次計數(shù)值。如圖4所示，該二叉搜索樹記錄了9個節(jié)點間的延遲信息，每個節(jié)點左側(cè)的值代表dij，其中是右側(cè)的值代表R。

圖4 存儲延遲信息的二叉搜索樹

在每個調(diào)整周期結(jié)束時，需要更新本地滯后時間Tlag。為保證DVE中各節(jié)點不出現(xiàn)超時情況，需使用二叉搜索樹中最大的dij作為下一調(diào)整周期中各個節(jié)點的Tlag。網(wǎng)絡(luò)傳輸中延遲的波動可能會造成延遲時間遠大于正常的延遲時間的情況，為去除這些數(shù)值的影響，需要對二叉搜索樹中的值進行過濾，去除掉其中最大的M個值。由于樹中的節(jié)點總數(shù)Ntotal是一定的，令m=Ntotal-M，在二叉搜索樹中第m大的值即為所需要的Tlag。

可以利用在二叉搜索樹中保存的計數(shù)值R在樹中查找第m大的值。二叉搜索樹中每個節(jié)點的左子樹中的值都小于該節(jié)點的值，而右子樹中的值都大于該節(jié)點的值，所以對于節(jié)點ni，在以ni為根節(jié)點的二叉搜索樹中，ni的值是第R+1大的。因此，只需從根節(jié)點出發(fā)，將m與R+1進行比較：若mR+1，說明要找的值比此節(jié)點的值小，則需要到以左子樹為根節(jié)點的樹中找第m-(R+1)大的節(jié)點；若m=R+1，說明要找的值就是此節(jié)點的值。查找次數(shù)小于等于該二叉搜索樹的層數(shù)。上述過程偽代碼如算法1所示。

算法1 查找二叉搜索樹中最大值偽代碼FindNthMax(bsTree,m)1:ifn<(GetChildCount(bsTree->root)+1)2: thenreturnFindNthMax(bstress->root->rightsubtree,m)//在節(jié)點的右子樹中查找第m大的值3: elseifm>(GetChildCount(bstress->root)+1)4: thenreturnFindNthMax(bstress->root->leftsubtree,m-(GetChildCount(bstress->root))+1)//在節(jié)點左子樹中查找第m-(R+1)大的值5: else6: returnGetDelayNumber(bstress->root)//當前節(jié)點為所求值

3 實驗仿真

為驗證動態(tài)延遲的本地滯后方法的可行性與性能，本文通過自主研發(fā)的分布式虛擬維修系統(tǒng)對該方法進行評估。分布式虛擬維修系統(tǒng)可以提供一個分布式虛擬維修環(huán)境，使多個用戶組成小組，協(xié)同完成A320飛機的維護訓練任務(wù)。在系統(tǒng)中，用戶能在飛機各區(qū)域內(nèi)完成對機載設(shè)備組件的操作、測試和拆裝等訓練。

DVE中一致性控制的效果可以用操作的一致性和實時性來進行評估。操作的一致性可以通過一致度來表示，操作的實時性可通過響應(yīng)時間來表示，下面給出操作的一致度和響應(yīng)時間的定義。

定義2操作的響應(yīng)時間：操作oi的觸發(fā)時間為Tt(ni,oi)，操作oi在本地節(jié)點ni上的執(zhí)行時間為Te(ni,oi)，則操作oi的響應(yīng)時間為Te(ni,oi)-Tt(ni,oi)。

實驗仿真模擬10個節(jié)點在隨機變化的網(wǎng)絡(luò)傳輸延遲中進行虛擬維修操作。DVE中每1秒進行一次本地滯后時間的調(diào)整，設(shè)置初始滯后時間為120 ms。模擬網(wǎng)絡(luò)的傳輸延遲隨時間變化的情況如圖5所示。

圖5 網(wǎng)絡(luò)傳輸?shù)难舆t時間變化

在DVE的一致性控制中分別采用LockStep方法(LS)、延遲一致性的本地滯后方法(DC)和本文中動態(tài)延遲的本地滯后方法(DD)對一致性和實時性進行評估，結(jié)果如圖6和圖7所示。

圖6 操作的一致度比較

圖7 操作的響應(yīng)時間比較

在圖6和圖7中，橫坐標表示時間，縱坐標分別表示一致度和響應(yīng)時間。 可以看出LockStep方法的操作一致度一直保持為1，但其響應(yīng)時間受網(wǎng)絡(luò)傳輸延遲影響程度高，在延遲較高時，響應(yīng)時間基本高于150 ms，實時性差。該方法通過阻塞各節(jié)點的時鐘推進保證了一致度，但時鐘的阻塞破壞了操作的實時性，成為了該方法在面對大量、快速的實時交互需求時的瓶頸。延遲一致性的控制方法不延遲操作在本地的執(zhí)行時間，因此操作的響應(yīng)性基本保持為0 ms，具有優(yōu)秀的實時性，但這也導致操作在各節(jié)點執(zhí)行順序不同，具有較差的一致性，操作一致度最低時僅為0.6。動態(tài)延遲的本地滯后方法在網(wǎng)絡(luò)延遲穩(wěn)定時一致度基本保持為1，有較高的操作一致度，在傳輸延遲突然增大時會出現(xiàn)不一致現(xiàn)象，一致度會下降到0.8，但隨后也能較快上升到1，恢復(fù)一致性。在實時性方面，該方法的響應(yīng)時間小于LockStep方法，并且在傳輸延遲劇烈變化的情況下也能穩(wěn)定在50～150 ms之間，滿足DVE中用戶交互的需求。

上述實驗說明了動態(tài)延遲的本地滯后方法改善了現(xiàn)有一致性控制方法的不足，在復(fù)雜網(wǎng)絡(luò)狀況下，不僅保證了一致性，還具有一定的操作實時性。

4 結(jié) 語

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