A Graph-Intersection-Based Algorithm to Determine Maximum Lifetime Communication Topologies for Cognitive Radio Ad Hoc Networks

A Graph-Intersection-Based Algorithm to Determine Maximum Lifetime Communication Topologies for Cognitive Radio Ad Hoc Networks

Copyright: © 2018 |Pages: 10
DOI: 10.4018/978-1-5225-2255-3.ch567
(Individual Chapters)
No Current Special Offers


We propose a generic graph intersection-based benchmarking algorithm to arrive at upper bounds for the lifetimes of any communication topology that spans the entire network of secondary user (SU) nodes in a cognitive radio ad hoc network wherein the SUs attempt to access the licensed channels that are not in use. At any time instant t when we need a stable communication topology spanning the entire network, we look for the largest value of k such that the intersection of the static SU graphs from time instants t to t+k, defined as the mobile graph Gt...t+k(SU) = Gt(SU) n Gt+1(SU) n .... n Gt+k(SU), is connected and Gt...t+k+1(SU) is not connected. We repeat the above procedure for the entire network session to determine the sequence of longest-living instances of the mobile graphs and the corresponding instances of the topology of interest such that the number of topology transitions is the global minimum. We prove the theoretical correctness of the algorithm and study its effectiveness by implementing it to determine a sequence of maximum lifetime shortest path trees.
Chapter Preview


Most of the work done so far in the CRAHN literature focused on developing routing solutions that are either full spectrum knowledge based or local spectrum knowledge based. The full spectrum knowledge based solutions assume each SU node to be completely aware of all the available PU channels in the network and choose optimal routes with respect to either minimum number of hops per SU-SU path (Xin et. al., 2005), maximum conflict-free assignment (Zhou et. al., 2009) of PU channels or minimum number of channel switches per SU-SU path (Xin et. al., 2008); there is bound to be switching of channels when none of the common available PU channels for the end nodes of an SU-SU link are the same as the preferred PU channels for one or both the end nodes to which they stay tuned by default for transmission and reception. Such full spectrum knowledge-based solutions take a centralized approach like we took in this chapter; however, the full spectrum knowledge for the current time instant alone cannot be used to arrive at benchmarks for the routing metric, if one intends to stay with a route as long as it exists.

Key Terms in this Chapter

Static Graph: Snapshot of a network of PUs and SUs at any particular time instant.

Shortest Path Tree: A communication topology that is rooted at a specific node and connects every other node in the network on the shortest path (minimum number of hops) to the root node.

Primary User (PU): Licensed user of a cognitive radio network.

Communication Topology: An arrangement of the nodes in the network that can be used for communication between any two nodes in the network.

Topology Lifetime: The duration of existence of a communication topology.

Ad Hoc Network: A decentralized and self-organized network of wireless nodes without any a priori dependence on any infrastructure.

Algorithm: A sequence of steps to perform a particular task.

Secondary User (SU): Unlicensed user of a cognitive radio network who uses one or more available channels of a PU.

Cognitive Radio: A software-defined radio that can dynamically adapt its transmission parameters to the channels (frequencies) available for use in the operating environment.

Mobile Graph: A sequence of static graphs generated for a time period.

Complete Chapter List

Search this Book: