（计算机软件与理论专业论文）分布式交互媒体的研究.pdf

摘要 随着网络和多媒体技术的迅速发展，目前，以视频和i p 电话为代表的多媒 体流技术已经得到了广泛应用，但用户对媒体交互性的要求也越来越高。分布 式交互媒体日渐成为重要的研究方向，其主要特征就是用户直接与媒体进行交 互。分布式交互媒体在远程教育、分布式虚拟环境、网络游戏等系统中有其广 泛的应用前景。 本文对分布式交互媒体的各种关键技术，包括一致佳控制模型、交互媒体传 输、应用控制模型、交互媒体安全等方面作了深入研究。首先分析了分布式交 互媒体的各种特性，然后深入研究一致性控制模型，讨论了基于本地延迟模型、 本地状态修补机制、状态请求等三层机制保证媒体的一致性，并对本地状态修 补机制作了改进。在研究各种网络传输协议和交互媒体特点基础上，发现r t p 协议并不适合作为交互媒体的传输载体，而是采用了分布式实时传输协议r t p i 作为传输载体。在讨论集中式和分布式控制优缺点后，本文提出了种结合i p 单播和组播技术新的应用控制模型一混合式控制模型，仿真实验表明该模型可 以有效的降低服务器负载、有更好的扩展性。本文还对分布式交互媒体的安全 传输作了探索性研究，讨论了基于密钥树的组播密钥体系和周期密钥重分配方 法在分布式交互媒体安全中的应用。最后针对一种特定的分布式交互媒体应用 共享白板提出了设计和实现方案，并讨论了白板的各种负载格式和重要算法 实现。 关键词：分布式交互媒体、媒体一致性、本地延迟、r t p i 、混合控制模型 a b s t r a c t w i t ht h e r a p i dd e v e l o p m e n t o fn e t w o r ka n dm u l t i m e d i a t e c h n o l o g i e s ， m u l t i m e d i a t e c h n o l o g i e sl i k ev i d e o p h o n e sa n d i pp h o n e sa r ew i d e l yu s e di ne v e r y d a y l i f e ，w h i c hi n t u r nh a si n c r e a s e dt h e u s e r s r e q u i r e m e n t s f o ri n t e r a c t i v em e d i a d i s t r i b u t e di n t e r a c t i v em e d i a ，c h a r a c t e r i z e db yt h ed i r e c ti n t e r a c t i o no fu s e r sw i t ht h e m e d i u mi t s e l f , h a sb e c o m ea n i m p o r t a n t r e s e a r c ha r e ao fc o m p u t e rs c i e n c e d i s t r i b u t e di n t e r a c t i v em e d i ah a v ew i d e a p p l i c a t i o n s i nd i s t a n c e e d u c a t i o n ， d i s t r i b u t e dv i r t u a le n v i r o n m e n ta n dn e t w o r k g a m e s e t c t h i sp a p e rs t u d i e ss e v e r a lk e yt e c h n o l o g i e so fd i s t r i b u t e di u t e r a c t i v em e d i a ， i n c l u d i n gc o n s i s t e n c yc o n t r o lm o d e l ，t r a n s p o r t a t i o no f i n t e r a c t i v em e d i a ，a p p l i c a t i o n c o u t r o lm o d e la n di n t e r a c t i v em e d i as e c u r i t ye t c i tc o i n l n e n c e sw i t ht h ef e a t u r e so f d i s t r i b u t e di n t e r a c t i v em e d i a ；f o l l o w e db yas t u d yo fc o n s i s t e n c yc o n t r o lm o d e l ， c o m p r i s e do fl o c a ll a gm o d e l ，l o c a lm e d i a s t a t er e p a i rm e c h a n i s ma n ds t a t er e q u e s t m e t h o dt og u a r a n t e et h em e d i ac o n s i s t e n c y a f t e ra na n a l y s i so fd i f f e r e n tn e t w o r k p r o t o c o l s ，t h i sp a p e rd i s c u s s e st h e u t i l i z a t i o no fr t p ip r o t o c o la st h et r a n s p o r t p a y l o a do f i n t e r a c t i v em e d i a an e w a p p l i c a t i o nc o n t r o lm o d e l a c o m b i n e dm o d e l t h a tc o m b i n e sw i t hi pu n i e a s ta n dm u l f i c a s tt e c h n o l o g i e si sp r o p o s e d t h ee m u l a t i o n e x p e r i m e n t ss h o w t h a tt h i sm o d e c a na l l e v i a t et h es e r v e r sp a y l o a da n di m p r o v e t h e s c a l a b i l i t ya sw e l l t h es e c u r i t yo f i n t e r a c t i v em e d i ai sa l s od i s c u s s e d ，i n c l u d i n gt h e m u l t i c a s t s e c u r i t y a r c h i t e c t u r eb a s e do nk e yt r e e sa n db a t c hp e r i o d i cr e k e y i n g m e t h o d s a f t e rt h ep r o p o s eo ft h ed e s i g na n da p p l i c a t i o nm o d e l so ft h es h a r e d w h i t e b o a r d o n ek i n do fd i s t r i b u t e di n t e r a c t i v em e d i a ，t h ep a p e rc o n c l u d e sw i t ht h e r e a l i z a t i o no fs h a r e dw h i t e b o a r dp a y l o a da n di m p o r t a n ta l g o r i t h m s k e yw o r d s ：d i s t r i b u t e d i n t e r a c t i v em e d i a ，c o n s i s t e n c yo fm e d i a ，l o c a l l a g ，r t p i ， c o m b i n e dc o n t r o lm o d e l i l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： ) 亟趁邀日期：一毕年j 月1 日 、 f 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：导师签名：越一 导师签名：弦! z 型 日期：3 晌咋年3 月y 1 日 电子科技大学硕士论文 1ii1lill 曼量曼曼曼曼曼! 喜皇曼曼曼曼 第一章引言 1 1 前言 网络和多媒体技术的快速发展使得各种多媒体的实时传输成为可能。目前， 以视频和i p 电话为代表的多媒体流技术已经得到了广泛应用，如i p 电话、可视 电话、视频会议等，这些媒体流的传输很多都基于实时传输协议r t p 【l l 基础上。 同时用户日趋增长的需求也促使了其他媒体的发展，同时也要求更多用户间的 交互。用户要求在网络互连时进行更多的交互，而不仅仅限于接收来自服务器 的媒体信息，而是希望能够与其他用户实时交换信息，共同完成任务或游戏。 这一类媒体就是分布式交互媒体，如今众多的分布式虚拟环境和网络游戏都是 这一类媒体的代表。而网络和多媒体的发展对交互媒体的要求也会越来越高。 目前，已经有不少特定的分布式交互媒体的应用开发出来，如n e t m e e f i n g 软件中提供了共享白板允许多人参与会话，都可以实时改变自板的状态，这是 一种离散分布式交互媒体；如网络游戏c s 则允许几十人同时在线进行枪战游戏， 每个用户可以选取一个角色，游戏中人的活动都由各自用户进行控制，这是一 种典型的连续分布式交互媒体。 1 2 分布式应用 分布式交互媒体是一种分布式应用。一个分布式应用系统是一些独立计算 机的集合，但是对特定应用用户而言，系统就像一台计算机一样，分布式应用 通过网络进行通信。与分布式系统区别的是，从硬件和操作系统角度来讲，每 台计算机都是自主的；从特定应用来讲，用户将这个系统看作是一台计算机。 分布式应用并不要求各台计算机拥有分布式操作系统，而是仅仅要求各台 计算机通过网络能够实现通信，特定的应用程序将各台计算机连在一起，针对 这个应用来讲，这个系统是统一的系统，而对于其他应用，各用户的计算机依 然是各自独立的。 以下我们不再区分系统中的各台计算机是普通p c 还是服务器，也不再区分 各计算机是否有相同的操作系统，但假定分布式应用中的计算机都有自己的 一一 电子科技大学硕士论文 c p u 、内存、外设和终端，且都可以通过计算机网络与其他计算机进行通信。 1 3 分布式交互媒体的概念与特征 1 31 交互媒体的概念 交互媒体，是指媒体状态可以对应于用户的交互操作而发生变化，它包括 共享白板、分布式文本编辑器、分布式虚拟环境、多人网络游戏等。但不包括 音频和视频，因为他们是非用户事件相关的。而分布式交互媒体就是分布式网 络上的某个用户媒体状态可以被其他用户的操作而改变，各个用户的媒体状态 应该是保持一致的，即某个用户做出了改变本地媒体状态的操作，其他用户的 媒体状态也应作相应变化。 为了更好的理解分布式交互媒体的概念，可以使用两种标准来区分媒体类 型，这种区分方法首先是由m a u v e 2 】等人提出来的。 第一种机制是根据媒体是连续还是离散的。离散媒体的特征是媒体状态独 立于时间的流逝，如共享静止图像或共享白板等。虽然离散媒体可能改变状态， 但只依赖于外部事件，如用户在白板上画图等。而连续媒体的状态可随时问的 流逝而改变而非事件，视频、音频都属于连续媒体。 第二种机制按媒体是否是交互的。非交互媒体的状态只依赖于时间的流逝 而不会对外部事件做出反应。典型的非交互媒体是视频、声音和图像。交互媒 交互媒体 共享白板 翁布式模 共享图片 囊耨输视 非交互媒体 图1 - 1媒体分类 体的特征是状态可被外部事件所改变，如分享自板和分布式虚拟环境就是这种 连粪体 离散媒体 电子科技大学硕士论文 媒体。 离散分布式交互媒体是媒体状态只会由外部事件引起的交互媒体，连续分 柿式交互媒体则是媒体状态既可能由时间推移导致状态变化，也可能由外部事 件引起变化。这就意味着各个用户需要一种统一的时钟机制来确定时间的变化， 出于连续分布交互媒体要求概括了离散交互媒体，除了特别注明，在满足两者 要求的基础上简称为交互媒体。 由此可见，交互媒体与非交互媒体的一个很重要的区别是交互媒体是多维 状态空间的，影响状态的即可能是时间，也可能是外部事件，包括分布式网络 的不同应用用户，可能有多个发送源。而非交互媒体的状态空间是线性的，如 视频和音频只随时间流逝而改变，发送源也只有一个。 1 3 2 交互媒体的特征 在分布式交互媒体中，由于参与会话的每个用户都可能改变用户状态，带来 了新的要求。各个用户看到的媒体状态应该是一致的，用户操作需要在特定时 间点及时执行，一般用物理时钟的时戳来表示这一时间点。为了保持各个用户 状态的一致性，需要找到所有操作的正确顺序。由此带来了几方面的要求： 状态的一致性。交互媒体要求特定时刻各个用户的媒体状态是一致的。如果 不一致，可能会导致错误的发生。而各个操作到达各个用户的时延是不同的， 如本地操作生成后可以立即执行，时延为0 ，而到其他用户的各个时延也存 在差别，因此需要一种机制来进行媒体状态一致性的控制。 事件的有序性。各个用户随时随地都可能改变媒体状态，这些操作有一个执 行顺利的问题。仅仅按照本地收到的操作次序进行排序并不能保证媒体一 致，因为同样一个操作，传输时延并不相同。例如本地操作生成后可以立即 执行，而到达其他用户节点却经历一个时延，如果按照收到操作的先后执行， 会造成各用户的状态不相同。 时钟的同步。对于连续媒体，每个事件都有一个特定的执行时间，而各个用 户的本地时间可能是各不相同的，因此需要一种机制来统一，可以采用两种 策略：1 ) 一秭所有用户都采用用特定用户的本地时阗；2 ) 一种是使用时钟 协议来统一各个用户的物理时钟。 传输的可靠性。每个参与者最后都知道远端引起的状态变化，如果用户晚于 电子科技大学硕士论文 操作执行时刻收到操作消息，则叫做操作迟到事件，这类事件的发生意味着 可能发生状态不一致，因此消息的传输需要一定的可靠性。且如果出现媒体 状态不一致状态，则需要提供一种机制来修复不一致状态。 在线加入用户。分布式交互媒体的状态并不仅仅依赖于单个发送源，因此并 不能像音频或视频一样向发送源请求当前状态，而且在加入过程中其他用户 可能依然会发送消息改变媒体状态，因此需要一种机制能够向晚加入提供状 态信息，也能将新发生的事件发送给该用户。 1 4 分布式交互媒体的研究现状 目前，国内外已经对不少特定媒体的应用进行了研究，包括了d i s 、 d i v e 、共享白板、网络战略游戏等。 分布式交互仿真( d i s t r i b u t e d i n t e r a c t i v es i m u l a t i o nd i s ) 1 3 j 是军方普遍使用的 仿真系统，利用计算机网络协议将各地仿真模拟器连网，构成在时间与空间上耦 合的虚拟合成环境。人可以随意地与之交互，供参训人员进行全方位的对抗演 练。d i s 系统具有结构简单、容错性好等优点。但也有一些缺点：主要采用广 播传送数据，对网络带宽和硬件要求较高缺乏仿真器间时间同步的功能。 p d u 针对某些特定领域制定，难以扩展使用。目前已经提出了高层体系结构( h l a ) 作为一种仿真应用系统的框架体系标准。 n e t m e e t i n g 是微软开发的多媒体会议系统软件，其中的共享白板就是分布 式交互媒体的一种应用。该软件采用了t 1 2 0 协议，通过抓包实验发现，其采 用的是集中式控制，其数据都通过服务器进行单播转发，采用了t c p 的p u s h 方式。尽管这种方式可以较好的实现同步，但同样存在缺点：单播的扩展性较 差，采用t c pp u s h 方式会对其他应用的网络正常传输造成影响，另外集中式控 制也存在扩展性差、单点失败点问题。 另外还有网络游戏等。 尽管如此，但对于分布式交互媒体，总体上还处于起步阶段，依然没有一个 类似于r t p 的公用传输平台，也没有如h 2 6 x 、g 7 x x 之类的交互媒体传输标准。 众多的应用也是根据自己的应用和媒体特点选择传输方式，控制模型等。因此 虽然有不少专用协议、专用模型被开发出来，但无法相互通用，扩展性、灵活 性方面依然较差。缺乏对通用分布式交互媒体的研究，主要有以下问题： 电子科技大学硕士论文 1 1 1 媒体的状态一致性模型专用，目前很多状态一致性模型一般都是针对特 定媒体提出的，缺少离散交互媒体和连续交互媒体共同适用的方案，而 出现暂时不一致之后的状态修补机制也有待优化。 交互媒体的网络传输，虽然有很多专用媒体协议，但缺乏适应多种媒体 的交互媒体传输协议，导致只能协议专用。 用户的在线加入、随机播放、记录服务等众多交互媒体的通用需求并没 有成熟的方案。 上述问题也是我们进行分布式交互媒体研究的主要动机。尽管不同的媒体应 用有所区别，但分布式交互媒体有其自身的共同特征，对这些特征的研究有助 于我们找到一个比较通用的分布式媒体控制模型、应用程序开发模型，交互媒 体的传输方式等。对这些的研究同时能够扩展分布式交互媒体的应用范围，电 能减小实际开发分布式交互媒体应用的难度，因此有必要对分布式交互媒体做 更加深入的研究。 1 5 本文的组织 以下的论文部分将以如下方式组织。 第二章首先介绍分布式交互媒体的主要组成元素。然后详细讨论了分布式交 互媒体中的一致性维持的方法，重点介绍了本地延迟( l o c a l l a g ) 一致性模型， 然后对本地状态修补机制进行了深入的研究，并对本地状态修补机制( t i m e w a r p ) 作了改进。另外也讨论了修补机制失效后的状态请求控制。 第三章重点讨论了分布式交互媒体的传输，首先针对交互媒体的特性对i p 层的三种传输策略：单播、广播、组播进行了分析，然后讨论了应用传输协议， 我们分析得出了r t p 协议并不适合作为交互媒体的载体，而采用了r t p t 协议 作为交互媒体的传输载体。 第四章对分布式交互媒体的应用模型作了深入研究，在分析集中式和分布式 两种控制模型优缺点基础上，提出了一种结合单播组播的应用控制模型一混合 控制模型，并通过理论分析和实验分析讨论了混合式模型的优缺点。 第五章针对目前网络安全严峻的形势，对分布式交互媒体的安全传输作了研 究。首先讨论了分布式组播模型下的密钥管理体系，采用了密钥树结构和周期 电子科技大学硕士论文 密钥重分配算法，然后对混合式控制模型下的密钥管理作了讨论，提出了在该 模型下的应用方案。 第六章是针对一种特定的分布式交互媒体一共享白板提出的设计和实现方 案。按照功能分为会话控制、通信组管理、媒体状态显示、消息处理、r t p i 协 议及接口等部分，然后分各模块进行了详细设计和部分重要算法的实现。 第七章对本文的研究内容和成果作了总结，指出了本文的创新和特色之处， 同时也指出了其中的缺陷和局限性，为下一步的工作进行了展望。 电子科技大学硕士论文 第二章分布式交互媒体的一致性模型 2 1 分布式交互媒体的组成元素 分布式交互媒体都有自己的状态，例如共享白板的状态定义为共享白板表 示的所有内容，包括图形、文字等。而且每个应用都需要保存该媒体的一份本 地拷贝，对所有用户而言，这些本地拷贝应该是一致的。这就需要控制所有用 户的本地状态的同步，这样媒体状态爿具有一致性。 分布式交互媒体的状态可能被两种因素改变：事件或时间，在两个连续事件 间空隙的状态是完全可以确定的，只依赖于时间。总的来说，由于时间流逝而 产生的状态改变并不需要在用户间交换信息，因为应用程序可以独立计算需要 的状态变化。例如是一个物体飞过屏幕的模拟。 任何不是完全由时间决定状态变化都是由事件引起的，如白板的翻页或游 戏中抢手射击等。事件分为外部事件和内部事件，外部事件是用户交互事件， 如白板翻页。内部事件是媒体状态的非决定性内部变化，如一个随机数的生成。 一旦事件发生，媒体状态就存在不一致的危险，因为各用户的本地拷贝可能不 能同步，因此要求应用程序交换信息，交换内容可以是两种：一种是事件本身， 另一种是更新后的状态信息。 为了提供一种方便灵活的状态处理机制，一般将交互媒体分为几个子构件， 这样整个媒体状态分成多个可控部分，用户可以只改变某个子构件的状态。例 如分布式虚拟环境中的3 d 物体( 房子、车、人等) ，共享白扳中的某个图形、 字等。每个事件都只能影响一个子构件目标，各个子构件应该是相互独立的。 两个子构件a 和b ，如果b 状态只能通过事件才能影响a 状态，则子构件 a 是独立于子构件b 的。对于某些构件本来就是相互独立的，对应的事件也只 能影响此类构件，但在某些场合下，看似独立的两个构件依然会产生联系，考 虑赛车场景，每辆赛车都应该是独立的子构件，正常情况下不能相互影响状态， 但意外事件的发生如撞车、堵塞车道等的发生依然会相互影响状态，因此需要 另外引入额外事件，比如说c o l l i s i o n ( a ，b ) 事件等，这样才能保证符合真实场景。 状态在某些时候可以延续一段时间有效，这段时间最大应该是解析状态后 到下一个陔子构件事件的时间段，例如共享自板的某页状态在没有用户改变状 电子科技大学硕士论文 态的操作前可以一直有效，赛车中的车速在收到另一个控制器事件前可以一直 保持原速不变。 子构件从上次全状态( f u l ls t a t e ) 以来改变的部分，包含了上次全状态和当前 状态间的差别部分，口q 做d e l t a 状态。d e l t a 状态的概念类似于m p e g 编码视频 的p 帧，一个d e l t a 状态只有在以前的全状态也提供时才有效。d e l t a 状态的主要好 处是他们数据量更小，计算比全状态访问方便，对于子构件较大的媒体，尽量 传输d e l t a 状态可以大大减少传输的数据量。 图2 - 2d e l t a 状态 整个媒体一般都有一个不变的背景，叫做分布式媒体的环境，如共享白板的 页框。因为是不变的，所以也不存在同步问题，环境信息仅仅是每个成员需要 接收的。因此尽量增加环境部分数据以减小状态信息。环境和状态的区别是相 对的，例如用户可能选择改变白板的页框，使得环境信息成为状态信息。因此 程序的设计者需要对状态和环境进行判别。 由此可见分布式交互媒体中的主要元素有：环境、状态、事件和应用。只有 状态的传递和事件的传递需要应用层协议。事件和状态传输构成了分布式交互 媒体流的基础，但这种媒体流是与音频和视频不同的：分布式交互媒体存在多 个发送源会话中的所有用户都有可能潜在影响媒体流。应用则负责解释和显示 事件或状态的操作效果，即改变后的媒体状态。 如上所述，用户间交换信息的方式可以有两种选择；状态或事件。事件具 有以下属性； 事件编码较小，一般不超过3 0 5 0 字节。 事件需要及时被交付，如果事件到达其他用户事件已经晚于该事件执行时 间，则就有可能出现状态不一致的问题。离散媒体的要求可能会低一些。 状态具有一些不同的属性： 电子科技大学硕士论文 ! 曼曼曼曼曼舅曼曼皇鼍曼曼皇曼曼曼葛曼曼曼曼曼曼! 皇曼曼皇i i i 曼曼! ! 皇曼皇皇曼曼寰寰曼曼曼曼曼曼! 蔓 状念编码需要更多字节，一个状态的大小可以根据应用不同从一百字节到 几千字节不等。 状态的传输对于交互媒体来说是不可避免的，因为应用初始时必须传输环 境，另外在线加入用户和重同步同样需要传输状态。 2 2 应用程序基本模型 一个分布式交互媒体应用程序可以由四部分构成：1 ) 媒体显示部件，用于 用户端媒体状态显示，2 ) 输入部件，用户与媒体交互的设备，3 ) 网络接口， 用于对等程序实例间的通信，4 ) 状态机，负责子构件的共享状态。 图2 - 3 分布式交互媒体应用的逻辑组成 图2 3 a 显示了用户生成的外部事件直接放入相关子构件状态，向对等用户 传输的是事件消息，但仍然需要定期传输一个子构件的全状态( 如晚加入用户 时) 。图2 3 b 则是新生成的事件直接插入到子构件状态，但传输的并非事件，而 是更新后的子构件状态。这两种方法可能适用于不同的媒体，a 适用于状态信息 较大的媒体，如共享白板；网络游戏则经常使用b 方法，状态空间较小，且全 状态的传输可以弥补因网络丢包引起的状态差错。 交互媒体可以只传输状态而不传输事件，专门有个实体负责更新后予构件 状态的传输，这种方法可以与周期性重传相结合，可以实现应用层可靠性。但 一般用于子构件较小的交互媒体环境中，叫做“状态共享”策略。 屯子科技大学硕士论文 对于状态信息较大的情况下，传输状态就消耗大量带宽和存储空间，此时 应该选择事件和应用相结合的办法，并尽可能的传输事件，状态传输仅仅用在 晚加入用户或不一致状态恢复，这种叫做“事件共享”策略。 2 3 交互媒体的一致性定义 分布式交互媒体根据应用不同可细分为离散交互媒体和连续交互媒体，这 两种媒体有一些区别，连续交互媒体的要求要比离散交互媒体要高，处理模型 也更复杂一些。 2 3 1 离散分布式交互媒体 离散分布式交互媒体是一种完全由事件来改变状态的媒体， 总的来说，离散分布式交互媒体的一致性是找到参加会话者的所有操作的征 确操作序列，使得在所有点来看来，媒体的状态都象是按照特定的次序线性执 行的一样，用因果关系( c a u s a lo r d e r i n gr e l a t i o n ) 和依赖操作( d e p e n d e n t o p e ，a t i o n ) 【4 5 】表示。 【定义2 1 】：因果关系“一 ”：给定两个分别在i 点和，点的操作仇，仇。当且仅当 满足以下条件时，称o a 一 o b 。 1 ) f = _ ，且仉在0 6 之前生成 或 2 ) i ，且o 。萄点的执行在0 6 生成之前 或3 ) 存在一个操作仉，使得仉斗仉，仇呻0 6 。 【定义2 2 】：依赖和独立操作：给定两个操作仉，d 6 ，则有： 1 ) 当且仅当仉寸0 6 时称d 6 依赖于伉。 2 ) 当且仅当两者既不满足仉_ 仇也不满足0 6 一仉，则称仉、仇是相互独 立的( 以o a l l 0 6 表示) 。 一致性有两层含义。 1 ) 收敛性：在所有操作执行完后，离散交互的媒体状态在所有节点上都是一 致的。 电子科技大学硕士论文 2 ) 优先性：如果两个操作有晚斗仇，则在每个节点沈都应在魄前执行。 保证所有用户最后看到的媒体状态是一致的，这是基本的特性，违反这一 特性意味着分布式媒体状态不同导致无效。优先性确保所有依靠事件按次序执 行， 保证离散媒体的一致性可采用严格控制单用户策略，但这些方法并不适用 于连续媒体。因为连续分布式交互媒体不仅仅要求找到操作的正确次序，而且 要求操作正点执行( e o r r e e f p o i n t i nt i m e ) ，所以为离散媒体考虑的算法对连续媒 体是不够的。 例如在连续分布式环境下的两个用户乩和阮，一辆即将通过开关的火车， 该开关可由或任一个开启。考虑火车刚刚到达开关的一刻，u 口操作了这个 开关，则乩处执行了这一操作，但由于时延操作需过一段时间才能到达， 如果操作不能及时到达并执行，则会出现不一致，因为u a 版本到达乩时， 火车可能已经开过开关这一点。 232 连续分布式交互媒体 连续分布式交互媒体是一种既可以由用户操作引起状态变化也可以由时间 推移而变化的分布式媒体。这意味着媒体需要一个物理时钟确定时间的消逝。 我们假定所有参与者的物理时钟是同步的( 误差在5 0 m s 以内，通过n t p1 6 】或者 其他方案) ，而且时钟的校准可以采用调慢或暂停方式，但不能倒退。 在连续分布式交互媒体中，用户操作需要在特定时间点及时执行，一般用 物理时钟的时戳来表示这一时间点。与离散空间的一致性类似，连续媒体的一 致性是找到所有操作的正确顺序，不过附加的一点是在所有节点，所有操作的 执行都像是在特定次序且按时戳准时执行的一样。 【定义2 3 】：物理时钟偏序关系“ ”( p a r t i a l p h y s i c a l t i m eo r d e r i n g r e l a t i o n ) ： 给定两个操作伉和0 6 分别有时戳t 。和t b ，当且仅当t 。( t b 则d 口需在d b 之 前发生，表示为仉 o b 。 【定义2 4 】：同步操作“”( s i m u l t a n e o u so p e r a t i o n s ) ：给定两个操作仇和 0 6 分别有时戳t a 和t b ，当且仅当t 。= t b 称0 。和轨是同步的，表示为o 。“o b 。 【定义2 5 】：时钟全序“”( t o t a l p h y s i e a l - t i m e o r d e r i n g r e l a t i o n ) ：给定两个 电子科技大学硕士论文 操作瓯和0 6 分别有时戳t 。和t b 和决胜点b 。和b b ，当且仅当满足 ( 1 ) t a 町b 或( 2 ) t a = t b 且b a b b 则有仇 o b 。 由此可见，连续分布式媒体的要求已经包含了离散媒体的要求，也更复杂， 因此我们主要考虑连续分布式媒体的一致性。 2 4 分布式交互媒体的一致性 分布式交互媒体的一致性：所有操作在所有节点执行完之后，媒体在所有 节点的状态是完全相同的；对于连续媒体还要附加媒体状态是完全按照物理时 钟( 以时戳表示) 次序执行得到的结果时，称媒体状态是一致的。 2 ，4 1一致性问题的提出 即使是所有用户的操作都成功的传递各个节点，媒体的一致性依然无法保 障，主要难题在于操作的传输都需要一定的网络延迟。在发送点用户可以立即 执行一个操作，而由于网络时延需要过一段时间后才能传到其他节点，这样就 有可能导致远方节点执行该操作延迟，导致状态的不一致。例如：在共享白板 中，两个用户都想改变白板中的球的颜色，第一个用户改成红色，第二个改成 蓝色，如果两者闻延迟较大，则可以发现第一个用户界面的球最终是蓝色的， 而第二个用户界面的球最终是红色的。 总的来说，存在两种方法预防出现这种情况：悲观法和乐观法。悲观法师预 防不一致状态的发生，典型的使用锁定算法或地板控制( f l o o rc o n t r 0 1 ) 以避 免同时冲突操作的发生【”。虽然这些方法是非常有效的，但有一个重大缺点：会 话用户的实际协作受到了一定限制。乐观法允许不一致状态的发生，不是采取 预防的方法而是采用修补恢复的方法【8 1 。然而现有的方法都太复杂，且与应用相 关，出现短期不一致也较频繁。 2 42 暂时不一致避免 如果一个时间戳t 的操作在i 节点没有在t 时间点执行，则这个操作引起了暂时不 电子科技大学硕士论文 致。这种情况经常出现在迟到操作，即，节点的一个操作在时间戳指示时间后 才到达f 节点。暂时不一致可能会导致依赖事件的执行错序，结果往往是视觉噪 声( v i s u a la r d f 如t s ) ( 比如说从一点跳到另一点) 。而且用户可能会针对不一致的 媒体状态采取操作，使之迟到操作的执行导致结果违背用户的本意。即使不一 致状态最后被修复了，仍然存在负面影响： 1 ) 用户已经观察到了不一致状态。 2 ) 应用程序不得不重新计算正确状态，这消耗大量的计算资源。 3 ) 可能会产生“视觉噪声”，即当应用程序恢复到正确状态时，正确 状态可能与观察到的错误状态显著不同，从而导致“跳跃”现象。 所以尽量避免不一致状态发生。 2 4 3 低响应时间 响应时问是指用户发布操作到该操作执行之间的时间间隔，理想状态下该 值为0 。如果响应时间超过了一定限度，用户会感觉到延迟的存在，这会导致媒 体的非自然状态。响应时间的优化和暂时的不一致避免是两个冲突的目标。 图2 - 4 短期不一致v s 响应时间 电子科技大学硕士论文 图2 - 4 a 显示了响应时间优化的例子( 响应时间= 0 ) ，但可以发现只有发布该操作 的用户没有暂时的不一致，其他用户都因为传送延迟存在暂时不一致情况。图 2 4 b 显示了使用暂时不一致优化的情况，这里暂时不一致通过增加每个操作的 响应时间( 根据最大传输延迟) 来避免。只有所有用户都有机会同时执行时才 真正执行。通过在接受队列中暂存直到执行时间的到来。可能有两个问题： 1 ) 发送者和接收者间的时钟偏差是否可以弥补传送延迟? 2 ) 在一个网络包可能丢失的情况下，如何计算一个操作的最大延迟? 第一个问题答案是：当发送者时钟快于接收者时钟时，时间偏差确实可能 弥补网络时延，但这种机制只能在发送者和接收者没有交换他们角色时候有效。 一旦双方角色转换，则会造成更大的时间差，从而导致暂时不一致的出现。 第二个问题是由于网络环境不可靠，所以定义一个时延上限是不可能的。 因为包总是可能丢失。因此我们一般采用了最大平均时延作为操作延迟。因此 在非可靠网络中，只能“减少”短期不一致，完全“防止”短期不一致是不可 能的。 2 5 推算定位 在分布式虚拟环境中( 如多用户虚拟现实环境和战地模拟游戏) ，一种常用 的保证一致性的机制是状态预测和状态传送的结合。在这种方法中，应用程序 知道对象在虚拟环境中的运动趋势，例如以匀速飞行的飞机或一个抛射体，这 种可预测对象行为的能力叫推算定位。 推算定位的每个对象都有一个唯一的控制实体，如飞机是飞行员，控制实 体在目标状态跟预订状态的差距达到一定界限时，就通知对等实体本对象的状 态改变，在偏离事件中，控制实体需要传送该对象的完整状态传送所有对等方。 对等方如果接收到该信息，则忽略以前的老状态使用新的状态用于推算定位。 在不可靠传输网络中，控制体需要隔一定时间就传送这个状态，叫做关键消息。 尽管这种方法有强壮性和可扩展性的优点，依然有它的局限性： 1 )导致相当数目的短期不一致 2 )要求每个操作都必须传送目标状态。这会占用大量的带宽，特别是 目标状态超过一定字节数之后 电子科技大学硕士论文 3 ) 只适用于目标有单个控制器的情况，不适用于合作行动。 在d i s 和d i v e 系统中频繁使用了这种技术，在典型的战场模拟环境中， 相关目标的状态数据是比较小的( 主要是位置和移动速度) ，也相对容易预测。 当一个目标只有一个控制实体时，视觉噪音( 立即采用新状态后导致的跳跃) 可以通过使用优化算法渐进修复到新状态来消除。如，在飞机需要改变改向或 位置时，不是直接采用新状态，而是计算原位置到新位置的线路，而后根据算 法逐渐改变状态，最后到新的状态为止。这种方法对于战略模拟和一些分布式 虚拟环境是可以的，因为这类状态的属性较少，在分布式虚拟环境中也比较容 易计算。但如果交互媒体具有以下属性，就不能使用该方法了。 1 ) 目标状态复杂 2 )目标的下个行动无法从过去行为中推断 3 )视觉噪声无法消除 4 )基于不一致状态的行动是至关重要的。 2 6 本地延迟模型 2 6 1 本地延迟的概念 本地t 垂迟_ ( l o c a l l a g ) 是指用户生成的操作并不立即执行，而是延迟一段时间 后再执行。这意味着操作的执行时戳大于该操作的生成时间，这两者之差就是 本地时延。本地延迟实际是将操作的执行时间从0 延迟到将来的某个时间，加 入的人为时延是发布这个操作到所有应用实例的时间，给所有用户的发布操作 都应该执行时间t 前传送完毕。 如图2 - 5 ，引入本地延迟前，o a 操作由于网络延迟到达其他点的时问不同 从而会导致短期不一致：引入本地延迟后，由于o a 人为延迟执行时间，从而可 s i t e0s i t o o p c m i l ，n d e l a y 电子科技大学硕士论文 n e t w o r k d e l 8 v 图2 - 5 本地延迟引入前后效果 以有较充分的时间内将操作发送到各个用户，并同时执行，从而维持状态的 致性。 本地延迟的实现如下：应用程序将所有本地和远端操作，都插入l o c a ll a g 队列，并按物理时钟进行排序。如果操作优的执行时间戳是t ，则服务线程在 浚时刻执行仉。由于本地延迟的引入，引进了一种新的编程范例。传统的编程 模式是执行一个操作后马上显示新状态，然后创建并发布相应的应用数据单元 ( a d u ) 。使用l o c a l l a g 以后，这个过程变成：创建并发送a d u ，把a d u 插入 l o c a ll a g 队列，等待执行时间到达，然后计算并显示新状态。因此，在l o c a ll a g 中，一旦a d u 被创建，就不再需要区别本地操作和远端操作。采用l o c a ll a g 技 术可以显著的消除短期不一致出现频率1 9 j 。 2 。6 。2 决定本地延迟的值 为本地时延选择一个合适的值并非一件容易的事。增加本地时延会减少短 期不致的出现，但同时也会减少媒体反应灵敏度，因为用户需要在发布这个 操作后需要更长的时间才能看到执行效果。两者间的平衡需要考虑到平均网络 延迟和用户的最长容忍反应延迟。依赖于不同的操作，用户可容忍的最大反应 延迟为5 0 m s 和3 0 0 m s 之间，这对于本地网络和世界范围内通信都是可以接受的， 两者的网络延迟分别为4 0 m s 和3 0 0 m s 。同时需要避免另一种极端：没有短期不 一致出现，但响应时间却高的无法接受。 我们采取三个步骤来决定本地延迟的值 1 )选择预防明显的短期不致而需要的本地延迟最小值 2 )决定适用用户可接受的最大响应时间的一个值 3 )选择一个值作为本地延迟。 一 一 ， ， _ ， ， ，1，。，p， 电子科技大学硕士论文 2 6 2 1 决定本地延迟最小值 本地延迟只有在显著减小所有用户的暂时不一致情况才有效，而且应该对 收发双方都有效。所以一般选取任意两个参与者间的最大平均网络时延作为本 地延迟的最小值。典型的网络时延对局域网是小于1 0 m s ，广域网2 0 一1 5 0 m s ，这 样只有在网络报丢失或者网络拥塞导致网络时延加大时才会出现暂时不一致。 如果两个用户的时钟不完全同步，则需要加入两个时钟间的最大差值，这是必 要的，因为如果发送者的时钟在某接收者的时钟后，则如果不计时钟差，传输 时延加上时钟差可能会导致进场的不一致。使用n t p 6 惦典型的时钟差广域网为 2 0 5 0 m s ，局域网为 1 0 m s 。 2 6 2 2 决定最大可接受响应时间 最大本地延迟值依赖于用户对交互媒体响应时间的忍受程度，这需要依据 生理感知结果，理想状态下有两个决定因素：一个是用户无法察觉到延迟的本 地时延值，另一个是用户可以察觉但可以忍受的本地时延值。使用后者更合理 些，试验表明8 0 i n s 值用户无法察觉，用户可忍受的程度往往依赖于操作，如单 击操作可以为3 0 0 4 0 0 m s 之间，而拖动操作则为1 0 0 一1 5 0 m s 。 2 6 23 选择一个值作为本地延迟 f 常的时候，最小本地延迟值应小于用户最大可忍受延迟，我们可以在其 中选择一个值，这往往需要依赖于其他的机制，如发送f e c 包所需时间或者媒 体要求的灵敏度等。如果不成立则只有权衡了，尽管这种可能性很小，这种情 况下只有降低为用户提供最好逼真度的一些标准。例如共享白板，可以选择 8 0 1 0 0 m s 作为本地延迟初值，然后根据网络拥塞情况动态调整。 2 7 暂时不一致状态的修补 尽管使用了合适的本地延迟，但不能避免暂时不一致的发生。需要一些机 制来修补发生的这种状态。可以有几种方法。 2 7 。1 状态预测和传送 这种方法是状态预测传送方法和l o c a ll a g 的结合：依然采用本地延迟机制， 但在用户发布操作的同时，基于该操作的新状态也立即计算，新状态包括了这 电子科技大学硕士论文 个操作且考虑了操作的时间戳。这个状态也发送给所有参与节点。当该操作执 行的物理时间到来时，远端节点使用新状态作为推算定位依据。当一个节点出 现暂时不一致，但马上被传送过来的新状态代替，纠正了不一致状态。 这种方法有两个缺点：第一是在用户发布操作时就计算新状态，如果在目 标在该时延内还有其他实体要改变该对象状态时该状态就失效了，即这种方法 只使用于单个控制器的对象。第二是每生成依次操作就需要发送一个操作事件 和一个状态，如果对象状态较大则网络负载较大，在操作频繁时，生成的发送 消息也较多，只能适用于目标状态较小，事件操作并不频繁的媒体。 2 7 2 请求状态 这种方法的基本思想：只有在暂时不一致状态发生时才请求发送状态，其 他时候发送操作。当收到操作过时，则需要识别有该目标物体正确状态的参与 者，另外需要保证至少一个参与者能决定该物体的正确状态，一种解决方法是 每个目标只允许一个控制实体，则该控制节点肯定知道正确状态然后回应，控 制节点可以改变但必须保证以前状态的正确性。 这种方法需要复杂的算法决定谁回应状态请求，另外修补需要附加一个状 态的来回。只适用于暂时不一致率较低的情况。 2 。7 。3 本地状态修补t i m e w a r p 技术 2 7 3 1t i m e w a r p 的基本原理 文献 9 】提出了t i m e w a r p 方法，这种方