Balancing energy consumption for the establishment of Multi-Interface networks

In heterogeneous networks, devices can communicate by means of multiple interfaces. By choosing which interfaces to activate (switch-on) at each device, several connections might be established. A connection is established when the devices at its endpoints share at least one active interface. Interfaces are associated with a cost defining the percentage of energy consumed to switch-on the corresponding interface. In this paper, we consider the case where each device is limited to activate at most a fixed number p of its available interfaces in order to accomplish the required task. In particular, we consider the so-called Coverage problem. Given a network G = (V,E), nodes V represent devices, edges E represent connections that can be established. The aim is to activate at most p interfaces at each node in order to establish all the connections defined by E. Parameter p implies a sort of balanced consumption among devices so that none of them suffers - in terms of consumed energy - for being exploited in the network more than others. We provide an NP-completeness proof for the feasibility of the problem even considering the basic case of p = 2 and unitary costs for all the interfaces. Then we provide optimal algorithms that solve the problem in polynomial time for different graph topologies and general costs associated to the interfaces.