Comparison between graph-based and interference-based STDMA scheduling

ABSTRACT

Spatial reuse TDMA is a fixed assignment access scheme for multi-hop radio networks. The idea is to increase network capacity by letting several radio terminals use the same time slot when the interferences caused are not too severe. We consider two methods of generating traffic controlled reuse schedules. One method uses full knolwedge of the interference environment to generate schedules. The other method uses a graph representation of the network, assuming limited knowledge of the interferences. By simulations, we evaluate the proposed methods in terms of average delay and throughput. The simulation results indicate that the network performance of the graph-based scheduling may suffer compared to the interference-based scheduling, depending on how the graph is created. In a stationary situation, or temporary stationary situation, where knowledge of the full interference environment can be assumed, interference based scheduling can improve the network capacity by up to one thrid, thereby being worth its increased complexity

REFERENCES

• 1: B. Asp, G. Eriksson, and P. Holm. Detvag-90 Final Report. Scientific Report FOA-R-97-00566-504-SE, Defence Research Est., Div. of Command and Control Warfare Tech. Linka oping, Sweden, Sept. 1997.
• 2: I. Chlamtac and A. Lerner. A link allocation protocol for mobile multi-hop radio networks. In GLOBECOM '85, IEEE Global Telecommunications Conference, Conference Record, volume 1, pages 238-242, 1985.
• 3: I. Chlamtac , S. S. Pinter, Distributed nodes organization algorithm for channel access in a multihop dynamic radio network, IEEE Transactions on Computers, v.36 n.6, p.728-737, June 1987 [doi>10.1109/TC.1987.1676965]
• 4: N. Funabiki and Y. Takefuji. A parallel algorithm for broadcast scheduling problems in packet radio networks. IEEE Trans. Commun., 41(6):828-831, 1993.
• 5: J. Gr~onkvist. Traffic controlled spatial reuse TDMA for multihop radio networks. In Personal, Indoor and Mobile Radio Communications, pages 1203-1207, 1998.
• 6: B. Hajek and G. Sasaki. Link scheduling in polynomial time. IEEE Trans. Inform. Theory., 34(5):910-917, sept 1988.
• 7: R. Nelson and L. Kleinrock. Spatial-TDMA: A collision-free multihop channel access protocol. IEEE Trans. Commun., 33(9):934-944, Sept. 1985.
• 8: C. G. Prohazka, Decoupling Link Scheduling Constraints in Multi-Hop Packet Radio Networks, IEEE Transactions on Computers, v.38 n.3, p.455-458, March 1989 [doi>10.1109/12.21132]
• 9: O. Somarriba. Multihop Packet Radio Systems in Rough Terrain. Tech.lic. thesis, Radio Communication Systems, Department of S3, Royal Institute of Technology, SE-100 44 Stockholm, Sweden, Oct. 1995.
• 10: J. Zander. Jamming in slotted ALOHA multihop packet radio networks. IEEE Trans. Commun., COM-39, Oct. 1991.

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:
  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.2 Graph Theory
          Subjects: Network problems

General Terms:
Design, Performance