Time-efficient distributed layer-2 auto-configuration for cognitive radio networks

Cognitive radios (CR) have the ability to dynamically adapt to local spectrum availability. In a network comprised of CR-enabled devices, layer-2 auto-configuration involves determining a common set of channels to facilitate communication among participating nodes. This is a unique challenge as nodes in the CR network may be unaware of (a) their neighbors and (b) the channels on which they can communicate with a neighbor. In this paper, we propose a time-efficient distributed algorithm for layer-2 auto-configuration for a CR network. Our algorithm finds the globally common channel set in 2MN+O(DN)2MN+O(DN) timeslots, where each node is assigned a unique identifier from the range [1,…,N][1,…,N], M is the maximum number of channels available for communication, and D is the diameter of the network. All nodes know M and N. We present both diameter-aware and diameter-unaware versions of the algorithm. We then show that the proposed algorithms are efficient by proving a matching lower bound. Finally, we investigate a special case when nodes have more knowledge available at their disposal and discuss how the time-complexity of our algorithm can be improved under this case.