Reliable Route Selection for Wireless Sensor Networks with Connection Failure Uncertainties
For wireless sensor networks (WSN) with connection failure uncertainties, traditional minimum spanning trees are no longer a feasible option for selecting routes. Reliability should come first before cost since no one wants a network that cannot work most of the time. First, reliable route selection...
Main Authors: | , , , |
---|---|
Format: | Article |
Language: | English |
Published: |
MDPI AG
2021-10-01
|
Series: | Sensors |
Subjects: | |
Online Access: | https://www.mdpi.com/1424-8220/21/21/7254 |
_version_ | 1797511814691422208 |
---|---|
author | Jianhua Lyu Yiran Ren Zeeshan Abbas Baili Zhang |
author_facet | Jianhua Lyu Yiran Ren Zeeshan Abbas Baili Zhang |
author_sort | Jianhua Lyu |
collection | DOAJ |
description | For wireless sensor networks (WSN) with connection failure uncertainties, traditional minimum spanning trees are no longer a feasible option for selecting routes. Reliability should come first before cost since no one wants a network that cannot work most of the time. First, reliable route selection for WSNs with connection failure uncertainties is formulated by considering the top-k most reliable spanning trees (RST) from graphs with structural uncertainties. The reliable spanning trees are defined as a set of spanning trees with top reliabilities and limited tree weights based on the possible world model. Second, two tree-filtering algorithms are proposed: the k minimum spanning tree (KMST) based tree-filtering algorithm and the depth-first search (DFS) based tree-filtering algorithm. Tree-filtering strategy filters the candidate RSTs generated by tree enumeration with explicit weight thresholds and implicit reliability thresholds. Third, an innovative edge-filtering method is presented in which edge combinations that act as upper bounds for RST reliabilities are utilized to filter the RST candidates and to prune search spaces. Optimization strategies are also proposed for improving pruning capabilities further and for enhancing computations. Extensive experiments are conducted to show the effectiveness and efficiency of the proposed algorithms. |
first_indexed | 2024-03-10T05:52:23Z |
format | Article |
id | doaj.art-dc6327f5e466401bb05de7e835539c2a |
institution | Directory Open Access Journal |
issn | 1424-8220 |
language | English |
last_indexed | 2024-03-10T05:52:23Z |
publishDate | 2021-10-01 |
publisher | MDPI AG |
record_format | Article |
series | Sensors |
spelling | doaj.art-dc6327f5e466401bb05de7e835539c2a2023-11-22T21:38:53ZengMDPI AGSensors1424-82202021-10-012121725410.3390/s21217254Reliable Route Selection for Wireless Sensor Networks with Connection Failure UncertaintiesJianhua Lyu0Yiran Ren1Zeeshan Abbas2Baili Zhang3School of Computer Science and Engineering, Southeast University, Nanjing 210096, ChinaSchool of Computer Science and Engineering, Southeast University, Nanjing 210096, ChinaSchool of Computer Science and Engineering, Southeast University, Nanjing 210096, ChinaSchool of Computer Science and Engineering, Southeast University, Nanjing 210096, ChinaFor wireless sensor networks (WSN) with connection failure uncertainties, traditional minimum spanning trees are no longer a feasible option for selecting routes. Reliability should come first before cost since no one wants a network that cannot work most of the time. First, reliable route selection for WSNs with connection failure uncertainties is formulated by considering the top-k most reliable spanning trees (RST) from graphs with structural uncertainties. The reliable spanning trees are defined as a set of spanning trees with top reliabilities and limited tree weights based on the possible world model. Second, two tree-filtering algorithms are proposed: the k minimum spanning tree (KMST) based tree-filtering algorithm and the depth-first search (DFS) based tree-filtering algorithm. Tree-filtering strategy filters the candidate RSTs generated by tree enumeration with explicit weight thresholds and implicit reliability thresholds. Third, an innovative edge-filtering method is presented in which edge combinations that act as upper bounds for RST reliabilities are utilized to filter the RST candidates and to prune search spaces. Optimization strategies are also proposed for improving pruning capabilities further and for enhancing computations. Extensive experiments are conducted to show the effectiveness and efficiency of the proposed algorithms.https://www.mdpi.com/1424-8220/21/21/7254wireless sensor networksconnection failure uncertaintyroute selectionreliable spanning treefiltering |
spellingShingle | Jianhua Lyu Yiran Ren Zeeshan Abbas Baili Zhang Reliable Route Selection for Wireless Sensor Networks with Connection Failure Uncertainties Sensors wireless sensor networks connection failure uncertainty route selection reliable spanning tree filtering |
title | Reliable Route Selection for Wireless Sensor Networks with Connection Failure Uncertainties |
title_full | Reliable Route Selection for Wireless Sensor Networks with Connection Failure Uncertainties |
title_fullStr | Reliable Route Selection for Wireless Sensor Networks with Connection Failure Uncertainties |
title_full_unstemmed | Reliable Route Selection for Wireless Sensor Networks with Connection Failure Uncertainties |
title_short | Reliable Route Selection for Wireless Sensor Networks with Connection Failure Uncertainties |
title_sort | reliable route selection for wireless sensor networks with connection failure uncertainties |
topic | wireless sensor networks connection failure uncertainty route selection reliable spanning tree filtering |
url | https://www.mdpi.com/1424-8220/21/21/7254 |
work_keys_str_mv | AT jianhualyu reliablerouteselectionforwirelesssensornetworkswithconnectionfailureuncertainties AT yiranren reliablerouteselectionforwirelesssensornetworkswithconnectionfailureuncertainties AT zeeshanabbas reliablerouteselectionforwirelesssensornetworkswithconnectionfailureuncertainties AT bailizhang reliablerouteselectionforwirelesssensornetworkswithconnectionfailureuncertainties |