Channel allocation algorithm

Question

We have a set of radio nodes in close proximity to each other and would like to allocate the frequencies for them to minimize overlap. To get complete coverage of the area, radio channels need to be oversubscribed and so we will have nearby radios transmitting on the same frequency.

Sample data:
5 Frequencies
343 Radios
4158 Edges

My current best guess is to randomly generate a population of frequency allocations and to swap frequencies between radios until the best score does not improve for 10 generations. Score is the sum of 1/range^2 for radios on the same frequency.

Each edge is the distance between the radios, corrected for walls and floors. Edges above 2* the max radio range have been culled from the list.

Is there a better way?

Answer 1

I agree that a simulation based on random initial assignment followed by some optimization is a good approach, but you're describing an optimization procedure which does not seem optimal, if I understand correctly (you're planning to swap frequencies at random if I read you correctly). At each optimization step you could pick a "reasonable" improvement by taking one radio from each frequency group and considering the 5*4/2=10 possible swaps of frequencies between two of them, and either choose the best, or (say) one of those which has positive delta score, with probabilities proportional to the deltas in the scores.

In the spirit of "simulated annealing", once the overall score seems to have more or less stabilized, you may want to switch for a small number of steps to "high temperature" (high randomness) where you just pick the set of 5 radios and swap them all e.g. with a circular permutation of frequency assignments -- do that a few times then go to the "cooling down" part again with the procedure in the above paragraph (which tries to get a cheap simulation of a maximum-gradient descent;-).

Answer 2

My quick stab at it would be to use a thin plate spline (or possibly a similar, cleverer linear algebra technique) to fit a plane to the function of frequency density. The average 'altitude' of each plane (per frequency) would then tell you whether a frequency is overused (i.e. when it's higher than the others); the slope would be an indication of the spatial distribution.

Answer 3

This is basically a graph-coloring problem with a twist. Rather than all proper colorings being equally good, some proper colorings are better than others, as defined by your scoring algorithm.

I think your genetic approach is practical and will yield good (if not provably optimal) solutions, but I would definitely suggest looking at some graph-coloring papers and seeing how applicable they are. It is very likely that you will get some great ideas for deciding how your algorithm should consider the available choices.