Scheduling Algorithms for Multihop Radio Networks

被引:296
作者
Ramanathan, Subramanian [1 ]
Lloyd, Errol L. [2 ]
机构
[1] BBN Syst & Technol Corp, Cambridge, MA 02138 USA
[2] Univ Delaware, Dept Comp Sci, Newark, DE 19716 USA
基金
美国国家科学基金会;
关键词
D O I
10.1109/90.222924
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
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 times optimum. Since the thickness is typically several orders of magnitude less 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.
引用
收藏
页码:166 / 177
页数:12
相关论文
共 30 条
  • [1] Alon N., 1989, Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, P274, DOI 10.1145/73007.73033
  • [2] Arikan E., 1984, IEEE T INFORM THEORY, VIT-30, P910
  • [3] Bar-Yehuda R., 1989, Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, P329, DOI 10.1145/72981.73005
  • [4] Bertsekas D., 1987, DATA NETWORKS
  • [5] Bollobas B., 1985, RANDOM GRAPHS
  • [6] Bondy JA., 2008, GRADUATE TEXTS MATH
  • [7] A DESIGN CONCEPT FOR RELIABLE MOBILE RADIO NETWORKS WITH FREQUENCY HOPPING SIGNALING
    EPHREMIDES, A
    WIESELTHIER, JE
    BAKER, DJ
    [J]. PROCEEDINGS OF THE IEEE, 1987, 75 (01) : 56 - 73
  • [8] ON THE NP-COMPLETENESS OF CERTAIN NETWORK TESTING PROBLEMS
    EVEN, S
    GOLDREICH, O
    MORAN, S
    TONG, P
    [J]. NETWORKS, 1984, 14 (01) : 1 - 24
  • [9] FIBONACCI HEAPS AND THEIR USES IN IMPROVED NETWORK OPTIMIZATION ALGORITHMS
    FREDMAN, ML
    TARJAN, RE
    [J]. JOURNAL OF THE ACM, 1987, 34 (03) : 596 - 615
  • [10] Gabow H. N., 1988, Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, P407, DOI 10.1145/62212.62252