Embracing wireless interference: analog network coding

ABSTRACT

Traditionally, interference is considered harmful. Wireless networks strive to avoid scheduling multiple transmissions at the same time in order to prevent interference. This paper adopts the opposite approach; it encourages strategically picked senders to interfere. Instead of forwarding packets, routers forward the interfering signals. The destination leverages network-level information to cancel the interference and recover the signal destined to it. The result is analog network coding because it mixes signals not bits.

So, what if wireless routers forward signals instead of packets? Theoretically, such an approach doubles the capacity of the canonical 2-way relay network. Surprisingly, it is also practical. We implement our design using software radios and show that it achieves significantly higher throughput than both traditional wireless routing and prior work on wireless network coding.

REFERENCES

• 1: Daniel Aguayo , John Bicket , Sanjit Biswas , Glenn Judd , Robert Morris, Link-level measurements from an 802.11b mesh network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 2: R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung. Network Information Flow. In IEEE Trans. on Info. Theory, 2000.
• 3: J. F. Cardoso. Blind signal separation: statistical principles. Proceedings of the IEEE, 86(10):2009--2025, 1998.
• 4: Szymon Chachulski , Michael Jennings , Sachin Katti , Dina Katabi, Trading structure for randomness in wireless opportunistic routing, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 5: Christos Gkantsidis and Pablo Rodriguez. Network Coding for Large Scale Content Distribution. In INFOCOM, 2005.
• 6: S. Deb, M. Effros, T. Ho, D. R. Karger, R. Koetter, D. S. Lun, M. Medard, and N. Ratnakar. Network coding for wireless applications: A brief tutorial. In IWWAN, 2005.
• 7: Definition and assessment of relay based cellular deployment concepts for future radio scenarios considering 1st protocol characteristics, Ch5. https://www.ist-winner.org/DeliverableDocuments/D3.4.pdf.
• 8: G. FSF. Gnu radio - gnu fsf project. http://www.gnu.org/software/gnuradio.
• 9: J. Geier. Snr cutoff recommendations, 2005. http://www.wi-fiplanet.com/tutorials/article.php/3468771.
• 10: J. Hamkins. An analytic technique to separate cochannel fm signals. IEEE Transactions on Communications, 48(11):2980--2989, 2000.
• 11: T. Ho, R. Koetter, M. Médard, D. Karger, and M. Effros. The Benefits of Coding over Routing in a Randomized Setting. In ISIT, 2003.
• 12: E. Inc. Datasheet for the basicrx, basictx, lfrx, lftx, tvrx, and dbsrx daugtherboards. http://www.ettus.com/Download.html.
• 13: E. Inc. Universal software radio peripheral. http://ettus.com.
• 14: S. Jaggi, P. Sanders, P. A. Chou, M. Effros, S. Egner, K. Jain, and L. Tolhuizen. Polynomial time algorithms for multicast network code construction. IEEE Transactions on Information Theory, 2003.
• 15: S. Katti, S. Gollakota, and D. Katabi. Analog network coding. Working Draft. Available on the authors webpage.
• 16: S. Katti, I. Maric, A. Goldsmith, D. Katabi, and M. Médard. Joint Relaying and Network Coding in Wireless Networks. In ISIT. 2007.
• 17: Sachin Katti , Hariharan Rahul , Wenjun Hu , Dina Katabi , Muriel Médard , Jon Crowcroft, XORs in the air: practical wireless network coding, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 18: Ralf Koetter , Muriel Médard, An algebraic approach to network coding, IEEE/ACM Transactions on Networking (TON), v.11 n.5, p.782-795, October 2003 [doi>10.1109/TNET.2003.818197]
• 19: J. N. Laneman, D. N. C. Tse, and G. W. Wornell. Cooperative diversity in wireless networks: Efficient protocols and outage behavior. IEEE Trans. Inform. Theory, Dec. 2004.
• 20: S.-Y. R. Li, R. W. Yeung, and N. Cai. Linear network coding. IEEE Transactions on Information Theory, 2003.
• 21: D. S. Lun, M. Médard, and R. Koetter. Efficient operation of wireless packet networks using network coding. In International Workshop on Convergent Technologies (IWCT), 2005.
• 22: E. C. V. D. Meulen. Three-terminal communication channels. Adv. Appl. Probab., 3:120--154, June 1971.
• 23: J. S. Park, M. Gerla, D. S. Lun, Y. Yi, and M. Médard. Codecast: A network-coding based ad hoc multicast protocol. IEEE Wireless Communications Magazine, 2006.
• 24: R. L. Pickholtz, L. B. Milstein, and D. L. Schilling. Spread spectrum for mobile communications. IEEE Trans Veh. Technology, 1991.
• 25: Ram Ramanathan, Challenges: a radically new architecture for next generation mobile ad hoc networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080843]
• 26: A. Ramamoorthy, J. Shi, and R. Wesel. On the capacity of network coding for wireless networks. In 41st Annual Allerton Conference on Communication Control and Computing, Oct. 2003.
• 27: B. Rankov and A. Wittneben. Achievable rate regions for the two-way relay channel. In Proc. IEEE Int. Symposium on Information Theory (ISIT), Jul 2006.
• 28: B. Rankov and A. Wittneben. Spectral efficient protocols for half-duplex fading relay channels. IEEE Journal on Selected Areas in Communications, 25, Feb. 2007.
• 29: Shengli Zhang , Soung Chang Liew , Patrick P. Lam, Hot topic: physical-layer network coding, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161129]
• 30: C. E. Shannon. Two-way communication channels. 4th Berkeley Symposium Math. Stat. Prob., 1:611--644.
• 31: David Tse , Pramod Viswanath, Fundamentals of wireless communication, Cambridge University Press, New York, NY, 2005
• 32: Sergio Verdu, Multiuser Detection, Cambridge University Press, New York, NY, 1998
• 33: Jörg Widmer , Jean-Yves Le Boudec, Network coding for efficient communication in extreme networks, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.284-291, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080147]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
cooperative transmission, network coding, wireless networks