A 2-Approximation Algorithm for Optimal Deployment of k Base Stations in WSNsReportar como inadecuado




A 2-Approximation Algorithm for Optimal Deployment of k Base Stations in WSNs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 UNSW - School of Computer Science and Engineering

Abstract : We study the problem of deploying k base stations in a wireless sensor network such that the maximum shortest hop distance from all the sensor nodes to their designated base stations is minimised. We propose a 2-approximation algorithm for this problem, and prove that a 2 − ε-approximation algorithm does not exist unless P = NP holds. The time complexity of our 2-approximation algorithm is On2 logn, where n is the number of sensor nodes of the wireless sensor network. In the special case where k is 1, we propose an On2 time algorithm that is guaranteed to find the optimal location of the base station. Furthermore, we show that our previous heuristic for balancing clusters of sensors can be modified to significantly improve the performance of our 2-approximation algorithm.





Autor: Hui Wu - Sabbir Mahmud -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados