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

Natarajan Meghanathan (Jackson State University, USA)
DOI: 10.4018/978-1-5225-7598-6.ch089

Abstract

The authors 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, the authors 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) ∩ Gt+1(SU) ∩ .... ∩ Gt+k(SU), is connected and Gt...t+k+1(SU) is not connected. The authors 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. They 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
Top

Background

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.

Complete Chapter List

Search this Book:
Reset