In distributed wireless communication systems, the cost of the distributed nature of the system manifests itself in form of interference. In particular, when two distributed users contend for the same portion of the wireless spectrum, they interfere with each other. This interference limits the amount of free bandwidth each user gets, which in turn limits the performance of each user in this communication system. In general, efficient design of wireless communication systems is widely believed to be limited because of interference. Interference alignment, in theory, can enable a performance that is comparable to the case where the system were not distributed. We show the key idea in the toy example below.



Toy Example for Alignment
Consider room with 60 speaker-listener pairs, and correspondingly 60 conversation. Each listener is uninterested in the 59 conversations of the remaining 59 speaker. Now, if the room is small enough so that all pairs are sufficiently close to each other, the conversations interfere with each other, i.e., each man is forced to listen to the words of all the 99 speakers in the system. Now suppose that interference cannot be resolved by the listeners, i.e., if two or more different words overlap simultaneously, then the listener does not understand either word. Then, assuming that all 60 pairs stay in the room for a total of an hour, how can we design this interference-free system?

A Naive Solution: Each listener can speak for 1/60 of an hour (i.e. one minute) so that all 60 conversations are interference-free. Because of interference, the amount of time a woman can speak reduces to a fraction of 1/60 of the total available time with this strategy of diving the one hour among the 60 speakers (like dividing a cake)! In other words, the amount of time each speaker gets to speak to the corresponding listener scales inversely as the number of pairs in the room.

Question: Can we do better? While it may appear that it is impossible to do better, it turns out that, under certain circumstances each speaker can speak for 30 minutes (i.e., each conversation is active for 30 minutes) free of interference. This is a huge gain (a factor of 60) over the naive strategy which allows each conversation to be active for only one minute. The principle behind this seemingly impossible solution is the idea of
interference alignment demonstrated in the picture below (for the case where there are only 3 speakers).

DelayforWeb


The key idea enabling each user to speak for half the available time (i.e., 30 minutes) is to exploit propagation delays. Suppose (somehow) the locations of the transmitters and receivers can be configured such that the delay from each transmitter to its intended receiver is an odd number of symbols, while the signal propagation delay from each transmitter to all unintended receivers is an even number of symbols. The communication strategy is that all speakers speak during simultaneously at odd symbol durations and stay silent during the even symbol durations. With this policy, each receiver sees its own transmitter's conversation (free of interference) over even time periods, while it sees all interfering signals
aligning simultaneously over odd time periods. Thus each user is able to get half the available spectrum free of interference!

While the above is simply a toy example to convey the idea, it is arguably artificial and unrealistic. In particular, the delays are forced to satisfy a particular property. However, quite surprisingly, the intuitions carry forward to more generic and naturally occurring models of wireless communication. Please refer to the resources below for more information.

Additional Resources


1.
This article in the IT Society Newsletter.
2.
Syed A. Jafar’s tutorial on Interference Alignment.
3. Robert Heath’s page on Interference Alignment
4.
Distributed Storage Wiki (for connections of alignment to distributed storage).