Coordinated energy efficient neighbor discovery

With the abundance of cell phones today and the rapid increase in the amount of smart phones and mobile computers available, more and more people have access to communication devices with wireless connectivity. In fact, many of these personal devices now come equipped with multiple wireless radios. Widespread access to wireless communication is allowing developers to create applications that leverage proximity. Rather than using the already overloaded wireless infrastructure, these proximity-based applications allow users to talk directly to one another in a peer-to-peer fashion. However, in order to send information to their neighbors, the devices need to be able to reliably discover each other. Currently, in almost every modern mobile device, the developer has two choices. They can scan for their neighbors using a high power 802.11 radio that will be able to reach a large number of their neighbors at the cost of high battery use or they can use a low power radio that can be used liberally with very little cost to the battery of the phone. However, these low power radios severely limit the number of neighbors that can be found. In order to find a balance between high neighbor discovery range and low battery usage, we explore a hybrid approach that leverages both radios at the same time. Our method creates a cluster of neighboring nodes that are in range of the low power radios. Then, the nodes within the cluster coordinate over the low power radios to share the burden of neighbor discovery over the high cost, long range radio. This distribution of the costly discovery allows users to discover neighbors far away while limiting the cost incurred from using the higher power radio. To test our method, we implemented the protocol as an Android service that can be run on several devices with 802.11 and Bluetooth radios