基于分布式虛擬環(huán)境的航位推測(cè)改進(jìn)算法

張文富，張明鋒，2，3*，林廣發(fā)，2，3，廖桂華

（1.福建師范大學(xué) 地理科學(xué)學(xué)院，福建 福州 350007；2.福建省陸地災(zāi)害監(jiān)測(cè)評(píng)估工程技術(shù)研究中心，福建 福州 350007；3.海西地理國情動(dòng)態(tài)監(jiān)測(cè)與應(yīng)急保障研究中心，福建 福州 350007）

基于分布式虛擬環(huán)境的航位推測(cè)改進(jìn)算法

張文富1，張明鋒1，2，3*，林廣發(fā)1，2，3，廖桂華1

（1.福建師范大學(xué) 地理科學(xué)學(xué)院，福建 福州 350007；2.福建省陸地災(zāi)害監(jiān)測(cè)評(píng)估工程技術(shù)研究中心，福建 福州 350007；3.海西地理國情動(dòng)態(tài)監(jiān)測(cè)與應(yīng)急保障研究中心，福建 福州 350007）

分布式交互應(yīng)用程序中使用航位推測(cè)算法實(shí)現(xiàn)實(shí)體狀態(tài)同步.文章利用臨近時(shí)間內(nèi)已經(jīng)接收到的多個(gè)航位推測(cè)載體，基于外推思想分別構(gòu)建了一次、二次、三次等多項(xiàng)式擬合得出速度變化曲線，然后根據(jù)當(dāng)前更新時(shí)間推測(cè)速度，這樣不但可以減少網(wǎng)絡(luò)帶寬，而且增加了預(yù)測(cè)結(jié)果的準(zhǔn)確性.算法在多個(gè)客戶端的網(wǎng)絡(luò)環(huán)境下進(jìn)行測(cè)試，從推測(cè)速度誤差與位置誤差方面將改進(jìn)后的算法與傳統(tǒng)模型算法進(jìn)行比較，結(jié)果表明改進(jìn)后的算法顯著地提高了模擬速度和位置的精度，在DIAs中具有一定的參考價(jià)值.

航位推測(cè)；位置同步；算法改進(jìn)；推測(cè)速度及位置

在分布式虛擬環(huán)境中多人交互協(xié)同日漸重要，如多人在線網(wǎng)絡(luò)游戲［1］、在線共同學(xué)習(xí)［2］、協(xié)同式軍事訓(xùn)練［3］等，分布式交互應(yīng)用程序（Distributed Interactive Applications，DIAs）可以讓地理位置不同的遠(yuǎn)程用戶通過一個(gè)共享的虛擬環(huán)境進(jìn)行交互［4-5］，在該虛擬環(huán)境下通過一個(gè)客戶端觀察到的某個(gè)物體運(yùn)動(dòng)狀態(tài)與通過其他客戶端觀察到的該物體運(yùn)動(dòng)狀態(tài)相同.為了實(shí)現(xiàn)這種運(yùn)動(dòng)狀態(tài)的同步，需要在DIAs開發(fā)過程中，使用同步算法.

現(xiàn)有的同步算法可以分為保守同步算法和樂觀同步算法［6］.航位推測(cè)（Dead Reckoning，DR）算法是一種典型的樂觀同步算法.該算法最早由美國國防部為了解決軍事模擬中存在的延遲問題而提出的，現(xiàn)實(shí)中該算法最早用于車輛、輪船的導(dǎo)航定位.隨著計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)的發(fā)展，DR算法在DIAs中人物位置同步方面得到了廣泛的應(yīng)用，為了減少網(wǎng)絡(luò)間數(shù)據(jù)傳輸，普遍使用DR算法外推實(shí)體位置［7］.由于網(wǎng)絡(luò)帶寬限制，客戶端只能以一定頻率或當(dāng)運(yùn)動(dòng)狀態(tài)超過一定閾值時(shí)才發(fā)送狀態(tài)變化信息，所以使用傳統(tǒng)上的DR算法每次狀態(tài)更新時(shí)都會(huì)發(fā)生跳躍或者抖動(dòng)現(xiàn)象.而且信息在網(wǎng)絡(luò)間傳輸過程中存在延遲問題，所以客戶端接收到的狀態(tài)更新信息實(shí)際上是存在延遲的.當(dāng)實(shí)體需要實(shí)時(shí)更新方向變化時(shí)，DR Vector還需要包含實(shí)體的方向變化信息.但是如果實(shí)體狀態(tài)信息數(shù)據(jù)量比較大，實(shí)體狀態(tài)信息在網(wǎng)絡(luò)間傳輸過程中就容易丟失，文獻(xiàn)［8］研究了網(wǎng)絡(luò)延時(shí)與丟包問題對(duì)游戲公平性與一致性的影響.

針對(duì)以上問題國內(nèi)外眾多學(xué)者進(jìn)行了探索及分析.為了使預(yù)測(cè)結(jié)果更加準(zhǔn)確，目前對(duì)算法的主要改進(jìn)方法有根據(jù)實(shí)體運(yùn)動(dòng)慣性進(jìn)行改進(jìn)；根據(jù)外界環(huán)境對(duì)實(shí)體的影響進(jìn)行改進(jìn)［9-11］；通過更改DR閾值［12］或者根據(jù)當(dāng)前帶寬、游戲一致性及公平性控制更新頻率［13］.還有一些學(xué)者把DR算法分為兩部分：位置推測(cè)和平滑處理［14-15］.首先根據(jù)收到的狀態(tài)信息進(jìn)行預(yù)測(cè)下一位置信息，然后在下一時(shí)刻到來之前將物體平滑到預(yù)測(cè)位置.文獻(xiàn)［15］對(duì)預(yù)測(cè)模型和平滑處理方法進(jìn)行了對(duì)比分析，但是其時(shí)間步長(zhǎng)均為1s，而且驗(yàn)證環(huán)境過于理想，并沒有在復(fù)雜多變的網(wǎng)絡(luò)環(huán)境下進(jìn)行實(shí)現(xiàn).文獻(xiàn)［16］列舉了各種推測(cè)模型，并在點(diǎn)對(duì)點(diǎn)模式下對(duì)網(wǎng)絡(luò)延遲進(jìn)行了研究.為了減少網(wǎng)絡(luò)帶寬，解決數(shù)據(jù)包丟失問題，主要改進(jìn)途徑包括提高算法性能、動(dòng)態(tài)更改閾值等，如文獻(xiàn)［17］用多閾值DR技術(shù)，根據(jù)實(shí)體間距離來建立不同閾值，以此減少網(wǎng)絡(luò)間信息傳輸頻率.此外也有一些學(xué)者對(duì)航位推測(cè)誤差進(jìn)行了相關(guān)研究，如文獻(xiàn)［12］中對(duì)航位推測(cè)過程進(jìn)行了詳細(xì)的解析，并對(duì)不同階段進(jìn)行了劃分，將DR Vector到來前的誤差稱為前出差（Before Export Errot），DR Vector到來后的誤差稱為后出差（After Export Error）；還提出全局時(shí)間鐘概念，減小了后出差，提高了算法預(yù)測(cè)精度，但是并沒有減少前出差.文獻(xiàn)［18］在文獻(xiàn)［12］的基礎(chǔ)上從游戲公平的角度進(jìn)行算法改進(jìn)，其計(jì)算過程過于復(fù)雜，對(duì)系統(tǒng)硬件要求高，并不適合一般的DIAs.文獻(xiàn)［19］對(duì)傳統(tǒng)DR算法進(jìn)行改進(jìn)，提出Pre-Reckoning算法，根據(jù)實(shí)體運(yùn)動(dòng)的特定狀態(tài)進(jìn)行實(shí)體未來狀態(tài)推測(cè).

本研究通過分析已經(jīng)收到的多個(gè)狀態(tài)信息并擬合實(shí)體速度變化曲線多項(xiàng)式，預(yù)測(cè)實(shí)體未來速度變化情況，實(shí)現(xiàn)無需傳遞實(shí)體加速度變化信息即可預(yù)測(cè)未來實(shí)體變化，大大減少了網(wǎng)絡(luò)帶寬.驗(yàn)證結(jié)果顯示這種算法比單一的利用上次狀態(tài)信息得到的結(jié)果更加精確，大大減少了前出差.在現(xiàn)實(shí)模擬中具有重要的應(yīng)用價(jià)值.

1 傳統(tǒng)Dead Reckoning模型

航位推測(cè)算法是一種基于實(shí)體運(yùn)動(dòng)狀態(tài)（方向、位置、速度）的短時(shí)臨近插值算法，用于推測(cè)傳實(shí)體未來狀態(tài).傳統(tǒng)的航位推測(cè)算法主要有以下3種（見式1-3）［15］.

其中，P表示實(shí)體在t時(shí)刻推測(cè)位置，P0表示實(shí)體當(dāng)前位置，V0表示實(shí)體當(dāng)前速度，t0表示當(dāng)前時(shí)刻.

模型（1）表示物體在同步位置過程中僅傳遞實(shí)體的位置信息，接收端收到實(shí)體的位置信息后將實(shí)體放在該位置點(diǎn)，其對(duì)應(yīng)的航位推測(cè)載體為DR（Px0，Py0，Pz0），在DIAs中可以看到該實(shí)體運(yùn)動(dòng)軌跡并不連續(xù)，該模型不能很好地表達(dá)實(shí)體運(yùn)動(dòng)軌跡.模型（2）表示在同步過程中，還需傳遞實(shí)體速度信息，對(duì)應(yīng)航位推測(cè)載體為DR（Px0，Py0，Pz0，Vx0，Vy0，Vz0），當(dāng)一個(gè)接收端收到該航位推測(cè)載體后會(huì)將實(shí)體放在指定位置上，并在下一個(gè)DR Vector到來前依據(jù)原有速度進(jìn)行運(yùn)動(dòng).模型（3）考慮了物體運(yùn)動(dòng)的速度變化情況，對(duì)應(yīng)的DR Vector為（Px0，Py0，Pz0，Vx0，Vy0，Vz0，ax0，ay0，az0），該DR Vector不僅包含物體運(yùn)動(dòng)的速度信息還包含了實(shí)體運(yùn)動(dòng)的加速度信息，因此在網(wǎng)絡(luò)間傳輸?shù)男畔⒘勘容^大，所花費(fèi)的時(shí)間也比較長(zhǎng)，當(dāng)考慮實(shí)體方向變化時(shí)還要加上方向變化信息，這樣會(huì)占用更多的網(wǎng)絡(luò)帶寬.無論使用哪種航位推測(cè)模型，都具有相同的推測(cè)流程（見圖1）.

圖1 Dead Reckoning軌跡分析Fig.1Dead Reckoning trajectory analysis

在圖1中水平方向表示時(shí)間變化過程，垂直方向表示實(shí)體位置變化過程.曲線ACD為發(fā)送端實(shí)體運(yùn)動(dòng)真實(shí)軌跡，A′B′BC′D′為接收端實(shí)體運(yùn)動(dòng)軌跡.假設(shè)T0時(shí)刻更新一個(gè)航位推測(cè)載體DR0，經(jīng)過網(wǎng)絡(luò)延遲dt0，接收端收到DR0，此時(shí)接收端實(shí)體位于B′.由于時(shí)間已經(jīng)同步，所以根據(jù)接收時(shí)間與發(fā)送時(shí)間可以計(jì)算網(wǎng)絡(luò)延時(shí)dt0，并根據(jù)該延時(shí)預(yù)測(cè)當(dāng)前發(fā)送端實(shí)體位置B，然后接收端實(shí)體從B′移動(dòng)到B，并按照DR0包含的速度信息進(jìn)行運(yùn)動(dòng).當(dāng)發(fā)送端在T1時(shí)刻再次發(fā)送一個(gè)航位推測(cè)載體DR1，經(jīng)過網(wǎng)絡(luò)延遲dt1，接收端收到該信息，此時(shí)接收端實(shí)體位于D′，然后接收端重復(fù)上述過程更新實(shí)體運(yùn)動(dòng)狀態(tài).

其他一些模型多是根據(jù)上述模型進(jìn)行的改進(jìn)，如根據(jù)網(wǎng)絡(luò)延遲時(shí)間預(yù)測(cè)下一時(shí)刻到來時(shí)實(shí)體所處位置，然后采用不同的平滑曲線將實(shí)體平滑到該預(yù)測(cè)位置，這種方式模擬出的實(shí)體軌跡十分平滑，增加了實(shí)體曲線外觀，但是擬合出的曲線并不一定是真實(shí)的實(shí)體路徑軌跡.而且實(shí)體接收到DR Vector前都是根據(jù)上次接收到的信息，這樣當(dāng)發(fā)送端實(shí)體運(yùn)動(dòng)狀態(tài)變化后，接收端并不會(huì)實(shí)時(shí)變化狀態(tài).因此接收端實(shí)體只有在接收到航位推測(cè)載體時(shí)才和遠(yuǎn)程發(fā)送端一致，其他時(shí)刻的運(yùn)動(dòng)狀態(tài)都是不一致的.

2 改進(jìn)的Dead Reckoning模型

實(shí)體前后運(yùn)動(dòng)狀態(tài)往往具有相關(guān)性，本文以一個(gè)賽車游戲進(jìn)行測(cè)試，模擬實(shí)體運(yùn)動(dòng)情況，并且每隔0.2s進(jìn)行一次實(shí)體速度測(cè)量，得出當(dāng)前速度與之前實(shí)體速度關(guān)系見表1.

表1 速度相關(guān)性表Tab.1 Correlation of velocity

由表1中當(dāng)前速度V0與其他時(shí)刻速度的Pearson指數(shù)可以看出與當(dāng)前實(shí)體速度相近的時(shí)間里實(shí)體狀態(tài)間具有很高的相關(guān)性，其相關(guān)性隨間隔時(shí)間的增加而減小.而傳統(tǒng)航位推測(cè)算法忽略了可用前后運(yùn)動(dòng)狀態(tài)信息［20］，因此本文根據(jù)每次發(fā)送的航位推測(cè)載體具有相關(guān)性進(jìn)行探索研究，利用以往接收到的多個(gè)航位推測(cè)載體進(jìn)行當(dāng)前實(shí)體運(yùn)動(dòng)狀態(tài)預(yù)測(cè)，實(shí)體在運(yùn)動(dòng)過程中可以隨時(shí)根據(jù)以往運(yùn)動(dòng)狀態(tài)分析其當(dāng)前運(yùn)動(dòng)規(guī)律，結(jié)合以往多個(gè)航位推測(cè)載體進(jìn)行推測(cè)，比單一的使用上次航位載體預(yù)測(cè)結(jié)果更加準(zhǔn)確，而且使用多個(gè)航位推測(cè)載體，可以預(yù)測(cè)實(shí)體速度加速度變化，因此在網(wǎng)絡(luò)傳輸過程中可以減少航位推測(cè)載體所承載的信息量，從而減少網(wǎng)絡(luò)帶寬.

實(shí)體當(dāng)前運(yùn)動(dòng)狀態(tài)與臨近的運(yùn)動(dòng)狀態(tài)具有很高的相關(guān)性，且這種相關(guān)性隨著時(shí)間間隔的增加逐漸減小.由于航位推測(cè)算法所預(yù)測(cè)的實(shí)體速度信息要求很高的實(shí)時(shí)性與精確性，所以本研究選取其前1s內(nèi)的航位推測(cè)載體來推測(cè)當(dāng)前速度信息.本研究以模型（2）為例進(jìn)行研究，根據(jù)實(shí)體運(yùn)動(dòng)前1s內(nèi)速度變化情況進(jìn)行多項(xiàng)式擬合，得出其速度變化曲線，這樣就可以在網(wǎng)絡(luò)間只傳遞其位置和速度信息.本文根據(jù)這種思想進(jìn)行算法設(shè)計(jì)，采用不同次數(shù)多項(xiàng)式進(jìn)行擬合分析（見式（4）～（7）），并與傳統(tǒng)算法推測(cè)的結(jié)果進(jìn)行比對(duì).

在公式（4）、（5）中，V表示預(yù)測(cè)速度，V0表示前一時(shí)刻速度，t表示當(dāng)前時(shí)刻，a，b，c分別表示各個(gè)模型系數(shù).模型（4）是傳統(tǒng)上航位推測(cè)技術(shù)使用的方法，在接收到下一個(gè)DR Vector前速度不會(huì)發(fā)生改變.模型（5）、（6）、（7）分別表示根據(jù)以前的DR Vector進(jìn)行擬合的1次、2次、3次速度變化曲線.將當(dāng)前的時(shí)間代入擬合出的曲線函數(shù)，計(jì)算出當(dāng)前實(shí)體速度.當(dāng)實(shí)體接收到新的DR Vector則重新擬合速度變化曲線.

當(dāng)接收端實(shí)體運(yùn)動(dòng)到B′時(shí)接收到發(fā)送端在T0時(shí)刻發(fā)送的DR0，此時(shí)接收端開始使用改進(jìn)的航位推測(cè)模型進(jìn)行預(yù)測(cè)當(dāng)前發(fā)送端實(shí)體位置B（見式（8）），并將接收端實(shí)體移動(dòng)到B，然后根據(jù)時(shí)間變化預(yù)測(cè)當(dāng)前實(shí)體速度，直到下次航位推測(cè)載體到來.

根據(jù)以上各種模型，本文分別進(jìn)行了相應(yīng)的研究并編寫算法進(jìn)行試驗(yàn)（見圖2、圖3）.

圖2 算法流程圖Fig.2 Algorithm flow chart

圖3 模擬界面Fig.3 UI of the simulation

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

根據(jù)以上模型進(jìn)行算法編程，并進(jìn)行誤差分析.在該研究中我們主要對(duì)傳統(tǒng)模型與改進(jìn)模型擬合結(jié)果進(jìn)行速度與位置比較.在相同的硬件環(huán)境下，每0.2s發(fā)送一個(gè)DR Vector，分別得出各模型擬合速度與真實(shí)速度曲線變化，由此來比較算法模擬結(jié)果.

公式（9）表示速度誤差計(jì)算公式.其中V表示真實(shí)速度，V′表示預(yù)測(cè)速度，Vx，Vy，Vz，Vx′，Vy′，Vz′分別表示實(shí)體在坐標(biāo)系中x，y，z方向上的真實(shí)速度與預(yù)測(cè)速度.公式（10）表示位置誤差計(jì)算公式，其中P表示真實(shí)位置，P′表示預(yù)測(cè)位置，Px，Py，Pz，Px′，Py′，Pz′分別表示實(shí)體在坐標(biāo)系中x軸，y軸，z軸方向上的實(shí)際位置與預(yù)測(cè)位置.

圖4～圖6中橫坐標(biāo)均表示時(shí)間變化，縱坐標(biāo)分別表示速度變化、速度誤差大小、位置誤差大小.從中可以看出傳統(tǒng)模型下每個(gè)更新間隔內(nèi)擬合速度保持不變，且其誤差均接近某一恒定值，并不能真實(shí)地反映實(shí)體真實(shí)運(yùn)動(dòng)情況.而改進(jìn)后的模型基本符合實(shí)體速度真實(shí)變化情況，因?yàn)槟M過程中是先加速后減速連續(xù)的運(yùn)動(dòng)，其速度誤差與位置誤差均具有一定的周期性.各模型下的誤差進(jìn)行取絕對(duì)值后平均得平均值（見表2）.

圖4 各模型下真實(shí)速度與擬合速度對(duì)比圖Fig.4The comparison diagram of real velocity and calculated velocity

圖5 各模型下擬合速度誤差圖Fig.5 The error diagram of calculated velocity in different model

圖6 各模型下擬合位置誤差圖Fig.6 The error diagram of calculated position in different model

表2 各模型下平均速度誤差與平均位置誤差對(duì)比表Tab.2 The mean error of velocity and position in different model

由各模型下擬合速度與真實(shí)速度變化曲線可以看出，因?yàn)閭鹘y(tǒng)模型僅根據(jù)上一次收到的DR vector進(jìn)行速度更新，在兩個(gè)時(shí)間間隔內(nèi)沒有考慮速度變化，其速度變化曲線成鋸齒狀，且其速度更新總是落后于真實(shí)速度.當(dāng)下一次DR vector到來時(shí)產(chǎn)生的平均速度誤差為2.12 m/s，平均位置誤差為0.40 m.由模型（1）擬合速度與真實(shí)速度結(jié)果圖可以看出在每次加速或者減速過程中，模型（1）擬合的速度可以很好地反映實(shí)體真實(shí)速度，但是在每次由加速變?yōu)闇p速或者由減速變?yōu)榧铀贂r(shí)，該模型不能很好地反映實(shí)體真實(shí)速度變化，其平均速度誤差和平均位置誤差都遠(yuǎn)小于傳統(tǒng)模型.由于每次模擬速度變化都接近于勻變速運(yùn)動(dòng)，所以在模型（2）和模型（3）的擬合結(jié)果中并沒有很好地發(fā)揮其優(yōu)勢(shì)，但是其總體擬合結(jié)果優(yōu)于傳統(tǒng)模型.

4 結(jié)論

通過以上實(shí)驗(yàn)證明，基于多航位推測(cè)載體改進(jìn)后的算法可以在DR vector不包含速度變化信息的情況下進(jìn)行擬合出速度變化情況，減少了網(wǎng)絡(luò)帶寬.考慮每個(gè)間隔時(shí)間內(nèi)實(shí)體速度變化后，大大減少了前出差.但是改進(jìn)后的模型在應(yīng)用的過程中還需要根據(jù)實(shí)體速度變化情況進(jìn)行使用，當(dāng)實(shí)體做簡(jiǎn)單的運(yùn)動(dòng)時(shí)，并不需要在接收端使用較高次的速度擬合.本文在此僅給出了這種算法的可行性，并在山洪應(yīng)急虛擬演練平臺(tái)中進(jìn)行了應(yīng)用.但是本研究也有一定的缺陷：1）DIAs中航位推測(cè)過程中考慮的因素繁多，這里僅基于實(shí)體運(yùn)動(dòng)慣性進(jìn)行了研究，并沒有考慮外界虛擬環(huán)境對(duì)人物或物體的影響.2）減少網(wǎng)絡(luò)帶寬的方式很多，這里也沒有在興趣管理、建立動(dòng)態(tài)用戶列表等［6］方面進(jìn)行研究.

［1］Hampel T，Bopp T，Hinn R.A peer-to-peer architecture for massive multiplayer online games［C］//General Chair-Cheok A D，General Chair-Ishibashi Y，Proceedings of 5th ACM SIGCOMM workshop on Network and system support for games，ACM Workshop on Network&System Support for Games，2006：48.

［2］Nitta T，F(xiàn)ujita K，Kohno S.An application of distributed virtual environment to foreign language education［C］//Pourriat J L，Lapandry C，Veyrac P，et al.Proceedings of the 30th Annual Frontiers in Education-Volume 01，F(xiàn)rontiers in Education.IEEE Computer Society，2000：F1G/9-F1G15.

［3］Miller D C，Thorpe J A.SIMNET：The advent of simulator networking［J］.Proceedings of the IEEE，1995，83（8）：1114-1123.

［4］Macedonia M R，Zyda M J.A taxonomy for networked virtual environments［J］.IEEE multimedia，1997，4（1）：48-56.

［5］Churchill E F，Snowdon D N，Munro A J.Collaborative virtual environments：digital places and spaces for interaction［J］.Educational Technology&Society，2002，5（4）：177-178.

［6］何高奇，潘志庚，李永青，等.虛擬健身網(wǎng)絡(luò)游戲集成同步技術(shù)［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2008，20（2）：207-212.

［7］Li，Z，Cai，W，Tang，X，et al.Loss-aware DR-based update scheduling for improving consistency in DVEs［J］.Journal of Simulation，2012，6（3）：164-178.

［8］Yasui T，Ishibashi Y.The Influence of Network Delays on Consistency and Fairness among Players in Networked Games［J］.Ieice Technical Report，2004，104：21-24.

［9］劉冬，趙躍龍，曾文英.云平臺(tái)ROIA中基于目標(biāo)預(yù)測(cè)的DR算法［J］.華南理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2013（9）：82-86.

［10］Yahyavi A，Huguenin K，Kemme B.Interest modeling in games：the case of dead reckoning［J］.Multimedia Systems，2013，19（3）：255-270.

［11］Walsh P J.Development of a Physics-Aware Dead Reckoning Mechanism for Distributed Interactive Applications［D］.National University of Ireland Maynooth，2011. Aggarwal S，Banavar H，Khandelwal A，et al.Accuracy In

［12］Dead-Reckoning Based Distributed Multi-Player Games［C］//Feng W C，Proceedings of 3rd ACM SIGCOMMworkshop on Network and system support for games，ACM Workshop on Network&System Support for Games 2004：161-165.

［13］Tang X，Zhou S.Update scheduling for improving consistency in distributed virtual environments［J］.Parallel and Distributed Systems，IEEE Transactions on，2010，21（6）：765-777.

［14］Li Y，Cai W.Consistency-Aware Zone Mapping and Client Assignment in Multi-Server Distributed Virtual Environments［J］.IEEE Transactions on Parallel&Distributed Systems，2014，26（6）：1-1.

［15］梁白鷗，陳雷霆，蔡洪斌.Dead Reckoning技術(shù)在網(wǎng)絡(luò)游戲中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用研究，2007，24（9）：231-233.

［16］劉璐.基于P2P的網(wǎng)絡(luò)游戲架構(gòu)和同步算法［D］.西安：西安電子科技大學(xué)，2007.

［17］何連躍，李思昆.多閾值推算定位技術(shù)研究［J］.計(jì)算機(jī)研究與發(fā)展，2000，37（8）：990-993.

［18］Aggarwal S，Banavar H，Mukherjee S，et al.Fairness in dead-reckoning based distributed multi-player games［C］// De Cataldo M A A，Proceedings of 4rd ACM SIGCOMM workshop on Network and system support for games，ACM The Workshop on Network&System Support for Games，2005：1-10.

［19］Duncan T P，Gracanin D.Algorithms and analyses：prereckoning algorithm for distributed virtual environments［C］//Chick S，Sanchez P J，F(xiàn)errin D，et al.Conference on Winter Simulation：Driving Innovation.Winter Simulation Conference，2003（2）：1086-1093.

［20］Hakiri A，Berthou P，Gayraud T.Survey study of the QoS Management in Distributed Interactive Simulation Through Dead Reckoning Algorithms［J］.arXiv preprint arXiv：2010，1008：3758.

責(zé)任編輯：黃 瀾

One Research of Modified Dead Reckoning Algorithm Based on Distributed Virtual Environments

ZHANG Wenfu1，ZHANG Mingfeng1，2，3*，LIN Guangfa1，2，3，LIAO Guihua1

（1.School of Geography，F(xiàn)ujian Normal University，F(xiàn)uzhou 350007，China；2.Fujian Provincial Engineering Research Center for Monitoring and Assessing Terrestrial Disasters，F(xiàn)uzhou 350007，China；3.Research Center for National Geographical Condition Monitoring and Emergency Support in the Economic Zone on the West Side of the Taiwan Strait，F(xiàn)uzhou 350007，China）

We use dead reckoning algorithm to implement state synchronization in distributed interactive applications.In this article we built linear，quadratic，cubic polynomial to predict the future state of the entry with more than one vector received in the past proximate time，and got current speed by extrapolation method and current time.It not only reduced the network bandwidth，but also increased the accuracy of the predicted result.At last we compared the speed error and the position error of the traditional algorithm and the modified algorithm in the simulation of multi-clients，and the result showed the modified algorithm improved accuracy of the velocity and the position，which is suitable for the DIAs.

dead reckoning；position synchronization；modify algorithm；predict velocity and position

TP 391.9

A

1674-4942（2016）02-0202-06

2016-01-30

福建省科技廳公益類科研院所重點(diǎn)項(xiàng)目；福建省科技廳產(chǎn)學(xué)研重大項(xiàng)目（2012Y4001）*通訊作者