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(2)P}) time, where n and P are the number of nodes and the path length of the tree [7], 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 [8]. (C) 2015 Elsevier B.V. All rights reserved.

The minimum k-storage problem on directed graphs

D'Angelo G;
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(2)P}) time, where n and P are the number of nodes and the path length of the tree [7], 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 [8]. (C) 2015 Elsevier B.V. All rights reserved.
Wireless sensor networks; Storage placement; Optimal algorithms; Dynamic programming
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12571/589
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact