Using N-body algorithms for interference computation in wireless cellular simulations

A comprehensive simulation model of wireless cellular networks must include the computation of transmitter power levels. In such systems, as time evolves, powers are continuously updated to minimize interference and maintain signal quality. Transmitters operate at the minimum power required to meet a target signal to noise ratio (SNR), which, in the real system, can be promptly estimated since the values involved come from direct measurements. In a simulation model, however, the interference over each receiver is a quantity that must be computed and the associated costs are not low. A system with N pairs of transmitters and receivers requires that O(N²) pairwise interactions be computed; it's easy to see how very large the workload is when we consider that, in order to advance simulated time by one second, this large computation may have to be performed hundreds of times. In this paper, we show that techniques devised for the simulation of systems of self-gravitating bodies (N-body problem) can be successfully applied to reduce the complexity of interference computations in simulations of wireless systems. However, our experiments suggest simple distance-based truncation may be the superior method.