nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Barrier Coverage with Uniform Radii in 2D

verfasst von : Andrew Cherry, Joachim Gudmundsson, Julián Mestre

Erschienen in: Algorithms for Sensor Systems

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Given a set B of disjoint line segments in the plane, the so-called barriers, and a set of n sensors with uniform range in the plane, the barrier coverage problem is to move the sensors so that they cover the segments in B, while minimizing the total movement of the sensors. In the 1D case when B contains a single barrier and all the sensors lie on B then the problem can be solved in \(O(n \log n)\) time. In 2D very little is known about the complexity of the problem.

We consider the 2D setting and give a \(\sqrt{2}\)-approximation algorithm when B contains a single barrier, or a set of parallel barriers. We also give an approximation algorithm for arbitrarily oriented disjoint barriers.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Fast Distributed Approximation for Max-Cut

Nächstes Kapitel Rendezvous on a Line by Location-Aware Robots Despite the Presence of Byzantine Faults

Arora, A., Ramnath, R., Ertin, E., Sinha, P., Bapat, S., Naik, V., Kulathumani, V., Zhang, H., Cao, H., Sridharan, M., Kumar, S., Seddon, N., Anderson, C., Herman, T., Trivedi, N., Zhang, C., Nesterenko, M., Shah, R., Kulkarni, S.S., Aramugam, M., Wang, L., Gouda, M.G., Choi, Y.-R., Culler, D.E., Dutta, P., Sharp, C., Tolle, G., Grimmer, M., Ferriera, B., Parker, K.: ExScal: elements of an extreme scale wireless sensor network. In: 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), pp. 102–108 (2005)

Bhattacharya, B.K., Burmester, B., Hu, Y., Kranakis, E., Shi, Q., Wiese, A.: Optimal movement of mobile sensors for barrier coverage of a planar region. Theor. Comput. Sci. 410(52), 5515–5528 (2009)MathSciNetCrossRefMATH

Chen, A., Kumar, S., Lai, T.: Local barrier coverage in wireless sensor networks. IEEE Trans. Mob. Comput. 9(4), 491–504 (2010)CrossRef

Czyzowicz, J., Kranakis, E., Krizanc, D., Lambadaris, I., Narayanan, L., Opatrny, J., Stacho, L., Urrutia, J., Yazdani, M.: On minimizing the sum of sensor movements for barrier coverage of a line segment. In: Nikolaidis, I., Wu, K. (eds.) ADHOC-NOW 2010. LNCS, vol. 6288, pp. 29–42. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14785-2_3 CrossRef

Dobrev, S., Durocher, S., Eftekhari, M., Georgiou, K., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Shende, S., Urrutia, J.: Complexity of barrier coverage with relocatable sensors in the plane. Theor. Comput. Sci. 579, 64–73 (2015)MathSciNetCrossRefMATH

Huang, C.-F., Tseng, Y.-C.: The coverage problem in a wireless sensor network. Mob. Netw. Appl. 10(4), 519–528 (2005)CrossRef

Kumar, S., Lai, T.-H., Arora, A.: Barrier coverage with wireless sensors. In: Proceedings of the 11th Annual International Conference on Mobile Computing and Networking (MOBICOM), MobiCom 2005, pp. 284–298. ACM (2005)

Meguerdichian, S., Koushanfar, F., Potkonjak, M., Srivastava. M.B.: Coverage problems in wireless ad-hoc sensor networks. In: Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies INFOCOM, vol. 3, pp. 1380–1387 (2001)

Mestre, J., Gaspers, S., Gudmundsson, J., Rümmele, S.: Barrier coverage with non-uniform length to minimize aggregate movements (2017, submitted manuscript)

10.

Tan, X., Wu, G.: New Algorithms for Barrier Coverage with Mobile Sensors. Springer, Heidelberg (2010). pp. 327–338CrossRefMATH

11.

Tao, D., Wu, T.Y.: A survey on barrier coverage problem in directional sensor networks. IEEE Sens. J. 15(2), 876–885 (2015)CrossRef

12.

Wu, F., Gui, Y., Wang, Z., Gao, X., Chen, G.: A survey on barrier coverage with sensors. Front. Comput. Sci. 10(6), 968–984 (2016)CrossRef

Titel: Barrier Coverage with Uniform Radii in 2D
verfasst von: Andrew Cherry
Joachim Gudmundsson
Julián Mestre
Verlag: Springer International Publishing
Buch: Algorithms for Sensor Systems
Print ISBN: 978-3-319-72750-9

Electronic ISBN: 978-3-319-72751-6

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-72751-6_5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"