An Efficient Simulated Annealing with a Valid Solution Mechanism for TDMA Broadcast Scheduling Problem

Date Added: Mar 2011
Format: PDF

In this paper, the authors present an efficient Simulated Annealing with valid solution mechanism for finding an optimum conflict-free transmission schedule for a broadcast radio network. This is known as a Broadcast Scheduling Problem (BSP) and shown as an NP-complete problem in earlier studies. Because of this NP-complete nature, earlier studies used genetic algorithms, mean field annealing, neural networks, factor graph and sum product algorithm, and sequential vertex coloring algorithm to obtain the solution. In their study, a valid solution mechanism is included in simulated annealing. Because of this inclusion, they are able to achieve better results even for networks with 100 nodes and 300 links. The results obtained using their methodology is compared with all the other earlier solution methods.