Abstract

Simulation of controlled queuing systems and its application to optimal resource management in multiservice cellular networks

Jinsung Choi

LG Information and Communication, KOREA

jinsung@lgic.co.kr

J. A. Silvester

Dept. of Electrical Engineering

University of Southerm California

University Park Los Angeles CA 90089

silvester@usc.edu

Abstract

We consider a controlled queuing model and derive the corresponding Markov decision process for simple G/M/1 call admission controller. As an application of the controlled queuing model, we look into an optimal resource management problem arising in the context of multiservice cellular network with reuse partitioning. In particular, we consider a channel borrowing scheme between zones in two-zone reuse partitioning in a two-class cellular network and investigated the performance of various channel borrowing policies via simulation. We also introduce the simulator developed for controlled queuing systems. Most importantly, we demonstrate that Markov decision processes are well suited to this kind of optimization problem.

Keywords: Controlled queuing, Markov decision process, channel borrowing, stochestic optimization.

1 Introduction

A Controlled queuing model is a useful model for systems requiring control of arrivals, service mechanism or service discipline. These types of systems arise in many contexts, including manufacturing, distributed computer systems, voice and data networks, and vehicular traffic flow. In this paper, we discuss a system requiring control of arrivals and model it as a Markov Decision Process (MDP) and introduce a simulator developed for this model. We apply the model to manage radio spectrum resources efficiently in multiservice cellular networks with reuse partitioning. In this application, arrivals correspond to new call requests originating in cells and the objective of control of arrivals is to maximize the revenue in terms of overall radio spectrum utilization while guaranteeing a call level Quality of Service (QOS) (that is, call blocking probability). Through this application, we show that the controlled queuing model combined with Markov decision process model is well suited to this kind of resource management application.

The study of controlled queuing systems began in the 1970s and a comprehensive discussion can be found in the literatures. Initial attention was directed toward investigations of operational characteristics of system under controls. These investigations were stimulated by ideas and techniques from the theory of Markov decision processes. It turns out that Markov decision processes is a good model for controlled queuing system and some results of optimal admission control problems using Markov decision processes can be found in literature [1] [11] [13]. Markov decision processes provide the theoretical foundations for sequential decision making tasks [1] [11]. A standard approach in the control of queuing systems consists of formulating the problem as a Markov decision process and deriving a functional equation of stochastic dynamic programming, from which the optimal policy is determined.

This paper is organized as follows. We start by introducing a model for queuing systems with control of arrivals in Section II. Then, in Section III and Section IV, the application to be considered is presented together with its corresponding Markov decision process model. Section V is devoted to the developed simulator. Numerical results obtained from the simulation are presented in Section V.

2 A Queuing Model with Control of Arrivals

In queuing systems, a typical control is based on admitting or rejecting arriving customers (Figure 1). Decisions may be based on various information available to the controller and motivated by different incentives. For example, customers may be divided into several classes, according to the reward they yield to the system. These rewards may be very important information to the controller. Also, information about the current state of the system may be available to the controller.

Let us consider the problem of accepting and rejecting customers at a single-server queue in a G/M/1 setting, where interarrival times are i.i.d. random variables with distribution function B(^.) and service times are i.i.d. random variables having the exponential distribution with mean 1/m . A controller regulates the system load by accepting or rejecting arriving customers. If rejected, the arrival leaves the system. This might serve as a simple model for a telephone call admission controller. Let the state space for the natural process denote the number of customers in the system (in service plus in the queue) at any time point. Assume that the system capacity (the size of Eligible Queue in Figure 1) is infinite. Each arriving customer contributes R units of revenue and the system incurs a holding cost at rate f(j) per unit time whenever there are j customers in the system. Decision epochs are the time immediately following an arrival and decisions are required only when customers enter the system. If at some decision epoch the system occupies state sÎ S, where S={ 0, 1, }, the controller must choose an action a from the action set A_s ={0,1} for all sÎ S, where action 0 denotes rejecting an arrival, while action 1 corresponds to accepting an arrival. As a consequence of choosing action a, the next decision epoch occurs at or before some time t, and the system state changes to other state according to the transition probability.

This controlled queuing system can be formulated as a semi-Markov decision process. A Markov decision process is a controlled stochastic process satisfying the Markov property with costs assigned to state transitions. A Markov decision problem (MDP) is a Markov decision process together with a performance criterion as an objective function. In general, a solution to a Markov decision problem is a policy, mapping states to actions, that determines state transitions to minimize the cost according to the performance criterion [1]. A semi-Markov decision process is the embeded Markov decision process that agrees with the natural process only at decision epochs. We prefer to use the semi-Markov decision process model in a queuing admission control model because what transpires between decision epochs provides no relevant information to the controller. The formulation of a semi-Markov decision process consists of determining the five elements: decision epochs, states, actions, rewards and transition probabilities [1]. The definitions of decision epochs, states and actions are already made above and the definitions of the rest are specified as follows.

Let F(t|s,a) denote the probability that the next decision epoch occurs within t time units of the current decision epochs, given that the controller chooses action a from A_s in state s at the current decision epoch. Also, let the quantity p(j|t,s,a) denote the probability that the natural process occupies state j, t time units after a decision epoch, given that action a was chosen in state s at the current decision epoch and that the next decision epoch has not occurred prior to time t. We use the transition probability p(j|t,s,a) to compute cumulative rewards between decision epochs.

Since decisions are made only at arrival times,

where B(^.) is the probability distribution function of the arrival process and is independent of s and a.

In between arrivals, the natural state may change because of service completions. From elementary probability theory, the number of service completions in t units of time follows a Poisson distribution with parameter m t. Consequently, the probabilistic evolution of the state of the natural process can be described by

for s ³ j >0 . Letting

it follows that

When the controller chooses action a in state s, he receives a lump sum reward, k(s,a), given by :

Further it accrues a reward at rate c(k,s,a) as long as the natural process occupies state k, and action a was chosen in state s at the preceding decision epoch.

where k denotes the state of the natural process.

Let Q(t,j|s,a) denote the probability that the next decision epoch occurs at or before time t, and the system state at that decision epoch equals j, given that the previous state was s and action a was taken at the previous epoch. Additionally, let P(j|s,a) denote the transition probability that the next state is j, given that the previous state was s and action a was taken at the previous epoch. Then, for this model, the followings hold ;

3 A Resource Management Problem – Optimal Channel Borrowing in Reuse Partitioning in Multiservice Cellular Networks

In the previous section, we discussed a controlled queuing system in the context of control of arrivals and formulated as a semi-Markov decision process. In this section, we introduce a practical problem as an application of controlled queuing system models, and in the next section we formulate this application using the knowledge obtained from Section II.

We consider an issue in the area of cellular network management. In cellular networks, it is crucial to be able to use the available radio spectrum as efficiently as possible. At the same time, there is a need to provide a certain quality of services (QOS) for mobile users, which may require a sophisticated resource management scheme. Let us consider a multiservice cellular network system with a fixed channel allocation scheme combined with a reuse partitioning scheme. By multiservice, we consider two classes of call traffic, namely broadband and narrowband, where each class can be described by a set of traffic parameters describing the call arrival process, average call duration and the number of channels required for each call.

Reuse partitioning is an effective concept to achieve high spectrum efficiency. In two-zone reuse partitioning, each cell is divided into two concentric subcells or zones, inner zone and outer zone, each corresponding to a different reuse factor (Figure 2) [3][5]. The idea behind reuse partitioning is that because the inner zone is closer to the base station, the power level required for a desired Carrier to Interference Ratio (CIR) in the inner zone can be much lower than the outer zone. As a result, the channel reuse factor of inner zones can be smaller than that of outer zones, thus resulting in higher spectrum efficiency compare to the system without reuse partitioning. For example, in [3], it is shown that the channel capacity can be increased by 30% by using two reuse factors of N_i=3 for inner zones and N_o=9 for outer zones over that achieved by a single reuse factor of N=7.

We can increase radio spectrum utilization further by adding an asymmetric channel borrowing scheme to the reuse partitioning. In this additional scheme, the inner zone can borrow free channels from its neighboring outer zone after all nominal channels assigned to the inner zone are used. By asymmetric, we mean that unused channels may be borrowed from outer zones to inner zones but the opposite, from inner zones to outer zones, is not allowed. This is because channel borrowing from inner zones to outer zones cause so-called channel locking problem, which in turn arises different resource management issues.

In asymmetric channel borrowing between zones, a tradeoff is noticed between increasing overall channel utilization and providing fair service to users in the same cells in terms of call blocking probability. In other words, it is not possible to increase overall channel utilization by channel sharing without degrading the call blocking probability of the users in outer zone. Therefore, what we can do is to control the channel borrowing in such a way that the constraint of outer zone call blocking probability is not violated. Otherwise, the channel borrowing may proliferate to such an extent that the outer zone call blocking probability is jeopardized. We call the controller in charge of this task the channel borrowing controller (CBC). In the following section, we formulate CBC as a Markov decision process.

4 Problem Formulation

The scheme described in the previous section can be viewed as a controlled queuing system having multiple servers and no waiting queue, i.e., if no server is available at the moment a new call originates, that call is blocked immediately (Figure 3). This type of queueing system is also known as a loss model. We classify calls into four categories based on the call originating location and the call class, namely: normal narrowband and broadband calls, which originate in the outer zone and overflow narrowband and broadband calls originating in the inner zone. (Notice that the two terms, outer zone call and normal call, mean the same, and therefore, will be used interchangeably throughout the paper.) More specifically, by overflow calls, we mean inner zone calls making use of borrowed channels from the outer zone, which occurs whenever new calls originate in the inner zone when all channels of the inner zone are busy. All types of calls are modeled as Poisson processes and it is assumed that call durations are exponentially distributed. Each type of calls has different traffic parameters.

In reality, it turns out that a so-called Interrupted Poisson process (IPP) is a more appropriate model for overflow calls in Markovian loss system [14]. However, it is not necessary to incorporate IPP into our model here because it can be approximated by a Poisson process under the condition that the traffic load of overflow calls is significantly much less than that of normal calls. In this system, channels are assigned in the following way. A newly originating normal call is accepted by the system as long as the server is idle. Whereas, a new overflow call coming from the inner zone is controlled by CBC regardless of the type of the call. The detailed operations of CBC will be discussed in the next section. The purpose of CBC is to maximize the overall channel utilization while guaranteeing the outer zone call blocking probability.

With the definitions above, the system ruled by CBC is now ready to be formulated as a Markov decision process. As mentioned earlier, five elements need to be specified in a Markov decision process modeling: states, actions, state transition probabilities, a reward function and decision epochs [1] [11].

These elements are given as follows. The state is defined by the vector s = (s_n, s_b), where s_n, s_b represent the number of on-going narrowband calls, broadband calls in the system respectively. Four kinds of actions are considered in each state, namely: (r, r) meaning rejecting both classes of overflow calls, (a, r) accepting only narrowband overflow calls, (r, a) accepting only broadband overflow calls and (a, a) accepting both classes of overflow calls, respectively. Notice that borrowing decisions are made before the occurrence of an event instead of after. This is necessary to reduce the size of the problem [13]. The state transition probabilities are calculated based on aggregate call arrival or departure rates and they depend on the state and the action chosen. Notice that since the underlying Markov Chain is a continuous-time system, it is required to transform the transition rates to equivalent transition probabilities through uniformization process [1]. They are given as follows after uniformization :

where m_n, m_b represent the call departure rates of narrowband calls and broadband call, respectively l_n, l_b, g_n, g_b denote the arrival rates of normal narrowband calls, normal broadband calls, overflow narrowband calls and overflow broadband calls respectively, I_n, I_b are indicator functions whose value is 0 (reject) or 1 (accept) depending on the action taken.

Channel utilization rate is used as the reward function. The reward function also needs to be transformed through uniformization. The reward function r(s,a) is defined as follows after uniformization ;

where c_n , c_b are the channel requirements of a narrowband, broadband call, respectively.

In order to complete the formulation, one more element needs to be specified, which is a performance criterion. We use the expected average channel utilization, which is calculated based on the reward function, as the performance criterion. The expected value is preferable over other performance criteria such as total reward or discounted total reward because the controller should make decisions frequently and infinitely. In the next section, we simulate the application.

5 Simulation

Simulation is a useful method to get the idea of statistical behavior of the system. In this section, we discuss about the simulator developed to simulate the controlled queuing system described above using discrete event simulation technique for Markovian queuing systems and present several simulation results of our application, optimal channel borrowing control problem. The numerical results show how the QOS statistics change according to channel borrowing control policy. This section is organized as follows; We first start by giving an overview of the simulator developed and discuss policy representation in Section V-B. We then cover the algorithms of CBC and preset numerical results obtained from the simulation. In the last subsection, a method to find the best policy is described.

A. An Overview of the Simulator

The underlying structure is based on typical discrete event simulator, which is one popular method in simulation of Markovian queuing systems. The main components of CQS are the following;

• Event Queue (EQ) and Event Handler (EH) on the upper left

• Channel Assignment Controller (CAC) and Channel Borrowing Controller (CBC) on the middle

• A channel borrowing control policy to be experimented on the upper right

All types of call arrivals including overflow calls and departures, i.e., call hang ups, are treated as events and are put into EQ together with the time stamp indicating when the event should happen or be processed. Whenever an event is extracted from the head of EQ and processed by EH, the next event of the same type is scheduled immediately according to the given probability dis-tribution using random number generator and is put into the tail of EQ. If the event extracted from the head of EQ turns out to be a call arrival, EH calls CAC to serve the call request.

The basic task of the CAC is to assign available channels to users. As mentioned earlier, there are two types of call requests, normal and overflow calls. If the incoming call is a normal call, then CAC checks the current state of the system describing the current channel occupancy and admits the call as long as there are available channel resources or rejects otherwise. In other words, normal calls are blocked only when the system is full. This task has nothing to do with the channel borrowing control policy. If it is an overflow call, then CAC calls its submodule, CBC, and CBC takes care of the overflow call requests. CBC, as is the case above, checks the current state of the system and the specified channel borrowing control policy for that state and accepts or rejects depending on the action associated with that state. In this case, it is possible to reject overflow call request despite the availability of channels to maximize the overall channel utilization while guaranteeing specified call blocking probabilities to normal calls.

After an event has been processed, the control is handed back to EH to continue to process next events. This task lasts until the simulation clock reaches the given maximum simulation time. While processing events, all statistical data are collected and updated. Among them, we are particularly interested in the overall channel utilization and blocking probabilities of normal calls. After the simulation, we compare the resulting blocking probabilities of normal calls and the required ones and see if the given policy made the system meet those QOS measures. In next section, we discuss about how to represent channel borrowing control policies.

B. Representation of Channel Borrowing Control Policy

In this section, we introduce a simple and intuitive way of policy representation using matrix and vector for the simulator. We start with a generic representation of stationary policies for the case of a two service networks with narrowband and broadband calls.

Let p a stationary policy. A policy p specifies the channel borrowing rule to be used throughout the simulation. A policy is called stationary if the rule does not change with time t and can be represented mathematically as follows: Let the channel borrowing control policy p:S ®{a,r}² , be defined by the vector mapping p(s) = (p_n(s), p_b(s))^T , where p_{n or b} (s) = a (or r) signifies that the system will accept (or reject) a future overflow narrowband or broadband calls when it is in state s. Let Ã(P) denote the set of all possible policies. We will discuss the cardinality of Ã(P) later. Using these notation, a policy can be represented in a tabular form with two columns, state column and action column, as an input form for the simulator. This representation is simple and useful in the case of small system. In case of moderate and large systems, however, simpler form is required. If we restrict the policy to the multidimensional threshold (or coordinate convex) type of policies, which is the case in this paper, the tabular form above can be reduced to a matrix as follows. We call this matrix a policy matrix P ;

where v_n , v_bdenote the control vector for narrowband overflow calls and broadband overflow calls respectively and tⁱ_k is the threshold value for type i calls when the number of on-going broadband calls is k. The dimension colomns, N_b, is determined by the total number of channels in the system, C and the required number of channels for a broadband call, c_b as above. In other words, channel borrowing control policies can be represented by a set of two control vectors, v_n and v_b. Vectors can be used because the Markovian system is discrete. If the threshold value tⁱ_k is –1, it means rejection of next type-i overflow calls. Channel Borrowing Controller (CBC) makes decisions based on those threshold values. The threshold value tⁱ_k is not necessarily an integer. If tⁱ_k has an explicit decimal point followed by a fractional part, the fractional part will be taken as the probability of acceptance of a new call in the state s = (s_n , s_b) = (tⁱ_k + l, k) . More detail will be discussed in the Section IV.4.

C. Execution of Channel Borrowing Control

When a new overflow call request comes in the system, first, we examine the current state of the system and see how many on-going broadband calls, s_b, are in the system. Then we take the s_b+1-th column in the policy matrix P as the threshold vector, T. For instance, in the previous example, say, s_b = 2. Then, T would be [2 0]^T, which in turn means that the threshold for overflow narrowband call, q_n, is 2 and the threshold for overflow broadband call, q_b, is 0. Then we check the state of the system again and see if the number of on-going narrowband calls, s_n, is less than or equal to that threshold value of the type of requesting calls. If so, that call will be accepted. Otherwise, it will be rejected. Similar procedures are taken for a new broadband overflow call.

As mentioned earlier, the thresholds, q_n and q_b, may be a number with fractional part. In that case, the thresholds are decomposed as follows ;

q = int(q) + fract(q)

The fractional part, fract(q), is used as the probability of acceptance of a new overflow call in state . s = (s_n , s_b) = (tⁱ_k + l, k) We call any policy having fractional parts in its policy matrix a randomized policy.

D. Simulation Results

Figure 4 through 7 show the simulation results of an example with the total number of channels in the system, C=24. Then the dimension of the policy matrix is 2´ 13. In this example, the traffic load of overflow calls was fixed at 30% of normal calls for both types and the traffic load of broadband calls was fixed at 30% of narrowband calls. The channel requirement of narrowband calls, c_n, is one channel per call and the channel requirement of broadband calls, c_b , is two times bigger than c_n. The average call duration of broadband calls is also two times longer than narrowband calls. The policy matrices used are summarized in Table 1.

Figure 4 - Simulation results for v_n = v₁

Again, -1 in matrix P means call rejection. The results show that the blocking probabilities of overflow calls,a _no and a _bo and the overall channel utilization, u. Among the results we are particularly interested in the normal call blocking probabilities, a _n and a _b because these are the QOS measures that we want to guarantee. We continue the simulation experiments with different channel borrowing policies in Figure 6 through 7. All those control vectors, v_n and v_b, used in these series of simulation experiments are summarized in Table 1. We used five different vectors for v_n and six different vectors for v_b and each chart shows six different combinations of v_n and v_b. We denote these six different control vectors by v₁ through v₆ as shown in Table 1.

As those values of thresholds in the vector imply, vector v₁ is the most generous channel borrowing control vector. On the other hand, v₆ is chosen as the most strict control vector and the other vectors, v₂ through v₅ were chosen between v₁ and v₆. In Figure 4, v_n is fixed at v₁ and the x axis is v_b changing from v₁ through v₆. As shown in the figure, call blocking probabilities of normal calls and narrowband overflow calls tend to decrease with v_b and so does the overall channel utilization. Whereas, the call blocking probability of broadband overflow calls increases rapidly. Apparently this is because as we change v_b from v₁ through v₆, the controller allows less channels for broadband overflow call requests, thus increase its blocking probability and the others, normal calls and narrowband overflow calls take advantage of it, therefore it decreases call blocking probabilities. The overall channel utilization, u, decreases because it is a monotonically increasing function of overall traffic load and this traffic load decreases with varying v_b from v₁ through v₆.

Figure 5 shows similar results. The difference between Figure 4 and ⁷ is v_n. In Figure 5, different v_n is used, which is v₂. All QOS measures except the blocking probability of narrowband overflow calls change just a little bit. Whereas, the blocking probability of narrowband overflow calls is shifted up. This happens because v₂ is stricter than v₁, thus gives higher blocks for narrowband overflow calls. Again, all other calls can benefit by decreasing the blocking probability.

Figure 6 and ⁷ display similar behavior for v_n = v_3,and v₄ respectively. It is evident from all these figures that as we use stricter channel borrowing control policy for overflow calls, their call blocking probabilities get higher and normal calls can lower their call blocking probabilities.

6 Conclusion

We considered a controlled queuing model and derived the corresponding Markov decision process for simple G/M/1 call admission controller. As an application of the controlled queuing model, we looked into an optimal resource management problem arising in the context of multiservice cellular network with reuse partitioning. In particular, we consider a channel borrowing scheme between zones in two-zone reuse partitioning in a two-classes cellular network and investigated the performance of various channel borrowing policies via simulation. We also introduced the simulator developed for controlled queuing system. Most importantly, we demonstrated that Markov decision processes are well suited to this kind of optimization problem.

7 References

Publication Dates