Fairness-Aware Scheduling for Millimeter Wave Backhaul Networks

Abstract

Millimeter wave (mmWave) backhaul networks are emerging as a promising candidate for the 5G mobile network. By exploiting highly directional antennas, the concurrent transmission technology which can greatly improve the network throughput is enabled in the mmWave backhaul communication. However, the existing concurrent transmission scheduling scheme ignores fairness, leading to the situation that some links in good state are always dispatched while some in poor state suffering starvation. In this paper we propose a Fairness-aware Global Scheduling (FAGS) algorithm in which a utility function and a scheduling threshold are designed to maximize the system throughput with the fairness requirements satisfied. And to quantify the impact of the scheduling algorithm on fairness a Jain Index is proposed. Simulations conducted in the 60 GHz band demonstrate the superior performance of our algorithm compared with other existing schemes.

1 Introduction

The next generation ubiquitous and ultra-high bandwidth communication system, known as 5G, is planned to support up to 1000-fold increase in wireless data traffic within the next 20 years [1]. The trend for dense deployment in future 5G mobile communication networks makes current wired backhaul infeasible owing to the high cost. Millimeter wave backhaul communication, a promising technique with the capability of providing a multi-gigabit transmission rate, offers a flexible and cost-effective candidate for 5G communication system.

However, one fundamental distinguishing feature of mmWave communications is the high propagation loss. A directional antenna with high directivity gains which allows more efficient concurrent transmissions is utilized to combat the severe path loss. Although concurrent transmission is an effective method to enlarge throughput in the backhaul network, serious unfairness may arise because some links get more opportunities to be concurrently transmitted than others. In a scenario where lots of available links are densely deployed, an effective and fairness-aware backhaul scheduling schemes needs to be designed.

The scheduling schemes of the backhaul network have been investigated in the literature [2,3,4]. The Exclusive Region (ER) based scheduling algorithm is proposed and derived in [5]. It makes sure that concurrent transmissions always outperform the serial TDMA (Time Division Multiple Access) by co-scheduling flows in the exclusive region. A concurrent transmission scheduling algorithm is introduced in [6] with rate adaptation, however, it does not consider the unique features of mmWave systems, such as high propagation loss and the use of directional antenna. In [7] multiple communication links are scheduled in the same time slot if the interference in this slot is below a specific threshold. In [8] the STDMA (Space/Time Division Multiple Access) algorithm takes full use of the concurrent transmission to achieve as much throughput as possible, but the fairness is ignored. To the best of our knowledge, none of the previous works are devoted to address the balance between the fairness requirement and the throughput between links in the mmWave backhaul network. And there are two aspects of challenges for the scheduling problem. In the first aspect, concurrent transmissions need to be fully exploited to maximize the system throughput. In the second aspect, the scheduling scheme should guarantee the fairness for links in the backhaul network.

In this paper we propose a heuristic algorithm for the mmWave backhaul network to achieve a good compromise between throughput and fairness. The main contribution of the paper is three-fold. First, we formulate the problem of optimal scheduling in the mmWave backhaul network as a nonlinear integer programming. Concurrent transmission is fully taken into account in this problem. Second, a heuristic scheduling algorithm, namely, the fairness-aware global scheduling (FAGS) is proposed to solve the formulated problem with low complexity. In the algorithm a utility function is defined to select the suitable links and a scheduling threshold is designed to eliminating the unfairness between links. Besides, a Jain Index is proposed to indicate the fairness level. Finally, simulation results of the FAGS algorithm in the 60 GHz band are presented in the end of the paper.

The rest of this paper is organized as follows. Section 2 gives an overview of the system model and assumption. Section 3 presents the problem formulation and analysis. The FAGS algorithm is described in Sect. 4. Section 5 gives the simulation and analysis of our scheduling scheme, followed by concluding remarks in Sect. 6.

2 System Model and Assumption

2.1 Single-Hop Link Scheduling

A typical mmWave backhaul network is shown in Fig. 1, where the small cells BSs are densely disposed. Mobile users are related with base stations (BSs) of the small cells, and BSs are connected by mesh backhaul network in the mmWave band. There are one or more BSs connected to the core network via the microcells, which are called gateways. Besides, there is a backhaul network controller (BNC) residing on one of the gateways.

Fig. 1.

The mmWave backhaul network for the small cells densely deployed

In the backhaul network, an end-to-end flow may go through multiple hops with a proper routing protocol in place. Once the routing path is fixed, all the single-hop links along the path will share the same constraint as the end-to-end flow. For this reason, the scheduling can only concentrate on the single-hop links, and the designing of routing protocol will be left for our future work. In this paper, considering there is a proper routing strategy in place, the only problem to be solved is the single-hop link scheduling scheme.

Fig. 2.

The superframe structure for mmWave backhaul network

2.2 Frame Architecture

In the backhaul network, time is partitioned into superframes [9], each of which is further divided into a beacon period (BP) and a channel time allocation period (CTAP), as shown in Fig. 2. The beacon period is controlled by the backhaul network controller to provide timing and global information, meanwhile broadcasting scheduling decision for the CTAP. The channel time allocation period is used for data transmission among BSs in a peer-to-peer fashion. There are at most M channel time slots in CTAP of each superframe. The BNC can arrange the length of CTAP adaptively according to the total occupied number of time slots if it does not outpace M.

2.3 Physical Model

Since non-line-of-sight (NLOS) transmissions in 60 GHz channels suffer from significant attenuation and a shortage of multipath [10], mmWave backhaul networks mainly rely on line-of-sight (LOS) propagation to achieve high data rate. It’s assumed that there are N flows requesting transmission time slots in the superframe, and each flow represents one backhaul link. For flow i, its sender and receiver is denoted by $s_i$ and $r_i$, respectively. And the distance between the sender $s_i$ and the receiver $r_j$ is $l_{ij}$. The antenna gain of $s_i$ in the direction of $s_i \rightarrow r_j$ is indicated by $A_t(i,j)$, in the same way, the antenna gain of $r_i$ in the direction of $s_j \rightarrow r_i$ by $A_r(j,i)$. Then considering the path loss and signal dispersion over distance, the received power at $r_i$ from $s_i$ can be calculated as [11]

$$\begin{aligned} \ P_r(i,i) = {k_0}A_t(i,i)A_r(i,i)l_{ii}^{-n}P_t \end{aligned}$$

(1)

where $k_0$ is a constant coefficient and proportional to $(\frac{\lambda }{4\pi })^{\small 2}$($\lambda$ denotes the wavelength), n denotes the path loss exponent, and $P_t$ denotes the transmission power. Considering the simultaneous transmission of multiple links in the system, the received interference at $r_i$ from $s_j$ can be calculated as

$$\begin{aligned} \ P_r(j,i) = \rho {k_0}A_t(j,i)A_r(j,i)l_{ji}^{-n}P_t \end{aligned}$$

(2)

where $\rho$ is the multi-user interference (MUI) factor related to the cross correlation of signals from different flows [12]. According to the Shannon’s channel capacity, the achievable data rate of flow i can be estimated as

$$\begin{aligned} \ R_i = {\eta }Wlog_2{(1+\frac{P_r(i,i)}{{N_0}W+\sum \limits _{j \ne i}P_r(j,i)})} \end{aligned}$$

(3)

where $\eta \in (0,1)$ describes the efficiency of the transceiver design, W is the bandwidth, and $N_0$ is the one sided power spectral density of white Gaussian noise.

3 Problem Formulation and Analysis

It’s assumed that there are N flows in the M time slots. For the time slot $m\in \{1,\ldots ,M\}$, $\mathbf{{R}}^m =\{R^m_1,\ldots ,R^m_N\}$ denotes the transmission rate vector, and ${\varvec{\alpha }}^m=\{\alpha ^m_1,\ldots ,\alpha ^m_n,\ldots ,\alpha ^m_N\}\in \{0,1\}^N$ indicates the link status (“1” means that the link is active, and “0” means that the link keeps silent). Thus, the optimization problem can be formulated to maximize the system throughput.

$$\begin{aligned} \begin{aligned} {\mathop {\text {Maximize}}\limits _{\{{\alpha _1^m},\ldots {\alpha _n^m},\ldots {\alpha _N^m}\}}} \sum \limits _{m = 1}^M {\sum \limits _{n = 1}^N{R_n^m\cdot t_{slot}/(T_{\small {BP}}+M\cdot t_{slot})}} \\ \mathrm{where} \, R_n^m={\alpha }_n^m\cdot \eta Wlog_2(1+\frac{P_r(n,n)}{{N_0}W+\sum \limits _{j \ne n}{\alpha }_j^mP_r(j,n)}) \end{aligned} \end{aligned}$$

(4)

$R_n^m$ represents the transmission rate of link n in the time slot m, $t_{slot}$ is the time duration of each time slot for CTAP period, and $T_{BP}$ is the time duration for beacon period.

The complexity of solving this optimization problem is extremely high. In addition, at the optimal point, only a few links achieve high throughput while others will be starved to death. Therefore, a fairness-aware suboptimal solution algorithm is raised to realize the compromise between link fairness and system throughput, beginning with a utility function definition.

3.1 Utility Function

We assume $\varOmega$ is the set of links that are being scheduled at the present time. A utility function is put forward to determine whether link i can join the current set. When flow i is chosen into the set, the gain obtained by flow i is expressed as its transmission rate, calculated by

$$\begin{aligned} G_i = \eta Wlog_2(1+\frac{P_r(i,i)}{N_0W+\sum \limits _{j\in \varOmega }{P_r(j,i)}}) \end{aligned}$$

(5)

At the same time, the cost (due to the increased interference from flow i to flow $k\in \varOmega$) is illustrated as the reduced transmission rate for flow k, given by

$$\begin{aligned} \begin{aligned} G_{ik}&= \eta Wlog_2(1+\frac{P_r(k,k)}{N_0W+\sum \limits _{j\in \varOmega ,j\ne k}{P_r(j,k)}})\\&-\eta Wlog_2(1+\frac{P_r(k,k)}{N_0W+\sum \limits _{j\in \varOmega ,j\ne k}{P_r(j,k)}+P_r(i,k)}) \end{aligned} \end{aligned}$$

(6)

Thus, a utility function is designed to represent the “system gain” for flow i:

$$\begin{aligned} U_i = G_i-\sum \limits _{k\in \varOmega }{G_{ik}} \end{aligned}$$

(7)

If $U_i>0$, that means flow i will bring a positive transmission rate gain to the network and can be scheduled in the present time slot; otherwise, it should be silent. For each scheduling time slot, the link with the positive value of utility function will be chosen. In this way, the system throughput can be the maximal but it is easy to cause unfairness among the links. Thus, a fairness weight factor is presented to ensure fairness among the links.

3.2 Fairness Weight Factor

For the mmWave backhaul network, it’s very challenging to achieve fairness. First, the notion of fairness is quite different from that in traditional networks, where fairness can be defined for a specific link with a fixed capacity. In a mmWave backhaul network, the links interfere with each other. The direct or indirect interfering relationship among links determines that the fairness in mmWave backhaul network should have a global definition instead of being limited to a specific link. Second, spatial reuse may conflict with fairness. Hence, a feasible tradeoff between throughput and fairness should be considered. The well-known proportional fair scheduling [13, 14] obtains a good compromise between throughput and fairness for code-division multiple access (CDMA) cellular systems. For each time slot, the scheduler schedules the link with the highest priority value defined as the ratio of the signal-to-interference-plus-noise ratio (SINR) to the average throughput. If a link has a low average throughput, its chance to be selected to transmit is relatively large, so as to achieve a certain level of fairness.

Based on the proportional fair scheduling, a fairness weight factor is introduced for mmWave backhaul network to ensure the fairness of scheduling. The basic idea is that links in good condition¹ are given priority while those in bad condition can get an acceptable scheduling share. Specifically, the fairness weight factor is written as

$$\begin{aligned} \omega _i(t)=\frac{\mu _i}{T_i(t-1)+\gamma },t=1,\ldots ,M \end{aligned}$$

(8)

where $\mu _i$ is the pre-specified service priority factor of link i, $T_i(t-1)$ represents the throughput of the link i obtained from the first $t-1$ time slots and $\gamma$ is a constant to balance the throughput. $T_i(t-1)$ is written as

$$\begin{aligned} T_i(t-1)=\frac{\sum \limits _{m=1}^{t-1}{R_i^m\cdot t_{slot}}}{T_{\small {BP}}+(t-1)\cdot t_{slot}} \end{aligned}$$

(9)

Specially, $T_i(0)=0(t=1)$ meaning that the throughput of each link is zero before the first time slot. Then the utility function is modified based on the fairness weight factor. The modified utility function is

$$\begin{aligned} U_i^t=\omega _i(t)G_i-\sum \limits _{k\in \varOmega }{\omega _i(t)G_{ik}},t=1,\ldots ,M \end{aligned}$$

(10)

The modified utility function gives the link selection criteria at the time slot t directly. From Eq. (8) and (10) it can be seen that if the link state of link i is better, then the number of times it may be scheduled in a short time is relatively large. So link i can get relatively high throughput. However, if the throughput is too large, the value of the utility function will be reduced under the fairness weight factor. Thus, each flow can get a fairness-aware scheduling.

3.3 Jain Index

For mmWave backhaul networks, a fair resource allocation is not necessarily the case when each link receives the same throughput and service level. Consider a network with 3 links, where links 1 and 2 are close to each other while link 3 is far away from them. Links 1 and 2 generate large interference to each other. Hence, it’s not appropriate to allow them transmitting simultaneously i.e. the probability that link 1 and link 2 are scheduled at the current time is 50%. As there is no interference link in link 3’s neighborhood, it is better to allow link 3 to be active at the present time. This simple example shows that, to evaluate fairness, the link condition should be taken into account. However, it is challenging to evaluate the link condition in the mmWave backhaul network. It should be determined by its path loss and the interference level. Here we use a heuristic approach. To begin with, a function that measures the link condition is given as

$$\begin{aligned} \nu _i=\frac{1}{1+S(I_i)} \end{aligned}$$

(11)

where $S(I_i)$ is the size of relative interference set for link i. And the relative interference set of link i is expressed as $RI_i$.

$$\begin{aligned} RI_i=\{j|j\ne i,\text {max}{\{\frac{P_r(j,i)}{P_r(i,i)},\frac{P_r(i,j)}{P_r(j,j)}\}}>\sigma \} \end{aligned}$$

(12)

where $\sigma$ is the interference threshold to measure relative interference between link i and j. From (11) and (12) it can be seen that if link i is less interfered by other links, a larger value for $\nu _i$ can be obtained,otherwise, the value is small. In this way, the link condition can be judged by the value of $\nu _i$.

On the performance analysis of the scheduling algorithm in Sect. 5, fairness is a very important indicator. The impact of scheduling strategy on the system fairness needs to be quantified. Based on the link condition function, $\text {Jain Index}$ is proposed for evaluating the fairness and is defined as follows

$$\begin{aligned} \text {Jain Index} = \frac{(\sum _{i=1}^{N}{\frac{T_{i,total}}{\mu _i\nu _i}})^2}{N\cdot \sum _{i=1}^{N}{({\frac{T_{i,total}}{\mu _i\nu _i}})^2}} \end{aligned}$$

(13)

where $T_{i,total}$ represents the total throughput achieved by link i during the whole scheduling time. And we have

$$\begin{aligned} T_{i,total}=\frac{\sum \limits _{m=1}^{M}{R_i^m\cdot t_{slot}}}{T_{\small {BP}}+M\cdot t_{slot}} \end{aligned}$$

(14)

In the definition of Jain Index, the greater of the Jain Index value is, the more fairness of the allocation scheme achieves. If $\text {Jain Index} = 1$, the scheduling scheme is perfectly fair, that is, each component is exactly equal.

4 Scheduling Algorithm Design

In this section, we propose the fairness-aware global scheduling (FAGS) algorithm. The algorithm combines the utility function defined in Sect. 3 and a scheduling threshold given in the following to put forward a suitable scheme.

4.1 Scheduling Threshold

In order to further ensure the fairness among links, a scheduling threshold for the scheduled times of each link is proposed as follows

$$\begin{aligned} TH_{schedule}=\imath \cdot M \end{aligned}$$

(15)

where $\imath$ is the scheduling threshold factor, namely, a constant coefficient to adjust the value of $TH_{schedule}$ which represents the maximum scheduled times for each link. The threshold value $TH_{schedule}$ is used to assure link i will not be selected too frequently. We use Ca(i) to record the number of times that link i was scheduled. If $Ca(i)>TH_{schedule}$, then link i can not be scheduled anymore. In addition, since $\imath$ determines the value of $TH_{schedule}$, the choice of the scheduling threshold factor $\imath$ has an important effect on system performance, which will be demonstrated in the simulation section.

4.2 Fairness-Aware Global Scheduling (FAGS) Algorithm

Combining the utility function and the scheduling threshold, we bring forward the FAGS algorithm. The scheduling algorithm starts in the first time slot and uses the utility function to select as many links as possible until all the links that meet the scheduling threshold conditions are traversed. And then the next time slot begins scheduling until the M time slots are completed. The decomposed method can solve the problem in a manner by reducing the searching space from $O(M^N)$ to $O(N\cdot M)$. For detail, the scheduling algorithm in each time slot can be concluded in three steps.

Step 1: Remove the links that do not meet the scheduling threshold. For link i, the number of scheduled times must be less than the scheduling threshold, namely, $Ca(i)<TH_{schedule}$. If this condition is not satisfied, the link can’t join into the current transmission set in the present time slot.

Step 2: Select the first scheduled link. The first link should not only have the largest value of utility function but also have never been scheduled in the past slots. This way of choice makes sure that the link in bad condition avoids suffering starvation and each link is properly scheduled.

Step 3: Chose the other links to take part in the present scheduling set in a greedy way. For each time we select the link with the largest value of utility function from the remaining links set and remove it from the set. The scheduling does not end until the utility function of the selected link is negative or the remaining links set is empty, then turning to the next time slot.

The pseudo-code of the fairness-aware global scheduling (FAGS) algorithm is presented in Algorithm 1. The initialization is completed by lines 1–3. The scheduling matrix $\mathbf B$ indicates whether the link i is scheduled in the m-th time slot and it’s initial value is $\mathbf 0$; The decision vector ${\varvec{\alpha }}_{\text {FAGS}}^m$ indicates which flows are scheduled in the k-th slot. A is the set of all links; $A^*$ is the set of links that meeting the scheduling threshold and is initialized to empty; $\varOmega$ is the set of links that hasn’t been scheduled and is initialized to all links. Line 4 ensures that the number of scheduling times can’t exceed the scheduling threshold. The first scheduled link is chosen by line 5–11. In line 12–20, we use the utility function to select as many links joining the current transmission set, in order to get a larger throughput. Line 21–23 updates the scheduling vector ${\varvec{\alpha }}_{\text {FAGS}}^m$ and scheduling matrix B, then the scheduling is completed.

5 Performance Evaluation

In this section, we evaluate the performance of the proposed scheduling algorithm in the 60 GHz band, and investigate the impact of the scheduling threshold factor on the performance of our scheme. Besides, we also compare the proposed scheduling algorithm with the existing schemes in terms of Jain Index and system throughput.

5.1 Simulation Setup

The simulation is conducted in a backhaul network with 10 base stations which has at most 90 flows. For the scheduling performance is dependent on the location of stations, the position for each BS is randomly generated within a square area of $100 \, \times 100 \, \text {m}^2$. Meanwhile, for every flow its source and destination is randomly chosen. And we use the channel model in Ref. [15] for the path loss. Besides, we adopt the widely used realistic directional antenna model in Ref. [16]. All the BSs in the system use the same transmission power level. Some other parameters are shown in Table 1.

Table 1. Simulation parameters

5.2 Choice of the Scheduling Threshold Factor

Since the choice of the scheduling threshold factor has an important impact on the performance of our scheme, we now investigate it under different typical number of flows, that is, $N=10,N=30,N=50,N=70$.

The system throughput of our scheme under different values of the scheduling threshold factor is displayed in Fig. 3. From the figure we can see that with the increase of the scheduling threshold factor, the system throughput increases significantly. In the cases $N=10,N=30,N=50,N=70$, the system throughputs are increased by 27%, 34%, 47%, 44% when $\tau$ changes from to 0.1 to 1. Owing to the improving of $\tau$, the value of $TH_{schedule}$ increases proportionally and the number of times for each link being scheduled are gradually increased. Thereby, the system throughput increases significantly. However, when the threshold is large enough, the main factor limiting the system throughput is the interference between the links. Thus, when $\tau$ is greater than 0.5, the system throughput increases slowly.

Fig. 3.

The system throughput under different scheduling threshold factors

Fig. 4.

The Jain Index under different scheduling threshold factors

In Fig. 4, we plot the Jain Index of our scheme under different values of the scheduling threshold factor. It can be seen that with the increase of the scheduling threshold factor, the value of Jain Index decreases. When the scheduling threshold factor is small, some of the links in good condition can’t be scheduled too frequency than other links, thus ensuring the fairness of the system; otherwise, the fairness reduces. In addition, when $\tau$ is in the range from 0.7 to 0.9, the slope of the curve becomes larger, significantly reducing the Jain Index.

Choosing the appropriate scheduling threshold factor is important for both the system throughput and fairness. According to the simulation results, when the threshold factor is controlled between [0.5–0.7], the fairness of the system can be guaranteed without losing the system throughput. And we will set $\tau =0.6$ in the following simulation.

5.3 Comparison with Other Schemes

In this case, we vary the number of flows in the backhaul network from 10 to 90. We adopted the serial TDMA scheme, and the MQIS scheme [11] for comparison. Under the increasing number of demanding flows, the system throughput and Jain Index of the proposed scheme are compared with the other two schemes and the results are shown in Figs. 5 and 6 correspondingly.

Fig. 5.

The system throughput under different number of links

It can be seen from Fig. 5 that the system throughput increases when the number of links becomes larger. And compared with the MQIS and TDMA algorithms, the FAGS algorithm has obvious advantages. When $N = 90$, the system throughput of FAGS algorithm is 3.28 times higher than that of TDMA algorithm and 57% higher than that of MQIS algorithm. Since the TDMA scheme doesn’t use the spatial multiplexing technology, the throughput curve is relatively gentle. The MQIS algorithm and the FAGS algorithm all utilize the spatial multiplexing technique, but after $N = 70$, the MQIS algorithm is no longer increased, and the latter continues to increase. In the MQIS algorithm, only those links in good state have completed the scheduling, the remaining links can begin to be scheduled, which resulting in some links can’t be timely scheduled. In this paper, the proposed FAGS algorithm is scheduled in each time slot, which ensuring as many links as possible obtaining timely scheduling. Thus, compared with the MQIS algorithm, the system throughput of our proposed FAGS algorithm increases greatly.

Fig. 6.

The Jain Index under different number of links

Figure 6 compares the Jain Index of the three algorithms under different number of links. Because of the absolute fairness, the Jain Index of the TDMA algorithm is always 1. The Jain Index of the FAGS algorithm decreases with the increase of N but gradually stabilized. And the Jain Index is always above 0.9. The MQIS algorithm decreases sharply with the increase of N, and the fairness is the worst. With the increase of interference between links, there are more links in the poor condition. The MQIS algorithm prefers the links with good condition, resulting in lower fairness. The FAGS algorithm makes use of the fairness weight factor to ensure that the links in different states being scheduled fairly. Thereby, the fairness is improved compared with the MQIS algorithm.

To summarize, the TDMA algorithm can guarantee the absolute fairness, but its system throughput is too small; the MQIS algorithm has high system throughput but the fairness is too low. The FAGS algorithm achieves the balance between throughput and fairness.

6 Conclusions

In this paper, we investigate the problem of maximizing the system throughput with the fairness requirements satisfied for the mmWave backhaul network of small cells densely deployed. We propose the Fairness-aware Global Scheduling (FAGS) algorithm in which a utility function and a scheduling threshold are designed for improving the system performance. To quantify the impact of scheduling algorithm on the fairness Jain Index is proposed. And the choice of the scheduling threshold factor is also analyzed to provide guidelines for parameter selection in practice. Extensive simulations demonstrate the superior performance of our algorithm in system throughput and fairness compared with the TDMA algorithm and the MQIS algorithm.