The WindoWSIL

In this post I want to discuss the deficiencies of practical link adaptation in current wireless systems and how algorithms that exploit machine learning will be the solution to all of these problems. First, a little background on link adaptation.

The quality of the medium through which communication occurs, i.e., the wireless channel, is constantly changing. Consider the following figure, courtesy of the Laboratory for Information Technology at Aachen University, which shows the channel quality of a cellular network throughout a rural town in Germany (green=good, red=bad). Reality is actually much worse than this since the channel also fluctuates due to small scale fading.

Digital communication parameters used to construct wireless waveforms (e.g., QAM order, FEC rate, the number of spatial streams, etc.) observe a tradeoff between reliability, e.g., the probability of a dropped call in a voice network, and data rate in terms of the wireless channel quality. Consequently, modern wireless networks get the most “bang for their buck'’ in today’s spectrum limited wireless market through link adaptation where link adaptation is the process of selecting digital communication parameters based on real-time channel quality measurements. Link adaptation allows for joint optimization of reliability and data rate tailored to each application.

Most published research makes link adaptation seem like a straightforward problem.

1. Measure the wireless channel.
2. Extract a link quality metric from the wireless channel.
3. Map the link quality metric to digital communication parameters using a look-up-table or rate/reliability formulas.

Look-up-tables/formulas are created offline through analysis, simulations, or measurements. When I attempted to do this on our IEEE 802.11n prototype, Hydra, I found out that link adaptation in practice can be very difficult. Here are a few of the lessons I learned.

• System nonlinearities make look-up-tables created through analysis or simulations inaccurate.
• Non-Gaussian noise make look-up-tables created through analysis or simulations inaccurate.
• Channel estimation error must be accounted for.
• Look-up-tables based on actual over-the-air measurements result in the most accurate adaptation.
• Look-up-tables based on actual over-the-air measurements for one device may result in inaccurate adaptation if placed on a different wireless device.

After my initial testing I was concerned that it might be difficult to use our prototype, even with significant amplifier backoff to design/evaluate practical link adaptation algorithms. Apparently, however, commercial systems suffer from the same issues. For example, the Roofnet project found that the SNR link quality metric did not consistently reflect the expected reliability of the associated digital communication parameters, even when interference/collisions are not an issue.

Another large problem we discovered is that good link quality metrics for MIMO-OFDM systems just weren’t available. It turns out that analyzing the error rate of practical MIMO-OFDM links is very difficult. Consequently, finding a good, single-dimensional (which is required for look-up-tables) link quality metric that modeled the spatial and frequency selective effects of the channel was also very difficult.

So what do we do? The linear, time-invariant models we have used to create link adaptation rate/reliability expressions or to run link simulations (which may then result in look-up-tables) do not reflect the actual system. One approach is to make our analysis model more complex to include nonlinear and non-Gaussian noise effects. This seemed like a difficult undertaking. Analysis was already difficult with our simplistic linear, time-invariant system and additive Gaussian noise. Using a more complex system model would only lead to more design time for engineers. Moreover, even if we are able to find a good link quality metric, it will likely be multi-dimensional, and look-up-tables aren’t easily created in this case. All of this lead us (Professor Heath and I) to machine learning.

Machine learning algorithms allow systems (in our case the link adaptation algorithm) to learn behavior solely from data observations. Hence, as long as we were able to define an accurate link quality metric and pose the problem correctly, machine learning should be able to discover the relationship between the link quality metric and the reliability of the link. First, we created the multi-dimensional ordered SNR link quality metric based on our new expression of packet error rate in MIMO-OFDM systems. Then, with the help of Professor Caramanis, we validated the efficacy of classification algorithms that exploited this new link quality metric for link adaptation. However, all this work was done using system models. To compensate for unique hardware nonidealities, we needed an online algorithm that tuned link adaptation to each transmit/receive device pair. Consequently, Professor Heath and I designed online classifiers that harness training information on-the-fly. These algorithms constantly observe packets transmitted over channels and improve the link adaptation classifier in real time based on these observations.

For example, see the following figure which shows a plot of throughput and packet error rate for offline and online machine learning in a static wireless channel with our wireless prototype and a packet error rate reliability constraint of 10%. The offline algorithm is not able to tune itself to the unique hardware characteristics of the transmit/receive pair, resulting in lost rate/reliability. The online algorithm, however, discovers the correct digital communication parameters in real-time. There have been other rate adaptation algorithms, notably auto-rate fallback (ARF), which adapt online. Unfortunately, they don’t take advantage of explicit link quality metrics and so cannot adapt well in dynamic channel conditions (see following figure).

The best part of our online learning algorithms for link adaptation is simplicity. The algorithms are installed and we’re done. No complex analysis of the reliability curves. No calibration algorithms to determine amplifier backoff. Additionally, our recent results with support vector machines also show that online learning can be implemented with low memory/processing complexity.

For More Information:

R. C. Daniels and R. W. Heath, Jr., “Online Adaptive Modulation and Coding with Support Vector Machines,” to appear in Proceedings of the IEEE European Wireless Conference, Lucca, Italy, April 2010.

R. C. Daniels and R. W. Heath, Jr, “An Online Learning Framework for Link Adaptation in Wireless Networks,” Proceedings of the Information Theory and Applications Workshop, San Diego, CA, February, 2009.

R. C. Daniels, C. M. Caramanis, and R. W. Heath, Jr, “Adaptation in Convolutionally-Coded MIMO-OFDM Wireless Systems through Supervised Learning and SNR Ordering,” IEEE Transactions on Vehicular Technology, January, 2010.

Charles K. Kao, who got his PhD in Electrical Engineering from Imperial College London, and founded the Electrical Engineering Department at Chinese University of Hong Kong, was just awarded the Nobel Prize in Physics for his pioneering work on fiber optic communications.

This is really amazing to me, a trained engineer winning this award. Yes, John Bardeen won two of these, but he was really trained as a physicist. I’m willing to bet money that physicists don’t like this decision.

I ran into this article today: Ten Signs a Claimed Mathematical Breakthrough is Wrong. While the author is writing from the perspective of quantum mechanics, I think we can extend many of the sanity checks to problems in communication theory and signal processing as well.

I really like the first point: “the authors don’t use TeX”. I don’t know why but there seems to be such a correlation but I have seen this time and again.

A very interesting play, perhaps most amusing for wireless engineers, centered around the story of frequency hopping.
http://www.sciam.com/article.cfm?id=hedy-lamarr-not-just-a-pr

I like how they use the music analogy. Perhaps the first hopping algorithm was something like “Scott Joplin’s Entertainer” since Bach would be easily recognized by the Germans.

Today I came across a nice result on the distribution of eigen values of matrix , where the entries of are i.i.d. Gaussian distributed. The result says that the eigen value (in the decreasing order) of has the following distribution, for small .
Its quite useful for analysing many MIMO techniques, such as MRC, MRT.
The reference is a recent IT Paper: http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4544985&isnumber=4544949

A student from China recently asked me about how I got interested in relay selection and started obtaining (publishable) results. Since I have some free time on my hands now, I figured I’d share some thoughts on this topic.

I actually don’t think that the way I got interested in relay selection was the ideal strategy in terms of “finding a good research topic.” Instead, I’ll discuss what I think is a better way of “finding a good research topic.” Note that the following is especially relevant for graduate students researching wireless communications (for the obvious reasons).

It’s fairly common for a new graduate student to be overwhelmed by the plethora of potential research topics. When I was starting work on my masters degree, I wanted to do research involving some aspect of wireless networks, since I felt (wrongly, as it turned out) that all of the good point-to-point problems had already been solved. During the summer of 2004, I worked on beamforming for MIMO ad hoc networks, but that ended up being a major dead end. On a related note, I recently perused my research notebook and found that during January 2006, I was interested in cooperative diversity for OFDM networks (my, how things have changed).

This brings up the key question: how should a new graduate student sort through the morass of potential research topics and come up with a good one? I’ll discuss two potential answers.

One approach is to have your advisor answer this question for you, assuming that you have an advisor. In general, you can assume that your advisor has a strong grasp of the current state of research in wireless communications. This knowledge can help him/her determine a topic for you that is 1) interesting, so you won’t be bored stiff for approximately 5 years and 2) worthy of a Ph.D. dissertation, so you will have made a fundamental contribution of some sort by the time you graduate.

The second approach, which I highly recommend, is to take the initiative. To start off, you should do a significant amount of reading. Survey articles in journals such as the IEEE Communications Magazine and the IEEE Signal Processing Magazine can be valuable starting points for the interested yet relatively inexperienced grad student.

A particularly well-written survey article can provide the reader with a good grasp of “what’s been done” on a topic such as “OFDMA power allocation for relay-based networks” and suggest various open problems that are both interesting and important. When reading through these survey articles, one should also scan the list of references to learn about the key papers (and researchers, so you can bookmark their home pages) in a particular area.

It’s then important to read through these key papers to grasp the nuances of the topic that you’re learning about and ask yourself tough questions along the way. For example, do you understand the (technical) paper that you’re reading? Can you justify all of the authors’ assumptions? Can you re-derive every expression (especially the proofs of key theorems) in the paper? I should note that sometimes papers contain typos/gross errors, so you shouldn’t automatically trust everything you read.

If you want to answer these questions in the affirmative, this is a great opportunity for building your technical background. For example, let’s say that the authors are studying a MIMO wireless system and assume that a two-ring scattering model is being employed. If you don’t know what a two-ring scattering model is, you should obtain a copy of a MIMO textbook such as this one by Paulraj et al. and learn more about channel modeling.

Also, let’s say that you’re reading through this famous paper by Gupta and Kumar, and you’re having trouble deriving some (or all, as this paper is actually quite tricky to understand) of the key results. In this case, you might want to strengthen your graph theory background by taking an appropriate class, such as this one at UT-Austin. You might also want to improve your knowledge of random geometry, and you can check your university library for a helpful book such as this one by Bollobas for more coverage of this advanced topic.

As you read through the key technical papers in the area that you’re learning about, you should think of additional open problems and ask yourself more tough questions. For example, you can ponder something like, “the authors’ assumption of a zero-error feedback channel seems a bit restrictive. From my other reading it’s clear that introducing a channel estimation error at the transmitter would better model a practical system. Maybe I can’t obtain an exact expression for the sum capacity given channel estimation errors, since that seems quite complicated, but can I obtain relatively tight bounds?”

Regardless of the approach that you take in terms of finding a good research topic, it’s crucial that you interact with your advisor during this process. Your advisor, who has worked in either the general area that you’re considering or a related area, can help you determine if the open problem you’re considering is either trivial, worthy of multiple dissertations, or actually reasonable for a dissertation. Note that by adopting the second approach I discussed above, your ability to have meaningful dialogue with your advisor during this process is enhanced. In particular, you can evaluate your advisor’s suggestions and converge on a reasonable topic more quickly; this is especially important if your advisor has not worked in the general area that you’re considering.

That’s all I had to say on this subject, at least for now. I welcome comments, especially from my group-mates on this issue of “finding a good research topic.”

San Francisco was the site of the 2008 WiNTECH Workshop, which held a contest between teams presenting demonstrations of their research prototypes. The theme of the contest was “The Next Big Thing in Wireless”, and consisted of teams building real wireless systems and giving a live demonstration of their capabilities.

The winning team consisted of Robert C. Daniels, Ketan Mandke, Steven W. Peters, Prof. Scott M. Nettles, and Prof. Robert W. Heath, Jr., and their winning presentation was called “Machine Learning for Physical Layer Link Adaptation in Multiple-Antenna Wireless Networks”. Daniels and Peters are graduate students in the WSIL, which is directed by Prof. Heath. The demo consisted of using simple machine learning techniques to do adaptation in wireless devices using a custom-built IEEE 802.11n physical layer (PHY). Because this PHY uses coded MIMO-OFDM, adaptation is a difficult prospect. The team successfully demonstrated that the devices were learning the channel with no pre-existing knowledge, and could easily adapt to changing conditions. They used the Hydra prototype, which is in continuous development, as the foundation for the demo.

The winning students received a $2500 cash prize kindly donated by the sponsors, ViaSat, Nokia Siemens Networks, The Center for Multimedia Communication, and BBN Technologies.

The work was sponsored in part by NSF and DARPA ITMANET.

Light up Turn on Engage
Laptop and Terminal Euphoria
Linking The Earth
Linking Telephony Everywhere
Luscious Telephony Experience
Limitless Technology for Everyone
Limited Time Enigma
Laugh Track Escapade
Lightning-fast Transfer of Everything
Let’s Turnaround East
Late Troublesome Expensive
Look, Talk, and Enjoy
Live Telecommunication Environment
Leading Telecommunication Excellence
Loads of Traffic for Everyone
Live connection To Everyone
Live communication To Everyone
Lifeline To Everyone
Let’s Take it Easy
Life Time Eternal
Love Thy Enemy
Link Technology Enhancement
Legacy Terminal Equipment

- from LTE / LTE-A TSG RAN mailing list

Some people also say “Long Term Employment” or “Life Time Employment.” :)
But my pick is “Love Thy Enemy.” How about you?

Although there is still a week of finals, the semester is basically finished. This has been my most eventful semester, personally, but how did the WSIL fare? Let’s take a look.

First and foremost, our dear Kaibin Huang just successfully defended his dissertation and is on his way to a post-doc at Hong Kong University of Science and Technology. Not only that, but he was awarded the WNCG Student Leadership award. A WSIL member has won this award two of the past three years.

Along the same lines, Takao Inoue is now a Ph.D. Candidate. He joins Chan-Byoung Chae and Caleb Lo as the next in line to graduate.

We also welcomed the well-known Dr. Marios Kountouris as a post-doctoral researcher.

In addition, we had eight journal papers published:

• R. C. Daniels R. W. Heath, Jr., “60 GHz Wireless Communications: Emerging Requirements and Design Recommendations,'’ IEEE Vehicular Technology Magazine, vol. 2, no. 3, pp. 41-50, Sept. 2007. [IEEE Xplore]
• J. G. Andrews, W. Choi, and R. W. Heath, Jr., “Overcoming interference in spatial multiplexing MIMO cellular networks,'’ IEEE Wireless Communications, vol. 14, no. 6, pp. 95-104, Dec. 2007. [IEEE Xplore]
• W. Choi, A. Forenza, J. G. Andrews, and R. W. Heath, Jr., “Opportunistic space division multiple access with beam selection,'’ IEEE Trans. on Communications, vol. 55, no. 12, pp. 2371-2380, Dec. 2007. [IEEE Xplore]
• K. Huang, R. W. Heath, Jr., and J. G. Andrews, “Uplink SDMA with Limited Feedback: Throughput Scaling,'’ EURASIP Journal on Advances in Signal Processing, special issue on MIMO Transmission with Limited Feedback, vol. 2008, Article ID 479357, 17 pages, doi:10.1155/2008/479357, 2008. [EURASIP Website]
• B. Mondal and R. W. Heath, Jr., “A Diversity Guarantee and SNR Performance for Quantized Precoded MIMO Systems,'’ EURASIP Journal on Advances in Signal Processing, special issue on MIMO Transmission with Limited Feedback, vol. 2008, Article ID 594928, 15 pages, doi:10.1155/2008/594928, 2008. [EURASIP Website]
• Kyung Seung Ahn, R. W. Heath, Jr., and H. K. Baik, “Shannon Capacity and Symbol Error Rate of Space-Time Block Codes in MIMO Rayleigh Channels with Channel Estimation Error,'’ IEEE Trans. on Wireless Communications, vol. 7, no. 1, pp. 324-333, Jan. 2008. [IEEE Xplore]
• C. B. Chae, T. Tang, R. W. Heath, Jr., and S. Cho, “MIMO Relaying with Linear Processing for Multiuser Transmission in Fixed Relay Networks,'’ IEEE Trans. on Signal Processing, vol. 56, no. 2, pp. 727-738, Feb. 2008. [IEEE Xplore]
• D. Piazza, N. J. Kirsch, A. Forenza, R. W. Heath, Jr., and K. R. Dandekar, “Design and Evaluation of a Reconfigurable Antenna Array for MIMO Systems,'’ IEEE Trans. on Antennas and Propagation, vol. 56, no. 3, pp. 869-881, Mar. 2008. [IEEE Xplore]

In addition, our fearless leader Prof. Heath, along with Prof. Andrews, won the WNCG Spring 2008 Bocce Ball tournament.

And finally, a long semester of ups and downs concludes with a nice week in the U.S. Virgin Islands for the IEEE Communication Theory Workshop, with Prof. Heath as General Chair.

Please add more here if I forgot something.

For U.S. PhD-degree holders, don’t use the title “Dr.” in your business cards when you visit Germany. If not, you may face a year behind bars.

News from Washington Post

Note: this news was not posted on April 1st.