Project topics and materials
Get Complete Project Material File(s) Now! »
Fuzzy Logic Approach to the DLAN Topology Design Problem
Topology design of LANs is a complex process which requires simultaneous optimization of a number of design objectives. Important objectives include monetary cost, maximum number of hops between a source-destination pair, network average delay, and network reliability. None of these objectives on their own gives sucient information to decide the quality of the network topology. It is also the case that some of these objectives, such as the delay, can only be approximated. The complexity of the problem is further amplied by the con icting nature of some of these objectives. Thus, a trade-o between the con icting objectives is required. Fuzzy logic comfortably provides a mechanism to handle imprecise information since the logic provides a rigorous algebra for dealing with imprecise information. Furthermore, the logic is a convenient method of combining con icting objectives and expert human knowledge.
The rest of this section describes how fuzzy logic is employed in combining the four con icting objectives into a single overall objective. This overall objective estimates the quality of a solution in terms of membership of a given topology to the fuzzy set of quality topologies. For simplicity, the following discussion uses the terms cost, delay, hops, and reliability. The goal is to nd a high quality solution, represented by a linguistic variable `good topology’.
Upper and Lower Bounds for Objective Values
The extreme values of the objectives can be found as given below. Some of these values, such as MinC, MaxC, MinD, MinH, and MaxR, can be pre-calculated, while others such as MaxD, MaxH, and MinR are computed during the initialization step of the optimization algorithm.
For the cost objective, the minimum value, `MinC’, is found by using the Esau-Williams algorithm [80], with all the constraints completely relaxed. This guarantees that the minimum possible cost of the topology is obtained. The value of `MinC’ for the ve test cases is given in Table 3.2. The maximum value for cost, `MaxC’, is taken to be the cost generated by the initialization step of the optimization algorithm. Once the two extreme values are available, the membership value, c, of cost is computed using Equation (3.7).
The minimum value for the delay objective, `MinD’, is found by connecting all the nodes directly to the root node, ignoring all constraints. The value of `MinD’ for the ve test cases is given in Table 3.2. The maximum value of delay, `MaxD’, is taken to be the delay generated by the initialization step. Once these values are obtained, the delay membership value, d, is calculated using Equation (3.8). For the number of hops objective, the minimum value, `MinH’, is taken to be 1 hop. The maximum value, `MaxH’, is taken to be the maximum number of hops between any source-destination pair generated by the initialization step. The membership value of hops, h, is computed using Equation (3.9). Finally, for the reliability objective, the maximum reliability, `MaxR’, is found using the Esau-Williams algorithm [80], with all constraints relaxed. This guarantees the maximum possible reliability that could be attained. The value of `MaxR’ for the ve test cases is given in Table 3.2. The minimum reliability, `MinR’, is taken to be the reliability of the initial solution. The membership value for reliability, r, is found using Equation (3.10).
Application of UAO and OWA to Ex1
In Ex1 of Section 4.4.4, the rule requires optimization of all four objectives, with strong preference given to cost. Tables 4.1 and 4.2 summarize the results obtained after application of UAO and OWA to SimE using rule Ex1. These results re ect the percentage improvement of the nal solution (average of thirty runs) with respect to the initial solution. Simulations were run using values of = 0.5 and = 0.5 for OWA and UAO respectively. It is observed from these tables that both OWA and UAO demonstrated a noticeable improvement in cost for all test cases, as validated by the t-test for statistical signicance. These improvements range from 25.46% to 32.42% for UAO and from 25.26% to 32.57% for OWA. The average cost improvement for UAO was 29.17 %, while OWA showed an improvement of 28.38%. Thus, as far as cost is concerned, both operators performed almost equally well, with OWA having, in general, a slightly higher standard deviation than UAO. However, although strong preference was given to cost, there was a remarkable improvement in reliability, with improvements of 4.53% to 77.74% for UAO and 13.16% to 86.45% for OWA. In general, the improvement in reliability was also statistically signicant (as validated by a t-test), with the exception of n15 when UAO was used. One possible argument for this behavior is that the search space could be constricted such that no further improvement in cost is possible, irrespective of the emphasis placed on the cost objective. However, reliability might have a tendency to improve remarkably in most parts of the search space, with the improvement being more signicant in some regions. Thus, for the reliability objective, OWA performed better than UAO with almost the same level of standard deviation for most of the test cases, with the exception of n50.
1 Introduction
1.1 Motivation
1.2 Objectives
1.3 Methodology
1.4 Contributions
1.5 Organization of Thesis
2 Optimization and Optimization Approaches
2.1 Optimization
2.2 Constrained Multi-objective Optimization
2.3 Fuzzy Logic and Multi-objective Optimization
2.4 Optimization Algorithms
2.5 Conclusion
3 Topology Design of Distributed Local Area Networks
3.1 Background
3.2 Assumptions and Problem Statement
3.3 Design Objectives and Constraints
3.4 Fuzzy Logic Approach to the DLAN Topology Design Problem
3.5 Characteristics of Test Cases
3.6 Conclusion
4 The Unied AND-OR Fuzzy Operator
4.1 Denition of the Unied AND-OR Operator
4.2 Mathematical Properties
4.3 Fuzzy Rules for Topology Design
4.4 Preferences and UAO
4.5 Application of UAO to Topology Design
4.6 Empirical Results and Discussion
4.7 Conclusions
5 Fuzzy Stochastic Evolution Algorithm for DLAN Topology Design
5.1 Fuzzy Stochastic Evolution
5.2 Tabu Stochastic Evolution
5.3 Experimental Results
5.4 Dynamic Value of Rc
5.5 Comparison of OWA and UAO Operators
5.6 Conclusions
6 Fuzzy Simulated Evolution for DLAN Topology Design
6.1 Fuzzy Simulated Evolution Algorithm
6.2 Tabu Simulated Evolution
6.3 Experimental Results
6.4 Dynamic Bias
7 Fuzzy Simulated Annealing for DLAN Topology Design
7.1 Fuzzy Simulated Annealing Algorithm
7.2 Hybrid Simulated Annealing Algorithms
7.3 Results and Discussion
7.4 Dynamic Markov chain size
7.5 Conclusion
8 Fuzzy Ant Colony Optimization Algorithm for DLAN Topology Design
8.1 Fuzzy Ant Colony Optimization Algorithm
8.2 Results and Discussion
8.3 Conclusions
9 Fuzzy Particle Swarm Optimization for DLAN Topology Design
9.1 Fuzzy Particle Swarm Optimization Algorithm
9.2 Results and Discussion
9.3 Comparison of OWA and UAO
9.4 Conclusions
10 Comparison of Techniques
10.1 Comparison of Single Solution Algorithms
10.2 Comparison of Population Based Algorithms
10.3 Overall Comparison of OWA and UAO
10.4 Overall Best Algorithm
10.5 Conclusion
11 Conclusion
11.1 Summary
11.2 Future Research
Appendix A – Nomenclature
Appendix B – Linear Regression Analysis
Appendix C – Derived Publications
