Base BS1 6s2 the second part log is the penalty on the number of Stations users associated with the BS.Therefore,these two parts can be maintained separately by users and BSs.Using this special structure of the problem,we design a distributed auction-based Users (UI algorithm,called Femto-Matching,as follows: U2 U4 i)Initialization (a)Communication rates for users In the initialization phase,BSs generates VBS Nodes v with pricep吵--logk-- Every user i measures its rates to neighboring BSs and set the utility for associating with BS log r log r jas c+logrii where c is a predefined constant which is large enough to make all utilities larger than initial prices p.All log (r/4) VBSs and users are not assigned in this phase. ii)Auction The auction process is divided into multiple rounds.At the beginning of each round,BS j will announce pricej. (b)Constructed bipartite graph which is the minimum price among all of its VBSs,to the Fig.2.Bipartite graph construction for user association problem neighboring users.Users will calculate the margin mij,which is c+log rii-price;.Each unassigned user find the BSs which optimal solution for subproblem I:optimal resource allocation provide the highest margin m and the second highest margin for a single BS m.User i submits bids of value m;-m to the BS with Lemma 1:The maximum utility sum for BS j,when the highest margin.In case of a tie,user i submits bid of a Kj users j,j2,....jK,are associated to BS j is equal to small value e to one of the BSs.BSs pick the user with the the weight for maximum weighted matching on a subgraph highest bid as the winner and temporarily assign the winner =(U,V,E')of G,induced by the node set U= to the VBS.The price of this VBS is raised by the amount {uj,山2，山k,}.V'={可吲，，，}. of the highest bid and the user previously assigned to this VBS is unassigned.A new round of auction starts after BSs Proof:See Appendix A for the proof of Lemma 1. ■ announce the new temporary assignment scheme.The price and temporary assignment announcement can use the broadcast Lemma 1 leads to the following Theorem: mechanism provided by wireless networks,so that the number of interaction messages can be reduced. Theorem /The maximum utility sum of the PFUA prob- lem in Eq.(1)-(4)is equal to the weight of maximum weighted iii)Termination matching on the constructed user association graph G. The auction process terminates when the assignment Proof:See Appendix B for the proof of Theorem 1. scheme stops changing.BSs will announce the final assign- ment scheme to the neighboring users. Complexity Analysis For a network with N Base Stations and M users,the For example,consider the network in Fig.2.Suppose that computational cost for constructing the user association graph we have ri1 r31 3.r21 r32 r42 2 and c 2. is O(M2N)and extracting the association plan from the At the initial state,prices for VBS nodes will be set as the matching result takes at most O(M)time.There are O(MN) first row in Table II.Both BS1 and BS2 will announce price VBS nodes and O(M)user nodes in the user association of 0 in the first round.UI's highest margin mi is 2+log3 graph.Thus,it takes O(M3N3)time to solve the maximum (associating with vf)and there is no secondary choice for U1. weighted matching problem on the user association graph So,UI will submit bid of 2+log3 to BS1.Similarly,U2 and using Hungarian Algorithm [16].Therefore,the overall time U4 will submit bid of 2+log 2 to BS1 and BS2,respectively. complexity for a centralized algorithm is O(M3N3).Actually, U3 has two choices and BS1 gives higher margin.So,U3 will this complexity bound is quite loose.As we will show in submit bid of 2 log 3-(2+log 2)=log 3/2 to BS1.In Sec.V,usually it is enough to include just O(M)VBS nodes this round,Ul wins the VBS v1,U4 wins the VBS v and the in the user association graph.The complexity can be reduced prices of these VBSs are raised.After the price adjustment, to O(M3)in this case. both BS1 and BS2 announce price of log 4(for vi and vz)in the second round.In this round,U2 and U3 will both bid for v.As the bid submitted by U2 is 2-log 2 which is larger than B.Distributed Auction-based Algorithm the bid of log3/2 submitted by U3.U2 wins irrespective of It is well known that maximum weighted matching problem its lower transmission rate compared to U3.In the third round, can be solved through an auction algorithm in a distributed U3 will compare the margin provided by vf and vz and choose way [17].However,directly applying a general solution leads to associate with BS2.We can verify that this solution actually to complex interactions between users and BSs.We observe maximizes the utility sum in PFUA. that the weight w in Eq.(5)consists of two parts log rij and Detailed algorithm for Femto-Matching is shown in Al- log.The first part log is the rate for users and gorithm 1 and 2.Our algorithm uses the Jacobi version ofUsers Base Stations U1 U2 U3 U4 BS1 BS2 r11 r21 r31 r32 r42 (a) Communication rates for users log (r /4) log (r /4) u u u u v v log r11 v v v 1 2 3 4 1 1 1 2 2 1 2 3 1 2 log r log r31 log r42 42 log (4r11/27) log r 32 log (r11/4) log (r21/4) 32 log (r /4) 31 log (4r /27) 21 log (4r /27) 31 21 (b) Constructed bipartite graph Fig. 2. Bipartite graph construction for user association problem. optimal solution for subproblem I: optimal resource allocation for a single BS. Lemma 1: The maximum utility sum for BS j, when Kj users j1, j2, . . . , jKj are associated to BS j is equal to the weight for maximum weighted matching on a subgraph G0 = (U 0 , V 0 , E0 ) of G, induced by the node set U 0 = {uj1 , uj2 , . . . , ujKj }, V 0 = {v 1 j , v2 j , . . . , v nj j }. Proof: See Appendix A for the proof of Lemma 1. Lemma 1 leads to the following Theorem: Theorem 1: The maximum utility sum of the PFUA prob￾lem in Eq. (1)–(4) is equal to the weight of maximum weighted matching on the constructed user association graph G. Proof: See Appendix B for the proof of Theorem 1. Complexity Analysis For a network with N Base Stations and M users, the computational cost for constructing the user association graph is O(M2N) and extracting the association plan from the matching result takes at most O(M) time. There are O(MN) VBS nodes and O(M) user nodes in the user association graph. Thus, it takes O(M3N3 ) time to solve the maximum weighted matching problem on the user association graph using Hungarian Algorithm [16]. Therefore, the overall time complexity for a centralized algorithm is O(M3N3 ). Actually, this complexity bound is quite loose. As we will show in Sec.V, usually it is enough to include just O(M) VBS nodes in the user association graph. The complexity can be reduced to O(M3 ) in this case. B. Distributed Auction-based Algorithm It is well known that maximum weighted matching problem can be solved through an auction algorithm in a distributed way [17]. However, directly applying a general solution leads to complex interactions between users and BSs. We observe that the weight w k ij in Eq. (5) consists of two parts log rij and log (k−1)k−1 kk . The first part log rij is the rate for users and the second part log (k−1)k−1 kk is the penalty on the number of users associated with the BS. Therefore, these two parts can be maintained separately by users and BSs. Using this special structure of the problem, we design a distributed auction-based algorithm, called Femto-Matching, as follows: i) Initialization In the initialization phase, BSs generates VBS Nodes v k j with price p k j = − log (k−1)k−1 kk . Every user i measures its rates to neighboring BSs and set the utility for associating with BS j as c+log rij where c is a predefined constant which is large enough to make all utilities larger than initial prices p k j . All VBSs and users are not assigned in this phase. ii) Auction The auction process is divided into multiple rounds. At the beginning of each round, BS j will announce pricej , which is the minimum price among all of its VBSs, to the neighboring users. Users will calculate the margin mij , which is c+log rij−pricej . Each unassigned user find the BSs which provide the highest margin m∗ i and the second highest margin m0 i . User i submits bids of value m∗ i − m0 i to the BS with the highest margin. In case of a tie, user i submits bid of a small value ε to one of the BSs. BSs pick the user with the highest bid as the winner and temporarily assign the winner to the VBS. The price of this VBS is raised by the amount of the highest bid and the user previously assigned to this VBS is unassigned. A new round of auction starts after BSs announce the new temporary assignment scheme. The price and temporary assignment announcement can use the broadcast mechanism provided by wireless networks, so that the number of interaction messages can be reduced. iii) Termination The auction process terminates when the assignment scheme stops changing. BSs will announce the final assign￾ment scheme to the neighboring users. For example, consider the network in Fig. 2. Suppose that we have r11 = r31 = 3, r21 = r32 = r42 = 2 and c = 2. At the initial state, prices for VBS nodes will be set as the first row in Table II. Both BS1 and BS2 will announce price of 0 in the first round. U1’s highest margin m∗ 1 is 2 + log 3 (associating with v 1 1 ) and there is no secondary choice for U1. So, U1 will submit bid of 2 + log 3 to BS1. Similarly, U2 and U4 will submit bid of 2 + log 2 to BS1 and BS2, respectively. U3 has two choices and BS1 gives higher margin. So, U3 will submit bid of 2 + log 3 − (2 + log 2) = log 3/2 to BS1. In this round, U1 wins the VBS v 1 1 , U4 wins the VBS v 1 2 and the prices of these VBSs are raised. After the price adjustment, both BS1 and BS2 announce price of log 4 (for v 2 1 and v 2 2 ) in the second round. In this round, U2 and U3 will both bid for v 2 1 . As the bid submitted by U2 is 2−log 2 which is larger than the bid of log 3/2 submitted by U3, U2 wins irrespective of its lower transmission rate compared to U3. In the third round, U3 will compare the margin provided by v 3 1 and v 2 2 and choose to associate with BS2. We can verify that this solution actually maximizes the utility sum in PFUA. Detailed algorithm for Femto-Matching is shown in Al￾gorithm 1 and 2. Our algorithm uses the Jacobi version of