渗流模型的计算机模拟毕业论文

《渗流模型的计算机模拟毕业论文》由会员分享，可在线阅读，更多相关《渗流模型的计算机模拟毕业论文（47页珍藏版）》请在装配图网上搜索。

1、 .毕业设计（论文）任务书题目：渗流模型的计算机模拟一、原始依据1、论文的工作基础：1逾渗是统计物理中的基础理论，在广泛的体系中得到应用。然而，除了极少的规则点阵，大多数结构的逾渗阈值都是依赖计算机模拟获得的。不规则结构的逾渗研究尤其薄弱。近年来，R.Ziff提出了计算机模拟新算法，并应用于正方形点阵和立方体点阵；该算法的模拟计算效率较高。本课题组在前期工作中提出了一种新的计算机模型：RCP-LV模型，用于模拟多晶材料等无序不规则胞状结构；该模型的数据结构完整易用。这种结构的逾渗问题，还没有研究过。2研究条件：电脑：cpu：P4 2.0GHz 存：2；应用软件：Matlab6.53工作目的：研

2、究RCP-LV模型的基本问题。具体为（1）设计统计发生逾渗时（估计）的逾渗值的方法和程序，用matlab编写程序并进行调试。（2）对这些逾渗值进行进一步处理，利用统计学关系将这些统计结果经过推导和计算获得正则下的逾渗值。（3）探讨提高Pc精度的方法。（4）统计逾渗的最大集团，并进行结果分析。二、参考文献1 R.泽仑非晶态固体物理学M：大学，19881552172M. E. J. Newman, R. M. Ziff. Efficient Monte Carlo algorithm and high-precision results for percolation JPhysical revi

3、ew letters. 2000, 85(19): 14.3M. E. J. Newman, R. M. Ziff. Fast Monte Carlo algorithm for site or bond percolation J. Physical review E, 2001, 64(016706): 116.4Geoffrey Grimmett. Percolation M. Beijing: World Publishing Corporation，2000, 6(1), 1992 . 6-105G.R. Jerauld, L.E Scriven and H.T. Davis. Pe

4、rcolation and conduction on the 3D voronoi and regular networks: a second case study in topological disorderJ.J. Phys. C: Solid State Phys. 1984, 17(22): 110.6智刚，吴裕功，选贺LaguerreVoronoi图软件包的设计和实现J大报，2003，36(6): 12. 7Scott Kirpatrick. Percolation and Conduction J. Reviews of modern physics，1973, 45(4):

5、 113.三、设计（研究）容和要求在本课题组的系列lognormal分布的Voronoi图上研究逾渗相关问题。在已经计算出的lognormal分布的Voronoi图上利用已有的数据结构，设计研究逾渗所需的数据结构，完成查找和连接等算法模块，对逾渗现象作模拟研究。具体目标参数如下所示。主要指标和技术参数：1、统计集团大小，比如发生逾渗时最大的集团大小，以与平均集团大小。2、设计计算（估计）Pc的方法和程序，用matlab编写程序并进行调试。3、尽量将Pc的精度提高（目前Pc值在各种模型即使是正方形模拟都没有精确值）。具体要求：1、了解逾渗模型的基础理论 2、在本课题组的Voronoi图上，利用m

6、atlab建模进行仿真运算。 3、在本课题组的Voronoi图上，通过计算机实验，统计并通过推导和计算估计Pc值，研究提高其精度的方法。4、统计最大集团的性质。指导教师（签字）年 月 日审题小组组长（签字）年 月 日摘要本文采用了一种新的模型LV（Laguerre-Voronoi）图来进行逾渗试验，由于还没有相关的报道，这使得这次试验更有意义。本文中，本文首先介绍了关于逾渗模型的一些概念，比如逾渗的定义，逾渗值，平均集团大小，以与各种应用。基于ziff的算法本试验给出了适于LV模型的算法以与计算机程序。在PC（cpu：P4 2.0G 存1G）上完成整个模拟试验。具体步骤是首先统计在不同规模下不

7、同的逾渗值的大量数据（本实验中每个规模计算了104次），然后利用这些数据画出Rl（n）图，并记录下函数Rl（n）的数据，最后利用二项分布式的关系，转换成为正则下的函数Rl（p），通过函数的最大值来估计该规模的逾渗值。并在最后分析了不同占据概率下最大集团在的图形。关键词：逾渗；LV模型；正则；微正则；逾渗值；集团ABSTRACTIn this paper, a new model-LV(Laguerre-Voronoi)-was choosed to detect the percolation threshold.Because of the absence of relevant repor

8、ts, which makes this test more meaningful. Firstly, the model of percolation has been discussed, so was some related concept, for example, percolation threshold ,average cluster size, and some applications in many fields. A model suitable for LV the algorithm and computer program were gave based on

9、Ziffs algorithm in the paper. The program was performed on the PC with 2.0GhzPentium 4 and 1G memory. Then for the particular run, the system is percolated for all higher values of p. When the results was average over, Rl(n) has been plot although it is actually the microcanonical. At last, the fina

10、l step is to get the canonical Rl(p) by convoLVing with the binomial distribution. From the maximum of the Rl(p), the percolation threshold was found. And the picture of the biggest cluster with different p was analysed .Key words：percolation；LV model; canonical ;microcanonical；percolation threshold

11、；cluster；2 / 47目录第一章 绪论11.1 课题的提出与研究意义11.2 课题的发展、背景与现状31.3 课题的目的与着重点41.4 论文安排4第二章 所用模型与逾渗模型简介52.1 逾渗模型与其概念的介绍52.1.1 逾渗实例说明52.1.2 标度理论52.1.3标度律与标度理论的普适性62.1.4 逾渗的相关定义62.2 逾渗理论三个应用的介绍72.2.1 Ag1-xCox巨磁电阻的应用82.2.2金属一绝缘颗粒复合介质的应用82.2.3逾渗理论在器件可靠性上的应用82.3 V图、PV图和LV图定义92.3.1V图简介92.3.2LV图简介92.4 伪随机数的产生122.4.1

12、 随机数生成的方法12第三章 逾渗算法与其计算机实现143.1 算法的描述143.1.1 已有的应用于正方形晶格的算法183.1.2 本文对于所采用的算法的基本思想与改动193.2 基于树的“连接/查找”的粗糙计算结果203.3 性能分析22第四章 非正则下逾渗值的计算254.1 微正则与正则规则的解释254.2 Rl(p)和Rl(n)的定义254.3 利用Rl(p)计算精确逾渗值（即正则下逾渗值）264.4 使用Rlh估算逾渗值324.5 逾渗值方差的计算324.6 系统的最大集团的统计34第五章 结论与建议365.1 结论365.2 建议365.3 待解决的问题36参考文献37外文资料中文

13、译文致第一章 绪论1.1 课题的提出与研究意义定量研究材料的宏观性能与其微观结构之间的关系，一直是材料科学的主要目标。但是在现实条件中，由于传统材料科学面临着现有实验手段和仪器难以满足需要等问题，这种研究受到了限制。随着计算机运行速度的不断提高和科研工作对定量预测要求的不断增加，数值方法在材料科学中的应用越来越广泛，使得基于理论辅助的材料设计计算材料学（computational materials science）正成为近年来一个迅猛发展起来的多学科交叉新兴研究领域。计算机可以用于模拟现实中许多无法完成或者成本很高的实验，验证已有理论的正确性以与根据模拟结果适当的修正已有理论，也可以从材料的

14、微观变化机制的模拟研究出发，对研究材料成分，结构以与制备参数进行优化设计，计算机模拟已成为除试验和理论外解决实际问题的重要组成部分，并且这种研究成本很低，近年来的文章，尤其是在逾渗方面发表很多1。逾渗模型是计算材料学中一个重要的模型，逾渗模型的核心容是存在一个尖锐的相变，在转变点系统的长程连接性突然消失（从另一个角度看突然出现）。这一基本转变是当系统的成分或某种广义的密度变化达到一定值（称为逾渗值）时突然发生的。在逾渗之处，许多重要的性质将以“行或者不行”的方式发生性质上的突变，比如两个通讯基站之间的联络能否进行，其答案只能是是或者否2。最初逾渗模型的提出是为了研究流体在无序多孔介质中流动时提

15、出的，如今已应用于各个领域中。例如：Ag1-xCox巨磁电阻3，聚乙烯-炭黑复合材料4，金属绝缘颗粒复合介质5，微电子可靠性6等领域中获得了应用。而除了这些物理应用以外，还在现代电阻网络，森林火灾还有其他生态扰动，传染病，因特网中得到了应用8。例如，可以想象一个果园，均匀栽植着一种果树，遭受某种高度传染的枯萎病的威胁，令函数p（r）代表病株传染给相距为r处的另一健康的树的概率，假定p（r）已知。果农想得到最大产量，自然希望利用已有的果园栽种实际最大可能数目的果树。现在要问：在能够避免枯萎病引起的果园毁灭危险的前提下，可以允许的最大栽植密度是多少？假定彼此分隔得很远的几个单株将不可避免的染病，即

16、破坏果园中有限百分比的果树，定义为果园的毁灭。显然，逾渗模型对所提问题的回答如下：果树之间的间距a必须足够大，以保证p（a）pc。即间距必须超过临界距离rc，在这个距离之外，p（r）已经降到低于pc。由此，逾渗理论的解应取arc。这种情况下，损失局限于最初感染的病株周围的有限集团2。当然也不能选取的a过大，这样虽然不会有感染的发生，但果园的产量会受到很大的影响。表1-1逾渗理论的应用例子2现象或体系转变多孔介质中流体的流动群体中疾病的传播通讯或电阻网络导体和绝缘体的复合材料超导体和金属复合材料不连续的金属膜螺旋状星系中恒星的随机形成核物质中的夸克表面上的液He薄膜弥散在绝缘体中的金属原子稀磁体

17、聚合物凝胶化，流化玻璃化转变非晶态半导体的迁移率非晶态半导体中的变程跳跃堵塞/流通抑制/流行断开/联结绝缘体/金属导体正常导电/超导绝缘体/金属导体非传播/传播禁闭/非禁闭正常的/超流的绝缘体/金属导体顺磁性的/铁磁体的液体/凝胶液体/玻璃局域态/扩展态类似于电阻网络逾渗理论的重要实际意义，在于它可广泛应用于说明众多物理、化学、生物与社会现象，迄今其应用围还在不断扩大，比如疾病传播等社会现象也可以用逾渗模型来描述。表1-1列举了十五种不同的现象，都是已采用逾渗模型加以分析的。表中约一半属宏观现象，一半属微观过程。宏观和微观的分界线在表的中间。这特意把两种极端情形并列以便于区别，请注意不同例子的

18、特征长度相差可达1035。银河系的特征尺度量级为1022cm，而核子的尺度量级为10-13cm，用以说明逾渗理论广阔的适用围。表1-1的下部列出了逾渗理论对非晶态固体的应用。请注意逾渗现象与电子定域问题（非晶态固体的迁移率或安德森转变）以与原子定域问题（玻璃化转变）的联系，二者均属于凝聚态物理现象，其特征长度的典型值为10-810-2cm。非晶态固体是逾渗理论概念的一个富有成果的应用领域，它提供了一个具有丰富的无规结构的自然对象。在这里，拓朴无序起着至关重要的作用。对聚合物科学而言，逾渗理论可用于阐明玻璃化转变、溶胶-凝胶转变（它是一种特殊类型的玻璃化转变）等相变过程，也可用于说明聚合物功能化

19、和高性能化改性研究中（如导电、导磁、发光、阻燃、组装、共聚、共混、复合、增韧、交联、碳黑增强、凝胶化、IPN等）各式各样的临界现象与其中最重要的物理概念2。1.2 课题的发展、背景与现状Broadbent和Hammersley在1957年共同发展了逾渗理论。当时的Broadbent正参与设计煤井作业时必须使用的防护面具。这些防护面具是利用多孔碳颗粒制成的，可以渗过空气，并利用多孔碳的吸附作用除去空气中悬浮的颗粒、粉尘等杂质，从而起到防护的作用。如果防护面具中的微孔与微孔间是充分连通的，空气就能通过对流、扩散作用深入多孔碳部，与碳颗粒表面充分接触，从而可以有效地去除杂质;反之，如果微孔与微孔间连

20、通不充分，空气就不能深入多孔碳部与碳颗粒表面充分接触，也就不能有效地去除杂质，防护面具就会失效。Hammersley后来也对这种“流体”在“随机介质”中的传播问题很感兴趣，于是他和Broadbent合作，发展了他们关于“逾渗”的理论。这里，“流体”和“随机介质”都可以看作是广义的(这也是逾渗理论得以广泛应用的原因之一)。“流体”可以指液体、蒸汽、热流、电流、甚至是传染病病毒等等;“随机介质”可以是多孔岩石、复合导电导热材料、化学催化剂、人群乃至社会等复杂无序系统。这类问题后来被人们称为“逾渗”(percolation)，因为“流体”流过“随机介质”的清形非常类似于咖啡流过过滤器(percola

21、tor)。图1-1 “咖啡壶”流通的逾渗模型2当时，J.M .Hammersley考虑的是流体在一个由许多通道组成的网路中流动，而某些通道无规地)被堵塞。图1-1是这一逾渗过程的草图，并附有一个理想化了的二维蜂房形的通道网络，表示出液体如何迂回曲折地通过六角形的“咖啡渣。图的右下部显示了相应的网络图，粗线表示联键，并标出了几个集团，其中一个集团己标明是一个可能的逾渗通路。因此，逾渗可以看成是某种广义的“流体”流过一种“介质”，后者由许多相互连接的“水管”组成，其中有些“水管”的阀门被无规地关上了。阀门放在接头处称为座逾渗，放在管子中间称为键逾渗。此后，逾渗理论得到不断发展，R.Zallen说:

22、“处理强无序和具有随机几何结构的系统的理论方法甚少，其中最好的方法之一是逾渗理论。逾渗模型引人入胜，一方面在于其数学上像玩游戏般的迷人，另一方面则是它为描述空间随机过程提供了一个明确、清晰、直观而又令人满意的模型。逾渗理论还有重要的实际意义，它可应用于广泛的(其围还在不断扩大)物理现象9。”自从逾渗理论提出以来，物理学家进行了大量的计算机模拟实验并将此理论广泛应用，这几十年来科学家们得到了无数的结果，但是，经过了数十年的努力，在最简单的正方形的晶格中的座逾渗问题仍然没有精确的结果，三维或者更高维的晶格也没有精确解，由于这些原因以与当前对于逾渗理解上的分歧，在这个领域许多模拟得到广泛应用8。而由

23、于三维LV图程序包的完成，使得在三维LV图计算Pc值成为可能，并且是前人未做过的结果。1.3 课题的目的与着重点通过计算机模拟可以将一些很难做的实验或者机理并不清晰的过程通过数值计算来获得一个近似的结果，通过模拟来指导实践以得到更高的效率。本文是在已有的LV数据结构上进行的仿真实验，用来算出LV图的逾渗值，分别计算了2维和3维的图形的逾渗值，2维模型可以用来作为森林火灾，疾病传染，薄膜淀积的过程的模型，而3维模型则可以用来模拟电介质的电学特性，多孔介质中流体的流动等。本文利用Robert.Ziff提出的算法进行仿真，计算逾渗值，着重点是对于不同规模尺度下的模型的逾渗值进行大量计算，并对这些结果

24、进行进一步的转换和处理，进行结果分析。1.4 论文安排文章的第一章是绪论，对模型与背景进行了简单的介绍。针对不同的模型，所需要模拟的维数也有所不同。第二章介绍了逾渗的基本概念以与一些在工程上的应用。在此还介绍了所采用的晶格模型，给出了各个图示，得到直接的认识，这种模型下的逾渗计算目前尚无报道。第三章对于粗糙的逾渗值进行了进一步的处理以与进行了复杂度的分析，给出了具体的算法和结果分析。第四章介绍了正则和微正则的概念，并计算了正则下的逾渗值。第五章为结论部分，对文章进行总结并提出以后的方向和优化方向。第二章 所用模型与逾渗模型简介2.1 逾渗模型与其概念的介绍2.1.1逾渗实例说明为了说明逾渗过程

25、并引入逾渗阈值的概念，考虑一个假想实验例子。一个相互联结的正方形点阵网络代表非常大的通讯网络。设想有一个醉汉手拿剪刀，边走边无规地（完全随机地）剪断某些联线。醉汉毫无“目的”，其行为的最终效果将破坏两个通讯中心间的电讯联络。现在问醉汉必须随机地剪断多大百分数的联线或联键，才能终断两通讯中心之间的全部联系?逾渗理论可以给上述问题以确定的回答。实际上，这个问题说明了逾渗模型的中心容，即存在一个尖锐的转变，在转变点处系统的长程联结性突然消失（或出现）。这一重要转变是当系统的成分或某种广义的密度变化达到一定值（称为逾渗阈值pc）时突然发生的。在逾渗阈值处，系统的许多重要的性质将以“行或不行”的方式发生

26、突变。此外另一个介绍逾渗理论的最常用的一个模型是无规导电网络。如图2-1所示，在这一导电网络中的座可以是随机被占座(相当于导体，以实心小球示例，概率为P)，也可以是空座(相当于绝缘体，以空心小球示例，概率为1-P )。在低密度P下，导体可以是孤立座，也可以和邻近座组成小集团(S集团)。当P很低，没有形成贯穿网络对边的通道，整个网络就是绝缘体。当P值足够高而达到临界值(逾渗阐值Pc)时，网络中出现从网络一端联到相对端的通道，整个网络成为导体。图2-1 无规导电网络的模型2.1.2 标度理论标度理论是对于几何相变(临界点附近现象)的一个“普适性”理论。对于几何相变，某些性质却能在临界点附近出现很明

27、显的变化。逾渗的标度理论讨论的就是逾渗的临界行为，即在临界点邻域，各种参数随自变量的变化程度相关基本概念参见表2-1).由上面的论述可知，对于逾渗概率,当PPc时为有限值。实际上，进一步研究表明，在临界点过后，以无穷大斜率突增，且与逾渗阈值的距离P-Pc的依赖关系遵从幂次律: （2-1）同样还可得到以下关系式 （2-2） （2-3） （2-4） 式中，的指数被称为临界指数。通过这一系列的表达式可将复合体系的宏观性能与微观的状态(被占座概率P)与逾渗值相联系。也就是说，可以通过标度理论对复合材料临界区的行为进行定量的描述。表2-1 逾渗标度理论中的基本定义物理量名称定义S-集团由S个相互联结的被

28、占座组成的群体S一集团数n单位网格节点上的S-集团的数目逾渗概率p被占座属于无限大逾渗网格的份额逾渗阈值Pc无限大网格上第一次出现无限大集团(即出现逾渗)的有限概率标度区域标度理论中参数适用的区域关联长度集团的平均跨越长度集团的平均大小Sav（P）集团大小对所有集团的平均值2.1.3标度律与标度理论的普适性上述，临界指数对于二维和三维点阵是正的非整数，且相互间存在一定的关系(如2-a=+2)，它们通过一系列的标度律关联，研究表明，只有两个临界指数是独立的7。这些幂次律的最突出的特征是这些指数不依赖于点阵几何结构的细节，对于一样维数的一切点阵都有一样的值，这一点与阈值(逾渗阈值可以随不同点阵而发

29、生很大的变化)不同。这就是标度理论的“普适性”特征。2.1.4 逾渗的相关定义空间任何一种点阵都由座（顶点，键之间的交点）和键（边，联线，两点之间的成对的联结）组成。点阵上的逾渗过程有两种基本类型：键逾渗（bond percolation）和座逾渗（site percolation）。两种情况都是从规则的、周期的点阵出发，然后对每一个座或每一条键，无规地指定反映问题统计特征的非几何性的两态性质（是或非、断或通、有或无、联结或不联结等），从而把规则几何结构上的问题转变成随机几何结构的问题。对于键逾渗过程，每条键只能有两种情况，或者是联结的，或者是不联结的；设联结的百分率为p。应该指出，这儿必须假

30、定系统是完全无序的，即每条键的联结概率p与其相邻键的状态无关，即每个键是否联接都是个独立事件。同样地，对于座逾渗，每条键都是联结的，但“座”具有结构的无规联结性特征每一个座或者是被占据的，或者是不被占据的，相应的百分率分别为p和1-p。仍假定，对于每一个座，概率p不受其相邻点的状态的影响。被占据的座和未被占据的座分别称为“已占座”和“空座”，用来表达逾渗过程模拟的现象与浓度或密度的依赖关系。集团是指一组联结的键或座，单个座或者键形成的集团被称为单座集团，而形成的不同集团的数量也是不同的，在逾渗点附近，最大的集团的大小会发生一个突变，后面的章节中会给出图形与分析。对于键逾渗，相邻的联键是彼此联结

31、的；同样，对于座逾渗，相邻的已占座也是彼此联结的。对座逾渗，若两个已占座可以通过由一系列最近邻的已占座连成的路径联结起来，则称这两个已占座属于同一集团。同样，对键逾渗，若两条键可以通过至少一条由联键连成的路径联结起来，则称这两条联键属于同一集团。所谓逾渗阈值，指存在一个极端尖锐的临界值pc，当p减小（或增大）到pc值时，系统的性质发生突变。这里涉与到一个约定的假定，即二维正方形点阵是无限大的。只有在这一极限情况下，数学上才可能确定联结性阈值。对于“有限大”的系统，所观测到的阈值将是一个包围pc的，展宽了的数值区间。对于正方形点阵键逾渗现象，前人推导的理论上的逾渗阈值为1/2，pc=0.5。这是

32、少数几个可以严格求得pc值的例子之一。另外还有几个二维点阵的逾渗问题的阈值也已严格解出。但对任何三维或更高维点阵的逾渗过程，至今尚无严格解。一维点阵不存在逾渗现象。对一维情形，立即得到pc=1；意即任何断键都将破坏长程联结性。一维情形（d=1）时无法像d2那样“绕过”障碍2。2.2 逾渗理论三个应用的介绍2.2.1 Ag1-xCox巨磁电阻的应用Ag1-xCox颗粒膜是将磁性纳米颗粒Co嵌埋于基质金属Ag中所构成的一类复合薄膜。在其巨磁电阻（GMR）效应的组成中，磁性元素所占的体积百分数大约处于15%至25%围，低于形成网络状结构的逾渗阈值。在磁性颗粒膜中，依赖磁性金属的含量，存在着3种明显的

33、结构区域，即过渡区域、分离区域或介电区域、连通区域或金属区域。如果，Ag所占比例较大，则整体表现为非磁性，而当Co的比例增加时，整体表现为有磁性，这个临界点的x值就是逾渗值3，也是本文最关心的。2.2.2金属一绝缘颗粒复合介质的应用所谓的金属-绝缘颗粒复合材料指金属颗粒无规地分布在绝缘的基质中或金属与绝缘颗粒无规地混合。文章5指出，这种混合物有效电导率e随着金属组分的浓度f减小而减小，当浓度f达到某一临界值fc时有效电导率会突然消失;而当浓度小于这个临界值时，有效电导率的值是0，整个系统处于不导电的状态;当浓度f等于这个临界值时，整个系统发生了金属一绝缘体转变.这个临界值称为渗流阈值.在fc附

34、近，复合介质的e由金属成分所组成导电通路的无限大集团确定，光学性质同样也会在阈值附近发生跃变，这主要是因为成分的变化使得波长发生了变化。2.2.3逾渗理论在器件可靠性上的应用按照国际半导体工业协会2001年修订发布的国际半导体技术发展规划(International TechnologyRoadmap for Semiconductors)，到2014年将进入35nm技术时代，如今主流是130nm和90nm工艺。事实上随着有些厂商要将45nm技术量产，所以35nm技术会时代更早到来。集成电路技术的进步要求金属连线的宽度减少，连线层数增加。在特征尺寸的缩小使器件门延迟减小的同时，也使得互连线性能

35、降低，这是因为特征尺寸的缩小将导致互连线横截面和线间距减小。而横截面减小不仅会引起连线电阻增加，电路互连延迟时间增大，而且直接导致互连线中电流密度增大，热应力和电迁移应力增大。严重影响互连线的可靠性。同时，金属互连在整个集成电路芯片中所占的面积越来越大，而性能却不断降低。金属互连线可靠性问题自然成了今后集成电路可靠性研究的重点。事实上，如今很多技术，比如在90nm都是采用的铜导线，这就避免了电迁移现象的影响，当然，成本也会更高一点。众所周知，铜是很难被刻蚀的，现在的解决方法是采用双大马士革方法，这种方式更像是一种介质的刻蚀过程，在此本文不做介绍。根据逾渗理论，可以认为电迁移过程实际上是互连线中

36、先产生缺陷而后产生绝缘缺陷的过程。在这个过程中，在电场的作用下，金属原子定向运动形成缺陷，并不断的产生缺陷积累。当应力时间足够长，互连线中的缺陷浓度足够大，达到了逾渗阈值，则在互连线中会形成大的缺陷逾渗集团，使实际参与导电的互连线横截面积急剧减小，电阻显著增大。互连线表现为电迁移失效。图26 Al膜的随机电阻模拟6如图26所示，可以将Al膜用随机电阻模拟，每个晶格用一个电阻代表，当电流通过时，只要存在一个通路就会有电流通过，可以将金属定向移动后留下空缺的过程认为是电阻的失效，随着电迁移的增加，电阻不断失效，当到一定程度后，突然会无电流通过，这时可以认为是Al线失效6。2.3V图、PV图和LV图

37、定义2.3.1V图简介许多科学以与工程问题可以转化为二维、三维的空间分割，如供货点供货区域划分问题以与无线通讯基站服务区域划分等问题。通讯基站或供货点位置可用孤立点表示，其空间划分多采用Voronoi模型，如图1所示,V图是计算几何中最重要的图形结构。N维V图的定义：在N维空间RN上有n个点组成的点集S=p1,p2,p3,pn,其中点pi的空间坐标为（k1i,k2i, ,kNi）,令 (2-5)为点p到点pi的距离，于是将满足(2-6)的空间区域R（S,pi）称为为点pi的Voronoi区域（V区域）。这样，N维空间被划分为n个V区域R（S,pi），R（S,p2），R（S,pn）和其区域的公共

38、边界，这种图结构称作点集S的V图，如图1所示。简而言之，就是将这些孤立点连接起来，取这些连线的中垂线，中垂线的交点所组成的图形就是V图，而孤立点的连线组成的图形是其对偶图，对偶图实际上是对空间进行三角剖分。很显然，V图可以模拟通讯基站或供货点的空间划分问题。但其缺陷也很明显，因为实际上每个通讯基站的功率或供货点储备货物量未必一样，有些情况下相差还很悬殊，而在做图时把各个点等同看待，就无法考虑各个点的差异性。图 2-1 V图模型2.3.2LV图简介为了更好的模拟实际的情况,对于模型进行了大量的改进,即加入了权重的概念。Laguerre-Voronoi图（LV图）就是一种施加权重的V图。LV图具体

39、定义：设在N维空间上有由n个球组成的集合G，Gc1,c2,cn,设ri,pi=（k1i,k2i, ,kNi）,分别是球ci的半径和球心坐标,定义空间一点p到球ci的距离dL(p,ci)为dL (p,ci)2=d(p,pi)2ri2,于是可将满足RL（G,ci）PRN| d(p,pi) d(p,pj),|ji的空间区域RL（G,c2）称为球ci的Laguerre-Voronoi区域(LV区域), 这样，N维空间被划分为N个区域和RL（G,c1）,RL（G,c2）,RL（G,cn）相应的边界，如此构成了LV图，或称power图。此外，当区域RL（G,ci）和RL（G,cij）有公共边时，可把两球的

40、球心pi和pj连接起来，用这种方法构成了空间的三角剖分，如图22中虚线画的三角形形态，即LaguerreDelaunay图（LD图）。用LV模拟主要是为了把各个通讯基站供货点不等同看待，以便更好的模拟真实情况，使得模拟效果更好。通过半径这个概念以权重的形式对生成的图形结构施加正向影响，通讯基站的功率越大或供货点储备的货物越多，他所划分得到的空间越大，通讯基站通过方程来计算它的辐射围，通过计算机来仿真并画出基站的辐射围。从上面的两个空间划分的实例可以看出，LV图比PV图有更好的实用性。在实际科研中，V图以与LV图在诸多学科建模中确实有着举足轻重的作用。这种重要的几何模型已经广泛地应用于材料、生物

41、、天文、经济、通讯以与人工智能等研究领域中10。图2-2 二维下的LV和LD图图23中，给出了胞数为4096个胞的LV图形。图23 实验所用的LV图（胞数为4096）2.4 伪随机数的产生2.4.1随机数生成的方法通常产生随机数是利用计算机程序，即由一个算法来产生随机序列，所谓序列是指一个有序数列，以往由计算机产生的随机数一般是先确定初值(即种子)，再由递推公式z 一f(x )产生下一个随机数，这样，数据间应是有明确关系的，即不独立的，故被称作伪随机数。但由于其快速、经济、方便的特点，仍得到了相当广泛的应用11。Matlab随机数发生器的种类丰富且用法简便。它不仅包括能生成服从均匀分布随机数的

42、发生器，还包括能生成常用分布(如泊松分布，指数分布等)随机数发生器。这些随机数发生器所采用的算法，都是经过反复测试并商品化的，其可靠性和稳定性都很强。Matlab提供的随机数发生器通常可归为两类。2.4.1.1 以Matlab部命令形式出现的随机数发生器(1)Rand函数，该函数用来产生数列或数组，这些数组的元素服从0，1之间的均匀分布。具体的调用方法可以参照Matlab的帮助文档。这一随机数发生器可以在区间2(一53)，12 (一53)之间生成所有的浮点型数据。理论上说，它能够产生21459个不重复的随机数值，这是一般高级语言提供的随机数发生器无法比拟的。当然要是想产生一个在-0.5，0.5

43、区间的随机数，实际上就是rand的一个函数关系，即2*rand-1。(2)Randn函数，该函数的调用完全类似于Rand函数，其功能是实现服从标准正态分布的随机数序列或者是数组。此外还有象Sprandn、Sprand等其它一些随机数产生函数。2.4.1.2 工具箱(Toolbox)中的随机数发生器(1)Randseed，种子“seed”的选取对随机数的产生有很重要的影响，是随机数产生中很关键的一项工作，该函数用于产生合适的随机数种子。(2)communication toolbox和simulink进行仿真也给出了随机数发生器，它们是以模块形式实现的，由它产生的随机数或随机变量的参数是通过对话

44、框设定的。表23 Matlab统计工具箱随机数发生嚣分布类型随机数发生器分布类型随机数发生器BetabetarndHypergeometrichygerndBinomialbinorndLognormallognrndChi-SquareChi2rndNegative BinomialnbinrndNoncentral Chi-Squarencx2radNormalnormalrndDiscrete UniformunidrndPoissonpoissrndExponentialexprndRayleighraylrndF DistributionfrndStudents ttrndNonce

45、ntral FncfrndNoncentral tnctrndGammagamrndContinuos UniformunifrndGeometricgeorndweibullweibrnd(3)Stastics toolbox中随机数发生器是最为全面的，该工具箱拥有大量能够生成特定分布随机数的函数Random 函数可以通过参数的设定产生符合各种分布的随机数。其调用方法y=random(name，A1，A2，A3，m ，n)统计工具箱除了提供了这种总的调用方式外，对于各种不同的分布函数还分别给出了相应的随机数发生器，可以分别调用。分布类型和随机数发生器名如表23所示12。本文中以时间作为种子产

46、生随机数，如果是matlab默认的情况下，每次打开matlab都会产生完全一样的随机数列，为了避免不必要的麻烦，本文以当前时间作为种子。第三章 逾渗算法与其计算机实现3.1 算法的描述3.1.1 已有的应用于正方形晶格的算法算法的整个流程是首先构造n个晶格的状态（包含是否被占据和若被占据属于哪个集团等信息），注意到实验中每次增加一个座都可以认为是在n个座已经被占据的情况下再增加一个座，形成一种亚平衡的状态。加入第一个座时系统只有一个单座集团，当其他座加入时，若连接到这个集团上时则形成一个更大的集团，如此往复，直到出现一个贯通整个系统的集团出现时仿真结束，出现逾渗点。整个过程是：（1）建立一个含

47、有任意顺序的包括所有键的表。在这个表中位置的标记数字从1到M；（2）先令i=1 ；（3）随机在i=j=M围随机选取一个j；（4）将i和j位置的键更换位置；（5）令i=i+1 ；（6）从第三步重复直到i=M为止。选择这样的顺序进行占据，在加入座时首先要判断该座是形成一个单座集团还是连接到其他集团上，更或者是将两个集团连接成一个大的集团。这样就需要进行另外两个步骤：查找和连接。查找是通过数据结构中的邻居关系来判断新添加的座的周围是否有占据的集团，而连接的过程则是在查找发现有相邻的集团的情况下进行，主要是将该座连接到相邻的一个或者几个集团上，以形成一个更大的集团。具体方式为：查找：当一个座添加到晶格

48、上时必须找到该座周围座的所属的集团。连接：如果这两个座属于不同的集团，那么这两个集团合并成一个集团；否则，如果这两个座属于同一个集团，则不作任何处理。那些达到这些步骤的算法称为“连接/查找”算法。“连接/查找”算法被广泛应用于数据结果，数形和图形计算以与编译程序中。而那些应用在计算机科学中也被大量研究，而且可以很好的应用计算机技术中的一系列结果简单而有效的应用于逾渗算法中。关于“连接/查找”方法可以采用两种不同的方式来进行。添加一个座，并判断该座周围是否有邻居？与相邻座所属的集团联接起来形成一个新的集团，并判断该新集团与新添加的座的邻居座所属集团是否属于同一集团？将该座形成单座集团YesYes

49、判断是否将所有座都添加了进来No将两个集团进行联接算法结束NoNoYes图3-1 算法结构图（）复杂的“联接/查找”算法这种算法中，将每个空座都添加标记，比如设置为0，定义若座的标记为0代表未被占据，1代表被占据。用这种方式来标记座，记录座的状态。程序的最初时，这些标记值一样，均为0。开始后，一个一个地加入座，加入一个座时检查该座周围的状态的标记值，若为0则不做任何动作；继续检查周围的座，若为1，则将该点与集团连接起来，为了将两个集团联接在一起，不得不选择其中一个最简单的方式是随即选择其中一个，并使集团中所有点的标记与另一个集团中的标记相等。然后继续寻找该座周围的所有相邻座的状态，若属于不同集

50、团则相连，若一样，则不做任何步骤。在图31中，可以清晰的看到整个算法的运算过程，这种方法最大的缺点是在进行到中间时连接过程会非常多，这样严重影响了算法的效率。在算法的初始阶段，大多数的座均未被占据，这种连接的步骤会非常的快捷和简单：大多数的座的周围都是空座，所以很少进行连接，所以很少进行座的重新标记。当算法进行到后面的阶段时，大部分的座将会被占据，此时大部分的座将属于一个系统级的大集团。此时，联接过程也很少发生。但是在中间过程中，特别是在接近逾渗点时将进行大量的联接过程，在这些区域，一般会有很多的大的集团，并且当两个集团合并时，会有很多座被重新标记，因此，这种算法随着通过临界区域显示了一种临界

51、的下降的形式，在图32中，给出了重标记进行的次数，y轴代表重标记的次数，x轴表示被占据的座所占的百分比。图32 重标记次数的函数添加一个座，并判断该座周围是否有邻居？Yes与相邻座所属的集团联接起来形成一个新的集团，并判断该新集团与新添加的座的邻居座所属集团是否属于同一集团？将该座形成单座集团No判断逾渗是否发生？将这两个集团联接起来，并将较小的集团的根座指针指向较大的集团的根座YesNo算法结束Yes图33 基于树的“连接/查找”算法的过程图（） 基于树的“连接/查找”算法树的数据结构几乎应用于所有的计算机的查找算法之中,不例外,采用这种方式来进行逾渗阈值的计算,可以得到很好的结果,节约更多

52、的时间。这种用树的思想似乎是由Galler和Fisher首先提出的。树的每个顶点都是集团上一个分立的座，每个集团都有一个单一的根座，根座是相应树的根，并且所有其他的座的指针或者指向根座或者指向集团中其他的座，因此用这种连续的指针可以从任何其他座来找到根座。用这种方式的树，可以很容易的确定两个座是否是同一个集团的成员：如果他们指向同一个根目录则他们属于同一个集团，否则则不是。对于以树的形式来存储集团信息，联结的过程非常简单：两个集团可以增加一个指针从一个的根指向另一个集团的任意一个座来实现两个集团简单的结合。一般情况下，可以选择一个新的指针来指向另一个集团的根，因为这样可以减少由于遍历整个树来找

53、到另一个座的根的平均距离。有很多基于树的联结/查找方法，这些算法的区别是算法过程中树的信息更新方式不同。然而，这类算法中已知最好的是有路径压缩的加权联合/查找方法。查找：在算法的查找部分，遍历树来查找根座，如果初始的两个座指向同一个根，则他们属于同一个集团。此外，在遍历结束之后，遍历的路径上的所有指针被改变直接指向树的根。这叫做“路径压缩”。路径压缩可以使在同样的座上执行联合时遍历变快。联合：在算法的联合部分，两个集团的联合是靠增加一个指针从一个集团的根指向另一个根，因此成为另一个树的子树。采用有权重的联合形式，即总是让其中一个较小的树成为另一个树的子树。为了这么做，本文在根座下记录相关集团的

54、树的大小的信息。当两个集团结合后，新的复合的集团是两个集团大小之和。因此完整的逾渗算法可以总结如下：（1）开始时所有的座都在他们自己的位置，每一个都有自己的根座，包含一个自己大小的信息，初始大小为1。（2）所有的座在晶格上随机被占据。（3） 加入一个座后判断该座周围是否有相邻的已被占据的座，若有则将该座联接到其相邻座所属的集团，若不存在则重复第一步。（4） 继续查找该座周围的相邻座，若是存在则查询这两个集团的根座。（5）如果两个根座是同一个座，则不进行任何操作。（6）如果两个根座不同，本文检查根座中存储的集团大小，并增加一个指针，由较小的集团的根指向较大的集团的根，因此让较小的树成为大树的子树

55、。如果这两个树的大小一样，可以任意选择一个作为另一个树的子树。同时也在加入了小的集团之后更新大的集团的信息。重图33中给出了这种方法的算法的简略图，可以看出这两种算不同法大致一样，但是是基于不同的思想而给出的，第二种算法使用的树的方式来减少运算的时间。对于计算机模拟来说，很大程度上运行时间的长短是评价一个算法与程序复杂程度的重要参数。在后面章节中，本文给出所用的算法与程序所用时间的具体分析，即性能分析。3.1.2 本文对于所采用的算法的基本思想与改动本文中所采用的算法就是利用的基于树的“连接/查找”算法来实现的。算法的第一步是先建立一个座被占据的顺序，由于matlab是由程序产生的伪随机数，本

56、文以当前时间作为种子产生随机数，以防止默认模式下matlab产生一样的伪随机数来干扰实验结果。具体不同为：、建立随机占据的顺序上的不同：1、建立一个含有任意顺序的包括所有座的数组。在这个数组中位置的标记数字从1到N；2、利用matlab中自带的的函数rand将数组的顺序打乱，进行重新排列；3、 产生的新数组中所记录的标记数字就可以作为占据的顺序。、算法上的差别：后面所用的连接查找的方法与ziff13提出的算法思想一样，改动主要是在将文章中的键逾渗的形式改成了座逾渗的形式，并在产生随机数组上有不同，首先产生一个从1到N的数组，记为数组A，并用rand（A）使得A随即排序，利用数组中的顺序来进行模

57、拟。本文中的主要工作就是利用这个算法在不同的晶格种类上进行编程，主要体现在晶格数据类型上有很大不同。、判断边界点上的方法不同：在建立指针时利用了一个结构数组，这个结构数组中包含两个数组，一个是ptr.arrow，用来记录指向根座的数组，ptr.boundary用来记录每个胞的边界情况，由于ziff13是在正方形的模型，所有胞的坐标和编号都是有规律的，便于判断，而本文的模型中采用LV图，每个晶胞的体积都是满足对数正态分布的，在判断边界点上远比正方形更复杂，由于实验室产生的LV数组中存在每个胞心的编号，坐标等，第一步判断胞是否处于边界，若是则在数组ptr.boundary中对应位置标记1，该数组初

58、始时为含有6个0的数组，16位分别用来标记胞在x负方向，x正方向，y负方向，y正方向，z负方向，z正方向的信息，例如：某个胞心的ptr.boundary0 1 0 0 0 0,则表示该点处于整个系统的x负方向的边界上。另外在微正则到正则的转换时所用方式也不同，这会在后面的章节中进行介绍。3.2 基于树的“连接/查找”的粗糙计算结果本文采用树的“连接/查找”算法来进行程序的实现，分别在2D和3D上分别进行了仿真，得到在不同规模下的逾渗值，本试验中，每次进行完一次计算，当发生逾渗时，就将程序停止，并将结果记录到一个数组中保存起来，这样对于二维模型可以节省大约百分之五十的时间，对于三维模型效率就更加

59、可观，在计算发生逾渗时增加一个break语句，可以省去发生逾渗后的循环过程，节约百分之八十的时间，这是非常可观的。当然这个结果是比较粗糙的，本文在不同尺度下分别进行了一万次的计算，得到大量的样本值，这只是在微规则（microcanonical）下的结果(关于微规则与规则的概念以与精确计算将放在后面章节进行具体描述),本文计算这些这些逾渗值的平均值以与方差，其数值如表3-1所示：表31 不同2D规模下的逾渗值p的平均值和方差N平均值方差10240501000414204805008003244096049960025381920499600206163840499900161从表中可以看出，在不

60、同的规模下，逾渗值总是在0.5附近，这与pv图的逾渗值相差不大（本文同样可以计算pv图的逾渗值，在做LV图时只要让x，y坐标随机产生满足泊松分布即可，并让让r0，这时LV图将退化成为v图）。而方差随着规模图34 2D下不同规模的逾渗值的增大呈现减小的趋势，这也很好理解，在较小规模下p值分布更加不均匀可能添加一个座就发生逾渗也可能要添加很多，稳定性不好。举例来说，像一个22的正方形格子组成的系统，要发生逾渗时，至少要有两个座被占据，而当三个座被占据时一定发生逾渗，两个被占据时逾渗值是0.5而三个座被占据时逾渗值是0.75，p的分布较广。图34是本文将这些均值和方差用图画出来，得到一个更直观的理解。其中红线联接的是均值，蓝色的虚线是平均值方差的围。横坐标表示规模，纵轴表示逾渗值。表32 不同规模3D下的逾渗值p的平均值和方差N平均值方差10240211300291204802018019454096019450018181