Controlling a dynamic network is interesting and important in practical applications, which is to drive the network from any initial state to any desired state. Much research has been conducted in revealing the controllability and seeking the underlying correlations of the network. However, no existing works have considered the time needed to control the network, which we refer to as control latency. In this paper, we initiate the study of control latency of dynamic networks. First of all, we formulate the minimum control latency (MCL) problem for designing the controlling pattern with minimum number of controllers. We show that the MCL problem is NP-hard by reducing the multiprocessor scheduling problem to it. Then, we propose a greedy algorithm for designing a controlling pattern that can control the network within two times the minimum control latency. Moreover, when the control latency is bounded by a given value, we propose another constant approximation algorithm to design a controlling pattern which uses at most three times the minimum number of controllers. We conduct extensive simulations on both synthetic and real networks to corroborate our theoretic analysis.

Rendezvous process is the cornerstone to construct Cognitive Radio Networks (CRNs), through which a secondary user can establish a link for communication with its neighbor on a common channel. Although many blind rendezvous algorithms have been proposed which do not rely on a central controller or a common control channel, all of these works still rely on the global parameters such as the number of licensed channels N and the number of users. This paper aims to design fully distributed blind rendezvous algorithms only based on each user's local information. We first give the Synchronous Check & Hop (SCH) algorithm for two synchronous users where they start the rendezvous process at the same time. The SCH algorithm guarantees rendezvous in O(min{ka,kb} N) time slots where ka,kb are the corresponding number of sensed channels of these two users. Our main contribution is a fully distributed algorithm called Conversion Based Hopping (CBH), where each user only uses its identifier (ID) and its number of sensed channels. CBH guarantees rendezvous between two asynchronous users in O((max{ka,kb})2) time slots. To our knowledge, this is the first result with rendezvous time independent of the global parameter N. We also derive a lower bound of rendezvous time between two users as Ω((ka-kg)(kb-kg)) where k_g is the number of their common channels. All of our results also apply to a more general blind rendezvous problem which we call Oblivious Blind Rendezvous where each user is free to assign their local labels to the sensed channels. Extensive simulation results compared with the state-of-the-art rendezvous algorithms corroborate our theoretical analyses.

Rendezvous process plays an important role in constructing Cognitive Radio Networks (CRNs), through which a user establishes a link on a common licensed channel for communication with its neighbors. Generally, the licensed spectrum is divided into N channels and most blind rendezvous algorithms are realized by the “channel hopping” method where each user repeats a Global Sequence constructed on top of all the N channels. This global sequence based method may contain lots of redundant channels resulting in large rendezvous time especially when the number of available channels each user has only accounts for a small fraction of all the N channels. In this paper, we introduce the Local Sequence based rendezvous algorithms where the local sequence is only constructed on top of each user's available channels and different user's local sequence could be different. Our first local sequence based algorithm called LS can guarantee rendezvous in O(N) time slots for symmetric users (both users have the same set of available channels) and in O(N2) time slots for asymmetric users, which matches the best known results [11]. Our major contribution is the Modified Local Sequence (MLS) based algorithm which can guarantee an exponentially shorter rendezvous time than the best known results when the number of available channels each user has is relatively small. Extensive simulation results comparing with the state-of-the-art rendezvous algorithms corroborate our theoretical analyses.