Cargando…

Connectivity Restoration in Wireless Sensor Networks via Space Network Coding

The problem of finding the number and optimal positions of relay nodes for restoring the network connectivity in partitioned Wireless Sensor Networks (WSNs) is Non-deterministic Polynomial-time hard (NP-hard) and thus heuristic methods are preferred to solve it. This paper proposes a novel polynomia...

Descripción completa

Detalles Bibliográficos
Autores principales: Uwitonze, Alfred, Huang, Jiaqing, Ye, Yuanqing, Cheng, Wenqing
Formato: Online Artículo Texto
Lenguaje:English
Publicado: MDPI 2017
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5426826/
https://www.ncbi.nlm.nih.gov/pubmed/28425923
http://dx.doi.org/10.3390/s17040902
_version_ 1783235560052097024
author Uwitonze, Alfred
Huang, Jiaqing
Ye, Yuanqing
Cheng, Wenqing
author_facet Uwitonze, Alfred
Huang, Jiaqing
Ye, Yuanqing
Cheng, Wenqing
author_sort Uwitonze, Alfred
collection PubMed
description The problem of finding the number and optimal positions of relay nodes for restoring the network connectivity in partitioned Wireless Sensor Networks (WSNs) is Non-deterministic Polynomial-time hard (NP-hard) and thus heuristic methods are preferred to solve it. This paper proposes a novel polynomial time heuristic algorithm, namely, Relay Placement using Space Network Coding (RPSNC), to solve this problem, where Space Network Coding, also called Space Information Flow (SIF), is a new research paradigm that studies network coding in Euclidean space, in which extra relay nodes can be introduced to reduce the cost of communication. Unlike contemporary schemes that are often based on Minimum Spanning Tree (MST), Euclidean Steiner Minimal Tree (ESMT) or a combination of MST with ESMT, RPSNC is a new min-cost multicast space network coding approach that combines Delaunay triangulation and non-uniform partitioning techniques for generating a number of candidate relay nodes, and then linear programming is applied for choosing the optimal relay nodes and computing their connection links with terminals. Subsequently, an equilibrium method is used to refine the locations of the optimal relay nodes, by moving them to balanced positions. RPSNC can adapt to any density distribution of relay nodes and terminals, as well as any density distribution of terminals. The performance and complexity of RPSNC are analyzed and its performance is validated through simulation experiments.
format Online
Article
Text
id pubmed-5426826
institution National Center for Biotechnology Information
language English
publishDate 2017
publisher MDPI
record_format MEDLINE/PubMed
spelling pubmed-54268262017-05-12 Connectivity Restoration in Wireless Sensor Networks via Space Network Coding Uwitonze, Alfred Huang, Jiaqing Ye, Yuanqing Cheng, Wenqing Sensors (Basel) Article The problem of finding the number and optimal positions of relay nodes for restoring the network connectivity in partitioned Wireless Sensor Networks (WSNs) is Non-deterministic Polynomial-time hard (NP-hard) and thus heuristic methods are preferred to solve it. This paper proposes a novel polynomial time heuristic algorithm, namely, Relay Placement using Space Network Coding (RPSNC), to solve this problem, where Space Network Coding, also called Space Information Flow (SIF), is a new research paradigm that studies network coding in Euclidean space, in which extra relay nodes can be introduced to reduce the cost of communication. Unlike contemporary schemes that are often based on Minimum Spanning Tree (MST), Euclidean Steiner Minimal Tree (ESMT) or a combination of MST with ESMT, RPSNC is a new min-cost multicast space network coding approach that combines Delaunay triangulation and non-uniform partitioning techniques for generating a number of candidate relay nodes, and then linear programming is applied for choosing the optimal relay nodes and computing their connection links with terminals. Subsequently, an equilibrium method is used to refine the locations of the optimal relay nodes, by moving them to balanced positions. RPSNC can adapt to any density distribution of relay nodes and terminals, as well as any density distribution of terminals. The performance and complexity of RPSNC are analyzed and its performance is validated through simulation experiments. MDPI 2017-04-20 /pmc/articles/PMC5426826/ /pubmed/28425923 http://dx.doi.org/10.3390/s17040902 Text en © 2017 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/).
spellingShingle Article
Uwitonze, Alfred
Huang, Jiaqing
Ye, Yuanqing
Cheng, Wenqing
Connectivity Restoration in Wireless Sensor Networks via Space Network Coding
title Connectivity Restoration in Wireless Sensor Networks via Space Network Coding
title_full Connectivity Restoration in Wireless Sensor Networks via Space Network Coding
title_fullStr Connectivity Restoration in Wireless Sensor Networks via Space Network Coding
title_full_unstemmed Connectivity Restoration in Wireless Sensor Networks via Space Network Coding
title_short Connectivity Restoration in Wireless Sensor Networks via Space Network Coding
title_sort connectivity restoration in wireless sensor networks via space network coding
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5426826/
https://www.ncbi.nlm.nih.gov/pubmed/28425923
http://dx.doi.org/10.3390/s17040902
work_keys_str_mv AT uwitonzealfred connectivityrestorationinwirelesssensornetworksviaspacenetworkcoding
AT huangjiaqing connectivityrestorationinwirelesssensornetworksviaspacenetworkcoding
AT yeyuanqing connectivityrestorationinwirelesssensornetworksviaspacenetworkcoding
AT chengwenqing connectivityrestorationinwirelesssensornetworksviaspacenetworkcoding