Energy-Efficient Communication in Multi-interface Wireless Networks

We study communication problems in wireless networks supporting multiple interfaces. In such networks, two nodes can communicate if they are close and share a common interface. The activation of each interface has a cost reflecting the energy consumed when a node uses this interface. We distinguish between the symmetric and non-symmetric case, depending on whether all nodes have the same activation cost for each interface or not. For the symmetric case, we present a (3/2 + 驴)---approximation algorithm for the problem of achieving connectivity with minimum activation cost, improving a previous bound of 2. For the non-symmetric case, we show that the connectivity problem is not approximable within a sublogarithmic factor in the number of nodes and present a logarithmic approximation algorithm for a more general problem that models group communication.