P-Dits for the Frequency Assignment Problem With Transmitter Deactivation in Dense Environments

The frequency assignment problem is a non-deterministic polynomial-time hard optimization problem concerning the assignment of frequency channels to wireless transmitters. Typically, the aim is to minimize interference between transmitters while maintaining a high level of service. In this work, the use of probabilistic d-dimensional bits, or p-dits, for this task is considered. These are stochastic elements which oscillate between discrete states that lie in a multi-dimensional space. Here, each dimension corresponds to an allowed wireless channel. Additionally, a special 0 state exists which corresponds to a disabled, and consequently completely non-interfering transmitter. Each transmitter maps to a single p-dit that undergoes repeatable stochastic updates. The p-dit influences the probability distributions of its neighbors, biasing them towards non-interfering states. To provide a realistic and varied dataset, geospatial data for a medium-sized city was used. A simple greedy, Tabu-style, DSatur-style, a traditional p-bit based probabilistic Ising machine solver, and the proposed p-dit based probabilistic Ising machine solver, were tasked with finding an assignment which penalized both deactivated transmitters and interference on a two, three, and four wireless channel problem. Overall, for the same non-trivially short runtime budgets, the probabilistic Ising machine solver found the highest quality solutions of all the approaches explored.