Measures of region failure survivability for wireless mesh networks

Recent works on network survivability evaluation provide the respective methodology mainly for wired networks (see e.g., [20‐25]). Only a few of them refer to wireless networks. Early papers on wireless networks survivability focused on connectivity of a network topology as a measure of fault-tolerance [26]. In general, this metric can be used to give a binary answer to the question, whether transmission after a simultaneous failure of k-1 elements (nodes/links) is possible. If the answer is positive, then the network is said to be k-connected. Specific variations of this metric include e.g., average connectivity [27], distance connectivity [28], or path connectivity [29].

However, they are all not suitable for a region failure scenario, where faults of network elements occur only in bounded areas. To capture these characteristics, region-based connectivity was introduced (see e.g., [15‐17], and [26]). In particular, in [26] it was shown that the difference between connectivity and region-based connectivity can be arbitrarily large.

Papers considering the circular region failure scenario in WMNs include the models of:

Natural disasters, or attacks are rarely deterministic, and nodes being within their scope fail with a certain probability. Therefore, the use of probabilistic models is more appropriate. However, known probabilistic approaches also have limitations. In particular, the authors of [15] assume that the size of a failure region (defined by radius r) is constant. Another constraint in [15] is that probability p _n of node n failure, even though it is decreasing with the distance r _n of node n from the failure epicentre, is constant in each i-th area between two consecutive concentric annuluses, as given in Fig. 2a. This in turn may result in over-, or underestimating the node failure probability values in some areas (which was in fact shown in that paper).

The main purpose of connectivity measures presented in [16, 17], and [26] is to determine whether transmission in WMNs is possible between pairs of non-faulty nodes. However, no survivability functions are currently available in the literature that are designed to evaluate vulnerability of WMNs to failures occurring in regions of differentiated radiuses r. Our paper is thus the first one to propose such measures for the case of varying radius r of a failure region, and utilizing the continuous function of node failure probability (see Fig. 2b and Eq. 3), thus covering the models from [15, 17] as special cases.

It is worth noting that some survivability measures have been proposed in the literature so far only for random failure scenarios in wired networks (see e.g., [30]), assuming that failures of network elements are statistically independent and equally probable. This is, however, completely in contrast to common characteristics of region failures in WMNs, which makes any comparison of measures introduced here with the ones for wired networks (e.g., from [30]) inadequate.

In this paper, we assume that the network topology is given by a graph G = (N, E), where N is the set of wireless mesh nodes, and E is the set of directed edges e _h  = (i, j). Each WMN link between nodes i and j is modelled by two edges in opposite directions. Location of any node n is given by coordinates (x _n , y _n ). Nodes are considered here to be stationary (which is a common scenario in WMNs [31]). However, analysis presented in this paper can be still valid for mobile nodes assuming evaluation of a network topology at certain time t (i.e., investigating the respective instant topology at time t).

Available capacity of any WMN link is a result of influence of multiple factors, the most important ones being: medium access protocol implementation, inter-channel interference implied by the respective link scheduling algorithm [32, 33], as well as time-varying factors including e.g., weather-based disruptions caused by heavy rain falls (general propagation conditions) [10, 34]. As a result, even in case of stationary WMN nodes, effective link capacity changes over time. In such a scenario, when evaluating survivability properties of WMNs, it is proper to analyze them at certain time t. Therefore, in this paper we assume that at the observation time t, each edge e _h is characterized by capacity c _h (t).

The set of demands, denoted as K, consists of demands k defined by ordered triples (p _k , q _k , \( \hat{d}_{k} \)), i.e., including the respective source and destination nodes p _k and q _k , as well as the demanded capacity \( \hat{d}_{k} \).

Two matrices will be used in our model description: A _nn and D _nn . Node-to-node incidence matrix A _nn is used to provide the connectivity information, with elements a _ij defined as given in Eq. 1.

Elements d _pq of matrix D _nn store information about aggregate capacities \( \hat{d}_{k} \) required for flows (commodities) k between given pairs of end nodes.

Each time, location of a failure epicentre is chosen at random within the smallest rectangular area containing the network. We assume a probabilistic failure scenario, in which any disruptive event affects nodes localized within a given radius r from the failure epicentre. In particular, in our model:

where:

Our definition of a WMN node failure probability function given by Eq. 3 is justifiable, since, as stated in [15], the power of real physical attacks (including e.g., bomb explosions, electromagnetic pulse (EMP) attacks), or natural disasters (e.g., earthquakes, floods, etc.) is known to attenuate gradually with the increase of the distance of WMN nodes from the failure epicentre. Following [15], the maximum value of node failure probability equals 1 (if the failure epicentre matches exactly the location of node n), while its minimal value (i.e., 0) is assumed for nodes located at a distance r _n of at least r from the failure epicentre.

This gradual attenuation of P(r _n ) values with the increase of the distance r _n can be disturbed by environmental factors including e.g., topography, or node protection characteristics. However, if we neglect them to simplify the analysis (e.g., as in [15]), we obtain the linear decrease of probability P(r _n ) of a node n failure with the increase of the distance r _n between this node and the centre of a disruptive event, as proposed in Eq. 3.

In the remaining part of the paper:

We introduce the following measures of a wireless mesh network survivability for a region failure scenario:

According to Eq. 5, for any value of ψ, RFS(ψ) is defined as the cumulative probability of all region failure scenarios δ (i.e., for differentiated radiuses r of failure regions), for which at least ψ percent of flows are successfully transmitted after failures. Therefore, it can be also expressed as the reverse cumulative distribution function of Ψ. Although Eq. 5 has some similarities with the respective one from [30] for wired networks, calculation of P(δ) values is completely different (see Sect. 5).

As given in formula (6), the value of p-fractile region survivability is defined as the minimum percentage ψ of flows successfully delivered after a region failure, for which the probability of not exceeding this value is equal to p. In other words, PFRS gives us useful information about probability p that the total flow will be reduced to at most ψ percent after a region failure.

The common feature of RFS and PFRS measures is that they do not depend directly on radius r (i.e., they allow radius r to take any value from (0, r _max ) interval). These functions are thus designed to give general information on network vulnerability to region failures.

RFS and PFRS measures are thus convenient to use if the objective is to analyze the performance of wireless mesh networks independent of the size r of a failure region. Although they are similar to each other in terms of utilization scenarios, information they provide is of a different type. For instance, if for a given WMN at least ψ percent of traffic should be delivered independent of region failures (e.g., because such a portion of traffic is considered to be critical based on the Service Level Agreement between network operator and the customers), then RFS measure will provide appropriate information about probability p of fulfilling this requirement under region failures independent of the failure region size r. Naturally, the greater is the value of p, the better.

PFRS, is in turn useful for a network operator to see, given probability p, what is the upper bound on the fraction ψ of flow surviving a region failure, e.g., in statements like: “with probability 0.5 the total flow will be reduced to at most 60 %”. This measure is thus useful to provide information on probability that not all of ψ percent of flows (e.g., referred to as the critical flow) will survive the region failure.

Unlike RFS and PFRS, the following EPFD function provides a detailed characteristics with respect to particular radiuses r of failure regions.

where:

As given in formula (7), EPFD(r) is defined as the expected value of percentage of flows to survive node failures occurring in circular regions of a given radius r, i.e., calculated using the probability density function f _Ψ (ψ, r) determined for region failures of a specified radius r [formula (8)].

Example scenarios of EPFD measure utilization include performance analysis/comparison of WMNs in case of region failures related e.g., to natural disasters (like flood, or volcano eruption) with expected radiuses r of the failure region. Also, when expecting a failure characterized by a given radius r (e.g., incoming flood), network operator can use this information to predict its impact on the WMN performance, and, if possible, try to take preventive actions.

In the latter part of the paper, we will provide information on how to utilize the introduced measures to evaluate vulnerability of wireless mesh networks to region failures. We will also show how to use them to compare characteristics of several different WMN topologies.

In this section, we show how to evaluate survivability characteristics of a wireless mesh network under region failures. In particular, this section is to explain the methodology of determining RFS, PFRS, and EPFD survivability characteristics for WMNs. Proposed measures can be derived from the auxiliary function F[ψ], where ψ ∈ {0,1,…, 100}, providing information on the frequency a given percentage ψ of flows was successfully delivered after region failures.

In real life, F[ψ] values would be collected for an existing wireless mesh network based on observations of the network performance after consecutive occurrences of disruptive events bringing about the region failures of WMN nodes. However, taking into consideration long values of real inter-failure time, typically measured in terms of months/years, deriving any survivability characteristics based on real-life experiments would be extremely time-consuming, and, therefore, practically impossible. It is thus crucial to define an iterative procedure to simulate consecutive region failures in a realistic way that eliminates the inter-failure time from evaluations. Additional benefit would be also the possibility to analyze not only the performance of existing networks, but also to predict the survivability characteristics of planned (i.e., non-deployed) wireless mesh networks based on information about the abstract topology of a WMN, as well as on estimated traffic demands.

Such a procedure of determining F[ψ] values by means of simulations for a single set of demands is proposed in Fig. 3. As an input, the most important information that it takes includes: (1) the topology of an existing/planned wireless mesh network determined by graph G = (N, E), where N and E are the sets of vertices and directed edges, accordingly, representing WMN nodes and links, respectively; (2) location of network nodes determined by coordinates (x _n , y _n ); (3) information related to traffic demands defined by the source and destination nodes, as well as the demanded capacity.

Each iteration of this procedure (defined by Steps 3–11) is to obtain the percentage ψ of flows successfully delivered after a single region failure. Following [15], coordinates of each region failure epicentre, as well as radius r of a failure region can be considered as random values defined by the continuous uniform distribution function. Therefore, in each iteration of our procedure, characteristics of a failure region can be determined randomly (Step 5), implying that inter-failure time need not be simulated. In particular, it means that in each iteration:

The set of failed nodes is next identified in Step 6, as proposed in Eq. 3. After that, in order to evaluate the percentage ψ of flows successfully delivered in a given region failure scenario, for each flow that can be served after a region failure (i.e., with both end nodes being non-faulty), our procedure tries to find a new (alternate) path of capacity \( \hat{d}_{k} \) (Steps 9.1–9.5). If the respective path is found, but, due to link capacity limitations, it cannot be assigned the full demanded capacity \( \hat{d}_{k} \), this procedure tries to apply the multipath routing to increase as much as possible the capacity assigned to demand k after a region failure (Step 10). After finishing the process of finding the alternate paths for all demands in a given region failure scenario, the percentage ψ of flows successfully delivered after a failure is calculated based on the ratio of the aggregate flow c _f restored after the failure to the total flow c being transported before the failure (Step 11). Calculations are repeated until the assumed number fr of region failures are analyzed (Step 13).

RFS, PFRS and EPFD functions can be easily obtained based on F[ψ]. In particular, RFS(ψ) can be calculated based on empirical probabilities of restoring ψ percent of flows after failures (each empirical probability of restoring ψ percent of flows can be obtained by dividing the respective value of F[ψ] by fr, i.e., by the total number of analyzed region failures). According to Eq. 5, RFS(ψ) can be next determined as the reverse cumulative distribution function of Ψ. PFRS(p) can be also calculated based on the cumulative distribution function of Ψ [see formula (6)]. Finally, EPFD(r) can be calculated based on probability density functions f(ψ, r) found separately for each radius r of a failure region, using Eq. 7.

It is worth noting that the optimal solution to the problem of finding a new set of paths after failures of nodes occurring in a given region with the objective to maximize the percentage of restored flows may be obtained e.g., by finding the solution to the respective linear programming problem (LP) [35]. However, due to its NP-completeness finding the optimal solution is feasible using only offline approaches for small problem instances (e.g., for networks up to 12–15 nodes). Therefore in our simulations, determining the detours in Step 9 of the algorithm from Fig. 3 was done using the reactive heuristic approach based on the Dijkstra’s algorithm from [36], having the polynomial computational complexity bounded in above by O(|N| ² ), where |N| is the number of WMN nodes.

In this section, we present utilization of proposed measures to evaluate the vulnerability of five example wireless mesh networks from Fig. 4 to region failures, i.e., N29, N29_2, N29_3, N44, and N59 networks. First three of them (shown in Fig. 4a–c) consist of 29 nodes connected by 68, 68, and 57 links, accordingly. The remaining two networks (Fig. 4d, e) are formed by 44, and 59 nodes, respectively, connected by 97, and 150 wireless links, accordingly. Nodes of 29-node networks were located in 4,000 × 10,000 m², 6,000 × 6,000 m², and 8,000 × 8,000 m² fields, accordingly, while for N44 and N59 networks, a field of 10,000 × 10,000 m² was assumed. Due to the fact that horizontal and vertical sizes of the first (i.e., N29) network rectangular areas (4,000 m and 10,000 m, accordingly) differed much from each other, this network was expected to have the worst properties concerning the portion of flows surviving the region failures of the analyzed radiuses r up to half the largest Euclidean distance between any two nodes in the network.

In simulations, both before and after failures, paths were found as the cheapest ones using the distance metric [37, 38]. After failures, redirection of flows with survived end nodes took place in a reactive manner. In order to provide the appropriate statistical results concerning RFS, PFRS, and EPFD functions, the respective F[ψ] values were the aggregate ones achieved with respect to all φ = 100 investigated demand sets of a certain size with fr = 9,000 analyzed random failure regions per each demand set.

In particular, we considered three simulation scenarios. The first two (Scenario A and B) were intended to utilize the proposed measures to evaluate characteristics of different WMN topologies, but under a similar network load. In this case, the sets of unicast transmission demands consisted of 25 % of randomly chosen node pairs. In Scenario A, special focus was put on analysing characteristics of networks of the same size in terms of the number of nodes (i.e., N29, N29_2, and N29_3 networks consisting of 29 nodes), while Scenario B was prepared to evaluate networks being similar in terms of the area they covered (i.e., not necessarily similar in terms of the number of nodes). Topologies analyzed in Scenario B included: N29, N44, and N59.

In Scenario C, we used our measures under differentiated loads of N59 network, implied by four sizes of demand sets (i.e., consisting of randomly chosen 25, 50, 75, and 100 % node pairs). For each unicast demand k, the requested capacity \( \hat{d}_{k} \) was assumed to be unitary, while each network link offered the aggregate capacity of 160 units in each direction. Radiuses r of failure regions were uniformly distributed in range (0, r _max ), where r _max was assumed to be equal to half the largest Euclidean distance between any two nodes in the network.

Statistical analysis of results based on 95 % confidence intervals, showed that sizes of these intervals did not exceed 1 % of the original values. Therefore, due to low visibility, these intervals are not shown in Figs. 5, 6, 7, 8, 9, 10, 11, 12, 13, 14.