{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,26]],"date-time":"2025-07-26T09:21:16Z","timestamp":1753521676195,"version":"3.37.3"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100020795","name":"Sensors Directorate","doi-asserted-by":"publisher","award":["FA9453-20-1-0002"],"award-info":[{"award-number":["FA9453-20-1-0002"]}],"id":[{"id":"10.13039\/100020795","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["EURASIP J. Adv. Signal Process."],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Optimizing the correlation properties of spreading codes is critical for minimizing inter-channel interference in satellite navigation systems. By improving the codes\u2019 correlation sidelobes, we can enhance navigation performance while minimizing the required spreading code lengths. In the case of low-earth orbit (LEO) satellite navigation, shorter code lengths (on the order of a hundred) are preferred due to their ability to achieve fast signal acquisition. Additionally, the relatively high signal-to-noise ratio in LEO systems reduces the need for longer spreading codes to mitigate inter-channel interference. In this work, we propose a two-stage block coordinate descent (BCD) method which optimizes the codes\u2019 correlation properties while enforcing the autocorrelation sidelobe zero property. In each iteration of the BCD method, we solve a mixed-integer convex program over a block of 25 binary variables. Our method is applicable to spreading code families of arbitrary sizes and lengths, and we demonstrate its effectiveness for a problem with 66 length-127 codes and a problem with 130 length-257 codes.<\/jats:p>","DOI":"10.1186\/s13634-024-01160-0","type":"journal-article","created":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T03:48:10Z","timestamp":1716954490000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Spreading code optimization for low-earth orbit satellites via mixed-integer convex programming"],"prefix":"10.1186","volume":"2024","author":[{"given":"Alan","family":"Yang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tara","family":"Mina","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1807-8637","authenticated-orcid":false,"given":"Grace","family":"Gao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,29]]},"reference":[{"key":"1160_CR1","doi-asserted-by":"crossref","unstructured":"T.G. Reid, T. Walter, P.K. Enge, D. Lawrence, H.S. Cobb, G. Gutt, M. O\u2019Connor, D. Whelan, Navigation from low earth orbit: part 1: concept, current capability, and future promise, in Position, Navigation, and Timing Technologies in the 21st Century: Integrated Satellite Navigation, Sensor Systems, and Civil. Applications, vol. 2 (2020), pp. 1359\u20131379","DOI":"10.1002\/9781119458555.ch43a"},{"key":"1160_CR2","doi-asserted-by":"crossref","unstructured":"K. Maine, C. Devieux, P. Swan, Overview of IRIDIUM satellite network, in Proceedings of WESCON\u201995 (IEEE, 1995), p. 483","DOI":"10.1109\/WESCON.1995.485428"},{"key":"1160_CR3","unstructured":"P.B. De\u00a0Selding, Virgin, Qualcomm invest in OneWeb satellite internet venture. Space News 15 (2015)"},{"key":"1160_CR4","unstructured":"F. Khan, Mobile Internet from the Heavens (2015). arXiv:1508.02383"},{"key":"1160_CR5","unstructured":"P.B. De\u00a0Selding, SpaceX to build 4,000 broadband satellites in Seattle. Space News 19 (2015)"},{"key":"1160_CR6","unstructured":"Septentrio: Septentrio collaborates with Xona on PULSAR GNSS receiver (2023). https:\/\/www.septentrio.com\/en\/company\/news\/septentrio-collaborates-xona-pulsar-gnss-receiver. Accessed 19 June 2023"},{"key":"1160_CR7","doi-asserted-by":"crossref","unstructured":"T.G. Reid, A.M. Neish, T.F. Walter, P.K. Enge, Leveraging commercial broadband LEO constellations for navigating, in Proceedings of the 29th International Technical Meeting of the Satellite Division of the Institute of Navigation (Ion Gnss+ 2016), Portland, Oregon, vol. 12 (2016), pp. 2016\u20132016","DOI":"10.33012\/2016.14729"},{"key":"1160_CR8","unstructured":"K. Dennehy, Is LEO PNT the Next Big Thing? vol. 33 (2023). https:\/\/www.ion.org\/publications\/upload\/ION-Winter2023.pdf"},{"key":"1160_CR9","doi-asserted-by":"publisher","first-page":"83971","DOI":"10.1109\/ACCESS.2022.3194050","volume":"10","author":"FS Prol","year":"2022","unstructured":"F.S. Prol, R.M. Ferre, Z. Saleem, P. V\u00e4lisuo, C. Pinell, E.-S. Lohan, M. Elsanhoury, M. Elmusrati, S. Islam, K. \u00c7elikbilek et al., Position, navigation, and timing (PNT) through low earth orbit (LEO) satellites: a survey on current status, challenges, and opportunities. IEEE Access 10, 83971\u201384002 (2022)","journal-title":"IEEE Access"},{"key":"1160_CR10","volume-title":"Global Positioning System: Signals, Measurements & Performance","author":"P Misra","year":"2012","unstructured":"P. Misra, P. Enge, Global Positioning System: Signals, Measurements & Performance (Ganga-Jamuna Press, Kathmandu, 2012)"},{"key":"1160_CR11","doi-asserted-by":"crossref","unstructured":"H.B. Bekhit, E. El\u00a0Diwany, S.H. El\u00a0Ramly, Design of ranging codes for low-earth orbit satellites, in Proceedings of 5th International Conference on Recent Advances in Space Technologies (RAST) (IEEE, 2011), pp. 324\u2013329","DOI":"10.1109\/RAST.2011.5966849"},{"key":"1160_CR12","unstructured":"S. Wallner, J.-A. Avila-Rodriguez, G.W. Hein, J.J. Rushanan, Galileo E1 OS and GPS L1C pseudo random noise codes-requirements, generation, optimization and comparison, in Proceedings of the 20th International Technical Meeting of the Satellite Division of the Institute of Navigation (ION GNSS 2007) (2007), pp. 1549\u20131563"},{"key":"1160_CR13","unstructured":"J.O. Winkel, Spreading codes for a satellite navigation system. United States Patent. Patent No.: US 8,035,555 B2 (2011)"},{"key":"1160_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-11008-0","volume-title":"Integer Programming","author":"M Conforti","year":"2014","unstructured":"M. Conforti, G. Cornu\u00e9jols, G. Zambelli, Integer Programming, vol. 271 (Springer, Berlin, 2014)"},{"key":"1160_CR15","doi-asserted-by":"crossref","unstructured":"A. Yang, T. Mina, G. Gao, Binary sequence set optimization for CDMA applications via mixed-integer quadratic programming, in IEEE International Conference on Acoustics, Speech, & Signal Processing (2023)","DOI":"10.1109\/ICASSP49357.2023.10095359"},{"key":"1160_CR16","doi-asserted-by":"crossref","unstructured":"A. Yang, T. Mina, G. Gao, Spreading code sequence design via mixed-integer convex optimization, in Proceedings of the 36th International Technical Meeting of the Satellite Division of the Institute of Navigation (ION GNSS+ 2023) (2023), pp. 1341\u20131351","DOI":"10.33012\/2023.19318"},{"key":"1160_CR17","unstructured":"L. Gurobi, Optimization, Gurobi Optimizer Reference Manual (2022). https:\/\/www.gurobi.com"},{"issue":"4","key":"1160_CR18","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1109\/TIT.1967.1054048","volume":"13","author":"R Gold","year":"1967","unstructured":"R. Gold, Optimal binary sequences for spread spectrum multiplexing. IEEE Trans. Inf. Theory 13(4), 619\u2013621 (1967)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"1160_CR19","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1002\/j.2161-4296.2007.tb00394.x","volume":"54","author":"JJ Rushanan","year":"2007","unstructured":"J.J. Rushanan, The spreading and overlay codes for the L1C signal. Navigation 54(1), 43\u201351 (2007)","journal-title":"Navigation"},{"key":"1160_CR20","unstructured":"A.-M. Legendre, Essai sur la th\u00e9orie des nombres. Chez Courcier (1808)"},{"key":"1160_CR21","doi-asserted-by":"crossref","unstructured":"T.Y. Mina, G.X. Gao, Devising high-performing random spreading code sequences using a multi-objective genetic algorithm, in Proceedings of the 32nd International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GNSS+ 2019) (2019), pp. 1076\u20131089","DOI":"10.33012\/2019.17044"},{"issue":"10","key":"1160_CR22","doi-asserted-by":"publisher","first-page":"2387","DOI":"10.3390\/rs14102387","volume":"14","author":"T Liu","year":"2022","unstructured":"T. Liu, J. Sun, G. Wang, Y. Lu, A multi-objective quantum genetic algorithm for MIMO radar waveform design. Remote Sens. 14(10), 2387 (2022)","journal-title":"Remote Sens."},{"key":"1160_CR23","doi-asserted-by":"crossref","unstructured":"T.Y. Mina, G.X. Gao, Designing low-correlation GPS spreading codes with a natural evolution strategy machine-learning algorithm. NAVIG. J. Inst. Navig. 69(1) (2022)","DOI":"10.33012\/navi.506"},{"key":"1160_CR24","doi-asserted-by":"crossref","unstructured":"T. Mina, A. Yang, G. Gao, Designing long GPS memory codes using the cross entropy method, in Proceedings of the 36th International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GNSS+ 2023) (2023), pp. 1328\u20131340","DOI":"10.33012\/2023.19260"},{"key":"1160_CR25","unstructured":"S. Wallner, J.-A. Avila-Rodriguez, J.-H. Won, G. Hein, J.-L. Issler, Revised PRN code structures for galileo E1 OS, in Proceedings of the 21st International Technical Meeting of the Satellite Division of the Institute of Navigation (ION GNSS 2008) (2008), pp. 887\u2013899"},{"issue":"13","key":"1160_CR26","doi-asserted-by":"publisher","first-page":"3347","DOI":"10.1109\/TSP.2019.2914878","volume":"67","author":"M Alaee-Kerahroodi","year":"2019","unstructured":"M. Alaee-Kerahroodi, M. Modarres-Hashemi, M.M. Naghsh, Designing sets of binary sequences for MIMO radar systems. IEEE Trans. Signal Process. 67(13), 3347\u20133360 (2019)","journal-title":"IEEE Trans. Signal Process."},{"issue":"18","key":"1160_CR27","doi-asserted-by":"publisher","first-page":"4756","DOI":"10.1109\/TSP.2017.2715010","volume":"65","author":"G Cui","year":"2017","unstructured":"G. Cui, X. Yu, G. Foglia, Y. Huang, J. Li, Quadratic optimization with similarity constraint for unimodular sequence synthesis. IEEE Trans. Signal Process. 65(18), 4756\u20134769 (2017)","journal-title":"IEEE Trans. Signal Process."},{"key":"1160_CR28","doi-asserted-by":"crossref","unstructured":"R. Lin, J. Li, On binary sequence set design with applications to automotive radar, in ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (IEEE, 2020), pp. 8639\u20138643","DOI":"10.1109\/ICASSP40776.2020.9054143"},{"key":"1160_CR29","doi-asserted-by":"crossref","unstructured":"W. Huang, R. Lin, Efficient design of Doppler sensitive long discrete-phase periodic sequence sets for automotive radars, in 2020 IEEE 11th Sensor Array and Multichannel Signal Processing Workshop (SAM) (IEEE, 2020), pp. 1\u20135","DOI":"10.1109\/SAM48682.2020.9104358"},{"key":"1160_CR30","unstructured":"G. Yuan, L. Shen, W.-S. Zheng, A Hybrid Method of Combinatorial Search and Coordinate Descent for Discrete Optimization (2017). arXiv:1706.06493"},{"key":"1160_CR31","doi-asserted-by":"publisher","first-page":"3619","DOI":"10.1109\/TSP.2020.2998637","volume":"68","author":"X Yu","year":"2020","unstructured":"X. Yu, G. Cui, J. Yang, J. Li, L. Kong, Quadratic optimization for unimodular sequence design via an ADPM framework. IEEE Trans. Signal Process. 68, 3619\u20133634 (2020)","journal-title":"IEEE Trans. Signal Process."},{"issue":"11","key":"1160_CR32","doi-asserted-by":"publisher","first-page":"5618","DOI":"10.1109\/TSP.2008.929657","volume":"56","author":"A De Maio","year":"2008","unstructured":"A. De Maio, S. De Nicola, Y. Huang, S. Zhang, A. Farina, Code design to optimize radar detection performance under accuracy and similarity constraints. IEEE Trans. Signal Process. 56(11), 5618\u20135629 (2008)","journal-title":"IEEE Trans. Signal Process."},{"issue":"11","key":"1160_CR33","doi-asserted-by":"publisher","first-page":"2998","DOI":"10.1109\/TSP.2018.2814990","volume":"66","author":"A Bose","year":"2018","unstructured":"A. Bose, M. Soltanalian, Constructing binary sequences with good correlation properties: an efficient analytical-computational interplay. IEEE Trans. Signal Process. 66(11), 2998\u20133007 (2018)","journal-title":"IEEE Trans. Signal Process."},{"issue":"4","key":"1160_CR34","doi-asserted-by":"publisher","first-page":"4719","DOI":"10.1002\/dac.4719","volume":"34","author":"S Boukerma","year":"2021","unstructured":"S. Boukerma, K. Rouabah, S. Mezaache, S. Atia, Efficient method for constructing optimized long binary spreading sequences. Int. J. Commun. Syst. 34(4), 4719 (2021)","journal-title":"Int. J. Commun. Syst."},{"issue":"10","key":"1160_CR35","doi-asserted-by":"publisher","first-page":"1537","DOI":"10.1049\/iet-rsn.2020.0168","volume":"14","author":"D Medina","year":"2020","unstructured":"D. Medina, L. Ortega, J. Vil\u00e0-Valls, P. Closas, F. Vincent, E. Chaumette, Compact CRB for delay, Doppler, and phase estimation-application to GNSS SPP and RTK performance characterisation. IET Radar Sonar Navig. 14(10), 1537\u20131549 (2020)","journal-title":"IET Radar Sonar Navig."},{"key":"1160_CR36","doi-asserted-by":"crossref","unstructured":"L. Ortega, J. Vil\u00e0-Valls, E. Chaumette, F. Vincent, On the time-delay estimation performance limit of new GNSS acquisition codes, in 2020 International Conference on Localization and GNSS (ICL-GNSS) (IEEE, 2020), pp. 1\u20136","DOI":"10.1109\/ICL-GNSS49876.2020.9115552"},{"key":"1160_CR37","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139095174","volume-title":"Waveform Design for Active Sensing Systems: A Computational Approach","author":"H He","year":"2012","unstructured":"H. He, J. Li, P. Stoica, Waveform Design for Active Sensing Systems: A Computational Approach (Cambridge University Press, Cambridge, 2012)"},{"issue":"1","key":"1160_CR38","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1287\/opre.22.1.180","volume":"22","author":"F Glover","year":"1974","unstructured":"F. Glover, E. Woolsey, Converting the 0\u20131 polynomial programming problem to a 0\u20131 linear program. Oper. Res. 22(1), 180\u2013182 (1974)","journal-title":"Oper. Res."},{"key":"1160_CR39","unstructured":"K. Bestuzheva, M. Besan\u00e7on, W.-K. Chen, A. Chmiela, T. Donkiewicz, J. Doornmalen, L. Eifler, O. Gaul, G. Gamrath, A. Gleixner et al., The SCIP optimization suite 8.0 (2021). arXiv:2112.08872"},{"issue":"4","key":"1160_CR40","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1287\/opre.14.4.699","volume":"14","author":"EL Lawler","year":"1966","unstructured":"E.L. Lawler, D.E. Wood, Branch-and-bound methods: a survey. Oper. Res. 14(4), 699\u2013719 (1966)","journal-title":"Oper. Res."},{"key":"1160_CR41","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0166-218X(94)90204-6","volume":"49","author":"P Brucker","year":"1994","unstructured":"P. Brucker, B. Jurisch, B. Sievers, A branch and bound algorithm for the job-shop scheduling problem. Discrete Appl. Math. 49, 107\u2013127 (1994)","journal-title":"Discrete Appl. Math."},{"key":"1160_CR42","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1137\/1033004","volume":"33","author":"M Padberg","year":"1991","unstructured":"M. Padberg, G. Rinaldi, A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33, 60\u2013100 (1991)","journal-title":"SIAM Rev."},{"key":"1160_CR43","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/s101070050103","volume":"86","author":"R Stubbs","year":"1999","unstructured":"R. Stubbs, S. Mehrotra, A branch-and-cut method for 0\u20131 mixed convex programming. Math. Program. 86, 515\u2013532 (1999)","journal-title":"Math. Program."},{"key":"1160_CR44","unstructured":"F. Soualle, M. Soellner, S. Wallner, J.-A. Avila-Rodriguez, G.W. Hein, B. Barnes, T. Pratt, L. Ries, J. Winkel, C. Lemenager et\u00a0al., Spreading code selection criteria for the future GNSS Galileo, in Proceedings of the European Navigation Conference GNSS (2005), pp. 19\u201322"},{"key":"1160_CR45","doi-asserted-by":"crossref","unstructured":"A. Yang, T.Y. Mina, G.X. Gao, Fast spreading code optimization under doppler effects, in Proceedings of the 2024 International Technical Meeting of the Institute of Navigation (ION ITM 2024) (2024)","DOI":"10.33012\/2024.19513"}],"container-title":["EURASIP Journal on Advances in Signal Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13634-024-01160-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13634-024-01160-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13634-024-01160-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,20]],"date-time":"2024-11-20T15:19:51Z","timestamp":1732115991000},"score":1,"resource":{"primary":{"URL":"https:\/\/asp-eurasipjournals.springeropen.com\/articles\/10.1186\/s13634-024-01160-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":45,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["1160"],"URL":"https:\/\/doi.org\/10.1186\/s13634-024-01160-0","relation":{},"ISSN":["1687-6180"],"issn-type":[{"type":"electronic","value":"1687-6180"}],"subject":[],"published":{"date-parts":[[2024,5,29]]},"assertion":[{"value":"7 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 May 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 May 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"67"}}