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

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

无向Kautz图的超级限制边连通性(英文)

限制边连通度作为边连通度的推广,是计算机互连网络可靠性的一个重要度量.Superλ-′是比限制边连通度更精确的一个网络可靠性指标.一个图是Superλ-′的,如果它的任一最小限制边割都孤立一条有最小边度的边.本文考虑一类重要的网络模型-无向K autz图UK(d,n)的限制边连通度λ,′证明了当d 3,n 2时,λ(′UK(d,n))=4d-4,并进一步指出此时的UK(d,n)是Superλ-′的.

有向Kautz图的超级限制弧连通性

限制边连通度是比传统的边连通度更精确的网络可靠性指标.限制边连通度在有向图中有4个推广,分别对应有向图的4种限制弧连通度.有向Kautz图可以作为多处理机系统的基础拓扑,是一类重要网络.证明了有向Kautz图K(d,n)的4种限制弧连通度都为2d-2,并且确定了对应的最小限制弧割的结构特征.

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

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

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

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

有向Kautz图的好邻连通度

有向Kautz图是并行计算系统的一类重要网络。根据实际应用中并行计算系统的故障分布情况,提出了有向图的好邻连通度的概念,该连通度是比传统连通度更精确的网络可靠性指标,并证明了有向Kautz图K(d,n)的好邻连通度为2d-2。

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

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

无向de Bruijn图和Kautz图的k元控制

在无向图G中,对于正整数k≥1,图G的一个k元控制集D是顶点集V(G)的一个子集,并且使得G中的每一个顶点至少被D中k个点控制.文章给出了在无向de Bruijn图和Kautz图中最小k元控制集的基数.

基于Kautz图和OPS的多层光分组交换网络调度准则研究

多跳光网络是满足日益增长的互联网服务应用的最合适的解决方案。将常规的Kautz图从一层扩展为多层,以产生更多架构上的变化。相邻层之间采用常规Kautz图的系统连接方式,并由此提出了一种基于属性的路由算法。采用光无源星形耦合器来实现新的拓扑结构。为了解决中间节点争用问题,评估并比较了三个调度准则,主要原则是它们提高可用性的能力。

无向 Kautz 图的限制性连通度和限制性容错直径

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

SKY:基于分布式Kautz图的高效P2P网络

P2P网络通常基于特定的网络拓扑图。给定静态拓扑图,处理节点加入退出的动态维护机制对P2P网络的性能具有重要影响。Kautz图具有常量度数、低拥塞以及最优网络直径等优良特性,然而,由于动态拓扑维护的复杂性,现有的P2P网络只能够基于以2为基(base)的Kautz图进行构建。针对该问题,面向基于Kautz图的P2P网络的拓扑维护需求,文中提出一种分布式Kautz(distributed Kautz,D-Kautz)图技术。利用D-Kautz图技术,进而提出了一种新颖的P2P网络-SKY,SKY是第一个能够基于以任意大于1的正整数为基的Kautz图进行构建的有效的P2P网络,通过理论分析和模拟实验,对SKY的有效性进行了验证。

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

在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」).

图的圈边连通度和圈弧连通度

令G是一个简单图.G的圈边连通度cλ(G)定义为E(G)的一个子集F的最小基数,其中G−F不连通且至少有两个分支包含圈.令D是一个有向图.D的圈弧连通度λ_(c)(D)定义为A(D)的一个子集S的最小基数,其中D−S不强连通且至少有两个强连通分支包含有向圈.在文章中,我们研究了无向二元Kautz图、无向de Bruijn图和无向二元广义de Bruijn图的圈边连通度.而且,我们获得了Kautz有向图、de Bruijn有向图和广义de Bruijn图的圈弧连通度.

一种QoS有保障的Web服务分布式发现模型

如何动态地选择、绑定并调用最适合用户需求的Web服务备受研究领域的关注.提出了一种QoS有保障的Web服务分布式发现模型,具体研究基于QoS约束的服务发现问题,以及如何提高服务发现系统的可用性问题.研究Web服务的三维QoS模型并设计基于QoS约束的服务选择算法.提出集成服务选择算法的UDDI(universal description,discovery,andintegration)兼容扩展模型,并运用可扩展Kautz图和Bloom Filters理论,提出分布式UDDI的实现机制.该模型的原型系统在国家地质调查网格中得到应用,测试结果显示:扩展UDDI模型具有很高的查准率、响应率以及较好的负载均衡能力,而模型的分布式实现机制在保障查询性能的前提下,提高了发现系统的有效性和可用性.

一种适用于移动对等网络的分簇算法

通过分簇算法减小网络振动效应,延长网络的寿命是移动对等网络的研究重点之一。在研究Kautz图及其特性的基础上,提出一种基于Kautz图的移动对等网络分簇算法。在算法中,定义地址空间树,使用Kautz串作为节点标识,并运用后根序和宽度优先算法遍历地址空间树等一系列技术生成簇。同时设计了相关机制管理和维护簇结构,保证结构一致性。理论证明和实验评估表明,该分簇算法能有效减小振动效应,延长网络寿命。

无线传感器和执行器网络可靠高效路由

针对当前的无线传感器与执行器网络(WSAN)技术缺乏实时性能以及工业无线环境的动态性问题,基于Kautz图设计容错、实时、高效、可靠的先验式路由FRER,不需要维持路由表,只利用节点IDs,根据节点IDs的匹配长度快速找到目标节点的最短路径.当节点故障时,不需要进行路径重挑,根据自身ID与目标节点ID的匹配,上一跳节点能够快速找到剩余节点的最短路径.考虑路径的多样性,不局限于Kautz拓扑,利用邻居节点信息拓展网络中路径的多样性.考虑链路故障,基于链路可用性历史信息组合多路径,保证在链路故障情况下网络维持可接受水平的路由路径可用性.实验结果表明,与REFER和Debruijn图相比,FRER在实时性、容错性和可靠性性能上优于两者.

P2P信息管理系统中的容错方法

FissionE是一种基于Kautz图的P2P信息管理系统网络架构,在给定节点度数(d = 2)下具有最优的网络直径。针对结点失效导致的FissionE路由性能较差的问题,本文对FissionE的容错路由算法进行研究,其基本思想是:如果下一跳结点失效或网络连接失效,那么将采用某种方法“绕过”失效的结点或连接,从而获得较好的路由性能。

图的超级限制边连通性

在Moor-Shannon网络模型中,边连通度和限制边连通度较大的网络一般有较好的可靠性和容错性.本文证明:除两种平凡情形外,无向Kautz网络的拓扑结构,无向Kautz图UK(2,n)是超级限制边连通的.因此,它们比de Bruijn网络有更好的限制边连通性.