Optimization of Anchor Selection Based on Graph Topology and Greedy Algorithm

Addressing the anchor selection problem for the DDS-DNNS (Decentralized Networked Navigation System Based on Data Distribution Service), a node location graph and a node location estimation model are constructed in this paper. The anchor selection problem is formulated as a D-optimal metric for maximizing the Fisher information matrix under a fixed cardinality constraint. Based on this, an optimization algorithm for anchor selection in DDS-DNNS is designed based on graph topology. This algorithm capitalizes on the connection between graph topology and the D-optimal metric of the Fisher information matrix, approximately transforming the maximization of the D-optimal metric of the Fisher information matrix into the maximization of the logarithmic determinant value of dimensionality-reduced weighted Laplacian matrix. Furthermore, based on the relevant properties of set functions and Cauchy’s alternating theorem, the approximate optimization model is proved as a non-regular, non-monotonic, and non-negative submodular maximization problem. Consequently, an improved greedy algorithm, which incorporates sparse Cholesky decomposition based on approximate minimum degree sorting, lazy evaluation, matrix dimension preservation and permutation vector reuse, and Cholesky decomposition result reuse, is devised to solve the approximate optimization model. It is also demonstrated that the algorithm possesses approximate optimization performance guarantees and a computational complexity significantly lower than that of the classical random greedy algorithm. Finally, the relationships between the number of anchors and the position estimation performance as well as the solution time under different algorithms are compared through simulation examples, and a selection criterion for fixed cardinality constraints is established. It is verified that the improved greedy algorithm can ensure high estimation accuracy under different numbers of anchors and effectively reduce the computational complexity.