In standard sensor network applications, sensors generate raw data that have to be sent to a sink node. In order to save energy, special intermediate storage nodes can be exploited in order to compress data before forwarding them to the sink. We consider the problem of locating k storage nodes in order to minimize the energy consumed for converging data to the sink. This is known as the minimum k-storage problem. We show that in directed graphs (and in particular in Directed Acyclic Graphs) the problem does not admit an algorithm with a constant approximation ratio, unless P=NP. If the topology is restricted to trees where the arcs are directed towards the sink (typical scenario in sensor networks), the problem is solvable in polynomial time. We give a dynamic programming algorithm that requires O(min{kn^2,k^2P}) time, where n and P are the number of nodes and the path length of the tree, respectively. We improve over a previous algorithm which requires O(kn^2(max{k,d})^(d−1)) time, where d is the maximum out-degree of the tree.
The minimum k-storage problem on directed graphs
DIODATI, DANIELE;NAVARRA, Alfredo;PINOTTI, Maria Cristina
2015
Abstract
In standard sensor network applications, sensors generate raw data that have to be sent to a sink node. In order to save energy, special intermediate storage nodes can be exploited in order to compress data before forwarding them to the sink. We consider the problem of locating k storage nodes in order to minimize the energy consumed for converging data to the sink. This is known as the minimum k-storage problem. We show that in directed graphs (and in particular in Directed Acyclic Graphs) the problem does not admit an algorithm with a constant approximation ratio, unless P=NP. If the topology is restricted to trees where the arcs are directed towards the sink (typical scenario in sensor networks), the problem is solvable in polynomial time. We give a dynamic programming algorithm that requires O(min{kn^2,k^2P}) time, where n and P are the number of nodes and the path length of the tree, respectively. We improve over a previous algorithm which requires O(kn^2(max{k,d})^(d−1)) time, where d is the maximum out-degree of the tree.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
