1 Partially-Distributed Resource Allocation in Small-Cell Networks arXiv:1408.3773v1 [cs.NI] 16 Aug 2014 Sanam Sadr, Student Member, IEEE, and Raviraj S. Adve, Senior Member, IEEE Abstract—We propose a four-stage hierarchical resource allocation scheme for the downlink of a large-scale small-cell network in the context of orthogonal frequency-division multiple access (OFDMA). Since interference limits the capabilities of such networks, resource allocation and interference management are crucial. However, obtaining the globally optimum resource allocation is exponentially complex and mathematically intractable. Here, we develop a partially decentralized algorithm to obtain an effective solution. The three major advantages of our work are: 1) as opposed to a fixed resource allocation, we consider load demand at each access point (AP) when allocating spectrum; 2) to prevent overloaded APs, our scheme is dynamic in the sense that as the users move from one AP to the other, so do the allocated resources, if necessary, and such considerations generally result in huge computational complexity, which brings us to the third advantage: 3) we tackle complexity by introducing a hierarchical scheme comprising four phases: user association, load estimation, interference management via graph coloring, and scheduling. We provide mathematical analysis for the first three steps modeling the user and AP locations as Poisson point processes. Finally, we provide results of numerical simulations to illustrate the efficacy of our scheme. Index Terms—Small-cell networks, hierarchical resource allocation, Poisson point processes, graph coloring I. I NTRODUCTION Each new generation of wireless communication systems promises to support a larger number of mobile users with higher data rates, new applications and ever-more stringent quality of service (QoS) requirements [1]. In a modern communication system where the mobile user is almost always connected to the network, supporting a large number of users with various applications results in a mix of traffic demands (bursty vs. continuous, high vs. low data rate) from the network point of view and high battery consumption from the user equipment (UE) point of view. Meeting these demands is getting harder largely due to the limited availability of transmission resources, most importantly wireless spectrum. This makes it impossible to completely separate concurrent transmissions in frequency, in turn, making interference the main factor that limits the capabilities of the wireless networks. Much of the relevant recent research focuses on the issue of interference e.g., [2], and network analysis in an interferencelimited regime e.g., [3]–[6]. In the cellular context, an effective approach to increase capacity is to reduce the distance between the transmitter and This work was sponsored by TELUS and the National Science and Engineering Research Council (NSERC) Canada. The authors are with the Edward S. Rogers Sr. Department of Electrical and Computer Engineering, University of Toronto, 10 King’s College Road, Toronto, Ontario, Canada M5S 3G4 (email: {ssadr, rsadve}@comm.utoronto.ca). the receiver. This allows for a reduction in the transmit power and, in turn, improving the frequency reuse factor [7]. As an example of this approach, heterogeneous networks have been proposed to increase the area spectral efficiency1 and the overall capacity through a revised network topology. The idea is to introduce a multi-tier network where each tier, also referred to as a layer, differs mainly in the density of its access points (APs) and the AP transmit power, hence coverage area. The traditional macro-cellular network would be one layer in the heterogeneous network with carefully planned deployment, the lowest density and the highest transmit power; the smallcell layer, on the other hand, is characterized by essentially random deployment, a much higher AP density and low AP transmit power. The randomness in the AP locations in small cells and their significantly greater number within a chosen geographical area precludes globally optimized resource planning. This necessitates new analysis techniques and algorithms beyond those for the centrally planned macro-cellular layer. In this paper, we focus on resource allocation techniques in small cells and propose a partially-distributed hierarchical scheme which can be applied to a large-scale network. A. Related Work The analysis of the signal-to-noise-plus-interference-ratio (SINR) in a heterogeneous network has been presented for a single-layer [3] and multi-layer [4]–[6] network using Poisson point processes (PPP). The presented analyses are based on the statistical distribution of the SINR in the network derived at a reference user randomly located in the cell. It is shown in [3] that in an interference-limited network, as is the case in small cells, the probability of coverage when the user is associated with a layer is independent of the AP density and the transmit power. The same result is shown in a multi-layer network with all the layers having the same layer association bias factor and path loss exponent [4]–[6]. While the coverage analysis here is a measure of the level of the received SINR, it is only synonymous with a chosen QoS if the reference user is guaranteed some resources. In other words, in a network with high density of users, while the users might be in coverage when considering the received SINR, the rate available to the user depends on the scheduling algorithms used at each AP. Several resource allocation schemes have been proposed in the literature to mitigate RF interference in small cells in the context of femtocell networks. Femtocells are essentially user-deployed, indoor, small cells. Regardless of the details 1 Area spectral efficiency is defined as the sum throughput per unit area that the system can provide per unit bandwidth. 2 of the system under consideration, they can be categorized into autonomous power control [8]–[12] and adaptive spectrum allocation [13]–[18]. The main feature of the first group is to adjust the AP coverage by setting the transmit power high enough to service its users but low enough so as not to interfere with the other APs on the same frequency of operation. The schemes in the second group manage interference by ensuring orthogonality between interfering APs. A two-phase frequency assignment is proposed in [14], with a fixed, limited number of users per femtocell. Li et al. [15] viewed the user-deployed femtocells as the secondary system and the femtocell resource allocation as a cognitive spectrum reuse procedure. The idea is to adaptively adjust the channel reuse factor according to the location of the femtocell in the macrocell. Jointly optimizing power and spectrum, Kim et al. [17] proposed a scheme to maximize the total system capacity in dense networks. Treating the macro-users as primary users, the authors in [19] prioritize them by performing a hand-over to the nearby femtocell whenever the small-cell interference is high. The graph-based approach proposed in [18] maximizes the logarithmic average cell throughput to ensure proportional fairness among femtocells each serving a single user. A system level simulation of an open-access network was carried out by Claussen et al. [9], [10], and the obtained data rates at the reference users (one macro-user and one femto-user) were used to evaluate the system performance. Two main results are shown: 1) if autonomous power control is used by femtocells, adding APs has little impact on the macrocell throughput, and the impact is independent of the number of femtocells; 2) the total throughput significantly increases with the increase in the number of femtocell users, especially in the uplink. Similar results were reported in [4]– [6]. When analyzing the system, it is assumed that either the reference user is guaranteed some resources, e.g., in [2]–[6], or only voice is considered, e.g., in [16]. A more realistic simulation-based study of small-cell deployment in a heterogeneous network was reported by Coletti et al. [20]. The results suggest either coordination among layers or orthogonal spectrum allocation to improve outage rate. The authors of [21] propose a combination of fractional frequency reuse (FFR) and orthogonal spectrum allocation in a two-tier network differentiating between commercial and home-based femtocells. An ambitious goal in dense networks is to achieve optimal but decentralized resource allocation. The problem of decentralized power allocation was first addressed by Foschini et al. [22]. They showed that there exists a fully distributed algorithm which requires only local information if there exists a common, known, SINR at which the system performance is globally optimum, and there exists a feasible but unknown power vector that achieves this SINR. Unfortunately, these assumptions are hard to satisfy in practice [23]. The proposed distributed algorithms in [24], [25] maximize the total system capacity ignoring user rate requirements and fairness among the users both within and among cells while [12] aims for proportional fairness ignoring individual user rate requirements. To obtain a distributed solution, the authors in [24], [25] simplify the network model to an “interference-ideal" network where the total interference is constant and independent of user location in the cell. B. Our Approach and Contributions While there are several works on resource allocation in small-cell networks, as the literature survey above shows, it is hard to scale these algorithms to large-scale networks with multiple hundreds of nodes. Specifically, we consider the downlink of a large-scale network of small cells. Instead of focusing on SINR, we attempt to provide users with their desired data rate as they declare to their corresponding AP. Each AP transmits at its full transmit power and we focus on frequency allocation to avoid interference. To maintain fairness among users, we formulate the resource allocation in the form of a max-min normalized rate problem, maximizing the minimum ratio between the achieved and the desired rates. This problem is, in general, NP-hard. The main contribution of this paper is an effective solution to this resource allocation problem with reasonable computational complexity. We propose a hierarchical scheme by decomposing the problem into four steps. This scheme has several advantages. As opposed to a fixed spectrum allocation as in [13] and [16], it considers the AP load, in terms of the number of users and their rate requirements, when allocating spectrum to the APs. This adaptivity in spectrum allocation allows for resources to follow user demands, i.e., high-rate users can be satisfied by a single AP. The proposed scheme is partially-distributed in the sense that three of the four steps are carried out locally and concurrently at each AP and, at worst, involve solving convex optimization problems using local information only. A single, graph coloring step must be executed at a central server. In contrast to the globally optimal solution requiring exponential complexity and global knowledge of channel state information, our hierarchical scheme imposes limited complexity and requires local knowledge only. Given the difficulty with applying available algorithms to large-scale networks, we compare the results of our scheme with a network with fixed number of channels allocated to each AP, and show how load-awareness can effectively reduce the outage rate. As far as possible, we provide a mathematical analysis for the proposed scheme based on stochastic geometry [26]. In particular, we use independent homogeneous Poisson point processes for AP and user locations. PPPs have been shown to capture the inherent randomness in user and AP locations and yet provide tractable analyses compared to the grid-based models [3]. Necessarily requiring a number of simplifying assumptions, the analysis does provide results that track the related simulations and can, therefore, be used for system design. The paper is structured as follows: in Section II, we describe the system model and formulate the resource allocation problem. The proposed hierarchical algorithm is presented in Section III with the outage analysis based on homogeneous PPP. This section also presents a complexity analysis. Section IV presents the simulation results in two parts: (a) comparing the performance of the proposed algorithm with its associated analysis; (b) comparing the performance with a fixed resource 3 allocation scheme. The parameters used in the simulations are based on the Long Term Evolution (LTE) standard. Section V concludes the paper with a discussion of the contributions. II. D OWNLINK S YSTEM M ODEL AND S TATEMENT THE P ROBLEM Figure 1 illustrates the network under consideration. The model comprises K users and L APs distributed randomly in the network. The macro base station (BS) is provided an orthogonal frequency allocation, and our analysis considers only users connecting to the small cells. If the BS allocation is not orthogonal, it can be easily incorporated into the algorithm as another transmitting node in the network with its own power budget. Associated with each AP is its potential coverage area which depends on the environment and the transmit power. Due to the random geographical distribution of access points, the coverage area for some (if using the same time-frequency resource) may overlap. In other words, some users might be in a location covered by more than one AP and transmissions from these APs would interfere. User AP Fig. 1. Random distribution of APs and users in the network. The optimization problem is formulated in the context of OFDMA as in the LTE standard. There are N effective frequency subchannels - physical resource blocks (PRBs) in LTE - available in the system each with a bandwidth of B. The channels between APs and users are modeled as frequencyselective Rayleigh fading with average power determined by distance attenuation and large scale fading statistics. The goal is to provide each user with its requested data rate. However, to achieve overall fairness in doing so, we formulate the problem to maximize the minimum normalized rate, i.e., max-min over all the users’ achieved rates normalized by their requested data rates. The rate achieved on a specific channel is assumed to be given by its Shannon capacity; a gap function can be added to account for practical modulation and coding [27]. Each AP schedules its users in a manner to cancel the intra-cell interference. Therefore, the interference experienced by a user is due to the transmissions from all the access points, other than its own serving AP, that transmit on the same frequencies. Under this setting, the general form of the resource allocation problem in the downlink is given by: " N !# (l) (l) pk,n hk,n 1 X B log2 1 + PL , max min (i) (i) (l) 2 Rk n=1 {pk,n },{Sl } k i=1,i6=l pk,n hk,n + σ subject to: N X X (l) pk,n ≤ Ptot , l = 1, 2, ..., L, n=1 k∈Sl (l) pk,n ≥ 0, ∀k, n, l, Si ∩ Sj = ∅ i 6= j, L [ |Sl | = K, l=1 (l) hk,n (l) where and pk,n are, respectively, the channel power gain and the transmit power from AP l to user k on subchannel n. Sl is the set of users connected to and being serviced by AP l. Rk is the required rate by user k in bits per second (bps), σ 2 is the noise power, and B is the bandwidth of each subchannel. PL (i) (i) The sum, i=1,i6=l pk,n hk,n , is the cumulative interference experienced by user k on subchannel n from all the access points except the serving AP indexed by l. The first constraint is on the total transmit power of each AP, while the second ensures non-negative transmit powers on each subchannel. The L third constraint ensures that the sets, {Sl }l=1 , are disjoint, since each user is serviced by one and only one AP. The final constraint ensures that all the users in the system are scheduled by an access point. The sets, {Sl }L l=1 , therefore, form a partition on the set of all users. The objective of (1) is to find the optimal user associations, (l) L {Sl }L l=1 , and power levels, {pk,n }l=1 determining which user should receive service from which AP on which subchannel, and how much power should be allocated to each subchannel. Being combinatorial, since it includes set selection, finding the optimal solution is exponentially complex. It seems infeasible from another point of view as well: it requires the knowledge of all the subchannels for all the users from all the APs at the central location. Getting this information to a central server would impose a huge overhead. Furthermore, this information needs to be updated every time the channel estimation is performed. Essentially, a resource allocation scheme based on global and perfect knowledge of SINR in a network of such scale is practically infeasible. This motivates developing partially-distributed, if suboptimal, solutions. III. P ROPOSED H IERARCHICAL A LGORITHM In response to the infeasibility of obtaining the globally optimum solution, we propose a partially-distributed resource allocation scheme to decompose the problem into four steps: 1) Cell association: each user is associated with the AP that offers the highest long-term average received power (based, e.g., on a pilot and large-scale fading); 2) Load estimation: the load imposed by the users is estimated by each AP based on its users’ data rate requirements and average channel gains; 3) Channel allocation: specific subchannels are allocated to APs based on coloring an interference graph; (1) 4 4) Scheduling: each AP schedules its own users considering the users’ required data rates and their instantaneous channel gains. For each step, we derive the statistical distribution of the important quantities as accurately as possible, which are then used in analysis of the system performance, specifically the outage rate. at each AP indexed by l = 1, . . . , L given by: X min nk , nk ,Pk subject to: k∈Sl Pk Hk ≥ Rk , ∀k ∈ Sl , nk B log2 1 + nk σ 2 X Pk ≤ Ptot , (3) k∈Sl Pk ≥ 0, nk ≥ 0, ∀k ∈ Sl . A. Partially-Distributed Resource Allocation Step 1: Cell Association The cell association is based on the large scale fading only. This implies that the cell association is the same whether the system considers the uplink or the downlink. At each user, the received power from all the APs are measured, and the user is associated with the AP that offers the highest longterm average received power. This ensures maximum data rate on average and makes the cell association independent of the instantaneous channel gains. This cell association is consistent with the downlink model for the system analysis based on PPP considered in [3] and [5]. Analysis: Considering only distance attenuation, each user’s serving AP is the closest access point to the user. The statistical analysis of the connection distance is straightforward. Taking the user’s location as the reference point, the connection distance is d if there is no other access point closer to the reference point. Modeling the AP locations by a homogeneous Poisson point process with density λf , the cumulative density function (CDF) of d can be written as: FD (d) = P(D < d) = 1 − P(Nf (Ad ) = 0) =1 − exp(−λf πd2 ). = 2πdλf exp(−λf πd2 ), d ≥ 0, (a) ⇒ fD (d) (2) where Ad is the area of a circle with radius d and the user at the center, P(B) denotes the probability of event B, and Nf (Ad ) is the number of APs in Ad . (a) results from the null probability of a 2-D Poisson process. Differentiating FD (d) with respect to d gives the probability density function (PDF) in the final equation. Here, nk is the number (can be a fraction) of subchannels that AP l budgets for user k ∈ Sl . As before, Sl is the set of users supported by AP l. Pk and Hk are, respectively, the total power allocated to and the average channel power seen by user k. The first constraint ensures that the access point requests adequate resources to meet its users’ demands. The objective is to minimize the total amount of spectrum needed by AP l. This is important since it affects the density of the interference graph in the next step. Analysis: The load of the l-th AP in terms of the required amount of spectrum is a random variable given by: Nl = m X nk , where m = |Sl | is itself a random variable representing the number of users connected to AP l. The CDF of Nl in the general form is given by: !# " m X , (5) FNl (nl ) = Em,{nk } P nk ≤ nl k=1 where Em,{nk } denotes expectation with respect to m and {nk }m k=1 , and nk , k = 1, . . . , m are i.i.d random variables representing the required spectrum of each user. A thorough mathematical analysis of the load requires the knowledge of the number of users in each AP’s coverage area, also referred to as Voronoi cells, and the users’ distance to the serving AP. Due to the intractability of the problem, we derive the CDF for a special case where (i) all the APs have the same coverage area on average, (ii) equal power is allocated to each subchannel to estimate the load, and (iii) all the users connect at a distance equal to the most probable distance from the AP. We now state and prove the main result at this step. Proposition: Under the assumptions stated above, the CDF of the AP load is given by: FNl (nl ) = B(nl /n∗ , K, p), Step 2: Load Estimation With users having different rate demands, the objective at each AP is to estimate the minimum number of subchannels required to service its users. Each AP is aware of the requested rates and instantaneous channel gains for all the users that it serves. However, it does not know which subchannels it will be allocated, and fading is frequency selective. Therefore, it estimates its load using only the average channel gains. We emphasize that the load is defined here as the minimum frequency resources needed to meet the users’ rate demands. We formulate this problem as a convex optimization problem (4) k=1 (6) where B(nl /n∗ , K, p) is the CDF of a binomial distribution with K trials and probability of success p = 1/L evaluated at nl /n∗ (n∗ is defined later in (11) to be the number of subchannels required by each user). Proof: In a network with L APs, the probability that a user is in the coverage area of a specific AP is 1/L. Since user locations are random and independent, the probability mass function of the number of users m connecting to an access point is a binomial distribution given by: K m K−m Pu (m) = p q , (7) m 5 where p = 1/L and q = 1 − p. From the first constraint in (3), the minimum required number of subchannels for user k with equal transmit power on each subchannel can be rewritten as: Rk nk = , (8) B log2 (1 + Ptot Hk /N σ 2 ) where Hk = L0 d−α , d is the distance between the AP and the user, L0 is the path loss at the reference distance (r0 = 1m), and α is the path loss exponent. Setting γ0 = Ptot L0 /N σ 2 and using FD (d) derived in (2), the CDF of the user load Fnk (n) can be written as: Fnk (n) = P(n k < n) Rk =P <n −α B log2 (1 + γ0 d ) Rk −α = P log2 (1 + γ0 d ) > nB −1/α ! Rk /nB 2 −1 =P d< γ0 Rk /nB −1/α ! 2 −1 . = FD γ0 (9) As shown in Fig. 5 in Section IV, this CDF approaches a step function as λf increases. In other words, in a dense network of small cells, the variance of the user load decreases. This motivates one to represent the user load in high-density AP networks with a single number rather than a random variable. Amongst various possibilities, the most probable link distance best predicts this number. Differentiating fD (d) with respect to d and setting it to zero, the most probable link distance is given by: s 1 d∗ = . (10) 2πλf Inserting d∗ in (8), the number of subchannels required by each user is given by: n∗ = Rk . B log2 (1 + γ0 (d∗ )−α ) (11) Using (4), the CDF of the AP load is then derived as: FNl (nl ) = P(Nl ≤ nl ) = P(n∗ m ≤ nl ) = P(m ≤ nl /n∗ ) = B(nl /n∗ , K, p), (12) where the last equation results from the distribution of m derived in (7) and the proof is complete. For a large K, the binomial distribution is very well approximated by a Poisson distribution with parameter η = K/L when η is small, and by a normal distribution when η is large [28]. In this paper, we will make use of the Poisson approximation. Step 3: Channel Allocation Among APs Using Graph Coloring After steps 1 and 2, users have been assigned to APs and the APs have estimated their loads. We now come to the crucial step of allocating subchannels to APs. Specifically, the objective at this step is to allocate the spectrum to the APs considering their load and the interference they can potentially cause to other small cells. In this paper, we consider a resource allocation scheme which avoids interference. To do so, we ensure that two neighboring small cells do not use the same frequencies. Small cells are considered neighbors if they potentially interfere with each other, i.e., their potential coverage areas overlap. Unlike the previous two steps (and the next step), this allocation is centralized. L All the access points report their load {Nl }l=1 to the central server. Ideally, the central server should allocate an orthogonal set of subchannels to every AP that also meets its users’P requirements. Given N total available subchannels, L if N ≥ l=1 Nl , each AP is easily satisfied. Realistically, however, this is highly unlikely; hence, the server must reuse channels across multiple APs. This can cause interference, and so the allocation must ensure that the interfering APs (APs with overlapping coverage areas) are assigned orthogonal frequency resources. As a consequence, it may be that all APs’ load demands cannot be satisfied. Alternatively, the goal is to assign subchannels to APs proportional to their estimated load while eliminating the interference among them. To do so, we use graph coloring by the central server. Graph algorithms have been used as a tool for channel assignment in multi-cellular networks, e.g., in [29]–[34], with the nodes representing either access points or users. Chang et al. [30] formulated the spectrum allocation in a macrocellular network in the form of max K-Cut with a fixed number of channels (or colors). Each node in the graph corresponds to a mobile device or user. The interference among users is denoted by weighted edges taking into account not only the distance between the users but also the anchor (serving) and the neighboring base stations. The objective is to partition the users into K clusters with maximum inter-cluster weight. This technique allows for asymmetrical channel allocations among the base stations. Authors in [32] proposed a two-step graph coloring approach for multicell OFDMA networks in which the users are clustered in a manner to minimize the total number of colors based on geographic user locations. In the second step, the subchannels are allocated based on instantaneous channel conditions. In graph-based schemes, wherever users correspond to graph nodes as in [32] and [34], user mobility results in rapid changes of the interference graph. Since we deal with small cells in a dense network, this computation is added to the signalling overhead due to handoff and synchronization among APs making it impractical. The authors in [31] differentiate between the cell centre and cell edge hence allowing for FFR. This approach assumes large cells, an assumption that is not valid here. Finally, the twostep spectrum allocation algorithm proposed in [33] uses the instantaneous channel information in deriving femtocells’ utilities while coloring the graph resulting in increased complexity and signalling overhead. In our approach, the nodes of the graph represent access points. An edge connects two nodes if they potentially interfere based on large-scale statistics. We make this choice to ensure that the graph does not change rapidly with each channel realization. While here we use an unweighted graph, this is not 6 fundamental to the proposed scheme. A weighted graph can very well be used instead, at the cost of increased complexity as long as the edge weights correctly reflect the intensity of the interference between any two nodes. Since each color corresponds to a single subchannel, to account for the AP loads, we modify the interference graph as follows: as opposed to the conventional approach, AP l is represented by not one but ⌈Nl ⌉ nodes forming a complete subgraph (⌈·⌉ denotes the “ceiling" function). The problem of channel assignment among APs becomes a graph coloring problem where two interfering nodes (nodes connected with an edge) should not be assigned the same color. An example of a three AP network with (estimated) N1 = 1, N2 = N3 = 3 is illustrated in Fig. 2. The corresponding interference graph is shown in Fig. 3. AP #1 potentially interferes with AP #2 and AP #3. So, allocations to AP #1 cannot be reused for AP #s 2 or 3. However, since AP #2 does not interfere with AP #3, frequencies can be reused across these two APs. One solution to the coloring problem is illustrated in Fig. 4. It is worth noting that the coloring is not unique. For example, a simple index shift (a re-ordering of the association between the graph and the frequency slots) is an equally valid solution to the graph coloring problem. Amongst these many solutions, there is one optimal solution that best meets the demands of the individual APs based on the specific instantaneous realizations of user-AP channels. However, none of this information is available at the central sever; this lack of optimality is the penalty for using a distributed algorithm with limited knowledge of CSI. For arbitrary graphs, graph coloring is an NP-hard problem. The optimal coloring is possible with low complexity algorithms if the interference graph is sparse such that each node is connected to at most N nodes where N is the total number of available colors. Such graphs can be colored with a modified Breadth First Search (BFS) algorithm with complexity of O(|V | + |E|) with |E| = O(|V |) where |E| and |V | are the cardinality of edges and vertices respectively. We adopt the heuristic (greedy) algorithm proposed by Brélaz [35]: at every iteration, the vertex which is adjacent to the greatest number of differentely-colored neighbours is colored, with a new color if necessary (until colors are exhausted). A major advantage of our proposed hierarchical scheme is that by carrying out the graph coloring step in a distributed manner as proposed in [36], we achieve a fully distributed scheme. Outage Analysis: While coloring an interference graph results in a higher spatial reuse factor for a channel, outage is inevitable if an access point and its interfering neighbours require more than the available number of subchannels. Let p˜ be the AP pilot power and τ be its receive threshold determining the coverage area. Two APs separated by r˜ = 2d˜ interfere if the received power at the midpoint of the distance between the two satisfies p˜d˜−α > τ . Now, taking a randomly chosen AP as the reference, we prove the following statement. Proposition: The probability that the reference AP and its neighbours will not have enough spectrum, hence leading to AP #1 AP #2 AP #3 Fig. 2. A network of 3 APs. N1 = 1, N2 = N3 = 3. AP #2 AP #3 AP #1 Fig. 3. Interference graph corresponding to Fig. 2. Fig. 4. Graph coloring corresponding to Fig. 3. Minimum number of colors is 4, with both optimal and suboptimal coloring algorithms. an outage, is given by: Po = 1 − L h i X ˜ ˜ , Pois(N/n∗ , Lη)P Nf (Ar˜) = L (13) ˜ L=1 ˜ is the number of APs in the area Ar˜ = π˜ where L r2 , −λf Ar ˜ ˜ ˜ ˜ = e (λf Ar˜)L , and Pois(N/n∗ , Lη) P Nf (Ar˜) = L ˜ L! ˜ is the CDF of the Poisson random variable with mean Lη evaluated at N/n∗ . ˜ − 1 be the total number of APs interfering Proof: Let L ˜ APs cannot share the same with the reference AP, i.e., L subchannel. The CDF of the minimum required number of ˜ such that our reference AP can support its subchannels N 7 users (without interfering with its neighbours) is given by: ˜ = P(N ˜ ˜ FN˜ (˜ n|L) ˜ |L) P≤˜ n L ˜ =P N ≤ n ˜ | L l l=1 ˜ = Pois(˜ n/n∗ , Lη), (14) ˜ independent Poisson where we use the fact that the sum of L random variables with mean η is a Poisson random variable ˜ The probability of outage is then given by: with mean Lη. h i ˜ > N ) = E ˜ [1 − F ˜ (N )] Po = EL˜ P(N L N L h i X ˜ P Nf (Ar˜) = L ˜ = 1 − FN˜ (N |L) ˜ L=1 =1− L h i X ˜ ˜ , Pois(N/n∗ , Lη)P Nf (Ar˜) = L ˜ L=1 (15) and the proof is complete. Unfortunately, it does not appear that this final expression can be further simplified. However, the summation is easily evaluated numerically. In a system with L points of a Poisson ˜ is binoprocess (representing APs) uniformly distributed, L mial with L trials and probability of success (˜ r/Rc )2 where Rc is the radius of the macrocell under consideration. FN˜ (˜ n) is the CDF of a Poisson random variable and can be calculated using the incomplete gamma function. Step 4: Resource Allocation Among Users At the end of step 3, each AP is assigned an integer number of subchannels without interfering with its neighbours. The problem at each AP is now reduced to maximizing the minimum rate of the users it services relative to their requested data rate. In doing so, the AP considers the instantaneous CSI of the subchannels it has been assigned. In this regard, it is worth restating that the previous three steps were based on average channel powers. ¯l be the number of subchannels assigned to AP l in Let N Step 3; this is not necessarily equal to its estimated requirement Nl . The scheduling problem at each AP is formulated as: ¯l N X 1 pk,n hk,n max min B ck,n log2 1 + pk,n ,ck,n k Rk ck,n σ 2 n=1 subject to ¯l N X X pk,n ≤ Ptot , pk,n ≥ 0 n=1 k∈Sl X ck,n = 1, k∈Sl ck,n ≥ 0 ∀n, k ∈ Sl (16) where ck,n is the fraction of subchannel n allocated to user k. hk,n and pk,n are the channel power gain and the transmit power to user k on subchannel n. This is a standard convex optimization problem. An even simpler alternative is to divide ¯l subchannels, pk,n = Ptot /N ¯, power equally amongst the N leading to a linear program in which users share the resources using time-division2. B. Complexity Analysis Step 1 - cell association: Each user connects to the AP with the highest average received power. Finding the AP with the maximum received power requires L comparisons at each user. Hence, the complexity of this step is of the order O(L) for each of K users. Step 2 - load estimation: This is a convex optimization problem with the complexity depending on the solution method, e.g., the interior-point method or Newton-Raphson. Furthermore, the number of iterations in each depends on the stopping criterion. In Newton-Raphson method, the computational complexity mainly results from finding the update direction. It is shown that the computational complexity of each iteration is O(M 3 ), where M is the number of users connected to one AP. The details are provided in the Appendix. Step 3 - spectrum allocation among APs: This step consists of two smaller steps. 1) Forming the interference graph: any two APs closer than a threshold distance are connected with an edge. Hence, the complexity of this step is of the order O(L2 ). 2) Graph coloring: the complexity depends on the density of the graph algorithm as provided in Step 3 of Subsection III-A. Since this step is carried out at the central unit, with slower changes compared to locally solved problems, more sophisticated algorithms can be used. Step 4 - scheduling: The normalized rate scheduling at this step is a modified version of the problem formulated by Rhee et al. [37]. A special case is when equal transmit power is used on all the subchannels leading to close to optimum performance when the system benefits from user-channel diversity. The proposed suboptimal subchannel allocation with ¯l ), where N ¯l equal transmit power has complexity of O(M ∗ N is the number of PRBs allocated to the AP. IV. S IMULATION R ESULTS In this section, we evaluate the performance of the proposed scheme and the mathematical analysis presented in the previous section. The simulations are based on the LTE standard closely following [38]. The downlink transmission scheme for an LTE system is based on OFDMA where the available spectrum is divided into multiple subcarriers each with a bandwidth of 15kHz. Resources are allocated to users in blocks of 12 subcarriers referred to as physical resource blocks; hence, the bandwidth of each PRB is 180kHz and is used as the signal bandwidth in calculating the noise power. The receiver noise power spectral density is set to -174dBm/Hz with an additional noise figure of 9dB at the receiver. Here, we consider the maximum LTE bandwidth (20MHz); N = 50 PRBs are allocated to the small-cell network. The APs are distributed within a circle of radius 100m, i.e., covering 3.14 × 104 m2 . Table I lists the parameters used in all the simulations, unless otherwise specified. 2 Standards such as LTE provide the ability to reassign physical resource blocks every millisecond. Such flexibility is reflected here as time-sharing of the subchannels. 8 TABLE I S IMULATION PARAMETERS Region covered (Rc ) Value 2 GHz 20 MHz 15 kHz 180 kHz 50 20dBm 0dB 1×1 9dB 1m from AP 10dB/3dB 1 0.9 Analysis − high density Simulation − high density Analysis − low density Simulation − low density 0.8 0.7 CDF of User Load Parameters Carrier frequency Channel bandwidth Carrier spacing Resource block (B) Number of PRBs available (N ) Transmit power Antenna gain Antenna configuration Noise Figure in UE Minimum distance of user Penetration loss (wall/window) d˜ 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.5 1 20m Circle of radius 100m 1.5 2 2.5 3 3.5 4 Numb er of PRBs Fig. 5. CDF of the user load Fnk (·) for high (λf = 1/100m2 ) and low (λf = 1/1000m2 ) AP density. Rk = 5Mbps. The path loss between the access point and the user accounts for indoor and outdoor propagation: 1 PL = 38.46 + 20 log10 (din ) + 37.6 log10 (d) + Lp + Ls (17) 0.8 0.7 CDF of AP Load where din is the distance between the access point and the external wall or window and has a uniform distribution between 1m and 5m; Lp is the penetration loss and is set to 10dB or 3dB (with equal probability) representing an external wall and window respectively; Ls accounts for shadowing and is modeled by a log-normal random variable with standard deviation of 10dB. Finally, assuming Rayleigh fading, the instantaneous power of the received signal is modeled as an exponential random variable with the mean equal to the average received power [39]. In the mathematical analysis, the path loss exponent, α, is set to 3. The multipath environment is such that the fading is effectively flat for the 12 subcarriers in one PRB but rich enough to yield an independent fade on each PRB. Each PRB is then allocated to a user for a subframe duration of 1ms. 0.9 0.6 0.5 0.4 0.3 0.2 Analysis Simulation − Fixed AP location Simulation − Random AP location 0.1 0 0 5 10 15 20 25 Numer of PRBs Fig. 6. CDF of the AP load FNl (·). λf = 1/(100m2 ), λu = 5λf and Rk = 5Mbps. A. Validating the Mathematical Analysis First, we validate the mathematical analysis of the proposed hierarchical algorithm. Figure 5 plots the CDF of the user load Fnk (·) for two cases: high (λf = 1/100 or 1 AP per 100m2 corresponding to 314 APs) and low (λf = 1/1000) AP density. At each run of the simulation, the APs and the users are randomly located in the cell according to the given densities with user density denoted by λu . Each user connects to the closest access point. The user load is then calculated for a randomly chosen user (as the reference) with equal transmit power on all the PRBs considering only the distance attenuation. The result is compared to the CDF derived in (9). As is clear, the analysis matches the simulation results exactly. Also, as expected, the CDF is shifted to the right in a network with lower AP density; the reason is a larger connection distance and a higher load (measured in terms of required subchannels) imposed by the user for the same data rate. Crucially, the figure shows that the CDF of the individual user load approaches a step function at a higher AP density. This justifies the approximation in (11). Figure 6 plots the CDF of the load of a randomly chosen access point in two scenarios: (i) random AP location as in PPP; (ii) fixed AP location with equal coverage area for all the APs. In both cases, the load of the reference AP is the sum of its users’ load. The CDF derived in (12) slightly deviates from the simulation results due to two main simplifying assumptions: 1) all APs have the same coverage area on average leading to a binomial distribution for the number of users connecting to an AP; 2) the most probable connection distance has been assumed for all the users connecting to an AP based on the AP density in the system. In a system where APs are randomly located, although uniformly distributed, they might have different coverage areas. For the purpose of comparison, a network with fixed AP locations is considered with equal coverage area for all APs. In such a system, Pu (m) 9 B. Performance Comparison 0.9 Analysis Simulation CDF of System Load 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 20 40 60 80 100 120 140 Numb er of PRBs Fig. 7. CDF of the system load FN˜ (·). λf = 1/(100m2 ), λu = 5λf and Rk = 1Mbps. follows the binomial distribution. A small deviation still exists due to the second simplifying assumption. The CDF of the system load, FN˜ (·) is shown in Fig. 7. The system load is the sum of the total number of PRBs required by a randomly chosen access point (as the reference) and all its interfering APs derived in (14). If the distance ˜ where d˜ is the radius between two APs is no more than 2d, of the coverage circle of one AP, the pair are assumed to interfere with each other. A lower SNR threshold results in a larger coverage area for each AP and a denser interference graph. Note that, for any SNR threshold, this is the worstcase scenario assuming the user is in the midpoint of the distance between the two APs. In practice, whether two APs interfere can be estimated more accurately by each AP based on a pre-defined coalition threshold [40] and reported to the central server (most protocols allow an access point to keep a “neighbour" list). Figure 8 plots the corresponding outage probability as a function of the common user demand Rk = R. Again, the analysis captures the essential behaviour of the outage probability with a slight mismatch due to the simplifying assumptions mentioned before for tractability. 1 In this section, we illustrate the performance of the proposed hierarchical scheme and compare its performance with a fixed-allocation scheme. The globally optimal solution through exhaustive search is impossible to obtain in a reasonable time due to its exponential complexity and so is not compared to. The fixed-allocation scheme is as follows: each AP is assigned NAP PRBs randomly chosen out of the N PRBs available to the small-cell network. The cell association and user level scheduling is the same for both algorithms. Hence, the main differences between the fixed-allocation and the proposed hierarchical scheme are the element of interference management and the effect of load estimation in dynamic distribution of PRBs among APs. The purpose of such dynamic distribution is to improve the user’s achieved rate in the whole system proportional to its demand. A user is considered to be in outage when it receives less than its required data rate. In a network with fixed spectrum allocation, NAP affects the density of the interfering APs [3]. We first consider the performance of the fixed-allocation scheme as a function of NAP , the number of PRBs assigned to each AP. Figure 9 plots the number of the users in outage normalized by the total number of the users for two user densities. All the users request the same data rate of 1.5Mbps. As shown in the figure, the outage decreases with NAP to a point where it is saturated such that further increase in NAP results in higher interference and hence, outage. In this example, NAP = 18 gives the best performance for the given AP and user densities. In subsequent testing, we use a fixed value of NAP = 18. This allows for a comparison of our results to the best-case scenario for the fixed-allocation scheme. 1 λ /λ = 3 u f λu/λf = 6 0.9 0.8 Outage Rate 1 0.7 0.6 0.9 0.5 0.8 Outage Rate 0.7 0.4 0 0.6 5 10 15 20 25 N AP 0.5 Fig. 9. Outage rate as a function of the fixed number of PRBs assigned to each AP. λf = 1/(200m2 ), λu = 3λf and λu = 6λf . Rk = 1.5Mbps. 0.4 0.3 0.2 0.1 0 0 Analysis Simulation 0.5 1 1.5 2 2.5 User demand (Mbps) Fig. 8. Outage rate versus user demand. λf = 1/(200m2 ) and λu = 5λf . The outage (in a log-scale) for both schemes versus the user demand is shown in Fig. 10. As expected for both algorithms, the number of users in outage increases with the increase in the user demand. In both user-to-AP densities (λu /λf ), there is an obvious gain with using the hierarchical scheme - the outage rate improves by up to an order of magnitude at the lower user demands. It is worth noting that at high user 10 0 10 −1 Outage Rate 10 −2 10 Fixed−Allocation λu/λf = 3 −3 Hierarchical λu/λf = 3 10 Fixed−Allocation λu/λf = 6 Hierarchical λu/λf = 6 0 0.5 1 1.5 2 2.5 User Demand (Mbps) Fig. 10. Users at outage in both schemes versus the user demand. λf = 1/(200m2 ), λu = 3λf and λu = 6λf . NAP = 18 for the fixed-allocation. 2.5 Fixed−Allocation λ /λ = 3 u f Hierarchical λ /λ = 3 u f Fixed−Allocation λ /λ = 6 u f Hierarchical λ /λ = 6 Min User Rate (Mbps) 2 u f User demand 1.5 1 the path loss model. Hence, the comparison here is between the worst-case scenario of the hierarchical scheme and the best-case scenario of the fixed-allocation. Using weighted interference graphs and more sophisticated graph algorithms in Step 3 should improve the performance at the cost of increased computational complexity. A significant advantage of the proposed scheme is to shift the available spectrum from the underloaded APs to the overloaded APs to achieve higher level of fairness over all the users in the network. Examining the minimum achieved user rate in the system in Fig. 11 shows that our proposed scheme achieves this goal. While both schemes converge to a constant value with the increase in the user demand, the hierarchical scheme reaches a higher value (more than twice the minimum rate in fixed-allocation) for both user densities. Any user achieved rate would fall between the minimum achieved rate and the user demand (the maximum rate assigned to the user represented by the dotted line). The closer the two are, the higher level of fairness is achieved. In other words, the hierarchical scheme achieves a higher degree of fairness and is more efficient in terms of allocating resources in comparison to the fixed resource allocation. It is worth noting that this gain is higher in a system with a lower user-to-AP density. The reason is that in a network with independent user locations, the probability density function of the user distribution in a unit area (and hence the AP load) approaches a dampened normal distribution as opposed to a Poisson distribution with the increase in the user density. This effect corresponds to a smaller variance in the AP load in the system. The proposed scheme is most effective in systems with higher possibility of underloaded and overloaded APs existing at the same time which explains the higher gain in λu = 3λf compared to λu = 6λf . As a final comparison, Fig. 12 plots the total throughput of the system. The higher throughput in the hierarchical scheme is the result of higher user achieved rate as discussed above. 0.5 V. C ONCLUSION 0 0 0.5 1 1.5 2 2.5 User Demand (Mbps) Fig. 11. Average minimum user achieved rate for both schemes versus the user demand. λf = 1/(200m2 ), λu = 3λf and λu = 6λf . NAP = 18 for the fixed-allocation. demands (above Rk = 1.5Mbps for λu /λf = 6 and above Rk = 2.5Mbps for λu /λf = 3) the fixed-allocation scheme actually has a lower outage. This is to be expected since in the hierarchical scheme, any two APs that are less than r˜ meters apart are connected in the interference graph regardless of the degree of interference. This results in higher system load estimation and smaller number of PRBs allocated to each AP in the system. In the fixed-allocation scheme on the other hand, due to the lack of any interference management, the effect of concurrent transmissions are added exactly according to In this paper, we have proposed a hierarchical 4-stage resource allocation scheme for large-scale small-cell networks. The main advantage of the proposed scheme is decomposing a complex non-convex optimization problem into several smaller convex problems with smaller sets of optimization variables. The result is a low complexity scheme effective with a large problem size; in our simulations, the resource allocation can be achieved across as many as 314 APs. The rationale behind the introduced hierarchy is as follows: user locations combined with various user demands result in a non-uniform distribution of the load in the system. Access points will experience very different load demands as shown in Fig. 6. Hence, in an efficient allocation, resources should be dynamically allocated to meet this load. Here, this load is approximated at each AP by solving the related optimization problem based on the local information, i.e., users’ demand and the average channel power. To do so, the APs do not require any global information. Load estimation and the last step of resource allocation at the APs would, in practice, be 11 1200 for k = 1, 2, . . . , M , where C = B log2 e and M = |Sl | are for simplicity of presentation. From (20), we obtain: Fixed−Allocation λu/λf = 3 Hierarchical λ /λ = 3 u µ 1 H1 µ k Hk = . (21) P1 H1 k 1 + PnkkH 1 + n1 σ2 σ2 P Combined with the power constraint k∈Sl Pk = Ptot , Pk Hk and the rate constraints nk B log2 1 + nk σ2 = Rk , k = 1, 2, . . . , M , there are 3M variables {Pk , nk , µk }M k=1 in the set of 3M non-linear equations in (19)-(21). Iterative methods such as Newton-Raphson can be used to obtain the solution, with the complexity mainly due to finding the update direction. Denote X = [P1 , . . . , PM , n1 , . . . , nM , µ1 , . . . , µM ]⊺ as the variables and G = 0 as the square system of non-linear equations. The update direction ∆X is found solving the following equation: f Fixed−Allocation λ /λ = 6 u Total Throughput (Mbps) 1000 f Hierarchical λu/λf = 6 800 600 400 200 0 0 0.5 1 1.5 2 2.5 User Demand (Mbps) Fig. 12. Total throughput of the system for both schemes versus the user demand. λf = 1/(200m2 ), λu = 3λf and λu = 6λf . NAP = 18 for the fixed-allocation. solved in parallel at each AP. Only a single step of graph coloring is executed at a central server - this centralized step ensures orthogonal allocations to APs that interfere with each other. The central server only requires knowledge of the demands made by each AP which significantly reduces the signaling overhead. The results confirmed an increase in the user’s achieved data rate with the proposed hierarchical scheme as apposed to the fixed resource allocation. Across a wide range of user rate demands, the scheme results in a significantly lower outage. Finally, the simulations confirm that the proposed scheme is most effective in systems with a higher possibility of underloaded and overloaded APs existing simultaneously. A PPENDIX C OMPLEXITY A NALYSIS FOR S TEP 2: LOAD ESTIMATION The load estimation problem in (3) is equivalent to finding the minimum of the following cost function X X Pk Hk L= nk + µk Rk − nk B log2 1 + nk σ 2 k∈Sl P k∈Sl +µ0 k∈Sl Pk − Ptot , (18) |Sl | where {µi }i=0 are the Lagrangian multipliers. Differentiating (18) with respect to Pk and nk , and setting each derivative to 0, we obtain: ∂L P H P H k k k k = 0, − = 1−µk C ln 1 + ∂nk nk σ 2 k σ 2 nk 1 + PnkkH σ2 (19) k µk C H ∂L σ2 + µ0 = 0, (20) =− k ∂Pk 1 + Pσk2H n k J (X)∆X = −G(X), (22) where J (X) is the Jacobian matrix of G(X) evaluated at X. Using Gauss-Jordan method, the complexity of the algorithm to solve for ∆X in each iteration is of the order O(M 3 ). A special case is when equal transmit power is used on the subchannels; in this case, estimating the load at each AP has the complexity of the order O(M ) (due to M divisions at each AP). R EFERENCES [1] D. C. Kilper, G. Atkinson, S. K. Korotky, S. Goyal, P. Vetter, D. Suvakovic, and O. Blume, “Power trends in communication networks,” IEEE J. Sel. Topics Quantum Electron., vol. 17, no. 2, pp. 275–284, Mar.-Apr. 2011. [2] M. Haenggi and R. K. Ganti, “Interference in large wireless networks,” Foundations and Trends in Networking, vol. 3, no. 2, pp. 127–248, 2008. [3] J. G. Andrews, F. Baccelli, and R. K. Ganti, “A tractable approach to coverage and rate in cellular networks,” IEEE Trans. Commun., vol. 59, no. 11, pp. 3122–3134, Nov. 2011. [4] H. S. Dhillon, R. K. Ganti, and J. G. Andrews, “A tractable framework for coverage and outage in heterogeneous cellular networks,” Inf. Theory and Appl. Workshop (ITA), Feb. 2011. [5] H.-S. Jo, Y. J. Sang, P. Xia, and J. G. Andrews, “Heterogeneous cellular networks with flexible cell association: A comprehensive downlink SINR analysis,” IEEE Trans. Wireless Commun., vol. 11, no. 10, pp. 3484– 3495, Oct. 2012. [6] H. S. Dhillon, R. K. Ganti, F. Baccelli, and J. G. Andrews, “Modeling and analysis of K-tier downlink heterogeneous cellular networks,” IEEE J. Sel. Areas Commun., vol. 30, no. 3, pp. 550–560, Apr. 2012. [7] V. Chandrasekhar, J. G. Andrews, and A. Gatherer, “Femtocell networks: A survey,” IEEE Commun. Mag., vol. 46, no. 9, pp. 59–67, Sept. 2008. [8] A. Barbieri, A. Damnjanovic, T. Ji, J. Montojo, Y. Wei, D. Malladi, O. Song, and G. Horn, “LTE femtocells: System design and performance analysis,” IEEE J. Sel. Areas Commun., vol. 30, no. 3, pp. 586–594, Apr. 2012. [9] H. Claussen, “Performance of macro- and co-channel femtocells in a hierarchical cell structure,” in Proc. PIMRC, Sept. 2007. [10] H. Claussen, L. T. W. Ho, and L. G. Samuel, “An overview of the femtocell concept,” Bell Labs Technical Journal - Wiley, vol. 13, no. 1, pp. 221–245, 2008. [11] V. Chandrasekhar, J. G. Andrews, T. Muharemovict, Z. Shen, and A. Gatherer, “Power control in two-tier femtocell networks,” IEEE Trans. Wireless Commun., vol. 8, no. 8, pp. 4316–4328, Aug. 2009. [12] F. Ahmed, A. A. Dowhuszko, and O. Tirkkonen, “Distributed algorithm for downlink resource allocation in multicarrier small cell networks,” in Proc. ICC, pp. 6802–6808, Jun. 2012. [13] V. Chandrasekhar and J. G. Andrews, “Spectrum allocation in twotier networks,” in Proc. IEEE Asilomar Conf. on Signals, Systems and Computers, pp. 1583–1587, Oct. 2008. 12 [14] D. Lopez-Perez, A. Ladanyi, A. Juttner, and J. Zhang, “OFDMA femtocells: A self-organizing approach for frequency assignment,” in Proc. PIMRC, pp. 2202–2207, Sept. 2009. [15] Y.-Y. Li, M. Macuha, E. S. Sousa, T. Sato, and M. Nanri, “Cognitive interference management in 3G femtocells,” in Proc. PIMRC, pp. 1118– 1122, Sept. 2009. [16] Y. Zhang, “Resource sharing of completely closed access in femtocell networks,” in Proc. WCNC, Apr. 2010. [17] J. Kim and D.-H. Cho, “A joint power and subchannel allocation scheme maximizing system capacity in dense femtocell downlink systems,” in Proc. PIMRC, pp. 1381–1385, Sept. 2009. [18] K. Zheng, Y. Wang, C. Lin, X. Shen, and J. Wang, “Graph-based interference coordination scheme in orthogonal frequency-division multiplexing access femtocell networks,” IET Commun., vol. 5, no. 17, pp. 2533– 2541, Nov. 2011. [19] L. Li, C. Xu, and M. Tao, “Resource allocation in open access OFDMA femtocell networks,” IEEE Wireless Commun. Lett., vol. 1, no. 6, pp. 625–628, Dec. 2012. [20] C. Coletti, L. Hu, N. Huan, I. Z. Kovács, B. Vejlgaard, R. Irmer, and N. Scully, “Heterogeneous deployment to meet traffic demand in a realistic LTE urban scenario,” in Proc. VTC, Sept. 2012. [21] A. Mahmud and K. A. Hamdi, “Hybrid femtocell resource allocation strategy in fractional frequency reuse,” in Proc. WCNC, pp. 2283–2288, Apr. 2013. [22] G. Foschini and Z. Miljanic, “A simple distributed autonomous power control algorithm and its convergence,” IEEE Trans. Veh. Technol., vol. 42, no. 4, pp. 641–646, Nov. 1993. [23] D. Mitra, “An asynchronous distributed algorithm for power control in cellular radio systems,” in Proc. 4th WINLAB Workshop on Third Generation Wireless Info. Netw., 1993. [24] S. G. Kiani and D. Gesbert, “Maximizing the capacity of large wireless networks: Optimal and distributed solutions,” in Proc. IEEE ISIT, pp. 2501–2505, July 2006. [25] S. G. Kiani, G. E. Øien, and D. Gesbert, “Maximizing multicell capacity using distributed power allocation and scheduling,” in Proc. WCNC, pp. 1690–1694, Mar. 2007. [26] F. Baccelli, M. Klein, M. Lebourges, and S. Zuyev, “Stochastic geometry and architecture of communication networks,” J. Telecommun. Syst., vol. 7, no. 1, pp. 209–227, June 1997. [27] A. J. Goldsmith and S.-G. Chua, “Variable-rate variable-power MQAM for fading channels,” IEEE Trans. Commun., vol. 45, no. 10, pp. 1218– 1230, Oct. 1997. [28] A. Leon-Garcia, Probability, Statistics, and Random Processes For Electrical Engineering, 3rd ed. Prentice Hall, 2008. [29] L. Narayanan, “Channel assignment and graph multicoloring,” Handbook of Wireless Networks and Mobile Computing, pp. 71–94, 2002. [30] Y.-J. Chang, Z. Tao, J. Zhang, and C.-C. J. Kuo, “A graph-based approach to multi-cell OFDMA downlink resource allocation,” in Proc. Globecom, Dec. 2008. [31] R. Y. Chang, Z. Tao, J. Zhang, and C.-C. J. Kuo, “A graph approach to dynamic fractional frequency reuse (FFR) in multi-cell OFDMA networks,” in Proc. ICC, Jun. 2009. [32] M. Zhang, Y. Liu, M. Tao, and X. Gao, “A graph approach for coordinated channel allocation in downlink multicell OFDMA networks,” in Proc. IET ICCTA, pp. 238–242, Oct. 2011. [33] B.-G. Kim, J.-A. Kwon, and J.-W. Lee, “Utility-based subchannel allocation for OFDMA femtocell networks,” in Proc. ICCCN, Aug. 2011. [34] E. Pateromichelakis, M. Shariat, A. Quddus, M. Dianati, and R. Tafazolli, “Dynamic clustering framework for multi-cell scheduling in dense small cell networks,” IEEE Commun. Lett., vol. 17, no. 9, pp. 1802– 1805, Sept. 2013. [35] D. Brélaz, “New methods to color the vertices of a graph,” J. Commun. of the ACM, vol. 22, no. 4, pp. 251–256, Apr. 1979. [36] O. Petelin and R. Adve, “Distributed resource allocation in femtocell networks,” in Proc. CWIT, pp. 102–107, Jun. 2013. [37] W. Rhee and J. M. Cioffi, “Increase in capacity of multiuser OFDM system using dynamic subchannel allocation,” in Proc. VTC, vol. 2, pp. 1085–1089, May. 2000. [38] Femto Forum, “Interference management in OFDMA femtocells,” white paper, Mar. 2010. [Online]. Available: www.smallcellforum.org [39] F. Hansen and F. I. Meno, “Mobile fading-Rayleigh and lognormal superimposed,” IEEE Trans. Veh. Technol., vol. 26, no. 4, pp. 332–335, Nov. 1977. [40] J. Liu, J. Wu, J. Chen, P. Wang, and J. Zhang, “Radio resource allocation in buildings with dense femtocell deployment,” in Proc. ICCCN, Aug. 2012. Sanam Sadr (S’07) was born in Tehran, Iran. She received the B.Sc degree in electrical engineering from the University of Tehran, Iran in 2003 and the M.Sc. degree from Ryerson University, Toronto, Canada in 2007. She is currently a Ph.D student at the University of Toronto, Canada, where her research has focused on load balancing and resource allocation in heterogeneous networks using tools from stochastic geometry, point process theory, optimization and graph algorithms. She held a summer internship at Alcatel-Lucent Bell Labs, Stuttgart, Germany. She is the recipient of the Alexander Graham Bell Canada Graduate Scholarship-Doctoral in 2010. Raviraj S. Adve (S’88, M’97, SM’06) was born in Bombay, India. He received his B. Tech. in Electrical Engineering from IIT, Bombay, in 1990 and his Ph.D. from Syracuse University in 1996. Between 1997 and August 2000, he worked for Research Associates for Defense Conversion Inc. on contract with the Air Force Research Laboratory at Rome, NY. He joined the faculty at the University of Toronto in August 2000 where he is currently a Professor. Dr. Adve’s research interests include analysis and design techniques for heterogeneous networks, energy harvesting networks and in signal processing techniques for radar and sonar systems. He received the 2009 Fred Nathanson Young Radar Engineer of the Year award.

© Copyright 2018 ExploreDoc