Wireless Sensor networks (WSNs) have recently received increased attractiveness driven by many mission-critical applications such as battlefield reconnaissance and homeland security monitoring. Mission critical here refers to networking for application domains whose infrastructure and operations are absolutely necessary for an organization to carry out its mission . Therefore, the main feature that must be guaranteed by all networks running mission critical applications is the network continuity.
However, due to the nature of the deployment field, these networks are vulnerable to natural disasters such as earthquakes, tornadoes or floods. Moreover, they are also subject to physical attacks such as an Electro-Magnetic Pulse (EMP) attack and security breaches such as sinkhole and selective forwarding attacks . Such real world events may happen in particular geographical areas and disrupt specific parts of the network. Therefore, the geographical layout of the network topology determines the impact of such events on the network’s connectivity.
Several contributions in the literature have addressed the failure modeling and survivability problems. The authors in [3, 4] tackled the single link failure problem in the logical topology. The authors in  focus on the dual link failure assumption. Most of these studies are based on a common assumption that failures are independent of their locations and randomly distributed across the network, which fails to reflect several real scenarios. Such real-world events have geographical nature, and therefore, the geographical structure of the network affects the impact of these events. Under such region failure scenarios, several network components within a geographically correlated region may be simultaneously destroyed, resulting in network holes, cuts (partitions) or even breakdown of the overall network connectivity as shown in Fig. 1. Therefore, it is essential to assess the vulnerabilities of mission critical networks to such region-failures.
Some research has been conducted to understand the impact of region failures on wired backbone networks such as [11–18]. On the other hand, the cut detection problem has been investigated by  and .
Recently, few studies have tackled the region-failure problem in wireless networks. The authors in [7–9] investigated the region- based connectivity issue in wireless networks and demonstrated the effect of the transmitting power on maintaining a region-based connectivity in the presence of single and multiple region failures. The authors in  proposed a more general Probabilistic Region Failure (PRF) Model to capture the key features of geographically correlated region failures. They also developed a framework to apply the PRF model for the reliability assessment of wireless mesh networks.
All of the aforementioned studies about regional-failures consider a worst-case cut as the cut which maximizes or minimizes certain performance metric (such as capacity) of the intersected links. However, such a definition is inadequate to capture many realistic situations where the faulty nodes may influence larger number of nodes rather than larger number of link-cuts. we claim that, using the number of failed links as the main criteria for defining the worst-case region cut underestimates the impact of a region failure on the overall network performance.
Therefore, in this chapter, we first introduce a new definition for a worst-case cut (partition) due to failure regions. Then, we identify the location of a disaster that would have the maximum impact on a test network using both definitions. Finally, we conduct a deeper analysis to understand the behavior of a single and dual region-failures on the network performance with mission-critical nodes. Our simulation results indicate that, current studies in regional failures under estimate the impact of the worst-case cut due to their dependence on a relaxed definition for the worst-case region-cut.
The rest of this chapter is organized as follows. Section 2 presents the problem investigation. Section 3 demonstrates our proposed scheme for identifying the worst-case cut under single and dual region-failures. Section 4 presents our experimental results. Finally, Section 5 concludes our chapter.
2. Problem investigation
Most of the available studies [21–23] in the literature consider that the failure probability of a node is independent of its location in the deployment area. Few studies [6–10] addressed the region failure problem of spatially correlated network nodes in the physical topology. Available studies focusing on region failures consider link-cuts due to a region-failure as the main criteria for identifying the worst-case region-failure and can be interpreted in terms of the network capacity and throughput. However, such fault scenario is inadequate to capture many realistic situations where the failure region may influence larger number of nodes rather than larger number of link-cuts as shown in Fig.2.
For the network shown in Fig. 2, suppose that all links have the same capacity. Then, it can be easily seen that the region failure in Fig. 2a leads to 10 link-cuts while the region failure shown in Fig. 2b leads to only 6 link-cuts. Based on the current studies, the region with the maximum number of link-cuts is identified as the worst-case cut (i.e the region in Fig. 2a). On the other hand, the failure region depicted in Fig. 2b disconnects the dashed region (8 nodes) from the rest of the network which has a greater impact on the network than the case shown in Fig. 2a which has only 6 disconnected nodes.
Therefore, we first propose a new model for the worst-case region-cut considering disconnected nodes (Node-Based) due to a region-failure as the major criteria for identifying the worst-case region-cut. In our proposed model, we may select a region with less number of link-cuts as the worst-case cut if it isolates a larger number of nodes. Moreover, in our proposed model mission-critical nodes are given more weight during the worst-case analysis process to reflect the importance of its service continuity.
3. Proposed model
The network model we consider here is composed of a base station, a sink node, and a set of distributed wireless sensor nodes. The base station can be inserted in any suitable place whether in the field or somewhere else. It is directly connected to the sink node through a wire or wireless link. The sink node is a wireless sensor with high capability in memory, processing, power, and wireless coverage. It works as an intermediate node between the base station and the other sensors. It receives commands from the base station and then conveys them to the deployed sensors. In addition, it collects data from the sensors and sends it to the base station. The other sensor nodes are categorized into mission-critical (MC) sensor nodes and regular sensor nodes. A mission-critical sensor node is a node that is responsible for sensing or reading mission-critical information such as a sensor node in the battle field. while the regular sensor node is any other node. These sensors which have limited capabilities in their battery-powers, memory, and processing are distributed all over the area of interest in such a way that any deployed node has at least one path to the sink node.
In the rest of this section we present the problem formulation of our proposed model in section 3.1. Then, in section 3.2 we introduce the routing process based on the above mentioned network model. Finally, we demonstrate the region failure analysis under single and dual region-failures in section 3.3.
3.1. Routing process
Nodes in a routing table are classified into three categories: 1) parent node, 2) sibling node and 3) child node. A parent node is a node in the transmission range of another sending node and having a hop count one less than the sending node. A sibling node is a node in the transmission range of another sending node and having the same hop count as the sending node. A child node is a node in the transmission range of another sending node and having a hop count one more than the sending node. After deploying sensor nodes into the network field, the routing tables of the underlying sensor nodes are established. To illustrate the process, a network is constructed in Fig. 3. The network has eight sensors: a sink node, two mission-critical sensors (
The routing process is started when the sink node broadcasts a setup packet to all nodes within its transmission range. The setup packet contains several parameters including the number of hops
3.2. Problem formulation
When considering circular cuts, we assume that a disaster results in a cut of radius
Equation 1 indicates that, the worst-case cut can be located by evaluating a weight function
Equation 2 evaluates the weight of a region cut centered at [x,y] by estimating the importance of three main factors: disconnected nodes, failed nodes, and link-cuts as described in Eq. 2.
The first term is the summation of the weights of all disconnected nodes due to the region-failure. Through the node weight
The second term represents the summation of all path weights of the failed nodes (all nodes within the region cut).
This weight function
In Eq.4, the path weight
Finally, if the failed node
The last term
On the other hand, if all links on the failed bridge are located on mission-path it is given the highest weight.
Finally, if not all of the links on the failed bridge are located on a mission-path, its weight is a percentage of the highest weight. This percentage can be evaluated by the ratio of the number of links carrying mission-critical information of the bridge to its total number of links as described in Equation 5
To further illustrate the evaluation of the worst-case region-failure, we provide the following example shown in Fig. 4. In this example compare two different region failures as shown in Fig. 4c and Fig. 4d. Here fater, we also provide the corresponding analytical calculations.
For the network shown in Fig. 4a, to find the worst-case region-failure we have to apply the routing process discussed earlier to configure the routing tables by the category (parent, sibling, child) of each neighbor. The result of routing phase for the given network topology is depicted in Fig. 4b. As described earlier in this section, the headed-arrow represents a child node toward the head and a parent node toward the tail while a line without heads represents a sibling relationship. Hereafter in the following example, we assume that the value of the constant c is equal to 5.
For the failure
Similarly, For the failure
For the calculation of the path weight
Finally, we calculate the bridge weight
Based on Eq. 1 of the proposed model, the region-failure with maximum weight will be chosen as the worst-case region-failure (
3.3. Region failure algorithms
In this section we introduce the main algorithms used to find out the worst-case region-failure under the single and dual region-failure scenarios in Section 3.3.1 and Section 3.3.2, respectively.
Hereafter, we present the main algorithms used in our model. The algorithm shown in Fig.5 finds all sensors within a region-failure. The algorithm depicted in Fig. 6 removes the failed sensors from the network topology (
The algorithm shown in Fig. 5 demonstrates how to find sensor nodes located within the region-failure. The input parameters to this algorithm are the network topology
The algorithm shown in Fig. 6 presents our strategy for removing a sensor node from the routing table (
The algorithm shown in Fig. 7 presents how to check if a sensor node
3.3.1. Single region-failure
The algorithm shown in Fig. 8 demonstrates how to estimate the number of disconnected nodes due to a single region-failure. The input parameters to this algorithm are the network topology
3.3.2. Dual region-failure
Under dual region-failure scenario, we propose the following algorithm shown in Fig. 9 to estimate the number of disconnected nodes within the given network topology.
The algorithm shown in Fig. 9 demonstrates our strategy to determine the number of disconnected nodes under dual region-failures scenario. The input parameters to this algorithm are the same as that of a single region failure shown in Fig. 8. In this algorithm, at the beginning, we follow similar steps to that used to find the number of disconnected nodes of a single region failure where we first generate a failure region with radius
Finally, Equation 1 is applied to estimate the worst case region-failure.
In this section, we present our simulation results. In our simulations we consider the network topology shown in Fig. 10 in which node 0 is the sink node. The failure information of different region failures generated during our simulations results are shown in Table 1 and Table 2, respectively.
|Region id||Failed Nodes IDs||No. of Failed links||No. of Disconnected Nodes|
|Region id||Failed Nodes’ IDs at Region 1||Failed Nodes IDs at Region 2|
|4||1, 4||2, 3|
|8||2, 3||5, 11|
|10||2, 3||11, 12|
|11||2, 3||12, 13|
|12||5, 11||7, 8|
|17||11, 12||7, 8|
|18||11, 12||31, 32|
Note that, due to the large number of region-failures generated, we present only region failures that lead to disconnecting more than two and eight nodes for the single and dual failure scenarios, respectively.
Hereafter, we investigate the location of the worst-case region-failure under Link-based, Node-based (without a mission critical node) and Node-based with a mission critical node in Fig. 12, Fig. 14 and Fig. 16, respectively. In the Node-based with a mission critical node, the node 28 is chosen as a Mission-Critical(MC) node.
The results shown in Fig. 11 show that, based on the traditional definition of the worst-case region cut, the failure region with id 5 is considered the worst-region cut as its failure leads to having the maximum number of failed links. The location of this failure-region is depicted in Fig 12. It is also notable that, according to Table 1 the failure of this region results in disconnecting 3 sensor nodes namely, node 33, 34, and 35 as depicted in Fig. 12.
The results shown in Fig. 13 clearly indicate that, in absence of mission-critical nodes within the network topology the proposed model is very clever to find out the worst-case region-failure. The worst-case region-failure is the region-failure that has the maximum impact on the network performance which is region 2 in this case as its failure results in disconnecting 8 sensor nodes, namely, 13, 14, 15, 16, 17, 18, 19 and 20. However, according to Fig. 11, the failure of this region leads to failure of 6 links only.
The results shown in Fig. 15 indicate clearly that, with the proposed model of a region-cut, introducing a mission-critical node into the network topology leads to a change in selecting the worst-case region cut which is region 4 as its failure results in disconnecting 5 sensor nodes, namely, 7, 8, 21, 23, and 28 as shown in Table 1. However, according to Fig. 11, the failure of this region leads to failure of 8 links.
Therefore, we claim that, using the failed links as the only criteria for defining the worst-case region cut is impractical as it ignores the case that the failure of some nodes may lead to failure of few links however its impact on the network is more severe due to disconnecting larger number of nodes. Moreover, it disregards the fact that some network nodes have higher priority than others.
Hereafter, we investigate the location of the worst-case dual region-failures without including a MC-node and with a MC-node in Fig. 17 and Fig. 18, respectively.
The locations of the worst-case dual region-failures shown in Fig. 17 indicate that, using the link-based approach (blue regions including nodes 11,12 and 31, 32) lead to cutting of 17 links and disconnecting 12 nodes. On the other hand, under the dual region failure scenario, using the proposed Node-based approach, the worst-case region-failure depicted in Fig. 17 (red regions including nodes 1,4 and 2) have only 8 link-cuts however, it results in a full disconnection of all the network nodes. This is due to the fact that, based on our approach, the worst-case region cuts are located near by the sink node and the failure of these nodes lead to isolating the sink node from the whole network. The results shown in Fig. 18 show that, by introducing the MC-node number 28, the worst-case dual region failure remains unchanged as the earlier case without MC-node. This is due to fact that, by introducing the MC-node, no further influence can affect the network as the maximum impact has been already happened by having a complete disconnected sensor network.
In this chapter, we introduced a new model for a worst-case cut (partition) due to failure regions. The proposed model takes into consideration the physical correlation among the locations of the network nodes and the possible priority of some nodes over the others. Based on the proposed model, We identified the location of a disaster that would have the maximum impact on a sample test network under single and dual region-failure scenario. Extensive Simulation results indicate that, using the number of failed links as the main criteria for defining the worst-case region cut, underestimates the impact of a region failure on the overall network performance.
Liotine M. 2003Mission-Critical Network Planning, Artech House Publishers, 158053516USA.
Markopoulou A. Iannaccone G. Bhattacharyya S. Chuah C. Diot C. 2004Characterization of failures in an IP backbone, IEEE INFOCOM 2004, 2307 2317
N., ( Azim A. Mohamed Mostafa. Kabir M. 2011Availability Study of M:N Automatic Protection Switching Scheme in WDM Networks, International Journal of High Speed Networks, 18 1 1 13IOS Press, Dec. 2011.
Lee K. Lee H. W. Modiano E. 2011Reliability in Layered NetworksWith Random Link Failures," IEEE/ACM Transactions onNetworking, 19 6 1835 1848Dec. 2011.
A.F.;( Kini S. Ramasubramanian S. Kvalbein A. Hansen A. 2010Fast Recovery From Dual Link or Single- Node Failures in IP Networks Using Tunneling," IEEE/ACM Transactions on Networking, 18 6 1988 1999Dec 2010.
Aly, ( Azim A. Mohamed Mostafa. El-semary M. 2012Vulnerability Assessment for Mission Critical Networks Against Region Failures: A Case Study, International Conference on Computing and Information Technology (ICCIT2012), 838 843March 2012.
Sen A. Shen B. Zhou L. Hao B. 2006Fault-tolerance in sensor networks: A new evaluation metric INFOCOM, 2006, 1 12
Sen A. Murthy S. Banerjee S. 2009Region-based connectivity: A new paradigm for design of fault-tolerant networks High Performance Switching and Routing 2009, 94 100Paris, France.
Sen A. Banerjee S. Ghosh P. Shirazipourazad S. 2009Impact of region-based faults on the connectivity of wireless networks. Allerton conference on communication control and computing 2009, Monticello, IL, 2009, 1430 1437
- 10. Jiajia Liu; Xiaohong Jiang; Nishiyama, H.; Kato, N.;, "Reliability Assessment for Wireless Mesh Networks Under Probabilistic Region Failure Model," Vehicular Technology, IEEE Transactions on, vol.60, no.5, pp.2253-2264, Jun 2011
MILCOM, Neumayer S. Zussman G. Cohen R. Modiano E. Assessing the. vulnerability of. geographically correlated. network failures. in Proc. M. I. L. C. O. 2008 1 6
INFOCOM, Neumayer S. Zussman G. Cohen R. Modiano E. Assessing the. vulnerability of. the fiber. infrastructure to. disasters in. Proc I. N. F. O. C. O. 2009 1566 1574
INFOCOM, Neumayer S. Modiano E. Network reliability. with geographically. correlated failures. in Proc. I. N. F. O. C. O. 2010 1658 1666
Hoboken, NJ: Wiley, Hayat M. M. Pezoa J. E. Dietz D. Dhakal S. Dynamic load. balancing for. robust distributed. computing in. the presence. of topological. impairments in. Handbook of. Science Technology for. Homeland Security. 2009
WAINA, Wu W. Moran B. Manton J. Zukerman M. Topology design. of undersea. cables considering. survivability under. major disasters. in Proc. W. A. I. N. 2009 1154 1159
GLOBECOM, Kimand K. Venkatasabramanian N. Assessing the. impact of. geograph-ically correlated. failures on. overlay-based data. dissemination in. Proc G. L. O. B. E. C. O. 2010 1 5
MILCOM, Agarwal P. Efrat A. Ganjugunte S. Hay D. Sankararaman S. Zussman G. Network vulnerability. to single. multiple probabilistic physical. attacks in. Proc M. I. L. C. O. 2010 1824 1829
Agarwal P. Efrat A. Ganjugunte S. Hay D. Sankararaman S. Zussman G. The resilience. of W. D. M. networks to. probabilistic geographical. failures I. N. F. O. C. O. M. 2011to be published.
Myounggyu Won & Stoleru, R.;, "Destination-Based Cut Detection in Wireless Sensor Networks," Embedded and Ubiquitous Computing (EUC),IFIP 9th International Conference on, vol., no., 55 62Oct. 2011
Barooah P. Chenji H. Stoleru R. Kalmar-Nagy T. 2012Cut Detection in Wireless Sensor Networks, IEEE Transactions on Parallel and Distributed Systems, 23 3 483 490
Turner D. Levchenko K. Snoeren A. C. Savage S. Computer S. I. G. C. O. M. M. Communcations California. fault lines. understanding the. causes impact of. network failures. Rev vol 315 326August 2010
Kini S. Ramasubramanian S. Kvalbein A. Hansen A. F. Fast recovery. from dual. link failures. in ip. networks in. Proceedings I. N. F. O. C. O. M. 1368 1376 2009
Choi H. Subramaniam S. ah H. Choi On. double-link failure. recovery in. W. D. M. optical networks. in in. Proceedings of. I. E. E. E. I. N. F. O. C. O. M. 2002 808 816