Cost minimisation in multi-interface networks

The paper focuses on the problem of minimisation of energy consumption by wireless devices. Since wireless communications are some of the main causes of battery drainage, connections must be carefully established. We study complexity issues of the so called Cost Minimisation in Multi-Interface Networks problem. Given a graph G = (V,E) with |V| = n and |E| = m, which models a set of wireless devices (nodes V) connected by multiple radio interfaces (edges E), the aim is to switch on the minimum cost set of interfaces at the nodes in order to satisfy all the connections. Every node holds a subset of all the possible k interfaces. A connection is satisfied when the endpoints of the corresponding edge share at least one active interface. We distinguish two main variations of the problem by treating the cost of maintaining an active interface as uniform (i.e., the same for all interfaces), or non-uniform. In general, we show that the problem is APX-hard while we obtain an approximation factor of min {(k+1)/2, 2m/n} for the uniform case and a (k − 1)-approximation for the non-uniform case. Next, we concentrate our attention on several classes of networks: with bounded degree, planar, with bounded treewidth and complete.