<figure><img src="image_1.png" /></figure>

HAL
open science

# Identifying Nearest Neighbor Nodes and Connectivity in Three-Dimensional Wireless Sensor Networks Using Poisson Point Field

Yanhuai Qu, Jianan Fang, Shuai Zhang

<figure><img src="image_2.png" /></figure>

## To cite this version:

Yanhuai Qu, Jianan Fang, Shuai Zhang. Identifying Nearest Neighbor Nodes and Connectivity in Three-Dimensional Wireless Sensor Networks Using Poisson Point Field. IFIP International Conference on Network and Parallel Computing (NPC), Sep 2010, Zhengzhou, China. pp.200-209, 10.1007/978-3-642-15672-4_18. hal-01054990

HAL Id: hal-01054990

https://inria.hal.science/hal-01054990

Submitted on 11 Aug 2014

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Identifying Nearest Neighbor Nodes and
Connectivity in Three-Dimensional Wireless
Sensor Networks Using Poisson Point Field

Yanhuai Qu¹, Jianan Fang¹, and Shuai Zhang²

¹ School of Information Science and Technology,

Donghua University, Shanghai 201620, P.R. China.

² School of Information and Electronic Engineering,

Shandong Institute of Business and Technology, Yantai 264005, P.R. China.

{Yanhuai.Qu@hotmail.com, jafang@dhu.edu.cn, fgsunny@163.com}

**Abstract.** Some problems about the connectivity of wireless sensor networks (WSNs) are always important and difficult topics in research, especially the trade-off between connectivity and energy control. In this paper, we present a novel and effective method to calculate nearest neighbor nodes in three-dimensional WSNs using Poisson point field theory, which enables each node to find the $k^{th}$ nearest neighbor node and adjust transmitting range according to local requirement. Moreover, we derive the probability expression of the $k$-connected network. Finally, we give corresponding simulation results and discussions about the practical value for node energy control and design of WSNs.

**Keywords:** wireless sensor networks, nearest neighbor nodes, connectivity, transmitting range, Poisson point field.

# 1 Introduction

Wireless Sensor Networks (WSNs) have received significant attention in recent years due to their numerous potential in military and civil applications. Typically, a wireless sensor node consists of sensing, computing, communication, actuation, and power components. Sensor nodes are often air-dropped in hostile or dangerous region. It is not possible for humans to reach these sensor nodes and maintain each sensor node, as often the number of sensor nodes is quite large. Hence, self-organization of sensor nodes to form a connected network is an essential requirement. Additionally, the unattended nature of WSNs destines a majority of sensors to have energy sources which may not be replenished. Though some WSNs have equipped renewable energy such as solar battery, the energy consumed will limit their application. So energy is a decisive resource in WSNs. Energy efficiency and network lifetime have occupied a large portion of research effort in WSNs [1],[2],[3],[4],[5].

In this paper, we investigate the problems of nearest neighbor nodes and connectivity of WSNs in three dimensions applying Poisson point field theory
and random geometry graphs theory. We assume n nodes (We denote sensor node by node later.) are distributed in $[0, l]^3$ according to a three-dimensional homogeneous Poisson point field with density $\lambda$ ($\lambda = n/l^3$). Firstly, we investigate nearest neighbor nodes of a node and make use of conditional probability to find the probability distribution function $F(r)$ of the $k^{th}$ nearest neighbor node distance. And then corresponding critical transmitting range of the node is given. Next, basis of prior obtained results of this paper we discuss the connectivity of WSNs applying the random geometric graphs theorem and derive the probability expression of the k-connected Network and corresponding critical transmitting range of all nodes. Moreover, we present simulation results and discuss the practical value for node power control and design of WSNs. Finally, we present conclusion and outline the directions for our future work.

## 2 Related Prior Work

In this section, we recall some related work. Hou and Li [6] presented a model for analyzing the performance of transmission strategies in a multihop packet radio network where each station had adjustable transmission radius. One of the transmission strategies, namely transmitting to the nearest forward neighbor by using adjustable transmission power, had desirable features in a high terminal density environment. Philips et al. [7] examined a model of a packet radio network in which transmitters with range $R$ were distributed according to a two-dimensional Poisson point process with density $D$. To ensure network connectivity, the expected number of nearest neighbors of a transmitter must grow logarithmically with the area of the network. Gupta and Kumar [8] derived the critical power a node in wireless network needed to transmit in order to ensure that the network was connected with probability one as the number of nodes in the network tended to infinity. They shown that if $n$ nodes were distributed in a disc of unit area in and each node transmitted at a power level so as to cover an area of $\pi r^2 = (\ln(n + c(n))/n)$, then the resulting network was asymptotically connected with probability one if and only if $c(n) \to +\infty$. Bettstetter [9],[10] investigated the minimum node degree and k-connectivity of wireless multihop network in the one (respectively, two) dimensional space, he derived an analytical expression of transmitting range of k-connected network.

## 3 Preliminary

### 3.1 Poisson Point Field

One-dimensional number distributions of stationary Poisson point field $N$:

$$ Prob(N(B) = k) = \frac{(\lambda|B|)^k}{k!}e^{-\lambda|B|} \quad (k = 0, 1, ..., N; |B| < \infty), \quad (1) $$

where $N(B)$ denotes the number of points of $N$ in a bounded Borel set $B$, $\lambda$ is the density of $N$, and $| \cdot |$ denotes Lebesgue measure [11],[12],[13],[14].
## 3.2 Some Basic Concepts of Graph Theory

**Definition 1 (Graph)** A graph $G$ is an ordered pair of disjoint sets $(V, E)$, where $E \subseteq V \times V$. Set $V$ is called the vertex(or node, or point), while set $E$ is the edge (or line) set of graph $G$.

**Definition 2 (Connected Graph)** A graph $G = (V, E)$ is connected if for any two nodes $u, v \in V$ there exists a path from $u$ to $v$ in $G$.

**Definition 3 (k-Connected and k-Edge-Connected Graph)** A graph $G = (V, E)$ is $k$-connected, for some $k \ge 2$, if removing any $k-1$ nodes from the graph does not disconnect it. Similarly, $G$ is $k$-edge-connected, for some $k \ge 2$, if removing any $k-1$ edges from the graph does not disconnect it [15]. (see Fig.1)

<figure><img src="image_4.png" /><figcaption>Fig. 1. 2-connected Graph.</figcaption></figure>

## 3.3 Elements of Random Geometric Graphs Theory

**Definition 4 (Random Geometric Graphs)** In the random geometric graphs $G(n,r)$, $n$ nodes are placed at random with uniform distribution in a square area of unit size (more generally, a $m$-dimensional cube). There is an edge $(u,v)$ between any pair of nodes $u$ and $v$, if the Euclidean distance between them is less than $r$ [16].

# 4 Network Model

## 4.1 Network Topology Model

Consider a WSN. Given $n \in \mathbb{N}^+(\mathbb{N}^+ = \{1, 2, ..., N\})$, we use $\mathbf{V}$ to denote the set of $n$ nodes, i.e. $\mathbf{V} = V_i : \in [n]$. Given $l \in \mathbb{N}^+$, we use $\mathbf{L}$ to denote the set of $l$ communication links between the nodes in $\mathbf{V}$, i.e. $\mathbf{L} = \{L_i : i \in [l]\}$.

**Definition 5 (Network Topology Graph)** The network topology graph $NTG = <\mathbf{V}, \mathbf{L}>$ is a graph with vertex set $\mathbf{V}$ representing the set of nodes, and edge set $\mathbf{L}$ representing the set of communication links.

An arbitrary WSN consists of a set of nodes randomly placed in a space. Each node can communicate with another node within distance $r$ through one-hop communication, where $r$ is given as the transmitting range of node (see Fig.2). Throughout the paper, we consider an independent and identically distributed (i.i.d.) network topology model.
<figure><img src="image_5.png" /><figcaption>Fig. 2. The topology of WSNs.</figcaption></figure>

## 4.2 Spatial Node Distribution Model

Assume $n$ nodes are distributed in $[0, l]^3$ according to a three-dimensional homogeneous Poisson point field with density $\lambda(\lambda = n/l^3)$.

# 5 Nearest Neighbor Nodes

For a Poisson point field, we can specify how the inter-node distances are distributed. By the stationarity of the Poisson point field and Slivnyak's theorem [11],[12], the distance between the origin and its the $k^{th}$ nearest neighbor is the same as the distance between an arbitrary point and its the $k^{th}$ nearest neighbor.

## 5.1 The $k^{th}$ Nearest Neighbor Node

In this section, we give the probability distribution function $F(r)$ of the $k^{th}$ nearest neighbor node distance, denoted by $F_k(r)$. According to the homogeneity of Poisson point field, we can calculate it for a point close to the origin $o$. The conditional probability

$$F_k(r) = 1 - \text{Prob}((N(B(o,r) - B(o, \varepsilon)) = 0) \cup (N(B(o,r) - B(o, \varepsilon)) = 1) \dots \cup (N(B(o,r) - B(o, \varepsilon)) = k - 1)|N(B(o, \varepsilon)) = 1) \quad (2)$$

is the probability that the $k^{th}$ neighbor node of a node in a small sphere $B(o, \varepsilon)(\varepsilon > 0)$ locates at distance not greater than $r$ from the origin $o$ (see Fig.3), where $r \gg \varepsilon$. As $\varepsilon$ tends 0, we can derive the probability distribution function $F_k(r)$ of the $k^{th}$ nearest neighbor node distance.

According to the definition of conditional probability, we have

$$F_k(r) = 1 - \text{Prob}(((N(B(o,r) - B(o, \varepsilon)) = 0) \cup (N(B(o,r) - B(o, \varepsilon)) = 1) \dots \cup (N(B(o,r) - B(o, \varepsilon)) = k - 1)), N(B(o, \varepsilon)) = 1)/\text{Prob}(N(B(o, \varepsilon)) = 1). \quad (3)$$

Because $B(o, r) - B(o, \varepsilon)$ and $B(o, \varepsilon)$ are disjoint Borel sets, by the fundamental properties of homogeneous Poisson point field, we get

$$F_k(r) = 1 - \text{Prob}((N(B(o,r) - B(o, \varepsilon)) = 0) \cup (N(B(o,r) - B(o, \varepsilon)) = 1) \dots \cup (N(B(o,r) - B(o, \varepsilon)) = k - 1)). \quad (4)$$
<figure><img src="image_6.png" /><figcaption>Fig. 3. Nearest neighbor nodes in three dimensions.</figcaption></figure>

Make use of (1), we can derive

$$F_k(r) = 1 - \text{Exp}(-\lambda|B(o, r) - B(o, \varepsilon)|)(1 + \lambda|B(o, r) - B(o, \varepsilon)| + \dots + (\lambda|B(o, r) - B(o, \varepsilon)|)^{k-1}/(k-1)!) \quad (5)$$

$$F_k(r) = 1 - \text{Exp}(-\frac{4}{3}\lambda\pi(r^3 - \varepsilon^3)) \cdot (1 + \frac{4}{3}\lambda\pi(r^3 - \varepsilon^3) + \dots + \frac{(\frac{4}{3}\lambda\pi(r^3 - \varepsilon^3))^{k-1}}{(k-1)!}). \quad (6)$$

Here we let $\varepsilon$ tend 0, then

$$F_k(r) = 1 - e^{-\frac{4}{3}\lambda\pi r^3} \left(1 + \frac{4}{3}\lambda\pi r^3 + \dots + \frac{\left(\frac{4}{3}\lambda\pi r^3\right)^{k-1}}{(k-1)!}\right) \\ = 1 - e^{-\frac{4}{3}\lambda\pi r^3} \sum_{i=1}^{k-1} \frac{\left(\frac{4}{3}\lambda\pi r^3\right)^i}{i!}. \quad (7)$$

The corresponding probability density function is

$$f_k(r) = \frac{3\left(\frac{4}{3}\lambda\pi r^3\right)^k}{r(k-1)!} e^{-\frac{4}{3}\lambda\pi r^3}. \quad (8)$$

We denote critical transmitting range of the node by $R_{k-th}$ when its the $k^{th}$ nearest neighbor node got. We can deduce the probability

$$Prob(r \le R_{k-th}) = \int_{0}^{R_{k-th}} f_k(r) dr$$
$$ 
\begin{aligned}
&= \int_{0}^{R_{k-th}} \frac{3(\frac{4}{3}\lambda\pi r^3)^k}{r(k-1)!} e^{-\frac{4}{3}\lambda\pi r^3} dr \\
&=1 - e^{-\frac{4}{3}\lambda\pi R_{k-th}^3} \sum_{i=1}^{k-1} \frac{(\frac{4}{3}\lambda\pi R_{k-th}^3)^i}{i!}.
\end{aligned} 
\quad (9) $$

## 5.2 The Isolated Node

Specially, when a node has no neighbor node, i.e. it is an isolated node, the probability is

$$ 
\begin{aligned}
\text{Prob(isolated node)} &= \text{Prob}(N(B(o,r) - B(o, \varepsilon)) = 0) \\
&= \text{Exp}(-\lambda|B(o,r) - B(o, \varepsilon)|) \\
&= \text{Exp}(-\frac{4}{3}\lambda\pi(r^3 - \varepsilon^3)) \\
&= e^{-\frac{4}{3}\lambda\pi r^3} \quad (\varepsilon \to 0),
\end{aligned} 
\quad (10) $$

and critical transmitting range $R_{iso}$ of the node is

$$ R_{iso} = \sqrt[3]{-\frac{3 \ln \text{Prob(isolated node)}}{4 \lambda \pi}}. \quad (11) $$

## 6 Connectivity

In this section, we investigate the k-connected network. In [17], Penrose has proved

$$ \text{Prob}(G \text{ is } k-\text{connected}) = \text{Prob}(\text{DEG}_{\min}(G) \geq k) \quad (12) $$

, where $DEG_{min}(G)$ denotes the minimum node degree of random geometric graph $G$, i.e. a network is said to be k-connected if each node has at least the $k^{th}$ nearest neighbor node.

So the probability for the k-connected network is

$$ \text{Prob}(k-\text{Connected}) \approx (1 - e^{-\frac{4}{3}\lambda\pi R_{kConn}^3}) \sum_{i=1}^{k-1} \frac{(\frac{4}{3}\lambda\pi R_{kConn}^3)^i}{i!} \quad (13) $$

where $R_{kConn}$ denotes critical transmitting range of all nodes of k-connected network.

## 7 Simulation and Discussion

In this section, we present simulation and discussion. In our simulation environment, the space of nodes distribution $V = [0, 125]^3$ (a unit of measurement: $m^3$), the number of nodes $n \in [0, 100]$, so node density $\lambda = n/V$.
Firstly, Fig.4 shows simulation results of the probability that a node has no neighbor node. For WSNs to function properly in the first place it must be connected, or mostly connected. Otherwise the network would consist of scattered isolated islands of information and could not support properly networking applications.

<figure><img src="image_7.png" /><figcaption>**Fig. 4.** (a) The probability that a node has no neighbor node, (b) Relation between the number of nodes and transmission range when probability that a node has no neighbor node is 99%.</figcaption></figure>

Next, Fig.5 shows the simulation results of the probability distribution that a node has the 3^rd^ nearest neighbor node. A main constraint in WSNs is energy. It would contribute to the survival of overall network if each node is capable of finding nearest neighbor node and adjusting transmitting range according to local requirement.

Then, Fig.6 shows simulation results of the probability distribution for 3-connected network. The connectivity is a vital attribute of WSNs. Through simulations, we notice that connectivity of network becomes multiple with augmentation of transmitting range rapidly.

Finally, the critical transmitting range values reported in Table 1 can be interpreted as transmitting range in different operation state of WSNs, where $R_{iso}$ denotes critical transmitting range of isolated node, $R_{1st}$ (respectively, $R_{2nd}$ and $R_{3rd}$) denotes critical transmitting range of the node having the 1^st^ (respectively, 2^nd^ and 3^rd^) nearest neighbor node, $R_{1Conn}$ (respectively, $R_{2Conn}$ and $R_{3Conn}$) denotes critical transmitting range of all nodes of 1-connected (respectively, 2-connected and 3-connected) network. We observe that the critical transmitting range values have significant differences between the $k^{th}$ nearest neighbor node and $k$-connected network. Due to sensor transmitting power in direct proportion to transmitting range, above results can provide a idea for designers of WSNs.
<figure><img src="image_8.png" /><figcaption>Fig. 5. (a) The probability distribution that a node has the 3^rd^ nearest neighbor node, (b) Relation between the number of nodes and transmitting range when probability that a node has the 3^rd^ nearest neighbor node is 99%.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 6. (a) The probability distribution of 3-connected network, (b) Relation between the number of nodes and transmitting range when probability of the 3-connected network is 99%.</figcaption></figure>
Under the conditions of a large connected component, local nodes or few isolated nodes can adjust transmitting range independent of any other node, which can maximally prolong lifetime of network.

<table><caption>**Table 1.** Critical transmitting range (a unit of measurement: *m*) yielding 99% of different operation state of WSNs varying with network capacity.</caption><thead><tr><th>n</th><th>R<sub>iso</sub></th><th>R<sub>1st</sub></th><th>R<sub>2nd</sub></th><th>R<sub>3rd</sub></th><th>R<sub>1Conn</sub></th><th>R<sub>2Conn</sub></th><th>R<sub>3Conn</sub></th></tr></thead><tbody><tr><td>10</td><td>7.77</td><td>59.88</td><td>67.64</td><td>73.18</td><td>68.53</td><td>75.50</td><td>80.59</td></tr><tr><td>25</td><td>5.72</td><td>44.12</td><td>49.84</td><td>53.92</td><td>52.64</td><td>57.59</td><td>61.23</td></tr><tr><td>50</td><td>4.54</td><td>35.02</td><td>39.56</td><td>42.80</td><td>42.98</td><td>46.81</td><td>49.64</td></tr><tr><td>75</td><td>3.97</td><td>30.59</td><td>34.56</td><td>37.39</td><td>38.13</td><td>41.43</td><td>43.88</td></tr><tr><td>100</td><td>3.61</td><td>27.79</td><td>31.40</td><td>33.97</td><td>35.01</td><td>37.98</td><td>40.19</td></tr></tbody></table>

# 8 Conclusion and Future Work

In this paper, we propose a novel method to investigate the problems of nearest neighbor nodes and connectivity of WSNs in three dimensions. We firstly provided probability distribution function of the $k^{th}$ nearest neighbor node distance and analytical expression of critical transmitting range of corresponding node. And then we derive probability expression of $k$-connected network and critical transmitting range of all nodes. Simulation results and discussions demonstrate that the method is accurate and effective which can provide some theoretical basis for furthering research energy efficiency and topology control of WSNs. Our future work will be focus on inhomogeneous WSNs and their stochastic properties.

**Acknowledgments.** This research was supported in part by the National Natural Science Foundation of China under Grant No. 60874113. The authors also thank the reviewers for their valuable comments.

# References

1. Akyildiz, I.F., Su, W., Sankarasubramaniam, Y., Cayirci, E.: Wireless sensor networks: A survey. Computer Networks 38(2), 393–422 (2002)

2. Chakrabarty, K., Iyengar, S.S.: Scalable Infrastructure for Distributed Sensor Networks. Springer-Verlag, London (2005)

3. Pottie, G.J., Kaiser, W.J.: Wireless sensor networks. Communications of the ACM 43, 51–58 (2000)

4. Brooks, R.R., Iyengar, S.S.: Multi-Sensor Fusion: Fundamentals and Applications with Software. Prentice Hall (1998)

5. Iyengar, S.S., Brooks, R.R.: Distributed Sensor Networks. Chapman & Hall/CRC, Boca Raton (2005)
6. Hou, T.C., Li, V.O.K.: Transmission range control in multihop packet radio networks. IEEE Trans. on Communications COM-34, 38–44 (1986)

7. Philips, T.K., Panwar S.S., Tantawi, A.N.: Connectivity properties of a packet radio network model. IEEE Trans. on Information Theory 35(5), 1044–1047 (1989)

8. Gupta, P., Kumar, P.R.: Critical power for asymptotic connectivity in wireless networks. in Stochastic Analysis, Control, Optimization and Applications. Birkhäuser, Boston (1998)

9. Bettstetter, C.: On the minimum node degree and connectivity of a wireless multihop network. In: Proc. ACM International Symposium on Mobile Ad Hoc Networking and Computing, ACM Press, New York (2002)

10. Bettstetter, C.: On the connectivity of wireless multihop networks with homogeneous and inhomogeneous range assignment. In: Proc. IEEE Vehicular Technology Conference, IEEE Press, Los Alamitos (2002)

11. Stoyan, D., Kendall, W., Mecke, J.: Stochastic Geometry and Its Applications. 2nd ed. John Wiley & Sons, Chichester (1996)

12. Stoyan, D., Stoyan, H.: Fractals, Random Shapes and Point Fields. John Wiley & Sons, Chichester (1994)

13. Daley, D., Jones, D.V.: An Introduction to the Theory of Point Processes Volume I: Elementary Theory and Methods. 2nd ed. Springer-Verlag, New York (2003)

14. Daley, D., Jones, D.V.: An Introduction to the Theory of Point Processes Volume II: General Theory and Structure. 2nd ed. Springer-Verlag, New York (2008)

15. Bollobás, B.: Modern Graph Theory. Springer-Verlag, New York (1998)

16. Penrose, M.D.: Random Geometric Graphs. Oxford University Press, Oxford (2003)

17. Penrose, M.D.: On k-connectivity for a geometric random graph. Random Structures and Algorithms 15(2), 145–164 (1999)