次临界随机相交图的最大连通分支

本文研究次临界情形下(即顶点度数的期望小于1)随机相交图G(n, m, p)的最大连通分支的大小.设m=[n^r].当r> 1时,随机相交图G(n, m, p)的最大连通分支和最大树分支大小都为Θ(log n),并具有相同形式的弱大数定律;当r=1时,最大连通分支不再是树分支,但最大连通分支和最大树分支的大小也是Θ(log n);当0 相似文献   

有限随机图上的随机游动和传染病模型

随机图是概率论研究的重要领域.在一个由若干图组成的集合上赋以一个概率测度,就得到一个随机图模型.关于随机图的研究主要集中于图的几何量,如最大连通分支的顶点个数、连通度、典型距离、直径、色数等,随机图模型有时也与概率论关注的其他主题进行综合,例如随机图上的随机游动和传染病模型.本文对于随机图上的随机游动和传染病模型的已有结果进行综述.     

折叠交叉立方体的分支边连通度

r-分支连通度(边连通度)是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且r是非负整数,如果G中存在某种点子集(边子集)使得G删除这种点子集(边子集)后得到的图至少有r个连通分支.则所有这种点子集(边子集)中基数最小的点子集(边子集)的基数称为图G的r-分支连通度(边连通度).n-维折叠交叉立方体FCQn是由交叉立方体CQn增加2n-1条边后所得.该文利用r-分支边连通度作为可靠性的重要度量,对折叠交叉立方体网络的可靠性进行分析,得到了折叠交叉立方体网络的2-分支边连通度,3-分支边连通度,4分支边连通度.确定了折叠交叉立方体FCQn的r-分支边连通度.     

一种基于网格模型的无限传感器网络K区域覆盖算法

目前无限传感器网络K覆盖问题的解决机制大都有颇为苛刻的假设条件,如要求节点具有很强的能量、节点的感知区域能被精确定义等.提出了一个基于布尔感知理论的分布式网格模型及相应的K区域覆盖算法,能够很好地处理感知区域形状不规则及大小发生变化的K覆盖问题,算法时间复杂度小,适用范围广泛.仿真实验证明了算法的有效性.     

应用群论方法对极小2-连通图计数

§1.引言在通讯网络和其它一些网络问题中需要研究保证一定的连通度而造价最低的网络设计问题,极小连通图的理论正是以这类实际问题为背景的.设 G=(V,E)是点集为V、边集为 E 的图,称|V|=n 为 G 的阶.若(?)v∈V,G-v 仍是连通的,则称 G 是2-连通图.一个2-连通图 G 若去掉其中任何一条边就不再是2-连通了,则称 G 是一个极小2-连通图,又称极小块.极小块早于60年代由 Dirac 和 Plummer 所研究,其后很多著作([4],[5])都对它的性质作了论述.Hobbs 于1973年用逐次加点法构造出10阶以下的全部极小块,Read 和 Hu 于1985年用压缩图法计算出12阶以下的全部极小块的数目.下面我们先给出极小块的一些性质和它的压缩图的概念.     

超越整函数的某些动力学性质

本文研究了由m个超越整函数{fl,f2,…,fm}生成的随机迭代系统的Fatou集分支的某些动力学性质.运用复动力系统理论与双曲度量理论,得到了随机迭代系统有界Fatou分支不存在的一个判别准则,同时回答了Baker所提出的问题,且给出了随机迭代系统Fatou分支为单连通的一个充分条件,推广了Bergweiler的结果.     

基于分布式极大独立集的无线传感器网络组网算法研究

运用图论理论,提出分布式无线传感器网络有效网络划分算法(RMIS)以实现WSN可靠数据传输需求.算法各节点间连通度和能量为优化约束,采用随机分布式极大独立集理论进行监测网格划分.数学证明算法在经过期望松弛同步轮数为O(log n)轮收敛.通过仿真分析,依RMIS算法划分网格可有效提高数据融合效率,减少数据传输平均距离,提高网络运行稳定性.     

(n,k)-排列图的条件连通度(英文)

点连通度是衡量互联网络容错性的一个重要参数.尽管点连通度能正确地反映了系统的容错性能,但是不能正确反映大规模网络的健壮性能.条件连通度通过对各分支附加一些要求(当整个网络被破坏时)来克服这个缺点.给定一个基于图G的网络和一个正整数l,G的R~l-连通度,记为k~l(G),定义为图G的最小节点子集的节点数,使其去掉后,G是不连通的,且每个分支的最小度至少是l.在本文中,我们得到了(n,k)-排列图的条件连通度k~l(A(_n,k))=[(l+1)k-l](n-k)-l,其中k≥l+2,n≥k+l.     

图的笛卡儿积及字典式积的连通性

文章给出了两个图的笛卡儿积及字典式的积为最大边连通的、最大连通的、super-λ,super-κ及hyper-κ的充分条件,同时证明了其中一些条件也是必要的.此外,对这两种积的局部割集和广义割集的性质也进行了考虑.     

紧带边流形到欧氏空间的嵌入

本文研究了紧带边流形到欧氏空间的嵌入问题,证明了K-连通、边界为(K-1)-连通的紧带边流形能嵌入和整齐嵌入到某些欧氏空间的一个充分必要条件;作为应用,给出了多个边界分支的K-连通紧带边流形,在每个边界分支为(K-1)-连通的情况下,到某些欧氏空间的嵌入结果。     

Optimization scheme for sensor coverage scheduling with bandwidth constraints

Wireless Sensor Network has attracted a lot of attentions due to its broad applications in recent years and also introduces many challenges. Network lifetime is a critical issue in Wireless Sensor Networks. It is possible to extend network lifetime by organizing the sensors into a number of sensor covers. However, with the limited bandwidth, coverage breach (i.e, targets that are not covered) can occur if the number of available time-slots/channels is less than the number of sensors in a sensor cover. In this paper, we study a joint optimization problem in which the objective is to minimize the coverage breach as well as to maximize the network lifetime. We show a “trade-off” scheme by presenting two strongly related models, which aim to tradeoffs between the two conflicting objectives. The main approach of our models is organizing sensors into non-disjoint sets, which is different from the current most popular approach and can gain longer network lifetime as well as less coverage breach. We proposed two algorithms for the first model based on linear programming and greedy techniques, respectively. Then we transform these algorithms to solve the second model by revealing the strong connection between the models. Through numerical simulation, we showed the good performance of our algorithms and the pictures of the tradeoff scheme in variant scenarios, which coincide with theoretical analysis very well. It is also showed that our algorithms could obtain less breach rate than the one proposed in (Cheng et al. in INFOCOM’ 05, 2005).     

Maximum lifetime coverage preserving scheduling algorithms in sensor networks

In wireless sensor networks, when each target is covered by multiple sensors, sensors can take turns to monitor the targets in order to extend the lifetime of the network. In this paper, we address how to improve network lifetime through optimal scheduling of sensor nodes. We present two algorithms to achieve the maximum lifetime while maintaining the required coverage: a linear programming-based exponential-time exact solution, and an approximation algorithm. Numerical simulation results from the approximation algorithm are compared to the exact solution and show a high degree of accuracy and efficiency.     

A framework of distributed indexing and data dissemination in large scale wireless sensor networks

Many data dissemination techniques have been proposed for wireless sensor networks (WSNs) to facilitate data dissemination and query processing. However, these techniques may not work well in a large scale sensor network where a huge amount of sensing data is generated. In this paper, we propose an integrated distributed connected dominating set based indexing (CBI) data dissemination scheme to support scalable handling of large amount of sensing data in large scale WSNs. Our CBI can minimize the use of limited network and computational resources while providing timely responses to queries. Moreover, our data dissemination framework ensures scalability and load balance as well as adaptivity in the presence of dynamic changes. Analysis and simulations are conducted to evaluate the performance of our CBI scheme. The results show that the CBI scheme outperforms the external storage-based scheme, local storage-based scheme and the data-centric storage-based scheme in overall performance.     

Sink移动的无线传感网中高连通性密钥预分配方案研究

在Sink移动的无线传感器网络中,安全性和连通性是密钥预分配方案研究中的两个难点.根据节点间安全通信的设计原理,移动Sink节点与传感器节点按一定概率进行安全通信,当网络规模较大时存在大量节点无法与移动Sink节点进行通信,从而降低整个网络的数据收集率.针对这一问题,基于算法N-PGPS为网络提供安全通信的前提下,提出了一种基于树的密钥预分配方案IN-PGPS.该方案以移动Sink节点为根节点,与其通信范围内的传感器节点构成一颗局部树,以此提高传感器节点与移动Sink节点连通的概率、提高网络连通性.分析结果表明,与已有的密钥预分配方案相比,IN-PGPS方案有效提高了网络的连通性.     

Some properties for the largest component of random geometric graphs with applications in sensor networks

In this paper we consider the standard Poisson Boolean model of random geometric graphs G（Hλ,s; 1） in Rd and study the properties of the order of the largest component L1 （G（Hλ,s; 1）） . We prove that ElL1 （G（Hλ,s; 1））] is smooth with respect to A, and is derivable with respect to s. Also, we give the expression of these derivatives. These studies provide some new methods for the theory of the largest component of finite random geometric graphs （not asymptotic graphs as s - co） in the high dimensional space （d 〉 2）. Moreover, we investigate the convergence rate of E[L1（G（Hλ,s; 1））]. These results have significance for theory development of random geometric graphs and its practical application. Using our theories, we construct and solve a new optimal energy-efficient topology control model of wireless sensor networks, which has the significance of theoretical foundation and guidance for the design of network layout.     

Two time-delay dynamic model on the transmission of malicious signals in wireless sensor network

Deployed in a hostile environment, motes of a Wireless sensor network (WSN) could be easily compromised by the attackers because of several constraints such as limited processing capabilities, memory space, and limited battery life time etc. While transmitting the data to their neighbour motes within the network, motes are easily compromised due to resource constraints. Here time delay can play an efficient role to reduce the adversary effect on motes. In this paper, we propose an epidemic model SEIR (Susceptible–Exposed–Infectious–Recovered) with two time delays to describe the transmission dynamics of malicious signals in wireless sensor network. The first delay accounts for an exposed (latent) period while the second delay is for the temporary immunity period due to multiple worm outbreaks. The dynamical behaviour of worm-free equilibrium and endemic equilibrium is shown from the point of stability which switches under some threshold condition specified by the basic reproduction number. Our results show that the global properties of equilibria also depends on the threshold condition and that latent and temporary immunity period in a mote does not affect the stability, but they play a positive role to control malicious attack. Moreover, numerical simulations are given to support the theoretical analysis.     

Modeling and optimization of energy efficient routing in wireless sensor networks

Wireless sensor networks (WSNs) have important applications in remote environmental monitoring and target tracking. The development of WSNs in recent years has been facilitated by the availability of sensors that are smaller, less expensive, and more intelligent. The design of a WSN depends significantly on its desired applications and must take into account factors such as the environment, the design objectives of the application, the associated costs, the necessary hardware, and any applicable system constraints. In this study, we propose mathematical models for a routing protocol (network design) under particular resource restrictions within a wireless sensor network. We consider two types of constraints: the distance between the linking sensors and the energy used by the sensors. The proposed models aim to identify energy-efficient paths that minimize the energy consumption of the network from the source sensor to the base station. The computational results show that the presented models can be used efficiently and applied to other network design contexts with resource restrictions (e.g., to multi-level supply chain networks).     

Universality of deep convolutional neural networks

Deep learning has been widely applied and brought breakthroughs in speech recognition, computer vision, and many other domains. Deep neural network architectures and computational issues have been well studied in machine learning. But there lacks a theoretical foundation for understanding the approximation or generalization ability of deep learning methods generated by the network architectures such as deep convolutional neural networks. Here we show that a deep convolutional neural network (CNN) is universal, meaning that it can be used to approximate any continuous function to an arbitrary accuracy when the depth of the neural network is large enough. This answers an open question in learning theory. Our quantitative estimate, given tightly in terms of the number of free parameters to be computed, verifies the efficiency of deep CNNs in dealing with large dimensional data. Our study also demonstrates the role of convolutions in deep CNNs.     

A Successive Projection Algorithm for Solving the Multiple-Sets Split Feasibility Problem

The multiple-sets split feasibility problem (MSFP) arises in many areas and it can be unified as a model for many inverse problems where the constraints are required on the solutions in the domain of a linear operator as well as in the operator's range. Some existing algorithms, in order to get the suitable step size, need to compute the largest eigenvalue of the related matrix, estimate the Lipschitz constant, or use some step-size search scheme, which usually requires many inner iterations. In this article, we introduce a successive projection algorithm for solving the multiple-sets split feasibility problem. In each iteration of this algorithm, the step size is directly computed, which is not needed to compute the largest eigenvalue of the matrix or estimate the Lipschitz constant. It also does not need any step-size search scheme. Its theoretical convergence results are also given.     

Embracing the giant component

Consider a game in which edges of a graph are provided a pair at a time, and the player selects one edge from each pair, attempting to construct a graph with a component as large as possible. This game is in the spirit of recent papers on avoiding a giant component, but here we embrace it. We analyze this game in the offline and online setting, for arbitrary and random instances, which provides for interesting comparisons. For arbitrary instances, we find that the competitive ratio (the best possible solution value divided by best possible online solution value) is large. For “sparse” random instances the competitive ratio is also large, with high probability (whp); If the instance has ¼(1 + ε)n random edge pairs, with 0 < ε ≤ 0.003, then any online algorithm generates a component of size O((log n)^3/2) whp , while the optimal offline solution contains a component of size Ω(n) whp . For “dense” random instances, the average‐case competitive ratio is much smaller. If the instance has ½(1 ? ε)n random edge pairs, with 0 < ε ≤ 0.015, we give an online algorithm which finds a component of size Ω(n) whp . © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005