Cognitive radio (CR) is seen as one of the enabling technologies for realizing a new regulatory spectrum management paradigm, viz. opportunistic spectrum sharing (OSS). In the OSS paradigm, unlicensed users (a.k.a. secondary users) opportunistically operate in fallow licensed spectrum on a non-interference basis to licensed users (a.k.a. incumbent or primary users). Incumbent users have absolute priority in licensed bands, and secondary users must vacate the channel where incumbent user signals are detected. A CR network is composed of secondary users equipped with CRs and it can coexist with incumbent users in licensed bands under the OSS paradigm. The coexistence between incumbent users and secondary users is referred to as incumbent coexistence, and the coexistence between CR networks of the same type is referred to as self-coexistence.

In this dissertation, we address three coexistence-related problems at the medium access control (MAC) layer in CR networks: (1) the rendezvous (control channel) establishment problem, (2) the channel assignment problem in an ad hoc CR network, and (3) the spectrum sharing problem between infrastructure-based CR networks, i.e., the 802.22 wireless regional area networks (WRANs). Existing MAC layer protocols in conventional wireless networks fail to adequately address the key issues concerning incumbent and self coexistence that emerge in CR networks. To solve the rendezvous establishment problem, we present a systematic approach, based on quorum systems, for designing channel hopping protocols that ensure a pair of CRs to "rendezvous" within an upper-bounded time over a common channel that is free of incumbent user signals. In a single radio interface, ad hoc CR network, we propose a distributed channel assignment scheme that assigns channels at the granularity of "segments" for minimizing the channel switching overhead. By taking into account the coexistence requirements, we propose an inter-network spectrum sharing protocol that enables the sharing of vacant TV white space among coexisting WRANs. Our analytical and simulation results show that these proposed schemes can effectively address the aforementioned MAC layer coexistence problems in CR networks.