A Benchmarking Algorithm to Determine Maximum Lifetime Communication Topologies in Cognitive Radio Ad hoc Networks
Natarajan Meghanathan · 2015
We propose a generic 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 use the licensed channels of the primary user (PU) nodes when the latter do not use them. When in need of a stable communication topology (that spans the SU nodes) at a time instant t, the algorithm looks 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, but 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 mobile graphs and the corresponding instances of the communication topology of interest such that the number of topology transitions is the global minimum. We prove the theoretical correctness of the algorithm and analyze its run-time complexity.