# Discrete-Time Analysis of Cognitive Radio Networks with Nonsaturated Source of Secondary Users

Authors: Vicent Pla; Attahiru S. Alfa; Jorge Martinez-Bauset; Vicente Casares-Giner
Journal: Wireless Communications and Mobile Computing
 (2019)

---

## Abstract

Sensing is a fundamental aspect in cognitive radio networks and one of the most complex issues. In the design of sensing strategies, a number of tradeoffs arise between throughput, interference to primary users, and energy consumption. This paper provides several Markovian models that enable the analysis and evaluation of sensing strategies under a broad range of conditions. The occupation of a channel by primary users is modeled as alternating idle and busy intervals, which are represented by a Markov phase renewal process. The behavior of secondary users is represented mainly through the duration of transmissions, sensing periods, and idle intervals between consecutive sensing periods. These durations are modeled byphase-type distributions, which endow the model with a high degree of generality. Unlike our previous work, here the source of secondary users is nonsaturated, which is a more practical assumption. The arrival of secondary users is modeled by the versatileMarkovian arrival process, and models for both finite and infinite queues are built. Furthermore, the proposed models also incorporate a quite general representation of the resumption policy of an SU transmission after being interrupted by PUs activity. A comprehensive analysis of the proposed models is carried out to derive several key performance indicators in cognitive radio networks. Finally, some numerical results are presented to show that, despite the generality and versatility of the proposed models, their numerical evaluation is perfectly feasible.


---

## Body

## 1. Introduction

The evolution and widespread deployment of wireless communications have generated an incessant and increasing demand for radio spectrum. This, combined with the static spectrum allocation policies that have been in place for quite some time, has led to a situation of spectrum scarcity (i.e., of unassigned frequency bands), at the same time, an important underutilization of a substantial part of the assigned bands.Cognitive Radio (CR) is viewed as the enabling technology for dynamic spectrum access, which would allow solving the seeming paradox between spectrum scarcity and underutilization [1]. The basic idea of CR is to allow the unlicensed users, known as secondary users (SUs), to access licensed channels opportunistically when they are not in use by licensed users, known as primary users (PUs). This way, the interference that SUs produce to PUs should be kept to a minimum.In this context,white space refers to spectrum that is not used by the PUs during a certain time interval at a specific location. The key to success for CR consists of effectively and efficiently sensing radio channels to detectwhite space when it occurs. An ideal, although unrealizable, sensing strategy would detect a portion of white space right after it starts and, likewise, would detect the end of it immediately after the transmission of a PU begins. Furthermore, such an ideal sensing strategy would only consume the minimum amount of energy needed for sensing. There has been a considerable long list of research papers over the years dealing with how to manage and implement CR. For details see [2] and other references therein.As noted in [3], sensing is a major and challenging issue in CR networks. The choice of detection parameters poses a series of tradeoffs between achievable throughput, energy consumption, and interference caused PUs [4–13]. In general, if SUs spend more time on channel sensing, they obtain lower throughput, but the interference caused to PUs is also lowered. This is referred to as thesensing-throughput tradeoff (STT), which has been studied in a large number of papers (e.g., [4, 5, 9] and references therein). Furthermore, more channel sensing also raises the consumption of energy, which constitutes a critical aspect in certain scenarios (e.g., sensor networks). Consequently, a significant number of studies have considered energy efficiency a crucial part of spectrum sensing [7, 8, 10–13].Several aspects come into play while considering sensing. Some examples are the duration of sensing periods, the width of the frequency band being scanned to search for unused channels, etc. For details see [2]. The vast majority of the models developed for studying CR networks, and specifically for spectrum sensing, assume that busy and idle times follow an exponential distribution (or geometric in discrete time); for example, see [14, 15] and all the above references to sensing studies. Using measurements, the authors of [16] showed that the channel idle time can be modeled by a lognormal distribution. This result was confirmed in [17], where it is shown that idle times follow a lognormal distribution for long durations, and a geometric distribution for short durations. Correlations between idle and busy times were also overlooked by most the previous papers. However, one could logically expect that some correlation exists between different intervals, as has in fact been noted in [17]. Our previous work in [2] was one of the first few ones to introduce correlation and also allow more general intervals.The research on sensing strategies for CR networks is not new, and neither is the application of mathematical modeling for analysis and optimization of those strategies. However, the models presented in this paper embody a number of contributions which stem from the generality of the model assumptions. Our purpose in this paper is to propose a number of models that enable the analysis and evaluation of sensing strategies in cognitive radio networks under a broad range of conditions. More specifically, a Markov phase renewal process [18] is used to model the channel availability for SUs. This allows to consider a wide variety of distributions for the duration of idle and busy intervals and also to capture correlations between consecutive intervals. The authors of [19] proposed a similar model for the activity of PUs. However, correlations between different intervals were not considered in their model.The behavior of SUs is represented mainly through the duration of transmissions, sensing periods, and idle intervals between consecutive sensing periods. These durations are modeled byphase-type distributions [18], which endow the model with a high degree of generality. In the literature of mathematical modeling, it is widely acknowledged that phase-type distributions offer an excellent compromise between applicability and tractability.Our model of SUs also allows sensing errors, which can be misdetections and false alarms. For both of them, two different situations are distinguished, depending on whether the SU is only sensing or sensing and transmitting. This allows us to capture a broad range of SUs sensing capabilities.However, most important in this paper is that we now have to introduce the arrival process of the SUs since the source is no longer saturated. We used the Markovian arrival process (MAP) to represent the SU arrival process. The MAP is a very versatile arrival process which can capture correlations and still allow modeling and computational tractability.In our previous paper [2] on this class of problems, we assume that the source of SUs is saturated (i.e., there is always at least an SU waiting and ready to transmit). That assumption is not too realistic, even though it does give us an idea of the best we can achieve if there are always some SUs looking to transmit. In this current paper, we have relaxed that assumption. This makes the model more realistic while making it slightly more challenging as now we need to introduce an arrival process for the SUs. In addition, this new model creates a situation where a channel could be idle simply because there are no PUs or SUs needing to use it. These are the main contributions of this paper.The rest of this paper is organized as follows. Section2 introduces the model of the channel from the perspective of the SUs. The model of the secondary network, which includes the behavior of SUs, is described in Section 3. In Section 4 we describe the models for the complete system and their analysis when sensing is assumed to be ideal; this assumption is relaxed in Section 5. Some numerical results are presented in Section 6 to exemplify the capabilities of the proposed models and to show the feasibility of their numerical evaluation. Finally, the paper is concluded in Section 7.


## 2. Channel Availability

We consider a single channel that can be idle or busy from the perspective of the SUs. The activity of PUs in this channel is described by a discrete-time Markov chain (DTMC)X
k with state space {
1,2
,
…
,
n
b
,
n
b
+
1
,
…
,
n
b
+
n
i
}. The channel isbusy (b) if X
k
∈
1,2
,
…
,
n
b, andidle (i) if X
k
∈
1,2
,
…
,
n
b. We assume that during a time slot the condition of the channel changes at most once.Let the matrixD
b represent the transitions between busy states and d
b
i represent the transitions from busy to idle states. Similarly, D
i represents the transitions between idle states, and d
i
b represents the transitions from idle to busy states. The matrices D
b and D
i are substochastic and of orders n
b and n
i, respectively.Based on this, the transition matrix ofX
k can be written as(1)
D
=
D
b
d
b
i
d
i
b
D
i
.


## 3. Secondary Network

This section discusses SUs actions and how SUs interact with PUs through the channel status. Throughout this paper, sometimes we use “the SU” to refer to the set of all the SUs that can use the channel or to the SU that is at the head of the waiting line of SUs. We assume there is some coordination mechanism among SUs to perform channel sensing and to arrange channel access. Although this coordination mechanism is not trivial, its study is beyond the scope of this paper.The SU can be in one of the following three modes:sleeping,sensing, ortransmitting. The continuous period of time that the SU remains in one of these modes is called acycle orperiod. Thus, we talk about, for example, asleeping period or asensing cycle. Next, we detail the characteristics of each type of cycle and how they alternate between them.(a) Sleeping. The duration of a sleeping period is modeled by the phase-type distribution (
δ
,
L
) of order n
l. A sleeping period is always followed by a sensing cycle.(b) Sensing. During a sensing cycle, the SU performs a series of consecutive channel state measurements. If a measurement senses the channel as busy, the sensing period is interrupted and the SU enters the sleeping mode. The maximum number of measurements that would be taken is defined by the PH distribution with representation (
β
,
S
), of order n
s. If the channel is sensed as idle in all the measurements of the cycle, the SU can initiate a transmitting period.(c) Transmitting. During a transmitting cycle the SU attempts to transmit a message. The required transmission time (i.e., the number of time slots) to transmit the message is given by the PH distribution with representation (
α
,
T
) of order n
t. If the channel becomes busy and the SU is capable (can sense the channel while transmitting) of detecting it, the message transmission is interrupted and the SU switches to sleeping mode. If the transmission of the message is fully completed, the SU goes into sensing mode.The SUs arrive according to a Markovian arrival process (MAP) represented by two substochastic matricesG
0 and G
1 of order n
a. Then, the mean arrival rate, λ, is given as λ
=
π
G
G
1
1, where π
G is the probability vector satisfying π
G
=
π
G
(
G
0
+
G
1
) and π
G
1
=
1 and 1 is a column vector of ones of appropriate dimensions.An SU that arrives and finds the channel busy waits in a buffer of sizeN
≤
∞.If an SU is in service when a PU arrives, the SU’s service is interrupted since the PU has preemptive priority. Now we specify the resumption policy followed by SUs when a message transmission was interrupted by PUs activity. This policy is described by matrixQ with elements Q
i
j. Suppose the SU’s service was interrupted in phase i, let its service restart in phase j with probability Q
i
j at resumption. It is clear that if it is a preemptive resume then Q
=
I, whereas if it is a preemptive repeat then Q
=
1
α. Hence, the matrix Q is a general representation.


## 4. System Model I: Ideal Sensing

For the sake of clarity, we first assume that the SU receives perfect knowledge of the state of the channel. In Section5 we relax that condition and assume that there could be errors in the sensing carried out by the SU.Sensing takes place only when there is an SU in the system waiting to get access. Hence, when there is an SU in the system either it is receiving service because there is white space or it is waiting. The waiting could be because the channel is busy with PUs, there are other SUs ahead of it, or it is sensing the system for white space.Here we assume that the time needed to perform a channel measurement cannot be neglected compared to the transmission time of a data unit. The length of a time slot is set so that a sensing measurement can be performed and know the result by the end of the slot. A conservative approach is applied to establish the outcome of the measurement: a sensing measurement taken during the time slot[
k
-
1
,
k
) does not returnidle as a result if the channel was busy at time instants k
-
1 or k.Although, as mentioned above, the duration of a single measurement cannot be neglected, in this section we assume that SUs can sense and transmit simultaneously. This could reflect instances in which SUs are equipped with two radios. The case in which SUs cannot transmit and sense simultaneously can be covered by the model with imperfect sensing described in Section5.


### 4.1. Head-of-the-Line (HoL) SU

Even though we are mainly interested in the nonsaturated case, first we consider the saturated case, from which we obtain the DTMC that constitutes the basis for the nonsaturated model.Let the states of this system be classified as shown in Table1.Table 1
State classification in the saturated system.
state
state #
Channel
SU
phases defining internal states
number of internal states
1
busy
sleeping
BPH, LPH, TPH∗
n
b
n
l
(
n
t
+
1
)
2
busy
sensing
BPH, TPH∗
n
b
1
(
n
t
+
1
)
3
idle
sleeping
IPH, LPH, TPH∗
n
i
n
l
(
n
t
+
1
)
4
idle
sensing
IPH, SPH, TPH∗
n
i
n
s
(
n
t
+
1
)
5
idle
transmitting
IPH, TPH
n
i
n
t
BPH: channel busy phase; IPH: channel idle phase; LPH: SU sleeping phase; SPH: SU sensing phase; TPH: SU trans. phase; TPH∗: TPH (extended) at interruption.In all states, we keep track of the channel phase (either a busy or an idle phase). When the SU is transmitting, we need to keep track of the transmission phase. Similarly, when the SU is sleeping (sensing) we need to keep track of the sleeping (sensing) phase, and also of how the last transmission epoch ended. A transmission epoch can finish because the channel becomes busy, or because the SU transmission finishes. In the first case, we record at which of then
t transmission phases the SU was interrupted, and an additional phase is used to indicate that the SU transmission finished completely. Thus, in total n
t
+
1 phases are used to represent how the last transmission epoch ended. Note also that when the channel is busy and the SU starts a sensing cycle, only the first sensing phase is required as the SU switches to the sleeping mode after the first sensing measure. Naturally, this situation will change when we consider imperfect sensing later on.Then we have the following discrete-time Markov chain (DTMC) for the saturated case:(2)
P
1
s
a
t
=
D
b
⊗
L
⊗
I
D
b
⊗
l
⊗
I
d
b
i
⊗
L
⊗
I
d
b
i
⊗
l
β
⊗
I
0
D
b
⊗
δ
⊗
I
0
d
b
i
⊗
δ
⊗
I
0
0
d
i
b
⊗
L
⊗
I
d
i
b
⊗
l
⊗
I
D
i
⊗
L
⊗
I
D
i
⊗
l
β
⊗
I
0
d
i
b
⊗
1
δ
⊗
I
0
0
D
i
⊗
S
⊗
I
D
i
⊗
s
⊗
Q
∗
d
i
b
⊗
δ
⊗
T
¯
0
0
D
i
⊗
β
⊗
t
¯
D
i
⊗
T
,where T
¯
=
I
0, t
¯
=
0
t, and Q
∗
=
Q
α.This transition matrix captures the full behavior of this saturated system with general preemptive discipline.However, in order to study the nonsaturated system, we need to extract, from the above matrix, the following four matrices:(3)
H
1
=
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
D
i
⊗
β
⊗
t
¯
0
,
(4)
H
0
=
P
1
s
a
t
-
H
1
,
(5)
F
0
=
0
D
b
⊗
0
1
×
n
t
1
0
d
b
i
⊗
β
⊗
0
1
×
n
t
1
0
0
d
i
b
⊗
0
1
×
n
t
1
0
D
i
⊗
β
⊗
0
1
×
n
t
1
0
,and(6)
F
1
=
0
0
0
0
0
0
0
0
0
D
i
⊗
t
.The matricesH
0 and H
1 are used to capture the transitions that affect the state of the channel and the state of the head-of-line SU: H
0 corresponds to the case where the head-of-line SU does not finish its service and H
1 to the one when it does. In H
0 and H
1, it is assumed that there is at least one SU in the queue (at both the initial and the final state). In a similar manner, the transitions from and to an empty queue are captured by F
0 and F
1, respectively. Note that the arrival process has not been taken into account yet.


### 4.2. Number of SUs in the System: The Nonsaturated Case

In order to study the distribution of the number of SUs in the system, we use a quasi-birth-and-death (QBD) Markov chain structure. Thelevel of the QBD represents the number of SUs in the system, and the phases in each level represent the rest of the system state information. Specifically, for level l
=
0 (i.e., when the queue is empty) the phases of the level represent the phase of the arrival process (i.e., the MAP) and the phase of the channel. For the rest of levels (l
=
1,2
,
…), the phases represent the phase of the MAP plus the same state information as in the saturated case.We now consider the cases of finite buffer (N
<
∞) and infinite buffer (N
=
∞) separately.


#### 4.2.1. Stationary Behavior for Finite Buffer (N
<
∞)

When the buffer size is finite, we have the discrete-time Markov chain (DTMC) with transition matrix(7)
P
=
B
C
E
A
1
A
0
A
2
A
1
A
0
A
2
A
1
A
0
⋱
⋱
⋱
A
2
A
1
+
A
0
,where(8)
B
=
G
0
⊗
D
,
(9)
C
=
G
1
⊗
F
0
,
(10)
E
=
G
0
⊗
F
1
,and(11)
A
0
=
G
1
⊗
H
0
,
(12)
A
1
=
G
0
⊗
H
0
+
G
1
⊗
H
1
,
(13)
A
2
=
G
0
⊗
H
1
.Note that the number of block rows and block columns of the transition matrix P coincides with the number of levels of the QBD, that is, N
+
1.Let the stationary vector associated with this DTMC bex
=
[
x
0
,
x
1
,
…
,
x
N
]. Then we have(14)
x
=
x
P
,
x
1
=
1
.This vector x exists and is unique, provided the DTMC represented by P is irreducible.The vectorx can be obtained by standard methods used for finite structured DTMCs (e.g., theblock state reduction, theblock state reduction, or thefolding algorithm). Given the vector x, we can easily obtain the following performance measures.(a) Mean Number of SUs in the System. Let X be the number of SUs in the system at steady state, and let(15)
p
k
=
P
X
=
k
=
x
i
1
,
k
=
0
,
…
,
N
.Then,(16)
E
X
=
∑
i
=
1
N
i
p
i
.(b) Loss Probability. The probability that an SU is lost because there is no buffer space to accommodate it is referred to as the loss probability, and it is given as(17)
P
L
=
x
N
A
0
1
λ
.(c) Throughput (or Effective Utilization). Let us define the throughput, γ, as the probability that an SU is transmitting during a time slot of white space or, equivalently, the mean number of SU transmitting slots per time unit.Let us first introduce(18)
π
=
π
1
π
2
π
3
π
4
π
5
=
∑
n
=
1
N
x
n
·
1
⊗
Iwhich contains the marginal probabilities for states of the saturated system; first the marginal distribution of the phases for levels above 0 is computed, and then the phase of the arrival process is dropped by summing along its dimension (right multiplication by 1
⊗
I).Now an expression for the throughput can be written as(19)
γ
=
π
5
1
=
∑
n
=
1
N
x
·
1
⊗
I
0
0
0
0
1
=
∑
n
=
1
N
x
·
1
⊗
0
0
0
0
1
.(d) Goodput. Goodput γ
g is the mean number of useful data units transmitted by an SU per unit of time. Even though we still are assuming perfect sensing, not all transmitted data units can be considered useful. For example, the data unit transmitted during a slot in which the presence of the PU was detected does not represent a useful transmission. Moreover, depending on the service resumption policy, a part or all of the transmitted units up to this point may not be useful transmissions either.Nonetheless, if the system is stable (and it is clearly the case whenN
<
∞) all SUs accepted to the system are eventually served in full. Therefore, the goodput can be easily obtained as(20)
γ
g
=
λ
1
-
P
l
E
L
t
,where L
t is the maximum length of an SU transmission phase, and its mean value is given by E
[
L
t
]
=
α
(
I
-
T
)
-
1
1.(e) Distribution of the Sojourn Time of SUs That Joined the Queue. Here we develop the expressions to obtain the distribution of the time an SU spends in the system (W), which includes the time spent at the head of the line. A similar approach could be followed to derive the distribution for the waiting time until the SU reaches the head of the line.Lety
=
[
y
0
,
y
1
,
…
,
y
N
-
1
] be the probability vector as seen by arriving customers that are not blocked. Then(21)
y
0
=
λ
1
-
P
l
-
1
x
0
G
1
⊗
F
0
+
x
1
G
1
⊗
H
1
,
(22)
y
n
=
λ
1
-
P
l
-
1
x
n
G
1
⊗
H
0
+
x
n
+
1
G
1
⊗
H
1
,
n
=
1
,
…
,
N
-
1
.We now consider the block absorbing DTMC with transition matrix(23)
P
~
=
I
I
⊗
F
1
I
⊗
H
0
I
⊗
H
1
I
⊗
H
0
⋱
⋱
I
⊗
H
1
I
⊗
H
0
,with the initial probabilities given by[
0
,
y
0
,
y
1
,
…
,
y
N
-
1
].This DTMC can be further simplified by leaving out the DTMC the phase of the arrival process. By doing this, the transition matrix becomes(24)
P
^
=
I
F
1
H
0
H
1
H
0
⋱
⋱
H
1
H
0
,and the initial probabilities are given by(25)
z
0
0
=
0
,
(26)
z
n
0
=
y
n
-
1
1
⊗
I
,
n
=
1
,
…
,
N
,or equivalently,(27)
z
0
0
=
0
,
(28)
z
1
0
=
λ
1
-
P
l
-
1
x
0
G
1
1
⊗
F
0
+
x
1
G
1
1
⊗
H
1
,
(29)
z
n
0
=
λ
1
-
P
l
-
1
x
n
-
1
G
1
1
⊗
H
0
+
x
n
G
1
1
⊗
H
1
,
n
=
2
,
…
,
N
,Now, the probabilities at time k can be obtained recursively as(30)
z
0
k
=
z
0
k
-
1
I
+
z
1
k
-
1
F
1
=
z
1
k
-
1
F
1
,
(31)
z
n
k
=
z
n
k
-
1
H
0
+
z
n
+
1
k
-
1
H
1
,
n
=
1
,
…
,
N
-
1
,
(32)
z
N
k
=
z
N
k
-
1
H
0and, from here, the distribution of the sojourn time follows easily(33)
P
W
≤
k
=
z
0
k
1
k
=
0,1
,
…
.


#### 4.2.2. Stationary Behavior for Infinite Buffer (N
=
∞)

Suppose now the buffer space for the SUs is unlimited. Then we have the associated transition matrix for the DTMC given as(34)
P
=
B
C
E
A
1
A
0
A
2
A
1
A
0
A
2
A
1
A
0
⋱
⋱
⋱
.The associated stationary vectorx
=
[
x
0
,
x
1
,
…
] can be obtained by using the matrix-geometric method. First, we point out that this stationary vector x exists and is unique, provided that the standard stability conditions are met. These conditions are given as follows. Let A
=
A
0
+
A
1
+
A
2 with π
=
π
A
,
π
1
=
1. We know that provided A is irreducible, then π exists and it is unique. The conditions for the vector x to exist and be unique are that π
A
2
1
>
π
A
0
1
. Provided these conditions are met, we have(35)
x
i
+
1
=
x
i
R
,
i
≥
1
,where R is the minimal nonnegative solution to the matrix quadratic equation(36)
R
=
A
0
+
R
A
1
+
R
2
A
2
.The boundary vectors x
0 and x
1 are obtained from solving(37)
x
0
,
x
1
=
x
0
,
x
1
B
C
E
A
1
+
R
A
2
,normalized by(38)
x
0
1
+
x
1
I
-
R
-
1
1
=
1
.From the knowledge of the vector x we can easily obtain the performance measures of interest, which are the same as in the finite buffer case in Section 4.2.1. Here, clearly, P
l
=
0. The expressions for the other performance measures are given below; we focus only on the changes with respect to Section 4.2.1.(a) Mean Number of SUs in the System. Let X be the number of SUs in the system and p
k
=
x
i
1
k
≥
0 its distribution, then (39)
p
0
=
x
0
1
,
p
k
=
x
k
1
=
x
1
R
k
-
1
1
,
k
≥
1
,and(40)
E
X
=
∑
i
=
1
∞
i
p
i
=
x
1
∑
i
=
1
∞
i
R
i
-
1
1
=
x
1
I
-
R
-
2
1
.(b) Throughput. Now(41)
π
1
π
2
π
3
π
4
π
5
=
∑
n
=
1
∞
x
n
·
1
⊗
I
=
x
1
I
-
R
-
1
1
⊗
I
,and thus,(42)
γ
=
∑
n
=
1
∞
π
5
1
=
x
1
I
-
R
-
1
1
⊗
0
0
0
0
1
.(c) Goodput
(43)
γ
g
=
λ
E
L
t
=
λ
α
I
-
T
-
1
1
.(d) Distribution of the Sojourn Time of SUs That Joined the Queue
(44)
P
W
≤
k
=
z
0
k
1
.As in Section 4.2.1,(45)
z
0
k
=
z
0
k
-
1
I
+
z
1
k
-
1
F
1
,
(46)
z
n
k
=
z
n
k
-
1
H
0
+
z
n
+
1
k
-
1
H
1
,
n
>
0
,and(47)
z
0
0
=
0
,
(48)
z
1
0
=
λ
-
1
x
0
G
1
1
⊗
F
0
+
x
1
G
1
1
⊗
H
1
,
(49)
z
n
0
=
x
n
-
1
J
=
x
n
-
2
R
J
=
⋯
=
x
1
R
n
-
2
J
,
n
>
1
,where J
=
λ
-
1
(
(
G
1
1
)
⊗
H
0
+
R
(
(
G
1
1
)
⊗
H
1
)
).


### 4.3. Comparison of Sensing Strategies

In order to compare any two sensing strategies, we need to determine what performance measure is going to be used for that purpose. In the finite buffer case, we can compare, for the two sensing strategies, the number of SUs in the system, the throughput, the loss probabilities, etc. Each of those comparisons requires that we compute the stationary vector associated with the finite state Markov chain.However, if we assume that the buffer size is large enough to be approximated by an infinite buffer system, then we can just compare the distribution of the number of SUs in the system. For a service provider, the most relevant performance measure for comparison in that case is the tail behavior of the system. As done in practice, we can assume that when one system is dominant in queue length, then it is also dominant in waiting times. Thus, for a quick comparison of different sensing strategies, we can use the tail behavior and skip the steps that require us to obtain the vectorx or even the matrix R.


#### 4.3.1. Tail Probabilities for Comparing Sensing Strategies

Now we assume that our buffer size is infinite and show how to compare the tail behavior of the number of SUs in the system.For a quasi-birth-and-death (QBD) type of Markov chain, we know from the literature that the probability that the number of customers in the system is at leastk, σ
k, can be approximated as(50)
p
k
=
σ
η
k
+
o
η
k
,
as
k
→
∞
,where η is called the decay rate and is equal to Perron Frobenius eigenvalue of the matrix R, and σ is a constant which depends on the boundary behavior of the Markov chain. The decay rate η can be obtained as the unique solution in (
0,1
) to the nonlinear equation(51)
η
=
χ
η
,where χ
(
z
) is the maximal absolute eigenvalue of the matrix(52)
A
z
=
A
0
+
z
A
1
+
z
2
A
2
,
z
≤
1
.Generally, η can be computed using the bisection method.


#### 4.3.2. Hazard Rate Order for Comparisons

In this section, we present a simple tool for comparing different sensing strategies. Since the primary interest is in not letting very long queues build up for the secondary users, a good measure is the tail probability of the number of SUs in the system. The hazard rate order is a useful tool for this purpose.Consider two discrete random variablesX and Y. Shaked and Shanthikumar showed in [20, Theorem (1.B.7)] that X is less than Y based on hazard rate, that is, X
≤
h
r
Y, if(53)
P
X
≥
k
∑
i
≥
k
P
X
≥
i
≤
P
Y
≥
k
∑
i
≥
k
P
Y
≥
i
,
∀
k
≥
0
.Similarly, we sayX is stochastically less than Y (i.e., X
≤
s
t
Y) if(54)
P
X
≥
k
≤
P
Y
≥
k
,
∀
k
≥
0
.In [20, Theorem (1.B.1)] they further showed that(55)
if
X
≤
h
r
Y
,
then
X
≤
s
t
Y
.Now consider two sensing strategiesA and B, with the number of SUs in the system given as X
A and X
B, respectively. Letting p
k
(
A
) an p
k
(
B
) be the associated tail probabilities as mentioned in Section 4.3.1, and also with η
j, and σ
j
,
j
=
A
,
B being the respective decay rates and constants, then we can write(56)
p
k
j
=
σ
j
η
j
k
+
o
η
j
k
,
as
k
→
∞
,
j
=
A
,
B
.Let us now assume that there is a K
<
∞ such that o
(
η
j
K
+
k
)
=
0
,
k
≥
0, then we can say that(57)
p
K
+
k
j
=
σ
j
η
j
K
+
k
,
∀
k
≥
0
,
j
=
A
,
B
.For the purpose of comparing two sensing strategies, we apply the following theorem.Theorem 1.
If our threshold of the number in the system isK, then(58)
X
A
≤
s
t
X
B
if
η
A
≥
η
B
.Proof.
This is based on the fact that(59)
P
X
≥
k
∑
i
≥
k
P
X
≥
i
=
σ
η
k
∑
i
≥
k
σ
η
i
=
σ
η
k
σ
η
k
1
-
η
-
1
=
1
-
η
,
k
≥
K
.In summary, we have, for a threshold of K,(60)
X
A
≤
s
t
X
B
if
η
A
≥
η
B
.


## 4.1. Head-of-the-Line (HoL) SU

Even though we are mainly interested in the nonsaturated case, first we consider the saturated case, from which we obtain the DTMC that constitutes the basis for the nonsaturated model.Let the states of this system be classified as shown in Table1.Table 1
State classification in the saturated system.
state
state #
Channel
SU
phases defining internal states
number of internal states
1
busy
sleeping
BPH, LPH, TPH∗
n
b
n
l
(
n
t
+
1
)
2
busy
sensing
BPH, TPH∗
n
b
1
(
n
t
+
1
)
3
idle
sleeping
IPH, LPH, TPH∗
n
i
n
l
(
n
t
+
1
)
4
idle
sensing
IPH, SPH, TPH∗
n
i
n
s
(
n
t
+
1
)
5
idle
transmitting
IPH, TPH
n
i
n
t
BPH: channel busy phase; IPH: channel idle phase; LPH: SU sleeping phase; SPH: SU sensing phase; TPH: SU trans. phase; TPH∗: TPH (extended) at interruption.In all states, we keep track of the channel phase (either a busy or an idle phase). When the SU is transmitting, we need to keep track of the transmission phase. Similarly, when the SU is sleeping (sensing) we need to keep track of the sleeping (sensing) phase, and also of how the last transmission epoch ended. A transmission epoch can finish because the channel becomes busy, or because the SU transmission finishes. In the first case, we record at which of then
t transmission phases the SU was interrupted, and an additional phase is used to indicate that the SU transmission finished completely. Thus, in total n
t
+
1 phases are used to represent how the last transmission epoch ended. Note also that when the channel is busy and the SU starts a sensing cycle, only the first sensing phase is required as the SU switches to the sleeping mode after the first sensing measure. Naturally, this situation will change when we consider imperfect sensing later on.Then we have the following discrete-time Markov chain (DTMC) for the saturated case:(2)
P
1
s
a
t
=
D
b
⊗
L
⊗
I
D
b
⊗
l
⊗
I
d
b
i
⊗
L
⊗
I
d
b
i
⊗
l
β
⊗
I
0
D
b
⊗
δ
⊗
I
0
d
b
i
⊗
δ
⊗
I
0
0
d
i
b
⊗
L
⊗
I
d
i
b
⊗
l
⊗
I
D
i
⊗
L
⊗
I
D
i
⊗
l
β
⊗
I
0
d
i
b
⊗
1
δ
⊗
I
0
0
D
i
⊗
S
⊗
I
D
i
⊗
s
⊗
Q
∗
d
i
b
⊗
δ
⊗
T
¯
0
0
D
i
⊗
β
⊗
t
¯
D
i
⊗
T
,where T
¯
=
I
0, t
¯
=
0
t, and Q
∗
=
Q
α.This transition matrix captures the full behavior of this saturated system with general preemptive discipline.However, in order to study the nonsaturated system, we need to extract, from the above matrix, the following four matrices:(3)
H
1
=
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
D
i
⊗
β
⊗
t
¯
0
,
(4)
H
0
=
P
1
s
a
t
-
H
1
,
(5)
F
0
=
0
D
b
⊗
0
1
×
n
t
1
0
d
b
i
⊗
β
⊗
0
1
×
n
t
1
0
0
d
i
b
⊗
0
1
×
n
t
1
0
D
i
⊗
β
⊗
0
1
×
n
t
1
0
,and(6)
F
1
=
0
0
0
0
0
0
0
0
0
D
i
⊗
t
.The matricesH
0 and H
1 are used to capture the transitions that affect the state of the channel and the state of the head-of-line SU: H
0 corresponds to the case where the head-of-line SU does not finish its service and H
1 to the one when it does. In H
0 and H
1, it is assumed that there is at least one SU in the queue (at both the initial and the final state). In a similar manner, the transitions from and to an empty queue are captured by F
0 and F
1, respectively. Note that the arrival process has not been taken into account yet.


## 4.2. Number of SUs in the System: The Nonsaturated Case

In order to study the distribution of the number of SUs in the system, we use a quasi-birth-and-death (QBD) Markov chain structure. Thelevel of the QBD represents the number of SUs in the system, and the phases in each level represent the rest of the system state information. Specifically, for level l
=
0 (i.e., when the queue is empty) the phases of the level represent the phase of the arrival process (i.e., the MAP) and the phase of the channel. For the rest of levels (l
=
1,2
,
…), the phases represent the phase of the MAP plus the same state information as in the saturated case.We now consider the cases of finite buffer (N
<
∞) and infinite buffer (N
=
∞) separately.


### 4.2.1. Stationary Behavior for Finite Buffer (N
<
∞)

When the buffer size is finite, we have the discrete-time Markov chain (DTMC) with transition matrix(7)
P
=
B
C
E
A
1
A
0
A
2
A
1
A
0
A
2
A
1
A
0
⋱
⋱
⋱
A
2
A
1
+
A
0
,where(8)
B
=
G
0
⊗
D
,
(9)
C
=
G
1
⊗
F
0
,
(10)
E
=
G
0
⊗
F
1
,and(11)
A
0
=
G
1
⊗
H
0
,
(12)
A
1
=
G
0
⊗
H
0
+
G
1
⊗
H
1
,
(13)
A
2
=
G
0
⊗
H
1
.Note that the number of block rows and block columns of the transition matrix P coincides with the number of levels of the QBD, that is, N
+
1.Let the stationary vector associated with this DTMC bex
=
[
x
0
,
x
1
,
…
,
x
N
]. Then we have(14)
x
=
x
P
,
x
1
=
1
.This vector x exists and is unique, provided the DTMC represented by P is irreducible.The vectorx can be obtained by standard methods used for finite structured DTMCs (e.g., theblock state reduction, theblock state reduction, or thefolding algorithm). Given the vector x, we can easily obtain the following performance measures.(a) Mean Number of SUs in the System. Let X be the number of SUs in the system at steady state, and let(15)
p
k
=
P
X
=
k
=
x
i
1
,
k
=
0
,
…
,
N
.Then,(16)
E
X
=
∑
i
=
1
N
i
p
i
.(b) Loss Probability. The probability that an SU is lost because there is no buffer space to accommodate it is referred to as the loss probability, and it is given as(17)
P
L
=
x
N
A
0
1
λ
.(c) Throughput (or Effective Utilization). Let us define the throughput, γ, as the probability that an SU is transmitting during a time slot of white space or, equivalently, the mean number of SU transmitting slots per time unit.Let us first introduce(18)
π
=
π
1
π
2
π
3
π
4
π
5
=
∑
n
=
1
N
x
n
·
1
⊗
Iwhich contains the marginal probabilities for states of the saturated system; first the marginal distribution of the phases for levels above 0 is computed, and then the phase of the arrival process is dropped by summing along its dimension (right multiplication by 1
⊗
I).Now an expression for the throughput can be written as(19)
γ
=
π
5
1
=
∑
n
=
1
N
x
·
1
⊗
I
0
0
0
0
1
=
∑
n
=
1
N
x
·
1
⊗
0
0
0
0
1
.(d) Goodput. Goodput γ
g is the mean number of useful data units transmitted by an SU per unit of time. Even though we still are assuming perfect sensing, not all transmitted data units can be considered useful. For example, the data unit transmitted during a slot in which the presence of the PU was detected does not represent a useful transmission. Moreover, depending on the service resumption policy, a part or all of the transmitted units up to this point may not be useful transmissions either.Nonetheless, if the system is stable (and it is clearly the case whenN
<
∞) all SUs accepted to the system are eventually served in full. Therefore, the goodput can be easily obtained as(20)
γ
g
=
λ
1
-
P
l
E
L
t
,where L
t is the maximum length of an SU transmission phase, and its mean value is given by E
[
L
t
]
=
α
(
I
-
T
)
-
1
1.(e) Distribution of the Sojourn Time of SUs That Joined the Queue. Here we develop the expressions to obtain the distribution of the time an SU spends in the system (W), which includes the time spent at the head of the line. A similar approach could be followed to derive the distribution for the waiting time until the SU reaches the head of the line.Lety
=
[
y
0
,
y
1
,
…
,
y
N
-
1
] be the probability vector as seen by arriving customers that are not blocked. Then(21)
y
0
=
λ
1
-
P
l
-
1
x
0
G
1
⊗
F
0
+
x
1
G
1
⊗
H
1
,
(22)
y
n
=
λ
1
-
P
l
-
1
x
n
G
1
⊗
H
0
+
x
n
+
1
G
1
⊗
H
1
,
n
=
1
,
…
,
N
-
1
.We now consider the block absorbing DTMC with transition matrix(23)
P
~
=
I
I
⊗
F
1
I
⊗
H
0
I
⊗
H
1
I
⊗
H
0
⋱
⋱
I
⊗
H
1
I
⊗
H
0
,with the initial probabilities given by[
0
,
y
0
,
y
1
,
…
,
y
N
-
1
].This DTMC can be further simplified by leaving out the DTMC the phase of the arrival process. By doing this, the transition matrix becomes(24)
P
^
=
I
F
1
H
0
H
1
H
0
⋱
⋱
H
1
H
0
,and the initial probabilities are given by(25)
z
0
0
=
0
,
(26)
z
n
0
=
y
n
-
1
1
⊗
I
,
n
=
1
,
…
,
N
,or equivalently,(27)
z
0
0
=
0
,
(28)
z
1
0
=
λ
1
-
P
l
-
1
x
0
G
1
1
⊗
F
0
+
x
1
G
1
1
⊗
H
1
,
(29)
z
n
0
=
λ
1
-
P
l
-
1
x
n
-
1
G
1
1
⊗
H
0
+
x
n
G
1
1
⊗
H
1
,
n
=
2
,
…
,
N
,Now, the probabilities at time k can be obtained recursively as(30)
z
0
k
=
z
0
k
-
1
I
+
z
1
k
-
1
F
1
=
z
1
k
-
1
F
1
,
(31)
z
n
k
=
z
n
k
-
1
H
0
+
z
n
+
1
k
-
1
H
1
,
n
=
1
,
…
,
N
-
1
,
(32)
z
N
k
=
z
N
k
-
1
H
0and, from here, the distribution of the sojourn time follows easily(33)
P
W
≤
k
=
z
0
k
1
k
=
0,1
,
…
.


### 4.2.2. Stationary Behavior for Infinite Buffer (N
=
∞)

Suppose now the buffer space for the SUs is unlimited. Then we have the associated transition matrix for the DTMC given as(34)
P
=
B
C
E
A
1
A
0
A
2
A
1
A
0
A
2
A
1
A
0
⋱
⋱
⋱
.The associated stationary vectorx
=
[
x
0
,
x
1
,
…
] can be obtained by using the matrix-geometric method. First, we point out that this stationary vector x exists and is unique, provided that the standard stability conditions are met. These conditions are given as follows. Let A
=
A
0
+
A
1
+
A
2 with π
=
π
A
,
π
1
=
1. We know that provided A is irreducible, then π exists and it is unique. The conditions for the vector x to exist and be unique are that π
A
2
1
>
π
A
0
1
. Provided these conditions are met, we have(35)
x
i
+
1
=
x
i
R
,
i
≥
1
,where R is the minimal nonnegative solution to the matrix quadratic equation(36)
R
=
A
0
+
R
A
1
+
R
2
A
2
.The boundary vectors x
0 and x
1 are obtained from solving(37)
x
0
,
x
1
=
x
0
,
x
1
B
C
E
A
1
+
R
A
2
,normalized by(38)
x
0
1
+
x
1
I
-
R
-
1
1
=
1
.From the knowledge of the vector x we can easily obtain the performance measures of interest, which are the same as in the finite buffer case in Section 4.2.1. Here, clearly, P
l
=
0. The expressions for the other performance measures are given below; we focus only on the changes with respect to Section 4.2.1.(a) Mean Number of SUs in the System. Let X be the number of SUs in the system and p
k
=
x
i
1
k
≥
0 its distribution, then (39)
p
0
=
x
0
1
,
p
k
=
x
k
1
=
x
1
R
k
-
1
1
,
k
≥
1
,and(40)
E
X
=
∑
i
=
1
∞
i
p
i
=
x
1
∑
i
=
1
∞
i
R
i
-
1
1
=
x
1
I
-
R
-
2
1
.(b) Throughput. Now(41)
π
1
π
2
π
3
π
4
π
5
=
∑
n
=
1
∞
x
n
·
1
⊗
I
=
x
1
I
-
R
-
1
1
⊗
I
,and thus,(42)
γ
=
∑
n
=
1
∞
π
5
1
=
x
1
I
-
R
-
1
1
⊗
0
0
0
0
1
.(c) Goodput
(43)
γ
g
=
λ
E
L
t
=
λ
α
I
-
T
-
1
1
.(d) Distribution of the Sojourn Time of SUs That Joined the Queue
(44)
P
W
≤
k
=
z
0
k
1
.As in Section 4.2.1,(45)
z
0
k
=
z
0
k
-
1
I
+
z
1
k
-
1
F
1
,
(46)
z
n
k
=
z
n
k
-
1
H
0
+
z
n
+
1
k
-
1
H
1
,
n
>
0
,and(47)
z
0
0
=
0
,
(48)
z
1
0
=
λ
-
1
x
0
G
1
1
⊗
F
0
+
x
1
G
1
1
⊗
H
1
,
(49)
z
n
0
=
x
n
-
1
J
=
x
n
-
2
R
J
=
⋯
=
x
1
R
n
-
2
J
,
n
>
1
,where J
=
λ
-
1
(
(
G
1
1
)
⊗
H
0
+
R
(
(
G
1
1
)
⊗
H
1
)
).


## 4.2.1. Stationary Behavior for Finite Buffer (N
<
∞)

When the buffer size is finite, we have the discrete-time Markov chain (DTMC) with transition matrix(7)
P
=
B
C
E
A
1
A
0
A
2
A
1
A
0
A
2
A
1
A
0
⋱
⋱
⋱
A
2
A
1
+
A
0
,where(8)
B
=
G
0
⊗
D
,
(9)
C
=
G
1
⊗
F
0
,
(10)
E
=
G
0
⊗
F
1
,and(11)
A
0
=
G
1
⊗
H
0
,
(12)
A
1
=
G
0
⊗
H
0
+
G
1
⊗
H
1
,
(13)
A
2
=
G
0
⊗
H
1
.Note that the number of block rows and block columns of the transition matrix P coincides with the number of levels of the QBD, that is, N
+
1.Let the stationary vector associated with this DTMC bex
=
[
x
0
,
x
1
,
…
,
x
N
]. Then we have(14)
x
=
x
P
,
x
1
=
1
.This vector x exists and is unique, provided the DTMC represented by P is irreducible.The vectorx can be obtained by standard methods used for finite structured DTMCs (e.g., theblock state reduction, theblock state reduction, or thefolding algorithm). Given the vector x, we can easily obtain the following performance measures.(a) Mean Number of SUs in the System. Let X be the number of SUs in the system at steady state, and let(15)
p
k
=
P
X
=
k
=
x
i
1
,
k
=
0
,
…
,
N
.Then,(16)
E
X
=
∑
i
=
1
N
i
p
i
.(b) Loss Probability. The probability that an SU is lost because there is no buffer space to accommodate it is referred to as the loss probability, and it is given as(17)
P
L
=
x
N
A
0
1
λ
.(c) Throughput (or Effective Utilization). Let us define the throughput, γ, as the probability that an SU is transmitting during a time slot of white space or, equivalently, the mean number of SU transmitting slots per time unit.Let us first introduce(18)
π
=
π
1
π
2
π
3
π
4
π
5
=
∑
n
=
1
N
x
n
·
1
⊗
Iwhich contains the marginal probabilities for states of the saturated system; first the marginal distribution of the phases for levels above 0 is computed, and then the phase of the arrival process is dropped by summing along its dimension (right multiplication by 1
⊗
I).Now an expression for the throughput can be written as(19)
γ
=
π
5
1
=
∑
n
=
1
N
x
·
1
⊗
I
0
0
0
0
1
=
∑
n
=
1
N
x
·
1
⊗
0
0
0
0
1
.(d) Goodput. Goodput γ
g is the mean number of useful data units transmitted by an SU per unit of time. Even though we still are assuming perfect sensing, not all transmitted data units can be considered useful. For example, the data unit transmitted during a slot in which the presence of the PU was detected does not represent a useful transmission. Moreover, depending on the service resumption policy, a part or all of the transmitted units up to this point may not be useful transmissions either.Nonetheless, if the system is stable (and it is clearly the case whenN
<
∞) all SUs accepted to the system are eventually served in full. Therefore, the goodput can be easily obtained as(20)
γ
g
=
λ
1
-
P
l
E
L
t
,where L
t is the maximum length of an SU transmission phase, and its mean value is given by E
[
L
t
]
=
α
(
I
-
T
)
-
1
1.(e) Distribution of the Sojourn Time of SUs That Joined the Queue. Here we develop the expressions to obtain the distribution of the time an SU spends in the system (W), which includes the time spent at the head of the line. A similar approach could be followed to derive the distribution for the waiting time until the SU reaches the head of the line.Lety
=
[
y
0
,
y
1
,
…
,
y
N
-
1
] be the probability vector as seen by arriving customers that are not blocked. Then(21)
y
0
=
λ
1
-
P
l
-
1
x
0
G
1
⊗
F
0
+
x
1
G
1
⊗
H
1
,
(22)
y
n
=
λ
1
-
P
l
-
1
x
n
G
1
⊗
H
0
+
x
n
+
1
G
1
⊗
H
1
,
n
=
1
,
…
,
N
-
1
.We now consider the block absorbing DTMC with transition matrix(23)
P
~
=
I
I
⊗
F
1
I
⊗
H
0
I
⊗
H
1
I
⊗
H
0
⋱
⋱
I
⊗
H
1
I
⊗
H
0
,with the initial probabilities given by[
0
,
y
0
,
y
1
,
…
,
y
N
-
1
].This DTMC can be further simplified by leaving out the DTMC the phase of the arrival process. By doing this, the transition matrix becomes(24)
P
^
=
I
F
1
H
0
H
1
H
0
⋱
⋱
H
1
H
0
,and the initial probabilities are given by(25)
z
0
0
=
0
,
(26)
z
n
0
=
y
n
-
1
1
⊗
I
,
n
=
1
,
…
,
N
,or equivalently,(27)
z
0
0
=
0
,
(28)
z
1
0
=
λ
1
-
P
l
-
1
x
0
G
1
1
⊗
F
0
+
x
1
G
1
1
⊗
H
1
,
(29)
z
n
0
=
λ
1
-
P
l
-
1
x
n
-
1
G
1
1
⊗
H
0
+
x
n
G
1
1
⊗
H
1
,
n
=
2
,
…
,
N
,Now, the probabilities at time k can be obtained recursively as(30)
z
0
k
=
z
0
k
-
1
I
+
z
1
k
-
1
F
1
=
z
1
k
-
1
F
1
,
(31)
z
n
k
=
z
n
k
-
1
H
0
+
z
n
+
1
k
-
1
H
1
,
n
=
1
,
…
,
N
-
1
,
(32)
z
N
k
=
z
N
k
-
1
H
0and, from here, the distribution of the sojourn time follows easily(33)
P
W
≤
k
=
z
0
k
1
k
=
0,1
,
…
.


## 4.2.2. Stationary Behavior for Infinite Buffer (N
=
∞)

Suppose now the buffer space for the SUs is unlimited. Then we have the associated transition matrix for the DTMC given as(34)
P
=
B
C
E
A
1
A
0
A
2
A
1
A
0
A
2
A
1
A
0
⋱
⋱
⋱
.The associated stationary vectorx
=
[
x
0
,
x
1
,
…
] can be obtained by using the matrix-geometric method. First, we point out that this stationary vector x exists and is unique, provided that the standard stability conditions are met. These conditions are given as follows. Let A
=
A
0
+
A
1
+
A
2 with π
=
π
A
,
π
1
=
1. We know that provided A is irreducible, then π exists and it is unique. The conditions for the vector x to exist and be unique are that π
A
2
1
>
π
A
0
1
. Provided these conditions are met, we have(35)
x
i
+
1
=
x
i
R
,
i
≥
1
,where R is the minimal nonnegative solution to the matrix quadratic equation(36)
R
=
A
0
+
R
A
1
+
R
2
A
2
.The boundary vectors x
0 and x
1 are obtained from solving(37)
x
0
,
x
1
=
x
0
,
x
1
B
C
E
A
1
+
R
A
2
,normalized by(38)
x
0
1
+
x
1
I
-
R
-
1
1
=
1
.From the knowledge of the vector x we can easily obtain the performance measures of interest, which are the same as in the finite buffer case in Section 4.2.1. Here, clearly, P
l
=
0. The expressions for the other performance measures are given below; we focus only on the changes with respect to Section 4.2.1.(a) Mean Number of SUs in the System. Let X be the number of SUs in the system and p
k
=
x
i
1
k
≥
0 its distribution, then (39)
p
0
=
x
0
1
,
p
k
=
x
k
1
=
x
1
R
k
-
1
1
,
k
≥
1
,and(40)
E
X
=
∑
i
=
1
∞
i
p
i
=
x
1
∑
i
=
1
∞
i
R
i
-
1
1
=
x
1
I
-
R
-
2
1
.(b) Throughput. Now(41)
π
1
π
2
π
3
π
4
π
5
=
∑
n
=
1
∞
x
n
·
1
⊗
I
=
x
1
I
-
R
-
1
1
⊗
I
,and thus,(42)
γ
=
∑
n
=
1
∞
π
5
1
=
x
1
I
-
R
-
1
1
⊗
0
0
0
0
1
.(c) Goodput
(43)
γ
g
=
λ
E
L
t
=
λ
α
I
-
T
-
1
1
.(d) Distribution of the Sojourn Time of SUs That Joined the Queue
(44)
P
W
≤
k
=
z
0
k
1
.As in Section 4.2.1,(45)
z
0
k
=
z
0
k
-
1
I
+
z
1
k
-
1
F
1
,
(46)
z
n
k
=
z
n
k
-
1
H
0
+
z
n
+
1
k
-
1
H
1
,
n
>
0
,and(47)
z
0
0
=
0
,
(48)
z
1
0
=
λ
-
1
x
0
G
1
1
⊗
F
0
+
x
1
G
1
1
⊗
H
1
,
(49)
z
n
0
=
x
n
-
1
J
=
x
n
-
2
R
J
=
⋯
=
x
1
R
n
-
2
J
,
n
>
1
,where J
=
λ
-
1
(
(
G
1
1
)
⊗
H
0
+
R
(
(
G
1
1
)
⊗
H
1
)
).


## 4.3. Comparison of Sensing Strategies

In order to compare any two sensing strategies, we need to determine what performance measure is going to be used for that purpose. In the finite buffer case, we can compare, for the two sensing strategies, the number of SUs in the system, the throughput, the loss probabilities, etc. Each of those comparisons requires that we compute the stationary vector associated with the finite state Markov chain.However, if we assume that the buffer size is large enough to be approximated by an infinite buffer system, then we can just compare the distribution of the number of SUs in the system. For a service provider, the most relevant performance measure for comparison in that case is the tail behavior of the system. As done in practice, we can assume that when one system is dominant in queue length, then it is also dominant in waiting times. Thus, for a quick comparison of different sensing strategies, we can use the tail behavior and skip the steps that require us to obtain the vectorx or even the matrix R.


### 4.3.1. Tail Probabilities for Comparing Sensing Strategies

Now we assume that our buffer size is infinite and show how to compare the tail behavior of the number of SUs in the system.For a quasi-birth-and-death (QBD) type of Markov chain, we know from the literature that the probability that the number of customers in the system is at leastk, σ
k, can be approximated as(50)
p
k
=
σ
η
k
+
o
η
k
,
as
k
→
∞
,where η is called the decay rate and is equal to Perron Frobenius eigenvalue of the matrix R, and σ is a constant which depends on the boundary behavior of the Markov chain. The decay rate η can be obtained as the unique solution in (
0,1
) to the nonlinear equation(51)
η
=
χ
η
,where χ
(
z
) is the maximal absolute eigenvalue of the matrix(52)
A
z
=
A
0
+
z
A
1
+
z
2
A
2
,
z
≤
1
.Generally, η can be computed using the bisection method.


### 4.3.2. Hazard Rate Order for Comparisons

In this section, we present a simple tool for comparing different sensing strategies. Since the primary interest is in not letting very long queues build up for the secondary users, a good measure is the tail probability of the number of SUs in the system. The hazard rate order is a useful tool for this purpose.Consider two discrete random variablesX and Y. Shaked and Shanthikumar showed in [20, Theorem (1.B.7)] that X is less than Y based on hazard rate, that is, X
≤
h
r
Y, if(53)
P
X
≥
k
∑
i
≥
k
P
X
≥
i
≤
P
Y
≥
k
∑
i
≥
k
P
Y
≥
i
,
∀
k
≥
0
.Similarly, we sayX is stochastically less than Y (i.e., X
≤
s
t
Y) if(54)
P
X
≥
k
≤
P
Y
≥
k
,
∀
k
≥
0
.In [20, Theorem (1.B.1)] they further showed that(55)
if
X
≤
h
r
Y
,
then
X
≤
s
t
Y
.Now consider two sensing strategiesA and B, with the number of SUs in the system given as X
A and X
B, respectively. Letting p
k
(
A
) an p
k
(
B
) be the associated tail probabilities as mentioned in Section 4.3.1, and also with η
j, and σ
j
,
j
=
A
,
B being the respective decay rates and constants, then we can write(56)
p
k
j
=
σ
j
η
j
k
+
o
η
j
k
,
as
k
→
∞
,
j
=
A
,
B
.Let us now assume that there is a K
<
∞ such that o
(
η
j
K
+
k
)
=
0
,
k
≥
0, then we can say that(57)
p
K
+
k
j
=
σ
j
η
j
K
+
k
,
∀
k
≥
0
,
j
=
A
,
B
.For the purpose of comparing two sensing strategies, we apply the following theorem.Theorem 1.
If our threshold of the number in the system isK, then(58)
X
A
≤
s
t
X
B
if
η
A
≥
η
B
.Proof.
This is based on the fact that(59)
P
X
≥
k
∑
i
≥
k
P
X
≥
i
=
σ
η
k
∑
i
≥
k
σ
η
i
=
σ
η
k
σ
η
k
1
-
η
-
1
=
1
-
η
,
k
≥
K
.In summary, we have, for a threshold of K,(60)
X
A
≤
s
t
X
B
if
η
A
≥
η
B
.


## 4.3.1. Tail Probabilities for Comparing Sensing Strategies

Now we assume that our buffer size is infinite and show how to compare the tail behavior of the number of SUs in the system.For a quasi-birth-and-death (QBD) type of Markov chain, we know from the literature that the probability that the number of customers in the system is at leastk, σ
k, can be approximated as(50)
p
k
=
σ
η
k
+
o
η
k
,
as
k
→
∞
,where η is called the decay rate and is equal to Perron Frobenius eigenvalue of the matrix R, and σ is a constant which depends on the boundary behavior of the Markov chain. The decay rate η can be obtained as the unique solution in (
0,1
) to the nonlinear equation(51)
η
=
χ
η
,where χ
(
z
) is the maximal absolute eigenvalue of the matrix(52)
A
z
=
A
0
+
z
A
1
+
z
2
A
2
,
z
≤
1
.Generally, η can be computed using the bisection method.


## 4.3.2. Hazard Rate Order for Comparisons

In this section, we present a simple tool for comparing different sensing strategies. Since the primary interest is in not letting very long queues build up for the secondary users, a good measure is the tail probability of the number of SUs in the system. The hazard rate order is a useful tool for this purpose.Consider two discrete random variablesX and Y. Shaked and Shanthikumar showed in [20, Theorem (1.B.7)] that X is less than Y based on hazard rate, that is, X
≤
h
r
Y, if(53)
P
X
≥
k
∑
i
≥
k
P
X
≥
i
≤
P
Y
≥
k
∑
i
≥
k
P
Y
≥
i
,
∀
k
≥
0
.Similarly, we sayX is stochastically less than Y (i.e., X
≤
s
t
Y) if(54)
P
X
≥
k
≤
P
Y
≥
k
,
∀
k
≥
0
.In [20, Theorem (1.B.1)] they further showed that(55)
if
X
≤
h
r
Y
,
then
X
≤
s
t
Y
.Now consider two sensing strategiesA and B, with the number of SUs in the system given as X
A and X
B, respectively. Letting p
k
(
A
) an p
k
(
B
) be the associated tail probabilities as mentioned in Section 4.3.1, and also with η
j, and σ
j
,
j
=
A
,
B being the respective decay rates and constants, then we can write(56)
p
k
j
=
σ
j
η
j
k
+
o
η
j
k
,
as
k
→
∞
,
j
=
A
,
B
.Let us now assume that there is a K
<
∞ such that o
(
η
j
K
+
k
)
=
0
,
k
≥
0, then we can say that(57)
p
K
+
k
j
=
σ
j
η
j
K
+
k
,
∀
k
≥
0
,
j
=
A
,
B
.For the purpose of comparing two sensing strategies, we apply the following theorem.Theorem 1.
If our threshold of the number in the system isK, then(58)
X
A
≤
s
t
X
B
if
η
A
≥
η
B
.Proof.
This is based on the fact that(59)
P
X
≥
k
∑
i
≥
k
P
X
≥
i
=
σ
η
k
∑
i
≥
k
σ
η
i
=
σ
η
k
σ
η
k
1
-
η
-
1
=
1
-
η
,
k
≥
K
.In summary, we have, for a threshold of K,(60)
X
A
≤
s
t
X
B
if
η
A
≥
η
B
.


## 5. System Model II: Imperfect Sensing

In this model we allow sensing errors, which can be misdetections and false alarms. A misdetection (false alarm) occurs when the channel is considered to be idle (busy) when it is actually busy (idle). In addition, for both of them (misdetection and false alarm) we differentiate two different types, depending on whether the SU is only sensing (type 1) or sensing and transmitting (type 2). The probability that a type-i misdetection occurs is ϕ
i, with ϕ
¯
i
=
1
-
ϕ
i and i
=
1,2; and the probability that a type-i false alarm occurs is θ
i, with θ
¯
i
=
1
-
θ
i and i
=
1,2; Table 2 shows a summary of these probabilities.Table 2
Sensing errors and their probabilities.
Misdetection
False alarm
Type 1
ϕ
1
θ
1
Type 2
ϕ
2
θ
2We add another state to the set from Model I (channel busy, SU transmitting). Now, the states of this system are classified as shown in Table3.Table 3
State classification in the saturated system with sensing errors.
state
state #
channel
SU
phases defining internal states
number of internal states
1
busy
sleeping
BPH, LPH,T
P
H
∗
n
b
n
l
(
n
t
+
1
)
2
busy
sensing
BPH, SPH,T
P
H
∗
n
b
n
s
(
n
t
+
1
)
3
busy
transmitting
BPH, TPH
n
b
n
t
4
idle
sleeping
IPH, LPH,T
P
H
∗
n
i
n
l
(
n
t
+
1
)
5
idle
sensing
IPH, SPH,T
P
H
∗
n
i
n
s
(
n
t
+
1
)
6
idle
transmitting
IPH, TPH
n
i
n
t
BPH: channel busy phase; IPH: channel idle phase; LPH: SU sleeping phase; SPH: SU sensing phase; TPH: SU trans. phase;T
P
H
∗: TPH (extended) at interruption.Unlike in Model I, in (channel busy, SU sensing) we now have to keep track of the sensing phase. The case in which the system is saturated with SUs is considered first.The associated transition matrix is(61)
P
2
s
a
t
=
D
b
⊗
L
⊗
I
D
b
⊗
l
β
⊗
I
0
d
b
i
⊗
L
⊗
I
d
b
i
⊗
l
β
⊗
I
0
ϕ
¯
1
D
b
⊗
1
δ
⊗
I
ϕ
1
D
b
⊗
S
⊗
I
ϕ
1
D
b
⊗
s
⊗
Q
∗
ϕ
¯
1
d
b
i
⊗
1
δ
⊗
I
ϕ
1
d
b
i
⊗
S
⊗
I
ϕ
1
d
b
i
⊗
s
⊗
Q
∗
ϕ
2
¯
D
b
⊗
δ
⊗
T
¯
ϕ
2
D
b
⊗
β
⊗
t
¯
ϕ
2
D
b
⊗
T
ϕ
¯
2
d
b
i
⊗
δ
⊗
T
¯
ϕ
2
d
b
i
⊗
β
⊗
t
¯
ϕ
2
d
b
i
⊗
T
d
i
b
⊗
L
⊗
I
d
i
b
⊗
l
β
⊗
I
0
D
i
⊗
L
⊗
I
D
i
⊗
l
β
⊗
I
0
ϕ
¯
1
d
i
b
⊗
1
δ
⊗
I
ϕ
1
d
i
b
⊗
S
⊗
I
ϕ
1
d
i
b
⊗
s
⊗
Q
∗
θ
1
D
i
⊗
1
δ
⊗
I
θ
¯
1
D
i
⊗
S
⊗
I
θ
¯
1
D
i
⊗
s
⊗
Q
∗
ϕ
¯
2
d
i
b
⊗
δ
⊗
T
¯
ϕ
2
d
i
b
⊗
β
⊗
t
¯
ϕ
2
d
i
b
⊗
T
θ
2
D
i
⊗
δ
⊗
T
¯
θ
¯
2
D
i
⊗
β
⊗
t
¯
θ
¯
2
D
i
⊗
T
.As we did in Model I, in order to study the case of nonsaturated SUs we need to extract, from the above matrix, the following set of matrices:(62)
F
0
=
0
D
b
⊗
β
⊗
0
1
×
n
t
1
0
0
d
b
i
⊗
β
⊗
0
1
×
n
t
1
0
0
d
i
b
⊗
β
⊗
0
1
×
n
t
1
0
0
D
i
⊗
β
⊗
0
1
×
n
t
1
0
,
(63)
F
1
=
0
0
0
0
ϕ
2
D
b
⊗
t
ϕ
2
d
b
i
⊗
t
0
0
0
0
ϕ
2
d
i
b
⊗
t
θ
¯
2
D
i
⊗
t
.
(64)
H
1
=
0
0
0
0
0
0
0
0
0
0
0
0
0
ϕ
2
D
b
⊗
β
⊗
t
¯
0
0
ϕ
2
d
b
i
⊗
β
⊗
t
¯
0
0
0
0
0
0
0
0
0
0
0
0
0
0
ϕ
2
d
i
b
⊗
β
⊗
t
¯
0
0
θ
¯
2
D
i
⊗
β
⊗
t
¯
0
,
(65)
H
0
=
P
2
s
a
t
-
H
1
.Using the same ideas as in the case of Model I, we can easily study the nonsaturated cases, both finite and infinite buffer situations. We skip this for Model II as it is merely a repetition of the procedure used in Model I.


## 6. Numerical Results

In this section, we present some results to exemplify the capabilities of the proposed models and to show the feasibility of their numerical evaluation.Since the source of SUs is not saturated, the arrival process of SUs must be taken into account. In our numerical results, the arrival of SUs is modeled by aplatoon arrival process (PAP) in which the following magnitudes follow geometric distributions: interplatoon times (mean value, 100); intraplatoon interarrival times (mean value, 20); and number of arrivals in a platoon (mean value, N
p); see [18, pp. 49&#x2013;50] for further details. The mean number of arrivals in a platoon, N
p, is varied from 1 to 40 so that the arrival rate of SUs varies from 0.01 to 0.0455 arrivals per time slot. Then, the matrices of the MAP are(66)
G
0
=
1
-
1
100
0
0
1
-
1
20
,
(67)
G
1
=
1
N
p
1
100
1
-
1
N
p
1
100
1
N
p
1
20
1
-
1
N
p
1
20
.The number of slots in a sensing cycle has a deterministic value equal to 4, that is,(68)
n
s
=
4
,
(69)
β
=
1
0
0
0
,
(70)
S
=
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
.The duration of a sleep period is uniformly distributed in{
1,2
,
…
,
10
}:(71)
n
l
=
10
,
(72)
δ
=
0.1
0.1
⋯
0.1
,
(73)
L
=
0
1
0
1
0
⋱
⋱
1
0
.The duration of an uninterrupted SU transmission follows a negative binomial distribution with mean 10 slots and variance2.5:(74)
n
t
=
8
,
(75)
α
=
1
0
0
0
0
0
0
0
,
(76)
T
=
0.6
0.4
0.6
0.4
⋱
⋱
0.6
0.4
.A preemptive repeat scheme is used when the transmission of an SU is interrupted by the transmission of a PU. Thus,(77)
Q
=
1
α
=
1
0
⋯
0
1
0
⋯
0
⋮
⋮
⋮
1
0
⋯
0
.Finally, we consider ideal sensing,ϕ
1
=
ϕ
2
=
θ
1
=
θ
2
=
0, and four different buffer sizes, N
=
1,10,100
,
∞.As in [2], the model proposed in [21] is used for channel occupancy. This model exhibits a self-similar behavior over an adjustable range of time-scales. Then, the transition matrix in (1) becomes(78)
D
=
​
1
-
∑
k
=
1
n
-
1
1
a
k
1
a
1
a
2
⋯
1
a
n
-
1
b
a
1
-
b
a
b
a
2
1
-
b
a
2
⋮
⋱
b
a
n
-
1
1
-
b
a
n
-
1where n, a, and b are the parameters of the model. The range of time-scales where the process shows a self-similar behavior can be adjusted the value of parameter n. Once the value of n is set, the values of a and b can be determined by fitting the channel utilization factor ρ
P
U
=
(
1
-
1
/
b
)
/
(
1
-
1
/
b
n
), and the average burst length E
[
B
]
=
(
∑
k
=
1
n
-
1
a
-
k
)
-
1. The following values have been considered here: n
=
8, ρ
P
U
=
0.2, and E
[
B
]
=
10.The chosen channel model, arrival process, and PH distributions do not intend to fit any specific scenario characterized by empirical results. Instead, our purpose is to show how a wide variety of distributions and characterizations can be easily incorporated into our models and to show the feasibility of their numerical evaluation. For this purpose, the channel model and the PH distributions that have been used are of a relatively high number of phases and, as shown in this section, the resulting DTMC is still amenable to numerical evaluation using a conventional desktop computer. Using distributions and models with a similar number of phases would allow obtaining a good fit of the available data in a broad variety of practical cases, while the required computational effort would be comparable to that of the examples shown here.Figures1, 2, 3, and 4 show, respectively, the mean number of SUs in the system, loss probability, throughput, and goodput. All of them are represented as a function of the mean number of arrivals in a platoon (N
p) for different sizes of the buffer. When N
p increases so do the rate and burstiness of the arrival process of SUs. Thus, as it may be expected, the curves for in all four graphs exhibit an increasing trend.Figure 1
Mean number of SUs in the system,E
[
X
].Figure 2
Loss probability,P
L.Figure 3
Throughput,γ.Figure 4
Goodput,γ
g.In the cases where buffer size is finite, the value of the mean number of SUs in the system (Figure1) rapidly saturates to about half the size of the buffer. This observation is consistent with the behavior of the loss probability (see Figure 2).The curves for the throughput and goodput (Figures3 and 4) show a similar shape, but the values of the goodput are lower than those of the throughput (around 12% lower on average). The latter is due to the fact that unfinished SU transmissions have to be repeated from the beginning the next time the SU gains access to the channel.In our examples here, more important than the values of the performance parameters themselves is the computational effort required to compute them. In Figure5 we show the required execution time for our implementation of the analysis in Matlab 2015 that was run in a laptop with an Intel Core i7-4702MQ, 2.2 GHz, and 16 GB RAM.Figure 5
Execution time in seconds.As observed, the execution time is of the order of 1 minute in the worst case (N
=
100). It is also observed that, for the finite buffer model, the required execution time increases linearly with the buffer size. Therefore, when the buffer size increases, at some point the computational effort for the finite buffer case exceeds that of the infinite buffer one. Note, however, that if the buffer size is large enough, then it can be approximated by an infinite buffer system.


## 7. Conclusions

In this paper, we have proposed and analyzed a number of Markovian models that enable the analysis and evaluation of sensing strategies in cognitive radio networks under a broad range of conditions. The proposed models are quite versatile and general. A Markov phase renewal process is used to model the channel availability for secondary users (SUs). This allows considering a wide variety of distributions for the duration of idle and busy intervals and also capturing correlations between consecutive intervals. The behavior of SUs is modeled using generalphase-type distributions and sensing capabilities. A major contribution with respect our previous work is that the unrealistic assumption that the source of SUs is saturated has been relaxed in the models presented here, and the arrival process of the SUs is introduced. This arrival process is represented by the Markovian arrival process, which is also very general and versatile. Furthermore, we consider a general buffer size, either finite or infinite, for the waiting SUs and a fairly general resumption of an SU transmission after being interrupted by PUs activity. Finally, some numerical examples and results have been presented to show the capabilities of our models and the feasibility of their numerical analysis.



---

*Source: 7367028-2019-01-02.xml*