（计算机软件与理论专业论文）基于p2p覆盖网的mmog关键问题研究.pdf

摘要 论文题目：基于p 2 p 覆盖网的m m o g 关键问题研究 专业：计算机软件与理论 博士生：。罗佳 指导教师：常会友教授 摘要 随着互联网和虚拟环境技术的发展，以大型多人在线游戏( m m o g ，m a s s i v e m u l t i - p l a y e ro n l i n eg a m e ) 为代表的网络游戏产业迎来了新世纪的空前繁荣。它 对社会经济的发展起着巨大的推动作用。然而，传统m m o g 主要采用集中式服 务器集群技术来处理大规模的资源行为和用户请求。这种方法不仅运营费用昂 贵，在伸缩性和稳定性方面也不能满足日益增大的用户需求。因此，与对等网络 ( p 2 p ，p e e r - t o p e e r ) 相结合的技术成为了m m o g 研究的新方向。 通过将负载分布到网络中的所有节点进行处理是提高系统伸缩性的最佳途 径。但是，分布式环境缺乏统一的中心控制机制，依靠多个节点之间的协作来维 持整个游戏世界的逻辑运行面临着许多挑战，主要包括：1 ) 精确的发现资源和 节点，以便它们之间能够进行交互；2 ) 当多个节点同时访问同一资源时，该资 源状态如何保证一致；3 ) 尽量实现节点间的负载均衡，避免局部节点因负载过 重而影响游戏的实时性；4 ) 尽量减少节点间交互的传输延迟和带宽消耗；5 ) 节 点间的关系频繁变化时，如何保证系统的稳定性：6 ) 为了让游戏世界向前发展， 无论是用户数据还是资源状态都要进行持久保存，如何实现这些状态的分布式存 储；7 ) 分布式环境下的节点更容易产生欺骗行为，系统需要实现更加有效的安 全机制来保证游戏的公平性。 本文结合以上问题分析了国内外已有的研究成果，总结出这些方法存在的缺 陷，并在区域内单协作者模型的基础上提出了一种结构化多代理节点( s m a ， 1 中山大学博士学位论文 s t r u c t u r e dm u l t i a g e n t ) 的p 2 pm m o g 模型。本文的主要创新点如下： 1 建立p 2 pm m o g 模型的关键任务是实现有效的兴趣管理机制。兴趣管理 是通过将节点和资源进行合理的组织，并以最有效的方式把与节点相关的信息反 馈给它。为了精确的发现资源，本文采用静态划分区域的方法，每个区域通过资 源定位算法映射给网络中的个管理节点。区域内的节点和资源由该管理节点进 行组织。由于管理节点成为了整个区域的控制中心，因此，任意节点通过资源定 位算法定位到其所在区域的管理节点后，可以获得区域内所有节点和资源的信 息。同时，为了与相邻区域的节点和资源交互，管理节点还要负责定位到邻居区 域的管理节点，进而获得邻居区域的所有节点和资源信息。 2 为了让系统具备更好的伸缩性，本文提出了一种基于资源处理权的分配算 法。算法规定，管理节点只负责组织区域内的节点，并缓存区域内的所有状态。 它不负责处理节点发生的任何事件。所有加入该区域的普通节点都被称为代理节 点。代理节点负责处理节点和资源间的交互事件。为了实现代理节点间的负载均 衡，并保证资源状态的一致性，算法充分考虑了区域内资源的消耗指数和节点的 性能指数，所有资源被分配给具备相应处理能力的代理节点维护。分配策略采用 最先匹配的方式。任意时刻，资源的状态都只能由唯一的代理节点进行修改和更 新。由于状态更新由区域内的所有节点承担，消息的传输方式可采用高效的单播 方式而不是延迟较大的应用层多播树。 3 本文采用了三种同步技术：节点更新同步，事件处理同步和安全管理同步。 采用节点更新同步的原因是，当区域内的节点关系变动时，需要重新分配资源的 处理权，这时节点相互间需要短暂的时间来转移处理权。如果在转移过程中出现 了多个节点同时拥有一个资源的处理权。那么，资源状态就会不一致。因此，必 须保证在处理权分配算法执行完成后进行事件的处理。事件处理同步技术主要用 于处理复杂( 具有多个影响对象) 事件。由于资源的状态只能由一个节点进行更 新，而具有多个对象的事件不能分配给唯一节点处理，因此，本文规定所有的事 件都必须是原子事件。即该事件只影响一个资源的状态。复杂事件必须分解成原 子事件，并通过多个节点间的同步计算来达到一致性。安全管理同步主要针对分 布式环境中最主要的8 种欺骗行为进行设计。它采用管理节点进行协作检测的方 式，定程度上保证了游戏的公平性。 4 对于用户数据和资源状态的持久性保存，本文暂时引入数据服务器来承 担。数据服务器具有一定的辅助功能。包括用户登录验证，用户状态保存，资源 状态维持，节点定位等。为了测试s m a 模型的各项性能。本文实现了一个可视 化仿真工具。通过分析服务器模式，区域内单协作者模型与s m a 模型各项性能 指数的差异，充分说明了s m a 模型的优势。 关键词：大型多人在线游戏；对等网络；兴趣管理；一致性；负载均衡。 i i i 中山大学博士学位论文 t i t l e ：r e s e a r c ho nk e yi s s u e so fm m o gb a s e d0 np 2 po v e r l a y m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：l u oj i a s u p e r v i s o r ：p r o f e s s o rc h a n g a b s t r a c t w i t ht h ed e v e l o p m e n to ft e c h n o l o g yi ni n t e r n e ta n dv i r t u a le n v i r o n m e n t , n e t w o r k g a m ei n d u s t r yr e p r e s e n t e db yt h em a s s i v em u l t i p l a y e ro n l i n eg a m e sh a su s h e r e di n u n p r e c e d e n t e dp r o s p e r i t yi nt h en e wc e n t u r y i tp l a y sag r e a ts o c i a la n de c o n o m i cr o l e i np r o m o t i n gt h ep r o g r e s s h o w e v e r , t h et r a d i t i o n a lm m o g s m a i n l yu s ea c e n t r a l i z e d s e r v e rc l u s t e rt e c h n o l o g yt oh a n d l el a r g e s c a l er e s o u r c e sb e h a v i o ra n du s e rr e q u e s t s b e s i d e st h ee x p e n s i v eo p e r a t i n gc o s t s ，t h es c a l a b i l i t ya n ds t a b i l i t ya r ea l s ol i m i t e d t h ea p p e a r a n c eo fp e e rt op e e r t e c h n o l o g yb r i n g st h em m o gan e wd i r e c t i o n d i s t r i b u t i n gt h el o a dt oa l ln o d e si su n d o u b t e d l yt h eb e s tc h o i c et oi m p r o v e s c a l a b i l i t yo fs y s t e m t h ed i s t r i b u t e de n v i r o n m e n tl a c k st h eu n i f i e dc e n t r a lc o n t r o l m e c h a n i s ma n dm a k e st h ep 2 pm m o gm o d e lm o r ec o m p l e xt oe s t a b l i s h t h em a i n c h a l l e n g e si n c l u d ef o l l o w i n g s ：1 ) h o wt ol o c a t er e s o u r c e sa n dn o d e sa c c u r a t e l ys ot h a t t h e yc a ni n t e r a c tw i t he a c ho t h e r ；2 ) w h e nm u l t i p l en o d e ss i m u l t a n e o u s l ya c c e s st h e s a m er e s o u r c e ，h o wt oe n s u r et h ec o n s i s t e n c yo ft h er e s o u r c es t a t e ；3 ) t r yt oa c h i e v e l o a db a l a n c i n gb e t w e e nn o d e sa n da v o i dt h es l o we x p e r i e n c ed u r i n gt h eg a m ec a u s e d b yt h eo v e r l o a d i n go fl o c a ln o d e s ；4 ) t h em e s s a g et r a n s m i s s i o nb e t w e e nn o d e ss h o u l d g u a r a n t e et h em i n i m u mt r a n s m i s s i o nd e l a ya n db a n d w i d t hc o n s u m p t i o n ；5 ) h o wt o e n s u r es t a b i l i t yo fs y s t e mw h e nt h er e l a t i o n s h i po fn o d e sc h a n g e sf r e q u e n t l y ；6 ) t h e s t a t e so fu s e r sa n dr e s o u r c e ss h o u l db ep r e s e r v e dp e r s i s t e n t l yf o rm a k i n gt h eg a m er u n f o r w a r da sar e a lw o r l d ；7 ) n o d e sa r ee a s i e rt oc h e a ti nt h ed i s t r i b u t e de n v i r o n m e n t , - a b s t r a c t t h es y s t e mm u s tp r o v i d eam o r er o b u s ts e c u r i t ym e c h a n i s m i nt h i sp a p e r , w ea n a l y z et h ee x i s t i n gr e s e a r c hr e s u l t sa th o m ea n da b r o a d s u m m e du pt h ep r o b l e m so ft h e m ，a n dp r o p o s eal o a db a l a n c i n gm o d e lb a s e do n s t r u c t u r e dm u l t i a g e n t i t sc o n t e n ti sa sf o l l o w s ： 1 t h ek e yt a s ko fe s t a b l i s h i n gap 2 pm m o gm o d e li st oa c h i e v ea ne f f e c t i v e m e c h a n i s mo fi n t e r e s tm a n a g e m e n t i n t e r e s tm a n a g e m e n to r g a n i z e sn o d e sa n d r e s o u r c e sr a t i o n a l l y , a n df e db a c kt h ei n f o r m a t i o na s s o c i a t e dw i mt h en o d eb ya n e f f e c t i v ew a y t ol o c a t er e s o u r c e sa c c u r a t e l y , t h i sp a p e ra d o p t sam e t h o do fd i v i d i n g w o r l di n t os t a t i cz o n e s e a c hz o n ei sm a p p e dt oam a n a g e rt h r o u g ht h er e s o u r c e a l l o c a t i n ga l g o r i t h m a l lt h en o d e sa n dr e s o u r c e si nt h ez o n ea r em a n a g e db yt h e m a n a g e r a st h em a n a g e rb e c o m e st h ec o n t r o lc e n t e ro fw h o l ez o n e ，a n y n o d ec a ng e t i n f o r m a t i o no fo t h e rn o d e sa n dr e s o u r c e si nt h es a m ez o n ea f t e rc o n n e c t i n gt ot h e m a n a g e r m e a n w h i l e ，t om a k ei n t e r a c t i o nb e t w e e nn o d e sa n dr e s o u r c e si na d j a c e n t z o n e s ，m a n a g e rs h o u l dl o c a t en e i g h b o rm a n a g e r sf o rg e t t i n gi n f o r m a t i o no fn e i g h b o r n o d e sa n dr e s o u r c e s 2 t og i v et h es y s t e mb e t t e rs c a l a b i l i t y , t h i sp a p e rp r o p o s e sa na s s i g n m e n t a l g o r i t h mb a s e do nt h ep r o c e s s i n gl i c e n s eo fr e s o u r c e t h i sa l g o r i t h mr e q u i r e st h a tt h e m a n a g e ri so n l yr e s p o n s i b l ef o ro r g a n i z i n gn o d e sa n dc a c h i n gs t a t e si nr e s p o n s i b l e z o n e s i tn ol o n g e rh a n d l e sa n ye v e n t so c c u r r e db yt h en o d e s i n s t e a d ，a g e n t si n v o l v e d i nt h ec o n t e x ta r ei nc h a r g eo ft a s kp r o c e s s i n gi naz o n e f o ra c h i e v i n gt h el o a d b a l a n c i n ga m o n gn o d e sa n dg u a r a n t e e i n gt h ec o n s i s t e n c yo fs t a t e s ，a l g o r i t h mt a k e s f u l la c c o u n to fr e s o u r c ec o n s u m p t i o ni n d e xa n dn o d ep e r f o r m a n c ei n d e xw i t h i nt h e z o n e e a c hr e s o u r c ei sa s s i g n e dt oa na g e n tw h oh a se n o u g hp r o c e s s i n gp o w e r s o ，t h e s t a t eo far e s o u r c ec a nb em o d i f i e da n du p d a t e db yo n l yo n en o d ea ta n yt i m e a st h e s t a t eu p d a t e sd i s t r i b u t e dt oa l ln o d e s ，t h et r a n s m i s s i o nm e s s a g ec a nb et a k e nt o e f f i c i e n tu n i c a s tr a t h e rt h a nt h ea p p l i c a t i o nl a y e rm u l t i c a s t 3 t h i sp a p e ru s e st h r e ek i n d so fs y n c h r o n i z a t i o nt e c h n o l o g y ：n o d er e l a t i o n s y n c h r o n i z a t i o n , e v e n tp r o c e s s i n gs y n c h r o n i z a t i o na n ds e c u r i t ys y n c h r o n i z a t i o n n o d er e l a t i o ns y n c h r o n i z a t i o ni su s e df o rr e a s s i g n i n gt h el i c e n s e sw h e nr e l a t i o n so f n o d e si naz o n ec h a n g e s t h e s en o d e sn e e das h o r tt i m et ot r a n s f e rl i c e n s e s i ft h e r ei s v 中山大学博士学位论文 n os y n c h r o n i z a t i o ne x e c u t e da m o n gn o d e s ，s o m el i c e n s e sc o u l db eh e l ds i m u l t a n e o u s b ym u l t i p l en o d e s t h e n c e ，t h ee v e n tp r o c e s s i n gm u s tb es t a r t e da f t e rf i n i s h i n gt h e l i c e n s ea s s i g n m e n t e v e n tp r o c e s s i n gs y n c h r o n i z a t i o ni sm a i n l yu s e dt oh a n d l et h e c o m p l e xe v e n tw h i c hc a na f f e c ts t a t e so fm u l t i p l et a r g e t s a so n es t a t ei sm a i n t a i n e d b yo n ea g e n t ，t h ec o m p l e xe v e n tw h i c hm o d i f i e sm u l t i p l et a r g e t sc a l l tb ea s s i g n e dt o a n ya g e n t s o ，i nt h i sp a p e r , a l lt h ee v e n t sm u s tb et r a n s f o r m e dt oa t o me v e n t sw h i c h c a no n l ya f f e c to n et a r g e t t h e n , t h ec o m p l e xe v e n t sa r ed e c o m p o s e di n t oa t o me v e n t s a n ds y n c h r o n i z a t i o nb e t w e e nn o d e si su s e dt oo r d e rt h es e q u e n c eo fe v e n t s s e c u r i t y s y n c h r o n i z a t i o ni sd e s i g n e da g a i n s tm a i n l ye i g h tc h e a t i n gb e h a v i o r si nd i s t r i b u t e d e n v i r o n m e n t c o l l a b o r a t i n gb yt h em a n a g e r , t h es y s t e mc a na c h i e v eac e r t a i nd e g r e e o ff a i r n e s s 4 f o rt h ep e r s i s t e n tp r e s e r v a t i o no ft h es t a t e so fu s e rd a t aa n dr e s o u r c e s ，t h i s p a p e ri n t r o d u c e st h ed a t as e r v e rt oa s s u m et h er e s p o n s i b i l i t y d a t as e r v e rh a ss o m e s u p p l e m e n t a r yf u n c t i o n s ，s u c ha su s e rl o g i na u t h e n t i c a t i o n , u s e rs t a t ep r e s e r v a t i o n , r e s o u r c es t a t u sm a i n t e n a n c e ，n o d el o c a t i n g ，e ta 1 f i n a l l y , f o rt e s t i n gt h ep e r f o r m a n c e o fs m a ，av i s u a ls i m u l m i o no ft h es m am o d e li si m p l e m e n t e d t h r o u g hc o m p a r i s o n w i t ht h ec sm o d e la n ds o m ee x i s t i n gp 2 pm m o gr e s e a r c h e s ，t h es u p e r i o r i t yo f s m 渔m o d e l i si n d i c a t e d k e y w o r d s ：m m o g ；p 2 p ；i n t e r e s tm a n a g e m e n t ；c o n s i s t e n c y ；l o a db a l a n c i n g ： v i 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：髻彳蔓 日期：勘1 口年6 月6 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版。有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅。有权将学位论文的内容编入 有关数据库进行检索。可以采用复印、缩印或其他方法保存学位论文。 1 1 研究背景和意义 第1 章绪论 1 1 1 网络游戏发展现状及其趋势 从九十年代的单调文字m u d 时代，到( 万王之王的巨大成功，再到现在 的3 d 大型多人在线游戏，网络游戏正以惊人的速度发展壮大，并成为数字娱乐 市场最为重要的组成部分。 据相关资料显示，中国网络游戏的市场规模由2 0 0 1 年的3l 亿人民币增长 为2 0 0 9 年的2 5 8 亿人民币，远远超过了传统的三大娱乐产业电影票房，电 视娱乐节目和音像制品发行的收入同时也为电信。i t 相关产业带来近6 7 0 亿 的直接收入。新增就业机会达到万人以上。而游戏玩家的数量从过去的几十万成 长为现在的上亿。 r n 塥 规 模 圈l - 】网络游戏市场规模增长和主漉游戏市场份额凹 短短的十年时间，网络游戏发生了翻天覆地的变化。除了源于自身技术的飞 速发展外，也反映了广大消费市场的需求。这就是为什么当金融危机使世界经济 步入寒冬的时候，网络游戏却以欣欣向荣的姿态向全世界展现着其独特的魅力。 由于网络游戏产业对社会经济的进步起着重要的推动作用，同时为企业带来了可 中山大学博士学位论文 观的经济效益。因此，在政府的大力扶持下，越来越多的开发商和投资者涌入到 这一行业。游戏产品层出不穷，游戏内容不断丰富，市场规模急剧扩张。 以梦幻西游和魔兽世界为代表的大型多人在线游戏( m m o g ，m a s s i v e m u l t i - p l a y e ro n l i n eg a m e ) 是网络游戏发展的主力军。这类游戏不仅塑造了极具 魅力的虚拟世界，更为玩家提供了协作，交流和对战的互动平台。可以看出， m m o g 正朝着多元化和集中化的方向发展。一方面，它不再以单纯的战斗升级 作为题材，而是引入各种互动因素。形式上，它可以结合多种娱乐方式，如聊天， 卡拉o k ，视频等。内容上也可与其他产业相互渗透，如动漫，电影和文学，甚 至可以体现教育的理念，另一方面，m m o g 可与多类互联网平台进行整合，建 立强大的虚拟社区，并形成一定规模的产业链，以吸引更多的游戏玩家。总之， 无论采用哪种形式，未来的m m o g 都将以积极健康的方式稳步持续地发展。 1 1 2 传统m m o g 的弊端 网络游戏具有巨大的经济和社会价值，因此，在这一方面的研究也有重要的 意义。网络游戏研究涉及到的领域非常多，它可以涵盖图形学，物理学，网络技 术，软件工程，数据库，人工智能等多种学科。而目前出现的基于p 2 p 的m m o g 是一项用于解决m m o g 伸缩性的新技术。为了说明这一技术的研究价值，本文 给出了传统m m o g 架构的特点及其弊端。 传统m m o g 主要采用服务器集群技术 2 1 来承担大规模的玩家和资源处理消 耗。通常，服务器集群被分为许多独立的服务器组，每组服务器维护一个虚拟世 界。组与组之间没有交互。其网络架构如图1 2 所示。其中，总控制服务器在数 据库中保存了所有注册用户的信息，用户在登录游戏时，需要首先与该服务器建 立连接，并进行身份验证。当用户成功登录后，选择与某一服务器组建立连接。 为了让用户能在真正的游戏世界中进行体验，用户在开始游戏前都需要创建和选 择特定的角色作为用户的化身。但是，由于传统m m o g 在服务器架构设计方面 的限制，用户创建的角色通常只存在于一组服务器中。角色不能从一个服务器组 跨越到另一个服务器组。只有服务器组内的角色才可以进行交互。若用户需要与 其它服务器组的用户交互，只能转移服务器组重新建立角色。 基于p 2 p 覆盖网的m m o g 关键问题研究 厂舷务器量，、 l 麓拎l h l| 厂聪务器簸2 、 厂凇务器组3 _ 、 乱国圄圜 i 乱囤l 圜。圜 激务器教纷器 i 嗽务器缀务器l 客p 幸l l 客拱l客n 机落户橇寓p 套l 荔p 垂l霹p 玩牟广枫 图1 2 服务器集群架构 以上描述概括了传统m m o g 服务器集群架构设计的特点。其优点是实现相 对简单，控制非常方便。然而，缺点也是显而易见的。下面从几个方面说明集群 技术的缺点。 1 ) 投资大：随着用户游戏品味的不断提高，越来越多的新鲜元素加入到游 戏设计中，游戏系统日趋复杂。加之用户数量的急剧增加。因此，维持 一个规模较大的m m o g 需要消耗的硬件资源相当昂贵。据魔兽世界 相关网站显示【3 1 ，最高人气的服务器组可承载三千多玩家同时在线，而 最低人气的服务器组也有几百。如果平均维持两千，那么支持百万玩家 同时在线就需要消耗五百组服务器。虽然无法得知每组服务器的数量， 但根据相关数据推断【4 】，服务器组通常包括网关服务器，登录服务器， 数据库服务器和世界服务器。因此，至少需要消耗两千台服务器。除此 之外，运营过程中的额外费用支出也不少，如广告宣传，网络带宽申请， 机房租用和维护人员薪资等，总之，运营一款大型的m m o g 至少需花 费几千万人民币。这一笔费用对中小型企业来说是一项庞大的开销。 2 ) 伸缩性：服务器集群技术能够同时承载上百万的游戏玩家。但所有玩家 并非位于相同的虚拟世界，实际上，一个虚拟世界( 服务器组) 只能维 持相对有限的玩家数量。其伸缩性主要由硬件性能和系统的复杂度决定。 若要增加玩家的数量，则只能依靠增加服务器数量来实现。虽然目前硬 件的性能越来越好，但随着游戏系统的不断丰富，硬件的进步是不能满 足日益增长的用户需求的。另外，经验显示，不断地增加新服务器会导 3 中山大学博士学位论文 致旧服务器的游戏玩家向新服务器转移，从而降低旧服务器的人气，使 得旧服务器大量玩家流失。 3 ) 健壮性：在传统m m o g 中，服务器是游戏运行的核心。所有的用户指 令和资源行为都由服务器进行处理后更新给用户显示。没有了服务器， 客户端就无法正常运行。当服务器崩溃时，不仅所有客户端都要终止运 行，服务器也会有数据丢失。这会降低用户的体验感【5 】。 4 ) 扩展性：由于逻辑和数据都集中在服务器，因此用户的数据和行为只能 由游戏开发者进行控制。这限制了用户对游戏进行个性化设置。 5 ) 响应速度【6 l ：服务器每秒要处理成千上万的用户指令，然后将对象状态 更新给所有的用户。因此，游戏的实时程度由服务器的计算能力和网络 带宽等性能决定。运营商必须依靠提高硬件性能来达到较高的响应速度。 以上问题都充分说明了集群式服务器存在的缺点。如何有效的解决这些问题 成为了下一代网络游戏研究的热点之一。 1 1 3p 2 p 技术与m m o g 的结合 为了解决集中式服务器架构的缺点，大量研究采用了对等网络( p e e r - t o p e e r ) 技术 7 1 来实现全分布式的游戏架构。的确，通过将服务器中的负载全部转移到客 户端节点可有效的提高系统的伸缩性。但这一方向是否具有可行性呢? 在将p 2 p 技术应用于m m o g 前，需要找到它们的结合点。本文首先介绍传统m m o g 的 实现原理，再根据其特点分析与p 2 p 技术结合的可能性。 在m m o g 中，通常包括以下三类资源： 1 ) 场景资源：指地形，建筑，植物，天空，水体等场景对象。这些对象一 般是不可交互的装饰性物体，通常直接保存在客户端。 2 ) 玩家控制角色( a v a t a r ) ，指由用户控制，能在虚拟世界中漫游，并与其 他角色交互的化身。每个角色通常具有很多的属性，如角色外观，体质 状况，装备物品，当前任务，好友，工会等。 3 ) 非玩家控制角色( n p c ，n o np l a y e rc h a r a c t e r ) ：泛指由服务器控制的具 4 - 基于p 2 p 覆盖网的m m o g 关键问题研究 有特定行为的对象，玩家可与n p c 进行交互。如：接交任务，购买商品， 厮杀战斗等。 当玩家登录游戏时，服务器会返回玩家a v a t a r 的所有属性，其中包括a v a t a r 当前所在的地图坐标。客户端则根据该坐标加载当前所在区域的场景资源。同时， 服务器也会实时返回该区域的其他a v a t a r 和n p c 信息以进行交互。无论是a v a t a r 与a v a t a r ，n p c 与a v a t a r ，还是n p c 之间的交互，都由服务器进行处理后更新给 客户端。 资源之间的交互过程有一个特点，即客户端能够感知的和能够进行交互的资 源都与a v a t a r 所在的区域有关。实际上，游戏世界中的每一个可交互资源都具有 其相应的兴趣域【s 】( a o i ，a r e ao f i n t e r e s t ) 。对于不同的资源，其a o i 有不同的 定义。例如，a v a t a r 的a o i 不仅包括以其所在坐标为原点并以视野为半径的可视 化区域，也包括好友群，工会，音效 9 1 等特殊交互渠道。对于怪物n p c 来说， 其a o i 则是设定的一个攻击区域。在游戏中定义a o i 的目的是为了更好的组织 和管理资源。即通常所说的兴趣管理【1 0 1 。兴趣管理的原则是：资源只能与位于 其a o i 内的资源进行交互，而位于a o i 外的资源都与该资源无关【1 1 1 。 如图1 3 所示，三个资源a ，b 和c 将视野作为它们的a o i 。三个a o i 的大 小不一样，表明它们的感知范围不同。虽然a o i 相互交叠，但不一定能相互感 知。图中，只有资源a 可以感知资源b 的存在，而资源b 和c 不能感知a 的存 在。这时，服务器只会把资源b 的信息返回给资源a 。那是不是意味着资源a 可以与资源b 交互。而资源b 不能与资源a 交互昵。其实a o i 的作用只是为了 定位可以进行交互的对象。资源a 可以定位到资源b ，资源b 不能定位到资源 a ，仅此而已。一旦资源a 发起与资源b 进行交互，资源b 也可以与资源a 进 行交互。这一过程是在服务器端判断，对用户来说完全透明。 图l - 3 资源兴趣域间的交互 一5 一 中山大学博士学位论文 良好的兴趣管理机制可以有效的减少无关对象之间的交互。对于玩家来说， 只有位于其所在a o i 的资源才是可见的，而a o i 外的大部分资源都是不可见的。 因此，服务器将所有的资源和a v a t a r 按照区域进行分组管理，并实时检查a v a t a r 的a o i ，返回其a o i 内相应的资源状态l l2 。 以上描述概括了传统m m o g 的设计核心。那么，这如何与p 2 p 技术进行结 合呢? 实际上，a o i 的特性正是实现全分布式系统架构的关键。由于玩家只需要 关心a o i 内的资源，因此，可将a o i 内的资源发布到客户端节点上，由节点来 维持a o i 中的所有资源行为。这是p 2 pm m o g 设计的基本思想。但实现这一思 想还需要解决许多难题【1 3 】。例如，如何对资源进行定位，以精确找到a o i 内的 所有资源；若多个节点的a o i 相互重叠，怎样确定节点间的组织关系；当节点 在场景上移动时，怎样进行节点关系的更新【1 4 】等。这些问题都属于p 2 pm m o g 兴趣管理机制的一部分，在第二章将有详细的描述。 1 2p 2 pm m o g 面临的挑战 目前已有不少p 2 pm m o g 模型被相续提出，如p a s t r y p e e r t l 5 1 ，m a n l i i l o t i l 【1 6 1 ， m a t r i x 1 7 1 ，b a d l l m n a 【阍，m e d i a t o r 【1 9 1 等。同集中式服务器集群技术相比，这些模 型为游戏系统带来了较好的伸缩性，但同时也引入了以下几方面问题： 1 ) 状态一致性【2 0 1 ：在传统m m o g 中，所有资源的状态都由服务器进行维 护，修改和更新，用户的指令也只能由服务器进行处理，虽然不同的节 点由于网络延迟会不同时收到同一资源状态的更新消息，从而引起节点 上资源状态的暂时不一致。但是，节点最终会从服务器同步到所有资源 的正确状态，使所有节点上的资源状态保持一致。在p 2 p 环境下，由于 节点可以充当资源的处理者，如果没有合理的资源状态处理规则，可能 会出现多个节点同时修改同一资源状态的情况。例如，节点a 和b 都位 于同一区域，a 和b 同时修改资源c 的状态，然后更新给其他节点，于 是，c 的状态在其他节点上出现了不一致。要解决这一问题，需要限制 资源状态在同一时间只能由一个节点进行修改和更新。 2 ) 负载均衡性：在m m o g 中，资源和节点的分布都是不均匀的。资源和 - 6 - 基于p 2 p 覆盖网的m m o g 关键问题研究 节点相对较多的地方，处理量也相对较大。因而有必要进行负载均衡的 处理。集中式服务器的负载均衡策略【4 】主要依靠专门的负载均衡服务器， 将负载较重服务器上的资源和玩家转移到负载较小或新增的服务器上。 而在p 2 p 环境下，由于节点的不确定性使得这种转移的难度增大。一方 面，要确定节点的性能，计算出该节点应该承载多少负载。并根据性能 参数来进行任务分配。另一方面，要确定节点a o i 的粒度。粒度太大， 需要处理和更新的资源状态就多，承载的负担就重，粒度太小，资源间 a o i 关系的更新就会更加频繁，系统稳定性就会降低。总之，基于p 2 p 的负载均衡策略涉及的问题更复杂。 3 ) 容错【2 1 1 和稳定性：无论节点是正常下线还是异常下线，节点上保存的资 源状态和要处理的事件都会丢失，这对其他节点的正常运行有一定的影 响。在节点失效时需要处理两个问题。即快速恢复丢失的数据和重新建 立节点间的关系。这是保证其他节点正常进行游戏的关键任务。 4 ) 状态持久性：在集中式服务器模式下，所有的资源状态都由服务器进行 维持和保存，控制非常方便。而在p 2 p 环境下，资源的状态是由节点进 行维持的。用户在上线时需要获取到最近一次下线时的节点状态。这些 状态该如何进行存储呢? 此外，当节点位于某一区域时，其a o i 内的 n p c 状态和行为是由节点维持的，当所有节点离开这一区域时，n p c 的 状态和行为就会丢失。游戏的真实性就会受到影响。因此，必须设计一 种机制来保存这些信息。 5 ) 安全性 2 2 , 2 3 】：在p 2 p 环境下，用户的命令是由节点进行处理的。节点的 可靠性决定了数据的真实性。但是，游戏中难免存在少量恶意玩家。他 们利用游戏的缺陷任意修改游戏数据，试图获得更好的游戏奖励。这种 行为严重损害了其他玩家的利益，破坏了游戏的公平性。因此，需要及 时预防和制止。但是，p 2 p 环境下的作弊方式非常多。如发送错误数据 包，打乱事件处理顺序，冒充正当节点，多节点勾结等。不同的应用还 会出现不同的作弊方式。要解决这些问题必须建立良好的安全管理机制。 一方面，要尽量减少作弊的可能性，对可能发生的作弊行为进行检测和 中山大学博士学位论文 处理。另一方面，安全管理机制对系统性能具有一定的影响，如何用较 小的性能消耗来换取较高的安全性是个重要课题。 总之，以上问题都是建立p 2 pm m o g 的核心问题。只有解决了这些问题， 游戏系统才能正确和持久地运行下去。 1 3 主要研究内容 本文在已有研究的基础上，提出了一种负载均衡的结构化多代理节点( s m a ， s t r u c t u r e dm u l t i a g e n t ) 模型。该模型充分利用了p 2 p 技术的优势，在解决一致 性，负载均衡，稳定性和持久性等问题的同时，使系统具备了更好的伸缩性。 s m a 是建立在全分布式结构化拓扑基础上的p 2 pm m o g 模型。它将世界地 图划分为许多连续相等的六边形静态区域。资源和节点根据其所在的区域被划分 到不同的组中。每一个区域对应一个管理节点。管理节点负责组织区域内的节点， 但不处理区域内发生的事件。当节点加入区域时，需要首先通过资源定位算法【2 4 】 定位到区域的管理节点，从管理节点处获取其他已加入节点的信息，并与它们建 立连接。这样，节点就能获取到区域内的所有资源并与它们进行交互了。所有的 计算任务与状态更新都由区域内的节点代理处理。 为了让系统稳定的运行，s m a 实现了节点加入算法，邻居发现算法，节点 失效算法和节点跨域算法。节点加入算法用于让区域内的所有节点建立起联系， 从而实现域内资源问的交互。邻居发现算法通过定位邻居区域内的所有节点，让 相邻区域的资源可交互。节点失效算法和跨域算法则是保证区域内的节点关系发 生变动时，能够快速更新并恢复到正常运行的状态。这几个算法组成了s m a 模 型