О вычислительной сложности задачи синтеза антенной решётки

О вычислительной сложности задачи синтеза антенной решётки

Еремеев А. В.
Дискретный анализ и исследование операций, 32, 3, 71-83 (2025)
Скачать статью

УДК 519.8 
DOI: 10.33048/daio.2025.32.829

Аннотация:

Рассматривается задача синтеза фазированной антенной решётки, которая заключается в выборе фаз и амплитуд для всех излучающих элементов, когда требуется, чтобы получаемая диаграмма направленности по каждому рассматриваемому направлению принадлежала заданному множеству. Установлено, что поиск допустимого решения является NP-трудной в сильном смысле задачей в случае, когда по каждому рассматриваемому направлению допускается одно или два значения мощности излучения. Кроме того, доказана NP-трудность поиска допустимого решения в задаче синтеза частично заполненной антенной решётки, когда требуется, чтобы получаемая диаграмма направленности по каждому рассматриваемому направлению принадлежала заданному интервалу и амплитуды всех излучателей были одинаковы. 

Библиогр. 19.

Литература:
  1. Hansen R. C. Phased array antennas. Hoboken, NJ: John Wiley & Sons, 1979. 580 p.
     
  2. Kudzin V. P., Lozovsky V. N., Shlyk N. I. The compact linear antenna array system of the short-wave band consisting of “butterfly” radiators // Proc. 9th Int. Conf. Antenna Theory and Techniques (Odessa, Ukraine, Sept. 16–20, 2013). Piscataway: IEEE, 2013. P. 252–253.
     
  3. Wilensky R. High-power, broad-bandwidth HF dipole curtain array with extensive vertical and azimuthal beam control // IEEE Trans. Broadcast. 1988. V. 34, No. 2. P. 201–209. DOI: 10.1109/11.1437.
     
  4. Echeveste J. I., González de Aza M. A., Zapata J. Shaped beam synthesis of real antenna arrays via finite-element method, floquet modal analysis, and convex programming // IEEE Trans. Antennas Propag. 2016. V. 64, No. 4. P. 1279–1286. DOI: 10.1109/TAP.2016.2526038.
     
  5. Bucci O., Caccavale L., Isernia T. Optimal far-field focusing of uniformly spaced arrays subject to arbitrary upper bounds in non-target directions // IEEE Trans. Antennas Propag. 2002. V. 50, No. 11. P. 1539–1554. DOI: 10. 1109/TAP.2002.803959.
     
  6. Юрков A. С. Оптимизация возбуждения передающих фазированных антенных решёток декаметрового диапазона длин волн. Омск: ОНИИП, 2014. 65 с.
     
  7. Юрков A. С. Максимизация направленности фазированных антенных решёток коротковолнового диапазона // Техника радиосвязи. 2016. № 2. С. 46–53.
     
  8. Isernia T., Di Iorio P., Soldovieri F. An effective approach for the optimal focusing of array fields subject to arbitrary upper bounds // IEEE Trans. Antennas Propag. 2000. V. 48, No. 12. P. 1837–1847. DOI: 10.1109/8.901272.
     
  9. Тюнин Н. Н. Задачи невыпуклого квадратичного программирования, связанные с оптимизацией фазированных антенных решёток // Дискрет. анализ и исслед. операций. 2021. Т. 28, № 3. С. 65–89.
     
  10. Indenbom M., Izhutkin V., Sharapov A., Zonov A. Synthesis of conical phased antenna arrays optimization of amplitude distribution parameters // Proc. 9th Int. Conf. Optimization and Applications (Petrovac, Montenegro, Oct. 1–5, 2018). Lancaster, PA: DEStech Publ., 2018. P. 273–285.
     
  11. Akdagli A., Guney K. Shaped-beam pattern synthesis of equally and unequally spaced linear antenna arrays using a modified tabu search algorithm algorithm // Microw. Opt. Technol. Lett. 2003. V. 36, No. 1. P. 16–20. DOI: 10.1002/mop.10657.
     
  12. Villegas F. J. Parallel genetic-algorithm optimization of shaped beam coverage areas using planar 2-D phased arrays // IEEE Trans. Antennas Propag. 2007. V. 55, No. 6. P. 1745–1753. DOI: 10.1109/TAP.2007.898601.
     
  13. Fuchs B. Application of convex relaxation to array synthesis problems // IEEE Trans. Antennas Propag. 2014. V. 62, No. 2. P. 634–640.
     
  14. Щелкунов С. А., Фриис Г. Т. Антенны: Теория и практика. М.: Советское радио, 1955. 604 с.
     
  15. Garey M. R., Johnson D. S. Computers and intractability: A guide to the theory of NP-completeness. San Francisco: Freeman, 1979. 338 p.
     
  16. Leeper D. G. Thinned aperiodic antenna arrays with improved peak sidelobe level control. US Patent 4,071,848 (Jan 31, 1978). Murray Hill, NJ: Bell Teleph. Lab., 1976. URL: patentimages.storage.googleapis.com/30/73/ fa/25b9b72c3d3e8a/US4071848.pdf (accessed: 20.09.2025).
     
  17. Steinberg B. D. The peak sidelobe of the phased array having randomly located elements // IEEE Trans. Antennas Propag. 1972. V. 20, No. 2. P. 129–136. DOI: 10.1109/TAP.1972.1140162.
     
  18. Steinberg B. D. Principles of aperture and array system design. New York: John Wiley & Sons, 1976. 356 p.
     
  19. Копилович Л. Е., Содин Л. Г. Линейные не-эквидистантные антеннырешётки на базе разностных множеств // Радиотехника и электроника. 1989. Т. 34, № 10. С. 2059–2066.

Исследование выполнено в рамках государственного задания Института математики им. С. Л. Соболева (проект № FWNF–2022–0020). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Еремеев Антон Валентинович
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: eremeev@ofim.oscsbras.ru

Статья поступила 17 февраля 2025 г.
После доработки — 5 мая 2025 г.
Принята к публикации 22 июня 2025 г.

Abstract:

We consider the problem of phased antenna array synthesis, which consists of choosing phases and amplitudes for all radiating elements when it is required that the resulting radiation pattern in each direction considered belongs to a given set. It is established that the search for an admissible solution is a strongly NP-hard problem in the case when, for each direction considered, one or two radiation power values are allowed. In addition, the NP-hardness of finding an admissible solution in the problem of synthesis of a thinned antenna array is proven in the case when, for each direction considered, radiation power belongs to a given interval and excitation amplitudes in all elements are identical. 

Bibliogr. 19.

References:
  1. R. C. Hansen, Phased Array Antennas (John Wiley & Sons, Hoboken, NJ, 1979).
     
  2. V. P. Kudzin, V. N. Lozovsky, and N. I. Shlyk, The compact linear antenna array system of the short-wave band consisting of “butterfly” radiators, in Proc. 9th Int. Conf. Antenna Theory and Techniques (Odessa, Ukraine, Sept. 16–20, 2013) (IEEE, Piscataway, 2013), pp. 252–253.
     
  3. R. Wilensky, High-power, broad-bandwidth HF dipole curtain array with extensive vertical and azimuthal beam control, IEEE Trans. Broadcast. 34 (2), 201–209 (1988), DOI: 10.1109/11.1437.
     
  4. J. I. Echeveste, M. A. González de Aza, and J. Zapata, Shaped beam synthesis of real antenna arrays via finite-element method, floquet modal analysis, and convex programming,IEEE Trans. Antennas Propag. 64 (4), 1279–1286 (2016), DOI: 10.1109/TAP.2016.2526038.
     
  5. O. Bucci, L. Caccavale, and T. Isernia, Optimal far-field focusing of uniformly spaced arrays subject to arbitrary upper bounds in non-target directions, IEEE Trans. Antennas Propag. 50 (11), 1539–1554 (2002), DOI: 10.1109/TAP.2002.803959.
     
  6. A. S. Yurkov, Optimizing Excitation of Transmitting Phased Antenna Arrays in the Decameter Wavelength Range (ONIIP, Omsk, 2014) [Russian].
     
  7. A. S. Yurkov, Maximizing the directivity of short-range phased antenna arras, Tekh. Radiosvyazi, No. 2, 46–53 (2016) [Russian].
     
  8. T. Isernia, P. Di Iorio, and F. Soldovieri, An effective approach for the optimal focusing of array fields subject to arbitrary upper bounds, IEEE Trans. Antennas Propag. 48 (12), 1837–1847 (2000). DOI: 10.1109/8.901272.
     
  9. N. N. Tyunin, The problems of non-convex quadratic programming related to phased antenna arrays optimization, Diskretn. Anal. Issled. Oper. 28 (3), 65–89 (2021) [Russian] [J. Appl. Ind. Math. 15 (3), 543-557 (2021), DOI:10. 1134/S1990478921030157].
     
  10. M. Indenbom, V. Izhutkin, A. Sharapov, and A. Zonov, Synthesis of conical phased antenna arrays optimization of amplitude distribution parameters, in Proc. 9th Int. Conf. Optimization and Applications (Petrovac, Montenegro, Oct. 1–5, 2018) (DEStech Publ., Lancaster, PA, 2018), pp. 273–285.
     
  11. A. Akdagli and K. Guney, Shaped-beam pattern synthesis of equally and unequally spaced linear antenna arrays using a modified tabu search algorithm algorithm, Microw. Opt. Technol. Lett. 36 (1), 16–20 (2003), DOI: 10.1002/ mop.10657.
     
  12. F. J. Villegas, Parallel genetic-algorithm optimization of shaped beam coverage areas using planar 2-D phased arrays, IEEE Trans. Antennas Propag. 55 (6), 1745–1753 (2007), DOI: 10.1109/TAP.2007.898601.
     
  13. B. Fuchs, Application of convex relaxation to array synthesis problems, IEEE Trans. Antennas Propag. 62 (2), 634–640 (2014). DOI: 10.1109/TAP.2013. 2290797.
     
  14. S. A. Schelkunoff and H. T. Friis, Antennas: Theory and Practice (John Wiley & Sons, New York, 1952; Sov. Radio, Moscow, 1955 [Russian]).
     
  15. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).
     
  16. D. G. Leeper, Thinned aperiodic antenna arrays with improved peak sidelobe level control, US Patent 4,071,848 (Jan 31, 1978) (Bell Teleph. Lab., Murray Hill, NJ, 1976), URL: patentimages.storage.googleapis.com/30/ 73/fa/25b9b72c3d3e8a/US4071848.pdf (accessed: 20.09.2025).
     
  17. B. D. Steinberg, The peak sidelobe of the phased array having randomly located elements, IEEE Trans. Antennas Propag. 20 (2), 129–136 (1972), DOI: 10.1109/TAP.1972.1140162.
     
  18. B. D. Steinberg, Principles of Aperture and Array System Design (John Wiley & Sons, New York, 1976).
     
  19. L. E. Kopilovich and L. G. Sodin, Linear non-equidistant antenna arrays based on difference sets, Radiotekh. Elektron. 34 (10), 2059–2066 (1989).