Precise Asymptotic Distribution of the Number of Isolated Nodes in Wireless Networks with Lognormal Shadowing ()
1. Introduction
Connectivity is one of the most fundamental properties of multi-hop wireless networks. It is the premise for enabling a network with proper functions. The path-loss model (also known as the unit-disk communication model) of wireless networks assumes that the received signal strength at a receiving node from a transmitting node is only determined by a deterministic function of the Euclidean distance between the two nodes. Under such a simple communication model, two nodes are directly connected if and only if their Euclidean distance is no more than a given threshold, and network connectivity has been well studied in the literature (e.g., [1] -[7] ). However, in reality, the received signal strength often shows probabilistic variations induced by the shadowing effects that are unavoidably caused by different levels of clutter (e.g., ubiquitous background noises and obstructions such as buildings and trees) on the propagation path. In order to better capture physical reality, the variations of the received signal strength should be considered. It has been shown that a more accurate and realistic modeling of the physical layer is indeed important for better understanding of wireless multi-hop network characteristics [8] [9] . This generalized radio propagation model is referred to as the log-normal shadowing model which has been widely used in the literature [10] - [15] . The generalized shadowing model provides a good abstraction of large scale wireless multi-hop networks, and is a realistic model for many types of wireless multihop network applications such as sensor wireless networks for bush fire monitoring, ocean temperature monitoring, volcano monitoring, etc.
The study of multihop wireless networks with the log-normal shadowing model can date back to the early of 1980s [11] [12] . Under such a realistic model, researchers have investigated fundamental problems related to network connectivity such as the largest connected component in the network, the relation between having a connected network and having no isolated node, etc. [10] [13] - [15] . But most of the known results on network connectivity were obtained only based on simulation studies or ignoring the important boundary effect to avoid the challenging technical analysis under, and thus cannot be applied to any practical wireless networks. It is extremely challenging to take the complicated boundary effect into consideration under such a realistic shadowing model because the transmission area of each node is an irregular region other than a circular area. To the best of our knowledge, under such a realistic shadowing model, there are no theoretical results obtained by rigorous analytical studies in multihop wireless networks when the important boundary effect is taken into consideration.
In this paper, we assume that the wireless networking nodes are represented by a Poisson point process with density
over a unit-area disk
on the plane
, and that the transmission power is properly chosen so that the expected node degree of the network is equal to
, where
approaches to some constant
as
. We derive the precise asymptotic distribution of the number of isolated nodes in the network under the log-normal shadowing model, taking the complicated boundary effect into consideration. The Brun’s sieve is utilized to derive the precise asymptotic distribution.
The vanishing of isolated nodes is not only a prerequisite but also a good indication of network connectivity. Under the path-loss model, it is well-known that the probability of having a connected network equals the probability of having no isolated nodes in the network as the node density
(see Penrose [16] ). With the log- normal shadowing model, such a result is predicted and has been verified by simulation studies (see Bettstetter et al. [10] ). Therefore, it is of importance to study the asymptotic distribution of the number of isolated nodes in the network under such a realistic shadowing model. The results obtained in this paper can be used as design guidelines for any practical multihop wireless network where both the shadowing and boundary effects must be taken into consideration.
In what follows,
is the origin of the Euclidean plane
, and
is the unit-area disk centered at
. We assume that
is the Poisson point process over
with density
. The Euclidean norm of a point
is denoted by
, and the Euclidean distance between two points
and
is denoted by
. The Lebesgue measure (or area) of a measurable set
is denoted by
. The disk of radius
centered at
is denoted by
.
The remaining of this paper is organized as follows. In Section 2, we give a literature review for related work of our paper. The log-normal shadowing model is introduced and explained in Section 3. In Section 4, we give some definitions and geometric results that will be used to prove the main result of this paper. In Section 5, we derive the precise asymptotic distribution of the number of isolated nodes in the network under the log-normal shadowing model. Finally, we conclude our paper in Section 6.
2. Related Work
Under the unit-disk communication model, network connectivity has been extensively studied, and a huge number of existing research work are available in the literature [1] - [7] . Gupta et al. [3] showed that if each node uses the transmission radius
![]()
where
is a positive parameter depending only on
, then the network is connected a.a.s. if and only if
, assuming the
nodes are uniformly distributed in a disk on the plane.
M.
Penrose proved that the longest edge of the minimum spanning tree (MST) equals the critical transmission range for connectivity [16] , he then derived in [17] the asymptotic distribution of the longest edge of the MST. Xue et al. obtained in [6] several results including a sufficient condition on the average node degree for connectivity. They proved that every node must connect to at least
closest neighbors if the network is to be connected as
, assuming that the
nodes are randomly and uniformly distributed in a unit square on the plane. Phillips et al. in [4] provided a necessary condition on the average node degree (i.e. the expected number of neighbors of an arbitrary node) required for connectivity and showed that the average node degree must grow logarithmically with the area of the network to ensure that the network is connected, assuming that the networking nodes are represented by a Poisson point process with density
in the plane.
The log-normal shadowing model is a much more realistic radio propagation model and has been widely used by many researchers for network connectivity [10] [13] - [15] . Hekmat et al. investigated in [13] the largest connected component in wireless ad-hoc networks through simulations, where the
nodes are uniformly distributed in a bounded region on the plane. In this paper the authors proposed a formula to evaluate the size of the largest connected component on average. In [10] , Bettstetter et al. investigated a relation between the probability of having a connected network and the probability of having no isolated node, where the wireless devices are represented by a Poisson point process with density
. The authors verified by using simulation that the two probabilities are approximately equal when
is sufficiently large. In [14] , Mukherjee et al. studied the probability distribution for the minimal number of hops required to connect an arbitrary source node to a destination node by ignoring the complicated boundary effect. Through simulation studies, Stuedi et al. investigated in [15] how the transmission range affects the end-to-end connection probability in a log-normal shadowing model and compared the results to theoretical bounds and measurements in the path-loss model. In [18] , with the complicated boundary effect taken into consideration, Wang et al. first derived an explicit formula for the expected number of the isolated nodes in the network under such a realistic shadowing model, then obtained an upper and a lower bound for the critical transmission power to ensure that the vanishing of isolated nodes is asymptotically almost sure (abbreviated as a.a.s.). The upper and lower bounds for the critical transmission power obtained in [18] are almost tight.
Most of the results in these known works were obtained only based on simulation studies or ignoring the important boundary effect to avoid the rigorous analysis by assuming the toroidal metric as done in the literature. To the best of our knowledge, there are no theoretical results on asymptotic distribution of the number of isolated nodes in the network obtained by rigorous analytical studies with the realistic log-normal shadowing model when the complicated boundary effect is taken into consideration.
3. The Log-Normal Shadowing Model
With the path-loss model, the received power levels decrease as the distance between the transmitter and the receiver increases. Attenuation of radio signals due to path-loss effect has been modelled by averaging the measured signal power over long times and distances around the transmitter. The averaged power at any given distance
to the transmitter is referred to as the area mean power
. Based on the path-loss model, the area mean power
is expressed as
![]()
where
is a constant depending on the receiver and transmitter antenna gains and the wavelength,
is the transmission power used by each node,
is the path-loss exponent which indicates the rate at which the received signal strength decreases with distance, and
is a close-in reference distance such that
for any two nodes
and
in the network. The value of
depends only on the environment and terrain structure and can vary between 2 in free space and
6 in
heavily built urban areas. The values of
and
depend on the density
. Under the path-loss model, the communication range of each node is a perfect circular disk (see Figure 1(a)). The node
can directly communicate with all other nodes that are within its communication range.
But the path-loss model could be inaccurate because in reality the received power levels may show significant variations around the area mean power value. Due to these variations, short links could disappear while long links could merge. The log-normal shadowing model allows for random power variations around the area mean power. With the log-normal shadowing model, the received mean power taken over all possible locations that are at distance
to the transmitter is equal to the area mean power. However, it is further assumed that the time averaged received power varies from location to location in an apparently random manner [19] .
Assume that links are symmetric and the received power at node
from node
is equal to the received power at node
from node
For any given Euclidean distance
let
denote the received power strength between any two nodes separated by the distance
under the log-normal shadowing model. The basic assumption in this realistic shadowing model is that the logarithm of
is normally distributed around the logarithm of the area mean power
. That is,
(1)
where
is a zero-mean Gaussian (normal) distributed random variable (in dB) with standard deviation
(also in dB). The standard deviation
is a nonnegative value and, in case of severe signal fluctuations due to irregularities in the surroundings of the receiving and transmitting antennas, measurements indicates that it can be as high as 12 dB [20] .
For any two nodes separated by the Euclidean distance
, there exists a link between them if and only if the received power
under such a model is not less than some given threshold
(also in dB milliwatts) that is assumed to be a constant in this paper, i.e.
(2)
And we say that any two nodes are directly connected if and only if there exists a link between them.
Define
as the Euclidean distance where the area mean power
is equal the given threshold power
That is,
Then
(3)
If both sides of Equation (1) minus
since
we have
![]()
Then Equation (2) is equivalent to
(4)
Thus for any two nodes separatedy the Euclidean distance
let
denote the probability that there is a link between the two nodes. Then
(5)
When
there is no shadowing (i.e.,
). Then
![]()
Thus, any two nodes are directly connected if and only if their Euclidean distance is at most
. In such a case, the channel model is reduced to the simple unit-disk communication model and
is the maximum transmission radius of each node.
When
, the existence of a link is determined by both a deterministic function of the link length r and the shadowing effect represented by
. The transmission area of each node is no longer a circular area under the log-normal shadowing model. Under the log-normal shadowing model, the communication range of each node is an irregular region other than a circular area (see Figure 1(b)). In this figure, the node
is closer to node A than node D, the nodes A and D are directly connected, but the nodes A and C are not because of the shadowing effect between the nodes A and C. In real applications, σ is larger than zero, hence, the communication model with shadowing is more realistic than that without shadowing.
The following lemma demonstrates how the probability
changes when the link length
, or the density
or the transmission power
changes.
Lemma 1. When
and
are fixed, the probability
decreases as
increases; when
and
are fixed, the probability
increases as
increases.
Proof. According to Equation (5),
is fixed when
and
are fixed, since
increases as
increases, it is easy to see that the probability
is a decreasing function of the link length
, which accords with intuition. When the density
and the link length
are fixed, as
increases,
increases and
decreases. Therefore, the probability
increases as
increases, which also accords with intuition. Thus, the lemma is proved.
4. Preliminaries
In this section, we shall give some definitions that will be used to prove our main result of this paper. The results in this section are purely geometric, with no probabilistic content. Let
be the maximum transmission radius of the nodes. For any finite set of nodes
in
, we use
to denote the
-disk graph over
in which there is an edge between two nodes if and only if their Euclidean distance is at most
. For any positive integers
and
with
, let
denote the set of
satisfying that
has exactly
connected components.
For the given maximum transmission radius r, the unit-area disk
is partitioned into three regions,
,
and
as shown in Figure 2:
is the disk of radius
centered at the origin;
is the annulus of radii
and
centered at the origin; and
is the annulus of radii
and
centered at the origin.
Then we have
![]()
![]()
![]()
![]()
(a) (b)
Figure 1. (a) Unit-disk communication model; (b) Log-normal shadowing model.
![]()
Figure 2. Partition of the unit-area disk
.
5. Precise Asymptotic Distribution of the Number of Isolated Nodes
In this section, we assume that all the nodes transmit at a uniform power
. We derive the precise asymptotic distribution of the number of isolated nodes in the network under the log-normal shadowing model with the complicated boundary effect taken into consideration.
We use the same notations as in Section 3. Recall that
denotes the probability that any two nodes separated by the distance
are directly connected. Then by Equation (5), we have
(6)
Let
(7)
Refer to the discussions in [10] and [21] ,
is actually the expected node degree of the network. By Equations (6) and (7)
(8)
Based on our assumptions,
is a function of
and
(see Equation (3)). Therefore,
depends only on
and
. When
is fixed, it is easy to see that the value of
increases as
increases from Equation (8).
Let
(9)
Then, when
is fixed,
also increases as
increases.
In this paper, we make the following two assumptions:
1)
has bounded support w.r.t.
i.e., there is a positive parameter
(depending only on
and
) such that
(10)
2) the transmission power
is properly chosen so that
for some constant
(including
).
The main theorem of this paper is stated below:
Theorem 2. Under the two assumptions given above, the total number of the isolated nodes in the network is asymptotically Poisson with mean ![]()
Remarks. If the probability
(i.e., the shadowing model is reduced to the path-loss model), then Equation (9) is reduced to
(11)
where
is the minimal transmission radius of each node (determined by the minimal transmission power) required for connectivity of multihop wireless networks under the path-loss model (see Gupta et al. [3] or Penrose [16] ).
If the probability
for some constant
(i.e., the shadowing model is reduced to the unreliable link model used in [22] with all nodes active and
), then Equation (9) is reduced to
![]()
where
is the maximum transmission radius of each node used to derive the precise asymptotic distribution of the number of isolated nodes in the network with the unreliable link model defined in [22] . Therefore, our Theorem 2 above is the generalization of the main theorem in [22] to the more realistic lognormal shadowing model.
Theorem 2 will be proved by using the Brun’s sieve in the form described, for example, in [23] , Chapter 8, which is an implication of the Bonferroni inequalities.
Theorem 3. (Brun’s sieve) Let
be a positive integer parameter. Suppose that
is a non- negative integer random variable depending on
, and
are
Bernoulli
random variables depending on
. Assume that for any subset
we have
![]()
If there is a constant
such that for every fixed positive integer
,
![]()
then
is asymptotically Poisson with mean
(with respect to
).
To apply Theorem 3, let
denote the event that the random point
is isolated for
and
be the number of
that holds. Then
is exactly the total number of isolated nodes. Clearly, for any subset ![]()
![]()
Therefore, in order to prove Theorem 2, it is sufficient to show that for any fixed positive integer
when the conditions of Theorem 2 hold, we have
(12)
The proof of this asymptotic equation will use the following lemmas.
Lemma 4. Assume the conditions of Theorem 2 hold. Then there exist a sufficiently large constant
and a sufficiently small constant
(both independent of
) satisfying that the probability ![]()
for all ![]()
Proof. We prove the lemma by contradiction and assume the contrary is true. Then for any arbitrarily large
and any arbitrarily small
such that
as
there is an
(with
) satisfies that
Since
is a decreasing function of
we have
for all
Note that
Then by Equation (7), for any fixed
we have
![]()
The above inequality holds for any arbitrarily large
when
is fixed. Fix
and let
we have
Therefore,
This contradicts with Equation (9). Therefore, the lemma is proved.
The following lemma shows that
has the order
when the conditions of Theorem 2 hold.
Lemma 5. Assume the conditions of Theorem 2 hold. Then we have
and
![]()
where
and
are the two constants obtained in Lemma 4.
Proof. Note that
By Equation (9) and Equation (7),
![]()
By Lemma 4, there exist a sufficiently large constant
and a sufficiently small constant ![]()
(both independent of
) satisfying that
for all
Thus, we have
![]()
Thus, the lemma is proved.
Next we introduce a lemma that has only one event involved and has been proved in [18] (see Equation (10) and Equation (12) in [18] ).
Lemma 6. For any
we have
![]()
If
then
(13)
Lemma 7. For any
and
there is a constant
such that for any
we have
![]()
Proof. First we prove the lemma holds when
and
Let
Then
We consider two cases:
Case 1.
Let
denote the event that
does not have links to nodes in
Then
![]()
It remains to show that there is a constant
such that
![]()
For any
let
denote the angle of the arc of
not contained in
Since
is increasing w.r.t.
we have
![]()
Let
![]()
Apply the same approach in deriving the probability for
(see Equation (10) and Equation (12) in [18] ), we have
![]()
Case 2.
We only consider the nodes in
Divide this disk by
concentric circles with
center
and radii
as we did in [18] . Since
is a decreasing function of
we have
![]()
Note that the inequality still holds for annuli not fully contained in
Therefore,
![]()
For any
we have
Let
![]()
Then
![]()
Thus,
![]()
The lemma holds for the constant
Thus, the lemma is proved when
and
.
When
, for any
since there always exist two overlapping disks (the distance between the two
centers is at most
) in the components
the lemma can be proved by following similar steps
as the case for
.
Next we assume
and
For any
the set
is parti- tioned into exactly
subsets
such that for each
the subgraph of
induced by only the nodes in
forms a connected component. Let
for each
and let
Then we have
![]()
Since at least one
for each
, we have
![]()
Thus, the lemma is proved.
Now we are ready to prove the asymptotic Equation (12). The proof of this asymptotic equation is divided into three lemmas. The case for
is proved in Lemma 8. The case for any
and
will be proved in Lemma 9. The case for any
and
will be verified in Lemma 10. Thus, the asymptotic Equation (12) holds for any
since ![]()
Lemma 8. ![]()
Proof.
![]()
We will prove
(14)
(15)
(16)
For the integral over
by Equation (13) we have
![]()
For the integral over
by Equation (13) we have
![]()
Next we calculate the integral over
For any
let
be the point on
such that
and
the diameter perpendicular to
(see Figure 3). Let
denote the half disk contained in
. Then
(17)
Therefore, by Equation (7) and Equation (17)
![]()
To complete the proof of the lemma, it is sufficient to prove that this integral over
is asymptotically vanishing as
. We consider two cases.
Case 1.
. Then
![]()
Thus,
![]()
The last equation holds since
by Lemma 5.
Case 2.
. Then
![]()
Thus,
![]()
Therefore, the lemma is proved.
Lemma 9. For any
and
we have
![]()
Proof. By Equations (15) and (16), it is straightforward to verify that the lemma holds when
for some
Therefore, we only need to consider the case when ![]()
We first prove the case when
For any
the
-disk graph
has exactly one connected component. That is, the graph
is connected. Assume that the points
is listed in the increasing order of the graph distances from
to
Then
![]()
where the second last equation holds from Lemma 5.
Next we assume
For any
the set
is partitioned into exactly
subsets
such that for each
the subgraph of
induced by only the nodes in
forms a connected component. Let
for each
and let
Then we have
![]()
where the last equation holds by following the similar arguments as the case ![]()
This completes the proof of the lemma.
Lemma 10. For any
we have
![]()
Proof. For any
the
disks
are disjoint. Thus,
are independent. Therefore,
![]()
Next we calculate the two integrals
and
separately.
![]()
the last equation holds by following the same steps as we used in the proof of Lemma 8.
![]()
where the last equation holds from Lemma 9.
This completes the proof of the lemma.
6. Conclusion
In this paper, we assume that the wireless nodes are represented by a Poisson point process with density n over a unit-area disk, and that the transmission power is properly chosen so that the expected node degree of the network equals
, where
approaches to a constant
as
. We also assume that the probability that a pair of nodes separated by a Euclidean distance
are directly connected has bounded support w.r.t
. Under the log-normal shadowing model with the boundary effect taken into consideration, we proved that the total number of isolated nodes is asymptotically Poisson with mean
.
Acknowledgements
The work of
Dr.
Lixin
Wang
in this paper is supported in part by the NSF grant HRD-1238704 of USA.