# The Construction of a Virtual Backbone with a Bounded Diameter in a Wireless Network

Authors: Jiarong Liang; Meng Yi; Yanyan Li; Xinyu Liang
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

We usually use a digraph to represent a wireless network (WN). Correspondingly, a connected dominating set (CDS) of the digraph is usually used to denote a virtual backbone (VB) of the corresponding WN. In this article, focusing on the problem of a minimum strongly connected dominating and absorbing set (MSCDAS) with a bounded diameter (or guaranteed routing cost) for a digraph, which is strongly connected, we introduce two algorithms. One is called the guaranteed routing cost strongly connected dominating and absorbing set (GOC-SCDAS), which can generate a strongly connected dominating and absorbing set (SCDAS) with a performance ratio14.4k+1/22 in respect of the optimal solution. Another is called the α guaranteed routing cost strongly connected bidirectional dominating and absorbing set (α-GOC-SCBDAS), which can generate a strongly connected bidirectional dominating and absorbing set (SCBDAS) with a performance ratio 8.8443k+1/22k+1/22 in respect of the optimal solution and a better routing cost, where k=rmax/rmin and rmin,rmax is the transmission range of nodes in the network. Through the simulation experiments, we obtain the conclusion that in terms of the diameter and average routing path length (ARPL) of CDS, the outputs of our algorithms are better than those of the algorithm in (Du et al. 2006).


---

## Body

## 1. Introduction

Owing to the development of wireless radio communication and very-large-scale technology, WNs such as wireless sensor networks (WSNs) or ad hoc WNs have begun to be widely applied in a lot of fields. For example, in WSNs, since the sensors can be randomly deployed to the expected destination area, WSNs have been successfully applied to numerous fields such as disaster rescue, sea surveillance, climate prediction, bridge health detection, and traffic control [1–7]. However, since there is no predefined infrastructure for facilities with a fixed setup, it is necessary to design a VB for the renewal of network topology and the performance of routing-related tasks [8]. The advantages of a VB established in a network are as follows: when the routing-related tasks are performed to find routing paths, it is enough to search the space of the VB rather than the whole network, which implies that it takes a shorter time for searching routing paths and needs a smaller size of routing table, and then, it causes that the routing maintenance becomes simpler. For constructing VBs in WNs, there are many different methods; particularly, in order to obtain a VB with a better performance, one prefers to find a CDS in a graph, which is modeled a WN containing the VB.When a VB in a WN is being constructed, the VB size is needed to be considered for the reason that a smaller VB causes less communication overhead. And then, it is a natural idea to construct a minimum VB in a given WN when people hope to reduce the communication overhead of the network. If a connected graphG is used to model the WN, then the problem of constructing a minimum VB in the WN is equal to the problem of finding an MCDS in the corresponding connected graph $G$. However, the MCDS problem for a connected graph has been proved to be an NP-hard problem [9]. Therefore, most researchers in this area concentrate on how to find smaller CDSs.It is worth mentioning that [10] is the first paper to introduce the approximation algorithms computing an MCDS in a unit disk graph (UDG), which is utilized to model a WN with the same transmission radius (or range) for each node. Most of previous researches on the MCDS problem have focused on UDGs [11–14]. These studies all aimed to obtain a smaller CDS to make the best of the existence of a minimum VB.However, in some WNs, say a WSN, since there are differences of the functionalities and control technologies for connectivity, the powers of these sensors may differ. According to the different requirements on different measured frequencies in collision, a node may be required to change its transmission range. Therefore, for such situations, it is more significant to study a WN with multiple heterogeneous transmission radiuses (ranges) than the one with coincident transmission radius.Moreover, in some WNs, the energy of the wireless nodes is limited and thus will affect the network lifetime. In other words, the question of how to efficiently use the energy of the wireless nodes is an important issue that the designers of such WNs must consider. Some unnecessary information transmissions can be avoided by choosing an efficient routing method, which can save much energy and extend the life of a network. Hence, when we construct an MCDS for a graph, it is necessary to consider the routing cost in the MCDS. Some research results on the MCDS problem considering the routing cost for a UDG have been obtained in [15–19].A digraph is strongly connected if and only if for any two vertexesx and y in the digraph, there exists a directed path from x to y in the digraph. For a strongly connected directed graph (SCDG), denoted by G=V,E, a subset S⊆V is called a dominating and absorbing set (DAS) if the following two conditions hold: (1) for any node x∈V−S, there exists a node y∈S such that y,x∈E; (2) for any node x∈V−S, there exists a node y∈S such that . A DAS is said to be an SCDAS if it induces a strongly connected subgraph. An MSCDAS is an SCDAS that has the minimum number of nodes. Figure 1(a) shows a sample MSCDAS in a directed graph where all red nodes {1, 2, 3} form an MSCDAS and are called the dominators. All the nodes that have a directed edge from some dominators are called dominatees. In Figure 1(b), all red nodes {1, 3, 10, 12} make an SCDAS. The MSCDAS problem of G is the problem of how to solve an MSCDAS of G.Figure 1
(a) An example of MSCDAS. (b) An example of SCDAS.
(a)(b)In this paper, for an SCDG, denoted byG=V,E, which models a WN with nodes’ transmission radiuses in the range rmin,rmax, we consider the problem of constructing MSCDAS of the SCDG. Our main works are as follows:
(1)
We propose a centralized algorithm, called by GOC-SCDAS, which produces an SCDASS with S≤14.4k+1/22opt+22.2k+1/22−5 such that for any two vertexes x and y of G, the length of the smallest routing path between them in S is dSx,y≤3DiamOPT+7, where k=rmax/rmin, OPT is an MSCDAS of G, opt=OPT and DiamOPT denote the diameter of OPT(2)
We propose another algorithm, called byα-GOC-SCBDAS, which produces an SCBDAS S with S⩽8.8443k+1/22k+1/22opt+13.6353k+1/22k+1/22 such that for any x,y∈V, dSx,y≤7dx,y, where opt denotes the cardinality of an MSCDAS of G, k=rmax/rminThe following is the rest of the article. The related work is introduced in Section2. The problem statement is formulated in Section 3. Section 4 presents two algorithms for constructing a VB from two different perspectives based on a directed graph model. Our simulation results are in Section 5. Our conclusion is in Section 6.


## 2. Related Work

In the study of a WN, for the sake of convenience, we usually use a graph to denote a WN and a CDS of the graph to model the corresponding VB for that WN. So far, the research on CDSs has received widespread attention. [20] pointed out the computation of the MCDS was an NP-hard problem for a general graph and even for a UDG [9]. Thus, most studies simply find CDSs with a reasonable approximation ratio. Based on the UDG model, [10] firstly introduced an algorithm for computing the MCDS of a UDG. In [10], using two approximation algorithms, which are polynomial-time, Guha and Kuller obtained two CDSs with performance radio 2FΔ+2 and FΔ+2, respectively, where Δ=maxdegv∣v∈V, Fx=1+1/2+⋯+1/x. During the process of constructing a sufficiently small CDS, the computation of the upper bound on the maximal independent set (MIS) is one uneasy work. In [21], Wan et al. obtained a result that the cardinality of each MIS does not exceed 4optMCDS+1. Later, people further improve this bound [19, 22–25]. [24] presented an upper bound of MIS 3.4306optMCDS+4.8185, which is the best bound on the cardinality of MIS in a UDG. However, most of previous studies have ignored the importance of the routing overhead. We know that when we obtain an MCDS, the shortest paths in such an MCDS-based VB may be unavailable. Currently, there are a few papers that have constructed a CDS with a bounded routing path length, whose size is slightly larger than the size of MCDS [26–31]. In order to obtain a CDS in a UDG, Kim et al. designed an algorithm, called by CDS-BD-D, which generates a CDS with a bounded diameter [29]. [17] presented an algorithm and presented a CDS D with the bound 4432/3optMCDS+2012/3 by the algorithm. Further, in [26], they proved that for two nodes x and y in UDG, there is a path with inner nodes in D from x to y such that its length does not exceed 5dx,y. In [27], Ding et al. defined a new concept, called by α-minimum routing cost CDS (α-MOC-CDS), where α≥2. Let GV,E be a graph, S be a CDS; S is called a α-MOC-CDS if the CDS has the property that dSp,q−1≤αdp,q−1 (pand q are any two nodes inG). For the sake of convenience, they turned the α-MOC-CDS problem into another equivalent problem, called by α-2hop-DS problem. The authors pointed out that α-2hop-DS α≥2 is also NP-hard [27] when NP⊈DTIMEnOloglogn. In [30], a centralized algorithm, called by GOC-MCDS-C, was proposed by Du et al. At the same time, they presented the corresponding distributed algorithm and pointed out the GOC-MCDS problem is still NP-hard when NP⊈DTIMEnOloglogn. They claimed that these algorithms produced a CDS S with S≤148optMCDS+208 and dSx,y≤7dx,y (x and y are any two nodes). It should be noted that the CDS’s cardinality is fairly large. For UBGs and quasi-UDGs, Wu et al. considered the similar problem to α-MOC-CDS; the details can be found in [31]. However, in the above studies, none of them investigate the problem of SCDAS with a guaranteed routing cost for an SCDG. Possibly because of different amounts of remaining electricity or the implementation of energy-saving devices on some nodes, the different nodes in a network may have different transmission ranges. For the case of nodes with different transmission ranges, there are two papers to discuss the problem of SCDAS for nonuniform networks (see [32, 33]), but they did not concern the routing cost in the corresponding graph. In [34], Liu et al. extended the conclusion in [30] to heterogeneous WSNs, and they formulated the α-MOC-SCBDS problem. In order to solve the α-MOC-SCBDS problem, they proposed a centralized algorithm and a corresponding distributed algorithm. They claimed that these α-MOC-SCBDS algorithms produced a strongly connected bidirectional dominating set (SCBDS) S with ∣S∣⩽38ρ+122ρ+12/2opt, where ρ=rmax/rmin. However, the authors of [34] did not consider the guaranteed routing cost for an SCDG with heterogeneous transmission ranges; in this case, the proof procedure for the upper bound of 38ρ+122ρ+12/2opt in [34] may be incorrect.


## 3. Preliminaries

In this article, we focus on the MSCDAS problem with a guaranteed routing cost in a WN. Letrmin(rmax) denote the minimum (maximum) transmission range of nodes in the network and xy denote the Euclidean distance between x and y. We use a digraph G=V,E to denote a WN with heterogeneous transmission ranges and rv to denote the transmission range of node v∈V, where V is the node set in the network and E is an edge set including all directed links in the network such that x,y∈E if and only if xy≤rx. Then, for x,y∈V, xy≤minrx,ry if and only if x,y∈E and y,x∈E. Suppose that digraph G=V,E is strongly connected. We use dx,y to represent the number of hops of the shortest directed path from node x to node y in G. For L⊆V, let PLx,y denote the shortest directed routing path from x to y, whose all inner nodes belong to L, and GL denote the subgraph induced by L. If for any two nodes p,q∈L, GL has a directed path from p toq, then GL is said to be strongly connected. If p,q∈E, then node p is called an in-neighbor node of q, at the same time, q is called an out-neighbor node of p. For D⊆V and node x∈V, let N+x=y∈V∣x,y∈E, N+D=∪x∈DN+x−D, and ξx=N+x. We use WG:ξx,IDx⟶R to denote a weight function, where x∈V is a node and IDx is the ID of node x. For two given 2-tuple variables ξx1,IDx1 and ξx2,IDx2, WGξx1,IDx1>WGξx2,IDx2 if and only if one of the following conditions is true:
(1)
ξx1>ξx2 or(2)
ξx1=ξx2,IDx1>IDx2Definition 1.
LetG=V,E be an SCDG, S⊆V, then S is an independent set (IS) if and only if for each pair of nodes p,q∈S, p,q∉E, or q,p∉E. S is called an MIS if S is an IS and for any p∈V−S, S∪p is not an IS.Definition 2.
LetG=V,E be an SCDG, S⊆V, then S is called a bidirectional dominating and absorbing set (BDAS) if for x∈V−S, S has at least one node y∈S such that x is simultaneously dominated and absorbed by y. A BDAS S of G is called an independent bidirectional dominating and absorbing set (IBDAS) if for two nodes x,y∈S, x,y∉E, or y,x∉E. An IBDAS S is called a maximal independent bidirectional dominating and absorbing set (MIBDAS) if for any x∈V−S, S∪x is not an IBDAS.Definition 3.
LetG=V,E be an SCDG, S⊆V. Then, S is called an SCBDAS with a guaranteed routing cost α (α≥1) if the following conditions hold:
(a)
S is a BDAS(b)
S is strongly connected(c)
dSp,q≤αdp,q, where p,q∈VDefinition 4.
LetG=V,E represent a connected digraph. For p,q∈V, let Pp,q represent a shortest path from p to q and Pp,q represent the length of Pp,q. Then, DiamG=maxPp,qp,q∈V is called the diameter of G.Definition 5.
LetG=V,E be an SCDG, r∈V, T be a breadth-first search (BFS) tree with root node r, and x,y∈V. In the BFS T, if y∈N+x and dr,y=dr,x+1, then x is called y′s parent and y is called x′s child.Definition 6.
LetG=V,E be an SCDG, x,y,r∈V, and T be a BFS tree with root node r. In the BFS T, if there exists a node z∈V satisfying x,y∈N+z and dr,y=dr,x, then x is called a brother node of y.Lemma 7.
Suppose thatG=V,E is an SCDG and D is a DAS of G. If for two nodes p,q∈V, dDp,q≤αdp,q, where α≥1 is a constant, then D is an SCDAS of G.Proof.
SinceG is an SCDG and p,q∈V, we always have a path from p to q, and dp,q<∞. According to the assumption, it holds that dDp,q≤αdp,q<∞, which means that there exists a path for transmitting a message from node p to node q via nodes in D. Hence, Dis an SCDAS of G.Lemma 8.
Suppose thatG=V,E is an SCDG and D is an MIS of G, then D is also a DAS of G.Proof.
According to the assumption thatD is an MIS of G, we have that D must be a dominating set. Next, we show that D must be an absorbing set of G. In contrast, suppose that V−D has a node, say x, such that for any node y∈D, y,x∉E, which implies that F=D∪y is an IS of G, a contradiction.
LetH denote a disk with center w and radius h≥1. Then, the number of independent nodes in H does not exceed the maximum number of circles of radius 0.5 that can be packed into the disk with center w and radius h+0.5. Since regular hexagons, each circumscribing a circle of radius 0.5, can densely fill in a given disk, these circles can be replaced with their corresponding circumscribed regular hexagons to compute the bound of the size of MIS in H (see [1]).Lemma 9.
LetH be an MIS in a UDG G=V,E, x∈V, Lt is a subset of H such that each node of it is covered by the disk with center x and radius t>0, then Lt≤3.685t+0.52.Proof.
Assume thatD is the disk with center x and radius t+0.5, SD denotes the area of D, and S0.5 denotes the area of a circle of radius 0.5, and Srh denotes the area of a regular hexagon circumscribing a circle of radius 0.5. Then,
(1)SD=πt+0.52,S0.5=π0.52,Srh=32.
According to the above discussion, it holds thatLt≤SD/S0.5=πt+0.52/π0.52=2t+12. To get a better bound on Lt, we use the area of a regular hexagon circumscribing a circle of radius 0.5 in place of the area of a circle of radius 0.5. Note that for a hexagon circumscribing such a circle near the boundary of D, not all of its area may be used. For example, in Figure 2, the part of the hexagon circumscribing circle C with center v, lies outside of D. The area of the part lying outside of D is no more than
(2)Srh−S0.56.
Hence, we have(3)∣Lt∣⩽SDSrh−Srh−S0.5/6⩽3.685t+0.52.Figure 2
The densest possible packing of the disk.


## 4. Algorithm Description

It has been proven in [35] that in a disk graph, it is impossible to obtain a polynomial-time ρlnδ-approximation 0<p<1 algorithm for α-MOC-CDS unless NP⊆DTIMEnOloglogn. Note that a directed disk graph is a special disk graph, this implies that finding an α-MOC-CDS in a directed disk graph is also NP-hard unless NP⊆DTIMEnOloglogn. In this section, we propose two algorithms for constructing a VB with guaranteed routing cost in a WN with heterogeneous transmission ranges.


### 4.1. Centralized Algorithm GOC-SCDAS

In this section, we present an SCDAS construction algorithm (called by GOC-SCDAS) for an SCDGG=V,E. Traditional CDS construction algorithms often consist of two steps. The first step is to find an MIS D. The second step is to add some nodes to D to form a CDS. Our basic idea on the centralized algorithm GOC-SCDAS can be summarized into three steps. During the first step, we choose a node r∈V as a root node by using a leader selection strategy [2]. In the second step, we build a BFS tree and then construct a dominating set Sd of G=V,E such that for every node x∈V, there is one path from r to x. In the last step, we construct another digraph G¯=V,E¯, where E¯=x,y∣y,x∈E. Using a method similar to that applied in the second step, we can obtain a dominating set of G¯, denoted by Sa, which is an absorbing set of G. Then, the union of Sd and Sa, denoted by S, is an SCDAS of G. In order to understand the concept of BFS tree in the algorithm, we give an example about the resulting BFS tree for a directed graph as follows: Figure 3 is an SCDG G=V,E with 15 nodes, Figure 4(a) shows a BFS tree with root node v7 using a leader selection strategy for G, and Figure 4(b) is a BFS tree with root node v7 for the corresponding graph G¯=V,E¯. Figure 5 is the flowchart of GOC-SCDAS.Algorithm 1: GOC-SCDAS.
Input: An SCDG G=V,EOutput: An SCDAS S1 select a noder∈V as a root node through a leader selection algorithm.2Sd=RoottreeV,E,r.3 construct a new digraphG¯=V,E¯, where E¯=p,q∣p,q∈V,q,p∈E.4Sa=RoottreeV,E¯,r.5S=Sd∪Sa.6 returnS.7 subroutineRoottreeV,E,r.8 color all nodes inV white, and let W=V denote all white nodes.9 construct a BFS treeT1 of G rooted at r by searching out-neighbors of each node.10 colorr black and each node in N+r gray.11W=V−r∪N+r.12 letdr,x represent the shortest path length from r to x in the BFS tree T1.13 letLk=x∈V∣dr,x=k, and kmax be the maximum value of k.14forallevenkdo15 find a dominating setDk of Gk using a greedy algorithm based on the weight function WGk, where Gk denotes the subgraph induced by Vk.16end17D=∪evenkDk.18 color the nodes inD black, color the nodes in N+D gray.19W=W−D∪N+D.20R=D.21whileW=ϕdo22 find a nodex in W, color it black, and color all nodes in N+x∩W gray.23R=R∪x.24W=W−N+x.25end26H=R.27 letp=kmax/2.28forq=1 to pdo29foreachnodex∈V2q∩Rdo30  suppose thaty is the parent of x with the largest WG2q−1ξy,IDy.31  suppose thatz is the parent of y with the largest WG2q−2ξz,IDz.32  colory and z black.33H=H∪y,z.34end35foreachnodex∈V2q−1∩Rdo36if there is not one black node in x′s parent nodes then37   choose onex′s parent node w with the largest WG2q−2ξw,IDw and color w black.38H=H∪w.39end40end41end42returnHLemma 10.
The node setH produced by the subroutine Roottree is a dominating set (DS) of G.Proof.
Note that the input graphG=V,E is an SCDG. From Line 20, Line 22, Line 26, Line 33, and Line 38 in the subroutine Roottree, we conclude that H contains all black nodes in G at the end of the subroutine Roottree. After Line 40, if x∈V−H, then x is gray or white. Note that after the loop in Line 21 to Line 25, there are no white nodes in G, which implies that x is gray. From Line 10, Line 18 and Line 22, we can get that there exists one black node y with x∈N+y. Hence, H is a dominating set.Lemma 11.
The node setRproduced by the subroutineRoottreeis an IS.Proof.
In contrast, suppose thatR is not an IS; then, there exist two black nodes x,y∈R with x,y∈Eand y,x∈E. Suppose that x is colored earlier than y. Consider the following situations.Case 1.
dr,x=dr,y. This means that x and y are at the same level in the BFS tree in G. According to Line 14~Line 20 in the subroutine Roottree, it can be found that x is colored black and subsequently node y is colored gray; consequently, y∈Ris gray, which is a contradiction.Case 2.
dr,x≠dr,y. This means that node x must be y′ parent node and that y is x′ child node. According to Line 21 ~ Line 25 in the subroutine Roottree, it can be found that x and y are subsequently colored black and gray, respectively; consequently, y∈R is gray, which is a contradiction.Theorem 12.
The setS output by GOC-SCDAS is an SCDAS in G=V,E.Proof.
According to Lemma10, Sd and Sa are a dominating set of G and a dominating set of G¯, respectively. Since G¯ is obtained by reversing all edges in G, Sa is an absorbing set of G, which implies that S=Sd∪Sa is a DAS of G. We claim that for any node w∈Sd, there exists one path, denoted by Prw, fromrtowin GSd. Suppose that w∈Vk,0≤k≤kmax. Next, in order to prove above claim, we use the induction on k. When k=0 or 1, the result is trivial. Suppose that k≥2 and that the result is true for 0,1,⋯,k−1. If k is even 2i, then according to Lines 29~34, there exists a parent node of w, denoted by w′∈Vk−1, such that w′∈Sd. According to the hypothesis, we have that there exists one path Prw′ from r to w′. Hence, Prw′∪w′⟶w is a path from r to w in GSd, and then, the result is true. If k is odd 2i−1, then according to Line 35~40, there exists a parent node of w, denoted by w′∈V2i−2=Vk−1, such that w′∈Sd. According to the hypothesis, we have that there exists one path Prw′ from r to w′. Hence, the result is true.Figure 3
A strongly connected directed graphG=V,Ewith 15 nodes.Figure 4
(a) A BFS tree forG=V,E. (b) A BFS tree for G¯=V,E¯.
(a)(b)Figure 5
The flowchart of Algorithm1.Similarly, the following claim is true: forw∈Sa, there exists one path from rto w in G¯Sa, which is equivalent to the claim that for w∈Sa, there exists one path from w to r in GSa.Now, we show thatGS is strongly connected. We need only to prove that for any x,y∈V, there exist two paths between x and y; one of them is from x to y, denoted by Pxy, and another is from y to x, denoted by Pyx. Consider the following situations:Case 1.
x,y∈Sd∩Sa. From the above discussion, we have that there is a path Prx from r to x and a path Pyr from yto r. Then, Pyr∪Prx is a path from yto x. Similarly, there exists a path from x to y.Case 2.
x,y∈Sd−Sa. Therefore, there is a path Prxfrom r to x. Since Sa is an absorbing set, there is a node z∈Sa with y,z∈E. On the other hand, according to the above discussion, there exists a path Pzr from z to r. Hence, y⟶z∪Pzr∪Prx is a path from y to x. A similar argument proves there exists a path from x to y.Case 3.
x,y∈Sa−Sd. An argument similar to that for Case 2 can be used here.Case 4.
x∈Sd−Sa,y∈Sd∩Sa. According to the above discussion, there exists a path Pyr from y to r and another path Prx from r to x, and thus, Pyr∪Prx is a path from yto x. Since x∈Sd−Sa and Sa is an absorbing set of G, there is node z∈Sa with z,x∈E. Therefore, there exists a path Pzr fromz to r. On the other hand, since y∈Sd, there exists a path Pry from r to y. Hence, x⟶z∪Pzr∪Pry is a path from x to y.Case 5.
x∈Sa−Sd,y∈Sd∩Sa. An argument similar to that for Case 4 can be used here.Case 6.
x∈Sd−Sa,y∈Sa−Sd. According to the above discussion, there exist a path Pyr from y to r and another path Prx from r to x, implying that Pyr∪Prx is a path from yto x. On the other hand, since SaSd is an absorbing set (a dominating set), there is one nodex′∈Say′∈Sd with x,x′∈Ey′,y∈E. A similar argument can be used to prove there is one path Px′y′ from x′ to y′. Hence, it is obtained one path from x to y:x⟶x′∪Px′y′∪y′⟶y.The following lemma follows [30].Lemma 13.
The length of the path from noder to each black node in Lkis at most Hk hops, where
(4)Hi=32i−12,i∈1,3,5,⋯;32i−1,i∈2,4,6,⋯.Lemma 14 [36].
Assume thatG=V,E is a digraph with the transmission rangermin,rmax, S is an IS, then S≤2.4k+1/22opt+3.7k+1/22, where k=rmax/rmin.Theorem 15.
LetS be the SCDAS obtained by GOC-SCDAS. Then, S≤14.4k+1/22opt+22.2k+1/22−5. For any two nodes p,q∈V, let PSp,q represent the shortest routing path between p and q, which includes only nodes in S except for p and q, dSp,q be the length of PSp,q; then, dSp,q≤3DiamOPT+7, where OPT is any one optimal SCDAS of G.Proof.
LetRd (Ra) denote the R produced by RoottreeV,E,r (RoottreeV,E¯,r), and let kd (ka) denote the kmax produced by RoottreeV,E,r (RoottreeV,E¯,r). According to GOC-SCDAS, we need only to add at most 2Rd−1 additional nodes to Rd such that all nodes in Rd can be connected to form a forward tree with root node r. Then, S⩽Sd∪Sa⩽Sd+Sa−1⩽3Rd−2+3Ra−2−1=3Rd+Ra−5. According to Lemma 11 and Lemma 13, it holds that Rd≤2.4k+1/22opt+3.7k+1/22 and Ra≤2.4k+1/22opt+3.7k+1/22. Hence, S⩽14.4k+1/22opt+22.2k+1/22−5.
On the other hand, it is obvious thatDiamG≥maxkd,ka. For any two nodesx,y∈V, let px,y be a path from x to y, px,y denote the length of px,y. Suppose that Lp,q is the longest shortest path a node p to q in G, then DiamG=Lp,q. Let Q represent an optimal solution on the SCDAS problem for G. Then, there exist two paths as follows: Pp,q is the shortest path from p to q that includes only nodes in Q except for pand q, and P′p,q is the shortest path from q to p that includes only nodes in Qexcept for p and. Let dQp,q=minPp,q,P′p,q. Then, the diameter DiamOPT of the subgraph induced by Q is no less than dQp,q−2. It is obvious that. Hence, DiamOPT≥dQp,q−2≥DiamG−2≥maxkd,ka−2. According to Lemma 13, for any pair of nodes pand q of G, we have the following inequalities:
(5)dSp,q≤DiamGS+2≤32kd−12+32ka−12+2≤3maxkd,ka+1≤3DiamOPT+7


### 4.2. Algorithm for constructing an SCBDAS

Assume thatG=V,E is an SCDG. In this section, one algorithm will be proposed for constructing an SCBDAS of G, which is a special case of an SCDAS of G. This algorithm includes two stages. Firstly, a BDAS D of G will be constructed by us. Next, we will add some nodes to D to form an SCBDAS. The details can be found in Algorithm 2.The following lemma follows [35].Lemma 16.
Assume thatG=V,E is an SCDG, S is an SCBDAS of G. If for any two nodes x,y∈V with dx,y=2, dSx,y≤α+1. Then, the following condition holds dSx,y≤αdx,y, where α≥1 and x,y∈V.Now, we introduce theα-GOC-SCBDAS algorithm. For the convenience of understanding this α-GOC-SCBDAS algorithm, we present its flowchart (see Figure 6).Algorithm 2:α-GOC-SCBDAS.
Input: An SCDG G=V,EOutput: An SCBDAS1 color all nodes inV white.2 use a leader selection algorithm to select a noder∈V to be a root node, and color r black and all nodes inNr=N+r∩N−rgray.3 build a BFS treeT1 of G with root r by searching out-neighbors of each node.4D=r, S=ϕ, andC=ϕ.5X=V−Nr∪r.6 letLk=x∈∣dr,x=k, and setkmax=maxk.7for every even kdo8 determine one MIBDASDkof Gkby using a greedy algorithm based on the weight functionWGk, where Gk is the subgraph induced by Vk.D=∪evenkDk.9end10 setNu=N+u∩N−u, color the nodes in ND=∪u∈DNu gray and the nodes in Dblack.11X=X−ND∪D.12whileX=ϕ} do13 find a nodex with the maximum weight function W in X, color it black, and color each node of Nx gray.D=D∪xX=X−Nx14end15 for each pair of nodesp,q∈D with dp,q⩽3, add each node in the shortest path from p to q toC.16S=C∪D.17returnS.Lemma 17.
For the digraphG=V,E with transmission ranges rmin,rmax, suppose that D is the BDAS produced by Algorithm 2. Then, the following conditions are true:
(1)
D is an IS, and(2)
for each ,I≤3.6853k+1/22, where I=v∣v∈D,0<du,v⩽3 andk=rmax/rminProof.
(1)
From Line 8, we know thatDk is an MIBDAS of Gk, which implies that ∪evenkDk is an IS of G (see Line 9). From Line 14 to Line 15, we find that for any x∈X, D∪x is still an IS of G. Hence, after the loop in Lines 13~17, D is still an IS(2)
For each nodeu∈D, let Cu be the circle of center u and radius (3rmax+1/2rmin) and Cu be the circle of center u and radius1/2rmin. From Line 7 to Line 17, we find that D is an IS, which implies that for any two nodes in D, say u and v, distu,v>rmin. It is easily seen that for any two nodes p,q∈D, if p and q are contained inCu, then Cp and Cq are disjoint and are covered byCu. Hence, the cardinality of I does not exceed the number of circles with radius 1/2rmin that are disjoint to each other and are contained in Cu. Since the densest possible packing of disks in a plane is attained with a hexagonal lattice [37], it is expectable that the area of a hexagon circumscribing a circle with radius 1/2rmin can be used to replace that of the circle to compute a upper bound of the number of independent nodes covered by Cu. According to Lemma 3.3, we can obtain the process of computing the upper bound on I as follows:
The area ofCu is
(6)SCu=π3rmax+12rmin2.
The area of a hexagon circumscribing a circle with radius1/2rmin is
(7)32rmin2.
Note that the part of a hexagon circumscribing a circle near the boundary may lie outsideCu (similar to the circle with center at v in Figure 2); however, the area of this part does not exceed
(8)1632rmin2−rmin22π.
Therefore, there is an upper bound of∣I∣:
(9)∣I∣⩽π3rmax+1/2rmin23/2rmin2−1/63/2rmin2−rmin/22π⩽π3rmax+1/2rmin2π+103/24rmin2⩽3.6853k+122Theorem 18.
For an SCDGG=V,E, let S be the set produced by Algorithm 2. Then, the following conditions are true:
(1)
S is an SCBDAS in G(2)
Forx,y∈V, it holds that dsx,y≤7dx,y(3)
S≤8.8443k+1/22k+1/22opt+13.6353k+1/22k+1/22,where k=rmax/rminProof.
(1)
SinceS=C∪D and D is a BDAS in G, S is a BDAS in G. Now, we will show that S is strongly connected. We need only to prove that for x,y∈S, there is a path from x to y and each node in the path belongs to S. Since G=V,E is an SCDG, there exists the shortest path P1x,y=x⟶x1⟶x2⋯⟶xk⟶y from x to y, where xi∈V1≤i≤k. Let xi be the first node of P1x,y in the direction from x to y that does not belong to S; then, there is a node x¯i+1∈S such that xi+1∈N+x¯i+1∩N−x¯i+1 and dxi−1,x¯i+1⩽3. Letqi=xi−1⟶xi1⋯⟶xil⟶x¯i+1 be the shortest path from xi−1 to x¯i+1. From Line 18 and Line 19 of Algorithm 2, we know that all nodes in qi are in S. Thus, P2x,y=x⟶x1⟶⋯⟶xi−2⟶qi⟶xi+1⟶⋯⟶y is one path from x to y. By repeating the above process, one path from x to y, whose each node belongs to S, can ultimately be obtained(2)
Suppose thatx,y∈V are a pair of nodes such that dx,y=2. Thus, there exists one node z∈N+x∩N−y. Since D is a BDAS, there exist nodes x′,y′,z′∈D such that x′∈N+x∩N−x,y′∈N+y∩N−y, and z′∈N+z∩N−z (see Figure 7). Therefore, dx′,z′≤dx′,x+dx,z+dz,z′≤3, and dz′,y′≤dz′,z+dz,y+dy,y′≤3. From Algorithm 2, we find that dSx′,z′≤3 and dSz′,y′≤3. Hence, dSx′,y′≤dSx′,z′+dSz′,y′≤6, and thus, dSx,y≤dSx′,y′+2≤8. According Lemma 16, we find that for any two distinct nodes x and y, dSx,y≤7dx,y(3)
Suppose thatD is a subset of nodes produced by Algorithm 2 and E′=x,y∣x,y∈D,0<dx,y≤s3. Consider the graph L=D,E′. According to Lemma 17, the degree of each node in L does not exceed 3.6853k+1/22−1, which implies that L contains at most 1/23.6853k+1/22−1D edges. Note that in Line 18 of Algorithm 2, each edge p,q of L with dp,q≤3 contributes at most two nodes outside D to C. Hence, C≤3.6853k+1/22−1D. According to Lemma 4.4, D≤2.4k+1/2opt+3.7k+1/22
From Line 19 of Algorithm2, we obtain the following inequalities:
(10)S≤C+D≤3.6853k+122−1D+D=3.6853k+122D≤8.8443k+122k+12opt+13.6353k+122k+122Remark 19.
There are two differences between GOC-SCDAS (Algorithm1) and α-GOC-SCBDAS (Algorithm 2). The first difference is in terms of the algorithm process, GOC-SCDAS computes an SCDAS by taking the union of two sets Sd and Sa, where Sd, a connected dominating set of G, is obtained by calling subroutine RottreeV,E,r and where Sa, a connected absorbing set of G, is obtained by calling subroutineRottreeV,E¯,r. While α-GOC-SCBDAS computes an SCBDAS by two steps, the first step is to compute an IS D that is a BDAS; the second step is to add some nodes into D such that it becomes an SCBDAS. The second difference is in terms of output result; the result output by GOC-SCDAS is an SCDAS while the result output by α-GOC-SCBDAS is an SCBDAS and they are two subsets of V that have different properties. According to Theorem 15 and Theorem 18, we can find that the performance ratio of GOC-SCDAS is better than that of α-GOC-SCBDAS, which is the advantage of GOC-SCDAS. However, the result output by α-GOC-SCBDAS is a CDS that guarantees the routing cost, while the CDS output by GOC-SCDAS does not have such a property, which is an outstanding advantage of α-GOC-SCBDAS.Figure 6
The flowchart of Algorithm2.Figure 7
Illustration of three pairs of nodes for the proof of Theorem18.


## 4.1. Centralized Algorithm GOC-SCDAS

In this section, we present an SCDAS construction algorithm (called by GOC-SCDAS) for an SCDGG=V,E. Traditional CDS construction algorithms often consist of two steps. The first step is to find an MIS D. The second step is to add some nodes to D to form a CDS. Our basic idea on the centralized algorithm GOC-SCDAS can be summarized into three steps. During the first step, we choose a node r∈V as a root node by using a leader selection strategy [2]. In the second step, we build a BFS tree and then construct a dominating set Sd of G=V,E such that for every node x∈V, there is one path from r to x. In the last step, we construct another digraph G¯=V,E¯, where E¯=x,y∣y,x∈E. Using a method similar to that applied in the second step, we can obtain a dominating set of G¯, denoted by Sa, which is an absorbing set of G. Then, the union of Sd and Sa, denoted by S, is an SCDAS of G. In order to understand the concept of BFS tree in the algorithm, we give an example about the resulting BFS tree for a directed graph as follows: Figure 3 is an SCDG G=V,E with 15 nodes, Figure 4(a) shows a BFS tree with root node v7 using a leader selection strategy for G, and Figure 4(b) is a BFS tree with root node v7 for the corresponding graph G¯=V,E¯. Figure 5 is the flowchart of GOC-SCDAS.Algorithm 1: GOC-SCDAS.
Input: An SCDG G=V,EOutput: An SCDAS S1 select a noder∈V as a root node through a leader selection algorithm.2Sd=RoottreeV,E,r.3 construct a new digraphG¯=V,E¯, where E¯=p,q∣p,q∈V,q,p∈E.4Sa=RoottreeV,E¯,r.5S=Sd∪Sa.6 returnS.7 subroutineRoottreeV,E,r.8 color all nodes inV white, and let W=V denote all white nodes.9 construct a BFS treeT1 of G rooted at r by searching out-neighbors of each node.10 colorr black and each node in N+r gray.11W=V−r∪N+r.12 letdr,x represent the shortest path length from r to x in the BFS tree T1.13 letLk=x∈V∣dr,x=k, and kmax be the maximum value of k.14forallevenkdo15 find a dominating setDk of Gk using a greedy algorithm based on the weight function WGk, where Gk denotes the subgraph induced by Vk.16end17D=∪evenkDk.18 color the nodes inD black, color the nodes in N+D gray.19W=W−D∪N+D.20R=D.21whileW=ϕdo22 find a nodex in W, color it black, and color all nodes in N+x∩W gray.23R=R∪x.24W=W−N+x.25end26H=R.27 letp=kmax/2.28forq=1 to pdo29foreachnodex∈V2q∩Rdo30  suppose thaty is the parent of x with the largest WG2q−1ξy,IDy.31  suppose thatz is the parent of y with the largest WG2q−2ξz,IDz.32  colory and z black.33H=H∪y,z.34end35foreachnodex∈V2q−1∩Rdo36if there is not one black node in x′s parent nodes then37   choose onex′s parent node w with the largest WG2q−2ξw,IDw and color w black.38H=H∪w.39end40end41end42returnHLemma 10.
The node setH produced by the subroutine Roottree is a dominating set (DS) of G.Proof.
Note that the input graphG=V,E is an SCDG. From Line 20, Line 22, Line 26, Line 33, and Line 38 in the subroutine Roottree, we conclude that H contains all black nodes in G at the end of the subroutine Roottree. After Line 40, if x∈V−H, then x is gray or white. Note that after the loop in Line 21 to Line 25, there are no white nodes in G, which implies that x is gray. From Line 10, Line 18 and Line 22, we can get that there exists one black node y with x∈N+y. Hence, H is a dominating set.Lemma 11.
The node setRproduced by the subroutineRoottreeis an IS.Proof.
In contrast, suppose thatR is not an IS; then, there exist two black nodes x,y∈R with x,y∈Eand y,x∈E. Suppose that x is colored earlier than y. Consider the following situations.Case 1.
dr,x=dr,y. This means that x and y are at the same level in the BFS tree in G. According to Line 14~Line 20 in the subroutine Roottree, it can be found that x is colored black and subsequently node y is colored gray; consequently, y∈Ris gray, which is a contradiction.Case 2.
dr,x≠dr,y. This means that node x must be y′ parent node and that y is x′ child node. According to Line 21 ~ Line 25 in the subroutine Roottree, it can be found that x and y are subsequently colored black and gray, respectively; consequently, y∈R is gray, which is a contradiction.Theorem 12.
The setS output by GOC-SCDAS is an SCDAS in G=V,E.Proof.
According to Lemma10, Sd and Sa are a dominating set of G and a dominating set of G¯, respectively. Since G¯ is obtained by reversing all edges in G, Sa is an absorbing set of G, which implies that S=Sd∪Sa is a DAS of G. We claim that for any node w∈Sd, there exists one path, denoted by Prw, fromrtowin GSd. Suppose that w∈Vk,0≤k≤kmax. Next, in order to prove above claim, we use the induction on k. When k=0 or 1, the result is trivial. Suppose that k≥2 and that the result is true for 0,1,⋯,k−1. If k is even 2i, then according to Lines 29~34, there exists a parent node of w, denoted by w′∈Vk−1, such that w′∈Sd. According to the hypothesis, we have that there exists one path Prw′ from r to w′. Hence, Prw′∪w′⟶w is a path from r to w in GSd, and then, the result is true. If k is odd 2i−1, then according to Line 35~40, there exists a parent node of w, denoted by w′∈V2i−2=Vk−1, such that w′∈Sd. According to the hypothesis, we have that there exists one path Prw′ from r to w′. Hence, the result is true.Figure 3
A strongly connected directed graphG=V,Ewith 15 nodes.Figure 4
(a) A BFS tree forG=V,E. (b) A BFS tree for G¯=V,E¯.
(a)(b)Figure 5
The flowchart of Algorithm1.Similarly, the following claim is true: forw∈Sa, there exists one path from rto w in G¯Sa, which is equivalent to the claim that for w∈Sa, there exists one path from w to r in GSa.Now, we show thatGS is strongly connected. We need only to prove that for any x,y∈V, there exist two paths between x and y; one of them is from x to y, denoted by Pxy, and another is from y to x, denoted by Pyx. Consider the following situations:Case 1.
x,y∈Sd∩Sa. From the above discussion, we have that there is a path Prx from r to x and a path Pyr from yto r. Then, Pyr∪Prx is a path from yto x. Similarly, there exists a path from x to y.Case 2.
x,y∈Sd−Sa. Therefore, there is a path Prxfrom r to x. Since Sa is an absorbing set, there is a node z∈Sa with y,z∈E. On the other hand, according to the above discussion, there exists a path Pzr from z to r. Hence, y⟶z∪Pzr∪Prx is a path from y to x. A similar argument proves there exists a path from x to y.Case 3.
x,y∈Sa−Sd. An argument similar to that for Case 2 can be used here.Case 4.
x∈Sd−Sa,y∈Sd∩Sa. According to the above discussion, there exists a path Pyr from y to r and another path Prx from r to x, and thus, Pyr∪Prx is a path from yto x. Since x∈Sd−Sa and Sa is an absorbing set of G, there is node z∈Sa with z,x∈E. Therefore, there exists a path Pzr fromz to r. On the other hand, since y∈Sd, there exists a path Pry from r to y. Hence, x⟶z∪Pzr∪Pry is a path from x to y.Case 5.
x∈Sa−Sd,y∈Sd∩Sa. An argument similar to that for Case 4 can be used here.Case 6.
x∈Sd−Sa,y∈Sa−Sd. According to the above discussion, there exist a path Pyr from y to r and another path Prx from r to x, implying that Pyr∪Prx is a path from yto x. On the other hand, since SaSd is an absorbing set (a dominating set), there is one nodex′∈Say′∈Sd with x,x′∈Ey′,y∈E. A similar argument can be used to prove there is one path Px′y′ from x′ to y′. Hence, it is obtained one path from x to y:x⟶x′∪Px′y′∪y′⟶y.The following lemma follows [30].Lemma 13.
The length of the path from noder to each black node in Lkis at most Hk hops, where
(4)Hi=32i−12,i∈1,3,5,⋯;32i−1,i∈2,4,6,⋯.Lemma 14 [36].
Assume thatG=V,E is a digraph with the transmission rangermin,rmax, S is an IS, then S≤2.4k+1/22opt+3.7k+1/22, where k=rmax/rmin.Theorem 15.
LetS be the SCDAS obtained by GOC-SCDAS. Then, S≤14.4k+1/22opt+22.2k+1/22−5. For any two nodes p,q∈V, let PSp,q represent the shortest routing path between p and q, which includes only nodes in S except for p and q, dSp,q be the length of PSp,q; then, dSp,q≤3DiamOPT+7, where OPT is any one optimal SCDAS of G.Proof.
LetRd (Ra) denote the R produced by RoottreeV,E,r (RoottreeV,E¯,r), and let kd (ka) denote the kmax produced by RoottreeV,E,r (RoottreeV,E¯,r). According to GOC-SCDAS, we need only to add at most 2Rd−1 additional nodes to Rd such that all nodes in Rd can be connected to form a forward tree with root node r. Then, S⩽Sd∪Sa⩽Sd+Sa−1⩽3Rd−2+3Ra−2−1=3Rd+Ra−5. According to Lemma 11 and Lemma 13, it holds that Rd≤2.4k+1/22opt+3.7k+1/22 and Ra≤2.4k+1/22opt+3.7k+1/22. Hence, S⩽14.4k+1/22opt+22.2k+1/22−5.
On the other hand, it is obvious thatDiamG≥maxkd,ka. For any two nodesx,y∈V, let px,y be a path from x to y, px,y denote the length of px,y. Suppose that Lp,q is the longest shortest path a node p to q in G, then DiamG=Lp,q. Let Q represent an optimal solution on the SCDAS problem for G. Then, there exist two paths as follows: Pp,q is the shortest path from p to q that includes only nodes in Q except for pand q, and P′p,q is the shortest path from q to p that includes only nodes in Qexcept for p and. Let dQp,q=minPp,q,P′p,q. Then, the diameter DiamOPT of the subgraph induced by Q is no less than dQp,q−2. It is obvious that. Hence, DiamOPT≥dQp,q−2≥DiamG−2≥maxkd,ka−2. According to Lemma 13, for any pair of nodes pand q of G, we have the following inequalities:
(5)dSp,q≤DiamGS+2≤32kd−12+32ka−12+2≤3maxkd,ka+1≤3DiamOPT+7


## 4.2. Algorithm for constructing an SCBDAS

Assume thatG=V,E is an SCDG. In this section, one algorithm will be proposed for constructing an SCBDAS of G, which is a special case of an SCDAS of G. This algorithm includes two stages. Firstly, a BDAS D of G will be constructed by us. Next, we will add some nodes to D to form an SCBDAS. The details can be found in Algorithm 2.The following lemma follows [35].Lemma 16.
Assume thatG=V,E is an SCDG, S is an SCBDAS of G. If for any two nodes x,y∈V with dx,y=2, dSx,y≤α+1. Then, the following condition holds dSx,y≤αdx,y, where α≥1 and x,y∈V.Now, we introduce theα-GOC-SCBDAS algorithm. For the convenience of understanding this α-GOC-SCBDAS algorithm, we present its flowchart (see Figure 6).Algorithm 2:α-GOC-SCBDAS.
Input: An SCDG G=V,EOutput: An SCBDAS1 color all nodes inV white.2 use a leader selection algorithm to select a noder∈V to be a root node, and color r black and all nodes inNr=N+r∩N−rgray.3 build a BFS treeT1 of G with root r by searching out-neighbors of each node.4D=r, S=ϕ, andC=ϕ.5X=V−Nr∪r.6 letLk=x∈∣dr,x=k, and setkmax=maxk.7for every even kdo8 determine one MIBDASDkof Gkby using a greedy algorithm based on the weight functionWGk, where Gk is the subgraph induced by Vk.D=∪evenkDk.9end10 setNu=N+u∩N−u, color the nodes in ND=∪u∈DNu gray and the nodes in Dblack.11X=X−ND∪D.12whileX=ϕ} do13 find a nodex with the maximum weight function W in X, color it black, and color each node of Nx gray.D=D∪xX=X−Nx14end15 for each pair of nodesp,q∈D with dp,q⩽3, add each node in the shortest path from p to q toC.16S=C∪D.17returnS.Lemma 17.
For the digraphG=V,E with transmission ranges rmin,rmax, suppose that D is the BDAS produced by Algorithm 2. Then, the following conditions are true:
(1)
D is an IS, and(2)
for each ,I≤3.6853k+1/22, where I=v∣v∈D,0<du,v⩽3 andk=rmax/rminProof.
(1)
From Line 8, we know thatDk is an MIBDAS of Gk, which implies that ∪evenkDk is an IS of G (see Line 9). From Line 14 to Line 15, we find that for any x∈X, D∪x is still an IS of G. Hence, after the loop in Lines 13~17, D is still an IS(2)
For each nodeu∈D, let Cu be the circle of center u and radius (3rmax+1/2rmin) and Cu be the circle of center u and radius1/2rmin. From Line 7 to Line 17, we find that D is an IS, which implies that for any two nodes in D, say u and v, distu,v>rmin. It is easily seen that for any two nodes p,q∈D, if p and q are contained inCu, then Cp and Cq are disjoint and are covered byCu. Hence, the cardinality of I does not exceed the number of circles with radius 1/2rmin that are disjoint to each other and are contained in Cu. Since the densest possible packing of disks in a plane is attained with a hexagonal lattice [37], it is expectable that the area of a hexagon circumscribing a circle with radius 1/2rmin can be used to replace that of the circle to compute a upper bound of the number of independent nodes covered by Cu. According to Lemma 3.3, we can obtain the process of computing the upper bound on I as follows:
The area ofCu is
(6)SCu=π3rmax+12rmin2.
The area of a hexagon circumscribing a circle with radius1/2rmin is
(7)32rmin2.
Note that the part of a hexagon circumscribing a circle near the boundary may lie outsideCu (similar to the circle with center at v in Figure 2); however, the area of this part does not exceed
(8)1632rmin2−rmin22π.
Therefore, there is an upper bound of∣I∣:
(9)∣I∣⩽π3rmax+1/2rmin23/2rmin2−1/63/2rmin2−rmin/22π⩽π3rmax+1/2rmin2π+103/24rmin2⩽3.6853k+122Theorem 18.
For an SCDGG=V,E, let S be the set produced by Algorithm 2. Then, the following conditions are true:
(1)
S is an SCBDAS in G(2)
Forx,y∈V, it holds that dsx,y≤7dx,y(3)
S≤8.8443k+1/22k+1/22opt+13.6353k+1/22k+1/22,where k=rmax/rminProof.
(1)
SinceS=C∪D and D is a BDAS in G, S is a BDAS in G. Now, we will show that S is strongly connected. We need only to prove that for x,y∈S, there is a path from x to y and each node in the path belongs to S. Since G=V,E is an SCDG, there exists the shortest path P1x,y=x⟶x1⟶x2⋯⟶xk⟶y from x to y, where xi∈V1≤i≤k. Let xi be the first node of P1x,y in the direction from x to y that does not belong to S; then, there is a node x¯i+1∈S such that xi+1∈N+x¯i+1∩N−x¯i+1 and dxi−1,x¯i+1⩽3. Letqi=xi−1⟶xi1⋯⟶xil⟶x¯i+1 be the shortest path from xi−1 to x¯i+1. From Line 18 and Line 19 of Algorithm 2, we know that all nodes in qi are in S. Thus, P2x,y=x⟶x1⟶⋯⟶xi−2⟶qi⟶xi+1⟶⋯⟶y is one path from x to y. By repeating the above process, one path from x to y, whose each node belongs to S, can ultimately be obtained(2)
Suppose thatx,y∈V are a pair of nodes such that dx,y=2. Thus, there exists one node z∈N+x∩N−y. Since D is a BDAS, there exist nodes x′,y′,z′∈D such that x′∈N+x∩N−x,y′∈N+y∩N−y, and z′∈N+z∩N−z (see Figure 7). Therefore, dx′,z′≤dx′,x+dx,z+dz,z′≤3, and dz′,y′≤dz′,z+dz,y+dy,y′≤3. From Algorithm 2, we find that dSx′,z′≤3 and dSz′,y′≤3. Hence, dSx′,y′≤dSx′,z′+dSz′,y′≤6, and thus, dSx,y≤dSx′,y′+2≤8. According Lemma 16, we find that for any two distinct nodes x and y, dSx,y≤7dx,y(3)
Suppose thatD is a subset of nodes produced by Algorithm 2 and E′=x,y∣x,y∈D,0<dx,y≤s3. Consider the graph L=D,E′. According to Lemma 17, the degree of each node in L does not exceed 3.6853k+1/22−1, which implies that L contains at most 1/23.6853k+1/22−1D edges. Note that in Line 18 of Algorithm 2, each edge p,q of L with dp,q≤3 contributes at most two nodes outside D to C. Hence, C≤3.6853k+1/22−1D. According to Lemma 4.4, D≤2.4k+1/2opt+3.7k+1/22
From Line 19 of Algorithm2, we obtain the following inequalities:
(10)S≤C+D≤3.6853k+122−1D+D=3.6853k+122D≤8.8443k+122k+12opt+13.6353k+122k+122Remark 19.
There are two differences between GOC-SCDAS (Algorithm1) and α-GOC-SCBDAS (Algorithm 2). The first difference is in terms of the algorithm process, GOC-SCDAS computes an SCDAS by taking the union of two sets Sd and Sa, where Sd, a connected dominating set of G, is obtained by calling subroutine RottreeV,E,r and where Sa, a connected absorbing set of G, is obtained by calling subroutineRottreeV,E¯,r. While α-GOC-SCBDAS computes an SCBDAS by two steps, the first step is to compute an IS D that is a BDAS; the second step is to add some nodes into D such that it becomes an SCBDAS. The second difference is in terms of output result; the result output by GOC-SCDAS is an SCDAS while the result output by α-GOC-SCBDAS is an SCBDAS and they are two subsets of V that have different properties. According to Theorem 15 and Theorem 18, we can find that the performance ratio of GOC-SCDAS is better than that of α-GOC-SCBDAS, which is the advantage of GOC-SCDAS. However, the result output by α-GOC-SCBDAS is a CDS that guarantees the routing cost, while the CDS output by GOC-SCDAS does not have such a property, which is an outstanding advantage of α-GOC-SCBDAS.Figure 6
The flowchart of Algorithm2.Figure 7
Illustration of three pairs of nodes for the proof of Theorem18.


## 5. Simulation and Analysis

To obtain simulation results, we first built a virtual space. This virtual space is a 2-dimensional space with dimensions of100×100. In this virtual area, we considered two types of system parameters: the number of nodes, which we varied between 10 and 100 in increments of 10 and the proportion of rmax and rmin, where rmax,rmin is the transmission ranges of nodes (for the sake of convenience to do experiments, rminis fixed to be 25). After a network had been produced, we checked if it was strongly connected. If not, we renounced such a network. Otherwise, it was regarded as a candidate for testing. By repeating this procedure, we obtained 100 network candidates for each performance measure, based on which, we took the average value at each point as the simulation results. Next, we would evaluate the performances of Algorithm 1 (GOC-SCDAS) and Algorithm 2 (α-GOC-SCBDAS) according to the size of CDS, the ARPL of CDS, and the diameter of CDS by making a comparison with the work in [32]. From now on, we call it CDS-BFS.It is necessary to introduce the concept of ARPL for an SCDG. Assume thatG=V,Eis an SCDG and D is an SCDAS in G, HDx,y is the hop number of the shortest path from x to y (x,y∈D), and C∣D∣2 is the number of all the possible pair of nodes in D. Then, ∑x,y∈DHDx,y/2C∣D∣2 is called the ARPL of D. Similarly, the ARPL of G is ∑x,y∈GHGx,y/2C∣G∣2.The simulation results are described in the following, where the results in Figure8-Figure 9 are obtained under the network size setting, and those in Figure 10–12 are obtained under the setting of proportion of rmax and rmin.Figure 8
The comparison of the size of CDS generated by these three algorithms under network size setting.Figure 9
The comparison of the diameter of CDS generated by these three algorithms under network size setting.Figure 10
The comparison of the size of CDS generated by these three algorithms under the setting of proportion ofrmax and rmin.Figure 11
The comparison of ARPL of CDS generated by these three algorithms under the setting of proportion ofrmax and rmin.Figure 12
The comparison of the diameter of CDS generated by these three algorithms under the setting of the proportion ofrmax and rmin.In Figure8, we present the performances of GOC-SCDAS, α-GOC-SCBDAS, and CDS-BFS according to the CDS size under the network size setting. It is easily seen that, as the number of nodes in the network increases, the number of nodes in the CDS increases for GOC-SCDAS, α-GOC-SCBDAS and CDS-BFS, respectively. It is natural since a bigger CDS is needed to dominate more nodes outside CDS. More specifically, for GOC-SCDAS, when the size of the network n changes in the range [8, 27], the number of nodes in CDS chosen by GOC-SCDAS is more than 58% of the total number of nodes n in the network. When n=80,110,130, the number of nodes in CDS chosen by GOC-SCDAS is approximately 34%, 32%, and 30%, of n. For CDS-BFS, when the size of the network n changes in the range [8, 27], the number of nodes in CDS chosen by CDS-BFS is more than 51% of the total number of nodes n in the network. When n=80,110,130, the number of nodes in CDS chosen by CDS-BFS is approximately 30%, 28%, and 26% of n. For α-GOC-SCBDAS, when the size of the network n changes in the range [8, 27], the number of nodes in CDS generated by α-GOC-SCBDAS is more than 70% of the total number of nodes n in the network. When n=80,110,130, the number of nodes in SCDAS generated by α-GOC-SCBDAS is approximately 65%, 62%, and 60% of n. Note that the size of CDS chosen by GOC-SCDAS is slightly bigger than that chosen by CDS-BFS. This is acceptable because GOC-SCDAS can achieve to guarantee a bounded diameter by loosening the size requirement of CDS. In addition, we can also find that the size of CDS chosen by α-GOC-SCBDAS is slightly bigger than that chosen by GOC-SCDAS. This is actually expected for the reason that the CDS generated by α-GOC-SCBDAS can guarantee routing cost, which is the first priority, while the CDS size is the second priority in our paper.The results shown in Figure13 are the tendency of the ARPL of CDS for all considered algorithms under the network size setting. It is well-known the fact that the shorter the resulting ARPL, the better the corresponding algorithm. As can be seen, at the beginning, when n=10, the ARPL of CDS for GOC-SCDAS, α-GOC-SCBDAS, and CDS-BFS is 2.11, 2.06, and 1.88, respectively, which implies that the performance of CDS generated by CDS-BFS is slightly better than that of CDS generated by the one in GOC-SCDAS and α-GOC-SCBDAS in terms of ARPL. However, when n, the network size, is greater than or equal to 20, the ARPL of CDS for all algorithms is decreasing as the number of nodes in the network is increasing. At the same time, the simulation results in Figure 13 show that when n is greater than or equal to 20, the resulting ARPL for α-GOC-SCBDAS is shorter than that for GOC-SCDAS while the ARPL for GOC-SCDAS is shorter than that for CDS-BFS. In other words, the simulation results indicate that under the network size setting, α-GOC-SCBDAS achieves successfully its goal as its performance is better than that of both of GOC-SCDAS and CDS-BFS in terms of ARPL, which can be used to depict the feature of routing cost of CDS. These findings further demonstrate that our approach can reduce effectively the routing cost in a WN.Figure 13
The comparison of ARPL of CDS generated by these three algorithms under network size setting.The results shown in Figure9 are the tendency of the diameter of CDS for all considered algorithms under the network size setting. Note that in a WN, the probability of message transmission failure often increases when a message is sent through a longer path, which implies that the diameter of CDS is an important factor to measure the quality of CDS. At the beginning, when n=10, the diameter of CDS for GOC-SCDAS, α-GOC-SCBDAS, and CDS-BFS is 4.34, 4.19, and 4.09, respectively, which implies that at the beginning the performance of CDS generated by CDS-BFS is slightly better than that of CDS generated by GOC-SCDAS and α-GOC-SCBDAS in terms of diameter. However, when n is greater than or equal to 20, the diameter of CDS for all algorithms decreases as the number of nodes in the network increases. At the same time, as these curves in Figure 9 show, when n is greater than or equal to 20, the resulting diameter for α-GOC-SCBDAS is smaller than that for GOC-SCDAS while the diameter for GOC-SCDAS is smaller than that for CDS-BFS. This further indicates that the performance of our algorithms is better than that of CDS-BFS in terms of diameter (n≥20).The following three simulation results are produced by all three algorithms under the setting of proportionρ∈rmax/rmin, where rmin is fixed to be 25 and the network size n is fixed to be 100 for the sake of convenience. According to the simulation curves in Figure 10, we can find that as ρ increases, the size of CDS decreases for all three algorithms under study. It is reasonable because when ρ increases, the number of nodes dominated by a node in a CDS may become larger, which causes the smaller CDS to be needed to dominate more nodes outside the CDS. More specifically, when ρ=1.25, the number of nodes in CDS chosen by α-GOC-SCBDAS, GOC-SCDAS, and CDS-BFS is approximately 79, 32, and 29, respectively. When ρ=1.6, the number of nodes in CDS chosen by α-GOC-SCBDAS, GOC-SCDAS, and CDS-BFS is approximately 63, 30, and 26, respectively. When ρ=2, the number of nodes in CDS chosen by α-GOC-SCBDAS, GOC-SCDAS, and CDS-BFS is approximately 51, 28, and 25, respectively. Therefore, in terms of CDS size, the performance of CDS-BFS is better slightly than that of GOC-SCDAS, which is better than that of α-GOC-SCBDAS. As mentioned previously (the discussion of Figure 8), this is acceptable for the reason that CDS-BFS is only aimed at a small CDS while GOC-SCDAS and α-GOC-SCBDAS are aimed at a small CDS with a bound diameter and guaranteed routing cost, respectively.In Figure11, we can observe that the ARPL of CDS obtained by these considered algorithms decreases as ρ increases. In addition, it can be found that when ρ=1.2,2, the ARPL of CDS for α-GOC-SCBDAS is 0.2 around less than that for GOC-SCDAS, which is 0.25 around less than that for CDS-BFS. As mentioned previously, we know that the smaller the ARPL, the better the corresponding algorithm. So, in terms of ARPL the performance of -GOC-SCBDAS is better than that of GOC-SCDAS and the performance of GOC-SCDAS is better than that of CDS-BFS.Figure12 shows the simulation results about the diameter of CDS for all considered algorithms under the setting of the proportion of rmax and rmin. On the whole, the tendency of the diameter of CDS for these three algorithms is down as ρ increases. As can be observed, the diameter of CDS for α-GOC-SCBDAS is smaller than that for GOC-SCDAS while the diameter of CDS for GOC-SCDAS is smaller than that for CDS-BFS. At the same time, we can also find that the difference between the diameter of CDS for α-GOC-SCBDAS and that for GOC-SCDAS is greater than the difference between the diameter of CDS for GOC-SCDAS and that for CDS-BFS when ρ≥1.3. Therefore, in terms of diameter, the performance of α-GOC-SCBDAS is the best and that of GOC-SCDAS is the second in these three considered algorithms under the setting of the proportion of rmax and rmin.In summary, according to the above analyses of simulation results, we can conclude that in terms of both routing cost and diameter, the quality of VB produced by GOC-SCDAS andα-GOC-SCBDAS proposed by this paper is better than that of VB produced by CDS-BFS proposed by [32] for a WN.


## 6. Conclusion

This article mainly studies the problem of constructing an MSCDAS with a guaranteed routing cost in an SCDG that services as a model of a WN with heterogeneous transmission radiuses in the rangermin,rmax. To obtain constant-approximation-factor solutions for the MSCDAS of an SCDG, we have proposed two algorithms: GOC-SCDAS and α-GOC-SCBDAS. GOC-SCDAS generates an SCDAS S with a constant approximation factor of 14.4k+1/22 such that for any two nodes p and q in G, dSp,q≤3DiamOPT+7, where k=rmax/rmin. α-GOC-SCBDAS generates an SCBDAS S with a constant approximation factor of 8.8443k+1/22k+1/22 and the routing cost dsu,v≤7du,v, where u,v∈V. We compare our algorithms with previous work in terms of the SCDAS size, ARPL, and diameter through simulations. The simulation results prove these two algorithms in the article are better than the previous algorithm considered for comparison. Other parameters, say fault tolerance, latency, and bandwidth, also influence the communication quality of a WN. We will consider these factors in new distributed algorithms in our future research.



---

*Source: 5602325-2020-07-04.xml*