Resource Allocation and Performance Optimization in Wireless Networks by Hui Zhou 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 May 5, 2014 Keywords: Network Optimization, Cell Association, Femtocell, Power Allocation, FSO Copyright 2014 by Hui Zhou Approved by Prathima Agrawal, Chair, Ginn Distinguished Professor of Electrical and Computer Engineering Shiwen Mao, Co-Chair, Associate Professor of Electrical and Computer Engineering Jitendra K. Tugnait, Professor of Electrical and Computer Engineering Ming Liao, Professor of Mathematics Abstract In the past few years, demand has kept increasing for higher data rates in wireless networks due to the increases in the numbers of mobile subscribers and multimedia applications. Femtocell and free space optics(FSO) networks, which both are important solutions to build next generation wireless networks, are two networks studied in this dissertation. In this dissertation, we adopt optimization approaches for network design in both femtocell and FSO networks. The first part of this dissertation provides an introduction to the background and related research issues of the femtocell and FSO networks. In the first two chapters, cell association, handover management and scheduling policies in two-tier femtocell networks are studied extensively. Cell association problem is to associate users to either a macro base station(MBS) or a femtocell base station(FBS). The objectives of cell asso- ciation problem can be: 1) Maximizing total network throughput; 2) Achieving fairness among all users; 3) Balancing load among all BSs. Cell association and handover algorithms are proposed to achieve these objectives. In the following chapters, research is extended to Free space optical (FSO) networking, which is an attractive energy-efficient technology with applications ranging from high capacity military communications to ?Last-mile? broadband access solutions. Topology control, spatial diversity techniques and adaptive transmissions in FSO systems are studied to mitigate weather turbulence which greatly degrades link performance. The problem of building a spanning tree when number of transceivers on each base station is limited in FSO networks is first studied. Then, the challeng- ing problem of relay selection and power allocation in cooperative FSO network is investigated. Last but not the least, the problem of optical power allocation under power budget and eye safety ii constraints is investigated for adaptive WDM transmission to combat the effect of weather tur- bulence in FSO networks. This research provides new visions for practical solutions to mitigate weather turbulence in FSO networks. iii Acknowledgments First of all, I would like to express my deepest gratitude to my advisor and committee chair Prof. Prathima Agrawal,who contributed her broad perspective in refining the ideas in this disser- tation. Thanks for her continuing and inspirational guidance, support and encouragement during my Ph.D. program. I would also like to thank my committee co-chair Prof. Shiwen Mao who provided me with valuable technical opinions. The dissertation would not be finished without his enlightening guidance and persistent support. He also donated precious time and effort to correct my writing with patience. I also would like to thank the other members of my dissertation committee, Prof. Jitendra Tugnait and Prof. Ming Liao, for their valuable comments and suggestions regarding my research work. I have also benefited a lot from the courses taught by them. I really appreciate their time and effort to read and provide valuable opinions on my PhD proposal and dissertation. I am also indebted to Prof. Alvin Lim for serving as the university reader, and reviewing my work. To all the professors whose courses I have taken , I owe my gratitude to their instructions and knowledge that help me finish my Ph.D program. I also want to take this opportunity to recognize all my fellow classmates and friends in the Electrical and Computer Engineering at Auburn University: Dr. Donglin Hu, Gopalakrishnan Iyer, Vijay Sheshadri, Jing Ning, Yi Xu, Yu Wang, Zhifeng He and Zhefeng Jiang for the discussions, cooperation and assistance during these years. In addition, I am very grateful to Dr. Yihan Li for her hospitality and help in my study and life at Auburn. Last, but not least, I would like to extend my heart felt thanks to my parents, without their continuous spiritual support, the achievements of this dissertation could not be possible. Again, I would like to express my gratitude to all my teachers, friends and relatives. My mere thanks would not be sufficient to express my thanks for them. iv Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Femtocell networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 History of Femtocell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.2 Advantage of Femtocell . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.3 Technical issues in femtocell networks . . . . . . . . . . . . . . . . . . . . 5 1.1.4 Major Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 FSO networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.1 Introdution to FSO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2.2 Technical issues in FSO networks . . . . . . . . . . . . . . . . . . . . . . 11 1.2.3 Major Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3 Overview of the Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2 Cell Association and Handover Management in Femtocell Networks . . . . . . . . . . 16 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3.1 Case I: Network Capacity . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3.2 Case II: User Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4 Proposed Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4.1 User Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 v 2.4.2 Handover Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.4.3 Admission Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3 Cell load balancing Policies in Femtocell Networks . . . . . . . . . . . . . . . . . . . 31 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.3 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3.1 Service Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.3.2 Femtocell Access Control . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.4 Cell Association Problem Formulation and Proposed Schemes . . . . . . . . . . . 37 3.4.1 Sequential Fixing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.4.2 Approximation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.4.3 Rounding Approximation Algorithm . . . . . . . . . . . . . . . . . . . . . 41 3.4.4 Greedy Approximation Algorithm . . . . . . . . . . . . . . . . . . . . . . 44 3.4.5 Randomized Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.5 Service Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.6 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.6.1 Case of Open Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.6.2 Case of Closed Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 4 Weather turbulence mitigation through topology control in FSO Networks . . . . . . . 58 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.3 System Model and Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . 61 4.3.1 Model Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.3.2 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 vi 4.4 Topology Control Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.4.1 Bootstrapping Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.4.2 Reconfiguration Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.5.1 Simulation Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.5.2 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5 Joint Relay Selection and Power Allocation in Cooperative FSO Networks . . . . . . . 74 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 5.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 5.3 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5.3.1 Channel Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5.3.2 Cooperation Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.4 Problem Formulation and Upper Bound . . . . . . . . . . . . . . . . . . . . . . . 80 5.4.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 5.4.2 Upper Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 5.5 Solution Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 5.5.1 Centralized Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 5.5.2 Distributed Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.6 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 6 Optical Power Allocation for Adaptive WDM Transmissions in Free Space Optical Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 6.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 6.3 System and Channel Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 6.3.1 Channel Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 vii 6.3.2 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 6.4 Adaptive WDM Transmission . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 6.4.1 Capacity Gain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 6.4.2 Diversity Gain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 6.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 6.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 7 Conclusion and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 7.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 7.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 viii List of Figures 1.1 Femtocell networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1 Femtocell networks with one MBS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 Total network capacity vs. number of users . . . . . . . . . . . . . . . . . . . . . . . 27 2.3 Fairness vs. number of users . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.4 Average number of handovers vs. number of users . . . . . . . . . . . . . . . . . . . 28 2.5 Average number of handovers vs. Nmax . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.1 Femtocell Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2 Femtocell Networks with a faulty BS . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.3 Total service time vs. number of users: Open Access . . . . . . . . . . . . . . . . . . 51 3.4 Average waiting time vs. number of users: Open Access . . . . . . . . . . . . . . . . 52 3.5 Fairness vs. number of users: Open Access . . . . . . . . . . . . . . . . . . . . . . . 52 3.6 Total service time vs. number of users: Close Access . . . . . . . . . . . . . . . . . . 53 3.7 Average waiting time vs. number of users: Close Access . . . . . . . . . . . . . . . . 54 3.8 Fairness vs. number of users: Close Access . . . . . . . . . . . . . . . . . . . . . . . 54 4.1 Algebraic connectivity of tree with degree constraint 5 . . . . . . . . . . . . . . . . . 71 ix 4.2 Average edge weight of tree with degree constraint 5 . . . . . . . . . . . . . . . . . . 72 4.3 Algebraic connectivity of tree with degree constraint from 2 to 4 . . . . . . . . . . . . 72 4.4 Average edge weight of tree with degree constraint from 2 to 4 . . . . . . . . . . . . . 72 5.1 Illustration of a cooperative FSO network. . . . . . . . . . . . . . . . . . . . . . . . . 75 5.2 Throughput vs. number of FSO BS?s. . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5.3 Throughput vs. power budget. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 5.4 Throughput vs. number of FSO transceivers. . . . . . . . . . . . . . . . . . . . . . . 92 5.5 Throughput vs. Attenuation Coefficient ?. . . . . . . . . . . . . . . . . . . . . . . . . 93 5.6 Throughput vs. number of FSO BS?s. . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6.1 Advanced DWDM RoFSO system. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 6.2 Four-point polyhedral outer approximation for log(1 +?) . . . . . . . . . . . . . . . 106 6.3 System capacity vs. the power budget Pmax. . . . . . . . . . . . . . . . . . . . . . . . 111 6.4 System capacity vs. the weather condition. . . . . . . . . . . . . . . . . . . . . . . . 111 6.5 System capacity vs. the distance. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 6.6 System capacity vs. No. of Subcarriers in clear weather. . . . . . . . . . . . . . . . . 113 6.7 System capacity vs. No. of Subcarriers in hazy weather. . . . . . . . . . . . . . . . . 114 6.8 System capacity vs. No. of Subcarriers in foggy weather. . . . . . . . . . . . . . . . . 114 x List of Tables 2.1 Cell Association Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2 Handover Algorithm for User j connecting to BS i . . . . . . . . . . . . . . . . . . . 25 2.3 Admission Algorithm for Inactive User j . . . . . . . . . . . . . . . . . . . . . . . . 25 2.4 Simulation Parameters for Cell Association Algorithms . . . . . . . . . . . . . . . . . 26 3.1 Sequential Fixing for Cell Association . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.2 Greedy Approximation Algorithm for Cell Association . . . . . . . . . . . . . . . . . 44 3.3 Randomized Algorithm for Cell Association . . . . . . . . . . . . . . . . . . . . . . . 49 3.4 Simulation Parameters for Cell Load Balancing Algorithms . . . . . . . . . . . . . . . 51 3.5 Simulation Running Time Open Access (s) . . . . . . . . . . . . . . . . . . . . . . . 53 3.6 Simulation Running Time Close Access (s) . . . . . . . . . . . . . . . . . . . . . . . 56 4.1 DCST Formulation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.2 Maximum Algebraic Connectivity(MAC) Algorithm . . . . . . . . . . . . . . . . . . 67 4.3 Reconfiguration Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 5.1 Simulation Parameters for Cooperative FSO Networks . . . . . . . . . . . . . . . . . 90 5.2 Atmospheric Attenuation Coefficient ? . . . . . . . . . . . . . . . . . . . . . . . . . 90 6.1 Simulation Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 xi Chapter 1 Introduction 1.1 Femtocell networks 1.1.1 History of Femtocell Demand is ever increasing for higher data rates in wireless networks to keep up with the remarkable speed-up of fiber-optic networks. The demand for data traffic has surpassed voice traffic and keeps on growing drastically. According to [1], global mobile data traffic is expected to grow to 10.8 exabytes (1 exa = 1018) per month by 2016, which is an 18-fold increase over 2011. This increase in data traffic on cellular networks is creating challenges for existing cellular networks. Moreover, around 90% of the data services and 60% of the voice services will take place on indoor environments in the near future [2]. How to accommodate needs for data requests from smartphones, tablets, and laptops and maintain quality of service (QoS) for customers is a big challenge. Traditional cellular networks are not able to meet this increasing demand for traffic and the reasons are as follows: ? Costly cell sites ? Limited spectrum availability ? Expensive cell site backhaul Many techniques have been studied in both academia and industry to reduce the energy con- sumption of cellular networks and increase the end user satisfaction. Heterogeneous networks can improve both throughput and energy consumption, due to the fact that macrocell provides better coverage and in the mean time QoS can be accounted for by smaller-size cells, which are usually deployed close to the end users. The diffusion of smaller cells into traditional cellular networks 1 presents a feasible, energy-efficient and cost-effective solution to cater to high volume of data de- mand from users, and in the mean time to maintain profitability for operators. Femtocells have emerged recently as a promising energy-efficient solution to foster growth in wireless data provi- sioning, especially indoors or at cell edge. The idea of small cells has been around for nearly 3 decades [3]. In the early 1990s, South- west Bell and Panasonic developed an indoor femtocell-like solution that re-used the same spec- trum as the macrocells and used wired backhaul. However, there are many reasons (such as, lack of ubiquitous IP backhaul) that refrained this solution from economial success at that time. Mod- ern autonomous and self-adaptive femtocell was introduced to address the mobile data explosion problem. In addition to the escalating data demands, several technological and societal trends have made low-cost femtocells viable. Rearch work in femtocell has increased greatly from 2007 till now. In addition, the European Union has started funding research on femtocells. Hence now we have seen successful commercial femtocell deployments. As of December 2010, 18 operators have launched commercial femtocell services, with a total of 30 committed to deployment [4]. According to the Femto Forum, operator deployments grew by 60% in the second quarter of 2011, including eight of the top ten global mobile operator groups [3]. Femtocells which are also called home base stations are often installed by home users to get better indoor voice and data coverage. Femtocell base station is typically the size of a residential gateway or smaller and connect to the service providers network via broadband such as digital subscriber line (DSL) or cable, and typically supports only a few users. Femtocell base stations operate on relatively low transmit power (100 mW or even 10 mW) andprovideshortrangecoverage(20-30m), inordertoavoidinterferencewithnearbyfemtocells. They share the licensed spectrum with the microcell allocated to operators (in the range of 1.9 - 2.6 GHz) and offer data rates from 7.2 - 14.4 Mbps, and with the advances in LTE/SAE, the data rates will keep increasing, up to 100Mbps [5]. The concept of femtocells is applicable to all standards including GSM, wideband code-division multiple access (WCDMA), World-Wide Interoperability 2 Internet Femtocell Base Station Macrocell Base Station Figure 1.1: Femtocell networks for Microwave Access (WiMAX), and LTE [1]. By the start of 2011, an estimated 2.3 million femtocells were already deployed globally. In femtocell networks, there are usually two types of base stations, the macrocell base station (MBS) and the femtocell base station (FBS, which is also commonly known as Femtocell Access Points or FAP). From the operators viewpoint, macrocell base station can offload a significant amount of traffic to femtocell base station so that equipment cost and power consumption can be greatly diminished. FBS provides a highly effective way to ease the traffic carried by a MBS. From the customers viewpoint, femtocells can be conveniently deployed as wanted and provide better service while consuming less power [6]. As shown in Fig. 1.1, A femtocell is usually a small cellular network, with a FBS connected to MBS via broadband wireline. It is designed to offload MBS traffic and serve the approved users when they are within the coverage. Due to the reduced distance of wireless transmission, femtocell is shown to be effective in reducing transmit power [7] and improving signal-to-interference-plus- noise ratio (SINR), which lead to prolonging battery life of mobile devices and enhancing network coverage as well as capacity [8]. 3 1.1.2 Advantage of Femtocell Femtocells have attracted significant interest from wireless industry. Recently, major wireless network operators in the United States such as AT&T, Sprint and Verizon, have provided femtocell serviceplans. Femtocellsprovideimprovedcoverageandcapacitytomobileuserswhenandwhere needed. The advantages of femtocells are summarized as: ? Better coverage and capacity, especially for users at home or at the cell edge; ? Improved macrocell reliability, since macrocell base stations will have more available re- sources to provide better service for mobile users; ? Reduces the operating and capital expenditure costs; femtocells can be deployed quickly, unliketraditionalmacrocellulardeployments,whichtakemuchlongerduetositeacquisition, purchase of radio infrastructure and backhaul, and other similar considerations [1]; ? Reduced subscriber turnover [8]. Although the potential of femtocells is highly promising, a broad range of problems across techni- cal issues, regulatory concerns and economic incentives should be addressed [3]. The challenging technical issues include synchronization, cell association, mobility and handover, interference mit- igation, network organization, and quality of service (QoS) provisioning [9]. Femtocell access point is installed at home or at work, and is of small size, which is similar to Wi-Fi AP. However, there are many differences between femtocells and Wi-Fi which distinguish them from each other. First, Wi-Fi operates in unlicensed bands, while femtocells operate in costly (licensed) and limited spectrum bands. Thus femtocells require careful planning compared to Wi- Fi networks [10]. Second, femtocells capture 100 percent of traffic, whether it is voice or data and whether it originates from a feature phone, smart phone, or a laptop. This is usually not possible in the case of Wi-Fi. And when it comes to data rates, femtocells still can not compete with Wi-Fi which can support data rates as high as 600 Mb/s both downlink and uplink. However, femtocells have advantages in providing guaranteed QoS using licensed bands, whereas Wi-Fi cannot [1]. 4 1.1.3 Technical issues in femtocell networks In femtocell networks, whenever a mobile user comes into the coverage area of a femtocell, the user equipment (UE) will automatically associate with it if the user equipment (UE) is au- thorized to use the service. A mobile user subscribed to one or more femtocells would want to get service from femtocells to benefit from preferential charging or better QoS support than an overlaying macrocell. The search function may be either autonomous or manual [11]. After UE is associated with one femtocell, the traffic flows over the air interface to the femtocell and over the Internet to the operators core network and/or other Internet destinations [1]. There are three different access control modes in femtocell networks, the open access, the closed access and the hybrid access mode. Open-access scheme allows all mobile users of an operator to connect; in this case, femtocell is often deployed directly by an operator to provide coverage in an area where there is a coverage hole. In closed-access mode, only a specific user group can get service. In the hybrid access scenario, the femtocell owner may allow access to all user equipment (UE) but with preferential access to a certain group of UE [11]. Closed access method has been shown to create high level of interference in the proximities of the FAP and decreased system throughput by 15%, however, surveys suggest that closed Access mode is subscribers favorite option [12]. On the other hand, open access scheme provides a better overall network performance in terms of throughput and utilization but handover increases and user satisfaction decreases. Introducing femtocell also means introducing interference if no appropriate mitigation strat- egy is adopted. Coexistence of femtocells and macrocells in orthogonal channels is simple but results in low spectrum efficiency from a system point of view [6]. Femtocells and macrocells using the same channel will introduce increased level of interference, especially in closed-access scenario. However, due to high cost of licensed spectrum, operators may prefer co-channel shared resource allocation but reusing frequency bands in an uncoordinated random fashion introduces potentially destructive interference [10]. For example, to get better received signal-to-interference- plus-noise-ratio(SINR),onefemtocellbasestationmayincreasetransmitpower; however,thiswill reduce the throughput of many neighboring cells. Thus, one research topic is on optimal resource 5 allocation in femtocell networks. With the consideration of interference, the optimal resource al- location problem may have different objectives, such as maximizing throughput or maximizing proportional-fairness. Femtocells are often installed by customers themselves in a plug-and-play manner, similar to a WiFi access point. Unlike WiFi, femtocells operate mainly in licensed bands. Because of the randomness in the locations of FBS, interference management is one of the most important technical challenges in femtocell networks. Fast power control has been adopted before in or- der to compensate for path loss and fading, and to provide uniform coverage. When femtocells are added in the networks, power control creates dead zones, which is also called loud neighbor problem [8]. On the reverse link, nearby macrocell user transmits with high power to macro BS and causes unacceptable interference to nearby femtocells users. On the forward link, at the cell edge macrocell users are severely affected by nearby femtocell transmissions [8]. Due to the fact that centralized interference management is difficult to implement in femtocell networks, there is a significant amount of research on a variety of interference management schemes, such as adaptive access scheme, cognitive radio, and dynamic frequency planning in WiMax femtocells. By the introduction of femtocell, mobile users are now facing more handovers than ever. The normalhandoveronlyoccurswhenusersmove fromoneMBStoanotherMBS.Now, therearetwo more kinds of handovers. One kind of handover occurs between MBS and FBS when UE moves from outdoors to indoors or vice versa. A certain level of synchronization between FBS and MBS is required during this kind of handover. Another kind of handover occurs when a user moves from one FBS to another FBS which is associated with the same cellular service [12]. Handover control among the femtocells and a macrocell is also one of the major technical challenges in femtocell networks. Research has been done on handover management considering signal strength, available wireless resources and access mode. The security of the transfer of cellular channels and more importantly the timing information is also still an open problem. Finally, since femtocells are likely to use xDSL, synchronization is 6 also a major challenge due to xDSL asymmetric bandwidth and the load on the core Point-to-Point (PTP) time servers [5]. 1.1.4 Major Contributions Femtocells are recognized as effective in improving network coverage and capacity, and re- ducing power consumption due to the reduced range of wireless transmissions. Although highly appealing, a plethora of challenging problems need to be addressed for fully harvesting its poten- tial. We investigate the problem of cell association and handover management in femtocell net- works. We consider an MBS and multiple FBS?s deployed in a femtocell network. The MBS and FBS?s cooperatively send data to users in the network through downlink transmission. Each user is allowed to connect to either the MBS or an FBS. Cell association, handover management and scheduling policies in two-tier femtocell networks are studied extensively. Cell association prob- lemistoassociateuserstoeitheramacrobasestation(MBS)orafemtocellbasestation(FBS).The objectives of cell association problem can be: 1) Maximizing total network throughput; 2) Achiev- ing fairness among all users; 3) Balancing load among all BSs. Cell association and handover algorithms are proposed to achieve these objectives. The problem of striking a balance between total network throughput and user fairness in femtocell networks is investigated in Chapter 2. Two extreme cases for cell association are first discussed and analyzed, and an algorithm to maximize network capacity while achieving fairness among users is proposed. Based on this algorithm, a handover algorithm to reduce the number of unnecessary handovers using Bayesian estimation is further developed. The proposed handover al- gorithmisdemonstratedtooutperformaheuristicschemewithconsiderablegainsinthesimulation study. In Chapter 3, we investigate the problem of cell association and service scheduling in femto- cell networks. In addition to the general goal of offloading macro base station (MBS) traffic, we also aim to minimize the latency of service requested by users, while considering both open and 7 closed access strategies. We show the cell association problem is NP-hard, and propose several near-optimal solution algorithms for assigning users to base stations (BS), including a sequential fixing algorithm, a rounding approximation algorithm, a greedy approximation algorithm, and a randomized algorithm. For the service scheduling problem, we develop an optimal algorithm to minimize the average waiting time for the users associated with the same BS. The proposed algo- rithms are analyzed with respect to performance bounds, approximation ratios, and optimality, and are evaluated with simulations. 1.2 FSO networks 1.2.1 Introdution to FSO Free Space Optical (FSO) networks, namely optical wireless networks, are wireless telecom- munication systems that make use of free space as transmission medium to deliver optical data signals at high bit rates. FSO are considered as an important alternative to the radio frequency (RF) systems as the backhaul solution for future data-intensive networks. It can support extremely high data rate while only requires relatively low operational cost. Due to these advantages along with others, FSO has drawn great attention from many research institutions. FSO technology does not require licensed spectrum and thus manifold gain in the mobile data capacity can be achieved to curtail the impact of the prevailing bandwidth capacity crunch phenomena without imposing much interference problem in the existing networks. FSO communications has already been used as a promising broadband wireless access technology to resolve the existing ?Last-mile? access network problems. The congestion and the limitations on bandwidths of the radio spectrum have inhibited unrestricted growth of traditional RF systems [13]. Drawing increasing attention, free space optical(FSO) networks are considered as an important alternative to the radio frequency (RF) systems as the backbone solution for future data-intensive networks. This appeal is primarily due to their high optical fiber-like data rates, resistance to electromagnetic interference, and secu- rity among other advantages. Nevertheless, the advantages of free space optics have not yet been fully exploited. 8 There are many advantages of optical communications, including [14]: ? Space optical links can support high date rate transmission. Free space optical links in the order of 10 Gb/s have been achieved over reasonable distances (1 km). ? It is license-free. FSO operates in the infrared(IR) spectral range of 8001700 nm and does not require operating license worldwide. ? Optical beams are immune to electromagnetic interference. ? FSO system is easy to deploy and especially in war-torn countries for example, or during disaster relief, FSO communication systems are highly suited to jump start the establishment of a core communication infrastructure. ? Due to confined beam and point-to-point transmission properties [14], 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. FSO and fiber both have the ability to support high-bandwidth transmission but intuitively, light transmits through free space in FSO systems while light transmit through a confined medium in fiber. Due to this fundamental difference, light intensity in FSO systems may suffer from scat- tering, physical obstructions, and scintillation. This is one disadvantage of FSO over fiber. In other words, laser power attenuation through the atmosphere is variable and difficult to predict. However, FSO is more cost-effective and flexible in multiple architectures, and FSO is more en- vironment friendly. FSO operates in the infrared(IR) spectral range of 800-1700 nm and does not require operating license worldwide. An FSO system can operate in full duplex operation. Each FSO link head typically includes a transceiver capable of receiving and transmitting in parallel and at the same time [15]. 9 FSO can be used for satellite-to-satellite communications, up-and-down links between space platforms and aircraft, ships, and other ground platforms [16], disaster recovery and emergency response, among others. FSO is considered as a potential solution for ?Last-mile? problem. Nowa- days, providers can provide broadband applications to the end user through fiber optic networks. However, financialissues arepreventing layingfibers tousers andthus instead, users are connected to the fiber optic networks via other means such as cable, DSL, or satellite [13]. However the cost per Mbps is high and will remain high at least for the foreseeable future [17]. With the advance of FSO technology, ?Last-mile? problem may be addressed without high cost. FSO represents the most viable alternative in terms of bandwidth scalability, deployment speed and cost effectiveness. The exponential growth in the demand for high throughput and low latency applications for mo- bile users is forcing fundamental changes to cellular network topologies. The most natural way to embed FSO products within cellular networks is to consider them as point-to-point replacements of terrestrial links within the core network [14]. In addition to ?Last-mile? problem, FSO has been extensively studied in the application of hybrid RF/FSO system. Due to the complementary nature of radio and FSO communications, both in capacity and coverage, the combined use for data transmission suggests advantages over a single media [14]. FSO links are severely attenuated in foggy conditions, whereas microwave RF frequencies are significantly attenuated by rain. RF can be utilized to facilitate functions such as acquisition, tracking, control signaling, neighbor discovery, and providing a backup communica- tion channel. In some proposed systems, RF serves as the backup for FSO networks, while in other systems, FSO serves as the backup for RF systems. There are many ways to explore the potential of FSO and ways to incorporate both FSO and RF technologies in wireless networks. Recently, in order to overcome the limitation of the conventional FSO systems, researchers have developed new generation FSO technology, which does not require converting the signal from electrical to optical and vice versa before transmitting or receiving through freespace. Radio on Free-Space Optics (RoFSO) is the technology that transmission of wireless signals using FSO 10 links. In this configuration, the radio signal is emitted directly to free-space and therefore, a pro- tocol and data rate transparent FSO link is achieved [18]. Signal transmission qualities of various high frequency band radio services over a RoFSO link are affected by not only a radio channel environment but also FSO channel condition [19]. RoFSO is analogous to Radio-over-Fiber (RoF) technology, which modulates RF subcarriers onto an optical carrier for distribution over fiber network at low cost, over long distance and low attenuation. However, the success of RoF technology depends on availability of installed optical fiber cables. RoFSO is more flexible and now it is shown by experiments that it is capable of simultaneously transmitting multiple RF signals representing various wireless services over atmo- sphere [20]. 1.2.2 Technical issues in FSO networks There are many research opportunities and also challenges in different aspects of FSO net- works, such as pointing, acquisition and tracking (PAT), weather/environment issue, channel ran- domness, and topology control [21]. One issue that needs to address before FSO system to see the life is the eye safety issue. Eye safety requires optical transmitters to comply with the regula- tions. In the United States, the Food and Drug Administration considers power density of about 100 mW/cm2 at 1550 nm, or 1 mW/cm2 at 780 nm safe to the unaided eye [14]. High-power beams can suppress atmospheric disturbance and make it possible to meet re- quired 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. The performance of FSO systems can be degraded by the safety regulations of the transmit power [13]. Operating low power sources demands the availabil- ity of sensitive receivers and may incur more interference from environments. Additionally, it is worthy to learn that indirect modulation/direct detection (IM/DD) is the main mode of detection in FSO systems but coherent communications have also been proposed as an alternative detection 11 mode. Among these, heterodyne detection is a more complicated detection method but has the ability to overcome the thermal noise effects [22]. Since an FSO transmitter is highly directional, FSO systems are often designed to have a divergence of a few milliradians or less in order to concentrate the optical energy on a receiver. Each ?optical transceiver? must be simultaneously pointed at the other for communication to take place. FSO links often need to use Pointing, Acquisition, and Tracking (PAT) subsystems. PAT in FSO communications is challenging and non-trivial. The pointing mechanism starts with finding out where potential nodes exist for establishing a link in the three dimensional free space and then proceeds to the connection procedure. The acquisition mechanism is related to signal modulation and detection techniques. 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. Atmospheric obstructions (e.g., due to the weather turbulence or flying objects) can degrade the link performance considerably. As a laser beam passes through a medium containing atoms, molecules, and particles, its intensity reduces and there are two processes that cause extinction: absorption, and scattering. Both of these processes remove energy from the forward propagating beam direction [15]. Random variations in the refractive index of the Earths atmosphere are re- sponsible forrandomfluctuationsinlaserbeamirradiance calledscintillations. Relatedturbulence- induced effects include beam spreading beyond the spreading predicted by diffraction and a con- tinuousrandommotionofthebeamcentroidaboutthereceiver. Theseeffectsmayresultinrandom signal losses at the receiver, and thus system bit error rates increase, and in severe weather condi- tions they may even lead to the complete loss of signal altogether [15]. Temperature fluctuations in the air will cause refractive-index changes greatly. Huygens-Fresnel principle models the fading of a wave due to passage through air turbulence. It is typical for deep fades to last about 1-100 12 us [16], and when the link is operating at multigigabits per second, the loss of potentially up to 109 consecutive bits may occur, causing devastating effects on the throughput of the network [16]. The constant presence of turbulence in the atmospheric channel is one of the limiting factor in reliable FSO communication link performance [15]. 1.2.3 Major Contributions In this dissertation, we propose techniques for improving the reliability of FSO systems to mitigate the effect of weather turbulence. We adopt optimization skills and graph theory to im- prove the energy efficiency of FSO systems. Topology control, spatial diversity techniques and adaptive transmissions have been studied and proved to be effective in maintaining system perfor- mance. Power allocation schemes are developed in cooperative FSO networks and adaptive FSO communication systems. Topology control is an important problem in FSO networks. The problem of building a span- ningtreewhennumberoftransceiversoneachbasestationislimited, inFSOnetworks,isNP-hard. What makes the problem even more challenging is to maximize the algebraic connectivity of the spanning tree. We develop an initially configuring, or bootstrapping, algorithm which produces a degree constrained spanning tree with high algebraic connectivity and also high average edge weight, where the edge weight in the graph represents the FSO link reliability. We also develop a fast reconfiguration algorithm when one or more links fail in the FSO network. Our algorithms outperform alternative schemes in improving both algebraic connectivity and average edge weight. The robustness of the resulting topology of FSO networks is significantly improved. Next, we also consider the challenging problem of relay selection and power allocation. We investigate the problem of maximizing the FSO network-wide throughput under constraints of a givenpowerbudgetandnumberofFSOtransceivers. TheproblemisformulatedasaMixedInteger Nonlinear Programming (MINLP) problem, which is NP-hard. We first adopt the reformulation- linearization technique (RLT) to derive an upper bound for the original MINLP problem. Due to 13 the relaxation, the solutions obtained from RLT is infeasible. We propose both centralized and dis- tributed algorithms using bipartite matching and convex optimization to obtain highly competitive solutions. The proposed algorithms are shown to outperform the non-cooperative scheme and an existing relay selection protocol with considerable gains through simulations. Radio over Free Space Optics (RoFSO) provides a promising enhancement to optical fiber systems. In an RoFSO system using wavelength-division multiplexing (WDM), it is possible to concurrently transmit multiple data streams consisting of various wireless services at very high rate. In this chapter, we develop power allocation schemes for adaptive WDM transmissions to combat the effect of weather turbulence in FSO networks. The problem of optical power allocation under power budget and eye safety constraints is investigated for adaptive WDM transmission in RoFSO networks. Simulation results show that WDM RoFSO can support high data rates even over long distance or under bad weather conditions with an adequate system design. This work provides new visions for practical solutions to mitigate weather turbulence in FSO networks. 1.3 Overview of the Dissertation The dissertation is organized into three parts. The first part is the introduction to femtocell networks and FSO networks in Chapter 1. Thesecondpartincludestwochapters: Chapter2andChapter3. InChapter2,cellassociation and handover management policies are discussed and several algorithms are proposed to maximize system throuput while maintaining certain user fairness. In Chapter 3, cell association policies are designed with the objectives of minimizing the service latency in femtocell networks. Research is extended to FSO networking in the third part of this dissertation. Topology con- trol, spatial diversity techniques and adaptive transmissions in FSO systems are studied to mitigate weather turbulence in the next chapters. In Chapter 4, the problem of building a spanning tree when the number of transceivers on each base station is limited in FSO networks is studied. In Chapter 5, the challenging problem of relay selection and power allocation in cooperative FSO network is investigated. Both centralized 14 and distributed algorithms using bipartite matching and convex optimization to obtain highly com- petitive solutions are proposed, and are shown to outperform the non-cooperative scheme and an existing relay selection protocol with considerable gains through simulations. In Chapter 6, power allocation schemes for adaptive WDM transmissions are developed to combat the effect of weather turbulence in FSO networks. The problem of optical power allocation under power budget and eye safety constraints is investigated for adaptive WDM transmission in RoFSO networks. Chapter 7 concludes past work and introduces the research topics in future studies. 15 Chapter 2 Cell Association and Handover Management in Femtocell Networks 2.1 Introduction Due to the nature of open space used as wireless transmission medium, wireless network ca- pacity is largely limited by interference. Mobile users at the border of cellular networks require considerably large transmit power to overcome attenuation, which in return causes interference to other users and reduces network capacity. To address this issue, femtocells provide an effec- tive solution by shortening transmission distance and bringing base stations (BS) closer to mobile users [8]. Femtocells have received considerable interest from both industry and academia. Technical challenges, regulatory requirements and economic concerns in femtocell networks are comprehen- sively discussed in [8] and [3]. Since FBS?s are distributedly deployed and are able to spatially reuse the same spectrum belonging to the MBS, many research efforts were made on interference mitigation by assigning users to the proper BS. In [23], the disadvantages of open and closed ac- cess mechanisms were discussed and a hybrid access control scheme was introduced. In [24], a stochastic geometric model was introduced to derive the success probability for MBS?s and FBS?s under open and closed access schemes. A learning-based cell selection method for an open access femtocell network was proposed in [25]. The main objective of handover algorithm is to determine an optimal connection while min- imizing handover latency and reducing unnecessary handovers. In [26], an efficient handover algorithm was proposed by considering the optimal combination of received signal strengths from a serving MBS and a target FBS. In [27], a new handover decision algorithm based on mobility pattern and location prediction was developed to reduce the number of unnecessary handovers due totemporaryfemtocellvisitors. Bothsignalstrengthandvelocitywereconsideredfortheproposed 16 handover algorithm in [28]. A hybrid access scheme and a femtocell-initiated handover procedure with adaptive threshold were studied in [29]. In this section, we investigate the problem of cell association and handover management in femtocell networks. We consider an MBS and multiple FBS?s deployed in a femtocell network. The MBS and FBS?s cooperatively send data to users in the network through downlink transmis- sion. Each user is allowed to connect to either the MBS or an FBS. Open access mechanism is employed since it is shown significantly higher network capacity than closed access system [24]. In open access systems, all users have chance to connect to each FBS. The problem is to decide the assignment between BS?s and users with the objective of maximizing network throughput and achieving fairness among users. Besides, when users are in motion, reducing the number of han- dovers and handover delay is critical for the success of femtocell technology. We provide an analysis of network downlink capacity for two extreme cases. In case I, each BS selects the best user and total network capacity is maximized. However, in case II, each user chooses the best BS to connect and fairness is achieved among users. Then we propose a new cell association algorithm to find a trade-off between two extreme cases. Based on the cell association algorithm, we further present a handover algorithm as well an access control algorithm for mobile users. The remainder of this chapter is organized as follows. The related work is discussed in Sec- tion2.2. WepresentthesystemmodelandanalyzetwoextremecasesinSection2.3. InSection2.4, cell association and handover management algorithms are proposed. The proposed algorithms are evaluated in Section 2.5. Section 2.6 concludes this chapter. 2.2 Related Work Femtocells have received considerable interest from both industry and academia. Technical challenges, regulatory requirements and economic concerns in femtocell networks are comprehen- sively discussed in [8] and [3]. Since FBS?s are distributedly deployed and are able to spatially reuse the same spectrum belonging to the MBS, many research efforts were made on interference 17 mitigation by assigning users to the proper BS. In [23], the disadvantages of open and closed ac- cess mechanisms were discussed and a hybrid access control scheme was introduced. In [24], a stochastic geometric model was introduced to derive the success probability for MBS?s and FBS?s under open and closed access schemes. A learning-based cell selection method for an open access femtocell network was proposed in [25]. The main objective of handover algorithm is to determine an optimal connection while min- imizing handover latency and reducing unnecessary handovers. In [26], an efficient handover algorithm was proposed by considering the optimal combination of received signal strengths from a serving MBS and a target FBS. In [30], a new handover decision algorithm based on mobility pattern and location prediction was developed to reduce the number of unnecessary handovers due totemporaryfemtocellvisitors. Bothsignalstrengthandvelocitywereconsideredfortheproposed handover algorithm in [28]. A hybrid access scheme and a femtocell-initiated handover procedure with adaptive threshold were studied in [29]. 2.3 System Model We consider a femtocell network with an MBS (indexed 0) and M FBS?s (indexed from 1 to M), which is illustrated in Fig. 2.1. The MBS and M FBS?s are connected to the Internet via broadband wireline connection, where N mobile users are randomly located inside the macrocell coverage area. We assume the MBS andM FBS?s are well synchronized and they occupy the same spectrum at the same time to send data to mobile users. Each BS allocates the whole bandwidth to users which are associated with it. Let P0 be the MBS transmit power and h0,k be the channel gain between the MBS and k-th user. Likewise, Pi and hi,k where i?1 denote the transmit power of the i-th FBS as well as the channel gain between the i-th FBS and k-th user. We assume an additional white Gaussian noise (AWGN) at mobile users with power density ?2. The capacity at the k-th user from its serving 18 Internet Macrocell Base Station Broadband wireline Femtocell User Figure 2.1: Femtocell networks with one MBS MBS is given by: Ck = BN 0 log2 parenleftbigg 1 + |h0,k| 2P0 ?2 +I0,k parenrightbigg (2.1) where B is the network bandwidth, N0 is the number of MBS users, and I0,k = summationtextMi=1|hi,k|2Pi is the interference from FBS?s. We assume the bandwidth is equally allocated to all served users. The capacity at the j-th user from the i-th FBS is given by: Cj = BN i log2 parenleftbigg 1 + |hi,j| 2Pi ?2 +Ii,j parenrightbigg (2.2) where Ni is the number of users served by the i-th FBS and Ii,j =summationtextMl=0,lnegationslash=i|hl,j|2Pl is the interfer- ence from the MBS and other FBS?s. By combining (2.1) and (2.2), we have the following equation for the capacity at the j-th user from the i-th BS: Cj = BN i log2 parenleftbigg 1 + |hi,j| 2Pi ?2 +Ij?|hi,j|2Pi parenrightbigg = BN i log2 parenleftbigg ?2 +I j ?2 +Ij?|hi,j|2Pi parenrightbigg = BN i log2 parenleftbigg 1 1??i,j parenrightbigg (2.3) 19 where Ij =summationtextMi=0|hi,j|2Pi is the sum of received power from its serving BS and interference from other BS?s, and ?i,j =|hi,j|2Pi/(?2 + Ij) is SINR, which is the percentage of desired power in Ij. Note that Ij does not depend on which BS the user is connected to, and it is a constant for any BS. 2.3.1 Case I: Network Capacity Initially, our objective is to maximize the total network capacity. By denoting Ui as the set of users connected to the i-th BS, we have Ni =|Ui|. Then, by using (2.3), the objective function can be expressed as: Maximize: Ctot = Msummationdisplay i=0 B Ni summationdisplay j?Ui log2 parenleftbigg 1 1??i,j parenrightbigg . (2.4) where Ui is the set variable and Ni is the set size. The optimal solution to the problem above is that each BS chooses one user with the highest SINR to connect. This solution is able to achieve the highest network throughput by assigning only one best user to each BS. The rest of users are not allowed to access the network. This solution is unfair and inefficient because only a small portion of users are served. With this scheme, this system can only accommodate at most M + 1 (the number of BS?s) users. 2.3.2 Case II: User Fairness To achieve fairness among users, we divide the bandwidth equally and allocate them to all users connected to the same BS. Then, a straightforward heuristic solution is proposed that each user j chooses a BS with the highest SINR to connect. However, this approach may incur the QoS problems, especially when all users choose the same BS to connect. Each user is assigned with a very small bandwidth which leads to extremely low capacity for each user. On the other hand, the users with low SINR from any of BS?s may jeopardize the total network throughput. Obviously, blocking these users can improve the total network capacity. To guarantee the minimum QoS 20 requirements of each user and maximize the total network capacity, only users with SINR above ?1 are allowed to access network and each BS is able to serve at most Nmax users. 2.4 Proposed Solution From our previous analysis in case I, we find that the total network capacity is maximized if each BS chooses only one user with the highest SINR. However, this scheme is not fair for the otherusersbecausetheydonothavechancetobeserved. AlthoughtheschemeincaseIIisfair, the network capacity is very low. Therefore, we want to find a trade-off between network performance and fairness. 2.4.1 User Classification Before introducing our scheme, we adopt q thresholds ?i?s to divide SINR?s into q+1 levels: Li,j = ? ???? ? ???? ? 0, ?i,j < ?1 l, ?l??i,j < ?l+1,l?{1,???,q?1} q, ?i,j ??l+1 (2.5) According to Li,j, the users are divided into q + 1 groups. Our idea is to group these users and let users in one group connect to the same BS. Since the SINR values of the users in the same group are very close, we can replace individual SINR with the average value. Then, the objective function in (2.4) can be rewritten as: Ctot = Msummationdisplay i=0 B Ni qsummationdisplay l=0 summationdisplay j?Ui,l log2 parenleftbigg 1 1??i,j parenrightbigg ? Msummationdisplay i=0 B qsummationdisplay l=0 Ni,l Ni log2 parenleftbigg 1 1??i,l parenrightbigg (2.6) 21 where Ui,l ={j|j?Ui,Li,j = l}, Ni,l =|Ui,l|is the number of users in Ui,l and ?i,l is the average value of SINR in Ui,l. If we denote CNC and CUC as the total network capacity achieved by case I and proposed scheme, respectively, we have the following lemma. Lemma 1. CNC is a upper bound of CUC. Proof. Although it is obvious that CNC is greater than CUC, we provide detailed mathematic anal- ysis proof. Due to the fact that arithmetic mean is always equal to or greater than geometric mean and the equality holds if all numbers are equal, we have the following inequality: productdisplay j?Ui,l (1??i,j)?(1??i)Ni,l (2.7) By taking inversion and logarithm to the both sides of the inequality above, we have: summationdisplay j?Ui,l log2 parenleftbigg 1 1??i,j parenrightbigg ?Ni,l log2 parenleftbigg 1 1??i,l parenrightbigg (2.8) Therefore, the lemma holds. Although CNC is a upper bound of CUC, their values are very close due to the fact that the SINR values of the users from the same group fall within the same range and are close to each other. Therefore we can adopt (2.6) as objective function instead of (2.4). Obviously, to maximize CUC, the number of the users at the q + 1 level Ni,q should be equal to Ni since ?i,l > ?i,l?1 for any 0 < l ?q. Then, we can merge users that do not connect to BS?s into one group and divide users into three groups with q = 2. In the first group, the SINR?s of these users are too low to allow them to connect to any of the BS?s. Comparatively, each user in the third group is connected to one of the BS?s. The rest of users in the second group are candidate that will be admitted to the BS?s when BS?s have available resource to allocate. Then, we rewrite CUC as: CUC = max Msummationdisplay i=0 Blog2 parenleftbigg 1 1??i,2 parenrightbigg (2.9) 22 Note that CUC only depends on the average SINR of users in the third class. Until now, we assume all BS?s adopt the same ? to classify the users. By considering the distribution of users and BS, we denote ?il as the threshold adopted by BS i to push users onto different BS?s. To simplify the analysis, we assume ?i1 = ?1 for all BS?s. An algorithm with objectiveoffindingatrade-offbetweennetworkcapacityanduserfairnessispresentedintable2.1. In step 2, the users with all SINRs below the threshold ?1 are removed from user set. From step 4 to step 16, each BS finds its candidate user set according to thresholds ?i2. Then, each user in the candidate user set can make its candidate BS list accordingly. The user on the candidate user list is allowed to choose the best BS from its candidate BS list. Once the BS is assigned with Nmax user, it is removed and not available for the rest of users. In steps 17?19, the BS?s adjust its ?i2 according to the number of users that have already been assigned. If the number of assigned users is small, the threshold ?i2 is reduced with large step-size ?. Once the execution of algorithm is completed, the BS with larger ?i2 usually has higher network capacity due to the higher average SINR. 2.4.2 Handover Algorithm Previously, we discuss the cell association when all users are not in motion. Now, we consider user mobility in this section. Since all users may travel from one cell to another, an efficient handover algorithm is essential to handle this issue. Before presenting our algorithm, we have to introduceseveralnotationsusedinthealgorithm. First,wedenote?i asthecoverageofthei-thBS, in which the received power from the i-th BS is dominant among all received power from all BS?s. ?i is denoted as the probability that user is in the coverage of the i-th BS. Since the coverage of femtocell is very small, the probability of user in the coverage of MBS, ?0, is much higher than the other?i?s(inegationslash= 0). Inaddition,wedefineaconditionalprobability?i = Pr(?i?,j > ?i,j|Loc(j)??i) as the probability that SINR from the i?-th BS is greater than that from the i-th BS conditioned on user j is in the coverage of the i-th BS where Loc(j) is the location of the user j. Then, we collect SINR information from all BS?s for T times and count the times that SINR from the BS i is less 23 Table 2.1: Cell Association Algorithm 1: Initialize ?i,j for all i,j, ?i1, ?i2,F,Uand ? 2: Remove users{j|?i,j < ?1,?i}fromU 3: WhileFis not empty andUis not empty 4: Find candidate user set: Vi ={j|j?U,?i,j ??i2} 5: If?Mi=0Vi is empty 6: The algorithm is terminated 7: End if 8: Find candidate BS set: Wj ={i|i?F,j?Vi,?j??Mi=0Vi} 9: For j??Mi=0Vi 10: Find the i? BS: i? = argmaxi?Wj ?i,j 11: Add user j to Ui? 12: Remove user j fromU 13: If Ni? = Nmax 14: Remove the BS i? fromFand all Wj?s 15: End if 16: End for 17: For i?F 18: Adjust ?i2 = max{?i2?|Nmax?Ni|?,?i1} 19: End for 20: End while than those from the other BS?s, denoted byni. Thus, SINR?s are comparedfor totallyM?T times. With comparison results of SINR, denoted by ?, we can adopt Bayesian estimation to estimate the posterior probability that user j is in the coverage of BS i as: Qi = Pr(Loc(j)??i|?) = Pr(?|Loc(j)??i)?isummationtextM i=0 Pr(?|Loc(j)??i)?i = ? ni i (1??i) MT?ni?i summationtextM i=0 ? ni i (1??i)MT?ni?i . (2.10) The proposed handover algorithm is presented in table 2.2. In steps 3?4, the connection between user and BS is terminated because the SINR requirement at user j cannot be satisfied by BS i. Note that ?i,j is the average SINR over T times. In steps 5?12, we compute the posterior 24 Table 2.2: Handover Algorithm for User j connecting to BS i 1: While TRUE 2: Collect SINR ?ti,j (t = 1,???,T) from all BS?s 3: If ?i,j < ?1 4: Break the connection between i and j 5: Else if ?i,j < ?i2 6: Compute posterior probability Qi 7: Wj ={i|Ni < Nmax and Qi?? and ?i,j ??i2} 8: If Wj is not empty 9: Find the BS i? = argmaxi?Wj Qi 10: Break the connection with BS i and connect to the BS i? 11: End if 12: End if 13: End while Table 2.3: Admission Algorithm for Inactive User j 1: While TRUE 2: Collect SINR ?ti,j (t = 1,???,T) from all BS?s 3: Compute posterior probability Qi 4: Wj ={i|Ni < Nmax and Qi?? and ?i,j ??i2} 5: If Wj is not empty 6: Find the BS i? = argmaxi?Wj Qi 7: Connect to the i? BS 8: End if 9: End while probabilityQi andfindavailableBS?swithQi aboveapredefinedthreshold?. Amongallavailable BS?s, user j chooses a best BS to connect. 2.4.3 Admission Algorithm According to the handover algorithm proposed before, handover procedure does not always succeed due to low SINR or busy BS. The connect of served users may be dropped. Therefore, the problem of letting users admitted or readmitted to the femtocell network should be addressed. To solve this problem, we present an admission algorithm in table 2.3. It is similar to the proposed handover algorithm expect that the users do not need to break the connect with previous BS. 25 Table 2.4: Simulation Parameters for Cell Association Algorithms Symbol Definition M = 9 The number of femtocells B = 10 MHz Total network bandwidth P0 = 43 dBm Transmit power of the MBS Pi = 31.5 dBm Transmit power of the i-th FBS PL0 = 28 + 35log10(d) Path loss model for MBS PLi = 38.5 + 20log10(d) Path loss model for FBS ?0,?i = 6 dB Shadowing effects for MBS and FBS Nmax = 10 Maximum number of users per BS 2.5 Performance Evaluation We evaluate the performance of the proposed cell association and handover algorithms using MATLAB. In the femtocell network, we randomly and uniformly generate N users in a circle centered at MBS with radius of 5km and randomly placed M FBS in the area. Each point in the following figures is the average of 10 simulation runs. The 95% confidence intervals are plotted for each point. We adopt the similar channel models used in [26].The values of channel gain from the BS?s can be expressed as: 10log10parenleftbig|hi,j(t)|2parenrightbig = ?PLi(t)?ui(t) = ?di?ci log10 [di,j(t)]?ui(t) where di and ci are two constants for path loss model PLi, di,j(t) is the distance from user i to BS j at time t and ui(t) represents shadowing effect which is normally distributed with mean zero and variance ?i. The simulation parameters are listed in table 2.4. For the proposed cell association algorithm, we compare it with the two straightforward schemes discussed in Section 2.3: ? Scheme 1 based on maximizing network capacity: each BS chooses the user with the highest SINR to connect. 26 ? Scheme 2 based on fairness among users: each user connects to the BS from which it can receive the highest SINR. In Fig. 2.2, we examine the impact of the number of users on the total network capacity. We increase N from 20 to 100 with step-size 20, and plot the total network capacity. We find that the total network capacity increases with the number of users because the probability that BS?s choose a user with better SINR to connect becomes higher as the number of users grows larger. As expected, scheme 1 achieves the highest network capacity, while network capacity in scheme 2 is the lowest since the users with poor SINR jeopardize the total network performance by occupying a portion of network bandwidth. The network capacity of the proposed scheme is almost as twice as scheme 2 when the number of users is close to 100. Although the network capacity of the proposed scheme is about one half of that of scheme 1, note that the number of served users in the proposed scheme achieves as Nmax = 10 times as that in scheme 1. 20 30 40 50 60 70 80 90 1000 20 40 60 80 100 120 Number of Users Ne tw ork C ap ac ity Scheme 1 Scheme 2 Proposed scheme Figure 2.2: Total network capacity vs. number of users Then, we adopt Raj Jain?s fairness index to investigate the impact of number of users on fairness among users. Jain?s equation is given by: J(C1,C2,???,CN) = ( summationtextN j=1 Cj) 2 N?summationtextNj=1 C2j (2.11) 27 where Cj is the network throughput for user j. The value of the index ranges from 1/N (worst case) to1(best case). It can be seen from Fig. 2.3 that fairness indexes decrease with the number of users. Scheme 1 has the lowest fairness index since it only serves at most M + 1 users. However, scheme 2 obtains the highest fairness index among three schemes because every user in scheme 2 has chance to connect to BS. Although the proposed scheme is not as fair as scheme 2, their fairness indexes are very close when the number of users is around 20. Next, we evaluate the 20 30 40 50 60 70 80 90 1000 0.05 0.1 0.15 0.2 0.25 Number of Users Fa irn es s Scheme 1 Scheme 2 Proposed scheme Figure 2.3: Fairness vs. number of users 20 30 40 50 60 70 80 90 1000 10 20 30 40 50 60 70 Number of Users Av era ge N um be r o f H an do ve rs Heuristic ProposedScheme Figure 2.4: Average number of handovers vs. number of users performance of our proposed handover algorithm by applying random walk model to each user. 28 2 3 4 5 6 7 8 9 100 10 20 30 40 50 60 70 Maximum Allowed Number of Users per BS Av era ge N um be r o f H an do ve rs Heuristic ProposedScheme Figure 2.5: Average number of handovers vs. Nmax Bothvelocityanddirectionofmobileusersareuniformlydistributedwithin[0,8.3]m/sand[0,2?], respectively. Since we do not find any similar schemes in the literature, we compare the proposed scheme with a heuristic scheme: Once the average SINR ?i,j falls below threshold ?i2, user j will choose a best available BS to connect. In Fig. 2.4, we show the impact of number of users on the average number of handovers. We increaseN from 20 to 100 with step-size 20. We find that when the number of users is less than 60, the average number of handovers in the heuristic scheme grows larger with the number of users. It is due to the fact that the more users, the more frequently handovers take place. Once the number of users gets beyond 60, the average number of handovers decreases because the probability of finding available BS gets smaller. However, the average number of handovers in our proposed scheme is much lower than the that of heuristic scheme and decreases slowly with the number of users. Finally, we examine the impact of maximum allowed number of user per BS on the average number of handovers in Fig. 2.5. We increase Nmax from 2 to 10 with step-size 2. When Nmax is below 4, the average number of handovers is close to 0 for both heuristic and proposed scheme because all BS are busy and users are not allowed to connect to the new BS. Beyond this critical 29 point, the average number of handovers in proposed scheme is significantly reduced compared with heuristic scheme. 2.6 Conclusion In this chapter, we investigated the problem of cell association and handover management in femtocell networks consisting of an MBS and multiple FBS?s. We first proposed a cell association algorithm with the objective of seeking a trade-off point between network capacity and fairness. Basedonthisalgorithm, wepresentedahandoveralgorithmformobileusers. Bothcellassociation and handover algorithm were evaluated with simulations. The handover algorithm was shown to outperform a heuristic scheme with considerable gains. 30 Chapter 3 Cell load balancing Policies in Femtocell Networks 3.1 Introduction The capacity of wireless network is significantly constrained by interference due to the broad- cast nature of wireless communication. Mobile users at the periphery of cellular networks require considerably high transmit power to compensate channel fading, which in return augments the in- terference to other users and degrades networks capacity. Femtocells provide an effective solution to address this problem by reducing wireless transmission distance and bringing base station (BS) closer to mobile users [8]. A femtocell, as shown in Fig. 3.1, is a relatively small cellular network with a femtocell base station (FBS) which is usually deployed in places where the signal reception from macro base station (MBS) is weak due to long distance or obstacles. Femtocell base stations is typically the size of a residential gateway or smaller and connect to the service providers network via broadband such as digital subscriber line (DSL) or cable, and typically supports only a few users. FBS is designed to offload the traffic on MBS and serve approved users within its coverage. Due to shortened wireless transmission distance, femtocell is shown very effective in reducing transmit power and boosting signal-to-interference-plus-noise ratio (SINR), which lead to prolonging the battery life of mobile devices and improving network coverage as well as network capacity [3]. Femtocells have gained a lot of attention from both academia and industry in the recent past. Femtocell research has been launched by a huge amount of universities and institutions. Three largest cellular network operators in United States (AT&T, Sprint and Verizon) have offered com- mercial femtocell products and service recently. Although the potential of femtocells is highly attractive and promising, a largely wide range of problems including both technical and economic issues have not been addressed yet. The study in [3] provides a comprehensive discussion of the 31 Internet Femtocell Base Station Macrocell Base Station Figure 3.1: Femtocell Networks challenging technical issues in femtocell networks which cover synchronization, cell association, network organization, and quality of service (QoS) provisioning. Unlike MBSwhoseplacementisplannedbyoperators, FBS?sare randomlyplacedbyusers in most cases. A FBS might locate in where user density is much high and with an inappropriate cell associationstrategy, thisFBShavetoprovideservicetoallusersinitscoveragewhichleadstovery high load for this FBS and high service latency for users. Load balancing between neighboring BS?s or between FBS and MBS should be considered in femtocell networks. Load balancing problem is more prominent in femtocell networks due to the unreliability of FBS. FBS operation might be interrupted by users who have physical control of it; FBS may experience power down; or any other fault happen in FBS. Then all the users in this FBS will recognize the disconnection of services and will be associated with neighboring BS?s. As shown in Fig. 3.2, FBS 1 breaks down and thus all its traffic goes to MBS. How to associate these users with neighboring BS?s without introducing a load burst on one BS is a load balancing problem. Cell association after FBS faulty during operation can be consider as an on-line load balancing problem. In this chapter, we investigate the problem of cell association and service scheduling in femto- cell networks. Our objectives include minimizing the total service time of the BS and minimizing the average waiting time of the user. 32 text Internet FBS 1 MBS Figure 3.2: Femtocell Networks with a faulty BS We consider one MBS with multiple FBS?s and mobile users located in the coverage of the MBS. Users submit their requests to BS?s for data downloading. We assume that each user is allowed to connect to either the MBS or a FBS. We further assume that BS?s cannot deal with those requests simultaneously and they have to send data packet to mobile users one by one. We first provide a sequential fixing algorithm to address cell association problem. Although it achieves the bestperformance,itscomplexityisveryhigh. Toreducethecomputationalcomplexity,wepropose approximation algorithms with proven bound. These centralized algorithms need to update the channel information frequently. We also present a randomized algorithm which allows users to pick a BS to connect from a reduced list randomly. Once the list is generated by randomized algorithm, no information exchange is required among users. Besides, we provide an optimal scheme for service scheduling problem. The remainder of this chapter is organized as follows. The related work is discussed in Sec- tion 3.2. We present the system model in Section 3.3. Cell Association problem formulation and solutions are presented in Section 3.4. The problem of scheduling the service order on the BS to minimize the average waiting time is discussed in 3.5. The proposed algorithm are evaluated in Section3.6. Allthreeproposedalgorithmswereevaluatedinbothopenandclosedaccessschemes. Section 3.7 concludes this chapter. 33 3.2 Related Work Femtocells have been acknowledged as an effective solution to next generation wireless com- munication. [8] and [3] provided a comprehensive discussion of technical issues, regulatory con- cerns and economic incentives in femtocell networks. Since FBS?s share the same spectrum with MBS, many research efforts have been made on interference mitigation by assigning users to proper orthogonal channels [31]. The shortcomings of open, closed and hybrid access mecha- nisms were discussed in [23]. [24] introduced a stochastic geometric model to derive the success probability for MBS?s and FBS?s in both open and access scenarios. In recent years, there are increasing number of papers on cell association or cell selection in different scenarios. [25] proposed a learning-based cell selection method for an open access fem- tocell network. The authors in [32] described new paradigms of addressing the problems of cell association in heterogeneous networks with the help of third-party backhaul connections. Their simple and lightweight methodologies and algorithms incur very low overhead in signaling. They focus on femtocell networks with closed subscriber group (CSG) (e.g. each user can only associate with its own femtocell). [33] formulated a convex optimization problem for cell association and proposed a dynamic range extension algorithm to maximize the minimum rate of the user on the downlink of heterogeneous networks. They do not directly optimize the load balancing in Hetero- geneous Network (HetNet) but rather they focus on the sum rate and min rat. [34] proposed an offline optimal algorithm for load balancing achieving the network-wide proportional fairness in multi-cell networks. They consider partial frequency reuse (PFR) jointly with load-balancing in a multicell network to achieve network-wide proportional fairness. Online practical algorithm was also proposed and expected throughput is taken as the decision making metric. On-line assign- ments when users arrive one-by-one was also studied and competitive ratio analysis in [35] show that any deterministic on-line algorithms can achieve a competitive ratio of logn. [9] presented a cell association and access control scheme to maximize network capacity while achieving fairness among users. [36] provided an analytical framework for evaluating 34 outage probability and spectral efficiency with flexible cell association in heterogeneous cellu- lar networks. [37] provided an analysis of downlink SINR distribution in heterogeneous networks with biased cell association. A theoretical framework for distributed user association and cell load balancing under spatially heterogeneous traffic distribution was presented in [38]. A distributed ?-optimal algorithm is proposed and it supports different load-balancing objectives, which include rate-optimal, throughput-optimal, delay-optimal, and load-equalizing, as ? get different value. However, most of femtocell research was focused on offloading MBS traffic and improv- ing network capacity with FBS?s. In the following sections, we propose several cell association schemes with the objectives of minimizing the service latency in femtocell networks. 3.3 System Model We consider a femtocell network with M base stations: one MBS (indexed 1) and M ?1 FBS?s (indexed from 2 to M). M?1 FBS?s are connected to the MBS via broadband wired line. There are N mobile users randomly located within the coverage of the femtocell network. We assume the MBS and M ?1 FBS?s are well synchronized and they share the same bandwidth. Each user requests a fixed length data packet from one of the M BS?s. Let Pm be the transmit power of the m-th BS and Gm,n be the power gain between the BS and the n-th user. According to Shannon Capacity theorem, the network capacity of user n connected to BS m is given by Cm,n = Blog2 parenleftbigg 1 + Gm,nPm?2 +I m,n parenrightbigg (3.1) 35 where B is network bandwidth, ?2 is noise power density, and Im,n is the interference from other BS?s. It can be obtained by Im,n = summationdisplay i/?m Gi,nPi = In?Gm,nPm = Msummationdisplay i=1 Gi,nPi?Gm,nPm (3.2) where In is the sum of the interference from all BS?s to the n-th user. It does not depend on which BS user n is connected to and is a constant for each user. By substitute Ii,j in (3.1) with (3.2), we have Cm,n = Blog2 parenleftbigg 1 + Gm,nPm?2 +I n?Gm,nPm parenrightbigg = Blog2 parenleftbigg ?2 +I n ?2 +In?Gm,nPm parenrightbigg = Blog2 parenleftbigg 1 1??m,n parenrightbigg (3.3) where ?m,n is signal to interference plus noise ratio (SINR), the same ratio of the received power in In. 3.3.1 Service Time We assume eachuser requests a fixedlength data packetfrom one of theM BS?s. For simplic- ity, we further assume all packets have the same length, denoted as L. Then the processing/service time of BS m for user n is given by tm,n = LC m,n . (3.4) The service time depends on the link capacity Cm,n derived by (3.3). Note that the service time defined here is actually the delivery time, in which the propagation delay is ignored, to finish the transmission of the data packet requested by users. 36 3.3.2 Femtocell Access Control The type of access control for femtocells can be classified into two categories: closed access and open access. Open-access scheme allows all mobile users of an operator to connect; in this case, femtocell is often deployed directly by an operator to provide coverage in an area where there is a coverage hole. In closed-access mode, only a specific user group can get service [11]. Closed access method has been shown to decrease system throughput by 15%, however, surveys suggest that closed Access mode is users favorite option [12]. These two access modes are both considered in this chapter. We denoteAm as the set of users that can be connected to BS m andBn as the set of BS?s that user n can be connected to. For open access, we haveAm ={1,???,N}andBn ={1,???,M}. 3.4 Cell Association Problem Formulation and Proposed Schemes As discussed before, we divide the problem into two steps. In the first step, we assign each user to one of the M BS?s with the objective of minimizing the total service time on each BS. In the second step, we schedule the service order on the BS to minimize the average waiting time of users. The cell association problem can be formulated as a load balancing problem. We are given a set of N users and a set of M BS?s. Each user n has a service time tm,n if it is connected to BS m. We can letCm denote the set of users assigned to BS m. The BS m needs to take a total time of Tm = summationdisplay n?Cm tm,n, (3.5) to transmit all packets. We seek to minimize the maximum load on any BS, T = maxm Tm. It is similar with a load balancing problem. For well-known load balancing problem, the service time for each user is identical to all BS?s. However, our scheduling problem is more complicated because its solution depends on not only user n, but also the BS m. This scheduling problem is 37 easily seen to be NP-hard by noting that, when all tm,n?s are the same on any BS, the problem becomes a known NP-hard load balancing problem. 3.4.1 Sequential Fixing Algorithm To solve the problem above, we first define xm,n as an indicator variable where it is 1 if user n is connected to BS m and otherwise 0 xm,n = ?? ? ?? 1, if user n is connected to BS m 0, otherwise. (3.6) Then we reformulate the problem as follows: min T (3.7) summationtext m xm,n = 1 for all users summationtext n tm,nxm,n?T for all BS?s xm,n?{0,1} for all n?Am xm,n = 0 for all n /?Am Let MILP denote the problem defined in (3.7). Note that the MILP problem is not a simple binary integer linear programming problem due to the variable T. In the MILP problem, all variables except T are binary variables. Thus, the MILP problem is a mixed integer linear programming problem, which is usually NP-hard. It gives the same conclusion as we discuss before. The original MILP is next relaxed to a linear programming (LP) problem, denoted as RLP. We relax binary variable xm,n?s to real number between 0 and 1, and allow xm,n?s to take fractional 38 Table 3.1: Sequential Fixing for Cell Association 1: InitializeN ={1,???,N} 2: Relax xm,n to real number 3: WhileN is not empty 4: Solve the RLP problem 5: Find xm?,n? that is the closest to integer xm?,n? = minn?Am?N{xm,n,1?xm,n} 6: Set xm?,n? to the closest integer 7: If xm?,n? is set to 1 8: Set xm,n? = 0 for all mnegationslash= m? 9: Remove n? fromN 10: Else 11: Remove n? from Am? 12: End if 13: End while values. Then, the MILP problem can be converted into RLP as follows: min T (3.8) summationtext m xm,n = 1 for all users summationtext n tm,nxm,n?T for all BS?s xm,n?0 for all n?Am xm,n = 0 for all n /?Am Since the sum of xm,n?s is already upper bounded by 1 in the first constraint, we remove the upper bounds of xm,n?s in the third constraint. Obviously, the solution to the RLP problem is a lower bound of the original MILP problem because it is obtained by expanding the solution space. Unfortunately, it is usually an infeasible solution to the original MILP problem. Therefore, we develop a sequential fixing (SF) algorithm [39] to find a feasible solution to the MILP problem which is presented in table 3.1. In steps 3?13, we solve the RLP problem iteratively. During each iteration, we find thexm?,n? whichhastheminimumvaluefor(xm,n?0)or(1?xm,n)amongallfractionalxm.n?sandrounditup 39 or down to the nearest integer. Setting xm?,n? to 1 means user n? is connected to BS m?. Therefore, user n? cannot be connected to any other BS?s and the rest of xm,n??s are set to 0. This procedure repeats until all xm,n?s are fixed. The complexity of SF depends on the specific LP algorithm. With Karmarkar?s algorithm, the worst-case polynomial bound for solving LP problems is O(nv3.5Lb) where nv is the number of variables and Lb is the number of bits of input to the algorithm. Then, we have the following lemma for the complexity of sequential fixing algorithm. Lemma 2. The computational complexity of sequential fixing algorithm is O((MN)4.5Lb). Proof. The number of binary variables in MILP is at most MN, so the number of loops in se- quential fixing problem is at most MN. In each iteration, the complexities of step 4, 5 and the rest are O((MN)3.5Lb), O(MN) and O(1), respectively. Besides, in each iteration, the number of variables is reduced by 1. Therefore, the complexity of sequential fixing algorithm is given by MNsummationdisplay i=1 O((MN?i+ 1)3.5Lb) = MNsummationdisplay i=1 O(i3.5Lb) = O((MN)4.5Lb). (3.9) Therefore, the complexity of sequential fixing algorithm is bounded by O((MN)4.5Lb). 3.4.2 Approximation Algorithm Although sequential fixing algorithm can solve the MILP problem within polynomial time, its complexity is still too high even for small femtocell networks. In this section, we propose an approximation algorithm with low complexity to address the MILP problem. Before we introduce the approximation algorithm, we first give the lemma below. Lemma 3. The optimal solution, denoted by T?, to the MILP problem is lower bounded by T? ? 1 M summationtextN n=1 tn where tn = minm?Bn tm,n. 40 Proof. Given the optimal allocationC?m for BS m, we have T? = maxmsummationtextn?C? m tm,n. Then we have T??maxm summationdisplay n?C?m tn? 1M Msummationdisplay m=1 summationdisplay n?C?m tn = 1M Nsummationdisplay n=1 tn. The first inequality is due to the definition of tn. The second inequality is due to the fact that the maximum value is always greater than mean value. The last equality is because all users have to be connected to one of the BS?s and?Mm=1C?m is the set of all users. Since the maximum total service time is at least the service time of only one user, intuitively we have the following lemma. Lemma 4. The optimal solution, denoted by T?, to the MILP problem is lower bounded by T? ? maxtn where tn = minm?Bn tm,n. These lemmas will be used in analyzing the approximation ratio in our algorithms, which are presented in following subsections. 3.4.3 Rounding Approximation Algorithm To ensure required SINR for each user, in real femtocell network, not all FBS?s should be in Bn (Am will be updated according to the change ofBn). Thus, here we use threshold ? to obtain the subsets ofAm andBn. B?n =Bn?({m|tm,nt n ??}) A?m ={n|m?B?n} (3.10) Only limited number of FBS?s should be taken into consideration of any user. After we adopt this threshold, not only users? SINR requirements will be satisfied, computational complexity will also decrease. 41 Thisfollowingrelaxedlinearprogrammingproblemcanbesolvedbyanylinearprogramming solver. min T (3.11) summationtext m xm,n = 1 for all users summationtext n tm,nxm,n?T for all BS?s xm,n?0 for all n?A?m xm,n = 0 for all n /?A?m We denote the solution obtained by solving this RLP program by T. Since x-variables are allowed to take fractional values, we have T ?T?. Without sequentially fixing these fractional values, we adopt a rounding method in [40] to get a feasible solution for the MILP problem. In this rounding method, a bipartite graph is constructed according to the solutions of RLP. The bipartite graph is constructed as a undirected bipartite graph G(A?B,E). In the disjoint setA, each node represents a user n, while the other disjoint setB consists of BS nodes. We create km =?summationtextn xm,n?nodes inBfor BS m and these node are denoted by {bm,1,bm,2,???,bm,k,???,bm,km}. The edges are determined in the following way. For BS m, we sort the users in the order of non-increasing service time tm,n and the users are renamed {u1,u2,???}. Let Xm,uj = summationtextji=1 xm,ui. For each BS, we divide the users associated to it into km groups G. User uj is included into k-th group (1 ? k ? km) if k?1 < Xm,uj ? k or k?1?Xm,uj?1 < k. If a user uj are included into two groups, the association x-variables need to adjust them, such that x?bm,k,uj = Xm,uj ?k +1 and x?bm,k?1,uj = xm,uj ?x?bm,k,uj. Then we add edges between BS node bm,k and all the user nodes in k-th group. Till now, the bipartite graph is all set up and we find a maximal matchingMfrom each user to nodes in the other partite. This maximal matchingMindicates a feasible solution for MILP problem: for each edge (n,bm,k) in M, we associate user n to BS m. 42 Let T(bm,k) denote the total service time on node bm,k before matching and T?(bm,k) denote the total service time on node bm,k obtained by this rounding method. We have the following lemma. Lemma 5. For each node bm,k, where km?k > 1, we have T(bm,k?1) ?T?(bm,k). Proof. The first important observation is that the minimum service time in (k?1)-th group will be always no less that the maximum service time in k-th group, because we sort the users in non- increasing service time. And according the above graph construction, for any k < km, we havesummationtexti?Gk x?bm,k,ui = 1; for k = km,summationtexti?Gk x?bm,k,ui ?1. T?(bm,k) will be no greater than the maximum service time in k-th group and will thus be no greaterthantheminimumservicetimein(k?1)-thgroup,whichislessthansummationtexti?Gk?1 x?bm,k?1,uitm,ui. Since T(bm,k?1) = summationtexti?Gk?1 x?bm,k?1,uitm,ui, consequently we have the conclusion that T(bm,k?1) ? T?(bm,k). Now we show that the solution produced by this algorithm is at most ? + 1 greater than the optimal solution. In other words, this algorithms produces a solution with ?+ 1-approximation of optimal solution. Lemma 6. The approximation algorithm based on linear programming ensures a solution with ?+ 1-approximation of optimal solution. Proof. For each BS m, we create km nodes for it and there are corresponding km groups of user nodes adjacent to them . Thus the total service time issummationtextkmk=1 T?(bm,k). Consider a BS m, according to Lemma 5, for km?k > 1, T(bm,k?1) ?T?(bm,k). Thus we have kmsummationdisplay k=2 T?(bm,k) ? km?1summationdisplay k=1 T(bm,k) ? kmsummationdisplay k=1 T(bm,k) ?T In the first group, the maximum load will be the maximum service time of users associated to m. Combining Lemma 4, we have T?(bm,1) ??T?. Then, the total service time on any BS computed by ourassociationalgorithmwillbesummationtextkmk=1 T?(bm,k) ??T?+T ?(?+1)T?. Ourproofiscomplete. 43 Table 3.2: Greedy Approximation Algorithm for Cell Association 1: Initialize Tm = 0 andCm = ? for all BS?s 2: Set the user setN ={1,???,N} 3: WhileN is not empty 4: Find the BS m? that has the minimum Tm m? = argminm?(?n?NBn) Tm 5: Find the user n? that has the minimum tm?,n n? = argminn?{Am??N} tm?,n 6: SetCm? =Cm??{n?} 7: Set Tm? = Tm? +tm?,n? 8: Set ?m?,n? = tm?,n?t n?9: Remove n? fromN 10: End while The complexity to compute a matching isO(VE), whereV andE is the number of nodes and edges,respectively. Sinceweonlyneedtodomatchingonceandobtaintheassociationrelationship from the matching result, the total computational complexity of this algorithm is O((MN)3.5Lb), which is better than the sequential fixing algorithm. 3.4.4 Greedy Approximation Algorithm In this section, we present a low computational complexity approximation algorithm. In this algorithm, we greedy pick the BS with the minimum load and assign to this BS a user whose completion time on this BS is small. The approximation algorithm is presented in table 3.2. We define a parameter ? to estimation the distance between optimal solution and the solution to approximation algorithm. In step 4, we find the candidate BS which is possible for users to connect and has the minimum Tm. Then we pick the user who has the minimum Tm,n on that BS. Obviously, the computational complexity of the approximation algorithm is O(MN), which is much lower than that of sequential fixing algorithm. Lemma 7. The solution obtained from the approximation algorithm, denoted by T, is upper bounded by ?M summationtextNn=1 tn +?T? where ? = max{m,n} ?m,n and tn = minm?Bn tm,n. 44 Proof. We first consider open access scheme and each user can be connected to any one of the BS?s. In the l-th iteration, we choose the BS with the minimum Tm in step 4. Thus we have Tl?1m? ? 1M Msummationdisplay m=1 Tl?1m = 1M Msummationdisplay m=1 summationdisplay n?Cl?1m tm,n = 1M Msummationdisplay m=1 summationdisplay n?Cl?1m ?m,ntn? ? l?1 M Msummationdisplay m=1 summationdisplay n?Cl?1m tn where ?l?1 = max{m,n?Cl?1m } ?m,n. Note thatCl?1m is set of users that have been assigned to BS m in the (l?1)-th iteration. In step 5, we pick user n? and let user n? connect to BS m?. Since ?l will always be greater than ?l?1 and according to Lemma 4, we have Tl?1m? +tm?,n? ? ? l M Msummationdisplay m=1 summationdisplay n?Clm tn +?lt?n. The algorithm stops after N iterations. Since Tl+1 = max{Tl,Tlm? +tm?,n?}and T0 = 0, we draw the conclusion that T = TN+1 = max{TN,TNm? +tm?,n?} ? ?M Msummationdisplay m=1 summationdisplay n?Cm tn +?T? = ?M Nsummationdisplay n=1 tn +?T?. In the closed access scheme, we can set tm,n to infinity for those BS?s that users cannot be con- nected to. Therefore, we have the same conclusion. Combining Lemma 3 and Lemma 7, we make a conclusion regarding the performance of the approximation algorithm as follows. Lemma 8. The approximation algorithm in table 3.2 produces a solution with 2?-approximation of optimal solution. 45 Proof. The proof is simple and straightforward. T??T ? ?M Nsummationdisplay n=1 tn +?T??2?T? where T? is optimal solution and T is approximation solution. From the Lemma 8, we find that ? is very important to the performance of approximation algorithm. The smaller the ? is, the closer optimal and approximation solutions are. In order to make the approximation solution close to the optimal solution, we only allow users to choose the BS from a subset,Bn of the original BS set. Then we have the subsetB?n andA?m as B?n =Bn?({m|tm,nt n ??}?{1}) A?m ={n|m?B?n} (3.12) where ? is a predefined threshold and{1}is the index of the MBS. ? can also be used to satisfy SINR requirement of users in the femtocell network. The setAm is replaced byA?m accordingly. Therefore the approximation solution is between T? and ??T?. 3.4.5 Randomized Algorithm The previous two centralized algorithms need to update link status frequently to keep the channel information on track. In this section, we introduce a randomized algorithm for cell associ- ation. Each user n chooses a subset ofBn to connect randomly. Once the subsets are determined, no information exchange is required among users. We assume user n is connected to BS m with probability pm,n and the expected service time for user n on each BS is identical. We have pm,ntm,n = Hn ?m?Bn. 46 Since each user has to choose a BS to connect and thus the sum,summationtextm?Bn pm,n = 1 for any user n. Then we have Hn = 1summationtext m?Bn 1/tm,n . (3.13) The expected load on BS m, denoted by Tm, is Tm = E[Tm] = summationdisplay n?Am tm,n?pm,n = summationdisplay n?Am Hn. (3.14) Since users are connected to the BS randomly, our objective becomes to minimize the maximum value of the expected load Tmax: min Tmax = minmax m Tm. (3.15) We can see from equation (3.14) that minimizing Tm is equivalent to reducing the number of users inAm. We divide the randomized algorithm into two phases. In the first phase, we use threshold ? to obtain the subsets ofAm andBn. B?n =Bn?({m|tm,n??}?{1}) A?m ={n|m?B?n} (3.16) Note that the subsetsA?m andB?n are different from those defined in (3.12). ? is the upper bound of the service time tm,n. Thus we have all tm,n?? for all n and n?A?m. Then we have the upper 47 bounds for Hn, Tm and Tmax which are given by Hn = 1summationtext m?B?n 1/tm,n ? 1summationtext m?B?n 1/? = ?|B? n| Tm = summationdisplay n?A?m Hn? |A ? m| minn|B?n|? Tmax = maxm Tm? maxm|A ? m| minn|B?n| ? (3.17) where|A?m|and|B?n|are the sizes of the subsetA?m andB?n, respectively. In the second phase, we would like to further reduce the size ofA?m andB?n. From equation (3.13), we can see that Hn? gets increased when BS m? is removed from the setB?n? and user n? is removed from the setA?m? simultaneously. The amount of increase, denoted by ?m?,n?, is given by ?m?,n? (3.18) = 1summationtext m?B?n 1/tm,n?1/tm?,n? ? 1summationtext m?B?n 1/tm,n = 1/tm?,n?(summationtext m?B?n 1/tm,n?1/tm?,n?)( summationtext m?B?n 1/tm,n) For those BS?s in the set{m|m?B?n?,mnegationslash= m?}, theirTm?s become larger when BSm? is removed from the setB?n? and user n? is removed from the setA?m?. On the other hand, Tm? is reduced by Hm?,n? according to the equation (3.14). Our proposed algorithm is described in table 3.3. In step 2, we collect the users which has more than one BS on their BS listB?n. Then from step 5 to step 18, we find the BS m? with the largest Tm? and compute the possible maximum load Tmaxm?,n on BS?s for all users that might be connected to the BS m? assumed user n is removed fromA??m?. In step 19, we pick the user n? with the minimum Tmaxm?,n value. If the value is less than the original Tm?, we remove the BS-user pair{m?,n?}from the setsA??m? andB??n?. Otherwise, the algorithm is terminated. Therefore, once the algorithm is carried out, the setA??m? andB??n? are the subsets of A?m? andB?n?, respectively. Since the complexity of algorithm from step 5 to step 18 is O(MN) in the worst case, the complexity of whole randomized algorithm is O(M?N2). The maximum 48 expected service time can be further bounded by Tmax? maxm|A ?? m| minn|B??n| ?maxn maxm?B??n tm,n. (3.19) Table 3.3: Randomized Algorithm for Cell Association 1: InitializeA??m =A?m,B??n =B?n 2: Set the user setN ={n||B??n|> 1} 3: Compute Tm according to (3.14) 4: WhileN is not empty 5: Find the BS m? with m? = argmaxm Tm 6: For user n in (A??m??N) 7: Compute ?m?,n according to (3.18) 8: For m = 1 to M 9: If m = m? 10: Set T?m? = Tm??Hn 11: Else if m in{m|m?B??n} 12: Set T?m = Tm + ?m?,n 13: Else 14: Set T?m = Tm 15: End if 16: End for 17: Set Tmaxm?,n = maxm T?m 18: End for 19: Find user n? with n? = argminn Tmaxm?,n 20: If Tm? ?Tmaxm?,n? 21: Remove m? fromB??n? and n? fromA??m? 22: Update all Tm?s 23: If|B??n?|= 1 24: Remove n? fromN 25: End if 26: Else 27: The algorithm is terminated 28: End if 29: End while 49 3.5 Service Scheduling Since we assume the bandwidth B is fully utilized when the packet from one user is being transmitted, we have to determine the order of users that are served on the same BS. Here we consider a certain BS which K users are connected to. The service time of each user is denoted by {t1,???,tK}. If we order the users by its index, the average waiting time is given by Twait = 1K Ksummationdisplay n=1 nsummationdisplay i=1 ti (3.20) To minimize the average waiting time, we have the following lemma. Lemma 9. Given K users with service time from t1 to tK, the average waiting time achieves the minimum when they are sorted in the increasing order of their service time. Proof. First we assume the users are sorted according to their service time and the ordered service time is denoted by t?1,???,t?K. We further assume there are two ordered users i and j where 1?i < j ?K. Thus we have t?i ?t?j. If the positions of i and j are swapped, it is obvious that the waiting time of users from 1 to i?1 and from j to K does not change and keeps the same values. However, the awaiting time for each user from i to j?1 is increased by t?j?t?i. Therefore we conclude that the average waiting time is the least when the users are sorted in the increasing order of the service time. 3.6 Performance Evaluation In this section, we evaluate the performance of the proposed cell association and service scheduling algorithms using MATLAB. The point in the presented figures is the average of 10 simulation runs and the 95% confidence intervals are plotted for each point. The channel models in [26] are adopted in our simulation. The channel gain (in dB) from the BS?s to users can be 50 Table 3.4: Simulation Parameters for Cell Load Balancing Algorithms Paramter Value The number of BS?s 6 Total network bandwidth 10 MHz Transmit power of the MBS 43 dBm Transmit power of the FBS 31.5 dBm Path loss model for MBS 28 + 35log10(d) Path loss model for FBS 38.5 + 20log10(d) Shadowing effects 6 dB Packet length 1 KBytes 30 40 50 60 70 80 0.5 1 1.5 2 2.5 3 Number of Users Maximum Total Service Time(ms) Greedy Approximation Sequential Fixing Randomized Algorithm Selfish User Rounding Approximation Low Bound Figure 3.3: Total service time vs. number of users: Open Access expressed as: 10log(Gm,n) =?PLm(dm,n)?um (3.21) where dm,n is the distance from BS m to user n, and um is shadowing effect which is normally distributed with zero mean and variance ?m. The simulation parameters are presented in table 3.4. We present simulation results for the following two scenarios: ? Open access scheme ? Closed access scheme 51 30 40 50 60 70 80100 200 300 400 500 600 700 800 Number of Users Average Waiting time(us) Greedy Approximation Sequential Fixing Randomized Algorithm Selfish User Rounding Approximation Figure 3.4: Average waiting time vs. number of users: Open Access 30 40 50 60 70 80 0.16 0.18 0.2 0.22 0.24 Number of Users Fairness Greedy Approximation Sequential Fixing Randomized Algorithm Selfish User Rounding Approximation Figure 3.5: Fairness vs. number of users: Open Access 52 Table 3.5: Simulation Running Time Open Access (s) No. of users 30 40 50 60 70 80 Greedy Approx. 0.0244 0.0337 0.0243 0.0300 0.0257 0.0380 Sequential Fixing 16.5317 24.0203 30.8086 48.7127 47.8417 50.6541 Randomized Algorithm 0.0300 0.0479 0.0769 0.1358 0.1321 0.1506 Selfish User Scheme 0.0345 0.0353 0.0346 0.0354 0.0359 0.0258 Rounding Approx. 0.1332 0.1479 0.1597 0.1679 0.1761 0.2129 30 40 50 60 70 80 1 2 3 4 5 6 7 Number of Users Maximum Total Service Time(ms) Greedy Approximation Sequential Fixing Randomized Algorithm Selfish User Rounding Approximation Low Bound Figure 3.6: Total service time vs. number of users: Close Access For comparison purpose, we also developed and simulated the following selfish scheme and com- pared it with the proposed schemes. For the selfish scheme, every user only chooses the best BS to connect. 3.6.1 Case of Open Access In the first scenario, there are M = 6 BS?s, i.e., one MBS and five FBS?s. The number of users ranges from 30 to 80 with step size 10. They are randomly located in the coverage of the MBS. Each user is allowed to be connected to one of the BS?s. We first examine the impact of the number of users on total service time. We plot the max- imum total service time for the five algorithms along with the low bound found by relaxing x- variables to real values in Fig. 3.3. As expected, the more users, the more total service time on BS?s. Except for the low bound obtained by solving relaxed LP, sequential fixing algorithm 53 30 40 50 60 70 80 500 1000 1500 2000 2500 Number of Users Average Waiting time(us) Greedy Approximation Sequential Fixing Randomized Algorithm Selfish User Rounding Approximation Figure 3.7: Average waiting time vs. number of users: Close Access 30 40 50 60 70 80 0.16 0.17 0.18 0.19 0.2 0.21 Number of Users Fairness Greedy Approximation Sequential Fixing Randomized Algorithm Selfish User Rounding Approximation Figure 3.8: Fairness vs. number of users: Close Access 54 achieves less total service time than other schemes. Rounding approximation algorithms has slight better performance than the greedy approximation algorithm in this respect and these approxima- tion algorithms achieve less load than both randomized algorithm and selfish scheme. We also observe that beyond 50 users, all proposed algorithms have less service time than simple selfish scheme. In Fig. 3.4, we investigate the impact of the number of users on average waiting time. Intu- itively, larger the number of users, more is the average waiting time per user. We can see from the figure that, expect for rounding approximation algorithm, the proposed algorithms outperform the selfish scheme. The average waiting time obtain by greedy approximation algorithm is very close to that by sequential fixing algorithm. Then, we adopt Raj Jain?s fairness index to investigate the impact of number of users on fairness among users. Jain?s equation is given by [9]: J(C1,C2,???,CN) = ( summationtextN n=1 Cn) 2 N?summationtextNn=1 C2n (3.22) where Cn is the network throughput for user n. The value of the index ranges from 1/N (worst case) to1(best case). It can be seen from Fig. 3.5 that fairness indexes decrease with the number of users. We notice that, selfish scheme and randomized algorithm achieve better fairness than other three schemes. Thus we can see from Fig. 3.3 and Fig. 3.5 that, from operator?s viewpoint, selfish scheme and randomized scheme are not preferred since they produce less balanced load on BS?s; while from users?s viewpoint these two schemes are better due to their fairness. We list the running time of five schemes in Table. 3.5. It can be seen that the running time in- crease as the number of users. We also find that the selfish scheme always has the smallest running time, while sequential fixing requires the largest running time. Although rounding approximation as seen above achieves less maximum load on BS?s, its running time is greater than the greedy 55 Table 3.6: Simulation Running Time Close Access (s) No. of users 30 40 50 60 70 80 Greedy Approx. 0.0029 0.0043 0.0047 0.0046 0.0069 0.0064 Sequential Fixing 0.8616 1.1296 1.5078 1.8453 2.3058 2.6798 Randomized Algorithm 0.0114 0.0153 0.0210 0.0303 0.0367 0.0492 Selfish User Scheme 0.0014 0.0015 0.0018 0.0018 0.0021 0.0031 Rounding Approx. 0.0287 0.0278 0.0319 0.0339 0.0365 0.0396 approximation scheme. And the greedy approximation algorithm is superior to both sequential fix- ing algorithm and randomized algorithm in running time. This result also justifies the complexity analysis for the proposed schemes. 3.6.2 Case of Closed Access We next investigate the second scenario with closed access scheme. Each BS maintains a user list and allows the users only on its list to connect. Especially for MBS, its user list contains all users cannot reject the connection request from any user. We increase the number of users from 30 to 80 with step size 10. In Fig. 3.6, we investigate the impact of the number of users on total service time. Intuitively, the total service time increases as the number of users. However, we find that it also depend on the user list on each FBS. It is because we choose the user set randomly for each BS. Moreover, after we set the SINR threshold, the user list on each FBS is pretty small and that is why all proposed algorithms achieve close performance in closed access scenario. The performance of all proposed algorithms is better than that of selfish scheme. We next show the impact of the number of the number of users on average waiting time in Fig. 3.7. It is similar to the open access that, all proposed algorithms are superior to the selfish scheme, expect for rounding approximation algorithm. Due to the randomness of user lists on BS?s, the confidential intervals are much larger than those in open access. 56 Then we plot the fairness in Fig 3.8. Randomized algorithm, although not better than selfish scheme, achieve better performance in fairness than other proposed schemes. Rounding approxi- mation, despite of its good performance in maximum total service time, is not preferable to users in the respect of average waiting time and user fairness. Finally, we list the running time of five schemes in Table. 3.6. As expected, the running time increases as the number of users. Compared with Table. 3.5, closed access scheme requires less running time than open access scheme, because in open access the user list include more users. 3.7 Conclusion In this chapter, we investigated the problem of cell association and service scheduling in fem- tocell networks consisting of one MBS and multiple FBS?s. The first sequential fixing algorithm achieves the best performance in total service time but it requires relatively high complexity to ad- dress cell association problem. Then we presented approximation algorithms with low complexity and proven bounds. We also proposed a new randomized algorithm which requires the least infor- mation exchange among users. Apart from load balancing problem, we also addressed the service scheduling problem and provided an optimal solution to it. All proposed algorithms were evalu- ated in both open and closed access schemes. They were shown to outperform a heuristic selfish scheme with considerable gains. 57 Chapter 4 Weather turbulence mitigation through topology control in FSO Networks 4.1 Introduction Drawing increasing attention, free space optical networks are considered as an important al- ternative to the radio frequency (RF) systems as the backbone solution for future data-intensive networks. This appeal is primarily due to their high optical fiber-like data rates, resistance to elec- tromagnetic interference, and security among other advantages. There are many research opportu- nities and also challenges in different aspects of FSO networks, such as pointing, acquisition and tracking (PAT), weather/environment issue, channel randomness, and topology control [21]. Be- cause an FSO transmitter is highly directional, the performance of the FSO networks is dependent on the reliability of a line-of-sight (LOS) path. Atmospheric obstructions (e.g., due to the weather turbulence or flying objects) can degrade the link performance considerably. The network must, therefore, be capable of control and reconfiguration of its topology. In topology control, bootstrap- ping and reconfiguration during operation are two important aspects, both of which are considered in this chapter. In designing the bootstrapping algorithm for FSO networks, the difficulty lies in the distributedformationoftopologywitheverynodeonlyknowingdirectlyconnectedneighborinfor- mation. Moreover, thereareonlyalimitednumberoftransceiversinonebasestation, whichmakes this problem even more challenging; because now the problem becomes Degree Constrained Min- imum Spanning Tree Problem (DCMST). The DCMST problem can be categorized as Euclidean Problem and non-Euclidean Problem, e.g., the random table. In Euclidean problems, the edge weights are said to obey the triangle inequality; but in non-Euclidean problems, the edge weights do not necessarily obey the triangle inequality [41]. Non-Euclidean problems were found to be far less tractable than Euclidean problems. The problem of building a spanning tree in FSO network is a random table problem. Moreover, even in non-weighted graphs, building Degree Constrained 58 Spanning Tree (DCST) is still NP-hard. After bootstrapping the FSO network, base stations can exchange information about their neighbors and hence a centralized algorithm for reconfiguration can be applied. A centralized algorithm will consume less computation time, which is desirable in linkfailuresituations. IfoneorseverallinksfailinFSOnetworks,thealgorithmshouldreconfigure the topology quickly to avoid partitioning or degradation. In this chapter, the objective is to maximize the edge weight and the algebraic connectivity of spanning tree, which result in higher robustness in topology of FSO networks. Edge weight repre- sents FSO link reliability. Algebraic connectivity, as defined in spectral graph theory, is the second smallest eigenvalue of the Laplacian matrix L associated with a graph [42]. It provides a good measure to determine how well the spanning tree is connected [43]. We develop a topology con- trol scheme when not only the number of transceivers on each base station is limited but also when these numbers are different on different base stations. Both of our bootstrapping and reconfiguring algorithms are shown to generate spanning tree with high average edge weight and algebraic con- nectivity. In addition, by exploiting the knowledge of topology history, our reconfiguring scheme requires much less computation time in case of link failure. The remainder of this chapter is organized as follows. In Section 4.2 we review some related works on topology control in FSO networks. We formulate the problem using 0-1 integer linear programming (ILP) in Section 4.3. The topology control algorithms and analysis are presented in Section 4.4. Our simulation results and performance analysis are presented in Section 4.5. Section 4.6 concludes this chapter. 4.2 Related Work Several previous works have focused on topology control in FSO networks. Some papers consider bootstrapping FSO networks and others propose reconfiguration schemes. In [44], a bottom-up (BU) algorithm is proposed for bootstrapping FSO networks. BU is a fully distributed approximation algorithm, which constructs a spanning tree with maximal node degree at most one larger than that in the optimal solution. In the algorithm proposed in [44], node ID is assigned 59 arbitrarily but used as an important factor in determining which neighbor to connect with. Another problem, as it is also stated in [44] but not solved, is synchronization problem. In [45], authors propose a hybrid network prototype using free space optical link for data transmission only, and RF link primarily for control signals as well as serving as a backup for data transmission whenever FSO link is unavailable. This scheme of dynamic path reconfiguration is shown to have high performance in terms of reconfiguration time and end-to-end delay. In this chapter, we consider pure FSO network, which means there is no backup RF systems. A heuristic distributed fragment selection and merging (FSM) algorithm [42] is presented to solve bootstrapping and reconfiguring FSO networks. The author formulates the topology creation as building a k-degree constrained spanning tree which means all the nodes in a graph are subject to the same degree constraint k. The proposed approach in [42] requires high computational complexity because of calculating the algebraic connectivity in every round, which makes this algorithm not competitive for fast reconfiguration. In this chapter, a more general case, that is different degree constraints on every single node, will be considered. Similar to [42], we also use algebraic connectivity in this chapter asitprovidesausefulmeasureforconnectivityofgraphs. Theauthorsin [46]proposeacentralized algorithm which aims to design mesh topology with strong connectivity and short diameter with degree bound. The closest neighbor algorithm proposed in this chapter starts with building a DCMST using the primal method. In order to construct a DCMST in polynomial time, many heuristicandexactalgorithmshavebeenproposed,suchasPrimalmethod,Dualmethod,simulated annealing, Lagrangean relaxation and branch and bound method [41]. Several of these algorithms can effectively provide sub-optimal solutions and generate a spanning tree with minimum weight sum. However, these algorithms do not work well in bootstrapping FSO networks, since a base stationwillonlyhave knowledge ofneighboring basestation?s information. Theyalsoarenotgood at reconfiguring the network which requires fast reaction to avoid partitioning or degradation. 60 4.3 System Model and Problem Statement 4.3.1 Model Description We consider network model using FSO technology to have the following characteristics: ? FSO network only consists of base stations equipped with FSO transceivers; ? FSO channel is full duplex; ? FSO transceivers can transmit data over a randomly oriented sector?of degree? (? typically is 2?/9). An edge in topology means a pair of nodes can communicate with each other bi- directionally; ? FSO transceivers have Pointing, Acquisition, and Tracking (PAT) capabilities; ? FSO base stations can use topology discovery to find their neighborhood, and in the begin- ning, base stations can adjust their transmitting power, if necessary. There are several different models for characterizing weather turbulence in FSO network, such as log-normal distribution for weak-to-moderate turbulence, gamma-gamma distribution for modeling moderate-to-strong turbulent channels and other models. We adopt the gamma-gamma model and therefore, focus on topology control under turbulent channel conditions. The gamma- gamma distribution of channel state h is given as [47] f (h) = 2(??) ?+? 2 ?h?(?)?(?) parenleftbiggh ?h parenrightbigg?+? 2 ?1 K??? parenleftBigg 2 radicalbigg ??h?h parenrightBigg (4.1) whereK?(?)isthemodifiedBesselfunctionofthesecondkindoforder?,?(?)istheGammafunc- tion, and ? and ? are parameters which are related to distance, aperture diameter and atmospheric conditions. ?h in this model is a scale parameter, which is related to geometric spread loss and path attenuation and can be calculated with the knowledge of transceiver parameters and atmospheric conditions. 61 Given a threshold of channel state h0 , link reliability is defined as L = ?? h0 2(??)?+?2 ?h?(?)?(?) parenleftbiggh ?h parenrightbigg?+? 2 ?1 K???(2 radicalbigg ??h?h)dh = ???h?(?)?(?) parenleftbigg ??h0?h parenrightbigg??? 2 G3,01,3 parenleftbigg ?? parenleftbiggh 0 ?h parenrightbigg | ??+?21??+? 2 , ??? 2 , ??? 2 parenrightbigg (4.2) Meijer G-function which is a standard built-in function in most of mathematical software pack- ages [47] can be used to solve this integral. Link reliability is an important parameter to measure the channel conditions in FSO networks. Hence, we use it as edge weight in graph. Weight on the edge which is incident on node i and node j is defined as the link reliabilityLij ifLij is larger than a threshold value and zero otherwise; edges with zero weight should not be included in graph in our problem. wi,j = ?? ? ?? 1, ifLij ?Lth 0, otherwise (4.3) 4.3.2 Problem Statement In this chapter, we address the degree constrained spanning tree problem given a feasibility undirected graph G = (V,E), whereV is the set of V base stations or vertices, andE is the set of E links or edges between vertices, containing no self-loops or parallel edges. Every edge has been assigned positive weight defined in (4.3) . In degree constraint vector D(V?1) = di, every entry di indicates the maximum number of edges which is allowed to be incident on node i. We formulate two separate problems for bootstrapping and reconfiguring FSO networks. With respect to the bootstrapping problem, we seek a spanning tree T subject to the degree bound which has maximum algebraic connectivity. For reconfiguring the FSO network when links fail, fast reaction is more desirable. Hence, we aim to minimize computation time and transceiver movement. The 62 problem of finding a spanning tree in bootstrapping an FSO network is formulated as follows max ?2(L) (4.4) 1? summationtext eij??(v) xij ?dv,?v?V 1T ?X?1 = 2(V ?1) xij ?{0,1} In the first constraint, ?(v) is the set of edges incident to node v. X is the adjacency matrix of the spanning tree. If there is a link between node i and j, xij = 1; otherwise, xij = 0. The problem of reconfiguring an FSO network is slightly different since a spanning tree has already been formed. Another spanning tree is needed because of link failure in the former spanning tree. The objective is to minimize the difference between these two trees (or maximize edges that do not need to move) that is to minimize the transceiver movement. The problem is formulated as max 1T ?(X1?X2)?1 (4.5) 1? summationtext eij??(v) xij ?dv,?v?V (4.6) 1T ?X2?1 = 2(V ?1) (4.7) X1?A1 = A1 (4.8) X2?A2 = A2 (4.9) xij ?{0,1} (4.10) Where, X1 is already given as an adjacency matrix of the old spanning tree and X2 is the ad- jacency matrix of the new spanning tree. Operator ? in graph theory gives the element-by- element minimum value in the two matrices. For example, if A = (aij)m?n, B = (bij)m?n, andC = (cij)m?n = A?B, then cij =min{aij,bij}. Adjacency matrices of the graphA1 before the link failure and matrix A2 after the link failure are known. Obviously, edges in spanning tree belong to set of edges in graph, which are formulated as Eq. (4.9) and (4.10). 63 Constructing a DCMST is proven to be an NP-hard problem for non-Euclidean graphs [41]. If the degree constraint dv is 2 for all nodes, then the problem reduces to the Hamilton path problem which is NP-complete [44]. The problem of maximizing algebraic connectivity is also proven to be NP-hard [48]. Hence, we develop a distributed heuristic algorithm for creating a spanning tree in the first place, and also design a scheme to reconfigure topology with small operational time. 4.4 Topology Control Algorithm Bootstrapping and reconfiguring FSO networks are two equally important aspects of topology control. To satisfy their unique requirements, we address these two problems individually. How- ever, in designing an algorithm for bootstrapping FSO networks, we keep in mind of making the reconfiguration easier. 4.4.1 Bootstrapping Algorithm Bootstrappingalgorithminthischapterincludetwophases, whicharepresentedinintable4.1 and 4.2. Before the execution of these algorithms, we assume that each node has already known its neighbors? information through topology discovery. Phase 1: Construct Degree Constrained Spanning Tree The first phase is to asynchronously construct a degree constrained spanning tree without violating degree constraint as fast as possible. At the beginning, every node in the tree is sleeping. Then, the first one node or a few nodes are awakened spontaneously; other nodes are awakened by their neighbors. Once a node is awake, it first reads neighbor information and forms a group with a unique identification. Any nodes that are connected are in the same group. After reading neighbor information, it sorts these neighbors according to their degree constraints. Neighbors with higher degree constraints are preferred when deciding which link to choose. A node marks neighbor nodes which are outside its group and need to be connected as ?VISIBLE?; especially, when this node?s degree constraint is satisfied, which means it can be connected with more neighbors, its 64 neighbor nodes are marked as ?REACHEABLE? and itself is marked as ?ACTIVE?. For the links inside the group, some links are connected in the spanning tree and these links are marked as ?ONTREE?; other links are not in the spanning tree, so they are marked as ?INGROUP?. A node will try to establish a link with its ?REACHABLE? node until its degree constraint is no longer satisfied. But sometimes a group has some ?VISIBLE? nodes which are isolated. Hence, we need to adjust the topology in the group to include these nodes in the graph. ?ADJUST? procedure is similar to ?IMPROVEMENT? in [44]. We add an edge, which is not in the tree and the addition will not violate any degree limits, to the spanning tree, which results in the formation of a cycle, and then we delete another link in the cycle. Now, the cycle is broken and a new spanning tree is formed. By repeating this procedure, we can adjust the degree distribution, which might lead to more ?ACTIVE? nodes. When two nodes in different groups establish a link between them, the group identification should update to a unique ID for the new merged group and a root is selected. When there is no more visible node for every group or node, which means all nodes are included in aspanningtree, thisDCSTalgorithmendswithadegreeconstrainedspanningtree. Thedistributed algorithm for constructing a DCST is presented in in table 4.1. Phase 2: Maximize Algebraic Connectivity The second phase is maximizing the algebraic connectivity of the degree constrained span- ning tree. This phase only runs in the root node. This heuristic maximum algebraic connectivity algorithm will generate a final sub-optimal topology and the final result will be distributed to all nodes in the FSO network. We use the edge exchange algorithm which is presented in table 4.2 to maximize algebraic connectivity. Reducing edge sets, which is similar to the concept in [44], will be also useful in the reconfiguration algorithm. Every edge will have a set of edges whose addition to the tree will lead to forming a cycle with this edge. This set of edges are called ?reducing edge? to this edge, and nodes with reducing edge incident to are named ?reducing node?. In the decision of which reducing edge to choose if multiple potential reducing edges exist, the motivation for our heuristic is as follows: If an edge is added to a graph G, the algebraic 65 Table 4.1: DCST Formulation Algorithm 1: Wait for awakening ; 2: Read neighbor information and Set Group identification; 3: While(there is still visible node for the group) 4: IF(node has no ?REACHABLE? neighbor ) 5: Mark yourself as ?NOTACTIVE?; 6: Else 7: Mark yourself as ?ACTIVE?; 8: END 9: Mark links which is in the spanning tree inside the group as ?ONTREE?, and all other potential links inside the group as ?INGROUP?; 10: Sort neighbors according to degree limit; 11: WHILE (ACTIVE) 12: Mark neighbors with different group ID as ?VISIBLE?, and mark neighbors as ?REACHABLE? if currently degree is smaller than dv; 13: Awaken and connect ?REACHABLE? node with largest degree; 14: Mark this link as ?ONTREE?; 15: IF(Degree constraint is not satisfied) 16: Mark yourself as ?NOTACTIVE?; 17: END 18: END 19: Send root node your status; 20: WHILE(Selected as ROOT) 21: IF (No ?ACTIVE? nodes in group) 22: Adjust a ?INGROUP? link by adding it and deleting another link which form a cycle with this link; 23: Change node status accordingly; 24: IF(Still no ?ACTIVE? node in group) 25: Randomly delete more ?ONTREE? links and add the same number of potential links to maintain the tree; 26: Change node status accordingly; 27: END 28: END 29: END 30: END 66 Table 4.2: Maximum Algebraic Connectivity(MAC) Algorithm 1: WHILE(for every edge in the tree) 2: Find a reducing edge with larger weight to exchange; 3: IF (multiple choices exist) 4: Choose a reducing edge which will give us a branch in whichsummationtext e?P(i,i) 1/w(e) for every reducing node is the smallest; 5: Break a tie by choosing an edge with largest wij(vi?vj)2 6: END 7: END connectivity ?2 will increase. ?2 is defined as the second smallest eigenvalue of the Laplacian matrix L and can be written as ?2 (L) = mina?1,anegationslash=0< L?a,a >< a,a > (4.11) Ifv is a normalized eigenvector corresponding to ?2 , for any symmetric matrixY, ?2(L+Y)??2(L) +Tr(YvvT). (4.12) If ?2 is isolated, the increase in ?2 can be found as ??x l ?2 = vT ?L?x l v where x is a Boolean vector to indicate whether an edge belongs to the tree or not [43]. By definition L = l=msummationdisplay l=1 xl?wl?al ? aTl (4.13) where m is the number of edges in current graph, wl is the weight of edge, and al is the edge vector. The edge vector, for an edge connecting vertices i and j, is defined as ali = 1,alj =?1,and alx = 0 for other vertices x. Since ?L ?xl = wl?al ? a T l (4.14) 67 We can find the partial derivative of ?2 with respect to x as ??2?x = wij(vi?vj)2, which means wij(vi?vj)2 gives the first order approximation of increase in ?2. To clarify, node i and j are incident to edge l and wij is the weight of edge. The computation of eigenvector for every edge exchange is time consuming which is not desirable in FSO networks and drives us to find a faster method to choose the reducing edge. According to Theorem 1 in [49], if bottleneck matrices for two branches satisfy the condition: M? ?M , then, algebraic connectivity of two trees with these two branches satisfies ?2 ???2. Bottleneck matrix for a branch B at a vertex v is a k?k matrix, where k is the number of vertices in the branch. The entry in position (i,j) is defined as summationtext e?P(i,j) 1/w(e), where P(i,j) is the set of edges which are on both the path from i to v and from j to v. Note that we can always find a branch B which includes the reducing edges and a vertex v which the branch is at. Smaller bottleneck matrix for the branch B will give us larger algebraic connectivity. Aftercarefulinspectionofthebottleneckmatrix,wefindthatthereisevennoneedtocalculate the whole bottleneck matrix. We only need to compare the summationtext e?P(i,i) 1/w(e) for every reducing node, where P(i,i) is the set of edges which are on the path from reducing node i to v. The reason is that if reducing node is not on the path from another node j, then the entry for node j will remain the same; otherwise the change of summationtext e?P(i,j) 1/w(e) will be the same with summationtext e?P(i,i) 1/w(e). Hence, to maximize the algebraic connectivity, we need to find out which reducing edge will give us a branch in which summationtext e?P(i,i) 1/w(e) for every reducing node is the smallest. Proposition 1. The complexity of our bootstrapping algorithm isO(V 2?E). Proof. In the phase 1, the computational complexity of the DCST formation algorithm isO(V 2? E). In the phase 2, the complexity of our Maximum Algebraic Connectivity algorithm isO(V 2? E),becauseinthefirstplace,findingreducingedgesfortheedgeintreetakesO(V?E). Ifmultiple choices of reducing edges exist, finding the best bottleneck matrix takesO(V 2) and computing eigenvector takesO(V). Hence the whole computational complexity isO(V 2?E). 68 Table 4.3: Reconfiguration Algorithm 1: If(a link failure information received) 2: Find a reducing edge with largest weight to exchange; 3: IF (multiple choices exist) 4: Choose a reducing edge which will give us a branch in whichsummationtext e?P(i,i) 1/w(e) for every reducing node is the smallest; 5: Break a tie by choosing an edge with largest wij(vi?vj)2 6: END 7: End 8: IF(multiple link failure information received simultaneously) 9: IF(check if there is node failure) 10: Bootstrapping FSO network; 11: Else 12: Find a reducing edge with largest weight to exchange for every failed edge; 13: End 14: End 4.4.2 Reconfiguration Algorithm Reconfiguration algorithm only applies when one or more FSO links fail in the system. We introduce an algorithm with low computational complexity because in best case we can make use of the knowledge that we get from the bootstrapping process. In bootstrapping algorithm, we have already found out the set of reducing edges for every edge. In the case of only one link failure, one backup link is chosen from the set of reducing edges to replace the failed or degraded link. In the case of two or more link failures, if these links are not all incident on one failed node, reducing edges are chosen separately to form the spanning tree. In case of node failure, bootstrapping algorithm is adopted and preferred to construct a reliable new spanning tree. To decrease the communication time and transceiver movement, this algorithm can be a centralized algorithm. It can also be used in a distributed fashion but may cost more time. The algorithm is presented in table 4.3. Proposition 2. The complexity of our reconfiguration algorithm isO(V 2?E). 69 Proof. It takesO(V 2 ?E) to find the reducing edge for every failed link in the graph. Finding the best bottleneck matrix takesO(V 2) and computing eigenvector takesO(V) . So the whole complexity isO(V 2?E). But in the best case, with the knowledge from the bootstrapping algorithm, we already know reducing edges for every edge in the spanning formed by bootstrapping algorithm. Hence, in this case, just communication of failure information and transceiver movement time is required. 4.5 Performance Evaluation 4.5.1 Simulation Setting In this section, we present simulation of our algorithms and compare them with alternative spanning tree construction algorithms in FSO network. We assume that FSO nodes are stationary and link reliability threshold Lth is set to be 0.9 which is often required for a reliable communica- tion. We abstract FSO network as a grid which is 100?100 and nodes are generated in this grid randomly. Edge weights are uniformly distributed between 0.9 and 1. Degree constraint on every node is uniformly distributed between x and y, which are preset before simulation. The simulation was implemented in C++. We provide a comparison with two alternative algorithms: ? bottom-up algorithm (BU) [44] ? fragment selection and merging algorithm (FSM) [42] We compare two aspects to measure how these schemes work in FSO network: (i) algebraic con- nectivity; (ii) average weight of the spanning tree. We generate 100 random graphs and use these algorithms to obtain a spanning tree from which algebraic connectivity and average link weight are calculated. 70 Figure 4.1: Algebraic connectivity of tree with degree constraint 5 4.5.2 Performance Analysis The simulation results demonstrate the advantages of our algorithms over other algorithms. Fig. 1 and Fig. 2 illustrate performance of our algorithm compared with BU and FSM with degree constraint x = y = 5. In Fig. 4.1, we plot algebraic connectivity for random networks with size ranging from 20 nodes to 50 nodes. The value of each point is the average of 100 random graphs. We can see that as the number of nodes increases, the algebraic connectivity decreases, which is consistent with Corollary 1.1 in [49] which asserts that adding a vertex will decrease algebraic connectivity for the graph. As we can see from Fig. 4.1, our algorithm produces a spanning tree with higher algebraic connectivity. It achieves 28.76% normalized improvement of algebraic connectivity over FSM, and 66.4% normalized improvement over BU. In Fig. 4.2, we plot average edge weight of resulting trees. The edge weight represents the reliability of FSO links. Fig. 2 illustrates that our Maximum Algebraic Connectivity (MAC) algorithm generates more robust spanning trees with higher average link weight. Our algorithm achieves1.36%normalizedimprovementonaveragelinkweightoverFSM,and4.14%normalized improvement over BU. Fig. 4.3 and Fig. 4.4 illustrate the performance of our algorithm compared with BU and FSM when x = 2,y = 4, which means degree constraint of each node is between 2 and 4. Nodes and 71 Figure 4.2: Average edge weight of tree with degree constraint 5 Figure 4.3: Algebraic connectivity of tree with degree constraint from 2 to 4 Figure 4.4: Average edge weight of tree with degree constraint from 2 to 4 72 links are generated in this grid randomly. The simulation results show that our algorithm performs better than other alternative scheme in FSO network in both aspects: algebraic connectivity and average link weight. The BU algorithm does not take into account the edge weight which is the reason why it achieves the lowest average weight; FSM focuses on algebraic connectivity solely. However, in our algorithm, we consider both individual links? weight, which is also an important indicator of quality of FSO networks, and the algebraic connectivity of the robust spanning tree. 4.6 Conclusion WestudiedtheproblemofbuildingrobustdegreeconstrainedspanningtreeforFSOnetworks. Initial configuring, also called bootstrapping, and reconfiguration are two crucial parts of topology control in FSO networks; algorithms for bootstrapping and reconfiguring are both developed. Al- gebraic connectivity, as defined in spectral graph theory, is the second smallest eigenvalue of the Laplacian matrix L associated with a graph and is adopted as measure of robustness. The prob- lem of building a degree constrained spanning tree with maximum algebraic connectivity and edge weight are formulated as 0-1 ILP problem and is proven to be NP-hard. For this NP-hard problem, we design fast bootstrapping and reconfiguration algorithms for FSO networks. Our simulation re- sults show that the algorithms presented in this chapter outperform other alternative algorithms for building spanning tree in FSO networks in terms of both algebraic connectivity and edge weight. 73 Chapter 5 Joint Relay Selection and Power Allocation in Cooperative FSO Networks 5.1 Introduction Drawing increasing attention, free space optics (FSO) is a cost effective technology with ap- plications ranging from high capacity military communications to ?last-mile? broadband access solutions. Although FSO links are able to support data intensive communications, a line-of-sight (LOS) path is required and there are many factors leading to significant link performance degra- dation. Most common is the adverse atmospheric conditions (e.g., due to the temperature and pressure changes or flying objects), which can greatly degrade the link performance [21]. Fading- mitigation techniques have to be employed to maintain FSO system performance. To this end, topology control in FSO networks has been studied and proved to be effective in maintaining system performance [50]. On the other hand, spatial diversity techniques, exten- sively studied in conventional RF communication systems [51], have recently been introduced to FSO systems. Multiple-input multiple-output (MIMO) FSO system can achieve significant diver- sity gain in the presence of atmospheric fading by deploying multiple transmit or receiver aper- tures [52] [53]. Under the circumstance of limited transceivers or antennas, another cost-effective alternative (compared to MIMO-FSO) is the cooperative diversity technique, which is studied in this chapter. Cooperative diversity is considered as an effective means for combating weather turbulence in FSO networks. Usually FSO networks are usually well planned with perfect LOS paths. However, under the situations of severe weather or flying objects, an FSO base station may still experience degraded communication performance. However, if the FSO BS transmits cooperatively through an FSO BS relay whose surrounding weather is better, the degradation can be greatly mitigated. 74 Relay Obstruction Relay Figure 5.1: Illustration of a cooperative FSO network. In [54], one-relay cooperative diversity is demonstrated to achieve significant gains over non- cooperative FSO links that suffer from correlated fading while multi-hop relaying can also be employed in FSO networks [55]. In this chapter, we consider the decode-and-forward (DF) cooperation strategy with one relay for FSO links [56]. The cooperative FSO network framework is illustrated in Fig. 5.1, within which each FSO BS is equipped with two or three transceivers. During operation, the LOS path might be influenced by severe weather conditions but a cooperative FSO transmission strategy can mitigate the weather influence and enhance the system performance. We consider one-relay cooperative FSO communication with intensity modulation and direct detection (IM/DD). In the proposedcooperativeFSOnetwork, aBScantransmitdirectlytothedestinationBS,oruseanother BS as relay. In the latter case, the source BS first transmits symbols to the relay BS in one time slot. Then, the source and relay BS?s will simultaneously transmit the symbols to destination BS in the next time slot. Unlike the prior work on cooperative FSO networks that focused on physical layer aspects, we investigate the problem of maximizing the network-wide throughput with consideration of power budget and cost (i.e., the number of available FSO transceivers) constraints. Specifically, we formulate the problem of joint relay selection and power allocation as a Mixed Integer Nonlinear Programming (MINLP) problem. A reformulation linearization technique (RLT) is first presented 75 to derive an upper bound for the original MINLP problem. Due to the relaxation, the solution obtained from RLT is infeasible. Wedevelopbothcentralizedanddistributedalgorithmstosolvetheformulatedproblem. First, we design a centralized algorithm for relay selection based on maximum weight matching on a bi- partite graph. We then show that the remaining power allocation problem is convex and then solve it using the gradient method in convex optimization. In the case when centralized coordination is not available, we develop a distributed algorithm that uses only local channel state information (CSI). The distributed algorithm is based on the the Distributed Extended Gale-Shapley (DiEGS) algorithmoriginallydesignedforsolvingthestablemarriageproblem[57]. Theperformanceofthe proposedalgorithmsareevaluatedwithsimulationsandareshowntooutperformanon-cooperative scheme and an existing relay selecting protocol with considerable gains. The remainder of this chapter is organized as follows. The related work is discussed in Sec- tion 5.2. We introduce the system model in Section 5.3. We present the problem formulation and a RLT method to obtain a upper bound in Section 5.4. Both centralized and distributed algorithms are proposed to address the MINLP problem in Section 5.5. Our simulation studies are presented and discussed in Section 5.6. Section 5.7 concludes this chapter. 5.2 Related Work FSO has attracted significant interest both in academia and industry as a promising solution for high capacity, long distance communications [58]. Weather turbulence strongly affects FSO communication links. [59] introduced a multipath fading resistant FSO communication system architecture to combat adverse weather conditions. The influence of turbulence-accentuated inter- channel crosstalk on wavelength division multiplexing (WDM) FSO system performance has been discussed in [60]. The cooperative diversity technique has been used in FSO networks in several recent pa- pers [61] [62] [54]. Relay-assisted FSO communication has been studied in [63?65]. Both se- rial and parallel relaying coupled with amplify-and-forward and decode-and-forward cooperation 76 modes are considered in [63]. The authors adopted multiple-relay communication to shorten the distance between FSO BS?s and reduce the hop counts, resulting in considerable performance im- provements. The work in [63] was extended in [64] and the authors further provided an interesting diversity gain analysis. In [65], the authors propose to select only a single relay in each transmis- sion slot, to avoid the need for synchronizing multiple relays? transmissions. In a recent work [54], a one-relay cooperative diversity scheme was proposed for combating turbulence-induced fading and cooperative diversity was analyzed for non-coherent FSO commu- nications. Numerical results demonstrated considerable performance gains over non-cooperative FSO networks. Abou-Rjeily and Haddad in [62] studied cooperative FSO systems with multiple relays. An optimal power allocation strategy was proposed to enhance diversity order and mini- mize error probability. It turned out that the solution was to transmit with the entire power along the strongest link between the source and destination. The prior work on optimal relay selection or relay placement in FSO networks focus on max- imizing the diversity gain, reducing the outage probability, or maximizing the capacity for an individual BS. In this chapter, we consider the challenging problem of relay selection and power allocation under power and cost constraints. We aim at maximizing the overall FSO network capacity. We develop effective algorithms that are based on bipartite matching and convex opti- mization to compute highly competitive solutions to maximize the throughput of the cooperative FSO network. 5.3 System Model Cooperative communication is investigated in this chapter as a fading mitigation method for FSO networks. When the direct link between source and destination suffers from atmospheric turbulence, FSO BS?s can use relays to enhance link quality. 77 5.3.1 Channel Model FSO links are highly directional and are prone to degradation caused by weather turbulence. In this chapter, we consider both effects of path loss and turbulence-induced fading over FSO links [55]. The optical channel state h is a product of two factors, as h = hl?hf, (5.1) where hl denotes the propagation loss and hf represents the impact of atmospheric turbulence. hl is a function of optical wavelength ? and link length d, as [21] hl = ATX?ARX?e ??d (??d)2 , (5.2) where ATX and ARX are aperture areas of the transmitter and receiver, respectively. The coeffi- cient ? is a parameter related to wavelength and environment. For hf, we assume the impact of atmospheric turbulence can be modeled as a log-normal distribution, which is a widely used in FSO network literature, especially under weak-to-moderate turbulence conditions. The FSO channel model can be written as y = h?x+n, (5.3) where x and y are the transmitted and received signals, respectively; n is the additive Gaussian noise. With the non-cooperative strategy, the maximum achievable data rate for a communication pair is given by the Shannon formula as ws,d = Blog2 parenleftbigg 1 +|hs,d| 2Ps ?2 parenrightbigg , (5.4) in which hs,d denotes the channel state of the direct link between source and destination. Let Ws,r denote the maximum achievable capacity between source and destination when one relay is used, 78 which can be expressed as ws,r = B2 min braceleftbigg log2 parenleftbigg 1 +|hs,r| 2Ps ?2 parenrightbigg , log2 parenleftbigg 1 +|hs,d| 2Ps ?2 + |hr,d|2Pr ?2 parenrightbiggbracerightbigg , (5.5) where Ps and Pr represent the source and relay?s transmit power, and hs,r and hr,d are the channel states of the source-relay link and and the relay-destination link, respectively. 5.3.2 Cooperation Model We consider a relay-assisted IM/DD FSO communication system with the DF strategy [66]. The transmission takes two time slots. In the first time slot, the source station first transmits symbols to one relay station, which will detect the information symbols; in the second time slot, the source and relay will simultaneously transmit the symbols to the destination. ThecooperationmodelconsistsofK basestations. Eachbasestationmaytransmitdirectly,or use one relay to assist its transmission. We assume the base stations will not decline a cooperation request under any circumstance. We have M(M ?K) BS?s generating traffic among these base stations. The set of source base stations is denoted bySand the set of destination base stations is denoted byD. The cardinalities ofS andDare both M. The destination of source Si is denoted as Di. Usually an FSO BS has a limited number of transceivers, which limits the number of communication links that a BS can have simultaneously. For every source-destination pair, we assume at most one relay is assigned. Assuming CSI is known, every source would like to greedily choose its best relay to maximize its data rate. However, every BS has a limited number of transceivers and a limited power budget. In this chapter, we thus focus on the problem of relay selection and transmit power allocation to maximize the overall capacity of the cooperative FSO network. 79 5.4 Problem Formulation and Upper Bound In this section, the problem formulation of relay selection and power allocation is formed as an MINLP problem. A RLT method is also introduced so that a upper bound of the problem can be obtained. 5.4.1 Problem Formulation First, we define the following variables for relay selection. Ii,j = ? ?? ?? 1, if BS i selects BS j as relay 0, otherwise, for all i,j?{1,???,M}. (5.6) Note that Ii,i = 1 indicates that BS i transmit directly to its destination without using any relay. The limited number of transceivers at the BS?s is translated into constraintsummationtextMi=1 Ii,j ?Tj, for all j, where Tj is the number of transceivers at BS j. The base stations will use their transceivers to cooperate with each other and allocate power to each transceiver. The power budget constraint for each base station is represented assummationtextMj=1 Pi,j ?Pi, for all i, where Pi,j is the power that BS i allocates to assist source j and Pi is the power budget of BS i. In FSO communications, laser eye safety issues should always been considered. For eye safety considerations, we enforce a peak power bound for the transmit powers, as Pi,j ?Pmax, for all i,j?S. We assume that during data transmission, the allocated powers do not change in each time slot. Given the transceivers and power constraints, the objective is to develop a relay selection and power allocation scheme for each BS, while the overall network capacity is maximized. The 80 problem is formulated as follows. max Msummationdisplay i=1 (Ii,iwi,is,d + Ksummationdisplay j=1,jnegationslash=i,jnegationslash=Di Ii,jwi,js,r) (5.7) s.t. Msummationdisplay i=1 Ii,j ?Tj,?j?B (5.8) Ksummationdisplay j=1 Ii,j ?1,?i?S (5.9) Msummationdisplay j=1 Pi,j ?Pi,?i?B (5.10) 0?Pi,j ?Pmax,?i?B,j?S (5.11) Ii,j ?{0,1},?i?B,j?S, (5.12) where the capacity achieved by direct communication (i.e., wis,d) and the capacity achieved by using BS j as relay (i.e., wi,js,r) can be calculated using (5.4) and (5.5), respectively. Each source can choose to either transmit directly or use one relay, which is specified in constraint (5.9). 5.4.2 Upper Bound The formulated problem is an MINLP problem, which is NP-hard in general. We first adopt the RLT method to relax the MINLP problem to obtain a upper bound [67]. The first step of relaxation is to allow the binary I-variables to take real values in [0,1]. The second step is to linearize the logarithmic terms in the objective function. We have wi,is,d as a logarithmic function of Pi,i, as wi,is,d = Blog2 parenleftbigg 1 +|hi,i| 2Pi,i ?2 parenrightbigg . (5.13) We linearize this logarithmic relationship in (5.13) over some tightly bounded interval using the polyhedral outer approximation [67]. LettingPi,i be 0 andPmax, we obtain the lower and upper 81 bounds of the term inside the log function, which are denoted as ?i = 1 and ?i = 1 + |hi,i|2Pmax?2 , respectively. We use the four-point approximation and obtain the following new linear constraints. ?? ? ?? wi,is,d? log2 ?i?log2 ?i? i??i (?i??i) + log2 ?i wi,is,d? ?i??k? k ln2 + log2 ?k, (5.14) where ?k = ?i + k(?i??i)3 , for k = 0,1,2,3. Next, we replace the product term Ii,i ?wi,is,d with a substitution variable vi. Since Ii,i and wi,is,d are each bounded by their respective lower and upper bounds, we obtain the following RLT bound-factor product constraints. ? ???? ???? ??? ???? ? (Ii,i?0)(wi,is,d?log2 ?i)?0 (Ii,i?0)(log2 ?i?wi,is,d)?0 (1?Ii,i)(wi,is,d?log2 ?i)?0 (1?Ii,i)(log2 ?i?wi,is,d)?0. (5.15) Similarly, substituting Ii,i?wi,is,d = vi, we obtain four linear constraints for variable vi. We deal with the terms Ii,j?wi,js,r in the same manner. The capacity achieved by relaying is more complicated wi,js,r = B2 min braceleftbigg log2 parenleftbigg 1 +|hi,j| 2Pi,i ?2 parenrightbigg , log2 parenleftbigg 1 +|hi,i| 2Pi,i ?2 + |hj,i|2Pj,i ?2 parenrightbiggbracerightbigg , (5.16) 82 where hj,i is actually hj,Di, which represents the channel condition between the relay BS and destination BS. We then introduce new variables wi,js,r,1, wi,js,r,2, and ti,j to have ?? ? ?? wi,js,r,1 = B2 log2 parenleftBig 1 + |hi,j|2Pi,i?2 parenrightBig ?ti,j wi,js,r,2 = B2 log2(1 + |hi,i|2Pi,i?2 + |hj,i|2Pj,i?2 )?ti,j. (5.17) Now maximizing wi,js,r is equivalent to maximizing ti,j. We then linearize the first logarithmic relationship using the polyhedral outer approximation. The second logarithmic relationship can be linearized similarly, but we need to introduce an additional variable SNRi,j = |hi,i| 2Pi,i ?2 + |hj,i|2Pj,i ?2 , which is bounded. The logarithmic relationship wi,js,r,2 = B2 log2(1 + SNRi,j) can be linearized with the polyhe- dral outer approximation. Finally, we replace the product term Ii,j ?ti,j with a substitution variable vi,j. Since Ii,j and ti,j are both bounded, we obtain the RLT bound-factor product constraints similar to (5.15). Now the original MINLP problem is relaxed to a linear programming (LP) problem with the additional constraints and variables, which can be solved in polynomial time with an LP solver. Unfortunately, the solution obtained from LP is likely to be infeasible due to the relaxations, but the solution can be used as an upper bound for the original problem. 5.5 Solution Algorithms In this section, we develop centralized and distributed relay selection and power control algo- rithms to solve the formulated problem. 83 5.5.1 Centralized Algorithm The formulated problem is an MINLP problem with binary variables Ii,j?s and real variables Pi,j?s, which is NP-hard [67]. We develop a centralized algorithm that first determines the relay selections and then allocates transmit powers to selected relays. The main idea is to fix I-variables first and then consider optimized power allocation at each relay. The first phase of the centralized algorithm is to solve the relay selection problem. The relay selection problem here can be interpreted as a weighted bipartite matching problem, which can be solved with polynomial-time algorithms such as Hungarian algorithm. First we construct a bipartite graph as follows: one disjoint set consists of the source BS?s, and the other disjoint set contains the destination BS?s and the BS?s that have available transceivers to relay traffic for the sources. We call such a BS a relay BS. The weight of each matching edge is the corresponding link capacity. Such matching problem can be solved with polynomial-time algorithms, such as Hungarian algorithm and the Primal Dual algorithm. The heuristic relay selection algorithm is presented in Algorithm 1, which incorporates max- imum weight matching. Let Nj be the number of sources that relay j serves. Initially, Nj is set to be as large as possible to accommodate more sources; however, the power that each source is allo- cated may be too small to achieve the desired capacity gain in this case. As the algorithm evolves over time, Nj will be decreased finally to one. If a source i cannot achieve the desired capacity gain even with one relay that is allocated with all the power budget Pi, it has to transmit directly to its destination. Actually, for every source i and relay j, we can calculate the minimum relay power Pi,jmin required to achieve more capacity than by the direct transmission, according to (5.4) and (5.5). InLine16ofAlgorithm1, maximumweightmatchingisexecutedontheconstructedbipartite graph. The bipartite graph is constructed as a undirected complete bipartite graph G(A?B,E). As discussed, the disjoint setAconsists of all the source nodes, while the other disjoint setBis the union of the relay nodes and destination nodes. The edge between source node i and destination node j indicates that node i chooses to transmit directly to node j; the edge between source node 84 Algorithm 1: Centralized Relay Selection Algorithm 1 Initialize sourceS, relayRand destinationD; 2 Remove source{i|hi,j < hi,?j}fromSand set Ii = 1 ; 3 whileSis not empty &&Ris not empty do 4 for j?Rdo 5 Find the minimum power to achieve capacity gain: Pjmin = mini?S Pj,imin ; 6 Get Nj: Nj = min{Nj,Tj,Pmax/Pjmin?summationtexti Ii,j}; 7 if Nj ?0bardblPmax?Pjmin then 8 Remove j fromR; 9 end 10 end 11 if|R|?0 then 12 break ; 13 end 14 Calculate wi,js,r by setting Pj,i = Pmax/(Nj +summationtexti Ii,j) ; 15 Calculate wis,d by setting Pi,i = Pmax/(Ni +summationtextj Ij,i) ; 16 Initial bipartite graphGwith setSand setR?Dand capacity assigned as weights; 17 Compute the maximum weight matching ; 18 for i?Sdo 19 if source i is matched to relay j then 20 Remove source i fromSand Set Ii,j = 1 and Tj = Tj?1 ; 21 end 22 end 23 for j?Rdo 24 if j is not matching saturated then 25 Set Nj = Nj?1 ; 26 end 27 end 28 end 29 if|S|?0 then 30 Set Ii = 1,?i?S; 31 end i and relay node j indicates that node i choose node j as relay and node j will relay symbols to the destination. In this graph, there are actually Nj nodes for one relay, as given in Line 6 in Algorithm 1. The weight of each edge is the capacity achieved by transmitting using the link, which can be calculated and assigned before the matching computation. During every iteration, we check if a relay has been assigned to any source or not. If a relay BS j has not been matched to any source BS?s, we will decrease its service capacity Nj, which is the number of source BS?s 85 that this relay serves. By decreasing service capacity, more power is available for candidate source BS?s. After the I-variables are determined as in Algorithm 1, the second phase of our centralized algorithm is to solve the power allocation problem, which can be shown to be a convex problem. The power allocation problem in the second phase, which is presented as max summationdisplay i?S1 wi,is,d + summationdisplay i?S2 wi,ris,r (5.18) s.t. Msummationdisplay j=1 Pi,j ?Pi,?i?S (5.19) 0?Pi,j ?Pmax,?i,j?S. (5.20) The sources are divided into two sets: one set is transmitting directly without using any relays, denoted byS1; the other set is transmitting using one relay, denoted byS2. For each BS i inS2, its relay is denoted by ri. This power allocation problem can be solved by many convex optimization methods, such as gradient, Interior point, or Newton method. 5.5.2 Distributed Algorithm The centralized algorithm requires a central controller to gather all channel information and executethealgorithm. Itmaynotbeapplicablewhenthereisnosuchcentralizedentity. Inthissec- tion, we propose a distributed greedy algorithm, where each base station only use its own channel gains. With knowledge of the channel gains, a source will always prefer to transmit through the channel with the best channel gain. Hence, for source BS i, we create a preference list according to channel gains hi,j; for relay j BS, we also get a preference list according to channel gains hj,i. Then we have two sets: one set is the source nodes; the other set is the relay or destination nodes. Each source node will select one node from the other set given the preference lists. Given these 86 preference lists, the problem of determining the I-variables can be treated as a stable marriage problem and we solve it with the DiEGS algorithm [57]. There are two parts of this algorithm: one part is called Men-procedure and another part is Women-procedure. Men-procedure will be executed in each source BS?s and Women-procedure will be executed in each relay and destination BS?s. DiEGS algorithm will produce a stable matching between two sets of BS?s so that there does not exist any alternative pair of BS?s in which both of them are better off, given their preference lists. In our case, the size of two parts are not equal; but, it is known that, an instance of stable marriagewithsetsofunequalsizehasexactlythesamesetofstablematchingsasthesameinstance with the unmatched nodes deleted. Hence, with some modification of the DiEGS algorithm, we can distributedly solve the relay selection problem in polynomial time. Now we have to solve the power allocation problem in a distributed manner, which is given in (5.18)?(5.20). For each BS, we have local variables Pi and Pi,j. For BS i inS2, variable Pj,i is the power that relay BS allocates to assist its transmission, which is not local. We will introduce auxiliary variables t?i to localize capacity wi,ris,r and P?i to localize power allocation at the relay. Now the problem becomes max summationdisplay i?S1 wi,is,d + summationdisplay i?S2 t?i (5.21) s.t. Msummationdisplay j=1 Pi,j ?Pi,?i?B 0?Pi,j ?Pmax,?i?B,j?S B 2 log2 parenleftbigg 1 +|hi,ri| 2Pi,i ?2 parenrightbigg ?t?i,?i?S2 B 2 log2 parenleftbigg 1 +|hi,i| 2Pi,i ?2 + |hri,i|2P?i ?2 parenrightbigg ?t?i,?i?S2 tri,i = t?i,tj,i = 0,?i?S2,jnegationslash= i,jnegationslash= ri Pri,i = P?i ,Pj,i = 0,?i?S2,jnegationslash= i,jnegationslash= ri, 87 where the subscription of tri,i indicates that the power allocation is determined by relay ri. We next take a dual decomposition approach to obtain a distributed algorithm for power allo- cation [68]. Applying the Lagrangian method, we show the original problem can be decomposed into subproblems with only local variables. For a BS in setS1, we have the local maximization problem as max wi,is,d +?1,i(Pi? summationdisplay j Pi,j) + (5.22) vector?1,iTvectorti + vector?2,iT vectorPi,?i?S1. where ?1,i, vector?1,i, vector?2,i are all Lagrange multipliers and vectorPi = [Pi,1,Pi,2,???,Pi,m]T is the power allo- cation vector. In this chapter, we use bold letters to denote vectors and (?)T denotes the transpose operation of a matrix. The local dual problem is to minimize g1(?1,i), which is obtained as the maximum value of the Lagrangian solved in (5.22) for given ?1,i. For a BS in setS2, we have the local maximization problem, which is more complicated since its relay power is decided by the relay BS. max t?i +?1,i(Pi? summationdisplay j Pi,j)+ (5.23) ?2,i parenleftbiggB 2 log2 parenleftbigg 1 +|hi,ri| 2Pi,i ?2 parenrightbigg ?t?i parenrightbigg + ?3,i parenleftbiggB 2 log2(1 + |hi,i|2Pi,i ?2 + |hri,i|2P?i ?2 )?t ? i parenrightbigg ? ?1,ri,it?i ??2,ri,iP?i + vector?1,iTvectorti + vector?2,iT vectorPi,?i?S2, where ?1,i,?2,i,?3,i, vector?1,i, vector?2,i are all Lagrange multipliers. The local dual problem is to minimize g2(?2,i,?3,i) and the dual objective is defined as the maximum value of the Lagrangian over vectorPi and vectorti. 88 Algorithm 2: Distributed Relay selection and Power allocation Algorithm 1 Initialize the channel gains and obtain the preference list of source BS?s ; 2 Run the Men- or Women-procedure of DiEGS and determine the I-variables ; 3 Set t = 0, initialize ?1,i,j(0),?2,i,j(0) to some value ; 4 while termination criterion not met do 5 Each BS solves (5.22) or (5.23) locally and sends solution to related BS?s ; 6 Update prices with the iterate in (5.25) and announce new prices to related BS?s ; 7 Set t?t + 1 ; 8 end The master problem is given by min g(vector?1, vector?2). (5.24) Theoptimalvalueof(5.22)and(5.23)forgivensetsof vector?1 and vector?2 definesthedualfunctiong(vector?1, vector?2) and this master problem can be solved with the following iterative updates: ?1,i,j(t+ 1) = ?1,i,j(t)??(tj,i(t)?ti(t)?) (5.25) ?2,i,j(t+ 1) = ?2,i,j(t)??(Pj,i(t)?Pi(t)?). (5.26) Finally,thedistributedalgorithmforpowerallocationisasfollows. First,initialize?2,i,j(0),?2,i,j(0) to some value; then each BS solves its local maximization problem and sends its solution to the re- lated BS?s (determined in the step of relay selection); each BS updates its prices?-value iteratively, then sends the new prices to other coupled BS?s. The algorithm terminates when convergence is achieved or when a maximum number of iterations is reached. The distributed relay selection and power allocation algorithm is presented in Algorithm 2. 5.6 Performance Evaluation We evaluate the performance of the proposed algorithms using MATLAB simulations. In the simulations, the FSO BS?s are randomly placed in an area of radius R. We assume enough transceivers are equipped and FSO BS?s are allowed to communicate with any other BS?s. In one 89 Table 5.1: Simulation Parameters for Cooperative FSO Networks Symbol Definition ? = 1550 nm Wavelength Dr = Dt = 0.1 m Rx. and Tx. Aperture Diameter K = M = 20 Number of FSO BS?s in the area B = 10 MHz Bandwidth R = 5 Km Radius of area Pmax = 2 W Peak power constraint Pi = 0.5 W ,?i Power budget for FSO BS i Ti = 3,?i Number of transceivers on FSO BS i Table 5.2: Atmospheric Attenuation Coefficient ? Weather Condition ? Very Clear 0.48 dB/km Light Fog 13 dB/km Clear 0.96 dB/km Dense Fog 73 dB/km Haze 2.8 dB/km Deep Fog 309 dB/km half of this area, there is clear weather; the other half of this area suffers from fog. We calculate channel gains as in Section 5.3.1. The simulation parameters are listed in Table 5.1 [69]. The at- mospheric attenuation coefficients are related to weather and the values are listed in Table 5.2 [69]. We also evaluate the upper bound that obtained from RLT method, but the upper bound is too loose and since the I-variables are taken non-integer value, the solution we get from RLT is not feasible. In Fig. 5.2, we evaluate the performance of the two proposed algorithms along with a simple non-cooperative scheme and examine the impact of the number of FSO BS?s on the total sys- tem capacity. Our proposed algorithms achieve much greater capacity than direct transmission. The centralized algorithm has the best performance since it has all the channel information in the network. The distributed algorithm outperforms the non-cooperative scheme, although achieves less capacity than the centralized algorithm, due to the fact that the distributed algorithm only has knowledge of the BS?s local CSI. As the network size increases, the advantage of centralized 90 5 10 15 20 25 300 200 400 600 800 1000 1200 Number of BS Throughput (Mbps) Distributed Algorithm Centralized Algorithm Noncooperative Figure 5.2: Throughput vs. number of FSO BS?s. algorithm becomes more obvious, but it would be more challenging to obtain up-to-date global CSI. Next, we examine the impact of the power budget Pi available at each BS. To fully examine the impact of the power budget, we set the number of transceivers to five. In Fig. 5.3, we increase Pi from 0.5 W to 3 W and plot the total network throughput. It can be seen from the figure that Pi has no impact on the non-cooperative scheme; but as Pi is increased from 0.5 W to 2.5 W, the throughput of the FSO network increases when both the centralized and distributed algorithms are used. Due to the limited number of transceivers, the network throughput stops increasing when the power budget is larger than 2.5 W. Then, we also examine the impact of the number of FSO transceivers at each BS on the total system capacity. The number of BS?s is set to be 20. In Fig. 5.4, we find that when the number of transceivers is greater than six, the average throughput of the three schemes all decrease. This is becausewhenthenumberofBS?sthatarelayBSservesistoolarge,thepowerthattherelayBScan allocate to each BS becomes too small. However, before this critical point, the average throughput increases with the number of transceivers for the centralized algorithm. It is interesting to see that the number of transceivers has little impact on the distributed algorithm and the non-cooperative scheme, indicating that the system have not been fully utilized by these two algorithms. 91 0.5 1 1.5 2 2.5 30 200 400 600 800 1000 1200 Maximum Power (W) Throughput (Mbps) Distributed Algorithm Centralized Algorithm Noncooperative Figure 5.3: Throughput vs. power budget. 2 3 4 5 6 70 200 400 600 800 1000 Number of Transceivers Throughput (Mbps) Distributed Algorithm Centralized Algorithm Noncooperative Figure 5.4: Throughput vs. number of FSO transceivers. We also investigate the impact of weather at each BS location on the total system capacity. The results are plotted in Fig. 5.5. We change the weather condition from very clear to foggy. As expected, system capacity decreases as weather gets worse. When weather condition is from very clear to hazy, our algorithms outperform the noncooperative scheme with considerable gains. However, after the atmospheric attenuation coefficient ? becomes larger than about four, as shown in Fig. 5.5, the system throughput decreases drastically although our algorithms still achieve better performance. These simulation results show that cooperative schemes can achieve larger through- put especially when the LOS path is severely affected or not available at all. 92 2 4 6 8 10 12 140 500 1000 1500 2000 2500 Atmospheric Attenuation Coefficient Throughput (Mbps) Distributed Algorithm Centralized Algorithm Noncooperative Figure 5.5: Throughput vs. Attenuation Coefficient ?. 5 10 15 20 25 300 200 400 600 800 1000 1200 Number of BS Throughput (Mbps) Distributed Algorithm Centralized Algorithm Select Max Figure 5.6: Throughput vs. number of FSO BS?s. Finally,wecomparetheproposedalgorithmswithanexistingschemeinFig.5.6. Therelaying protocol in [65], which was called Select Max, selects a relay with the maximum minimum SNR of the path?s intermediate links, i.e., argmin r {SNRs,r,SNRr,d}. (5.27) In this scheme, every source BS uses one relay, and the same power is used for both source BS and relay BS transmissions. This scheme is a centralized one and thus achieves better performance 93 than the proposed distributed algorithm, when the network size becomes large. In the case of small network sizes, this scheme has almost the same performance as the proposed distributed algorithm. Under the same scenario when there is centralized control, our proposed centralized algorithm outperforms Select-Max in all the scenarios studied with considerable gains. 5.7 Conclusion In this chapter, we investigated the problem of maximizing the FSO system throughput un- der the constraints of limited power budget and number of FSO transceivers. Two algorithms are proposed and compared with non-cooperative scheme. Our simulation study showed that the cen- tralized algorithm achieved the greatest capacity but it required a central controller, while the pro- posed distributed algorithm can be adopted to achieve better performance than the non-cooperative scheme if centralized coordination is not available. 94 Chapter 6 Optical Power Allocation for Adaptive WDM Transmissions in Free Space Optical Networks 6.1 Introduction Recently, demand for multimedia service with high quality of service (QoS) requirements has been drastically increasing. To cater to the increasing demand, optical fibers have been uti- lized for years to deliver high volume of data. Due to the relatively high cost of deploying optical fibers, Free Space Optics (FSO) has been developed as a cost-effective wireless access technology for multi-Gigabit rate communication networks. FSO provides an excellent alternative to optical fiber systems for last-mile applications [18], ranging from local area network (LAN)-to-LAN con- nection for enterprise/campus, high capacity military communications, to disaster recovery and emergency response, among others. Attracting considerable attention from the research community, FSO has also been studied for carrying various wireless services, as known as Radio on Free Space Optics (RoFSO). FSO systems can operate on wavelengths in the 1520?1600 nm range, which makes the development of wavelength-division multiplexing (WDM) FSO systems feasible. Advanced Dense Wavelength Division Multiplexing (DWDM) RoFSO systems are emerging to support the simultaneous trans- mission of multiple wireless signals [18]. Despite of its great potential of supporting data intensive communications, a line-of-sight (LOS) path is required in any FSO system. Consequently, FSO is highlysusceptibletotheatmosphericenvironmentduetotheinhomogeneityofairtemperatureand pressure, or flying objects [58]. To harvest the high potential of FSO, fading-mitigation techniques should be employed to mitigate atmospheric turbulence-induced intensity fluctuations. To this end, topology control [50,58,70,71], load-balancing [72] and spatial diversity tech- niques [52] have been studied and proved to be effective in maintaining system performance. Adaptive transmissions have been recently introduced into FSO systems and is emerging as a 95 potential solution to mitigate the effect of atmospheric turbulence [73]. In FSO systems, channels are usually slow-fading and FSO transceivers have full-duplex capabilities. With negligible effect on data rates, a small portion of the bandwidth can be used for feedback of channel state informa- tion (CSI). In some hybrid RF/FSO systems, the RF channel can be used for CSI feedback. Thus reliable CSI could be available in FSO systems, which will be highly useful for designing adaptive transmission schemes. In this chapter, we propose optical power allocation schemes for an adaptive WDM RoFSO system in which variable wavelengths are adopted to mitigate the effect of weather turbulence. Proposed optical power allocation schemes optimally allocate transmit power to achieve maxi- mum capacity and enhance the performance of the WDM system. Nowadays, the 1520?1600 nm wavelength band has already been used in FSO systems. Furthermore, the emerging quantum cascade laser (QCL) technology can offer great flexibility on adjusting an FSO transceiver to op- erate on the optimal transmit wavelengths [74]. Under a total power constraint, different optical powers can be allocated to the chosen wavelengths in a WDM RoFSO system, to achieve further enhanced system performance. We investigate the problem of optical power allocation under the power budget and eye safety power constraints for adaptive WDM transmission in RoFSO sys- tems. To achieve capacity gain, we first analyze a conventional FSO system and develop a simple water-filling based algorithm to derive the optimal power allocation for the chosen wavelengths. For WDM RoFSO systems, a near-optimal RoFSO power allocation algorithm is developed based on the reformulation-linearization technique (RLT) [67], which can provide a linear programming (LP) relaxation of the complex problem. A computationally efficient scheme is also developed based on an approximation of the channel model. Finally, we investigate the diversity gain in the WDM FSO system. The performance of the proposed schemes are evaluated with simulations, and are demonstrated to be highly effective for achieving high systemcapacity under various scenarios. The remainder of this chapter is organized as follows. The related work is discussed in Sec- tion 6.2 and the system model is presented in Section 6.3. The three power allocation schemes are 96 developed in Section 6.4 to fully utilize DWDM FSO systems. Simulation studies are presented in Section 6.5. Section 6.6 concludes this chapter. 6.2 Related Work Attracting significant interest both in academia and industry, the FSO technology has been recognized as a promising solution for high capacity, long distance communications. The perfor- mance of the FSO networks highly depend on the reliability of a line-of-sight (LOS) path since an FSO transmitter is highly directional. Weather turbulence strongly affects FSO communication links. Weather effects on the connectivityof FSO networks was studied in [21]. The influence of turbulence-accentuated interchannel crosstalk on WDM FSO system performance has been dis- cussed in [60]. Many fading-mitigation techniques have recently been employed to maintain FSO system performance. [59] introduced a multipath fading resistant FSO communication system architec- ture to combat adverse weather conditions. Spatial diversity techniques, extensively studied in conventional RF communication systems [51], can also be applied in FSO systems to improve system performance. Multiple-input multiple-output (MIMO) FSO system can achieve significant diversity gain in the presence of atmospheric fading by deploying multiple transmit or receiver apertures [52] [53]. Cooperative diversity technique [75] [64] is also a cost-effective alternative to maintain system performance. In a recent work [54], a one-relay cooperative diversity scheme was proposed for combating turbulence-induced fading and cooperative diversity was analyzed for non-coherent FSO communications. Adaptive transmission technology has been introduced into FSO systems to mitigate weather turbulence. Djordjevic in [76] applied the conventional wireless adaptive modulation and coding method in an FSO system and further studied adaptive low-density-parity-check (LDPC) coded modulation to compensate performance degradation when turbulence is strong. Karimi and Uysal in [73] designed transmission algorithms with consideration of the number of bits carried per chip 97 time (BpC) in an FSO link, in which intensity modulation/direct detection (IM/DD) with M-ary pulse position modulation (M-PPM) was employed. Several other adaptive schemes have also been proposed and studied. In [74], the authors pro- posed using variable wavelength to combat the effects of atmospheric interference. Varying wave- length becomes feasible as the QCL technology becomes more mature. In [77], the authors pro- posed an adaptive transmission scheme to satisfy the requirements of various wireless services. A WDMpowerallocationmethodconsideringOpticalModulationIndex(OMI)wasproposedintheir adaptive RoFSO system design. Authors in [78] studied the potential of multiple-input/multiple- output channel for combating link fading. However, FSO MIMO system performance is limited by thermally noise limited receivers and thus Avalanche photodiodes (APDs) [79] were studied and commonly used in FSO systems. In this chapter, we propose power allocation schemes for adaptive WDM transmissions to achieve capacity gain or diversity gain. WDM has been employed in FSO transmission systems and has been shown to be capable of supporting very high data rate transmission in [80]. RoFSO technology makes it possible to transmit multiple RF signals using WDM. RoFSO provides a promising alternative to optical fiber systems. In [20], the authors designed and evaluated an RoFSO system as an universal platform for the integration of optical fiber and FSO networks. In [19], optical fading in FSO Channels was statistically analyzed, while [18] provides a compre- hensive study of RoFSO and the satisfactory results confirmed that the effect of scintillation on RoFSO performance can be estimated by an analytical model. IntheadaptiveWDMRoFSOsystemwestudied, variablenumberofwavelengthsareadopted to mitigate weather turbulence and optical transmit power are optimally allocated to achieve max- imum capacity gain. Although turbulence may not change significantly with wavelength in some weather conditions, considering the huge bandwidth that DWDM RoFSO system can support, it is still non-trivial to study the problem of utilizing wavelength properly. Moreover, Since QCL technology can offer great flexibility on adjusting wavelengths, more wavelengths can be utilized 98 as FSO systems advance. Alternatively, the multiple wavelengths used in WDM FSO system can be utilized to achieve robustness of the system. 6.3 System and Channel Model In this section, we will introduce the channel model and system models. 6.3.1 Channel Model FSOtransceiversarehighlydirectional, butFSOlinksarepronetodegradationduetoweather turbulence. We consider both effects of path loss and turbulence-induced fading over FSO links [75]. The optical channel state h is modeled as a product of two factors: h = hlhf, (6.1) where hl denotes the attenuation and hf represents the atmospheric turbulence. hl is a function of optical wavelength ? and link length d, as hl = ATXARXe ??d (?d)2 , (6.2) where ATX and ARX are the aperture areas of transmitter and receiver, respectively. The atmo- spheric attention coefficient ? is give by ? = (3.91/V)(?/550)?q, (6.3) where V is the visibility in kilometers and q is a parameter related to the visibility as [73] q = ? ?? ?? 0.585V 1/3, V ?6km 1.3, 6km?V ?50km. (6.4) 99 For modeling hf, we assume atmospheric turbulence modeled as a Log-normal distribution [55]. The Log-normal model is a widely used fading model, especially under weak-to-moderate turbulence conditions. The channel model for an FSO link can be written as y = h?Pt?x+n, (6.5) where x and y are transmitted and received signal respectively; n is the additive Gaussian noise; Pt is the power of the transmitted pulse. 6.3.2 System Model Radio on Free Space Optics (RoFSO) is a new technology that provides high data rate and reliable transmission. The RoFSO system using WDM allows simultaneous transmission of mul- tiple data streams consisting of various wireless services at very high rates. An advanced DWDM RoFSO system is illustrated in Fig. 6.1 [18]. We assume a WDM FSO system that is capable of operating from the 1520 nm wavelength band to the 1600 nm wavelength band. Apart from the data-transmitting antenna, we assume that an atmospheric influence measurement antenna or weather measurement device is equipped at the FSO BS. Thus, we can estimate atmospheric loss for channels using different wavelengths. Alternatively, CSI can be obtained by using a small portion of the bandwidth to provide channel information without affecting data rates. In some hybrid RF/FSO systems, the RF channel can be used for CSI feedback. Since atmospheric turbulence is a major degrading factor in FSO systems, we propose power allocation schemes for the adaptive FSO system, in which both wavelength and transmit power will be adaptively allocated according to channel conditions. 100 FSO attenna ... ?1 ?2 ?m ... ?1 ?2 ?m Figure 6.1: Advanced DWDM RoFSO system. An important parameter to evaluate the performance of RF-FSO is the carrier to noise ratio (CNR). The CNR of an RoFSO system using an APD photo detector is given as [18] CNR = 0.5(OMI?mPr) 2 RIN?P2r + 2em(2+F)Pr + 4KT?Gf , (6.6) where OMI is the optical modulation index, m is the photodiode gain, T is the temperature, K is the Boltzman?s constant, e is the electrical charge and Gf is the photodiode output conductance. In the denominator, 4KTGf is thermal noise; 2em(2+F)Pr is optical short noise, and RINP2r is the relative intensity noise from Laser diode(LD). The numerator represents the received signal power. Pr = rPpd, wherer is the photodiode responsivity andPpd is the received powerat the detector and is given as the product of transmit power and channel gain. Without loss of generality, we assume all tones are modulated with the same OMI that will not introduce intermodulation distortion. 6.4 Adaptive WDM Transmission To mitigate the effect of weather turbulence, we adapt wavelength and adjust power allo- cation to achieve better system performance. First, our proposed FSO system uses wavelength ??[1520,1600]nm and the available wavelengths are divided into N parts, non-overlapping with adequate spacing. We assume the FSO channel is slow varying [73]. For each channel with wave- length ?i, we can estimate its channel state hi or get feedback channel information from feedback channel. The multiple wavelengths used in FSO system can be utilized to achieve not only the ca- pacity gain but also the diversity gain, which will be discussed separately in the following sections. 101 6.4.1 Capacity Gain In different weather conditions, it is desirable to choose the wavelengths that have the best channel conditions. We assume that the WDM FSO system will use at most M different wave- lengths. Among the N available wavelengths, we will first choose M wavelengths that have the greatest channel gains. The next step is to allocate transmit powers to different wavelengths such that the system capacity is maximized. Conventional FSO System We first consider conventional modeling of wireless channels under white Gaussian noise. For the sake of simplicity, we denote channel gain for channel i by hi = |hlhf| 2 N0 . (6.7) According to the estimated channel gains, we choose M wavelengths that can offer the greatest channel gains from the N available wavelengths. Let Pi be the optical power allocated to channel i. Due to fixed power budget Pmax for each FSO base station, we have the following total power constraint Msummationdisplay i=1 Pi?Pmax. (6.8) In FSO systems, eye safety problem should be always taken into consideration in the system de- sign. Thus we have the additional power constraint 0?Pi?P. (6.9) 102 where P is the peak power bound for the transmit powers. Thus, we formulate the following capacity maximization problem. max Msummationdisplay i=1 log(1 +Pihi) (6.10) s.t. Msummationdisplay i=1 Pi?Pmax (6.11) 0?Pi?P,?i. (6.12) By applying Karush-Kuhn-Tucker(KKT) theorem, we can find that optimal power allocation sat- isfies ? ?? ?? Pi = min{P,[1?? 1hi]+} summationtextM i=1 Pi = Pmax, (6.13) where ? is the Lagrange multiplier. The inverse of ? is often regarded as the water level. The algorithm to solve the capacity maximization problem is to first sort the channels accord- ing to their channel gains. We then find the number of channels n, which are allocated with a nonzero power, as in Steps 2?3. The water volume Hn that is required to fill n channels can be cal- culated assummationtextni=1 i(1/hi+1?1/hi) and Hn should not be greater than Pmax. Then we can calculate the water level and allocate power to each selected channel according to (6.13). This procedure is base on the assumption that a feasible power should also satisfy the eye safety power constraint. If the allocated power 1? ? 1hi is greater than P, we need to adjust the water level accordingly. The detailed water-filling algorithm is presented in Algorithm 3. DWDM RoFSO System Next, we develop the model for the RoFSO channels as described in Section 6.3, which is more suitable for RoFSO using APD photo-detectors. CNR defined in Section 6.3.2 will be an important parameter to evaluate the RoFSO performance. 103 Algorithm 3: Simple Water-Filling Algorithm 1 Sort channels according to channel gains as: h1?h2?...?hM ; 2 Calculate Hn =summationtextni=1 i(1/hi+1?1/hi) ; 3 Find n such that Hn+1?Pmax?Hn ; 4 Determine Water level: 1? = 1n(Pmax +summationtextni=1 1hi) ; 5 Allocate power to each channel: Pi = [1?? 1hi]+,?i ; 6 if Pi?P,?i then 7 Terminate with the power allocation ; 8 end 9 Set i = 1 ; 10 while Pi > P do 11 Set Pi = P and Pmax = Pmax?P ; 12 Delete channel i in the next power allocation round; 13 i + + ; 14 end 15 Go to Step 2 ; To simply notation, we denote constant value 0.5(mOMI)2 bya, relative intensity noise level RIN by b, optical short noise 2em(2+F) by c, and thermal noise 4KTGf by d. Thus, our adaptive power allocation problem becomes max Msummationdisplay i=1 log parenleftbigg 1 + ai(Pihi) 2 bi(Pihi)2 +ciPihi +di parenrightbigg (6.14) s.t. Msummationdisplay i=1 Pi?Pmax (6.15) 0?Pi?P,?i. (6.16) If we denote CNR by ?i = ai(Pihi) 2 bi(Pihi)2 +ciPihi +di, (6.17) 104 the optimization problem, termed Problem OPT-FSO, can be rewritten as max Msummationdisplay i=1 log(1 +?i) (6.18) s.t. Msummationdisplay i=1 Pi?Pmax (6.19) 0?Pi?P,?i (6.20) ?i = ai(Pihi) 2 bi(Pihi)2 +ciPihi +di,?i. (6.21) It is challenging to solve this problem due to its complexity and nonlinear nonconvex properties. In the following, we adopt the RLT technique to obtain an LP relaxation of Problem OPT-FSO and derive a feasible near-optimal solution. The RLT relaxation is as follows. Letting ci = log(1+?i), the objective functionsummationtextMi=1 ci will now be linear and new constraintsci = log(1+?i) are introduced.We first linearize the logarithmic terms in the new constraints using the polyhedral outer approximation as follows. Letting Pi be 0 and P, we obtain the lower and upper bounds of ?i, respectively. We denote the upper bound of ?i by ?i. We use the four-point approximation and obtain the following new linear constraints. ? ?? ?? ci? ?i?log(1+?i)? i ci?log(1 +?ki ) + ?i??ki1+?k i , (6.22) where ?ki = k??i3 , for k = 0,1,2,3. The first equation in (6.22) is for the segment connecting the two end points of the logarithm function, and the second equation in (6.22) is for the tangent lines at the four points on the logarithm function. A four-point approximation for log(1 + ?) is illustrated in Fig. 6.2. The corresponding convex envelope is formed by four tangent lines and a chord connecting the two end points. Problem OPT-FSO now becomes a polynomial programming problem. We next introduce substitution variables and the corresponding RLT bound-factor product constraints to remove the 105 log(1+? ) ?0 Tangent lines Segment connecting the end points Figure 6.2: Four-point polyhedral outer approximation for log(1 +?) quadratic terms and to obtain an LP relaxation. Specifically, constraint (6.21) contains quadratic terms. We can rewrite (6.21) as bi(Pihi)2?i +cihiPi?i +di?i?ai(Pihi)2 = 0. (6.23) To remove quadratic terms, we define substitution variables ui = P2i , vi = ?iPi, and wi = ?iui, for all i. Thus constraint (6.21) becomes bih2iwi +cihivi +di?i?aih2iui = 0. (6.24) 106 Since Pi is bounded, it can easily show that ui ?(0,P2). For variables vi, we can obtain the following RLT bound-factor product constraints. ?? ???? ??? ???? ???? (?i?0)(Pi?0)?0 (?i??i)(Pi?0)?0 (?i?0)(P?Pi)?0 (?i??i)(P?Pi)?0. (6.25) Substituting vi = ?iPi, we obtain the following four linear constraints for variable vi. ?? ???? ??? ??? ???? ? vi?0 ?iPi?vi?0 P?i?vi?0 P?i??iPi?P?i +vi?0. (6.26) We deal with the variables wi in the same manner and obtain the following four linear constraints for variable wi. ? ???? ???? ???? ???? wi?0 ?iui?wi?0 P2?i?wi?0 P2?i??iui?P2?i +wi?0. (6.27) NowtheoriginalproblemisrelaxedtoanLPproblemwiththeadditionalconstraints andvari- ables, which can be solved in polynomial time with an LP solver. Note that during the procedure of reformulation and linearization, we preserve the original power constraints of Problem OPT-FSO, i.e., (6.19) and (6.20). Hence the optimal transmit power allocation policy obtained for the LP relaxation is also feasible to the original problem OPT-FSO. The feasibility of the LP solution is summarized in the following proposition. 107 Proposition 3. The optimal transmit power allocation policy to the LP relaxation of Problem OPT-FSO is a feasible solution to the original problem. Due to the complexity of the RLT-based method, it may not be suitable when the channels vary quickly. We also develop a more computational cost-effective scheme in the following. If we ignore the relative intensity noise and optical short noise, CNR can be approximated by 0.5P2r (mOMI)24KTG f . To simplify notation, denote constant value 0.5(mOMI)2/4KTGf by a. We obtain the following optimization problem. max Msummationdisplay i=1 logparenleftbig1 +ai(Pihi)2parenrightbig (6.28) s.t. Msummationdisplay i=1 Pi?Pmax (6.29) 0?Pi?P,?i. (6.30) According to Karush-Kuhn-Tucker(KKT) theorem, ifP? = [P?1,P?2,???,P?M]is a local max- imizer for the above optimization problem, there exists ??R and ?i ?R, for i?{1,???,M}, such that ? ???? ???? ??? ???? ? ?[log(1+ai(P?i hi)2)] ?Pi ????i = 0,?i ? parenleftBigsummationtext M i=1 P ? i ?Pmax parenrightBig = 0 ?i(P?i ?P) = 0,?i ??0,?i?0,?i (6.31) According to (6.31), if ?i > 0, then P?i = P; and if ?i = 0, we can solve (6.31) to have P?i = 1? + radicalBigg 1 ?2 ? 1 aih2i . (6.32) 108 Algorithm 4: RoFSO Power Allocation Algorithm 1 Sort channels according to channel gains as: h1?h2?...?hM ; 2 SolvesummationtextMi=1 Pi = Pmax numerically according to (6.33) ; 3 Obtain ? and calculate Pi for i?[1,M] according to (6.32) ; 4 if Pi?P,?i then 5 Terminate with the power allocation ; 6 end 7 Set i = 1 ; 8 while Pi > P do 9 Set Pi = P and i + + ; 10 end 11 Go to Step 2 ; Thus we find that the optimal power allocation satisfies ?? ??? ? ???? ? Pi = min braceleftBig P, 1? + radicalBig 1 ?2 ? 1 aih2i bracerightBig ,if ?2 ?aih2i Pi = 0,otherwise summationtextM i=1 Pi = Pmax. (6.33) Regarding the inverse of ? as some kind of ?water level,? we find that the greater the channel gain,thelargerthedeviationofthepowerallocatedtothischannelfromthewaterlevel. Usuallywe cannot directly solve from (6.33) the optimal power allocation. An iterative algorithms is needed to obtain an appropriate?and solve this optimization problem. The detailed algorithm is presented in Algorithm 4. 6.4.2 Diversity Gain In addition to multiplexing capacity gain discussed in Section 6.4.1, the multiple wavelengths usedintheWDMFSOsystemcanalsobeutilizedtoachievesystemrobustness. Thesamesymbols are sent to the receiver by using different wavelength and at the receiver multiple signals will be coherently combined to obtain diversity gain. Without loss of generality, we assume CSI are available at both the transmitter and receiver. A transmit symbol is sent on the i-th wavelength using power Pi. Let the power budget at the FSO 109 BS be Pmax and the power allocated to each wavelength is a part of the total power budget. That is, Pi = wiP, for all i, wheresummationtextMi=1 wi = 1. We normalized the power vector. The power vector P = [P1,P2,???,PM] is normalized so thatbardblPbardbl= 1. Thus the received signal is given by y = PHx+n, (6.34) where H is the diagonal CSI matrix. We assume different wavelengths adopted in the system are separated with sufficient guard bands, so that there is no interference between adjacent channels. It is not difficult to show that, to maximize the received SNR, the entry of the weight vector P corresponding to the largest entry of vector H should be one and all other entries should be zero. The corresponding received SNR is then the largest entry of vectorH. Thus, the wavelength with the best channel gain at the time of transmission should be solely selected and used to enhance the system performance. Although multiple wavelengths can be utilized to achieve diversity gain or capacity gain, it is not necessary to use the wavelengths purely for one purpose. For instance, some wavelengths can be grouped together to transmit the same symbols for diversity gain and the remaining wavelengths can be used to achieve capacity gain. By studying the tradeoff between the diversity and capacity gain, we can better utilize multiple wavelengths to improve system performance . 6.5 Performance Evaluation In this section, we evaluate the performance of the proposed algorithms with MATLAB sim- ulations. We calculate channel gains as shown in Section 6.3.1 and CNR are calculated according to(6.6)fortheevaluatedschemes. Thesimulationparametersarethesamefrompriorworkandare listed in Table 6.1 [18] [77]. We investigate the three algorithms introduced in the previous section for power allocation in WDM RoFSO system. Wavelengths in the band 1520?1580nm are as- sumed in our WDM RoFSO simulations. We adopt a 5nm spacing between adjacent wavelengths used in the simulations. 110 Table 6.1: Simulation Parameters Dt 15 mm Tx. Aperture Diameter Dr 0.1 m Rx. Aperture Diameter B 1 GHz Bandwidth d 1 Km Distance Pmax 0.5 W Power budget P 0.1 W Peak power constraint OMI 17.5% Optical modulation index m 5 Photodiode gain RIN -150 dB/Hz Relatively intensity noise 0.3 0.4 0.5 0.6 0.7 0.8 100 120 140 160 180 200 220 240 260 280 300 Power Budget(W) Capacity (Gbps) RLT Algorithm Water Filling RoFSO Power Allocation Figure 6.3: System capacity vs. the power budget Pmax. Clear Hazy Foggy 50 100 150 200 250 300 Weather Conditions Capacity (Gbps) RLT Algorithm Water?filling RoFSO Power Allocation Figure 6.4: System capacity vs. the weather condition. 111 0.5 1 1.5 2 2.5 3 50 100 150 200 250 300 Distance(Km) Capacity (Gbps) RLT Algorithm Water Filling RoFSO Power Allocation Figure 6.5: System capacity vs. the distance. InFig.6.3, wecomparethethreealgorithmsintroducedinSection6.4andexaminetheimpact of the power budget on the total system capacity. We increase Pmax from 0.5 to 1 with step-size 0.1 and plot the total capacity. As can be seen in Fig. 6.3, the RoFSO power allocation algorithm outperformstheothertwoalgorithmswithconsiderablegains. Sincetherelativeintensitynoiseand optical short noise are very small in our simulations, the RoFSO power allocation algorithm will achievethebestnear-optimalsolution. TheRLTalgorithm,althoughconsumesmuchrunningtime, can only produce an optimal power allocation for the relaxed LP problem. The power allocation solution obtained from RLT is feasible but achieves the worst performance in terms of capacity gain due to relaxation. We also find that the total capacity increases along with the power budget for both the water-filling algorithm and RoFSO power allocation algorithm, albeit not obviously for the latter. After the power budget becomes even larger, there is much less space for capacity increment due to the eye safety power constraint. Next, we examine the effect of weather conditions on the system capacity in Fig. 6.4. The distance between FSO BS?s is set to 500 m. We change the weather condition from clear to foggy by changing the atmospheric attention coefficient. The coefficient is 0.48 db/km for clear weather, 2.8 db/km for hazy weather, and 15 db/km for foggy weather [69]. As can be seen from Fig. 6.4, the system capacity decreases as weather gets worse. We also find that the simple water-filling 112 15 25 35 100 200 300 400 500 600 700 No. of Subcarriers in clear weather Capacity (Gbps) RLT Algorithm Water Filling RoFSO Power Allocation Figure 6.6: System capacity vs. No. of Subcarriers in clear weather. algorithm which is developed for conventional RF systems is not suitable for the RoFSO system when weather condition is severe. The capacity achieved by the simple water-filling algorithm decreasethemostastheweatherbecomesworse. Whentheweatherisfoggy, thecapacityachieved by the water-filling algorithm is about 10Gbps. Wealsoplotthetotalcapacityvs. thedistancebetweentheFSOBS?sinFig.6.5. Asexpected, the total capacity decreases as the distance is increased. When the distance between the FSO transceivers is relatively small, the difference between the capacities achieved by three algorithms is also small. But as we increase the distance from 500m to 1Km or even greater, the capacities achieved by simple water filling algorithm and RLT algorithm drop dramatically. The capacity obtained by using the RoFSO power allocation algorithm decreases the least and is always greater than capacities produced by the other two schemes. Finally, we examine the impact of the number of subcarriers used in adaptive WDM RoFSO system on the system capacity. In the wavelength bands starting from 1520nm, We adopt a 1nm spacing between adjacent wavelengths. The simulation results in clear weather is presented in Fig. 6.6. As we can see in Fig. 6.6, system capacity increase if we adopt more subcarriers in the adaptive WDM RoFSO system. When there are 15 channels in the system, the difference between the achieved capacity of the three schemes is not much great. However, as the number 113 15 25 35 100 200 300 400 500 600 700 No. of Subcarriers in hazy weather Capacity (Gbps) RLT Algorithm Water Filling RoFSO Power Allocation Figure 6.7: System capacity vs. No. of Subcarriers in hazy weather. 15 25 35 50 100 150 200 250 No. of Subcarriers in foggy weather Capacity (Gbps) RLT Algorithm Water Filling RoFSO Power Allocation Figure 6.8: System capacity vs. No. of Subcarriers in foggy weather. of subcarriers increase, the advantage of the RoFSO power allocation scheme becomes greater. We also run our simulations in in hazy and foggy weather and presented in Fig. 6.7 and Fig. 6.8, respectively. InFig.6.7, theRoFSOpowerallocationalgorithmachievegreatercapacitywithmore subcarriers. System capacities increased with the number of subcarriers for all three algorithms. However, due to the simplified objective function used in the development of the water-filling algorithm, the water-filling algorithm does not achieve as much capacity as the RLT algorithm when the number of sub carriers is 35. The RoFSO power allocation algorithm make better use 114 of available subcarriers to enhance system capacity and thus provide the greatest capacity. When weather conditions become worse, the system capacity become much small and the results are shown in Fig. 6.8. When the weather is foggy, the capacity achieved by the water-filling algorithm is very small. But the RoFSO power allocation algorithm and the RLT algorithm can maintain system performance in foggy weather. Also when more subcarriers are utilized in the system, more system capacity can be achieved by using these two algorithms. To conclude, the system performance in terms of capacity by using the RoFSO power alloca- tion algorithm is the best in all situations studied here. These simulation results indicate that with proper system design, the RoFSO system can support high data rates even over long distance and under bad weather conditions. 6.6 Conclusions In this chapter, we investigated the problem of optical power allocation under a power budget constraint and eye safety power constraint for adaptive WDM transmission to mitigate the effect of weatherturbulence, andsolutionalgorithmsaredeveloped. Forconvectionaltransmissionsystems, a simple water-filling algorithm can be adopted to allocate power to different wavelengths; for WDM RoFSO systems, a RoFSO power allocation algorithm was demonstrated to achieve the greatest system capacity. It is capable of supporting high data rates even over long distance or under bad weather conditions. Utilizing multiple wavelengths in WDM FSO system for diversity gain was also investigated. 115 Chapter 7 Conclusion and Future Work 7.1 Summary The research in femtocell networks includes two chapters: Chapter 2 and Chapter 3. In Chap- ter 2, the problem of cell association and handover management in femtocell networks is investi- gated. Two extreme cases for cell association are first discussed and analyzed, and an algorithm to maximize network capacity while achieving fairness among users is proposed. Based on this algorithm, a handover algorithm to reduce the number of unnecessary handovers using Bayesian estimation is further developed. The proposed handover algorithm is demonstrated to outperform a heuristic scheme with considerable gains in the simulation study. In Chapter 3 , cell association policies are designed with the objectives of minimizing the service latency in femtocell networks. The objective is to offload the traffic from macro base sta- tion to femtocell base stations and minimize the latency of service requested by users. This cell association problem is proven to be NP-hard and the optimal solution cannot be obtained in poly- nomial time. Therefore, three nearly optimal algorithms to address the problem with the objective of minimizing the total service time on each base station are proposed. The first sequential fixing algorithm achieves the best performance in total service time. The second approximation algo- rithm has the lowest computational complexity and proven optimal gaps. The third randomized algorithm requires the least information exchange among users. An optimal solution for service scheduling to minimize the average waiting time per user on the same BS is also discussed in the section. The proposed schemes are shown to outperform a heuristic selfish scheme with significant gains. 116 Research is extended to FSO networking in the third part of this dissertation. Topology con- trol, spatial diversity techniques and adaptive transmissions in FSO systems are studied to mitigate weather turbulence in the next chapters. InChapter4, theproblemofbuildingaspanningtreewhenthenumberoftransceiversoneach base station is limited in FSO networks is studied. We develop an initially configuring algorithm which produces a spanning tree with high algebraic connectivity and average edge weight. We also develop a fast reconfiguration algorithm when one or more links fail. Our algorithms outper- form alternative schemes in improving both algebraic connectivity and average edge weight. The robustness of the resulting topology of FSO networks is significantly improved. In Chapter 5, the challenging problem of relay selection and power allocation in cooperative FSO network is investigated.The problem is formulated as a Mixed Integer Nonlinear Program- ming (MINLP) problem, which is NP-hard. We first adopt the reformulation-linearization tech- nique (RLT) to derive an upper bound for the original MINLP problem. Due to the relaxation, the solutions obtained from RLT are infeasible. Both centralized and distributed algorithms using bipartite matching and convex optimization to obtain highly competitive solutions are proposed, and are shown to outperform the non-cooperative scheme and an existing relay selection protocol with considerable gains through simulations. In Chapter 6, Power allocation schemes for adaptive WDM transmissions are developed to combat the effect of weather turbulence in FSO networks. The problem of optical power allocation under power budget and eye safety constraints is investigated for adaptive WDM transmission in RoFSO networks. Simulation results show that WDM RoFSO can support high data rates even over long distance or under bad weather conditions with an adequate system design. This work provides new visions for practical solutions to mitigate weather turbulence in FSO networks. 7.2 Future Work There are still significant amount of research opportunities in two-tier femtocell networks and FSO networks. In femtocell networks, handover management may be further explored, especially 117 in femtocell networks with Quality-of-Service (QoS) requirements or with different access poli- cies. Also, service scheduling policies can also be extended to networks with multiple MBS?s and cells of different sizes. Femtocells also might be able to play an important part in mobile data offloading. To reduce the application response time and to save energy for the mobile devices, cyber foraging has been proposed. In cyber foraging network (CFN), the problem of balancing load among surrogates is also very important. With the ever-increasing advancement of mobile device technology and their pervasive usage, large number of powerful applications are expected to run on mobile devices and they can be offloaded to surrogates, that are powerful non-mobile computers usually in the geographical vicinity of mobile users. Communication overheads, which include both time and energy costs, will be further aggravated if mobile devices share the same spectrum to offload tasks. Dynamic spectrum allocation policies could also be investigated in heterogeneous networks. As the age of ?Big Data? comes, in addition to data offloading solutions, operators have also been considering a number of optimization approaches to relieve congestion on their networks. Data offloading through femtocells is effective for a number of reasons. Offloading policies con- sidering different metrics could be further investigated in femtocell networks. In additional to current work in femtocell networks, I will also extend my research in Free Space Optical (FSO) network, which is an energy-efficient alternative to existing wireless technol- ogy to cater to large data transmission. Due to the highly directionality, FSO links may suffer from external objects or severe weather conditions. Fading-mitigation techniques have to be employed to maintain FSO system performance. Oneinterestingandmostpromisingsolutiontonextgenerationwirelessnetworksisthehybrid RF/FSO systems. Due to the complementary nature of radio and FSO communications, both in capacity and coverage, the combined use for data transmission suggests advantages over a single media [14]. There are many ways to explore the potential of FSO and ways to incorporate both technologies in wireless networks. The challenge of implementing hybrid FSO/RF networks is 118 the dynamic, autonomous reconfiguration both in hardware and software in order to maximize communications availability and capacity for tactical operations. There is also research potential in full-optical wireless communication systems in which op- tical beam is emitted directly from a fiber termination to free space using an optical antenna. The need to convert the signal from electrical to optical and back is eliminated which results in a band- width and protocol transparent communication link much easier to integrate with cabled infras- tructure. Dense Wavelength Division Multiplexing (DWDM) enables transmitting simultaneously mutilple data streams consisting of various wireless services. Heterogeneous wireless services with different QoS requirements may transmit simultaneously and thus there is the scheduling problem in full-optical networks with the objective of enhancing capacity while maintaining QoS requirements. 119 Bibliography [1] A. Aijaz, H. Aghvami, and M. Amani, ?A survey on mobile data offloading: technical and business perspectives,? Wireless Communications, IEEE, vol. 20, no. 2, pp. 104?112, 2013. [2] D. Lopez-Perez, G. de la Roche, A. Valcarce, A. Juttner, and J. Zhang, ?Interference avoid- ance and dynamic frequency planning for wimax femtocells networks,? in Communication Systems, 2008. ICCS 2008. 11th IEEE Singapore International Conference on, 2008, pp. 1579?1584. [3] J.Andrews, H.Claussen,M.Dohler, S.Rangan, andM.Reed,?Femtocells: Past,present, and future,? Selected Areas in Communications, IEEE Journal on, vol. 30, no. 3, pp. 497?508, Apr. 2012. [4] Wikipedia, ?Femtocell ? Wikipedia, the free encyclopedia,? 2014, [Online; accessed 22-Jan-2014]. [Online]. Available:\url{http://en.wikipedia.org/wiki/Femtocell} [5] O. Tipmongkolsilp, S. Zaghloul, and A. Jukan, ?The evolution of cellular backhaul technolo- gies: Current issues and future trends,? Communications Surveys Tutorials, IEEE, vol. 13, no. 1, pp. 97?113, 2011. [6] K. Zheng, Y. Wang, W. Wang, M. Dohler, and J. Wang, ?Energy-efficient wireless in-home: the need for interference-controlled femtocells,? Wireless Communications, IEEE, vol. 18, no. 6, pp. 36?44, 2011. [7] D. Hu and S. Mao, ?Multicast in femtocell networks: a successive interference cancellation approach,? in Proc. IEEE GLOBECOM?11, Huston, TX, Dec. 2011, pp. 1?6. [8] V. Chandrasekhar, J. Andrews, and A. Gatherer, ?Femtocell networks: a survey,? Communi- cations Magazine, IEEE, vol. 46, no. 9, pp. 59?67, Sept. 2008. [9] H. Zhou, D. Hu, S. Mao, P. Agrawal, and S. A. Reddy, ?Cell association and handover man- agement in femtocell networks,? in Proc. IEEE WCNC 2013, Shanghai, China, Apr. 2013, pp. 667?672. [10] P. Palanisamy and S. Nirmala, ?Downlink interference management in femtocell networks - a comprehensive study and survey,? in Information Communication and Embedded Systems (ICICES), 2013 International Conference on, 2013, pp. 747?754. [11] A.Golaup, M.Mustapha, andL.Patanapongpibul, ?Femtocellaccesscontrolstrategyinumts and lte,? Communications Magazine, IEEE, vol. 47, no. 9, pp. 117?123, 2009. 120 [12] S. Hasan, N. Siddique, and S. Chakraborty, ?Femtocell versus wifi - a survey and comparison of architecture and performance,? in Wireless Communication, Vehicular Technology, Infor- mation Theory and Aerospace Electronic Systems Technology, 2009. Wireless VITAE 2009. 1st International Conference on, 2009, pp. 916?920. [13] A. Mahdy and J. Deogun, ?Wireless optical communications: a survey,? in Wireless Commu- nications and Networking Conference, 2004. WCNC. 2004 IEEE, vol. 4, 2004. [14] F. Demers, H. Yanikomeroglu, and M. St-Hilaire, ?A survey of opportunities for free space optics in next generation cellular networks,? in Communication Networks and Services Re- search Conference (CNSR), 2011 Ninth Annual, 2011, pp. 210?216. [15] J. C. Ricklin, S. M. Hammel, F. D. Eaton, and S. L. Lachinova, ?Atmospheric channel effects on free-space laser communication,? Optical and Fiber Communications Reports, Journal of, vol. 3, no. 2, pp. 111?158, April 2006. [16] V. W. S. Chan, ?Free-space optical communications,? Lightwave Technology, Journal of, vol. 24, no. 12, pp. 4750?4762, 2006. [17] H. Willebrand and B. S. Ghuman, Free Space Optics: Enabling Optical Connectivity in To- day?s Networks. Indianapolis, USA: Sams Publishing, 2002. [18] P. Dat, A. Bekkali, K. Kazaura, K. Wakamori et al., ?Studies on characterizing the trans- mission of RF signals over a turbulent FSO link,? Optics Express, vol. 17, pp. 7731?7743, 2009. [19] K.-H. Kim, T. Higashino, K. Tsukamoto et al., ?Statistical analysis on the optical fading in free space optical channel for RoFSO link design,? in Proc. SPIE 7620, Broadband Access Communication Technologies IV, 76200G, 2010, pp. 1?10. [20] K. Kazaura, K. Wakamori, M. Matsumoto, T. Higashino, K. Tsukamoto, and S. Komaki, ?RoFSO:Auniversalplatformforconvergenceoffiberandfree-spaceopticalcommunication networks,? in Innovations for Digital Inclusions, 2009. ITU-T Kaleidoscope:, 2009, pp. 1?8. [21] A. Vavoulas, H. Sandalidis, and D. Varoutas, ?Weather effects on FSO network connectivity,? IEEE/OSA J. Optical Commun. Netw., vol. 4, no. 10, pp. 734?740, Oct. 2012. [22] I.Ansari, M.-S.Alouini, andF.Yilmaz,?Ontheperformanceofhybridrfandrf/fsofixedgain dual-hop transmission systems,? in Electronics, Communications and Photonics Conference (SIECPC), 2013 Saudi International, 2013, pp. 1?6. [23] G. de la Roche, A. Valcarce, D. Lopez-Perez, and J. Zhang, ?Access control mechanisms for femtocells,? Communications Magazine, IEEE, vol. 48, no. 1, pp. 33?39, Jan. 2010. [24] W. C. Cheung, T. Quek, and M. Kountouris, ?Access control and cell association in two- tier femtocell networks,? in Wireless Communications and Networking Conference (WCNC), 2012 IEEE, Paris, France, Apr. 2012, pp. 893?897. 121 [25] C. Dhahri and T. Ohtsuki, ?Learning-based cell selection method for femtocell networks,? in Vehicular Technology Conference (VTC Spring), 2012 IEEE 75th, Yokohama, Japan, May 2012, pp. 1?5. [26] J.-M. Moon and D.-H. Cho, ?Novel handoff decision algorithm in hierarchical macro/femto- cell networks,? in Wireless Communications and Networking Conference (WCNC), 2010 IEEE, Sydney, Australia, Apr. 2010, pp. 1?6. [27] B. Jeong, S. Shin, I. Jang, N. W. Sung, and H. Yoon, ?A smart handover decision algorithm using location prediction for hierarchical macro/femto-cell networks,? in Vehicular Technol- ogy Conference (VTC Fall), 2011 IEEE 74th, San Francisco, CA, Sept. 2011, pp. 1?5. [28] S. Wu, X. Zhang, R. Zheng, Z. Yin, Y. Fang, and D. Yang, ?Handover study concerning mobility in the two-hierarchy network,? in Vehicular Technology Conference, 2009. VTC Spring 2009. IEEE 69th, Barcelona, Spain, Apr. 2009, pp. 1?5. [29] Z. Fan and Y. Sun, ?Access and handover management for femtocell systems,? in Vehicular Technology Conference (VTC 2010-Spring), 2010 IEEE 71st, Taipei, Taiwan, May 2010, pp. 1?5. [30] B. Jeong, S. Shin, I. Jang, N. W. Sung, and H. Yoon, ?A smart handover decision algorithm using location prediction for hierarchical macro/femto-cell networks,? in Vehicular Technol- ogy Conference (VTC Fall), 2011 IEEE 74th, San Francisco, CA, Sept. 2011, pp. 1?5. [31] D.HuandS.Mao,?Onmediumgrainscalablevideostreamingoverfemtocellcognitiveradio networks,? Selected Areas in Communications, IEEE Journal on, vol. 30, no. 3, pp. 641?651, Apr. 2012. [32] R. Madan, J. Borran, A. Sampath, N. Bhushan, A. Khandekar, and T. Ji, ?Cell association and interference coordination in heterogeneous lte-a cellular networks,? Selected Areas in Communications, IEEE Journal on, vol. 28, no. 9, pp. 1479 ?1489, Dec. 2010. [33] S. Corroy, L. Falconetti, and R. Mathar, ?Dynamic cell association for downlink sum rate maximization in multi-cell heterogeneous networks,? in Communications (ICC), 2012 IEEE International Conference on, Aachen, Germany, June 2012, pp. 2457?2461. [34] K. Son, S. Chong, and G. Veciana, ?Dynamic association for load balancing and interference avoidance in multi-cell networks,? Wireless Communications, IEEE Transactions on, vol. 8, no. 7, pp. 3566?3576, Jul. 2009. [35] J. N. Yossi Azar and R. Rom, ?The competitiveness of on-line assignments,? in Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, Orlando, Florida, United States, September 1992, pp. 203?210. [36] H.-S. Jo, Y. J. Sang, P. Xia, and J. Andrews, ?Heterogeneous cellular networks with flexible cell association: A comprehensive downlink sinr analysis,? Wireless Communications, IEEE Transactions on, vol. 11, no. 10, pp. 3484?3495, Oct. 2012. 122 [37] S. Mukherjee, ?Downlink sinr distribution in a heterogeneous cellular wireless network with biased cell association,? in Communications (ICC), 2012 IEEE International Conference on, Ottawa, Canada, June 2012, pp. 6780?6786. [38] H. Kim, G. de Veciana, X. Yang, and M. Venkatachalam, ?Distributed alpha-optimal user association and cell load balancing in wireless networks,? Networking, IEEE/ACM Transac- tions on, vol. 20, no. 1, pp. 177?190, Feb. 2012. [39] Y. Hou, Y. Shi, and H. Sherali, ?Spectrum sharing for multi-hop networking with cognitive radios,? Selected Areas in Communications, IEEE Journal on, vol. 26, no. 1, pp. 146?155, Jan. 2008. [40] v. T. David B. Shmoys, ?An approximation algorithm for the generalized assignment prob- lem,? Mathematical Programming, vol. 62, no. 3, pp. 461?474, Feb. 1993. [41] J. Knowles and D. Corne, ?A new evolutionary approach to the degree-constrained minimum spanning tree problem,? Evolutionary Computation, IEEE Transactions on, vol. 4, no. 2, pp. 125?134, 2000. [42] I. K. Son, S. Kim, and S. Mao, ?Building robust spanning trees in free space optical net- works,? in MILITARY COMMUNICATIONS CONFERENCE, 2010 - MILCOM 2010, 2010, pp. 1857?1862. [43] A. Ghosh and S. Boyd, ?Growing well-connected graphs,? in Decision and Control, 2006 45th IEEE Conference on, 2006, pp. 6605?6611. [44] F. Liu, U. Vishkin, and S. Milner, ?Bootstrapping free-space optical networks,? Selected Ar- eas in Communications, IEEE Journal on, vol. 24, no. 12, pp. 13?22, 2006. [45] S. Gurumani, H. Moradi, H. Refai, P. LoPresti, and M. Atiquzzaman, ?Dynamic path re- configuration among hybrid fso/rf nodes,? in Global Telecommunications Conference, 2008. IEEE GLOBECOM 2008. IEEE, 2008, pp. 1?5. [46] P. Gurumohan and J. Hui, ?Topology design for free space optical networks,? in Computer Communications and Networks, 2003. ICCCN 2003. Proceedings. The 12th International Conference on, 2003, pp. 576?579. [47] H. E. Nistazakis, E. Karagianni, A. Tsigopoulos, M. Fafalios, and G. Tombras, ?Average capacity of optical wireless communication systems over atmospheric turbulence channels,? Lightwave Technology, Journal of, vol. 27, no. 8, pp. 974?979, 2009. [48] D. Mosk-Aoyama, ?Maximum algebraic connectivity augmentation is np-hard,? Oper. Res. Lett, vol. 36, no. 6, pp. 677?679, 2008. [49] S. Kirkland and M. Neumann, ?Algebraic connectivity of weighted trees under perturbation,? Linear and Multilinear Algebra, vol. 42, no. 3, pp. 187?203, 1996. [50] I. K. Son and S. Mao, ?Design and optimization of a tiered wireless access network,? in Proc. IEEE INFOCOM?10, San Diego, CA, Mar. 2010, pp. 1?9. 123 [51] V. V. Sivakumar, D. Hu, and P. Agrawal, ?Relay positioning for energy saving in cooperative networks,? in IEEE 45th Southeastern Symposium on System Theory, March 2013, pp. 1?5. [52] A.FaridandS.Hranilovic,?Diversitygainandoutageprobabilityformimofree-spaceoptical links with misalignment,? IEEE Trans. Commun., vol. 60, no. 2, pp. 479?487, Feb. 2012. [53] A. Johnsi and V. Saminadan, ?Performance of diversity combining techniques for fso-mimo system,? in Communications and Signal Processing (ICCSP), 2013 International Conference on, 2013, pp. 479?483. [54] C. Abou-Rjeily and A. Slim, ?Cooperative diversity for free-space optical communications: Transceiver design and performance analysis,? IEEE Trans. Commun., vol. 59, no. 3, pp. 658?663, Mar. 2011. [55] M. Safari, M. Rad, and M. Uysal, ?Multi-hop relaying over the atmospheric poisson channel: Outage analysis and optimization,? IEEE Trans. Commun., vol. 60, no. 3, pp. 817?829, Mar. 2012. [56] N. Laneman, D. Tse, and G. Wornell, ?Cooperative diversity in wireless networks: Efficient protocols and outage behavior,? Trans. Inf. Theory, vol. 50, no. 11, pp. 3062?3080, Nov. 2004. [57] I. Brito and P. Meseguer, ?Distributed stable marriage problem,? in Proceedings of The Sixth InternationalWorkshopinDistributedConstraintReasoning,Edinburgh,Scotland,July2005, pp. 135?147. [58] H. Zhou, A. Babaei, S. Mao, and P. Agrawal, ?Algebraic connectivity of degree constrained spanning trees for FSO networks,? in Proc. IEEE ICC?13, Budapest, Hungary, June 2013, pp. 1?6. [59] V. Sharma and G. Kaur, ?Modelling of ofdm-odsb-fso transmission system under different weather conditions,? in Advanced Computing and Communication Technologies (ACCT), 2013 Third International Conference on, 2013, pp. 154?157. [60] A. Aladeloba, M. Woolfson, and A. Phillips, ?Wdm fso network with turbulence-accentuated interchannel crosstalk,? Optical Communications and Networking, IEEE/OSA Journal of, vol. 5, no. 6, pp. 641?651, 2013. [61] C. Abou-Rjeily, ?Achievable diversity orders of decode-and-forward cooperative protocols over gamma-gamma fading fso links,? pp. 1?12, 2013. [62] C. Abou-Rjeily and S. Haddad, ?Cooperative FSO systems: Performance analysis and opti- mal power allocation,? J. Lightwave Techno., vol. 29, no. 7, pp. 1058?1065, Apr. 2011. [63] M. Safari and M. Uysal, ?Relay-assisted free-space optical communication,? IEEE Transac- tions on Wireless Communications, vol. 7, no. 12, pp. 5441?5449, Dec. 2008. [64] M. Kashani, M. Safari, and M. Uysal, ?Optimal relay placement and diversity analysis of relay-assisted free-space optical communication systems,? IEEE/OSA J. Optical Commun. Netw., vol. 5, no. 1, pp. 37?47, Jan. 2013. 124 [65] N. Chatzidiamantis, D. Michalopoulos, E. Kriezis, G. Karagiannidis, and R. Schober, ?Relay selection in relay-assisted free space optical systems,? in Proc. IEEE GLOBECOM?11, Dec. 2011, pp. 1?6. [66] D. Hu and S. Mao, ?Cooperative relay in cognitive radio networks: Decode-and-forward or amplify-and-forward?? in Proc. IEEE GLOBECOM?10, Miami, FL, Dec. 2010, pp. 1?5. [67] Y. Huang and S. Mao, ?Downlink power control for variable bit rate videos over multicell wireless networks,? in Proc. IEEE INFOCOM?11, Apr. 2011, pp. 2561?2569. [68] D. Palomar and M. Chiang, ?A tutorial on decomposition methods for network utility maxi- mization,? IEEE J. Sel. Areas Commun., vol. 24, no. 8, pp. 1439?1451, Aug. 2006. [69] V. Rajakumar, M. Smadi, S. Ghosh, T. Todd, and S. Hranilovic, ?Interference management in WLAN mesh networks using free-space optical links,? J. Lightwave Techno., vol. 26, no. 13, pp. 1735?1743, July 2008. [70] I. K. Son and S. Mao, ?Design and optimization of a tiered wireless access network,? in Proc. IEEE INFOCOM?10, San Diego, CA, Mar. 2010, pp. 1?9. [71] I.-K. Son, S. Mao, and S. K. Das, ?On the design and optimization of a free space optical access network,? Elsevier Optical Switching and Networking, vol. 11, no. Part.A, pp. 29?43, Jan. 2014. [72] ??, ?On joint topology design and load balancing in fso networks,? Elsevier Optical Switching and Networking, vol. 11, no. Part A, pp. 92?104, Jan. 2014. [73] M. Karimi and M. Uysal, ?Novel adaptive transmission algorithms for free-space optical links,? IEEE Trans. Commun., vol. 60, no. 12, pp. 3808?3815, Dec. 2012. [74] X. Liu, ?Free-space optics optimization models for building sway and atmospheric interfer- ence using variable wavelength,? IEEE Trans. Commun., vol. 57, no. 2, pp. 492?498, Feb. 2009. [75] H. Zhou, D. Hu, S. Mao, and P. Agrawal, ?Joint relay selection and power allocation in cooperative FSO networks,? in Proc. IEEE GLOBECOM?13, Atlanta, GA, Dec. 2013, pp. 1?6. [76] I. Djordjevic, ?Adaptive modulation and coding for free-space optical channels,? IEEE/OSA J. Opt. Commun. Netw., vol. 2, no. 5, pp. 221?229, May 2010. [77] K.-H. Kim, T. Higashino, K. Tsukamoto, and S. Komaki, ?WDM optical power allocation method for adaptive radio on free space optics system design,? in 2011 International Topi- cal Meeting on Microwave Photonics & 2011 Asia-Pacific Microwave Photonics Conference (MWP/APMP), Singapore, Oct. 2011, pp. 361?364. [78] S. Wilson, M. Brandt-Pearce, Q. Cao, and I. Leveque, J.H., ?Free-space optical mimo trans- mission with q-ary ppm,? Communications, IEEE Transactions on, vol. 53, no. 8, pp. 1402? 1412, 2005. 125 [79] N. Cvijetic, S. Wilson, and M. Brandt-Pearce, ?Performance bounds for free-space optical mimo systems with apd receivers in atmospheric turbulence,? Selected Areas in Communica- tions, IEEE Journal on, vol. 26, no. 3, pp. 3?12, 2008. [80] E. Ciaramella, Y. Arimoto, G. Contestabile, M. Presi, A. D?Errico, V. Guarino, and M. Mat- sumoto, ?1.28 terabit/s (32x40 gbit/s) WDM transmission system for free space optical com- munications,? IEEE J. Sel. Areas Commun., vol. 27, no. 9, pp. 1639?1645, Dec. 2009. 126