STOCHASTIC MODELING OF ROUTING PROTOCOLS FOR COGNITIVE RADIO
NETWORKS
By
Soroor Soltani

A DISSERTATION
Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of
Electrical Engineering-Doctor of Philosophy
2013

ABSTRACT
STOCHASTIC MODELING OF ROUTING PROTOCOLS FOR COGNITIVE RADIO
NETWORKS
By
Soroor Soltani
Cognitive radios are expected to revolutionize wireless networking because of their ability to
sense, manage and share the mobile available spectrum. Efficient utilization of the available spectrum could be significantly improved by incorporating different cognitive radio based networks.
Challenges are involved in utilizing the cognitive radios in a network, most of which rise from the
dynamic nature of available spectrum that is not present in traditional wireless networks. The set of
available spectrum blocks (channels) changes randomly with the arrival and departure of the users
licensed to a specific spectrum band. These users are known as primary users. If a band is used
by a primary user, the cognitive radio alters its transmission power level or modulation scheme to
change its transmission range and switches to another channel. In traditional wireless networks,
a link is stable if it is less prone to interference. In cognitive radio networks, however, a link that
is interference free might break due to the arrival of its primary user. Therefore, links’ stability
forms a stochastic process with OFF and ON states; ON, if the primary user is absent. Evidently,
traditional network protocols fail in this environment. New sets of protocols are needed in each
layer to cope with the stochastic dynamics of cognitive radio networks.
In this dissertation we present a comprehensive stochastic framework and a decision theory
based model for the problem of routing packets from a source to a destination in a cognitive radio
network. We begin by introducing two probability distributions called ArgMax and ArgMin for
probabilistic channel selection mechanisms, routing, and MAC protocols. The ArgMax probability
distribution locates the most stable link from a set of available links. Conversely, ArgMin identifies

the least stable link. ArgMax and ArgMin together provide valuable information on the diversity
of the stability of available links in a spectrum band. Next, considering the stochastic arrival of
primary users, we model the transition of packets from one hop to the other by a Semi-Markov
process and develop a Primary Spread Aware Routing Protocol (PSARP) that learns the dynamics
of the environment and adapts its routing decision accordingly.
Further, we use a decision theory framework. A utility function is designed to capture the
effect of spectrum measurement, fluctuation of bandwidth availability and path quality. A node
cognitively decides its best candidate among its neighbors by utilizing a decision tree. Each branch
of the tree is quantified by the utility function and a posterior probability distribution, constructed
using ArgMax probability distribution, which predicts the suitability of available neighbors. In
DTCR (Decision Tree Cognitive Routing), nodes learn their operational environment and adapt
their decision making accordingly. We extend the Decision tree modeling to translate video routing
in a dynamic cognitive radio network into a decision theory problem. Then terminal analysis
backward induction is used to produce our routing scheme that improves the peak signal-to-noise
ratio of the received video.
We show through this dissertation that by acknowledging the stochastic property of the cognitive radio networks’ environment and constructing strategies using the statistical and mathematical
tools that deal with such uncertainties, the utilization of these networks will greatly improve.

To my parents, Reza and Afsaneh.

iv

ACKNOWLEDGMENTS

I would like to express my greatest gratitude to the people who helped me throughout my research.
I am grateful to my father Professor Ahmad Reza Soltani for his continuous support and guidance.
His advice through difficult times enlightened my way of success. I thank my mother for her
undivided help and inspiration. I also thank my advisor Professor Matt Mutka for showing me a
successful path in my research. Finally, I truly appreciate my husband Farid Roshanghalb whose
encouragement and comfort made me resistable to PhD life challenges.

v

PREFACE

Should the answer not satiate my ambition
Leave me to my sword, and my battle ground.
Hakim Abul-Qasim Ferdowsi Tusi(940 1020 CE)

vi

TABLE OF CONTENTS

LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

x

LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

xi

Chapter 1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1 Overview of Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Organization of The Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
4
6

Chapter 2
Background . . . . . . . . . . . . . . . . .
2.1 Development of Cognitive Radios . . . . . . . . .
2.2 Cognitive Radio Architecture . . . . . . . . . . . .
2.3 Cognitive Radio Networks . . . . . . . . . . . . .
2.3.1 Knobs and Meters . . . . . . . . . . . . . .
2.4 Spectrum Sharing . . . . . . . . . . . . . . . . . .
2.5 Use of Decision Theory and Game Theory in CRN
2.6 Static and Semi-dynamic Routing Protocols . . . .
2.7 Dynamic Routing Protocols . . . . . . . . . . . . .
2.8 Cross Layer Design . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

8
8
10
12
13
15
19
24
25
27

Cognitive
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .

.
.
.
.
.

29
30
32
34
38

Stochastic Modeling of Cognitive Radio Networks and Probabilistic Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
An Overview of Markov and Semi-Markov Process . . . . . . . . . . . . . . . . .
Truncated Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Cognitive Radio Network Model . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.1 Medium Access and Physical Layer Assumptions . . . . . . . . . . . . . .
4.3.2 Spectrum Usage Assumptions . . . . . . . . . . . . . . . . . . . . . . . .
Probabilistic Routing Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Model implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Simulation Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6.1 Modeling of Inter-arrival Time of Primary Users . . . . . . . . . . . . . . .
4.6.2 Channel Occupancy Modeling . . . . . . . . . . . . . . . . . . . . . . . .
4.6.3 Modeling of Available Channel Usage Time . . . . . . . . . . . . . . . . .
Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39
40
42
42
44
45
48
51
54
55
55
56
56

Chapter 3
3.1
3.2
3.3
3.4

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

ArgMax and ArgMin: Transitional Probabilistic Models in
Radio Mesh Networks . . . . . . . . . . . . . . . . . . . . . .
ArgMax and ArgMin distributions . . . . . . . . . . . . . . . . . . .
Exponentially Distributed Random Variables . . . . . . . . . . . . . .
Primary Weight Measure . . . . . . . . . . . . . . . . . . . . . . . .
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

Chapter 4
4.1
4.2
4.3

4.4
4.5
4.6

4.7

vii

4.8

4.7.1 PSRP with ArgMax Probability Distribution . . . . . . . . . . . . . . . . . 57
4.7.2 PSRP with ArgMin Probability Distribution . . . . . . . . . . . . . . . . . 61
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

Chapter 5
Stochastic Routing Protocol . . . . . . . . . . . . . . . .
5.1 Stochastic Routing . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1 PSARP Operating Environment Assumptions . . . . . .
5.1.1.1 Primary User Model . . . . . . . . . . . . . .
5.1.1.2 Secondary User Model . . . . . . . . . . . . .
5.1.1.3 Medium Access and Physical Medium Model.
5.1.2 Theory . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.2.1 Neighbor’s forwarding ability . . . . . . . . .
5.1.2.2 Link reliability . . . . . . . . . . . . . . . . .
5.1.2.3 System Transitional Probabilities . . . . . . .
5.1.3 PSARP Implementation . . . . . . . . . . . . . . . . . .
5.1.3.1 PSARP Tables . . . . . . . . . . . . . . . . .
5.1.3.2 Control Messages . . . . . . . . . . . . . . .
5.1.3.3 Transition Probabilities . . . . . . . . . . . .
5.1.3.4 PSARP Forwarding Mechanism . . . . . . . .
5.2 Additional Features . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1 Update Period . . . . . . . . . . . . . . . . . . . . . . .
5.2.2 Channel Selection Mechanism . . . . . . . . . . . . . .
5.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3.1 Primary Users Traffic Patterns . . . . . . . . . . . . . .
5.3.2 Effect of Network Load . . . . . . . . . . . . . . . . . .
5.3.3 Large Network . . . . . . . . . . . . . . . . . . . . . .
5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

65
66
66
66
67
67
68
68
69
69
71
72
73
75
76
77
78
78
79
81
82
85
87

Chapter 6
Decision Tree Cognitive Routing . . .
6.1 System Model . . . . . . . . . . . . . . . . .
6.1.1 Experiment e . . . . . . . . . . . . .
6.1.2 A Sample Distribution . . . . . . . .
6.1.3 The Posterior Distribution . . . . . .
6.1.4 Utility Function . . . . . . . . . . . .
6.2 Making a decision using Backward Induction
6.3 Simulation . . . . . . . . . . . . . . . . . . .
6.3.1 Implementation Details . . . . . . . .
6.3.2 Effect of Network Load . . . . . . . .
6.3.3 Effect of Network Size . . . . . . . .
6.3.4 Primary Users Traffic Patterns . . . .
6.3.5 Adjusting the DTCR Parameters . . .
6.4 Summary . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

88
91
95
97
98
98
100
104
104
107
109
109
111
113

viii

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

Chapter 7
7.1

7.2
7.3
7.4

Decision Tree Modeling for Video Routing in Cognitive Radio Mesh Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Decision Theory Framework of VCR . . . . . . . . . . . . . . . . . . . . . . . .
7.1.1 Initial Learning Phase . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.1.1 Local Spectral Bandwidth Observations . . . . . . . . . . . . .
VCR Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chapter 8
Summary and future work . . . .
8.1 Summary . . . . . . . . . . . . . . . . .
8.2 Extensions and future works . . . . . . .
8.2.1 Utility Function Adjustments . . .
8.2.2 Primary Weight Measure in DTCR
8.2.3 More Decision Theory . . . . . .

.
.
.
.
.
.

BIBLIOGRAPHY . . . . . . . . . . . . . .

ix

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.
.

115
117
120
120
125
127
132

.
.
.
.
.
.

133
133
135
135
136
137

. . . . . . . . . . . . . . . . . . . 138

LIST OF TABLES

Table2.1

Knobs and Meters by layer [1] . . . . . . . . . . . . . . . . . . . . . . . 14

Table4.1

Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

Table4.2

Average throughput with 95% confidence interval for different sending
rates, l=12, 78 nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

Table4.3

Average throughput with 95% confidence interval for different sending
rate with Gamma distribution, l=12, 78 nodes . . . . . . . . . . . . . . . 59

Table4.4

95% confidence interval of average end-to-end delay for different rates . . 59

Table4.5

Average throughput with 95% confidence interval for different network
size, sending rate is 8Mb/sec . . . . . . . . . . . . . . . . . . . . . . . . 59

Table5.1

An entry of the neighbor Table . . . . . . . . . . . . . . . . . . . . . . . 72

Table5.2

An entry of the forwarding Table . . . . . . . . . . . . . . . . . . . . . . 73

Table5.3

Average throughput (bytes/sec), (30-node network) with different primary users traffic patterns . . . . . . . . . . . . . . . . . . . . . . . . . . 82

Table5.4

Average throughput (bytes/sec), (70-node network) with different primary users traffic patterns . . . . . . . . . . . . . . . . . . . . . . . . . . 85

Table6.1

DTCR Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

Table6.2

Average throughput for different average OFF periods of primary users . . 111

x

LIST OF FIGURES

Figure 2.1

Software-Defined Radio Technology Continuum. [1]. For interpretation
of the references to color in this and all other figures, the reader is referred
to the electronic version of this thesis dissertation. . . . . . . . . . . . .

9

Figure 2.2

CR platform; computational intelligence and learning capabilities are added
to SDR platform [1]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

Figure 2.3

CR architecture with a cognitive engine connected to the network protocol stack and a policy engine that checks the support ability of the hardware in response to the commands of the cognitive engine [1]. . . . . . . 13

Figure 2.4

Decision tree with states {s1 , s2 , ..., }, actions {a1 , a2 , ..., }, and posterior distributions P (s|z). . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Figure 4.1

A simple mesh cognitive radio network architecture . . . . . . . . . . . . 43

Figure 4.2

The tree graph representation of the simple network architecture. The SU
user S1 is the node i = 1 in layer l = 3 that has M1,2 = 1 (R1) accessible
neighbor, and is connected to it by n1 = 1 channel. The SU user S3 is
the node i = 3 that has M3,2 = 3 accessible neighbors (R1, R2, R3), and
is connected to R1 by n1 = 2 channels, to R2 by n2 = 2 channels and to
R3 by n3 = 1 channel. . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

Figure 4.3

The node selection procedure . . . . . . . . . . . . . . . . . . . . . . . . 53

Figure 4.4

Effect of primary users on average throughput for a network with 12 layers and 78 nodes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

Figure 4.5

Effect of primary users on average delay for a network with 12 layers and
78 nodes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

Figure 4.6

Queue Status for a network with 12 layers and 78 nodes. . . . . . . . . . 61

Figure 4.7

Dropped packets status for a network with 12 layers and 78 nodes. . . . . 62

Figure 4.8

Minimum packet delivery ratio of a network with 12 layers and 78 nodes
under frequent arrival of primary users. . . . . . . . . . . . . . . . . . . . 63

Figure 4.9

Minimum packet delivery ratio of a network with 12 layers and 78 nodes
under frequent arrival of primary users at low rates. . . . . . . . . . . . . 63

xi

Figure 5.1

Transition probabilities tree diagram . . . . . . . . . . . . . . . . . . . . 70

Figure 5.2

Simple topology, node 4 is the destination, generating DACK messages. . 74

Figure 5.3

Average throughput under different loading conditions, 30-nodes network. 83

Figure 5.4

Average end-to-end delay under different loading conditions, 30-nodes
network. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

Figure 5.5

Average throughput under different loading condition, 70-nodes network.

Figure 5.6

Relative frequency distribution of overhead in the first 4 hours of network
operation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

Figure 6.1

A simple mesh cloud within a city with its node diagram . . . . . . . . . 93

Figure 6.2

Node 12 decision tree, with three states and three acts . . . . . . . . . . . 95

Figure 6.3

Node 12 decision tree with some utilities . . . . . . . . . . . . . . . . . . 101

Figure 6.4

Node 12 decision tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

Figure 6.5

Average throughput with 95% confidence interval for different sending
rate, size = 78 nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

Figure 6.6

Average throughput with 95% confidence interval for different sending
rate, size = 78 nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

Figure 6.7

Average throughput with 95% confidence interval for different network
size, sending rate is 2Mb/sec . . . . . . . . . . . . . . . . . . . . . . . . 110

Figure 6.8

95% confidence interval of average end-to-end delay for different network size, sending rate is 2Mb/sec . . . . . . . . . . . . . . . . . . . . . 110

Figure 6.9

Utility on the states of 5 neighboring nodes, with different β values. . . . 112

Figure 6.10

Utility on the states of 5 neighboring nodes, with different γ values. . . . 112

Figure 6.11

Utility on the states of 5 neighboring nodes, with different η values. . . . 113

Figure 7.1

A simple downlink mesh network topology within a city with its node
diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

Figure 7.2

Node 0 decision tree with some utilities . . . . . . . . . . . . . . . . . . 123

xii

86

Figure 7.3

Node 0 decision tree with backward induction procedure . . . . . . . . . 126

Figure 7.4

Mean peak-signal-to-noise ratio for different α

Figure 7.5

End-to-end delay for different values of α . . . . . . . . . . . . . . . . . 129

Figure 7.6

Reconstructed Video frames (a) α=20msec, (b) α=30msc . . . . . . . . . 130

Figure 7.7

The relative loss frequency of I, P and B frames . . . . . . . . . . . . . . 131

xiii

. . . . . . . . . . . . . . 128

Chapter 1
Introduction
Advances in technology and development of new wireless devices increase the need for better
utilization of spectrum bands. The number of unlicensed spectrum bands are limited and according
to FCC, up to 85% of licensed spectrum bands is wasted when the licensed users are not using
their dedicated spectrum band. Cognitive radio networks (CRN) are developed to solve the underutilization problem of licensed spectrum bands.
Cognitive radios make use of not only their own available band, but also the vacancies of other
user’s bands. The cognitive radio interrupts its transmission upon the arrival of the other users.
Since the transmission is subjected to licensed (primary) user’s random interruptions, the communication environment is stochastic. Protocols should be designed to cope with the stochastic
behavior of primary users and include the uncertainty in the availability of spectrum in their implementation. In traditional wireless networks, a link is stable if it is less prone to interference. In
cognitive radio networks, however, a link that is interference free might break due to the arrival
of its primary user. Therefore, links’ stability forms a stochastic process with OFF and ON states;
ON, if the primary user is absent. Evidently, traditional network protocols fail in this environment.
New sets of protocols are needed in each layer to cope with the stochastic dynamics of cognitive
radio networks. The new MAC and routing layer protocols should consider the stability of a link
because each time the communication fails, packets are lost. In addition, radios restart the handshaking process, which increases communication overhead and severely damages the performance

1

in terms of throughput and delay. By using a routing protocol that guides the packets through the
paths with higher probability of stability than others, CRNs throughput and delay will substantially
improve. With acknowledging CRNs’true nature and using probability and stochastic theory tools,
we can develop protocols that nicely adapt to any uncertainty in the communication environment.
In order to identify a channel that has the highest probability of stability, we need to use the
statistical observations of channels availabilities and develop a probability distribution describing
the channels stabilities. Therefore, we introduce two probability distributions called ArgMax and
ArgMin, that are able to identify the most and the least stable channels. These probability distributions have broad applications in cognitive channel selection mechanisms, routing and MAC
protocols. The ArgMax probability distribution locates the maximum random variable among a set
of random variables, while the ArgMin locates the minimum random variable. The ArgMin probability distribution has a variety of applications and is shown to be useful in achieving a lower bound
on the network’s minimum spectral capacity. To show an application of the proposed probability
distributions, a Probabilistic Selection Routing Procedure (PSRP) is designed to guide packets in
a mesh CRN operating in a densely populated urban area. In PSRP the path is constructed step by
step based on the localized random decision of each node. Selection probabilities are assigned to
each neighbor node and evaluated periodically using the ArgMax probability distribution according to the available usage time of a channel.
Next, we extend PSRP into a Primary Spread Aware Routing Protocol (PSARP). The proposed
Primary Spread Aware Routing Protocol (PSARP) is based on nonhomogeneous Markovian transitions that give priority to the paths with the minimum expected frequency presence of primary
users. The PSARP selects the next hop probabilistically. The probability of selection depends on
both the next hop’s ability to transfer a packet to a particular destination and also the stability of
the links connecting it to the sender node. A Primary Weight Measure (PWM) is used in assessing
2

the next hop ability to transfer packets to its own intermediate neighbor. PWM is constructed using
both ArgMax and ArgMin distribution and identifies the diversity of spread of channels around a
particular node, the sender node is able to estimate the stability in the network environment beyond
its next hop neighbor. Therefore, nodes are able to divert their traffic through the paths that are
less frequently affected by primary users. The PSARP is designed as an adaptive per-hop routing
scheme to quickly adapt to changes in the dynamic CRN environment and is successful to do so
based on our simulation results.
Finally, considering the basic definition of routing that decides among possible routes, and the
intrinsic property of cognitive radio networks that is the uncertainty of available resources, we
use decision theory to construct a more advance routing mechanism. In decision theory a player
plays against nature, meaning the player opponent does not try to increase its fortune, but exhibits
stochastic performance that is explained by probability laws. Decision theory address decision
making problems in an environment where uncertainty exists and the true state cannot be fully
predicted. This is exactly the situation of a cognitive radio sender. First, the variety of spectrums
and their corresponding channels provide multiple routes from the server to the client. Hence, the
server has multiple options with different routing consequences. Second, the chosen route might
not stay stable during the transmission period. Therefore, the sender node is uncertain about the
consequences of its decision. In other words, the circumstances governing a node’s decision might
change. The Decision Tree Cognitive Routing (DTCR) scheme is able to predict the dynamic
of the network environment and routes the client packets to a server that operates in a heavily
populated urban area. To accommodate the needs of video applications, the DTCR is extended
into a Video Cognitive Routing (VCR) scheme that finds the best downlink route when video
packets are traversing from a server to a client.
In summary, this dissertation investigates the problem of routing in dynamic cognitive radio
3

networks. Specifically, by considering the CRNs’ uncertainties, we introduce two frameworks, a
stochastic framework and a Decision theory based framework, to study the dynamics of CRN. Our
objective is to (1) provide a more accurate decision making tool to capture the stochastic behavior
of primary users in CRNs, and (2) maximize throughput and consequently packet loss by proposing
routing procedures that captures the uncertainties and adapts to variations accordingly.

1.1 Overview of Contributions
We summarize the contribution of this dissertation as follows:
• Identification of the most stable channel is crucial in decision making of MAC and routing
protocols in CRN. Therefore, we introduce the ArgMax and ArgMin probability distributions
and show their application in probabilistic channel selection mechanisms, routing, and MAC
protocols. In almost all of the probabilistic approaches designed for multi-channel-multihop networks such as the work of Song et al [2] and Cui [3], the well-known probability
distribution Odds-On-Mean (OOM) is used to evaluate the selection probabilities. In OOM
probability distribution the probabilities are proportional to the population mean. However,
the ArgMax distribution locates the largest variable (in terms of magnitude) in a set of random variables. Therefore, the ArgMax probability distribution is more suitable in modeling
probabilistic behavior than OOM in network systems. Replacing the OOM probability distribution by the ArgMax probability distribution in many probabilistic selection mechanisms
improves their performance significantly. The main functionality of the ArgMin probability
distribution is to locate the random variable that at an instant is the minimum of a set of
random variables. Therefore, ArgMin probability distribution has variety of applications in
networks. For instance, the minimal spectral capacity can be identified using the ArgMin
4

probability ditribution. Using the ArgMax and ArgMin probability distributions, we introduce an interesting measure called primary weight measure, that indicates the frequency and
the nature of the distribution of primary users around a particular node. A low value of the
primary weight measure metric indicates uniform and frequent primary users interruptions
on the channels surrounding a node. With this information MAC and routing decisions are
taken more efficiently.
• By acknowledging the stochastic behavior of CRNs, we develop a stochastic model of a
mesh CRN in a densely populated urban area. In our model, the number of available nodes,
channels and the available usage time are random. Through this analysis, we formulate the
available usage time of each channel in a spectrum with a truncated distribution. Next, a
Probabilistic Selection Routing Procedure (PSRP) is proposed to guide packets in the CRN.
The superiority of ArgMax is shown by evaluating the performance of the PSRP adopting
ArgMax and OOM as its selection probabilities. We further, extend the PSRP and develop a
Primary Spread Aware Routing protocol (PSARP). PSARP is able to adapt to the uncertainties of spectrum availability in cognitive radio networks. PSARP is based on the Markovian
property of a particular flow from a source to a destination and uses PWM as one of its routing metrics. We demonstrated through simulation that PSARP is robust to the variation of
the primary users’ activity. Our results confirm that using a stochastic protocol for a stochastic environment is indeed more suitable than using deterministic protocols. We believe this
research is the beginning of a new line of work on the development of stochastic routing
protocols.
• We proceed to adopt the techniques in statistics that address decision making problems in
an environment where uncertainty exists and the true state cannot be fully predicted. Hence,

5

we construct the Decision Tree Cognitive Routing (DTCR) scheme. By adopting the decision problem components, we construct appropriate sample and posterior distributions to
explain the status of channels and nodes in supporting packet delivery. We also introduce a
utility function that captures the effects of spectrum availability, bandwidth fluctuations and
path quality. This utility function is expandable to include other important decision making
factors. Our results show that DTCR is successful in maintaining the network throughput
near the optimal value and works significantly better than the AODV-based routing schemes
designed for dynamic cognitive radio networks.
• Transferring video applications over dynamic cognitive radio networks is challenging due
to the variation in bandwidth availability and the stability of the available bands. Therefore,
we use the decision theory components and expand on DTCR to develop a Video aware
Cognitive Routing scheme (VCR). We model and analyze the problem of downlink routing
of video packets in a dynamic CRN. The previous sample and posterior distributions are now
modified to explain the status of channels and nodes in supporting video frames quality of
service. The performance of DTCR and VCR is compared with the most acceptable class
of the previous dynamic routing strategies for CRNs with implementing the protocols on the
real time network simulator.

1.2 Organization of The Dissertation
The rest of this dissertation is organized as follows. Chapter provides the background on the
cognitive radios and cognitive radio networks as well as an overview of the related work that has
been done on the design and implementation of routing protocols. In Chapter , the definition
of the ArgMax and the ArgMin probability distributions is presented. In addition, we introduce
6

the PWM routing metric that is made by combining these two probability measures. In Chapter
the stochastic modeling of a cognitive radio mesh network that leads to development of PSRP is
introduced. We show the usage of the ArgMax and the ArgMin probability distribution in PSRP
through simulation. In Chapter , the stochastic routing protocol PSARP is presented that routes
the packets in a CRN operating in a highly dynamic environment. The concept of decision theory
and DTCR is presented in Chapter . We show that by using the decision theory components, one
could utilize the cognitive abilities of CR nodes to design routing strategies adaptive to the dynamic
nature of cognitive radio networks. Chapter demonstrates how VCR is developed from the basis
of DTCR. At the end of each chapter a summary of the comparison results is presented. Finally
we highlight the possible future directions of this dissertation in Chapter .

7

Chapter 2
Background
This chapter presents the background on the development of cognitive radios and cognitive radio
networks. The dynamics of cognitive radio networks are discussed, which led the development of
new sets of protocols at different network layers. Related work on routing protocols in network
layer of cognitive radio networks is also presented in this chapter.

2.1 Development of Cognitive Radios
The idea of cognitive radio was first introduced by Joe Mitola in 1991, “a radio that is aware of its
spectral environment as well as its user and network environment”. Traditional radios were built
on a fixed platform. Gradually, advances in digital communication transformed the analog design
to a programmable digital radio. Radio use could be flexible by modifying the software with no
hardware development.
Figure 2.1 shows a continuum of the software defined radio technology. The very first generation of these radios are software capable radios. These radios have fixed modulation capabilities,
relatively small number of frequencies, limited data and data rate capabilities, and the ability to
handle data under software control. They emerged into software programable radios, new functionalities could be added through software changes and their advance network capabilities. The
next generation of these radios are software defined radios (SDR). By FCC definition a SDR is

8

a communications device whose attributes and capabilities are developed and/or implemented in
software [4]. In SDR systems, there is complete adjustability through software of all radio operating parameters. To reach the vision of Mitola, sensors are added to SDRs that collect information,
such as chemical surroundings, geolocation, time of day, biometric data, or even network qualityof-service (QoS) measures. These type of radios are aware radios. The aware radios do not use the
collected information and are simply aware of the changes. In the adaptive radios, frequency, instantaneous bandwidth, modulation scheme, error-correction coding, channel mitigation strategies
(e.g., equalizers or RAKE filters), system timing (e.g., a TDMA structure), data rate (baud timing),
transmit power, and even filtering characteristics and operating parameters are adapted based on
the sensory measurement. Finally cognitive radios (CR) were developed. In this class of radios,
sensors create awareness of the environment and actuators interact with the environment. The CR
has the ability to create a model of the environment that includes state or memory of the observed
events. The CR has a learning capability that helps to select specific actions or adaptations to reach
a performance goal.

Figure 2.1 Software-Defined Radio Technology Continuum. [1].
For interpretation of the references to color in this and all other figures, the reader is referred to
the electronic version of this thesis dissertation.

The very first CRs were modeled in the Defense Advanced Research Projects Agency (DARPA)
NeXt Generation (XG) radio development program. The spectrum environment is sensed, the
unoccupied portion is identified. These radios rendezvous in the unoccupied band, communicate

9

in that band, and vacate the band if a legacy signal reenters that band. [1].

2.2 Cognitive Radio Architecture
The cognitive radios are built on top of SDR platforms. The cognitive radio platform is shown in
Figure 2.2. The cognition engine sits on top of the software unit that controls the tunable parameters in the hardware unit. The hardware is similar to other next generation radios (SDR, adaptive
radios). The main difference is in the processor that contains the cognition engine and a set of
computational modules. The modules have Radio Knowledge Representation Language (RXML)
frames. RXML provides a standard language within which unanticipated data exchanges can be
defined dynamically. The radio itself, including the equalizer, in the context of a comprehensive
ontology, is written in RXML.

Figure 2.2 CR platform; computational intelligence and learning capabilities are added to SDR
platform [1].

Each of the following functional components should be in place in order to have a complete
10

cognitive radio. Some are developed and some are still under development. A minimal cognitive
radio architecture should have the following functional components:
• User interface, which includes haptic, acoustic, and video sensing and perception functions.
• Environmental sensor functions that sense environmental characteristics such as temperature, location, etc.
• SDR functions, which includes radio frequency sensing and software defined radio applications.
• Cognition functions; system control, planning and learning.
• Local effector functions; text, graphics and multimedia displays.
A CR node follows through the following cycle to command its effector unit for appropriate action.
It first observes the environment and gathers the sensory measurement. After this stage, the Orient
phase starts, which determines how significant is an observation. In this phase the CR creates a
short term memory of its observed data and after analyzing its short term memory, it saves the
important reading in its long term memory. Information manipulation is still an important topic in
the CR research. A CR then follows a plan to decide about its reaction to a certain stimuli. Finally
using effector modules, it initiates a selected process according to its plan.
Nokia Research Center, Qualcome and the XG technology INC, are the leading research and
development companies in cognitive radio technology. XG technology developed a new line of
products called Xmax systems, which includes “line of high-performance access points, fixed and
mobile personal WiFi hotspots, mobile switching centers (MSC’s) as well as network management
and deployment tools. XG’s unique and patented protocol outperforms WiFi, WiMax and traditional cellular technologies like LTE in shared and interference prone radio bands”. [5]. Currently
11

different SDRs are commercially available that can be used in experimental test beds such as SDR
MK1.5 ’Andrus’ [6], USRP1 and USRP2 [7].

2.3 Cognitive Radio Networks
Cognitive radio networks are built with networking the CR nodes together. Researchers have
two categories for such networks: Network of Cognitive Radios (NCR) and Cognitive Networks
(CN). In the first category each node focuses on its own requirements and changes its parameters
according to its individual needs. In such networks, the end-to-end goal of the network might be
achieved as it is investigated by Neel, et al. [8] through game theory. However, these networks are
not actively perusing the end to end goals of the network. CNs on the other hand are the networks
that cognitively adapt their parameters to reach a set of predefined goals. The common feature
between these two categories is that the CR nodes functionalities should be extended to encompass
the entire network stack. The architecture of a cognitive radio node is shown in Figure 2.3. The
communication system includes the network layer stack. The end to end goals are defined by the
user domain. They could be end-to-end network requirements such as the quality of service or
delay. The cognitive engine is the core of the device. It performs the modeling, learning, and
optimization processes necessary to reconfigure the communication system in order to achieve the
goals. Information such as radio frequency (RF) and environmental data that could affect system
performance are gathered by the radio domain. The policy engine checks and controls the solutions
to follow the regulations set by the network administrators and federal communication policies.
A cognitive radio follows a loop of self-explanatory components: Observe, Orient, Decide and
Act, to reach the requirements of wireless communication from its own perspective and network
perspective. Here, we elaborate on observable parameters (Meters) at each networking layer and

12

Figure 2.3 CR architecture with a cognitive engine connected to the network protocol stack and a
policy engine that checks the support ability of the hardware in response to the commands of the
cognitive engine [1].
the corresponding control mechanisms (Knobs) that can improve the communication process. We
also present the cognition cycle that takes place by observing different parameters at each layer.

2.3.1 Knobs and Meters
The CR senses its environment and needs to be aware of the major factors that affect its communication. The environmental and communication factors could be directly observed by CR’s sensors
or conceived from previous measurement. The observable parameters at the different layers of
the network are called meters. By observing and comparing the meters with their desired value,
control parameters (knobs) are adjusted by the embedded protocols. Table 2.1 summarizes meters
and knobs at each network layer.
The cognitive engine requires four levels of awareness to make its decision: (1) recognizing
the needs of the user, (2) understanding the limitations imposed on the radio operation by the
13

Table 2.1 Knobs and Meters by layer [1]
Layer

Meters(Observable parameters)

Knobs(Writable parameters)

NETWORK

Packet delay
Packet jitter

Packet size
Packet rate

MAC

Cyclic redundancy check (CRC)
Automatic repeat request (ARQ)
Frame error rate
Data rate

Source coding
Channel coding rate and type
Frame size and type
Interleaving details
Channel/slot/code allocation
Duplexing
Multiple access
Encryption

PHY

Bit error rate (BER)
Signal-to-noise ratio (SNR)
Signal-to-interference and noise ratio (SINR)
Received signal strength indicator (RSSI)
Pathloss
Fading statistics
Doppler spread
Delay spread
Multipath profile
Angle of arrival (AOA)
Noise power
Interference power
Peak-to-average power ratio
Error vector magnitude
Spectral efficiency

Transmitter power
Spreading type
Spreading code
Modulation type
Modulation index
Bandwidth
Pulse shaping
Symbol rate
Carrier frequency
Dynamic range
Equalization
Antenna beam shape

channel and external environment, (3) realizing its own limitations in flexibility and power, and (4)
conforming to local regulations and policy. This is achieved by observing multiple meters related
to each category of awareness.
Advances in technology are bringing the vision of mixing intelligence with communication into
reality. This vision was first pictured by Claude Shannon. The CRs are the intelligent radios that
require a new set of protocols to communicate with each other. Protocols that have the ability to
14

change different knobs in relation to the variations observed from multiple meters at the same time.
Traditional network protocols do not make use of the intelligence of CRs and therefore downgrade
them to an ordinarily wireless transmitter and receiver. For CRs to work to their full capacities,
network protocols should be fully adaptive to the changes made by cognitive engine.
Besides handling the unexpected changes due to the intelligent decision making of the device,
the operational environment of CRNs are very different from traditional wireless networks. In
such networks once a channel is available for a network node, it could use that channel without
interruption as long as it continues to transmit. In CRNs, radios are intelligent enough to make use
of not only their own available bandwidth but other’s available bands. Vacancies of other user’s
bands are exploited and a CR interrupts its transmission upon the arrival of the users. A stochastic
communication environment is created when the transmission is interrupted by the random arrivals
of other users. Protocols should be designed to cope with stochastic behavior of users and include
the uncertainties involved in their design. The MAC and routing layer protocols should consider the
stability of a band, since failing to make the right decision would severely damage the performance
of such networks. In the next section we introduce how CRs rendezvous to different bands and
elaborate more on the stochastic nature of CRNs and possible solutions in protocol design.

2.4 Spectrum Sharing
Cognitive radios have the ability to sense the available spectrum and identify whether it is being
used by other users. Their cognition engine can decide whether a sensed idle portion of a spectrum
in terms of frequency, time and space could be used. Two CRs could rendezvous at an unoccupied
channel and communicate. Traditional wireless networks use a dedicated spectrum band (channel)
for their communication. When the network users are inactive, a large portion of spectrum is

15

wasted. The advance sensing ability of CRs opens a possibility to have a network consists of
CR nodes that only use the white space of spectrum to communicate. This will substantially
improve the existing spectrum utilization. The CRs that only use the white space spectrum are
called Secondary Users (SU). These users should interrupt their transmission on a specific band if a
licensed user of that band comes back. The licensed user is also referred to as Primary User (PU). A
CR should be able to observe the presence of primary and secondary users. Moreover, for reliable
communication, the received signal and interference to noise ratio (SINR), current connectivity,
packet delays and the state of other nodes’ parameter choices (power, channel selection, location)
also need to be observed and communicated with other nodes.
For a successful rendezvous in a CRN, multiple SUs must dynamically sense large number of
channels to identify vacancies. In addition, for two radios to establish a link, control messages
need to be exchanged among the users. The problem of rendezvous is obviously not trivial. Approaches for rendezvous could be classified into two main categories: aided and unaided. The aided
rendezvous is infrastructure-based, meaning the information regarding the channel availability are
periodically broadcasted by a server. The server may also be a clearinghouse for link establishment
and the scheduling of transmissions. As it can be perceived from its name, in unaided rendezvous
each CR finds another node in the network by its own. In this type of rendezvous, a dedicated
control channel may or may not exist. Using a single control channel might result in a single point
of failure in large networks. Therefore a distributed solution in which different cluster of nodes
use different control channels, can be adopted. Another approach allows the control messages to
use data channels. As a result, all channels could be used as control channels. The process of
establishing a link without a control channel is called blind rendezvous. In an infrastructure-based
network, a control channel is used to identify spectrum availability. In the architecture proposed by
Buddhikot, et al. [9], some frequencies are selected for use as spectrum information channels. A
16

wireless interface is dedicated by clients to scan these channels to broadcast information regarding
spectrum availability from the base-stations. Control channels are also used by clients to send the
beacon messages requesting the use of an available channel. Clearly, the use of a common control
channel simplifies the process of rendezvous. However, if multiple base-stations and associated
radios are in close vicinity of one another, they all compete to use the control channel. As the
users are quite diverse, possibly covering all wireless users, some regulators worry about how to
resolve the potential contention. The policy engine of CR nodes needs to be equipped with appropriate rules, preventing unfair allocation of the control channel, giving priority based on service
providers’ advantages in order to encourage them to invest in CR technology.
In most of the work on multi channel medium access control in decentralized networks, the control packet information is also sent on a dedicated control channel. They assume nodes equipped
with two radios [10]. One radio constantly monitors a dedicated control channel and by sending
request-to-send (RTS) and clear-to-send (CTS) frames uses that channel to reserve transmission
on one of the potential data channels. The second radio tunes to the reserved data channel for
the exchange of data frames. This approach simplifies the rendezvous problem but as the network
size increases, the control channel acts as a bottleneck. If the control channel is congested, the
operation of the entire network fails. A possible solution is to have multiple control channels.
The disadvantage is that the presence of PUs may not be sensed correctly that raises the issue of
fairness.
When there is no dedicated control channel (blind rendezvous), all channels are potentially
available for the exchange of control and data. The set of channels must be sensed in random
on pre established order for possible availability. The radios then need to send beacons and wait
for responses to make a connection with other users. A possible solution for blind rendezvous is
described in Horine and Turgut [11]. Radios take turns and access the channel in time slots. If
17

the radio does not sense other users (PU or SU) in its vicinity, it sends a beacon message followed
by a period of silence to receive a response from a potential receiver. Two existing methods by
which the radios can eventually meet in the same channel are random rendezvous and sequence
based rendezvous. In random rendezvous, a radio wishing to join a network visits the potential
communications channels in random order. Sequence-based rendezvous was proposed by DaSilva
and Guerreiro [12] in which predefined sequences used by each radio arranges the potential channels in their visiting order. The idea is that both transceivers follow the same sequence, although
arbitrarily delayed with respect to each other.
For a successful and efficient transmission between two SUs, not only the rendezvous solutions
should be robust to the dynamic spectrum occupation but also take into consideration the stability
of an available channel. If two CRs establish a connection following one of the rendezvous solutions, and shortly after they start sending the data frames, the connection is torn down due to return
of a primary user, a substantial amount of network resources will be wasted. Large delay caused
by reestablishing a link will make the network useless for a wide range of applications. Since
CRs have the memory and the intelligence, the probabilistic approach is the promising solutions to
overcome this problem.
Undeniably, CRNs structure falls under the framework of stochastic systems. With acknowledging their true nature and using the probability and stochastic theory tools we can develop protocols that nicely adapt to any uncertainly and randomness exits in the communication environment. For instance, observing the history of the meters variations and using statistical methods
to assign selection probabilities to potential channels would substantially reduce the possibility of
connection interruption. Recently probabilistic approach is being used in MAC physical layer but
simplistic probability models are being adopted. In this dissertation we introduce a probability
model that points to most stable channel with higher accuracy than the commonly used probability
18

model.
The medium access strategies are extensively under investigation. However, less attention
is made to the design of routing protocols for CRNs. In this dissertation, after introducing a
new probability distribution to find the most stable path, design of routing protocols in stochastic
environment is discussed. The routing protocols proposed in this dissertation use the learning
capabilities of CR to select the appropriate route.

2.5 Use of Decision Theory and Game Theory in CRN
In cognitive radio networks, secondary users are intelligent and act to optimize their performance.
They aim at maximizing their own benefits. Therefore, Game theoretic models are preferred.
game theory analyzes the strategies that decision makers can take in interacting with one another
in order to optimize their gain. As the definition suggests, by adopting game theory tools one
is able to obtain useful strategies in spectrum sharing and routing. The components of spectrum
sharing games in cognitive radio networks are described as follows: Players are the secondary
users that compete for the unlicensed spectrum band. Actions are the transmission parameters,
such as transmission power level, access rate, etc. Payoff (Utility) is a non-decreasing function of
the QoS by utilizing the spectrum. The games are divided into the following main categories:
• Non-cooperative games and Nash equilibria
• Economic games, auction games and mechanisms design
• Cooperative games
• Stochastic games

19

Efficient distributed approaches for dynamic spectrum sensing is derived by adopting non-cooperative
game theory. Neel et.al [13] and Giupponi et.al [13], present useful applications of this adaptation
in CRN. Economic games and cooperative games are also adopted in CRN as explained in [14].
However, one important aspect of CRN is overlooked in these schemes. The spectrum opportunities and the surrounding radio environment keep changing overtime. Therefore, for a dynamic
environment, we cannot assume that the stage of the game is constant. However, this is the major
assumption in the first three game categories mentioned above. A stochastic game that is an extension of Markov Decision Process [15] is a better fit for designing MAC and routing strategies in
dynamic CRNs. In a stochastic game, after the players select and execute their actions, the game
moves to a new random state with transition probability determined by the current state and one
action from each player. Meanwhile, at each stage each player attempts to maximize an objective
function. The objective function is the expected sum of the payoffs over an infinite horizon. The
solution is called policy and is a probability distribution over action set at any state. Stochastic
game is used in transmission control, anti-jamming defense and spectrum auction. However using
stochastic game for routing is a challenge because the players should have complete knowledge
about the game being played. Meaning secondary users in a dynamic CRN should have a complete
knowledge of the available routes and the other secondary and primary users. The game should be
divided into stages so that the secondary users obtain some information about the others actions
and payoffs.
An alternative to game theory is statistical decision theory. Pratt, Raiffa and Schlaifer in [16]
explain that a problem of decision making under uncertainty can be addressed by using statistical
decision theory. The problem should have the following characteristics:
1. A choice, or in some cases, the sequence of choices must be made among various course of
actions.
20

2. The choice or sequence of choices will ultimately lead to some consequence, but the decision
maker cannot be sure in advance what this sequence will be because it depends not only on
his choice or choices but on an unpredictable event or sequence of events.
It is clear from the above characteristics that this associates well with situation of secondary users
when deciding their route in a dynamic CRN. First, a secondary user has multiple choices (different links and routes) for routing. Second, the secondary user cannot be sure whether the chosen
route will stay stable to transfer its packets to the ultimate destination. The advantage of using
decision theory is that we assume that the player is playing against nature meaning the player opponent does not try to increase its fortune, but exhibits stochastic performance that is explained
by probability laws. In decision theory the current state of the game is taken to be uncertain and
the decisions are made considering such uncertainties. In a highly dynamic environment, decision theory leads to less computational complexity than game theory since many types of games
have multiple equilibria under such variations. Using the learning capability of cognitive radios
we modeled the problem of routing in CRN into a decision problem and obtained satisfactory improvement in the performance of the network. To the best of our knowledge, this is the first time
that statistical decision theory is adopted to model the problem of routing in dynamic CRN.
The problem of routing in CRN falls under a class of decision problem that is concerned with
the logical analysis of choices among various course of actions. For this class of problem, (a) the
consequence of any course of action depends on the state of the world s, (b) the true state (the
correct route) is as yet unknown, (c) it is possible to obtain some information about the true state
by conducting an experiment e at a cost, and observing the outcome z of the experiment. The
basic assumption is that the preference of the decision maker does not change. This means his
judgment about the outcome z of each potential experiment is consistent with his preference of the
consequence of his choice. His preference is presented by a utility function u and his judgment is
21

sealed in terms of a probability measure P .
Here we introduce some definitions and notations that are used in these class of problems in
decision theory.
State space S = {s1 , s2 , ..., }: Set of possible states (choices) available to the decision maker.
Action space A = {a1 , a2 , ..., }: Variable ai is the act of choosing state sj to visit.
Set of experiments E = {e0 , e1 }: When the decision maker performs a test to get some information
in support of an act. Experiments are classified by e0 and e1 , where e0 stands for no experiment
and e1 is to perform an experiment or test to support a right act. The experiment e1 gives rise to
possible samples Z = {z1 , z2 , ...}, zi is a sample observation that is in favor of a state si .
Sample distribution P (z|s): In statistics samples and measurements are subject to false readings,
therefore although samples are informative, but are not 100% reliable. Sample distribution P (z|s)
governs this probabilistic situation: it gives the probability of observing sample z whenever s is the
true state. For s to be a true state means that it is the right and the most appropriate state. Sample
distribution is used in quantifying our observation in indeterministic environment.
Prior distribution P (s) is assigned to the state space S. An appropriate prior distribution is based
on the history of availability of a state and usually does not reflect current status of states. Posterior
distribution P (s|z): The probability of observing the state s when the sample observation is z. This
measure indicates the possibility of choosing a true state s by observing a sample observation z.
This probability is found using the conditional probability formula

P (s|z) =

P (z|s)P (s)
.
s P (z|s)P (s)

(2.1)

Note that the denominator in the above equation is the marginal distribution of sample observation.

22

In analyzing a decision problem a diagram known as decision tree is used. The tree demonstrates different paths of reaching a state by performing or not performing an experiment and
following different acts as shown in Figure 2.4. In any decision problem there is a loss/gain associated with a decision. When the decision maker makes a decision to perform an experiment e
(relies on the sampling probabilities P (z|s)), it pays a cost and in return gains extra knowledge on
the possible consequence of his decision. Therefore, the utility function U(e, z, a, s) is assigned to
the decision data (e, z, a, s).

Figure 2.4 Decision tree with states {s1 , s2 , ..., }, actions {a1 , a2 , ..., }, and posterior
distributions P (s|z).

23

The utility function u indicates the decision maker gains or losses. Decision data is usually
denoted by (e, z, a, s). The decision maker runs experiment e, observes sample z, takes act a when
the true state is indeed s. An optimal act minimizes the expected loss or maximizes the expected
gain; the later is maxe Ep(z|e) [maxa [Ep(s|z,e) U(e, z, a, s)]].
In Chapter we present the details of modeling routing in a dynamic CRN using the decision
theory concepts mentioned above. In the following sections we categorize the routing protocols
developed for cognitive radio networks and provide an overview on their design.

2.6 Static and Semi-dynamic Routing Protocols
Developing routing protocols for wireless mesh networks has been investigated for years. With the
development of new technologies, more advanced routing schemes could be designed and implemented. The importance of routing in CRN is greatly dependent on the behavior of PUs. Long
absence of PUs categorizes the CRN as a static multi-channel-multi-hop network and the traditional routing protocols are applied. When the PU’s behavior is more dynamic, new approaches
in routing are necessary. Zhu et al. [17] propose a spectrum based routing protocol that simplifies
the collaboration between spectrum decision and route selection by establishing a spectrum tree
at each spectrum band. They assume that the statistics of PU’s activities and available spectrum
band information can be obtained by existing spectrum sensing and sharing techniques. In [18] the
authors develop a routing protocol called SAMER, which offers a set of candidate routes to the destination. The actual forwarding path opportunistically adapts to the dynamic spectrum conditions
and exploits the link with the highest spectrum availability at the time. In [19], authors propose
a new metric based on the probabilistic definition of link available capacity into the cost of the
Dijkstra-like algorithm. Researchers such as Wu et al. [20] propose a distributed multi-channel

24

and routing assignment in heterogeneous multi radio multi-channel-multi-hop wireless networks
where the channel coordination and route selection is based on the information exchanged among
two hop neighbors. In [21], authors allow each network node to exchange their spectrum opportunity information and select the optimal channel. The network learns the behavior of PUs via a
nonparametric statistical learning method based on past observations. In the work of Cui et al [3]
and Song [2], a probabilistic approach is introduced in which the OOM distribution is used to
assign the selection probabilities for every path.
ROSA-PMQ is designed for video or multimedia applications in semi-dynamic environment
[22]. It is a cross layer protocol that jointly does the routing, spectrum assignment, scheduling and
power assignment functionalities. Khalife et al. [19] propose a joint routing and channel selection
scheme to fulfill bandwidth requirements of flows. Jashni et al. [23] propose a routing scheme with
channel selection to support multimedia application in which the probability of channel selection
of neighbor SUs is evaluated using the game theory fictitious play technique. Xie et al. [24], Gao
et al. [25], and Xie and Xi in [26] propose routing schemes to support multicast communication in
CRNs. In Chapter , we present our scheme that focuses on the unicast transport of video application
packets in a highly dynamic environment.

2.7 Dynamic Routing Protocols
As mentioned in the previous section, by incorporating cognitive radios, the wireless network
possesses new dynamics and many researchers started to design new routing protocols accordingly.
Among those are the works of [17], [18] and [27]. They model the spectrum utilization as a new
metric to enhance the selection mechanism in traditional routing schemes. In [28], [29] and [30],
the problem of routing, scheduling and interference awareness is formulated into different forms

25

of an optimization problem. These studies’ underlying assumption is that the behavior of primary
users is fairly predictable. The protocols we propose on the other hand, considers a dynamic
environment and takes into account the stochastic behavior of CRNs.
Many of the proposed routing schemes for dynamic CRNs adopted the framework of ad hoc or
wireless sensor networks. The uncertainty in the links’ availability is mapped into the unavailability of nodes in the above networks. Hence, protocols such as SODV [31], CODV [32], OSDRP [33]
and [34] are proposed. In fact, the nature of instability in ad hoc or sensor networks is very different from CRNs. Links’ availability is unpredictable in CRNs and the repetition of calling a route
discovery mechanism in such protocols would increase the delay and degrade the overall throughput. Previous studies mainly focus on reliable routing of video or multimedia applications that
require a certain quality of service in semi-dynamic environment. How et al. [33] propose OSDRP,
a quality of service aware routing protocol for dynamic environment that adopts the frame work of
AODV protocol.
In DTCR, we take a decision theory approach that gives a solution for decisions that need to be
made under uncertainties. A relatively close approach is game theory. Pavlidou and Kolsidas [35]
surveyed different routing protocols for wireless communication networks designed by the game
theory framework. These studies, however have static spectrums and channels. Nurmi [36] uses a
dynamic Bayesian game to form a dynamic stage game with incomplete information. Our decision
theory approach also uses the Bayesian rule to construct the posterior distributions in order to
include the effect of cognitive radio dynamics. In [14], the authors summarize the applications of
game theory in cognitive radio networks. In the work of Zhu et al. [37], nodes are grouped into
layers similar to our work. They also use a game theory framework with an end-to-end path utility
to route the secondary users’ control messages in a pilot channel. Cacciapuoti et al. [38] develop a
theoretical model to analyze the opportunistic routing procedures. Our framework uses cognitive
26

decision making to make its selection an opportunistic routing scenario.
The DTCR is different from the above since it uses the decision theory framework and a decision tree to model a decision strategy for a node. We construct sample and posterior distributions
to explain the status of channels and nodes in supporting packet delivery. These distributions use
a simple metric such as channel availability duration. However, they can be easily extended to use
advance metrics such as OPERA, proposed by Caleffi et al. [39]. There is no central agent helping
in decision making; the nodes try to estimate the future uncertainties and choose neighbor nodes
that maximizes their expected gain.

2.8 Cross Layer Design
As explained in section 2.3.1, we need to combine different meters from different layers to achieve
a performance goal. Therefore, at first glance, it might be plausible to adopt the cross layer approach and use the previously designed cross layer protocols for cognitive radio networks. To take
into account meters of different layers, originally researchers combine two layer’s meter (physical
and MAC layer) but this would optimize one objective in the expense of other objectives. Recently,
a new kind of cross layer design is proposed. CrossTalk [40], ECLAIR [41], CLD [42] and the
framework of Gong et al. [43] propose using a parallel structure that acts as a shared database
accessible to whichever layers choose to use it. The cognitive network design however, is taking a
different approach. They use the cognitive process that would consider not only the network goals
but also learns from its past behaviors. Use of learning and proactive adaptation is included in
cognitive radio networks. The protocols at each layer should be modified to include the learning
and adaptation processes.
We propose two new probability distributions ArgMax for the selection probabilities, and

27

ArgMin to find minimal spectral capacity. The proposed distributions is not only limited to the
probabilistic routing but also could be used in probabilistic MAC layer techniques. We develop
two routing mechanism. First, PSARP that is specifically designed for nondeterministic dynamical
systems. In PSARP, we design a stochastic-based routing to locate the best route in a stochastic
environment using stochastic systems tools. We observed that the transition of packets from a
source to a destination in a cognitive radio network is a stochastic process since the random arrival
of primary users on channels make the next state of the system (next hop) in the path indeterministic. PSARP adapts to the change of behavior of network dynamics and selects the next node
based on the uncertainty of channel existence. Second, the DTCR that is developed using decision
theory components to deal with decision making under uncertainties of cognitive radio networks
environment.
In the following chapter we elaborate more on the stochastic modeling of cognitive radio networks and the proposed routing schemes.

28

Chapter 3
ArgMax and ArgMin: Transitional
Probabilistic Models in Cognitive Radio
Mesh Networks
Random phenomena are present in any realistic system. Many parameters in computer networks
are random and follow a certain distribution. It is often of interest to find the maximum or the
minimum element of these random variables. The parameters could be channel occupancy, queue
capacity, packets arrival and departure rate, delay, etc. The main functionality of the ArgMax
(ArgMin) probability distribution is to locate the random variable that at an instant is the maximum
(minimum) of a set of random variables. In this chapter, we present the definition of the ArgMax
and ArgMin distributions. We also develop a new metric called Primary Weight Measure (PWM)
to capture the uniformity or diversity of availability in the channels of different spectrum bands. In
other words, PWM shows how the primary users affect the channels around a particular node. If all
the channels are affected uniformly by primary users, then all channels provide the same utilization
for a secondary node and there is no priority in selecting one channel over another. Moreover, if a
node has the highest PWM, it has at least one channel that is minimally affected by primary users.
In subsequent chapters, we elaborate on the application of the proposed distributions and the PWM
metric in cognitive radio network.

29

3.1 ArgMax and ArgMin distributions
Let Z1 , · · · , Zn be a finite sequence of continuous random variables defined on a probability
space. We let Zmax = max{Zi , i = 1, ..., n}. The corresponding ArgMax random variable τmax
indicates the index of the random variable that attains the maximum values. Precisely, (τmax =
i) = (Zmax = Zi ), for i = 1, ..., n. A probability distribution of τmax , {p(1), p(2), · · · , p(n)}, is
called the ArgMax distribution which is unique because of the continuity of the random variables
Z1 , Z2 , ..., Zn . Therefore

p(i) = P {τmax = i} = P {Zmax = Zi },

i = 1, · · · , n.

(3.1)

The corresponding ArgMin random variable τmin indicates the index of the random variable that
attains the minimum values. Therefore

q(i) = P {τmin = i} = P {Zmin = Zi },

i = 1, · · · , n.

(3.2)

Theorem 1. The ArgMax and ArgMin probability distribution for an array of independent continuous random variables Z1 , · · · , Zn with distribution functions F1 , F2 , · · · , Fn are respectively
given by
p(i) =

q(i) =



+∞



−∞
+∞

−∞






n
j=1,j=i

Fj (z) dFi (z),


n

j=1,j=i

1 − Fj (z) dFi (z),

i = 1, · · · , n.

i = 1, · · · , n.

(3.3)

(3.4)

Proof. The theorem will be easily proven by conditioning on Zi = z, using the law of total

30

probability and the independence assumption.
+∞
p(Z1 , Z2 , · · · , Zn < z|Zi = z)dFi (z)
p(i) = P {Zmax = Zi } =
−∞


n
+∞

=
p(Zj < z) dFi (z), i = 1, · · · , n.
−∞
j=1,j=i

(3.5)

We prove directly in the following lemma that {p(1), p(2), · · · , p(n)} given in (2) is indeed a
probability distribution.
Lemma 1. Assume p(1), p(2), · · · , p(n) are given by (2), then
p(1) + p(2) + · · · + p(n) = 1.
Proof. Let U(x) =

j=i Fj (x) and dv(x) = fi (x)dx. Then dU(x) =

k=i fk (x)

j=i=k Fj (x),

and V (x) = Fi (x). Therefore it follows from integration by parts that

p(i) = [
j
Therefore

Fj (x)]∞ −
0

+∞
k=i

−∞

[
Fj (x)]fk (x)dx = 1 −
pk .
j=k
k=i

n p(j) = 1
j=1

Following the same reasoning, the validity of the ArgMin probability distribution is also proven.
The odds-on-mean probability distribution, the well-known probability distribution that is used

31

in most probabilistic channel selections and routing, is defined as follows.

µ
φ(i) = n i ,
µi
i=1

(3.6)

where µi = E(Zi ), i = 1, · · · , n. In our application µi >= 0.
The distribution of state space probabilities of odds-on-mean is different than the ArgMax
distribution. In the following subsection we demonstrate this difference through an example, where
the random variable Z follows an exponential distribution.

3.2 Exponentially Distributed Random Variables
We let St denote the class of all subsets of {1, 2, ..., n} that contain exactly t nonidentical members,
t = 1, · · · , n.
Theorem 2. Let Z1 , · · · , Zn be independent exponentially distributed random variables with parameters λ1 , · · · , λn . Then the following holds:
a. The ArgMax probability distribution is given by
n−1
p(n) = 1 +
i=1

λn
−
λn + λi

+
{i,j,k}∈S3

+(−1)n

λn
λn + λi + λj

{i,j}∈S2
λn
+···
λn + λi + λj + λk

λn
.
λn + λ1 + λ2 + ... + λn−1

32

b. The ArgMin probability distribution is given by

q(i) =

λi
n λ .
j=1 j

To derive the probability distribution p(1), · · · , p(n), apply Theorem 2 using the transformation
πi (j) = j − i, for j > i, and πi (j) = n + j − i, for j ≤ i, and rearrange the set of the parameters
λ1 , · · · , λn to
{λi+1 , · · · , λn , λ1 , · · · , λi−1 , λi }.
Special Cases: Let n = 3. Then

λ1
λ1
λ1
−
+
,
λ1 + λ2 λ1 + λ3 λ1 + λ2 + λ3
λ2
λ2
λ2
p(2) = 1 −
−
+
,
λ2 + λ1 λ2 + λ3 λ1 + λ2 + λ3
λ3
λ3
λ3
−
+
.
p(3) = 1 −
λ3 + λ1 λ3 + λ2 λ1 + λ2 + λ3

p(1) = 1 −

In terms of µi = 1
λi
p(1) = 1 −

µ2
µ3
µ2 µ3
−
+
.
µ1 + µ2 µ1 + µ3 µ1 µ2 + µ1 µ3 + µ2 µ3

µ
1
For µ1 = 1, µ2 = 2, µ3 = 3, p(1) ≃ 1 , while φ(1) = µ +µ1 +µ = 6 . Therefore, we see that
8
1 2 3
the ArgMax distribution could be substantially different from the odds-on-mean distribution.

33

3.3 Primary Weight Measure
The primary weight measure is a metric with nonnegative values. It is developed to capture the
uniformity or diversity in spectrum bands available to a secondary user. Small values of PWM
indicate uniformity while large values of PWM indicate diversity. The PWM metric is evaluated
by measuring the distance between the two probability distributions: ArgMax and ArgMin.
The ArgMax probability distribution points to the channel that at an instant of time appears to
have the maximum idle frequency. Assume a node i is connected to j via a set of Nt available
channels at time t. A channel between node i and j is stable if it is less prone to the arrivals of
primary users. We let uij [k, t] be the random variable that represents the link (i, j) utilization
via channel k at time t; defined as the average frequency that a channel, sensed by the node i,
is available without any interruption from primary users. We suppress the time index t from our
notation whenever there is no ambiguity. In our simulation, we record the number of times that
a channel is sensed idle over a period of time and then use it for uij [k]. The probability that the
channel n between node i and j has the maximum utility is modeled by the ArgMax probability
distribution as follows:

pi,j (n) = P r{k ∗ = n} = P r uij [n] = max{uij [k], uij [k] ∈ E[i, j : t]} ,

(3.7)

where k ∗ is the channel between nodes i and j with maximum utilization at time t, and E[i, j; t] is
the set of all available channels between nodes i and j at time t.
Following the same analogy the ArgMin measure points to the channel that is less stable and
is highly exposed to the presence of primary users. Therefore, the probability that the channel h

34

between node i and j has the minimum utility is

qi,j (h) = P r{k ∗ = h} = P r uij [n] = min{ uij [k], uij [k] ∈ E[i, j : t]}

(3.8)

where k ∗ is the channel between i and j with minimum utilization at time t. More comprehensive
definitions of ArgMax and ArgMin probability distributions is presented in the Appendix.
Monitoring the ArgMax and ArgMin probability distributions provides interesting information
on the utilization of channels. If the primary users arrive frequently, the channels will be affected
almost uniformly by the primary users arrival. Therefore, the probability that a channel n has the
maximum idle frequency is close to the probability that the same channel has the minimum idle
frequency. Therefore the difference between pi,j (n)and qi,j (n) is small. Large gap between the
two probability distribution p and q imply a nonuniform spread of primary users on channels; and
hence, there exists a channel whose utilization is substantially larger. We measure the distance
between the distribution functions ArgMin and ArgMax by the Kullback-Leibler divergence (KL) [44] measure.
The K-L divergence is a non-symmetric measure of the difference between two probability distributions h and g. In probability theory, h represents the “true” distribution of data, observations,
or a precisely calculated theoretical distribution. The distribution g represents a theory, model, description, or approximation of h. It also can be interpreted as the opportunity lost for implementing
g instead of h.The K-L divergence for two discrete probability distributions h and g is defined to
be
DKL (h g) =

h(k) log
k

h(k)
.
g(k)

(3.9)

It requires that g(k) > 0 for all the values of k for which h(k) > 0. It possesses the properties that

35

• DKL (h g) = DKL (g h).
• DKL (h g) ≥ 0.
• DKL (h g) = 0 ⇔ h = g.
In the context of a cognitive network, with h = pi,j , g = qi,j , and channel utilization as the
average frequency that a channel is idle without any interruption from primary user, we have the
following interpretations for the K-L divergence.
• DKL (pi,j qi,j ): The expected utility acquired by transferring packets through channels
with maximum utilizations, instead of employing channels with minimum utilizations.
• DKL (pi,j qi,j ): The expected utility lost by transferring packets through channels with
minimum utilizations, instead of employing channels with maximum utilizations.
Primary Weight Measure at node i is denoted by δi,j defined by taking the average of the above
measures.
1
δi,j = {DKL (pi,j qi,j ) + DKL (qi,j pi,j )}.
2

(3.10)

The K-L divergence is not symmetric. However, the δi,j is symmetric in i, j and indicates the
degree of the nonuniform spread of primaries in channels between nodes i and j. When there is
no primary user around a particular node, pi,j = qi,j and the δi,j = 0. However, if primary
users are present, channel utilizations follow a continuous distribution so the D(pi,j qi,j ) > 0
and consequently δi,j > 0. For δi,j > 0, the larger the value of δi,j , the more the channels that
are less occupied by primary users, and thus have priority over the other channels in the vicinity
of the node i. When δi,j approaches zero, primary users are spread uniformly, and consequently
there is no privilege to any transition. Note that when primary users are present, the δi,j could be
near zero but not exactly equal.
36

To show how the PWM represents the nature of the spread of primary users on channels around
a node, let us look at the following numerical example.
Example 1. Assume there are two nodes 1 and 2, each one has 5 different channels available to
its neighbor j. Primary users arrive at each of these channels randomly. The ArgMax probability
distribution p1,j indicates the channel that is more likely to stay stable among the other channels.
For instance, if channel 3 has been idle the most during N sensing periods, then the p1,j (3) has
the maximum value. Now if the primaries are affecting all the channels with the same rate channel
3 might also be the channel that has been idle the least among other channels. Therefore, the
difference between p1,j (3) and q1,j (3) is small. As explained above, the PWM measure quantifies
this difference. Below, the primaries are spread around node 1 according to normal distribution and
around node 2 following a uniform distribution. After evaluating ArgMax and ArgMin probability
densities for all channels, we have the following results for each node respectively:

ch1
node 1;

ch3

ch4

ch5




p1,j  0.26 0.21 0.28 0.12 0.13 
,

q1,j 0.17 0.22 0.12 0.2 0.29
ch1

node 2;

ch2

ch2

ch3

ch4

ch5




p2,j  0.13 0.18 0.25 0.19 0.25 
.

q2,j 0.16 0.24 0.24 0.19 0.17

The δ1,j is 0.17 but the δ2,j is 0.02. As a result, the PWM is substantially lower when the channels
are affected uniformly by the arrivals of primary users.

37

3.4 Summary
In this chapter we proposed two new probability distributions called ArgMax and ArgMin that
could be used in probabilistic protocols. The ArgMax probability distribution locates the maximum random variable among a set of random variables, while the ArgMin locates the minimum
random variable. Using these two probability distributions, we introduced an interesting measure
called primary weight measure, which indicated the frequency and the nature of the distribution of
primaries around a particular node. A low value of the primary weight measure metric indicated
uniform and frequent primary users interruptions on the channels surrounding a node. With this
information MAC and routing decisions are taken more efficiently.

38

Chapter 4
Stochastic Modeling of Cognitive Radio
Networks and Probabilistic Routing
In this chapter, we focus on modeling a cognitive radio mesh network that is operating in a dynamic
environment similar to cities’ downtown. More specifically the system is modeled by a semiMarkov process. The ArgMax probability distribution that accurately identifies the most stable
available channel corresponding to a neighboring node is used as transition probabilities in the
stochastic process of the network. We show that the ArgMax probability distribution is a better
candidate than the frequently used OOM probability distribution through developing a Probabilistic
Selection Routing Procedure (PSRP) that adopts both probability distributions to guide packets
throughout the network. The simulation results suggest that ArgMax enables the routing scheme
to adapt to the network dynamic more quickly than the OOM probability distribution. The ArgMax
enhances the network throughput and end-to-end delay by over 30% when network load increases.
We also present an application of the ArgMin probability distribution by using it to select channels
with the lowest duration of availability, and to measure the throughput of the network. Since
the CRN is a stochastic system, the minimum spectral capacity is rarely zero. Therefore, the
identification of the minimum spectral capacity is useful in the development of a smart channel
allocation strategy. We show through simulation that with the help of ArgMin, the worst channel
in our setup could be used to transfer time-insensitive data at low rates.

39

In the next sections we present the definition of a Markov and Semi-Markov process that are
adopted in this dissertation to model the dynamics of a CRN. We also discuss the truncated distribution that is used to model the duration of channel availability in CRNs.

4.1 An Overview of Markov and Semi-Markov Process
A Markov chain is a system that moves from one state to the next in such a manner that the future
location is independent of the past if the present is known. In Markov chains we do not consider
the time it takes to transient from one state to another. Real systems are running on actual time.
Markov processes not only take into account the changes of state but also the actual times spent in
between [45].
The stochastic process Y = {Yt ∈ ℜ+ } is said to be a Markov process with state space E if
for any t, s ≥ 0 and j ∈ E,
P {Yt+s = j|Yu ; u ≤ t} = P {Yt+s = j|Yt}
When the conditional probability mentioned above is independent of t ≥ 0 for all i, j ∈ E and
s ≥ 0, the process Y is said to be a time-homogeneous Markov process. For fixed i, j ∈ E, the
function t → Pt (i, j) is called transition function, where
Pt (i, j) = P {Yt = j|Yt−1 = i}
and the family of matrices Pt , t ≥ 0, of the transition matrix Pt (i, j) is simply called the transition

40

matrix of the Markov process Y. The transition functions satisfy the following:

Pt (i, j) ≥ 0,

(4.1)

Pt (i, j) = 1,

(4.2)

Ps (i, k)Pt (k, j) = Pt+s (i, j).

(4.3)

j∈E
k∈E
A semi-Markov process is one that, when it enters state i, i ≥ 0 :
1. At the next state, it will enter state j with probability Pt (i, j), i, j ≥ 0
2. Given that the next state to be entered is j, the time until the transition from i to j occurs has
distribution Fij .
From the above dynamics we observed that the operation of the cognitive radio network is
similar to a semi-Markov process. It takes a random amount of time for the network traffic to
stay in node i before it moves to node j. Let nodes 1, 2, ...n denote the states of a stochastic
process, then the transition of packets could be modeled by a semi-Markov process. Since the
spectrum bands that could be used to transfer the packets from node i to node j are random and
are chosen based on the specified MAC and routing protocols, the transition probabilities Pij vary
for different networks. In this chapter, we use the ArgMax probability distribution to model the
Pij s. Based on the above definition, Let J(t) denote the states (nodes) entered at time t. Then J(t)
is a semi-Markov process with the state space equal to the number of nodes in the network. Next,
we present the definition of the truncated distribution. This distribution is used later to model the
density function of the available duration of channels.

41

4.2 Truncated Distributions
Since the distribution of available usage time of a channel is unknown, we use the concept of a
truncated distribution later to model the remaining usage time of available channels. Therefore the
definition of a truncated distribution is provided here for the ease of readers. Let Y be a random
variable whose distribution function F (y) is not concentrated entirely on [0, ∞). Let t[Y ] be a
random variable with distribution function

F (y) − F (0)
ˆ
= P (Y < y|Y ≥ 0), y ≥ 0.
F (y) =
1 − F (0)

(4.4)

Then t[Y ] is called truncated random variable; Zolotarev refers to t[Y ] as the cut off of Y at
zero [46].

4.3 Cognitive Radio Network Model
The Cognitive Radio Network (CRN) under study has the general architecture of a mesh network,
where there exists a gateway node (node G), providing the main access to the internet. The edge
routers are connected to the gateway by the intermediate relay routers and the clients who access
the edge routers send or receive information at any instant of time.
In a populated urban area, smart phones, PDAs, laptops, radios and TVs operate and use their
specific spectrum bands. In a cognitive radio network, a cellular phone acts as a SU sender on an
unlicensed 2.4 GHz spectrum band and a SU relay node for transferring a network traffic generated
by a personal laptop. A general cognitive radio mesh network architecture is shown in Figure 4.1.
In this example, there are 4 spectrum bands available and all the nodes send their traffic to the
gateway at the top. As it can be seen, the number of relay nodes and spectrum bands available vary

42

based on the strength of the radio equipment, inter arrival time of primary users and the number
of SUs located in the vicinity of a node. For instance, the senders S1 can access the relay R1 in

Figure 4.1 A simple mesh cognitive radio network architecture

the domain of spectrum band III but for the cellular phone sender S2, two spectrum bands III and
II are available, providing two relays R1 and R2. Since S2 is a secondary user, it should choose a
channel from the two spectrum bands that is less interrupted by the arrival of primary users.
When employing CRNs within a city, different sources of uncertainties are present. The behavior of primary users are unpredictable and produce uncertainty in the availability of channel
resources. Location discrepancy of primary users causes uncertainty in stability of channels. Furthermore, it is possible that some SUs are affected by many PUs while others are not. Therefore,
the transmission bandwidth for each node is variable and is divided among secondary nodes. Moreover, the wireless radio range is affected by the interference and reflection therefore the number of

43

Figure 4.2 The tree graph representation of the simple network architecture. The SU user S1 is
the node i = 1 in layer l = 3 that has M1,2 = 1 (R1) accessible neighbor, and is connected to it
by n1 = 1 channel. The SU user S3 is the node i = 3 that has M3,2 = 3 accessible neighbors
(R1, R2, R3), and is connected to R1 by n1 = 2 channels, to R2 by n2 = 2 channels and to R3 by
n3 = 1 channel.
accessible relays for a sender is not fixed. As a result, the dynamics of a CRN operating in a city
is unpredictable and should be studied under a stochastic framework. In the following sections we
present our stochastic modeling of such systems and the PSRP implementation.

4.3.1 Medium Access and Physical Layer Assumptions
We assume the channel is shared with a Non-Contiguous Orthogonal Frequency Division Multiplexing (NC-OFDM) technique. This multi-carrier modulation technique is based on the Orthogonal Frequency Multiplexing (OFDM) technique. By using the NC-OFDM, portions of the
target licensed spectrum are occupied by both primary and secondary users. This is achieved by
deactivating (i.e. nulling) subcarriers that can potentially interfere with other users. This form of
OFDMA fills in the available spectral gaps within the channel’s transmission bandwidth partially

44

occupied by other users while not sacrificing its error robustness [47].
The fluctuation of the wireless channel is modeled by the Rayleigh fading model. According
to the study in [48], Rayleigh fading is a useful model in heavily built-up city centers where there
is no line-of-sight between the transmitter and receiver.

4.3.2 Spectrum Usage Assumptions
Each spectrum band has a set of channels that are shared by other users with the help of OFDMA/NC
multiplexing. All SUs can tune to any combination of licensed channels using a single antenna
from different spectrums. Without loss of generality, one PU is associated with one spectrum band
(SB). The PU activity is modeled by an OFF/ON process. By the random arrival of PUs the ON
period is started.
To model such an agile network, a stochastic framework is considered. Nodes that are located
l hop away from the gateway, take a layer index l. Therefore a tree graph topology with L layers is
formed. The tree graph topology of our simple example is shown in Figure 6.1b. At a given time
t, from the perspective of a secondary user i in layer l, the number of accessible neighbors at each
upper layer l − 1 is denoted by Mi,l−1 (t). The number of channels between node i and each of
its accessible neighbors j is represented by Nij (t), j = 1, · · · , Mi,l−1 (t). Therefore, a channel
between node i and its upper layer neighbor j is presented by (i, nj ), nj = 1, · · · , Nij (t). We
summarize the notations in Table 6.1. We suppress the time index t and the layer index l whenever
there is no ambiguity.
Since Mi and Nij , j = 1, · · · , Mi are random, elaborating on their distribution is essential.
∗
Assume there are a total of Ml−1 nodes in layer l − 1. In the initial configuration of the network,
nodes identify the layer index of their neighbor nodes by exchanging control messages. We consider a mesh network where the nodes are stationary with long lasting energy. In this case, the hop
45

Table 4.1 Notations
Symbol
L
Mi,l−1 (t)
Nij (t)
W(i,n ) (t)
j
X(i,n ) (t)
j
Y(i,n ) (t)
j

Description.
Number of layers.
Number of nodes in layer l −1 accessible to a node
i in layer l at time t.
Number of channels available between the node i
and its neighbor j at time t.
Idle period of channels (i, nj ); j
=
1, · · · , Mi,l−1 (t), nj = 1, · · · , Nij (t) at
time t.
Inter arrival time of PUs on the channels (i, nj ) of
a spectrum band at time t .
The amount of time that the PU or other secondary
users occupy the channels (i, nj ) at time t.

number would not be dynamic. A node j in layer l − 1 is considered assessable if it is within node
i’s transmission range. For simplicity, we assume that if j is accessible by i, i is also accessible by
j. Let di be the transmission range of node i, and dij represent the radial distance of node i from
node j at time t. Then the number of accessible neighbors at node i is
∗
Ml−1
I[dij < di ],

Mi =

(4.5)

j=1
where I(A) is the indicator function: I(A) = 1, if A is true, and I(A)=0, if A is false.
From [47], when the channel is experiencing Rayleigh fading, the total available bandwidth
f(i,n ) of channel (i, nj ) at time t is
j
f(i,n ) = (1 − α(i,n ) )B(i,n ) ,
j
j
j

(4.6)

where B(i,n ) is the total bandwidth (Hz), and α(i,n ) is the incumbent occupancy of the channel
j
j
(i, nj ) at time t. The signal-to-noise ratio gain SNRg(i,n ) of the channel (i, nj ) at time t roughly
j

46

indicates the occupancy influence on the channel (the SNR of a shared channel over the SNR of
the same channel when it is not shared by other users) and is given by

SNRg(i,n ) = −20 log10 (1 − α(i,n ) ).
j
j

(4.7)

By substituting (4.7) into (4.6), we have

f(i,n ) = B(i,n ) 10
j
j

(−SNRg(i,n ) /20)
j
.

(4.8)

We represent the inter-arrival time of PUs on the channel (i, nj ) by random variable X(i,n ) with
j
density function ut (x) from a SB. The period of occupancy is represented by Y(i,n ) = 1/f(i,n )
j
j
in seconds with density function vt (y). Let W(i,n ) = X(i,n ) − Y(i,n ) denote the available
j
j
j
usage time of the nth channel between nodes i and j. Then the channel (i, nj ) is available if
W(i,n ) > 0. Therefore, the number of channels available between nodes i and j at time t is given
j
by
Nij =

N∗
nj =1

I[W(i,n ) > 0],
j

(4.9)

where N ∗ is the total number of channels between node i and j from different spectrum bands. We
assume the system is in a steady state, and there are stationary distributions on Mi,l−1 and Nij ,
not depending on time t. Therefore, the expected number of available nodes is
∗
Ml−1
pij ,

E(Mi,l−1 ) =

(4.10)

j=1
where pij = P [dij < di ], depends on the strength of the radio signal. Moreover, the expected

47

number of available channels between nodes i and j is
N∗

E(Nij ) =

nj =1

P [W(i,n ) > 0].
j

(4.11)

Recall that the PU inter-arrival time on channel (i, nj ) is represented by a random variable
X(i,n ) with density function ut (x), and the occupancy period of other users is shown by a random
j
variable Y(i,n ) . Now, by using the definition of the truncated distribution given in section 4.2 the
j
density function of t[W(i,n ) ], the truncation of W(i,n ) at zero is given by
j
j
fW (w)
t
, w≥0
ft[W ] (w) =
1 − FW (0)
where







fW (x) =
t





(4.12)

∞
0 vt (s − x)ut (s)ds, x ≤ 0,
∞
x vt (s − x)ut (s)ds, x ≥ 0.

4.4 Probabilistic Routing Approach
In this section we propose the probabilistic routing approach (PSRP) and the usage of ArgMax
probability distribution. In the mesh CRN, in which packets move to the upper layers to reach
the gateway, transitions form a Markov chain whose states are transient, except for the gateway,
which is absorbing. The transition probabilities are not stationary in time, but certain stationary
assumptions are made as follows.
• The parameters of the available channel’s usage time distributions could be time dependent.
For instance, if the available channel’s usage time has Gamma distribution, then the parameters αt , βt might be time dependent.
48

• The accessible states from an upper layer are time dependent random processes, but their
distributions are time invariant.
• The transition probabilities are time dependent only because of the time dependency of the
available usage time distribution parameters. The PSRP is self updating, in the sense that
at the commence of each transition it receives information on the number of spectrums and
their time portion of availability. Then, PSRP estimates the parameters of the distributions
of the idle period of channels using idle period data that are stored and updated.
Odds-On-Mean (OOM) is an intuitive nonparametric procedure that computes transition probabilities using sample means of the channel idle period data sets. A parametric approach is more
informative and gives deep insights into the underlying statistical distributions of the variables
governing the system. We should bring to the attention of the reader that PSRP is not a complete
routing protocol. It is an uplink routing procedure with the purpose of presenting the strength of
the ArgMax over OOM probability distribution. (PSRP will be shown to evolve into a routing
protocol in the next chapter.) Following this procedure, node i at layer l constructs its localized
Available Resources (AR) matrix at time t after communicating with its neighbors and sensing its
environment as follows.




t[W1,1 ] · · ·
t[W1,1 ] 
 t[W1,1 ]




 t[W ]
t[W1,2 ] · · ·
t[W1,2 ] 
1,2


ARl [i; M, N1 , ..., Nj ] = 
.


.
.
.
..
.
.
.


.
.
.
.




t[W1,N ] t[W1,N ] · · · t[W1,N ]
1
2
M
Since the AR matrix is constructed for node i in a specific layer l at time t, these indices are
exhibited from our notation when we refer to AR matrix elements. Each column corresponds to a

49

neighboring node j = 1, · · · , M and Nj is the size of column j that represents the total number
of channels available linking node i to node j at time t. The variation of the column index is seen
in the NM index of t[W1,N ] element of the matrix. The random variable t[W(i,n ) ] is the
M
j
available usage time of each channel (i, nj ) at time t. This quantity is related to the available
bandwidth as explained in the previous section. Note that the dimensions M, N1 , ..., Nj are taken
to be random as the AR matrix varies for one transition of packets from one layer to another.
The position of the channel (i, n∗ ) with the highest available bandwidth is unknown to node i.
j
Hence, the idea is to define a probability distribution PS on the set of states S ≡ S[i; M, N1 , ..., NM ] =
{(i, nj ), j = 1, ....., M, nj = 1, ..., Nj } such that transition to S[i, M, N1 , ..., NM ] occurs based
on PS targeting a channel with the highest available usage time for given values of M, N1 , ..., NM .
The ArgMax probability distribution locates the index of the maximum element of an array of
random variables. Therefore, based on equation 3.7, the transition distribution PS based on the
random available usage time of channels t[W(i,n ) ] is
j

PS (i, n∗ ) = P
j

t[W(i,n∗ ) ] = max[ t[W(i,n ) ], (i, nj ) ∈ S] .
j
j

In statistics, whenever the distribution of the estimator is unavailable or is computationally
challenging, simulation methods are used to estimate the probability distribution. This method
is used by Kulldorff [49]. In network applications, the timely computation of PS is very important. We use an idea similar to what Kulldroff suggested, and propose a simulation method in the
following section to estimate the ArgMax probabilities online.
The OOM probability distribution is the well known probability distribution that is used in
most probabilistic routing applications. According to OOM probability distribution in equation

50

4.13, PS is

µ(i, n∗ )
j
∗) =
PS (i, nj
,
Nm
M
µ(i, nj )
j=1 nj =1

(4.13)

where µ(i, n∗ ) is the average available bandwidth of the channel (i, n∗ ) between the node i and j.
j
j
This well known probability distribution is often used since its computation is simple. However,
recall that the node in a particular layer wants to identify the path among all the channels from
different bands that has the most available bandwidth to transfer the packets to its neighbors in the
upper layer. Therefore, OOM does not accurately point to the maximum location.

4.5 Model implementation
This section describes implementation details of the ArgMax and ArgMin distributions and the
route selection scheme. We rely on the ability of the software defined radio transceivers embedded
in the nodes to detect the number of spectrums available. With the use of NC-OFDMA MAC layer,
a SU could select from different channels in a spectrum band and share the channel with other
SUs. SUs communicate with each other using a common control channel in the lower portion of
the spectrum where the transmission range is higher. The use of the common control channel can
improve the reliability of the framework [19]. In the initial configuration of the network, nodes
transmit fast messages to each other and try to calculate their distance based on the number of hops
from the gateway node. After this step, each node obtains an extra identity index l indicating its
layer allocation, which will identify its upper layer neighbors. There is a time period allocated to
a node to complete its packet transmission. This time is divided into two parts: decision making
time td and transmission time ts . During the decision making time td , the following actions are

51

completed:
1. Node i starts handshaking with each of its upper layer neighbors, and obtains the SNRg(i,n )
j
of every channel (i, nj ) connecting its neighbor j. SNRg(i,n ) is evaluated at the receiver
j
antennas of neighbors.
2. Node i evaluates the available bandwidth, f(i,n ) , of each channel (i, nj ) from their SNRg(i,n )
j
j
based on equation 6.1.
3. The AR matrix is constructed using the values of f(i,n ) . It should be noted that the usage
j
time t[W(i,n ) ] of the channel has a one-to-one relationship with the available bandwidth.
j
The more the available bandwidth, the longer the usage time.
t[W(i,n ) ] is used instead of f(i,n ) in our simulation model to portray a more realistic
j
j
setting, where our model distributions are gathered by the measurement study in [50]. Notice
that the two values (i.e., t[W(i,n ) ], f(i,n ) ) could be used interchangeably.
j
j
4. Node i evaluates the ArgMax or ArgMin probability distributions state space by analyzing
its AR matrix as follows:
Simulation Procedure to Estimate ArgMax and Argmin
ArgMax indicates the location of the maximum element and ArgMin indicates the location
of the minimum element. Hence in the following steps, whenever the ArgMin needs to be
implemented instead of the ArgMax the maximum is replaced by the minimum.
(a) Node i finds the channel (i, n∗ ) that has the maximum (minimum) t[W(i,n ) ] among
j
j
the AR matrix elements.
(b) Every time node i tries to route its packets, it looks at its past AR matrices and evaluates
the likelihood that the channel (i, n∗ ) has the maximum (minimum) t[W(i,n ) ]. For
j
j
52

example, consider node i, making its routing decision for the 10th time. If in 4 out of
10 series of stored AR matrices, the channel (i, n∗ ) has the maximum available usage
j
time, then the ArgMax probability of (i, n∗ ) is 4/10. This method of estimating the
j
ArgMax and ArgMin probability distributions is adopted from the method used in [49].
5. Having the probability of each channel, node i applies a Monte Carlo simulation to obtain
its routing selection information (i.e. the index of the next hop and the corresponding channel). The Monte Carlo performs a basic selection of candidates based on their probability
distributions. We like to emphasize that this simple and non-complex step exists in every
probabilistic routing protocol that locates the next node with its transition probability.
6. At this step, node i has the routing information and starts its transmission of packets during
the transmission time ts .
The above steps are summarized in Figure 4.3.

Figure 4.3 The node selection procedure

53

The run time complexity of the proposed algorithm is Θ(n), where n = N ∗ ×M ∗ , N ∗ and M ∗
correspond to the maximum row and column size of the AR matrix. The complexity is the same
as OOM since the summation over all elements of the AR matrix is needed in estimating OOM as
well. We discarded the memory of the node after taking a sample of 100 AR matrices. The OOM
finds the maximum average value among the elements of AR matrix. Therefore, to obtain the
average value empirically, the sum of the 100 samples of each element should be divided by 100.
With 100 samples, we achieve satisfactory estimates for the OOM and ArgMax probability masses.
Note that in ArgMax, each time the AR matrix is stored, the index of the maximum variable
is evaluated and stored. Overall, the distributed nature of the algorithm makes the maximum
number of nodes and channels bounded. Therefore, the amount of memory needed to evaluate
the ArgMax is bounded. By using advance processors such as RAW proposed in [51] or multicore SIMD architecture presented in [52] for software defined radios, the PSRP algorithm is easily
implementable on small portable devices such as a cellphone [53].

4.6 Simulation Model
In order to analyze the effect of ArgMax and ArgMin, we simulate a cognitive radio network that
operates in a city center. Through our simulation setup we are able to drive actual workloads from
the network with varying sizes and dynamical parameters. Thus we have more flexibility over the
existing testbeds. In order to simulate a cognitive radio environment in a city center, we arrange the
nodes into a tree graph topology shown in Figure 6.1b. An extra identity index l is assigned to each
node, indicating the node’s layer allocation from other nodes. At time t, the number of accessible
nodes Mi,l−1 from the upper layer vary for each node i depending on the radio signal strength,
which is affected by interference, reflection, and radio power. In the initial configuration, each

54

node i has a random value for its transmission range di . In addition, a random value is assigned
for the radial distance of node j from node i, dij . Then Mi,l−1 is evaluated using equation (4.5).
For simplicity, if a node j is accessible from its lower layer node i, then node i is also accessible
by j.

4.6.1 Modeling of Inter-arrival Time of Primary Users
The primary user’s traffic follows a semi-Markov process with OFF/ON period following the exponential distribution with mean λ. This model is based on the measurement study in [54]. As λ
gets larger, the channel is available for a longer period of time to be used by secondary users. We
change the value of λ to see the effect of inter-arrival time of primary users on the performance of
the network.

4.6.2 Channel Occupancy Modeling
Once the channel is available, it is shared among other users. The usage time of a channel Y
is always a positive number. Hence, gamma and lognormal distributions are the two appropriate
candidates. We use both of the two distributions to cover a wide range of channel usage patterns.
The lognormal distribution is used with different mean µ and standard deviation σ. Based on the
measurement study [50] performed on a cellular network in a crowded urban area, the channel
occupancy duration is represented by lognormal distribution. Note that the larger the value of µ,
the more occupied the channel would be, hence the smaller available usage time t[W(i,n ) ] on
j
that channel. Later, to cover traffic patterns other than the one in cellular networks, we substitute
the lognormal distribution with the gamma distribution. The two parameters α and β of gamma
distribution control the amount of channel usage similar to lognormal distribution parameters.

55

4.6.3 Modeling of Available Channel Usage Time
The available channel usage times, t[W(i,n ) ]s, are generated by truncating X − Y values at zero.
j
The truncated density function is evaluated based on equation 4.12. For each node j there are a
total of Nij channels available, which are found based on equation 4.9.
In our simulation setup, we first use the simulation technique described in step 4 of the previous
section to evaluate ArgMax probabilities. After assigning the probabilities, a neighboring node
from the lower layer is chosen based on a Monte Carlo simulation on channel probabilities. We
use these probabilities in PSRP and compare its performance with the case when OOM is used
instead of ArgMax. Second, we find ArgMin probability distribution by simply evaluating the
minimum element in our simulation instead of the maximum element, and provide the minimal
network throughput when the most unstable channels are used. For both scenarios, our simulated
model retains and updates the AR matrix values every 100 seconds.
By changing the distributions of primary user arrival patterns and their corresponding parameters, we are able to analyze the performance of ArgMax in different environmental dynamics.
We believe our simulation setup mimics real implementations to a good extend because firstly, we
selected the distributions in our simulation based on measurement studies on real networks as explained above. Secondly, we tried different distributions as well that were not reported in studies,
but are highly probable of occurring in nature such as gamma distribution.

4.7 Results
In this section, we first present the simulation results and compare the performance of ArgMax
probability distribution with OOM probability distribution in a probabilistic selection routing algorithm (PSRP). Second we elaborate on the applications of ArgMin by demonstrating network
56

throughput when channels with minimum duration of availability are used to route packets.

4.7.1 PSRP with ArgMax Probability Distribution
We present the performance of the network in terms of throughput and end-to-end delay under
variations of primary user arrival distribution, network load, and network size. We expect to see
improvement when the amount of traffic is increased because of the nature of the ArgMax probability distribution. As a result, we evaluate the network with different sending rates to observe
different loads on the network.
A network with 75 nodes is selected and the simulation runs for 12 hours. The number of
accessible channels for each node changes every 100 seconds. In our simulation model, other SUs
behave in diverse manners; a heavy user who uses a large portion of the spectrum, leaving a small
portion to be used by others, a light user who consumes a small portion of the spectrum band,
and an average user who uses the spectrum band in a moderate fashion. Therefore, three kinds
of channels could be available. A lognormal distribution with means 0.8, 0.2, and 0.5, a variance
of 0.5, and a gamma distribution with α = 1.5, 2, 3 and β = 1 are used to model this diversity.
As explained in previous sections, the truncated distribution of available usage time of channels
is estimated using the exponential model for inter-arrival of PUs on channels with λ = 30sec and
the lognormal or gamma distribution model of SUs. We have 5 spectrum bands with a minimum
bandwidth of 6Mb/sec (which could correspond to FM radio band) and a maximum of 144Mb/sec
(similar to a TV channel). Note that a spectrum band can have different numbers of channels
depending on its type. The bandwidth of each spectrum is divided equally among its channels.
For example, the 144Mb/sec spectrum band has 6 channels, each with a bandwidth of 24 Mb/sec.
Overall we have 30 channels with heterogeneous bandwidths in our simulation.
For the routing layer, the total available usage time of each channel is important for selecting
57

the next node and the access techniques in the MAC layer are responsible for providing the node
with an interference free channel from a band. Note that in a cognitive radio the transmission rate
varies based on the type of available channel.
Nodes 67 to 78 are sources and they generate packets according to a Poisson process. The
packets mean arrival rate follows an exponential distribution between 30ms to 100ms. The packets
size is 2000 bytes. We change the sending rate of the packets and observe the performance of the
network.
Table 4.2 shows the difference between the average throughput for the two methods when sending rate is changed and lognormal distribution is used to model the channel occupancy of SUs. The
PSRP that uses ArgMax in its decision making outperforms the PSRP with OOM. As the sending
rate is over 5Mb/sec, ArgMax performs much better than OOM because locating the most stable
path with the highest amount of available bandwidth is more crucial when the load increases. In
dynamic environments, mislabeling the most stable path would result in a greater amount of packet
loss and unwanted delay for the remaining packets. ArgMax chooses the path more precisely and
is able to learn the behavior of the network faster. In a very simple analogy, the difference is similar to the difference of selecting a maximum value over an average value from a series of data.
The difference is more obvious when the system is in need of timely, accurate decisions. We see
the same trend in throughput when gamma distribution is used to model SU behavior in Table 4.3.
Therefore we conclude that ArgMax is able to identify the channel with maximum duration of
availability regardless of the shape of its corresponding underlying distribution.
We present the overall end-to-end delay of the network with varying sending rates for both
OOM and ArgMax in Table 4.4. Our results show that the estimation of the ArgMax probability
through our proposed simulation scheme did not increase the delay and even reduced it by 60%.
To investigate the effect of network size, we changed the number of layers l from 6 to 12 while
58

Table 4.2 Average throughput with 95% confidence interval for different sending rates, l=12, 78
nodes
Rate (Mb/s) OOM Throughput ArgMax Throughput
2
0.59± 0.0104
0.78± 0.0033
4
0.88±0.0061
0.96±0.0017
6
0.50±0.0095
0.87±0.0052
8
0.30±0.0071
0.64±0.0122
Table 4.3 Average throughput with 95% confidence interval for different sending rate with
Gamma distribution, l=12, 78 nodes
Rate (Mb/s) OOM Throughput ArgMax Throughput
2
0.873± 0.004
0.958± 0.0004
4
0.653±0.0018
0.935±0.002
6
0.471±0.0101
0.861±0.006
8
0.366±0.0074
0.751±0.008
Table 4.4 95% confidence interval of average end-to-end delay for different rates
Rate(Mb/sec)
6
8
10

OOM Delay(msec) ArgMax Delay(msec)
383±21
149± 4
642± 34
285± 9
654±39
397± 12

keeping the sending rate constant at a high rate of 8Mb/sec. Table 4.5 shows that network size has
little effect on the average throughput of both ArgMax and OOM. This is due to the decentralized
nature of the PSRP algorithm. The ArgMax performs better because of its accuracy in locating the
path with the maximum available usage time.
Table 4.5 Average throughput with 95% confidence interval for different network size, sending
rate is 8Mb/sec
l
6
8
10
12

OOM Throughput ArgMax Throughput
0.41± 0.008
0.66±0.010
0.36±0.007
0.65±0.011
0.30±0.005
0.64±0.014
0.32±0.006
0.6±0.008

Figure 4.4 and Figure 4.5 show the average throughput and the average end-to-end delay when
the mean duration of the idle period of PUs λ changes from 15sec to 60sec. As the idle period
59

of PUs increases, the average throughput increases as well, while the average delay decreases.
However, the average throughput and the average delay change gradually when ArgMax is used
because the most stable channel is correctly identified, even when the idle period of PUs is small.
When OOM is used, the average throughput increases and the average delay decreases abruptly
after 30sec because the channels are more stable after this period on average.
1

Average throughput

0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2

ArgMax
30

45

Primary user average idle period λ (sec)

OOM
60

Figure 4.4 Effect of primary users on average throughput for a network with 12 layers and 78
nodes.

Figures 4.6 and 4.7 show the average number of MTUs stored in node queues and the maximum
number of dropped packets for each node. Nodes 67 to 78 are not shown in the figures since
they are source nodes. The distribution of the number of packets is uniform when PSRP uses
ArgMax, distributing the packets fairly over the network nodes by correctly identifying the network
dynamics. When PSRP uses OOM, the nodes that are closer to the source fill up fast, but due to the
incorrect decision of a stable link, most of the packets are dropped during their trip from source to
destination. Therefore the resources of the nodes closer to the gateway are wasted.

60

Average end−to−end delay(msec)

2000

OOM

ArgMax

1500

1000

500

0
1

1.5

2

2.5

3

Primary user average idle period λ(sec)

3.5

4

Figure 4.5 Effect of primary users on average delay for a network with 12 layers and 78 nodes.

Figure 4.6 Queue Status for a network with 12 layers and 78 nodes.

4.7.2 PSRP with ArgMin Probability Distribution
In this section we evaluate the spectral resources that are available to a node by a channel subject
to frequent arrivals of primary users. A node always chooses a channel that is more stable at any

61

Figure 4.7 Dropped packets status for a network with 12 layers and 78 nodes.
given time and ignores the resources of other channels available. In the stochastic framework of
cognitive radio networks, a channel can never be categorized as 100% occupied, but it is given
a low priority probabilistically. An interesting observation is to determine the minimal spectral
capacity that is offered by our network configuration. In other words, we determine the minimum
rate that can be accommodated when the data is sent over the most unstable channels. Figure 4.8
shows the percentage of packets that are successfully received by the gateway when the packets
are sent over the worst channels. In the worst case scenario, at 2Mb/sec, 30% of packets reach
the destination successfully. Using this information, we change the sending rate from 60Kb/sec to
300Kb/sec, which is only half of 600Kb/sec (i.e. 30% of 2Mb/sec). The results are shown in Figure
4.9. We can see that about 80% of packets are successfully transferred using the channel with the
lowest duration of availability at low rates. This result shows that with proper rate scheduling
and data classification, cognitive radio networks can truly achieve maximum spectral utilization.
With the help of ArgMin probability distribution this minimum capacity is identified and used

62

for transferring data that do not require high bandwidths or are not time-sensitive. Whenever
identification of a minimum random variable is needed, ArgMin comes into play. There are many
other scenarios in networking specifically in information theory or coding, where we need such
identifications.

Packet recieved ratio

0.4
0.3
0.2
0.1
0
0

2

4
6
Rate(Mb/sec)

8

Figure 4.8 Minimum packet delivery ratio of a network with 12 layers and 78 nodes under
frequent arrival of primary users.

Packet received ratio

1
0.8
0.6
0.4
0.2
0
50

100

150
200
Rate(kb/sec)

250

300

Figure 4.9 Minimum packet delivery ratio of a network with 12 layers and 78 nodes under
frequent arrival of primary users at low rates.

63

4.8 Summary
In this chapter we proposed a decentralized probabilistic routing scheme (PSRP) for a cognitive
radio operating in a crowded urban area. PSRP uses ArgMax probability distribution to decide
among neighboring nodes with variable band channels. To show the strength of ArgMax over the
classical Odds-On-Mean probability distribution, which is used in most probabilistic protocols,
PSRP is implemented with both probability distributions. We have shown that the ArgMax is more
accurate in modeling and estimating the location of the maximum available band and increases the
aggregate throughput significantly. It also decreases the network delay by 60% when the traffic is
high. In the next chapter we extend the PSRP into an stochastic protocol.

64

Chapter 5
Stochastic Routing Protocol
In dynamic cognitive radio mesh networks the variation in spectrum diversity and availability is
high due to the presence and the sojourn time of primary users. In this chapter, we use the developed Primary Weight Measure (PWM) metric in Chapter that measures the uniformity of spread
of primary users around a particular node and propose a decentralized routing algorithm called
Primary Spread Aware Routing Protocol (PSARP). The PSARP is an adaptive per-hop routing
scheme that, unlike the predecessor schemes, is nondeterministic. The traffic from a source to
a destination is modeled by a Markov process, and packets are forwarded hop by hop based on
transition probabilities that reflect the next hop spectral availability as well as the entire path quality. The PWM metrics of the nodes are relayed via back-pressure and are used in the construction
of transition probabilities. On a cognitive-based NS2 network simulator, we compare the performance of PSARP with two previously developed routing protocols for dynamic environment. We
also develop a Cognitive Stochastic Routing (CSR) protocol based on the PSARP stochastic framework that uses backlogged queue capacity instead of PWM. Our results show higher throughput
in PSARP and CSR, which indicate the advantage of stochastic-based routing in a dynamic environment. In addition, PSARP with its PWM measure is more successful in choosing the best path
due to the correct identification of the primary users’ distribution, and performs substantially better
than CSR at high rates.

65

5.1 Stochastic Routing
Stochastic routing is the term given to the process of locating the best route in a stochastic environment using stochastic systems tools. In theory of stochastic systems, the observed system
parameters are random and variable. The evolution of the system is governed by transitional probabilities that estimate the possibility of system landing on a next state. System designers create
transitional probabilities according to their preference. We observed that the transition of packets
from a source to a destination in a cognitive radio network is a stochastic process since the random
arrival of primary users on channels make the next state of the system (next hop) in the path indeterministic. Packets may be sent to a next hop but never reach that hop due to the arrival of primary
users. Therefore, we develop a stochastic routing scheme that uses the transitional probabilities to
find the most stable path. Our protocol is different in nature from all other previous work since it is
not deterministic. First, we begin by presenting the protocol operating environment assumptions.
Next, the theoretical modeling is presented and finally, the protocol implementation is discussed.

5.1.1 PSARP Operating Environment Assumptions
We consider a mesh network of secondary users in the downtown area of a city, where there are
heterogenous primary users with a variety of spectrum availability. Secondary users may choose
their particular destinations randomly. We also assume that all users in our system have little to no
mobility.

5.1.1.1 Primary User Model
We consider a number of primary users with different transmission range and dynamic behavior.
The occupancy pattern of our primary users are random and categorized as follows: A heavy user

66

that occupies the channel for a longer period of time (e.g., TV band users), a medium user that
has an average occupancy period, and a light user has a short period of usage similar to a cellular
telephony and data traffic patterns. A number of primary users are randomly deployed throughout
the network. Therefore, the secondary channel availability is not consistent. Some secondary users
might be affected by more primary users than others. Primary users access their dedicated channel
anytime they desire without notifying other secondary users on the channel.

5.1.1.2 Secondary User Model
The secondary users have access to a number of channels from different spectrum bands. The
medium access is CSMA. Hence, once a channel is available, other secondary users compete to
access the channel and transfer their packets when the channel is sensed idle. If a secondary users
senses a primary user transmission, it interrupts its transmission, queues up its packet, and waits
for the next channel availability.

5.1.1.3 Medium Access and Physical Medium Model.
The CSMA technique is used by the secondary users to access the physical channel. The CSMA is
enhanced with a PU detection mechanism. By the presence of a primary user, the secondary users
would not transmit and back-off until primary users have left the channel. Secondary users are
equipped with two radio interfaces with omni directional antennas. A control channel is dedicated
to the exchange of control packets and is monitored by one interface. Due to the irregular arrival of
primary users, a dedicated control channel is necessary for the reliable transfer of control packets.
The other interface monitors the data channels. The wireless channel has the Rayleigh fading
model. According to [48], Rayleigh fading is appropriate for an urban area, where there is no line
of sight between the sender and the receiver.
67

5.1.2 Theory
As explained in previous chapter, the flow of packets initiated from a sender to a receiver can be
modeled by a Markov process with time dependent transition probabilities. The transitions are step
wise from one node to another [55]. All the nodes of a particular flow form the transient states of
the Markov chain except the receiver, which is absorbing. Let us consider a secondary network. At
a time epoch t, a secondary user sender i chooses any of its neighboring nodes j, {j = i, j ∈ Mi,t }
(Mi,t : total number of neighboring nodes of i accessible from i at time t) to send its packets to
the destination d via channel k, k = 1, · · · , Nij based on the transition probabilities pt[ij;d] (k).
The variable Nij represents the total available channels between nodes i and j at time t. The time
index t is suppressed from now in our notations whenever there is no ambiguity.
To have a reliable transmission, from a local perspective, the node i at time t looks for a
neighboring node j with a reliable link connection. In a global view however, the neighboring
node j should be able to forward received packets to the desired destination. In other words, node
j should be on a valid path to the destination. Therefore, in any formulation for pt[ij;d] (k), the
following two criteria must be addressed.
• Neighbor’s forwarding ability
• Neighbor’s link quality
5.1.2.1 Neighbor’s forwarding ability
To model a node’s forwarding ability, a selection probability gd (j) is assigned to each neighbor
node j for a specific ultimate destination d at time t based on its maximum PWM value ∆j .
Probabilistically, the transition must go through the nodes that have maximum PWM meaning
they are less affected by the primary users. Therefore, gd (j) is found based on the odds on PWM
68

probability distribution as follows.
∆j

gd (j) =

∆m

, j ∈ Mi,d

(5.1)

m∈Mi,d
where Mi,d consists of the node i neighbor nodes that could be chosen for the ultimate destination
d at time t.
∆j = max{δj,m , m ∈ Mj,d }

(5.2)

The set Mi,d is identified in the initial setup phase of the PSARP protocol. As explained in section
3.3, when ∆j = 0, there are no primary users around the node j. Therefore, gd (j) = 1.
5.1.2.2 Link reliability
A link between node i and node j is stable if it is less interrupted by the primary users. When a
primary user is absent, the channel is used by other secondary users. Therefore, a link reliability
metric should also capture other secondary users traffic load on the channel. We use the ArgMax
probability distribution to characterize the channel that has the maximum utility among the set of
all available channels. Therefore, the probability that channel n at node i has the maximum utility
is Pij (n), evaluated using equation (3.7).

5.1.2.3 System Transitional Probabilities
Let us summarize the probabilistic dynamics of transitions. A node i seeks an accessible node
with maximum PWM through a link with maximum utilization at a given epoch. The system has
stochastic dynamics; consequently, the desirable nodes and links are subject to change. The transition has two stages: the selection of the desirable neighboring node for the ultimate destination d,

69

and the selection of the desirable link. The tree diagram with root i and branches [i → j, j → kj ],
j = 1, · · · , Mi,d , kj = 1, · · · , Nij , shown in Figure 5.1, depicts the transitions from i to j through
channel k. Thus, the transition probability from i to j through the channel k at time t is

Figure 5.1 Transition probabilities tree diagram

p[ij;d] (k) = gd (j)Pij (k).

70

(5.3)

Therefore the transition is from i to any of the states in {(j, k) : j = 1, · · · , Mi,d , kj =
1, · · · , Nij } The following matrix governs the transition probabilities.




p[i2;d] (1) · · ·
p[iM ;d] (1) 
 p[i1;d] (1)
i,d




 p
(2)
p[i2;d] (2) · · ·
p[iM ;d] (2) 
 [i1;d]

i,d
,
Tid = 


.
.
.
..


.
.
.
.
.
.
.






p[i1;d] (Ni1 ) p[i2;d] (Ni2 ) · · · p[iM ;d] (NiM )
i,d
i,d

(5.4)

The number of columns of Tid , Mi,d , is the number of neighbors available to node i leading to
destination d at time t, and the number of rows, Nij , is the number of channels available between
node i and its neighbor j at time t.
Ni,j Mi,d
Clearly,
Pij,d [t; chk ] = 1. We see this is satisfied since the elements of the
jk
transition matrix Tid are the ending branches of the conditional tree diagram in Figure 5.1. In
the next subsection, we present the framework and forwarding mechanism based on the transition
matrix Tid of PSARP.

5.1.3 PSARP Implementation
In this section we layout the implementation of the stochastic protocol. First, we list different
routing components that are used to make the protocol reliable and sustainable in actual implementation. Second, we explain how these components are constructed. Finally, we explain the
adaptive per-hop forwarding procedure by following packets from a source to a destination. We
categorized the routing components into:
1. Tables
2. Control messages
71

3. Transition probabilities

5.1.3.1 PSARP Tables
Two tables are held and maintained at each CR nodes.
• Neighbor table
Similar to AODV based protocols [31], CODV [32], OSDRP [33], each node holds a table
to store some attributes of its neighbors. These attributes will eliminate the count to infinity
and the discontinuity problems that are usually present in a decentralized decision making
protocols. A neighbor table entry corresponding to a neighbor j is shown in Table 5.1.
Table 5.1 An entry of the neighbor Table
Neighbor Id (j)
Destination Id (d)
Number of hops
Authorization index (connectivity attribute)
Time to live (Expiration time for this node)
Max PWM, ∆j
Reception channel k ∗ .
The channel utilization effect is captured in evaluating the channel k ∗ that has the maximum
utility around neighbor j by using equation (3.7).
• Forwarding table
The entries in the forwarding table construct the sets of candidates among the neighbors
that are suitable to receive packets for a specific destination. See Table 5.2. Each node
uses the forwarding table information to construct its transitional probabilities. This process is explained in detail in the following subsections. Active neighbors are those with a

72

lower number of hops and a valid authorization index; this information is obtained from the
neighbor table. Note that the forwarding table also exists in the other routing protocols.
Table 5.2 An entry of the forwarding Table
Destination
List of authorized neighbors
p[ij;d] (k) transition probabilities
for all authorized neighbors

5.1.3.2 Control Messages
In order to update the entries of the neighbor table and forwarding table according to the system
dynamics, neighbors exchange two types of control messages.
• HELLO Packet
Similar to decentralized protocols, HELLO packets are responsible to update the neighbor
and forwarding table of each node. A HELLO packet carries the destination of the next
packet waiting to be transmitted. The HELLO packet is generated when a node does not
have an entry for a particular destination or when the transition probability update period is
reached. HELLO packets are broadcast to neighbors on the common control channel with
the following information:
– Destination
– Number of hops
– Max PWM, ∆j
– Received channel ID
Upon receiving the HELLO packet, the node updates the corresponding information in its

73

Neighbor table. In order to avoid HELLO packet collisions, nodes send HELLO packets in
random time slots.
• Destination Acknowledgment DACK Packet
In order to avoid isolated nodes, the neighbors are authorized for a specific destination. To
set the authorization index in the neighbor table, when destination receives a message, it will
generate the DACK message. Instead of acknowledging each path, which may introduce
overhead for long packet headers, we authorize each neighbor via back-pressure. See Figure
5.2. Node 1 wants to send to node 4. Once node 4 receives a packet, node 4 authorizes
2 and 3, letting them know that they can reach node 4. Then, nodes 2 and 3 authorize 1,
letting node 1 know that it can reach 4 through 2, 3. The DACK is sent locally. Once a

Figure 5.2 Simple topology, node 4 is the destination, generating DACK messages.

node is authorized, no DACK message will be sent to it. We also authorize all paths with
a minimum number of hops to the destination to skip long paths. The DACK messages are
only sent in the initial set up. We consider a mesh network where the nodes are stationary
with long lasting energy. Therefore, the hop number would not be dynamic. Note that the
dynamics of channel availability and node occupancy are included in the Tid matrix. Hence,
contrary to DSR, DSDV, AODV, and other reactive and proactive protocols, we do not need
to repeat this process during network operation.

74

5.1.3.3 Transition Probabilities
As mentioned earlier, the next node is found based on the transition probability associated to it. In
order to find each entry of the transition matrix Ti,d , Pij (k) is calculated by both nodes i and j,
and the gd (j) is evaluated by node i based on the values of ∆j that are stored in its Neighbor table.
• Evaluation of Channel Reliability Probabilities
Each node i is aware of its surrounding and gathers the number of times that a channel k is
sensed idle (uij [k], the channel utilization parameter for each channel k). It constructs the
following vector for a pre-specified observation period:

Ri (t) = [uij [1] . . . uij [k]].

Therefore, the node has many realization of vector Ri (t) after t sensing periods. The
ArgMax and ArgMin probability distributions corresponding to the channel utilizations are
evaluated based on simplified simulation method presented in Algorithm 1. The variable
Tmax corresponds to the maximum number of observations. The variables Maxk and
Mink represent the number of times that channel k has the maximum and minimum utilization respectively.
• Evaluation of Forwarding Ability Probabilities
The ∆j metric of the neighboring node j informs the sender i of the distribution of primary
users around its neighbor j. Each node j calculates its ∆j according to equation (5.2) at each
time t that a Hello-reply packet is sent. Based on the ∆j obtained from all the neighbors,
p[ij;d] is calculated for each neighboring node j based on equation (5.1).

75

Algorithm 1 ArgMax and ArgMin probabilities calculation procedure
for t = 1 to Tmax do
in Ri (t)
if channel k has the maximum uij then
Maxk = Maxk + 1
end if
if channel k has the minimum uij then
Mink = Mink + 1
end if
end for
Pij (k) = Maxk /Tmax
Qij (k) = Mink /Tmax
5.1.3.4 PSARP Forwarding Mechanism
The procedure of forwarding packets from a source to a destination is presented here. In the initial
setup the neighbor and forwarding tables need to be constructed. Hence, to identify the authorized
neighbors, source nodes broadcast the data packets destined for a particular destination. By simple
flooding, the packets are delivered to the destination. The destination generates the DACK messages and the nodes that are authorized by receiving the DACK packet from the destination, will
authorize their neighbors as explained in the construction of control messages above. The DACK
messages are propagated back to the source so that the source node can update the forwarding
table. After this initial setup the forwarding mechanism is as follows:
• The source node i;
1. Checks the neighbor table to see if the destination d is in the neighbor table. If not,
broadcasts the message (waits for DACK messages to arrive).
2. Sends the HELLO packets and collects the HELLO packets from its neighbors. Hence,
the forwarding and neighbor table elements are updated.
3. Computes p[ij;d] (k) for each neighbor based on equation (5.3).
76

4. Sends number of packets with the same destination to neighbor j proportional to the
value of p[ij;d] (k). Therefore, the neighbor j that has the highest value of p[ij;d] (k)
associated to it, is more often the next hop.
• The intermediate node j upon receiving a message, checks the destination of the message
and
1. Checks the neighbor table to see if the destination d is in the neighbor table. If not,
broadcasts the message (waits for DACK messages to arrive).
2. Looks at the forwarding table, if there is a neighbor h for the destination d, gets the
transition probabilities p[jh;d] (k) from the table.
3. Forwards the number of packets destined to d to neighbor h proportional to the value
of p[jh;d] (k).
• The destination node d receives the packets and looks up the previous hop from the message
header and checks if it is included in the list of the authorized previous hops. If not, the
destination gathers a list of the unauthorized previous hops and insert them in the DACK
message. The DACK message is then broadcasted. Therefore, all the unauthorized previous
hops are authorized with one DACK message.

5.2 Additional Features
Here, we elaborate on some features embedded in PSARP that may be used in other stochastic
routing protocols.

77

5.2.1 Update Period
Note that the p[ij;d] (k) is highly dependent on how fast Pij (k) and gd (j) are updated. Currently,
the update period is around one second. During this period, we can have 100 samples of Ri matriˆ
ces to estimate Pij (k) and gd (j). From the law of the iterated algorithm proposed by Kolmogorov
ˆ
in [56], the upper and lower bound on the rate of convergence of the estimator of a distribution to
its true value are as follows:
√ ˆ
n Pn − P
≤ 1/2
lim sup √
n→∞
2 ln ln n
√
ˆ
lim inf 2n ln ln n Pn − P = π/2
n→∞
where n is the number of samples. From the above we can find the upper bound on the error of the
estimator based on n, for large n
√
ln ln n
ˆ
Pn − P < √
2n

(5.5)

We can see that by selecting n = 100, the error is about 0.15; and as n increases, the rate of
convergence will go exponentially to zero. By selecting n = 200, the error is 0.004. Therefore, by
having our update period around one second, or in other words by collecting 100 to 200 samples,
we have a very good estimate for the ArgMax and OOM distributions corresponding to Pij (k) and
gd (j) respectively.

5.2.2 Channel Selection Mechanism
The process of handshaking with neighbors in CRNs is challenging. A neighboring node that
chooses to change its channel due to the presence of a primary user should notify its neighbors of
78

its decision in a timely manner. Nodes choose their sending channel based on their local sensing
measurement. For instance, suppose node 1 is choosing channel 1 because the P12 (1) is maximum, while node 2 is selecting channel 2 because based on its sensing measurement P2j (2) is
maximum, where node j is a neighbor of node 2. Therefore node 1 should check which channel
node 2 is on before sending its packet on its decided channel. We have the following mechanism
in place to reduce packet loss for such a scenario. This mechanism will also reduce handshaking
overhead.
1) Each node chooses its receiving channel according to the values of the ArgMax probability distribution that locates the channel with the maximum idle frequency in the set of available channels.
The channel ID is sent to neighbors via HELLO packets and saved in the neighbor table.
2) When node i wants to send its packets, the next hop j is selected based on the transition probability p[ij;d] (k) in equation (5.3). Then, node i switches to the receiving channel of node j for
sending. If the receiving channel of node j is occupied on the side of node i, the next hop is reselected.
3) After sending, node i switches back to its own best receiving channel.
We can see that this mechanism forces the node to choose a link that is reliable at the both
sender and receiver side.

5.3 Evaluation
We study the effectiveness of PSARP in a dynamic environment through simulation. The current
version of NS2 computer simulator has the traditional MAC layer that is suitable for evaluating protocols designed for wireless networks. However, a cognitive radio network has its own enhanced
MAC layer. In order to test the routing layer, we designed the cognitive MAC layer. We started

79

by using the open source Cognitive Radio Cognitive Network simulator (CRCN) [57]. Although
a primary user is defined in CRCN, the MAC layer would not interrupt its transmission when
sensing primary users’ activities. Furthermore, the primary users’ traffic does not have priority
to secondary users’ traffic. Hence, the CRCN MAC layer is modified substantially to incorporate
these realistic scenarios.
We focus on a dynamic environment. The primary transmitters and receivers locations are
unknown and their transmission duration is unpredictable. Therefore, we compare the protocol
with the Local Coordination Based Routing and spectrum assignment (LCBR) [58], and OSDRP
[33]. The LCBR is an AODV based protocol that uses the summation of frequency switching and
back off delay at a node on top of the number of hops as its routing metric. The protocol also
identifies traversing flows at each node and calculates the active frequency bands taken, which are
used for multi-flow multi-frequency scheduling. As mentioned in the related work, many other
schemes that are designed for the dynamic environment adopt the same approach. The OSDRP
estimates the route lifetime based on the channel availability, as well as channel switching and
queuing delays, and adjusts the time of a flow according to the route lifetime. In addition, it
controls the transmission power and selects the nearest forwarding SUs to the SU destination node
to support QoS.
Further more, to show that the PWM measure truly has an advantage to show the distribution
of primaries around a node, we also compare the PSARP with the Cognitive Stochastic Routing
(CSR) protocol that we developed. CSR has the same stochastic dynamics as PSARP but uses
the backlogged queue capacities as an indication of next node’s reliability instead of PWM. The
results show that the stochastic approach we proposed is indeed successful in coping with the
uncertainties in dynamic environment in both protocols. However, the PSARP performs better
because the PWM measure enables it to recognize unstable routes more accurately.
80

We used different scenarios. In the first scenario a network with 30 nodes with 4 primary users
in a 1000X1000sqm area is considered. The secondary users are spread randomly throughout
the plane. The radio range is 250m and a channel is dedicated to the control channel with the
bandwidth of 250kb/sec. Three other channels are available, each with the bandwidth of 2Mb/sec.
The secondary nodes are able to switch to another channel when their transmission is interrupted or
the channel is occupied. This scenario is similar to the test configuration of the OSDRP protocol.

5.3.1 Primary Users Traffic Patterns
The distribution of the inter-arrival time of primary users is exponential with a mean of 3.0. As a
result, the primary user’s traffic follows a Semi-Markov process with an OFF/ON period following
the exponential distribution. This illustrates the model presented in the measurement study [54]
of the behavior of primary users. Note that under the uniform distribution, small, mid-size, and
large values assume the same frequencies. In other words, the frequencies that a primary user
who is on for a short time and a primary user who is using the channel for a longer period are the
same. Therefore, the uniform distribution is not a legitimate distribution for the sojourn time of a
primary user. The exponential distribution ideally explains the sojourn time distribution in which
the frequency of a primary users whose sojourn time exceeds a threshold τ decreases exponentially.
To evaluate PSARP under different primary user patterns, we changed both the distributions
and their corresponding mean of the idle period of primary users and kept all the parameters of
scenario 1 constant. The average throughput of the protocols is shown in Table 5.3. With the
exponential pattern, all four protocols gain higher throughput. This was expected, since the shape
of the distribution is skewed to the right. The average idle period will be higher than the uniform
distribution. PSARP and CSR maintain throughput even though the inter-arrival time of primary
users is changing from 3 to 30 seconds. When the inter-arrival time of primary users is 3 seconds,
81

Table 5.3 Average throughput (bytes/sec), (30-node network) with different primary users traffic
patterns
Average Idle Period (sec)
Exponential (mean 3 sec)
Exponential (mean 30 sec)
Uniform (mean 3 sec)
Uniform (mean 30 sec)

OSDRP
2.30E4
4.40E4
2.20E4
3.91E4

LCBR
CSR
PSARP
3.49E4 5.20E4 5.5E4
4.70E4 4.80E4 5.10E4
3.3E04 4.50E4 4.80E4
4,40E4 4.51E 4.83E4

the protocols should quickly adapt to the changes in the network dynamics. The PSARP adapts
to the primaries’ change of behavior. Its good performance is also an indication that the transition
probabilities are estimated in a timely manner to cope with the uncertainties. The OSDRP and
LCBR are not successful in capturing the randomness effect because of their deterministic framework and frequent calling of route recovery mechanisms. However, as the idle periods increase,
meaning the channels are less interrupted by the primary users, the throughput of both protocols
improves and approaches that of the CSR and PSRP. This shows that stochastic modeling works
better than deterministic modeling when the environment is dynamic.

5.3.2 Effect of Network Load
We were also interested in measuring the performance of protocols under different loading conditions. We change the sending rate from 81kb/sec to 1638kb/sec in the first scenario. We use the
exponential distribution with the mean of 3 for the inter-arrival time for the primary users. We
used 15 different random scenarios with the same configuration as the first scenario, the results
shown in Figure 5.3 and Figure 5.4 are the average of the throughput and end-to-end delay from
all the 15 random scenarios. There is a peak around a 409kb/sec rate in all four protocols. This
was expected since there are 8 CBR connections, meaning 8 sources are sending packets with
409Kb/sec. The channel’s bandwidth is 2Mb/sec. If the packets are distributed fairly across all
three channels, the network generates high throughput around this rate. However, if the availabil82

Throughput(kbytes/sec)

60

CSR
OSDRP
PSARP
LCBR

50
40
30
20
10

200

400
Rate(kb/sec)

700

800

Figure 5.3 Average throughput under different loading conditions, 30-nodes network.
ity of a channel is not determined accurately and packets are sent through an unreliable channel
or if the route is not updated on time, a bottleneck is generated. When the sending rate is higher
than 409kb/sec, the overall sending rate is more than the channel capacity. As a result, queues fill
up quickly. The power of PSARP and CSR are in their stochastic nature. Both protocols benefit
from the uncertainty of the network parameters. Hence, while OSDRP and LCBR try to find a
new route by unexpected arrival of a primary users, PSARP and CSR stochastic framework have
already predicted primary users arrival and chosen an appropriate node for forwarding the packets
to. PSARP and CSR learn and adapt to the primary users’ behavior more quickly. In OSDRP and
LCBR, when a link disappears, the corresponding node is removed from the routing table and the
new route discovery mechanism is initiated. Hence, the network operates with less nodes and does
not reach its optimal performance and generates less throughput. The LCBR performs better than
OSDRP due to its spectrum assignment mechanism that helps a node to forward packets with less
channel switching. We can see at higher rates that the network saturates and throughput drops. The

83

sharp decrease in CSR is due to the decrease in queue capacity variation. Hence CSR selection is
blind to the behavioral pattern of primary users located one hop away from the intermediate neighbors at high rates. PSARP on the other hand, uses the PWM measure and is able to identify the
correct path. In Figure 5.4, we represent the end-to-end delay comparison. Since the environment
is highly dynamic, OSDRP does deliver a substantial amount of packets compared to PSARP and
CSR, which adds to end-to-end delay. PSARP and CSR are using ArgMax probability distribution
in locating the channel with the maximum utilization. The strength of ArgMax probability distribution is in its accurate identification of the maximum random variable among a set of random
variables. Therefore, the channel that is chosen has a higher probability to stay stable and provide
stable transmission. Therefore, packets are rarely buffered in the network. This further enhances
the performance of the PSARP and CSR and minimizes its end to end delay. Since PSARP chooses
the more stable path, its end to end delay is better than CSR. At the rate of 409kb/sec, CSR and
PSARP delay are the lowest and the throughput is at its peak value.
1200

CSR
OSDRP
PSARP
LCBR

Average delay(msec)

1000

800

600

400

200

200

400
Rate(Kb/sec)

600

800

Figure 5.4 Average end-to-end delay under different loading conditions, 30-nodes network.
84

5.3.3 Large Network
In the second scenario, we use a network with 70 nodes. The sending rate is 409kb/sec. The number of primary users are 15, and they choose different channels from the three available channels.
There are 10 CBR connections and sources are distributed randomly in a 1500X1500 sqm field.
Since primary users’ inter-arrival time is random, learning their behavior and selecting the route
adaptively substantially improves the performance of the network. Table 5.4, shows the simulation
results for different distribution for the inter-arrival time of primary users. We can see that OSDRP
fails substantially to deliver packets due to the large instability of links and nodes. However, as the
idle period of the primaries increases and the network operational environment is closer to a semidynamic environment, OSDRP and LCBR throughput increases. On the other hand, PSARP is still
successful in maintaining throughput within a range and adapts to the uncertainties. Since PSARP
and CSR are stochastic in nature, their throughput degrades as the environment tends to be more
static. The reason is that a node in these protocols selects the next hop and the receiving channel
probabilistically. It does not stay on a specific best channel or rely on a specific best next hop.
Nevertheless, PSARP has a higher throughput than CSR because the PWM measure captures the
distribution of primaries more accurately than the queue average backlogged capacity. When the
environment is semi-dynamic, PSARP performs slightly better than OSDRP and LCBR because it
distributes the packets fairly among the nodes based on its selection probabilities.
Table 5.4 Average throughput (bytes/sec), (70-node network) with different primary users traffic
patterns
Average Idle Period
Exponential (mean 3 sec)
Exponential (mean 30 sec)
Uniform (mean 3 sec )
Uniform (mean 30 sec)

DSODV
1.35E4
3.91E4
1.20E4
3.70E4

LCBR
CSR
PSARP
2.01E4 3.8E4 3.95E4
4.1E4 3.84E 4.10E4
1.9E4 3.75E4 3.91E4
3.8E4 3.71E4 4.02E4

We also test the performance of PSARP under different loading conditions in the large network.
85

Figure 5.5 present the average throughput. Although the network size has increased, the PSARP
is still successful in maintaining the throughput. The queues have more variations in their capacities, when there are more nodes in the network. Therefore, CSR throughput has less variation and
degrades slower compared to the scenario 1. The OSDRP and LCBR are showing the same trends
as scenario 1. Maintaining throughput is very useful in applications that require a guarantee of
delivery within a certain user defined quality of service range. In the future, it will be interesting
to evaluate the lower and upper bound of the PSARP delivery range. Evaluation of the delivery
range is useful to control the applications’ sending rate in order to have a guaranteed delivery in
dynamic CRNs. Finally we present the comparison of the relative overhead frequency of the pro-

Throughput(kbyte/sec)

40

CSR
OSDRP
PSARP
LCBR

30

20

10

0

200

400
Rate(kb/sec)

600

800

Figure 5.5 Average throughput under different loading condition, 70-nodes network.

tocols over the first four hours of the large network operation in Figure 5.6. The relative overhead
frequency is the ratio of the number of overhead packets of each protocol over the total number of
overhead packets collected from all four protocols over that particular hour. The relative overhead
frequency of PSARP and CSR is larger in the first hour of operation due to the transmission of
DACK messages. Recall that the DACK messages are needed in the initial configuration of the
86

network to configure the neighbor and forwarding table. However, the relative overhead frequency
decreases substantially after the first hour because only the HELLO messages would provide the
information needed to the sender nodes to update their transition probabilities. On the other hand,
the relative frequency of LCBR and OSDRP is higher due to the frequent calling the route recovery
and spectrum assignment mechanism.

Figure 5.6 Relative frequency distribution of overhead in the first 4 hours of network operation.

5.4 Summary
In this chapter, we introduced the Primary Spread Aware Routing Protocol (PSARP), which is able
to adapt to the uncertainties of spectrum availability in cognitive radio networks. PSARP is based
on the Markovian property of a particular flow from source to destination and uses PWM as one of
its routing metrics. We demonstrated through simulation that PSARP is robust to the variation of
the primary users’ activity. Our results confirmed that using a stochastic protocol for a stochastic
environment is indeed more cost efficient and suitable than using deterministic protocols that map
channels’ availability to nodes’ availability. We believe this research is the beginning of a new line
of work on the development of stochastic routing protocols.

87

Chapter 6
Decision Tree Cognitive Routing
In the previous chapters we explained that in a dynamic CRN, the arrival rate of primary users is
high, causing small windows of spectrum usage opportunity. High variations in spectrum opportunities produce uncertainties in the problem of spectrum sharing and routing. In this chapter, we
focus on developing another routing scheme that works under such uncertainties.
It is indeed plausible to adopt elaborate techniques in statistics that address decision making
problems in an environment where uncertainty exists and the true state cannot be fully predicted.
This is exactly the situation of a cognitive radio sender. First, the variety of spectrums and their
corresponding channels provide multiple routes from the server to the client. Hence, the server has
multiple options with different routing consequences. Second, the chosen route might not stay stable during the transmission period. Therefore, the sender node is uncertain about the consequences
of its decision. In other words, the circumstances governing a node’s decision might change. The
theory of games and decision theory deal with decision making problems under uncertainty. In
game theory the players play against each other. Each player wishes to maximize its fortune. This
theory is intensively used in networks [14]. In decision theory a player plays against nature, meaning the player opponent does not try to increase its fortune, but exhibits stochastic performance
that is explained by probability laws. In decision theory the current state of the game is taken to be
uncertain and the decisions are made considering such uncertainties. In a highly dynamic environment, decision theory leads to less computational complexity than game theory since many types

88

of games have multiple equilibria under such variations. In this chapter, we bring the problem
of routing in a dynamic CRN to the framework of a decision making problem. Then, backward
induction terminal analysis is used to produce the decision strategy for a sender node.
To translate routing in CRNs into a decision problem, notice that in a CRN, a sender does
not have a full knowledge of the availability and stability of the neighboring nodes due to the
instability of available channels. The sender information is expressed by two probability distributions, called prior and posterior distributions. A prior distribution governs and explains the natural
status of the states (neighboring nodes) unknown to the decision maker (sender). A posterior distribution gives the sender understandings of unknown states after performing an experiment that
gives partial additional information on the status of the unknown states. A utility function also
indicates the decision maker gains or losses. Decision data is usually denoted by (e, z, a, s). The
decision maker runs experiment e, observes sample z, takes act a when the true state is indeed s.
An optimal act minimizes the expected loss or maximizes the expected gain; the latter equals to
maxe Ep(z|e) [maxa [Ep(s|z,e) U(e, z, a, s)]], where p(z|e) is the marginal sample distribution for
e, p(s|e, z) is the posterior distribution, and U(e, z, a, s) is the utility function. When the decision
maker does not perform an experiment, p(s) ∼ p(s|e◦ , z◦ ) stands for the prior distribution, while
e◦ , z◦ means no experiment, no observation.
One important challenge is to propose appropriate posterior distribution. This will give weight
to the sampling and reduces the cost due to uncertainty. It is understood in Bayesian statistics that
a good posterior ultimately and efficiently will estimate the unknown parameters. However, in
cognitive radio networks the classical statistical distributions cannot be used as default probability
laws governing the sender realization of the status of the channels connecting it to its neighboring
nodes. This is due to the non-stationary presence of primary users. The performance of the ArgMax
distribution [59] motivates one to build the empirical ArgMax distribution that acts as a sample
89

distribution. Then the posterior distribution is easily deduced. This nicely and effectively provides
the sample information to the sender, and is one of the contributions of this work.
The utility function also plays a crucial role in taking into consideration the side issues that are
imposed on a decision problem. In routing, it is vital to design a correct utility function, as it affects
the overall routing performance. We form a utility function, formula (8.1) in subsection 6.1.4,
which is equipped with different control knobs that adjust the gain by changing the significance of
parameters associated with spectrum stability, node reliability and bandwidth variability.
By adopting the decision problem components, we build a Decision Tree Cognitive Routing
scheme (DTCR) that aids a sender node in selecting the most appropriate next hop neighbor in
terms of stability and reliability. In summary the contribution of this chapter is as follows:
• We develop a decision tree cognitive routing scheme to model and analyze the problem of
routing in a dynamic CRN.
• We construct appropriate sample and posterior distributions to explain the status of channels
and nodes in supporting packet delivery.
• We introduce a utility function that captures the effects of spectrum availability, bandwidth
fluctuations and path quality. This utility function is expandable to include other important
decision making factors.
We compare the performance of our DTCR strategy with the optimal strategy. In the optimal
strategy, nodes have full knowledge of the future changes in the network parameters. In other
words, no routing strategy performs better than the optimal strategy. We also compare our method
with the local coordination based routing and spectrum assignment protocol [58] to measure the
deviation of our scheme and a routing protocol designed for a dynamic environment from the
optimum strategy. We like to emphasize here that the DTCR is specifically designed for dynamic
90

distributed cognitive radio networks, therefore choosing a semi dynamic routing protocol would
not provide us with a fair comparison. Our results show that our DTCR successfully treats the
occurrence of uncertainty and performs close to the optimal scenario. The DTCR uses the posterior
probability distribution to estimate the availability of a neighbor under uncertainty. The backward
induction scheme helps a node to choose a neighbor that is more likely to be the correct candidate;
it reduces the cost of choosing wrong candidates. Therefore it operates substantially better than
the local coordination based routing protocol; its performance is indeed near optimal at low and
moderate sending rates. However, at high sending rates, it still outperforms the local coordination
based routing.
The organization of this chapter is as follows. In Section 6.1, we present the decision theory
frame work and DTCR utility function. The terminal analysis backward induction and its use in
obtaining a correct decision in our strategy is discussed in Section 6.2. Section 6.3 presents the
details of implementation and simulation results.

6.1 System Model
We consider the mesh cognitive radio network in section 4.3 that is installed in an urban area.
Nodes have access to multiple spectrum bands and are able to choose any channel from those
spectrum bands. The diversity of the clients and the available spectrum bands result in a fairly
dynamic operating environment. The variety of spectrums and their corresponding channels provide multiple routes to the gateway. However, the chosen route might not stay stable during the
transmission period. Therefore, it cannot be guaranteed that the packets will reach the destination.
In such an environment, an end-to-end path does not provide a feasible solution. In our strategy a
node only decides among its neighbors and the quality of the remainder of the path to the gateway

91

is translated by the amount of weight allocated to the neighbors.
We assume the channel is shared with a Non-Contiguous Orthogonal Frequency Division Multiplexing (NC-OFDM) technique, which is sufficiently agile with respect to spectrum usage. By
deactivating (i.e, nulling) subcarriers that can potentially interfere with other users, this form of
OFDMA fills in the available spectral gaps within the channel’s transmission bandwidth partially
occupied by other users while not sacrificing its error robustness [47].
Similar to previous chapters, the fluctuation of the wireless channel is modeled by the Rayleigh
fading model.
A mesh cloud with a single gateway with four different spectrum bands is shown in Figures
(6.1a) and (6.1b). For simplicity, nodes located within the same number of hops from the gateway
are grouped into one layer. We refer to a node i in a layer l as i[l], i = 1, 2, · · · , M, where M
represents the total number of nodes in the network. The node i[l] chooses a node that is located
either in its own layer l or in the upper layer l − 1, and is inside its radio transmission range. Let
Ni denote the number of candidate nodes available for node i[l].
Table 6.1 summarizes the notations that are used in this article. For simplicity, we suppress the
notations l and t, and use i and ki,j whenever there is no ambiguity. Let us assume that the node
12[4] in Figure (6.1b) has packets to send to the gateway. Based on the spectrum coverage and node
12[4] radio range, this node has 3 intermediate neighbors: 8[3], 9[3] and 11[4]. Node 12[4] chooses
one of its neighbors. In terminology of decision theory [16], the set of possible states (choices)
available to the decision maker i is represented by Si = {s1 , s2 , ..., sN }. The node 12[4] is the
i
decision maker. The states unknown to the decision maker are the intermediate neighboring nodes,
s1 = 8[3], s2 = 9[3] and s3 = 11[4]. Therefore, S12 = {s1 , s2 , s3 }. There is also a set of actions
that the decision maker can take, represented by Ai = {a1 , ..., aN }; aν is the act of choosing a
i
state sν to visit. According to our example, we have three acts, a1 , a2 , a3 ; aν corresponds to
92

(a)

(b)
Figure 6.1 A simple mesh cloud within a city with its node diagram

93

choosing a neighbor sν , ν = 1, 2, 3.
Table 6.1 DTCR Notations
Si
Ai
Zi
e
e0
i[l]
k

i[l],j[l′ ]
Ni[l]
M
i zj

(t)

aj
(e, z, a, s)
ui (e, z, a, s)

Decision state space of node i.
Decision action space of node i.
Decision sample space of node i.
The experiment of assessing the duration of channel
availability between the sender and its neighbors.
No experiment.
Node i in layer l; l hop away from the gateway.
channel k between node i[l] and j[l′ ] at time t.
Number of neighbors available for node i[l].
Total number of nodes in the network.
Maximum duration of channels availability in
spectrums between node i and neighbor j.
The act of choosing node j.
Branch of the tree corresponding to the experiment e that
leads to sample z taking action a when the true state is s.
Utility function corresponding to the branch (e, z, a, s).

In the initial learning phase the sender gathers information from their neighbors and their surrounding spectral measurements to construct the decision tree (refer to Section 2.5). The decision
tree is a technical term in statistical theory [16] and should not be misinterpreted by a routing
tree or a graph theory tree. The decision tree demonstrates all possibilities in a decision making
problem. Figure 6.2 shows the decision tree associated to the decision making of the node 12[4].
The node 12[4], sits at the root of the tree and the states are at the ending branches of the tree. In
the beginning of any decision problem, the decision maker can perform an experiment to obtain
additional information in support of an act. Performing an experiment e is not obligatory and the
node may go for e0 , which means no experiment. The experiment here, is sensing the duration
of availability of channels connecting the node 12[4] to its neighbors. The possible outcome of
the experiment is 12 zj , the maximum duration of channels availability in spectrum bands between
94

node 12[4] and neighbor j. The outcome of e0 is z0 , corresponding to no observation.

Figure 6.2 Node 12 decision tree, with three states and three acts

6.1.1 Experiment e
Performing an experiment in decision theory means that the decision maker is willing to give
some cost in exchange for gaining partial information about the status of the unknown states. The
experiment e is collecting and reading a history of primary users’ activities on its surrounding
channels, then measuring the maximum duration of channels availability 12 zj in spectrum bands
95

between the node 12[4] and its neighbor j. Many previous studies in routing also rely on past
measurements on the activities of primary users to find the most stable path [33, 60].
We assume that there are Ki,j spectrum bands available between nodes i and j. Each spectrum
band has a number of channels. Node i[l] handshakes with its neighbor node j, j = 1, 2, · · · , Ni ,
and receives the signal-to-noise ratio gain (SNRgk

i,j

(t)) of a channel ki,j of that spectrum band,

which connects node i[l] to the node j[l − 1]. The SNRgk
ceiving antennas. The SNRgk

i,j

i,j

(t) is evaluated at the neighbors’ re-

(t) at time t is the signal-to-noise ratio, SNR, of a shared channel

over the SNR of the same channel when it is not shared by other users. Hence, the SNRgk

i,j

(t)

roughly indicates the occupancy influence on the channel. Based on [47], the occupied bandwidth
of the channel ki,j , denoted by Ok , is given by:
ij

Ok

where Bk

i,j

i,j

(t) = Bk

i,j

10

(−SNRgk

i,j

(t)/10)

,

(6.1)

is the bandwidth of the channel ki,j in Hz. Therefore the period of occupancy on the

channel ki,j approximately is:
Yk

i,j

(t) = 1/Ok

i,j

(t).

Let us denote the duration that the channel ki,j is sensed idle by the random variable Xk
the duration of channel availability is Tk

i,j

= Xk

i,j

− Yk

(6.2)

i,j

. Then

i,j

Finally, node i stores the maximum observed duration of channel availability in the spectrum
bands between itself and each of its neighboring nodes, into a vector Ri :
Ri =

i z1 i z2 · · · i zNi .

(6.3)

The variable i zj = maxk Tk shows the maximum observed duration of channel availability
i,j i,j
in the spectrums between node i and j. The variable i zj is a sample observation in favor of
96

neighbor j. Therefore, the node 12[4] in our simple mesh network, Figure (6.1b), constructs the
following record.
R12 =

12 z1 12 z2 12 z3 .

(6.4)

The record vector Ri is used to construct a sample and ultimately a posterior distribution for the
maximum spectral channel availability durations as follows.

6.1.2 A Sample Distribution
We quantify the stability of the spectrum bands and their corresponding channels by using the
ArgMax probability distribution introduced in Chapter . In [59], the authors show the accuracy
of the ArgMax distribution in targeting the most stable channel. From the perspective of node i,
i z = maxj i zj is the quantity of the sampling interest. The ArgMax probability distribution for a
neighbor node j ∗ is the probability that the node j ∗ contributes i zj ∗ . The sampling distribution
is the ArgMax distribution whenever the neighbor node that has the maximum available channel
duration is j. We denote the sampling distribution by pi (j ∗ |j), j ∗ , j = 1, 2 · · · , Ni .
The sampling distribution is estimated by the corresponding empirical distribution as follows: After the ArgMax distribution is estimated for a single realization of available channel
durations at each node (see algorithm (2) in Section 6.3) then the procedure will be repeated
for many realizations. The sampling ArgMax probabilities are classified according to nodes assuming maximum ArgMax probabilities. Then the sampling distribution is obtained by finding
the mean vector of each class. The result will be an Ni × Ni matrix, where the j-th column
stands for the estimated sampling distribution whenever j is the true (state) neighbor node. Let
us make a brief demonstration. Let Ni = 3 and the ArgMax probabilities for 6 realizations to
be:[.3 .5 .2], [.6 .1 .3], [.2 .7 .1], [.8 .1 .1], [.3 .6 .1], [.2 .3 .5]. The realization {[.6 .1 .3], [.8 .1 .1]}

97

are assigned to node 1, the realizations {[.3 .5 .2], [.2 .7 .1], [.3 .6 .1]} are assigned to node 2, and
[.2 .3 .5] is assigned to node 3. The sampling distribution will be the 3 × 3 matrix:


.7 .266 .2




pi (j ∗ |j) = .1 .6 .3 .




.2 .134 .5

(6.5)

6.1.3 The Posterior Distribution
Now that the sample probabilities pi (j ∗ |j) are constructed, the decision maker can compute the
probability that neighbor node j is the true node whenever his sample indicates that j ∗ is the
appropriate state. In other words, the node j is the true neighbor to send to but the outcome of the
experiment is in favor of j ∗ . This is indeed the posterior distribution on the neighboring nodes,
and is given by
pi (j|j ∗ ) =

pi (j ∗ |j)p(j)
,
∗
j pi (j |j)pi (j)

(6.6)

where pi (j) is the priori distribution on the neighboring nodes. In our design the prior distribution
of a neighbor node j is proportional to the total number of channels that connects it to the sender.
Note that the denominator in the above equation is the marginal sample distribution. This
probability distribution will be used in our backward induction procedure.

6.1.4 Utility Function
A utility function assigns a quantity (gain) to a decision datum (e,z,a,s). In a decision problem,
a utility function is either given or is formed to explain gains for correct decisions and losses for
wrong decisions, by taking into consideration the cost of sampling. Although a utility function can
take negative values, in practice, it is adjusted or transformed so that it assumes only nonnegative
98

values. Naturally for fix s, the utility function attains its maximum at decision data (e0 , as , s),
where e0 is no experiment, and as is the trivial immediate act. The decision maker chooses as if
he knows the true state is s. Sampling cost as well as incorrect or inappropriate acts will reduce
the gain.
In our routing modeling, we go for zero-one scenario, in the sense that wrong selection of the
node is a total loss, i.e. zero utility. Thus we let

µ(a, j) =

Consequently




 1 if a = j, when j is the true state,



 0 if a = j, when j is the true state.

ui (e0 , a, j) = ηj µ(a, j),

(6.7)

where ηj is a constant that reflects the transferring quality of node j specified by the remaining
∗
(−γi zj )
queue capacity of node j. We let the maximum gain be reduced by the factor 1 − e
due
∗
to the sampling cost, where zj is a sample and γi is the controlling factor to quantify the amount
of channel availability variation from the sender perspective. Depending on the sensitivity of the
application on the bandwidth fluctuation, γ is selected. For example, when γ is around 0.5, a small
difference in the duration of channel availability would provide a significantly higher gain and the
node is encouraged to choose the node with highest duration of availability. Although sampling
is expected to some extent guide one to the true state, it may not always point to the optimal act.
Such a deviation will reduce the gain. The factor V (a, a∗ ) is for the corresponding reduction. We
j
assume that
−β[Ae (a)−Ae (a∗ )]2
j ,
V (a, a∗ ) = e
j

99

(6.8)

where Ae (a) is the gain associated with choosing the right act a and Ae (a∗ ) is the gain of choosing
j
the act a∗ following observing the sample j ∗ . In our work Ae (a) will be the maximum duration
j
of channel availability. The parameter β is the knob that controls the significance of the amount of
gain associated with relying on the spectrum measurement. If β is small, a node may be chosen
that does not necessarily have the highest duration of channel availability. In other words, β acts
as an error tolerance factor in channel availability measurement. By considering the fact presented
above, our utility function assumes the following formulation.
∗
(−γi zj )
ui (e, j ∗ , a, j) = ηj [1 − e
][v(a, a∗ )µ(a, j)].
j

(6.9)

As mentioned previously, the environmental dynamics of the cognitive radio network might
change and the node might choose a neighbor that was not the most appropriate node in routing.
The indicator function µ is chosen to model the gain/loss for such a scenario. Note that based on µ,
we assume total loss when a wrong node is selected to transfer packets. A wrong node would not
necessarily give a total loss but may be able to transfer some packets based on its queue capacity.
An interesting future direction is to model µ according to nodes’ queue length.

6.2 Making a decision using Backward Induction
After the construction of an appropriate decision tree for our routing problem, the optimum strategy
(course of action) is specified by a branch that leads to the maximum average utility. It is specified
by the backward induction terminal analysis.
Backward induction is to work back from the ending branches of the decision tree to the initial
starting point (root). The decision data (e, j ∗ , a, j) are eliminated one at the time. Random data j

100

Figure 6.3 Node 12 decision tree with some utilities
and j ∗ are eliminated through expectations; deterministic and optional data a and e are eliminated
using maximizing process.
The first step is to find the expected utility with respect to the state distributions.

Eui (e, j ∗ , a) =
Eui (e0 , z0 , a) =

∗
∗
j ui (e, j , a, j)p(j|e, j ),

(6.10)

j ui (e, z0 , a, j)p(j|e0 , z0 ),

(6.11)

101

where the state distribution p(j|e0 , z0 ) for the experiment (e0 , z0 ) is the prior distribution, and
p(j|e, j ∗ ) is the posterior distribution. The second step is to identify the optimal act a∗ for the
j
experiment e and outcome j ∗ , defined by
Eui (e, j ∗ , ao ) = max Eui (e, j ∗ , a).
j
a

(6.12)

The maximum expected utility is Eui (e, j ∗ , ao ). We let I(e0 ) = maxa Eui (e0 , z0 , a), I(e0 ) be
j
the maximum expected gain under no experiment.
The third step is to use sample information by taking expectation of the maximum expected
utility for the optimal ao with respect to the marginal sample distribution:
j
I(e) := E Eui (e, j ∗ , a0 ) =
j
Recall that pi (j ∗ ) =

z

Eui (e, j ∗ , a0 ) pi (j ∗ ).
j

(6.13)

∗
j pi (j |j)pi (j) is the marginal sample distribution. The I(e) is the maxi-

mum expected gain under experiment e.
Finally I = max{I(e0 ), I(e)} specifies the total utility index. The branch that corresponds to
the index I and optimal act ao specifies the right neighbor.
j
The backward induction procedure for our simple mesh network is depicted in Figure 6.4. After
following the above steps, the course of action in this example is through experiment e because
I(e) > I(e0 ). Then for j ∗ = 1 choose j = 3 since Es U(e, 1, a3 ) is maximum among other
branches extended from observing j ∗ = 1, and for j ∗ = 2, choose j = 1, and for j ∗ = 3, choose
j = 3 for the same reasoning as above. As we see in this simple example, collecting the samples
and evaluating the sample and posterior distribution is needed in the initial learning phase of the
DTCR strategy. After this initial learning, the decision maker only decides its next hop by a saved

102

Figure 6.4 Node 12 decision tree
strategy developed in the learning phase. This is the reason that the DTCR is adaptable to the
changes in a highly dynamic environment. After the learning phase, it understands the dynamics
by relying on having only one sample observation which is available from any MAC protocol and
chooses the next hop according to the saved procedure.

103

6.3 Simulation
In this section we present the details of implementing our decision tree cognitive routing scheme
and the results of simulation. In our simulation setup we are able to explore larger size networks
with a variable range of parameters more effectively than what is possible in existing testbeds.
The simulation parameters and the traffic patterns are chosen based on measurement analysis done
on real networks. We have the capability to derive actual workload patterns from a network that
operates in a highly dynamic environment.

6.3.1 Implementation Details
Our topology is similar to Figure 6.1b. There is a single gateway and nodes are arranged into
layers based on their number of hops from the gateway node. The number of accessible nodes Ni
varies depending on the radio signal strength. A random value is assigned for the radial distance
of node i from node j. If node j is within the radio transmission range of node i, it is considered
accessible by node i. In our simulation model we have K = 5 spectrum bands. The range of their
corresponding bandwidth changes from 6Mb/sec (which could correspond to the FM radio band)
to 144Mb/sec (similar to a TV channel). Note that a spectrum band depending on its type could
have a different number of channels. The bandwidth of each spectrum is divided equally among
its channels. For example, the 144Mb/sec spectrum band has 6 channels, each with a bandwidth
of 24 Mb/sec (similar to sub CATV band).
To demonstrate the effect of primary users on channels, we generate random numbers from an
exponential distribution with parameter λ. As λ gets larger, the amount of time that the PU is not
using a channel is less. Once the channel is available, it is shared among other users. Based on
a measurement study [50], the occupied portion of the channel is modeled by a lognormal distri-

104

bution with mean µ and standard deviation σ. The larger the value of µ, the more occupied the
channel would be. The duration of channel availability i zj , can be found by using a truncated distribution when the occupied portion of the channel is available, refer to Section 4.2. The record Ri
is constructed by collecting the maximum duration of channel availabilities from each spectrum
band for each neighboring node and discarding the rest. Using Ri record, the ArgMax probability pi (i zj ) is evaluated empirically using algorithm 2. The variable Tmax corresponds to the
length of the sensing period. The ArgMax probability distribution is updated and evaluated every
τ seconds. The variable τ decreases if the decision procedure indicates no testing is necessary
according to the dynamics of the network. In other words, no new records need to be collected.
The sensing period of channels could also be controlled according to network dynamics in future
designs. As explained in the previous section, in the initial phase of network operation (learning
Algorithm 2 ArgMax probability calculation procedure
for t = 1 to Tmax do
in Ri (t)
if i zj is maximum then
Maxj = Maxj + 1
end if
end for
pi (i zj ) = Maxj (t)/t

phase), a sender constructs a decision tree on the set of its neighboring node. It evaluates the best
decision strategy based on backward induction to consider future uncertainties. After the initial
phase (operation phase), a node only looks at its Ri record at time t and makes its decision, based
on its current sensing observation. Algorithm 3 summarizes the steps of the decision tree cognitive
routing procedure in each phase.
In the above algorithm, the end of the operation period depends on the node’s mobility, traffic
arrival rate and other network design factors. For a fairly static network, where nodes disappear

105

Algorithm 3 Decision tree cognitive routing procedure
Require: pi (j), Ri , pi (i zj ) records.
Initial learning phase:
Evaluate pi (j ∗ |j) using the ArgMax probability distributions pi (i zj ).
Using multiple Ri records, evaluate utilities based on equation (8.1).
Evaluate pi (j|j ∗ ) and pi (j ∗ ) using pi (j ∗ |j) and pi (j), equation (6.6).
Use the backward induction steps in Section 6.2 and get the decision strategy.
if I(e0 ) > I(e1 ) (taking e0 branch) then
Decrease the nodes sensing period.
else
Save the decision strategy.
end if
Operation phase:
At time t look at the Ri
if i zj is maximum then
Look at the saved decision strategy, get the case when i zj is observed and choose the next
node accordingly.
end if
Switch to initial phase when operation period is ended.
due to their expected battery life, the operation period could be weeks. Note that any uncertainty
due to different environmental parameters is already counted in the initial learning phase. The
operation period can also be controlled adaptively. For instance, when the gateway throughput is
falling below a certain predefined threshold, a flag is sent to the nodes to enter the initial phase and
change their decision strategy.
In our simulation, our nodes update their decision strategy every 4 hours and the simulation ran
for 12 hours. Every 300 seconds the radial distance of nodes changes, meaning the set of neighbors
changes for a particular sender node. Based on study [50], we use an exponential distribution with
mean λ = 1/3 to model the arrival rate of primary users. We consider a lognormal distribution
with means 0.8, 0.2, 0.5 and 0.5 variance to model heavy, moderate and light users on channels,
respectively.
We compare our decision framework with an optimal strategy. In the optimal strategy, nodes
have complete knowledge of the future changes in the network states. In other words, this is
106

the best performance that the network could have with its queue length, number of channels and
packet arrival rate. We are also interested in making a comparison between the deviation of DTCR
and other protocols from the optimum strategy. As explained in the related work, many routing
protocols designed for dynamic CRNs use the framework of ad-hoc networks. We used the local
coordination based routing and spectrum assignment protocol [58], which is an AODV based protocol that uses the summation of frequency switching and back off delay at a node on top of the
number of hops as its routing metric. The protocol also identifies traversing flows at each node
and calculates the active frequency bands taken, which are used for multi-flow multi-frequency
scheduling. As mentioned in the related work, many other schemes that are designed for the
dynamic environment adopt the same approach. The performance of this protocol is shown by
using the abbreviation of Secondary Option Protocol (SOP) in our simulation results. Since we are
considering a dynamic environment, DTCR is not compared to other protocols such as CRP [60]
designed for a semi dynamic environment.

6.3.2 Effect of Network Load
To test the decision strategy under various network loads, we used 78 nodes in our network, distributed randomly in a 1500 × 1500 sqm field. There are 12 sources and a single gateway. The
sending rate of the sources is changed from 1Mb/sec to 7Mb/sec. The MTU size is 2000 bytes.
The average throughput and delay with their 95% confidence intervals are shown in Figure 6.5
and Figure 6.6. The environment is highly dynamic with the average OFF period of primary users
ν = 3sec.
The DTCR procedure is more successful in capturing the uncertainties than the Secondary Option Protocol (SOP). In SOP the routing tables are not updated frequently enough and the repetition
of calling the route request mechanism results in transmission delay and packet loss. DTCR op107

1

Average Throughput

DTCR

SOP

Optimum

0.8

0.4

0
1

2

3

4
Rate(Mb/sec)

5

6

7

Figure 6.5 Average throughput with 95% confidence interval for different sending rate, size = 78
nodes

Average delay (msec)

800

400

0
1

DTCR
2

3

4
Rate(Mb/sec)

SOP
5

optimum
6

7

Figure 6.6 Average throughput with 95% confidence interval for different sending rate, size = 78
nodes
erates near optimum when the rate is below 3Mb/sec. After this rate, the DTCR performance is
lower because as the rate increases, the variation in channel opportunities is larger and nodes have

108

to adjust their decision making more quickly. In most of the applications, the sending rate does not
exceed the 3Mb/sec rate. In addition, there are many controlling parameters such as 0 ≤ β, γ ≤ 1,
the length of the operation period and the sensing period in DTCR that can be adjusted to achieve
the desired performance. One interesting future direction is to find the optimum value of these
parameters by solving a classical optimization problem at each layer with the objective of maximizing the gain Ii (β, γ), see Section 6.2. In the last subsection, we elaborate on the effect of
control knobs in the utility function of DTCR and its decision making. We experimentally tried
different values for β, γ in their corresponding ranges to achieve better performance at the gateway.

6.3.3 Effect of Network Size
We also changed the network size from 30 to 78 nodes, and kept the sending rate constant at
2Mb/sec, and ν = 3sec. Figure 6.7 and Figure 6.8 show the average throughput and end-to-end
delay with 95% confidence intervals. Since DTCR is decentralized, network size does not affect
the performance significantly. The performance of SOP drops significantly since the end-to-end
path is highly unstable.

6.3.4 Primary Users Traffic Patterns
We changed the primary users arrival rate λ and decreased it to create a semi-dynamic environment.
In table 6.2, variable ν = 1/λ indicates the mean OFF time of the primary users. The network has
78 nodes and the sending rate is 2Mb/sec. We see that the SOP protocol performance improves
significantly. DTCR is still able to adapt to the changes in the environment. The performance is
closer to the optimum scenario. We would like to emphasize here that our design is tailored towards
a dynamic environment but we also foresee the DTCR working satisfactorily in a semi-dynamic

109

Average Throughput

1

0.6

0.2
0

DTCR
30

Optimum
40

SOP

50
Number of nodes

60

70

Average end−to−end delay (msec)

Figure 6.7 Average throughput with 95% confidence interval for different network size, sending
rate is 2Mb/sec

DTCR

SOP

Optimum

400

0

30

40

50
Number of nodes

60

70

Figure 6.8 95% confidence interval of average end-to-end delay for different network size,
sending rate is 2Mb/sec
environment.

110

6.3.5 Adjusting the DTCR Parameters
In the utility function described in Section 6.1.4, three control parameters β, γ, η exist that quantify
the importance of local spectral measurement, its variation and path quality. In this section we show
how these variables change the utility function and change the selection of neighboring nodes. The
Table 6.2 Average throughput for different average OFF periods of primary users
ν (sec)
3
30
60

SOP DTCR Optimum
0.211 0.921
0.931
0.816 0.925
0.931
0.919 0.928
0.931

variable 0 ≤ β ≤ 1 is the knob that controls the significance of the amount of gain associated with
relying on the spectrum measurement. Consider a node i with 5 neighbors. After sensing, it has
the following maximum duration of channel availability of a spectrum for each of its neighbors

Ri =

0.33d∗ 0.5d∗ 0.66d∗ .88d∗ d∗ ,

where neighbor 5 with d∗ has the maximum duration of channel availability to node i. In order
to see the effect of β in the utility function, we kept all the parameters in equation 8.1 constant.
First, we let η = 1 for all the neighbors, meaning we assumed the remainder of the path to the
gateway is good for all of them. The variable γ = 0.05. As shown in the Figure 6.9, the utility
corresponding to the fifth neighboring node is equal to one, and the utility of other neighbors
decreases exponentially as β increases. The smaller the value of β, the less is the difference
between the neighbors’ utility. The parameter β could be chosen so that a node that does not
necessarily have the maximum duration of channel availability is selected. As explained in the
previous section, for some applications it is important to avoid paths that have high fluctuation of
bandwidth variation. The parameter 0 ≤ γ ≤ 1 controls the sensitivity of a node to this variation.
111

1
.88d*

Utility

0.8
0.6
0.4 .66d*
0.2

.50d*
.33d*

0
0

0.2

0.4

β

0.6

0.8

1

Figure 6.9 Utility on the states of 5 neighboring nodes, with different β values.
According to Figure 6.10, when γ increases, the nodes’ utility assumes a larger distance from each
other. After some point, there is no increase in utility. By choosing γ = 0.2, a designer can avoid
choosing nodes with duration of channel availability below 0.88 of maximum channel availability
duration. Hence, a node is sensitive to channel variations. The parameter ηj is very important in
5
.88d*

d*

4

utility

.66d*
3
.50d*
2
.33d*
1
0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

c1

Figure 6.10 Utility on the states of 5 neighboring nodes, with different γ values.
choosing a stable end to end path. This variable could be evaluated according to any metric that the
112

designers feel suitable and affordable such as delay. We used relative queue remaining capacities
of a neighbor node j. Therefore 0 ≤ η ≤ 1. We assigned the following values for each of the
neighbors, η1 = 1, η2 = 0.8, η3 = 0.6, η4 = 0.4, η5 = 0.2. Therefore, the first neighboring node
is on a very good path to the gateway. However, note that from Ri record, this neighbor channel’s
stability to node i is very low. On the other hand, the fifth neighbor that has a high channel stability
to node i, is not on a stable path to the gateway. We choose these controversial values for parameter
η on purpose to show how all of the above parameters come into play to aid node i to choose a
good neighbor. We set β = 0.05, γ = 0.2. The utilities are shown in Figure 6.11. In this scenario,
the fourth neighboring node has the highest utility. This neighbor is connected to node i and the
gateway on a fairly stable path.

Cs=0.6
Cs=0.4

Cs=0.8

1

utility

0.8
Cs=1

Cs=0.2

0.6
0.4
0.2
0

1

2

3
4
Neighbor node Index

5

Figure 6.11 Utility on the states of 5 neighboring nodes, with different η values.

6.4 Summary
We presented a decision theory framework to analyze the problem of routing in a cognitive radio
network operating in a highly dynamic environment. We modeled a node’s decision among its
candidate neighbors into a decision tree, and utilized a novel utility function to include the effect of
113

spectrum availability, bandwidth fluctuation and path uncertainties in a node decision making. The
best candidate is chosen by analyzing the tree with backward induction and eliminating the choices
that might decrease the node gain when selected with uncertainty. The Decision Tree Cognitive
Routing scheme (DTCR) leads the node to choose the best candidate under high environmental
variations.

114

Chapter 7
Decision Tree Modeling for Video Routing
in Cognitive Radio Mesh Networks
In this chapter, we translate video routing in a dynamic cognitive radio network into a decision theory problem. Then terminal analysis backward induction that was used in previous chapter is used
again to produce our routing scheme that improves the peak signal-to-noise ratio of the received
video. In the proposed Video aware Cognitive Routing strategy (VCR), the sample and posterior
distributions of the decision theory based scheme of previous chapter are tailored to explain the
status of channels and nodes in supporting video frame quality of service, more specifically, the
priority of I B and P video frames.
Similar to DTCR, in VCR the two probability laws, prior and posterior distributions are used.
A prior distribution governs and explains the natural status of the states (neighboring nodes) unknown to the decision maker (sender). A posterior distribution gives the sender understandings
of unknown states after performing an experiment that gives partial additional information on the
status of unknown states. The nodes use their sensing data to predict future state of channels and
reliability of the candidate nodes. New coding schemes such as H.264 [61] slices the video into I, P
and B frames, with high to low priority of reconstructing the video at the receiver. The VCR selection takes into account the video frames priorities and their required bandwidth. More specifically,
the VCR is a per-hop routing scheme, in which the next node decision process is modeled into a

115

decision tree. Each branch of the tree models a different scenario that might be shaped by spectrum availability uncertainties in dynamic cognitive radio networks. Nodes sense the surrounding
channels and construct a record of channel availability durations. The bandwidth requirement of
different frames in a group of video pictures (GOP) is taken into considerations, and nodes classify
their channels records accordingly. Then, sampling probabilities are constructed using the ArgMax
probability distribution introduced in Chapter that points to the node with the maximum duration
of channel availability in its records. Using the sampling probabilities, we construct posterior
probability distributions. The posterior distributions provide partial information on the uncertainty
in the existence of channels that can support the required video quality of service. Using this approach, nodes undertake spectrum and node selection simultaneously. The utility function similar
to previous chapter is used to adjust the gain by changing the significance of parameters associated
with spectrum stability, node reliability and bandwidth variability. We use backward induction
to analyze the decision tree and find a decision road map for the nodes to select their next hop
neighbor is response to changes in the environment
In summary the contribution of this chapter is as follows:
• Using a decision theory framework, we develop a video aware cognitive routing scheme
(VCR) to model and analyze the problem of downlink routing of video packets in a dynamic
CRN.
• We construct appropriate sample and posterior distributions to explain the status of channels
and nodes in supporting video frames quality of service.
We compare the performance of VCR with OSDRP [33] in a cognitive radio mesh network that
operates in a city downtown. A video file is transferred from a server to a client. Our simulation
results show that VCR is more successful in maintaining an acceptable Peak Signal-to-Noise Ratio
116

(PSNR) than OSDRP as the arrival rate of primary users increases. In addition the reconstructed
video is played back successfully at the receiver when VCR is used. However, due to loss of frames
in OSDRP, the decoder is not able to reconstruct the entire video at the receiver.
The organization of this chapter is as follows. In Section 7.1, we show how DTCR decision
theory framework is modified to generate the VCR scheme.In Sections 7.2 we elaborate on the
VCR complexity. Section 7.3 presents the details of implementation and simulation results.

7.1 Decision Theory Framework of VCR
We consider a cognitive radio client in a multi-hop mesh topology network that is downloading
high definition video from a server. The network is located in a city downtown, where activities of
primary users is highly dynamic and unpredictable. All the nodes in the network have a cognitive
radio transceiver. They also have an extra interface dedicated to a control channel. The control
channel is only used for transferring control messages between the nodes. The video frames are
transported hop by hop from the server to the client. Figure 7.1 shows a simple topology. In this
section, this topology is used to explain the steps of our per-hop routing strategy. However, we
show in Section 7.3 that the scheme is indeed applicable to larger size ad-hoc mesh networks. For
simplicity, nodes that are located within the same number of hops from the server are grouped
into one layer. We refer to a node i in a layer l as i[l], i = 1, 2, · · · , M, where M is random
and represents the total number of nodes in the network. A node in a layer l can choose any
node in the lower layer l + 1 other than the nodes in its own layer who are authorized to send
packets to the receiver. The client broadcasts its layer index in a video request packet, when a
neighbor receives the request, it authorizes itself for that particular destination and informs its
neighbors of its authorization by broadcasting the received video packet. Therefore via a back

117

Figure 7.1 A simple downlink mesh network topology within a city with its node diagram

118

pressure approach, all the nodes are notified of their authorized neighbors. In addition, when a
node handshakes with its neighbor it receives the neighbor’s layer index. The layer index helps to
avoid count to infinity problem.
Due to the nature of a cognitive radio network, available channels at each node have diversity
in their bandwidth and duration of availability. Channels are available from a spectrum band
when the primary user of that band is absent. Nodes access and share the available channels with
OFDMA/NC medium access technique.
We view the selection of the best candidate among the neighbors of a sender node as a decision
problem. Considering the uncertainties involved due to the arrival of primary users in cognitive
radio networks, it is desirable to choose a neighbor that is most reliable in receiving video packets
and forwarding them to the next node; and ultimately to the destination. The notations, we use in
this chapter are that used in in Table 6.1. Lets assume that node 12[4] in Figure 7.1 is the client,
and is downloading a video from the server (0[0]). Based on the spectrum coverage, and radio
range of the gateway node, this node has 3 intermediate neighbors: 1[1], 2[1] and 3[1]. Node 0[0]
chooses one of its neighbors. Due to the nodes mobility and variation in transmission range, each
neighbor has a random number of neighbors Ni . In terminology of decision theory [16], the set of
possible states (choices) available to the decision maker is represented by S = {s1 , s2 , ..., }. The
node 0[0] is the decision maker. The states unknown to the decision maker are the intermediate
neighboring nodes, s1 = 1[1], s2 = 2[1] and s3 = 3[1]. Therefore, S = {s1 , s2 , s3 }. There is
also a set of actions that the decision maker can take, represented by A = {a1 , ..., aN }; aν is the
i
act of choosing a state sν to visit. According to our example, we have three acts, a1 , a2 , a3 ; aν
corresponds to choosing a neighbor sν ν = 1, 2, 3.

119

7.1.1 Initial Learning Phase
In this phase the sender gathers information from their neighbors and their surrounding spectral
measurements to construct the decision tree as explained in Section 2.5. The node 0[0], sits at
the root of the tree and the states are at the ending branches of the tree. Now similar to the
uplink routing explained in previous chapter, the decision maker can perform an experiment to
obtain additional information in support of an act. Performing an experiment e is not obligatory
and the node may go for e0 which means no experiment. Performing an experiment in decision
theory means that the decision maker is willing to give some cost in exchange of gaining partial
information about the status of the unknown states. The experiment e is collecting and reading
a history of primary users’ activities on its surrounding channels, then measuring the maximum
duration of channels availability 0 zj in spectrum bands between node 0[0] and neighbor j. Many
previous studies in routing also rely on past measurements on the activities of primary users to find
the most stable path [33, 60].

7.1.1.1 Local Spectral Bandwidth Observations
We assume that there are Ki,j spectrum bands available between nodes i and j. Each spectrum band c has Kc number of channels. Node i[l] handshakes with its neighbor node j, j =
1, 2, · · · , Ni , and receives the signal-to-noise ratio gain (SNRg ) of every channel ki,j in spectrum band c, ki,j = 1, · · · , Kc , that connects node i[l] to the node j[l + 1]. It then evaluates the
period of occupancy of each channel occupied bandwidth of the channel ki,j , denoted by Yk ,
i,j
based on equation 6.2. Let us denote the duration that the primary users do not use the channel
ki,j by Xk . Then the duration of channel availability is Tk
= Xk − Yk The video
i,j
i,j
i,j
i,j
is compressed using H.264 codec standard [61]. After compression, a group of pictures (GOP)

120

consists of three types of frames: Intra-coded picture or I frame, Predictive picture or P frame and
Bi-predictive picture or B frame. An I frame is the most important frame. It has the main static
picture of a GOP, meaning if an I frame is lost, the scene of the video corresponding to that particular GOP will not be constructed at the receiver. P frames are also important to provide reasonable
video quality. On the other hand, B frames could be predicted if I and P frames are available. This
type of video compression will provide a tolerance on packet loss as long as they are mostly B
frames. Therefore, the I frames are larger in size and receive high priority. In order to make our
decision scheme sensitive to the priority of I and P frames, we classify the Tk
of Ik

i,j

i,j

into two groups

and Pki,j , as follows:

Ik

i,j

Pk

i,j

= Tk if Tk > TI , for ki,j = {1, · · · , Kc }
i,j
i,j
= Tk if TI > Tk > TP , for ki,j = {1, · · · , Kc },
i,j
i,j

where TI and TP are the time durations required for sending I and P frames across the channel
ki,j respectively. Ii,j = {ki,j ; Tk > TI } and Pi,j = {ki,j ; TI > Tk > TP }.
i,j
i,j
Finally, node i stores the maximum observed duration of channel availability in the spectrum
bands between itself and each of its neighboring node, into a vector Ri :

Ri =

.
i z1 i z2 · · · i zNi

The variable i zj = maxk ∈I Ik + maxk ∈P Pk
shows the maximum observed
i,j i,j i,j
i,j i,j i,j
duration of channel availability in the spectrums between node i and j. The set of possible samples
is represented by Z = {i z1 ,i z2 , ...}. The variable i zj is a sample observation in favor of node j.

121

Therefore, node 0[0] in our simple mesh network, Figure 7.1, constructs the following record.

R0 =

0 z1 0 z2 0 z3

.

The record vector Ri is used to construct the sample and the posterior distribution for the
maximum spectral channel availability durations similar to the previous chapter. Refer to section
6.1.2 and section 6.6 to see how these distributions are constructed from Ri records.
Similar to previous chapter, We define the following utility function. for the experiment e
∗
∗ , a, j) = c [1 − e(−γi zj ) ][v(a, a∗ )µ(a, j)].
ui (e, j
j
j

(7.1)

ui (e0 , a, j) = cj µ(a, j),

(7.2)

For no experiment e0

where cj is a constant that reflects the transferring quality of node j specified by the remaining
queue capacity of nodej. The γ is the controlling factor to quantify the amount of channel availability variation. The function V (a, a∗ ) reflects the spectrum band quality, defined in formula
j
7.3.
µ(a, j) =





 1 if a = j, when j is the true state,


 0 if a = j, when j is the true state.


Figure 7.2 shows some utilities on the node 0 decision tree.

When observing the channels in a spectrum and measuring the maximum duration of their
availability without any interruption from primary users, it might be more beneficial to a node to
use a channel from a specific spectrum that has less availability duration but is connected to a node
that might be on a better path. The gain associated to choosing a node based on its spectrum band
122

Figure 7.2 Node 0 decision tree with some utilities
quality is quantified with the following formula.
−b [Ae (a)−Ae (a∗ )]2
j
V (a, a∗ ) = b1 e 2
j

(7.3)

where Ae (a) is the gain associated with choosing the right act a and Ae (a∗ ) is the gain of choosing
j
123

the act a∗ following the sample observation j ∗ . For example, if the measurement of the maximum
j
duration of channel availability of spectrums are as follows,

R1 =

12 8 18 ,

then the Ae (a) = 18, Ae (a1 ) = 12 , Ae (a2 ) = 8 , Ae (a3 ) = 18. Therefore, sample 0 z3 ,
leading to choose node 3[1] in our scenario, provides the maximum gain. The parameters b1 and
b2 are the knobs that control the significance of the amount of gain associated with relying on the
spectrum measurement. If b2 is small, a node may be chosen that does not necessary have the
highest duration of spectrum availability. In other words b1 and b2 provide the network designers
with an error tolerance factor in spectral measurement.
Some applications in CR networks suffer from high fluctuation of bandwidth availability due to
∗
fluctuation in the channels’ availability. The variable i , zj is a measure of the maximum duration
∗
of channels availability between i and j obtained from the experiment. When i , zj is high the utility
is large. The variable γ is the controlling factor to quantify the amount of variation. Depending on
the sensitivity of the application on the bandwidth fluctuation, γ is selected. For example, when γ is
around 0.5, a small difference in the duration of channel availability would provide a significantly
higher gain and the node is encouraged to choose the node with highest duration of availability.
As mentioned previously, the environmental dynamics of the cognitive radio network might
change and the node might choose a neighbor that was not the most appropriate node in routing.
The indicator function µ is chosen to model the gain/loss for such scenario. Note that based on µ,
we assume total loss when a wrong node is selected to transfer packets. A wrong node would not
necessarily give a total loss but may be able to transfer some packets based on its queue capacity.
An interesting future direction is to model µ according to nodes queue length.

124

It is essential that the node considers the quality of the remainder of the path to the gateway
when choosing its intermediate neighbor. The variable cs reflects this metric. Some researchers
use the average backlogged queue length [14] to quantify the quality of the path. For our utility
function we use the remaining queue capacity of node j to quantify the value of cs .
After the construction of an appropriate decision tree for our routing problem, the optimum
strategy (course of action) is specified by the backward induction terminal analysis introduced in
section 6.2
The backward induction procedure for our simple mesh network is depicted in Figure 7.3, The
course of action in this example is through experiment e. Then for j ∗ = 1 choose j = 3, for
j ∗ = 2, choose j = 1, and for j ∗ = 3, choose j = 3.

7.2 VCR Complexity
2
The run time complexity of the proposed scheme (VCR), is Θ(n), where n = Ni corresponds to
the size of the matrix for the construction of the posteriori distribution. we recall that Ni is the
maximum number of neighbors of node i at time t. Since the VCR is a decentralized algorithm, the
number of accessible neighbors of a node is bounded and limited. Therefore, VCR will converge
quickly.
In order to have an estimate of the sample size m required for the construction of posterior probability distribution Pi (j|j ∗ ). We use the law of the iterated algorithm proposed by Kolmogorov,
in [56]. The upper and lower bound on the rate of convergence of the estimator of a distribution to

125

Figure 7.3 Node 0 decision tree with backward induction procedure
its true value are as follows
√
ˆ
m P −P
≤ 1/2
lim supm→∞ √ m
2 ln ln m
√
ˆ
lim inf m→∞ 2m ln ln m Pm − P = π/2
From the above, the upper bound on the error of the estimator based on the sample size m, follows

126

that for large m:

√
ln ln m
ˆ
.
Pm − P < √
2m

(7.4)

Therefore, for m = 100, the error is about 0.15; as m increases the error converges exponentially
to zero. By selecting m = 200, the error is 0.004. If we assume that the network installed in an
area, just started to operate, then the first 150 msec of the operation time should be dedicated to
collecting about 150 samples.
We discarded the memory of the node after taking and using a sample of 150 matrices to
minimize memory usage.

7.3 Simulation
Our topology is similar to Figure 7.1. The number of accessible nodes Ni varies depending on the
radio signal strength. A random value is assigned for the radial distance of node i from node j. If
node j is within the radio transmission range of node i, it is considered accessible by node i. In our
simulation model we have 5 spectrum bands. The range of their corresponding bandwidth changes
from 6Mb/sec (could correspond to FM radio band) to 144Mb/sec (similar to a TV channel). Note
that a spectrum band depending on its type could have different number of channels. The bandwidth of each spectrum is divided equally among its channels. We used the JSVM software tools
to generate realtime traffic. A YUV video file with 176x144 pixels per inch (ppi) spatial resolution
is encoded and the stream file is extracted. The stream file has I, P and B packets with high to low
frame length respectively. In addition, network nodes also generate traffic packets with 512 bytes
size, to demonstrate a real life scenario where there exists other traffic activities on the network.
The packets arrival rate is based on a lognormal distribution with mean ν and standard deviation σ,
based on the measurement study [50]. We used µ as 0.8, 0.2, 0.5 and 0.5 variance to model a heavy,
127

moderate and light occupancy of users on channels. The video file is sent from the server to the
client which is located in the outer layer. We compared our method with OSDRP [33] designed for
40

PSNR (ppi)

35
30
25
20
15
10

15

20

α (msec)

25

30

MCR
OSDRP
35

Figure 7.4 Mean peak-signal-to-noise ratio for different α

a dynamic environment. In OSDRP protocol, the end to end routes are found based the deterministic strategy of the DSR protocol, and are prioritized according to the route lifetime. Route lifetime
is based on the channel availabilities as well as channel switching and queuing delays. In addition,
in order to support QoS, it controls the transmission power and selects the nearest forwarding SUs
to the SU destination node.
Figure 7.4, shows the robustness of our scheme to the primary users’ arrival rate. A network
with 30 nodes is chosen scattered around in 1000x1000sqm field. The measurement study [54]
suggests that the primary user’s traffic follows a Semi-Markov process with OFF/ON periods following an exponential distribution. Therefore, the primary users’ idle period is an exponential
distribution with mean α. As α gets larger, the channels are interrupted less frequently by primary
users.
As the mean idle period of primary users decreases, the PSNR tends to degrade for OSDRP.
In OSDRP the routing tables are not updated frequently enough and the repetition of calling the

128

120

MCR
OSDRP

delay (msc)

110
100
90
80
70
10

15

20

α (msc)

25

30

35

Figure 7.5 End-to-end delay for different values of α
route request mechanism results in transmission delay and packet loss. VCR makes its decision
considering the uncertainty of primary users’ arrival. In addition, the links are chosen that can
support the required transmission duration of I and P frames. As a result the video quality is
acceptable even when the primary users’ arrival is high. There are many controlling parameters
such as b1 , b2 , c2 , in the utility function of VCR that can be adjusted to achieve better performance.
One interesting future direction is to adjust those parameters adaptively according to the video
quality variations at the receiver. We used b1 =5,b2 =1 and c2 =0.5 in our simulation.
Figure 7.5 shows the end-to-end delay of video frames for different mean idle periods of primary users. We see that the OSDRP achieves lower delay. However, based on Figure 7.7, the
relative loss frequency of I and P frames are higher in OSDRP than those of VCR. The video quality degrades substantially with the loss of I and P frames. We see that VCR is losing the B frames
more than the other frames. Hence it is able to provide better video quality. The initial learning
phase of VCR also adds to its end-to-end delay but VCR fast decision making based on the stored
optimum strategy compensates for the delay. Ultimately, the video is received with a high quality
at the receiver. The relative loss frequency is calculated by dividing the total number of loss of

129

Video image recieved

Original

OSDRP

VCR

Video image received

(a)

Original

OSDRP

VCR

(b)
Figure 7.6 Reconstructed Video frames (a) α=20msec, (b) α=30msc
each particular frame over the total number of that frame in the original YUV file.
Figure 7.6, shows the decoded video at the receiver for α=20 msec, and α=30 msec. As shown
in Figure 7.6a, the video player is unable to decode the video beyond a received image and freezes.
When α=30 msec, the video is viewable but its quality degrades in OSDRP in comparison to MCR.
Our simulation results show that it is beneficial to use nondeterministic system theories such
as decision theory framework to cope with agile variations is spectrum diversity and availability of
dynamic cognitive radio networks.

130

% frequency of loss of I frames

50

MCR
OSDRP

40
30
20
10
0
0

10

20

30
40
α (msec)

50

60

70

% loss frequency of P frame

(a)

25

MCR
OSDRP

20
15
10
5
0
0

10

20

30
40
α (msec)

50

60

70

% loss frequency of B frames

(b)

40

MCR
OSDRP

30
20
10
0
0

10

20

30
40
α (msec)

50

60

(c)
Figure 7.7 The relative loss frequency of I, P and B frames

131

70

7.4 Summary
We used a decision theory framework to analyze the problem of downlink video routing in a cognitive radio network operating in a highly dynamic environment. The video cognitive routing (VCR)
strategy models a node’s decision among its candidate neighbors into a decision tree. VCR utilizes
a posterior distribution that provides information on the links durations uncertainty and ultimately
the suitability of a neighbor node by taking the priorities of video frames into consideration. The
best candidate is chosen by analyzing the tree with backward induction and eliminating the choices
that might decrease the sender’s gain. The VCR guides the node to choose the best candidate under high environmental variations. Our results show that VCR is successful to maintain the video
quality even when the primary users arrival rate is extremely high.

132

Chapter 8
Summary and future work

8.1 Summary
We investigated the problem of routing in cognitive radio networks. We proposed two new probability distributions called ArgMax and ArgMin that could be used in probabilistic protocols. The
ArgMax probability distribution locates the maximum random variable among a set of random
variables, while the ArgMin locates the minimum random variable. The ArgMax probability distribution is shown to outperform odds-on-mean probability distribution which is used frequently in
many applications. The ArgMin probability distribution has a variety of applications and is shown
to be useful in achieving a lower bound on the network’s minimum spectral capacity. Using these
two probability distribution, we introduced an interesting measure called primary weight measure,
which indicated the frequency and the nature of the distribution of primaries around a particular
node. A low value of the primary weight measure metric indicated uniform and frequent primary
users interruptions on the channels surrounding a node. With this information MAC and routing decisions are taken more efficiently. We developed a stochastic based routing called Primary
Spread Aware Routing Protocol (PSARP). On a cognitive-based NS2 network simulator, we compared the performance of PSARP with two previously developed routing protocols for dynamic
environment. We also developed a Cognitive Stochastic Routing (CSR) protocol based on the
PSARP stochastic framework that uses backlogged queue capacity instead of PWM. Our results

133

show higher throughput in PSARP and CSR, which indicate the advantage of stochastic-based
routing in a dynamic environment. In addition, PSARP with its PWM measure is more successful
in choosing the best path due to the correct identification of the primary users’ distribution, and
performs substantially better than CSR at high rates.
We used the decision theory concept and developed the decision tree cognitive routing scheme
(DTCR) and extended it to VCR to support a downlink video transfer in a dynamic environment.
We compared the performance of our DTCR strategy with the optimal strategy. In the optimal strategy, nodes had full knowledge of the future changes in the network parameters. In other words,
no routing strategy performs better than the optimal strategy. We also compared our method with
the local coordination based routing and spectrum assignment protocol [58] to measure the deviation of our scheme and a routing protocol designed for a dynamic environment from the optimum
strategy. Our results show that our DTCR successfully treats the occurrence of uncertainty and
performs close to the optimal scenario. The DTCR uses the posterior probability distribution to
estimate the availability of a neighbor under uncertainty. The backward induction scheme helps
a node to choose a neighbor that is more likely to be the correct candidate; it reduces the cost of
choosing wrong candidates. Therefore, it operates substantially better than the local coordination
based routing protocol; its performance is indeed near optimal at low and moderate sending rates.
However, at high sending rates, it still outperforms the local coordination based routing. Our simulation results of evaluating the VCR also show that VCR is more successful in maintaining an
acceptable Peak Signal-to-Noise Ratio (PSNR) as the arrival rate of primary users increases. In
addition the reconstructed video is played back successfully at the receiver when VCR is used.
The strategies developed could be used in many future designs to accommodate different needs
of network administrators. Using decision theory in cognitive radio networks opens the possibility
to use unlimited decision theory tools in developing new controlling and monitoring schemes. One
134

can also simply look at the utility function defined in DTCR to adjust its parameter according to
the designers requirements or network performance. In this chapter, we elaborate on some possible
future directions.

8.2 Extensions and future works
8.2.1 Utility Function Adjustments
Recall that the DTCR uses a utility function as one of its decision making component. The utility
function we used is defined in subsection 6.1.4 as follows:
∗
(−γi zj )
ui (e, j ∗ , a, j) = ηj [1 − e
][v(a, a∗ )µ(a, j)].
j

(8.1)

Note that in our modeling, we go for zero-one scenario, in the sense that wrong selection of the
node is a total loss, i.e. zero utility. Thus, we let

µ(a, j) =




 1 if a = j, when j is the true state,



 0 if a = j, when j is the true state.


However, the selection of a wrong node does not necessary mean a total loss because as long
as the selected node does not have a full queue, it is still able to transfer some of the packets.
One future direction is to model the parameter µ as a function of remaining queue capacity of the
neighbor nodes. Therefore, we do not assume total loss by selecting a wrong node but some loss
according to the transfer ability of the neighbor node.
The three control parameters β, γ, η exist that quantify the importance of local spectral mea-

135

surement, its variation, and path quality. Any of these parameters can be modeled as a function of
changes in flow dynamics or the quality of service requirements of a particular flow. For instance,
variable γ can be a function of required bandwidth of a certain flow to make the sensitivity of
the DTCR strategy self adaptive to the requirement of a particular flow passing through a specific
node.
Also, our utility function is concentrating on choosing a channel that has the least bandwidth
variability and the most stability in dynamic environment. This function could be altered to consider the delay or Expected Transmission Time (ETT) of packets in applications that are delay
sensitive. In addition, the utility function could take into account the transport level requirements
or be replaced by the utility functions that are designed for congestion control schemes such as the
ones described by Kunniyur et. al. in [62].

8.2.2 Primary Weight Measure in DTCR
The parameter η is the average queue capacity of the neighboring node. This metric provides a reliability measure over links located one hop further. However, the queue capacity variation decreases
when the load increases. Hence, DTCR selection is blind to the behavioral pattern of primary users
located one hop away from its intermediate neighbors at low and high rates. We proposed the PWM
metric in Chapter that not only provides a measure on the reliability of non-intermediate links but
indicating the distribution of primaries around a particular node. One interesting future direction
is to design η not only based on the queue capacity but also the PWM measure. The P W M[i, j]
indicates the degree of nonuniform spread of primaries in channels between nodes i and j. For
P W M[i, j] ∼ 0, primaries are more spread uniformly, and consequently there be no privilege to
any transitions distribution. For large values of P W M[i, j] there is a cluster of channels at that
node for which the presence of primaries is much less than the others and therefore choosing that
136

particular node provides a significantly stable path. This metric is highly informative about the
reliability of the links surrounding a node. PWM could be used as one of the meters that is read
by the cognitive engine of cognitive radios to indicate what knobs needs to be adjusted to avoid
inefficient transmission. (We encourage the readers to refer to Chapter for the definition of knobs
and meters).

8.2.3 More Decision Theory
It is also interesting to bring the advance concepts of decision theory into our decision theory
modeling of cognitive radio networks to evaluate the behavior of these networks over time. For instance, recall that the optimal act will minimizes the expected loss or maximizes the expected gain;
the later is maxe Ep(z|e) [maxa [Ep(s|z,e) U(e, z, a, s)]], where p(z|e) is the marginal sample distribution for the e and p(s|z, e) is the posterior distribution, p(s) ∼ p(s|z◦ , e◦ ) stands for the prior
distribution, e◦ (no experiment), z◦ (no observation). The quantity Ep(s) [maxa U(e◦ , z◦ , a, s)] −
maxa Ep(s) U(e◦ , z◦ , a, s) is referred to as EVPI, the expected value for perfect information. It
is simply the expected opportunity lost by taking the act that maximizes the expected utility. This
quantity helps a cognitive node to consider the opportunity loss. If this quantity is not high, it
takes the act that is more cost efficient. The cost could be the node energy, storage or delay. In the
broader perspective, the EVPI could be used to analyze the end-to-end cost of the system.
We encourage the readers to look at further concepts of decision theory and see how many
of them could be incorporated in system evaluation, design and modeling in cognitive radio networks.

137

BIBLIOGRAPHY

138

BIBLIOGRAPHY
[1] B. Fette, Cognitive radio technology. Academic Press, 2009.
[2] Y. Song, C. Zhang, and Y. Fang, “Stochastic traffic engineering in multihop cognitive wireless
mesh networks,” IEEE Transactions on Mobile Computing, vol. 9, pp. 305–316, 2010.
[3] Y. Cui, W. Hu, S. Tarkoma, and A. Yla-Jaaski, “Probabilistic routing for multiple flows in
wireless multi-hop networks,” in Local Computer Networks, 2009. LCN 2009. IEEE 34th
Conference on, pp. 261–264, IEEE, 2009.
[4] “Federal Communications Commission, Notice of Proposed Rule Making,,” August 12,
2000.
[5] “http://www.xgtechnology.com/,”
[6] “http://uvb-76.net/p/sdr-mk15-andrus.html,”
[7] “http://www.ettus.com/products,”
[8] J. Neel, J. Reed, and R. Gilles, “Convergence of cognitive radio networks,” in Wireless Communications and Networking Conference, 2004. WCNC. 2004 IEEE, vol. 4, pp. 2250–2255,
Ieee, 2004.
[9] M. Buddhikot, P. Kolodzy, S. Miller, K. Ryan, and J. Evans, “Dimsumnet: New directions in
wireless networking using coordinated dynamic spectrum access,” 2005.
[10] J. Mo, H. So, and J. Walrand, “Comparison of multichannel mac protocols,” IEEE Transactions on Mobile Computing, pp. 50–65, 2007.
[11] B. Horine and D. Turgut, “Link rendezvous protocol for cognitive radio networks,” in New
Frontiers in Dynamic Spectrum Access Networks, 2007. DySPAN 2007. 2nd IEEE International Symposium on, pp. 444–447, IEEE, 2007.
[12] L. DaSilva and I. Guerreiro, “Sequence-based rendezvous for dynamic spectrum access,”
in New Frontiers in Dynamic Spectrum Access Networks, 2008. DySPAN 2008. 3rd IEEE
Symposium on, pp. 1–7, IEEE, 2008.

139

[13] L. Giupponi and C. Ibars, “Distributed cooperation in cognitive radio networks: overlay versus underlay paradigm,” in Vehicular Technology Conference, 2009. VTC Spring 2009. IEEE
69th, pp. 1–6, IEEE, 2009.
[14] B. Wang, Y. Wu, and K. Liu, “Game theory for cognitive radio networks: An overview,”
Computer Networks, vol. 54, no. 14, pp. 2537–2561, 2010.
[15] J. Filar and K. Vrieze, “Competitive markov decision processes(book),” New York: SpringerVerlag, 1997., 1997.
[16] J. Pratt and H. Raiffa, R. 0. SCHLAIFER. 1965. Introduction to Statistical Decision Theory.
McGraw-Hill, New York.
[17] G. Zhu, I. Akyildiz, and G. Kuo, “STOD-RP: a spectrum-tree based on-demand routing protocol for multi-hop cognitive radio networks,” in Proceedings of the IEEE Globecom, 2008.
[18] G. Cheng, W. Liu, Y. Li, and W. Cheng, “Spectrum aware on-demand routing in cognitive radio networks,” in 2nd IEEE International Symposium on New Frontiers in Dynamic Spectrum
Access Networks, 2007. DySPAN 2007, pp. 571–574, 2007.
[19] H. Khalife, S. Ahuja, N. Malouch, and M. Krunz, “Probabilistic path selection in opportunistic cognitive radio networks,” in Proceeding of the IEEE GlobeCom Conference, vol. 30.
[20] H. Wu, F. Yang, K. Tan, J. Chen, Q. Zhang, and Z. Zhang, “Distributed channel assignment
and routing in multiradio multichannel multihop wireless networks,” Selected Areas in Communications, IEEE Journal on, vol. 24, no. 11, pp. 1972–1983, 2006.
[21] H. Shiang and M. van der Schaar, “Distributed resource management in multihop cognitive
radio networks for delay-sensitive transmission,” Vehicular Technology, IEEE Transactions
on, vol. 58, no. 2, pp. 941–953, 2009.
[22] L. Ding, S. Pudlewski, T. Melodia, S. Batalama, J. Matyjas, and M. Medley, “Distributed
Spectrum Sharing for Video Streaming in Cognitive Radio Ad Hoc Networks,” Ad Hoc Networks, pp. 855–867, 2010.
[23] B. Jashni, A. Tadaion, and F. Ashtiani, “Dynamic link/frequency selection in multi-hop cognitive radio networks for delay sensitive applications,” in Telecommunications (ICT), 2010
IEEE 17th International Conference on, pp. 128–132, IEEE, 2010.
[24] M. Xie, W. Zhang, and K. Wong, “A geometric approach to improve spectrum efficiency for
cognitive relay networks,” Wireless Communications, IEEE Transactions on, vol. 9, no. 1,
pp. 268–281, 2010.
140

[25] C. Gao, Y. Shi, Y. Hou, H. Sherali, and H. Zhou, “Multicast communications in multi-hop
cognitive radio networks,” Selected Areas in Communications, IEEE Journal on, vol. 29,
no. 4, pp. 784–793, 2011.
[26] L. Xie and J. Xi, “A qos routing algorithm for group communications in cognitive radio ad
hoc networks,” in Mechatronic Science, Electric Engineering and Computer (MEC), 2011
International Conference on, pp. 1953–1956, IEEE, 2011.
[27] K. Chowdhury and I. Akyildiz, “Cognitive wireless mesh networks with dynamic spectrum
access,” Selected Areas in Communications, IEEE Journal on, vol. 26, no. 1, pp. 168–181,
2008.
[28] Y. Hou, Y. Shi, and H. Sherali, “Spectrum sharing for multi-hop networking with cognitive
radios,” Selected Areas in Communications, IEEE Journal on, vol. 26, no. 1, pp. 146–155,
2008.
[29] K. Yang and X. Wang, “Cross-layer network planning for multi-radio multi-channel cognitive
wireless networks,” Communications, IEEE Transactions on, vol. 56, no. 10, pp. 1705–1714,
2008.
[30] Y. Shi and Y. Hou, “A distributed optimization algorithm for multi-hop cognitive radio networks,” in INFOCOM 2008. The 27th Conference on Computer Communications. IEEE,
pp. 1292–1300, IEEE, 2008.
[31] G. Cheng, W. Liu, Y. Li, and W. Cheng, “Spectrum aware on-demand routing in cognitive
radio networks,” in New Frontiers in Dynamic Spectrum Access Networks, 2007. DySPAN
2007. 2nd IEEE International Symposium on, pp. 571–574, IEEE, 2007.
[32] K. Chen, B. Cetin, Y. Peng, N. Prasad, J. Wang, and S. Lee, “Routing for cognitive radio networks consisting of opportunistic links,” Wireless Communications and Mobile Computing,
vol. 10, no. 4, pp. 451–466, 2010.
[33] K. How, M. Ma, and Y. Qin, “An Opportunistic Service Differentiation Routing Protocol for
Cognitive Radio Networks,” in GLOBECOM 2010, 2010 IEEE Global Telecommunications
Conference, pp. 1–5, IEEE.
[34] H. Song and X. Lin, “Spectrum aware highly reliable routing in multihop cognitive radio networks,” in Wireless Communications & Signal Processing, 2009. WCSP 2009. International
Conference on, pp. 1–5, IEEE, 2009.

141

[35] F. Pavlidou and G. Koltsidas, “Game theory for routing modeling in communication networks: A survey,” Journal of communication and networks, vol. 10, no. 3, pp. 268–286,
2008.
[36] P. Nurmi, “Modelling routing in wireless ad hoc networks with dynamic bayesian games,”
in Sensor and Ad Hoc Communications and Networks, 2004. IEEE SECON 2004. 2004 First
Annual IEEE Communications Society Conference on, pp. 63–70, IEEE, 2004.
[37] Q. Zhu, Z. Yuan, J. Song, Z. Han, and T. Basar, “Dynamic interference minimization routing game for on-demand cognitive pilot channel,” in GLOBECOM 2010, 2010 IEEE Global
Telecommunications Conference, pp. 1–6, IEEE, 2010.
[38] A. Cacciapuoti, M. Caleffi, and L. Paura, “A theoretical model for opportunistic routing in
ad hoc networks,” in Ultra Modern Telecommunications & Workshops, 2009. ICUMT’09.
International Conference on, pp. 1–7, IEEE, 2009.
[39] M. Caleffi, I. F. Akyildiz, and L. Paura, “OPERA: Optimal Routing Metric for cognitive radio
ad hoc networks,” IEEE Transactions on Wireless Communications, vol. 11, pp. 2884–2894,
2012.
[40] R. Winter, J. Schiller, N. Nikaein, and C. Bonnet, “Crosstalk: Cross-layer decision support
based on global knowledge,” Communications Magazine, IEEE, vol. 44, no. 1, pp. 93–99,
2006.
[41] V. Raisinghani and S. Iyer, “Cross-layer feedback architecture for mobile device protocol
stacks,” Communications Magazine, IEEE, vol. 44, no. 1, pp. 85–92, 2006.
[42] S. Khan, Y. Peng, E. Steinbach, M. Sgroi, and W. Kellerer, “Application-driven cross-layer
optimization for video streaming over wireless networks,” Communications Magazine, IEEE,
vol. 44, no. 1, pp. 122–130, 2006.
[43] M. Gong, S. Midkiff, and S. Mao, “Design principles for distributed channel assignment in
wireless ad hoc networks,” in Communications, 2005. ICC 2005. 2005 IEEE International
Conference on, vol. 5, pp. 3401–3406, IEEE, 2005.
[44] S. Kullback and R. A. Leibler, On information and sufficiency. Ann. Math. Statistics, 22(1),
1951.
[45] E. Cinlar, Introduction to Stochastic Processes. Prentice-Hall, Inc, 1975.
[46] V. Zolotarev and H. McFaden, One-dimensional stable distributions. American Mathematical
Society Providence, RI, 1986.
142

[47] R. Rajbanshi, A. Wyglinski, and G. Minden, “OFDM-Based Cognitive Radios for Dynamic
Spectrum Access Networks,” Cognitive Wireless Communication Networks, pp. 165–188,
2007.
[48] D. Chizhik, J. Ling, P. Wolniansky, R. Valenzuela, N. Costa, and K. Huber, “Multiple-inputmultiple-output measurements and modeling in Manhattan,” Selected Areas in Communications, IEEE Journal on, vol. 21, no. 3, pp. 321–331, 2003.
[49] M. Kulldorff, “A spatial scan statistic,” Communications in Statistics-Theory and Methods,
vol. 26, no. 6, pp. 1481–1496, 1997.
[50] D. Willkomm, S. Machiraju, J. Bolot, and A. Wolisz, “Primary user behavior in cellular
networks and implications for dynamic spectrum access,” IEEE Communications Magazine,
vol. 47, no. 3, pp. 88–95, 2009.
[51] M. Taylor, J. Psota, A. Saraf, N. Shnidman, V. Strumpen, M. Frank, S. Amarasinghe, A. Agarwal, W. Lee, J. Miller, et al., “Evaluation of the Raw microprocessor: An exposed-wire-delay
architecture for ILP and streams,” in Computer Architecture, 2004. Proceedings. 31st Annual
International Symposium on, pp. 2–13, IEEE, 2004.
[52] Y. Lin, H. Lee, Y. Harel, M. Woh, S. Mahlke, T. Mudge, and K. Flautner, “A System Solution
for High-Performance, Low Power SDR,” in SDR technical conference, Citeseer, 2005.
[53] B. Bing and N. Jayant, “A cellphone for all standards,” Spectrum, IEEE, vol. 39, no. 5,
pp. 34–39, 2002.
[54] S. Geirhofer, L. Tong, and B. Sadler, “A measurement-based model for dynamic spectrum
access in WLAN channels,” in Proc. IEEE MILCOM, Citeseer, 2006.
[55] T. Sobh, K. Elleithy, and A. Mahmood, Novel Algorithms and Techniques in Telecommunications and Networking. Springer Verlag, 2010.
[56] A. van der Vaart, Asymptotic statistics. Cambridge University Press. ISBN 978-0-521-784504, 1998.
[57] “http://stuweb.ee.mtu.edu/ ljialian/,”
[58] Z. Yang, G. Cheng, W. Liu, W. Yuan, and W. Cheng, “Local coordination based routing and
spectrum assignment in multi-hop cognitive radio networks,” Mobile Networks and Applications, vol. 13, no. 1, pp. 67–81, 2008.

143

[59] S. Soltani and M. Mutka, “On Transitional Probabilistic Routing in Cognitive Radio Mesh
Networks,” in WoWMoM 2011.
[60] K. Chowdhury and I. Akyildiz, “Crp: A routing protocol for cognitive radio ad hoc networks,”
Selected Areas in Communications, IEEE Journal on, vol. 29, no. 4, pp. 794–804, 2011.
[61] T. Wiegand, G. Sullivan, G. Bjontegaard, and A. Luthra, “Overview of the h. 264/avc video
coding standard,” Circuits and Systems for Video Technology, IEEE Transactions on, vol. 13,
no. 7, pp. 560–576, 2003.
[62] S. Kunniyur and R. Srikant, “End-to-end congestion control schemes: Utility functions, random losses and ecn marks,” Networking, IEEE/ACM Transactions on, vol. 11, no. 5, pp. 689–
702, 2003.

144