Fast information sharing in proximity-based multichannel wireless networksIntroductionThis 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. PreliminariesCoupon 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 in any time slot is given by the probability a node transmits , given that the remaining nodes remain silent. This probability () is given by: the optimal transmit probability is proven to be and substituting , we obtain . The classical coupon collector analysis can be formulated as follows: Let denote the number time-slots to discover all neighbors. Let denote the time a node discovers the node. Let be a random variable that denotes the number of elapsed time-slots starting from the discovery of the node till the discovery of the new node, i.e, . After the discovery of the node, at any random trial, there still exists nodes to be discovered, each with probability . We can deduce that has a geometric distribution with expectation , and by the linearity of the expectations . Therefore, the expected time can be computed as: where denotes the 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 .
Implications to low-power wireless communicationsFor low-power wireless the goal is to having a fast and energy-efficient information exchange, which translates into having a smaller value of .
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 discoveryWe analyze a theoretical three-phase protocol and show that it allows for a discovery-time speedup on the order of 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:
The equation gives the sum of for the coupon collector analysis of the three phase algorithm. 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 (lower bound on ) that minimizes , which gives Hence, the protocol achieves a speedup of roughly compared to the singlechannel protocol References
|