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.
- Ari84.E. Arikan. Some complexity results about packet radio networks. IEEE Transactions on Inform. Theory, vol iT-30, pages 910-918, Jul 1984.Google Scholar
- BG87.D. Bertsekas and R. Gallager. Data Networks. Prentice-Hall Inc., 1987. Google ScholarDigital Library
- BM76.J.A. Bondy and U. S. R. Murty. Graph Theory with Applications. American Elsevier Publishing Co. inc., New York, 1976. Google ScholarDigital Library
- Bol85.B. Bollobas. Random Graphs. Academic Press Inc., London, 1985.Google Scholar
- 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 ScholarDigital Library
- CL85.I. Chlamtac and S. Lerner. A link allocation protocol for mobile multi-hop radio networks. In Proc. Globecom, Dec. 1985.Google Scholar
- CLR90.T.H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. McGraw- Hill Book Co., 1990. Google ScholarDigital Library
- CS85.I. Chlamtac and S.Kutten. A spatial reuse tdma/fdma for mobile multi-hop radio networks. In INFOCOM conference proceedings, March 1985.Google Scholar
- 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 Scholar
- 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 ScholarCross Ref
- 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 Scholar
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- Joh.D.S. Johnson. The np completeness column. Journal of Algorithms. (Appears periodically from 1981). Google ScholarDigital Library
- Law76.E.L. Lawler. Combinatorial Optimization. Holt and Reinhardt and Winston, New York, 1976.Google Scholar
- 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 Scholar
- 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 ScholarDigital Library
- 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 Scholar
- Man83.A. Mansfield. Determining the thickness of graphs is np-hard. Math. Proc. Cambridge Philos. Society, Vol. 93, pages 9-23, 1983.Google Scholar
- MMI72.D.W. Matula, G. Marble, and J. F. Issacson. Graph coloring algorithms, in Graph Theory and Computing, Academic Press NY, 1972.Google Scholar
- NW61.C. St. J. A. Nash-Williams. Edge-disjoint spanning trees of finite graphs. J. London Math. Soc., 36, pages 213-228, 1961.Google Scholar
- Ogi86.R. Ogier. 'A decomposition method for optimal scheduling. In Proc. ~dth Allerton Conference, Oct 1986.Google Scholar
- 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 Scholar
- 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 Scholar
- RP89.R. Ramaswami and K. K. Parhi. Distributed scheduling of broadcasts in a radio network. In Proceedings of the INFOCOM, 1989.Google ScholarCross Ref
- Tan88.A.S. Tanenbaum. Computer Networks. Prentice-HM1 international Inc., Englewood Cliffs, 2 edition, 1988. Google ScholarDigital Library
- Wig83.A. Wigderson. Improving the performance guarantee for approximate graph coloring. J. A CM, vol. 30, No. ,i, pages 729-735, Oct 1983. Google ScholarDigital Library
Index Terms
Scheduling algorithms for multi-hop radio networks
Recommendations
Scheduling algorithms for multi-hop radio networks
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 ...
Enhancing multi-hop communication over multi-radio multi-channel wireless mesh networks: A cross-layer approach
The multi-channel multi-radio technology represents a straightforward approach to expand the capacity of wireless mesh networks (WMNs) in broadband wireless access scenarios. However, the effective leveraging of this technology in WMNs requires (i) ...
Minimum energy scheduling in multi-hop wireless networks with retransmissions
MaxWeight algorithm, a.k.a., back-pressure algorithm [1]-[4], has received much attention as a viable solution for dynamic link scheduling in multi-hop wireless networks. The basic principle of the MaxWeight algorithm is to select a set of interference-...
Comments