Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

12-09-2016 | Issue 3/2017

Wireless Personal Communications 3/2017

PSH: A Pruning and Substitution Based Heuristic Algorithm for Relay Node Placement in Two-Tiered Wireless Sensor Networks

Journal:
Wireless Personal Communications > Issue 3/2017
Authors:
Chaofan Ma, Wei Liang, Meng Zheng

Abstract

Delay constrained relay node placement (DCRNP) problem minimizes the quantity of deployed relays that are employed to build at least one path between the sink and each sensor, while guaranteeing that the delay constraints for the built paths are fulfilled. Published literature only focus on the DCRNP problem in single-tiered wireless sensor networks (WSNs). Considering the benefits in terms of network scalability and energy consumption by the two-tiered network topology, this paper studies the DCRNP problem in two-tiered WSNs and proposes a pruning-and-substitution-based-heuristic (PSH) algorithm to solve the DCRNP problem. PSH consists of two phases, i.e., the covering phase and the connecting phase. In the covering phase, a shortest-path-based algorithm (SPA) is proposed to deploy relays at a subset of predetermined deployment locations such that each sensor is covered by at least one relay, meanwhile ensuring the obedience of delay constraints. Then, in the connecting phase, a tree-based connecting algorithm (TCA) is proposed to build the high-tier network connectivity. TCA first builds a shortest path tree to connect the relays deployed by SPA to the sink, and then, saves the deployed relays by gradually pruning or substituting them by the relays placed at the locations that several feasible paths pass through. The time complexity and the approximation ratio of this work are explicitly analyzed and extensive simulations are implemented to demonstrate its effectiveness.

Please log in to get access to this content

To get access to this content you need the following product:

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.

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.

Literature
About this article

Other articles of this Issue 3/2017

Wireless Personal Communications 3/2017 Go to the issue