| An ad hoc radio network operates with no existing infrastructure to support communication and co-ordination amongst nodes. Performing complex tasks in such networks often depends on each node initially knowing some information about all other nodes that are within its communication range, i.e., its neighbourhood. In this thesis, we explore the complexity of deterministically learning this initial information.;There are several known algorithms for neighbourhood learning in network models where nodes are stationary. However, even for the most studied models and algorithm classes, it was not known if the best existing algorithms are optimal. We prove new lower bounds that, for several models, are the first non-trivial lower bounds for neighbourhood learning. Our lower bounds also serve to provide the first formal separations between several popular classes of neighbourhood learning algorithms. For some of these classes, the lower bounds show that the best known algorithms are optimal (or nearly optimal).;For networks of mobile nodes, we provide several new formalizations of what neighbourhood learning means when neighbourhoods may change during an algorithm's execution. We also define a new task, delta-local gossip, that involves each node sharing a piece of information with all other nodes that, at some point during the execution of the task, are within a delta-multiple of its transmission range. We then show how a variety of problems can be reduced to delta-local gossip, including several neighbourhood learning tasks, initializating certain neighbourhood maintenance algorithms, and implementing a MAC layer. We provide a deterministic algorithm for delta-local gossip in a model where nodes move along arbitrary, continuous trajectories on the line, and using it, we create new deterministic algorithms for gossiping and geocasting. |
