Speedup of information exchange using multiple channels in wireless ad hoc networks

Abstract

This paper initiates the study of distributed information exchange in multi-channel wireless ad hoc networks. Information exchange is a basic operation in which each node of the network sends an information packet to other nodes within a specific distance R. Our study is motivated by the increasing presence and popularity of wireless networks and devices that operate on multiple channels. Consequently, there is a need for a better understanding of how and by how much multiple channels can improve communication. Based on the SINR interference model, we propose a multi-channel network model which incorporates certain features commonly seen in wireless ad hoc networks, including asynchrony, little non-local knowledge, limited message size, and limited power control. We then present a randomized algorithm that can accomplish information exchange in O ((Δ/F + Δlog n/P) log n + log Δ log n) timeslots with high probability, where n is the number of nodes in the network, Δ is the maximum number of nodes within the range R, F is the number of available channels and P is the maximum number of packets that can fit in a message. Our algorithm significantly surpasses the best known results in single-channel networks, achieving a Θ(F) times speedup if Δ and P are sufficiently large. We conducted empirical studies that confirmed the performance of the proposed algorithm as derived in the analysis.