1. DOF: A Local Wireless Information Plane [pdf]

Steven Hong , Sachin Katti

DOF Presentation at SIGCOMM 2011

Historically, unlicensed band co-existence has been managed "socially". Different radios would expect to operate in different bands and given the low density of radios in an area, the likelihood of stepping on each other's toes was low.

Today, we all carry around devices (such as our phones), which have multiple radios on them, and we each carry many such devices. Given the increasing number of protocols and the increasing density of radios around us, the assumption that our devices will always be able to find non-overlapping bands of spectrum is becoming more and more tenuous. How should we design future systems such that they will be able to maximize their own throughput while causing minimal harm to coexisting legacy radios?

Let's say we want to design a smart radio protocol which can coexist peacefully with the different wireless protocols which might operate within a home, what information will it need?

1. Radio Type - The first thing it would require is the knowledge of what protocols are operating in the local vicinity. For example, if the coexisting protocol is WiFi, it would be ok to interfere a bit and compete with it for spectrum. But if it's a sensitive medical sensor, such as a heart monitor, any packet drops could be potentially life threatening and our system would want to ensure that it does not interfere.

2. Spectrum Occupancy - But it is not sufficient to simply know which protocols exist, our smart radio must also be aware of which bands are occupied by which protocols so that it can correctly coexist with each neighboring radio in different bands.

3. Spatial Occupancy - Lastly, if our system were equipped with multiple antennas, a third piece of information that would be useful is the spatial locations of each neighboring protocol. For example if the neighboring protocol was a microwave signal, knowing which angles the microwave signal was arriving at would enable the smart radio to steer its transmission away from the interference caused by the microwave
We believe that this ability to detect what unlicensed radios are operating in a neighborhood, their spectrum occupancies and the spatial directions their signals are traversing is a fundamental primitive needed by future wireless systems. For example, smart and agile radios could use it to detect what spectral resources are unused, and exploit them to provide high throughput. They could detect what spatial directions are unoccupied, and directionally steer their signals to further increase capacity. They could also use the primitive to be gentle when needed, if a low power medical wireless sensor is operating in the neighborhood, the smart radio could detect it and take extra measures to avoid causing interference to the sensor, lest some critical communication is impaired. Similarly, network administrators can use such a primitive to manage their "airspace", improve channel allocation and diagnose performance problems. Such detectors could also be used to compute what spatial directions signals arrive at for wireless network security. Thus, a large and growing number of applications could benefit from such a primitive.

At SIGCOMM'11, we presented Degrees Of Freedom (DOF), a single framework that accurately detects what radios exist in a neighborhood, what parts of the spectrum they occupy, and their angles of arrival (AoA) at the detector. We believe this to be a first. DOF is robust and works accurately (around 90% accuracy) in a large SNR range (0 to 30dB) as well as in the presence of multiple interfering signals. DOF is passive and does not impose any measurement overhead, it can operate even when the detecting radio is being used for other communication. Finally, DOF is efficient to implement, it builds on top of commonly available FFT modules and requires modest extra resources ( 30% more computation compared to a standard FFT).

The key insight behind DOF is the observation that for most wireless protocols, there are hidden repeating patterns that are unique and necessary for their operation. For example, Wifi uses a repeating cyclic prefix to avoid intersymbol interference between consecutive OFDM symbols. A Zigbee radio has a repeating pulse which it uses for QPSK data transmission, Bluetooth has a Gaussian pulse on which it modulates data bits using FSK that is repeating with a different frequency and so on. DOF exploits the existence of these patterns to create unique signatures for each signal type. Further, DOF shows that the same signatures can also be exploited to determine the spectrum occupied and the AoA of that signal type.
Algorithmically, DOF extracts feature vectors using the following key idea: if a signal has a repeating hidden pattern, then a delayed version of the signal correlated with the original signal will show peaks at specific delay intervals. These intervals form a signature for each signal and can be used to extract feature vectors. We build on prior work [9, 19] in cyclostationary signal analysis to design an efficient feature extraction technique based on standard FFT operations. However, DOF's key contribution over prior work in cyclostationary analysis is to show that the extracted feature vector encodes information about the component signal types, what spectrum they occupy, as well as what AoAs they arrive at the detecting radio. DOF designs a novel SVM decision tree to classify component signal types, and new algorithms to estimate their spectrum occupancies as well as AoAs from the feature vector.

Implementation and Summary of Results: We implement DOF using the fftw library and GnuRadio software on a wideband radio that is capable of operating over the entire 100 MHz ISM band and has 4 MIMO antennas. We evaluate DOF using testbed experiments in an indoor office environment and compare it to three prior approaches, RFDump [16] for signal type, Jello [28] for spectrum occupancy, and SecureAngle [27] for AoA estimation (the best known implemented systems for each component respectively). We find that:

1. DOF is accurate and robust at all SNRs - it classifies co-existing radio types with greater than 85% accuracy even at SNRs as low as 0dB. On the other hand, RFDump is at most 60% accurate at SNRs lower than 8dB.

2. DOF is robust to interference - it achieves more than 82% accuracy in detecting component signal types even when there are three overlapping and interfering signals. The compared approach RFDump cannot operate in this case.

3. DOF's spectrum occupancy estimates are more than 85% accurate at low SNRs or in the presence of interference. The compared approach, Jello has an error of 35%, and cannot detect individual spectrum occupancies of interfering component signals.

4. DOF's AoA estimation error is less than 6 degrees for SNRs as low as 0dB, and is the same as SecureAngle.

Application in Smart Radios: DOF is practical and can be applied to many problems. While we leave most of DOF's applications to future work, we demonstrate the potential benefits of DOF for building smart and agile radios by designing and implementing a preliminary prototype, DOF-SR. The key novel component in DOF-SR is that it's aggressiveness in scavenging for unused spectral resources can be tuned by a user specified policy so that interference to co-existing radios is controlled. To demonstrate this flexibility we implement three sample policies, from one which only uses unoccupied spectrum and minimizes interference to co-existing radios to ones which use microwave oven occupied spectrum and compete with co-existing WiFi radios. We deploy DOF-SR in our indoor testbed and compare it with Jello (the best known prior approach which uses edge detection for finding unused spectrum). Our evaluation shows that DOF-SR provides nearly a 80% throughput increase over Jello in crowded environments. Further, the co-existing WiFi/Zigbee radios suffer less than 10% throughput drop with DOF-SR, while Jello can cause nearly a 45% throughput drop. DOF-SR outperforms because it can accurately detect (un)occupied spectrum even at low SNRs as well as the occupying signal types, allowing it to more accurately scavenge unused spectrum, yet guarantee that it does not affect the co-existing radios.

Steven Hong, Sachin Katti, "DOF: A Local Wireless Information Plane", In ACM SIGCOMM 2011, Toronto, Ontario, Canada