An Energy-Optimal Scheme for Neighbor Discovery in Opportunistic Networking

In opportunistic networking, networks are sparse and nodes are moving around, so it is hard to predict when a node gets and how long it keeps in contact with another. For prompt neighbor discovery, a node is assumed to broadcast continuously probing messages to discover another in its vicinity. This kind of persistent probing consumes too much energy for battery- operated devices to afford. One way to save energy for neighbor discovery is simply to turn off radio during non-contact time. In this paper, as the first step toward the general solution, we simplify the problem consisting of one sender and one receiver moving around and present a novel neighbor discovery scheme with radio "on" and "off\´ which is optimal in a sense that it does not miss a contact with the minimum energy consumed.