A mixed neural-genetic algorithm for the broadcast scheduling problem |
| |
Authors: | Salcedo-Sanz S Bousono-Calzon C Figueiras-Vidal AR |
| |
Affiliation: | Dept. of Signal Theor. & Commun., Univ. Carlos de Madrid, Leganes-Madrid, Spain; |
| |
Abstract: | 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. |
| |
Keywords: | |
|
|