Abstract

This paper argues for the need to address the issue of multi-channel network performance under constraints on channel switching. We present examples from emergent directions in wireless networking to motivate the need for such a study, and introduce some models to capture channel switching constraints. For some of these models, we study connectivity and capacity of a wireless network comprising n randomly deployed nodes, equipped with a single interface each, when there are c = O(logn) channels of equal bandwidth W c available. We consider an adjacent (c, f) channel assignment where a node may switch between f adjacent channels, but the adjacent channel block f is randomly assigned. We show that the per-flow capacity for this channel assignment model is Θ(W cnlogn). We then show how the adjacent (c,2) assignment maps to the case of untuned radios [1]. We also consider a random (c, f) assignment where each node may switch between a pre-assigned random subset of f channels. For � prnd this model, we prove that per-flow capacity is O(W nlogn) (where prnd = 1 − (1 − f f f c)(1 − c−1)...(1 − c − f +1)) f prnd and Ω(W cnlogn), with the conjecture that it is Θ(W nlogn). The capacity constructions presented in this paper are also relevant and applicable to other scenarios including fixed deterministic assignment (which has interesting practical implications for elimination of channel switching costs), and we briefly discuss this issue