Localized Algorithm to Improve Connectivity and Topological Resilience of Multihop Wireless Networks
 Author: Kim TaeHoon, Tipper David, Krishnamurthy Prashant
 Organization: Kim TaeHoon; Tipper David; Krishnamurthy Prashant
 Publish: Journal of information and communication convergence engineering Volume 11, Issue2, p69~81, 30 June 2013

ABSTRACT
Maintaining connectivity is essential in multihop wireless networks since the network topology cannot be predetermined due to mobility and environmental effects. To maintain the connectivity, a critical point in the network topology should be identified where the critical point is the link or node that partitions the network when it fails. In this paper, we propose a new critical point identification algorithm and also present numerical results that compare the critical points of the network and
H hop subnetwork illustrating how effectively subnetwork information can detect the networkwide critical points. Then, we propose two localized topological control resilient schemes that can be applied to both global and localH hop subnetwork critical points to improve the network connectivity and the network resilience. Numerical studies to evaluate the proposed schemes under node and link failure network conditions show that our proposed resilient schemes increase the probability of the network being connected in variety of link and node failure conditions.

KEYWORD
Connectivity , Critical points , Multihop wireless networks , Resilience , Topology control

I. INTRODUCTION
Recent innovations in wireless technology have contributed to the rapid growth of wireless communication such as cellular and multihop wireless networks. Multihop wireless networks are considered to play an especially important role in communications due to their mobility and flexibility. Examples are wireless mesh networks being considered for the replacement of the backbone network [1], vehicular adhoc networks creating the connectivity between moving cars [2], wireless sensor networks monitoring and tracking the environment or the target remotely [3], and mobile adhoc networks that selforganize without infrastructure aid [4]. One considerably attractive network is the mobile adhoc network (MANET), which creates dynamical arbitrary topologies due to node mobility. Since multihop wireless networks create conectivity without a preexisting infrastructure, they have been considered in the deployment of many applications involved in difficult or dangerous tasks where the network infrastructure may not be available. For example, network infrastructure may not be available on the military battlefield, during disasters, or in a rescue environment. A MANET can also be used to provide extended connectivity for the coverage increments in a cellular network or wireless health monitoring system. Such a network requires cooperative nodes willing to act as a router because the wireless link is determined by the receiving signal strength, which is affected by node mobility and interference.
The topology changes with dynamical link changes and adaptive route establishment is required in a multihop wireless network. Therefore, connectivity is essential.
In a multihop wireless network, connectivity should be maintained to maintain communication because of dynamical topology changes. The network is known to be connected if all pairs of nodes have at least one path, while the network is not connected or partitioned if at least one pair of nodes does not have a path. Note that predetermined network design is not possible where a wireless link is susceptible to node mobility and interference. Therefore, maintaining connectivity in a multihop wireless network is challenging because of its unstructured topology, link and node failure, unreliable wireless channel properties, and limited battery life [14].
Here we provide an approach to improving the network connectivity to increase the reliability of a given multihop wireless network. For a given connected network, we identify the weak or critical points of the network and strengthen those critical points to improve the network survivability. In a multihop wireless network, a critical point can be a link, node, or combination of them that partitions the network topology into two or more due to its failure. A link whose failure partitions the network is defined as a critical link, and it is also called a bridge link in a network graph. A node that partitions the network when it fails is defined here as a critical node and is also known as an articulation node. In Fig. 1, for example, link DE and node G are critical points. The link DE is a critical link because the network partitions into two network clusters (i.e., ABCD and EFGHI). Similarly, when node G fails, the network is broken into two clusters, ABCDEF and HI.
In a traditional wired network, a backup route is utilized for the network survivability where the backup route can be link or node disjoint. The backup route allows the network to remain connected in any circumstance of link or node failure. For the network that is still connected from simultaneous failure of (
k 1) number of nodes, at leastk node disjoint routes for each pair of nodes are required. The network isk connected if and only if each pair off nodes has at leastk disjoint routes. In a multihop wireless network, ak connected network topology is also recommended to prevent a network partition from node or link failure. In order to achieve kconnectivity, many studies have investigated how kconnectivity can be inferred probabilistically or estimated in multihop wireless networks [4,5,79]. Most of these studies have focused on topological control by transmission power based on node density to accomplishk node connectivity for a homogeneous wireless network. Bettstetter [7] looked into this problem by identifying the behavior off a minimum node degree for the minimum transmission range. He identified the minimum node degree to maintaink connectivity of the network topology that uniformly distributed homogeneous nodes within a limited deployment area. the work was extended in [8]. Ling and Tian [8] develop a probabilistic upper and lower boundary of ak connected network for the transmission range and node density. Their study is based on the relationship between the node degree and probability of beingk connected [7]. Zhang and Hou [9] propose a transmission power control technique to maintain thek connectivity via a mathematical approach. They reduce the total transmission power to maintaink connectivity with ann assumption based on the relationship of minimum node degree andk connectivity in [7]. Recent studies [79] have looked atk connectivity using the node degree theoretically; however, it can be ensured in very high node density, which would generate a large interference and lower the throughput. Thus, those results are not adequate for sparse to mediumsized multihop wireless networks [10].In a
k connected network, each node has at leastk neighbor nodes (i.e., the minimum node degree ≥k ). However, a network in which the minimum node degree isk (i.e.,k neighbor nodes) does not guarantee ak connected network. Although the minimum node degree creates more connectivity, critical connectivity points that partition the network graph may still exist. Therefore, maintaining a minimum node degree ofk is a necessary butt not sufficient condition for ak connected network. Recently, a few papers have begun to look into this problem by defining and identifying the critical points of multihop wireless networks. The depth first search algorithm (DFS) is proposed in [11], and it only finds the critical links where the critical node is out of scope in that paper. For a better algorithm, Milic and Malek [12] propose the distributed breadth first search algorithm (dBFS) to detect the critical node and link utilizing distributed computation. In [13], critical node and link detection heuristics are proposed and they utilize local topology and location information. Their proposed algorithm is to find the critical points using a subnetwork graph created by eliminating incident links. If the subnetwork is not connected, then it is a critical point. As noted in [13], locally detected critical points may not be global critical points due to the existence of alternate routes outside the local topology information. In [14], we proposed a critical point identification algorithm and topology control resilient schemes. The critical point identification algorithm is based on results from algebraic graph theory, namely the algebraic connectivity of the network topology graph. The proposed algorithm requires global connectivity information, which can result in significant communication overhead.In this paper, we propose a novel algorithm for identification of critical points in a network. The approach is based on examining the connectivity between neighbor nodes without global connectivity information. In many cases, obtaining network topology may not be easy while obtaining limited subnetwork information may be relatively easy. Therefore, we also introduce how each node makes its decision on critical points based on
H hop neighbor node information. TheseH hop local critical points can be used to predict multiple critical points and global critical points. Using the critical nodes identified by our algorithm, we propose two techniques to improve the survivability of the network by removing theH hop local critical points. The basic idea is adjusting the transmission power of individual neighbor nodes around a critical point in order to create additional backup links between the nodes. The rest of the paper is organized as follows. In Section II, the proposed critical point detection algorithm is presented, along with implementations forH hop local critical points and multiple critical points. We also propose two resilient techniques to strengthen the network around critical points. Simulation results illustrating the effectiveness and tradeoffs of the resilience schemes are given in Section III. Lastly, we present our conclusions in Section IV.II. SYSTEM MODEL AND METHODS
In this section, we provide the notation used in the paper. Then, we present the proposed heuristic critical point identification algorithm.
> A. Network Model
We consider an arbitrary multihop wireless network of
N nodes. At any point in time, the topology can be represented by a graph G consisting of a set of vertices/nodesV , and edges/linksE . For simplicity, a homogeneous wireless network is assumed, where nodes have identical properties and inhabit a uniform environment (e.g., identical battery life, transmission power, antennas, radio propagation ranges, etc.). Table 1 lists our notation.> B. Critical Point Identification
In wired networks, the concept of identifying critical network nodes has recently been investigated from an infrastructure protection standpoint [15,16]. This literature focuses on which nodes will have the most impact on the network (in terms of connectivity or traffic loss) and a variety of heuristics have been proposed to identify the critical nodes, such as maximum degree nodes and maximum traffic nodes. In this section, some simple heuristics in identifying critical nodes are examined for their effectiveness; specifically, we consider the maximum node degree (Max ND), minimum node degree (Min ND), most heavily utilized (HU) nodes (i.e., nodes on the greatest number of shortest primary path routes), and nodes having the greatest backup path (GB) routes passing through them. The backup path routes are node disjoint with the shortest path primary route for each pair of nodes.
In evaluating the heuristics in the literature, we tested 100 connected random topologies that contained at least one critical node. The topologies were created by randomly placing 50 nodes each with 250 m of communication range in an area of 1,000 m × 1,000 m. Table 2 shows the average percentage of correct detection in the 100 topologies using the metrics Max ND, Min ND, HU, and GB. For each metric, three nodes, as selected by the metric, were evaluated for node criticality. For example, with Max ND, the three nodes with highest node degree were evaluated.
The results in Table 2 show that the HU heuristic has the highest critical node detection rate. However, its detection rate is still very low at 32% and one can infer that none of the heuristics are a reliable critical node identification method.
Here, we propose a new heuristic algorithm to identify topological critical points. Our proposed algorithm utilizes the network layer routing protocol to examine the alternate connectivity between neighbor nodes to identify critical points. The algorithm can be executed locally at a node as a selftest. The basic idea is to test a link or node for criticality by deleting all routes through the test point and seeing if alternate routes exist between neighbor nodes of the test point. If the test point is a link, alternate routes between the two end nodes are considered. Our proposed algorithm is shown below in Table 3.
The concept of the critical point identification algorithm is illustrated by example for the network of Fig. 2. Consider the test point node E, which has three neighbor nodes,
B_{e} = {D, F, H}. The combinations of neighbor node pairs is given by, (D, H), (D, F), and (F, H). One can see from the figure that the neighbor node pairs all have an alternate path that does not go through node E. Hence node E is not a critical node. In contrast, consider node M as the test point node. Node M has four neighbor nodes, N, L, O, and P.Note, that the neighbor node pairs (N, L) and (O, P) have an alternate path between them (i.e., NIJKL for N and L, OP for O and P). However, nodes (O, N), ((O, L), (P, N), and (P, L) do not have an alternate path; thus node M is a critical node.
The time complexity of the proposed algorithm is largely determined by computational time to determine the routes between neighbor nodes. In fact, the proposed algorithm takes the same time as the routing algorithms adopted in the network.
> C. Multiple Critical Points
Multiple critical points are a combination of nodes and/or links whose simultaneous failure partitions the network. For example, double critical nodes are a combination of two nodes/links whose failure causes the network to partition. Multiple critical points can be found by our proposed algorithm with modification of the test points. Consider the double critical node case, in which all combinations of two neighbor nodes, one neighbor node from one test point node and one neighbor node from another test point node, should be tested for alternate paths that do not include the test point nodes. If any combination of two neighbor nodes does nott have an alternate path, then the e test point nodes are double critical nodes. In determining double critical nodes, single critical nodes are excluded because the failure of any combination with a single critical node partitions the network. In Fig. 2, for example, the failure of any combination of nodes with node M partitions the network because node M is already a s single critical node. Node F and J are not single critical nodes and could be tested for double critical node status. the neighbor pairs of F and J, which are (A, H), (A, I), (A, K), (G, I), (G, H), (G, K), (E, I)), (E, H), and (E, K)), are considered for alternate paths with F and J removed. In this case, the node pairs (A, H), (G, I), (G, K), and (E, H) have alternate paths while other pairs off nodes do not. Thus, the combination of F and J form a double critical node pair.
> D. Local Hhop Critical Points
Our proposed critical point test algorithm can also be used for local
H hop critical point identification as in [12]. Specifically, one uses the algorithm with all of the possibleH hop paths through each neighbor node of the test point. These alternateH hop paths can be found at each node using receiving flooding messages that include visited node information. In the collection phase, all nodes send out ahello message adjusting the TTL value ofH . Each node receives thehello message from all nodes within anH hop. All intermediate nodes can easily insert their information by piggybacking on thehello message. Multiplehello messages may come from the same source where only onehello message arrives if only one path exists in anH hop subnetwork. For example in the network of Fig. 2, consideringH = 3, node E receive s one hello message from node F, D, H, G, J, A, C, and K because those nodes are less than 3 hops away from node E and any alternate path has more than 3 hops in Fig. 2. From those nodes that have alternate paths In theH hop subnetwork around the test point node, more than one hello message will arrive through an alternate path. In Fig. 2, node E will receive 2 hello messages from node I (i.e., IGFE and IJHE) and another 2 hello messages from node B (i.e., BAFE and BCDE). TheH hop connectivity of node E inH = 2 and 3 are shown in Fig. 3.Once a test point node collects
H hop subnetwork connectivity information, it can determine its criticality status by testing alternate connectivity between neighbor nodes. Alternate connectivity can be determined by examining the sets of intermediate nodes of all pairs of neighbor nodes. If at least one common node exists, two neighbor nodes have alternate connectivity besides the route through the test point node.Each nodes checks the connectivity between all pairs off nodes from its neighbor nodes set
(i.e.,B = {B B_{i} ;i = 1, 2, 3, …,d } whered is the node degree). If any neighbor node is not connected to other neighbor nodes in a direct or multihop fashion, the test point node is a critical node. Table 4 illustrates an algorithm to identify the localH hop critical node.Consider the critical point identification problem using Hhop local connectivity regarding node M or E in the network topology of Fig. 2. The 2hop and 3hop connectivity subnetworks of node M are in Fig. 3(a) and (b), respectively. Similarly, Fig. 3(c) and (d) show 2hop and 3hop subnetworks of node E, respectively. In order to apply the critical point test algorithm, each test point M or E should examine all hello messages with a TTL value of 2. For example, node M in Fig. 3(a) will receive
hello messages from I,K,P, and O via its neighbor node such as through INM, KLM, NM, LM, PM, PGM, GM, and GPM. From those messages (i.e., PM, PGM, GM, and GPM), node M can find that neighbor nodes G and P have alternate routes, but that there are one between (N,L), (N,O), (N,P), (L,O), and (L, P). Therefore, node M determines that it is a local critical point in a 2hop subnetwork around it. Similarly, Fig. 3(b) and (c) s show that node M and E are local critical points in 3hop and 2hop subnetworks, respectively. However, the 3hop subnetwork of node E indicates that node E is not a local critical point due to 3hop paths (i.e., B AFE, BCDE, IGFE, and IJHE); neighbor node D is connected to F via DCBAF, while F is connected to H via FGIJH. These results imply that false detection using anH hop subnetwork depends on the value ofH . In general, forany localized test, if only localH hop connectivity information is known,false positives on critical nodes or links will occur when the alternate routes are longer than theH hop limit. It is worth noting that hop count limits on routes are often used in networks for performance reasons (e.g., endtoend delay bounds).We also observe that the set of global critical nodes will be contained in the set of all local critic al nodes identified by the algorithm with
H hop information. Hence, unlike the algorithms in [13], the critical test point algorithm will have a 100% global critical point detection rate.> E. Local Resilience Schemes
In this section, we present two topology modification schemes to improve the resilience of the network by strengthening the connectivity around the critical node. The first scheme adds additional links to provide full connectivity around the critical node while the other scheme creates the minimum number of additional links in the
H hop subnetwork to make the node no longer critical. The first scheme needs the connectivity information between neighbor nodes, while the other manipulatesH hop connectivity information. An assumption for both cases is that nodes have enough power to establish the required new links and for now we ignore interference issues and maximum power limitations.1) Local Mesh Connectivity Scheme
The local mesh connectivity (LMC) scheme creates a fully connected 1hop local network around a critical node. An additional link between each pair of 1hop nodes can be established by adjusting transmission power. All 1hop nodes of the critical node check for direct link connectivity with all the rest of the 1hop nodes or neighbor nodes set
of the critical node (i.e.,B ={B B_{i} ;i =1,2,3,…,d 1} whered is node degree). It can be determined byhello flooding message dissemination from the critical point identification process or new 1hop messages. Then, it creates additional links to all other neighbor nodes, which have no direct link connectivity by increasing transmission power. The LMC algorithm is illustrated in Table 5.Adding additional links between 1hop nodes of the critical node creates an alternate path for each pair of 1hop nodes so that the network is still connected even when the critical node fails. For example, node M is a critical node off the 3hop subnetwork in Fig. 3(b). Node MM, whose node degree is 4 (i.e.,
d _{A}= 4), has 4 1 hop or neighbor nodes (i.e., _{M} == {L, N, O, P}).B In the LMC scheme, all pairs s of neighbor nodes are to be examined for direct link connectivity (i.e.,
A (O,P)=1,,A (L,N)=A (L,O)=A (L,P)=A ((N,O)=A (N,P)=0). Then, all nodes in all pairs of 1hop or neighbor node shaving no direct link connectivity (i.e., LLN, LO, LP, NO, and NP) increase the transmission power until direct link connectivity is created between each other. As a result, a fully connected network is established around the critical nodes as shown in Fig. 4(a), where the dotted line represents the establishment of addition a links by adjusting the transmission power of each neighbor node. Then, node M is not a critical node anymore since there still exists connectivity between all pairs of neighbor nodes when node M fails. The number of nodes that increase their transmission power is 4, and 5 new links are created a round the critical node M in this example.2) Local Least Connectivity Scheme
Similarly, the local least connectivity (LLC) scheme also creates additional links around a critical node. LLC finds fewer additional links than does LMC. Since LLC utilizes
H hop subnetwork connectivity information, unnecessary links would not be created. In anH hop subnetwork, one or more alternate routes not including acriticalnodemayyexisstbetween 1hop nodes of a critical node. Therefore, connected 1hop nodes do not require an additional link, which reduces a number of meaningless additional links created by LMC. LLC also finds the minimum cost links between 1hop nodes from each cluster, which also reduces the cost of creating an additional link. The LLC algorithm is illustrated in Table 6.The example of LLC is shown in Fig. 4(b). Node M is a critical node and the subnetwork breaks into two clusters when node M fails. 1hop nodes L and N are connected via an alternate route (i.e., LKJIN) and they are in the same cluster, while the other 1hop nodes O and P are directly connected. Then, LLC recognizes connectivity within the 3 hop subnetwork and creates one additional link between L and P to create an alternate route between the two clusters assuming the distance LP is shortest (i.e.,
dst (L,P) <dst (L,O),dst (N,O),dst (N,P)).3) Implementation of the Schemes
The critical node initiates LMC and 1hop neighbor nodes execute it. First, the critical node sends an initiation message including the set of 1hop neighbor nodes to all other 1hop nodes. As soon as this message arrives at each neighbor node, each 1hop neighbor node sends a message to all of the other 1hop neighbor nodes by setting the timetolive (TTL) value of 1 to check for direct link connectivity. Only directly connected 1hop nodes receive this message. Then, each 1hop neighbor node learns which other nodes with which it should create an additional link.
Unlike in LMC, the critical node initiates and executes the LLC scheme. LLC uses the
H hop subnetwork, which can be obtained from theH hop critical node identification process. The information about all possibleH hop paths through 1hop neighbor nodes from flooding messages informs the critical node of the set of visited nodes in all possibleH hop paths through neighbor nodes. The critical node can compare the visited node sets of each pair of neighbor nodes to determine the multihop connectivity. Thus, the critical node can identify connected and not connected 1hop neighbor nodes withinH hops. LLC then determines the minimum number of pairs of nodes needing an additional least cost link until each pair of clusters is connected. Note that the least cost links can be computed by acquisition of the node position utilizing global positioning system or localization techniques [13,17].III. RESULTS
In this section, we present results from sets of simulations. We first present the numerical study of
H hop effects on critical node detection. Then, we present numerical results on the effect of the topology control resilient scheme inH hops on network parameters. The improvement in resilience by proposing resilient schemes is also studied.> A. Critical Node Detection by Hhop
We use our proposed critical point identification algorithm to illustrate the effects of limited information (i.e.,
H hop) on critical node detection. At each node, it performs the critical point identification algorithm based on obtainedH hop subnetwork information. This was implemented in MATLAB. We randomly generate network topologies with different numbers of nodes (50, 75, 100) in a 1,500 m × 1,500 m network area. The nodes are randomly and independently distributed in the network area with the (x ,y ) coordinates determined according to two independent uniform [01500] random variables. All nodes are identical and have a 250 m transmission range. For each node density, we randomly generate topologies until 100 connected topologies are found. For each network topology, each node findsHhop connectivity inH = {2, 3, 4, 5} and executes the critical point identification algorithm to test for critical nodes. Fig. 5 shows the false detection rate of single and double critical node(s) usingH hop subnetwork critical node(s). The false detection rate is calculated by dividing the number of falsely detected critical nodes by the total number of detected nodes by theH hop critical point identification algorithm. As shown in Fig. 5, both the single and double false detection rates (i.e., FR1, FR2) are always lower with a largerH hop since the largerH hop subnetwork provides more accurate network connectivity information. The double critical nodes are a pair of nodes that partition the network when they fail at the same time. Similarly, FR also increases, as the network is denser. This is because limitedH hop connectivity information is less accurate in a denser network.Comparing FR1 and FR2, critical node detection by an
H hop subnetwork is more significant in double critical node identification. The falsely detected node for a signal critical node can be one of double critical nodes. For example, node F in Fig. 2 is detected as a critical node in a 2hop subnetwork, which is not a single critical node but one of double critical nodes (i.e., (F,E), (F,H), and (F,J)). Thus, FR2 is always lower than FR1.To illustrate the effect on double critical node detection, we introduce the protection rate of double critical nodes (PR2): the ratio of the number of double critical nodes in which at least one node is detected by an
H hop critical node to the total number of critical nodes. If either one of the double critical nodes is strengthened by the resilient scheme, the network remains connected at simultaneous failures of double critical nodes. Fig. 6 shows PR2 and FR2 in differentH hop values of 2, 3, and 4. Given that they have a lowerH value for theH hop, both PR2 and FR2 increase overall network density. FR2 does not show a difference byH hop in a sparse network (i.e., FR2 = 0.0187, 0.00412, 0 atH = 2, 3, 4, respectively). FR2 increases dramatically with network density at a lowerH value (i.e., FR2 = 0.0187, 0.1265, 0.4141 in 50, 75, 100 nodes density atH = 2). On the other hand, PR2 decreases, as the network is denser at allH values.The value of the
H hop local critical node approach can be determined by the difference between PR2 and FR2. The difference between PR2 and FR2 is more significant in sparse networks and less significant in denser networks (i.e., PR2 ？ FR2 = 0.7592, 0.5869, 0.1953 in 50, 75, 100 nodes network atH = 2).> B. Local Resilient Schemes in Hhop Subnetwork
We evaluate the effectiveness of our critical node management schemes using simulation. In this study, we implement our proposed resilient schemes for
H hop local critical nodes and global critical nodes and then compare them. We generate random topologies with different numbers of nodes (i.e., 50, 75, and 100) in a network area of 1,500 m × 1,500 m. The nodes are independently distributed according to a uniform [01500] random variable in the network area. For each network density, we generate 50 connected random topologies, where every pair of nodes has at least one route (i.e., they arek = 1 or more connected) and at least one critical node in the topology. A free space propagation model is used and a uniform disk of the transmission range is created in the simulation. We assume all nodes are identical and have a capability of adjusting transmission power with an initial power with a transmission range of 250 m. We use MATLAB to implement our proposed critical node management schemes (LMC, LLC) atH = 2, 3, 4. First, we examine the effectiveness of the proposed schemes in providingk = 2 connectivity for the entire network. It makes 100% of 2 conneted networks for both schemes in 50, 75, and 100 nodes.Although our proposed schemes can effectively provide a 2connected network, there are some tradeoffs between LMC and LLC. We consider the average node degree and average number of added links as the tradeoffs, and they are shown in Figs. 7 and 8, respectively. The average node degree provides a metric of connectivity and interference. In the sparse network case (i.e., 50node network), LMC has a higher average node degree (i.e., LLC 4.45, LMC 5.63). When the network is denser, the average node degrees of the proposed resilient schemes are closer. A different value for H in LLC does not make much difference in the average node degrees in all network density while LMC makes a difference. LLC on a global critical node shows a lesser average node degree than that on
H hop local critical nodes in 50, 75, and 100node networks for all values ofH (i.e., 5.63 global, 5.84H =4, 6.04H =3, 6.35H =2, 6.35 at 50 nodes).The average number of added links can be related to the average energy consumption of the network since adding additional links is achieved by increasing the transmission power of the node. As shown in Fig. 8, LMC requires significantly more energy than LLC for the 50node network (i.e., 60.36 at
H = 2) case since it requires a larger number of additional links. As network density increases, LMC still creates more additional links than LLC, but it is not as significantly large as it is in a 50node network. A lowerH hop requires a larger number of added links for both LMC and LLC as expected. As the network density increases, the number of links decreases significantly except for LMC withH = 2 (i.e., 60.36, 62.64, 53.32 at 50, 75, 100 nodes, respectively).To further examine the resilience of the proposed schemes, we randomly fail nodes and links in the network and determine the probability the network remains connected (i.e.,
P (Connected )). Each node fails according to probabilityP_{nf} , and each link with link failure probabilityP_{lf} . The probability of node failure was set to result in an average of one node failure for each network density (i.e.,P_{nf} = 1/N ). The link failure rate was varied (P_{lf} = 0.00, 0.05, 0.1, 0.15, 0.2), whereP_{lf} = 0.1 means that on average 100 ×P_{lf} = 10% of the links fail in the network. For each of the 50 topologies, we randomly generate 100 experiments for eachP_{nf} andP_{lf} and determine the probability the network is connected.The probability of the network being connected on the estimate of LMC is computed and plotted for 50, 75, and 100node networks, as shown in Fig. 9(a)？(c), respectively. As one would expect, the lower
H hop improvesP (Connected ) the most. For example, for the 50 node network case, the LMC scheme provides close to 95% chance the network is connected even withP_{nf} = 0.02 andP_{lf} = 0.1 atH = 2. As the network density increases,P (Connected ) increases.For example, for a 100node network with link failure of 0.2,
P (Connected ) becomes 0.8348 by LMC on global critical nodes while LMC onH = 2 improves it up to 0.8838 and onH = 4 improves it to 0.8444 for the minimum improvement.The probability,
P (Connected ), of LLC for 50, 75, and 100node networks is shown in Fig. 10(a)？(c), respectively. As in LMC, LLC improvesP (Connected ) the most when implemented for a lower value of H (i.e., 0.8642H = 2, 0.8554H = 3, 0.8410H = 4, 0.81 on global) withP_{lf} = 0.1 in a 50node network. Similarly, LLC also provides a higherP (Connected ) in a denser network. For example, for a 100 node network with a link failure of 0.2,P (Connected ) becomes 0.7792 by LMC on global critical nodes while LFC onH = 2 improves it up to 0.8136 and onH = 4 improves it to 0.7942 for the minimum improvement.When LLC is compared with LMC, LMC improves the probability of network connectivity more than LLC at any network density. Another observation is that
P (Connected ) decreases faster when implemented on global critical nodes as the network is experiencing more severe link failure. For example, in the 50node network case, when the link failure rate increases from 0 to 0.2,P (Connected ) decreases from 0.9922 to 0.6734 with global critical nodes while it decreases from 0.9968 to 0.814 with 2hop local critical nodes (atH = 4, it shows the largest decrease inP (Connected ) amongH hop local critical nodes ).Figs. 11 and 12 illustrate
P (Connected ) of LMC and LLC with higher probability of node failure at each given link failure (i.e.,P_{lf} = 0.00, 0.05, 0.1, 0.15, 0.2). In this set of studies, we used the probability of node failure, set to result in an average of two node failures for each network density (i.e.,P_{nf} = 2/N ). In more severe node failures, the results are similar to the results from the previous case (i.e.,P_{nf} = 1/N ). LMC has a greater probability of providing a 2connected network than LLC.P (Connected ) increases as the network is denser in both schemes. Similarly, the lowerH hop has a greaterP (Connected ) in both schemes. Note that theP (Connected ) by LLC gets significantly lower at severe node and link failure as the network is sparser (i.e., 0.4124 on global for the minimum, 0.5004 atH = 2 for the maximum).Note that while the LMC scheme has a higher
P (Connected ) under node and link failure, it consumes more energy. Thus it will be the best scheme in a sparse network if the network has unlimited or rechargeable power sources. Otherwise, either the LLC scheme is better because they create significantly less node interference and require less energy consumption than LMC. Both schemes on lowerH hop provide better connectivity but also create more interference and consume more energy. However, LMC will outperform in a sparse network with severe node and link failure conditions.IV. CONCLUSIONS
We have proposed a new algorithm to identify the critical connectivity points of a multihop wireless network topology utilizing the connectivity between local neighbor nodes. Unlike the existing algorithms, the proposed technique can be tested locally at the node and has a simple implementation using only local information at the expense of false positives in the results. Local subnetwork critical nodes can be used to predict multiple failure critical points and can reduce the number of broadcasting messages by limiting the TTL value. We have also proposed two resilient schemes that strengthen the critical nodes by utilizing transmission power control. Our proposed schemes can be applied to global and local
H hop critical nodes and create a 2connectivity network topology. The simulation results in a variety of node and link failure scenarios indicate that the proposed resilient schemes on localH hop subnetwork critical nodes outperform those schemes on global critical nodes in all network densities where a lowerH hop provides better connectivity. Furthermore, the LLC scheme on anH hop local critical node is considered the best approach for improving the network resilience while minimizing energy and interference. Future research will focus on the prediction of critical nodes in anH hop local subnetwork approach. Since the network topology may change in time due to node mobility and interference, one should predict the critical points in advance.

[Fig. 1.] Example of critical connectivity points in a 9node network.

[Table 1.] Notation used

[Table 2.] Percentage (%) of correct critical node detection

[Table 3.] Critical point identification algorithm

[Fig. 2.] A 16node network.

[Fig. 3.] Hhop subnetwork of node E when H = 2, 3. (a) Two hop local network at node M, (b) 3 hop local network at node M, (c) 2 hop local network at node E, and (d) 3 hop local network at node E.

[Table 4.] Hhop critical node identification algorithm

[Table 5.] Local mesh connectivity (LMC) algorithm

[Fig. 4.] Local mesh connectivity (LMC) and local least connectivity (LLC) on critical node M. A red dotted line indicates additional links created by the scheme. (a) LMC on node M and (b) LLC on node M.

[Table 6.] Local least connectivity (LLC) algorithm

[Fig. 5.] Single and double critical node false detection rate using Hhop subnetworks.

[Fig. 6.] Single and double critical node protection rate (PR) and false detection rate (FR) using Hhop subnetworks.

[Fig. 7.] Average node degree at k = 2. Average nodes degree by (a) local mesh connectivity (LMC) and (b) local least connectivity (LLC).

[Fig. 8.] Average number of adding links in Hhop subnetwork when H = 2, 3 by (a) local mesh connectivity (LMC) and (b) local least connectivity (LLC).

[Fig. 9.] Probability of the network being connected by LMC at 1 node failure and several link failure rates in H = 2, 3. (a) 50node, (b) 75node, and (c) 100node network.

[Fig. 10.] Probability of the network being connected by LLC at 1 node failure and several link failure rates in H = 2, 3. (a) 50node, (b) 75node, and (c) 100node network.

[Fig. 11.] Probability of the network being connected by LMC at 2 node failure and several link failure rates in H = 2, 3. (a) 50node, (b) 75node, and (c) 100node network.

[Fig. 12.] Probability of the network being connected by LLC at 2 node failure and several link failure rates in H = 2, 3. (a) 50node, (b) 75node, and (c) 100node network.