Pickup Game: Acquainting Neighbors Quickly and Efficiently in Crowd

Effective and energy efficient neighbor discovery protocol is a crucial component for the success of emerging opportunistic encounter-based mobile (ad hoc) networking for social and gaming. In this work, we design P-Game, an effective neighbor discovery protocol to find a group of neighbors. By leveraging a quick estimation of the number of neighbors, we design various protocols for collecting the IDs of these neighboring nodes with the objective of either minimizing the latency of neighbor-discovery process or minimizing the active slots (i.e. energy consumption) of each neighbor. We validate PickupGame through rigorous theoretical analysis. When the required acquaintances k is a constant fraction of neighbors, our protocol is proved to have optimum delay Θ(k) and optimum active slots Θ(1). When we need to find all neighbors, our protocols achieve tradeoffs in the delay and active slots: one approach has discovery latency O(k ln ln k) and active slots O(ln ln k). Our evaluations corroborate our theoretical results and show considerable improvement in discovery latency over existing approaches in almost all cases.