
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A Greedy Genetic Algorithm for the TDMA Broadcast Scheduling Problem
ChihChiang LIN PiChung WANG
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E96D
No.1
pp.102110 Publication Date: 2013/01/01
Online ISSN: 17451361 Print ISSN: 09168532 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 adhoc networks is a wellknown NPcomplete combinatorial optimization problem. The BSP aims at finding a transmission schedule whose time slots are collision free in a wireless adhoc network with timedivision 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 largescale networks with 2,500 nodes.

