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. A connection is satisfied when the endpoints of the corresponding edge share at least one active interface. Every node holds a subset of all the possible k interfaces. The problem is called Cost Minimisation in Unbounded Multi-Interface Networks and in [1] the case with bounded k was studied. In this paper we generalise the model by considering the unbounded version of the problem, i.e., k is not set a priori but depends on the given instance. 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 prove that the problem is not approximable within O(log k) while it holds min{(k+1)/2, 2m/n} -approximation factor for the uniform case and min {k−1, sqrt(n)(1+ ln n)-approximation factor for the non-uniform case. Next, we also provide hardness and approximation results for several classes of networks: with bounded degree, trees, planar and complete graphs.
Cost minimisation in unbounded multi-interface networks
NAVARRA, Alfredo
2007
Abstract
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. A connection is satisfied when the endpoints of the corresponding edge share at least one active interface. Every node holds a subset of all the possible k interfaces. The problem is called Cost Minimisation in Unbounded Multi-Interface Networks and in [1] the case with bounded k was studied. In this paper we generalise the model by considering the unbounded version of the problem, i.e., k is not set a priori but depends on the given instance. 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 prove that the problem is not approximable within O(log k) while it holds min{(k+1)/2, 2m/n} -approximation factor for the uniform case and min {k−1, sqrt(n)(1+ ln n)-approximation factor for the non-uniform case. Next, we also provide hardness and approximation results for several classes of networks: with bounded degree, trees, planar and complete graphs.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
