TY - JOUR

T1 - Routing strategies for multicast packet radio networks

AU - Hemminger, Thomas L.

AU - Coulston, Chris

AU - Pomalazza-Raez, Carlos A.

PY - 2002

Y1 - 2002

N2 - A common problem in a packet radio network (PRN) environment is to construct a multicasting network from a single source to a set of remote destinations which minimizes the number of transmissions. This problem is known to be NP-complete, thus computing an optimal solution may be infeasible for sizable networks. This paper provides two alternative solutions to this problem. The first is a heuristic algorithm which iteratively builds a spanning tree from the destinations to the source. A second solution, included for comparative purposes, is based on the Hopfield neural network whose dynamics are governed by a motion equation and a set of constraints. Both solutions are tested on a variety of instances against an optimal algorithm. Results show the approaches form good solutions (the number of transmissions is within about 3% of the optimum) and run in a fraction of the time required to form the optimal solution.

AB - A common problem in a packet radio network (PRN) environment is to construct a multicasting network from a single source to a set of remote destinations which minimizes the number of transmissions. This problem is known to be NP-complete, thus computing an optimal solution may be infeasible for sizable networks. This paper provides two alternative solutions to this problem. The first is a heuristic algorithm which iteratively builds a spanning tree from the destinations to the source. A second solution, included for comparative purposes, is based on the Hopfield neural network whose dynamics are governed by a motion equation and a set of constraints. Both solutions are tested on a variety of instances against an optimal algorithm. Results show the approaches form good solutions (the number of transmissions is within about 3% of the optimum) and run in a fraction of the time required to form the optimal solution.

UR - http://www.scopus.com/inward/record.url?scp=0036649482&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036649482&partnerID=8YFLogxK

U2 - 10.1080/10255810213479

DO - 10.1080/10255810213479

M3 - Article

AN - SCOPUS:0036649482

SN - 1025-5818

VL - 4

SP - 215

EP - 223

JO - International Journal of Smart Engineering System Design

JF - International Journal of Smart Engineering System Design

IS - 3

ER -