Scheduling Link Activation in Multihop Radio Networks by Means of Hopfield NeuralNetwork Techniques

摘要

We address the problem of link activation or scheduling in multihop packet radionetworks, a contention-free form of channel access that is appropriate for many military communication applications. It is well known that this problem, in almost all of its forms, is a combinatorial-optimization problem of high complexity. We approach this problem by use of a Hopfield neural network model in which the method of Lagrange multipliers is used to vary dynamically the values of the coefficients used in the connection weights. Two forms of the scheduling problem are considered. In the first, communication requirements are specified in terms of the number of packets that must be transmitted over each link in the network. In the second, an additional constraint is incorporated, namely that the sequence of link activations along any multihop path must be preserved. Extensive software simulation results demonstrate the effectiveness of this approach in producing schedules of optimal length. Issues associated with the extension of this approach to the joint routing/scheduling problem are discussed. (Author)