Link Scheduling in STDMA Wireless Networks: A Line Graph Approach

We consider point to point link scheduling in Spatial Time Division Multiple Access (STDMA) wireless networks under the physical interference model. We propose a novel link scheduling algorithm based on a line graph representation of the network, by embedding the interferences between pairs of nodes into the edge weights of the line graph. Our algorithm achieves lower schedule length and lower run time complexity than existing algorithms.

• Publication year

  2007

• Venue

  arXiv.org

• Publication date

  2007-12-11

• Fields of study

  Computer Science, Engineering

• Identifiers
  arXiv 0712.1662
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On High Spatial Reuse Link Scheduling in STDMA Wireless Ad Hoc Networks

  2007cited by this paper
• The Complexity of Connectivity in Wireless Networks

  2006cited by this paper
• Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks

  2006influential reference
• On High Spatial Reuse Broadcast Scheduling in STDMA Wireless Ad Hoc Networks

  2006cited by this paper
• Efficient interference-aware TDMA link scheduling for static wireless networks

  2006cited by this paper
• Joint Channel Assignment and Routing for Throughput Optimization in Multiradio Wireless Mesh Networks

  2005cited by this paper
• Impact of Interference on Multi-Hop Wireless Network Performance

  2003cited by this paper
• Outdoor IEEE 802.11 cellular networks: radio link performance

  2002cited by this paper
• The capacity of wireless networks

  2000cited by this paper
• Introduction to Graph Theory

  1995cited by this paper
• Scheduling algorithms for multihop radio networks

  1993cited by this paper
• Spatial TDMA: A Collision-Free Multihop Channel Access Protocol

  1985influential reference

• OLSR-aware channel access scheduling in wireless mesh networks

  2011cites this paper
• A Novel Approach for Scheduling in STDMA for High-Throughput Backbone Wireless Mesh Networks Operating within 60-80 GHz

  2010cites this paper
• Joint Routing, Channel Assignment, and Scheduling for Throughput Maximization in General Interference Models

  2010cites this paper
• Optimisation de la capacité des réseaux radio maillés

  2009cites this paper
• On Wireless Link Scheduling and Flow Control

  2008cites this paper