共查询到20条相似文献,搜索用时 15 毫秒
1.
在并行计算机系统中,Mesh网络是最重要的网络拓扑结构之一。该文研究了基于结点出错概率Mesh网络的连通性,提出了k-Mesh子网连通的概念,运用严格的数学推理,推导出网络结点出错概率和Mesh网络的连通概率之间的关系。研究表明:特定的Mesh网络能保持相当高的连通概率,例如,笔者严格证明了,当网络结点出错概率控制在0.1%以下,则对多达几十万个结点的Mesh网络,网络连通的概率仍可保持在99%以上。 相似文献
2.
Mesh网络是大型多处理器并行计算机系统中极为重要的拓扑结构.本文提出了一种计算Mesh网络连通概率的新方法,该方法在给定网络规模和结点出错概率时,计算出Mesh网络连通概率的一个下界,或者对于要求的Mesh网络连通概率,该方法能计算出对结点出错概率的要求.例如,本文运用严格数学推导证明了当网络结点出错概率控制在0.12%以下,则多达四万个结点的Mesh网络仍可保持高达99%的连通概率.理论计算和实验结果表明,该方法在计算Mesh网络连通概率下界时是一种强有力的技术. 相似文献
3.
Mesh network is very popualr and important topological structure in parallel computing. In this paper,we focus on the fault tolerance of 3-dimensional mesh. We use the probability model to analyze the fault tolerance of mesh. To simplify our analysis, we assume the failure probability of each node is independent. We partition a 3-dimensional mesh into smaller submeshes and compute the probability with which each submesh satisfies the condition we define. If each submesh satisfies the condition, then the whole mesh is connected. We then compute the probability that a 3-dimensional mesh is connected assuming each node has a failure probability p. We use mathematical methods to derive a relationship between network node failure probability and network connectivity probability. Our simulations show that 3-dimensional mesh networks can remain connected with very high probability in practice. For example, the paper formally proves that when the network node failure probability is bounded by 0.05%, 3-dimensional mesh network of more than two hundred thousand nodes remain connected with probability larger than 99%. Theoretical and experimental results show that our method is powderful technique to calculate the lower bound of the connectivity probability of mesh network. 相似文献
4.
容错性是多计算机网络中非常重要的研究主题.本文基于节点随机出错概率研究多计算机网络Mesh的容错性,采用子网划分方法,将网络划分为相互独立且不相交的子网,假设每个节点具有随机出错概率,通过分析子网的连通性,得到整个网络的连通概率.数值和模拟结果表明,网络连通概率随时间的增大而减小,在给定的时间内,网络规模越大,连通概率越低.例如,对于给定的指数分布(λ=3 509×10-6),当时间比较小(4000秒内)的情况下,多达四万节点的Mesh网络几乎总是连通的,连通概率达到99%以上,这也表明以Mesh网络为拓扑的多计算机系统是相当可靠的. 相似文献
5.
Yuanyuan Zeng Cormac J. Sreenan Naixue Xiong Laurence T. Yang Jong Hyuk Park 《The Journal of supercomputing》2010,52(1):23-46
One of the main design challenges for wireless sensor networks (WSNs) is to obtain long system lifetime without sacrificing
system original performance such as communication connectivity and sensing coverage. A large number of sensor nodes are deployed
in redundant fashion in dense sensor networks, which lead to higher energy consumption. We propose a distributed framework
for energy efficient connectivity and coverage maintenance in WSNs. In our framework, each sensor makes self-scheduling to
separately control the states of RF and sensing unit based on dynamic coordinated reconstruction mechanism. A novel energy-balanced
distributed connected dominating set algorithm is presented to make connectivity maintenance; and also a distributed node
sensing scheduling is brought forward to maintain the network coverage according to the surveillance requirements. We implemented
our framework by C++ programming, and the simulation results show that our framework outperforms several related work by considerably
improving the energy performance of sensor networks to effectively extend network lifetime. 相似文献
6.
Gao-CaiWang Jian-ErChen Guo-JunWang 《计算机科学技术学报》2004,19(2):0-0
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. 相似文献
7.
ZHANG Yong yi 《数字社区&智能家居》2008,(Z2)
超立方体网络是大型多处理器并行计算机系统中极为重要的拓扑结构.本文使用概率分析的方法研究了在给定结点错误概率的情况下,具有子连通性的超立方体网络容错模型的连通性。理论分析和试验结果表明:在具有大量分布结点错误情况下,超立方体网络是子连通的概率非常高。 相似文献
8.
如何在资源受限的无线传感器网络中进行高效的数据路由是无线传感器网络研究的热点之一。基于群智能优化技术的蚁群优化算法被广泛应用于网络路由算法。提出一种无线传感器网络蚁群优化路由算法,能够保持网络的生存时间最长,同时能找到从源节点到基站节点的最短路径;采用的多路数据传输也可提供高效可靠的数据传输,同时考虑节点的能量水平。仿真结果表明:提出的算法延长了无线传感器网络的寿命,实现无线传感器网络在通信过程中快速、节能的路由。 相似文献
9.
Jianer Chen GaoCai Wang Chuang Lin Tao Wang GuoJun Wang 《Journal of Parallel and Distributed Computing》2007
Mesh networks are among the most important interconnection network topologies for large multicomputer systems. Mesh networks perform poorly in tolerating faults in the view of worst-case analysis. On the other hand, such worst cases occur very rarely in realistic situations. In this paper, we study the fault tolerance of 2-D and 3-D mesh networks under a more realistic model in which each network node has an independent failure probability. We first observe that if the node failure probability is fixed, then the connectivity probability of these mesh networks can be arbitrarily small when the network size is sufficiently large. Thus, it is practically important for multicomputer system manufacture to determine the upper bound for node failure probability when the probability of network connectivity and the network size are given. We develop a novel technique to formally derive lower bounds on the connectivity probability for 2-D and 3-D mesh networks. Our study shows that these mesh networks of practical size can tolerate a large number of faulty nodes thus are reliable enough for multicomputer systems. For example, it is formally proved that as long as the node failure probability is bounded by 0.5%, a 3-D mesh network of up to a million nodes remains connected with a probability larger than 99%. 相似文献
10.
无线传感器网络的安全性是目前研究的热点。传统基于临时初始密钥和基于密钥池预分配的方案难以在网络连通性和节点存储计算消耗之间有效平衡,网络生命期内使用固定不变的初始密钥/密钥池难以抵抗节点捕获攻击。本文基于中国剩余定理提出了传感器网络密钥管理协议,每个节点携带较少的密钥素材,能够实现网络最大连通,并具有较少的存储空间和计算与通信能耗;基于时间概念分多个阶段部署传感器节点时,发布的密钥素材在不同的节点部署阶段相应变化,使得网络具有自愈合功能,从而具有较强的抗节点捕获攻击。 相似文献
11.
在无线传感器网络( WSNs)中提出的许多路由算法因其真实应用场景下存在大量单向链路而使其性能大幅降低,甚至无法正常工作。对此如何在WSNs中实现准确、高效能单向链路故障检测成为一个重要的研究课题。针对这种情况提出了一种基于Hello报文的单向链路故障检测( ALFD-H)算法,该算法充分利用WSNs组成的苯环网络模型,由苯环中心节点发起周期检测信号来完成单向链路故障检测。通过苯环中心节点处理故障单向链路来控制报文数量降低网络资源的消耗,并且提高了网络的连通性和可扩展性。通过NS2仿真实验结果表明:ALFD-H相较传统检测算法采用了苯环网络模型,减少了用于故障检测的能量消耗,从而大大延长了节点的工作时间和网络的生命周期。 相似文献
12.
Critical Density for Coverage and Connectivity in Three-Dimensional Wireless Sensor Networks Using Continuum Percolation 总被引:3,自引:0,他引:3
Although most of the studies on coverage and connectivity in wireless sensor networks (WSNs) considered two-dimensional (2D) settings, such networks can in reality be accurately modeled in a three-dimensional (3D) space. The concepts of continuum percolation theory best fit the problem of connectivity in WSNs to find out whether the network provides long-distance multihop communication. In this paper, we focus on percolation in coverage and connectivity in 3D WSNs. We say that the network exhibits a coverage percolation (respectively, connectivity percolation) when a giant covered region (respectively, giant connected component) almost surely spans the entire network for the first time. Because of the dependency between coverage and connectivity, the problem is not only a continuum percolation problem but also an integrated continuum percolation problem. Thus, we propose an integrated-concentric-sphere model to address coverage and connectivity in 3D WSNs in an integrated way. First, we compute the critical density lambdaC con above which coverage percolation in 3D WSNs will almost surely occur. Second, we compute the critical density lambdac con above which connectivity percolation in 3D WSNs will almost surely occur. Third, we compute the critical density lambdac cov-con above which both coverage and connectivity percolation in 3D WSNs will almost surely occur. For each of these three problems, we also compute their corresponding critical network degree. Our results can be helpful in the design of energy-efficient topology control protocols for 3D WSNs in terms of coverage and connectivity. 相似文献
13.
All properties of mobile wireless sensor networks (MWSNs) are inherited from static wireless sensor networks (WSNs) and meanwhile have their own uniqueness and node mobility. Sensor nodes in these networks monitor different regions of an area of interest and collectively present a global overview of monitored activities. Since failure of a sensor node leads to loss of connectivity, it may cause a partitioning of the network. Adding mobility to WSNs can significantly increase the capability of the WSN by making it resilient to failures, reactive to events, and able to support disparate missions with a common set of sensor nodes. In this paper, we propose a new algorithm based on the divide-and-conquer approach, in which the whole region is divided into sub-regions and in each sub-region the minimum connected sensor cover set is selected through energy-aware selection method. Also, we propose a new technique for mobility assisted minimum connected sensor cover considering the network energy. We provide performance metrics to analyze the performance of our approach and the simulation results clearly indicate the benefits of our new approach in terms of energy consumption, communication complexity, and number of active nodes over existing algorithms. 相似文献
14.
15.
16.
17.
András Faragó 《Algorithmica》2007,49(4):337-356
We prove two results that provide new fundamental limits for topology control in large ad hoc and sensor networks. First,
we show that it remains true under very general conditions that the maximum expected node degree must grow to infinity at
least logarithmically if we want to maintain asymptotic connectivity. This has been known so far only for much more special
models than ours. Building on this result, we prove a new fundamental limit regarding link dynamics, which means the worst case length ratio of the longest and shortest link adjacent to the same node. We prove that if link
dynamics remains bounded, then no topology control algorithm can keep a large network connected with high probability. Moreover,
bounded link dynamics prevents connectivity in the limit without any a priori assumption on node degrees or transmission ranges.
Our results hold in a model that is much more general than the frequently used assumption of uniformly distributed nodes in
a regularly shaped planar domain. Our more abstract setting also aims at finding (hopefully) more robust and elegant proofs
that have less dependence on the special geometry. Since link dynamics is expected to be bounded in practice, the results
strenghten the theoretical basis for the argument that a very large ad hoc or sensor network is unable to maintain connectivity
if it has a flat, random organization without additional structure.
Supported in part by NSF Grants ANI-0220001 and CCF-0634848. 相似文献
18.
19.
20.
采用子网和概率模型对E-2DMesh网络在节点随机出错概率下的容错性进行分析,推出不同时间下的不同规模的E-2DMesh网络的连通概率下界,并且运用严密的数学方法推导出网络连通率与其节点出错概率的关系。实验结果表明以E-2DMesh为拓扑结构的并行计算机网络具有相当高的可靠性,通过对比进一步说明了E-2DMesh网络比Mesh网络具有更好的容错性。 相似文献