# Joint Cell Muting and User Scheduling in Multicell Networks with Temporal Fairness

Authors: Shahram Shahsavari; Nail Akar; Babak Hossein Khalaj
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

A semicentralized joint cell muting and user scheduling scheme for interference coordination in a multicell network is proposed under two different temporal fairness criteria. In the proposed scheme, at a decision instant, each base station (BS) in the multicell network employs a cell-level scheduler to nominate one user for each of its inner and outer sections and their available transmission rates to a network-level scheduler which then computes the potential overall transmission rate for each muting pattern. Subsequently, the network-level scheduler selects one pattern to unmute, out of all the available patterns. This decision is shared with all cell-level schedulers which then forward data to one of the two nominated users provided the pattern they reside in was chosen for transmission. Both user and pattern selection decisions are made on a temporal fair basis. Although some pattern sets are easily obtainable from static frequency reuse systems, we propose a general pattern set construction algorithm in this paper. As for the first fairness criterion, all cells are assigned to receive the same temporal share with the ratio between the temporal share of a cell center section and that of the cell edge section being set to a fixed desired value for all cells. The second fairness criterion is based onmax-min temporal fairness for which the temporal share of the network-wide worst case user is maximized. Extensive numerical results are provided to validate the effectiveness of the proposed schemes and to study the impact of choice of the pattern set.


---

## Body

## 1. Introduction

Frequency reuse of the scarce radio spectrum is key to building high capacity wireless cellular networks [1, 2]. However, when frequency reuse increases as in a frequency reuse 1 LTE system for which all cells use the same band of frequencies, controlling the adverse impact of Intercell Interference (ICI) is a challenging task, especially for cell edge users. Mitigation-based Intercell Interference Coordination (ICIC) consists of methods that are employed to reduce ICI through approaches such as interference cancellation and adaptive beamforming [3]. Avoidance-based ICIC techniques consist of frequency reuse planning algorithms through which resources are restricted or allocated to users in time and frequency domains whereas power levels are also selected with the aim of increasing SINR and network throughput [1, 4]. Avoidance-based ICIC schemes can be static and frequency reuse-based or dynamic and cell coordination-based [1]. In static ICIC, the cell-level resource allocation is fixed and does not change over time. The most well-known frequency reuse schemes include (i) conventional frequency reuse schemes, (ii) fractional frequency reuse (FFR), and (iii) soft frequency reuse (SFR). The focus of this paper will be on avoidance-based ICIC.A conventional frequency reuse system with reuse factorn>1 statically partitions the system bandwidth into n subbands each of which is allocated to individual cells with the reuse factor n (typical values being 3, 4, or 7) determining the distance between any two closest interfering cells using the same subband [5]. In conventional frequency reuse systems, cell edge users are penalized due to poor channel conditions and ICI. In order to alleviate this situation, FFR partitions the system bandwidth into two groups, one for cell center (also referred to as inner or interior) users and the other for cell edge (outer or exterior) users. The association of a given user to a cell center or cell edge section is made on the basis of its distance from the serving BS or SINR measurements [6]. The frequency reuse parameter n is set to unity for inner users whereas a strictly larger reuse factor (typically three) is used for outer users [3]. It is shown in [7] that the optimal frequency reuse factor for outer users is 3. Despite increased SINR for outer users as shown in [3], FFR has the apparent disadvantage that a subband of the outer group is left unused in cell center sections. On the other hand, SFR performs per-section power allocation by assigning a lower (higher) transmission power to inner (outer) users thereby making it possible to use the whole frequency band for the cell center section. SFR is shown to be superior to FFR in achieving higher spectral efficiency [8, 9]. Moreover, using power optimization can improve the performance of SFR as shown in [10]. For other variations of static frequency reuse-based ICIC schemes, we refer to the recent survey papers on ICIC specific to OFDM-based LTE networks [1, 2, 6].In realistic cellular wireless networks, the traffic demand is spatially inhomogeneous and changes over time. At one time, users may be concentrated in a given cluster of cells while at other times user concentration may move to another cluster. Moreover, user distributions in the cell center and the cell edge sections may also change in time in an unpredictable way throughout the cellular network. Therefore, static frequency reuse-based ICIC schemes fall short in coping with dynamic workloads in time and space and methods are proposed for dynamic workloads in [4, 11, 12]. Dynamic ICIC (D-ICIC), on the other hand, relies on cell coordination-based methods that dynamically react to changes in traffic demands and user distributions [13]. Despite the apparent theoretical advantage of D-ICIC network throughput, most proposed schemes in this category are very complex to implement. D-ICIC schemes are categorized into centralized, semicentralized, and decentralized, on the basis of how cell-level coordination is achieved and subsequently the complexity of implementation of the underlying scheme [14]. In centralized D-ICIC, the channel state information of each user is fed to a centralized entity which then makes scheduling decisions to maximize the throughput under fairness and power constraints [15]. However, such centralized scheduling is complex to implement due to the requirement of timely and large per-user feedback information as well as the complexity of the centralized scheduler [16]. Semicentralized schemes use centralized entities which only perform cell-level coordination while user-level allocation is performed by each BS [17, 18]. Reference [19] considers a semicentralized radio resource allocation scheme in OFDMA networks where radio resource allocation is performed at two layers. At the upper layer, a centralized algorithm coordinates ICI between BSs at the superframe level and each BS makes its scheduling decisions opportunistically based on instantaneous channel conditions of users. The computational complexity of semicentralized schemes is much less than centralized schemes with reduced feedback requirement; however, a sufficiently low-delay infrastructure is still needed. In decentralized D-ICIC, there is no centralized entity but a local signaling exchange is still needed among BSs [14]. The focus of this paper is the multicell scheduling problem with semicentralized D-ICIC which can be implemented provided a low-delay and efficient backhaul exists.In nondense frequency reuse-n networks with n>1, a single-cell scheduler decides which user to schedule without a need for coordination among cells. In this paper, we focus on opportunistic scheduling with fairness constraints. In opportunistic scheduling, the scheduler tries to select a user having the best channel condition at a given time [20]. Such a greedy opportunistic scheduler would maximize the throughput; however fairness among users would not be achieved. Practical opportunistic schedulers exploit the time-varying nature of the wireless channels for maximizing cell throughput under certain fairness constraints. In proportional fair (PF) scheduling, at a scheduling instant, the BS chooses to serve the user which has the largest ratio of available transmission rate to its exponentially smoothed average throughput [21, 22]. Different variations of the PF algorithm are possible depending on how the scheduler treats empty or short queues and how the average throughput is maintained [23]. In temporal fair (TF) (or air-time fair) single-cell opportunistic scheduling, the cell throughput is maximized under the constraint that users receive the same temporal share, that is, the same average air-time [24]. The work in [24] shows that the optimum single-cell TF scheduler chooses the user that has the largest sum of available transmission rate and another user-dependent term when an appropriate channel model is available, or alternatively this additional term can be obtained using an online learning algorithm. Under some simplifying assumptions involving channel characteristics of users, the PF and TF methods are shown to be equivalent [22, 25]. We refer the reader to [26] for a survey on single-cell scheduling in LTE networks. There have been few studies to generalize single-cell fairness to multicell or network-wide fairness in multicell networks. Reference [27] shows via simulations that network-wide opportunistic scheduling and power control are effective for fairness-oriented networks. The authors in [28] propose a semicentralized approach to achieve intercell and intracell temporal fairness in multicell networks but user-level network-wide fairness is not studied in that work.In this paper, we focus on network-wide throughput maximization with two separate fairness criteria involving temporal fairness. Although PF scheduling is more commonly used in LTE networks [29], we choose TF criteria in this paper since it is relatively easier to tell whether a resource allocation scheme satisfies TF constraints in different time scales by means of monitoring time-use of individual users, cells, and so on. This also makes it possible to propose semicentralized and computationally efficient algorithms for TF criteria which is in contrast with centralized approaches and higher computational complexities encountered in PF-based resource allocation in multicell networks [30]. In particular, we propose a semicentralized joint cell muting and user scheduling scheme for interference coordination in the downlink of a multicell network. In the proposed scheme, a set of cell muting patterns are a priori given each of which is associated with a set of cells that can transmit simultaneously with acceptable ICI in the multicell network. The scheduler operates in two levels (cell-level and network-level) as in [19] as follows. Each BS employs a cell-level scheduler (CLS) to nominate one user for each of its inner and outer sections at a scheduling instant and their available transmission rates to the network-level scheduler (NLS) on the basis of TF constraints. The NLS then computes the potential overall transmission rate for each muting pattern. Subsequently, the NLS decides which pattern to activate. This decision is then shared with all BSs. The BSs then forward data to one of the two nominated users (by the CLS) provided the pattern they reside in was chosen for transmission.The CLS and NLS can be tuned to conform to one of two different temporal fairness criteria studied in this paper. As for the first fairness criterion, all cells receive the same temporal share with the ratio between the temporal share of a cell center section and that of the cell edge section being set to a fixed desired value for all cells. Within a section, all users receive the same temporal share. Although the first fairness criterion achieves fairness among cells and also users within the same section, this criterion does not seek network-wide user fairness. As a remedy, we propose using network-wide max-min temporal fairness as the second fairness criterion. A broad range of centralized and/or distributed algorithms are available in the literature to implement max-min fairness in the context of sharing resources including link bandwidth [31], network bandwidth [32], CPU [33], and cloud computing [34]. Algorithms seeking max-min fairness in resource allocation problems involving wireless networks have been proposed in [35–37]. The high popularity of the notion of max-min fairness in general computing and communication systems has led us to study in this paper the network-wide max-min temporal fairness for which the temporal share of the network-wide worst case user in the multicell network is to be maximized. To the best of our knowledge, network-wide max-min temporal fairness in this context has not been studied before. Both fairness criteria are shown to be handled within the framework we propose in this paper. As a further contribution, we propose a novel general pattern set construction algorithm with reasonable computational complexity using fractional frequency reuse principles with M cell muting patterns. The complexity of the proposed NLS scheduler turns out to be the same as that of a single-cell TF scheduler with M users and is therefore quite efficient for relatively small cardinality parameter M. The impact of choice of the cell muting pattern set and its cardinality M is also studied through numerical examples for various cellular topologies. The proposed approach leads to reduced computational complexity of the NLS and reduced information exchange requirements between CLSs and the NLS in comparison with centralized schemes that have higher implementation complexities [15].Although most of the literature on the interference coordination techniques is based on OFDM-based LTE networks, we consider in this paper a time-slotted single-carrier air interface for the sake of simplicity. Most of the well-known wireless scheduling algorithms were originally designed for single-carrier systems [38] such as proportional fair scheduler [21, 22], temporal fair scheduler [24], and max-weight scheduler [39]. Reference [38] presents existing work on how single-carrier scheduling algorithms can be adapted to multicarrier environments including OFDM-based LTE networks. Multicarrier systems have their own requirements; for example, a user may have to use the same adaptive modulation and coding scheme on different carriers [29] or a user should be assigned consecutive carriers rather than an arbitrary subset of carriers [40]. These further requirements are known to give rise to complications in multicarrier adaptation [38]. The adaptation of the proposed single-carrier multicell scheduler to multicarrier networks such as LTE-A is deliberately left for future research.The paper is organized as follows. We present the proposed multicell architecture along with the descriptions of cell muting patterns and pattern set construction algorithms in Section2. The two forms of fairness criteria that we employ as well as the two-level scheduler proposed to satisfy both criteria are presented in Section 3. We validate the effectiveness of the proposed approach in Section 4. Finally, we draw a conclusion.


## 2. Proposed Multicellular Architecture

### 2.1. Cells and Users

We consider the downlink of a time-slotted single-carrier frequency reuse 1 unsectored cellular network (CN) with bandwidthBW where the time slots are indexed by 1≤τ<∞. We assume that each cell is divided into inner and outer sections; see Figure 1 for a cell with cell radius RC and inner section radius RI. Let Ci,  i=1,2,…,K, denote cell i in the CN where K is the total number of cells. Let BSi denote the base station located in Ci. Also let Ii and Oi denote the inner and outer sections of Ci, respectively. We let N denote the total number of users in the network and let Ni, NiI, and NiO denote the number of users associated with cell Ci and with sections Ii and Oi, respectively. The cell or section association of a given user is assumed to be a priori known throughout this paper. Obviously, Ni=NiI+NiO and N=∑iNi. Let Ui,jI,  j=1,2,…,NiI and Ui,jO,  j=1,2,…,NiO denote the user j associated with Ii and Oi, respectively. We assume all users are persistent; that is, they always have data to receive. For a given time slot τ, the cell Ci is active (unmuted) if its BSi is transmitting. Otherwise, Ci is said to be muted. When Ci is active and BSi is transmitting to a user in Ii, then Ii is called active; otherwise Oi is active.Figure 1
Inner and outer sections of a cell.


### 2.2. Cell Muting Patterns

A cell muting or transmission pattern (or pattern in short) is defined as a subset of the set of all sections in the CN satisfying the following two properties:(i)
Patterns are noise-limited as opposed to being interference-limited; that is, the elements of a pattern can be activated simultaneously without the associated base stations creating destructive interference on users associated with other active cells. Obviously, when a pattern is selected by the scheduler, all cells which do not have any inner or outer sections in that chosen pattern would be muted.(ii)
Patterns are maximal; that is, a pattern cannot be included in another pattern with larger cardinality.Obviously, a pattern is governed by the geometry of the CN, the power levels used by a BS for transmitting to inner and outer section users, and the definition of destructive interference.In this paper, patterns are constructed on the basis of an underlying fractional frequency reuse-n- (FFR-n-) type CN; see [41, 42]. In our proposed architecture, the entire bandwidth BW of the frequency reuse 1 system is dynamically shared by the available patterns in time and not in frequency, by means of dynamically muting all but one pattern at a given time slot. Deployment of a general FFR-n system with n=x2+xy+y2 for some nonnegative integers x and y can provide M=n+1 patterns for x,y≥1 [5]. We call the set of n+1 patterns an Essential Pattern Set (EPS-n) for the associated FFR-n system. Among the patterns in ESP-n, except one transmission pattern which consists of all inner sections in the network, there are n patterns each of which consists of a number of outer sections in the network. We call all such n patterns a Mother Pattern Set (MPS-n). As an example, Figure 2 illustrates ESP-3 which consists of four patterns in a 9-cell CN. Here, MPS-3 denotes the set {P1,P2,P3}.Figure 2
EPS-3 for the 9-cell CN:P1={O3,O4,O8}, P2=O1,O5,O9, P3={O2,O6,O7}, and P4={I1,I2,…,I9}.On the other hand, a general pattern set (GPS) is an arbitrary collection of patterns in which each section in the CN is an element of at least one pattern. It is clear that EPS-n is a GPS. The Universal Pattern Set (UPS) is the set of all possible patterns. Obviously, GPSs are subsets of the UPS. A pattern is said to be active at a given slot if all the sections included in the pattern are active. A section may be included in multiple patterns for a GPS. However, for EPS-n, the patterns are mutually exclusive. Figure 3 illustrates a sample GPS for the 9-cell CN; note that I9 is an element of the three patterns P1, P3, and P4 for this sample GPS.Figure 3
A sample GPS with 6 patterns for the 9-cell CN:P1={I1,I9,O5}, P2={I4,I5,I6,O1,O9}, P3={I8,I9,O3,O4}, P4={I7,I9,O2,O6}, P5={I1,I2,O6,O7}, and P6={I1,I3,O4,O8}.


### 2.3. General Pattern Set Construction Mechanism

In this section, we propose an algorithm to construct a GPS which can effectively be used in multicell networks. For this purpose, let the operator↔n represent the interference relationship in an FFR-n system with X↔nY implying the activation of sections X and Y causing destructive interference of X on Y and vice versa. In the lack of destructive interference between the two associated cells, we say X↮nY. We assume that the interference is not destructive if its power is much lower (e.g., 5 times) than the noise power. The interference relationship which holds for any two given sections X and Y depends on the following two parameters:(i)
The physical distance between the BSs with which sectionsX and Y are associated(ii)
The transmission power levels assigned to inner and outer section users.In order to quantify interference between two sections, we make use of the mother patterns in an FFR-n system. Let Dn denote the distance between the centers of the nearest active cells in the patterns of MPS-n. According to [5], we have Dn=RC3n. Let us denote by di,j the distance between the centers of Ci and Cj. Consequently, we have the following interference identities in an FFR-n system:(1)Oi⟷nOjiffdi,j<Dn,(2)Ii⟷nOjiffdi,j<Dn,(3)Ii↮nIj∀i,j.Moreover, we consider different fixed downlink power levels for inner and outer section users, designed in a way that (1)–(3) hold. We note that, ∀i:Ii↔nOi based on (2), meaning that at most one section per cell can be active at a time slot. The following theorem (given without a proof since it is relatively straightforward) provides the necessary and sufficient conditions for a set of sections to constitute a pattern in an associated FFR-n CN with K cells.Theorem 1.
A set of sectionsP≠⌀ amounts to a pattern if and only if(a)
∀i,j:Oi↔nOj,Oi∈P⇒Oj∉P,(b)
∀i,j:Oi↔nIj,Oi∈P⇒Ij∉P,(c)
∀i,j:Ii↔nOj,Ii∈P⇒Oj∉P,(d)
∀i:Ii∉P⇒∃k:Ok↔nIi,Ok∈P,(e)
∀i:Oi∉P⇒({∃k:Ok↔nOi,Ok∈P} or {∃k:Ik↔nOi,Ik∈P}).In Theorem1, the first three conditions are required for a pattern to be noise-limited whereas the remaining two conditions are required for a pattern to be maximal. One straightforward way to construct all transmission patterns (UPS) is an Exhaustive Search (ES) among all possible sets of sections of cardinality 3K since each cell’s inner section or outer section is included in a given set or not, leading to three possibilities for each cell and there are K such cells. In the ES method, all of these sets are generated first; then, using Theorem 1, one can check whether each set of sections is a pattern or not. Consequently, in order to check the validity of all the generated sets of sections, the ES method requires O(3K) steps.In this paper, we propose a novel algorithm with reduced computational complexity (compared to ES) to construct a GPS using MPS-n. For this purpose, we let {Pm∗}m=1n be the patterns of MPS-n. Also, let Skm,k=1,2,…,2Qm denote the subset k of the set of sections included in Pm∗, where Qm=Pm∗ denotes the number of sections included in Pm∗. For convenience, let S1m=∅ and SQmm=Pm∗ for each m. Algorithm 1 proposes a method to generate a GPS using MPS-n for an arbitrary value of n. Figure 4 illustrates the working principle of Algorithm 1 for n=3. In Figure 4(a), one of the mother patterns in the FFR-3 system is depicted. Figure 4(b) depicts one of the subsets of that mother pattern. Due to interference, neither the inner nor the outer sections of the shadowed cells can be a member of the new pattern V in Figure 4(c) based on (1) and (2). In Figure 4(d), inner sections of the remaining cells are added to the pattern V to attain maximality based on (3). It is clear that EPS-n is a subset of the pattern set constructed by this algorithm. This is because (i) the set of all inner sections is obtained as a pattern when we start from the subset S1m for any m and (ii) Pm∗ is obtained by Algorithm 1 when SQmm is used in the inner loop for every m. According to the definition, the collection of all of these patterns is EPS-n. Next, we present Theorem 2 along with its proof showing that the pattern set produced by Algorithm 1 is indeed a GPS.Algorithm 1:Constructing a GPS using MPS-n.
Input: MPS-n Output: GPS ( 1 ) GPS ←⌀ ( 2 ) for m = 1 to n step (1)do ( 3 )  for k = 1 to 2Pm∗do 4  V ← S k m ( 5 ) Add to V all the inner sections which do not interfere with the outer sections in V. ( 6 )  if V ∉ GPS then ( 7 ) Add V to the GPS. ( 8 )  end if ( 9 )  end for ( 10 ) end forFigure 4
Steps to construct a transmission pattern from a mother pattern in an FFR-3 system.
(a) (b) (c) (d)Theorem 2.
The pattern set produced by Algorithm1 is a GPS.Proof.
We need to show that the elements of the pattern set produced by Algorithm1 are noise-limited and maximal and moreover each section in the CN is an element of at least one pattern in the pattern set. It is clear that all the patterns are noise-limited due to the way a new pattern, V, is generated by Algorithm 1. This is because (i) Skm is noise-limited since ∀k,m:Skm⊂Pm∗ and Pm∗ is noise-limited for every m and (ii) line (5) of the algorithm ensures that any added inner section to Skm does not make destructive interference. On the other hand, assume at least one of the generated patterns is not maximal meaning that we can at least add one other section (say section X) to it, while it remains noise-limited. Clearly, section X cannot be an inner section, because Algorithm 1 adds all possible inner sections (line (5) of Algorithm 1). On the other hand, X cannot be an outer section because of assuming that X is the outer section of cell Y with the inner section Z. If adding X would not cause destructive interference, then adding Z also would not cause destructive interference. However, this contradicts with the way the algorithm works (line (5) of Algorithm 1). To show that each section is an element of at least one pattern, recall that patterns which belong to MPS-n are among the generated patterns and each of the outer sections is an element of an individual MPS. Moreover, the set of all inner sections is obtained as a pattern when we start from the subset S1m for any m. This concludes the proof.We now elaborate on the computational aspects of the GPS construction algorithm that we have proposed. The outer loop of Algorithm1 requires n iterations and the inner loop requires approximately 2⌈K/n⌉ iterations. To see this, there are n mother patterns, namely, {Pm∗}m=1n, and each mother pattern Pm∗ consists of approximately Pm∗≈⌈K/n⌉ outer sections, so each inner loop will be executed approximately 2⌈K/n⌉ times. Therefore, the total number of required iterations is O(2⌈K/n⌉n) which is substantially less than that of the ES method. Moreover, the per-iteration computational load of Algorithm 1 is less than that of ES. However, recall that this GPS is only a subset of the UPS and there may be patterns in the UPS that cannot be constructed by the proposed algorithm. To evaluate the pattern construction capability of Algorithm 1, we consider two different CNs illustrated in Figure 5 depicting (a) 9-cell and (b) 6-cell scenarios, which will be used in numerical examples. We use the FFR-3 interference relationships and subsequently MPS-3 as input to the proposed algorithm. The ES and Algorithm 1 are run for each of the two scenarios and the patterns constructed by each method are presented in Tables 1 and 2, respectively, for the 9-cell and 6-cell scenarios. We observe that ES generates the UPS with cardinality 42 and cardinality 13, whereas Algorithm 1 constructs 22 and 10 patterns, respectively, for the 9-cell and 6-cell scenarios. Although the proposed algorithm cannot construct the UPS, we will later show through numerical examples that the network performance obtained by the GPS produced by the proposed algorithm is only slightly inferior to that attained by that of the UPS.Table 1
The UPS with 42 patterns for the 9-cell network. The patterns labeled with∗ are constructed by Algorithm 1.
m i : I i ∈ P m i : O i ∈ P m 1 ∗ 1 , … , 9 – – 2 ∗ 1 , … , 6 9 3 ∗ 1,2 , 3,4 8 4 ∗ 1,2 , 3,6 7 5 ∗ 1,2 , 4,7 , 9 6 6 1,2 , 4 6,9 7 ∗ 1,2 6,7 8 ∗ 1,3 , 6,8 , 9 4 9 1,3 , 6 4,9 10 ∗ 1,3 4,8 11 ∗ 1,9 5 12 ∗ 1 5,9 13 1,9 4,6 14 1 4,6 , 9 15 ∗ 4,7 , 8,9 3 16 4 3,9 17 ∗ 4 3,8 18 – – 3,7 19 ∗ 8,9 3,4 20 – – 3,4 , 9 21 ∗ – – 3,4 , 8 22 ∗ 6,7 , 8,9 2 23 6 2,9 24 ∗ 6 2,7 25 – – 2,8 26 ∗ 7,9 2,6 27 – – 2,6 , 9 28 ∗ – – 2,6 , 7 29 ∗ 4 , … , 9 1 30 ∗ 4,5 , 6 1,9 31 4 1,8 32 4,7 , 9 1,6 33 4 1,6 , 9 34 6 1,7 35 – – 1,6 , 7 36 ∗ 9 1,5 37 ∗ – – 1,5 , 9 38 6,8 , 9 1,4 39 6 1,4 , 9 40 – – 1,4 , 8 41 9 1,4 , 6 42 – – 1,4 , 6,9Table 2
The UPS with 13 patterns for the 6-cell network. The patterns labeled with∗ are constructed by Algorithm 1.
m i : I i ∈ P m i : O i ∈ P m 1∗ – – 1,6 2∗ – – 2,4 3∗ – – 3,5 4∗ 1 , … , 6 – – 5∗ 2,3 , 6 4 6∗ 4 2 7∗ 3 5 8∗ 1,4 , 5 3 9∗ 3,6 1 10 – – 3,4 11 – – 4,6 12∗ 1,4 6 13 – – 1,3Figure 5
Two different scenarios: (a) 9-cell CN; (b) 6-cell CN.
(a) (b)


## 2.1. Cells and Users

We consider the downlink of a time-slotted single-carrier frequency reuse 1 unsectored cellular network (CN) with bandwidthBW where the time slots are indexed by 1≤τ<∞. We assume that each cell is divided into inner and outer sections; see Figure 1 for a cell with cell radius RC and inner section radius RI. Let Ci,  i=1,2,…,K, denote cell i in the CN where K is the total number of cells. Let BSi denote the base station located in Ci. Also let Ii and Oi denote the inner and outer sections of Ci, respectively. We let N denote the total number of users in the network and let Ni, NiI, and NiO denote the number of users associated with cell Ci and with sections Ii and Oi, respectively. The cell or section association of a given user is assumed to be a priori known throughout this paper. Obviously, Ni=NiI+NiO and N=∑iNi. Let Ui,jI,  j=1,2,…,NiI and Ui,jO,  j=1,2,…,NiO denote the user j associated with Ii and Oi, respectively. We assume all users are persistent; that is, they always have data to receive. For a given time slot τ, the cell Ci is active (unmuted) if its BSi is transmitting. Otherwise, Ci is said to be muted. When Ci is active and BSi is transmitting to a user in Ii, then Ii is called active; otherwise Oi is active.Figure 1
Inner and outer sections of a cell.


## 2.2. Cell Muting Patterns

A cell muting or transmission pattern (or pattern in short) is defined as a subset of the set of all sections in the CN satisfying the following two properties:(i)
Patterns are noise-limited as opposed to being interference-limited; that is, the elements of a pattern can be activated simultaneously without the associated base stations creating destructive interference on users associated with other active cells. Obviously, when a pattern is selected by the scheduler, all cells which do not have any inner or outer sections in that chosen pattern would be muted.(ii)
Patterns are maximal; that is, a pattern cannot be included in another pattern with larger cardinality.Obviously, a pattern is governed by the geometry of the CN, the power levels used by a BS for transmitting to inner and outer section users, and the definition of destructive interference.In this paper, patterns are constructed on the basis of an underlying fractional frequency reuse-n- (FFR-n-) type CN; see [41, 42]. In our proposed architecture, the entire bandwidth BW of the frequency reuse 1 system is dynamically shared by the available patterns in time and not in frequency, by means of dynamically muting all but one pattern at a given time slot. Deployment of a general FFR-n system with n=x2+xy+y2 for some nonnegative integers x and y can provide M=n+1 patterns for x,y≥1 [5]. We call the set of n+1 patterns an Essential Pattern Set (EPS-n) for the associated FFR-n system. Among the patterns in ESP-n, except one transmission pattern which consists of all inner sections in the network, there are n patterns each of which consists of a number of outer sections in the network. We call all such n patterns a Mother Pattern Set (MPS-n). As an example, Figure 2 illustrates ESP-3 which consists of four patterns in a 9-cell CN. Here, MPS-3 denotes the set {P1,P2,P3}.Figure 2
EPS-3 for the 9-cell CN:P1={O3,O4,O8}, P2=O1,O5,O9, P3={O2,O6,O7}, and P4={I1,I2,…,I9}.On the other hand, a general pattern set (GPS) is an arbitrary collection of patterns in which each section in the CN is an element of at least one pattern. It is clear that EPS-n is a GPS. The Universal Pattern Set (UPS) is the set of all possible patterns. Obviously, GPSs are subsets of the UPS. A pattern is said to be active at a given slot if all the sections included in the pattern are active. A section may be included in multiple patterns for a GPS. However, for EPS-n, the patterns are mutually exclusive. Figure 3 illustrates a sample GPS for the 9-cell CN; note that I9 is an element of the three patterns P1, P3, and P4 for this sample GPS.Figure 3
A sample GPS with 6 patterns for the 9-cell CN:P1={I1,I9,O5}, P2={I4,I5,I6,O1,O9}, P3={I8,I9,O3,O4}, P4={I7,I9,O2,O6}, P5={I1,I2,O6,O7}, and P6={I1,I3,O4,O8}.


## 2.3. General Pattern Set Construction Mechanism

In this section, we propose an algorithm to construct a GPS which can effectively be used in multicell networks. For this purpose, let the operator↔n represent the interference relationship in an FFR-n system with X↔nY implying the activation of sections X and Y causing destructive interference of X on Y and vice versa. In the lack of destructive interference between the two associated cells, we say X↮nY. We assume that the interference is not destructive if its power is much lower (e.g., 5 times) than the noise power. The interference relationship which holds for any two given sections X and Y depends on the following two parameters:(i)
The physical distance between the BSs with which sectionsX and Y are associated(ii)
The transmission power levels assigned to inner and outer section users.In order to quantify interference between two sections, we make use of the mother patterns in an FFR-n system. Let Dn denote the distance between the centers of the nearest active cells in the patterns of MPS-n. According to [5], we have Dn=RC3n. Let us denote by di,j the distance between the centers of Ci and Cj. Consequently, we have the following interference identities in an FFR-n system:(1)Oi⟷nOjiffdi,j<Dn,(2)Ii⟷nOjiffdi,j<Dn,(3)Ii↮nIj∀i,j.Moreover, we consider different fixed downlink power levels for inner and outer section users, designed in a way that (1)–(3) hold. We note that, ∀i:Ii↔nOi based on (2), meaning that at most one section per cell can be active at a time slot. The following theorem (given without a proof since it is relatively straightforward) provides the necessary and sufficient conditions for a set of sections to constitute a pattern in an associated FFR-n CN with K cells.Theorem 1.
A set of sectionsP≠⌀ amounts to a pattern if and only if(a)
∀i,j:Oi↔nOj,Oi∈P⇒Oj∉P,(b)
∀i,j:Oi↔nIj,Oi∈P⇒Ij∉P,(c)
∀i,j:Ii↔nOj,Ii∈P⇒Oj∉P,(d)
∀i:Ii∉P⇒∃k:Ok↔nIi,Ok∈P,(e)
∀i:Oi∉P⇒({∃k:Ok↔nOi,Ok∈P} or {∃k:Ik↔nOi,Ik∈P}).In Theorem1, the first three conditions are required for a pattern to be noise-limited whereas the remaining two conditions are required for a pattern to be maximal. One straightforward way to construct all transmission patterns (UPS) is an Exhaustive Search (ES) among all possible sets of sections of cardinality 3K since each cell’s inner section or outer section is included in a given set or not, leading to three possibilities for each cell and there are K such cells. In the ES method, all of these sets are generated first; then, using Theorem 1, one can check whether each set of sections is a pattern or not. Consequently, in order to check the validity of all the generated sets of sections, the ES method requires O(3K) steps.In this paper, we propose a novel algorithm with reduced computational complexity (compared to ES) to construct a GPS using MPS-n. For this purpose, we let {Pm∗}m=1n be the patterns of MPS-n. Also, let Skm,k=1,2,…,2Qm denote the subset k of the set of sections included in Pm∗, where Qm=Pm∗ denotes the number of sections included in Pm∗. For convenience, let S1m=∅ and SQmm=Pm∗ for each m. Algorithm 1 proposes a method to generate a GPS using MPS-n for an arbitrary value of n. Figure 4 illustrates the working principle of Algorithm 1 for n=3. In Figure 4(a), one of the mother patterns in the FFR-3 system is depicted. Figure 4(b) depicts one of the subsets of that mother pattern. Due to interference, neither the inner nor the outer sections of the shadowed cells can be a member of the new pattern V in Figure 4(c) based on (1) and (2). In Figure 4(d), inner sections of the remaining cells are added to the pattern V to attain maximality based on (3). It is clear that EPS-n is a subset of the pattern set constructed by this algorithm. This is because (i) the set of all inner sections is obtained as a pattern when we start from the subset S1m for any m and (ii) Pm∗ is obtained by Algorithm 1 when SQmm is used in the inner loop for every m. According to the definition, the collection of all of these patterns is EPS-n. Next, we present Theorem 2 along with its proof showing that the pattern set produced by Algorithm 1 is indeed a GPS.Algorithm 1:Constructing a GPS using MPS-n.
Input: MPS-n Output: GPS ( 1 ) GPS ←⌀ ( 2 ) for m = 1 to n step (1)do ( 3 )  for k = 1 to 2Pm∗do 4  V ← S k m ( 5 ) Add to V all the inner sections which do not interfere with the outer sections in V. ( 6 )  if V ∉ GPS then ( 7 ) Add V to the GPS. ( 8 )  end if ( 9 )  end for ( 10 ) end forFigure 4
Steps to construct a transmission pattern from a mother pattern in an FFR-3 system.
(a) (b) (c) (d)Theorem 2.
The pattern set produced by Algorithm1 is a GPS.Proof.
We need to show that the elements of the pattern set produced by Algorithm1 are noise-limited and maximal and moreover each section in the CN is an element of at least one pattern in the pattern set. It is clear that all the patterns are noise-limited due to the way a new pattern, V, is generated by Algorithm 1. This is because (i) Skm is noise-limited since ∀k,m:Skm⊂Pm∗ and Pm∗ is noise-limited for every m and (ii) line (5) of the algorithm ensures that any added inner section to Skm does not make destructive interference. On the other hand, assume at least one of the generated patterns is not maximal meaning that we can at least add one other section (say section X) to it, while it remains noise-limited. Clearly, section X cannot be an inner section, because Algorithm 1 adds all possible inner sections (line (5) of Algorithm 1). On the other hand, X cannot be an outer section because of assuming that X is the outer section of cell Y with the inner section Z. If adding X would not cause destructive interference, then adding Z also would not cause destructive interference. However, this contradicts with the way the algorithm works (line (5) of Algorithm 1). To show that each section is an element of at least one pattern, recall that patterns which belong to MPS-n are among the generated patterns and each of the outer sections is an element of an individual MPS. Moreover, the set of all inner sections is obtained as a pattern when we start from the subset S1m for any m. This concludes the proof.We now elaborate on the computational aspects of the GPS construction algorithm that we have proposed. The outer loop of Algorithm1 requires n iterations and the inner loop requires approximately 2⌈K/n⌉ iterations. To see this, there are n mother patterns, namely, {Pm∗}m=1n, and each mother pattern Pm∗ consists of approximately Pm∗≈⌈K/n⌉ outer sections, so each inner loop will be executed approximately 2⌈K/n⌉ times. Therefore, the total number of required iterations is O(2⌈K/n⌉n) which is substantially less than that of the ES method. Moreover, the per-iteration computational load of Algorithm 1 is less than that of ES. However, recall that this GPS is only a subset of the UPS and there may be patterns in the UPS that cannot be constructed by the proposed algorithm. To evaluate the pattern construction capability of Algorithm 1, we consider two different CNs illustrated in Figure 5 depicting (a) 9-cell and (b) 6-cell scenarios, which will be used in numerical examples. We use the FFR-3 interference relationships and subsequently MPS-3 as input to the proposed algorithm. The ES and Algorithm 1 are run for each of the two scenarios and the patterns constructed by each method are presented in Tables 1 and 2, respectively, for the 9-cell and 6-cell scenarios. We observe that ES generates the UPS with cardinality 42 and cardinality 13, whereas Algorithm 1 constructs 22 and 10 patterns, respectively, for the 9-cell and 6-cell scenarios. Although the proposed algorithm cannot construct the UPS, we will later show through numerical examples that the network performance obtained by the GPS produced by the proposed algorithm is only slightly inferior to that attained by that of the UPS.Table 1
The UPS with 42 patterns for the 9-cell network. The patterns labeled with∗ are constructed by Algorithm 1.
m i : I i ∈ P m i : O i ∈ P m 1 ∗ 1 , … , 9 – – 2 ∗ 1 , … , 6 9 3 ∗ 1,2 , 3,4 8 4 ∗ 1,2 , 3,6 7 5 ∗ 1,2 , 4,7 , 9 6 6 1,2 , 4 6,9 7 ∗ 1,2 6,7 8 ∗ 1,3 , 6,8 , 9 4 9 1,3 , 6 4,9 10 ∗ 1,3 4,8 11 ∗ 1,9 5 12 ∗ 1 5,9 13 1,9 4,6 14 1 4,6 , 9 15 ∗ 4,7 , 8,9 3 16 4 3,9 17 ∗ 4 3,8 18 – – 3,7 19 ∗ 8,9 3,4 20 – – 3,4 , 9 21 ∗ – – 3,4 , 8 22 ∗ 6,7 , 8,9 2 23 6 2,9 24 ∗ 6 2,7 25 – – 2,8 26 ∗ 7,9 2,6 27 – – 2,6 , 9 28 ∗ – – 2,6 , 7 29 ∗ 4 , … , 9 1 30 ∗ 4,5 , 6 1,9 31 4 1,8 32 4,7 , 9 1,6 33 4 1,6 , 9 34 6 1,7 35 – – 1,6 , 7 36 ∗ 9 1,5 37 ∗ – – 1,5 , 9 38 6,8 , 9 1,4 39 6 1,4 , 9 40 – – 1,4 , 8 41 9 1,4 , 6 42 – – 1,4 , 6,9Table 2
The UPS with 13 patterns for the 6-cell network. The patterns labeled with∗ are constructed by Algorithm 1.
m i : I i ∈ P m i : O i ∈ P m 1∗ – – 1,6 2∗ – – 2,4 3∗ – – 3,5 4∗ 1 , … , 6 – – 5∗ 2,3 , 6 4 6∗ 4 2 7∗ 3 5 8∗ 1,4 , 5 3 9∗ 3,6 1 10 – – 3,4 11 – – 4,6 12∗ 1,4 6 13 – – 1,3Figure 5
Two different scenarios: (a) 9-cell CN; (b) 6-cell CN.
(a) (b)


## 3. The Proposed Multicell Scheduler

In this section, we assume that the pattern set{Pm}m=1M is a priori given whether being EPS-n, or the UPS if available, or the GPS produced by the algorithm presented in the previous section, or any other GPS. At a decision epoch τ, the NLS decides to activate one of the available patterns, say Pm∗(τ), from the M available patterns in the GPS, and mutes all other patterns. How this decision is to be made will be discussed in the sequel.


### 3.1. Per-Pattern and Per-User Temporal Shares

LetAm, ai,jI, and ai,jO denote the long-term temporal (or equivalently air-time) share of pattern Pm, user Ui,jI, and user Ui,jO, respectively:(4)Am=limt→∞⁡1t∑τ=1t1m∗τ=mai,jI=limt→∞⁡1t∑τ=1t1userUi,jIis  scheduled  at  slotτai,jO=limt→∞⁡1t∑τ=1t1userUi,jOis  scheduled  at  slotτ,where 1{·} denotes the conventional indicator function which is either one or zero depending on whether the argument is true or not, respectively. Similarly, let AiI, AiO, and AiC denote the long-term air-time share of section Ii, section Oi, and cell Ci, respectively. Mathematically, (5)AiI=limt→∞⁡1t∑τ=1t1Ii∈Pm∗τAiO=limt→∞⁡1t∑τ=1t1Oi∈Pm∗τAiC=AiI+AiO.We introduce positive (target) scheduling weights {wm}m=1M for patterns {Pm}m=1M satisfying ∑mwm=1. The target scheduling weight wm is the long-term target average probability that pattern Pm is selected by the scheduler. Note that use of scheduling weight {wm}m=1M by the scheduler should give rise to Am=wm,∀m. In this case, the system is said to be interpattern weighted temporal fair with respect to the weights {wm}m=1M. In the specific case of wm=1/M, the system is called interpattern temporal fair. Similarly, we introduce target positive scheduling weights {wi,jI}j=1NiI and {wi,jO}j=1NiO for user Ui,jI and user Ui,jO, respectively, satisfying ∑jwi,jI=1 and ∑jwi,jO=1 for each of the cells Ci. We remark that the use of user scheduling weights {wi,jI}j=1NiI and {wi,jO}j=1NiO leads to ai,jI=AiIwi,jI,∀j, for any section Ii and ai,jO=AiOwi,jO,∀j, for any section Oi. In this case we have intrasection weighted temporal fairness in sections Ii and Oi, respectively, with respect to the weights {wi,jI}j=1NiI and {wi,jO}j=1NiO. In this paper, we only consider ordinary intrasection temporal fairness which leads to the following two identities:(6)wi,jI=1NiI,1≤j≤NiI,wi,jO=1NiO,1≤j≤NiO.In case when NiI or NiO is zero, no per-user scheduling weights are assigned for that particular section. Moreover, no downlink transmission would take place due to the lack of a user in that section even if the included pattern is selected for transmission. Therefore, the only unknowns to the scheduler in the numerical examples of the current study are the per-pattern weights. Once the weights are decided, then the following identities immediately hold:(7)AiI=∑m=1Mwmem,i,ai,jI=AiINiI,(8)AiO=∑m=1Mwmfm,i,ai,jO=AiONiO,where em,i≜1Ii∈Pm and fm,i≜1Oi∈Pm. In the next subsection, we focus on methods of obtaining these weights leading to two different forms of temporal fairness being sought in the CN.


### 3.2. Temporal Fairness Criteria

In this paper, we consider two different TF criteria for the multicell CN for which the per-pattern weights can easily be obtained at reasonable computational complexity. The first TF criterion is the so-called Intersection Proportional Temporal Fairness (IS-PTF) in which the CN is intercell temporal fair one but an inner section of each cell receives a temporal share proportional to the temporal share of the outer section of the same cell using the same network-wide proportionality constant. Mathematically,AiC=AjC,1≤i,j≤K, and AiI=dAiO,1≤i≤K, hold for a fairness proportionality constant d to be chosen by the network operator. As a matter of fact, employing d>1 causes the inner sections to be scheduled more often than the outer sections and vice versa for the case 0<d<1. It is clear that IS-PTF cannot be achieved for some general pattern sets such as GPS of Figure 3. However, as stated in the theorem below, IS-PTF is achievable when EPS-n is used as the pattern set.Theorem 3.
With EPS-n used as the pattern set, IS-PTF is achieved by the following choice of weights:(9)wi=1d+n1≤i≤n,wn+1=dd+n,where M=n+1 and the pattern PM is the set of all inner sections of the CN; that is, PM=⋃i=1KIi.Proof.
We note that EPS-n= MPS-n ∪  PM and Am,1≤m≤n, and AM are the temporal shares of  mth individual MPS-n and PM, respectively. Furthermore, the scheduler can guarantee that Am=wm,1≤m≤n and AM=wM. Patterns in MPS-n are mutually exclusive; thus for each section Oi there is only one index m,1≤m≤n, such that AiO=wm. Furthermore, ∀i:AiI=wM. We thus conclude that, for all i, there exists m,1≤m≤n, such that AiC=wm+wM. Recall that intercell fairness requires ∀m1,m2,1≤m1,m2≤n:wm1+wM=wm2+wM which in turn implies that ∀m1,m2,1≤m1,m2≤n:wm1=wm2≜w. Moreover, using intersection fairness we have ∀m,1≤m≤n:wM=dwm=dw. Finally, the pattern weights sum to unity; that is, ∑m=1nwm+wM=1. Therefore, nw+dw=1 which implies that ∀m,1≤m≤n:wm=w=1/d+n and wM=wn+1=d/d+n.For the special case of EPS-3, there areM=4 patterns depicted in Figure 2 where the corresponding weights are w1=w2=w3=1/d+3 and w4=d/(d+3).Although IS-PTF criterion guarantees equal user temporal shares within each section, it does not seek network-wide fairness among all the network users. That is why IS-PTF does not take into account the number of users located in each section for obtaining pattern weights{wm}m=1M. As a result, using IS-PTF along with unbalanced user distribution may lead to unequal temporal share for the users located in different sections of the network. The second TF criterion we study in this paper is max-min temporal fairness (MMTF) for which the pattern weights {wm}m=1M are selected so that the minimum user temporal share in the network is maximized. Thus, MMTF is a network-wide fairness criterion. The MMTF is easily shown to be reducible to the following linear program:(10)maximizez,w1,w2,…,wMzsubject  to:z≤∑m=1Mwmem,iNiI,z≤∑m=1Mwmfm,iNiO1≤i≤K,∑m=1Mwm=1,wm≥01≤m≤M,where z is the minimum network-wide user temporal share.The convexity of optimization problem (10) follows from the linearity of the objective function and constraints [43]. It is not difficult to show that for a given GPS this linear program has at least one solution and in the case of a nonunique solution, the objective function value, that is, z, is the same for all the solutions due to the convexity of the program. While there is no general closed form solution for MMTF, Theorem 4 provides a closed form solution when the patterns are mutually exclusive (e.g., EPS-n). When patterns are not mutually exclusive, there are numerous efficient numerical methods including simplex and interior point algorithms via which one can obtain a solution for MMTF with reasonable effort.Theorem 4.
If the patterns are mutually exclusive, the solution to the MMTF problem is unique and one has(11)wm∗=nm∑l=1Mnl1≤m≤M,z∗=1∑l=1Mnl,where nm denotes the number of users in the most crowded section of pattern m; that is, nm = maxi⁡{NiIem,i,NiIfm,i}i=1K.Proof.
Let{wm∗}m=1M and z∗ denote the solution of MMTF problem (10). Because the patterns are mutually exclusive, each section of the network is covered by one pattern. Therefore, according to (7), the minimum user air-time in pattern m is wm∗/nm. In other words, users in the most crowded section of pattern m have the minimum air-time share among all the users in that pattern. The claim is that the value of wm∗/nm is the same for every m. Let us assume that the claim is not correct. Therefore, if the user with minimum air-time share is in pattern m′, then there exists at least one m′′ for which wm′∗/nm′<wm′′∗/nm′′. It is clear that we can increase the minimum user air-time share in the network by decreasing wm′′∗ and increasing wm′∗. Therefore, wm′′∗ and wm′∗ are not optimal which is contradiction and the claim is correct. We can conclude that ∀m:z∗=wm∗/nm. On the other hand, we know that ∑m‍wm=1. Eventually, we can find the unique solution of MMTF problem, that is, {wm∗}m=1M and z∗, by solving the system of these M+1 independent linear equations as given in (11).We should note that, unlike IS-PTF, the MMTF problem always has a solution for any GPS. We also note that to solve the MMTF problem eachBSi is required to send the values NiI and NiO to the NLS which subsequently solves linear program (10) to obtain the per-pattern scheduling weights {wm}m=1M. Note that it is not necessary to solve the MMTF problem at each time slot. Instead, the MMTF problem can be solved when the number of users in any one of the sections of the CN changes. Alternatively, the MMTF linear program can be solved if the change in the number of users in the individual sections of the CN is substantial and the previous solutions’ weights can be used until such a substantial change. It is clear that this alternative mechanism may reduce the computational burden on the NLS.For the two fairness criteria studied in this paper, namely, IS-PTF and MMTF, we have described methods by which the scheduling weights{wm}m=1M are obtained. Exploration of other temporal fairness criteria are left for future research. In the next subsection, we are going to introduce a two-level scheduler that uses these scheduling weights so as to make opportunistic fair decisions to select patterns at the network-level and also users belonging to these patterns at the cell-level.


### 3.3. Two-Level Opportunistic Scheduler

In this section, we assume that the scheduling weights{wm}m=1M, {wi,jI}j=1NiI, and {wi,jO}j=1NiO are a priori given. Although the per-user scheduling weights in the current study are based on the identities (6), the proposed two-level scheduler described later in this section works for arbitrary per-user scheduling weights {wi,jI}j=1NiI and {wi,jO}j=1NiO. Subsequently, we introduce a credit parameter bi,jI for each inner section user Ui,jI and another credit parameter bi,jO for each outer section user Ui,jO with these two per-user credit parameters maintained by the CLS at BSi. We also introduce a credit parameter Bm for each pattern Pm maintained by the NLS. The initial values of all these credit parameters are set to zero at the beginning of network operation. We also define the instantaneous spectral efficiency (SE) ri,jI(τ) (ri,jO(τ)) in units of bps/Hz for user Ui,jI (Ui,jO) at time slot τ. In particular, in our numerical experiments, we use the Shannon formula(12)ri,jIτ=log2⁡1+SNRi,jIτ,ri,jOτ=log2⁡1+SNRi,jOτ,where SNRi,jI(τ) and SNRi,jO(τ) denote the signal to noise ratio of users Ui,jI and Ui,jO, respectively, at slot τ [44]. Other relationships of SE to the SNR than (12) can also be used. Next, we describe our proposed two-level multicell scheduling algorithm at a given time slot τ in a six-step process.Step 1.
As for the CLS,BSi of each cell Ci selects two users ji,I∗ and ji,O∗ from the inner section Ii and outer section Oi of the cell, respectively, based on the instantaneous user SEs and per-user credit parameter values as follows:(13)ji,I∗=arg⁡max1≤j≤NiI⁡ri,jIτ+αbi,jI,ji,O∗=arg⁡max1≤j≤NiO⁡ri,jOτ+αbi,jO,where α>0 is an algorithm parameter that we will study in the numerical examples to be shown to affect the convergence time and the overall network throughput.Step 2.
For each cell, the CLS of cellCi then nominates the users ji,I∗ and ji,O∗ and the instantaneous per-section SEs of the sections Ii and Oi, denoted by(14)RiIτ=ri,ji,I∗Iτ,RiOτ=ri,ji,O∗Oτ,respectively, if the nominated users were to be served. BSi then disseminates the values RiI(τ) and RiO(τ) to the NLS.Step 3.
For the pattern selection, in the third step, the NLS obtains the network-wide SE of patternPm, denoted by Rm(τ), as follows:(15)Rmτ=∑i=1KRiIτem,i+RiOτfm,i,1≤m≤M.Step 4.
The NLS selects the patternPm∗ to be activated based on the following identity:(16)m∗=arg⁡max1≤m≤M⁡Rmτ+βBm,where β is a second algorithm parameter similar to α in (13).Step 5.
Oncem∗ is determined, the per-pattern credit parameters are updated in the fifth step as follows:(17)Bm=Bm+wm-1m=m∗1≤m≤M.The NLS then sends a message to all CLSs with the information on which pattern was selected in the current slot.Step 6.
The nominated users in the sections belonging to the selected patternPm∗ are scheduled in the current time slot. Moreover, the credit parameters of users in the sections belonging to the selected pattern Pm∗ are updated as follows:(18)bi,jI=bi,jI+wi,jI-1j=ji,I∗,∀j,Ii∈Pm∗,bi,jO=bi,jO+wi,jO-1j=ji,O∗,∀j,Oi∈Pm∗.The credit parameters of users in sections that do not reside in the selected pattern are not updated and those sections are not activated in the current slot.Moreover, one can write the long-term average network throughputT as follows:(19)T=limt→∞⁡BWt∑τ=1tRm∗τ.


### 3.4. Remarks on the Proposed Algorithm

Per-pattern credit parameters are updated in (17) and it is obvious that these parameters cannot grow to either plus or minus infinity. This can be observed from the decision made to activate a pattern at the network-level according to (16) which ensures that credit parameters will stay bounded. Bounded credit parameters are indication of satisfaction of desired temporal fairness constraints at the pattern level. Similar conclusions can be drawn for the per-user credit parameters and the satisfaction of desired temporal fairness constraints at the user level. Although we do not have optimality results for the proposed multicell scheduler, we note that the structures of the two TF schedulers NLS in (16) and the CLSs in (13) follow that of the single-cell optimum TF scheduler described in [24] except that we use fixed coefficients α and β as in [28] instead of those that decay in time. The purpose of this choice is to satisfy fairness constraints not only in the long-term but also in shorter time scales. Numerical examples will be presented to validate these choices.The NLS hasO(MK) computational complexity and O(M) storage requirements and presents a scalable solution when compared to existing methods whose complexity depends on the overall number of users N in the network. Due to low communications overhead between the CLSs and the NLS, the proposed method is relatively practical and can be implemented using a sufficiently low-delay backhaul. However, we note that the two-way CLS to NLS communication should be completed before any data transmission can start in the proposed algorithm. For larger slot lengths, this communication delay is less of a problem. However, for shorter slots, inefficiencies due to signaling overhead may be significant. The adaptation of the proposed algorithm to more realistic multicarrier wireless networks with short slots (e.g., LTE-A with subframes of 0.1 ms) is left for future research.


## 3.1. Per-Pattern and Per-User Temporal Shares

LetAm, ai,jI, and ai,jO denote the long-term temporal (or equivalently air-time) share of pattern Pm, user Ui,jI, and user Ui,jO, respectively:(4)Am=limt→∞⁡1t∑τ=1t1m∗τ=mai,jI=limt→∞⁡1t∑τ=1t1userUi,jIis  scheduled  at  slotτai,jO=limt→∞⁡1t∑τ=1t1userUi,jOis  scheduled  at  slotτ,where 1{·} denotes the conventional indicator function which is either one or zero depending on whether the argument is true or not, respectively. Similarly, let AiI, AiO, and AiC denote the long-term air-time share of section Ii, section Oi, and cell Ci, respectively. Mathematically, (5)AiI=limt→∞⁡1t∑τ=1t1Ii∈Pm∗τAiO=limt→∞⁡1t∑τ=1t1Oi∈Pm∗τAiC=AiI+AiO.We introduce positive (target) scheduling weights {wm}m=1M for patterns {Pm}m=1M satisfying ∑mwm=1. The target scheduling weight wm is the long-term target average probability that pattern Pm is selected by the scheduler. Note that use of scheduling weight {wm}m=1M by the scheduler should give rise to Am=wm,∀m. In this case, the system is said to be interpattern weighted temporal fair with respect to the weights {wm}m=1M. In the specific case of wm=1/M, the system is called interpattern temporal fair. Similarly, we introduce target positive scheduling weights {wi,jI}j=1NiI and {wi,jO}j=1NiO for user Ui,jI and user Ui,jO, respectively, satisfying ∑jwi,jI=1 and ∑jwi,jO=1 for each of the cells Ci. We remark that the use of user scheduling weights {wi,jI}j=1NiI and {wi,jO}j=1NiO leads to ai,jI=AiIwi,jI,∀j, for any section Ii and ai,jO=AiOwi,jO,∀j, for any section Oi. In this case we have intrasection weighted temporal fairness in sections Ii and Oi, respectively, with respect to the weights {wi,jI}j=1NiI and {wi,jO}j=1NiO. In this paper, we only consider ordinary intrasection temporal fairness which leads to the following two identities:(6)wi,jI=1NiI,1≤j≤NiI,wi,jO=1NiO,1≤j≤NiO.In case when NiI or NiO is zero, no per-user scheduling weights are assigned for that particular section. Moreover, no downlink transmission would take place due to the lack of a user in that section even if the included pattern is selected for transmission. Therefore, the only unknowns to the scheduler in the numerical examples of the current study are the per-pattern weights. Once the weights are decided, then the following identities immediately hold:(7)AiI=∑m=1Mwmem,i,ai,jI=AiINiI,(8)AiO=∑m=1Mwmfm,i,ai,jO=AiONiO,where em,i≜1Ii∈Pm and fm,i≜1Oi∈Pm. In the next subsection, we focus on methods of obtaining these weights leading to two different forms of temporal fairness being sought in the CN.


## 3.2. Temporal Fairness Criteria

In this paper, we consider two different TF criteria for the multicell CN for which the per-pattern weights can easily be obtained at reasonable computational complexity. The first TF criterion is the so-called Intersection Proportional Temporal Fairness (IS-PTF) in which the CN is intercell temporal fair one but an inner section of each cell receives a temporal share proportional to the temporal share of the outer section of the same cell using the same network-wide proportionality constant. Mathematically,AiC=AjC,1≤i,j≤K, and AiI=dAiO,1≤i≤K, hold for a fairness proportionality constant d to be chosen by the network operator. As a matter of fact, employing d>1 causes the inner sections to be scheduled more often than the outer sections and vice versa for the case 0<d<1. It is clear that IS-PTF cannot be achieved for some general pattern sets such as GPS of Figure 3. However, as stated in the theorem below, IS-PTF is achievable when EPS-n is used as the pattern set.Theorem 3.
With EPS-n used as the pattern set, IS-PTF is achieved by the following choice of weights:(9)wi=1d+n1≤i≤n,wn+1=dd+n,where M=n+1 and the pattern PM is the set of all inner sections of the CN; that is, PM=⋃i=1KIi.Proof.
We note that EPS-n= MPS-n ∪  PM and Am,1≤m≤n, and AM are the temporal shares of  mth individual MPS-n and PM, respectively. Furthermore, the scheduler can guarantee that Am=wm,1≤m≤n and AM=wM. Patterns in MPS-n are mutually exclusive; thus for each section Oi there is only one index m,1≤m≤n, such that AiO=wm. Furthermore, ∀i:AiI=wM. We thus conclude that, for all i, there exists m,1≤m≤n, such that AiC=wm+wM. Recall that intercell fairness requires ∀m1,m2,1≤m1,m2≤n:wm1+wM=wm2+wM which in turn implies that ∀m1,m2,1≤m1,m2≤n:wm1=wm2≜w. Moreover, using intersection fairness we have ∀m,1≤m≤n:wM=dwm=dw. Finally, the pattern weights sum to unity; that is, ∑m=1nwm+wM=1. Therefore, nw+dw=1 which implies that ∀m,1≤m≤n:wm=w=1/d+n and wM=wn+1=d/d+n.For the special case of EPS-3, there areM=4 patterns depicted in Figure 2 where the corresponding weights are w1=w2=w3=1/d+3 and w4=d/(d+3).Although IS-PTF criterion guarantees equal user temporal shares within each section, it does not seek network-wide fairness among all the network users. That is why IS-PTF does not take into account the number of users located in each section for obtaining pattern weights{wm}m=1M. As a result, using IS-PTF along with unbalanced user distribution may lead to unequal temporal share for the users located in different sections of the network. The second TF criterion we study in this paper is max-min temporal fairness (MMTF) for which the pattern weights {wm}m=1M are selected so that the minimum user temporal share in the network is maximized. Thus, MMTF is a network-wide fairness criterion. The MMTF is easily shown to be reducible to the following linear program:(10)maximizez,w1,w2,…,wMzsubject  to:z≤∑m=1Mwmem,iNiI,z≤∑m=1Mwmfm,iNiO1≤i≤K,∑m=1Mwm=1,wm≥01≤m≤M,where z is the minimum network-wide user temporal share.The convexity of optimization problem (10) follows from the linearity of the objective function and constraints [43]. It is not difficult to show that for a given GPS this linear program has at least one solution and in the case of a nonunique solution, the objective function value, that is, z, is the same for all the solutions due to the convexity of the program. While there is no general closed form solution for MMTF, Theorem 4 provides a closed form solution when the patterns are mutually exclusive (e.g., EPS-n). When patterns are not mutually exclusive, there are numerous efficient numerical methods including simplex and interior point algorithms via which one can obtain a solution for MMTF with reasonable effort.Theorem 4.
If the patterns are mutually exclusive, the solution to the MMTF problem is unique and one has(11)wm∗=nm∑l=1Mnl1≤m≤M,z∗=1∑l=1Mnl,where nm denotes the number of users in the most crowded section of pattern m; that is, nm = maxi⁡{NiIem,i,NiIfm,i}i=1K.Proof.
Let{wm∗}m=1M and z∗ denote the solution of MMTF problem (10). Because the patterns are mutually exclusive, each section of the network is covered by one pattern. Therefore, according to (7), the minimum user air-time in pattern m is wm∗/nm. In other words, users in the most crowded section of pattern m have the minimum air-time share among all the users in that pattern. The claim is that the value of wm∗/nm is the same for every m. Let us assume that the claim is not correct. Therefore, if the user with minimum air-time share is in pattern m′, then there exists at least one m′′ for which wm′∗/nm′<wm′′∗/nm′′. It is clear that we can increase the minimum user air-time share in the network by decreasing wm′′∗ and increasing wm′∗. Therefore, wm′′∗ and wm′∗ are not optimal which is contradiction and the claim is correct. We can conclude that ∀m:z∗=wm∗/nm. On the other hand, we know that ∑m‍wm=1. Eventually, we can find the unique solution of MMTF problem, that is, {wm∗}m=1M and z∗, by solving the system of these M+1 independent linear equations as given in (11).We should note that, unlike IS-PTF, the MMTF problem always has a solution for any GPS. We also note that to solve the MMTF problem eachBSi is required to send the values NiI and NiO to the NLS which subsequently solves linear program (10) to obtain the per-pattern scheduling weights {wm}m=1M. Note that it is not necessary to solve the MMTF problem at each time slot. Instead, the MMTF problem can be solved when the number of users in any one of the sections of the CN changes. Alternatively, the MMTF linear program can be solved if the change in the number of users in the individual sections of the CN is substantial and the previous solutions’ weights can be used until such a substantial change. It is clear that this alternative mechanism may reduce the computational burden on the NLS.For the two fairness criteria studied in this paper, namely, IS-PTF and MMTF, we have described methods by which the scheduling weights{wm}m=1M are obtained. Exploration of other temporal fairness criteria are left for future research. In the next subsection, we are going to introduce a two-level scheduler that uses these scheduling weights so as to make opportunistic fair decisions to select patterns at the network-level and also users belonging to these patterns at the cell-level.


## 3.3. Two-Level Opportunistic Scheduler

In this section, we assume that the scheduling weights{wm}m=1M, {wi,jI}j=1NiI, and {wi,jO}j=1NiO are a priori given. Although the per-user scheduling weights in the current study are based on the identities (6), the proposed two-level scheduler described later in this section works for arbitrary per-user scheduling weights {wi,jI}j=1NiI and {wi,jO}j=1NiO. Subsequently, we introduce a credit parameter bi,jI for each inner section user Ui,jI and another credit parameter bi,jO for each outer section user Ui,jO with these two per-user credit parameters maintained by the CLS at BSi. We also introduce a credit parameter Bm for each pattern Pm maintained by the NLS. The initial values of all these credit parameters are set to zero at the beginning of network operation. We also define the instantaneous spectral efficiency (SE) ri,jI(τ) (ri,jO(τ)) in units of bps/Hz for user Ui,jI (Ui,jO) at time slot τ. In particular, in our numerical experiments, we use the Shannon formula(12)ri,jIτ=log2⁡1+SNRi,jIτ,ri,jOτ=log2⁡1+SNRi,jOτ,where SNRi,jI(τ) and SNRi,jO(τ) denote the signal to noise ratio of users Ui,jI and Ui,jO, respectively, at slot τ [44]. Other relationships of SE to the SNR than (12) can also be used. Next, we describe our proposed two-level multicell scheduling algorithm at a given time slot τ in a six-step process.Step 1.
As for the CLS,BSi of each cell Ci selects two users ji,I∗ and ji,O∗ from the inner section Ii and outer section Oi of the cell, respectively, based on the instantaneous user SEs and per-user credit parameter values as follows:(13)ji,I∗=arg⁡max1≤j≤NiI⁡ri,jIτ+αbi,jI,ji,O∗=arg⁡max1≤j≤NiO⁡ri,jOτ+αbi,jO,where α>0 is an algorithm parameter that we will study in the numerical examples to be shown to affect the convergence time and the overall network throughput.Step 2.
For each cell, the CLS of cellCi then nominates the users ji,I∗ and ji,O∗ and the instantaneous per-section SEs of the sections Ii and Oi, denoted by(14)RiIτ=ri,ji,I∗Iτ,RiOτ=ri,ji,O∗Oτ,respectively, if the nominated users were to be served. BSi then disseminates the values RiI(τ) and RiO(τ) to the NLS.Step 3.
For the pattern selection, in the third step, the NLS obtains the network-wide SE of patternPm, denoted by Rm(τ), as follows:(15)Rmτ=∑i=1KRiIτem,i+RiOτfm,i,1≤m≤M.Step 4.
The NLS selects the patternPm∗ to be activated based on the following identity:(16)m∗=arg⁡max1≤m≤M⁡Rmτ+βBm,where β is a second algorithm parameter similar to α in (13).Step 5.
Oncem∗ is determined, the per-pattern credit parameters are updated in the fifth step as follows:(17)Bm=Bm+wm-1m=m∗1≤m≤M.The NLS then sends a message to all CLSs with the information on which pattern was selected in the current slot.Step 6.
The nominated users in the sections belonging to the selected patternPm∗ are scheduled in the current time slot. Moreover, the credit parameters of users in the sections belonging to the selected pattern Pm∗ are updated as follows:(18)bi,jI=bi,jI+wi,jI-1j=ji,I∗,∀j,Ii∈Pm∗,bi,jO=bi,jO+wi,jO-1j=ji,O∗,∀j,Oi∈Pm∗.The credit parameters of users in sections that do not reside in the selected pattern are not updated and those sections are not activated in the current slot.Moreover, one can write the long-term average network throughputT as follows:(19)T=limt→∞⁡BWt∑τ=1tRm∗τ.


## 3.4. Remarks on the Proposed Algorithm

Per-pattern credit parameters are updated in (17) and it is obvious that these parameters cannot grow to either plus or minus infinity. This can be observed from the decision made to activate a pattern at the network-level according to (16) which ensures that credit parameters will stay bounded. Bounded credit parameters are indication of satisfaction of desired temporal fairness constraints at the pattern level. Similar conclusions can be drawn for the per-user credit parameters and the satisfaction of desired temporal fairness constraints at the user level. Although we do not have optimality results for the proposed multicell scheduler, we note that the structures of the two TF schedulers NLS in (16) and the CLSs in (13) follow that of the single-cell optimum TF scheduler described in [24] except that we use fixed coefficients α and β as in [28] instead of those that decay in time. The purpose of this choice is to satisfy fairness constraints not only in the long-term but also in shorter time scales. Numerical examples will be presented to validate these choices.The NLS hasO(MK) computational complexity and O(M) storage requirements and presents a scalable solution when compared to existing methods whose complexity depends on the overall number of users N in the network. Due to low communications overhead between the CLSs and the NLS, the proposed method is relatively practical and can be implemented using a sufficiently low-delay backhaul. However, we note that the two-way CLS to NLS communication should be completed before any data transmission can start in the proposed algorithm. For larger slot lengths, this communication delay is less of a problem. However, for shorter slots, inefficiencies due to signaling overhead may be significant. The adaptation of the proposed algorithm to more realistic multicarrier wireless networks with short slots (e.g., LTE-A with subframes of 0.1 ms) is left for future research.


## 4. Numerical Examples

In all the numerical examples, we use one of the 6-cell and 9-cell CNs provided in Figure5 and an additional 37-cell CN depicted in Figure 6. The radii parameters RI and RC are assumed to be 0.5km and 1km, respectively, for all the CNs. The system frequency is assumed to be 2GHz and BW is set to 20MHz. Noise power spectral density and user equipment noise figure are assumed to be −174 dBm/Hz and 9 dB, respectively. Transmission power of each BS to the inner and outer users is 30 dBm and 40 dBm, respectively. It is straightforward to show that the choices of transmit powers and radii parameters RC and RI satisfy (1)–(3) for n=3 which is our focus in this section. The large-scale fading channel coefficients are modeled based on the COST-231 model as -140.7-35.2log10⁡dBSU+Ψ in dB scale, where dBSU is the distance between the corresponding user and BS, and Ψ~N(0,σΨ2) represents the log-normal shadowing effect. We assume that σΨ = 4dB. Rayleigh fading model is adopted for small-scale channel coefficient variations [5]. It is assumed that small-scale fading channel coefficients are fixed during each time slot and vary independently over different time slots (block fading). Also, we assume that shadow fading coefficients are fixed in the duration of 50 consecutive time slots and vary independently otherwise.Figure 6
37-cell cellular network.


### 4.1. Study of Scheduler Parametersα and β

In this example, we study the effect of the algorithm parametersα and β employed through the identities (13) and (16), on the convergence time and long-term network throughput. We assume that the scheduler uses EPS-3 with cardinality 4 in the 9-cell network of Figure 5(a). We employ IS-PTF with the parameter d set to unity; that is, we seek ordinary intercell and intersection fairness in this example. For a given section Ii (Oi), let JiI(t) (JiO(t)) denote Jain’s fairness index for the temporal shares ai,jI(t) (ai,jO(t)) which are shares of the users Ui,jI(Ui,jO(t)) up to time t. We refer to [45] for the definition of Jain’s fairness index. Let us also define the intrasection fairness index JI(t)=mini⁡JiI(t) (JOt=mini⁡JiO(t)) for inner (outer) sections. Proximity of JI(t) (JO(t)) to unity is representative of intrasection fairness for the inner (outer) section users up to time t. Also, let the interpattern fairness index J(t) be defined by Jain’s fairness index for the individual per-pattern temporal shares Amt. Similarly, proximity of J(t) to unity is representative of interpattern fairness up to time t. Furthermore, we note that interpattern fairness is equivalent to ordinary intercell fairness in this example since the patterns are mutually exclusive. We assume N=64 uniformly located users in the 9-cell network of Figure 5(a) for each of the 20 simulation instances and for each instance we run the two-level scheduler for a duration of 5×106 slots with various choices of α and β. In each simulation instance, we obtain the values ΓJ and ΓJI (ΓJO), which are defined as the minimum value of t such that J(Ht)≥1-ϵ and JI(Ht)≥1-ϵ (JO(Ht)≥1-ϵ), respectively, for a small tolerance parameter ϵ>0 which is set to 0.05 and for a sampling parameter H set to 1000. A relatively large value of ΓJI (ΓJO) is indicative of longer convergence times and therefore adverse impact on short-term intrasection fairness for inner (outer) section users. On the other hand, a relatively large value of ΓJ is indicative of short-term intercell unfairness. The steady-state throughput T and three fairness metrics ΓJ, ΓJI, and ΓJO (average values obtained over the 20 simulation instances) are tabulated in Table 3 for various choices of α and β.Table 3
The average throughputT and the average of three fairness metrics ΓJ, ΓJI, and ΓJO for various values of α and β for the 9-cell CN.
α β T (Mbps) Γ J Γ J I Γ J O 0.1 125.4 1.00 1.40 2.60 0.1 0.01 125.5 5.10 1.05 3.00 0.001 125.8 45.35 1.00 8.00  0.1 126.4 1.05 11.45 20.05 0.01 0.01 126.5 4.90 9.85 20.55 0.001 126.9 45.35 4.35 25.60  0.1 126.9 1.15 111.40 195.90 0.001 0.01 127.1 6.25 110.00 196.50 0.001 127.4 44.05 94.35 201.00We observe from Table3 that the particular choice of the algorithm parameters α and β has only a slight impact on the overall throughout with slight improvement in T with lower choices of α and β. On the other hand, when α and β are decreased, as a penalty, the various fairness indices of interest converge in a slower manner and short-term intercell and intrasection fairness measures are consequently compromised. In particular, while ΓJ is more sensitive to the change of β, ΓJI and ΓJO appear to more sensitive to the change of α. Similar observations are made in other scenarios as well but are not reported in the current manuscript. As a trade-off between short-term intercell and intrasection fairness and total network throughput, we fix α=β=0.01 in the remaining numerical examples.


### 4.2. Comparison of Opportunistic FFR versus Benchmark FFR

The use of the pattern set EPS-3 with the proposed opportunistic scheduler based on IS-PTF is referred to as opportunistic FFR (OFFR) in this paper. In this example, OFFR uses the IS-PTF formulation with a certain choice of the parameterd introduced in (9). In particular, we first study three different values of the parameter d, namely, d=1/4,1,4, and consequently use the per-pattern weights as given in (9). The benchmark system called benchmark FFR (BFFR) splits the BW into four subbands, the bandwidth of each subband being proportional to wm for m∈{1,2,3,4} based on identity (9). The intracell scheduler of BFFR is the same as that of the OFFR. Besides, we note that there is no NLS in BFFR and ICI is handled by static spectrum partitioning as described above. For each value of d, we simulated BFFR and OFFR in both 9-cell and 37-cell CNs for a total of 400 instances each of which spans 106 time slots. In each of these simulations, the number of users N is set to 64 and the users are randomly spread over the CN. Let TOFFR and TBFFR denote the overall network throughput when we employ OFFR and BFFR, respectively. Also, let Ti,jI,OFFR and Ti,jI,BFFR denote the average throughput of user Ui,jI when we employ OFFR and BFFR, respectively. Similarly, let Ti,jO,OFFR and Ti,jO,BFFR denote the average throughput of user Ui,jO when OFFR and BFFR, respectively, are employed. Furthermore, let(20)G=TOFFR-TBFFRTBFFR100%denote the network throughput percentage gain of OFFR over BFFR. Similarly, let (21)Gi,jI=Ti,jI,OFFR-Ti,jI,BFFRTi,jI,BFFR100%,Gi,jO=Ti,jO,OFFR-Ti,jO,BFFRTi,jO,BFFR100%denote the user throughput percentage gain of OFFR over BFFR for users Ui,jI and Ui,jO, respectively. Figures 7(a) and 7(b) illustrate the empirical Cumulative Distribution Function (CDF) of the gains Gi,jI and Gi,jO for the specific case of N=64 for 9-cell and 37-cell CNs, respectively.Figure 7
Empirical CDF of the users throughput gainsGi,jI and Gi,jO for N=64 for three different values of d in 9-cell and 37-cell networks.
(a)
9-cell scenario (b)
37-cell scenarioWe first note that as the parameterd decreases, the patterns including outer sections are scheduled more frequently in OFFR and a wider frequency band is assigned to outer section users in BFFR. We have the following observations from Figures 7(a) and 7(b):(i)
In all studied cases, a large majority of users benefited from OFFR, that is, positive gains, in comparison with BFFR. This situation is more apparent in the 37-cell scenario. These positive gains stem from network-wide opportunistic scheduling in OFFR as opposed to conventional single-cell scheduling along with static spectrum partitioning in BFFR.(ii)
We also observe that whend increases (decreases), outer (inner) section users gain substantially more with OFFR against BFFR.We further extend this example by varyingN∈{32,64,128} and the parameter d∈{1/4,1,4} and simulate the same scenario. Let G, GI, and GO denote the empirical expected values of the quantities G, Gi,jI, and Gi,jO, respectively, out of the 400 simulation instances. Also, let P, PI, and PO denote the percentage fraction of samples of G, Gi,jI, and Gi,jO, respectively, which are below zero, that is, those scenarios or users who do not benefit from OFFR. Table 4 provides the quantities G, GI, GO, PI, and PO, for varying choices of d and N. We note that the quantity P is found to be zero for all studied cases; that is, all networks benefited from OFFR in comparison with BFFR in terms of average throughput. Our further findings are as follows:(i)
As the number of users in the network increases, the average gain obtained with OFFR decreases and moreover the fraction of users that do not benefit from OFFR also increases with increasedN. The OFFR gain becomes more substantial when the number of users in the network is relatively smaller. This observation can be explained by the fact that when there is just one user or few users within a cell (which happens when the overall number of users is small), opportunistic scheduling within a cell as in BFFR is not as effective. In such scenarios, network-wide opportunistic scheduling helps the network users significantly.(ii)
The OFFR average gains are slightly more substantial in the 37-cell network than the 9-cell network.(iii)
Only a relatively small fraction of users appeared to fail to gain with OFFR. This quantity is observed to diminish significantly in the particular 37-cell network scenario. For example, in the worst case, for the 37-cell network scenario, only 6.8% (1.1%) of the outer (inner) users failed to gain with OFFR ford=1/4 (d=1) out of all the studies we have performed.Table 4
The comparative results associated with OFFR and BFFR when the system parametersd and N are varied.
Scenario d N G G I G O P I P O 32 24.5 32.6 16.8 0 0.5 1 / 4 64 16.6 21.1 10.6 0.2 2.0 128 11.1 14.7 6.5 0.5 6.8 32 24.1 20.6 19.0 0 0.4 37-cell 1 64 16.2 13.7 11.9 0.3 2.1 128 10.9 8.8 7.2 1.1 6.7 32 19.8 10.5 23.5 0 0.4 4 64 12.7 7.0 14.5 0.1 1.9 128 8.0 4.6 8.9 0.6 6.1  32 22.0 29.5 14.5 0.7 4.3 1 / 4 64 14.8 17.6 9.0 3.0 10.0 128 10.5 11.5 6.1 6.1 15.0 32 22.1 17.8 16.1 0.6 4.3 9-cell 1 64 14.5 10.5 9.8 4.4 10.0 128 9.9 6.5 6.7 9.4 14.5 32 16.4 9.4 19.8 0.5 4.4 4 64 10.3 5.8 12.3 3.1 8.9 128 6.5 3.4 8.3 9.1 12.1


### 4.3. Impact of GPS Selection for the MMTF Formulation

In this section, we study the impact of the choice of the underlying pattern set in the context of MMTF problem (10). The performance metric is taken as the minimum of the temporal shares of all the users served in the CN (z in (10)). Recall that MMTF attempts to maximize this quantity through the linear program given in Section 3.2 through which we obtain the per-pattern weights for this numerical example and consequently the performance metric. For this purpose, given the CNs with K=6 or 9 cells depicted in Figure 5, 10K users are spread through the CN uniformly, leading to an average population of 10 users per cell. After locating 10K users in the CN, one section is selected at random and 10P,P∈{1,2,…,10} users are further introduced in this cell for the purpose of making the user distribution through the network more nonuniform. To quantify this nonuniformity, we introduce the parameter η=(1+P)/(K+P) which gives the expected number of users in the most crowded cell divided by the overall number of users in the network. The larger the parameter P or η is, the more nonuniform the user distribution becomes. Subsequently, each MMTF problem is solved 1000 times each of which is obtained by associating 10(K+P) users in the CN with the individual cells and their sections. The average of the 1000 instances is then reported. We first study the 9-cell scenario given in Figure 5(a). We study the following pattern sets in the simulation study (the individual patterns are defined in Table 1):(i)
GPS1 = {P1,P2,P3,P4,P5,P8,P11,P15,P22,P29}(ii)
GPS2 = GPS1∪P24,P36(iii)
GPS3 = GPS2∪P6,P10,P17,P19,P21(iv)
GPS4: pattern set obtained by Algorithm 1 with cardinality 22 which is presented in Table 1(v)
EPS-3(vi)
UPS presented in Table1.Figure8 depicts the performance of the six pattern sets of choice mentioned above in terms of the minimum temporal share as a function of the nonuniformity parameter η. As η increases, the minimum temporal share decreases for all the employed pattern sets. This observation stems from the fact that an increase in η implies that one of the sections gets more crowded and consequently the users in that section get less chance to be scheduled. UPS outperforms all the other pattern sets for all values of η. This is because UPS includes every possible pattern which leads to the largest possible feasible set for problem (10). We remark that that the performance of UPS is an upper-bound for any GPS since every GPS is a subset of UPS according to Section 2.2. On the other hand, the performance of GPS4, obtained by Algorithm 1, is only slightly below that of UPS while the computational load required by Algorithm 1 to construct GPS4 is remarkably lower than that of ES. This implies that the patterns generated by Algorithm 1 can be used along with MMTF scheduler to manage nonuniform user distribution well. Furthermore, we observe that GPS3 outperforms GPS2 which in turn outperforms GPS1. This is because GPS1⊂GPS2⊂GPS3. Therefore, we conclude that adding more patterns to an employed pattern set consistently enhances the performance of the MMTF scheduler as expected. Similar conclusions are drawn for the 6-cell scenario for which we comparatively study four pattern sets, namely, EPS-3, UPS, GPS1 = {P1,P2,P3,P4,P5,P6,P7,P8}, and GPS2 being the GPS obtained by Algorithm 1 where the patterns are illustrated in Table 2. Figure 9 illustrates the performance of these four pattern sets. We conclude that pattern set selection and/or its cardinality are crucial for MMTF schedulers especially for CNs with larger number of cells.Figure 8
Performance of various pattern sets in the 9-cell scenario as a function of the nonuniformity parameterη.Figure 9
Performance of various pattern sets in the 6-cell scenario as a function of the nonuniformity parameterη.


### 4.4. Performance of the Proposed Scheduler in Nonhomogeneously Populated Networks

In this example, we use Zipf-distributed user populations in the multicell CN for nonuniform traffic demands [46]. The Zipf distribution has been successfully used in modeling various behaviors in computing and communications systems [46, 47]. Particular to traffic demand distribution in wireless networks, [48] uses a Zipf distribution to model traffic demands across multiple access points in an enterprise wireless LAN. The work in [49] studies a wireless network with heterogeneous clusters in which the cluster population sizes are distributed according to a Zipf distribution. In order to describe the Zipf distribution based on [46], let K be the number of elements and k∈{1,2,…,K} be the rank of an element. Let s denote the parameter characterizing the Zipf distribution. A given entity is an element of rank k with probability c/ks,s≥0 where c is a normalization constant. When K→∞, the parameter s should satisfy s>1. When K is finite and s=0, we have a discrete uniform distribution. When the parameter s is increased, the population of the individual elements in the entire population becomes more nonuniform.In this example, we will study the impact of the parameters if a selected user n∈1,2,…,N resides in a cell k∈1,2,…,K according to a Zipf distribution with parameters K and s. We fix K=9 and we distribute N∈32,64,128 users in the 9-cell CN according to a Zipf distribution with parameter s∈0,0.5,1,1.5,2. The ranks of cells in the 9-cell network are depicted in Figure 5(a). The user location within a cell is uniformly random. For each value of N, we distribute the users in the CN as described above and subsequently run the two-level scheduler using the MMTF formulation with GPS4 in Section 4.3 with 22 patterns. We also run the scheduler using IS-PTF with EPS-3 and d=1 as a benchmark. For each pair of s and N, we run the experiment 100 times each with a duration of 106 time slots. We obtain the minimum user temporal share and minimum and average user throughput for each instance using MMTF and IS-PTF schedulers and take the averages of these individual values over all the 100 simulated instances for a given pair (N,s). Table 5 illustrates the minimum user temporal share (denoted by amin), the minimum user throughput (denoted by Tmin), and the average user throughput (denoted by Tavg) for both MMTF and IS-PTF schedulers as a function of s and N. In general, we observe that the MMTF scheduler leads to higher minimum user throughput than IS-PTF. This is not surprising since MMTF is guaranteed to maximize minimum temporal share according to (10). Also, when N increases, the minimum user throughput and temporal share decrease for both schedulers because increasing N leads to less chance for the users to be scheduled. Furthermore, when s increases, the performance of the MMTF scheduler gets better relative to the IS-PTF scheduler in terms of Tmin and amin. This is because the user distribution is more nonuniform for larger values of s and MMTF scheduler takes into account the number of users in different sections of the network while IS-PTF does not. Therefore, we conclude that the MMTF scheduler becomes more effective in nonhomogeneously populated cellular networks if the performance metric is to be taken as the minimum user throughput or temporal share. We also observe that while the average user throughput is slightly larger with IS-PTF in most of the cases, the gap between IS-PTF and MMTF is small.Table 5
Minimum user temporal share, minimum network-wide user throughput (in kbps), and average network-wide user throughput (in Mbps) using MMTF and IS-PTF schedulers in the 9-cell CN.
s N a m i n M M T F a m i n I S - P T F T m i n M M T F T m i n I S - P T F T a v g M M T F T a v g I S - P T F 32 0.093 0.048 207.1 174.5 3.10 3.02 0 64 0.041 0.028 81.9 71.9 1.92 2.08 128 0.022 0.015 35.9 35.5 1.09 1.24  32 0.066 0.042 184.4 161.6 2.96 2.91 0.5 64 0.035 0.023 81.3 77.1 1.91 1.96 128 0.018 0.012 30.2 30.1 1.17 1.22  32 0.052 0.029 180.5 149.1 2.81 2.73 1 64 0.027 0.015 69.3 55.3 1.77 1.78 128 0.013 0.007 27.4 24.1 1.14 1.15  32 0.043 0.019 131.5 85.9 2.27 2.24 1.5 64 0.022 0.010 54.5 39.2 1.58 1.60 128 0.011 0.005 21.2 16.3 0.95 0.97  32 0.038 0.016 130.4 78.7 2.02 1.95 2 64 0.019 0.007 51.3 31.9 1.27 1.30 128 0.009 0.004 19.9 11.7 0.81 0.84


### 4.5. Transient Behavior of the Proposed Scheduler

In this example, we study the transient behavior of the proposed two-level scheduler in the 9-cell CN considering the two different fairness criteria, namely, IS-PTF and MMTF. For the MMTF criterion, we obtain pattern weights by solving problem (10) while employing the GPS constructed by Algorithm 1 with n=3. For the IS-PTF criterion, we consider the pattern set EPS-3 and use (9) with the proportionality parameter d set to unity. At time τ=0, we distribute 3 and 9 users in each inner and outer section of the 9-cell CN, respectively, at uniformly random locations within the cells. Subsequently, we run the proposed two-level scheduler using the pattern weights obtained based on the corresponding fairness criterion. At time slot τ1=4×105, we add 3 and 9 more users to I5 and O5, respectively, and update the per-pattern weights. At time slot τ2=8×105, we remove these users back from the network and update back the per-pattern weights. Figures 10(a) and 10(b) illustrate the sampled cumulative temporal share of a randomly selected user in O5 with sampling rate of H=0.1 (one sample per ten slots) as a function of time, for the IS-PTF and MMTF scenarios, respectively. We observe that the proposed scheduler converges with the employed parameters as time evolves for any of the three time intervals (before the next per-pattern weight updates take place). Figures 11(a) and 11(b) depict the sampled average throughput of the same user as a function of time for the IS-PTF and MMTF criteria, respectively. We observe that the steady-state throughput of the selected user is higher in each interval with the MMTF criterion in place, compared with IS-PTF. This is because MMTF considers the number of users in different cells while IS-PTF does not.Figure 10
Transient behavior of the temporal share associated with a randomly chosen outer section user in cell 5 for (a) IS-PTF and (b) MMTF.
(a)
Cumulative temporal share of an outer user in cell 5 using IS-PTF criterion with respect to time (b)
Cumulative temporal share of an outer user in cell 5 using MMTF criterion with respect to timeFigure 11
Transient behavior of the throughput associated with a randomly chosen outer section user in cell 5 for (a) IS-PTF and (b) MMTF.
(a)
Throughput of an outer user in cell 5 using IS-PTF criterion with respect to time (b)
Throughput of an outer user in cell 5 using MMTF criterion with respect to time


## 4.1. Study of Scheduler Parametersα and β

In this example, we study the effect of the algorithm parametersα and β employed through the identities (13) and (16), on the convergence time and long-term network throughput. We assume that the scheduler uses EPS-3 with cardinality 4 in the 9-cell network of Figure 5(a). We employ IS-PTF with the parameter d set to unity; that is, we seek ordinary intercell and intersection fairness in this example. For a given section Ii (Oi), let JiI(t) (JiO(t)) denote Jain’s fairness index for the temporal shares ai,jI(t) (ai,jO(t)) which are shares of the users Ui,jI(Ui,jO(t)) up to time t. We refer to [45] for the definition of Jain’s fairness index. Let us also define the intrasection fairness index JI(t)=mini⁡JiI(t) (JOt=mini⁡JiO(t)) for inner (outer) sections. Proximity of JI(t) (JO(t)) to unity is representative of intrasection fairness for the inner (outer) section users up to time t. Also, let the interpattern fairness index J(t) be defined by Jain’s fairness index for the individual per-pattern temporal shares Amt. Similarly, proximity of J(t) to unity is representative of interpattern fairness up to time t. Furthermore, we note that interpattern fairness is equivalent to ordinary intercell fairness in this example since the patterns are mutually exclusive. We assume N=64 uniformly located users in the 9-cell network of Figure 5(a) for each of the 20 simulation instances and for each instance we run the two-level scheduler for a duration of 5×106 slots with various choices of α and β. In each simulation instance, we obtain the values ΓJ and ΓJI (ΓJO), which are defined as the minimum value of t such that J(Ht)≥1-ϵ and JI(Ht)≥1-ϵ (JO(Ht)≥1-ϵ), respectively, for a small tolerance parameter ϵ>0 which is set to 0.05 and for a sampling parameter H set to 1000. A relatively large value of ΓJI (ΓJO) is indicative of longer convergence times and therefore adverse impact on short-term intrasection fairness for inner (outer) section users. On the other hand, a relatively large value of ΓJ is indicative of short-term intercell unfairness. The steady-state throughput T and three fairness metrics ΓJ, ΓJI, and ΓJO (average values obtained over the 20 simulation instances) are tabulated in Table 3 for various choices of α and β.Table 3
The average throughputT and the average of three fairness metrics ΓJ, ΓJI, and ΓJO for various values of α and β for the 9-cell CN.
α β T (Mbps) Γ J Γ J I Γ J O 0.1 125.4 1.00 1.40 2.60 0.1 0.01 125.5 5.10 1.05 3.00 0.001 125.8 45.35 1.00 8.00  0.1 126.4 1.05 11.45 20.05 0.01 0.01 126.5 4.90 9.85 20.55 0.001 126.9 45.35 4.35 25.60  0.1 126.9 1.15 111.40 195.90 0.001 0.01 127.1 6.25 110.00 196.50 0.001 127.4 44.05 94.35 201.00We observe from Table3 that the particular choice of the algorithm parameters α and β has only a slight impact on the overall throughout with slight improvement in T with lower choices of α and β. On the other hand, when α and β are decreased, as a penalty, the various fairness indices of interest converge in a slower manner and short-term intercell and intrasection fairness measures are consequently compromised. In particular, while ΓJ is more sensitive to the change of β, ΓJI and ΓJO appear to more sensitive to the change of α. Similar observations are made in other scenarios as well but are not reported in the current manuscript. As a trade-off between short-term intercell and intrasection fairness and total network throughput, we fix α=β=0.01 in the remaining numerical examples.


## 4.2. Comparison of Opportunistic FFR versus Benchmark FFR

The use of the pattern set EPS-3 with the proposed opportunistic scheduler based on IS-PTF is referred to as opportunistic FFR (OFFR) in this paper. In this example, OFFR uses the IS-PTF formulation with a certain choice of the parameterd introduced in (9). In particular, we first study three different values of the parameter d, namely, d=1/4,1,4, and consequently use the per-pattern weights as given in (9). The benchmark system called benchmark FFR (BFFR) splits the BW into four subbands, the bandwidth of each subband being proportional to wm for m∈{1,2,3,4} based on identity (9). The intracell scheduler of BFFR is the same as that of the OFFR. Besides, we note that there is no NLS in BFFR and ICI is handled by static spectrum partitioning as described above. For each value of d, we simulated BFFR and OFFR in both 9-cell and 37-cell CNs for a total of 400 instances each of which spans 106 time slots. In each of these simulations, the number of users N is set to 64 and the users are randomly spread over the CN. Let TOFFR and TBFFR denote the overall network throughput when we employ OFFR and BFFR, respectively. Also, let Ti,jI,OFFR and Ti,jI,BFFR denote the average throughput of user Ui,jI when we employ OFFR and BFFR, respectively. Similarly, let Ti,jO,OFFR and Ti,jO,BFFR denote the average throughput of user Ui,jO when OFFR and BFFR, respectively, are employed. Furthermore, let(20)G=TOFFR-TBFFRTBFFR100%denote the network throughput percentage gain of OFFR over BFFR. Similarly, let (21)Gi,jI=Ti,jI,OFFR-Ti,jI,BFFRTi,jI,BFFR100%,Gi,jO=Ti,jO,OFFR-Ti,jO,BFFRTi,jO,BFFR100%denote the user throughput percentage gain of OFFR over BFFR for users Ui,jI and Ui,jO, respectively. Figures 7(a) and 7(b) illustrate the empirical Cumulative Distribution Function (CDF) of the gains Gi,jI and Gi,jO for the specific case of N=64 for 9-cell and 37-cell CNs, respectively.Figure 7
Empirical CDF of the users throughput gainsGi,jI and Gi,jO for N=64 for three different values of d in 9-cell and 37-cell networks.
(a)
9-cell scenario (b)
37-cell scenarioWe first note that as the parameterd decreases, the patterns including outer sections are scheduled more frequently in OFFR and a wider frequency band is assigned to outer section users in BFFR. We have the following observations from Figures 7(a) and 7(b):(i)
In all studied cases, a large majority of users benefited from OFFR, that is, positive gains, in comparison with BFFR. This situation is more apparent in the 37-cell scenario. These positive gains stem from network-wide opportunistic scheduling in OFFR as opposed to conventional single-cell scheduling along with static spectrum partitioning in BFFR.(ii)
We also observe that whend increases (decreases), outer (inner) section users gain substantially more with OFFR against BFFR.We further extend this example by varyingN∈{32,64,128} and the parameter d∈{1/4,1,4} and simulate the same scenario. Let G, GI, and GO denote the empirical expected values of the quantities G, Gi,jI, and Gi,jO, respectively, out of the 400 simulation instances. Also, let P, PI, and PO denote the percentage fraction of samples of G, Gi,jI, and Gi,jO, respectively, which are below zero, that is, those scenarios or users who do not benefit from OFFR. Table 4 provides the quantities G, GI, GO, PI, and PO, for varying choices of d and N. We note that the quantity P is found to be zero for all studied cases; that is, all networks benefited from OFFR in comparison with BFFR in terms of average throughput. Our further findings are as follows:(i)
As the number of users in the network increases, the average gain obtained with OFFR decreases and moreover the fraction of users that do not benefit from OFFR also increases with increasedN. The OFFR gain becomes more substantial when the number of users in the network is relatively smaller. This observation can be explained by the fact that when there is just one user or few users within a cell (which happens when the overall number of users is small), opportunistic scheduling within a cell as in BFFR is not as effective. In such scenarios, network-wide opportunistic scheduling helps the network users significantly.(ii)
The OFFR average gains are slightly more substantial in the 37-cell network than the 9-cell network.(iii)
Only a relatively small fraction of users appeared to fail to gain with OFFR. This quantity is observed to diminish significantly in the particular 37-cell network scenario. For example, in the worst case, for the 37-cell network scenario, only 6.8% (1.1%) of the outer (inner) users failed to gain with OFFR ford=1/4 (d=1) out of all the studies we have performed.Table 4
The comparative results associated with OFFR and BFFR when the system parametersd and N are varied.
Scenario d N G G I G O P I P O 32 24.5 32.6 16.8 0 0.5 1 / 4 64 16.6 21.1 10.6 0.2 2.0 128 11.1 14.7 6.5 0.5 6.8 32 24.1 20.6 19.0 0 0.4 37-cell 1 64 16.2 13.7 11.9 0.3 2.1 128 10.9 8.8 7.2 1.1 6.7 32 19.8 10.5 23.5 0 0.4 4 64 12.7 7.0 14.5 0.1 1.9 128 8.0 4.6 8.9 0.6 6.1  32 22.0 29.5 14.5 0.7 4.3 1 / 4 64 14.8 17.6 9.0 3.0 10.0 128 10.5 11.5 6.1 6.1 15.0 32 22.1 17.8 16.1 0.6 4.3 9-cell 1 64 14.5 10.5 9.8 4.4 10.0 128 9.9 6.5 6.7 9.4 14.5 32 16.4 9.4 19.8 0.5 4.4 4 64 10.3 5.8 12.3 3.1 8.9 128 6.5 3.4 8.3 9.1 12.1


## 4.3. Impact of GPS Selection for the MMTF Formulation

In this section, we study the impact of the choice of the underlying pattern set in the context of MMTF problem (10). The performance metric is taken as the minimum of the temporal shares of all the users served in the CN (z in (10)). Recall that MMTF attempts to maximize this quantity through the linear program given in Section 3.2 through which we obtain the per-pattern weights for this numerical example and consequently the performance metric. For this purpose, given the CNs with K=6 or 9 cells depicted in Figure 5, 10K users are spread through the CN uniformly, leading to an average population of 10 users per cell. After locating 10K users in the CN, one section is selected at random and 10P,P∈{1,2,…,10} users are further introduced in this cell for the purpose of making the user distribution through the network more nonuniform. To quantify this nonuniformity, we introduce the parameter η=(1+P)/(K+P) which gives the expected number of users in the most crowded cell divided by the overall number of users in the network. The larger the parameter P or η is, the more nonuniform the user distribution becomes. Subsequently, each MMTF problem is solved 1000 times each of which is obtained by associating 10(K+P) users in the CN with the individual cells and their sections. The average of the 1000 instances is then reported. We first study the 9-cell scenario given in Figure 5(a). We study the following pattern sets in the simulation study (the individual patterns are defined in Table 1):(i)
GPS1 = {P1,P2,P3,P4,P5,P8,P11,P15,P22,P29}(ii)
GPS2 = GPS1∪P24,P36(iii)
GPS3 = GPS2∪P6,P10,P17,P19,P21(iv)
GPS4: pattern set obtained by Algorithm 1 with cardinality 22 which is presented in Table 1(v)
EPS-3(vi)
UPS presented in Table1.Figure8 depicts the performance of the six pattern sets of choice mentioned above in terms of the minimum temporal share as a function of the nonuniformity parameter η. As η increases, the minimum temporal share decreases for all the employed pattern sets. This observation stems from the fact that an increase in η implies that one of the sections gets more crowded and consequently the users in that section get less chance to be scheduled. UPS outperforms all the other pattern sets for all values of η. This is because UPS includes every possible pattern which leads to the largest possible feasible set for problem (10). We remark that that the performance of UPS is an upper-bound for any GPS since every GPS is a subset of UPS according to Section 2.2. On the other hand, the performance of GPS4, obtained by Algorithm 1, is only slightly below that of UPS while the computational load required by Algorithm 1 to construct GPS4 is remarkably lower than that of ES. This implies that the patterns generated by Algorithm 1 can be used along with MMTF scheduler to manage nonuniform user distribution well. Furthermore, we observe that GPS3 outperforms GPS2 which in turn outperforms GPS1. This is because GPS1⊂GPS2⊂GPS3. Therefore, we conclude that adding more patterns to an employed pattern set consistently enhances the performance of the MMTF scheduler as expected. Similar conclusions are drawn for the 6-cell scenario for which we comparatively study four pattern sets, namely, EPS-3, UPS, GPS1 = {P1,P2,P3,P4,P5,P6,P7,P8}, and GPS2 being the GPS obtained by Algorithm 1 where the patterns are illustrated in Table 2. Figure 9 illustrates the performance of these four pattern sets. We conclude that pattern set selection and/or its cardinality are crucial for MMTF schedulers especially for CNs with larger number of cells.Figure 8
Performance of various pattern sets in the 9-cell scenario as a function of the nonuniformity parameterη.Figure 9
Performance of various pattern sets in the 6-cell scenario as a function of the nonuniformity parameterη.


## 4.4. Performance of the Proposed Scheduler in Nonhomogeneously Populated Networks

In this example, we use Zipf-distributed user populations in the multicell CN for nonuniform traffic demands [46]. The Zipf distribution has been successfully used in modeling various behaviors in computing and communications systems [46, 47]. Particular to traffic demand distribution in wireless networks, [48] uses a Zipf distribution to model traffic demands across multiple access points in an enterprise wireless LAN. The work in [49] studies a wireless network with heterogeneous clusters in which the cluster population sizes are distributed according to a Zipf distribution. In order to describe the Zipf distribution based on [46], let K be the number of elements and k∈{1,2,…,K} be the rank of an element. Let s denote the parameter characterizing the Zipf distribution. A given entity is an element of rank k with probability c/ks,s≥0 where c is a normalization constant. When K→∞, the parameter s should satisfy s>1. When K is finite and s=0, we have a discrete uniform distribution. When the parameter s is increased, the population of the individual elements in the entire population becomes more nonuniform.In this example, we will study the impact of the parameters if a selected user n∈1,2,…,N resides in a cell k∈1,2,…,K according to a Zipf distribution with parameters K and s. We fix K=9 and we distribute N∈32,64,128 users in the 9-cell CN according to a Zipf distribution with parameter s∈0,0.5,1,1.5,2. The ranks of cells in the 9-cell network are depicted in Figure 5(a). The user location within a cell is uniformly random. For each value of N, we distribute the users in the CN as described above and subsequently run the two-level scheduler using the MMTF formulation with GPS4 in Section 4.3 with 22 patterns. We also run the scheduler using IS-PTF with EPS-3 and d=1 as a benchmark. For each pair of s and N, we run the experiment 100 times each with a duration of 106 time slots. We obtain the minimum user temporal share and minimum and average user throughput for each instance using MMTF and IS-PTF schedulers and take the averages of these individual values over all the 100 simulated instances for a given pair (N,s). Table 5 illustrates the minimum user temporal share (denoted by amin), the minimum user throughput (denoted by Tmin), and the average user throughput (denoted by Tavg) for both MMTF and IS-PTF schedulers as a function of s and N. In general, we observe that the MMTF scheduler leads to higher minimum user throughput than IS-PTF. This is not surprising since MMTF is guaranteed to maximize minimum temporal share according to (10). Also, when N increases, the minimum user throughput and temporal share decrease for both schedulers because increasing N leads to less chance for the users to be scheduled. Furthermore, when s increases, the performance of the MMTF scheduler gets better relative to the IS-PTF scheduler in terms of Tmin and amin. This is because the user distribution is more nonuniform for larger values of s and MMTF scheduler takes into account the number of users in different sections of the network while IS-PTF does not. Therefore, we conclude that the MMTF scheduler becomes more effective in nonhomogeneously populated cellular networks if the performance metric is to be taken as the minimum user throughput or temporal share. We also observe that while the average user throughput is slightly larger with IS-PTF in most of the cases, the gap between IS-PTF and MMTF is small.Table 5
Minimum user temporal share, minimum network-wide user throughput (in kbps), and average network-wide user throughput (in Mbps) using MMTF and IS-PTF schedulers in the 9-cell CN.
s N a m i n M M T F a m i n I S - P T F T m i n M M T F T m i n I S - P T F T a v g M M T F T a v g I S - P T F 32 0.093 0.048 207.1 174.5 3.10 3.02 0 64 0.041 0.028 81.9 71.9 1.92 2.08 128 0.022 0.015 35.9 35.5 1.09 1.24  32 0.066 0.042 184.4 161.6 2.96 2.91 0.5 64 0.035 0.023 81.3 77.1 1.91 1.96 128 0.018 0.012 30.2 30.1 1.17 1.22  32 0.052 0.029 180.5 149.1 2.81 2.73 1 64 0.027 0.015 69.3 55.3 1.77 1.78 128 0.013 0.007 27.4 24.1 1.14 1.15  32 0.043 0.019 131.5 85.9 2.27 2.24 1.5 64 0.022 0.010 54.5 39.2 1.58 1.60 128 0.011 0.005 21.2 16.3 0.95 0.97  32 0.038 0.016 130.4 78.7 2.02 1.95 2 64 0.019 0.007 51.3 31.9 1.27 1.30 128 0.009 0.004 19.9 11.7 0.81 0.84


## 4.5. Transient Behavior of the Proposed Scheduler

In this example, we study the transient behavior of the proposed two-level scheduler in the 9-cell CN considering the two different fairness criteria, namely, IS-PTF and MMTF. For the MMTF criterion, we obtain pattern weights by solving problem (10) while employing the GPS constructed by Algorithm 1 with n=3. For the IS-PTF criterion, we consider the pattern set EPS-3 and use (9) with the proportionality parameter d set to unity. At time τ=0, we distribute 3 and 9 users in each inner and outer section of the 9-cell CN, respectively, at uniformly random locations within the cells. Subsequently, we run the proposed two-level scheduler using the pattern weights obtained based on the corresponding fairness criterion. At time slot τ1=4×105, we add 3 and 9 more users to I5 and O5, respectively, and update the per-pattern weights. At time slot τ2=8×105, we remove these users back from the network and update back the per-pattern weights. Figures 10(a) and 10(b) illustrate the sampled cumulative temporal share of a randomly selected user in O5 with sampling rate of H=0.1 (one sample per ten slots) as a function of time, for the IS-PTF and MMTF scenarios, respectively. We observe that the proposed scheduler converges with the employed parameters as time evolves for any of the three time intervals (before the next per-pattern weight updates take place). Figures 11(a) and 11(b) depict the sampled average throughput of the same user as a function of time for the IS-PTF and MMTF criteria, respectively. We observe that the steady-state throughput of the selected user is higher in each interval with the MMTF criterion in place, compared with IS-PTF. This is because MMTF considers the number of users in different cells while IS-PTF does not.Figure 10
Transient behavior of the temporal share associated with a randomly chosen outer section user in cell 5 for (a) IS-PTF and (b) MMTF.
(a)
Cumulative temporal share of an outer user in cell 5 using IS-PTF criterion with respect to time (b)
Cumulative temporal share of an outer user in cell 5 using MMTF criterion with respect to timeFigure 11
Transient behavior of the throughput associated with a randomly chosen outer section user in cell 5 for (a) IS-PTF and (b) MMTF.
(a)
Throughput of an outer user in cell 5 using IS-PTF criterion with respect to time (b)
Throughput of an outer user in cell 5 using MMTF criterion with respect to time


## 5. Conclusions

We have proposed a semicentralized joint cell muting and user scheduling scheme for interference coordination in a multicell network under two temporal fairness criteria, namely, IS-PTF and MMTF. We have also proposed a novel cell muting pattern set construction algorithm required for this joint scheme. For the IS-PTF criterion, we have shown that the proposed scheme, OFFR, outperforms the benchmark FFR system in in terms of network and users’ average throughput. On the other hand, the MMTF criterion allows one to perform dynamic load balancing with reasonable computational complexity. Furthermore, it has been shown that the general pattern set and its cardinality play a major role in the performance of the network-wide worst case user temporal share which is the performance metric we have used in this paper. For various cellular topologies and scenarios, we have shown that the pattern set we use by the proposed construction algorithm performs almost as well as using all possible patterns. Future work will consist of extending the methodology to more realistic OFDMA-based LTE networks and heterogeneous networks as well as incorporation of alternative fairness criteria and dynamic traffic models.



---

*Source: 4846291-2018-03-14.xml*