Introduction

The problem of supporting multiple senders and receivers in wireless networks has received significant attention in the past decade. One domain where this communication pattern naturally arises is fixed wireless multi-hop networks, such as community networks [1,23,4,6]. Increasing the capacity of such wireless networks has been the focus of much recent research (e.g., [14,20,27]). A natural approach to increase the network capacity is to use frequency diversity [9,31]. Commodity wireless networking hardware commonly supports a number of orthogonal channels, and distributing the communication across channels permits multiple simultaneous communication flows.

Channelization was added to the IEEE 802.11 standard to increase the capacity of infrastructure networks -- neighboring access points are tuned to different channels so traffic to and from these access points does not interfere [9]. Non-infrastructure (i.e., ad-hoc) networks have thus far been unable to capture the benefits of channelization. The current practice in ad-hoc networks is for all nodes to use the same channel, irrespective of whether the nodes are within communication range of each other [4,6].

In this paper, we propose a new protocol, Slotted Seeded Channel Hopping (SSCH), that extends the benefits of channelization to ad-hoc networks. Logically, SSCH operates at the link layer, but it can be implemented in software over an IEEE 802.11-compliant wireless Network Interface Card (NIC). The SSCH layer in a node handles three aspects of channel hopping (i) implementing the node's channel hopping schedule and scheduling packets within each channel, (ii) transmitting the channel hopping schedule to neighboring nodes, and (iii) updating the node's channel hopping schedule to adapt to changing traffic patterns. SSCH is a distributed protocol for coordinating channel switching decisions, but one that only sends a single type of message, a broadcast packet containing that node's current channel hopping schedule. Our simulation results show that SSCH yields a significant capacity improvement in ad-hoc wireless networks, including both single-hop and multi-hop scenarios.

The primary research contributions of our paper can be summarized as follows:

• We present a new protocol that increases the capacity of IEEE 802.11 ad-hoc networks by exploiting frequency diversity. This extends the benefits of channelization to ad-hoc networks. The protocol is suitable for a multi-hop environment, does not require changes to the IEEE 802.11 standard, and does not require multiple radios.
• We introduce a novel technique, optimistic synchronization, for distributed rendezvous and synchronization. This technique allows control traffic to be distributed across all channels, and thus avoids control channel saturation, a bottleneck identified in prior work on exploiting frequency diversity [31].
• We introduce a second novel technique to achieve good performance for multi-hop communication flows. The partial synchronization technique allows a forwarding node to partially synchronize with a source node and partially synchronize with a destination node. This synchronization pattern allows the load for a single multi-hop flow to be distributed across multiple channels.

The rest of this paper is organized as follows: we provide background and motivate the problem in Section 2. In Section 3 we describe SSCH in detail, and in Section 4 we analyze its performance. We discuss design alternatives in Section 5, and we consider related work in Section 6. Finally, we discuss future work in Section 7, and conclude in Section 8.