Network Dimensioning in WDM-Based All-Optical Networks

The problem of network dimensioning, which involves optimal network designs using minimal resources for a given well-predicted traffic between individual nodes but without a pre-determined network topology, is analyzed in details in this paper. Such optimal designs are critical as the network resources are directly related to the cost of implementation. The problem complexity increases as the traffic between every node pair varies in a periodic manner. Furthermore, the presence of wavelength conflicts makes the network-dimensioning problem distinct and more complicated than that for traditional circuit-switching networks. Here, we adopt the approach based on a multi-commodity flow problem. A general cost function covering the resources of all system components is formulated, and two solution approaches are presented; one based on integer programming and one on heuristics.     

Effect of Selfish Node Behavior on Efficient Topology Design

The problem of topology control is to assign per-node transmission power such that the resulting topology is energy-efficient and satisfies certain global properties such as connectivity. The conventional approach to achieve these objectives is based on the fundamental assumption that nodes are socially responsible. We examine the following question: if nodes behave in a selfish manner, how does it impact the overall connectivity and energy consumption in the resulting topologies? We pose the above problem as a non-cooperative game and use game-theoretic analysis to address it. We study Nash equilibrium properties of the topology control game and evaluate the efficiency of the induced topology when nodes employ a greedy best response algorithm. We show that even when the nodes have complete information about the network, the steady state topologies are suboptimal. We propose a modified algorithm based on a better response dynamic and show that this algorithm is guaranteed to converge to energy-efficient and connected topologies. Moreover, the node transmit power levels are more evenly distributed and the network performance is comparable to that obtained from centralized algorithms.     

A generalized service deployment framework for OSPF networks using multi‐topology routing: Modeling and methodology

The exponential growth of various applications requires deploying an ever‐growing number of network services. A generalized service deployment framework for Open Shortest Path First (OSPF) networks is proposed in this paper. The framework includes placing programmable routers, distributing different types of services on these routers, and leading traffic flow through them according to the predetermined sequence order requirement. However, it is not possible to direct all the traffic flows through the required service nodes along the shortest path with a single and suitable set of link weights. To address the issue, multiple topology routing (MTR) technique is incorporated to have various logical topologies with multiple sets of link weights. Correspondingly, the problem of jointly optimizing Placement of programmable routers, Distribution of different types of services among these routers, and Link Weights setting based on MTR (shortened to PD‐LW‐MTR) and its mixed integer linear programming formulation are presented in this paper. A novel decomposition algorithm is also proposed to address this problem efficiently. Experiment results validate the correctness and feasibility of our algorithm. It is also shown that the optimization algorithm can obtain near‐optimal solution and just only a few logical topologies over multiple sets of link weights are necessary for traffic flows to guarantee service order requirements.     

A topology preserving cluster‐based channel assignment for wireless mesh networks

Wireless Mesh Networks (WMN) with multiple radios and multiple channels are expected to resolve the capacity limitation problem of simpler wireless networks. However, optimal WMN channel assignment (CA) is NP complete, and it requires an optimal mapping of available channels to interfaces mounted over mesh routers. Acceptable solutions to CA must minimize network interference and maximize available network throughput. In this paper, we propose a CA solution called as cluster‐based channel assignment (CBCA). CBCA aims at minimizing co‐channel interference yet retaining topology through non‐default CA. Topology preservation is important because it avoids network partitions and is compatible with single‐interface routers in the network. A ‘non‐default’ CA solution is desired because it uses interfaces over different channels and reduces medium contention among neighbors. To the best of our knowledge, CBCA is a unique cluster‐based CA algorithm that addresses topology preservation using a non‐default channel approach. The main advantage of CBCA is it runs in a distributed manner by allowing cluster heads to perform CA independently. CBCA runs in three stages, where first the WMN nodes are partitioned into clusters. The second stage performs binding of interfaces to neighbors and third stage performs CA. The proposed algorithm improves over previous work because it retains network topology and minimizes network interference, which in turn improves available network throughput. Further, when compared with two other CBCA algorithms, CBCA provides better performance in terms of improved network interference, throughput, delay, and packet delivery ratios when tested upon network topologies with various network densities and traffic loads. Copyright © 2014 John Wiley & Sons, Ltd.     

基于代数连通度优化的空间信息网络分布式拓扑控制方法

针对空间信息网络中节点高速运动导致的网络拓扑结构难以长期稳定的问题,本文提出了基于代数连通度优化的网络动态拓扑控制方法,通过少量链路调整来维持网络拓扑的稳定性.为减小空间信息网络节点持续相对运动对网络拓扑结构稳定性造成的不利影响,针对网络初始化和网络重构场景,采用图论中的拉普拉斯矩阵特征值优化思想,构建了星上资源约束条件下的加权代数连通度最大化模型.为降低计算复杂度来实现网络拓扑的捷变控制,提出了基于连通矩阵弱摄动的动态网络拓扑控制策略.研究结果表明,提出的算法能够通过内点法,可高效地得到次优解,且次优解与全局最优解十分接近.     

Adaptive and Decentralized Operator Placement for In-Network Query Processing

In-network query processing is critical for reducing network traffic when accessing and manipulating sensor data. It requires placing a tree of query operators such as filters and aggregations but also correlations onto sensor nodes in order to minimize the amount of data transmitted in the network. In this paper, we show that this problem is a variant of the task assignment problem for which polynomial algorithms have been developed. These algorithms are however centralized and cannot be used in a sensor network. We describe an adaptive and decentralized algorithm that progressively refines the placement of operators by walking through neighbor nodes. Simulation results illustrate the potential benefits of our approach. They also show that our placement strategy can achieve near optimal placement onto various graph topologies despite the risks of local minima.     

Game of energy consumption balancing in heterogeneous sensor networks

In a multi‐hop sensor network, sensors largely rely on other nodes as a traffic relay to communicate with targets that are not reachable by one hop. Depending on the topology and position of nodes, some sensors receive more relaying traffic and lose their energy faster. Such imbalanced energy consumption may lead to server problems like network partitioning. In this paper, we study the problem of energy consumption balancing (ECB) in heterogeneous sensor networks by assuming general any‐to‐any traffic pattern. We consider both factors of transmission power and forwarding load in measuring energy consumption. To find a solution, we formulate the problem as a strategic network formation game with a new utility function. We show that this game is guaranteed to converge to strongly connected topologies which have better ECB and bounded inefficiency. We propose a localized algorithm in which every node knows only about its k‐hop neighbourhood. Through simulations on uniform and clustered networks with various densities, we show that the performance of our algorithm is comparable with global and centralized algorithms. Copyright © 2015 John Wiley & Sons, Ltd.     

A tabu-search approach for designing computer-network topologieswith unreliable components

The topological design of computer networks is a part of network planning, and consists of finding a network topology configuration that minimizes the total communication cost, while considering some performance and reliability constraints. Given the computational complexity of techniques that allow an optimal solution to this problem, heuristic methods are often proposed to reduce the search of candidate topologies and provide suboptimal solutions. The tabu search (TS) approach in this paper is one such method. Our adaptation of TS to the topological design of computer networks applies some moves to a starting topology in order to reduce its total link-cost and/or to improve its average delay. Such an approach is an attempt to generalize a local-search method. Simulation results confirm the efficiency and robustness of this method for designing backbone networks interconnecting between 12 and 30 nodes. Our implementation of TS generally provides better solutions than CS, SA, and GA. Our implementation of TS uses a routing strategy where packets travel according to the shortest distances between nodes. This strategy is easy to implement and allows the direct evaluation of flow and delay, but has some shortcomings. The routes do not vary according to the charge of the network. In practice, it is suitable to use the dynamic routing strategy where routes vary according to the traffic supported by the network. The length of the tabu list can noticeably affect the final results, therefore the use of dynamic list is entirely suitable     

A Lagrangian-Relaxation Based Network Profit Optimization For Mesh SONET-Over-WDM Networks

In Wavelength Division Multiplexing (WDM) networks, the huge capacity of wavelength channels is generally much larger than the bandwidth requirement of individual traffic streams from network users. Traffic grooming techniques aggregate low-bandwidth traffic streams onto high-bandwidth wavelength channels. In this paper, we study the optimization problem of grooming the static traffic in mesh Synchronous Optical Network (SONET) over WDM networks. The problem is formulated as a constrained integer linear programming problem and an innovative optimization objective is developed as network profit optimization. The routing cost in the SONET and WDM layers as well as the revenue generated by accepting SONET traffic demands are modelled. Through the optimization process, SONET traffic demands will be selectively accepted based on the profit (i.e., the excess of revenue over network cost) they generate. Consiering the complexity of the network optimization problem, a decomposition approach using Lagrangian relaxation is proposed. The overall relaxed dual problem is decomposed into routing and wavelength assignment and SONET traffic routing sub-problems. The subgradient approach is used to optimize the derived dual function by updating the Lagrange multipliers. To generate a feasible network routing scheme, a heuristic algorithm is proposed based on the dual solution. A systematic approach to obtain theoretical performance bounds is presented for an arbitrary topology mesh network. This is the first time that such theoretical performance bounds are obtained for SONET traffic grooming in mesh topology networks. The optimization results of sample networks indicate that the roposed algorithm achieves good sub-optimal solutions. Finally, the influence of various network parameters is studied.     

A Game Theoretical Approach for Topology Control in Wireless Ad Hoc Networks with Selfish Nodes

In ad hoc networks, a significant amount of energy available to devices is utilized in network management operations. Since devices have limited energy resources, therefore, they drop data packets of other nodes to reduce their energy consumption. This selfish behaviour increases number of retransmissions over the link which increases energy consumption of the source node, introduces time delays, and degrades throughput of the network. Although conventional distributed topology control solutions minimize energy utilization of the nodes by adjustment of transmission power, however, selfish behaviour by devices introduce additional complexity in design which make topology control a challenging task. In this paper, we proposed Energy Efficient Topology Control Algorithm (EETCA) using game theoretical approach, in which, utility of the node depends on selfishness of the neighbors, link traffic rate, and link length. In decision-making step, nodes remove the links with other nodes that have high drop rate under the condition that network remains connected. We show that Nash Equilibrium point of the proposed game results in Pareto optimal network topology. We compare results of EETCA with Optimum (OPT) and Minimum Least Power Path Tree (MLPT) algorithms presented in literature. We carried our simulations under multiple sources scenario which show that EETCA outperforms previous approaches when number of nodes in the network increases. Furthermore, we simulate the performance of Ad-hoc On-demand Distance Vector (AODV) routing protocol under EETCA topology and compare it with MLPT and OPT topologies. The results show that the ad hoc network constructed using proposed solution substantially improves throughput of AODV routing protocol as compared to MLPT and OPT topology control algorithms.     

Autonomous Reconfiguration in Free-Space Optical Sensor Networks

This research focuses on the physical and logical control and reconfigurability of network topologies through intelligent and dynamic rearrangement of nodes in an optical wireless sensor network. We address high data rate sensor networks (e.g., infrastructure monitoring; surveillance), which consist of gigabit per second, narrow beam, free-space optical links between fixed and/or mobile nodes. In our approach, the seamless operation of such networks requires maintenance of wireless link connectivity and quality and at all times, amidst, for example, changing atmospheric, and traffic and platform conditions. This is achieved by dynamic reconfiguration through topology control. We address the problem of dynamic formulation of topologies, which contain only two transceivers per communications node or switch. The task of reconfiguration requires the formation of a biconnected graph or a ring topology. The problem is similar to the traveling salesman problem and is NP complete. We address the mixed integer programming formulation of this problem, and show that it does not scale even for a small network. We then focus on heuristics for dynamic, autonomous reconfiguration. Using simulations, we investigate tradeoff between solution quality and computational time. We also investigate the effectiveness of these dynamic reconfiguration heuristics compared to fixed, degraded topologies.     

Diffusion Recursive Least-Squares for Distributed Estimation Over Adaptive Networks

We study the problem of distributed estimation over adaptive networks where a collection of nodes are required to estimate in a collaborative manner some parameter of interest from their measurements. The centralized solution to the problem uses a fusion center, thus, requiring a large amount of energy for communication. Incremental strategies that obtain the global solution have been proposed, but they require the definition of a cycle through the network. We propose a diffusion recursive least-squares algorithm where nodes need to communicate only with their closest neighbors. The algorithm has no topology constraints, and requires no transmission or inversion of matrices, therefore saving in communications and complexity. We show that the algorithm is stable and analyze its performance comparing it to the centralized global solution. We also show how to select the combination weights optimally.     

Distributed dynamic grooming routing and wavelength assignment in WDM optical mesh networks

The bandwidth of a wavelength channel in WDM optical networks is very high compared to the user’s requirements for various applications. Therefore, there is a scope for better utilization of channel bandwidth by traffic grooming, in which several user’s channels are multiplexed for transmission over a single channel. Several research works have been reported on traffic grooming routing and wavelength assignment (GRWA) for static and dynamic traffic pattern under centralized environment. Distributed dynamic grooming routing and wavelength assignment (DDGRWA) is a new and quite unexplored area in WDM optical mesh networks. This article introduces the concept of distributed traffic grooming in WDM mesh networks which also includes virtual topology construction, reconfiguration, routing and wavelength assignment in the distributed environment assuming incoming traffic to be dynamic in nature. We have also presented simulation results of our algorithm on dynamically generated traffic under various network topologies.     

Hop count based optimization of Bluetooth scatternets

In the past five years Bluetooth scatternets were one of the most promising wireless networking technologies for ad hoc networking. In such networks, mobility together with the fact that wireless network nodes may change their communication peers in time, generate permanently changing traffic flows. Thus, forming an optimal scatternet for a given traffic pattern may be not enough, rather a scatternet that best supports traffic flows as they vary in time is required.In this paper we study the optimization of scatternets through the reduction of communication path lengths. After demonstrating analytically that there is a strong relationship between the communication path length on one hand and throughput and power consumption on the other hand, we propose a novel heuristic algorithm suite capable of dynamically adapting the network topology to the existing traffic connections between the scatternet nodes. The periodic adaptation of the scatternet topology to the traffic connections enables the routing algorithms to identify shorter paths between communicating network nodes, thus allowing for more efficient communications. We evaluate our approach through simulations, in the presence of dynamic traffic flows and mobility.     

Network lifetime maximization with cross-layer design in wireless sensor networks

This paper investigates a cross-layer design approach for minimizing energy consumption and maximizing network lifetime (NL) of a multiple-source and single-sink (MSSS) WSN with energy constraints. The optimization problem for MSSS WSN can be formulated as a mixed integer convex optimization problem with the adoption of time division multiple access (TDMA) in medium access control (MAC) layer, and it becomes a convex problem by relaxing the integer constraint on time slots. Impacts of data rate, link access and routing are jointly taken into account in the optimization problem formulation. Both linear and planar network topologies are considered for NL maximization (NLM). With linear MSSS and planar single-source and single-sink (SSSS) topologies, we successfully use Karush-Kuhn-Tucker (KKT) optimality conditions to derive analytical expressions of the optimal NL when all nodes are exhausted simultaneously. The problem for planar MSSS topology is more complicated, and a decomposition and combination (D&C) approach is proposed to compute suboptimal solutions. An analytical expression of the suboptimal NL is derived for a small scale planar network. To deal with larger scale planar network, an iterative algorithm is proposed for the D&C approach. Numerical results show that the upper-bounds of the network lifetime obtained by our proposed optimization models are tight. Important insights into the NL and benefits of cross-layer design for WSN NLM are obtained.     

Design of virtual topologies for large optical networks through an efficient MILP formulation

In this paper we propose a Mixed-Integer Linear Programming (MILP) formulation for designing virtual topologies of wavelength-routed optical networks, considering as objective function the minimization of the traffic electronically forwarded at the network nodes. Our goal is twofold. Firstly, to reduce packet router processing requirements of the electronic routers, and secondly, to get the most transparent traffic distribution for a given traffic matrix, using the available optical resources at the nodes. The proposed formulation was applied successfully to reasonable sized networks yielding optimal solutions in a few minutes. To the best knowledge of the authors, this is the first report on optimizing virtual topology and traffic routing of large optical networks with a low computational cost MILP formulation.     

Design of logical topologies for wavelength-routed optical networks

The problem of designing a logical topology over a wavelength-routed all-optical network (AON) physical topology is studied. The physical topology consists of the nodes and fiber links in the network. On an AON physical topology, we can set up lightpaths between pairs of nodes, where a lightpath represents a direct optical connection without any intermediate electronics. The set of lightpaths along with the nodes constitutes the logical topology. For a given network physical topology and traffic pattern, our objective is to design the logical topology and the routing algorithm so as to minimize the network congestion while constraining the average delay seen by a source-destination pair and the amount of processing required at the nodes (degree of the logical topology). Ignoring the delay constraints can result in fairly convoluted logical topologies with very long delays. On the other hand, in all our examples, imposing it results in a minimal increase in congestion. While the number of wavelengths required to imbed the resulting logical topology on the physical all optical topology is also a constraint in general, we find that in many cases of interest this number can be quite small. We formulate the combined logical topology design and routing problem described above as a mixed integer linear programming problem which we then solve for a number of cases of a six-node network. This programming problem is split into two subproblems: logical topology design, and routing. We then compare the performance of several heuristic topology design algorithms against that of randomly generated topologies, as well as lower bounds     

A tutorial on using genetic algorithms for the design of network topology

The design of network topology is an important part of network design, since network topology is directly associated with network operational behavior, capacity, reliability, and cost. This paper is a tutorial paper concerned with illustrating how the optimization capabilities of genetic algorithms can be used to design suitable network topologies considering basic topology problems. Simple genetic algorithms have been developed for the topology problem of mesh networks, considering single node and single link failure tolerance. The algorithms are based on criteria of two important measures: minimizing the length of communication links; and minimizing traffic flow through these links for given traffic loads. The first measure contributes to minimizing the cost of cabling, while the second measure contributes to minimizing the cost of link capacity. The work provides a useful approach and tools to network students and professionals concerned with the topology design of backbone networks. The developed software is made available on the Internet. Copyright © 2006 John Wiley & Sons, Ltd.     

A distributed self-healing approach to Bluetooth scatternet formation

This paper proposes a distributed self-healing technique for topology formation in dynamic Bluetooth wireless personal area networks (BT-WPANs) and analyzes three new algorithms for scatternet formation. The three algorithms employ distributed procedures for the insertion of one or more nodes in a BT-WPAN, and are able to effectively compromise between the need for system efficiency and the desire to promptly adapt to topology changes. Depending on which algorithm is employed, the proposed approach generates BT-WPANs with different connectivity properties as well as topology structures.