Lattice-Based 3-Dimensional Wireless Sensor Deployment

Abstract

With the wide application of wireless sensor networks (WSNs) in real space, there are numerous studies on 3D sensor deployments. In this paper, the $k$-connectivity theoretical model of fixed and random nodes in regular lattice-based deployment was proposed to study the coverage and connectivity of sensor networks with regular lattice in 3D space. The full connectivity range and cost of the deployment with sensor nodes fixed in the centers of four regular lattices were quantitatively analyzed. The optimal single lattice coverage model and the ratio of the communication range to the sensing range$r_{\text{c}}/r_{\text{s}}$ were investigated when the deployment of random nodes satisfied the $k$-connectivity requirements for full coverage. In addition, based on the actual sensing model, the coverage, communication link quality, and reliability of different lattice-based deployment models were determined in this study.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

Wireless sensor networks (WSNs) are considered one of the important technologies in the 21st century [1]. High coverage and connectivity of node deployment are the guarantee of WSN data collection and transmission. A proper sensor deployment not only provides comprehensive coverage of the entire detection area but also reduces the deployment costs and minimizes the network energy consumption. Most terrestrial WSNs adopt two-dimensional (2D) sensor deployment models, and little attention has been paid to three-dimensional (3D) sensor deployment models. In recent years, there has been an increase in the WSN application in 3D real-world scenarios due to the development of related technologies and the urgent demands of various industries, such as military monitoring, industrial area monitoring, air pollution monitoring, alpine and underwater monitoring, and emergency response and disaster relief [2–6].

The deployment structure is related to the coverage, connectivity, performance, and multitarget deployment of the network [7]. There are two main approaches for 3D sensor deployment: one is to map the 3D model onto the 2D plane [8], but the original 3-D network topology cannot be destroyed and it is difficult to calculate the effective solution of 3D space; the other is to optimize the 3D space topology [9]. While related studies have identified the laws of the sensor deployment patterns and their superiority in two-dimensional space [10], lattice-based 3D wireless sensor deployment is little studied [11]. Due to the stability, symmetry, and anisotropy of the lattice arrangement, the deployment structure of 3D space has some similarities with the crystal structure in nature. The topology of lattice-based regular sensor networks with full spatial coverage was investigated in this study.

In addition, the law of increasing path loss with the distance between nodes during the wireless signal propagation verified the relationship between the successful packet reception rate (PRR) and the distance of any node [12]. Taking signal attenuation and other stochastic factors into consideration in the deployment structure design, the experiments in this study were closer to the real-world scenarios in terms of coverage, communication quality, and the dependency of sensor networks.

As a challenging issue, the 3D WSN deployment obtained three conclusions for the regular lattice-based deployment:

(1) The coverage parameters, connectivity, and deployment cost of four lattice structures with full spatial coverage were further explored, and the connectivity of fixed and random nodes in the lattice was quantitatively analyzed based on the studies on the 3D WSNs coverage

(2) The probabilistic coverage model of 2D WSNs was applied to 3D space to build the probabilistic coverage model of 3D WSN with fixed sensor nodes, and the coverage quality and communication link of different lattice-based deployments were experimentally compared.

(3) The model of regular lattice-based deployment with random node was deduced, and its effectiveness was verified in an experiment to formulate the optimal deployment structure for different $r_{\text{c}}/r_{\text{s}}$ and its actual connectivity in random case

This paper was organized as follows: Section 2, a review of related works on regular deployment; Section 3, definitions, premises, and probabilistic coverage models of 3D sensor network deployment structure; Section 4, a study of fixed and random deployment models of sensor nodes in a regular lattice; Section 5, an analysis of the performance of deployment structure; and Section 6, conclusions.

2. Related Work

The spatial coverage of regular lattice is a spatial geometric problem in the field of 3D mathematical models. Previous studies have found that the sphere has the minimum coverage density among regular lattices with full spatial coverage [13], whose cube has a radius of about $4/\sqrt{5}$ times the side length. Bambah [14] introduced the minimum density coverage of regular deployment in 3D space to 4D space, which was further applied in the $n$-D space [15]. Meanwhile, the maximum density of spheres filling 3D space in Euclidean space without overlap is $5\sqrt{5}\pi /24$, and the maximum density of face-centered cubic stacking is $4/\sqrt{5}$ [16].

A lattice centered on sensor nodes is the basic unit of 3D sensor deployment. Yun et al. [17] presented optimal coverage and connectivity for lattice-based 2D sensor deployment. A structural 3D sensor deployment pattern based on truncated octahedral was proposed and verified to be superior to cubes, hexagonal prisms, and rhombic dodecahedra regarding spatial coverage. Most research focused on the optimization of intelligence-based irregular sensor coverage algorithms, but little explored rule-based deployment sensor methods. For example, Khalaf et al. [18] proposed a sensor coverage method based on the Bee Algorithm. Yu et al. [19] designed a goal heuristic algorithm balancing energy consumption and reliability to deploy relay nodes and obtained the best results of NSGA-II by HV and CTS evaluation indexes. Wang et al. [20] improved the coverage of sensor networks and reduced energy consumption by combining an improved PSO algorithm with grid division. Zhou et al. [21] proposed a three-dimensional spatial coverage method based on Chaotic Parallel Artificial Fish Swarm Algorithm (CPAFSA), which had better performance compared with Genetic Algorithm (GA) and Particle Swarm Optimization (PSO). However, these methods relied on accurate positioning and high-energy sensors, which were expensive in practical applications.

In addition to considering whether sensor nodes are deployed regularly, several studies have proposed other methods that improve the performance of wireless sensor networks. Mobile receiver is an effective method to improve network performance. Paper [22] assumed that there were multiple mobile sinks, and the optimal parking position and moving trajectory were optimized by the metaheuristic algorithm. Similarly, paper [23] introduced mobile sinks to solve the hotspot problems of sensor node deployment. In terms of sensor network communication, effective cluster head selection and communication protocol design were also the main ways to improve the performance of sensor networks. For example, Vijayalakshmi and Anandan [24] designed an effective intelligent optimization algorithm to select cluster heads, and Hady [25] designed a cyclic centralized, hierarchical routing protocol to improve the network performance.

Facing the constraints of energy consumption and cost, few studies have completed the following: calculating the deployment cost of fixed nodes at different communication ranges and sensing ranges under different regular lattice patterns; studying the coverage and communication reliability when fixed nodes were at the center of the lattice; investigating the connectivity law caused by different $r_{\text{c}}/r_{\text{s}}$ when the node positions in the regular lattice structure changed randomly. Therefore, the quantitative analysis of the regular lattice-based 3D sensor deployment provided practical implications for routing algorithms and positioning algorithms in 3D space and other transmission mechanisms of sensor networks.

3. The 3D Sensor Deployment Conditions

The definitions, premises, and sensing models of the regular lattice coverage model were provided in this section to better design the sensor deployment in 3D space.

3.1. Definitions and Premises

Assuming that the radii of the spherical communication region and the detection region of each sensor in Euclidean space were $r_{\text{c}}$ and$r_{\text{s}}$ and that the detection region was large enough to ignore the boundary influence, this study gives the following definitions and hypothesis:

Definition 1.

The 3D detection was divided into $n$ regular basic lattices with only one sensor node in each lattice, denoted as$S_0,S_1,S_2,\cdots ,S_{n-1}$.

Definition 2.

In regular lattice deployment space, the lattice side length was$l^{\text{Lattice}}$ and the volume was$V^{\text{Lattice}}$.

Definition 3.

The connectivity of regular lattice deployment was${\Lambda }_{\text{Lattice}-\text{Connected}}$.

Definition 4.

The coverage density was represented by the ratio of the total volume of a regular lattice to the volume of a circumscribed sphere of radius $r_{\text{s}}$.

Accordingly, the following hypotheses were made:

Hypothesis 5.

All sensor nodes were homogeneous and undirected, and the sensor type did not affect the communication and sensing range.

Hypothesis 6.

Only the connectivity of the adjacent lattices was considered. For example, for a cube, the maximum connectivity in a regular model was 6 adjacent connectivity models.

Hypothesis 7.

The stochastic deployment of sensor nodes was built based on the basis that nodes moved randomly within each cell lattice, and $1\gamma \in 0,1$ was defined as a random movement factor conforming to a normal distribution.

3.2. Properties of Sensor Nodes

Sensor nodes were designed with physical properties, and several mathematical models of the node were determined in terms of sensing, communication, and lifetime.

3.2.1. Sensing Model

Boolean sensing model, directional sensing model, and probability sensing model are three main sensing models for sensors. The sensing model selection is the primary issue in sensor network coverage calculation.

The sensing range of the Boolean perception model was centered on the sensor. In a sphere of radius $r_{\text{s}}$, the probability of detecting outside the sensing range was 0 and within the range was 1. In the directional sensing model, the sensing range was a fan-shaped area centered on the sensor with a fixed sensing distance as the radius. However, these models could not be applied in an environment full of uncertainties because the sensing signal was subject to environmental factors, causing failure in some sensing areas. Therefore, the probabilistic sensing model was applied to fully reflect the sensing characteristics of the sensor networks with the following equation [7]: $$\begin{array}{}\text{(1)}& ps,t=\begin{array}{cc}1,\hfill & 0\le ds,t<r_s-∆r,\hfill \\ e^{-\lambda {\alpha }^{\beta }},\hfill & r_s-∆r\le ds,t<r_s+∆r,\hfill \\ 0,\hfill & ds,t\ge r_s+∆r,\hfill \end{array}\end{array}$$where $r_{\text{s}}$ denotes the maximum radius of accurate sensing without any interference; $∆r$ denotes the uncertain distance of the sensing area; $\alpha$ is the difference between the sensing distance $ds,t$ and the maximum complete sensing distance ($r_{\text{s}}-∆r$); and $\lambda$ and $\beta$ represent the probability parameters of the sensing nodes within the sensing range.

3.2.2. Communication Quality

In the wireless signal communication process, certain signal attenuation occurred during transmission. The link quality was measured by the packet reception rate (PRR), expressed as $$\begin{array}{}\text{(2)}& \text{PRR}d={1-\frac{1}{2}{e}^{-\frac{P_{\text{t}}-\text{PL}d-P_{\text{n}}}{2}}}^{8l},\end{array}$$where $d$ represents the distance between the transmitter and the receiver, $P_{\text{t}}$ is the transmitter output power, $\text{PL}d$ is the path loss, $P_{\text{n}}$ is the noise floor, and $l$ is the frame length.

3.2.3. Sensor Failure

Sensor components had a certain probability of failure over time; thus, the formula for the reliability ($R$) of a single sensor component over time $t$ was used in simulation experiments: $$\begin{array}{}\text{(3)}& R_{i}t=e^{-{\lambda }_{i}t},\end{array}$$where $t$ represents the operating time of the sensor components and ${\lambda }_i$ varies with the properties of the sensor, usually taking the value of 0.0001. The product of the reliability of sensor communication quality and sensor failure is used as the reliability formula of the lattice model in the experiment.

4. Deployment Scheme

In this section, four lattices with full spatial coverage were presented, the deployment cost of the lattice model with the centered sensor was estimated, and the $k$-connectivity model was deduced with the nodes being randomly deployed inside the lattices.

4.1. The Deployment Structure of the Lattice Model with Centered Node

The lattice-based sensor deployment model had the full 3D spatial coverage capability, which was designed on the basis of a regular lattice with space coverage. The regular polyhedral model size for sensor deployment depended on the communication and sensing range of the sensors. When the sensor nodes were fixed at the center of the lattice, the lattice deployment cost with full 3D spatial coverage was obtained by the following theorem:

Theorem 8.

In the regular lattice deployment model with fixed nodes, the deployment costs were truncated octahedron, rhombic dodecahedron, hexagonal prism, and cube in the same detection area from lowest to highest.

Proof.

It is assumed that the total deployment cost of all sensors is$\delta$; the deployment cost of a single sensor is $\text{cost}{c}_i$; the side length of a lattice is $l^{\text{Lattice}}$; the distance from the center to the farthest vertex is the sphere radius length$r_{\text{Lattice}}$; the lattice volume is $v^{\text{Lattice}}$; the deployment cost factor of the lattice is $\delta$; and the number of lattices in the deployment space $V$ is $n$, and the following can be obtained: $$\begin{array}{}\text{(4)}& \delta =\sum _{i=1}^n{c}_i,\text{(5)}& n=\frac{V}{v^{\text{Lattice}}}.\end{array}$$☐

To achieve full area and nonredundant lattice coverage of sensor nodes, the circumscribed sphere size of a lattice was dependent on the sensor sensing range and the communication range. For example, the deployment space size depended on the communication range if faced with a large sensor sensing range and a small communication range, and vice versa. Meanwhile, $\mu$ is the ratio of the communication range to the radius of the outer sphere of lattice and is shown as $$\begin{array}{}\text{(6)}& \mu =\frac{r_{\text{c}}}{r_{\text{Lattice}}}.\end{array}$$

Therefore, the maximum circumscribed sphere radius of the four regular lattices depending on the minimum communication range and the sensing range is expressed as $$\begin{array}{}\text{(7)}& r_{\text{Lattice}}=\min \frac{r_{\text{c}}}{\mu },r_{\text{s}},\end{array}$$where $\mu$ denotes the ratio of the communication radius to the radius of the four regular lattices (cubes, hexagonal prisms, and rhombic dodecahedra) to the radius of the circumscribed sphere. When the deployment structure $r_{\text{s}}>r_{\text{c}}/\mu$, the size of the deployed lattice was calculated by the communication range, and $\mu$ for the four lattices were$2\sqrt{3}/3$, $\sqrt{2}$, and $2\sqrt{15}/5$, respectively. When the sensing range $r_{\text{s}}<r_{\text{c}}/\mu$, the deployed lattice size was dependent on $r_{\text{s}}$, the sensing range of the sensor. Figure 1 shows the schematic results of $r_{\text{c}}$ and $r_{\text{s}}$, and $l_{\max }^{\text{Lattice}}$ of different lattices were calculated below.

[figure omitted; refer to PDF]

With full coverage of the sensing area of the lattice, the relationship of the side length of the cubic model and the minimum sensing and communication ranges is expressed as $$\begin{array}{}\text{(8)}& l_{\max }^{\text{C}}=\frac{2\sqrt{3}}{3}{r}_{\text{Lattice}}=\frac{2\sqrt{3}}{3}\min \frac{r_{\text{c}}}{\mu },r_{\text{s}}.\end{array}$$

In the hexagonal prism model, the adjacent lattices had different communication distances. It was assumed that the side length in the vertical direction was $l_{\max }^{\text{H}-\text{vertical}}$ and in the horizontal direction was $l_{\max }^{\text{H}-\text{horizontal}}$. In this paper, $l_{\max }^{\text{H}}$ was used to represent $l_{\max }^{\text{H}-\text{horizontal}}$. Thus, the relationship among the side lengths in different directions, $r_{\text{c}}$ and $r_{\text{s}}$, was presented as follows: $$\begin{array}{c}\text{(9)}& l_{\max }^{\text{H}-\text{vertical}}=\sqrt{2}{l}_{\max }^{\text{H}},l_{\max }^{\text{H}}=\frac{\sqrt{6}}{3}{r}_{\text{Lattice}}=\frac{\sqrt{6}}{3}\min \frac{r_{\text{c}}}{\mu },r_{\text{s}}.\end{array}$$

For the truncated octahedron model and the rhombic dodecahedron model, the distance from the center point to each vertex was the same, and their side lengths were expressed as follows: $$\begin{array}{c}\text{(10)}& l_{\max }^{\text{R}}=\frac{\sqrt{3}}{2}{r}_{\text{Lattice}}=\frac{\sqrt{3}}{2}\min \frac{r_{\text{c}}}{\mu },r_{\text{s}},l_{\max }^{\text{T}}=\frac{\sqrt{10}}{2}{r}_{\text{Lattice}}=\frac{\sqrt{10}}{2}\min \frac{r_{\text{c}}}{\mu },r_{\text{s}}.\end{array}$$

The sensing range of the sensor deployment was calculated by the maximum side length formulas. The coverage connectivity and the connectivity structure of the single-lattice structure of the four models are given in Figures 1–4.

[figure omitted; refer to PDF]

Combined with equation (8), the volume of the cubic lattice was obtained as follows: $$\begin{array}{}\text{(11)}& V_{\max }^{\text{C}}={l_{\max }^{\text{C}}}^3={\frac{2\sqrt{3}}{3}\min \frac{r_{\text{c}}}{\mu },r_{\text{s}}}^3.\end{array}$$

If the base side length of a hexagonal prism was $l_{\max }^{\text{H}}$ and the height was $\sqrt{2}{l}_{\max }^{\text{H}}$, then the volume of the model was obtained as follows: $$\begin{array}{}\text{(12)}& V_{\max }^{\text{H}}=\frac{1}{2}\times l_{\max }^{\text{H}}\times \frac{\sqrt{3}}{2}{l}_{\max }^{\text{H}}\times 6\times \sqrt{2}{l}_{\max }^{\text{H}}=2\min {\frac{r_{\text{c}}}{\mu },r_{\text{s}}}^3.\end{array}$$

The twelve sides of the rhombic dodecahedron had the same planar structure with the side length of $l_{\max }^{\text{R}}$; thus, the volume of the model was obtained as follows: $$\begin{array}{}\text{(13)}& V_{\max }^{\text{R}}=\frac{1}{3}\times \frac{1}{2}\times \sqrt{2}R\times R\times \frac{\sqrt{2}}{2}R\times 12=\frac{16\sqrt{3}}{9}{l_{\max }^{\text{R}}}^3=2\min {\frac{r_{\text{c}}}{\mu },r_{\text{s}}}^3.\end{array}$$

The truncated octahedron sides included six square planes and eight identical square hexagonal structures with the side length of $l_{\max }^{\text{T}}$; thus, the volume of the model was obtained as follows: $$\begin{array}{}\text{(14)}& V_{\max }^{\text{T}}=\frac{1}{3}\times \frac{1}{2}\times l_{\max }^{\text{T}}\times \frac{\sqrt{3}}{2}{l}_{\max }^{\text{T}}\times 6\times \frac{\sqrt{6}}{2}{l}_{\max }^{\text{T}}\times 8+\frac{1}{3}\times {l_{\max }^{\text{T}}}^2\times \frac{1}{2}\times l_{\max }^{\text{T}}\times 6=\frac{32\sqrt{5}}{25}\min {\frac{r_{\text{c}}}{\mu },r_{\text{s}}}^3.\end{array}$$

When the 3D space achieved the maximum sensing range deployed by a homogeneous sensor, the sensing range satisfied the following equation if the $r_{\text{c}}$ and $r_{\text{s}}$ of the four lattices were equal. $$\begin{array}{}\text{(15)}& V_{\max }^{\text{T}}>V_{\max }^{\text{H}}=V_{\max }^{\text{R}}>V_{\max }^{\text{C}}.\end{array}$$

The relationship of the deployment costs of different lattices was obtained after being substituted into equation (4). $$\begin{array}{}\text{(16)}& {\delta }^{\text{T}}<{\delta }^{\text{H}}={\delta }^{\text{R}}<{\delta }^{\text{C}}.\end{array}$$

Different lattices have different connectivities in the full coverage mode of 3D space, so does the lattice deployment in the direction of variational function estimation. For example, each cubic lattice has two connectivities in the horizontal direction and one connectivity in the vertical direction, and the specialized directional routing reduces the network load. Therefore, in the Euclidean space covered by sensors, if the higher-level nodes of the central nodes of the four deployment methods were fully connected to the lower-level nodes [10], the law is obtained in Table 1.

Table 1

Lattice deployment properties of nodes.

Deployed lattice	Unit cost	Connectivity	Direction
Cube	0.368	6	3
Hexagonal prism	0.477	8	4
Rhombic dodecahedron	0.477	12	6
Truncated octahedron	0.683	14	7

The relationship between the number of needed sensor nodes and the lattice range is shown in Figure 5.

[figure omitted; refer to PDF]

The relationship between the regular node-based deployment and cost is shown in Figure 6.

[figure omitted; refer to PDF]

As seen in Figure 5, the needed node number for the four lattice-based deployments is positively correlated with the size of the deployment space. A single truncated octahedral with the largest space share occupied the least nodes in the same detection area, while a hexagonal prism with the same space share occupied almost the same nodes as a rhombic dodecahedron. The relationship between the number of nodes and the deployment cost for different models is shown in Figure 6, where the truncated octahedral lattice structure is the most cost-effective if all sensor nodes are active.

4.2. The Deployment with Random Nodes

If the sensor node was not in the center, but a random location of the lattice, the connectivity of the deployment structure changed with the communication range. Because of the high symmetry of the lattice, sensors deployed according to the lattice model have the same connectivity in some directions. Theorems 9–12 of regular lattice-based deployment are proposed in this study.

Theorem 9.

In the cubic lattice-based deployment with random nodes and the maximum sensed volume, when$\sqrt{33}/3\le r_{\text{c}}/r_{\text{s}}<2\sqrt{2}$, ${\Lambda }_{\text{C}-1}$, the 1-connectivity of the cubic deployment is achieved; when $r_{\text{c}}/r_{\text{s}}>2\sqrt{2}$, ${\Lambda }_{\text{C}-6}$is achieved (see Figure 7).

Proof.

In Figure 7, assume that node $S_0$ was located in the area with random connected directions; when $S_0\in OABCD$, the node types inside the neighboring lattice were $S_1$,$S_2$, and $S_3$ due to the symmetry of the lattice structure of the cube. To maintain connectivity, the relationship between side length and sensor sensing range satisfied the following condition: $$\begin{array}{}\text{(17)}& l_{\max }^{\text{C}}\le \frac{2\sqrt{3}}{3}{r}_{\text{s}}.\end{array}$$

[figure omitted; refer to PDF]

The cube had a total of six symmetric connected parts in the three connected directions; thus, only $S_0$ needed to be analyzed in the polyhedron$OABCD$. The communication distance $r_{\text{c}}$ in this region satisfied the conditions below: $$\begin{array}{}\text{(18)}& \begin{array}{c}d{S}_0,S_1\le \frac{\sqrt{11}}{2}l\le r_{\text{c}},\hspace{1em}1-\text{connectivity},\hfill \\ d{S}_0,S_2\le \sqrt{6}l\le r_{\text{c}},\hspace{1em}6-\text{connectivity},\hfill \\ d{S}_0,S_3\le \sqrt{6}l\le r_{\text{c}},\hspace{1em}6-\text{connectivity}.\hfill \end{array}\end{array}$$

According to equations (14) and (15), the equation below is obtained: $$\begin{array}{}\text{(19)}& l_{\max }^{\text{C}}=\begin{array}{cc}\min \frac{2\sqrt{3}}{3}{r}_{\text{s}},\frac{2\sqrt{11}}{11}{r}_{\text{c}},\hfill & 1-\text{connectivity},\hfill \\ \min \frac{2\sqrt{3}}{3}{r}_{\text{s}},\frac{\sqrt{6}}{6}{r}_{\text{c}},\hfill & 6-\text{connectivity}.\hfill \end{array}\end{array}$$

Substituting equation (16) into (11), the following equation is obtained: $$\begin{array}{}\text{(20)}& V_{\max }^{\text{C}}=\begin{array}{cc}{\frac{2\sqrt{11}}{2}{r}_{\text{s}}}^3{\min \frac{\sqrt{33}}{3},\frac{r_{\text{c}}}{r_{\text{s}}}}^3,\hfill & 1-\text{connectivity},\hfill \\ {\frac{\sqrt{6}}{6}{r}_{\text{s}}}^3{\min 2\sqrt{2},\frac{r_{\text{c}}}{r_{\text{s}}}}^3,\hfill & 6-\text{connectivity}.\hfill \end{array}\end{array}$$

Theorem 10.

In the hexagon lattice-based deployment with random nodes and the maximum sensed volume, when $\sqrt{186}/6\le r_{\text{c}}/r_{\text{s}}<2\sqrt{2}$, ${\Lambda }_{\text{H}-1}$, the 1-connectivity of the hexagon deployment is obtained; when $2\sqrt{2}\le r_{\text{c}}/r_{\text{s}}<2\sqrt{10}$, ${\Lambda }_{\text{C}-2}$ is obtained; and when $r_{\text{c}}/r_{\text{s}}\ge 2\sqrt{10}$, ${\Lambda }_{\text{C}-8}$ is obtained (see Figure 8).

Proof.

In Figure 8, assume that node $S_0$ was located in the area with random connected directions, and the space was divided into $OABCDEF$ and $OBCMN$. To maintain connectivity, the relationship between side length and sensor sensing range satisfied the following condition: $$\begin{array}{}\text{(21)}& l_{\max }^{\text{H}}\le \frac{\sqrt{6}}{3}{r}_{\text{s}}.\end{array}$$☐

[figure omitted; refer to PDF]

When the sensor nodes of $S_0$ and $S_1$ were in regions $OABCDEF$ and $CMN$, 1-connectivity and 2-connectivity needed to satisfy the following condition: $$\begin{array}{}\text{(22)}& \begin{array}{c}d{S}_0,S_2\le \frac{\sqrt{22}}{2}{l}^{\text{H}}\le r_{\text{c}},\hspace{1em}1-\text{connectivity},\hfill \\ d{S}_1,S_3\le \frac{\sqrt{30}}{2}{l}^{\text{H}}\le r_{\text{c}},\hspace{1em}1-\text{connectivity},\hfill \\ d{S}_0,S_4\le 2\sqrt{3}{l}^{\text{H}}\le r_{\text{c}},\hspace{1em}2-\text{connectivity}.\hfill \end{array}\end{array}$$

Since the symmetry of the lattice structure, 8-connectivity needed to meet the following restrictions: $$\begin{array}{}\text{(23)}& \begin{array}{c}d{S}_0,S_4\le \frac{\sqrt{30}}{2}{l}^{\text{H}}\le r_{\text{c}},\hspace{1em}8-\text{connectivity},\hfill \\ d{S}_1,S_2\le 2\sqrt{3}{l}^{\text{H}}\le r_{\text{c}},\hspace{1em}8-\text{connectivity},\hfill \\ d{S}_1,S_5\le \sqrt{15}{l}^{\text{H}}\le r_{\text{c}},\hspace{1em}8-\text{connectivity},\hfill \\ d{S}_0,S_{3,5}\le \sqrt{15}{l}^{\text{H}}\le r_{\text{c}},\hspace{1em}8-\text{connectivity}.\hfill \end{array}\end{array}$$

Since the connectivity distance between the base and side of the hexagon was less than the distance of simultaneous connectivity in the direction of the three functional variants of the sides, three different connectivity results are obtained as below. $$\begin{array}{}\text{(24)}& l_{\max }^{\text{H}}=\begin{array}{c}\min \frac{\sqrt{6}}{3}{r}_{\text{s}},\frac{2}{\sqrt{30}}{r}_{\text{c}},\hspace{1em}1-\text{connectivity},\hfill \\ \min \frac{\sqrt{6}}{3}{r}_{\text{s}},\frac{1}{2\sqrt{3}}{r}_{\text{c}},\hspace{1em}2-\text{connectivity},\hfill \\ \min \frac{\sqrt{6}}{3}{r}_{\text{s}},\frac{1}{\sqrt{15}}{r}_{\text{c}},\hspace{1em}8-\text{connectivity}.\hfill \end{array}\end{array}$$

Substituting equation (24) into (12), the following equation is obtained: $$\begin{array}{}\text{(25)}& V_{\max }^{\text{H}}=\begin{array}{c}\frac{2\sqrt{6}}{3}\times {\frac{2}{\sqrt{30}}{r}_{\text{s}}}^3\times {\min \sqrt{5},\frac{r_{\text{c}}}{r_{\text{s}}}}^3,\hspace{1em}1-\text{connectivity},\hfill \\ \frac{2\sqrt{6}}{3}\times {\frac{1}{2\sqrt{3}}{r}_{\text{s}}}^3\times {\min 2\sqrt{2},\frac{r_{\text{c}}}{r_{\text{s}}}}^3,\hspace{1em}2-\text{connectivity},\hfill \\ \frac{2\sqrt{6}}{3}\times {\frac{1}{\sqrt{15}}{r}_{\text{s}}}^3\times {\min \sqrt{10},\frac{r_{\text{c}}}{r_{\text{s}}}}^3,\hspace{1em}8-\text{connectivity}.\hfill \end{array}\end{array}$$

Theorem 11.

In the rhombic dodecahedra lattice-based deployment with random nodes and the maximum sensed volume, when $\sqrt{34}/2\le r_{\text{c}}/r_{\text{s}}<\sqrt{5}$, ${\Lambda }_{\text{R}-12}$, the 12-connectivity of the rhombic dodecahedra deployment is obtained (see Figure 9).

Proof.

In Figure 9, assume that node $S_0$ was located in the $OABCD$ region. To maintain connectivity, the relationship between side length and sensor sensing range satisfied the following condition: $$\begin{array}{}\text{(26)}& l_{\max }^R\le \frac{\sqrt{3}}{2}{r}_{\text{s}}.\end{array}$$☐

[figure omitted; refer to PDF]

When $S_0$ was in $OABCD$, 1-connectivity and 12-connectivity met the following condition: $$\begin{array}{}\text{(27)}& \begin{array}{c}d{S}_0,S_1\le \frac{2\sqrt{15}}{3}{l}^{\text{R}}\le r_{\text{c}},\hspace{1em}1-\text{connectivity},\hfill \\ d{S}_0,S_2\le \frac{\sqrt{102}}{3}{l}^{\text{R}}\le r_{\text{c}},\hspace{1em}12-\text{connectivity}.\hfill \end{array}\end{array}$$

Since the rhombic dodecahedron on each rhombic base has the same structure, two different connectivity effects are obtained with adjacent lattices. $$\begin{array}{}\text{(28)}& {\text{l}}_{\max }^{\text{R}}=\begin{array}{c}\min \frac{\sqrt{3}}{2}{r}_{\text{s}},\frac{\sqrt{15}}{10}{r}_{\text{c}},\hspace{1em}1-\text{connectivity},\hfill \\ \min \frac{\sqrt{3}}{2}{r}_{\text{s}},\frac{\sqrt{102}}{34}{r}_{\text{c}},\hspace{1em}12-\text{connectivity}.\hfill \end{array}\end{array}$$

Substituting equation (28) into (13), the following equation is obtained: $$\begin{array}{}\text{(29)}& V_{\max }^{\text{R}}=\begin{array}{c}\frac{16\sqrt{3}}{9}\times {\frac{\sqrt{15}}{10}{r}_{\text{s}}}^3{\min \sqrt{5},\frac{r_c}{r_s}}^3,\hspace{1em}1-\text{connectivity},\hfill \\ \frac{16\sqrt{3}}{9}\times {\frac{\sqrt{102}}{34}{r}_{\text{s}}}^3{\min \frac{\sqrt{34}}{2},\frac{r_c}{r_s}}^3,\hspace{1em}12-\text{connectivity}.\hfill \end{array}\end{array}$$

Theorem 12.

In the truncated octahedral lattice-based deployment with random nodes and the maximum sensed volume, the lattice models with different communication ranges to sensing range ratios had three connectivity modes with adjacent lattices: when $\sqrt{145}/5\le r_{\text{c}}/r_{\text{s}}<2\sqrt{70}/5$, the 1-connectivity of the truncated octahedral (${\Lambda }_{\text{T}-1}$) deployment is obtained; when $2\sqrt{70}/5\le r_{\text{c}}/r_{\text{s}}<2\sqrt{85}/5$, the${\Lambda }_{\text{T}-14}$is obtained; when $r_{\text{c}}/r_{\text{s}}>2\sqrt{85}/5$,the ${\Lambda }_{\text{T}-14}$ is obtained (see Figure 10).

Proof.

In Figure 10, assume that node $S_0$ was located in the area with random connected directions, and space was divided into $OABCD$ and $OCDEFGH$. To maintain connectivity, the relationship between the side length and sensor sensing range of the truncated octahedral lattice-based deployment met the following condition: $$\begin{array}{}\text{(30)}& l_{\max }^{\text{T}}\le \frac{\sqrt{10}}{5}{r}_{\text{s}}.\end{array}$$☐

[figure omitted; refer to PDF]

According to the structural properties of the truncated octahedron, the furthest connection distance in the $OABCD$ direction was longer than that in the $OCDEFGH$ direction. When $S_0$ was in $OABCD$, 1-connectivity and 14-connectivity needed to meet the following condition: $$\begin{array}{}\text{(31)}& \begin{array}{c}d{S}_0,S_2\le \frac{37\sqrt{2}}{2}{l}^{\text{T}}\le r_{\text{c}},\hspace{1em}1-\text{connectivity},\hfill \\ d{S}_0,S_4\le \sqrt{34}{l}^{\text{T}}\le r_{\text{c}},\hspace{1em}14-\text{connectivity}.\hfill \end{array}\end{array}$$

When $S_1$ was in $OCDEFGH$, 1-connectivity and 8-connectivity needed to meet the following condition: $$\begin{array}{}\text{(32)}& \begin{array}{c}d{S}_1,S_3\le \frac{\sqrt{58}}{2}{l}^{\text{T}}\le r_{\text{c}},\hspace{1em}1-\text{connectivity},\hfill \\ d{S}_1,S_3\le 2\sqrt{7}{l}^{\text{T}}\le r_{\text{c}},\hspace{1em}8-\text{connectivity}.\hfill \end{array}\end{array}$$

Since the connectivity distance between the hexagon base and side of the truncated octahedral was less than the simultaneous connectivity distance in the direction of the three functional variants of the sides, three different connectivity results are obtained as below. $$\begin{array}{}\text{(33)}& l_{\max }^{\text{T}}=\begin{array}{c}\min \frac{\sqrt{10}}{5}{r}_{\text{s}},\frac{2}{\sqrt{58}}{r}_{\text{c}},\hspace{1em}1-\text{connectivity},\hfill \\ \min \frac{\sqrt{10}}{5}{r}_{\text{s}},\frac{1}{2\sqrt{7}}{r}_{\text{c}},\hspace{1em}8-\text{connectivity},\hfill \\ \min \frac{\sqrt{10}}{5}{r}_{\text{s}},\frac{1}{\sqrt{34}}{r}_{\text{c}},\hspace{1em}14-\text{connectivity}.\hfill \end{array}\end{array}$$

Substituting equation (33) into (16), the following equation is obtained: $$\begin{array}{}\text{(34)}& V_{\max }^{\text{T}}=\begin{array}{c}8\sqrt{2}\times {\frac{2}{\sqrt{58}}{r}_{\text{s}}}^3\times {\min \frac{\sqrt{145}}{5},\frac{r_{\text{c}}}{r_{\text{s}}}}^3,\hspace{1em}1-\text{connectivity},\hfill \\ \frac{2\sqrt{6}}{3}\times {\frac{1}{2\sqrt{7}}{r}_{\text{s}}}^3\times {\min \frac{2\sqrt{70}}{5},\frac{r_{\text{c}}}{r_{\text{s}}}}^3,\hspace{1em}8-\text{connectivity},\hfill \\ \frac{2\sqrt{6}}{3}\times {\frac{1}{\sqrt{34}}{r}_{\text{s}}}^3\times {\min \frac{2\sqrt{85}}{5},\frac{r_{\text{c}}}{r_{\text{s}}}}^3,\hspace{1em}14-\text{connectivity}.\hfill \end{array}\end{array}$$

Therefore, in the regular lattice-based deployment with the maximum sensing range, the conditions of $r_{\text{c}}/r_{\text{s}}$ ratio of the random nodes were proposed to achieve different connectivities inside the lattices.

5. Experimental Results and Analysis

The coverage and the connectivity quality of the deployment with fixed and random nodes were analyzed in this section.

5.1. Practical Considerations in a Regular Lattice

However, the practical sensing model of the sensor could not fully simulate the detection of spherical sensing range. Cao et al. conducting extensive experiments found that the sensing probability of the sensor’s sensing range in different directions followed the Gaussian distribution [26]. A typical probabilistic perception model was given in equation (1). To unify the coverage effects of the four models, the values of $\lambda$ and $\alpha$ in the equation related to the device and environmental factors were taken as 0.1. Assume that the coverage quality of the regular lattice-based model with fixed nodes was obtained when the single sensor node was studied simultaneously inside different lattices, as shown in Figure 11.

[figure omitted; refer to PDF]

As shown in Figure 11, when the $r_{\text{c}}/r_{\text{s}}$ ratio is relatively small, the lattice shape region remains completely covered. Assuming that the sensor communication range remained constant, coverage rate is increased by increasing the sensing distance of the sensor. A single sensor was able to cover the detection area of the corresponding lattice model and exceed the node range corresponding to the lattice. With the increase of the $r_{\text{c}}/r_{\text{s}}$ ratio and the reduction of the redundancy space, the coverage had the same situation with the actual probabilistic sensing model. When the ideal deployment structure with a maximum communication range was built, the coverage rate did not change. Meanwhile, the cube structure was the first to reach the perceived probability of a stable detection area because of the smallest $r_{\text{c}}/r_{\text{s}}$ ratio.

In addition, in real WSNs, the path loss of the sensor nodes’ communication signals is caused by the devices and environmental factors. Referring to the paper [27] and the mathematical model of the wireless sensor link in equation (2), the relationship between sensor PRR and signal-to-noise ratio for four lattice-base deployment models is demonstrated in Figure 12.

[figure omitted; refer to PDF]

As shown in Figure 12, the PRR between sensors increased significantly from 3 db to 10 db SNR. Since the truncated octahedral lattice satisfying 14-connectivity had more adjacent nodes and redundant links which generated communication, the reliability of data transmission of the single node was the best in the four lattice deployment modes without considering the system energy consumption. The other three lattice modes had roughly similar PRR trends with the truncated octahedron for communication link data. Due to fewer redundant links in the maximum 6-connectivity mode, the cubic structure needed a larger signal-to-noise ratio to achieve higher PRR.

To further investigate the impact of sensor lifetime on communication quality, the decay function of the device over time was introduced, and equation (3) was applied to study the truncated octahedral deployment model with lower deployment cost. The product of the sensor link quality and the time-based reliability was used as the node quality assessment metric in this model. As shown in Figure 13, the reliability decreases to a stable state as time goes by, while the reliability after the signal-to-noise ratio exceeding 10 db becomes unaffected by the signal-to-noise ratio.

[figure omitted; refer to PDF]

The cubic structure rapidly covered the whole detection area when 1-connectivity was satisfied with a short communication distance, i.e., $\sqrt{33}/3\le r_{\text{c}}/r_{\text{s}}<2\sqrt{2}$. With $r_{\text{c}}/r_{\text{s}}$ ratio increasing, the hexagonal prism and rhombic dodecahedra achieved 1-connectivity when the ratio of communication distance to sensor radius was $\sqrt{5}$. The truncated octahedron with the biggest space coverage needed the ratio of $\sqrt{145}/5$ to achieve 1-connectivity.

The multiconnectivity of the four regular lattice-based 3D deployments was further analyzed. According to the calculation, when $2\sqrt{2}\le r_{\text{c}}/r_{\text{s}}<\sqrt{34}/2$, the 2-connectivity of hexagonal prism and the 6-connectivity of the cube were obtained; when $\sqrt{34}/2\le r_{\text{c}}/r_{\text{s}}<\sqrt{10}$, the 12-connectivity of rhombic dodecahedron was obtained with the maximum connectivity ratio; when $\sqrt{10}\le r_{\text{c}}/r_{\text{s}}<2\sqrt{70}/5$, the 8-connectivity of the hexagonal prism was obtained; when $2\sqrt{70}/5\le r_{\text{c}}/r_{\text{s}}<2\sqrt{85}/5$, the 8-connectivity of truncated octahedron was obtained; when $r_{\text{c}}/r_{\text{s}}>2\sqrt{85}/5$, the 14-connectivity was obtained.

The effect of random nodes in the lattice on the connectivity was verified experimentally using $\gamma$ as the random factor with the central node as the reference. Consistent with the reliability experiments, the connectivity of the truncated octahedron with less deployment cost was further investigated, and the average connectivity effects of four different lattice structures as the number of nodes increased are shown in Figure 15.

[figure omitted; refer to PDF]

The effect of the deployment boundary was analyzed in this experiment. As shown in Figure 15, when the node fixed in the center of the lattice does not move, the boundary effect caused by more nodes is smaller. The connectivity increases with the increase of the number of nodes. The connectivity of the nodes decreases as $\gamma$ increases, and the average connectivity of rhombic dodecahedra decreases significantly when the random factor $\gamma$ of the nodes increases from 0 to 0.1. Although the connectivity of hexagonal prism with the same space proportion was lower than that of rhombic dodecahedra in fixed time, the average connectivity of hexagonal prisms was greater than that of rhombic dodecahedra with the increase of node mobility. Due to the structural characteristics, the connectivity of truncated octahedral showed a significant cascade with the increase of mobility factor $\gamma$, dropping from an average 11-connectivity level to a 5-connectivity level, and was superior to other three structures under the same number of nodes. Cubic structures had the worst connectivity, averaging between 3-connectivity and 5-connectivity. Therefore, the truncated octahedral structure outperformed the other three lattice structures with full connectivity $r_{\text{c}}/r_{\text{s}}$ for fixed nodes only.

6. Conclusion

In this study, the regular lattice-based 3D wireless sensor deployment with full spatial coverage was studied. First, the study designed four sensor deployment patterns based on a single-lattice structure with full spatial coverage and calculated the deployment costs. Second, the regular lattice-based deployment with random nodes was analyzed, and the connectivity differences of deployment models with different communication ranges and sensing ranges were deduced. Finally, combined with the characteristics of the actual sensor sensing and links, the deployment coverage, communication quality, and connectivity effects were analyzed under four structures. The design of sensor communication protocols is based on random node deployment and ignores the topology of node deployment. Therefore, the sensor device with better adaptation is required to improve the detection quality of 3D sensor deployment in future studies, with reference to the characteristics of the regular lattice-base deployment models.

Acknowledgments

This research was supported in part by the China National Key Research and Development (No. 2018YFC0808306), Hebei Key Research and Development Program (No. 19270318D), Hebei Internet of Things Engineering and Technology Research Center (No. 3142018055), and Qinghai Internet of Things Key Laboratory (No. 2017-ZJ-Y21).

References

[1] R. V. Kulkarni, A. Förster, G. K. Venayagamoorthy, "Computational intelligence in wireless sensor networks: a survey," IEEE Communications Surveys & Tutorials, vol. 13 no. 1, pp. 68-96, DOI: 10.1109/SURV.2011.040310.00002, 2011.

[2] T. Wang, Z. Peng, J. Liang, S. Wen, M. Z. A. Bhuiyan, Y. Cai, J. Cao, "Following targets for mobile tracking in wireless sensor networks," ACM Transactions on Sensor Networks (TOSN), vol. 12 no. 4, 2016.

[3] U. Lerner, O. Hirshfeld, B. Fishbain, "Optimal deployment of a heterogeneous air quality sensor network," Journal of Environmental Informatics, vol. 34 no. 2, pp. 99-107, 2019.

[4] T. R. Wanasinghe, R. G. Gosine, L. A. James, G. K. Mann, O. De Silva, P. J. Warrian, "The internet of things in the oil and gas industry: a systematic review," IEEE Internet of Things Journal, vol. 7 no. 9, pp. 8654-8673, 2020.

[5] M. Zafer, M. R. Senouci, M. Aissani, "On coverage of 3D terrains by wireless sensor networks," Federated Conference on Computer Science and Information Systems, pp. 501-504, DOI: 10.15439/2019F24, .

[6] W. Kim, H. W. Moon, Y. J. Yoon, "Adaptive triangular deployment of underwater wireless acoustic sensor network considering the underwater environment," Journal of Sensors, vol. 2019,DOI: 10.1155/2019/6941907, 2019.

[7] Y. Xiang, Z. Xuan, M. Tang, J. Zhang, M. Sun, "3D space detection and coverage of wireless sensor network based on spatial correlation," Journal of Network and Computer Applications, vol. 61, pp. 93-101, DOI: 10.1016/j.jnca.2015.11.005, 2016.

[8] S. Oktug, A. Khalilov, H. Tezcan, "3D coverage analysis under heterogeneous deployment strategies in wireless sensor networks," 2008 Fourth Advanced International Conference on Telecommunications, pp. 199-204, DOI: 10.1109/AICT.2008.50, .

[9] M. C. Zhao, J. Lei, M. Y. Wu, Y. Liu, W. Shu, "Surface coverage in wireless sensor networks," IEEE INFOCOM 2009, pp. 109-117, DOI: 10.1109/INFCOM.2009.5061912, .

[10] X. Bai, Z. Yun, D. Xuan, T. H. Lai, W. Jia, "Deploying four-connectivity and full-coverage wireless sensor networks," IEEE Communications Surveys & Tutorials, vol. 13 no. 1, pp. 68-96, 2011.

[11] B. Shah, K. I. Kim, "A survey on three-dimensional wireless ad hoc and sensor networks," International Journal of Distributed Sensor Networks, vol. 10 no. 7,DOI: 10.1155/2014/616014, 2014.

[12] Q. Miao, B. Huang, B. Jia, "Estimating distances via received signal strength and connectivity in wireless sensor networks," Wireless Networks, vol. 26 no. 2, pp. 971-982, DOI: 10.1007/s11276-018-1843-8, 2020.

[13] E. S. Barnes, "The covering of space by spheres," Canadian Journal of Mathematics, vol. 8 no. 1, pp. 93-100, 1956.

[14] R. P. Bambah, "Lattice coverings with four-dimensional spheres," Mathematical Proceedings of the Cambridge Philosophical Society, vol. 50 no. 2, pp. 203-208, DOI: 10.1017/S0305004100029248, 1954.

[15] M. N. Bleicher, "Lattice coverings ofn-Space by spheres," Canadian Journal of Mathematics, vol. 14, pp. 632-650, DOI: 10.4153/CJM-1962-054-7, 1962.

[16] T. C. Hales, "A proof of the Kepler conjecture," Annals of Mathematics, vol. 162 no. 3, pp. 1065-1185, DOI: 10.4007/annals.2005.162.1065, 2005.

[17] Z. Yun, X. Bai, X. Dong, T. Lai, W. Jia, "Optimal deployment patterns for full coverage and k-connectivity (k," IEEE/ACM Transactions on Networking, vol. 18 no. 3, pp. 934-947, 2010.

[18] O. I. Khalaf, G. M. Abdulsahib, B. M. Sabbar, "Optimization of wireless sensor network coverage using the bee algorithm," Journal of Information Science and Engineering, vol. 36 no. 2, pp. 377-386, 2020.

[19] W. J. Yu, X. B. Li, H. Yang, B. Huang, "A multi-objective metaheuristics study on solving constrained relay node deployment problem in WSNS," Intelligent Automation and Soft Computing, vol. 24 no. 2, pp. 367-376, DOI: 10.1080/10798587.2017.1294873, 2018.

[20] J. Wang, C. Ju, Y. Gao, A. K. Sangaiah, G. J. Kim, "A PSO based energy efficient coverage control algorithm for wireless sensor networks," Computers, Materials & Continua, vol. 56 no. 3, pp. 433-446, 2018.

[21] J. Zhou, G. Qi, C. Liu, "A chaotic parallel artificial fish swarm algorithm for water quality monitoring sensor networks 3D coverage optimization," Journal of Sensors, vol. 2021,DOI: 10.1155/2021/5529527, 2021.

[22] J. Wang, Y. Gao, C. Zhou, R. S. Sherratt, L. Wang, "Optimal coverage multi-path scheduling scheme with multiple mobile sinks for WSNs," Computers, Materials & Continua, vol. 62 no. 2, pp. 695-711, DOI: 10.32604/cmc.2020.08674, 2020.

[23] J. Wang, Y. Gao, X. Yin, F. Li, H. J. Kim, "An enhanced PEGASIS algorithm with mobile sink support for wireless sensor networks," Wireless Communications and Mobile Computing, vol. 2018,DOI: 10.1155/2018/9472075, 2018.

[24] K. Vijayalakshmi, P. Anandan, "Global levy flight of cuckoo search with particle swarm optimization for effective cluster head selection in wireless sensor network," Intelligent Automation & Soft Computing, vol. 26 no. 2, pp. 303-311, 2020.

[25] A. A. Hady, "Duty cycling centralized hierarchical routing protocol with content analysis duty cycling mechanism for wireless sensor networks," Computer Systems Science and Engineering, vol. 35 no. 5, pp. 347-355, DOI: 10.32604/csse.2020.35.347, 2020.

[26] Q. Cao, T. Yan, J. A. Stankovic, "Analysis of target detection performance for wireless sensor networks," International Conference on Distributed Computing in Sensor Systems, pp. 276-292, .

[27] M. Zuniga, B. Krishnamachari, "Analyzing the transitional region in low power wireless links," 2004 First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, pp. 517-526, DOI: 10.1109/SAHCN.2004.1381954, .