Optimal Admission Control and State Space Reduction in Two-Class Preemptive Loss Systems

ETRI Journal.
2015.
Oct,
37(5):
917-921

- Received : March 20, 2014
- Accepted : May 20, 2015
- Published : October 01, 2015

Download

PDF

e-PUB

PubReader

PPT

Export by style

Article

Metrics

Cited by

TagCloud

We consider a multiserver system with two classes of customers with preemption, which is a widely used system in the analysis of cognitive radio networks. It is known that the optimal admission control for this system is of threshold type. We express the expected total discounted profit using the total number of customers, thus reducing the stochastic optimization problem with a two-dimensional state space to a problem with a one-dimensional birth-and-death structure. An efficient algorithm is proposed for the calculation of the expected total discounted profit.
i
= 1, 2, customers of class
i
arrive according to a Poisson process with intensity
λ_{i}
; these two Poisson processes are assumed to be independent. There are
C
identical parallel servers, of which the service times for all customers are independent and exponentially distributed with mean
μ
^{−1}
, unless terminated prematurely. Class-1 customers (primary users) have preemptive priority over class-2 customers (secondary users). Thus, if all
C
servers are busy upon the arrival of a class-1 customer, then a class-2 customer (if exists) is
preempted
. A preempted class-2 customer is withdrawn from the system permanently. Whenever a class-2 customer is preempted, a preemption cost,
K
, is incurred, while a reward,
R
, is earned whenever a class-2 customer departs successfully. The aim of this study is to find the optimal admission control policy for class-2 customers to maximize the expected total discounted profit. For related works, see
[3]
–
[5]
.
Turhan and others
[3]
–
[4]
showed that the optimal policy is of threshold type and that the threshold depends only on the total number of customers in the system. Furthermore, Turhan and others
[4]
expressed the long-run average profit under the threshold policy in terms of the stationary distribution of the total number of customers in the system. With this, the issue of maximizing the long-run average profit is reduced from a stochastic dynamic programming problem with a two-dimensional Markov process, to a problem with a one-dimensional birth-and-death process.
In this work, we express the expected total discounted profit under the threshold policy using a Markov process representing the total number of customers. Thus, the maximization of the expected total discounted profit is reduced from a stochastic dynamic programming problem with a two-dimensional state space to a problem with a one-dimensional birth-and-death structure. Using the reduced one-dimensional birth-and-death structure, we also provide an efficient algorithm for the calculation of the expected total discounted profit. This algorithm makes it possible to determine the optimal threshold within a short time.
Transition diagram of two-dimensional Markov decision process without admission control.
Let
X
(
t
) and
Y
(
t
) be the number of class-1 and class-2 customers, respectively, at time
t
. Then, (
X
(
t
),
Y
(
t
)) defines the state of the system. Now, let
S
be the state space for (
X
(
t
),
Y
(
t
)); that is, the set of all pairs (
x
,
y
) of non-negative integers such that
x
+
y
≤
C
. Further, let
S
_{1}
be the subset of
S
that consists of preemptive states; that is,
S
_{1}
= {(
x
,
y
) ∈
S
:
x
+
y
=
C
,
y
≥ 1}.
Upon the arrival of a class-2 customer, the system decides whether the customer may be accepted. However, a class-1 customer is always admitted if there is a free server. A class-1 customer who arrives when all the servers are busy is accepted by preempting a class-2 customer, if there exists a class-2 customer in the service. Preempted class-2 customers are lost. An incoming class-1 customer is lost in the case that, on arrival, every server is busy serving class-1 customers. Hence,
X
(
t
) does not depend on any adopted admission policy, though
Y
(
t
) does.
If the discounting rate is
α
,
α
> 0, then the total discounted profit is given by
(1) $$R\underset{0}{\overset{\infty}{{\displaystyle \int}}}{e}^{-\alpha t}\text{d}{D}_{2}(t)-K\underset{0}{\overset{\infty}{{\displaystyle \int}}}{e}^{-\alpha t}{1}_{\left\{\left(X(t-),Y(t-)\right)\in {S}_{1}\right\}}\text{d}{N}_{1}(t),$$
where
D
_{2}
(
t
) is the number of successful class-2 customer departures until time
t
,
N
_{1}
(
t
) is the number of class-1 customer arrivals until time
t
, and 1
_{{·}}
denotes the indicator of {·}; that is, 1
_{{·}}
is “1” if {·} holds, and “0” otherwise.
By applying Palm calculus
[6]
to (1), the expected total discounted profit under a policy
p
, given the initial state (
X
(0),
Y
(0)) = (
X
,
Y
), is given by
(2) $$\begin{array}{ll}{J}_{\alpha}^{p}\left(x,y\right)=\hfill & R\mu {\displaystyle \underset{0}{\overset{\infty}{\int}}{e}^{-\alpha t}}\text{}{\displaystyle \sum _{\left({x}^{\prime},{y}^{\prime}\right)\in S}y{\pi}_{t}^{p}\left({x}^{\prime},{y}^{\prime}|x,y\right)\text{d}t}\hfill \\ \hfill & \text{}-K{\lambda}_{1}{\displaystyle \underset{0}{\overset{\infty}{\int}}{e}^{-\alpha t}}\text{}{\displaystyle \sum _{\left({x}^{\prime},{y}^{\prime}\right)\in {S}_{1}}{\pi}_{t}^{p}\left({x}^{\prime},{y}^{\prime}|x,y\right)\text{d}t},\hfill \end{array}$$
where
X
(
t
),
Y
(
t
)) = (
x
′,
y
′) given that (
X
(0),
Y
(0)) = (
x
,
y
) under policy
p
. The objective of the optimization problem is to find a policy
p
that maximizes the expected total discounted profit,
T
(that is, class-2 customers can be admitted only when the total number of customers is less than
T
), the total number of customers
Z
(
t
) ≡
X
(
t
) +
Y
(
t
) is a Markov process, with the infinitesimal generator
$${q}_{ij}^{T}=\{\begin{array}{ll}{\lambda}_{1}+{\lambda}_{2}{1}_{\left\{i<T\right\}}\hfill & \text{if}j=i+1,\hfill \\ -{\lambda}_{1}-{\lambda}_{2}{1}_{\left\{iT\right\}}-i\mu \hfill & \text{if}j=i,\hfill \\ i\mu \hfill & \text{if}j=i-1,\hfill \\ 0\hfill & \text{otherwise}.\hfill \end{array}$$
We now present the expected total discounted profit under the threshold policy in terms of the infinitesimal generator of
Z
(
t
). Since
Z
(
t
) has a birth-and-death structure, we can reduce the dimension of the state space in the stochastic dynamic programming from two to one.
From this point on, we use
p
is the threshold policy with threshold
T
. Since
Y
(
t
) =
Z
(
t
) −
X
(
t
) and
$$\sum}_{({x}^{\prime},{y}^{\prime})\in S}y{\pi}_{t}^{T}({x}^{\prime},{y}^{\prime}\text{\hspace{0.17em}|\hspace{0.17em}}x,y)\text{\hspace{0.17em}}=\text{\hspace{0.17em}}{\displaystyle \sum}_{{z}^{\prime}=1}^{C}{z}^{\prime}{\psi}_{t}^{T}({z}^{\prime}\text{\hspace{0.17em}|\hspace{0.17em}}x\text{\hspace{0.17em}}+\text{\hspace{0.17em}}y)\text{\hspace{0.17em}}-\text{\hspace{0.17em}}{\displaystyle \sum}_{{x}^{\prime}=1}^{C}{x}^{\prime}{\varphi}_{t}({x}^{\prime}\text{\hspace{0.17em}|\hspace{0.17em}}x)$$
and
$$\sum}_{({x}^{\prime},{y}^{\prime})\in {S}_{1}}{\pi}_{t}^{T}({x}^{\prime},{y}^{\prime}\text{\hspace{0.17em}|\hspace{0.17em}}x,y)={\psi}_{t}^{T}(C\text{\hspace{0.17em}|\hspace{0.17em}}x+y)-{\varphi}_{t}(C\text{\hspace{0.17em}|\hspace{0.17em}}x),$$
where
Z
(
t
) =
z
′ given that
Z
(0) =
z
under the threshold policy with threshold
T
; and
ϕ_{t}
(
x
′ |
x
) is the probability of
X
(
t
) =
x
′ given that
X
(0) =
x
. Note that
ϕ_{t}
(
x
′ |
x
) does not depend on the admission policy for the class-2 customers. Substituting the above equations into (2) yields
z
th component of column vector
f
^{k}
≡ (
α
I
−
Q
^{k}
)
^{−1}
ξ, where ξ is a column vector whose
z
th component is
ξ_{z}
=
Rμz
−
Kλ
_{1}
1
_{{z=C}}
;
z
= 0, 1, ... ,
C
.
Note that we can easily compute
f^{k}
using the birth-and-death structure of
Q
^{k}
. Using the Thomas algorithm
[7]
, which has a linear computational complexity in
C
, we can obtain the following formulae to calculate the expected total discounted profit under the threshold policy with threshold
T
:
Z
(
t
). For
Figs. 2
and
3
, we set
C
= 100;
μ
= 1;
R
= 1;
K
= 2; and (
λ
_{1}
,
λ
_{2}
) = (40, 20), (40, 70), (80, 20), (80, 70), (100, 20), and (100, 70).
Figure 2
shows the plot of the expected total discounted profit with the discounting rate
α
= 1, initial state (
X
(0),
Y
(0)) = (30, 30), and varying threshold
T
. It is observed that, as the threshold
T
increases, the expected total discounted profit also increases until
T
reaches the optimal value, and decreases thereafter. Additionally, the threshold is more dependent on the value of
λ
_{1}
than on that of
λ
_{2}
. Note that the expected total discounted profit can take a negative value if
T
is large, because class-2 customers may initially exist.
Expected total discount profit ${J}_{\alpha}^{T}(x,y)$ with C = 100, μ = 1, R = 1, K = 2, and (X (0), Y (0)) = (30, 30).
Figure 3
shows the relationship between the optimal threshold and the discount rate
α
. The optimal threshold decreases as the class-1 arrival rate (
λ
_{1}
) increases and shows greater dependence on the value of
λ
_{1}
than on that of (
λ
_{2}
). This is consistent with intuition, since preemptions occur more frequently when the class-1 arrival rate (
λ
_{1}
) increases, and other conditions remain the same. Additionally, the optimal threshold decreases as the class-2 arrival rate
λ
_{2}
increases. This is also consistent with intuition, since if the arrival rate of class-2 customers
λ
_{2}
is high, then there is a greater possibility of admitting class-2 customers. Therefore, it is not necessary to admit class-2 customers to the system under inferior circumstances.
Optimal threshold with C = 100, μ = 1, R = 1, and K = 2.
bara@korea.ac.kr
Bara Kim is a professor in the Department of Mathematics, Korea University, Seoul, Rep. of Korea. He received his BS, MS, and PhD degrees in mathematics from the Korea Advanced Institute of Science and Technology, Daejeon, Rep. of Korea. His research interests include probability theory; mathematical finance; insurance models; applied operations research; and queueing theory and its applications.
Corresponding Author ssko@konkuk.ac.kr
Sung-Seok Ko is a professor in the Department of Industrial Engineering, Konkuk University, Seoul, Rep. of Korea. He received his BS degree in industrial engineering from Hanyang University, Seoul, Rep. of Korea, in 1997. He received his MS and PhD degrees in industrial and systems engineering, in 1999 and 2003, respectively, from the School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, USA. His research interests are in operations research; production and inventory control; and parallel processing and collaboration systems.

Preemptive loss system
;
optimal admission policy
;
cognitive radio networks
;
Markov decision process

I. Introduction

Nowadays, although the most important yet scarce resource for wireless communications is the radio spectrum, the utilization of the spectrum is very low in the real world
[1]
. Cognitive radio networks have emerged as a promising technology in the hope of solving this problem
[2]
. Cognitive radio networks contain two types of users — primary and secondary. Primary users have access to the licensed spectrum with a preemptive priority, and secondary users can opportunistically use the spectrum whenever it is not in use by primary users. Hence, to maximize profit, a service provider serving both primary and secondary users must attract as many secondary users as possible, while not diminishing performance for its primary users.
We consider a two-class preemptive loss system, which is widely used in the analysis of cognitive radio networks. There are two classes of customers — primary users and secondary users. For
II. Optimal Admission Problem

- 1. Problem Definition

Since class-1 customers (primary users) and class-2 customers (secondary users) arrive according to independent Poisson processes, and service times are exponentially distributed, the system can be represented as a continuous-time Markov decision process with a two-dimensional state space.
Figure 1
shows the transition diagram for the Markov decision process when there is no admission control.
PPT Slide

Lager Image

π t p ( x ′ , y ′ | x,y)

is the probability of (
J α p (x,y)

.
- 2. Reduced Markov Process under Optimal Policy

Turhan and others
[3]
showed that the optimal policy is of threshold type and that the threshold depends only on the total number of customers in the system. Under a threshold policy with a threshold
Q T =( q ij T );i,j=0,1,…,C

, where
J α T (x,y)

and
π t T ( x ′ , y ′ | x,y )

instead of
J α P (x,y)

and
π t P ( x ′ , y ′ | x,y )

, respectively, if the policy
1 {(X(t),Y(t))∈ S 1 } = 1 {Z(t)=C} − 1 { X(t)=C }

, we have
ψ t T ( z ′ | z)

is the probability of
J α T ( x,y ) = ∫ 0 ∞ e −αt ∑ z ′ ∈1 C ( Rμ z ′ −K λ 1 1 { z ′ =C } ) ψ t T ( z ′ |x+y )dt − ∫ 0 ∞ e −αt ∑ x ′ ∈1 C ( Rμ x ′ −K λ 1 1 { x ′ =C } ) ϕ t ( x ′ |x )dt = f x+y T − f x 0 ,

with
f z k

denoting the
c 0 = − q 01 k α− q 00 k , c i = − q i,i−1 k α− q ii k + c i−1 q i,i−1 k (i=1,2, ... ,C−1), d 0 = ξ 0 α− q 00 k , d i = ξ i + d i−1 q i,i−1 k α− q ii k + c i−1 q i,i−1 k (i=1,2, … ,C), f C k = d C , f i k = d i − c i f i+1 k (i=c−1,c−2, … ,0).

III. Numerical Examples

In this section, we provide some numerical examples of finding the optimal threshold using the birth-and-death process
PPT Slide

Lager Image

PPT Slide

Lager Image

IV. Conclusion

For the multiserver system containing two classes of customers with preemption, the expected total discounted profit has been presented in terms of the infinitesimal generator of the total number of customers. Thus, to maximize the expected total discounted profit, a stochastic dynamic programming problem with a two-dimensional state space has been reduced to a problem with a one-dimensional birth-and-death structure. Using this reduced state space model, we can easily calculate the expected total discounted profit and determine the optimal threshold in a short time. This can be applied to practical problems of cognitive radio networks.
BIO

Wang B.
,
Liu K.J.R.
2011
“Advances in Cognitive Radio Networks: A Survey,”
IEEE J. Sel. Topics Signal Process.
5
(1)
5 -
23
** DOI : 10.1109/JSTSP.2010.2093210**

de Domenico A.
,
Strinati E.C.
,
Di Benedetto M.-G.
2012
“A Survey on MAC Strategies for Cognitive Radio Networks,”
IEEE Commun. Surveys Tutorials
14
(1)
21 -
44
** DOI : 10.1109/SURV.2011.111510.00108**

Turhan A.
,
Alanyali M.
,
Starobinski D.
2012
“Optimal Admission Control in Two-Class Preemptive Loss Systems,”
Operations Res. Lett.
40
(6)
510 -
515
** DOI : 10.1016/j.orl.2012.08.012**

Turhan A.
,
Alanyali M.
,
Starobinski D.
“Optimal Admission Control of Secondary Users in Preemptive Cognitive Radio Networks,”
IEEE Int. Symp. Modeling Optimization Mobile, Ad Hoc, Wireless Netw.
Paderborn, Germany
May 14–18, 2012
138 -
144

Ulukus M.Y.
,
Gullu R.
,
Ormeci L.
2011
“Admission and Termination Control of a Two Class Loss System,”
Stochastic Models
27
(1)
2 -
25
** DOI : 10.1080/15326349.2011.542719**

Fralix B.H.
,
Riaño G.
,
Serfozo R.F.
2007
Time-Dependent Palm Probabilities and Queueing Application
European Institute for Statistics, Probability, Stochastic Operations Research and their Applications

Conte S.D.
,
de Boor C.
1972
“Elementary Numerical Analysis – An Algorithmic Approach,”
McGraw-Hill
New York, NY, USA

Citing 'Optimal Admission Control and State Space Reduction in Two-Class Preemptive Loss Systems
'

@article{ HJTODO_2015_v37n5_917}
,title={Optimal Admission Control and State Space Reduction in Two-Class Preemptive Loss Systems}
,volume={5}
, url={http://dx.doi.org/10.4218/etrij.15.0114.0348}, DOI={10.4218/etrij.15.0114.0348}
, number= {5}
, journal={ETRI Journal}
, publisher={Electronics and Telecommunications Research Institute}
, author={Kim, Bara
and
Ko, Sung-Seok}
, year={2015}
, month={Oct}