Algorithms Of Space-based Information Network Flow Problems

With the rapid development of space technology to build space-based information network, capturing space superiority becomes a national important tasks of technological and military development. Space-based information network is a kind of space wireless network system consisted of all types of satellite network nodes connected through ISLs, with wide coverage, transmission capacity and other characteristics. Routing and flow problems, which are two important ways of information transferring in space-based information network, gradually appeal to scholars’ studies.In this dissertation, the space-based information network’s flow problems are studied based on the characteristics of the network. Based on the classification of flow problem, three flow problems which have proposed targeted, important application background and practical significance are proposed, so do their corresponding solving algorithms.The main work and achievements of this dissertation are given below:1. This dissertation proposes a space-based information network flow problem’s classification criteria, breaks it down into three kinds of flow problem—static flow problem, dynamic information flow problem and dynamic topology flow problem. Then differences and similarities of these three kinds of flow problem are pointed out and their corresponding practical application is also showed. Finally dynamic topology flow problem is changed into the sensitivity analysis of static flow problem.2. According to space-based information network QoS protocol mode, this dissertation describes the practical value of multi-objective optimization problem and abstracts with a model of minimum double-cost flow problem which has two partial ordered costs. Using the idea of primal-duality, this dissertation designs an efficient solving algorithm for the problem and then extends the algorithm to the multi-cost case.3. For the information transmission delay problem which exists in space-based information network, this dissertation abstracts with a model of continuous-time capacity network and proposes a new concept—shortest dynamic time flow. The relationship between classic network and restrict network with nodes is discovered and then shortest dynamic time flow algorithms for these two kinds of network model are proposed.4. The background and research status of sensitivity analysis of maximal information flow in space-based information network is introduced. For its two major sub-problems—vital satellites problem and optimal add-link problem, this dissertation designs efficient algorithms respectively. Compared to natural algorithms based on definition, algorithms in this dissertation are much better in both theoretical complexity and practical computation.