М.М. Valikhanov – Ph.D. (Eng.), Associate Professor, Siberian Federal University (Krasnoyarsk)
U.B. Voloshko – Leading Engineer, JSC Academician M.F. Reshetnev Information Satellite Systems (Zheleznogorsk)
А.S. Pustoshilov – Post-graduate Student, Siberian Federal University (Krasnoyarsk)
S.P. Tsarev – Dr.Sc. (Phys.-Math.), Professor, Siberian Federal University (Krasnoyarsk)
We propose an algorithm for minimization of transmission time of the almanac for GLONASS satellites for all users globally, which
allows collection of the complete almanac in 12 seconds (without the time for transmission of other navigation information) for navigation messages L3OCd, L1OCd, L1SCd or L2SCd with CDMA. This time compares favorably with 150 sec for transmission of the complete almanac in the current FDMA signals and the available CDMA signals (48 sec for L1OCd and 72 sec for L3OCd). We give three variants of the optimization algorithm: complete optimization, a simpler suboptimal version with the transmission time very close to the optimal one and finally the simplest algorithm which gives the same performance in 87,57% of cases. The last version does not require recalculation of the transmission table which remains valid for the complete period of existence of the orbital satellite constellation. The more involved first and second variants of the algorithm require recalculation of the transmission table every 15…20 minutes. This requires realistic computer resources. These two algorithms use the idea of covering subsets of navigation satellites. Such subsets provide visibility of at least one of the satellites of this subset from any point on the Earth (or the given priority target region on the Earth surface). The covering subsets of navigation satellites we use are quasiminimal: if one removes any of the satellites of the subset, the remaining ones do not cover the required target region. Such covering satellite subsets can be found for any given satellite constellation at a given time epoch in a reasonable time using a dynamic programming approach.
The first approach that guarantees complete optimality reduces the problem in question to an integer linear programming problem. This reduction turned out to be nontrivial and was not used previously; various well-known approaches of combinatorial and discrete optimization, scheduling theory, traffic and network flows, queueing processes and other operations research approaches resulted in prohibitively slow procedures. Optimality of our proposed solution for the first algorithm is rigorously proved.
Our method is easily adaptable to the problem of optimization of transmission time to a limited priority target region on the Earth surface. We give a modification of our method for pseudoframe optimization in the case of simultaneous transmission over several channels.
- INTERFACE CONTROL DOCUMENT General Description of Code Division Multiple Access Signal System, Edition 1.0. Moscow. 2016. URL: http://russianspacesystems.ru/wp-content/uploads/2016/08/IKD-L1-s-kod.-razd.-Red-1.0-2016.pdf
- Information and Analysis Center GLONASS. URL: https://www.glonass-iac.ru/
- Schrijver A. Theory of Linear and Integer Programming. John Wiley & Sons. 1998.
- Bellman R. Dynamic Programming. Princeton Univ. Press. 1957.
- Conway R.W., Maxwell W.L., Miller L.W. Theory of scheduling. Courier Corporation. 2003.
- Onn S. Nonlinear discrete optimization. EMS. 2010.
- De Loera J.A., Hemmeke R., Koeppe M. Algebraic and geometric ideas in the theory of discrete optimization. SIAM. 2013.
- Vielma J.P. Mixed integer linear programming formulation techniques. Siam Review. 2015. V. 57. № 1. P. 3–57.
- CBC (Coin-or branch and cut) – an open-source mixed integer programming solver. URL: https://projects.coin-or.org/Cbc
- GLPK (GNU Linear Programming Kit) solving large-scale linear programming (LP), mixed integer programming (MIP), and other related problems. URL: http://www.gnu.org/software/glpk/