Satellite Geometry Optimization with Genetic Algorithms
Optimization of satellite configurations to improve positioning accuracy by minimizing geometric dilution of precision (GDOP), using a genetic algorithm.
Positions of satellites during their distribution (top left: 1 iteration, top right: 500 iterations, bottom: 10,000 iterations)
Motivation
The accuracy of satellite-based positioning depends not only on measurement errors, but also strongly on the geometric distribution of the satellites used for the position estimate. Unfavorable satellite geometry can significantly increase the resulting positioning error, while a well-distributed constellation reduces the Geometric Dilution of Precision (GDOP). The motivation of this work was therefore to derive the GDOP coefficient, demonstrate its practical calculation, and investigate how satellite positions can be optimized to minimize GDOP. A genetic algorithm was used to search for favorable satellite configurations for an arbitrary number of visible satellites.
System overview
The system was implemented in MATLAB and consisted of two main computational stages: satellite constellation optimization and GDOP evaluation. A candidate constellation was represented by a chromosome in which each gene described the spherical coordinates of one satellite. An initial population of randomly generated constellations was iteratively improved using a genetic algorithm with elitism, crossover, mutation and elimination.
The optimization objective was to obtain an approximately uniform distribution of satellites over the visible hemisphere. The fitness function therefore maximized the angular distance between the two closest satellites. A minimum elevation constraint was applied to exclude satellites close to the horizon. After optimization, the resulting satellite coordinates were used to construct the geometry matrix and calculate the covariance of the estimated receiver position. From this covariance matrix, GDOP and its individual components—HDOP, VDOP, PDOP and TDOP—were obtained.
Complete workflow for satellite position optimization problem.
Genetic algorithm
The optimization was solved using a genetic algorithm. Each individual in the population represented one complete satellite constellation. The constellation was encoded as a chromosome, where each gene represented one satellite and contained its spherical coordinates. The initial population was generated randomly within the allowed region of the hemisphere.
The quality of each constellation was evaluated by a fitness function based on the angular separation between satellites. For every candidate solution, the smallest angular distance between any two satellites was determined. The optimization objective was to maximize this minimum distance, forcing the satellites to become progressively more evenly distributed over the visible hemisphere.
Each optimization iteration consisted of four main operations:
- Elitism: the best-performing individuals were temporarily preserved so that the best solution found so far could not be lost.
- Crossover: two individuals were selected and divided at a randomly chosen crossover point. Parts of both chromosomes were combined to create a new satellite constellation.
- Mutation: with a defined probability, one gene of a randomly selected individual was modified, introducing new satellite positions into the population.
- Elimination: the worst-performing individuals were removed and the preserved elite individuals were returned to the population.
After every iteration, the best individual was compared with the best solution obtained previously. The process was repeated for a predefined number of iterations. Alternatively, convergence of the fitness value can be used as a termination criterion. Population size, mutation probability, number of iterations and reproduction parameters can be adjusted to influence the optimization process.
Fitness function
For each candidate constellation, the fitness value was defined as the minimum angular separation between any pair of satellites:
\[ d = \min_{i \neq j} \left( \arccos \left( x_i x_j + y_i y_j + z_i z_j \right) \right) \]The genetic algorithm maximizes \(d\). Increasing the distance between the closest pair of satellites drives the complete constellation towards a more uniform distribution.
GDOP calculation
After optimization, the satellite positions were used to build the geometry matrix \(G\). The covariance matrix of the estimated receiver state is obtained from:
\[ Q = (G^T G)^{-1} \]The diagonal elements of \(Q\) describe the variances of the estimated spatial coordinates and receiver clock term. The Geometric Dilution of Precision is then:
\[ GDOP = \sqrt{ \sigma_{xx}^2 + \sigma_{yy}^2 + \sigma_{zz}^2 + \sigma_{tt}^2 } \]A lower GDOP indicates a more favorable satellite geometry and therefore lower amplification of measurement errors in the final position estimate.
Results
The genetic algorithm was evaluated for different numbers of satellites, elevation constraints and numbers of optimization iterations. The results showed that the algorithm progressively produced a more uniform satellite distribution and, consequently, a lower GDOP value.
In the four-satellite example, GDOP decreased from 4.0341 after 5 iterations to 1.8700 after 50 iterations and 1.7123 after 500 iterations. This demonstrates the direct relationship between improvement of the satellite geometry and reduction of the GDOP coefficient.
| Satellites | Min. elevation | Iterations | TDOP | PDOP | HDOP | GDOP |
|---|---|---|---|---|---|---|
| 4 | 10° | 5,000 | 0.3334 | 1.6331 | 1.1547 | 1.7322 |
| 12 | 14° | 20,000 | 0.1573 | 1.0752 | 0.6537 | 1.1460 |
| 45 | 14° | 160,000 | 0.0531 | 0.5691 | 0.3471 | 0.6139 |
The experiments confirmed that a more uniform satellite geometry results in a lower GDOP. Within the simplified model, increasing the number of satellites also reduced the resulting dilution of precision. At the same time, constellations containing more satellites required substantially more genetic-algorithm iterations to reach a good distribution.
The simulation used a simplified model of the Earth and satellite visibility. The 12- and 45-satellite cases were included primarily to evaluate the behavior and scalability of the optimization algorithm.
This paper was published in 2011 at Czech Technical Univerity in Prague. Read full paper.