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.

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 the paper published at IPSN'10 for details.

Protocol Overview

U-Connect is an unified protocol to address both the symmetric and asymmetric asynchronous neighbor discovery problems.
The intuition behind the protocol design is as follows. Consider a protocol in which a node picks a prime number p and stays active for 1 slot 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 /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. The operation of U-Connect for a duty-cycle of 1.5%, i.e. prime p=101, is depicted in the figure below.

Image(operation.png, 300px)

Interoperability

In applications where the mobile nodes use infrastructure support,
interoperability of the neighbor discovery protocol with the MAC
protocol used by the infrastructure nodes for data flows is a desired feature.
For example, the networks deployed as part of Sensor Andrew use BMAC as
the MAC protocol.
U-Connect achieves interoperability with LPL-based MAC protocols such as
B-MAC by transmitting for duration equal to BMAC's check-period, whenever a packet needs to be sent to an infrastructure node. Also U-Connect will be able to receive any BMAC packet
as long as the listen period of U-Connect is less than the
check period used by BMAC.

Slot Non-Alignment

In practice, slots will rarely be aligned since nodes run independently
and do not adjust for clock skews or set up a global time-reference. We
need to ensure that two nodes will discover each other regardless of how
their slots overlap. In U-Connect, when in LPT mode of operation,
an unmodulated preamble is transmitted for $\rho$ consecutive slots.
The actual data, which is the node id in our implementation, is sent at the end of this
preamble. Any other node that wakes up during this LPT will find the channel
busy and will receive the data at the end of the preamble. When this
happens, both nodes will attempt to transmit at the same time resulting
in a collision. To avoid collisions in our protocol a CCA check is done before transmitting.
Also, since the probability of two nodes being exactly phase-aligned to come in contact is low, we have not taken any explicit measures to overcome this.

operation.png (43.9 kB) Arvind Kandhalu, 02/11/2010 01:13 am