Distributed algorithms for communication problems in heterogeneous cognitive radio networks

The unlicensed wireless spectrum bands are evidently getting over-crowded. On the other hand, studies have shown that the licensed spectrum bands such as TV broadcast and public service bands are largely underutilized. Cognitive Radio technology has emerged as the most promising approach to combat the congestion problem in the wireless spectrum, and will gradually get deployed in a variety of wireless networks, such as mobile ad hoc networks, sensor networks and cellular networks. This brings novel technical challenges to a range of network communication problems, arising from the heterogeneous nature of channel availability across the network. In this dissertation, we model cognitive radio networks as M2HeW, i.e., M ulti-hop Multi-channel Heterogeneous Wireless Networks, and investigate two critical communication problems in the M2HeW model: Neighbor Discovery and Convergecast Scheduling.;An essential step in initializing a wireless ad hoc network is neighbor discovery, in which every node attempts to determine the set of nodes it can communicate within a single hop. We first prove a lower bound on the time complexity of deterministic neighbor discovery, and then design, analyze and evaluate two efficient deterministic algorithms for neighbor discovery in M2HeW networks. We also design and analyze a suite of randomized neighbor discovery algorithms under a variety of conditions.;The next problem is convergecast scheduling which focuses on computing a minimum length schedule for gathering data from all nodes in a M 2HeWnetwork to a designated sink. In time-critical wireless network applications (such as battlefield and disaster relief), data should be periodically delivered to the sink node with minimum delay. We formulate the convergecast scheduling problem in arbitary M2HeW networks as an Integer Linear Program and show the incentive for exploiting multiple channel convergecast scheduling. We design centralized and distributed convergecast scheduling algorithms, and evaluate their performance through theoretical analysis as well as experiments.