Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Numerical Computations with Infinite and Infinitesimal Numbers: Theory and Applications Read chapter Read first chapter

2013 | OriginalPaper | Chapter

Minimum Connected Sensor Cover and Maximum-Lifetime Coverage in Wireless Sensor Networks

Authors : Lidong Wu, Weili Wu, Kai Xing, Panos M. Pardalos, Eugene Maslov, Ding-Zhu Du

Published in: Dynamics of Information Systems: Algorithmic Approaches

Publisher: Springer New York

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Energy efficiency is an important issue in the study of wireless sensor networks. The minimum connected sensor cover problem and the maximum lifetime coverage problem are very well known in the literature on energy efficiency. In recent years, there are important developments in the study of these two problems through studying the relationship between the connected sensor cover and the group Steiner tree and the relationship between coverage and weighted dominating set. In this article, we introduce those relationships and related new developments on the minimum connected sensor cover problem and the maximum lifetime coverage problem.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Models for Assessing Vulnerability in Imperfect Sensor Networks
next chapter Influence Diffusion, Community Detection, and Link Prediction in Social Network Analysis
Literature
1.
S.M.N. Alam and Z.J. Haas, Coverage and connectivity in three-dimensional networks, MobiCom’06, 2006.
2.
C. Ambühl, T. Erlebach, M. Mihalák and M. Nunkesser, Constant-approximation for minimum-weight (connected) dominating sets in unit disk graphs, Proceedings of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2006), LNCS 4110, Springer, 2006, pp. 3–14.
3.
X. Bai, S. Kumar, D. Xuan, Z. Yun, and T.H. Lai, DEploying wireless sensors to achieve both coverage and connectivity, MobiHoc’06, 2006, pp.131–142.
4.
Y. Bartal, Probability approximation of metric spaces and its algorithmic applications, Proc of 37th FOCS, 1996, pp. 184–193.
5.
Y. Bartal, On approximating arbitrary metrics by tree metrics, Proc of 30th STOC, 1998, pp. 161–168.
6.
Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoss and Laura Sanita, An improved LP-based approximation for Steiner tree, STOC’10, June 5–8, 2010, pp. 583–592.
7.
M. Cardei, Coverage problems in sensor networks, Handbook of Combinatorial Optimization (2nd Edition), P. M. Pardalos, D. Z. Du, and R. Graham (eds.), Springer, to appear.
8.
M. Cardei and D.-Z. Du, Improving wireless sensor network lifetime through power aware organization, ACM Wireless Networks, Vol. 11, No. 3, pp. 333–340, May 2005.CrossRef
9.
M. Cardei and J. Wu, Coverage in wireless sensor networks, in Handbook of Sensor Networks, M.Ilyas and I. Mahgoub (eds.), CRC Press, 2004.
10.
Mihaela Cardei, Dave MacCallum, Xiuzhen Cheng, Manki Min, Xiaohua Jia, Deying Li and Ding-Zhu Du, Wireless sensor networks with energy efficient organization, Journal of Interconnection Networks vol 3 no 3–4 (2002) 213–229.CrossRef
11.
Mihaela Cardei, My Thai, Yingshu Li, and Weili Wu, Energy-efficient target coverage in wireless sensor networks, IEEE INFOCOM (2005).
12.
J. Carle and D. Simplot, Energy efficient area monitoring by sensor networks, IEEE Computer Vol 37, No 2 (2004) 40–46.CrossRef
13.
Maggie X. Cheng, Lu Ruan and Weili Wu, Achieving minimum coverage breach under bandwidth constraints in wireless sensor networks, INFOCOM 2005, pp. 2638–2645.
14.
Maggie Xiaoyan Cheng, Lu Ruan, Weili Wu, Coverage breach problems in bandwidth-constrained sensor networks, TOSN 3(2): 12 (2007).
15.
C. Chekuri, G. Even and G. Kortsarz, A greedy approximation algorithm for the group Steiner problem, Discrete Applied Mathematics, 154 (2006) 15–34.MathSciNetMATHCrossRef
16.
Ling Ding, Weili Wu, James K. Willson, Lidong Wu, Zaixin Lu and Wonjun Lee, Constant-approximation for target coverage problem in wireless sensor networks, Proc. of The 31st Annual Joint Conf. of IEEE Communication and Computer Society (INFOCOM), 2012.
17.
D.-Z. Du, Ker-I Ko, and X. Hu, Design and Analysis of Approximation Algorithms, Springer, 2012, pp. 142–157.
18.
Hongwei Du, Panos M. Pardalos, Weili Wu, Lidong Wu, Maximum Lifetime Connected Coverage with Two Active-Phase Sensors, Journal of Global Optimization, online in 2012.
19.
T. Erlebach and M. Mihalk, A (4 + ε)-approximation for the minimum-weight dominating set problem in unit disk graphs, WAOA 2009, pp. 135–146.
20.
G. Even, G. Kortsarz, An approximation algorithm for the group Steiner problem, Proceedings of SODA, 2002, pp. 49–58.
21.
S. Funke, A. Kesselman, F. Kuhn, Z. Lotker, and M. Segal, Improved approximation algorithms for connected sensor cover, Wireless Networks 13 (2007) 153–164.CrossRef
22.
N. Garg and J. Könemann, Faster and simpler algorithms for multicommodity flows and other fractional packing problems, Proc. 39th Annual Symposium on the Foundations of Computer Science, 1998, pp 300–309.
23.
N. Garg, G. Konjevod and R. Ravi, A polylogarithmic approximation algorithm for the group Steiner tree problem, SODA, 2000.
24.
A. Ghosh and S.K. Das, A distributed greedy algorithm for connected sensor cover in dense sensor networks, LNCS 3560 (2005) 340–353.
25.
A. Ghosh and S.K. Das, Coverage and connectivity issues in wireless sensor networks, in Movile, Wireless, and Sensor Networks: Technology, Applications, and Future Directions, by R. Shorey, A.L. Ananda, M.C. Chan, and W.T. Ooi (eds.), John Wiley & Sons, Inc., 2006, pp. 221–256.
26.
H. Gupta, S.R. Das and Q. Gu, Connected sensor cover: self-organization of sensor networks for efficient query execution, MobiHoc’03, 2003, pp. 189–200.
27.
Eran Halperin, Robert Krauthgamer: Polylogarithmic inapproximability. STOC 2003: 585–594.
28.
Y. Huang, X. Gao, Z. Zhang and W. Wu, A better constant-factor approximation for weighted dominating set in unit disk graph, Journal of Combinatorial Optimization 18 (2009) 174–194.MathSciNetCrossRef
29.
K. Kar and S. Banerjee, Node placement for connected coverage in sensor networks, Proc. of WiOpt 2003: Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, 2003.
30.
S. Slijepcevic and M. Potkonjak, Power efficient organization of wireless sensor networks, IEEE International Conference on Communications, Jun. 2001, pp. 472–476.
31.
D. Tian and N. D. Georganas, A coverage-preserving node se scheduling scheme for large wireless sensor networks, Proc. of 1st ACM Workshop on Wireless Sensor Networks and Applications, 2002.
32.
X. Wang, G. Xing, Y. Zhang, C. Lu, R. Pless, C. Gill, Integrated coverage and connectivity configuration in wireless sensor networks, Proceedings of the 1st International Conference on Embedded Networked Sensor Systems, Sensys.03, Los Angeles, CA, November 2003, pp. 28–39.
33.
L. Wu, H. Du, W. Wu, D. Li, J. Lv, and W. Lee, Approximations for Minimum Connected Sensor Cover, IEEE Conference on Computer Communications, 2013.
34.
G. Xing, X. Wang, Y. Zhang, C. Liu, R. Pless, and C. Gill, Integrated coverage and connectivity configuration for energy conservation in sensor networks, ACM Transactions on Sensor Networks, vol. 1 no. 1 (2005) 36–72.CrossRef
35.
S. Yang, F. Dai, M. Cardei, J. Wu and F. Patterson, On connected multiple point coverage in wireless sensor networks, Journal of Wireless Information Networks 13 (2006), pp. 289–301CrossRef
36.
H. Zhang and J. C. Hou, Maintaining sensing coverage and connectivity in large sensor networks, Ad Hoc & Sensor Wireless Networks 1 (2005) 89–124.
37.
Z. Zhou, S. Das, H. Gupta, Connected k-coverage problem in sensor networks, Proceedings of the 13th International Conference on Computer Communications and Networks, 2004, pp. 373–378.
38.
Z. Zhou, S.R. Das, H. Gupta, Variable radii connected sensor cover in sensor networks, ACM Transactions on Sensor Networks, vol. 5 no. 1 (2009).
39.
F. Zou, X. Li, S. Gao, and W. Wu, Node-weighted Steiner tree approximation in unit disk graphs, J. Comb. Optim. 18 (2009) 342–349.MathSciNetMATHCrossRef
40.
Feng Zou, Yuexuan Wang, Xiaohua Xu, Hongwei Du, Xianyue Li, Pengjun Wan and Weili Wu, New approximations for weighted dominating sets and connected dominating sets in unit disk graphs, Theoretical Computer Science vol 412 no 3 (2011) 198–208.MathSciNetMATHCrossRef
Metadata
Title
Minimum Connected Sensor Cover and Maximum-Lifetime Coverage in Wireless Sensor Networks
Authors
Lidong Wu
Weili Wu
Kai Xing
Panos M. Pardalos
Eugene Maslov
Ding-Zhu Du
Copyright Year
2013
Publisher
Springer New York
Book
Dynamics of Information Systems: Algorithmic Approaches

Print ISBN: 978-1-4614-7581-1

Electronic ISBN: 978-1-4614-7582-8

Copyright Year: 2013

DOI
https://doi.org/10.1007/978-1-4614-7582-8_10