, ; z.
21512.4}
I1}.3 Vvllv.
.
E.
. _

.1};
.. .

. (v?!-
J..r... .1.

 

.m-

qh-{wnw-Qtfl'r‘

on:

. 22A. ..

“4...,

u"

m
‘
,
.
a

 

 

TEES“

 

 

Michiga... State
University

 

 

 

This is to certify that the
thesis entitled

A LOCALIZED AND DISTRIBUTED CHANNEL ASSIGNMENT
FRAMEWORK FOR COGNITIVE RADIO NETWORKS

presented by

Anthony Tyrone Plummer Jr.

has been accepted towards fulfillment
of the requirements for the

Master of degree in Electrical and Computer
Science Engineering

 

 

Major Professor’s Signature
127/0 5709—
, -

Date

MSU is an aflinnatlve—actfon, equal-opportunity employer

. -—-—-—--c—v ..

qc-I-l-o-I-I-D-O-I-I-I-0-t---o-n-o-a-n-n-.~..—

PLACE IN RETURN BOX to remove this checkout from your record.
To AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DATE DUE

DATE DUE

DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6/07 p:/CIRC/DateDue.indd-p.1

u—_———

A LOCALIZED AND DISTRIBUTED CHANNEL ASSIGNMENT
FRAMEWORK FOR COGNITIVE RADIO NETWORKS

By

Anthony Tyrone Plummer Jr.

A THESIS
Submitted to
Michigan State University

in partial fulfillment of the requirements
for the degree of

MASTERS OF SCIENCE
Electrical and Computer Engineering

2007

ABSTRACT

A LOCALIZED AND DISTRIBUTED CHANNEL ASSIGNMENT
FRAMEWORK FOR COGNITIVE RADIO NETWORKS

By

Anthony Tyrone Plummer Jr.

Cognitive radio (CR) technology allows the observation of the network conditions
to dynamically discover available and underutilized spectrum. A cognitive network is the
framework that uses the CR to take advantage of underutilized spectrum. The availability
of using multiple interfaces and channels with cognitive radio abilities in wireless devices
is expected to alleviate the capacity limitations that exist in traditional single channel
wireless mesh networks.

Although having multiple radio interfaces and available channels can generally
increase the effective throughput, a problem arises as to what is the best strategy to
dynamically assign available channels to multiple radio interfaces for maximizing
effective network throughput by minimizing the interference. This thesis presents a
distributed and localized interference-aware channel assignment framework for multi-
radio wireless mesh networks in a cognitive network environment. The proposed
framework uses a novel interference estimation method by utilizing distributed conflict
graphs at each network interface to model the interference. Extensive simulation studies
in 802.11 based multi-radio mesh networks have been performed. The results indicate
that for both local and multi-hop traffic, the proposed protocol can facilitate a large
increase in network throughput in comparison with a Common and Centralized Channel

Assignment mechanisms that is used as a benchmark in the literature.

Copyright by
Anthony Tyrone Plummer Jr.

2007

To My Parents
For All Their

Love and Support

iv

Acknowledgements

I would like to thank my advisor Dr. Subir Biswas for supporting me through my
work. His guidance allowed me to flourish during my time graduate school. I would also
like to thank my committee Dr. Matt Mutka and Dr. Tongtong Li for their time and
support. I would also like to thank Dr. Abdol—Hossein Esfahanian for assisting me on
understanding graph theory concepts. I would also like to thank the CSE department for
providing the HPCC for allowing me to reduce simulation time greatly.

I would also like to thank Dr. Percy Pierre and Dr. Barbara O’kelly for their
guidance and support in helping me attend and be successful in graduate school.

Thanks must be given to my lab mates Tao, Fan and Jayanthi for all of the
brainstorming and implementation discussions. Last but not least, I would like give
thanks to Raenita Fenner and Dr. Uche Wejinya along with the rest of my friends for

supporting me through this process.

TABLE OF CONTENTS

List of Tables ....................................................................................... viii
List of Figures ....................................................................................... ix
Chapter 1: Introduction ................................................................................................... l
1.] Cognitive Networks ............................................................................................ 1

1.2 Traditional Networks vs. Cognitive Networks ................................................... 2

1.3 Fixed Spectrum Policy Effects ............................................................................ 3

1.4 Spectrum Opportunities and Cognitive Radio .................................................... 4

1.5 Applications of Cognitive Networks ................................................................... 6
1.5.1 Military Applications ................................................................................ 6

1.5.2 Emergency Applications ........................................................................... 7

1.5.3 Other Applications .................................................................................... 7

1.6 Research Issues and Limitations of Cognitive Networks ................................... 7
1.6.1 Detection of Primary Users ...................................................................... 8

1.6.2 Channel Assignment Issues ...................................................................... 8

1.6.3 Cognitive Network Routing ...................................................................... 9

1.6.4 Representation of Information .................................................................. 9

1.6.5 Security ..................................................................................................... 9

1.6.6 Hardware Limitations and Design Concerns .......................................... 10

1.7 Research Issues Addressed in this Thesis ......................................................... 10
Chapter 2: Related Work ............................................................................................... 12
2.1 Centralized vs. Distributed Protocols ................................................................ 12
2.1.1 Centralized Protocols .............................................................................. 12

2.1.2 Distributed Protocols .............................................................................. 15

2.2 Coupled or Decoupled Design .......................................................................... 17

2.3 Primary and Secondary Users ........................................................................... 19
Chapter 3: CoSAP Framework ...................................................................................... 20
3.1 Motivation ......................................................................................................... 20

3.2 Problem Formation ........................................................................................... 21
3.2.1 Network Model ....................................................................................... 21

3.2.2 Conflict Graph ........................................................................................ 22

3.2.3 Channel-to-Interface Assignment Problem ............................................ 23

3.3 CoSAP Architectural View ............................................................................... 24

3.4 Neighbor Discovery .......................................................................................... 26

3.5 Distributed Channel Assignment ...................................................................... 28
3.5.1 Assignment Initiation ............................................................................. 28

3.5.2 Computing Useable Channel Set (UCS) ................................................ 28

3.5.3 Constructing Local Channel Set (LCS) .................................................. 30

3.5.4 Conflict Graph Computation .................................................................. 31

vi

3.6 Channel Selection ............................................................................................. 32

3.7 Reassignment for Connectivity Maintenance ................................................... 35

3.8 Channel Coordination Protocol ......................................................................... 36

3.9 Primary Network Considerations ...................................................................... 38
Chapter 4: Centralized Channel Assignment Algorithm ............................................... 40
4.1 Centralized Advantages .................................................................................... 40

4.2 Centralized Protocol .......................................................................................... 41

4.3 Primary Network Considerations ...................................................................... 43
Chapter 5: Experimental Setup ..................................................................................... 45
5.1 Multiple Channel, Multiple Interface Extension ............................................... 45

5.2 Ns-2 CoSAP Extension ..................................................................................... 48
Chapter 6: Performance of CoSAP with Homogeneous Spectrum Opportunity .......... 50
6.1 Simulation Setup ............................................................................................... 50

6.2 One-hop UDP Throughput ................................................................................ 51

6.3 Multi-hop TCP Throughput .............................................................................. 55

6.4 Comparison with Centralized Channel Assignment Algorithm ....................... 59

6.5 Algorithmic Performance .................................................................................. 63

6.6 Connectivity Maintenance ................................................................................ 67

6.7 Scalability of CoSAP: ....................................................................................... 70
Chapter 7: Perfomrance of CoSAP with Heterogeneous Spectrum Opportunity ......... 72
7.1 Primary users ..................................................................................................... 72

7.2 Primary User Effects ......................................................................................... 73

7.3 Different Primary Users Types Simulations ..................................................... 78
7.3.1 Random Access Points Case ................................................................... 79

7.3.2 Smart Access Points Case ....................................................................... 82

7.3.3 Mesh Network Case ................................................................................ 84

7.3.4 Comparison of Primary User Cases ........................................................ 87

Chapter 8: Conclusions ................................................................................................. 89
8.1 Conclusions ....................................................................................................... 89

8.2 Future Work ...................................................................................................... 90
Chapter9: Appendix” . 9.1
9.1 Homogeneous UDP Simulations ...................................................................... 91

9. 2 TCP Experiments .............................................................................................. 96
Bibliography .. .................................................................................................................. 99

vii

LIST OF TABLES

Table 3-1: Hello Tuple Contents .............................................................................. 27
Table 7-1: Average Amount of Secondary Nodes Affected by a Primary Node ..... 74
Table 7-2: Primary users TCP simulation setup ...................................................... 79

viii

LIST OF FIGURES

Figure 1-1: Spectrum opportunities (adapted from [6]) ............................................. 5
Figure 2-1: Coupled and Decoupled Design (adapted from [18]) ........................... 18
Figure 3-1: Cognitive Network ................................................................................ 21
Figure 3-2: Conflict graph of a sample network ...................................................... 23
Figure 3-3: Architectural components of CoSAP .................................................... 25
Figure 3-4: Sample UCS .......................................................................................... 30
Figure 3-5: Channel Assignment Algorithm in CoSAP ............................................. 1
Figure 3-6: Channel Assignment Algorithm in CoSAP (Continued) ........................ 1
Figure 3-7: Protocol components of a link establishment cycle .............................. 36
Figure 4-1: Sample topology to explain interface constraint ................................... 41
Figure 4-2: Sample topology to explain channel flexibility .................................... 42
Figure 5-1: Original Node Architecture [27] ........................................................... 46
Figure 5-2: Multiple Channel Multiple Interface Extension [26] ............................ 47
Figure 5-3: CoSAP Extension [27] .......................................................................... 49
Figure 6-1: 1-hop throughput with 2 interfaces per node (degree 4) ....................... 52
Figure 6—2: Packet Delivery Delay for 1-hop traffic (degree 4) .............................. 53
Figure 6-3: l-hop throughput with 3 interfaces per node (degree 4) ....................... 54
Figure 6-4: Packet Delivery Delay for l-hop traffic (degree 4) .............................. 55
Figure 6-5: Throughput improvement with 2 interfaces for peer-to-peer model ..... 56
Figure 6-6: Throughput improvement with 2 interfaces for gateway model ........... 57
Figure 6—7: TCP throughput improvement with 3 interfaces for P2P model ........... 58
Figure 6-8: Throughput improvement with 3 interfaces for gateway model ........... 58

ix

Figure 6-9: Centralized sparse load comparison (2 interfaces) ................................ 60

Figure 6-10: Centralized sparse load comparison (3 interfaces) .............................. 61
Figure 6-11: Centralized dense load comparison (2 interfaces) .............................. 62
Figure 6-12: Centralized dense load comparison (3 interfaces) .............................. 62
Figure 6-13: Fractional network interference for 2 interfaces ................................. 64
Figure 6-14: Fractional network interference for 3 interfaces ................................. 65
Figure 6-15: Maximum concurrent transmissions for 2 interfaces .......................... 66
Figure 6-16: Maximum concurrent transmissions for 3 interfaces .......................... 66
Figure 617: Percentage of links assigned for 3 interfaced nodes ........................... 69
Figure 6-18: Percentage of links assigned for 2 interfaced nodes ........................... 69
Figure 6-19: Convergence characteristics of CoSAP .............................................. 71
Figure 7-1: Percentage of affected secondary users (1 interface) ............................ 75
Figure 7-2: Percentage of affected secondary users (2 interfaces) .......................... 75
Figure 7-3: Average amount of channels lost by secondary users (1 interface) ...... 77

Figure 7-4: Average amount of channels lost by secondary users (2 interfaces) ....77

Figure 7-5: Random Access Point Case ................................................................... 80
Figure 7-6: RAP case TCP results (1 interface primary) ......................................... 81
Figure 7-7: RAP case TCP results (2 interface primary) ......................................... 81
Figure 7-8: Smart Access Point Case ....................................................................... 82
Figure 7-9: SAP case TCP results (1 interface primary) ......................................... 83
Figure 7-10: SAP case TCP results (2 interface primary) ....................................... 84
Figure 7-11: Mesh Network Case ............................................................................ 85
Figure 7-12: Mesh network case TCP results (1 interface primary) ........................ 86

X

Figure 7-13: Mesh network case TCP results (2 interface primary) ........................ 86

Figure 7- 14: Comparison of primary user types (1 interface primary) .................... 88
Figure 7-15: Comparison of primary user types (2 interfaced primaries) ............... 88
Figure 9-1: l-hop throughput with 2 interfaces per node (degree 5) ....................... 91
Figure 9-2: Packet Delivery Delay for 1-hop traffic (degree 5) .............................. 92
Figure 9-3: l-hop throughput with 3 interfaces per node (degree 5) ....................... 92
Figure 9-4: Packet Delivery Delay for l-hop traffic (degree 5) .............................. 93
Figure 9-5: l-hop throughput with 2 interfaces per node (degree 7) ....................... 93
Figure 9-6: Packet Delivery Delay for l-hop traffic (degree 7) .............................. 94
Figure 9—7: l-hop throughput with 3 interfaces per node (degree 7) ....................... 94
Figure 9-8: Packet Delivery Delay for l-hop traffic (degree 7) .............................. 95
Figure 9-9: Percentage increase with 2 interfaces over CCA (degree 4) ................. 96
Figure 9-10: Percentage increase with 3 interfaces over CCA (degree 4) ............... 97
Figure 9-11: Percentage increase with 2 interfaces over CCA (degree 5) ............... 97
Figure 9-12: Percentage increase with 3 interfaces over CCA (degree 5) ............... 98

xi

Chapter 1: Introduction

Wireless network applications have increased dramatically over the last decade.
Many wireless standards have been introduced during this period including Wifi, Ultra
Wide Band (UW B), Bluetooth, and WiMax. Increased usage of these applications is
encouraged by technology advocates, but a limiting factor of these applications is that
they must coexist within a fixed amount of spectrum. This creates a spectrum
underutilization problem which can be defined as the inefficient reuse of the available
physical spectrum within a particular environment. A main source of limited spectrum
arises from the traditional wireless network hardware that is used to support these
applications. In traditional wireless hardware predetermined analog operating parameters
are utilized to assign the spectrum to facilitate the operation of these applications. With
an increased saturation of wireless devices, the fixed spectrum usage strategy has been
shown to strain the available spectrum. This strain of available spectrum is not because of
a physical limitation of usable spectrum, it is conversely the result of inefficient
partitioning of the spectrum space. There have been studies [1] that have verified large

underutilization of spectrum.

1.1 Cognitive Networks

To better utilize available spectrum, suggestions have been given to design network
hardware and protocols that are able to adapt to the environment. A network that can
dynamically adapt to the environment and use the available spectrum effectively will
alleviate the spectrum limitation problem. These smart and adaptive networks have been

generally known as cognitive networks. A cognitive network has been defined as a

l

cognitive process that can perceive current network conditions, and then plan, decide and
perform actions based on those conditions. The network can learn from these adaptations
and use them to make future decisions, all while taking into account end to-end goals [2].
Network operators and networks user’s perspectives end-to-end goals should also be
taken into account. Dynamic and intelligent switching of frequencies at a radio interface
requires the use of many technologies namely a software defined radio, signal-processing
and machine-learning procedures. In addition, dynamic and intelligent cross-layer design

of the network stack is needed to implement a cognitive network.

1.2 Traditional Networks vs. Cognitive Networks

The design and operation of cognitive networks differs in a number of ways than
that of a traditional network. Differences are usually realized through the adaptive
characteristics, including the ability to react to network stimuli, of a cognitive network.
An excellent example of the adaptive characteristics of a cognitive network is the
cognitive radio. A key difference between traditional radios and cognitive radios is the
ability for the cognitive radio to sense the radio environment and dynamically switch to a
particular frequency. Traditional radios are typically assigned a specific set of frequencies
that are shared among its users. IEEE 802.11b has 11 channels in the 2.4 GHz spectrum,
3 of which are orthogonal, and IEEE 802.11a has 13 orthogonal channels in the 5 GHz
spectrum [3]. Using only the set of predetermined channels the radios of wireless devices
are assigned channels to facilitate communication. This assignment of channels could be
preconfigured or dynamically assigned through protocols. An issue with this type of
channel selection is the limitation of only using the predetermined channels. If all of the
channels experience heavy interference then the network performance can be degraded.

2

On the other hand a cognitive radio would have the ability to adapt to the situation
through sensing the environment and detecting “better” channels that can be used for
communication.

Another important difference between cognitive and traditional networks is the
network layer stack design. Traditionally, networks are designed using the layered
protocol model, where each layer performs its function independently. An issue with the
layered protocol model design is that each layer can only respond to network conditions
with which it has visibility. This situation means that problems or adjustments usually
can only be made within the scope of the particular layer. These modular modifications at
each individual layer may not lead to the best possible network performance.
Alternatively, cognitive networks are envisioned as having a highly cross layer design,
especially at the lower layers. Using network conditions as seen from of multiple layers,

protocols can be designed to fully explore the best performance in an end to end fashion.

1.3 Fixed Spectrum Policy Effects

Traditional hardware limitations are not the only cause of the spectrum usage
problem. Today’s wireless access networks are regulated by fixed spectrum assignment
policies. Government organizations strategically dispense spectrum use based on
geographical areas and various license holders. Additionally, a broad section of the
spectrum is allocated for free access of unlicensed users. With this static allocation, parts
of the licensed spectrums can remain idle when its primary users do not have enough
traffic. For example, the US. Navy Maritime has a specific frequency dedicated for its
communications. Use of devices in land-lock locations will most likely not interfere with
the Navy’s frequency allocations but because of the fixed spectrum policy these

3

frequencies cannot be utilized. The Federal Communications Commission (FCC) [4]
estimates that the average channel occupancy of the licensed spectrum bands can is
typically less than 15%. Additional studies have shown that when portions of the radio
spectrum are examined in urban areas the following can be observed [5]:

1. some frequency bands are largely unoccupied most of the time

2. some other frequency bands are moderately occupied

3. the remaining frequency bands are heavily utilized.

Using a fixed spectrum policy was sufficient in the past for the reason that the
amount of users of spectrum was minimal. In contrast with the increasing disparity in
utilization between the licensed and unlicensed bands along with the proliferation of new
low-cost radio technologies and commodity oriented services, certain unlicensed bands
are on the verge of getting saturated. With these usage trends, it is desirable to introduce
dynamic channel allocation strategies so that the unused segments of a licensed band by

its primary users can be used by unlicensed secondary users.

1.4 Spectrum Opportunities and Cognitive Radio

Issues with spectrum underutilization have lead to the concept of spectrum holes.
Spectrum holes have been defined as a band of frequencies assigned to a licensed user,
but, at a particular time and specific geographic location when the band is not being
utilized by that user [5]. A licensed user or primary user (which will be referred to for the
duration on the thesis) is defined as an entity that has a high priority in a given frequency
band. For example a primary user can be a cell phone provider, TV station, or emergency
services. The primary user has the rights to this spectrum because the primary has
exclusive usage of the spectrum. Primary users may be aware of unlicensed users aware,

4

but they are typically unaware. Spectrum holes appear as useable channels to unlicensed
users with respect to the licensed band in question. An unlicensed user or secondary user
is an entity that can benefit from unused spectrum opportunistically, but departs when a
primary user begins to transmit. For a secondary user, given its locations, a set of
spectrum holes can be available at a given time. Such a set of available channels are
referred to as the spectrum opportunity (SOP) of the secondary user. Note that there will
be no change in the primary users’ architecture in the existence of secondary users. As
shown in Figure 1-1, spectrum holes can appear temporally, in frequency, power and
other parameters. The secondary user can dynamically select and use these SOPs for its

own communication.

 

Frequency
A Power Primary Users
...v' 4 ,

 

    

 

 

 

"Secondary Usef"

 

Figure l- 1: Spectrum opportunities (adapted from [6])

In order to leverage those SOPs or holes for enhancing the effective network
throughput, as perceived by the secondary users, it is necessary to develop mechanisms
for dynamic spectrum opportunity/channel assignment to the secondary users’ interfaces.
Cognitive Radio is the technology that enables a radio interface to change its transmitter

parameters based on sensing and interaction with the environment in which it operates.
5

The cognitive radio is the basis for the cognitive network. A cognitive radio, for example,
can sense the available spectrum opportunities and their corresponding interference, and
offer a set of suitable channels (spectrum holes). Afterwards using this information a

cognitive layer can analyze and decide what best strategy to maximize throughput

1.5 Applications of Cognitive Networks

The greatest advantage of the cognitive networks is its reconfigurability and
adaptability to environment stimuli. As a result there are many applications that this

technology has already infiltrated and will penetrate in the future.

1.5.1 Military Applications

Cognitive networks have garnered heavy interest for use in military applications.
The adaptability of the cognitive network in different network environments especially is
attractive. When the military enters various international environments with the goal of
setting up wireless networks, there are local issues that will have to be resolved. Local
governments and policy makers may have regulated spectrum in dissimilar ways to what
the military systems are preconfigured. There may be unavoidable interference to military
networks because of the sharing of the local spectrum. Cognitive networks would be able
to detect and select the best channels for communications in an unknown environment.

Taking the cognition higher than the lower layers and looking at the cognitive
network as an entire system, [7] discusses cognitive networks as having the ability to be
mission aware. The network should be able to understand what the objective of an
application is, and vice versa an application should be able to understand what the

network is capable of doing at any given moment. The network can learn application

requirements and dynamically choose the network protocols that will meet those

requirements.

1.5.2 Emergency Applications

Cognitive networks can provide large improvements in the capabilities of
emergency network applications. For example in the after effects of a devastating
hurricane some parts of the communication infrastructure could become damaged, but
emergency service workers will still need to communicate effectively. Emergency
personnel working in the disaster site must know exact positions of each other for
efficient coordination of rescue operations. In another example, if there is an emergency
in a chemical factory, each worker must be advised immediately about leakages through a
network capable of multicasting information reliably [8]. The cognitive network would
be able to self organize in these emergency situations to setup the necessary

communications systems.

1.5.3 Other Applications

An advantage of a cognitive network is that it is typically an ad-hoc network. This
leads to its possible use in extreme applications. One such application is underground
communications. The network would be able to self configure itself even in environments

without any predetermined infrastructure.

1.6 Research Issues and Limitations of Cognitive Networks

With all of the discussions about cognitive networks, the technology is still in the

infancy stage. There are a large amount of issues and research that focus on the topic.

1.6.1 Detection of Primary Users

The discovery or detection of primary users remains a heavily researched topic. A
fundamental goal of the cognitive network is to not interfere with existing legacy
networks, representing primary users. When a primary user starts to use a particular
frequency, secondary users must vacate that frequency. This requires secondary users to
continually sense and detect primary user existence. Every primary user does not have the
same characteristics, requiring different sensitivity and rate of sensing for detection. As
an example, a GPS (global positioning system) receiver typical receive power is
-127.5 dBm, while a Bluetooth receiver is at 20 dBm. Another issue is that the primary
user typically will not cooperate with the secondary users. Therefore, the secondary user
must rely on local sensing information which can be affected by environmental factors
including the hidden terminal problem, shadowing, and path loss [5]. The detection of a
primary user demands a continuous period of sensing. Primary users may go into and out
of the environment, leading to a change in the availability of spectrum. This may require

having alternate choices depending on the current situation.

1.6.2 Channel Assignment Issues

The cognitive radio purpose is to discover available spectrum, more specifically
channels, for use in communications. Once these usable channels are found they must be
assigned to the radio interfaces of hardware devices. Hardware devices can be equipped
with single or multiple interfaces. In the single interface case different channels will have
to be assigned over the time. In the multiple interface case channels must be assigned to
each interface. Effective channel assignment should aid in attaining the best performance

of the network.

1.6.3 Cognitive Network Routing

In a cognitive network, the dynamic nature can create numerous problems with
routing data through the network. There is no guarantee that a channel will be available
for use for the entire communication duration between two nodes. There are many
reasons why a path between two nodes can be affected. Along with the traditional path
breakage problems, channels can become unavailable due to the retum of primary user or
increased congestion from other secondary users. Traditional. routing protocols may not
be sufficient. For example, if a channel becomes unavailable on a path, that link will be
considered broken and all the packets for that link will be dropped. There are even cases
where the network can become disjoint as a result of a primary user entrance. Therefore,
it is important to consider how frequently a channel becomes unavailable on a link while

computing the path between source and destination nodes.

1.6.4 Representation of Information

Cognitive networks have the notion of being a smart, dynamic, evolving
technology. This requires an idea of intelligence in the machines that are to implement
cognitive networks. New languages that can capture the necessary logic may need to be
developed. The Web Ontology Language (OWL) [9], for example, allows both first-order

logic, and higher-order, class-based reasoning.

1.6.5 Security

The cognitive network may be vulnerable to malicious users because of the
inherent flexibility of the design. This issue must also be addressed in the design of the

cognitive network.

1.6.6 Hardware Limitations and Design Concerns

The cognitive network requires the use of advanced radios. The cognitive radio is
typically thought to have the ability to listen to a wide range of frequencies. Thus the
radio hardware must be capable of sensing the spectrum in a wide frequency band.
Because of this requirement, cognitive radios will require efficient power control and
high capacity power sources which could be cost prohibitive. Intuitively, the cognitive
network will be more complex than traditional networks, but attention must be given to
the actual implementation of the system in real hardware. Additionally the system must
be able to scale. For example, some application may require the use of many cooperating

cognitive devices increasing the need of the system scalability.

1.7 Research Issues Addressed in this Thesis

The operation of the cognitive network involves the detection of available channels
open for communication. Once these channels are known the decision of how to utilize
these channels to maximize network throughput, arises. Some current and future
hardware will have the benefit of utilizing multiple interfaces that can be assigned to
multiple channels. Unlike single interface networks, multiple interfaced nodes must be
assigned to specific channels to enable communication. The Cognitive Spectrum
Allocation Protocol (CoSAP) takes advantage of this hardware to perform a fully
distributed and localized channel allocation strategy. Each node uses collaborative
sensing through exchanging information with its l-hop neighbors to learn about its m-hOp
neighborhood. A node broadcasts hello messages containing information [available
channels, interface count, current channel-to-interface assignment] about up to its m-hop

neighbors. A node receiving this information can create the connectivity graph, and a

10

conflict graph for each channel in its m-hop neighborhood. This graph information is then
used by the node for channel-to-interface assignments with minimized interference for its
links. The mechanism is localized because a node relies on information only from its
local m-hop neighborhood, and it is distributed because each node computes its own
version of the neighborhood conflict graph and channel-to-interface allocation for its own
radio interfaces.

As mentioned in the discussion of cognitive networks in Section 1.4, within the same
network secondary users must coexist with the primary users, with respect to the sharing
of spectrum. CoSAP is designed to perform the channel assignment for secondary users
that minimizes or eliminates any interference that secondary users may cause on the
primary network while maintaining a usable network for the secondary users. CoSAP
supports heterogeneous SOPs which are representative of the diversity of the SOP from
the secondary users’ point of view as a result of primary users’ selection of channels. A
centralized protocol is also implemented to determine performance benchmarking. To
properly evaluate the protocol performance, simulation models are utilized; these

simulations include access point networks and mesh networks representing primary users.

11

Chapter 2: Related Work

This chapter provides a literature review of the channel assignment protocols
related to cognitive networks. There are many design decisions that must be made as to

the type of protocol that would be best served for cognitive networks.

2.1 Centralized vs. Distributed Protocols

Wireless network protocols generally are considered centralized or distributed. A
centralized protocol commonly requires a central node or a few nodes that will perform
some or most of the calculations and decisions for all nodes in the network. The central
node or nodes has visibility to the entire network, which allows for performing
calculations with the most information. This can lead to a heterogeneous deployment of
the nodes (hardware) in the network, because nodes would run different protocols. On the
other hand a distributed protocol has homogeneous nodes, where nodes perform the same
tasks. As a result the nodes in the distributed case may not have all of the information

about the network.

2.1.1 Centralized Protocols

For the centralized case, nodes in the network will send information about their
current status to the central node periodically. The type of data that is sent is relative to
the requirements of a given protocol. In a centralized topology control network protocol
like CONNECT [10], power levels of each node in the network are computed by a central
node. The purpose of using power control is typically to reduce inference between nodes
or decrease nodal energy usage, therefore increasing throughput. In a real world

implementation of this type of protocol the central node will need to gather information
12

from every node in the network. This is accomplished with packets containing
information about the nodes current status. In the topology control case the current
location of the node information is gathered. After the central node receives all the
information from all the nodes it will perform the necessary calculations. The results of
these calculations are sent back to all of the other nodes in the network.

Centralized channel assignment algorithms rely on a central spectrum server [11,
12] which collects channel and radio information periodically. A spectrum server role can
be realized in many fashions. The direct assignment of all radios in a network based on
an interference estimation scheme has been proposed. Another example is the
management of a direct pricing or competitive spectrum allocation scheme. Issues of
spectrum fairness can also be address by a spectrum server. Nonetheless the primary goal
of the spectrum server is to perform an optimal channel assignment to maximize network
throughput.

CLICA [13], is an example of centralized multiple channel assignment algorithm.
The authors formulate the channel assignment problem as a topology control problem. As
mentioned earlier, a goal of topology control is to reduce interference. As with most
wireless network protocols the measurement of interference or factors that are a function
of interference, such as packet loss rates or RTI‘, is important. CLICA estimates
interference using the Protocol Model [14], which characterizes the interference between
nodes in a given channel. Using the interference range for each node, this is usually
larger that the transmission range, the interference that is created between nodes
transmissions is defined. Based on 802.11 RTS/CTS mechanism the transmission must be

successful to and from a receiver. Given two nodes i and j a with interference range R, a

13

transmission from i to j is successful if no other nodes transmit at the same time within a
distance R from i or j. Using this model a weighted conflict graph, which represents the
interference between nodes, is created for every channel. An objective function is run on
these graphs to determine the best channel to use for a given link in the network.

Connectivity maintenance is an important feature of a channel assignment protocol.
In a single interface, single channel network when a node sends data it will be received
by another node within its transmission range barring any interference. This is not
guaranteed in a multiple channel network because at least one interface on each node
involved in a transmission must be set to the same channel. Without the assurance of
maintaining the original connectivity possible connections between nodes can be lost and
the network can become disconnected. In addition, the number of hops to reach nodes in
the network can be increased. Most centralized channel assignment protocols guarantee
connectivity maintenance because they have complete information about the nodes in the
network. This can be an issue for distributed protocols.

CLICA algorithm bases the assignment of a channel to a link on the priority of
nodes in the network. Initially, all nodes are given a priority which can be randomly
chosen or by a specific metric. CLICA first begins by assigning radios of the nodes with
higher priority. As radios are assigned a channel, the flexibility of node assignment then
decreases. Thus, there is a risk of losing connectivity maintenance. To ensure this
situation is not realized the priority of nodes with constrained interfaces are increased,
therefore their radio assignments receives a higher precedence. A greater detail of this

algorithm is provided in Chapter 4.

l4

Another centralized channel assignment protocol BSF-CA [15] also attempts to
assign channels to minimize radio interference. The protocol proposes the use of a CAS
(Central Assignment Server) to perform the channel assignment for all nodes in the
network For interference estimation, each node in the network tries to capture a packet
on every channel for a short duration. Afterwards the node gives a rank to each channel
using the gathered results. This information is sent by every node to the CAS. The CAS
creates a multi-radio conflict graph that using the information from the nodes in the
network. The weights of the links in the conflict graph are the average of rankings from
both nodes on a particular link. One conflict graph is created a heuristic breadth first
search strategy is used for assigning channels to radio interfaces.

The centralized allocation approach provides the benefit of full network
knowledge, allowing for possibly the most efficient protocol design and performance. A
notable limitation of these centralized approaches is that all network information is
required to be sent to a spectrum server, and propagate the allocation information back to
individual nodes after the allocation is done. This incurs a high overhead, especially in
large networks. In addition, during the process of updating the network with channel
assignments conditions may change in certain areas of the network. In dynamic spectrum
environment, those algorithms would not scale well. Our proposed CoSAP framework
addresses this scalability problem by adopting a distributed and localized strategy of

channel assignment.

2.1.2 Distributed Protocols

Distributed channel assignment protocols have the advantage over centralized
protocols with the ability to react quickly to changes. With the lack of a central entity to

15

perform the channel assignment for the network, only nodes within the affected area can
adjust to a modification in the network. For example, given five nodes, located an
average of five hops away from the spectrum server. Unexpectedly, the nodes channel
availability changes. The nodes will have to send the information about the change to the
spectrum server, wait for the spectrum server to calculate a new channel assignment and
send that assignment back to the nodes. Conversely, in a distributed protocol neighboring
nodes would communicate to resolve the situation therefore allowing the problem to be
handled locally and not propagate throughout the network.

The algorithm in [16] deals with a specific traffic model for mesh networks to
Internet access gateways. Information and channel assignments are exchanged between
nodes within (k-l-l) hops, where k is the ratio between interference and communication
ranges (typically between 2 and 3). Each node calculates a channel usage metric and
shares this information with its neighbors. Using the gathered information nodes will
calculate an aggregate traffic load for each channel. The channels with the lowest traffic
loads are assigned to their interfaces. Another protocol in [17] provides a distributed self-
stabilizing channel assignment for peer to peer traffic. Relying only on local information,
each node continually tries to determine the channel that will minimize the additive
interference cost between the nodes within its interference range. The nodes stops
changing its channel when a previous choice is minimizes the sum of interference. Using
this protocol, however, each node relies only on one-hop information for interference
estimation during the channel assignment process. In the proposed CoSAP, on the other
hand, a node relies on information up to m-hops (m > 1), and therefore it is expected to

deliver better network throughput because of superior interference estimation. In

16

addition, due to its distributed nature, the protocol in [17] is not able to guarantee the full
topological connectivity after the channel allocation process is concluded. To address
this, a specific connectivity maintenance phase has been introduced as a part of the

proposed CoSAP framework.

2.2 Coupled or Decoupled Design

A question that arises in the development of channel assignment protocols is should
routing be included in the design of the protocol? Traditionally, the MAC layer uses
spectrum management to connect individual nodes while the routing layer establishes
paths between nodes in the network. The routing protocol will rely on the lower layers
(MAC and PHY) to provide the links that are connecting the nodes in the network.
Contrasting a single channel network where usually there is only one link between two
nodes, multi-channel multi—interface networks can have many links to the same node or
even none at all, as a result of channel assignment. These issues leads to the discussion of
coupled or decoupled designs. A decoupled design is where the MAC layer or a layer
between routing and MAC performs the channel assignments, while the routing layer
continues with its normal operations. On the other hand, a coupled or cross-layer design
integrates routing and channel assignment. Figure 2-1 shows the representation of this

design in the network stack.

17

 

 

 

 

 

 

Routing (Normal) | Routing(Spectrum)

i Link Status II:
Channel Link
M AC Selection Status
‘ Channel MAC
‘ Selection
: l 1

Cognitive Radio Cognitive Radio

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Decoupled Coupled

 

Figure 2-1: Coupled and Decoupled Design (adapted from [18])

The papers [19] and [18] introduce cross-layer channel assignment mechanisms in
which channel assignment and network layer connection routing are performed together.
In [19] a distributed ECA-AODV protocol is introduced that utilizes the routing messages
in AODV [20] to perform channel assignments. During the route discovery phase,
channels are chosen such that there is a diverse selection of channels for the nodes on the
route. Channels are selected to vary channel usage between each node neighbors within
k-hops of a given route. In [18], for a given source node a centralized algorithm finds all
feasible paths along with all possible channel assignments. It then selects the route and
channel assignment that achieves best throughput and schedules a conflict free channel
usage. In most practical deployments, however, it is not likely that the traffic profile
information will be available as a priori, thus limiting the usefulness of the cross-layer
solutions offered in [19] and [18]. Issues of connectivity maintenance and usefulness of
the protocol arises when the number of traffic flows increases in the network. This
problem is the result of the limitations of a fixed number of interfaces for each node in
the network which is a coupled design can fail to address. In the proposed CoSAP
mechanism, a decoupled design is adopted so that the routing layer path computation is

18

completely independent of the channel selection, and no specific assumptions about the

traffic profile are made.

2.3 Primary and Secondary Users

A challenge with cognitive networks is the interaction between the primary users
and secondary users. Within the same network secondary users must coexist with the
primary users, with respect to the sharing of spectrum. The secondary user has the
constraint of not interfering with the channels that are used by the primary users.
Therefore secondary users must select channels that are unoccupied by primary users. A
network with multiple secondary and primary users creates a heterogeneous spectrum
environment. Research into the interactions between the primary and secondary users is
an important topic to the performance and design of cognitive protocols. A theoretical
discussion on the impact of different topologies on a cognitive network is given by
Mahonen [21]. Zhao [22] discusses the assignment of common control channels for the
secondary users in a network with primary users with large transmission ranges. Channel
assignment with fairness considerations is evaluated on a topology with randomly
distributed primary users in [23]. In [24], randomly distributed primary users are also
used for evaluations, however a discussion on the effects of television broadcast stations
on a secondary users is provided. Previous proposed protocols lack evaluation on a

simulation model that a real cognitive network might experience.

19

Chapter 3: CoSAP Framework

In this chapter the Cognitive Spectrum Assignment Protocol (CoSAP) is introduced
and described. CoSAP is a localized and distributed channel assignment protocol for
cognitive networks. It uses a conflict graph based interference estimation to choose

channels that minimizes interference in the network, therefore increasing throughput

3.1 Motivation

A cognitive network invokes the notion that a network will self organize or
configure itself to operate in the particular environment where the network is currently
located. The enabling technology for the cognitive network is the cognitive radio, which
“senses” or measures the radio spectrum to determine available spectrum to use for
communication. The available spectrum can be affected by primary users or
environmental factors. The cognitive radio should provide a list or report of the available
spectrum which could be a function of space, time, power, or frequency. This list can
continually be modified with changes in the sensing environment. Cognitive networks
uses this information in many fashion including creating connectivity for the network,
optimizing network through, ensuring quality of service, ect. Figure 3-1 shows the

cognitive network feedback loop.

20

 

   
  
 

COGNITIVE
NETWORK
(HIGHER RADIO
LAYERS)

  
 
 

     

"7 5 ANALYIZE'

  
 

REPORT

 

 

 

Figure 3-1: Cognitive Network
The purpose of this work is to develop a distributed and localized framework called
Cognitive Spectrum Assignment Protocol (CoSAP) which utilizes the cognitive features
of a cognitive radio to facilitate dynamic channel assignments in a wireless network for

secondary users to take advantages of the available spectrum opportunities.

3.2 Problem Formation

3.2.1 Network Model

The problem formulation is given as a channel assignment problem for secondary
users. A wireless mesh topology with K non-overlapping wireless channels (spectrum
holes) is studied. The number of channels that are available to a given node can be varied.
This heterogeneous channel sets for each node represent the spectrum opportunity (SOP)
of a particular node. The SOP is a function of primary users that are in range of a
secondary node. Each node is equipped with Q network interface cards (NTCs), where 1 S
Q S K. This number is typically 2 or 3 for the simulations in this work. A node’s NICs

21

are to be mapped to different channels for maximizing the effective network throughput.
All the NICs are half-duplex with Omni-directional antennas, and fixed transmission (r >
0) and interference (R > r) ranges. An undirected graph G( V, E), which is referred to as
the connectivity graph, is used to represent the topology where V is the set of n nodes
(vertices) and E is the set of links (edges). A link between nodes i and j exists if the
distance d( i, j) S r, and the link is represented as ( i, j). The connectivity graph of a network

is a function of the nodes’ locations and their transmission range.

3.2.2 Conflict Graph

Concurrent transmissions by two nodes within interference range R are allowed
only if the transmissions happen on different channels. Altemately, if the transmissions
are on the same channel then they interfere with each other. This interference can be
modeled using a weighted conflict graph. In a conflict graph F, the vertices correspond to
links of a connectivity graph G, and an edge in F exists when two links in G represented
by vertices in F interfere with each other. The interference on links in F is governed by
the protocol based interference model as proposed in [14]. To accurately estimate
interference, a different conflict graph is created for each channel.

The relationship between a network’s connectivity graph and the channel specific
conflict graphs are depicted in Figure 3-2. Figure 3-2(a) shows a sample network in terms
of its connectivity graph G. Figure 3-2(a) also shows how the two channels (1, 2) are
assigned to different node interfaces. Figure 3-2(b) shows the conflict graph
corresponding to G when the interfaces of all the nodes are assigned the same single
channel. Figure 3-2(c) and Figure 3-2(d) show the conflict graphs corresponding to
channels 1 and 2 respectively, as assigned in Figure 3—2(a).

22

 

 

 

 

 

Figure 3-2: Conflict graph of a sample network
These figures indicate as to how the concept of conflict graph can be utilized for
representing network interference. The resulting graph for a given channel is referred to
as a topology. It should be noted that the connectivity graph is a function of the node
locations and the transmission range, and the topology is a function of the connectivity

graph and the channel-to-interface assignments.

3.2.3 Channel-to-Interface Assignment Problem

Given a mesh network with primary and secondary nodes with secondary nodes
having multiple NICs and multiple available channels, the channel assignment problem
involves the mapping of available channels to the NICs of each secondary node in the
network with the goal of avoiding using channels chosen by primary users and
minimizing the network inference for maximizing the system throughput. Primary users
can have a large range of impact on the secondary network depending on the degree or

usage of the spectrum.

23

3.3 CoSAP Architectural View

CoSAP uses a decoupled design as discussed in section 2.2, in which the channel
selection is traffic independent. This makes CoSAP to be able to easily leverage the
existing routing and MAC layer protocols for wireless mesh networks. The CoSAP
extension to the network stack occurs between the routing and MAC layers. Any routing
protocol can be employed to choose paths in the network. This is a direct result of the
connectivity maintenance component of CoSAP because links will not change based on
the individual channel assignments of the nodes. As a result of each node having multiple
interfaces there are multiple MACS. These MACS maybe heterogeneous but for this work
they are using the 802.11 protocol. CoSAP assigns the channel to each MAC (interface)
that a node uses to communication with each neighbor. As shown in Figure 3-3, the main
CoSAP protocol uses consists of three modules, Channel Assignment Protocol, Neighbor
Discovery, and Channel Coordination Protocol to perform the channel—to-interface
assignment for each node. CoSAP is a distributed protocol therefore this framework is the

same for every node in the network.

24

 

 

User Applications I

 

  
 

 

  

User Data Routrn g Protocol

   
  

 

CoSAP Protocol

 

 

 

 

    
 

 

 

 

 

 

 

 

 

CoSAPProtocol , ‘ j I
Coordination
Protocol MAC MAC
forCSCC
' . Cognitive
Radio

   

 

 

 

 

 

 

Figure 3-3: Architectural components of CoSAP

The Channel Assignment module performs the channel assignment for each of the
nodes interfaces. The module uses the local neighborhood information gathered from the
Neighbor Discovery module, which discovers the neighbors that are around the node. It
uses also learns of neighbors that are m-hop away from the node. Once channel
assignments are made at a node, the facilitation of these decisions to neighboring nodes
are performed by the Channel Coordination module. The Channel Coordination module
controls the messages that are passed between two nodes dining the channel assignment
phase. This module is important because in a distributed protocol information must
remain uniform throughout nodes in a neighborhood.

These modules use a dedicated Common Spectrum Control Channel (CSCC) [25]
to send messages. Using this dedicated CSCC, the nodes form a control overlay whose

topology is the same as the basic connectivity graph for the network. The common
25

channel allows for nodes to have a dedicated form of communication between all of their
neighbors. All control messages used by the neighbor discovery protocol, and the channel
coordination protocol are exchanged over the CSCC overlay. Note that the CSCC
channel is permanently assigned to a dedicated interface to each node, thus being
completely independent of the channel assignment process described in the following

sections.

3.4 Neighbor Discovery

In a distributed protocol typically the first task for a node is to discover neighbors
that it may be able to communicate. Initially, each node periodically sends out hello-
tuples with information about its own along with up to m-hop neighborhood status. A
hello-tuple from a node contains its available channels, interface count, and the existing
channel-to-interface assignments. Table 3-1 shows the information within each tuple sent
Node ID and Number of interfaces is the id of the node and number of interfaces that are
available for channel assignment respectively that is sending the tuple. The One, Two,
and Three hop Neighbor fields contains the corresponding neighbor of the node. Next,
the Tuple Count value determines which neighbor (one, two or three hop) the Neighbor
Channel, List of spectrum opportunity (SOP) and Channel to Interface Assignment fields

are corresponding to.

26

 

 

Node ID One hop Neighbor Two hop Neighbor Three hop
Neighbor
Number Tuple Count Neighbor Channel List of
Interfaces Neighbor
SOP

 

 

 

 

Interface - Channel Assignments

 

 

 

Table 3-1: Hello Tuple Contents

Each tuple gives all the information about a neighbor that a node has gathered at
the time of sending. The protocol uses on local (one hop) messages to gather information
about nodes that are m-hop away. When a node receives a tuple from one of its neighbors
the node updates its own table, then adds its own information and rebroadcasts the new
information on its next hello message. Suppose a node i receives a hello message from its
neighbor node j. On i’s next hello-tuple update, all the above information about node i
and j, and other l-hop neighbors of i is transmitted. In the next iteration of i 's hello-tuple
update information of all its 2-hop neighbors will be transmitted. This process is
expanded such that at steady state, i’s hello-tuple update will contain the information
about all its neighbors up to m-hops away.

Flooding is an issue that arises when broadcasting hello messages periodically. To
reduce flooding different timers are used to control the amount to messages sent. In the
first 5 minutes of the networks life hello messages are sent at an average of 1 minute.
This allows all of the nodes to learn of their neighbors. Afterwards, during the channel
assignment phase nodes send messages at an average of 2 minutes. A second method of
reducing the amount of flooding it to only send information when there is a change in one

of the fields, i.e. a new channel assignment is made.

27

3.5 Distributed Channel Assignment

In this section, a discussion of the CoSAP channel assignment protocol will be
given. CoSAP is a fully localized and distributed protocol; therefore this algorithm will
be carried out in every node of the network. The interface to channel assignment
mechanism is described here in terms of the actions taken by node i in steady state. Using
the Neighbor Discovery module node i first identify all its l-hop neighbors with which it
has not yet established a link. A link between two neighbors is considered established

when the nodes have at least one common channel assigned to their respective interfaces.

3.5.1 Assignment Initiation

For a l-hop neighbor node j, with which node i has not yet established a link, node
i sends an Approval_Request message. This message is used to request node j for an
approval to initiate a link establishment. If node j has not received another request
message or is not currently assigning a channel he will send an Approval Reply message.
After receiving the reply message stating that the assignment is approved by j, node i
initiates the channel selection process. The node that sends the initial request message

will determine the channel assignment between for the link. The first step node I takes is

to calculate the Useable Channel Set (UCS).

3.5.2 Computing Useable Channel Set (U CS)

The UCS determines the flexibility of channel choices for the current link
assignment. This flexibility is a function of the current status of both nodes interface to
channel assignments. From neighbor discovery, node i has complete knowledge of the

SOP and current channel to interface assignments for node j. The available channels for

28

communication are a result of the current SOP of each node. Node i determines the USC
by checking the four possible states of both nodes:
(1) if node i and j both have a free interface, therefore a new channel can be
assigned both i’s and j’s interfaces. This gives the greatest flexibility.
(2) if one of i or j has all of its interfaces already assigned, and the other node
has at least one free interface.
(3) if all interfaces of node i and j are assigned, This case gives the least
amount of flexibility.

If (1) is true, then the useable set is the intersection of the available channels at i
and at j. Otherwise, if (2) is the case then useable set is the intersection between the
assigned channel set of the node without any free interface and the available channels in
the node with at least one free interface. lastly, if (3) is true then the useable set is the
intersection of the channels assigned at its interfaces at node i and at node j. With the
dynamic nature of the distributed protocol it is possible that the UCS can be a null set.
Therefore no channels are at the time of creating the UCS are available for establishing
the link (ij). Such a situation will trigger a channel reassignment phase as described later
in Section 3.5. A sample UCS creation is shown in Figure 34, where two nodes are
establishing a link. Node 1 and 2 already have a channels assigned to their interfaces that
are part of the other nodes available channel sets. These are channels 1 and 2. Channel 5
is part of both available sets of both nodes. Since both nodes have a free interface,

channel 5 can be assigned.

29

 

Available Channels: 2, 5, 6 Available Channels: 1 , 5,7

18‘ Interface: 3 13t Interface: 2
2"d Interface: 1 2"d Interfacez4
3rd Interface: Unassigned 3rd Interface: Unassigned

6 UCSH’Z’S @

Figure 34: Sample UCS

 

 

 

3.5.3 Constructing Local Channel Set (LCS)

For a sequential and distributed channel assignment, the selection of a channel
between nodes i and j affects the later choices of channels among their respective
neighbors. In certain scenarios the choice of a specific channel for link (ij) may give rise
to a situation in which no appropriate channels may be available for constructing one or
more links emanating from the neighbors of nodes i and j. Such situations are detected
through an empty UCS set, as discussed in the last section. Due to such unrealized links,
the topological connectivity of a network cannot be guaranteed, and thus the network can
become partitioned. Note that this problem happens only for a distributed allocation
approach. For a centralized allocation [13], which is done in the presence of the full
network information, such topological disconnection is typically not an issue.

Disconnection in CoSAP is reduced by employing a heuristic based channel
filtering mechanism for obtaining a Local Channel Set (IJCS) from the Useable Channel
Set (UCS) derived in the last phase of the algorithm. LCS is created by taking the
channels in UCS and estimating the connectivity impact of choosing each channel to the

rest of i’s and j’s unassigned neighbors. Estimation of connectivity impact begins with i’s

30

knowledge of the m-hop neighborhood. Constrained nodes, nodes with interfaces already
fully assigned, channels are given higher priority in the channel decision. In addition,
channels that have greater commonality between the nodes in the m-hop neighborhood
are given higher priority. The general motivation of this filtering is to avoid using
relatively less used channels for realizing link (i,j), so that those channels will be

available for future link realization in the m-hop neighborhood of nodes i and j.

3.5.4 Conflict Graph Computation

Once the channels are chosen for LCS, they must be evaluated to determine the
channel that will minimize interference on the link (ij). Node i first creates a connectivity
graph of its m-hop neighborhood by using the information received during the neighbor
discovery process. The connectivity graph contains all of the currently known channel
assignments between nodes in the neighborhood. From the connectivity graph, a
weighted conflict graph for each channel of the LCS is constructed. Each vertex in the
conflict graph for channel 3 corresponds to an edge (link) in the connectivity graph
realized using the channel 3. In other words, whenever a new link is established using the
channel 3, a new vertex, representing the link, is added to the conflict graph for the
channel 3. Now, if there are two channel s links are there within the radio transmission
range (i.e. transmission in one link can interfere with the other), an edge will be created
in the channel-s conflict graph between the two vertices representing those links.
Therefore, the degree (number of edges) of a vertex in the conflict graph for channel-s
represents the amount of interference, which the corresponding channel-s link in the
network is expected to experience. This degree is referred to as link conflict weight. A
small link conflict weight represents low interference.

31

knowledge of the m-hop neighborhood. Constrained nodes, nodes with interfaces already
fully assigned, channels are given higher priority in the channel decision. In addition,
channels that have greater commonality between the nodes in the m—hop neighborhood
are given higher priority. The general motivation of this filtering is to avoid using
relatively less used channels for realizing link (i, j), so that those channels will be

available for future link realization in the m-hOp neighborhood of nodes i and j.

3.5 .4 Conflict Graph Computation

Once the channels are chosen for LCS, they must be evaluated to determine the
channel that will minimize interference on the link (iJ). Node i first creates a connectivity
graph of its m—hop neighborhood by using the information received during the neighbor
discovery process. The connectivity graph contains all of the currently known channel
assignments between nodes in the neighborhood. From the connectivity graph, a
weighted conflict graph for each channel of the LCS is constructed. Each vertex in the
conflict graph for channel 3 corresponds to an edge (link) in the connectivity graph
realized using the channel s. In other words, whenever a new link is established using the
channel 3, a new vertex, representing the link, is added to the conflict graph for the
channel 3. Now, if there are two channel 3 links are there within the radio transmission
range (i.e. transmission in one link can interfere with the other), an edge will be created
in the channel-s conflict graph between the two vertices representing those links.
Therefore, the degree (number of edges) of a vertex in the conflict graph for channel-s
represents the amount of interference, which the corresponding channel-s link in the
network is expected to experience. This degree is referred to as link conflict weight. A
small link conflict weight represents low interference.

31

knowledge of the m-hop neighborhood. Constrained nodes, nodes with interfaces already
fully assigned, channels are given higher priority in the channel decision. In addition,
channels that have greater commonality between the nodes in the m-hop neighborhood
are given higher priority. The general motivation of this filtering is to avoid using
relatively less used channels for realizing link (i, j), so that those channels will be

available for future link realization in the m-hop neighborhood of nodes i and j.

3.5.4 Conflict Graph Computation

Once the channels are chosen for LCS, they must be evaluated to determine the
channel that will minimize interference on the link (i,j). Node i first creates a connectivity
graph of its m-hop neighborhood by using the information received during the neighbor
discovery process. The connectivity graph contains all of the currently known channel
assignments between nodes in the neighborhood. From the connectivity graph, a
weighted conflict graph for each channel of the LCS is constructed. Each vertex in the
conflict graph for channel 3 corresponds to an edge (link) in the connectivity graph
realized using the channel s. In other words, whenever a new link is established using the
channel 3, a new vertex, representing the link, is added to the conflict graph for the
channel .9. Now, if there are two channel s links are there within the radio transmission
range (i.e. transmission in one link can interfere with the other), an edge will be created
in the channel-s conflict graph between the two vertices representing those links.
Therefore, the degree (number of edges) of a vertex in the conflict graph for channel-s
represents the amount of interference, which the corresponding channel-s link in the
network is expected to experience. This degree is referred to as link conflict weight. A
small link conflict weight represents low interference.

31

The concept of a conflict graph was explained in Figure 3-2 and Section 3.2.2. Note
that because of the distributed and localized nature of the CoSAP framework, each node
constructs and maintains the connectivity graph and conflict graph information only
about its m-hop neighborhood. This is in contrast to the centralized approach [15], in
which a centralized spectrum server is expected to construct and maintain those graphs
for the entire network. This directly relates to the scalability of the CoSAP approach,
where regardless of network size nodes will only maintain information about its m-hop

neighborhood.

3.6 Channel Selection

After node i computes the conflict graph of its m-hop neighborhood for all channels
in the useable set for the link (i, j), it chooses channel k from that set, such that the link
conflict weight for link (i,j) is the minimum. Then node i chooses channel k for
establishing the link (i, j), since this channel is expected to create minimum interference at

that link. The channel assignment process is summarized in Figure 3-6 and Figure 3-6.

32

 

 

Channel Selection Algorithm at Node-i
Initiation:

While node i has an unassigned incident link, perform channel assignment for

a link.
Node chooses node j for channel assignment.
Node i send a channel request message to node j
If node i receives a channel reply from j I
Set channel assign flag to not accept incoming channel requests
Create UCS; }
Useable Channel Set (UCS) Computation:
If (both nodes i and j have at least one free interface)
UCS <— i ’s available channels fl j ’5 available channels;
else
If (only one of i and j has all its interfaces already assigned ){
U CS <— all assigned channels for the node with no free interface I)
channels available to the node with free interface;
)else // both nodes do not have any free interface
U CS «— i ’s assigned channels fl j’s assigned channels;
If(UCS is a NULL set)

The link ( i, j ) cannot be established; // channel reassignment will be initiated

 

Figure 3-5: Channel Assignment Algorithm in CoSAP

33

 

 

 

Channel Selection Algorithm at Node-i (continued)
Local Channel Set (LCS) Construction:
For (each channel in the UCS)!
If (the number of links in the m-hop neighborhood of i and j
that are realized using the channel 2: p)
Add the channel to LCS;
}
If (LCS is a null set) // not enough links have been realized in
LCS = UCS; // the neighborhood; CoSAP just started
Construction of Conflict Graph for channel-s in the LCS :
Create a graph with each vertex representing a channel-s link in the m-hop
neighborhood of node-i;
Add an edge between two vertices, if the links represented by the vertices are
within the radio interference range;
Compute the link conflict weigh for each vertex as its degree;
Channel Selection for link (i,j):
Constmct conflict graphs for all channels in LCS;
Choose a channel from LCS such that:
Chosen Channel r—Min {link conflictweight(c)}, forall ce LCS
// the link conflict weight for the conflict graph vertex

// corresponding to link ( i, j ) is minimized

 

Figure 3-6: Channel Assignment Algorithm in CoSAP (Continued)

34

 

3.7 Reassignment for Connectivity Maintenance

Even using the [CS filtering process discussed in Section 3.5.3, in certain scenarios
it is possible that upon convergence of the CoSAP, some of the links on the connectivity
graph remain unrealized. To handle such occurrences, a channel reassignment strategy
that is run iteratively until successful assignment with no or very few (within a preset
tolerable limit) links remain unrealized has been implemented. The adopted reassignment
strategy is as follows.

When node i finds the link (i,j) to be unrealizable, it first attempts to reassign its
existing established links so that one of its interfaces can be freed. Reassignment of an
already established link also requires node i to request its neighbor to assign a different
channel for that link. Node i has knowledge all of the channel assignments and
connections of every neighbor, therefore node i determines which interface can be
modified. The node uses a Reassign_Request message to accomplish this. Once an
interface becomes free, node i chooses the minimum interference channel that are
currently used by node j on all of its assigned interfaces. In this case, it is guaranteed that
the link will be realized.

If, however, freeing an interface at node i is not feasible (one of node i’s neighbors
will lose a link if there is a reassignment), then all the links of node i are reassigned. Such
reassignment involves first de-assigning the already established links by sending De-
assign_Request to appropriate neighbors, and then run the assignment logic (see Figure
3-6) for all of i’s de-assigned and unassigned links. This cycle of attempting to free

interface and reassignment constitutes a reassignment iteration. Each such iteration

35

reduces the number of unrealized links in the network, since most of the interfaces of

neighboring nodes are assigned at the time of the reassignment.

3.8 Channel Coordination Protocol

For a distributed channel assignment protocol that relies on knowledge of
neighboring nodes assignment information, correctness of node status is important. The
Channel Coordination Protocol facilities the channel assignment messaging between
pairs of nodes in the network Once node i selects a channel for realizing the link (i,j),
coordination between nodes i and j begins for the actual assignment. In CoSAP, each
node continually builds the connectivity graph using the neighbor discovery information,
and whenever it detects an unrealized link with one of its neighbors, the node initiates the
channel coordination protocol with that neighbor as an attempt to assign channel for that
link. Since this operation is distributed and asynchronous across the nodes, the

coordination protocol is needed.

 

 

 

 
 
   
   

 

Nodei 1‘10de
Approval _Request
E T”
E
g a) Approval_Reply
”o a
0 <2

Assignment
Verification

Assign_Channel

K

Accept_Channel

'— Link Establishment ——'1
Duration

Reassrgnment
(If necessary)

   

 

M

 

 

 

 

 

Figure 3-7: Protocol components of a link establishment cycle

36

As shown in Figure 3-7, after a node i detects an unrealized link (i, j ), it executes an
Approval_Request! Approval_Reply transaction cycle with neighbor j to initiate the
channel assignment process. Neighbor j responds with an Approval_Reply only if it is not
already in the middle of another channel assignment process. This is done to ensure that
during the assignment process node j interface status does not change. After node i
receives the Approval_Reply, it selects the best channel following the algorithm
presented in Section 3.6 and sends an Assign_Channel message to node j with the
selected channel information. Upon reception of this message, node j runs a channel
verification phase based on its own notion of the neighborhood connectivity graph and
the conflict graphs. If node j finds the channel acceptable then it performs an interface-to-
channel assignment for itself and sends an Accept_Channel message back to node i. Node
i then performs its own channel-to-interface assignment and that concludes the link
establishment process. The ongoing neighbor discovery process ensures that the
information about the new channel-to—interface assignments at both nodes i and j will
eventually be propagated up to all m-hop neighbors.

Since the process is asynchronous across the nodes, either of i and j may initiate the
establishment process of the link (i, j). The node that initiates the Approval_Request
message becomes a master and the other node becomes a slave during this link
establishment process. The approval part of the channel coordination protocol ensures
that at a time, a node cannot be a part of more than one link establishment process. This

helps avoiding any assignment inconsistencies caused by the distributed operation.

37

3.9 Primary Network Considerations

The previous discussion was specifically regarding the channel assignment
characteristics of CoSAP. Cognitive networks require the handling of primary users
within the same network. CoSAP is able to perform channel assignment with primary
users present in the network. Channel assignment protocols designed for nodes in a
typical mesh network assumes uniform channels for every node. In other words, every
node in the network can assign the same set of channels to their interfaces. For a
distributed implementation the list of available channels can be hard coded in every node
because it will not change for the lifetime of the network. A uniform available channel
listing is sufficient for networks that do not consider primary users. Recall the discussion
in Section 1.4 where the term SOP (spectrum opportunity) is defined. SOP is defined as
the set of available channels for a given node. The availability of channels in this set for a
given node is a function of primary users within a given range (transmission) of the node.
As a result of the goal of cognitive networks to not interfere with a primary user network
a nodes SOP is reduced in the presence of primary users. The cognitive radio determines
the channels that are available to the node for interface assignment.

In channel assignment algorithms that do not consider primary users, nodes in the
network SOPs are homogenous. When primary users are considered the SOPs for nodes
in the network are heterogeneous. For example if nodes i SOP is initially l, 2, 3, 4 then
after some time a primary user using channel 2 comes into range of the node. To avoid
interfering with the primary user the node reduces its SOP to 1, 3, and 4. When there are
many primary users in the network using different channels nodes SOPs can become very

diverse. The assigning of a channel between nodes requires first finding the intersection

38

of the nodes SOP. This fact can create problem of channel assignment algorithms.
CoSAP handles homogeneous and heterogeneous SOPs of secondary nodes by sending
SOP information through hello messages. When channel assignments are performed there
is a check of the compatibility between two neighbor nodes SOP and only channels that

are common from both SOPs are used.

39

Chapter 4: Centralized Channel Assignment Algorithm

In this chapter, a centralized channel assignment algorithm is introduced. The
purpose of this algorithm is to provide benchmarking for the distributed CoSAP
algorithm. The introduced algorithm is a modified implementation of the CLICA
algorithm [13]. The centralized algorithm is connectivity preserving, interference

bounded and adaptive priority algorithm.

4.1 Centralized Advantages

As discussed in Section 2.1.1, centralized algorithms have the advantage of full
network information. Additional network information that can be available to a
centralized channel assignment algorithm includes current channel assignments for every
node, node locations, and knowledge of every nodal link. Knowledge of all nodes
channel assignments at every instant allows for the greatest estimation of interference in
the network. This is different to a distributed algorithm because in a distributed case
nodes have knowledge of no more than their local neighborhood. Using the information
about channel assignments and nodal links a centralized algorithm should be able to
maintain connectivity between nodes in the network. It can choose channels that will not
impact the interface constraint of every node in the network. In addition, knowledge of
the locations of node allows for interference estimation using the interference range of
nodes. This information is not feasible for a distributed protocol. Furthermore, centralized
algorithms can control the order of channel assignment between nodes. This gives an

advantage over distributed solutions because in the distributed case channel assignments

40

can happen between many different nodes in different locations in the network

concurrently.

4.2 Centralized Protocol

When nodes are assigning channels, their decisions impact future channel
assignments. A nodes assignment can reduce the interference of a link, increase the
interference, or create a partition in the network. This implies that every channel
assignment decision by a node can be very flexible depending on the situation. The
centralized protocol takes advantage of this flexibility by increasing the priority of nodes
that can perform channel assignments. This priority is used to which node will assign a
channel to a link. This is typically based on the interface constraint at particular nodes.
Nodes with an interface constraint will have a greater priority. Higher priority nodes
assign channels to all of their links before lower priority nodes. Initially nodes are given a

default priority, which can be node id or any other criteria.

 

 

 

 

1|F

 

Figure 4-1: Sample topology to explain interface constraint

41

An example of the algorithm operation will now be described. In Figure 4-1 there
are 4 nodes that connected in the fashion shown in the figure. Each node has 1 interface
that need to be assigned to channels. Initially the priority if the nodes are in the order of i
— j — k — m. First node i attempts to assign neighbor j. If node i choose channel 1, then all
of nodes i and j interfaces are assigned. This causes the algorithm to increase the priority
of node j. At this time, node j starts to recursively assign links that are on other paths that
connects j to i. This is performed to ensure the channel assignment decision at node j will
not break the interface constraint of other nodes in the network. With the knowledge of
all links in the network j can check every other path back to ensure that the interface
constraint is satisfied. Proof of the connectivity maintenance is given in [13]. Therefore
the next link to be assigned is link j — k. Because node j only have 1 interface it must
assign channel 1 to link j — k. Following this situation the link k — m and m — i must be

assigned channel 1.

 

 

 

 

1|F

 

Figure 4-2: Sample topology to explain channel flexibility

42

 

If nodes i and k have two interfaces (Figure 4-2) then the channel assignment has
more flexibility. As before, node i starts assigning channels to all of its unassigned links.
Node i assigns the link i - j to channel 1. Afterwards it has another interface that can be
assigned to a channel for the link i — m, but node j interface is constrained greater than
that of node i. Therefore node j priority is increased. Node j must assign channel 1 to link
j— k. Since all of node j’s links are assigned node k is next to assign links. Because node
k has two interfaces it assigns channel 2 to the link k — m. Afterwards, node m priority is
increased because of its interface constraint. Node m must then assign channel 2 to the
link m - i.

The centralized algorithm makes the channel assignment decisions in a greedy
fashion. The algorithm maintains a connectivity graph and conflict graph with every link
and channel assignment for every node in the network During each channel assignment
the conflict graph is updated based on the current connectivity graph. The channel
conflict weight is found using the conflict graph for each possible channel for
assignment. This is similar to the process discussed in Section 3.5.4. When a link i - j is
to be assigned, channel that is chosen is the channel that minimizes the link conflict
weight for the link In other words, the channel that has the least amount of interference

as seen by the link is chosen.

4.3 Primary Network Considerations

As discussed in Section 3.9, the cognitive network requires being able to assign
channels in an environment with primary users. When every node in the network is
equally affected by the same primary nodes the spectrum opportunity (SOP) of the
secondary nodes is homogeneous, meaning that the set of channels that can be assigned is

43

the same for every node in the network. When primary users are not uniformly affecting
secondary nodes the SOP becomes reduced and heterogeneous. The centralized algorithm
has knowledge a priori to the channel assignments. Therefore nodes SOPs are adjusted

accordingly. Channels are assigned only from the SOP of nodes.

 

Chapter 5: Experimental Setup

In this chapter, a discussion of the simulation setup is given. Performance of
CoSAP was evaluated using ns-2 network simulator version 2.30. Ns-2 is an event-driven
C++ and TCL language based simulator. It is open source and can be extended to
implement many wired and wireless network protocols. Currently ns-2 does not support
multiple channel, multiple interface networks, therefore extensions where added to

support these features. An extension to ns-2 was added to support the CoSAP protocol.

5.1 Multiple Channel, Multiple Interface Extension

The multiple channel and multiple interface extension used was based on the
contributions from [26]. As shown in Figure 5-1, the original ns-2 wireless node model
consists of a components that would typically be found in any wireless device. These
include modules for 3 Routing Agent, Link Layer, MAC protocol, Arp, Interface Queue,
and Network Interface. In addition there is a Propagation model to simulate the effects of
wireless channels on a transmitted signal. All of these modules are connected to a single
channel, hence only supporting a single channel network. The goal is to extend the
wireless node model to multiple channels and multiple interfaces.

To extend the wireless node model, functions where added that logically gave a
node multiple interfaces. All of the modules below the Routing Agent are instantiated
multiple times within the multiple interfaces, as shown in Figure 5-2. In other words each
interface has a set of Link layer, MAC, and ARP for communications. The Routing
Agent is given the ability to select the interface with which each packet is transmitted. At

a high level, a user can define the amount of interfaces and channels that each node in the

45

network will have. It should be noted that the channels in this implementation will be
non-overlapping channels, meaning that a packet transmitted on one channel will not

interfere with transmissions on a different channel.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4...... w]

W I

 

 

 

 

 

 

 

 

 

 

MAC ._.._.

 

 

 

 

 

 

 

 

Propagmion lm

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 5-1: Original Node Architecture [27]

46

 

 

 

 

Figure 5-2: Multiple Channel Multiple Interface Extension [26]

47

 

5.2 Ns-2 CoSAP Extension

As a decoupled channel assignment protocol CoSAP is functionally located
between the Routing and MAC layers. CoSAP uses a dedicated control channel which is
always channel 0 and data channels designated as channel 1, 2, 3, and so on. Figure 5-3
shows this architecture. The CoSAP algorithm is implemented in Ns-2 using OTcl and
C++ languages. Network functions is N s-2 can be described by primitives such as Nodes,
Links, Agents, and Applications. Nodes represent end-host in the network, Links are
connectors through which Nodes exchange packets, Agents are basic blocks to implement
network protocols at various layers where network-layer packets are constructed and
consumed, and Applications sit on top of transport agents for traffic generation and
simulated applications. The distributed channel assignment portion of CoSAP is
implemented as an Agent primitive in Ns-2. The CoSAP implementation consists of
many software components including but not limited to messaging protocols, timers, and
channel assignment related algorithms. The messaging protocols implementation controls
the operation of all of the forwarding, receiving, neighbor discovery, channel request and
reply messages. Within the CoSAP Agent, timers are used to schedule when hello
messages are sent, timeouts for channel assignment replies, and channel reassignment
initiations. Finally there are many channel assignment related functions, including
interface assignment checks, neighbor lists, and minimal channel weight calculators.

The topology, traffic, and routing of the network is not implemented within the N s-
2 simulator. A separate C++ program output is inputted into the Ns-2 at run-time with the
simulation infomration. The C++ program creates the node locations, TCP and UDP
connections and shortest hop routing for the network. An external program was

48

developed to provide full control over the simulation parameters. The external program
guarantees that every node has at least one neighbor and can reach every other node
through at least one other node, signifying networks with no partitions. The program also
houses the centralized algorithm. which its channel assignment results are inputted in the

Ns-2 at run-time.

 

 

  
 

Control
Channel

   
 
 

Channel
1

  
 

Channel
2

 

 

  
 
 
 
 

 

 

Figure 5-3: CoSAP Extension [27]

49

Chapter 6: Performance of CoSAP with Homogeneous Spectrum
Opportunity

In this chapter CoSAP is evaluated using homogeneous SOPs of secondary users.
For all simulations in this thesis the performance of the secondary user is evaluated.
When primary users are present in a network they can reduce the amount of channels that
can be utilized by secondary users. Homogeneous SOPs represents the case were all
secondary users in the network are affected by the same primary users, leading to all
nodes having the same set of channels in their SOP. Simulations were performed to
evaluate many aspects of the CoSAP algorithm. First single hop link layer performance
was evaluated using UDP traffic. Next TCP traffic was used to evaluate multi-hop
performance. Then a centralized channel assignment algorithm is evaluated to determine
bench marking performance. Finally results are provided to show the connectivity

maintenance and scalability of CoSAP.

6.1 Simulation Setup

Most of the simulations use static mesh topologies with 50 randomly places nodes.
As mentioned in Section 3.2.2, interference modeling was performed using the Protocol
Model as used in [14]. Because these experiments consider secondary users are equally
affected by the same primary users, the channel sets or spectrum opportunity (SOP) of all
the nodes are homogeneous. The SOP is modeled in the simulations as a set of channels
that nodes can select from to assign to an interface. Once the interface is assigned data is
sent using the assigned interface. Results are reported for scenarios with 2 and 3 NIC’s

per node running 802.11 MAC layer protocol. All nodes use 250m transmission range
50

 

and 550m interference range. Each reported data point corresponds to the average taken
from 1500 see simulation runs over 25 different networks.

The notation CoSAP (x, y) is used for denoting the scenario with x interfaces and y
channels available to each node. The performance of CoSAP has been compared with
traditional 802.11 MAC Single Channel performance (SC) and a Common Channel
Assignment (CCA) [l3] protocol. With CCA, a distinct channel is statically assigned to
each NTC of a node. Therefore, the number of channels available to a node is the same as
the number of its NICs. During each packet transmission, a node randomly chooses a
channel and its statically assigned interface. Unlike CoSAP, in which an interface is pre-
assigned to a link, in CCA, the interface used for a link is decided on a per-transmission

basis.

6.2 One-hop UDP Throughput

One-hop UDP throughput traffic is run over a static mesh topology with 50 nodes.
This represents link layer performance of the protocols for the fact that transmissions are
only limited to one-hop neighbors. The traffic model for this experiment consists of
unicast data between every pair of neighbor nodes in the network. The packet sending
rate was varied to obtain different loads, with a fixed packet size of 1 Kb [13]. Nodes
were random placed in three different terrain sizes to represent sparse and dense
networks. The topology sizes were 1400m x 1400m, 1200m x 1200m, and 1000m x
lOOOm. This corresponds to an average nodal degree of 4, 5, and 7 respectively. A denser
network means that there are larger amounts of links that must be assigned, which can
lead to connectivity maintenance issues. A discussion on how CoSAP handles this
situation is given in Section 3.7 and simulation results are shown in Section 6.6.

51

Figure 6-1 depicts the channel assignment performance for l-hop UDP traffic with
degree equal to 4. As expected, both CCA and CoSAP outperform the SC scenario in
terms of the network throughput. Observe that CCA-2 (with 2 interfaces and 2 channels
per node) and CCA-3 attain approximately 2 and 3 times the throughput of SC
respectively. This is because with CCA-n, n independent networks are created, each with
a separate channel. Therefore the effective network throughput is n-times that with a

single channel.

 

O

 

 

+Cosap 2,5
-— I-Cosap 2,4
-+Compz3
“ err—CCA 3

__ *CCAZ ‘ .., _. ,,
*SC ,, " ‘4"-

 

 

 

Throughput (Mbps)

N b.) & LII O'\ \l 00 \D
I
l

 

u—n
‘

 

 

 

 

0 - l 1' l i l l
0 5 10 15 20 25 30 35
Load (Mbps)

 

Figure 6-1: l-hop throughput with 2 interfaces per node (degree 4)

CoSAP (2,3), (2,4) and (2,5) correspond to scenarios with 3, 4, and 5 available
channels respectively. Note that the throughput achieved by CoSAP (2,3) is comparable
to that of CCA-3. This means that with only 2-interfraces and three channels per node,
CoSAP can deliver similar throughput compared to CCA with 3 interfaces per node. The
figure also shows that by adding more (4 and 5) channels, the throughput can be further

52

improved. For example, with 2 interfaces and 5 channels available to each node, the
maximum CoSAP throughput can be up to twice that of CCA with two interfaces, and up
to 4 times that of a single channel network The conflict graph based interference
reduction in CoSAP accounts for this capacity gain. In addition to higher effective
throughput, lower packet delivery delay for CoSAP is also evident from the results for l-

hop UDP traffic as shown in Figure 6-2.

 

 

16 Y

I .

. .

- : z

. ; .

. . : a
14 q- . , ‘ ....... ,7 _ __...{._-~a...... .,._....:,..

. , r

.

.

12

 

.—
O
r
1

Delay (Sec)
00

    
 

 

 

 

 

 

 

 

6 -L .
+sb
4 -- -I-CCA3
+CCA2 3
i : *CoSAP2,2 i
2 " 2 j ' r " *CoSAP2,3
{a g j +CoSAP2,4 §
o l a , : reams:
O 5 10 15 20 25 30 35

 

 

Load (Mbps)

 

Figure 6-2: Packet Delivery Delay for l—hop traffic (degree 4)

Similar to Figure 6-1, the performance of CCA and CoSAP with three interfaces
per node is presented in Figure 6-3. Relative performance variation trends here are very
similar to the 2-interface case. Figure 6-3 shows that with 3 interfaces and 6 channels
available to each node, the maximum CoSAP throughput can be again up to twice that of

CCA with 3 interfaces and 2 channels, and up to 6 times that of a single channel network.

53

 

 

 

+Cosap 3,6
l-Cosap 3,5
+Cosap 3,4

*CCAB 1 /

 

 

 

i.
O

Throughput (Mbps)
0\ 00
l l

.p
r
I

 

 

 

0 5 10 15 20 25 30 35
Load (Mbps)

 

 

 

Figure 6-3: l-hop throughput with 3 interfaces per node (degree 4)

These indicate that the performance gain using CoSAP over CCA is maintained
with increasing number of interfaces per node. The delay performance of the 3-interface
experiments, Figure 6-4, shows patterns very similar to the 2-interface results in Figure
6—2. It was observed that both the throughput and the delay results of CoSAP are found to
be consistent with the results reported for the centralized solution CLICA presented in
[13]. Additional simulation results for different topologies sizes are presented in the

Appendix.

54

 

 

 

l—l
0‘

 

 

 

 

+SC
ifCCA3 f g 3 §
#fiCoSAP3,4 3 i =
12 . *COSAP3’5 .
F-O-CoSAP3,6 .
10 ‘

Delay (Sec)
00

 

 

 

 

 

6 - ............................................
4 ..
0 ' ' I if t % fil é

0 5 10 15 20 25 30 35

 

 

Load (Mbps)

 

Figure 6-4: Packet Delivery Delay for l-hop traffic (degree 4)

6.3 Multi-hop TCP Throughput

Experiments were also carried out to evaluate the throughput impacts of CoSAP on
multi-hop TCP traffic. As in [13], we modeled two different application traffic models.
The first model involves peer-to-peer (P2P) traffic, in which 100 TCP connections were
set up between randomly chosen source and destination nodes.

The second model is an intemet gateway traffic model in which 4 nodes in the 50
node network were arbitrarily selected as gateway nodes for transporting traffic from the
ad hoc network to intemet routers. Data connections were set up between the gateway
nodes and nodes that are certain hops away from the gateway nodes. Average
experimental TCP throughput percentage increase over CCA for both the models are

reported in Figure 6-5 and Figure 6-6 respectively. The network is simulated with an

55

average degree of 7. Throughput data has been recorded based on the connection hop

count.

 

 

 

 

 

 

100% .
907 *CoSAP2,5 g ,_ A, _
o ; ‘I-CoSAP2,4 , ,
580% v ..... -A....-.V3...A..---.flog/(1,2,3..._‘._._.

 

 

 

 

0% ': .1 : E i
l 2 3 4 5 6 7 8
Number of Hops

 

 

 

 

Figure 6-5: Throughput improvement with 2 interfaces for peer-to-peer model

With P2P traffic, the percentage throughput improvement of CoSAP over CCA
(both with 3 interfaces per node) is reported in Figure 6—5. For TCP connections in a
single channel wireless mesh network, the throughput increase becomes less with longer
connections. This is because of interference between packets within a connection but at
different hops, as well as the interference between multiple connections. It turns out that
for longer connections, CoSAP is slightly less effective in reducing the interference
problem. However, across all the experimented hop counts, that is up to 8, the throughput
enhancements by CoSAP ranges from 10% to 40%, when 4 channels are used. With
higher number of channels (5 and 6) the improvement of CoSAP ranges from 20% to

60%. We have also conducted TCP experiments with 2 interfaces per node for which the

56

 

performance trend was observed to be very similar to those with 3 interfaces as shown in

 

 

 

 

 

 

 

 

 

 

 

Figure 6—5.
120% 3
1 +Cosap2,5 ,
f *Cosap2,4 :
510% ; +Cosap2,3
o 1
5'5 4
> 80%
O
i
5 60%
E.
0
5° 40%
r:
8
5'5
9" 20%
0% if r
l 2 3 5
NumberofHops

 

 

 

Figure 6-6: Throughput improvement with 2 interfaces for gateway model
Very similar throughput improvement trends, with 3 interfaces, can be also

observed for the gateway model traffic as shown in Figure 6-7 and Figure 6-8.

57

 

 

Percentage Increase
N b) 8 U!
o o o
09 <35 95 39

10%
0%

 

 

 

*CoSAP3, 6

 

 

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

+CoSAP3, 4 ..

 

 

 

,..- ~3-
. g '1

L... f ......... .L
r r r r r r
l r I r r r

4 5
Number of Hops

 

Figure 6-7: TCP throughput improvement with 3 interfaces for P2P model

 

 

100%
90%

 

 
 

 

 

{
l
I

+Cosap 3, 4

f

 

l

-I-Cosap3,5 ‘

 
 

   

 

 

 

 

 

 

 

Number of Hops

 

Figure 6-8: Throughput improvement with 3 interfaces for gateway model

58

 

 

 

 

 

90%*

 

*CoSAP3,6
80% - ; -.A'COSAP3’5 _
..-.... .f ....... ............... ........... +cOsAP3,4 ............... ..............................

 

 

 

-.. ... ..............................................

 

Percentage Increase v C
N b.) #- UI 8 \l
O O O O O
05 65 59 39 39 a?

i

 

i r r r
K I r I I

1 2 3 4 5 6 7 8
Number of Hops

o
05

 

Figure 6—7: TCP throughput improvement with 3 interfaces for P2P model

 

 

 

100%

90% , *C083p3,6 ._
080% ............ 'l'Cosap3,5
: +Cosap3,4

 

r

   
   
    

 

 

 

70% ““““““ ,,,,,,,, ‘
60% ....................... ........
50% _____________
40% i
30%
20%
10% 1 § ,
0%

Percentage Increase OverC CCA

 

 

 

 

Number of Hops

 

Figure 6-8: Throughput improvement with 3 interfaces for gateway model

58

 

 

6.4 Comparison with Centralized Channel Assignment Algorithm

The previous reported results were for the distributed CoSAP algorithm. A possible
drawback of distributed solutions is that nodes in the network typically do not have full
network information that can be utilized to increase performance as discussed in Section
2.1.1. Additional network information that can be available to a centralized channel
assignment algorithm includes current channel assignments for every node, node
locations, and knowledge of every nodal link. Furthermore, centralized algorithms can
control the order of channel assignment between nodes. This gives an advantage over
distributed solutions because in the distributed case channel assignments can happen
between many different nodes in different locations in the network concurrently.

The following figures compare CoSAP algorithm with the centralized algorithm
introduced in Chapter 4. The network was simulated with 50 nodes random distributed in
a 1000m x lOOOm area with each node having 2 and 3 interfaces. Available channels for
assignment were varied from 3 to 7 and from 4 to 8 for the 2 and 3 interface cases
respectively. 25 and 50 random 3 hop connections were run to simulate sparse and dense
loads respectively.

Figure 6—9 shows the results of the sparse load with 2 interfaces per node. The CCA
and single channel cases remain relatively constant because they cannot benefit from
additional available channels resources. CoSAP performance is on par with that of the
centralized case. The two algorithms are close in performance for when the number of
channels is 3 to 5. When the available channels are 6 and 7 CoSAP shows a 14% increase
in throughput. In Figure 6-10 with 3 interfaces per node, the centralized channel

assignment algorithm performs better. CoSAP performance is similar to the. centralized

59

algorithm for the 2 interface case because of the knowledge of the 3-hop neighborhood.
The 3-hop neighborhood information allows CoSAP to create a rich conflict graph when
determining channel assignments. The centralized algorithm performs better with the 3
interfaces case because the advantages of the centralized algorithm start to take effect.
These benefits were described earlier in Chapter 4, where the channel selections of the

centralized algorithm are able to better utilized the increased interfaces amount.

 

 

 

  
 
   

 

800
+Cosap
-, *Centml ......
700 +CCA

 

 

 

 

 

 

Throughput (kbps)
A
8

 

 

 

 

 

4\ p L
300 .... V...... 4/‘H .......
20° “ x V
1001. i. i ______ g
0 l l i
3 4 5 6 7
Number of Channels

 

 

Figure 6-9: Centralized sparse load comparison (2 interfaces)

60

 

1200

 

 

win-Central
*Cosap
+CCA

    
 

y—ue
l
I
fi

 

 

 

 

00

O

O
r

 

Throughput (kbps)
05
8

N
C
O
r
l
(

 

 

q|—-....

0 r r
r r

3 4 5 6 7
Number of Channels

 

 

 

 

Figure 6- 10: Centralized sparse load comparison (3 interfaces)

Similar trends in throughput can be also observed in the dense load case (Figure

6-11 and Figure 6-12).

61

 

 

Throughput (kbps)

 

 

+Cosap

+CCA

 

 

 

 

  
   

.----.o-----.-~.---.._-- o- .....

if“:

 

a
1

N
o
o
l
at

35. ...

 

100 __ ....................... .............. .............

 

 

Number of Channels

 

Figure 6-11: Centralized dense load comparison (2 interfaces)

 

 

Throughput (kbps)

A
s
l

 

1400

 

+Central
l-Cosap
+CCA
*SC

1200 4

1000

 

 

 

l

as oo
8 8

 

2m .. \. ........

  
 
  
 
 
  

 

 

 

 

Number of Channels

-—

 

Figure 6-12: Centralized dense load comparison (3 interfaces)

62

 

 

 

 

6.5 Algorithmic Performance

In this section, the presentation of the CoSAP algorithm in terms of fractional
network interference and maximum concurrent transmission is presented to further
validate the channel assignment performance. These characteristics are completely
independent of any traffic flows in the network. The performance metrics are based on
the direct channel assignments for every node in the network. Two metrics are presented
to evaluate the protocols; fractional network interference [28] and maximum network—
wide concurrent transmission. The fractional network interference is a measure of the
amount of interference that has been reduced in a network. It is the ratio of the number of
links in the resulting conflict graph after channel assignment to the number of links in the
conflict graph for the original topology. In other words it indicates the amount of reduced
interference in the network from performing channel assignments. A lower ratio indicates
a greater decrease of interference in the network. The maximum network-wide concurrent
transmission represents the maximum number of simultaneous successful transmissions
that can be preformed.

Simulations were considered with 50 nodes random distributed in a 1000m x
lOOOm area with each node having 2 and 3 interfaces. Available channels for assignment
were varied from 3 to 7 and from 4 to 8 for the 2 and 3 interface cases respectively.
Figure 6-13 shows the fractional network interference for the 2 interfaces simulation. The
CCA performance remains constant again because it cannot benefit from additional
channels. In accordance with the throughput results for 2 interfaces, CoSAP has the
lowest values. At 7 channels CoSAP is able to achieve the reduction of links to about

10% of the original conflict graph. This means that about 90% of the links that would be

63

interfering in a single channel network are removed from the conflict graph. In contrast,
Figure 6-14 shows that the centralized algorithm has a larger reduction of network
interference for the 3 interface case. This is also in agreement with the previous

throughput results for the 3 interface nodes.

 

 

0.6

 

05‘r —i. at i

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

_O
A
r
I

 

 

Fractional Network Interference
o
09

 

 

 

 

 

 

 

0.2
0.1
+Cosap .
0 i. 1
3 4 5 6 7

 

 

Number of Channels

 

Figure 6-13: Fractional network interference for 2 interfaces

 

 

7%
|>
}
I>
,1

 

 

 

0.1 "' *CCA

Fractional Network Interference

H l-Cosap ,, :
+Central

 

 

 

 

 

O

 

 

 

Number of Channels

 

Figure 6-14: Fractional network interference for 3 interfaces

The maximum concurrent transmissions simulation results are reported in Figure
6-15 and Figure 6-16. CCA maximum transmissions can only reach a maximum of
roughly 5 and 8 for the 2 and 3 interface simulation respectively. CoSAP and the
centralized algorithm both have greater values. Their maximum concurrent transmission
values are similar for both the 2 and 3 interface cases. This shows that with any number
of interfaces per node, an intelligent assignment i.e. CoSAP and central algorithm, is
consistently able to support more number of concurrent transmissions, which in turn
translates to higher effective network throughput.

The higher number of fractal network interference and allowable concurrent
transmissions for CoSAP translates into higher effective capacity, and subsequently

lower MAC as well as queuing delays compared to the CCA scenarios.

65

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Max. Concurrent Transmissions

 

 

0%
.2
E ,
E i
a . '
g 4 ......
0. *‘COSflP i
:5 l-Central i
Z 2 ~— +CCA ~

0 l l 2

3 4 5 6 7
Number of Channels
Figure 6-15: Maximum concurrent transmissions for 2 interfaces
20
18 1- , . . . . .......

 

 

 

 

 

 

 

.. *Central ...é..-_.._l..w-r_...- . , ....;.._.--..,r...-....... ..

 

 

 

 

2 .- ‘ *Cosap ‘
0 i l t
3 4 5 6 7
Number of Channels

 

Figure 6-16: Maximum concurrent transmissions for 3 interfaces

66

 

 

6.6 Connectivity Maintenance

Connectivity maintenance is an important feature of a distributed channel
assignment algorithm as discussed in Section 3.7. In this context, connectivity is
maintained when every possible link between every neighbor is assigned a channel. A
link is defined here as a connection between two nodes within transmission range of each
other. It is possible with distributed channel assignment algorithms links may not be able
to be assigned because of the interface constraint. If every link is not assigned a channel,
partitions can be introduced into the network. This will most likely reduce performance
as routes will have increased hop counts. In [17] channel connectivity is not guaranteed.

To reduce the occurrence of this issue CoSAP has two separate algorithms that
were implemented to work toward the goal of maintaining connectivity. The first
algorithm called Local Channel Set (LCS) tries to ensure that common channels are
assigned within a local neighborhood, which is discussed in detail in Section 3.5.3. This
is performed during the actual channel assignments. The second algorithm involves
reassigning channels after the initial channel assignment is performed, as discussed in
Section 3.7.

Experimental results for characterizing the channel reassignment phase of CoSAP
are reported in Figure 6-17 and Figure 6-18. Figure 6-17 results correspond to an average
of 25 CoSAP runs with 3 interfaces and 4 - 12 channels available to each of 50 randomly
distributed network nodes. Figure 6-18 results correspond to 2 interfaces and 3 - 12
channels. We simulate 4 cases to determine the performance of each connectivity
maintenance algorithms. These four cases are:

1. With LCS enabled and with channel reassignments

67

2. With LCS enabled and without channel reassignments

3. Without LCS enable and with channel reassignments

4. Without LCS enable and without channel reassignments.
In the figures, NB represents the [CS algorithm and RE represent channel reassignment
For the 3 interface case (Figure 6—17) the first two channels every link is assigned.
Afterwards the protocols begin to separate. The case with no LCS or channel
reassignments decreases with the fastest rate. Using the LCS independently provides a
greater amount of link establishments then only using the channel reassignments.
Observe that with the LCS and channel reassignment on average all links are assigned.
These results are expressed even greater with Figure 6-18 for the 2 interface case.
Without taking connectivity maintenance into consideration at 12 channels up to only
60% of the links are assigned. Also this figure shows that considering the neighbor
connectivity at the time of channel assignment performs better than performing the
reassignment after the initial channel assignments. As with the 3 interface case using both
algorithms will almost always fully assign every link. These results indicate the
effectiveness of CoSAP in terms of its connectivity maintenance through LCS filtering

and channel reassignments.

68

 

 

 

 

SD
\0
Ln
I
I

 

 

*With NB, With RE
. 'I‘With NB, No RE
+No NB, With RE

Percentage of links assigned
E; o
Ur \O
: :

 

 

 

 

   

 

 

0.8 - *No NB, NoRB
0.75 I. : : i : : 1
4 5 6 10 11

7 8 9
Number of Channels

 

Figure 6—17: Percentage of links assigned for 3 interfaced nodes

 

 

1.1

y..-

.0
so

.o
\r

NB.
NB, No RE
NB, With RE

Percentage of links assigned
S3
on

.o
as

0.5

3 4 5 6 7 8 9 10 l 1
Number of Channels

 

 

Figure 6-18: Percentage of links assigned for 2 interfaced nodes

69

 

 

6.7 Scalability of CoSAP:

Up to this point results have been shown of CoSAP performance for 50 node
networks. In this section, the scalability of the protocol is presented. Scalability is a very
attractive feature of distributed algorithms. This attribute can be lacking is most
centralized solutions because it requires large amount of data to be passed to a central
server from all the nodes in the network, which can lead to increased overhead and slow
reaction to network dynamics. The convergence characteristics of the CoSAP protocol
execution is reported in Figure 6-19. Convergence is measured as the total time taken for
network wide link establishments, normalized by the link establishment duration, as
marked in Figure 3-7. Normalized assignment durations are presented for varying
network sizes, but with a fixed network degree of 5. Total number of links, which is a

linear function of network size, is also shown in Figure 6-19.

70

 

 

 

 

 

 

 

 

 

 

 

25 . 5 , 900
at +CoSAPZ 5 E r
= ’ i 2 --
a +CoSAP2,4 ' ‘ 800
g 20 " 1+CoSAP2,3 J- 700
g ,3 *NumberofLinks
g g : T 600 g

a G

15 -~ --------- .-
g g .- 500 :fi
8 *5 a
'5 a -- 400 .t:
g a 10 --
e E -- 300 Z
a <
“5’ -- 200
a» 5 w
a -- 100
‘5 a

0 r i i 0

0 50 100 150 200
NumberofNodas

 

 

 

Figure 619: Convergence characteristics of CoSAP
Note that while the normalized convergence duration increases with the network
size, it increases with a rate slower than the number of links in the network. This is a
result of the distributed and localized nature of CoSAP, leading to channel assignments
being preformed concurrently throughout the network. This result indicates CoSAP’s

scalability with network size from an assignment convergence standpoint.

71

Chapter 7: Performance of CoSAP with Heterogeneous Spectrum
Opportunity

An important objective of cognitive networks is to operate within other networks
but not interfere with the operation of the primary network. A primary network can be
modeled in various forms. In [29] a discussion of the UHF TV bands as a possible place
for a cognitive radios to operate. The cognitive network objective in this case would be to
detect and avoid using the frequency of the UHF TV channels. Primary networks can also

be access points, cell phone towers, or other legacy network devices.

7.1 Primary users

When secondary users are not affected by primary users equally the spectrum
opportunity (SOP) of nodes becomes diversified. Nodes that are neighbors to each other
may not have the same available channels because one of the nodes has lost the use of a
set of channels due to being in the transmission range of a primary user. Because of this
occurrence heterogeneous SOPs of nodes in a network are created in this environment.
This constrains the channel assignment that can be made for each node links. To observe
the effects of primary users on a secondary network, models of different types of primary
users has been created. Then the performance of channel assignment for secondary
network of nodes that are not equally affected while in the presence of primary network
is evaluated. In our simulation models we assume primary user behavior remains constant

for a long duration of time.

72

7.2 Primary User Effects

Initially, an observation of the effects that primary users can have on a secondary
network was performed. In a 1400111 by 1400m square area, 50 nodes with transmission
and interference ranges of 250m and 550m respectively were randomly placed. These
represent secondary users of the network. Within the same area, nodes with 250m
transmission ranges are incrementally added from 0 nodes to 50 nodes at 5 node
increments. These nodes represent primary users of the network Two type’s simulations
were preformed to show the effects of the primary nodes on the secondary nodes. In the
first simulation every primary node will choose 1 channel from five different sets, namely
[3], (l — 2), (1 - 3), (1 — 4), and (1. - 5), representing a primary users with 1 interface. In
the second simulation every primary node will choose 2 channel from four different sets,
namely (1 - 2), (l - 3), (1 - 4), and (l - 5), representing a primary users with 2 interfaces.
If a secondary user is located within the transmission range of a primary user then the
secondary node cannot use the channel that the primary user chose. This leads to a

heterogeneous SOP for the secondary users in the network.

73

 

 

 

 

 

 

 

 

Terrain Size Average Amount of Secondary
Nodes Affected by a Primary Node
800m x 800m 11.8
900m x 900m 9.5
1000m x 1000m 8
1100m x 1100m 6.5
1200m x 1200m 5.8
1300m x 1300m 5
1400m x 1400m 4

 

 

 

 

Table 7-1: Average Amount of Secondary Nodes Affected by a Primary Node

Table 7-1 shows the average amount of secondary nodes that a primary user affects
as a function of terrain size. When the network size is smaller there is a larger amount of
secondary nodes affected. This result is a direct function of node degree of the network.
When the number of primary users increases the number of secondary nodes that are
affected also increases. Figure 7-1 and Figure 7-2 shows the percentage of affected nodes
as a function of the number of primary users for the network size of 1000m by 1000m.
Initially with 5 primary nodes, 60% of secondary nodes are affected. This shows that a
small amount of primary users can affect 60% of the nodes in a network. With 30 and
greater primary users in the network almost every node in the network is affected by at

least on primary user.

74

 

 

 

—
N

 

y—n

.0
oo
1

Percentage of Nodes Affected
g: o
A O‘

.0
N
l

 

Number of Primary Users

1

 

 

Figure 7-1: Percentage of affected secondary users (1 interface)

 

 

 

1.2

 

Percentage of N odes Affected
O
O\

 

5 10 15 20 25 30 35 40 45
Number of Primary Users

50

 

Figure 7-2: Percentage of affected secondary users (2 interfaces)

75

 

 

 

The last experiment shows the average amount of channels that a secondary node
would use loose from their spectrum opportunity (SOP) when in the presence of primary
users. Figure 7-3 shows the results for the 1 interface primary nodes. When primary users
are limited to selecting 1 channel, secondary nodes in the network can only lose 1
channel at most. But for larger channel sets node have the possibility of losing more
channels. For the primary user channel set (1 — 5) secondary users lost the most channels.
At most nodes lost an average of 3 channels. Figure 7-4 shows a similar figure to Figure
7-3 but it is for primary users with 2 interfaces. This means that a single primary node
will occupy 2 channels at the same time. These results show that when 2 interfaces are
used the maximum channels that can be lost are approached faster. Here at most 4
channels can be lost by secondary users.

Two conclusions can be said of these results. First the number of primary users in a
network can greatly affect the secondary users of the same network Setting up secondary
networks in a densely populated primary user networks can create many negative effects
on the secondary users. The second statement that can be made from the results is that
secondary users may need to have access to mutually exclusive channels than that of

primary users. This will allow secondary users to still communicate effectively.

76

 

 

 
 

4 *PriChanS
3.5 __ , +PnChan3

 

 

*PriChan4 ..

 
 
 

*mCharlz .k...a.: ...t......:.,,..,,, : I

 

\

 

 

 

 

 

 

Average Amount of Channels Lost

 

 

 

i I i r

l l

 

 

20 25 30 35
Number of Primary Users

 

40 45 50

 

Figure 7-3: Average amount of channels lost by secondary users (1 interface)

 

 

 

*Pri Chan5

 

+Pri Chan 4
4 " 'I-Pri Chan 3

 

 

 

+PriChan2 . .

 

     

 

 

Average Amount of Channels Lost

 

 

 

 

 

 

0.5 _.. .............................
O l i I l | l i l
5 10 15 20 25 30 35 40 45 50
Number of Primary Users

 

 

Figure 74: Average amount of channels lost by secondary users (2 interfaces)

77

 

7.3 Different Primary Users Types Simulations

The previous experiments observed the effects of primary nodes on secondary users
in a network. The primary users were represented as randomly distributed nodes in the
network. Primary users will consist of many different types of networks. They will have
different distributions, purposes, and amounts. Experiments were performed to model
two different primary user deployments. First is an access point case, in which access r
points are placed in random locations and channels are chosen for each access point.
Within the access point case there are two distributions; random and smart. In the random

access point case access points randomly choose channels for their interfaces. For the

 

F-

smart distribution, nodes try to minimize their interference. The second type of primary
user is a mesh network. Primary nodes here must be connected to each other.
TCP Experiments where run to evaluate the performance of CoSAP and the
centralized algorithm. The TCP results are reported for the secondary users.

Table 7-2 shows the simulation setup of the TCP primary user simulations.

78

 

 

 

 

 

 

 

 

 

 

 

Parameter 2 Interface Secondary Nodes 3 Interface Secondary Nodes
Terrain 1000m x 1000m 1000m x 1000m
Secondary Nodes 50 50
Primary Nodes 0 - 50 (at 5 node steps) 0 — 50 (at 5 node steps)
Available Channels 5 7
Primary interfaces 1, 2 1, 2
Primary Set 1 - 3 l - 5
Secondary Interfaces 2 3
TCP Connections 3 hops 3 hops
Number Connections 50 50

 

 

 

Table 7-2: Primary users TCP simulation setup
For the heterogeneous simulations, the centralized algorithm has knowledge of all
of the spectrum opportunities (SOP) for every secondary node in the network. Because
CoSAP is a distributed protocol it must discover the SOP of its neighboring nodes
through hello messages. CoSAP has knowledge of its three hop neighbors SOP so that it

can create the conflict graph for channel assignment.

7.3.1 Random Access Points Case

Primary users in the Random Access Point (RAP) case are modeled as access
points that are randomly distributed in an environment. Each access point randomly
chooses a channel to communicate with its end users i.e. laptops and Wi-Fi devices.
Figure 7-5 in an example of the RAP case. In this example every nodes initial SOP is 1,

2, 3 and each access point can randomly chose a channel between 1, 2, and 3. Nodes l

79

 

 

and 2 will both lose channel 2 from their SOP because they are in the range of access
points that have chosen to use channel 2. Nodes 2 and 3 will still be able to communicate
even though they are in the range of different access points because they have common

channel 3.

 

 

 

 

 

Figure 7-5: Random Access Point Case

Figure 7-6 and Figure 7-7 shows the results from the TCP simulations of the RAP
case. The results show as expected that as the number of primary nodes increases the
throughput of the secondary nodes decreases. Initially the secondary nodes have use of
most of the channels available for channel assignment, signifying larger SOPs. But as the
number of primary users increases the SOP decreases. In Figure 7-6 the primary users
have only 1 interface, therefore the SOP of the secondary users’ decreases at a slower
rate, as compared to Figure 7-7 where the primary users have 2 interfaces. In 2 interface
primary case the throughput drops significantly as the more primary users are in the

network.

80

 

 

 

+Central 3 IF

'I'Cosap 3 IF

‘ +Central 2 IF
*Cosap 2 IF

   

 

 

 

  
    

Throughput (kbps)

 

 

 

 

 

 

 

0 5 10 15 20 25 30 35 40 45 50
Number of Primaflisers

 

 

 

Figure 7-6: RAP case TCP results (1 interface primary)

 

 

 

l _ 1+Central3IF ,
*Cosap 3 IF
3 ' +Centra121F ‘
; , - *Cosap2IF

 

 

 

 

 

 

 

 

0 : i l : : l l : :
0 5 10 15 20 25 30 35 40 45 50
Number of Primary Users

 

 

Figure 7-7: RAP case TCP results (2 interface primary)

81

 

7.3.2 Smart Access Points Case

Primary users of the Smart Access Points Case (SAP) try to minimize interference
when selecting channels. This is different from the RAP case for the reason that in the
RAP case access points do not care about the interference when channels are selected.
Each access point in the SAP case avoids using the same channels as other access points.
The access points choose the least used channel within their interference range. Figure
7-8 gives an example of the SAP case. The three access points in the example choose
channels 1, 2, and 3 to minimize interference. As a result of this assignment node 1 being
in range of two access points loses channels 2 and 3 from its SOP, while node 2 only
loses channel 3. This demonstrates how primary users can limit the availability of

channels for secondary users.

 

 

 

 

 

Figure 78: Smart Access Point Case
In the SAP case primary nodes try to minimize the interference that is experienced
on their interface. The effect of this type of primary node is that it can create more
diversity in the SOPs of the secondary nodes. The reason for the increased diversity is

that the access points are trying to seek out different channels for their interfaces. Figure
82

 

7-9 and Figure 7-10 shows the results from TCP experiments. Similar to previous results

the throughput decrease happens faster when the primary users have 2 interfaces.

 

 

+Central3IF

l-Cosap3IF '
i i 5 E I ; +Centra12IF
800 __ ., .. ... ... .. , 1"” *Cosa2lF

    

Throughput (kbps)
Ur
O
O

 

 

 

 

 

. . r
. , , .

0 I I I l I; I I; l I
l I r I I I l I I

0 5 10 15 20 25 30 35 40 45 50
Number of Primag Users

 

 

 

Figure 7-9: SAP case TCP results (1 interface primary)

83

 

 

 

 

 

 

 

0 41 A; A; r g i 1 4L 4

 

 

 

 

0 5 10 15 20 25 30 35 40 45 50
Number of Primary Users

 

Figure 7-10: SAP case TCP results (2 interface primary)

7.3.3 Mesh Network Case

In this case primary users are modeled as mesh network routers [30]. In the
previous two cases each access point has no concerns about maintaining a connection
with other access points. On the other hand, for mesh networks this is a necessity. Mesh
networks usually have a gateway that nodes must connect to or are connected to other
nodes for peer to peer connections. A centralized algorithm is run to perform channel
assignment for the interfaces of the mesh routers in the network. Figure 7-11 shows an
example of the mesh network case. In this example each mesh router has two interfaces
which can be assigned to any channel in the set 1, 2, 3, and 4. Every mesh router is able

to have a common channel for communication in this case.

84

 

 

 

 

 

Figure 7-11: Mesh Network Case

In this case primary nodes must be connected which requires all neighboring nodes
to use a common channel. This is unlike the SAP case where primary users essentially
avoid each other. The mesh network case leads to a less diverse SOP for the secondary
nodes. The decrease in diversity is a result of the interface constraint of the nodes, which
requires nodes to use the same channels on their interfaces. In Figure 7-12, which is
where the primary nodes have 1 interface, the primary can only use 1 channel. If not then
they will have partitions in the network. The results show that the throughput decreases
very slowly as the number of primary user’s increases. Every secondary node will only
lose a maximum of 1 channel. For the 2 interface case, Figure 7- 13, nodes can lose more

channels in their SOP but it is as a reduced rate.

85

' in l‘h‘ MAB"

 

 

 

 

O

 

 

 

+Central 3 IF
" ‘l-Cosap 3 IF
+Central 2 IF
. , . *Cos 2 IF

 

 

 

 

 

I l
I I I I I

15 20 25 30 35 40 45 50
Number of Primary Users

 

Figure 7-12: Mesh network case TCP results ( 1 interface primary)

 

1200

 

é

Throughput (kbps)

 

  
     

 

+Centra13 IF

, ‘l-Cosap 3 IF

+Centra12 IF
*Cosap 2 IF

 

 

 

 

I l I I I

 

 

15 20 25 30 35 40 45 50
NumberofPrimaryUsers

 

 

Figure 7-13: Mesh network case TCP results (2 interface primary)

86

 

7.3.4 Comparison of Primary User Cases

The three different types of primary users affect the secondary network in different
ways. The smart access point (SAP) case increases the diversity of the spectrum
opportunity (SOP) of the secondary users. It does this by the primary users’ attempts to
fully explore the available channels, therefore increasing the difficulty of secondary
nodes ability to find unused channels. On the other hand the mesh network case reduces
the diversity of the SOP because of the need of the mesh routers to satisfy the interface
and connectivity constraints. The random access point case gives a middle ground
between the other two cases.

Figure 7-14 and Figure 7-15 shows the comparison between the three cases. The
results shown are for CoSAP with 3 interfaces per node. The graphs show that the mesh
networking case has the best performance when compared to the other cases. The smart
access point case caused the least amount of performance for the secondary network. This
result is seen in both the 1 and 2 interface case. From these results, it can be said that
different primary networks can have varying impacts on a secondary networks. Also
primary networks that could work with secondary networks may be able to improve the

throughput of the secondary network.

87

 

 

“A ‘..

 

 

 

Thoughput (kbps)

§

 

é"

 

 

 

 

 

 

 

700 '. : 4. r l l i r l
0 5 10 15 20 25 30 35 40 45
Number of Primary Useg

 

 

Figure 7-14: Comparison of primary user types (1 interface primary)

 

 

1300

Throughput (kbps)
‘° 8 S
8 o o

on

O

O
l

700 -

 

I : ' =1 5
1200 _ .... .... .........._..... .;..........1...,............_H..........._. . .. ”US... l... P. . ._ ..

 

 

 

600 l : i : l l r i r
0 5 10 15 20 25 30 35 40 45
Number of Primary Users

 

 

 

Figure 7-15: Comparison of primary user types (2 interfaced primaries)

88

 

 

Chapter 8: Conclusions

8.1 Conclusions

In this thesis, a distributed and localized channel assignment protocol CoSAP,
which can be used for network capacity enhancement in a cognitive network environment
with spectrum opportunities is introduced. The operation of the cognitive network
involves the detection of available channels that are not being used for communication by
primary users. Once these channels are known the decision of how to utilize these
channels to maximize network throughput, arises. CoSAP takes advantage of multiple
interfaces and multiple channels which provide many benefits over single channel single
interfaced hardware. In the CoSAP algorithm each node uses collaborative sensing
through exchanging information with its 1-hop neighbors to leam about its m-hop
neighborhood. A node broadcasts hello messages containing information [available
channels, interface count, current channel-to-interface assignment] about up to its m-hop
neighbors. A node receiving this information can create the connectivity graph, and a
conflict graph for each channel in its m-hop neighborhood. This graph information is then
used by the node for channel-to-interface assignments with minimized interference for its
links. The mechanism is localized because a node relies on information only from its
local m-hop neighborhood, and it is distributed because each node computes its own
version of the neighborhood conflict graph and channel-to-interface allocation for its own
radio interfaces.

CoSAP is designed to perform the channel assignment for secondary users that
minimizes or eliminates any interference that secondary users may cause on the primary

network while maintaining a usable network for the secondary users. CoSAP supports
89

 

heterogeneous SOPs which are representative of the diversity of the SOP from the
secondary users’ point of view as a result of primary users’ selection of channels. In
addition to the protocol description, an ns-2 based simulation model is utilized to evaluate
CoSAP’s performance and to compare it with a Common Channel Assignment (CCA)
strategy and a centralized channel assignment for benchmarking. The results indicate that
CoSAP can achieve significant interference reductions, and subsequent capacity
enhancements, for both local UDP traffic and global TCP traffic. Furthermore, CoSAP
was shown to effectively perform channel assignments in networks with different

primary user deployments.

8.2 Future Work

Future work on this topic will include the extension and evaluation of the CoSAP
framework for handling time and space varying dynamic spectrum opportunities. In
addition, extending of the CoSAP framework with the design of a cognitive network
routing protocol and MAC protocol to provide a fully cross layer solution for cognitive

networks will be performed.

90

Chapter 9: Appendix

This chapter presents results for various simulations.

9.1 Homogeneous UDP Simulations

 

 

 

*COSAPZ, 5 ;
.i-CoSAP2,4 _
*CoSAP2, 3 5
*CCAB
*CCAZ
+sc

   

\I
r

 

 

O‘
LAT

 

UI

 

 

U)
r
1

Throughput (Mbps)
&
\\

 

 

 

 

i i L
I r 1

O

l 1
r I

0 4 8 12 16 20 24 28 32
Load (Mbps)

 

 

 

Figure 9-1: l-hop throughput with 2 interfaces per node (degree 5)

91

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

16 -l-....... .........
14 -_ . 3 . , . _ .. ._. . ________ ______ ’
I § A I
12 -_ ....... .. Tr ... .
a .
£10 __ ........
E”
— 8 __ .......................
B
6 _-
4 __ ......
2 -. ,,,,,, *CoSAP2,3 _____
*CoSAP2,4
0 . , , +CoSAP2,5
0 4 12 16 20 24 28 32
Imam
Figure 9-2: Packet Delivery Delay for l-hop traffic (degree 5)
12
+CoSAP3,6
l-CoSAP3,5 :
‘0 l+cOSAP3,4
A *CCA3 ,
Es - *SC
516 --
.fl
3"
E
g 4 _.. .......................
2 .— 2. v V——-—-——>:" X X
0 r l l l r i l
0 4 8 12 16 20 24 28 32
Load(Mbp§)

 

 

Figure 9-3: l-hop throughput with 3 interfaces per node (degree 5)

92

 

 

 

 

Delay (Sec)

u—n
N

p—s
O

00

O\

 

 

 

 

 

    

 

 

 

 

_- ............ +sc
' . *CCA3
E +CoSAP 3, 4
T ‘f """"" *CoSAP3, 5 ’
, 1 . . . . *CoSAP3, 6

 

 

 

 

16
Load (Mbps)

20

28

32

 

Figure 9-4: Packet Delivery Delay for 1-hop traffic (degree 5)

 

 

Throughput (Mbps)

(J!

k

b.)

N

...n

 

— +COSAP 2, 3

- *CCAZ

 

+COSAP 2, 5
'I-CoSAPZ, 4

*CCA 3

 

'O-SC

 

 

 

I ' .' i . .
l I I l l %

 

l

 

 

12 16 20
Load (Mbps)

24

I

28

32

 

Figure 9-5: l-hop throughput with 2 interfaces per node (degree 7)

93

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

18 ~-
16 ‘-
14 -—
6‘12 --
:3.
>10 -
2
3 8 ——
6 __
4 " E
2 4—
0 i r
0 4 8 12 16 20 24 28 32
Load(Mbps)
Figure 9-6: Packet Delivery Delay for l-hop traffic (degree 7)
l2
*CoSAP3,6
'I‘COSAP3,5
10 ‘ +COSAP3,4 " ' t
*CCA3 I
53 - *SC -
p
2.6 --
'Er .
s a
$24-- .-
2 -- .. 4.4
0 : i l 4; 1 i :
0 4 8 12 16 20 24 28 32
Load(Mbps)

 

Figure 9-7: l-hop throughput with 3 interfaces per node (degree 7)

94

 

 

 

 

 

DelaflSeg)

ON-P-ONOO

ON

 

 

 

 

 

 
    

 

+SC
l-CCAS
+CoSAP3, 4
*CoSAP3, 5
*CoSAP3, 6

 

 

 

 

 

 

 

 

I I I I I I

 

4 8 12 16 20 24 28 32
Load (Mbps)

 

Figure 9-8: Packet Delivery Delay for l—hop traffic (degree 7)

95

 

 

9.2 TCP Experiments

 

100%
90%
5 80%

Q
g; 70%
>

 

 

 

 

+CoSAP2,5 .
+CoSAP2, 3 ' ‘

 

 

 

 

 

 

I
‘-.-..-..:.v--o~t \
1

1
r

4 5
Number of Hops

 

Figure 9-9: Percentage increase with 2 interfaces over CCA (degree 4)

96

 

 

 

 

Percentage Increase Over CCA
o o 3 o o
89 89 89 as 68

80%

 

70% A

0‘

UI

 

   

-_ I
r

 

+COSAP3, 6 '
‘I-CoSAP 3, 5 .

 

 

 

 

 

3 ..................................................................
2
10% <
0% l l I.
l 3 4 5 6
Number of Hops

 

Figure 9—10: Percentage increase with 3 interfaces over CCA (degree 4)

 

 

Percentage Increase Over CCA

70%

 

60%-'

50% ‘
40%
30%

20%

10% --

 

0%

 

 

+COSAP2, 5
‘ 'I'CoSAP2, 4
+COSAP2,3

 

 

 

 

3 4 5 6

Number of Hops

 

Figure 9-11: Percentage increase with 2 interfaces over CCA (degree 5)

97

' +CoSAP3,4

 

 

 

 

 

 

Percentage Increase Over CCA

 

 

 

 

 

 

 

 

 

; +C0SAP3,6 ,~ .
60% ' “““““““ """""" a-cOsAp3,5
+C0SAP3,4
40%
30%
20%
10%
0% i + i i i 1‘
1 2 3 4 5 6 7 8

Number of Hops

 

 

 

 

Figure 9-12: Percentage increase with 3 interfaces over CCA (degree 5)

98

Fm-..

[1]

[2]

[3]

[4]
[5]

[6]

[7]

[8]

[9]

[ICU

[11]

[12]

[13]

[14]

Bibliography

G. Staple and K. Werbach, "The end of spectrum scarcity," in IEEE Spectrum.
vol. 41, Mar. 2004, pp. 48-52.

R. W. Thomas, L. A. DaSilva, and A. B. MacKenzie, "Cognitive networks," in
New Frontiers in Dynamic Spectrum Access Networks, 2005, pp. 352-360.

I. 802.11b/D3.0, "Wireless LAN Medium Access Control (MAC) and Physical
(PHY) Layer Specification," 1999.

FCC, "Spectrum policy task force report," ET Docket No 02-135, Nov 2002.

S. Haykin, "Cognitive radio: brain—empowered wireless communications," IEEE
Journal on Selected Areas in Communications, vol. 23, pp. 201-220, Feb. 2005.

I. Akyildiz, W. Lee, M. Vuran, and S. Mohanty, "Next generation dynamic
spectrum access for cognitive radio networks: A survery," IEEE Computer
Networks, May 2006.

C. Ramming, "Cognitive networks," in DARPATech 2004, 2004.

P. Pawelczak, R. V. Prasad, L. Xia, and I. G. M. M. Niemegeers, "Cognitive radio
emergency networks - requirements and design," in DySPAN 2005, Nov. 2005.

L. Berlemann, S. Mangold, and B. H. Walke, "Policy-based reasoning for
spectrum sharing in cognitive radio networks," in IEEE DySPAN 2005, 2005.

R. Ramanathan and R. Rosales-Hain, "Topology control of multihop wireless
networks using transmit power adjustment," in IEEE INFOCOM, 2000.

M. Buddhikot, P. Kolodzy, S. Miller, K. Ryan, and J. Evans, "DIMSUMNet: new
directions in wireless networking using coordinated dynamic spectrum access," in
IEEE Wo WMoM, June 2005.

R. Yates, C. Raman, and N. Mandayarrr, "Fair and efficient scheduling of variable
rate links via a spectrum server," in IEEE ICC, Jun 2006.

M. Marina and S. Das, "A topology control approach for utilizing multiple
channels in multi-radio wireless mesh networks," in 2nd International Conference
on Broadband Networks, Oct. 2005.

P. Gupta and P. Kumar, "The capacity of wireless networks," IEEE Transactions
on Information Theory, vol. 46, March 2000.

99

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[23]

K. Ramachandran, E. Belding, K. Almeroth, and M. Buddhikot, "Interference-
aware channel assignment in multi-radio wireless mesh networks," in IEEE
Infocom, 2006.

A. Raniwala and T. Chiueh, "Architechure and algorithms for an IEEE 802.11
based multi-channel wireless mesh network," in IEEE Infocom, 2005.

B. K0, V. Misra, J. Padhye, and D. Rubenstein, "Distributed channel assignment
in multi-radio 802.11 mesh networks," in IEEE Wireless Communications and
Networking Conference, March 2007.

Q. Wang and H. Zheng, "Route and spectrum selection in dynamic spectrum
networks," in Consumer Communications and Networking Conference, Jan. 2006.

M. Gong, S. Midkiff, and S. Mao, "Design principles for distributed channel
assignment in wireless adhoc networks," in IEEE International Conference on
Communications, May 2005.

C. E. Perkins and E. M. Royer, "Ad-hoe on-demand distance vector routing," in
Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and
Applications New Orleans, LA, Feb. 1999, pp. 90— 100.

P. Mahonen, M. Peu'ova, and J. Riihijarvi, "Applications of topology information
for cognitive radios and networks," in DySPAN, April 2007.

J. Zhao, H. Zheng, and G. Yang, "Distributed coordination in dynamic spectrum
allocation networks," in DySPAN, Nov. 2005.

W. Wang and X. Liu, "List-coloring based channel allocation for open-spectrum
wireless networks," in Vehicula technology Conference, Sept. 2005.

C. Peng, H. Zheng, and B. Zhao, "Utilization and fairness in spectrum assignment
for opportunistic spectrum access," Mobile Networks and Applications, vol. 11,
pp. 555 - 576, 2006.

P. Kayasanur and N. Vaidya, "Routing and interface assignment in multi-channel
and multi-interface wireless networks," in Wireless Communications and
Networking Conference, March 2005.

R. A. Calvo and J. P. Campo, "Adding multiple interface support in n32," Jan.
2007.

http://www.isi.edu/nsnam/ns/doc/index.htrnl, "The ns Manual."

A. P. Subramanian, H. Gupta, and S. R. Das, "Minimum interference channel
assignment in multi-radio wireless mesh networks," in SECON 2007, Jun. 2007.

100

 

[29] D. Cabric, S. M. Mishra, and R. W. Brodersen, "Implementation issues in
spectrum sensing for cognitive radios," in Signals, Systems and Computers, Nov.
2004.

[30] I. F. Akyildiz and W. Xudong, "A survey on wireless mesh networks," Sept.
2005.

101

 

llllllllllfllflllflflfll

lllllllllllllll

V
956 2976

      

4.“;
1‘}?!