A proposal of a greedy neural network for route assignments in multihop radio networks

✍ Scribed by Takayuki Baba; Nobuo Funabiki; Seishi Nishikawa

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 240 KB
• Volume: 30
• Category: Article
• ISSN: 0882-1666
• DOI: 10.1002/(sici)1520-684x(19991130)30:13<52::aid-scj6>3.0.co;2-v

✦ Synopsis

In a radio communications network, all of the nodes cannot communicate with each other directly. Then packets are transferred from a source node to a destination node through several nodes. Therefore, we need to schedule transfer timing at each node, and communications routes must be assigned to minimize the total transfer time when many packet transfers are requested. This problem is divided into two problems: the communications route assignment problem and the scheduling problem. The former problem is subdivided into the communication route candidate extraction problem and the communication route selection problem. This paper first proposes an evaluation function (Cost) which gives the lowest limit of the total transfer time for the communication route assignment problem. Next this paper proposes a k-shortest route extraction procedure for the communication route extraction problem. This procedure is based on the k-shortest route algorithm. It prevents extraction of a route whose number of hops is more than the upper limit, sets an appropriate number of extraction routes, prevents loops, and prevents redundant route extraction. We also propose a greedy neural network procedure for the communication route selection problem. This procedure introduces the Z function into the operation equation of the neuron initial value setting based on the number of hops and a cost minimization term for the evaluation function. The procedure uses an appropriate termination condition for iterative computation. It also uses the first-order maximum neuron. Through simulations of 500-vertex communication network examples, the pro-posed procedure has the merits of high precision, short computation, and smaller number of computations in a region.