Collision scheduling for cellular networks

Consider a cellular network composed of several base stations with overlapping coverage areas. Conventional scheduling algorithms ensure that each base station hears only a single user over each orthogonal sub-channel, i.e., collisions are avoided. Recent work on compute-and-forward has demonstrated that it is possible for a receiver to decode a linear combination of interfering codewords. We examine how the adoption of the compute-and-forward technique affects the scheduling problem for cellular networks. Specifically, instead of avoiding collisions, the base stations can schedule collisions to obtain a set of linear combinations that can be solved for the original messages. For the special case of two base stations, we propose a simple scheduling algorithm that finds the minimal number of sub-channels needed for each user to successfully communicate one packet. For the general case, we formulate an integer program that can be solved using dynamic programming with pseudo-polynomial complexity with respect to the number of users.