A mixed neural-genetic algorithm for the broadcast scheduling problem

• Published in: IEEE transactions on wireless communications 2003-03, Vol.2 (2), p.277-283
• Main Authors: Salcedo-Sanz, S., Bousono-Calzon, C., Figueiras-Vidal, A.R.
• Format: Article
• Language: English
• Subjects: Algorithms; Applied sciences; Broadcasting; Combinatorial analysis; Computational modeling; Delay; Exact sciences and technology; Frames; Genetic algorithms; Hopfield neural networks; Interference constraints; Neural networks; Optimization; Packet radio networks; Radio broadcasting; Scheduling; Scheduling algorithm; Systems, networks and services of telecommunications; Telecommunications; Telecommunications and information theory; Throughput; Transmission and modulation (techniques and equipments); Wireless communication
• ISSN: 1536-1276; 1558-2248
• DOI: 10.1109/TWC.2003.808967

The broadcast scheduling problem (BSP) arises in frame design for packet radio networks (PRNs). The frame structure determines the main communication parameters: communication delay and throughput. The BSP is a combinatorial optimization problem which is known to be NP-hard. To solve it, we propose an algorithm with two main steps which naturally arise from the problem structure: the first one tackles the hardest contraints and the second one carries out the throughput optimization. This algorithm combines a Hopfield neural network for the constraints satisfaction and a genetic algorithm for achieving a maximal throughput. The algorithm performance is compared with that of existing algorithms in several benchmark cases; in all of them, our algorithm finds the optimum frame length and outperforms previous algorithms in the resulting throughput.