Chao Xu

Min S Sheng

Vineeth Varma

Tony Q S Quek

Wireless service provider selection and bandwidth resource allocation in multi-tier HCNs

published or not. The documents may come

Wireless Service Provider Selection and Bandwidth

Resource Allocation in Multi-tier HCNs Chao Xu, Min Sheng, Member, IEEE, Vineeth S. Varma, Tony Q.S. Quek, Senior Member, IEEE Abstract-In this work, the inter-linked problems of wireless service provider (WSP) selection by users and bandwidth allocation by WSPs in multi-tier heterogeneous cellular networks (HCNs) are addressed. This paper employs the approach combining stochastic geometry and game theory to solve these problems. Particularly, the expected average achievable rate for each user is calculated by modeling the distributions of users and base stations (BSs) as independent homogeneous Poisson Point Process (PPP) and a hierarchical game framework is presented to investigate the interactions between users and WSPs. In this framework, the evolutionary game, non-cooperative game and multi-leader multi-follower Stackelberg game models are adopted to formulate the competition among users, competition among WSPs and interaction among users and WSPs, respectively. Moreover, for the formulated evolutionary game, the evolutionary equilibrium (EE) was investigated and its asymptotically stability was analyzed after deriving its closed form expression. Then, conditioned on the obtained EE, a non-cooperative spectrum bandwidth allocation game (N-BAG) has been formulated to investigate the bandwidth allocation of WSPs. The existence of Nash equilibrium (NE) for N-BAG has been proven and an offline algorithm to achieve the equilibrium state was proposed. Finally, simulation results verify the validity of the analysis and demonstrate that a unique NE would be achieved by the HCNs adopting the proposed scheme.

Index Terms-Heterogenous cellular networks (HCNs), operator selection, bandwidth allocation, evolutionary game, evolutionary equilibrium (EE).

I. INTRODUCTION

A. Motivation

Heterogeneous cellular networks (HCNs) are regarded as a promising approach to cater for the increased demand of high-data-rate services and requirement of ubiquitous access. Augmenting an existing macro-cell covered by a large BS by deploying small coverage cellular networks with high density can potentially dramatically increase the network capacity without incurring a high operation cost [START_REF] Damnjanovic | A survey on 3GPP heterogeneous networks[END_REF]- [START_REF] Xu | Distributed subchannel allocation for interference mitigation in OFDMA femtocells: A utility-based learning approach[END_REF]. In this light, the muti-tier HCN is a novel network structure for the future. Particularly, in contrast to the traditional pure macro cellular network, the HCN would consist of high power macro BSs (MBSs) as well as various classes of low power nodes, which may include micro BSs (often called eNBs), pico BSs (PBS), femto BSs (FBSs), and possibly future radiating elements [START_REF] Andrews | Femtocells: Past, present, and future[END_REF].

C. Xu and M. Sheng are with the State Key Laboratory of Integrated Service Networks, Institute of Information Science, Xidian University, Xi'an, Shaanxi, 710071, China (e-mail: {cxu, msheng}@mail.xidian.edu.cn).

T. Q. S. Quek and Vineeth S. Varma are with the Singapore University of Technology and Design and the Institute for Infocomm Research, Singapore (e-mail: tonyquek@sutd.edu.sg and vineethsvarma@gmail.com).

While deploying such an HCN, it is essential to analyze the system-level performance and investigate the impact of different system parameters to obtain some design insights. Hence, analytically tractable models would be of great interest in this scenario. In contrast to the hexagonal grid model widely applied to evaluate traditional well-planned single-tier cellular networks, an alternate approach based on stochastic geometry was recently proposed, with which the transmitting nodes (e.g., BSs) are modeled as randomly located points through a Poisson point process (PPP) [START_REF] Andrews | Femtocells: Past, present, and future[END_REF]. Compared to the femto-cells which may be randomly deployed, it seems somewhat counterintuitive to model macro cellular networks as a PPP. However, the accuracy of this tractable model has been verified through empirical validation in recent works like [START_REF] Andrews | A tractable approach to coverage and rate in cellular networks[END_REF]. To this end, based on such a tractable, yet reasonable assumption that BSs are distributed according to independent PPPs, the performance of HCNs can be efficiently studied.

This work studies the interactions between the users and the wireless service providers (WSPs) in an environment where HCNs are deployed by different WSPs. Each WSP determines the bandwidth allocation for each service while the users decide which WSP to subscribe to. Naturally, as each user and WSP are independent decision makers, this results in a situation best modeled through game theory.

B. Related works

The signal-to-interference-plus-noise-ratio (SINR) as well as other system key performance indexes (KPIs), e.g., coverage probability and throughput, have been analyzed in studies [START_REF] Dhillon | Modeling and analysis of K-tier downlink heterogeneous cellular networks[END_REF]- [START_REF] Mukherjee | Distribution of downlink SINR in heterogeneous cellular networks[END_REF]. On top of such stochastic geometry based performance analysis, some efficient spectrum resource allocation strategy have be proposed for heterogenous wireless networks with the dedicated-channel deployment [START_REF] Chandrasekhar | Spectrum allocation in tiered cellular networks[END_REF]- [START_REF] Lin | Joint spectrum partition and user association in multitier heterogeneous networks[END_REF]. Specifically, in [START_REF] Chandrasekhar | Spectrum allocation in tiered cellular networks[END_REF], [START_REF] Huang | Spectrum sharing between cellular and mobile ad hoc networks: Transmission-capacity trade-off[END_REF] a two-tier heterogeneous network was considered where the disjoint spectrum resources were allocated to different tiers to eliminate cross-tier interference and its optimal spectrum allocation strategy was investigated. Authors in [START_REF] Cheung | Throughput optimization, spectrum allocation, and access control in two-tier femtocell networks[END_REF] focused on the HCN consisting of macrocells and femtocells, and studied the optimal spectrum allocation strategy for both the open and closed access modes. Although only the specific case of two-tier was studied, some analysis results obtained in [START_REF] Cheung | Throughput optimization, spectrum allocation, and access control in two-tier femtocell networks[END_REF] can also be generalized to multi-tier HCNs. The spectrum partition and user association were jointly studied for multiiter HCNs in [START_REF] Lin | Joint spectrum partition and user association in multitier heterogeneous networks[END_REF], where the cell range expansion scheme was adopted for load balancing. Besides these works, the service selection as well as bandwidth allocation for the two-tier femtocell network has also been studied from the economic perspective in [START_REF] Duan | Economics of femtocell service provision[END_REF].

In all the above mentioned works [START_REF] Chandrasekhar | Spectrum allocation in tiered cellular networks[END_REF]- [START_REF] Duan | Economics of femtocell service provision[END_REF], they have the common point in that they only consider the case where there only exist one WSP deploying all the tiers of networks, i.e., a monopoly. However, in practice there are generally multiple WSPs coexisting, who would deploy their own individual HCNs and hence have to compete with each other to attract more users for higher revenue. As a mathematical tool for analyzing the the conflict and cooperation among autonomous agents, game theory [START_REF] Myerson | Game theory: analysis of conflict[END_REF] has been widely adopted to formulate and study the interactions among service operators [START_REF] Sengupta | An economic framework for dynamic spectrum access and service pricing[END_REF]- [START_REF] Jiang | Optimal pricing strategy for operators in cognitive femtocell networks[END_REF]. Wherein, some of these works have also focused on the HCN based scenarios [START_REF] Chen | Utility-aware refunding framework for hybrid access femtocell network[END_REF]- [START_REF] Jiang | Optimal pricing strategy for operators in cognitive femtocell networks[END_REF]. Nevertheless, the major differences between these studies and ours are two fold: (i) the type of HCN considered in [START_REF] Chen | Utility-aware refunding framework for hybrid access femtocell network[END_REF]- [START_REF] Jiang | Optimal pricing strategy for operators in cognitive femtocell networks[END_REF] is different to that studied in ours and previous studies [START_REF] Dhillon | Modeling and analysis of K-tier downlink heterogeneous cellular networks[END_REF]- [START_REF] Lin | Joint spectrum partition and user association in multitier heterogeneous networks[END_REF]. Specifically, different tiers have been deployed by different WSPs and each WSP only provides one service to users. Hence, their main concerns are spectrum leasing among different WSPs. Our work however jointly studies the WSP selection of users and spectrum allocation of WSPs. (ii) Beside game theory, the tools from stochastic geometry have also been applied in our work to study the behavior of users as well as WSPs. Compared with the pure game theory based methodology focusing on the deterministic model [START_REF] Chen | Utility-aware refunding framework for hybrid access femtocell network[END_REF]- [START_REF] Jiang | Optimal pricing strategy for operators in cognitive femtocell networks[END_REF], the analysis combining game theory and stochastic geometry would provide more design insights to system designers or WSPs. A similar idea has also been adopted by recent reseraches [START_REF] Kwon | A game-theoretic approach for energy-efficient power control in spectrum sharing networks[END_REF] and [START_REF] Zhu | An evolutionary game for distributed resource allocation in self-organizing small cells[END_REF], where the distributed power control and sub-channel selection have been addressed, respectively.

C. Contributions

In order to avoid the cross-tier interference in HCNs, a dedicated-channel deployment can be adopted, with which the orthogonal radio resource will be allocated to different tiers. Though this deployment is sub-optimal from the spectral efficiency standpoint, it is a relative simple approach that can be conveniently implemented in practice [START_REF] Lopez-Perez | Enhanced intercell interference coordination challenges in heterogeneous networks[END_REF], [START_REF] Lin | Macro-femto heterogeneous network deployment and management: From business models to technical solutions[END_REF]. In this case, how to properly split the the precious but scarce spectrum bandwidth resources 1 and allocate them to different tiers is one fundamental and important issue directly faced by the WSPs [START_REF] Lopez-Perez | Enhanced intercell interference coordination challenges in heterogeneous networks[END_REF], [START_REF] Lin | Macro-femto heterogeneous network deployment and management: From business models to technical solutions[END_REF]. With a better allocation strategy, the WSP can provide a better quality of service, attract more subscribers (i.e., gain a larger market share) and finally achieve higher revenue.

Here, we consider the scenario consisting of multiple HCNs deployed by different WSPs and each tier favored by a certain population of the users. We think this scenario is practical because, on one hand, competition among multiple WSPs is common in many countries, for instance, Sprint, Verizon as well as AT&T are coexisting in the US. On the other hand, the number of users in the market is large and may change, so from the system-level perspective, it is more sensible to treat them using a statistical method. Furthermore, while a stationary user will prefer to connect to a femto-cell nearby, a highly mobile user would connect to a macro-cell in order to avoid frequent handovers. Thus, on average the total population of users can be divided into parts that prefer each tier of the heterogenous network; each user can select the best WSP for any tier. Besides that, to attract more users and further obtain higher revenue, each WSP needs to decide how to allocate his own available spectrum resource to different tiers by fully considering both the behavior of users and other WSPs. For this reason, there are two levels of competitions and a cyclic dependency having to be addressed, i.e., the competition among users, the competition among WSPs, and the coupling between the behavior of populations of users and WSPs. This makes the spectrum resource partition problem nontrivial.

The main contributions of this work can be summarized as follows.

1) We systematically analyze the average achievable rate can be provided by WSPs with the stochastic geometry based approach. Moreover, we present a hierarchical game framework to investigate the interactions in the multi-tier HCNs. Particularly, in the lower level of the framework we formulate the WSP selection of users as an evolutionary game [START_REF] Cressman | Evolutionary dynamics and extensive form games[END_REF] and meanwhile, in the upper level the competition among different WSPs is modeled as a Non-cooperative spectrum Bandwidth Allocation Game (N-BAG). Additionally, the cyclic dependency between the users and WSPs is studied by applying the multi-leader multi-follower Stackelberg game theory. With the proposed framework, WSPs can capture the equilibrium of users and further guide the deployment of HCNs. 2) For the formulated evolutionary service selection game, we consider the evolutionary equilibrium (EE) as the solution, investigate the uniqueness and get the close form expression of the interior EE. Furthermore, we prove that the interior EE is also the evolutionary stable strategy (ESS) which is asymptotical stable, i.e., when ESS is achieved in the population, a small amount of invaders adopting other strategies instead of the ESS can finally be eliminated. 3) Simulation results show that, compared with the solution brought by other three approaches, when WSPs allocate their own spectrum resources by adopting our proposed strategy, an efficient and fair equilibrium solution can be achieved.

The outline of this paper is as follows. In Section II, the description of system model and formulation of the hierarchical game framework are given. Subsequently, Section III presents the evolutionary WSP selection game and studies its solutions. In Section IV, we present the N-BAG, analyze the existence of Nash equilibrium (NE), and develop an algorithm to obtain the NE for this game. Some numerical simulation results are presented and analyzed in Section V and finally, conclusions are drawn in Section VI.

II. SYSTEM MODEL AND THE HIERARCHICAL GAME FRAMEWORK

In this work, we consider an area of interest where a total of K different service would be provided to users (e.g., the macrocell service, picocell service and femtocell service) by N different WSPs having deployed N different HCNs. Additionally, for each HCN n, there are K n tiers, each of which has the BSs of a particular class, such as macrocell BSs (MBSs) or picocell BSs (PBSs). Note that the BSs in different tiers may be differ among each other due to differences in the transmit power, coverage area and spatial density [START_REF] Dhillon | Modeling and analysis of K-tier downlink heterogeneous cellular networks[END_REF], [START_REF] Jo | Heterogeneous cellular networks with flexible cell association: A comprehensive downlink SINR analysis[END_REF]. An illustration of a 3-tier HCN is shown in Fig. 1, where there are three classes of BSs. Also note that the MBS has the largest coverage (i.e., highest transmit power) but the lowest density.

A. Network deployment model

For notational simplicity, we denote the set of WSPs as N = {1, 2, • • • , N } and meanwhile, for each WSP n, we denote the set of the K n tiers of networks as K n . Without loss of generality, we consider that K n ⊆ K = {1, 2 • • • K}, which means different WSPs may like to provide different services to users. For instance, some WSPs may provide macrocell service, picocell service and femtocell service, but some WSPs may only provide the macrocell service. Here, for each HCN n, we assume that the BSs in the k-th tier are spatially distributed as a two dimensional independent homogeneous Poisson Point Process (PPP) Ψ n,k of density λ n,k and transmit at power P n,k per unit of bandwidth, where k ∈ K n . Moreover, we consider that the potential users of each service k are located according to a homogeneous PPP Ψ u k with intensity λ u k where k ∈ K [START_REF] Chandrasekhar | Spectrum allocation in tiered cellular networks[END_REF]- [START_REF] Cheung | Throughput optimization, spectrum allocation, and access control in two-tier femtocell networks[END_REF]. The above assumption indicates that each service is associated to a certain user density. This is explained by the preferences of different kinds of users to different services. For example a highly mobile user population will prefer the macro-cell service in order to avoid regular hand-overs. Of course in practice, the same user can jump from one population set to another, but on an average the population of each set of user types can be assumed to be a constant.

HCNs are operating on the orthogonal spectrum and meanwhile, each WSP n has to properly allocate the available spectrum bandwidth B n to different tiers, i.e., the WSP deployment framework is adopted [START_REF] Duan | Economics of femtocell service provision[END_REF], [START_REF] Lin | Macro-femto heterogeneous network deployment and management: From business models to technical solutions[END_REF]. For the HCN operated by WSP n, we denote the spectrum bandwidth allocated to tier k by B n,k and the spectrum allocation profile by

B n = (B n,1 , B n,2 , • • • , B n,Kn
). With the dedicated-channel deployment, there is no cross-tier interference in the HCN, only co-tire interference. In each HCN, the downlink transmission is considered and in the k-th tier network deployed by WSP n, the signal from each BS to each user experience path loss with the path loss exponent α n,k > 2, Rayleigh fading with average power of unity, as well as lognormal shadow fading with mean µ n,k and standard deviation σ n,k in dB.

When providing services to users, let us denote the price charged by WSP n for service k as C n,k which is the fixed access fee having units $ per unit of time. We note that pricing for services should consider the combination of many complex factors in practice, e.g., the operation investment of WSPs, the management made by the government, the real consumption level of the concerning country, etc. For easy of exposition, we will set services prices as fixed and focus on the interaction between service selection and resource allocation in the following. On the other hand, each user in a certain population type, picks one out of the N WSPs to get his service. Following previous studies [START_REF] Sengupta | An economic framework for dynamic spectrum access and service pricing[END_REF], [START_REF] Duan | Duopoly competition in dynamic spectrum leasing and pricing[END_REF], [START_REF] Gajic | Competition of wireless providers for atomic users[END_REF], [START_REF] Zhu | Pricing, spectrum sharing, and service selection in two-tier small cell networks: A hierarchical dynamic game approach[END_REF], we assume, for simplicity, that each user would churn from one provider to another without incurring any additional cost. In addition, each user is only able to transmit data through one HCN at each time (i.e., the concurrent transmission is not considered) and meanwhile, he will communicate with the BS bringing his the maximum received power [START_REF] Andrews | A tractable approach to coverage and rate in cellular networks[END_REF], [START_REF] Jo | Heterogeneous cellular networks with flexible cell association: A comprehensive downlink SINR analysis[END_REF]. We note that the choice of each user is determined by the data rates and prices offered by WSPs, and finally results in a population share of x n,k associated to each WSP n and service k, i.e., ∑ n∈N k

x n,k = 1, ∀k ∈ K, where N k denotes the set of WSPs supporting service k.

B. Hierarchical game framework

Here, we consider that all the WSPs and users are selfish, i.e., each individual user wants to maximize his payoff by selecting the best WSP and meanwhile, each WSP wants to attract more users and further improve his own revenue by properly allocating the spectrum resource to different tiers. To be more specific, after selecting the service provided by a particular WSP, each user will obtain some payoff determined by both the service price and expected transmission rate. Intuitively, the expected rate of each user will be determined by both the number of users choosing the same network (i.e., the effects of other users' actions) and the available spectrum bandwidth of the network (i.e., the effect of WSPs' actions). Meanwhile, to attract more users, each WSP also need to make his own decision on the spectrum partition by fully considering the behavior of other WSPs and of users. The scenario under investigation therefore allows two levels of competition and meanwhile one cyclic dependency as described above. These competitions and cyclic dependency can be illustrated with the hierarchical framework shown Fig. 2, where three different game formulation are adopted to investigate the concerned problem. Specifically, in the lower level we formulate the WSP selection of users as an evolutionary game, with which the long-term equilibrium behavior of users can be captured. Meanwhile, in the upper level we have formulated a non-cooperative game to depict the competition among WSPs. In addition, the cyclic dependency interaction between the users and WSPs is modeled by applying the multi-leader multifollower Stackelberg game theory, where the WSPs are the leaders and the populations of users are the followers.

We note that the formulated Stackelberg game can be solved with backward induction, i.e., the leaders (WSPs) can make their responses (i.e., B * ) by fully considering the followers' (users') equilibrium reactions (i.e., x * (B * )) [START_REF] Duan | Duopoly competition in dynamic spectrum leasing and pricing[END_REF], [START_REF] Chen | Utility-aware refunding framework for hybrid access femtocell network[END_REF]. The mapping x * (B * ) denotes the equilibrium behaviour of users, when given the WSPs' strategy profile B * . Here,

x = (x 1 , x 2 , • • • , x K ) where ∀k ∈ K, x k = (x a k ,k ; a k ∈ N k )
represents the population state, which will be formally defined in next section. Hence, for each WSP n, the key problem becomes how to accurately estimate the equilibrium behavior of users and thus make an informed decision. In the following, the evolutionary game modelling the user reaction to the WSP bandwidth allocation is studied first in Section IV. Then, the WSPs compete for the higher revenue assuming the user population to stabilize at the proposed EE based on their bandwidth allocation, which is investigated in Section V.

III. WSP SELECTION EVOLUTIONARY GAME When given the resource allocation profiles of WSPs

B = (B 1 , B 2 , • • • , B N ) where B n = (B n,k ) k∈Kn and B n,k > 0, ∀n ∈ N ,
the expected transmission rate of each user is determined by which WSP he get service from and how many users selecting the same WSP as him. In this section, we formulate the users' WSP selection behavior as an evolutionary game which is initially used in biology to study the evolution of animal populations, and then later applied in economics to model human behavior [START_REF] Cressman | Evolutionary dynamics and extensive form games[END_REF]. Recently, this mathematical tool has also been adopted to study engineering problems in wireless communications, see [START_REF] Jiang | Joint spectrum sensing and access evolutionary game in cognitive radio networks[END_REF] and [START_REF] Chen | Evolutionarily stable spectrum access[END_REF] for an example. The main advantage of this tool is that it can be efficient applied to study the dynamics of a large amount of users active for a long duration. Meanwhile, in contrast to some traditional game models [START_REF] Myerson | Game theory: analysis of conflict[END_REF], [START_REF] Chen | Utility-aware refunding framework for hybrid access femtocell network[END_REF], [START_REF] Xu | Pricing-based multiresource allocation in OFDMA cognitive radio networks: An energy efficiency perspective[END_REF], there is no requirement that each player in the game is fully rational or that he has global information on the other players. This is the primary motivation behind the use of the evolutionary game formulation in this context. Next, we will first analyze the expected average rate of each user with the stochastic geometry based approach and then, present the formulation of the WSP selection game as well as the investigation of the solutions for the formulated game.

A. Expected average user rate

Since different HCNs and tiers operate on orthogonal spectrum bands, we can equally consider the N multi-tier HCNs as ∑ n∈N K n different single-tier cellular networks when analyzing the quality of provided services. For natational simplicity, we denote these equivalent one-tier cellular networks by set

S = {(n, k) |n ∈ N , k ∈ K n } (1)
where the network with index s = (n, k) ∈ S represents the k-th tier of cells deployed by WSP n. In this subsection, we would briefly call one tier of a HCN as one network. In each network s, ∀s ∈ S, the expected achievable rate that can be offered by each cell Rs can be computed by considering a typical user and using the stochastic geometry based approach. According to Slivnyak's theorem [START_REF] Stoyan | Stochastic Geometry and Its Applications[END_REF], the typical user in each network can be arbitrarily chosen. Therefore, we consider the typical user located at the origin without loss of generality and furthermore, denote the position of the BS associated to the typical user as y 0 s . Then, the received power of the typical user from the BS in y 0 s can be expressed as

P ( y 0 s ) = P s h 0 s ψ 0 s y 0 s -αs = P s h 0 s ( ψ 0 s ) 1 αs y 0 s -αs (2)
where h 0 s and ψ 0 s represent the effect of Rayleigh fading and that of shadow fading, respectively. Modeling the channel with shadow fading makes that the received power is not exponentially distributed and then, some important and useful conclusions drawn in previous studies, e.g., [START_REF] Andrews | A tractable approach to coverage and rate in cellular networks[END_REF], [START_REF] Jo | Heterogeneous cellular networks with flexible cell association: A comprehensive downlink SINR analysis[END_REF], [START_REF] Haenggi | Interference in Large Wireless Networks[END_REF], can not be implemented. Fortunately, as pointed in the recent work of Dhillon and Andrews [START_REF] Dhillon | Downlink rate distribution in heterogeneous cellular networks under generalized cell selection[END_REF], the long-term shadowing effects can be interpreted as a random displacement of the location of the BS placed according to the original PPP. In this light, we have the following lemma by resorting to Lemma 1 presented in [START_REF] Dhillon | Downlink rate distribution in heterogeneous cellular networks under generalized cell selection[END_REF].

Lemma 1: For each network s = (n, k) ∈ S, by defining z s = (ψ s )

1 αs y s , ∀y s ∈ Ψ s , we have a new point process Ψ (e) s = { z s z s = (ψ s ) 1 αs y s , ∀y s ∈ Ψ s } . Furthermore, the new point process Ψ (e) s
is also a homogeneous PPP whose density is

λ (e) s = λ s E [ (ψ s ) 1 αs ] (3)
= λ s exp ( ln 10 5

µ s α s + 1 2 ( ln 10 5 σ s α s ) 2 )
where µ s and σ s are the mean and standard deviation of the shadow fading in network s, respectively.

Based on Lemma 1 we would consider the equivalent point process Ψ (e) s instead of the original one Ψ s hereafter, when analyzing the expected achievable rate Rs in network s. Meanwhile, in this case it should be noted that the association based on the maximum received power is equal to the one based on minimum distance, i.e, each user will communicate with the closest BS in each networks s. For the new point process, let

z 0 s ∈ Ψ (e)
s denote the position of the BS associated to the typical user located at the origin and then, the SINR at the typical user can be equally expressed as

γ s = P s h 0 s z 0 s -αs I s + σ 2 (4)
= P s h 0 s z 0 s -α k ∑ z i k ∈Ψ (e) s /z 0 s P s h i s ∥z i s ∥ -αs + σ 2 , ∀s = (n, k) ∈ S
where Ψ (e) s / y 0 s denotes the set of the positions of BSs causing interference to the typical user, and I s denotes the cumulative interference. Furthermore, the expected achievable rate Rs is

Rs = E [B s log 2 (1 + γ s )] = B 0 s R0 s , ∀s = (n, k) ∈ S (5) where B 0 s = B n,k ln 2 , R0 s = E [ln (1 + γ s )
] and additionally, the expectation is taken over both the spatial PPP and the fading distribution. Since for a positive random variable X the expectation can be calculated as

E [X] = ∫ x>0 P (X > x)dx, we have R0 s (a) = ∫ r>0 e -πλ (e) s r 2 E [ ln ( 1 + P s h 0 s r -αs I s + σ 2 )]
2πλ (e) s rdr (6)

= ∫ r>0 e -πλ (e) s r 2 ∫ x>0 P [ ln ( 1 + P s h 0 s r -αs I s + σ 2 ) > x ] dx2πλ (e) s rdr (b) = ∫ r>0 e -πλ (e) s r 2 ∫ x>0 E [ e (-r αs Ps (Is+σ 2 )(e x -1)) ] dx2πλ (e) s rdr = ∫ r>0 e -πλ (e) s r 2 ∫ x>0 e -r αs Ps σ 2 (e x -1)
L Is ( r αs P s (e x -1))dx2πλ (e) s rdr where (a) follows the fact that the probability density function (PDF) of the distance

z 0 k is 3 f ∥z 0 k ∥ (r) = e -λsπr 2
2πλ (e) s r [START_REF] Dhillon | Modeling and analysis of K-tier downlink heterogeneous cellular networks[END_REF] and (b) follows from the distribution that h 0 s ∼ exp (1). In addition, L Is (ω) is the Laplace transform of the PDF of the cumulative interference I s . Recalling the assumptions on the channel model and the expression of I s in (4), we can get the expression of L Is ( r αs Ps (e x -1)) as follows [START_REF] Andrews | A tractable approach to coverage and rate in cellular networks[END_REF] L Is ( r αs P s (e x -1))

= exp

( -πλ (e) s r 2 ∫ u≥1 e x -1 e x -1 + u αs/2 du ) = exp ( -πλ (e)
s r 2 (e x -1)

2/αs ∫ v≥(e x -1) -2/αs 1 1 + v αs/2 dv ) .
Finally, combining Eq. ( 6) and ( 8), we would obtain the expression of the expected achievable rate in a cell of networks s, i.e., Rs , when given the spectrum allocation profiles of WSPs B = (B 1 , B 2 , • • • , B N ). Moreover, under the assumption that the orthogonal transmission is implemented in each cell, i.e., equal time (and/ or frequency) slots are allocated to each users one after another in a round-robin manner, then for each network s the expected average user rate in a cell can be expressed as [START_REF] Jo | Heterogeneous cellular networks with flexible cell association: A comprehensive downlink SINR analysis[END_REF] Rs,u = Rs

N s = B 0 s R0 s N s , N s = x s λ u k λ s , ∀s = (n, k) ∈ S ( 9
)
where N s denotes the average number of users per cell in network s and meanwhile, x s (s = (n, k)) represents the probability that one user would get service k from WSP n or equally, the proportion of users choosing WSP n in the population having the requirement of service k. In other words, x s can also be referred as the population share in the evolutionary game, which will be formally defined in following subsection.

B. Evolutionary game formulation

For the WSP selection of users, the formulated evolutionary game can be formally depicted as follows:

• Population: Each set of users requesting one common service is referred to as a population. Hence, there are totally K different populations which can be denoted by the set K = {1, 2, • • • , K}. • Strategy space: For each user in the k-th population, he can decide to get the service from which WSP. Therefore, his strategy space can be depicted with the set

A k = N k = {n |n ∈ N , k ∈ K n } . ( 10
)
• Population state: For an evolutionary game, the proportion of users choosing strategy a k ∈ A k , denoted by x a k , is referred to as the population share of strategy a k . Moreover, in each population k, the population share of all strategies is termed as a population state, which can be denoted by the vector

x k = (x a k ) a k ∈A k . Obviously, we have x a k ∈ [0, 1], ∀a k ∈ A k , and
∑ a k ∈A k x a k = 1.
Similarly, the population state of the whole K populations can be expressed as

x = (x 1 , x 2 , • • • , x K ). • Payoff function:
The payoff is used to quantify the satisfaction level or fitness of a user adopting a strategy when given the population state. Mathematically speaking, the payoff function of an individual player choosing strategy a k can be considered as a mapping π a k : x → R. In this work, we depict the payoff function with the following logarithmic function

π a k = ln ( 1 + Ra k ,k,u C a k ,k ) = ln ( 1 + β a k ,k R0 a k ,k x a k ) (11)
where

β a k ,k = λ a k ,k B a k ,k ln 2λ u k C a k ,k .
We note that, from the economic perspective, the logarithmic payoff function π = ln (1 + y) can capture both the user's non-satiation, i.e., dπ dy > 0, and risk aversion, i.e., dπ 2 dy 2 < 0, properties. Hence, such a function has been widely used in wireless resource allocation to evaluate satisfaction degree of an agent [START_REF] Lin | Joint spectrum partition and user association in multitier heterogeneous networks[END_REF], [START_REF] Duan | Economics of femtocell service provision[END_REF]. It is worth noticing that although only the logarithmic function is considered here, the following analysis also holds when other monotonically increasing functions are adopted. We note that in dynamic evolutionary game theory, as shown above, the population share of each strategy x a can be interpreted as the current proportion of individuals in the corresponding population using the pure strategy a. Meanwhile, the population state x can also be interpreted as a mixed strategy for the corresponding symmetric normal form game and in this case, the population share x a ∈ x represents the probability that each individual player uses the pure strategy a [START_REF] Cressman | Evolutionary dynamics and extensive form games[END_REF]. In addition, these two representations of the population state are coincident when the number of players is large.

C. Replicator dynamic

To depict the dynamically learning behavior of users, the replicator dynamic is adopted in this paper, which can be expressed as follows:

ẋa k = δx a k (π a k (x k ) -πk (x k )) (12)
= δx a k   π a k - ∑ a ′ k ∈A k x a ′ k π a ′ k (x k )   , ∀k ∈ K
where δ > 0 is the rate of strategy adaption and π (x) is the average payoff in the population. Under this dynamic in each population, the percentage growth rate of the population share of each strategy is proportional to the excess of the strategy's payoff over the population's average payoff. This dynamic could be interpreted biologically as a model of natural selection, and economically as a model of imitation [START_REF] Cressman | Evolutionary dynamics and extensive form games[END_REF]. As shown in the above equation, the dynamics of service selection can be described with K first-order differential equations. Hence, in order to investigate the equilibrium behaviour of users, we consider the solution of this evolutionary dynamic as the fixed point of the differential equations, which is termed as the evolutionary equilibrium (EE) represented by x * . When the population state of the game is at EE, then no user would like to change his strategy.

Based on the support, the EE can be mainly divided into two classes, i.e., the boundary EE and interior EE. Particularly, let us consider a EE x * and denote its support as supp

(x * ) = { (a k , k) a k ∈ A k , k ∈ K, x * a k > 0, x * a k ∈ x * } . If supp (x * ) = (A k , k) k∈K we say x * is an interior EE.
Otherwise, we term it as a boundary EE. Generally, the class of the achieved EE for each replicator dynamic is determined by the initial state x(0), i.e., supp (x(0)) = supp (x * ). In the concerned problem, we note for the applied replicator dynamic the boundary EE is not stable since any small perturbation will make the system deviate from this boundary state. Hence, in the rest of this paper, we just focus on the interior EE. Furthermore, we have the following Theorem.

Theorem 1: For the replicator dynamic shown in Eq. ( 12), the formulated WSP selection game has an unique interior EE state. Let us denote this EE by x * , and then, each element x * a k in x * can be expressed as

x * a k = η a k B a k ,k ∑ a ′ k ∈AK η a ′ k B a ′ k ,k , ∀a k ∈ A k , ∀k ∈ K (13)
where

η a k ,k = λ a k ,k R0 a k ,k C a k ,k
. Intuitively, η a k ,k can be seen as the cost performance per unit bandwidth of the k-th service provided by WSP a k .

Proof: The proof is given in Appendix A. Remark 1: From an economic perspective, elements in x * denote the expected long-term equilibrium of market shares of different services. For instance, the expected market share of each WSP n can be represented as

∑ k∈K ∑ a k ∈N k ,a k =n
x * a k . Therefore, with such statistical results, WSPs can get some insights about the effect of bandwidth allocation on users' WSP selection and further, appropriately deploy the HCNs.

Besides EE, for an evolutionary game the evolutionary stable strategy (ESS) is another important solution standing for a refinement of NE with interesting features [START_REF] Friedman | Evolutionary games in economics[END_REF]. Particularly, if the NE is reached, no player is willing to unilaterally change his own strategy under the condition that no other players will deviate from the NE. While, if the ESS is archived, then no player would like to adopt another strategy even if there is a small group of players irrationally deviate from the ESS. Next, we formally give the definition of ESS [START_REF] Cressman | Evolutionary dynamics and extensive form games[END_REF].

Definition 1: ESS: We term x as an ESS, if for any different population state (or mixed strategy) x ̸ = x, there exists some ε x ∈ (0, 1) that for all ε ∈ (0, ε x ), we have

π (x, (1 -ε) x + εx) > π (x, (1 -ε) x + εx)
where π (x, (1 -ε) x + εx) and π (x, (1 -ε) x + εx) denote the expected payoff of the group of users having the state (or adopting the mixed strategy) x and x given the current population state (1 -ε) x + εx, respectively.

One intuitive interpretation of the above definition is that if the ESS is achieved in a population, a small amount of invaders adopting other strategy instead of ESS would achieve a lower expected payoff than the incumbent does. To see more interpretations of this definition, the readers are encouraged to see [START_REF] Cressman | Evolutionary dynamics and extensive form games[END_REF] and [START_REF] Sandholm | Evolutionary game theory[END_REF]. For our formulated evolutionary game and the adopted replicator dynamic, an interior ESS is also an asymptotically stable state, which means that it is stable and attracting (Theorem 2.7.1 in [START_REF] Cressman | Evolutionary dynamics and extensive form games[END_REF]). Hence, such a state can be finally reached via evolutionary process with an initial point in some open neighborhood of the asymptotically stable state. The detailed definition about asymptotically stability can be found in Definition 2.5.2 in [START_REF] Cressman | Evolutionary dynamics and extensive form games[END_REF]. Unfortunately, in general there is no guarantee that every EE would be aligned with an ESS. In other words, there is no guarantee that the fixed point of a replicator dynamic is also asymptotical stable. However, for the interior EE obtained in Theorem 1, we have the following theorem.

Theorem 2: The unique interior EE x * obtained in Theorem 1 is an ESS and hence, is asymptotical stable for the adopted replicator dynamic.

Proof: This theorem can be proved with the similar method applied in the proof of Theorem 2 of [START_REF] Zhu | Pricing, spectrum sharing, and service selection in two-tier small cell networks: A hierarchical dynamic game approach[END_REF] and in that of Theorem 3 of [START_REF] Chen | Evolutionarily stable spectrum access[END_REF]. However, we still present the proof in Appendix B for completeness.

Remark 2: It should be noted that for our concerned WSP selection game, the reason resulting in the mutation from the equilibrium state EE can be intuitively interpreted from many perspectives. On one hand, if we suppose that the formulated game operates in EE x * and at that moment, there are some users joining or leaving the market. Then, the evolution state may deviate form the EE, i.e., the mutation is introduced for the equilibrium state. On the other hand, the mutation may also be introduced at some moment when parts of users have accidentally made an irrational decision due to some reasons. Fortunately, as shown in the above theorem, the effect of such a mutation would be eliminated and the EE would be reached again. These comments will be illustrated with simulation results shown in Section VI.

IV. SPECTRUM BANDWIDTH ALLOCATION GAME

In order to obtain a higher market share and revenue, a WSP must properly allocate the available spectrum. Since the spectrum allocation profile may not be frequently adjusted, each WSP should make his decision based on the equilibrium state of the service selection of users, i.e., the EE. 4 Hence, we define the payoff function for the WSP as follows

U n (B n , B -n ) = ∑ k∈Kn U n,k = ∑ k∈Kn λ u k x * n,k C n,k (14)
= ∑ k∈Kn φ n,k B n,k ∑ m∈N k η m,k B m,k = ∑ k∈Kn φ n,k B n,k ∑ m∈N k ,m̸ =n η m,k B m,k + η n,k B n,k where B -n = (B 1 , • • • , B n-1 , B n+1 , • • • , B N ) denotes bandwidth allocation profiles of WSPs other than WSP n. In addition, η n,k = λ n,k R0 n,k C n,k , and φ n,k = λ u k η n,k C n,k , ∀k ∈ K n , ∀n ∈ N .
We also impose the constraint B n,k ≥ b on each WSP's bandwidth allocation strategy, where b > 0 is a positive constant. 5As shown in Eq. ( 14), the payoff of each WSP is determined by both its own bandwidth allocation profile and those of other WSPs. In contrast to the study in the previous section, we assume that each WSP is fully capable of acquiring all the information on HCNs deployed by its competitors (i.e., other operators) [START_REF] Duan | Duopoly competition in dynamic spectrum leasing and pricing[END_REF]- [START_REF] Chen | Utility-aware refunding framework for hybrid access femtocell network[END_REF], [START_REF] Duan | Economic analysis of 4G upgrade timing[END_REF], e.g., the BSs densities and transmit powers. Conditioned on this, we can formulate the problem as a Non-cooperative spectrum Bandwidth Allocation Game (N-BAG) and hereafter, the terms WSP and player would be used interchangeably in this section.

Definition 2: N-BAG: This game can be represented by the tuple

G = Γ ( N , (B n ) n∈N , (U n ) n∈N ) . ( 15
)
Here, N denotes the set of players which is identical to the WSP set. For each player n, its strategy space B n is defined as the set of available spectrum bandwidth allocation profiles

B n = { B n B n = (B n,k ) k∈Kn , B n,k > b, ∑ k∈Kn B n,k = B n } (16)
Based on Eq. ( 14), when given a strategy profile

(B n ) n∈N = (B 1 , B 2 , • • • , B N ) ∈ (B n ) n∈N , ( 17
)
the payoff function of each player n, n ∈ N , can be expressed as

U n (B n , B -n ) = ∑ k∈Kn φ n,k B n,k χ n,k (B -n ) + η n,k B n,k ( 18
)
where the term

χ n,k (B -n ) = ∑ m∈N k ,m̸ =n η m,k B m,k depicts
the interference caused to player n from other players. For a non-cooperative game, NE is the standard solution standing for the equilibrium state, under which no player can unilaterally improve its own payoff by choosing a different strategy [START_REF] Myerson | Game theory: analysis of conflict[END_REF]. Accordingly, we have the following theorem about the existence of NE for N-BAG.

Theorem 3: For our formulated non-cooperative game N-BAG, there always admits at least one NE under which no WSP would like to unilaterally change his own bandwidth allocation strategy. Furthermore, when given other WSPs' strategy profile B -n , the best response of WSP n,

B * n = ( B * n,k
) k∈Kn , is unique and can be expressed as

B * n,k = max { b, √ λ u k C n,k χ n,k (B -n ) υ * n η n,k - χ n,k (B -n ) η n,k } . ( 19
)
where

∑ k∈Kn max { b, √ λ u k C n,k χ n,k (B -n ) υ * n η n,k - χ n,k (B -n ) η n,k } = B n . ( 20
)
Proof: The proof is given in C. Based on the above, an iterative algorithm has been developed to obtain the NE of N-BAG, which is shown in Algorithm 1. Particularly, at the beginning of this algorithm, the starting point will be initialized based on the available bandwidth of each WSP, i.e., ∑ k∈Kn B n,k = B n , ∀n ∈ N . After that, the algorithm goes into a loop. At each iteration t, each WSP n calculates the optimal Lagrange multiplier υ * n with (20) and then, updates the best response B n (t) by applying [START_REF] Gajic | Competition of wireless providers for atomic users[END_REF]. Then, the loop will stop when the relative difference of the two optimal solutions obtained after the consecutive iterations (i.e., (B n (t -1)) n∈N and (B n (t)) n∈N ) is small Set t = t + 1 and B n (t) = B n (t -1) .

4:

for n = 1 to N users do 5:

Calculate the optimal Lagrange multiplier υ * n with Eq. ( 20)and then, update the best response B n (t) by applying Eq. ( 19).

6:

end for 7: until the stop criterion shown in Eq. ( 21) is satisfied. 8: For B n,k (t) being equal to b set its value (i.e., B n,k (t))

and the corresponding payoff

U n,k (t) to 0, ∀k ∈ K n , ∀n ∈ N . 9: Set B * n = B n (t) and U * n = ∑ n∈N U n,k (t), ∀n ∈ N .
enough. Mathematically speaking, the stopping criterion of Algorithm 1 can be expressed as

(B n (t)) n∈N -(B n (t -1)) n∈N (B n (t -1)) n∈N < ε ( 21
)
where ∥•∥ denotes a proper vector norm and ε is a small positive constant. Finally, the effects the added constraint that B n,k ≥ b would be eliminated with the step in line 8 of the proposed algorithm. Remark 3: It should be noted that given the initial point (B n (0)) n∈N , Algorithm 1 will converge to the unique solution NE (B * n ) n∈N . Meanwhile, when the initial point changes, the finally achieved solution may be different unless the NE of N-BAG is unique. However based on our extensive simulation results, we conjecture that the NE is unique and hence, the algorithm will converge to the same point irrespective of the starting allocation chosen.

Remark 4: From a mathematical perspective, note that this game and the corresponding IWF algorithm proposed is indeed quite similar to the well known IWFA for power allocation [START_REF] Scutari | Asynchronous iterative water-filling for gaussian frequency-selective interference channels[END_REF]. However, a significant difference that makes the problem harder to prove uniqueness of the NE is that, the water level in each service k for this work are different unlike the uniform water level over channels seen in [START_REF] Scutari | Asynchronous iterative water-filling for gaussian frequency-selective interference channels[END_REF].

Here, we note that the developed algorithm is an offline algorithm. In addition, since we assume that each WSP can acquire the related information of the co-players, this algorithm can be independently implemented by each WSP and will convergence to an NE when given the initial point. Hence, with the finally obtained solution, no WSP has the incentive to deviate from this strategy, i.e., the equilibrium state is achieved. On the other hand, it is worth noting that this algorithm can also be implemented by some neutral institution [START_REF] Iosifidis | A double-auction mechanism for mobile data-offloading markets[END_REF] and the achieved NE based strategy would be informed to each WSP independently, i.e., providing a centralized bandwidth allocation scheme. Due to the fact that each WSP knows he cannot unilaterally improve his own revenue by choosing a strategy different from that suggested by the neutral institution, these suggested strategies will be adopted by these rational WSPs, eventually.

V. SIMULATION RESULTS

To validate the effectiveness of our theoretical analysis, simulations are conducted and the corresponding results are presented in this section. We consider the region where totally K = 3 different services would be provided to users by HCNs, i.e., macrocell service, picocell service and femtocell service, which are labeled by 1, 2, and 3, respectively. Accordingly, the three populations of users are respectively denoted by P1, P2, and P3. Unless specified otherwise, the simulation parameters are adopted as listed in Table I.

A. EE and ESS for users' WSP selection

In this subsection, we illustrate the dynamics of user behavior. There exist three different WSPs each of which offers all the three services to users. We label these WSPs as WSP 1, WSP 2 and WSP 3 and meanwhile, set the densities of BSs deployed by them as [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave N-person games[END_REF][START_REF] Xu | Pricing-based multiresource allocation in OFDMA cognitive radio networks: An energy efficiency perspective[END_REF] and (λ 3,1 , λ 3,2 , λ 3,3 ) = (1, 10, 60). 6 Intuitively, this setting means that the three WSPs respectively have their own appealing service. To see the dynamics of users, we conduct the simulation in a region with 1000 km 2 and equally, consisting of 20000, 60000, and 100000 users in P1, P2 and P3, respectively. Here, we consider that each WSP would equally allocate the available bandwidth to each tier. During the initialization of this simulation, users in each population would randomly select the available WSPs. After that, they will adopt the pairwise proportional imitation during the evolutionary progress, which means that each user would randomly select an opponent and imitates the opponent only if the opponent's payoff is higher than his own with probability proportional to the payoff difference [START_REF] Sandholm | Evolutionary game theory[END_REF]. The dynamics of population state and payoff achieved by each user are shown in Fig. 3 and Fig. 4, respectively.

(λ 1,1 , λ 1,2 , λ 1,3 ) = (3, 15, 40), (λ 2,1 , λ 2,2 , λ 2,3 ) = (2,
From these two figures, we can see that the EE of formulated evolutionary game can be achieved less than 30 iterations. Meanwhile, as shown in Theorem 2, when this equilibrium state is achieved in each population, all the users will obtain the same payoff no matter getting the service from which WSP. In other words, from the perspective of payoff achieved by each user, the load among WSPs is balanced when EE is reached. In order to further show the asymptotic stability of the EE, we suppose that at the moment that the evolutionary time is 40, in each population there are 20 percents of the users selecting WSP 1 and WSP 2 decide to churn to WSP 3, for example, due to the inaccuracy of obtained information, i.e., the mutation occurs. It can be seen that the payoff achieved by the user selecting WSP 3 is reduced due to the fact that the mutation demolish the load balance among WSPs. However, since the EE is asymptotically stable, the equilibrium state EE would be finally reached again. For this reason, from the long term perspective, it seems plausible for each WSP to evaluate the market and investigate the deployment of his own HCN based on this stable state of users' behavior.

B. Convergence of Algorithm 1

In this subsection the convergence of our proposed algorithm, i.e., Algorithm 1, is illustrated by simulations. Here, the required relative accuracy ε (in Eq. ( 21)) and the added bandwidth allocation constraint b (in Eq. ( 32)) are set to 10 -3 and 10 -5 MHz, respectively. Moreover, the densities of BSs are set to the same value as in Section VI-A. To show the uniqueness of NE for the formulated game N-BAG, we run the simulation with 10000 independent realizations of the initial point in our algorithm and for clearly exposition, present 200 results in Fig. 5. 7 Here, the bandwidth allocation profile at iteration 0 denotes the starting point of the algorithm. As illustrated in the figure, the equilibrium state of N-BAG can be reached after a few iterations, i.e., about 5 iterations. Moreover, we can see that the same strategy would be finally adopted by each individual WSP which does not depend on the initial point. In other words, the NE of the game is unique. Besides that, we notice that for WSP 1, 2 and 3, in order to achieve a higher payoff, they have allocated the most bandwidth to macrocell service, picocell service and femtocell service, respectively. One main reason lies into the fact that, compared with other WSPs, they have deployed the most dense BSs for these three different service, respectively, e.g., λ 1,1 > λ 2,1 > λ 3,1 .

C. Performance evaluation

At the beginning of this subsection, we want to show the effects of BSs' densities on the bandwidth allocation of the WSP. For easy of exposition, we consider two WSPs (WSP 1 and WSP 2) each of which would provide two services (macrocell service and picocell service) to two populations of users (P1 and P2). Here, we suppose that the densities of users in the two populations and those of BSs deployed by WSP 1 are fixed, which are set as (λ u 1 , λ u 2 ) = (20, 60) and (λ 1,1 , λ 1,2 ) = [START_REF] Ghosh | Heterogeneous cellular networks: From theory to practice[END_REF][START_REF] Chen | Utility-aware refunding framework for hybrid access femtocell network[END_REF], respectively, while the densities of MBSs and PBSs deployed by WSP 2 (i.e., λ 2,1 and λ 2,2 ) vary. According to the changes of λ 2,1 and λ 2,2 , the bandwidth allocated to the macrocell service by WSP 2, B 2,1 , and his achieved payoff, U 2 , are illustrated in Fig. 6 and7, respectively. In these figures, λ 2,1 varies from 1 to 5 and meanwhile λ 2,2 varies form 5 to 60. Since B 2,1 + B 2,1 = B 2 which is a constant, the results about B 2,2 are omitted here for the sake of brevity.

From Fig. 6 it is seen that the densities of MBSs and PBSs have a significant effect on WSP 2's bandwidth allocation strategy even for the case consisting of two WSPs. More specifically, two observations can be made. On one hand, when given the density of PBS, λ 2,2 , the bandwidth allocated to macrocell service, B 1,2 , first increases with respect to the density of MBS λ 2,1 and then decreases. Additionally, the threshold is around λ 2,1 = 2 which equals to the density of MBSs deployed by WSP 1. The reason is that when λ 2,1 is small, in order to attract more users in population P1 and increase his own payoff, WSP 2 has to allocate more bandwidth to macrocell service to improve the competitiveness. However, when λ 2,1 > λ 1,1 the macrocell service offered by WSP 2 can provide users higher expected achievable rate per bandwidth, i.e., R 0 2,1 > R 0 1,1 . As shown in Theorem 1, this further means that WSP 2 may attract more users in P1 than WSP 1 dose, even WSP 2 allocates less bandwidth to this service. Hence, he can allocate more bandwidth to the second service to further improve the payoff. On the other hand, it is shown that when given λ 2,1 , B 1,2 would first decrease and then increase when λ 2,2 gradually becomes larger. The reason resulting in this performance is similar to the one previously stated. Besides that, it is not surprising that the divide in this case appears near to the point that λ 2,2 = 20, which is equal to λ 1,2 . Here we should note that these results are different to those illustrated in [START_REF] Lin | Joint spectrum partition and user association in multitier heterogeneous networks[END_REF], where it is shown that the spectrum allocated to some service s is monotonic increasing with respect to the density VI. CONCLUSIONS The users' wireless service provider (WSP) selection as well as WSPs' bandwidth allocation in multi-tier heterogeneous cellular networks (HCNs) has been investigated by adopting the approach combining stochastic geometry and game theory. To be more specific, after analyzing the expected average rate for users, the WSP selection of users has been formulated as an evolutionary game. Then, a closed form expression for the EE (which denotes the state of user behavior at equilibrium) and its asymptotic stability has been proven. Based on this analysis, the bandwidth allocation of WSPs as a non-cooperative game has been formulated and the existence of Nash equilibrium (NE) has been proven. Here, an algorithm used to achieve the NE has also been developed. Simulation results have shown the effects of the BSs' as well as users' densities on the WSP's bandwidth allocation decision. In addition, it has also been demonstrated by simulation that, compared with other schemes, an efficient and fair solution would be obtained by implementing our proposed algorithm.

APPENDIX A PROOF OF THEOREM 1

Proof: Substituting Eq. ( 11) into Eq. ( 12), we can equally transform the replicator dynamics of the formulated evolutionary service selection game as Eq. ( 24). Based on Eq. ( 24), we note that to get the EE x * we should make sure that ẋ *

a k = 0, ∀a k ∈ A k , ∀k ∈ K. Meanwhile, recalling that x > a k 0 (∀a k ∈ A k , ∀k ∈ K) and ∑ a k ∈A k x a k = 1, we have x * a k = β a k ,k R0 a k ,k β a ′′ k ,k R0 a ′′ k ,k x * a ′′ k , ∀a k , a ′′ k ∈ A k ( 25
)
and

∑ a ′ k ∈A k β a ′ k ,k R0 a ′ k ,k β a ′′ k ,k R0 a ′′ k ,k x * a ′′ k = 1 (26)
Further, we can get the expression of the EE as

x * a k = β a k ,k R0 a k ,k ∑ a ′ k ∈A k β a ′ k ,k R0 a ′ k ,k = λ a k ,k B a k ,k C a k ,k R0 a k ,k ∑ a ′ k ∈A k λ a ′ k ,k B a ′ k ,k C a ′ k ,k R0 a ′ k ,k (27)
where ∀a k ∈ A k , ∀k ∈ K.

Then, replacing the term

λ a k ,k B a k ,k C a k ,k
by η a k ,k we can draw the conclusion shown in Theorem 1.

APPENDIX B PROOF OF THEOREM 2

Proof: Based on the folk theorem of an evolutionary game, any strict NE corresponds to an ESS [START_REF] Cressman | Evolutionary dynamics and extensive form games[END_REF]. Meanwhile, it is obvious that the solution in Eq. ( 13) is an equilibrium for the evolution dynamics in Eq. ( 12), since there is no player would change his own strategy, i.e., ẋs = 0 for any s ∈ S. Hence, we will prove this theorem by showing the equilibrium x * is a strict NE. Considering the evolution game operates in EE x * , the payoff obtained by a user selecting service s is

π s (x * ) = ln ( 1 + βs R0 s x * s )
(as shown in Eq. ( 11)). In addition, we have π s (x * ) = π l (x * ), ∀s, l ∈ S. Now, suppose that some user (or users) deviates (or deviate) the strategy from s to l where s ̸ = l, and then the population state becomes

x = ( x * 1 , • • • , x * s -ξ, • • • , x * l + ξ, • • • , x * |S| ) (28)
where the constant ξ > 0 is determined by the number of users deviating the strategy. In addition, with the deviation from strategy s to l, the payoff of the user becomes π l ( x) = ln

( 1 + β s R0 s x * l + ξ ) < ln ( 1 + β s R0 s x * l ) = π l (x * ). ( 29
)
It follows that π s (x * ) > π l ( x) and further means that the deviating from the equilibrium state will lower the payoff of the user, which satisfies the definition of the strict NE. Now, the proof is completed.

APPENDIX C PROOF OF THEOREM 3

Proof: First, we will prove the existence of NE for the formulated game N-BAG. After some algebraic computations we can transform the payoff of WSP n as

U n (B n , B -n ) = τ n - ∑ k∈Kn λ u k C n,k χ n,k (B -n ) χ n,k (B -n ) + η n,k B n,k (30)
where

τ n = ∑ k∈Kn φ n,k η n,k = ∑ k∈Kn λ u k C n,k .
It is easy to prove that the n-th player's payoff U n is concave over his strategy set B n for each fixed B -n and meanwhile, the strategy space (B n ) n∈N is a closed and bounded convex set [START_REF] Boyd | Convex optimization[END_REF]. Therefore, we can know that G is a concave game which always admits at least one NE [START_REF] Rosen | Existence and uniqueness of equilibrium points for concave N-person games[END_REF]. We note that this proposition can be proved through three steps. First, when given a strategy profile, it can be proved that the best response of each player is compact and convex which is due to the continuity and concavity of the payoff function. Then, it can be proved that that the best response function Ω : (B n ) n∈N → (B n ) n∈N is upper semicontinuous. Finally, by applying Kakutani fixed point theorem, it can be proved that there exists a fixed point Ω((B * n ) n∈N ) = (B * n ) n∈N . To be more specific, this fixed point (B * n ) n∈N is a NE for the considered concave game.

Next, we will derive the expression of the best response of WSP n when given the strategy profile of other WSPs B -n . In this case, for each player n, selecting the strategy maximizing his own payoff is equivalent to solving the following optimal spectrum allocation problem

P : min Bn ∑ k∈Kn λ u k C n,k χ n,k (B -n ) χ n,k (B -n ) + η n,k B n,k (31)
s.t. B n,k ≥ b, ∀k ∈ K n , (32)

∑ k∈Kn B n,k = B n , ( 33
)
which is a convex problem. For problem P, the lagrangian

ẋa k = δx a k ( ln ( 1 + β a k ,k Ra k ,k,u x a k ) - ∑ a ′ k ∈A k x a ′ k ln ( 1 + β a ′ k ,k Ra ′ k ,k,u x a ′ k
) ) , ∀a k ∈ A k , ∀k ∈ N [START_REF] Lopez-Perez | Enhanced intercell interference coordination challenges in heterogeneous networks[END_REF] function can be written as

L n = ∑ k∈Kn λ u k C n,k χ n,k (B -n ) χ n,k (B -n ) + η n,k B n,k (34)
-

∑ k∈Kn θ n,k (B n,k -b) + υ n ( ∑ k∈Kn B n,k -B n )
where θ n,k ≥ 0 and υ n are the Lagrange multipliers [START_REF] Boyd | Convex optimization[END_REF]. Moreover, the KKT conditions can be expressed as

∂Ln ∂B n,k = - λ u k C n,k χ n,k (B -n )η n,k (χ n,k (B -n ) + η n,k B n,k ) 2 -θ n,k + υ n = 0, B n,k ≥ b, ∑ k∈Kn B n,k = B n , θ n,k ≥ 0, θ n,k (B n,k -b) = 0, ∀k ∈ N k . ( 35
)
Since problem P is a convex problem, the optimal variable

B * n = ( B * n,k
) k∈Kn can be achieved by solving the KKT conditions [START_REF] Sandholm | Evolutionary game theory[END_REF], which could be further transformed as

υ n ≥ λ u k C n,k χ n,k (B-n)η n,k (χ n,k (B-n)+η n,k B n,k ) 2 , (B n,k -b) ( υ n - λ u k C n,k χ n,k (B-n)η n,k (χ n,k (B-n)+η n,k B n,k ) 2 ) = 0, B n,k -b ≥ 0, ∑ k∈Kn B n,k = B n , ∀k ∈ N k . ( 36
)
To solve the above equations, two disjoint cases need to be considered. Firstly, if υ n <

λ u k C n,k χ n,k (B-n)η n,k (χ n,k (B-n)) 2 = λ u k C n,k η n,k
χ n,k (B-n) , the first three conditions in Eq. ( 36) only hold when

B n,k = √ λ u k C n,k χ n,k (B -n ) υ n η n,k - χ n,k (B -n ) η n,k ≥ b. ( 37
)
or

B n,k = b, √ λ u k C n,k χ n,k (B -n ) υ n η n,k - χ n,k (B -n ) η n,k < b. ( 38
)
On the other hand, if

υ n ≥ λ u k C n,k η n,k
√ λ u k C n,k χ n,k (B -n ) υ * n η n,k - χ n,k (B -n ) η n,k } = B n .
Finally, we will prove the uniqueness of B * n when given B -n . It should be noted that the left side of the above equation is a piece-wise-linear increasing function of 1 υ * n , hence the solution of this equation is unique when given B -n , which further means that the solution shown in Eq. ( 19) is also unique in the same case, i.e., given B -n . Now, we complete the proof.

Fig. 1 .

 1 Fig. 1. Illustration of a 3-tier HCN, which consists of the macrocell, picocells and femtocells.

2

 2

Fig. 2 .

 2 Fig. 2. Illustration of the hierarchical game framework.

Algorithm 1 :

 1 Computation of NE (B * n ) n∈N . 1: Initialization: For ∀n ∈ N , initialize the starting point B n,k (0) satisfying ∑ k∈Kn B n,k = B n and set t = 0.

Fig. 3 .Fig. 4 .

 34 Fig.3. The dynamic of population sate in the population P1, P2 and P3. To illustrate the asymptotic stability of the EE, the mutation is added in each population at the moment that the evolutionary time is 40.

Fig. 5 .Fig. 6 .

 56 Fig. 5. The bandwidth allocation strategies of three WSPs.

2 Fig. 7 .

 27 Fig. 7. The payoff achieved by WSP 2 vs. the densities of MBSs and PBSs.

χ

  n,k(B-n) , then B n,k > b > 0 and the second condition in Eq.[START_REF] Duan | Economic analysis of 4G upgrade timing[END_REF] can not be satisfied simultaneously, which further means B n,k can only equal to b. To this end, the optimal solutionB * n = C n,k χ n,k (B -n ) υ * n η n,k -χ n,k (B -n ) η n,k } .Meanwhile, recalling the constraint that ∑ k∈Kn B n,k = B n , we can get the optimal Lagrange multiplier υ * n by solving ∑ k∈Kn max { b,

Electromagnetic spectrum is typically divided into a number of bands by regulatory agencies such as the FCC or the European Commission. Then, each WSP can obtain some bands by executive fiat or auction. Therefore, the spectrum resource is previous and limited for each WSP[START_REF] Jindal | Bandwidth partitioning in decentralized wireless networks[END_REF].

The derivation of expected rate of each user as well as the definitions for both the use's payoff function and WSP's revenue will be sequentially given in the following two sections.

This expression is derived based on the assumption that, in each network, the typical user will associate with the closest BS. The detail can be found in[START_REF] Andrews | A tractable approach to coverage and rate in cellular networks[END_REF].

This consideration is mainly because in practice, each operator usually makes a long-term decision instead of changing his decision frequently[START_REF] Duan | Economic analysis of 4G upgrade timing[END_REF].

This b can be interpreted as a minimum bandwidth allocation required in order to deploy a certain service. b = 0 leads to a potentially undefined payoff function when B n,k = 0, ∀n for any k. So from a mathematical point of view this constraint keeps the function continuous and easier to handle. Note, this extra constraint will be finally removed when designing the spectrum allocation algorithm at the end of this section.

All the density related parameters have the same units in this section, i.e., the number of BSs or users per km 2 . Hereafter, the units will be omitted for convenience.

Although we have not shown all the 10000 simulation results here, we note that the remain results have shown the same convergence behavior.

of the corresponding BSs λ s . This difference is mainly caused by the competition among WSPs.

To see the trend of the obtained payoff U 2 , we can refer to Fig. 7. It should be noted that, in contrast to B 2,1 , the payoff U 2 is monotonically increasing with respect to both λ 2,1 and λ 2,2 . The reasons can be explained as follows. When deploying more BSs, the WSP will have a higher competitiveness in the market and hence, can attract more users to further improve his own payoff. Additionally, another reason for the monotonically increasing of U 2 is due to the fact that the cost for BSs deployment is not taken into account. Otherwise, the trend of U 2 would probably first increase and then decrease, since the upper bound of the revenue could be obtained by WSP 2 in the market is fixed, i.e., λ u 1 C 2,1 +λ u 2 C 2,2 , which appears when every user chooses to get service from WSP 2.

Finally, we want to compare our algorithm with other three bandwidth allocation schemes which are presented as follows.

• Uniform distribution (UD): With this approach each WSP would equally divide the available bandwidth into subbands and allocated them to different tiers. • Proportion to density of BSs (PDBS): With this approach each WSP would allocate the available bandwidth to each tier based on the density of BSs, i.e.,

• Proportion to density of users (PDU): With this approach each WSP would allocate the available bandwidth to each tier based on the density of potential users in each population, i.e.,

We note that this scheme is similar to the one proposed in [START_REF] Lin | Joint spectrum partition and user association in multitier heterogeneous networks[END_REF], which focuses on the single WSP scenario. Here, we consider there are three WSPs, each of which deploys a 3-tier HCN with the BS density as λ 1,k = 2λ 2,k = 4λ 3,k , where (λ 3,1 , λ 3,2 , λ 3,3 ) = (0.5, 5, 10). In addition, the available bandwidth of the three WSPs are set as (B 1 , B 2 , B 3 ) = (20, 10, 5) MHz, which means that the bandwidth obtained by each WPS is not the same and may sometimes happen in some practical cases. Based on the different deployment of HCNs, we consider that the price charged by WSPs are also different:

We evaluate the performance of these schemes in terms of the sum payoff U = ∑ n∈N U n and Jain's fairness index, i.e.,

, which are illustrated in Fig. 8 and9, respectively. While λ u 3 varies from 60 to 150 during the simulation, the density of users in P1 and P2 are set according to Table I, i.e., λ u 1 = 20 and λ u 2 = 60. From Fig. 8 we can see that, compared with other three schemes, our proposed algorithm can bring the highest sum payoff to WSPs. For instance, when λ u 3 = 150 our algorithm yields a performance advantage around 11.8% relative to the scheme PDBS, i.e., from 66.01 to 73.77. The main reason for this improvement mainly lies into the fact that, by formulating the bandwidth allocation problem as a game, the rational WSPs could intelligently allocate the available bandwidth into different tiers fully considering the effects caused by the competition from other WSPs. In addition we can find that the sum payoff achieved by the scheme UD and that by PDU is the same. To explain this, it should be noted that when implementing these two strategies, the ratio of provided bandwidth from different WSPs is the same for a given service, i.e., B 1,k : B 2,k : B 3,k = 4 : 2 : 1, ∀k ∈ K. Recalling Eq. ( 14), this further means that a particular WSP n will obtain the same payoff when adopting UD and PDU. To see the fairness we can refer to Fig. 9, which shows that our proposed approach is the fairest one among these four schemes. This is mainly due to the fact both the rationality and individual interest of each WSP can be well considered by resorting to the game theory based formulation. Meanwhile, it is not surprising to see that UD and PDU also have the same performance. The reason is the same as previously described. As a consequence, the simulation results illustrated in these two figures demonstrate that, compared with the scheme UD, PDBS and PDU, the equilibrium solution achieved by Algorithm 1 is efficient as well as fair.


Vineeth S Varma

Tony Q S Quek

Congestion Games in Caching Enabled Heterogeneous Cellular Networks

In this work, a heterogeneous cellular network with caching enabled at the small cell aggregators is analyzed. The caching technology is enabled to help offload some of the popular traffic requests onto the cache. In this framework, a network congestion game is formulated to study the evolution of traffic when every user as an independent decision maker decides its choice of communication, i.e, via the macro cell or the caching enabled small cells. To study the effect of the cache on the network delay, a numerical simulation is implemented. The file popularity is modeled using the well known Zipfdistribution and the network delay is studied as a function of the cache buffer size and network traffic. In summary, these results can be utilized by network operators to deploy infrastructure efficiently.

I. INTRODUCTION

Motivation: The increased demand of high-data-rate services and requirement of ubiquitous access calls for innovative solutions that can drastically improve the data rates offered by networks. Augmenting an existing macro-cell by deploying a high density small cell (SC) network, i.e., deploying a heterogeneous cellular networks (HCNs), is considered as an efficient solution to resolve the problem of heavy data demands [START_REF] Quek | Small cell networks: Deployment, PHY techniques, and resource management[END_REF]- [START_REF] Ghosh | Heterogeneous cellular networks: From theory to practice[END_REF]. While the deployment of an HCN potentially allows for a higher data rate on the wireless end, the data rate is often restricted through the backhaul links and more significantly through the data server links. Data caching, i.e., storing frequently accessed data within each SC or SC aggregator, is a novel approach that could significantly reduce backhaul bandwidth required and also improve the quality of service to users [START_REF] Imielinski | Mobile wireless computing: challenges in data management[END_REF]- [START_REF] Bastug | Proactive small cell networks[END_REF].

Typically data caching in the network edge can be implemented at either the SC base stations or at the SC aggregator 1 . As the small cell network is highly dense, 1 The aggregator is the node where multiple neighboring SC base stations are connected via weaker backhaul links (for cost efficiency). The aggregator is subsequently connected to the core network through a stronger backhaul link.

it is potentially more efficient to implement the cache at the aggregator end, in terms of cost efficiency. In this work, the focus is on the caching system implemented at the aggregator. When an HCN is deployed, the users have a choice on which network they utilize in order to access their targeted data. Users can decide between the caching enabled SC network or the macro network. This choice results in a competitive game between all the users involved. In this work, the resulting game is modeled as a congestion game, while taking into account the possibility of data being cached at the SC aggregator.

Related works: Congestion games, first introduced by Rosenthal (1973) [START_REF] Rosenthal | A class of games possessing pure-strategy nash equilibria[END_REF], have been extensively studied in literature and applied to various scenarios like traffic control problems and information networks. In the wireless literature, several works use game theory to predict user behavior and model systems [START_REF] Altman | A survey on networking games in telecommunications[END_REF]- [START_REF] Lasaulce | Game theory and learning for wireless networks: fundamentals and applications[END_REF]. However, to the best of our knowledge, studying the competition between users in a caching enabled HCN is a novel problem. The results of this work can be used to design HCN infrastructural and networking parameters in a more efficient manner when caching is enabled at the SC aggregator.

Organization: This paper is structured in the following format. In Section II, we present the system model and define the proposed performance metric. In Section III, we conduct an analytic study of the proposed congestion game while Section IV provides many numerical results to sustain the proposed approach. Finally, we conclude the paper and some possible extensions to this work are provided.

II. SYSTEM MODEL

We consider a HCN with a macro BS working in parallel with several SCs. The SCs are connected to an aggregator where data can also be cached. We assume a simple file model where all files are of the same size φ. The file popularity of file n is given by q(n) where n ∈ N = {1, 2, ..., N }. We are interested in the situation where the independent reference model (IRM) can be ISBN 978-3-901882-68-5 c 2015 IFIP applied. Adopting the IRM implies that this popularity stays a constant through a large period of time. Each of these files are stored in servers connected to the internet. We assume that each server is independently connected to the internet with links that offer peak rates of B Sn (files per second). As each server is accessed by several such HCN's simultaneously, the B Sn that we use for a single HCN (as studied in this work) has to be modified based on the total number of HCNs using the same server given by N c . For example, a video file stored in the Singapore server of the respective website would be accessed by hundreds of networks deployed all over the country.

Let the total traffic generated by users in a cycle be given by T in unit files. This traffic is assumed to be generated by the users periodically every τ seconds which is the cycle duration. Since each SC serves very few users, the transfer time from the SC aggregator to the users is a constant δ F seconds independent of the traffic T F . As the macro serves many users, the transfer time from the BS to the user depends on the traffic through the macro BS T M and the peak rate offered B M (files per second). We assume the backhaul from the macro BS to the internet to be quite large and so the transfer time is again assumed to be a constant δ M seconds. However, the backhaul from the aggregator to the internet (or core network) is slower and is given by B F . To compensate for this, we also assume that the aggregator can store data by caching.

The buffer at the cache has a maximum capacity given by C (files) or Cφ bits. We assume that the cache operates with the least recently used (LRU) replacement policy. That is, when a request for a file absent in the cache arrives, the least recently used file in the buffer is replaced by the new request (after being downloaded through the backhaul). In this work, since the file popularity is assumed to be unknown (to the users and to the network), the LRU caching mechanism is a natural choice. If the requested file is available in the cache, the request can be granted with a very small delay of δ C2 . The net delay over a path is calculated as the maximum delay incurred across all the elements in the path (this model is most suitable for file streaming or large data downloads where the file is split into smaller parts and is transferred).

Users SC aggregator

Caching

Macro BS Internet File 1 File 2 ...files .. File N δ F ; T F TM BM1 ; T M δ M ; T M λ T F B F ; λ T F N c Tf n BS n ; T fn δ C ; (1 -λ)T F Fig. 1.
Congestion game with caching: Information on the delay and traffic through a link are labeled below it in the format (delay;traffic).

III. THE CONGESTION GAME

In Fig. 1 we present the schematic of the proposed congestion game. Here, 1 -λ is the average hit rate for requests arriving at the cache. We also take the traffic through the server corresponding to file n to be T fn . If we assume that the hit rate of file n is h(n) and m q(m)h(m) = 1-λ, then we can calculate the traffic through server n as:

T fn = q(n)N c (T M + T F (1 -h(n)) (1)
where N c is the number of cells in the region accessing the server for file n.

We now make use of the popular Che approximation for the hit rate in LRU caching buffers [START_REF] Fricker | A versatile and accurate approximation for lru cache performance[END_REF]:

h(n) = 1 -exp(-q(n)κ C ) (2)
where κ C is the unique solution of:

n (1 -exp(-q(n)κ C )) = C (3)
In a link X with backhaul B X and traffic T X , the delay is given by TX BX . Now, we can proceed to define the congestion game by defining:

1) The set of congestible elements

E = {U → M, U → F, F → C, F → I, M → I, f 1 , f 2 , . . . , f N }
where X -Y represents the congestible element between node X and node Y . The nodes are as defined in the schematic: U the users, M the MC, F the SC aggregator, C the cache, I the internet node and f n the server with file n.

2) The players are the users generating each traffic file, i.e T = {1, 2, ...T }.

3) The set of strategies which are subsets of E. Here clearly there are only two strategies possible S = {α, β} where α corresponds to download via the SC and β to download via the MC. 4) For each element e ∈ E the traffic or load is given by T e . 5) For the strategy α the net delay for file type n can be calculated as:

d α (n, T) =h(n) max(δ F , δ C )+ (1 -h(n)) max δ F , λT F B F , T fn B Sn
and

d β (n, T) = max T M B M , δ M , N c T fn B Sn (4)
It is a well known result that congestion games being potential games have at least one pure Nash equilibrium (NE). Hence, the next task is to study the NE and its efficiency.

A. The Nash equilibrium

In a hypothetical case where each user is aware of the popularity of his file request n and the probability of it being cached, the user's would be able to pick the strategy specific to n. However, based on our system model, these values are unknown at the user or network end. Therefore the users can observe only the average delays along paths α and β. Hence, the NE will be at the point where both of these paths have the same average delay. First, we will calculate the delay along each path when downloading a file n, when x users out of T opt to use the SC path as:

d α (n, x) = h(n) max(δ F , δ C )+ (1 -h(n)) max δ F , λx B F , q(n)N c (λx + T -x) B Sn
Similarly, the delay along the macro station path is:

d β (n, x) = max T -x B M , δ M , q(n)N c (λx + T -x) B Sn
(5) Let T F = x * be a possible NE solution, then x * can be found by solving [START_REF] Bastug | Proactive small cell networks[END_REF] [START_REF] Rosenthal | A class of games possessing pure-strategy nash equilibria[END_REF].

E n [d α (n, x * ) -d β (n, x * )] = 0 (6)

B. Equilibrium analysis

In this subsection we would like to analyze the NE obtained from [START_REF] Bastug | Proactive small cell networks[END_REF]. For this purpose, we make some assumptions on the delay parameters without much loss in generality. Note that these assumptions are just used for the simplification of the calculations and the following results can be proved even without them, but will involve a more convoluted, yet straightforward proof.

1) The primary delay when the file is found in cache is the backhaul; δ C < δ F < λx BF .

2) The macro backhaul has a very low delay;

δ M < T -x BM .
With these assumptions, we can prove that: Theorem 1: The NE of the defined congestion game is unique and ( 6) has a unique solution x * .

Proof: For this, we re-write [START_REF] Bastug | Proactive small cell networks[END_REF] as:

E n : (1 -h(n)) max λx B F , N c q(n)(λx + T -x) B Sn - max T -x B M , N c q(n)(λx + T -x) B Sn + h(n)δ F = 0 (7)
Now we study the summation over n which can be split into (1 -λ)δ F + P 1 + P 2 + P 3 defined by these threshold values

n (x) : λx B F = N c q(n )(λx + T -x) B Sn (8)
and

n (x) : T -x B M = N c q(n )(λx + T -x) B Sn (9)
The first part of the summation is independent of x, and so we focus on the other parts. P 1 is when n < n , n . In this case, the term is (assuming ordered files q(n) ≥ q(n + 1)):

P 1 : min(n ,m ) 1 -h(n)q(n)N c q(n)(λx + T -x) B Sn (10)
As λ < 1 this term is clearly increasing in x.

The term P 3 is when n > n , n . In this case, the term is:

P 3 : N max(n ,n ) q(n)N c λx B F - T -x B M (11)
Clearly, this term is also increasing in x.

Finally, if n > n , the term P 2 is when n > n > n . In this case, the term is:

P 2 : n n N c q(n) (1 -h(n))q(n) q(n)(λx + T -x) B Sn - T -x B M (12) Since by definition of n > n , T -x BM > N c q(n )(λx+T -x) BS n
, we can conclude that this term is also increasing in x by studying ∂P3 ∂x . For the case of n > n it can be trivially seen that all terms increase in x.

Therefore, we have shown that

E n [d α (n, x) -d β (n, x)] is a strictly increasing function of x. Therefore if E n [d α (n, x * ) -d β (n, x * )] = 0, this point x * is unique.

C. Quality of Service

Normally, the quality of service (QoS) criteria of such a network could be considered to be the average expected delay, i.e.:

δ(x) = E n [xd α (n, x) + (T -x)d β (n, x)] T (13)
However, there is also another possible QoS metric that can be studied, which is the expected maximum delay, i.e., the maximum delay encountered on average while downloading a file, maximized over all possible files and all possible paths.

δ(x) = max[max n {d α (n, x)}, max n {d β (n, x)}] (14)
This metric is highly relevant as this delay can cause the network to become potentially unstable. It can be seen that when δ(x) > τ , new users arrive into the network before the existing T users are finished downloading. As the users downloading this n-th file (with maximum delay), always encounters a higher delay on average, these users can potentially accumulate in the network destabilizing it 3 .

D. Price of Anarchy

We can define the global optimum for the average expected delay QoS criteria as min x δ(x). Thus the price of anarchy (PoA) is given by:

P oA 1 = δ(x * ) min x δ(x) (15)
where x * is the user allocation to the SC path at the NE. Similarly, when the QoS criteria is the expected maximum delay, the price of anarchy can be calculated as:

P oA 2 = δ(x * ) min x δ(x) (16
) 3 The user data traffic is simply given by φT τ in bits per second.

IV. NUMERICAL RESULTS

So far we have analyzed the NE and PoA from a mathematical perspective. However, in this section, we are interested in the practical application of our calculations. Specifically, we would like to consider a typical file popularity distributions and study the performance of the NE with various values of key parameters like the cache capacity C and the number of HCNs per server N c . Some of the general parameters used are: 1) File size φ = 100 MB and N = 10 6 files.

2) The file distribution is a Zipf style distribution with 10 files sharing the same rank, i.e the 11-th to 20th file is half as popular the 1st to 10th file, the 21st to 30th file is one third as popular as the 1st to 10th file etc. (total of N files). 3) Delays δ F = 1 s, δ M = 1 s and δ C = 1 s. 4) Bandwidths B M = 10 files per second or 1 GBps and B F = 5 files per second or 500 MBps. 5) Bandwidth of each server is taken to be a constant 10 files per second. The number of cells sharing the same server N c = 1000 unless otherwise indicated. 6) Number of users per cycle T = 300. A higher traffic condition would be represented by a smaller value for τ like 60 seconds, whereas a low traffic condition could be represented by τ = 180 seconds for example.

A. Cache performance

Based on the Che approximation and numerical calculations, we plot the average hit rate of the cache (1 -λ) against the Cache Capacity C in Fig. 2. From the figure, it can be seen that an average hit rate of 50% is achievable with C = 40dB, i.e, 10,000 files. As each file is assumed to be of 100 MB each, the scale on the X-axis can be seen as from a minimum cache capacity of 1 GB (10 dB) to a maximum at 10 TB (Terabytes).

B. QoS: expected average delay

We plot the average delay δ(x * ) at the NE against the Cache Capacity C in Fig. 3. From the figure, it can be seen that when the servers are under a higher load due to a larger number of cells accessing them (higher N c ), the improvement in the average delay is more pronounced due to a higher cache capacity. In Fig 4 ., the PoA for this QoS is plotted and it is interesting to see that the PoA is in both cases quite close to unity, i.e., the average delay at the NE is very close to the delay at the global optimum. Thus, the congestion game can be seen as "efficient" in terms of average delay. In Fig. 5, the population share for the SC at the NE x * is plotted against the cache capacity C. From the figure, it can be seen that when the servers are under a higher load (higher N c ), a higher population of users would tend towards choosing the SC, and this population share would grow with the cache capacity.

C. QoS: expected maximum delay

We plot the maximum expected delay δ(x * ) at the NE against the Cache Capacity C in Fig. 6. Similar to the the case of average delay, it can be seen that when the servers are under a higher load, the improvement in the maximum delay is also more pronounced due to a higher cache capacity. As seen from the figure, when N c = 1000, the network becomes congested even for the lower traffic case where τ = 180 s. In Fig. 7, the PoA for this QoS is plotted against the cache capacity. Unlike the case of average delay, the PoA is in fact quite large for both cases of high and low load on the servers (N c = 100 or 1000). Surprisingly, it can be seen from the figure that switching off the macro BS can actually help improve the maximum expected delay when (N c = 1000). Of course, in practice this would imply that if the macro-BS stop providing "heavy" data services (like video streaming) and only provide light data traffic (such as messaging), the users will be forced to demand heavy data traffic through the SCs resulting in a lower maximum expected delay.

Remark. 1: Note that, the parameters in this numerical simulation are only approximations or guesses of the real values. The parameters N -c, T and τ are all interrelated. A high traffic time (peak hours in the day) could be represented by N c = 1000 or by a large T . A larger N c implies that the servers are more heavily loaded due to higher global traffic, while a higher T corresponds to a higher local and global traffic.

Remark. 2: The result that actually switching off the macro BS (i.e., the heavy data traffic through the macro BS) can effectively reduce the maximum delay is a result similar to the situation of Braess's paradox in road traffic [START_REF] Braess | Über ein paradoxon aus der verkehrsplanung[END_REF]. Intuitively, this can be explained as users will naturally try to access data through the macro BS when then observe higher average download speeds via the macro network. However, the lower server speeds cause the congested files to adversely affect the maximum delay. Plotting the price of anarchy PoA2 against the Cache Capacity C.

V. CONCLUSION

This work has studied the congestion game, resulting from the heterogeneous network, where a user can chose to access a file through the caching enabled SC network, or through the macro network. We have shown that the resulting congestion game has a unique Nash equilibrium. This result ensures that the user behavior is predictable once the other parameters are known. Additionally after an extensive numerical analysis, we have studied the impact of the caching mechanism on the delay experienced by users. Surprisingly, it can be seen that in some specific cases, the expected maximum delay can be reduced by actually blocking users from downloading their requested files through the macro network.

This work has shown promising results and is ripe for many extensions. If we abandon the IRF (the assumption that file popularity is independent of time), the caching mechanism will become much more complicated and interesting. The hit rates of the new LRU cache would also depend on the data traffic as having a higher traffic of users would increase the update rate of the cache. This would imply that the resulting game will have a hit rate dependent on the user traffic which in turn depends on the hit rate. Other possible extensions would include accounting for multiple service providers, caching enabled at the SC base station level etc.

Fig. 2 .

 2 Fig. 2. Average hit rate of the cache (1 -λ) against the Cache Capacity C in dB.

Fig. 3 .

 3 Fig. 3. Plotting the average delay δ(x * ) at the NE against the Cache Capacity C.

Fig. 4 .

 4 Fig. 4.Plotting the price of anarchy PoA1 against the Cache Capacity C.

Fig. 5 .

 5 Fig. 5. Plotting the population share at the NE (on the SC) x * against the Cache Capacity C.

Fig. 6 .

 6 Fig. 6. Plotting the maximum expected delay δ(x * ) at the NE against the Cache Capacity C.

  N c = 1000, With HCN active N c = 1000, With Macro BS OFF N C =100, With Macro BS OFF N C =100, With HCN active

Fig. 7 .

 7 Fig. 7.Plotting the price of anarchy PoA2 against the Cache Capacity C.

These delays δF ,δS and δM are due to network architecture that cause small delays even when the backhaul is large.