The embedding of rings and meshes into RP(k) networks

Copyright by Science in China Press 2004 Interconnection networks, as an important means in parallel processing systems, are investigated widely[1,2]. Recently a class of lower-degree networks is proposed[2—4]. In ref. [3] we have investigated a constant degree network, called RP(k) network. Com-pared with rings and 2-D mesh networks, the RP(k) network has many good properties. The RP(k) network has a much smaller diameter than that of 2-D meshes when the number of network nodes is less …     

A simple fault-tolerant adaptive and minimal routing approach in 3-D meshes

In this paper we propose a sufficient codition for minimal routing in 3-dimensional (3-D) meshes with faulty nodes,It is based on an early work of the author on minial routing in 2-dimensional(2-D) meshes,Unlike many traditional models that assume all the nodes know global fault distribution or just adjacent fault information,our approach is based on the concept of limited global fault information,First,we propose a fault model called faulty cube in which all faulty nodes in the system are contained in a set of faulty cubes.Fault information is then distributed to limited number of nodes while it is still sufficeint to support minimal routing.The limited fault information collcted at each node is represented by a vector caaled extended safety level.The extended safety level associated with a node can be used to determine the existence of a minimal path from this node to a given destination .Specifically,we study the existence of minimal paths at a given source node,limited distribution of fault information,minimal routing,and deadlock-free and livelock-free routing.our results show that any minimal routing that is partially adaptive can be applied in our model as long as the dstination node meets a certain conditon.We also propose a dynamic planar-adaptive routing scheme that offers better fault tolerance and adaptivity than the planar-adaptive routing scheme in 3-D meshes.Our approach is the first attempt to address adaptive and minimal routing is 3-D meshes with faulty nodes using limited fault information.     

Improved Chord Routing Algorithm Based on the Finger Table

Chord as one kind of structured P2P network＇s protocol, mainly used for network resource locator, and the efficiency of the routing algorithm influence the entire network performance. Study found that when the actual number of nodes in the network is much smaller than the size of the network, each node＇s finger table will contains multiple redundant routing information which is not conducive to the resource discovery and location. To address this problem, this paper presents an improved Chord routing algorithm based on the finger table： CA-Chord （continuous arc chord）, and simulation results confirmed that the improved algorithm can effectively eliminate redundant information in the finger table, and replace the redundant information with nodes information on an arc which are adjacent to each other on the logical position in the network, thereby improving the utilization of the finger table, then reduced the average query step, and greatly improved the efficiency of query.     

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.     

Cross-layer Enhancement to Multi-hop Routing in Sensor Networks： an Empirical Study

Lossy link is one of the unique characteristics in random-deployed sensor networks. We envision that robustness and reliability of routing cannot be ensured purely in network layer. Our idea is to enhance the performance of routing protocol by cross-layer interaction. We modified mint protocol, a routing protocol in TinyOS and proposed an enhanced version of mint called PA-mint. A transmission power control interface is added to network layer in PA-mint. When routing performance of the current network is not satisfied, PA-mint monotonically increases the transmission power via the interface we added. PA-mint is able to connect orphan nodes and robust to node mobility or key nodes failure. In the case that automatic request retransmission is employed, the number of retransmissions can be reduced by PA-mint. Results from experiments show that PA-mint increases the reliability and robustness of routing protocol by cross-layer interaction.     

Reliable energy-efficient routing with novel route update in wireless sensor networks

In this paper we introduce a novel energy-aware routing protocol REPU (reliable, efficient with path update), which provides reliability and energy efficiency in data delivery. REPU utilizes the residual energy available in the nodes and the received signal strength of the nodes to identify the best possible route to the destination. Reliability is achieved by selecting a number of intermediate nodes as waypoints and the route is divided into smaller segments by the waypoints. One distinct advantage of this model is that when a node on the route moves out or fails, instead of discarding the whole original route, only the two waypoint nodes of the broken segment are used to find a new path. REPU outperforms traditional schemes by establishing an energy-efficient path and also takes care of efficient route maintenance. Simulation results show that this routing scheme achieves much higher performance than the classical routing protocols, even in the presence of high node density, and overcomes simultaneous packet forwarding.     

基于跨层强化思想的传感网络多跳路由协议实验性研究

Lossy link is one of the unique characteristics in random-deployed sensor networks. We envision that robustness and reliability of routing cannot be ensured purely in network layer. Our idea is to enhance the performance of routing protocol by cross-layer interaction. We modified mint protocol, a routing protocol in TinyOS and proposed an enhanced version of mint called PA-mint. A transmission power control interface is added to network layer in PA-mint. When routing performance of the current network is not satisfied, PA-mint monotonically increases the transmission power via the interface we added. PA-mint is able to connect orphan nodes and robust to node mobility or key nodes failure. In the case that automatic request retransmission is employed, the number of retransmissions can be reduced by PA-mint. Results from experiments show that PA-mint increases the reliability and robustness of routing protocol by cross-layer interaction.     

A Routing Algorithm with Candidate Shortest Path

An improved algorithm based on the next node routing principle is proposed in this paper.In this algorithm there is a column added to the classical routing table, in which the candidateshortest distance to the destination node is the entry. When a link fails, the new shortest path inthe nodes connected directly with the failure link can be found immediately (it is just thecandidate shortest path before failure). For all other nodes in which routing tables should bechanged, the required number of control messages and time for convergence are also less thanTajibnapis' algorithm and Predecessor algorithm. The message looping problem does not existin duplex loop networks and is radically improved in mesh networks. These statements areproved by the analysis and simulation in this paper. From the simulation results of a 30-nodemesh network, when one link goes down, the total number of control messages generatedduring convergence with this algorithm on the average is about 30% of Tajibnapis' algorithm.The iterations required is 50% of Tajibnapis' algorithm. The memory space required andcomputation complexity in nodes are almost the same as the two algorithms mentioned aboveand the algorithm implementation is as easy as well.     

Cluster based node scheduling method for wireless sensor networks

By researching on the node scheduling problem of m-covered and connected sensor networks,a new concept of two-hops-cluster is proposed in this paper,and based on it,a new distributed node scheduling algorithm THCNS for allocating all nodes in the sensor network into k(k≤m) different groups {0,1,...,k 1} is designed,without requiring location information.Our algorithm guarantees that each group to be connected and maintains the coverage ratio with high possibility.Theoretical analysis and simulation results show that it has better performance than previous randomized scheduling scheme,and can prolong the lifetime of the sensor network effectively.     

Energy-efficient multipath routing in wireless sensor network considering wireless interference

Due to the energy and resource constraints of a wireless sensor node in a wireless sensor network (WSN), design of energy-efficient multipath routing protocols is a crucial concern for WSN applications. To provide high-quality monitoring information, many WSN applications require high-rate data transmission. Multipath routing protocols are often used to increase the network transmission rate and throughput. Although large-scale WSN can be supported by high bandwidth backbone network, the WSN remains the bottleneck due to resource constraints of wireless sensors and the effects of wireless interference. In this paper, we propose a multipath energy-efficient routing protocol for WSN that considers wireless interference. In the proposed routing protocol, nodes in the interference zone of the discovered path are marked and not allowed to take part in the subsequent routing process. In this way, the quality of wireless communication is improved because the effects of wireless interference can be reduced as much as possible. The network load is distributed on multiple paths instead of concentrating on only one path, and node energy cost is more balanced for the entire wireless network. The routing protocol is simulated in NS2 software. Simulation result shows that the proposed routing protocol achieves lower energy cost and longer network lifetime than that in the literature.     

一种实用的互联网络RPn(k)及其路由算法

基于环的简单扩展性和Petersen图的短直径,提出了一类新型互联网络RPn(k),研究了该互联网络的性质,它不但具有正则性和良好的可扩展性,还具有比RP(k)互联网络更短的网络直径、更好的可分组性以及更小的网络构造开销。最后,讨论了RPn(k)网络的路由问题,给出了点点路由算法,其通信效率为[k/2]+2n个时间步。在节点个数相同时,RPn(k)比RP(k)网络上的路由算法的通信效率有明显提高。     

双环Petersen图互联网络及路由算法

Petersen图由于具有短直径和正则性等特性,因此在并行与分布式计算中具有良好的性能.基于双环结构,构造了一个双环Petersen图互联网络DLCPG(k).同时,分别设计了DLCPG(k)上的单播、广播和容错路由算法.证明了DLCPG(k)不但具有良好的可扩展性、短的网络直径和简单的拓扑结构等特性,而且对于10k个节点组成的互联网络,DLCPG(k)还具有比二维Torus以及RP(k)互联网络更小的直径和更优越的可分组性.另外,还证明了其上的单播、广播路由算法的通信效率与RP(k)上的单播和广播路由算法的通信效率相比均有明显的提高.仿真实验表明,新的容错路由算法也具有良好的容错性能.     

光RP(k)网络上Hypercube通信模式的波长指派算法

波长指派是光网络设计的基本问题,设计波长指派算法是洞察光网络通信能力的基本方法.基于光RP(k)网络,讨论了其波长指派问题. 含有N=2ⁿ个节点的Hypercube通信模式,构造了节点间的一种排列次序Xn,并设计了RP(k)网络上的波长指派算法.在构造该算法的过程中,得到了在环网络上实现n维Hypercube通信模式的波长指派算法.这两个算法具有较高的嵌入效率.在RP(k)网络上,实现Hypercube通信模式需要max{2,「5(2^n-5/3」}个波长.而在环网络上,实现该通信模式需要复用(N/3+N/12(个波长,比已有算法需要复用「N/3+N/4」个波长有较大的改进.这两个算法对于光网络的设计具有较大的指导价值.     

基三分层互连网络及其路由算法设计

从降低节点度、减少网络链路数和缩短网络直径的角度出发,提出一种新型的互连网络结构--基三分层互连网络,深入地研究了该网络的静态度量并和2-D Mesh做了相应的比较.针对基三分层互连网络提出了一种使消息沿两节点间确定路径传递的分布式确定路由算法DDRA.该算法充分利用基三分层互连网络的层次特性,不需要构建路由表,且算法实现简单,路由效率高,且易于硬件实现.     

超立方体双环互连网络及路由算法*

给出了一种可扩展的互连网络拓扑结构,称为超立方体双环。该互连网络拓扑结构结合了超立方体拓扑的短直径、高连通性、对称性、路由简单和一种新的双环拓扑结构的可扩展性和常数节点度的优点,使得网络规模增大时,网络节点度可以保持常数;网络节点采用格雷编码和约翰逊编码的混合编码方法,网络的任意相邻节点编码有且仅有一位不同,使得路由算法设计简单。最后分别设计了基于混合编码的单播、广播路由算法。分析表明提出的互连网络具有较好的拓扑性质和通信性能。     

Metacube—a versatile family of interconnection networks for extremely large-scale supercomputers

In the next decade, the high-performance supercomputers will consist of several millions of CPUs. The interconnection networks in such supercomputers play an important role for achieving high performance. In this paper, we introduce the Metacube (MC), a versatile family of interconnection network that can connect an extremely large number of nodes with a small number of links per node and keep the diameter rather low. An MC network has a 2-level hypercube structure. An MC(k,m) network can connect 2^2km+k2^{2^{k}m+k} nodes with m+k links per node, where k is the dimension of the high-level hypercubes (classes) and m is the dimension of the low-level hypercubes (clusters). An MC is a symmetric network with short diameter, easy and efficient routing and broadcasting similar to that of the hypercube. However, the MC network can connect millions of nodes with up to 6 links per node. An MC(2,3) with 5 links per node has 16,384 nodes and an MC(3,3) with 6 links per node has 134,217,728 nodes. We describe the MC network’s structure, topological properties, routing and broadcasting algorithms, and the Hamiltonian cycle embedding in the Metacube networks.     

双环网络的[+h]边优先寻径策略

提出一种先走[ h]边、当走[ h]边不利时才走[ 1]边的[ h]边优先寻径策略;得出[ h]边优先最短路径和双环网络的"竹筏"(一种新L形瓦)型空间解;"竹筏"中节点之间的[ h]边优先最短路径存在递推关系;由节点的[ h]边优先最短路径推出双环网络的直径公式;利用VB6.0和SQLServer2000仿真了[ h]边优先寻径策略;作者曾提出的[ 1][ h]双边寻径策略是固定路径,寻找节点,而[ h]边优先寻径策略是固定节点,寻找路径;传统L形瓦难以构造但易求其等价双环网络的直径,而新L形瓦易构造但难以求其等价双环网络的直径;指出了陈忠学文中的几个错误.     

基于改进蚁群优化的无线传感器网络路由算法

针对无线传感器网络节点能量、通信能力有限等特点,提出了一种改进蚁群优化的路由算法,算法对下一节点的选择充分考虑了通信距离和剩余能量等因素,将蚂蚁搜索行为集中到最优解附近,为避免早熟收敛行为的发生,将信息素轨迹的值域范围进行限制,通过对信息素轨迹的平滑化,快速逼近无线传感器网络最优路径;仿真结果证明,该算法有效地减少了网络能量消耗、节点死亡数量和链路长度,延长了网络生命期。     

Exact Solutions to Diameter and Routing Problems in PEC Networks

Recently, the diameter problem for packed exponential connections (PEC) networks was addressed by Cho-Chin Lin and V. K. Prasanna [Proc. Symposium on Parallel and Distributed Processing, 1992, pp. 368–375], who presented asymptotically tight bounds for the diameter and showed asymptotically optimal routing algorithms. In this paper exact, solutions to the diameter and routing problems of PEC networks are derived, thereby strengthening the asymptotic bounds of Lin and Prasanna. For anN= 2ⁿnode PEC network, with[formula]an integer, it is shown that the diameter is given by the simple expression[formula]An exact expression for the diameter of PEC networks for generalNis also derived. Efficient algorithms for shortest-path routing between nodes in a PEC network are then developed. These algorithms use at mostO(log²N) time for computing the lengths of minimal routes between nodes. Finally, a simple modification to obtain symmetric PEC networks is suggested.