计算机科学与技术（参考文献）Femto-Matching - Efficient Traffic Offloading in Heterogeneous Cellular Networks

Femto-Matching:Efficient Traffic Offloading in Heterogeneous Cellular Networks Wei Wang,Xiaobing Wu,Lei Xie and Sanglu Lu State Key Laboratory for Novel Software Technology, Department of Computer Science and Technology,Nanjing University.China Email:[ww,wuxb,Ixie,sanglu}@nju.edu.cn Abstract-Heterogeneous cellular networks use small base intrinsic spatial imbalance in network resource provisioning, stations,such as femtocells and WiFi APs,to offload traffic from i.e.,certain areas in the network may have more small cells macrocells.While network operators wish to globally balance the than others.To globally balance the traffic.users should be traffic,users may selfishly select the nearest base stations and "pushed"towards regions with higher small cell density,so make some base stations overcrowded.In this paper,we propose that their traffic gets a better chance to be offloaded by small to use an auction-based algorithm-Femto-Matching,to achieve cells.However,users and small cells only have limited local both load balancing among base stations and fairness among users.Femto-Matching optimally solves the global proportional views on network topology.Therefore,it is hard to achieve fairness problem in polynomial time by transforming it into global balance through distributed algorithms. an equivalent matching problem.Furthermore,it can efficiently In this paper,we design an auction-based algorithm,called utilize the capacity of randomly deployed small cells.Our trace- driven simulations show Femto-Matching can reduce the load of Femto-Matching.to address the above challenges.We show macrocells by more than 30%compared to non-cooperative game that we can achieve global optimality by carefully designing based strategies the auction mechanism.In our algorithm,the load of a BS is reflected by its price and users evaluate BSs based on how I.INTRODUCTION much improvement that the best BS can provide over the secondary choice.We prove that our design leads to an optimal In recent years,there is a trend for wireless cellular net- solution in the sense of global proportional faimess. works to incorporate different types of accessing technologies to meet the fast growing mobile traffic demands [1].Unlike One important observation gained from our design and traditional cellular networks,where a single-tier of macrocells analysis is that global optimization is crucial to the offloading provides coverage over a large area,next generation wireless efficiency for HetNets.With global matching schemes,it is networks utilize multiple tiers of small Base Stations (BSs), possible to fully utilize the available resources provided by ran- including microcells,picocells,femtocells and WiFi APs,to domly deployed small BSs.In this way,the load of macrocells offload mobile traffic from marcocells.In these Heterogeneous can be greatly reduced so that the network deployment cost Networks (HetNets),a single mobile device can be covered by is minimized.Our trace-driven simulations show that Femto- several BSs at the same time.For example,it is not uncommon Matching can reduce the load of macrocells by more than 30% to have more than five WiFi APs available to mobiles in urban compared to non-cooperative game based strategies. areas [2].How to select the right BS among all these nearby The main contributions of this work are as follows: BSs for users becomes a critical issue for HetNets. -We propose a new auction-based algorithm which can There are several challenges that are unique to the serving achieve the optimal solution for the proportional fair user BS selection problem in HetNets.Firstly,users and network association problem. operators have misaligned objectives.Users wish to be associ- ated with a BS which can provide the highest data throughput We are the first to study offloading efficiency in random However,decisions based on users'preference usually lead networks under different user association strategies.We prove to imbalanced network traffic,i.e.,some base stations are that the ratio of users that cannot be offloaded by the optimal overcrowded while others remain idle.To improve network matching scheme is(R)for homogenous Poisson efficiency,network operators would like to globally balance Point Process,where Af is the density of femtocells and R is the traffic.This may be unfair to some users as they are forced the communication range of femtocells. to be associated with a less preferred BS.Due to the mobility of users,these temporarily "bad"choices may lead to long- II.RELATED WORK term benefits in average throughput.However,most existing association algorithms utilize local preferences over a static The load balancing problem in HetNets has been inten- snapshot of the network topology [3],[4],which prevents the sively studied in recent years [5].One of the basic approaches possibility of long-term traffic balancing. to increase the number of users served by small cells is to introduce SINR Biasing.which encourages users to associate Secondly,small cell base stations are randomly deployed. with a small cell even when the perceived SINR of the Unlike macrocells which are deployed with careful planning, small cell is lower than the SINR of the macrocell [6].[7]. small cell base stations,such as femtocell and WiFi APs,are Global optimization algorithms are also proposed in [6],[8] often deployed by users in an ad-hoc manner.This leads to [9],where the problem is formulated as a mixed integer

Femto-Matching: Efficient Traffic Offloading in Heterogeneous Cellular Networks Wei Wang, Xiaobing Wu, Lei Xie and Sanglu Lu State Key Laboratory for Novel Software Technology, Department of Computer Science and Technology, Nanjing University, China Email: {ww, wuxb, lxie, sanglu}@nju.edu.cn Abstract—Heterogeneous cellular networks use small base stations, such as femtocells and WiFi APs, to offload traffic from macrocells. While network operators wish to globally balance the traffic, users may selfishly select the nearest base stations and make some base stations overcrowded. In this paper, we propose to use an auction-based algorithm – Femto-Matching, to achieve both load balancing among base stations and fairness among users. Femto-Matching optimally solves the global proportional fairness problem in polynomial time by transforming it into an equivalent matching problem. Furthermore, it can efficiently utilize the capacity of randomly deployed small cells. Our trace￾driven simulations show Femto-Matching can reduce the load of macrocells by more than 30% compared to non-cooperative game based strategies. I. INTRODUCTION In recent years, there is a trend for wireless cellular net￾works to incorporate different types of accessing technologies to meet the fast growing mobile traffic demands [1]. Unlike traditional cellular networks, where a single-tier of macrocells provides coverage over a large area, next generation wireless networks utilize multiple tiers of small Base Stations (BSs), including microcells, picocells, femtocells and WiFi APs, to offload mobile traffic from marcocells. In these Heterogeneous Networks (HetNets), a single mobile device can be covered by several BSs at the same time. For example, it is not uncommon to have more than five WiFi APs available to mobiles in urban areas [2]. How to select the right BS among all these nearby BSs for users becomes a critical issue for HetNets. There are several challenges that are unique to the serving BS selection problem in HetNets. Firstly, users and network operators have misaligned objectives. Users wish to be associ￾ated with a BS which can provide the highest data throughput. However, decisions based on users’ preference usually lead to imbalanced network traffic, i.e., some base stations are overcrowded while others remain idle. To improve network efficiency, network operators would like to globally balance the traffic. This may be unfair to some users as they are forced to be associated with a less preferred BS. Due to the mobility of users, these temporarily “bad” choices may lead to long￾term benefits in average throughput. However, most existing association algorithms utilize local preferences over a static snapshot of the network topology [3], [4], which prevents the possibility of long-term traffic balancing. Secondly, small cell base stations are randomly deployed. Unlike macrocells which are deployed with careful planning, small cell base stations, such as femtocell and WiFi APs, are often deployed by users in an ad-hoc manner. This leads to intrinsic spatial imbalance in network resource provisioning, i.e., certain areas in the network may have more small cells than others. To globally balance the traffic, users should be “pushed” towards regions with higher small cell density, so that their traffic gets a better chance to be offloaded by small cells. However, users and small cells only have limited local views on network topology. Therefore, it is hard to achieve global balance through distributed algorithms. In this paper, we design an auction-based algorithm, called Femto-Matching, to address the above challenges. We show that we can achieve global optimality by carefully designing the auction mechanism. In our algorithm, the load of a BS is reflected by its price and users evaluate BSs based on how much improvement that the best BS can provide over the secondary choice. We prove that our design leads to an optimal solution in the sense of global proportional fairness. One important observation gained from our design and analysis is that global optimization is crucial to the offloading efficiency for HetNets. With global matching schemes, it is possible to fully utilize the available resources provided by ran￾domly deployed small BSs. In this way, the load of macrocells can be greatly reduced so that the network deployment cost is minimized. Our trace-driven simulations show that Femto￾Matching can reduce the load of macrocells by more than 30% compared to non-cooperative game based strategies. The main contributions of this work are as follows: – We propose a new auction-based algorithm which can achieve the optimal solution for the proportional fair user association problem. – We are the first to study offloading efficiency in random networks under different user association strategies. We prove that the ratio of users that cannot be offloaded by the optimal matching scheme is O(￾￾1/2 f R￾1) for homogenous Poisson Point Process, where ￾f is the density of femtocells and R is the communication range of femtocells. II. RELATED WORK The load balancing problem in HetNets has been inten￾sively studied in recent years [5]. One of the basic approaches to increase the number of users served by small cells is to introduce SINR Biasing, which encourages users to associate with a small cell even when the perceived SINR of the small cell is lower than the SINR of the macrocell [6], [7]. Global optimization algorithms are also proposed in [6], [8], [9], where the problem is formulated as a mixed integer

programming and solved through linear relaxation or brute- force searching. Unlike above global optimization approaches,game theory based algorithms utilize user preference to select the best BS in a distributed way.It is shown in [3]that the BS selection game converges to Nash equilibria when there is only one class of radio access technology.However,only carefully designed game strategies can converge in case there are multiple classes of BSs in the network.When both the preference of the user and the small cells are considered a college admission algorithm can be used to find a stable matching between users and femtocells [4].Unfortunately. (a)Loc ased association these distributed algorithms do not provide any performance guarantee for randomly deployed networks. III.MOTIVATION AND SYSTEM MODEL A.Motivation As a motivating example,Fig.I gives a snapshot of user association plan for randomly distributed users and BSs in a 70x70 meters area.To simplify the illustration,we only draw a single tier of femtocells,where each femtocell can serve up n 40 to 6 users.Fig.1(a)shows the result when users select serving BS based on local preference,e.g.,they try to associate with (b)Globally optimized association the BS which provides the highest throughput as in [3].[4].In the lower-right region of Fig.1(a),there is a cluster of users Fig.1.User association for randomly deployed femtocells (femtocells:blue not associated with any femtocells,since all nearby femtocells stars,users:red dots,association relationship:red or green lines). do not have any vacancy.Although there are abundant lightly B.System Model loaded femtocells in the upper-right region,they cannot serve Hinted by the observations in the previous section,we these "orphan"users due to the limited communication range This imbalanced traffic load for femtocells leads to higher formulate the user association problem as a global optimization traffic burdens on the next tier of BSs.i.e..these "orphan" problem.Consider a HetNet which consists of N BSs in the BS set B and M users in the user set W.Base Stations can be either users have to turn to the microcell tier or the marcocell tier for help. macrocells,picocells,femtocells or WiFi APs.Different types of BSs are characterized by their Radio Access Technologies Fig.1(b)shows a more balanced association plan con (RATs),transmission powers and backhaul bandwidths.We structed through global optimization algorithm.In this case assume that users can switch between multiple BSs,but they lightly loaded femtocell can take over users associated with can only associate with one BS at the same time,due to heavily loaded femtocells in a cascading way so that more the capability limitations of mobile devices.If a user has users can be served by femtocells,as illustrated in the red multiple interfaces that can operate independently,we treat rectangle of Fig.1(b).Some of these femtocells serve users each interface as a separate user. outside their Voronoi cells.This means the global optimization We assume that the achievable throughput for a given user solution forces users to accept a less preferred choice by is determined by two factors,the transmission bit rate and re- associating them to a femtocell which is not the nearest one to sources allocated to the user.Firstly,the wireless transmission them.Existing association algorithms,such as SINR Biasing bit rate for a given user is determined by the received SINR [7]or Game Theory based algorithm [3],cannot sacrifice the of the serving BS.As instantaneous SINR perceived by the welfare of some users to achieve global optimality. user is time-varying due to slow/fast fading and transmission The difference between the user association plans in of nearby BSs/users,we use the long-term average rate to Fig.1(a)and 1(b)leads to drastic difference in the load of characterize the achievable rate.In the following discussions, we assume the average rate that user i can receive from BS j is macrocells.For example,femtocells serve about 80%users in Fig.1(a).In a three tier HetNet which consists of femtocells, rij.Secondly,the throughput for user i is also determined by microcells and macrocells,the marcocell tier needs to serve the amount of wireless resources that BS j allocates for user i. By wireless resources,we mean time slots in TDMA systems, (1-80%)x(1-80%)=4%users,assuming the microcell tier subcarriers in OFDM systems or Resource Blocks (RBs)in can also offload 80%users.If the offloading ratio is improved to 95%as in Fig.1(b),the macrocell only needs to serve LTE.We use ci;to denote the proportion of resources that 0.25%of all users,which is an order of magnitude less than the BSj allocates to user i.Combining these two factors,the previous case.In consequence,fewer costly macrocells need to throughput of user i under BS j can be written as cijrij be deployed or upgraded.Therefore,achieving an offloading The goal of the user association problem for HetNet is ratio close to 100%is crucial for reducing the network cost. to find an optimal association scheme for each user i along

programming and solved through linear relaxation or brute￾force searching. Unlike above global optimization approaches, game theory based algorithms utilize user preference to select the best BS in a distributed way. It is shown in [3] that the BS selection game converges to Nash equilibria when there is only one class of radio access technology. However, only carefully designed game strategies can converge in case there are multiple classes of BSs in the network. When both the preference of the user and the small cells are considered, a college admission algorithm can be used to find a stable matching between users and femtocells [4]. Unfortunately, these distributed algorithms do not provide any performance guarantee for randomly deployed networks. III. MOTIVATION AND SYSTEM MODEL A. Motivation As a motivating example, Fig. 1 gives a snapshot of user association plan for randomly distributed users and BSs in a 70⇥70 meters area. To simplify the illustration, we only draw a single tier of femtocells, where each femtocell can serve up to 6 users. Fig. 1(a) shows the result when users select serving BS based on local preference, e.g., they try to associate with the BS which provides the highest throughput as in [3], [4]. In the lower-right region of Fig. 1(a), there is a cluster of users not associated with any femtocells, since all nearby femtocells do not have any vacancy. Although there are abundant lightly loaded femtocells in the upper-right region, they cannot serve these “orphan” users due to the limited communication range. This imbalanced traffic load for femtocells leads to higher traffic burdens on the next tier of BSs, i.e., these “orphan” users have to turn to the microcell tier or the marcocell tier for help. Fig. 1(b) shows a more balanced association plan con￾structed through global optimization algorithm. In this case, lightly loaded femtocell can take over users associated with heavily loaded femtocells in a cascading way so that more users can be served by femtocells, as illustrated in the red rectangle of Fig. 1(b). Some of these femtocells serve users outside their Voronoi cells. This means the global optimization solution forces users to accept a less preferred choice by associating them to a femtocell which is not the nearest one to them. Existing association algorithms, such as SINR Biasing [7] or Game Theory based algorithm [3], cannot sacrifice the welfare of some users to achieve global optimality. The difference between the user association plans in Fig. 1(a) and 1(b) leads to drastic difference in the load of macrocells. For example, femtocells serve about 80% users in Fig. 1(a). In a three tier HetNet which consists of femtocells, microcells and macrocells, the marcocell tier needs to serve (1￾80%)⇥(1￾80%) = 4% users, assuming the microcell tier can also offload 80% users. If the offloading ratio is improved to 95% as in Fig. 1(b), the macrocell only needs to serve 0.25% of all users, which is an order of magnitude less than the previous case. In consequence, fewer costly macrocells need to be deployed or upgraded. Therefore, achieving an offloading ratio close to 100% is crucial for reducing the network cost. 0 100 200 300 400 500 600 700 0 100 200 300 400 500 600 700 meters meters (a) Local preference based association 0 10 20 30 40 40 60 70 0 10 20 30 40 50 60 70 meters meters (b) Globally optimized association Fig. 1. User association for randomly deployed femtocells (femtocells: blue stars, users: red dots, association relationship: red or green lines). B. System Model Hinted by the observations in the previous section, we formulate the user association problem as a global optimization problem. Consider a HetNet which consists of N BSs in the BS set B and M users in the user set U. Base Stations can be either macrocells, picocells, femtocells or WiFi APs. Different types of BSs are characterized by their Radio Access Technologies (RATs), transmission powers and backhaul bandwidths. We assume that users can switch between multiple BSs, but they can only associate with one BS at the same time, due to the capability limitations of mobile devices. If a user has multiple interfaces that can operate independently, we treat each interface as a separate user. We assume that the achievable throughput for a given user is determined by two factors, the transmission bit rate and re￾sources allocated to the user. Firstly, the wireless transmission bit rate for a given user is determined by the received SINR of the serving BS. As instantaneous SINR perceived by the user is time-varying due to slow/fast fading and transmission of nearby BSs/users, we use the long-term average rate to characterize the achievable rate. In the following discussions, we assume the average rate that user i can receive from BS j is rij . Secondly, the throughput for user i is also determined by the amount of wireless resources that BS j allocates for user i. By wireless resources, we mean time slots in TDMA systems, subcarriers in OFDM systems or Resource Blocks (RBs) in LTE. We use cij to denote the proportion of resources that BS j allocates to user i. Combining these two factors, the throughput of user i under BS j can be written as cij rij . The goal of the user association problem for HetNet is to find an optimal association scheme for each user i along

TABLE I.NOTATIONS PFUA can be solved in polynomial time by casting the Symbol Description problem into a matching problem without fixing the number T西 average transmission rate of user i under BSj resource allocated by BS j to user i of users in each BS.We divide PFUA into two subproblems: cij association indicator for user i and BSj 1.)Optimize resource allocation for a single BS 限 the number of users covered by BS j the number of users associated to BS The goal of this subproblem is to find the optimal propor- maximum number of users that femtocells can serve 入f the density of femtocells tional fair share cij when there are Kj users associated to BS 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]. II.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 i has utility of users associated to each BS so that global utility can be of log(i)when the throughput for user i is i.It is well known maximized.This subproblem handles the dynamics in K;for that logarithm utility functions lead to proportional fairness each BS.where larger K;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 w and BS set B,we construct a bipartite problem as: graph G=(U,V,E)as follows.We introduce user node u max ∑：log(∑，cijrijar), (1) in the first vertex set U for every user iu.We introduce nj 8.t. ∑：≤1ieB, (2) virtual BS (VBS)nodes v,v,...,v in the second vertex ∑，a≤1ie4, (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}，cy≥0i∈4，j∈B. (4) (ui,vf)between ui and vf,k =1,...,nj.with weight of: In the above optimization problem,aii is the association (k-1)k-r indicator for user i and BS j.If user i is associated to BS w哈=log k (5) j,we set aii=1 and otherwise we set ai=0.Therefore. c in Eq.(1)is the total throughput that user i can when user i is within the communication range of BS j. get from the serving BS.Constraint(2)ensures that BS i 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 beside the corresponding links.Since there are three users Ul this paper are summarized in Table I. U2 and U3 within BSI's communication range,we split BS1 IV.ALGORITHM DESIGN to three VBS nodes v.v2 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 Ul,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 v with edge recently.Most existing work on this topic uses two types of weight of logr.This weight is equal to the utility for Ul. relaxations to solve this problem approximately.One way is as BS1 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 aj 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 log(r11/2)+log(r21/2)-logr1 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 vf.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 actually keep track of the marginal utility gain that the user all possible combinations on the user number for each BS brings to BS1.In this way,we can handle the changing number While preparing the camera ready version of this paper,we 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 the

TABLE 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 8j 2 B, (2) P j aij  1 8i 2 U, (3) aij 2 {0, 1}, cij ￾ 0 8i 2 U, j 2 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 2 U. We introduce nj virtual BS (VBS) nodes v1 j , v2 j ,...,vnj j in the second vertex set V for every BS j 2 B, where nj equals the number of users within communication range of BS j. We add an edge (ui, vk j ) between ui and vk j , k = 1,...,nj , with weight of: wk ij = log ✓(k ￾ 1)k￾1rij kk ◆ , 8 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 v1 1, v2 1 and v3 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 v1 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 v2 1. By matching the kth user associated to BS1 to VBS node vk 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

Base a52 the second part logis 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 algorithm.called Femto-Matching.as follows: Users (u1 U2 4 i)Initialization (a)Communication rates for users In the initialization phase,BSs generates VBS Nodesv with price p =-log (1 Every user i measures its rates to neighboring BSs and set the utility for associating with BS jas c+logr where c is a predefined constant which is large enough to make all utilities larger than initial prices p.All 0g4】 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 mj.which is c+log rij-pricej.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. mi.User i submits bids of value mi-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 j1,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 G=(U,V,E)of G,induced by the node set U= to the VBS.The price of this VBS is raised by the amount {,ua,西x,】,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 ri r31 3.r21 r32 r42 =2 and c 2. is O(M-N)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.Ul's highest margin mi is 2 log 3 graph.Thus,it takes O(MN3)time to solve the maximum (associating with vf)and there is no secondary choice for Ul. weighted matching problem on the user association graph So,U1 will submit bid of 2+log 3 to BS1.Similarly,U2 and using Hungarian Algorithm [16].Therefore,the overall time U4 will submit bid of 2+log2 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 v,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 v and v2)in the second round.In this round,U2 and U3 will both bid for B.Distributed Auction-based Algorithm v.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 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 vand v 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 logrj 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 of

Users 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 = (U0 , V 0 , E0 ) of G, induced by the node set U0 = {uj1 , uj2 ,...,ujKj }, V 0 = {v1 j , v2 j ,...,vnj 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 wk 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 vk j with price pk 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 pk 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 v1 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 v1 1, U4 wins the VBS v1 2 and the prices of these VBSs are raised. After the price adjustment, both BS1 and BS2 announce price of log 4 (for v2 1 and v2 2) in the second round. In this round, U2 and U3 will both bid for v2 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 v3 1 and v2 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

TABLE IL PRICE FOR VBS IN THE AUCTION SAMPLE Algorithm 2 Auction procedure for user i rounds p Pi p 1:Calculate ri;for each neighboring BS 0 log4 1og(27/4) log4 2:while Assignment not finalized do 2+1og3 log 4 1og(27/4) 2+log 2 log 4 2 2+1og3 2+1og2 10g(27/4④ 2+1og2 log 4 味 Collect price;and temporary assignment from neigh- 2+1og3 2+1og2 10g(27/4) 2+1og2 log(9/2) boring BSs 又 if not temporarily assigned then Algorithm 1 Auction procedure for BSj 以 m←c+log rij-pricei,i 6 1上←-log--巴 *←argmar{m},m←matj{m} Vk. k msecond largest value in mij 2:while Assignment changes do 8: if m:-m 0 then 3: pricej+mink p},announce pricej Submit bidi m:-m:to BS j* 4 k*←arg mink{p} 10: else 5: Collect bid;from neighboring users 11: Submit bidi=E to BSj* 6 winning_user +argmaribidi 12 end if 7: Temporarily assign VBS with index*to the 13: end if winning_user and remove the user previously assigned 14:end while with VBSk* 8: p←p+bidwinning_user 9 Announce the new temporary assignment and asks neighboring users to bid for that VBS.This may also 10:end while lead to cascaded reassignments.We can reduce the impact of 11:Announce the final assignment this by asking users to be conservative in reassignment,e.g.. requesting new bids to be larger than a given value. When the device moves around and its communication the auction where all unassigned users submit their bids in rate changes,we can treat this case as a simultaneous user the same round.It is also possible to use the Gauss-Seidel leave and join to get the new association plan. version of auction,which allows users to submit bids in an asynchronous manner. It is possible to tune the price to reduce the number of handoffs when user mobility patterns need to be considered. As Femto-Matching essentially solves the dual problem of For example,we can reduce the constant c for a moving user the weighted bipartite matching problem,we can show that the so that handoff happens only when transmission rate of the solution is within Me to the optimal solution in a similar way previous serving BS is lower than a given bound. as in [17].Note that the price for the announced VBS increases by at least e in each round,therefore the maximum number of 2)Multiuser diversity gain rounds for biding is upper bounded by max{c+logrij}xk/e. Proportional Fairness Scheduling (PFS)implemented in where K is the maximum number of VBS nodes that a BS can 3G/4G networks can opportunistically schedule a user with have.By tuning the value of e,we can tradeoff between the better channel quality to improve the average throughput convergence time and the approximation ratio. As users experience independent fading and noise conditions. there is a multiuser diversity gain which can be achieved via C.Practical Issues PFS.For Rayleigh Fading channel,the average throughput for 1)Handling user mobility user i is given as/K,×∑k是：when there are Kusers under a PFS based BS [18].By defining the multiuser diversity One advantage of Femto-Matching is that it can work in dynamical environments where users keep moving around. gain function asg()we can set the weight for Once the assignment is calculated for a network snapshot, edges connect ui to VBS v as: we can extend the algorithm to handle network dynamics as follows: w跨=log (k-1)-1g()r k*g(k-1) (7) -When a new user joins the network,he can use Algorithm 2 to bid for a VBS under the current set of prices.The By a similar procedure as in Sec.IV-A,we can show that our matching algorithm can also achieve the maximum utility calculation of the new association plan only involves nearby for PFUA with this new weight function.As we can adjust BSs and users.In case that there is a vacant VBS in the nearby the weights for each Base Station,our algorithm can work in BS,the new user will be served by the vacant VBS.Otherwise, HetNets which consist of both PFS based BS and non-PFS the new user may "kickout"one of the existing users and based BS at the same time. causes a cascaded handoff which involves multiple users There are two ways to reduce the impact of cascaded handoff 3)Including multiple tiers of BSs The first one is to balance the vacant VBS by increasing the price of the last free VBS of each BS.Therefore,the last free Our solution for PFUA can work for networks with dif- VBS is always reserved for new comers.The other way is ferent types of BSs.Small BSs such as femtocells may have to introduce handoff penalty by increasing the price of VBS limited service capability so that only a limited number of users which is assigned to existing users. can be associated to them.For these small BSs,we can impose a bound on the number of VBS Nodes for the given small -When a user leaves the network,the BS reduces the BS.On the other hand,macrocells have significantly more price of the VBS associated to that user to the initial value resources and higher transmission powers than small BSs.We

TABLE II. PRICE FOR VBS IN THE AUCTION SAMPLE rounds p1 1 p2 1 p3 1 p1 2 p2 2 0 0 log 4 log(27/4) 0 log 4 1 2 + log 3 log 4 log(27/4) 2 + log 2 log 4 2 2 + log 3 2 + log 2 log (27/4) 2 + log 2 log 4 3 2 + log 3 2 + log 2 log (27/4) 2 + log 2 log (9/2) Algorithm 1 Auction procedure for BS j 1: pk j ￾ log (k￾1)k￾1 kk , 8 k. 2: while Assignment changes do 3: pricej mink{pk j }, announce pricej 4: k⇤ arg mink{pk j } 5: Collect bidi from neighboring users 6: winning user arg maxi{bidi} 7: Temporarily assign VBS with index k⇤ to the winning user and remove the user previously assigned with VBS k⇤ 8: pk⇤ j pk⇤ j + bidwinning user 9: Announce the new temporary assignment 10: end while 11: Announce the final assignment the auction where all unassigned users submit their bids in the same round. It is also possible to use the Gauss-Seidel version of auction, which allows users to submit bids in an asynchronous manner. As Femto-Matching essentially solves the dual problem of the weighted bipartite matching problem, we can show that the solution is within M" to the optimal solution in a similar way as in [17]. Note that the price for the announced VBS increases by at least " in each round, therefore the maximum number of rounds for biding is upper bounded by max{c+log rij}⇥/", where  is the maximum number of VBS nodes that a BS can have. By tuning the value of ", we can tradeoff between the convergence time and the approximation ratio. C. Practical Issues 1) Handling user mobility One advantage of Femto-Matching is that it can work in dynamical environments where users keep moving around. Once the assignment is calculated for a network snapshot, we can extend the algorithm to handle network dynamics as follows: – When a new user joins the network, he can use Algorithm 2 to bid for a VBS under the current set of prices. The calculation of the new association plan only involves nearby BSs and users. In case that there is a vacant VBS in the nearby BS, the new user will be served by the vacant VBS. Otherwise, the new user may “kickout” one of the existing users and causes a cascaded handoff which involves multiple users. There are two ways to reduce the impact of cascaded handoff. The first one is to balance the vacant VBS by increasing the price of the last free VBS of each BS. Therefore, the last free VBS is always reserved for new comers. The other way is to introduce handoff penalty by increasing the price of VBS which is assigned to existing users. – When a user leaves the network, the BS reduces the price of the VBS associated to that user to the initial value Algorithm 2 Auction procedure for user i 1: Calculate rij for each neighboring BS 2: while Assignment not finalized do 3: Collect pricej and temporary assignment from neigh￾boring BSs 4: if not temporarily assigned then 5: mij c + log rij ￾ pricej , 8j 6: j⇤ arg maxj{mij}, m⇤ i maxj{mij} 7: m0 i second largest value in mij 8: if m⇤ i ￾ m0 i > 0 then 9: Submit bidi = m⇤ i ￾ m0 i to BS j⇤ 10: else 11: Submit bidi = " to BS j⇤ 12: end if 13: end if 14: end while and asks neighboring users to bid for that VBS. This may also lead to cascaded reassignments. We can reduce the impact of this by asking users to be conservative in reassignment, e.g., requesting new bids to be larger than a given value. – When the device moves around and its communication rate changes, we can treat this case as a simultaneous user leave and join to get the new association plan. It is possible to tune the price to reduce the number of handoffs when user mobility patterns need to be considered. For example, we can reduce the constant c for a moving user so that handoff happens only when transmission rate of the previous serving BS is lower than a given bound. 2) Multiuser diversity gain Proportional Fairness Scheduling (PFS) implemented in 3G/4G networks can opportunistically schedule a user with better channel quality to improve the average throughput. As users experience independent fading and noise conditions, there is a multiuser diversity gain which can be achieved via PFS. For Rayleigh Fading channel, the average throughput for user i is given as rij/Kj ⇥PKj k=1 1 k , when there are Kj users under a PFS based BS [18]. By defining the multiuser diversity gain function as g(Kj ) = PKj k=1 1 k , we can set the weight for edges connect ui to VBS vk j as: wk ij = log ✓(k ￾ 1)k￾1g(k)rij kkg(k ￾ 1) ◆ . (7) By a similar procedure as in Sec. IV-A, we can show that our matching algorithm can also achieve the maximum utility for PFUA with this new weight function. As we can adjust the weights for each Base Station, our algorithm can work in HetNets which consist of both PFS based BS and non-PFS based BS at the same time. 3) Including multiple tiers of BSs Our solution for PFUA can work for networks with dif￾ferent types of BSs. Small BSs such as femtocells may have limited service capability so that only a limited number of users can be associated to them. For these small BSs, we can impose a bound on the number of VBS Nodes for the given small BS. On the other hand, macrocells have significantly more resources and higher transmission powers than small BSs. We

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]

8 (a)Ratio of users that cannot be offloaded (b)Average rate (c)Fairness among users Fig.3.Simulation result for different association algorithms in a 100x 100 meters region.K=I=5(95%confidence interval). TABLE IV. sImuLATiOn PARAMETERS Symbol Deseription Value 山 Simulation region size 100 meters Transmission range 15 meters Pathloss exponent 3 oSimulation resul Transmission power 40 (macro).20(femto)dBm Noise level -90 dBm Load of femtocells In college admission algorithm,users rank nearby BS based (a)Load distribution for femtocells (b)Number of rounds for Femto- Matching (95%confidence interval) on their preferences and submit requests to femtocells in sequence.Femtocells rank received requests and turn down Fig.4.Simulation result for randomly deployed networks with =8.I=5. lower ranked requests when the number of requests exceeds its capacity.In our implementation,we use average commu- Fig.4(a)shows the load distribution for femtocells when nication rate to determine the preference for both users and the capacity of femtocells=8 is larger than the load I= femtocells. 5 for a network with 150 femtcocells.We see that college admission algorithm gives unbalanced results.where more than B.Performance Evaluation 40 femtocells reach their capacity limit of 8 users.Femto- Fig.3 compares the performance of Femto-Matching with Matching achieves much better load balancing where about 1/3 femtocells are serving 5 users,which is exactly equal to other association algorithms.As the number of femtocells in the average load. the simulation region increases,the ratio of users that cannot be offloaded,1-n,remains the same in the associate-to-nearest The number of auction rounds that Femto-Matching used algorithm.On the other hand,Femto-matching has the highest for different network sizes is shown in Fig.4(b).For networks decreasing speed in 1-n among all association algorithms with 150 femtocells and 750 users,Femto-Matching need only In most cases,the proportion of users that cannot be offloaded about 800 rounds of auctions.Using curve fitting.we find is less than half of the RAT selection game solution and it is the number of auction rounds required under our simulation very close to the lower bound,the ratio of users that has no settings is 485.4log N-1617.7.Therefore,our simulation femtocells within communication range. result hints that the number of rounds increase as O(log N). The result of average throughput is given in Fig.3(b) We see that college admission algorithm has the highest C.Trace-Driven Simulation average throughput,as this algorithm tries to assign users We use WiFi trace collected by the UIUC UIM system [21] to their nearest femtocell and users close to femtocells get to verify the usefulness of Femto-Matching in real networks. very high rates.Femto-Matching outperforms RAT game in This database contains more than 22.000 WiFi scan records average throughput.This is because a large number of users are for 28 mobile phones during a period of 3 weeks.Fig.5(a)is assigned to the marcocell in the RAT game algorithm,which the histogram of the number of APs observed per-scan,where makes the macrocell overcrowded and lowers the throughput the average number of APs observed per-scan is 8.39. for those associated with the macrocell.Fig.3(c)shows Jain's fairness index for user throughput,which is defined as: In our trace driven experiment,we treat each unique scan as J) a virtual user and randomly pick M virtual users from all the (12) scans as users to be offloaded.Fig.5(b)compares the number ∑ of users cannot be offloaded when APs can serve up to K=4 users.Both RAT game and Femto-Matching outperform the where ri=;cijrijaij is the throughput for user i.We college admission algorithm in real traces.Femto-Matching see that Femto-Matching has the highest fairness index among can further reduce the number of unmatched users by 30% all algorithms.The reason that college admission algorithm is compared to RAT game. poor in fairness is that users at borders of femtocell are often assigned to the macrocell,which gives them a much smaller VII.CONCLUSION throughput share compared to those associated to a nearby femtocell.Compared to college admission algorithm,Fetmo- In this paper,we proposed a new auction-based user Matching provides reasonable tradeoff by achieving much association algorithm which uses matching between users and better fairness with a small reduction in average throughput. femtocells to improve the offloading efficiency of randomly

50 100 150 0 0.05 0.1 0.15 0.2 0.25 0.3 N 1−η Nearest College RAT game FemtoMatching lower bound (a) Ratio of users that cannot be offloaded 50 100 150 3 3.1 3.2 3.3 3.4 3.5 3.6 N Average rate (bits/s/Hz) College RAT game FemtoMatching (b) Average rate 50 100 150 0.6 0.7 0.8 0.9 1 N Fairness index College RAT game FemtoMatching (c) Fairness among users Fig. 3. Simulation result for different association algorithms in a 100⇥100 meters region,  = l = 5 (95% confidence interval). TABLE IV. SIMULATION PARAMETERS Symbol Description Value L Simulation region size 100 meters R Transmission range 15 meters ↵ Pathloss exponent 3 Pj Transmission power 40 (macro), 20 (femto) dBm N0 Noise level -90 dBm In college admission algorithm, users rank nearby BS based on their preferences and submit requests to femtocells in sequence. Femtocells rank received requests and turn down lower ranked requests when the number of requests exceeds its capacity. In our implementation, we use average commu￾nication rate to determine the preference for both users and femtocells. B. Performance Evaluation Fig. 3 compares the performance of Femto-Matching with other association algorithms. As the number of femtocells in the simulation region increases, the ratio of users that cannot be offloaded, 1￾⌘, remains the same in the associate-to-nearest algorithm. On the other hand, Femto-matching has the highest decreasing speed in 1 ￾ ⌘ among all association algorithms. In most cases, the proportion of users that cannot be offloaded is less than half of the RAT selection game solution and it is very close to the lower bound, the ratio of users that has no femtocells within communication range. The result of average throughput is given in Fig. 3(b). We see that college admission algorithm has the highest average throughput, as this algorithm tries to assign users to their nearest femtocell and users close to femtocells get very high rates. Femto-Matching outperforms RAT game in average throughput. This is because a large number of users are assigned to the marcocell in the RAT game algorithm, which makes the macrocell overcrowded and lowers the throughput for those associated with the macrocell. Fig. 3(c) shows Jain’s fairness index for user throughput, which is defined as: J = ( PM i=1 xi)2 M PM i=1 x2 i , (12) where xi = P j cij rijaij is the throughput for user i. We see that Femto-Matching has the highest fairness index among all algorithms. The reason that college admission algorithm is poor in fairness is that users at borders of femtocell are often assigned to the macrocell, which gives them a much smaller throughput share compared to those associated to a nearby femtocell. Compared to college admission algorithm, Fetmo￾Matching provides reasonable tradeoff by achieving much better fairness with a small reduction in average throughput. 1 2 3 4 5 6 7 8 0 20 40 60 Number of femtocells Load of femtocells College RAT game FemtoMatching (a) Load distribution for femtocells 50 100 150 400 600 800 N Number of rounds Simulation result Curve fitting (b) Number of rounds for Femto￾Matching (95% confidence interval) Fig. 4. Simulation result for randomly deployed networks with  = 8, l = 5. Fig. 4(a) shows the load distribution for femtocells when the capacity of femtocells  = 8 is larger than the load l = 5 for a network with 150 femtcocells. We see that college admission algorithm gives unbalanced results, where more than 40 femtocells reach their capacity limit of 8 users. Femto￾Matching achieves much better load balancing where about 1/3 femtocells are serving 5 users, which is exactly equal to the average load. The number of auction rounds that Femto-Matching used for different network sizes is shown in Fig. 4(b). For networks with 150 femtocells and 750 users, Femto-Matching need only about 800 rounds of auctions. Using curve fitting, we find the number of auction rounds required under our simulation settings is 485.4 log N ￾ 1617.7. Therefore, our simulation result hints that the number of rounds increase as O(log N). C. Trace-Driven Simulation We use WiFi trace collected by the UIUC UIM system [21] to verify the usefulness of Femto-Matching in real networks. This database contains more than 22,000 WiFi scan records for 28 mobile phones during a period of 3 weeks. Fig. 5(a) is the histogram of the number of APs observed per-scan, where the average number of APs observed per-scan is 8.39. In our trace driven experiment, we treat each unique scan as a virtual user and randomly pick M virtual users from all the scans as users to be offloaded. Fig. 5(b) compares the number of users cannot be offloaded when APs can serve up to  = 4 users. Both RAT game and Femto-Matching outperform the college admission algorithm in real traces. Femto-Matching can further reduce the number of unmatched users by 30% compared to RAT game. VII. CONCLUSION In this paper, we proposed a new auction-based user association algorithm which uses matching between users and femtocells to improve the offloading efficiency of randomly

0.1 where ()--log(().As log is an increasing 0.09 FemtoMatchinc convex function when >1,we can verify that g()>0 and 0.06 g(k)Kj pfui}c2+logrij i∈UJ' (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，pu}≥0，w≤p{u}+p{,i∈U',Vk. 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≤∑(pu}+p})》 (ui,v)EM (ui,uf)EM ACKNOWLEDGEMENT ≤∑p{u}+∑p} This work is partially supported by NSFC Grants uiEUI No.61373129.No.91218302.No.61373130.No.61100196. No.61472185 and No.61321491),key project of Jiangsu =K2+∑1 Ogrjkj+K9+ Research Program Grant (No.BE2013116),NSF of Jiangsu k= 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). As G is a complete bipartite graph with=Kj<nj= APPENDIX V,we always have K;edges in the maximum weighted matching.By removing the weight adjustment factor on edges. A.Proof of Lemma 1 which is equal to(e),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）=s (13) B.Proof of Theorem 1 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 showing that their optimal solutions can be converted to each i)We first show that the weight for maximum weighted other and optimal values of the solutions are equal. matching in G'is lower bounded by the utility given by 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 v.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 Gi only contains VBS nodes v 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 (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 G;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 U;G;C 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,c and c2.to the weight of each edge in G.i.e=w+c+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=q(Kj),c2 =minflog rij+q(nj), to one of the VBS node vf.In a similar way,we can also

0 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 0 @ QKj k=1 rjkj KKj j 1 A . (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 vk j . The sum of the weights for edges in this matching is given by: XKj k=1 log (k ￾ 1)k￾1rjkj kk ! = log 0 @ QKj k=1 rjkj KKj j 1 A , (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., w0k ij = wk ij +c1+c2, to avoid negative weights. We set c1 = q(Kj ), c2 = | mini {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) : c1 if k = 1 c1 ￾ q(k) if 1 Kj (15) p{ui} = c2 + log rij 8i 2 U0 . (16) With this construction, we can verify that: p{vk j } ￾ 0, p{ui} ￾ 0, w0k ij  p{ui} + p{vk j }, 8i 2 U0 , 8k. For any matching M on G0 we have: X (ui,vk j )2M w0k ij  X (ui,vk j )2M ⇣ p{ui} + p{vk j } ⌘  X ui2U0 p{ui} + X vk j 2V 0 p{vk j } = Kj c2 + XKj k=1 log rjkj + Kj c1 + XKj k=2 log ✓(k ￾ 1)k￾1 kk ◆ = Kj (c1 + c2) + log 0 @ QKj k=1 rjkj KKj j 1 A . (17) As G0 is a complete bipartite graph with |U0 | = 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 )2M wk 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 vk 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 vk j . In a similar way, we can also

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')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 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