Precise Asymptotic Distribution of the Number of Isolated Nodes in Wireless Networks with Lognormal Shadowing

Lixin Wang, Alberto Argumedo, William Washington

Department of Mathematics, Sciences and Technology, Paine College, Augusta, USA.

DOI: 10.4236/am.2014.515219                

Abstract

In this paper, we study the connectivity of multihop wireless networks under the log-normal shadowing model by investigating the precise distribution of the number of isolated nodes. Under such a realistic shadowing model, all previous known works on the distribution of the number of isolated nodes were obtained only based on simulation studies or by ignoring the important boundary effect to avoid the challenging technical analysis, 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 model because the transmission area of each node is an irregular region other than a circular area. Assume that the wireless nodes are represented by a Poisson point process with densitynover a unit-area disk, and that the transmission power is properly chosen so that the expected node degree of the network equals lnn + ξ (n), where ξ (n) approaches to a constant ξ as n → ∞. Under such a shadowing model with the boundary effect taken into consideration, we proved that the total number of isolated nodes is asymptotically Poisson with mean e$ {-ξ}. The Brun’s sieve is utilized to derive the precise asymptotic distribution. Our results can be used as design guidelines for any practical multihop wireless network where both the shadowing and boundary effects must be taken into consideration.

Keywords

Connectivity, Asymptotic Distribution, Random Geometric Graph, Isolated Nodes, log-Normal 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,

Figure 3.

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.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Bettstetter, C. (2004) On the Connectivity of Ad Hoc Networks. The Computer Journal, 47, 432-447. http://dx.doi.org/10.1093/comjnl/47.4.432
[2]	Bettstetter, C. (2002) On the Minimum Node Degree and Connectivity of a Wireless Multihop Network. 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing, Lausanne, 80-91. http://dx.doi.org/10.1145/513800.513811
[3]	Gupta, P. and Kumar, P. (1998) Critical Power for Asymptotic Connectivity in Wireless Networks. Stochastic Analysis, Control, Optimization and Applications, 547-566.
[4]	Philips, T.K., Panwar, S.S. and Tantawi, A.N. (1989) Connectivity Properties of a Packet Radio Network Model. IEEE Transactions on Information Theory, 35, 1044-1047. http://dx.doi.org/10.1109/18.42219
[5]	Wan, P.-J. and Yi, C.-W. (2004) Asymptotic Critical Transmission Radius and Critical Neighbor Number for k-Connectivity in Wireless Ad Hoc Networks. MobiHoc 2006, Roppongi, 1-8.
[6]	Xue, F. and Kumar, P. (2004) The Number of Neighbors Needed for Connectivity of Wireless Networks. Wireless Networks, 10, 169-181. http://dx.doi.org/10.1023/B:WINE.0000013081.09837.c0
[7]	Yi, C.-W., Wan, P.-J., Li, X.-Y. and Frieder, O. (2006) Asymptotic Distribution of the Number of Isolated Nodes in Wireless Ad Hoc Networks with Bernoulli Nodes. IEEE Transactions on Communications, 54.
[8]	Takai, M., Martin, J. and Bagrodia, R. (2001) Effects of Wireless Physical Layer Modeling in Mobile Ad Hoc Networks. ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc), Long Beach.
[9]	Zorzi, M. and Pupolin, S. (1995) Optimum Transmission Ranges in Multihop Packet Radio Networks in the Presence of Fading. IEEE Transactions on Communications, 43, 2201-2205. http://dx.doi.org/10.1109/26.392962
[10]	Bettstetter, C. and Hartmann, C. (2005) Connectivity of Wireless Multihop Networks in a Shadow Fading Environment. Wireless Networks, 11, 571-579. http://dx.doi.org/10.1007/s11276-005-3513-x
[11]	Bernhardt, R.C. (1987) Macroscopic Diversity in Frequency Reuse Systems. IEEE Journal of Selected Areas in Communications SAC, 5, 862-878. http://dx.doi.org/10.1109/JSAC.1987.1146594
[12]	Cox, D.C., Murray, R. and Norris, A. (1984) 800 MHz Attenuation Measured in and around Suburban Houses. AT & T Bell Laboratory Technical Journal, 63, 921-954. http://dx.doi.org/10.1002/j.1538-7305.1984.tb00030.x
[13]	Hekmat, R. and Mieghem, P.V. (2006) Connectivity in Wireless Ad-Hoc Networks with a Log-Normal Radio Model. Mobile Networks and Applications, 11, 351-360. http://dx.doi.org/10.1007/s11036-006-5188-7
[14]	Mukherjee, S. and Avidor, D. (2005) On the Probability Distribution of the Minimal Number of Hops between Any Pair of Nodes in a Bounded Wireless Ad-Hoc Network Subject to Fading. International Workshop on Wireless Ad-Hoc Networks (IWWAN), London.
[15]	Stuedi, P., Chinellato, O. and Alonso, G. (2005) Connectivity in the Presence of Shadowing in 802.11 Ad Hoc Networks. IEEE Wireless Communications and Networking Conference, 2225-2230.
[16]	Penrose, M. (1997) The Longest Edge of the Random Minimal Spanning Tree. The Annals of Applied Probability, 7, 340-361. http://dx.doi.org/10.1214/aoap/1034625335
[17]	Penrose, M. (1999) A Strong Law for the Longest Edge of the Minimal Spanning Tree. The Annals of Applied Probability, 27, 246-260. http://dx.doi.org/10.1214/aop/1022677261
[18]	Wang, L. and Baker, A.J. (2013) Critical Power for Vanishing of Isolated Nodes in Wireless Networks with Log-Normal Shadowing. IEEE MASS 2013, Hangzhou.
[19]	Bertoni, H. (2000) Radio Propagation for Modern Wireless Systems. Prentice Hall PTR, New Jersey.
[20]	Rappaport, T.S. (2001) Wireless Communications: Principles and Practice. 2nd Edition, Prentice Hall PTR, New Jersey.
[21]	Meester, R. and Roy, R. (1996) Continuum Percolation. Cambridge University Press, Cambridge. http://dx.doi.org/10.1017/CBO9780511895357
[22]	Yi, C.-W., Wan, P.-J., Lin, K.-W. and Huang, C.-H. (2006) Asymptotic Distribution of the Number of Isolated Nodes in Wireless Ad Hoc Networks with Unreliable Nodes and Links. IEEE GLOBECOM.
[23]	Alon, N. and Spencer, J.H. (2000) The Probabilistic Method. 2nd Edition, Wiley, New York. http://dx.doi.org/10.1002/0471722154