（计算机应用技术专业论文）一种基于元胞自动机的自调节的网络模型.pdf

南京理工大学硕士学位论文 一种基于元胞自动机的自调节的网络模型 摘要 随着计算机网络深入研究和应用，出现了一些新的复杂性现象，如相变、幂率、 自相似性等。为了方便研究，网络实验模拟成为测试和研究网络性质的一种方法，但 代价较大，因此建立各种网络模型来研究网络特性成为一种新兴的研究方向。 元胞自动机( c e l l u l a ra u t o m a t a ，c a ) 理论是针对离散数值计算而提出的，目 前c a 研究和应用越来越深广。研究表明，具有特性和规则的c a 可用来建立计算机网 络模型。本文在n a s e h 模型和袁坚等人模型的基础上，基于c a 建立了一个新的计算 机网络模型：s e l f - a d j u s t i n gn e t w o r km o d e lb a s e d - o nc e l l u l a ra u t o m a t a ，简称 s a n c a 。该模型特点如下：1 ) 基于元胞自动机：把链路中数据包及路由缓存器作为 一个整体进行元胞模型化，根据步骤推进演化。2 ) 可自调节：根据现有的网络协议 引入反馈机制，控制数据元胞传送速度，实现自调节。3 ) 引入随机化参数：更好的 模拟实际网络的额外开销的扰动。在该模型基础上，给出了网络数据包传输的模拟更 新步骤，并对此建立了算法，运用m a t l a b 进行了模拟。结果显示了带宽和负载的变 化使网络流量产生自由流相态和拥塞相态。并分析了相变及相变的标准。结果表明该 模型能有效地、简单地模拟网络数据流传输和相变特性，为更深入研究网络其它特性， 如幂率、自相似性等提供了模型，具有良好发展前景。 关键词：元胞自动机网络模型网络特性相变 a b s t r a c t 硕士论文 a b s t r a c t w i t ht h ed e e p e rr e s e a r c ha n da p p l i c a t i o no fi n t e r a c t ，t h e r ea p p e a rs o m en e w c o m p l e x p h e n o m e n a , s u c ha sp h a s et r a n s i t i o n ，p o w e rp h e n o m e n o n ，s e l f - s i m i l a r i t yp h e n o m e n o n f o r t h ec o n v e n i e n c es a k e t h es i m u l a t i o no fn e t w o r kh a sb e c o m ea ni m p o r t a n tw a yt ot e s ta n d r e s e a r c ht h et r a i t so fn e t w o r k b u ts o m ec o s tm u c h s op e o p l ee s t a b l i s hm a n yn e t w o r k m o d e l st os t u d yt h en e t w o r k , w h i c hb e c o m e san e wr e s e a r c h t h et h e o r yo fc e l l u l a ra u t o m + a t aw a sp r o p o s e df o rt h ed i s c r e t en u m e r i c a lv a l u e c o m p u t a t i o n sa tt h ef i r s t n o w , t h er e s e a r c h e sa n da p p l i c a t i o n so fc a a r ed e e p e ra n dl a r g e r i ts h o w st h a tw i t hi t so w nc h a r a c t e r sa n dr u l e s ，c ac a ne s t a b l i s hn e t w o r km o d e l s t h i s p a p e re s t a b l i s h e san e w o n eb a s e do nc a t a k i n gt h en a s c hm o d e la n dy u a n j i a n sm o d e l f o rr e f e r e n c e a n dw en a l n ei ts e l f - a d j u s t i n gn e t w o r km o d e lb a s e d - 0 1 1c e l l u l a ra u t o m a t a ， s a n c af o rs h o r t t h ef e a t u r e so ft h es a n c aa r ea sf o l l o w s ：nb a s e do nc a i tt a k e s t h ep a c k e t sa n dc a c h ea saw h o l et ou p d a t ea c c o r d i n gt ot h es t e p s 2 ) s e l f - a d j u s t i n g i tc a n c o n t r o lt h er a t eo fp a c k e tt r a n s i t i o nw i t ht h em e c h a n i s mo ff e e d b a c kt or e a l i z et h e s e l f - a d j u s t i n g _ 3 、w i t ht h er a n d o mp a r a m e t e r s i tc a ns i m u l a t et h ed i s o r d e ra sar e s u l to ft h e i n c i d e n t a le x p e n s e so ft h er e a ln e t w o r k s o ，b a s e do nt h es a n c a ，w eg i v et h es t e p so f s i r e u l a t i o na n da na l g o r i t h mo fi t t h e ns i m u l a t ei tw i t hm a t l a b t h er e s u l t ss h o wt h a t t h eb a n d w i d t ha n dl o a di n f l u e n tt h ep h a s e so fn e t w o r kf l o wi n t of r e eo n ea n dc o n g e s t i o n a n dw ea n a l y z et h ep h a s et r a n s i t i o na n dt h ec r i t e r i o no fi t t h er e s u l t sa l s op r o v et h a t s a n - c ac a l ls i m u l a t et h en e t w o r ks i m p l ya n da v a i l a b l y a n di tp r o v i d e sag o o dm o d e lf o r t h ef u r t h e rr e s e a r c ho fo t h e rt r a i t sa sp o w e rp h e n o m e n o n ，s e l f - s i m i l a r i t yp h e n o m e n o na n d h a sa p r o m i s i n gf o r e g r o u n d k e yw o r d s ：c e l l u l a r a u t o m a t a n e t w o r km o d e l n e t w o r kt r a i t p h a s et r a n s i t i o n 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：鳢争年月日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的全部或部分内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的全部或部分内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名： 年月日 南京理工大学硕士学位论文一种基于元胞自动机的自调节的网络模型 1 1 背景 1 绪论 本课题是计算系统性能保持关键技术研究的个分支。 因特网( i n t e r n e t ) 集现代通信技术和现代计算机技术于一身，将各种各样的物 理网络联接起来，构成一个整体，是计算机之间进行国际信息交流和实现资源共享的 良好手段”。在技术牵引和应用驱动下，随着网络的规模不断扩大和结构日益复杂， i n t e r n e t 技术在不断的发展、其规模也在不断扩大，已逐渐演变为一个超分布、超 并行的复杂非线性系统，存在着大量复杂的网络行为。尽管组成网络的元素不同、各 类网络有其自身的复杂性，但却存在某些代表普遍规律的共同性质。网络中节点间的 相互作用常导致集体行为的“涌现”。因而，揭示复杂的网络的性质和行为等特性有 重要的意义。 人们对网络的和用和依赖已经渗透入日常的每个细节，两络的发展与否直接关系 到人类社会的发展。网络的发展，不仅可以从物理硬件上对其更新替换，而且可以从 软件和协议上更好韵管理和控制。前者要求入 f j 把硬件往更大、更快的方面发展，如 存储器更大，传输介质传输信号更快等等；后者则要求人们制定出更好，更合适的方 案，而这一工作的前提。就是要对不断发展的网络有与对俱进的了解和研究。因此， 研究网络及其特性和行为，显得十分重要。在就近几十年来，网络本身的研究已经引 起了越来越多专家的注意，研究成果也越来越丰硕。 这一领域的研究，主要有两种方法f j2 1 。其一是实验的方法。例如，最初人们研究 网络所用的解决方案是严格的、静态的。是从真实的计算机网络中得到实验数据来分 析网络。这样的研究不仅复杂，而且实验数据往往不准确，而且又是我们根本无法完 全控制的网络。另一个方法就是建立一些计算机网络模型，然后通过计算机来模拟它， 从而分析网络。网络模型是对真实网络的一个建模，通过把真实网络中实体的抽象化， 在个模型中模拟网络的运行。显然，这样做更有利于我们改变网络的一些参数，从 而研究这些参数对网络性能的影响，以及更好的研究网络的一些特性。因此，用网络 模型来模拟网络。可以使研究网络更方便、更具体、更具可视化。现在，网络模型是 研究网络管理解决方案的一个基础部分。 文献【8 1 提到，在1 9 5 9 年，e r d o s 和r e n y i 提出了随机网络的e r 模型，概括出t _ - 个网络特征：( 1 ) 聚集系数小；( 2 ) 均路径小；( 3 ) p o i s s o n 度分布。但是大量真 实网络的经验结果显示出高聚集系数、小平均路径，同时涌现出p o w e r l a w 成分布， 这些结论与e r 模型的p o i s s o n 分布背离。1 9 9 8 年w a t t s 和s t r o g a t z 在e r 模型基础上对比 真实网络提出了小世界模型( w s ) ，也指出了网络的一些特性。之后，b a r a b a s i $ 口a l b e r t 领士论文 ( b a ) 研究了包含w w w 在内的大型网络拓扑，发现决定真实网络演化的两个基本因素 是生长性和优先性，这两个因素导致网络遵从p o w e r - l a w 度分布。基于这个特性我们 叫它做s c a l e f r e e 网络( s f ) 。由于b a 模型受到广泛关注，许多研究者纷纷提出扩展 模型希望能够模拟真实网络，被广泛接受的推广b a 模型有：( 1 ) d o r o g o v t s e v - m e n d e s s a m u k h i n 模型( d m s ) ；( 2 ) k r a p i v s k y r e d n e r 模型( k r ) 。在1 9 6 9 年，s t u a r t k a u f f m a n 就建立y n - k 模型来描述网络的一些动态特性d g t , a t l a w n i c z a k 等入建立了 p s n 模型，利用离散事件的算法模拟模型，来研究网络大小、连接拓扑结构和路由算 法等对相变的影响【l5 1 。又在1 9 8 1 年，l i n s e n m a y e r ，g l e n nr o s s 根据网络元素和参数 设计了c o m p n e t 模型。之后，人们又建立网络业物流模型来模拟研究网络。现有的业 务流建模研究成果中，p o i s s o n 模型是最为经典的，如最为经典的e o i s s o n 模型，但是 随着发展，它已不能真实地反映出网络流量，尤其是在大尺度下的特性，特别是他已 经不能反映出网络流量的自相似性了。 一系列的网络模型的建立，说明了建立模型是研究网络的很好的方法；而模型的 不断发展，我们可以看出用来观察网络的静态行为和代表网络组成的有限状态的传统 的网络模型，已经发展到了可以动态更新行为和状态的智能网络模型。 因此，运用网络模型研究计算机网络及其特性是一种比较好的、行之有效的方法。 本文也正是采用了这种方法。 1 2 元胞自动机的发展 文献【1 】【2 】指出，元胞自动机( c e l l u l a r a u t o m a t a , 简称c a ，又称细胞自动机或点 格自动机) 的发源可以追溯到图灵( a m t u r i n g ) 和冯诺依曼( v o n n e u m a n n ) 的 数值计算的开端甚至更早。2 0 世纪4 0 年代，在著名的“m a n h a t t a n 工程”开展过程中， v o nn e a m a n n 受数学家兼物理学家s u l a m 思想的启发，着手探讨自增殖系统( s e l f - r e p r o d u c i n gs y s t e m ) 的逻辑性质，进而发展了c a 理论与方法。 自从v o nn e u r n a n n 提出了元胞自动机模型之后，其研究一宜停滞了十余年，直到 1 9 7 0 年剑桥大学的数学家j h c o n w a y 编制了个名为“生命游戏( 1 i f eg a m e ) ” 的游戏程序后才再次掀起。而“生命游戏”的本质思想就是通过几条简单的规则组 合，使元胞在网格中运行、演化，可以产生变化莫测的复杂圈式1 2 】。从八十年代起， 元胞自动机的理论研究出现了新的进展，进入了热潮时期。科学家们成功的利用元胞 自动机模型在其简单规则下伴随着分形、复杂性理论、混沌和计算机图形学的兴起， 快速的成为了非线性前沿科学的重要分支领域，并成为了研究复杂系统的重要工具。 使得c a 理论成为一种应用技术不断发展，逐渐渗透进了其他学科。 在元胞自动机的发展过程中，科学家们构造了各种各样的元胞自动机模型。其中， 2 南京理工大学硕士学位论文 一种基于元艟自动机的自调节的网络模型 以下几个典型模型对元胞自动机的理论方法的研究起到了极大的推动作用，因此，它 们又被认为是元胞自动机发展历程中的几个里程碑们。 ( 1 ) s w o l f r a m 和初等元胞自动机 ( 2 ) j c o n w a y 和“生命游戏” ( 3 ) 格子气自动机 ( 4 ) l a n g t o n 和“能自我复制的元胞自动机” 经过近5 0 年的发展，元胞自动机已经被广泛应用于各个领域，被认为是分析复杂 系统的重要工具。目前。元胞自动机已经开始在复杂性研究、计算机科学与技术、数 据处理、模式识别、人工智能和固体中动力学问题等诸多领域内得到了广泛的应用， 展现了令人瞩目的研究前景【2 1 。 本文正是要运用元胞自动机，对具有复杂非线性的网络建立模型，进行研究。 1 3 元胞自动机用于网络建模 随着对计算机网络更深入地研究，人们对计算机网络的相变特性产生了越来越多 的注意。元胞自动机理论的不断发展，它所应用的领域越来越广，所涉及的学科研究 也越来越深。大量元胞通过简单的相互作用而构成动态系统的演化。不同于一般的动 力学模型，元胞自动机不是由严格定义的物理方程或函数确定，而是用一系列模型构 造的规则构成。凡是满足这些规则的模型都可以算作是元胞自动机模型。因此其特点 是时间、空问、状态都离散，每个变量只取有限多个状态，且其状态改变的规则在时 间和空间上都是局部的。元胞自动机易于在计算机上模拟各种复杂现象，能够揭示 像交通流这样复杂系统的非线性行为，因此，这一模型越来越多地被应用于网络数据 流的模拟。 n a g e l i 】7 】最初运用元胞自动机研究高速公路上交通流可作为一种整体行为。鉴于 计算机网络和公路交通流有类似之处，他和s e h r e c k e n b e r g 又提出了网络模型。元胞 自动机在计算机网络模型上的应用是新发展起来的，还出于初期起步阶段。在1 9 6 9 年，s t u a r tk a u f f m a n 就建立了n l ( 模型来描述网络的一些动态特性哪l 。 a t l a w n i c z a k 等人建立了p s n 模型，利用离散事件的算法模拟模型，来研究网络 大小、连接拓扑结构和路由算法等对相变的影嗡】。最新韵研究已经将相变的概念用 于解释数据包传输时间的波动f 1 9 】f 2 0 。t r e t y a k o v 等人对一种计算机网络模型相交的 研究，发现网络在临界点附近处于最有效的状态【1 9 1 。恧o h i r a 等人研究另一秘嘲络模 型相变时，也推断路由器的整体行为对相变点的变化起着关键作用【2 0 】。2 0 0 0 年，袁 峰等人利用元胞自动机建立了网络模型，模拟得出了时空图，对网络内部节点的整体 行为进行了探讨。文献 3 9 通过分析网络节点数据包排队长度在空间上的互相关函 绪论 磺士论文 数，发现节点排队长度的互相关特性中存在着明显的相变现象，并且在临界点附近其 功率谱有一致的幂律特性。文献 3 9 和 7 是相同的一类二维网络模型，利用节点排 队长度来计量的均方涨落函数，研究了网络中节点在时间上的长程相关特性。 一系歹0 的研究都表明元胞自动机也以凭借自身特定的性质和规则，对计算机网络 进行建模，从而来研究网络的特性和整体行为特征。本文在参考了以上这些文献后， 基于对元胞自动机的研究，着手建立c a 网络模型来研究网络的某些特性。 1 4 本文主要工作 作为计算系统性能保持关键技术研究的一个分支本文通过对元胞自动机定义， 相关概念和若干规则的研究和理解，借鉴于元胞自动机的公路交通模型，在研究现有 计算机网络的元胞自动机模型的基础上，建立了一种基于元胞自动机的自调节的计算 机网络模型( s a n - c a ) ，并应用该模型将网络中数据包的传输节拍化和离散化，给出 了网络链路中数据包从业务源端经过路由节点到目的端这一传输模拟过程的更新步 骤。应用此模型，本文研究了网络这一复杂非线性系统表现出的相变特性。 本文在建立了模型之后，提出了基于该模型的模拟网络的算法，实现了对网络链 路上数据包传输的模拟，进而研究了网络的数据包传输特性和相变特性及相变的标 准。最终得出的模拟结果表明，带宽和负载的不同使网络流量产生自由流相态和拥塞 相态。本文建立的s a n c a 模型能简单、有效地模拟网络数据流传输和相变特性，是 一种为更深入研究计算机网络特性的良好的模型。 本文主要工作总结如下： ( 1 ) 对元胞自动机的有关概念、发展和应用进行了研究，分析了已有的基 于元胞自动机的硝络模型，如n a s c h 模型和袁坚等人模型。在此基础 上，提出了一个基于元胞自动机的自调节的计算机网络模型( s a n c a ) ， 目的是利用元胞自动机的徜单规则特性及其它特性，更方便简单地为 具有非线性复杂性的计算机网络建立模型，从而能进行网络模拟，以 有效分析研究一些新的现象和阊题。 ( 2 )在模型中，提出网络模拟的演化更新步骤。运用元胞自动机的离散化 特性，对网络中数据流的传输时间和过程进行离散化处理，给整个模 型的演化以节拍使网络特性的理解和研究更为简单，体现了元胞自 动机模型的特色。同时弓i 进了发送数据包的随机概率，用来代表真实 网络因外界因素而引起的扰动，使模型更好的模拟网络。 ( 3 ) 在模型基础上，提出了个模拟计算机网络数据流的算法，设定了一 系列参数和数值。运用m a t l a b 对算法进行实现，并通过模拟数据的 南京理工太学硬士学位论文一种基于元胞自动机的自调节的网络模型 输入得到了一组的关系曲线模拟结果图。得出了一些影响网络处于不 同相位的因素，并分析了相变及相交标准。进一步理解了网络特性， 为理解网络行为和控制网络拥塞提供了理论研究基础。 1 5 本文的组织结构 本文从元胞自动机的基础理论谈起，通过研究和学习现有的对计算机网络特性的 模型和方法，对比参照于现在已有的用于研究网络的元胞自动机模型如n a s c h 模型和 袁坚等人的元胞自动机模型，考虑到现有的网络协议和实际的控制策略，提出并建立 了基于元胞自动机的自调节的计算机网络模型。目的在于运用此模型对网络流量、相 变等网络本身所固有的一些特性进行研究，从而为探讨网络拥塞的解决提供有利的依 据。 下面是各章内容安排： 第一章是绪论，介绍论文的背景，元胞自动机的发展和现状，着重介绍了元胞自 动机模型应用于研究网络流量和特性的发展情况和已有研究成果，引出了本文的方 法、过程和目的。 第二章阐述了元胞自动机的定义和相关概念及应用，从各个角度解释和理解元胞 自动机的相关理论，并介绍几种典型的和实用的元胞自动机模型，从实际应用角度来 解释和阐述元胞自动机理论。 第三章在参考n a s c h 模型和袁坚等人的元胞自动机网络模型的基础上，提出基 于元胞自动机的自调节的网络模型( s a n c a ) 。并给出了用它模拟网络的演化更新 步骤。 第四章应用s a n c a 网络模螫建立了相应韵模拟算法，并实现了对两络数据传 输特性和不同相位的模拟，对“相交”的临界状态和转换标准进行了分析和研究，探 讨隔络的某些属性和特征。 第五章对全文进行了总结，并展望了今后要开展的工作，提出了进一步研究的方 向。 最后是致谢和参考文献列表。 元胞自动机的理论、模型及应用硕士论文 2 元胞自动机的理论、模型及应用 2 1 元胞自动机理论基础 2 1 1c a 的定义 首先，我们先来了解一下自动机( a u t o m a t o n ) 的概念：自动机通常指不需要人 们逐步进行操作指导的设备。举些生活当中的例子，银行韵自动取款机能够根据人的 些要求，通过响应人工编织的各种编码指令，完成分析、计算和执行命令；全自动 洗衣机可按照预先安排好的操作步骤做自动地运行；新兴的机器人则将自动控制系统 和人工智能结合，实现类人的一系列操作和活动。另一方面，自动机也可被看作为一 种离散数字动态系统的数学模型。例如，英国数学家a m t u d n g 于1 9 3 6 年提出的图 灵机就是一个描述计算过程的数学模型。它是由一个有限控制器、一条无限长存储带 和一个读写头构成的抽象的机器，并能完成一系歹1 j 的指令i 。 元胞自动机是由空间上的各项同性的一系列元胞所组成，是在有限元胞自动机基 础上发展起来的，用于模拟和分析几何空间内的各种现象。它有着宽松的构成条件， 但是作为一个数理模型，他还是有着严格的定义的【2 2 1 。但是由于它是物理学家、数学 家、计算机科学家和生物学家的共同研究的成果，因此，在各个领域的定义也是不尽 相同的。下面给出几种常见的定义1 5 【6 】： ( 1 ) 元胞自动机的物理学定义 元胞自动机是定义在一个由具有离散、有限状态的元胞组成的元胞空间上，并按 照一定局部规则，在离散的时间维上演化的动力学系统。 具体讲，构成元胞自动机的部件被称为“元胞”，每个元胞具有一个状态。这个状 态只能取某个有限状态集中的一个，例如或“生”或“死”，或者是2 5 6 中颜色中的 一种，等等；这些元胞规则地排列在被称为“元胞空间”的空间格网上：它们各自的 状态随着时间变化。丽根据一个局部规则来进行更新，也就是说。一个元胞在某时刻 的状态取决于、而且仅仅取决于上时刻该元胞的状态以及该元胞的所有邻居元胞的 状态；元胞空间内的元胞按照这样的局部规则进行同步的状态更新，整个元胞空间则 表现为在离散的时间维上的变化。 ( 2 ) 元胞自动机的数学定义 美国数学家l p h u r d 和k - c u l i k 等人在9 0 年代初，对元胞自动机分别从集合论 和拓扑学等角度进行了严格地描述和定义。 i ) 基于集合论的定义 6 南京理工大学硕士学位论文 一种基于元胞自动机的自调节的网络模型 设d 代表空间维数，k 代表元胞的状态，并在一个有限集合s 中取值，r 袭元胞 的邻居半径。z 是整数集，表示一维空间，t 代表时间。 为叙述和理解上简单起见，在一维空间上考虑元胞自动机，即假定d = l 。那么整 个元胞空间就是在一维空间，将整数集z 上的状态集s 的分布，记为s 2 。元胞自动机 的动态演化就是在时间上状态组合的变化，可以记为： f ：s i s 毛 这个动态演亿又由各个元胞的局部演化规则f 所决定的。这个局部函数f 通常又 常常被称为局部规则。对于一维空间，元胞及其邻居可以记为s ”“，局部函数则可以 记为： f ：s 寸s 。 对于局部规则f 来讲，函数的输入、输出集均为有限集合。实际上，它是一个有限的 参照表。例如，r ：l ，f 的形式则形似如下： o ，0 ，0 一 0 ； 0 ，0 ，l 卜 o ； 0 ，1 ， 0 一 l ； 1 ，0 ，0 - ) 0 ； 0 ，1 ，1 一 1 ； 1 ，0 ，1 一 o ； 1 ，1 ，o 一 0 ； 1 ，1 ， 1 卜 o 对元胞空间内的元胞，独立施加上述局部函数，则可得到全局的演化： f ( + ，) = ，( 0 ，一，c ：，一，叫+ ，) c 。表示在位置i 处的元胞，至此，我们就得到了一个元胞自动机模型。 2 ) 元胞自动机的拓扑学定义 为描述和理解方便，同样假定维数d 为1 。设s 为k 个符号约有限集。z 为整数 全体的集台，称z 到s 的映射的全体s 2 为构形空间。显然s 。就是用s 中的符号组成 的双侧无限的符号序列的全体。即一维元胞自动机的所有构形的集合。称a = ( a 。a o ah ) 为构形空间中的点。 在s 2 中引进任意两点x 和y 之间的距离 d ( x ，y ) = 占( x y ) 2 州 其中当x ，= y i 时8 ( x 。，y 。) = o ，当x ，y 。时6 ( x 、，y 。) = 1 。然后。在s 2 中可以建 立起开、闭、紧等拓扑概念。 在s 2 中定义移位算子8 为8 ( x ；) = x 。，i z 。若连续映射f ：s z - s 2 产与8 可 交换，即f8 = 8f 。或对任意的x s z 有f ( ( 8 ( x ) ) = 8 ( f ( x ) ) ，则称f 为 元胞自动机。 对予以上定义，我们很容易将它扩展到一个任意维空间，所要傲的工作只是将 s 2 记为s 2 。4 ，s 2 记为s “”1 等，同时对一些描述作相应改变即可。 2 1 2c a 的构成 j i 胞自动机的理论、模型及应用硕士论文 元胞自动机是由最基本的四部分组成的：元胞、元胞空间、邻居及规则。简单讲， 元胞自动机可以视为由一个元胞空间和定义子该空间的变换函数所组成。( 如图 2 1 1 所示) 图2 1 1 元胞自动机的组成 1 元胞( c e l l ) 元胞又称为单元或基元，是元胞自动机最基本的组成部分。元胞分布在离散的 一维、二维或多维欧几里德空间的晶格点上。 2 状态( s t a t e ) 状态可以是 0 ，1 ) 的二进制形式，或是f s 。，s s ，s 。 整数形式的散集。在 实际应用中，元胞都进行了扩展，每个元胞可以拥有多个状态变量。 3 元胞空间( l a t t i c e ) 元胞所分布的空间网点集合就是这里的元胞空间， ( 1 ) 元胞空间的几何划分：理论上，它可以是任意维数的欧几里德空间规则划 分。 ( 2 ) 边界条件：在理论上，元胞空间通常是在各维向上是无限延展的，这有利 于在理论上的推理和研究。但是在实际应用过程中，我们无法在计算机上实现这一理 想条件，因此，我们需要定义不同的边界条件。归纳起来，边界条件主要有三种类型： 周期型、反射型和定值型。 4 邻居( n e i i g h b o r ) 在元胞自动机中，加入演化规则将元胞及元舰空闻弓i 入“动态”系统，这些规则 是定义在空间局部范围内的，即一个元胞下一时刻的状态决定于本身状态和它的邻居 元胞的状态。因两，在指定规则之前，必须定义一定的邻居规则，明确哪些元胞属于 该元胞的邻居。在一维元胞自动机中，通常以半径，来确定邻居，距离一个元胞内的 南京理工大学硕士学位论文一种基于元胞自动机的自调节的婀络模型 所有元胞均被认为是该元胞的邻居。二维元胞自动机的邻居定义较为复杂，但通常有 以下几种形式( 我们以最常用的规则四方网格划分为例) 。见图2 1 2 ，黑色元胞为 中心元胞，灰色元胞为其邻居，它们的状态一起来计算中心元胞在下一时刻的状态。 ( a ) v o n n e u m a n n 型( b ) m o o r e 受( c ) 扩展的m o o r e 型 图2 1 2 元胞自动机的扩展模型 5 规则( r u l e ) 根据元胞当前状态及其邻居状况确定下一时刻该元胞状态的动力学函数，简单 讲，就是个状态转移函数。我们将一个元胞的所有可能状态连同负责该元脆的状态 变换的规则一起称为一个变换函数。这个函数构造了种简单的、离散的空问时间 的局部物理成分。要修改的范围里采用这个局部物理成分对其结构的“元胞”重复修 改。这样，尽管物理结构的本身每次都不发展。但是状态在变化。它可以记为f ：s i t * l = f ( s ，s , t ) ，s 。为t 时刻的邻居状态组合，我们称f 为元腿自动枫的局部映射或局部 规则。 6 时间( t i m e ) 元胞自动机是个动态系统，它在时间维上的变化是离散的，即时间f 是一个整 数值，面且连续等间距。假设时间间距d t = l ，若t = o 为初始时刻。在上述转换函数 中，一个元胞在t + t 的时刻只直接决定于t 时刻的该元胞及其邻居元胞的状态，虽然， 在1 ：- 1 时刻的元胞及其邻居元胞的状态间接( 时间上的滞后) 影响了元胞在t + l 的时 刻的状态。 由以上对元胞自动机的组成分析，我们可以更加深入地理解元胞自动机的概念。 用数学符号来表示。标准的元胞自动机是一个四元组：a = ( l d ，s ，n ，f ) ，这里a 代表 一个元胞自动机系统；l 表示元胞空间，d 是一正整数，表示元胞自动机内元胞空间 的维数；s 是元胞的有限的、离散的状态集合；n 表示一个所有邻域内元胞的组合( 包 括中一c l 元胞) ，即包含n 个不同元胞状态的一个空间矢量，记为： n = ( s ，sz - _ s 。) n 是元胞的邻居个数。s 。z ( 整数集合) ，i 1 ，。n ；f 表示将s “映射到s 上的 一个局部转换函数。所有的元胞位于d 维空间上，其位置可用一个d 元的整数矩阵 z 。来确定。 9 ，j 胞自动机的理论、模型及应用硕士论文 2 1 3c a 的特征 从元胞自动机的定义上分析，可以将元胞自动机的基本特性总结为： ( 1 ) 它是一个有很多离散的格点( 元胞) 组成的系统； ( 2 ) 每个元胞仅与空间局部邻域相联系。 ( 3 ) 每个元胞的状态由其离散或连续值的参数来描述，并且这些参数随时间按 照某种确定的规律而变化。 ( 4 ) 元胞的状态取决于它的邻域。 从元胞自动机的构成及其规则上分析，标准的元胞自动机应具有以下几个特征： ( 1 ) 同质性、齐性。同质性反映在元胞空阀内的每个元胞的变化都服从相圊的 规律，即元胞自动机的规则，或称为转换函数；而齐性指的是元胞的分布方式相同， 大小、形状相同，空问公布规则整齐； ( 2 ) 空间离散：元胞分布在按照一定规则划分的离散的元胞空间上： ( 3 ) 时间离散：系统的演化是按照等间隔时间分步进行的，时间变量t 只能取 等步长的时刻点，形似整数形式的t 0 t 十l ，件2 ，而且，t 时刻的状态构形只对其下 时刻，即t + l 时刻的状态构形产生影响，而t + 2 时刻的状态构形完全决定于t + l 的状 态构形及定义在上面的转换函数。元胞自动机的时间变量区别于微分方程中的时间变 量t ，那里t 通常是个连续值变量； ( 4 ) 状态离散有限：元胞自动器的状态只能取有限( k ) 个离散值( s l ，s 2 ，s k ) 。 相对于连续状态的动力系统，它不需要经过粗粒化处理就能转化为符号序列。而在实 际应用中，往往需要将有些连续变量进行离散化，如分类、分级，以便于建立元胞自 动机模型； ( 5 ) 同步计算( 并行性) ：各个元胞的在时刻”l 的状态变化是独立的行为，相 互没有任何影响。若将元胞自动机的构形变化看成是对数据或信息的计算或处理，则 元胞自动机的处理是同步进行的，特别适合于并行计算； ( 6 ) 时空局部性：每一个元胞的下一时刻t i + l 的状态，取决于其周围半径为r 的邻域( 或者其它形式邻居规则定义下的邻域) 中的元胞的当前时刻t i 的状态，即所 谓时间、空间的局部性。从信息传输的角度来看，元胞自动机中信息的传递速度是有 限的； ( 7 ) 维数高：在动力系统中一般将变量的个数成为维数。例如，将区间映射生 成的动力系统称为一维动力系统；将平面映射生成的动力系统称为二维动力系统；对 于偏微分方程描述的动力系统则称为无穷维动力系统。从这个角度来看，由于任何完 备元胞自动机的元胞空间是定义在一维、二维或多维空间上的无限集，每个元胞的状 态便是这个动力学系统的变量。因此，元胞自动机是一类无穷维动力系统。在具体应 南京理工大学硕士学位论文一种基于元胞自动机的皂调节的网络模型 用中或计算机模拟时当然不可能处理无限个变量，但一般也总是处理数量很大的元胞 组成的系统。因此可以说维数高是元胞自动机研究中的一个特点。 2 1 4c a 的分类 元胞自动机的分类目前尚未有一个统一的标准，但是在基于不同的出发点，元胞 自动机可以有很多分类。其中，最简单和最常用的划分方法是基于维数的元胞自动机 的分类【3 1 。 理论上，元胞自动机是可以任意维数的，但实际上，通常分为： ( 1 ) 一维元胞自动机( 又称为初等元胞自动机) ：元胞等问隔方式分布在一条向两侧 无限延伸的直线上，每个元胞具有有限个状态s ，s s _ s l ，s 2 ，s d ，定义邻居半径r ， 元胞的左右两侧共有2 r 个元胞作为其邻居集合n 。现阶段，对于元胞自动机的理论 研究多集中在一维元胞自动机上。 ( 2 ) 二维元胞自动机：元胞分布在二维欧几里德平面上规则划分的网格( 方格) 点 上。现在的多数应用模型都是二维元胞自动机模型，它的应用最为广泛。 ( 3 ) 三维元胞自动机：是一维和二维元胞自动机的拓展。 ( 4 ) 高维元胞自动机：只是很少量的理论探讨，实际应用的系统模型很少。 同时，s w o l f r a m 在8 0 年代初做的基于动力学行为的元胞自动机分类是最具影 响力的。他在大量的计算机实验的基础上，将所有元胞自动机的动力学行为归纳为四 大类： ( 1 ) 平稳型；自任何初始状态开始，经过一定时间运行后，元胞空间趋于一个空间平 稳的构形，这里空间平稳即指每一个元胞处于固定状态，不随时间变化而变化。 ( 2 ) 周期型：经过一定时间运行后，元胞空间趋于一系列简单的固定结构( s t a b l e p a t t m n s ) 或周期结构( p e f i o d i c f lp a t t e r n s ) 。 ( 3 ) 混沌型：自任何初始状态开始，经过一定时间运行后，元胞自动机表现出混沌 的非周期行为，所生成的结构的统计特征不明显，通常表现为分形分维特征。 ( 4 ) 复杂型：出现复杂的局部结构，或局部的混沌，其中有些会不断地传播。 另外，按照元胞自动机的元胞空间可以分为有限元胞自动机和无限元胞自动机；根据 状态函数的不同可以分为b o o l e a n 元胞自动机和t h r e s h o u d 元胞自动机：按照元胞状 态的演化方式可以分为有串行元胞自动机和并行元胞自动机等等。 2 1 4c a 几种典型的行为 运用n e t l o 9 0 2 ，我们演示一下元胞自动机所能具有的几种典型行为，如图2 i 3 元膪自动机的理论、模型及应用 硕士论文 ( a ) s a l e2 5 0 p( b ) r u l e9 0 v t c ) r u l e3 0 p( d ) r u l e1 1 0 p 图2 1 3 元胞自动机的几种行为 元胞自动机在简单的规则和简单的初始条件下，能产生各种不同的行为模式。例 如国2 ，1 3 中所示，( a ) 在规则2 5 0 下，能产生有规律的行为，最终进入趋于同一均 匀模式；( b ) 在规则9 0 下，能产生嵌套的行为，最终进入维持不断重复的同一模式； ( c ) 在规则3 0 下，产生了随机的行为当然无论多少步，它的模式都是随机的：( d ) 在规则1 1 0 下，产生了有局部结构的行为，这种情况比较复杂，最终进入的模式也是 有序和随机的混台模式。 2 2 典型的元胞自动机模型 在元胞自动机的产生和发展过程中，科学家和研究学者们构造出了各种各样不同 类型的元胞自动机模型。他们都用于不同的场合，具有这不同的应用和理论意义，为 元胞自动机的进步发展提供了很好的基础模型。阻下是几种比较典型的元胞自动机 的模型，他们被认为是元胞自动机发展过程中的里程碑，对元胞自动机的理论研究起 了极大的推动作用。 2 2 1 初等元胞自动机 南京理工大学硕士学位论文一种基于元胞自动机的自调节的网络模型 初等元胞自动机( e l e m e n t a r yc e l l u l a ra u t o m a t a ，简称e c a ) 是一种最简单的 元胞自动机。它的状态集s 只有两个元素 0 ，1 ) ，且它的邻居半径为固定值r = l ，它 是一个一维的元胞自动机。它的局部影射：f ：s 3 一s 可记为： s ( t + 1 ) = f ( s f l ( t ) s ( t ) s h ( t ” s w o l f r a m 对他们作了深入的研究，发现虽然初等元胞自动机简单，但是他们却能演 化成高度复杂的空闻形态。并且将他们分成了四种类型：趋于一个不随时间演化的 定态；趋于周期结构；导致混沌行为的出现；演化为更复杂的结构( 如图 2 1 3 ) 。s ，w o l f r a m 对初等元胞自动机的硪究为以后的理论发展、人工生命以及复杂 性科学研究作出了巨大的贡献。 2 2 2 “生命游戏” 生命游戏( g a m eo fl i f e ) 是j h c o n w a y 在2 0 世纪6 0 年代末设计的一种计算 机游戏。生命游戏的构成及规则如下：元胞分布在规则划分的网格上，元胞具有0 和1 两种状态，0 代表“死”，1 代表“生”；元胞的生死由其在该时刻本身的和周围 八个邻居的状态决定；在当前时刻，如果一个元胞状态为“生”，且八个相邻元胞中 有两个或三个的状态为“生”，则在下一时刻该元胞继续保持为“生”；否则“死”去； 在当前时刻，如果一个元胞状态为“死”，且八个相邻元胞中正好有三个为“生”，则 该元胞在下一时刻“复活”，否则保持为“死”。以上这些就是生命游戏的规则，虽然 很简单，但是通过这些规则可以产生很多有趣的图案，其中最为著名的就是“滑翔机 ( g l i d e r ) ”图案。生命游戏的图案与初始元胞状态有关，经过若干步，得出各种不 同的图案。这些图案有的很稳定，有的稍纵即逝，有的周而复始。 生命游戏模型已经应用在很多方面了。因为它的格演化规则能近似的描述生物的 生存繁殖规律，并且具有计算能力，因此它能模拟任何一种计算机。a k d e w d n e y 通 过后期的不断研究和拓展，已经将c o n w a y 的一维生命游戏拓展到了三维和四维空间， 2 2 。3 格子气自动机 格子气自动机( l a t t i c e - g a sa u t o m a t a ，镯称乙g a ) 是元鼹自动机在流体力学与 同级物理中的具体化，主要利用元胞自动机的动态特性来模拟流体粒子的运动。它是 一种特殊的元胞自动机模型，主要有三大特征：它是一个可逆的元胞自动机模型， 从而确保模型中流体粒子不会随便消失；它的规则是基于一个2 2 的网络空间 的，考虑由这四卜元胞所组成的方块的状态变化。按照其规煲i j 计算完成一次之后， 需要把这个2 2 的模板沿对角方向滑动后再计算次。这三个特征使得格子气自动 正咆自动机的理论、模型及应甩硬士论文 机从时间和空间的角度看具有较为独特的特征。正由于格子气自动机的上述特征，因 此它较传统的数值方法而亩，具有了其没有的优点：算法稳定，没有数值误差，边界 条件容易处理，程序设计简单，完全并行，且容易在计算机上实现。但是格子气方法 也存在着问题；比如格子气模型给宏观统计带来极难消去的统计噪声，为此进行的