lower bound 3.3 ★★ (a)Ratio of users that cannot be offloaded (b)Average rate (c)Faimess among users Fig.3.Simulation result for different association algorithms in a 100x 100 meters region,K==5(95%confidence interval). TABLE IV. SIMULATION PARAMETERS Symbol Description Value Simulation region size 100 meters R Transmission range 15 meters Pathloss exponent oSimulation resu P) 40 (macro).20 (femto)dBm ---Curve fitting Transmission power o Noise level -90 dBm 150 Load of femtocells (a)Load distribution for femtocells (b)Number of rounds for Femto- In college admission algorithm,users rank nearby BS based 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 K=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 k=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- Matching achieves much better load balancing where about Fig.3 compares the performance of Femto-Matching with other association algorithms.As the number of femtocells in 1/3 femtocells are serving 5 users,which is exactly equal to 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 1= 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 i= ∑，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 randomly50 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 x 2 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