（计算机系统结构专业论文）构造基于internet的虚拟环境开发平台的关键技术研究.pdf

摘要 捅要 虚拟环境( v i r t u a le n v i r o n m e n t ) 能够满足交互性要求较高的应用需要，它具 有广泛的应用前景。v e d p ( v i r t u a le n v i r o n m e n td e v e l o pp l a t f o r m ) 是一个虚拟环 境的开发平台，通过它可以开发基于i n t e m e t 的虚拟环境应用。 论文主要讨论了实现v e d p 的关键技术。( 1 ) 基于虚拟环境区域划分、信息分 类和用户数据缓存的思想，提出了一种可以支持大用户的网络拓扑结构。( 2 ) 用 户数据缓存采用了本地一致性方法，减少了数据传输，能够灵活地适应于不同带 宽的网络用户，通过用户所在范围的空间选取对已有的无效集协议进行了改进， 进一步减少需要传输数据。( 3 ) 使用三级描述的方法来描述虚拟环境，允许多个 虚拟环境开发者并行地开发虚拟环境的各个部分，最后整合成一个大的虚拟环境 应用。( 4 ) v e d p 采用q o t a 算法，实现了快速的地形跟随。( 5 ) 支持基于空间 交互模型的会话管理，采用i - - c o l l i d e 算法实现了对象交互范围的冲突检测。 其中，提出了一种求相交线段集的算法，把原i - - c o l l i d e 算法时间复杂度降为 o ( n l o g n ) 。 v e d p 提供了内嵌的开发语言( v e d p c ) 并实现了对虚拟环境应用的驱动，这 是为实现v e d p 而进行的主要编程工作。 关键字：虚拟环境开发平台本地一致性地形跟随冲突检测内嵌开发语言 a b s t r a c t a b s t r a c t v e ( v i r t u a le n v i r o n m e n t ) c a ns a t i s f yt h er e q u e s to f i n t e r a c t i v en e t w o r k a p p l i c a t i o n i th a sab r o a da p p l i c a t i o nf o r e g r o u n d v e d p ( v i r t u a le n v i r o n m e n td e v e l o pp l a t f o r m ) u s e dt od e v e l o pv eb a s e do nt h ei n t e r n e ti st h e t a r g e to fm y w o r k t h i sp a p e rm o s t l yd i s c u s s e st h ek e yt e c h n i q u eo f i m p l e m e n t i n gv e d p i ti n c l u d e s t h ef o l l o w i n gs e v e r a lp o i n t s ( 1 ) b a s e do nt h ei d e a so f s e p a r a t i n gr e g i o n ，d i v i d i n gt h e i n f o r m a t i o na n dc l i e n t c a c h i n go b j e c t s ，t h ep a p e rb r i n g s f o r w a r dan e wn e t w o r k t o p o l o g yf o rs c a l a b l em u l t i u s e rv e ( 2 ) v e d pi m p l e m e n t sc l i e n tc a c h i n go b j e c t sb y t h e a p p r o a c hc a l l e dl o c a lc o n s i s t e n c y b ys p a t i a lc u l l i n g ，t h ep a p e ra d v a n c e st h eo r i g i n i n v a l i d a t i o n s e tp r o t o c 0 1 ( 3 ) b yt h em e t h o do ft h r e e - l e v e ld e s c r i p t i o n ，v e d pa l l o wt h e d e v e l o p e r si n d e p e n d e n t l y t od e v e l o po n ep a r to f v ea tl a s t ，a c c o r d i n gt ot h er e l a t i o no f p o s i t i o no f e a c hp a r t ，w ec a nc o m b i n et h e mi n t oal a r g ev e ( 4 ) v e d p u s e st h eq o t a a l g o r i t h mv e r yf a s tt oc o m p l e t et h ec a l c u l a t i o no f t e r r a i nf o l l o w i n g ( 5 ) v e d ps u p p o r t s t h ec o n v e r s a t i o nm a n a g e m e n tb a s e do nt h es p a t i a li n t e r a c t i o nm o d a l ，u s i n gi - c o l l i d e a l g o r i t h mt oi m p l e m e n t t h ec o l l i s i o nd e t e c t i o no fc o n v e r s a t i o na r e a p a p e rg i v e so u ta l l a l g o r i t h mf o rs e e k i n gt h es e to f i n t e r s e c t i o ni n t e r v a l s b yi t ，t h ei - c o l l i d ea l g o r i t h m i sr e d u c e dt oo ( m o g n ) a sap l a t f o r m ，v e d pp r o v i d e se m b e d d e dp r o g r a m m i n gl a n g u a g ea n dd r i v e sv e s a p p l i c a t i o n m a n yc o d e so f v e d p a r eu s e dt oi m p l e m e n tt h e m k e y w o r d ：v i r t u a l e n v i r o n m e n t d e v e l o pp l a t f o r m l o c a l c o n s i s t e n c y t e r r a i n f o l l o w i n g c o l l i s i o nd e t e c t i o ne m b e d d e d p r o g r a m m i n gl a n g u a g e 第一章绪论 第一章绪论 1 1 论文工作 两年前，国内一家著名的在线网络游戏公司在我们研究所建立了一个“虚拟 现实v r ”实验室，致力于网络虚拟环境和多用户交互技术的基础研究。该公司 开发的十几款在线游戏大多基于m u d o s l 0 1 i ( 运行在l i n u x 上) 平台，开发人员使 用l p c ( m u d o s 的内嵌开发语言) 开发游戏。他们多数对l p c 编程都很精通， 但是对m u d o s 的内核机制了解甚少，不能对当前的系统从底层上做进一步的系 统扩展。我当时承担的任务是分析m u d o s 的内核对系统进行了功能扩展( 如 改变对象的调度策略、加入远端数据库连接支持、m u d o s 中间代码加密、c l i e n t 与s e r v e r 通信加密等) 。现在该公司的游戏s e r v e r 使用的就是我改造后的m u d o s ， 运行一直很稳定。 m u d o s 有明显的优点：它是基于对象的；可以使用l p c 方便快速的开发游戏 系统：支持远程在线游戏修改而勿需重新启动m u d o s 系统；高效的内存调度管 理等等。 但是由于m u d o s 是基于文本的，并且使用了简单的集中式结构，客户端程序 以虚拟终端的方式连接在系统上，这限制了m u d o s 的可扩展性，不能用它实现 2 d 、3 d 图形化的虚拟环境。 m u d o s 的这些不足通过对它的简单改造是无法克服的，同时考虑到建立基于 i n t e m e t 的虚拟环境应用具有广泛的应用前景( 除了网络游戏外，可以实现网络教 学、小区智能化管理，工作组合作和虚拟社区等等应用) ，我确定了自己的论文目 标实现一个虚拟环境开发平台v e d p ( v i r t u a le n v i r o n m e n td e v e l o pp l a t f o r m ) ， 在v e d p 上能够开发基于i n t e r a c t 的虚拟环境应用。 构造v e d p 是一个复杂的工程，涉及到的知识领域很多，而国内几乎没有相 关的研究，这是我的工作所面对的困难。我先用了半年多的时间分析m u d o s 的 所有源代码( 5 0 0 0 0 多行) l o t 】，给出了系统框架、功能流程、数据流程等，完成 了全部的技术文档。通过代码的分析，我学会了如何构造一个虚拟环境的开发平 台，包括如何架构一个开发平台，如何实现内嵌的开发语言，如何定义应用与平 台的关系，如何实现对具体应用的驱动等等重要的问题。这为实现v e d p 奠基了 基础。剩下的半年多时间里，论文的主要工作是解决虚拟环境构造中的关键问题 ( 通信设计，环境描述和会话管理等) 。分析比较了当前存在的一些虚拟环境，借 鉴了当前虚拟环境中的许多思想，根据i n t e m e t 的实际，论文给出了v e d p 中关 键问题的设计思想和实现方法。 论文各章的安排如下： 基于i n t e r a c t 的交互式网络平台 第一章：绪论。 第二章：通信设计。给出了v e d p 使用的网络拓扑结构和相关的设计思想， 同时给出了v e d p 部分数据备份的数据模型。 第三章：环境描述和地形跟随。主要描述了v e d p 使用的虚拟环境环境描述 方法和地形跟随的实现。 第四章：会话管理。主要解释了空间交互模型，并且给出v e d p 对它的支持 方法。 第五章：内嵌的开发语言。主要讨论了v e d p 的内嵌开发语言v e d p c 的实 现。 第六章：平台总体结构。给出了v e d p 整个平台的构成，主要讨论了驱动器 的实现方法。 1 2 引言 随着i n t e r n e t 的飞速发展和快速普及，构造基于i n t e m e t 的应用成为了研究热 点。当前的i n t e r n e t 可以说是世界上最大的图书馆，我们可以从中获取几乎所有 需要的信息：世界各地的新闻、技术资料、科技动态、经贸信息，使我们充 分的体验到了网络带给我们的便利。但是，i n t e r a c t 不应该仅仅是一个资料库，它 更应该成为我们和世界联系的工具，成为我们和其他人交流的场所。现在人们在 i n t e m e t 上的交互还处在一个比较初级的阶段，主要是通过e m a i l 、聊天程序和别 人交流，随着网络的发展这样的一些应用难以满足人们的需要。i n t e m e t 上需要交 互手段丰富、参与性和真实性更强的应用。虚拟环境( v i r t u a l e n v i r o n m e n t ) 能够 满足这种交互能力更强的应用需求，伴随着网络的发展，虚拟环境的应用将成为 一个新的应用领域并且将变得越来越重要。 所谓虚拟环境就是在计算机网络上建立一个虚拟的空间( 社区) ，网络用户作 为这个空间( 社区) 的一员加入到其中，每个用户有一个代表自己的标志对象( 符 号、图形、图像等) ，用户通过输入设备即可以操作它们在虚拟环境中活动，也可 以根据具体的环境和其它用户进行各种交流。相对于当前i n t e m e t 上的一些简单 应用，虚拟环境提供更强的交互能力和更强的真实感，使网络用户有一种“生活” 在网络中的感觉。 出现在8 0 年代初期的m u d ( m u l t i u s e rd u n g e o n s ) 是最早的虚拟环境，它 是基于文本的，网络用户通过各种字符命令和其它用户交互，用户“生活”的虚 拟空间通常由“房间”构成。在i n t e r n e t 上m u d 得到了广泛的应用，当今存在的 m u d 数以百计( b b s 也是m u d 的一种变型) ，它们中的大多数都对早期的m u d 进行了扩展i j 5 j i ”】。 s i m n e t l 4 5 1 ( 仿真器联网) 可以说是大范围、图形化虚拟环境的鼻祖，它最 第一章绪论 大的一次试验支持了8 5 0 个仿真器实时交互。s 1 m n e t 是比较成功的，它使用的 交互仿真协议后来发展成分布式交互仿真( d i s ，d i s t r i b u t e di n t e r a c t i v es i m u l a t i o n ) 标准。遗憾的是s i m n e t 要求一个实时网络( 最大延迟为2 5 0 m s ) 。 n p s n e t l 2 4 是采用d i s 协议开发的基于多播网络、支持3 d 的虚拟环境。网 络用户作为一个p l a y e r 加入其中，既可以活动也可以和其它用户进行多种形式的 交互。系统周期地把p l a y e r 的位置更新等信息通知其他网络用户，使用 d e a d r e c k o n i n g 算法【1 2 l 来减少需要发送的更新信息。不过，d i s 协议本身的一些问 题限制了n p s n e t 的可扩展性i ”1 。 d i v e ( d i s t r i b u t e di n t e r a c t i v ev i r t u a le n v i r o n m e n t ) 4 6 1 是一个用来开发多用户 虚拟环境的软件平台。由s i c s ( t h es w e d i s hi n s t i t u t eo f c o m p u t e rs c i e n c e ) 开发完 成。d i v e 可以让多个参与者在一个3 d 空间中移动，可以看到并和其它参与者交 互。d i v e 采用点到点( p e e r - t o p e e r ) 的完全的分布式结构，各个参与者采用虚拟 环境数据完全的备份的方法。它可以支持2 0 个用户在广域网( w a n ) 上活动， 延迟时间低于2 0 0 m s 4 q 。用d i v e 开发的应用包括虚拟战斗、空间交互模型、虚 拟代理和多模式交互等【1 3 。 r i n g ( r e a l - t i m ei n t e r a c t i v en e t w o r k e dg r a p h i c s ) 1 9 1 中给出了一种可以支持 多个用户交互的混合式网络模型，它可以用来构造支持大用户的虚拟环境。 m a s s i v e ( t h em o d e l ，a r c h i t e c t u r ea n ds y s t e mf o rs p a t i a li n t e r a c t i o ni nv i r t u a l e n v i r o n m e n t ) 【4 刀是一个试验性质的分布式协作的虚拟现实系统，它使用邛多播 实现用户间的通信，希望实现支持大用户的虚拟环境，它提出了基于空间交互模 型p 别管理会话的思想。 s p l i n e ( s c a l a b l ep l a t f o r ml a r g ei n t e r a c t i v en e t w o r k e de n v i r o n m e n t s ) 3 4 1 是一 个实现多人交互虚拟环境的软件开发平台。s p l i n e 已经用来开发了钻石公园 ( d i a m o n dp a r k ) 虚拟环境，公园中的游客可以骑着自行车在公园中参观并且可 以和别的游客交互。s p l i n e 中的所有用户的交互都发生在世界模型( w o r l d m o d a l ) 中，世界模型包括了虚拟环境的所有对象，所有的用户程序都建立在世界 模型上，在每个客户端有一个世界模型的备份。s p l i n e 提出了使用区域划分构 造虚拟环境的方法2 1 1 。和d i v e 、m a s s i v e 一样，s p l i n e 也是一种基于多播网 络的分布式虚拟环境。 当前存在的有代表性的虚拟环境应用都提出了一些新的方法，它们中的多数 是比较成功的。它们基本上都采用分布式结构，使用多播网络在对象之间传递更 新信息，遗憾的是它们基本上都不能应用到i n t e m e t 上，主要原因是： ( 1 ) 在i n t e r n e t 上基本无法使用多播通信。 ( 2 ) i n t e r n e t 上网络用户的资源差别很大，并且i n t e r n e t 上的虚拟环境应用 一般要求数据的统一管理，所以采用分布式结构不太合适。 基于i n t e r n e t 的交互式网络平台 ( 3 ) i n t e r n e t 上的网络延迟时间是很不稳定的，不能对网络提出要求( 例如 限制最大延迟时间) 。 所以，根据现实情况构造基于i n t e r n e t 的虚拟环境应用是非常必要的，开发一 个虚拟环境开发平台用它来开发具体的虚拟环境应用是非常有意义的，这也是我 工作的目标。 1 3 面临的问题 构造基于i n t e m e t 的虚拟环境开发平台主要需要解决两个大的问题：如何构 造i n t e m e t 上的虚拟环境；向虚拟环境应用提供什么样的开发环境以及如何驱 动开发好的虚拟环境应用。 构造i n t e m e t 上的虚拟环境首先需要考虑的就是虚拟环境的通信问题。通信问 题主要需要考虑下面是几个问题： ( 1 ) 网络带宽。 网络带宽决定了虚拟环境可以提供的服务，如果需要支持多用户、视频，音 频和3 d 模型，则系统需要比较大的带宽。i n t e m e t 上网络用户的带宽差别比较大， 虚拟环境应该根据网络用户的带宽提供相应的服务，这种思想体现在 2 3 1 1 3 2 1 1 4 1 】 等许多论文中。如何向不同的用户提供不同的服务是构造i n t e m e t 上虚拟环境需 要解决的问题。 ( 2 ) 拓扑结构。 不同的拓扑结构实现的虚拟环境的可扩展性是不同的，所以虚拟环境拓扑结 构的设计非常重要的。集中式网络结构和分布式网络结构各有优点，如何利用它 们的优点设计适用于i n t e m e t 的虚拟环境拓扑结构是一个关键问题。当前网络可 用的通信方式有单播( u n i c a s t ) ，广播( b r o a d c a s t ) 和多播( m u l t i c a s t ) 。在i n t e r n e t 上广泛使用的是单播的通信方式，广播和多播通信只能用在某一个子网中，当前 的t c p i p 协议不支持在整个i n t e m e t 上的广播或多播通信【5 】【6 1 。虽然可以使用 m b o n e 【“i 在i n t e m e t 上模拟一个多播网络，但实际i n t e m e t 上的服务器基本上都不 支持多播。 ( 3 ) 网络延迟。 网络延迟直接影响到虚拟环境中的交互和其它动态特性。许多虚拟环境都采 用d e a d r e c k o n i n g 算法或者类似的算法去减少网络延迟对虚拟环境的影响，希望 给网络用户呈现一个流畅的虚拟环境画面。i n t e m e t 上网络用户的带宽差别很大， 网络延迟很不稳定，所构造的虚拟环境要能够动态的适应不同的网络延迟。 ( 4 ) 可靠性。 可靠性需要与网络带宽和延迟的需要是矛盾的，高的可靠性会增加网络带宽 和延迟时间，这就需要考虑选择什么样的协议。在i n t e r n e t 上，t c p 是可靠的传 第一章绪论 输协议，u i ) , p 则不是。不过u p d 需要更少的网络延迟时间，它可以实现实时性 要求比可靠性要求更高的一些应用。虚拟环境中传递的信息可以根据应用的不同 采用不同的传输协议。 ( 5 ) 数据模型。 设计虚拟环境的数据模型是构造虚拟环境需要慎重考虑的问题，它对于构造 适合于i n t e m e t 的虚拟环境显得更为关键。当前的虚拟环境存在4 种数据模型： 统一备份模型( s i m n e t ) 。所有用户备份整个虚拟环境模型，包括虚拟环境中出 现的所有对象，在虚拟环境运行时，用户只需要获取其它对象的位置更新信息； 数据集中模型( m u d ) 。服务器集中管理虚拟环境的所有数据，客户端不需要做 任何数据备份，用户在程序运行期间向服务器索取所有需要的信息：点到点的 分布式共享模型( d i v e ) 。d i v e 用户有一个整个虚拟环境备份，和s i m n e t 不 同的是它备份的数据是动态的，如果某用户产生了新的对象，其它用户可以加入 这个新的备份：o 客户服务器方式的分布式共享模型( b f i c k n e t t 4 8 1 ) 。这种模型 的用户备份了虚拟环境的数据，不过用户的交互是由中心服务器统一管理的【1 ”。 环境的描述和会话管理也是构造虚拟环境需要考虑的问题。环境描述就是怎 样来描述虚拟环境的外貌，构造虚拟环境也就是在网络上实现一个虚拟的空间， 显然，这个空间的描述方法是虚拟环境构造需要解决的问题。构造i n t e r n e t 上的 虚拟环境，虚拟环境的可扩展性是很重要的，虚拟环境必须是一个可以支持许多 用户的虚拟环境。需要实现大用户的虚拟环境，管理用户间的交互就成为一个很 重要的问题，会话管理的好坏直接影响到虚拟环境可以支持的用户数量。 虚拟环境开发平台不需要考虑具体虚拟环境应用的处理过程，但是它需要确 定虚拟环境的构成方式和运行模式。构成方式确定了虚拟环境应用的组织原则， 它说明了具体的虚拟环境应用是如何组织在一起的。运行方式确定了开发平台驱 动虚拟环境运行的流程，可以使用虚拟环境开发平台开发各种应用，不过平台对 它们的驱动过程是一样的，它有一个固定的驱动流程。在平台看来，虚拟环境应 用就是运行在它上面的一些应用程序，开发平台就像是一个管理虚拟环境应用程 序的操作系统，它浓缩了操作系统的许多方面 “】。虚拟环境的构成方式和运行模 式最终都反映在平台提供的开发语言上，开发语言的代码组织方式和平台向开发 语言提供的回调( c a l l b a c k ) 接口函数基本上反映了虚拟环境的构成方式和运行 模式。开发语言开发出来的程序是运行在平台上而不是直接运行在操作系统之上 的，所以开发平台通常提供的开发语言都是解释语言，平台负责解释源程序。 基于i n t e r n c t 的交互式网络平台 第二章通信设计 v e d p 的目标是用来开发i n t e r n e t 上的交互式网络应用，通信是v e d p 的重要 组成部分，通信的设计对v e d p 是非常关键的。在给定的网络资源下，通信设计 的好坏直接影响到网络应用的可扩展性【1 4 l 【1 8 】。 本章首先讨论了现有的一些网络拓扑结构，接着提出了一种适用于i n t e r n e t 应 用，支持太用户和不同的网络连接的网络拓扑结构，同时给出了使用数据缓存处 理更新消息分发的方法。 2 1 网络拓扑结构比较 当前的多数虚拟环境都采用了基于对象的设计方式，虚拟环境被看作对象群的 一个集合。对象分为静态对象和动态对象，静态对象是在程序运行期间状态不变 的对象( 如建筑物) ，动态对象是状态可能改变的对象( 如人物) 。用户通过网络 在虚拟环境中活动，这使得虚拟环境成为一个动态变化的虚拟世界。构造虚拟环 境需要处理的一个重要问题就是如何把系统中的动态对象的更新消息分发给那些 关心这些对象的网络用户，对于i n t e r n e t 上支持大用户的虚拟环境应用，这个问题 显得尤为重要。下面讨论当前的一些网络结构和对应的消息处理方法。 2 11 集中式网络模型 集中式网络模型也就是一般的客户服务器( c s ) 模型( 见图2 1 ) 。在这种模 型中，服务器负责保存虚拟环境的所有对象，收集所有网络用户的更新消息并且 在进行相应的处理后把对象的更新信息发送给用户。由于服务器保存了所有的动 态对象并且客户的所有更新消息都来自服务器，这种模型自然地保证了数据的一 致性，并且它可以方便地进行消息过滤处理，从而有效地减少了更新消息的分发 量。 图2 1 集中网络模型 假设虚拟环境的网络用户数为n ，如果平均每个用户关心的对象数为m ，则所 有用户状态更新一次服务器需要分发m x n 条消息，由于用户交互范围的限制， 通常m 是比较小的常数，它不随n 的增大而增大。集中式网络模型的实现比较简 单，所以当前i n t e n l e t 上的许多虚拟环境应用都采用这种模型1 6 1 。由于服务器需要 第二章通信设计 处理所有的事件，服务器的处理能力成为集中式网络模型扩展的一个瓶颈。对f 图形化的网络应用，冲突检测需要的计算量还是比较大的。网络延迟是集中式控 制的又一个问题，每个对象的更新消息都要经过服务器的中转，这增大了用户间 交互信息传递的网络延迟时间。 2 12 分布式网络模型 在分布式网络模型中，每个用户都保存了虚拟环境的一个完整备份，它和所有 其他网络用户直接通信，如果自己的状态发生了改变，它负责向所有其它用户发 送更新消息，从而维护整个虚拟环境在各个用户上的数据一致性。对于一个运行 在单播( u n i c a s t ) 暖 络上的n 个用户的虚拟环境，如果每个用户的状态更新一次，网 络需要分发，一d 条更新信息【”1 。单播网络上的分布式网络模型见图2 2 。 图2 2 单播的分布式网络模型 多数的系统采用了消息过滤的方法来减少需要发送的消息数量。通常的做法是 把虚拟环境分成小的单元( 如小的六变形) ，每个用户保存各个单元中对象的链表， 当一个对象更新时，更新这个对象的用户计算出可以看见这个对象更新的其他用 户集合，然后把更新消息仅仅发送给这个集合中的所有用户。通常情况下，可以 看见对象更新的用户是全部网络用户的一个小的子集。不过，只把数据发送给一 个子集破坏了虚拟环境中数据的一致性。为了弥补这种数据一致性破环的影响， 当用户每次从一个单元移动到另一个单元时他需要将自己的所有更新信息发送到 其它所有的用户【1 ”。显然，通过消息过滤可以减少需要发送的消息量，但是需要 发送的更新消息还是比较多的。 对于支持多播( m u l t i c a s t ) 的网络，使用分布式网络模型的虚拟环境通常把虚 拟环境的单元和多播地址联系起来，用户每到达一个单元就加入到相应的多播组 1 1 2 1 2 “。这样，用户每次更新对象时，只需要把更新消息发送给所在单元的多播组， 组内的用户也就能感觉到了对象的更新。这样，每个用户就不需要维护各个单元 的对象链表，避免了一些计算，同时，系统需要发送的更新消息也大大减少。如 果有个对象更新，系统需要发送的消息量是o c v ) 。多播网络上的分布网络模型 如图2 3 所示。 分布式网络模型具有比较好的实时性，它的更新消息不需要通过服务器的中 基于i n t e r n e t 的交互式网络平台 转；由于没有服务器，每个用户处理自己的计算集中式网络模型中的服务器处 理能力的瓶颈也就不存在；对于支持多播的网络，分布式结构的可扩展性是比较 好的。 分布式网络模型的主要问题是数据的一致性，由于没有一个集中的数据中心， 实现数据的一致性是比较复杂的；每个用户需要保存虚拟环境的完全备份，这就 对网络上的每个用户的计算和存储能力提出了比较高的要求。这限制了分布式网 络模型在i n t e r n e t 上的应用；多播是很好的特性，它通过网络自动完成了消息的过 滤【2 “，但是i n t e r n e t 上基本没有广泛可用的多播网络，多播通常只能在小的网络( 如 局域网) 上使用，这也使得现有的基于分布式网络模型的虚拟环境应用都局限在 小的网络上，i n t e r n e t 上的应用基本不采用分布式网络模型。 、食、， 、遵 伍沁爿 多播 墅一跨 图2 3 多播的分布网络模型 213 混合网络模型 混合网络模型使用消息服务器管理用户之间的通信。对于每个需要更新的对 象，用户把更新消息发送给服务器，服务器根据更新对象所属的单元，把更新消 息发送给相应的服务器和用户。这种网络模型的主要优点是把客户之间消息传递 的负担转移成服务器与服务器、服务器与客户之间的消息传递。用户把自己的更 新消息发送给服务器，从服务器获取其它对象的更新信息，用户不需要自己负责 把更新信息传递给其它用户。相对于分布式模型，混合网络模型对用户的处理和 存储能力要求相当较低。这个模型对用户的处理能力、存储、网络带宽的需求是 由虚拟环境中的动态对象的密度决定的，不受对象总数的限制，所以它有比较好 的可扩展性i ”1 。 图2 4 混合网络模型 第二章通信设计 r i n g ( r e a l t i m ei n t e r a c t i v en e t w o r k e dg r a p h i c s ) 1 9 1 使用的混合网络模型如图 2 4 所示。为了使用这个网络模型实现通信，服务器必须维护整个虚拟环境中各个 单元中对象的链表，当对象在单元中移动时需要把所有的更新消息发送给各个 服务器，这种实现方法和分布式网络模型中实现数据一致性的方法相似。虽然在 服务器之间采用的是分布式结构，但是混合结构可以达到更好的消息过滤效果， 主要的原因是：服务器的数量比用户数少的多：服务器有更强的处理能力， 并且它不需要处理显示；服务器有更大的存储能力：服务器一般连接在高速 的局域网 1 8 1 。 混合模型结合了集中式与分布式网络模型的优点，它在客户和服务器之间使用 c s 结构，对客户的资源要求比较低，在服务器之间使用分布的结构，它把分布结 构局限在服务器之间，这样可以比较好的实现数据的一致性。同时，由于使用了 多个服务器，很大程度地克服了集中式模型单个服务器处理能力不足的瓶颈。 但是，混合式网络模型存在三个问题限制了它的可扩展性： ( 1 ) 每个服务器需要保存整个虚拟环境的数据，为实现这些数据的一致性需 要在服务器之间发送大量的更新消息。同时随着虚拟环境的扩大，每个服务器保 存和处理整个虚拟环境的数据也会影响的它可扩展性； ( 2 ) 在客户之间没有直接通道。有些数据( 如话音数据) 没有必要经过服务 器中转，它们在客户之间的直接连接不会对虚拟环境产生影响，因此用户间的直 接通道还是需要的； ( 3 ) 对象更新消息都要经过服务器中转这增加了网络延迟。 2 2v e d p 的通信结构设计 上一节比较了当前存在的虚拟环境应用采用的网络拓扑结构，总体而言现在 比较适合构造i n t e m e t 上虚拟环境的网络模型应该是混合的网络模型，它对网络客 户的硬件资源和网络带宽要求相对较低，同时克服了单个服务器处理能力不足的 缺陷。r i n g 使用的混合式网络模型取得了不错的效果，但是它还存在一些问题( 参 考2 1 ) 。 在r i n g 混合网络模型的基础上，本节提出了v e d p 的网络模型( 见图2 5 ) ， 并且给出了实现这种网络模型的方法。虽然这个网络模型从结构上看与r i n g 的 结构比较相似，但在分布策略上与r i n g 有较大的差别。这个网络模型主要是基 于虚拟环境区域划分、信息分类和用户数据缓存的思想提出的。 基于i n t c r n c t 的交互式网络平台 i 区域i 的；ii 1 ； i部分数据 ：j： 区域l ；整个； 图2 5 v e d p 的网络模型 2 2 1 区域划分 区域划分是分治法( d i v i d ea n dc o n q u e r ) 在虚拟环境构造中的应用，目的是实 现基于本地的通信。构造基于i n t e m e t 的大用户虚拟环境一个关键的问题就是处理 虚拟环境中动态数据的更新，在一个比较大的虚拟环境中可能存在成千上万的网 络用户，他们需要在虚拟环境中“生活”，如果每个服务器需要保存和处理全部的 这些数据，那么最好的服务器也难以满足应用的需要。r i n g 中的每个服务器需要 保存所有的虚拟环境数据，这实际上已经限制了它的扩展能力。区域划分的思想 出现在 2 l 】 2 2 】中，它使用区域划分的目的是将区域与多播地址联系起来实现消息 的过滤。因为每个用户只关心自己所在区域的对象的更新，虚拟环境被分成小的 区域以后，用户的更新信息只需要发送给自己所在区域的用户，也就是把更新消 息发送到与此区域相关的多播地址组。区域由构造这个区域的程序维护，这个程 序管理所有加入到这个区域的对象。当用户在区域之间移动时，他只需要加入相 应区域的多播地址组。 在v e d p 的网络模型中使用了区域划分的思想，但是在应用上不同于 2 1 2 2 。 v e d p 首先将虚拟环境划分为一些区域，每个服务器管理一个区域，服务器可以看 成是一个独立自治的“服务机构”，它只需要保存自己管理区域内的对象。这样， 在服务器之间没有数据一致性的问题，通常的状态更新信息只发生在一个区域内， 所以在服务器之间不需要传递状态更新消息，服务器之间的数据传输是很少的。 对虚拟环境进行划分并且由单独的服务器进行管理解决了r i n g 的第一个问题， 单个服务器不需要保存和处理整个虚拟环境数据，同时由于区域划分本身就是一 种消息过滤的体现，所以大大的减少了服务器之间的消息传递。 使用区域划分以后，需要解决的一个问题就是挂接于不同服务器的用户之间的 交互问题。虽然在虚拟环境的应用中很少出现不同服务器之间( 也就是不同区域 第二章通信设计 之间) 的直接交互，不过不同服务器用户间的交互能力还是需要的( 例如在整个 虚拟环境中找自己的朋友，而你和他不在一个区域内) 。如果没有服务器问的通信 能力，整个虚拟环境就不是一个完整的应用，而是许多应用的集合。v e d p 把所有 的服务器放在一个局域网( 如以太网) 内，服务器之间使用广播( b r o a d c a s t ) 进行 通信。 v e d p 使用用户服务器u s e r s e f v e r 保存虚拟环境中所有注册用户的信息( 包括 用户名，密码等) 。用户在注册成为虚拟环境的用户以后，他的信息被保存在 u s e r s e r v e r 上，当用户连接加入到莱区域时，管理这个区域的服务器首先通过 u s e r s e r v e r 上的数据验证用户身份，然后取出用户以前的记录初始化用户对象，这 样用户就可以延续以前的属性值在虚拟环境中继续“生活”。 当用户在从一个区域间移动到另一个区域时，用户和新的区域服务器建立t c p 连接( 各个区域服务器的u d p 端口是约定好的，不需要连接) ，用户对象也就从 当前服务器转移到相应区域的服务器，这个连接的转移过程对于用户是透明的。 由于每个服务器管理的虚拟环境区域一般是一个比较大的虚拟空间，用户在服 务器间的移动频率是比较低的，所以，每次区域间的移动采用重新连接服务器的 方式对虚拟环境应用没有大的影响。当用户离开虚拟环境时，用户的当前状态数 据被记录到u s e r s e r v e r ，作为用户下次进入虚拟环境时的初始化数据。 22 2 网络信息分类 许多虚拟环境应用的个重要不足就是没有对虚拟环境中需要传递的网络信 息进行分类。在【2 3 】提出了将网络信息进行分类的想法。在v e d p 中采用了网络信 息分类，将网络信息分为对象信息( o b j e c ta t t r i b u t e ) 和用户数据( u s e rd a t a ) 两类， 它们各自的特性见表2l 。 表2 1 对象属性和用户数据 对象属性用户数据 可靠性需求高低 共享范围 多个用户通常两个用户之间 带宽需求低高 传输协议t c pu d p 例子对象的各种属性值，用户的操作声频数据，对象的详细图形 命令等。描述。 应用对不同的网络信息有着不同的需求。如果采用同一个通道发送所有的数据 ( 多数虚拟环境采用的方法) ，在实现上要简单一些，但是提供的网络服务不太理 想。v e d p 对信息进行分类，对不同种类地信息采用不同的通道进行传输，这样可 基于i n t e r n e t 的交互式网络平台 以达到比较好的服务效果。为了支持网络信息的分类传输，v e d p 在客户和服务器 之间建立一条t c p 通道和一条u d p 通道。 根据用户的交互范围，v e d p 在可以直接交互的用户之间维持了u d p 通道， 这样能够满足某些应用的需要。比如两个用户之间的话音服务，一方面话音数据 是不需要保存的临时数据，没有必要经过服务器进行处理另一方面语音传输对 实时性要求比较高，因此在进行会话的双方之间使用u d p 传输话音信息是一个比 较合适的选择。随着用户的移动，用户可以交互对象也跟着变化，所以用户之间 的u d p 通道也是动态改变的。在用户移动的过程中，服务器把用户可以交互的用 户的u d p 地址发送给用户。每个用户都维护了一个可交互用户的u d p 地址的链 表，通过链表中记录的地址可以实现用户间的直接通信。v e d p 提供的这个通道解 决了r i n g 的第二个问题。 22 3 数据的缓存 在传统的集中式虚拟环境中，服务器保存了所有区域的数据，客户端一般没有 数据的备份，它每次都直接从服务器获取当时需要的所有数据。显然，这种每次 都去获取当时需要的所有数据是不合理的，因为：，每两次索取的数据间有许 多重复部分，存在较大的数据传输冗余；在虚拟环境中用户和环境的交互是比 较频繁的，大量的数据传输对用户的带宽提出了比较高的要求；同时也增加了 服务器的负担。 当前的虚拟环境应用一般都采用数据备份的方法来解决这个问题，多数虚拟环 境在客户端保存了整个区域的所有对象，当对象更新时服务器将更新消息发送给 客户。这种数据的完全备份方法对客户端的存储能力、网络带宽的要求较高，更 糟的是服务器的负担太重，它向用户发送数据的频率比较高。这种在分布式结构 中经常使用的方法显然不适合集中式网络模型。由于服务器保存了整个虚拟环境 的对象，虚拟环境中的数据一致性得到了有效保证( 这和分布式不同) ，在此基础 上，由于用户每次交互的范围都是非常有限的，他需要保存的数据应该是他近期 内可能交互的对象，所以用户应该保存的数据只是他加入区域的一小部分对象， 这个需要保存的对象子集可以根据用户的当前位置通过预计算来确定。 在v e d p 中使用了数据部分备份的方法，数据的部分备份对于减少网络传输是 非常有效的方法，它是构造大用户虚拟环境的一个关键技术，在下一节给出了 v e d p 实现数据部分备份的方法。 2 3 数据备份方法 v e d p 采用服务器保存完全的虚拟环境数据，各个网络用户缓存所需数据的方 法来减少网络传输数据，从而提高平台的可扩展性。服务器的对象被多个用户节 第二章通信设计 点缓存，这就需要解决一个分布在各个客户端的对象副本的一致性问题。 由于i n t e m e t 上网络用户的资源的差别很大，要实现基于i n t e r n e t 上的真正可 用的虚拟环境，就需要一种比较灵活、适用于不同用户资源的数据一致性协议。 网络用户的在虚拟环境中“生活”，应该由网络用户根据自己客户端能力灵活的决 定虚拟环境中对象的更新速度，这对于建造可扩展的虚拟环境是非常重要的。现 在多数虚拟环境【“】【”1 实现数据一致r 陛方法是当某个用户更新某个共享对象后，这 个用户负责通知( 直接或者通过服务器转发) 所有保存了这个共享对象副本的用 户。在i n t e r n e t 上，网络用户分布在不同的地方，他们的网络带宽差别很大，每次 完成这样的一个数据更新会产生一个比较大的延迟时间，这在交互式的网络应用 中通常是难以忍受的。 在 3 2 1 中提出了本地一致性( l c ，l o c a lc o n s i s t e n c y ) 方法。使用基于l c 的协 议，更新共享对象的用户不需要负责把更新信息发送给其它用户，只有当一个网 络用户需要这个共享对象的信息时，才对这个对象进行更新。本节首先讨论了基 于l c 的协议，然后给出根据v e d p 的应用需要而对它进行的改进。 23ll c 方法 首先定义两个概念：全局视角和节点视角。 v e d p 的服务器包括了其管理的区域的全部对象，把从服务器中可以看到的虚 拟环境定义为全局视角；客户端保存了部分对象的副本，把客户端能够看到的虚 拟环境定义为节点视角。由于所看到的虚拟环境实际上就是指虚拟环境的一个对 象集合，所以全局视角( g l o b a lv i e w ) 就是服务器上的对象集合( 包括了全部的 对象) ，节点视角( n o d ev i e w ) 就是客户端缓存的对象集合。实现数据一致性的 理想情况是： n o d ev i e w 当前g l o b a lv i e w 。 为了达到这个理想情况，某个用户在更新一个对象以后，服务器需要同步的通 知所有包含了这个对象副本的用户更新这个对象。广域网的延迟时间使得这种满 足数据一致性的方法非常费时，所以，构造i n t e r n e t 上的交互式虚拟环境时这种实 现数据一致性的策略不太合适。另外随着用户的活动，用户的交互范围也随之改 变，用户保存的某个对象发生变化时，服务器会通知用户更新