Leveraging multiple channels in Ad Hoc networks

Abstract

We explore the utility of multiple channels of communication in wireless networks under the SINR model of interference. The central question is whether multiple channels can result in linear speedup, up to some fundamental limit. We answer this question a rmatively for the data aggregation problem, perhaps the most fundamental problem in sensor networks. To achieve this, we form a hierarchical structure of independent interest, and illustrate its versatility by obtaining a new algorithm with linear speedup for the node coloring problem.