第 卷第 期 南 京 邮 电 大 学 学 报 自 然 科 学 版 VolNo
年 月 Journal of Nanjing University of Posts and TelecommunicationsNatural Science Dec
一 种 支 持 大 型 多 人 在 线 游 戏 的 覆 盖 网 组 播 生 成 树 算 法
林巧民
王汝传
许棣华
林萍
南京邮电大学 数字媒体研究中心江苏 南京
南京邮电大学 计算机学院江苏 南京
南京大学 计算机软件新技术国家重点实验室江苏 南京
摘要提出了一种基于 AOIArea of Interest域的可调覆盖组播生成树算法 AOMST Adjustable Overlay Multicast
Spanning Tree该算法可用于支持大型多人在线游戏 MMOGMassively Multiplayer Online Games 它的基本思想
是先将 MMOG 按照兴趣域划分分区在每个分区内以结点带宽及时延为可调影响因子构建组播生成树然后再通
过 种不同的结点变换操作来进一步减少组播生成树中的时延 仿真实验表明AOMST 算法是有效的
关键词大型多人在线游戏兴趣域覆盖网组播带宽时延
中图分类号TP文献标识码B文章编号
The Design and Implementation of an Intelligent Game Engine
Based on OGRE
LIN Qiaomin
WANG Ruchuan
XU Dihua
LIN Ping
Digital Media Research CenterNanjing University of Posts and TelecommunicationsChina
College of ComputerNanjing University of Posts and TelecommunicationsChina
State Keylab for Novel Software TechnologyNanjing UniversityChina
AbstractThis paper presents an Adjustable Overlay Multicast Spanning Tree AOMST algorithm which
is based on Area of Interest AOIThe algorithm can be used to support Massively Multiplayer Online
Games MMOGIts fundamental idea is to divide the MMOG world into different areas of interestthen
construct multicast spanning tree based on bandwidth and latencywhose affection factors are adjustable
within each AOINextthe latency of the multicast spanning tree can still be reduced via three different
node swap operationsThe experimental results indicate that AOMST is really effective
Key wordsmassively multiplayer online game area of interest overlay multicast bandwidth latency
收稿日期修回日期
基金项目国家自然科学基金 国家高技术研究发展计划 计划 AAZAAZ 江苏省高 技术研
究计划 BG 南京市高科技计划 软资 现代通信国家重点实验室基金C 江苏省高校科技创新
计划 CXBZCXBZ 南京邮电大学青蓝基金 NYNY 资助项目
通讯作者林巧民电话Emailqmlinnjupteducn
0引言
目 前 的 MMOG Massively Multiplayer Online
Games大多数采用的是集群 C S 模式这种模式面
临着伸缩性问题资源用户热区以及过多的服务器
之间通信等 针对 MMOG 的伸缩性问题可以有两
种不同的解决方法一种是通过增加硬件资源的方
法如花费重金部署更多的服务器这种方法的基本
思想是以牺牲硬件资源来进行系统扩容另一种方
法是通过减少通信负载来实现系统扩容主要包括
AOI Area of Interest 技术
DR Dead Reckon
ing 技术
和 ALM Application Layer Multicast 技
术
等AOI 是利用游戏环境中的玩家一般只跟他
周边的其他玩家打交道这一系统特征通过只给临
近的对象发送状态更新数据的方法来减少通信负
载DR 的实质是以牺牲系统一致性来优化通信