TABLE I. NOTATIONS PFUA can be solved in polynomial time by casting the Symbol Description problem into a matching problem without fixing the number rij average transmission rate of user i under BS j of users in each BS.We divide PFUA into two subproblems: Cij resource allocated by BS j to user i aij association indicator for user i and BS j 1.)Optimize resource allocation for a single BS n the number of users covered by BS j the number of users associated to BSj The goal of this subproblem is to find the optimal propor- maximum number of users that femtocells can serve tional fair share cij when there are K;users associated to BS 入f the density of femtocells 入u the density of users j.This problem can be easily solved as the optimal resource the ratio of users served by femtocells allocation has a closed form solution of cij =1/Kj [6],[3]. Il.Find a global optimal association scheme with a resource allocation plan for each base station j so that the overall system utility is maximized.We choose the The goal of this subproblem is to balance the number logarithm function as our utility function,i.e.,user ihas utility of users associated to each BS so that global utility can be of log(i)when the throughput for user i is zi.It is well known maximized.This subproblem handles the dynamics in Kj for that logarithm utility functions lead to proportional fairness each BS.where larger Ki leads to a more crowded BS and among users and it gives a balanced solution for both fairness lower throughput for each user.This subproblem is solved by and system efficiency [10].In practice,Proportional Fairness constructing a bipartite graph using the solution of subproblem Scheduling(PFS)is also a widely used scheduling algorithm I and finding a maximum weighted matching on it. for LTE eNBs [11]. Construction of the User Association Graph We define the Proportional Fair User Association(PFUA) Given user set and BS set B,we construct a bipartite problem as: graph G=(U,V,E)as follows.We introduce user node u max ∑ilog（∑jCijrijaij): (1) in the first vertex set U for every user iu.We introduce nj s.t ∑：c≤1∈B, (2) virtual BS(VBS)nodesin the second vertex ∑，a≤1i∈4， (3) set V for every BS j B,where n;equals the number of users within communication range of BS j.We add an edge a∈{0,1}，c20i∈4，jeB. (4) (ui,vf)between ui and vf,k =1,...,nj,with weight of: In the above optimization problem,aij is the association (k-1)k-1r indicator for user i and BS j.If user i is associated to BS w log K不 k (5) j,we set aij=1 and otherwise we set aij=0.Therefore, c in Eq.(1)is the total throughput that user ican when user i is within the communication range of BS j. get from the serving BS.Constraint(2)ensures that BS j will As an example,consider the network in Fig.2(a),which not over-utilize its resources.Constraint (3)ensures that each has four users and two BSs with communication rates shown user can only be associated to one BS.The symbols used in this paper are summarized in Table I. beside the corresponding links.Since there are three users U1. U2 and U3 within BSI's communication range,we split BSI IV.ALGORITHM DESIGN to three VBS nodes vi,vi and vi in G.The VBS nodes are connected to user nodes with different weights to account for A.Equivalent Matching Problem the dynamics in the number of users associated to the given PFUA is a mixed integer programming problem where aij BS. can only take integer values.Although a general extention An intuitive explanation of this construction is as follows of the PFUA-the GPF1 problem in [12]has been proven When the first user,say U1,is associated to BS1,the cor- to be NP-hard,the hardness of PFUA is not known until responding user node u will be matched to vf with edge recently.Most existing work on this topic uses two types of weight of logr11.This weight is equal to the utility for U1, relaxations to solve this problem approximately.One way is as BSI will allocate all its resources to U1.When a new user to allow users to associate with multiple BSs at the same U2 is associated with BS1,the proportional fairness scheduler time,so that ai becomes a continuous variable [13].[6].[8] will equally divide the resource of BSI between Ul and and the solution can be approximated via rounding the result U2.Therefore,they get utility of log(r11/2)and log(r21/2). of the relaxed convex optimization problem.The other way respectively.The marginal utility gain for adding U2 is: is to fix the number of users that each BS serves [12],[9]. In this way,the optimal throughput for each user-BS pair is 1og(r11/2)+log(r21/2)-logr11=log(r21/4), (6) also fixed,so that the problem can be directly reduced to a which is equal to the edge weight between u2 and v.By maximum weighted bipartite matching problem.The optimal matching the kth user associated to BSI to VBS node vf,we solution can then be found by exhaustively searching over all possible combinations on the user number for each BS actually keep track of the marginal utility gain that the user While preparing the camera ready version of this paper,we brings to BS1.In this way,we can handle the changing number of associated users in each BS and achieve global optimality found that a parallel work by Prasad et al.also proposed to in utility. use virtual BS based matching scheme to optimally solve the PFUA problem [14],[15].Compared to their work,our auction To prove the equivalence of these two problems,we first based solution reveals structure of this problem and leads to a use the following lemma to show that maximum weighed naturally distributed algorithm. matching on a subgraph of user association graph can find theTABLE I. NOTATIONS Symbol Description rij average transmission rate of user i under BS j cij resource allocated by BS j to user i aij association indicator for user i and BS j nj the number of users covered by BS j Kj the number of users associated to BS j κ maximum number of users that femtocells can serve λf the density of femtocells λu the density of users η the ratio of users served by femtocells with a resource allocation plan for each base station j so that the overall system utility is maximized. We choose the logarithm function as our utility function, i.e., user i has utility of log(xi) when the throughput for user i is xi . It is well known that logarithm utility functions lead to proportional fairness among users and it gives a balanced solution for both fairness and system efficiency [10]. In practice, Proportional Fairness Scheduling (PFS) is also a widely used scheduling algorithm for LTE eNBs [11]. We define the Proportional Fair User Association (PFUA) problem as: max P i log P j cij rijaij , (1) s.t. P i cij ≤ 1 ∀j ∈ B, (2) P j aij ≤ 1 ∀i ∈ U, (3) aij ∈ {0, 1}, cij ≥ 0 ∀i ∈ U, j ∈ B. (4) In the above optimization problem, aij is the association indicator for user i and BS j. If user i is associated to BS j P , we set aij = 1 and otherwise we set aij = 0. Therefore, j cij rijaij in Eq. (1) is the total throughput that user i can get from the serving BS. Constraint (2) ensures that BS j will not over-utilize its resources. Constraint (3) ensures that each user can only be associated to one BS. The symbols used in this paper are summarized in Table I. IV. ALGORITHM DESIGN A. Equivalent Matching Problem PFUA is a mixed integer programming problem where aij can only take integer values. Although a general extention of the PFUA – the GPF1 problem in [12] has been proven to be NP-hard, the hardness of PFUA is not known until recently. Most existing work on this topic uses two types of relaxations to solve this problem approximately. One way is to allow users to associate with multiple BSs at the same time, so that aij becomes a continuous variable [13], [6], [8] and the solution can be approximated via rounding the result of the relaxed convex optimization problem. The other way is to fix the number of users that each BS serves [12], [9]. In this way, the optimal throughput for each user-BS pair is also fixed, so that the problem can be directly reduced to a maximum weighted bipartite matching problem. The optimal solution can then be found by exhaustively searching over all possible combinations on the user number for each BS. While preparing the camera ready version of this paper, we found that a parallel work by Prasad et al. also proposed to use virtual BS based matching scheme to optimally solve the PFUA problem [14], [15]. Compared to their work, our auction based solution reveals structure of this problem and leads to a naturally distributed algorithm. PFUA can be solved in polynomial time by casting the problem into a matching problem without fixing the number of users in each BS. We divide PFUA into two subproblems: I.) Optimize resource allocation for a single BS The goal of this subproblem is to find the optimal propor￾tional fair share cij when there are Kj users associated to BS j. This problem can be easily solved as the optimal resource allocation has a closed form solution of cij = 1/Kj [6], [3]. II.) Find a global optimal association scheme The goal of this subproblem is to balance the number of users associated to each BS so that global utility can be maximized. This subproblem handles the dynamics in Kj for each BS, where larger Kj leads to a more crowded BS and lower throughput for each user. This subproblem is solved by constructing a bipartite graph using the solution of subproblem I and finding a maximum weighted matching on it. Construction of the User Association Graph Given user set U and BS set B, we construct a bipartite graph G = (U, V, E) as follows. We introduce user node ui in the first vertex set U for every user i ∈ U. We introduce nj virtual BS (VBS) nodes v 1 j , v2 j , . . . , v nj j in the second vertex set V for every BS j ∈ B, where nj equals the number of users within communication range of BS j. We add an edge (ui , vk j ) between ui and v k j , k = 1, . . . , nj , with weight of: w k ij = log  (k − 1)k−1 rij k k  , ∀ k, (5) when user i is within the communication range of BS j. As an example, consider the network in Fig. 2(a), which has four users and two BSs with communication rates shown beside the corresponding links. Since there are three users U1, U2 and U3 within BS1’s communication range, we split BS1 to three VBS nodes v 1 1 , v 2 1 and v 3 1 in G. The VBS nodes are connected to user nodes with different weights to account for the dynamics in the number of users associated to the given BS. An intuitive explanation of this construction is as follows. When the first user, say U1, is associated to BS1, the cor￾responding user node u1 will be matched to v 1 1 with edge weight of log r11. This weight is equal to the utility for U1, as BS1 will allocate all its resources to U1. When a new user U2 is associated with BS1, the proportional fairness scheduler will equally divide the resource of BS1 between U1 and U2. Therefore, they get utility of log(r11/2) and log(r21/2), respectively. The marginal utility gain for adding U2 is: log(r11/2) + log(r21/2) − log r11 = log(r21/4), (6) which is equal to the edge weight between u2 and v 2 1 . By matching the kth user associated to BS1 to VBS node v k 1 , we actually keep track of the marginal utility gain that the user brings to BS1. In this way, we can handle the changing number of associated users in each BS and achieve global optimality in utility. To prove the equivalence of these two problems, we first use the following lemma to show that maximum weighed matching on a subgraph of user association graph can find the