Adaptive network coding and scheduling for maximizing throughput in wireless networks

ABSTRACT

Recently, network coding emerged as a promising technology that can provide significant improvements in throughput and energy efficiency of wireless networks, even for unicast communication. Often, network coding schemes are designed as an autonomous layer, independent of the underlying Phy and MAC capabilities and algorithms.Consequently, these schemes are greedy, in the sense that all opportunities of broadcasting combinations of packets are exploited. We demonstrate that this greedy design principle may in fact reduce the network throughput. This begets the need for adaptive network coding schemes. We further show that designing appropriate MAC scheduling algorithms is critical for achieving the throughput gainsexpected from network coding. In this paper, we propose a general framework to develop optimal and adaptive joint network coding and scheduling schemes. Optimality is shown for various Phy and MAC constraints. We apply this framework to two different network coding architectures: COPE, a scheme recently proposed in [7], and XOR-Sym, a new scheme we present here. XOR-Sym is designed to achieve a lower implementation complexity than that of COPE, and yet to provide similar throughput gains.

REFERENCES

• 1: R. Ahlswede, N. Cai, S. Li, and R. Yeung. Network information flow. IEEE Trans. on Information Theory, 46(4):1204--1216, 2000.
• 2: Andrew Brzezinski , Gil Zussman , Eytan Modiano, Enabling distributed throughput maximization in wireless mesh networks: a partitioning approach, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161094]
• 3: P. Chaporkar and S. Sarkar. Stable scheduling policies for maximizing throughput in generalized constrained queueing. In Proc. of IEEE Infocom, 2006.
• 4: A. Gupta, X. Lin, and R. Srikant. Low-complexity distributed scheduling algorithms for wireless networks. In 26th IEEE International Conference on Computer Communications(INFOCOM'07), pages 1631--1639, May 2007.
• 5: P. Gupta and P. R. Kumar. The capacity of wireless networks. IEEE Trans. on Information Theory, 46(2):388--404, 2000.
• 6: T. Ho and R. Koetter. Online incremental network coding for multiple unicasts. In Proc. of DIMACS Working Group on Network Coding, 2005.
• 7: 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
• 8: S.-Y. R. Li, R. W. Yeung, and N. Cai. Linear network coding. IEEE Trans. on Information Theory, 49(2):371--381, 2003.
• 9: Z. Li and B. Li. Network coding: The case of multiple unicast sessions. In Proc. of Allerton Conference, 2004.
• 10: Xiaojun Lin , Ness B. Shroff, The impact of imperfect scheduling on cross-layer congestion control in wireless networks, IEEE/ACM Transactions on Networking (TON), v.14 n.2, p.302-315, April 2006 [doi>10.1109/TENT.2006.872546]
• 11: J. Liu, D. Goeckel, and D. Towsley. Bounds of the gain of network coding and broadcasting in wireless networks. In Proc. of IEEE Infocom, 2007.
• 12: D. S. Lun, N. Ratnakar, R. Koetter, M. Medard, E. Ahmed, and H. Lee. Achieving minimum-cost multicast: A decentralized approach based on network coding. In Proc. of IEEE Infocom, 2005.
• 13: Eytan Modiano , Devavrat Shah , Gil Zussman, Maximizing throughput in wireless networks via gossiping, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 14: M. Neely. Energy optimal control for time varying wireless networks. In IEEE Infocom, 2005.
• 15: A. Ramamoorthy, J. Shi, and R. Wesel. On the capacity of network coding for random networks. IEEE Trans. on Information Theory, 51(8):2878--2885, 2005.
• 16: Y. E. Sagduyu and A. Ephremides. Network coding in wireless queueing networks: Tandem network case. In Proc. of IEEE ISIT, 2006.
• 17: Y. E. Sagduyu and A. Ephremides. Some optimization trade-offs in wireless network coding. In Proc. of CISS, 2006.
• 18: Sujay Sanghavi , Loc Bui , R. Srikant, Distributed link scheduling with constant overhead, Proceedings of the 2007 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 12-16, 2007, San Diego, California, USA
• 19: S. Sengupta, S. Rayanchu, and S. Banerjee. An analysis of wireless network coding for unicast sessions: The case for coding-aware routing. In Proc. of IEEE Infocom, 2007.
• 20: Alexander L. Stolyar, Maximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual Algorithm, Queueing Systems: Theory and Applications, v.50 n.4, p.401-457, August 2005 [doi>10.1007/s11134-005-1450-0]
• 21: L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multi-hop radio networks. IEEE Trans. on Automatic Control, 37(12):1936--1949, 1992.
• 22: Y. Wu, P. A. Chou, and S.-Y. Kung. Information exchange in wireless networks with network coding and physical-layer broadcast. Technical Report MSR-TR-2004-78, Microsoft Research, 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design, Performance

Keywords:
multi-hop wireless networks, network coding, throughput optimality