Complexity of scheduling with analog network coding

ABSTRACT

In this paper we analyze the complexity of scheduling wireless links in the physical interference model with analog network coding capability. We study two models with different definitions of network coding. In one model, we assume that a receiver is able to decode several signals simultaneously, provided that these signals differ in strength significantly. In the second model, we assume that routers are able to forward the interfering signal of a pair of nodes that wish to exchange a message, and nodes are able to decode the "collided" message by subtracting their own contribution from the interfered signal. For each network coding definition, we construct an instance of the scheduling problem in the geometric SINR model, in which nodes are distributed in the Euclidean plane. We present NP-completeness proofs for both scenarios.

REFERENCES

• 1: R. Ahlswede, N. Cai, S. Y. R. Li, and R. W. Yeung. Network information flow. IEEE Trans. on Inf. Theory, 46(4):1204--1216, 2000.
• 2: Mainak Chatterjee , Haitao Lin , Sajal K. Das, Rate Allocation and Admission Control for Differentiated Services in CDMA Data Networks, IEEE Transactions on Mobile Computing, v.6 n.2, p.179-191, February 2007 [doi>10.1109/TMC.2007.29]
• 3: M. R. Garey and D. S. Johnson. Complexity results for multiprocessor scheduling under resource constraints. SIAM Journal on Computing, page 397, 1975.
• 4: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 5: Olga Goussevskaia , Yvonne Anne Oswald , Roger Wattenhofer, Complexity in geometric SINR, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1288107.1288122]
• 6: P. Gupta and P. R. Kumar. Critical Power for Asymptotic Connectivity in Wireless Networks. Stochastic Analysis, Control, Optimization and Applications, pages 547--566, 1998.
• 7: P. Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Trans. Inf. Theory, 46(2):388--404, 2000.
• 8: J. Hamkins. Joint viterbi algorithm to separate cochannel fm signals. In IEEE Int. Conf. Acoustics, Speech, Signal Processing, 1998.
• 9: J. Hamkins. An analytic technique to separate cochannel fm signals. IEEE Transactions on Communications, 48(4):543--546, 2000.
• 10: T. Ho, M. Medard, R. Koetter, D. R. Karger, M. Effros, J. Shi, and B. Leong. A random linear network coding approach to multicast. IEEE Trans. on Inf. Theory, 52(10):4413--4430, 2006.
• 11: Harry B. Hunt, III , Madhav V. Marathe , Venkatesh Radhakrishnan , S. S. Ravi , Daniel J. Rosenkrantz , Richard E. Stearns, NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs, Journal of Algorithms, v.26 n.2, p.238-274, feb. 1998 [doi>10.1006/jagm.1997.0903]
• 12: 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
• 13: 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
• 14: I. T. L. Kozat, U. C. Koutsopoulos. Cross-layer design for power efficiency and qos provisioning in multi-hop wireless networks. IEEE Trans. on Wireless Communications, 5, 2006.
• 15: Sven O. Krumke , Madhav V. Marathe , S. S. Ravi, Models and approximation algorithms for channel assignment in radio networks, Wireless Networks, v.7 n.6, p.575-584, November 2001 [doi>10.1023/A:1012311216333]
• 16: K. Leung and L. Wang. Integrated link adaptation and power control for wireless ip networks, 2000.
• 17: S. Y. R. Li, R. W. Yeung, and N. Cai. Linear network coding. Information Theory, IEEE Transactions on, 49(2):371--381, 2003.
• 18: T. Moscibroda, R. Wattenhofer, and Y. Weber. Protocol Design Beyond Graph-based Models. In HotNets, 2006.
• 19: Peter Sanders , Sebastian Egner , Ludo Tolhuizen, Polynomial time algorithms for network information flow, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777464]
• 20: Suresh Singh , C. S. Raghavendra, PAMAS—power aware multi-access protocol with signalling for ad hoc networks, ACM SIGCOMM Computer Communication Review, v.28 n.3, p.5-26, July 1998 [doi>10.1145/293927.293928]
• 21: Y. Wu. Broadcasting when receivers know some messages a priori. In IEEE Int. Symp. Inf. Theory, 2007.
• 22: Y. Wu, P. A. Chou, and S.-Y. Kung. Minimum-energy multicast in mobile ad hoc networks using network coding. IEEE Transactions on Communications, 53(11):1906--1918, 2005.
• 23: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

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

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory

General Terms:
Theory

Keywords:
analog network coding, complexity, geometric sinr, np-complete, physical interference model, scheduling, wireless ad-hoc networks