Cognitive Radio (CR) is one possible option for mitigating the inefficient wireless spectrum distribution that occurs as a result of fixed spectrum allocation. The use of Dynamic Spectrum Access capabilities will potentially enable secondary users to utilize available and unoccupied frequency slots (channels) whenever the licensed users for those channels are absent. In Cognitive Radio Networks (CRNs), whenever users access the spectrum in an opportunistic manner, control messaging is a crucial issue to ensure that secondary users, i.e. Cognitive Radio Users (CRUs), do not interfere with the licensed users, i.e. Primary Users. In CRNs, where not all CRUs share the same set of channels, i.e. CRUs with Heterogeneous Frequency Devices (HFD), a set of channels must be chosen with care to allow all CRUs in the network to be able to transmit and receive control information. The thesis considers how Control Messaging Schemes (CMSs) can be used within CRNs and proposes a novel CMS for a CRN supporting HFDs. The thesis starts by classifying the CMSs; generating a new taxonomy and identifying the main characteristics for an efficient CRN with HFD. Then, different mathematical approaches for choosing the set of channels used for control information are presented. Next, a CMS for a CRN with HFDs model based upon the aforementioned characteristics and calculating the minimum number of channels for transmitting control information is proposed. Finally the thesis concludes with a number of CMS being presented and evaluated in terms of their impact upon transmission efficiency.