skip to main content
10.1145/144179.144283acmconferencesArticle/Chapter ViewAbstractPublication PagescommConference Proceedingsconference-collections
Article
Free Access

Scheduling algorithms for multi-hop radio networks

Published:01 October 1992Publication History

ABSTRACT

New algorithms for transmission scheduling in multihop broadcast radio networks are presented. Both link scheduling and broadcast scheduling are considered. In each instance scheduling algorithms are given that improve upon existing algorithms both theoretically and experimentally. Theoretically, it is shown that tree networks can be scheduled optimally, and that arbitrary networks can be scheduled so that the schedule is bounded by a length that is proportional to a function of the network thickness times the optimum. Previous algorithms could guarantee only that the schedules were bounded by a length no worse than the maximum node degree, the algorithms presented here represent a considerable theoretical improvement. Experimentally, a realistic model of a radio network is given and the performance of the new algorithms is studied. These results show that, for both types of scheduling, the new algorithms (experimentally) perform consistently better than earlier methods.

References

  1. Ari84.E. Arikan. Some complexity results about packet radio networks. IEEE Transactions on Inform. Theory, vol iT-30, pages 910-918, Jul 1984.Google ScholarGoogle Scholar
  2. BG87.D. Bertsekas and R. Gallager. Data Networks. Prentice-Hall Inc., 1987. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. BM76.J.A. Bondy and U. S. R. Murty. Graph Theory with Applications. American Elsevier Publishing Co. inc., New York, 1976. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. Bol85.B. Bollobas. Random Graphs. Academic Press Inc., London, 1985.Google ScholarGoogle Scholar
  5. BYII89.R. Bar-Yehuda, A. Israeli, and A. itai. Multiple communication in multi-hop radio networks. In Proc. Eighth Annual A CM Symposium on Princ. Distrib. Comput., pages 329- 338, 1989. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. CL85.I. Chlamtac and S. Lerner. A link allocation protocol for mobile multi-hop radio networks. In Proc. Globecom, Dec. 1985.Google ScholarGoogle Scholar
  7. CLR90.T.H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. McGraw- Hill Book Co., 1990. Google ScholarGoogle ScholarDigital LibraryDigital Library
  8. CS85.I. Chlamtac and S.Kutten. A spatial reuse tdma/fdma for mobile multi-hop radio networks. In INFOCOM conference proceedings, March 1985.Google ScholarGoogle Scholar
  9. EGMT84.S. Even, O. Goldreich, S. Moran, and P. Tong. On the NP-completeness of certain network testing problems. Networks, vol. 1~, pages 1- 24, 1984.Google ScholarGoogle Scholar
  10. ET88.A. Ephremedis and T. Truong. A distributed algorithm for efficient and interference free broadcasting in radio networks. In Proceedings of the INFOCOM, 1988.Google ScholarGoogle ScholarCross RefCross Ref
  11. EWB87.A. Ephremedis, J.E. Wieselthier, and D.J. Baker. A design concept for reliable mobile radio networks with frequency hopping signalling, in Proceedings of the IEEE vol 75, No. 1, pages 56-73, Jan 1987.Google ScholarGoogle Scholar
  12. FT87.M.L. Fredman and R. E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the A CM vol. 3J, no. 3, pages 596-615, 1987. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. GJ79.M.R. Garey and D. S. Johnson. Computers and Intractability: A guide to the theory of NP-completeness. W. H. Freeman, San Fransicisco, 1979. Google ScholarGoogle ScholarDigital LibraryDigital Library
  14. GW88.H.N. Gabow and H. H. Westermann. Forests, frames and games: Algorithms for matroid sums and applications. In Proc. 20th Annual A CM Symposium on Theory of Comp., pages 407-421, 1988. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. Joh.D.S. Johnson. The np completeness column. Journal of Algorithms. (Appears periodically from 1981). Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. Law76.E.L. Lawler. Combinatorial Optimization. Holt and Reinhardt and Winston, New York, 1976.Google ScholarGoogle Scholar
  17. LNT87.B.M. Leiner, D.L. Nielson, and F.A. Tobagi. Issues in packet radio network design. In Proceedings of the IEEE, vol. 75, No. 1, Jan 1987.Google ScholarGoogle Scholar
  18. LR92a.E.L. Lloyd and S. Ramanathan. On the complexity of distance-2 coloring. In Proc. Jth International Conference on Computing and Information, May 1992. (To appear). Google ScholarGoogle ScholarDigital LibraryDigital Library
  19. LR92b.E.L. Lloyd and S. Ramanathan. On the complexity of link scheduling in multi-hop radio networks. In Proc. 26th Conference on Information Sciences and Systems, Mar 1992. (To appear).Google ScholarGoogle Scholar
  20. Man83.A. Mansfield. Determining the thickness of graphs is np-hard. Math. Proc. Cambridge Philos. Society, Vol. 93, pages 9-23, 1983.Google ScholarGoogle Scholar
  21. MMI72.D.W. Matula, G. Marble, and J. F. Issacson. Graph coloring algorithms, in Graph Theory and Computing, Academic Press NY, 1972.Google ScholarGoogle Scholar
  22. NW61.C. St. J. A. Nash-Williams. Edge-disjoint spanning trees of finite graphs. J. London Math. Soc., 36, pages 213-228, 1961.Google ScholarGoogle Scholar
  23. Ogi86.R. Ogier. 'A decomposition method for optimal scheduling. In Proc. ~dth Allerton Conference, Oct 1986.Google ScholarGoogle Scholar
  24. RL92a.S. Ramanathan and E. L. Lloyd. An algorithmic study of certain broadcast network problems. Technical Report 92-19, Dept. of Computer Science, University of Delaware, 1992.Google ScholarGoogle Scholar
  25. RL92b.S. Ramanathan and E. L. Lloyd. Complexity of certain graph coloring problems with applications to radio networks. Technical Report 92-18, Dept. of Computer Science, University of Delaware, 1992.Google ScholarGoogle Scholar
  26. RP89.R. Ramaswami and K. K. Parhi. Distributed scheduling of broadcasts in a radio network. In Proceedings of the INFOCOM, 1989.Google ScholarGoogle ScholarCross RefCross Ref
  27. Tan88.A.S. Tanenbaum. Computer Networks. Prentice-HM1 international Inc., Englewood Cliffs, 2 edition, 1988. Google ScholarGoogle ScholarDigital LibraryDigital Library
  28. Wig83.A. Wigderson. Improving the performance guarantee for approximate graph coloring. J. A CM, vol. 30, No. ,i, pages 729-735, Oct 1983. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Scheduling algorithms for multi-hop radio networks

                  Recommendations

                  Comments

                  Login options

                  Check if you have access through your login credentials or your institution to get full access on this article.

                  Sign in
                  • Published in

                    cover image ACM Conferences
                    SIGCOMM '92: Conference proceedings on Communications architectures & protocols
                    October 1992
                    326 pages
                    ISBN:0897915259
                    DOI:10.1145/144179

                    Copyright © 1992 ACM

                    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]

                    Publisher

                    Association for Computing Machinery

                    New York, NY, United States

                    Publication History

                    • Published: 1 October 1992

                    Permissions

                    Request permissions about this article.

                    Request Permissions

                    Check for updates

                    Qualifiers

                    • Article

                    Acceptance Rates

                    Overall Acceptance Rate554of3,547submissions,16%

                  PDF Format

                  View or Download as a PDF file.

                  PDF

                  eReader

                  View online with eReader.

                  eReader