Fast information sharing in proximity-based multichannel wireless networks

Introduction

This work considers the problem of distributed neighbor discovery in multi-channel wireless networks. We propose a protocol in which nodes randomly select a channel and decide whether to transmit or listen for neighbor discovery beacons. When nodes transmit, they use epidemic information dissemination to spread knowledge about all the nodes they have discovered so far.

Preliminaries

Coupon Collector: In (Vasudevan et al., 2009) the authors noted that the discovery process resembles the classical coupon collector problem in statistics.

Consider a clique network with nodes, where any node can directly communicate with any other node. Under Slotted-Aloha, the probability that a node successfully transmits $p_{s}$ in any time slot is given by the probability a node transmits $p_{t}$ , given that the remaining N-1 nodes remain silent. This probability ( $p_{s}$ ) is given by:

$p_{s} = p_{_{t}}left( 1 - p_{_{t}} right)^{N-1},$

the optimal transmit probability is proven to be $p^{*}_{_{t}}=1/N$ and substituting $p^{*}_{_{t}}$ , we obtain $p_s approxfrac{1}{Ne}$ . The classical coupon collector analysis can be formulated as follows:

Let denote the number time-slots to discover all N-1 neighbors. Let X_i denote the time a node discovers the $i^{th}$ node. Let T_i be a random variable that denotes the number of elapsed time-slots starting from the discovery of the $i^{th}$ node till the discovery of the $(i+1)^{th}$ new node, i.e, $T_i = X_{i+1}-X_i$ . After the discovery of the $i^{th}$ node, at any random trial, there still exists n-i nodes to be discovered, each with probability p_s . We can deduce that T_i has a geometric distribution with expectation $E[T_i]=frac{1}{(n-i)p_s}$ , and by the linearity of the expectations $E[T]=sum_{i=0}^{N-1}E[T_i]$ . Therefore, the expected time can be computed as:

$E[T]=sum_{i=0}^{N-1}E[T_i] =sum_{i=0}^{N-1}frac{1}{(n-i)p_s} approx NeH_N =Ne big( ln N+Theta(1) big) ,$

where H_N denotes the $N^{th}$ harmonic number.

Multichannel coupon collector: In multichannel coupon collector, there are (k) channels, which are used to broadcast information. Before transmitting a packet, each node selects the transmission channel with equal probability. Assuming there are k channels and nodes, the transmission probability is given by $p_t = frac{k}{N}$ .

E[T] as a function of N and k. Employing multichannel communications alone do not perform better. This fact motivates the need to introduce other another approach for neighbor discovery.

Implications to low-power wireless communications

For low-power wireless the goal is to having a fast and energy-efficient information exchange, which translates into having a smaller value of E[T] .

Single channel neighbor discovery suffers many drawbacks: (i) inability to manage the radio interference properly, (ii) network performance degrades with the increase in the number of nodes, (iii) the idle probability tends to be high, which results in unnecessary long discovery times. The probability of an idle slot $p_{idle} = (1 − frac{1}{N})^N$ , which approaches $e^{−1} approx$ 36.8% as N grows large. When the broadcast is unreliable, i.e., when only a subset of the nodes are able to successfully decode a beacon, the discovery times will be even larger.

Multichannel communications alone do not do better either. For example, consider the following facts: (i) the choice of using an empirical number of channels performs worst than a single channel approach; (ii) multichannel communications alone cannot reduce the average discovery latency for any node to discovery all its neighbors.

The critical factors for enhancing neighbor discovery performance are (i) epidemic discovery, and (ii) tuning the number of channels k depending on the network size N. This is the approach we explore in this project.

Assessing the potential of multi-channel epidemic discovery

We analyze a theoretical three-phase protocol and show that it allows for a discovery-time speedup on the order of sqrt{N} We then introduce and analyze a simpler and more easily implementable protocol that retains many of the advantages of the theoretical protocol. The theoretical protocol proceeds in three phases:

Single channel vs multichannel epidemic discovery with k channels; given the network size N we choose k (lower bound on k^* ) that minimizes E[T] .

Multichannel coupon collector: in the first phase, we run k parallel neighbor discovery processes (one per channel), each with N/k nodes (note that if N/k is not an integer we take integers close to N/k, so that the number of nodes in all channels is N);
Epidemic coupoun collector: in the second phase, one node from each of the k channels enters an epidemic dissemination process where nodes broadcast information about all nodes discovered in their respective channels;
finally, the k nodes return to their original channels and broadcast information about all nodes in the network.

The equation gives the sum of E[T] for the coupon collector analysis of the three phase algorithm.

$E[T] = frac{N}{k}left[lnleft(frac{N}{k} right) +Theta(1)right] + kbig(ln k + Theta(1)big)+ Theta(1) approx frac{N}{k}ln(frac{N}{k})+kln k$

Admittedly, this protocol have the first and second phases asymptomatic termination. However, it allows for a simple discovery time estimate (see Figure). Given the network size N we choose k = sqrt{N} (lower bound on k^* ) that minimizes E[T] , which gives

E(T) approx 2sqrt{N}lnleft(sqrt{N}right)= sqrt{N}ln(N).

Hence, the protocol achieves a speedup of roughly compared to the singlechannel protocol

References

Vasudevan et al., 2009, “Neighbor discovery in wireless networks and the coupon collector’s problem”, ACM Mobicom’09