The WindoWSIL

Some of you may be familiar with the Erdos number in mathematics. This number is sort of a “degrees of separation”, in publication terms, from one Paul Erdos. I did a little surfing and found out that Prof. Heath’s Erdos number is about to become 6, if a recently submitted article is accepted.

Claude Shannon has an Erdos number of 3. Also, Bob Gallager published a couple papers with Shannon, one of them being:

Claude E. Shannon, Robert G. Gallager, Elwyn R. Berlekamp: Lower Bounds to Error Probability for Coding on Discrete Memoryless Channels. I Information and Control 10(1): 65-103 (1967)

One of Gallager’s students was Randall Berry:

Randall A. Berry, Robert G. Gallager: Communication over fading channels with delay constraints. IEEE Transactions on Information Theory 48(5): 1135-1149 (2002)

Finally, a recently submitted article to IEEE Communications magazine is co-authored by Prof. Heath and Prof. Berry, collaboraters on the DARPA IT-MANET project:

J. G. Andrews, N. Jindal, M. Haenggi, R. Berry, S. Jafar, D. Guo, S. Shakkottai, R. W. Heath, Jr., M. Neely, S. Weber, A. Yener, P. Stone, “Rethinking Information Theory for Mobile Ad Hoc Networks,'’ submitted to IEEE Communications Magazine Dec. 2007.

If this is accepted, it will give anyone connected to Prof. Heath an Erdos number of at most 7. It’s amazing how connected we all are. Albert Einstein has an Erdos number of 2, so (at most) 9 papers separate us from Albert Einstein. Isn’t that crazy?

If you’re not a member of WSIL, what is your Erdos number?

Chan-Byoung’s recent flurry of blog activity has inspired me to emerge from blogging hibernation.

Many of us wonder what forms need to be signed in order for us to graduate. We’ve heard stories about the “green sheet,” the “gold sheet,” the “pink sheet” and even the mysterious “white sheet.” What, exactly, are these various forms?

I can now say with some certainty that the mysterious “white sheet” is the “Report of ECE Ph.D. Qualifying Exam Committee.” Your qualifying exam committee chair fills out this form and signs it at the bottom. The highlights of this form include: 1) a list of the qualifying exam committee members and 2) the committee’s recommendation (including the dreaded “Other” option).

As for the “green,” “gold” and “pink” sheets, stay tuned (perhaps Kaibin’s defense will shed some light on this).

The IEEE is without a doubt the society whose publications we submit to (and read from) the most. They have recently released an 18-page style manual (pdf) that all transactions adhere to. Some of the more useful sections include proper referencing of different things (references make up about 14 pages of the document), proper abbreviations, and where in the paper to acknowledge funding.

IEEE P802.16j/D2 passed letter ballot today. After comments on the draft made by negative voters are resolved, the draft will move to Sponsor Ballot and then on the the Standards Board Review Committee (RevCom). I expect it will be approved by the Standards Board by October.

There’s a really nice article* in this month’s IEEE Spectrum Magazine about Sprint’s Xohm, which will provide the first WiMAX service in the United States. I’m usually not too excited about this kind of stuff, but I will definitely look into it when it is offered here in Austin. This year they plan on deploying in Chicago, Baltimore, and Washington, D.C., followed by New York City.

Perks:

• 2-4 Mbps, which is 4-8 times faster than 3G.
• Equipment available will include laptop adapters, mobile phones, and home modems, meaning one service can give you broadband access to your home, give you a WiFi-like hotspot anywhere in the city, and be your mobile phone.
• Prices are expected to be competitive with DSL.
• No contracts.

Now we just have to hope WiMAX equipment isn’t too expensive.

The second draft of IEEE 802.16j, the Multihop Relay amendment to IEEE 802.16e/Mobile WiMAX, is currently being voted on by IEEE 802.16 members. The first draft only garnered a 67% approval while needing 75%. Over 1050 comments have been resolved since Draft 1, and so far the turnout has looked positive—6 people have changed their vote from Disapprove to Approve so far; 2 changed from Abstain to Approve; 1 that did not vote before now Approves.

Votes from the first ballot carry over if the person does not vote again, which means if no one else votes between now and January 14th–when the ballot closes–Draft 2 will have a 69.85% approval, meaning it will fail again. However, by the number of changes in votes so far, I’m betting this draft will be approved by a narrow margin.

Ever wonder how OFDM-based systems estimate the channel response? I know I have. In fact it was the topic of my M.Sc. dissertation. The idea is quite simple: we dedicate a fraction of what I will loosely call the degrees of freedom of the system to the task at hand. As a case in point, a portion of the orthogonal subcarriers within an OFDM bandwidth may be used to estimate and/or track the frequency selective channel. So let me define energy and frequency as two degrees of freedom. For example, a widely accepted and also widely employed means of acquiring channel state information (CSI) at the receiver of wireless links is to multiplex known pilot symbols into the transmission data stream; a technique referred to as pilot symbol aided modulation (PSAM). PSAM directly utilizes both energy and frequency, and the channel response is then obtained using either Bayesian or ML techniques. I should note that using pilot symbols has been around for a long time; in fact it dates all the way back to the early days of FM radio. Interestingly it has proven to be so robust that it is even used in modern systems such as WiMAX/802.16. The degrees of freedom in PSAM have been optimized in almost every way an engineer can imagine: to minimize error rate, to maximize capacity, to minimize MSE, etc.

So what else can we do? Well this brings me back to what I called degrees of freedom. I forgot to tell you that PSAM is designed for open-loop systems. The TX allocates energy and frequency to the pilot symbols without any knowledge of the channel within which the pilots propagate through. Intuitively one would expect that the degrees of freedom be uniformly distributed: both in the sense of energy and in the sense of frequency. This is in fact the case and is a well established theoretical fact: equi-power, uniformly frequency-spaced pilots are optimal in the SER, capacity and even MSE sense. Well what if the TX somehow had CSI through, e.g., an ideal feedback link? You expect that the TX now makes a more intelligent decision on distributing the degrees of freedom, right? For example say a certain subcarrier frequency is experiencing a deep fade, the TX may opt to allocate a pilot symbol to this fade instead of a data symbol. Clearly this will be at the expense of channel MSE (uniform pilots are always MSE optimum). So given a certain number of data symbols M, and a certain number of pilot symbols P, where M+P=const, we clearly have a fundamental trade-off we may optimize.

I hope I have convinced you that uniform pilots are no longer (at least intuitively) optimal in any sense. So if you’ve managed to read this far and are curious to find out what the optimal pilots are I encourage you to check out [J1] on my website. There I look at pilot symbols that obtain maximal SNR at the RX. For my MIMO course project, and based on [J1], I extended to pilot allocations that optimize for minimum SER and also for allocations that maximize ergodic capacity. I’ve also got some nice results using vector quantization and Alamouti STBC. I’m putting some finishing touches on these results and will hopefully submit a finalized version to IEEE Transactions on Vehicular Technology later this month. Of course I’ll have a preprint up afterwards, so stay tuned!

I stumbled across this interesting article on SmallNetBuilder about the performance of commercial 802.11g devices. To summarize, they used an RF channel emulator between two 802.11g stations to observe the performance of competing devices. The results are, in my opinion, shocking. The best device performs as well as the worst device with over 10 dB more path loss.

As engineers we often believe that better engineering results in more sales and a larger market share…but this isn’t necessarily true. Linksys will sell many, many products due to their brand name recognition, even if the 11g chip they use performs poorly. This brings me to the question, does the average consumer care enough about engineering to make a difference? That is, even if you develop a poorly performing device, as long as it performs well enough it really doesn’t mean much if you can’t market it. I think maybe this situation is unique to wireless LAN, because there is more patience in the performance of WLAN devices. For cell phone chipmakers, if your product drops calls at a high rate, I think you’ll see a consumer reaction. What are all of your thoughts?

As a side note, check out the throughput curve from the figure above. Notice that, at best, you get 23 Mbps of throughput when the PHY rate supports 54 Mbps. This is a point-to-point link using near-field antennas. At best, you won’t even get 50% of the PHY throughput. Clearly, there is much work to be done in improving the 802.11 MAC (even though alot of work was done for the 802.11n standard). You can also get a hint about the link adaptation used from the throughput curve. I suspect the curves that have dips at low path loss must not use SNR-based feedback and maybe an auto-rate fallback method while the others use SNR-based feedback. I cannot confirm this because I don’t know how reliable the testing is, but it seems plausible given some of the observations we’ve seen testing these algorithms in Hydra.

I know this is Bob’s thing, but he’s busy doing real engineering work at the moment.

This semester has gone by extremely quickly. Unbelievably, I’ve been in WSIL for six months already. Amazing.

I’ll first present the latest news. Sumohana Channappayya successfully defended his dissertation and will be heading to San Diego to join the real world as a newly anointed Ph.D. Congratulations, Sumo!

Along similar lines, Caleb Lo and Chan-Byoung Chae both successfully passed quals yesterday. These two, along with Kaibin Huang, are next in line to graduate.

Further, we have published, submitted, or have had accepted numerous papers on topics ranging from prototyping to information theory. In particular, we published the following seven journal papers this semester:

• R. Chen, J. G. Andrews, R. W. Heath, Jr., and A. Ghosh, “Uplink Power Control in Multi-Cell Spatial Multiplexing Wireless Systems,” IEEE Trans. on Wireless, vol. 6, no. 7, pp. 2700-2711, July 2007. [IEEE Xplore]
• A. Forenza, D. J. Love, and R. W. Heath, Jr., “Simplified Spatial Correlation Models for Clustered MIMO Channels with Different Array Configurations,'’ IEEE Trans. on Veh. Tech., vol. 56, no. 4, part 2, pp. 1924-1934, July 2007. [IEEE Xplore]
• K. Huang, R. W. Heath, Jr., and J. G. Andrews, “Space Division Multiple Access with a Sum Feedback Rate Constraint”, IEEE Trans. on Signal Processing, pp 3879-3891, Jul. 2007. [IEEE Xplore]
• B. Mondal and R. W. Heath, Jr., “Quantization on the Grassmann Manifold,'’ IEEE Trans. on Signal Processing, vol. 55, no. 8, pp. 4208-4216, Aug. 2007. [IEEE Xplore]
• V. Raghavan, R. W. Heath, Jr., and A. Sayeed, “Systematic Codebook Designs for Quantized Beamforming in Correlated MIMO Channels,'’ IEEE Journal on Sel. Areas in Comm., Special Issue on Optimization of MIMO Transceivers for Realistic Communication Networks: Challenges and Opportunities, vol. 25, no. 7. pp. 1298-1310, Sept. 2007. [IEEE Xplore]
• M. R. McKay, I. B. Collings, A. Forenza, and R. W. Heath, Jr., “Multiplexing/Beamforming Switching for Coded MIMO in Spatially Correlated Channels Based on Closed-Form BER Approximations,'’ IEEE Transactions on Vehicular Technology, vol. 56, no. 5, part 1. pp. 2555-2567, Sept. 2007. [IEEE Xplore]
• D. Gesbert, M. Kountouris, R. W. Heath, Jr., C. B. Chae, and T. Salzer, ‘Shifting the MIMO Paradigm: From Single User to Multiuser Communications,’ IEEE Signal Processing Magazine, Vol. 24, No. 5, pp. 36-46, Oct., 2007 [IEEE Xplore]
  

Also, first year grad student Alvin Leung taught us all a ping pong lesson in the first annual WSIL ping pong tournament. His skills will surely diminish as grad school takes over his life.

There really was so much more to this semester. In many ways, Fall 07 will be remembered as a semester where a lot of work was put into projects that other semesters will be able to claim to have finished, as this semester did with the above journal papers. We submitted far more journal papers than we published. We welcomed 6 new members and said goodbye to only 1. And we put in hundreds of hours into projects whose payoffs are still months away. In that way, you might say it was a blue-collared semester.

If anyone else has something to add (feel free to toot your own horn), please comment.

Back in the day I used to frequent some grad school discussion boards on the internet. Yes, I’m a loser (I can feel Bob laughing at me already). It really struck me how different the grad school experience is in the rest of the world. For instance, at Ali’s M.S. university in Canada, he had to defend his M.S. thesis. In Australia, they don’t even have to defend their Ph.D. thesis. Even more astounding, in Europe and Australia (and probably several other places), a PhD generally takes three years after a bachelors. And they have no coursework.

On the other hand, in North America, we are required to earn Master’s degrees before our Ph.D. (or Sc.D.), and must take quite a few courses to do so, the exact amount of which varies from school to school. I believe I heard the average time from bachelors to Ph.D. in the U.S. is around 5.5 years.

How can it take more than two more years for us to get our Ph.D.’s relative to other areas of the world? Do we learn more? Are we less prepared? Are our programs less intense? Certainly at least one of these has to be true to some extent.

When Dan Ryan (from CSIRO in Australia) came to visit the WSIL this summer, he said classes are pointless for grad school; we should be able to learn everything we need to know out of a book. What is our response to this?

I’m afraid I only have questions on this topic.