Application of the steiner street problem to a more economical data bus

Abstract

A data bus consists of the interconnection of N terminals, each of which is connected to every other terminal. There are three fundamental approaches to the topology of the network: (1) the tee network, for which the connecting nodes coincide with the communicating nodes; (2) the star network, for which there is only one connection node, which may not coincide with a communication node; and (3) the Steiner minimal tree network, for which there can be many nodes, each of which is difficult to locate in the x-y plane. The tee and star approaches are receiving most attention but the third is the only one that economizes on the use of cable (glass fiber waveguide). After a discussion of the tee and star networks, we turn to the Steiner minimal tree network and a method of locating the connecting nodes so that the total amount of cable is minimized.     

Comparison of optical network topologies for wavelength division multiplexed transport networks

In this paper, the various network topologies comprising of various nodes have been investigated and compared. The signal is analyzed as it passes through each node in each of the network topology. For the ring topology, it is shown that there is no appreciable signal degradation in the ring network. It is seen that there is increase in Quality factor i.e. signal keeps on improving as it passes through the successive nodes. For the bus topology, the quality of signal goes on decreasing with increase in the number of nodes and the power penalty goes on increasing. For the star topology, it is observed that received power values of each node at a same distance from the hub are same and the performance is same. For the tree topology, it is observed that the performance of the optical tree is almost identical to the performance of ring topology, as signal quality is improved as it passes through the successive nodes of the hierarchy but the overall length of each segment is limited by the type of cabling used and if the backbone line breaks, the entire segment goes down.     

Rapid self-organised initiation of ad hoc sensor networks close above the percolation threshold

This work shows potentials for rapid self-organisation of sensor networks where nodes collaborate to relay messages to a common data collecting unit (sink node). The study problem is, in the sense of graph theory, to find a shortest path tree spanning a weighted graph. This is a well-studied problem where for example Dijkstra’s algorithm provides a solution for non-negative edge weights. The present contribution shows by simulation examples that simple modifications of known distributed approaches here can provide significant improvements in performance. Phase transition phenomena, which are known to take place in networks close to percolation thresholds, may explain these observations. An initial method, which here serves as reference, assumes the sink node starts organisation of the network (tree) by transmitting a control message advertising its availability for its neighbours. These neighbours then advertise their current cost estimate for routing a message to the sink. A node which in this way receives a message implying an improved route to the sink, advertises its new finding and remembers which neighbouring node the message came from. This activity proceeds until there are no more improvements to advertise to neighbours. The result is a tree network for cost effective transmission of messages to the sink (root). This distributed approach has potential for simple improvements which are of interest when minimisation of storage and communication of network information are a concern. Fast organisation of the network takes place when the number k of connections for each node (degree) is close above its critical value for global network percolation and at the same time there is a threshold for the nodes to decide to advertise network route updates.     

Transport in weighted networks: partition into superhighways and roads

Transport in weighted networks is dominated by the minimum spanning tree (MST), the tree connecting all nodes with the minimum total weight. We find that the MST can be partitioned into two distinct components, having significantly different transport properties, characterized by centrality--the number of times a node (or link) is used by transport paths. One component, superhighways, is the infinite incipient percolation cluster, for which we find that nodes (or links) with high centrality dominate. For the other component, roads, which includes the remaining nodes, low centrality nodes dominate. We find also that the distribution of the centrality for the infinite incipient percolation cluster satisfies a power law, with an exponent smaller than that for the entire MST. The significance of this finding is that one can improve significantly the global transport by improving a tiny fraction of the network, the superhighways.     

波长重用-扩大基于单纤连接节点的WDM星形单跳网容量

针对可利用的有限信道波长数对基于单纤连接节点的WDM星形单跳网容量限制问题,本文提出了一种有效的解决方案-波长重用.根据该方案,在信道波长数一定的条件下,至少可使网络所支持的节点数-网络容量扩大一倍;在网络节点数不变时,则可大大减少网络节点的排队时延,缓和网络中各通信节点对数据信道波长使用权的竞争矛盾,使网络吞吐量增加1～3倍,有效地改善网络性能.本文首先论述了该基于单纤连接节点的波长重用WDM星形单跳网结构,接着分析了网络的波长重用特性,进而对所要求的光放大器增益和输出功率进行了计算;最后计算了网络的最大节点数和最大信道波长数.     

Deterministic scale-free small-world networks of arbitrary order

In many real-life networks, both the scale-free distribution of degree and small-world behavior are important features. There are many random or deterministic models of networks to simulate these features separately. However, there are few models that combine the scale-free effect and small-world behavior, especially in terms of deterministic versions. What is more, all the existing deterministic algorithms running in the iterative mode generate networks with only several discrete numbers of nodes. This contradicts the purpose of creating a deterministic network model on which we can simulate some dynamical processes as widely as possible. According to these facts, this paper proposes a deterministic network generation algorithm, which can not only generate deterministic networks following a scale-free distribution of degree and small-world behavior, but also produce networks with arbitrary number of nodes. Our scheme is based on a complete binary tree, and each newly generated leaf node is further linked to its full brother and one of its direct ancestors. Analytical computation and simulation results show that the average degree of such a proposed network is less than 5, the average clustering coefficient is high (larger than 0.5, even for a network of size 2 million) and the average shortest path length increases much more slowly than logarithmic growth for the majority of small-world network models.     

多层单向耦合星形网络的特征值谱及同步能力分析

随着复杂网络同步的进一步发展,对复杂网络的研究重点由单层网络转向更加接近实际网络的多层有向网络.本文分别严格推导出三层、多层的单向耦合星形网络的特征值谱,并分析了耦合强度、节点数、层数对网络同步能力的影响,重点分析了层数和层间中心节点之间的耦合强度对多层单向耦合星形网络同步能力的影响,得出了层数对多层网络同步能力的影响至关重要.当同步域无界时,网络的同步能力与耦合强度、层数有关,同步能力随其增大而增强;当同步域有界时,对于叶子节点向中心节点耦合的多层星形网络,当层内耦合强度较弱时,层内耦合强度的增大会使同步能力增强,而层间叶子节点之间的耦合强度、层数的增大反而会使同步能力减弱;当层间中心节点之间的耦合强度较弱时,层间中心节点之间的耦合强度、层数的增大会使同步能力增强,层内耦合强度、层间叶子节点之间的耦合强度的增大反而会使同步能力减弱.对于中心节点向叶子节点耦合的多层星形网络,层间叶子节点之间的耦合强度、层数的增大会使同步能力增强,层内耦合强度、节点数、层间中心节点之间的耦合强度的增大反而会使同步能力减弱.     

Power control of optical CDMA star networks

In this paper, we apply the power control concept to optical CDMA star networks. Two approaches are considered, namely, centralized and distributed power control. Both approaches are used to optimize the optical transmit power and to maximize network capacity in terms of the number of users satisfying a target signal to interference (SIR) ratio. Centralized algorithms result in the optimum power vector while distributed algorithms are more suitable for practical system implementation and eliminate the need for a centralized control node. Both analytical and simulation results show significant improvement in the performance of the power controlled optical CDMA system. For instance, in a network of 31 nodes, a doubling of the capacity as compared to the non power control case is obtained. Furthermore, we show in the interference-limited case that the network performance is upper bounded by the number of nodes and the correlation properties of the employed code rather than network attenuation and optical fiber lengths. The concept of network partitioning is then introduced to simplify optimum power calculations. Using network partitioning, we find in the interference-limited case that the optical fibers after the star coupler are irrelevant to the optimum power evaluation.     

Network models: Action formulation

We develop a technique to formulate quantum field theory on an arbitrary network, based on different randomly disposed sets of scattering points. We define the R-matrix of the whole network as a product of R-matrices attached to each scattering node. Then an action is formulated for a network in terms of fermionic fields, which allows to calculate the transition amplitudes as Green functions. On so-called bubble and triangle diagrams it is shown that the method produces the same results as the one which uses the generalized star product. The approach allows to extend network models by including multiparticle interactions at the scattering nodes.     

两层星形网络的特征值谱及同步能力

多层网络是当今网络科学研究的一个前沿方向.本文深入研究了两层星形网络的特征值谱及其同步能力的问题.通过严格导出的两层星形网络特征值的解析表达式,分析了网络的同步能力与节点数、层间耦合强度和层内耦合强度的关系.当同步域无界时,网络的同步能力只与叶子节点之间的层间耦合强度和网络的层内耦合强度有关;当叶子节点之间的层间耦合强度比较弱时,同步能力仅依赖于叶子节点之间的层间耦合强度;而当层内耦合强度比较弱时,同步能力依赖于层内耦合强度;当同步域有界时,节点数、层间耦合强度和层内耦合强度对网络的同步能力都有影响.当叶子节点之间的层间耦合强度比较弱时,增大叶子节点之间的层间耦合强度会增强网络的同步能力,而节点数、中心节点之间的层间耦合强度和层内耦合强度的增大反而会减弱网络的同步能力;而当层内耦合强度比较弱时,增大层内耦合强度会增强网络的同步能力,而节点数、层间耦合强度的增大会减弱网络的同步能力.进一步,在层间和层内耦合强度都相同的基础上,讨论了如何改变耦合强度更有利于同步.最后,对两层BA无标度网络进行数值仿真,得到了与两层星形网络非常类似的结论.     

Investigation of wavelength division multiplexed hybrid ring-tree-star network topology to enhance the system capacity

In this paper, we have investigated wavelength division multiplexed (WDM) hybrid (ring-tree-star) topology. Eight optical add/drop multiplexers (OADMs) are used to make ring structure. The single mode fiber and dispersion compensating fiber and semiconductor optical amplifier (SOA) are employed between each OADM to achieve a maximum. To increase the number of users each OADM node of ring network is connected to star and tree network topology which can accommodate more than 2048 users. Various system parameters (for different channel spacing, different input power signal, different data rates and the fiber length) are varied to investigate the system performance in the term of BER and Q factor.     

基于层间相似性的时序网络节点重要性研究

时序网络可以更加准确地描述节点之间的交互顺序和交互关系.结合多层耦合网络分析法,本文提出了基于节点层间相似性的超邻接矩阵时序网络节点重要性识别方法,与经典的认为所有层间关系为常数不同,层间关系用节点的邻居拓扑重叠系数进行度量.Workspace和Enrons数据集上的结果显示:相比经典的方法,使用该方法得到的Kendall’sτ值在各时间层上的平均提高,最高为17.72%和12.44%,结果表明层间相似性的度量对于时序网络的节点重要性度量具有十分重要的意义.     

基于K-阶结构熵的网络异构性研究

结构熵可以考察复杂网络的异构性.为了弥补传统结构熵在综合刻画网络全局以及局部特性能力上的不足,本文依据网络节点在K步内可达的节点总数定义了K-阶结构熵,可从结构熵随K值的变化规律、最大K值下的结构熵以及网络能够达到的最小结构熵三个方面来评价网络的异构性.利用K-阶结构熵对规则网络、随机网络、Watts-Strogatz小世界网络、Barabási_-Albert无标度网络以及星型网络进行了理论研究与仿真实验,结果表明上述网络的异构性依次增强.其中K-阶结构熵能够较好地依据小世界属性来刻画小世界网络的异构性,且对星型网络异构性随其规模演化规律的解释也更为合理.此外, K-阶结构熵认为在规则结构外新增孤立节点的网络的异构性弱于未添加孤立节点的规则结构,但强于同节点数的规则网络.本文利用美国西部电网进一步论证了K-阶结构熵的有效性.     

Degree and wealth distribution in a network induced by wealth

A network induced by wealth is a social network model in which wealth induces individuals to participate as nodes, and every node in the network produces and accumulates wealth utilizing its links. More specifically, at every time step a new node is added to the network, and a link is created between one of the existing nodes and the new node. Innate wealth-producing ability is randomly assigned to every new node, and the node to be connected to the new node is chosen randomly, with odds proportional to the accumulated wealth of each existing node. Analyzing this network using the mean value and continuous flow approaches, we derive a relation between the conditional expectations of the degree and the accumulated wealth of each node. From this relation, we show that the degree distribution of the network induced by wealth is scale-free. We also show that the wealth distribution has a power-law tail and satisfies the 80/20 rule. We also show that, over the whole range, the cumulative wealth distribution exhibits the same topological characteristics as the wealth distributions of several networks based on the Bouchaud-Mèzard model, even though the mechanism for producing wealth is quite different in our model. Further, we show that the cumulative wealth distribution for the poor and middle class seems likely to follow by a log-normal distribution, while for the richest, the cumulative wealth distribution has a power-law behavior.     

Hierarchical Characterization of Complex Networks

While the majority of approaches to the characterization of complex networks has relied on measurements considering only the immediate neighborhood of each network node, valuable information about the network topological properties can be obtained by considering further neighborhoods. The current work considers the concept of virtual hierarchies established around each node and the respectively defined hierarchical node degree and clustering coefficient (introduced in cond-mat/0408076), complemented by new hierarchical measurements, in order to obtain a powerful set of topological features of complex networks. The interpretation of such measurements is discussed, including an analytical study of the hierarchical node degree for random networks, and the potential of the suggested measurements for the characterization of complex networks is illustrated with respect to simulations of random, scale-free and regular network models as well as real data (airports, proteins and word associations). The enhanced characterization of the connectivity provided by the set of hierarchical measurements also allows the use of agglomerative clustering methods in order to obtain taxonomies of relationships between nodes in a network, a possibility which is also illustrated in the current article.     

Cluster synchronization in community network with nonidentical nodes via intermittent pinning control

In this paper, cluster synchronization in community network with nonidentical nodes is investigated. By combining intermittency with a pinning control scheme, some effective controllers are designed. In the control scheme, only one node in each community is controlled and coupling weights of a spanning tree in each community are enhanced. Based on the Lyapunov function method and mathematical analysis technique, two results for achieving cluster synchronization are obtained. Noticeably, by introducing an adaptive strategy, some universal adaptive intermittent pinning controllers are designed for different networks. Finally, two numerical simulations are performed to verify the correctness of the derived results.     

Geographical Effects on Complex Networks

We investigate how the geographical structure of a complex network affects its network topology, synchronization and the average spatial length of edges. The geographical structure means that the connecting probability of two nodes is related to the spatial distance of the two nodes. Our simulation results show that the geographical structure changes the network topology. The synchronization tendency is enhanced and the average spatial length of edges is enlarged when the node can randomly connect to the further one. Analytic results support our understanding of the phenomena.     

Geographical Effects on Complex Networks

We investigate how the geographical structure of a complex network affects its network topology, synchronization and the average spatial length of edges. The geographical structure means that the connecting probability of two nodes is related to the spatial distance of the two nodes. Our simulation results show that the geographical structure changes the network topology. The synchronization tendency is enhanced and the average spatial length of edges is enlarged when the node can randomly connect to the further one. Analytic results support our understanding of the phenomena.     

Mobile sink-based data collection in event-driven wireless sensor networks using a modified ant colony optimization

The hotspot problem is one of the primary challenges in the wireless sensor networks (WSNs) because it isolates the sink node from the remaining part of the WSN. A mobile sink (MS)-based data acquisition strategy mitigates the hotspot problem, but the traditional MS-based data gathering approaches do not resolve the issue. However, the conventional techniques follow a fixed order of visits and static traversal of the MS. In this context, this paper uses a modified version of the ant colony optimization strategy for the data collected through a MS to mitigate the hotspot problem in the WSNs while improving the energy efficiency, network lifetime, throughput by reducing the packet loss and delay. In our work, we initially construct a forwarded load spanning tree to estimate the freight of each node in the WSN. Further, we choose RPs and their path simultaneously using the modified ACO algorithm by considering the forward loads, remaining energy, distance, etc. The proposed work also adopts the virtual RP selection strategy void unnecessary data exchanges between the nodes and RPs. Hence, it reduces the burden on relay nodes and optimize the energy usage among the nodes. We compare our approach with the recent ACO-based algorithms, and our approach outperforms them.