×

The minimum \(k\)-storage problem on directed graphs. (English) Zbl 1328.68146

Summary: 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 \(\mathrm{P} = \mathrm{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 \{k n^2, k^2 P \})\) 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(k n^2(\max \{k, d \})^{d - 1})\) time, where \(d\) is the maximum out-degree of the tree [B. Sheng, Q. Li and W. Mao, “Optimize storage placement in sensor networks”, IEEE Trans. Mobile Comput. 9, No. 10, 1437–1450 (2010; doi:10.1109/TMC.2010.98)].

MSC:

68R10 Graph theory (including graph drawing) in computer science
68W25 Approximation algorithms
90C35 Programming involving graphs or networks
90C39 Dynamic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bertossi, A. A.; Diodati, D.; Pinotti, C. M., Storage placement in path networks, IEEE Trans. Comput., 64, 4, 1201-1207 (2015) · Zbl 1360.68139
[2] D’Angelo, G.; Diodati, D.; Navarra, A.; Pinotti, C. M., Approximation bounds for the minimum \(k\)-storage problem, (Proc. of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics. Proc. of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS. Proc. of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics. Proc. of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS, LNCS, vol. 8243 (2013), Springer), 123-138 · Zbl 1397.68054
[3] Dinur, I.; Steurer, D., Analytical approach to parallel repetition, (Proc. of the 46th ACM Symposium on Theory of Computing. Proc. of the 46th ACM Symposium on Theory of Computing, STOC (2014), ACM), 624-633 · Zbl 1315.91001
[4] Ganesan, D.; Greenstein, B.; Estrin, D.; Heidemann, J. S.; Govindan, R., Multiresolution storage and search in sensor networks, Trans. Storage, 1, 3, 277-315 (2005)
[5] Gehrke, J.; Madden, S., Query processing in sensor networks, IEEE Pervasive Computing, 3, 1, 46-55 (2004)
[6] Guha, S.; Khuller, S., Greedy strikes back: improved facility location algorithms, J. Algorithms, 31, 1, 228-248 (1999) · Zbl 0928.68137
[7] Sedgewick, R.; Flajolet, P., An Introduction to the Analysis of Algorithms (1996), Addison-Wesley
[8] Sheng, B.; Li, Q.; Mao, W., Optimize storage placement in sensor networks, IEEE Trans. Mob. Comput., 9, 10, 1437-1450 (2010)
[9] Sheng, B.; Tan, C. C.; Li, Q.; Mao, W., An approximation algorithm for data storage placement in sensor networks, (Proc. of the 2nd International Conference on Wireless Algorithms, Systems and Applications. Proc. of the 2nd International Conference on Wireless Algorithms, Systems and Applications, WASA (2007), IEEE), 71-78
[10] Shenker, S.; Ratnasamy, S.; Karp, B.; Govindan, R.; Estrin, D., Data-centric storage in sensornets, Comput. Commun. Rev., 33, 1, 137-142 (2003)
[11] Tamir, A., An \(O(p n^2)\) algorithm for the \(p\)-median and related problems on tree graphs, Oper. Res. Lett., 19, 2, 59-64 (Aug. 1996) · Zbl 0865.90089
[12] Tilak, S.; Abu-Ghazaleh, N. B.; Heinzelman, W. R., A taxonomy of wireless micro-sensor network models, Mob. Comput. Commun. Rev., 6, 2, 28-36 (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.