partition G into a set of subgraphs Gi.In this case,none of where e is a small constant that can be derived from Eq.(21). the edges in the maximum weighted matching will be deleted, There are at most 2 choices for B'.since the number of so the maximum weighted matching on UjG;is equal to femtocells is N.Using the union bound,the chance that there the maximum weighted matching on G.By Lemma 1,there exists a subset B'with A(B')<IB'-(1-nm)M is o(1). exists a scheme for PFUA that has the sum utility equal to Consequently,the number of unmatched users is smaller than the maximum matching weight for each Gi.As nodes in G (1-nm)M with high probability when N-oo.When K>1, are disjoint,we can construct a solution for PFUA with the the number of matched users is always larger than the case utility sum equal to the maximum weighted matching on G. K=I.Therefore,the conclusion of Theorem 2 follows. Combining the result of the two steps,the optimal value for the two problems must be equal to each other. REFERENCES C.Proof of Theorem 2 [1]Cisco,"Cisco visual networking index:Global mobile data traffic forecast update,2013-2018,"Cisco White Paper,2014. Proof:We first consider the case where K =1.Suppose [2]H.Soroush,N.Banerjee.A.Balasubramanian,M.D.Corner,B.N. there are more than (1-nm)M users cannot be matched to Levine,and B.Lynn,"Dome:a diverse outdoor mobile testbed,"in femtocells.Under this condition,with arguments similar to Proceedings of ACM HotPlanet,2009. Hall's marriage Theorem,we can always find a subset of BSs E.Aryafar.A.Keshavarz-Haddad,M.Wang.and M.Chiang."RAT B'C B where its neighborhood size: selection games in hetnets."in Proceedings of IEEE INFOCOM,2013. [4]W.Saad.Z.Han,R.Zheng.M.Debbah,and H.V.Poor."A college W(B)≤IBI-(1-m)M (18) admissions game for uplink user association in wireless small cell networks,"in Proceedings of IEEE INFOCOM.2014. where B'l is the number of BSs in set B'and N(B')is [5]J.G.Andrews,S.Singh,Q.Ye,X.Lin,and H.S.Dhillon,"An overview the number of users within the communication range of BSs of load balancing in HetNets:old myths and open problems."IEEE in B'.Note that we only need to consider subsets with size Wireless Communications,vol.21,no.2,pp.18-25,2014. B'l larger than(1-7m)B,since otherwise the right side of [6 Q.Ye,B.Rong.Y.Chen,M.Al-Shalash,C.Caramanis.and J.An- drews,"User association for load balancing in heterogeneous cellular Eq.(18)is smaller than 0. networks,"Wireless Communications,IEEE Transactions on,vol.12 When BSs are distributed as Poisson Point Process.the 0.6,pp.2706-2716.2013. chance that a user is within the neighborhood of the subset B' [7]S.Singh and J.Andrews,"Joint resource partitioning and offloading of the BSs is given by [22]: in heterogeneous cellular networks,"IEEE Trans.Wireless Commumni- cations,vol.13,no.2,pp.888-901,2014 [8) W.Zhao.S.Wang.C.Wang.and X.Wu."Cell planning for heteroge- PB'=1-e (19) neous networks:An approximation algorithm."in Proceedings of IEEE As users are also distributed as PPP.A(B')follows binomial INFOCOM,2014. distribution with parameters of M and pe. By Chernoff [9]K.Son,S.Chong.and G.Veciana,"Dynamic association for load balancing and interference avoidance in multi-cell networks"IEEE bound,we have: Trans.Wireless Communications,vol.8.no.7,pp.3566-3576,2009. P{W(B的SB1-(1-m)M≤e-D(-1-mPgM [10]F.Kelly,"Charging and rate control for elastic traffic,"Eur with:( transactions on Telecommumications.vol.8,no.1,pp.33-37,1997. [11]F.Khan,LTE for 4G Mobile Broadband:Air Interface Technologies =(g--m）g B1-(1-m】 and Performance.Cambridge University Press,2009. [12] T.Bu,L.Li,and R.Ramjee,"Generalized proportional fair scheduling PB in third generation wireless data networks,"in Proceedings of IEEE 1-4+(1-m) INFOCOM,2006. +(-4g+a-m 1-PB' [13]L.Li,M.Pal,and Y.R.Yang."Proportional fairness in multi-rate wireless LANs,"in Proceedings of IEEE INFOCOM.2008. =-(g--+(g-a- [14]N.Prasad.M.Arslan,and S.Rangarajan,"Exploiting cell dormancy and PB load balancing in LTE HetNets:Optimizing the proportional faimess +-0+-m）小so utility,"in IEEE ICC.2014. (20) [15 "Exploiting cell dormancy and load balancing in LTE HetNets Optimizing the proportional faimess utility,"IEEE Trans.Communica- where H()is the entropy of (in nats).Using the fact that ioms,vol.62.no.10.pp.3706-3722.2014. -He)≥-log2and(1-nm)≤4'≤l,we have: [16]R.E.Burkard,M.Dell'Amico,and S.Martello.Assignment Problems Siam.2009. D(g-a-mPs）>a-ms1-pa 1 -1og2 [17]D.P.Bertsekas,"A new algorithm for the assignment problem," Mathematical Programming.vol 21.no.1.pp.152-171,1981. The strict larger than sign comes from the fact that the first [18]E.Liu,Q.Zhang.and K.K.Leung."Asymptotic analysis of pro- portionally fair scheduling in rayleigh fading."IEEE Trans.Wireless two terms in Eq.(20)cannot reach their minimum value at the Communications,vol.10.no.6.pp.1764-1775,2011. same time.Using Eq.(10)and Eq.(19),we have: [19]J.-S.Ferenc and Z.Neda,"On the size distribution of poisson voronoi cells,"Physica A:Statistical Mechanics and its Applications,vol.385. D(g--）>2 (21) n0.2,Pp.518-526.2007. M [20]S.M.Yu and S.-L.Kim."Downlink capacity and base station density in cellular networks."n Proceddings of IEEE WiOpt.2013.pp.119-124. as≥1-m: [21]K.Nahrstedt and L.Vu,"CRAWDAD data set uiuc/uim (v.2012-01- 24)."Aviable online,http://crawdad.org/uiuc/uim/,Jan.2012. Since M=IN,we get [22]P.Hall,Introduction to the theory of coverage processes. John Wiley P{N(B')≤B'1-(1-m)M}<2-w1+O, (22) Sons,Inc,1988.partition G into a set of subgraphs Gj . In this case, none of the edges in the maximum weighted matching will be deleted, so the maximum weighted matching on [jGj is equal to the maximum weighted matching on G. By Lemma 1, there exists a scheme for PFUA that has the sum utility equal to the maximum matching weight for each Gj . As nodes in Gj are disjoint, we can construct a solution for PFUA with the utility sum equal to the maximum weighted matching on G. Combining the result of the two steps, the optimal value for the two problems must be equal to each other. C. Proof of Theorem 2 Proof: We first consider the case where  = l. Suppose there are more than (1 ￾ ⌘m)M users cannot be matched to femtocells. Under this condition, with arguments similar to Hall’s marriage Theorem, we can always find a subset of BSs B0 ✓ B where its neighborhood size: N (B0 )  l|B0 | ￾ (1 ￾ ⌘m)M, (18) where |B0 | is the number of BSs in set B0 and N (B0 ) is the number of users within the communication range of BSs in B0 . Note that we only need to consider subsets with size |B0 | larger than (1 ￾ ⌘m)|B|, since otherwise the right side of Eq. (18) is smaller than 0. When BSs are distributed as Poisson Point Process, the chance that a user is within the neighborhood of the subset B0 of the BSs is given by [22]: pB0 = 1 ￾ e ￾ ⇡|B0|￾f R2 |B| . (19) As users are also distributed as PPP, N (B0 ) follows binomial distribution with parameters of M and pB0 . By Chernoff bound, we have: P ￾ N (B0 )  l|B0 | ￾ (1 ￾ ⌘m)M  e￾D( l|B0| M ￾(1￾⌘m)||pB0 )M, with: D ✓l|B0 | M ￾ (1 ￾ ⌘m)||pB0 ◆ = ✓l|B0 | M ￾ (1 ￾ ⌘m) ◆ log l|B0| M ￾ (1 ￾ ⌘m) pB0 + ✓ 1 ￾ l|B0 | M + (1 ￾ ⌘m) ◆ log 1 ￾ l|B0| M + (1 ￾ ⌘m) 1 ￾ pB0 = ￾H ✓l|B0 | M ￾ (1 ￾ ⌘m) ◆ + ✓l|B0 | M ￾ (1 ￾ ⌘m) ◆ log 1 pB0 + ✓ 1 ￾ l|B0 | M + (1 ￾ ⌘m) ◆ log 1 1 ￾ pB0 , (20) where H(x) is the entropy of x (in nats). Using the fact that ￾H(x) ￾ ￾ log 2 and (1 ￾ ⌘m)  l|B0 | M  1, we have: D ✓l|B0 | M ￾ (1 ￾ ⌘m)||pB0 ◆ > (1 ￾ ⌘m) log 1 1 ￾ pB0 ￾ log 2. The strict larger than sign comes from the fact that the first two terms in Eq. (20) cannot reach their minimum value at the same time. Using Eq. (10) and Eq. (19), we have: D ✓l|B0 | M ￾ (1 ￾ ⌘m)||pB0 ◆ > log 2 l , (21) as |B0 | |B| ￾ 1 ￾ ⌘m. Since M = lN, we get P ￾ N (B0 )  l|B0 | ￾ (1 ￾ ⌘m)M < 2￾N(1+✏), (22) where ✏ is a small constant that can be derived from Eq. (21). There are at most 2N choices for B0 , since the number of femtocells is N. Using the union bound, the chance that there exists a subset B0 with N (B0 )  l|B0 | ￾ (1 ￾ ⌘m)M is o(1). Consequently, the number of unmatched users is smaller than (1￾⌘m)M with high probability when N ! 1. When  > l, the number of matched users is always larger than the case  = l. Therefore, the conclusion of Theorem 2 follows. REFERENCES [1] Cisco, “Cisco visual networking index: Global mobile data traffic forecast update, 2013–2018,” Cisco White Paper , 2014. [2] H. Soroush, N. Banerjee, A. Balasubramanian, M. D. Corner, B. N. Levine, and B. Lynn, “Dome: a diverse outdoor mobile testbed,” in Proceedings of ACM HotPlanet, 2009. [3] E. Aryafar, A. Keshavarz-Haddad, M. Wang, and M. Chiang, “RAT selection games in hetnets,” in Proceedings of IEEE INFOCOM, 2013. [4] W. Saad, Z. Han, R. Zheng, M. Debbah, and H. V. Poor, “A college admissions game for uplink user association in wireless small cell networks,” in Proceedings of IEEE INFOCOM, 2014. [5] J. G. Andrews, S. Singh, Q. Ye, X. Lin, and H. S. Dhillon, “An overview of load balancing in HetNets: old myths and open problems,” IEEE Wireless Communications, vol. 21, no. 2, pp. 18–25, 2014. [6] Q. Ye, B. Rong, Y. Chen, M. Al-Shalash, C. Caramanis, and J. An￾drews, “User association for load balancing in heterogeneous cellular networks,” Wireless Communications, IEEE Transactions on, vol. 12, no. 6, pp. 2706–2716, 2013. [7] S. Singh and J. Andrews, “Joint resource partitioning and offloading in heterogeneous cellular networks,” IEEE Trans. Wireless Communi￾cations, vol. 13, no. 2, pp. 888–901, 2014. [8] W. Zhao, S. Wang, C. Wang, and X. Wu, “Cell planning for heteroge￾neous networks: An approximation algorithm,” in Proceedings of IEEE INFOCOM, 2014. [9] K. Son, S. Chong, and G. Veciana, “Dynamic association for load balancing and interference avoidance in multi-cell networks,” IEEE Trans. Wireless Communications, vol. 8, no. 7, pp. 3566–3576, 2009. [10] F. Kelly, “Charging and rate control for elastic traffic,” European transactions on Telecommunications, vol. 8, no. 1, pp. 33–37, 1997. [11] F. Khan, LTE for 4G Mobile Broadband: Air Interface Technologies and Performance. Cambridge University Press, 2009. [12] T. Bu, L. Li, and R. Ramjee, “Generalized proportional fair scheduling in third generation wireless data networks,” in Proceedings of IEEE INFOCOM, 2006. [13] L. Li, M. Pal, and Y. R. Yang, “Proportional fairness in multi-rate wireless LANs,” in Proceedings of IEEE INFOCOM, 2008. [14] N. Prasad, M. Arslan, and S. Rangarajan, “Exploiting cell dormancy and load balancing in LTE HetNets: Optimizing the proportional fairness utility,” in IEEE ICC, 2014. [15] ——, “Exploiting cell dormancy and load balancing in LTE HetNets: Optimizing the proportional fairness utility,” IEEE Trans. Communica￾tions, vol. 62, no. 10, pp. 3706 – 3722, 2014. [16] R. E. Burkard, M. Dell’Amico, and S. Martello, Assignment Problems. Siam, 2009. [17] D. P. Bertsekas, “A new algorithm for the assignment problem,” Mathematical Programming, vol. 21, no. 1, pp. 152–171, 1981. [18] E. Liu, Q. Zhang, and K. K. Leung, “Asymptotic analysis of pro￾portionally fair scheduling in rayleigh fading,” IEEE Trans. Wireless Communications, vol. 10, no. 6, pp. 1764–1775, 2011. [19] J.-S. Ferenc and Z. Neda, “On the size distribution of poisson voronoi ´ cells,” Physica A: Statistical Mechanics and its Applications, vol. 385, no. 2, pp. 518–526, 2007. [20] S. M. Yu and S.-L. Kim, “Downlink capacity and base station density in cellular networks,” in Proceddings of IEEE WiOpt, 2013, pp. 119–124. [21] K. Nahrstedt and L. Vu, “CRAWDAD data set uiuc/uim (v. 2012-01- 24),” Aviable online, http://crawdad.org/uiuc/uim/, Jan. 2012. [22] P. Hall, Introduction to the theory of coverage processes. John Wiley & Sons, Inc, 1988