OTIS网络的支配集问题算法研究

图的最小支配集问题和最小连通支配集问题在网络与并行分布式计算中有重要应用,计算上它们都属于NP难问题。OTIS网络是一类可以任意图为因子网络的复合网络,它能继承因子网络的良好特性,因而成为可扩展性、模块化、容错性的大规模并行计算机系统的体系结构形式之一。研究如何构建OTIS网络的较小支配集和连通支配集。基于OTIS网络构图规则,分别根据因子网络的支配集算法和连通支配集算法得到了求解OTIS网络的支配集算法和连通支配集算法。从理论上分析了这些算法的性能,并通过实例进行了验证。     

一种构建超大规模数据中心的模块化网络结构

模块化数据中心网络的模块间互联结构和路由负责模块的有效组织,以及不同模块服务器间的高效通信.为此,如何设计具有高带宽、高容错和高可扩展能力的互联结构以支持大规模、超大规模数据中心的构建成为模块化数据中心网络需要解决的首要问题.提出了一种构建超大规模模块化数据中心的模块间互联结构MDKautz,该结构通过模块内大量未被使用的交换机预留高速端口将模块以Kautz图互连,在无需额外增加任何高端交换设备的前提下,构造出具有高带宽、高容错和灵活可持续扩展性的超大规模数据中心网络.对MDKautz的构建方法、路由策略以及扩展方法进行了分析,数学分析和模拟实验结果证明了该新型网络结构具有良好的拓扑特性和通信性能,可有效支持数据中心高带宽、高容错的典型应用.     

THUDS系统互连网络容错性的分析研究

混合组混洗互连网络是我们的THUDS实验性分布计算机系统采用的一种新型互连网络。本文着重分析和研究了这种网络的容错性能,指出对于一个有N=m·r~m个结点的这样的网络(正常情况下网络直径为2m-1),在有m(r-1)-1个结点失效的情况下,能在3m+[2·logrm]+2步内实现任意正常结点间的通信。本文还将该网络同最近发表的一些具有容错直径的互连网络就容错性能进行了比较,结果表明,混合组混洗网络具有最优的容错性能。     

一类数据中心网络中顶点独立生成树的一种通用构造方法

数据中心网络设计的新趋势是在互连网络的顶点和边上分别部署交换机和双端口服务器,其逻辑图可以抽象为复合图.顶点独立生成树(node-independent spanning trees,NIST)是数据中心网络中的一种重要结构,可用于设计数据中心网络中的可靠通信协议,容错广播和安全消息分发,IP快速重路由等.给定一个复合图G(Kn),首先表明,如果图G的直径为d,则复合图G(Kn)的直径为2d或2d+1.假设n-正则、n-顶点连通的互连网络G中存在以任一顶点为根的n棵NIST,通过提出一种时间复杂度O(N)的高效算法(其中N是顶点数),给出了G(Kn)中一种构造n棵NIST的通用方法.对复合图Qn(Kn)的顶点分析表明,NIST的最大高度仅为其直径加3.另外,基于增广立方体的数据中心网络上的模拟实验也从另一个方面证明了上述结论的正确性.     

基于Cayley图的三维六度环面网络研究

提出了一种三维六度环面Cayley图网络模型.针对该网络模型,给出了一种简单的三维节点编址方案,并利用该编址方案得到了任意两个节点间的最短距离公式;开发了一种简单的分布式最优路由算法,该算法可以运行于网络中的任意节点,可以建立任意两点之间的最短路由路径;基于陪集图(coset graph)理论,给出了一种新型的广播通信算法,并对该算法的效率进行了分析;给出了三维六度环绕网络模型直径的界限值.     

连环图：一种新的多计算机系统通信体系结构

本文根据Ｃａｙｌｅｙ图模型，提出了一种新的互连网络，它具有预点对称性。固定的顶点度、易于路由、通信延迟小以及容错等特点。本文给出了这种互连网络的路由算法和容错路由算法，证明了其连通度为３。     

MDCent:一种高可扩展、高吞吐量的模块间互连结构

近年来,提出的以服务器为中心的新型数据中心网络互连结构部分程度地解决了传统树型结构面临的性能瓶颈和可扩展性难题,同时出现了以集装箱为基本模块构建超大规模的数据中心.然而,如何设计模块之间的互连结构,确保数据中心网络具有高可扩展性、模块之间具有高带宽是一个非常具有挑战性的问题.以BCube为代表的新型数据中心网络,能够将数千台服务器互连在一个集装箱内,且对各种典型流量模式提供较高的带宽.提出了一种常量度数的模块之间的互连结构MDCent.MDCent基于BCube结构进行模块内服务器互连,利用模块内大量未被使用的上行端口,在各个模块保持常量度数的情况下,能够保证模块之间具有高可扩展性,同时模块之间具有较高的带宽.     

交叉立方体在两种策略下的可诊断性

互连网络可诊断性度的高低是衡量这种网络性能优劣的重要标志二交叉立方体是近年提出的一类互连网络，它有一些比超立方体更好的性质．本文用PMC模型证明了n维交叉立方体Dn在精确策略和悲观策略下分别是n-可诊断的和（2n－2）／（2n－2）一可诊断的，从而证明民在这两种策略下的可诊断性度与n维超立体的相同．另外，本文在证明Dn是n-可诊断的同时，还得到了Dn中任何两顶点之间的n条互不相交的路径，它们可作为容错远路的依据．     

具有自适应性的star网络容错寻径策略研究

大规模并行处理机系统中寻径算法对互连网络的通信性能和系统性能起着至关重要的作用,而star互连网络作为超立方体网络的最好替代之一,其寻径问题的解决变得非常重要。在有条件的容错模型基础上,对寻径时的规则进行了研究,提出了一种基于自适应规则的容错寻径算法。对算法的正确性以及容错性进行了分析。经仿真实验证明了该算法具有较高的成功概率。在边失效独立的情况下,对star网络终端对间通信可靠性进行了分析,推导出了其约束下界,并给予了证明。     

简化数据变换网络与全交叉网络拓扑等价的多套逻辑名矩阵

用光互连取代电互连实现多处理机系统的互连通信具有潜在的优势。本文提出了互连网络逻辑名结构的矩阵表示形式，并采用互连网络拓扑等价的图分析法获得了简化数据变换网络与全交叉网络拓扑等价的四套逻辑名矩阵，为拓展光互连简化数据变换网络系统的互连功能，提高其性能价格比提供了理论依据。     

基于贝叶斯网络的体域网多模态健康数据融合方法

体域网作为无线传感器网络在生物医学领域的一个重要分支能够远程实时监测人体多项健康数据.针对基于体域网采集到的多模态健康数据融合与分析方法进行研究,设计了一套包括动态心电传感器、血压传感器和血氧饱和度传感器的体域网组网方式,提出了一种基于贝叶斯网络模型和推理算法的心肌缺血监测识别方法.通过对60例确诊心脏病患者施行单一模态动态心电监测和多模态健康数据监测对比实验,验证了所提出的多模态健康数据融合方法能够有效提高无症状性心肌缺血的检出率,为临床应用提供了一种新的辅助判别手段.     

A lightweight distributed scheme for mitigating inter-user interference in body sensor networks

Inter-user interference deteriorates reliable communication in body sensor networks (BSNs) when multiple BSNs are transmitting simultaneously in close proximity to each other. This paper presents a lightweight and distributed inter-user interference mitigation (IIM) scheme, that can be easily integrated with the IEEE 802.15.4 protocol stack. The proposed scheme takes into consideration the generic property of low channel utilization in BSNs and enables affected BSNs to adaptively reschedule their transmission time or switch channels. Based on the detected information from neighboring BSNs, BSNs reschedule their transmissions in a distributed and coordinated manner, so that wireless channels can be effectively utilized by multiple BSNs. Moreover, the IIM scheme is performed only when the performance of the BSN is degraded to an unacceptable level due to severe interference to reduce the rescheduling cost. Simulation results show that the proposed scheme improves the network throughput by 18% and reduces the energy consumption by 22% as compared with the existing beacon schedule scheme.     

A sensitive data aggregation scheme for body sensor networks based on data hiding

Body sensor networks (BSNs) enable the pervasive, long-term, and real-time monitoring in any environment and without restriction of activity. Security and privacy are extremely critical issues of BSNs, as sensitive information is transmitted through the wireless network. This paper proposes a novel sensitive data aggregation scheme based on data hiding for BSNs, namely SDAS. SDAS adopts the packet combination based on the sensitive data aggregation tree built in each BSN to reduce the transmission energy consumption by eliminating transmitted redundancy. After lossless compression, the compressed sensitive data are embedded into various ordinary data in the combined packet by using a lightweight data hiding algorithm to prevent the disclosure of the sensitive data and avoid arousing the attention of attackers. Extensive analysis demonstrates that our proposed scheme can ensure a high level of security and privacy of the sensitive data without affecting the ordinary data quality, while delivering low power consumption.     

On fault tolerance of 3-dimensional mesh networks

In this paper, the concept of k-submesh and k-submesh connectivity fault tolerance model is proposed. And the fault tolerance of 3-D mesh networks is studied under a more realistic model in which each network node has an independent failure probability. It is first observed that if the node failure probability is fixed, then the connectivity probability of 3-D mesh networks can be arbitrarily small when the network size is sufficiently large. Thus, it is practically important for multicomputer system manufacturer to determine the upper bound for node failure probability when the probability of network connectivity and the network size are given. A novel technique is developed to formally derive lower bounds on the connectivity probability for 3-D mesh networks. The study shows that 3-D mesh networks of practical size can tolerate a large number of faulty nodes thus are reliable enough for multicomputer systems. A number of advantages of 3-D mesh networks over other popular network topologies are given.     

一个有效的动态网络节点影响力模型

网络节点影响力度量对社会网络研究具有重要的价值,静态网络的影响力度量是目前研究的主要问题。然后社会网络的结构经常会随着时间变化,呈现出动态网络。静态网络节点影响力度量模型虽然可以对动态网络不同时间点上的快照进行度量,然后这种机制很难刻画动态网络节点影响力的变化过程。本文将动态网络建模为不同时间点网络的叠加快照,然后构建了动态网络边权重衰减和节点影响力衰减机制,基于衰减机制提出了动态网络节点影响力模型,模型可以应用于加权或无权动态网络节点影响力度量。为了客观衡量本文模型的性能,在一个模拟网络和三个真实网络进行了不同实验。在模拟网络上,将结果与人工标注的结果计算肯德尔系数,针对三个真实网络则进行了不同角度的影响力效果分析。实验结果表明本文模型不仅可以较好的刻画动态网络节点影响力的变化过程,还可以准确度量动态网络节点影响力。     

加权迭代节点匹配算法及其在语言网络中的应用

复杂网络间节点匹配在很多领域中均具有重要现实意义。然而,传统的节点匹配算法通常只利用网络的局部拓扑信息,在对拥有高对称性的真实网络作用时往往会失效。为了克服这一缺点,我们近期利用网络拓扑信息和连边权重信息,提出了一种新型的同时来计算不同网络间节点相似度的方法,并在此基础上设计了一种加权迭代节点匹配算法。将该算法在高度拓扑对称仿真网络对和真实中英文语言网络对上分别进行了测试,结果表明加权迭代节点匹配算法在此类网络上优于纯拓扑迭代节点匹配算法。     

Adaptive synchronization of uncertain coupled stochastic complex networks

In this paper, the problem of adaptive synchronization of uncertain coupled complex networks is investigated. Some controllers and adaptive laws are designed to ensure achieving synchronization of a general complex network model. In particular, synchronization of coupled stochastic networks subject to random perturbations is studied, with a referenced node introduced as the target node for synchronization. An example is simulated on delayed neural networks coupled in a small‐world network topology, which demonstrates the feasibility and effectiveness of the proposed adaptive control method. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Fully symmetric swapped networks based on bipartite cluster connectivity

The class of swapped or OTIS (optical transpose interconnect system) networks, built of n copies of an n-node cluster by connecting node i in cluster j to node j in cluster i for i≠j, has been studied extensively. One problem with such networks is that node i of cluster i has no intercluster link. This slight asymmetry complicates a number of algorithms and hinders both theoretical investigations and practical pursuits, such as building parallel node-disjoint paths for fault tolerance. We introduce biswapped networks that are fully symmetric and have cluster connectivity very similar to swapped/OTIS networks. We derive basic topological parameters, present a simple distributed shortest-path routing algorithm, and point to a number of other interesting properties under investigation for biswapped networks.     

加权社会网络中重要节点发现算法

从社会网络中发现重要节点是一个很有意义的研究问题,目前多数重要节点发现方法是基于不加权网络。由于在社会网络中,节点之间的关系具有强弱差异,社会网络本质上是一个加权网络。对于加权社会网络中的重要节点发现较少有研究。利用节点交互,提出了节点间关系强度的一种度量方法,该方法考虑了节点局部有向交互特征与全局交互特征。利用节点的行为特征定义了节点活跃度。 采用关系强度作为边的权重,活跃度作为节点权重形成了加权社会网络。基于PageRank算法的思想,提出了两个改进算法,算法采用节点权值作为阻尼系数,在迭代式过程用边的权重代替了PageRank算法中的入边和。分别选择国内外具有代表性的2个社交网络上的数据集进行大量实验,并分别选择了不同的方法作为比较,实验结果表明改进算法能较好地发现加权社会网络中的重要节点。     

基于时间部署的无线传感器网络密钥管理方案

提出一种基于时间部署的随机密钥管理方案.该方案采用了特殊的两级随机密钥预分配和清除机制以及按时间顺序的成组部署方法:每个传感器节点从多个密钥池中随机选择密钥并在一定条件下删除相关的密钥;所有传感器节点被组织成部署组并按时间顺序被部署到网络中.与经典的随机密钥管理方案相比,该方案在为成对密钥的生成提供了较高的节点连通度的同时,提高了节点资源利用率并且增强了网络抵抗节点受损攻击的能力.