Subchannel allocation for the OFDMA-based femtocell system☆
Introduction
Femtocells are low-cost and low-power cellular base stations designed to serve very small areas, such as home and office areas. One of the most important features of femtocells is that they connect customers to the mobile operators’ network through the IP-based residential backhauls such as DSL and cable. Hence, mobile operators can relieve stress on their macrocell network and increase the overall capacity of their network with reduced installation and maintenance costs. In addition, the small cell size of femtocells enables customers to communicate with low energy consumption and high SINR, resulting in prolonged battery life time and improved communication quality.
Although the deployment of femtocells brings many benefits to both customers and mobile operators, femtocell networks might have an irregular topology and the number of deployed femtocells is expected to be very large. Hence, in femtocell networks, more sophisticated resource allocation algorithms are required to effectively treat interferences between cells. There are various interference scenarios in femtocell networks according to channel sharing methods between femtocells and macrocell. In the dedicated channel deployment, the macrocell operates on the dedicated frequency band which is separated from that of femtocells, and thus there is no interference between femtocells and macrocell. Hence, in this case, we only have to consider intercell interferences among femtocells. However, in the shared channel deployment, femtocells and macrocell share the whole frequency band. Hence, in this case, intercell interferences can occur not only among femtocells but also between femtocell and macrocell, which makes interference management more difficult.
Earlier works on resource allocation problems for femtocell networks (e.g., [2], [3], [4], [5]) have mainly focused on the 3G systems such as CDMA and UMTS that are based on single-carrier transmissions. Although, they provided a different approach to each other, such as auto-configuration [2], [3], interference avoidance through a time-hopped CDMA [4], and admission control and channel re-allocation [5], they commonly proposed the interference mitigation schemes through the transmission power control to improve system capacity and coverage. However, those works cannot be applicable for orthogonal frequency-division multiple access (OFDMA) cellular networks, such as WiMax and 3GPP LTE, which are based on multi-carrier transmissions.
In OFDMA systems, each subchannel can be flexibly assigned to a different transmission. Hence, when femtocells are deployed, each OFDMA subchannel can be reused independently among femtocells, providing more flexibility for efficient resource allocation [6], [7]. To exploit the potential advantages of OFDMA-based femtocell networks, some works (e.g., [8], [9]) proposed fractional frequency reuse (FFR) schemes, in which different frequency planing is adopted in each of outer and inner regions of femtocells. In this approach, subchannels cannot be allocated flexibly considering intercell interference on each subchannel, and thus the spectral efficiency of subchannel allocation is limited. Another approach to enable OFDMA subchannel reuse in femtocell networks is exploiting intercell interference coordination (ICIC) [10]. However, it is obvious that appropriate subchannel allocation schemes are required before leveraging ICIC.
Recently, subchannel allocation problems in OFDMA-femtocell networks considering the irregularity of femtocell deployments have been studied intensively in the literature. In [11], a game theoretic subchannel exchange algorithm was developed assuming that there is an initial subchannel allocation and each femtocell has a different preference for subchannels. However, in this approach, it is hard to guarantee the optimality of the resultant subchannel allocation. In [12], a random-access subchannel allocation scheme was proposed for the dedicated channel femtocell deployment. In this scheme, aiming at maximizing weighted sum rates of femtocells, each femtocell randomly chooses multiple subchannels at the first frame, and subchannel collisions between femtocells are resolved through the subsequent frames. The proposed scheme is also extended to the shared channel femtocell deployment. However, this scheme requires some iterations to eliminate those collisions and some geometric information of mobile stations to avoid interference between femtocells and macrocell.
In this paper, we study a utility-based subchannel allocation problem for the OFDMA-based femtocell networks, which can be applied to both the dedicated channel and shared channel femtocell deployments. We first define an optimization problem that aims at maximizing the sum utility of the whole network. Since the original problem is a nonlinear integer optimization problem, which is an NP-hard problem, we develop a two-step suboptimal subchannel allocation algorithm. At the first step, we construct an interference graph based on the degree of intercell interference, which occurs between macrocell and femtocell, as well as among femtocells. Then, we convert it to a chordal graph in order to ensure the scheduling feasibility of subchannel allocation. Based on the chordal graph, we formulate a modified optimization problem and by solving this problem, we calculate the number of subchannels that should be granted to each cell. At the next step, we obtain an actual subchannel allocation that achieves the granted number of subchannels to each cell. To this end, we first introduce an extended graph to apply a coloring algorithm for subchannel allocation to each cell, and then adopt a greedy coloring algorithm with perfect elimination ordering (PEO), which is one of the optimal minimum coloring algorithms for the chordal graph. In addition, we also provide a time scheduling algorithm for enhancing performance by allowing femtocells and the macrocell to share the same subchannel in the time domain.
Recently, similar problems to our problem have been studied through the graph-based interference model [13], [14]. The authors in [13] proposed a simple heuristic subchannel allocation algorithm for OFDMA femtocell networks that tries to maximize the sum usage of frequency resources, while guaranteeing the minimum number of subchannels to each cell. The proposed algorithm is based on the interference graph, which represents the interference relationship among femtocells. Similarly, based on graph theory, the authors in [14] proposed an approximated subchannel allocation algorithm to achieve the weighted max–min fairness between femtocells. In this paper, since we use a utility-based framework in which we adopt general (concave) utility functions, problems [13], [14] (i.e., maximization of the sum usage of frequency resources and the weighted max–min fair allocation) can be regarded as special cases of ours. With allowing general utility functions, we can have higher flexibility to consider the heterogeneity of each femtocell such as the number of users and the required data rates in each femtocell than [13], [14]. Moreover, the algorithms in [13], [14] are tailored to their own specific problem and they cannot be applied to the problem with general utility functions. Hence, in this paper, we will develop a new subchannel allocation algorithm considering general utility functions.
The rest of the paper is organized as follows. In Section 2, we introduce basic backgrounds on graph theory that we will use to develop a subchannel allocation algorithm. Section 3 contains the description of the system model. In Section 4, we develop the subchannel allocation algorithm that aims at maximizing the sum utility of the femtocell network. We provide numerical results in Section 5 and finally conclude in Section 6.
Section snippets
Backgrounds on graph theory
In this section, we introduce basic backgrounds on graph theory that we will use to model femtocell networks and develop a subchannel allocation algorithm later. First of all, we introduce the following terminologies on a graph [15]:
- •
Clique: a set of vertices where two vertices are connected by an edge.
- •
Maximal clique: a clique that is not contained in any other clique.
- •
Size of a clique: the number of vertices that are contained in that clique.
- •
Chromatic number of a graph: the smallest number of
System model
In this paper, we first consider an OFDMA-based femtocell network with the shared channel deployment, which consists of a set of femtocells, , and a single macrocell indexed by ‘0’, as shown in Fig. 1. We denote the set of all cells including macrocell and femtocells in this system by . At the end of this section, we will show that our system model can also be used to model the femtocell network with the dedicated channel deployment with minor modifications. The entire frequency band is
Subchannel allocation algorithm
In this section, we develop a subchannel allocation algorithm that maximizes the sum of utilities of all cells. We first formulate an optimization problem asIn problem (P0), the first constraint is the restriction on the integer-valued subchannel assignment indicator and the second constraint represents the restriction on subchannel reuse, defined in (5). Problem (P0) is a nonlinear integer
Simulation results
In this section, we present numerical results for the proposed subchannel allocation algorithm. We first consider a shared channel femtocell deployment in an area of 100 m × 100 m, where the macrocell base station is located at the center of the area. We consider two types of random femtocell topologies: uniform topology and non-uniform topology. In the uniform topology, femtocells are deployed uniformly over the whole area. On the other hand, in the non-uniform topology, femtocells are deployed
Conclusion
In this paper, we have studied a subchannel allocation problem in the OFDMA-based femtocell network. Based on graph theory, we developed a unified system model that can be applied to both the shared channel and dedicated channel femtocell deployments. With this model, we formulated the optimization problem to maximize the sum utilities of all cells and we developed a suboptimal subchannel allocation algorithm that consists of two steps. In numerical simulation, we compared the average sum
Byung-Gook Kim received his B.S. and Ph. D. degrees in electrical and electronic engineering from Yonsei University, Seoul, Korea, in August 2007 and in August 2013, respectively. Since September 2013, he has been with Samsung Electronics. His research interests include resource allocation, opportunistic scheduling in wireless networks, network optimization and smart grid.
References (21)
Minimal triangulations of graphs: a survey
Discrete Mathematics
(2006)- B.-G. Kim, J.-A. Kwon, J.-W. Lee, Utility-based subchannel allocation for ofdma femtocell networks, in: Proc. of IEEE...
- H. Claussen, Performance of macro- and co-channel femtocells in a hierarchical cell structure, in: Proc. of IEEE PIMRC,...
- L. Ho, H. Claussen, Effects of user-deployed, co-channel femtocells on the call drop probability in a residential...
- V. Chandrasekhar, J. Andrews, Uplink capacity and interference avoidance for two-tier cellular networks, in: Proc. of...
- X. Li, L. Qian, D. Kataria, Downlink power control in co-channel macrocell femtocell overlay, in: Proc. of CISS,...
- et al.
OFDMA femtocells: a loadmap on interference avoidance
IEEE Communications Magazine
(2009) - D. Lopez-Perez, A. Ladanyi, A. Juttner, J. Zhang, OFDMA femtocells: a self-organizing approach for frequency...
- H.-K. Lee, M.-Y. Chung, Virtual-cell frequency reuse scheme to support seamless service in femtocell environments, in:...
- C.-Y. Oh, M.-Y. Chung, H.-S. Choo, T.-J. Lee, A novel frequency planning for femtocells in OFDMA-based cellular...
Cited by (7)
Maximizing Fairness for Resource Allocation in Heterogeneous 5G Networks
2021, IEEE Transactions on Mobile ComputingRandom graph coloring-based resource allocation for achieving user level fairness in femtocellular LTE-A networks
2018, Wireless Personal CommunicationsMulti-objective Resource Allocation for LTE/LTE-A Femtocell/HeNB Networks Using Ant Colony Optimization
2017, Wireless Personal CommunicationsFair Resource Allocation with Interference Mitigation and Resource Reuse for LTE/LTE-A Femtocell Networks
2016, IEEE Transactions on Vehicular TechnologyCoordinated Inter Cell Interference Avoidance Techniques and Performance Parameters for Cross Layer Interference in LTE-A Network
2016, Proceedings - 6th International Advanced Computing Conference, IACC 2016
Byung-Gook Kim received his B.S. and Ph. D. degrees in electrical and electronic engineering from Yonsei University, Seoul, Korea, in August 2007 and in August 2013, respectively. Since September 2013, he has been with Samsung Electronics. His research interests include resource allocation, opportunistic scheduling in wireless networks, network optimization and smart grid.
Jeong-Ahn Kwon received his B.S. and M.S. degrees in Electrical and Electronic Engineering from Yonsei University, Seoul, Korea in 2006 and 2008, respectively. He is currently working toward his Ph.D. degree in the School of Electrical and Electronic Engineering, Yonsei University, Seoul, Korea. His research areas include opportunistic scheduling, resource allocation, optimization, femto cell, and cognitive radio in communication networks.
Jang-Won Lee received his B.S. degree in Electronic Engineering from Yonsei University, Seoul, Korea in 1994, M.S. degree in Electrical Engineering from Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Korea in 1996, and Ph.D. degree in Electrical and Computer Engineering from Purdue University, West Lafayette, IN, USA in 2004. In 1997–1998, he was employed with Dacom R& D Center, Daejeon, Korea. In 2004–2005, he was a Postdoctoral Research Associate in the Department of Electrical Engineering at Princeton University, Princeton, NJ, USA. Since September 2005, he has been with the School of Electrical and Electronic Engineering at Yonsei University, Seoul, Korea and currently, he is an associate professor. He is a senior member of IEEE. His research interests include resource allocation, QoS and pricing issues, optimization, and performance analysis in communication networks, and smart grid.
- ☆
The earlier work of this paper has been presented at IEEE coHetNets 2011 that was held in conjunction with IEEE ICCCN 2011 [1]. This work was conducted when B.-G. Kim was a Ph.D. student in the Dept. of Electrical and Electronic Engineering, Yonsei University. This work was supported by Seoul R&BD Program (WR080951) and by Basic Science Research Program through the National Research Foundation (NRF) of Korea funded by the Ministry of Education, Science and Technology (2009-0067264).