A communication network can be illustrated by set of nodes (or switches) and links (or arcs) where all nodes are connected by links. The typical communication network structure is composed of two levels. The first one is backbone network and the second one is local access network (LAN). The backbone network dedicate for delivery of information from source to destination (end to end) using its switching nodes. The LAN is typically centralized system that allows users to access hosts or local servers. This chapter focuses only on the backbone network design considered as distributed network. The advent of low cost devices has led to explosive growth in communication networks. The topology network design is a part of network planning which finds a topology in order to satisfy any constraints. One of the major advantages of distributed network over the centralized system is their flexibility to improve system reliability. The reliability of a system depends not only on the reliability of its nodes and links, but also on the topology of network. A completely connected network has the highest network reliability while the simple loop (ring) network has the lowest network reliability. Many researchers have studied the designing of the network when considering system reliability as a constraint or an objective. The reliable network design problems state as source-sink and all-terminal network reliability (also known as overall reliability). The problem of optimal topology network design that selects the links connections that either maximizes reliability or minimizes cost can formulate as a combinatorial problem. This problem is a well known NP-hard problem and very difficult to solve. For such problem, many researchers have studied with enumerative-based and heuristic method. Jan (1993) developed an algorithm using decomposition based on brand and bound to minimize link cost of communication network subject to reliability constraint. Aggarwal et al. (1982) employed greedy heuristic approach to maximize reliability given a cost constraint for networks with different reliability of links and nodes. Pierre et al. (1995) also used simulated annealing to find the optimal design for packet switching networks where considering the delay and capacity, but reliability was not. For the network design, Kumar et al. (1995) developed a genetic algorithm (GA) considering diameter, average distance, and communication network reliability and applied it to four test problems of up to nine nodes. with alternative link reliabilities and all-terminal network reliability constraint. Furthermore, Glover et al. (1991) used tabu search (TS) algorithm to choose the topologies of network when considering cost and capacity, but not reliability. Another work of TS algorithm, Beltran & Skorin-Kapov (1994) used TS algorithm to design reliable networks by searching for the least cost spanning two-tree, where the two-tree objective was a coarse surrogate for reliability. Recently, modern heuristic optimization techniques such as simulated annealing (SA), GA, evolutionary programming (EP), TS algorithm, artificial neural network (ANN), particle swarm optimization (PSO) and ant colony optimization (ACO) have been paid much attentions by many researchers because of their abilities to find an almost global optimal solution. Among of them, the TS algorithm expected as one of the advanced search technique. The TS algorithm is able to escape from local optimal and fast converge to global optimum. However, a conventional TS algorithm might have a problem of reaching the global optimum solution in a reasonable computational time when the initial solution is far a way from the region where optimum solution exists. Nowadays, the personal computer has more high-speed computation. To solve the largescale problem, several computers may use for computation at the same time. This method called "parallel searches". On the other hand, the "multiple search" implemented in this chapter is executed by only one personal computer. The multiple searches help to find the promising region where the global optimum solution exists. This idea applies for improvement the performance of a conventional TS algorithm. Pothiya et al. (2006) developed the multiple tabu search (MTS) algorithm and applied this algorithm to design the optimal fuzzy logic PI controller. After that, MTS applied to solve the economic dispatch problem with generator constraint (Pothiya et al., 2008) . The MTS is the execution of individual TS algorithm simultaneously by only single personal computer. The MTS introduces the additional salient mechanisms for improvement of search process, i.e. initialization, adaptive searches, multiple searches, replacing and restarting process. The feasibility study of the MTS for this chapter demonstrated for solving the topology network design when considering both reliability and cost. The optimized results by the MTS compared to those obtained by the conventional approaches such as GA, TS and ACO in terms of solution quality and computational efficiency. The remainders of this chapter organize as follows. Section 2 describes the problem formulation, assumptions of system, and reliability calculation. Section 3 presents the principle of MTS algorithm for solving the topology network design. Section 4 illustrates the examples and simulation results. Finally, Section 5 contains the discussion and conclusion.
In addition, the Multiple TS algorithm REF was used to solve the NTD-CR problem with 19 nodes; however, the algorithm may not reach the global optimum solution in a reasonable computation time when the initial solution is far away from the region where the optimum solution exists.
Multiple Tabu Search Algorithm for Solving the Topology Network Design
Tabu Search
Tabu Search
Computer Science