The feasibility of matchings in a wireless network

ABSTRACT

The problem of determining what links can be simultaneously activated in a wireless network such that a signal-to-interference-and-noise (SINR) constraint is satisfied at all receivers is considered. The term "feasible matching" is introduced to describe a set of (transmitter, receiver) pairs for which there exists some set of transmit powers which can simultaneously meet the SINR equirements at the receivers. Given disjoint equally sized sets of transmitters and receivers, it is shown that when the SINR requirement at the receivers is greater than 1, no more than one feasible matching between the transmitters and the receivers exists. Sufficient conditions are provided under which certain broad classes of matchings in a network are guaranteed to be feasible; for example all matchings involving k or fewer links. The application of these results to ad hoc wireless networks and to scheduling is discussed.

REFERENCES

• 1: [1] R. D. Yates and C.-Y. Huang, "Integrated power control and base station assignment," IEEE Trans. Veh. Technol., vol. 44, no. 3, pp. 638-644, Aug. 1995.
• 2: [2] S. Grandhi, R. Vijayan, D. Goodman, and J. Zander, "Centralized power control in cellular radio systems," IEEE Trans. Veh. Technol., vol. 42, no. 4, p. 466, Nov. 1993.
• 3: [3] S. A. Grandhi, R. Vijayan, and D. J. Goodman, "Distributed power control in cellular radio systems," IEEE Trans. Commun., vol. 42, pp. 226-228, Feb. 1994.
• 4: [4] G. J. Foschini and Z.Miljanic, "A simple distributed autonomous power control algorithm and its convergence," IEEE Trans. Veh. Technol., vol. 42, no. 4, pp. 641-646, Nov. 1993.
• 5: [5] S. Grandhi, J. Zander, and R. Yates, "Constrained power control," Int. J. Wireless Pers. Commun., vol. 1, no. 4, 1995.
• 6: [6] S. A. Borbash and A. Ephremides, "Wireless link scheduling with power control," in Proc. WiOpt, 2004.
• 7: [7] S. A. Borbash, "Design Considerations in Wireless Sensor Networks," Ph.D. dissertation, Univ. Maryland, College Park, 2004.
• 8: [8] B. Hajek and G. Sasaki, "Link scheduling in polynomial time," IEEE Trans. Inf. Theory, vol. 34, no. 5, pp. 910-917, Sep. 1988.
• 9: [9] R. L. Cruz and A. V. Santhanam, "Optimal routing, link scheduling and power control in multi-hop wireless networks," in Proc. INFOCOM, 2003.
• 10: [10] H. Minc, Nonnegative Matrices. New York:Wiley Interscience, 1988.
• 11: [11] A. Berman and R. Plemmons, Nonnegative Matrices in the Mathematical Sciences. New York: Academic, 1979.
• 12: Roger A. Horn , Charles R. Johnson, Matrix analysis, Cambridge University Press, New York, NY, 1985
• 13: [13] R. Vahrenkamp, "Derivatives of the dominant root," Appl. Math. Comput., vol. 2, pp. 29-39, 1976.
• 14: [14] S. A. Borbash and A. Ephremides, "The feasibility of matchings in a wireless network," in Proc. Int. Symp. Inf. Theory, 2004.
• 15: [15] S. V. Hanly, "An algorithm for combined cell-site selection and power control to maximize cellular spread spectrum capacity," IEEE J. Sel. Areas Commun., vol. 13, no. 7, pp. 1332-1340, Sep. 1995.

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.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies; Modeling techniques; Performance attributes

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Design, Performance

Keywords:
feasibility, interference, matchings, power control, wireless networks