NEURAL NETWORK APPROACH FOR BROADCAST SCHEDULING IN PACKET RADIO NETWORK

Abstract

Neural network application have experienced a spurt in recent years. The artificial neural network models are massively parallel connected network of the Neuron. The property of massive parallelism makes these models an ideal tool for computational work in constrained optimization problems. This capacity could be exploited to solve the broadcast scheduling problems in Packet Radio networks. The objective is to determined a conflict free schedule of minimum "time slots" in a TDMA cycle. The purpose of Broadcast scheduling is to prevent interference among transmission from Neighouring nodes. It is well known that this problem in almost all of its forms, is a combinatorial optimization problem of high complexity. Starting with a reviewal survey of artificial- neural- network, this report focuses on the use of Boltzmann machine model of Neural Network for Broadcast Scheduling problem in packet radio network. A Boltzmann machine is a computational model that can be viewed as a novel approach to a connectionist models. This model uses a distributed knowledge representation and a massively parallel network of simple computing elements (Neurons). The processing elements in the network are connected in some way and with each a connection strength is associated. By This approach near-optimal solutions can be obtained by mapping the corresponding 0-1 variables onto the logic computing elements of a Boltzmann machine, - and by transforming the Broadcast scheduling constraints into the concensus function associated with Boltzmann machine. The algorithm requires nxm processing elements for an n-node-m-time slot radio network problem. This report proposes a centralized algorithm that runs in polynomial time and results in efficient schedules.