In order to improve the total system throughput and QoS for different users while keeping certain fairness, we need to determine the users’ queue priority for deriving an online measurement based resource allocation. The overflow probability estimation model is derived by applying large deviation principle, which requires no statistical knowledge of the network conditions. Then, we rank the users’ queue priority by their remaining life time or their queue overflow probability.
3.1 Estimation model for the queue overflow probability
The arrival rate of the incoming bits depends on the service type, while the service rate depends on the resource allocation policy as well as the wireless channel conditions which are time-varying in nature. Hence, the arrival process and the service process are independent of each other. Our aim is to control all user queues in such a way that the service demands of the data in each queue could be satisfied. Moreover, the resulted scheme should be robust to the variations of the arrival and service processes.
Let I
k
(t)=A
k
(t)−V
k
(t), where I
k
(t)∈{−m
V
,⋯,0,1,⋯,m
A
}, and let \({\pi _{i}^{k}}=P(I_{k}(t)=i)\) denote the corresponding kth user queue-length variation probability distribution. Since A
k
(t) is determined by the bit arrival number during the slot t and V
k
(t) is determined by the bit number served during the slot t, their difference I
k
(t) characterizes the mismatch between the bit service rate and the bit arrival rate of the kth user queue during the slot t. I
k
(t)<0 implies that the bit service rate is higher than the arrival rate in the tth slot, while I
k
(t)>0 implies that the bit service rate cannot satisfy the bit arrival. Due to the time-varying number of bit arrivals and the state of SBs, the polarity of the sequence I
k
(t)(t=1,2,…) may change frequently between negative and positive.
The
kth user queue length increment during the period spanning from the
tth slot to the (
t+
T)th slot can be formulated as
$$ I_{k}^{t+T}=\sum_{i=1}^{T} I_{k}(t+i), $$
(10)
where T is called prediction interval.
Then, the length of the
kth user queue at the beginning of the (
t+
T)th slot can be expressed as
$$ Q_{k}(t+T)= Q_{k}(t)+ I_{k}^{t+T}. $$
(11)
Let
\(P_{k_{\textit {overflow}}}^{t+T}\) denote the overflow probability of the
kth user queue during the slot (
t+
T), which is defined as
$$ P_{k_{overflow}}^{t+T}=P\left(Q_{k}(t+T)> Q_{k}^{max}\right). $$
(12)
The above expression can be rewritten as
$$ P_{k_{overflow}}^{t+T}=P\left(Q_{k}(t)+ I_{k}^{t+T} > Q_{k}^{max}\right). $$
(13)
Define the achievable average queue growth of the
kth user queue during the future
T slots as
$$ g_{k}=\frac{Q_{k}^{max}-Q_{k}(t)}{T}, $$
(14)
and the expected average queue growth of the
kth user queue in each slot during the
T slots as
$$ c_{k}=E\left[\frac{\sum_{i=1}^{T} I_{k}(t+i)}{T}\right]. $$
(15)
where
E[·] denotes expectation operator.
c
k
>
g
k
implies that there is high overflow possibility of the
kth user queue after
T slots. Equation (
12) can be further written as
$$\begin{array}{@{}rcl@{}} P_{k_{overflow}}^{t+T} &=& P\left(Q_{k}(t)+ I_{k}^{t+T} > Q_{k}^{max}\right)\\ &=& P\left({I_{k}^{t+T}/T}> {({Q_{k}^{max}-Q_{k}(t)})/T}\right)\\ &=& p\left({{\sum_{i=1}^{T} I_{k}(t+i)}\over T} > g_{k}\right). \end{array} $$
(16)
The term
\(\frac {\sum _{i=1}^{T} I_{k}(t+i)}{T}\) in (
16) is determined by the bits departure or the resource allocation, while
g
k
is determined by the current length of the
kth user queue. Since the queue overflow probability indicates the mismatch between the resource and the traffic, we can dynamically rank the users’ queue priority based on the value of
\(P_{k_{\textit {overflow}}}^{t+T}\). The larger value of
\(P_{k_{\textit {overflow}}}^{t+T}\) means that queue overflow is more likely to occur and the corresponding user queue should have the higher priority of resource allocation, thus reducing the bit loss rate and satisfying QoS requirement. This is why the proposed method jointly considers RB capacity and the queue priority.
\(Cram \acute e r's\) Theorem in the context of large deviation principle can be applied to estimate the overflow probability in [
30]. Since
A
k
(
t) is an i.i.d process,
I
k
(
t)(
t=1,2,…) are also i.i.d random variables with a finite moment generating function
\(\phantom {\dot {i}\!}G(\theta)=E \lbrace e^{\theta I_{k}(t)}\rbrace \). According to
\(Cram \acute e r's\) Theorem [
31], if
c
k
<
g
k
, the sequence
I
k
(
t)(
t=1,2,…) obeys the large deviation principle, and we have
$$ {\lim}_{T \rightarrow \infty} \frac{1}{T} log P \left(\frac{\sum_{i=1}^{T} I_{k}(t+i)}{T} > g_{k}\right)= -l(g_{k}). $$
(17)
where
$$ l(g_{k})={{sup}_{\theta>0}} \lbrace g_{k} \theta - log G(\theta)\rbrace. $$
(18)
and
$$ log G(\theta)=log \left\{\sum_{i=-m_{V}}^{m_{A}}{\pi_{i}^{k}} e^{i \theta}\right\}. $$
(19)
Note that
l
o
g
G(
θ) is a convex function, and the rate function
l(
g
k
) is also convex [
31]. For a sufficiently large value of
T, according to (
17) the overflow probability can be approximated by
$$ P_{k_{overflow}}^{t+T} \approx e^{-T l(g_{k})}. $$
(20)
In theory, the overflow probability estimate becomes more accurate as
T increases. Hence, the value of
T should be sufficiently large. However, owing to the rapid exponential decay of the overflow probability estimate with
T, we can set
T to a moderate value for the sake of acquiring an accurate overflow probability estimate. The experimental results in the section of ‘
Performance evaluation’ demonstrate that
T≥60 is appropriate.
In the next section, we show how to online estimate the overflow probability based on (
20).
3.2 Online estimation of the queue overflow probability
According to (
20), estimating the overflow probability requires the values of
g
k
,
c
k
, and
\({\pi _{i}^{k}}\). It is easy to calculate
g
k
according to (
14). However, we have to estimate
c
k
and
\({\pi _{i}^{k}}\) because there is no prior knowledge about
I
k
(
t). Therefore, the historical observations are utilized to estimate these parameters by applying a sliding window-based method.
Suppose the observed sequence is given by {I
1,I
2,I
3,⋯ }. The sliding window covers the T
s
most recent entries in this sequence, which is slid over this sequence. For the nth window, the observation vector is denoted by \(\phantom {\dot {i}\!}W_{n}=[I_{n}, I_{n-1}, I_{n-2}, \cdots I_{n-T_{s}+1}]\).
For the parameter
c
k
, we use the sample mean as its estimate, i.e.,
$$ \hat c_{k}={{\sum_{i={n-T_{s}+1}}^{n} I_{k}(i)}\over {T_{s}}}. $$
(21)
Following the similar steps in [
32], we can apply the large deviation principle to analyze the confidence interval of
c
k
.
Below, we will estimate
\({\pi _{i}^{k}} (i\in \lbrace -m_{V}, \ldots,0,1, \ldots, m_{A} \rbrace)\). Let
\({T_{i}^{k}}\) denote the number of
I
k
(
t)=
i events during the
T
s
slots, which can be calculated by
$$ {T_{i}^{k}}=\sum_{t={n-T_{s}+1}}^{n} 1_{i}(I_{k}(t)). $$
(22)
where 1
i
(·) is a indicator function. When
I
k
(
t)=
i, it has a value of 1, otherwise 0. Then, the frequency of
I
k
(
t)=
i can be estimated as
$$ \hat {u_{i}^{k}}(t)={{T_{i}^{k}} \over T_{s}}. $$
(23)
If the value of
T
s
is too small, it may result in a large estimate error of
\( \hat {u_{i}^{k}}(t)\), while too large, it may reduce the sensitivity to queue variations. Hence,
T
s
should be set to a moderate value. We set it to 60 in our experiments. We apply an exponential smoothing method to smoothen the estimated value, which is written as
$$ \hat {\pi_{i}^{k}}(t)= \rho \hat {\pi_{i}^{k}}(t-1)+(1- \rho) \hat {u_{i}^{k}}(t). $$
(24)
where the parameter
ρ∈[0,1]. If
ρ approaches to 1, the value of
\(\hat {\pi _{i}^{k}}(t)\) largely depends on the past estimation, while if
ρ=0,
\(\hat {\pi _{i}^{k}}(t)\) totally depends on the current estimate
\( \hat {u_{i}^{k}}(t)\). According to Gardner’s report [
33],
ρ∈[0.7,0.9] is usually recommended.
The above steps assist us to derive the online measurement-based method to estimate the queue overflow probability
\(P_{k_{\textit {overflow}}}^{t+T}\) based on (
20) in the (
t+
T) slot, by setting
T to a moderate value in a practical application. The experimental results show that
T≥60 is appropriate.
3.3 User priority determination algorithm
In the case of
\(\hat c_{k}\geq g_{k}\), the average growth length of the
kth user queue in each slot,
\(\hat c_{k}\), is higher than the achievable average growth length of the
kth user queue per slot,
g
k
, in the forthcoming
T slots. This implies that if keeping the current queue configuration unchanged with the bit service rate
V
k
(
t), after
T slots, the queue will be more likely to have an overflow situation. Therefore, in this scenario, we should improve the bit service rate to prolong the remaining life time. In this paper, remaining life time
R
k
(
t) can be calculated by (
5) to rank the queue priority of resource allocation.
However, in the case of
\(\hat c_{k}< g_{k}\), the average growth length of the
kth user queue in each slot,
\(\hat c_{k}\), is lower than the achievable average growth length of the
kth user queue,
g
k
, in the forthcoming
T slots. But this does not necessarily imply that no overflow will happen in the future
T slots, since
\(\hat c_{k}\) is the average growth per slot which cannot characterize the specific queue length growth in a single time slot. Hence, the queue overflow might still occur. Since we have
\(g_{k}> \hat c_{k}\), the queue overflow remains a rare event, and the queue overflow probability in the (
t+
T) slot,
\(P_{k_{\textit {overflow}}}^{t+T}\), can be approximated by (
20).
The buffer-aware priority determination algorithm determines a priority value for each user, where the user in the case of \(\hat c_{k}\geq g_{k}\) is more emergent than in the case of \(\hat c_{k}< g_{k}\). The smallest value of R
k
(t) indicates the highest priority of the kth user. The value in ascending order represents that the users’ priority is from high to low. The smaller value is \(P_{k_{\textit {overflow}}}^{t+T}\), the lower priority is the kth user. The value in descending order indicates that the users’ priority is from high to low. According to the user queues’ different priorities, in the next section, we show how to dynamically allocate the RBs to adjust the service rate for each user queue for improving the system throughput subject to providing QoS guarantee while keeping a certain fairness.