# Asymptotic Distribution of Isolated Nodes in Secure Wireless Sensor Networks under Transmission Constraints

Authors: Y. Tang; Q. L. Li
Journal: Discrete Dynamics in Nature and Society
 (2016)

---

## Abstract

The Eschenauer-Gligor (EG) key predistribution is regarded as a typical approach to secure communication in wireless sensor networks (WSNs). In this paper, we establish asymptotic results about the distribution of isolated nodes and the vanishing small impact of the boundary effect on the number of isolated nodes in WSNs with the EG scheme under transmission constraints. In such networks, nodes are distributed either Poissonly or uniformly over a unit square. The results reported here strengthen recent work by Yi et al.


---

## Body

## 1. Introduction

A wireless sensor network is composed of a collection of wireless sensors distributed over a geographic region. A wireless sensor network can be an integral part of military command, control, communication, computing, intelligence, surveillance, reconnaissance, and target system. It has been the subject of intense research in recent decades. Asymptotic analysis, valid when the number of nodes in the network is large enough, has been useful for understanding the characteristic of the network.In many applications, a large number of wireless sensors are independently and uniformly deployed in the sensor field. They can be deployed by dropping from a plane or delivered in a missile. To model such a randomly deployed wireless sensor network, it is natural to represent the sensor nodes by a finite random point process over a network square areaS. In addition, due to the short transmission range of communication links, two wireless sensors can build a link if and only if they are within each other’s transmission range. Assume all n sensors have the same transmission range of radius r
n, then the induced network topology is a r
n-disk graph in which two nodes are joined by an edge if and only if their distance is at most r
n. This model is proposed by Gilbert [1] and referred to as a random geometric graph, denoted by G
(
n
,
r
n
,
S
).However, in many applications, a wireless sensor network is composed of low cost sensors. Due to the limited capacity, traditional security schemes and key management algorithms are too complicated and not feasible for such a system. The Eschenauer-Gligor (EG) [2] key predistribution scheme is a widely recognized way to secure communication. In this scheme, in a WSN with n sensors and sensor set V
=
{
v
1
,
v
2
,
…
,
v
n
}, the EG scheme independently assigns a set of K
n distinct cryptographic keys, which are selected uniformly at random from a pool of P
n keys, to each sensor node; the set of keys of each sensor is called the key ring and is denoted by S
x for sensor v
x. The EG scheme is denoted by a random key graph G
(
n
,
K
n
,
P
n
) in [3–6], in which an edge exists between two nodes v
x and v
y if and only if they possess at least one common key; that is, S
x
∩
S
y
≠
∅.In a WSN using the EG scheme under transmission constraint, two sensorsv
x and v
y establish a direct link between them if and only if they share at least one key and their distance is no greater than r
n. We denote the event establishing this direct link by E
x
y. If we let the graph G
(
n
,
θ
n
,
S
) model such a WSN, it is obvious to see G
(
n
,
θ
n
,
S
) is the intersection of random key graph G
(
n
,
K
n
,
P
n
) and random geometric graph G
(
n
,
r
n
,
S
) with n nodes uniformly distributed over a square S; namely, (1)Gn,θn,S=Gn,Kn,Pn∩Gn,rn,S,where θ
n represents the parameters K
n
,
P
n, and r
n together.Letv
x
^
∈
S be the location of point v
x. A direct link E
x
y exists in G
(
n
,
θ
n
,
S
) if both of the following two conditions are satisfied: (2)vx^-vy^≤rn;Sx∩Sy≠∅,where ∥
·
∥ represents the Euclidean norm.We letp
s be the probability of key sharing between two sensors and note that p
s is also the edge probability in random key graph G
(
n
,
K
n
,
P
n
). It holds that (3)ps=PSx∩Sy≠∅.Clearly ifP
n
<
2
K
n, then p
s
=
1. If P
n
≥
2
K
n, as shown in previous work [5–7], we have (4)ps=1-Pn-KnKnPnKn.If P
n
≥
2
K
n, by [8], it further holds that(5)ps≤Kn2Pn.By [9], (5) implies that if K
n
2
/
P
n
=
o
(
1
), then(6)ps=Kn2Pn·1-OKn2Pn~Kn2Pn.We will use (5) and (6) throughout the paper.Letp
e be the probability that a secure link exists between two sensors in the WSN with EG scheme under practical constraint; obviously, p
e is the edge probability in G
(
n
,
θ
n
,
S
). It holds that p
e
=
P
[
E
x
y
]. It is simple matter to show p
e
≤
π
r
n
2
·
p
s and p
e
≥
(
1
-
2
r
n
)
2
π
r
n
2
·
p
s, if r
n
=
o
(
1
), p
e
~
π
r
n
2
·
p
s. Therefore if r
n
=
o
(
1
) and K
n
2
/
P
n
=
o
(
1
), we get p
e
~
π
r
n
2
·
K
n
2
/
P
n in view of (6).The secure wireless sensor network with nodes uniformly distributed is modeled by graphG
(
n
,
θ
n
,
S
), in which two nodes have an edge if their Euclidean distance is at most r
n and have a secure link if their key rings have at least one common key. Compared to the work done by Yi et al. [10], in this paper, by using a different method, we establish that the number of isolated nodes in the secure wireless sensor network has an asymptotic Poisson distribution whether the n nodes are induced by a uniform point process or Poisson point process.To model transmission constraints, we use the popular disk model [11], and under the disk model, two nodes are directly connected if and only if their Euclidean distance is smaller or equal to a given threshold r
n, where parameter r
n is termed as the transmission range.The following notations are used throughout the paper:(i)
a
(
n
)
=
o
(
b
(
n
)
) if l
i
m
n
→
∞
a
(
n
)
/
b
(
n
)
→
0;
(ii)
a
(
n
)
=
ω
(
b
(
n
)
) if l
i
m
n
→
∞
b
(
n
)
/
a
(
n
)
→
0;
(iii)
a
(
n
)
~
b
(
n
) if l
i
m
n
→
∞
a
(
n
)
/
b
(
n
)
→
1;
(iv)
a
(
n
)
=
Θ
(
b
(
n
)
) if there exist sufficiently n
0 and c
1
,
c
2
>
0 such that, for any n
>
n
0, c
1
b
(
n
)
≤
a
(
n
)
≤
c
2
b
(
n
);
(v)
a
(
n
)
=
Ω
(
b
(
n
)
) if there exist sufficiently n
0 and C
>
0 such that, for any n
>
n
0, a
(
n
)
≥
C
b
(
n
);
(vi)
the notation “l
n” stands for the natural logarithm function.The rest of the paper is organized as follows. Section2 reviews related work. Section 3 comparatively studies the distribution of isolated nodes in WSNs employing the EG scheme with nodes Poissonly or uniformly distributed over a unit square S. Through the study, it shows that under certain conditions the impact of boundary effect on the number of isolated nodes is negligible. Finally, Section 4 summarizes conclusions and discusses prospects of establishing the distribution of isolated nodes and tighter connectivity thresholds for secure wireless sensor networks under improved conditions.


## 2. Related Work

With regard to the sensor distribution, we consider thatn nodes are independently and uniformly deployed in unit square area S. The disk model induces a random geometric graph [4, 12–15] which is denoted by G
(
n
,
r
n
,
S
); an edge exists between two sensors if and only if their Euclidean distance is no more than r
n. Extensive research has been done on random geometric graphs. The connectivity of random geometric graphs has been studied by Dette and Henze [16], Penrose [17], and others [12, 18–20]. For a uniform n point process over a unit area square S, Dette and Henze [16] showed that, for any constant c, if r
n
=
ln
⁡
n
+
c
/
π
n, then graph G
(
n
,
r
n
,
S
) has no isolated nodes with probability e
-
c asymptotically. Eight years later, Penrose [14] established that if a random geometric graph induced by a uniform point process or Poisson point process has no isolated nodes, then it is almost surely connected. Besides the overall connectivity, some applications are concerned with whether there exists a giant connected component. Continuum percolation is a useful theorem in analyzing threshold phenomena. Ammari and Das [21] focused on percolation in coverage and connectivity in three-dimensional space and found out whether the network provides long distance multihop communication.For random key graphG
(
n
,
K
n
,
P
n
), Godehardt and Jaworshi [22] focused on the distribution of the number of isolated vertices in G
(
n
,
K
n
,
P
n
). Some partial results concerning the connectivity of random key graphs were given in [6, 7, 23]. In [5], Rybarczyk gave asymptotic tight bounds for the thresholds of the connectivity, phase transition, and diameter of the largest connected component in random key graphs for all ranges of K
n. Other related works regarding G
(
n
,
K
n
,
P
n
) model have been reported. For example, Bloznelis et al. [24] treated the evolution of the order of the largest component. Connectivity and communication security aspects of G
(
n
,
K
n
,
P
n
) in various important settings are also studied in [7, 25, 26]. Although some properties of secure WSNs with the EG scheme have been extensively studied in [4–7, 13, 27], most research [5–7, 27] unrealistically assumes unconstrained sensor-to-sensor communications; that is to say, any two sensors can communicate regardless of the distance between them.Recently, there is interest in random graphs in which an edge is determined by more than one random property, that is, intersection of different random graphs. The intersection of Erdős-Rényi random graphG
(
n
,
p
) [28] and random geometric graph G
(
n
,
r
n
,
S
) has been of interest for quite some time now. Recent work on such random graphs is by [20, 29] where connectivity properties and the distribution of isolated nodes are analyzed. And the intersection of random graphs G
(
n
,
p
) and random key graph G
(
n
,
K
n
,
P
n
) is considered in [30]. Such a graph is constructed as follows: a random key graph G
(
n
,
K
n
,
P
n
) is first formed based on the key distribution and each edge in this graph is deleted with a specified probability.The intersection of random key graphG
(
n
,
K
n
,
P
n
) and random geometric graph G
(
n
,
r
n
,
S
) (i.e., G
(
n
,
θ
n
,
S
)) is first studied in [31]. Di Pietro et al. [31] have shown that, under the scaling π
r
n
2
K
n
2
/
P
n
=
c
ln
⁡
n
/
n, the one law that this class of random graphs is connected follows if r
n
>
0 and c
>
20
π. Another notable work is due to Krzywdziński and Rybarczyk [13], where the authors have improved this result and established that, in G
(
n
,
θ
n
,
S
), if π
r
n
2
K
n
2
/
P
n
=
8
ln
⁡
n
/
n with K
n
>
2, P
n
=
ω
(
1
), and without any constraint on r
n, then G
(
n
,
θ
n
,
S
) is almost surely connected. And Krishnan et al. [4] demonstrated that if π
r
n
2
K
n
2
/
P
n
≥
2
π
ln
⁡
n
/
n with K
n
=
ω
(
1
) and K
n
2
/
P
n
=
o
(
1
), then G
(
n
,
θ
n
,
S
) is almost surely connected. Recently, Tang and Li [32] and Zhao et al. [33] presented the first zero-one laws for connectivity in G
(
n
,
θ
n
,
S
); these laws improve the results [4, 13] significantly and help specify the critical transmission ranges for connectivity. Also the distribution of isolated nodes in G
(
n
,
θ
n
,
S
) is considered by Yi et al. [10] and Pishro-Nik et al. [34], where the network with n nodes distributed uniformly over a unit disk D or a unit square S.In addition to random key graphs and random geometric graphs, the Erdös-Rényi graphG
(
n
,
p
) [28] has also been extensively studied. An Erdös-Rényi graph G
(
n
,
p
) is defined on a set of n nodes such that any two nodes establish an edge independently with probability p. As already shown in the literature [5–7, 27], random key graph G
(
n
,
K
n
,
P
n
) and Erdös-Rényi graph G
(
n
,
p
) have similar connectivity properties when they are matched through edge probability; that is, p
s
=
p. Hence, it would be tempting to exploit this analogue and conclude that the distribution of isolated nodes in G
(
n
,
θ
n
,
S
)
(
G
(
n
,
K
n
,
P
n
)
∩
G
(
n
,
r
n
,
S
)
) is similar to that of G
(
n
,
p
)
∩
G
(
n
,
r
n
,
S
) in [20], whether the n nodes are distributed Poissonly or uniformly on a unit square S.


## 3. Main Result

In this section, we study the expected number of isolated nodes in WSNs with the EG scheme under transmission constraints with nodes either Poissonly or uniformly on a unit squareS. The number of isolated nodes is a key parameter in the analysis of network connectivity. A necessary condition for a network to be connected is that the network has no isolated nodes, and this may be possibly true for the intersection of random key graph and random geometric graph.In order to obtain the distribution of isolated nodes inG
(
n
,
θ
n
,
S
), we prove the same result for its Poissonized version, graph G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
), where the only difference between G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
) and G
(
n
,
θ
n
,
S
) is that the node distribution of the former is a homogeneous Poisson point process with intensity n on a unit square S while that of the latter is a uniform n point process.


### 3.1. Expected Number of Isolated Nodes inG
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
)

In graphG
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
), let I
x denote the event that node v
x is isolated, and let D
r
n
(
v
x
^
) denote the intersection of S and the disk centered at position v
x
^
∈
S with radius r
n. When node v
x is at position v
x
^, the number of nodes within area D
r
n
(
v
x
^
) follows a Poisson distribution with mean n
D
r
n
(
v
x
^
), and to have an edge with v
x in graph G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
), a node not only has to be within D
r
n
(
v
x
^
) but also has to share at least a key with node v
x. Then the number of nodes neighboring to v
x at v
x
^ follows a Poisson distribution with mean n
p
s
D
r
n
(
v
x
^
), and the probability that such number is 0 is equal to e
-
n
p
s
D
r
n
v
x
^. Integrating v
x
^ over S, then the probability that the node v
x is isolated is given by(7)PIx=∫Se-npsDrnvx^dvx^.Theorem 1.
Suppose thatK
n
2
/
P
n
=
o
(
1
), p
s
=
ω
(
1
/
ln
⁡
n
), and n nodes are Poissonly distributed on a unit square S with the maximum transmission radius π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n for some constant c. Then the expected number of isolated nodes in G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
) converges asymptotically to e
-
c as n
→
∞.Proof.
LetW denote the number of isolated nodes in graph G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
). By (7), we know P
(
I
x
)
=
∫
S
e
-
n
p
s
D
r
n
v
x
^
d
v
x
^ holds. To compute P
(
I
x
) based on S, we divide S in a way similar to that by Li et al. [35] and Wan and Yi [15]. Specially, S is divided into S
0
,
S
1
,
S
2, and S
3, respectively, as illustrated in Figure 1 (note that r
n
=
o
(
1
)). S
0 consists of all points each with a distance greater than r
n to its nearest edge to S, whereas S
3 is a square of size r
n
×
r
n at the four corners of S. We further divide S
∖
{
S
0
∪
S
3
} into S
1 and S
2 as follows. In S
∖
{
S
0
∪
S
3
}, S
1 contains points whose distance to the nearest edge of S is no greater than r
n
/
2, while the remaining area is S
2. Then the expected number of isolated nodes is given by (8)limn→∞EW=limn→∞nPIx=limn→∞n∫Se-npsDrnvx^dvx^=limn→∞n∫S0e-npsDrnvx^dvx^+limn→∞n∫S1e-npsDrnvx^dvx^+limn→∞n∫S2e-npsDrnvx^dvx^+limn→∞n∫S3e-npsDrnvx^dvx^.The four summands in (8) represent, respectively, the expected number of isolated nodes in the central area S
0, in the boundary area along the four sides of S, and in the four corners of S. In the following analysis, we will show that the first term approaches e
-
c as n
→
∞, and the remaining terms approach 0 an n
→
∞.
Consider the first summand in (8). It is clear that, for any position v
x
^
∈
S
0, we have |
D
r
n
(
v
x
^
)
|
=
π
r
n
2, and note that π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n, S
0
=
(
1
-
2
r
n
)
2 to get(9)limn→∞n∫S0e-npsDrnvx^dvx^=limn→∞n∫S0e-npsπrn2dvx^=limn→∞ne-npsπrn2∫S0dvx^=limn→∞e-c1-2rn2=e-c.
For the second term in (8), we introduce some notation as follows. For any position v
x
^
∈
S
1, we let the distance from v
x
^ to the nearest edge of square S be g, where 0
≤
g
≤
r
n
/
2. For v
x
^
∈
S
1, clearly |
D
r
n
(
v
x
^
)
| is determined by g, and we denote it by H
(
g
). It is easy to obtain(10)Hg=Drnvx^=πrn2-rn2arccos⁡grn+grn2-g2,(11)H′g=2rn2-g2,(12)H′′g=-2grn2-g2.
SinceS
1 consists of four retangles, each of which has length 1
-
2
r
n and width r
n
/
2, it follows that(13)limn→∞n∫S1e-npsDrnvx^dvx^=4n1-2rnlimn→∞∫0rn/2e-npsHgdg. For simplicity, we write H
(
g
) as H. Then(14)e-npsHgdg=-nps-1H′-1de-npsH=-nps-1·dH′-1e-npsH-e-npsHdH′-1=nps-1·d-H′-1e-npsH-H′-2H′′e-npsHdg.In view of (14), we further have(15)-H′-2H′′e-npsHdg=-H′-3H′′e-npsHdH=-nps-1H′-3H′′d-e-npsH.For 0
≤
g
≤
r
n
/
2, it holds from (11) and (12) that(16)-H′′H′3=g4rn2-g22≤rn/24×3/4rn22=29rn3.By (15) and (16), it follows that(17)-∫0rn/2H′-2H′′e-npsHdg≤29rn3psn∫0rn/2d-e-npsH.Applying (17) into (14),(18)
∫
0
r
n
/
2
e
-
n
p
s
H
g
d
g
=
1
n
p
s
∫
0
r
n
/
2
d
-
H
′
-
1
e
-
n
p
s
H
-
∫
0
r
n
/
2
H
′
-
2
H
′
′
e
-
n
p
s
H
d
g
≤
1
n
p
s
∫
0
r
n
/
2
d
-
H
′
-
1
e
-
n
p
s
H
+
2
9
r
n
3
p
s
n
∫
0
r
n
/
2
d
-
e
-
n
p
s
H
≤
e
-
n
p
s
H
0
n
p
s
H
′
0
+
2
e
-
n
p
s
H
0
9
r
n
3
p
s
2
n
2
.From (10) and (11), we obtain H
(
0
)
=
π
r
n
2
/
2 and H
′
(
0
)
=
2
r
n. Consider(19)∫0rn/2e-npsHgdg≤e-npsH0npsH′0+2e-npsH09rn3ps2n2=e-npsπrn2/22rnnps+2e-npsπrn2/29rn3ps2n2.Using π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n and (6) in (19), we derive(20)∫0rn/2e-npsHgdg≤e-npsπrn2/22rnnps1+o1.Using (20) in (13), we get(21)limn→∞n∫S1e-npsDrnvx^dvx^=4n1-2rnlimn→∞∫0rn/2e-npsHgdg≤4nlimn→∞e-npsπrn2/22rnnps1+o1.From K
n
2
/
P
n
=
o
(
1
)
,
p
s
=
ω
(
1
/
ln
⁡
n
), and with Δ denoting π
r
n
2
p
s
n (note that Δ
=
Θ
(
ln
⁡
n
)),(22)rn=π-1/2ps-1/2n-1/2Δ1/2.We obtain(23)limn→∞n∫S1e-npsDrnvx^dvx^=0.
Now we considerl
i
m
n
→
∞
n
∫
S
2
e
-
n
p
s
|
D
r
n
(
v
x
^
)
|
d
v
x
^. For v
x
^
∈
S
2, when the distance from v
x
^ to the nearest edge of square S is g, where r
n
/
2
≤
g
≤
r
n, the function expression of |
D
r
n
(
v
x
^
)
| still is H
(
g
). H
(
g
) is increasing with g for r
n
/
2
≤
g
≤
r
n by H
′
(
g
)
=
2
r
n
2
-
g
2
≥
0. Thus, when the distance from v
x
^ to the nearest edge of S equals r
n
/
2, the area |
D
r
n
(
v
x
^
)
| reaches its minimum value: (24)Drnvx^min=Hrn2=23+34ππrn2.With C
0 denoting 2
/
3
+
3
/
4
π, then |
D
r
n
(
v
x
^
)
|
m
i
n
=
C
0
π
r
n
2. And with |
S
2
|
=
2
r
n
(
1
-
2
r
n
), we derive (25)limn→∞n∫S2e-npsDrnvx^dvx^≤limn→∞n∫S2e-npsC0πrn2dvx^=limn→∞ne-npsC0πrn2∫S2dvx^≤2limn→∞rnne-npsC0πrn2.From p
s
=
ω
1
/
ln
⁡
n, Δ
=
Θ
(
ln
⁡
n
), and (22), it follows(26)limn→∞n∫S2e-npsDrnvx^dvx^=0.
For the last term in (8), we have 1
/
4
π
r
n
2
≤
|
D
r
n
(
v
x
^
)
|
≤
π
r
n
2 for any v
x
^
∈
S
3 and |
S
3
|
=
4
r
n
2 to get(27)limn→∞n∫S3e-npsDrnvx^dvx^≤nlimn→∞∫S3e-1/4npsπrn2dvx^=limn→∞ne-1/4npsπrn2∫S3dvx^=limn→∞4nrn2n-1/4e-1/4npsπrn2=0,where (22), Δ
=
Θ
(
ln
⁡
n
), and p
s
=
ω
1
/
ln
⁡
n are used in reaching (27).
As a result of (8),(9), (23), (26), and (27), we prove (28)limn→∞EW=e-c.
The parameterc in Theorem 1 is a constant, or it can depend on n, in which case c
=
o
(
ln
⁡
n
). The following corollary can be established.Figure 1
The unit squareS and its divisions S
0, S
1, S
2, and S
3.Corollary 2.
In graphG
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
) under conditions K
n
2
/
P
n
=
o
(
1
), p
s
=
ω
(
1
/
ln
⁡
n
), and π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n with c
=
o
(
ln
⁡
n
) or a constant c, then for any constant ϵ
>
0 such that E
(
W
)
=
o
(
n
ϵ
) holds.Now we examine the impact of boundary effect on the number of isolated nodes inG
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
) since the network area in our analysis is a square. The square accounts for the real-world boundary effect whereby some transmission region of a sensor close to the network boundary may fall outside the network field. In contrast, the torus eliminates the boundary effect. The analysis of impact of the boundary effect is done by comparing the number of isolated nodes in G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
) and the number in a network with nodes Poissonly distributed on a unit torus S
T with a pair of nodes v
x
,
v
y separated by a toroidal distance v
x
^
-
v
y
^
T. Denote such network on a unit torus by G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
). The following Theorem can be established.Theorem 3.
Suppose thatK
n
2
/
P
n
=
o
(
1
), p
s
=
ω
(
1
/
ln
⁡
n
), and n nodes are Poissonly distributed on a unit torus S
T with the maximum transmission radius π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n for some constant c. Then the expected number of isolated nodes in G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
) converges to e
-
c as n
→
∞.Proof.
LetW
T denote the number of isolated nodes in graph G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
), and let D
r
n
T
(
v
x
^
) denote the intersection of S
T and the disk centered at position v
x
^
∈
S
T with radius r
n. The probability that node v
x is isolated is P
(
I
x
T
)
=
∫
S
T
‍
e
-
n
p
s
|
D
r
n
T
(
v
x
^
)
|
d
v
x
^. Since S
T is a unit torus, it holds that |
D
r
n
T
(
v
x
^
)
|
=
π
r
n
2 for any v
x
^
∈
S
T. Then(29)PIxT=∫STe-npsDrnTvx^dvx^=e-πrn2psn∫STdvx^=e-πrn2psn·ST=e-πrn2psn.Using the condition π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n, we obtain (30)limn→∞EWT=limn→∞nPIxT=limn→∞ne-πrn2psn=e-c.On the basis of Theorems1 and 3, using the coupling technique, the following theorem can be obtained.Theorem 4.
Suppose thatK
n
2
/
P
n
=
o
(
1
), p
s
=
ω
(
1
/
ln
⁡
n
), and n nodes are Poissonly distributed on a unit square S with the maximum transmission radius π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n for some constant c. Then the number of isolated nodes in G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
) due to the boundary effect converges asymptotically to 0 as n
→
∞.Proof.
Comparing Theorems1 and 3, it is noted that the expected numbers of isolated nodes on a unit torus S
T and on a unit square S, respectively, asymptotically converge to the same constant e
-
c as n
→
∞. Now we use the coupling technique [36] to construct the connection between W and W
T. Consider a graph G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
), and the number of isolated nodes in that graph is W
T. Remove each connection of the above graph with probability 1
-
|
D
r
n
(
v
x
^
)
|
/
|
D
r
n
T
(
v
x
^
)
|, independently of the event that another connection is removed. Due to |
D
r
n
(
v
x
^
)
|
≤
|
D
r
n
T
(
v
x
^
)
|, then 0
≤
1
-
|
D
r
n
(
v
x
^
)
|
/
|
D
r
n
T
(
v
x
^
)
|
≤
1. We further note that only connections between nodes near the boundary will be affected. Denote the number of newly appearing isolated nodes by W
E; namely, W
E is the number of isolated nodes due to the boundary effect; it is straightforward to show that W
E is a nonnegative random integer. Further, such a connection removal process results in a random network with nodes Poissonly distributed with density n. That is, a random network on a unit square with boundary effect is included. The following equation result holds: (31)W=WE+WT.By Theorems 1 and 3 and the above equation, it can be shown that (32)limn→∞EWE=limn→∞EW-WT=0.Due to the nonnegativity of W
E, (33)limn→∞PWE=0=1.


### 3.2. Distribution of the Number of Isolated Nodes inG
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
)

In this subsection, we analyze the distribution of the number of isolated nodes inG
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
). For this purpose, we give some definitions. Let Poi(λ) be a Poisson random variable with parameter λ.LetΓ be a finite set of indices and let (
I
a
)
a
∈
Γ be a family of random indicator variables. We say (
I
a
)
a
∈
Γ are positively related (see [37]), if, for each a
∈
Γ, there exist random indicator variables (
J
b
a
)
b
∈
Γ
∖
{
a
} with the distributions (34)LJbab∈Γ∖a=LIbb∈Γ∖a∣Ia=1, such that J
b
a
≥
I
b for every b
≠
a.A useful result obtained by Stein-Chen method is the following.Lemma 5 (see [37, 38]).
Suppose thatY
=
∑
a
∈
Γ
‍
I
a, where the indicator variables (
I
a
)
a
∈
Γ are positively related random indicator variables. Then one has (35)dTVY,PoiEY≤1-e-EYEYVar⁡Y-EY+2∑a∈ΓEIa2.Forx
=
1
,
…
,
n, let I
x
T
=
1 if node v
x is isolated in G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
) and W
T
=
∑
x
=
1
n
I
x
T. Therefore, W
T is the number of isolated nodes in G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
) as defined in Theorem 3. We will demonstrate the asymptotic Poisson distribution of W
T by employing the Stein-Chen method [37]. The result is given in Theorem 6.Theorem 6.
SupposeK
n
≥
ln
⁡
n
/
ln
⁡
ln
⁡
n, K
n
2
/
P
n
=
o
(
1
), p
s
=
ω
1
/
ln
⁡
n, and n nodes are Poissonly distributed on a unit torus S
T with the maximum transmission radius π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n for some constant c. Then the distribution of the number of isolated nodes in G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
) converges to a Poisson distribution with mean e
-
c as n
→
∞.Proof.
The triangular inequality for the total variation distance implies(36)dTVWT,Poie-c≤dTVWT,PoiEWT+dTVPoiEWT,Poie-c. By a coupling argument [39] and Theorem 3, we have(37)dTVPoiEWT,Poie-c≤EWT-e-c=o1. Combining this with (36), we now only need to prove(38)limn→∞dTVWT,PoiEWT=0.
First, we claim that(
I
x
T
)
x
=
1
n are positively related. To see this, define (39)IyxT=1ifnodevyisisolatedinGPoissonTn,θn′,S1T,where G
P
o
i
s
s
o
n
T
(
n
,
θ
n
′
,
S
1
T
) is a graph with P
n
∖
|
S
x
| or S
1
T
=
S
T
∖
D
r
n
T
(
v
x
^
) compared to G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
), where S
x represents the key ring which is adjacent to v
x in G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
). Conditional on the isolation of node v
x in G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
), any node v
y is not adjacent to S
x or v
y
^
∈
S
T
∖
D
r
n
T
(
v
x
^
) in G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
). Hence, we have (40)LIyxTy=1,y≠xn=LIyTy=1,y≠xn∣IxT=1.For every y
≠
x, if I
y
T
=
1 then I
y
x
T
=
1. Consequently, we get I
y
x
T
≥
I
y
T.
By Lemma5, the binary nature, and exchangeability of the random variables involved, we find that(41)dTVWT,PoiEWT≤1-e-EWTEWTVarWT-EWT+2∑x=1nEIxT2≤1EWTVarWT-EWT+2∑x=1nEIxT2≤1EWTnn-1EIxTIyT-nn-2EIxT2.
The cross termE
(
I
x
T
I
y
T
) in (41) is given by [33], and we have(42)EIxTIyT≤1-4πrn2e-2πrn2psn+4πrn2e-2πrn2psne2πrn2nKn4/Pn2+Kn2/Pn-Kneπrn2nKn/Pn. With F
(
n
) denoting e
2
π
r
n
2
n
K
n
4
/
P
n
2
+
K
n
2
/
P
n
-
K
n
e
π
r
n
2
n
K
n
/
P
n, combining (29), (41), and (42) readily gives(43)dTVWT,PoiEWT≤nn-1e-2πrn2psn1+4πrn2Fn-n-2e-2πrn2psnne-πrn2psn≤ne-2πrn2psn1+4nπrn2Fnne-πrn2psn≤e-πrn2psn1+4nπrn2Fn=o1,where K
n
≥
ln
⁡
n
/
ln
⁡
ln
⁡
n, K
n
2
/
P
n
=
o
(
1
), p
s
=
ω
1
/
ln
⁡
n
π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n, and (22) are used in reaching (43), along with (36), (37), and (43), which concludes the proof.We now consider the asymptotic distribution of the number of isolated nodes inG
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
). From Theorem 4, l
i
m
n
→
∞
P
(
W
E
=
0
)
=
1 holds, and using Slutsky’s Theorem [40], the following result on the asymptotic distribution of W can be readily obtained.Theorem 7.
SupposeK
n
≥
ln
⁡
n
/
ln
⁡
ln
⁡
n, K
n
2
/
P
n
=
o
(
1
), p
s
=
ω
1
/
ln
⁡
n, and n nodes are Poissonly distributed on a unit square S with the maximum transmission radius π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n for some constant c. Then the distribution of the number of isolated nodes in G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
) converges to a Poisson distribution with mean e
-
c as n
→
∞.


### 3.3. Distribution of the Number of Isolated Nodes inG
(
n
,
θ
n
,
S
)

We derive the distribution of isolated nodes inG
(
n
,
θ
n
,
S
) by using standard Poissonization technique [11, 14]. The idea is that the result about the distribution of isolated nodes for G
(
n
,
θ
n
,
S
) follows once we establish the result with Poissonization, that is to say, once we obtain the distribution of isolated nodes for G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
). See the following lemma for rigorous argument.Lemma 8.
Suppose thatK
n
2
/
P
n
=
o
(
1
), p
s
=
ω
(
1
/
ln
⁡
n
), and n nodes have the same maximum transmission radius π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n for some constant c. Then with m denoting n
-
n
1
/
2
+
c
0, where c
0 is an arbitrary constant with 0
<
c
0
<
1
/
2, then node v
i is isolated in G
(
n
,
θ
n
,
S
) if and only if v
i is an isolated node in G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
).Proof.
We will use the standard de-Poissonization technique [11, 14, 18] to prove Lemma 8. Let M denote the number of nodes in graph G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
); clearly M follows a Poisson distribution with mean m, for any positive t, and from Chebyshev’s inequality, we have(44)PM-m≥tm≤t-2.Without loss of generality, we take n
-
n
1
/
2
+
c
0 as an integer. With t
=
n
-
m
/
m, substituting m
=
n
-
n
1
/
2
+
c
0 into (46), we get(45)PM≤n-2n1/2+c0orM≥n≤n-n1/2+c0n1+2c0=o1.Hence, n
-
2
n
1
/
2
+
c
0
<
M
<
n holds almost surely.
WhenM
<
n, we construct a coupling C between graph G
(
n
,
θ
n
,
S
) and graph G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
); let graph G
(
n
,
θ
n
,
S
) be the result of adding n
-
M nodes uniformly distributed on S to graph G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
). Let V
P be the node set of G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
); clearly, V
P is a subset of V, where V is the node set of G
(
n
,
θ
n
,
S
). In addition, it is straightforward to see that the edge set of G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
) is also a subset of that of G
(
n
,
θ
n
,
S
). Then under coupling C, graph G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
) is a subgraph of G
(
n
,
θ
n
,
S
).
LetD
X
,
D
P denote the set of isolated nodes in G
(
n
,
θ
n
,
S
) and G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
), respectively. To prove Lemma 8, we show (46)PDX≠DP=o1.It is straightforward to see (47)PDX≠DP≤PDP∖DX≠∅∩n-2n1/2+c0<M<n+PDX∖DP≠∅∩n-2n1/2+c0<M<n+PM≤n-2n1/2+c0orM≥n. By (47), we will prove P
(
D
X
≠
D
P
)
=
o
(
1
) if we can derive(48)PDP∖DX≠∅∩n-2n1/2+c0<M<n=o1,(49)PDX∖DP≠∅∩n-2n1/2+c0<M<n=o1. To prove (48) and (49), with n
-
2
n
1
/
2
+
c
0
<
M
<
n, we consider the coupling C under which G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
) is a subgraph of G
(
n
,
θ
n
,
S
).
First, we consider (48) with n
-
2
n
1
/
2
+
c
0
<
M
<
n; event D
P
∖
D
X
≠
∅ happens if and only if there exists at least one node v
i such that v
i
∈
D
P and v
i
∉
D
X; that is to say, v
i is isolated in G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
) but is not isolated in G
(
n
,
θ
n
,
S
). Then there exists at least one node v
′ in V
∖
V
P such that v
′ and v
i are neighbors in G
(
n
,
θ
n
,
S
). Due to |
V
∖
V
P
|
=
n
-
M
<
2
n
1
/
2
+
c
0, noting that p
e is the edge probability in G
(
n
,
θ
n
,
S
), then with W
P denoting the number of isolated nodes in G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
), as an easy consequence of the union bound,(50)PDP∖DX≠∅∩n-2n1/2+c0<M<n≤WP·2n1/2+c0·pe.
In order to apply Corollary2 to G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
), for n sufficiently large, the following condition holds:(51)πrn2·Kn2Pn=ln⁡m+cm.We demonstrate (51) in view of (52)m·πrn2·Kn2Pn-ln⁡m+c=m·ln⁡n+cn-ln⁡m+c=n-n1/2+c0·ln⁡n+cn-ln⁡n-n1/2+c0+c=1-nc0-1/2ln⁡n+c-ln⁡n-ln⁡1-nc0-1/2-c=o1,where 0
<
c
0
<
1
/
2
. And sufficiently large n are used in the final step. Then with (51), for any constant ϵ
>
0, we use Corollary 2 to get(53)WP=omϵ=onϵ.
Note thatp
e
≤
π
r
n
2
·
p
s, and π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n. Then from (50), with ϵ satisfying 0
<
ϵ
<
1
/
2
-
c
0, it follows that(54)PDP∖DX≠∅∩n-2n1/2+c0<M<n≤onϵ·2n1/2+c0·ln⁡n+cn=o1.
Second, in order to prove (49) with n
-
2
n
1
/
2
+
c
0
<
M
<
n, we consider event that D
X
∖
D
P
≠
∅ occurs if and only if there exists at least one node v
j such that v
j
∈
D
X and v
j
∉
D
P. With v
j
∈
D
X, then v
j is isolated in G
(
n
,
θ
n
,
S
), which along with v
j
∉
D
P leads to v
j
∉
V
P and v
j
∈
V
∖
V
P. Let q denote the probability that a node is isolated in G
(
n
,
θ
n
,
S
); it follows via a union bound that(55)PDX∖DP≠∅∩n-2n1/2+c0<M<n≤2n1/2+c0·q.
Sinceq
=
∫
S
‍
e
-
n
p
s
|
D
r
n
(
v
x
^
)
|
d
v
x
^, according to the proof of Theorem 1, it is easy to show q
=
Θ
(
ln
⁡
n
/
n
). With q
=
Θ
ln
⁡
n
/
n and 0
<
c
0
<
1
/
2, then(56)PDX∖DP≠∅∩n-2n1/2+c0<M<n=o1.
In conclusion, sinceP
D
X
≠
∅
-
P
D
P
≠
∅
≤
P
(
D
X
≠
D
P
), the above discussions lead to establish Lemma 8.Applying Theorem7 and Lemma 8, we get the following theorem.Theorem 9.
SupposeK
n
≥
ln
⁡
n
/
ln
⁡
ln
⁡
n, K
n
2
/
P
n
=
o
(
1
), p
s
=
ω
1
/
ln
⁡
n, and n nodes are uniformly distributed on a unit square S with the maximum transmission radius π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n for some constant c. Then the distribution of the number of isolated nodes in G
(
n
,
θ
n
,
S
) converges to a Poisson distribution with mean e
-
c as n
→
∞.Noting that the number of isolated nodes in a network is a nonnegative integer, the following result can be obtained as a consequence of Theorems7 and 9. Notice that, in formulating this result, we drop the assumption that c originally is a constant and allow it instead to be n-dependent.Corollary 10.
SupposeK
n
2
/
P
n
=
o
(
1
), p
s
=
ω
(
1
/
ln
⁡
n
), and n nodes are Poissonly (uniformly) distributed on a unit square S with the maximum transmission radius π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
n
/
n for some c
n. A necessary condition for graph G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
)
(
G
(
n
,
θ
n
,
S
)
) to be asymptotically connected is c
n
→
∞.


## 3.1. Expected Number of Isolated Nodes inG
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
)

In graphG
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
), let I
x denote the event that node v
x is isolated, and let D
r
n
(
v
x
^
) denote the intersection of S and the disk centered at position v
x
^
∈
S with radius r
n. When node v
x is at position v
x
^, the number of nodes within area D
r
n
(
v
x
^
) follows a Poisson distribution with mean n
D
r
n
(
v
x
^
), and to have an edge with v
x in graph G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
), a node not only has to be within D
r
n
(
v
x
^
) but also has to share at least a key with node v
x. Then the number of nodes neighboring to v
x at v
x
^ follows a Poisson distribution with mean n
p
s
D
r
n
(
v
x
^
), and the probability that such number is 0 is equal to e
-
n
p
s
D
r
n
v
x
^. Integrating v
x
^ over S, then the probability that the node v
x is isolated is given by(7)PIx=∫Se-npsDrnvx^dvx^.Theorem 1.
Suppose thatK
n
2
/
P
n
=
o
(
1
), p
s
=
ω
(
1
/
ln
⁡
n
), and n nodes are Poissonly distributed on a unit square S with the maximum transmission radius π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n for some constant c. Then the expected number of isolated nodes in G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
) converges asymptotically to e
-
c as n
→
∞.Proof.
LetW denote the number of isolated nodes in graph G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
). By (7), we know P
(
I
x
)
=
∫
S
e
-
n
p
s
D
r
n
v
x
^
d
v
x
^ holds. To compute P
(
I
x
) based on S, we divide S in a way similar to that by Li et al. [35] and Wan and Yi [15]. Specially, S is divided into S
0
,
S
1
,
S
2, and S
3, respectively, as illustrated in Figure 1 (note that r
n
=
o
(
1
)). S
0 consists of all points each with a distance greater than r
n to its nearest edge to S, whereas S
3 is a square of size r
n
×
r
n at the four corners of S. We further divide S
∖
{
S
0
∪
S
3
} into S
1 and S
2 as follows. In S
∖
{
S
0
∪
S
3
}, S
1 contains points whose distance to the nearest edge of S is no greater than r
n
/
2, while the remaining area is S
2. Then the expected number of isolated nodes is given by (8)limn→∞EW=limn→∞nPIx=limn→∞n∫Se-npsDrnvx^dvx^=limn→∞n∫S0e-npsDrnvx^dvx^+limn→∞n∫S1e-npsDrnvx^dvx^+limn→∞n∫S2e-npsDrnvx^dvx^+limn→∞n∫S3e-npsDrnvx^dvx^.The four summands in (8) represent, respectively, the expected number of isolated nodes in the central area S
0, in the boundary area along the four sides of S, and in the four corners of S. In the following analysis, we will show that the first term approaches e
-
c as n
→
∞, and the remaining terms approach 0 an n
→
∞.
Consider the first summand in (8). It is clear that, for any position v
x
^
∈
S
0, we have |
D
r
n
(
v
x
^
)
|
=
π
r
n
2, and note that π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n, S
0
=
(
1
-
2
r
n
)
2 to get(9)limn→∞n∫S0e-npsDrnvx^dvx^=limn→∞n∫S0e-npsπrn2dvx^=limn→∞ne-npsπrn2∫S0dvx^=limn→∞e-c1-2rn2=e-c.
For the second term in (8), we introduce some notation as follows. For any position v
x
^
∈
S
1, we let the distance from v
x
^ to the nearest edge of square S be g, where 0
≤
g
≤
r
n
/
2. For v
x
^
∈
S
1, clearly |
D
r
n
(
v
x
^
)
| is determined by g, and we denote it by H
(
g
). It is easy to obtain(10)Hg=Drnvx^=πrn2-rn2arccos⁡grn+grn2-g2,(11)H′g=2rn2-g2,(12)H′′g=-2grn2-g2.
SinceS
1 consists of four retangles, each of which has length 1
-
2
r
n and width r
n
/
2, it follows that(13)limn→∞n∫S1e-npsDrnvx^dvx^=4n1-2rnlimn→∞∫0rn/2e-npsHgdg. For simplicity, we write H
(
g
) as H. Then(14)e-npsHgdg=-nps-1H′-1de-npsH=-nps-1·dH′-1e-npsH-e-npsHdH′-1=nps-1·d-H′-1e-npsH-H′-2H′′e-npsHdg.In view of (14), we further have(15)-H′-2H′′e-npsHdg=-H′-3H′′e-npsHdH=-nps-1H′-3H′′d-e-npsH.For 0
≤
g
≤
r
n
/
2, it holds from (11) and (12) that(16)-H′′H′3=g4rn2-g22≤rn/24×3/4rn22=29rn3.By (15) and (16), it follows that(17)-∫0rn/2H′-2H′′e-npsHdg≤29rn3psn∫0rn/2d-e-npsH.Applying (17) into (14),(18)
∫
0
r
n
/
2
e
-
n
p
s
H
g
d
g
=
1
n
p
s
∫
0
r
n
/
2
d
-
H
′
-
1
e
-
n
p
s
H
-
∫
0
r
n
/
2
H
′
-
2
H
′
′
e
-
n
p
s
H
d
g
≤
1
n
p
s
∫
0
r
n
/
2
d
-
H
′
-
1
e
-
n
p
s
H
+
2
9
r
n
3
p
s
n
∫
0
r
n
/
2
d
-
e
-
n
p
s
H
≤
e
-
n
p
s
H
0
n
p
s
H
′
0
+
2
e
-
n
p
s
H
0
9
r
n
3
p
s
2
n
2
.From (10) and (11), we obtain H
(
0
)
=
π
r
n
2
/
2 and H
′
(
0
)
=
2
r
n. Consider(19)∫0rn/2e-npsHgdg≤e-npsH0npsH′0+2e-npsH09rn3ps2n2=e-npsπrn2/22rnnps+2e-npsπrn2/29rn3ps2n2.Using π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n and (6) in (19), we derive(20)∫0rn/2e-npsHgdg≤e-npsπrn2/22rnnps1+o1.Using (20) in (13), we get(21)limn→∞n∫S1e-npsDrnvx^dvx^=4n1-2rnlimn→∞∫0rn/2e-npsHgdg≤4nlimn→∞e-npsπrn2/22rnnps1+o1.From K
n
2
/
P
n
=
o
(
1
)
,
p
s
=
ω
(
1
/
ln
⁡
n
), and with Δ denoting π
r
n
2
p
s
n (note that Δ
=
Θ
(
ln
⁡
n
)),(22)rn=π-1/2ps-1/2n-1/2Δ1/2.We obtain(23)limn→∞n∫S1e-npsDrnvx^dvx^=0.
Now we considerl
i
m
n
→
∞
n
∫
S
2
e
-
n
p
s
|
D
r
n
(
v
x
^
)
|
d
v
x
^. For v
x
^
∈
S
2, when the distance from v
x
^ to the nearest edge of square S is g, where r
n
/
2
≤
g
≤
r
n, the function expression of |
D
r
n
(
v
x
^
)
| still is H
(
g
). H
(
g
) is increasing with g for r
n
/
2
≤
g
≤
r
n by H
′
(
g
)
=
2
r
n
2
-
g
2
≥
0. Thus, when the distance from v
x
^ to the nearest edge of S equals r
n
/
2, the area |
D
r
n
(
v
x
^
)
| reaches its minimum value: (24)Drnvx^min=Hrn2=23+34ππrn2.With C
0 denoting 2
/
3
+
3
/
4
π, then |
D
r
n
(
v
x
^
)
|
m
i
n
=
C
0
π
r
n
2. And with |
S
2
|
=
2
r
n
(
1
-
2
r
n
), we derive (25)limn→∞n∫S2e-npsDrnvx^dvx^≤limn→∞n∫S2e-npsC0πrn2dvx^=limn→∞ne-npsC0πrn2∫S2dvx^≤2limn→∞rnne-npsC0πrn2.From p
s
=
ω
1
/
ln
⁡
n, Δ
=
Θ
(
ln
⁡
n
), and (22), it follows(26)limn→∞n∫S2e-npsDrnvx^dvx^=0.
For the last term in (8), we have 1
/
4
π
r
n
2
≤
|
D
r
n
(
v
x
^
)
|
≤
π
r
n
2 for any v
x
^
∈
S
3 and |
S
3
|
=
4
r
n
2 to get(27)limn→∞n∫S3e-npsDrnvx^dvx^≤nlimn→∞∫S3e-1/4npsπrn2dvx^=limn→∞ne-1/4npsπrn2∫S3dvx^=limn→∞4nrn2n-1/4e-1/4npsπrn2=0,where (22), Δ
=
Θ
(
ln
⁡
n
), and p
s
=
ω
1
/
ln
⁡
n are used in reaching (27).
As a result of (8),(9), (23), (26), and (27), we prove (28)limn→∞EW=e-c.
The parameterc in Theorem 1 is a constant, or it can depend on n, in which case c
=
o
(
ln
⁡
n
). The following corollary can be established.Figure 1
The unit squareS and its divisions S
0, S
1, S
2, and S
3.Corollary 2.
In graphG
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
) under conditions K
n
2
/
P
n
=
o
(
1
), p
s
=
ω
(
1
/
ln
⁡
n
), and π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n with c
=
o
(
ln
⁡
n
) or a constant c, then for any constant ϵ
>
0 such that E
(
W
)
=
o
(
n
ϵ
) holds.Now we examine the impact of boundary effect on the number of isolated nodes inG
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
) since the network area in our analysis is a square. The square accounts for the real-world boundary effect whereby some transmission region of a sensor close to the network boundary may fall outside the network field. In contrast, the torus eliminates the boundary effect. The analysis of impact of the boundary effect is done by comparing the number of isolated nodes in G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
) and the number in a network with nodes Poissonly distributed on a unit torus S
T with a pair of nodes v
x
,
v
y separated by a toroidal distance v
x
^
-
v
y
^
T. Denote such network on a unit torus by G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
). The following Theorem can be established.Theorem 3.
Suppose thatK
n
2
/
P
n
=
o
(
1
), p
s
=
ω
(
1
/
ln
⁡
n
), and n nodes are Poissonly distributed on a unit torus S
T with the maximum transmission radius π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n for some constant c. Then the expected number of isolated nodes in G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
) converges to e
-
c as n
→
∞.Proof.
LetW
T denote the number of isolated nodes in graph G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
), and let D
r
n
T
(
v
x
^
) denote the intersection of S
T and the disk centered at position v
x
^
∈
S
T with radius r
n. The probability that node v
x is isolated is P
(
I
x
T
)
=
∫
S
T
‍
e
-
n
p
s
|
D
r
n
T
(
v
x
^
)
|
d
v
x
^. Since S
T is a unit torus, it holds that |
D
r
n
T
(
v
x
^
)
|
=
π
r
n
2 for any v
x
^
∈
S
T. Then(29)PIxT=∫STe-npsDrnTvx^dvx^=e-πrn2psn∫STdvx^=e-πrn2psn·ST=e-πrn2psn.Using the condition π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n, we obtain (30)limn→∞EWT=limn→∞nPIxT=limn→∞ne-πrn2psn=e-c.On the basis of Theorems1 and 3, using the coupling technique, the following theorem can be obtained.Theorem 4.
Suppose thatK
n
2
/
P
n
=
o
(
1
), p
s
=
ω
(
1
/
ln
⁡
n
), and n nodes are Poissonly distributed on a unit square S with the maximum transmission radius π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n for some constant c. Then the number of isolated nodes in G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
) due to the boundary effect converges asymptotically to 0 as n
→
∞.Proof.
Comparing Theorems1 and 3, it is noted that the expected numbers of isolated nodes on a unit torus S
T and on a unit square S, respectively, asymptotically converge to the same constant e
-
c as n
→
∞. Now we use the coupling technique [36] to construct the connection between W and W
T. Consider a graph G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
), and the number of isolated nodes in that graph is W
T. Remove each connection of the above graph with probability 1
-
|
D
r
n
(
v
x
^
)
|
/
|
D
r
n
T
(
v
x
^
)
|, independently of the event that another connection is removed. Due to |
D
r
n
(
v
x
^
)
|
≤
|
D
r
n
T
(
v
x
^
)
|, then 0
≤
1
-
|
D
r
n
(
v
x
^
)
|
/
|
D
r
n
T
(
v
x
^
)
|
≤
1. We further note that only connections between nodes near the boundary will be affected. Denote the number of newly appearing isolated nodes by W
E; namely, W
E is the number of isolated nodes due to the boundary effect; it is straightforward to show that W
E is a nonnegative random integer. Further, such a connection removal process results in a random network with nodes Poissonly distributed with density n. That is, a random network on a unit square with boundary effect is included. The following equation result holds: (31)W=WE+WT.By Theorems 1 and 3 and the above equation, it can be shown that (32)limn→∞EWE=limn→∞EW-WT=0.Due to the nonnegativity of W
E, (33)limn→∞PWE=0=1.


## 3.2. Distribution of the Number of Isolated Nodes inG
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
)

In this subsection, we analyze the distribution of the number of isolated nodes inG
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
). For this purpose, we give some definitions. Let Poi(λ) be a Poisson random variable with parameter λ.LetΓ be a finite set of indices and let (
I
a
)
a
∈
Γ be a family of random indicator variables. We say (
I
a
)
a
∈
Γ are positively related (see [37]), if, for each a
∈
Γ, there exist random indicator variables (
J
b
a
)
b
∈
Γ
∖
{
a
} with the distributions (34)LJbab∈Γ∖a=LIbb∈Γ∖a∣Ia=1, such that J
b
a
≥
I
b for every b
≠
a.A useful result obtained by Stein-Chen method is the following.Lemma 5 (see [37, 38]).
Suppose thatY
=
∑
a
∈
Γ
‍
I
a, where the indicator variables (
I
a
)
a
∈
Γ are positively related random indicator variables. Then one has (35)dTVY,PoiEY≤1-e-EYEYVar⁡Y-EY+2∑a∈ΓEIa2.Forx
=
1
,
…
,
n, let I
x
T
=
1 if node v
x is isolated in G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
) and W
T
=
∑
x
=
1
n
I
x
T. Therefore, W
T is the number of isolated nodes in G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
) as defined in Theorem 3. We will demonstrate the asymptotic Poisson distribution of W
T by employing the Stein-Chen method [37]. The result is given in Theorem 6.Theorem 6.
SupposeK
n
≥
ln
⁡
n
/
ln
⁡
ln
⁡
n, K
n
2
/
P
n
=
o
(
1
), p
s
=
ω
1
/
ln
⁡
n, and n nodes are Poissonly distributed on a unit torus S
T with the maximum transmission radius π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n for some constant c. Then the distribution of the number of isolated nodes in G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
) converges to a Poisson distribution with mean e
-
c as n
→
∞.Proof.
The triangular inequality for the total variation distance implies(36)dTVWT,Poie-c≤dTVWT,PoiEWT+dTVPoiEWT,Poie-c. By a coupling argument [39] and Theorem 3, we have(37)dTVPoiEWT,Poie-c≤EWT-e-c=o1. Combining this with (36), we now only need to prove(38)limn→∞dTVWT,PoiEWT=0.
First, we claim that(
I
x
T
)
x
=
1
n are positively related. To see this, define (39)IyxT=1ifnodevyisisolatedinGPoissonTn,θn′,S1T,where G
P
o
i
s
s
o
n
T
(
n
,
θ
n
′
,
S
1
T
) is a graph with P
n
∖
|
S
x
| or S
1
T
=
S
T
∖
D
r
n
T
(
v
x
^
) compared to G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
), where S
x represents the key ring which is adjacent to v
x in G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
). Conditional on the isolation of node v
x in G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
), any node v
y is not adjacent to S
x or v
y
^
∈
S
T
∖
D
r
n
T
(
v
x
^
) in G
P
o
i
s
s
o
n
T
(
n
,
θ
n
,
S
T
). Hence, we have (40)LIyxTy=1,y≠xn=LIyTy=1,y≠xn∣IxT=1.For every y
≠
x, if I
y
T
=
1 then I
y
x
T
=
1. Consequently, we get I
y
x
T
≥
I
y
T.
By Lemma5, the binary nature, and exchangeability of the random variables involved, we find that(41)dTVWT,PoiEWT≤1-e-EWTEWTVarWT-EWT+2∑x=1nEIxT2≤1EWTVarWT-EWT+2∑x=1nEIxT2≤1EWTnn-1EIxTIyT-nn-2EIxT2.
The cross termE
(
I
x
T
I
y
T
) in (41) is given by [33], and we have(42)EIxTIyT≤1-4πrn2e-2πrn2psn+4πrn2e-2πrn2psne2πrn2nKn4/Pn2+Kn2/Pn-Kneπrn2nKn/Pn. With F
(
n
) denoting e
2
π
r
n
2
n
K
n
4
/
P
n
2
+
K
n
2
/
P
n
-
K
n
e
π
r
n
2
n
K
n
/
P
n, combining (29), (41), and (42) readily gives(43)dTVWT,PoiEWT≤nn-1e-2πrn2psn1+4πrn2Fn-n-2e-2πrn2psnne-πrn2psn≤ne-2πrn2psn1+4nπrn2Fnne-πrn2psn≤e-πrn2psn1+4nπrn2Fn=o1,where K
n
≥
ln
⁡
n
/
ln
⁡
ln
⁡
n, K
n
2
/
P
n
=
o
(
1
), p
s
=
ω
1
/
ln
⁡
n
π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n, and (22) are used in reaching (43), along with (36), (37), and (43), which concludes the proof.We now consider the asymptotic distribution of the number of isolated nodes inG
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
). From Theorem 4, l
i
m
n
→
∞
P
(
W
E
=
0
)
=
1 holds, and using Slutsky’s Theorem [40], the following result on the asymptotic distribution of W can be readily obtained.Theorem 7.
SupposeK
n
≥
ln
⁡
n
/
ln
⁡
ln
⁡
n, K
n
2
/
P
n
=
o
(
1
), p
s
=
ω
1
/
ln
⁡
n, and n nodes are Poissonly distributed on a unit square S with the maximum transmission radius π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n for some constant c. Then the distribution of the number of isolated nodes in G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
) converges to a Poisson distribution with mean e
-
c as n
→
∞.


## 3.3. Distribution of the Number of Isolated Nodes inG
(
n
,
θ
n
,
S
)

We derive the distribution of isolated nodes inG
(
n
,
θ
n
,
S
) by using standard Poissonization technique [11, 14]. The idea is that the result about the distribution of isolated nodes for G
(
n
,
θ
n
,
S
) follows once we establish the result with Poissonization, that is to say, once we obtain the distribution of isolated nodes for G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
). See the following lemma for rigorous argument.Lemma 8.
Suppose thatK
n
2
/
P
n
=
o
(
1
), p
s
=
ω
(
1
/
ln
⁡
n
), and n nodes have the same maximum transmission radius π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n for some constant c. Then with m denoting n
-
n
1
/
2
+
c
0, where c
0 is an arbitrary constant with 0
<
c
0
<
1
/
2, then node v
i is isolated in G
(
n
,
θ
n
,
S
) if and only if v
i is an isolated node in G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
).Proof.
We will use the standard de-Poissonization technique [11, 14, 18] to prove Lemma 8. Let M denote the number of nodes in graph G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
); clearly M follows a Poisson distribution with mean m, for any positive t, and from Chebyshev’s inequality, we have(44)PM-m≥tm≤t-2.Without loss of generality, we take n
-
n
1
/
2
+
c
0 as an integer. With t
=
n
-
m
/
m, substituting m
=
n
-
n
1
/
2
+
c
0 into (46), we get(45)PM≤n-2n1/2+c0orM≥n≤n-n1/2+c0n1+2c0=o1.Hence, n
-
2
n
1
/
2
+
c
0
<
M
<
n holds almost surely.
WhenM
<
n, we construct a coupling C between graph G
(
n
,
θ
n
,
S
) and graph G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
); let graph G
(
n
,
θ
n
,
S
) be the result of adding n
-
M nodes uniformly distributed on S to graph G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
). Let V
P be the node set of G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
); clearly, V
P is a subset of V, where V is the node set of G
(
n
,
θ
n
,
S
). In addition, it is straightforward to see that the edge set of G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
) is also a subset of that of G
(
n
,
θ
n
,
S
). Then under coupling C, graph G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
) is a subgraph of G
(
n
,
θ
n
,
S
).
LetD
X
,
D
P denote the set of isolated nodes in G
(
n
,
θ
n
,
S
) and G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
), respectively. To prove Lemma 8, we show (46)PDX≠DP=o1.It is straightforward to see (47)PDX≠DP≤PDP∖DX≠∅∩n-2n1/2+c0<M<n+PDX∖DP≠∅∩n-2n1/2+c0<M<n+PM≤n-2n1/2+c0orM≥n. By (47), we will prove P
(
D
X
≠
D
P
)
=
o
(
1
) if we can derive(48)PDP∖DX≠∅∩n-2n1/2+c0<M<n=o1,(49)PDX∖DP≠∅∩n-2n1/2+c0<M<n=o1. To prove (48) and (49), with n
-
2
n
1
/
2
+
c
0
<
M
<
n, we consider the coupling C under which G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
) is a subgraph of G
(
n
,
θ
n
,
S
).
First, we consider (48) with n
-
2
n
1
/
2
+
c
0
<
M
<
n; event D
P
∖
D
X
≠
∅ happens if and only if there exists at least one node v
i such that v
i
∈
D
P and v
i
∉
D
X; that is to say, v
i is isolated in G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
) but is not isolated in G
(
n
,
θ
n
,
S
). Then there exists at least one node v
′ in V
∖
V
P such that v
′ and v
i are neighbors in G
(
n
,
θ
n
,
S
). Due to |
V
∖
V
P
|
=
n
-
M
<
2
n
1
/
2
+
c
0, noting that p
e is the edge probability in G
(
n
,
θ
n
,
S
), then with W
P denoting the number of isolated nodes in G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
), as an easy consequence of the union bound,(50)PDP∖DX≠∅∩n-2n1/2+c0<M<n≤WP·2n1/2+c0·pe.
In order to apply Corollary2 to G
P
o
i
s
s
o
n
(
m
,
θ
n
,
S
), for n sufficiently large, the following condition holds:(51)πrn2·Kn2Pn=ln⁡m+cm.We demonstrate (51) in view of (52)m·πrn2·Kn2Pn-ln⁡m+c=m·ln⁡n+cn-ln⁡m+c=n-n1/2+c0·ln⁡n+cn-ln⁡n-n1/2+c0+c=1-nc0-1/2ln⁡n+c-ln⁡n-ln⁡1-nc0-1/2-c=o1,where 0
<
c
0
<
1
/
2
. And sufficiently large n are used in the final step. Then with (51), for any constant ϵ
>
0, we use Corollary 2 to get(53)WP=omϵ=onϵ.
Note thatp
e
≤
π
r
n
2
·
p
s, and π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n. Then from (50), with ϵ satisfying 0
<
ϵ
<
1
/
2
-
c
0, it follows that(54)PDP∖DX≠∅∩n-2n1/2+c0<M<n≤onϵ·2n1/2+c0·ln⁡n+cn=o1.
Second, in order to prove (49) with n
-
2
n
1
/
2
+
c
0
<
M
<
n, we consider event that D
X
∖
D
P
≠
∅ occurs if and only if there exists at least one node v
j such that v
j
∈
D
X and v
j
∉
D
P. With v
j
∈
D
X, then v
j is isolated in G
(
n
,
θ
n
,
S
), which along with v
j
∉
D
P leads to v
j
∉
V
P and v
j
∈
V
∖
V
P. Let q denote the probability that a node is isolated in G
(
n
,
θ
n
,
S
); it follows via a union bound that(55)PDX∖DP≠∅∩n-2n1/2+c0<M<n≤2n1/2+c0·q.
Sinceq
=
∫
S
‍
e
-
n
p
s
|
D
r
n
(
v
x
^
)
|
d
v
x
^, according to the proof of Theorem 1, it is easy to show q
=
Θ
(
ln
⁡
n
/
n
). With q
=
Θ
ln
⁡
n
/
n and 0
<
c
0
<
1
/
2, then(56)PDX∖DP≠∅∩n-2n1/2+c0<M<n=o1.
In conclusion, sinceP
D
X
≠
∅
-
P
D
P
≠
∅
≤
P
(
D
X
≠
D
P
), the above discussions lead to establish Lemma 8.Applying Theorem7 and Lemma 8, we get the following theorem.Theorem 9.
SupposeK
n
≥
ln
⁡
n
/
ln
⁡
ln
⁡
n, K
n
2
/
P
n
=
o
(
1
), p
s
=
ω
1
/
ln
⁡
n, and n nodes are uniformly distributed on a unit square S with the maximum transmission radius π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n for some constant c. Then the distribution of the number of isolated nodes in G
(
n
,
θ
n
,
S
) converges to a Poisson distribution with mean e
-
c as n
→
∞.Noting that the number of isolated nodes in a network is a nonnegative integer, the following result can be obtained as a consequence of Theorems7 and 9. Notice that, in formulating this result, we drop the assumption that c originally is a constant and allow it instead to be n-dependent.Corollary 10.
SupposeK
n
2
/
P
n
=
o
(
1
), p
s
=
ω
(
1
/
ln
⁡
n
), and n nodes are Poissonly (uniformly) distributed on a unit square S with the maximum transmission radius π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
n
/
n for some c
n. A necessary condition for graph G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
)
(
G
(
n
,
θ
n
,
S
)
) to be asymptotically connected is c
n
→
∞.


## 4. Conclusion and Future Work

Yi et al. [10] considered that a wireless ad hoc network consists of n nodes distributed independently and uniformly in a unit disk D or a unit square S. They used Brun’s sieve to show that, for graph G
(
n
,
θ
n
,
D
) or G
(
n
,
θ
n
,
S
), if π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n and K
n
2
/
P
n
=
ω
1
/
ln
⁡
n, the number of isolated nodes asymptotically follows a Poisson distribution with mean e
-
c. Pishro-Nik et al. [34] also obtained such result on asymptotic Poisson distribution with condition K
n
2
/
P
n
=
ω
1
/
ln
⁡
n generalized to K
n
2
/
P
n
=
Ω
1
/
ln
⁡
n.In this paper, we discuss the distribution of isolated nodes in WSNs employing the widely Eschenauer-Gligor key predistribution scheme under transmission constraint with nodes distributed either Poissonly or uniformly on a unit squareS or a unit torus S
T. Using the coupling technique, it is shown that the impact of the boundary effect on the number of isolated nodes vanishes small as n
→
∞. We obtain that the numbers of isolated nodes in graph G
(
n
,
θ
n
,
S
) and graph G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
) asymptotically follow a Poisson distribution with mean e
-
c with π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n and K
n
2
/
P
n
=
ω
1
/
ln
⁡
n.In practice WSNs,K
n is expected to be several orders of magnitude smaller than P
n, so it often holds that K
n
2
/
P
n
=
o
1
/
ln
⁡
n. We believe that the following conjecture is true.Conjecture 11.
Suppose thatK
n
2
/
P
n
=
o
(
1
), K
n
2
/
P
n
=
o
(
1
/
ln
⁡
n
), and n nodes are uniformly (Poissonly) distributed on a unit square S with the maximum transmission radius π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
/
n for some constant c. Then the distribution of the number of isolated nodes in graph G
(
n
,
θ
n
,
S
) (graph G
P
o
i
s
s
o
n
(
n
,
θ
n
,
S
)) converges to a Poisson distribution with mean e
-
c as n
→
∞.
Connectivity in secure wireless sensor networks under transmission constraints is another important subject. Although the significant improved conditions and results for asymptotic connectivity are presented by Krishnan et al. [4], Krzywdziński and Rybarczyk [13], Tang and Li [32], and Zhao et al. [33], we want to show that the connectivity in WSN with the EG scheme (i.e., G
(
n
,
θ
n
,
S
)) is exactly analogue of the counterpart in classic random graphs.Conjecture 12.
Suppose thatK
n
2
/
P
n
=
o
(
1
), K
n
2
/
P
n
=
o
1
/
ln
⁡
n, and π
r
n
2
·
K
n
2
/
P
n
=
ln
⁡
n
+
c
n
/
n.(i)
Ifc
n
→
-
∞, then with high probability G
(
n
,
θ
n
,
S
) is disconnected.
(ii)
Ifc
n
→
c, then the probability that G
(
n
,
θ
n
,
S
) is connected tends to e
-
e
-
c.
(iii)
Ifc
n
→
∞, then with high probability G
(
n
,
θ
n
,
S
) is connected.
It would be interesting to carry out an illustrative simulation to strengthen the theoretical asymptotic results of the distribution of the number of isolated nodes and connectivity. The simulations may be carried out for small, medium, and large but not very large networks. Such results hold under conditionK
n
2
/
P
n
=
o
(
1
/
ln
⁡
n
), which remains an open research challenge.



---

*Source: 4319426-2016-08-03.xml*