检索结果-南通市图书馆

上海交通大学学报 1997年第2期31卷 1-6页

作者：李乔张翊上海交通大学应用数学系国立新加坡大学数学系

证明直径为ｌ且最小和最大度分别为３和４的无向Ｋａｕｔｚ图具有限制性连通度４，且其限制性容错直径至多ｌ＋１４．

关键词： kautz图限制性连通度限制性容错直径无向图

基于kautz图的无线传感器网络接收节点位置隐私保护算法

在线全文

学校读者我要写书评

暂无评论

南京理工大学学报 2018年第2期42卷 222-228页

作者：周倩秦小麟刘亮南京航空航天大学计算机科学与技术学院江苏南京211106 南京航空航天大学江苏省物联网与控制技术重点实验室江苏南京211106

在无线传感器网络(WSNs)中,攻击者可通过窃听网络中的数据流量和跟踪数据包捕获接收节点。现有方法通常利用注入虚假数据包和概率转发的方法来保护点位置隐私,消耗了过多的网络能量,增加了数据包延时,也降低了数据包的投递率。为此,该... 详细信息

在无线传感器网络(WSNs)中,攻击者可通过窃听网络中的数据流量和跟踪数据包捕获接收节点。现有方法通常利用注入虚假数据包和概率转发的方法来保护点位置隐私,消耗了过多的网络能量,增加了数据包延时,也降低了数据包的投递率。为此,该文提出了一种新颖的基于kautz图的分区巡逻法(ZPA)。利用分布式哈希表中构建的树形拓扑结构,将数据包传输到每个分区的交叉点,最后路由至接收节点完成数据投递。ZPA方法提高了网络的隐私安全性和鲁棒性。理论分析和仿真实验表明,与传统方法相比,ZPA可降低延时约52%,减少能耗约93%。

关键词：无线传感器网络 kautz图分布式哈希表位置隐私网络安全

kautz图K(d,n)和Kn(?)del图W(4,n)的反馈数研究

在线全文

学校读者我要写书评

暂无评论

Kautz图K(d,n)和Kn(?)del图W(4,n)的反馈数研究

作者：尹春大连理工大学

学位级别：硕士

对简单图G=(V,E),子集FcV,如果由子集V\F导出的子图不含圈,那么称子集F是图G的反馈点集,顶点数最小的子集F的顶点数称为图G最小反馈数。反馈数是互连网络拓扑结构图的一个重要参数,它可以用来估计并行处理器计算机的性能。人们重视确定... 详细信息

对简单图G=(V,E),子集FcV,如果由子集V\F导出的子图不含圈,那么称子集F是图G的反馈点集,顶点数最小的子集F的顶点数称为图G最小反馈数。反馈数是互连网络拓扑结构图的一个重要参数,它可以用来估计并行处理器计算机的性能。人们重视确定图的最小反馈点集问题研究,是由于在诸多领域内它都具有广泛的应用。例如,波长改变器在光纤网络中的安装问题、广播风暴在网络传输过程中的避免问题以及图的最小反馈点集问题都可以由计算机操作系统避免死锁问题等转化而来。实践表明,图论在设计和分析互连网络方面发挥着不可替代的作用,因为互连网络的结构可以抽象为图。通过对某些特殊互连网络拓扑结构图的研究,为设计出新一代的计算机系统提供更坚实的理论基础。本文主要采用数学归纳法与计算机算法相结合的研究方法,对以下两种类型图的反馈数的界进行研究：首先,对n≥8,本文将kautz图K(d,n)的反馈数f(d,n)的渐近公式由改进为其次研究了Knodel图W4,n的反馈数f(n),本文提出一种求W4,n的无圈子图的方法,并利用该方法证明了对于任何大于等于18的正整数n,W4,n的反馈数为：

关键词： kautz图 Kn(O|")del图反馈数

一种求解kautz图K(d,n)反馈数的改进算法

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

小型微型计算机系统 2016年第10期37卷 2279-2284页

作者：张思佳徐喜荣杨元生尹春大连海洋大学信息工程学院辽宁大连116023 大连理工大学电子信息与电气工程学部计算机科学与技术学院辽宁大连116024

研究了一类重要的互连网络拓扑结构kautz网络K(d,n)的反馈数.一个图的反馈集是指使得图G不含圈所需要移去的顶点集合,最小反馈集的阶数称为图G的反馈数.反馈集问题是经典的组合优化问题,在电路测试、操作系统解决死锁、波长转换器安装... 详细信息

研究了一类重要的互连网络拓扑结构kautz网络K(d,n)的反馈数.一个图的反馈集是指使得图G不含圈所需要移去的顶点集合,最小反馈集的阶数称为图G的反馈数.反馈集问题是经典的组合优化问题,在电路测试、操作系统解决死锁、波长转换器安装等领域都有重要的应用.确定一般网络的最小反馈点集问题属于NP问题.由于kautz图在结点规模、路径长度和容错性上的良好性质,因此适合作为构建高效、容错、可扩展的数据中心网络的拓扑结构,被认为是对超立方体网络的挑战而替代成为下一代的并行计算机互连网络之一.本文通过构造一种算法改进了n≥8时kautz网络反馈数的渐进公式,同时确定了n=9时kautz网络的反馈数为精确值.

关键词： kautz图反馈集无圈子图消圈数反馈数

一类无向kautz图的k限制边连通度的上界

在线全文

学校读者我要写书评

暂无评论

应用数学学报 2009年第2期32卷 269-276页

作者：黄学臻林上为王世英山西大学数学科学学院太原030006

在Moor-Shannon网络模型中,k限制边连通度较大的网络一般有较好的可靠性和容错性.本文在无向kautz图UK(2,n)中研究k限制边连通度的上界ξ_k,证明了ξ_5(UK(2,3))=6,ξ_5(UK(2,n)) =8,n≥4,且当4≤k≤n时,ξ_k(UK(2,n))≤2(k-「k/3」).

关键词： kautz图边连通度限制边连通度

基于kautz图的服务覆盖网带宽约束路由算法

在线全文

学校读者我要写书评

暂无评论

计算机应用 2010年第6期30卷 1443-1446页

作者：王玉林游红李广军电子科技大学计算机科学与工程学院中国人民解放军78179部队电子科技大学通信与信息工程学院

为实现服务覆盖网(SON)的服务质量保证路由,提出了一种完全分布式的带宽约束路由算法(DBRRA)。该算法以反映网络实时特性的可用带宽为路由度量,每个节点仅保持部分链路的状态,利用kautz图的自路由特性实现带宽约束的分布式路由选择。该... 详细信息

为实现服务覆盖网(SON)的服务质量保证路由,提出了一种完全分布式的带宽约束路由算法(DBRRA)。该算法以反映网络实时特性的可用带宽为路由度量,每个节点仅保持部分链路的状态,利用kautz图的自路由特性实现带宽约束的分布式路由选择。该算法具有计算复杂性低、附加开销小、自适应性强、不产生回路等优点。仿真结果表明,DBRRA的路由成功率接近基于全局状态带宽约束路由算法。

关键词： kautz图服务覆盖网带宽约束路由服务质量

基于kautz图的数据中心网络拓扑结构研究

在线全文

学校读者我要写书评

暂无评论

基于Kautz图的数据中心网络拓扑结构研究

作者：刘盛云国防科学技术大学

学位级别：硕士

近年来,随着云计算和数据密集型计算技术的飞速发展,数据中心网络作为底层基础设施发挥着越来越重要的作用,成为云计算领域的研究热点。数据中心网络向上层的分布式文件系统、结构化数据和虚拟化技术等提供可靠、高效的数据通信、计算... 详细信息

近年来,随着云计算和数据密集型计算技术的飞速发展,数据中心网络作为底层基础设施发挥着越来越重要的作用,成为云计算领域的研究热点。数据中心网络向上层的分布式文件系统、结构化数据和虚拟化技术等提供可靠、高效的数据通信、计算和存储服务。如何高效地连接数目日益增长的服务器,即如何设计数据中心网络的拓扑结构,成为了研究中的关键问题。企业界的数据中心网络以树形结构为主,但树形结构存在性能瓶颈和单点失效问题。DCell网络具有很好的带宽性能、可扩展性和容错性,其缺点是互联关系复杂,难以在大规模环境下实现。基于上述考虑,本文研究基于kautz图的数据中心网络拓扑结构及其路由协议,利用kautz图在结点规模、路径长度和容错性上的良好性质,构建高效、容错、可扩展的数据中心网络。论文的主要工作有: 基于kautz图的数据中心网络拓扑结构。针对树形结构的带宽瓶颈问题和DCell网络互联关系复杂的问题,本文利用kautz图在结点规模和路径长度上的良好性质,提出了基于层次kautz图的HUK拓扑结构,包括服务器编址方式、互联规则和增量扩展算法。HUK结构能有效地降低DCell层次结构的互联层数,简化互联结构,降低网络的布署和维护开销。同时利用kautz图在网络直径为2时的原子扩展性质,继承并改进了DCell的的增量扩展算法,支持后续服务器以HUK0为单位的灵活扩展,满足数据中心网络的可扩展性需求。针对静态的层次kautz结构设计了分布式容错路由算法。基于层次kautz结构,本文提出了在同一层次结点之间使用移位路由策略,在不同层次结点之间使用递归路由策略的HUK路由算法。同时针对网络中出现的各类失效问题,利用kautz图良好的容错性,设计了HUK容错路由策略。并利用HUK结构互联层次相对简单的特点,进一步优化了容错路由策略。由理论分析和实验结果可知,分布式路由算法在大规模HUK网络中的路径长度是可接受的,增量扩展过程中结点之间的路由性能保持较好;容错路由算法在部分设备失效的情况下能保证网络的良好运行,且容错路径长度随失效率增长的趋势较DCell结构缓慢,路径长度更优。验证HUK拓扑结构和路由算法有效性的仿真实验程序。仿真实验程序实现了HUK互联结构定义,常规路由算法,容错路由算法和增量扩展过程。本文通过仿真实验程序验证了HUK结构及其路由算法在大规模环境下的有效性。

关键词：数据中心网络组合网络结构 kautz图容错性可扩展性

de Bruijn图与kautz图的κ元控制数和特殊圈

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

de Bruijn图与Kautz图的κ元控制数和特殊圈

作者：徐建勇山西大学

学位级别：硕士

当前VLSI技术的进步,使得建造具有数千甚至数万个处理器的超大型并行分布式系统已经可以实现了.而在这些并行分布式系统中,最重要的一个步骤就是决定各个处理器之间连接的拓扑结构,即互联网络（简称网络）.这是因为网络的拓扑性质直接... 详细信息

当前VLSI技术的进步,使得建造具有数千甚至数万个处理器的超大型并行分布式系统已经可以实现了.而在这些并行分布式系统中,最重要的一个步骤就是决定各个处理器之间连接的拓扑结构,即互联网络（简称网络）.这是因为网络的拓扑性质直接影响到并行分布式系统的硬件和软件两个层面的各种设计.de Bruijn图与kautz图是应用比较广泛的两类互联网络. 出于多方面的考虑,人们期望通过一定数量的处理器来控制整个网络系统.对于无向图上控制问题的研究是近年来的一个研究热点.在一个无向图G中,称一个点控制它本身及其相邻的所有点.对于正整数κ≥1,图G的一个κ元控制集D是顶点集V（G）的一个子集,使得G中的每一个顶点被D中至少κ个点控制.图G的最小κ元控制集的基数称为κ元控制数,记为γκ（G）. 在并行处理系统中,由于圈的结构可被用于模拟网络的稳定性,所以在图中我们经常选择圈来作为考察对象.一个有向圈C的逆,记作C,是指一个满足V（C）=V（C）且A（C）={（v,w）|（w,v）∈A（C）}的圈.若存在一个同构映射σ,使得σ（C）=C,则称C是自逆的或σ自逆的. 在本文中,我们主要研究de Bruijn图与kautz图的κ元控制数和特殊自逆圈问题.本文分为四章. 在第一章,我们介绍了一些本文将要用到的有关图论方面的基本概念. 在第二章,我们研究了无向de Bruijn图（记为UB（d,n））与无向kautz图（记为UK（d,n））的κ元控制问题,主要结果如下：（1）当d≥2,2d-1≥κ≥2时, （2）当d≥2,2d≥κ＞1时, 在第三章,我们研究了在有向de Bruijn图（记为B（d,n））中,当d为偶数时的特殊圈问题,主要结果如下：（1）设n＞2为偶数,那么在B（d,n）中不存在自逆的Hamilton圈. （2）设n≥2,在B（d,n）中至少存在2/d个长度为2n的σ自逆圈. （3）当n为奇数时,在B（d,n）中存在长度至少为4的σ自逆圈当且仅当在B（d,n）中存在一条不包含交错弧和σ不动点的路P=v1v2…vk,使得（σ（v1），v1）与（vk,σ（vk））是交错弧,其中k≤（dn）/2. （4）当n为偶数时,在B（d,n）中存在长度至少为4的σ自逆圈当且仅当在B（d,n）中存在一条不包含交错弧的路P=v1v2…vk,并且路P上存在2个不动点v1与vκ,其中k≤（（dn）/2+1）. （5）当n为奇数时,在B（d,n）中至少存在2/d个长为2n的σ自逆圈. （6）在B（d,n）中至少存在2/d个长为4的σ自逆圈. （7）若C是B（d,n）中的σ自逆圈,那么L（C）是B（d,n+1）中的σ自逆圈. 在第四章,我们研究了在有向kautz图中（记为K（d,n））,当d为奇数时的特殊圈问题.主要结果如下：（1）对于d≥3,并且n≥2为偶数,那么在K（d,n）中不存在σ自逆的Hamilton圈. （2）当n为奇数时,在K（d,n）中存在长度至少为4的σ自逆圈当且仅当在K（d,n）中存在一条不包含交错弧和σ不动点的路P=v1v2…vk,使得（σ（v1）,v1）与（vk,σ（vk））是交错弧,其中k≤（dn+d（n-1））/2 （3）当n为偶数时,在K（d,n）中存在长度至少为4的σ自逆圈当且仅当在K（d,n）中存在一条不包含交错弧的路P=v1v2…vk,并且路P上存在2个不动点v1与vκ,其中k≤（dn+d（n-1））/2+1. （4）若C是K（d,n）中的σ自逆圈,那么L（C）是K（d,n+1）中的σ自逆圈.

关键词： de Bruijn图 kautz图线图 k元控制数 σ自逆圈

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

一类无向kautz图的k限制边连通性

一类无向Kautz图的k限制边连通性

作者：黄学臻山西大学

学位级别：硕士

多处理机系统的互连网络的拓扑结构通常以图为数学模型.设G=(V,E)是有限的无向简单连通图,S是G的一个边割,如果G-S的每个连通分支至少有k个顶点,则称S是k限制边割.把G的最小k限制边割所含的边数称为G的k限制边连通度,记为λ(G).k限制边... 详细信息

多处理机系统的互连网络的拓扑结构通常以图为数学模型.设G=(V,E)是有限的无向简单连通图,S是G的一个边割,如果G-S的每个连通分支至少有k个顶点,则称S是k限制边割.把G的最小k限制边割所含的边数称为G的k限制边连通度,记为λ(G).k限制边连通度作为边连通度和限制边连通度的推广,更精确地反映了一个互连网络的容错性和可靠性.对图G的任一个子图X,我们用(?)(X)表示连结X和G-X的边的数目,定义ξ(G)=min{(?)(X):v(X)=k,X连通}.称一个连通图G是极大k限制边连通图,如果λ(G)=ξ(G).称一个极大k限制边连通图G是超级k限制边连通的,如果G的每个最小k限制边割只能分离一个k阶连通子图,即G的每个最小k限制边割都是G的一个k阶连通子图的关联边集. 无向kautz图是一个重要的图类,它被广泛地应用在互连网络的设计和分析上.本文主要研究一类无向kautz图UK(2,n)的k限制边连通性. 在第一章第一节,我们给出本文将用到的图论方面的主要术语和记号,以及连通性方面的基本概念和基本结论.在第二节,我们介绍了无向kautz图的基本概念和基本结论. 本文第二章第一节研究无向kautz图UK(2,n)的k限制边连通度的上界ξ,证明了(?),且当n≥4时,(?).在第二节,我们证明了当4≤k≤n时,(?). 在本文第三章中,我们先给出了已有的无向kautz图的k限制边连通性方面的结论.在第二节,首先证明了当n≥4和5≤k≤v/2时,ξ(UK(2,n))≥7,并由此得到一个重要的结论:当n≥4时,UK(2,n)是超级4限制边连通的.

关键词：可靠性互连网络 kautz图边连通度限制边连通度

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

kautz图的等周数的一个新上界

洛阳师范学院学报 2002年第5期21卷 5-9页

作者：杨家亮吕可波大连理工大学应用数学系辽宁大连116024

kautz和DeBruijn图由于其在大型计算机互联网上的应用而被人们广泛的研究 ,互联网的一个重要的参数是它的等周数 .Deplorme和Tillich运用特征值技术发现了kautz和De Bruijn图等周数的一个上界 (见文献 [1 ]) .Bulterman给出了一个构造... 详细信息

kautz和DeBruijn图由于其在大型计算机互联网上的应用而被人们广泛的研究 ,互联网的一个重要的参数是它的等周数 .Deplorme和Tillich运用特征值技术发现了kautz和De Bruijn图等周数的一个上界 (见文献 [1 ]) .Bulterman给出了一个构造性的方法改进了DeBruijn图等周数的上界 (见文献 [2 ]) .我们运用该构造方法得到了kautz图的一个新的上界 .

关键词：上界等周数 kautz图无向图特征值构造方法图论