海军航空大学 山东 烟台 264001

关键词: 锚点选取, 图拓扑, D-最优度量, 集合函数, 子模性, 改进贪心算法

Abstract:

Addressing the anchor selection problem for the Decentralized Networked Navigation System Based on DDS (DDS-DNNS), a node location graph and a node location estimation model were constructed. The anchor selection problem was 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 was designed, leveraging 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 maximizing the logarithmic determinant value of the dimensionality-reduced weighted Laplacian matrix. Furthermore, based on the relevant properties of set functions and Cauchy's alternating theorem, it was proven that the approximate optimization model is a non-regular, non-monotonic, and non-negative submodular maximization problem. Consequently, an improved greedy algorithm was devised to solve the approximate optimization model, incorporating sparse Cholesky decomposition based on approximate minimum degree sorting, lazy evaluation, matrix dimension preservation and permutation vector reuse, and Cholesky decomposition result reuse. It was 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 effectiveness of the algorithm was verified through experiments.

Key words: anchor selection, graph topology, D-optimal metric, set function, submodularity, improved greedy algorithm