劉家學(xué) 王 浩 耿 宏

(中國(guó)民航大學(xué)電子信息與自動(dòng)化學(xué)院 天津 300300)

0 引 言

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

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

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

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

1 本地滯后的原理和模型

1.1 本地滯后的原理

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

圖1 本地滯后的原理

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

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

有限狀態(tài)機(jī)，又稱有限狀態(tài)自動(dòng)機(jī)，是一種具有離散輸入輸出的數(shù)學(xué)模型，可以表示有限個(gè)狀態(tài)之間的相互轉(zhuǎn)移[9-10]。一個(gè)系統(tǒng)的有限狀態(tài)機(jī)可以表示為一個(gè)五元組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ù)。其中λ和μ也可用時(shí)序關(guān)系表示為：s(t+1)=λ(s(t),x(t))，y(t)=μ(s(t),x(t))。

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

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

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

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

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

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

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

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

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

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

2.2 操作發(fā)送階段

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

2.3 操作接收階段

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

圖3 操作接收流程

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

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

2.4 本地滯后時(shí)間的動(dòng)態(tài)延遲

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

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

圖4 存儲(chǔ)延遲信息的二叉搜索樹

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

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

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

3 實(shí)驗(yàn)仿真

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

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

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

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

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

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

圖6 操作的一致度比較

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

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

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

4 結(jié) 語

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