Article
Reliable Route Selection for Wireless Sensor Networks with
Connection Failure Uncertainties.
Jianhua Lyu
1,2,
*, Yiran Ren
1
, Zeeshan Abbas
1
and Baili Zhang
1,2
Citation: Lyu, J.; Ren, Y.; Abbas, Z.;
Zhang, B. Reliable Route Selection for
Wireless Sensor Networks with
Connection Failure Uncertainties.
Sensors 2021, 21, 7254. https://
doi.org/10.3390/s21217254
Academic Editors: Hamed Badihi,
Tao Chen and Ningyun Lu
Received: 3 October 2021
Accepted: 29 October 2021
Published: 31 October 2021
Publisher’s Note: MDPI stays neutral
with regard to jurisdictional claims in
published maps and institutional affil-
iations.
Copyright: © 2021 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 (https://
creativecommons.org/licenses/by/
4.0/).
1
School of Computer Science and Engineering, Southeast University, Nanjing 210096, China;
220201951@seu.edu.cn (Y.R.); ZeeshanAbbas5@hotmail.com (Z.A.); zhangbl@seu.edu.cn (B.Z.)
2
Key Laboratory of Computer Network and Information Integration (Southeast University),
Ministry of Education, Nanjing 210096, China
* Correspondence: lujianhua@seu.edu.cn
Abstract:
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.
Keywords:
wireless sensor networks; connection failure uncertainty; route selection; reliable span-
ning tree; filtering
1. Introduction
Wireless sensor networks (WSN) are widely used in various applications, such as
military battlefield monitoring, traffic surveillance, environmental monitoring, intelligent
agriculture, industrial system health management and transportation [
1
–
4
]. They are often
deployed in cites that are not friendly to both human and chips. Moreover, the sensor nodes
have limited resources on power, communication, computation and storage. Therefore,
the communication channel between sensor nodes is susceptible to environmental events
and node failures due to weather conditions, atmospheric qualities, moving obstacles
and fabrication problems. Such connection failure obtains automatic recovery for the
time being while the environment becomes normal. We regard them as
Wireless Sensor
Networks with Connection Failure Uncertainties
. It is of great significance to develop
route selection strategies for such WSNs in order to obtain all sensors connected with low
cost and high reliability. We anticipate that a network with the highest reliability can serve
for a longer period of time than the others possibly can.
Route selection for wired communication networks have been studied for decades
and has become mature [
5
]. Connectivity and cost are two common objectives. Minimal
spanning trees (MST) has been widely used to achieve minimal communication cost when
all nodes are connected. However, cost is no longer the first consideration in addition to
connectivity for WSNs with connection failure uncertainties. The route with minimal cost
may serve only for a very short period of time since the connection edges it involves have
Sensors 2021, 21, 7254. https://doi.org/10.3390/s21217254 https://www.mdpi.com/journal/sensors
