Efficient information exchange in single-hop multi-channel radio networks

Abstract

This paper studies the information exchange problem in single-hop multi-channel radio networks, which is to disseminate k messages stored in k arbitrary nodes to the entire network (with n nodes) with the fewest timeslots. By using Θ(√n) channels, the previous best result [9] showed that this problem can be solved in Θ(k) time slots with high probability even if k is unknown and no bounds on k are given. Under the same assumptions but by using Θ(n) channels, this paper presents a novel randomized distributed algorithm called Detect-and-Drop that can solve the information exchange problem in O(logkloglogk) time slots with high probability. Thus by allowing using more channels, our proposed algorithm contributes an exponential improvement in running time compared to that in [9]. The simulation results corroborate the analysis result. © 2012 Springer-Verlag.