Sage Journals: Discover world-class research

Abstract

When nodes and/or links are down in a network, the network may not function normally. Most of the existing work focuses on the reachability between two nodes along a path, that is, path reliability, and that through arbitrary paths, that is, network reliability. However, in case of wireless multi-hop networks and road networks, it may be inefficient or difficult to recalculate a path from the source to the destination when a failure occurs at an intermediate link in the path. In such cases, we can expect that the reachability between two nodes will improve by taking a detour from the entry of the failure link (i.e. failure point) to the destination without traversing the failure link. Since the detour may also increase the communication/travel delay, in this paper, we propose a new path metric (i.e. path reachability including distance-constrained detours), which consists of the conventional path reachability and the reachability along distance-constrained detours under arbitrary link failures in the original path. We first prove the two important characteristics: (1) the proposed metric is exactly the same as the network reliability in case of no distance constraint and (2) it is upper bounded by the diameter constrained network reliability. Through numerical results using a grid network and more realistic networks (i.e. wireless networks and a road network), we show the fundamental characteristics of the proposed metric and analyze the goodness of several representative paths in terms of the proposed metric as well as the conventional metrics (i.e. path length and path reachability).

Keywords

Path reachability detour distance constraint network reliability diameter constrained network reliability wireless network road network

Introduction

Nowadays, our human society relies on various types of networks such as communication networks and road networks. When some of nodes (e.g. network devices and intersections) and/or links (e.g. communication links and road segments) are down, due to failures, natural disasters, or malicious attacks, the network may not be able to work normally. There are many studies on quantitatively evaluating the reliability of the network when the failure probability (or availability) of each node/link is given.^1–4 In this paper, we mainly focus on the link failure.

One possible path reliability metric is the path reliability (reachability), which is defined as the probability that a path $r_{s, t}$ from the source $s$ to the destination $t$ is available (reachable). If the link availability $p_{e} (0 \leq p_{e} \leq 1)$ of each link $e$ in $r_{s, t}$ is independent, the path reliability is given by the product of link availability of all links in $r_{s, t}$ , that is, $\underset{e \in r_{s, t}}{Π} p_{e}$ .⁵ The $s$ – $t$ network reliability is also a well-known network reliability metric, which is the probability that at least one available path exists from the source $s$ to the destination $t$ ^1,2 In what follows, the $s$ – $t$ network reliability is simply called the network reliability⁶ if there is no confusion. The extension of the network reliability with distance (diameter) constraint is called diameter constrained network reliability.⁶ The path reliability considers the reachability from $s$ to $t$ under a certain $s$ – $t$ path while the network reliability considers the reachability from $s$ to $t$ under all possible $s$ – $t$ paths.

In case of several situations, for example, multi-hop communications in wireless networks and evacuation over road networks,^5,7,8 when a failure occurs at an intermediate link in the $s$ – $t$ path, taking a detour from the entry of the failure link (i.e. failure point) to the destination $t$ without traversing the failure link will be important/essential to improve the reachability between $s$ and $t$ . Note that taking the detour may increase the total path length, which results in increase of communication delay and travel time, and thus we should consider detour possibility under a certain distance constraint.

In this paper, we introduce a new concept of distance-constrained detour possibility, which is the probability that the source $s$ is reachable to the destination $t$ using detours from arbitrary failure points along the given $s$ – $t$ path such that the total path length is equal to or less than a certain threshold. We further formulate a new path metric of path reachability including distance-constrained detours as the sum of the conventional path reliability and the distance-constrained detour possibility. The proposed metric plays a role in bridging the above-mentioned two metrics, that is, path reliability and network reliability. Actually, we will prove the two important characteristics: (1) the proposed metric is exactly the same as the network reliability in case of no distance constraint and (2) it is upper bounded by the diameter constrained network reliability.

The main purposes of the manuscript are following: (1) proposing the new metric (i.e. path reachability including distance-constrained detours) and (2) revealing the potential of the proposed metric in terms of path selection through several numerical experiments. In this context, we mainly focus on the application of the proposed metric in a proactive approach. More specifically, given a certain $s$ – $t$ path and the parameters (i.e. length $d_{e}$ and availability $p_{e}$ ) of each link $e$ in the network, we can assess the goodness of the path in terms of the proposed metric as well as the conventional metrics (i.e. path length and path reliability). Simply speaking, if there are multiple path candidates achieving similar performance in terms of the conventional metrics, it is desirable to select a path with the largest value of the proposed metric among them. In other words, the proposed metric compensates for the existing metrics.

Through numerical experiments using a grid network, we show the fundamental characteristics of the proposed metric and the relation with the existing metrics, that is, path length, path reliability, and network reliability. We further evaluate the goodness of some representative paths in terms of the proposed metric and existing ones through numerical experiments using realistic networks, that is, wireless networks and a road network.

The rest of the paper is organized as follows. The following section gives related work, and the subsequent section gives the proposed path metric of the path reachability including distance-constrained detours. A further section demonstrates numerical results using three kinds of networks. The final section provides conclusions and future work.

Related work

Network reliability metrics

The $s$ – $t$ network reliability is a representative network reliability metric, which is the probability that at least one available path exists from the source $s$ to the destination $t$ under the assumption where each link in the network independently becomes unavailable at a certain probability.^1,2 The $s$ – $t$ network reliability is also called the two-terminal network reliability and can be generalized as the $k$ -terminal network reliability, which is the probability that terminals (nodes) in any subset $K$ of the whole nodes $V$ in the network ( $K \subseteq V, k = | K |$ ) are reachable with each other.⁹ Xiang and Yang¹⁰ proposed the generalized $k$ -terminal network reliability, which is the probability that at least $k$ arbitrary nodes in the network are available and form a connected graph. Petingi and Rodriguez further extended the $k$ -terminal network reliability with the diameter constraint, called the diameter constrained network reliability, which is the probability that the set $K$ of the whole nodes in the network are reachable through paths of length equal to or less than a certain threshold.⁶

Since the computational complexity of the network reliability and its variants are NP-hard,^11–13 many researchers have studied on efficient algorithms for exact solutions (e.g. sum of disjoint products,¹⁴ state enumeration,¹⁵ direct decomposition,¹⁶ factoring,¹⁷ and binary decision diagram (BDD) based approaches^9,18) or those for approximate solutions (e.g. Monte Carlo simulation method,¹⁹ its extension with binary-addition-tree algorithm,²⁰ approximate zero-variance importance sampling,²¹ counting based method,²² convolutional neural network based method,²³ and graph neural network based method²⁴). As we will see in “Proposed metric” section, the proposed metric (i.e. path reachability including distance-constrained detours) requires the calculation of the diameter constrained network reliability. Since our main focus is revealing the potential of the proposed metric as mentioned in “Introduction” section, we adopt one of the efficient algorithms for exact solutions. (The details will be given in “Numerical experiments” section.) As for other network reliability metrics, several studies focused on the fraction of important nodes to maintain the network connectivity. Li et al.²⁵ proposed a new network reliability metric using percolation theory.^26,27 Percolation theory focuses on the network connectivity when part of the nodes and/or links are removed from a network. If a link has capacity (e.g. radio frequency of a wireless link and road width), the link availability depends not only on the failures but also on the capacity. Inoue³ evaluated the network reliability when using two disjoint $s$ – $t$ paths and proposed a method to detect critical links,²⁸ which have a great impact on the reliability. Detecting critical links will help to analyze how much the network connectivity can be maintained against node/link failures.²⁹

In this paper, we focus on the path reachability including distance constrained detours, which is the reachability of the $s$ – $t$ path including distance-constrained detours when a link failure occurs at an intermediate link in the $s$ – $t$ path. The concept of the path reachability including distance constrained detours is somewhat similar to that of the diameter constrained network reliability with $k = 2$ . The biggest difference is that the former focuses on a certain $s$ – $t$ path and its derived detours while the latter focuses on all the possible paths from $s$ to $t$ . In other words, the diameter constrained network reliability with $k = 2$ will give the upper bound of the path reachability including distance constrained detours. We will also show that the proposed metric without the distance constraint is equivalent to the $s$ – $t$ network reliability. (See details in “Proposed metric” section.)

Path reliability metrics

One possible path reliability metric is the path reliability, which is reachability of an $s$ – $t$ path $r_{s, t}$ .^5,30 In wireless sensor networks, communication failures may occur due to environmental noise and/or battery life of sensor nodes.³¹ Zonouz et al. proposed the reliability model for each of two types of sensor nodes, that is, energy-harvesting sensor nodes and battery-powered sensor nodes.³² They also proposed a link reliability model of the two types of the sensor nodes by considering battery life, shadowing, noise, and positioning errors of global positioning system (GPS). In addition, they analyzed the performance of the shortest distance path, the smallest hop path, and the highest reliable path based on the proposed reliability model, in terms of the number of hops of the path and load balancing. Nowsheen et al.³³ proposed a routing scheme for underwater sensor networks, which considers the number of successfully transmitted packets between sensor nodes, the reachability to a gateway node, and the probability that neighboring sensor nodes exist within the transmission range.

In mobile ad-hoc networks (MANETs), dynamic change of link reliability between nodes due to the node mobility may fail in guaranteeing the quality of service (QoS) of the routing. Chatterjee and Das and Das³⁴ proposed a dynamic source routing scheme based on the number of hops, congestion degree of a path, and the received signal strength (RSS) of nodes. Kumar and Padmavathy³⁵ proposed a link reliability model that determines whether a link between two nodes is connected or not based on the Euclidean distance, transmission distance, and the radio propagation characteristics between them. Thanks to this reliability model, they further evaluated the reliability of the shortest path between two nodes.

These existing schemes focus on the reliability of a certain path between two arbitrary nodes but it may be inefficient and/or difficult to reconstruct an alternative $s$ – $t$ path under the occurrence of link failures. In such cases, detours from the failure point to the destination $t$ may improve the $s$ – $t$ reachability. In this paper, we consider the path reachability including distance-constrained detours.

Routing with detours

In wireless sensor networks, each sensor node may not be able to accurately grasp its own location as well as other nodes’ locations, which will make data packets encounter a routing hole where there is no node closer to the destination.³⁶ To address this problem, several studies proposed geographical routing algorithms to transfer data to the destination node by bypassing routing holes.^37,38 Lima et al.³⁸ proposed a geographic routing algorithm for transferring data to the destination node by bypassing routing holes under the assumption that RSS from the sink node has a positive correlation with the distance to the sink node. Huang et al.³⁷ proposed an energy-aware geographic routing protocol with bypasses of routing holes for wireless sensor networks with resource constraints.

These schemes can be regarded as reactive ones because they determine a detour after a link failure occurs in the $s$ – $t$ path. On the contrary, in this paper, we focus on a proactive approach, which can evaluate the reachability along the $s$ – $t$ path and its yielding distance-constrained detours in advance.

Proposed metric

In this section, we will define the proposed metric, that is, path reachability including distance-constrained detours. Table 1 summarizes the notations used in this paper. Figure 1 illustrates the flow to derive the proposed metric, where the left side gives the steps in general cases and the right side gives an illustrative example using a $3 \times 3$ grid network.

Table 1.

Notations.

Notation	Definition
$G$	Network $G = (V, E)$
$V$	Set of vertices $(V = \| V \|)$
$E$	Set of links $(E = \| E \|)$
$d_{e}$	Length of link $e$
$d$	Vector of link length, $d = (d_{1}, \dotsg, d_{E})$
$p_{e}$	Availability of link $e$
$p$	Vector of link availability, $p = (p_{1}, \dots, p_{E})$
$r_{s, t}$	$s$ – $t$ base path, $r_{s, t} = (e_{1}, \dots, e_{\| r_{s, t} \|})$
$R_{s, t}$	Set of paths from $s \in V$ to $t \in V \ {s}$
$f_{d} (r_{s, t})$	Length of path $r_{s, t}$
$f_{p} (r_{s, t})$	Path reliability of $r_{s, t}$
$d_{s, t}^{min}$	Shortest path length from $s \in V$ to $t \in V \ {s}$
$x_{e}$	State of link $e$ : If $e$ is available, $x_{e} = 1$ ; otherwise, $x_{e} = 0$
$x$	Vector of link state, $x = (x_{1}, \dots, x_{E})$
$G_{s, t, G}$	Set of events such that $s \in V$ and $t \in V \ {s}$ are connected
$G_{s, t, G} (D)$	Set of events such that $s \in V$ and $t \in V \ {s}$ are connected under diameter constraint $D$
$η$	Allowable distance increase from the shortest path distance $d_{s, t}^{min}$
$r_{s, u_{l}}^{s, t}$	Partial path of $r_{s, t}$ from $s \in V$ to failure point $u_{l} \in V$
$R_{u_{l}, t} (d_{s, t}^{min} + η - f_{d} (r_{s, u_{l}}^{s, t}))$	Set of distance-constrained detours deriving from failure point $u_{l} \in V$
$f_{D} (r_{s, t})$	Detour possibility of $r_{s, t}$
$f_{D} (r_{s, t}, η)$	Detour possibility of $r_{s, t}$ under distance constraint $η$
$f_{R} (r_{s, t}, η)$	Path reachability including distance-constrained detours
$f_{N} (G_{s, t, G}, p)$	$s$ – $t$ network reliability under the set $p$ of link availability
$f_{N} (G_{s, t, G} (D), p)$	$s$ – $t$ network reliability under the set $p$ of link availability and diameter constraint $D$

Figure 1.

Flow to derive proposed metric.

Preliminaries

For simplicity of explanation, in what follows, we assume communication networks. $G = (V, E)$ denotes a directed graph representing the internal structure of a target network, where $V$ denotes a set of $V$ vertices and $E$ denotes a set of $E$ directed links. Each link $e \in E$ has the length $d_{e} > 0$ and the availability $p_{e} (0 \leq p_{e} \leq 1)$ . In the right side of Figure 1, we assume that $d_{e} = 1$ and $p_{e} = 0.99$ ( $e \in E$ ). In what follows, we focus on a certain $s$ – $t$ path $r_{s, t}$ (i.e. base path) in the set $R_{s, t}$ of all possible $s$ – $t$ paths (Step 1 in Figure 1). Note that how to select the base path will be discussed in “Base path selection strategy” section. In the right side of Figure 1, we focus on $r_{s, t} = (e_{1}, e_{2}, e_{3}, e_{4})$ .

The length $f_{d} (r_{s, t})$ of the path $r_{s, t}$ is given by the sum of the length of all links in the path $r_{s, t}$ (Step 2 in Figure 1):

f_{d} (r_{s, t}) = \sum_{e \in r_{s, t}} d_{e},

where the path $r_{s, t}$ is given by a vector of links in the path, $(e_{1}, \dots, e_{| r_{s, t} |})$ and $| r_{s, t} |$ denotes the total number of links in the path $r_{s, t}$ . Hereinafter, the terms length and distance will be used interchangeably. In case of the communication network, $d_{e}$ can also be regarded as the propagation delay of the link $e$ . Let $d = (d_{1}, \dots, d_{E})$ denote a vector of link length. In the right side of Figure 1, $f_{d} (r_{s, t}) = 4$ .

If the link availability $p_{e} (0 \leq p_{e} \leq 1)$ of each link $e$ in an $s$ – $t$ path $r_{s, t}$ is independent, the path reliability (reachability) is defined as follows (Step 2 in Figure 1):

f_{p} (r_{s, t}) = \underset{e \in r_{s, t}}{Π} p_{e} .

(1)

Let $p = (p_{1}, \dots, p_{E})$ denote a vector of link availability. In the right side of Figure 1, $f_{p} (r_{s, t}) = 0 . 99^{4} \approx 0.96$ .

The $s$ – $t$ network reliability is the probability that at least one available reachable path between $s$ and $t$ exists under the assumption that the link availability of each link $e \in E$ in the network is independent. The state of the network can be expressed by $x = (x_{1}, \dots, x_{E}) \in {0, 1}^{E}$ where $x_{e} \in {0, 1}$ represents the state of link $e$ . Each link $e \in E$ will be available (resp. unavailable), that is, $x_{e} = 1$ (resp. $x_{e} = 0$ ), with the probability $p_{e}$ (resp. $(1 - p_{e})$ ). The $s$ – $t$ network reliability $f_{N} (G_{s, t, G}, p)$ can be expressed by the sum of the occurrence probabilities of all events $G_{s, t, G}$ , each of which corresponds to a distinct set of available links such that $s$ is reachable to $t$ . Here, $G_{s, t, G}$ and the occurrence probability $P (x)$ are given as follows:

G_{s, t, G} = {x \in {0, 1}^{E} | \exists r_{s, t} \in R_{s, t}, \underset{e \in r_{s, t}}{Π} x_{e} = 1},

P (x) = \underset{e \in E}{Π} (p_{e} x_{e} + (1 - p_{e}) (1 - x_{e})) .

As a result, $f_{N} (G_{s, t, G}, p)$ is given by

f_{N} (G_{s, t, G}, p) = \sum_{x \in G_{s, t, G}} P (x) .

Similarly, the diameter constrained network reliability for an $s$ – $t$ pair, $f_{N} (G_{s, t, G} (D), p)$ , can be defined as the sum of the occurrence probabilities of all events $G_{s, t, G} (D)$ where $s$ is reachable to $t$ along with paths of length equal to or less than a threshold $D \geq 0$ . Here, $G_{s, t, G} (D)$ and $f_{N} (G_{s, t, G} (D), p)$ are given by

\begin{matrix} G_{s, t, G} (D) = \\ {x \in {0, 1}^{E} | \exists r_{s, t} \in R_{s, t}, \underset{e \in r_{s, t}}{Π} x_{e} = 1, f_{d} (r_{s, t}) \leq D}, \end{matrix}

f_{N} (G_{s, t, G} (D), p) = \sum_{x \in G_{s, t, G} (D)} P (x),

(2)

respectively. Therefore, $f_{N} (G_{s, t, G} (\infty), p) = f_{N} (G_{s, t, G}, p)$ .

In what follows, we will see the calculation of the diameter constrained network reliability is required to derive the proposed metric (i.e. path reachability including distance-constrained detours) in equation (8). Note that the computational complexity of the network reliability and its variants are NP-hard as mentioned in “Network reliability metrics” section. In this paper, to reveal the potential of the proposed metric itself, we will strictly calculate the (diameter constrained) network reliability. (The details will be explained in “Evaluation model” section.) As for a more lightweight algorithm for the calculation, which will be more important in reactive approaches, we plan to develop it with the help of existing studies given in “Network reliability metrics” section.

Detour possibility

Suppose that the $l$ th ( $l = 1, \dots, | r_{s, t} |$ ) link $e_{l} = (u_{l}, v_{l})$ ( $u_{l}, v_{l} \in V, u_{l} \neq v_{l}$ ) in the $s$ – $t$ path $r_{s, t}$ is unavailable (Step 3 in Figure 1). In the right side of Figure 1, we focus on the failure of link $e_{2}$ out of all the four possibilities of link failures in $r_{s, t}$ , that is, $e_{1}, \dots, e_{4}$ . We consider the detour possibility from the node $u_{l}$ to the destination $t$ along detours that derive from the $s$ – $t$ path $r_{s, t}$ without using the failure link $e_{l}$ . At first, from equation (1), we obtain the path reliability of $r_{s, u_{l}}^{s, t} \subseteq r_{s, t}$ as follows (Step 4 in Figure 1):

f_{p} (r_{s, u_{l}}^{s, t}) = Π_{j = 1}^{| r_{s, u_{l}}^{s, t} |} p_{e_{j}},

(3)

where $r_{s, u_{l}}^{s, t}$ denotes the partial path of $r_{s, t}$ from $s$ to the failure point $u_{l}$ and we define $Π_{j = 1}^{0} p_{e_{j}} = 1$ . Note that $| r_{s, u_{l}}^{s, t} | = l - 1$ . In the right side of Figure 1, $f_{p} (r_{s, u_{2}}^{s, t}) = p_{e_{1}} = 0.99$ .

Under the events where the partial path $r_{s, u_{l}}^{s, t}$ is available and the link $e_{l}$ is unavailable, denoted by $G_{u_{l}, t, G}^{r_{s, u_{l}}^{s, t}, e_{l}^{0}}$ , the probability that $u_{l}$ is reachable to $t$ is given by the conditional network reliability $f_{N} (G_{u_{l}, t, G}^{r_{s, u_{l}}^{s, t}, e_{l}^{0}}, p)$ under the events $G_{u_{l}, t, G}^{r_{s, u_{l}}^{s, t}, e_{l}^{0}}$ (Step 5 in Figure 1):

\begin{matrix} G_{u_{l}, t, G}^{r_{s, u_{l}}^{s, t}, e_{l}^{0}} = {x \in {0, 1}^{E} | r_{s, u_{l}}^{s, t} \in r_{s, t} \\ Π_{j = 1}^{| r_{s, u_{l}}^{s, t} |} x_{e_{j}} = 1, {x_{l}}_{e_{l}} = 0, \exists r_{u_{l}, t} \in R_{u_{l}, t}, \\ \underset{e \in r_{u_{l}, t}}{Π} x_{e} = 1} \end{matrix}

(4)

f_{N} (G_{u_{l}, t, G}^{r_{s, u_{l}}^{s, t}, e_{l}^{0}}, p) = \sum_{x \in G_{s, t, G}^{r_{s, u_{l}}^{u_{l}, t}, e_{l}^{0}}} P (x) .

(5)

This event occurs with the probability, which is the product of the path reliability of $r_{s, u_{l}}^{s, t}$ , that is, equation (3), and the probability $1 - p_{e_{l}}$ that link $e_{l}$ is unavailable. Considering all the possible events where one of the links, that is, $e_{l}$ $(l = 1, \dots, | r_{s, t} |)$ , in the path $r_{s, t}$ becomes unavailable, we can define the detour possibility $f_{D} (r_{s, t}, p)$ of the path $r_{s, t}$ using equations (3) and (5):

f_{D} (r_{s, t}, p) = \sum_{l = 1}^{| r_{s, t} |} f_{p} (r_{s, u_{l}}^{s, t}) \cdot (1 - p_{e_{l}}) \cdot f_{N} (G_{u_{l}, t, G}^{r_{s, u_{l}}^{s, t}, e_{l}^{0}}, p) .

(6)

In the right side of Figure 1, part of $G_{u_{2}, t, G}^{r_{s, u_{2}}^{s, t}, e_{2}^{0}}$ is shown at the right part of Step 5.

Path reachability including distance-constrained detours

As for the detour possibility, taking a detour may increase the total length of the $s$ – $t$ path including the detour, which will also increase the communication delay in communication networks (resp. travel time in road networks). In this section, we focus on the distance constrained detour from a failure point to the destination excluding the corresponding failure link.

Suppose that the $l$ th ( $l = 1, \dots, | r_{s, t} |$ ) link $e_{l} = (u_{l}, v_{l})$ ( $u_{l}, v_{l} \in V, u_{l} \neq v_{l}$ ) in the path $r_{s, t}$ is unavailable. In case of the detour possibility without the distance constraint, we consider all detour candidates $R_{u_{l}, t}$ from the failure point $u_{l}$ to the destination $t$ excluding $e_{l}$ . On the other hand, in case of the distance-constrained detour possibility, we need to consider the distance-constrained detour candidates $R_{u_{l}, t} (d_{s, t}^{min} + η - f_{d} (r_{s, u_{l}}^{s, t}))$ from the failure point $u_{l}$ to the destination $t$ , which exclude $e_{l}$ and allow certain distance increase $η$ of the total path length from the shortest path distance $d_{s, t}^{min}$ between $s$ and $t$ :

\begin{matrix} R_{u_{l}, t} (d_{s, t}^{min} + η - f_{d} (r_{s, u_{l}}^{s, t})) = \\ {r_{u_{l}, t} | f_{d} (r_{s, u_{l}}^{s, t}) + f_{d} (r_{u_{l}, t}) \leq d_{s, t}^{min} + η, r_{u_{l}, t} \in R_{u_{l}, t}}, \end{matrix}

where $d_{s, t}^{min} = min_{r'_{s, t} \in R_{s, t}} f_{d} (r'_{s, t})$ denotes the shortest path distance between $s$ and $t$ and the parameter $η$ denotes the allowable distance increase of the total path from $d_{s, t}^{min}$ . The upper (resp. lower) bound of $η$ is given by $max_{r'_{s, t} \in R_{s, t}} f_{d} (r'_{s, t}) - f_{d} (r_{s, t})$ (resp. $f_{d} (r_{s, t}) - d_{s, t}^{min}$ ). The parameter $η$ can control the tradeoff between the total path length and the detour possibility.

In the right side of Figure 1, $R_{u_{2}, t}$ and $R_{u_{2}, t} (d_{s, t}^{min} + η - f_{d} (r_{s, u_{2}}^{s, t}))$ are illustrated in the right part of Step 6. By comparing them, we observe some important characteristics of detours. (1) There are many detour candidates where only part of them have the good properties in terms of the path length. (2) These two sets will change depending not only on the failure point in the base path but also on the base path itself.

Under the event where the path $r_{s, u_{l}}^{s, t}$ is reachable and the link $e_{l}$ is unavailable, the probability that $u_{l}$ is reachable to $t$ under the distance constraint $η$ can be expressed by the conditional network reliability under the events $G_{u_{l}, t, G}^{r_{s, u_{l}}^{s, t}, e_{l}^{0}} (d_{s, t}^{min} + η - f_{d} (r_{s, u_{l}}^{s, t}))$ where $\exists r_{u_{l}, t} \in R_{u_{l}, t} (d_{s, t}^{min} + η - f_{d} (r_{s, u_{l}}^{s, t}))$ is connected. Here, $G_{u_{l}, t, G}^{r_{s, u_{l}}^{s, t}, e_{l}^{0}} (d_{s, t}^{min} + η - f_{d} (r_{s, u_{l}}^{s, t}))$ and $f_{N} (G_{u_{l}, t, G}^{r_{s, u_{l}}^{s, t}, e_{l}^{0}} (d_{s, t}^{\min} + η - f_{d} (r_{s, u_{l}}^{s, t})), p)$ are given as follows (Step 6 in Figure 1):

\begin{array}{l} G_{u_{l}, t, G}^{r_{s, u_{l}}^{s, t}, e_{l}^{0}} (d_{s, t}^{\min} + η - f_{d} (r_{s, u_{l}}^{s, t})) = \\ {x \in {0, 1}^{E} | r_{s, u_{l}}^{s, t} \in r_{s, t}, \\ \prod_{j = 1}^{| r_{s, u_{l}}^{s, t} |} x_{e_{j}} = 1, x_{e_{l}} = 0, \exists r_{u_{l}, t} \in ℛ_{u_{l}, t}, \\ \prod_{e \in r_{u_{l}, t}} x_{e} = 1, f_{d} (r_{s, u_{l}}^{s, t}) + f_{d} (r_{u_{l}, t}) \leq d_{s, t}^{\min} + η} \end{array}

\begin{matrix} f_{N} (G_{u_{l}, t, G}^{r_{s, u_{l}}^{s, t}, e_{l}^{0}} (d_{s, t}^{min} + η - f_{d} (r_{s, u_{l}}^{s, t})), p) = \\ \sum_{x \in G_{u_{l}, t, G}^{r_{s, u_{l}}^{s, t}, e_{l}^{0}} (d_{s, t}^{min} + η - f_{d} (r_{s, u_{l}}^{s, t}))} P (x) . \end{matrix}

(7)

In the right side of Figure 1, part of $G_{u_{2}, t, G}^{r_{s, u_{2}}^{s, t}, e_{2}^{0}} (d_{s, t}^{min} + η - f_{d} (r_{s, u_{2}}^{s, t}))$ is shown at the right part of Step 8.

From equations (3) and (7), we can define the detour possibility under the distance constraint $η$ as follows (Step 7 in Figure 1):

\begin{matrix} f_{D} (r_{s, t}, p, d_{s, t}^{min} + η) = \sum_{l = 1}^{| r_{s, t} |} f_{p} (r_{s, u_{l}}^{s, t}) \cdot (1 - p_{e_{l}}) \cdot \\ f_{N} (G_{u_{l}, t, G}^{r_{s, u_{l}}^{s, t}, e_{l}^{0}} (d_{s, t}^{min} + η - f_{d} (r_{s, u_{l}}^{s, t})), p) . \end{matrix}

(8)

The path reachability including the distance-constrained detours of $r_{s, t}$ , $f_{R} (r_{s, t}, p, η)$ , can be expressed by the sum of equations (1) and (8) (Step 8 in Figure 1):

f_{R} (r_{s, t}, p, d_{s, t}^{min} + η) = f_{p} (r_{s, t}) + f_{D} (r_{s, t}, p, d_{s, t}^{min} + η) .

(9)

Here, we provide the following important theorems related to the path reachability including the distance-unconstrained detours.

Theorem 1. Given a certain path $r_{s, t}$ , the path reachability including the distance-unconstrained detours of $r_{s, t}$ , $f_{R} (r_{s, t}, p, \infty)$ , is exactly same as the $s$ – $t$ network reliability $f_{N} (G_{s, t, G}, p)$ :

f_{R} (r_{s, t}, p, \infty) = f_{N} (G_{s, t, G}, p) .

The proof will be given in “Proof to Theorem 1” section.

Theorem 2. Given a certain path $r_{s, t}$ and $η \geq η_{0}$ such that $f_{d} (r_{s, t}) = d_{s, t}^{min} + η_{0}$ , the $s$ – $t$ diameter constrained network reliability $f_{N} (G_{s, t, G} (d_{s, t}^{min} + η), p)$ gives the upper bound of the path reachability including the distance-constrained detours of $r_{s, t}, f_{R} (r_{s, t}, p, d_{s, t}^{min} + η)$ ,:

f_{R} (r_{s, t}, p, d_{s, t}^{min} + η) \leq f_{N} (G_{s, t, G} (d_{s, t}^{min} + η), p) .

The proof will be given in “Proof to Theorem 2” section.

Base path selection strategy

As mentioned above, given a base path, the proposed metric can be calculated. At the last of this section, we briefly explain how to select the base path. It is difficult to evaluate the distance-constrained detour possibility of all possible $s$ – $t$ paths due to the computational complexity. In addition, taking detours will be required only when some failure occurs on the original path. In other words, the original path should have good properties in terms of the existing path metrics, that is, path length and path reliability.

Considering these points, in this paper, we will focus on the following five representative paths, that is, the shortest path $r_{s, t}^{d_{min}}$ , the path with the highest path reliability, $r_{s, t}^{p_{max}}$ , and three paths taking account of the balance between path reliability and path length: $r_{s, t}^{B 1}$ , $r_{s, t}^{B 2}$ , and $r_{s, t}^{B 3}$ . $r_{s, t}^{B 1}$ , $r_{s, t}^{B 2}$ , and $r_{s, t}^{B 3}$ are calculated as follows. We first enumerate all possible $s$ – $t$ paths $r_{s, t} \in R_{s, t}$ except $r_{s, t}^{d_{min}}$ and $r_{s, t}^{p_{max}}$ in descending order of the path reliability. Then, we select three paths out of the sorted path candidates such that the selected path $r_{s, t}$ should satisfy the distance condition $f_{d} (r_{s, t}) \leq f_{d} (r_{s, t}^{p_{max}})$ . Note that the selected paths are labeled as $r_{s, t}^{B 1}$ , $r_{s, t}^{B 2}$ , and $r_{s, t}^{B 3}$ in ascending order of their path length.

There may be more suitable base path selection strategies but it is one of the future directions.

Numerical experiments

In this section, we first show the fundamental characteristics of the the proposed metric (i.e. path reachability including distance-constrained detours) through evaluations under a grid network. Then, we further evaluate the goodness of some representative paths in terms of the path length, path reliability, and proposed metric, under wireless networks and a road network.

Evaluation model

Since the computation of the network reliability is NP-hard, multiple algorithms have been proposed to tackle the computational complexity.^18,39 In this paper, we use Graphillion,⁴⁰ which is a Python library for efficiently computing the network reliability utilizing a zero-suppressed binary decision diagram (ZDD).⁴¹ ZDD is one of the compressed data structures for a family of sets. As for the evaluation networks, we use three kinds of networks, that is a grid network, wireless networks, and a road network.

Fundamental characteristics of proposed metric

We first reveal the fundamental characteristics of the path reachability including distance-constrained detours through numerical experiments using a grid network. Figure 2 illustrates the $5 \times 5$ grid network for evaluation, where the length of each link is set to be 1. We set the availability of each link $e$ highlighted in red color (i.e. located at the central $3 \times 5$ region) to be $p_{e} = 0.9$ and that of each remaining link $e$ to be $p_{e} = 0.99$ . As a result, all $s$ – $t$ paths will be required to traverse the low-availability area. We select two representative $s$ – $t$ paths, $r_{s, t}^{1}$ (a blue line) and $r_{s, t}^{2}$ (a green line), both of which are the shortest path and have the same path reliability.

Figure 2.

Grid network ( $V = 25$ , $E = 40$ ).

Figure 3 depicts the transition of the path reachability including distance-constrained detours of $r_{s, t}^{1}$ and that of $r_{s, t}^{2}$ when changing the allowable distance increase $η$ from the shortest path distance $d_{s, t}^{min}$ . For comparison purpose, we also show the path reliability of $r_{s, t}^{1}$ and $r_{s, t}^{2}$ , network reliability, and diameter constrained network reliability. Recall that the path reliability and the path reachability including distance-constrained detours are path reliability metrics, which depend on the $s$ – $t$ path, that is, $r_{s, t}^{1}$ and $r_{s, t}^{2}$ , while the network reliability and the diameter constrained network reliability are the network reliability metrics, which depend on the $s$ – $t$ pair. We first observe that the path reachability including distance-constrained detours monotonically increases with $η$ . From equation (9), recall that the difference from the path reachability including distance-constrained detours with $η$ to the path reliability is exactly same as the distance-constrained detour possibility with $η$ . For example, when $η = 0$ , we observe from the figure that the distance-constrained detour possibility of $r_{s, t}^{1}$ (resp. $r_{s, t}^{2}$ ) is represented by the blue vertical arrow (resp. green vertical arrow) and becomes 0.196 (resp. 0.038). Since $r_{s, t}^{1}$ always shows higher path reachability including distance constrained detours than $r_{s, t}^{2}$ , it can be regarded as a better path in terms of distance-constrained detours. This is because $r_{s, t}^{1}$ adopts the links located at the center of the network and can have abundant detour candidates, compared with $r_{s, t}^{2}$ . This simple example demonstrates that the proposed metric matches well with the intuitive understanding and can quantitatively evaluate the goodness of a certain path in terms of the distance-constrained detours.

Figure 3.

Impact of $η$ on path reachability including distance-constrained detours of $r_{s, t}^{1}$ and $r_{s, t}^{2}$ (grid network case).

We also confirm that the path reachability including distance-constrained detours of $r_{s, t}^{1}$ and $r_{s, t}^{2}$ is always upper bounded by the diameter constrained network reliability and approaches the $s$ – $t$ network reliability with increase of $η$ . These phenomena can be regarded as the numerical verification of the proof in Appendices: “Proof to Theorem 1” section and “Proof to Theorem 2” section.

Numerical examples of proposed metric for representative paths under realistic networks

In this section, we evaluate the goodness of some representative paths under realistic networks, that is, wireless networks and a road network, in terms of the path length, path reliability, and path reachability including distance-constrained detours. In what follows, we use the five representative paths (i.e. the shortest path $r_{s, t}^{d_{min}}$ , the path with the highest path reliability, $r_{s, t}^{p_{max}}$ , and three paths taking account of the balance between path reliability and path length: $r_{s, t}^{B 1}$ , $r_{s, t}^{B 2}$ , and $r_{s, t}^{B 3}$ ), according to the discussion in “Base path selection strategy” section.

Evaluation under wireless networks

As for wireless networks, we use a unit disk graph model,⁴² which has widely been used for modeling MANETs and sensor networks.^43,44 In the unit disk graph, nodes with transmission range $R$ ( $R > 0$ ) are randomly distributed in the two-dimensional Euclidean space and two nodes are considered to be connected (i.e. have a link) if their Euclidean distance is equal to or less than $R$ , that is, they are located within the transmission range with each other. We generate 25 unit disk graphs with 35 nodes ( $V = 35$ ), identical transmission range ( $R = 0.25$ ), and area size of $1 \times 1$ . Note that the number $E$ of links will be determined by the geographical locations of nodes. Figure 4 illustrates one example among 25 networks, that is, wireless network 1, where $V = 35$ and $E = 70$ .

Figure 4.

Wireless network 1 ( $V = 35$ , $E = 70$ ).

We randomly select 60% links as “less reliable” and the remaining as “more reliable.” In particular, each less (resp. more) reliable link $e$ has link availability $p_{e}$ following a uniform distribution in the range of $[0.80, 0.95]$ (resp. $[0.998, 1.0]$ ) as in the existing work.⁴⁵ We set the source node $s$ (resp. destination node $t$ ) to the node closest to the upper left (resp. lower right) of the network. We also show the five representative paths in Figure 4. Since they share some links with others, their locations are adjusted to avoid the overlapping as much as possible.

Figure 5 illustrates the impact of $η$ on the path reachability including distance-constrained detours of the five representative paths in wireless network 1. For comparison purpose, we also show the network reliability, diameter constrained network reliability, and path reliability of them. Note that unlike with Figure 3, the path reliability becomes different among the five paths. As for each path except the shortest path, that is, $r_{s, t}^{p}$ ( $p \in {p_{max}, B 1, B 2, B 3}$ ), we show a vertical arrow from the point of the path reachability $f_{p} (r_{s, t}^{p})$ to that of the path reachability including distance-constrained detours with $η = η_{0}^{p}$ , that is, $f_{R} (r_{s, t}^{p}, p, d_{s, t}^{min} + η_{0}^{p})$ , where $η_{0}^{p}$ is the difference of path length between $r_{s, t}^{p}$ and $r_{s, t}^{d_{min}}$ , that is, $f_{d} (r_{s, t}^{p}) - f_{d} (r_{s, t}^{d_{min}})$ . Note that we omit the vertical arrow for $r_{s, t}^{d_{min}}$ because its arrow length becomes zero. The length of the vertical arrow for $r_{s, t}^{p}$ presents the lower bound of the distance-constrained detour possibility, $f_{D} (r_{s, t}, d_{s, t}^{min} + η_{0}^{p})$ , (i.e. the difference between the lower bound of the path reachability including distance-constrained detours $f_{R} (r_{s, t}^{p}, p, d_{s, t}^{min} + η_{0}^{p})$ and path reliability $f_{p} (r_{s, t}^{p})$ ) for the corresponding path $r_{s, t}^{p}$ . Note that unlike with Figure 3, each path $r_{s, t}^{p}$ has the different path length, and thus the corresponding $η_{0}^{p}$ also differs. The long (resp. small) vertical arrow indicates that the corresponding path can drastically (resp. slightly) improve the reachability thanks to the detours without increasing the total path length. In this aspect, we confirm that the representative paths except the shortest path are attractive.

Figure 5.

Impact of $η$ on path reachability including distance-constrained detours (Wireless network 1).

We also observe that the path reachability including distance-constrained detours monotonically increases with $η$ , regardless of the paths. In particular, we confirm that the path reachability including distance-constrained detours of $r_{s, t}^{B 1}$ can be improved by 6.53%, compared with that of $r_{s, t}^{p_{max}}$ , when $η = 0.35$ . Since $r_{s, t}^{B 1}$ also has shorter path length than $r_{s, t}^{p_{max}}$ at the slight decrease of the path reachability, it can be viewed as an attractive path. We also confirm that the diameter constrained network reliability gives the upper bound of the path reachability including distance-constrained detours, regardless of the paths.

Next, we focus on another network example (wireless network 2) with five representative paths, as shown in Figure 6. Figure 7 illustrates the impact of $η$ on the path reachability including distance-constrained detours of the five representative paths in wireless network 2. As in Figure 5, we also give the network reliability, diameter constrained network reliability, and path reliability of them. As for the vertical arrow, we only show it for $r_{s, t}^{p_{max}}$ . We observe that the lower bound $f_{D} (r_{s, t}, d_{s, t}^{min} + η_{0}^{p})$ of the path reachability including distance-constrained detours of path $r_{s, t}^{p}$ ( $p \in {d_{min}, B 1, B 2, B 3}$ ) exhibits almost the same performance as the path reliability $f_{p} (r_{s, t}^{p})$ of $r_{s, t}^{p}$ . This phenomenon stems from the structure of wireless network 2 where every $s$ – $t$ path must pass through a crucial link, which is designated in Figure 6, and thus taking detours becomes difficult.

Figure 6.

Wireless network 2 ( $V = 35$ , $E = 86$ ).

Figure 7.

Impact of $η$ on path reachability including distance-constrained detours (Wireless network 2).

As for the impact of $η$ on the path reachability including distance-constrained detours, we confirm the similar tendency observed in Figure 5. In this case, $r_{s, t}^{p_{max}}$ shows relatively good characteristics from the viewpoint of both the path reliability and path reachability including distance-constrained detours.

So far we have focused on wireless networks 1 and 2 as illustrative examples. Finally, we demonstrate more general results by showing the average results of 25 wireless networks, as shown in Figure 8. We confirm that the trends observed in the two examples hold.

Figure 8.

Impact of $η$ on path reachability including distance-constrained detours (Average of 25 wireless networks).

Finally, we focus on the routing hole problem. Although the routing hole itself is a problem in the reactive approach (i.e. the hop-by-hop based routing like the greedy forwarding), where nodes in the routing hole cannot find any nodes closer to the destination, we can use the above-mentioned proactive approach to assess the upper bound of the reactive routing performance under a potential risk of routing holes. In what follows, we give a simple example.

Suppose that a node $υ$ vanishes from wireless network 1 in Figure 4, due to some reason (e.g. node failure or battery depletion), which causes a routing hole as shown in Figure 9. By comparing Figure 9 with Figure 4, we confirm that $r_{s, t}^{d_{min}}$ is identical while the remaining $r_{s, t}^{p_{max}}$ , $r_{s, t}^{B 1}$ , $r_{s, t}^{B 2}$ , and $r_{s, t}^{B 3}$ change. More specifically, $r_{s, t}^{d_{min}}$ and $r_{s, t}^{B 1}$ take the southern routes, which emphasize the distance, while $r_{s, t}^{p_{max}}$ , $r_{s, t}^{B 2}$ , and $r_{s, t}^{B 3}$ take the northern routes, which emphasize the reliability.

Figure 9.

Wireless network 1 with routing hole ( $V = 35$ , $E = 70$ ).

Figure 10 depicts the impact of $η$ on the path reachability including distance-constrained detours of the five representative paths in Figure 9. As in Figure 5, we also give the network reliability, diameter constrained network reliability, and path reliability of them. By comparing Figure 10 with Figure 5, we can confirm that the disappearance of the four dotted links of node $υ$ causes the longer path length of northern routes (i.e. $r_{s, t}^{p_{max}}$ , $r_{s, t}^{B 2}$ , and $r_{s, t}^{B 3}$ ) and the lower path reachability including distance-constrained detours for all the representative paths.

Figure 10.

Impact of $η$ on path reachability including distance-constrained detours (Wireless network 1 with routing hole).

Evaluation under a road network

We consider an evacuation situation under a large-scale disaster. In Japan, a municipality, for example, Nagoya city, has been assessing the potential blockage risk of each road segment in its administrative area under large-scale disasters, for example, earthquake. More specifically, using a mathematical model, it gives the road blockage probability $p'_{e}$ $(0 \leq p'_{e} \leq 1)$ that the road segment $e \in E$ is blocked by collapsed roadside buildings due to an earthquake.⁴⁶ In this case, we can regard the availability $p_{e}$ of each link $e \in E$ as $1 - p'_{e}$ .

Figure 11 shows the road network of $2, 640 [m] \times 1, 690 [m]$ Arako area of Nagoya city in Japan.⁴⁶ This area is further divided into three refuge areas using the existing refuge assignment scheme⁴⁷: Area 1 ( $1, 220 [m] \times 960 [m]$ green area), Area 2 ( $540 [m] \times 740 [m]$ red area), and Area 3 ( $1, 680 [m] \times 1, 500 [m]$ blue area). We also show the availability $p_{e}$ of each link $e$ .

Figure 11.

Road network ( $2, 640 [m] \times 1, 690 [m]$ area of Nagoya city in Japan) with three refuge areas: Area 1 ( $1, 220 [m] \times 960 [m]$ green area), Area 2 ( $540 [m] \times 740 [m]$ red area), Area 3 ( $1, 680 [m] \times 1, 500 [m]$ blue area).

In each area $a \in {1, 2, 3}$ , we prepare three evacuation situations where an evacuee moves from a certain position $s = s_{a, i}$ $(i \in {1, 2, 3})$ (a green point) to the corresponding refuge $t = t_{a}$ (a blue point), as shown in Figures 12(a), 13, and 14(a) for Area 1, Figures from 15(a) through 17(a) for Area 2, and Figures from 18(a) through 20(a) for Area 3. Note that Figures 13 through 20 are given as the supplemental materials. In each figure, we also show the five representative paths: the shortest path $r_{s, t}^{d_{min}}$ , the path with the highest path reachability, $r_{s, t}^{p_{max}}$ , and three paths taking account of the balance between path reliability and path length: $r_{s, t}^{B 1}$ , $r_{s, t}^{B 2}$ , and $r_{s, t}^{B 3}$ . Considering the computational complexity to calculate the path reachability including distance-constrained detours using ZDD, we first extract the part of the road network in a minimum polygon shape such that the extracted road network includes the five representative paths.

Figure 12.

Results of road network (Area 1, $s = s_{1, 1}, t = t_{1}$ ): (a) network topology and five representative paths. (b) impact of η on path reachability including distance-constrained detours.

Figure 12(b) illustrates the impact of $η$ on the path reachability including distance-constrained detours of the five representative paths in case of Area 1 with $s = s_{1, 1}$ and $t = t_{1}$ . As in Figure 5, we also give the network reliability, diameter constrained network reliability, and path reliability of them. As for the vertical arrows, we show them for $r_{s, t}^{p}$ ( $p \in {p_{max}, B 1, B 2, B 3}$ ). We first observe that $r_{s, t}^{p}$ ( $p \in {p_{max}, B 1, B 2, B 3}$ ) has 25.28–27.13 (resp. 1.19–1.38) times as large path reliability (resp. long path length) as $r_{s, t}^{d_{min}}$ . From the viewpoint of the path reachability including distance-constrained detours, $r_{s, t}^{p}$ ( $p \in {d_{min}, B 1, B 2}$ ) always outperforms $r_{s, t}^{p'}$ ( $p' \in {p_{max}, B 3}$ ). As a result, in this case, we think $r_{s, t}^{B 1}$ and $r_{s, t}^{B 2}$ are well-balanced in terms of the path length, path reliability, and distance-constrained detour possibility.

We can confirm the similar tendency in other cases as shown in Figures 13 through 20 in the supplemental materials.

Conclusion

In this paper, we have proposed a new concept of distance-constrained detour possibility, which is the probability that the source $s$ is reachable to the destination $t$ using detours such that the total path length including a detour is equal to or less than a certain threshold. We have further formulated a new path metric of path reachability including distance-constrained detours as the sum of the path reliability and the distance-constrained detour possibility. We have proved that (1) the proposed metric is equivalent to the network reliability in case of no distance constraint and (2) it is upper bounded by the diameter constrained network reliability.

Through numerical experiments using a grid network, we have shown the fundamental characteristics of the path reachability including distance-constrained detours and the relation with the network reliability and diameter constrained network reliability. We have further evaluated the goodness of five representative paths, that is, the shortest path, the most reliable path, and three paths taking account of the balance between path reliability and path length, through numerical experiments using realistic networks, that is, wireless networks and a road network. We have shown that some of the representative paths can be well-balanced paths for these networks in terms of the path length, path reliability, and path reachability including distance-constrained detours.

In future work, we plan to tackle the computation complexity problem of calculating path reachability including distance-constrained detours, with the help of approximation methods for network reliability, for example, Monte Carlo based approaches.

Supplemental Material

sj-pdf-1-pio-10.1177_1748006X221133600 – Supplemental material for Path reachability including distance-constrained detours

Supplemental material, sj-pdf-1-pio-10.1177_1748006X221133600 for Path reachability including distance-constrained detours by Masahiro Sasabe, Miyu Otani, Takanori Hara and Shoji Kasahara in Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability

Footnotes

Appendix

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

Masahiro Sasabe

Supplemental material

Supplemental material for this article is available online.

References

Boesch

Satyanarayana

Suffel

CL.

A survey of some network reliability analysis and synthesis results. Networks 2009; 54(2): 99–107.

Gertsbakh

Shpungin

Models of network reliability: analysis, combinatorics, and Monte Carlo. Boca Raton, FL: CRC Press, 2016.

Inoue

Reliability analysis for disjoint paths. IEEE Trans Reliab 2019; 68(3): 985–998.

Gaur

Yadav

Soni

, et al. A literature review on Network Reliability Analysis and its engineering applications. Proc IMechE, Part O: J Risk and Reliability 2021; 235(2): 167–181.

Hara

Sasabe

Kasahara

Geographical risk analysis based path selection for automatic, speedy, and reliable evacuation guiding using evacuees’ mobile devices. J Ambient Intell Humaniz Comput 2019; 10(6): 2291–2300.

Petingi

Rodriguez

Reliability of networks with delay constraints. Congressus Numerantium 2001; 152: 117–124.

Kasai

Sasabe

Kasahara

Congestion-aware route selection in automatic evacuation guiding based on cooperation between evacuees and their mobile nodes. EURASIP J Wirel Commun Netw 2017; 2017(1): 164–211.

Komatsu

Sasabe

Kawahara

, et al. Automatic evacuation guiding scheme based on implicit interactions between evacuees and their mobile nodes. GeoInformatica 2018; 22(1): 127–141.

Hardy

Lucet

Limnios

K-terminal network reliability measures with binary decision diagrams. IEEE Trans Reliab 2007; 56(3): 506–515.

10.

Xiang

Yang

k-Terminal reliability of ad hoc networks considering the impacts of node failures and interference. IEEE Trans Reliab 2020; 69(2): 725–739.

11.

Ball

MO.

Computational complexity of Network Reliability Analysis: an overview. IEEE Trans Reliab 1986; 35(3): 230–239.

12.

Canale

Cancela

Robledo

, et al. Diameter constrained reliability: complexity, distinguished topologies and asymptotic behavior. Netw 2015; 66(4): 296–305.

13.

Rosenthal

Computing the reliability of complex networks. SIAM J Appl Math 1977; 32(2): 384–393.

14.

Abraham

JA.

An improved algorithm for network reliability. IEEE Trans Reliab 1979; R-28(1): 58–61.

15.

Ball

Colbourn

Provan

JS.

Chapter 11 network reliability. In: Handbooks in operations research and management science, Vol. 7, 1995, pp.673–762. Amsterdam: Elsevier.

16.

Dotson

Gobien

A new analysis technique for probabilistic graphs. IEEE Trans Circuits Syst 1979; 26(10): 855–865.

17.

Satyanarayana

Chang

MK.

Network reliability and the factoring theorem. Netw 1983; 13(1): 107–120.

18.

Beccuti

Bobbio

Franceschinis

, et al. A new symbolic approach for network reliability analysis. In: Proceedings of IEEE/IFIP international conference on dependable systems and networks2012, pp.1–12. New York: IEEE.

19.

Fishman

GS.

A Monte Carlo sampling plan for estimating network reliability. Oper Res 1986; 34(4): 581–594.

20.

Yeh

WC.

Novel Self-adaptive Monte Carlo simulation based on binary-addition-tree algorithm for binary-state network reliability approximation. Reliab Eng Syst Saf 2022; 228: 108796.

21.

L’Ecuyer

Rubino

Saggadi

, et al. Approximate zero-variance importance sampling for static network reliability estimation. IEEE Trans Reliab 2011; 60(3): 590–604.

22.

Paredes

Dueñas-Osorio

Meel

, et al. Principled network reliability approximation: a counting-based approach. Reliab Eng Syst Saf 2019; 191: 106472.

23.

Davila-Frias

Yadav

OP.

All-Terminal network reliability estimation using convolutional neural networks. Proc IMechE, Part O: J Risk and Reliability 2022; 236(4): 584–597.

24.

Davila-Frias

Yadav

Salem

, et al. All-Terminal network reliability estimation with Graph Neural Networks. In: Proceedings of annual reliability and maintainability symposium (RAMS)2022, pp.1–6. New York: IEEE.

25.

Zhang

Zio

, et al. Network reliability analysis based on percolation theory. Reliab Eng Syst Saf 2015; 142: 556–562.

26.

Bunde

Havlin

Fractals and disordered systems. Berlin Heidelberg: Springer Science & Business Media, 2012.

27.

Stauffer

Aharony

Introduction to percolation theory. London: CRC press, 2018.

28.

Kuo

Yeh

Lin

HY.

Efficient and exact reliability evaluation for networks with imperfect vertices. IEEE Trans Reliab 2007; 56(2): 288–300.

29.

Walteros

Pardalos

PM.

Selected topics in critical element detection. In: Applications of mathematics and informatics in military science. Berlin Heidelberg: Springer, 2012. pp. 9–26.

30.

Ahuja

Network flows: Theory, algorithms, and Applications. Englewood Cliffs, NJ: Prentice Hall, 1993.

31.

Yick

Mukherjee

Ghosal

Wireless Sensor Network Survey. Comput Netw 2008; 52(12): 2292–2330.

32.

Zonouz

Xing

Vokkarane

, et al. Reliability-oriented single-path routing protocols in wireless sensor networks. IEEE Sens J 2014; 14(11): 4059–4068.

33.

Nowsheen

Karmakar

Kamruzzaman

PRADD: A Path Reliability-aware data delivery protocol for Underwater Acoustic Sensor Networks. J Netw Comput Appl 2016; 75: 385–397.

34.

Chatterjee

Das

Ant colony optimization based enhanced dynamic source routing algorithm for mobile ad-hoc Network. Inf Sci 2015; 295: 67–90.

35.

Sai Kumar

Padmavathy

. A hybrid link reliability model for estimating path reliability of Mobile ad hoc Network. Procedia Comput Sci 2020; 171: 2177–2185.

36.

Cadger

Curran

Santos

, et al. A survey of geographical routing in wireless ad-hoc Networks. IEEE Commun Surv Tutor 2013; 15(2): 621–653.

37.

Huang

Yin

Min

, et al. Energy-aware dual-path geographic routing to bypass routing holes in wireless sensor networks. IEEE Trans Mob Comput 2018; 17(6): 1339–1352.

38.

Lima

Oliveira

HAB

Guidoni

, et al. Geographic Routing and hole bypass using long range sinks for wireless sensor networks. Ad Hoc Netw 2017; 67: 1–10.

39.

Graph-based algorithms for Boolean function manipulation. IEEE Trans Comput 1986; C-35(8): 677–691.

40.

Inoue

Iwashita

Kawahara

, et al. Graphillion: Software Library for very large sets of labeled graphs. Int J Softw Tools Technol Transf 2016; 18(1): 57–66.

41.

Minato

SI.

Zero-suppressed BDDs and their applications. Int J Softw Tools Technol Transf 2001; 3(2): 156–170.

42.

Clark

Colbourn

Johnson

DS.

Unit disk graphs. In: Annals of discrete mathematics, vol. 48. Amsterdam: Elsevier, 1991, pp. 165–177.

43.

Hoffmann

Wanke

. Generic Route Repair: augmenting wireless ad hoc sensor networks for local connectivity. In: Proceedings of 2016 15th ACM/IEEE international conference on information processing in sensor networks (IPSN)2016, pp.1–10. New York: IEEE.

44.

Khallef

Molnar

Benslimane

, et al. Multiple constrained QoS routing with RPL. In: Proceedings of 2017 IEEE international conference on communications (ICC)2017; 1–6. New York: IEEE.

45.

Malboubi

Sharma

Compressive sensing network inference with multiple-description fusion estimation. In: Proceedings of 2013 IEEE global communications conference (GLOBECOM)2013,pp. 1557–1563. New York: IEEE.

46.

City of Nagoya. Earthquake-resistance city development policy (in Japanese). http://www.city.nagoya.jp/jutakutoshi/cmsfiles/contents/0000002/2717/honpen.pdf (2015, accessed 10 January 2022).

47.

Hara

Sasabe

Matsuda

, et al. Capacitated refuge assignment for speedy and reliable evacuation. ISPRS Int J Geo Inf 2020; 9(7): 442442–519.

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

0.65 MB