A Greedy Genetic Algorithm for the TDMA Broadcast Scheduling Problem

Chih-Chiang LIN  Pi-Chung WANG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E96-D   No.1   pp.102-110
Publication Date: 2013/01/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Biocybernetics, Neurocomputing
Keyword: 
broadcast packet radio networks,  broadcast scheduling problem,  optimum transmission schedule,  time division multiple access,  genetic algorithm,  

Full Text: PDF(472.1KB)
>>Buy this Article


Summary: 
The broadcast scheduling problem (BSP) in wireless ad-hoc networks is a well-known NP-complete combinatorial optimization problem. The BSP aims at finding a transmission schedule whose time slots are collision free in a wireless ad-hoc network with time-division multiple access (TDMA). The transmission schedule is optimized for minimizing the frame length of the node transmissions and maximizing the utilization of the shared channel. Recently, many metaheuristics can optimally solve smaller problem instances of the BSP. However, for complex problem instances, the computation of metaheuristics can be quite time and memory consuming. In this work, we propose a greedy genetic algorithm for solving the BSP with a large number of nodes. We present three heuristic genetic operators, including a greedy crossover and two greedy mutation operators, to optimize both objectives of the BSP. These heuristic genetic operators can generate good solutions. Our experiments use both benchmark data sets and randomly generated problem instances. The experimental results show that our genetic algorithm is effective in solving the BSP problem instances of large-scale networks with 2,500 nodes.