Date of Award

3-2-2007

Document Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Department of Electrical and Computer Engineering

First Advisor

Kenneth M. Hopkinson, PhD

Abstract

Information and Networked Communications play a vital role in the everyday operations of the United States Armed Forces. This research establishes a comparative analysis of the unique network characteristics and requirements introduced by the Topology Control Problem (also known as the Network Design Problem). Previous research has focused on the development of Mixed-Integer Linear Program (MILP) formulations, simple heuristics, and Genetic Algorithm (GA) strategies for solving this problem. Principal concerns with these techniques include runtime and solution quality. To reduce runtime, new strategies have been developed based on the concept of flow networks using the novel combination of three well-known algorithms; knapsack, greedy commodity filtering, and maximum flow. The performance of this approach and variants are compared with previous research using several network metrics including computation time, cost, network diameter, dropped commodities, and average number of hops per commodity. The results conclude that maximum flow algorithms alone are not quite as effective as previous findings, but are at least comparable and show potential for larger networks.

AFIT Designator

AFIT-GCS-ENG-07-03

DTIC Accession Number

ADA469317

Download

Share

COinS