Critique paper on wireless network research paper

FD-MMAC: Combating Multi-Channel Hidden and Exposed Terminals Using a Single Transceiver

Yan Zhang, Loukas Lazos, Kai Chen, Bocan Hu, and Swetha Shivaramaiah Dept. of Electrical and Computer Engineering, University of Arizona

Email: {yanzhang, llazos, chenkai, bocanhu, sshivaramaiah}@email.arizona.edu

Abstract—We address the problem of improving the throughput and delay efficiency of distributed multi-channel MAC (MMAC) protocols. We design an MMAC protocol called FD-MMAC that exploits recent advances in full-duplex (FD) communications to coordinate channel access in a distributed manner. Compared with prior MMAC designs, the FD-MMAC protocol eliminates the use of in-band or out-of-band control channels for combat- ing the multi-channel hidden terminal problem, discovering the resident channel of destinations, and performing load balancing. Furthermore, FD-MMAC improves the spectral efficiency by enabling the operation of multi-channel exposed terminals. To achieve its goals, FD-MMAC integrates an advanced suite of PHY-layer techniques, including self interference suppression, error vector magnitude and received power measurements, and signal correlation techniques. We validate the proposed PHY-layer techniques on NI USRP devices. Further, we show via simulations that FD-MMAC achieves significantly higher throughput and lower delay compared with prior art.

I. INTRODUCTION

The delay and throughput performance of wireless net-

works can be significantly improved by accommodating parallel

transmissions over orthogonal frequency bands. Most wireless

standards (e.g., [1]) already provision for multiple bands, herein

referred to as channels. For networks without centralized con- trol, channel access is coordinated in a distributed fashion by

the medium access control layer (MAC), using a multi-channel

MAC (MMAC) protocol [2]–[7].

The design of MMAC protocols poses significant challenges.

Senders must employ low-overhead mechanisms for discov-

ering the resident channel of their respective destinations.

Moreover, parallel transmissions must be efficiently distributed

over all available channels to balance the traffic load and

alleviate contention. The latter is a complicated process due to

the multi-channel hidden terminal problem [3]. In this problem,

a sender that switches to a busy channel is unable to detect an

ongoing transmission if it is a hidden terminal to the transmitter.

Current solutions to the multi-channel hidden terminal problem

incur significant control overhead by requiring the use of in-

band or out-of-band control channels [2]–[5], or the availability

of multiple transceivers per device [6], [8], [9]. Finally, most

existing MMAC protocols fail to address the multi-channel

exposed terminal problem [10], whereby a sender switching to

a busy channel, but being an exposed terminal to a transmitter,

cannot proceed with a parallel non-interfering transmission.

978-1-4799-3360-0/14/$31.00 c©2014 IEEE

To improve the spectral efficiency of MMAC protocols, we

exploit recent advances in full-duplex (FD) communications

over a single channel [11]–[14]. In certain low-power wireless environments, sophisticated self interference suppression (SIS)

techniques allow for concurrent transmission and reception over

a single channel. This is achieved by suppressing a significant

portion of the self interference (up to 80 dB), using a com-

bination of antenna-based SIS [14], signal inversion [12], RF

and digital interference cancellation [13], [15]. The integration

of FD communications in the MMAC design provides unique

opportunities for reducing the control overhead and increasing

the spatial channel reuse. In this paper, we address the problem of improving the throughput and delay efficiency of MMAC protocols, when nodes can operate in FD mode.

Our Contributions–We design an MMAC protocol called FD-MMAC that enables distributed coordination of channel

access over orthogonal channels for devices using a single

transceiver. Compared with prior MMAC designs, the FD-

MMAC protocol provides the following attractive features.

• It eliminates in-band and out-of-band control signaling for combating the multi-channel hidden terminal problem,

discovering the resident channel of destinations, and per-

forming load balancing.

• It increases the spatial channel reuse by enabling the operation of multi-channel exposed terminals.

• It achieves load balancing and fairness autonomously.

Though security considerations are beyond the scope of the

present work, FD-MMAC is less vulnerable to denial-of-service

attacks launched against the control channel [16], [17], due to

the elimination of signaling on a dedicated control band. To

achieve its goals, FD-MMAC integrates an advanced suite of

PHY-layer techniques, including SIS, error vector magnitude

(EVM) and received power measurements, and signal correla-

tion techniques. We validate these PHY-layer techniques on an

NI USRP testbed. Further, we show via packet-level simulations

that FD-MMAC achieves significantly higher throughput and

lower delay compared with prior art. To the best of our

knowledge, this is the first work to propose an MMAC protocol

design that exploits the FD communication mode.

Paper Organization–In Section II, we motivate our problem by discussing the limitations of related work. The system model

is described in Section III. Section IV describes the FD carrier

sensing operation. In Section V, we address the multi-channel

hidden and exposed terminal problems. In Section VI, we

IEEE INFOCOM 2014 - IEEE Conference on Computer Communications

978-14799-3360-0/14/$31.00 ©2014 IEEE 2742

2

Fig. 1. The multi-channel hidden terminal problem.

present the operational details of FD-MMAC. We compare the

performance of FD-MMAC with existing MMAC designs in

Section VII and conclude in Section VIII.

II. MOTIVATION - RELATED WORK

MMAC protocols can be broadly categorized to three classes:

(a) split-phase [3], [5], [18], (b) dedicated control channel

(DCC) [6]–[10], and (c) rendezvous [2], [19]. In split-phase

MMACs, time is divided to alternating control and data phases.

During the control phase, all nodes converge to a default

channel to negotiate the channel assignment for the upcoming

data phase using a variant of the virtual carrier sensing mech-

anism [1]. During the data phase, nodes exchange data on the

assigned channels. In DCC MMACs, nodes are equipped with

two radios. One radio is always tuned to a DCC to perform

channel assignment and virtual carrier sensing. The second

radio switches between the remaining channels to perform

data transmissions. Finally, in rendezvous protocols, nodes

hop between channels using predefined hopping sequences.

These sequences are designed to enable the sender-destination

rendezvous within a fixed time period. We now motivate our

work by highlighting the limitations of existing MMACs.

The multi-channel hidden terminal problem: We first describe the multi-channel hidden terminal problem using the

topology of Fig. 1. Let nodes A and B reside on channel f1, while node C resides on f2. Topologically, C is a hidden terminal to A. Assume that A performs an RTS-CTS exchange over f1 (virtual carrier sensing enabled) before communicating packet PA to B. Let the transmission of PA start at time t0 and terminate at t1. Assume that C switches to f1 at t2 with t0 < t2 < t1. Because t2 > t0, node C will not overhear the CTSB. Moreover, because t2 < t1, the transmission of PA is ongoing when C switches to f1. At time t3 < t1, node C becomes active and causes a collision at B.

Split-phase MMACs avoid multi-channel hidden terminals by

performing channel negotiations on a default control channel.

Because all nodes reside on the default channel during the

control phase, the virtual carrier sensing mechanism prevents

hidden terminals. However, no data transmissions take place

during the control phase, thus decreasing the overall spectral

efficiency. The control phase can be considerably long under

high-contention conditions. Moreover, when a sender has pack-

ets for multiple destinations, it may switch channels during a

single data phase. In this case, a multi-channel hidden terminal

can avoid collisions only if it defers from transmission for a

period equal to the duration of the maximum transmission unit

plus an ACK. This delay decreases the spectral efficiency.

In DCC MMACs, virtual carrier sensing is performed over

the DCC. Because one radio is always tuned to this channel,

nodes are aware of all scheduled data transmissions. Hence,

multi-channel hidden terminals are avoided. However, the use

of one extra radio increases the device cost. Moreover, the

spectral efficiency is decreased by dedicating one channel for

signaling. The capacity of the control channel becomes the

performance bottleneck in high-contention scenarios. Finally,

from a security standpoint, the control channel constitutes a

single point of failure [16], [17]. Rendezvous protocols do not

address the multi-channel hidden terminal problem.

The multi-channel exposed terminal problem: Multi- channel exposed terminals lose transmission opportunities when

switching to a busy channel in the middle of a data trans-

mission. Referring to Fig. 1, assume that B transmits a data packet to A on f1 starting at t0. Node C switches to f1 at t2 with t0 < t2 < t1. Node C will sense the channel busy and defer from transmission, thus losing an opportunity to

operate in parallel with the B → A transmission. Prior MMAC protocols solve the exposed terminal problem using additional

radios and/or dedicated control channels [7], [10].

Destination discovery and load balancing: In a multi- channel setting, a destination must be discoverable by a can-

didate sender. Moreover, parallel communications must be

distributed over all channels to balance the traffic load and

alleviate contention. In DCC and split-phase MMAC proto-

cols, these two functions are performed by exchanging control

messages, thus decreasing the spectral efficiency. Rendezvous

protocols incur less overhead for destination discovery, since

a destination’s hopping sequence can be known a priory.

However, these protocols do not combat multi-channel hidden

terminals. Moreover, in some designs, an initial discovery

delay is incurred until the sender’s and destination’s hopping

sequences overlap [2]. In FD-MMAC, destination discovery and

load balancing are achieved without the exchange of control

information. Nodes independently switch to idle channels by

tracking the state of each channel.

III. SYSTEM MODEL

Network model: We consider a wireless network that op- erates over a set of orthogonal channels, denoted by F = {f1, f2, ..., fn}. For simplicity, we assume that all channels have the same bandwidth and propagation characteristics.

Nodes are equipped with a single radio transceiver and are

assumed to be time-synchronized to a common slotted sys-

tem. Time synchronization can be achieved using out-of-band

solutions such as GPS [20], or any of the readily available in-

band methods [21]. We note that time-slotted synchronization

is not a necessary FD-MMAC requirement. It is assumed here

to facilitate legacy operations used by FD-MMAC, such as

the slotted CSMA algorithm. However, FD-MMAC can also

operate in an asynchronous mode.

SIS and signal correlation: Nodes can operate in FD mode by applying a combination of analog and digital SIS

techniques [11]–[14]. In FD mode, a node can receive while

simultaneously transmitting over the same channel. Moreover,

IEEE INFOCOM 2014 - IEEE Conference on Computer Communications

2743

3

Fig. 2. Detecting a known bit pattern P when two packets collide using the signal correlation technique.

nodes can apply signal correlation techniques for detecting

the transmission of known bit patterns. These techniques are

common in frame detection, even in the presence of collisions

[15]. The concept of signal correlation is shown in Fig. 2.

Consider the concurrent reception of packets PA and PB at C. Node C is interested in detecting whether PB = P, where P is a known bit pattern. Let the sampled signal representing P be L samples long. Node C computes the signal correlation value between PA + PB + w and P (w denotes the noise component at the receiver) by aligning the L samples of P with the first L samples of PA + PB + w. It then shifts the alignment of P by one sample and recomputes the correlation until the end of PA + PB + w is reached. Formally, let x[i] denote the i

th

sample of P and y[j] the jth sample of the received signal. The correlation value at the jth sampled position of y[j] is:

C[j] = L∑

i=1

x∗[i]y[j + i], (1)

where x∗[i] is the complex conjugate of x[i]. The correlation value will peak when P is aligned with PB. Using this correlation method, node C can identify if P is transmitted, despite the concurrent transmission of PA. In practice, node C must compensate C[j] for the frequency offset of B. The frequency offset can be estimated in advance from prior packet

exchanges between B and C. A limitation of signal correlation is that the known bit pattern has to exhibit desirable cross-

correlation properties.

IV. FD CARRIER SENSING

The carrier sensing function can be extended to the receiver’s

collision domain when that receiver operates in FD mode [12],

[22]. We refer to this mechanism as FD carrier sensing. In FD-MMAC, we improve FD carrier sensing by integrating a

suite of PHY-layer techniques. Our techniques extend beyond

the estimation of the carrier state (idle or busy) and determine

a node’s operational state relative to an ongoing transmission.

The state information is used to create transmission opportu-

nities for exposed terminals, avoid collisions caused by hidden

terminals, and discover the resident channel of a destination.

Operation in FD mode: The FD carrier sensing mechanism is shown in Fig. 3. A sender A initiates the transmission of PA to B. Node B decodes the MAC header of PA and determines it is the destination. Node B transmits a beacon packet BCNB

Table 1: Region Classification Rules

BCN EV M < γEV M RSS < γRSS Region C1 No Yes Yes TO C2 No Yes No CO C3 No No - CO C4 Yes - - RO

Fig. 3. The three regions for a node C relative to a data transmission A → B.

while receiving PA by operating in FD mode. This mechanism was demonstrated in [22] for a single channel MAC. Node

A receives BCNB by also operating in FD mode. With the reception of BCNB, node A verifies that B is receiving PA and continues the transmission of PA. Lack of a BCN reply implies either that B is unavailable (B is at another channel or a hidden terminal to another transmission) or that the MAC

header of PA got corrupted. Node A uses the lack of BCNB as an early collision detection mechanism and aborts the further

transmission of PA.

Generally, a data packet P is expected to be much longer than a BCN packet. To account for this difference, BCN packets are

transmitted back-to-back until the reception of P is completed. The reception ending time te is known to the destination based on the network allocation vector (NAV) included in P ’s MAC header. The BCN contains the destination’s id, the time slot

tACK at which the ACK transmission is to be completed, and a CRC code. If the reception of P is successful, the destination replies with an acknowledgement (ACK).

Operation State Classification: To combat multi-channel hidden terminals and enable multi-channel exposed terminals,

nodes that sense channel activity perform region classification to determine their operation state. We divide the collision

domains of A and B to the three regions shown in Fig. 3: (a) the receiver-only (RO) region, (b) the collision region (CO),

and (c) the transmitter-only (TO) region. Referring to Fig. 3, a

node C can determine its region using the following rules.

1) If C can decode BCNB, it infers that it is in the RO region (hidden terminal).

2) if C cannot decode the received signal due to the collision of PA with BCNB, it infers it is in the CO region.

3) If C can decode PA, it infers that it is in the TO region

IEEE INFOCOM 2014 - IEEE Conference on Computer Communications

2744

4

(exposed terminal).

If C concludes that it is located in the CO/RO regions, it defers from transmission to prevent a collision at B. Otherwise, it explores transmission opportunities as an exposed terminal.

Practical Issues: Several practical issues complicate the proposed region classification rules. First, when C is in the TO region (position C1 in Fig. 3), it cannot verify the correct decoding of PA until PA’s transmission is completed and the CRC code is checked. Similarly, if C switches to a busy channel in the middle of PA’s transmission, the CRC code cannot be checked. Both these scenarios eliminate exposed terminal

transmission opportunities. To evaluate the decodability of PA before the reception of the CRC code, node C computes the error vector magnitude (EV M) on the received symbols. The RMS EV M value (dB) is given by [23]:

EV MRMS(dB) = 20 log

(√ 1 n

∑n k=1 |stk − srk|2

1 M

∑M i=1 |si|2

) , (2)

where stk is the k th transmitted symbol, srk is the k

th received

symbol, n is the window size (in symbols) over which the EV M is computed, si is the i

th constellation symbol, and M is the number of constellation symbols. The EV M serves as a measure of the signal quality and is strongly correlated to the

bit error rate [23]. It characterizes the signal distortion due to

impairments of the wireless channel and undesired interference.

Note that the stks corresponding to the received s r ks are

not known to C for arbitrary packets. To compute the EV M using formula (2), node C selects those stks in the constellation diagram that are closest to the received srks. This is because when a packet is correctly decoded, it is expected that the

received symbols are closest to the actual transmitted symbols

(hence, the correct decoding). On the other hand, in a collision

scenario, the received symbols have a large distance from the

ideal symbols, yielding a larger EV M. In our classification, we compute the EV M over the duration

of two BCN packets. This is to differentiate between the TO

and the RO regions, where nodes are expected to have a lower

EV M compared with the CO region. If a node C is located in the RO region, it is likely to decode at least one BCN packet

within two BCN packet durations (recall that C can switch to a busy channel at any time). Otherwise, if C is in the TO region, it will not decode a BCN packet, but will have a low

EV M value. For the EV M classification rule, the EV M at C is compared with a threshold γEV M .

Low EV M values and undecodability of a BCN packet can also be recorded due to the capture effect [24], when C is in the CO region but very close to A (position C2 in Fig. 3). In this case, a potential transmission by C will cause a collision at B. To prevent this collision, we incorporate received signal strength (RSS) measurements. If the RSS measurement at C is beyond a threshold γRSS, node C concludes that it is in the CO region, despite having a low EV M value. Finally, if C is in the CO region, but can decode the BCN due to its proximity

to B, for all practical purposes we allow C to infer that it is in

(a)

(b) Fig. 4. (a) Combating the multi-channel hidden terminal problem, (b) exposed terminal operation. Transmission C → D occurs in parallel with transmission A → B on the same channel.

the RO region. This is because for both the CO and RO regions,

C will defer from transmission. The region classification rules used by FD-MMAC are summarized in Table 1. In Section

VII, we perform testbed experiments for determining γEV M and γRSS based on measurements at locations C1 . . . C4.

V. COMBATING HIDDEN AND EXPOSED TERMINALS

FD carrier sensing eliminates the multi-channel hidden ter-

minal problem. We illustrate this in Fig. 4(a) for the topology

of Fig. 3, in which C is a hidden terminal to A. Node A transmits PA to B over f1 at time t0. Node B decodes the PHY and MAC headers and infers that it is the destination.

Node B replies with BCNB that is repeated for the duration of PA, which terminates at t1. Node C switches to f1 at t2 with t0 < t2 < t1. First, C senses f1 to be busy due to the BCNB transmissions. Second, C attempts to decode a BCN for two BCN durations. By decoding BCNB, node C infers it is in the RO region and defers from transmission. If BCNB cannot be

decoded, the EV M is expected to be high and hence, C will infer it is in the CO region and defer from transmission.

Early collision detection: A collision due to hidden termi- nals is still possible during the transmission of the PHY and

MAC headers of P . Under a collision scenario, the destination will be unable to decode the MAC header and will not transmit

a BCN packet. We use the absence of a BCN packet as an early

collision detection mechanism. If the sender does not receive

a BCN reply, it assumes that the attempted data transmission

has collided or the destination is unavailable. The sender aborts

further transmission of P and attempts retransmission without waiting for the expiration of the ACK timer.

Enabling Exposed Terminal Transmissions: An exposed terminal node C located in the TO region of an ongoing transmission A → B will attempt to communicate PC to a candidate destination D. If D can decode the MAC header of PC , it will respond with BCND packets by operating in FD mode. Node C will continue the transmission of PC if it detects BCND, and will abort otherwise. The destination D will not be able to respond with BCND if one of the following

occurs: (a) D is in the collision domain of another transmission and hence, cannot decode the MAC header of PC or, (b) D

IEEE INFOCOM 2014 - IEEE Conference on Computer Communications

2745

5

(a) (b) (c)

Fig. 5. (a) The state diagram of an FD-MMAC destination, (b) the CST table for node E, and (c) the state diagram of an FD-MMAC sender.

resides on another channel. The exposed terminal operation for

transmissions A → B and C → D is shown in Fig. 4(b). Receiving BCN/ACK packets in the presence of exposed

terminals: Exposed terminal transmissions create two funda- mental problems. First, nodes A and C cannot decode BCNB and BCND, respectively, due to the interference they cause to each other. Similarly, nodes A and C cannot decode ACKB and ACKD, respectively, due to the interfering transmissions of PC and PA. To enable the concurrent operation of A → B and C → D, we use the signal correlation technique for detecting known bit patterns [15].

Node C applies the signal correlation technique to detect BCND and ACKD when PA is concurrently transmitted. Sim- ilarly, node A applies the signal correlation technique to detect BCNB and ACKB when PC is concurrently transmitted. Note that a node is aware of the exact composition of the BCN

(ACK) packet and the approximate time that a BCN (ACK) is

expected. Hence, it can limit the signal correlation within only

a few sample shifts. One limitation here is that the BCN (ACK)

has to exhibit desirable cross-correlation properties. Therefore,

the BCN (ACK) is hashed (except the PHY header) with a

uniform hash function to produce a random output.

VI. THE FD-MMAC PROTOCOL

FD-MMAC is a contention-based, time-slotted protocol

based on CSMA/CA. To improve its spectral efficiency, FD-

MMAC eliminates the message overhead related to virtual

carrier sensing, destination discovery, and channel negotiation.

The destination and sender state diagrams are shown in Fig. 5.

A. Destination Operation When a node’s transmission queue is empty, it operates as a

destination. A destination selects a resident channel such that it

can be discovered by candidate senders. Referring to the state

diagram of Fig. 5(a), a destination operates as follows. Sense state: In the “Sense” state, the destination contin-

uously senses the resident channel. If the resident channel

becomes busy, the destination transitions to the “Decode” state. Decode state: In the “Decode” state, the destination attempts

to decode the received signal. It transitions to the “FD” state

if the MAC header is successfully decoded, the receiving node

is the intended destination, and it is available for reception.

Otherwise, it transitions to the “Switch” state. FD state: In the “FD” state, the destination operates in

FD mode. Based on the MAC header of P , the destination

determines the tACK and the number of BCN packets that need to be transmitted. Then, it transmits BCN packets until

the reception of P is completed. The destination checks the CRC code of P . If P is successfully received, it transitions to the “ACK” state. Otherwise, it returns to the “Sense” state.

ACK state: After a successful packet reception, the destina- tion replies with an ACK and returns to the “Sense” state.

Switch state: In the “Switch” state, the destination au- tonomously determines its resident channel. This decision is

based on a channel state table (CST) that records the expected time that each channel becomes idle (idle time). The CST is updated in the following way:

1) If the resident channel fi is idle, set the idle time for fi to the current slot tcurr.

2) If the resident channel fi is busy and the destination is the RO region (BCN is decodable), set the idle time for

fi to tACK (contained in the BCN). 3) If the resident channel fi is busy and the destination is in

the CO/TO region (BCN not decodable), set the idle time

for fi to tcurr +TMT U, where TMT U is the transmission duration of the maximum transmission unit (MTU) packet

plus the corresponding ACK.

After the CST update, the destination switches to the channel

with the earliest idle time. In the case of ties, the current

resident channel is preferred to avoid unnecessary channel

switches. Otherwise, ties are broken arbitrarily. The proposed

switching mechanism achieves several desirable properties.

First, a destination waits for a candidate sender on the channel

with the earliest idle time. This facilitates destination discovery,

as the sender will also switch to the channel with the earliest

idle time. Second, load balancing is indirectly achieved, as idle

destinations avoid busy channels. Both properties are achieved

without exchanging control messages.

As an example, consider the topology of Fig. 5(b). Assume

that destination E resides on f1. Initially, E sets the idle time for all channels to tcurr. When the A→B transmission occupies f1, node E decodes BCNB because it is a hidden terminal to A. Node E updates the idle time for f1 to tACK and switches to f2, because f2 has the earliest idle time (ties are broken arbitrarily). Assume that transmission C→D is ongoing on f2 when E switches to f2. Node E cannot decode BCND since it is in the TO region. Node E uses the the worst-case estimate for the idle time of f2 and sets the idle time to tcurr + TMT U. It then switches to f3 which is currently idle.

IEEE INFOCOM 2014 - IEEE Conference on Computer Communications

2746

6

(a) (b) Fig. 6. Two operational examples of FD-MMAC.

B. Sender Operation

In FD-MMAC, we adapt the CSMA backoff mechanism

to the multi-channel environment to reduce packet delay and

achieve fairness. Referring to the state diagram of Fig. 5(c), a

sender operates as follows.

Sense state: In the “Sense” state, the sender senses its resident channel fi. If fi is idle, it transitions to the “Backoff” state. If fi is busy, it classifies its operation state using the region classification rules of Section IV. If the sender is in the

TO region (exposed terminal), it transitions to the “Backoff”

state. Otherwise, it transitions to the “Switch” state.

Backoff state: In the “Backoff” state, the sender selects a backoff value β for a packet P , by using the following rules:

1) In the first transition to the “Backoff” state for P , the sender draws β uniformly from [0, cw0], where cw0 is the minimum contention window.

2) In any following transition from the “Sense” state, the

sender retains the current β value (backoff is resumed from the current value).

3) In a transition from the “Wait ACK” state, the sender

doubles the contention window and draws β uniformly (the contention window is capped at cwmax).

In the “Backoff” state, the sender decrements β by one unit with every “idle” slot. Here, a slot is assumed to be idle if: (a)

no channel activity is detected, or (b) the channel is busy but the

sender is in the TO region. When β = 0, the sender transitions to the “Transmit” state. If the channel becomes busy before

β = 0 (and the sender is not in the TO region), the sender transitions to the “Switch” state and freezes β.

Transmit state: In the “Transmit” state, the sender initiates the transmission of P . If the destination responds with a BCN packet, the sender continues the transmission of P . With the completion of P ’s transmission, the sender transitions to the ‘Wait ACK” state. If a BCN is not detected, the sender aborts

the transmission of P and transitions to the “Switch” state. Wait ACK state: With the completion of P ’s transmission,

the sender waits for an ACK by the destination. The sender

transitions to the “Backoff” state if an ACK is not received

by the expiration of the ACK timer, without transitioning to

the “Switch” state. This is because the sender is aware that the

destination resides on the current channel due to the reception

of the BCN during the “Transmit” state. If the ACK reception

is successful, the sender transitions to the “Switch” state.

Switch state: In the “Switch” state, the sender performs two operations. First, it updates the CST information and second, it

decides on the next channel using the same switching rules as

the destination. The CST is updated using the following rules:

1) If the sender is in the RO region of a transmission on fi (BCN is decodable), it sets the idle time of fi to tACK

2) If the sender is in the CO/TO region of a transmission

on fi (BCN is not decodable), it sets the idle time of fi to tcurr + TMT U.

3) If a sender transmitted a packet P on fi, but did not receive a BCN response it sets the idle time of fi to tcurr + TMT U. This update leads to a channel switch to continue the destination discovery process.

Once the CST has been updated, the sender switches to the

channel with the earliest idle time. Ties are broken arbitrarily.

C. FD-MMAC Operational examples

In Fig. 6, we present two operational examples for FD-

MMAC. In the example of Fig. 6(a), node C has a packet for D while being in the TO region of the A → B transmission. Node C determines that it is in the TO region and can operate as an exposed terminal. Node C transitions to the “Backoff” state, selects β, and starts the backoff countdown. When β = 0, node C transitions to the “Transmit” state. Node C transmits PC and receives BCND from D. Node C detects BCND using the signal correlation technique and continues the transmission

of PC . Upon termination of the PA transmission, B transmits ACKB which is detected at A using the signal correlation technique. Upon termination of the PC transmission, D replies with ACKD which is decodable at C.

In the example of Fig. 6(b), node A communicates with B at f1. Node D switches from f1 to f2 to be available for packet reception. Node C, who resides on f1, has a packet PC for D. Initially, D is in the “Sense” state. Since f1 is idle from C’s perspective, C transitions to the “Backoff” state and selects a β. When β = 0, node C transitions to the “Transmit” state and starts the transmission of PC . Because D resides on f2, node C does not receive BCND. Node C transitions to the “Switch” state and updates the idle time for f1 to tcurr + TMT U. Based on the CST entries, C switches to f2 which has the earliest idle time and transitions to the ”Sense” state. Since f2 is idle, C transitions to the ”Backoff” state for a second time and retains

β = 0. It then completes the communication with D.

IEEE INFOCOM 2014 - IEEE Conference on Computer Communications

2747

7

−80 −60 −40 −20 0 20 0

0.2

0.4

0.6

0.8

1

EV M (dB)

P r

TO/RO Capture effect CO

γE V M = -18 dB

−15 −10 −5 0 5 10 15 −4

−2

0

2

4

6

R S S ( d B m )

Distance(ft)

BA

γRSS = 1 dBm

0 500 1000 1500 2000 2500 3000 3500 4000 0

0.002

0.004

0.006

0.008

0.01

0.012

Sample position in received signal

C o r r e la t io n ( n o r m )

(a) (b) (c) Fig. 7. (a) The EV M CDF at the RO, CO, and TO regions, (b) average RSS at different positions, (c) normalized correlation values for 10 BCN packets.

Fig. 8. The network topology used in the simulation experiments.

VII. TESTBED EXPERIMENTS AND SIMULATIONS

In this section, we experimentally verify the PHY-layer

techniques used by FD-MMAC and compare its performance

with prior art via packet-level simulations.

A. Experimental Evaluation

Testbed: We performed our experiments on NI USRPs devices [25], over the 2.4 GHz band. The signal processing

blocks were implemented in Labview [25]. Transmissions were

modulated using the Quadrature Phase Shift Keying (QPSK)

scheme at a transmission rate of 2Mbps. The radios applied

phase/frequency offset correction and time synchronization

using 88-bit preamble sequences.

Operation State Classification: To validate the operation state classification rules presented in Section IV, we replicated

the topology of Fig. 3. Nodes A and B were placed 7ft apart and transmitted concurrently. Node A transmitted 100 P packets carrying a 500-bit payload, while node B transmitted 500 BCN packets with a 50-bit payload. We placed node C at positions C1, . . . , C4 of Fig. 3 and measured the EV M, RSS, and the decodability of BCNs.

Fig. 7(a) shows the CDF of the EV M for the RO/TO region (positions C1 and C4), the CO region (position C3), and position C2 in the CO region. The RO and TO curves were averaged since they yielded very similar values. We observe that

the EV M in the CO region (position C3) is significantly higher compared with all other locations due to the collision of P with the BCN. The difference allows us to select the threshold

γEV M for the EV M classification rule. In our experiments, we set γEV M = −18 dB to achieve a false positive rate of 2% (EV M < γEV M when in the CO region) and a false negative rate of 4% (EV M ≥ γEV M when in the TO/RO region).

For position C2, EV M < γEV M due to the capture effect [24]. To avoid the classification of a node located at C2 as an exposed terminal, we use the mean RSS value. Fig. 7(b) shows the mean RSS value for different receiver locations, averaged

over the experiment duration. Nodes A and B were placed at positions 0ft and 7ft, respectively. For the RSS classification rule, we set γRSS to 1dBm. We observe that for location C2 (within 2ft from A), C has an RSS value significantly higher than γRSS, and therefore infers that it is located in the CO region, despite having an EV M < γEV M . Also, for exposed terminal locations (more than 5ft from A), the EV M and RSS are below γEV M and γRSS, respectively.

Finally, we measured the fraction of BCN packets that can

be decoded by C over ten repeated experiments (500 BCN packets each run). We recorded zero decodable BCN packets

at locations C1, C2, and C3, while 100% of the BCN packets were recovered at position C4. We also placed C in the vicinity of B but within the CO. For this position, C was able to decode a large fraction of BCN packets due to the capture effect

and falsely assume it is in the RO region. However, this error

does not impact the correct FD-MMAC operation because, for

all practical purposes, a node in the RO region defers from

transmission similar to a node in the CO region.

Signal Correlation: We experimentally evaluated the signal correlation technique for the exposed terminal topology of Fig.

4(b). Node A transmitted 500-bit long data packets contin- uously while node D transmitted 50-bit long BCN packets. Node C applied the signal correlation method to detect BCND packets. Fig. 7(c) shows the normalized correlation [25] for a

snapshot of ten BCN packets, when C is placed between A and D, at a 7ft distance from each. The correlation peaks correspond to the BCN transmissions and can be clearly distinguished.

In our experiments, we set the detection threshold to 0.005.

We placed C in three discrete positions between A and D to replicate the exposed terminal topology and measured the

percentage of BCND packets that can be detected by correlating

the received signal with the known BCN pattern (preamble +

payload). Node D transmitted 1,000 BCN packets. The results are shown in Table 2. Distances are measured from node D.

Table 2: Fraction of Detected BCN Packets

Distance from D 3 ft 5 ft 7 ft Percentage 100% 99% 94%

IEEE INFOCOM 2014 - IEEE Conference on Computer Communications

2748

8

10 1

10 2

10 30

1

2

3

4

λ (packets/sec)

T (M

b p s)

FD−MMAC, 3 flows SP−MMAC, 3 flows FD−MMAC, 6 flows SP−MMAC, 6 flows

10 1

10 2

10 30

1

2

3

4

λ (packets/sec)

T (M

b p s)

FD−MMAC, 9 flows SP−MMAC, 9 flows FD−MMAC, 12 flows SP−MMAC, 12 flows

10 1

10 2

10 30

1

2

3

4

λ (packets/sec)

T (M

b p s)

DCC MMAC, 3 flows DCC MMAC, 6 flows DCC MMAC, 9 flows DCC MMAC, 12 flows

10 1

10 2

10 30

0.5

1

1.5

λ (packets/sec)

T (M

b p s)

FD−MMAC, 3 flows SP−MMAC, 3 flows FD−MMAC, 6 flows SP−MMAC, 6 flows

(a) (b) (c) (d)

10 1

10 2

10 30

0.1

0.2

0.3

0.4

λ (packets/sec)

T (M

b p s)

FD−MMAC, 9 flows SP−MMAC, 9 flows FD−MMAC, 12 flows SP−MMAC, 12 flows

10 1

10 2

10 30

1

2

3

4

5

λ (packets/sec)

T (M

b p s)

FD−MMAC SP−MMAC DCC MMAC FD−MMAC, 95% detection

10 1

10 2

10 30

1

2

3

4

5

λ (packets/sec)

T (M

b p s)

FD−MMAC SP−MMAC DCC MMAC FD−MMAC, 95% detection

3 6 9 12 0

500

1000

1500

2000

Number of competing flows

A v e ra g e D e la y (m

s)

FD−MMAC SP−MMAC DCC MMAC

(e) (f) (g) (h)

Fig. 9. (a),(b),(c) Aggregate T of FD-MMAC, SP-MMAC, and DCC MMAC when 3, 6, 9, and 12 flows are within same collision domain, (d),(e) per-flow average T for FD-MMAC and SP-MMAC when 3, 6, 9, and 12 flows are within same collision domain, (f) aggregate T in the presence of an exposed terminal, (g) aggregate T in the presence of one exposed and one hidden terminal, (h) average delay for transmitting a batch of 100 data packets.

Table 2 shows that a node in the collision domain of two

transmitters can reliably detect a packet with known pseudo-

random pattern using the signal correlation.

B. Simulated Experiments

Simulation Setup: We performed packet-level simula- tions using OPNETTM [26]. In our setup, multiple sender- destination pairs (flows) were organized in the topology of Fig.

8 and shared three orthogonal channels with 2Mbps capacity.

For each sender, the arrival process at the MAC layer followed

the Poisson distribution with parameter λ packets per second. Each packet was 512 bytes long. The channel switching delay

was set to 20 μsec. Simulations were run for 40 sec and results were averaged over 20 simulation runs.

Throughput (T ): In the first set of experiments, we com- pared the FD-MMAC throughput with the throughput of the

split-phase MMAC (SP-MMAC) in [3] and of the DCC MMAC

in [6]. The control and data phase of SP-MMAC were set

to 20ms and 80ms, respectively [3]. Fig. 9(a), 9(b), and 9(c)

compare the aggregate throughput for a varying number of

contending flows, co-located in the same collision domain

(senders SE and SH were idle). For low λ’s, all protocols achieve similar throughput due to low contention. However, in

saturation conditions, FD-MMAC achieves significantly higher

aggregate throughput compared with the other protocols, due

to the elimination of signaling for channel negotiation and

virtual carrier sensing. Fig. 9(d) and 9(e) show the average per-

flow throughput of FD-MMAC and SP-MMAC. FD-MMAC

significantly outperforms SP-MMAC in saturation conditions.

In the second set of experiments, we placed five flows

S1 → D1,. . . ,S5 → D5 in the same collision domain, while SE operated as an exposed terminal to S1, . . . , S5. For FD-

MMAC, we considered two scenarios. In the first scenario,

BCN and ACK packets were perfectly detected using the signal

correlation technique. In the second scenario, 5% of BCNs

and 5% of ACKs were undetectable by the intended recipients.

From Fig. 9(f), we observe that in saturation conditions, FD-

MMAC achieves an aggregate throughput that is 65% higher

compared with SP-MMAC and 75% higher compared with

DCC MMAC under ideal operating conditions. The throughput

improvement drops to 49% and 58%, respectively, when 5% of

BCN and ACK packets are assumed lost.

The superior performance of FD-MMAC is due to the

parallel operation of SE with any of the S1, . . . , S5. In fact, the individual throughput of SE was 51% higher than the through- put of S1, . . . , S5 (1.12 Mbps for SE vs. 0.74Mbps for each S1, . . . , S5) because SE did not contend with any other sender. On the other hand, for SP-MMAC and DCC MMAC, SE operated in the same collision domain with S1, . . . , S5 and its throughput dropped to 0.51Mbps and 0.68Mbps, respectively.

Further, we evaluated the concurrent existence of exposed and

hidden terminals. Five flows were placed in the same collision

domain, SE operated as an exposed terminal and SH operated as a hidden terminal. Fig. 9(g) shows that FD-MMAC achieves

43% and 38% higher throughput in saturation conditions com-

pared with SP-MMAC and DCC MMAC, respectively.

Delay: In the third set of experiments, we evaluated the packet delay for bursty packet arrivals. We loaded the trans-

mission queue of each sender with 100 packets and measured

the delay until all 100 packets were delivered to their respective

destinations. All flows were within same collision domain. Fig.

9(h) shows the average delay as a function of the number of

competing flows. We observe that FD-MMAC reduces the delay

due to the elimination of the control message exchange before

IEEE INFOCOM 2014 - IEEE Conference on Computer Communications

2749

9

packet transmissions. The delay increases almost linearly with

the number of contending flows for all protocols, because the

available channels are shared by more flows in a fair manner.

Fairness and Load Balancing: We also examined the fairness and load balancing properties of FD-MMAC under

different traffic load conditions. To evaluate fairness, we use

the Raj Jain’s Fairness Index (FI):

FI = ( ∑n

i=1 Ti) 2

n × ∑ni=1(Ti)2 (3) where Ti is the throughput of the i

th flow and n is the total number of flows. The FI varied from 0.97 (for a topology with an exposed terminal present) to 0.999 (for a topology with six

flows in the same collision domain), indicating that FD-MMAC

achieves fair distribution of resources among competing flows.

The FI is slightly smaller than one in the presence of an exposed terminal flow, because the exposed terminal node does

not contend with other senders. We also evaluated the traffic

load carried by each channel by computing the Load Balancing Index (LBI) in saturation conditions:

LBI = ( ∑3

i=1 Tfi) 2

3 × ∑3i=1(Tfi)2 , (4) where Tfi is the aggregate throughput on channel fi. The LBI value varied from 0.904 (for a topology with an exposed terminal) to 1 (for a topology with only three flows). The

LBI value is lower than 1 under an exposed terminal topology because the same channel is concurrently occupied by two flows

during an exposed terminal operation.

VIII. CONCLUSION

We proposed FD-MMAC, a distributed MMAC protocol that

exploits FD communications to coordinate channel access at

low control overhead. FD-MMAC eliminates control signaling

for combating the multi-channel hidden terminal problem,

discovering the resident channel of destinations, and performing

load-balancing. Further, it increases the spatial channel reuse by

enabling the operation of multi-channel exposed terminals. The

FD-MMAC properties are achieved by utilizing an advanced

suite of PHY-layer techniques, including SIS, EVM and RSS

measurements, and signal correlation techniques. These tech-

niques were experimentally validated on the NI USRP testbed

and via simulations.

ACKNOWLEDGMENTS

This research was supported in part by the NSF under grants

CNS-0844111 and CNS-1016943 and ARO grant W911NF-13-

1-0302. Any opinions, findings, conclusions, or recommenda-

tions expressed in this paper are those of the author(s) and do

not necessarily reflect the views of the NSF.

REFERENCES

[1] IEEE 802.11 Working Group. Wireless LAN medium access control (MAC) and physical layer (PHY) specifications. IEEE 802.11 LAN Standards 2007, 2007.

[2] P. Bahl, R. Chandra, and J. Dunagan. SSCH: slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad-hoc wireless networks. In Proc. of the MOBICOM Conference, pages 216–230, 2004.

[3] J. So and N.H. Vaidya. Multi-channel MAC for ad hoc networks: handling multi-channel hidden terminals using a single transceiver. In Proc. of the MOBIHOC Conference, pages 222–233, 2004.

[4] T. Luo, M. Motani, and V. Srinivasan. Cooperative asynchronous multichannel MAC: Design, analysis, and implementation. IEEE Trans. on Mobile Computing, 8(3):338–352, 2009.

[5] J. Zhang, G. Zhou, C. Huang, S.H. Son, and J.A. Stankovic. TMMAC: An energy efficient multi-channel mac protocol for ad hoc networks. In Proc. of the ICC Conference, pages 3554–3561, 2007.

[6] S. L. Wu and J. Y. Yang. A novel channel assignment scheme for improving channel reuse efficiency in multi-channel ad hoc wireless networks. Computer Communications, 30(17):3416–3424, 2007.

[7] K. H. Almotairi and X. S. Shen. Multichannel medium access control for ad hoc wireless networks. Wireless Communications and Mobile Computing, pages 1–14, 2011.

[8] N. Jain, S.R. Das, and A. Nasipuri. A multichannel CSMA MAC protocol with receiver-based channel selection for multihop wireless networks. In Proc. of the ICCCN Conference, pages 432–439, 2001.

[9] T. Shu, S. Cui, and M. Krunz. Medium access control for multi- channel parallel transmission in cognitive radio networks. In Proc. of the Globecomm Conference, pages 1–5, 2006.

[10] X. Xing, K Liu, and H. Lu. A multichannel mac protocol to solve exposed terminal problem in multihop wireless networks. In Proc. of the CCNC Conference, pages 1–2, 2009.

[11] A. Sahai, G. Patel, and A. Sabharwal. Pushing the limits of full-duplex: Design and real-time implementation. Technical Report TREE1104, Rice University, February 2011.

[12] M. Jain, J. Choi, T. Kim, D. Bharadia, S. Seth, K. Srinivasan, P. Levis, S. Katti, and P. Sinha. Practical, real-time, full duplex wireless. In Proc. of the MobiCom Conference, pages 301–312, 2011.

[13] B. Radunovic, D. Gunawardena, P. Key, A. Proutiere, N. Singh, V. Balan, and G. Dejean. Rethinking indoor wireless mesh design: Low power, low frequency, full-duplex. In IEEE Workshop on Wireless Mesh Networks, pages 1–6, 2010.

[14] J. Choi, M. Jain, K. Srinivasan, P. Levis, and S. Katti. Achieving single channel, full duplex wireless communication. In Proc. of the MobiCom Conference, pages 1–12, 2010.

[15] S. Gollakota and D. Katabi. ZigZag decoding: combating hidden termi- nals in wireless networks. In Proc. of the ACM SIGCOMM Conference, pages 159–170, 2008.

[16] S. Liu, L. Lazos, and M. Krunz. Thwarting control-channel jamming attacks from inside jammers. IEEE Trans. on Mobile Computing, 11(9):1545–1558, 2012.

[17] A. Proano and L. Lazos. Selective jamming attacks in wireless networks. In Proc. of the ICC Conference, pages 1–6, 2010.

[18] J. Chen, S.T. Sheu, and C.A. Yang. A new multichannel access protocol for IEEE 802.11 ad hoc wireless LANs. In Proc. of the PIMRC Conference, volume 3, pages 2291–2296, 2003.

[19] W. So, J. Walrand, and J. Mo. McMAC: a parallel rendezvous multi- channel MAC protocol. In Proc. of the WCNC Conference, pages 334– 339, 2007.

[20] A. Gupta, X. Lin, and R. Srikant. Low-complexity distributed scheduling algorithms for wireless networks. IEEE/ACM Trans. on Networking (TON), 17(6):1846–1859, 2009.

[21] O. Simeone, U. Spagnolini, Y. Bar-Ness, and S. Strogatz. Distributed synchronization in wireless networks. IEEE Signal Processing Magazine, 25(5):81 –97, 2008.

[22] N. Singh, D. Gunawardena, A. Proutiere, B. Radunovic, H. Balan, and P. Key. Efficient and fair MAC for wireless networks with self- interference cancellation. In In Proc. of the WiOpt Symposium, pages 94–101, 2011.

[23] R. A. Shafik, S. Rahman, and R. Islam. On the extended relationships among EVM, BER and SNR as performance metrics. In Proc. of the ICECE Conference, pages 408–411, 2006.

[24] J. Lee, W. Kim, S. Lee, D. Jo, J. Ryu, T. Kwon, and Y. Choi. An experimental study on the capture effect in 802.11a networks. In Proc. of ACM WiNTECH Conference, pages 19–26, 2007.

[25] NI. National instruments. http://www.ni.com/usrp/, 2013. [26] OPNET. OPNET technologies inc. http://www.opnet.com, 2009.

IEEE INFOCOM 2014 - IEEE Conference on Computer Communications

2750