# Construction of Quality Virtual Backbones with Link Fault Tolerance in Wireless Sensor Networks

Authors: Xinyu Liang; Jiarong Liang; Weiguang Zhang
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

Wireless sensor networks (WSNs) are extensively utilized in various circumstances. For applications, the construction of the virtual backbones (VBs) of WSNs has attracted considerable attention in this field. Generally, a homogeneous WSN is formulated as a unit disk graph (UDG), and the VB of the corresponding WSN is modeled as a connected dominating set (CDS) in the UDG. In certain applications, communication between sensors in a network may fail for various reasons, such as sensor movement, signal interference, and the appearance of obstacles. Consequently, a CDS in a UDG should possess fault tolerance on the edges. In this paper, we introduce a new concept called the 2 edge-connected 2 edge-dominating set (2,2-ECDS); then, we design an approximation algorithm for computing 2,2-ECDSs in UDGs, the performance ratio of which is 30.51. By means of simulations, we compare our algorithm and existing algorithms in terms of the CDS size, running time, success rate, and network lifetime. The simulation results indicate that our algorithm exhibits better performance and is more suitable for constructing a VB with edge fault tolerance in a WSN.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) are multihop self-organizing network systems that contain numerous sensor nodes. Because no predefined infrastructure is required, WSNs can be flexibly deployed in various circumstances, such as the Internet of Things, ocean monitoring, and traffic surveillance [1–5]. However, the wireless sensors in WSNs are usually powered by batteries, which means that minimizing sensor energy consumption is a critical challenge [6, 7]. Generally, the energy of sensor nodes in a WSN is mainly consumed in the signal transmission process. Specifically, when a signal is transmitted from a source node to a target node, the required energy increases exponentially with increasing distance [8]. Thus, most WSNs use a multihop communication strategy rather than long-range direct communication to enhance the energy efficiency of the sensor nodes [9–14].In multihop communication, a message from a source node to a target node may be retransmitted many times, which can result in substantial wireless signal interference and collision and waste a large amount of energy. Hence, a high-quality routing path for information transmission is critical. To address this issue in WSN communication, the concept of the VB, inspired by the backbone of wired networks, is supposed to reduce information overload and improve the efficiency and lifespan of the network [1].In theory, a VB is a subset of sensor nodes in a WSN that meets the following requirements [15]. First, each node in a WSN is adjacent to a node in this subset. Second, any two nodes in the subset have a routing path between them in the VB. To investigate VBs in homogeneous WSNs, the WSN is typically modeled as a UDG G=V,E, where a vertex in V is a simplification of a sensor node and an edge in E stands for the message transmission between two sensors; a VB of a WSN is modeled as a CDS in the corresponding graph G. In the research of WSNs, since a smaller VB entails less routing overhead and wireless signal collision, the size of the VB is an important index in measuring the quality of the VB. Thus, it is natural to find a minimum CDS (MCDS) of G when constructing a CDS. However, Garey and Johnson [16] have proven that calculating MCDSs is NP-hard. Consequently, many efforts have been made to obtain an approximate solution to this problem by designing approximation algorithms.In practical applications, in a WSN, a few sensors and the links between them may be out of operation for various reasons, such as sensor movement, signal interference, and the appearance of obstacles. Thus, the VB for a WSN should be fault tolerant such that it continues to work when some nodes and links fail. Fortunately, in recent years, progress has been made in designing node fault-tolerant VBs for WSNs. In fact, in 2005, Dai and Wu [17] proposed a special CDS, the k‐connected k‐dominating set, for a node fault-tolerant VB in a WSN against node failure. Later, Thai et al. [18] extended this concept to the famous k‐connected m‐dominating set (k,m‐CDS), where 1≤k≤m. Since the construction of the minimum 1,1‐CDS is NP-hard, the construction of the minimum k,m‐CDS is also NP-hard. As a result, numerous researchers have focused on developing approximation algorithms to calculate a k,m‐CDS with a worst-case performance guarantee for any given pair of integers k and m (1≤k≤m) [19–27].Note that the above literature considered only the problem of a fault-tolerant VB against node failure and neglected the impact of edge failure. In practical applications, edge failure may impact the operation of a VB in the considered WSN; in other words, edge failure may lead to failure of the VB even if all nodes in the VB are fault-free. For example, in a WSN with 9 nodes, which is modeled by the UDG shown in Figure1, the VB consists of nodes u1, u3, and u7. When edge u3,u5 fails, some aspects of the VB, such as domination, will fail, even though each node is fault-free. In practice, edge failure in a WSN may be inevitable due to various factors, such as node movement, signal interference, and obstacles. For example, in the WSN shown in Figure 1, when node u1 is moved to a position outside of the transmission range of u3 (see Figure 1(b)), edge u1,u3 fails, which results in subset u1,u3,u7 no longer being a VB.Figure 1
An example scenario of a WSN with 9 nodes.
(a)
u1,u3,u7 is not a CDS when edge u3,u5 fails(b)
Edgeu1,u3 fails when node u1 moves outside of the transmission range of u3, even though all nodes are fault-freeNote that in a UDG, if a CDS is a node fault-tolerant CDS, such ask,m-CDS with m≥k≥2, it must be an edge fault-tolerant CDS. Formally, in a UDG G=V,E, a CDS S is a node fault-tolerant CDS if for any v∈V, S−v is still a CDS in G−v. Similarly, in a UDG G=V,E, a CDS S is an edge fault-tolerant CDS if for any e∈E, S is still a CDS in G−e. Compared to that of constructing an edge fault-tolerant CDS in a UDG, the cost of constructing a node fault-tolerant CDS may be higher. On the other hand, in some UDGs, there may not exist a node fault-tolerant CDS, while there is an edge fault-tolerant CDS. For example, in the UDG G shown in Figure 2, there are no node fault-tolerant CDSs; however, the CDS u1,u2,u3,u5,u6 is an edge fault-tolerant CDS because when any edge in G fails, u1,u2,u3,u5,u6 is still a CDS. Hence, it is necessary to explore how to construct an edge fault-tolerant CDS in a UDG. Unfortunately, few efforts have been made in this direction in the existing literature.Figure 2
An example scenario of a WSN where no2,2-CDS exists but a 2,2-ECDS exists.In this paper, we investigate the construction of an edge fault-tolerant CDS in a UDG. Specifically, this paper introduces a new concept called the 2 edge-connected 2 edge-dominating set (in short,2,2-ECDS) and develops a constant factor approximation algorithm to calculate a 2,2-ECDS in a given UDG.The main work of our paper is described as follows:(i)
To obtain an edge fault-tolerant VB in a WSN, we introduce a new concept called the2,2-ECDS(ii)
A centralized approximation algorithm is designed for the construction of a2,2-ECDS in a given UDG, whose performance ratio is proven to be 30.51(iii)
The designed algorithms are supported by strict theoretical analysis and simulation experiments. In the theoretical analysis, we conduct strict mathematical proof of the correctness of these algorithms. By means of simulation experiments, we illustrate that the CDSs output by our algorithms outperforms those obtained with the state-of-the-art algorithms presented in [25, 26]The rest of this paper is organized as follows. In Section2, related research is introduced. In Section 3, an introduction of the definitions, terms, and related results used in the remaining sections is provided. Section 4 presents an approximation algorithm for constructing a 2,2-ECDS. Section 5 reports simulation results on the comparison between our algorithm and other related algorithms. Finally, in Section 6, we summarize our work and introduce potential directions for future work.


## 2. Related Work

A WSN can be abstracted as a graphG=V,E; correspondingly, the VB of the WSN can be abstracted as a CDS of G. In recent years, numerous efforts have been made to construct MCDSs. In a general graph, Guha and Khuller [28] proved that for the MCDS problem, it is impossible to obtain a polynomial time approximation algorithm with a performance ratio ρlnn for any 0<ρ<1 unless NP⊆DTIMEnOloglogn, where n is the number of nodes in the graph. They introduced a 2HΔ+1-approximation algorithm and a HΔ+2-approximation algorithm based on a greedy strategy, where Δ is the maximum degree of nodes in the corresponding network graph and H is the harmonic function. In [29], Du et al. improved this result and presented an 1+εlnδ−1-approximation algorithm ε>0, which is the best result in general graphs thus far.For UDGs, the MCDS problem has been widely investigated, and a variety of results have been obtained [26, 30–39], in which different approximation algorithms have been proposed for this problem. These algorithms usually consist of two phases: (1) a maximal independent set (MIS), which serves as a dominating set in a given UDG, is determined, and (2) some nodes are selected into the MIS such that it becomes connected. Researchers analyzed the performance ratio of the resulting CDS from two aspects: the size of the MIS obtained in the first phase and the number of newly added nodes in the second phase. For the MIS size, in [33], Wan et al. demonstrated that the upper bound of an MIS is 4∗opt+1 in a UDG, where opt represents the size of the MCDS in the UDG. Later, this upper bound was improved by [30, 34–37], where [30] obtained an upper bound of 3.399∗opt+4.874, which is the best result thus far. For the size of the newly added nodes, in [33], Wan et al. showed that the size bound generated by their algorithms in the second phase is ∣I∣−1, where ∣I∣ is the MIS obtained in the first phase. This result was used by [34, 35] to evaluate the performance ratios of their algorithms. In [31, 38], the Steiner tree strategy was used to design approximation algorithms for the MCDS problem, and the size of the newly added nodes in the second phrase was no more than 1+ln5CT∗, where CT∗ is the number of Steiner nodes in the minimum Steiner tree containing the MIS obtained in the first phase. To our knowledge, this is the best result thus far.In research on the construction of node fault-tolerant VBs, Dai and Wu [17] introduced a concept called the k,k-CDS. For a k,k-CDS in a given G=V,E, after k−1 nodes are deleted from G, the set of residual nodes in the k,k-CDS is still a CDS for the subgraph induced by the residual nodes of G. They presented three algorithms to compute a k,k-CDS for a given UDG. Unfortunately, they did not present the performance ratios of these three algorithms. In [18], Thai et al. extended this concept to the famous k-connected m-dominating set, where 1≤k≤m. In their paper, a centralized approximation algorithm was provided for the minimum k,m-CDS problem. Since then, numerous constant factor approximation algorithms for the construction of k,m-CDSs have been proposed. In [40], Wu et al. presented a distributed algorithm with a performance ratio of 5/mk2+1m+42. In [25], Shang et al. proposed another approximation algorithm, whose performance ratio is 5+25/m2≤m≤5 or 11 m>5, for constructing a 2,m-CDS. In [26], Shi et al. noted mistakes in the proof process of the performance ratio of the algorithm in [25] and found that the ratio should be 15+15/m2≤m≤5 or 21 m>5 rather than 5+25/m2≤m≤5 or 11 m>5. Moreover, Shi et al. [26] used a submodular function and greedy strategy to design a new approximation algorithm with a performance ratio of α+21+lnα, where α is the performance ratio of the algorithm for constructing the 1,m-CDS. In 2010, Kim et al. [23] introduced a 15r‐ approximation algorithm for computing a 3,m-CDS in a UDG, where r is the performance ratio of the algorithm for the 2,m-CDS (m≥2) problem. In [41], Liu et al. used Tutte decomposition to design a 5r‐approximation algorithm to calculate a 3,m-CDS (m≥3) in a UDG, where r is the performance ratio of the algorithms for the 2,m-CDS (m≥2) problem. When m=3, they noted that the performance ratio of their algorithm is 62.30, which is better than the 580/3 performance ratio achieved by [23]. In [8], Wang et al. introduced the concepts of “good points” and “bad points” and proposed an algorithm to calculate a k,m-CDS in a given UDG, where k=3,4 and m≥k. The main idea of their algorithm is to first obtain a k−1,m-CDS by means of an existing algorithm and then convert all degree-k−1 bad points in the k−1,m-CDS into good points by adding “H-paths.” Second, they construct a simplified auxiliary graph for the CDS obtained in each iteration. Finally, the k,m-CDS is constructed by means of the simplified auxiliary graph. They achieved a performance ratio of 5β2 for the 3,m-CDS problem (7β3 for the 4,m-CDS problem), where βk is the performance ratio of the algorithm proposed in [26] for k,m-CDS problem k=2,3.In recent years, research on link failure in WSN communication has attracted considerable attention. In [42], Zonouz et al. proposed a model, called time-dependent lognormal shadowing radio propagation, to analyze and estimate the reliability of a wireless link under consideration of the power consumption in different modes and wireless channel conditions. In [43], Fu et al. noted that the capacity of links is significantly limited in most WSNs. They believed that when the load of a few links in the network exceeds their capacity, link failures may occur, which may cause paralysis of the global network. Later, in [44], Draz et al. provided a link failure detection algorithm to proactively diagnose faulty links in a WSN and introduced a recovery mechanism against link failures. In [45], Xu et al. used independent Bernoulli processes to describe link failures in a WSN and employed a Kalman-consensus filter and CI algorithm to estimate these link failures through a hierarchical fusion method. In [46], to improve the robustness of VBs, Liang et al. proposed a new concept, robust VB, and corresponding algorithms against link failures in WSNs with unstable transmission ranges. In their work, a more robust VB, named the d-robust CDS, is obtained by their algorithms, and based on this VB, the communication in the corresponding WSN does not fail when Re≥1−d∗R, where Re is the effective transmission range of the nodes and R is the initial transmission range of the nodes.As described above, link failures can impact WSN communications. A natural idea is to investigate VBs with link fault tolerance, namely, the problem of edge fault-tolerant VBs against link failure. Unfortunately, research on the construction of edge fault-tolerant VBs in WSNs remains scarce. In this paper, we consider this problem and introduce the concept of the2,2-ECDS for UDG, which is a kind of edge fault-tolerant VB in the corresponding homogeneous WSN, and propose an approximation algorithm for the construction problem of the 2,2-ECDS.


## 3. Preliminaries

For convenience, some concepts, notations, and knowledge related to graph theory are now introduced. In this paper, all considered graphs are connected unless otherwise specified.


### 3.1. System Model and Problem Definition

In this paper, we adopt the following assumptions: the sensors in the considered WSN are randomly placed in a given area and immobile thereafter; each sensor has the same transmission radius and initial energy; two sensors can communicate with each other if and only if one of them is within the transmission range of the other; and in the considered WSN, each link between sensors is bidirectional. We abstract each sensor of the WSN as a node of a graph and each communication link between two sensors as an edge between the corresponding nodes. Thus, a WSN is modeled as an undirected connected graphG=V,E.The problem that we address in this paper is called theminimum2,2-ECDS problem. For the sake of understanding the minimum 2,2-ECDS problem, we first introduce some necessary concepts related to this problem.Definition 1 (2 edge-connected graph).
A graphG=V,E is called a 2 edge-connected graph if for any e∈E, GE−e is connected, where GE−e is the spanning subgraph induced by edge set E−e. In particular, a graph with a single node is defined as a 2 edge-connected graph.Definition 2 (2 edge-dominating set).
In a given graphG=V,E, a subset D⊆V is called a 2 edge-dominating set if for each node v∈V−D, ∣ED,v∣≥2.
In a given UDGG=V,E, let u∈V and D⊆V. If ∣ED,u∣≥2, then we say that u is 2 edge-dominated by D.Definition 3 (2 edge-connected 2 edge-dominating set).
In a given UDGG=V,E, a CDS D⊆V is a 2,2-ECDS if the following conditions hold:
(1)
D is a 2 edge-dominating set of G(2)
GD is a 2 edge-connected graphA2,2-ECDS with the minimum cardinality is called a minimum 2,2-ECDS.Definition 4 (minimum2,2-ECDS problem).
For a given graphG=V,E, the minimum 2,2-ECDS problem is the problem of constructing a minimum 2,2-ECDS for G.
Note that because the MCDS problem for a graph is NP-hard, the minimum2,2-ECDS problem for a graph is also NP-hard. In this paper, we will design an approximation algorithm for the minimum 2,2-ECDS problem.


### 3.2. Notations

In this subsection, we useG=V,E to denote a UDG.
(i)
GE∗: the spanning subgraph induced by E∗⊆E, namely, GE∗=V,E∗(ii)
GS: the subgraph induced by S⊆V(iii)
Ev: the edge subset, where each edge is incident to v∈V, namely, Ev=e∈Evisoneofe’sendpoints(iv)
ES,v: ES,v=e∈EoneendpointofeisvandanotherendpointofeisinS, where v∈V−S(v)
Nu: the set of neighbor nodes of u∈V(vi)
Nu: Nu=Nu∪u(vii)
IDu: the ID of node u(viii)
eu: the energy of node u(ix)
EG: the set consisting of all edges of G(x)
VG: the set consisting of all nodes of G


### 3.3. Definitions

Definition 5 (weight functionWx1,x2,x3).
Given two 3-tuple variablesx1i,x2i,x3i and x1j,x2j,x3j, for a weight function W:x1,x2,x3↦R, Wx1i,x2i,x3i>Wx1j,x2j,x3j if and only if at least one of the following conditions is true:
(i)
x1i>x1j(ii)
x1i=x1j and x2i>x2j(iii)
x1i=x1j and x2i=x2j and x3i<x3jDefinition 6 (bridge).
In a given UDGG=V,E, e∗∈E is called a bridge of G if GE−e∗ is disconnected.
According to Definitions1 and 6, a given UDG G=V,E is a 2 edge-connected graph if and only if each edge e∈E is not a bridge of G.Definition 7 (edge-disjoint).
In a given UDGG=V,E, let P1 and P2 be two different paths. Then, P1 and P2 are called edge-disjoint if EP1∩EP2=∅.Definition 8 (simple cycle).
In a given UDGG=V,E, let P=x1↔x2↔⋯↔xk be a path of G. The path P is called a simple cycle in G if x1=xk and xi≠xji,j=2,3,⋯,k−1,i≠j.
According to Whitney’s theorem [47], the proposition that for a given G=V,E, e∗ is a bridge of G is equal to any one of the following propositions.
(1)
InG, ∃x,y∈V such that all paths between x and y contain edge e∗(2)
G has no simple cycle containing e∗Definition 9 (2E-block).
In a given UDGG=V,E, let S⊆V. GS is a 2E-block of G if one of the following conditions holds:
(1)
S⊂V consists of a single node, and for any nonempty subset S′⊆V−S, GS∪S′ is not 2 edge-connected(2)
S⊂V consists of at least two nodes; GS is a 2 edge-connected graph; and for any nonempty subset S′⊆V−S, GS∪S′ is not 2 edge-connected(3)
S=V and G is a 2 edge-connected graphRemark 10.
According to the definitions of the2E-block and 2 edge-connected graphs, for a given graph UDG G=V,E and a set S⊆V, we have the following conclusions:
(1)
IfGS is a 2E-block of G, then GS is 2 edge-connected blocks(2)
GS is the unique 2E-block of GS if and only if GS is 2 edge-connectedDefinition 11 (LkSpath).
In a given UDGG=V,E, let S⊆V and x,y∈S. A path from x to y with k+2 nodes is called a LkS path if its k inner nodes belong to V−S.Lemma 12.
In a given UDGG=V,E, for any u,v∈V, there exist two paths that are edge-disjoint between u and v if and only if G is a 2 edge-connected graph.According to Definition7 and Whitney’s theorem, the proof of Lemma 12 is easy to obtain.


## 3.1. System Model and Problem Definition

In this paper, we adopt the following assumptions: the sensors in the considered WSN are randomly placed in a given area and immobile thereafter; each sensor has the same transmission radius and initial energy; two sensors can communicate with each other if and only if one of them is within the transmission range of the other; and in the considered WSN, each link between sensors is bidirectional. We abstract each sensor of the WSN as a node of a graph and each communication link between two sensors as an edge between the corresponding nodes. Thus, a WSN is modeled as an undirected connected graphG=V,E.The problem that we address in this paper is called theminimum2,2-ECDS problem. For the sake of understanding the minimum 2,2-ECDS problem, we first introduce some necessary concepts related to this problem.Definition 1 (2 edge-connected graph).
A graphG=V,E is called a 2 edge-connected graph if for any e∈E, GE−e is connected, where GE−e is the spanning subgraph induced by edge set E−e. In particular, a graph with a single node is defined as a 2 edge-connected graph.Definition 2 (2 edge-dominating set).
In a given graphG=V,E, a subset D⊆V is called a 2 edge-dominating set if for each node v∈V−D, ∣ED,v∣≥2.
In a given UDGG=V,E, let u∈V and D⊆V. If ∣ED,u∣≥2, then we say that u is 2 edge-dominated by D.Definition 3 (2 edge-connected 2 edge-dominating set).
In a given UDGG=V,E, a CDS D⊆V is a 2,2-ECDS if the following conditions hold:
(1)
D is a 2 edge-dominating set of G(2)
GD is a 2 edge-connected graphA2,2-ECDS with the minimum cardinality is called a minimum 2,2-ECDS.Definition 4 (minimum2,2-ECDS problem).
For a given graphG=V,E, the minimum 2,2-ECDS problem is the problem of constructing a minimum 2,2-ECDS for G.
Note that because the MCDS problem for a graph is NP-hard, the minimum2,2-ECDS problem for a graph is also NP-hard. In this paper, we will design an approximation algorithm for the minimum 2,2-ECDS problem.


## 3.2. Notations

In this subsection, we useG=V,E to denote a UDG.
(i)
GE∗: the spanning subgraph induced by E∗⊆E, namely, GE∗=V,E∗(ii)
GS: the subgraph induced by S⊆V(iii)
Ev: the edge subset, where each edge is incident to v∈V, namely, Ev=e∈Evisoneofe’sendpoints(iv)
ES,v: ES,v=e∈EoneendpointofeisvandanotherendpointofeisinS, where v∈V−S(v)
Nu: the set of neighbor nodes of u∈V(vi)
Nu: Nu=Nu∪u(vii)
IDu: the ID of node u(viii)
eu: the energy of node u(ix)
EG: the set consisting of all edges of G(x)
VG: the set consisting of all nodes of G


## 3.3. Definitions

Definition 5 (weight functionWx1,x2,x3).
Given two 3-tuple variablesx1i,x2i,x3i and x1j,x2j,x3j, for a weight function W:x1,x2,x3↦R, Wx1i,x2i,x3i>Wx1j,x2j,x3j if and only if at least one of the following conditions is true:
(i)
x1i>x1j(ii)
x1i=x1j and x2i>x2j(iii)
x1i=x1j and x2i=x2j and x3i<x3jDefinition 6 (bridge).
In a given UDGG=V,E, e∗∈E is called a bridge of G if GE−e∗ is disconnected.
According to Definitions1 and 6, a given UDG G=V,E is a 2 edge-connected graph if and only if each edge e∈E is not a bridge of G.Definition 7 (edge-disjoint).
In a given UDGG=V,E, let P1 and P2 be two different paths. Then, P1 and P2 are called edge-disjoint if EP1∩EP2=∅.Definition 8 (simple cycle).
In a given UDGG=V,E, let P=x1↔x2↔⋯↔xk be a path of G. The path P is called a simple cycle in G if x1=xk and xi≠xji,j=2,3,⋯,k−1,i≠j.
According to Whitney’s theorem [47], the proposition that for a given G=V,E, e∗ is a bridge of G is equal to any one of the following propositions.
(1)
InG, ∃x,y∈V such that all paths between x and y contain edge e∗(2)
G has no simple cycle containing e∗Definition 9 (2E-block).
In a given UDGG=V,E, let S⊆V. GS is a 2E-block of G if one of the following conditions holds:
(1)
S⊂V consists of a single node, and for any nonempty subset S′⊆V−S, GS∪S′ is not 2 edge-connected(2)
S⊂V consists of at least two nodes; GS is a 2 edge-connected graph; and for any nonempty subset S′⊆V−S, GS∪S′ is not 2 edge-connected(3)
S=V and G is a 2 edge-connected graphRemark 10.
According to the definitions of the2E-block and 2 edge-connected graphs, for a given graph UDG G=V,E and a set S⊆V, we have the following conclusions:
(1)
IfGS is a 2E-block of G, then GS is 2 edge-connected blocks(2)
GS is the unique 2E-block of GS if and only if GS is 2 edge-connectedDefinition 11 (LkSpath).
In a given UDGG=V,E, let S⊆V and x,y∈S. A path from x to y with k+2 nodes is called a LkS path if its k inner nodes belong to V−S.Lemma 12.
In a given UDGG=V,E, for any u,v∈V, there exist two paths that are edge-disjoint between u and v if and only if G is a 2 edge-connected graph.According to Definition7 and Whitney’s theorem, the proof of Lemma 12 is easy to obtain.


## 4. Algorithm and Analysis

In this section, we present an algorithm (called LLZ20) to construct a2,2-ECDS in a 2 edge-connected UDG G. LLZ20 includes three main parts. First, a CDS in G is constructed with the two-stage approximation algorithm (called ACC11) in [32]. Next, a connected 2 edge-dominating set is calculated by adding some nodes to the CDS obtained in the first part; this can be implemented by calling Algorithm 2, whose flow chart is shown in Figure 3. Finally, LkS paths are added to connect the nodes of the connected 2 edge-dominating set obtained in the second part to make it a (2,2)-ECDS; this can be implemented by calling Algorithm 3, whose flow chart is shown in Figure 4. In Algorithm 3, to compute 2E-blocks in a subgraph, we need to call another algorithm, Algorithm 4, whose flow chart is shown in Figure 5. LLZ20 is described formally in Algorithm 1.Algorithm 1: LLZ20.
Input: A 2 edge-connected UDG G=V,E.Output: A 2,2-ECDS S1′.1 Construct a CDSSCDS with ACC11 in G.2 Construct a connected 2 edge-dominating setS0 and a pseudocontrol node set VD with Algorithm 2 based on SCDS.3 Construct a2,2-ECDS S1′ with Algorithm 3 based on S0 and VD.4returnS1′.Algorithm 2: Calculate a 2 edge-dominating set.
Input: A connected graph G=V,E and a CDS SCDS of G.Output: A connected 2 edge-dominating set S0 and a pseudocontrol node set VD.1B0=V−SCDS2for each node v∈B0kdo3If∣ESCDS,v∣≥2then4B0=B0−v5end if6end for7D=∅, B=B0, L1=V−SCDS−B08whileB≠∅do9  Find a nodeu∈B with the highest Weu,∣Nu∩B∣,IDu.10if∣Nu∩B∣=0then11VD=VD∪u12end if13D=D∪u and B=B−Nu.14end while15S0=SCDS∪D16returnS0 and VD.Algorithm 3: Calculate a 2 edge-connected set.
Input: A 2 edge-connected graph G=V,E, a connected 2 edge-dominating set S0 in G and the corresponding pseudocontrol node set VD.Output: A 2,2-ECDS S1′ of G.1 Color all nodes white and assign each nodex∈V a super ID (called Eblock ID, denoted by Eblock_IDx). Initially, let Eblock_IDx=∞ for each node x∈V.2 Letconnector=∅, and calculate all 2E-blocks with Algorithm 4 in GS0∪connector.3while the number of 2E-blocks in GS0∪connector is more than 1 do.4if there exists an L1S0∪connector path connecting at least two 2E-blocks, then5  Find anL1S0∪connector path L1∗ whose inner node x connects the most 2E-blocks.6connector=connector∪x. Recompute the 2E-blocks in GS0∪connector with Algorithm 4.7else8  Find anL2S0∪connector path L2∗ such that the number of 2E-blocks connected by its inner nodes is the most.9connector=connector∪y,z, where y and z are the inner nodes of L2∗. Recompute the 2E-blocks in GS0∪connector with Algorithm 4.10end if11end while12S1=S0∪connector and S1′=S113for each node s in VDdo14ifGS1′−s is 2-edge connected then15S1′=S1′−s16end if17end for18returnS1′Algorithm 4: Calculate 2E-blocks.
Input: A 2 edge-connected graph G=V,E, a colored subgraph GS of G and Eblock_IDx, where x∈S⊆V.Output: The set EB consisting of all 2E-blocks in GS.1 Construct a BFS treeT in GS, and let BRANCH be the set of edges in T. Let Edone=∅, Sundo=S.2fori=1 to ∣S∣do3  Select a nodeu with the smallest IDu in Sundo.4ifES,u−BRANCH=∅then5ifu is a white node then6  Coloru blue, and Eblock_IDu=IDu.7end if8else9  LetEu=u,v∣u,v∈ES,u−BRANCH∪Edone10for each edge e∈Eudo11  Find a simple circleC, whose edges are all in the edge set BRANCH∪e, and let FC be the set of all nodes in C.12if there are no red nodes in FCthen.13  LetK1 be the minimum ID of nodes in FC.14  For eachw∈FC, let Eblock_IDw=K1.15  Color all nodes inFC red.16else17  LetEblock_IDFC=Eblock_IDw∣w∈FC. Let Q=Eblock_IDFC and K2=minx∣x∈Q.18  For eachw∈FC, Eblock_IDw=K2.19  Color all nodes inFC red.20for each p∈Q−K2,∞do21  For each nodew∈S with Eblock_IDw=p, Eblock_IDw=K2.22end for23end if24end for25Edone=Edone∪Eu.26end if27Sundo=Sundo−u.28end for29 LetEID1,EID2,⋯,EIDM=Eblock_IDx∣x∈S and Ri=x∈S∣Eblock_IDx=EIDii=1,2,⋯,M. Let EB=GR1,GR2,⋯,GRM30returnEB.Figure 3
The flow chart of Algorithm2.Figure 4
The flow chart of Algorithm3.Figure 5
The flow chart of Algorithm4.For readers to understand LLZ20 more intuitively, an example network graph is presented in Figure6 to illustrate the steps of LLZ20. For convenience, let the initial energy of each node be the same.
(1)
For a given WSN, which is abstracted as the network graphG=V,E (shown in Figure 6(a)), LLZ20 calls ACC11 to construct a CDS in G (line 1). In this process, u1, u2, and u4 are selected consecutively to form a CDS, and then, pseudocontrol node u4 is deleted because u4 does not affect the connectivity of the CDS. When this step is complete, u1,u2 (blue nodes shown in Figure 6(b)) is the resulting CDS SCDS(2)
In line 2 of LLZ20, Algorithm2 is called to calculate a dominating set D (green nodes shown in Figure 6(c)) in GV−u1,u2. Before Algorithm 2 is executed, nodes u3, u4, u7, u8, and u9 are not 2 edge-dominated by the CDS u1,u2. When Algorithm 2 is executed, u4 and u3 are consecutively selected to obtain a connected 2 edge-dominating set S0=u1,u2,u3,u4, and the pseudocontrol node set VD is an empty set (see Figure 6(c) for details)(3)
In line 3 of LLZ20, Algorithm3 is called to calculate the set connector, which consists of the inner nodes of the selected LkS path. Specifically, before Algorithm 2 is executed, u1,u2,u3,u4 is not 2 edge-connected. When Algorithm 2 is executed, the path u1↔u5↔u2 and the path u2↔u7↔u4 are consecutively selected; in other words, u5 and u7 are consecutively selected into the set connector. After this step is finished, S1′=u1,u2,u3,u4,u5,u7 is the resulting 2,2-ECDS (see Figure 6(d) for details)Figure 6
Illustration of the steps of LLZ20.
(a)
Illustration of a network graphG=V,E with 9 nodes(b)
The CDSSCDS obtained by calling ACC11 for G(c)
The connected 2 edge-dominating setS0 obtained by calling Algorithm 2 for G(d)
The2,2-ECDS S1′ obtained by calling Algorithm 3 for G


### 4.1. Analysis of Algorithm Correctness

In this subsection, we provide proof of the correctness of our algorithms and show that a2,2-ECDS must be obtained after executing LLZ20. For this purpose, we need to show only that the following three results are true: (1) ACC11 in [32] can generate a CDS, (2) Algorithm 2 can generate a connected 2 edge-dominating set, and (3) Algorithm 3 can generate a 2,2-ECDS.According to [32], the first result is true. Next, we show the correctness of the second result that Algorithm 2 can generate a connected 2 edge-dominating set.Lemma 13.
After executing Algorithm2, the output S0 is a connected 2 edge-dominating set.Proof.
We need to prove thatGS0 is connected and that S0 is a 2 edge-dominating set. First, since SCDS is a CDS and S0=SCDS∪D, GS0 is connected. Next, we prove that S0 is a 2 edge-dominating set. Let L2=B0−D, where B0 (D, respectively) is B0 (D, respectively) obtained after executing line 15. Then, V=S0∪L1∪L2. Let v∈V−S0; then, v∈L1∪L2. We claim that there are two edges with a common endpoint v such that their other endpoints are in S0. If v∈L1, then according to lines 2-7, ∣ESCDS,v∣≥2, our claim is true. If v∈L2, then according to lines 8-14, after executing line 14, D is an MIS in GB0, which means there is an edge with one endpoint v and another endpoint belonging to D. On the other hand, since SCDS is a CDS, there is an edge with endpoint v and another endpoint belonging to SCDS. Hence, our claim is true. According to the above analysis, S0 is a 2 edge-dominating set.According to the above lemma and lines 10-12 of Algorithm2, it is easy to obtain the following corollary.Corollary 14.
After Algorithm2 is executed, for any S∗⊆VD, S0−S∗ is a 2 edge-dominating set in GV−VD.Now, we show thatS1′ (the result of Algorithm 3) is a 2,2-ECDS. Before we present the proof, let us first introduce some definitions and lemmas used in the following discussions. The following preliminaries, which serve as proof of the correctness of the results, are necessary.For nodeu chosen in line 3, let Eu=e1,e2,⋯,eku (line 9), Sju be a set of red nodes with the same Eblock_IDu after executing the jth iteration of the for-loop (lines 10-24) in Algorithm 4j=1,2,⋯,ku, which is the iteration for ej (line 10). Let kju be the number of Eblock_IDs of the red nodes in C (line 11) before executing the jth iteration of the for-loop (lines 10-24), and let SPj be the subset of Sju that consists of all nonred nodes in C (line 11) before executing the jth iteration of the for-loop (lines 10-24) in Algorithm 4. When kju≥1, let Sjii=1,2,⋯,kju be the nonempty subset of Sju, which consists of all red nodes with the same Eblock_ID before executing the jth iteration of the for-loop (lines 10-24) in Algorithm 4. Then, Sju=Sj1∪Sj2∪⋯∪Sjkju∪SPj. In this case, Sj1,Sj2,⋯,Sjkju,SPj is called the TC decomposition of Sju, Sji is called a red TC decomposition piece of Sju, and SPj is called a nonred TC decomposition piece of Sju. Clearly, if there is no TC decomposition in Sju, then Sju=SPj.For a better understanding of TC decomposition, let us consider the network graphG1 shown in Figure 7, which is one part of the network obtained before executing the jth iteration of the for-loop (lines 10-24) in Algorithm 4, where the integer j is determined as follows. Assume that in network graph G1, u10 is the node u chosen by line 3 in Algorithm 4 and Eu10=u10,u2,u10,u4, the jth iteration of the for-loop (lines 10-24) is referred to as the iteration, in which the edge u10,u2∉BRANCH is considered (line 10). Assume that C=u2↔u3↔u4↔u5↔u9↔u10↔u2 is the simple circle determined by line 11 in the jth iteration, where Eblock_IDu2=Eblock_IDu3=Eblock_IDu4 and Eblock_IDu2≠Eblock_IDu5 before the jth iteration of the for-loop (lines 10-24). Then, Sju10=u1,u2,⋯,u10, kju10=2, S11=u1,u2,u3,u4, S12=u5,u6,u7,u8, SP1=u9,u10. Finally, S11,S12,SP1 is a TC decomposition of Sju10.Lemma 15.
If there is no TC decomposition inSju, then GSju contains a simple circle with all nodes of Sju.Proof.
According to the above discussion, it is easy to see that the result is true.Lemma 16.
Suppose thatkju≥1 and Sj1,Sj2,⋯,Sjkju,SPj is the TC decomposition of Sju, where j=1,2,⋯,ku. If GSjii=1,2,⋯,kju is 2 edge-connected, then GSju is 2 edge-connected.Proof.
According to the definition ofSPj and line 19, SPj⊆FC, where FC is the node set of the simple circle C selected in line 11 of Algorithm 4. Clearly, Sj1∪Sj2∪⋯∪Sjkju∪FC=Sju. We claim that Sji∩FC≠∅1≤i≤kju. Otherwise, after executing the jth iteration of the for-loop (lines 10-24) in Algorithm 4, the Eblock_IDs of the nodes in Sji are not equal to Eblock_IDu, which implies that Sji is not contained in Sju, a contradiction. Let E1,E2,⋯,Ekju and Ekju+1 be the edge sets in GSj1,GSj2,⋯,GSjkju and C, respectively. Construct a new graph G∗=V∗,E∗, where V∗=Sj1∪Sj2∪⋯∪Sjkju∪FC, E∗=E1∪E2∪⋯∪Ekju∪Ekju+1. Clearly, G∗ is connected: we claim that G∗ is 2 edge-connected. We need to prove only that for any edge e∈E∗, G∗E∗−e is connected.Case 1.
e∈Eii=1,2,⋯,kju. Since GSji is 2 edge-connected, GSji−e is still connected. According to Sji∩FC≠∅ and the fact that C is connected, we have that G∗E∗−e is connected.Case 2.
e∈Ekju+1. Since C is a simple circle, C−e is still connected. Note that Sji∩FC≠∅ and GSji are 2 edge-connected i=1,2,⋯,kju; thus, we have that G∗E∗−e is connected.Figure 7
An example illustrating TC decomposition.Hence,G∗ is 2 edge-connected. Since G∗ is a spanning subgraph of GSju, GSju is 2 edge-connected.Lemma 17.
After executing line 29 in Algorithm4, GRii=1,2,⋯,M is a 2E-block in GS.Proof.
According to line 6, lines 14-15, and lines 18-22,Rii=1,2,⋯,M consists of red nodes with the same Eblock_ID or a single blue node. Consider the following cases.Case 1.
Ri consists of a single blue node. Let x be this node. Clearly, x is not in any simple circle in GSju (otherwise, according to lines 10-24, x would be colored red). We claim that for any nonempty subset S′⊆S−x, GS′∪x is not 2 edge-connected. In contrast, assume that there exists a nonempty subset S′⊆S−x such that GS′∪x is 2 edge-connected. Let y∈S′; then, there exist two edge-disjoint paths between x and y in GS′∪x that form a simple circle and contain node x, a contradiction. Thus, this claim is true. According to the definition of a 2E-block, GRi is a 2E-block.Case 2.
Ri consists of red nodes with the same Eblock_ID.
According to the definition ofRi (line 29) and the structure of the for-loop (lines 2-28), we conclude that there is some selected node u∈S (line 3) with ES,u−BRANCH≠ϕ and some integer j1≤j≤ku such that the corresponding Sju is Ri. Now, consider the following two subcases:Case 1.
There is no TC decomposition inRi (Sju).
According to Lemma15, GRi contains a simple circle with all nodes in Ri, which implies that GRi is 2 edge-connected nodes. Next, we show that for any nonempty set S′⊆S−Ri, GS′∪Ri is not 2 edge-connected. To the contrary, assume that GS′∪Ri is 2 edge-connected. Let x∈S′ and y∈Ri; then, there are two edge-disjoint paths between x and y in GS′∪Ri that form a simple circle Cx,y. Cx,y has at least one edge that does not belong to BRANCH. Note that for any x1,y1∉BRANCH, there exists a unique simple cycle containing x1,y1, whose other edges belong to BRANCH. Hence, there exists a simple cycle C¯x,y containing x,y and an edge x2,y2∉BRANCH, whose other edges belong to BRANCH. Without loss of generality, suppose that IDx2<IDy2. When x2 is selected in line 3, x2,y2∈Ex2. Then, a simple circle C (line 11), whose edges are all in set BRANCH∪x2,y2, is determined in the iteration in which x2,y2 is chosen (line 10). Clearly, C is C¯x,y. After this iteration is finished, x,y are colored red, and Eblock_IDx=Eblock_IDy. Furthermore, after executing line 9, it is still true that Eblock_IDx=Eblock_IDy, which implies that x,y∈Ri, a contradiction to the assumption that x∈S′. Hence, GS′∪Ri is not 2 edge-connected. As a result, GRi is a 2E-block.Case 2.
There is a TC decomposition inRiSju.
We first prove thatGRi is 2 edge-connected. Assuming that GRi is not a 2 edge-connected graph, we will arrive at a contradiction. Let Sj1,Sj2,⋯,Sjku,SPj be the TC decomposition of Ri; then, according to Lemma 16, there must exist t1t1∈1,2,⋯,ku such that GSjt1 is not 2 edge-connected. According to the structure of the for the-loop (lines 2-28), there is some u1∈S and some integer j1 such that Sjt1=Sj1u1.
If there is no TC decomposition inSjt1, then according to Lemma 15, GSjt1 is 2 edge-connected, a contradiction. If there is a TC decomposition in Sjt1, we have that there exists a Sj1t2⊆Sjt1 such that GSj1t2 is not 2 edge-connected, where t2∈1,2,⋯,ku1. Repeating this procedure, we obtain a series of sets Sj0t1,Sj1t2,⋯,Sjm−1tm and Sjmtm+1 that satisfy the following conditions:
(1)
Sjiti+1 is a red TC decomposition piece of Sji−1ti, 1≤i≤m(2)
GSjiti+10≤i≤m is not 2 edge-connected(3)
Sjiti+10≤i≤m−1 has a TC decomposition, and Sjmtm+1 has no TC decomposition
Here,Sj0t1=Sjt1. Notably, the iteration of this procedure can terminate because each Sju that has a TC decomposition is determined by an edge in GS−BRANCH and the number of edges in GS−BRANCH is bounded (see the definition of TC decomposition). According to Lemma 15, GSjmtm+1 is 2 edge-connected, a contradiction. Hence, GRi is 2 edge-connected.
Next, we show that for any nonempty setS′⊆S∗−Ri, GS′∪Ri is not 2 edge-connected. A similar discussion to the proof of Case 1 can be used to prove this result.
From the above analysis,GRi is a 2E-block.Lemma 18.
After executing line 29 in Algorithm4, EB=GR1,GR2,⋯,GRM contains exactly all 2E-blocks in GS.Proof.
Lemma17 shows that each GRi∈EB is a 2E-block. Next, we need to prove only that except for GR1,GR2,⋯,GRM, there are no other 2E-blocks in GS. In contrast, assume that there is another 2E-block GR∗∉EB with R∗=x1,x2,⋯,xk⊆Sk≥1 in GS. Consider the following cases.Case 1.
∣R∗∣=1. Note that S=R1∪R2⋯∪RM; then, there exists some i∈1,2,⋯,M such that R∗=x1⊆Ri. According to the definition of a 2E-block, GR∗ is not a 2E-block, a contradiction.Case 2.
∣R∗∣≥2. Consider the following subcases.
Case 1. There isRii∈1,2,⋯,M such that R∗⊆Ri. According to the definition of a 2E-block, GR∗ is not a 2E-block, a contradiction.
Case 2. There is not anRii∈1,2,⋯,M such that R∗⊆Ri. Note that R∗⊆S=R1∪R2⋯∪RM. Then, ∃xi,xj∈R∗ and Rp,Rq∈EB such that xi∈Rp and xj∈Rqp≠q. According to the assumption, R∗ is a 2E-block, which implies that GR∗ is 2 edge-connected paths; thus, there exist 2 edge-disjoint paths between x1 and x2 that form a simple circle. Hence, GR∗∪Rp∪Rq is 2 edge-connected, a contradiction to the assumption that GR∗ is a 2E-block.
Thus,EB=GR1,GR2,⋯,GRM contains exactly all 2E-blocks in GS.Lemma 19.
In each iteration of thewhile-loop (lines 3-11) in Algorithm 3, before the execution of line 4, there must exist a shortest path LkS0∪connectork≤2 in G that connects at least 2 different 2E-blocks in GS0∪connector.Proof.
According to line 3, before the execution of line 4, there exist at least two2E-blocks in GS¯, where S¯=S0∪connector. In the following discussions, S¯=S0∪connector is a set obtained before the execution of line 4. Let EC1,EC2,⋯,ECrr≥2 be all the 2E-blocks in GS¯.First, we prove that inG, there must exist an LkS¯ path that connects at least 2 different 2E-blocks. Since r≥2, there must exist a bridge in GS¯. Let e be a bridge in GS¯; then, ∃x,y∈S¯ such that all paths between x and y contain bridge e, which implies that there are no edge-disjoint paths between x and y in GS¯. On the other hand, since G is a 2 edge-connected graph, there are two edge-disjoint paths between x and y in G (Lemma 12). Let H be the shortest path from x to y in G that does not contain bridge e and has at least one node outside GS¯. For convenience, for u,v∈V, we use Pu,v to denote a path from u to v and P¯u,v to denote Pu,v−u,v, and we let H=x⟶⋯⟶x1⟶P¯x1,x2⟶x2⟶⋯⟶x3⟶P¯x3,x4⟶x4⋯⟶xt⟶P¯xt,xt+1⟶xt+1⟶⋯⟶y, where each P¯xi,xi+11≤i≤t is nonempty and its nodes are outside GS¯ and the nodes in H−∪i=1tP¯xi,xi+1 are in GS¯. We claim that there exists some P¯xi,xi+11≤i≤t such that xi and xi+1 belong to two different 2E-blocks in GS¯. In contrast, assume that for each P¯xi,xi+11≤i≤t, xi,xi+1 belongs to the same 2E-block, say ECl1≤l≤t in GS¯ (see Figure 8). According to the definition of a 2E-block, there is a path Qxi,xi+1 from xi to xi+1 in the 2E-block ECl. Now, using Qxi,xi+1 to replace xi⟶P¯xi,xi+1⟶xi+11≤i≤t in H, we obtain a new path H′ in GS¯ that does not contain bridge e, a contradiction. Hence, the claim is true.Figure 8
An example illustrating pathP¯xi,xi+1 and path Qxi,xi+1.Now, we suppose thatP¯xi,xi+1 satisfies the condition that xi and xi+1 belong to two different 2E-blocks in GS¯, say xi∈EC1, xi+1∈EC2. Let P¯xi,xi+1=xi1⟶xi2⟶⋯⟶xik; then, xi⟶xi1⟶xi2⟶⋯⟶xik⟶xi+1 is an LkS¯. Next, we prove that there is an LmS¯m≤2 in G by induction on k, the number of nodes in P¯xi,xi+1. When k≤2, the result is clearly true.Whenk=3, since S¯ is a dominating set, there is a node in S¯, say z, such that z∈Nxi2. If z∉EC1, then xi⟶xi1⟶xi2⟶z is an L2S¯; the result is true. If z∈EC1, then z⟶xi2⟶xi3⟶xi+1 is an L2S¯; the result is true.Assume that whenk=n, the result is true. Now, we consider the situation k=n+1. Then, P¯xi,xi+1=xi1⟶xi2⟶⋯⟶xin+1. Similarly, since S¯ is a dominating set, there is a node in S¯, say z, such that z∈Nxi2. If z∉EC1, then xi⟶xi1⟶xi2⟶z is an L2S¯; the result is true. If z∈EC1, then z⟶xi2⟶⋯⟶xin+1⟶xi+1 is an LnS¯. According to the inductive assumption, we have that the result is true.Lemma 20.
In Algorithm3, let connectorj be the set connector obtained after executing the jth iteration of the while-loop (lines 3-11) 1≤j≤∣S0∣ and let EBj be the set consisting of all 2E-blocks in GS0∪connectorj (EB0 denotes the set consisting of all 2E-blocks in GS0). Then, ∣EBj∣<∣EBj−1∣.Proof.
LetLkj be the LkS0∪connectorjk=1or2 in the jth iteration of the while-loop (lines 3-11) in Algorithm 3 and EBj=M1j,M2j,⋯,Msj. Without loss of generality, let M1j−1,M2j−1 be these two 2E-blocks in EBj−1, which are connected by Lkj, and let x1 and x2 be the two endpoints of Lkj with xi∈VMij−1i=1,2. Since GS0∪connectorj−1 is connected, there is a path P1 between x1 and x2 in GS0∪connectorj−1. Note that ELkj∩EP1=∅. Therefore, there is a simple circle containing x1 and x2 in Lkj∪P1, denoted by C1. After calling Algorithm 4 to recompute the 2E-blocks of GS0∪connectorj, the 2E-block_IDs of nodes in M1j∪M2j∪VLkj are the same.
LetEIDC1=Eblock_IDx∣x∈VC1. Clearly, ∣EIDC1∣≥2 before executing the jth iteration of the while-loop (lines 3-11). Let Aj=x∈S0∪connectorj∣Eblock_IDx∈EIDC1.
In thejth iteration of the while-loop (lines 3-11) in Algorithm 3, after executing line 6 or line 9, which calls Algorithm 4 to recompute the 2E-blocks in GS0∪connectorj, each node x∈Aj is set to have the same Eblock_ID value, while the Eblock_ID values of the nodes in S0∪connectorj−Aj are unchanged. Thus, the number of different Eblock_IDs of the nodes in GS0∪connectorj is less than that of different Eblock_IDs of the nodes in GS0∪connectorj−1. According to line 29 in Algorithm 4 and Lemma 18, we conclude that the number of different 2E-blocks in GS0∪connectorj is less than that in GS0∪connectorj−1; in other words, ∣EBj∣<∣EBj−1∣.
Next, we use the above preliminaries to prove thatS1′ generated by Algorithm 3 is a 2,2-ECDS of G. In fact, according to Lemmas 18 and 19, we know that in Algorithm 3, the while-loop (lines 3-11) can be executed only if the number of 2E-blocks in GS0∪connector is more than 1. Thus, according to Lemma 20, we conclude that after executing Algorithm 3, there is only one 2E-block in GS0∪connector. Furthermore, according to the definition of a 2E-block, GS0∪connector is 2 edge-connected blocks. This implies that S1=S0∪connector (line 12) is a 2,2-ECDS of G. Note that VD⊆D and D⊆S0 (see while-loop (lines 8-14) and line 15 in Algorithm 2); thus, VD⊆S0. According to the for-loop (lines 13-17), it is easy to see that S1′ (line 18) is 2 edge-connected.
LetS∗⊆VD be the set of nodes deleted in the for-loop (lines 13-17); then, after Algorithm 3 is executed, S1′=S1−S∗ and S∗⊆VD⊆S1, which imply that V−S1′=S∗∪V−S1. Next, we prove that S1′ is a 2 edge-dominating set. Equivalently, we need to prove only that for u∈V−S1′, u is 2 edge-dominated by S1′. Note that S∗∩V−S1=∅; thus, u∈S∗ or u∈V−S1. Consider the following cases.Case 1.
u∈S∗. Since S∗⊆VD is an independent set and GS1=GS1′∪S∗ is 2 edge-connected, u is 2 edge-dominated by S1′, where S1′ is the S1′ obtained after the for-loop (lines 13-17) is executed.Case 2.
u∈V−S1. Note that V−S1=V−S1∪S∗⊆V−S0∪S∗ and that, according to Corollary 14, u is 2 edge-dominated by S0−S∗. On the other hand, since S0−S∗⊆S1−S∗=S1′, u is 2 edge-dominated by S1′.Overall,S1′ is a 2 edge-dominating set. Thus, S1′ (line 18) is a 2,2-ECDS of G.According to the above discussions, we obtain the following theorem.Theorem 21.
The output of Algorithm1 is a 2,2-ECDS of G.


### 4.2. Analysis of the Performance Ratio and Time Complexity

In the above subsection, we provided proof that a2,2-ECDS must be obtained by our algorithms. In this subsection, we prove that LLZ20 is an approximation algorithm and then present its performance ratio.In line 1 of Algorithm1, for a given graph G, we utilize ACC11 in [32] to construct a CDS in G. In this process, a CDS is calculated in 2 steps. In the first step, an MIS is obtained; in the second step, some nodes outside the MIS are added to the MIS such that it becomes a CDS SCDS. Das et al. [32] proved that the size of SCDS is no more than 6.78∗optG+8.12, where optG is the MCDS size in G.Lemma 22.
After executing line 2 in Algorithm1, ∣S0∣≤10.17∗optG+12.68, where optG is the MCDS size in G.Proof.
According to lines 7-14 of Algorithm2, D is an MIS in GB0. Since D⊆SMIS, ∣D∣≤∣SMIS∣, where SMIS is an MIS in G. According to [30], ∣SMIS∣≤3.39∗optG+4.56. Hence, ∣D∣≤3.39∗optG+4.56.
According to line 15 of Algorithm2, we obtain the following inequalities:
(1)∣S0∣≤∣SCDS∣+∣D∣≤6.78∗optG+8.12+3.39∗optG+4.56=10.17∗optG+12.68.Lemma 23.
After executing Algorithm3, ∣connector∣≤2∗∣S0∣−1.Proof.
Letm be the number of 2E-blocks in line 2 of Algorithm 3. Clearly, m≤∣S0∣. According to Lemma 20, the number of iterations of the while-loop (lines 3-11) in Algorithm 3 is no more than m−1. Note that in each iteration of the while-loop (lines 3-11), one or two new nodes are added to connector. Hence, ∣connector∣≤2∗m−1≤2∗∣S0∣−1.Theorem 24.
After executing line 3 in Algorithm1, ∣S1′∣≤30.51∗opt+36.04, where opt is the minimum 2,2-ECDS size in G.Proof.
LetoptG be the MCDS size in G; then, optG≤opt. According to Algorithm 3 and Lemmas 22 and 23, we have the following inequalities:
(2)∣S1′∣≤∣S1∣=∣S0∣+∣connector∣≤3∣S0∣−2≤30.51∗optG+36.04≤30.51∗opt+36.04.In the following paragraphs, we discuss the time complexity of LLZ20. The overall time cost of LLZ20 includes three components: (1) the time cost of computing a CDSSCDS by ACC11, (2) the time cost of computing a 2 edge-dominating CDS S0 by Algorithm 2, and (3) the time cost of constructing a 2,2-ECDS S1′ by Algorithm 3.Denote the number of nodes in a given inputG by n. In the first phase, according to [32], the time cost of constructing a CDS SCDS by ACC11 is On3.In the second phase, the time cost of calculating the setB0 of the nodes that have only one dominator in SCDS is On (the for-loop (lines 2-6)). Moreover, the time cost of finding an MIS in GB0 is On2 (the while-loop (lines 8-14)). Hence, the time cost of constructing a 2 edge-dominating CDS S0 by Algorithm 2 is On+n2=On2.In the third phase, since Algorithm4 is called to compute the 2E-blocks in the subgraph induced by the updated S0∪connector, the time complexity of Algorithm 4 must be analyzed. In Algorithm 4, the time cost of constructing a BFS tree T is On2. In the iterations of the for-loop (lines 2-28), the time cost of computing all 2E-blocks in GS based on T is On3. Hence, the time complexity of Algorithm 4 is On2+n3=On3. Now, we discuss the time cost of using Algorithm 3 to obtain the 2,2-ECDS S1′. In Algorithm 3, iteration of the while-loop (lines 3-11) is equal to On, and the overall behavior of line 2, line 6, and line 9 is similar. Each computes the 2E-blocks in the subgraph induced by the updated S0∪connector by calling Algorithm 4, which implies that all of their time costs are On3. Consequently, the time cost of adding LkS0∪connector paths to connect a 2 edge-dominating set S0 to form a 2,2-ECDS (while-loop (lines 3-11)) is On4. In addition, the time cost of deleting some redundant nodes from S1 (lines 13-17) is On4. Hence, in the third phase, the time complexity of constructing a 2,2-ECDS S1′ by Algorithm 3 is On3+n4+n4=On4.Overall, the time complexity of Algorithm1 is On3+n2+n4=On4.Theorem 25.
Suppose that the number of nodes in a given inputG is n; then, the time complexity of LLZ20 (Algorithm 1) is On4.


## 4.1. Analysis of Algorithm Correctness

In this subsection, we provide proof of the correctness of our algorithms and show that a2,2-ECDS must be obtained after executing LLZ20. For this purpose, we need to show only that the following three results are true: (1) ACC11 in [32] can generate a CDS, (2) Algorithm 2 can generate a connected 2 edge-dominating set, and (3) Algorithm 3 can generate a 2,2-ECDS.According to [32], the first result is true. Next, we show the correctness of the second result that Algorithm 2 can generate a connected 2 edge-dominating set.Lemma 13.
After executing Algorithm2, the output S0 is a connected 2 edge-dominating set.Proof.
We need to prove thatGS0 is connected and that S0 is a 2 edge-dominating set. First, since SCDS is a CDS and S0=SCDS∪D, GS0 is connected. Next, we prove that S0 is a 2 edge-dominating set. Let L2=B0−D, where B0 (D, respectively) is B0 (D, respectively) obtained after executing line 15. Then, V=S0∪L1∪L2. Let v∈V−S0; then, v∈L1∪L2. We claim that there are two edges with a common endpoint v such that their other endpoints are in S0. If v∈L1, then according to lines 2-7, ∣ESCDS,v∣≥2, our claim is true. If v∈L2, then according to lines 8-14, after executing line 14, D is an MIS in GB0, which means there is an edge with one endpoint v and another endpoint belonging to D. On the other hand, since SCDS is a CDS, there is an edge with endpoint v and another endpoint belonging to SCDS. Hence, our claim is true. According to the above analysis, S0 is a 2 edge-dominating set.According to the above lemma and lines 10-12 of Algorithm2, it is easy to obtain the following corollary.Corollary 14.
After Algorithm2 is executed, for any S∗⊆VD, S0−S∗ is a 2 edge-dominating set in GV−VD.Now, we show thatS1′ (the result of Algorithm 3) is a 2,2-ECDS. Before we present the proof, let us first introduce some definitions and lemmas used in the following discussions. The following preliminaries, which serve as proof of the correctness of the results, are necessary.For nodeu chosen in line 3, let Eu=e1,e2,⋯,eku (line 9), Sju be a set of red nodes with the same Eblock_IDu after executing the jth iteration of the for-loop (lines 10-24) in Algorithm 4j=1,2,⋯,ku, which is the iteration for ej (line 10). Let kju be the number of Eblock_IDs of the red nodes in C (line 11) before executing the jth iteration of the for-loop (lines 10-24), and let SPj be the subset of Sju that consists of all nonred nodes in C (line 11) before executing the jth iteration of the for-loop (lines 10-24) in Algorithm 4. When kju≥1, let Sjii=1,2,⋯,kju be the nonempty subset of Sju, which consists of all red nodes with the same Eblock_ID before executing the jth iteration of the for-loop (lines 10-24) in Algorithm 4. Then, Sju=Sj1∪Sj2∪⋯∪Sjkju∪SPj. In this case, Sj1,Sj2,⋯,Sjkju,SPj is called the TC decomposition of Sju, Sji is called a red TC decomposition piece of Sju, and SPj is called a nonred TC decomposition piece of Sju. Clearly, if there is no TC decomposition in Sju, then Sju=SPj.For a better understanding of TC decomposition, let us consider the network graphG1 shown in Figure 7, which is one part of the network obtained before executing the jth iteration of the for-loop (lines 10-24) in Algorithm 4, where the integer j is determined as follows. Assume that in network graph G1, u10 is the node u chosen by line 3 in Algorithm 4 and Eu10=u10,u2,u10,u4, the jth iteration of the for-loop (lines 10-24) is referred to as the iteration, in which the edge u10,u2∉BRANCH is considered (line 10). Assume that C=u2↔u3↔u4↔u5↔u9↔u10↔u2 is the simple circle determined by line 11 in the jth iteration, where Eblock_IDu2=Eblock_IDu3=Eblock_IDu4 and Eblock_IDu2≠Eblock_IDu5 before the jth iteration of the for-loop (lines 10-24). Then, Sju10=u1,u2,⋯,u10, kju10=2, S11=u1,u2,u3,u4, S12=u5,u6,u7,u8, SP1=u9,u10. Finally, S11,S12,SP1 is a TC decomposition of Sju10.Lemma 15.
If there is no TC decomposition inSju, then GSju contains a simple circle with all nodes of Sju.Proof.
According to the above discussion, it is easy to see that the result is true.Lemma 16.
Suppose thatkju≥1 and Sj1,Sj2,⋯,Sjkju,SPj is the TC decomposition of Sju, where j=1,2,⋯,ku. If GSjii=1,2,⋯,kju is 2 edge-connected, then GSju is 2 edge-connected.Proof.
According to the definition ofSPj and line 19, SPj⊆FC, where FC is the node set of the simple circle C selected in line 11 of Algorithm 4. Clearly, Sj1∪Sj2∪⋯∪Sjkju∪FC=Sju. We claim that Sji∩FC≠∅1≤i≤kju. Otherwise, after executing the jth iteration of the for-loop (lines 10-24) in Algorithm 4, the Eblock_IDs of the nodes in Sji are not equal to Eblock_IDu, which implies that Sji is not contained in Sju, a contradiction. Let E1,E2,⋯,Ekju and Ekju+1 be the edge sets in GSj1,GSj2,⋯,GSjkju and C, respectively. Construct a new graph G∗=V∗,E∗, where V∗=Sj1∪Sj2∪⋯∪Sjkju∪FC, E∗=E1∪E2∪⋯∪Ekju∪Ekju+1. Clearly, G∗ is connected: we claim that G∗ is 2 edge-connected. We need to prove only that for any edge e∈E∗, G∗E∗−e is connected.Case 1.
e∈Eii=1,2,⋯,kju. Since GSji is 2 edge-connected, GSji−e is still connected. According to Sji∩FC≠∅ and the fact that C is connected, we have that G∗E∗−e is connected.Case 2.
e∈Ekju+1. Since C is a simple circle, C−e is still connected. Note that Sji∩FC≠∅ and GSji are 2 edge-connected i=1,2,⋯,kju; thus, we have that G∗E∗−e is connected.Figure 7
An example illustrating TC decomposition.Hence,G∗ is 2 edge-connected. Since G∗ is a spanning subgraph of GSju, GSju is 2 edge-connected.Lemma 17.
After executing line 29 in Algorithm4, GRii=1,2,⋯,M is a 2E-block in GS.Proof.
According to line 6, lines 14-15, and lines 18-22,Rii=1,2,⋯,M consists of red nodes with the same Eblock_ID or a single blue node. Consider the following cases.Case 1.
Ri consists of a single blue node. Let x be this node. Clearly, x is not in any simple circle in GSju (otherwise, according to lines 10-24, x would be colored red). We claim that for any nonempty subset S′⊆S−x, GS′∪x is not 2 edge-connected. In contrast, assume that there exists a nonempty subset S′⊆S−x such that GS′∪x is 2 edge-connected. Let y∈S′; then, there exist two edge-disjoint paths between x and y in GS′∪x that form a simple circle and contain node x, a contradiction. Thus, this claim is true. According to the definition of a 2E-block, GRi is a 2E-block.Case 2.
Ri consists of red nodes with the same Eblock_ID.
According to the definition ofRi (line 29) and the structure of the for-loop (lines 2-28), we conclude that there is some selected node u∈S (line 3) with ES,u−BRANCH≠ϕ and some integer j1≤j≤ku such that the corresponding Sju is Ri. Now, consider the following two subcases:Case 1.
There is no TC decomposition inRi (Sju).
According to Lemma15, GRi contains a simple circle with all nodes in Ri, which implies that GRi is 2 edge-connected nodes. Next, we show that for any nonempty set S′⊆S−Ri, GS′∪Ri is not 2 edge-connected. To the contrary, assume that GS′∪Ri is 2 edge-connected. Let x∈S′ and y∈Ri; then, there are two edge-disjoint paths between x and y in GS′∪Ri that form a simple circle Cx,y. Cx,y has at least one edge that does not belong to BRANCH. Note that for any x1,y1∉BRANCH, there exists a unique simple cycle containing x1,y1, whose other edges belong to BRANCH. Hence, there exists a simple cycle C¯x,y containing x,y and an edge x2,y2∉BRANCH, whose other edges belong to BRANCH. Without loss of generality, suppose that IDx2<IDy2. When x2 is selected in line 3, x2,y2∈Ex2. Then, a simple circle C (line 11), whose edges are all in set BRANCH∪x2,y2, is determined in the iteration in which x2,y2 is chosen (line 10). Clearly, C is C¯x,y. After this iteration is finished, x,y are colored red, and Eblock_IDx=Eblock_IDy. Furthermore, after executing line 9, it is still true that Eblock_IDx=Eblock_IDy, which implies that x,y∈Ri, a contradiction to the assumption that x∈S′. Hence, GS′∪Ri is not 2 edge-connected. As a result, GRi is a 2E-block.Case 2.
There is a TC decomposition inRiSju.
We first prove thatGRi is 2 edge-connected. Assuming that GRi is not a 2 edge-connected graph, we will arrive at a contradiction. Let Sj1,Sj2,⋯,Sjku,SPj be the TC decomposition of Ri; then, according to Lemma 16, there must exist t1t1∈1,2,⋯,ku such that GSjt1 is not 2 edge-connected. According to the structure of the for the-loop (lines 2-28), there is some u1∈S and some integer j1 such that Sjt1=Sj1u1.
If there is no TC decomposition inSjt1, then according to Lemma 15, GSjt1 is 2 edge-connected, a contradiction. If there is a TC decomposition in Sjt1, we have that there exists a Sj1t2⊆Sjt1 such that GSj1t2 is not 2 edge-connected, where t2∈1,2,⋯,ku1. Repeating this procedure, we obtain a series of sets Sj0t1,Sj1t2,⋯,Sjm−1tm and Sjmtm+1 that satisfy the following conditions:
(1)
Sjiti+1 is a red TC decomposition piece of Sji−1ti, 1≤i≤m(2)
GSjiti+10≤i≤m is not 2 edge-connected(3)
Sjiti+10≤i≤m−1 has a TC decomposition, and Sjmtm+1 has no TC decomposition
Here,Sj0t1=Sjt1. Notably, the iteration of this procedure can terminate because each Sju that has a TC decomposition is determined by an edge in GS−BRANCH and the number of edges in GS−BRANCH is bounded (see the definition of TC decomposition). According to Lemma 15, GSjmtm+1 is 2 edge-connected, a contradiction. Hence, GRi is 2 edge-connected.
Next, we show that for any nonempty setS′⊆S∗−Ri, GS′∪Ri is not 2 edge-connected. A similar discussion to the proof of Case 1 can be used to prove this result.
From the above analysis,GRi is a 2E-block.Lemma 18.
After executing line 29 in Algorithm4, EB=GR1,GR2,⋯,GRM contains exactly all 2E-blocks in GS.Proof.
Lemma17 shows that each GRi∈EB is a 2E-block. Next, we need to prove only that except for GR1,GR2,⋯,GRM, there are no other 2E-blocks in GS. In contrast, assume that there is another 2E-block GR∗∉EB with R∗=x1,x2,⋯,xk⊆Sk≥1 in GS. Consider the following cases.Case 1.
∣R∗∣=1. Note that S=R1∪R2⋯∪RM; then, there exists some i∈1,2,⋯,M such that R∗=x1⊆Ri. According to the definition of a 2E-block, GR∗ is not a 2E-block, a contradiction.Case 2.
∣R∗∣≥2. Consider the following subcases.
Case 1. There isRii∈1,2,⋯,M such that R∗⊆Ri. According to the definition of a 2E-block, GR∗ is not a 2E-block, a contradiction.
Case 2. There is not anRii∈1,2,⋯,M such that R∗⊆Ri. Note that R∗⊆S=R1∪R2⋯∪RM. Then, ∃xi,xj∈R∗ and Rp,Rq∈EB such that xi∈Rp and xj∈Rqp≠q. According to the assumption, R∗ is a 2E-block, which implies that GR∗ is 2 edge-connected paths; thus, there exist 2 edge-disjoint paths between x1 and x2 that form a simple circle. Hence, GR∗∪Rp∪Rq is 2 edge-connected, a contradiction to the assumption that GR∗ is a 2E-block.
Thus,EB=GR1,GR2,⋯,GRM contains exactly all 2E-blocks in GS.Lemma 19.
In each iteration of thewhile-loop (lines 3-11) in Algorithm 3, before the execution of line 4, there must exist a shortest path LkS0∪connectork≤2 in G that connects at least 2 different 2E-blocks in GS0∪connector.Proof.
According to line 3, before the execution of line 4, there exist at least two2E-blocks in GS¯, where S¯=S0∪connector. In the following discussions, S¯=S0∪connector is a set obtained before the execution of line 4. Let EC1,EC2,⋯,ECrr≥2 be all the 2E-blocks in GS¯.First, we prove that inG, there must exist an LkS¯ path that connects at least 2 different 2E-blocks. Since r≥2, there must exist a bridge in GS¯. Let e be a bridge in GS¯; then, ∃x,y∈S¯ such that all paths between x and y contain bridge e, which implies that there are no edge-disjoint paths between x and y in GS¯. On the other hand, since G is a 2 edge-connected graph, there are two edge-disjoint paths between x and y in G (Lemma 12). Let H be the shortest path from x to y in G that does not contain bridge e and has at least one node outside GS¯. For convenience, for u,v∈V, we use Pu,v to denote a path from u to v and P¯u,v to denote Pu,v−u,v, and we let H=x⟶⋯⟶x1⟶P¯x1,x2⟶x2⟶⋯⟶x3⟶P¯x3,x4⟶x4⋯⟶xt⟶P¯xt,xt+1⟶xt+1⟶⋯⟶y, where each P¯xi,xi+11≤i≤t is nonempty and its nodes are outside GS¯ and the nodes in H−∪i=1tP¯xi,xi+1 are in GS¯. We claim that there exists some P¯xi,xi+11≤i≤t such that xi and xi+1 belong to two different 2E-blocks in GS¯. In contrast, assume that for each P¯xi,xi+11≤i≤t, xi,xi+1 belongs to the same 2E-block, say ECl1≤l≤t in GS¯ (see Figure 8). According to the definition of a 2E-block, there is a path Qxi,xi+1 from xi to xi+1 in the 2E-block ECl. Now, using Qxi,xi+1 to replace xi⟶P¯xi,xi+1⟶xi+11≤i≤t in H, we obtain a new path H′ in GS¯ that does not contain bridge e, a contradiction. Hence, the claim is true.Figure 8
An example illustrating pathP¯xi,xi+1 and path Qxi,xi+1.Now, we suppose thatP¯xi,xi+1 satisfies the condition that xi and xi+1 belong to two different 2E-blocks in GS¯, say xi∈EC1, xi+1∈EC2. Let P¯xi,xi+1=xi1⟶xi2⟶⋯⟶xik; then, xi⟶xi1⟶xi2⟶⋯⟶xik⟶xi+1 is an LkS¯. Next, we prove that there is an LmS¯m≤2 in G by induction on k, the number of nodes in P¯xi,xi+1. When k≤2, the result is clearly true.Whenk=3, since S¯ is a dominating set, there is a node in S¯, say z, such that z∈Nxi2. If z∉EC1, then xi⟶xi1⟶xi2⟶z is an L2S¯; the result is true. If z∈EC1, then z⟶xi2⟶xi3⟶xi+1 is an L2S¯; the result is true.Assume that whenk=n, the result is true. Now, we consider the situation k=n+1. Then, P¯xi,xi+1=xi1⟶xi2⟶⋯⟶xin+1. Similarly, since S¯ is a dominating set, there is a node in S¯, say z, such that z∈Nxi2. If z∉EC1, then xi⟶xi1⟶xi2⟶z is an L2S¯; the result is true. If z∈EC1, then z⟶xi2⟶⋯⟶xin+1⟶xi+1 is an LnS¯. According to the inductive assumption, we have that the result is true.Lemma 20.
In Algorithm3, let connectorj be the set connector obtained after executing the jth iteration of the while-loop (lines 3-11) 1≤j≤∣S0∣ and let EBj be the set consisting of all 2E-blocks in GS0∪connectorj (EB0 denotes the set consisting of all 2E-blocks in GS0). Then, ∣EBj∣<∣EBj−1∣.Proof.
LetLkj be the LkS0∪connectorjk=1or2 in the jth iteration of the while-loop (lines 3-11) in Algorithm 3 and EBj=M1j,M2j,⋯,Msj. Without loss of generality, let M1j−1,M2j−1 be these two 2E-blocks in EBj−1, which are connected by Lkj, and let x1 and x2 be the two endpoints of Lkj with xi∈VMij−1i=1,2. Since GS0∪connectorj−1 is connected, there is a path P1 between x1 and x2 in GS0∪connectorj−1. Note that ELkj∩EP1=∅. Therefore, there is a simple circle containing x1 and x2 in Lkj∪P1, denoted by C1. After calling Algorithm 4 to recompute the 2E-blocks of GS0∪connectorj, the 2E-block_IDs of nodes in M1j∪M2j∪VLkj are the same.
LetEIDC1=Eblock_IDx∣x∈VC1. Clearly, ∣EIDC1∣≥2 before executing the jth iteration of the while-loop (lines 3-11). Let Aj=x∈S0∪connectorj∣Eblock_IDx∈EIDC1.
In thejth iteration of the while-loop (lines 3-11) in Algorithm 3, after executing line 6 or line 9, which calls Algorithm 4 to recompute the 2E-blocks in GS0∪connectorj, each node x∈Aj is set to have the same Eblock_ID value, while the Eblock_ID values of the nodes in S0∪connectorj−Aj are unchanged. Thus, the number of different Eblock_IDs of the nodes in GS0∪connectorj is less than that of different Eblock_IDs of the nodes in GS0∪connectorj−1. According to line 29 in Algorithm 4 and Lemma 18, we conclude that the number of different 2E-blocks in GS0∪connectorj is less than that in GS0∪connectorj−1; in other words, ∣EBj∣<∣EBj−1∣.
Next, we use the above preliminaries to prove thatS1′ generated by Algorithm 3 is a 2,2-ECDS of G. In fact, according to Lemmas 18 and 19, we know that in Algorithm 3, the while-loop (lines 3-11) can be executed only if the number of 2E-blocks in GS0∪connector is more than 1. Thus, according to Lemma 20, we conclude that after executing Algorithm 3, there is only one 2E-block in GS0∪connector. Furthermore, according to the definition of a 2E-block, GS0∪connector is 2 edge-connected blocks. This implies that S1=S0∪connector (line 12) is a 2,2-ECDS of G. Note that VD⊆D and D⊆S0 (see while-loop (lines 8-14) and line 15 in Algorithm 2); thus, VD⊆S0. According to the for-loop (lines 13-17), it is easy to see that S1′ (line 18) is 2 edge-connected.
LetS∗⊆VD be the set of nodes deleted in the for-loop (lines 13-17); then, after Algorithm 3 is executed, S1′=S1−S∗ and S∗⊆VD⊆S1, which imply that V−S1′=S∗∪V−S1. Next, we prove that S1′ is a 2 edge-dominating set. Equivalently, we need to prove only that for u∈V−S1′, u is 2 edge-dominated by S1′. Note that S∗∩V−S1=∅; thus, u∈S∗ or u∈V−S1. Consider the following cases.Case 1.
u∈S∗. Since S∗⊆VD is an independent set and GS1=GS1′∪S∗ is 2 edge-connected, u is 2 edge-dominated by S1′, where S1′ is the S1′ obtained after the for-loop (lines 13-17) is executed.Case 2.
u∈V−S1. Note that V−S1=V−S1∪S∗⊆V−S0∪S∗ and that, according to Corollary 14, u is 2 edge-dominated by S0−S∗. On the other hand, since S0−S∗⊆S1−S∗=S1′, u is 2 edge-dominated by S1′.Overall,S1′ is a 2 edge-dominating set. Thus, S1′ (line 18) is a 2,2-ECDS of G.According to the above discussions, we obtain the following theorem.Theorem 21.
The output of Algorithm1 is a 2,2-ECDS of G.


## 4.2. Analysis of the Performance Ratio and Time Complexity

In the above subsection, we provided proof that a2,2-ECDS must be obtained by our algorithms. In this subsection, we prove that LLZ20 is an approximation algorithm and then present its performance ratio.In line 1 of Algorithm1, for a given graph G, we utilize ACC11 in [32] to construct a CDS in G. In this process, a CDS is calculated in 2 steps. In the first step, an MIS is obtained; in the second step, some nodes outside the MIS are added to the MIS such that it becomes a CDS SCDS. Das et al. [32] proved that the size of SCDS is no more than 6.78∗optG+8.12, where optG is the MCDS size in G.Lemma 22.
After executing line 2 in Algorithm1, ∣S0∣≤10.17∗optG+12.68, where optG is the MCDS size in G.Proof.
According to lines 7-14 of Algorithm2, D is an MIS in GB0. Since D⊆SMIS, ∣D∣≤∣SMIS∣, where SMIS is an MIS in G. According to [30], ∣SMIS∣≤3.39∗optG+4.56. Hence, ∣D∣≤3.39∗optG+4.56.
According to line 15 of Algorithm2, we obtain the following inequalities:
(1)∣S0∣≤∣SCDS∣+∣D∣≤6.78∗optG+8.12+3.39∗optG+4.56=10.17∗optG+12.68.Lemma 23.
After executing Algorithm3, ∣connector∣≤2∗∣S0∣−1.Proof.
Letm be the number of 2E-blocks in line 2 of Algorithm 3. Clearly, m≤∣S0∣. According to Lemma 20, the number of iterations of the while-loop (lines 3-11) in Algorithm 3 is no more than m−1. Note that in each iteration of the while-loop (lines 3-11), one or two new nodes are added to connector. Hence, ∣connector∣≤2∗m−1≤2∗∣S0∣−1.Theorem 24.
After executing line 3 in Algorithm1, ∣S1′∣≤30.51∗opt+36.04, where opt is the minimum 2,2-ECDS size in G.Proof.
LetoptG be the MCDS size in G; then, optG≤opt. According to Algorithm 3 and Lemmas 22 and 23, we have the following inequalities:
(2)∣S1′∣≤∣S1∣=∣S0∣+∣connector∣≤3∣S0∣−2≤30.51∗optG+36.04≤30.51∗opt+36.04.In the following paragraphs, we discuss the time complexity of LLZ20. The overall time cost of LLZ20 includes three components: (1) the time cost of computing a CDSSCDS by ACC11, (2) the time cost of computing a 2 edge-dominating CDS S0 by Algorithm 2, and (3) the time cost of constructing a 2,2-ECDS S1′ by Algorithm 3.Denote the number of nodes in a given inputG by n. In the first phase, according to [32], the time cost of constructing a CDS SCDS by ACC11 is On3.In the second phase, the time cost of calculating the setB0 of the nodes that have only one dominator in SCDS is On (the for-loop (lines 2-6)). Moreover, the time cost of finding an MIS in GB0 is On2 (the while-loop (lines 8-14)). Hence, the time cost of constructing a 2 edge-dominating CDS S0 by Algorithm 2 is On+n2=On2.In the third phase, since Algorithm4 is called to compute the 2E-blocks in the subgraph induced by the updated S0∪connector, the time complexity of Algorithm 4 must be analyzed. In Algorithm 4, the time cost of constructing a BFS tree T is On2. In the iterations of the for-loop (lines 2-28), the time cost of computing all 2E-blocks in GS based on T is On3. Hence, the time complexity of Algorithm 4 is On2+n3=On3. Now, we discuss the time cost of using Algorithm 3 to obtain the 2,2-ECDS S1′. In Algorithm 3, iteration of the while-loop (lines 3-11) is equal to On, and the overall behavior of line 2, line 6, and line 9 is similar. Each computes the 2E-blocks in the subgraph induced by the updated S0∪connector by calling Algorithm 4, which implies that all of their time costs are On3. Consequently, the time cost of adding LkS0∪connector paths to connect a 2 edge-dominating set S0 to form a 2,2-ECDS (while-loop (lines 3-11)) is On4. In addition, the time cost of deleting some redundant nodes from S1 (lines 13-17) is On4. Hence, in the third phase, the time complexity of constructing a 2,2-ECDS S1′ by Algorithm 3 is On3+n4+n4=On4.Overall, the time complexity of Algorithm1 is On3+n2+n4=On4.Theorem 25.
Suppose that the number of nodes in a given inputG is n; then, the time complexity of LLZ20 (Algorithm 1) is On4.


## 5. Simulation and Analysis

In the previous sections, we proposed an approximation algorithm LLZ20 to compute a2,2-ECDS, a new CDS with edge fault tolerance, in a given network graph. At the same time, we conducted a theoretical analysis of the performance ratio of LLZ20. In this section, we perform simulation experiments to evaluate the performance of our algorithm in terms of the size of the CDS, running time, and success rate and compare our algorithms with the existing related algorithms proposed by [25, 26]. In the rest of this section, we refer to the algorithm in [25] as SYWH08 and that in [26] as SZZW16. To objectively compare the performances of these three algorithms (LLZ20, SYWH08, and SZZW16), we utilize the algorithm proposed in [32], which, to the best of our knowledge, is the algorithm with the minimum performance ratio in terms of the size of the CDS, to generate a CDS. Notably, the authors of [26] proposed an algorithm to calculate a 2,m-CDS based on a known 1,m-CDS; however, they did not present a specific method to generate such a 1,m-CDS. In our simulation experiments, we use the algorithms proposed by [48] to calculate a 1,m-CDS based on a CDS obtained by [32]’s algorithm. The key parameters used in the simulations are listed in Table 1. In the simulation experiments, the employed hardware and software are an Intel Core i5 CPU 2.56 GHz, 16 GB DRAM, 64-bit Windows 10, and the Programming IDE is MATLAB.Table 1
Parameters and their values used in the simulations.
ParametersDefinitionsValuesnThe size of network[10, 250]rTransmission range of each node25 m or 35 mkData packet size256 bytesEelecEnergy dissipated in electronics for 1-bit transmission and reception50 nJ/bitEtrEnergy consumed in power amplifier in two-ray propagation model0.0013 pJ/bit/m4βRatio of energies consumed in reception and idle listening modes0.8E0Initial energy of each node1 JmNumber of packets per round10


### 5.1. Effects of the Number of Nodes

In the experimental setup, for convenience, we choose a virtual space with a100×100 experimental area. We let the transmission radius r of each node be 25 m and set the network size n to 10,20,30,40,⋯,250.First, we provide a brief introduction to the generation process of candidate networks. Considern nodes randomly distributed in the above virtual space. After a WSN has been determined, the program judges whether it is 2 connected: if yes, the network is chosen as a candidate network for the experiments; otherwise, it is abandoned. The procedure is repeated 100 times, and the candidate networks are saved. In the simulation experiment in this subsection, the chosen network graphs are 2 connected but not 2 edge-connected graphs. The main reasons for this selection are as follows. On the one hand, when the chosen network graph is a 2 connected graph, all three algorithms can generate a 2,2-ECDS; however, when the chosen network graph is a 2 edge-connected graph, only our algorithm can guarantee the generation of a 2,2-ECDS (SYWH08 and SZZW16 cannot). On the other hand, to objectively compare the performance of our algorithm with that of SYWH08 and SZZW16 in terms of CDS size and algorithm running time, the three algorithms should be able to generate a 2,2-ECDS in the same experimental environment.For each candidate network,G, LLZ20 (SYWH08 and SZZW16, respectively) is run to calculate a 2,2-ECDS, and the running time and resulting CDS size are recorded. These operations are repeated for all candidates, and the averages are calculated as the simulation result. Figures 9 and 10 exhibit the simulation results for LLZ20, SYWH08, and SZZW16 in terms of CDS size and algorithm running time, respectively.Figure 9
Comparison of LLZ20, SYWH08, and SZZW16 in terms of the CDS size.Figure 10
Comparison of LLZ20, SYWH08, and SZZW16 in terms of running time.Figure9 presents the relationship between the simulation curves for the 2,2-ECDS size of these three algorithms. The resulting 2,2-ECDS size increases as the network size increases for all three algorithms. This result is reasonable because the larger the network size is, the greater the number of nodes needed to dominate the network. Moreover, our algorithm (LLZ20) outperforms SYWH08 in terms of the CDS size, and the CDS size difference between LLZ20 and SYWH08 increases as the network size increases. This is because SYWH08 is designed for a 2,2-CDS, which is a 2,2-ECDS, while LLZ20 is specifically designed for a 2,2-ECDS. This difference may cause the number of nodes added to the 1,2-ECDS to form the resulting 2,2-ECDS in SYWH08 to be greater than that in LLZ20. According to Figure 10, the average running time of our algorithm is almost the same as that of SYWH08. Strictly speaking, the average running time of SYWH08 is slightly less than that of our algorithm. This slightly longer running time is tolerable because the performance of our algorithm is clearly better than that of SYWH08 in terms of CDS size, and the difference in average running time is within 5 s, even when the network size n is 250.Figure9 shows that the size of the 2,2-ECDS obtained by our algorithm is slightly larger than that obtained by SZZW16 for different network sizes. This result is acceptable for the following reasons. On the one hand, compared with SZZW16, our algorithm requires a shorter time to obtain the simulation results (see the discussion in the next paragraph). On the other hand, as mentioned in Introduction, some network graphs have an edge fault-tolerant CDS and do not contain any node fault-tolerant CDS. To guarantee that the simulation result of SZZW16 is obtained, 2-connected network graphs have to be chosen as the candidate networks for simulations in the simulation experiment. More specifically, compared with SZZW16, to guarantee that an expected CDS is obtained, our algorithm is designed to be suitable for a larger number of wireless networks; see the discussions regarding the next simulation for details. In addition, the difference between the size of the CDS obtained by our algorithm and that of the CDS obtained by SZZW16 is small (approximately 2).Next, we consider the simulation results shown in Figure10, which show that the performance of our algorithm is better than that of SZZW16 in terms of average running time.Figure10 shows that the average running time of our algorithm is less than that of SZZW16 and that the average running time of SZZW16 increases superlinearly with increasing network size, while the average running time of our algorithm increases slightly with increasing network size. When n≥150, the average running time of SZZW16 exceeds 570 s and is more than 57 times that of our algorithm. This result is reasonable. In fact, in the process of generating the 2,2-ECDS, to select some nodes to add to the 1,2-ECDS to form a 2,2-ECDS, SZZW16 needs to compute the potential function value of each node in the network to determine whether it can be selected, and the computation of the potential function value for a node is very complex. Therefore, this process has a high time cost. Consequently, it is natural that this time cost increases as the network size increases. However, in the process of selecting some nodes to add to a 1,2-ECDS to form a 2,2-ECDS, for a node outside the 1,2-ECDS, our algorithm only needs to make a simple comparison of the node neighbor information between this node and other nodes outside the 1,2-ECDS to determine whether it can be selected, which entails only a small time cost.On the basis of the above analysis, we can conclude that among SYWH08, SZZW16, and LLZ20, our algorithm is the most suitable algorithm to compute a2,2-ECDS in network graphs based on the comprehensive consideration of the CDS size and algorithm running time.


### 5.2. Effects of the Network Density

In this subsection, we present simulations carried out to investigate the effects of the network density to compare the performance of the three algorithms. Specifically, we investigate how a change in network density affects the CDS size for these three algorithms. To obtain simulation results showing how the CDS size changes as the network density changes, we fix the network size ton=250 and the node transmission radius to 25 m and vary the area from 40m×40m to 140m×140m. In this experiment, we randomly generate 100 candidate networks, which are 2-connected, in an area with the size varying as described. For each candidate network, we run each of the three algorithms to obtain a 2,2-ECDS and record the CDS size. For a given density, we repeat this operation for 100 candidate networks and take the average of the simulation results.Figure11 compares the performance of the three algorithms in terms of the CDS size. From Figure 11, it is easily found that the CDS size increases as the network area size increases; in other words, the CDS becomes larger as the network density decreases. This is reasonable because the sparser the network is, the fewer nodes are dominated by a node in the network. In additional, from Figure 11, we can see that LLZ20 outperforms SYWH08 for each area size (i.e., network density) and shows similar performance to SZZW16. Specifically, the CDS generated by LLZ20 is smaller than that generated by SYWH08 by at least 57, and the difference increases as the network density increases (when the network area size is 40m×40m, the difference is approximately 81). On the other hand, the size of the CDS obtained by LLZ20 is generally close to that obtained by SZZW16, and as the density increases, their difference decreases. In particular, when the network area size is 40m×40m, this difference is approximately 2. This is acceptable for a reason similar to that mentioned when discussing the above simulation results, namely, the time complexity of SZZW16 is far greater than that of our algorithm, LLZ20. In other words, LLZ20 outperforms SZZW16 on average.Figure 11
Comparison of LLZ20, SYWH08, and SZZW16 in different network density.


### 5.3. Comparison of the Success Rate

As mentioned in the beginning of Subsection4.1, in theory, for any given 2 edge-connected network graphs, our algorithm can always output a 2,2-ECDS, while SYWH08 and SZZW16 may fail. If an algorithm cannot output an expected 2,2-ECDS for the problem of finding the minimum 2,2-ECDS for a given 2 edge-connected network, the algorithm is useless for this problem. In other words, in a randomly generated 2 edge-connected network, for the problem of finding the minimum 2,2-ECDS, the probability that the considered algorithm successfully outputs a 2,2-ECDS is an important factor in evaluating its performance. We call this probability the success rate of the considered algorithm. In this subsection, we compare the performance of three algorithms (LLZ20, SYWH08, and SZZW16) in terms of the success rate by means of a simulation experiment. For convenience, Ts/Ta is utilized to denote the considered algorithm’s success rate, where Ta is the number of total experimental networks and Ts is the number of experimental networks in which a 2,2-ECDS is successfully output by the algorithm.In the experimental setup, we also select 100 candidates, where the selection process is similar to that in the above subsection, except for the condition used to determine whether a randomly generated network graph is a candidate. In this simulation, this condition is the following: “After such a WSN has been determined, the program judges whether it is 2 edge-connected; if yes, this network is chosen as a candidate network for experiments; otherwise, it is abandoned.”For each candidate networkG, we run LLZ20 to calculate a 2,2-ECDS and record whether a 2,2-ECDS can be output. After the results are obtained for 100 candidate networks, we calculate the success rate Ts/Ta, where Ta=100. We perform similar operations for SYWH08 and SZZW16 to obtain the corresponding success rates. The simulation results for these three algorithms are shown in Table 2.Table 2
The success rates in the case ofr=25.
Network size102030405060708090100SYWH0874%90%94%96%97%97%98%98%99%99%SZZW1674%90%94%96%97%97%98%98%99%99%LLZ20100%100%100%100%100%100%100%100%100%100%According to Table2, the success rate of our algorithm is 100% for all network sizes. This result is reasonable because in the theoretical analysis (Section 4), for any 2 edge-connected network graphs, we strictly prove that our algorithm must output a 2,2-ECDS. Table 2 also shows that the success rates of SYWH08 and SZZW16 are less than 100%, which is reasonable for the following reasons. On the one hand, when SYWH08 (SZZW16) runs in a network that is not 2 connected, it fails to generate a 2,2-2ECDS. On the other hand, the network graphs in the simulation experiments are 2 edge-connected but not necessarily 2 connected graphs (according to the definitions of a 2 edge-connected graph and 2 connected graph, a 2 connected graph must be a 2 edge-connected graph, but the inverse is not true). Moreover, Table 2 indicates that when the network size n decreases, the number of candidate networks in which SYWH08 and SZZW16 fail to output an expected 2,2-ECDS becomes larger. It is natural because when the network size n decreases or the number of nodes deployed randomly in a given area decreases, the density of the network becomes sparser, which increases the probability that cut nodes exist in the network. Consequently, the probability that this network graph is not a 2 connected graph increases.


### 5.4. Comparison of the Network Lifetime

In this subsection, we compare SYWH08, SZZW16, and LLZ20 in terms of the network lifetime. Note that for each of these algorithms, the first step requires the employment of other algorithms to generate a1,1-CDS. Therefore, to objectively compare the network lifetime performance of these three algorithms, we utilize the 1,1-CDS generated by the algorithm proposed in [49], which is an approximation algorithm with favorable performance in terms of the network lifetime, as the CDS generated in the first step. For the experimental setup, we choose a virtual space with a 100×100 experimental area. We let the transmission radius r of each node to be 25 m (or 35 m) and set the network size n to 10,20,30,40,⋯,150. Similar to Subsection 4.1, 100 candidate networks are generated for this simulation experiment.For convenience, we use the model proposed in [50] as the energy consumption model for our simulation. The energy consumption model mainly includes the following features: (1) the energy consumption for sending a packet is ETX=Eelec∗k+Etr∗k∗r4, (2) the energy consumption for receiving a packet is ERX=Eelec∗k, and (3) the energy consumption in the idle listening state is ERX=β∗Eelec∗k. The definitions of the notations Eelec, Etr, k, and β are given in Table 1. The energy consumption for constructing or reconstructing a CDS for these three algorithms is ignored.To measure the performance of an algorithmK in terms of the network lifetime, we need to introduce an index, called the number of rounds and denoted by RoundK, which is defined as follows. Based on the above energy consumption model, for the algorithm of interest, the following actions are considered to constitute one round: a sender s and receiver r are randomly selected, and s successfully sends m packets to r via the shortest path in the CDS generated by the algorithm under the condition that whole network contains no nodes with an energy of 0. To compute RoundK, some additional assumptions are needed, as follows: (1) the initial energy of every node in the network is 1 J; (2) all nodes in the CDS are in the idle listening state; (3) the nodes outside the CDS are in the sleeping state, so their energy consumption is ignored; (4) each packet is 256 bytes; (5) all nodes on this shortest path in the CDS (except s and r) both receive and transmit these m packets; (6) for each node on this shortest path in the CDS, its neighbors outside the shortest path only receive these m packets and do not forward them to their neighbors; and (7) a new CDS needs to be generated by the algorithm K once the residual energy of any node in the CDS is reduced to 50%.We take the average number ofrounds for 100 networks as the simulation result for each algorithm, and the simulation results are shown in Figure 12.Figure 12
Comparison of LLZ20, SYWH08, and SZZW16 in terms of network lifetime.
(a)
Transmission ranger=25(b)
Transmission ranger=35Figure12 shows that the performance of our algorithm LLZ20 is much better than that of SZZW16 or SYWH08 in terms of the network lifetime. Specifically, the number of rounds (network lifetime) under SZZW16 or SYWH08 is 360 fewer than that under LLZ20 for all network sizes. This result is reasonable because when a new CDS is constructed, LLZ20 uses the greedy strategy based on the remaining node energy to select the nodes to constitute its CDS, while both SZZW16 and SYWH08 use other strategies to select the nodes for their CDSs; this implies that compared with LLZ20, SZZW16 (or SYWH08) has a higher probability of selecting some nodes selected in previous rounds to perform message routing in the current round, which, in turn, implies that the number of rounds under LLZ20 may be greater than that under SZZW16 (SYWH08).Moreover, it can be observed that for LLZ20, the network lifetime increases as the network size increases. This is also reasonable. In the process of reconstructing a CDS via a greedy strategy based on energy, as the network size increases, the number of nodes with high residual energy available to form a CDS also increases. This means that compared with those in a smaller network, the new CDS nodes in a larger network will have higher residual energy after the same number of rounds. In contrast, from Figure12, we can see that for SZZW16 or SYWH08, the network lifetime changes little with increasing network size. This is easily understood. Because some of the nodes chosen to form a new CDS during CDS reconstruction are selected in ways other than an energy-based greedy strategy in these two algorithms, this implies that there is a higher probability that nodes selected in previous rounds will be selected for message routing in the current round. In other words, in these two algorithms, it is expected that some nodes will be repeatedly selected to form different CDSs regardless of the network size, and the residual energy of these nodes will heavily impacts the lifetime of the whole network.


## 5.1. Effects of the Number of Nodes

In the experimental setup, for convenience, we choose a virtual space with a100×100 experimental area. We let the transmission radius r of each node be 25 m and set the network size n to 10,20,30,40,⋯,250.First, we provide a brief introduction to the generation process of candidate networks. Considern nodes randomly distributed in the above virtual space. After a WSN has been determined, the program judges whether it is 2 connected: if yes, the network is chosen as a candidate network for the experiments; otherwise, it is abandoned. The procedure is repeated 100 times, and the candidate networks are saved. In the simulation experiment in this subsection, the chosen network graphs are 2 connected but not 2 edge-connected graphs. The main reasons for this selection are as follows. On the one hand, when the chosen network graph is a 2 connected graph, all three algorithms can generate a 2,2-ECDS; however, when the chosen network graph is a 2 edge-connected graph, only our algorithm can guarantee the generation of a 2,2-ECDS (SYWH08 and SZZW16 cannot). On the other hand, to objectively compare the performance of our algorithm with that of SYWH08 and SZZW16 in terms of CDS size and algorithm running time, the three algorithms should be able to generate a 2,2-ECDS in the same experimental environment.For each candidate network,G, LLZ20 (SYWH08 and SZZW16, respectively) is run to calculate a 2,2-ECDS, and the running time and resulting CDS size are recorded. These operations are repeated for all candidates, and the averages are calculated as the simulation result. Figures 9 and 10 exhibit the simulation results for LLZ20, SYWH08, and SZZW16 in terms of CDS size and algorithm running time, respectively.Figure 9
Comparison of LLZ20, SYWH08, and SZZW16 in terms of the CDS size.Figure 10
Comparison of LLZ20, SYWH08, and SZZW16 in terms of running time.Figure9 presents the relationship between the simulation curves for the 2,2-ECDS size of these three algorithms. The resulting 2,2-ECDS size increases as the network size increases for all three algorithms. This result is reasonable because the larger the network size is, the greater the number of nodes needed to dominate the network. Moreover, our algorithm (LLZ20) outperforms SYWH08 in terms of the CDS size, and the CDS size difference between LLZ20 and SYWH08 increases as the network size increases. This is because SYWH08 is designed for a 2,2-CDS, which is a 2,2-ECDS, while LLZ20 is specifically designed for a 2,2-ECDS. This difference may cause the number of nodes added to the 1,2-ECDS to form the resulting 2,2-ECDS in SYWH08 to be greater than that in LLZ20. According to Figure 10, the average running time of our algorithm is almost the same as that of SYWH08. Strictly speaking, the average running time of SYWH08 is slightly less than that of our algorithm. This slightly longer running time is tolerable because the performance of our algorithm is clearly better than that of SYWH08 in terms of CDS size, and the difference in average running time is within 5 s, even when the network size n is 250.Figure9 shows that the size of the 2,2-ECDS obtained by our algorithm is slightly larger than that obtained by SZZW16 for different network sizes. This result is acceptable for the following reasons. On the one hand, compared with SZZW16, our algorithm requires a shorter time to obtain the simulation results (see the discussion in the next paragraph). On the other hand, as mentioned in Introduction, some network graphs have an edge fault-tolerant CDS and do not contain any node fault-tolerant CDS. To guarantee that the simulation result of SZZW16 is obtained, 2-connected network graphs have to be chosen as the candidate networks for simulations in the simulation experiment. More specifically, compared with SZZW16, to guarantee that an expected CDS is obtained, our algorithm is designed to be suitable for a larger number of wireless networks; see the discussions regarding the next simulation for details. In addition, the difference between the size of the CDS obtained by our algorithm and that of the CDS obtained by SZZW16 is small (approximately 2).Next, we consider the simulation results shown in Figure10, which show that the performance of our algorithm is better than that of SZZW16 in terms of average running time.Figure10 shows that the average running time of our algorithm is less than that of SZZW16 and that the average running time of SZZW16 increases superlinearly with increasing network size, while the average running time of our algorithm increases slightly with increasing network size. When n≥150, the average running time of SZZW16 exceeds 570 s and is more than 57 times that of our algorithm. This result is reasonable. In fact, in the process of generating the 2,2-ECDS, to select some nodes to add to the 1,2-ECDS to form a 2,2-ECDS, SZZW16 needs to compute the potential function value of each node in the network to determine whether it can be selected, and the computation of the potential function value for a node is very complex. Therefore, this process has a high time cost. Consequently, it is natural that this time cost increases as the network size increases. However, in the process of selecting some nodes to add to a 1,2-ECDS to form a 2,2-ECDS, for a node outside the 1,2-ECDS, our algorithm only needs to make a simple comparison of the node neighbor information between this node and other nodes outside the 1,2-ECDS to determine whether it can be selected, which entails only a small time cost.On the basis of the above analysis, we can conclude that among SYWH08, SZZW16, and LLZ20, our algorithm is the most suitable algorithm to compute a2,2-ECDS in network graphs based on the comprehensive consideration of the CDS size and algorithm running time.


## 5.2. Effects of the Network Density

In this subsection, we present simulations carried out to investigate the effects of the network density to compare the performance of the three algorithms. Specifically, we investigate how a change in network density affects the CDS size for these three algorithms. To obtain simulation results showing how the CDS size changes as the network density changes, we fix the network size ton=250 and the node transmission radius to 25 m and vary the area from 40m×40m to 140m×140m. In this experiment, we randomly generate 100 candidate networks, which are 2-connected, in an area with the size varying as described. For each candidate network, we run each of the three algorithms to obtain a 2,2-ECDS and record the CDS size. For a given density, we repeat this operation for 100 candidate networks and take the average of the simulation results.Figure11 compares the performance of the three algorithms in terms of the CDS size. From Figure 11, it is easily found that the CDS size increases as the network area size increases; in other words, the CDS becomes larger as the network density decreases. This is reasonable because the sparser the network is, the fewer nodes are dominated by a node in the network. In additional, from Figure 11, we can see that LLZ20 outperforms SYWH08 for each area size (i.e., network density) and shows similar performance to SZZW16. Specifically, the CDS generated by LLZ20 is smaller than that generated by SYWH08 by at least 57, and the difference increases as the network density increases (when the network area size is 40m×40m, the difference is approximately 81). On the other hand, the size of the CDS obtained by LLZ20 is generally close to that obtained by SZZW16, and as the density increases, their difference decreases. In particular, when the network area size is 40m×40m, this difference is approximately 2. This is acceptable for a reason similar to that mentioned when discussing the above simulation results, namely, the time complexity of SZZW16 is far greater than that of our algorithm, LLZ20. In other words, LLZ20 outperforms SZZW16 on average.Figure 11
Comparison of LLZ20, SYWH08, and SZZW16 in different network density.


## 5.3. Comparison of the Success Rate

As mentioned in the beginning of Subsection4.1, in theory, for any given 2 edge-connected network graphs, our algorithm can always output a 2,2-ECDS, while SYWH08 and SZZW16 may fail. If an algorithm cannot output an expected 2,2-ECDS for the problem of finding the minimum 2,2-ECDS for a given 2 edge-connected network, the algorithm is useless for this problem. In other words, in a randomly generated 2 edge-connected network, for the problem of finding the minimum 2,2-ECDS, the probability that the considered algorithm successfully outputs a 2,2-ECDS is an important factor in evaluating its performance. We call this probability the success rate of the considered algorithm. In this subsection, we compare the performance of three algorithms (LLZ20, SYWH08, and SZZW16) in terms of the success rate by means of a simulation experiment. For convenience, Ts/Ta is utilized to denote the considered algorithm’s success rate, where Ta is the number of total experimental networks and Ts is the number of experimental networks in which a 2,2-ECDS is successfully output by the algorithm.In the experimental setup, we also select 100 candidates, where the selection process is similar to that in the above subsection, except for the condition used to determine whether a randomly generated network graph is a candidate. In this simulation, this condition is the following: “After such a WSN has been determined, the program judges whether it is 2 edge-connected; if yes, this network is chosen as a candidate network for experiments; otherwise, it is abandoned.”For each candidate networkG, we run LLZ20 to calculate a 2,2-ECDS and record whether a 2,2-ECDS can be output. After the results are obtained for 100 candidate networks, we calculate the success rate Ts/Ta, where Ta=100. We perform similar operations for SYWH08 and SZZW16 to obtain the corresponding success rates. The simulation results for these three algorithms are shown in Table 2.Table 2
The success rates in the case ofr=25.
Network size102030405060708090100SYWH0874%90%94%96%97%97%98%98%99%99%SZZW1674%90%94%96%97%97%98%98%99%99%LLZ20100%100%100%100%100%100%100%100%100%100%According to Table2, the success rate of our algorithm is 100% for all network sizes. This result is reasonable because in the theoretical analysis (Section 4), for any 2 edge-connected network graphs, we strictly prove that our algorithm must output a 2,2-ECDS. Table 2 also shows that the success rates of SYWH08 and SZZW16 are less than 100%, which is reasonable for the following reasons. On the one hand, when SYWH08 (SZZW16) runs in a network that is not 2 connected, it fails to generate a 2,2-2ECDS. On the other hand, the network graphs in the simulation experiments are 2 edge-connected but not necessarily 2 connected graphs (according to the definitions of a 2 edge-connected graph and 2 connected graph, a 2 connected graph must be a 2 edge-connected graph, but the inverse is not true). Moreover, Table 2 indicates that when the network size n decreases, the number of candidate networks in which SYWH08 and SZZW16 fail to output an expected 2,2-ECDS becomes larger. It is natural because when the network size n decreases or the number of nodes deployed randomly in a given area decreases, the density of the network becomes sparser, which increases the probability that cut nodes exist in the network. Consequently, the probability that this network graph is not a 2 connected graph increases.


## 5.4. Comparison of the Network Lifetime

In this subsection, we compare SYWH08, SZZW16, and LLZ20 in terms of the network lifetime. Note that for each of these algorithms, the first step requires the employment of other algorithms to generate a1,1-CDS. Therefore, to objectively compare the network lifetime performance of these three algorithms, we utilize the 1,1-CDS generated by the algorithm proposed in [49], which is an approximation algorithm with favorable performance in terms of the network lifetime, as the CDS generated in the first step. For the experimental setup, we choose a virtual space with a 100×100 experimental area. We let the transmission radius r of each node to be 25 m (or 35 m) and set the network size n to 10,20,30,40,⋯,150. Similar to Subsection 4.1, 100 candidate networks are generated for this simulation experiment.For convenience, we use the model proposed in [50] as the energy consumption model for our simulation. The energy consumption model mainly includes the following features: (1) the energy consumption for sending a packet is ETX=Eelec∗k+Etr∗k∗r4, (2) the energy consumption for receiving a packet is ERX=Eelec∗k, and (3) the energy consumption in the idle listening state is ERX=β∗Eelec∗k. The definitions of the notations Eelec, Etr, k, and β are given in Table 1. The energy consumption for constructing or reconstructing a CDS for these three algorithms is ignored.To measure the performance of an algorithmK in terms of the network lifetime, we need to introduce an index, called the number of rounds and denoted by RoundK, which is defined as follows. Based on the above energy consumption model, for the algorithm of interest, the following actions are considered to constitute one round: a sender s and receiver r are randomly selected, and s successfully sends m packets to r via the shortest path in the CDS generated by the algorithm under the condition that whole network contains no nodes with an energy of 0. To compute RoundK, some additional assumptions are needed, as follows: (1) the initial energy of every node in the network is 1 J; (2) all nodes in the CDS are in the idle listening state; (3) the nodes outside the CDS are in the sleeping state, so their energy consumption is ignored; (4) each packet is 256 bytes; (5) all nodes on this shortest path in the CDS (except s and r) both receive and transmit these m packets; (6) for each node on this shortest path in the CDS, its neighbors outside the shortest path only receive these m packets and do not forward them to their neighbors; and (7) a new CDS needs to be generated by the algorithm K once the residual energy of any node in the CDS is reduced to 50%.We take the average number ofrounds for 100 networks as the simulation result for each algorithm, and the simulation results are shown in Figure 12.Figure 12
Comparison of LLZ20, SYWH08, and SZZW16 in terms of network lifetime.
(a)
Transmission ranger=25(b)
Transmission ranger=35Figure12 shows that the performance of our algorithm LLZ20 is much better than that of SZZW16 or SYWH08 in terms of the network lifetime. Specifically, the number of rounds (network lifetime) under SZZW16 or SYWH08 is 360 fewer than that under LLZ20 for all network sizes. This result is reasonable because when a new CDS is constructed, LLZ20 uses the greedy strategy based on the remaining node energy to select the nodes to constitute its CDS, while both SZZW16 and SYWH08 use other strategies to select the nodes for their CDSs; this implies that compared with LLZ20, SZZW16 (or SYWH08) has a higher probability of selecting some nodes selected in previous rounds to perform message routing in the current round, which, in turn, implies that the number of rounds under LLZ20 may be greater than that under SZZW16 (SYWH08).Moreover, it can be observed that for LLZ20, the network lifetime increases as the network size increases. This is also reasonable. In the process of reconstructing a CDS via a greedy strategy based on energy, as the network size increases, the number of nodes with high residual energy available to form a CDS also increases. This means that compared with those in a smaller network, the new CDS nodes in a larger network will have higher residual energy after the same number of rounds. In contrast, from Figure12, we can see that for SZZW16 or SYWH08, the network lifetime changes little with increasing network size. This is easily understood. Because some of the nodes chosen to form a new CDS during CDS reconstruction are selected in ways other than an energy-based greedy strategy in these two algorithms, this implies that there is a higher probability that nodes selected in previous rounds will be selected for message routing in the current round. In other words, in these two algorithms, it is expected that some nodes will be repeatedly selected to form different CDSs regardless of the network size, and the residual energy of these nodes will heavily impacts the lifetime of the whole network.


## 6. Conclusion

In this paper, to address the problem of the edge fault tolerance of VBs in WSNs, we introduced the concept of the2,2-ECDS, a kind of CDS with edge fault tolerance, and proposed an effective algorithm for computing a 2,2-ECDS in a 2 edge-connected network graph. The proposed algorithm is proven to be an approximation algorithm with a performance ratio of 30.51. By means of simulations, we compared the performance of our algorithm with that of existing related algorithms in terms of CDS size, algorithm running time, and algorithm success rate; the simulation results show that our algorithm is more suitable than the existing related algorithms for constructing a CDS with edge tolerance. In recent years, how to improve the energy efficiency of networks has been investigated in several studies [39, 51]. In our future work, we will investigate the construction of VBs by considering edge fault tolerance and energy efficiency in heterogeneous WSNs and develop new algorithms for constructing k,m-ECDSs for any k and m with m≥k≥2 in homogeneous WSNs.



---

*Source: 5977781-2021-12-08.xml*