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...
Autores principales: | , , , |
---|---|
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 |