Tối ưu hóa viễn thông và thích nghi Kỹ thuật Heuristic P3

The efficient design of telecommunication networks has long been a challenging optimization problem. It is made difficult by the conflicting, interdependent requirements necessary to optimize the network’s performance. The goal of the designer is to produce a minimum cost network that allows maximum flow of information (in the form of messages) between multiple source-sink pairs of nodes that simultaneously use the network. An optimum design method must also produce a network topology that efficiently routes these messages within an acceptable amount of time...
Nội dung trích xuất từ tài liệu:
Tối ưu hóa viễn thông và thích nghi Kỹ thuật Heuristic P3 Telecommunications Optimization: Heuristic and Adaptive Techniques. Edited by David W. Corne, Martin J. Oates, George D. Smith Copyright © 2000 John Wiley & Sons Ltd ISBNs: 0-471-98855-3 (Hardback); 0-470-84163X (Electronic)3Efficient Network Design usingHeuristic and GeneticAlgorithmsJeffrey Blessing3.1 IntroductionThe efficient design of telecommunication networks has long been a challengingoptimization problem. It is made difficult by the conflicting, interdependent requirementsnecessary to optimize the network’s performance. The goal of the designer is to produce aminimum cost network that allows maximum flow of information (in the form of messages)between multiple source-sink pairs of nodes that simultaneously use the network. Anoptimum design method must also produce a network topology that efficiently routes thesemessages within an acceptable amount of time. The problem of designing minimum-cost,multi-commodity, maximum-flow networks with efficient routing of messages in asynthesized network topology, is NP-complete (Clementi and Di Ianni, 1996; Gavish, 1992;King-Tim et al., 1997). NP-complete problems are those for which no known algorithm canfind the optimum solution besides brute force, exhaustive approaches. Thus, the challenge isto develop algorithms that run in polynomial time, which produce designs as near aspossible optimum. Since lower bounds on the network design problem are only known forsimple cases (involving only one type of communication link, for instance Dutta and Mitra(1993); Ng and Hoang (1983; 1987); Gerla and Kleinrock (1977)), the method of choice forselecting good algorithms is to compare their results on identical problems. The approachtaken in this chapter is to implement several of the best known methods in order toobjectively compare them on randomly generated instances of the network design problem.Telecommunications Optimization: Heuristic and Adaptive Techniques, edited by D. Corne, M.J. Oates and G.D. Smith© 2000 John Wiley & Sons, Ltd36 Telecommunications Optimization: Heuristic and Adaptive Techniques Because there is keen interest in designing optimum networks, many approaches havebeen developed, including branch exchange (Maruyama, 1978; Steiglitz et al., 1969), cutsaturation (Gerla et al., 1974), genetic algorithms (Elbaum and Sidi, 1995; King-Tim et al.,1997; Pierre and Legault, 1996), MENTOR algorithms (Grover et al., 1991; Kershenbaum,1993), and simulated annealing. In this chapter, we will look at the results of several ofthese methods and perform an in-depth study of several heuristic and genetic techniques.3.2 Problem DefinitionThe basic topology of a communication network can be modeled by an undirected graph ofedges and nodes (vertices) and is referred to by the symbol G(V, E). The network designproblem is to synthesize a network topology that will satisfy all of the requirements set forthas follows.3.2.1 Minimize CostEach edge represents a set of communication lines that connect the two nodes. Each linetype has a unit cost, uab, which is the cost per unit distance of line type b on edge a (whichlinks the nodes (i, j)). The unit cost of a line is a function of the line’s capacity. For instance,a 6 Mbps line may cost $2 per mile; a 45 Mbps line, $5 per mile, etc. Communication linetypes are available in discrete capacities, set by the local telephone company or mediacarrier. Normally, telephone tariff charges follow an ‘economy of scale’ in which the unitcost decreases with increasing line capacity. Additionally, some tariffs may have a fixedcharge per line type in addition to a cost per distance fee. In this case, both components ofthe line cost must be incorporated into one unit cost per line type, per edge (since each edgepresumably has a unique length). The fixed cost is divided by the length of the line andadded to the cost per unit distance to yield one unit cost per line type, per edge. If anundirected graph, G(V, E), has m edges, and each edge (i, j) has a distance dij and representsl line types, each with a unit cost uab, then the objective function of the optimization problemis: m l min ∑∑ d ij uab xab (3.1) a =1 b =1where xab is the quantity of line type b’s selected for edge a. Note that each edge a has twoother representations: (i, j), and (j, i). So, dij could also be referred to as da.3.2.2 Maximize FlowSince minimizing cost while maximizing flow are di ...