# On Constructing Strongly Connected Dominating and Absorbing Set in 3-Dimensional Wireless Ad Hoc Networks

Authors: Jiarong Liang; Meng Yi; Weiguang Zhang; Yanyan Li; Xinyu Liang; Bin Qin
Journal: Complexity
 (2020)

---

## Abstract

In a wireless ad hoc network, the size of the virtual backbone (VB) is an important factor for measuring the quality of the VB. The smaller the VB is, the less the overhead caused by the VB. Since ball graphs (BGs) have been used to model 3-dimensional wireless ad hoc networks and since a connected dominating set can be used to represent a VB undertaking routing-related tasks, the problem of finding the smallest VB is transformed into the problem of finding a minimum connected dominating set (MCDS). Many research results on the MCDS problem have been obtained for unit disk graphs and unit ball graphs, in which the transmission ranges of all nodes are identical. In some situations, the node powers can vary. One can model such a network as a graph with different transmission ranges for different nodes. In this paper, we focus on the problem of minimum strongly connected dominating and absorbing sets (MSCDASs) in a strongly connected directed ball graph with different transmission ranges, which is also NP-hard. We design an algorithm considering the construction of a strongly connected dominating and absorbing set (SCDAS), whose size does not exceed319/15k3+116/5k2+29/5kopt+29/3k3+116/5k2+87/5k+13/15, where opt is the size of an MCDAS and k denotes the ratio of rmax to rmin in the ad hoc network with transmission range rmin,rmax. Our simulations show the feasibility of the algorithm proposed in this paper.


---

## Body

## 1. Introduction

Along with the rapid development of wireless radio communication technologies, embedded sensors, and VLSI, the cost of establishing a wireless ad hoc network is decreasing and the performance of wireless ad hoc networks is improving. Recently, wireless ad hoc networks have been widely used in many areas, such as disaster rescue, environmental monitoring, military operations, and mobile computing (see [1–4]), where it is difficult to build a physical backbone for the network; it can be expected that wireless ad hoc networks will play an increasingly important role in the communication of future networks.In wireless ad hoc networks, the power source that each node (sensor) possesses is limited, which results in a limited distance over which the nodes in the wireless ad hoc network can transfer information and the time that the nodes can continue to work. To reduce energy and storage requirements and avoid information conflict and broadcast storms, a backbone-like structure has been proposed [5], called the virtual backbone (VB). A VB is defined as a subset of wireless ad hoc network nodes. Since every operation request between nodes in a wireless ad hoc network can be transformed into a homologous operation on the VB, the routing overhead in the wireless ad hoc network can be significantly reduced by the VB [6]. When the nodes in the VB perform tasks related to routing, they are interfered to some extent by the equipment in the fixed physical backbones. To reduce the interference from the fixed physical backbones, it is natural to attempt to design a VB in which the number of nodes is minimized. In many wireless ad hoc networks [7], a VB can be modeled by a connected dominating set of the wireless ad hoc network. In other words, finding the minimum size VB is equal to determining the minimum connected dominating set in the wireless ad hoc network.Many results related to the problem of computing the MCDS can be found in references [6, 8–11]. Note that the previous references about MCDS are based on the unit disk graph in the two-dimensional plane.However, in some situations, such as undersea resource exploration, disaster prevention, offshore exploration, and ocean environmental monitoring (see [12, 13]), it is not suitable to use MCDS of the unit disk graph to describe the VB of the wireless ad hoc networks. For this reason, people have studied the MCDS problem in three-dimensional space. For example, D. Kim et al. studied the MCDS problem in unit ball graphs and obtained an approximation algorithm of MCDS with a performance ratio of 14.937 (see [13]). In [14], Chizari and Schmutz obtained two CDS algorithms on random unit ball graphs and compared them. In [15], Butenko et al. discussed the MCDS problem in unit-ball graphs. In [16], Gao et al. noted that bugs existed in the approximation deduction process of [13] and proposed a new method to correct these bugs; they then used pruning techniques to optimize the algorithms to choose MCDS. UDG can be viewed as a special case of UBG in which all nodes are restrained to be coplanar. In other words, the MCDS problem in UBGs has more generality than that in UDGs.However, in UDGs, and in UBGs, it is assumed that all nodes in the wireless ad hoc network have the same transmission range at any time; this is incorrect in some situations. When we focus on the powers of nodes in a wireless ad hoc network, differences exist in their functionalities and control technologies for connectivity, and thus, the powers of these nodes may be different. According to the different requirements of the measured frequency in collisions, a node may have to change its transmission range. In such situations, the MCDS problem in a unit disk graph becomes that of a minimum strongly connected dominating and absorbing set (MSCDAS) in a disk graph in reference [17], which was the first paper to study MSCDAS in a network with different transmission ranges. A strongly connected dominating and absorbing set (SCDAS) can usually be used to denote a VB of a wireless ad hoc network in which the nodes have different transmission ranges. This model (SCDAS) guarantees the sharing and interworking of information in the whole network. The research results on SCDAS can be found in the following references. Wu [18] extended the concept of the dominating set in UDG to the dominating and absorbing set (DAS) in disk graphs (DGs) and proposed a localized algorithm to find an SCDAS, which was also extended by the marking process in UDG. In [19], My Thai et al. first presented an approximation algorithm to solve the problem of the strongly connected dominating set (SCDS), and then, based on the obtained SCDS, they proposed a heuristic algorithm to obtain the solution to the SCDAS problem with an approximation ratio. Li et al. discussed the problem of constructing an SCDAS for an asymmetric multihop wireless ad hoc network [20]. Results related to the SCDAS problem can also be found in [21–23]. Note that the previously mentioned results related to the SCDAS problem are all based on two-dimensional space. However, to the best of our knowledge, the field of wireless ad hoc networks with nodes that have different transmission ranges in three-dimensional space has not been studied. In this paper, we study the MSCDAS problem of a wireless ad hoc network with different transmission ranges in three-dimensional space. Note that the MSCDAS problem is also NP-hard because the MCDS problem in UBG is NP-hard and because UBG is a special situation of a ball graph (BG).The remainder of this paper is organized as follows. Section2 introduces some basic definitions and terms. Section 3 separately calculates an improved upper bound for maximal independent sets in UBGs and BGs. Then, we present an algorithm to construct an SCDAS in Section 4. Section 5 provides the simulation results with different parameter settings. Finally, in Section 6, we summarize this paper.


## 2. Preliminaries

For the sake of convenience, we introduce some background information, including special terms in graph theory, which will be used in the paper. A wireless ad hoc networkN, in which each node has a transmission range, can be denoted by a directed graph G=V,E. For each node v∈V, let rv denote the transmission range of node v, rmin=minrvv∈Vrmax=maxrvv∈V is the minimum (maximum) transmission range of the wireless ad hoc network N, and idv is the unique identification of v. For two nodes vi,vj∈V, we use dvi,vj to denote the Euclidean distance between vi and vj and define that vi,vj∈E if and only if dvi,vj≤rvi. The edge vi,vj is said to be a unidirectional edge from vi to vj if vi,vj∈E and vj,vi∉E. The edge vi,vj between vi and vj is said to be a bidirectional edge if vi,vj∈E and vj,vi∈E. According to the above assumptions, we can conclude that the edge vi,vj is a bidirectional edge if and only if dvi,vj≤minrvi,rvj.For nodev∈V, we use N−v=u∈Vu,v∈E (N+v=u∈Vv,u∈E, N−v=N−v∪v, and N+v=N+v∪v) to denote the incoming neighborhood (respectively, the outgoing neighborhood, the closed incoming neighborhood, and the closed outgoing neighborhood) of v. Assume that S is a dominating set of G=V,E; then, S∪N+S=V, where N+S=∪u∈SN+u. A subset R⊆V is called an absorbing set of G if, for any node x∈V−R, there exists a node y∈R such that x,y∈E. It is obvious that if R is an absorbing set, then for any node u∈V−R, N+u∩R≠ϕ. A subset S is called an independent set (IS) of G if and only if, for any two nodes u,v∈S, u,v∉E or v,u∉E. A directed graph G=V,E is called a strongly connected graph if and only if, for any two nodes vi,vj∈V, there exist two directed paths, one of them being from vi to vj and the other being from vj to vi. A subset S⊆V is called a strongly connected dominating set (SCDS) if and only if S is a DS, and GS, which is a subgraph of G induced by S, is strongly connected. A subset S⊆V is called a strongly connected dominating and absorbing set (SCDAS) if and only if S is an SCDS, and for each node u∉S, N+u∩S≠ϕ.


## 3. An Improved Upper Bound for Maximal Independent Sets

For an undirected graphH=V1,E1, when an approximation algorithm for the MCDS of H is considered to obtain a CDS with a performance ratio with respect to MCDS, generally, there are two steps. The first step is to find an MIS M in H, which is a domination set of H. The second step is to find some nodes in V1−M to connect the nodes in M to obtain a CDS. However, for a directed graph G=V,E, when we design an approximation algorithm for an SCDAS of G with a performance ratio with respect to MSCDAS, it is not sufficient that there are only two steps as in the above method for a CDS. The main reason for this is that for a directed graph G, an MIS is not necessarily a dominating set. In this paper, we use the following three steps to obtain an SCDAS of G with a better performance ratio to MSCDAS. The first step is to find a dominating set M for G. The second step is to locate some nodes in V−M and add them to the dominating set M such that it becomes a CDS Sd for G. The third step is to reverse all edges in G to obtain a new directed ball graph G¯=V,E¯. A similar method to the first and second steps is used to obtain a connected dominating set Sa of G¯, which is a connected absorbing set for G. Then, Sd∪Sa, an SCDAS of G, is obtained. For the sake of convenience, let us first discuss the upper bound of the size of MIS for a unit ball graph G=V,E.


### 3.1. An Improved Upper Bound for the Size of an MIS in a Unit Ball Graph

In this section, we determine an upper bound for an MIS in a unit ball graphG=V,E. Let αG denote the size of the MIS in G, and opt1 is the size of the MCDS in G. For the number of independent nodes in the unit ball graph G=V,E, the following result has been presented in [24].Lemma 1 (see [24]).
Assume thatG=V,E is a unit ball graph. Then, for any node v∈V, the unit ball with the center v has at most 12 independent nodes.For the bound of an MIS in the unit ball graphG=V,E, using Lemma 1, Butenko et al. [15] showed that αG≤11opt1+1. Remarkably, using Lemma 1, Kim et al. [13] improved the result in [15] and obtained an upper bound of the size of the MIS in UBG as follows.Lemma 2 (see [13]).
Assume thatG=V,E is a unit ball graph. Then, αG≤10.917opt1+1.083.To obtain an improved upper bound for maximal independent sets in a connected unit ball graph, we present some important results in the following.LetDi with the center ei and Dj with the center ej be two connected unit balls (see Figure 1). Let Di¯ and Dj¯ be two balls with radius 1.5 and centers ei and ej, respectively (see Figure 2), where dei,ej=1. Let B1=Di∪Dj and B2=Di¯∪Dj¯. The following result is obvious.Figure 1
Two adjacent unit balls with centersei and ej, where dei,ej=1.Figure 2
Two adjacent balls with centersei and ej, where dei,ej=1 and the radius of the balls is 1.5.Lemma 3.
The number of independent nodes inB1 does not exceed the number corresponding to the maximum packing of balls with radius 0.5 in B2.According to Lemma3, we know that the number of independent nodes in a UDS is related to the upper bounds for the sphere backing problem. It is worth mentioning that there are a lot of studies being related to the bounds for the sphere backing problem (see [25, 26]). Now, we derive the main result in the section.Lemma 4.
Assume thatG=V,E is a connected unit ball graph and G¯=V¯,E¯ is another connected ball graph with V¯=V, for which the radius of each ball is 1.5. Let I=e1,e2,…,eopt1 be an MCDS of G, and A is the covered area with balls in G¯ with centers eis in I. Then, the volume of A is at most 14.1372+6.8068opt1−1, where opt1 is the number of nodes in the MCDS of G.Proof.
Assume thatD¯i with the center ei and D¯j with the center ej are two connected balls with radius 1.5 in G¯. Then, dei,ej≤1. We first consider the case in which dei,ej=1. Let Vi and Vij denote the volumes of D¯i and D¯j−D¯i, respectively; then, Vi=4/3π1.53≤14.1372. From Figure 2, we see that Vij=Vi−2×1/3πh23×1.5−h=Vi−2×1/3π123×1.5−1≤6.8068. It is obvious that for the case dei,ej<1, the result Vij≤6.8068 is still true. Hence, the volume of A is at most 14.1372+6.8068opt1−1.
A rhombic dodecahedron has 12 identical rhombic faces with 24 edges and 14 vertices [27]. In these 14 vertices, there are 6 vertices, called Type I vertex, in which each one is exactly the intersection of four rhombic faces, and there are also 8 vertices, called Type II vertex, in which each one is exactly the intersection of three rhombic faces. For example, in Figure 3, A,I,K,M,C,andF belong to Type I vertex and D,B,E,G,H,N,L,andJ belong to Type II.Figure 3
Illustration of a rhombic dodecahedron surrounding an inscribed ball with radius 0.5.Lemma 5.
The volume of a rhombic dodecahedron that surrounds an inscribed ball with radius 0.5 is 0.7071.Proof.
Leta be the edge length of a rhombic dodecahedron and r be the radius of its inscribed ball (see Figure 3); then, the volume of the rhombic dodecahedron is V12=16/93a3, and the relationship between a and r is r=6/3a. Since r=0.5, V12=42r3≈4×1.4142×0.53=0.7071.
According to Lemma3, to obtain an upper bound of the size of the maximal independent set in the connected unit ball graph G, we need to calculate the number corresponding to the maximum packing of balls with radius 0.5 in G¯. Since the volume of a ball with radius 0.5 is 4/3π0.53≈0.5236, we obtain an upper bound of the size of the MIS:(1)αG≤14.1372+6.8068opt1−10.5236=13opt1+14.
Note that for two independent nodesu and v in G, there exist two corresponding packing balls with radius 0.5 and centers u and v, respectively, denoted by Bu and Bv, in G¯, and they are not adjacent. In other words, there is space between Bu and Bv. To derive a better upper bound of the size of the maximal independent set in the connected unit ball graph G, we use a rhombic dodecahedron, which surrounds a ball with radius 0.5 to replace each packing ball with radius 0.5 in G¯. The reasons are described as follows.
LetBu0.5 denote a ball with center u and radius 0.5, Burd denote a rhombic dodecahedron surrounding Bu0.5, Vu0.5 be the volume of the ball Bu0.5, Vurd be the volume of Burd, VA be the volume of A, and the covered area with balls in G¯ with centers eis in I. According to Lemma 3, we conclude that the number of independent nodes in G, denoted by l, does not exceed the number of the maximum packing of balls with radius 0.5 in A, denoted by k. In other words, l≤k. Since there is some space between these balls, VA/V0.5 may be not a better upper bound for αG. On the other hand, since the area covered by G¯ can be seamlessly filled by rhombic dodecahedrons [27], it is expectable to obtain VA/Vurd, an upper bound of αG, which is better than VA/Vu0.5.
LetS0.5=Bu10.5,Bu20.5,…,Buk0.5 be the set of all balls packed in A, where dui,uj≥1,i≠j,1≤i,j≤k. Let S0.5rd=Bu1rd,Bu2rd,…,Bukrd be the set of all rhombic dodecahedrons corresponding to these balls in S0.5 and VS0.5rd be the volume of Bu1rd∪Bu2rd∪⋯∪Bukrd. If each rhombic dodecahedron in S0.5rd is covered by A, then k=VS0.5rd/Vurd≤VA/Vurd<VA/Vu0.5, which implies that VA/Vurd is better than VA/V0.5. Then, the size of the MIS in G is upper bounded by(2)αG≤14.1372+6.8068opt1−10.7071=9.6264opt1+10.3668.
Note that when one nodeu in the independent set in G is on the surface of the unit ball with center ei∈I, the corresponding ball Bu0.5 in G¯ is inscribed by some balls with center ei and radius 1.5 in G¯. In this case, the rhombic dodecahedrons surrounding Bu0.5 may be incompletely covered by A. In other words, there may be some rhombic dodecahedrons, say Buird, in S0.5rd such that the part of Buird is outside A. In the case, let λi be the volume of Buird−Buird∩A1≤i≤k. Without loss of generality, suppose that λ1=maxλi, then k=VS0.5rd/Vurd≤VA/Vu1rd−λ1<VA/Vu0.5, which implies that VA/Vu1rd−λ1 is better than VA/Vu0.5 as a upper bound of αG. In this case, it is necessary to analyse the upper bound of λ1 to evaluate a better upper bound of VA/Vu1rd−λ1.
It is obvious that the largestλ1 can take place only if node u1 is on the surface of some unit ball with center ei∈I. Under the situation, as it is illustrated in Figure 4, there are at most 4 vertices of Bu1rd outside the ball with center ei and radius 1.5 (M,N,K,andL in Figure 4), where two of them belong to Type I and other two belong to Type II, which implies that there are at most 4 vertices of Bu1rd outside A. Let w be the volume of Bu1rd−Bu1rd∩Bei1.5, where Bei1.5 is the ball with center ei and radius 1.5 and z is the volume of Bu1rd−Bu1rd∩Bu10.5. Consider a partition of Bu1rd−Bu1rd∩Bu10.5, σ=σ1,σ2,…,σ14, which satisfies the following conditions:(1)
Eachσi in σ contains one and only one vertex of Bu1rd(2)
Eachσi in σ containing one Type I vertex is identical and has the same volume, denoted by x(3)
Eachσi in σ containing one Type II vertex is identical and has the same volume, denoted by y(4)
w≤2x+2y
It is easily seen thatz=6x+8y. Next, consider the following cases:Case 1.x≤y. Since 2x+y−2/7z=2/7x−y≤0, 2x+y≤2/7z.Case 2.x>y. Since z=6x+8y, 2x+y=1/4z+1/2x≤1/3z.
Hence,λ1≤w≤2x+y≤max2/7z,1/3z, and then, λ1≤1/3z.
Then, we obtain a new upper bound of MIS inG as follows:(3)αG≤k≤VAVu1rd−λ1≤14.1372+6.8068opt1−142×0.53−1/342×0.53−4/3π×0.53≤14.1372+6.8068opt1−10.6459≤10.5385opt1+11.3491.
According to the above discussion, we have the following results.Figure 4
Size of a rhombic dodecahedron outsideG¯.Theorem 1.
Letopt1 be the number of nodes in an MCDS of a connected unit ball graph G and αG is the number of nodes in an MIS of G; then,(4)αG≤10.5385opt1+11.3491.Remark 1.
Whenopt1≥28, the result is better than that in [13].


### 3.2. An Upper Bound of the Size of an MIS in a Directed Ball Graph

In this section, we use a method similar to that in the previous section to obtain an upper bound of a directed ball graph. Suppose that a directed graphG=V,E represents a wireless ad hoc network with transmission range rmin,rmax and is strongly connected. Let OPTd denote a minimum strongly connected dominating set of G, OPT denote a minimum strongly connected dominating and absorbed set of G, optd=OPTd, and opt=OPT. Since OPTd⊆OPT, optd≤opt. Since OPTd is strongly connected, we can always obtain an order of nodes in OPTd as v1,v2,…,voptd such that for each integer k∈2,3,…,optd, there exists at least an integer l∈1,2,…,k−1 satisfying dvk,vl≤rmax.LetDi be a ball with center ei and radius rei∈rmin,rmax, Dj be a ball with center ej and radius be rej∈rmin,rmax, Di¯ and Dj¯ be two balls with radius rmax+1/2rmin and centers ei and ej, respectively, where ei,ej∈V, and dei,ej≤rmax. Let B1=Di∪Dj and B2=Di¯∪Dj¯.Lemma 6.
The volume ofDj¯−Di¯, denoted by VDj¯−Di¯, does not exceed(5)11π12rmax3+πrmax2rmin+π4rmaxrmin2.Proof.
We first consider the casedei,ej=rmax. In Figure 5, we see that the height of a spherical cap is h=1/2rmax+1/2rmin; then, the volume of the spherical cap Vsc is determined as follows:(6)Vsc=π3h23R−h=π3×12rmax+12rmin2×3×rmax+12rmin−12rmax+12rmin=5π24rmax3+π2rmax2rmin+3π8rmin2rmax+π12rmin3.
Then, we have that(7)VDj¯−Di¯=43πR3−2Vsc=11π12rmax3+πrmax2rmin+π4rmaxrmin2.
In the casedei,ej<rmax, it is obvious that(8)VDj¯−Di¯<11π12rmax3+πrmax2rmin+π4rmaxrmin2.Figure 5
Illustration of two balls with centersei and ej and dei,ej≤rmax.Lemma 7.
[19] Let u and v be two independent nodes in G; then, du,v>rmin.Lemma7 implies that the following result is true.Lemma 8.
Assuming thatB1 and B2 are adjacent, the number of independent nodes in B1 does not exceed the number representing the maximum packing of balls with radius 1/2rmin in B2.Lemma 9.
Assume thatG=V,E is a strongly connected ball graph. Let OPTd=v1,v2,…,voptd, in which for each integer k∈2,3,…,optd, there exists at least an integer l∈1,2,…,k−1 satisfying dvk,vl≤rmax, which is a minimum strongly connected dominating set. Ai denotes the area covered by the ball with center vi in OPTd and radius rvi, Ai∗ denotes the area covered by the ball with center vi in OPTdand radius R=rmax+1/2rmin, A=A1∪A2∪⋯∪Aoptd, and A∗=A1∗∪A2∗∪⋯∪Aoptd∗. Then, the following conditions hold:(1)
A⊆A∗.(2)
The volume ofA∗ does not exceed 4/3πR3+optd−1×V0, where(9)V0=11π12rmax3+πrmax2rmin+π4rmaxrmin2.Proof.
Condition (1) is trivial. Now, we consider condition (2). We show condition (2) by induction on optd. When optd=1, the result is true. When optd=2, Lemma 6 implies that the result is true. Assume that when optd≤kk≥2, the result is true. Next, assume that optd=k+1. By induction hypothesis, we have that(10)Ak∗≤43πR3+k−1×V0.
According to the assumption on the order ofOPTd, there exists at least one node vi∈v1,v2,…,vk such that dvi,vk+1≤rmax. According to Lemma 6, we have that the volume of D¯k+1−D¯i, denoted by VD¯k+1−D¯i, exceeds V0, where D¯iD¯k+1 is a ball with radius R and center vivk+1. Hence, the inequality(11)Ak+1∗≤Ak∗+VD¯k+1−D¯i≤Ak∗+V0≤43πR3+k+1−1×V0implies that, when OPTd=k+1, the result is also true.
According to Lemma8, we have that the number of nodes in an MIS of G does not exceed the number representing the maximum packing of balls with radius 1/2rmin in A∗. Note that for any two independent nodes u and v in G, the two corresponding balls with radius 1/2rmin and centers u and v are contained in an area A∗ and they are disjoint. In addition, since rhombic dodecahedrons can be used to densely fill a space, we can use a rhombic dodecahedron, which surrounds a ball with radius 1/2rmin, to replace the ball with radius 1/2rmin to fill A∗. It is easily determined that the volume of a rhombic dodecahedron surrounding a ball with radius 1/2rmin is 421/2rmin3. At the same time, we note that when an independent node w is on the surface of a ball with a center node in OPTd, the corresponding rhombic dodecahedron (surrounding the ball) may not be completely contained in an area A∗ and the volume of the part of the rhombic dodecahedron outside A∗ may attain 1/742−4/3π1/2rmin3. From the above analysis, we can obtain an upper bound of the size of an MIS for G as follows:(12)αG≤4/3πR3+optd−1×V042×1/2rmin3−1/342−4/3π1/2rmin3≤4/3πR3+optd−1V05π/29rmin3≤31960k3+295k2+2920koptd+2912k3+295k2+8720k+2930.
Sinceoptd≤opt,(13)αG≤31960k3+295k2+2920koptd+2912k3+295k2+8720k+2930.Theorem 2.
In a directed connected ball graphG,(14)αG≤31960k3+295k2+2920koptd+2912k3+295k2+8720k+2930.


## 3.1. An Improved Upper Bound for the Size of an MIS in a Unit Ball Graph

In this section, we determine an upper bound for an MIS in a unit ball graphG=V,E. Let αG denote the size of the MIS in G, and opt1 is the size of the MCDS in G. For the number of independent nodes in the unit ball graph G=V,E, the following result has been presented in [24].Lemma 1 (see [24]).
Assume thatG=V,E is a unit ball graph. Then, for any node v∈V, the unit ball with the center v has at most 12 independent nodes.For the bound of an MIS in the unit ball graphG=V,E, using Lemma 1, Butenko et al. [15] showed that αG≤11opt1+1. Remarkably, using Lemma 1, Kim et al. [13] improved the result in [15] and obtained an upper bound of the size of the MIS in UBG as follows.Lemma 2 (see [13]).
Assume thatG=V,E is a unit ball graph. Then, αG≤10.917opt1+1.083.To obtain an improved upper bound for maximal independent sets in a connected unit ball graph, we present some important results in the following.LetDi with the center ei and Dj with the center ej be two connected unit balls (see Figure 1). Let Di¯ and Dj¯ be two balls with radius 1.5 and centers ei and ej, respectively (see Figure 2), where dei,ej=1. Let B1=Di∪Dj and B2=Di¯∪Dj¯. The following result is obvious.Figure 1
Two adjacent unit balls with centersei and ej, where dei,ej=1.Figure 2
Two adjacent balls with centersei and ej, where dei,ej=1 and the radius of the balls is 1.5.Lemma 3.
The number of independent nodes inB1 does not exceed the number corresponding to the maximum packing of balls with radius 0.5 in B2.According to Lemma3, we know that the number of independent nodes in a UDS is related to the upper bounds for the sphere backing problem. It is worth mentioning that there are a lot of studies being related to the bounds for the sphere backing problem (see [25, 26]). Now, we derive the main result in the section.Lemma 4.
Assume thatG=V,E is a connected unit ball graph and G¯=V¯,E¯ is another connected ball graph with V¯=V, for which the radius of each ball is 1.5. Let I=e1,e2,…,eopt1 be an MCDS of G, and A is the covered area with balls in G¯ with centers eis in I. Then, the volume of A is at most 14.1372+6.8068opt1−1, where opt1 is the number of nodes in the MCDS of G.Proof.
Assume thatD¯i with the center ei and D¯j with the center ej are two connected balls with radius 1.5 in G¯. Then, dei,ej≤1. We first consider the case in which dei,ej=1. Let Vi and Vij denote the volumes of D¯i and D¯j−D¯i, respectively; then, Vi=4/3π1.53≤14.1372. From Figure 2, we see that Vij=Vi−2×1/3πh23×1.5−h=Vi−2×1/3π123×1.5−1≤6.8068. It is obvious that for the case dei,ej<1, the result Vij≤6.8068 is still true. Hence, the volume of A is at most 14.1372+6.8068opt1−1.
A rhombic dodecahedron has 12 identical rhombic faces with 24 edges and 14 vertices [27]. In these 14 vertices, there are 6 vertices, called Type I vertex, in which each one is exactly the intersection of four rhombic faces, and there are also 8 vertices, called Type II vertex, in which each one is exactly the intersection of three rhombic faces. For example, in Figure 3, A,I,K,M,C,andF belong to Type I vertex and D,B,E,G,H,N,L,andJ belong to Type II.Figure 3
Illustration of a rhombic dodecahedron surrounding an inscribed ball with radius 0.5.Lemma 5.
The volume of a rhombic dodecahedron that surrounds an inscribed ball with radius 0.5 is 0.7071.Proof.
Leta be the edge length of a rhombic dodecahedron and r be the radius of its inscribed ball (see Figure 3); then, the volume of the rhombic dodecahedron is V12=16/93a3, and the relationship between a and r is r=6/3a. Since r=0.5, V12=42r3≈4×1.4142×0.53=0.7071.
According to Lemma3, to obtain an upper bound of the size of the maximal independent set in the connected unit ball graph G, we need to calculate the number corresponding to the maximum packing of balls with radius 0.5 in G¯. Since the volume of a ball with radius 0.5 is 4/3π0.53≈0.5236, we obtain an upper bound of the size of the MIS:(1)αG≤14.1372+6.8068opt1−10.5236=13opt1+14.
Note that for two independent nodesu and v in G, there exist two corresponding packing balls with radius 0.5 and centers u and v, respectively, denoted by Bu and Bv, in G¯, and they are not adjacent. In other words, there is space between Bu and Bv. To derive a better upper bound of the size of the maximal independent set in the connected unit ball graph G, we use a rhombic dodecahedron, which surrounds a ball with radius 0.5 to replace each packing ball with radius 0.5 in G¯. The reasons are described as follows.
LetBu0.5 denote a ball with center u and radius 0.5, Burd denote a rhombic dodecahedron surrounding Bu0.5, Vu0.5 be the volume of the ball Bu0.5, Vurd be the volume of Burd, VA be the volume of A, and the covered area with balls in G¯ with centers eis in I. According to Lemma 3, we conclude that the number of independent nodes in G, denoted by l, does not exceed the number of the maximum packing of balls with radius 0.5 in A, denoted by k. In other words, l≤k. Since there is some space between these balls, VA/V0.5 may be not a better upper bound for αG. On the other hand, since the area covered by G¯ can be seamlessly filled by rhombic dodecahedrons [27], it is expectable to obtain VA/Vurd, an upper bound of αG, which is better than VA/Vu0.5.
LetS0.5=Bu10.5,Bu20.5,…,Buk0.5 be the set of all balls packed in A, where dui,uj≥1,i≠j,1≤i,j≤k. Let S0.5rd=Bu1rd,Bu2rd,…,Bukrd be the set of all rhombic dodecahedrons corresponding to these balls in S0.5 and VS0.5rd be the volume of Bu1rd∪Bu2rd∪⋯∪Bukrd. If each rhombic dodecahedron in S0.5rd is covered by A, then k=VS0.5rd/Vurd≤VA/Vurd<VA/Vu0.5, which implies that VA/Vurd is better than VA/V0.5. Then, the size of the MIS in G is upper bounded by(2)αG≤14.1372+6.8068opt1−10.7071=9.6264opt1+10.3668.
Note that when one nodeu in the independent set in G is on the surface of the unit ball with center ei∈I, the corresponding ball Bu0.5 in G¯ is inscribed by some balls with center ei and radius 1.5 in G¯. In this case, the rhombic dodecahedrons surrounding Bu0.5 may be incompletely covered by A. In other words, there may be some rhombic dodecahedrons, say Buird, in S0.5rd such that the part of Buird is outside A. In the case, let λi be the volume of Buird−Buird∩A1≤i≤k. Without loss of generality, suppose that λ1=maxλi, then k=VS0.5rd/Vurd≤VA/Vu1rd−λ1<VA/Vu0.5, which implies that VA/Vu1rd−λ1 is better than VA/Vu0.5 as a upper bound of αG. In this case, it is necessary to analyse the upper bound of λ1 to evaluate a better upper bound of VA/Vu1rd−λ1.
It is obvious that the largestλ1 can take place only if node u1 is on the surface of some unit ball with center ei∈I. Under the situation, as it is illustrated in Figure 4, there are at most 4 vertices of Bu1rd outside the ball with center ei and radius 1.5 (M,N,K,andL in Figure 4), where two of them belong to Type I and other two belong to Type II, which implies that there are at most 4 vertices of Bu1rd outside A. Let w be the volume of Bu1rd−Bu1rd∩Bei1.5, where Bei1.5 is the ball with center ei and radius 1.5 and z is the volume of Bu1rd−Bu1rd∩Bu10.5. Consider a partition of Bu1rd−Bu1rd∩Bu10.5, σ=σ1,σ2,…,σ14, which satisfies the following conditions:(1)
Eachσi in σ contains one and only one vertex of Bu1rd(2)
Eachσi in σ containing one Type I vertex is identical and has the same volume, denoted by x(3)
Eachσi in σ containing one Type II vertex is identical and has the same volume, denoted by y(4)
w≤2x+2y
It is easily seen thatz=6x+8y. Next, consider the following cases:Case 1.x≤y. Since 2x+y−2/7z=2/7x−y≤0, 2x+y≤2/7z.Case 2.x>y. Since z=6x+8y, 2x+y=1/4z+1/2x≤1/3z.
Hence,λ1≤w≤2x+y≤max2/7z,1/3z, and then, λ1≤1/3z.
Then, we obtain a new upper bound of MIS inG as follows:(3)αG≤k≤VAVu1rd−λ1≤14.1372+6.8068opt1−142×0.53−1/342×0.53−4/3π×0.53≤14.1372+6.8068opt1−10.6459≤10.5385opt1+11.3491.
According to the above discussion, we have the following results.Figure 4
Size of a rhombic dodecahedron outsideG¯.Theorem 1.
Letopt1 be the number of nodes in an MCDS of a connected unit ball graph G and αG is the number of nodes in an MIS of G; then,(4)αG≤10.5385opt1+11.3491.Remark 1.
Whenopt1≥28, the result is better than that in [13].


## 3.2. An Upper Bound of the Size of an MIS in a Directed Ball Graph

In this section, we use a method similar to that in the previous section to obtain an upper bound of a directed ball graph. Suppose that a directed graphG=V,E represents a wireless ad hoc network with transmission range rmin,rmax and is strongly connected. Let OPTd denote a minimum strongly connected dominating set of G, OPT denote a minimum strongly connected dominating and absorbed set of G, optd=OPTd, and opt=OPT. Since OPTd⊆OPT, optd≤opt. Since OPTd is strongly connected, we can always obtain an order of nodes in OPTd as v1,v2,…,voptd such that for each integer k∈2,3,…,optd, there exists at least an integer l∈1,2,…,k−1 satisfying dvk,vl≤rmax.LetDi be a ball with center ei and radius rei∈rmin,rmax, Dj be a ball with center ej and radius be rej∈rmin,rmax, Di¯ and Dj¯ be two balls with radius rmax+1/2rmin and centers ei and ej, respectively, where ei,ej∈V, and dei,ej≤rmax. Let B1=Di∪Dj and B2=Di¯∪Dj¯.Lemma 6.
The volume ofDj¯−Di¯, denoted by VDj¯−Di¯, does not exceed(5)11π12rmax3+πrmax2rmin+π4rmaxrmin2.Proof.
We first consider the casedei,ej=rmax. In Figure 5, we see that the height of a spherical cap is h=1/2rmax+1/2rmin; then, the volume of the spherical cap Vsc is determined as follows:(6)Vsc=π3h23R−h=π3×12rmax+12rmin2×3×rmax+12rmin−12rmax+12rmin=5π24rmax3+π2rmax2rmin+3π8rmin2rmax+π12rmin3.
Then, we have that(7)VDj¯−Di¯=43πR3−2Vsc=11π12rmax3+πrmax2rmin+π4rmaxrmin2.
In the casedei,ej<rmax, it is obvious that(8)VDj¯−Di¯<11π12rmax3+πrmax2rmin+π4rmaxrmin2.Figure 5
Illustration of two balls with centersei and ej and dei,ej≤rmax.Lemma 7.
[19] Let u and v be two independent nodes in G; then, du,v>rmin.Lemma7 implies that the following result is true.Lemma 8.
Assuming thatB1 and B2 are adjacent, the number of independent nodes in B1 does not exceed the number representing the maximum packing of balls with radius 1/2rmin in B2.Lemma 9.
Assume thatG=V,E is a strongly connected ball graph. Let OPTd=v1,v2,…,voptd, in which for each integer k∈2,3,…,optd, there exists at least an integer l∈1,2,…,k−1 satisfying dvk,vl≤rmax, which is a minimum strongly connected dominating set. Ai denotes the area covered by the ball with center vi in OPTd and radius rvi, Ai∗ denotes the area covered by the ball with center vi in OPTdand radius R=rmax+1/2rmin, A=A1∪A2∪⋯∪Aoptd, and A∗=A1∗∪A2∗∪⋯∪Aoptd∗. Then, the following conditions hold:(1)
A⊆A∗.(2)
The volume ofA∗ does not exceed 4/3πR3+optd−1×V0, where(9)V0=11π12rmax3+πrmax2rmin+π4rmaxrmin2.Proof.
Condition (1) is trivial. Now, we consider condition (2). We show condition (2) by induction on optd. When optd=1, the result is true. When optd=2, Lemma 6 implies that the result is true. Assume that when optd≤kk≥2, the result is true. Next, assume that optd=k+1. By induction hypothesis, we have that(10)Ak∗≤43πR3+k−1×V0.
According to the assumption on the order ofOPTd, there exists at least one node vi∈v1,v2,…,vk such that dvi,vk+1≤rmax. According to Lemma 6, we have that the volume of D¯k+1−D¯i, denoted by VD¯k+1−D¯i, exceeds V0, where D¯iD¯k+1 is a ball with radius R and center vivk+1. Hence, the inequality(11)Ak+1∗≤Ak∗+VD¯k+1−D¯i≤Ak∗+V0≤43πR3+k+1−1×V0implies that, when OPTd=k+1, the result is also true.
According to Lemma8, we have that the number of nodes in an MIS of G does not exceed the number representing the maximum packing of balls with radius 1/2rmin in A∗. Note that for any two independent nodes u and v in G, the two corresponding balls with radius 1/2rmin and centers u and v are contained in an area A∗ and they are disjoint. In addition, since rhombic dodecahedrons can be used to densely fill a space, we can use a rhombic dodecahedron, which surrounds a ball with radius 1/2rmin, to replace the ball with radius 1/2rmin to fill A∗. It is easily determined that the volume of a rhombic dodecahedron surrounding a ball with radius 1/2rmin is 421/2rmin3. At the same time, we note that when an independent node w is on the surface of a ball with a center node in OPTd, the corresponding rhombic dodecahedron (surrounding the ball) may not be completely contained in an area A∗ and the volume of the part of the rhombic dodecahedron outside A∗ may attain 1/742−4/3π1/2rmin3. From the above analysis, we can obtain an upper bound of the size of an MIS for G as follows:(12)αG≤4/3πR3+optd−1×V042×1/2rmin3−1/342−4/3π1/2rmin3≤4/3πR3+optd−1V05π/29rmin3≤31960k3+295k2+2920koptd+2912k3+295k2+8720k+2930.
Sinceoptd≤opt,(13)αG≤31960k3+295k2+2920koptd+2912k3+295k2+8720k+2930.Theorem 2.
In a directed connected ball graphG,(14)αG≤31960k3+295k2+2920koptd+2912k3+295k2+8720k+2930.


## 4. An SCDAS Computation Algorithm in a Directed Ball Graph

In this section, we introduce an efficient heuristic algorithm to construct an SCDAS for a directed ball graphG=V,E. The idea of this algorithm is described as follows. We choose a node s with the largest degree in G and construct two node sets Sd and Sa by calling a subroutine called UnidiTree such that S=Sd∪Sa is an SCADAS for G, where UnidiTree is a subroutine, which can generate a rooted tree for G.LetG=V,E be a strongly connected ball graph and Lx,C be a set of independent nodes in N+x and not in C. To obtain a DAS, we first use a greedy method to find a DS Sd. Second, we consider another strongly connected ball graph G¯=V¯,E¯, where V¯=V,E¯=u,vv,u∈E, and then, we use the same method to find a DS Sa in G¯. It is obvious that Sa is an absorbing set in G. In addition, S=Sd∪Sa is a DAS of G, and the details of the computation for the above DAS S can be found in Algorithm 1 LYZLLQ.Algorithm 1:LYZLLQ.
(1)
Input: A strongly connected directed ball graph G=V,E.
(2)
Output: An SCDAS S.
(3)
Choose a roots∈V with the largest degree N+s∪N−s;
(4)
S
d
=
UnidTree
V
,
E
,
s;
(5)
Reverse all directed edges inE, form a new edge set E¯=u,vu,v∈V,v,u∈E;
(6)
S
a
=
UnidTree
V
,
E
¯
,
s;
(7)
S
=
S
d
∪
S
a;
(8)
Return
S;Lemma 10.
Assume thatL0 is obtained after executing UnidTree (Algorithm 2). Decompose L0 into two subsets: L1,L2⊂L0,Li≠ϕi=1,2,L1∪L2=L0,andL1∩L2=ϕ. Then, the distances L1 and L2 in G=V,E do not exceed two hops.Algorithm 2:Subroutine UnidTree (V,E,s).
(1)
Procedure UnidTree (V, E, s)
(2)
SetL0=ϕ,V1=V;
(3)
Colors black;
(4)
SetL0=s,W=N+s, and V1=V1−s∪N+s;
(5)
While
V
1
≠
ϕ
do
(6)
Choosex∈N+W such that N+x∩V1 is maximized, color x back;
(7)
SetL0=L0∪x,W=W∪N+x∩V1, and V1=V1−x∪N+x;
(8)
End while
(9)
SetC=s,L=L0−s;
(10)
While
L
≠
ϕ
do
(11)
Choose a nodev∈N+C such that Lv,C=maxLx,C:x∈N+C, color v blue;
(12)
SetC=C∪v∪Lv,C,L=L−Lv,C;
(13)
End while
(14)
Return
C;
(15)
End procedureProof.
Without loss of generality, assume thatL0=v0,v1,…,vk, where v0=s and vi1≤i≤k is the node added to L0 after the ith iteration (see lines 4–8). By line 6 and line 7, we have that, for integer 1≤i≤k, vi has an incoming node in W, which is an outgoing node of some nodes, say, vit, in v0,v1,…,vi−1. In other words, there exists one node vit in v0,v1,…,vi−1 such that the distance between vi and vit is at most two hops. Since L1,L2⊂L0,Li≠ϕi=1,2,L1∪L2=L0,andL1∩L2=ϕ, there exist some integers 1≤i≤k such that vi∈L1,v0,v1,…,vi−1⊆L2 or vi∈L2,v0,v1,…,vi−1⊆L1. Hence, the distance between L1 and L2 does not exceed two hops.Lemma 11.
AfterUnidTree (Algorithm 2) is executed, the following conditions hold:(1)
L0⊆C(2)
For any nodeu∈C−s, there exists a direct path, say, Psu, from root node s to u such that all nodes of Psu belong to C(3)
C≤2L0−1Proof.
Condition (1) is trivial.
Now, we show that condition (2) is true. Let Ci be the set C after the ith iteration and C0=s, and Ri=Ci−C0; it is obvious that Ri∪Rj=ϕi≠jandRi∩C0=ϕi≠0. Assume that the number of iterations is n (lines 10–13 in Algorithm 2). For any node u∈C, if u∈C0, the result is trivial. Assuming that u∉C0, there exists an integer i such that u∈Ri. Next, we show that condition (2) is true by induction on i1≤i≤n. When i=1, if u is the blue node in R1, then u∈N+s, and the result is true. If u is a node in Lv,C, then s⟶v⟶u is a directed path, which implies that the result is true. Assume that the result is true for i≤k,k≤n−1. When i=k+1, if u is the blue node in Rk+1, since u∈N+Ck and Ck=C0∪R1∪⋯∪Rk, then there exists a node w∈C0 or w∈Rj1≤j≤k such that w,u∈E. By the inductive hypothesis, there exists a directed path Psw from s to w. Then, Psw∪w,u is a directed path from s to u. If u is in Lv,Ck, then by the above argument, there exists a directed path Psv from s to v. Hence, Psv∪v,u is a directed path from s to u. Hence, when i=k+1, the result is true.
The proof of condition (3): after line 9, C contains only a black node s. In lines 10–13, after each iteration, one blue node is added to C, and the number of black nodes added to C is Lv,C. By the process of producing black nodes (lines 5–8), we have that Lv,C≥1. Therefore, after line 14, the number of black nodes contained in C is greater than or equal to the number of blue nodes contained in C. Hence, C≤2L0−1.Theorem 3.
Assume thatG=V,E is a directed strongly connected ball graph, which possesses transmission ranges rmin,rmax. OPT is an MSCDAS of size opt for G. Then, the following conditions hold:(1)
The set of nodesS output by the algorithm is a strongly connected dominating and absorbing set(2)
S≤319/15k3+116/5k2+29/5kopt+29/3k3+116/5k2+87/5k+13/15Proof.
(1) We first show that the set of nodes S output by the algorithm is a dominating and absorbing set. We claim that L0 produced by unidTree (Algorithm 2) is a DS for the graph run by unidTree (Algorithm 2). In lines 4–8 of Algorithm 2, it is easily seen that each node in W has at least one incoming neighbor in L0, and after line 8, since V1=ϕ, all nodes are in W or L0, which implies that L0 is a DS for the graph run by unidTree (Algorithm 2). By Lemma 11, we have that C is a dominating set for the graph run by unidTree (Algorithm 2). Hence, SdSa is a DS for G=V,EG¯=V,E¯. Furthermore, Sa is an absorbing set for G=V,E, which implies that S=Sd∪Sa is a DAS for G=V,E.
Now, we show thatS is strongly connected. We claim that for any node v∈S, there are two directed paths: one path is from root node s to node v and the other path is from node v to root node s. If v=s, this claim is trivial. Assume that v≠s. Since S=Sd∪Sa, v∈Sd or v∈Sa. Consider the following cases:Case 1.v∈Sd∪Sa. According to Lemma 11, there exists a directed path Psv=s⟶⋯⟶v from root node s to node v in G, and another directed path Q¯sv exists from root node s to node v in G¯. We reverse all edges in Q¯sv, and we obtain a directed path, denoted by Qvs, from node v to root node s in G.Case 2.v∈Sd−Sa. According to Lemma 11, there exists a directed path Psv=s⟶⋯⟶v from root node s to node v in G. Since Sa is a dominating set for G¯, there exists a node, u, in Sa such that u,v∈E¯, which implies that v,u∈E. Additionally, according to condition (2) in Lemma 11, there exists a directed path, denoted by P¯su, from root node s to node u for G¯. We reverse all edges in P¯su, and we obtain another directed path, denoted by Pus, from node u to root node s. Then, v,u∪Pus is a directed path from node v to root node s.Case 3.v∈Sa−Sd. A similar argument in Case 2 can be used here.
Next, we show thatS≤319/15k3+116/5k2+29/5kopt+29/3k3+116/5k2+87/5k+13/15. We first show that the set of black nodes L0 produced by unidTree (Algorithm 2) is an independent set for the graph run by unidTree (Algorithm 2). As the proof of Lemma 10, assume that L0=v0,v1,…,vk, where v0=s, and vi1≤i≤k is the node added to L0 after the ith iteration (see lines 5–7). Since there exist two hops from vi to vi+1, vi,vi+1∉E, which implies that vi,vi+1 is independent. By lines 5–8, we conclude that, for any two nodes vi,vj∈L0j≥i+2, vi is not an incoming neighbor of vj. Hence, L0 is an independent set for the graph run by unidTree (Algorithm 2). By Lemma 11, it is obtained that C≤2L0−1≤2αG−1, where αG is the bound of the maximum independent set for the strongly connected directed graph G=V,E. After line 8 of Algorithm 1, we have that S=Sd∪Saands∈Sd∩Sa, which means that S≤Sd+Sa−1≤2C−1≤4αG−3. By Theorem 2, we have(15)S≤31915k3+1165k2+295kopt+293k3+1165k2+875k+1315.


## 5. Simulation

In this section, we employ simulations to analyse the performance (in terms of the number of nodes in SCDAS) of our algorithm, denoted by LYZLLQ, by making a comparison with the work in [18], which has been used in [28] to compute SCDAS and the work in [29]. We call them EMP and CDS-BFS from now on. More specifically, we investigate how the network density and the ratio of the transmission range impact the performance of each scheme in terms of the size of the SCDAS. First, let us introduce the procedure for a candidate of a strongly connected network for simulation. Let a given number of nodes be randomly distributed in an area with a given size, and we randomly select each node’s transmission range according to a given range of transmission ranges rmin,rmax. After such a network has been generated, it is necessary to determine if it is strongly connected. If this network is not strongly connected, it will be abandoned; otherwise, it is considered a candidate for the simulations. Repeating this procedure, 1000 network candidates can be obtained. For each candidate network, we compute the performance of LYZLLQ, EMP, and CDS-BFS, respectively, and take the average value as the result of the simulations. Figures 6 and 7 are network candidates generated by the above method, which has 20 nodes distributed in a spatial area of size 1000m×1000m×1000m, where Figure 6 shows the connected relationship of nodes in the network and Figure 7 shows the positions of the 20 nodes in the network.Figure 6
A 20-node strongly connected network with different transmission ranges.Figure 7
Illustration of the positions of nodes in a 20-node strongly connected network.


### 5.1. Impact of Network Density When Varying the Number of Nodes

Suppose that the size of the fixed three-dimensional virtual space is1000m×1000m×1000m and that the range of network transmission ranges is rmin,rmax, where rmin=200m andrmax=600m. We randomly deploy nodes in such a fixed virtual space. Assume that the number of nodes n changes from 10 to 150, with an increment of 10. Each node chooses a transmission range in rmin,rmax. For each n, we investigate 1000 network candidates and take the average value as the result of the simulations.Figure8 shows the results of the simulations with respect to the performance of LYZLLQ, EMP, and CDS-BFS as the number of nodes increases. In Figure 8, it is easily seen that, as the size of the network increases, the number of nodes in the SCDAS increases for LYZLLQ, EMP, and CDS-BFS, respectively. More specifically, for LYZLLQ, when the size of the network n changes in the range 10,40, the number of nodes in SCDAS chosen by LYZLLQ is more than 50% of the total number of nodes n in the network. When n=80,110,and130, the number of nodes in SCDAS chosen by LYZLLQ is approximately 39%,32%,and29% of n. For EMP, when the size of the network n changes in the range 10,40, the number of nodes in SCDAS chosen by EMP is also more than 50% of the total number of nodes n in the network. When n=80,110,and130, the number of nodes in SCDAS chosen by EMP is approximately 64%,62%,and60% of n. For CDS-BFS, when the size of the network n changes in the range 10,40, the number of nodes in SCDAS chosen by CDS-BFS is also more than 50% of the total number of nodes n in the network. When n=80,110,and130, the number of nodes in SCDAS chosen by LYZLLQ is approximately 43%,36%,and33% of n.Figure 8
Impact of the number of nodes on the performance of the SCDAS.Naturally, the sparser the network is, the larger the number of nodes contained by an SCDAS of the network, and the denser a network is, the smaller the number of nodes contained by an SCDAS of the network. Figure8 shows that when n, the size of the network, changes in [10, 17], the size of the SCDAS in EMP [18] is lightly less than that in LYZLLQ (our algorithm) and the size of the SCDAS in LYZLLQ is lightly less than that in CDS-BFS [29]. However, when n is more than 20, the size of the SCDAS in EMP is larger than that in CDS-BFS and the size of the SCDAS in CDS-BFS is larger than that in LYZLLQ (our algorithm) and the difference of them increases as n increases. This shows that the performance of our algorithm in terms of the size of SCDAS is better than that of [18, 28] and that of [29] in a given set of nodes nn≥20.


### 5.2. Impact of Network Density When Varying the Spatial Size of the Network

In the previous section, we evaluate the impact of the network density when varying the number of nodes on the performance of the algorithms. In this section, we consider the impact of the network density when the spatial size of the network is varied. In the experiment, let us fix the number of nodes in a network to be 100, and we change the size of the network from600m×600m×600m to 1300m×1300m×1300m with an edge-length increment of 100. In addition, we randomly arranged 100 nodes in the area with size varying as described above, and we randomly set up a value for the transmission range in the range of 200m,600m for each node. For each case (in terms of the area), we generated 1000 candidates of the network according to the method described in the start of this section, and then, we ran the simulations for each network candidate and averaged the results of 1000 network candidates.Figure9 shows the size of the SCDAS output by the algorithms under the impact of network density when varying the area with a fixed number of nodes. As the area of the network increases, the size of the SCDAS increases almost linearly. More specifically, for LYZLLQ, when the edge length of the area l=600m,700m, and 800m, SCDAS contains approximately 13, 18, and 23 nodes (the number of nodes in each candidate network is always 100), and when the edge length of the area is l=1100m,1200m, and 1300m, SCDAS contains approximately 38, 43, and 47 nodes, respectively. For EMP, when the edge length of the area l=600m,700m, and 800m, SCDAS contains approximately 27, 38, and 48 nodes, and when the edge length of the area is l=1100m,1200m, and 1300m, SCDAS contains approximately 67, 71, and 72 nodes, respectively. Now, let us consider the situation of CDS-BFS, when the edge length of the area l=600m,700m, and 800m, SCDAS contains approximately 17, 22, and 27 nodes, and when the edge length of the area is l=1100m,1200m, and 1300m, SCDAS contains approximately 43, 48, and 52 nodes, respectively.Figure 9
The impact of the network density when varying the spatial size.Intuitively, this follows the law mentioned in the previous section: the sparser a network is, the greater the number of nodes contained in an SCDAS of the network. In the case, the size of SCDAS output by our algorithm is at least 14 less than that output by the relative algorithm in [18] or [28] and is at least 4 less than that output by the algorithm in [29], which implies that the performance of our algorithm is better than that of both the algorithms in [18, 28, 29].


### 5.3. Impact of Varying the Transmission Range Ratio

In this section, to change the ratio of the transmission rangek=rmax/rmin, we fixed rmin=200m and changed rmax from 200 m to 800 m with an increment of 100. In this experiment, we deployed 100 nodes in a fixed area of size 1000m×1000m×1000m. We randomly chose a transmission range in rmin,rmax for each node. For each case (in terms of the ratio of transmission ranges k=rmax/rmin), we generated 1000 network candidates according to the method described in the first part of this section. Then, we ran the simulations for each network candidate and averaged the results of 1000 network candidates.Figure10 shows the change in the number of nodes in SCDAS as the ratio of the transmission range k varies. As the ratio of the transmission range k increases, the number of nodes in the SCDAS decreases, and as k increases with step length 0.5 from k=3, the decrement of the number of nodes in the SCDAS becomes small. More specifically, for LYZLLQ, when k=2and2.5, the number of nodes in SCDAS is approximately 48 and 39, respectively, and when k=3.5​and4, the number of nodes in SCDAS is 29 and 25, respectively. For EMP, when k=2and2.5, the number of nodes in SCDAS is approximately 74 and 69, respectively, and when k=3.5and4, the number of nodes in SCDAS is 55 and 48, respectively. Similarly, we can find that for CDS-BFS, when k=2and2.5, the number of nodes in SCDAS is approximately 52 and 44, respectively, and when k=3.5and4, the number of nodes in SCDAS is 34 and 32, respectively. Intuitively, the larger the k is, the larger the maximum transmission range rmax. Then, it is possible that the transmission range of the randomly chosen node will be larger, which results in fewer nodes in the SCDAS. In the case, the size of SCDAS output by our algorithm is at least 23 less than that output by the relative algorithm in [18] or [28] and is at least 4 less than that output by the relative algorithm in [29]. This can also explain that the performance of our algorithm is better than that of the algorithm, which is better than that of the algorithm in [29] and [18, 28].Figure 10
The impact of the ratio of the transmission range.


## 5.1. Impact of Network Density When Varying the Number of Nodes

Suppose that the size of the fixed three-dimensional virtual space is1000m×1000m×1000m and that the range of network transmission ranges is rmin,rmax, where rmin=200m andrmax=600m. We randomly deploy nodes in such a fixed virtual space. Assume that the number of nodes n changes from 10 to 150, with an increment of 10. Each node chooses a transmission range in rmin,rmax. For each n, we investigate 1000 network candidates and take the average value as the result of the simulations.Figure8 shows the results of the simulations with respect to the performance of LYZLLQ, EMP, and CDS-BFS as the number of nodes increases. In Figure 8, it is easily seen that, as the size of the network increases, the number of nodes in the SCDAS increases for LYZLLQ, EMP, and CDS-BFS, respectively. More specifically, for LYZLLQ, when the size of the network n changes in the range 10,40, the number of nodes in SCDAS chosen by LYZLLQ is more than 50% of the total number of nodes n in the network. When n=80,110,and130, the number of nodes in SCDAS chosen by LYZLLQ is approximately 39%,32%,and29% of n. For EMP, when the size of the network n changes in the range 10,40, the number of nodes in SCDAS chosen by EMP is also more than 50% of the total number of nodes n in the network. When n=80,110,and130, the number of nodes in SCDAS chosen by EMP is approximately 64%,62%,and60% of n. For CDS-BFS, when the size of the network n changes in the range 10,40, the number of nodes in SCDAS chosen by CDS-BFS is also more than 50% of the total number of nodes n in the network. When n=80,110,and130, the number of nodes in SCDAS chosen by LYZLLQ is approximately 43%,36%,and33% of n.Figure 8
Impact of the number of nodes on the performance of the SCDAS.Naturally, the sparser the network is, the larger the number of nodes contained by an SCDAS of the network, and the denser a network is, the smaller the number of nodes contained by an SCDAS of the network. Figure8 shows that when n, the size of the network, changes in [10, 17], the size of the SCDAS in EMP [18] is lightly less than that in LYZLLQ (our algorithm) and the size of the SCDAS in LYZLLQ is lightly less than that in CDS-BFS [29]. However, when n is more than 20, the size of the SCDAS in EMP is larger than that in CDS-BFS and the size of the SCDAS in CDS-BFS is larger than that in LYZLLQ (our algorithm) and the difference of them increases as n increases. This shows that the performance of our algorithm in terms of the size of SCDAS is better than that of [18, 28] and that of [29] in a given set of nodes nn≥20.


## 5.2. Impact of Network Density When Varying the Spatial Size of the Network

In the previous section, we evaluate the impact of the network density when varying the number of nodes on the performance of the algorithms. In this section, we consider the impact of the network density when the spatial size of the network is varied. In the experiment, let us fix the number of nodes in a network to be 100, and we change the size of the network from600m×600m×600m to 1300m×1300m×1300m with an edge-length increment of 100. In addition, we randomly arranged 100 nodes in the area with size varying as described above, and we randomly set up a value for the transmission range in the range of 200m,600m for each node. For each case (in terms of the area), we generated 1000 candidates of the network according to the method described in the start of this section, and then, we ran the simulations for each network candidate and averaged the results of 1000 network candidates.Figure9 shows the size of the SCDAS output by the algorithms under the impact of network density when varying the area with a fixed number of nodes. As the area of the network increases, the size of the SCDAS increases almost linearly. More specifically, for LYZLLQ, when the edge length of the area l=600m,700m, and 800m, SCDAS contains approximately 13, 18, and 23 nodes (the number of nodes in each candidate network is always 100), and when the edge length of the area is l=1100m,1200m, and 1300m, SCDAS contains approximately 38, 43, and 47 nodes, respectively. For EMP, when the edge length of the area l=600m,700m, and 800m, SCDAS contains approximately 27, 38, and 48 nodes, and when the edge length of the area is l=1100m,1200m, and 1300m, SCDAS contains approximately 67, 71, and 72 nodes, respectively. Now, let us consider the situation of CDS-BFS, when the edge length of the area l=600m,700m, and 800m, SCDAS contains approximately 17, 22, and 27 nodes, and when the edge length of the area is l=1100m,1200m, and 1300m, SCDAS contains approximately 43, 48, and 52 nodes, respectively.Figure 9
The impact of the network density when varying the spatial size.Intuitively, this follows the law mentioned in the previous section: the sparser a network is, the greater the number of nodes contained in an SCDAS of the network. In the case, the size of SCDAS output by our algorithm is at least 14 less than that output by the relative algorithm in [18] or [28] and is at least 4 less than that output by the algorithm in [29], which implies that the performance of our algorithm is better than that of both the algorithms in [18, 28, 29].


## 5.3. Impact of Varying the Transmission Range Ratio

In this section, to change the ratio of the transmission rangek=rmax/rmin, we fixed rmin=200m and changed rmax from 200 m to 800 m with an increment of 100. In this experiment, we deployed 100 nodes in a fixed area of size 1000m×1000m×1000m. We randomly chose a transmission range in rmin,rmax for each node. For each case (in terms of the ratio of transmission ranges k=rmax/rmin), we generated 1000 network candidates according to the method described in the first part of this section. Then, we ran the simulations for each network candidate and averaged the results of 1000 network candidates.Figure10 shows the change in the number of nodes in SCDAS as the ratio of the transmission range k varies. As the ratio of the transmission range k increases, the number of nodes in the SCDAS decreases, and as k increases with step length 0.5 from k=3, the decrement of the number of nodes in the SCDAS becomes small. More specifically, for LYZLLQ, when k=2and2.5, the number of nodes in SCDAS is approximately 48 and 39, respectively, and when k=3.5​and4, the number of nodes in SCDAS is 29 and 25, respectively. For EMP, when k=2and2.5, the number of nodes in SCDAS is approximately 74 and 69, respectively, and when k=3.5and4, the number of nodes in SCDAS is 55 and 48, respectively. Similarly, we can find that for CDS-BFS, when k=2and2.5, the number of nodes in SCDAS is approximately 52 and 44, respectively, and when k=3.5and4, the number of nodes in SCDAS is 34 and 32, respectively. Intuitively, the larger the k is, the larger the maximum transmission range rmax. Then, it is possible that the transmission range of the randomly chosen node will be larger, which results in fewer nodes in the SCDAS. In the case, the size of SCDAS output by our algorithm is at least 23 less than that output by the relative algorithm in [18] or [28] and is at least 4 less than that output by the relative algorithm in [29]. This can also explain that the performance of our algorithm is better than that of the algorithm, which is better than that of the algorithm in [29] and [18, 28].Figure 10
The impact of the ratio of the transmission range.


## 6. Conclusion

In this paper, we mainly study the problem of constructing MSCDASs in a directed strongly connected ball graph with different transmission ranges for its nodes, which is NP-hard for obtaining an optimal solution. To obtain a constant factor approximation solution for MSCDASs in a strongly directed connected ball graph, we proposed an algorithm that produces an SCDAS by computing a dominating set and an absorbing set. We proved that the dominating set and absorbing set are independent sets. To obtain the ratio of the SCDAS to MSCDAS, we first proved that the upper bound of the number of nodes in MIS in a directed strongly connected ball graph is319/15k3+116/5k2+29/5kopt+29/3k3+116/5k2+87/5k+13/15. Using the upper bound, we derived that the size of the SCDAS generated by the algorithm proposed in the paper does not exceed 319/15k3+116/5k2+29/5kopt+29/3k3+116/5k2+87/5k+13/15.



---

*Source: 9189645-2020-02-24.xml*