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:
Comparative Study of Estimation Algorithms for Predistorter Coefficients of GaN Power Amplifier Read chapter Read first chapter

2018 | OriginalPaper | Chapter

Approximating Sweep Coverage Delay

Authors : Gokarna Sharma, Jong-Hoon Kim

Published in: Ubiquitous Networking

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

We consider the following fundamental sweep coverage problem that arises in mobile wireless sensor networks: Given a set of k mobile sensors and a set of m points of interests (POIs) in the Euclidean plane, how to schedule the mobile sensors such that the maximum delay between two subsequent visits to a POI by any sensor is minimized. We study two scenarios of this problem: (i) start positions of the sensors are fixed such that they must return to their start positions between subsequent traversals to POIs that fall in their trajectories, and (ii) sensor positions are not fixed and they are not required to return to their start positions between subsequent traversals. Scenario (i) models battery-constrained sensors which need to be recharged frequently, whereas scenario (ii) models sensors that have no constraint on battery and hence frequent recharging is not necessary. We present two constant factor approximation algorithms for each scenario. The problem we consider is NP-hard and, to the best of our knowledge, these are the first algorithms with guaranteed approximation bounds for this 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 Comparative Study of Estimation Algorithms for Predistorter Coefficients of GaN Power Amplifier
next chapter Cell Selection Game in 5G Heterogeneous Networks
Literature
1.
Bai, X., Xuan, D., Yun, Z., Lai, T.H., Jia, W.: Complete optimal deployment patterns for full-coverage and k-connectivity in wireless sensor networks. In: MobiHoc, pp. 401–410 (2008)
2.
Batalin, M.A., Sukhatme, G.S.: Multi-robot dynamic coverage of a planar bounded environment. Technical report (2002)
3.
Cardei, M., Thai, M.T., Li, Y., Wu, W.: Energy-efficient target coverage in wireless sensor networks. In: INFOCOM, pp. 1976–1984 (2005)
4.
Chen, A., Kumar, S., Lai, T.H.: Designing localized algorithms for barrier coverage. In: MobiCom, pp. 63–74 (2007)
5.
Chen, W., Chen, S., Li, D.: Minimum-delay pois coverage in mobile wireless sensor networks. EURASIP J. Wirel. Commun. Netw. 2013, 262 (2013)CrossRef
6.
Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report (1976)
7.
Ding, L., Wu, W., Willson, J., Wu, L., Lu, Z., Lee, W.: Constant-approximation for target coverage problem in wireless sensor networks. In: INFOCOM, pp. 1584–1592, March 2012
8.
Even, G., Garg, N., KöNemann, J., Ravi, R., Sinha, A.: Min-max tree covers of graphs. Oper. Res. Lett. 32(4), 309–315 (2004)MathSciNetCrossRef
9.
Frederickson, G.N., Hecht, M.S., Kim, C.E.: Approximation algorithms for some routing problems. In: FOCS, pp. 216–227 (1976)
10.
Gorain, B., Mandal, P.S.: Approximation algorithms for sweep coverage in wireless sensor networks. J. Parallel Distrib. Comput. 74(8), 2699–2707 (2014)CrossRef
11.
Gorain, B., Mandal, P.S.: Line sweep coverage in wireless sensor networks. In: COMSNETS, pp. 1–6 (2014)
12.
Hefeeda, M., Bagheri, M.: Randomized k-coverage algorithms for dense sensor networks. In: INFOCOM, pp. 2376–2380 (2007)
13.
Howard, A., Mataric, M.J., Sukhatme, G.S.: Mobile sensor network deployment using potential fields: a distributed, scalable solution to the area coverage problem. In: Asama, H., Arai, T., Fukuda, T., Hasegawa, T. (eds.) Distributed Autonomic Robotic Systems 5, pp. 299–308. Springer, Tokyo (2002). https://​doi.​org/​10.​1007/​978-4-431-65941-9_​30CrossRef
14.
15.
Kumar, S., Lai, T.H., Arora, A.: Barrier coverage with wireless sensors. In: MobiCom, pp. 284–298 (2005)
16.
Kumar, S., Lai, T.H., Balogh, J.: On k-coverage in a mostly sleeping sensor network. In: MobiCom, pp. 144–158 (2004)
17.
18.
Li, M., Cheng, W., Liu, K., He, Y., Li, X.Y., Liao, X.: Sweep coverage with mobile sensors. IEEE Trans. Mob. Comput. 10(11), 1534–1545 (2011)CrossRef
19.
Liang, W., Lin, X.: Approximation algorithms for min-max cycle cover problems. IEEE Trans. Comput. 64(3), 600–613 (2014)MathSciNetMATH
20.
Liu, B., Brass, P., Dousse, O., Nain, P., Towsley, D.: Mobility improves coverage of sensor networks. In: MobiHoc, pp. 300–308 (2005)
21.
Liu, B., Dousse, O., Wang, J., Saipulla, A.: Strong barrier coverage of wireless sensor networks. In: MobiHoc, pp. 411–420 (2008)
22.
23.
Saipulla, A., Westphal, C., Liu, B., Wang, J.: Barrier coverage with line-based deployed mobile sensors. Ad Hoc Netw. 11(4), 1381–1391 (2013)CrossRef
24.
Wan, P.J., Yi, C.W.: Coverage by randomly deployed wireless sensor networks. IEEE/ACM Trans. Netw. 14(SI), 2658–2669 (2006)MathSciNetMATH
25.
Wang, B.: Coverage problems in sensor networks: a survey. ACM Comput. Surv. 43(4), 32:1–32:53 (2011)CrossRef
26.
Wang, D., Liu, J., Zhang, Q.: Probabilistic field coverage using a hybrid network of static and mobile sensors. In: IWQoS, pp. 56–64 (2007)
27.
28.
Wang, W., Srinivasan, V., Chua, K.-C.: Trade-offs between mobility and density for coverage in wireless sensor networks. In: MobiCom, pp. 39–50 (2007)
29.
Wang, X., Xing, G., Zhang, Y., Lu, C., Pless, R., Gill, C.: Integrated coverage and connectivity configuration in wireless sensor networks. In: SenSys, pp. 28–39 (2003)
30.
Xi, M., Wu, K., Qi, Y., Zhao, J., Liu, Y., Li, M.: Run to potential: sweep coverage in wireless sensor networks. In: ICPP, pp. 50–57 (2009)
31.
Zhou, Z., Das, S., Gupta, H.: Connected k-coverage problem in sensor networks. In: ICCCN, pp. 373–378 (2004)
32.
Zou, Y., Chakrabarty, K.: Sensor deployment and target localization based on virtual forces. In: INFOCOM (2003)
Metadata
Title
Approximating Sweep Coverage Delay
Authors
Gokarna Sharma
Jong-Hoon Kim
Copyright Year
2018
Book
Ubiquitous Networking

Print ISBN: 978-3-030-02848-0

Electronic ISBN: 978-3-030-02849-7

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-030-02849-7_2

Premium Partner

    Image Credits