TY - GEN
T1 - Constant-approximation for target coverage problem in wireless sensor networks
AU - Ding, Ling
AU - Wu, Weili
AU - Willson, James
AU - Wu, Lidong
AU - Lu, Zaixin
AU - Lee, Wonjun
PY - 2012
Y1 - 2012
N2 - When a large amount of sensors are randomly deployed into a field, how can we make a sleep/activate schedule for sensors to maximize the lifetime of target coverage in the field? This is a well-known problem, called Maximum Lifetime Coverage Problem (MLCP), which has been studied extensively in the literature. It is a long-standing open problem whether MLCP has a polynomial-time constant-approximation. The best-known approximation algorithm has performance ratio 1 + ln n where n is the number of sensors in the network, which was given by Berman et. al [1]. In their work, MLCP is reduced to Minimum Weight Sensor Coverage Problem (MWSCP) which is to find the minimum total weight of sensors to cover a given area or a given set of targets with a given set of weighted sensors. In this paper, we present a polynomial-time (4 + ε)-approximation algorithm for MWSCP and hence we obtain a polynomial-time (4+ξ)-approximation algorithm for MLCP, where ε > 0, ξ > 0.
AB - When a large amount of sensors are randomly deployed into a field, how can we make a sleep/activate schedule for sensors to maximize the lifetime of target coverage in the field? This is a well-known problem, called Maximum Lifetime Coverage Problem (MLCP), which has been studied extensively in the literature. It is a long-standing open problem whether MLCP has a polynomial-time constant-approximation. The best-known approximation algorithm has performance ratio 1 + ln n where n is the number of sensors in the network, which was given by Berman et. al [1]. In their work, MLCP is reduced to Minimum Weight Sensor Coverage Problem (MWSCP) which is to find the minimum total weight of sensors to cover a given area or a given set of targets with a given set of weighted sensors. In this paper, we present a polynomial-time (4 + ε)-approximation algorithm for MWSCP and hence we obtain a polynomial-time (4+ξ)-approximation algorithm for MLCP, where ε > 0, ξ > 0.
UR - https://www.scopus.com/pages/publications/84861618557
U2 - 10.1109/INFCOM.2012.6195527
DO - 10.1109/INFCOM.2012.6195527
M3 - Conference contribution
AN - SCOPUS:84861618557
SN - 9781467307758
T3 - Proceedings - IEEE INFOCOM
SP - 1584
EP - 1592
BT - 2012 Proceedings IEEE INFOCOM, INFOCOM 2012
T2 - IEEE Conference on Computer Communications, INFOCOM 2012
Y2 - 25 March 2012 through 30 March 2012
ER -