We divide the prior work relevant to SSCH into three categories: prior uses of pseudo-random number generators in wireless networking, channel switching for reasons other than capacity improvement, and alternative approaches to exploiting frequency diversity. In the first category, we find that pseudo-random number generators have been used for a variety of tasks in wireless networking. For example, the SEEDEX protocol [29] uses pseudo-random generators to avoid RTS/CTS exchanges in a wireless network. Nodes build a schedule for sending and listening on a network, and publish their seeds to all the neighbors. A node will attempt a transmission only when all its neighbors (including the receiver) are in a listening state. Assuming relatively constant wireless transmission ranges, this protocol also helps in overcoming the hidden and exposed terminal problem. The TSMA protocol [11,12] is a channel access scheme proposed as an alternative to ALOHA and TDMA, for time-slotted multihop wireless networks. TSMA aims to achieve the guarantees of TDMA without incurring the overhead of transmitting large schedules in a mobile environment. Each node is bootstrapped with a fixed seed that determines its transmission schedule. The schedules are constructed using polynomials over Galois fields (which have pseudo-random properties), and the construction guarantees that each node will overlap with only a single other node within a certain time frame. The length of the schedule depends on the number of nodes and the degree of the network. Porting these schedules to a multichannel scenario, where the number of channels is fixed, remains an open problem, and even such a porting would not meet the SSCH goal of supporting traffic-driven overlap. Redi et al. [13] use a pseudo-random generator to derive listening schedules for battery-constrained devices. Each device's seed is known to a base station, which can then schedule transmissions for the infrequent moments when the battery-constrained device is awake. Although pseudo-random generators have been used for a number of tasks (as this survey of the literature makes clear), to the best of our knowledge, SSCH is the first protocol to use a pseudo-random generator to construct a channel hopping schedule.
The second category of prior work is channel switching for reasons other than capacity improvement. MultiNet [10] is the main piece of work that we are aware of in this category. MultiNet allows a NIC to periodically hop between two channels, enabling a single wireless NIC to connect to two logically distinct networks, such as an AP network and an ad-hoc network. MultiNet is designed to provide new functionality: simultaneous connectivity to distinct networks using a single NIC. In contrast, SSCH is designed to yield capacity improvement within a single ad-hoc network.
The third category of prior work we define encompasses all prior approaches to increasing network capacity by exploiting frequency diversity. This is a significant body of work. The first division we make in this body of work is between research that assumes a single NIC capable of communicating on a single channel at any given instance in time, and research that assumes more powerful radio technology, such as multiple NICs [9,30] or NICs capable of listening on many channels simultaneously [26,21], even if they can only communicate on one. Our work falls in to the former category; the SSCH architecture can be deployed over a single standards-compliant NIC supporting fast channel switching.
Dynamic Channel Assignment (DCA) [33] and Multi-radio Unification Protocol (MUP) [9] are both technologies that use multiple radios (in both cases, two radios) to take advantage of multiple orthogonal channels. DCA uses one radio on a control channel, and the other radio switches across all the other channels sending data. Arbitration for channels is embedded in the RTS and CTS messages, and is executed on the control channel. Although this scheme may fully utilize the data channel, it does so at the cost of using an entire radio just for control. MUP uses both radios for data and control transmissions. Radios are assigned to orthogonal channels, and a packet is sent on the radio with better channel characteristics. This scheme gives good performance in many scenarios. However, it still only allows the use of as many channels as there are radios on each physical node. From our perspective, the key drawback to both DCA and MUP is simply that they require the use of multiple radios. Recently, commercial products have appeared that claim the ability to place multiple radios on a single NIC [2]. It is still not known whether these products will ever achieve as many radios on a NIC as there are available channels, nor what their power consumption will be.
A straightforward way to view the different potential gains of SSCH compared to a true multiple radio design is to consider two distinct sources of bottleneck in a single-radio, single-channel system: the saturation of the channel, and the saturation of any particular radio. Conceptually, SSCH significantly increases the channel bandwidth, without increasing the bandwidth of any individual radio. In contrast, a true multiple radio design increases both. A specific example of this difference is that a node using MUP (a true multiple radio design) can simultaneously send and receive packets on separate channels, while a node using SSCH can only perform one of these operations at a time.
We next turn our attention to work assuming more powerful radio technology than is currently technologically feasible. HRMA [35] is designed for frequency hopping spread spectrum (FHSS) wireless cards. Time is divided into slots, each one of which corresponds to a small fraction of the time required to send a packet, and the wireless NIC is on a different frequency during each slot. All nodes are required to maintain synchronized clocks, where the synchronization is at the granularity of slot times that are much shorter than the duration of a packet. Each slot is subdivided in to four segments of time for four different possible communications: HOP-RESERVED/RTS/CTS/DATA. The first three segments of time are assumed to be small in comparison with the amount of time spent sending a segment of the packet during the DATA time interval. To the best of our knowledge, a FHSS wireless card that supports this type of MAC protocol at high data rates is not commercially available.
Another line of related work assumes technology by which nodes can concurrently listen on all channels. For example, Nasipuri et al[26] and Jain et al[21] assume wireless NICs that can receive packets on all channels simultaneously, and where the channel for transmission can be chosen arbitrarily. In these schemes, nodes maintain a list of free channels, and either the sending or receiving node chooses a channel with the least interference for its data transfer. Wireless NICs do not currently support listening on arbitrarily many channels, and we do not assume the availability of such technology in the design of SSCH.
We finally consider prior work that only assumes the presence of a
single NIC with a single half-duplex transceiver. The only other
approach that we are aware of to exploiting frequency diversity under
this assumption is Multichannel MAC
(MMAC) [31].
Like SSCH, MMAC attempts to improve capacity by arranging for nodes to
simultaneously communicate on orthogonal channels. Briefly, MMAC
operates as follows: nodes using MMAC periodically switch to a common
control channel, negotiate their channel selections, and then switch to
the negotiated channel, where they contend for the channel as in IEEE
802.11.
This scheme raises several concerns that SSCH
attempts to overcome. First, MMAC has stringent clock synchronization
requirements, and to the extent that these are relaxed, MMAC must spend
more time on the common control channel doing discovery. Clock
synchronization is particularly hard to provide in multi-hop wireless
networks [19]. In contrast,
SSCH does not require tight clock synchronization because SSCH does
not have a common control channel or a dedicated neighbor
discovery interval. Secondly, synchronization traffic in MMAC
can be a significant fraction of the system traffic, and the
common synchronization channel can become a bottleneck on system
throughput.
SSCH addresses this concern by
distributing synchronization and control traffic across all the available channels. A
third concern with MMAC is that it assumes wireless NICs are capable
of switching across channels in less than a microsecond. As we justify
in the beginning of Section 4, an 80 
s
switching time better reflects the current state of the art in
wireless NIC design, and SSCH performs well with this assumption. A
fourth concern with MMAC is that it may not efficiently support
multi-hop flows because forwarding nodes may not predictably split
their time between their sending and receiving neighbors. SSCH
addresses this by allowing nodes to achieve predictable partial
synchronization with multiple neighbors.
Although this survey does not cover all related work, it does characterize the current state of the field. At the level of detail in this section, prior work such as CHMA [32] is similar to HRMA [35], and MAC-SCC [25] and the MAC protocols implicit in the work of Li et al [24] and Fitzek et al [16] are similar to DCA [33]. However, a final related channel hopping technology that is worth mentioning is the definition of FHSS channels in the IEEE 802.11 [8] specification. At first glance, it may seem redundant that SSCH does channel hopping across logical channels, each one of which (per the IEEE 802.11 specification) may be employing frequency hopping across distinct frequencies at the physical later. The IEEE 802.11 specification justifies this physical layer frequency hopping with the scenario of providing support for multiple Basic Service Sets (BSS's) that can coincide geographically without coinciding on the same logical channel. In contrast, SSCH does channel hopping so that any two nodes can coincide as much or as little of the time as they desire. This is also at the heart of the difference between SSCH and past work on channel-hopping protocols where nodes overlap a fixed fraction of the time [12] - the degree of overlap between any two nodes using SSCH is traffic-dependent.