分布式虛擬地理環(huán)境中時間同步問題研究

辛 欣 ,游 雄 ,劉 芳 ,趙曉亮

(信息工程大學 測繪學院,河南 鄭州 450052)

分布式虛擬地理環(huán)境中時間同步問題研究

辛 欣 ,游 雄 ,劉 芳 ,趙曉亮

(信息工程大學 測繪學院,河南 鄭州 450052)

分布式虛擬地理環(huán)境中的時間同步問題是達成系統(tǒng)時空一致,確保仿真正確,是用戶對虛擬地理環(huán)境形成正確認識的前提條件。文中針對分布式虛擬地理環(huán)境中3個時間概念,重點對機器時間和仿真時間同步問題進行研究,基于網(wǎng)絡延時、各仿真節(jié)點時間偏移和PC機及操作系統(tǒng)本身時間分辨率不高的因素對時間不同步造成的影響,提出時間同步自適應模型和算法。

分布式虛擬地理環(huán)境;時間同步;自然時間;機器時間;仿真時間

分布式虛擬地理環(huán)境(Distributed Virtual Geographic Environment,DVGE)[1-4]是利用虛擬現(xiàn)實技術[5]與網(wǎng)絡技術建立起來的分布共享虛擬地理空間,是一種可供多用戶同時異地參與的基于可計算信息的沉浸式交互環(huán)境[6]。

在分布式虛擬地理環(huán)境系統(tǒng)中,時間是系統(tǒng)進行仿真所面臨的很重要的概念,其中有3個主要的時間概念:自然時間(N T),又稱真實時間或實際時間,指自然界客觀存在的真實時間;機器時間(M T),又稱物理時間,指仿真系統(tǒng)根據(jù)仿真計算機的時鐘物理部件產生的時間計數(shù)所折算的時間;仿真時間(ST),又稱虛擬時間或仿真模型時間,指仿真模型運行時由仿真系統(tǒng)產生的仿真世界的時間[7]。

1 自然時間同步

對于自然時間的同步B IH通過引入閏秒(leapsecond)解決了問題,當用原子計時和用太陽秒計時的差距增到800μs時,使用閏秒。這種糾正使在基于連續(xù)的 TA I秒時間系統(tǒng)加值,但卻可以和太陽的運動保持一致,它稱作統(tǒng)一協(xié)調時間(Universal Time Coordinated,U TC),U TC是所有現(xiàn)代人使用的時間,它基本上取代了老標準——格林威治天文時間。為了保持時間的精確,操作系統(tǒng)在一年內必須使用專用的軟件。到目前為止,U TC中引入閏秒大約有30次。通過對DVGE系統(tǒng)中時間服務器連接到可接收U TC信號的設備上,可以實現(xiàn)系統(tǒng)內部與外部的自然時間同步,其同步精度可以使得上百萬個時鐘能夠在幾個U TC毫秒內同步,甚至更高。

2 機器時間同步性分析

每臺計算機上的計時器通常是由一個精確的石英晶體制成,石英晶體以一定的頻率振蕩,其計數(shù)頻率約為3.6 M Hz,該頻率也會因環(huán)境溫度變化、磁場、震動等隨機因素的影響而有所變化。與每個晶體相關的是2個寄存器、1個計數(shù)器和1個保持寄存器。每次振蕩時計數(shù)器減1,當計數(shù)器減到0時,產生一次中斷,計數(shù)器重新在保持寄存器中裝入起始值,通過這種編程方法可以使得一個計時器每秒產生60個中斷或以其他希望的頻率產生中斷成為可能,每次中斷都稱作一個時鐘點(Clock Tick)。一旦當系統(tǒng)中有n臺計算機時,引入了多個CPU時間系統(tǒng),每個CPU將擁有自己的時鐘。所有n個計算機中的石英晶體計時器將以略微不同的頻率振蕩,導致時間逐漸不同步,盡管每個晶體的振蕩頻率總是相當穩(wěn)定,要保證不同計算機上的晶體以完全相同的頻率震蕩是不現(xiàn)實的,并且隨著仿真計算機本身時間偏移的積累,使得計算機本地時間不再精確,導致無法在分布式虛擬地理環(huán)境系統(tǒng)內部,保持各仿真節(jié)點上的機器時間一致,從而造成時間產生不同步現(xiàn)象的發(fā)生。

計算機器時間的數(shù)學模型[8]為

式中:t為當前時間,T(t)是從時間t0開始到當前時間t的時鐘偏移量,R為時鐘頻率偏移,D為由于計算機的可變頻率振蕩器的老化引起的漂移率。通常情況下,時鐘頻率偏移 R主要受溫度的影響較大,其誤差的范圍可從幾PPM(Parts-Per-M illion)到幾百PPM。由式(1)的右邊第三項引起的誤差主要由其前兩項決定,因此,可以只對式(1)的前兩項進行計算,確定機器時間的偏移量,從而調整計算機本地時間,確保時間保持一致。

從上面的分析可以看出,引起時鐘偏差的主要因素是可變頻率振蕩器的頻率漂移。因此,如果利用PC機性能計數(shù)器構造新的時鐘,理論上時間分辨率可高達0.3μs左右(性能計數(shù)器的計數(shù)周期),而在實際測試中Window s 2000/N T操作系統(tǒng)下,以GPS時統(tǒng)板提供的時間為基準,在某臺主頻為2.6GHz的DELLE PC機上對系統(tǒng)時間函數(shù) Get System Time的時間誤差積累情況和時間分辨率進行測試,測試結果如圖1所示。從測試結果可以看出,系統(tǒng)時間函數(shù)分辨率為15～16m s,并且時間誤差積累速度很快,大約24 m s/h。通過對多臺其它型號的PC機進行相同測試,從測試結果來看,時間分辨率都是大致相同的,時間漂移率也大致一樣。因此,可以得出這樣的結論:PC機系統(tǒng)時鐘時間分辨率只有15～16m s,時間漂移率約為60m s/h。受計算機操作系統(tǒng)時間分辨率較低和時間漂移等因素的影響,DVGE系統(tǒng)的時間同步精度往往不可能很高,也就是說如果在分布式實時仿真系統(tǒng)中使用系統(tǒng)時鐘,不管時間同步有多精確,計算機之間的時間同步精度都不可能超過16 m s,即不可能超過系統(tǒng)時間的分辨率。并且時間同步的網(wǎng)絡開銷和CPU時間開銷也會比較大,而采用硬件同步模式不但會增加系統(tǒng)成本,也不利于系統(tǒng)擴展。因此,為了在不增加系統(tǒng)硬件成本的前提下,獲取高的時間同步精度,就必須為 PC機構建新的高性能(高時間分辨率、低時間漂移率)時間同步算法。

圖1 Get System Time函數(shù)時間誤差累積曲線圖

3 仿真時間同步性分析

實際上在分布式虛擬地理環(huán)境仿真中,如果兩個進程不相互作用,它們的時間就無需同步,即使缺少同步也察覺不出來,不會產生什么問題,所以全部機器并不需要在進程時間上保持一致,而是在事件發(fā)生的時間順序上要完全一致,也就是說在同一時間上達到一致就足夠了,重要的不是它們是否都與自然時間嚴格一致,而是系統(tǒng)內部各節(jié)點時間的一致。自然時間和機器時間相比較,仿真時間對系統(tǒng)仿真可靠性的影響最直接、最關鍵。其所造成的不一致對分布式虛擬地理環(huán)境的影響主要表現(xiàn)在兩個方面:①導致仿真過程中的計算錯誤;②影響用戶對虛擬地理環(huán)境的正確認識。因此,對于仿真時間的同步性問題關注程度也是最高。

對于仿真時間同步性分析的思路:①假設在DVGE中仿真執(zhí)行過程中,除時間不同步外不存在其它影響實體狀態(tài)計算正確性的不穩(wěn)定因素,其中單個仿真節(jié)點的仿真過程如圖2所示;②將實際計算出的實體真實狀態(tài)變化過程及結果與理論情況下計算出的實體真實狀態(tài)變化過程及結果進行比較,如果它們之間的差異符合仿真計算正確性要求,說明該過程中的仿真時間同步性對于保證分布式虛擬地理環(huán)境中仿真計算正確性來說,是可以接受的[9-10];③如果對于任意仿真節(jié)點,它輸出的虛擬地理環(huán)境變化過程同理論仿真計算得到的實體真實狀態(tài)相比較,可以被用戶接受,就說明該過程中的仿真時間同步性對于保證用戶正確認識虛擬地理環(huán)境來說,是可以容忍的。

圖2 單個節(jié)點上仿真過程中的時間延遲

從圖2中可以看出,影響DVGE中仿真時間不同步主要是由網(wǎng)絡延遲和機器時間不同步導致的延遲。其中,網(wǎng)絡延遲導致的延遲是正數(shù),機器時間不同步導致的延遲可以是正數(shù)也可以是負數(shù),當仿真節(jié)點的時間落后于發(fā)送節(jié)點的時間時,機器時間不同步導致的延遲是負數(shù),否則為正數(shù)。

4 DVGE系統(tǒng)中時間同步自適應模型

保持實體對象在各個計算節(jié)點上時間同步的方法有很多,例如,可進行時間扭曲和異地延時,但從其根源上講,認為其關鍵在于保證不同事件的發(fā)生時間對所有相關計算節(jié)點來說是相同的。由于各類分布式虛擬環(huán)境的應用領域不同、目標不同、環(huán)境內實體的類型、特點不同,因而對時間一致性的要求強度也各不相同。例如,用于協(xié)同工作的分布式虛擬環(huán)境在工作對象為連續(xù)媒體時,對時間一致性的要求很高;而分布式虛擬戰(zhàn)場環(huán)境通常在實體交互時對時間一致性要求較強,除此之外對實體其它狀態(tài)時間誤差要求較低;另外,不同系統(tǒng)的操作平臺對時間一致性的影響也不盡相同。因此,對DVGE系統(tǒng)中時間同步模型的建立必須要有一定的自適應性。

4.1 DVGE系統(tǒng)中標準時間基的確立

對系統(tǒng)中的各節(jié)點時間進行同步,首先,必須要確立一個標準時間基,其直接關系到時間同步的精度。可以通過統(tǒng)計DVGE系統(tǒng)中所有時鐘運行時間段的均值來獲得這個標準時間基。隨著仿真的進行和時間變換,可以再次選擇運行更為準確的時鐘作為標準時間基節(jié)點,因此,它的確立過程是動態(tài)的。其思路是:

首先,選中系統(tǒng)中一個節(jié)點,并假設其為標準時間基節(jié)點。這個標準時間基節(jié)點向下面每個從節(jié)點發(fā)出一個收集時間信息的廣播。然后,根據(jù)下面從節(jié)點返回的時間值來計算當前標準時間。如果此時所使用的時間是即時時間,那么網(wǎng)絡鏈路的狀態(tài)將對即時時間的傳送帶來很大的影響。由于采用的是廣播方式,下面的節(jié)點幾乎是在同一時刻進行應答,這樣大量時間信息幾乎會同時到達標準時間基節(jié)點,為了避免造成網(wǎng)絡的擁塞,導致時間延時的增大,可以定義一個時間間隔τ,在τ時間間隔內,下面的各個節(jié)點主動向標準時間基節(jié)點發(fā)送當前的時間信息。在具有 N個時間節(jié)點的系統(tǒng)中,每個非標準時間基節(jié)點以周期τ向標準時間基節(jié)點發(fā)送帶有時間戳的數(shù)據(jù)報。其對應的時序圖如圖3所示。

圖3 發(fā)送數(shù)據(jù)報時序

在進行時間比較時,使用的是一個連續(xù)的時間段,而不是某一刻的時間值[11]。在這里比較 tj-ti和 t′j-t′i。如果在 t′i+1時刻發(fā)送出去的時間標識遇到較大的網(wǎng)絡延遲時,在ti+1時刻到達標準時間基節(jié)點,如果使用此時刻的時間來判定2個時間之間的誤差是很不精確的。但是從長時間的運行看,鏈路狀態(tài)還是相對穩(wěn)定的。如果采用tj-ti和t′jt′i來計算2個時鐘間的誤差的話,就能有效地減小由于鏈路延遲造成的形響。在具有 N個節(jié)點的系統(tǒng)中,作為標準時間基節(jié)點在第 i次時間同步時,計算整個系統(tǒng)運行的平均時間的公式為

在完成調整時間的同時,系統(tǒng)也要重新確定標準時間基節(jié)點,即時間間隔最接近這個平均值的時間服務器為標準時間基節(jié)點。在標準時間基調整后以及當前標準時間基節(jié)點確定完成后,原標準時間基節(jié)點將發(fā)送廣播,通知下面各個節(jié)點新的標準時間基節(jié)點信息。

4.2 時間同步算法

系統(tǒng)中各時間客戶端以一定的時間周期向標準時間基節(jié)點發(fā)送同步請求,并且在發(fā)送的數(shù)據(jù)報中帶有本地的時間戳 T1。標準時間基節(jié)點收到客戶端的同步請求后響應一個數(shù)據(jù)報,其中包括3個時間戳:客戶端發(fā)送的請求數(shù)據(jù)報中的客戶端本地時間戳 T1,標準時間基節(jié)點收到同步請求時的時間戳T2和標準時間基節(jié)點發(fā)送響應數(shù)據(jù)報時的時間戳T3?？蛻舳私邮艿綐藴蕰r間基節(jié)點的響應數(shù)據(jù)報后,向其中添加第4個時間戳,即客戶端收到此數(shù)據(jù)報時的時間戳 T4。設系統(tǒng)中第k-1次與第 k次同步,間隔時間延時為 T′delay,并且認為客戶端到標準時間基節(jié)點消息傳輸時間延時與標準時間基節(jié)點到客戶端的消息傳輸時間延時近似相同,設為 Ttrans,在此基礎上可以計算出時間同步間隔延遲和網(wǎng)絡信息傳輸延時為

在系統(tǒng)完成第一輪時間同步后,為了減少時鐘同步過程中對網(wǎng)絡帶寬的需求,可以根據(jù)DVGE的仿真需要,控制系統(tǒng)時間同步的時間間隔,當時間同步精度較差時,同步的時間間隔就相對較短;當時間同步精度較好時,則同步的時間間隔較長,或者當某一節(jié)點的時間與標準時間基的誤差超過某一個閾值時,系統(tǒng)就開始啟動同步過程。

5 結束語

分布式系統(tǒng)本身的特點,決定著各節(jié)點的物理地域有所不同,由于分布式虛擬地理環(huán)境實體類型日益復雜、規(guī)模日益擴大,再加之PC機計時器和操作系統(tǒng)的局限,使在DVGE中時間同步問題成為一個重要而又不能從根本上徹底解決的問題。影響系統(tǒng)時間同步的因素多而復雜,解決的方法也還有很多,比如推算定位(DR)技術、時間扭曲技術、異地狀態(tài)延遲技術、相關數(shù)據(jù)過濾技術、減少心跳技術等。由于單一的時空一致性控制技術通常局限性較大、應用領域也比較有限,如滯后策略很難確定一個滿足各項要求的滯后量;回卷策略不適合實時仿真,有時會給用戶造成仿真結果自相矛盾的印象;推算定位策略有時會造成推算結果與仿真結果的不一致。因此,集成多種技術來共同實現(xiàn)DVGE的時間同步,是達成系統(tǒng)時空一致,保證仿真正確,用戶對虛擬地理環(huán)境的正確認識的必然要求。

[1]潘志庚,姜曉紅.分布式虛擬環(huán)境綜述[J].軟件學報,2000,11(4):461-467.

[2]D.LEE,M.L IM,S.HAN.A tlas:a scalable network framework for distributed virtual environments[J].Bonn,Germany,September 30-October,2002,2.

[3]惠天舒,李伯虎.分布交互仿真技術綜述[J].系統(tǒng)仿真學報,1998,10(1):1-7.

[4]陳 誼.分布式虛擬環(huán)境關鍵技術及其在復雜系統(tǒng)仿真中的應用研究[D].北京:北京理工大學,2002.

[5]汪成為,高 文,王行仁.靈境(虛擬現(xiàn)實)技術的理論、實現(xiàn)和應用[M].北京:清華出版社,1996.

[6]楊孟洲,姜曉紅.多用戶分布式虛擬環(huán)境系統(tǒng)MUDVE的實現(xiàn)技術[J].計算機輔助設計與圖形學學報,2001,13(2):173-178.

[7]李 軍,黃紹軍,龔光紅.戰(zhàn)術仿真系統(tǒng)中數(shù)據(jù)交互的實時性研究[J].系統(tǒng)仿真學報,2006,18(2):381-382.

[8]DAV ID L.M ILLS,Computer Network Time Synchronization Executive Summary,http://www.eecis.udel.edu/%7emills/exec.htm l,2003.3.20/2004.2.5.

[9]李 元.利用相似理論來指導建模[J].計算機仿真,1999,16(1):49-51.

[10]M.MAUVE,J.VOGEL,V H IL T et al..Local-lag and Timewarp:Providing Consistency fo r Rep licated Continuous App lications.IEEE Transactions on M ultimedia,2004,6(1):45-57.

[11]賀 鵬,李 菁,吳海濤.網(wǎng)絡時間同步算法研究和實現(xiàn)[J].計算機應用,2003,23(2):15-17.

The research of time synchronization in distributed virtual geographic environment

XIN Xin,YOU Xiong,L IU Fang,ZHAO Xiao-liang
(Institute of Surveying and Mapping,Info rmation Engineering University,Zhengzhou 450052,China)

The time synchronization in distributed virtual geographic environment is the p rem ise to timespace consistency of the system and to make sure it can simulate co rrectly,in w hich w ay the user can cognize the virtual geographic environment accurately.In this paper,among the three time concep tions in distributed virtual geographic environment,the research of machine time synchronization and simulation time synchronization have been emphasized.A self-adap tive time synchronization model and algorithm have been put forward w hich based on network time-lapse,time deviation of system nodes and low-time-dip of operating system and computer itself.

distributed virtual geographic environment;time synchronization;natural time;machine time;simulation time

TP273

A

1006-7949(2010)01-0021-04

2009-05-17

辛 欣(1981-),男,博士研究生.

[責任編輯李銘娜]