TABLEⅡL. PRICE FOR VBS IN THE AUCTION SAMPLE Algorithm 2 Auction procedure for user i rounds 1:Calculate rii for each neighboring BS 0 log4 1og(27/4) 0 10g4 2:while Assignment not finalized do 2+log3 log 4 1og(27/4) 2+log 2 log 4 2+1og3 2 log 2 1og(27/4④ 2+log 2 10g4 3: Collect price;and temporary assignment from neigh- 3 2+1og3 2 log 2 1og(27/4④ 2+log21og(9/2) boring BSs if not temporarily assigned then Algorithm 1 Auction procedure for BS j mi←c+logr-pricejs,j 6: j*←arg maxj{m},m璧←-maxj{m} 1:p吃← -log (k1)*- Vk. 7: misecond largest value in mij 2:while Assignment changes do if m:-m >0 then pricej mink{p},announce pricej 9 Submit bidi mi-m to BS j* k*←arg mink{p} 10: else Collect bid;from neighboring users 11: Submit bidi=s to BS j* winning_user +arg marifbidi 12 end if Temporarily assign VBS with index k*to the 13: end if winning_user and remove the user previously assigned 14:end while with VBS k* p吋`←py十bidwinning.-user 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+log rij}x K/s, 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,x∑k是，when there areK,users 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 functionas(K=∑ki点，we can set the weight for Once the assignment is calculated for a network snapshot, edges connect u;to VBS v as: we can extend the algorithm to handle network dynamics as (k-1)k-1g(k)r follows: wj=log kkg(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 BS,the new user will be served by the vacant VBS.Otherwise the weights for each Base Station,our algorithm can work in 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.WeTABLE II. PRICE FOR VBS IN THE AUCTION SAMPLE rounds p 1 1 p 2 1 p 3 1 p 1 2 p 2 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: p k j ← − log (k−1)k−1 kk , ∀ k. 2: while Assignment changes do 3: pricej ← mink{p k j }, announce pricej 4: k ∗ ← arg mink{p k 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: p k ∗ j ← p k ∗ 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 , ∀j 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 v k j as: w k ij = log  (k − 1)k−1 g(k)rij k kg(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