U-Connect

Mobile sensor nodes can be used for a wide variety of applications such as social networks and location tracking. An important requirement for all such applications is that the mobile nodes need to actively discover their neighbors with minimal energy and latency. Nodes in mobile networks are not necessarily synchronized with each other, making the neighbor discovery problem all the more challenging.

Protocol Overview

U-Connect is an unified protocol to address both the symmetric and asymmetric asynchronous neighbor discovery problems. Consider a protocol in which a node picks a prime number p and stays active for 1 every p slots. Any two primes are by definition relatively prime with each other. Hence, two nodes choosing different primes will discover one another. If the nodes choose the same pair of primes, discovery can still be ensured by each node staying active for slightly longer than half the prime period p.

The protocol has been implemented on a custom designed light-weight, small and rechargeable mobile sensor-networking hardware platform called FireFly-Badge. In the implementation, the node listens at the slots that are multiples of p. This operation is fundamentally "Low Power Listening" (LPL), where the listen period is p slots. The node transmits continuously for {p + 1}/2 slots for every hyper-cycle. This periodic transmission is called "Low Power Transmit" (LPT). Clustering the transmission slots in this fashion, enables our implementation to spread the packet transmission over multiple slots, thereby enabling much lower slot sizes.

U-Connect achieves neighbor discovery at minimal and predictable energy costs while allowing nodes to pick dissimilar duty-cycles. We have analytically established that U-Connect is an 1.5-approximation algorithm for the symmetric asynchronous neighbor discovery problem, whereas existing protocols like Quorum and Disco are 2-approximation algorithms. Please refer to () for details.