RAT GE where ()=-log )As log is an increasing 0.08 convex function when x>1,we can verify that g(k)>0 and 0.0 100 q(k)<q(k+1): 0.04 500 0.0 With the above adjustments.we have weightsfor Number of observed APs all edges in G.We then assign a price pf}to each node in 50 1000 Number of users 000 G.with: (a)Number of observed APs per-scan (b)Ratio of users that cannot be of- floaded ifk =1 P{}={c1-q()if1<k≤K: (15) Fig.5.Trace driven simulation result. 0 if k>Ki pfui}c2+logrij i∈U' (16) deployed HetNets.There are several interesting issues which may deserve further study:The first issue is how does user mo- With this construction,we can verify that: bility affect the performance of user association algorithm.The p{}≥0，p{u}≥0，w≤p{u:}+p{,∈U',k. second is related to our assumption that users are cooperative and give truthful bids.In practical systems,how to design a For any matching M on G'we have: mechanism to prevent malicious users from benefiting through the auction system needs to be considered. ∑w≤∑(pfu,}+p) (u4,)eM(u4,)EM ACKNOWLEDGEMENT ≤∑p{u}+∑p{5} This work is partially supported by NSFC Grants HiEU v∈VW No.61373129,No.91218302,No.61373130,No.61100196, K No.61472185 and No.61321491),key project of Jiangsu =Kc2+∑1 OgTjkj+Kj+】 s(- Research Program Grant (No.BE2013116),NSF of Jiangsu k-1 Province Grant (No.BK20141319),EU FP7 IRSES Mobile- Cloud Project Grant (No.612212)and EU FP7 CROWN Ki(c1+c2)+log (17) project(PIRSES-GA-2013-610524). K As G'is a complete bipartite graph with '=Kj<nj= APPENDIX V,we always have Kj edges in the maximum weighted matching.By removing the weight adjustment factor on edges, A.Proof of Lemma I which is equal toK(c),we can see that Proof:As the optimal cij is equal to 1/Kj [6],[3],the for any matching on G is upper bounded by the right side maximum utility sum for the K;users is given by: of Eq.(13).As the upper bound and lower bound for the maximum weighted matching are the same,the conclusion follows. (g= (13) B.Proof of Theorem I Proof:We prove the equivalence of the optimal solution Now consider the maximum weighted matching in G for PFUA and the maximum weighted matching problem by i)We first show that the weight for maximum weighted showing that their optimal solutions can be converted to each matching in G'is lower bounded by the utility given by other and optimal values of the solutions are equal. Eq.(13).We can construct a matching in G'where user node First,consider the optimal solution of the PFUA problem. uj is matched to vf.The sum of the weights for edges in Given the optimal user association indicator aij,we can this matching is given by: partition the bipartite graph G into a set of subgraphs Gi,with each Gj only contains VBS nodes v of BS j and user nodes that are associated to BS j in the optimal solution of PFUA. Kj All edges connecting VBS nodes and user nodes belonging to log (k-1)k-1r log kR (14) different subgraphs are removed.By Lemma 1,the weight for maximum weighted matching on each subgraph G;is equal to which is equal to the result in Eq.(13). the utility sum for each BSj in PFUA.Therefore,the matching weight sum over all Gi is equal to the maximum utility sum ii)We next show that the utility given by Eq.(13)is also of the optimal solution for PFUA.As UjGj G,maximum an upper bound for the maximum weighted matching in G weighted matching in G is no less than the sum of maximum Consider the dual problem of maximum weighted matching, weighted matching on each subgraph.Therefore,the weight which assigns a non-negative price on each node and find the of maximum weighted matching in G is larger than or equal minimum price vertex cover in G[16].As edges in G'may to the maximum utility sum of the PFUA problem. have negative weights,we add two positive constants,ci and c2.to the weight of each edge in .i.e..w=wc+2. Second,consider the maximum weighted matching on G. to avoid negative weights.We set When the matching is given,we can generate an associate scheme,where user i is associated to BS j if ui is matched c1 =g(Ki),c2 =minflogrii+g(nj), to one of the VBS node vf.In a similar way,we can also0 10 20 30 40 50 0 500 1000 1500 2000 Number of observed APs Occurance of scans (a) Number of observed APs per-scan 1000 1500 2000 0 0.02 0.04 0.06 0.08 0.1 Number of users 1− η College RAT Game FemtoMatching (b) Ratio of users that cannot be of- floaded Fig. 5. Trace driven simulation result. deployed HetNets. There are several interesting issues which may deserve further study: The first issue is how does user mo￾bility affect the performance of user association algorithm. The second is related to our assumption that users are cooperative and give truthful bids. In practical systems, how to design a mechanism to prevent malicious users from benefiting through the auction system needs to be considered. ACKNOWLEDGEMENT This work is partially supported by NSFC Grants (No.61373129, No.91218302, No.61373130, No.61100196, No.61472185 and No.61321491), key project of Jiangsu Research Program Grant (No.BE2013116), NSF of Jiangsu Province Grant (No.BK20141319), EU FP7 IRSES Mobile￾Cloud Project Grant (No.612212) and EU FP7 CROWN project (PIRSES-GA-2013-610524). APPENDIX A. Proof of Lemma 1 Proof: As the optimal cij is equal to 1/Kj [6], [3], the maximum utility sum for the Kj users is given by: XKj k=1 log  rjkj Kj  = log   QKj k=1 rjkj K Kj j   . (13) Now consider the maximum weighted matching in G0 . i) We first show that the weight for maximum weighted matching in G0 is lower bounded by the utility given by Eq. (13). We can construct a matching in G0 where user node ujk is matched to v k j . The sum of the weights for edges in this matching is given by: XKj k=1 log (k − 1)k−1rjkj k k ! = log   QKj k=1 rjkj K Kj j   , (14) which is equal to the result in Eq.(13). ii) We next show that the utility given by Eq.(13) is also an upper bound for the maximum weighted matching in G0 . Consider the dual problem of maximum weighted matching, which assigns a non-negative price on each node and find the minimum price vertex cover in G0 [16]. As edges in G0 may have negative weights, we add two positive constants, c1 and c2, to the weight of each edge in G0 , i.e., w 0k ij = w k ij +c1+c2, to avoid negative weights. We set c1 = q(Kj ), c2 = | min i {log rij}| + q(nj ), where q(k) = − log  (k−1)k−1 kk  . As x log x is an increasing convex function when x ≥ 1, we can verify that q(k) ≥ 0 and q(k) < q(k + 1). With the above adjustments, we have weights w 0k ij ≥ 0 for all edges in G0 . We then assign a price p{·} to each node in G0 , with: p{v k j } =    c1 if k = 1 c1 − q(k) if 1 < k ≤ Kj , 0 if k > Kj (15) p{ui} = c2 + log rij ∀i ∈ U 0 . (16) With this construction, we can verify that: p{v k j } ≥ 0, p{ui} ≥ 0, w0k ij ≤ p{ui} + p{v k j }, ∀i ∈ U 0 , ∀k. For any matching M on G0 we have: X (ui,vk j )∈M w 0k ij ≤ X (ui,vk j )∈M  p{ui} + p{v k j }  ≤ X ui∈U0 p{ui} + X v k j ∈V 0 p{v k j } = Kj c2 + XKj k=1 log rjkj + Kj c1 + XKj k=2 log  (k − 1)k−1 k k  = Kj (c1 + c2) + log   QKj k=1 rjkj K Kj j   . (17) As G0 is a complete bipartite graph with |U 0 | = Kj ≤ nj = |V 0 |, we always have Kj edges in the maximum weighted matching. By removing the weight adjustment factor on edges, which is equal to Kj (c1+c2), we can see that P (ui,vk j )∈M w k ij for any matching on G0 is upper bounded by the right side of Eq. (13). As the upper bound and lower bound for the maximum weighted matching are the same, the conclusion follows. B. Proof of Theorem 1 Proof: We prove the equivalence of the optimal solution for PFUA and the maximum weighted matching problem by showing that their optimal solutions can be converted to each other and optimal values of the solutions are equal. First, consider the optimal solution of the PFUA problem. Given the optimal user association indicator aij , we can partition the bipartite graph G into a set of subgraphs Gj , with each Gj only contains VBS nodes v k j of BS j and user nodes that are associated to BS j in the optimal solution of PFUA. All edges connecting VBS nodes and user nodes belonging to different subgraphs are removed. By Lemma 1, the weight for maximum weighted matching on each subgraph Gj is equal to the utility sum for each BS j in PFUA. Therefore, the matching weight sum over all Gj is equal to the maximum utility sum of the optimal solution for PFUA. As ∪jGj ⊆ G, maximum weighted matching in G is no less than the sum of maximum weighted matching on each subgraph. Therefore, the weight of maximum weighted matching in G is larger than or equal to the maximum utility sum of the PFUA problem. Second, consider the maximum weighted matching on G. When the matching is given, we can generate an associate scheme, where user i is associated to BS j if ui is matched to one of the VBS node v k j . In a similar way, we can also