Genetic algorithm for broadcast scheduling in packet radio networks

Packet Radio (PR) networks are to provide data communication among a set of nodes distributed over a region. A time division multiple access (TDMA) protocol is adopted for conflict free communication. The goal is to find a conflict free transmission schedule for different nodes at different time slots of a fixed length time cycle, called TDMA cycle. The optimization criterion is primarily to minimize the TDMA cycle length, and then to maximize the number of transmissions. First classical Genetic Algorithm is tried to solve this NP-complete problem, which showed poor performance for bigger networks. Then we proposed some special crossover operators suitable for this kind of problem. This modified operator could deliver very good quality of results even for big networks and in few generations. Some study on the dependence of the result on population:ion size etc. are studied. The results are empirically compared with other approaches, a greedy-heuristic algorithm and mean field annealing.