Broadcast scheduling algorithms for radio networks

We investigate scheduling problems associated with radio networks using models based on graphs. Scheduling in networks is typically solved using graph coloring algorithms. In many cases the coloring algorithms are based on simplifying assumptions about the network structure. We show the limitations of the current models and propose modifications. The current models do not address the nonuniform transceiver/transmitter networks and they over-restrict transceiver interconnections. We develop algorithms which are more specific to the domain of radio network scheduling. We compare the performance of the earlier algorithms to our algorithms. The results are analyzed with respect to both execution time and quality of solution for networks of various sizes and densities