Exact and approximate link scheduling algorithms under the physical interference model

ABSTRACT

Given n arbitrarily distributed single-hop wireless links, using the physical interference model, the objective is to minimize the scheduling length. This is an open problem (Problem 1) proposed by Locher et al. [21]. In this paper, we solve this open problem at the cost of moderately exponential time. Specifically, this paper gives two classes of exact and approximate link scheduling algorithms, one based on the somewhat straightforward link independent set covering, and the other on counting the number of set covers. Let p(n) denote the time of checking whether the spectral radius of an irreducible non-negative matrix is smaller than 1 or not, then the time complexity for the set covering based exact algorithm is O(2^C(n,n/2)), whereas the proposed counting based exact scheduling algorithm called ESA_MLSAT needs only time O(3ⁿ*n*(logn)²*p(n)) with polynomial space. If exponential space is allowed, the time complexity can be further reduced to O(2ⁿ*n*(logn)²*p(n)). The time complexity for the set covering based approximate algorithm is O(C(n,n/2)*logn*p(n)) with approximation ratio O(logn). The time complexity of the first counting based approximation algorithm is O(n²*polylog(n)) with approximation ratio O(n/logn), the time complexity of the second counting based approximation algorithm is O(n^{(1+log3*(logn)(k-1)})*polylog(n)) with approximation ratio O(n/(logn)^k), and the time complexity of the third counting based approximate algorithm is O((C(n,n/2)+3^{(e(-epsilon)*n)*n*logn)*logn*p(n)}) with approximation ratio ceiling function of (1+epsilon). All these approximation algorithms use polynomial space.

REFERENCES

• 1: Michael Andersin , Zvi Rosberg , Jens Zander, Gradual removals in cellular PCS with constrained power control and noise, Wireless Networks, v.2 n.1, p.27-43, Jan. 1996 [doi>10.1007/BF01201460]
• 2: A. Behzad and I. Rubin. Optimum Integrated Link Scheduling and Power Control for Multihop Wireless Networks. IEEE Transactions on Vehicular Technology, 56(1):194--205, 2007.
• 3: Andreas Björklund , Thore Husfeldt , Petteri Kaski , Mikko Koivisto, Fourier meets möbius: fast subset convolution, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250801]
• 4: Andreas Bjorklund , Thore Husfeldt, Inclusion--Exclusion Algorithms for Counting Set Partitions, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.575-582, October 21-24, 2006 [doi>10.1109/FOCS.2006.41]
• 5: A. Björklund, T. Husfeldt, and M. Koivisto. Set Partitioning via Inclusion-Exclusion. SIAM Journal on Computing, to appear.
• 6: S. A. Borbash and A. Ephremides. Wireless Link Scheduling With Power Control and SINR Constraints. IEEE Transactions on Information Theory, 52(11): 5106--5111, 2006.
• 7: Gurashish Brar , Douglas M. Blough , Paolo Santi, Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161092]
• 8: Massimiliano Caramia , Paolo Dell'olmo, Constraint Propagation in Graph Coloring, Journal of Heuristics, v.8 n.1, p.83-107, January 2002 [doi>10.1023/A:1013665718444]
• 9: D. Chafekar, V. S. A. Kumar, M. V. Marathe, S. Parthasarathy and A. Srinivasan. Approximation Algorithms for Computing Capacity of Wireless Networks with SINR Constraints. In Proc. 27th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), Phoenix, AZ, US, April 2008.
• 10: Deepti Chafekar , V.S. Anil Kumar , Madhav V. Marathe , Srinivasan Parthasarathy , Aravind Srinivasan, Cross-layer latency minimization in wireless networks with SINR constraints, 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.1288123]
• 11: T. ElBatt and A. Ephremides. Joint Scheduling and Power Control for Wireless Ad-hoc Networks. In Proc. INFOCOM, New York, US, June 2002.
• 12: Thomas Erlebach , Klaus Jansen , Eike Seidel, Polynomial-Time Approximation Schemes for Geometric Intersection Graphs, SIAM Journal on Computing, v.34 n.6, p.1302-1323, 2005 [doi>10.1137/S0097539702402676]
• 13: Fedor V. Fomin , Fabrizio Grandoni , Dieter Kratsch, Measure and conquer: a simple O(2^0.288n) independent set algorithm, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.18-25, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109560]
• 14: Martin Fürer , Shiva Prasad Kasiviswanathan, Algorithms for Counting 2-Sat Solutions and Colorings with Applications, Proceedings of the 3rd international conference on Algorithmic Aspects in Information and Management, June 06-08, 2007, Portland, OR, USA [doi>10.1007/978-3-540-72870-2_5]
• 15: 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]
• 16: Piyush Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Transactions on Information Theory, 46(2):388--404, 2000.
• 17: B.E. Hajek and G.H. Sasaki. Link Scheduling in Polynomial Time. IEEE Transactions on Information Theory, 34(5): 910--917, 1988.
• 18: Qiang-Sheng Hua , Francis C. M. Lau, The scheduling and energy complexity of strong connectivity in ultra-wideband networks, Proceedings of the 9th ACM international symposium on Modeling analysis and simulation of wireless and mobile systems, October 02-06, 2006, Terromolinos, Spain [doi>10.1145/1164717.1164767]
• 19: Q.-S. Hua and F.C.M. Lau. Balancing the Scheduling and Energy Complexities in Wireless Networks. Submitted to MSWiM'08.
• 20: Mikko Koivisto, An O*(2^n ) Algorithm for Graph Coloring and Other Partitioning Problems via Inclusion--Exclusion, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.583-590, October 21-24, 2006 [doi>10.1109/FOCS.2006.11]
• 21: T. Locher, P. von Rickenbach, and R. Wattenhofer. Sensor Networks Continue to Puzzle: Selected Open Problems (Invited paper). In Proc. 9th International Conference on Distributed Computing and Networking (ICDCN), Kolkata, India, Jan. 2008.
• 22: J.W. Moon and L. Moser. On Cliques in Graphs. Israel Journal of Mathematics, Vol. 3, pp. 23--28, 1965.
• 23: T. Moscibroda, Y. A. Oswald, and R. Wattenhofer. How Optimal are Wireless Scheduling Protocols? In Proc. INFOCOM, Anchorage, Alaska, US, May 2007.
• 24: Thomas Moscibroda, The worst-case capacity of wireless sensor networks, Proceedings of the 6th international conference on Information processing in sensor networks, April 25-27, 2007, Cambridge, Massachusetts, USA [doi>10.1145/1236360.1236362]
• 25: T. Moscibroda, R. Wattenhofer, and Y. Weber. Protocol Design Beyond Graph-Based Models. In Proc. 5th Workshop on Hot Topics in Networks (HotNets), Irvine, California, US, Nov. 2006.
• 26: T. Moscibroda and R. Wattenhofer. The Complexity of Connectivity in Wireless Networks. In Proc. INFOCOM, Barcelona, Spain, April 2006.
• 27: Thomas Moscibroda , Roger Wattenhofer , Aaron Zollinger, Topology control meets SINR: the scheduling complexity of arbitrary topologies, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132939]
• 28: S. U. Pillai, T. Suel, and S. Cha. The Perron-Frobenius Theorem and Some of its Applications. IEEE Signal Processing Magazine, 22(2):62--75, 2005.
• 29: Christian Scheideler , Andrea Richa , Paolo Santi, An O(log n) dominating set protocol for wireless ad-hoc networks under the physical interference model, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China [doi>10.1145/1374618.1374632]
• 30: Gaurav Sharma , Ravi R. Mazumdar , Ness B. Shroff, On the complexity of scheduling in wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161116]
• 31: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 32: R. J. Wood and M. J. O'Neill. An Always Convergent Method for Finding the Spectral Radius of an Irreducible Non--Negative Matrix. The ANZIAM Journal, V45:C474-C485, 2004.
• 33: J. Zander. Performance of Optimum Transmitter Power Control in Cellular Radio Systems. IEEE Transactions on Vehicular Technology, 41(1):57--62, 1992.

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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

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

General Terms:
Algorithms, Theory

Keywords:
ad hoc networks, coloring, constraint satisfaction problem., counting, inclusion-exclusion principle, link scheduling, physical interference model, sensor networks, sinr, wireless