Formulas and algorithms for optimizing the performance of rapidly changing satellite networks

Rapidly changing satellite networks are now in the design stage. Interest in this new area has been fostered by the Strategic Defense Initiative (SDI). Many SDI architectures have been proposed, but because the technology has not been fully developed and no satellite-to-satellite links exist, the architecture is only loosely defined.; This dissertation considers the SDI communications network from a systems point of view. Research was performed in the areas of topology, link assignment, routing, models, and performance measures. At the systems level, these areas are closely related. For example, consider the physical network which is a topology. In order to determine the performance of the system model using packet delay as a metric, a link assignment and routing algorithm are required.; The emphasis of this research was to develop link assignment and routing algorithms for optimizing the performance of rapidly changing satellite network topologies. Performance measures for the link assignment included connectivity, retargeting frequency, and propagation delay. Measures for routing included end-to-end delay, rerouting frequency, and number of common satellites on multiple paths between origin and destination. Minimizing the number of common satellites on multiple paths is an important consideration for survivable SDI communications and is a new area of research. Efficient algorithms for this problem were developed.; The topology optimization of satellite networks used a model of Np (orbit planes) and Ns (satellites per orbit) which provided complete coverage of the earth at all times. Closed formulas for the Np,Ns model were derived for the minimum altitude, minimum propagation delay, and maximum propagation delay. Algorithms were developed to obtain minimum, average, and maximum propagation delay for arbitrary single altitude topologies.; Optimization of link assignment for arbitrary topologies used a 2-level hierarchical model based on an NpNs region concept. The regions were circles which covered all points on an arbitrary altitude shell. Level 1 satellites formed a mesh backbone between regions which contained level 2 satellites. This link assignment has an optimal connectivity when satellites are constrained to have 4 antennas. An analytical solution for the total delay of the 2-level hierarchical model was derived for region disjoint path routing.; The routing research extended the minimum cost flow problem to include a minimum number of common nodes on multiple paths. The general minimum cost flow problem finds paths of minimum cost without regard to repeated nodes, which is undesirable for survivable network routing.