Channel-Hopping Multiple Access
Asimakis Tzamaloukas and J.J. Garcia-Luna-Aceves
Computer Engineering Department
Baskin School of Engineering
University of California, Santa Cruz, California 95064
f
jamal, jj
g
@cse.ucsc.edu
Abstract— The medium-access control (MAC) protocols for wireless networks
proposed or implemented to date based on collision-avoidance handshakes between
sender and receiver either require carrier sensing or the assignment of unique codes
to nodes to ensure that intended receivers hear data packets without interference
from hidden sources. We present and analyze aprotocol that we call channel-hopping
multiple access (CHMA) for multi-channel, ad-hoc networks which does not require
carrier sensing or the assignment of unique codes to nodes to ensure collision-free
reception of data at the intended receivers in the presence of hidden terminals. We
compare CHMA against MACA-CT and show considerable improvement in the per-
formance achieved. The correct avoidance of collisions in CHMA protocols is veri-
fied, and their throughput and delay characteristics is studied analytically. CHMA
protocols are applicable to ad-hoc networks based on commercial off-the-shelf spread
spectrum radios operating in unlicensed frequency bands.
I. INTRODUCTION
Medium-access control (MAC) protocols based on collision avoid-
ance have received considerable attention over the past few years, be-
cause they are simple to use in wireless LANs and ad-hoc networks.
The traditional collision-avoidance protocols, a node that needs to
transmit data to a receiver first sends a request-to-send (RTS) packet to
the receiver, who responds with a clear-to-send (CTS) if it receives the
RTS correctly. A sender transmits a data packet only after receiving a
CTS successfully. Several variations of this scheme have been devel-
oped since SRMA (split-channel reservation multiple access) was first
proposed by Kleinrock and Tobagi [10], including IEEE 802.11 [1]
and FAMA [3]. More recently, receiver-initiated collision-avoidance
protocols have also been proposed for single-channel networks, in
which the receiver initiates the collision-avoidance handshake [5], [9].
The need for collision-avoidance MAC protocols for single-channel
networks to sense the channel as an integral part of the collision-
avoidance handshake limits their applicability. Most commercial ra-
dios do not provide true carrier sensing, and direct sequence spread-
spectrum (DSSS) radios may capture none or one of multiple over-
lapping transmissions depending on the proximity and transmission
power of the sources. Even if frequency-hopping spread-spectrum
(FHSS) radios are used, carrier sensing adds to the complexity of the
radio, which has already to provide coarse time synchronization at the
dwell-time level.
In the past, several MAC protocols have been proposed and an-
alyzed that take advantage of spreading codes for multiple access.
Sousa and Silvester [8] presented and analyzed various spreading-
code protocols that are sender-, receiver- or sender-receiver based, i.e.,
in which codes are assigned to senders, receivers, or combinations.
Gerakoulis et. al. [6] used carrier sensing to propose a receiver-based,
asynchronous transmissions protocol. Several other proposals have
been made to implement correct collision-avoidance in multi-hop net-
works without requiring nodes to use carrier sensing; these proposals
rely on multiple codes assigned to senders, receivers or a combina-
tion of the two, to eliminate the need for carrier sensing (e.g., [2], [4],
[7]). The limitation of protocols based on code assignments is that
This work was supported by the Defense Advanced Research Projects Agency (DARPA) under Grant
No. F30602-97-2-0338.
senders and receivers have to find each others’ codes before commu-
nicating with one another. Most of the commercial DSSS radios today
use only 11 chips per bit therefore CDMA is not an option. On the
other hand, according to the FCC regulations up to 15 FHSS radios
can be co-located with minimum interference problems. In ad-hoc
networks built with commercial radios operating in ISM bands, code
assignments do not guarantee that receivers can capture one of multi-
ple simultaneous transmissions.
Section II describes a new protocol that that operates over any
spread spectrum modulation and does not require code assignments or
carrier sensing. We call this new protocol CHMA (channel hopping
multiple access). According to CHMA, all nodes in a network are re-
quired to follow a common channel-hopping sequence. A channel can
be defined to be a frequency hop, a spreading code, or a combination
of both. At any given time, all nodes that are not sending or receiving
data listen on the common channel hop. To send data, nodes engage
in a sender-initiated dialogue over the channel hop in which they are
at the time they require to send data; those nodes that succeed in a
collision-avoidance handshake remain in the same channel hop for the
duration of their data transfer, while the rest of the nodes continue to
follow the common channel hopping sequence. Section III proves that,
in the absence of fading, CHMA protocol provides correct floor acqui-
sition in a multi-hop network. Section IV analyzes the throughput in
unslotted, multi-hop networks with CHMA. We compare CHMA with
the MACA-CT protocol [7], which uses MACA collision-avoidance
handshakes over a common channel and a transmitter-oriented data
channel assigned to avoid collisions of data packets; we chose MACA-
CT for our comparison, because it is essentially the same concept as
that used in CHMA and is a good representative of collision-avoidance
solutions that eliminate the need for carrier sensing at the expense of
requiring unique channel assignments. Section V calculates the sys-
tem delay in multi-hop networks for CHMA as well as MACA-CT.
Section VI presents our conclusions.
II. C
HANNEL-HOPPING PROTOCOLS
A. Basic Concepts in Channel Hopping
Hidden-terminal interference can be eliminated by the assignment
of channels or codes to senders or receivers in a way that no two
senders or receivers share the same code if they are within a two hop
neighborhood. With commercial frequency-hopping radios operating
in ISM bands, radios have to synchronize in time so that all radios hop
to different frequency hops at approximately the same time.
CHMA exploits the fact that the nodes of a frequency-hopping net-
work must agree on when to hop to eliminate hidden-terminal inter-
ference. A common frequency-hopping sequence is assumed by all
the nodes (i.e., a common channel), so that nodes listen on the same
frequency hop pattern at the same time, unless instructed otherwise.
Nodes then carry out a sender-initiated collision-avoidance handshake
to determine which sender-receiver pair should remain in the same hop
in order to exchange data, while all other nodes that are not engaged
in data exchange continue hopping on the common hopping sequence.