An evolutionary approach for configuring economical packet switched computer networks

The topological design of computer networks essentially consists in finding a network topology which minimizes the communication costs, taking into account some constraints such as performance and quality of service. This optimization problem is well known as difficult to solve, such that only heuristic methods are usually recommended and used. These methods are incremental in the sense that they take a starting topology as input solution and perturb it in order to produce a better solution. In this paper, we propose an evolutionary approach, based on the genetic algorithm paradigm, for solving this problem. Simulation results confirm the appropriateness and efficiency of this approach which yields solutions of very good quality for moderate size networks.     

Simultaneous topology and sizing optimization of a water distribution network using a hybrid multiobjective evolutionary algorithm

This paper proposes a new direction for design optimization of a water distribution network (WDN). The new approach introduces an optimization process to the conceptual design stage of a WDN. The use of multiobjective evolutionary algorithms (MOEAs) for simultaneous topology and sizing design of piping networks is presented. The design problem includes both topological and sizing design variables while the objective functions are network cost and total head loss in pipes. The numerical technique, called a network repairing technique (NRT), is proposed to overcome difficulties in operating MOEAs for network topological design. The problem is then solved by using a number of established and newly developed MOEAs. Also, two new MOEAs namely multiobjective real code population-based incremental learning (RPBIL) and a hybrid algorithm of RPBIL with differential evolution (termed RPBIL–DE) are proposed to tackle the design problems. The optimum results obtained are illustrated and compared. It is shown that the proposed network repairing technique is an efficient and effective tool for topological design of WDNs. Based on the hypervolume indicator, the proposed RPBIL–DE is among the best MOEA performers.     

An artificial neural network approach for routing in distributed computer networks

This paper presents a new approach based on the Hopfield model of artificial neural networks to solve the routing problem in a context of computer network design. The computer networks considered are packet switching networks, modeled as non-oriented graphs where nodes represent servers, hosts or switches, while bi-directional and symmetric arcs represent full duplex communication links. The proposed method is based on a network representation enabling to match each network configuration with a Hopfield neural network in order to find the best path between any node pair by minimizing an energy function. The results show that the time delay derived from flow assignment carried out by this approach is, in most cases, better than those determined using conventional routing heuristics. Therefore, this neural-network approach is suitable to be integrated into an overall topological design process of moderate-speed and high-speed networks subject to quality of service constraints as well as to changes in configuration and link costs.     

The impact of topology on energy consumption for collection tree protocols: An experimental assessment through evolutionary computation

The analysis of worst-case behavior in wireless sensor networks is an extremely difficult task, due to the complex interactions that characterize the dynamics of these systems. In this paper, we present a new methodology for analyzing the performance of routing protocols used in such networks. The approach exploits a stochastic optimization technique, specifically an evolutionary algorithm, to generate a large, yet tractable, set of critical network topologies; such topologies are then used to infer general considerations on the behaviors under analysis. As a case study, we focused on the energy consumption of two well-known ad hoc routing protocols for sensor networks: the multi-hop link quality indicator and the collection tree protocol. The evolutionary algorithm started from a set of randomly generated topologies and iteratively enhanced them, maximizing a measure of “how interesting” such topologies are with respect to the analysis. In the second step, starting from the gathered evidence, we were able to define concrete, protocol-independent topological metrics which correlate well with protocols’ poor performances. Finally, we discovered a causal relation between the presence of cycles in a disconnected network, and abnormal network traffic. Such creative processes were made possible by the availability of a set of meaningful topology examples. Both the proposed methodology and the specific results presented here – that is, the new topological metrics and the causal explanation – can be fruitfully reused in different contexts, even beyond wireless sensor networks.     

Topological network design: A survey

We consider the problem of topological optimization of communication networks subject to a number of design constraints, such as maximum network diameter, maximum node degree, k-node (link) survivability, and network fault tolerance. The primary design problem can be described as follows: Given a set of network nodes, it is required to find a topology Ψ, selected from all possible topologies, so that the cost of Ψ (measured possibly in terms of the maximum diameter, maximum node degree, etc.) is less than that of any other network topology and such that Ψ satisfies some given design constraints. Fault tolerance is concerned with the ability of the network nodes to communicate in the presence of a set of faulty links and/or nodes. The network design problem considering reliability constraints is NP-hard. We classify the research efforts presented in the literature for solving the topological optimization design problem as hierarchical, enumerative, or iterative techniques. In this paper, we provide a survey of the topological network design techniques under different design constraints. Experimental results obtained by applying a number of algorithms to a set of randomly generated networks are presented and compared.     

Estimation of all-terminal network reliability using an artificial neural network

The exact calculation of all-terminal network reliability is an NP-hard problem, with computational effort growing exponentially with the number of nodes and links in the network. During optimal network design, a huge number of candidate topologies are typically examined with each requiring a network reliability calculation. Because of the impracticality of calculating all-terminal network reliability for networks of moderate to large size, Monte Carlo simulation methods to estimate network reliability and upper and lower bounds to bound reliability have been used as alternatives. This paper puts forth another alternative to the estimation of all-terminal network reliability — that of artificial neural network (ANN) predictive models. Neural networks are constructed, trained and validated using the network topologies, the link reliabilities, and a network reliability upperbound as inputs and the exact network reliability as the target. A hierarchical approach is used: a general neural network screens all network topologies for reliability followed by a specialized neural network for highly reliable network designs. Both networks with identical link reliability and networks with varying link reliability are studied. Results, using a grouped cross-validation approach, show that the ANN approach yields more precise estimates than the upperbound, especially in the worst cases. Using the reliability estimation methods of the ANN, the upperbound and backtracking, optimal network design by simulated annealing is considered. Results show that the ANN regularly produces superior network designs at a reasonable computational cost.Scope and purposeAn important application area of operations research is the design of structures, products or systems where both technical and business aspects must be considered. One expanding design domain is the design of computer or communications networks. While cost is a prime consideration, reliability is equally important. A common reliability measure is all-terminal reliability, the probability that all nodes (computers or terminals) on the network can communicate with all others. Exact calculation of all-terminal reliability is an NP-hard problem, precluding its use during optimal network topology design, where this calculation must be made thousands or millions of times. This paper presents a novel computationally practical method for estimating all-terminal network reliability. Is shown how a neural network can be used to estimate all-terminal network reliability by using the network topology, the link reliabilities and an upperbound on all-terminal network reliability as inputs. The neural network is trained and validated on a very minute fraction of possible network topologies, and once trained, it can be used without restriction during network design for a topology of a fixed number of nodes. The trained neural network is extremely fast computationally and can accommodate a variety of network design problems. The neural network approach, an upper bound approach and an exact backtracking calculation are compared for network design using simulated annealing for optimization and show that the neural network approach yields superior designs at manageable computational cost.     

基于神经网络的动态路由选择算法

在分析了网络中基于QoS组播路由问题的基础上,文章给出了基于Hopfield神经网络的动态路由选择算法的模型。仿真研究表明该算法具有良好的分布特性和智能决策能力,此方案不仅保证了带宽、端到端延时和延时抖动,优化了路由树的代价,而且有效地控制了算法的复杂性,是一种快速动态组播路由算法,能实现全局网络资源利用的优化,容易扩展到大型网络中应用。     

Genetic algorithms with immigrants schemes for dynamic multicast problems in mobile ad hoc networks

In this paper, the problem of dynamic quality-of-service (QoS) multicast routing in mobile ad hoc networks is investigated. Lots of interesting works have been done on multicast since it is proved to be a NP-hard problem. However, most of them consider the static network scenarios only and the multicast tree cannot adapt to the topological changes. With the advancement in communication technologies, more and more wireless mobile networks appear, e.g., mobile ad hoc networks (MANETs). In a MANET, the network topology keeps changing due to its inherent characteristics such as the node mobility and energy conservation. Therefore, an effective multicast algorithm should track the topological changes and adapt the best multicast tree to the changes accordingly. In this paper, we propose to use genetic algorithms with immigrants schemes to solve the dynamic QoS multicast problem in MANETs. MANETs are considered as target systems because they represent a new generation of wireless networks. In the construction of the dynamic network environments, two models are proposed and investigated. One is named as the general dynamics model in which the topologies are changed due to that the nodes are scheduled to sleep or wake up. The other is named as the worst dynamics model, in which the topologies are altered because some links on the current best multicast tree are removed. Extensive experiments are conducted based on both of the dynamic network models. The experimental results show that these immigrants based genetic algorithms can quickly adapt to the environmental changes (i.e., the network topology changes) and produce high quality solutions following each change.     

Topological dynamics characterization for LEO satellite networks

The highly topological dynamics characterizes the most fundamental property of satellite networks with respect to terrestrial ones. The manifest feature directs the researches on various aspects of satellite networks, including protocol architecture investigations, routing protocol and reliable transmission control protocol design and enhancement, etc. This paper systematically quantifies the dynamical activities of regular low earth orbit (LEO) satellite network topologies. The number and length of network snapshots are formulated concisely. With this work, it compensates for the simplified topological assumptions in many LEO satellite network related researches. The thorough understanding of this basic feature not only provides for an accurate quantification of network behavior for researchers on satellite network community, but also could act as a guidance for future satellite constellation design and optimization.     

A systematic approach to constructing incremental topology control algorithms using graph transformation

Communication networks form the backbone of our society. Topology control algorithms optimize the topology of such communication networks. Due to the importance of communication networks, a topology control algorithm should guarantee certain required consistency properties (e.g., connectivity of the topology), while achieving desired optimization properties (e.g., a bounded number of neighbors). Real-world topologies are dynamic (e.g., because nodes join, leave, or move within the network), which requires topology control algorithms to operate in an incremental way, i.e., based on the recently introduced modifications of a topology. Visual programming and specification languages are a proven means for specifying the structure as well as consistency and optimization properties of topologies. In this paper, we present a novel methodology, based on a visual graph transformation and graph constraint language, for developing incremental topology control algorithms that are guaranteed to fulfill a set of specified consistency and optimization constraints. More specifically, we model the possible modifications of a topology control algorithm and the environment using graph transformation rules, and we describe consistency and optimization properties using graph constraints. On this basis, we apply and extend a well-known constructive approach to derive refined graph transformation rules that preserve these graph constraints. We apply our methodology to re-engineer an established topology control algorithm, kTC, and evaluate it in a network simulation study to show the practical applicability of our approach.     

A genetic algorithm for designing distributed computer networktopologies

The topological design of distributed packet switched networks consists of finding a topology that minimizes the communication costs by taking into account a certain number of constraints such as the delay and the reliability. This paper proposes a genetic algorithm (GA) for generating low-cost feasible computer network topologies subject to these constraints. The implementation of this algorithm has been subjected to extensive tests in order to measure the quality of solutions. Computational results confirm the efficiency of the GA to provide good solutions for medium-sized computer networks, in comparison with well-tried conventional methods.     

基于先验节点序学习贝叶斯网络结构的优化方法

针对小样本数据集下学习贝叶斯网络 (Bayesian networks, BN)结构的不足, 以及随着条件集的增大, 利用统计方法进行条件独立 (Conditional independence, CI) 测试不稳定等问题, 提出了一种基于先验节点序学习网络结构的优化方法. 新方法通过定义优化目标函数和可行域空间, 首次将贝叶斯网络结构学习问题转化为求解目标函数极值的数学规划问题, 并给出最优解的存在性及唯一性证明, 为贝叶斯网络的不断扩展研究提出了新的方案. 理论证明以及实验结果显示了新方法的正确性和有效性.     

Dynamic power management in energy-aware computer networks and data intensive computing systems

Energy awareness is an important aspect of modern network and computing system design and management, especially in the case of internet-scale networks and data intensive large scale distributed computing systems. The main challenge is to design and develop novel technologies, architectures and methods that allow us to reduce energy consumption in such infrastructures, which is also the main reason for reducing the total cost of running a network. Energy-aware network components as well as new control and optimization strategies may save the energy utilized by the whole system through adaptation of network capacity and resources to the actual traffic load and demands, while ensuring end-to-end quality of service. In this paper, we have designed and developed a two-level control framework for reducing power consumption in computer networks. The implementation of this framework provides the local control mechanisms that are implemented at the network device level and network-wide control strategies implemented at the central control level. We also developed network-wide optimization algorithms for calculating the power setting of energy consuming network components and energy-aware routing for the recommended network configuration. The utility and efficiency of our framework have been verified by simulation and by laboratory tests. The test cases were carried out on a number of synthetic as well as on real network topologies, giving encouraging results. Thus, we come up with well justified recommendations for energy-aware computer network design, to conclude the paper.     

基于重填化学反应优化解决无线网络动态最短选路优化问题

采用人工智能优化技巧轻易解决静态最短选路(SP)优化问题,但是随着无线通讯的发展,诸如移动Ad Hoc网络与无线传感网络等新式无线网络被大量广泛使用.在这些新式无线网络中,网络拓扑随着时间而不断变化从而导致最短选路优化问题被转变成动态优化问题.提出了一种新式的基于化学反应优化(CRO)的算法来解决这个问题.化学反应优化...     

Parameter Estimation and Topology Identification of Uncertain General Fractional-order Complex Dynamical Networks with Time Delay

Complex networks have attracted much attention from various fields of sciences and engineering in recent years. However, many complex networks have various uncertain information, such as unknown or uncertain system parameters and topological structure, which greatly affects the system dynamics. Thus, the parameter estimation and structure identification problem has theoretical and practical importance for uncertain complex dynamical networks. This paper investigates identification of unknown system parameters and network topologies in uncertain fractional-order complex network with time delays (including coupling delay and node delay). Based on the stability theorem of fractional-order differential system and the adaptive control technique, a novel and general method is proposed to address this challenge. Finally two representative examples are given to verify the effectiveness of the proposed approach.      

The Optical Chained-Cubic Tree interconnection network: Topological structure and properties

Interconnection networks with optical communication links outperform others using electronic communication links when the distance is long in terms of speed and power consumption. However, for short distances, electronic network topologies are preferred due to lower material cost requirements. As a result, hybrid network topologies were constructed to combine the benefits of both types of network topologies, such as Optical Transpose Interconnection System (OTIS). This paper presents a new hybrid interconnection network topology, which is constructed using both optical and electronic links, called the Optical Chained-Cubic Tree (OCCT). This new OCCT topology is based on the Chained-Cubic Tree (CCT) interconnection network and is designed to cope with both types of binary trees; full and complete. Also, the topological properties of OCCT in terms of diameter, connectivity, degree, bisection width, and cost are presented and compared with OTIS-Mesh and CCT interconnection networks.     

基于条件互信息和概率突跳机制的贝叶斯网络结构学习算法

贝叶斯网络分类器的精确构造是NP难问题,使用K2算法可以有效地缩减搜索空间,提高学习效率。然而K2算法需要初始的节点次序作为输入,这在缺少先验信息的情况下很难确定;另一方面,K2算法采用贪婪的搜索策略,容易陷入局部最优解。提出了一种基于条件互信息和概率突跳机制的贝叶斯网络结构学习算法(CMI-PK2算法),该算法首先利用条件互信息生成有效的节点次序作为K2算法的输入,然后利用概率突跳机制改进K2算法的搜索过程来提高算法的全局寻优能力,学习较为理想的网络结构。在两个基准网络Asia和Alarm上进行了实验验证,结果表明CMI-PK2算法具有更高的分类精度和数据拟合程度。     

Structure versus function: a topological perspective on immune networks

Many recent advances have been made in understanding the functional implications of the global topological properties of biological networks through the application of complex network theory, particularly in the area of small-world and scale-free topologies. Computational studies which attempt to understand the structure–function relationship usually proceed by defining a representation of cells and an affinity measure to describe their interactions. We show that this necessarily restricts the topology of the networks that can arise—furthermore, we show that although simple topologies can be produced via representation and affinity measures common in the literature, it is unclear how to select measures which result in complex topologies, for example, exhibiting scale-free functionality. In this paper, we introduce the concept of the potential network as a method in which abstract network topologies can be directly studied, bypassing any definition of shape-space and affinity function. We illustrate the benefit of the approach by studying the evolution of idiotypic networks on a selection of scale-free and regular topologies, finding that a key immunological property—tolerance—is promoted by bi-partite and heterogeneous topologies. The approach, however, is applicable to the study of any network and thus has implications for both immunology and artificial immune systems.     

A new fuzzy operator and its application to topology design of distributed local area networks

Topology design of distributed local area networks can be classified as a hard combinatorial optimization problem. The problem has several conflicting objectives, such as cost, reliability, network delay, and number of hops between source and destination. These objectives can conveniently be expressed in linguistic terms - a key component of fuzzy logic. This paper presents an approach based on fuzzy logic that combines the conflicting objectives into a single optimization function. A new fuzzy operator, namely, the unified AND-OR (UAO) operator is also proposed, and a decision-making approach based on fuzzy rules and preference rules is introduced. The UAO operator is empirically compared with the well-known ordered weighted averaging (OWA) operator through application to an evolutionary algorithm. Results show that the UAO operator exhibits comparatively better performance than the OWA operator.     

An Optimization Methodology for Neural Network Weights and Architectures

This paper introduces a methodology for neural network global optimization. The aim is the simultaneous optimization of multilayer perceptron (MLP) network weights and architectures, in order to generate topologies with few connections and high classification performance for any data sets. The approach combines the advantages of simulated annealing, tabu search and the backpropagation training algorithm in order to generate an automatic process for producing networks with high classification performance and low complexity. Experimental results obtained with four classification problems and one prediction problem has shown to be better than those obtained by the most commonly used optimization techniques