Throughput and stability of digital and analog network coding for wireless networks with single and multiple relays

ABSTRACT

We evaluate the throughput and stability properties of digital and analog network coding for wireless terminals exchanging broadcast traffic with the assistance of relay nodes. For stochastically varying traffic, the stable operation is compared under the different schemes of plain routing, and digital and analog network coding, at the packet and the signal levels, respectively. For each network coding scheme, the queue dynamics are specified for the terminal and relay nodes, and the maximum throughput region is optimized over all transmission schedules. We then give generalizations of the well-known back-pressure policy for each scheme, which accounts for the coupling of the queues due to network coding and is throughput optimal, i.e., it stabilizes the network whenever this is possible. Our initial analysis focuses on a network with a single relay node. We then discuss extensions of this to arbitrary terminal-relay configurations in a general multihop network. A general framework is established to construct the maximum throughput region and throughput optimal scheduling is jointly designed with network coding for relay networks with general channel rates. For any achievable rates in the maximum throughput region the dynamic scheduling and coding ensure that the average queue lengths at the terminal and relay nodes are asymptotically bounded.

REFERENCES

• 1: L. Tassiulas and A. Ephremides, "Stability Properties of Constrained Queueing Systems and Scheduling for Maximum Throughput in Multihop Radio Networks", IEEE Trans. Autom. Control, vol. 37, no. 12, pp. 1936--1949, Dec. 1992.
• 2: S. Sarkar and L. Tassiulas, "A Framework for Routing and Congestion Control for Multicast Information Flows", IEEE Trans. Inform. Theory, vol. 48, no. 10, pp. 2690--2708, Oct. 2002.
• 3: R. Ahlswede, N. Cai, S. -Y. R. Li, and R. W. Yeung, "Network Information Flow", IEEE Trans. Inform. Theory, vol. 46, no. 4, pp. 1204--1216, July 2000.
• 4: Sachin Katti , Shyamnath Gollakota , Dina Katabi, Embracing wireless interference: analog network coding, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 5: T. Ho and H. Viswanathan, "Dynamic Algorithms for Multicast with Intra-session Network Coding", Proc. Allerton Annual Conference on Communication, Control, and Computing, Monticello, IL, Sept. 2005.
• 6: Y. E. Sagduyu and A. Ephremides, "Cross-Layer Optimization of MAC and Network Coding in Wireless Queueing Tandem Networks", IEEE Trans. Inform. Theory, vol. 54, no. 2, pp. 554--571, Feb. 2008.
• 7: C.-C. Wang and N. B. Shroff, "On Wireless Network Scheduling with Intersession Network Coding", Proc. Conference on Information Sciences and Systems, Princeton, NJ, Mar. 2008.
• 8: T. J. Oechtering and H. Boche, "Stability Region of an Efficient Bidirectional Regenerative Half-duplex Relaying Protocol", Proc. IEEE Information Theory Workshop, Chengdu, China, Oct. 2006.
• 9: F. Xue, C.-H. Liu, and S. Sandhu, "MAC-Layer and PHY-Layer Network Coding for Two-Way Relaying: Achievable Rate Regions and Opportunistic Scheduling", Proc. Allerton Conference on Communication, Control and Computing, Monticello, IL, Sept. 2007.
• 10: Ertugrul N. Ciftcioglu, Aylin Yener, and Randall Berry, "Stability of Bi-Directional Cooperative Relay Networks", Proc. IEEE Information Theory Workshop, Porto, Portugal, May 2008.
• 11: A. Eryilmaz and D. S. Lun, "Control for Inter-session Network Coding", Proc. Workshop on Network Coding, Theory and Applications, San Diego, CA, Jan. 2007.
• 12: Y. E. Sagduyu, D. Guo, and R. Berry, "On the Delay and Throughput of Digital and Analog Network Coding for Wireless Broadcast", Proc. Conf. on Information Sciences and Systems, Princeton, NJ, Mar. 2008.
• 13: Y. E. Sagduyu, D. Guo, and R. Berry, "Throughput Optimal Control for Relay-Assisted Wireless Broadcast with Network Coding", Proc. The First IEEE International Workshop on Wireless Network Coding, San Francisco, CA, June, 2008.
• 14: L. Tassiulas and A. Ephremides, "Dynamic Server Allocation to Parallel Queues with Randomly Varying Connectivity", IEEE Trans. Inform. Theory, vol. 39, no. 2, pp. 466--478, Mar. 1993.
• 15: F. Xue and S. Sandhu, "PHY-Layer Network Coding for Broadcast Channel with Side Information", Proc. IEEE Information Theory Workshop, Lake Tahoe, CA, Sept. 2007.
• 16: Dimitri Bertsekas , Robert Gallager, Data networks (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 17: Leonidas Georgiadis , Michael J. Neely , Leandros Tassiulas, Resource allocation and cross-layer control in wireless networks, Foundations and Trends® in Networking, v.1 n.1, p.1-144, April 2006 [doi>10.1561/1300000001]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

General Terms:
Design, Performance, Reliability

Keywords:
analog network coding, digital network coding, queue stability, stable throughput region, throughput optimal control