Network design problems, formulations and solutions

Network planning and optimized design is critical to utilizing existing resources under low cost with a degree of quality of service. In this dissertation, we focus on network design analysis, formulation, and optimization techniques. We introduce typical network design problems, classifications, and their mathematical solutions such as Simulated Annealing (SA) and Genetic Algorithm (GA). We also propose a new heuristic method called Landscape Smoothing Search (LSS) to solve real network design problems. LSS is an improved hill climbing method that incorporates a new mechanism to escape from the traps of local optima.;In the network planning stage, node allocation and topology design is an important design problem. By carefully selecting backbone node and service node, we can minimize build cost. We introduce a new data structure to formulate this problem. This new data structure can greatly reduce the scale of design complexity and simplify constraint conditions.;In cognitive radio networks (CRNs), call admission control (CAC) is an important functionality. A call admission control (CAC) scheme for a homogeneous multi-service cognitive radio network (CRN) is investigated. The quality of service (QoS) requirements, such as call blocking probability, call dropping probability, and spectrum utilization are evaluated for each service class.;We then extend this CAC scheme for a heterogeneous multi-service CRN. A composite objective cost function is defined as a combination of QoS requirements for design optimization. To optimize the CAC performance in the heterogeneous multi-service CRN, we use our new heuristic method, called Landscape Smoothing Search (LSS), to deal with this hard problem. We compare the LSS technique with two existing popular heuristic methods: Simulated Annealing (SA) and Genetic Algorithm (GA).;In the virtual private network (VPN) design, our goal is to implement a logical overlay network on top of a given physical network. We model the traffic loss caused by blocking not only on isolated links but at the network level. We form the VPN design as an optimization problem of maximizing the carried traffic in the VPN. We propose a Fast Landscape Smoothing Search (FLSS) to deal with this VPN optimization. The simulation results show that the FLSS outperforms SA and GA both in terms of solution quality and optimization speed.