Background and Motivation

In this paper, we will limit our discussion to the widely-deployed IEEE 802.11 Distributed Coordination Function (DCF) protocol [8]. We begin by reviewing some relevant details of this protocol. IEEE 802.11 recommends the use of a Request To Send (RTS) and Clear To Send (CTS) mechanism to control access to the medium. A sender desiring to transmit a packet must first sense the medium free for a DCF interframe space (DIFS). The sender then broadcasts an RTS packet seeking to reserve the medium. If the intended receiver hears the RTS packet, the receiver sends a CTS packet. The CTS reserves the medium in the neighborhood of the receiver, and neighbors do not attempt to send a packet for the duration of the reservation. In the event of a collision or failed RTS, the node performs an exponential backoff. For additional details, we refer the reader to [8].

The IEEE 802.11 standard divides the available frequency into orthogonal (non-overlapping) channels. IEEE 802.11b specifies 11 channels in the 2.4 GHz spectrum, 3 of which are orthogonal, and IEEE 802.11a specifies 13 orthogonal channels in the 5 GHz spectrum. Packet transmissions on these orthogonal channels do not interfere if the communicating nodes on them are reasonably separated (at least 12 inches apart for common hardware [9]).

Using only a single channel limits the capacity of a wireless network. For example, consider the scenario in Figure 1 where there are 6 nodes within communication range of each other, all the nodes are on the same channel, and 3 of the nodes have packets to send to distinct receivers. Due to interference on the single channel, only one of them, in this case node 3, can be active. In contrast, if all 3 orthogonal channels are used, all the transmissions can take place simultaneously on distinct channels. SSCH captures the additional capacity provided by these orthogonal channels.

Figure 1: Only one of the three packets can be transmitted when all the nodes are on the same channel.

We imposed three constraints on ourselves in the design of SSCH:

• SSCH should require only a single radio per node. Some of the previous work on exploiting frequency diversity has proposed that each node be equipped with multiple radios [9,33]. Multiple radios draw more power, and energy consumption continues to be a significant constraint in mobile networking scenarios. By requiring only a single standards-compliant NIC per node, SSCH faces fewer deployability hurdles than schemes with additional hardware requirements.
• SSCH should use an unmodified IEEE 802.11 protocol (including RTS/CTS) when not switching channels. Requiring standards-compliant hardware allows for easier deployment of this technology.
• SSCH should not cause logical partitions; any two nodes in communication range should be able to communicate with each other despite channel hopping. Because SSCH switches each NIC across frequency channels, different NICs may be on different channels most of the time. Despite this, any two nodes in communication range will overlap on a channel with moderate frequency (e.g., at least 10 ms out of every half second) and discovery is accomplished during this time. The mathematical properties of the SSCH protocol guarantee that this overlap always occurs, even in the absence of synchronization.

SSCH exploits frequency diversity using an approach we call optimistic synchronization. SSCH is designed to make the common case be that nodes are aware of each other's channel hopping schedules, yet SSCH allows any node to change its channel hopping schedule at any time. If node A has traffic to send to another node B, and A knows B's hopping schedule, A will probably be able to quickly send to B by changing its own schedule. In the uncommon case that A does not know B's schedule, or A has out-of-date information about B, then the traffic incurs a latency penalty while A discovers B's new schedule. The SSCH design achieves this good common case behavior when SSCH is used with a workload where traffic patterns change (i.e., new flows are started) with lower frequency than hopping schedule updates are propagated. Because hopping schedule update propagation requires only tens of milliseconds, this is a good workload assumption for many wireless networking scenarios. Our performance evaluation in Section 4 gives absolute numbers for these qualitative claims.

SSCH is designed to work in a single-hop or multi-hop environment, and therefore SSCH must support multi-hop flows. We introduce the partial synchronization technique to allow one node B to follow a channel hopping schedule that overlaps half the time with another node A, and half the time with a third node C; this is necessary for node B to efficiently forward traffic from node A to node C. Although it is trivially possible for node B to have a channel hopping schedule that is an interleaving of A and C's schedules, this leaves open how B will represent its schedule when a fourth node desires to synchronize with B. The design for channel hopping that we describe in Section 3.3 resolves this issue.