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 integerFemto-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