skip to main content
10.1145/1132905.1132939acmconferencesArticle/Chapter ViewAbstractPublication PagesmobihocConference Proceedingsconference-collections
Article

Topology control meets SINR: the scheduling complexity of arbitrary topologies

Published: 22 May 2006 Publication History

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]
D. M. Blough, M. Leoncini, G. Resta, and P. Santi. The K-Neigh Protocol for Symmetric Topology Control in Ad Hoc Networks. In Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing (MOBIHOC) pages 141--152,2003.
[5]
P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia. Routing with Guaranteed Delivery in Ad Hoc Wireless Networks.In Proc. of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM) pages 48--55, 1999.
[6]
M. Burkhart, P. von Rickenbach, R. Wattenhofer, and A. Zollinger. Does Topology Control Reduce Interference? In Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC)pages 9--19, 2004.
[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]
J.Grönkvist and A. Hansson. Comparison Between Graph-Based and Interference-Based STDMA Scheduling. In Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking & Computing (MOBIHOC)pages 255--258, 2001.
[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]
K. Jain, J. Padhye, V. Padmanabhan, and L. Qiu. Impact of Interference on Multi-hop Wireless Network Performance.In Proc. of the 9 th Annual International Conference on Mobile Computing and Networking (MOBICOM)2003.
[17]
F. Kuhn, R. Wattenhofer, Y. Zhang, and A. Zollinger. Geometric Routing:Of Theory and Practice. In Proc. of the 22nd ACM Symposium on the Principles of Distributed Computing (PODC)2003.
[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]
X.-Y. Li, W.-Z. Song, and W. Wang. A Unified Energy Efficient Topology for Unicast and Broadcast. In Proceedings of the 11th International Conference on Mobile Computing and Networking (MOBICOM) 2005.
[21]
F. Meyer auf der Heide, C. Schindelhauer, K. Volbert, and M.Grünewald. Energy, Congestion and Dilation in Radio Networks.In Proceedings of the 14th ACM Symposium on Parallel Algorithms and Architectures (SPAA)pages 230--237, 2002.
[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]
T. Moscibroda and R. Wattenhofer. Coloring Unstructured Radio Networks.In Proceedings of the 17th Symposium on Parallel Algorithms and Architectures (SPAA)pages 39--48, 2005.
[24]
T. Moscibroda and R. Wattenhofer. Minimizing Interference in Ad Hoc and Sensor Networks. In Proc. of the International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM)pages 24--33, 2005.
[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]
R. Prakash. Unidirectional Links Prove Costly in Wireless Ad-Hoc Networks.In Proc. of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL-M)1999.
[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 and E. L. Lloyd. Scheduling Algorithms for Multi-Hop Radio Networks. In Proceedings on Communications Architectures and Protocols (SIGCOMM)pages 211--222, 1992.
[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.

Cited By

View all
  • (2024)CORA: Cooperative Communication and Optimal Resource Allocation in Multihop Wireless Multimedia Sensor NetworksIEEE Internet of Things Journal10.1109/JIOT.2023.330077411:3(4076-4084)Online publication date: 1-Feb-2024
  • (2023)A genetic scheduling strategy with spatial reuse for dense wireless networksInternational Journal of Hybrid Intelligent Systems10.3233/HIS-230015(1-15)Online publication date: 11-Jul-2023
  • (2023)Data aggregation protocols for WSN and IoT applications – A comprehensive surveyJournal of King Saud University - Computer and Information Sciences10.1016/j.jksuci.2023.01.00835:2(651-681)Online publication date: 1-Feb-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
MobiHoc '06: Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing
May 2006
378 pages
ISBN:1595933689
DOI:10.1145/1132905
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 May 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. algorithmic analysis
  2. interference
  3. scheduling complexity
  4. topology control
  5. wireless ad hoc networks

Qualifiers

  • Article

Conference

MobiHoc06
Sponsor:

Acceptance Rates

Overall Acceptance Rate 296 of 1,843 submissions, 16%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)9
  • Downloads (Last 6 weeks)1
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)CORA: Cooperative Communication and Optimal Resource Allocation in Multihop Wireless Multimedia Sensor NetworksIEEE Internet of Things Journal10.1109/JIOT.2023.330077411:3(4076-4084)Online publication date: 1-Feb-2024
  • (2023)A genetic scheduling strategy with spatial reuse for dense wireless networksInternational Journal of Hybrid Intelligent Systems10.3233/HIS-230015(1-15)Online publication date: 11-Jul-2023
  • (2023)Data aggregation protocols for WSN and IoT applications – A comprehensive surveyJournal of King Saud University - Computer and Information Sciences10.1016/j.jksuci.2023.01.00835:2(651-681)Online publication date: 1-Feb-2023
  • (2021)Network Design under General Wireless InterferenceAlgorithmica10.1007/s00453-021-00866-zOnline publication date: 10-Aug-2021
  • (2020)Median Access Control Protocols for Sensor Data Collection: A ReviewIEEE Access10.1109/ACCESS.2020.30193928(160078-160098)Online publication date: 2020
  • (2019)Distributed Link Scheduling Algorithm Based on Successive Interference Cancellation in MIMO Wireless NetworksWireless Communications & Mobile Computing10.1155/2019/90832822019Online publication date: 19-Jun-2019
  • (2019)Simulated versus reduced noise quantum annealing in maximum independent set solution to wireless network schedulingQuantum Information Processing10.1007/s11128-018-2117-118:1(1-25)Online publication date: 1-Jan-2019
  • (2019)Wireless Network AlgorithmicsComputing and Software Science10.1007/978-3-319-91908-9_9(141-160)Online publication date: 2019
  • (2018)Characterizing Data Deliverability of Greedy Routing in Wireless Sensor NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2017.273700517:3(543-559)Online publication date: 1-Mar-2018
  • (2018)Wireless Aggregation at Nearly Constant Rate2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS.2018.00078(753-763)Online publication date: Jul-2018
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media