An Efficient Metaheuristic for Dynamic Network Design and Message Routing

The implementation of Net-centric warfare presents major challenges in terms of effectively and efficiently delivering critical information across the Global Information Grid. In many cases, the amount of information requested will exceed the capabilities of the network. One challenge is to dynamically design the network (assign transceivers) to maximize the amount of required information that can be transmitted and the quality of service for those transmissions - to best implement the communications tasking order. The problem is as follows: given a list of required message traffic, to include source, destination, size, and priority, design the network to maximize the delivery of the message traffic based on message priority and quality of service. Once the network is designed, the routing for the messages must be determined. Due to the dynamic nature of the problem and the combinatorial explosion in size as new network nodes are added, a quick-running heuristic approach is needed. In this research, a metaheuristic is developed to dynamically design the network based on the projected message traffic requirements and efficiently route the required messages on the network, based on priority, maximizing the number of messages successfully delivered and the quality of service of the delivery. The meta-heuristic is tested against previous efforts and is shown to generate high quality solutions in a very short amount of time relative to methods in the current literature.