Deterministic information-exchange with epidemics in multihop wireless networks

Deterministic neighbor discovery protocols on the other hand, schedule listening and transmission phases to offer a deterministic guarantee on the worst-case neighbor discovery time.

In this work, we therefore propose protocol enhancements that allow for faster average discovery times while maintaining the same worst-case guarantees. Specifically, we propose an epidemic information dissemination mechanism to speed up the discovery times in deterministic neighbor discovery protocols. The main idea is to let each node broadcast information about the beaconing slot locations of already discovered neighbors, so that other nodes in the network that are neighbors to these nodes can discover them much earlier. This simple extension to classical neighbor discovery protocols has two key advantages which lead to strong performance improvements while still ensuring determinism in the discovery.

Preliminaries

Our protocol is an asynchronous cyclic slot-based deterministic discovery protocol based on the ideas developed by previous protocols of this type (emph{e.g.}, Searchlight, Hello}). These protocols operate in cycles defined by two parameters: (a) the period of

slots and (b) the hyper-period

specifying the number of periods within a cycle. Slot sizes are fixed and equal for all nodes. To save energy, nodes are not active throughout, but wake up and communicate occasionally. A discovery occurs when the active slots of two nodes overlap. Active slots are classified into two categories: (i) anchor slots, which always occupy the first position within a period, and (ii) probe slots, whose positions within the cycle vary with time.

Searchlight is based on the observation that the temporal distance between the anchor slots of any two nodes is constant and upper bounded by $leftlfloor frac{p}{2} rightrfloor$ . Hence, by adding an additional probing action that searches slots $1, 2, dots, lfloor frac{p}{2}rfloor$ , discovery is guaranteed. Specifically, Searchlight increments the probe slot position by one every hyper-period, and resets the position to

when it exceeds $lfloor frac{p}{2} rfloor$ . In this way, Searchlight uses $leftlfloor frac{p}{2} rightrfloor$ hyper-periods and the total number of slots required for discovery is never more than $T = pleftlfloor frac{p}{2}rightrfloor$ .

Protocol schedule design

Epidemic probing, activates extra probe slots to rapidly discover possible neighbors within a hyper period.

Epidemic probing mechanism

Each node

maintains, among others, data about its one-hop neighbors. We will demonstrate how this data can be spread epidemically and how nodes can use it to target discovery probes to speed up the neighbor discovery process.

Consider a node

and let

denote the number of time slots since the node was booted. Then

where

is an unknown offset between the global and local notions of time. The local timer t_i

can be also expressed in terms of its period p_i

and its offset delta_i (t_i)

from the anchor slot of the emph{current period} (emph{i.e.}, the period that slot $t_{i}$ belongs to):

where

is the number of periods that have passed since boot time of node

, and

is the number of time slots since the most recent period start. Although nodes do not have access to the global time

, they always know the corresponding values of kappa_i(t)

and

Let $t_{ij}$ be the time (or the slot, since we assume that the slots of all nodes are aligned) emph{of the global clock} at which node

discovers node

. Since we assume mutual discovery, $t_{ij}equiv t_{ji}$ . When node

discovers node

, it shares (i) the number of slots $delta_i(t_{ij})$ of the current slot from the anchor slot of the current period and the size of its period p_i

. Node

shares the corresponding information with node

. Thus, node

can deduce that future anchor slots of node

will appear at

$t_{ij} - delta_i (t_{ij})+k p_i, quad k=1,2, ldots,$

and, similarly, node

can deduce that future anchors of node

will appear at slots

$t_{ij} - delta_j (t_{ij})+m p_j, quad m=1,2, ldots.$

As a result, given the offset and the period, each of the nodes can determine when anchor slots of the other node will appear. For example, node

can compute the offset of the anchor slots of node

emph{relative to its own anchor slots} as the difference between the future anchor slots for both nodes, i.e., by subtracting the first two equations to find

$delta_{ji}(t_{ij},k,m) =t_{ij} - delta_i (t_{ij})+k p_i -(t_{ij} - delta_j (t_{ij})+m p_j) = delta_j(t_{ij}) - delta_i(t_{ij}) - m p_j + k p_i ,$

where

(

is the set of natural numbers). This will be the key expression for computing and updating $delta_{ij}$ , the offset to the first anchor slot of node

relative to the start of the most recent period of node

. Note that no reference to global time is needed to evaluate the expression, all that is required is the quantity $delta_{i}(t_{ij})-delta_j(t_{ij})$ and the period size of the nodes.

By increasing

and

node

finds the number of slots between the

-th anchor slot (after the discovery time) of node

and the

-th anchor slot of node

. As a result, at every time instant

, node

is able to determine $delta_{i}(t)$ of every node

discovered so far.

In our protocol, node

computes the offset $delta_{ji}(t,k,m)$ at every anchor slot. Even though it is not necessary, for simplicity of exposition we assume that the offsets are updated also at the probe slots where there can be a new discovery and a node has to share information with other nodes. In this case, at a discovery time $t_{ i ell}$ , node

can provide the triplet ${j, delta_j(t_{iell}), p_j}$ about already discovered node

to any newly discovered node ell

. Then, node ell

follows the same procedure for computing the relative offset $delta_{ell j}$ as in equation above.

Targeted probes for direct discovery

When nodes

and

discover each other, node

provides, apart from its information ( $delta_j(t_{jell})$ and p_j

), the corresponding information for all nodes

discovered by

until time instant $t_{jell}$ . As a result, node ell

can determine the location of the anchor slots of node

(for passing this information to future discoveries) and those of its discovered neighbors, for which it will initiate targeted probes for direct discovery.

At discovery of node

by node

and node

computes $delta_{ji}$ by adjusting

until it finds the smallest non-negative value of $delta_{ji}(t_{ij},k,0)$ ; if we denote the corresponding

, we have $delta_{ji}(t_{ij},k_0, 0)$ . At the next period start of node

$delta_{ji}=delta_{ji}(t_{ij},k, 1) =delta_j(t_{ij}) - delta_i(t_{ij}) - p_j + k p_i =delta_{ji}(t_{ij},k_0, 0)+ (k-k_0) p_j - p_i .$

To maintain its data structure up to date, node

now needs to adjust $delta_{ji}(t_{ij},k_0, 0)$ so that it becomes equal to the smallest non-negative value of $delta_{ji}(t_{ij},k, 1)$ . We see from the expression above that we can do this by subtracting p_i

from the current value of $delta_{ji}$ , and then add multiples of p_j

until the value becomes non-negative.

Duty-cycle

In deterministic neighbor discovery for which every period

has an anchor, the duty cycle gamma

is given by

$gamma=frac{n+lfloorfrac{p}{2}rfloor}{np},$

where

is the number of periods in a hyper-period. Without receiving any epidemic information, the duty-cycle is the same as the deterministic neighbor discovery protocol used as the basis of our algorithm; in this case it is Searchlight. If there is activation of extra probe slots due to epidemic discovery, our protocol uses extra slots. Therefore, the instantaneous duty-cycle in period

is given by

$gamma_k = frac{n+ lfloor frac{p}{2}rfloor + nu_k}{n lfloor frac{p}{2}rfloor},$

where

is the total number of extra slots activated during period

. When we use Searchlight and striped transmission, the instantaneous duty-cycle becomes

$gamma_k = frac{2(1+Delta)+nu_k(1+Delta)}{p}.$

increases and almost all neighbors have been discovered, nu_k

goes to zero and the instantaneous duty-cycle is the same as that of Searchlight. The average duty cycle over

periods is given by

$gamma =frac{1}{k}sum_{j=1}^k gamma_j = frac{2(1+Delta)k+sum_{j=1}^knu_j(1+Delta)}{pk} .$

$gamma = lim_{krightarrow infty} frac{2(1+Delta)k+sum_{j=1}^knu_j(1+Delta)}{pk}=frac{2(1+Delta)}{p}+frac{(1+Delta)}{t}lim_{krightarrow infty}frac{sum_{j=1}^knu_j}{k} =frac{2(1+Delta)}{p},$

Performance evaluation

We study the following key metrics: (i) discovery latency, i.e., the longest time recorded for any node in the network to discover all its neighbors; (ii) energy consumption, quantified by the duty cycle during the discovery process; and (iii) the performance in dynamic scenarios, where two networks merge, or a single node joins an already converged network.

Worst-case latency

The figure is based on 1000 network realizations (that is, 1000 different realizations of the period offsets for the nodes), each of which is simulated for t^2/4

time slots. We have used p = 200, which corresponds to a duty cycle of 1% and a worst-case discovery time for Searchlightof 10000 slots.

Observation: When there are only two nodes in the network, Searchlightand our epidemic discovery protocol are equivalent. However, as the number of nodes increase, the likelihood that two nodes have an unfortunate offset increases, and many node pairs experience a latency close to the worst-case bound. With epidemic probing, on the other hand, the performance improves as the network size increases. This result can be explained from the fact the larger the clique size, the more information tends to be conveyed by the epidemic probing, and the faster the discovery process comes to an end.

Energy consumption

Observation: Average energy consumption over time (top) and instant energy consumption (bottom) for asymmetric (left) and symmetric (right) discovery. There is an initial increase in the energy consumption, due to the discovery process, but after a while the average energy returns to its nominal value.

Dynamic scenarios

The dynamic increase in duty cycles “when needed” is particularly useful in dynamic scenarios. To make the point, we first consider a scenario where two fully converged networks merge. On such scenario could be when two buses drop their passengers, whose devices have discovered each other during the bus ride, simultaneously at a bus station. The epidemic probing then allows to bootstrap the discovery process at the bus station and allows a rapid and energy efficient discovery of the complete network.

Observation: The initial network discovery on each bus is similar to previous simulations. However, when the two nodes merge, the discovery of the full network is both faster and much more energy efficient. This performance improvement is because when the networks merge, the nodes convey a lot of epidemic information already from the start.

We show the energy consumption when a single node joins a converged network. This node can discover all its neighbors quickly and a modest and temporary increase of duty cycle. The impact on the energy consumption of the other network node is very limited.

Extension to multihop networks

In practice, the network topology is often more complicated than a single clique, and packet transmissions are unreliable. This section extends the concepts developed in the previous sections to neighbor discovery in general networks.

When the network is subject to losses (due to fading or collisions), we cannot just probe once, but should allow for a few discovery attempts. This leads us to include a retry limit

on the number of times we attempt to probe a node after it has become known to us. The selection of

involves a trade-off between energy expenditure for targeted probing of nodes that are not neighbors and the the probability of failing to detect direct neighbors.

Energy consumption

Experimental validation: Indriya testbed

We conducted all our experiments at the Indriya testbed. Indriya is a large-scale and low-power wireless sensor network testbed, consisting of 100 TelosB motes built on an active-USB infrastructure at National University of Singapore.

Average node degree

Instant and average duty-cycle

Observation: The small peaks observed during the stationary period are due to discovery attempts of nodes not previously known. This is also an artefact of lossy communication: sometimes, the epidemic dissemination is delayed due to packet losses. The inner plot highlights the location-dependent performance, where nodes with large two-hop neighborhoods have high peak duty cycles, while sparsely connected nodes have lower energy consumption.

Conclusions

We have proposed a simple yet novel protocol for rapid and deterministic neighbor discovery that employs epidemic probing, a mechanism that dynamically increases the number of active slots whenever this is likely to be useful. During network formation or topology changes, the protocol temporarily spends more energy in speeding up discovery and then returns to a low-energy mode. This results in a protocol with dramatically decreased discovery times and a long-term average energy consumption close to the current state-of-the-art Searchlight protocol. Significant performance benefits were reported in simulations and realworld deployments, in cliques and multi-hop networks, and under reliable and unreliable communication.

Deterministic information-exchange with epidemics in multihop wireless networks

Introduction

Preliminaries

Protocol schedule design

Epidemic probing mechanism

Targeted probes for direct discovery

Duty-cycle

Performance evaluation

Worst-case latency

Energy consumption

Dynamic scenarios

Extension to multihop networks

Energy consumption

Experimental validation: Indriya testbed

Average node degree

Instant and average duty-cycle

Conclusions