Design and Optimization of Free Space Optical Networks by In Keun Son A dissertation submitted to the Graduate Faculty of Auburn University in partial fulfillment of the requirements for the Degree of Doctor of Philosophy Auburn, Alabama December 13, 2010 Keywords: Free space optics, FSO, Network design, Network optimization Copyright 2010 by In Keun Son Approved by Shiwen Mao, Chair, Assistant Professor of Electrical and Computer Engineering Prathima Agrawal, Professor of Electrical and Computer Engineering Chwan?Hwa ?John? Wu, Professor of Electrical and Computer Engineering Abstract Recent advances in wireless communication technologies and the explosive growth of the number and variety of mobile devices and multimedia applications motivate the development of next generation wireless networks, i.e., beyond 4G mobile systems. Indeed, the compelling demand for extensive coverage and high capacity has brought about a challenging problem to design adaptive and scalable network architectures. Some broadband wireless technologies, such as WiMAX, millimeter-wave, and free space optics (FSO), have been developed to meet this demand. Free space optics have emerged as a promising technology for next generation wireless broadband networks [1] [2]. FSO is a wireless telecommunication system that uses free space as transmission medium to transmit optical data at high bit rates. Compared with traditional wireless technologies, such optical wireless links have many advantages, including cost effectiveness, long transmission distance, license-free operation, interference immunity, high bandwidth, and so on. In this dissertation, we propose to design and optimize broadband wireless networks based on the FSO technology. We first provide a comprehensive survey of prior work. We classify prospective global FSO networks into three categories, and present current state of the art in the field and discuss the challenging issues and open problems. The objective is to achieve a fundamental understanding of the context and importance of our research and proposed solutions. Next, we investigate the problem of building robust spanning trees for FSO networks. We adopt the notion of the algebraic connectivity from spectral graph theory as a measure of network robustness, and formulate it as a 0-1 integer linear programming (ILP) problem. The formulated problem is NP-hard. We then present a fragment selection and merging ii (FSM) algorithm, which is executed in a distributed and asynchronous fashion, to obtain a strongly connected spanning tree. FSM can be used not only for FSO network bootstrapping, but also for auto-reconfiguration in response to network dynamics during operation. We also investigate the design and optimization of a wireless access network, i.e., wireless mesh network, that exploits free space optical (FSO) communications. In order to improve the scalability of wireless mesh networks, we propose a hierarchical architecture: (i) the lower tier consists of mesh routers that are clustered based on traffic demand and delay requirements, and (ii) the cluster heads are equipped with wireless optical transceivers and form the upper tier FSO network. We develop the plane sweeping and clustering (PSC) and greedy edge-appending (GEA) algorithms for the lower and upper tiers respectively. The proposed algorithms are analyzed with regard to complexity and performance bounds, and evaluated via simulations. Finally, we study the problem of joint optimization of topology design and load bal- ancing in FSO networks. We consider FSO physical characteristics, cost constraint, traffic demand, and QoS requirements in the formulation, along with various objective functions in- cluding network-wide average load and delay. We first propose Reformulation-Linearization Technique (RLT)-based branch and bound (BnB) algorithm, which can produce highly com- petitive solutions with performance guarantees in the form of the bounded optimality gap. We then develop a fast heuristic algorithm to provide feasible solutions with significantly reduced computation time. This algorithm iteratively perturbs the current topology and computes optimal network flows for the new topology, thus progressively improves the con- figuration and load balancing of the FSO network. Our simulation results show that the fast heuristic algorithm can also achieve an optimality gap close to that of the BnB algorithm proposed in our prior work. We conclude this dissertation with a discussion of potential directions for future work, including distributed topology control, Wavelength Division Multiplexing (WDM) FSO net- works, and topology transformation. iii Acknowledgments Most of all, I would like to express my sincere gratitude to my advisor Professor Shiwen Mao without whom none of this would have been possible. He has been a constant source of invaluable support and enlighten guidance throughout my doctoral program. His extensive knowledge, continuous encouragement, and positive view have made my work very successful. It has been a deep pleasure to be working under him every single day of my Ph.D. program with his warm-heartedness. I also would like to thank my dissertation committee, Professor Prathima Agrawal and Professor Chwan?Hwa ?John? Wu for their valuable comments and suggestions regarding my research work. What I have learned from their classes can not be forgettable in my future. As an university leader, Professor Xiao Qin showed a great interest in my work. His comments have been very helpful and influential. Special thanks should given to Professor Soo-Young Lee for supporting me invisibly but tenderly. I want to appreciate my friends at Auburn University, Yingsong Hwang and Donglin Hu,for discussion and cooperation. I would like to thank the Korea Army and Korea DAPA (Defense Acquisition Program Administration). It has been great to stay with Korea military officers, Major Hyosung Kim, Major Dongjin Kim, Major Seungbae Park, Captain Wonsuk Kang, Captain Sangsung Lee, Captain Ehun Jung, and Captain Sunjai Kim, at Auburn. Finally, I show my all appreciation to my dear wife Jungmi ?Alice? In, my adorable sons Suuk ?Henry? Son, Houk ?Andy? Son, and Wihun ?Larry? Son, my parents, my parents- in-law, and my sisters and their husbands. All days in my doctoral program can exist with their patience, love, and belief. iv Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Free Space Optical Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Key Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Dissertation Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 A Survey of Free Space Optical Networks . . . . . . . . . . . . . . . . . . . . . . 5 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Classification of FSO Networks . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1 OWSNs (Optical Wireless Satellite Networks) . . . . . . . . . . . . . 10 2.2.2 OWTNs (Optical Wireless Terrestrial Networks) . . . . . . . . . . . . 11 2.2.3 OWHNs (Optical Wireless Home Networks) . . . . . . . . . . . . . . 13 2.3 Design Factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.1 Channel Condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.2 Link Availability and Reliability . . . . . . . . . . . . . . . . . . . . . 16 2.3.3 Automation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.4 Network Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3.5 Quality of Service (QoS) . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3.6 Production Costs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3.7 Eye Safety . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.4 Research Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 v 2.4.1 Channel Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4.2 PAT (Pointing, Acquisition, and Tracking) . . . . . . . . . . . . . . . 24 2.4.3 Advanced Hardware Techniques . . . . . . . . . . . . . . . . . . . . . 27 2.4.4 Networking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.4.5 Transport Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3 Building Robust Spanning Trees for Free Space Optical Networks . . . . . . . . 37 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.3 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.3.1 Model Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.3.2 Algebraic Connectivity Preliminaries . . . . . . . . . . . . . . . . . . 41 3.3.3 Algebraic Connectivity-based Topology Design . . . . . . . . . . . . . 42 3.4 Fragment Selection and Merging Algorithm . . . . . . . . . . . . . . . . . . . 44 3.4.1 Fragment Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.4.2 Asynchronous Merging . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.4.3 Example of FSM Operation . . . . . . . . . . . . . . . . . . . . . . . 48 3.4.4 Bootstrapping and Auto-reconfiguration . . . . . . . . . . . . . . . . 49 3.4.5 Computational Complexity . . . . . . . . . . . . . . . . . . . . . . . . 49 3.5 Simulation Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.5.1 Simulation Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.5.2 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 4 Tiered Topology Design and Optimization of a Free Space Optical-based Wireless Access Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 vi 4.2.1 Tiered Access Network Model . . . . . . . . . . . . . . . . . . . . . . 60 4.2.2 FSO Channel Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.3 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.3.1 Lower Tier: Optimized Clustering Problem . . . . . . . . . . . . . . . 63 4.3.2 Upper Tier: Topology Optimization Problem . . . . . . . . . . . . . . 66 4.3.3 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.4 Lower Tier: Cluster Formation . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.4.1 Plane Sweeping and Clustering Algorithm . . . . . . . . . . . . . . . 71 4.4.2 Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.4.3 Complexity Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.5 Upper Tier: Topology Optimization . . . . . . . . . . . . . . . . . . . . . . . 78 4.5.1 Theoretical Upper Bound . . . . . . . . . . . . . . . . . . . . . . . . 79 4.5.2 Greedy Edge-Appending Algorithm . . . . . . . . . . . . . . . . . . . 80 4.5.3 Alternative and Distributed Algorithms . . . . . . . . . . . . . . . . . 81 4.6 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 4.6.1 Optimized Clustering Results . . . . . . . . . . . . . . . . . . . . . . 83 4.6.2 Topology Optimization Results . . . . . . . . . . . . . . . . . . . . . 86 4.7 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 5 Joint Topology Design and Load Balancing in Free Space Optical Networks . . . 96 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 5.2 System Model and Problem Statement . . . . . . . . . . . . . . . . . . . . . 99 5.2.1 Network Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 5.2.2 FSO Channel Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.2.3 Performance Measures . . . . . . . . . . . . . . . . . . . . . . . . . . 101 5.2.4 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 5.3 RLT and Branch-and-Bound Algorithm . . . . . . . . . . . . . . . . . . . . . 104 vii 5.3.1 Reformulation and Linearization: OPT-TDLB(T1) . . . . . . . . . . . 104 5.3.2 Reformulation and Linearization: OPT-TDLB(T2) . . . . . . . . . . . 105 5.3.3 Branch-and-Bound Algorithm . . . . . . . . . . . . . . . . . . . . . . 107 5.4 Fast Heuristic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 5.4.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 5.4.2 Initial Topology Design . . . . . . . . . . . . . . . . . . . . . . . . . . 110 5.4.3 Multipath Routing for Load Balancing . . . . . . . . . . . . . . . . . 112 5.4.4 Topology Perturbation . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.4.5 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5.5 Simulation Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5.5.1 Simulation Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5.5.2 RLT and Branch-and-Bound Algorithm . . . . . . . . . . . . . . . . . 115 5.5.3 Fast Heuristic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 120 5.6 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 6 Summary and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 6.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 viii List of Figures 2.1 The conceptual topology of integrated optical wireless satellite, terrestrial, and home networks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Link reliability (?ij) vs Index of refraction structure parameter (C2n). The wave- length is 550 nm on the 4 km path. The ratios of Ith/I0 are 0.05, 0.10, 0.15, and 0.20 respectively. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3 Link reliability (?ij) vs Transmission distance (z). The wavelength is 550 nm. Transmission distance (z) ranges from 2 to 6 km. The refractive index parameter (C2n) is 10?15m?2/3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.4 An example architecture of outdoor FSO transmitter and receiver [3]. . . . . . . 28 3.1 An example illustrating the operation of the FSM algorithm. . . . . . . . . . . . 48 3.2 Spanning trees formed by FSM, MST, and BU, respectively, in a 7-node FSO network. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.3 Algebraic connectivity for random networks with various sizes. . . . . . . . . . . 52 3.4 Average edge weight for random networks with various sizes. . . . . . . . . . . . 52 4.1 Reference architecture for the tiered wireless access network. . . . . . . . . . . . 57 4.2 Algebraic connectivity examples when edges are deleted from an unweighted graph. 67 ix 4.3 The subgraph corresponding to A?? (marked as red squares and green diamonds) after deleting a node from a 500-node network deployed in a 1500 ? 1500 m2 area with r = 150 m and hmax = 3. . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.4 A tiered network designed using PSC and GEA. . . . . . . . . . . . . . . . . . . 84 4.5 PSC performance: number of clusters for various hmax values. . . . . . . . . . . 85 4.6 Computational cost reduction achieved by using the reduced adjacency matrix A??. 86 4.7 Algebraic connectivity for the small network.. . . . . . . . . . . . . . . . . . . . 87 4.8 Algebraic connectivity for the large network. . . . . . . . . . . . . . . . . . . . . 89 4.9 Algebraic connectivity vs. network parameters. . . . . . . . . . . . . . . . . . . 90 4.10 Lattice topologies of 20-node networks. . . . . . . . . . . . . . . . . . . . . . . . 91 4.11 Algebraic connectivity of lattice networks. . . . . . . . . . . . . . . . . . . . . . 92 5.1 Convergence of the branch-and-bound algorithm for the 5-node network with optimality gap ? = 0.01,0.01, and 0.07, respectively. . . . . . . . . . . . . . . . . 116 5.2 Convergence of the branch-and-bound algorithm for the 7-node network with optimality gap ? = 0.01,0.01, and 0.07, respectively. . . . . . . . . . . . . . . . . 117 5.3 Performance of the heuristic algorithm for the 7-node network, comparing to the results of the branch-and-bound algorithm. . . . . . . . . . . . . . . . . . . . . . 121 5.4 Performance of the heuristic algorithm for the 15-node network. . . . . . . . . . 122 x List of Tables 2.1 Characteristics of optical wireless satellite, terrestrial and home networks . . . . 9 2.2 FSO challenges and possible solutions . . . . . . . . . . . . . . . . . . . . . . . 21 3.1 Fragment Selection and Merging (FSM) Algorithm . . . . . . . . . . . . . . . . 45 3.2 Comparison of Execution Times (sec) . . . . . . . . . . . . . . . . . . . . . . . . 53 4.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2 Plane Sweeping and Clustering (PSC) Algorithm . . . . . . . . . . . . . . . . . 72 4.3 The Greedy Edge-Appending (GEA) Algorithm . . . . . . . . . . . . . . . . . . 80 4.4 Distributed GEA Algorithm at FSO Node i . . . . . . . . . . . . . . . . . . . . 83 5.1 Branch-and-Bound Algorithm for Problem OPT-TDLB. . . . . . . . . . . . . . 108 5.2 Heuristic Algorithm for Problem OPT-TDLB. . . . . . . . . . . . . . . . . . . . 109 5.3 Average Building and Execution Time per Subproblem for the Branch-and-bound Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.4 Average Building and Execution Times per Iteration with the Heuristic Algorithm.124 xi Chapter 1 Introduction 1.1 Free Space Optical Networks The field of wireless communications has been extensively researched in order to take advantage of beneficial properties over wired communications such as mobility and flexibility. Due to the rapid growth of wireless technologies, the number and variety of mobile devices are explosively increased. Furthermore, demand for multimedia data services over traditional voice service ignites the necessity of higher capacity and speed of networks. These changes have stimulated researchers to propose broadband wireless communication architectures for the next generation. The main challenging problem is to provide adaptive and scalable network architecture, which can support high bandwidth and wide coverage for pervasive mobile users. Of course, broadband communication technologies like WiMAX, millimeter- wave, and free space optics (FSO) have been introduced recently. Compared to the alternatives, wireless optical links have many advantages like cost ef- fectiveness, long transmission distance, license-free operation, high-bandwidth, and so on. FSO transceiver transmits optical data signals through free space at multi gigabit rates over kilometers. Additionally, FSO channels are immune to electromagnetic interference (EMI) and are secure with low probability of interception and low probability of detection (LPI/LPD) properties [4]. Due to these advantages, FSO has been considered a viable tech- nology for next generation broadband communications. However, FSO networks have not been widely popular yet because of insufficient availability and low reliability due to suscep- tibility to weather turbulence. Previous researchers have focused mainly on the problems in the physical layer in order to exploit properties of wireless optical channels and mitigate 1 performance degradation for several decades. Meanwhile, recent successful experimental re- sults have demonstrated the feasibility of FSO communications under desired requirements. This has opened up many new research areas. 1.2 Key Contributions In this dissertation, we propose to design and optimize broadband wireless networks based on free space optics. We first provide a comprehensive survey of current state of the art and enumerate challenges in FSO networks. Then, we address several problems of design and optimization of FSO-based networks. The key contributions are as follows: First, we classify prospective global FSO networks into three categories. Several existing overview paperson optical wireless communication include [2,5?7]. However, theseprior work do not represent global FSO network, but focus on their specific subnetwork(s). We roughly classify FSO networks into three types with detailed characteristics: (i) Optical wireless satellite networks (OWSNs), (ii) Optical wireless terrestrial networks (OWTNs), and (iii) Optical wireless home networks (OWHNs), according to the locations of optical transmitters and receivers and network size. It is meaningful to take a look at various FSO subnetworks and their integration, that results in end to end FSO. Second, we focus on FSO-based network problems, and discuss critical issues. This survey on free space optics will give a fundamental understanding of the importance of our future research and proposed solutions. FSO network problems reflect FSO specific properties, which are different from other wireless network issues. Third, we investigate the problem of building robust spanning trees for FSO networks by the measure of algebraic connectivity. We formulate it as a 0?1 integer linear programming (ILP) problem, and present a fragment selection and merging (FSM) algorithm, which is executed in a distributed and asynchronous fashion to compute highly competitive solutions. Compared to prior approaches, FSM can be used not only for FSO network bootstrapping, but also for auto-reconfiguration in response to network dynamics during operation. 2 Fourth, we address the problem of design and optimization of a tiered wireless access network that exploits FSO communications. We first partition current wireless access net- work, i.e., wireless mesh network, to satisfy traffic demands and delay requirements, and then embed each cluster head with FSO devices to build robust upper tier network. For each tier, we formulate the design and optimization problem as 0?1 integer linear programming (ILP) problem. We develop the plane sweeping and clustering (PSC) and greedy edge-appending (GEA) algorithms for the lower and upper tiers respectively. The proposed algorithms are analyzed with regard to complexity and performance bounds, and evaluated via simulations. Finally, we study the joint optimization problem of topology design and load balanc- ing in FSO networks. We consider FSO physical characteristics, cost constraint, traffic demand, and QoS requirements in the formulation, along with various objective functions including network-wide average load and delay. Since the problem is mixed integer linear pro- gramming (MILP) or mixed integer nonlinear programming (MINLP) problem according to objective function, we apply binary relaxation and Reformulation-Linearization Technique (RLT) methods to obtain a linear problem. We propose branch-and-bound-based solution procedure, which aims to provide an (1-?)-optimal solution where ? is an arbitrarily small number representing desired accuracy. Then, we develop a heuristic algorithm to provide highly competitive solutions with significantly reduced computation time. The heuristic al- gorithm iteratively perturbs the current topology and computes network flows for the new topology, thus progressively improving the configuration and load balancing of the FSO network. The efficacy of the proposed approaches is demonstrated with simulation studies 1.3 Dissertation Outline The dissertation is organized as follows. In chapter 2, we survey free space optical networks. We classify integrated FSO network into three subnetworks and enumerate their characteristics. We also present design factors and research challenges in FSO networks. 3 In chapter 3, we present an FSM algorithm to maximize network robustness by the measure of algebraic connectivity. We assume that there are FSO base stations, which need to be connected by a tree topology. We propose a distributed and asynchronous algorithm. In chapter 4, we propose two efficient algorithms for tiered wireless mesh networks: plane sweeping and clustering (PSC) and greedy edge-appending (GEA) algorithms for the lower and upper tiers respectively. The PSC algorithm is for minimizing the number of clusters satisfying QoS constraints, and the GEA algorithm is for maximizing network robustness of the mesh topology by the measure of algebraic connectivity. In chapter 5, we formulate the joint optimization problem of topology design and load balancing. We assume that network topology can be dynamically reformulated in order to optimize load balancing. The RLT-based branch-and-bound approach is applied for obtain- ing performance guaranteed feasible solution, and a fast heuristic algorithm is proposed. In chapter 6, we conclude this dissertation with a summary and discussions of future research directions. 4 Chapter 2 A Survey of Free Space Optical Networks Free Space Optical (FSO) networks, known as optical wireless networks, have emerged as a viable candidate for broadband wireless communications. FSO network ranges from home to satellite. However, FSO networks have not been popular because of insufficient availability and reliability. Researchers have focused on the problems in the physical layer to exploit properties of wireless optical channels. Meanwhile, recent technological development with successful results makes it possible to take advantage of high bandwidth. Some researchers are focusing on problems of network and upper layers. In this chapter, we classify prospective global FSO networks into three subnetworks, and give an account of them. We also present current state of the art and discuss challenging issues. 2.1 Introduction Free Space Optical (FSO) networks, namely optical wireless networks, are wireless telecommunication systems that make use of free space as transmission medium to deliver optical data signals at high bit rates. Wireless optical links have high capacities, but FSO communications have not prevailed so far in spite of long investigation history starting in the 1960s. As new advances are being made on optics and communication devices gradually, there has been considerable interest in analyzing and enhancing wireless optical links and adopting FSO technology for wireless access networks. Recent successful experimental results have demonstrated the feasibility of FSO communications under desired requirements [2,6]. Thus, FSO networks began to be considered as a viable candidate for broadband wireless networks of the next generation [1,7,8]. 5 123435256789 101121249711561221391368149 156164179182121418784 Figure 2.1: The conceptual topology of integrated optical wireless satellite, terrestrial, and home networks. Wireless communications have many advantages over wired communications such as low installation cost, simpler network topology, easier to operate and maintain, and so on. Wireless communications also allow users of mobile devices to access the Internet. For instance, 802.11 (?Wi-Fi?), Bluetooth, and IrDA are suitable for short-range wireless data communications [9]. Due to the rapid growth of wireless technologies, the number and variety of mobile users are explosively increased. Therefore, the amount of data traffics on wireless channels is rising. In addition, various multimedia services like AOD (Audio On Demand), VOD (Video On Demand), and P2P (Peer-To-Peer) data sharing stimulate the necessity for higher data rate networks. Radio wireless communications have been deployed and used popularly so far, but they have limitations on scalability and bandwidth. FSO networks are considered as a strong supplementary option. The advantages over radio wireless networks are outlined below. The comparisons between radio and optical wireless communications are mentioned in [1,5,10,11]. 6 ? Space optical links can support broadband data transmission. There are already com- mercial transceivers providing over Gbps performance over several kilometers. ? Optical wireless spectrum is a license-free. It is not necessary to obtain permission to use optical signals. ? Optical beams are immune to electromagnetic interference. ? Optical components are inexpensive and consume less power. ? Due to narrow beam and point-to-point transmission properties, space optical links have LPI/LPD (Low Probability of Intercept/Low Probability of Detection). ? Light sources with same specifications can be reused at overlapped deployment area or rooms in the building since light beams can not penetrate the walls and it is hard to interfere each other. Two main problems, however, have hampered practical deployment of wireless optical networks. The first problem is atmospheric turbulence which makes link quality unreliable and hard to estimate link status. Atmospheric turbulence affects performance directly in terms of various conditions like SNR (Signal-to-Noise Ratio), BER (Bit per Error Rate), outage frequency, and so on. The second problem is PAT (Pointing, Acquisition, and Track- ing) technique because of unguided narrow beam propagation through free space. FSO nodes normally emit very narrow beam so that it is very hard to find out receiver?s location, make a connection with precise alignment, and track the other side. Because of narrow beam prop- erty, stationary nodes should also need it. At first, researchers have concentrated on these critical problems especially on one hop link and achieved considerable results. Present com- mercial transceivers are mostly used for bridging two remote places. In previous introductory papers like [5,6,11,12], it is asserted that satisfactory link robustness and performance on single link are possible. As these single links was getting reliable and durable enough, some researchers start to have focused on problems on network and upper layers [1,7,13]. 7 There have been several informative papers on FSO networks, which present a broad view of FSO links and networks [1,2,5?7]. The objectives of [5,6] are to tidy up the po- tential advantages, specific properties, and limitations and present possible applications. Meanwhile, FSO networks are emerging recently as a viable solution of broadband wireless networks for the future. The emphases in [1,2,7] are placed on exploring extensive applica- tions of FSO networks and corresponding challenging issues. However, it is still necessary to take a look at the extensive range of FSO networks from home to satellite. Furthermore, FSO links still have challenging issues, thus research challenges need to be simultaneously considered. The remainders of this chapter are organized as follows. FSO network architecture and design factors are presented at first. FSO network architecture is for showing potential usability of optical links and design factors are to present characteristics and concerns about FSO networks. Research challenges are then mentioned with an emphasis on current state and future research issues. We then finish this chapter with final remarks. 2.2 Classification of FSO Networks Due to its high potentials for a broad spectrum of applications, FSO networks have been investigated and applied for networks ranging from a few meters to over thousands of kilometers. As illustrated in Fig. 2.1, FSO networks can be roughly classified into three types: (i) Optical wireless satellite networks (OWSNs), (ii) Optical wireless terrestrial networks (OWTNs), and (iii) Optical wireless home networks (OWHNs), according to the locations of optical transmitters and receivers and network size. It may not be easy to precisely delineate these networks, since various FSO subnetworks can be integrated and operated as a whole as in Fig. 2.1. We discuss each class of FSO networks in detail in this section, while their characteristics are summarized in Table 2.1. 8 Table 2.1: Characteristics of optical wireless satellite, terrestrial and home networks OWSNs OWTNs OWHNs OWHNs (IrDA) (MSD, White LED) Location Orbit High/open place Indoor Indoor Link distance ? 84,000 kilometers ? 10 kilometers ? a few meters ? tens of meters Channel Vacuum channel Air turbulent channel Weak turbulent channel Weak turbulent channel TX/RX FOV Very narrow Narrow About 30 degrees Wide Performance Beam pointing/tracking Atmospheric turbulence Power limit on eye safety Power limit on eye safety Impairment errors on long path (Fog, snow, and dust) Path blocking Multipath dispersion Factors Hardware Precise PAT technology Reliability enhancement Lighweight, portable, and Inter-cell backbone Requirement (Ex. Automatically (Ex. Spatial Diversity, inexpensive component Holographic optical steerable gimbals/beam) RF/FSO hybrid) diffuser Misc. Long distance coverage Many degrading factors Very short-range point- Exploiting reflection Difficulty in maintenance to-point link 1-to-n communication 9 2.2.1 OWSNs (Optical Wireless Satellite Networks) OWSNs are aimed for providing high-bandwidth optical wireless network access to end-users by making use of satellites positional advantages to cover large areas on the earth [2,12,14,15]. OWSNs can establish a global space backbone network with optical links, since satellites can support any terrestrial residents regardless of topographical limita- tions as long as a Line-Of-Sight (LOS) space path exists. Therefore, OWSNs can offer high quality data services even to isolated areas such as an island, a remote country, and so forth. OWSNs consist of different kinds of free-space links including inter-satellite, satellite-to-air, and satellite-to-surface optical links. Inter-Satellite Links (ISLs) are designated for routing data traffic hop-by-hop through satellites toward a final destination satellite that has up- and-down links between aircraft or the surface of the earth. Usually such links have very very high rates (?10 Gbps). Thus, ISLs can be used for inter-continental communications. The receivers can be stationary by placing on top of buildings, mountains, towers, and so forth. The receivers in motion are also possible by installing in airplanes, merchant vessels, ground vehicles, etc. Geostationary Earth Orbit (GEO; ?40,000 Km altitude), Medium Earth Orbit (MEO; ?5,000 - 15,000 Km), and Low Earth Orbit (LEO; ?1,000 - 2,000 Km) satellites, along with FSO links, can serve as commercially viable backbone nodes as reasoned in [12]: ? OWSNs can be an alternative for the current wired Internet, especially for over-the- ocean communications that are largely carried through undersea fiber communication systems. OWSNs do not need such communication infrastructure as undersea cables and can easily overcome the obstacles of large distances. ? With OWSNs, broadband wireless services can be provided even for secluded areas without much difficulty. Internet users who are on a mobile platform or are located remotely from the town can be provided with broadband data communications, which are otherwise hard to be achieved with the traditional access network technologies. 10 Service providers and architecture designers, however, should consider well both eco- nomical and technical factors to make sure that OWSNs will be successful as commercial systems since the initial investment on satellite systems is usually considerable and manual maintenance for unexpected defects is actually impossible after satellites are once launched. Therefore, several design factors such as physical topology, link capacity, and routing strat- egy are critical issues to consider [16]. There are considerable efforts on investigation and development for robustness and reliability [12]. Military organizations are also actively concentrating on developing OWSNs required for strategic and tactical operations. In May 2001, the U.S. National Reconnaissance Office (NRO) launched a Geosynchronous Lightweight Technology Experiment (GeoLITE) satellite to test laser communications. Furthermore, the U.S. Department of Defense (DoD) Military Satellite Communications (MILSATCOM) Joint Program Office has a plan to operate Trans- formational Satellite Communications System (TSAT) fully in 2016 as an integral part of the Global Information Grid (GIG) architecture for the U.S. military [17]. The TSAT net- work will be a FSO backbone using satellites supporting high data rate (tens of Gbps) to air-fighters, battleships, various troops, and so forth. The U.S. military also developed the fundamental technologies such as Steered Agile Beam (STAB), a technology to align direc- tion of an optical beam without steerable hardware devices like gimbals, and Airborne Laser Terminal (ALT) to operate in air-to-ground and air-to-air scenarios [18]. 2.2.2 OWTNs (Optical Wireless Terrestrial Networks) OWTNs, as known as outdoor FSO networks, establish a point-to-point and LOS optical wireless connection between two transceivers through outdoor atmospheric turbulence [1,5? 7]. Due to the LOS property, the distance of light propagation through free atmospheric space is from hundreds of meters up to tens of kilometers. This telecommunication paradigm has a great potential for wireless communications, and is becoming an important means for broadband Internet access. Some application scenarios are given below: 11 ? OWTNs can be used to bridge existing high-data-rate networks. For instance, FSO links for ship-to-ship, building-to-building, or community-to-community communica- tions can be established without ditching and laying optical fibers, while mobile ter- minals can be easily supported. ? OWTNs are effective solutions for the ?last? or ?first? mile problem [1]. Even though optical fiber cables have been widely used, there are still many end-users who do not have their own fiber connection for the Fiber To The Home (FTTH) service. OWTN can provide high bandwidth connection over large distance for remote end-users. ? OWTNs can be integrated with wireless radio networks, to mitigate the capacity and scalability limitations of Radio Frequency (RF) channels [19?22]. For example, the throughput and fairness of existing wireless mesh networks are seriously limited, espe- cially when the hop-count is large [23,24]. With a high-speed OWTN overlay on the wireless mesh networks, this scalability problem can be easily mitigated [25]. Service providers and architecture designers, however, should take into consideration how to handle link-quality deterioration caused by atmospheric loss like clear air absorption, scattering, refraction, as well as by bad weathers to maintain reliable connectivity and sup- port required level of Quality of Service (QoS). Many practical solutions have been suggested to adapt to changing atmospheric conditions so far such as diversity techniques [26], hybrid RF/FSO systems [10,21,27], multipath routing algorithms [16], and autonomous topology (re)configurations [4,28]. We will discuss these techniques in more detail later in this survey. Several FSO transceivers for commercial and military purposes have been developed [2, 7,29]. They can support from hundreds meters to kilometers transmission distances with data rates ranging from hundreds of Mbps to multi Gbps. Most transceivers have been developed for stationary terminals and links should be aligned by manual configurations so far. There have been some researchers who are investigating the more challenging case of mobile environments and autonomous topology management [4,7,28,29]. 12 2.2.3 OWHNs (Optical Wireless Home Networks) OWHNs, as known as indoor FSO networks, are desirable for wireless broadband com- munications inside houses and offices. OWHNs can be used to construct a Local Area Network (LAN) comprising of cells, where each cell is one of the divided spaces in the building [5,6,11,30?32]. Usually each cell has a base station to which several terminals are connected with short-range optical wireless connections such as infrared and Light Emitting Diode (LED). Unlike radio waves, infrared and LED beam can not penetrate walls. Each wireless optical cell should be confined to a room and need to be connected and integrated to a broadband backbone infrastructure. Usually each cell is free from signal interference of neighboring cells. As a result, the same beam specifications can be reused. According to different propagation modes, we can classify the indoor FSO links into two types: (i) LOS links and (ii) non-LOS link, as known as diffused links. A LOS link requires a direct path between the sender and receiver. Any unexpected obstacles between the sender and receiver can easily break the LOS link. Compared with non-LOS links, LOS links achieve higher capacity because of better power budget and the absence of multipath propagation effects. Beam-steering mechanism, however, is necessary to support mobile terminals with LOS links. In non-LOS links, a diffused light source is used to disperse a light beam within a room to take advantage of multiple path propagations caused by reflections from all sorts of surfaces in a confined space, such as walls, ceiling, and floor. As a result, non-LOS links are more robust to obstacles. However, there is a trade-off between network capacity and reliability of connection. Usually a diffused link supports a lower data rate as compared to LOS links. Infrared Data Association (IrDA) standards are excellent examples for indoor LOS links. IrDA was founded in 1993 to design wireless point-to-point optical link using infrared medium [9,33]. Currently, IrDA has become one of the popular standards for short-range wireless networks along with Wi-Fi [34] and Bluetooth [35]. Shipments of IrDA transceivers in 2001 were 100 million units and increased to over 300 million units in 2007. Compared 13 with Wi-Fi and Bluetooth, IrDA transceivers are competitive since they are economical. The cost of typical IrDA component is about $2 USD while Wi-Fi and Bluetooth components cost around $20 USD and $4 USD, respectively. To establish a connection, the typical IrDA technology requires that both transceivers be located within each other?s 30 degrees and 1 meter cone centered around the line of direct path. IrDA links support data rates varying from several Kbps to tens of Mbps. IrDA Very Fast Infrared (VFIR), for example, can sup- port a data rate of 16 Mbps. IrDA IrSimple is a new high-speed-infrared communications protocol designed for mobile devices. It aims at delivering 100 Mbps data rates ? some 25 times the data rates of today?s IrDA interfaces [33]. In December 2007, Gigabyte Infrared Communications (Giga-IR) was proposed to meet the demand of high bandwidth. The main objective is to develop a protocol for 1 Gbps data rate. At the official website of IrDA [33], there is a demonstration of 1 Gbps communication by opto-wireless technology. Two promising solutions for diffused OWHN have been proposed, namely, Multi-Spot Diffusing (MSD) [31,36] and white LED lights [32]. Both diffused OWHNs can support high speed data transmission over hundreds Mbps. In MSD system, the multibeam transmitter is located on the floor and projects multiple beams onto the surface of the room ceiling, and an angle diversity receiver reads diffusing spots. A holographic optical diffuser can generate multiple beams to be uniformly distributed to diffusing spots on a ceiling. The key factors to design MSD architecture are how to configure the shape of multiple beams on the entire surface and increase SNR (Signal-to-Noise Ratio) for each spot. As the other solution, White LED has been proposed since it is considered to be a future commercial lighting appliance with the potential for massive production. White LED has many beneficial properties such as low-power consumption, high brightness, and little shadowing, and is highly suited for indoor wireless networks. Furthermore, all electric equipments in the house and office are connected by power lines, each cell using white LED wireless networks can be integrated with Power Line Communications (PLC). Thus, the backbone infrastructure for cells is not required additionally. 14 OWHNs provide an effective solution to the proliferation of communication devices and services in home networks.OWHNs can provide sufficient data rates and channel capacity at low cost and are thus a strong candidate for future home networks. However, it is challenging to provide seamless roaming service to portable equipments, since light mediums usually cannot penetrate cell boundaries. 2.3 Design Factors In this section, we will discuss critical design factors in designing FSO networks. The critical factors have influence on the performance of FSO networks and bring up the direction of required technology development, protocols, and algorithms. 2.3.1 Channel Condition The unguided beam propagates through free space as the transmission medium, so the channel condition should be deliberately analyzed. The typical channel condition can be fluctuated and deteriorated by the atmospheric turbulence. Indeed, the atmospheric turbu- lence has been one of main clogging factors in practical usage. The atmospheric impairment and disturbance diminish the channel performance and make it hard to achieve constant availability and reliability. The refractive index structure parameter, typically denoted as C2n, presents the strength of the atmospheric turbulence, which has strong impact on the channel fading [2,37,38]. In [2], it says that if the deep fading lasts for ?1?100?s on the multiple Gbps optical channel, up to 109 consecutive bits can be lost. There are many atmospheric turbulence factors such as weather phenomena and scin- tillation by pressure, humidity, and temperature. When the weather condition is severe, the performance of free space link is significantly hampered. However the channel availability can be satisfactorily achieved with good probability even though severe weather condition can dominate the channel performance. According to [6], it already said by the experimental results in the early 1980?s that atmospheric attenuation is constantly low over 99 percent for 15 three major U.K cities. When sufficient power budget is applied, the availability up to 99.5 percent can be achievable. The scintillation, meaning the temporary spatial variation of light intensity, can degrade the performance of FSO links even in the clear weather. Especially, the variations in temper- ature dominate the refractive index structure parameter. According to [38], the scintillation effects induced by pressure and humidity are relatively small, and the effects by temperature is significant. This channel condition problem is mostly concerned in satellite-to-terrestrial and inter- terrestrial connections due to the air turbulent channel. In order to further understand the channel condition, various statistic channel models are proposed such as log-normal, K-, lognormal-Rician, and Gamma-Gamma distributions [39]. However, the inter-satellite links and OWHNs are rather free from atmospheric loss since inter-satellite optical beams propagate through the vacuum space and distance of OWHN links is negligibly short. 2.3.2 Link Availability and Reliability The availability and reliability of wireless optical channels are essential factors for FSO networks. If the wireless optical links suffer from low availability and reliability, the overall performance of FSO networks are also degraded. There are several sources that deteriorate link quality. In OWTNs, atmospheric turbulence degrades the link performance severely. Besides the atmospheric turbulence, the narrow beam property of FSO link is another cause that makes it hard to keep link strongly connected. Typical optical beam propagates with a few mrad narrow divergence, and the field of view (FOV) at the receiver is also small [7,29]. Due to these small angles, link loss or inaccurate alignment can happen. Thus, precise pointing, acquisition, and tracking (PAT) techniques are demanded. In the case of mobile platform like satellites and airplanes, PAT techniques become more challenging [40]. In ad- dition, optical beams can not penetrate non-transparent bodies, so if there is any stationary 16 obstacle on the LOS path between two points, it is impossible to make a link. Even though wireless optical link exists, it can suffer from temporary outage by moving objects like birds. The trivial approach is placing FSO devices where has less probability of disturbance by objects and better weather conditions on average. However, there are still opportunities to achieve higher availability and reliability of FSO links by considering one or some of affecting sources. Indeed, viable approaches have been suggested to strengthen availability and reliability of FSO channels such as autonomous PAT mechanisms [4,29,41], diversity techniques [26,42,43], hybrid RF/FSO systems [10,27], and so forth. 2.3.3 Automation There is a trade-off to operate FSO links between handwork and automation in order to establish/maintain link connections. The level of automatic operation depends on the applications. If the FSO link is built in the area with high reliability and does not need to be changed in direction for a long time, the manual operation with simple tracking mechanism can be possible with saving the costs. However, OWSNs, for example, require high level of automation for the purpose of topology control, since it is impossible to manipulate the direction after launching the satellites. If FSO transceivers operate autonomously, self- configuring and self-healing algorithms should be accompanied [4,28]. 2.3.4 Network Architecture The fundamental consideration in FSO networks is what kind of network architecture should be used. When it comes to FSO network architecture, pure FSO network or hybrid RF/FSO network should be selected. Pure FSO network consists of high-speed optical wireless links only [4,5,28,40,44?48]. It is based on the assumption that the connected channel can be mostly reliable in practical usage, even though FSO link can still suffer from performance degradation under severe atmospheric conditions. In the meanwhile, hybrid RF/FSO network is a mixture of RF and FSO links [19?21,25,27,49,50]. There can be 17 two motivations to select the hybrid network: (1) FSO is a still unreliable technology to be used exclusively. The radio has complementary features, such as reflection on the surface, penetration through obstacles, better survivability under fog or mist condition, and so on [27]. Thus, the radio channels can be a good back-up method even with much less capacity. (2) The current wireless radio networks have the limitation to upgrade into broadband wireless networks. Furthermore, wireless radio networks conventionally have the scalability problem. However, FSO technology has high potential to solve both problems [25]. Thus, we can upgrade our wireless radio networks by embedment of FSO links. When pure FSO network architecture is used, corresponding issue is which topology should be formed. Since network can be modeled as a graph G(V,E) where V and E represent wireless node and channel sets respectively, methodologies in graph theory can be considered to solve possible problems. In the case of hybrid RF/FSO network, there can be several types of designs. It can be hierarchical [25,46] or non-hierarchical [19,27,49]. FSO links can be selectively installed [19?21] or equally equipped with radio devices [27,49]. 2.3.5 Quality of Service (QoS) The broadband serviceability of FSO networks is one of promising advantages due to very high frequency band. The FSO networks will surpass radio wireless networks in the capacity since FSO links have no limitation on data speed [31]. According to [1], it says that 1.55 ?m laser operating on a 200 THz frequency can provide almost 200,000 times more capacity than a 2 GHz microwave signal. The FSO links can solve ?last mile? problem [1], increase the capacity of existing wireless networks [20], or constitute broadband wireless communication networks [2,28]. However, it has to say that capacity unboundedness is limited by the transceiver performance [31] and eye safety [5] even though multiple Gbps can be achieved. How much should be achieved in the capacity is determined by the aggregate of individual traffic passing through the link. 18 In addition to the broadband demand, the FSO networks should consider various QoS requirements such as end-to-end transmission delay, jitter, packet loss, and fairness by net- working algorithms and protocols. For example, the end-to-end delay in OWSNs is a consid- erable factor because of long round trip distance. Beyond that, frequent packet dropping on FSO channels is very challenging issue to the current TCP scheme [2,40,48]. Especially, the congestion control in the current TCP protocol can reduce the performance significantly, so adaptive TCP protocol should be demanded. 2.3.6 Production Costs FSO link has a point-to-point connection. Thus, each link needs two transceivers at both ends. It means that the number of required devices is proportional to the number of required connections in FSO networks, so the cost of the FSO device is an important issue to operate FSO networks. In OWHNs, the typical IrDA component costs just about $2 USD which is relatively cheap. However, the purchase and installation cost in OWTNs is estimated from $10,000 USD to $25,000 USD for medium and long-distance link during 2003 [51]. Hence, it is necessary to further develop transmitter and receiver in consideration of production cost. Chan in [2] pointed out high system costs and proposed photon-counting receivers and coherent system for vacuum and air turbulent channels in order to reduce system costs respectively. 2.3.7 Eye Safety High-power beams can suppress atmospheric disturbance and make it possible to meet required data rates further. However, laser sources beyond certain power threshold can be harmful to human body including eyes. Thus, it is indispensable to make each optical wireless networks have limitation on laser-emission power. There are laser safety standards like ANSI Z136.1 and IEC 60825-1 [5]. According to IEC 60825-1, the objective is to protect human body from excessive laser radiation which 19 wavelength ranges from 180 nm to 1 mm by classifying lasers and laser products based on their degree of hazard. The optical beams in Class 1 and 2 is considered completely safe and safe except direct and long exposure. The Class 3 beams can achieve a good power budget, but are recommended not to be contacted by human body. (See [5,6] for detail information.) 2.4 Research Challenges FSO networks have enormous potential capability over Gbps data rate per link. The transmission is normally LOS propagation with directional narrow beam over long distance. FSO channels are deployable on wide range areas from home to satellite. Those unique properties make researchers devote themselves to study. However, the researches in utilizing the potential of FSO networks have not been active even though many challenging problems are still required to be resolved. 2.4.1 Channel Modeling For several decades there have been many researches in mathematically modeling wire- less optical channels [52], since atmospheric turbulence impairs link performance. So, it is meaningful to understand channel property with fading factors. As a consequence, var- ious statistic channel models are proposed such as log-normal, K-, lognormal-Rician, and Gamma-Gamma distributions [39]. The advantage is that those models enable link reliability to be deduced from the probability density functions. In this survey, log-normal distribution is mainly described in order to show that link reliability is strongly affected by atmospheric turbulence. The atmospheric turbulence is represented as the refractive index structure parameter, ordinarily denoted as C2n. According to [37], the marginal distribution of light intensity fading induced by atmospheric turbulence can be statistically modeled as 20 Table 2.2: FSO challenges and possible solutions Challenges Viable Solutions Channel randomness - Mathematical channel modelingwith various fading factors FSO PAT - Coarse- and fine-pointing/detecting system link - (Omnidirectional) control channel Problems - Automation technology - Radio back-up communication Outage/Fading - Spatial/time diversity technique - RF/FSO hybrid architecture - Advanced hardware technology - Mitigating protocol (Interleaving, FEC, etc) Point-to-multipoint link - MSD- White LED - Self-(re)configuration algorithm FSO Dynamic network (Centralized/distributed fashion) network configuration - Autonomous PAT system problems - FSO link monitoring system Topology control - Special topology design algorithm (Tree, ring, mesh topology, etc) - Cross-layer optimization of topology design and network performance (Delay, congestion, traffic load, etc) - Wavelength routed optical network design - Topology transformation algorithm - Hierarchical/non-hierarchical structure Hybrid RF/FSO network - FSO link placement algorithm architecture - FSO node selection algorithm TCP performance - Efficient TCP variants- Path selection for end-to-end delay 21 fI(I) = 12? XI 1? 2? exp braceleftbigg ?(ln(I)?ln(I0)) 2 8?2X bracerightbigg (2.1) where ?2X is a variance of the log-amplitude fluctuation X of plane or spherical waves and I0 is a received average intensity without turbulence. The mean is eln(I0)+2?2X and the variance is (e4?2X ? 1)e2ln(I0)+4?2X. The standard deviation of log-amplitude fluctuation ?2X can be achieved by ?2X = 0.30545 parenleftbigg2? ? parenrightbigg7/6 C2n(L)z11/6 ? ? 2 R 4 (2.2) where 2pi? is the optical wave number with wavelength ?, C2n(L) is the index of refraction structure parameter with constant altitude L, z is a transmission distance, and ?2R is the Rytov variance which is defined as ?2R = 1.23C2n(L) parenleftbigg2? ? parenrightbigg7/6 z11/6. (2.3) According to [37], for atmospheric channels near the ground (L < 18.5m), C2n ranges from 10?13m?2/3 to 10?17m?2/3 for strong and weak atmospheric turbulence respectively. The common average is 10?15m?2/3. Assume that link reliability indicates the probability that the intensity of received signal (I) is over than certain threshold (Ith). Since the probability density functions for log-normal distribution can be known, the link reliability(?ij) between two points of nodes i and j can be obtained by 22 10?17 10?16 10?15 10?14 10?13 0.65 0.7 0.75 0.8 0.85 0.9 0.95 1 Index of refraction structure parameter (Cn2) Reliability ( ? ij ) transmittance Ith/I0 = 0.20 0.15 0.10 0.05 Figure 2.2: Link reliability (?ij) vs Index of refraction structure parameter (C2n). The wave- length is 550 nm on the 4 km path. The ratios of Ith/I0 are 0.05, 0.10, 0.15, and 0.20 respectively. 2000 2500 3000 3500 4000 4500 5000 5500 6000 0.9 0.92 0.94 0.96 0.98 1 Transmission Distance (z) Reliability ( ? ij ) transmittance Ith/I0 = 0.20 0.15 0.10 0.05 Figure 2.3: Link reliability (?ij) vs Transmission distance (z). The wavelength is 550 nm. Transmission distance (z) ranges from 2 to 6 km. The refractive index parameter (C2n) is 10?15m?2/3. 23 ?ij = P(I ? Ith) = integraldisplay ? Ith 1 2?XI 1? 2? exp braceleftbigg ?(ln(I)?ln(I0)) 2 8?2X bracerightbigg dI = 12 ? 12 erf parenleftbiggln(I th)?ln(I0) 2?X?2 parenrightbigg (2.4) where Ith is a threshold of received signal intensity [25]. Note that the ratio of Ith/I0 can be described as transmittance by the Beers-Lambert law [53]. It is known that the transmittance is determined by the distance and absorption coefficient. Normally, the transmittance, namely the ratio of Ith/I0, is reversely proportional to the distance and atmospheric attenuation. For the wavelength of 550 nm, the ratio threshold is adopted as 0.05 (5%) by the World Meteorological Organization. (In practice, FSO transceivers usually use optical beams with wavelength of 830, 1,300, or 1,550 nm.) The figures 2.2 and 2.3 show that for certain fixed ratio of Ith/I0 the link reliability is determined by standard deviation of log-amplitude fluctuation (?X), which is strongly influenced by weather conditions and transmission distance. Open Research Issues. A statistical modeling for intensity fluctuation has been challenging issue for long time, but it is still open research issue due to a broad spectrum of applications from home to satellite. Furthermore, there are many factors impairing link performance. For example, a channel model combining the effects of atmospheric turbulence and pointing errors is proposed [54]. 2.4.2 PAT (Pointing, Acquisition, and Tracking) Pointing, Acquisition, and Tracking (PAT) schemes have been essential problems for optical wireless links. Typical FSO beams have a broadband and point-to-point directional link in a beeline between sender and receiver. Transmitters shoot out narrow beams and divergence of the beams is less than a few mrad. Receivers have small angle degrees for 24 Field of View (FOV). This narrow beam property makes optical space links less-interfered, energy-efficient, and secure with LPI/LPD (Low Probability of Intercept / Low Probability of Detection). On the other hand, this properties make the FSO link hard to be established between two points. To maintain connectivity between two end-points, both sides need to point at each other with precise LOS direction during transmission. According to [7], OWSNs require 1-10 ?rad pointing accuracy for supporting a data rate of 10 Gbps. As the distance between the two end-points gets larger, it becomes more challenging to design effective PAT techniques. In OWSNs, the propagation distance between two satellites can be up to 84,000 km. It is a great challenge to design precise PAT techniques for maintaining high date rates. The pointing mechanism starts with finding out where potential nodes exist for es- tablishing a link in the three dimensional free space and then proceeds to the connection procedure. Since there may be many connection options when multiple nodes are within range of each other, FSO nodes need to coordinate themselves with respect to which node to point to. That is, there is an inherent network design problem associated with the pointing mechanism [25]. Even for stationary nodes, e.g., where FSO transceivers are mounted on top of buildings or geostationary satellites, it is non-trivial to establish an initial connection between two transceivers due to the narrow beam property. Furthermore, coordinating the two end-points, or synchronization, is also a challenging task, especially for mobile users. FSO network nodes, e.g., OWSN or OWTN nodes, are normally far away from each other. It is also non-trivial to synchronize the pointing procedure of the two end-points to establish a FSO link, even though the location of neighboring nodes are known. Several promising ap- proaches supported by specific hardware design have been proposed so far even though PAT problems still remain in research challenges. In order to recognize the existence of each other, coarse-pointing system having wide divergence angle of beacon signal is suggested [29,41], or coarse-sensing system can be an alternative option by wide FOV at the receiver. In [4], omnidirectional beacon mounted on gimbals is proposed as a prototype in order to exchange the location information. Once coarse-seeking procedure is completed, fine-pointing can be 25 followed. In [55], Shim, Milner, and Davis demonstrated a precise pointing technique by the experiment in outdoor testbed utilizing real-time Kinematic GPS coordinates. The acquisition mechanism is related to signal modulation and detection techniques. Many potential optical beams can be intercepted by a receiver aperture. Then the receiver should decide which signal is exactly desired and should be decoded. For example, a binary morphological technique in [4] is applied to distinguish different optical signals. In the aspect of physical architecture, the size of receiver aperture needs to be adjusted according to divergence angle of emitted laser beam and distance in order to maximize the efficiency of power budget. In [54], Farid and Hranilovic proposed statistical models for outage probability and achievable rates considering beam width, pointing error, and detector size. The tracking mechanism is also induced by the narrow-beam property. Signal tracking mechanisms have to be under consideration even between stationary transceivers since FSO links need very high pointing accuracy and misalignment of optical beams effects leads to reduction of available capacity and increment of outage probability. When node mobility is getting higher, more delicate hardwares and protocols are needed. If the receiver fails in keeping the track of current connection, it should be back to the coarse-seeking mechanism. For running a tracking mode in OWSNs, a centroid algorithm utilizing windowing techniques is applied by [41] in order to evaluate misaligned angle of received beam. In [56,57], the performance of alignment and tracking corresponding to terrestrial FSO stations is investi- gated. Open Research Issues. To the best of our knowledge, PAT problems has not been completely solved in spite of long investigations and promising approaches. ? Hardware architecture for dynamic PAT: Even though there have been active researches on PAT problems, they do not progress enough to be flexible to various platforms. Some researchers are interested in automated PAT mechanisms, but it is not fully exploited. For PAT issues, the integrated solution is needed. 26 ? Synchronization: Synchronized PAT process is another critical issue. To make initial connection, both transceivers need to point at each other simultaneously. In this case, certain method is also demanded in order to exchange information between them such as location, mobility, and time to point. If both platforms are in motion, synchronized alignment of transceivers for tracking is also required. 2.4.3 Advanced Hardware Techniques Link reliability is an important requirement in FSO networks. Indeed, the FSO networks can not be stabilized and acceptable in use unless transmitters and receivers can maintain reliable wireless optical channels constantly. Figure 2.4 in [3] shows an example of outdoor FSO transmitter and receiver. The transmitter converts electrical signals into optical power and emits light beams through the atmosphere with small divergence and the receiver trans- lates received optical signal into a photocurrent. As shown in the figure 2.4, the divergence angle of the transmitter, the aperture size of the receiver, and atmospheric loss can affect the efficiency of received power. The main concern has been the turbulent air conditions, so advanced techniques mitigating its effects are needed. There have been several approaches for advanced transmitter and receiver techniques in order to increase reliability and stability of FSO links like multiple input multiple output (MIMO) systems and hybrid of radio frequency and optical beam [10,27]. Adopting diffusive wireless optical systems like MSD [31,36] and white LED lights [32] can also increase link reliability, but have to sacrifice the performance and is not proper for outdoor FSO networks. Spatial diversity technique such as MIMO systems has been already proposed in radio wireless systems like WiMAX. Typical MIMO architecture has arrayed communication com- ponents on transmitters and receivers in order to increase capacity and overcome channel fading. Researchers in [15,26,42] ensure that this technique can be also useful in wireless optical networks and it is efficient in turbulent atmospheric channels. Lee and Chan in [42] 27 Data Point source emitter Optical Source Telescope Propagation Channel Lens Control Receiver Data Amplifier Figure 2.4: An example architecture of outdoor FSO transmitter and receiver [3]. shows that MIMO system can significantly reduce the probability of outage and increase power gain over single transmitter and receiver set. Hybrid RF/FSO architecture has been considered as one of practical techniques since both media can make up each other?s limitations. The radio frequency can penetrate, diffract, reflect, and scatter on obstacles and omnidirectional propagation is widely used in practice. Thus, it is not such difficult to maintain connections with neighbors. However, wireless radio networks have limitations on capacity and scalability. To achieve better performance, higher frequency should be used, but radio spectrum is not free. Furthermore, it needs more expensive and complicated components. On the contrary, optical beam is free in use and can support high data rate transmission. The small divergence angle of light source, however, makes it hard to establish and maintain the connection. To make matters worse, the performance of wireless optical channel can be deteriorated or unacceptable due to severe atmospheric conditions, inaccurate alignment, kinds of obstacles, and so forth. According to [27], it says about the weather that optical beams are highly susceptible to dense fog, mist, and dust particles, but relatively stronger to rain while radio frequency, especially over 10 GHz, suffers from significant deterioration by rain. There are several scenarios in operating hybrid system of RF and FSO. Typical example is that both channels work in parallel [2,10,27]. While FSO links support high bit rates, radio channels take charge of some parts of current traffic load. In the case of complete outage 28 of optical links, radio channels temporarily substitute for them. Meanwhile, Hranilovic and his fellows are interested in upgrading the capacity and mitigating the radio interference of existing wireless mesh networks by inserting FSO links selectively [19,20]. Desai and Milner in [28] suggested that radio frequency can be used for the purpose of maintaining FSO links connected. It is a possible option that radio channel is assigned to work as a control channel in the process of PAT. Open Research Issues. There have been many researches in improving FSO archi- tecture, and this goal is still actively under consideration. ? Advanced techniques: Advanced hardware techniques for improving reliability still need to be challenged including cost problem. For example, dynamic adjustment of beam divergence at the transmitter and FOV of the receiver according to distance and turbulent channel condition can increase power efficiency. As another example, Arnon in his results [43] say that adaptive wavelength selection can improve somewhat of link availability even though there is no magic wavelength for current channel condition. ? Potential of hybrid RF/FSO system: Hybrid system of RF and FSO links is not fully explored. Especially, it is still challenging to maximize reliability and bandwidth utilization under turbulent channel conditions [10,27]. This goal needs to consider solutions through multiple layers such as dynamic rate allocation, routing, and topology monitoring. 2.4.4 Networking One of promising applications by FSO technology has been to satisfy the need for high- speed bridging technology between optical fiber networks and end users, which is called the ?last? or ?first? mile problem [1]. However, because of technology infancy and insufficient studies on atmospheric effects, many researches have been confined within the physical layer problems for analyzing or enhancing the performance of optical wireless communications between two points. Now, recent experimental successes and technological improvement have 29 accelerated research interests in networking problems. Note that FSO-specific characteristics should be considered in FSO network problems: ? Influence by atmospheric turbulence: The reliability of wireless optical link is still af- fected by air condition, even though advanced technologies have been introduced [6,25]. Thus, current weather condition should be important factor in designing a topology. In [25], FSO network is modeled as a weighted simple graph, edge weight of which is determined by the index of refraction structure parameter and distance. ? Autonomous reconfiguration: Since FSO link has a point-to-point connection of narrow beam from several to thousands of kilometers, it is very difficult to maintain the con- nection. In OWSNs, manual maintenance for unexpected errors is almost impossible after satellite are once launched. As a promising technique, automated PAT (Pointing, Acquisition, and Tracking) technology has been introduced [4,49]. When the current link suffers from performance degradation by frequent outage, it is possible to select and configure alternative connection dynamically. ? Immunity to electromagnetic interference: In wireless radio networks, the existence of exposed and hidden terminals are well-known issues because of interference property of radio frequencies, so concurrent transmission control has been the fundamental prob- lem [25]. However, FSO communication is free from the interference, so the same FSO channel can be reused. This benefit can be also used in FSO network design with long distance property. The planar graph is a planar graph, which has no edge intersection when we map each node to a point in 2D space. For example, a topology generated by Delaunay triangulation or Voronoi tessellation is embeddable in the plane. However, even if there is an intersection between FSO channels in 2D space, it is mostly unlikely to be intersected in practical usage and it is assumed that FSO channels do not affect each other. Thus, FSO network does not matter whether the topology is planar, or not. 30 ? Degree constraint: Because of point-to-point connections, FSO networks need much more transceivers in comparison with radio networks. In addition, cost is a still big concern in FSO networks [2]. According to [51], FSO communication systems cost from $10,000 USD to $25,000 USD for medium and long-distance link during 2003. So, limitation on the number of transceivers is an acceptable assumption [4,25,44,46]. Degree constraint can be also caused by space concerns. For example, satellite and aircraft may not have enough space for FSO device. In networking problems, it should start with selection of FSO network architecture between pure FSO network and hybrid RF/FSO network. The pure FSO network consists of high-speed optical wireless links only [4,5,28,40,44?48], and the hybrid RF/FSO network is a mixture of RF and FSO links [19?21,25,27,49,50]. Of course, the architectural differences produce variant issues to be solved. In pure FSO networks, the main issue is to form a desired topology. Normally, network can be modeled as a graph G(V,E) where V and E represent wireless node and channel sets respectively. So, some methodologies in graph theory can be considered to solve possible problems. In literature work, several types of topologies have been targeted: tree [4,5,58], ring [1,28], mesh [25,44?47], and so on. The graph is mostly simple and degree-constrained. The simple graph means that all vertices have no self-loop and adjacent nodes do not have multiplicity. In [46,58], the graph is weighted by the function of traffic load and potential path, and the graph in [25] is weighted by the function of weather condition and distance. The purposes of FSO topology design are various and corresponding suggestions are also different. Several researches focus on problems in graph theory. In [4], the approximation algorithm is proposed to form a degree-bounded spanning tree in distributed fashion with minimizing computation cost. In [45], MDT (Modified Delaunay Triangulation), CN (Closest Neightbor), and FN (Farthest Neightbor) algorithms are presented in centralized fashion to build robust mesh topology by the measure of edge connectivity and diameter. With a same purpose, NTD (Network Topology Design) algorithm is proposed in [47]. In [44], 31 several heuristics to minimize the number of edges are proposed because of cost concerns. In [25], the GEA (Greedy-Edge Appending) algorithm is proposed to maximize the algebraic connectivity, which represents a quantitative measure of network robustness in spectral graph theory. In the meanwhile, topology design problem is also studied in consideration for network performance together. The motivation is that FSO topology can be dynamically reconfigured to maximize network performance. So, layered optimization technique is greatly challeng- ing [28,49,58]. Such cross-layer problems, however, are very complex, so efficient heuristics have been proposed. There are several proposals. It is assumed that traffic matrix can be given by analyzing the traffic pattern in the network [46,58]. For minimizing network con- gestion, several heuristics such as single-hop, multi-hop, rollout, and branch exchange are introduced and compared in [28]. The ring topology is considered and shortest path routing protocol is applied. The objective in [46] is to maximize the throughput by aggregate of traffic flow on each link. Single path and multipath routings are considered and correspond- ing heuristics are proposed respectively. For single path routing, several variants of rollout algorithm are compared. For multipath routing, an algorithm based on maximum weight matching is presented. In order to maximize overall traffic flow, [58] suggests a TD(Traffic delivery) algorithm to form a tree topology from candidate graph, which is weighted by traffic load and path. Since any pair of two nodes in a tree has only on path, routing path is determined by the tree topology. Hybrid RF/FSO networks, however, have somewhat different issues from those of pure FSOnetworks. Therecanbeseveraltypesofdesigns. Hierarchical[25,46]ornon-hierarchical[19, 27,49] network design is possible. FSO links can be selectively installed [19?21] or equally equipped with radio devices [27,49]. So, hybrid network design starts with questions: what is the purpose of hybrid of RF and FSO, what kinds of devices should be used, and what types of networks is selected. In [27], there are two application scenarios: WDM SONET ring architecture and terrestrial/airborne/satellite link protection architecture. This is surely 32 motivated by the fact that FSO link can support high data rates but it is strongly weak to turbulent weather. So, RF and FSO subsystems are combined in parallel for mutual protection. To utilize the hybrid architecture efficiently, two link restoration schemes are proposed: dynamic load switching and multihop routing based on link monitoring system. Hranilovic suggests two applications of hybrid RF/FSO networks [19,20]. In [20], FSO links are inserted into existing wireless mesh network, which is suffering from limitation to support increased traffic demands. The wireless mesh network is partitioned into clusters, and each cluster head is equipped with a FSO transceiver to have a connection to an ISP (Internet Service Provider). For this gateway placement problem, genetic algorithm and ILP (Integer Linear Programing) problem solver are used and compared. In [19], minimum number of FSO links are used to reduce RF link interference in populated WLAN (Wireless Local Area Network) mesh networks. Similarly, this problem is also solved by genetic algo- rithm and ILP problem solver. In [25], hierarchical RF/FSO network is considered to solve the scalability problem of wireless mesh networks. Wireless mesh network is partitioned in the lower tier and each cluster is connected by FSO networks in the upper tier. The FSO network in the upper tier is designed to maximize network robustness by the measure of algebraic connectivity. Then, the suggested architecture can solve the scalability problem and expect the enhancement of network performance. About throughput enhancement of the hybrid of RF and FSO, Wang and Abouzeid in [21] represent interesting result. They focus throughput capacity per node in hybrid RF/FSO network to shows the benefit of using FSO links. It is assumed that there are n RF nodes and m nodes among n RF nodes are additionally equipped with FSO transceivers. Then, the upper bound of capacity per node is c1W1radicalbig1/n log(n) + c2W2radicalbigm log(m)/n, where c1 and c2 are constant, and W1 and W2 are the capacity of RF and FSO link respectively. Open Research Issues. Even though there have been several literature work, network- ing problems are not fully investigated yet and several research issues still remain unresolved. 33 ? Distributed topology control: For the maintenance of wide range of FSO networks, dis- tributed topology control are necessary. The atmospheric condition can be temporarily severe in local area. Then, the distributed topology control can be more flexible. ? Various topology design and problem: So far, tree, ring, and mesh topologies have been proposed to form a FSO network. Because of a broad range of applications, the other topologies are still good candidate such as bipartite graph between two groups and digraph for a half-duplex FSO system. In addition, it is meaningful to consider weighted graph according to incomplete link reliability. ? Dynamic optimization of topology design and network performance: It is very chal- lenging that FSO topology can be reconfigured to improve network performance such as delay, congestion, and traffic load. The weather condition changes day and night, even in hours. The traffic flow is not consistent. Thus, adaptive solution by cross-layer optimization can be helpful to enhance network performance. ? WDM FSO network: According to [59], WDM (Wavelength Division Multiplexing) system in FSO communication can be applicable. So, wavelength routed optical net- work problem can be considerable [60] to minimize the number of wavelength changes in multihop delivery. Since FSO topology is not fixed, logical wavelength topology can be optimized by changing current network physically. ? Topology transformation: When FSO network is being reformed, there must be packet losses in the channel. The prototype device in University of Maryland shows that it takes less than one second to look around for the discovery purpose [4]. However, the amount of packet losses in the channel should be considerable due to the high capacity of FSO technology. So, efficient topology transformation technique is necessary from current to new network topology. 34 ? Applications of Hybrid RF/FSO networks: the applications of hybrid RF/FSO net- works have not fully investigated from home to satellite networks. Various kinds of wireless radio networks can be combined with FSO networks. 2.4.5 Transport Layer To date, successful transport protocol have not proposed in order to match with the distinct features of FSO networks [2]. Furthermore, there have not active researches for the transport layer problems, so the further investigation is necessary. In [61], it says that FSO links need different communication protocols since the behavior of optical wireless channels in error are distinct. Chan [2,13,61] shows that the current congestion control scheme in TCP significantly cause poor throughput. Especially in OWSNs, the transmission distance going through satellite links is enormously long. It means that end-to-end transmission delay should be considered. In addition, FSO networks support high data rate transmission with temporary outages. These properties can cause poor efficiency on typical transport layer protocol (TCP). When there are outages, the congestion control mechanism goes to slow start mode. However, it will take ?10-100?s of long round trips to recover full system rate after every outages. In [2], it shows that current TCP?s throughput is less than 10% even though advanced hardware techniques are utilized. Under such circumstances, end users can not take advantage of broadband services either. Hence, TCP variant which is flexible to long transmission delay and high speed having occasional outages is needed. Open Research Issues. Researches in data transport are in the early phase. For the problem of end-to-end transmission delay, Efficient TCP variant has not been successfully suggested yet. The distinct feature, e.g., high bandwidth through very long propagation distance with temporary outages, cause challenging issue in the transport layer. 35 2.5 Summary In this chapter, we present overall range of FSO networks from home to satellite in order to show a broad spectrum of applications in utilizing space optical links and discuss open research issues which have been exploited. Many researches have been confined within typical problems in the physical layer, but it is time to study FSO?s potential possibilities including networking and upper layers. 36 Chapter 3 Building Robust Spanning Trees for Free Space Optical Networks Free space optical (FSO) technology has been considered as a viable solution for broad- band wireless networks. It has high potential for military communications for the next decade. In this chapter, we investigate the problem of building robust spanning trees for FSO networks. We adopt algebraic connectivity as robustness measure, and formulate a 0-1 integer linear programming (ILP) problem. We present a fragment selection and merging (FSM) algorithm, which is executed in a distributed and asynchronous fashion to iteratively merge fragments until a spanning tree is formed. Our simulation study shows that FSM can achieve significantly improved connectivity at the cost of slightly degraded average link weight performance, compared to prior approaches. The FSM can be used not only for FSO network bootstrapping, but also for auto-reconfiguration in response to network dynamics during operation. 3.1 Introduction Network centric warfare (NCW) is a new theory to share information and enhance col- laboration in operations through robust networks [62]. Robustly networked forces can be aware of current combat situation and manipulate shared information. Ultimately, mission operation can be dramatically improved. The global information grid (GIG) is a communi- cation project of the United States Department of Defense to globally interconnect military forces [63]. There is a compelling demand for broadband wireless communications for mili- tary applications. 37 Free space optics (FSO) has been a viable technology for next-generation broadband communications. FSO transmits optical data signals through free space at high bit rates. It has high potential for military applications [7,63]. Besides broadband capacity, FSO links are immune to electromagnetic interference (EMI). They are secure with low probability of interception and low probability of detection (LPI/LPD) properties [4]. However, FSO link performance is degraded by turbulent atmospheric conditions. There has been considerable research on mitigating the impact of turbulent atmosphere [4,7,37]. It is important to design and optimize FSO network topology to achieve rich connectivity, and to make it auto-reconfigurable to adapt to bad weather conditions. In this chapter, we investigate the problem of building robust spanning trees in FSO networks. The problem is usually associated with the bootstrapping process: when isolated FSO nodes are powered on, an effective algorithm is needed to form a connected topology. The problem may also involve reconfiguration of FSO networks: when nodes or links fail, the network may be partitioned; an effective algorithm is needed to adapt to such dynamics to maintain a connected network during operation. In both cases, a distributed algorithm is needed since there is no network connectivity in the first place and there is no global information for centralized control. In a recent work [4], a distributed bottom-up (BU) bootstrapping algorithm was pre- sented to form a spanning tree from isolated FSO nodes. Although constructing a spanning tree with maximal node degree at most one larger than that in the optimal solution, the BU algorithm assumes that all participating nodes work synchronously and does not consider link quality. As indicated in the paper, such synchronous execution may be hard to achieve due to the lack of network connectivity. Furthermore, strong links should be preferred when constructing the spanning tree to obtain robust networks. In this chapter, we adopt algebraic connectivity from spectral graph theory as measure of network robustness [64]. Motivated by the observation that networks with the same set of nodes and same amount of links can have quite different algebraic connectivity, we aim 38 to build spanning trees with maximized algebraic connectivity. The formulated problem considers FSO link quality, node degree constraints, and algebraic connectivity, and is NP- hard. For competitive solutions, we develop a distributed fragment selection and merging (FSM) algorithm that keeps on merging network fragments, starting from isolated nodes, until a spanning tree is formed. Each fragment executes FSM independently to seek the ?best? neighbor to merge to with no need of synchronized execution, where ?best? means the largest algebraic connectivity after merging. The proposed FSM algorithm is evaluated with simulations. Compared with the min- imum weight spanning tree (MST) algorithms [65], the proposed algorithm can achieve significantly improved connectivity at the cost of slightly degraded average link weight per- formance. FSM also outperforms BU [4] on both connectivity and average link weight performance. The FSM algorithm can be used not only for bootstrapping an FSO network, but also for auto-reconfiguring an FSO in response to network dynamics during operation. The remainder of this chapter is organized as follows. Related work are reviewed, and we describe the system model and problem statement. Then, the FSM algorithm is presented. The performance of the heuristic algorithm is presented by simulation studies. 3.2 Related Work Building a spanning tree is one of the well-known problems in graph theory. A spanning tree is a connected and undirected graph with no loop and multiplicity over one. For graphs with weighted edges, MST algorithms have been well studied. The Prim?s algorithm and Kruskal?s algorithm are well-known centralized MST algorithms. In [65], Gallager, Humblet and Spira proposed a distributed MST algorithm assuming that each node knows the link weights of its neighbors. Aiming to minimize or maximize the weight sum of connected edges, each fragment seeks neighbor independently to connect to. Using link reliability as weights, it seems that a spanning tree with the maximum weight sum may also have rich 39 connectivity. However, in this chapter we will show that this is not always true. The weight sum does not seem tightly correlated with network robustness. Recently, there have been several papers on the design [25,66] and (re)configuration [4, 28] of FSO networks. In these works, integer linear programming (ILP) problems were formulated and various heuristic algorithms were proposed to provide sub-optimal solutions. In a recent work [21], Wang and Abouzeid investigated a hybrid radio-frequency (RF) and FSO multi-hop network and derived an upper bound on the per node capacity. In [4], the authors proposed a bottom-up (BU) algorithm for bootstrapping an FSO network. The objective is to form a spanning tree. BU is a distributed and synchronous heuristic, where the executions are synchronized among the fragments and fragment selection is solely based on node IDs (without considering link quality). As mentioned in [4], the time synchronization problem has not been solved. Algebraic connectivity is a useful tool from spectral graph theory [64,67]. It has been used in several papers as measure of connectivity [25,68]. In [68], a semidefinite program (SDP) formulation was presented for the relaxed problem. The authors proposed a greedy heuristic based on the Fiedler vector to grow a well-connected network. In our prior work [25], we study the problem of building a richly connected mesh topology for FSO networks, and iteratively inserts edges into a connected graph. Such greedy edge-insertion approach cannot be applied here since it starts from a spanning tree. It is also a centralized algorithm that may not be suitable for bootstrapping an FSO network with initially isolated nodes. 3.3 Problem Statement 3.3.1 Model Description We consider an FSO network consisting of n base stations. Each base station works as a backbone router, aggregating traffic though its RF transceiver to/from mobile users, and relaying the aggregate traffic through wireless optical links. Due to cost and space concerns, each base station has a limited number of FSO transceivers. We assume that 40 autonomous Pointing, Acquisition, and Tracking (PAT) technologies are incorporated, in order to seek available neighbors and maintain current connections. Thus location and channel information can be shared between two neighboring nodes. We adopt the log-normal model to characterize fading under turbulent atmosphere [37]. Under such model, link reliability ?ij is the probability that the intensity of received signal (I) is over than certain threshold (Ith). Letting I0 be the average received intensity, ?ij can be computed as ?ij = P(I ? Ith) = 12 ? 12 erf parenleftbiggln(I th/I0) 2?X?2 parenrightbigg . (3.1) The ratio Ith/I0 is determined by distance and absorption coefficient. ?ij also depends on the standard deviation ?X, which is strongly influenced by weather condition and transmission distance. An edge satisfying ?ij ? ?th becomes a candidate link for constructing the FSO network topology. An FSO network can be modeled as a simple graph G(V,E), where V is the set of vertices and E is the set of edges. Each vertex v ? V represents an FSO base station and each edge e ? E represents a wireless optical link between two distinct nodes. As in prior work [25], we assume that each FSO channel is full duplex. Due to line-of-sight transmissions with narrow beam divergence we assume symmetric link reliability, i.e., ?ij = ?ji for i,j ? V. The link reliability is used as edge weight. The simple graph G is undirected and weighted. 3.3.2 Algebraic Connectivity Preliminaries In graph theory, there are several graph connectivity measures, such as k-vertex/edge connectivity and bisection connectivity. We consider algebraic connectivity from spectral graph theory, which is a useful measure of network robustness [64]. The algebraic connec- tivity of a graph G is the second smallest eigenvalue of the Laplacian matrix L of the graph, denoted as ?2(L). It is a quantitative measure of graph connectivity: it is greater than zero 41 when the network has exactly one connected component, and a higher ?2(L) value indicates a better connected topology. Algebraic connectivity is shown to have close relation with various graph invariants. Consider a connected graph G that is not complete. Let Kv(G) denote the vertex connectiv- ity, Ke(G) the edge connectivity, ?(G) the minimum degree of the graph, and D the graph diameter. The following inequality condition holds true [69]: 4 D ?|V(G)| ? ?2(L) ? Kv(G) ? Ke(G) ? ?(G). (3.2) 3.3.3 Algebraic Connectivity-based Topology Design In this section, we formulate the spanning tree topology optimization problem as a 0-1 ILP problem. We assume each base station can have at most ? transceivers due to cost or space constraints. During bootstrapping, each node first searches its neighbors using the PAT mechanism as described in [4,28]. Each node then shares location and channel information with its identified neighbors. We now have a set of potential edges, denoted as Epot. The spanning tree design problem is to choose an (n ? 1)-edge set E from Epot such that (i) the unweighted degree of each node is no higher than ? and (ii) the algebraic connectivity ?2(L) of the resulting spanning tree is maximized. We follow the Laplacian matrix definition in [67]. Let edge l = {i,j} ? E be a link between node i and j with weight ?l. Let ml be a Rn vector, where [ml]i = 1, [ml]j = ?1, and [ml]k = 0 for k negationslash= i,j. Then, the n ? n Laplacian matrix L of a graph G is L(G) = summationtextn?1 l=1 ?l?ml?m T l = M?diag(vector?)?M T, where diag(vector?) ? R(n?1)?(n?1) is a diagonal matrix with diagonal elements ?l, l = 1,2,...,n?1. Note that L is a positive semi-definite matrix, which has n eigenvalues satisfying ?1(L) ? ?2(L) ? ... ? ?n(L). Its smallest eigenvalue, ?1(L), is always zero, corresponding to eigenvector 1 = [1,1,...,1]T. The second smallest eigenvalue ?2(L) is algebraic connectivity that we aim to maximize. 42 The problem of finding the spanning tree that maximizes algebraic connectivity can be formulated as follows. maximize ?2(L) (3.3) subject to d(v) ? ?, for all v ? V (3.4) E ? Epot, (3.5) |E| = n?1, (3.6) where d(v) is the unweighted degree of node v. For edge l ? Epot, define an index variable xl as: xl = 1 if edge l is included in E, and xl = 0 otherwise. We have a 0-1 vector x ? {1,0}|Epot|. The FSO spanning tree design problem can be reformulated into a 0-1 ILP problem as follows. maximize ?2(summationtext|Epot|l=1 xl ??l ?ml ?mTl ) (3.7) subject to d(v) ? ?, for all v ? V (3.8) 1T ?x = n?1 (3.9) x ? {1,0}|Epot|. (3.10) The optimal solution consists of a boolean vector x that achieves the maximum algebraic connectivity. The formulated problem is NP-hard [70]. For small-sized networks, a centralized exhaus- tive search may be applied. Further, an edge-deleting greedy heuristic can also be applied to delete edges from a richly connected graph until a spanning tree is reached [25]. The Greedy Edge-Appending (GEA) algorithm in [25] can be used to grow a richly connected graph starting from a spanning tree. The challenge of using algebraic connectivity in building a tree stems from the fact that, as discussed, ?2(L) is always zero until a tree is formed. Fur- thermore, a centralized algorithm like GEA requires sharing link and topology information. 43 Although this is possible in [25] where a spanning tree is already formed, it is not an easy task now since we aim to build a tree in the first place [4]. In the following section, we develop a distributed heuristic algorithm for the formulated problem, which achieves significantly improved algebraic connectivity without centralized control and global information. 3.4 Fragment Selection and Merging Algorithm The FSM algorithm is a distributed and asynchronous algorithm where starting from isolated nodes, each fragment seeks the ?best? neighbor node or fragment and merge with it, until a spanning tree is formed. Since the objective is to form a tree with maximized robustness, each fragment identifies the ?best? neighbor or fragment with respect to algebraic connectivity. The FSM algorithm is presented in Table 3.1. Each node first adopts a precise PAT mechanism to search for potential neighbors and exchanges location and channel information with identified neighbors. When two fragments (or nodes) are connected by inserting an FSO link to form a larger fragment, we assume all the information are shared among nodes within the same fragment [4]. The unweighted node degree is upper bounded by ?. The two key components, Fragment Selection and Merging, are discussed in the following. 3.4.1 Fragment Selection Consider a tagged fragment that selects one of its neighboring fragment to merge to. Since the objective is to maximize algebraic connectivity, the tagged fragment selects a neighbor which can achieve the highest connectivity in the merged subgraph. We consider the following three cases: (i) node-to-node, (ii) fragment-to-node, and (iii) fragment-to- fragment. In the following, we examine the algebraic connectivity of these cases and then describe the fragment selection rules. First, assume that two single nodes i and j are to be connected. They must be neighbor of each other and the edge weight is ?ij. The resulting subgraph, denoted as T, consists 44 Table 3.1: Fragment Selection and Merging (FSM) Algorithm 1: Read current member information. 2: Read neighbor information; 3: IF there exists a neighbor to be connected 4: Try to connect to a single-node neighbor: 5: Search candidate edges; 6: Rule out edges not satisfying degree constraint; 7: Select the edge with the highest weight; 8: IF information of corresponding neighbor is not changed 9: Insert the selected edge; 10: ELSE 11: Update neighbor information; 12: Go to Step 3. 13: END 14: Update current member and neighbor information; 15: go to Step 3. 16: Try to connect to a fragment neighbor: 17: Search candidate edges; 18: Rule out edges not satisfying degree constraint; 19: Calculate candidate ?2?s; 20: Select the edge with the largest ?2; 21: IF information of corresponding neighbor is not changed 22: Insert selected edge; 23: ELSE 24: Update neighbor information; 25: Go to Step 3; 26: END 27: Update current member and neighbor information; 28: Go to Step 3; 29: IF current member is not changed; 30: Go to Step 33; 31: END 32: ELSE 33: Terminate with MST formed; 34: END 45 of nodes i and j, and the weighted edge. The algebraic connectivity of T can be derived. Let d?(i) be the weighted degree of node i ? V, defined as d?(i) = summationtexti ?ij for all j negationslash= i. We have summationtextni=1 ?i = summationtextni=1 d?(i) from spectral graph theory [69]. That is, the sum of all the eigenvalues is equal to the sum of weighted degree of all nodes. Since ?1 is zero for the connected subgraph, it follows that ?2(T) = summationtext2i=1?i(T) = summationtext2i=1d?(i) = 2?ij. (3.11) Second, consider the case that a fragment T1 is to be merged with a node i. Let T? be the resulting new fragment. This is equivalent to adding a new pendant vertex with an edge to a tree. According to Corollary 1.1 in [71], ?2(T?) is bounded as ?2(T?) ? ?2(T1). (3.12) Third, consider the case of merging two fragments T1 and T2 by adding an weighted edge to connect them. Let T?? denote the resulting new fragment. In [72], it is shown that the algebraic connectivity of T?? is bounded as ?2(T??) ? min{?2(T1),?2(T2)}. (3.13) Equations (3.11), (3.12), and (3.13) provides useful insights for fragment selection. Re- call that all potential links satisfy ?ij ? ?th. Usually ?th > 0.5 to exclude weak links. Therefore we have ?2(T) = 2?ij > 1. On the other hand, the algebraic connectivity of a graph is less than the minimum node degree if the graph is not complete (i.e., not fully connected) [69]. Any tree with n ? 3 is not complete and has at least one leaf node. Thus the corresponding ?2(T?) or ?2(T??) should be less than the minimum node degree 1. The single-edge subgraph T always has higher connectivity than the other two subgraphs T? and 46 T??. Consequently, when a node seeks a neighbor, an isolated neighbor with the highest edge weight is preferred over neighboring fragments. When all the cases of node-to-node merging are done, then we consider the cases of node-to-fragment and fragment-to-fragment merging. Assume that the tagged fragment T1 searches for a neighbor. From (3.12) and (3.13), the resulting new subgraph has an algebraic connectivity no larger than that of the original fragments. That is, the algebraic connectivity decreases as the tree grows. The strategy is to let each fragment find a neighbor that achieves the smallest reduction in algebraic connectivity. The tagged fragment T1 will first search for isolated neighbor nodes and merge to the one with the highest edge weight. When there is no such isolated neighbor, the tagged fragment T1 will choose a neighboring fragment with the highest algebraic connectivity to merge to. 3.4.2 Asynchronous Merging Duringbootstrapping, eachnodeorfragmentexecutestheFSMalgorithmindependently to search for a neighbor node or fragment to merge to. Unlike prior work [4], there is no need to synchronize the executions at the FSO nodes. As shown in Table 3.1, each fragment executes FSM independently. When the ?best? neighboring node or fragment is identified, the fragment requests to connect to the neighbor fragment. Before inserting a new link to connect the two fragments, FSM checks if the network state has been changed (e.g., the target fragment or node is merged to another fragment). If that is the case, the two fragments will not be merged and FSM is executed to identify the ?best? fragment under the updated neighbor information. Otherwise, a link will be inserted to merge the the two fragments. The synchronization requirement with respect to algorithm operation can be greatly relaxed [4]. 47 0.91 0.97 T1 T2 N2 N3N1 (a) Merging N1 and N3 T1 T2 N1 N2 N3 0.92 (b) Merging N1 ?N3 and N2 =0.37 T1 T2 N1 12 N2 N3 =0.3212 (c) Merging N1 ?N2 ?N3 and T1 T1 T2 N1 N2 N3 (d) Final tree topology Figure 3.1: An example illustrating the operation of the FSM algorithm. 3.4.3 Example of FSM Operation An example of FSM operation is given in Fig. 3.1. Assume that there are three node fragments, N1,N2, and N3, and two tree fragments, T1 and T2, each having more than one nodes. We assume that all the merging procedures are executed in the fragment that containing N1. In the beginning, N1 has three candidate edges with two single-node neighbor, N2 and N3, and one fragment neighbor, T1. Since FSM first seeks an isolated neighbor according to edge weight, N1 first selects the edge with the highest weight 0.97 (i.e., the solid line between N1 and N3 in Fig. 3.1(a)). Next, the fragment consisting of N1 and N3 selects the edge between N2 and N3, since an isolated node neighbor is preferred than a fragment neighbor, as shown in Fig. 3.1(b). In the third iteration, there are two fragment neighbors to choose. Fragment T1 is chosen since it has a higher algebraic connectivity value than fragment T2, as shown in Fig. 3.1(c). Finally, the edge between N3 and T2 is chosen since T2 is the last fragment to merge to. The algorithm stops and a spanning tree is formed. 48 3.4.4 Bootstrapping and Auto-reconfiguration TheFSMalgorithmcanbeusedtobootstrapanFSOnetworkandforauto-reconfiguration of an operating FSO network. As in [4], the FSM algorithm can be used to form a spanning tree when the isolated FSO nodes are started. Since link quality and connectivity are explic- itly considered, the resulting spanning tree has rich connectivity as compared to alternative approaches. During operation, there are three types of network dynamics: (i) one or more new FSO nodes are started, (ii) some operating FSO nodes fail, (iii) some operating FSO links are broken, and (iv) the quality of some operating FSO links are changed (e.g., due to weather changes). The FSM algorithm can be executed to handle all these cases to to automatically reconfigure the network and to restore a robust spanning tree. 3.4.5 Computational Complexity It is worth noting that the objective of BU is to obtain a connected graph as quickly as possible without caring about the weight or quality of the links. It has a low computational complexity O(n ?|E|pot), where n is the number of FSO nodes and |E|pot is the number of potential edges [4]. The proposed FSM algorithm considers link quality when building span- ning trees with better connectivity, but at the cost of comparatively higher computational complexity. The proposed FSM algorithm works in a distributed and asynchronous fashion, so we consider its worst case complexity. The worst case occurs when the nodes are connected one at a time. The worst case complexity is O(n3?|E|pot). Specifically, finding the algebraic con- nectivity (i.e., finding eigenvalues of an Laplacian matrix) incurs most of the computations. There should be (n?1) iterations in the worst case to build a tree. To determine the ?best? neighbor at each iteration, FSM compares at most |E|pot algebraic connectivity values, each computed for an n?n matrix. According to [73], it takes O(n2) to compute eigenvalues of a real symmetric n?n matrix (i.e., Laplacian matrix in our case). 49 3.5 Simulation Studies 3.5.1 Simulation Setup In this section, we present our simulation results to evaluate the performance of FSM and to provide a comparison with alternative schemes. In the simulations, we use two types of FSO networks: a 7-node network with a regular topology and randomly generated networks with various sizes. Specifically, we use the 7-node FSO network to visually demonstrate the resulting spanning trees and link weights. We then study the more general case of random networks with sizes ranging from 20 to 50 in a rectangular region. To maintain a constant density, we enlarge the region as the number of nodes is increased. We assume that each base station is stationary and can have at most five transceivers. Link connectivity between nodes is determined by link reliability, which is derived using the FSO channel model described. We set the reliability threshold as ?th = 0.9. The potential edge set Epot includes all the edges with a reliability value greater than the threshold. We consider three algorithms in our simulations: (i) FSM, (ii) Prim?s minimum spanning tree (MST) algorithm, and (iii) the bottom-up algorithm (denoted as BU) proposed in [4]. For comparison purpose, we use the algebraic connectivity of the resulting spanning tree graph as a measure of robustness. We also consider the average weight of the chosen links, which is an indication of the capability of choosing strong links. Since ?th = 0.9, each link in Epot has reliability ranging from 0.9 to 1, and thus the average weight is also within this range. 3.5.2 Simulation Results In Fig. 3.2, we plot the spanning trees formed by FSM, MST, and BU for the 7-node FSO network. For the 7-node network, six edges are chosen to build a spanning tree. As shown in Fig. 3.2, the maximum weight graph could not be well-connected according to the measure of algebraic connectivity. The algebraic connectivity values achieved by FSM, MST 50 12331234 1235 12361237 1237 1238 1239 1231 1 2 3 4 5 6 7 12331234 1235 12361237 1237 1238 1239 1231 1 2 3 4 5 6 7 12331234 1235 12361237 1237 1238 1239 1231 1 2 3 4 5 6 7 Figure 3.2: Spanning trees formed by FSM, MST, and BU, respectively, in a 7-node FSO network. and BU are 0.3617, 0.2519, and 0.2112, respectively; the average edge weight achieved by FSM, MST and BU are 0.9517, 0.9617, and 0.9467, respectively. The spanning tree formed by FSM yields the largest algebraic connectivity (43.59% normalized improvement), at the cost of slightly reduced sum weight (a decrease of 0.01) as compared to MST. In Fig. 3.3, we plot the algebraic connectivities for random networks with various sizes. Each point on the curves is the average of the results for 10 random topologies, with 95% confidence intervals plotted as error bars. It can be seen that networks with larger sizes have smaller algebraic connectivity, which is consistent with the analysis in Section 3.4.1. The corresponding average edge weights achieved by the three algorithms are plotted in Fig. 3.4, where each point is also the average of 10 random topologies and the 95% confidence intervals are plotted as well. It can be seen that FSM can produce a robust spanning with greatly enhanced algebraic connectivity in all the cases examined. Furthermore, such improvement is achieved at the cost of slightly reduced average edge weight. For the random networks examined, on average, FSM achieves 71.26% normalized improvement on algebraic connec- tivity over MST, and BU achieves 28.14% normalized improvement on algebraic connectivity over MST. The average edge weight over all cases achieved by FSM is 1.42% lower than that of MST, and the average edge weight over all cases achieved by BU is 4.31% lower than that of MST. 51 20 25 30 35 40 45 500 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 Network Size Algebraic Connectivity MST FSM BU Figure 3.3: Algebraic connectivity for random networks with various sizes. 20 25 30 35 40 45 500.9 0.91 0.92 0.93 0.94 0.95 0.96 0.97 0.98 0.99 1 Network Size Average Edge Weight MST FSM BU Figure 3.4: Average edge weight for random networks with various sizes. 52 Table 3.2: Comparison of Execution Times (sec) Number of Nodes MST FSM BU 20 0.003288 0.108970 0.031655 25 0.005526 0.176748 0.037470 30 0.009415 0.392533 0.040043 35 0.015275 0.566627 0.041535 40 0.024081 0.739200 0.062009 45 0.035776 0.865721 0.070993 50 0.051839 1.084987 0.089595 We find BU achieves better algebraic connectivity over MST. This is due to the fact that smaller graph diameter indicates better connectivity [69]. MST only considers the maximum weight edges among neighbors and expands the connected network using such edges, while BU can achieve smaller diameters than MST by merging neighboring fragments. Since BU considers neither link quality nor connectivity, it may choose edges with low weights close to ?th. In Fig. 3.4, we find the BU average edge weight is approximately 0.95, which is considerably lower than that of the other two algorithms. Note that such gap will increase when ?th is reduced (i.e., when edge weights are more diverse). Finally, we present the execution times for the algorithms in Table 3.2. The algorithms are implemented in MATLAB and executed in a desktop computer with an Intel core duo CPU 2.2 GHz and 2GB RAM. We assume that both FSM and BU algorithms work in the worst case when the nodes are connected one at a time. Compared with BU and MST, it takes more time to execute the FSM algorithm due to the need of solving eigenvalues. However, FSM is reasonably fast for practical systems: in the worst case, it takes about 1 sec to building a tree for a 50-node FSO network. 3.6 Summary In this chapter, we studied the problem of building robust spanning trees for FSO networks. We adopted algebraic connectivity as measure of robustness and formulated a 0-1 ILP problem. For the NP-hard ILP problem, we developed a distributed FSM algorithm that 53 can compute highly competitive solutions without synchronized execution. Our simulation studies showed that FSM can achieve significant improvements on algebraic connectivity at slightly reduced average edge weight, comparing to prior approaches. FSM can be used for both bootstrapping and auto-reconfiguration of FSO networks. 54 Chapter 4 Tiered Topology Design and Optimization of a Free Space Optical-based Wireless Access Network Although having high potential for broadband wireless access, wireless mesh networks are known to suffer from throughput and fairness problems, and are thus hard to scale to large size. To this end, hierarchical architectures provide a solution to this scalability problem. In this chapter, we address the problem of design and optimization of a tiered wireless access network that exploits free space optical (FSO) communications. The lower tier consists of mesh routers that are clustered based on traffic demands and delay requirements. The cluster heads are equipped with wireless optical transceivers and form the upper tier FSO network. For topology design and optimization, we first present a plane sweeping and clustering (PSC) algorithm aiming to minimize the total number of clusters. PSC sweeps the network area and captures cluster members under delay and traffic load constraints. For the upper tier FSO network, we present an algebraic connectivity-based formulation for topology optimization. We then develop a greedy edge-appending (GEA) algorithm, as well as its distributed version, that iteratively inserts edges to maximize algebraic connectivity. The proposed algorithms are analyzed and evaluated via simulations, and are shown to be highly effective as compared to the performance bounds derived in this chapter. 4.1 Introduction The recent explosive increases in pervasive mobile devices and wireless data applica- tions have greatly stressed the capacity of existing wireless access networks. The significant increase in wireless data volume will also have far-reaching impact on the design of future wireless access networks. To this end, wireless mesh networks (WMN) have emerged as a 55 promising technology for providing ubiquitous broadband wireless access to mobile users [74]. Recent years have witnessed significant growth in WMN research and deployment. However, WMNs are also known to suffer from poor scalability. In [75], Jun and Sichitiu showed that the per node throughput decreases as O(1/n), where n is the number of nodes. In [76], the authors demonstrated that starvation occurs even in the simple scenario where one-hop flows contend with two-hop flows for gateway access. This is largely due to the inefficiency and bi-stability of existing MAC protocols, as well as high penalty for multi-hop flows to re-capture system resources [76]. Historically, hierarchical network architectures have provided an effective solution to the scalability problem, as demonstrated in the Internet and wireless sensor networks [77]. In the case of WMNs, the authors in [78] investigated a hybrid network architecture consisting of an underlying n-node wireless ad hoc network and a sparse overlay network of m base stations, which are connected with high-bandwidth wired links. The authors showed that the asymptotic throughput capacity of the hybrid network increases linearly with m if m grows faster than ?n. In this chapter, we investigate the design and optimization of a tiered wireless access network, as illustrated in Fig. 4.1. The lower tier consists of a WMN with a large number of mesh routers providing wireless access to mobile users. To mitigate the scalability problem, we group mesh routers into clusters with bounded diameter. Traffic from/to the cluster members are aggregated and routed through the cluster head, which are equipped with free space optical (FSO) transceivers with multi-gigabit data rates and multi-kilometer ranges. With this architecture, resource contention mainly occurs within the cluster and end-to-end hop counts are greatly reduced due to the use of FSO links. Compared to the architec- ture in [78], FSO links are easier to deploy than wired links, and can be easily rearranged when traffic requirements change, or when links or nodes fail. The challenging task of QoS provisioning (e.g., delay and throughput) can be greatly simplified. 56 Mesh Router Cluster head with optical transceiver Wireless Optical Link Gateway node Internet Figure 4.1: Reference architecture for the tiered wireless access network. FSO communications provide cost-effective, license-free, and high-bandwidth links for the upper tier [1]. FSO links require line-of-sight (LOS) and are point-to-point connections. They are immune to electromagnetic interference and are secure due to point-to-point con- nection with narrow beam divergence. However, FSO links are subject to impairments in the open-air transmission medium, such as attenuation, atmospheric turbulence, obstacles, and beam misalignment. It is important to design topologies with rich connectivity to cope with transmission impairments. We address the challenging problem of network planning for the tiered wireless access network. The objective is to jointly determine the optimal partition for the lower tier WMN as well as the optimal topology for the upper tier FSO network. However, such a topology design problem is highly complex due to its combinatorial nature. To make the problem tractable, we take a divide-and-conquer approach to break it down into two sub-problems. The first sub-problem is cluster formation in the underlying WMN. The objective is to minimize the number of clusters (i.e., cost) while satisfying the delay and traffic load re- quirements. The second sub-problem is topology design and optimization for the upper tier 57 FSO network to achieve maximum connectivity for a given number of edges. The two sub- problems are coupled with the common objectives of minimizing the cost and maximizing the reliability of the tiered system, while satisfying the QoS requirements. The formulated sub-problems belong to the class of NP-hard problems [79]. To provide effective solutions, we take a graph theoretic approach to develop heuristic algorithms. First, we develop a plane sweeping and clustering (PSC) algorithm that sweeps the network area and captures cluster members one after another under delay and traffic load constraints. PSC chooses cluster members by manipulating the adjacency matrix and hop-count matrix of the underlying graph. We derive a lower bound on the number of clusters, which can be used as a benchmark for performance evaluation, and investigate effective schemes to reduce the computational complexity of PSC. Second, we present an algebraic connectivity- based formulation for FSO network topology optimization. We then develop a greedy edge- appending (GEA) algorithm, as well as its distributed version, that iteratively inserts edges to maximize algebraic connectivity. The proposed algorithms are analyzed with regard to complexity and performance bounds, and evaluated via simulations. They are shown highly effective for solving the network design and optimization problem as compared to the performance bounds developed in this chapter. The rest of this chapter is organized as follows. We first present the system model based on wireless mesh networks, of which network performance will be reinforced by free space optical technology on the upper tier. Then, design and optimization problems for the lower and upper tier networks are formulated. We present corresponding PSC and GEA algorithms, and analyze their performance, respectively. Simulation results are presented and related work is discussed. At last, we concludes the chapter. The notation is summarized in Table 4.1. 58 Table 4.1: Notation Symbol Definition Cij: capacity of the FSO link from cluster head i to j C2n: index of refraction structure parameter ?ij: reliability of FSO link {i,j} ?ij: weight of the FSO link {i,j} F: traffic matrix for the lower tier WMN F?: traffic matrix for the higher tier FSO network Mi: set of mesh routers in cluster i fMi: the larger one of the aggregate incoming and outgoing traffic of cluster Mi fmax: upper bound on the traffic load for each cluster H(G): hop count matrix of a graph G hmax: maximum hop count huv: hop count of the shortest path (? hmax) between mesh routers u and v yu: indicator for cluster head selection, yu ? {0,1} xuv: indicator for associating node u to cluster head v, xuv ? {0,1} xl: indicator for choosing link l, xl ? {0,1} ?(G): minimum degree of a graph G ?(G): maximum degree of a graph G Ki: number of FSO links on cluster head i di: unweighted node degree of vertex i n: total number of mesh routers in the WMN nc: number of chosen cluster heads m: total number of FSO links V: set of cluster heads, |V| = nc E: set of FSO edges, |E| = m Epot: set of potential FSO edges, |Epot| = mpot ?i(L): ith smallest eigenvalue of a graph G D: diameter of a graph G DMi: diameter of cluster Mi Ke(G): k-edge connectivity of a graph G Kv(G): k-vertex connectivity of a graph G ?(G): unweighted incidence matrix of a graph G L(G): Laplacian matrix of a graph G A(G): adjacent matrix of a graph G 59 4.2 System Model 4.2.1 Tiered Access Network Model As shown in Fig. 4.1, the lower tier of the wireless access network is a WMN consisting of n mesh routers that provide access to mobile users [74]. The mesh routers use broadcast radio transceivers and each covers a small service area. Without loss of generality, we assume the mesh routers form a connected network. A small fraction of the mesh routers are gateway nodes with connection to the Internet. Traffic to/from the Internet is routed via the gateways, while traffic between a pair of mesh routers are relayed through multi-hop routes. The traffic demand is characterized by a given traffic matrix F, where element [F]uv is the required traffic load from mesh router u to v. WMNs are known to suffer from throughput and fairness problems [76]. They are hard to scale to large sizes, resulting in the so-called ?a-few-hop? wireless networks. Although increasing the link data rate helps, it is not practical to have FSO transceivers at each mesh router, due to the cost constraint and the mismatch on data rate and range between radio and FSO links. We form clusters in the WMN. The mesh router traffic is aggregated at the cluster heads, which are connected with high speed FSO links to provide fast lanes for aggregate traffic. The upper tier network is designated to cover wide range with high data rate. FSO provides license-free and high-bandwidth links for this purpose. We assume each cluster head can be equipped with multiple FSO transceivers for rich connectivity, and the links are full duplex. The link capacity from cluster head i to j is denoted by Cij. Due to LOS and narrow beam divergence, we assume Cij = Cji, for all i negationslash= j. The main design considerations for FSO networks are cost and reliability. Available FSO systems cost from $10,000 USD to $25,000 USD for medium to long link ranges [51], more expensive than mesh routers. Therefore it is important to minimize the number of FSO transceivers (or, links) to reduce the deployment cost. In addition, FSO links are also susceptible to atmospheric 60 turbulence, unexpected tiny obstacles, and beam misalignment. It is important to achieve rich connectivity for the FSO topology. We assume three operation modes for the tiered access network: (i) Mode I: inter-cluster or Internet traffic are aggregated at cluster heads and forwarded through FSO links; (ii) Mode II: when an FSO link is temporarily blocked, a multipath routing protocol will redirect traffic through alternative paths in the upper tier FSO network; and (iii) Mode III: during severe weather conditions such as heavy snow, many FSO links may be blocked (like satellite links that could be blocked by a heavy thunder storm). The WMN will backoff to the normal mesh networking mode with radio communications and multi-hop relays. Experimental results in three U.K. cities from Jan. 1975 to Dec. 1983 show that atmospheric attenuation was constantly low over 99% of the time [6]. So the tiered access network will work in Modes I and II most of the time, exploiting the high-speed FSO links for high throughput/low delay performance. 4.2.2 FSO Channel Model We assume that point-to-point wireless optical transceivers are used for the cluster heads in the outdoor field. Practical FSO communication systems usually adopt intensity modulation with direct detection (IM/DD) with On-Off Keying (OOK) in the physical layer. There are several impairing factors through a LOS path, such as attenuation, atmospheric turbulence, unexpected tiny obstacles, and beam misalignment. In this chapter, we consider attenuation and atmospheric turbulence as characterized by the refractive-index structure parameter, which affect the FSO channel at the relatively large timescale relevant to network planning. Several irradiance distributions have been used for modeling a light beam propagat- ing through turbulent air. The log-normal distribution is shown to be highly accurate for weak weather turbulences [37]. The marginal distribution of received light intensity can be 61 modeled as fI(I) = 12? XI 1? 2pi exp braceleftBig ?(ln(I)?ln(I0))28?2 X bracerightBig , where I0 is the average received inten- sity and ?2X is the variance of the log-amplitude fluctuation. The variance has the form ?2X = 0.30545parenleftbig2pi? parenrightbig7/6 C2n(?)z11/6, where ? is the wavelength, C2n(?) is the index of refraction structure parameter with constant altitude ?, and z is the transmission distance. The received optical intensity of fixed FSO links mainly depends on C2n(?). For atmo- spheric channels near the ground, e.g., ? < 18.5 m, C2n ranges from 10?13 m?2/3 to 10?17 m?2/3 for strong to weak atmospheric turbulences, with typical value 10?15 m?2/3 [37]. Under log-normal fading, the reliability of an FSO link can be computed as ?ij = Pr{I ? Ith} = 12 ? 12 erf parenleftbiggln(I th)?ln(I0) 2?X?2 parenrightbigg , (4.1) where Ith is a threshold of received signal intensity. With a suitable threshold ?th, we define the weight of an FSO link as: ?ij = ?? ? ?? ?ij, if ?ij ? ?th 0, otherwise. (4.2) Due to LOS and narrow beam divergence, we assume that the links are symmetric, i.e., ?ij = ?ji for all i negationslash= j. The main factors affecting link weights are the transmission distance and atmospheric turbulence. If the nominal capacity for all FSO links is Copt, the effective capacity of an FSO link is Cij = ?ijCopt considering the transmission impairments. The upper tier FSO network, therefore, can be modeled as a undirected and weighted graph G(V,E), where V represents the set of cluster heads and E the set of FSO links. Each link (i,j) has weight ?ij for all i negationslash= j. 4.3 Problem Statement In this section, we formulate the design and optimization problem for the tiered wireless access network. Such network planning problems are combinatorial in nature and often have 62 large sizes. To make the problem tractable, we adopt a divide-and-conquer approach to consider the following two sub-problems: (i) the optimized clustering problem, on cluster formation in the underlying WMN; and (ii) the topology optimization problem, on designing the upper tier FSO network topology. These two sub-problems are integrated with the overall objectives of minimizing the cost and maximizing the reliability of the tiered wireless network, while satisfying the traffic and delay requirements. 4.3.1 Lower Tier: Optimized Clustering Problem The first step is to partition the underlying wireless routers into clusters, while consid- ering delay and traffic demand requirements. End-to-end delay consists of queueing delay, processing delay, and transmission (and retransmission) delay induced at each hop. For net- work planning purpose, we consider time averages of the delay components. This is because clustering is performed at relatively large timescales for which time averages matters. There is no need (or, it would be too costly) to adapt clusters in response to, say, queueing delay fluctuations at small timescales. As in prior work [80], we translate the delay requirement to a bound hmax, i.e., the maximum hop count of the shortest path from any mesh router to its cluster head. Assume the traffic matrix F ? Rn?n is given for the mesh network. When the clusters are formed, the aggregate incoming and outgoing traffic of cluster Mi, denoted by fo,Mi and fMi,o respectively, can be computed as: fo,Mi = summationtextnu=1,u/?Mi summationtextv?Mi [F]uv and fMi,o = summationtext v?Mi summationtextn u=1,u/?Mi [F]vu. Operators may enforce a bound on traffic load, fmax, for a cluster, i.e., fMi = max{fo,Mi,fMi,o} ? fmax. (4.3) Assuming that the transmission ranges of mesh radios are identical disks with radius r. For network design purpose, we focus on average link quality over relatively large timescales 63 and ignore fast variations of channel quality. The mesh network can be represented by a graph G, with vertices representing mesh routers and edges representing radio links among neighboring mesh routers. The adjacency matrix A ? Rn?n of graph G can be derived for given node locations and r. We have the following fact from graph theory. Fact 4.3.1 Let A be the adjacency matrix of graph G. The number of walks from vertex u to v in G with length k is bracketleftbigAkbracketrightbiguv [81]. Recall that cluster diameters are bounded by hmax. So we only concern with the maxi- mum hop count hmax, i.e., up to the (hmax)-th power of A. From Fact 4.3.1, the hop count of the shortest path between two nodes u and v can be computed as: huv = ? ?? ?? min{k}, if bracketleftbigAkbracketrightbiguv > 0,k ? [1,??? ,hmax] 0, otherwise. (4.4) The first line in (4.4) is for the case when nodes u and v are less than hmax hops away from each other; the second line is for the case when nodes u and v cannot belong to the same cluster. We can define a hop-count matrix for graph G, denoted as H ? Rn?n, with element [H]uv = huv as defined in (4.4), i.e., the hop count of the shortest path from node u to v, for u,v ? [1,??? ,n]. Let binary variable yu, u = 1,??? ,n, be the indicator whether the u-th mesh router is chosen to be a cluster head and let xuv be the indicator whether mesh router u is associated with cluster head v. The clustering problem can be formulated as a 0-1 integer linear 64 programming (ILP) problem as: minimize nc = summationtextnu=1yu (4.5) subject to summationtextn v=1xuv = 1,for all u (4.6) summationtextn v=1 (xuv ?huv) ? hmax,for all u (4.7) fMu ? fmax,for all Mu (4.8) xuv ? {0,1},yu ? {0,1},for all u,v. (4.9) The main objective is to minimize the number of clusters to reduce the cost of the FSO network, under delay and traffic load constraints. Constraint (4.6) requires that each mesh router is assigned to one cluster. Constraint (4.7) indicates that the hop counts from all cluster members to the cluster head is bounded by hmax. Constraint (4.8) represents the bound on the aggregated incoming and outgoing traffic for a cluster. Once the clusters are formed, the new traffic matrix for the inter-cluster traffic, denoted by F?, can be derived as: [F?]ij = ? ?? ?? yiyj summationtextnu=1summationtextnv=1 xuixvj[F]uv, if i negationslash= j 0, otherwise. The number of FSO transceivers at cluster head i, denoted as Ki, can be determined from F?, as: Ki = max{kmin,min{ki,kmax}}, (4.10) wherekmin ? [1,???, kmax]isapredefinedlowerboundonnodedegrees, ki = ?fMi/(?th ?Copt)?, and kmax = ?fmax/(?th ?Copt)?. In the following topology optimization problem, Ki will be the degree for cluster head i. As will be shown in (4.11), the connectivity of a graph G is 65 upper bounded by its minimum degree ?(G). Here we enforce a minimum value kmin for ?(G) to avoid trivial cases with poor connectivity (e.g., stubs or trees). Once the degrees for the cluster heads are derived, we have the following facts from graph theory, which will be used in topology optimization. Fact 4.3.2 The sum of node degrees is equal to twice of the total number of edges, i.e., summationtextn i=1 Ki = 2?|E| [64]. Fact 4.3.3 The number of edges of a simple graph (i.e., loop-free and without multiple edges) is upper bounded by parenleftbign2parenrightbig [64]. 4.3.2 Upper Tier: Topology Optimization Problem The next step is to optimize the topology of the upper tier FSO backbone. As discussed, the upper tier FSO network can be modeled as a weighted simple and mesh graph G(V,E) with |V| = nc vertices and |E| = m edges. The problem is to find a simple graph with vertex set V that achieves maximum connectivity for robustness to atmosphere turbulence and link failures, while satisfying node degree constraints (4.10). In the following, we first introduce algebraic connectivity and its properties, and then formulate the topology optimization problem. Algebraic Connectivity Preliminaries There are several graph connectivity measures, including graph degree and diameter, k-vertex/edge connectivity and bisection connectivity [81].1 In this chapter, we consider alge- braic connectivity from spectral graph theory, based on the following considerations [64,83]: (i) Algebraic connectivity is well-studied as a key component of spectral graph theory. It is amenable for mathematical modeling and effective algorithm design. Algebraic connectiv- ity can also provide bounds on graph operations such as subgraph, factorization, Cartesian 1Vertex (edge) connectivity is the minimum vertex (edge) cut for nonadjacent vertices i and j. Bisection connectivity is the likelihood that the graph would be separated into two components [82]. 66 Topology Origin graph One edge deletion One edge deletion Two edge deletions Two edge deletions Min degree 2 2 1 1 1 Diameter 2 2 2 2 3 4/(D1|V|) 0.5 0.5 0.5 0.5 0.3333 Algebraic connectivity 2 2 1 1 0.5858 Figure 4.2: Algebraic connectivity examples when edges are deleted from an unweighted graph. product, disjoint union, and complement of a graph. (ii) Algebraic connectivity has several interesting properties. It is closely related to graph invariants including diameter, mini- mum degree, and connectivity, thus being more helpful to understand network topology as compared to other measures. The algebraic connectivity of a graph G is defined to be the second smallest eigenvalue of the Laplacian matrix L of graph G, denoted as ?2(L), where L = L(G) [64]. The value of ?2(L) is a nice indication of graph connectivity with the following facts [84]. Fact 4.3.4 A graph is connected if and only if ?2(L) > 0. Fact 4.3.5 The number of zero eigenvalues of L(G) is equal to the number of disjoint com- ponents of G. Fact 4.3.6 For two graphs G1 = (V,E1) and G2 = (V,E2) with E1 ? E2, we have ?2(L1(G1)) ? ?2(L2(G2)). According to the facts, a graph with ?2 = 0 is partitioned, while a graph with ?2 > 0 is connected with one component. The algebraic connectivity is non-decreasing as more edges are inserted to the graph. Furthermore, algebraic connectivity is closely related to other connectivity measures. For a connected graph G that is not complete, let Kv(G) be 67 the vertex connectivity and Ke(G) the edge connectivity. The following inequalities hold true [83,84]: 4 D ?|V(G)| ? ?2(L2) ? Kv(G) ? Ke(G) ? ?(G), (4.11) where ?(G) is the minimum degree of the graph and D is the graph diameter. The inequalities are illustrated in Fig. 4.2. It is interesting to see that graphs with the same number of edges can have different ?2 values, as the second and third graphs in Fig. 4.2. For a given number of links, it is thus desirable to design a topology that maximizes the algebraic connectivity. Topology Design and Optimization Problem As a result of the clustering problem, the nc cluster heads form an upper tier FSO network, which is modeled as a weighted graph G(V,E). Each vertex vi ? V represents a cluster head with degree Ki, given in (4.10) as determined by the delay and traffic load requirements. The number of edges is m = |E| = (1/2)summationtextnci=1 Ki. Let the set of potential edges be Epot (i.e., set of edges with positive weight). We have E ? Epot and |Epot| = mpot. The topology design problem is to choose E from Epot such that (i) the degree of each vertex is satisfied, and (ii) the algebraic connectivity is maximized. We follow the Laplacian matrix definition in [67]. Assume edge l connects two distinct vertices vi and vj, l ? [1,??? ,m], vi,vj ? V. We also denote edge l as (i,j) when there is need to distinguish the endpoints. We define al ? Rnc of the unweighted incidence matrix ? ? Rnc?m of graph G as [al]k = ?? ???? ??? ?? +1, if k = i and ?ij > 0 ?1, if k = j and ?ij > 0 0, otherwise. (4.12) The nc ?nc weighted Laplacian matrix L of graph G is: L(G) = summationtextml=1?l ?al ?aTl = ?? diag(?)??T, (4.13) 68 where diag(?) ? Rm?m is a diagonal matrix with diagonal elements ?l, l = 1,??? ,m. It follows from the definition that L(G) is a positive semi-definite matrix, i.e., L(G) followsequal 0. Its smallest eigenvalue, ?1(L), is zero with eigenvector 1 = [1,1,??? ,1]T. The eigenvalues also satisfy the following inequality condition: 0 = ?1 ? ?2 ? ?3 ? ??? ? ?nc. Since we consider connected graphs, it follows from Facts 4.3.4 and 4.3.5 that there is only one zero eigenvalue. Therefore we have 0 = ?1 < ?2 ? ?3 ? ??? ? ?nc. (4.14) The topology optimization problem for the upper tier FSO network can be formulated as follows.2 minimize ?2(L) (4.15) subject to m = 12summationtextnci=1Ki ? parenleftbiggn c 2 parenrightbigg (4.16) di = Ki, for all i (4.17) E ? Epot, (4.18) where di is the non-weighted degree of node i. To optimize the topology, we populate edge set E by selecting edges from Epot, such that ?2 of the resulting graph G is maxi- mized and the delay and traffic load requirements are satisfied. The first constraint is from Facts 4.3.2 and 4.3.3. The second constraint is on the degree of each cluster head, such that the incoming and outgoing traffic from that cluster can be served. 2It is worth noting that Ki is determined using ?th as in (4.10), rather than the exact link reliability ?ij ? ?th, for (i,j) ? Epot. As a result, some redundancy is provided for the capacity of cluster Mi, which is useful to accommodate fluctuations in the instantaneous cluster Mi load. If such redundancy is unnecessary, we can modify the formulation by replacing constraint (4.17) with Copt ?summationtextj:(i,j)?E ?ij ? min{fmax,fMi}, for all i. 69 When the problem is solved, each potential link l ? Epot will either be chosen to be included in E or not chosen. Define binary variables xl, for all l ? Epot, as: xl = ? ?? ?? 1, if potential edge l is included in E 0, otherwise. (4.19) The topology optimization problem can be reformulated into a 0-1 ILP problem as: minimize ?2parenleftbigsummationtextmpotl=1 xl ?wl ?al ?aTl parenrightbig (4.20) subject to 1T ?x = 12summationtextni=1Ki ? parenleftbiggn c 2 parenrightbigg (4.21) di = Ki, for all i (4.22) x ? {0,1}mpot, ?l = ?ij, l ? (i,j). (4.23) The solution is the boolean vector x that maximizes the algebraic connectivity of the resulting graph under node degree and edge constraints. 4.3.3 Remarks Clustering is like a graph partitioning problem, while optimally partitioning a graph according to certain performance measure is NP-hard [79,80]. In [70], it is shown that the problem of adding a specified number of edges to an input graph to maximize the algebraic connectivity of the augmented graph is also NP-hard. In the next two sections, we develop bounds and heuristic algorithms for the formulated problems. Specifically, we develop a plane sweeping and clustering (PSC) algorithm for the WMN clustering problem and a greedy edge-appending (GEA) algorithm for the FSO topol- ogy optimization problem, along with performance bounds. Both algorithms are evaluated via simulations. 70 4.4 Lower Tier: Cluster Formation In this section, we first describe the PSC algorithm for cluster formation in the lower- tier WMN. We then develop a lower bound on the number of clusters, which can be used as a benchmark for the algorithm performance. Finally we discuss ways to reduce the computational complexity of the PSC algorithm. 4.4.1 Plane Sweeping and Clustering Algorithm There have been a few clustering heuristics in the literature [85,86], and several schemes that consider QoS constraints [20,80]. However, we find it difficult to apply or enhance the existing algorithms for our problem with both traffic demand and delay constraints. Most existing schemes select a cluster head first and then select cluster members. For example, the recursive dominating set algorithm in [80] first selects a maximum degree node and then all its neighbors become cluster members. This approach may not be suitable for the case when the mesh routers have different traffic demands. Furthermore, existing work in [20,80] consider only the Internet traffic of the mesh routers, but not the inter-cluster traffic. The PSC algorithm continually sweeps the network area to capture cluster members while satisfying the delay and load constraints, until every mesh router is assigned to a cluster. We then choose cluster head for each cluster formed. The objective is to minimize the number of clusters, thus reducing the deployment cost of the upper tier FSO network. The pseudo-code of the PSC algorithm is presented in Table 4.2. Starting from the lower left corner of the network region,3 PSC iteratively sweeps the network area and forms a new cluster after each iteration. Each iteration consists of three steps as follows. 3Since PSC is to sweep all the mesh routers, starting from a corner is a better choice than, say, starting from a gateway node. Since a gateway node could be located anywhere in the network, starting from a gateway node may complicate the sweep process. 71 Table 4.2: Plane Sweeping and Clustering (PSC) Algorithm 1: i=0; 2: Compute matrices Ai and Hi for graph Gi = G; 3: Choose the lower left corner node as base node; 4: WHILE (some nodes not clustered) 5: i++; 6: Add the base node to cluster Mi; 7: FOR h = 1 : hmax 8: WHILE (some h-hop neighbors not checked) 9: Find a node u that is h-hops from the base node; 10: IF (huk > hmax for any k ? Mi) 11: Go to 20; 12: ELSE IF (fMi > fmax) 13: Go to 20; 14: ELSE 15: Add node u to cluster Mi; 16: Update traffic load fMi; 17: END IF 18: END WHILE 19: END FOR 20: Determine cluster head for cluster Mi; 21: Generate the reduced graph Gi = Gi?1 ?Mi; 22: Generate matrices Ai and Hi for graph Gi; 23: Find the next base node; 24: END WHILE 25: IF (there is an isolated node) 26: Merge to a neighboring cluster with the max diameter; 27: Reparitition to get two new cluseters; 28: END IF 29: Compute number of FSO devices for each cluster head; 72 PSC Step 1: Cluster Formation PSC first chooses a base node as starting point for the next cluster to be formed. It then explores the neighbors of the base node within hmax hops, and adds the neighboring nodes into the cluster, until one of the conditions, DMi ? hmax or fMi ? fmax, is violated (Lines 5?19 in Table 4.2). DMi is the diameter of the new cluster Mi, which can be computed as: DMi = max u,v?Mi,unegationslash=v [Hi]uv , (4.24) where Hi is the hop-count matrix for cluster Mi. Recall that fMi = max{fo,Mi,fMi,o} is the larger one of the aggregate incoming or outgoing traffic load of cluster Mi, as given in (4.3). It is worth noting that in the optimized clustering problem (4.5)?(4.9), the delay con- straint is translated to summationtextnu=1 xuv ?huv ? hmax for all u,v ? V. That is, the hop count of the shortest path from any cluster member to its cluster head should be upper bounded by hmax. Since the cluster head could be located anywhere in the cluster (not necessarily at the center, see the discussion of PSC Step 2), this condition is satisfied by bounding cluster diameter with hmax in PSC, such that the maximum hop count for any node pair in the cluster does not exceed hmax. This also provides redundancy for accommodating fluctuations in the delay components. PSC Step 2: Cluster Head Selection When a new cluster Mi is formed, PSC will select a cluster head from the nodes in Mi (Line 20 in Table 4.2). This node will be equipped with FSO transceivers and become a node in the upper tier FSO network. Since all the incoming and outgoing traffic for a cluster will go through the cluster head, it should be judiciously chosen such that the relay traffic load within the cluster is minimized. If there is a gateway node in the cluster, it should be the cluster head, since all the traffic will finally be directed to and from there. If there are more than one gateway nodes in the 73 cluster, it will be split into multiple smaller ones, each using a gateway node as cluster head. Each non-gateway node in the cluster will be associated with the closest gateway node after the partitioning. Note that this case rarely happens since the number of gateway nodes is usually small. If there is no gateway node in the cluster Mi, we select a node as cluster head by solving the following optimization problem: argmin q?Mi ? ? ? summationdisplay u?Mi,unegationslash=q huq ? ? nsummationdisplay v/?Mi,v=1 ([F]uv + [F]vu) ? ? ? ? ?, where the overall relay load for the cluster?s incoming and outgoing traffic is minimized. PSC Step 3: Graph and Matrices Update If there is still node not clustered, PSC will obtain a reduced graph Gi by deleting the nodes in cluster Mi from graph Gi?1, and update the adjacency matrix Ai and hop-count matrix Hi for the reduced graph Gi. PSC then chooses in Gi the closest node from the current base node point, as well as close to certain trajectory (horizontal or vertical), as the next base node, and will repeat Steps 1) and 2) to generate a new cluster (Lines 21?23 in Table 4.2). PSC sweeps a network plane until all the nodes are covered. However, there could be single-node clusters (e.g., a single node in Mi) in the border zone. In this case, we refine the cluster formation by first identifying the neighboring cluster with the largest diameter (e.g., cluster Mj), and then iteratively reassigning members of Mj to Mi, until the diameter or traffic load constraints of Mi is met, or when the two clusters Mi and Mj have similar number of nodes. It is easy to see that the total number of clusters are still the same, and both refined clusters are feasible. Line 29 in Table 4.2 computes the number of FSO transceivers for each cluster head as given in (4.10). The number is determined by the traffic load fmax and the capacity of 74 FSO links. It is the degree of the cluster head, and determines the number of edges for the upper-tier FSO network. 4.4.2 Lower Bound We next derive a lower bound on the objective value achieved by PSC. To avoid trivial cases4 and without loss of generality, we assume that every point in the deployment area, S, is covered by at least one mesh router. The lower bound on the number of clusters is given in the following theorem. It will be useful for evaluating the performance of heuristic clustering algorithms, especially for large-scale networks. Theorem 4.4.1 n0 = ?4S/(?r2h2max)? ? nc is a lower bound on the total number of clusters. Proof In order to minimize the number of clusters, the size of each cluster should be maxi- mized. For given constraints hmax and fmax, there are two cases when a cluster is formed, i.e., the cluster size is confined by either (i) the maximum cluster diameter or (ii) the maximum aggregate traffic load. (Case i) Since the cluster size is confined by hmax, the minimum number of clusters can be obtained by forming each cluster with diameter hmax. With transmission range r, the maximum Euclidean distance between any two cluster members is thus rhmax. The maximum coverage of a cluster is ?r2h2max/4, which is a disk with radius rhmax/2. To cover the deployment area, the minimum number of clusters can be estimated as ?4S/(?r2h2max)?. (Case ii) Since the cluster size is confined by fmax, the maximum cluster diameter bound is not violated when the cluster is formed. As a result, the Euclidean distance of the cluster diameter cannot be larger than rhmax. Therefore, the minimum number of clusters for this case cannot be lower than that in Case i. Therefore, we can make a conclusion that the minimum number of clusters is n0 = ?4S/(?r2h2max)?. 4For example, the lower bound will be one if all the mesh routers are installed at the same location with low traffic load. 75 4.4.3 Complexity Reduction PSC involves manipulation of several matrices. It can be shown to have a complexity of O(nc ?n2.376), which mainly stems from matrix multiplications. In this section, we discuss techniques on further reducing the computational complexity. Theorem 4.4.2 Consider reduced graph G? = G?k for k ? V(G). For any u ? V(G) such that huk ? hmax, we have [H]uv = [H?]uv for all v ? V(G) and v negationslash= k. Proof For u,k ? V(G) and u negationslash= k, assume that there is an uk-walk, of which the shortest path has n walks, meaning huk = n. If huk > hmax, we have huk = 0. Then, the uk- walk is denoted by ?u = ?0e0?1e1 ????n?1en?1?n = ?k for n ? hmax. For the reduced graph G? = G?k, assume there is a vertex v negationslash= k. We consider the following three cases. (Case i) Assume that huk > hmax. If huv ? hmax, h?uv is equal to huv since the uv-walk does not include ?k by the case condition huk > hmax. If huv > hmax, h?uv is also equal to huv (i.e., both are 0), since deleting a vertex does not reduce the number of any walk. Thus we have [H]uv = [H?]uv. (Case ii) Assume that huk = hmax. If huv < hmax, h?uv is equal to huv since the uv-walk does not include ?k by the assumption huk = hmax. If huv = hmax, there should be another walk which does not go through ?k. If not, the condition, huv = hmax, will be violated. For the condition huv > hmax, h?uv is also equal to huv since both of them are 0 in this case. Thus [H]uv = [H?]uv holds true in this case. (Case iii) Assume that huk < hmax. If hvk < hmax and huv = huk + hkv, it is possible that the shortest uv-walk is unique and ?k is in the path. It is possible to have h?uv negationslash= huv. We have that [H]uv = [H?]uv when huk ? hmax. Corollary 4.4.2.1 Consider reduced graph G? = G ? k for k ? V(G). Assuming disjoint vertices u,v,k ? V(G), it is possible to have that h?uv negationslash= huv, if huv = huk+hvk for huk < hmax and hvk < hmax. 76 Proof We have huv negationslash= h?uv if huv = huk + hvk for huk < hmax and hvk < hmax. If one of the vertices u or v is more than hmax hops from k, we have h?uv = huv according to Theorem 4.4.2. We consider three cases for huk < hmax and hvk < hmax as follows: (Case i) If huv < huk + hvk, it means that the uv-walk does not go through vertex k. (Case ii) If huv = huk + hvk, it is possible that the shortest path between u and v including vertex k is unique. In that case, when k is deleted, the unique shortest path will no longer exist. We then have h?uv > huv or h?uv = 0 according to (4.4). (Case iii) The case of huv > huk + hvk cannot happen. Therefore, we have h?uv negationslash= huv when huv = huk + hvk for huk < hmax and hvk < hmax. Corollary 4.4.2.2 Consider reduced graph G? = G?k for k ? V(G). Assume that vertex u,v,k ? V(G) are disjoint. Then [H?]uv can be obtained by the power calculation of an adjacency matrix, denoted as A??, consisting of rows and columns corresponding to vertices s and t ? V(G), satisfying hks ? 2(hmax ?1) and hkt ? 2(hmax ?1). Proof Consider disjoint vertices u,v,k ? V(G), huv = huk + hvk for huk < hmax and hvk < hmax. Therefore [H?]uv could be different from [H]uv. From Corollary 4.4.2.1, vertices u and v can be located at most hmax ? 1 hops from vertex k. Let p ? V(G?), p negationslash= u, and p negationslash= v. In order to check [H?]uv, p should be located less than hmax ?1 hops from u and v. According to location conditions of u and v, and p, the adjacency matrix, A??, with vertices less than 2(hmax ?1) hops from k can be used to compute [H?]uv. As examples, consider the 500-node network shown in Fig. 4.3. In Fig. 4.3(a), a node around the center of the region is deleted (i.e., included into an existing cluster). In Fig. 4.3(b), a node near the boarder is deleted. We show in the figure the set of nodes that are required for getting the reduced adjacency matrix A??, obtained after the node deletion. Such nodes are marked as red squares and green diamonds. According to Theorem 4.4.2 77 0 100 200 300 400 500 600 700 800 900 10000 100 200 300 400 500 600 700 800 900 1000 (a) A central node deletion. 0 100 200 300 400 500 600 700 800 900 1000 (b) A border node deletion. Figure 4.3: The subgraph corresponding to A?? (marked as red squares and green diamonds) after deleting a node from a 500-node network deployed in a 1500 ? 1500 m2 area with r = 150 m and hmax = 3. and the corollaries, we need to recompute the H? entries for the red square nodes in the figures, while the green diamond nodes are also involved in the computation. Except for the red square nodes, the H? entries for all other nodes are not changed by the node deletion. Compared to recomputing the entire H? using A, significant computation reduction can be achieved by using the much smaller adjacency matrix A??. We also find that deleting an edge node achieves more computation reduction than deleting a central node, as illustrated in Fig. 4.3. 4.5 Upper Tier: Topology Optimization The objective of topology optimization is to maximize algebraic connectivity for the upper tier FSO network, while satisfying the traffic load requirements. We first derive a theoretic upper bound for the increase in algebraic connectivity when an additional edge is added. We then present the centralized greedy edge-appending (GEA) algorithm and its distributed version. 78 4.5.1 Theoretical Upper Bound The algebraic connectivity upper bound is useful for evaluating the performance of GEA, since the global optimal lies in between the GEA solution (i.e., a lower bound) and the upper bound. Let G(V,E) be a connected and weighted graph and let G? be a graph by adding an edge l ? (i,j) to G, denoted as G? = G+ l. The upper bound is given in the following. Theorem 4.5.1 An upper bound on the algebraic connectivity of graph G? is given as: ?2(G?) ? minbraceleftbig?3(G),?2(G) + ?ij ?(?i ??j)2bracerightbig, (4.25) where ?i and ?j are the ith and jth elements of the normalized eigenvector v of L(G) corre- sponding to eigenvalue ?2(G). Proof Let L and L? be the Laplacian matrix of G and G?, respectively. We first show that ?2(G?) ? ?3(G). Assuming that graph G has one component, we have L? = L+ ?l ?al ?aTl . Since the Laplacian matrix L is symmetric positive semidefinite, it satisfies the following conditions: (i) L = LT, (ii) L followsequal 0, and (iii) L ? 1 = 0, where 1 = [1,1,??? ,1]T and 0 = [0,0,??? ,0]T. Let ?1 ? ?2 ? ????nc be the eigenvalues of L and ??1 ? ??2 ? ?????nc be the eigenvalues of L?. According to Theorem 3.2 in [83], we have ?1 ? ??1 ? ?2 ? ??2 ? ?3 ? ??3 ??? ? ?nc ? ??nc. Therefore, it follows that ?2(G?) ? ?3(G). We next prove the second part. Let v = (?1,?2,??? ,?nc) be the normalized eigenvector of L corresponding to ?2(L). According to the Courant-Fischer formula, the second smallest eigenvalue of L? can be written as ?2(L?) = minx?1,xnegationslash=0 ?L??x,x??x,x? , where ??,?? is the inner product 79 Table 4.3: The Greedy Edge-Appending (GEA) Algorithm 1: Build a degree bounded minimum spanning tree; 2: WHILE (there remains an edge to be inserted) 3: Append the edge with the largest ?ij ?(?i ??j)2 among remaining edges in Epot; - Conditioned on: (di < Ki) and (dj < Kj); - Break a tie by considering the node pair with the min degree first and then that with the max distance; 4: Update graph and the corresponding Laplacian matrix; 5: END WHILE of two vectors [83]. We have ?2(L?) = min x?1,xnegationslash=0 ?L? ?x,x? ?x,x? ? ?L? ?v,v? ?v,v? = summationtext (a,b)?E(G?) ?ab ?(?a ??b) 2 summationtext a?V (G) ?2a = summationtext {(a,b)?E(G)}?{(i,j)/?E(G)} ?ab ?(?a ??b) 2 summationtext a?V (G) ?2a = summationdisplay (a,b)?E(G) ?ab ?(?a ??b)2 + ?ij ?(?i ??j)2 = ?2(L) + ?ij ?(?i ??j)2. The fourth equality is due to the fact thatv is a normalized vector. We have ?2(L?) ? ?2(L)+ ?ij(?i??j)2. Since both cases should be satisfied, we have that ?2(G?) ? min {?3(G),?2(G)+ ?ij ?(?i ??j)2}. 4.5.2 Greedy Edge-Appending Algorithm The pseudo-code of the GEA algorithm is given in Table 4.3. The procedure starts with nc vertices and a null edge set. Therefore, the initial value of ?2(L) is zero and will remain zero until the graph becomes connected (see Facts 4.3.4 and 4.3.5). To speed up the initialization phase, we first apply an enhanced version of Prim?s algorithm to build a degree 80 bounded minimum spanning tree (MST) [87]. Next, GEA iteratively picks an edge from the remaining edges in Epot and appends it to the graph such that the algebraic connectivity is progressively improved. Recall that v = (?1,?2,??? ,?nc) is the normalized eigenvector corresponding to ?2(L). During each iteration, GEA chooses an edge with the largest ?ij ?(?i ??j)2 value among all the remaining edges in Epot. As shown in the proof of Theorem 4.5.1, ?ij ? (?i ? ?j)2 is an upper bound on the increase in algebraic connectivity achieved by adding edge (i,j). This strategy will achieve the largest expected increase in ?2(L). In the case of a tie where multiple edges have the same maximum ?ij ?(?i ??j)2 value, GEA chooses the edge whose endpoint has the minimum degree. If there is a tie again, GEA chooses the edge with the largest distance. This strategy is motivated by the inequality condition (4.11), i.e., 4D?nc ? ?2(G) ? ?(G), which implies that algebraic connectivity may be improved by increasing the minimum degree and/or by decreasing the diameter of the graph. Recall that m is the total number of edges to be inserted. It takes O(n2c) to build the minimum spanning tree with nc?1 edges [87]. Since a Lapacian matrix of a connected graph is symmetric tridiagonal, it takes O(n2c) to compute its eigenvector [73]. The complexity of appending the remaining (m ? nc + 1) edges mainly comes from computing eigenvector v, each takes O(n2c), for the remaining edges in Epot. The overall GEA complexity is O(n2c + (m?nc + 1)n2cmpot). 4.5.3 Alternative and Distributed Algorithms In addition to the bottom-up approach taken in GEA, alternative methods can be explored. For example, a top-down approach that deletes an edge from current topology starting from G(V,Epot). In each iteration, the edge with the minimum ?ij ?(?i ??j)2 value will be selected and deleted, until mpot ?m edges are deleted. Note that this approach may not be suitable for large networks where mpot ? m. 81 As another intuitive edge-appending algorithm, we can select the edge with the largest weight to insert, since a more reliable edge could make stronger connection than weak link. That is, the strategy is to select the edge with maximum ?ij among unselected potential edges. This algorithm can guarantee the highest link weight sum, but the resulting alge- braic connectivity is hard to predict. We call it simple greedy heuristic, and compare its performance with the GEA algorithm in the simulations. The GEA algorithm described in Table 4.3 is executed at a centralized entity with global information. It would be interesting to develop a distributed version of GEA that does not require the centralized entity. Such a distributed version executed at FSO node i is presented in Table 4.4. First, a distributed MST algorithm is executed at each node to form a tree topology [65], as given in Lines 1?3. As in prior work [4], we assume that nodes within a connected graph component share topology information with each other. Therefore, once the tree is formed, the FSO nodes can share and obtain information of the current topology. Then, node i iteratively identifies a neighbor j, such that inserting edge (i,j) achieves the largest potential increase in algebraic connectivity among all other possible links to node i?s neighbors. Then node i will request to connect to node j, using one of the remaining FSO transceivers at each node. If it succeeds, it will increase its node degree by 1 and continue to find the next edge to insert. Note that since each node autonomously decide which edge to insert, it is possible that when node i tries to insert edge (i,j), node j has already used up all of its transceivers in the meantime. In this case, node i will give up and try to find the next edge to insert to other neighbors. This procedure, shown in Lines 4?10, is repeated at each node until all its transceivers are used. In the distributed GEA, the next edge is chosen from those edges in Epot that connect itself to its neighbors. In the centralized GEA, however, the next edge is chosen from all the remaining edges in Epot. Thus, the distributed GEA algorithm is expected to provide smaller potential increase in algebraic connectivity than achieved that by the centralized 82 Table 4.4: Distributed GEA Algorithm at FSO Node i 1: WHILE (the network is partitioned) 2: Participate in the distributed MST algorithm; 3: END WHILE 4: WHILE (node degree constraint (4.22) is not met) 5: Read current topology information; 6: Select a neighbor j = argmax{?ij ?(?i ??j)2}; 7: IF (succeed in inserting edge (i,j)) 8: Increase node degree by 1; 9: END IF 10: END WHILE GEA algorithm. As will be shown in our simulation studies, it slightly sacrifices connectivity performance to eliminate the need for a centralized entity. 4.6 Simulation Results In this section, we evaluate the performance of PSC and GEA. The algorithms are implemented in Matlab. We use fixed transmission range r for the lower tier radio network, and simulate log-normal fading for the upper tier FSO links. In each simulation, a large number of mesh routers are uniformly distributed in a square region and a small number of gateway nodes are randomly chosen from the set of mesh routers. The traffic matrix is randomly generated as follows. Each mesh router generates two types of traffic: (i) Internet traffic that is forwarded to/from a gateway, and (ii) inter-cluster traffic that is delivered between two mesh routers. The inter-cluster traffic is randomly distributed among mesh routers and the Internet traffic is directed to the closest gateway. We assume the incoming Internet traffic rate is twice that of the outgoing Internet traffic (i.e., more downloading traffic than uploading traffic). 4.6.1 Optimized Clustering Results We first evaluate the PSC performance with regard to number of clusters and computa- tion reduction. Although there is considerable literature on clustering in wireless networks, 83 Figure 4.4: A tiered network designed using PSC and GEA. we find that many existing algorithms are designed for highly specific problems and may not apply for the FSO-based wireless access network considered in this chapter. For ex- ample, energy efficiency has been the major consideration for clustering in wireless sensor networks [77,85], while power conservation is not an issue in WMNs since the mesh routers are usually plugged in to power outlets. In addition, traffic demand between clusters, as represented by the traffic matrix, is not considered in many prior work on clustering in WMNs [80]. Therefore, we compare the PSC algorithm with the lower bound in this section to avoid unfair comparisons. We follow the setting in [80] to consider a small network with 175 mesh routers uniformly deployed in a 1,000 ? 1,000 m2 region. There are two gateway nodes. The radio transmission range is r = 100 m, and the minimum distance between any two mesh routers is 60 m. The cluster diameter bound is set to hmax = 4. Applying PSC, the mesh routers are divided into 20 clusters, as illustrated in the lower tier of Fig. 4.4. The upper tier in Fig. 4.4 is constructed by GEA. In Fig. 4.5, we plot the number of clusters formed by PSC for increasing cluster diameter bound hmax, where the same setting as in Fig. 4.4 is used. For each hmax value, we randomly 84 5 10 15 200 5 10 15 20 25 30 35 40 45 Cluster Diameter (hmax) Number of Clusters PSC (simulation, 95% conf. int.) Lower bound (analysis) Figure 4.5: PSC performance: number of clusters for various hmax values. generate 25 different topologies for the mesh network. Each point on the PSC curve is the average of the 25 topologies, with 95% confidence intervals plotted as error bars. The confi- dence intervals are generally negligible, implying that the PSC performance is quite stable. As expected, the number of clusters quickly decreases for increased hmax, and converges to one when hmax = 20. We also plot the lower bound as given in Theorem 4.4.1. The lower bounding curve lies below the PSC curve and is reasonably tight for practical systems. Finally we examine the computational cost reduction as given in Theorem 4.4.2 and Corollaries 4.4.2.1 and 4.4.2.2. Let G?? ? G? be the subgraph corresponding to A??. We define the computation reduction ratio as ? = |V(G ?)|?|V(G??)| |V(G?)| ?100(%). (4.26) A larger ratio implies multiplication of smaller matrices and larger computation reduction. Fig. 4.6 shows the reduction ratios by deleting a node from a 500-node network and a 1,000- node network, respectively. It can be seen that deleting a border nodes results in smaller 85 3 4 5 60 20 40 60 80 100 Cluster Diameter hmax Reduction Ratio (%) Center node deletion, 500 nodes Boarder node deletion, 500 nodes Center node deletion, 1000 nodes Boarder node deletion, 1000 nodes Figure 4.6: Computational cost reduction achieved by using the reduced adjacency matrix A??. A?? than deleting a central node, and more significant reductions can be achieved for larger networks. 4.6.2 Topology Optimization Results When the clusters are formed, location and degree information of cluster heads are used as input to GEA algorithm for optimizing the top tier topology. We assume ?th = 0.9, I/I0 = 0.8, and ? = 1,550 nm. The link reliability ?ij and weight ?ij are determined by distance and weather condition using the FSO channel model. The distances are computed from cluster head locations. For weather condition, the index of refraction structure parameter C2n is randomly generated in [10?16,10?14] m?2/3. The typical weather condition is set to C2n = 10?15 m?2/3. Small FSO Network We first examined a small network with the same setting as that in Fig. 4.4 (but with a different random topology). With cluster diameter bound hmax = 3, the mesh routers are 86 26 28 30 32 34 36 380 0.1 0.2 0.3 0.4 0.5 0.6 0.7 Number of Edges Inserted Algebraic Connectivity Upper bound Exhaustive search GEA Distributed GEA Simple greedy Figure 4.7: Algebraic connectivity for the small network.. divided into 26 clusters. The traffic demand requires that m = 39 FSO edges should be added in the top tier, and the total degree is summationtext26i=1 Ki = 2 ? m = 78. We first execute the enhanced Prim?s algorithm to build a degree bounded minimum spanning tree, which uses 25 edges. GEA then iteratively inserts 14 edges to the tree graph. In Fig. 4.7, we plot the resulting algebraic connectivity after each edge is appended. For comparison, we also plot the upper bound as given in Theorem 4.5.1 and the global optimal values found by an exhaustive search, which is possible for this small network. We also implement the distributed GEA algorithm and the simple greedy algorithm, and plot the corresponding algebraic connectivity curves in the figure. We find that the upper bound provide a very good approximation for the global op- timum. The GEA curve overlaps with the global optimal curve for most of the iterations, except for the 26th, 33rd, 35th, and 38th edge insertions. When GEA terminates, the upper bounding algebraic connectivity is 0.6357 and the GEA value is 0.6353, which are all identi- cal to the global optimum. There is a moderate gap between the centralized GEA curve and the distributed GEA curve. The distributed GEA terminates with algebraic connectivity value 0.5698, which is 89.7% of the global optimal solution. This shows that the distributed 87 GEA slightly sacrifices the achievable algebraic connectivity in order to exclude the need for a centralized entity. Although the simple greedy algorithm always chooses the link with the best quality to insert and achieves the largest link weight sum among all the algorithms, it performs poorly with respect to algebraic connectivity. The algebraic connectivity achieved by the simple greedy algorithm is 0.2624, which is 41.3% of the global optimum. Large FSO Network We next design a large-sized network deployed in a 6,000 ? 6,000 m2 area. The PSC algorithm forms 184 clusters, and 326 edgesare to beinserted according to thetraffic demand. The unweighted node degree of each node ranges from 2 to 5. Building the spanning tree uses 183 edges, and the remaining 143 edges are iteratively appended by GEA. In Fig. 4.8, we plot the algebraic connectivity traces as edges are iteratively inserted. Due to the large network size, exhaustive search is not feasible. We plot the upper bound as given in (4.25) as indicator of the global optimal solutions. We find the GEA curve overlaps with the upper bound curve for most of the iterations. When GEA terminates, it achieves the same algebraic connectivity value 0.3527 as the upper bound. Clearly, not only the upper bound is highly tight, the greedy heuristic GEA algorithm also achieves the global optimum for this large network. Similarly to the case of small network, the distributed GEA and simple greedy algorithms also show similar trends. At the last iteration, the algebraic connectivity of distributed GEA algorithm is 0.3010, which is 85.3% of the upper bound. However, the simple heuristic algorithm achieves an algebraic connectivity value of 0.0413, which is 11.7% of the upper bound. Using the same 184-cluster FSO network, we examine the impact of several network parameters on algebraic connectivity in Fig. 4.9, including the minimum node degree and link weight. The minimum node degree is determined by the traffic matrix and is an indicator of the network traffic demand. Link weights are determined by weather conditions. In Fig. 4.9(a), we plot algebraic connectivity for increased minimum node degree. It can be 88 200 220 240 260 280 300 3200 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 Number of Edges Inserted Algebraic Connectivity Upper bound GEA Distributed GEA Simple greedy Figure 4.8: Algebraic connectivity for the large network. seen that the three algebraic connectivity curves all increase with the minimum node degree. This is because a larger minimum node degree allows more edges to be inserted. According to Fact 4.3.6, algebraic connectivity increases when more edges are inserted. However, both GEA curves increase with minimum node degree at a much fast rate than the simple greedy algorithm curve, indicating their effectiveness in building well connected graphs. In Fig. 4.9(b), we reduce link reliability by certain ratios and plot the resulting algebraic connectivities. Since link reliability largely depends on weather condition, this is equivalent to examinethealgorithmsundervariousweatherconditions. Asexpected, all thethreecurves decrease as link reliability is reduced. When link reliability is reduced by 50%, the GEA algebraic connectivity is reduced in half, i.e., from 0.3527 to 0.1764. The distributed GEA value is reduced from 0.3010 to 0.1575, and the simple greedy algorithm value is constantly low and is reduced from 0.0413 to 0.0206. Interestingly, choosing the most reliable edges as in the simple greedy algorithm, does not necessarily provide strongly connected topology with respect to algebraic connectivity. 89 2 3 4 5 6 7 80 0.5 1 1.5 2 2.5 3 3.5 4 Unweighted Minimum Degree Algebraic Connectivity GEA Distributed GEA Simple greedy (a) The impact of minimum degree 0 10 20 30 40 500 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 Reduction Ratio of Link Reliability (%) Algebraic Connectivity GEA Distributed GEA Simple greedy (b) The impact of link reliability Figure 4.9: Algebraic connectivity vs. network parameters. 90 0 500 1000 1500 2000 2500 3000 3500 4000 0 500 1000 1500 2000 2500 3000 3500 (a) Triangle lattice 0 500 1000 1500 2000 2500 3000 3500 4000 0 500 1000 1500 2000 2500 3000 3500 (b) Square lattice (c) GEA topology Figure 4.10: Lattice topologies of 20-node networks. Comparison with Regular Topologies A natural question that arises at this juncture is ?how about topologies with regular structures?? To answer this question, we consider grid network deployment, such as the triangular and square lattice networks as shown in Figs. 4.10(a) and 4.10(b). We assume that each node in the triangular lattice network can have a fixed degree from 2 to 6, which depends on its location (i.e., center or edge). Each node in the square lattice network can have a degree between 2 and 4. We also execute GEA for the same network deployment and the same number of edges. The topology designed by GEA is plotted in Fig. 4.10(c), which looks quite different from the lattice ones. How about algebraic connectivity performance? In Fig. 4.11, we plot the algebraic connectivity curves for different network sizes. For comparison, we first assume that FSO links are not weighted (or, all the links have identical reliability 1) in Fig. 4.11(a). We find that lattice networks are not well connected by the measure of algebraic connectivity. The algebraic connectivity of the 20-node triangular network is 0.5204, which is only 39.4% of the corresponding GEA value. For the 56-node square network, the algebraic connectivity is 0.1522, which is only 32.3% of the corresponding GEA value. This is due to the fact that algebraic connectivity is determined by various graph invariants, not only edge/vertex connectivity, but also graph diameter and minimum degree. In the lattice networks, nodes 91 12 20 30 40 50 560 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.5 Network Size Algebraic Connectivity Triangle lattice GEA on Tri. lat. Square lattice GEA on Squ. lat. (a) Unweighted lattice network 12 20 30 40 50 560 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 Network Size Algebraic Connectivity Triangle lattice GEA on Tri. lat. Square lattice GEA on Squ. lat. (b) Weighted lattice network Figure 4.11: Algebraic connectivity of lattice networks. 92 only connect to their neighbors, so their network diameters are usually larger than that of the GEA topology, indicating smaller algebraic connectivity according to inequality (4.11). There are several interesting observations to make. First, algebraic connectivity is a decreasing function of network size, since a larger network usually has a larger diameter. Second, it can be seen that the square lattice network is a subgraph of the triangular lattice network. According to Fact 4.3.6, the triangular lattice network always has better connec- tivity than the square lattice network. Finally, we also considered weighted lattice networks, in which each FSO can have different weight according to the channel model. The results are plotted in Fig. 4.11(b), where similar trends can be observed for the four curves. However the algebraic connectivity value in Fig. 4.11(b) is always lower than the corresponding value in Fig. 4.11(a), due to the worse link qualities. 4.7 Related Work This work is closely related to the class of network planning work [20,60,88,89]. Network planning problems usually belong to the class of combinatorial optimization problems, which are NP-hard, and metaheuristics, e.g., simulated annealing [88] or genetic algorithms [20,89] are used to provide sub-optimal solutions. The main limitations of these approaches are the lack of performance guarantees and the relatively high complexity. This work is also related to FSO research. See excellent surveys in [1,2,6] and ref- erences therein. Major FSO research has focused on the PHY so far, such as hardware architecture [2] and optical channel modeling [37]. Recently, there have been several work on the design [8,45,66,90] and (re)configuration [1,4,28] of FSO networks. As in the class of network planning work, ILPs are usually formulated and various heuristic algorithms are proposed to provide sub-optimal solutions. In [8,90], the authors study two generic fam- ily of mesh-based topologies for FSO networks: GPeterNet, a graph theoretic framework based on the well known Petersen graph, and FraNtiC, a fractal geometric architecture, for arbitrary access network deployments. In [21], Wang and Abouzeid investigate a hybrid 93 radio-frequency (RF) and FSO multi-hop network and derive an upper bound on the per node capacity. A hybrid routing scheme is proposed in which the data traffic is divided into two classes: one forwarded through the FSO nodes and the other through the multi-hop RF links. The authors show that by properly balancing the load between the two classes, the upper bound is tight. WMNs are known to suffer from capacity and fairness problems, especially when size grows [76]. A hierarchical network architecture represents a solution to the scalability prob- lem, as observed in wireless sensor networks [77,85]. In [85], Bandyopadhyay and Coyle present a hierarchical clustering algorithm for wireless sensor networks with the objective of energy effciency. In [80], the authors study the problem of optimal placement of the gateway nodes in a WMN and propose a recursive dominating set (DS) selection algorithm under delay and bandwidth constraints. Genetic algorithms is used in [20] to improve the capacity performance with minimum number of hybrid FSO/RF gateways. Algebraic connectivity is a useful tool from spectral graph theory [64,67]. It has been used in several papers as measure of connectivity [68,91]. In an interesting work [68], Ghosh and Boyd present an SDP formulation as well as a greedy perturbation heuristic for adding edges into existing graph, with the objective of maximize its algebraic connectivity. In [91], the authors propose a multi-level algorithm for finding the the best locations for a given set of relays, for enhancing the connectivity of wireless sensor networks. A standard SDP problem is formulated and solved in each level. 4.8 Summary We studied the problem of design and optimization of a tiered wireless access network. The lower tier mesh network is first partitioned into clusters, and then the topology of the upper tier FSO network is optimized. The objective is to maximize connectivity (and thus robustness) while meeting traffic demand and delay requirements. We presented a PSC algo- rithm for the clustering problem and a GEA algorithm for the topology optimization problem 94 and derived bounds on their performance. Our simulation studies show the algorithms are highly effective for the design and optimization of the tiered wireless network, as indicated by the closeness of their performance to the performance bounds. 95 Chapter 5 Joint Topology Design and Load Balancing in Free Space Optical Networks Free space optical networks have emerged as a viable technology for broadband wireless backbone networks of the next generation. In this chapter, we investigate the challenging problem of joint topology design and load balancing in FSO networks. We consider FSO link characteristics, cost constraints, traffic characteristics, traffic demand, and QoS requirements in the formulation, along with various objective functions including network-wide average load and delay. We apply the Reformulation-Linearization Technique (RLT) to obtain linear programming (LP) relaxations of the original complex problem, and then incorporate the LP relaxations into a branch-and-bound framework. The proposed algorithm can produce highly competitive solutions with performance guarantees in the form of bounded optimality gap. We develop a fast heuristic algorithm to provide highly competitive solutions. The heuristic algorithm iteratively perturbs the current topology and computes network flows for the new topology, thus progressively improving the configuration and load balancing of the FSO network. Our simulation results show that the heuristic algorithm can achieve an optimality gap close to that of a branch-and-bound algorithm developed in our prior work, with significantly reduced computation time. The heuristic algorithm is complementary to the branch-and-bound algorithm. Jointly applying the algorithms can make the FSO network dynamically reconfigurable and adaptive to events occurring at both large and small timescales. The RLT-based branch-and-bound algorithm is evaluated with extensive simulation studies and is shown to be highly suitable for jointly optimizing topology and load balancing in FSO networks. 96 5.1 Introduction Free space optics (FSO) have emerged as a promising technology for broadband wire- less networks of the next generation [2]. FSOs are wireless systems that use free space as transmission medium to transmit optical data signals at high bit rates. FSOs have many advantages such as cost effectiveness, long transmission distance, free license, interference immunity, high-bandwidth, among others. In recent years, considerable advances have been made in understanding the FSO channel, and both experimental data and commercial FSO transceivers are now available [2]. For widespread deployment of FSO networks, several important network problems should be addressed, such as how to design an FSO network topology with rich connectivity (making it robust to link failures) and how to accommodate traffic demands and QoS requirements of the underlying wired or wireless access network. The FSO network topology design problem has been addressed in several prior works. In [4], a distributed Minimum Spanning Tree (MST) algorithm was proposed to build degree- bounded tree topologies. In [25,45], algorithms were developed to maximize network con- nectivity and make a mesh topology. The load balancing problem was addressed in [28,46], where several topology design heuristics were developed to minimize network-wide average load. To maximize the potential of FSO networks, the unique characteristics of FSO links should be considered in the formulation, and the problems of topology design and routing of the traffic flows should be jointly considered and optimized [28,46]. Usually such problems are highly complex. However, an approximation algorithm with performance guarantees (i.e., in the form of a bounded optimality gap) would be highly appealing. In this chapter, we investigate the problem of joint topology design and load balancing in FSO networks, considering important design issues such as link reliability, cost constraints, traffic characteristics and demand, QoS requirements, routing policies, and network topology. We assume that a traffic matrix is known and the total number of edges used for building a topology is given a priori (due to some cost constraint). We then formulate the joint topology design and load balancing problem with objectives to minimize network-wide average load or 97 network-wide average delay. Both short-range dependent (SRD) and long-range dependent (LRD) traffic models are considered in deriving the network delays. With the objective function of average load, the formulated problem is a Mixed Integer Linear Programming (MILP) problem, while with the objective function of average delay, the formulated problem is a Mixed Integer Nonlinear Programming (MINLP) problem. These problems are NP-hard in general [28,46]. In prior works [28,46], effective heuristic algorithms were presented to minimize the network-wide average load. However, there was no guarantee on the optimality performance of these heuristics, and the algorithms do not apply to the more complex problem of minimizing network-wide average delay. Inthischapter, wedevelopaReformulation-LinearizationTechnique(RLT)-basedbranch- and-bound algorithm that can produce highly competitive solutions with bounded perfor- mance. RLT is a useful technique that can be applied to derive linear programming (LP) relaxations for an underlying non-linear non-polynomial programming problem [92]. We first adopt RLT to obtain LP relaxations for the complex MILP and MINLP problems. We then incorporate the LP relaxations into the branch-and-bound framework to compute (1-?)-optimal solutions, where 0 ? ? ? 1 is a prescribed tolerance. When the algorithm terminates, it produces a feasible solution to the original MILP or MINLP problem, which is within the ? range of the global optimum. The RLT-based branch-and-bound algorithm is evaluated with simulations, and is shown to be highly suitable for joint topology and load balancing optimization in FSO networks. Although highly appealing, the RLT-based branch-and-bound algorithm has relatively high computational complexity. In this chapter, we present a fast heuristic algorithm to the joint topology design and load balancing problem. The heuristic algorithm consists of three components: (i) initial topology design, (ii) multipath routing for load balancing, and (iii) topology perturbation. Starting from an initial topology that is designed to minimize the network-wide average load, the heuristic algorithm iteratively perturbs the current topology 98 and computes network flows for the new topology, thus progressively improving the con- figuration and load balancing of the FSO network. Our simulation results show that the heuristic algorithm can achieve an optimality gap close to that of the branch-and-bound algorithm, with significantly reduced computation time. The heuristic algorithm is complementary to the branch-and-bound algorithm. The latter is suitable for optimizing the FSO network design and operation at large timescales with guaranteed optimality. The former is suitable for dynamic reconfiguration of the FSO network in response to small timescale evens. We envision that the RLT-based branch-and- bound algorithm will be executed at relatively large time intervals when significant changes occur in the FSO network, while the heuristic algorithm will be kept running to continuously optimize the operation and configuration of the FSO network in response to small timescale events such as bad weather conditions or temporary changes in traffic demand. The remainder of this chapter is organized as follows. At first, we describe our network, channel, and performance models and assumptions, and formulate the optimization problem. Then, RLT-based algorithm is presented and its performance is evaluated. 5.2 System Model and Problem Statement 5.2.1 Network Model We consider an FSO network consisting of n base stations (BS), which provide mobile users with network access. Each BS could be the head of a cluster consisting of multiple access points [25]. The aggregate traffic will be relayed through wireless optical links. We assume that each BS has multiple sets of wireless optical devices in order to support the aggregate traffic load and provide a rich mesh connectivity. The FSO links are point-to-point connections with narrow beam divergence, and are immune to electromagnetic interference [2, 25,28,46]. The FSO network can be modeled as a simple graph G(V,E), where each vertex v ? V represents a BS and each edge e ? E is an FSO link. Let n and m denote the cardinality of 99 V and E respectively. We assume an n?n traffic matrix F that describes the traffic demand (measured, estimated, or projected) for the access network, where each element fsd = [F]sd represents the mean data rate between each source and destination pair s-d. We characterize each FSO link e = (i,j) ? E with two parameters: i) link capacity cij; and ii) link reliability ?ij. As in prior work [46], we assume that each FSO channel is full duplex with symmetric capacity and a nominal data rate c is achievable within a predefined transmission range, i.e., cij = cji = c for all i negationslash= j. We also assume symmetric link reliability, i.e., ?ij = ?ji for all i negationslash= j, due to the line-of-sight transmissions with narrow beam divergence. There is connectivity between two BS?s if the link reliability is larger than a threshold ?th. 5.2.2 FSO Channel Model We adopt the log-normal model to characterize FSO link reliability under turbulent at- mosphere [37,52]. The marginal distribution of light intensity fading induced by atmospheric turbulence can be statistically modeled as [37] fI(I) = 12? XI 1? 2? exp braceleftbigg ?[ln(I)?ln(I0)] 2 8?2X bracerightbigg , (5.1) where ?2X is the variance and I0 is the received average intensity without turbulence. The standard deviation ?2X can be approximated as ?2X = 0.30545(2?/?)7/6 C2n(L)z11/6, where ? is the wavelength, C2n(L) is the index of refraction structure parameter with constant altitude L, and z is the distance. It is shown that for atmospheric channels near the ground (i.e., L < 18.5m), C2n ranges from 10?13m?2/3 to 10?17m?2/3 for strong and weak atmospheric turbulence respectively. The common average is 10?15m?2/3. 100 The link reliability ?ij is the probability that the intensity of received signal I exceeds a threshold Ith, which can be computed using the error functin erf(?) as ?ij = P(I ? Ith) = 12 ? 12 erf parenleftbiggln(I th/I0) 2?2?X parenrightbigg . (5.2) The ratio Ith/I0 can be interpreted as transmittance according to Beer-Lambert Law [53], which is determined by the distance and absorption coefficient. For a fixed ratio Ith/I0, ?ij depends on the standard deviation ?X, which is strongly influenced by weather conditions and transmission distance. We assume that the set of edges satisfying ?ij ? ?th forms the candidate link set for constructing the FSO network topology. 5.2.3 Performance Measures Network-wide Average Load (L) We adopt multipath routing for load balancing, where a flow fsd may be split into multiple subflows. Let fsdij be the subflow passing through a link (i,j). We have the flow- conservation condition: nsummationdisplay j=1 fsdij ? nsummationdisplay j=1 fsdji = ?? ???? ??? ?? fsd, i = s, for all i ? V ?fsd, i = d, for all i ? V 0, otherwise, for all i ? V. (5.3) Considering all the s-d pairs, the average traffic load ?ij and the link utilzation ?ij are ?ij = summationtexts,d?V fsdij and ?ij = ?ij/cij < 1. (5.4) For the link to be stable, we have ?ij < 1, for all (i,j) ? E. We define the network-wide average load L as L ?= (1/?)?summationtext(i,j)?E?ij, (5.5) 101 where ? = summationtexts,d?V fsd, i.e., the sum of total traffic demands. Note that when a packet is forwarded, it is counted multiple times in L. When all the s-d traffic are transmitted through direct links, L achieves its minimum value 1. Network-wide Average Delay (T1, T2) We model each link (i,j) ? E as a general queueing system with average input rate ?ij and service capacity cij. The average delay incurred at the link depends on the traffic auto- correlation structure. When the traffic constantly exhibits short-range dependent (SRD) characteristics (e.g., VoIP traffic), we can model the link queueing delay with an exponential distribution with parametercij??ij [93]. Applying Little?s formula, thenetwork-wideaverage delay T1 can be computed as T1 ?= summationtext(i,j)?E 1? ?ijc ij ??ij . (5.6) When the traffic exhibits long-range dependent (LRD) characteristics (e.g., data traffic), we can model each link as a fractional Brownian motion (fBm) queueing system, where the queue length has a heavy-tailed Weibull distribution [94] Pr{Qij > q} ? exp braceleftbigg ?(cij ??ij) 2H 2?2(H)a?ij q 2?2H bracerightbigg , (5.7) where ?(H) = HH(1 ? H)1?H, H ? [0.5,1) is the Hurst parameter, and a is the index of dispersion. Applying Little?s formula, the network-wide average delay T2 is T2 ?= 1?? parenleftbigg 1 + 12?2H parenrightbiggsummationtext (i,j)?E bracketleftbigg(c ij ??ij)2H 2?2(H)a?ij bracketrightbigg ?12?2H . (5.8) Defining ? = 1??(1 + 12?2H)[2?2(H)a] 12?2H , we have T2 = ? ?summationtext(i,j)?E bracketleftbig?ij/(cij ??ij)2Hbracketrightbig 12?2H . (5.9) 102 5.2.4 Problem Statement Without loss of generality, we consider the case of fixed BS?s. The atmospheric condition can be known through weather forecast and past experiences. Then we can evaluate the edge reliabilities and determine the candidate edge setEc. The number of links in the FSO network is upper bounded by mc = |Ec|. The number of links is also lower bounded by n ? 1, the number of links that is needed to construct a connected network (i.e, a minimum spanning tree). The problem is to select m links from mc candidate edges to form a mesh topology. In addition, we also determine multipath routing for the s-d flows, such that either the network- wide average load L or the network-wide average delay T1 or T2 is minimized. Define the following index variables for each link (i,j) ? V as xij = ? ?? ?? 1, if (i,j) ? Ec 0, otherwise. yij = ? ?? ?? 1, if (i,j) is chosen 0, otherwise. We have xij ? yij for all (i,j) ? V. The problem of joint topology design and load balancing, denoted as Problem OPT-TDLB, can be formulated as: minimize L/T1/T2 (5.10) subject to summationtextn i=1 summationtextn j=ixij = mc, summationtextn i=1 summationtextn j=iyij = m, for i,j ? V (5.11) yij ? xij,xij = xji,yij = yji, for i,j ? V (5.12) ?li ?summationtextnj=1yij ? ?ui , for i ? V (5.13) 0 ? fsdij ? yijfsd, for i,j,s,d ? V (5.14) ?ij = summationtexts,d?V fsdij ? cij, for (i,j) ? Ec (5.15) flow conservation constraint (5.3) (5.16) xij ? {0,1},yij ? {0,1}, for i,j ? V. (5.17) 103 InProblemOPT-TDLB,theoptimizationvariablesincludebinaryvariablesy = {yij | ? i,j ? V} and continuous variables f = {fsdij | ? i,j,s,d ? V}. With objective function L, Problem OPT-TDLB(L) is an MILP problem, while with objective function T1 or T2, the correspond- ing Problems OPT-TDLB(T1) and OPT-TDLB(T2) are MINLP problems. Constraints (5.11) ? (5.13) are for edge selection and topology design, while constraints (5.14) ? (5.16) are for multipath routing and load balancing. In (5.13), ?ui is the maximum degree (enforced by some cost constraints), and ?li is the minimum degree for BS i, which is required to support the incoming and outgoing traffic from the BS, as ?li = max{?summationtextnd=1?id/c?,?summationtextns=1?si/c?}. (5.18) 5.3 RLT and Branch-and-Bound Algorithm Our solution procedure for Problem OPT-TDLB is to incorporate an LP relaxation of the original problem into a branch-and-bound framework [92]. Problem OPT-TDLB(L) is an MILP. We can obtain its LP relaxation by allowing the binary variables yij to take real values in [0, 1]. In this section, we reformulate and linearize MINLP problems OPT-TDLB(T1) and OPT-TDLB(T2). The LP relaxations will then be incorporated into a branch-and-bound algorithm that can compute (1-?)-optimal solutions. 5.3.1 Reformulation and Linearization: OPT-TDLB(T1) To linearize the objective function T1, we define substitution variables t?ij as t?ij = ?ij/(cij ? ?ij). Then we obtain a linear objective function summationtextt?ij and additional nonlinear constraints t?ij ?cij ?t?ij ??ij ??ij = 0. We next linearize the nonlinear constraint by defining substitution variables for the quadratic term ?ij = t?ij ??ij. Substituting ?ij into the additional nonlinear constraints, we make them linear, but with the following additional RLT bound-factor product constraints for the new variable ?ij. Since t?ij and ?ij are bounded by their respective lower and upper 104 bounds as 0 ? t?ij ? ?t? and 0 ? ?ij ? cij, we have ? ???? ???? ??? ???? ? (t?ij ?0)?(?ij ?0) ? 0 (t?ij ?0)?(cij ??ij) ? 0 (?t? ?t?ij)?(?ij ?0) ? 0 (?t? ?t?ij)?(cij ??ij) ? 0. (5.19) Expanding (5.19) and substituting ?ij = t?ij ??ij, we obtain the following RLT constraints: ?? ???? ??? ???? ??? ? ?ij ? 0 cij ?t?ij ??ij ? 0 ?t? ??ij ??ij ? 0 ?t? ?cij ?cij ?t?ij ??t? ??ij + ?ij ? 0. (5.20) Therefore we obtain an LP relaxation l-OPT-TDLB(T1) as minimize (1/?)?summationtext(i,j)?Et?ij (5.21) subject to constraints (5.11) ? (5.16) (5.22) 0 ? yij ? 1, for (i,j) ? Ec (5.23) cij ?t?ij ??ij ??ij = 0, for (i,j) ? Ec (5.24) RLT bound-factor constraints (5.20) for (i,j) ? Ec. (5.25) 5.3.2 Reformulation and Linearization: OPT-TDLB(T2) The objective function T2 consists of exponents. We define substitution variables for the exponents as t??ij = bracketleftbig?ij/(cij ??ij)2Hbracketrightbig1/(2?2H). Substituting t??ij we obtain a linear objective function ? summationtextt??ij, along with additional nonlinear constraints: t??ij?(cij??ij) H1?H ??ij 12?2H = 0. Letting ?ij = c ? ?ij, we have t??ij ? (?ij) H1?H ? ?ij 12?2H = 0. Finally, taking logarithms and 105 defining substituting variables ?t??ij = log(t??ij), ??ij = log(?ij), ??ij = log(?ij), (5.26) we obtain linear constraints ?t??ij ? 12?2H??ij + H1?H??ij = 0. We still need to linearize the new nonlinear constraints (5.26), which are all in the form of y = log(x). If x is bounded by 0 < xl ? x ? xu, the logarithm relationship can be linearized using a polyhedral outer approximation comprised of a convex envelop in concert with several tangential supports [92], i.e., ?? ? ?? y ? log(xu)?log(xl)xu?x l ?(x?xu) + log(xu) y ? x/xk + log(xk)?1, (5.27) where xk = xl + kkmax?1(xu ? xl) for k = 0,??? ,kmax ? 1. The convex envelope consists of a chord connecting two end points and kmax supports each being tangent to the log(x) curve at xk. Therefore, we generate (kmax + 1) new linear constraints for each logarithmic substitution variables. Therefore we obtain an LP relaxation l-OPT-TDLB(T2) as minimize ? ?summationtext(i,j)?Et??ij (5.28) subject to constraints (5.11) ? (5.16) (5.29) 0 ? yij ? 1, for (i,j) ? Ec (5.30) ?t??ij ? 12?2H??ij + H1?H??ij = 0, for (i,j) ? Ec (5.31) ?ij + ?ij = cij, for (i,j) ? Ec (5.32) polyhedral outer approximations (5.27) for ?t??ij,??ij,??ij given in (5.26), for (i,j) ? Ec. (5.33) 106 5.3.3 Branch-and-Bound Algorithm In this section, we embedded the LP relaxations into the branch-and-bound framework to obtain solutions with bounded optimality gap. Branch-and-bound is an iterative opti- mization algorithm that is especially useful for solving discrete and combinatorial problems. It consists of two key components: (i) a strategy to split a problem into subproblems with smaller sizes, i.e., branching, and (ii) a fast way to obtain lower and upper bounds (LB, UB) for the subproblems, i.e., bounding. The resulting subproblems forms a tree structure, while the set of leaf nodes is called problem list P. During the solution process, a branch of the tree may be deleted (or, fathomed) from future search, if all its solutions are dominated by some other subproblems, therefore reducing the computational cost. Our RLT-based Branch-and-Bound algorithm is given in Table 5.1. Solving the LP relaxation l-OPT-TDLB with an LP solver can provide an infeasible solution ?? = (?y,?f) and an LB for the original problem. Then we apply a local search algorithm to derive a feasible solution ? in the neighborhood of ??, which provides an UB for the original problem. The global LB and UB are updated as follows: ? ?? ?? LB = min{LBh : all problems h ? P} UB = min{UBh : all problems h ? P}. (5.34) We adopt a simple local algorithm that first determines the network topology (i.e., fixing the yij?s to binaries). According to constraint (5.11), m links should be selected from the candidate set Ec to form a topology. Hence, we choose the m largest ?yij?s in y and set them to 1; the rest smaller ?yij?s are set to 0. When the topology is fixed, we determine the optimal multipath routing by solving Problem l-OPT-TDLB again for the fsdij ?s. The resulting solution ? = (y,f) is thus feasible and provides an upper bound. For branching, we choose the subproblem h with the smallest LBh, which is indicative of the global optimal solutions. Subproblem h is then partitioned into two subproblems, h1 107 Table 5.1: Branch-and-Bound Algorithm for Problem OPT-TDLB. 1: Initialization: 2: Initialize ?? = ? and UB = ?; 3: Initialize problem list P with the original Problem 1; 4: Relaxation: 5: Obtain l-OPT-TDLB for Problem 1; 6: Solve l-OPT-TDLB to obtain solution ?? =(?y,?f) and the 7: objective value as the lower bound LB1; 8: Iteration: 9: Select problem h with the minimum LBh from P 10: Set LB=LBh and let ?? be its relaxed solution; 11: Local Search: 12: Obtain feasible solution ? from ?? with the local search alg.; 13: Compute UBh from (y, f); 14: If (UBh < UB) 15: Update ?? = ? and UB = UBh; 16: If LB ? (1??)?UB, stop with (1??)-solution ??; 17: Otherwise, discard all problems h? from P satisfying 18: LBh ? (1??)? UB; 19: Partition: 20: Find ?yij which is closest to 1 but not fixed yet; 21: Split problem h into h1 and h2 with respect to ?yij; 22: Bounding: 23: Solve the RLT relaxations of the two subproblems and obtain 24: their lower bounds LBh1 and LBh2; 25: Remove problem h from P; 26: If LBh1 < (1??)? UB, insert problem h1 into P; 27: If LBh2 < (1??)? UB, insert problem h2 into P; 28: If P = ?, stop with current best solution, ??; 29: Otherwise, enter the next iteration; 108 Table 5.2: Heuristic Algorithm for Problem OPT-TDLB. 1: Initialization: 2: Read N, F, and C2n; 3: Derive the candidate edge matrix X; 4: Derive the minimum multihop matrix H; 5: Derive the minimum traffic demand matrix F?; 6: Select edges to form adjacency matrix Y(? X): 7: Choose the largest unselected f?sd; 8: Find k multiple shortest paths for s-d; 9: Insert unselected edges into Y; 10: if {m edges have been selected} Break with Y; 11: else Goto Step 7; 12: Solve l-OPT-TDLB(L/T1/T2) for f with given topology Y; 13: Iteration: 14: Perturb the current topology: 15: Execute the branch exchange algorithm to get ?Y: 16: Delete the link with the smallest load/delay; 17: Connect the two nodes with the maximum load/delay; 18: if {no further branch exchange} Terminate with (Y,f); 19: Multipath routing for load balancing: 20: Solve l-OPT-TDLB(L/T1/T2) for ?f with given topology ?Y; 21: if {(?Y,?f) ? (Y,f)} (Y,f) = (?Y,?f); 22: if {maximum number of iterations has not been reached} 23: Go to Step 14; 24: else Terminate with (Y,f); and h2, which replace the subproblem h in P. The corresponding LBh1, LBh2, UBh1, and UBh2 are calculated, and the global LB and UB are updated as in (5.34). The iteration procedure terminates when there is a feasible solution satisfying LB ? (1??)?UB, or when the problem list P is empty. 109 5.4 Fast Heuristic Algorithm 5.4.1 Overview In this section, we present a fast heuristic algorithm for Problem OPT-TDLB. In Sec- tion 5.3, we observe that joint optimization with binary variables yij?s and continuous vari- ables fsdij ?s requires long execution time. To speed up computation, we first determine the network topology to minimize average network load, and then solve the multipath routing problem for load balancing. To further improve the optimality, we iteratively perturb the topology and then compute new network flows f, until some termination criterion is met. The pseudo-code of the algorithm is given in Table 5.2. It consists of three parts: (i) initial topology design, (ii) multipath routing for load balancing, and (iii) topology pertur- bation. The algorithm iteratively perturbs the current topology by deleting and inserting FSO links, and computes the network flow for the s-d pairs based on the new topology. The network flow is derived by solving the LP relaxations l-OPT-TDLB(L/T1/T2) with fixed yij values, thus the computation is very fast. If the new topology and network flow produce a better objective value for the original problem, the new solution will replace the existing one. Thus the objective function will be progressively improved over iterations. The algo- rithm terminates when no further perturbation can be made or when a prescribed maximum number of iterations is reached. The three key components of the algorithm are described in detail in the remainder of this section. 5.4.2 Initial Topology Design As discussed, the proposed algorithm iteratively improves the topology and network flow starting from an initial topology. A properly designed initial topology could speed up the convergence and achieve better solutions. In the following, we show how to choose m links from the candidate set Ec to form an initial topology. The initial topology is represented by 110 an adjacency matrix Y = [yij], a 0-1 n?n matrix, where yij = 1 if and only if link (i,j) ? Ec is included in the topology. Prerequisite Information Assume the traffic matrix F is known. Let N denote node information, such as node ID and location, and C2n represent FSO channel information. Then we can derive the reliability of the FSO links as in (5.2), and the set of candidate linksEc. The candidate links then form a topology with adjacency matrix X = [xij]. If link (i,j) ? Ec (i.e., ?ij ? ?th), we have xij = 1; otherwise xij = 0. The total number of candidate links is mc = |Ec| = summationtextni=1summationtextnj=1 xij/2. The minimum degree of each node can be derived as in (5.18) using traffic matrix F and link capacity c. Minimum Traffic Matrix F? For a given topology, the traffic matrix F is usually supported with both single-hop and multihop flows. If nodes s and d are not one-hop neighbors, the flow fsd will be forwarded multiple times through multihop paths. The network traffic load associated with fsd is thus proportional to the hop-counts of the s-d paths. We aim to have small hop-counts for s-d pairs with high traffic demands when determining the initial topology. We consider both single-hop and multihop traffic patterns by constructing a minimum traffic matrix, denoted as F?. Assume K disjoint paths {Pksd}k=1,???,K between nodes s and d. The s-d traffic subflow on path Pksd is denoted as fksd, and the length (or, hop-count) of Pksd is denoted as lksd, for 1 ? i ? K. We have fsd = summationtextKk=1 fksd. For the total traffic load associated with flow fsd, denoted as ??sd, we have ??sd = summationtextKk=1lksd ?fksd ? minbraceleftbiglksd | k = 1,2,??? ,Kbracerightbig?fsd ?= f?sd. (5.35) 111 We next introduce a technique to compute minkbraceleftbiglksdbracerightbig, which is based on the adjacency matrix X defined earlier. We have the following from graph theory. Fact 5.4.1 Let A be the adjacency matrix of graph G. The number of walks from vertex s to d in G with length l is bracketleftbigAlbracketrightbigsd [81]. From 5.4.1, the hop-count of the shortest path between nodes s and d can be found by identifying the smallest l, such that bracketleftbigAlbracketrightbigsd > 0. That is, min k braceleftbiglk sd bracerightbig = l, if bracketleftbigAlbracketrightbig sd > 0 andbracketleftbigAhbracketrightbigsd = 0, for all 1 ? h < l. (5.36) Once the hop-counts of the shortest paths are obtained, we can derive the minimum traffic matrix F?, with elements f?sd = minkbraceleftbiglksdbracerightbig?fsd. Link Selection When the minimum traffic matrix is obtained, we next construct the initial topology based on F? and the adjacency matrix X representing all the candidate links. To minimize the network-wide average load L, we choose the links that are on the shortest paths for all s-d pairs. We examine the elements of F? in nonincreasing order, starting from the largest one, and choose links from Ec (or, X) to insert into Y until m edges are selected. If two nodes are adjacent according to X, the direct link will be inserted. In the case of multihop flows, multiple paths will be selected for rich connectivity and load balancing. 5.4.3 Multipath Routing for Load Balancing When the topology Y is fixed, the binary optimization variables y are all determined. The LP relaxations l-OPT-TDLB(L/T1/T2) now only have continuous subflow variables f. 112 We then solve Problem l-OPT-TDLB(L/T1/T2) again with all the yij?s determined, to obtain multipath routing of the s-d flows f for this given topology. To obtain the LP relaxations l-OPT-TDLB(L/T1/T2), the following two types of con- straints are relaxed: (i) the binary variables yij are allowed to take real values in [0, 1], and (ii) the nonlinear objective functions T1 and T2 are linearized with additional RLT bound factor constraints and polyhedral out approximation constraints [92]. Except for these two, all the other constraints (5.11) ? (5.16) are preserved during the procedure. When yij?s are fixed, the f solved from the LP relaxations are also feasible to the original problem OPT- TDLB(L/T1/T2). That is, the solution {y,f} is feasible to both the LP relaxations and the original problem. Plugging it into the the objective function of OPT-TDLB(L/T1/T2) yields an upper bound. Clearly the optimality of the feasible solution {y,f} depends on the topology. It is possible to obtain a better solution with a different topology. Thus, we next perturb the current topology Y to get a new topology ?Y to further improve the current solution {y,f}, as discussed in the next subsection. 5.4.4 Topology Perturbation We adopt a branch exchange algorithm similar to that in [95] for topology perturbation. This algorithm deletes a link from the current topology Y. It then chooses a remaining link from the candidate set Ec and inserts it into the reduced topology. When deleting and inserting links, the degree constraints (5.11) and (5.13) should be satisfied. The performance of this algorithm depends on the decision rules for link deletion and insertion. We adopt the following strategies in our algorithm. ? Link deletion: for objective function L, we delete the link with the minimum load ?ij. For objective functions T1 and T2, we delete the link with the minimum delay. That is, delete the least used link from the current topology. 113 ? Link insertion: for objective function L, let the sum load at node i be ?i = summationtextnj=1 yij ? ?ij. We insert the link (i,j) with argmax{xij ?(?i + ?j) | i negationslash= j,i,j ? V,yij = 0}. For objective functions T1 and T2, let the sum delay at node i be ti = summationtextnj=1 yij?tij. We insert the link (i,j) with argmax{xij ?(ti + tj) | i negationslash= j,i,j ? V,yij = 0}. If no improvement is achieved by inserting such a link (i,j), the link that achieves the second largest value will be inserted in the next iteration, and so forth. The algorithm iteratively perturbs the topology and computes the network flows with the new topology. It terminates with solution{y,f}when the maximum number of iterations is achieved or when no further perturbation can be made. 5.4.5 Remarks The heuristic algorithm can be executed independently to solve Problem OPT-TDLB for an underlying FSO network, as discussed above. In addition, it is worth noting that it is also complementary to the RLT-based branch-and-bound algorithm developed in Section 5.3. In practice, the branch-and-bound algorithm can be executed at relatively large time intervals (e.g., when significant changes occur), to provide new topology y and network flows f with guaranteed optimality. On the other hand, the heuristic algorithm can be kept on running or executed at more frequent intervals. It keeps on perturbing the topology generated by the branch-and-bound algorithm and computing new network flows, thus making the FSO network dynamically reconfigurable and adaptive to small timescale changes such as bad weather or fluctuation in the traffic matrix F. 5.5 Simulation Studies 5.5.1 Simulation Setting In the simulations, n BS?s are randomly deployed in a rectangular region. We present simulation results for the cases n = 5 and n = 7. Assume the traffic matrix F is given, which 114 is randomly generated for the s-d pairs [46]. Each s-d flow fsd ranges from 0 to 40% of the FSO link capacity. The constraints of minimum node degrees are determined from F as in (5.18). Link connectivity is determined by the link reliability, which is derived using the FSO channel model. Then the xij are known and the the candidate link set Ec is found. We use reliability threshold ?th = 99.99% when determining the candidate set. For LRD traffic model, the index of dispersion a is set to a half of the link capacity and Hurst parameter H is chosen to be 0.7. The proposed solution procedure is implemented in Matlab ver 7.4.0 for manipulating matrices and solving the LP relaxations. The codes are executed on a standard PC with a Core Duo 2.20 GHz processor and 2 GB memory. 5.5.2 RLT and Branch-and-Bound Algorithm Convergence and Optimality Gap The branch-and-bound algorithm can provide (1 ? ?)-optimal solution. That is, the feasible solution it produces is within the ? range of the global optimal solution. We first examine the convergence and the final optimality gap achieved by the proposed algorithm. In Fig. 5.1, we plot the simulation results for the 5-node FSO network. We use the branch-and-bound algorithm to solve the three variations of Problem OPT-TDLB, i.e., Problem OPT-TDLB(L) with SRD traffic, Problem OPT-TDLB(T1), and Problem OPT- TDLB(T2). The termination criteria are chosen to be ? = 0.01, 0.01, 0.07 for the three problems, respectively. The simulations terminate when LB ? (1 ? ?) ? UB, and the up- per bounding solution is a feasible one. The Problem OPT-TDLB(L) results are shown in Fig. 5.1(a), where the proposed algorithm terminates after 3 iterations and achieves an opti- mality gap of 0.78%. The Problem OPT-TDLB(T1) results are shown in Fig. 5.1(b), where the algorithm terminates after 4 iterations and achieves a 0.62% optimal gap. In the case of 115 1 2 3 1.28 1.3 1.32 1.34 1.36 1.38 1.4 Number of Iterations Average Traffic Load Lower Bound Upper Bound Average Traffic Load (a) OPT-TDLB(L) with SRD traffic, gap = 0.78% 1 2 3 4 0.0128 0.013 0.0132 0.0134 0.0136 0.0138 Number of Iterations Lower Bound Upper Bound Average Network Delay (s) (b) OPT-TDLB(T1), gap = 0.62% 1 2 3 4 5 6 7 0.021 0.022 0.023 0.024 0.025 Number of Iterations Average Network Delay (s) Lower Bound Upper Bound Average Network Delay (s) (c) OPT-TDLB(T2), gap = 3.33% Figure 5.1: Convergence of the branch-and-bound algorithm for the 5-node network with optimality gap ? = 0.01,0.01, and 0.07, respectively. 116 1 2 3 4 5 6 7 8 9 10 11 12 1.29 1.3 1.31 1.32 1.33 1.34 1.35 Number of Iterations Average Traffic Load Lower Bound Upper Bound Average Traffic Load (a) OPT-TDLB(L) with SRD traffic, gap = 0.33% 1 2 3 4 5 6 7 0.0129 0.013 0.0131 0.0132 0.0133 0.0134 0.0135 Number of Iterations Average Network Delay (s) Lower Bound Upper Bound Average Network Delay (s) (b) OPT-TDLB(T1), gap = 0.58% 1 2 3 4 5 6 7 0.018 0.019 0.02 0.021 0.022 Number of Iterations Average Network Delay (s) Lower Bound Upper Bound Average Network Delay (s) (c) OPT-TDLB(T2), gap = 4.91% Figure 5.2: Convergence of the branch-and-bound algorithm for the 7-node network with optimality gap ? = 0.01,0.01, and 0.07, respectively. 117 Problem OPT-TDLB(T2), the algorithm terminates after 7 iterations (due to the high vari- ation in LRD traffic and the need to handle logarithm functions) with a 3.33% optimality gap, as shown in Fig. 5.1(c). In Fig 5.2, we show convergence and optimality gap results for the 7-node FSO network. The proposed algorithm takes slightly more iterations to finish, due to increased network size. For Problem OPT-TDLB(L), the algorithm takes 12 iterations to achieve an optimal gap of 0.33% (see Fig. 5.2(a)). For Problem OPT-TDLB(T1), the algorithm takes 7 iterations to achieve an optimality gap of 0.58%, as shown in Fig. 5.2(b). For Problem OPT-TDLB(T1), the algorithm takes 7 iterations to achieve an optimality gap of 4.91%. Computational Cost We next present the computation cost results in the form of execution time of the proposed algorithm, which largely depends on the efficiency of the underlying LP solver on handling large matrices. Since the algorithm is an iterative one, we focus on the execution time per iteration for clarity. In Table 5.3, the average parameter building time (i.e., the time spent on obtaining the LP relaxations and assembling the input matrices to the LP solver) and the average execution time (i.e., the time it takes for the LP solver to solve the relaxed problem) for solving one sub-problem in the Problem List P are listed. In the table, Q and Qeq are matrix inputs to the LP solver, whose sizes largely depend on the number of constraints of the LP relaxation l-OPT-TDLB. We find that the building and execution times are proportional to the parameter matrix sizes. To compute the LB for a subproblem, the corresponding LP relaxation, l-OPT-TDLB, should be solved to determine the topology design variables y and the multipath routing variables f. The constraints for fsdij ?s have more impact on the matrix sizes, due to new linear constraints introduced during the reformulation and linearization procedure for the objective functions. Once the lower-bounding solution ?? is found, it takes negligible time for 118 Table 5.3: Average Building and Execution Time per Subproblem for the Branch-and-bound Algorithm Problem Type Size of Q Size of Qeq Average Building Time (s) Average Execution Time (s) OPT-TDLB(L), LB, 5 nodes 425 ? 440 131 ? 440 0.835 0.710 OPT-TDLB(L), UB, 5 nodes n/a 112 ? 252 0.018 0.036 l-OPT-TDLB(T1), LB, 5 nodes 445 ? 480 151 ? 480 1.075 0.219 l-OPT-TDLB(T1), UB, 5 nodes 12 ? 276 124 ? 276 0.024 0.042 l-OPT-TDLB(T2), LB, 5 nodes 733 ? 540 159 ? 540 4.518 0.242 l-OPT-TDLB(T2), UB, 5 nodes 216 ? 312 136 ? 312 0.140 0.091 l-OPT-TDLB(T1), LB, 7 nodes 1,813 ? 1,848 358 ? 1,848 85.067 7.995 l-OPT-TDLB(T1), UB, 7 nodes n/a 318 ? 1,032 1.296 0.081 l-OPT-TDLB(T1), LB, 7 nodes 1,855 ? 1,932 400 ? 1,932 93.516 8.963 l-OPT-TDLB(T1), -UB, 7 nodes 24 ? 1,080 342 ? 1,080 1.613 0.089 l-OPT-TDLB(T2), LB, 7 nodes 2,543 ? 2,058 436 ? 2,058 184.305 14.110 l-OPT-TDLB(T2), UB, 7 nodes 432 ? 1,152 366 ? 1,152 4.823 0.281 11 9 the local search algorithm to find an upper-bounding solution ?? in the neighborhood, since the topology is already given in ??. For example, the average execution time is approximately 14 s to get the LB for a subproblem of l-OPT-TDLB(T2), while it only takes 0.3 s to obtain the UB for the subproblem. From these simulation studies, we find that the branch-and-bound algorithm can pro- duce feasible solutions that are highly competitive, as indicated by the very small optimality gaps when the algorithm terminates. Although the global optimum is unknown, the guar- antee on the optimality gap ensures that the solutions are near-optimal. The threshold ? provides a convenient handle for the trade-off between computation time and optimality of the solution. These are useful features for the design and control of FSO networks. 5.5.3 Fast Heuristic Algorithm In this section, we present simulation studies on the performance of the proposed heuris- tic algorithm. We first examine the optimality performance of the proposed heuristic algo- rithm. Since the parameters (such as traffic matrix and node location) are not provided in prior works [28,46], it is non-trivial to truthfully reproduce their results. Our strategy is to compare the heuristic algorithm with the branch-and-bound algorithm developed in Section 5.3. Specifically, the lower and upper bounds provided by the branch-and-bound algorithm are good indicators of the global optimal for the joint topology design and load balancing problem. The gap between the heuristic solution and the branch-and-bound al- gorithm solution provides an upper bound on the optimality gap achieved by the heuristic algorithm. In Fig. 5.3, we plot the network-wide average traffic load L and average delays T1/T2 for the 7-node network. In the figures, the markers correspond to the iterations for the algorithms. When the objective function is L, the branch-and-bound algorithm terminates after 12 iterations, achieving an optimality gap of 0.33% (i.e., the feasible solution it produces is within 0.33% range of the global optimal). The heuristic algorithm also terminates after 120 BnB Upper Bound BnB Lower Bound 0 500 1000 1500 2000 1.29 1.30 1.31 1.32 1.33 1.34 1.35 Execution Time (s) Avergage Traffic Load 0 2 4 6 8 10 12 14 16 Heuristic (a) OPT-TDLB(L) with SRD traffic, gap = 1.11% BnB Upper Bound BnB Lower Bound 0 200 400 600 800 1000 1200 0.0129 0.0130 0.0131 0.0132 0.0133 0.0134 0.0135 Execution Time (s) Avergage Network Delay 0 5 10 15 20 Heuristic (b) OPT-TDLB(T1), gap = 1.12% BnB Upper Bound BnB Lower Bound 0 500 1000 1500 2000 2500 0.018 0.019 0.020 0.021 0.022 Execution Time (s) Avergage Network Delay 0 10 20 30 40 50 60 70 80 Heuristic (c) OPT-TDLB(T2), gap = 4.33% Figure 5.3: Performance of the heuristic algorithm for the 7-node network, comparing to the results of the branch-and-bound algorithm. 121 0 10 20 30 40 50 60 701 1.1 1.2 1.3 1.4 1.5 1.6 1.7 Number of Iterations Average Traffic Load Heuristic Lower Bound (a) OPT-TDLB(L) with SRD traffic, gap = 9.16% 0 10 20 30 40 50 60 700.01 0.011 0.012 0.013 0.014 0.015 0.016 Number of Iterations Average Network Delay (s) Heuristic Lower Bound (b) OPT-TDLB(T1), gap = 9.15% 0 10 20 30 40 500.03 0.031 0.032 0.033 0.034 0.035 0.036 0.037 0.038 0.039 0.04 Number of Iterations Average Network Delay (s) Heuristic Lower Bound (c) OPT-TDLB(T2), gap = 8.16% Figure 5.4: Performance of the heuristic algorithm for the 15-node network. 122 12 iterations, achieving an optimality gap of 1.11%. When the objective function is T1, the branch-and-bound algorithm achieves optimality gap 0.58% in 7 iterations, while the heuristic achieves optimality gap 1.12% in 12 iterations. When the objective function is T2, the branch-and-bound algorithm achieves optimality gap 4.91% in 7 iterations, while the heuristic achieves optimality gap 4.33% in 16 iterations. The optimality of the heuristic solutions is shown in Fig. 5.4 for the 15-node network. We also plot the lower bound for comparison purpose. It takes 76, 75, and 55 iterations, respectively, for the heuristic algorithm to achieve optimality gaps of 9.16%, 9.15%, and 8.16%, for problems OPT-TDLB(L), OPT-TDLB(T1), and OPT-TDLB(T2), respectively. We next examine the computation time of the proposed algorithm. In Fig. 5.3, the x-axis on the top marks the execution time of the iterations of the heuristic algorithm, while the x-axis at the bottom are for the execution time of the iterations of the branch-and-bound algorithm. It can be seen that the heuristic algorithm is computationally efficient compared to the branch-and-bound algorithm. For example, in Fig. 5.3(a), the heuristic algorithm achieves an optimality gap of 1.11% in about 16 s, while the branch-and-bound algorithm achieves an optimal gap of 0.33% in about 2,100 s. The same observation is made in all our simulation studies. Finally we present the execution time of each iteration for the heuristic algorithm in Table 5.4, where matrices Q and Qeq are inputs to the LP solver. The average parameter building time is used to obtain the LP relaxations, perturb the topology, and assemble the input matrices to the LP solver. The average execution time is for the LP solver to solve the relaxed problem for optimal flows f. It can be seen that the building time is in the range of a few seconds and the execution time is in the range from tens to a few hundreds of ms. The largest building time 27.538 s occurs for the 15-node network with LRD traffic, due to the extra constraints introduced by the polyhedral outer approximation. 123 Table 5.4: Average Building and Execution Times per Iteration with the Heuristic Algorithm. Problem Type Size of Q Size of Qeq Average Building Time (s) Average Execution Time (s) l-OPT-TDLB(L), 7 nodes n/a 318 ? 1,032 1.296 0.081 l-OPT-TDLB(T1), 7 nodes 24 ? 1,080 342 ? 1,080 1.613 0.089 l-OPT-TDLB(T2), 7 nodes 432 ? 1,152 366 ? 1,152 4.823 0.281 l-OPT-TDLB(L), 15 nodes n/a 500 ? 1,550 5.350 0.131 l-OPT-TDLB(T1), 15 nodes 50 ? 1,650 550 ? 1,650 6.452 0.175 l-OPT-TDLB(T2), 15 nodes 900 ? 1,800 600 ? 1,800 27.538 0.476 12 4 5.6 Related Work This chapter is closely related to the class of network planning work [20,60,88,89]. Network planning problems usually belong to the class of combinatorial optimization prob- lems, which are NP-hard, and metaheuristics, e.g., simulated annealing [88] or genetic al- gorithms [20,89] are used to provide sub-optimal solutions. The main limitations of these approaches are the lack of performance guarantees and relatively high complexity. This work is also related to FSO research. See excellent surveys in [1,2,6] and references therein. Major FSO research has focused on the PHY so far, such as hardware architecture [2] and optical channel modeling [37]. Recently, there have been several work on the design [8, 45,66,90] and (re)configuration [1,4,28] of FSO networks. As in the class of network planning work, ILPs are usually formulated and various heuristic algorithms are proposed to provide sub-optimal solutions. In a recent work [21], Wang and Abouzeid investigate a hybrid radio- frequency (RF) and FSO multi-hop network and derive an upper bound on the per node capacity. The authors also design a hybrid routing scheme in which the data traffic is divided into two classes: one forwarded through the FSO nodes and the other through the multi-hop RF links. The authors show that by properly balancing the load between the two classes, the upper bound is tight. WMNs are known to suffer from capacity and fairness problems, especially when size grows [74]. A hierarchical network architecture represents a solution to the scalability prob- lem, as observed in wireless sensor networks [77,85]. In [85], Bandyopadhyay and Coyle present a hierarchical clustering algorithm for wireless sensor networks with the objective of energy effciency. In [80], the authors study the problem of optimal placement of the gateway nodes in a WMN and propose a recursive dominating set (DS) selection algorithm under delay and bandwidth constraints. Genetic algorithms is used in [20] to improve the capacity performance with minimum number of hybrid FSO/RF gateways. Algebraic connectivity is a useful tool from spectral graph theory [64,67]. It has been used in several papers as measure of connectivity [68,91]. In an interesting work [68], Ghosh 125 and Boyd present an SDP formulation as well as a greedy perturbation heuristic for adding edges into existing graph, with the objective of maximize its algebraic connectivity. In [91], the authors propose a multi-level algorithm for finding the the best locations for a given set of relays, for enhancing the connectivity of wireless sensor networks. A standard SDP problem is formulated and solved in each level. 5.7 Summary In this chapter, we studied problem of joint topology design and load balancing in FSO networks. For a given traffic matrix, the objective is to design the topology and multipath routing policies for end-to-end flows, such that network-wide average load or network-wide average delay can be minimized. We developed effective branch-and-bound algorithm based on RLT for the formulated MILP and MINLP problems, which can provide highly competitive solutions with guaranteed performance. The efficacy of the proposed algorithm is demonstrated with our simulation studies. 126 Chapter 6 Summary and Future Work 6.1 Summary In the previous chapters, we surveyed free space optical networks as next generation broadband wireless networks and enumerated design factors and research challenges. We formulated problems in earlier chapters, and proposed efficient design and optimization tech- niques for FSO networks. We noted that most FSO network design and optimization prob- lems are very complex. The main concern in FSO networking problems related to wireless optical properties, as explained in chapter 2. In chapter 3 and 4, we used the notion of the algebraic connectivity from spectral graph theory, as a good measure of network robustness. FSO networks are modeled as a simple weighted graph. Our method is to insert an edge iteratively until the desired number of edges are connected. Simulation results show that the sum of connected edge weights can not guarantee robustness. Hence, an FSM algorithm for a tree and GEA algorithm for a mesh are proposed. The FSM algorithm is executed in a distributed and asynchronous fashion as we assume initially that the deployed FSO base stations do not have global information. In chapter 4, we address poor scalability problem in wireless mesh networks. Since hier- archical network architectures have provided an effective solution to the scalability problem, the lower tier mesh network is first partitioned into clusters and the topology of the upper tier FSO network is formed by FSO links. The PSC algorithm is proposed to minimize the number of clusters under delay and traffic load requirements, and the GEA algorithm maximizes the algebraic connectivity using a given number of total edges. By simulation studies, we present that the algorithms are effective for the design and optimization of the 127 tiered access network, as indicated by the closeness of their performance to the performance bounds. Chapter 5 is motivated by the fact that FSO topology can be dynamically reconfig- urable by PAT mechanism. Hence, FSO topology can be optimized for load balancing. This joint optimization problem of topology design and load balancing is a very complex problem, comparable to mixed integer linear programming (MILP) or mixed integer nonlinear pro- gramming (MINLP) problem. However, this problem can be simplified by binary relaxation and RLT methods. We proposed branch and bound procedure for performance guarantee and fast heuristic algorithm for significantly reduced computation time. The efficacy of the proposed algorithms is demonstrated with simulation studies. 6.2 Future Work We have addressed several challenging problems suggested in chapter 2. However, there are still interesting research issues that are worth investigating as future work. Here are several examples that we have not investigated as follows: First, distributed topology control. For the maintenance of wide range of FSO networks, distributed topology control is necessary. Local atmospheric condition can be temporarily severe. Then, thedistributed control for various topologies can bemore flexible. We proposed a distributed FSM algorithm for tree topology in chapter 3, but more extensive simulations and different topologies still need to be considered. Second, WDM (Wavelength Division Multiplexing) FSO network. According to [59], WDM system in FSO communication can be applicable, meaning that multiple wavelengths of optical beams are used in a single channel to carry different signals. Note that the channel performance depends not only on the surrounding weather conditions, but also on its wave length. We assume that an FSO channel has single wavelength. So, wavelength routed optical network problem can be considerable [60] to minimize the number of wavelength changes in multihop delivery or to maximize network performance. Since FSO topology is 128 not fixed, logical wavelength topology can also be optimized by changing current network physically. Third, topology transformation. An adaptive FSO system is based on the advanced techniques in pointing, acquisition, and tracking (PAT) schemes, as explained in chapter 2. Topology reconfiguration can mitigate the impact of local atmospheric fluctuation and im- prove network performance. However, there will be a considerable number of packet loss during the reconfiguration process. So, efficient topology transformation technique is neces- sary for configuring the current topology into a new network topology under minimized data loss. Besides the above examples, there could be other issues because of wide range of appli- cations of FSO networks. Furthermore, FSO technology is still in its infancy. It is possible that many new challenges will be encountered. 129 Bibliography [1] C. C. Davis, I. I. Smolyaninov, and S. D. Milner, ?Flexible optical wireless links and networks,? IEEE Communications Magazine, vol. 41, no. 3, pp. 51?57, Mar. 2003. [2] V. W. Chan, ?Free-space optical communications,? IEEE/OSA Journal of Lightwave Technology, vol. 24, no. 12, pp. 4750?4762, Dec. 2006. [3] J. Li and M. Uysal, ?Achievable information rate for outdoor free space optical commu- nication with intensity modulation and direct detection,? in Proc. IEEE Global Telecom- munications Conference (GLOBECOM) 2003, San Francisco, CA, Dec. 2003, pp. 2654? 2658. [4] F. Liu, U. Vishkin, and S. Milner, ?Bootstrapping free-space optical networks,? IEEE J. Sel. Areas Commun., vol. 24, no. 12, pp. 13?22, Dec. 2006. [5] A. Mahdy and J. S. Deogun, ?Wireless optical communications: a survey,? in Proc. IEEE Wireless Communications and Networking Conference (WCNC)?04, Atlanta, GA, Mar. 2004, pp. 2399?2404. [6] D. J. Heatley, D. R. Wisely, I. Neild, and P. Cochrane, ?Optical wireless: the story so far,? IEEE Communications Magazine, vol. 36, no. 12, pp. 72?74, 79?82, Dec. 1998. [7] J. C. Juarez, A. Dwivedi, A. R. M. Jr., S. D. Jones, V. Weerackody, and R. A. Nichols, ?Free-space optical communications for next-generation military networks,? IEEE Com- munications Magazine, vol. 44, no. 11, pp. 46?51, Nov. 2006. [8] S. Ghosh, K. Basu, and S. Das, ?MeshUp: Self-organizing mesh-based topologies for next generation radio access networks,? Ad Hoc Networks Journal, vol. 5, no. 6, pp. 652?679, Aug. 2007. [9] G. Diviney, ?An introduction to short-range wireless data communications,? in Proc. Embedded Systems Conference, San Francisco, Apr. 2003. [10] S. Vangala and H. Pishro-Nik, ?Optimal hybrid rf-wireless optical communication for maximum efficiency and reliability,? in Proc. 41st Annual Conference on Information Sciences and Systems (CISS) 2007, Baltimore, MD, Mar. 2007, pp. 684?689. [11] K.-D. Langer and J. Grubor, ?Recent developments in optical wireless communications using infrared and visible light,? in Proc. 9th International Conference on Transparent Optical Networks (ICTON) 2007, Rome, Italy, July 2007, pp. 146?151. 130 [12] V. W. Chan, ?Optical satellite networks,? IEEE/OSA Journal of Lightwave Technology, vol. 21, no. 11, pp. 2811?2827, Nov. 2003. [13] ??, ?Some research directions for future integrated satellite and terrestrial networks,? in Proc. IEEE Military Communications Conference (MILCOM)?07, Orlando, FL, Oct. 2007, pp. 1?7. [14] N. Karafolas and S. Baroni, ?Optical satellite networks,? IEEE/OSA Journal of Light- wave Technology, vol. 18, no. 12, pp. 1792?1806, Dec. 2000. [15] V. Weerackody., A. H. Jr., and D. Tebben, ?Multi-input multi-output free space optical satellite communication links,? Mar. 2007, pp. 679?683. [16] L. L. Dai and V. W. Chan, ?Capacity dimensioning and routing for hybrid satellite and terrestrial systems,? IEEE Journal on Selected Areas in Communications, vol. 22, no. 2, pp. 287?299, Feb. 2004. [17] D. Voce, D. S. Gokhale, R. David, and P. Bose, ?Considerations for a tsat quality of service architecture,? in Proc. Military Communications Conference (MILCOM) 2004, Monterey, CA, Oct./Nov. 2004, pp. 85?92. [18] M. Gangl, D. Fisher, J. Zimmermann, and L. Durham, ?Airborne laser communication terminal for intelligence, surveillance and reconnaissance,? in Proc. SPIE Free-Space Laser Communications IV, Denver, CO, Aug. 2004, pp. 92?103. [19] V. Rajakumar, M. N. Smadi, S. C. Ghosh, T. D. Todd, and S. Hranilovic, ?Interference management in wlan mesh networks using free-space optical links,? IEEE/OSA Journal of Lightwave Technology, vol. 26, no. 13, pp. 1735?1743, July 2008. [20] M. N. Smadi, S. C. Ghosh, A. A. Farid, T. D. Todd, and S. Hranilovic, ?Free-space optical gateway placement in hybrid wireless mesh networks,? IEEE/OSA Journal of Lightwave Technology, vol. 27, no. 14, pp. 2688?2697, July 2009. [21] D. Wang and A. A. Abouzeid, ?Throughput capacity of hybrid radio-frequency and free-space-optical (rf/fso) multi-hop networks,? in Proc. Information Theory and Ap- plications Workshop 2007, San Diego, CA, Feb. 2007, pp. 3?10. [22] A. Acampora, S. H. Bloom, and S. Krishnamurthy, ?Uninet: a hybrid approach for universal broadband access using small radio cells interconnected by free-space optical links,? IEEE Journal on Selected Areas in Communications, vol. 16, no. 6, pp. 973?987, Aug. 1998. [23] J. Li, C. Blake, D. Coute, H. Lee, and R. Morris, ?Capacity of ad hoc wireless networks,? in Proc. ACM MobiCom?01, Rome, Italy, July 2001, pp. 61?69. [24] V. Gambiroza, B. Sadeghi, and E. Knightly, ?End-to-end performance and fairness in multihop wireless backhaul networks,? in Proc. ACM MobiCom?04, Philadelphia, PA, Sept. 2004, pp. 287?301. 131 [25] I. K. Son and S. Mao, ?Design and optimization of a tiered wireless access network,? in IEEE INFOCOM 2010, San Diego, CA, Mar. 2010. [26] S. M. Navidpour, M. Uysal, and M. Kavehrad, ?Ber performance of free-space optical transmission with spatial diversity,? IEEE Communications Magazine, vol. 6, no. 8, pp. 2813?2819, Aug. 2007. [27] H. Izadpanah, T. Elbatt, V. Kukshya, F. Dolezal, and B. K. Ryu, ?High-availability free space optical and rf hybrid wireless networks,? IEEE Wireless Communications, vol. 10, no. 2, pp. 45?53, Apr. 2003. [28] A. Desai and S. Milner, ?Autonomous reconfiguration in free-space optical sensor net- works,? IEEE Journal on Selected Areas in Communications, vol. 23, no. 8, pp. 1556? 1563, Aug. 2005. [29] B. Epple and H. Henniger, ?Discussion on design aspects for free-space optical commu- nication terminals,? IEEE Communications Magazine, vol. 45, no. 10, pp. 62?69, Oct. 2007. [30] R. Ramirez-Iniguez and R. Green, ?Indoor optical wireless communications,? 1999, pp. 14/1?14/7. [31] M. Kavehrad and S. Jivkova, ?Indoor broadband optical wireless communications: op- tical subsystems designs and their impact on channel characteristics,? IEEE Wireless Communications, vol. 10, no. 2, pp. 30?35, Apr. 2003. [32] T. Komine and M. Nakagawa, ?Fundamental analysis for visible-light communication system using LED lights,? IEEE Transactions on Consumer Electronics, vol. 50, no. 1, pp. 100?107, Feb. 2004. [33] Infrared Data Association, [online]. Available: http://www.irda.org. [34] IEEE, ?Wireless LAN media access control (MAC) and physical layer (PHY) specifica- tions,? 1999. [35] Bluetooth Special Interest Group, [online]. Available: https://www.bluetooth.org/apps/content/. [36] A. G. Al-Ghamdi and J. M. Elmirghani, ?Analysis of diffuse optical wireless channels employing spot-diffusing techniques, diversity receivers, and combining schemes,? IEEE Transactions on Consumer Electronics, vol. 52, no. 10, pp. 1622?1631, Oct. 2004. [37] X. Zhu and J. M. Kahn, ?Free-space optical communication through atmospheric tur- bulence channels,? IEEE Trans. Commun., vol. 50, no. 8, pp. 1293?1300, Mar. 2003. [38] M. Abtahi, P. Lemieux, W. Mathlouthi, and L. A. Rusch, ?Suppression of turbulence- induced scintillation in free-space optical communication systems using saturated optical amplifiers,? IEEE/OSA Journal of Lightwave Technology, vol. 24, no. 12, pp. 4996?4973, Dec. 2006. 132 [39] L. C. Andrews, R. L. Phillips, and C. Y. Hopen, Laser Beam Scintillation with Appli- cations. SPIE Publications, 2001. [40] B. Epstein and V. Mehta, ?Free space optical communications routing performance in highly dynamic airspace environments,? vol. 2, Mar. 2004, pp. 1398?1406. [41] G. Baister and P. Gatenby, ?Pointing, acquisition and tracking for optical space com- munications,? Electronics and Communication Engineering Journal, vol. 6, no. 6, pp. 271?280, Dec. 1994. [42] E. J. Lee and V. W. Chan, ?Part 1: optical communication over the clear turbulent atmospheric channel using diversity,? IEEE Journal on Selected Areas in Communica- tions, vol. 22, no. 9, pp. 1896?1906, Nov. 2004. [43] D. Kedar and S. Arnon, ?Urban optical wireless communication networks: the main challenges and possible solutions,? IEEE Communications Magazine, vol. 42, no. 5, pp. S2?S7, May 2004. [44] S. Chen, S. Cheng, P. Verma, and R. Huck, ?Heuristic algorithms for designing minimum cost fso networks,? Dec. 2009, pp. 1?3. [45] P. C. Gurumohan and J. Hui, ?Topology design for free space optical networks,? in Proc. 21th International Conference on Computer Communications and Networks (ICCCN) 2003, Dallas, TX, Oct. 2003, pp. 576?579. [46] A. Kashyap, K. Lee, M. Kalantari, S. Khuller, and M. Shayman, ?Integrated topology control and routing in wireless optical mesh networks,? Computer Networks, vol. 51, no. 15, pp. 4237?4251, 2007. [47] Z. Hu, P. Verma, and J. S. Jr., ?Improved reliability of free-space optical mesh networks through topology design,? Journal of Optical Networking, vol. 7, no. 5, pp. 426?448, 2008. [48] E. J. Lee and V. W. Chan, ?Performance of the transport layer protocol for diversity communication over the clear turbulent atmospheric optical channel,? vol. 1, May 2005, pp. 333?339. [49] S. D. Milner and C. C. Davis, ?Hybrid free space optical/rf networks for tactical opera- tions,? in Proc. Military Communications Conference (MILCOM) 2004, Monterey, CA, Oct./Nov. 2004, pp. 409?415. [50] J. Sonnenberg, M. Oyler, R. Peach, and G. Burdge, ?Routing impact in highly dynamic mesh networks of rf and fso links,? Oct. 2009, pp. 1?7. [51] E. Korevaar, I. I. Kim, and B. McArthur, ?Atmospheric propagation characteristics of highest importance to commercial free space optics,? in Proceedings International Congress of Mathematicians, vol. 4976, no. 1, Apr. 2003, pp. 1?12. 133 [52] M. Al-Habash, L. C. Andrews, and R. L. Phillips, ?Mathematical model for the irradi- ance probability density function of a laser beam propagating through turbulent media,? Society of Photo-Optical Instrumentation Engineers, vol. 40, no. 8, pp. 1554?1562, Aug. 2001. [53] A. Prokes, ?Atmospheric effects on availability of free space optics systems,? Optical Engineering, vol. 48, no. 6, p. 066001, June 2009. [54] A. A. Farid and S. Hranilovic, ?Outage capacity optimization for free-space optical links with pointing errors,? IEEE/OSA Journal of Lightwave Technology, vol. 25, no. 7, pp. 1702?1710, July 2007. [55] Y. Shim, S. D. Milner, and C. C. Davis, ?A precise pointing technique for free space optical networking,? in Proc. Military Communications Conference (MILCOM) 2003, Boston, MA, Oct. 2004, pp. 1?7. [56] A. Harris, J. J. S. Jr., H. H. Refai, and P. G. LoPresti, ?Alignment and tracking of a free-space optical communications link to a uav,? in The 24th Digital Avionics Systems Conference (DASC) 2005, Oct. 2005, pp. 1.C.2?1?1.C.2?9. [57] G. A. Cap, H. H. Refai, and J. James J. Sluss, ?Optical tracking and auto-alignment transceiver system,? in IEEE/AIAA 27th Digital Avionics Systems Conference (DASC) 2008, Oct. 2008, pp. 2.B.1?1?2.B.1?9. [58] K. Guan, R. Ghanadan, K. McNeil, and S. Kumar, ?Topology formation for tactical networks with directional rf and free-space optical links,? nov. 2008, pp. 1 ?7. [59] E. Ciaramella, Y. Arimoto, G. Contestabile, M. Presi, A. D?Errico, V. Guarino, and M. Matsumoto, ?1.28?tb/s (32x40 gb/s) free?space optical WDM transmission system,? IEEE Photonics Technology Letters, vol. 21, no. 16, pp. 1121?1123, Aug. 2009. [60] R. M. Krishnaswamy and K. N. Sivarajan, ?Design of logical topologies: a linear formulation for wavelength-routed optical networks with no wavelength changers,? IEEE/ACM Transactions on Networking, vol. 9, no. 2, pp. 186?198, Apr. 2001. [61] M. Bilgi and M. Yuksel, ?Multi-element free-space-optical spherical structures with intermittent connectivity patterns,? in IEEE INFOCOM Workshops 2008, Apr. 2008, pp. 1?4. [62] D. S. Alberts, Information age transformation: Getting to a 21st Century military. CCRP Publications, 1996. [63] P. Clark and A. Sengers, ?Wireless optical networking challenges and solutions,? in IEEE MILCOM?04, Monterey, CA, Oct./Nov. 2004, pp. 416?422. [64] F. R. K. Chung, Spectral Graph Theory. American Mathematical Society, 1997. [65] R. G. Gallager, P. Humblet, and P. Spira, ?A distributed algorithm for minimum-weight spanning trees,? ACM Trans. Programming Languages Syst., vol. 5, no. 1, pp. 66?77, 1983. 134 [66] X. Cao, ?Optimizing and modeling topology design in high-speed optical wireless com- munication networks,? in Proc. IEEE ICCSC?08, Shanghai, China, May 2008, pp. 683? 687. [67] S. Boyd, ?Convex optimization of graph laplacian eigenvalues,? in Proc. International Congress of Mathematicians, 2006, pp. 1311?1319. [68] A. Ghosh and S. Boyd, ?Growing well-connected graphs,? in 45th IEEE Conference on Decision and Control, Dec. 2006, pp. 6605?6611. [69] B. Mohar, ?Eigenvalues, diameter, and mean distance in graphs,? Graphics and Com- binatorics, vol. 7, no. 1, pp. 53?64, Mar. 1991. [70] D. Mosk-Aoyama, ?Maximum algebraic connectivity augmentation is NP-hard,? Oper. Res. Lett., vol. 36, no. 6, pp. 677?679, 2008. [71] S. Kirkland and M. Neumann, ?Algebraic connectivity of weighted trees under pertur- bation,? Linear and Multilinear Algebra, vol. 42, no. 3, pp. 187?203, 1996. [72] J. J. Molitierno and M. Neumann, ?The algebraic connectivity of two trees connected by an edge of infinite weight,? The Electronic Journal of Linear Algebra, vol. 8, no. 3, pp. 1?13, 2001. [73] I. S. Dhillon and B. N. Parlett, ?Orthogonal eigenvectors and relative gaps,? SIAM J. Matrix Anal. Appl., vol. 25, no. 3, pp. 858?899, 2003. [74] I. F. Akyildiz, X. Wang, and W. Wang, ?Wireless mesh networks: A survey,? Comput. Netw, Mar. 2005. [75] J. Jun and M. Sichitiu, ?The nominal capacity of wireless mesh networks,? IEEE Wire- less Commun., vol. 10, no. 5, pp. 8?14, Oct. 2003. [76] J. Shi, O. Gurewitz, V. Mancuso, J. Camp, and E. Knightly, ?Measurement and model- ing of the origins of starvation in congestion controlled mesh networks,? in Proc. IEEE INFOCOM?08, Phoenix, AZ, Apr. 2008, pp. 1633?1641. [77] A. A. Abbasi and M. Younis, ?A survey on clustering algorithms for wireless sensor networks,? Computer Commun., vol. 30, no. 14/15, pp. 2826?2841, Oct. 2007. [78] B. Liu, Z. Liu, and D. Towsley, ?On the capacity of hybrid wireless networks,? in Proc. IEEE INFOCOM?03, San Francisco, CA, Mar. 2003, pp. 1543?1552. [79] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, NY: W.H. Freeman & Co., 1990. [80] B. Aoun, R. Boutaba, Y. Iraqi, and G. Kenward, ?Gateway placement optimization in wireless mesh networks with qos constraints,? IEEE Journal on Selected Areas in Communications, vol. 24, no. 11, pp. 2127?2136, Nov. 2006. 135 [81] J. L. Gross and J. Yellen, Graph Theory and Its Applications. New York, NY: CRC Press, 1999. [82] G. W. Flake, R. E. Tarjan, and K. Tsioutsiouliklis, ?Graph clustering and minimum cut trees,? Internet Mathematics, vol. 1, no. 4, pp. 385?408, 2004. [83] B. Mohar, ?The Laplacian spectrum of graphs,? in Graph Theory, Combinatorics, and Applications, Y. Alavi, G. Chartrand, O. Oellermann, and A. Schwenk, Eds. Hoboken, NJ: Wiley, 1991, pp. 871?898. [84] M. Fiedler, ?Algebraic connectivity of graphs,? Czechoslovak Mathematical Journal, vol. 23, no. 2, pp. 298?305, 1973. [85] S. Bandyopadhyay and E. Coyle, ?An energy efficient hierarchical clustering algo- rithm for wireless sensor networks,? in Proc. IEEE INFOCOM?03, San Francisco, CA, Mar./Apr. 2003, pp. 1713?1723. [86] J. Lian, K. Naik, and G. B. Agnew, ?A framework for evaluating the performance of cluster algorithms for hierarchical networks,? IEEE/ACM Trans. Netw., vol. 15, no. 6, pp. 1478?1489, Dec. 2007. [87] R. Jothi and B. Raghavachari, ?Degree-bounded minimum spanning trees,? Discrete Appl. Math., vol. 157, no. 5, pp. 960?970, Mar. 2009. [88] C. Ersoy and S. Panwar, ?Topological design of interconnected LAN-MAN networks,? IEEE J. Sel. Areas Commun., vol. 11, no. 8, pp. 1172?1182, Oct. 1993. [89] R. Elbaum and M. Sidi, ?Topological design of local-area networks using genetic algo- rithms,? IEEE/ACM Trans. Netw., vol. 4, no. 5, pp. 766?778, Oct. 1996. [90] S. Ghosh, K. Basu, and S. Das, ?What a mesh! Architectures for next generation radio access networks,? IEEE Network, vol. 19, no. 5, pp. 35?42, Sept./Oct. 2005. [91] A. S. Ibrahim, K. G. Seddik, and K. R. Liu, ?Improving connectivity via relays deploy- ment in wireless sensor networks,? in Proc. IEEE GLOBECOM?07, Washington, DC, Nov. 2007, pp. 1159?1163. [92] S. Kompella, S. Mao, Y. Hou, and H. Sherali, ?On path selection and rate allocation for video in wireless mesh networks,? IEEE/ACM Trans. Netw., vol. 17, no. 1, pp. 212?224, Feb. 2009. [93] D. Bertsekas and R. Gallager, Data Networks. Prentice Hall, 1992. [94] I. Norros, ?On the use of fractional brownian motion in the theory of connectionless networks,? IEEE Journal on Selected Areas in Communications, vol. 13, no. 6, pp. 953?962, Aug. 1995. [95] E. Miguez, J. Cidras, E. Diaz-Dorado, and J. L. Garcia-Dornelas, ?An improved branch- exchange algorithm for large-scale distribution network planning,? IEEE Transaction of Power Systems, vol. 17, no. 4, pp. 931?936, Nov. 2002. 136