{'fraction_non_alphanumeric': 0.0382449745668199, 'fraction_numerical': 0.005358648641296956, 'mean_word_length': 4.233309608540925, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On Cell Association and Scheduling Policies in Femtocell Networks

Femtocells are recognized effective for improving network coverage and capacity, and reducing 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 potential. In this paper, we investigate the problem of cell association and service scheduling in femtocell 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 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 algorithms are analyzed with respect to performance bounds, approximation ratios, and optimality, and are evaluated with simulations.


I. INTRODUCTION
A femtocell, as shown in Fig. 1, is a relatively small cellular network with a femtocell base station (FBS), usually deployed in places where signal reception from the macro base station (MBS) is weak due to long distance or obstacles. An FBS is typically the size of a residential gateway or smaller and connects to the service provider's network via broadband connections. FBS is designed to serve approved users within its coverage to offload wireless traffic from MBS. 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 prolonged battery life of mobile devices, improved network coverage, and enhanced network capacity [1].
Femtocells have gained a lot of attention from both academia and industry in the recent past. The three largest cellular network operators in the United States (i.e., AT&T, Sprint and Verizon) have offered commercial femtocell products and service recently. Although highly promising, a plethora of problems with both technical and economic natures have not been fully addressed yet. In [1], a comprehensive discussion is provided of the challenging technical issues in femtocell networks, ranging from synchronization, cell association, network organization, to quality of service (QoS) provisioning.
Unlike the MBS, whose placement is planned and optimized by operators, FBS's are usually randomly deployed by users. When the chaotic femtocell placement meets randomly distributed mobile users, cell association (or load balancing) becomes a critical problem for the performance of femtocell networks. For example, an FBS might be deployed at a place with high user density. With an inappropriate cell association  strategy, this FBS may have to serve all the users within its coverage, leading to very high load at this FBS and high service latency for its users. An effective cell association scheme should be used in this case to evenly distribute the load among neighboring FBS's and/or MBS. The cell association problem is particularly prominent in femtocell networks due to the unreliability of FBS's. The operation of an FBS may be interrupted by its owner (e.g., turned off after office hours); it may also experience power outage or any other faults. Then all the users initially associated with this FBS should be quickly assigned to other neighboring FBS's or the MBS. It is a load balancing problem on how to effectively associate these users with neighboring BS's without introducing a load burst and performance degradation at a particular BS.
In this paper, we investigate the problem of cell association and service scheduling in a two-tier femtocell network. In addition to the general goal of offloading wireless traffic from the MBS, we also aim to minimize the latency of service requested by users, while considering both open and closed access strategies. In particular, we consider one MBS and multiple FBS's serving randomly distributed mobile users. Users request to the BS's for downlink transmission of data packets. Without loss of generality, we assume that each user is allowed to connect to either the MBS or an FBS. The cell associate problem is to assign the users to the BS's such that the transmission of all the data packets can be completed as soon as possible. When multiple users are associated with one BS, we also aim to develop a service scheduling scheme such that the average waiting time for the users will be minimized.
We provide a general framework for the cell association problem for both open and closed access scenarios, which can be reduced to the classic load balancing problem and is NP-hard [2]. Therefore, we develop effective near-optimal algorithms with guaranteed performance. In particular, we first provide a sequential fixing algorithm based on a linear programming (LP) relaxation, which can achieve the best performance among the proposed schemes but with a relatively high computational complexity. To reduce the complexity, we propose a rounding approximation algorithm that ensures an (ρ + 1)-approximation of the optimal solution, and a greedy approximation algorithm that ensures a (2ρ)-approximation of the optimal solution. To further reduce the requirement on frequently updated channel state information (CSI), we then develop a randomized algorithm that allows a user to randomly pick a BS to connect to from a reduced BS list. Once the reduced BS list is generated by the randomized algorithm, no information exchange is required among users. An upper bound for the maximum expected service time achieved by the randomized algorithm is then derived.
After the users are assigned to the BS's, we next address the service scheduling problem for determining the transmission order of the data packets requested by the users associated with the same BS. We develop a simple algorithm to minimize the average waiting time for the users, and prove its optimality. In addition rigorous analysis of the proposed algorithms with respect to performance bounds, approximation ratios, and optimality, we also evaluate the proposed schemes with simulations, where superior performance is observed.
The remainder of this paper is organized as follows. The related work is discussed in Section II. We present the system model in Section III. Cell Association problem formulation and solutions are presented in Section IV. The scheduling problem is studied in V. The proposed algorithm are evaluated in Section VI. Section VII concludes this paper.

II. RELATED WORK
Femtocells have been acknowledged as an effective solution to the capacity problem of wireless networks. Ref. [1] provided comprehensive discussions of the technical issues, regulatory concerns, and economic incentives in femtocell networks. There are three different access control strategies in femtocell networks, open access, closed access and hybrid access. The pros and cons of these strategies were studied in [3].
Deploying femtocells also means introducing interference if no appropriate mitigation strategy is incorporated. Considerable research have been conducted on interference mitigation by assigning users to proper orthogonal channels [4].
Apart from the studies on interference mitigation, there are an increasing number of papers on cell association or cell selection under various scenarios [5]- [10]. Dhahri and Ohtsuki in [5] proposed a learning-based cell selection method for an open access femtocell network. The authors in [6] described new paradigms of cell association in heterogeneous networks with the help of third-party backhaul connections. Their simple and lightweight methodologies and algorithms incur very low signaling overhead. In [7], a convex optimization problem was formulated for cell association and a dynamic range extension algorithm was proposed to maximize the minimum rate of users on the downlink of heterogeneous networks. However, this paper did not directly optimize the load balancing in Heterogeneous Networks (HetNet), but rather focused on the sum rate and min rate. In [8], a cell association and access control scheme was presented to maximize network capacity while achieving fairness among users. In [9], the authors provided an analytical framework for evaluating outage probability and spectral efficiency with flexible cell association in heterogeneous cellular networks. Mukherjee in [10] analyzed the downlink SINR distribution in heterogeneous networks with biased cell association.
There are also some interesting prior work on load balancing in cellular networks. A theoretical framework was presented in [11] for distributed user association and cell load balancing under spatially heterogeneous traffic distribution. A distributed α-optimal algorithm was proposed and it supports different load-balancing objectives, which include rate-optimal, throughput-optimal, delay-optimal, and load-equalizing, as α is set to different values. In [12], the authors developed an off-line optimal algorithm for load balancing to achieve network-wide proportional fairness in multi-cell networks. They considered partial frequency reuse (PFR) jointly with load-balancing in a multi-cell network to achieve networkwide proportional fairness. An on-line practical algorithm was also proposed and the expected throughput was taken as the decision making metric. On-line assignments when users arrive one at a time was studied extensively in computer science literature. The competitive ratio analysis in [13] showed that any deterministic on-line algorithm can achieve a competitive ratio of log n, where n is the number of servers.
We find most of the related research was focused on offloading MBS traffic and improving network capacity with FBS's. In the following sections, we propose several cell association and transmission scheduling schemes with the objective of minimizing service latency in femtocell networks.

III. SYSTEM MODEL
We consider a two-tier femtocell network with M base stations: one MBS (indexed by 1) and M − 1 FBS's (indexed from 2 to M ). The All the BS's are connected to the Internet via broadband wired connections. There are N mobile users randomly located within the coverage of the femtocell network. We assume the MBS and FBS's are well synchronized and they share the same spectrum. Assume each user requests a fixed-length data packet from one of the M BS's. The problem is to assign the users to the BS's and schedule the transmission of their requested data packets at each BS, such that the transmissions can be finished as earlier as possible.

A. Link Capacity
Let P m be the transmit power of BS m and G m,n the channel gain between the BS and user n. According to the Shannon Theorem, the network capacity of user n connected to BS m is given by where B is network bandwidth, 1 σ 2 is noise power density, and I m,n is the interference from all other BS's. We have that where I n is the sum of interference from all BS's to user n. It does not depend on which BS user n is connected to and is a constant for each user. Substituting (2) into (1), we have where η m,n is signal to interference plus noise ratio (SINR), the same ratio of the received power in I n at user n.

B. Service Time
We assume each user requests a fixed-length data packet from one of the BS's. For simplicity of notation, we assume all the packets have the same length, denoted as L. Then the processing/service time of BS m for user n is given by The service time depends on the link capacity C m,n as given in (3). Note that the service time defined here is actually the transmission delay, i.e., the time it takes to finish the transmission of the data packet. The propagation delay is negligible due to the short distance and is ignored.

C. Femtocell Access Control
The type of access control for femtocells can be classified into two categories: closed access and open access. The open-access strategy allows all mobile users of an operator to connect to the FBS's; in this case, femtocells are often deployed by an operator to enhance coverage in an area where there is a coverage hole. With the closed access strategy, only a specific user group can get service from the FBS's [14]. Although closed access has been shown to decrease system throughput by 15%, surveys suggest that closed access is users' favorite option [15].
In this paper, we consider both access strategies. Let A m denote the set of users that can connect to BS m and B n the set of BS's that user n can connect to. Both open and closed access strategies can be easily modeled by these two sets. Specifically, for open access, we have A m = {1, · · · , N } and B n = {1, · · · , M }.

IV. CELL ASSOCIATION PROBLEM FORMULATION AND PROPOSED SCHEMES
To make the complex problem tractable, we divide the problem into two steps. First, we assign each user to one of the M BS's with the objective of minimizing the total service time on each BS. Second, we schedule the service order at each BS to minimize the average waiting time of users.

A. Problem Statement
The cell association problem can be formulated as a load balancing problem. Given a set of N users and a set of M BS's. Each user n has a service time t m,n if it is connected to BS m. Let C m denote the set of users assigned to BS m. Then it takes a total amount of time T m = n∈Cm t m,n for BS m to transmit all the packets. For optimal network-wide performance, we seek to minimize the maximum load among all the BS's, i.e., We find the cell association problem is similar to a load balancing problem. However, our problem is more challenging than the classic load balancing problem, where the service time of a user is identical when connecting to any BS. In our cell associate problem, the service time is a function of the link capacity as in (4). Its solution depends on not only user n, but also BS m. This cell association problem is easily seen to be NP-hard: when all the t m,n 's are identical for any BS m, the problem is reduced to the classic load balancing problem, which is NP-hard [2].
In the remainder of this section, we develop effective algorithms to solve the cell association problem. In particular, we present a sequential fixing algorithm, an approximation algorithm, as well as a randomized algorithm, and derive several approximation ratios and performance bounds.

B. Sequential Fixing Algorithm
To solve the above problem, we first define an indicator variable x m,n as Then we reformulate the problem as follows: In the formulated problem (7), all the indicator variable x m,n 's are binary, while T is a real variable. Thus it is a mixed integer linear programming problem [2], denoted by MILP, which is usually NP-hard. The original MILP is next relaxed to a linear programming (LP) problem, denoted as RLP. Specifically, we allow binary variable x m,n 's to take real values in [0, 1]. Then, the MILP problem can be converted into RLP as follows: 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 [16] to find a feasible solution to the MILP problem, which is presented in Algorithm 1.
Algorithm 1, we solve the RLP problem iteratively. During each iteration, we find the x m ′ ,n ′ that has the minimum value for (x m,n − 0) or (1 − x m,n ) among all fractional x m.n 's, and round it up or down to the nearest integer. Setting x m ′ ,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 x m,n ′ 's are set to 0, for all m. This procedure repeats until all the x m,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(n v 3.5 L b ), where n v is the number of variables and L b is the number of bits of input to the algorithm. We have the following proposition.  1), respectively. Besides, in each iteration, the number of variables is reduced by 1. Therefore, the complexity of SF is given by

C. Approximation Algorithm
Although the sequential fixing algorithm can solve the MILP problem within polynomial time, its complexity may be high even for small femtocell networks. In this section, we propose an approximation algorithm with low complexity to solve the MILP problem. Before we introduce the approximation algorithm, we first give the lemma below. Proof: Given the optimal allocation C * m for BS m, we have T * = max m n∈C * m t m,n . Then we have The first inequality is due to the definition of t n . The second inequality is due to the fact that the maximum value is always greater than the mean value. The last equality is because all users have to be connected to one of the BS's and ∪ M m=1 C * m is the set of all users. Intuitively, the maximum total service time is at least the service time of any one user. We have the following lemma.

Lemma 2.
The optimal solution, denoted by T * , to the MILP problem is lower bounded by T * ≥ max t n , where t n = min m∈Bn t m,n .
These lemmas will be used in analyzing the approximation ratio of the proposed approximation algorithms, which are presented in following subsections.
1) Rounding Approximation Algorithm: To ensure required SINR for each user, B n should not include all the FBS's in a real femtocell network. For example, some faraway FBS should not be considered by a user. Thus, we can use a threshold ρ to obtain the subsets A m and B n (A m will be updated when B n is determined).
Usually only a limited number of FBS's will be taken into consideration for a user. After we adopt this threshold, not only users' SINR requirements will be satisfied, but also the computational complexity will be greatly reduced.
Once A ′ m and B ′ n are determined, the following relaxed LP problem can be solved by any LP solver. x m,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 from [17] to obtain a feasible solution for the MILP problem. In this rounding method, a bipartite graph is constructed according to the RLP solution, which is constructed as a undirected bipartite graph G (A ∪ B, E). In the disjoint set A, each node represents a user n, while the other disjoint set B consists of BS nodes. We create k m = ⌈ n x m,n ⌉ nodes in B for BS m and these node are denoted by {b m,1 , b m,2 , · · · , b m,k , · · · , b m,km }. The edges are determined in the following way. For BS m, we sort the users in the order of non-increasing service time t m,n and the users are renamed {u 1 , u 2 , · · · }. Let X m,uj = j i=1 x m,ui .
For each BS, we divide the users associated to it into k m groups, as G 1 , G 2 , · · · , G Km . User u j will be included in group k (1 ≤ k ≤ k m ) if k − 1 < X m,uj ≤ k or k − 1 ≤ X m,uj−1 < k. If a user u j is included in two groups, the association x-variables need to be adjusted, such that x ′ b m,k ,uj = X m,uj − k + 1 and x ′ b m,k−1 ,uj = x m,uj − x ′ b m,k ,uj . Then we insert edges between BS node b m,k and all the user nodes in group k. Now the bipartite graph is created and we next find a maximum matching M from each user to nodes in the other disjoint set. This maximum matching M indicates a feasible solution for MILP problem: for each edge (n, b m,k ) in M, we associate user n to BS m.
Let T (b m,k ) denote the total service time at node b m,k before the matching operation and T ′ (b m,k ) the total service time at node b m,k obtained by the above rounding method. We have the following lemma.
. Proof: First, observe that the minimum service time in group (k−1) will be always no less than the maximum service time in group k, because we sort the users according to their service time in the non-increasing order.
According the above bipartite graph construction, for any (bm,k) will be no greater than the maximum service time in group k and will thus be no greater than the minimum service time in group (k − 1), which is less than i∈G k−1 x ′ b m,k−1 ,ui t m,ui . Since T (bm,k−1) = i∈G k−1 x ′ b m,k−1 ,ui t m,ui , consequently, we have the conclusion that T (bm,k−1) ≥ T ′ (bm,k) . Now we show that the solution produced by this rounding approximation algorithm is at most (ρ + 1) times greater than the optimal solution.

Theorem 1. The approximation algorithm based on linear programming and the rounding method ensures a (ρ + 1)approximation of the optimal solution.
Proof: For each BS m, we create k m nodes for it and there are k m corresponding groups of user nodes adjacent to them. Thus the total service time is In the first group, the maximum load will be the maximum service time of users associated with m. According to Lemma 2 and the definition of ρ in (9), we have T ′ (bm,1) ≤ max t m,n ≤ ρ max t n ≤ ρT * . Then, the total service time on any BS computed by our association algorithm will be km k=1 T ′ (bm,k) ≤ ρT * + T ≤ (ρ + 1)T * . The last inequality was due to T ≤ T * , since T is the solution of the relaxed problem (10). Our proof is complete.
The complexity to compute a maximum matching is O(V E), where V and E are the number of nodes and Algorithm 2: Greedy Approximation Algorithm for Cell Association 1 Initialize Tm = 0 and Cm = φ for all BS's ; 2 Set the user set N = {1, · · · , N } ; 3 while N is not empty do 4 Find the BS m ′ that has the minimum Tm: m ′ = arg min m∈(∪ n∈N Bn) Tm ; 5 Find the user n ′ that has the minimum t m ′ ,n : n ′ = arg min n∈{A m ′ ∩N } t m ′ ,n ; Remove n ′ from N ; 10 end edges, respectively. Since we only need to run the matching algorithm once to obtain the association relationship, the total computational complexity of this algorithm is O((M N ) 3.5 L b ), which is better than that of the sequential fixing algorithm.

Proposition 2. The computational complexity of the rounding approximation algorithm is
2) Greedy Approximation Algorithm: We next present a low complexity approximation algorithm, where the BS with the lowest load is greedily chosen and the user whose completion time at this BS is the smallest is assigned to this BS.
By abuse of notation, we define ρ m,n = t m,n /t n and ρ = max {m,n} ρ m,n , which will be used in the optimality analysis. The greedy approximation algorithm is presented in Algorithm 2. In Step 4, we find the candidate BS for users that has the minimum T m . Then we pick the user who has the minimum T m,n at the chosen BS in Step 5. Obviously, the computational complexity of the approximation algorithm is O(M N ), which is much lower than that of sequential fixing.

Proposition 3. The computational complexity of the greedy approximation algorithm is O(M N ).
We have the following lemma for the performance of the greedy approximation algorithm. 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 2, we have The algorithm stops after N iterations. Since T (l+1) = max{T (l) , T (l) m ′ + t m ′ ,n ′ } and T (0) = 0, we conclude that With the closed access stragegy, we set t m,n = ∞, for BS m that user n cannot connect to, for all m, n. The proof follows the same procedure and we have the same conclusion. Combining Lemmas 1 and 4, we have the following theorem regarding the performance of Algorithm 2.

Theorem 2. The greedy approximation algorithm in Algorithm 2 ensures a (2ρ)-approximation of optimal solution.
Proof: The proof is straightforward. We have where T * is the optimal solution and T is the greedy approximation algorithm solution. Note that unlike in Section IV-C1, we have T * ≤ T since there is no relaxation here. From Theorem 2, ρ is an important parameter to the performance of the greedy approximation algorithm. The smaller the ρ, the smaller the optimality gap. In order to make the greedy approximation algorithm solution more competitive, we only allow users to choose from a subset B n of the original BS set. Then we have the new subsets B ′ n and A ′ m as where Γ is a predefined threshold and {1} is the index of the MBS. Γ can also be used to indicate the SINR requirement of users. The set A m is replaced by A ′ m accordingly. This way, the greedy approximation algorithm solution will be

D. Randomized Algorithm
Both the rounding and greedy approximation algorithms are centralized algorithms that require frequent CSI updates. In this section, we introduce a randomized algorithm for the cell association problem. With the randomized algorithm, each user n randomly chooses a subset of B n to connect to. Once the subsets are determined, no information exchange is required among the users. We assume user n connects to BS m with probability p m,n and the expected service time for user n on each BS is identical (i.e., by tuning the p m,n 's), i.e., p m,n t m,n = H n , for all m ∈ B n .
Since a BS with a smaller t m,n should have higher preference, we set p m,n proportional to 1/t m,n . Since each user has to choose a BS to connect to, we have m∈Bn p m,n = 1 for all n. It follows that , for all n.
The expected load on BS m, denoted by T m , is Since users are randomly connected to the BS's, our objective is to minimize the maximum value of the expected load T max .
It can be seen from (14) that minimizing T m is equivalent to reducing the number of users in A m . The randomized algorithm consists of two phases. In Phase I, we use a threshold Λ to obtain the subsets A m and B n .
(16) Note that the subsets A ′ m and B ′ n are different from those defined in (11): Λ is the upper bound of service time t m,n , while Γ is the upper bound on the service time ratios. Thus we have all t m,n ≤ Λ for all n and n ∈ A ′ m . Then we derive the upper bounds for H n , T m and T max as where |A ′ m | and |B ′ n | are the cardinalities of subsets A ′ m and B ′ n , respectively. In Phase II, we aim to further reduce the sizes of A ′ m and B ′ n . From (13), we find that H n ′ gets increased when BS m ′ is removed from set B ′ n ′ and user n ′ is removed from set A ′ m ′ simultaneously. The increase, denoted by ∆ m ′ ,n ′ , is given by For those BS's in the set {m|m ∈ B ′ n ′ , m = m ′ }, their T m 's become larger when BS m ′ is removed from set B ′ n ′ and user n ′ is removed from set A ′ m ′ . On the other hand, T m ′ is reduced by H m ′ ,n ′ according to (14).
The randomized algorithm is presented in Algorithm 3. In Step 2, we find the users that each has more than one BS on their BS list B ′ n . Then from Step 5 to Step 18, we find the BS m ′ with the largest T m ′ and compute the possible maximum load T max m ′ ,n on BS's for all users that might be connected to BS m ′ , assuming user n is removed from A ′′ m ′ . In Step 19, we pick user n ′ with the minimum T max m ′ ,n value. If the value is less than the original T m ′ , we remove the BS-user pair {m ′ , n ′ } from sets A ′′ m ′ and B ′′ n ′ . Otherwise, the algorithm is terminated.  Finally, we have the following theorem on the performance of the randomized algorithm.

Theorem 3. The maximum expected service time achieved by the randomized algorithm is upper bounded by
Proof: The proof is similar to the derivation of (17), but the new upper bound of service time, max n max m∈B ′′ n t m,n , is used, instead of the service time bound Λ.
V. SERVICE SCHEDULING Once the cell associate problem is solved as in Section IV, we then study how to schedule the transmissions of multiple users connecting to the same BS. Since we assume the bandwidth B is fully utilized for transmitting a user's data packet (see (3)), the packets are transmitted consecutively. We need to determine the service order of the users that are associated with the same BS. Consider a tagged BS to which K users are connected. The user service times are {t 1 , t 2 , · · · , t K }. If the service order follows the user index, the average waiting time is given by We have the following theorem to minimize the average waiting time T wait .

Theorem 4.
Given K users with service times {t 1 , t 2 , · · · , t K }, the average waiting time is minimized when the users are served in the increasing order of their service times.
Proof: First we sort the users according to their service times in the increasing order. The ordered service times are denoted by {t ′ 1 , · · · , t ′ K }. Consider two ordered users i and If the positions of i and j are swapped, it is obvious that the waiting times of users from 1 to i − 1 and the users from j to K are not affected and remain 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 served in the increasing order of their service times.

VI. PERFORMANCE EVALUATION
In this section, we evaluate the performance of the proposed cell association and service scheduling algorithms using MAT-LAB simulations. The channel models from [18] are adopted in our simulations. The channel gain (in dB) from the BS's to users can be expressed as 10 log(G m,n ) = −P L m (d m,n ) − u m , where d m,n is the distance from BS m to user n, and u m is the shadowing effect, which is normally distributed with a zero mean and variance δ m . The simulation parameters are presented in Table VI. In the figures, each point in the average of 10 simulation runs; we included 95% confidence intervals as error bars to make the simulation results credible.
We present simulation results for the following two scenarios: (i) open access femtocells; (ii) closed access femtocells. For comparison purpose, we also developed and simulated a selfish scheme and compared it with the proposed schemes. With the selfish scheme, every user simply chooses the BS with the best channel condition to connect to.

A. Open Access Strategy
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 network area. Each user can connect to one of the BS's.
We first examine the impact of the number of users on total service time. In Fig. 2(a), we plot the maximum total service time for the five algorithms along with the lower bound found by solving the relaxed LP. As expected, the more users, the more total service time on BS's. Except for the low bound, the sequential fixing algorithm achieves the smallest total service time. The rounding approximation algorithm has a slightly better performance than the greedy approximation algorithm and the result justifies the approximation ratio proven in Section IV-C. Both approximation algorithms always achieve lower load than both the randomized algorithm and the selfish scheme. We also observe that beyond 50 users, all the proposed algorithms have lower service times than the simple selfish scheme. When number of users becomes larger, the simple selfish scheme becomes less competitive and the rounding approximation algorithm achieves almost 50% less total service time in the case of 80 users.
After cell association, users should be properly scheduled to get service in BS's to minimize average waiting time. In Fig. 2(b), we investigate the impact of the number of users on average waiting time. In the scheme of greedy approximation, randomized algorithm and sequential fixing, we use the service scheduling policy in Section V to schedule users in BS's and obtain the corresponding waiting time. For comparison, we randomly schedule users in BS's in the selfish scheme and rounding approximation scheme. Intuitively, the larger the number of users, the larger the average waiting time. We can see from the figure that, the average waiting time obtained by the greedy approximation algorithm is very close to that by the sequential fixing algorithm, while without appropriate scheduling, the rounding approximation algorithm achieves the largest waiting time, which is almost twice as large as the waiting time achieved by greedy approximation algorithm.
To evaluate the fairness performance, we adopt Raj Jain's fairness index given by J (C 1 , C 2 , · · · , C N ) = where C n is the network throughput for user n [8]. The value of the index ranges from 1/N (worst case) to 1 (best case). It can be seen from Fig. 2(c) that fairness indexes decrease when the number of users is increased. We notice that, the selfish scheme and the randomized algorithm achieve better fairness than the other three schemes. Figs. 2(a) and 2(c) show that from operator's viewpoint, the selfish and the randomized schemes are not preferred since they produce less balanced load on BS's. From users's viewpoint, these two schemes may be appealing due to their fairness performance.
We list the execution times of the five schemes in Table VI-A. We find the execution time increases as the number of users is increased. The selfish scheme always has the smallest execution time, while sequential fixing has the largest execution time. Although the rounding approximation algorithm can achieve smaller load on the BS's, its execution time is greater than that of the greedy approximation algorithm. This result also justifies the complexity analysis for the proposed schemes. The running time of the greedy approximation algorithm and the selfish scheme is always much smaller than other schemes and does not increase obviously with the number of users. For the closed access simulations shown in Section VI-B, the execution times of the proposed algorithms are all much smaller than that shown in Table VI-A, since the user list include fewer users in the closed access case. We omit these results for brevity.

B. Closed Access Strategy
We next investigate the second scenario with closed access femtocells. Now each FBS maintains a user list and only serves the listed users. Note that the MBS will always serve all the users inside its coverage.
In Fig. 3(a), we evaluate 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 depends on the user list at each FBS. In the simulation, we randomly choose the user set A m for BS m. Moreover, the user list at each FBS is further reduced due to the SINR threshold. Consequently, all the proposed algorithms achieve close performance in the closed access scenario. The total service time of the proposed algorithms is close to the low bound in closed access scenario. However, the performance of all the proposed algorithms is better than that of the selfish scheme, as we can see in Fig. 3(a). We next show the impact of the number of users on average waiting time in Fig. 3(b). The scheduling policy setting is the same as that in the open access scenario. The result thus is also similar to the open access case that, the selfish scheme and the rounding approximation scheme achieve the largest waiting time. Actually with proposed optimal service scheduling, the approximation algorithms will achieve as less waiting time as that of the sequential fixing scheme.
Finally, we plot the fairness indices in Fig 3(c). The randomized algorithm, although not better than the selfish scheme, achieves the best performance in fairness than the other proposed schemes. Despite of its good performance in minimizing the maximum service time, the rounding approximation algorithm, is not competitive with respect to fairness. Due to the randomness of user lists at BS's, the confidential intervals are larger than those in the open access scenario.

VII. CONCLUSION
In this paper, we investigated the problem of cell association and service scheduling in two-tier femtocell networks. We developed several algorithms and analyzed their performance. The sequential fixing algorithm achieves the best performance in total service time but it has a relatively high complexity. Then we presented two approximation algorithms with lower complexity and proven approximation ratios. We also proposed a randomized algorithm with a proven performance bound that requires the least information exchange among users. In addition, we addressed the service scheduling problem with an optimal solution. The proposed algorithms were validated with simulations in both open and closed access scenarios.