1、当今的网页游戏也越来越强调及时性，Server 的负载过重也会造成 Server 与 Client 之间的不同步而导致延迟的出现，因 Server 较晚回应给 Client，玩家的动作会因此变慢，因此造成很多玩家感觉游戏本身的游戏性较差而造成大量流失玩家，下面就将次问题讨论Server 负载与解决之道!传统线上游戏系统架构主要有四种：Client/Server、Peer2Peer 、Hybrid Client/Server 及 Multi-Server，不同的游戏拥有不同的架构，具体情况具体分析。1、Client/Server 架构N 个 Client 连接至一个 Server，Client
2、只负责将玩家输入的信息发送给Server，Server 处理大部分运算并将处理结果发回给 Client。优势：设计简单，玩家作弊情形不容易发生劣势：由于整个运算都是在 Server 端进行，所以 Server 的运算能力及网络的流量是真个系统的瓶颈，当 Client 没有收到 Server 的任何信息前，Client 无法对玩家的输入做出任何反应，画面也无法及时更新，因此容易因 Server 运算延迟或网络延迟，造成游戏的不流畅，一旦 Server 达到上线或者 Client 增多时，则必须考虑使用功能强大的 Server 来取代。2、P2P 架构点对点构架最大的优势就是及时性，没有 Serv
3、er 的介入，所有消息都是参与游戏的电脑之间的做资料的传送。这种构架避免了不必要的传送延迟，但是要在网络环境上建立点对点的架构，那么每台电脑必须对所哟的电脑先建立连线并做出传输的处理，因此电脑的运算能与连线的频宽会造成不小的负担。3、Hybrid Client/Server 构架此构架的特点在于 Client 可以自行推测目标的状态，并且可以立即针对玩家的输入做出反应。这种构架把整个虚拟世界当成一个由所有玩家共同享的资料库，Client可分到部分资料库类容，并且可以依照资料对玩家的输入与玩家在游戏中的状态进行推测，兵即时的反应给玩家。因此如果 Client 尚未收到 Server 信息，则 C
4、lient 端依旧可以进行游戏，但是最终数据的决定全仍然掌握咋 Server 中，如果 Client 的自行计算结果与服务器的结果不相符合，则 Server 便会去修正 Client 的状态。此架构最大的问题在于网络延迟所带来的影响，若 Client 和 Server 之间传输延迟过大，则将会导致Client 端所推测的资料库内容与 Server 端的资料库内容差距过大。4、Multi-Server 架构早起的 mmorpg 游戏是有单一的 Server 负责整个游戏的内容，由于是单一的Server，因此游戏中能够容纳的线上人数及玩家间的互动会受到限制。而在 Multi-Server 构架中，
5、通过每一个 Server 负责一个部分的游戏的内容，但是在不同的 Server上玩家长处于不同的游戏世界里，因此无法互动，为了要提高系统整体的效能有效利用系统的运算及频宽的资源，一半以空间切割的方式分配 Server 权限范围及适当划分Server 负责的工作，是不同的 Server 负责不同区域间的玩家，因此能支持更多的线上玩家。目前 mmorpg 逐渐采用 Multi-Server 方式来减少 Server 的负载以及减轻网络的频宽限制。目前使用的 Multi-Server 分工的技术，大多采用空间切割的上市将虚拟世界的地图切成跟 Server 同等数量的片段，再将地图的片段分配给每一台
6、Server。当玩家靠近地图片段的边界时，玩家所在的 Server 会通知临近的地图片段的 Server，那么在最佳的情况下网络流量在这两个 Server 之间为零流量，没有玩家通过这两个 Server，而最差的情况为 O（mn） ，n 为玩家的数量，m 为 Server 的数量。MMORPG 负载均衡机制1.静态分布玩家到服务器平均分配玩家给每个 Server，使每个 Server 有相同数量的玩家。这种方法的优点是算法简单，但玩家在地图上移动，因此过一段时间，最差的情况下，Server 之间可能有大量的网络流量，因为当玩家在完成一个动作后，所有的 Server 必须获得另一个 Server
7、 的玩家数据，而其附近的玩家皆在不同的Server 上，如此依赖，每个玩家的一个动作需要传送消息到不同的 Server 上，将造成 communication 的极大负担。2.静态分配地图片段到服务器利用空间切割的方式将虚拟世界切割成和 Server 同等数量的地图片段，再将这些地图片段分配给每一个 Server 负责，然后再有一个 Dispacher Server负责将每一个玩家分配到所对应的 Server 上去，但由于玩家会在地图上移动，因此时间一久，在最差情况下，玩家可能都到同一个 Server 的地图片段上，这样当初的负载平衡就完全被破坏了。3.动态分配地图片段到服务器静态分配地图片段
8、至每个 Server 虽然可以减少 Server 间网络的频宽和负载，但必须使玩家在正确的分布地图上，玩家的位置是由玩家所操作的，因此会发生不可预料的问题，为了克服这类问题，将地图分切成更小的片段，然后动态的分配地图片段至 Server 上是需要的。然而这种方法要有效率，其关键在于如何切割地图片段，要切成何种几何形状的，该切成多少片段？传统的方法大都是切成正方形方块，切割数根据实际情况或模拟后作适当的处理。4、MMORPG 动态负载机制实现在上一片段中我们讨论了目前 MMORPG 所采用的负载平衡机制的架构，这里我们将提出我们的负载平衡方法，并且讨论如何动态以动态负载机制来调整线上游戏 Ser
9、ver 负载不平衡的现象。1、负载定义多人在线游戏中 Server 端必须完成一下三个工作：A.接受 Client 端玩家的状态、移动及交谈的讯息B.处理玩家和 NPC（Server 控制的角色，如怪物，任务角色等）间的互动。C.更新虚拟世界状态D.将虚拟世界更新后的信息传送回 Client 端以上工作当玩家越来越多的时候将话费更多的时间处理，因此 Server 上玩家暴增时，可能无法将信息及时的传送给每一个玩家，在这里我们把这四个工作所需要的时间定义成一个 Server 的负载；很明显的，在一个 Multi-Server 的 MMORPG 系统中，每一个 Server的负载和它所负责的玩家个
10、数成正比，因此，我们将每一个 Server 所负责的玩家的个数当成其负载的重要指标。2、负载平衡机制在虚拟世界中，在非常多玩家的情况下，单一的 Server 必定会导致负载过重的现象，因此 Multi-Server 的架构无疑是必须采用的解决方式，但是前面我们已经讨论了Multi-Server 负载平衡机制的优缺点，其中较为有效的是动态的分配地图至服务器，下面我们讨论如何实现这种机制。首先我们必须解决如何切割游戏地图的问题，以及切成多少等分，因为这些将影响到在此机制下实现整个系统的效率。我们考虑的原则有一下几点：1.尽量分散玩家到各个 Server 上。2.尽量较少玩家间的跨 Server 的
11、信息传送。3.尽量避免玩家因为在地图上的位置移动而必须更换 Server。其中第一点是为了平均分摊 Server 的负载，第二点是为了减少 Client 间通讯的时间成本，第三点是为了减少 Server 间玩家资料的转移次数。首先我们必须将地图切成跟 Server 个数相等的分数，使得每个 Server 至少有一份地图，然而因为玩家会在地图上移动，因此若每个 Server 负责一份地图，那么时间一久，必会导致负载开始不平衡。另一种方式是将地图切成若干个小等分，然后透过合理的方式将每个小等分分散到各个 Server 上。当然，和上述情况一样，时间一久仍会产生负载不平衡，然而这时候我们可以将负载太
12、重的 Server 上的一部分地图片段再转移给其他负载较轻的Server 上去，以达到负载平衡的目的。转移的时机是以 Server 的负载是否超过某一临界值，而转移的对象是可采用 random polling 的方式，也就是询问相邻的 Server 负载情况如何，是否可以接受额外的负载。其次目前 Multi-Server MMORPG 大多采用将地图切割成正方形，然而应为正方形区域共有东、西、南、北、东南、东北、西北、西南等八个相邻的区域，如此会正佳玩家因为移动而转换区域的机会，因此另有系统采用正六角形切割，然而这种切割虽然相邻的区域减少到六个，但是其切割方式较为复杂，并且判断玩家位于哪个区域
13、也较为耗时。另一可行方式是采用正三角形的切割，此方式的优点是切割方法和判断位置区域的演算法均较正六角形简单。但是以上切割方式都有一共同的缺点，就是他们都为考虑到游戏地图的内容，也就是说不论地图的任何角落皆采用同样的切割方式，因此会很容易造成某个区域内没有任何的NPC，而另外一个区域内却包含数个 NPC，而拥有 NPC 的区域通常是玩家驻足停留的地方，因此包含数个 NPC 的区域意味这其高负载的可能性较高，未包含任何 NPC 的区域意味着玩家不会长时间停留，大多属于路过性质，因此玩家转换 Server 的可能性便会较高。为了解决上述切割的缺点，我们试图使用与地图内容相关的切割方式，我们以每个NP
14、C 为中心来切割地图区域，是的每个区域仅含有一个 NPC，并且为避免玩家因暂时移动而跨出区域，我们希望每个区域中的 NPC 和其他的 NPC 要有适当的距离。这里提供参考的分割方式如下:首先定出所有 NPC 的所在位置，然后对于每一个 NPC和其他各个 NPC 间各画出一条垂直平分线，最后整理这些分割线而成的一个包围一个NPC 的区域。该区域所形成的多边形中的一个边，即是该 NPC 和他的临近 NPC 间的等距离分割线。事实上，这些多边形区域的所有形成的图形是计算几何中的所有的 Voronoi diagram，而各个区域称为 Voronoi polygon。Voronoi diagram 的正
15、式定义如下：我们给定一个 N 个点的集合 S ，对所有属于 S 中的任意连个点 Pi 和 Pj，PiPj 线段的中央垂直分割线将平面分割成连个半平面，包含 Pi 的半平面我们以 H（Pi,Pj）表示之，则所有在平面上靠经 Pi 的所有点所形成的区域 V(i) = ijH(pi,pj)，我们称 V(i)为关于 Pi 的Voronoi diagram，表示成 Vor（S） 。如图Voronoi diagram of NPCs利用 Voronoi diagram 来分割游戏地图可以使得定义一个 NPC 区域的边界与其相邻的 NPC间为相等距离，因而令玩家与该 NPC 互动时不会不经意的离开边界而到了
16、另一个地图区域中，因此答复的降低了玩家在 Server 间转换的可能次数。Voronoi diagram 的建立并不如想象中的那么复杂费时，利用以上提供的演算法可以建立出Voronoi diagram，利用该演算法我们可以在给定 N 个借点的图形中以 O（NlogN）的时间复杂度求的包含该节点的 Voronoi diagram。在下一段中我们将模拟我们的负载分配方法，并且规划如何与其他传统的方法作效能的分析比较，最后将其实现在 open source 的Arriane server game server 上。5、模拟环境和比较分析在本节实验中我们与 micro-cell 切割方式做比较，所谓
17、 micro-cell 是将游戏地图切割成小方格，之后再将这些小方格动态分配到各个 server 上。实验条件如下：1.地图坐标解析度：1000*10002.模式：Voronoi 切割，micro-cell 切割（10*10，20*20 格，配合 NPC 个数）3.4.玩家移动模式：NPC-oriented（朝最近的 NPC 移动，停留 500steps 后离开）5.Total number of steps：500006.Number of servers ：2，4，8，167.Number of players： 1000， 5000， 10000，15000，200008.Number
18、of NPCs：100，400计算超过临界值（threshold）需要做的负载分配(reallocation)的次数(note：每移动一次即检查是否需要做 reallocation，负载分配下限为 player 平均数)实验结果分析：我们分别比较 NPC 个数为 100 和 400 时，Voronoi 切割法和 micro-cell 切割法在player 移动 50000 次中，所发生的负载中心分配的次数。如表 1，表 2很明显的可以看出来，我们所提供的 Voronoi 分割方法是优于 micro-cell 的方法。我们另外将其中四个图标化成图形供比较：我们特别指出的是，除了我们采用 Voro
19、noi 切割方式之外，当在 player 移动的过程中，超过负载的情况发生时，我们首先是选取未超过负载的 servers 中负载比较低者，在将超过负载的 server 中的 Voronoi 区域依附负载人物大小，依序重新分配给低负载者，直到负载降低到 players 的平均数以下为止。至于为什么玩家人数越多超过负载的次数反而减少呢？其原因是在于我们所选定的负载上限值，该值是依玩家人数的不同而不同，我们采用的负载上线值是，因此我们认为若服务器可以提供更多人上线时，其单机的功能应该是更强，否则不应该容许太多人同时上线，因此而调高其负载时的上线，换句话说，我们模拟中不同玩家人数所使用的伺服器的能力是
20、不同的。人数越多，伺服器的能力应越强，否则可能无法负载过多的玩家上线。6实战分析1.硬件架构硬件设备方面，我们将尝试以 6 台 PentiumIV PC 搭配 256Mb RAM，作为操作系统 Windows XP，当成 Server；每台 Server 间以 10/100Mbps 以太网路相连接，Client端硬件不受限制，所有 Client 经由路由器连接到 Dispacher Server，再由 Dispacher Server 咨询 World Database Server 后，将该 Client 上的玩家依其所在的地图分配到负责该地图区域的 Server 上。如图：实验 Multi
21、-user 系统构架图2.软件架构采用 Arianne 这款游戏开发系统，Arianne 是一套开放程序源码的的哦人线上角色扮演游戏引擎，目前 Arranne 可以支援 Linux、MacOS 以及 Win32 系统，它是以C、C+ 、Java 、Python 编制而成，我们可以修改该游戏所放出的源码，加入动态负载平衡的机制来达到我们实验的目的。Arranne 主要包括两大模块程式，分别为 Client及 Server，如下图构架：Arianne 架构图当玩家产生事件时，时间会被传至 GUI，GUI 在获得命令之后再将此命令送至Black Box，再经由路由来改变虚拟世界，之后会回传讯息给其他
22、相关的玩家。3.实验方法在本文中我们在 Arriane 上实验我们提出的负载分配方法，实验中除了我们所提供的以 Voronoi diagram 方好似切割地图做动态分配外，另外加入两种传统方式以作比较，分别是与正方形切割发，切成四等份后，做静态分配给四台 Server 主机；另外一种是将游戏地图切成死的倍数个小正方形格子，然后动态方式分配给各个主机。在灯座警惕啊分配多边形（第一种实验的 Voronoi polygon）或小正方形（第三种实验）单位地图时，我们以该主机上所停留的玩家总数为负载标准，若某 Server 上玩家个数超过某以临界值时，即以 random polling 方式询问其他主机
23、是否接受该主机上的单位多边形或小方格。实验效绩分析将以各个玩家对于 Server 的回应时间之总和来衡量，我们将在后续的计划中分析在不同的负载量下，这三种实验的技校差异性，我们预计当时间增长和负载量增大时，动态分配方式优于静态分配，而同时我们将观察 Voronoi diagram 的分割方式在何种情况下会显示出他的有点。4.结论大部分线上游戏采用单机 Client/Server 架构，在这样的架构下会有一些优势但是也存在一些限制，当有新地图、新消息欲在呢国家至游戏中的时候，只需要在一台Server 上做修改即可，也因为是有一台 Server 控制管理，玩家的资料及游戏的公平行维持较为容易，但是
24、另一方面当线上玩家数目逐渐增多时，Server 端所需要运算能力小雨需求，便会有人数上的限制，若 Server 超过负荷则会导致延迟甚至宕机的现象产生。由于所有资料需要先送至 Server 做完处理后再送出， Server 对外的频宽在不足的情况且多人连线时便会有延迟现象。若以空间分割的方式分配 Server 的权限范围与适当分配每一个 Server 负责的工作，那么便能减少 Server 的负载并支持更多的线上人数。目前有许多机制被用来直言多人线上角色扮演游戏，在本文中我们详细讨论了我们所提出的 Voronoi 切割方式的有点，并且透过模拟的方式，对于我们提出的切割方法和其他的切割方法做多种
25、指标的技校比较，并且以实验证明我们所提出的方法的却由于传统的方法。最后我们尝试透过修改开放源码的 Arianne 游戏引擎来实战我们提出的负载均衡方法。7参考文献1 Christophe Diot, SPRINT ATL, Laurent Gautier, INRIA, “A Distributed Architecturefor Multiplayer Interactive Applications on the Internet”, 1999.2 Eric Cronin, Burton Filstrup, Anthony R. Kurc, Sugih Jamin, “An Efficie
26、ntSynchronization Mechanism for Mirrored Game Architectures, 20023 E. Cronin, B. Filstrup, and A.R. Kurc, “A distributed multiplayer game server system”,UM EECS589 Course Project Report.4 Wentong Cai; Xavier, P.; Turner, S.J.; Bu-Sung Lee “A Scalable Architecture forSupporting Interactive Games on t
27、he Internet”. Parallel and Distributed Simulation, 2002.pp. 54-61.5 L. Gautier and C. Diot. “Distributed Synchronization for Multiplayer InteractiveApplications on the Internet”. Submitted for publication, October 1998.6 Age of King, http:/ Arrianne, http:/www.arianne.cx/8 Hlaf-life, http:/ Ultima O
28、nline, http:/ - Terazona, http:/ SDK, http:/.tw/sdk/index.html12 DFC Intelligence, http:/ Franco P. Preparata and Michael lan Shamos, “Computational Geometry”,Springer-Verlag, 198514 Arrianne, http:/ , 200415 Bart De Vleeschauwer, Bruno Van Den Bossche, Tom Verdickt, Filip De Turck, BartDhoedt, Piet Demeester , “Multiplayer game architectures Dynamic microcell assignmentfor massively multiplayer online gaming”, Proceedings of 4th ACM SIGCOMM workshopon Network and system support for games NetGames, 2005
