Symbol-level network coding for wireless mesh networks

ABSTRACT

This paper describes MIXIT, a system that improves the throughput of wireless mesh networks. MIXIT exploits a basic property of mesh networks: even when no node receives a packet correctly, any given bit is likely to be received by some node correctly. Instead of insisting on forwarding only correct packets, MIXIT routers use physical layer hints to make their best guess about which bits in a corrupted packet are likely to be correct and forward them to the destination. Even though this approach inevitably lets erroneous bits through, we find that it can achieve high throughput without compromising end-to-end reliability.

The core component of MIXIT is a novel network code that operates on small groups of bits, called symbols. It allows the nodes to opportunistically route groups of bits to their destination with low overhead. MIXIT's network code also incorporates an end-to-end error correction component that the destination uses to correct any errors that might seep through. We have implemented MIXIT on a software radio platform running the Zigbee radio protocol. Our experiments on a 25-node indoor testbed show that MIXIT has a throughput gain of 2.8x over MORE, a state-of-the-art opportunistic routing scheme, and about 3.9x over traditional routing using the ETX metric.

REFERENCES

• 1: Sanjit Biswas , Robert Morris, ExOR: opportunistic multi-hop routing for wireless networks, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 2: 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
• 3: E. M. Gabidulin. Theory of codes with maximum rank distance. Probl. Inform. Transm., pages 1--12, July 1985.
• 4: J. Hagenauer and P. Hoecher. A Viterbi Algorithm with Soft-Decision Outputs and its Applications. In IEEE GLOBECOM, Dallas, USA, 1989.
• 5: T. Ho, R. Koetter, M. M´edard, D. Karger, and M. Effros. The Benefits of Coding over Routing in a Randomized Setting. In ISIT, Yokohoma, Japan, 2003.
• 6: E. Inc. Universal software radio peripheral. http://ettus.com.
• 7: S. Jaggi, M. Langberg, S. Katti, T. Ho, D. Katabi, and M. Médard. Resilient network coding in the presence of byzantine adversaries. In IEEE INFOCOM, Alaska, USA, 2007.
• 8: Kyle Jamieson , Hari Balakrishnan, PPR: partial packet recovery for wireless networks, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 9: S. Katti. Network Coded Wireless Architecture. PhD thesis, MIT, 2008.
• 10: S. Katti, S. Gollakota, and D. Katabi. Analog network coding. In ACM SIGCOMM, Kyoto, Japan, 2007.
• 11: 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
• 12: R. Koetter and F. Kschischang. Coding for errors and erasures in random network coding. IEEE Transactions on Information Theory, 2007. To appear.
• 13: 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]
• 14: J. N. Laneman, D. N. C. Tse, and G. W. Wornell. Cooperative diversity in wireless networks: Efficient protocols and outage behavior. IEEE Trans. on Inform. Theory, Volume 50, Issue 12, Dec. 2004 Page(s):3062--3080.
• 15: H. Lee. A high-speed low-complexity reed-solomon decoder for optical communications. IEEE Transactions on Circuits and Systems, 52(8):461--465, Aug. 2005.
• 16: Shu Lin , Daniel J. Costello, Error Control Coding, Second Edition, Prentice-Hall, Inc., Upper Saddle River, NJ, 2004
• 17: F. J. McWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland, 1977.
• 18: Allen Miu , Hari Balakrishnan , Can Emre Koksal, Improving loss resilience with multi-radio diversity in wireless networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080832]
• 19: Christos Gkantsidis , Wenjun Hu , Peter Key , Bozidar Radunovic , Pablo Rodriguez , Steluta Gheorghiu, Multipath code casting for wireless mesh networks, Proceedings of the 2007 ACM CoNEXT conference, December 10-13, 2007, New York, New York [doi>10.1145/1364654.1364667]
• 20: Charles Reis , Ratul Mahajan , Maya Rodrig , David Wetherall , John Zahorjan, Measurement-based models of delivery and interference in static wireless networks, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 21: G. Richter and S. Plass. Error and erasure decoding of rank-codes with a modified berlekamp-massey algorithm. In 5th International ITG Conference on Source and Channel Coding, Erlangen, Germany, 2004.
• 22: 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]
• 23: D. Silva, F. R. Kschischang, and R. Koetter. A rank-metric approach to error control in random network coding. submitted, 2007.
• 24: Dongjin Son , Bhaskar Krishnamachari , John Heidemann, Experimental study of concurrent transmission in wireless sensor networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182831]
• 25: David Tse , Pramod Viswanath, Fundamentals of wireless communication, Cambridge University Press, New York, NY, 2005
• 26: Mythili Vutukuru , Kyle Jamieson , Hari Balakrishnan, Harnessing exposed terminals in wireless networks, Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation, p.59-72, April 16-18, 2008, San Francisco, California
• 27: M. Wang, X. Weimin, and T. Brown. Soft Decision Metric Generation for QAM with Channel Estimation Error. IEEE Transactions on Communications, 50(7):1058--1061, 2002.
• 28: A. Willig, M. Kubisch, C. Hoene, and A. Wolisz. Measurements of a wireless link in an industrial environment using an ieee 802.11-compliant physical layer. IEEE Transaction on Industrial Electronics, 49(6), 2002.
• 29: Grace R. Woo , Pouya Kheradpour , Dawei Shen , Dina Katabi, Beyond the bits: cooperative packet recovery using physical layer information, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287871]
• 30: R. W. Yeung and N. Cai. Network error correction, part 1: Basic concepts and upper bounds. Communications in Information and Systems, 6(1):19--35, 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
cooperative diversity, network coding, wireless networks