【毕业学位论文】（Word原稿）基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法

兰州大学硕士研究生学位论文 基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法 1 第一章 引言 行计算机 人类发明出计算机是人类智慧发展到一定高度的体现，它大大地提高了人类的计算能力，深刻地改变了人类的生活方式。因此有必要简略地回顾一下计算机的发展史 1。 大概在公元前 5世纪，中国人发明了算盘，算盘被认为是早期的具有运算能力的机器，在当时被广泛应用在生活中，算盘是我们祖先留给后人的一笔宝贵遗产。 直到 17世纪，由法国人 1623发明的自动进位加法器， 得早期计算机器有了进一步的提升。随后，这种机器被德国数学家1646加以改进，实现了乘法运算。法国人这基础上进一步改造成能够进行四则运算的计算器 。 现代计算机的真正起源来自英国数学教授 起先他设计差分机用于计算导航表，但是由于它是用于专门导航的机器，于是 是开始分析机的设计，分析机被看作是包含现代计算机基本组成部分的机器。 在接下来的若干年中，著名的穿孔片计算机诞生， 随后在 1946年 2月 15日， 费城问世。 计算机发展史上的重要里程碑，它标志着现代计算机的诞生。它由电子管构造，体积庞大，耗能高。之后晶体管的发明使得电子设备的体积和耗能得以减小。 1956年，计算机中用晶体管代替原来的电子管，使得后面制造的计算机体积更小、功耗更低、性能更稳定。同时还出现了像 编程语言，之后操作系统的产生使得不同的应用程序能够在计算机同时运行。 之后随着 集成电路的发明使得计算机体积进一步减小，同时计算能力进一步提高，最后诞生了超级计算机。超级计算机计算能力最强的计算机，被广泛用于国家重要领域，如国防，证券，天气预报。“天河一号”是我国成功研制的计算 图 天河一号”千万亿次超级计算机 兰州大学硕士研究生学位论文 基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法 2 能力在千万亿次的超级计算机，它标志着我国在计算机领域的重要突破 2。 行计算机体系结构 著名的计算机体系结构的分类方法是论文 3中的 类法。按照此分类法，早期的计算机分为以下四种类型：单指令流单数据流（ 多指令流单数据流（ 单指令流多数据流（ 多指令流多数据流 （ ，目前，有很多不同种类的并行计算机系统，达到下面四个级别的并行处理 4： (1)作业或程序级并行 ； (2)任务或过程级并行； (3)指令级并行； (4)指令内部级并行。 一个作业可能由几个程序的顺序执行完成，也可能由几个程序的并行执行完成。计算机执行每一串指令，是对每一组数据进行按要求的处理。通常，把计算机执行的指令序列称为 “ 指令流 ” ，而被指令流调用的数据序列称为 “ 数据流 ” 。 计算机系统按照指令流和数据流能够归纳为如下四类 5： (1) 单指 令流单数据流（ 这类计算机只有一个指令部件，一次只对一条指令译码，并且只对一个操作部件分配数据。 (2) 单指令流多数据流（ 这类计算机有多个处理单元，它们在同一个控制部件的管理下执行同一条指令，并向各个处理单元分配各自需要的不同数据。 (3) 多指令流单数据流（ 。这类计算机包含多个处理单元，同时执行多条指令对同一数据及其中兰州大学硕士研究生学位论文 基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法 3 间结果进行不同的处理。 (4) 多指令流多数据流 （ 这类计算机系统内有多个处理机，实际上是多个独立的 算机的有机的集合，它们同时运行多个程序并对各自的数据进行处理。 以上四类是计算机系统中执行作业时最普遍的方法。 行计算机体系结构的几个要素 并行计算机体系结构中 主要包括结点（一个或多个 路由器。其中路由器负责将计算机连接到网络中并负责数据在结点间寻找路由地址的部件。 拓扑结构决定了互联网络的主体。互联网络按照给定的拓扑结构将各结点之间在物理空间上相互联接，如图 示 6。 图 代并行机的拓扑结构 互联网络的拓扑结构主要有静态拓扑结构，动态拓扑结构。所谓静态拓扑结构就是结点之间的物理联接方式是固定的，不会因为程序执行而改变点对点联接关系。例如，一维阵列，环，多维网格、多维环，树， 超立方体；如果结点之间无固定的物理联接关系，而是在联接路径的交叉点处用电子开关、路由器或仲裁器等提供动态联接特性，这样的网络拓扑结构称作动态拓扑结构。 有了拓扑结构后，就有了基于该拓扑结构的路由选择算法，路由算法中最常用的有贪心算法，动态路由选择算法以及虫孔算法。其中贪心法是指每个数据包沿最短路径传输（二维阵列举例），该方法容易在某一条边上形成通信阻塞；动兰州大学硕士研究生学位论文 基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法 4 态路由选择算法是指数据包根据当前边的申请队列长度，动态地改变传输路径；虫孔算法（ 指数据包分解为长度更小的字节流，所有字节流在网络中按动 态路由选择算法在网络中传输，最后在目的地址合并还原成数据包。 行计算机路由算法 消息路由就是将组成消息的数据包如何在网络中通过一定的中转结点次序从源结点到达目标结点的过程，因此路由策略的好坏直接关系到网络系统的性能。从适应性的角度，路由分为确定性路由和适应性路由。在确定性路由中，路径的选择完全是由源结点和目标结点来决定的，而不用考虑其它结点的状况。在适应性路由中路径的选择根据网络的一些实际情况随时进行调整，比如出现网络拥塞情况和坏结点坏连接的情况。显然，确定星路由比较容易实现，而适应性路由比较麻 烦，但是适应性路由在容错性能方面远远优于确定性路由。 并行计算机路由要解决的一个问题就是死锁， 提通过使用四个虚拟通道（ 实现在 路由。该算法不仅可以对网格内部的错误区域进行容错路由，并且可以对网格的边界错误实现容错自适应路由。而 提出了错误环（ 方法实现网络的容路自适应由。有故障的节点或链路包含在错误环内，路由的时候对错误环 上的点实现 由。错误环的优点是它的构建只由局部信息完成，没有全局消息的参与。该算法还提高了虫洞路由（ 法，当错误环发生互相交叠的情况的时候，算法将使用四个虚拟通道的方法实现无活锁路由和无死锁路由。 通过将网络划分成相互链接的两个虚拟子网络（ 现自适应无死锁路由 。 其中确定性无死锁路由在 拟网络上进行，而在 拟子网络上进行完全自适应路由。网络中的所有节点被分成安全（ 不安全（ 错误（ 种状态。当 者于可用状态时，它们都被用来进行正常的消息路由。当有故障发生时，算法随即将出错的节点或者链接标记成不安全或者错误状态，当节点或者链接被标记为这种状态的时候，将在与之相邻的 进行容错路由，最终消息将通过 而实现容错自适应路由。 0 通过用错误块标记网络中发生的故障，发生故障的节点和链接包含在一个凸（ 区域中，将有错的节点或链接与无错的部分区分开来，实现容错路 由。但是为了保持凸的性质，一部分正常节点和链接被包含在这个凸区域中，从而降低了节点的利用率，而且当故障发生在网络边界的时候，无法解决边界的容错路由。 11 提出了仅用两条虚拟通道实现了兰州大学硕士研究生学位论文 基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法 5 在 3 维网格网络上的无死锁路由，而且无死锁情况可以拓展到 n 维网格上。 12中，提出了使用错误立方体的的方法寻找 3维网格网络中的最短容错路由路径。错误立方体（ 出错的的节点包含进去。通过收集一些信息来寻找一条从源节点到目的节点的最短路径。 一个好的路由规则必须很容易实现 ，不需要全局信息，并且支持容错。杨 裔在他的博士论文 32中提出有缝隙的错误矩形块容错模型和基于该模型下的容错自适应算法。算法将网络中发生故障的结点和链接都包含在这种错误矩形块中，路由的时候对于好的网络部分，用贪婪路由算法，而碰到故障块时，绕过有缝隙的矩形故障块，并通过访问这些矩形块的内部树实现对故障块内部节点的访问。与传统模型相比，裂痕故障块模型有两个重大的突破，第一，实现故障块内部节点的路由。通过矩形块内部依然保持连通的生成树，消息能够路由矩形块内部的节点，从而大大提高了结点的利用率。第二，生成和维护这 些矩形块的完全是动态的，并且是根据局部信息来完成的。随着网络中出错节点的改变，矩形块将实时地根据局部消息动态组建，并且从理论上证明了只要网络是连通的，消息就能够实现准确传送。 线传感器网络 近年来，无线传感器网络得到了广泛的研究与应用。所谓传感器网络指成千上万个无线传感器节点按照一定的无线通信协议连接起来，并将传感器检测的各种数据通过网络传送到终端用户或者基站。由于传感器具有低成本，低功耗，多功能的特性，并且随着技术的发展，这些传感器节点功能越来越强，通讯距离越来越大，因此将会得到越来越广泛的应用 。传感器节点能够简单处理数据，并能够相互连通，实现组网 23下面简单介绍无限传感器节点，一个传感器是由以下四个基本部分组成的：感知单元，处理单元，收发单元和供能单元。根据应用的不同还会有一些额外的附加组件，比如：定位器，能量产生单元，行动单元。 感知单元是整个传感器的核心组件，它主要由感知组件和模数转换器组成。其中感知组件负责感知周围环境的各种参数，比如温度，湿度，压力，重力，声波等。而模数转换器的功能是将这些感知到的模拟信号（参数）转换成数字信号，以便将来处理单元对这些信号进行处理。 处理单元是 用来完成处理数据，以及实现协同其他传感器节点共同完成特定应用的重要组件，通常它和一个本地的存储器相连，当然存储器的容量相当有限。 收发单元使得传感器节点和其他节传感器节点之间互相链接，形成网络，它兰州大学硕士研究生学位论文 基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法 6 是无线传感器通讯的主要模块，由它发送数据给其他传感器或者从其他传感器接收数据。一般的，这个收发的通讯距离是有限的。 传感器的另外一个重要的组件是供能单元，传统的传感器通常是由不可循环利用的电池供电，采用这种方式供能的传感器，需要注意传感器节点的电能保护，即尽可能低降低能耗，因此节能对于这类传感器非常重要。对于新型的 传感器，往往采用可再生能源部件供电，比如太阳能电池等。 无线传感器网络是大量地理上分散分布的传感器节点，通过无线通讯协议组织成网络，并且这些节点和网络都是自治的，它们之间通过网络互相连接，协同合作完成对特定区域或者环境的监控，比如：温度，湿度，压力，速度等 32。无线传感器网络通常包含成千上万个传感器节点，他们分布在范围比较大的地理区域中。一般这些区域是人类难以到达或者无法长期驻地呆监测的地方，比如地下，水下，峡谷，火山，当然也可布置在一般的环境里，比如农田，自然保护区，城市等。根据不同的环境，无线传感器 网络可分为：陆地无线传感器网络，海洋无线传感器网络，森林无线传感器网络。不同的环境无线传感器网络具有不同的应用，但归纳起来，有以下特点： 有限的能量供给，大多数传感器节点的能量供给是不可更新的，所以尽可能地节能，延长传感器网络的使用寿命，就变得非常重要； 有限的感知距离，传感器节点的有效感知范围是有限的，所以传感器网络拓扑结构的设计需要考虑到传感器节点的感知范围； 有限的计算能力和存储能力，这也决定了应用于传感器节点上的程序不可能过于复杂，也不可能存储大量数据，因此程序要尽可能简练，不能有太多计算和数据存储 要求； 有限的通信距离，传感器节点间的通信距离有限，因此在传输数据时，往往源节点与目的节点不能够直接通信，而是需要进行多跳路由，好的路由算法就变得非常关键。 线传感器网络路由 无线传感器网络的跟踪和监视功能主要通过将节点感知的数据通过合理的路由方案传送到基站来实现，但由于传感器的上述特点，使得已有各种成熟的路由算法不能应用于无线传感器网络。近些年，随着对无线传感器的进一步研究，出现了很多优秀的专门应用于无线传感器网络的路由协议。在无线传感器网络中，两种常用路由机制分别是泛滥式路由和流言式路由， 采用这两种路由介质不需要维护网络的拓扑结构和相关的路由计算，但是两个机制都有不足的地方，比如泛洪机制容易造成网络拥堵，而流言机制则会引起数据冗余的缺陷，从而导致兰州大学硕士研究生学位论文 基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法 7 网络负载的几何膨胀以及和严重的网络延时，对于大规模网络来说，这种问题就更加明显。 为了克服这问题，许多人改进了这两种路由机制。 1999年，文献 25提出了基于数据协商和资源分配的消息传播协议，通过节点间本地的兴趣协商，确定是否继续将该消息或者数据通过该邻居继续转发，这样有效的限制了信息爆炸，从而在减少数据冗余方面得到很大的改进。然而基于协商的协议不 能保证网络中所有感兴趣的节点都能接收到相应的数据，因为协商属于局部协商。 2000 年，文献 26首次提出采用分层的思想在无线传感器网络中进行数据传输，网络被划分成互不相交的集群，每个集群内部选举出各自的头节点，集群内部各节点将消息发送给头节点，再有这些头节点负责将该集群内收集的信息直接发送到终端用户或者基站。这就是有名的 法。 法的优点就是能够使得整个无线传感器网络的能量分布比较均匀，也意味着能量的节约，因此它能够延长整个无线传感器网络的寿命。但是在头节点到基站的路由中，是直接传输， 这也意味着头节点的能量要大，使其能够与基站直接通信。 2001年，在 法的基础上，文章 27做了进一步改进，采用的依然是分层路由算法的思想，但是节点之间是链状连接，数据传送的原则是传送给离自己最近的节点，并规定和基站节点轮流进行通信。这个算法的优点就是实现了能量分布的平衡，但是对于距离头节点比较远的节点，数据路由的延迟比较严重，而且每一层的头节点成为路由的瓶颈。 然而上面的路由算法解决的是能量分布的均衡，而对于每个节点的负载平衡却并未涉及，由于拓扑结构不是预先定义好的，因此及有可能有些边远的 节点未能参与路由，处于饥饿状态，而中心节点像头节点则负载很重。这导致了节点负载的不均衡，有可能有的节点完全没参与路由，因为对于传感器网络，只要一部分节点参与就能实现网络的连通。本文采用预先定义好的拓扑结构，二维网格，实现无线传感器网络的路由，并且通过改进二维网格，使得二维网格的部分边界节点也能够实现一跳的路由，从而实现让每个网络中的节点都尽可能低地参与路由，实现负载平衡。改进后的拓扑结构是类环形结构，但是，方向不是单一地从一个节点移到下一个节点，因此不会降低路由的效率。此外，改进的拓扑结构不是所有的边界节点 都能够实现单跳的路由，这也是与环形结构最大的区别。 关于无线传感器网络平衡问题的研究更多的是集中在能量平衡以及采用法中的分层结构，但是基于二维网格的无线传感器网络拓扑结构上的负载平衡问题却鲜有研究，在现实应用中采用设定好的特定分布布置节点是经常会被采用的，一方面已知的拓扑结构便于问题的研究，另一方面便于节点的管理，所以研究无线传感器网络特定拓扑结构的负载平衡问题具有很大的现实意义。低兰州大学硕士研究生学位论文 基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法 8 维网格（如二维，三维）由于它结构简单，应用起来方便，因此获得广泛应用。本文就采用二维网格拓扑结构研究无线传感器网 络的负载平衡问题。 在下面的章节中，第二章介绍二维网格中的容错自适应容错路由，第三章介绍容错自适应路由表容错算法，第四章将介绍路由算法应用在无线传感器网络中的情况，进一步研究在容错自适应路由算法下的负载平衡问题。为了方便问题的研究，使其不受故障块的影响，假设无线传感器网络是完好的，各个无线传感器节点是正常工作的。第五章介绍解决死锁的路由策略，采用分区运用虚拟通道，从而整体上降低虚拟通道的数量。第六章对工作的总结。 兰州大学硕士研究生学位论文 基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法 9 第二章 二维网格中的容错自适应路由 由算法 一般地，网络中有两种基本的路由方式： 确定性路由和自适应路由。确定性路由的优点是简单，容易实现，而自适应路由比确定性路由麻烦，然而自适应路由在减少网络延迟，提高网络吞吐量以及容错性能 13 要比比确定性路由更有优势。因此，自适应路由的重要性不言而喻。我们给出了基于裂痕故障块模型下的二维网格容错自适应路由算法。该算法的基本思想是，在网络好的情况下采用贪婪算法实现最短路由，而遇到出错节点时，采用贪婪算法会引起死锁问题。因此，通过构造故障块可以解决死锁问题，并通过构造有缝隙故障块，实现访问内部节点。本文提出的容错路由方案里，处于块边界及内部的点都有 特殊的路由，并证明只要节点是连通的，节点间的消息就一定能被传送到，从而克服潜在的活锁。传统的故障块 14然由于将正常的节点包含进去，因而导致大量正常节点无法参与并行计算机的其他工作，而在裂痕故障块模型下，故障块内部的节点也能被访问到，只要故障块内部的点能够与故障块外面的网络连通，就能像正常节点那样参与路由 。 因此我们的路由方案大大滴提高了节点的使用，当网络中小部分节点出错，不会导致大量节点不能使用，从而提高了并行计算机网络的性能 。 维网格中的容错自适应路由 网状结构是多处理器计算机系统互联 常用的拓扑结构，它已被广泛应用在商业产品中。网状结构中的低维网格由于其使用简单，处理起来容易，因此比高维网格更流行。比如二维网格，在 010 17、 18、 都被作为拓扑结构得到应用，而 用三维网格。通信网络和无线网络传感器网络中的应用 32中提到的算法就是以网格作为并行计算机的拓扑结构，并在其上进行路由规则和容错规则的研究。在介绍二维网格的容错自适应路由算法之前，先来看看一些基本定义 19。 维网格的一些基本定义 二维网格记为 其中 是整数且 ，网兰州大学硕士研究生学位论文 基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法 10 格中的节点 N 用二维向量 N(其中 0 n1 0 n2 中 相当于横坐标和纵坐标。 两个不同节点 X( Y (足 或者 且 示这两个点是邻居。对任意的节点 v，令 S 为 与 v 相邻的点构成的集合 (简称，邻集 )。 对任意的非边界点 X = ( X 有四个邻点，分别用 W(X)、 E(X)、 N(X)和 S(X)表示，其中 W(X) = ( E(X) = (， N(X) = ()， S(X) = ( 若 X = (是非边界节点，而是边界节点，则 X 的邻居是 (X)、E(X)、 N(X)和 S(X)中的 2 到 3 个。两节点 X = ( Y = (之间的距离用 d(X， Y )表示，所谓距离是从 X 到 Y 所经过的最少链路数。 X 和 Y 的距离 d(X，Y )包括横向距离和纵向距离，分别定义为 ， Y )和 ,Y ) ， 其中 ， Y ) = ,Y ) = 于是我们有 d(X， Y ) = ， Y )+， Y )。 维网格中的故障块形成 本节的主要工作是 : 在含有故障的网格中形成一些极小的不交块，使得处于块的边界和块的外部的链路都无故障，而所有的故障链路或节点都位于块的内部，称这样的块为故障块。 我们考虑网络中故障的基本元素为链路和节点。当节点 X 连接到其他节点的链路只要有一条发生故障时，则这个点被标记为故障点；为构造故障块，本文采用发送系统消息的办法，通过发送系统消息，通知邻点自己的被标记的状态，从而使得 接收该系统消息的节点做出相应的标记，并将改变后的状态继续告知周围的邻居节点，直到最终状态稳定后才不再发送系统消息。该系统消息用 M 表示，M(示节点 送的系统消息。其中 示发送系统消息给结点 X 的邻点。 定义节点 X 的故障数为网格中与 X 关联的故障链路的数目，记为 )。 易知 0 m / 2 时，这意味着 通过图 示结构的 基站路由消息比经过内部网络路由更好， 因为它有两个好处。其中之一是，路由路径是尽可能短 ，绕边走，水平距离就更短 ，另一种是，不通过 缓解 中心节点的 负载 。如果 n / 2 以及 m / 2 或 n/2 时 ，就 让 消息 沿着基站路由 ， m, n 为 无线传感器网络 长和宽的 大小。 基于以上分析，我们提出了一种 基于类 环 形拓扑结构的负载平横算法。 SN m, n is , ) DXm/2 DYn/2 by .2 if .2 if SN by DXm/2&n/2 m/2&n/2 S.xm/2 S.yn/2 n/2 S.yn/2 n/2 to S S N N S S N 州大学硕士研究生学位论文 基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法 31 N, EN N S, ES S S N N m/2 S.yn/2 n/2 S.yn/2 n/2 to S S N,WN N to N N S, WS S S S S N N N m/2&n/2 S.xm/2 S.yn/2 n/2 to S S N N N S m/2 S.yn/2 n/2 to S S N to N N S 表 路由情况本质上就是看源节点和目标节点两者之间距离是进还是远，从而决定路由是内部路由还是通过基站路由，这保证了路由路径长度从短的特点，又避免了内部节点超负载的情况。 于类环结构的负载分布 我们 随机生成 1000 对 源 节点和 目的节点 ，对于不同大小的无线传感器网络兰州大学硕士研究生学位论文 基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法 32 里运行算法 1，得到 4 组 模拟结果。 图 2525 大小的无线传感器网络各个节点的 载荷分布 ， 其他尺寸的网格（ 5050， 100100,200200）具有相同的负载分布 ，因此在此节的论述中，只以 2525 规模的网格进行说明。 从结果 中，我们得到的结论是，基站 承担了最 主要的负载， 其次是与基站靠近的 边界节点 ，越靠近基站，承受的负载越大。原因是经过边界路由的消息都要经过基站转发，因此越靠近基站，负载越大，而 基站的负荷是最重的。 相比于基站的负载，边界节点的负载要小得多，这一点可以从图 以看出。 基站 的 运算能力 比 传感器节点 要强大得 多，所以基站可以进行最重的负载。如果我们 只计算除 基站和边界节点的负载， 那么得到的 负载平衡 如图 示 。从图 们可以看到， 内部节点的 负载平衡是非常完美的。 05101520250102030050100150200250300图 环形拓扑结构负载分布情况 010203001020305101520253010121416182022242628图 统计内部节点（不含边界节点和基站）负载分布情况 兰州大学硕士研究生学位论文 基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法 33 类环形拓扑结构 在负载平衡 方面取得了 良好的性能。因此，如何 构造一个如图 类环形结构图是非常重要 的。 为此，我们给出了 以下两条规则 构造类环形结构 ： ( I )当边界节点的 平均负载大于阈 值 ，把此 边界传感器节点 用 基站 代替 。 （ 当 边界传感器节点 的 平均负载大于阈值 ，将这些边界节点 更改为处理能力更强的，能够胜任负载大于 于 无线传感器节点 值小于 种节点传输半径小于基站，不能实现从边界间的一跳路由 。 示需要将边界节点变成基站的临界值， 示要将边界节点改成更强大的传感器节点的临界值。 无线传感器网络基站负载量 函数 。我们定义 ， 是一个实数，我们可以根据实际应用 取 的值 为 。 值可以按实际情况确定，例如，如果 更强大的 点 可以承担 2E 的 负载， 那么 值就取 2E。我们定义 的函数， f（ E） 。 有一种“ 线 基站 ”模块的节点就能胜任文章所说处理能 力更强大的节点，它 不是真的基站，但它的传输半径较大，相比正常的传感器节点可以处理更多的 信息 ，但远远低于实际基站。 如果增加二维网格的边界基站的数目， 那么无线传感器网络的 负载平衡将进一步改善。如果所有的边界节点 都 由基站所取代， 此时的类环形结构就变成环形结构 24， 其 负载平衡 效果 是最佳的。图 示了在 环形 拓 结构下的 载荷分布。从 图 们可以看到， 环形拓扑结构的 负载平衡是大大优于二维网状拓扑结构和 类环形 拓扑 结构 。 但是 ，基站 的造价 比传感器节点昂贵得多， 两者的造价不是 010203001020301015202530351214161820222426283032图 形结构负载分布情况 兰州大学硕士研究生学位论文 基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法 34 在一个 数量级上， 更 糟糕的是 ， 环形 拓扑 结构 中的基站非常接近， 如果二维网络的边界都用基站代替的话 ，它们将产生严重的干扰。所以 环形拓扑结构 不适合使用 在无线传感器网络中 。 除去边界节点只考虑类环形结构的内部节点，我们发现图 图 乎是 一样的 。由于我们在类环形结构里没有统计边界节点的负载，因此图 负载值小于图 负载值，在图上的反映就是图 线没有图 。但是 我们提出的二维网状拓扑结构的无线传感器网络 对于内部传感器节点来说， 几乎 达到了最佳负载平衡（接近环形结构的负载分布） 。 果评估 在无线传感器网络中， 传感器节点 从 睡眠状态 被唤醒需要 15 毫秒的 时间，还需要额外 30 毫秒的时间链接 节 到 网络 中去，使得参与无线传感器网络中的工作 。这 个时间开销 是 无线传感器网络通信 的 主要延迟时间 。在 这段 延迟时间 里 ，由基站产生的电磁波 ，以 光的传输速度约 行走了 13500 公里，这 远远大于部署在无线传感器网络里的 两个基站的距离 。因此，让基站 实现一跳 通信在整个网络的延迟时间 里 影响 可以被忽略 。 其次采用类环形拓扑结构易于维护，由于内部节点负载均衡，因此节点寿命得到保障，而边界除了基站外的节点，根据需要采用功能更强大的节点，因此 网络能得到更好的维护。基于准环形结构下的路由算法路由在保证路由长度尽可能短的情况下，实现对每个点都均衡路由。 我们 把用虚拟故障块方 法， 类环形 拓扑结构 方法，环形拓扑结构方法与没做任何处理的二维 网格 下的负载分布情况分别对他们进行仿真，并将得到 的实验结果 画成 表 ，如表 示。我们可以看到， 类环形 拓扑结构比二维网状拓扑和环面拓扑有 更 大的期望和均方误差。 这是 由于它需要 路由 到基站，所以路由路径不是最短的 ，因而平均路由长度 E 更大 。 其次， 基站承担主 要 负载，这样 均方 差 就更 大。然而，增加的负载主要集中在边界节点和基站，尤其 是基站。 让 基站承担大部分的负载 不会影响网络的使用寿命 。 其次对整个网络的维护也必将容易 ， 因为，负载大的节点都集中在边界，就算这些节点坏了也容易维修，当然我们对边界节点按照 规则 变成 更为强大的节点 ， 使得边界节点也不容易坏。 采用虚拟故障块的方 法具有最大的 E 和 ，因为几乎所有的路由路径 在 遇到虚拟故障块后 ， 需要绕着虚拟故障块的边界路由，边界上的节点就会被不断地访问 。 而且绕行故障块的过程，路由路径就会变长很多， 这 导致该 方法下的 E 是非常大的。边界节点的负载 比 其他节点相比大得多 ，可以说主要集中在虚拟故障块的边界上， 因此， 也 非常大 。 而环形结构的负载平衡是最好的，表中 E 和 都是最小的，因为环形结构中路由长度是二维网格拓扑结构的一半，且每个节点的兰州大学硕士研究生学位论文 基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法 35 负载都是均衡的。 图 表 数据的图形表示。 通过图形 我们 可以直观地发现 ，期望 E 随网格规模 的增长而降低。这是很容易理解这种现象。总路由 次数是 1000次 ， 因此对于各个规模的网络 总 的 负载 量是 几乎相同 的（这里用几乎是因为这是统计意义上的一样，每个网络的 1000 次路由都是不一样的） 。因此，更大的网 络规模 ，分配给每个节点的负载 就更小 。然而，均方误差 的变化是不一样的。 类环形 随 网 格规模 的增加 而变大 ，而 其他两种方法却 没有 随网格规模的增多而减少 。 这是因为 基站的负载 稳定在接近 250（ 1000/4）左右，即几乎 大部分 路由 都有 通过基站 。然而 网格规模变大，对应 每一个节点的负载减小，因此， 增加。剩余的 两个 方法不具有某些节点的 负载是固定的 情况 ，所以 随着网络规模的增加，分到每个节点的负载减小，因此每个节点负担的多少差别就不明显， 其 随 网络规模 的增加 而减小。举个极端的例子，网格节点无穷大，那么分配给每个节点的负载都趋于 0，这事均方差就最小，也趋于 0。 表 he of by E T=2D T=2D 5 25 0 50 00 100 兰州大学硕士研究生学位论文 基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法 36 图 兰州大学硕士研究生学位论文 基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法 37 第五章 解决二维网格容错自适应路由的死锁问题 言 大多数商业化的 多机网络 使用确定性的路由 ， 因为 其无死锁 和 并且 易于实施的。但是，自适应路由可以减少网络延迟提高网络吞吐量。它也可以比确定性路由容忍 更多 故障。但是， 自适应路由 可能引起死锁 和 活锁的问题。 死锁问题发生在 消息等待 一件 永远不会发生 的 事件。 而 活锁 问题是 消息保持无限 的路由 ，但未能 达到目的地 节点。活锁问题已经在第二章中解决，本章将着重解决基于裂痕故障块的死锁问题。 在无死锁自适应路由 中， 控制虚拟通道的数量是一个挑战性的问题，这是密切 关系到 路由器 的 缓冲 空间和 面积 大小 。这 对于使用集成 网络 的 芯片 尤其重要 。我们希望提出一种 基于二维网格，使用裂痕故障块的 无死锁自适应路由算法 ，该算法严格控制 虚拟信道 的数量。 虫洞 路由能够使 消息路由 时 避免使用节点中的存储带宽。此外，它 在 很大程度上使消息延迟 对 网络中的距离不敏感。为了减少消息阻塞的影响，物理通道可以通过 为 分成 多个虚拟通道，并为 每 一个虚拟通道提供独立的缓冲区 ，并 复 用 物理信道的带宽。虚拟通道通过动态共享物理带宽， 从而 大大提高吞吐量。如果路由算法 不 精心设计， 就 会出现死锁 问题 。在多计算机时互联网络， 当消息 因为队列中的消息系统是满的 而不能 走向它的目标 点时，死锁问题就会发生 。 在该锁定状态， 所有的 渠道陷入僵局 ，从而无法进行通信 ，直到 有某个 特殊 的 行动打破 该僵局 。 由于路由必须非常快 地做出 决定，在虫洞网络， 设计一个 避免死锁 的容错自适应路由算法 是一个切实可行的办法。 在虫洞 模型下 ， 数据被切割成一片片的数据流，被切割的最小单元为 旦消息 的 头 碎 片（ 已被信道接受，其余的微片必须 被接收完才能让 其他消息 的 微片被接受。 因此，必须 对 路由加以限制，以避免死锁。 出了 适应路由， 该方法通过确保 虚拟通道 的子集是连通且无环的确保 无死锁路由 29 8提出了一个 在 确定 性 路由 下无死锁 的 充分必要 条件。基于这种情况下，他开发了一种设计方法，定义一个通道的依赖图和 在依赖图的 渠道之间建立一个总的顺序。限制路由 按照 关系图通道的递减顺序访问 ，以取消虚拟通道依赖图的循环关系。按照这种路由规则能保证不会出现死锁 。如果该路由限制 使得 网络断开， 那么 物理信道 将会 分割成虚拟通道 重新 连接到网络。这方法已被应用到的路由芯片的 多核 设计 中 ，多节点的集成通信支持 。 兰州大学硕士研究生学位论文 基于裂痕故障块的二维网格容错自适应路由，负载平衡路由及无死锁路由算法 38 虽然 定理， 是对 确定性路由提出 的 ， 但 它已被广泛地应用于自适应路由。此外，它已被应用到组播路由。在这些情况下， 理变得有 是无死锁路由的充分条件 。一个新颖的看无死锁自适应路由的条件是转模型。然而，反过来也是基于模型达利的定理，需要信道依赖图 中 没有循环 。这种方法过于严格，限制了 能被 使用的替代路径的数量 。 在本文中，我们考虑 对网络 使用虫洞 路由的方式， 而不是存 储和转发 方式 的路由。 虫洞路由 不 需要 在一个节点中存储一个完全的数据包 ， 然后将其发送到下一个节点， 而是 直接从输入 通道 推进 数据 包包头到 输出通道 ， 每个节点仅 储存 几个流控制数 据 （ 数据碎片 ）。 数据碎片是 一个队列或通道可以接受或拒绝最小 信息 单位 。 一旦 节点检查 完 一个消息 的数据的 头 碎片，路由器就 选择下一个 通道，并按照数据碎片 开始转发 消息给被选中的 通道。 由通道转发数据碎片 ， 消息开始在 源节点 和目标 节点间实现传递 。 可能 消息的 头碎片 到达目的节点 ，而消息的最后数据片还在 源 节点哪里 。由于大多数 数据碎片 不包含路由的信息， 因此消息的数据碎 片必须路由网络 的连续通道，并 且不能够和 其他消息 相互交错 。当一个消息的头数据碎片被 阻塞 时 ， 该 消息的 其他 所有的 数据片都 停止前进 ，并且阻止 任何其他 需要使用 他们占据 的通道的消息通过 。 本文设计的解决死锁饿路由算法的基本思路就是使得通道依赖关系图中不会出现循环，从而不会出现死锁问题。这个结论已经被 明。如何路由使得基于裂痕故障块的容错自适应路由算法避免死锁问题是本文的关键。对于网络无故障的部分，是不会出现死锁，因为消息始终从当前节点沿着靠近目标节点的方向路由，下一节中我们就考虑碰到故障块的情况。 于 裂痕故障块的无死锁容错自适应路由 在介绍基于裂痕故障块的无死锁容错自适应路由之前，先来看看，虫洞路由的几个假设： 1）一个节点可以生成发往任何其他节点 的消息 。 2）确定消息采取的路由仅通过其目的 节点 ，而不是由网络的其他流量。 3）一个节点可以产生任意长度的 消 息。 消息一般比基本传输单元大 。 4）一个节点可以接收任意长度的消息。 消息到达目标节点 后 最终 被消耗掉 。 5）一旦一个队列接受消息的 第一个数