TY - GEN
T1 - Algorithm design for base station placement problems in sensor networks
AU - Shi, Yi
AU - Hou, Y. Thomas
AU - Efrat, Alon
PY - 2006
Y1 - 2006
N2 - Base station placement has significant impact on sensor network performance. Despite its significance, results on this problem remain limited, particularly theoretical results that can provide performance guarantee. This paper proposes a set of procedure to design (1 - ) approximation algorithms for base station placement problems under any desired small error bound > 0. It offers a general framework to transform infinite search space to a finite-element search space with performance guarantee. We apply this procedure to solve two practical problems. In the first problem where the objective is to maximize network lifetime, an approximation algorithm designed through this procedure offers 1 / 2 complexity reduction when compared to a state-of-the-art algorithm. This represents the best known result to this problem. In the second problem, we apply the design procedure to address base station placement problem for maximizing network capacity. Our (1 - ) approximation algorithm is the first theoretical result on this problem.
AB - Base station placement has significant impact on sensor network performance. Despite its significance, results on this problem remain limited, particularly theoretical results that can provide performance guarantee. This paper proposes a set of procedure to design (1 - ) approximation algorithms for base station placement problems under any desired small error bound > 0. It offers a general framework to transform infinite search space to a finite-element search space with performance guarantee. We apply this procedure to solve two practical problems. In the first problem where the objective is to maximize network lifetime, an approximation algorithm designed through this procedure offers 1 / 2 complexity reduction when compared to a state-of-the-art algorithm. This represents the best known result to this problem. In the second problem, we apply the design procedure to address base station placement problem for maximizing network capacity. Our (1 - ) approximation algorithm is the first theoretical result on this problem.
UR - http://www.scopus.com/inward/record.url?scp=34547632699&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34547632699&partnerID=8YFLogxK
U2 - 10.1145/1185373.1185391
DO - 10.1145/1185373.1185391
M3 - Conference contribution
AN - SCOPUS:34547632699
SN - 1595935371
SN - 9781595935373
T3 - ACM International Conference Proceeding Series
BT - ACM International Conference Proceeding Series - Proceedings of the 3rd International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks
T2 - 3rd International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks
Y2 - 7 August 2006 through 8 September 2006
ER -