Network Utilization Improvement via a Predictive Load Scheduling Scheme in Heterogeneous Wireless Networks

Abstract

In heterogeneous wireless networks (HWNs), the large-coverage cellular networks are usually overlaid with denser small-coverage microcells, wireless local area networks (WLANs), femtocells, and even relays. To prevent unbalanced load distribution in these HWNs from decreasing network utilization and degrading the quality of service (QoS), load scheduling between the overlaid networks is essential and should be reasonably designed. In fact, unbalanced load distribution can be directly reflected by the idle durations of networks and channels. In this paper, a predictive load scheduling scheme is proposed from the point of decreasing the capacity-weighted idle durations of networks and channels. For the proposed scheme, a fairly general HWNs scenario is considered, the scheduling problem is formulated, an iteration-based predictive method is given to obtain the idle duration, and a gradient descent method is derived for the optimal scheduled load. In the simulation, the effectiveness of the idle duration prediction method is validated, and the simulation results show that the proposed load scheduling scheme can greatly improve the network utilization and QoS.

1. Introduction

The integration of heterogeneous wireless networks (HWNs) has become a promising trend to satisfy the fast increasing demand for higher wireless data rate and lower transmission delay. In HWNs, the small-coverage microcells, WLANs, femtocells, and even relays are deployed in hotspots to offload from the large-coverage cellular networks. In general, the deployment of small-coverage cells can increase the bandwidth reusability and global network capacity. Different from the traditional homogeneous cellular networks, the coverage of HWNs with different radio transmission techniques can be overlapped and user equipments (UEs) in the overlapped region can be served by different networks. So, how to reasonably distribute these UEs or their traffic to the overlapped HWNs for load balance is a key problem.

On the other hand, due to the time-variant traffic arrivals and the diversity of traffic classes, the unbalanced load distribution that some networks are overloaded while some other networks are underloaded may occur from time to time. Unbalanced load distribution leads to an irrational result, that under-loaded networks or some of their channels are in idle state when other networks cannot cope with their heavy traffic load and thus decreases the network utilization and degrades the QoS of UE. Therefore, in HWNs with overlapped coverage, when load unbalance occurs, re-distributing these UEs or traffic load in the overlapped regions through load scheduling may improve the load balance.

Meanwhile, with the development of multimode access terminals and multipath technic [1], the emerging mobile wireless terminal would be able to access several networks simultaneously. So a traffic stream in the multimode UE can be divided into several substreams that are transmitted through different networks. This potential traffic stream division method brings breakthrough in load scheduling, that through reasonably dividing traffic streams into substreams and finely distributing traffic data amount in these divided substreams, a more precise load scheduling can be obtained. This paper focuses on traffic streams scheduling and employs this stream division method to implement scheduling.

As an important aspect of load balancing, load scheduling has drawn keen interests of investigators, and its basic idea is to schedule some traffic load in the overlapped region from the overloaded networks to the underloaded network. These works on load scheduling can be divided into two classes: hard load scheduling [2–5] and soft load scheduling [6–9]. The hard load scheduling schedules the load in units of UEs or traffic streams while the soft scheduling schedules the load in units of substreams or packets by taking multipaths technic [1] into consideration. In the literature, many metrics such as load threshold [2], economic utilities [4, 7–9], balance factors [3], residual resource [5], interference level [6] have been developed to implement load scheduling.

Works in [2] give a hysteresis threshold based load scheduling scheme that the scheduling triggering and scheduled load is decided by the load thresholds. Works in [3] use a load balance factor that considers the global load distribution and UEs’ characteristics to implement load scheduling in HWNs and give a fuzzy logic method to decide which UE would be scheduled. Works in [4] define a utility function that considers load states and traffic types for load scheduling and give a Q-learning based method to obtain the scheduled traffic. Works in [5] schedule load based on the residual resources in different networks and give an Markov decision process based method to achieve scheduled load. Works in [6] use the interference level to deploy load scheduling and derive the scheduled load by solving the interference function. Works in [7, 8] formulate utility functions considering traffic load size and transmission rate, and achieve load balance by scheduling substreams. Works in [9] formulate a utility function that considers network capacity and residual resource and obtain the optimal scheduled load by a weighted bargaining game framework.

In this paper, we investigate the soft load scheduling in HWNs and propose a predictive scheduling scheme from the point of decreasing the capacity-weighted idle durations of networks and channels. Compared with the former works, our works have the following novelties and improvements.

• (i)

Our works consider a fairly general heterogeneous wireless network scenario where the number of networks and their positions are not fixed. Multipaths is considered and the loads that can be and cannot be scheduled between two overlapped networks are differentiated.

(ii)

Our works not only consider the current load distribution in the global networks but also consider the arriving traffic loads before the next scheduling. An iteration process based predictive method is proposed to predict the idle durations.

(iii)

Our works firstly formulate the objective of minimizing the capacity-weighted idle durations of networks and channels for scheduling and derive a gradient descent method to obtain the optimal solution.

2. Scenario and Problem Formulation

Consider a geographical region with a set, $\mathcal{N}=\{\mathrm{1,2},\dots ,N\}$ , of different available wireless base stations (BSs) and access points (APs), as shown in Figure 1. Each BS or AP has its unique coverage and may have overlapped coverage in some regions with other BS/AP. As a result, the geographical region is partitioned to a set, $\mathcal{K}=\{\mathrm{1,2},\dots ,K\}$ , of service regions. Each service region, $k\in \mathcal{K}$ , is covered by a unique subset of BSs/APs, as shown in Figure 1. The subset of available wireless BSs/APs at service region k is denoted by ${\mathcal{N}}_k$ , and the subset of service regions that are covered by BS/AP n is denoted by ${\mathcal{K}}_n$ . As shown in Figure 1, the coverage of BS 1 is divided into 5 service regions, so ${\mathcal{N}}_{\mathrm{1}}=\{\mathrm{1,2},\mathrm{3,4},\mathrm{5}\}$ , and the available wireless BSs/APs at service region 3 include BS 1 and AP 2, so ${\mathcal{K}}_{\mathrm{3}}=\{\mathrm{1,2}\}$ . It is assumed that all the BSs/APs are connected to a backbone to exchange their roaming signal information, and the proposed scheduling scheme relies on the roaming signal to exchange the traffic load state information and traffic load scheduling information.

Figure 1

The heterogeneous wireless networks coverage regions.

Hence, the traffic load that can be scheduled between two BSs is the unserved traffic load in the overlapped regions of the two BSs. The traffic load in each BS n, $n\in \mathcal{N}$ , can be divided into a set ${\mathcal{R}}_n=\{r_{n,k},\hspace{0.17em}\hspace{0.17em}k\in {\mathcal{K}}_n\}$ , of traffic loads in the regions of ${\mathcal{K}}_n$ , and $r_{n,k}$ denotes the traffic load of BS n in region k. The traffic load that would be scheduled from BS n to BS m in region k, which is denoted by $x_k^{n-m}$ , should be less than the traffic load of BS n in region k, that is $r_{n,k}$ , so

$$\begin{array}{cc}& \mathrm{0}\le x_k^{n-m}\le r_{n,k},\hspace{1em}k\in {\mathcal{K}}_n,\hspace{0.17em}\hspace{0.17em}k\in {\mathcal{K}}_m.\end{array}$$

(1)

And the total scheduled load from BS n in region k should be less than $r_{n,k}$ ; that is

$$\begin{array}{cc}& {\displaystyle \sum }_{m\in {\mathcal{N}}_k}{x}_k^{n-m}\le r_{n,k}.\end{array}$$

(2)

Denote the downlink transmission capacity of BS n as $C_n$ . So when BS n stays in idle state for a duration of t, the network utilization loss is $C_n·t$ , and when a channel of BS n stays in idle duration of t, the network utilization loss is $C_n{\gamma }_n·t$ , where ${\gamma }_n$ is the ratio of a channel capacity to the total capacity $C_n$ . For the network utilization loss, the idle duration t of a channel is equivalent to an idle duration ${\gamma }_n·t$ of BS n. Thus we only consider the idle durations of BSs in the following by assuming that all the idle durations of channels have been converted into BS idle durations.

An example of idle state durations and active state durations for BS n between two scheduling is shown in Figure 2. When the residual load equals 0, the BS n transfers to idle state, and when new traffic streams arrive, the BS n in idle state transfers to active state. The sum of idle durations in BS n between the current scheduling and the next scheduling is denoted by ${\mathcal{D}}_n(r_n,x_n,T)$ , where $r_n$ is the traffic load in BS n before the current scheduling, $r_n={\sum }_{r_{n,k}\in {\mathcal{R}}_n}^{}{r}_{n,k}$ , $x_n={\sum }_{m\in \mathcal{N},k\in {\mathcal{K}}_n}{x}_k^{m-n}-{\sum }_{m\in \mathcal{N},k\in {\mathcal{K}}_n}{x}_k^{n-m}$ , and T is the duration between the current scheduling and the next scheduling. The network utilization loss between the current scheduling and the next scheduling can be given as $h(\{r_{n,k}\},\{x_k^{n-m}\},T)={\sum }_{n\in \mathcal{N}}{C}_n{\mathcal{D}}_n(r_n,x_n,T)$ . Therefore, the load scheduling problem can be solved by solving the following problem:

$$\begin{array}{l}\underset{\left\{\right\{x_k^{n-m}\},n,m\in \mathcal{N},k\in \mathcal{K}\}}{\min }h\left(\left\{r_{n,k}\right\},\left\{x_k^{n-m}\right\},T\right)\\ \phantom{\text{llllllllll}}\text{s}.\text{t}.\phantom{\text{lllllllll}}\left(\mathrm{1}\right)\hspace{0.17em}\mathrm{0}\le x_k^{n-m}\le r_{n,k},\hspace{1em}k\in {\mathcal{K}}_n,\hspace{0.17em}\hspace{0.17em}k\in {\mathcal{K}}_m\\ \phantom{\text{llllllllllllllllllllllll}}\left(\mathrm{2}\right)\hspace{0.17em}{\displaystyle \sum }_{m\in {\mathcal{N}}_k}‍x_k^{n-m}\le r_{n,k}\\ \phantom{\text{llllllllllllllllllllllll}}\left(\mathrm{3}\right)\hspace{0.17em}{x}_k^{n-m}=\mathrm{0},\hspace{1em}k\notin {\mathcal{K}}_n\hspace{0.17em}\hspace{0.17em}\text{or}\hspace{0.17em}\hspace{0.17em}k\notin {\mathcal{K}}_m.\end{array}$$

(3)

Figure 2

An example of idle durations and active durations for BS n between two scheduling.

3. System Model

3.1. Networks Distribution

The HWNs may consist of a series of networks with different spectra, cell size levels, and radio transmission technics, such as cellular network, WLAN, WiMax, microcell, and femtocell. In this paper, a general scenario of HWNs is considered, as shown in Figure 1, that some networks may be regularly distributed while the other networks are distributed irregularly. The networks using different spectra can be overlapped, while networks using the same spectra can not be overlapped and the border is determined by the UE-side received power. So any region $k\in \mathcal{K}$ cannot be covered with two BSs using same spectra. The downlink capacity of each BS $n\in \mathcal{N}$ (denoted by $C_n$ ) is assumed to be constant.

3.2. Traffic Model

The traffic arrival in each BS $n\in \mathcal{N}$ from each region $k\in {\mathcal{K}}_n$ is assumed to be time-heterogeneous Poisson arrival with arrival rate of ${\lambda }_{n,k}(t)$ , where t denotes the time, so the traffic arrival rate in each region k is ${\lambda }_k(t)={\sum }_{n\in {\mathcal{N}}_k}{\lambda }_{n,k}(t)$ . Traffic data size are assumed to be negative exponential distributed with mean value $f_d$ , and its probability density function (PDF) is given by

$$\begin{array}{cc}& f\left(x\right)=\frac{\mathrm{1}}{f_d}·e^{-x/f_d}.\end{array}$$

(4)

3.3. Service Model

No bandwidth or channel reservation is considered for each network, and a process-sharing scheme in which all the admitted user equipments (UEs) equally share the available bandwidth is adopted by all the networks. That means all the bandwidth would be in use when the BS is in active state. Each UE is assumed to be equipped with multiple network interfaces so that can access all types of wireless networks. Multipaths technic [1] is considered for the UE that each UE can be admitted to one or more available networks simultaneously and the traffic in the UE can be divided into multiple substreams.

4. Predictive Method for Idle Duration

4.1. Idle Duration Division

Consider a BS having constant traffic arrival rate of λ at the period T, that is the duration between the current scheduling and next scheduling. And the BS has a traffic load of $L_{\mathrm{0}}$ after the current scheduling and has constant capacity of C. The expected sum of idle durations (denoted by D), of the considered BS at the period T can be given as

$$\begin{array}{cc}& D={\displaystyle \sum }_{i=\mathrm{0}}^{+\infty }‍D_i{P}_i,\end{array}$$

(5)

where $D_i$ denotes the average idle duration when i traffic streams arrive in the period T, and $P_i$ denotes the probability that i traffic streams arrive in the period T. According to the Poisson process, the expression of $P_i$ can be given as

$$\begin{array}{cc}& P_i=\frac{{\left(\lambda T\right)}^i}{i!}\exp (-\lambda T).\end{array}$$

(6)

Indeed, the average idle duration when no traffic stream arrives in the period T can be given by

$$\begin{array}{cc}& D_{\mathrm{0}}=T-\frac{L_{\mathrm{0}}}{C}.\end{array}$$

(7)

4.2. Idle Duration Expectation with One Traffic Stream

When one traffic stream arrives in the period T ( $i=\mathrm{1}$ ), the idle duration distribution in the period T is shown in Figure 3. In Figure 3, $t_a$ denotes the traffic stream arrival time, a denotes the data size of the arrived traffic stream. When $t_a\le L_{\mathrm{0}}/C$ , the idle duration distribution is shown in Figure 3(a), based on which the expectation of idle duration ( $D_{\mathrm{1}}$ ) can be derived as

$$\begin{array}{l}{D}_{\mathrm{1}}\left(\mathrm{0}\le t_a\le \frac{L_{\mathrm{0}}}{C}\right)\\ =\mathbb{E}\left[{\left[T-\frac{L_{\mathrm{0}}+a}{C}\right]}^{+}\hspace{0.17em}|\hspace{0.17em}\mathrm{0}\le t_a\le \frac{L_{\mathrm{0}}}{C}\right]\\ ={{\displaystyle \int }}_{\mathrm{0}}^{L_{\mathrm{0}}/C}{{\displaystyle \int }}_{\mathrm{0}}^{C·T-L_{\mathrm{0}}}\left(T-\frac{L_{\mathrm{0}}+a}{C}\right)\frac{\mathrm{1}}{f_d}\exp \left(-\frac{a}{f_d}\right)daf\left(t_a\right)d{t}_a\\ =\frac{L_{\mathrm{0}}}{CT}\left(T-\frac{L_{\mathrm{0}}}{C}-\frac{f_d}{C}+\frac{f_d}{C}\exp \left(\frac{L_{\mathrm{0}}-CT}{f_d}\right)\right),\end{array}$$

(8)

where $[x{]}^{+}$ equals x when $x>\mathrm{0}$ , equals $\mathrm{0}$ otherwise, $f(t_a)$ is the PDF of the arrival time $t_a$ and is given by the following referred to [10]

$$\begin{array}{cc}& f\left(t_a\right)=\left\{\begin{array}{cc}\frac{\mathrm{1}}{T},\hfill & \mathrm{0}\le t_a\le T,\hfill \\ \mathrm{0},\hfill & \text{else}.\hfill \end{array}\right.\end{array}$$

(9)

Figure 3

Two cases of idle duration distribution when one traffic stream arrives.

Besides, when $L_{\mathrm{0}}/C<t_a\le T$ holds, the idle duration distribution is shown Figure 3(b), based on which the idle duration expectation can be derived as

$$\begin{array}{l}{D}_{\mathrm{1}}\left(\frac{L_{\mathrm{0}}}{C}<t_a\le T\right)\\ \hspace{1em}=\mathbb{E}\left[\left(t_a-\frac{L_{\mathrm{0}}}{C}\right)+{\left[T-t_a-\frac{a}{C}\right]}^{+}\hspace{0.17em}|\hspace{0.17em}\frac{L_{\mathrm{0}}}{C}<t_a\le T\right]\\ \hspace{1em}={{\displaystyle \int }}_{L_{\mathrm{0}}/C}^T{{\displaystyle \int }}_{\mathrm{0}}^{C\left(T-t_a\right)}\begin{array}{l}\left(\left(t_a-\frac{L_{\mathrm{0}}}{C}\right)+\left(T-t_a-\frac{a}{C}\right)\right)\end{array}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}·\frac{\mathrm{1}}{f_d}\exp \left(-\frac{a}{f_d}\right)daf\left(t_a\right)d{t}_a\\ \hspace{1em}=\frac{\mathrm{1}}{T}\left(-\frac{\mathrm{2}{L}_{\mathrm{0}}}{C}T+\frac{L_{\mathrm{0}}^{\mathrm{2}}}{C^{\mathrm{2}}}+T^{\mathrm{2}}-\frac{f_d}{C}T+\frac{f_d{L}_{\mathrm{0}}}{C^{\mathrm{2}}}+\frac{f_d^{\mathrm{2}}}{C^{\mathrm{2}}}\right.\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\left.-\frac{f_d^{\mathrm{2}}}{C^{\mathrm{2}}}\exp \left(\frac{L_{\mathrm{0}}-CT}{f_d}\right)\right).\end{array}$$

(10)

Based on the expressions of $D_{\mathrm{1}}(\mathrm{0}\le t_a\le L_{\mathrm{0}}/C)$ and $D_{\mathrm{1}}(L_{\mathrm{0}}/C<t_a\le T)$ , the idle duration expectation of $D_{\mathrm{1}}$ is derived as

$$\begin{array}{l}{D}_{\mathrm{1}}\\ =D_{\mathrm{1}}\left(\mathrm{0}\le t_a\le \frac{L_{\mathrm{0}}}{C}\right)+D_{\mathrm{1}}\left(\frac{L_{\mathrm{0}}}{C}<t_a\le T\right)\\ =T-\frac{L_{\mathrm{0}}}{C}-\frac{f_d}{C}+\frac{f_d^{\mathrm{2}}}{C^{\mathrm{2}}T}+\left(\frac{f_d{L}_{\mathrm{0}}}{C^{\mathrm{2}}T}-\frac{f_d^{\mathrm{2}}}{C^{\mathrm{2}}T}\right)\exp \left(\frac{L_{\mathrm{0}}-CT}{f_d}\right).\end{array}$$

(11)

Based on (7) and (11), the following iteration expression for $D_{\mathrm{1}}$ could be obtained:

$$\begin{array}{l}{D}_{\mathrm{1}}\\ =D_{\mathrm{0}}-\frac{f_d}{C}\left[\frac{CT-f_d}{CT}+\frac{f_d-CT+C{D}_{\mathrm{0}}}{CT}\exp \left(-\frac{C{D}_{\mathrm{0}}}{f_d}\right)\right].\end{array}$$

(12)

4.3. The Two-Stage Predictive Method

Similar to the above analysis, when there are i traffic streams arriving at the period T and $i\ge \mathrm{2}$ holds, there are two cases of the last traffic stream's arrival time: the former $i-1$ traffic streams have finished service or have not finished service before the last traffic stream's arrival. Thus when there are i traffic streams arriving during the period T ( $i\ge \mathrm{0}$ ), there are ${\mathrm{2}}^i$ cases of idle duration distributions.

Consequently, it is practically impossible to derive the formulation of $D_i$ when i is large. Indeed, we have found that the scale of the polynomial expression for $D_i$ increases rapidly with i. Nevertheless, based on the relationship of $D_i$ and $D_{i+\mathrm{1}}$ and through approximation, a two-stage predictive method is given to approximate $D_i$ in

$$\begin{array}{cc}& D_i\approx \left\{\begin{array}{cc}{D}_i^{\left(\mathrm{1}\right)},\hfill & \mathrm{1}\le i<\frac{CT-L_{\mathrm{0}}}{f_d}-\mathrm{1},\hfill \\ D_i^{\left(\mathrm{2}\right)},\hfill & i\ge \frac{CT-L_{\mathrm{0}}}{f_d}-\mathrm{1},\hfill \end{array}\right.\end{array}$$

(13)

where

$$\begin{array}{l}{D}_{i+\mathrm{1}}^{\left(\mathrm{1}\right)}\\ =D_i-\frac{f_d}{C}\left[\frac{CT-f_d}{CT}+\frac{f_d-CT+C{D}_i}{CT}\exp \left(-\frac{C{D}_i}{f_d}\right)\right],\\ D_{i+\mathrm{1}}^{\left(\mathrm{2}\right)}\\ =D_i-\frac{f_d}{C}\left[\frac{CT-f_d}{CT}+\frac{f_d-CT+C{D}_i}{CT}\exp \left(-\frac{C{D}_i}{f_d}\right)\right]\\ \hspace{1em}·\frac{L_{\mathrm{0}}+C{D}_i}{CT}.\end{array}$$

(14)

The iteration expressions of $D_i^{(\mathrm{1})}$ and $D_i^{(\mathrm{2})}$ are derived through approximation in Appendix A, and the effectiveness of the two-stage iteration method has been validated through extensive simulation. In the simulation, we found that the effectiveness of the two-stage iteration method is mainly determined by the ratio of $f_d/CT$ and the method has a good performance when $f_d/CT<\mathrm{0.1}$ holds. Some simulation results are given as Figures 4 and 5. In the two figures, the Y axis represents the normalized idle duration (i.e., $D/T$ ), the estimate value of idle-duration is calculated by (5) and (13), and the real value of idle duration is obtained by simulating the traffic arrival process and the traffic serving process. Figure 4 shows the averaged normalized idle-durations with the variation of the arrived traffic numbers in the period T, and Figure 5 shows the averaged normalized idle-durations with the variation of the $\lambda ·T$ . For Figure 5, the arrived traffic number in the period T is determined by the Poisson process with arrival rate λ. From the two figures, it can be seen that the effectiveness of the predictive method is almost determined by the ratio of $f_d/CT$ , and the estimate value by the two-stage iteration method matches well with the real value when $f_d/CT\le \mathrm{0.1}$ . Indeed, the condition of $f_d/CT\le \mathrm{0.1}$ can be fulfilled by the current and future wireless networks like 4G cellular network, WiMAX and WLAN, and so forth.

Figure 4

Estimate and real value of the average $D/T$ with variations of $f_d/CT$ , $L_{\mathrm{0}}/CT$ , and the arrived traffic number i.

Figure 5

Estimate and real value of the average $D/T$ with variations of $f_d/CT$ , $L_{\mathrm{0}}/CT$ , and $\lambda T$ .

5. Method for Optimal Solution

With the idle duration of ${\mathcal{D}}_n(r_n,x_n,T)$ approximated by (5) and (13), the load scheduling problem (3) would be proved to be a convex optimization problem by proving ${\partial }^{\mathrm{2}}h(\{r_{n,k}\},\{x_k^{n-m}\},T)/\partial (x_k^{n-m}{)}^{\mathrm{2}}\ge \mathrm{0}$ for all n, $m\in \mathcal{N}$ , and $k\in \mathcal{K}$ in the following. Then the gradient expression of $\partial h(\{r_{n,k}\},\{x_k^{n-m}\},T)/\partial x_k^{n-m}$ is derived to obtain the gradient descent method for optimal solution.

According to the expression of $h(\{r_{n,k}\},\{x_k^{n-m}\},T)$ and (5) and (13), ${\partial }^{\mathrm{2}}h(\{r_{n,k}\},\{x_k^{n-m}\},T)/\partial (x_k^{n-m}{)}^{\mathrm{2}}$ is derived as

$$\begin{array}{l}\frac{{\partial }^{\mathrm{2}}h\left(\left\{r_{n,k}\right\},\left\{x_k^{n-m}\right\},T\right)}{\partial {\left(x_k^{n-m}\right)}^{\mathrm{2}}}\\ \hspace{1em}=\frac{{\partial }^{\mathrm{2}}{\sum }_{n_{\mathrm{1}}\in \mathcal{N}}{C}_{n_{\mathrm{1}}}{\mathcal{D}}_{n_{\mathrm{1}}}\left(r_{n_{\mathrm{1}}},x_{n_{\mathrm{1}}},T\right)}{{\partial \left(x_k^{n-m}\right)}^{\mathrm{2}}}\\ \hspace{1em}={\displaystyle \sum }_{n_{\mathrm{1}}\in \mathcal{N}}‍C_{n_{\mathrm{1}}}\frac{{\partial }^{\mathrm{2}}{\mathcal{D}}_{n_{\mathrm{1}}}\left(r_{n_{\mathrm{1}}},x_{n_{\mathrm{1}}},T\right)}{{\partial \left(x_k^{n-m}\right)}^{\mathrm{2}}}\\ \hspace{1em}={\displaystyle \sum }_{n_{\mathrm{1}}\in \mathcal{N}}‍C_{n_{\mathrm{1}}}\left({\displaystyle \sum }_{i=\mathrm{0}}^{\infty }‍P_i\frac{{\partial }^{\mathrm{2}}{D}_i\left(L_{\mathrm{0}}=r_{n_{\mathrm{1}}}+x_{n_{\mathrm{1}}}\right)}{\partial {\left(x_k^{n-m}\right)}^{\mathrm{2}}}\right)\\ \hspace{1em}={\displaystyle \sum }_{n_{\mathrm{1}}\in \mathcal{N}}‍C_{n_{\mathrm{1}}}\left({\displaystyle \sum }_{i=\mathrm{0}}^{\infty }‍P_i\frac{{\partial }^{\mathrm{2}}{D}_i\left(L_{\mathrm{0}}=r_{n_{\mathrm{1}}}+x_{n_{\mathrm{1}}}\right)}{\partial L_{\mathrm{0}}^{\mathrm{2}}}{\left(\frac{\partial x_{n_{\mathrm{1}}}}{\partial \left(x_k^{n-m}\right)}\right)}^{\mathrm{2}}\right).\end{array}$$

(15)

Thus, ${\partial }^{\mathrm{2}}h(\{r_{n,k}\},\{x_k^{n-m}\},T)/\partial (x_k^{n-m}{)}^{\mathrm{2}}\ge \mathrm{0}$ can be proved by proving ${\partial }^{\mathrm{2}}{D}_i/\partial L_{\mathrm{0}}^{\mathrm{2}}\ge \mathrm{0}$ . According to (13), ${\partial }^{\mathrm{2}}{D}_i/\partial L_{\mathrm{0}}^{\mathrm{2}}\ge \mathrm{0}$ can be proved by proving $d^{\mathrm{2}}{D}_i^{(\mathrm{1})}/L_{\mathrm{0}}^{\mathrm{2}}\ge \mathrm{0}$ and $d^{\mathrm{2}}{D}_i^{(\mathrm{2})}/L_{\mathrm{0}}^{\mathrm{2}}\ge \mathrm{0}$ . For the clarity of proof, define $f(D_i)$ and $g(D_i)$ as follows:

$$\begin{array}{l}f\left(D_i\right)=\frac{f_d}{C}\left[\frac{CT-f_d}{CT}+\frac{f_d-CT+C{D}_i}{CT}\exp \left(-\frac{C{D}_i}{f_d}\right)\right],\\ g\left(D_i\right)=\frac{C{D}_i+L_{\mathrm{0}}}{CT}.\end{array}$$

(16)

Based on (A.6) and (A.8), the following relationships hold: $D_{i+\mathrm{1}}^{(\mathrm{1})}=D_i-f(D_i)$ and $D_{i+\mathrm{1}}^{(\mathrm{1})}=D_i-f(D_i)g(D_i)$ . So, when $d^{\mathrm{2}}{D}_i^{(\mathrm{1})}/d{L}_{\mathrm{0}}^{\mathrm{2}}\ge \mathrm{0}$ , the following relationships can be derived:

$$\begin{array}{l}\frac{d^{\mathrm{2}}{D}_{i+\mathrm{1}}^{\left(\mathrm{1}\right)}}{L_{\mathrm{0}}^{\mathrm{2}}}=\frac{d^{\mathrm{2}}{D}_i^{\left(\mathrm{1}\right)}}{L_{\mathrm{0}}^{\mathrm{2}}}-\frac{d^{\mathrm{2}}f\left(D_i^{\left(\mathrm{1}\right)}\right)}{d{L}_{\mathrm{0}}^{\mathrm{2}}}\\ =\frac{d^{\mathrm{2}}{D}_i^{\left(\mathrm{1}\right)}}{L_{\mathrm{0}}^{\mathrm{2}}}-\frac{d^{\mathrm{2}}{D}_i^{\left(\mathrm{1}\right)}}{d{L}_{\mathrm{0}}^{\mathrm{2}}}\left(\mathrm{1}-\frac{D_i^{\left(\mathrm{1}\right)}}{T}\right)\exp \left(-\frac{C{D}_i^{\left(\mathrm{1}\right)}}{f_d}\right)\\ \hspace{1em}+{\left(\frac{d{D}_i^{\left(\mathrm{1}\right)}}{d{L}_{\mathrm{0}}}\right)}^{\mathrm{2}}\left[\frac{\mathrm{1}}{T}+\left(\mathrm{1}-\frac{D_i^{\left(\mathrm{1}\right)}}{T}\right)\right]\exp \left(-\frac{C{D}_i^{\left(\mathrm{1}\right)}}{f_d}\right)\\ \ge \frac{d^{\mathrm{2}}{D}_i^{\left(\mathrm{1}\right)}}{d{L}_{\mathrm{0}}^{\mathrm{2}}}\frac{D_i^{\left(\mathrm{1}\right)}}{T}.\end{array}$$

(17)

Hence, $d^{\mathrm{2}}{D}_{i+\mathrm{1}}^{(\mathrm{1})}/d{L}_{\mathrm{0}}^{\mathrm{2}}\ge \mathrm{0}$ only when $d^{\mathrm{2}}{D}_i^{(\mathrm{1})}/d{L}_{\mathrm{0}}^{\mathrm{2}}\ge \mathrm{0}$ holds. Since $d^{\mathrm{2}}{D}_{\mathrm{0}}/d{L}_{\mathrm{0}}^{\mathrm{2}}=\mathrm{0}$ holds, $d^{\mathrm{2}}{D}_i^{(\mathrm{1})}/d{L}_{\mathrm{0}}^{\mathrm{2}}\ge \mathrm{0}$ is proved.

When $d^{\mathrm{2}}{D}_i^{(\mathrm{2})}/d{L}_{\mathrm{0}}^{\mathrm{2}}\ge \mathrm{0}$ holds, $d^{\mathrm{2}}{D}_{i+\mathrm{1}}^{(\mathrm{2})}/d{L}_{\mathrm{0}}^{\mathrm{2}}\ge \mathrm{0}$ can be proved as the following equation based on (22), (23), and Lemma 2 in Appendix B:

$$\begin{array}{l}\frac{d^{\mathrm{2}}{D}_{i+\mathrm{1}}^{\left(\mathrm{2}\right)}}{d{L}_{\mathrm{0}}^{\mathrm{2}}}\\ =\frac{d^{\mathrm{2}}{D}_i^{\left(\mathrm{2}\right)}}{d{L}_{\mathrm{0}}^{\mathrm{2}}}-\frac{d^{\mathrm{2}}f\left(D_i^{\left(\mathrm{2}\right)}\right)}{d{L}_{\mathrm{0}}^{\mathrm{2}}}g\left(D_i^{\left(\mathrm{2}\right)}\right)\\ \hspace{1em}-\mathrm{2}\frac{df\left(D_i^{\left(\mathrm{2}\right)}\right)}{d{L}_{\mathrm{0}}}\frac{dg\left(D_i^{\left(\mathrm{2}\right)}\right)}{d{L}_{\mathrm{0}}}-f\left(D_i^{\left(\mathrm{2}\right)}\right)\frac{d^{\mathrm{2}}g\left(D_i^{\left(\mathrm{2}\right)}\right)}{d{L}_{\mathrm{0}}^{\mathrm{2}}}\\ \ge \frac{d^{\mathrm{2}}{D}_i^{\left(\mathrm{2}\right)}}{d{L}_{\mathrm{0}}^{\mathrm{2}}}-\frac{d^{\mathrm{2}}f\left(D_i^{\left(\mathrm{2}\right)}\right)}{d{L}_{\mathrm{0}}^{\mathrm{2}}}g\left(D_i^{\left(\mathrm{2}\right)}\right)-f\left(D_i^{\left(\mathrm{2}\right)}\right)\frac{d^{\mathrm{2}}g\left(D_i^{\left(\mathrm{2}\right)}\right)}{d{L}_{\mathrm{0}}^{\mathrm{2}}}\\ \ge \frac{d^{\mathrm{2}}{D}_i^{\left(\mathrm{2}\right)}}{d{L}_{\mathrm{0}}^{\mathrm{2}}}-\frac{d^{\mathrm{2}}{D}_i^{\left(\mathrm{2}\right)}}{d{L}_{\mathrm{0}}^{\mathrm{2}}}\left(\mathrm{1}-\frac{D_i^{\left(\mathrm{2}\right)}}{T}\right)-\frac{D_i^{\left(\mathrm{2}\right)}}{T}\frac{d^{\mathrm{2}}{D}_i^{\left(\mathrm{2}\right)}}{d{L}_{\mathrm{0}}^{\mathrm{2}}}=\mathrm{0}.\end{array}$$

(18)

Therefore, ${\partial }^{\mathrm{2}}h(\{r_{n,k}\},\{x_k^{n-m}\},T)/\partial (x_k^{n-m}{)}^{\mathrm{2}}\ge \mathrm{0}$ is proved, so the load scheduling problem (3) is a convex optimization problem when it adopts the two-stage predictive method. There are many methods proposed in the literature such as descent method, gradient descent method, and Newton's method [11] for convex optimization problem. Here, we give a gradient descent method to solve problem (3) and derive the gradient expression of $\partial h(\{r_{n,k}\},\{x_k^{n-m}\},T)/\partial x_k^{n-m}$ in the following:

$$\begin{array}{l}\frac{\partial h\left(\left\{r_{n,k}\right\},\left\{x_k^{n-m}\right\},T\right)}{\partial x_k^{n-m}}\\ \hspace{1em}={\displaystyle \sum }_{n_{\mathrm{1}}\in \mathcal{N}}‍C_{n_{\mathrm{1}}}\left({\displaystyle \sum }_{i=\mathrm{0}}^{\infty }‍P_i\frac{\partial D_i\left(L_{\mathrm{0}}=r_{n_{\mathrm{1}}}+x_{n_{\mathrm{1}}}\right)}{\partial L_{\mathrm{0}}}\left(\frac{\partial x_{n_{\mathrm{1}}}}{\partial \left(x_k^{n-m}\right)}\right)\right),\end{array}$$

(19)

where

$$\begin{array}{cc}& \frac{\partial x_{n_{\mathrm{1}}}}{\partial \left(x_k^{n-m}\right)}=\left\{\begin{array}{cc}\mathrm{1},\hfill & k\in {\mathcal{K}}_n,\hspace{0.17em}\hspace{0.17em}k\in {\mathcal{K}}_m,\hspace{0.17em}\hspace{0.17em}m=n_{\mathrm{1}}\hfill \\ -\mathrm{1},\hfill & k\in {\mathcal{K}}_n,\hspace{0.17em}\hspace{0.17em}k\in {\mathcal{K}}_m,\hspace{0.17em}\hspace{0.17em}n=n_{\mathrm{1}}\hfill \\ \mathrm{0},\hfill & \text{else}.\hfill \end{array}\right.\end{array}$$

(20)

And $\partial D_i(L_{\mathrm{0}}=r_{n_{\mathrm{1}}}+x_{n_{\mathrm{1}}})/\partial L_{\mathrm{0}}$ is given by

$$\begin{array}{l}\frac{d{D}_{i+\mathrm{1}}}{d{L}_{\mathrm{0}}}\\ =\left\{\begin{array}{ll}\frac{d{D}_i}{d{L}_{\mathrm{0}}}-\frac{df\left(D_i\right)}{d{L}_{\mathrm{0}}},\hfill & k<\frac{C_{n_{\mathrm{1}}}T-L_{\mathrm{0}}}{f_d}-\mathrm{1}\hfill \\ \frac{d{D}_i}{d{L}_{\mathrm{0}}}-\frac{df\left(D_i\right)}{d{L}_{\mathrm{0}}}g\left(D_i\right)\hfill & \hfill \\ \hspace{1em}-f\left(D_i\right)\frac{dg\left(D_i\right)}{d{L}_{\mathrm{0}}},\hfill & \text{else},\hfill \end{array}\right.\end{array}$$

(21)

where

$$\begin{array}{l}\frac{df\left(D_i\right)}{d{L}_{\mathrm{0}}}=\frac{d{D}_i}{d{L}_{\mathrm{0}}}\left(\mathrm{1}-\frac{D_i}{T}\right)\exp \left(-\frac{C_{n_{\mathrm{1}}}{D}_i}{f_d}\right),\\ \frac{dg\left(D_i\right)}{d{L}_{\mathrm{0}}}=\frac{\mathrm{1}}{T}\frac{d{D}_i}{d{L}_{\mathrm{0}}}+\frac{\mathrm{1}}{C_{n_{\mathrm{1}}}T},\hspace{1em}\frac{d{D}_{\mathrm{0}}}{d{L}_{\mathrm{0}}}=-\frac{\mathrm{1}}{C_{n_{\mathrm{1}}}}.\end{array}$$

(22)

And according to Lemma 2 in Appendix B, the following relationships can be derived:

$$\begin{array}{cc}& \frac{df\left(D_i\right)}{d{L}_{\mathrm{0}}}\le \mathrm{0},\hspace{1em}\hspace{1em}\frac{dg\left(D_i\right)}{d{L}_{\mathrm{0}}}\ge \mathrm{0}.\end{array}$$

(23)

All the results above can be combined to obtain the gradient descent method [11] for problem (3) as Algorithm 1. By implementing the iteration process in the gradient descent method, the optimal solution of scheduled loads ( $\{x_k^{n-m}{\}}^{\mathrm{\ast }},\hspace{0.17em}\hspace{0.17em}n,m\in \mathcal{N},\hspace{0.17em}\hspace{0.17em}k\in \mathcal{K}$ ) can be obtained.

Algorithm 1: Gradient descent method for the optimization problem (3).

(1) Given a starting point of $$x_{k,\mathrm{0}}^{n-m}\in [\mathrm{0},r_{n,k}]$$ for all $$n,m\in \mathcal{N}$$ and $$k\in \mathcal{K}$$ .

(2) Calculated   $$\partial h(\{r_{n,k}\},\{x_k^{n-m}\},T)/\partial x_{k,\mathrm{0}}^{n-m}$$ for each ( $$n,m,k$$ ) by (19)–(21).

(3) Initialized   $$j=\mathrm{0}$$ , step size $${\delta }_{k,\mathrm{0}}^{n-m}$$ for each ( $$n,m,k$$ ).

(4) while  existing ( $$n,m,k$$ ) satisfy $$\left|\partial h(\{r_{n,k}\},\{x_k^{n-m}\},T)/\partial x_{k,j}^{\mathrm{n}-m}\right|>\epsilon$$   do

(5) Calculated   $$x_{k,j+\mathrm{1}}^{n-m}=x_{k,j}^{n-m}-{\delta }_{k,j}^{n-m}(\partial h(\{r_{n,k}\},\{x_k^{n-m}\},T)/\partial x_{k,j}^{n-m})$$ .

(6) Updated   $$j=j+\mathrm{1}$$ , and step size $${\delta }_{k,j}^{n-m}$$ .

(7) Calculated   $$\partial h(\{r_{n,k}\},\{x_k^{n-m}\},T)/\partial x_{k,j}^{n-m}$$ for each ( $$n,m,k$$ ) by (19)–(21).

(8) end while

(9) Obtain the optimal solution $${(x_k^{n-m})}^{\mathit{\ast }}=x_{k,j}^{n-m}$$ .

6. Simulation Results and Discussion

In this section, the effectiveness of the proposed load scheduling scheme is validated, the performance of the proposed scheme and other schemes are compared, and the impacts of system parameters are evaluated.

In the simulation, the considered scenario is shown in Figure 6: three BSs of $\mathcal{N}=\{\mathrm{0,1},2\}$ and three regions of $\mathcal{K}=\{\mathrm{0,1},2\}$ .

Figure 6

Simulation scenario with a macrocell and two microcells.

6.1. Validation of the Proposed Load Scheduling Scheme

In the literature, a load balance index based method has been extensively investigated [12–14], and the general expression of the balance index is given by

$$\begin{array}{cc}& B\left(y\right)=\frac{{\left({\sum }_i{y}_i\right)}^{\mathrm{2}}}{\left|\mathcal{N}\right|\left({\sum }_i{y}_i^{\mathrm{2}}\right)}.\end{array}$$

(24)

The reference load scheduling scheme, denoted by “ref” in the simulation results, is obtained by maximizing $B(y)$ with $y_i=\left(r_i+x_i\right)/C_i$ . In the simulation results, the scheme without load scheduling is denoted by non, the proposed load scheduling scheme is denoted by eff, and the throughput-optimal load scheduling scheme is denoted by opt. The opt scheme obtain its optimal scheduling loads by exhaustive search and trials.

In the simulation for effectiveness validation of the proposed scheme, the sums of capacity-weighted idle durations are collected by fixing the residual load of $r_{n,k}$ ( $n\in \mathcal{N},\hspace{0.17em}\hspace{0.17em}k\in \mathcal{K}$ ) before each scheduling, and the results are averaged by 10000 trials. The simulation parameters are configured as $r_{\mathrm{0,1}}=\mathrm{15}$  Mbits, $r_{\mathrm{0,2}}=\mathrm{10}$  Mbits, $r_{\mathrm{1,1}}=\mathrm{5}$  Mbits, $r_{\mathrm{2,2}}=\mathrm{10}$  Mbits, $C_{\mathrm{0}}=\mathrm{20}$  Mbps, $C_{\mathrm{1}}=C_{\mathrm{2}}=\mathrm{10}$  Mbps, ${\lambda }_{\mathrm{0,0}}=\mathrm{10}$ calls/s, ${\lambda }_{\mathrm{0,1}}={\lambda }_{\mathrm{2,2}}=\mathrm{2.4}$ calls/s, ${\lambda }_{\mathrm{1,1}}={\lambda }_{\mathrm{0,2}}=\mathrm{9.6}$ calls/s, $f_d=\mathrm{1}$  Mbits, and the maximum acceptable UE number is 40 for each BS.

Some results of the four scheduling schemes are given by Figures 7 and 8, where the normalized utilization loss is calculated by $h(\{r_{n,k}\},\{x_k^{n-m}\},T)/(C_{\mathrm{0}}+C_{\mathrm{1}}+C_{\mathrm{2}})T$ . Figure 7 shows the normalized utilization loss values of the four schemes with the variation of the initial residual load in BS 0 from region 0 (i.e., $r_{\mathrm{0,0}}$ ), and Figure 8 shows the normalized utilization loss values with the variation of the scheduling period T. In the two figures, the throughput-optimal load scheduling scheme (denoted by “opt”) always has the best performance and the scheme without load scheduling always has the worst performance. The performance of the proposed scheme is very close to the performance of the throughput-optimal scheme, and the performance gap is smaller when the initial residual load $r_{\mathrm{0,0}}$ is larger or when the scheduling period T is smaller. In Figure 7, the normalized utilization loss values of the four schemes decrease with the initial residual load $r_{\mathrm{0,0}}$ because larger initial residual load means smaller idle-duration expectation. In Figure 8, the normalized utilization loss values of the four schemes increases with the period T because the total capacity ${\sum }_{n\in \mathcal{N}}{C}_n$ is larger than the sum of arriving traffic loads ${\sum }_{n\in \mathcal{N},k\in \mathcal{K}}{\lambda }_{n,k}{f}_d$ . Furthermore, similar results have been obtained with variations of initial residual loads in the other two BSs and traffic arrival rates in the other two regions, but they are not given here due to space limitation. All the results show that the proposed scheduling scheme can closely approach the optimal solution.

Figure 7

Normalized utilization loss with variation of the initial residual load in BS 0 form region 0 ( $r_{\mathrm{0,0}}$ ).

Figure 8

Normalized utilization loss with variation of scheduling period T.

6.2. Throughput and Delay Improvement

We evaluate the performance of the proposed load scheduling scheme with the periodically changed traffic arrival rates as Figure 9, and the common fluctuation cycle of traffic arrival rates is 300 s. And in Figure 9, ${\lambda }_i$ ( $i=\mathrm{0,1},2$ ) denotes the traffic arrival rates in region i, ${\lambda }_{iH}$ and ${\lambda }_{iL}$ ( $i=\mathrm{1,2}$ ) denote the peak value and minimal value of arrival rates in region i, and ${\lambda }_{iH}=\mathrm{2}{\lambda }_{iL}$ . We collect results by running the emulator of load serving process and traffic arrival process for 10000 seconds for each trial and average the results through 100 trials.

Figure 9

Periodic traffic arrival rates in the three regions.

Figures 10 and 11 show the blocking probabilities and delays of the three load scheduling schemes when traffic load is light, respectively. The blocking probability is the probability that a new arrival UE is blocked, and the blocking happens when the numbers of admitted UEs in all the available BSs reach their upper limits. The traffic arrival rates are configured as ${\lambda }_{\mathrm{0}}=\mathrm{10}$ calls/s, ${\lambda }_{\mathrm{1}H}={\lambda }_{\mathrm{2}H}=\mathrm{5}$ calls/s, ${\lambda }_{\mathrm{0,0}}=\mathrm{10}$ calls/s, ${\lambda }_{\mathrm{0,1}}=\mathrm{0.3}{\lambda }_{\mathrm{1}}$ , ${\lambda }_{\mathrm{0,2}}=\mathrm{0.7}{\lambda }_{\mathrm{2}}$ , ${\lambda }_{\mathrm{1,1}}=\mathrm{0.7}{\lambda }_{\mathrm{1}}$ , ${\lambda }_{\mathrm{2,2}}=\mathrm{0.3}{\lambda }_{\mathrm{2}}$ , and other parameters are the same as those in the former subsection.

Figure 10

Blocking probability of traffic when load is relatively light.

Figure 11

Average delay of traffic when load is relatively light.

As shown in Figures 10 and 11, the proposed load scheduling scheme always has the best performance of decreasing average delays and blocking probabilities. Compared with the “non” scheme, the proposed load scheduling scheme can reduce almost 20% blocking probabilities and 30% delays when the scheduling period T is small. In the two figures, the blocking probabilities and average delays of the proposed scheme and the reference scheme increase with the scheduling period, because the scheduling frequency decreases and the gain brought by scheduling decreases accordingly when T increases.

Figures 12 and 13 show the performance of these schemes when traffic load is relatively heavy, which is configured as ${\lambda }_{\mathrm{0}}=\mathrm{10}$ calls/s and ${\lambda }_{\mathrm{1}H}={\lambda }_{\mathrm{2}H}=\mathrm{9}$ calls/s. As shown in Figures 12 and 13, the proposed load scheduling scheme can almost reduce 60% blocking probability and reduce about 50% delay compared with the scheme without load scheduling when the scheduling period T is small. The proposed load scheduling scheme always has the best performance. Comparing these results with the results when the traffic load is light, we can see that the proposed load scheduling scheme has better performance improvements of blocking probability and average delay when the traffic load is heavier.

Figure 12

Blocking probability of traffic when load is relatively heavy.

Figure 13

Average delay of traffic when load is relatively heavy.

7. Conclusion

In this paper, a predictive load scheduling scheme is proposed from the point of decreasing the capacity-weighted idle durations of networks and channels. For the proposed scheme, a fairly general HWNs scenario is considered, the objective of minimizing the capacity-weighted idle durations is formulated, a two-stage predictive method is given to predict the idle duration, and a gradient descent method is given for the optimal scheduled loads. By simulation, the effectiveness of the two-stage predictive method is validated with a variety of system parameters, the effectiveness and the performance of the proposed load scheduling scheme is demonstrated, and the impacts of system parameters are evaluated. This work may shed some light for future extension and study.