We address the multi-satellite scheduling problem with limited observation capacities that arises from the need to observe a set of targets on the Earth's surface using imaging resources installed on a set of satellites. We define and analyze the conflict indicators of all available visible time windows of missions, as well as the feasible time intervals of resources. The problem is then formulated as a mixed integer linear programming model, in which constraints are derived from a careful analysis of the interdependency between feasible time intervals that are eligible for observations. We apply the proposed model to several different problem instances that reflect real-world situations. The computational results verify that our approach is effective for obtaining optimum solutions or solutions with a very good quality.
In comparison to the single satellite scheduling problem, the use of multiple satellites gives more flexibility and is thus more challenging . @cite_6 @cite_11 @cite_4 use graph representations to formulate the problem, for which dynamic programming and ant colony optimization algorithms are proposed to produce a near-optimal solution. To this end, simple sequential missions with conflicts can easily be represented as graphs. However, if the problem involves multiple satellites, the visibility fields of different resources may overlap. Furthermore, several targets may be in the field of view of the same resource simultaneously, and a target may be observed by more than one resource at the same time. Thus, the visible time windows are highly overlapping during the scheduling period, making the combinational characteristic of the problem more prominent. This ultimately renders the uniform modelling of the problem difficult .
@cite_4 @cite_6 @cite_11
2087326379 2082026440 2154125468 2540490069
Satellite observation scheduling plays a significant role in improving the efficiency of satellite observation systems. Although extensive scheduling algorithms have been proposed for the satellite observation scheduling problem (SOSP), the task clustering strategy has not been taken into account up to now. This paper presents a novel two-phase based scheduling method with the consideration of task clustering for solving SOSP. This method comprises two phases: a task clustering phase and a task scheduling phase. In the task clustering phase, we construct a task clustering graph model and use an improved minimum clique partition algorithm to obtain cluster-tasks. In the task scheduling phase, based on overall tasks and obtained cluster-tasks, we construct an acyclic directed graph model and utilize a hybrid ant colony optimization coming with a mechanism of local search, called ACO-LS, to produce optimal or near optimal schedules. Extensive experimental simulations demonstrate the efficiency of the proposed scheduling method. In this paper, we develop models and algorithms for solving the single-satellite, multi-ground station communication scheduling problem, with the objective of maximizing the total amount of data downloaded from space. With the growing number of small satellites gathering large quantities of data in space and seeking to download this data to a capacity-constrained ground station network, effective scheduling is critical to mission success. Our goal in this research is to develop tools that yield high-quality schedules in a timely fashion while accurately modeling on-board satellite energy and data dynamics as well as realistic constraints of the space environment and ground network. We formulate an under-constrained mixed integer program (MIP) to model the problem. We then introduce an iterative algorithm that progressively tightens the constraints of this model to obtain a feasible and thus optimal solution. Computational experiments are conducted on diverse real-world data sets to demonstrate tractability and solution quality. Additional experiments on a broad test bed of contrived problem instances are used to test the boundaries of tractability for applying this approach to other problem domains. Our computational results suggest that our approach is viable for real-world instances, as well as providing a strong foundation for more complex problems with multiple satellites and stochastic conditions. In the interference scheduling problem, one is given a set of n communication requests described by source-destination pairs of nodes from a metric space. The nodes correspond to devices in a wireless network. Each pair must be assigned a power level and a color such that the pairs in each color class can communicate simultaneously at the specified power levels. The feasibility of simultaneous communication within a color class is defined in terms of the Signal to Interference plus Noise Ratio (SINR) that compares the strength of a signal at a receiver to the sum of the strengths of other signals. The objective is to minimize the number of colors as this corresponds to the time needed to schedule all requests. We introduce an instance-based measure of interference, denoted by I, that enables us to improve on previous results for the interference scheduling problem. We prove the upper and lower bounds in terms of I on the number of steps needed for scheduling a set of requests. For general power assignments, we prove a lower bound of @W(I ([email protected])) steps, where @D denotes the aspect ratio of the metric. When restricting to the two-dimensional Euclidean space (as in the previous work) the bound improves to @W(I [email protected]). Alternatively, when restricting to linear power assignments, the lower bound improves even to @W(I). The lower bounds are complemented by an efficient algorithm computing a schedule for linear power assignments using only O(Ilogn) steps. A more sophisticated algorithm computes a schedule using even only O(I+log^2n) steps. For dense instances in the two-dimensional Euclidean space, this gives a constant factor approximation for scheduling under linear power assignments, which shows that the price for using linear (and, hence, energy-efficient) power assignments is bounded by a factor of O([email protected]). In addition, we extend these results for single-hop scheduling to multi-hop scheduling and combined scheduling and routing problems, where our analysis generalizes the previous results towards general metrics and improves on the previous approximation factors. In this paper, we study resource allocation for a multicarrier-based cognitive radio (CR) network. More specifically, we investigate the problem of secondary users’ energy-efficiency (EE) maximization problem under secondary total power and primary interference constraints. First, assuming cooperation among the secondary base stations (BSs), a centralized approach is considered to solve the EE optimization problem for the CR network where the primary and secondary users are using either orthogonal frequency-division multiplexing (OFDM) or filter bank based multicarrier (FBMC) modulations. We propose an alternating-based approach to solve the joint power-subcarrier allocation problem. More importantly, in the first place, subcarriers are allocated using a heuristic method for a given feasible power allocation. Then, we conservatively approximate the nonconvex power control problem and propose a joint successive convex approximation-Dinkelbach algorithm (SCADA) to efficiently obtain a solution to the nonconvex power control problem. The proposed algorithm is shown to converge to a solution that coincides with the stationary point of the original nonconvex power control subproblem. Moreover, we propose a dual decomposition-based decentralized version of the SCADA. Second, under the assumption of no cooperation among the secondary BSs, we propose a fully distributed power control algorithm from the perspective of game theory. The proposed algorithm is shown to converge to a Nash-equilibrium (NE) point. Moreover, we propose a sufficient condition that guarantees the uniqueness of the achieved NE. Extensive simulation analyses are further provided to highlight the advantages and demonstrate the efficiency of our proposed schemes.