云平台ROIA中基于目标预测的DR算法*

刘冬 赵跃龙 曾文英，3

(1．华南理工大学计算机科学与工程学院，广东广州510640;2．暨南大学计算机科学系，广东广州510632;3．广东科学技术职业学院计算机工程技术学院，广东珠海519090)

实时在线交互应用(ROIA)是近几年来出现的一类基于互联网的、云计算环境下的新分布式应用［1］，包括交互式电子学习和大型多人在线游戏(MMOG)在内的应用系统等都是ROIA的典型应用．ROIA的高密集用户交互、单应用实例高并发性、连接的随意性、高服务质量要求，决定了ROIA需要较高的网络带宽和较低的网络延迟来保证这些实时交互用户之间的状态一致性．为避免有限的网络带宽被大量的更新信息所耗尽，ROIA通常以尽可能低的频率发送更新信息．这就需要有某种技术来弥补两个更新信息之间ROIA用户状态信息的连续性，确保良好的用户体验．因此，如何根据现有互联网状况，在有限的网络带宽和较大的网络延迟情况下保证状态一致性问题，已经成为目前ROIA技术的研究热点之一．

航位推算(DR)算法是目前在ROIA中为解决此问题而最常采用的一种技术．DR算法［2-3］最初用于分布式虚拟仿真系统中，是缓解实时性问题及减少通信量的有效方法，现已大量应用于交通、游戏等领域．文献［3］中提出了根据虚拟角色相对位置自适应地调整阈值的DR算法．文献［4］中提出了一种多阈值的DR算法，该算法中虚拟角色所发送的数据是经过分类的，不同类型的数据对应不同距离的虚拟角色责任域空间．文献［5］针对点对点(P2P)环境下的ROIA提出了一种自适应调整错误阈值的增强DR算法模型．

在基于DR算法的更新机制中，实体的实际位置和推测位置存在不一致性，度量这种不一致性最简单、最直接的方法就是测量实际位置和推测位置之间的空间差异．文献［6］中证明了不一致状态持续时间的长短对用户感觉上的影响，并提出了一种时空不一致的度量方法，该方法综合考虑了空间的差异和持续时间的长短．文献［7］在减小可觉察的不一致状态时也考虑到了不一致时间持续长短的影响．另外，更新间隔期间积累的航迹推算误差在文献［8-9］中被用来作为不一致性程度的一种度量．文献［10］中提出了一种新的在消息丢失情况下提高一致性程度的DR算法的更新调度策略．

在DR算法中，如果能提高预测的准确度，则将大大提高DR算法的整体性能．文献［11］中采用神经网络来预测实体的速度变化．AntReckoning［12］则借鉴蚁群算法的思想来改进DR算法，以提高DR算法预测的准确度．ARIVU［13］在移动游戏环境下通过预测用户的下一步动作来决定是否将移动设备的网卡转入休眠状态，从而达到节能的目的．

但传统DR算法大多仅基于物理力学公式进行预测［14-15］，没有考虑到应用中虚拟角色的状态及目标对预测的影响．而在实际应用中，即使在相同的场景下，虚拟角色状态的不同也会使得其运动轨迹有所不同．例如，当虚拟角色的生命值较高时，宝物等物品对其吸引较大，而在虚拟角色的生命值较低时，其向医疗点运动的可能性很大．因此，传统DR算法单纯考虑其惯性的思想大大降低了其预测的准确度．为此，文中提出了一种改进的DR算法，并通过仿真实验验证该改进算法的有效性．

1 ROIA云平台

传统的ROIA通常采用客户/服务器模式，并在服务器端通过服务器集群等技术来支持大规模的用户并发操作．此结构虽然有实施简单、安全性容易保证等优点，但其可扩展性、可伸缩性较差．为应付高峰时段大规模的用户数，传统的ROIA提供商必须储备足够的计算与存储资源，然而不少资源在非高峰时段却被白白闲置．为此，文中提出了一种ROIA云平台，利用云计算可伸缩性好的优点来提高底层硬件的利用率，降低ROIA提供商的运营费用．

ROIA云平台结构如图1所示，其中ROIA提供者可以是基础设施提供者，也可以从其他云计算提供商租用相关资源．基础设施提供者提供了底层硬件资源的监控和管理工作．ROIA提供者除将ROIA应用部署到基础设施上运行外，还要根据反馈的底层资源监控情况，并结合ROIA运行的特点进行负载预测，从而进行优化的资源调度．

图1 ROIA云平台结构Fig．1 Structure of ROIA cloud platform

在ROIA中，用户通过客户端操纵着虚拟角色在游戏世界中进行生产、竞争、探险及战斗等活动．客户端周期性地将虚拟角色的状态、位置等信息发送给服务器，而服务器也会周期性地将其他虚拟角色、非玩家控制角色(NPC)等的状态及位置信息发送给客户端，客户端利用这些信息对其游戏世界进行更新，使其与服务器的游戏世界保持一致．

在这些更新信息到达前，如果游戏世界保持静止不动直到收到更新信息才继续活动，将极大降低游戏的可玩性．引入预测技术可使得在没收到更新信息之前，游戏世界中各角色能按照算法预测继续运动而不让用户感到明显的停顿．当预测和实际运动出现偏差时，需引入平滑处理技术，将虚拟角色平滑地拉回正确的位置而不出现明显的跳动．

目前，大多数的游戏均使用DR算法进行预测和平滑处理．传统的DR算法主要是基于如下物理运动学公式［14］进行预测:

式(1)表明，从t时刻到t+Δt时刻虚拟角色的位置保持不变;式(2)描述了虚拟角色从t时刻以匀速vt运动Δt时间后的位置;式(3)描述了从t时刻开始以vt为初始速度、at为加速度运动Δt时间后的位置．

从式(1)-(3)可以看到，传统DR算法所预测的虚拟角色运动轨迹只与虚拟角色现在的位置及运动状态有关，并没有考虑其他因素的吸引和虚拟角色自身状态对虚拟角色运动轨迹的影响．然而，在实际的ROIA中，用户在很多情况下会因为其他因素的吸引而改变其运动方向．例如，刚刚出现在用户兴趣域的宝物、装备、快速移动的敌人和NPC等，均会影响虚拟角色的运动轨迹，使其不是严格按照惯性进行运动．此外，虚拟角色自身的状态也会对其运动方向产生很大的影响．例如，在同样的游戏场景下，健康的虚拟角色(即生命值较高)很可能被宝物、装备等物品所吸引，然而受伤的虚拟角色(特别是生命值很低的情况下)往往会不顾一切地向医疗品、急救包这类物品运动．

因此，文中的改进算法综合考虑了其他因素的吸引和虚拟角色自身的状态，以提高预测的准确度．

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)为调节新产生吸引力和积累吸引力对结果影响度的参数;D(R2，R1)为R2和R1之间的最短可达路径长度，吸引力随着可达路径长度(该长度不一定是直线距离，而是游戏中R2到R1的最短可达路径长度，因为有可能R2虽然在R1的兴趣域内，但因为有障碍物而使它们不可达或之间的实际路径很长)的增加而衰减;α为调节距离对吸引力衰减影响的参数．

B(R2，R1)根据R1的生命值与生命阈值Lth(由阈值参数δ乘以最大生命值得到，0≤δ≤1)的比较结果来量化吸引力:①R1的生命值大于Lth，表示虚拟角色健康，可按照等级越高或价值越大的物品吸引力越大、敌人等级越低吸引力越大等兴趣预测规则产生一个吸引力值．②R1的生命值小于Lth，若R2是医疗类物品，则产生一个绝对大的固定值，该值远大于过程①产生的吸引力值，但不是无穷大，当同时有多个医疗物品时，就由距离来决定其吸引力的大小;若R2不是医疗类物品，则按过程①产生吸引力值．

热度Ht(R2)反映R2的受欢迎程度，并用它来影响R2的吸引力值．文中借鉴蚁群算法中信息素增减的思想来规范Ht(R2)的产生和减小．Ht(R2)作为角色或物品的属性值(0≤Ht(R2)≤100)，其初始值为0，每次将R2选定为目标后R2的热度增加k(0≤k≤100)个单位值．另外，热度随时间的延长而衰减，即式中，ε为调节热度衰减快慢的参数，0≤ε≤1．

2．3 预测数学模型

吸引力量化后就可以通过比较选择出最大者作为目标．假设t时刻R2对R1的吸引力最大，则将其吸引力值At(R2，R1)引入式(3)并适当优化，可得到如下预测公式:

式中，ω为调节吸引力值和加速度的参数，0≤ω≤1．vt和at可按如下公式进行优化:

文献［15］已经证明此优化(见式(7))可以有效地提高预测曲线的平滑度．

3 仿真实验及结果分析

文中采用Python 2．5实现了基于目标预测的改进DR算法和传统的DR算法，并设计实现了一个模拟实验环境，如图3所示．用不同图标点模拟了MMOG中其他玩家角色、医疗点、修理点或宝物等对象，每个图标下方的数据分别标明了该点所在的坐标(单位为像素)和当前热度值，只有兴趣域中的点才进行吸引力计算．另外，为了降低实现难度，文中没有引入障碍物的情形，但D(R2，R1)已经考虑到了有障碍物的情形，在实际应用中只需将寻径算法得出的最短可达路径长度代入计算模型即可，因此该仿真实验的结果仍不失其普适性．

图3 模拟实验程序界面Fig．3 Interface of simulation program

实验中发现，基于目标预测的改进DR算法的预测准确度高于传统的DR算法．图4是两种算法的预测路线与实际路线的偏离值，可以知道，文中算法的预测偏离值在大部分时间(73%的实验时间)内比传统的DR算法小，即文中算法的预测准确度在73%的实验时间内均优于传统DR算法．

图4 两种算法的预测偏离值比较Fig．4 Comparison of predicted deviations between two algorithms

图5给出了传统DR算法与基于目标预测的改进DR算法的预测偏离值的差值．从图中可知:在大部分时间内2种算法的预测偏离值的差值大于0，即文中算法的预测偏离值较小，说明其预测结果更为准确;从差值的幅度看，文中算法总体上优于传统的DR算法．

图5 两种算法的预测偏离值的差值Fig．5 Predicted deviation difference of two algorithms

4 结语

传统DR算法大多是基于物理运动学公式(即运动惯性)进行预测的，没有考虑到实际应用中虚拟角色状态及目标对其预测运动轨迹的影响，因此其预测准确度较低．为此，文中提出了一种云平台实时在线交互应用中基于目标预测的改进DR算法，该算法既考虑了运动惯性对预测轨迹的影响，又考虑了虚拟角色当前状态及其目标对预测轨迹的影响．仿真实验结果表明，文中提出的基于目标预测的改进DR算法的预测准确度优于传统的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］．计算机研究与发展，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．