Microwave Weewr

Journal of Network and Computer Applications 45 (2014) 79–95
Contents lists available at ScienceDirect
Journal of Network and Computer Applications

journal homepage: www.elsevier.com/locate/jnca
Review
Clustering algorithms for Cognitive Radio networks: A survey

Kok-Lim Alvin Yau a,n, Nordin Ramli b, Wahidah Hashim b, Hafizal Mohamad b
a
Faculty of Science and Technology, Sunway University, No. 5 Jalan Universiti, Bandar Sunway, 46150 Petaling Jaya, Selangor, Malaysia
b
Wireless Network and Protocol Research Laboratory, MIMOS Berhad, Technology Park Malaysia, 57000 Kuala Lumpur, Malaysia
ar t ic l e i nf o a b s t r a c t
Article history: Cognitive Radio (CR) networks enable unlicensed or Secondary Users (SUs) to sense for and operate in the
Received 16 August 2013 underutilized spectrum (or white spaces) owned by licensed or Primary Users (PUs) without causing
Received in revised form unacceptable interference to the PUs' activities. Clustering, which is a topology management mechanism,
17 June 2014
organizes nodes into logical groups in order to provide network-wide performance enhancement. Clustering
Accepted 21 July 2014
aims to achieve network scalability and stability, as well as to support cooperative tasks, such as channel
Available online 1 August 2014
sensing and channel access, which are essential to CR operations. While clustering has been well investigated
Keywords: in traditional networks such as mobile ad hoc networks, similar investigations in CR networks remain in the
Cognitive Radio infancy stage. New clustering algorithms must be designed to address new challenges associated with the
Software defined radio
intrinsic characteristics of CR, namely the dynamicity of channel availability that changes with time and
Topology management
location. This article reviews clustering algorithms, and they are characterized by clustering objectives,
Clustering
Routing metrics and the number of hops in each cluster. We also present complexity analysis, performance
enhancements achieved by the clustering algorithms, as well as open issues, in order to establish a
foundation for further research and to spark new research interests in this area.
& 2014 Elsevier Ltd. All rights reserved.
Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
1.1. Cognitive radio: an overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
1.2. Clustering: an overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
1.3. Clustering in cognitive radio networks: advantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
1.4. Clustering: challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2. Taxonomy of clustering attributes in cognitive radio networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2.1. Clustering objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2.2. Clustering characteristics. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3. Clustering algorithms in cognitive radio networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.1. Establishment of common control channel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.1.1. Li's node ranking approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.2. Enhancement on cluster stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.2.1. Huang's node importance degree approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.2.2. Baddour's affinity propagation message-passing approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.2.3. Connectivity degree approach. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.2.4. Bipartite graphs approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.3. Enhancement on energy efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.3.1. Zhang's group-wise constrained approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.3.2. Ozger's event-driven approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.4. Enhancement on cooperative tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.4.1. Wei's contribution decision approach. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
n
Correspondence author. Tel.: þ 60 3 7491 8622x3216.
E-mail addresses: koklimy@sunway.edu.my (K.-L. Yau),
nordin.ramli@mimos.my (N. Ramli), wahidah.hashim@mimos.my (W. Hashim),
hafizal.mohamad@mimos.my (H. Mohamad).
http://dx.doi.org/10.1016/j.jnca.2014.07.020
1084-8045/& 2014 Elsevier Ltd. All rights reserved.
80 K.-L.A. Yau et al. / Journal of Network and Computer Applications 45 (2014) 79–95
4. Performance enhancements and complexity analysis of clustering algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

4.1. Performance enhancements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.2. Complexity analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5. Open issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.1. Cluster maintenance: migration of clusterhead, cluster merging, cluster splitting, node joining and node leaving. . . . . . . . . . . . . . . . . . 93
5.2. Common assumptions in cognitive radio networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.3. Tradeoff between various network performance metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.4. Gateway's schedule for intra-cluster and inter-cluster communications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.5. Effects of clustering to cognitive radio schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.6. Optimal cluster size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.7. Other open Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
Acknowledgment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
1. Introduction performance enhancements, complexity analysis (i.e. time and

message complexities), as well as open issues. It focuses on
Cognitive Radio (CR) (Akyildiz et al., 2006) enables unlicensed clustering algorithms, particularly clustering metrics and how
users (or Secondary Users, SUs) to sense for licensed users' (or these metrics have been applied to form clusters in CR networks,
Primary Users, PUs) underutilized channels (called white spaces), rather than application schemes that apply the cluster structure
and subsequently uses the channels in an opportunistic manner such as cluster-based routing that focuses on the enhancement of
conditional on the interference to the PUs being below an routing rather than clustering (Talar and Altilar, 2011), and it does
acceptable level. IEEE 802.22 is a standard for CR networks that not focus on the traditional coordination mechanisms for cluster-
uses white spaces in the television frequency bands; and it is ing algorithms because there has been a considerable amount of
designed for centralized networks comprised of base stations and literature being published in the context of mobile and static ad
wireless hosts (or Customer Premise Equipment (CPE)) (Fan and hoc (or mesh) networks. Since clustering algorithms have been
Rocky, 2009). A distributed Cognitive Radio network is comprised traditionally incorporated into the network layer to form clusters,
of a number of SUs who communicate with each other in the which help to limit the flooding of routing overheads (e.g. Route
absence of fixed network infrastructure such as an access point or Request and Route Reply) throughout the entire network
a base station. This article focuses on clustering in distributed CR (Ephremides et al., 1987; Jeng and Jan, 2007), the other layers
networks. such as the application and physical layers are not discussed in this
Clustering organizes nodes into clusters in order to provide article. Additionally, the contributions are to The purposes of this
network-wide performance enhancement. Generally speaking, there article are to establish a foundation and to spark new interests in
are three main advantages brought about by clustering to CR net- this emerging research area. Note that, for simplicity, the terms
works, namely scalability, stability, and supporting cooperative tasks, SUs and nodes are used interchangeably throughout the entire
such as channel sensing and channel access, which are essential to CR article. The organization of this article is as follows. The rest of
operations, and these advantages have led to the use of clustering in Section 1 presents an overview of CR networks, as well as an
CR networks. An intrinsic characteristic of CR networks that warrants overview, advantages and challenges of clustering in CR networks.
further investigation on clustering is dynamicity of channel availability Section 2 presents taxonomy of the attributes of clustering algo-
in which the channel availability (or white spaces) of each SU is rithms in CR networks. Section 3 presents various clustering
different, and it changes with the level of PU activities, time and algorithms in CR networks, as well as to relate them to the
location. Popular traditional clustering algorithms, such as lowest ID attributes of clustering algorithms presented in Section 2.
(Ephremides et al., 1987) and maximum node degree (Jeng and Jan, Section 4 presents performance enhancements achieved by clus-
2007), may not be suitable, and so various new clustering algorithms tering algorithms. This section also presents complexity analysis of
have been proposed. The lowest ID clustering algorithm selects a node the clustering algorithms. Section 5 presents open issues. Section 6
with the lowest ID as the leader of a cluster (or clusterhead); while the presents conclusions.
maximum node degree clustering algorithm selects a node with the
highest number of neighbor nodes as the clusterhead. There are three 1.1. Cognitive radio: an overview
reasons why traditional clustering algorithms applied to wireless ad
hoc and sensor networks (Peiravi et al., 2013; Lee and Lee, 2013; Khan The traditional spectrum allocation policy has been partitioning
et al., 2011) are not suitable for CR networks. Firstly, the algorithms do radio spectrum into smaller ranges of licensed and unlicensed
not adapt to the channel dynamics in CR networks. Secondly, the frequency bands (also called channels). The licensed channels,
algorithms may not achieve objectives specific to CR networks. For which are auctioned off by the government, provide exclusive
instance, a common channel may not be established due to the lack of channel access to PUs. SUs, such as the popular wireless commu-
white spaces, so some nodes in a cluster may not be able to nication systems IEEE 802.11, are forbidden to access any of the
communicate with the clusterhead. Thirdly, the algorithms may not licensed channels. Instead, they access unlicensed channels with-
enhance network performance pertinent to CR networks such as out incurring any monetary cost.
achieving a higher number of common channels in a cluster, and Cognitive Radio enables SUs to sense radio spectrum and use
application-specific network performance, such as achieving lower white spaces whilst minimizing interference to PUs. The purpose
error probability in channel sensing outcomes. is to improve the availability of bandwidth at each SU, and hence
The main contribution of this article is to present an extensive improving the overall utilization of radio spectrum, which is one of
review on the various aspects of clustering algorithms in distrib- the scarcest resources in wireless communications. The main
uted CR networks, including clustering objectives, clustering difference between CR and the traditional wireless networks is
characteristics (i.e. metrics and intra-cluster distance), the presence of PU activities in CR networks; hence the main
K.-L.A. Yau et al. / Journal of Network and Computer Applications 45 (2014) 79–95 81
challenge of CR is to establish a “friendly” environment, in which (Rayment et al., 2009) and Korea (Kim et al., 2010), respectively. CR
the PUs and SUs coexist without causing interference with each has become more and more prevalent since the digital television
other as shown in Fig. 1. In Fig. 1, a SU switches its operating switchover has completed in year 2009 in US and 2012 in UK
channel across various channels from time to time in order to (Nekovee, 2008) with some CR products (e.g. xG technology
utilize white spaces in the licensed channels. Note that, each SU (2013)) emerging in the market.
may observe different white spaces, which are time and location Recently, there has been growing research interest in Cognitive
dependent. For a successful communication, a particular white Radio Sensor Network (CRSN). CRSN incorporates CR capability
space must be available at both SUs in a communication node pair. into the traditional Wireless Sensor Networks (WSNs) so that each
Opportunistic spectrum access, which can be realized using CR, sensor node can sense radio spectrum and use white spaces (Ozger
has been approved in 2004 in US through Notice of Proposed Rule and Akan, 2013) while detecting and monitoring physical and
Making (NPRM) by Federal Communications Commission (FCC) environmental events. Generally speaking, in CRSNs, each sensor
(2006), and in 2007 in UK through Digital Dividend Review (DDR) node inherits important characteristics of WSNs, particularly
by Office of Communications (Ofcom) (2007). Upon completion of the limitation of hardware and energy resources. Hence, one of
the digital television switchover, which replaces the analog the main objectives of CRSNs is to reduce energy consumption.
terrestrial TV services with the digital terrestrial TV services called The main difference between CRSNs and the traditional CR net-
Digital Video Broadcasting – Terrestrial (DVB-T), there will be works is that, data packets are generated by nodes that have
vacant spectrum called digital dividend. In UK, opportunistic detected event(s) and are sent to a sink node; while in the
spectrum access has been proposed in the award of digital traditional CR networks, data packets may be generated by any
dividend, and no digital dividend will be awarded exclusively to nodes and are sent to a base station.
licensed users (Office of Communications (Ofcom), 2007), which
has strengthened the essential role of CR in the near future. There 1.2. Clustering: an overview
are approximately 128 MHz and 90 MHz of digital dividend in UK
Clustering, which is a topology management mechanism,
organizes nodes into logical groups (or clusters) in order to
provide network-wide performance enhancement. Figure 2 shows
an example of a cluster structure in which nodes in a CR network
are grouped to form clusters. Note that, the formed cluster
structure depends on the underlying network, such as the location
and channel availability (or white spaces) of the nodes. The SUs
form three clusters (i.e. C1, C2, C3). Each cluster comprises three
kinds of nodes, namely clusterhead, member node and gateway
node. A clusterhead (i.e. CH1, CH2, CH3) serves as a local point of
process for various applications such as channel sensing, which is
essential to CR operation, and routing. A member node associates
itself with a clusterhead. For instance, member nodes M1,1, M1,2,
M1,3, M1,4, M1,5 are associated with clusterhead CH1. Clusterhead
Fig. 1. A SU exploits white spaces across various channels. and member nodes communicate regularly among themselves,
Fig. 2. A cluster structure in a CR network consists of PUs and SUs.

and these are called intra-cluster communications. The gateway so it forms a cluster itself and becomes a clusterhead. Secondly, the
nodes, which are the member nodes located at the fringe of a node receives beacon only, and so it becomes a member node of
cluster, can hear from neighboring clusters, and so they provide the respective clusterhead. Thirdly, the node receives message
inter-cluster communications. For instance, gateway node M1,2 is only, and so it is located two hops away from the clusterhead;
associated with clusterhead CH1, and it provides inter-cluster subsequently, it switches to another channel in search of a single-
communications for clusterheads CH1 and CH2. Since the neigh- hop clusterhead, and if it still fails to join any clusters, it may
boring clusters may use distinctive channels, which is common- become a clusterhead itself. A clusterhead discovers its neighbor
place in CR networks, a gateway node may need to switch its clusters, which may be a single, two or three hops away, and
operating channel regularly. The clusterheads and gateway nodes subsequently selects gateway nodes to form inter-cluster commu-
form a backbone to the base station. For instance, in Fig. 2, nodes nications. Nodes in a cluster switch from channel to channel in
M1,5–CH1–M1,2–CH2–M3,3–CH3–SU BS form a backbone. The num- order to discover neighboring clusters, and exchange information
ber of hops between member nodes and clusterhead in a cluster with them. Generally speaking, the clusterhead assumes several
(or cluster size) may be a single, two (Huang et al., 2011) or more. roles, including coordinating the member nodes and serving as
The main difference among the clustering algorithms is the a local point of process for essential applications including channel
cluster formation procedure, which generally comprises cluster- sensing, channel access and routing (Talay and Altilar, 2013; Liming
head selection and member node joining. A node initiates the cluster et al., 2012). Hence, the clusterhead incurs higher energy consump-
formation procedure whenever it fails to find any clusters nearby. tion compared to member nodes, and so the clusterhead role may be
Local information, such as a list of available channels, is exchanged rotated among nodes in a cluster. A considerable amount of literature
among neighboring nodes to form clusters in line with some has been published on coordination mechanisms for clustering
global objectives, such as higher number of common channels in a algorithms in the context of mobile and static ad hoc (or mesh)
cluster and higher network-wide throughput (Badoi et al., 2011). networks. The rest of this article focuses on clustering algorithms,
During the clusterhead selection procedure, a clusterhead is such as the use of clustering metrics in clusterhead selection and
elected from nodes in a cluster based on certain clustering metrics, member node joining, in the context of CR networks.
such as channel availability. For instance, a clusterhead has the
highest number of single-hop neighbor nodes (or node degree 1.3. Clustering in cognitive radio networks: advantages
level) in Jeng and Jan (2007) and Badoi et al. (2011), and the lowest
node ID in Ephremides et al. (1987). In Huang et al. (2011), a There are three main advantages associated with clustering in
clusterhead has higher node degree level, as well as lower number CR networks: scalability, stability and cooperative tasks support.
of hops and number of channel switches from member nodes to the Firstly, clustering improves scalability through the reduction of
clusterhead. During the member node joining procedure, a node communication overhead and parallelism. Traditionally, in non-
chooses a cluster to join based on some criteria, such as the number clustered networks, nodes exchange information with all other
of common channels between a node and a cluster (Badoi et al., nodes in the networks. However, in clustered networks, clusterheads
2011). Higher number of common channels in a cluster prevents re- and gateway nodes form a backbone to the base station and
clustering due to the lack of a common channel as a result of the re- exchange information, such as routing messages, among themselves;
appearance of PU activities. Note that, a node may reduce the and member nodes exchange information with their respective
number of common channels in a cluster upon joining the cluster clusterheads only, and so the communication overhead can be
causing instability, and so careful consideration must be made. reduced. Parallelism is important to CR networks. Firstly, in clustered
We present an example of cluster formation using Fig. 2. networks, clusterheads serve as local points of process for coopera-
Denote a set of available channels, which are not occupied by tive tasks, such as channel sensing in which each member node
PUs, by K. Suppose, the available channels at each node in cluster senses for white spaces, and subsequently sends the sensing out-
C1 is K CH1 ¼ f1; 2; 3g; K M1;1 ¼ f1; 2; 3g; K M1;2 ¼ f2; 3; 4g; K M1;3 ¼ comes to their respective clusterheads for final decisions in the
f2; 3; 4g; K M1;4 ¼ f2; 3; 5g and K M1;5 ¼ f2; 3; 6g; while the node presence of PU activities. Secondly, nodes in a cluster can select a
degree level is DCH1 ¼ 5; DM1;1 ¼ 1; DM1;2 ¼ 2; DM1;3 ¼ 1; DM1;4 ¼ 1 local common control channel, rather than a global common control
and DM1;5 ¼ 1. The local information (i.e. a set of available channels channel, which may not exist, for intra-cluster communications.
and node degree level) is exchanged among neighboring nodes to Secondly, clustering improves stability through the reduction
form clusters in line with some global objectives such as improv- of global effects on network-wide performance as a result of any
ing the network stability. To address the dynamicity of channel changes to network dynamics, such as channel availability and
availability and network topology, network stability can be network topology. This means that, any changes on network
achieved by increasing the number of common channels among dynamics cause local updates among member nodes and their
nodes in a cluster, and the node degree level of clusterhead and respective clusterheads only. This is because only the member
gateway nodes, respectively. Hence, clusterhead CH1 is selected nodes and their respective clusterheads are reconfigured in
because it provides the highest number of common channels (i.e. response to the changes. Since global update is not necessary,
channels 2 and 3), and it has the highest node degree level more white spaces are available to SUs for data transmission.
DCH1 ¼ 5 among nodes in its neighborhood. Additionally, gateway Thirdly, clustered networks support cooperative tasks, such as
node M1,2 is selected because it can hear from clusterheads CH1 channel switch, channel sensing, and routing, in order to improve
and CH2. network performance. For instance, in the aforementioned exam-
We present an example of the steps involved in the coordina- ple of channel sensing, clusterheads and member nodes cooperate
tion mechanism for cluster formation in which single-hop clusters to minimize miss detections and false alarms leading to lower SUs'
are constructed (Chen et al., 2007). Consider a new and indepen- interference levels to PUs. The clustered networks have also been
dent node. Being unassociated with any clusters, the node aims to chosen as a framework to implement game theoretic-based
become a member node through associating itself with a cluster or approach, which is a popular technique to achieve the optimal
become a clusterhead itself. It switches from channel to channel in network performance in CR networks (Zou and Chigan, 2009).
order to wait for and receive beacons from clusterheads or any In Zou and Chigan (2009), a geographical clustering approach is
messages from its neighbor nodes. There are three cases in regards proposed to form single-hop clusters with minimal overlapping in
to the reception of clusterhead's beacons and neighbor node's which member nodes in a cluster play a single game, which is
messages. Firstly, the node receives both beacon and message, and initiated and terminated by the respective clusterheads. Nodes
that are physically close to each other join a cluster, and this helps control channel. A global common control channel may not
to reduce clustering overhead and delay associated with the game exist due to the dynamicity of channel availability; however, a
process. group of geographically adjacent SUs tend to share a similar
set of available channels. Hence, nodes form clusters, and
1.4. Clustering: challenges select a local common control channel, which is available to all
nodes in a cluster (Chen et al., 2007; Li and Gross, 2011;
The main challenge associated with clustering is the dynami- Baddour et al., 2011; Gong et al., 2008; Bradonjic and Lazos,
city of channel availability, which is an intrinsic characteristic of 2012; Li et al., 2012; Liu et al., 2012). Before the establishment
CR networks. Traditionally, the cluster structure changes with of a common control channel in a cluster, nodes may hop into
network topology; however, in CR networks, the channel avail- various channels in the hope of receiving information from
ability of each node changes with time and location. This has neighbor nodes and gathering information for clustering
brought about new challenges to clustering in CR networks in purpose (Li et al., 2012). It shall be noted that, this clustering
which the lack of common channels among nodes in a cluster may objective focuses on clustering algorithms whose main objec-
cause loss of connectivity among clusterheads, as well as the tive is to establish common control channels to form clustered
connectivity among clusterheads and their respective member networks, and the literature on the establishment of common
nodes. As a consequence, cluster maintenance and re-clustering control channels in non-clustered networks can be found in
may need to be performed more often than that in the traditional (Kim, 2009; Liu, 2010).
ad hoc networks in order to optimize network performance of B.2 Enhancement on Cluster Stability. Cluster stability (or robust-
clusters at most of the times. Most clustering algorithms in the ness) improves intra-cluster and inter-cluster connectivity in
literature have been proposed to address this challenge. For the presence of the dynamicity of channel availability. Greater
instance, in Li and Gross (2011), the clustering algorithm increases cluster stability minimizes the occurrence of re-clustering
the number of common channels among nodes in a cluster, because re-clustering may result in sub-optimal network
particularly the gateway nodes, in order to prevent re-clustering performance due to the increment of clustering overhead.
as a result of the lack of a common channel. Increasing the number of common channels in a cluster
increases bandwidth availability for intra-cluster communica-
tions (Huang et al., 2011); while increasing the number of
2. Taxonomy of clustering attributes in cognitive radio common channels with neighboring clusters increases band-
networks width availability for inter-cluster communications and con-
nectivity with neighboring clusters (Ozger and Akan, 2013).
This section presents the taxonomy of attributes (see Fig. 3) Higher bandwidth availability is important to applications that
relevant to clustering in CR networks. Generally speaking, cluster- require constant message exchange such as channel sensing
ing algorithms have been designed for static and mobile networks. and routing.
Both static and mobile networks must address the dynamicity of B.3 Enhancement on Energy Efficiency. Nodes form clusters with
channel availability; while mobile networks must address topol- the objective of reducing energy consumption in order to
ogy changes caused by nodal mobility. The rest of this section prolong network lifetime and improve intra-cluster and inter-
presents clustering objectives and clustering characteristics. cluster connectivity. This can be achieved by minimizing
transmission power, intra-cluster distance, and the Euclidean
2.1. Clustering objectives distance between member nodes and their respective cluster-
heads (Zhang et al., 2011). Additionally, since a clusterhead
Nodes form clusters with the objective of network performance depletes energy faster compared to member nodes because of
enhancement. In general, there are five clustering objectives as its role as a local point of process for cooperative tasks, such as
follows: channel sensing, channel access and routing, the role of
clusterhead is rotated among nodes in a cluster in order to
B.1 Establishment of Common Control Channel. The common con- achieve load balancing and a well-balanced energy consump-
trol channel is used by SUs to exchange essential control tion among nodes throughout the entire network Xu et al.
messages, such as channel sensing, channel access and routing (2010).
messages. The unlicensed channels, such as Industrial, Scien- B.4 Enhancement on Cooperative Tasks. In channel sensing, each
tific and Medical (ISM), may be highly utilized and so an member node senses for white spaces, and subsequently
available licensed channel may be selected as a common sends the sensing outcomes to its clusterhead, which makes
Fig. 3. Taxonomy of clustering attributes in CR networks.

the final decisions on the presence of PU activities. Hence, a performance of the application. In (Ozger and Akan,
cluster, which is comprised of a clusterhead and its member 2013), shorter Euclidean distance between a clusterhead
nodes, provides a suitable model for cooperative tasks. and a sink node is preferred in CRSNs. This metric has
Generally speaking, clustering enhances channel sensing para- been applied in Ozger and Akan (2013), Zhang et al.
meters (e.g. bandwidth availability and probability of false (2010, 2011) and Wei and Zhang (2010).
alarm), as well as the associated performance metrics (e.g. C.1.3 Signal strength and channel quality. SUs select their
energy consumption). The application of clustering to enhance respective clusterheads based on Received Signal
network performances of channel sensing has been found in Strength Indicator (RSSI) (Ramli and Grace, 2010;
Wei and Zhang (2010). Alsarhan and Agarwal, 2009). In Ramli and Grace
B.5 Minimizing Number of Clusters. With reduced number of (2010), SUs form clusters with reduced average distance
clusters (or increased number of member nodes in a cluster), between member nodes and their respective cluster-
clustering provides efficient coverage and minimizes overheads, as well as minimum level of overlap among
lapping among clusters, while maintaining the original net- clusters. This helps to reduce the inter-cluster and
work connectivity of non-clustered networks. Lower number intra-cluster contentions, as well as the number of
of clusters (or higher number of member nodes in a cluster) clusters in the network. In Ramli and Grace (2010),
reduces inter-cluster communication overheads, particularly nodes with higher RSSI indicate higher node degree
routing messages, leaving more white spaces for data trans- levels, and so they are selected as clusterheads; while
mission (Chen et al., 2007; Baddour et al., 2011). Lower member nodes connect to a single clusterhead with the
number of clusters has been achieved in most clustering strongest RSSI. Higher signal strength may also indicate
algorithms (Huang et al., 2011; Chen et al., 2007; Li and higher channel quality (Li et al., 2012). This metric has
Gross, 2011; Baddour et al., 2011; Liu et al., 2012; Zhang et been applied in Li et al. (2012) and Ramli and Grace
al., 2011, 2010; Ramli and Grace, 2010). (2010).
C.1.4 Node degree. Higher level of node degree, which repre-
sents the number of neighbor nodes, reduces intra-
2.2. Clustering characteristics cluster distance; and subsequently reduces the amount
of overhead associated with intra-cluster communica-
There are two types of clustering characteristics, namely tions. This metric has been applied in Ozger and Akan
clustering metrics and intra-cluster distance. Clustering metrics (2013), Huang et al. (2011), Li and Gross (2011), Baddour
have been applied to perform cluster formation and cluster et al. (2011) and Asterjadhi et al. (2010).
maintenance, such as clusterhead selection and member node C.2 Intra-cluster distance:
joining. There are four kinds of clustering metrics, namely, channel C.2.1 Single hop. SUs form single-hop clusters in which each
availability, geographical location, signal strength and channel member node communicates with its clusterhead in a
quality, as well as node degree. Intra-cluster distance defines the single hop (Ozger and Akan, 2013; Chen et al., 2007; Li
number of hops between member nodes and their respective and Gross, 2011; Baddour et al., 2011; Bradonjic and
clusterheads. Nodes may form clusters with single or multiple Lazos, 2012; Li et al., 2012; Liu et al., 2012; Zhang et al.,
hops, and both larger and smaller clusters have their pros and cons 2011; Wei and Zhang, 2010; Ramli and Grace, 2010).
(see Section 5.6 for further descriptions). Generally speaking, single-hop clusters enhance net-
work stability, parallelism and inter-cluster communica-
C.1 Clustering metrics: tion delays.
C.1.1 Channel availability. Higher number of common channels C.2.2 Multiple hops. SUs form multiple-hop clusters in which
in a cluster increases cluster stability, and so it minimizes each member node communicates with its clusterhead
the occurrence of re-clustering, which is caused by the in multiple hops (e.g. two hops) (Huang et al., 2011;
lack of a common channel. Due to the dynamicity of Zhang et al., 2010; Asterjadhi et al., 2010). Generally
channel availability, PU activities may reappear, and this speaking, multiple-hop clusters reduce the number of
causes the member nodes to switch the common control clusters in the network and hence, it provides lower
channel; however, if there is lack of a single channel inter-cluster communication overhead, such as routing
commonly available to all nodes in a cluster, migration of messages.
clusterhead, or re-clustering may be triggered and this
increases the clustering overhead. Hence, nodes form 3. Clustering algorithms in cognitive radio networks
clusters and select clusterheads while ensuring higher
number of common channels among nodes in a cluster. This section presents existing work on clustering algorithms in
This metric has been applied in Ozger and Akan (2013), CR networks, and they are presented in accordance to the cluster-
Huang et al. (2011), Chen et al. (2007), Li and Gross ing objectives (see Section 2.1). Generally speaking, the clustering
(2011), Baddour et al. (2011), Bradonjic and Lazos (2012), algorithms aim to achieve lower number of clusters (see Section
Li et al. (2012), Liu et al. (2012), Zhang et al. (2011, 2010), 2.1, B.5) (Huang et al., 2011; Chen et al., 2007; Li and Gross, 2011;
and Asterjadhi et al. (2010). Baddour et al., 2011; Li et al., 2012; Liu et al., 2012; Zhang et al.,
C.1.2 Geographical location. SUs determine their respective 2011, 2010; Ramli and Grace, 2010; Asterjadhi et al., 2010), in
geographical locations (e.g. through Global Positioning addition to the other clustering objectives.
System (GPS)), and use this information in cluster
formation and maintenance. Physically close nodes may
share the same amount and characteristics of white 3.1. Establishment of common control channel
spaces; and so these nodes form a cluster to increase
the number of common channels among nodes in a While there has been some literature on the establishment
cluster. Additionally, physically close nodes may coop- of common control channel in non-clustered networks (Kim,
eratively perform similar tasks, such as channel sensing, 2009; Liu, 2010); there is lack of clustering algorithm that helps
and so these nodes form a cluster to enhance network to achieve this goal in clustered networks, and this section
presents a clustering algorithm whose main objective is to estab- Firstly, nodes exchange the local cluster formation information,
lish a common control channel (see Section 2.1, B.1) in a cluster. such as a list of their respective available channels, with neighbor
nodes. Subsequently, each node computes a metric called reserved
value for each link connecting to each of its neighbor nodes using
the cluster formation information. The reserved value is computed
3.1.1. Li's node ranking approach using the rank values; for instance, node i estimates the capacity of
Li et al. (2012) proposed a cluster formation procedure for static link (i,n) based on Shannon's formula, and ranks the capacity of
(or quasi-stationary) networks with the objective of establishing each link (i,n AN) connecting to each neighbor node. Hence, if a
common control channels in single-hop clusters (see Section 2.2, link (i,n) has the lowest rank of capacity or C(i,n)¼1, it represents
C.2.1). The clustering metrics are channel availability (see Section that link (i,n) is the most favorable one with the highest capacity.
2.2, C.1.1) as well as signal strength and channel quality (see The reserved value of the link of node i connecting to one of its
Section 2.2, C.1.3). The steps of the clustering algorithm for a node i neighbor node n A N is the weighted sum of the rank values as
are shown in Fig. 4. Generally speaking, each node i ranks its follows:
neighbor nodes nA N based on the link characteristics, namely,
number of common channels, as well as the capacity and quality of Rði; n A NÞ ¼ w1 Cði; nÞ þ w2 Sði; nÞ þ w3 Q ði; nÞ ð1Þ
the link. Lower rank value is favorable, and so node i associates where w1, w2 and w3 represent weights (e.g. w1 ¼ w2 ¼w3 ¼1/3).
itself with the lowest ranked neighbor node. Note that, for Value S(i,n) represents the rank of the stability level. Lower value
simplicity, the nodal representations (or the labels of the nodes), of S(i,n) indicates higher number of common channels in link (i,n),
which may indicate the roles of the nodes in Fig. 5, remain the and so it provides greater stability, thereby reducing the occur-
same before and after the clustering procedure although the roles rence of re-clustering. Value Q(i,n) represents the rank of the
of clusterhead and member node are assigned upon completion of channel quality, which is estimated based on the available dura-
the procedure. tion of the link for data transmission. Lower value of Q(i,n)
indicates higher probability of two nodes i and n belonging to
the same cluster. For instance, in Fig. 5(a), the reserved values of
the links of node M1,2 connecting to its neighbor nodes CH1 and
CH1 are R(M1,2,CH1) ¼1 and R(M1,2,CH2)¼ 3, respectively. Note that,
each link has two ends, and so it has two reserved values: R(i,n)
and R(n,i); for instance, R(M1,2,CH1) ¼1 and R(CH1,M1,2) ¼2.
Secondly, the reserved values are exchanged among neighbor
nodes, and each of them adds the reserved values of each link to
provide an aggregated reserved value as follows:
R0 ði; nÞ ¼ R0 ðn; iÞ ¼ Rði; nÞ þ Rðn; iÞ ð2Þ
0 0
For instance, in Fig. 5(b), R ðM 1;2 ; CH 1 Þ ¼ R ðCH 1 ; M 1;2 Þ ¼ RðM 1;2 ;
CH 1 Þ þ RðCH 1 ; M 1;2 Þ ¼ 1 þ 2 ¼ 3. A node becomes a clusterhead if it
has either the highest node degree level or the lowest node ID
among neighboring nodes or both.
Thirdly, nodes form clusters, and this is accomplished through
nodes associating themselves with clusterheads that provide links
with the least aggregated reserved value R0 (i,n) (or R0 (n,i)). For
instance, in Fig. 5(c), M1,2 is associated with CH1 because
Fig. 4. Steps of the Li's node ranking approach at node i. R0 ðM 1;2 ; CH 1 Þ oR0 ðM 1;2 ; CH 2 Þ. In other words, CH 1 ¼ argminn A N R0
Fig. 5. The Li's node ranking approach. (a) Nodes calculate reserved values. (b) Nodes calculate aggregated reserved values. (c) Nodes form clusters.
ðM 1;2 ; nÞ. A common control channel is selected out of the available

common channels in a cluster.
Li's node ranking approach has been shown to provide lower
number of clusters (see Section 4.1, P.1), higher number of
common channels in a cluster (see Section 4.1, P.2), lower cluster-
ing overhead (see Section 4.1, P.3), and lower number of re-
clustering (see Section 4.1, P.5).
3.2. Enhancement on cluster stability
This section presents clustering algorithms whose main objec-

tive is to enhance cluster stability (see Section 2.1, B.2).
Fig. 6. The Huang's node importance degree approach. Node M2,4 must switch
between channels 3 and 4 in order to communicate with CH2 and M2,5. The set of
3.2.1. Huang's node importance degree approach available channels is shown at each node.
Huang et al. (2011) proposed a cluster formation procedure
to form multiple-hop clusters (see Section 2.2, C.2.2) in mobile
networks. The clustering metrics are channel availability (see
Section 2.2, C.1.1) and node degree level (see Section 2.2, C.1.4).
There are two metrics pertinent to cluster stability at link and
cluster levels.
Firstly, the probability of link availability, which is computed
using the nodal mobility characteristics (i.e. speed and direction),
must be greater than a certain threshold within a long-enough
period of time T. Higher probability of link availability increases
the link stability of each pair of nodes in a cluster.
Secondly, using channel m, each node i calculates a metric
called node importance degree as follows:
Di;m ¼ ni;m =ð1 þ hi;m þsi;m Þ ð3Þ
where ni,m represents the number of one-hop and two-hop

neighbor nodes on channel m; hi,m represents the average number
of hops (or intra-cluster distance), which affects the intra-cluster
delay, from node i to all one-hop and two-hop neighbor nodes;
and si,m represents the average number of channel switches due to
the distinctive channels being selected by node i and its neighbor
nodes. Nodes with the highest node importance degree Di,m
among their respective two-hop neighbor nodes are selected as Fig. 7. Steps of the Baddour's affinity propagation message-passing approach at
node i.
clusterheads; while the rest of the nodes associate themselves
with clusterheads that provide the highest Di,m.
The clusterhead chooses a common control channel m; how-
ever, this channel may not be available to some of its member Firstly, nodes exchange the local cluster formation information,
nodes. Such cases may be reduced by minimizing the average including a list of their respective available channels for each
number of channel switches si,m; however, if this happens, an neighbor node and node degree level, with neighbor nodes. The
upstream member node must switch between channel m and a affinity propagation approach applies a metric that represents the
common channel between the two nodes. For instance, in Fig. 6, similarity level of a node pair (i.e. nodes i and n), which indicates
clusterhead CH2 selects a common control channel m ¼3; while the number of common channels among node i and n AN.
channel availability at member node M2,4 is K M2;4 ¼ f3; 4g and M2,5 Specifically, the similarity between nodes i and n is sði; nÞ ¼
is K M2;5 ¼ f4; 5g. Since K M2;5 excludes the common control channel sðn; iÞ ¼ jK i \ K n j, where Ki and Kn are the sets of available channels
of the cluster, and the common channel between member nodes at nodes i and n, respectively.
M2,4 and M2,5 is channel 4, member node M2,4 must constantly Secondly, nodes compute and further exchange the local cluster
switch between channels 3 and 4. formation information including responsibilities and availabilities.
Huang's node importance degree approach has been shown Node i sends responsibility r(i,n) to node n, specifically
to provide lower number of clusters (see Section 4.1, P.1), lower rði; nÞ’sði; nÞ maxn0 a n faði; n0 Þ þ sði; n0 Þg ð4Þ
clustering overhead (see Section 4.1, P.3), and higher number of
common channels with neighboring clusters (see Section 4.1, P.9), and node n sends availability a(i,n) to node i, specifically
which improves connectivity among clusters. ( )
aði; nÞ’ min 0; rðn; nÞ þ ∑ max f0; rði0 ; nÞg ð5Þ
i0 2
= fi;ng
3.2.2. Baddour's affinity propagation message-passing approach
Baddour et al. (2011) proposed a cluster formation procedure to Since s(i,n) represents the similarity level between nodes i and n,
form single-hop clusters (see Section 2.2, C.2.1) in mobile net- both responsibility r(i,n) and availability a(i,n) indicate how well-
works using the affinity propagation message-passing approach. suited node n is to serve as clusterhead for node i from the
The clustering metrics are channel availability (see Section 2.2, perspective of nodes i and n, respectively.
C.1.1) and node degree level (see Section 2.2, C.1.4). The steps of the Thirdly, nodes that fulfill r(i,i)þa(i,i)4 0 become potential
clustering algorithm for a node i are shown in Fig. 7. clusterheads. Among the potential clusterheads, nodes with the
highest node degree level among its single-hop neighborhood degree level (see Section 2.2, C.1.4). The steps of the clustering
become clusterheads. algorithm for a node i are shown in Fig. 8.
Baddour's affinity propagation message-passing approach has Firstly, nodes exchange the local cluster formation information,
been shown to provide lower number of clusters (see Section 4.1, such as a list of their respective available channels for each
P.1). neighbor node, with neighbor nodes. Each node i keeps track of
connectivity vector comprises two-tuple metrics 〈Pi,Gi〉 pertinent
to cluster stability, where Pi represents spectrum connectivity
3.2.3. Connectivity degree approach
degree and Gi represents local connectivity degree. The spectrum
Li and Gross (2011) proposed a cluster formation procedure
connectivity degree Pi is the total number of common channels
to form single-hop clusters (see Section 2.2, C.2.1) in order to
between node i and each of its neighbor nodes, and so it indicates
increase the number of common channels among nodes in a
the adhesiveness of node i to the network. For instance, node i has
cluster in static (or quasi-stationary) networks. The objective is
two neighbor nodes j and k, and the set of the available channels at
to prevent loss of connectivity among clusterheads, as well as the
each node is Ki ¼{1,2,3,4,5}, Kj ¼{1,2,3} and Kk ¼ {2,4}; the spectrum
clusterheads and their respective member nodes. The clustering
connectivity degree is computed as Pi ¼ Pi,j þ Pi,k ¼3 þ 2¼ 5. The
metrics are channel availability (see Section 2.2, C.1.1) and node
local connectivity degree Gi is the number of common channels
among node i and all of its neighbor nodes, and it indicates the
suitability of node i to form a robust cluster with its neighboring
nodes. For instance, using the aforementioned example, Gi ¼1
because there is a single common channel among nodes i, j and
k, specifically, channel 2. Figure 9(a) shows an original non-
clustered network. The two-tuple metrics 〈Pi,Gi〉 are shown at each
node, and the number of pairwise common channels for each node
pair Pi,n A N is shown at each link.
Secondly, nodes compute and further exchange the local cluster
formation information, including spectrum connectivity degree Pi
and local connectivity degree Gi. Node i becomes a clusterhead if
node I's spectrum connectivity degree is less than those of its
neighbor nodes, specifically, Pi oPn A N\CH, where N represents node
i's set of neighbor nodes and CH represents node i's set of
clusterheads among its neighbor nodes. The purpose of choosing
nodes with lower spectrum connectivity degree as clusterheads is
that, it increases the number of common channels with neighbor-
ing clusters, and so it increases connectivity among clusters.
However, if node i's spectrum connectivity degree is similar to
any of its neighboring nodes, specifically, Pi ¼Pn A N\CH, then the
node with higher local connectivity degree value, or Gi 4Gn A N\CH,
becomes clusterhead. Non-clusterheads associate themselves with
clusterheads and become member nodes. Note that, smaller
Fig. 8. Steps of the Li and Gross's connectivity degree approach at node i. cluster size increases the number of common channels among
Fig. 9. The Li and Gross's connectivity degree approach. (a) Nodes calculate two-tuple metrics 〈Pi,Gi〉. (b) Nodes form clusters. (c) Debatable nodes associate themselves with
clusterheads.
nodes in a cluster, and so nodes may be eliminated from their Firstly, nodes exchange the local cluster formation information,
respective clusters until there is at least a single common channel such as a list of their respective available channels, with neighbor
in the cluster. Figure 9(b) shows the updated values of two-tuple nodes. Each node i represents its local network topology, which
metrics 〈Pi,Gi〉 and the newly formed clusters. For instance, since consists of neighboring nodes and the available channels for each
P CH1 ¼ 2 o P M1;1 ¼ 11, node CH1 becomes a clusterhead. neighbor node, using a bipartite graph. The bipartite graph GðA [
Thirdly, nodes that are physically located in more than a single B; EÞ comprises two disjoint sets of vertices A [ B, and all edges in
cluster, which are also called debatable nodes, choose to associate E connect vertices from A to B. For instance, Fig. 11(b) shows a
themselves with a single cluster respectively. The debatable nodes bipartite graph constructed by node CH1 in (a), where vertices A
choose to associate themselves with clusterheads that can max- (or the upper row) represent node CH1 and its neighboring nodes,
imize the number of common channels in a cluster in order to vertices B (or the lower row) represent the available channels at
increase cluster stability. For instance, in Fig. 9(c), node M1,1 is a node CH1, and each edge eAE indicates that node a A A has an
debatable node, which may associate itself with either CH1, CH2, available channel b AB. The objective of the approach is to achieve
CH3 or CH5, and it chooses to associate itself with CH1. a balanced tradeoff between cluster size and the number of
Li and Gross's connectivity degree approach has been shown to common channels among nodes in a cluster (see Section 5.3).
provide lower number of clusters (see Section 4.1, P.1), higher Higher number of common channels among nodes in a cluster
number of common channels in a cluster (see Section 4.1, P.2), and helps to increase the amount of bandwidth availability for intra-
higher number of common channels with neighboring clusters cluster communications and reduce the occurrence of re-cluster-
(see Section 4.1, P.9). ing; however, the cluster size tends to be smaller and so the main
A similar clustering algorithm that applies the local connectiv- drawback is that there would be higher amount of bandwidth
ity degree parameter has been proposed in Asterjadhi et al. (2010) consumption on inter-cluster communications. Three clustering
for cluster formation to form multiple-hop clusters (see Section criteria are proposed to achieve different levels of the aforemen-
2.2, C.2.2) in order to increase the number of common channels tioned tradeoff as follows:
among nodes in a cluster in static networks. The clustering metrics
are channel availability (see Section 2.2, C.1.1) and node degree Maximum Node Biclique (MNB). MNB maximizes Q nMNB ðA; BÞ,
level (see Section 2.2, C.1.4). Nodes exchange the local cluster which is the sum of the number of member nodes |A| and the
formation information, including a list of the available channels for number of common channels in the cluster |B|, as follows:
each neighbor node n AN (see Sections 2.2, C.1.1) and node degree
Q nMNB ðA; BÞ ¼ argmaxQ jAj þ jBj ð6Þ
level (see Section 2.2, C.1.4) with k-hop neighbor nodes where N is
a set of node i's neighbor nodes. Node i calculates the local
connectivity degree Gi, which is the minimum number of common Higher Q nMNB ðA; BÞ indicates that member nodes share a higher
channels among node i and all of its neighbor nodes, or number of common channels in a cluster, or there is at least a
Gi ¼ minn A N jK i \ K n j, where Ki is a set of available channels at single common channel in a cluster with higher number of
node i. Nodes with the largest f(Gi) value, which is computed using member nodes in a cluster. For instance, Fig. 11(c) shows the
Gi, among their respective k-hop neighborhood become cluster- bipartite graph constructed by node CH1 using MNB in which
heads. Suppose, node i is a clusterhead. Neighbor node n A N that Q nMNB ðA; BÞ ¼ 7 þ1 ¼ 8.
receives higher f(Gi), specifically f(Gn)of(Gi), associates itself with Maximum Edge Biclique (MEB). MEB maximizes Q nMEB ðA; BÞ,
cluster i and becomes its member node. Asterjadhi's connectivity which is the product of the number of member nodes |A| and
degree approach has been shown to provide lower number of the number of common channels in the cluster |B|, as follows:
clusters (see Section 4.1, P.1), and higher number of common Q nMEB ðA; BÞ ¼ argmaxQ jAj UjBj ð7Þ
channels in a cluster (see Section 4.1, P.2).
The nature of product in MEB exhibits a higher sensitivity to

changes in |A| and |B|; hence, MEB does not construct clusters with
3.2.4. Bipartite graphs approach
smaller cluster size and lower number of common channels. For
Bradonjic and Lazos (2012) proposed a cluster formation
instance, Fig. 11(d) shows the bipartite graph constructed by node
procedure to form single-hop clusters (see Section 2.2, C.2.1) in
CH1 using MEB in which Q nMEB ðA; BÞ ¼ 4 3 ¼ 12. Note that,
static networks using bipartite graphs. The clustering metric is
bipartite graph in Fig. 11(d) provides higher Q nMEB ðA; BÞ ¼ 12 when
channel availability (see Section 2.2, C.1.1). The steps of the
using MEB, compared to the bipartite graph in Fig. 11(c) in which
clustering algorithm for a node i are shown in Fig. 10.
Q nMEB ðA; BÞ ¼ 7 1 ¼ 7.
Maximum One-Sided Edge Cardinality Biclique (MECB). MECB
maximizes Q nMECB ðA; BÞ in order to form clusters with the high-
est possible number of member nodes |A| under a constraint on
the number of common channels in a cluster |B| as follows:
Q nMECB ðA; BÞ ¼ argmaxQ jAj with jBj 4 BT ð8Þ
where BT is a threshold. This means that MECB maximizes the
cluster size while providing a guarantee on the minimum
amount of bandwidth availability in a cluster using threshold
BT. Hence, the bipartite graph is equivalent to Fig. 11(c) and
(d) given BT ¼ 1 and BT ¼ 3, respectively. Note that, cluster size
becomes smaller when the number of common channels
among nodes in a cluster becomes higher.
Using one of the three proposed clustering algorithms (i.e.

Fig. 10. Steps of the bipartite graphs approach at node i. MNB, MEB and MECB), each node i segregates the bipartite graph
Fig. 11. Bipartite graphs approach. (a) Original network topology. (b) A bipartite graph constructed by node CH1. (c) A bipartite graph constructed by node CH1 using MNB.
(d) A bipartite graph constructed by node CH1 using MEB.
(network) into biclique graphs (clusters). Each node i computes communications, member nodes exchange information among
wi ¼Q*(A,B). themselves and their respective clusterheads; for instance, mem-
Secondly, nodes exchange wi among themselves, and nodes with ber nodes exchange the local cluster formation information (i.e.
the maximum wi among its neighbor nodes become clusterheads. node location, the current cluster size and a list of common
Thirdly, non-clusterhead nodes associate themselves with clus- channels in the cluster) with neighbor nodes and clusterhead.
terheads. Each non-clusterhead node selects clusterhead with the During inter-cluster communications, clusterheads send data to
maximum wi among its single-hop neighbor clusterheads and upstream clusterheads using the maximum transmission power in
becomes its member node. order to improve network connectivity.
As part of the cluster maintenance, re-clustering may be There are two main steps in the group-wise constrained
necessary when the number of common channels in a cluster approach for cluster formation. Firstly, all nodes form disjoint
with node i being clusterhead is less than a threshold, or |Bi| oBT. clusters, and each cluster is comprised of a single node itself.
In this case, all nodes in the cluster switch into “undecided” state, Secondly, the clusters merge among themselves with adjacent
and a new clusterhead j with |Bj| 4BT is selected. clusters if they share at least a single common channel; and this
Bradonjić's bipartite graphs approach has been shown to proceeds until the number of clusters reduces to the optimal
provide lower number of clusters (see Section 4.1, P.1), and higher number, which is dependent on the number of nodes in the
number of common channels in a cluster (see Sections 4.1, P.2). network, node density and the maximum transmission range.
The investigation on achieving a balanced tradeoff between cluster In other words, physically closest nodes with common channel
size and the number of common channels among nodes in a (s) form clusters that grow in cluster size as more nodes join a
cluster is also presented. Similar approach has been applied in Liu particular cluster one after another through cluster merging.
et al. (2012) and Nafees et al. (2013). Since the clusterheads incur higher energy consumption com-
pared to member nodes, the clusterhead role is rotated among all
nodes with equal probability. Zhang's group-wise constrained
3.3. Enhancement on energy efficiency
approach has been shown to provide lower number of clusters (see
Section 4.1, P.1), and lower energy consumption (see Section 4.1, P.8).
This section presents clustering algorithms whose main objec-
tive is to enhance energy efficiency.
3.3.2. Ozger's event-driven approach

3.3.1. Zhang's group-wise constrained approach Ozger and Akan (2013) proposed Event-driven Spectrum-
Zhang et al. (2011) proposed a cluster formation procedure to Aware Clustering (ESAC) protocol for cluster formation in static
form single-hop clusters (see Section 2.2, C.2.1) in static networks CRSNs with the main objective of minimizing energy consumption
using the group-wise constrained approach. The clustering metrics in single-hop clusters (see Section 2.2, C.2.1). The clustering
are channel availability (see Section 2.2, C.1.1) and geographical metrics are channel availability (see Section 2.2, C.1.1) as well as
location (see Section 2.2, C.1.2). There are two factors pertinent to geographical location (see Section 2.2, C.1.2) and node degree (see
the reduction of energy consumption. Section 2.2, C.1.4).
Firstly, the transmission power can be reduced by minimizing There are three strategies to minimize energy consumption.
the distance between member nodes and their respective cluster- Firstly, ESAC is an event-driven approach that forms temporary
heads (or intra-cluster distance). Additionally, SUs' interference to clusters that is initiated upon detection of an event, and it is
PUs can be reduced with lower transmission power. maintained until the termination of the event. This avoids energy
Secondly, the transmission power can be reduced by achieving consumption required to form and maintain clusters at all times.
the optimal cluster size (or the number of clusters in the network), Secondly, ESAC forms clusters in regions between event(s) and
which affects intra-cluster and inter-cluster communications, and sink, rather than in the entire network. Thirdly, ESAC prevents
hence the transmission power. During intra-cluster re-clustering by maximizing the number of common channels in a
cluster, as well as with two-hop nodes, which are from neighbor-

ing clusters. The rest of this section presents how the second and
third strategies are achieved. There are two main phases, namely
identifying eligible nodes for clustering, and forming clusters.
In the first phase, a node that detects an event becomes an
eligible node for clustering. The node chooses neighbor nodes that
are physically closer to the sink and farther from the event
to become eligible nodes as well. Next, the new eligible nodes
determine their next-hop eligible nodes, and this is performed
until the sink node is found. The outcome is that, nodes in the
region between event(s) and sink node become eligible for
clustering, and this achieves the aforementioned second strategy.
In the second phase, there are two main steps, namely cluster-
head selection and cluster formation. The steps of the clustering
algorithm for a node i are shown in Fig. 12. During clusterhead
selection, an eligible node i with the maximum weight
ws;i ¼ jK i j Di þ 10=di;sink among its single-hop neighborhood is
chosen as clusterhead, where |Ki| is the number of available
channels at node i, Di is the node degree level involving single-
hop eligible nodes at node i, and di,sink is the Euclidean distance
between node i and the sink node. Higher weight value indicates
that a node has higher number of available channels, node degree
level involving eligible nodes, and closer to the sink node among
its single-hop neighborhood nodes. During cluster formation, the
purpose is to discover a candidate (or potential) cluster with the
maximum weight wf,i,j, and this requires |J| iterations. For each
iteration jA J¼ {1,…, |K|} where Ki represents a set of available
channels at clusterhead node i, clusterhead i creates a candidate
cluster using a particular available channel kj A Ki, and subse-
Fig. 12. Steps of the Ozger's ESAC protocol at node i.
quently, it calculates weight wf ;i;j ¼ jK j j jni;1;j j jni;2;j j for the
cluster. Next, the sets Kj, ni,1,j and ni,2,j are updated. At each
iteration j, the respective channel kj is included in the set Kj, networks using the contribution decision approach. The clustering
specifically jK j j [ kj . The ni,1,j represents the set of single-hop metric is geographical location (see Section 2.2, C.1.2), and it is also
eligible nodes of node i using channel kj. The ni;2;j represents the based on the accuracy of the sensing outcomes. A clustered
set of two-hop eligible nodes in set ni,1,j using channels in set Kj. In network is comprised of member nodes, clusterheads and a fusion
other words, by using the metric ni,2,j, a clusterhead considers the center. Each cluster comprises member nodes and a clusterhead.
number of two-hop neighbors that are accessible by its one-hop Among the clusterheads, one is selected to serve as a fusion center.
neighbors using the cluster channels. This helps to increase To obtain accurate decisions on sensing outcomes, clusterheads
connectivity among clusters. Higher weight wf,i,j values indicate a make local decisions based on sensing outcomes collected from
candidate cluster with higher number of common channels for their respective member nodes; and subsequently, the fusion
intra-cluster and inter-cluster communications. Hence, this center makes global decisions based on local decisions collected
achieves the aforementioned third strategy. from clusterheads. There are two main steps in cluster formation.
Finally, clusterhead i selects the candidate cluster jA J with the Firstly, nodes form clusters based on their respective physical
maximum weight wf,i,j, which was created in one of the |J| locations, and so nodes that are physically close to each other are
iterations. Upon selecting a candidate cluster, the clusterhead i clustered.
sends request message to inform its single-hop neighborhood so Secondly, each SU keeps track of its own contribution value,
that nodes can join this cluster as member nodes. which is calculated based on the consistency (or similarity) of
Ozger's event-driven approach has been shown to provide sensing outcomes compared to final decisions of the sensing
lower energy consumption (see Section 4.1, P.8), and higher outcomes, which are made by the fusion center. The contribution
number of neighboring nodes with common channels (see value is positive if a member node's sensing outcome is consistent
Section 4.1, P.9). with the final decision, and vice-versa. The contribution value
is further evaluated using a pre-defined threshold. Specifically, a
member node sends its channel sensing outcomes to its cluster-
3.4. Enhancement on cooperative tasks
head if its contribution value is greater than the pre-defined
threshold, otherwise it keeps silence due to its unreliability. A
This section presents a clustering algorithm whose main
node with the highest contribution value among its single-hop
objective is to enhance the performance of an application scheme,
neighborhood is selected as the clusterhead. Since the cluster-
namely channel sensing. Channel sensing aims to detect white
heads incur higher energy consumption compared to member
spaces and the presence of PU activities. For instance, in Wei and
nodes, the clusterhead role is rotated among nodes, and this has
Zhang (2010), a clustering algorithm is proposed for channel
been shown to reduce energy consumption.
sensing with the objective of reducing the error probability in
Wei's contribution decision approach has been shown to
sensing outcomes.
provide lower energy consumption (see Section 4.1, P.8), and
lower error probability in sensing outcomes (see Section 4.1,
3.4.1. Wei's contribution decision approach P.10). The algorithm achieves lower energy consumption because
Wei and Zhang (2010) proposed a cluster formation procedure member nodes with contribution value lower than a pre-defined
to form single-hop clusters (see Sections 2.2, C.2.1) in static threshold do not send their sensing outcomes to their respective
clusterheads. Note that, achieving lower error probability in cluster, and subsequently reduces the number of channel
sensing outcomes (see Section 4.1, P.10) requires higher number switches due to distinctive channels being selected by mem-
of local sensing outcomes from more nodes, and so this incurs ber nodes in a cluster. Note that, if there must be at least a
higher energy consumption. Hence, further research could be single common channel in a cluster, then either rotation of
pursued to investigate approaches to achieve a balanced tradeoff clusterhead or re-clustering is necessary to achieve this.
between these two network performances. P.5 Lower number of re-clustering reduces clustering overhead
(see Section 4.1, P.3) and energy consumption (see Section 4.1,
P.8) associated with re-clustering, and so it increases network
4. Performance enhancements and complexity analysis of lifetime. Re-clustering is necessary whenever a common
clustering algorithms channel cannot be found in a cluster, and it may be avoided
by the rotation of clusterhead.
This section presents performance enhancements and com- P.6 Shorter intra-cluster distance reduces the number of hops or
plexity analysis of various clustering algorithms. the Euclidean distance (Ramli and Grace, 2010) between
member nodes and their respective clusterheads in a cluster.
4.1. Performance enhancements This helps to reduce the intra-cluster delay and energy
consumption due to lower transmission power.
Table 1 compares various aspects of clustering algorithms, includ- P.7 Lower level of overlap among clusters reduces channel conten-
ing clustering objectives, clustering attributes and performance tion among nodes in different clusters, and so it provides
enhancements in comparison with conventional and traditional network performance enhancement such as throughput and
approaches in CR networks. The comparison presents the advantages end-to-end delay.
brought about by various clustering algorithms; for instance, single- P.8 Lower energy consumption increases network lifetime. In Wei
hop clusters (see Section 2.2, C.2.1) enhances stability, parallelism and Zhang (2010), a threshold is chosen against the reliability
and inter-cluster communication delays while multiple-hop clusters of information in which member nodes do not send unreli-
(see Section 2.2, C.2.2) reduces the number of clusters in the network. able sensing outcomes to their respective clusterheads in
On the other hand, open issues (see Section 5) presents the short- channel sensing in order to reduce energy consumption.
comings of existing clustering algorithms and proposes mechanisms Higher threshold values reduce energy consumption.
to address them. Additionally, Table 1 also presents simulation tools P.9 Higher number of common channels with neighboring clusters
applied to investigate the clustering algorithms. indicates higher probability of connectivity among clusters. This
Simulation has been adopted to evaluate network performance prevents loss of connectivity with neighboring clusters, and
achieved by the clustering algorithms. There are various simula- reduces the number of channel switches due to distinctive
tion tools including self-developed tool (S.1), and network simu- channels being selected by a cluster and its neighboring clusters.
lators such as NS-2 or NS-3 (Network Simulator 3 (NS-3), 2013) P.10 Lower error probability in sensing outcomes helps to improve
(S.2), OMNeTþ þ (OMNeTþ þ, 2013) (S.3) and Qualnet (Qualnet, accuracy in the detection of PU activities and white spaces in a
2013) (S.4). Generally speaking, the self-developed tool is devel- channel sensing scheme, which is one of the main functions of
oped by the authors of the literature themselves using program- CR networks. Note that, the enhancement of network perfor-
ming languages, such as C/C þ þ in Li and Gross (2011), and the mance in other kinds of applications is possible, although channel
tool may run on computer applications, such as MatLab in Ramli sensing has seemed to fit in well with clustered networks.
and Grace (2010). Most simulations in the literature use self-
developed tool (S.1) (see Table 1).
The performance enhancements may be relevant to each other, 4.2. Complexity analysis
and they are shown as follows:
This section investigates the clustering algorithms with respect to
P.1 Lower number of clusters provides efficient coverage by time and message complexities associated with cluster formation
increasing cluster size or the number of member nodes in a starting from initial networks comprised of non-clustered nodes. The
cluster. Lower number of clusters reduces the high amount of complexity analysis conducted in this section is inspired by similar
inter-cluster communications, particularly routing, and so it investigation in Bettstetter and Konig (2013). This analysis is highly
leaves more white spaces for control and data transmissions relevant to clustering, and so the exchanges of clustering information
(Chen et al., 2007; Baddour et al., 2011). Additionally, it (e.g. a set of available channels) using Hello messages are not counted
minimizes overlaps among clusters (see Section 4.1, P.7), as these messages are incurred even in non-clustered networks. The
and so it reduces channel contention among clusters. time complexity is the number of time steps to form clusters in a
P.2 Higher number of common channels in a cluster increases the network; and each time step involves a packet transmission from each
availability of at least a single common channel in a cluster, while node. The message complexity is the number of clustering messages
leaving some common channels as backups. Hence, higher exchanged among non-clustered nodes to form clusters in a network.
number of common channels in a cluster prevents re-clustering Note that, Wei and Zhang' (2010) contribution decision approach is
(see Section 4.1, P.5) as a result of the re-appearance of PU not analyzed as it is associated with a cooperative task in which nodes
activities, and subsequently improves cluster stability. with the highest channel sensing capability are selected to become
P.3 Lower clustering overhead reduces unnecessary exchanges of clusterheads which can be rotated; while Zhang et al.'s (2010)
clustering overhead. This may reduce energy consumption (see approach is also not analyzed as it incorporates neighbor discovery
Section 4.1, P.8) and increase the amount of white spaces for mechanism in clusterhead selection. Denote the number of nodes in a
control and data transmissions. For instance, in Bradonjic and CR networks by M. Table 2 compares the time and message complex-
Lazos (2012), nodes broadcast clustering messages to their ities of the clustering algorithms.
respective single-hop neighborhood, rather than multiple-hop The time and message complexities of several clustering algo-
neighborhood in order to reduce clustering overhead. rithms are explained. In the Li et al.'s (2012) node ranking approach
P.4 Lower number of unconnected nodes reduces the number of (see Section 3.1.1), each node broadcasts a reserved value, and its
member nodes that do not share any common channels in its choice of being a clusterhead or a member node, so time complex-
cluster. This improves connectivity among member nodes in a ity is at most 2 time steps. The message complexity is at most 2M
92
Table 1
Comparison of clustering algorithms in CR networks.
References Clustering objective Clustering attributes
Clustering metric Intra-cluster distance
B.1 Establishment of c B.2 Enhancement on B.3 Enhancement on B.4 Enhancement on B.5 Minimizing C.1.1 C.1.2 C.1.3 Signal strength C.1.4 Node C.2.1 C.2.2
ommon control cluster stability energy efficiency cooperative tasks number of clusters Channel Geographical and channel quality degree Single hop Multiple
channel availability location hops
Li et al. (2012)
Huang et al. (2011)
Baddour et al. (2011)
Li and Gross (2011)
Ramli and Grace (2010)
Asterjadhi et al. (2010)
K.-L.A. Yau et al. / Journal of Network and Computer Applications 45 (2014) 79–95
Bradonjic and Lazos (2012)
Liu et al. (2012)
Zhang et al. (2011)
Ozger and Akan (2013)
Wei and Zhang (2010)
Chen et al. (2007)
Zhang et al. (2010)
References Performance enhancements compared to existing approaches Simulation tool
P.1 Lower P.2 Higher P.3 Lower P.4 Lower P.5 Lower P.6 Shorter P.7 Lower P.8 Lower P.9 Higher number of P.10 Lower error S.1 Self- S.2 S.3 S.4
number of number clustering number of number of intra- level of energy common channels with probability in developed NS- OMNeT þ þ Qualnet
clusters of common overhead unconnected re-clustering cluster overlap consump- neighboring clusters sensing outcomes tool 2 or
channels in a nodes distance among tion NS-3
cluster clusters
Li et al. (2012)
Huang et al.
(2011)
Baddour et al.
(2011)
Li and Gross
(2011)
Ramli and
Grace
(2010)
Asterjadhi
et al. (2010)
Bradonjic and
Lazos
(2012)
Liu et al.
(2012)
Zhang et al.
(2011)
Ozger and
Akan (2013)
Wei and
Zhang
(2010)
Chen et al.
(2007)
Zhang et al.
(2010)
Table 2 has been limited literature on cluster maintenance, and the motivation
Comparison of time and message complexities among clustering algorithms. of this investigation stems from the fact that the dynamicity of
channel availability caused by PUs has introduced new open issues,
References Time complexity Message complexity
leading to the dynamic amount of available bandwidth at clusterheads
Li et al. (2012) r2 r 2M and member nodes. Additionally, there are traditional factors that
Huang et al. (2011) r2 r 2M affect the amount of available bandwidth at clusterheads, such as the
Baddour et al. (2011) r3 r 3M traffic amount and the effects of nodal mobility on the interference to
Li and Gross (2011) r2 r 2M
Ramli and Grace (2010) r2 r 2M
clusterheads. Due to the important role of clusterheads and gateways
Asterjadhi et al. (2010) r2k r kM as backbone nodes, channel availability at the clusterheads should be
Bradonjic and Lazos (2012) r2 r 2M well managed because insufficient amount of bandwidth may cause
Liu et al. (2012) r2 r 2M packet loss and this affects Quality of Service (QoS) of the entire
Zhang et al. (2011) r2 r 2M
cluster. In the context of CR, cluster maintenance affects the number of
Ozger and Akan (2013) r2 r 2M
Chen et al. (2007) r2 r 2M common channels and the traffic amount in an existing or a new
Zhang et al. (2010) r2 r 2M cluster. Therefore, cluster maintenance must take into consideration
the number of common channels in a cluster (and other performance
metrics of interest) to ensure successful and smooth cluster main-
in which each node in a network, which comprises M nodes, tenance in order to minimize the occurrence of re-clustering. In
exchanges at most 2 messages. In Huang et al.'s (2011) node Sharma and Abrol (2013), an initial study on the migration of cluster-
importance degree approach (see Section 3.2.1), 2-hop clusters head in a cluster using thresholds based on miss detection, false alarm
are formed. Each node calculates its own node importance degree and the traditional signal-to-noise ratio is presented for channel
using information which can be exchanged using Hello messages, sensing. Further research could be pursued to investigate cluster
and broadcasts its choice of being a clusterhead or a member node maintenance while providing optimal network performance.
within its two-hop neighborhood. Since a node may be two hops
away from a clusterhead, it takes at most 2 time steps for a 5.2. Common assumptions in cognitive radio networks
clusterhead to announce its role, as well as member nodes to
announce their respective choice of clusterheads, so time complex- Future research could be pursued to relax the following
ity is at most 2 time steps. The message complexity is at common assumptions applicable to the investigation of clustering
most 2M messages. In Baddour et al.'s 2011 affinity propagation algorithms in CR networks:
message-passing approach (see Section 3.2.2), each node broad- The links are considered bi-directional (or symmetric) (Zou and
casts responsibilities, availabilities, and its choice of being a Chigan, 2009; Baddour et al., 2011; Gong et al., 2008). However, in
clusterhead or a member node, so time complexity is at most CR networks, links may be asymmetric because each node may
3 time steps. The message complexity is at most 3M. In Asterjadhi have different sets of available channels. For instance, node i may
et al.'s (2010) approach (see Section 3.2.3), k-hop clusters are communicate with node j using channel k; while node j can only
formed. Each node calculates its own local connectivity degree communicate with node i using channel m.
and broadcasts this information, as well as its choice of being a
clusterhead or a member node, within its k-hop neighborhood; and Network dynamics, such as nodal mobility, channel availability and
a non-clustered node takes at most k time steps to inform a traffic amount, change at a relatively slow rate or even static
clusterhead, which is k hops away to join the cluster. Hence, time throughout the duration of cluster formation (Chen et al., 2007;
complexity is at most 2k time steps, and message complexity is at Baddour et al., 2011). This means that most clustering algorithms
most kM messages. assume near-static scenarios so that clusters are formed using
In short, the time and message complexities increase with the static and the latest information. However, in real scenarios,
number of hops between member nodes and their clusterhead in a clusters are formed in the presence of network dynamics.
cluster (or cluster size), and the amount of clustering messages The common channels in a cluster are homogeneous in terms of
associated with a clustering algorithm. channel quality, and this can be seen in the widely use of the
number of common channels in a cluster (see Section 4.1, P.2) as a
performance metric. However, in real scenarios, clustering algo-
5. Open issues rithms should consider the channel quality of the common
channels.
This section discusses open issues that can be pursued in this Performance metrics such as the number of clusters, the
research area in order to address the shortcomings of existing number of common channels in a cluster, and the number of
clustering algorithms. re-clustering (see Section 4.1), are commonplace to measure
the performance of clustering algorithms, rather than the
5.1. Cluster maintenance: migration of clusterhead, cluster merging, overall network-wide QoS performance, including throughput,
cluster splitting, node joining and node leaving end-to-end delay, jitter and packet loss rate. Hence, the
investigation on achieving satisfactory QoS performance in
The objective of cluster maintenance is to provide smooth various clustering algorithms is necessary.
procedures of the migration of clusterhead in a cluster, cluster
merging, cluster splitting, node joining and node leaving. Migration
of clusterhead is initiated to change the clusterhead node in a cluster 5.3. Tradeoff between various network performance metrics
so that a more suitable member node is selected to better serve as a
clusterhead for the cluster. Cluster merging combines adjacent Various network performance metrics (see Section 4.1) have
clusters; while cluster splitting separates a single cluster into more been applied in the investigation of clustering algorithms in CR
than ones. Both cluster merging and splitting require re-clustering, networks. Examples of the tradeoffs are as follows:
and the clusterhead should be maintained, re-elected or withdrawn
to ensure that there is only a single clusterhead in a cluster. Node Cluster size (see Section 4.1, P.1) and number of common channels in a
joining and leaving affects the traffic amount. In CR networks, there cluster (see Section 4.1, P.2). Larger cluster size increases the number
of member nodes in a cluster; and it has been shown to reduce the regards to the operation of CR as a whole, rather than the effects of
overall network overhead (e.g. resource management and routing). clustering on some particular objectives or applications (Guo et al.,
However, larger cluster size reduces the number of common 2009).
channels in a cluster (Kim, 2009), and so it affects cluster stability
and may increase the occurrence of re-clustering.
5.6. Optimal cluster size
Number of common channels in a cluster (see Section 4.1, P.2) and
number of common channels with neighboring clusters (see
There are pros and cons with larger and smaller cluster sizes.
Section 4.1, P.9). While higher number of common channels in
Clustering algorithms may determine the optimal cluster size,
a cluster and with neighboring clusters are both favorable,
although it may change with network scenarios. For instance,
achieving a balanced number of channels for both intra-cluster
cluster size may reduce with higher nodal mobility (Huang et al.,
and inter-cluster communications are both important to ensure
2011).
connectivity throughout the entire networks. However, higher
There are three main advantages of smaller cluster size (or
number of common channels in a cluster may cause lower
larger number of clusters). Firstly, it reduces energy consumption
number of common channels with neighboring clusters.
associated with the exchanges of local clustering information, such
as the contribution values (Wei and Zhang, 2010) (see Section
Future research could be pursued to investigate approaches to
3.4.1). Secondly, it increases parallelism and so it reduces proces-
achieve a balanced tradeoff among the network performance metrics.
sing delay. Thirdly, it increases cluster stability because it increases
the number of common channels for intra-cluster communication,
5.4. Gateway's schedule for intra-cluster and inter-cluster
and reduces the occurrence of re-clustering.
communications
The main advantage of larger cluster size is that, it reduces
overhead associated with inter-cluster communication, particu-
Gateway nodes, which are the member nodes located at the
larly resource management and routing overheads.
fringe of a cluster, can hear from neighboring clusters, and so they
Future research could be pursued to achieve an optimal cluster
provide both intra-cluster and inter-cluster communications. Since
size in order to achieve a balanced tradeoff.
adjacent clusters may use distinctive common channels, regular
channel switches may be necessary at gateway nodes. An optimal
schedule for channel switches is necessary so that a gateway node 5.7. Other open Issues
listens to the right channel, and this ensures successful transmis-
sions while minimizing packet collisions in both clusters. More in-depth research could be pursued in most clustering
algorithms in order to further understand and enhance various
5.5. Effects of clustering to cognitive radio schemes aspects of the new and existing algorithms. The following inves-
tigations can be performed to enhance clustering algorithms:
Clustered networks support cooperative tasks, such as channel
sensing, dynamic channel selection and routing; however, the Generally speaking, Table 1 shows a wide range of potential
effects of clustering on the QoS of a wide range of applications are open issues and enhancements that could be further investi-
yet to be explored. Examples of the different applications are as gated. For instance, there has been lack of research efforts in
follows: the investigation of providing shorter intra-cluster distance
(see Section 4.1, P.6), lower level of overlap among clusters (see
In channel sensing, the SU member nodes sense for white Section 4.1, P.7), and lower error probability in sensing out-
spaces and send the sensing outcomes to their respective comes (see Section 4.1, P.10).
clusterheads for final decisions on channel availability. The Cluster size tends to change with the number of common
accuracy of the final decisions on sensing outcomes may be channels in a cluster, and so it varies with PU activities. Hence,
affected by the number of member nodes in a cluster (or cluster a highly dynamic operating environment may affect cluster
size), with larger cluster size being favorable. stability. This may cause high occurrence of re-clustering with
In dynamic channel selection, nodes in a cluster choose a constant migration of clusterhead, cluster merging, cluster
common channel for control and data transmissions. Channel splitting, node joining and node leaving. Future research could
contention may be affected by cluster size, with smaller cluster be pursued to investigate clustering in highly dynamic operat-
size being favorable. This means that smaller cluster size ing environment.
reduces channel contention with neighboring clusters, All connected nodes must be clustered, or associated with at
although larger cluster size has been shown to reduce the least a single cluster, within a certain amount of time during
overall overhead (e.g. resource management and routing). cluster formation. Further research could be pursued to ensure
In routing, larger cluster size reduces routing overheads, which that cluster formation in most clustering algorithms forms
are broadcast among the clusterheads, although it may incur connected and clustered networks if the equivalent flat net-
higher amount of clustering and control overheads between works (or non-clustered networks) are connected.
clusterhead and member nodes. Cluster stability may be Mathematical models of the clustering algorithms for CR net-
jeopardized due to the lack of a common channel because works can be developed so that the algorithms can be analyzed
larger cluster size reduces the number of common channels in mathematically. Various analytical results, such as the mean,
a cluster (Asterjadhi et al., 2010). upper and lower bounds of network performances, achieved by
the algorithms can be derived. Additionally, the clustering
Future research could be pursued to investigate approaches to algorithms can be analyzed with respect to various network
achieve a balanced tradeoff among the clustering metrics (e.g. scenarios, such as single-hop or multiple-hop clusters.
number of clusters, and number of common channels in a cluster)
and application metrics (e.g. accuracy of the sensing outcomes and 6. Conclusions
channel contention level). Further research could also be pursued
to investigate a clustering framework in which the effects of In this article, we have presented a review on clustering
clustering on network performance and QoS are investigated in algorithms to establish single-hop or multiple-hop clusters in
Cognitive Radio (CR) networks. There are five types of clustering Khan AuR, Madani SA, Hayat K, Khan SU. Clustering-based power-controlled
objectives, namely the establishment of common control channel, routing for mobile wireless sensor networks. Int J Commun Syst 2011;25(4):
529–42.
minimizing the number of clusters in the network, as well as Kim C-J, Kim S-W, Kim J, Pyo C. Dynamic spectrum access/cognitive radio activities
enhancements on cluster stability, energy efficiency and coopera- in Korea. In: Proceedings of the IEEE symposium on new frontiers in dynamic
tive tasks; and four types of clustering metrics, namely channel spectrum access networks (DySPAN’10), Singapore; 6–9 April 2010. p. 1–5.
Kim M-R. Distributed coordination protocol for common control channel selection
availability (e.g. the number of common channels in a node pair), in multichannel ad-hoc cognitive radio networks. In: Proceedings of the IEEE
geographical location, signal strength and channel quality, as well conference on wireless and mobile computing, networking and communica-
as node degree. The algorithms are characterized by clustering tions (WIMOB’09), Marrakech, Morocco; 12–14 October 2009. p. 227–32.
Lee K, Lee H. Energy-efficient self-organized clustering with splitting and merging
objectives and clustering metrics. Generally speaking, clustering
for wireless sensor networks. Int J Distrib Sens Netw 2013:1–11.
algorithms aim to achieve lower number of clusters in a network Li D, Gross J. Robust clustering of ad-hoc cognitive radio networks under
and higher number of common channels in each cluster. Certainly, opportunistic spectrum access. In: Proceedings of the IEEE international
conference on communications (ICC’11), Kyoto, Japan; 5–9 June 2011. p. 1–6.
there is plenty of future work in addressing the open issues
Li X, Hu F, Zhang H, Zhang X. A cluster-based MAC protocol for cognitive radio ad
associated with clustering algorithms in the conventional CR hoc networks. Wirel Pers Commun 2012;69(2):937–55.
networks, and this article has laid a great foundation and sparked Liming X, Xiaohua J, Kunxiao Z. QoS multicast routing in cognitive radio ad hoc
new research interests in this area which has remained in the networks. Int J Commun Syst 2012;25(1):30–46.
Liu C. Design on common control channel of MAC protocol of cognitive radio
infancy stage. networks. In: Proceedings of the international conference on electrical and
control engineering (ICECE’10), Wuhan, China; 25–27 June 2010. p. 3621–4.
Liu S, Lazos L, Krunz M. Cluster-based control channel allocation in opportunistic
cognitive radio networks. IEEE Trans Mob Comput 2012;11(10):1436–49.
Acknowledgment Nafees M, Islam AKMM, Zareei M, Baharun S, Komaki S. Spectrum aware cluster-
based architecture for cognitive radio ad-hoc networks. In: Proceedings of 2nd
This work was supported by the Malaysian Ministry of Science, international conference on advances in electrical engineering (ICAEE’13),
Dhaka, Bangladesh; 2013. p. 181–5.
Technology and Innovation (MOSTI) under Science Fund 01-02-16- Nekovee M. Impact of cognitive radio on future management of spectrum. In:
SF0027. Proceedings of 3rd international conference on cognitive radio oriented
wireless networks and communications (CROWNCOM’08), Singapore; 15–17
May 2008. p. 1–6.
References Network Simulator 3 (NS-3). Available online: 〈http://www.nsnam.com〉; 2013
[accessed 16.08.13].
OMNeTþ þ. Available online: 〈http://www.omnetpp.org〉; 2013 [accessed 16.08.13].
Akyildiz IF, Lee WY, Vuran MC, Mohanty S. Next generation/dynamic spectrum Office of Communications (Ofcom). Digital dividend review, a statement on our
access/cognitive radio wireless networks: a survey. Comput Netw 2006;50 approach to awarding the digital dividend. Resource document. Ofcom. Avail-
(13):2127–59. able online: 〈http://stakeholders.ofcom.org.uk/binaries/consultations/ddr/state
Alsarhan A, Agarwal A. Cluster-based spectrum management using cognitive radios ment/statement.pdf〉; 200. [accessed 16.08.13].
in wireless mesh networks. In: Proceedings of 18th international conference on Ozger M, Akan OB. Event-driven spectrum-aware clustering in cognitive radio
computer communications and networks. (ICCCN), San Francisco, CA; 3–6 sensor networks. In: Proceedings of the IEEE conference on computer and
August 2009. p. 1–6. communications (INFOCOM’13), Turin, Italy; 14–19 April 2013. p. 1483–91.
Asterjadhi A, Baldo N, Zorzi M. A cluster formation protocol for cognitive radio ad Peiravi A, Mashhadi HR, Javadi SH. An optimal energy-efficient clustering method
hoc networks. In: Proceedings of the European wireless conference (EW’10), in wireless sensor networks using multi-objective genetic algorithm. Int
Lucca, Italy; 12–15 April 2010. p. 955–61. J Commun Syst 2013;26(1):114–26.
Baddour KE, Ureten O, Willink TJ. A distributed message-passing approach for Qualnet. Available online: 〈http://web.scalable-networks.com/content/qualnet〉;
clustering in cognitive radio networks. Wirel Pers Commun 2011;57(1):119–33. 2013 [accessed 16.08.13].
Badoi, C-I, Croitoru, V, Popescu, A. HC-IPSAG cognitive radio routing protocol: Ramli A, Grace D. RF signal strength based clustering protocols for a self-organizing
models and performance. In: Proceedings of the wireless and optical commu- cognitive radio network. In: Proceedings of 7th international symposium on
nications networks (WOCN’11), Paris, France; 24–26 May 2011. p. 1–5. wireless communication systems (ISWCS’10), York, UK; 19–22 September 2010.
Bettstetter C, Konig S. On the message and time complexity of a distributed mobility – p. 228–32.
adaptive clustering algorithm in wireless ad hoc networks. Available online: 〈http:// Rayment SG, Eccelsine P, Chouniard G, Lubar D, Christensen M, Austin M,
citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.98.1082&rep=rep1&type=pdf〉; Sandmann M. Regulatory tutorial material. In: IEEE ECSG on whitespace sg-
2013 [accessed 08.08.13]. whitespace-09/0048r5. Available online: 〈https://mentor.ieee.org/802-sg-white
Bradonjic M, Lazos L. Graph-based criteria for spectrum-aware clustering in space/dcn/09/sg-whitespace-09-0048-05-0000-regulatory-tutorial-material.
cognitive radio networks. Ad Hoc Netw 2012;10(1):75–94. ppt〉; 2009 [accessed 16.08.13].
Chen T, Zhang H, Maggio GM, Chlamtac I. Topology management in CogMesh: a Sharma P, Abrol V. Optimized cluster head selection & rotation for cooperative
cluster-based cognitive radio mesh network. In: Proceedings of the IEEE spectrum sensing in cognitive radio networks. In: Proceedings of 10th inter-
international conference on communications (ICC’07), Glasgow, Scotland; 24– national conference on wireless and optical communications networks
28 June 2007. p. 6516–21. (WOCN’13), Bhopal, India; 2013. p. 1–5.
Ephremides A, Wieselthier JE, Baker DJ. A design concept for reliable mobile radio Talar AC, Altilar DT. United nodes: cluster-based routing protocol for mobile
networks with frequency hopping signaling. Proc IEEE 1987;75(1):56–73. cognitive radio networks. IET Commun 2011;5(15):2097–105. http://dx.doi.
Fan Z, Rocky Z. Spectrum allocation and medium access in cognitive radio wireless org/10.1002/dac.1280.
networks. In: Proceedings of the European wireless conference (EW’09), Talay AC, Altilar DT. Self adaptive routing for dynamic spectrum access in cognitive
Aalborg, Denmark; 17–20 May 2009. p. 90–5. radio networks. J Netw Comput Appl 2013;36(4):1140–51.
Federal Communications Commission (FCC). First report and notice of rulemaking Wei J, Zhang X. Energy-efficient distributed spectrum sensing for wireless cognitive
in the matter of unlicensed operation in TV broadcast bands. Resource radio networks. In: Proceedings of the IEEE conference on computer and
document. FCC. Available online: 〈http://www.apwpt.org/downloads/ communications (INFOCOM’10), San Diego, CA; 15–19 March 2010. p. 1–6.
fcc_2012-11906_exemptedt.pdf〉; 2006 [accessed 16.08.13]. Xu G, Tan X, Wei S, Guo S, Wang B. An energy-driven adaptive cluster-based
Gong L, Chen J, Tang W, Li S. A multi-channel access-based clustering protocol in rotation algorithm for cognitive radio network. In: Proceedings of 1st interna-
hierarchical spectrum sharing network. In: Proceedings of 11th IEEE Singapore tional conference on pervasive computing signal processing and applications
international conference on communication systems (ICCS’08), Guangzhou, (PCSPA’10), Harbin, China; 17–19 September 2010. p. 138–41.
China; 19–21 November 2008. p. 1005–9. xG technology. 〈http://www.xgtechnology.com〉; 2013 [accessed 6.04.13].4.
Guo C, Peng T, Xu S, Wang H, Wang W. Cooperative spectrum sensing with cluster- Zhang H, Zhang Z, Dai H, Yin R, Chen X. Distributed spectrum-aware clustering in
based architecture in cognitive radio networks. In: Proceedings of the IEEE 69th cognitive radio sensor networks. In: Proceedings of the IEEE global telecom-
vehicular technology conference (VTC Spring’09), Barcelona, Spain; 2009. munications conference (GLOBECOM’11), Houston, Texas; 5–9 December 2011.
p. 1–5. p. 1–6.
Huang X-L, Wang G, Hu F, Kumar S. Stability–capacity–adaptive routing for high- Zhang J-Z, Fan W, Yao F-Q, Zhao H-S, Li Y-S. Cluster-based distributed topology
mobility multihop cognitive radio networks. IEEE Trans Veh Technol 2011;60 management in cognitive radio ad hoc networks. In: Proceedings of the
(6):2714–29. international conference on computer applications and system modeling
Jeng AAK, Jan R-H. The r-neighborhood graph: an adjustable structure for topology (ICCASM’10), Taiyuan, China; 22–24 October 2010. p. 544–8.
control in wireless ad hoc networks. IEEE Trans Parallel Distrib Syst 2007;18 Zou C, Chigan C. On game theoretic DSA-driven MAC for cognitive radio networks.
(4):536–49. Comput Commun 2009;32(18):1944–54.

Microwave Weewr

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

Microwave Weewr

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Microwave Weewr

Uploaded by

Copyright:

Available Formats

Journal of Network and Computer Applications 45 (2014) 79–95

Contents lists available at ScienceDirect

Journal of Network and Computer Applications

Clustering algorithms for Cognitive Radio networks: A survey

4. Performance enhancements and complexity analysis of clustering algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

1. Introduction performance enhancements, complexity analysis (i.e. time and

Fig. 2. A cluster structure in a CR network consists of PUs and SUs.

Fig. 3. Taxonomy of clustering attributes in CR networks.

ðM 1;2 ; nÞ. A common control channel is selected out of the available

3.2. Enhancement on cluster stability

This section presents clustering algorithms whose main objec-

where ni,m represents the number of one-hop and two-hop

The nature of product in MEB exhibits a higher sensitivity to

Using one of the three proposed clustering algorithms (i.e.

3.3.2. Ozger's event-driven approach

cluster, as well as with two-hop nodes, which are from neighbor-

References Clustering objective Clustering attributes

Clustering metric Intra-cluster distance

References Performance enhancements compared to existing approaches Simulation tool

You might also like