劉冬 趙躍龍 曾文英，3

(1．華南理工大學計算機科學與工程學院，廣東廣州510640;2．暨南大學計算機科學系，廣東廣州510632;3．廣東科學技術職業(yè)學院計算機工程技術學院，廣東珠海519090)

實時在線交互應用(ROIA)是近幾年來出現的一類基于互聯網的、云計算環(huán)境下的新分布式應用［1］，包括交互式電子學習和大型多人在線游戲(MMOG)在內的應用系統等都是ROIA的典型應用．ROIA的高密集用戶交互、單應用實例高并發(fā)性、連接的隨意性、高服務質量要求，決定了ROIA需要較高的網絡帶寬和較低的網絡延遲來保證這些實時交互用戶之間的狀態(tài)一致性．為避免有限的網絡帶寬被大量的更新信息所耗盡，ROIA通常以盡可能低的頻率發(fā)送更新信息．這就需要有某種技術來彌補兩個更新信息之間ROIA用戶狀態(tài)信息的連續(xù)性，確保良好的用戶體驗．因此，如何根據現有互聯網狀況，在有限的網絡帶寬和較大的網絡延遲情況下保證狀態(tài)一致性問題，已經成為目前ROIA技術的研究熱點之一．

航位推算(DR)算法是目前在ROIA中為解決此問題而最常采用的一種技術．DR算法［2-3］最初用于分布式虛擬仿真系統中，是緩解實時性問題及減少通信量的有效方法，現已大量應用于交通、游戲等領域．文獻［3］中提出了根據虛擬角色相對位置自適應地調整閾值的DR算法．文獻［4］中提出了一種多閾值的DR算法，該算法中虛擬角色所發(fā)送的數據是經過分類的，不同類型的數據對應不同距離的虛擬角色責任域空間．文獻［5］針對點對點(P2P)環(huán)境下的ROIA提出了一種自適應調整錯誤閾值的增強DR算法模型．

在基于DR算法的更新機制中，實體的實際位置和推測位置存在不一致性，度量這種不一致性最簡單、最直接的方法就是測量實際位置和推測位置之間的空間差異．文獻［6］中證明了不一致狀態(tài)持續(xù)時間的長短對用戶感覺上的影響，并提出了一種時空不一致的度量方法，該方法綜合考慮了空間的差異和持續(xù)時間的長短．文獻［7］在減小可覺察的不一致狀態(tài)時也考慮到了不一致時間持續(xù)長短的影響．另外，更新間隔期間積累的航跡推算誤差在文獻［8-9］中被用來作為不一致性程度的一種度量．文獻［10］中提出了一種新的在消息丟失情況下提高一致性程度的DR算法的更新調度策略．

在DR算法中，如果能提高預測的準確度，則將大大提高DR算法的整體性能．文獻［11］中采用神經網絡來預測實體的速度變化．AntReckoning［12］則借鑒蟻群算法的思想來改進DR算法，以提高DR算法預測的準確度．ARIVU［13］在移動游戲環(huán)境下通過預測用戶的下一步動作來決定是否將移動設備的網卡轉入休眠狀態(tài)，從而達到節(jié)能的目的．

但傳統DR算法大多僅基于物理力學公式進行預測［14-15］，沒有考慮到應用中虛擬角色的狀態(tài)及目標對預測的影響．而在實際應用中，即使在相同的場景下，虛擬角色狀態(tài)的不同也會使得其運動軌跡有所不同．例如，當虛擬角色的生命值較高時，寶物等物品對其吸引較大，而在虛擬角色的生命值較低時，其向醫(yī)療點運動的可能性很大．因此，傳統DR算法單純考慮其慣性的思想大大降低了其預測的準確度．為此，文中提出了一種改進的DR算法，并通過仿真實驗驗證該改進算法的有效性．

1 ROIA云平臺

傳統的ROIA通常采用客戶/服務器模式，并在服務器端通過服務器集群等技術來支持大規(guī)模的用戶并發(fā)操作．此結構雖然有實施簡單、安全性容易保證等優(yōu)點，但其可擴展性、可伸縮性較差．為應付高峰時段大規(guī)模的用戶數，傳統的ROIA提供商必須儲備足夠的計算與存儲資源，然而不少資源在非高峰時段卻被白白閑置．為此，文中提出了一種ROIA云平臺，利用云計算可伸縮性好的優(yōu)點來提高底層硬件的利用率，降低ROIA提供商的運營費用．

ROIA云平臺結構如圖1所示，其中ROIA提供者可以是基礎設施提供者，也可以從其他云計算提供商租用相關資源．基礎設施提供者提供了底層硬件資源的監(jiān)控和管理工作．ROIA提供者除將ROIA應用部署到基礎設施上運行外，還要根據反饋的底層資源監(jiān)控情況，并結合ROIA運行的特點進行負載預測，從而進行優(yōu)化的資源調度．

圖1 ROIA云平臺結構Fig．1 Structure of ROIA cloud platform

在ROIA中，用戶通過客戶端操縱著虛擬角色在游戲世界中進行生產、競爭、探險及戰(zhàn)斗等活動．客戶端周期性地將虛擬角色的狀態(tài)、位置等信息發(fā)送給服務器，而服務器也會周期性地將其他虛擬角色、非玩家控制角色(NPC)等的狀態(tài)及位置信息發(fā)送給客戶端，客戶端利用這些信息對其游戲世界進行更新，使其與服務器的游戲世界保持一致．

在這些更新信息到達前，如果游戲世界保持靜止不動直到收到更新信息才繼續(xù)活動，將極大降低游戲的可玩性．引入預測技術可使得在沒收到更新信息之前，游戲世界中各角色能按照算法預測繼續(xù)運動而不讓用戶感到明顯的停頓．當預測和實際運動出現偏差時，需引入平滑處理技術，將虛擬角色平滑地拉回正確的位置而不出現明顯的跳動．

目前，大多數的游戲均使用DR算法進行預測和平滑處理．傳統的DR算法主要是基于如下物理運動學公式［14］進行預測:

式(1)表明，從t時刻到t+Δt時刻虛擬角色的位置保持不變;式(2)描述了虛擬角色從t時刻以勻速vt運動Δt時間后的位置;式(3)描述了從t時刻開始以vt為初始速度、at為加速度運動Δt時間后的位置．

從式(1)-(3)可以看到，傳統DR算法所預測的虛擬角色運動軌跡只與虛擬角色現在的位置及運動狀態(tài)有關，并沒有考慮其他因素的吸引和虛擬角色自身狀態(tài)對虛擬角色運動軌跡的影響．然而，在實際的ROIA中，用戶在很多情況下會因為其他因素的吸引而改變其運動方向．例如，剛剛出現在用戶興趣域的寶物、裝備、快速移動的敵人和NPC等，均會影響虛擬角色的運動軌跡，使其不是嚴格按照慣性進行運動．此外，虛擬角色自身的狀態(tài)也會對其運動方向產生很大的影響．例如，在同樣的游戲場景下，健康的虛擬角色(即生命值較高)很可能被寶物、裝備等物品所吸引，然而受傷的虛擬角色(特別是生命值很低的情況下)往往會不顧一切地向醫(yī)療品、急救包這類物品運動．

因此，文中的改進算法綜合考慮了其他因素的吸引和虛擬角色自身的狀態(tài)，以提高預測的準確度．

2 改進的DR算法

2．1 算法的基本思想

基于目標預測的改進DR算法的基本思想如下:首先計算出虛擬角色R1的興趣域內其他虛擬角色、非玩家控制角色以及物品對R1的吸引力，然后從中選取最大者設定為R1的目標，將其吸引力作為影響虛擬角色運動方向的外力加入到預測的數學模型中．

文中算法示意圖如圖2所示，其中有若干虛擬角色或物品，而t時刻只有R2、R3和 R7出現在R1的興趣域內，所以只需計算R2、R3和R7對R1的影響．但R7對R1的吸引力方向與R1現在的運動方向大于90°，表明該物品不在運動前方，而且也不是第一次出現在R1的興趣域內，即用戶很可能對該物品沒有興趣，因此，雖然R7在R1的興趣域內，但算法也不再考慮其對R1的吸引力．如圖2所示，R2對R1的吸引力大于R3對R1的吸引力，則將R2作為預測目標并將R2對R1的吸引力引入到運動模型中，以影響R1的運動方向及速度．然后通過插值計算等平滑處理技術將R1的運動平滑展現出來．

圖2 文中算法示意圖Fig．2 Schematic diagram of the proposed algorithm

2．2 吸引力的量化計算

要比較出吸引力的大小并以此預測運動目標，就必須先量化計算吸引力，而且這里所量化的吸引力是由角色運動方向前方的物品產生的，即吸引力方向和角色運動方向夾角在90°以內．文中將t時刻某個角色或物品R2對虛擬角色R1的吸引力記為At(R2，R1)，其計算式為

由式(4)可知:At(R2，R1)的一部分由函數B(R2，R1)計算得到，表示R2對R1產生的當前吸引力;另一部分則來自于近來一段時間內其他角色將R2選定為目標后遺留下的吸引力積累，文中稱之為t時刻R2的熱度，記為Ht(R2)．(0≤ ≤1)為調節(jié)新產生吸引力和積累吸引力對結果影響度的參數;D(R2，R1)為R2和R1之間的最短可達路徑長度，吸引力隨著可達路徑長度(該長度不一定是直線距離，而是游戲中R2到R1的最短可達路徑長度，因為有可能R2雖然在R1的興趣域內，但因為有障礙物而使它們不可達或之間的實際路徑很長)的增加而衰減;α為調節(jié)距離對吸引力衰減影響的參數．

B(R2，R1)根據R1的生命值與生命閾值Lth(由閾值參數δ乘以最大生命值得到，0≤δ≤1)的比較結果來量化吸引力:①R1的生命值大于Lth，表示虛擬角色健康，可按照等級越高或價值越大的物品吸引力越大、敵人等級越低吸引力越大等興趣預測規(guī)則產生一個吸引力值．②R1的生命值小于Lth，若R2是醫(yī)療類物品，則產生一個絕對大的固定值，該值遠大于過程①產生的吸引力值，但不是無窮大，當同時有多個醫(yī)療物品時，就由距離來決定其吸引力的大小;若R2不是醫(yī)療類物品，則按過程①產生吸引力值．

熱度Ht(R2)反映R2的受歡迎程度，并用它來影響R2的吸引力值．文中借鑒蟻群算法中信息素增減的思想來規(guī)范Ht(R2)的產生和減?。瓾t(R2)作為角色或物品的屬性值(0≤Ht(R2)≤100)，其初始值為0，每次將R2選定為目標后R2的熱度增加k(0≤k≤100)個單位值．另外，熱度隨時間的延長而衰減，即式中，ε為調節(jié)熱度衰減快慢的參數，0≤ε≤1．

2．3 預測數學模型

吸引力量化后就可以通過比較選擇出最大者作為目標．假設t時刻R2對R1的吸引力最大，則將其吸引力值At(R2，R1)引入式(3)并適當優(yōu)化，可得到如下預測公式:

式中，ω為調節(jié)吸引力值和加速度的參數，0≤ω≤1．vt和at可按如下公式進行優(yōu)化:

文獻［15］已經證明此優(yōu)化(見式(7))可以有效地提高預測曲線的平滑度．

3 仿真實驗及結果分析

文中采用Python 2．5實現了基于目標預測的改進DR算法和傳統的DR算法，并設計實現了一個模擬實驗環(huán)境，如圖3所示．用不同圖標點模擬了MMOG中其他玩家角色、醫(yī)療點、修理點或寶物等對象，每個圖標下方的數據分別標明了該點所在的坐標(單位為像素)和當前熱度值，只有興趣域中的點才進行吸引力計算．另外，為了降低實現難度，文中沒有引入障礙物的情形，但D(R2，R1)已經考慮到了有障礙物的情形，在實際應用中只需將尋徑算法得出的最短可達路徑長度代入計算模型即可，因此該仿真實驗的結果仍不失其普適性．

圖3 模擬實驗程序界面Fig．3 Interface of simulation program

實驗中發(fā)現，基于目標預測的改進DR算法的預測準確度高于傳統的DR算法．圖4是兩種算法的預測路線與實際路線的偏離值，可以知道，文中算法的預測偏離值在大部分時間(73%的實驗時間)內比傳統的DR算法小，即文中算法的預測準確度在73%的實驗時間內均優(yōu)于傳統DR算法．

圖4 兩種算法的預測偏離值比較Fig．4 Comparison of predicted deviations between two algorithms

圖5給出了傳統DR算法與基于目標預測的改進DR算法的預測偏離值的差值．從圖中可知:在大部分時間內2種算法的預測偏離值的差值大于0，即文中算法的預測偏離值較小，說明其預測結果更為準確;從差值的幅度看，文中算法總體上優(yōu)于傳統的DR算法．

圖5 兩種算法的預測偏離值的差值Fig．5 Predicted deviation difference of two algorithms

4 結語

傳統DR算法大多是基于物理運動學公式(即運動慣性)進行預測的，沒有考慮到實際應用中虛擬角色狀態(tài)及目標對其預測運動軌跡的影響，因此其預測準確度較低．為此，文中提出了一種云平臺實時在線交互應用中基于目標預測的改進DR算法，該算法既考慮了運動慣性對預測軌跡的影響，又考慮了虛擬角色當前狀態(tài)及其目標對預測軌跡的影響．仿真實驗結果表明，文中提出的基于目標預測的改進DR算法的預測準確度優(yōu)于傳統的DR算法，它對構建云平臺下的實時在線交互應用系統研究有較好的參考價值．

［1］Glinka F，Raed A，Gorlatch S，et al．A service-oriented interface for highly interactive distributed application［C］∥Proceedings of the 15th International Euro-Par Conference．Berlin:Springer-Verlag，2010:266-277．

［2］Lin K C．Dead reckoning and distributed interactive simulation［C］∥Proceedings of the Third Annual Conference of the Chinese-American Scholars Association of Florida．Orlando:SPIE，1995:16-36．

［3］Cai W，Lee F B，Chen L．An auto-adaptive dead reckoning algorithm for distributed interactive simulation［C］∥Proceedings of the Thirteenth Workshop on Parallel and Distributed Simulation．Atlanta:IEEE，1999:82-89．

［4］何連躍，李思昆．多閾值推算定位技術研究［J］．計算機研究與發(fā)展，2000，37(8):990-993．He Lian-yue，Li Si-kun．Research on technique of dead reckoning with multi-threshold ［J］．Journal of Computer Research and Development，2000，37(8):990-993．

［5］McLoone S C，Walsh P J，Ward T E．An enhanced dead reckoning model for physics-aware multiplayer computer games［C］∥Proceedings of IEEE/ACM the 16th International Symposium on Distributed Simulation and Real Time Applications．Dublin:IEEE，2012:111-117．

［6］Zhou Suiping，Cai Wentong，Lee B S，et al．Time-space consistency in large-scale distributed virtual environment［J］．ACM Transactions on Modeling and Computer Simulation，2004，14(1):31-47．

［7］Roberts D，Aspin R，Marshall D，et al．Bounding inconsistency using a novel threshold metric for dead reckoning update packet peneration［J］．Simulation，2008，84(5):239-256．

［8］Aggarwal S，Banavar H，Mukherjee S，et al．Fairness in dead-reckoning based distributed multi-playergames［C］∥Proceedings of the 4th ACM SIGCOMM Workshop on Network and System Support for Games．New York:ACM，2005:1-10．

［9］Hanawa D，Yonekura T．A proposal of dead reckoning protocol in distributed virtual environment based on the Taylor expansion［C］∥Proceedings of the 2006 International Conference on Cyberworlds．Lausanne:IEEE，2006:107-114．

［10］Li Zengxiang，Cai Wentong，Tang Xueyan，et al．Dead reckoning-based update scheduling against message loss for improving consistency in DVEs［C］∥Proceedings of 2011 IEEE Workshop on Principles of Advanced and Distributed Simulation．Nice:IEEE，2011:1-9．

［11］McCoy A，Ward T．Multistep-ahead neural-network predictors for network traffic reduction in distributed interactive applications［J］．ACM Transactions on Modeling and Computer Simulation，2007，17(4):1-30．

［12］Yahyavi A，Huguenin K，Kemme B．AntReckoning:dead reckoning using interest modeling by pheromones［C］∥Proceedings of the 10th Annual Workshop on Network and Systems Support for Games．Ottawa:IEEE，2011:1-6．

［13］Anand B，Thirugnanam K，Le Thanh L，et al．ARIVU:poweraware middleware for multiplayer mobile games［C］∥Proceedings of the 10th Annual Workshop on Network and Systems Support for Games．Taipei:ACM，2010:1-6．

［14］梁白鷗，陳雷霆，蔡洪斌．Dead Reckoning技術在網絡游戲中的應用［J］．計算機應用研究，2007，24(9):231-233．Liang Bai-ou，Chen Lei-ting，Cai Hong-bin．Implementation of dead reckoning technique in network game ［J］．Application Research of Computers，2007，24(9):231-233．

［15］Brown R．Smoothing，forecasting and prediction of discrete time series［M］．New York:Dover Publications，2004:23-25．