Scheduling Link Activation in Multihop Radio Networks by Means of Hopfield Neural Network Techniques
Abstract
We address the problem of link activation or scheduling in multihop packet radio networks, 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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 03, 1991
- Accession Number
- ADA241242
Entities
People
- Anthony Ephremides
- Craig M. Barnhart
- Jeffrey E. Wieselthier
Organizations
- United States Naval Research Laboratory