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