基于分布式虚拟环境的航位推测改进算法

张文富，张明锋，2，3*，林广发，2，3，廖桂华

（1.福建师范大学 地理科学学院，福建 福州 350007；2.福建省陆地灾害监测评估工程技术研究中心，福建 福州 350007；3.海西地理国情动态监测与应急保障研究中心，福建 福州 350007）

基于分布式虚拟环境的航位推测改进算法

张文富1，张明锋1，2，3*，林广发1，2，3，廖桂华1

（1.福建师范大学 地理科学学院，福建 福州 350007；2.福建省陆地灾害监测评估工程技术研究中心，福建 福州 350007；3.海西地理国情动态监测与应急保障研究中心，福建 福州 350007）

分布式交互应用程序中使用航位推测算法实现实体状态同步.文章利用临近时间内已经接收到的多个航位推测载体，基于外推思想分别构建了一次、二次、三次等多项式拟合得出速度变化曲线，然后根据当前更新时间推测速度，这样不但可以减少网络带宽，而且增加了预测结果的准确性.算法在多个客户端的网络环境下进行测试，从推测速度误差与位置误差方面将改进后的算法与传统模型算法进行比较，结果表明改进后的算法显著地提高了模拟速度和位置的精度，在DIAs中具有一定的参考价值.

航位推测；位置同步；算法改进；推测速度及位置

在分布式虚拟环境中多人交互协同日渐重要，如多人在线网络游戏［1］、在线共同学习［2］、协同式军事训练［3］等，分布式交互应用程序（Distributed Interactive Applications，DIAs）可以让地理位置不同的远程用户通过一个共享的虚拟环境进行交互［4-5］，在该虚拟环境下通过一个客户端观察到的某个物体运动状态与通过其他客户端观察到的该物体运动状态相同.为了实现这种运动状态的同步，需要在DIAs开发过程中，使用同步算法.

现有的同步算法可以分为保守同步算法和乐观同步算法［6］.航位推测（Dead Reckoning，DR）算法是一种典型的乐观同步算法.该算法最早由美国国防部为了解决军事模拟中存在的延迟问题而提出的，现实中该算法最早用于车辆、轮船的导航定位.随着计算机网络技术的发展，DR算法在DIAs中人物位置同步方面得到了广泛的应用，为了减少网络间数据传输，普遍使用DR算法外推实体位置［7］.由于网络带宽限制，客户端只能以一定频率或当运动状态超过一定阈值时才发送状态变化信息，所以使用传统上的DR算法每次状态更新时都会发生跳跃或者抖动现象.而且信息在网络间传输过程中存在延迟问题，所以客户端接收到的状态更新信息实际上是存在延迟的.当实体需要实时更新方向变化时，DR Vector还需要包含实体的方向变化信息.但是如果实体状态信息数据量比较大，实体状态信息在网络间传输过程中就容易丢失，文献［8］研究了网络延时与丢包问题对游戏公平性与一致性的影响.

针对以上问题国内外众多学者进行了探索及分析.为了使预测结果更加准确，目前对算法的主要改进方法有根据实体运动惯性进行改进；根据外界环境对实体的影响进行改进［9-11］；通过更改DR阈值［12］或者根据当前带宽、游戏一致性及公平性控制更新频率［13］.还有一些学者把DR算法分为两部分：位置推测和平滑处理［14-15］.首先根据收到的状态信息进行预测下一位置信息，然后在下一时刻到来之前将物体平滑到预测位置.文献［15］对预测模型和平滑处理方法进行了对比分析，但是其时间步长均为1s，而且验证环境过于理想，并没有在复杂多变的网络环境下进行实现.文献［16］列举了各种推测模型，并在点对点模式下对网络延迟进行了研究.为了减少网络带宽，解决数据包丢失问题，主要改进途径包括提高算法性能、动态更改阈值等，如文献［17］用多阈值DR技术，根据实体间距离来建立不同阈值，以此减少网络间信息传输频率.此外也有一些学者对航位推测误差进行了相关研究，如文献［12］中对航位推测过程进行了详细的解析，并对不同阶段进行了划分，将DR Vector到来前的误差称为前出差（Before Export Errot），DR Vector到来后的误差称为后出差（After Export Error）；还提出全局时间钟概念，减小了后出差，提高了算法预测精度，但是并没有减少前出差.文献［18］在文献［12］的基础上从游戏公平的角度进行算法改进，其计算过程过于复杂，对系统硬件要求高，并不适合一般的DIAs.文献［19］对传统DR算法进行改进，提出Pre-Reckoning算法，根据实体运动的特定状态进行实体未来状态推测.

本研究通过分析已经收到的多个状态信息并拟合实体速度变化曲线多项式，预测实体未来速度变化情况，实现无需传递实体加速度变化信息即可预测未来实体变化，大大减少了网络带宽.验证结果显示这种算法比单一的利用上次状态信息得到的结果更加精确，大大减少了前出差.在现实模拟中具有重要的应用价值.

1 传统Dead Reckoning模型

航位推测算法是一种基于实体运动状态（方向、位置、速度）的短时临近插值算法，用于推测传实体未来状态.传统的航位推测算法主要有以下3种（见式1-3）［15］.

其中，P表示实体在t时刻推测位置，P0表示实体当前位置，V0表示实体当前速度，t0表示当前时刻.

模型（1）表示物体在同步位置过程中仅传递实体的位置信息，接收端收到实体的位置信息后将实体放在该位置点，其对应的航位推测载体为DR（Px0，Py0，Pz0），在DIAs中可以看到该实体运动轨迹并不连续，该模型不能很好地表达实体运动轨迹.模型（2）表示在同步过程中，还需传递实体速度信息，对应航位推测载体为DR（Px0，Py0，Pz0，Vx0，Vy0，Vz0），当一个接收端收到该航位推测载体后会将实体放在指定位置上，并在下一个DR Vector到来前依据原有速度进行运动.模型（3）考虑了物体运动的速度变化情况，对应的DR Vector为（Px0，Py0，Pz0，Vx0，Vy0，Vz0，ax0，ay0，az0），该DR Vector不仅包含物体运动的速度信息还包含了实体运动的加速度信息，因此在网络间传输的信息量比较大，所花费的时间也比较长，当考虑实体方向变化时还要加上方向变化信息，这样会占用更多的网络带宽.无论使用哪种航位推测模型，都具有相同的推测流程（见图1）.

图1 Dead Reckoning轨迹分析Fig.1Dead Reckoning trajectory analysis

在图1中水平方向表示时间变化过程，垂直方向表示实体位置变化过程.曲线ACD为发送端实体运动真实轨迹，A′B′BC′D′为接收端实体运动轨迹.假设T0时刻更新一个航位推测载体DR0，经过网络延迟dt0，接收端收到DR0，此时接收端实体位于B′.由于时间已经同步，所以根据接收时间与发送时间可以计算网络延时dt0，并根据该延时预测当前发送端实体位置B，然后接收端实体从B′移动到B，并按照DR0包含的速度信息进行运动.当发送端在T1时刻再次发送一个航位推测载体DR1，经过网络延迟dt1，接收端收到该信息，此时接收端实体位于D′，然后接收端重复上述过程更新实体运动状态.

其他一些模型多是根据上述模型进行的改进，如根据网络延迟时间预测下一时刻到来时实体所处位置，然后采用不同的平滑曲线将实体平滑到该预测位置，这种方式模拟出的实体轨迹十分平滑，增加了实体曲线外观，但是拟合出的曲线并不一定是真实的实体路径轨迹.而且实体接收到DR Vector前都是根据上次接收到的信息，这样当发送端实体运动状态变化后，接收端并不会实时变化状态.因此接收端实体只有在接收到航位推测载体时才和远程发送端一致，其他时刻的运动状态都是不一致的.

2 改进的Dead Reckoning模型

实体前后运动状态往往具有相关性，本文以一个赛车游戏进行测试，模拟实体运动情况，并且每隔0.2s进行一次实体速度测量，得出当前速度与之前实体速度关系见表1.

表1 速度相关性表Tab.1 Correlation of velocity

由表1中当前速度V0与其他时刻速度的Pearson指数可以看出与当前实体速度相近的时间里实体状态间具有很高的相关性，其相关性随间隔时间的增加而减小.而传统航位推测算法忽略了可用前后运动状态信息［20］，因此本文根据每次发送的航位推测载体具有相关性进行探索研究，利用以往接收到的多个航位推测载体进行当前实体运动状态预测，实体在运动过程中可以随时根据以往运动状态分析其当前运动规律，结合以往多个航位推测载体进行推测，比单一的使用上次航位载体预测结果更加准确，而且使用多个航位推测载体，可以预测实体速度加速度变化，因此在网络传输过程中可以减少航位推测载体所承载的信息量，从而减少网络带宽.

实体当前运动状态与临近的运动状态具有很高的相关性，且这种相关性随着时间间隔的增加逐渐减小.由于航位推测算法所预测的实体速度信息要求很高的实时性与精确性，所以本研究选取其前1s内的航位推测载体来推测当前速度信息.本研究以模型（2）为例进行研究，根据实体运动前1s内速度变化情况进行多项式拟合，得出其速度变化曲线，这样就可以在网络间只传递其位置和速度信息.本文根据这种思想进行算法设计，采用不同次数多项式进行拟合分析（见式（4）～（7）），并与传统算法推测的结果进行比对.

在公式（4）、（5）中，V表示预测速度，V0表示前一时刻速度，t表示当前时刻，a，b，c分别表示各个模型系数.模型（4）是传统上航位推测技术使用的方法，在接收到下一个DR Vector前速度不会发生改变.模型（5）、（6）、（7）分别表示根据以前的DR Vector进行拟合的1次、2次、3次速度变化曲线.将当前的时间代入拟合出的曲线函数，计算出当前实体速度.当实体接收到新的DR Vector则重新拟合速度变化曲线.

当接收端实体运动到B′时接收到发送端在T0时刻发送的DR0，此时接收端开始使用改进的航位推测模型进行预测当前发送端实体位置B（见式（8）），并将接收端实体移动到B，然后根据时间变化预测当前实体速度，直到下次航位推测载体到来.

根据以上各种模型，本文分别进行了相应的研究并编写算法进行试验（见图2、图3）.

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

图3 模拟界面Fig.3 UI of the simulation

3 实验结果分析

根据以上模型进行算法编程，并进行误差分析.在该研究中我们主要对传统模型与改进模型拟合结果进行速度与位置比较.在相同的硬件环境下，每0.2s发送一个DR Vector，分别得出各模型拟合速度与真实速度曲线变化，由此来比较算法模拟结果.

公式（9）表示速度误差计算公式.其中V表示真实速度，V′表示预测速度，Vx，Vy，Vz，Vx′，Vy′，Vz′分别表示实体在坐标系中x，y，z方向上的真实速度与预测速度.公式（10）表示位置误差计算公式，其中P表示真实位置，P′表示预测位置，Px，Py，Pz，Px′，Py′，Pz′分别表示实体在坐标系中x轴，y轴，z轴方向上的实际位置与预测位置.

图4～图6中横坐标均表示时间变化，纵坐标分别表示速度变化、速度误差大小、位置误差大小.从中可以看出传统模型下每个更新间隔内拟合速度保持不变，且其误差均接近某一恒定值，并不能真实地反映实体真实运动情况.而改进后的模型基本符合实体速度真实变化情况，因为模拟过程中是先加速后减速连续的运动，其速度误差与位置误差均具有一定的周期性.各模型下的误差进行取绝对值后平均得平均值（见表2）.

图4 各模型下真实速度与拟合速度对比图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 各模型下平均速度误差与平均位置误差对比表Tab.2 The mean error of velocity and position in different model

由各模型下拟合速度与真实速度变化曲线可以看出，因为传统模型仅根据上一次收到的DR vector进行速度更新，在两个时间间隔内没有考虑速度变化，其速度变化曲线成锯齿状，且其速度更新总是落后于真实速度.当下一次DR vector到来时产生的平均速度误差为2.12 m/s，平均位置误差为0.40 m.由模型（1）拟合速度与真实速度结果图可以看出在每次加速或者减速过程中，模型（1）拟合的速度可以很好地反映实体真实速度，但是在每次由加速变为减速或者由减速变为加速时，该模型不能很好地反映实体真实速度变化，其平均速度误差和平均位置误差都远小于传统模型.由于每次模拟速度变化都接近于匀变速运动，所以在模型（2）和模型（3）的拟合结果中并没有很好地发挥其优势，但是其总体拟合结果优于传统模型.

4 结论

通过以上实验证明，基于多航位推测载体改进后的算法可以在DR vector不包含速度变化信息的情况下进行拟合出速度变化情况，减少了网络带宽.考虑每个间隔时间内实体速度变化后，大大减少了前出差.但是改进后的模型在应用的过程中还需要根据实体速度变化情况进行使用，当实体做简单的运动时，并不需要在接收端使用较高次的速度拟合.本文在此仅给出了这种算法的可行性，并在山洪应急虚拟演练平台中进行了应用.但是本研究也有一定的缺陷：1）DIAs中航位推测过程中考虑的因素繁多，这里仅基于实体运动惯性进行了研究，并没有考虑外界虚拟环境对人物或物体的影响.2）减少网络带宽的方式很多，这里也没有在兴趣管理、建立动态用户列表等［6］方面进行研究.

［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，Fujita 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，Frontiers 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］何高奇，潘志庚，李永青，等.虚拟健身网络游戏集成同步技术［J］.计算机辅助设计与图形学学报，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］刘冬，赵跃龙，曾文英.云平台ROIA中基于目标预测的DR算法［J］.华南理工大学学报：自然科学版，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技术在网络游戏中的应用［J］.计算机应用研究，2007，24（9）：231-233.

［16］刘璐.基于P2P的网络游戏架构和同步算法［D］.西安：西安电子科技大学，2007.

［17］何连跃，李思昆.多阈值推算定位技术研究［J］.计算机研究与发展，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，Ferrin 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.

责任编辑：黄 澜

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，Fujian Normal University，Fuzhou 350007，China；2.Fujian Provincial Engineering Research Center for Monitoring and Assessing Terrestrial Disasters，Fuzhou 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，Fuzhou 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

福建省科技厅公益类科研院所重点项目；福建省科技厅产学研重大项目（2012Y4001）*通讯作者