Advanced
Optimal Admission Control and State Space Reduction in Two-Class Preemptive Loss Systems
Optimal Admission Control and State Space Reduction in Two-Class Preemptive Loss Systems
ETRI Journal. 2015. Oct, 37(5): 917-921
Copyright © 2015, Electronics and Telecommunications Research Institute (ETRI)
  • Received : March 20, 2014
  • Accepted : May 20, 2015
  • Published : October 01, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Bara Kim
Sung-Seok Ko

Abstract
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.
Keywords
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 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.
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
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
R 0 e αt d D 2 (t)K 0 e αt 1 { ( X(t),Y(t) ) S 1 } 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
J α p ( x,y )= Rμ 0 e αt   ( x , y )S y π t p ( x , y |x,y )dt    K λ 1 0 e αt   ( x , y ) S 1 π t p ( x , y |x,y )dt ,
where
π t p ​(​ x ′ ​, y ′  | x,y​)
is the probability of ( 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,
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 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 T =( q ij T );i,j=0,1,…,C
, where
q ij T ={ λ 1 + λ 2 1 { i<T } if  j=i+1, λ 1 λ 2 1 { i<T } iμ if  j=i, iμ if  j=i1, 0 otherwise.
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
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 p is the threshold policy with threshold T . Since Y ( t ) = Z ( t ) − X ( t ) and
1 {(X(t),Y(t))∈ S 1 } = 1 {Z(t)=C} − 1 { X(t)=C }
, we have
( x , y )S y π t T ( x , y  | x,y)= z =1 C z ψ t T ( z  | x+y) x =1 C x ϕ t ( x  | x)
and
( x , y ) S 1 π t T ( x , y  | x,y)= ψ t T (C | x+y) ϕ t (C | x),
where
ψ t T ( z ′  | z)
is the probability of 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
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 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 1 1 {z=C} ; z = 0, 1, ... , C .
Note that we can easily compute fk 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 :
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 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.
PPT Slide
Lager Image
Expected total discount profit J α 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.
PPT Slide
Lager Image
Optimal threshold with C = 100, μ = 1, R = 1, and K = 2.
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
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.
References
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