Connectivity-aware Relay Node Deployment in Grid-based Wireless Sensor Networks
Authors:
- 1 April 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-4
Abstract
Relay node placement can be an effective mean for boosting the performance of a Wireless Sensor Network (WSN) in terms of several metrics such as network connectivity, network lifetime and fault tolerance. In this paper, we consider the problem of deploying relay nodes (RNs) in a WSN to ensure network connectivity. We propose a novel heuristic to find a minimum number of RNs together with their locations needed in order to repair a disconnected network with a grid topology. We first determine the optimal solution for connecting a set of four disconnected nodes and then, by applying our heuristic, we ensure connectivity between these sets via steinerized edges. The runtime complexity of the proposed heuristic is quasilinear in the number of nodes, which is lower than competitive approaches. In addition to that, our heuristic can achieve network connectivity using 32% less of RNs. The performances of the proposed heuristic are validated through simulations.Keywords
This publication has 8 references indexed in Scilit:
- Novel relay node placement algorithms for establishing connected topologiesJournal of Network and Computer Applications, 2016
- Energy-efficient deployment strategies in structural health monitoring using wireless sensor networksStructural Control and Health Monitoring, 2012
- Relay sensor placement in wireless sensor networksWireless Networks, 2007
- An introduction to structural health monitoringPhilosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2006
- Wireless sensor networks: a surveyComputer Networks, 2002
- Approximations for Steiner Trees with Minimum Number of Steiner PointsJournal of Global Optimization, 2000
- Steiner tree problem with minimum number of Steiner points and bounded edge-lengthInformation Processing Letters, 1999
- Steiner Trees on a CheckerboardMathematics Magazine, 1989