On the performance of heuristics for broadcast scheduling

被引:0
作者
Commander, CW [1 ]
Butenko, SI [1 ]
Pardalos, PM [1 ]
机构
[1] Univ Florida, Dept Ind & Syst Engn, Gainesville, FL 32611 USA
来源
THEORY AND ALGORITHMS FOR COOPERATIVE SYSTEMS | 2004年 / 4卷
关键词
broadcast scheduling problem; ad-hoc networks; combinatorial optimization; NP-complete; heuristics;
D O I
暂无
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
In the Broadcast Scheduling Problem (BSP), a finite set of stations are to be scheduled in a time division multiple access (TDMA) frame. In a TDMA frame, time is divided into equal length transmission slots. Unconstrained message transmission can result in a collision of messages, rendering them useless. Therefore, the objective of the BSP is to provide a collision free broadcast schedule which minimizes the total frame length or maximizes the slot utilization within the frame. In this chapter, we introduce the BSP as a NP-complete combinatorial optimization problem and discuss several heuristics which have been applied to the problem. The heuristics are tested on over 60 networks of varying sizes and densities and the results compared.
引用
收藏
页码:63 / 80
页数:18
相关论文
共 34 条