Algorithms for Blind Rendezvous in Wireless Networks

Blind rendezvous is a fundamental problem in wireless networks. Rendezvous problems involve a collection of agents, or nodes, each of which would like to discover and communicate with the other agents in the collection who are within its transmission range. Two agents are said to rendezvous when they become aware of one another and are able to communicate. Blindness refers to a set of constraints on any algorithm that is to guarantee rendezvous in a typical wireless network. Agents begin with no knowledge of one another and have no means of coordination other than the common radio channels available to them. Agents are typically not synchronized, so different agents may be deployed with their clocks offset from one another by some amount. Individual agents are identical. This means that two agents operating on a common rendezvous protocol can only make decisions based on their clock readings and on their experiences since deployment. They cannot act differently based on a distinction between their individual identities. Problems of this nature take different forms in various wireless settings. This dissertation describes two different blind rendezvous problems: The multi-channel rendezvous problem pertains to cognitive radio networks where each node has access to a potentially different subset of the radio spectrum, and can only utilize a single radio frequency at one time. The challenge here is achieving rendezvous between agents who each do not know what channel their neighbor will be using at any given time. The energy-constrained, single channel rendezvous problem for wireless sensor networks, in which a sensor node wishes to maximize its battery life by keeping its radio powered off as much a possible, while still achieving a timely rendezvous with neighboring sensors on the network\u27s common radio channel. In the following, we describe the two specific settings in detail, present contributions which advance the state of the art in both settings, and discuss some lines along which we feel further investigation may yield additional progress