HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

A 2-Approximation Algorithm for Optimal Deployment of k Base Stations in WSNs

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.
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Friday, June 2, 2017 - 11:23:18 AM
Last modification on : Thursday, June 6, 2019 - 2:42:14 PM
Long-term archiving on: : Wednesday, December 13, 2017 - 9:28:43 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Hui Wu, Sabbir Mahmud. A 2-Approximation Algorithm for Optimal Deployment of k Base Stations in WSNs. 11th International Networking Conference (NETWORKING), May 2012, Prague, Czech Republic. pp.378-391, ⟨10.1007/978-3-642-30054-7_30⟩. ⟨hal-01531960⟩



Record views


Files downloads