What is Static Graph

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.