Exact formulations for the minimum interference problem in k-connected ad hoc wireless networks

Energy consumption is one of the most critical issues in wireless ad hoc and sensor networks. A considerable amount of energy is dissipated due to radio transmission power and interference (message collisions). A typical topology control technique aims at reducing energy consumption while ensuring specific desired properties to the established wireless network (such as biconnectivity). Energy minimization can be achieved by reducing the transmission power and selecting edges that suffer or cause less interference. We propose four integer programming formulations for the k-connected minimum wireless ad hoc interference problem, which consists in a topology control technique to find a power assignment to the nodes of an ad hoc wireless network such that the resulting network topology is k-vertex connected and the radio interference is minimum. Interference is measured by three different models: Boolean, protocol, and physical. We report computational experiments comparing the formulations and interference models. Optimal solutions for moderately sized networks are obtained using a commercial solver.