Abstract
The notion of duty cycling is common in problems which seek to maximize the lifetime of a wireless sensor network. In the duty cycling model, sensors are grouped into shifts that take turns covering the region in question, and each sensor can belong to at most one shift. We consider the imposition of the duty cycling model upon the Strip Cover problem, where we are given n sensors on a one-dimensional region, and each shift can contain at most k ≤ n sensors. We call the problem of finding the optimal set of shifts so as to maximize the length of time that the entire region can be covered by a wireless sensor network, k-Duty Cycle Strip Cover (k-DutySC ). In this paper, we present a polynomial-time algorithm for 2-DutySC. Furthermore, we show that this algorithm is a \(\frac{35}{24}\)-approximation algorithm for k-DutySC. We also give two lower bounds: \(\frac{15}{11}\), for k ≥ 4, and \(\frac{6}{5}\), for k = 3, and provide experimental evidence suggesting that these lower bounds are tight. Finally, we propose a fault tolerance model and find thresholds on the sensor failure rate, over which our algorithm has the highest expected performance.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abrams, Z., Goel, A., Plotkin, S.A.: Set k-cover algorithms for energy efficient monitoring in wireless sensor networks. In: IPSN, pp. 424–432 (2004)
Aloupis, G., Cardinal, J., Collette, S., Langerman, S., Orden, D., Ramos, P.: Decomposition of multiple coverings into more parts. Discrete & Computational Geometry 44(3), 706–723 (2010)
Bar-Noy, A., Baumer, B.: Maximizing Network Lifetime on the Line with Adjustable Sensing Ranges. In: Erlebach, T., Nikoletseas, S., Orponen, P. (eds.) ALGOSENSORS 2011. LNCS, vol. 7111, pp. 28–41. Springer, Heidelberg (2012)
Bar-Noy, A., Baumer, B., Rawitz, D.: Set It and Forget It: Approximating the Set Once Strip Cover Problem. Arxiv preprint arXiv:1204.1082v1 (2012)
Buchsbaum, A., Efrat, A., Jain, S., Venkatasubramanian, S., Yi, K.: Restricted strip covering and the sensor cover problem. In: SODA, pp. 1056–1063 (2007)
Cardei, M., Du, D.: Improving wireless sensor network lifetime through power aware organization. Wireless Networks 11(3), 333–340 (2005)
Cardei, M., Wu, J., Lu, M.: Improving network lifetime using sensors with adjustable sensing ranges. Int. J. Sensor Networks 1(1/2), 41–49 (2006)
Cardei, M., Wu, J., Lu, M., Pervaiz, M.: Maximum network lifetime in wireless sensor networks with adjustable sensing ranges. In: WiMob (3), pp. 438–445 (2005)
Chambers, E.W., Fekete, S.P., Hoffmann, H.-F., Marinakis, D., Mitchell, J.S.B., Srinivasan, V., Stege, U., Whitesides, S.: Connecting a Set of Circles with Minimum Sum of Radii. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol. 6844, pp. 183–194. Springer, Heidelberg (2011)
Cook, W.J., Cunningham, W.H., William, R., Pulleyblank, A.S.: Combinatorial Optimization. John Wiley & Sons (1998)
Gibson, M., Varadarajan, K.: Decomposing coverings and the planar sensor cover problem. In: FOCS, pp. 159–168. IEEE (2009)
Lev-Tov, N., Peleg, D.: Polynomial time approximation schemes for base station coverage with minimum total radii. Computer Networks 47(4), 489–501 (2005)
Pach, J.: Covering the plane with convex polygons. Discrete & Computational Geometry 1(1), 73–81 (1986)
Pach, J., Tóth, G.: Decomposition of multiple coverings into many parts. Computational Geometry 42(2), 127–133 (2009)
Perillo, M., Heinzelman, W.: Optimal sensor management under energy and reliability constraints. In: Wireless Communications and Networking, vol. 3, pp. 1621–1626. IEEE (2003)
Slijepcevic, S., Potkonjak, M.: Power efficient organization of wireless sensor networks. In: IEEE Intl. Conf. on Communications, vol. 2, pp. 472–476 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bar-Noy, A., Baumer, B., Rawitz, D. (2012). Changing of the Guards: Strip Cover with Duty Cycling. In: Even, G., Halldórsson, M.M. (eds) Structural Information and Communication Complexity. SIROCCO 2012. Lecture Notes in Computer Science, vol 7355. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31104-8_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-31104-8_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31103-1
Online ISBN: 978-3-642-31104-8
eBook Packages: Computer ScienceComputer Science (R0)