ON THE PERFORMANCE OF HEURISTICS FOR BROADCAST SCHEDULING

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.