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 O(n2 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 O(n2) 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.
Type de document :
Communication dans un congrès
Robert Bestak; Lukas Kencl; Li Erran Li; Joerg Widmer; Hao Yin. 11th International Networking Conference (NETWORKING), May 2012, Prague, Czech Republic. Springer, Lecture Notes in Computer Science, LNCS-7290 (Part II), pp.378-391, 2012, NETWORKING 2012. 〈10.1007/978-3-642-30054-7_30〉
https://hal.inria.fr/hal-01531960
Contributeur : Hal Ifip
<>
Soumis le : vendredi 2 juin 2017 - 11:23:18
Dernière modification le : dimanche 11 février 2018 - 16:56:02
Document(s) archivé(s) le : mercredi 13 décembre 2017 - 09:28:43
Hui Wu, Sabbir Mahmud. A 2-Approximation Algorithm for Optimal Deployment of k Base Stations in WSNs. Robert Bestak; Lukas Kencl; Li Erran Li; Joerg Widmer; Hao Yin. 11th International Networking Conference (NETWORKING), May 2012, Prague, Czech Republic. Springer, Lecture Notes in Computer Science, LNCS-7290 (Part II), pp.378-391, 2012, NETWORKING 2012. 〈10.1007/978-3-642-30054-7_30〉. 〈hal-01531960〉
