On the joint link dimensioning and routing metric assignment problem for reliable WDM networks

In this paper, we tackle the joint link dimensioning and routing metric assignment problem for reliable wavelength division multiplexing (WDM) networks. This design problem consists to find the number of wavelength channels on each link and the routing metrics (considering shortest-path routing) that ensure the routing of all virtual wavelength paths (VWPs) and the successful rerouting of the reliable VWPs for all failure scenarios of interest to the network planner. A mixed integer mathematical programming model is proposed for the problem. The model is adapted for the single link failure scenarios. Since the problem is NP-hard, we propose a tabu search algorithm to obtain good approximate solutions for real-size instances of the problem. Finally, a lower bound is proposed and numerical results are presented and analyzed.     

Probability based dynamic-alternate routing and the corresponding converter placement algorithm in all-optical WDM networks

This paper proposes a new dynamic-alternate routing algorithm and its corresponding converter placement algorithm in order to reduce the connection blocking probability for all-optical WDM networks. The main idea in the proposed dynamic-alternate routing algorithm is to try to route the traffics according to a predefined optimal probability distribution. The problem for finding the optimal probability distribution was shown as a convex optimization problem. The problem can be solved by flow deviation method or other standard optimization techniques. Simulation results show that the proposed routing algorithm yields lower connection blocking probabilities than the previous works. The proposed routing algorithm produces similar traffic pattern as the optimal traffic pattern. The similarity between the traffic pattern produced by the proposed dynamic-alternate routing algorithm and the optimal traffic pattern can be further employed for solving other network designing problems such as converter placement problem. Since the optimal traffic pattern can be easily predicted, the optimal traffic pattern which minimizes the blocked traffic intensity is utilized for finding the locations of wavelength converters. The key idea is to place the wavelength converters at the nodes where they are needed most. Simulations have been performed to study the performance of the proposed wavelength converter placement method. The simulation results have shown that the proposed placement method combined with the proposed probability based dynamic-alternate routing algorithm yields smaller connection blocking probability than the two converter placement methods with their corresponding alternate routing algorithms.     

Joint routing and wavelength assignment in wavelength division multiplexing networks for permanent and reliable paths

In this paper, we tackle the routing and wavelength assignment problem for wavelength division multiplexing (WDM) networks containing permanent and reliable wavelength paths (WPs). It consists of finding the route and the wavelength of each WP for the normal state of the network and for the important failure scenarios. These scenarios might be the most probable failure scenarios or simply the failure scenarios of interest to the network planner (e.g., the single link failure scenarios). We propose a mathematical programming model for this problem. In order to find a solution within a reasonable amount of time, a simple heuristic algorithm is proposed. The results show that “good” solutions can be obtained with the proposed heuristic algorithm.     

Routing and wavelength assignment for hypercube communications embedded on optical chordal ring networks of degrees 3 and 4

Routing and wavelength assignment for realizing hypercube communications on WDM ring networks has been discussed in previous research. To reduce the wavelength requirement, we study routing and wavelength assignment for realizing hypercube communications on WDM ring networks with additional links. We design the embedding schemes and derive the numbers of wavelengths required on WDM chordal ring networks of both degrees 3 and 4. Based on our proposed embedding schemes, we provide the analysis of chord length with optimal number of wavelengths to realize hypercube communications on 3-degree and 4-degree chordal rings. Results show that the wavelength requirement for realizing hypercube communications on optical chordal ring networks is significantly lower than that on optical ring networks. In addition, our research also provides solutions for embedding hypercube graph on chordal rings in graph embedding theory.     

Routing wavelength and time-slot reassignment algorithms for TDM based optical WDM networks

In this paper, we consider the problem of maximizing the time of first lightpath request rejection, T in the circuit-switched time division multiplexed (TDM) wavelength-routed (WR) optical WDM networks. TDM is incorporated into WDM, to increase the channel utilization when the carried traffic does not require the entire channel bandwidth. In TDM–WDM network, multiple sessions are multiplexed on each wavelength by assigning a sub-set of the TDM slots to each session. Thus, given a session request with a specified bandwidth, a lightpath has to be established by using the routing, wavelength and time-slot assignment (RWTA) algorithms. If the lightpath cannot be established, lightpath request rejection or call blocking occurs. As each lightpath is substantial revenue and long-lived, lightpath request rejection is highly unfavourable in the optical backbone networks. In this paper, we are proposing an intelligent routing, wavelength and time-slot reassignment algorithm for multi-rate traffic demands, where, when a call gets blocked, the already established calls in the network are rerouted, wavelength and time-slot reassigned so as to accommodate the blocked call. Since we are talking of slow arrivals and long holding times for the lightpaths, it is possible to do this reassignment while provisioning a new call. Simulation based analyses are used to study the performance of the proposed reassignment algorithm. The results show that the proposed reassignment algorithm can be used to maximize the time of first call blocking, thereby accommodating more calls in the network before upgrading the network capacity.     

A multipopulation parallel genetic simulated annealing-based QoS routing and wavelength assignment integration algorithm for multicast in optical networks

In this paper, we propose an integrated Quality of Service (QoS) routing algorithm for optical networks. Given a QoS multicast request and the delay interval specified by users, the proposed algorithm can find a flexible-QoS-based cost suboptimal routing tree. The algorithm first constructs the multicast tree based on the multipopulation parallel genetic simulated annealing algorithm, and then assigns wavelengths to the tree based on the wavelength graph. In the algorithm, routing and wavelength assignment are integrated into a single process. For routing, the objective is to find a cost suboptimal multicast tree. For wavelength assignment, the objective is to minimize the delay of the multicast tree, which is achieved by minimizing the number of wavelength conversion. Thus both the cost of multicast tree and the user QoS satisfaction degree can approach the optimal. Our algorithm also considers load balance. Simulation results show that the proposed algorithm is feasible and effective. We also discuss the practical realization mechanisms of the algorithm.     

Selfish routing and wavelength assignment strategies with advance reservation in inter-domain optical networks

The main challenge in developing large data network in the wide area is in dealing with the scalability of the underlying routing system. Accordingly, in this work we focus on the design of an effective and scalable routing and wavelength assignment (RWA) framework supporting advance reservation services in wavelength-routed WDM networks crossing multiple administrative domains. Our approach is motivated by the observation that traffic in large optical networks spanning several domains is not controlled by a central authority but rather by a large number of independent entities interacting in a distributed manner and aiming at maximizing their own welfare. Due to the selfish strategic behavior of the involved entities, non-cooperative game theory plays an important role in driving our approach. Here the dominant solution concept is the notion of Nash equilibria, which are states of a system in which no participant can gain by deviating unilaterally its strategy. On this concept, we developed a selfish adaptive RWA model supporting advance reservation in large-scale optical wavelength-routed networks and developed a distributed algorithm to compute approximate equilibria in computationally feasible times. We showed how and under which conditions such approach can give rise to a stable state with satisfactory solutions and analyzed its performance and convergence features.     

一种无线传感器网络蚁群优化路由算法

如何在资源受限的无线传感器网络中进行高效的数据路由是无线传感器网络研究的热点之一.将蚁群优化算法(ACO)应用于无线传感器网络的路由,提出一种无线传感器网络蚁群优化路由算法.该算法利用蚁群的自组织、自适应和动态寻优能力进行网络优化路径的建立与维护,采用Stigmergy的概念来减少控制信息的流量,以实现网络数据的高效传输.仿真分析表明,该算法和DD算法相比在传输延时方面性能相当,在路由代价方面效果显著.另外,该算法还具有可靠性高、适应性强等优点,并能够根据需要实现网络的拥堵控制和能量均衡等综合优化.     

Wavelength decomposition approach for computing blocking probabilities in WDM optical networks without wavelength conversions

We present an approximate analytical method to evaluate the blocking probabilities in Wavelength Division Multiplexing (WDM) networks without wavelength converters. Our approach assumes fixed routing with Random or First-Fit wavelength assignment. The new approach views the WDM network as a set of different layers (colors) in which, blocked traffic in one layer is overflowed to another layer. Analyzing blocking probabilities in each layer of the network is derived from an exact approach. A moment matching method is then used to characterize the overflow traffic from one layer to another. The results indicate that our approach is more accurate than previous works.     

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

如何在资源受限的无线传感器网络中进行高效的数据路由是无线传感器网络研究的热点之一。基于群智能优化技术的蚁群优化算法被广泛应用于网络路由算法。提出一种无线传感器网络蚁群优化路由算法,能够保持网络的生存时间最长,同时能找到从源节点到基站节点的最短路径;采用的多路数据传输也可提供高效可靠的数据传输,同时考虑节点的能量水平。仿真结果表明:提出的算法延长了无线传感器网络的寿命,实现无线传感器网络在通信过程中快速、节能的路由。     

Efficient fault-tolerant routing in multihop optical WDM networks

This paper addresses the problem of efficient routing in unreliable multihop optical networks supported by Wavelength Division Multiplexing (WDM). We first define a new cost model for routing in (optical) WDM networks that is more general than the existing models. Our model takes into consideration not only the cost of wavelength access and conversion but also the delay for queuing signals arriving at different input channels that share the same output channel at the same node. We then propose a set of efficient algorithms in a reliable WDM network on the new cost model for each of the three most important communication patterns-multiple point-to-point routing, multicast, and multiple multicast. Finally, we show how to obtain a set of efficient algorithms in an unreliable WDM network with up to f faulty optical channels and wavelength conversion gates. Our strategy is to first enhance the physical paths constructed by the algorithms for reliable networks to ensure success of fault-tolerant routing, and then to route among the enhanced paths to establish a set of fault-free physical routes to complete the corresponding routing request for each of the communication patterns     

Routing and wavelength assignment for hypercube in array-based WDM optical networks

Hypercube is one of the most versatile and efficient communication patterns shared by a large number of computational problems. As the number of edges in hypercube grows logarithmically with the size of networks, the complexity of network topologies can be significantly reduced to realize hypercube in optical networks by taking advantage of the parallel transmission characteristic of optical fibers. In this paper, we study the routing and wavelength assignment for realizing hypercube on WDM optical networks including linear arrays and rings with the consideration of communication directions. Specifically, we analyze this problem for both bidirectional and unidirectional hypercubes. For each case, we identify a lower bound on the number of wavelengths required, and design the embedding scheme and wavelength assignment algorithm that uses a provably near-optimal number of wavelengths. In addition, we extend the results to meshes and tori. By our embedding schemes, many algorithms, originally designed based on hypercubes, can be applied to optical networks, and the wavelength requirements can be easily derived using our obtained results.     

基于改进蚁群优化算法的分布式多播路由算法

蚁群优化算法在优化计算特别是在多播路由问题中得到了广泛应用,但在进行大规模优化时,蚁群算法与其它随机优化算法一样,存在着收敛速度慢易于限于局部最小点等缺点。为此,该文提出了一种新的改进蚁群算法。仿真实验表明,应用这种改进型蚁群算法于多播路由问题,可以得到比现有启发式算法更好的结果。     

全光网络中组播路由波长分配的一种遗传算法

在WDM网络中,组播是一种重要的通信需求。组播算法就是要建立一棵从源节点到目的节点的组播树,并给这棵组播树分配波长。但是在网络中有波长转换器的情况下计算的复杂性会大大增加。该文在分层图结构中基础上,提出了组播路由和波长分配的一种遗传算法,可以在满足时延约束的情况下,寻找费用最小的组播树,将路由和波长分配统一进行,同时考虑到了网络中波长转换器的存在。数值仿真实验结果表明该算法具有较好的平均性能和较低的时间复杂度。     

Particle swarm optimization-based DRWA for wavelength continuous WDM optical networks using a novel fitness function

Greater demand of bandwidth and network usage flexibility from customers along with new automated means for network resource management has led to the concept of dynamic resource provisioning in WDM optical networks where unlike the traditional static channel assignment process, network resources can be assigned dynamically. This paper examines a novel particle swarm optimization (PSO)-based scheme to solve dynamic routing and wavelength assignment (dynamic RWA) process needed to provision optical channels for wavelength continuous Wavelength Division Multiplexed (WDM) optical network without any wavelength conversion capability. The proposed PSO scheme employs a novel fitness function which is used during quantization of solutions represented by respective particles of the swarm. The proposed fitness function takes into account the normalized path length of the chosen route and the normalized number of free wavelengths available over the whole route, enabling the PSO-based scheme to be self-tuning by minimizing the need to have a dynamic algorithmic parameter ‘α’ needed for better performance in terms of blocking probability of the connection requests. Simulation results show better performance of the proposed PSO scheme employing novel fitness function for solving dynamic RWA problem, not only in terms of connection blocking probability but also route computation time as compared to other evolutionary schemes like genetic algorithms.     

WDM optical interconnects with recirculating buffering and limited range wavelength conversion

All-optical communication, in particular, wavelength-division-multiplexing (WDM) technique, has been proposed as a promising candidate to meet the ever-increasing demands on bandwidth from emerging bandwidth-intensive computing/networking applications. However, with current technology, the cost of optical communication, especially the cost of optical buffering and wavelength conversion, remains a major concern for such applications. In this paper, we study WDM optical interconnects that utilize low cost recirculating buffering and limited range wavelength conversion. We first consider the packet scheduling problem in this type of interconnect, and formalize the problem of maximizing throughput and minimizing packet delay as a matching problem in a bipartite graph. We give an optimal parallel algorithm for this problem that runs in O(Bk/sup 2/) time, compared to O((N+B)/sup 3/k/sup 3/) time if directly applied to existing matching algorithms for general bipartite graphs, where N is the number of input/output fibers of the interconnect, B is the number of fiber delay lines, and k is the number of wavelengths. We also consider efficient switching fabric designs for this type of interconnect. We distinguish between the switching fabric connecting the input fibers to the output fibers and the switching fabric connecting the input fibers to the delay lines and show that by adopting the idea of concentration, the cost of the latter can be reduced significantly in terms of the number of crosspoints.     

时间依赖型车辆路径问题的一种改进蚁群算法

时间依赖型车辆路径规划问题(TDVRP),是研究路段行程时间随出发时刻变化的路网环境下的车辆路径优化.传统车辆路径问题(VRP)已被证明是NP-hard问题,因此,考虑交通状况时变特征的TDVRP问题求解更为困难.本文设计了一种TDVRP问题的改进蚁群算法,采用基于最小成本的最邻近法(NNC算法)生成蚁群算法的初始可行解,通过局部搜索操作提高可行解的质量,采用最大--最小蚂蚁系统信息素更新策略.测试结果表明,与最邻近算法和遗传算法相比,改进蚁群算法具有更高的效率,能够得到更优的结果;对于大规模TDVRP问题,改进蚁群算法也表现出良好的性能,即使客户节点数量达到1000,算法的优化时间依然在可接受的范围内.     

An improved ant colony optimization-based approach with mobile sink for wireless sensor networks

Traditional wireless sensor networks (WSNs) with one static sink node suffer from the well-known hot spot problem, that of sensor nodes near the static sink bear more traffic load than outlying nodes. Thus, the overall network lifetime is reduced due to the fact some nodes deplete their energy reserves much faster compared to the rest. Recently, adopting sink mobility has been considered as a good strategy to overcome the hot spot problem. Mobile sink(s) physically move within the network and communicate with selected nodes, such as cluster heads (CHs), to perform direct data collection through short-range communications that requires no routing. Finding an optimal mobility trajectory for the mobile sink is critical in order to achieve energy efficiency. Taking hints from nature, the ant colony optimization (ACO) algorithm has been seen as a good solution to finding an optimal traversal path. Whereas the traditional ACO algorithm will guide ants to take a small step to the next node using current information, over time they will deviate from the target. Likewise, a mobile sink may communicate with selected node for a relatively long time making the traditional ACO algorithm delays not suitable for high real-time WSNs applications. In this paper, we propose an improved ACO algorithm approach for WSNs that use mobile sinks by considering CH distances. In this research, the network is divided into several clusters and each cluster has one CH. While the distance between CHs is considered under the traditional ACO algorithm, the mobile sink node finds an optimal mobility trajectory to communicate with CHs under our improved ACO algorithm. Simulation results show that the proposed algorithm can significantly improve wireless sensor network performance compared to other routing algorithms.     

The performance of a hybrid routing intelligent algorithm in a mobile ad hoc network

End-to-end delay, power consumption, and communication cost are some of the most important metrics in a mobile ad hoc network (MANET) when routing from a source to a destination. Recent approaches using the swarm intelligence (SI) technique proved that the local interaction of several simple agents to meet a global goal has a significant impact on MANET routing. In this work, a hybrid routing intelligent algorithm that has an ant colony optimisation (ACO) algorithm and particle swarm optimisation (PSO) is used to improve the various metrics in MANET routing. The ACO algorithm uses mobile agents as ants to identify the most feasible and best path in a network. Additionally, the ACO algorithm helps to locate paths between two nodes in a network and provides input to the PSO technique, which is a metaheuristic approach in SI. The PSO finds the best solution for a particle’s position and velocity and minimises cost, power, and end-to-end delay. This hybrid routing intelligent algorithm has an improved performance when compared with the simple ACO algorithm in terms of delay, power consumption, and communication cost.     

WDM全光网络中Multicast的寻径与波长分配算法

在WDM全光网络中实现实时Multicast功能是计算机网络的应用要求,也是现代计算机网络的重要特征。该文提出了一种在WDM全光网络中实现实时Multicast的算法。该算法以辅助的波长图为基础,将寻径与波长分配统一进行,构造满足延迟约束的、具有较低成本的Multicast树,实现Multicast功能。