United we find: Enabling mobile devices to cooperate for efficient neighbor discovery

The recent surge in the use of mobile devices have opened up new avenues for communication. While most existing applications designed to exploit this potential are infrastructure based, there is a growing trend to leverage physical proximity between end-users to enable direct peer-to-peer communication. However, the success of these applications relies on the ability to efficiently detect contact opportunities, Devices that participate in such opportunistic communication often come equipped with multiple radios. For an individual node, performing neighbor discovery can be too expensive with a high-power, long-range radio (e.g., Wi-Fi). On the other hand, relying only on a low-power, short-range radio for detecting neighbors results in significantly fewer available contacts. To mitigate this problem, we have developed CQuest, a novel scheme for more efficient long-range neighbor discovery that leverages the clustering of nodes as well as the radio heterogeneity of mobile devices. The basic idea is that coordination over a low-power, short-range radio can help clustered nodes distribute the load of high-power, long-range scanning. We present results from extensive simulation that shows CQuest discovers significantly more contacts than a low-power only scheme but without incurring the high energy cost usually associated with long-range discovery. We also present results and experience from a successful implementation of the protocol on a testbed of Android G1/G2 phones that shows the feasibility of the protocol in a real network.