Exploiting Group Structure in MAC Protocol Design for Multichannel Ad Hoc Cognitive Radio Networks

The design of an efficient medium access control (MAC) protocol for multichannel ad hoc cognitive radio networks is an important problem and has been the topic of extensive recent research. In this paper, we present the design and performance evaluation of a protocol, group MAC (GMAC), which is customized for a situation that commonly arises in ad hoc networks: The network consists of multiple groups of nodes such that a large fraction of the traffic of each node needs to be sent to other nodes of its own group. Some examples are 1) units (e.g., platoons) in a military ad hoc network; 2) divisions in an emergency or disaster relief network; and 3) departments in a corporate or university network. Our protocol requires each secondary node to have only one narrowband transceiver, does not rely on a control channel, and incorporates a novel technique for dynamically balancing the traffic load of secondary nodes across the set of free channels. We formulate the problem of partitioning the network nodes into groups based on the volumes of data traffic to be sent between different pairs of nodes, which we call the group formation problem (GFP). We show that the GFP is NP-complete and propose a greedy algorithm to solve it. We analyze the stability region of the GMAC protocol using a queuing theoretic framework. Our extensive simulations show that a large fraction of the bandwidth unoccupied by primary users is utilized by the GMAC protocol for data transmissions.