Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

07.12.2019 | Ausgabe 3/2020

Journal of Combinatorial Optimization 3/2020

The complexity of symmetric connectivity in directional wireless sensor networks

Zeitschrift:
Journal of Combinatorial Optimization > Ausgabe 3/2020
Autoren:
Tien Tran, Dung T. Huynh
Wichtige Hinweise
This paper is a revised and expanded version of a paper entitled “Symmetric Connectivity Algorithms in Multiple Directional Antennas Wireless Sensor Networks” presented at the IEEE International Conference on Computer Communications (INFOCOM 2018), 15–19 April 2018, Honolulu, HI, USA (Tran and Huynh 2018).

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Abstract

In this paper, we investigate the Antenna Orientation (AO) and Antenna Orientation and Power Assignment (AOPA) problems concerning symmetric connectivity in Directional Wireless Sensor Networks (DWSNs) where each sensor node is equipped with \( 2 \le k \le 5\) directional antennas having beam-width \(\theta \ge 0\). The AO problem for DWSNs is closely related with the well-known Euclidean Degree-Bounded Minimum Bottleneck Spanning Tree (EBMBST) problem where different cases for the degree bound have been studied. While current works on DWSNs focus on solving each case of k (\(=2,3,4\)) separately, we propose a uniform approach for the AO problem that yields constant-factor approximation algorithms for the AO as well as the EBMBST problem where the degree bound is between 2 and 4. Our method achieves the same constant factors. For the AOPA problem, to the best of our knowledge, our paper provides the first results concerning this problem. We show that the problem is NP-hard when \(2 \le k \le 4\). We also establish the first constant-factor approximation algorithms for the problem. Finally, we perform some simulations to understand the practical performance of our algorithms.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

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

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

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

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

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




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 3/2020

Journal of Combinatorial Optimization 3/2020 Zur Ausgabe

Premium Partner

    Bildnachweise