Algorithm to calculate coordinated radio frequencies

Question

I'm stuck on this algorithm problem for a project I'm working on. I can find no relevant documentation, and would very much appreciate any help that can be offered on this! I will try to explain it the best I can.

I need to calculate as many radio frequencies (channels) as possible within a certain range. Each channel must be a safe distance from other channels as well as a safe distance from any intermodulation products generated by multiple channel interactions.

An intermodulation (IM) product is created from the interaction between 2 or 3 frequencies. The following IM products need to be taken into account:

WHERE:
f1 = frequency 1
f2 = frequency 2
f3 = frequency 3

2T3O // 2 channel, 3rd Order = (2 * f1) - f2
                             = (2 * f2) - f1
2T5O // 2 channel, 5th Order = (3 * f1) - (2 * f2)
                             = (3 * f2) - (2 * f1)
3T3O // 3 channel, 3rd Order = f1 + f2 - f3
                             = f2 + f3 - f1
                             = f3 + f1 - f2

If we have one channel at 500 MHz, there is no IM and no channel interactions.

If we add one channel at 501 MHz, according to the formulas above, 2 x 2T3O IM products would be created at 499 MHz and 502 MHz and 2T50 IM products would be created at 498 MHz and 503 MHz due to the interactions between these 2 frequencies. No 3T3O IM products would be created.

If we add one more channel at 504 MHz, the previously calculated IM products remain, but new 2T3O IM products are generated due to the interactions of the 2 x previous frequencies with the new frequency at 496 MHz, 498 MHz, 507 MHz and 508 MHz. Similarly, new 2T5O IM products are generated at 492 MHz, 495 MHz, 510 MHz and 512 MHz. Also, as there are now 3 channels, 3T3O IM products will be generated at 497 MHz, 503 MHz and 505 MHz.

You could graph it as below, where asterisks are IM products, and the required channels are interleaved between at 500, 501 and 504 MHz.

Channel                                   -   -           -
                                          |   |           |
2T3O                      *       *   *   |   |   *       |           *   *
2T5O      *           *   |       *   |   |   |   |   *   |           |   |       *       *
3T3O      |           |   |   *   |   |   |   |   |   *   |   *       |   |       |       |
Freq.    492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512

On first glance, you could perhaps add another channel on 493MHz or 494MHz, but IM products between the new channel and the existing channels would have to be calculated to ensure that this would not cause any interference with current "clean" channels. Alternatively, these channels that are no longer clean could be recalculated to a new frequency.

When generating a new channel, it must be a certain "distance" from other channels and intermodulation products, which could be for example:

• Channel to channel spacing must be 0.3 MHz or more.
• Channel to 2T3O spacing must be 0.1 MHz or more.
• Channel to 2T5O spacing must be 0.09 MHz or more.
• Channel to 3T3O spacing must be 0.05 MHz or more.
• Each channel can tune to an accuracy of 0.025 MHz, so you can not create a channel at 500.01 MHz, only 500 or 500.025.

The Algorithm

I want to supply a start frequency and an end frequency, and to be able to compute as many clean channels as possible within this range. For example, given the following input:

calculate(startFrequency: 500, endFrequency: 508)

You might get the following output of valid frequencies:

[500.0, 500.3, 500.75, 501.85, 502.55, 503.5, 504.65, 505.65, 506.55, 507.15, 508.0]

This is however not the only possible output given this input. The algorithm should calculate as many frequencies as possible, given relevant restraints such as number of iterations or a time limit etc. It must also be able to scale up to a range of, ideally 200 MHz or so.

At present, using a single 8 MHz TV channel as a starting point, I can successfully derive 8 or 9 frequencies, whereas a commercial piece of software can easily calculate 11 instantaneously every time.

I have developed a reasonably quick algorithm to test a given set of frequencies for validity and generate a detailed report about intermodulation products and conflicts. I've tried randomly picking frequencies, starting from the lower bound and calculating the next valid frequency, but now I'm stuck. Any starting points or other ideas would be great!

Thanks in advance, Steve.

Answer 1

If you want to solve this in practice, you could express it as as an instance of integer linear programming and solve with an ILP solver.

Let's see how to test whether there is a way to fit $n$ channels in the given range, using an ILP solver. (You can then use binary search on $n$.) Introduce $n$ variables, $f_1,\dots,f_n$, to represent the $n$ frequencies. Then your first constraint has the form $|f_i-f_j| \ge 0.3$ for all $i,j$, the second constraint has the form $|(2f_i-f_j) - f_k| \ge 0.1$ for all $i,j,k$, and so on. You can express the first constraints by requiring $f_1 < \cdots < f_n$ and $f_j-f_i \ge 0.3$. You can express the second constraints by encoding the absolute value using a zero-or-one integer variable: namely, $|(2f_i-f_j) - f_k| \ge 0.1$ becomes $(2f_i-f_j) - f_k \ge 0.1 t_{i,j,k}$ and $f_k - (2f_i-f_j) \ge 0.1 (1-t_{i,j,k})$, where $0 \le t_{i,j,k} \le 1$ is constrained to be an integer. And so on. Now apply an off-the-shelf integer linear programming solver.

Of course this algorithm could become exponential-time in the worst case, but it might work in practice if $n$ is not too large. Whether this is effective in practice is something you could test empirically.