Uniform Information Exchange in Multi-channel Wireless Ad Hoc Networks

Abstract

Information exchange is a basic primitive for maintaining the smooth running of a network or a system with multiple communicating agents. Given k packets initially stored at k nodes respectively, the problem is to disseminate the k packets to the whole network with the objective of minimizing the time used. We study this problem in single-hop multi-channel networks of n nodes, and target on devising uniform distributed protocols that do not rely on any prior knowledge of network parameters, such as the network size n or the number of packet holders k. Uniform protocols have better scalability and are more suitable for implementation in reality. Specifically, we propose a uniform distributed protocol that with high probability accomplishes the dissemination in O(k/F + F · log n) rounds, assuming F available channels. This protocol is asymptotically optimal when k is large (k ≥ F2 · log n), and provides the best possible linear speedup with multiple channels comparing with the results using a single channel. To the best of our knowledge, this is the first uniform protocol for information exchange in multi-channel networks.