A mixed neural-genetic algorithm for the broadcast scheduling problem

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...

Full description

Saved in:
Bibliographic Details
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
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1536-1276
1558-2248
DOI:10.1109/TWC.2003.808967