System analysis of the problem of using standard frequencies of radar stations of battery fighting vehicles

Introduction

When several radioelectronic facilities (REF) operate in the same frequency range, mutual jamming occurs. Specific features of interaction and the level of such jamming are determined by a number of factors, among which the main ones are spectral and spatial characteristics of radiating and receiving devices, as well as distances between the REFs. To reduce cross-influences between REF, limitations on spatial and frequency parameters are applied, when an REF is assigned frequencies that are prohibited to be used by other REFs. The problem of allocating standard frequencies for a target locator (TL) and a multifunction radar (MFR) consists in determining an operating frequency spectrum for each REF of all fighting vehicles (FV) in a battery, taking into account their relative location to one another. The operating frequencies of TL and MFR lie in different frequency bands, so solving the problem can be reduced to solving the tasks of TL and MFR standard frequencies allocation.

Problem statement

From the formal viewpoint, the problem of allocating standard frequencies has two modifications. In the first case, at m > r (where m – number of battery FVs; r – number of standard frequencies), the FVs operate on coinciding frequencies (to a greater extent, it concerns MFR). In the second case, at m ≥ r, each FV operates on its individual frequency (for contemporary TLs and MFRs, the number of standard frequencies may reach several hundreds), and the allocation effectiveness is determined by the frequency difference between FVs and distances between them.

When solving the first problem, primary attention is paid to the analysis of environment around the FVs operating on coinciding standard frequencies. When solving the second problem, it is important to ensure the maximum level of electromagnetic compatibility in case of uniform usage of the frequency band, which is conditioned by signal jamming by the enemy and unacceptability of using some frequency combinations in the battery structure. The use of coinciding frequencies is a self-contained problem, requiring an individual approach in development of a solution method, therefore, in the given case, such operation is not considered.

Let us define the problem of allocating REF standard frequencies. It is necessary to assign a certain operating frequency to each FV L_i based on the values of the initially specified frequency setting

   (1)

so that the value of a certain effectiveness criterion F would be the best (maximum or minimum). In so doing, the components of frequency vector including certain standard frequencies of the initial setting are associated with FV conventional numbers. Then notation means that FV 1 is assigned standard frequency L₁, FV 2 – L₂, and so on. The values of frequencies L_i belong to the initial setting (1), i.e.  .  The criterion of optimality must be indicative of the level of electromagnetic compatibility of the fighting vehicles, which is determined, first of all, by the distances between the FVs S_ij and their frequencies 

  (2)

where i, j – conventional numbers of the interacting FVs.

Joint use of REF, depending on their implementation, implies certain limitations on the standard frequencies and distances between the FVs operating on either coinciding or differing frequencies. In some cases the frequency setting falls into two ranges, upper and lower one, which in fact are disjoint. Sometimes the FV frequencies must comply with logic , where Δ – a certain frequency difference. In each particular REF implementation there are individual peculiarities which have to be responded to by appropriate limitations when searching for effective allocation of standard frequencies.

Let us put down an optimisation problem with criterion

  (3)

and system limitations

  (4)

Here, k₀ – number of limitations (conditions).

As stated by (3), (4), the problem relates to the class of discrete optimisation problems of NP type, i.e. such that have no rigorous solutions and defy development of accurate, effective algorithms. An accurate solution can be found if only by applying the brute force method, whose variance is extremely high in the presence of a large number of standard frequencies (for example, 10³⁰). For this reason, without application of special partitioning techniques [1][2] the brute force method is infeasible. Hence, for solving this problem, it would be appropriate to use the random search theory and genetic algorithms, briefly described in [3][4]. However, in this case there is a difficulty implementing optimisation algorithm on FV computing facilities. Proceeding from this, for finding an efficient option for allocating REF standard frequencies, it seems appropriate to use the brute force method based on the problem partitioning, which leads to reduction of the number of considered options.

Specifics of solving the problem under small number of standard frequencies

Let us consider one of the approaches to solving the problem for a case of m > r  and small dimensionality. First, it should be appropriate to distribute the available frequencies (r pcs.) among closely located FVs (the 1st cluster of amount r). Then the 2nd cluster shall be built, proceeding from the maximum remoteness from the 1st cluster objects, and allocation performed with account of the already assigned standard frequencies. The 3rd and all subsequent clusters are analysed similarly, up to allocation for the last FV. When assigning standard frequencies, it should be taken into account that for FVs with different standard frequencies, the distance between them shall be no less than a certain minimum acceptable value ∆S₁ (about 100 m), and for those with the same standard frequencies, at least ∆S₂ (of the order of 2 km).

On the one hand, such approach allows to reveal a number of nuances, accounting of which leads to different solutions and uncertainties. On the other hand, under varying number of FVs and standard frequencies, it is required to logically revise the algorithm and re-program it. The advantages of the described algorithm are the reliability and unambiguity of solution, with the minimum time expenditure for computer operations.

The other approach is a formal one. Let us elaborate on the case when the number of FVs exceeds that of the available standard frequencies. If each FV can operate on any one of r frequencies (i.e. there are r allocation options for a single FV), then it is easy to determine the total number of standard frequency allocation options for a group, which will amount to N = r^m  . For example, at m = 7 and r = 3, the number of different allocation options N = 2187, which is quite implementable when applying the brute force method for solution.

Given such variety, two issues are of importance: how to compare different options of standard frequency distribution among the FVs and which option to select as a preference. In this way, solving the problem of standard frequency allocation in an optimisation statement comes down to defining a criterion of optimality and restrictions within the limits of which the model is adequate and resolvable.

Most certainly, the criterion for the problem of allocating standard frequencies of a battery FV shall account for location of the FVs operating on the same frequency. The distances between objects with coinciding standard frequencies shall be the maximum at that. It is also necessary to take into account mutual arrangement of the FVs and the available standard frequencies, with consideration of the cut-off angles and digital terrain map. It should as well be appropriate to consider deviations from the normative values in arrangement of FVs operating on different and coinciding standard frequencies. All the aspects mentioned must serve as a base in development of an aggregate of criteria and restrictions in solving of this problem.

When applying the brute force method, all standard frequency combinations are generated and each option is evaluated as per the aggregate of criteria , with the use of Pareto multicriteria decision making.

The total deviation from norm H of distances  between the FVs with respect to coinciding standard frequencies L is determined:

   (5)

  (6)

Here, L₀ – number of MFR standard frequencies;
L – index of coinciding standard frequencies;
x_i,L, x_j,L, y_i,L, y_j,L, – coordinates i , j of FVs operating on the same frequency.

In so doing, only those FVs and standard frequencies are considered under which . Then a particular distribution of frequencies will be defined by vector where  in accordance with (1). For three standard frequencies M = {1, 2, 3} .

Another important element determining solution is criterion , defining the shortest distance between FVs operating on the same frequency. Its maximisation corresponds to the analysis objective:

  (7)

This is the so-called maximin (minimax) approach, under which system quality is evaluated for the worst option (concerning the problem at hand, it is the closest location of the FVs using the same standard frequency), which is improving gradually.

Ultimately, the improvement and optimality are determined as per the rule

  (8)

where B – logic variable taking the value of 0 or 1;

– next due criteria values;
– the best current criteria values.

If condition (8) is satisfied, the solution changes, i.e. improvement occurs. The brute force method procedure continues up to the last-generated solution.

To illustrate the essence of the brute force method, an example is given below. Let us consider an FV arrangement diagram (Figure). According to the program listing, there are 7 FVs operating on three frequencies, the coordinates are entered, jamming resistance determined, standard frequency allocation marked, 2187 different allocation options specified.

The data in Table 1 correspond to standard implementation of the algorithm. Standard frequencies are allocated between the FVs in accordance with pattern 1, 2, 3, 2, 3, 2, 1, i.е. FV 1 operates on the 1st standard frequency, 2 – on the 2nd standard frequency, ..., 7 – on the 1st standard frequency. In combat conditions, mutual arrangement of FV 3 and FV 5 is inadmissible, as the distance between them is 1000 m (instead of 2000 m as required by norm). Only one of them shall be used, or their mutual arrangement needs changing.

A summary risk estimate on similar standard frequencies:
• number of critical distance violations – 2;
• sum of critical distance violations for all FVs on all standard frequencies – 2000;
• magnitude of an average critical distance violation – 1000.

A summary risk estimate on different standard frequencies:
• number of critical distance violations – 0;
• sum of critical distance violations for all FVs on all standard frequencies – 0;
• magnitude of average critical distance violation – 0;
• no critical distances on similar standard frequencies.

Table 2 gives the results of brute force method implementation, with the found effective standard frequency allocation: 1, 2, 3, 3, 1, 3, 2. In that case sufficient jamming immunity of the battery from negative cross-influence of the FVs is ensured.

 A summary risk estimate on similar standard frequencies:
• number of critical distance violations – 0;
• sum of critical distance violations for all FVs on all standard frequencies – 0;
• magnitude of average critical distance violation – 0. 

Specifics of solving the problem of standard frequency allocation for TL

With a large number of standard frequencies available, which is characteristic of present-day TLs, each FV is assigned an individual standard frequency. An expression “operation on coinciding standard frequencies”, which used to be the key determinant in shaping the optimality criterion, is not applicable in this case. The criterion applying to operation of two radars is determined by distance  between the interacting radars and frequency difference , with this relationship being directly proportional:

  (9)

The power of jamming signal from the operating radar No. 2 at the receiver input of radar No. 1 can be described by [5][6][7] with the use of relationship:

  (10)

The criterion of FVs electromagnetic interaction F we represent as:

  (11)

where M_D – allowable set of frequency values determined by external factors; M – initial set of frequency values.

Here, the so-called maximin (minimax) approach is used, which registers frequency allocations on the basis of “picking the best from the worst” logic, or, in the given case, “making the most out of the least” [8]. If an acceptable state is achieved in the most constrained location (FV), then at other positions (FV) it should all the more be no worse. In this case the allocation obtained registers a state when there is electromagnetic compatibility of that fighting vehicle of all the battery FVs which is the most prone to be affected by mutual jamming, with due consideration of the entire variety of the frequency setting and FV locations.

The model of solution to the problem of standard frequency allocation for TL, based on the optimisation approach, looks as follows:

  (12)

  (13)

  (14)

Here, – fixed inadmissible frequency difference;
– magnitude determining inadmissibility of including closely located frequencies into the setting and indirectly influencing the uniformity of using the initial frequency setting.

Let us estimate time indices of the problem under consideration. If the 1st battery strength comprises n₁ FVs, the 2nd battery – n₂ , the 3rd battery – n₃ , and the number of available standard frequencies is r , then the total number of allocation options at the regiment level will be

(15)

If the number of standard frequencies r = 20 and the number of FVs n₁ = n₂ = n₃ = 6, then the total number of allocation options N = 20⁶·20⁶·20⁶ = 2.62214 · 10²².  At r = 200 (in fact, 217), n₁ = n₂ = n₃ = 6, N = 200⁶·200⁶·200⁶ = 2.62214 · 10⁴⁰. At r = 500 (in fact, 559), n₁ = n₂ = n₃ = 6, N = 500⁶ · 500⁶ · 500⁶ = 3.8146973 · 10⁴⁸. It is quite obvious that looking through that many options on the computer is impossible, as it would take a googol amount of time (10⁹ ...10³⁵ years).

This problem belongs to the class of NP problems, which can only be solved by the brute force method, searching through all the options. In this case, the optimisation methods have to be resorted to, or the methods of partitioning, allowing to substantially reduce variability due to rational use of its specific properties. On the one hand, optimisation does not guarantee optimality and acceptable solution time; on the other hand, it leads to development of special complex algorithms in the set of battery computing facilities. In connection with this, the partitioning approach with subsequent implementation of the brute force method is of certain interest.

The partitioning is based on the system analysis of a problem [2]. A point worth mentioning is the relevance of assigning to each battery an individual set of frequencies within a broad uniform range of the initial setting. In other words, the initial range of frequency setting M should be split into three non-overlapping sub-ranges (M₁, M₂, M₃), each one of which is uniform in the sense of consecutive values change:

(16)

This procedure is fairly simple in implementation. If there are 558 discrete frequencies, then a frequency setting corresponding to M₁ will be obtained on the basis of relationship

  (17)

Accordingly, for M2 and M3 we have: 

  (18)

  (19)

Datum points of the setting can be selected in different ways, in an elementary case, . Then we come up with the following sets of uniformly arranged and non-overlapping frequencies:
M₁: 1, 4, 7, 10, 13, 16, ..., 550, 553, 556; (20)
M₂: 2, 5, 8, 11, 14, 17, ..., 551, 554, 557; (21)
M₃: 3, 6, 9, 12, 15, 18, ..., 552, 555, 558. (22)

Each set contains 150 unique frequency designators (numbers) by which it is possible to calculate real frequency, measured in megahertz, for example:

  (23)

In this case the amount of look-through options at the regiment level will be

  (24)

which leads to intolerably large number of options to look through. As a result, it is relevant to use the same sorting procedure, leaving 50 basic, uniformly non-overlapping values, taking into account the requirement for mutually inadmissible frequencies to be absent in the set. In this case a computation run on the computer will take a few minutes. However, the 50 frequencies intended for referencing to no more than six FVs, with terrain map considered, are a reliable basis for solving the initial problem of standard frequency allocation. The obtained frequencies will be a priori widely spaced from one another, and after optimisation this spacing will be still wider with account for FVs spatial arrangement. In this case, frequency settings battery-wise will be as follows:

M₁: 1, 12, 23, 35, 46, 57, ..., 524, 536, 547, 556; (25)
M₂: 2, 13, 24, 36, 47, 58, ..., 525, 537, 548, 557; (26)
M₃: 3, 14, 25, 37, 48, 59, ..., 526, 538, 549, 558. (27)

The number of options will amount to:

N = 50⁶+50⁶+50⁶=3⋅5⁶⋅10⁶=4.6875⋅10¹⁰ (28)

processing of which will require a few minutes of computer operation.

For solving the same problem on the TL base, which includes 42 standard frequencies, we have the following frequency settings:

M₁ : 1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40; (29)
M₂ : 2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41; (30)
M₃ : 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42. (31)

The number of look-through options

N = 14⁶+14⁶+14⁶=7.529536·10⁶ (32)

In this case, computer operations will take no longer than 1 s.

To demonstrate the method on the base of six FVs and TLs, comprising 42 standard frequencies, for the 1st battery we have:

M₁ : 1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40.

The solution is to yield six non-overlapping values of this setting, corresponding to the maximum (minimum) of the investigated criterion.

Given below are the results of program implementation of the method, in which an effective allocation of standard frequencies was found: a set of numbers 1(1), 16(6), 40(14), 13(5), 4(2), 28(10). The notation in brackets corresponds to sequential numbering of 14 different frequencies of the 40 available, by the numbers of which the real frequency value, measured in hertz, can be computed. In so doing, sufficient jamming immunity of the battery from negative cross-influence of the FVs is ensured, with the criterion value equal to 86.26.

For comparison and method sensitivity evaluation, the opposite results are given, unwanted for the electromagnetic compatibility considerations. In this case the frequency setting is as follows: 1(1), 4(2), 7(3), 13(5), 10(4), 16(6). Criterion – 79.38. The FV coordinates are given in Table 3.

FV numbers: 3, 5, 6, 2, 1, 4

Average distance from FVs of other FVs: 399.103; 427.934; 437.111; 463.925; 591.312; 661.542

Average distance between FVs – 496.821

Number of permissible frequency allocation options – 2,162,160

Total number of frequency allocation options – 7,529,536

Optimal frequency allocation:
Effectiveness criterion value – 86.26
FV 1 – 1(1) FV 2 – 16(6) FV 3 – 40(14)
FV 4 – 13(5) FV 5 – 4(2) FV 6 – 28(10)

Frequency misallocation:
Effectiveness criterion value – 79.38
FV 1 – 1(1) FV 2 – 4(2) FV 3 – 7(3)
FV 4 – 13(5) FV 5 – 10(4) FV 6 – 16(6)

Values of criterion F in the optimal state: 
FV 1 – 86.26
FV 2 – 86.26
FV 3 – 86.38
FV 4 – 86.57
FV 5 – 86.29
FV 6 – 86.29

Values of criterion F in the worst state:
FV 1 – 82.22
FV 2 – 81.48
FV 3 – 79.38
FV 4 – 84.09
FV 5 – 79.38
FV 6 – 82.03

Processor time – 22.532 s
Total program run time – 43.613 s

Hence, with a large number of standard frequencies and the brute force method applied, the following procedures must be implemented.
1. Splitting the initial standard frequency set into three non-overlapping, uniformly distributed sub-ranges so as to provide for a possibility of frequency allocation at the regiment level.
2. Bringing standard frequency set of each battery down to a permissible size that enables search for an optimal solution within acceptable time (several minutes) by the brute force method.
3. Performing optimisation by the brute force method.

It should be noted that the method is sufficiently effective, simple in implementation, not requiring much computational resources, and fit for being used in management of standard frequencies of REF of the same frequency band.

Conclusion

A system analysis of the problem of allocating REF standard frequencies has been carried out, with account for the specifics of MFR and TL operation between battery FVs of a regiment, when their number is smaller than that of the FVs and the number of frequencies reaches several hundreds. Optimality criteria for standard frequency allocation have been developed, with their effectiveness and fitness for practical use established on the model level proceeding from the experimental research results. A mathematical model of the optimal distribution of standard frequencies has been built with account for FVs location, the available frequency setting, compatibility restrictions and limits on distribution uniformity in a given frequency range with a view to enemy’s directional jamming. An algorithm for solving the problem of standard frequency allocation has been developed and verified on test examples.