Choosing a network topology to connect communication nodes subject to specific objectives, constraints, and properties is a broadly studied problem, with approaches varying widely depending on the hardware capabilities and limitations, the required performance criteria, and the available budget. This thesis is motivated by a topology problem in which naval, ground, air, and space vehicles require secure, high bandwidth data communications across long distances in an unstable environment. Each wireless connection in the network requires a pair of directional antennae; the connection is point-to-point line-of-sight, not broadcast over a wider region. While some nodes may be stationary, stable, and secure, the majority of the hundreds of nodes in the network are moving. As a result, a line-of-sight connection between a pair of nodes is subject to predictable and unpredictable interruption. Because the network is constantly evolving, new topologies must be generated very quickly so that network connectivity is maintained.;This thesis defines the connectivity problem as finding a modified degree-constrained spanning tree. It develops optimal algorithms which can generate the topology backbone for large point-to-point wireless networks quickly, even in networks with hundreds of nodes. The algorithms presented are compared to other network generating algorithms. This thesis extends the algorithms to new variations of this topology problem including scenarios where the antennae in the network consist of multiple incompatible technologies, and uses discrete time stages to maximize full connectivity over a time horizon. The results of the thesis provide algorithms for the design of real-time topology maintenance algorithms, as well as bounds for comparison with the performance of faster heuristic approaches for topology maintenance.
展开▼
