Energy consumption balancing in 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 a NP -completeness proof for the feasibility of the problem even considering the basic case of p= 2 and unitary costs for all the interfaces. That is, each interface costs the same as all the others. Then we provide optimal algorithms that solve the problem in polynomial time for different graph topologies and general costs associated to the interfaces.