MAC AND ROUTING PROTOCOLS FOR MULTI-HOP COGNITIVE
RADIO NETWORKS
Except where reference is made to the work of others, the work described in this
thesis is my own or was done in collaboration with my advisory committee. This
thesis does not include proprietary or classifled information.
Yogesh Reddy Kondareddy
Certiflcate of Approval:
Sadasiva M. Rao
Professor
Electrical and Computer Engineering
Prathima Agrawal, Chair
Samuel Ginn Distinguished Professor
Electrical and Computer Engineering
Shiwen Mao
Assistant Professor
Electrical and Computer Engineering
George T. Flowers
Interim Dean, Graduate School
MAC AND ROUTING PROTOCOLS FOR MULTI-HOP COGNITIVE
RADIO NETWORKS
Yogesh Reddy Kondareddy
A Thesis
Submitted to
the Graduate Faculty of
Auburn University
in Partial Fulflllment of the
Requirements for the
Degree of
Master of Science
Auburn, Alabama
August 9, 2008
MAC AND ROUTING PROTOCOLS FOR MULTI-HOP COGNITIVE
RADIO NETWORKS
Yogesh Reddy Kondareddy
Permission is granted to Auburn University to make copies of this thesis at its
discretion, upon the request of individuals or institutions and at
their expense. The author reserves all publication rights.
Signature of Author
Date of Graduation
iii
Vita
Yogesh Reddy Kondareddy, son of Bhakthavatsala Reddy Kondareddy and Gir-
ija Sakkuru was born on June 8th, 1985, in Chittoor District, India. He received
the Bachelor of Technology degree in Electrical Engineering from Mahatma Gandhi
Institute of Technology in 2006. He joined the Masters program in the Department
of Electrical and Computer Engineering at Auburn University in August 2006. His
current area of research is focused on Multi-Hop cognitive radio networks.
iv
Thesis Abstract
MAC AND ROUTING PROTOCOLS FOR MULTI-HOP COGNITIVE
RADIO NETWORKS
Yogesh Reddy Kondareddy
Master of Science, August 9, 2008
(B.Tech., Mahatma Gandhi Institute of Technology, 2006)
55 Typed Pages
Directed by Prathima Agrawal
Cognitive radio networks that allow dynamic spectrum access are considered
spectrally more e?cient than networks using flxed spectral allocation. These net-
works are characterized by dynamically changing channel sets at each node. Multi-
hop cognitive radio network is a cooperative network in which cognitive users take
help of their neighbors to forward data to the destination. Control signals used to
enable cooperation are communicated through a common control channel (CCC).
Such a usage introduces conditions like channel saturation which degrades the over-
all performance of the network. Thus, exchanging control information is a major
challenge in cognitive radio networks. Moreover, the graph theoretic approach used
in traditional multi-hop networks fails to e?ciently model multi-hop cognitive radio
networks and capture the required information for optimal routing. Hence, conven-
tional graph-based routing protocols such as DSR or AODV cannot be used directly,
for route discovery in such networks.
v
Two ideas are proposed in this thesis as a solution to the above problems. Firstly,
a MAC protocol for multi-hop cognitive radio networks is proposed to avoid a com-
mon control channel. The scheme is applicable in heterogeneous environments where
channels have difierent bandwidths and frequencies of operation. It inherently pro-
vides a solution to issues like CCC saturation problem, Denial of Service attacks
(DoS) and multi-channel hidden problem. The proposed protocol is shown to provide
better connectivity and higher throughput than a CCC based protocol, especially
when the network is congested.
Secondly, a unique multi-edge planar graph model for routing is proposed which
can e?ciently represent a multi-hop cognitive radio network. The model is quite
simple and could be used in conjunction with any conventional graph-based routing
protocol. The model is validated through simulations and the complexity of the model
is shown to be lesser than an earlier layered graph model.
vi
Acknowledgments
First and foremost, I would express my sincere gratitude to my advisor Professor
Prathima Agrawal for her guidance and help during my study and research at Auburn.
Thanks for leading me into the research area of wireless networks. Without her
patience and support, this thesis would not be possible.
I also thank Professors Sadasiva M. Rao and Shiwen Mao for serving on my
advisory committee. My thanks also go out to my colleagues in the Wireless Re-
search Laboratory, Shaoqiang Dong, Pratap Simha, Srivathsan Soundararajan, Nir-
mal Andrews and Harish Kongara for the discussions and valuable suggestions on our
research.
I am grateful to my parents for their consistent support and encouragement
during my study and thanks to my friends for their kind presence whenever needed.
Part of the research was supported by a grant from Air Force O?ce of Scientiflc
Re- search (AFOSR) grant No. FA9550-06-1-0103.
vii
StylemanualorjournalusedJournalofApproximationTheory(togetherwiththe
style known as \aums"). Bibliograpy follows van Leunen?s A Handbook for Scholars.
Computer software used The document preparation package TEX (speciflcally
LATEX) together with the departmental style-flle aums.sty.
viii
Table of Contents
List of Figures x
1 Introduction 1
1.1 Cognitive Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Multi-Hop Cognitive Network . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 MAC Layer Issues in Multi-Hop Cognitive Networks 6
2.1 The Common Control Channel problem . . . . . . . . . . . . . . . . . 6
2.2 Multi-channel hidden terminal problem in MHCRNs . . . . . . . . . . 8
2.3 Literature review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4 Synchronized MAC Protocol . . . . . . . . . . . . . . . . . . . . . . . 10
2.4.1 Network initialization state . . . . . . . . . . . . . . . . . . . 11
2.4.2 Exchange of control signals and data . . . . . . . . . . . . . . 12
2.5 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5.1 Throughput performance . . . . . . . . . . . . . . . . . . . . . 16
2.5.2 Network Connectivity . . . . . . . . . . . . . . . . . . . . . . 17
3 Routing Issues in Multi-Hop Cognitive Networks 20
3.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 Multi-Edge Graph Model . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.1 Graph Topology Formation . . . . . . . . . . . . . . . . . . . 24
3.2.2 Weight assignment and Routing in Multi-Edged Graph Model 27
3.3 Simulation results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.3.1 Analytical Model . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3.2 Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4 Conclusion 41
Bibliography 42
ix
List of Figures
2.1 Two cognitive nodes with a set of free channels. . . . . . . . . . . . . 7
2.2 Four nodes with respective available channels. . . . . . . . . . . . . . 8
2.3 Six cognitive nodes with a set of free channels at each node. . . . . . 13
2.4 Five channels with the control and data transfer events in their respec-
tive time slots. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5 Average Throughput vs. Flow Rate. Packet size is 512 bytes. . . . . . 17
2.6 Percentage of network connectivity as the number of channels are var-
ied for a group of 10 nodes. . . . . . . . . . . . . . . . . . . . . . . . 18
2.7 Percentage of network connectivity as the number of nodes is varied
for a set of 10 channels. . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.1 Example layered graph model representing a 4 node network with 3
possible channels. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 Nodes A and B linked by 2 edges. . . . . . . . . . . . . . . . . . . . . 25
3.3 Graphical representation in traditional network. . . . . . . . . . . . . 26
3.4 Graphical representation in cognitive network. . . . . . . . . . . . . . 26
3.5 Path taken if only weights were considered. . . . . . . . . . . . . . . . 28
3.6 Path followed as the new weights are calculated. . . . . . . . . . . . . 29
3.7 Comparison of percentage of successful routes as a function of number
of nodes with and without switching interfaces. . . . . . . . . . . . . 32
3.8 Comparison of percentage of successful routes as a function of number
of channels with and without switching. . . . . . . . . . . . . . . . . . 33
x
3.9 Comparison of Practical Results and Theoretical Results for a switch-
ing radio network as the number of nodes are varied for a set of 10
channels. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.10 Comparison of Practical Results and Theoretical Results for a non-
switching radio network as the number of nodes is varied for a set of
10 channels. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.11 Layered Graph model representing a sample 4 node network. . . . . . 38
3.12 Planar Graph model representing a sample 4 node network. . . . . . . 39
xi
Chapter 1
Introduction
Guglielmo Marconi?s flrst Radio Broadcast was a point-to-point communication.
With the emerging radio technologies such as Wi-Fi, WiMax, Bluetooth, ZigBee and
the growing panoply of cellular and satellite communication, we need to pack the
radio waves to accommodate each of these services. To minimize interference, each of
these technologies is restricted to speciflc bands of the spectrum. If we tried imposing
this sort of regime on road transportation, we might wind up with a system in which
buses, cars and trucks were each restricted to their own separate roadways.
Radiospectrumallocationisrigorouslycontrolledbyregulatoryauthoritiesthrough
licensing processes. Most countries have their own regulatory bodies, though regional
regulators do exist. In the U.S., regulation is done by the Federal Communications
Commission (FCC). Spectrum has long been allocated in a flrst-come, flrst-served
way. According to the FCC [1], temporal and geographical variations in the utiliza-
tion of the assigned spectrum range from 15% to 85% [2]. If radios could somehow
use a portion of this unutilized spectrum without causing interference, then there
would be more room to operate and exploit. Cellular telephony and other important
services would then be a lot cheaper and would be a lot faster as well. To manage
such feats, cellphone handsets would have to be able to shift their frequency of opera-
tion on demand without packing in lots of extra hardware. The key technology which
enables dynamic spectrum access is a Software-deflned Radio [3]. A bigger goal is a
1
wireless device that is smart enough to analyze the radio environment and decide for
itself the best spectral band and protocol at the lowest level of power consumption.
The name of such a device is \Cognitive Radio", and some have already emerged
from the laboratory to be fleld tested by the U.S. military.
1.1 Cognitive Network
A cognitive network is an opportunistic network. The basic premise of a cognitive
network is that the owner of a licensed spectrum may not be using the spectrum
always. Hence, this unused and licensed spectrum can be utilized by other users who
have a need for the same. The licensed owner of a frequency band is called a primary
user and the one who utilizes spectrum opportunities for communication is called a
secondary user. Networks built using this concept are called cognitive radio networks.
The part of spectrum, allocated to a user for communication, is referred to as
a channel. A channel is temporarily available to a secondary user when the primary
user of that channel is not using it at that instant of time. Every secondary user is
assumed to have the capability of sensing a channel for the presence of primary user
using a cognitive radio i.e. every secondary user is assumed to have a cognitive PHY
layer. Thus, a secondary user may have a set of free channels (available channels)
for communication. One of the available channels is chosen for communication. An
important constraint on the choice of the channel is that, both the sender and receiver
should be on the same channel for possible communication. If the receiver is not in
communicating range of the sender, the communication has to be set up through
2
several intermediate nodes. Such types of networks are called Multi-hop Cognitive
Radio Networks (MHCRN).
1.2 Multi-Hop Cognitive Network
A MHCRN is, in many ways, similar to a multi-channel network. In both net-
works, each user has a set of channels available for communication. When two users
want to communicate, they negotiate via a common control channel (CCC) to select
a communicating channel. Two major difierences in these two network environments
are:
? The number of channels available at each node is flxed in a multi-channel net-
work whereas it is a variable in a MHCRN. It is possible that a user has no
available channel at all due to the complete occupancy of the spectrum by
primary users.
? In general, the channels in a multi-channel environment have equal transmission
ranges and bandwidths unlike in a MHCRN in which the environment is hetero-
geneous. Thus, a MHCRN is a combination of a multi-hop and a multi-channel
network.
While the MHCRN concept appears attractive, there are many complexities in-
troduced not only due to the frequency shifting in the PHY layer but also due to
multi-hop characteristics of these networks. Some of them are:
? Since the available channels for communication vary with primary user?s tra?c,
the cognitive PHY layer is dynamic in nature.
3
? Due to the multi-hop nature, the choice of a channel for each secondary user
is now constrained by the available channel set at every user along the route.
A route is possible only if every pair of users along the route have at-least one
common channel available at their respective locations.
? After a communication path is established through a set of intermediate nodes,
still the route may fail due to the dynamic nature of the PHY layer at each
node. A new route has to be discovered with the new set of available channels.
Due to the abrupt failure in communications and delays caused in discovering a new
route, traditional routing protocols in the network stack are either not applicable
or very ine?cient on MHCRNs. Similarly the MAC protocols used in multi-channel
networks cannot be applied to a MHCRN due to the above mentioned difierences
in the two networks. However, the issues and challenges related to these networks
apply to a MHCRN as well. For example, CCC and multi-channel hidden terminal
problems [4] which are related to a multi-channel network are common to a MHCRN.
This work addresses two of the problems associated with MHCRNs. Firstly; it
addresses the impact of the cognitive PHY layer on the network (routing) layer of
the protocol stack. Routing operations in MHCRN are analyzed using a multi-edge
planar graph model. Such a model is general enough to be applied to well known
routing protocols such as AODV [5], DSDV [6], and DSR [7].
Secondly, a new MAC protocol for MHCRNs is proposed which avoids the need
of a dedicated CCC and solves the multi-channel hidden terminal problem [4]. The
main idea is to divide total time into flxed-time intervals, each representing one of the
available channels. At the beginning of each time slot, all nodes in the network listen
4
to a channel which the time slot represents for exchanging control signals. Thus, all
nodes in the network are synchronized.
1.3 Organization
The work is divided into two parts. The flrst part discusses about the MAC
layer issues and protocol and the second part discusses the Routing layer issues and
protocol. The related work and the introduction required for the respective topics
are discussed before the idea is presented. As a result, a separate literature review
section is obviated.
5
Chapter 2
MAC Layer Issues
in Multi-Hop Cognitive Networks
In this chapter, we describe the common control channel (CCC) problem and
brie y explain the multi-channel hidden terminal problem [4] in the context of a
MHCRN.
2.1 The Common Control Channel problem
As discussed earlier, two users in a MHCRN are connected if they have a common
channel for communication. It is possible that each user has a choice of more than
one channel. In that case, the sender and the receiver need to agree upon a common
communicating channel which is available to both. The initial handshake signals
to negotiate the choice of a common channel are called control signals. But such
negotiations require communication over a common signaling channel. This is called
the common control channel problem. This problem is illustrated in more detail using
Fig. 2.1. A cognitive user is referred to as a ?node? in the rest of the work.
Suppose Node A has channels 1, 3 and 4 available and node B has 1, 2 and 4
available as shown in Fig. 2.1. These available channels form the channel set of the
respective pair of nodes. Also, suppose that A is unaware of B?s channel set and vice
versa. It can be seen from the flgure that channels 1 and 4 are common among the
two nodes. When node A wants to transmit to node B, A and B should:
6
Figure 2.1: Two cognitive nodes with a set of free channels.
? Negotiate their channel sets and
? Exchange ?Request to Send? (RTS) and ?Clear to Send? (CTS) messages to
reserve a channel for communication in a manner similar to IEEE 802.11 Dis-
tributed Coordination function (DCF). These control messages in turn have to
be negotiated via a channel.
Intuitively, a separate dedicated channel for control signals would seem a simple
solution. But a dedicated CCC has several drawbacks as discussed in [8]. Firstly,
a dedicated channel for control signals is wasteful of channel resources. Secondly,
a control channel would get saturated as the number of users increases similar to a
multi-hop network as identifled in [4]. Thirdly, an adversary can cripple the dedicated
control channel by intentionally  ooding the control channel. This is the Denial of
Service (DoS) attack as discussed in [9].
Another solution to exchange control messages is to choose a channel among the
available channels as the control channel. For example, in Fig. 2.1, channel 1 or 4
can be chosen as the control channel. When the primary user of that channel returns,
a new channel which is available to all users is chosen. This approach is not feasible
because the probability that a particular channel is available to all users is small.
Moreover, the available channels may vary in the frequency of operation, bandwidth
7
and transmitting range. Due to such heterogeneity in the transmission range, the
connectivity and scalability of the network varies with the control channel because
a channel with shorter transmission range may not cover all the areas covered by a
channel with a longer transmission range. Thus, there is a need for a better protocol
which avoids the use of a CCC and which takes heterogeneity into account while
choosing a channel for communication.
2.2 Multi-channel hidden terminal problem in MHCRNs
The multi-channel hidden terminal problem was identifled in [4] for multi-channel
networks. The same problem is extended to a cognitive network environment in [10].
It is brie y explained below.
Figure 2.2: Four nodes with respective available channels.
Fig. 2.2 represents 4 nodes with their respective channel sets. Suppose that only
adjacent nodes are in transmitting range. Since channel 1 is available to all nodes,
suppose that channel 1 is chosen as the control channel and that node C and D are
already communicating using channel 3. When node A wants to transmit a packet to
node B in channel 2, it sends an RTS to B on the control channel (channel 1 in this
case). B sends a CTS proposing channel 2 for data communication. Node A sends
a conflrmation message to B and to its neighbors that channel 2 is reserved for data
8
communication. But since C was communicating in channel 3, it did not receive the
CTS from B. So C assumes that channel 2 is free and might initiate a communication
with node B in channel 2 resulting in a collision. This is called the multi-channel
hidden terminal problem. In [10], this problem is addressed by allocating special
slots. In these time slots the communicating pair of nodes gets updated from its
neighboring nodes about any potential hidden terminals in their vicinity. Though,
the problem is solved successfully using this method, a CCC is still used for control
signal exchange.
To avoid the above mentioned disadvantages, a MAC protocol which does not
need a pre-allotted control channel and which solves the multi-channel hidden termi-
nal problem, is proposed in this work.
2.3 Literature review
Considerable number of MAC-protocols have been proposed for cognitive net-
works previously [11, 12, 13, 14, 15, 16, 17, 18, 19]. But most of these assume a
Common Control Channel (CCC) which limits the robustness of the network in many
ways as pointed out earlier. [11, 12] assume a CCC which is one among the available
channels. Similarly [13, 14, 15] also assume a CCC for the purpose of exchanging
control signals. There are a few proposals which solve the problem of CCC partially.
Since the probability that a CCC is available at every node is small, [16] proposes a
method in which a group of users which are close together form a sub-ad hoc network
and select a channel for communicating control information. If the primary user of the
channel returns, a difierent channel which is available to everyone in the sub-group
9
is chosen. It is assumed that one of the members of the group has the capability to
connect to the neighboring groups. Though it is an indirect solution to the problem
of availability of a CCC, it does not completely eliminate the dependency on a CCC.
There is still a possibility that a user can pose a DoS [17] attack. Moreover, the
group head that is responsible for sharing of the information between two groups gets
a chance to act selflshly on its data. [10] solves multi-channel hidden node problem
but still uses a CCC for control signal exchanges.
Though the MAC layer misbehaviors have been pointed out in [9], there is no ex-
isting protocol which considers the control channel saturation problem, multi-channel
hidden terminal problem and heterogeneity of channels simultaneously. Compared to
the above proposals, our protocol does not require a separate control channel for the
purpose of control signal exchange. Instead it requires synchronization among all
nodes. Though it is an extra requirement on the network, it will be shown in next
chapter that it achieves better throughput and network connectivity than maintaining
a separate control channel.
2.4 Synchronized MAC Protocol
In this chapter, the proposed scheme is presented. Before that, the assumptions
are summarized below.
? Every node is assumed to be equipped with two radios. One of the two radios
is used for just listening (listening radio) to the control signals and the other
for both receiving and transmitting data (data radio).
10
? The maximum number of channels at each node is N, but the channels available
at each node may vary with the primary user?s tra?c.
The proposed protocol will be referred to as Synchronized MAC (SYN-MAC) [20]
from now on.
2.4.1 Network initialization state
Initially, when there are no cognitive users (nodes) to form a network or when the
new user wants to form a sub-group independent of the existing users, the network is
said to be in the initialization state.
In the network initialization state, a node checks whether it is the flrst node or
not by listening in each channel for N ? Tc seconds. If it hears no beacons then
it is considered the flrst node. The flrst node divides time into N number of equal
time slots of flxed duration Tc, since there are N possible channels. Each time slot
is dedicated to one channel for control signal exchange. The node then beacons in all
its available channels at the beginning of the corresponding time slots. The following
nodes choose one of the channels and listen for beacon messages to synchronize their
listening radios. Since the flrst node broadcasts in all its available channels, the
following nodes can choose any channel and be sure to receive a beacon message within
N ? N ? Tc seconds. After it receives a message, the nodes exchange information
about their channel sets. If it did not receive a beacon, then it is considered to be
the flrst node.
At the end of the network initialization state, all nodes are synchronized and
every node has the information about its neighbors and their respective channel sets.
11
Nodes being synchronized mean that at the beginning of every slot, the listening radio
of every node tunes to the respective channel which the slot represents and listens
in that channel. It is analogous to passing a token among the channels and every
node is listening to that particular channel at a given time. The continuous scanning
(listening) of channels is necessary for three reasons, which are:
1. To keep track of primary user?s presence,
2. For exchanging control signals and
3. To avoid multi-channel hidden node problem.
2.4.2 Exchange of control signals and data
When a node wants to start a communication, it should exchange the required
control signals. To exchange the control signals it chooses one of the channels common
between itself and its neighbor. It then waits for the time slot which represents the
chosen channel. Since all nodes will be listening to that channel in that slot duration,
it will start exchanging its control signals with its neighbor.
Unlike the exchange of control signals which need to be exchanged only at the
beginning of specifled time slots, the data is exchanged after exchanging the control
signals. So exchange of data occurs in an un-synchronized fashion using the second
radio (data radio). Control signals or information is exchanged among the nodes
whenever an event occurs. These events are called information events. There are 4
information events (IEs) which are:
? IE-1: When a new node enters the network, it should notify its arrival to its
neighboring nodes.
12
? IE-2: When the available channel list at a node changes due to the primary user
tra?c, the node?s neighbors have to be updated about its new channel list.
? IE-3: When a node starts, stops or changes its channel of communication, the
information is forwarded to its neighbors to enable them to know whether the
data packets can be forwarded through the communicating node.
? IE4: When a node wants to communicate with its neighbor, it sends a set of
control signals to inform its intent to start a communication in a particular
channel. This event is followed by an acknowledgement by the neighbor to
convey its acceptance/denial. On acceptance, data transfer takes place on the
negotiated channel without any delay.
Figure 2.3: Six cognitive nodes with a set of free channels at each node.
The complete process of starting a communication is illustrated with an example
shown in Fig. 2.3.
Consider a network of 6 nodes as shown in Fig. 2.3. There are a total of 5
possible channels among them. The array of blocks above each node represents the
available channels at that node. Since the total number of channels is 5, time is
divided into 5 slots and the listening radio of the nodes keep listening to successive
channels at the beginning of the respective slots. Now, suppose Sender (S) wants to
13
start a communication with Receiver (R). Since the nodes know the available channel
sets of their neighbors, node S sees that it has channels 1 and 5 in common with node
R. It chooses one of these channels for communicating with node R. If channel 1 is
chosen, then node S waits for a random back ofi time (shown using solid shading in
Fig. 2.4) and starts its negotiations, similar to IEEE 802.11 DCF. Once the nego-
tiation is successful the data transfer takes place in channel 1 immediately. This is
shown in Fig. 2.4.
Figure 2.4: Five channels with the control and data transfer events in their respective
time slots.
Now, suppose that node B observes that primary user of channel 4 has returned.
So, it generates an IE2 which contains its new channel set. Since node B knows
that it can reach its neighbors through channel 2, it waits for the time slot which
represents channel 2, backs ofi for a random time and then transmits its information
(IE2). Nodes S and A, on receiving this information learn that node B will not be
available on channel 4. Similarly, when node C sees that primary user of channel
4 has returned, it waits till the slot representing channel 3 and then broadcasts the
14
information to nodes R and D. All activities described above are summarized in Fig.
2.4.
With the above explanation, we will demonstrate the advantages of the protocol
over CCC based protocols now. We will also show how difierent issues discussed in
chapter 2 are solved using our protocol.
Firstly, it should be clear by now that there is no dedicated CCC for control
signals, so there would be no concept of control channel saturation. It will be shown
in the next section that there is a signiflcant beneflt in terms of throughput from not
having a CCC in a MHCRN. Also, in Fig. 2.3, it is seen that there is not even one
channel common at all of the six nodes and hence control signal exchange could not
have been possible using the CCC based protocols. But in SYN-MAC communication
could be established as discussed.
Secondly, observe that when node S wanted to transmit to R, it chose channel
1 and sent an RTS to R and node R sent CTS back to S. Suppose that nodes C
and D are already communicating over channel 3. Though nodes C and D are busy
communicating data in channel 3, since the listening radio of C is listening to channel
1, it receives the CTS sent by node R and hence notes that channel 1 will be busy for
the ?Network Allocation Vector? (NAV) amount of time. But for the synchronization
and the extra radio (listening radio), multi-channel hidden terminal problem could
not be avoided.
Thirdly, suppose the transmitting range of channel 1 is so short that node S
can?t reach R through that channel and that of channel 5 is long enough to reach its
adjacent node. This is an example of heterogeneous environment. When node S wants
to send a packet to R as discussed, S chooses channel 5 now, instead of channel 1 and
15
starts its negotiations in the flfth time slot. Hence maximum connectivity is possible
in a heterogeneous environment also. In the following section, the efiectiveness of the
proposed protocol is demonstrated using simulations.
2.5 Simulation results
In this section the SYN-MAC protocol is compared with the CCC based protocol
proposed in [11] for throughput performance and network connectivity.
2.5.1 Throughput performance
NS2 with CMU wireless extensions is used for this part of simulations. A multi-
hop network with 80 nodes, randomly placed in a 1000m 1000m area is considered. 40
nodes are chosen randomly as the sources and the other 40 nodes as destinations. The
transmission range of each node is set to 250m. A set of three channels is chosen, each
of which is available at each node with a probability of p = 80 %. The primary users
are accounted for using this probability. The  ow rate is varied for each connection
to increase the network tra?c and the throughput performance of CCC-MAC and
SYN-MAC is compared. Each point in the graph in Fig. 2.5 is an average of 100
simulations.
Fig. 2.5 shows the aggregated throughput of both the protocols as the network
tra?c is increased. The throughput of SYN-MAC is signiflcantly higher than that of
CCC-MAC. The major reason for this behavior is that a CCC among all the nodes is
not always available and so many times a connection is not established. Due to these
failures the throughput is signiflcantly lower in CCC-MAC. It can also be observed
that when the tra?c is very high, the throughput of CCC-MAC starts dropping.
16
Figure 2.5: Average Throughput vs. Flow Rate. Packet size is 512 bytes.
This is because a single channel is used for control signal exchange. With increased
tra?c, contention of control packets increases and throughput degrades. Whereas, in
SYN-MAC the control signal tra?c is shared among all available channels and there
is lower contention and hence, better throughput.
2.5.2 Network Connectivity
Network connectivity is deflned as the percentage of nodes in the network which
are connected together either directly or through several hops.
The network connectivity of CCC-MAC and SYN-MAC protocols are compared
in this subsection using MATLAB simulations. A network of 10 nodes randomly
deployed in a 500m?500m area is considered. Each node is assigned a set of channels.
Each channel is available at a node with a probability of p= 80%. Fig. 2.6 shows the
percentage of network connectivity as a function of the number of channels. It can
17
be observed that the SYN-MAC protocol assures higher connectivity than the CCC-
MACapproach. Asthenumberofchannelsisincreasedtheprobabilitythatacommon
channel is found among all nodes increases. The rate of increase in SYN-MAC is
higher than that of CCC-MAC. The SYN-MAC assures nearly 100% connectivity
while the CCC-MAC provides only 65% connectivity for a group of 10 nodes and a
set of 10 channels.
Figure 2.6: Percentage of network connectivity as the number of channels are varied
for a group of 10 nodes.
Fig. 2.7 shows the percentage of network connectivity versus the number of
nodes. It is observed that for a flxed number of channels, as the number of nodes
is increased, the connectivity of both the approaches drop. But the fall in the CCC
approach is very steep. This is due to the fact that as the number of nodes increases,
the probability that a common channel is available at all the nodes decreases. For a
network of just 10 nodes, the percentage connectivity of CCC-MAC fell to nearly 65%
18
and that of SYN-MAC is 93%. So, it can be concluded that the proposed protocol
provides higher network connectivity than the CCC approach.
Figure 2.7: Percentage of network connectivity as the number of nodes is varied for
a set of 10 channels.
Till now, we have discussed the MAC layer issues and a solution to these problems
in MHCRNs by introducing a MAC protocol which avoids the need for a common
control channel for the entire network. In the following chapters routing issues will
be discussed and a innovative solution will be proposed.
19
Chapter 3
Routing Issues
in Multi-Hop Cognitive Networks
Routing in multi-hop networks has been extensively studied in the literature.
Several protocols have been proposed among which AODV [5], DSDV [6], DSR [7]
are some of the widely used ones. Most of these protocols are graph based protocols,
wherein a network is represented as a graph. Nodes in the graph represent the users
and edges are used to join two nodes which can communicate with each other. The
edges are assigned weights which generally represent the distance from one node
to another. Protocols, mentioned above use this graph based information and flnd
routes between nodes using various metrics, like DSDV flnds a route based on the
shortest distance or hop count. Hence, the graph theoretic approach is very e?cient in
modeling traditional networks and provides su?cient information for route discovery.
Traditional wireless networks make two general but fundamental assumptions.
? Fixed spectrum allocation i.e., pair of nodes communicate over a flxed band of
spectrum (channel) and
? That the flxed channel is always available for communication.
This means that the physical layer and its fundamental characteristics like bandwidth,
and channel of operation do not change and are static both in space and time. As a
20
result of these general assumptions, the graph model mentioned above is su?cient to
represent traditional networks.
In a MHCRN, as discussed earlier, secondary users scan for the channels in which
the primary users are inactive. Among the set of free channels, a suitable channel is
used by the secondary user and when the primary user returns, a new free channel
is located which may have difierent physical characteristics like bandwidth, power
constraints and interference levels. This basic characteristic difierentiates a MHCRN
from traditional networks.
For a MHCRN:
? The channel of communication is not flxed
? A particular channel is not always available for communication and depends on
primary user?s tra?c.
Thus, PHY layer of a MHCRN may vary both in space and time and is dynamic
in nature. If a route discovery has to be initiated in such networks, a series of steps
have to be followed in which, scanning for available channels at each node, deciding
on a common channel for each pair of neighbors are most important ones. If there
is more than one common channel between a pair of nodes, then an optimal channel
has to be chosen based on various criterion such as interference level, bandwidth
etc. Moreover, FCC regulations may specify difierent limits on the maximum allowed
transmission power for difierent frequency bands. As a result, difierent channels may
support varied transmission ranges [21] due to which a node reachable in one channel
may not be reachable in another. Hence, the neighbor set of a node may depend on the
type of channel used for communication. Due to lack of consideration of important
21
information like available channel set at each node, possible routes to other nodes
and neighbor set in each channel, traditional graph model is insu?cient to model
MHCRNs. For example, DSR [7] was used in a multi-radio multi-hop single channel
network [22] to flnd an e?cient route. If the network were characterized by multiple
channels which keep varying, the routing would not have been possible using simple
DSR since, the graph model can represent only one flxed channel.
3.1 Related Work
A layered graph model was proposed as a solution to this problem in [23]. Fig.
3.1 shows a multi-layered graph model representing a 4 node network with three
possible channels for communication. In this graph model, each channel or frequency
of operation is represented by a layer of the graph. Since, there are three possible
channels, the graph contains three layers. Each layer is a graph containing nodes
representing users and edges joining any two nodes if they are in the transmission
range of each other through that particular channel. For example, node pairs A-B and
B-C are reachable to each other in channel 1, but node 4 is not in the communicating
range of any other node through channel 1 and hence is shown isolated in the layer.
Communication among the nodes across layers is possible through inter-layer links.
Such inter-layer communication is not shown to keep the model simple.
Using this graph model, a routing strategy was built to flnd a near optimal
route [23]. The disadvantages of this graph model are that the model is complex to
represent and most importantly since, traditional routing protocols like AODV [5],
22
Figure 3.1: Example layered graph model representing a 4 node network with 3
possible channels.
DSDV [6] and DSR [7] assume planar structured graphs, a direct application of these
protocols on layered graph model is not possible.
Hence a new ?Multi-Edge Planar Graph Model for Routing in MHCRNs? is pro-
posed in this work. Such a model is simpler and accurate as it takes into account
various radio channel related parameters in determining edge weights. The next
chapter discusses the model and its performance evaluation.
3.2 Multi-Edge Graph Model
As the name implies, this graph model, unlike the traditional graph models used
in routing, has multiple edges between a pair of nodes. This added feature of the
graph accounts for the modeling of extra characteristics of MHCRNs such as available
channel set, possible routes to other nodes through various channels and neighbor
set of each channel. Unlike in layered graph model where layers represent difierent
channels, multi-edged graph model takes advantage of extra edges to represent the
channels and weights of these edges to represent the channel?s characteristics. Due to
this characteristic of multi-edged graph model, a layered structure is obviated and is
23
reduced to a planar structure. It can be argued that the layer complexity is shifted to
edge complexity in the multi-edge planar graph model. But it will be demonstrated
later in this chapter that edge complexity of the new model is much lower than layered
graph model. The following section explains the proposed model in detail.
3.2.1 Graph Topology Formation
In MHCRN, routing depends on the available channels which in turn depend on
the primary user?s tra?c. This means that for an optimal choice of the route, the
routing layer should be provided with information about the available channel set at
each node by the PHY layer. Additionally, the total number of interfaces available at
each node is also important for optimal choice of the route. A node with a single radio
(interface) cannot communicate simultaneously over two difierent channels. Hence, to
avoid choosing routes which violate the interface constraint, knowledge of the number
of interfaces is necessary for the routing layer. So a cross layer design is necessary to
keep the routing layer updated about the changes in the PHY layer. It is assumed
in the rest of the paper that the information about the total number of interfaces
and available channels at each node is provided to the routing layer of the nodes in
question.
In the Multi-Edge planar graph model, each user is represented as a Node in the
graph. Each channel is represented by an Edge. Let graph G denote the multi-edged
graph, N denote the set of nodes and C denote the set of all possible channels. So a
pair of nodes can have 2 edges if they can use two difierent frequencies (channels) for
communication unlike conventional graph models where each pair of nodes has only
1 channel in common as in [22]. For example, if nodes A and B have two channels to
24
communicate, then it is represented as shown in Fig. 3.2. A and B can communicate
through channel 1 and channel 2. Therefore, nodes A and B are connected by two
edges. W1 and W2 represent the weights of the edges in each channel which can be
simple distance or a complex combination of difierent factors like interference, energy
etc. Every channel is assigned a channel ID. For example Channel 1 is assigned ?1?
as channel ID.
Figure 3.2: Nodes A and B linked by 2 edges.
Now, consider a graph with 4 nodes and 3 difierent channels. Each node may
have difierent channels available with it. Two nodes in this graph are connected if
they have a common channel in their channel sets. Graphical representation of these
4 nodes in a traditional network with flxed channel allocation is shown in Fig. 3.3.
Since all the nodes can communicate in only one channel in such networks, there is
only one edge between every pair of nodes which can communicate with each other.
The numbers on the edges represent the weights of the edges which in this case are
distances.
A cognitive network where each node has varying number of channels available
with it is shown in Fig. 3.4. In this graph, the node pairs A-D, D-C, and B-C have
channels 1 and 2 in common but the node pair A-B has channels 1, 2 and 3 in common
25
Figure 3.3: Graphical representation in traditional network.
Figure 3.4: Graphical representation in cognitive network.
consequently having three edges between them. All edges between every pair of nodes
are assigned the same weight because, the weights represent distance between pair of
nodes and it does not vary with type of channel. So, any routing protocol such as
AODV [5], DSDV [6], and DSR [7] gives the shortest route as an optimal route.
Algorithm 1 is used for the construction of the Multi-Edged graph model.
Algorithm 1 Construction of Multi-Edged graph model
? Add a node Ni to the graph G for each user in MHCRN.
? Add an edge between between node Ni and node Nj if they are potential neigh-
bors through channel Ci for all Ni;Nj 2 N and Ci 2 C.
? AssignweightsforeachedgebetweennodesNi andNj usingaweightassignment
algorithm for all Ni;Nj 2 N.
26
3.2.2 Weight assignment and Routing in Multi-Edged Graph Model
All graph based protocols, flnd a route based on the weights of the edges of the
graph. If the weights of the edges represent the distance between the nodes, a graph
based protocol like DSDV would choose the shortest path route. If the weights were
a function of interference then the route with lowest interference is chosen. Therefore
weight assignment is a very important step in building a graph model. In the multi-
edged graph model a problem of interface constraint arises due to the multi-edged
nature of the graph. The problem is explained below and solved by modifying the
weights of the edges. Finally, the weights of all edges are added with a cognitive cost
function which is explained later.
A node can have a single or multiple radios. Each radio (interface) is capable of
changing to a required frequency (channel) to communicate. Switching the interface
between channels is feasible in a classical wireless network, though it requires flne
synchronization between neighboring nodes and introduces overhead. But in a cogni-
tive environment where the channels are not bound to 2.4 GHz ISA band, this type
of switching might not be feasible. Moreover, the channels in a cognitive network
are distributed across a large spectrum and the channels may be separated with a
large band. In such a scenario, it might not be practical to switch channels at packet
granularity. A method to avoid the choice of routes in which switching occurs, is
proposed below.
27
Interface constraint
Now let us consider Fig. 3.4. If the weights are a simple function of distance,
then all the edges between a flxed pair of nodes would weigh the same as explained
earlier. For example, weights of channels 1, 2 and 3 are the same between nodes A
and B. In this case, distance vector routing might choose channel 1 between A, D and
channel 2 between D, C as shown in Fig. 3.5. Channel used from A to D is difierent
from D to C in this route. If node D were have having a single radio it should switch
the interface (radio) between channels 1 and 2 for carrying on the communication. As
mentioned above, it might not be always feasible, though faster radios are promised
by the growing technology. Hence, there should be a way for the routing protocol
to avoid choosing difierent channels if a node has a single available radio and when
switching is not allowed.
Figure 3.5: Path taken if only weights were considered.
This is done by adding an Interface Constraint term to the weights of outgoing
edges of single radio nodes only as shown below:
Let Interference Constraint term (IC) = jx?yj1
Where:
W - Weight of the edge
28
X - Channel ID of the incoming channel
Y - Channel ID of the outgoing channel
D - Distance Metric
Since X and Y are channel ID?s, if a same channel is chosen for incoming and
outgoing communication, then the value of X and Y will be equal and their difierence
is zero. As a result the interference constraint term is zero and the weight, W of the
edge will just be distance, D. Suppose difierent channels are chosen for the incoming
and outgoing communications, then mod of the difierence of X and Y will be a
positive non-zero value. The interference constraint term will now be inflnity and the
flnal weight, W would also be inflnity. Hence, this option will not be considered as a
successful route.
Now consider the same graph as in Fig. 3.4 and let us assume that node D has
a single radio and it cannot communicate over two difierent channels. Suppose the
routing protocol chose channel 1from A to D. The weights for the next hop would be
as shown below and the path followed is shown in Fig. 3.6.
Figure 3.6: Path followed as the new weights are calculated.
W1 = j1?2j1+7 = 1
W2 = j1?1j1+7 = 7
29
It is seen from Fig. 3.6 that the protocol would choose channel 1 in the second
hop since the weight of the edge through channel 2 (W1) is inflnity. So, by adding
an interface constraint term(IC) to the weights of outgoing edges of the single radio
nodes which cannot switch, the possibility of choosing two difierent channels by the
protocol at that node is avoided.
Cognitive cost function
The nodes in a MHCRN have the capability to sense the channels using cogni-
tive radio. This capability of the nodes can be used to flnd better routes in terms
of interference. This can be done by adding an additional term to the weights of
the edges, cognitive cost function (CF). A routing cost function incorporating mea-
surements of the instantaneous behavior of the external world, as represented for
example by current network status in terms of interference sufiered by overlaid net-
works was proposed in [24]. The cost function accounted for various terms, of which,
power, multi-user interference, reliability of the channel, tra?c in the channel and
delay factor are important. This cost function is added to the weights of the edges
to incorporate cognitive routing.
Now that we have an unlabeled graph, an algorithm to assign the weights to the
edges of the graph is needed. Algorithm 2 is used for weight assignment and routing
in MHCRN.
In the following section the performance and complexity of the multi-edged graph
model is studied.
30
Algorithm 2 Weight assignment and Routing
? Assign distance D as the weight for the edge connecting nodes Ni and Nj for
all Ni;Nj 2 N.
? Add the Interference constraint term (IC) to outgoing edges of nodes Ni if Ni
has a single radio for all Ni 2 N.
? Add the Cognitive cost function (CF) to the weights of all edges connecting
nodes Ni and Nj for all Ni;Nj 2 N.
? Use the graph G for route discovery using any graph based routing protocols
like distance vector routing.
3.3 Simulation results
A custom simulator written in C is used to simulate the multi-edge graph. The
graph model is tested using DSDV protocol. A grid topology is considered with
varying number of nodes from 2?2 to 10?10. The channels available at each node
are randomly selected. The probability that a particular channel is available at a
node is p. The value of p is chosen to be 0.5. Maximum number of channels (channel
set) at each node is varied from 2 to 10. The connectivity from the flrst node to
the last node in the graph is examined for and the percentage of successful routes is
plotted. Each point on the graphs is an average of 100 simulations.
Two sets of simulations were carried out. The flrst set of simulations assume
that all the intermediate nodes in a route can switch between channels to commu-
nicate with their two neighbors and the second set of simulations assume that no
intermediate node can switch between channels in a communication. Though these
assumptions are unrealistic, they serve two purposes.
? They help us verify the proposed model intuitively.
31
? They act as upper and lower bounds respectively.
In practice, results will lie in-between these results.
Fig. 3.7 shows the variation of percentage of successful routes with the number
of nodes in the networks in which switching the interface between the channels is
allowed and not allowed respectively.
Figure 3.7: Comparison of percentage of successful routes as a function of number of
nodes with and without switching interfaces.
It is observed that there is a success rate of 90% with switching. When switching
is not allowed, a node cannot communicate in two difierent channels simultaneously.
This constraint, limits all nodes in the route to communicate using the same frequency
(Channel). Because it is less probable that all nodes in the route have a common
channel, the success rate is lower in such a network. When switching is possible, a
route is possible if there is at least one channel between every pair of nodes along
32
the route. As a result the percentage of successful routes is far better with switching
than without switching.
It is also observed that as the number of nodes increases, the success rate de-
creases. This is because of the fact that with the increase in the number of nodes,
the probability of flnding a route with a common channel between every pair of nodes
along the route decreases.
In Fig. 3.8, percentage of successful routes is plotted against the maximum
number of channels (channel set). From this graph it is seen that with an increase in
the number of channels, the success rate of the routes increases drastically to nearly
100% with switching. This is obvious from the fact that the probability of flnding
at least one available channel between a pair of nodes increases with the number of
channels. Whereas, the probability that a common channel is found among all the
nodes with increase in number of channels increases marginally.
Figure 3.8: Comparison of percentage of successful routes as a function of number of
channels with and without switching.
33
In a real world scenario a network consists of heterogeneous nodes. Some nodes
might have single interface and some have more than one interface. When the nodes
have more than one interface, they can use one interface for each incoming and outgo-
ing channel in which case, the percentage of success rate is similar to the network in
which switching is possible. So, the practical success rate lies in-between the results
shown above.
3.3.1 Analytical Model
To verify these results an analytical model is needed to determine variation of
the probability of a successful route with the number of nodes and the maximum
number of channels is varied.
Probability of a successful route is derived below:
Consider a path along a chain of n nodes. Probability that there exists a route
between the flrst node and the last node if a channel is available at a particular node
with a probability of p is derived. Let the total number of possible channels be c.
Where:
n - Number of nodes in the route
c - Number of possible channels at each node
p - Probability that a particular channel is available at a node
P - Probability that a route exists between the flrst node and the last node
In a non-switching radio network, each radio can communicate over only one
channel at a time. So a route is possible only if all nodes in the path have at least
one common channel available.
Probability that one common channel exists among n nodes
34
= pn.
Probability that one common channel does not exist
= 1?pn.
Probability that no common channel exists among all c possible channels
= (1?pn)c.
Probability that at least one common channel exists among all possible channels
= 1?(1?pn)c.
Thus P = 1?(1?pn)c.
In a switching radio network, each node can receive and send along difierent
channels. So, a route is possible if there is at least one common channel between
the two nodes along every hop. To calculate this probability we consider each hop
separately.
Probability that one common channel exists between two nodes
= p2
Probability that a common channel does not exist between 2 nodes
= 1?p2
Probability that no common channel exists between two nodes along c possible
channels
= (1?p2)c
Probability that at least one common channel exists between two nodes
= 1?(1?p2)c
Probability that at least one common channel exists between every hop
= (1?(1?p2)c)n?1
Thus, P = (1?(1?p2)c)n?1
35
Since, the probability of a successful route along a path is known; the results from
the graph model can be verifled. The model is used to flnd the route possibility along
the shortest path. Since grid topology was used in simulating the graph model, the
shortest path would be along the diagonal. This will be a pessimistic value because,
there can be other routes possible and hence the actual probability is expected to be
higher. Results from the graph model and analytical model are plotted in Figs. 3.9
and 3.10.
Figure 3.9: Comparison of Practical Results and Theoretical Results for a switching
radio network as the number of nodes are varied for a set of 10 channels.
It is seen from the simulations that the results from the graph model match the
results from the analytical model. Hence, the proposed graph model is demonstrated
to be valid in modeling MHCRN. Since the multi-edged graph can model the MHCRN
and provide su?cient information for routing, all graph based protocols can use this
graph to flnd the routes in a MHCRN. In the above simulations, DSDV has been used
for this purpose.
36
Figure 3.10: Comparison of Practical Results and Theoretical Results for a non-
switching radio network as the number of nodes is varied for a set of 10 channels.
3.3.2 Complexity
A graph model, while modeling the network correctly should be simple. In the
following discussion the complexity of the graph model is compared with the layered
graph model proposed in [23]. A sample 4 node network represented using layered
graph model is reproduced from [23] in Fig. 3.11. Node A has not been shown by
the author for demonstration purpose. The same network is represented using multi-
edged graph model in Fig. 3.12. It can be said that multi-edged graph model is
simpler compared to layered graph model just by visual observation. Moreover it can
be observed that the layered graph model contains many unidirectional edges which
add to the complexity of the graph; unlike in multi-edged model where all edges are
assumed bidirectional and this is more realistic since wireless medium is bidirectional.
37
Figure 3.11: Layered Graph model representing a sample 4 node network.
Node complexity and edge complexity of the two models is given below. To
understand the derivation of the complexity of the layered graph model the reader is
referred to [23].
Let An?n?c be a three dimensional matrix, with two dimensions representing the
pair of nodes and the third dimension represents the channel in which each pair can
communicate. This matrix represents all possible node pairs in all channels. The
value of an element A(x;y;z) = 1 means that nodes x and y can communicate using
channel z.
Let Bn?c be a two dimensional matrix representing the available channels at each
pair of nodes. B(n;c) is 1 if nth node has channel c available. For a group of n nodes
and a total of c possible channels, let X and Y be two variables deflned as follows:
X = Pni=1Pnj=1Pck=1 A(i;j;k)
38
Figure 3.12: Planar Graph model representing a sample 4 node network.
Y = Pcj=1 B(i;j)
Using these variables the layered graph model has:
Number of Nodes = 2nc+n.
Number of Edges = X +Pni=1 Y C2 +3nc.
The planar graph model has:
Number of Nodes = n.
Number of Edges = X.
In the planar graph model, the elements of matrix A represent the edges since
A(x;y;z), represents a possible communication between node pairs x and y through
channel z. Hence, sum of all elements in matrix A, which is deflned as X, is equal to
the number of edges in multi-edged graph model. The number of nodes is equal to
n since there is only one layer. For example, in a set of 5 possible channels and 10
nodes, the layered graph model has 110 nodes and 258 edges whereas, the multi-edged
graph model has only 10 nodes and 30 edges. Thus, the multi-edged graph model is
much simpler than the layered graph model.
From the above discussion the clear advantages of the multi-edge graph model are:
39
? Planar structure as in traditional graph models.
? Lower node and edge complexity.
? Bidirectional edges.
? Graph based routing protocols like AODV, DSDV, DSR can be adopted. .
40
Chapter 4
Conclusion
In the flrst part of this work, a MAC protocol for MHCRNs is presented which
avoids the need for a common control channel for the entire network. This auto-
matically eliminates the control channel saturation problem and DoS attacks. The
multi-channel hidden terminal problem is solved by introducing synchronization into
the protocol. The protocol is also applicable to heterogeneous channels. NS2 sim-
ulation results show that SYN-MAC achieves higher throughput than CCC based
protocols. It was also demonstrated through MATLAB simulations that SYN-MAC
ofiers higher network connectivity than CCC-MAC.
In the second part, a multi-edged graph to model a MHCRN is presented. Using
such a graph to model an MHCRN enables the direct use of traditional routing
protocols for route discovery. The graph model is validated using a custom simulator
built in C. DSDV routing protocol is used in the simulations. Finally, the node and
edge complexity of the proposed model was demonstrated to be lesser than layered
graph model. In the future, the feasibility of our model will be further tested by using
difierent graph based protocols like DSR and AODV.
As a future work, we plan to combine the two concepts and study the simulated
results. Experimenting with practical Software Deflned Radios and implementing
these protocols on them is the ultimate goal.
41
Bibliography
[1] FCC, ET Docket No 03-222 Notice of proposed rulemaking and order, December
2003.
[2] Akyildiz, Ian F. ,Lee, Won-Yeol, Vuran, Mehmet C, Mohanty, Shantidev, \NeXt
generation dynamic spectrum access cognitive radio wireless networks: A sur-
vey," Computer Networks, v 50, n 13, Sep 15, 2006, p 2127-2159.
[3] Joseh Mitola and G. Q. Maguire.\Cognitive radio: making software radios more
personal," IEEE Personal Communications, 6(4):1318, 1999.
[4] J. So, N. Vaidya; \Multi-Channel MAC for Ad Hoc Networks: Handling Multi-
Channel Hidden Terminals Using A Single Transceiver," Proc. ACM MobiHoc
2004.
[5] C. E. Perkins, E. M. Royer, and S. R. Das, \Ad Hoc On-Demand Distance Vector
(AODV) Routing," IETF Mobile Ad Hoc Networks Working Group, IETF RFC
3561.
[6] C. E. Perkins and P. Bhagwat, \Highly dynamic destination-sequenced distance-
vector routing (DSDV) for mobile computers". In Proceedings of the ACM Spe-
cial Interest Groupon Data Communications (SIGCOMM), August 1994, pages
234-244.
[7] D. B. Johnson, D. A. Maltz, and Y-C Hu, \The Dynamic Source Routing Pro-
tocol for Mobile Ad Hoc Networks (DSR)," IETF Mobile Ad Hoc Networks
Working Group, Internet Draft, work in progress, 24 February 2003.
[8] J. Zhao, H. Zheng, G.-H. Yang, \Distributed coordination in dynamic spectrum
allocation networks," in: Proc. IEEE DySPAN 2005, pp. 259-268, November
2005.
[9] K. Bian and J.-M. Park, \MAC-layer misbehaviors in multi-hop cognitive ra-
dio networks," 2006 US - Korea Conference on Science, Technology, and En-
trepreneurship (UKC2006), Aug. 2006.
[10] Hao Nan, Sang-jo Yoo and Tae-In Hyon, \Distributed Coordinated Spectrum
Sharing MAC Protocol for Cognitive Radio," IEEE International Symposium on
New Frontiers in Dynamic Spectrum Access Networks, pp. 240249, April 2007.
42
[11] S. Krishnamurthy, M. Thoppian, S. Venkatesan, and R. Prakash, \Control
Channel-based MAC-layer Conflguration, Routing and Situation Awareness for
Cognitive Radio Networks," in: MILCOM 2005, Atlantic City, NJ, October 2005.
[12] C. M. Cordeiro and K. Challapali, \C-MAC: A Cognitive MAC Protocol for
Multi-Channel Wireless Networks," in IEEE Symposium on New Frontiers in
Dynamic Spectrum Access Networks, April 2007.
[13] S.-L. Wu , C.-Y Lin , Y.-C. Tseng , J.-P. Sheu, \A New Multi-Channel MAC
Protocol with On-Demand Channel Assignment for Multi-Hop Mobile Ad Hoc
Networks," Proceedings of the 2000 International Symposium on Parallel Archi-
tectures, Algorithms and Networks (ISPAN ?00), p.232, December 07-07, 2000.
[14] Thoppian, M.; Venkatesan, S.; Prakash, R.; Chandrasekaran, R., \MAClayer
scheduling in cognitive radio based multihop wireless networks," World of Wire-
less, Mobile and Multimedia Networks, 2006.
[15] Q. Zhao, L. Tong, and A. Swami, \Decentralized cognitive MAC for dynamic
spectrum access," in Proc. of IEEE Symposium on New Frontiers in Dynamic
Spectrum Access Networks, Nov. 2005.
[16] Q. Zhao, L. Tong, A. Swami, and Y. Chen, \Decentralized Cognitive MAC for
Opportunistic Spectrum Access in Ad Hoc Networks: A POMDP Framework",
submitted to IEEE Journal on Selected Areas in Communications, February,
2006.
[17] Pradeep Kyasanur , Nitin H. Vaidya, \Selflsh MAC Layer Misbehavior in Wire-
less Networks," IEEE Transactions on Mobile Computing, v.4 n.5, p.502-516,
September 2005.
[18] Q. Zhao, L. Tong, and A. Swami, \A Cross-Layer Approach to Cognitive MAC
for Spectrum Agility," in Proc. of Asilomar Conference on Signals, Systems, and
Computers, Nov. 2005.
[19] Athanassios V. Adamis, Konstantinos N. Maliatsos, Philip Constantinou, \A
New MAC Protocol with Control Channel Auto-Discovery for Self-Deployed Cog-
nitive Radio Networks," in Program for European Wireless 2007.
[20] Y. Kondareddy and P. Agrawal, \Synchronized MAC Protocol for Multi-Hop
Cogintive Radio Networks," IEEE ICC, Beijing, China, May 2008.
[21] Pradeep Kyasanur, Nitin H. Vaidya, \Protocol Design Challenges for Multi-hop
Dynamic spectrum Access Networks," Proc. IEEE DySPAN 2005, November
2005, pp. 645- 648.
43
[22] Bing Qi, Saad Biaz, Shaoen Wu, Yiming Ji, \An interference-aware routing
metric in multi-radio multi-hop networks," ACM Southeast Regional Conference
2007: 549-500.
[23] Chunsheng Xin, Bo Xie, Chien-Chung Shen, \A novel layered graph model for
dynamic spectrum access networks," Proc. IEEE DySPAN 2005, November 2005,
pp. 308-317.
[24] L. De Nardis and M.-G. Di Benedetto, \Cognitive routing in UWB networks," in-
vited paper at the IEEE International Conference on UWB 2006 (ICUWB2006),
September 24 - 27 2006.
[25] Dipankar Raychaudhuri and Xiangpeng Jing, \A spectrum etiquette protocol
for e?cient coordination of radio devices in unlicensed bands," in: 14th IEEE
PIMRC2003, September 2003.
[26] P. Pawelczak, R.V. Prasad, Xia Liang, I.G.M.M. Niemegeers, \Cognitive radio
emergency networks - requirements and design," Proc. DySPAN, Nov. 2005, pp.
601- 606.
[27] Srinivasan Krishnamurthy,Mansi Thoppian, Srikant Kuppa, R. Chandrasekaran,
S. Venkatesan, Neeraj Mittal and Ravi PrakashM, \Time-e?cient layer-2 auto-
conflguration for cognitive radios," In IASTED International Conference on Par-
allel and Distributed Computing and Systems (PDCS), pages 459-464,November
2005.
44