TABLE IIL OFFLOADING EFFICIENCY FOR THE adjust the rate ri;for the given macrocell j by multiplying the ASSOCIATE-TO-NEAREST ALGORITHM rate calculated through SINR with a modification factor b;to reflect that the marcocell j has more wireless resources than K=1K=2K=3K=4K=5 三6 0.58510.84740.94830.9835 00g0 0.9985 small BSs. 0.6636 0.8230 0.9110 0.9568 0.9796 0.6980 0.8132 0.8877 0.9341 V.OFFLOADING EFFICIENCY ANALYSIS 0.71760.8080 08721 5 0.7303 0.8048 In this section,we study the efficiency of association 6 0.7393 algorithms in a randomly deployed network to get a better such as Femto-Matching can achieve the optimal offloading understanding about the performance of matching based solu- efficiency.This is because offload efficiency is maximized tions.We mainly focus on the metric of offloading efficiency n.which is defined as the ratio of users which can be served when the size of matching between users and femtocells is maximized.By using a matching algorithm considering by the femtocell tier under the given association scheme.In the global topology,we can fully utilize the capability of a network with multiple tiers,offloading efficiency determines how many users should be served by the higher tiers of BSs femtocells,as shown by Theorem 2. as discussed in Sec. Theorem 2:The offloading efficiency of global matching based association algorithm is lower bounded by: We assume that both femtocells and the users are dis- tributed as homogenous Poisson Point Process (PPP)with (1+)1og2 intensity of Af and A.respectively.We define the load factor m=1- (10) I as AuAAf.i.e..the average number of users that a femtocell πlArR should serve.We further assume that each femtocell can serve with high probability,when both users and femtocell are at most k users within its communication range of R.Under distributed according to PPP with intensity of A and Af with these capacity and communication range constraints,we can ≥I. analytically compare the efficiency of different association algorithms Proof:See Appendix C for the proof of Theorem 2. First,consider the association scheme which tries to asso- Theorem 2 shows that the offloading efficiency quickly ciate users to the nearest femtocell.If the nearest femtocell is approaches 1 when the network density increases with a fixed full,the user is associated to the higher tier of cells. value of K and l.This hints that global matching algorithms could be a powerful way to smooth out the randomness in Define PIN=k}as the probability that the Voronoi user/femtocell distributions.The actual performance compari- cell of a femtocell contains k users.We have the offloading son between global matching algorithm and local preference efficiency of the associate-to-nearest algorithm as: based algorithms is studied via simulations in Sec.VI. =k+k P(N =h VI.SIMULATION RESULTS A.Simulation Setup = (-k)PN=k) (8) Our simulation is conducted in randomly deployed net- k=0 works within a 100 x 100 meters region.We assume that the marcocell is located at the center of the network while Unfortunately,there is no closed form solution for PIN=k users and femtocells are distributed according to PPP.The the best known approximation is given by [19].[20]: communication rate for a user i under BS j is set to: P{N,=k}= 3.53.5T(k+3.5)1 T(3.5)(L+3.5)k+3.3 (9) (11) Nod号 where I(x)is the Gamma function. where dij is the distance between user and BS.The meaning We observe that the offloading efficiency nn is only related of other parameters and the default simulation setting is to k and l.Thus,it cannot be improved by increasing the summarized in Tab.IV. network density while keeping K and fixed.This implies that the offloading efficiency for the associate-to-nearest algorithm We compare our Femto-Matching algorithm with three is governed by the intrinsic randomness in node distribution association algorithms: Table III gives numerical results for nn.When K=l,i.e., -Associate-to-nearest femtocells have just enough resources to serve all users, the associate-to-nearest algorithm have offloading efficiency This algorithm associates users to the nearest femtocell,as lower than 75%.To achieve offloading efficiency higher than described in Sec.V. 95%,we often need K>2l,which means the capacity of femtocells should be over-provisioned by two times than the RAT selection game 3] actual number of users to be served. In this algorithm,users use their expected throughput as their preference.Users always try to switch to a BS which Algorithms using local preference can improve over the provides higher expected throughput. naive associate-to-nearest algorithm by associating users to nearby vacant femtocells.However,global matching schemes -College admission [4]adjust the rate rij for the given macrocell j by multiplying the rate calculated through SINR with a modification factor bj to reflect that the marcocell j has more wireless resources than small BSs. V. OFFLOADING EFFICIENCY ANALYSIS In this section, we study the efficiency of association algorithms in a randomly deployed network to get a better understanding about the performance of matching based solu￾tions. We mainly focus on the metric of offloading efficiency ⌘, which is defined as the ratio of users which can be served by the femtocell tier under the given association scheme. In a network with multiple tiers, offloading efficiency determines how many users should be served by the higher tiers of BSs, as discussed in Sec. III. We assume that both femtocells and the users are dis￾tributed as homogenous Poisson Point Process (PPP) with intensity of ￾f and ￾u, respectively. We define the load factor l as ￾u/￾f , i.e., the average number of users that a femtocell should serve. We further assume that each femtocell can serve at most  users within its communication range of R. Under these capacity and communication range constraints, we can analytically compare the efficiency of different association algorithms. First, consider the association scheme which tries to asso￾ciate users to the nearest femtocell. If the nearest femtocell is full, the user is associated to the higher tier of cells. Define P{Nv = k} as the probability that the Voronoi cell of a femtocell contains k users. We have the offloading efficiency of the associate-to-nearest algorithm as: ⌘n = 1 l X k=0 kP{Nv = k} +  X1 k=+1 P{Nv = k} ! = 1 l  ￾X k=0 ( ￾ k)P{Nv = k} ! . (8) Unfortunately, there is no closed form solution for P{Nv = k}, the best known approximation is given by [19], [20]: P{Nv = k} = 3.53.5￾(k + 3.5)l k ￾(3.5)k!(l + 3.5)k+3.5 , (9) where ￾(x) is the Gamma function. We observe that the offloading efficiency ⌘n is only related to  and l. Thus, it cannot be improved by increasing the network density while keeping  and l fixed. This implies that the offloading efficiency for the associate-to-nearest algorithm is governed by the intrinsic randomness in node distribution. Table III gives numerical results for ⌘n. When  = l, i.e., femtocells have just enough resources to serve all users, the associate-to-nearest algorithm have offloading efficiency lower than 75%. To achieve offloading efficiency higher than 95%, we often need  > 2l, which means the capacity of femtocells should be over-provisioned by two times than the actual number of users to be served. Algorithms using local preference can improve over the naive associate-to-nearest algorithm by associating users to nearby vacant femtocells. However, global matching schemes TABLE III. OFFLOADING EFFICIENCY FOR THE ASSOCIATE-TO-NEAREST ALGORITHM l  = 1  = 2  = 3  = 4  = 5  = 6 1 0.5851 0.8474 0.9483 0.9835 0.9950 0.9985 2 0.6636 0.8230 0.9110 0.9568 0.9796 3 0.6980 0.8132 0.8877 0.9341 4 0.7176 0.8080 0.8721 5 0.7303 0.8048 6 0.7393 such as Femto-Matching can achieve the optimal offloading efficiency. This is because offload efficiency is maximized when the size of matching between users and femtocells is maximized. By using a matching algorithm considering the global topology, we can fully utilize the capability of femtocells, as shown by Theorem 2. Theorem 2: The offloading efficiency of global matching based association algorithm is lower bounded by: ⌘m = 1 ￾ s (1 + l) log 2 ⇡l￾fR2 , (10) with high probability, when both users and femtocell are distributed according to PPP with intensity of ￾u and ￾f with  ￾ l. Proof: See Appendix C for the proof of Theorem 2. Theorem 2 shows that the offloading efficiency quickly approaches 1 when the network density increases with a fixed value of  and l. This hints that global matching algorithms could be a powerful way to smooth out the randomness in user/femtocell distributions. The actual performance compari￾son between global matching algorithm and local preference based algorithms is studied via simulations in Sec. VI. VI. SIMULATION RESULTS A. Simulation Setup Our simulation is conducted in randomly deployed net￾works within a 100 ⇥ 100 meters region. We assume that the marcocell is located at the center of the network while users and femtocells are distributed according to PPP. The communication rate for a user i under BS j is set to: rij = log 1 + Pj N0d↵ ij ! , (11) where dij is the distance between user and BS. The meaning of other parameters and the default simulation setting is summarized in Tab. IV. We compare our Femto-Matching algorithm with three association algorithms: – Associate-to-nearest This algorithm associates users to the nearest femtocell, as described in Sec.V. – RAT selection game [3] In this algorithm, users use their expected throughput as their preference. Users always try to switch to a BS which provides higher expected throughput. – College admission [4]