A GRASP for broadcast scheduling in ad-hoc TDMA networks

The Broadcast Scheduling Problem (BSP) arises in the study of ad-hoc networks. The BSP is an NP-Complete problem in which 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 slots in which transmissions occur. Unconstrained message transmission can result in a collision of messages, therefore the objective of the BSP is to provide a collision free broadcast schedule which minimizes the total frame length and maximizes the blot utilization within the frame. In this article, we present a GRASP (Greedy Randomized Adaptive Search Procedure) for the BSP. GRASP is a two-phase multi-start heuristic for hard combinatorial problems. A reactive heuristic was used to automatically balance GRASP parameters. A variant of the post-optimization enhancement procedure Path Relinking is also applied. We report experimental results given by our approach.