Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Composition and Scaling Challenges in Sensor Networks: An Interaction-Centric View Kapitel lesen Erstes Kapitel lesen

2011 | OriginalPaper | Buchkapitel

4. Optimal Placement of Ad Hoc Devices Under a VCG-Style Routing Protocol

verfasst von : Peter Widmayer, Luzi Anderegg, Stephan Eidenbenz, Leon Peeters

Erschienen in: Theoretical Aspects of Distributed Computing in Sensor Networks

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

Motivated by a routing protocol with VCG-style payments, we investigate the combinatorial problem of placing new devices in an ad hoc network such that the resulting shortest path transmission costs, defined as sums of squared Euclidean distances, are minimum. For the cases of only one new device and of one communication request with multiple devices with identical transmission ranges, we provide polynomial-time algorithms. On the negative side, we show that even for a single communication request, placing multiple new devices with different transmission ranges is NP-hard. For identical transmission ranges, the placement of multiple new devices is NP-hard under multiple communication requests.

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 Maintaining Connectivity in Sensor Networks Using Directional Antennae
Nächstes Kapitel Population Protocols and Related Models
Literatur
1.
P. Agarwal, O. Schwarzkopf, and M. Sharir. The overlay of lower envelopes and its applications. Discrete & Computational Geometry, 15(1):1–13, Springer, New York, NY, 1996.MATHCrossRefMathSciNet
2.
S. Albers, S. Eilts, E. Even-Dar, Y. Mansour, and L. Roditty. On Nash equilibria for a network creation game. In: Proceedings SODA 2006, pages 89–98, Miami, Florida, 2006.
3.
L. Anderegg and S. Eidenbenz. Ad hoc-VCG: a truthful and cost-efficient routing protocol for mobile ad hoc networks with selfish agents. In: Proceedings MOBICOM 2003, pages 245–259, San Diego, California, 2003.
4.
L. Anderegg, S. Eidenbenz, L. Peeters, and P. Widmayer. Optimal placement of ad-hoc devices under a vcg-style routing protocol. In M. Kutylowski, J. Cichon, and P. Kubiak, editors, ALGOSENSORS, vol. 4837 of Lecture Notes in Computer Science, pages 58–70. Springer, New York, NY, 2007.
5.
E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden. The price of stability for network design with fair cost allocation. In: Proceedings FOCS 2004, pages 295–304, Rome, Italy, 2004.
6.
E. Anshelevich, A. Dasgupta, E. Tardos, and T. Wexler. Near-optimal network design with selfish agents. In: Proceedings STOC 2003, pages 511–520, 2003.
7.
J. Corbo and D. Parkes. The price of selfish behavior in bilateral network formation. In: Proceedings PODC 2005, pages 99–107, Las Vegas, Nevada, 2005.
8.
M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer, New York, NY, 1997.MATH
9.
10.
S. Eidenbenz, G. Resta, and P. Santi. The commit protocol for truthful and cost-efficient routing in ad hoc networks with selfish nodes. IEEE Transactions on Mobile Computing, 7(1):19–33, 2008.CrossRef
11.
A. Fabrikant, A. Luthra, E. Maneva, C. Papadimitriou, and S. Shenker. On a network creation game. In: Proceedings PODC 2003, Boston, Massachusetts, 2003.
12.
M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, NY, 1979.MATH
13.
O. Goussevskaia, M. Halldórsson, R. Wattenhofer, and E. Welzl. Capacity of Arbitrary Wireless Networks. In: 28th Annual IEEE Conference on Computer Communications (INFOCOM), Rio de Janeiro, Brazil, April, 2009.
14.
O. Goussevskaia, Y. A. Oswald, and R. Wattenhofer. Complexity in Geometric SINR. In: ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), Montreal, Canada, September, 2007.
15.
A. Hayrapetyan, E. Tardos, and T. Wexler. A network pricing game for selfish traffic. In: Proceedings PODC 2005, pages 284–291, Las Vegas, Nevada, 2005.
16.
M. Hoefer and P. Krysta. Geometric Network Design with Selfish Agents. In: Proceedings of 11th Annual International Conference on Computing and Combinatorics (COCOON 2005), pages 167–178, Kunming, Yunnan, 2005.
17.
G. Kant. Drawing planar graphs using the lmc-ordering. In: Proceedings FOCS 1992, pages 101–110, Pittsburgh, Pennsylvania, 1992.
18.
S. Krumke. The Approximability of Location and Network Design Problems. PhD thesis, University of Wuerzburg, 1996.
19.
A. Mas-Colell, M. Whinston, and J. Green. Microeconomic Theory. Oxford University Press, 1995.
20.
C. Thielen and S. O. Krumke. Truthful mechanisms for selfish routing and two-parameter agents. In: SAGT, pages 36–47, Paphos, Cyprus, 2009.
Metadaten
Titel
Optimal Placement of Ad Hoc Devices Under a VCG-Style Routing Protocol
verfasst von
Peter Widmayer
Luzi Anderegg
Stephan Eidenbenz
Leon Peeters
Copyright-Jahr
2011
Verlag
Springer Berlin Heidelberg
Buch
Theoretical Aspects of Distributed Computing in Sensor Networks

Print ISBN: 978-3-642-14848-4

Electronic ISBN: 978-3-642-14849-1

Copyright-Jahr: 2011

DOI
https://doi.org/10.1007/978-3-642-14849-1_4