Building on previous work [Bonifaci et al., Minimizing flow time in the wireless gathering problem, STACS 2008] we study data gathering in a wireless network through multi-hop communication with the objective to minimize the average flow time of a data packet. We show that for any the problem is NP-hard to approximate within a factor better than, where m is the number of data packets. On the other hand, we give an online polynomial time algorithm that we analyze using resource augmentation. We show that the algorithm has average flow time bounded by that of an optimal solution when the clock speed of the algorithm is increased by a factor of five. As a byproduct of the analysis we obtain a 5-approximation algorithm for the problem of minimizing the average completion time of data packets. © 2008 Springer Berlin Heidelberg.

Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., Stougie, L. (2008). Minimizing average flow time in sensor data gathering. In Proc. 4th Conf. on Algorithmic Aspects of Wireless Sensor Networks (pp.18-29). Berlin : Springer [10.1007/978-3-540-92862-1_3].

Minimizing average flow time in sensor data gathering

Bonifaci V.;
2008-01-01

Abstract

Building on previous work [Bonifaci et al., Minimizing flow time in the wireless gathering problem, STACS 2008] we study data gathering in a wireless network through multi-hop communication with the objective to minimize the average flow time of a data packet. We show that for any the problem is NP-hard to approximate within a factor better than, where m is the number of data packets. On the other hand, we give an online polynomial time algorithm that we analyze using resource augmentation. We show that the algorithm has average flow time bounded by that of an optimal solution when the clock speed of the algorithm is increased by a factor of five. As a byproduct of the analysis we obtain a 5-approximation algorithm for the problem of minimizing the average completion time of data packets. © 2008 Springer Berlin Heidelberg.
2008
978-3-540-92861-4
Bonifaci, V., Korteweg, P., Marchetti-Spaccamela, A., Stougie, L. (2008). Minimizing average flow time in sensor data gathering. In Proc. 4th Conf. on Algorithmic Aspects of Wireless Sensor Networks (pp.18-29). Berlin : Springer [10.1007/978-3-540-92862-1_3].
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/11590/380495
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 1
social impact