Topology control meets SINR: the scheduling complexity of arbitrary topologies

ABSTRACT

To date, topology control in wireless ad hoc and sensor networks--the study of how to compute from the given communication network a subgraph with certain beneficial properties .has been considered as a static problem only; the time required to actually schedule the links of a computed topology without message collision was generally ignored. In this paper we analyze topology control in the context of the physical Signal-to-Interference-plus-Noise-Ratio (SINR) model, focusing on the question of how and how fast the links of a resulting topology can actually be realized over time.For this purpose, we define and study a generalized version of the SINR model and obtain theoretical upper bounds on the scheduling complexity of arbitrary topologies in wireless networks. Specifically, we prove that even in worst-case networks, if the signals are transmitted with correctly assigned transmission power levels, the number of time slots required to successfully schedule all links of an arbitrary topology is proportional to the squared logarithm of the number of network nodes times a previously defined static interference measure Interestingly, although originally considered without explicit accounting for signal collision in the SINR model, this static interference measure plays an important role in the analysis of link scheduling with physical link interference. Our result thus bridges the gap between static graph-based interference models and the physical SINR model. Based on these results, we also show that when it comes to scheduling, requiring the communication links to be symmetric may imply significantly higher costs as opposed to topologies allowing unidirectional links.

REFERENCES

• 1: A.Behzad and I.Rubin.On the Performance of Graph-based Scheduling Algorithms for Packet Radio Networks. In Proceedings of the IEEE Global Tel ecommunications Conference (GLOBECOM) pages 3432--3436, 2003.
• 2: A. Behzad and I. Rubin. Impact of Power Control on the Performance of Ad Hoc Wireless Networks. In Proceedings of the 24 th Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)2005.
• 3: P.Björklund,P.Värbrand,and D. Yuan. A Column Generation Method for Spatial TDMA Scheduling in Ad Hoc Networks. Ad Hoc Networks 2(4):405--418, 2004.
• 4: Douglas M. Blough , Mauro Leoncini , Giovanni Resta , Paolo Santi, The lit K-neigh protocol for symmetric topology control in ad hoc networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778433]
• 5: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.48-55, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313282]
• 6: Martin Burkhart , Pascal von Rickenbach , Roger Wattenhofer , Aaron Zollinger, Does topology control reduce interference?, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989462]
• 7: R. Cruz and A. Santhanam. Optimal Routing, Link Scheduling, and Power Control in Multi-hop Wireless Networks. In Proc. of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)2003.
• 8: T. ElBatt and A. Ephremides. Joint Scheduling and Power Control for Wireless Ad-hoc Networks. In Proc. of the 21 st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)2002.
• 9: A.Ephremides and T.Truong.Scheduling Broadcasts in Multihop Radio Networks.IEEE Transactions on Communications 38: 456--460, 1990.
• 10: M. Fussen, R. Wattenhofer,and A. Zollinger. Interference Arises at the Receiver. In Proc. of the International Conference on Wireless Networks, Communications, and Mobile Computing(WirelessCom) June 2005.
• 11: J. Grönkvist.Interference-Based Scheduling in Spatial Reuse TDMA PhD thesis,Royal Institute of Technology, Stockholm, Sweden, 2005.
• 12: Jimmi Grönkvist , Anders Hansson, Comparison between graph-based and interference-based STDMA scheduling, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501449.501453]
• 13: P. Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Trans. Information Theory 46(2): 388--404,2000.
• 14: T. Hou and V. Li. Transmission Range Control in Multihop Packet Radio Networks.IEEE Transactions on Communications 34(1): 38--44, 1986.
• 15: L. Hu. Topology Control for Multihop Packet Radio Networks. IEEE Trans. on Communications 41(10), 1993.
• 16: Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938993]
• 17: Fabian Kuhn , Roger Wattenhofer , Yan Zhang , Aaron Zollinger, Geometric ad-hoc routing: of theory and practice, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.63-72, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872044]
• 18: N. Li, C.-J. Hou, and L. Sha. Design and Analysis of an MST-Based Topology Control Algorithm. In Proc. of the 22 nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)2003.
• 19: X.-Y. Li, G. Calinescu, and P.-J. Wan. Distributed Construction of Planar Spanner and Routing for Ad Hoc Wireless Networks. In Proc. of the 21 st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)2002.
• 20: Xiang-Yang Li , Wen-Zhan Song , Weizhao Wang, A unified energy-efficient topology for unicast and broadcast, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080831]
• 21: Friedhelm Meyer auf de Heide , Christian Schindelhauer , Klaus Volbert , Matthias Grünewald, Energy, congestion and dilation in radio networks, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564910]
• 22: K. Moaveni-Nejad and X.-Y. Li. Low-Interference Topology Control for Wireless Ad Hoc Networks. In Proc. of the 2nd IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON)Santa Clara,California, USA, 2005.
• 23: Thomas Moscibroda , Roger Wattenhofer, Coloring unstructured radio networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073977]
• 24: Thomas Moscibroda , Roger Wattenhofer, Minimizing interference in ad hoc and sensor networks, Proceedings of the 2005 joint workshop on Foundations of mobile computing, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080810.1080816]
• 25: T. Moscibroda and R. Wattenhofer. The Complexity of Connectivity in Wireless Networks. In Proc. of the 25th Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)2006.
• 26: Ravi Prakash, Unidirectional links prove costly in wireless ad hoc networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.15-22, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313263]
• 27: R. Ramanathan and R. Rosales-Hain. Topology Control of Multihop Wireless Networks Using Transmit Power Adjustment.In Proc. of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)2000.
• 28: S. Ramanathan , Errol L. Lloyd, Scheduling algorithms for multi-hop radio networks, Conference proceedings on Communications architectures & protocols, p.211-222, August 17-20, 1992, Baltimore, Maryland, United States
• 29: V. Rodoplu and T. H. Meng. Minimum Energy Mobile Wireless Networks. IEEE J. Selected Areas in Communications 17(8), 1999.
• 30: P. Santi. Topology Control in Wireless Ad Hoc and Sensor Networks Wiley,2005.
• 31: H. Takagi and L. Kleinrock. Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals. IEEE Transactions on Communications 32(3):246--257, 1984.
• 32: P. von Rickenbach, S. Schmid, R. Wattenhofer, and A. Zollinger. A Robust Interference Model for Wireless Ad-Hoc Networks.In Proc. of the 5th Int. Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN)Denver,Colorado, USA,April 2005.
• 33: R. Wattenhofer, L. Li, P. Bahl, and Y.-M. Wang. Distributed Topology Control for Power Efficient Operation in Multihop Wireless Ad Hoc Networks. In Proceedings of the 20th Joint Conference of the IEEE Computer and Communications Societies (INFOCOM)2001.
• 34: R. Wattenhofer and A. Zollinger. XTC: A Practical Topology Control Algorithm for Ad-Hoc Networks. In Proc. of the 4 th Int. Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN)Santa Fe, New Mexico, USA, April 2004.

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Theory

Keywords:
algorithmic analysis, interference, scheduling complexity, topology control, wireless ad hoc networks