构建一类新网络簇的可靠性控制集

网络的可靠性研究也称网络的容错性研究,一般分为容错性分析和容错性设计两个方面,有时容错性设计也称网络的容错性综合.容错性研究指的是假设网络的站点和连线以独立且相等概率失效情形下的可靠性分析.即计算一个已知网络因站点或站点之间的连线出现故障而引起整个网络失效的概率,或者在点边出现故障概率已知的情况下设计一个网络使其出现故障的概率最小.对于具有n个站点e条连线的所有不同拓扑结构的连通无向网络拓扑所组成的簇Ω(n,e)叫做网络簇,也叫簇网络.一般认为在每个网络簇中肯定存在一个网络,它的容错性要比该网络簇巾其它网络的容错性好.事实上有些网络簇巾不存在一致最优可靠性网络,但可以在这样的网络簇中找几个这样的网络,使得该网络簇中其它网络的容错性要比这几个网络中的某一个小.由这几个网络的容错性来衡量整个网络簇的容错性,而这几个被选定的网络所组成的集称之为这个网络簇的可靠性控制集.文中给出了当n≥8且为奇整数时,构建一类新网络簇Ω(n(n-1)/2-n+5/2的可靠性控制集.了当n≥8且为奇整数时,构建一类新网络簇Ω(n,(n-1)/2-n+5/2)的可靠性控制集.     

无线传感网络中能量均衡的连通支配集算法

连通支配集是无线传感器网络中构建虚拟骨干网络的重要手段.由于支配集中节点的能耗相对其他节点要多,支配集中剩余能量较小的节点决定了虚拟骨干网的生命周期.现有算法或者只是关注构造较小的支配集,或者没有考虑调整能耗极快的支配节点.提出了一种能量均衡的连通支配集算法,基于节点剩余能量和连通度构造支配集,在网络运行过程中根据耗能速度,提前选择候选支配节点,分流负载过重的支配节点.仿真结果表明,新算法能以较小消息开销,有效延长网络寿命.     

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

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

一种利用水平集的图像分割快速GPU并行算法

研究医学生物图像的快速分割问题。针对传统图像分割算法效率低、分割不准确的缺陷,提出一种利用水平集自动演化获得最优图像分割的方法。首先,定义水平集方程,并针对方程中不同分量进行分析,确定以图像灰度为依据的最优化算法;然后通过对差分方程的离散化,定义最优化算法的求解步骤,并使得该最优化计算方法能并行化处理。该方法可以有效地对医学图像进行分割,尤其适合并行化GPU处理,在确保图像分割质量的前提下,极大地提高了运算效率。     

基于水平集方法的航拍图像运动分割

针对航拍图像由于受噪声和光照影响导致分割精度差问题,将一种改进的C-V水平集方法引入到航拍图像运动分割中.首先对C-V模型作了改进,通过引入新的能量项使改进方法无需重新初始化符号距离函数,在保证分割精度的同时提高了分割速度;其次对水平集函数的偏微分方程进行改进,消除了原始C-V方法对远离实际边缘的轮廓曲线进化的抑制作用.实验结果显示,改进方法能有效地分割出航拍图像中的运动目标,在初始轮廓线远离目标实际轮廓时也能够正确分割,并能更好地满足实时性的要求.改进方法具有分割精度高,耗时少的优点,可用于航拍图像运动目标检测跟踪系统.     

LAN/WLAN集成网络的可靠性评估及预测研究

以LAN/WLAN集成网络为例,首先从业务性能的角度给出了网络可靠性的定义,并基于此定义利用熵权双基法对其进行了可靠性评估;然后利用一种新的改进PSO-BP融合算法建立了可靠性预测模型,并以可靠性评估数据为样本设计了三组实验,仿真结果证明了该模型在网络可靠性预测精度方面的优越性。     

基于边分割的社交网络敏感边保护技术

用户间的敏感关系是社交网络中用户的重要隐私信息。为了解决社交网络中用户间敏感关系泄露问题,提出一种边分割算法。首先,将已删除敏感边的简单匿名社交网络的非敏感边分割成多条子边;然后,将原非敏感边携带的信息分配到子边上,使得每条子边只携带原非敏感边的部分信息,从而生成具有隐私能力的匿名社交网络。理论分析和仿真实验结果表明,相比cluster-edge和cluster-based with constraints算法,边分割算法在保证数据具有较高可用性的情况下能更大限度降低敏感关系泄露的概率,泄露概率分别降低了约30%和20%,因此所提算法能够有效解决社交网络中敏感关系泄露问题。     

一个无线传感器网络的网络分割模型

首先指出网络分割会影响网络连通性，并进而影响网络的通信效率；接着从物理层和MAC协议入手，讨论了导致无线传感器网络网络分割问题的通信因素。为了定量地刻画网络分割，定义了网络分割比，并分析了影响网络分割比的物理及几何因素。通过试验采集的大量数据及曲线族拟合法，建立了一个无线传感器网络的网络分割模型，定量地确定了网络节点数、面积比与网络分割比的数学关系。     

基于最小连通支配集的无线传感器网络容错研究

过多的跳数对于无线传感器网络容错是不利的。无线传感器网络以往的研究中最小连通支配集主要是作为骨干网来使用,通过结合度来构建最小连通支配集,使得所构建的最小连通支配集不仅具备骨干网的功能,还具有容错的作用。提出了构建具有容错作用的基于度的最小连通支配集算法,仿真证明该算法可以有效地减少无线传感器网络的跳数,从而达到增强无线传感器网络容错的目的。     

无线传感器网络中的连通支配集求解算法

连通支配集在无线传感器网络中有着重要的作用,通过对连通支配集的深入分析得到了关于连通支配集的一个新特性,即最小连通支配集是图的一棵包含最多叶子节点的生成树中的非叶子节点的集合。根据这个结论设计了一种全新的连通支配集求解算法,即通过建立一棵含叶子节点较多的生成树来寻找一个较小的连通支配集。仿真实验表明,新算法较前人的算法有明显的改进。     

Computing the Scattering Number of Graphs

The scattering number of a noncomplete connected graph G is defined by s ( G )= max{ y ( G m X ) m X X ² V ( G ), y ( G m X ) S 2}, where y ( G m X ) denotes the number of components of G m X . This parameter can be used to measure the vulnerability of networks. It shows not only the difficulty to break down the network but also the damage that has been caused. In this paper, we prove that the problem of computing the scattering number of a graph is NP-complete. At the same time, the scattering numbers of grids and those of Cartesian products of two complete graphs are determined.     

一种提高UDP传输可靠性的简捷方法

UDP通信简单且支持组播,在工程中得到广泛应用,但是传输是不可靠的。为了解决传输可靠性问题,经常采用多数判决机制或应答确认机制,但这些机制都或多或少地增加了程序的复杂性,带来了一些其他的问题,比如延时和不稳定等。针对这一问题,提出了对帧序号进行判决的重发机制,对接口格式及收发双方的程序逻辑进行了简要介绍。经过工程实验验证,该方法简便有效,切实可行。     

On the Crossing Number of Complete Graphs

Let (G) denote the rectilinear crossing number of a graph G. We determine (K₁₁)=102 and (K₁₂)=153. Despite the remarkable hunt for crossing numbers of the complete graph K_n – initiated by R. Guy in the 1960s – these quantities have been unknown forn>10 to date. Our solution mainly relies on a tailor-made method for enumerating all inequivalent sets of points (order types) of size 11. Based on these findings, we establish a new upper bound on (K_n) for general n. The bound stems from a novel construction of drawings of K_n with few crossings.     

Image‐Based Edge Bundles: Simplified Visualization of Large Graphs

We present a new approach aimed at understanding the structure of connections in edge‐bundling layouts. We combine the advantages of edge bundles with a bundle‐centric simplified visual representation of a graph's structure. For this, we first compute a hierarchical edge clustering of a given graph layout which groups similar edges together. Next, we render clusters at a user‐selected level of detail using a new image‐based technique that combines distance‐based splatting and shape skeletonization. The overall result displays a given graph as a small set of overlapping shaded edge bundles. Luminance, saturation, hue, and shading encode edge density, edge types, and edge similarity. Finally, we add brushing and a new type of semantic lens to help navigation where local structures overlap. We illustrate the proposed method on several real‐world graph datasets.     

基于移动传感器网络的节能目标跟踪

首先证明最小化移动传感器网络的目标跟踪能耗是 NP 完全问题, 并基于邻近图理论提出一种近似最优的分布式引导跟随算法. 每一时刻离目标预测位置中心较近的节点引导较远处节点向中心移动, 逐步覆盖目标下一时刻可能在的区域, 整个网络在跟踪全程保持连通. 证明该算法的节点运动能耗在数值上逼近最小能耗. 仿真结果进一步验证了该方案的有效性.     

仿真技术在通信网可靠性研究中的应用

论文主要对用仿真技术来研究通信网的可靠性的一些基本技术作探讨,就目前通信网可靠性研究中的观点和方法作简要归纳,并对运用仿真方法来求出通信网的可靠性测度之一的全网端间业务完成性作了较具体的阐述。     

Inequalities for the Number of Walks in Graphs

We investigate the growth of the number w _k of walks of length k in undirected graphs as well as related inequalities. In the first part, we deduce the inequality w _2a+c ?w _2(a+b)+c ≤w _2a ?w _2(a+b+c), which we call the Sandwich Theorem. It unifies and generalizes an inequality by Lagarias et al. and an inequality by Dress and Gutman. In the same way, we derive the inequality w _2a+c (v,v)?w _2(a+b)+c (v,v)≤w _2a (v,v)?w _2(a+b+c)(v,v) for the number w _k (v,v) of closed walks of length k starting at a given vertex v. We then use a theorem of Blakley and Dixon to show $w_{2\ell+p}^{k}\leq w_{2\ell+pk}\cdot w_{2\ell}^{k-1}$ , which unifies and generalizes an inequality by Erd?s and Simonovits and, again, the inequality by Dress and Gutman. Both results can be translated directly into the corresponding forms using the higher order densities, which extends former results. In the second part, we provide a new family of lower bounds for the largest eigenvalue λ ₁ of the adjacency matrix based on closed walks. We apply the Sandwich Theorem to show monotonicity in this and a related family of lower bounds of Nikiforov. This leads to generalized upper bounds for the energy of graphs. In the third part, we demonstrate that a further natural generalization of the Sandwich Theorem is not valid for general graphs. We show that the inequality w _a+b ?w _a+b+c ≤w _a ?w _a+2b+c does not hold even in very restricted cases like w ₁?w ₂≤w ₀?w ₃ (i.e., $\bar{d}\cdot w_{2}\leq w_{3}$ ) in the context of bipartite or cycle free graphs. In contrast, we show that surprisingly this inequality is always satisfied for trees and we show how to construct worst-case instances (regarding the difference of both sides of the inequality) for a given degree sequence. We also prove the inequality w ₁?w ₄≤w ₀?w ₅ (i.e., $\bar{d}\cdot w_{4}\leq w_{5}$ ) for trees and conclude with a corresponding conjecture for longer walks.     

On the Stab Number of Rectangle Intersection Graphs

Theory of Computing Systems - We introduce the notion of stab number and exact stab number of rectangle intersection graphs, otherwise known as graphs of boxicity at most 2. A graph G is said to be...     

具有大量错误结点的超立方体网络中的单播路由算法的设计与分析

本文讨论具有大量错误结点的超立方体网络中的单播路由算法，假定Hn是一个局部3－维子立方体连通的n-维超立方体网络并且每一个基本的3－维子立方体中分别最多有1个和2个错误结点，本文提出的单播路由算法能够在线性时间找到路径长度分别为源结点和目的结点之间大约1．5倍和2倍海明距离的次优路径，我们提出的单播路由算法只需要结点知道其邻结点的状态，而无需知道整个网络信息，也就是说，该算法是基于局部信息的，因而该算法具有很强的实际意义。