云平臺(tái)ROIA中基于目標(biāo)預(yù)測的DR算法*

劉冬 趙躍龍 曾文英，3

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

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

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

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

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

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

1 ROIA云平臺(tái)

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

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

圖1 ROIA云平臺(tái)結(jié)構(gòu)Fig．1 Structure of ROIA cloud platform

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

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

目前，大多數(shù)的游戲均使用DR算法進(jìn)行預(yù)測和平滑處理．傳統(tǒng)的DR算法主要是基于如下物理運(yùn)動(dòng)學(xué)公式［14］進(jìn)行預(yù)測:

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

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

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

2 改進(jìn)的DR算法

2．1 算法的基本思想

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

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

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

2．2 吸引力的量化計(jì)算

要比較出吸引力的大小并以此預(yù)測運(yùn)動(dòng)目標(biāo)，就必須先量化計(jì)算吸引力，而且這里所量化的吸引力是由角色運(yùn)動(dòng)方向前方的物品產(chǎn)生的，即吸引力方向和角色運(yùn)動(dòng)方向夾角在90°以內(nèi)．文中將t時(shí)刻某個(gè)角色或物品R2對(duì)虛擬角色R1的吸引力記為At(R2，R1)，其計(jì)算式為

由式(4)可知:At(R2，R1)的一部分由函數(shù)B(R2，R1)計(jì)算得到，表示R2對(duì)R1產(chǎn)生的當(dāng)前吸引力;另一部分則來自于近來一段時(shí)間內(nèi)其他角色將R2選定為目標(biāo)后遺留下的吸引力積累，文中稱之為t時(shí)刻R2的熱度，記為Ht(R2)．(0≤ ≤1)為調(diào)節(jié)新產(chǎn)生吸引力和積累吸引力對(duì)結(jié)果影響度的參數(shù);D(R2，R1)為R2和R1之間的最短可達(dá)路徑長度，吸引力隨著可達(dá)路徑長度(該長度不一定是直線距離，而是游戲中R2到R1的最短可達(dá)路徑長度，因?yàn)橛锌赡躌2雖然在R1的興趣域內(nèi)，但因?yàn)橛姓系K物而使它們不可達(dá)或之間的實(shí)際路徑很長)的增加而衰減;α為調(diào)節(jié)距離對(duì)吸引力衰減影響的參數(shù)．

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

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

2．3 預(yù)測數(shù)學(xué)模型

吸引力量化后就可以通過比較選擇出最大者作為目標(biāo)．假設(shè)t時(shí)刻R2對(duì)R1的吸引力最大，則將其吸引力值A(chǔ)t(R2，R1)引入式(3)并適當(dāng)優(yōu)化，可得到如下預(yù)測公式:

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

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

3 仿真實(shí)驗(yàn)及結(jié)果分析

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

圖3 模擬實(shí)驗(yàn)程序界面Fig．3 Interface of simulation program

實(shí)驗(yàn)中發(fā)現(xiàn)，基于目標(biāo)預(yù)測的改進(jìn)DR算法的預(yù)測準(zhǔn)確度高于傳統(tǒng)的DR算法．圖4是兩種算法的預(yù)測路線與實(shí)際路線的偏離值，可以知道，文中算法的預(yù)測偏離值在大部分時(shí)間(73%的實(shí)驗(yàn)時(shí)間)內(nèi)比傳統(tǒng)的DR算法小，即文中算法的預(yù)測準(zhǔn)確度在73%的實(shí)驗(yàn)時(shí)間內(nèi)均優(yōu)于傳統(tǒng)DR算法．

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

圖5給出了傳統(tǒng)DR算法與基于目標(biāo)預(yù)測的改進(jìn)DR算法的預(yù)測偏離值的差值．從圖中可知:在大部分時(shí)間內(nèi)2種算法的預(yù)測偏離值的差值大于0，即文中算法的預(yù)測偏離值較小，說明其預(yù)測結(jié)果更為準(zhǔn)確;從差值的幅度看，文中算法總體上優(yōu)于傳統(tǒng)的DR算法．

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

4 結(jié)語

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

［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］何連躍，李思昆．多閾值推算定位技術(shù)研究［J］．計(jì)算機(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技術(shù)在網(wǎng)絡(luò)游戲中的應(yīng)用［J］．計(jì)算機(jī)應(yīng)用研究，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．