
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 Gradual Neural Network Algorithm for Broadcast Scheduling Problems in Packet Radio Networks
Nobuo FUNABIKI Junji KITAMICHI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E82A
No.5
pp.815824 Publication Date: 1999/05/25 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: neural network, packet radio network, TDMA cycle, broadcast scheduling problem,
Full Text: PDF>>
Summary:
A novel combinatorial optimization algorithm called "Gradual neural network (GNN)" is presented for NPcomplete broadcast scheduling problems in packet radio (PR) networks. A PR network provides data communications services to a set of geographically distributed nodes through a common radio channel. A time division multiple access (TDMA) protocol is adopted for conflictfree communications, where packets are transmitted in repetition of fixedlength timeslots called a TDMA cycle. Given a PR network, the goal of GNN is to find a TDMA cycle with the minimum delay time for each node to broadcast packets. GNN for the NnodeMslot TDMA cycle problem consists of a neural network with N M binary neurons and a gradual expansion scheme. The neural network not only satisfies the constraints but also maximizes transmissions by two energy functions, whereas the gradual expansion scheme minimizes the cycle length by gradually expanding the size of the neural network. The performance is evaluated through extensive simulations in benchmark instances and in geometric graph instances with up to 1000 vertices, where GNN always finds better TDMA cycles than existing algorithms. The result in this paper supports the credibility of our GNN algorithm for a class of combinatorial optimization problems.

