Problems of Routing and Scheduling in Multihop Radio Networks. A Hopfield NeuralNetwork Approach

摘要

Although the issues of routing and scheduling in packet radio networks are highlyinterdependent, few studies have addressed their interactions. After reviewing the major issues associated with the joint study of these problems, we address both components individually. Each is formulated as a combinatorial-optimization problem, and Hopfield neural network (NN) models are developed for solving several versions of these problems. A key feature of our models is the use of the method of Lagrange multipliers, which permits the coefficients in the connection weights to vary dynamically with the evolution of the system state. Extensive software simulation results demonstrate the capability of our approach to determine good sets of routes and link activation schedules. These results also demonstrate that these problems are not separable, i.e., that a model that jointly optimizes routes and link-activation schedules is needed. Issues associated with the extension of this approach to the joint routing/scheduling problem are discussed, and a preliminary description of such a model is provided.