计算机科学与技术（参考文献）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