# Dynamic Adjustment Optimisation Algorithm in 3D Directional Sensor Networks Based on Spherical Sector Coverage Models

Authors: Xiaochao Dang; Chenguang Shao; Zhanjun Hao
Journal: Journal of Sensors
 (2019)

---

## Abstract

In directional sensor networks research, target event detection is currently an active research area, with applications in underwater target monitoring, forest fire warnings, border areas, and other important activities. Previous studies have often discussed target coverage in two-dimensional sensor networks, but these studies cannot be extensively applied to three-dimensional networks. Additionally, most of the previous target coverage detection models are based on a circular or omnidirectional sensing model. More importantly, if the directional sensor network does not design a better coverage algorithm in the coverage-monitoring process, its nodes’ energy consumption will increase and the network lifetime will be significantly shortened. With the objective of addressing three-dimensional target coverage in applications, this study proposes a dynamic adjustment optimisation algorithm for three-dimensional directional sensor networks based on a spherical sector coverage model, which improves the lifetime and coverage ratio of the network. First, we redefine the directional nodes’ sensing model and use the three-dimensional Voronoi method to divide the regions where the nodes are located. Then, we introduce a correlation force between the target and the sensor node to optimise the algorithm’s coverage mechanism, so that the sensor node can accurately move to the specified position for target coverage. Finally, by verifying the feasibility and accuracy of the proposed algorithm, the simulation experiments demonstrate that the proposed algorithm can effectively improve the network coverage and node utilisation.


---

## Body

## 1. Introduction

A three-dimensional (3D) wireless sensor networks (WSNs) consists of several tiny, battery-powered sensors that can communicate with each other to monitor a 3D field of interest (FOI) [1] for target events. WSNs include sensor networks (i.e., omnidirectional sensor networks) and directional sensor networks (DSNs). Research into WSN coverage is roughly classified into three branches: area coverage, barrier coverage, and target coverage. In recent years, WSNs coverage has been an active research area with a wide range of practical applications: target detection [2], healthcare applications [3], target location [4], data transmission [5], etc. In these real-world applications, we can detect some target events in the region of interest by deploying sensor nodes. Therefore, the use of existing methods and techniques to achieve effective event detection is now the current research focus. At the same time, improving multiple objectives (e.g., reducing the network’s overall energy consumption while ensuring a high coverage ratio) is an indispensable consideration in research.In most of the previous studies, the researchers have discussed and presented solutions for 2D coordinate systems under realistic conditions to reduce the difficulty and they have made great progress [6–8]. However, modelling and studying DSNs coverage are still less common in 3D systems than in 2D systems; not only does the difficultly of research increase in 3D systems, but deployed sensor nodes often encounter complex environmental influences (e.g., weather and climate). In recent years, some researchers have established models for 3D WSNs and proposed corresponding distributed optimisation algorithms [9–11]. However, the WSN node coverage model is mainly based on the 2D omnidirectional sensing model, and a large part of the research in 3D systems is based on the omnidirectional ball sensing model. While the omnidirectional sensing model can provide better range and node utilisation for area coverage, we only require modest energy and nodes with limited directional detection to achieve target coverage for a set of targets or special events in practice. Therefore, 3D DSNs coverage research is more suitable for the above conditions.Of course, the directional sensor not only needs to consider its own position and sensing range (as with the omnidirectional sensor) but must also consider the angle change problem. Furthermore, when nodes are randomly deployed covered, they cannot be accurate and some omissions will occur. Therefore, in a specific environment, we need a dynamic algorithm to select the optimal number of active nodes to detect the target [12]. At the same time, we need to consider moving or rotating these active nodes within a certain period to adjust their own headings to achieve the best coverage. For example, in [8], the use of unattended sensor networks has been discussed for detecting targets using energy-efficient methods. The authors are dedicated to analysing the trade-offs between power consumption and quality of service in WSNs in terms of detection capabilities and latency. In [13], the authors propose using the hybrid movement strategy (HMS) to solve the problem of high energy consumption (resulting from mobility) and improve the coverage ratio of DSNs. Although the method proposed above can reduce the energy consumption of the network and improve the coverage ratio, the rotation angle of the 3D directional sensor node is difficult to determine; increased dimensionality brings further complications.Therefore, we propose a network model suitable for directional sensors and related dynamic adjustment optimisation algorithms for 3D systems. We first design a sensing model that is more suitable for 3D DSNs and allows us to quantify the rotation angle of the node. Secondly, to achieve accurate coverage, we extend traditional 2D Voronoi division and apply it to 3D DSNs. We also use theory and experimentation to verify the algorithm to further reduce network energy consumption. Finally, we design experimental simulations and perform algorithm comparisons to further analyse our algorithm’s effectiveness. Our main contributions are highlighted as follows:(i)
We are the first to propose a spherical sector sensing model for 3D DSNs that quantifies the rotation angle in combination with using a 3D Voronoi method [14] to divide space using the sensors’ positions
(ii)
We design a synergistic priority coverage mechanism to reduce the moving distance of nodes, thereby reducing excessive energy consumption while guaranteeing a high coverage ratio for the sensor network
(iii)
We optimise the traditional virtual force algorithm to suit practical conditions, and we perform a full theoretical analysis and experimental comparative analysis of the algorithm proposed in this paper to verify its validity and accuracyThe remainder of this paper is organised as follows. In Section2, the research progress and related work on DSNs in recent years are summarised. In Section 3, the DSNs coverage model and sensing angle are described and the relevant definitions are provided. After this, we compare the differences between 2D and 3D Voronoi and give the 3D Voronoi partition theory in Section 4. We then show how we have designed and improved the relevant algorithms and provide its design steps in Section 5. In Section 6, we describe the simulations and experiments we performed on the algorithm and compare it with other algorithms for analysis. Conclusions and future works are discussed in the final section.


## 2. Related Works

In recent years, research on DSNs has been carried out mainly based on 2D planes. For example, in [15], the authors propose a cluster head- (CH-) based distributed target coverage algorithm to solve a Maximum Coverage with Minimum Sensor (MCMS) problem. The authors also designed distributed clustering and target coverage algorithms to reduce network energy consumption. Subsequently, in [12], they designed a target coverage algorithm for DSNs, in an energy-saving manner based on [15], through the distributed clustering mechanism. The authors improved the distributed algorithm in [15] to use the CH approach and ensure that it is used appropriately to enhance DSNs target coverage. In [16], the authors propose a new method (based on particle swarm optimisation) to maximise coverage for 2D regions. This algorithm allows a directional sensor node to constantly adjust its sensing direction to provide the best coverage. However, most of the above studies map 3D sensor coverage problems into 2D for discussion—they cannot be applied directly in three dimensions. Therefore, we need to consider not only dimensionality but also a node-aware model that can be applied in the dimension of the actual environment.In addition, the nodes are often distributed randomly in the monitoring area. Reducing the deployment cost—while using the limited node energy for efficient coverage—has become an active research topic. The authors point out that motility and mobility are essential for DSN nodes to minimise occlusion effects and coverage overlap in [17]. At the same time, motility is superior to mobility in terms of network cost and energy efficiency. Therefore, almost all research aims to solve coverage problems through motility.In practice, however, there are still some coverage holes that can only be addressed through mobility. For example, the authors in [18] use the directionality of the orientation sensor to rotate it to locate periodic detection objects. Therefore, the above authors developed an event monitoring system that proposed a maximum coverage deployment (MCD) heuristic iteration to deploy sensors to cover targets. But we must not only consider the direction of the orientation sensor (i.e., the change or rotation of its sensing angle) to enable efficient deployment; we must also consider that the orientation sensor can move to fill coverage holes in the monitoring area (i.e., DSNs can be moved). Therefore, the literature [13] proposes HMS to solve the high energy consumption of directional sensor movement. The authors use the cascading method to adjust the coverage of the DSNs, effectively reducing network energy consumption. In [19], the authors propose an algorithm based on learning automata to address the orientation sensor network’s coverage quality requirements and to maximise the network lifetime (i.e., priority-based target coverage). The algorithm divides the DSNs into several coverage sets so that each coverage set can meet the coverage quality requirements of all targets. Thus, it effectively extends the network lifetime.In [13, 18, 19], the authors have better solved the problem of mobile energy consumption, but these are based on 2D plane verification and are not suitable for 3D environments. Therefore, the research of the literature [20–22] has successively proposed the orientation sensor model and algorithm for the 3D coordinate system. For example, the authors studied the low-power green communication of 3D DSNs and proposed the space-time coverage optimisation scheduling (STCOS) algorithm to obtain the maximum network coverage in [21]. In [22], the authors propose a network coverage enhancement algorithm based on an artificial fish swarm algorithm to improve the coverage rate. However, the authors only optimised the angle of the sensor and did not solve the mobility problem in the directional sensor. In [23], the authors propose prescheduling-based k-coverage group scheduling (PSKGS) and self-organised k-coverage scheduling (SKS) algorithms to reduce the cost of the algorithm and ensure the effective monitoring of node quality. The experimental results show that PSKGS improves monitoring quality and the SKS algorithm reduces the node’s computation and communication costs.In addition, the special geometric properties of the Voronoi diagram are applied in many aspects of WSN coverage. In [24], the authors propose Voronoi-based centralised approximation (VCA) and Voronoi-based distributed approximation (VDA) for optimal coverage in DSNs. The authors have experimentally verified that the two algorithms can reduce the coverage overlap and achieve a higher coverage rate. In [25], the authors combine the special set features of the 2D Voronoi graph with the real-time response of dynamic environment changes and propose a distributed greedy algorithm that can select and adjust the intracellular sensing direction based on coverage (IDS&IDA). Obviously, the research on the 2D Voronoi algorithm has shown better results, but it is rarely applied in three dimensions.Therefore, based on the typical literature [14, 25], this paper improves and extends the Voronoi method, making it suitable for 3D DSNs target coverage. In this paper, we propose a dynamic adjustment optimisation algorithm for 3D DSNs based on a spherical sector coverage model. This algorithm can maximise coverage and improve network lifetime by adjusting the direction and specific movements of nodes in the DSNs. In the subsequent experimental verification section, we discuss the proposed algorithm and compare it with other algorithms.


## 3. Network Coverage Model and Angle Quantification Method

### 3.1. Network Coverage Model

First, we assume that the sensing model of the sensor node covers a sphere with its midpoint at the node’s positionoixi,yi,zi and its sensing range Rs is the maximum detection distance. Initially, it is assumed that sensor nodes si are randomly scattered in an L3 target area, and the set of nodes is sis1,s2,⋯,sn. Rc represents the communication radius of the node, when the Euclidean distance between two nodes si and sj satisfies dsi,sj<Rc; we call them neighbour nodes [26]. In a traditional 2D study, most researchers transform the sensor nodes into a 2D planar fan to achieve coverage optimisation. In some related 3D research fields, the node’s sensing range is abstracted into a covering model of a rounded hammer. However, the coverage model of the 3D directional sensor should be obtained by rotating a planar fan with radius Rs and central angle 2θ around its axis of symmetry, as shown in Figure 1. Therefore, we define the directional node’s sensing range as a spherical sector sensing model. As shown in Figure 1, the spherical sector O—A1B1C1 represents the coverage model of the directional sensor. When 2θ=360°, its coverage matches that of the omnidirectional sensor node. Therefore, the spherical sector network model redefined in this paper is more suitable for modelling the coverage of 3D sensor nodes.Figure 1
Spherical sector sensing model.Initially, sensor nodes are randomly scattered in the target monitoring area, which may result in an uneven node distribution, excessive node energy consumption, and duplicate or missing coverage for some targets. In Figure2, the grey dots indicate targets that need to be covered, and the three spherical sectors represent sensor coverage. Some of the targets in Figure 2 are not completely covered. Therefore, the sensor network may also have omission problems, resulting in lower node utilisation. Before designing a 3D DSNs coverage algorithm based on the 3D Voronoi diagram partition, the following assumptions are made:
(i)
The sensor nodes are isomorphic, and each node has access to its own location and that of its neighbour nodes through some technical means
(ii)
Each node has the same detection range, but its sensing range can be different; that is, each sensor can select different sensing angles2θ, where each si can select its own sensing angle 2θi
(iii)
Each node can rotate and move freely in any directionFigure 2
Target detection model.


### 3.2. Model Angle Quantification

In previous studies, the randomly distributed target pointp in space is covered by the directional node si and the basic conditions doi,p≤Rs and ∣φ≤θ∣ need to be satisfied. Most studies [27, 28] use the partitioning model shown in Figure 3 to specify angles. However, it is difficult for this model to quantify the angle φ between the target point p and the node si. In particular, it is difficult to determine the necessary rotation amount when a node must rotate to cover a target. Furthermore, the sensing model and direction angle partitioning of Figure 3 is abstract and impractical for directional sensor nodes with differing θ and varying main direction angle ψ.Figure 3
Node sensing direction.Therefore, we redefine the sensing model and propose an angle and direction division method using one octant of a sphere to unify the rotation as shown in Figure4. As long as the spherical sector busbar is exactly tangent to the three edges of O—ABC (i.e., the spherical sector contains O—ABC), coverage can be achieved by rotating the model to the coordinate system in which the target event is located—when the condition dsi,p≤Rs is satisfied. The above assumptions can reduce omissions and node energy consumption. In this regard, we subsequently respecified the conditions under which the target event can be covered by the directed node.Figure 4
Angle division of sensing model.
(a)
(b)
(c)
(d)
(e)As shown in Figure4, we cut the sphere of radius r along its axes of symmetry to divide it into eight parts; that is, the shaded portion in Figure 4(a) is the isolated polyhedron O—ABC. For a more intuitive understanding and for analysis and quantification, we separately extract the shaded parts removed in Figure 4(a) and draw the perspective view shown in Figure 4(b). To quantify the angle θ in our model, we need to solve for ∠COO′. Therefore, we project the point O onto a plane containing O′ that is perpendicular to the line passing through O and O′. For a more intuitive understanding and analysis, we separately extract the triangle △ABC in Figure 4(b) and draw the plane view shown in Figure 4(c). The line segments AO, BO, and CO are perpendicular and congruent (i.e., AO=BO=CO=r), so we determine AB=AC=BC=2r. In Figure 4(c), O′ represents the projection of point O, which is located at the centre of the equilateral triangle △ABC. Note that CD=2/2r. We now calculate CO′=CD/cos30∘=2/2r/cos30∘=6/3r. The connecting line segments O′G and OG form the right triangle △GOO′, as shown in Figures 4(b) and 4(d). In Figure 4(d), φ=∠COO′ is exactly on the direction angle we need to calculate; that is, φ=arcsin6/3≈54.74∘. Note that φ is not related to the radius r. Next, we draw a plane view of the spherical sector projection on the plane, as shown in Figure 4(e). We know that 2φ is not equal to the true angle at which the spherical sector O—ABC is projected onto the plane, 2φ≠∠COG; the inner angle of the calculated ∠COG=90∘. Therefore, we can get the minimum sensing angle θ when the condition θ=arcsin6/3 is satisfied, as shown in Figure 4(e). At this time, the regular triangular pyramid OABC is surrounded by the spherical sector O—A1B1C1. Meanwhile, when the projected fan’s central angle 2θ≥2arcsin6/3, the spherical sector sensing area contains the polyhedron O—ABC.In summary, we first assume that the node’s central angle2θ≥2arcsin6/3 can meet the required coverage. We then specify that a target point px,y,z is to be covered by the sensor node sixi,yi,zi, subject to the following conditions:
(i)
The Euclidean distance between pointsp and si must be less than or equal to the maximum sensing distance of the node; that is, dsi,p≤Rs
(ii)
The angleφ formed between the vector from p to si and the node’s main sensing direction must be less than θ; that is, φ≤arcsin6/3≈54.74∘
(iii)
The central angle of the directed sensing model satisfies2θ≥2arcsin6/3≈109.5∘


### 3.3. Related Definitions

For a more intuitive follow-up analysis and discussion of this article, we introduce the following definitions to better describe the problem.Definition 1 (3D-directed node sensing model).
A 3D-directed sensing model can be represented by the five-tuple<six,y,z,w,Rs,2θ,ψ>, where si, w, Rs, 2θ (0≤θ≤π), and ψ represent the vertex position coordinate, the main sensing direction vector, the node’s sensing radius, the node’s sensing angle, and the node’s sensing direction, respectively.Definition 2 (neighbour node).
Each node is unique within the Voronoi; therefore, according to reference [29], we can specify that two sensor nodes that have the same neighbouring edge are neighbouring nodes.Definition 3 (network coverage ratio).
We refer to the sensing accuracy model in [27] to determine the probability that any point p in space is monitored by node si. Assuming that the sensing accuracy C decays as the distance increases, the sensing accuracy Csi,p is
(1)Csi,p=11+αdsi,pβ,where Csi,p represents the sensing accuracy of sensor si at point p and dsi,p represents the Euclidean distance from point p to si, which can be calculated as
(2)dsi,p=x−xi2+y−yi2+z−zi2.Constantsα and β reflect the device correlation coefficient for the physical characteristics of the sensor. Typically, β has a range of (1~4) and α is used as an adjustment parameter.A target in the monitoring area can be covered simultaneously by multiple sensor nodes, and its coverage probabilityC can be expressed as
(3)C=1−∏i=1N1−Csi,p,which is equivalent to
(4)C=1−∏i=1N1−11+αdsi,pβ.


## 3.1. Network Coverage Model

First, we assume that the sensing model of the sensor node covers a sphere with its midpoint at the node’s positionoixi,yi,zi and its sensing range Rs is the maximum detection distance. Initially, it is assumed that sensor nodes si are randomly scattered in an L3 target area, and the set of nodes is sis1,s2,⋯,sn. Rc represents the communication radius of the node, when the Euclidean distance between two nodes si and sj satisfies dsi,sj<Rc; we call them neighbour nodes [26]. In a traditional 2D study, most researchers transform the sensor nodes into a 2D planar fan to achieve coverage optimisation. In some related 3D research fields, the node’s sensing range is abstracted into a covering model of a rounded hammer. However, the coverage model of the 3D directional sensor should be obtained by rotating a planar fan with radius Rs and central angle 2θ around its axis of symmetry, as shown in Figure 1. Therefore, we define the directional node’s sensing range as a spherical sector sensing model. As shown in Figure 1, the spherical sector O—A1B1C1 represents the coverage model of the directional sensor. When 2θ=360°, its coverage matches that of the omnidirectional sensor node. Therefore, the spherical sector network model redefined in this paper is more suitable for modelling the coverage of 3D sensor nodes.Figure 1
Spherical sector sensing model.Initially, sensor nodes are randomly scattered in the target monitoring area, which may result in an uneven node distribution, excessive node energy consumption, and duplicate or missing coverage for some targets. In Figure2, the grey dots indicate targets that need to be covered, and the three spherical sectors represent sensor coverage. Some of the targets in Figure 2 are not completely covered. Therefore, the sensor network may also have omission problems, resulting in lower node utilisation. Before designing a 3D DSNs coverage algorithm based on the 3D Voronoi diagram partition, the following assumptions are made:
(i)
The sensor nodes are isomorphic, and each node has access to its own location and that of its neighbour nodes through some technical means
(ii)
Each node has the same detection range, but its sensing range can be different; that is, each sensor can select different sensing angles2θ, where each si can select its own sensing angle 2θi
(iii)
Each node can rotate and move freely in any directionFigure 2
Target detection model.


## 3.2. Model Angle Quantification

In previous studies, the randomly distributed target pointp in space is covered by the directional node si and the basic conditions doi,p≤Rs and ∣φ≤θ∣ need to be satisfied. Most studies [27, 28] use the partitioning model shown in Figure 3 to specify angles. However, it is difficult for this model to quantify the angle φ between the target point p and the node si. In particular, it is difficult to determine the necessary rotation amount when a node must rotate to cover a target. Furthermore, the sensing model and direction angle partitioning of Figure 3 is abstract and impractical for directional sensor nodes with differing θ and varying main direction angle ψ.Figure 3
Node sensing direction.Therefore, we redefine the sensing model and propose an angle and direction division method using one octant of a sphere to unify the rotation as shown in Figure4. As long as the spherical sector busbar is exactly tangent to the three edges of O—ABC (i.e., the spherical sector contains O—ABC), coverage can be achieved by rotating the model to the coordinate system in which the target event is located—when the condition dsi,p≤Rs is satisfied. The above assumptions can reduce omissions and node energy consumption. In this regard, we subsequently respecified the conditions under which the target event can be covered by the directed node.Figure 4
Angle division of sensing model.
(a)
(b)
(c)
(d)
(e)As shown in Figure4, we cut the sphere of radius r along its axes of symmetry to divide it into eight parts; that is, the shaded portion in Figure 4(a) is the isolated polyhedron O—ABC. For a more intuitive understanding and for analysis and quantification, we separately extract the shaded parts removed in Figure 4(a) and draw the perspective view shown in Figure 4(b). To quantify the angle θ in our model, we need to solve for ∠COO′. Therefore, we project the point O onto a plane containing O′ that is perpendicular to the line passing through O and O′. For a more intuitive understanding and analysis, we separately extract the triangle △ABC in Figure 4(b) and draw the plane view shown in Figure 4(c). The line segments AO, BO, and CO are perpendicular and congruent (i.e., AO=BO=CO=r), so we determine AB=AC=BC=2r. In Figure 4(c), O′ represents the projection of point O, which is located at the centre of the equilateral triangle △ABC. Note that CD=2/2r. We now calculate CO′=CD/cos30∘=2/2r/cos30∘=6/3r. The connecting line segments O′G and OG form the right triangle △GOO′, as shown in Figures 4(b) and 4(d). In Figure 4(d), φ=∠COO′ is exactly on the direction angle we need to calculate; that is, φ=arcsin6/3≈54.74∘. Note that φ is not related to the radius r. Next, we draw a plane view of the spherical sector projection on the plane, as shown in Figure 4(e). We know that 2φ is not equal to the true angle at which the spherical sector O—ABC is projected onto the plane, 2φ≠∠COG; the inner angle of the calculated ∠COG=90∘. Therefore, we can get the minimum sensing angle θ when the condition θ=arcsin6/3 is satisfied, as shown in Figure 4(e). At this time, the regular triangular pyramid OABC is surrounded by the spherical sector O—A1B1C1. Meanwhile, when the projected fan’s central angle 2θ≥2arcsin6/3, the spherical sector sensing area contains the polyhedron O—ABC.In summary, we first assume that the node’s central angle2θ≥2arcsin6/3 can meet the required coverage. We then specify that a target point px,y,z is to be covered by the sensor node sixi,yi,zi, subject to the following conditions:
(i)
The Euclidean distance between pointsp and si must be less than or equal to the maximum sensing distance of the node; that is, dsi,p≤Rs
(ii)
The angleφ formed between the vector from p to si and the node’s main sensing direction must be less than θ; that is, φ≤arcsin6/3≈54.74∘
(iii)
The central angle of the directed sensing model satisfies2θ≥2arcsin6/3≈109.5∘


## 3.3. Related Definitions

For a more intuitive follow-up analysis and discussion of this article, we introduce the following definitions to better describe the problem.Definition 1 (3D-directed node sensing model).
A 3D-directed sensing model can be represented by the five-tuple<six,y,z,w,Rs,2θ,ψ>, where si, w, Rs, 2θ (0≤θ≤π), and ψ represent the vertex position coordinate, the main sensing direction vector, the node’s sensing radius, the node’s sensing angle, and the node’s sensing direction, respectively.Definition 2 (neighbour node).
Each node is unique within the Voronoi; therefore, according to reference [29], we can specify that two sensor nodes that have the same neighbouring edge are neighbouring nodes.Definition 3 (network coverage ratio).
We refer to the sensing accuracy model in [27] to determine the probability that any point p in space is monitored by node si. Assuming that the sensing accuracy C decays as the distance increases, the sensing accuracy Csi,p is
(1)Csi,p=11+αdsi,pβ,where Csi,p represents the sensing accuracy of sensor si at point p and dsi,p represents the Euclidean distance from point p to si, which can be calculated as
(2)dsi,p=x−xi2+y−yi2+z−zi2.Constantsα and β reflect the device correlation coefficient for the physical characteristics of the sensor. Typically, β has a range of (1~4) and α is used as an adjustment parameter.A target in the monitoring area can be covered simultaneously by multiple sensor nodes, and its coverage probabilityC can be expressed as
(3)C=1−∏i=1N1−Csi,p,which is equivalent to
(4)C=1−∏i=1N1−11+αdsi,pβ.


## 4. Voronoi Partitioning Method

### 4.1. 2D Voronoi Principle

In the early research of two dimensional DSN coverage, nodes are randomly distributed in the plane and divided into the 2D Voronoi method. As shown in Figure5, given a set of sensor nodes si=s1,s2,⋯,sn, the bounded plane is divided into polygonal cells Ki=K1,K2,⋯,Kn, such that each cell Ki contains exactly one of the sensor nodes si, where si is called the Ki-divided generation node [14, 30]. Furthermore, according to the partitioning property of the Voronoi diagram, the distance Dsi,T from any point T in cell Ki to si is shorter than the distance Dsj,T between the point T and the neighbour nodes of si.Figure 5
2D Voronoi diagram.As shown in Figure6, there are 70 sensor nodes in the plane and the grey area represents the coverage of each node. After division, each Voronoi unit corresponds to a single node.Figure 6
2D Voronoi node coverage.


### 4.2. 3D Voronoi Partition Principle

After reviewing the related 2D Voronoi research in the previous section, we extend it to divide three-dimensional volumes. The volume is divided into polyhedral Voronoi units called V-body units; each is an irregular, multifaceted, closed, convex body according to the literature [14]. Meanwhile, each unit Vi∈V1,V2,⋯,Vn contains a unique node si. Hence, according to the property of 2D-Voronoi, the 3D Voronoi partitioning definition satisfies
(5)QVi=Vi∈L3∣dT,si≤dT,sj,j=1,2,⋯,n−1,∀j≠i.It can be concluded from the aforementioned results that the number of nodesNsi is equal to the number of Voronoi units NVi after division; that is, Nsi=NVi,i=1,2,⋯,n. Thus, this paper first uses this important neighbouring property to divide and study the 3D coverage problem.


## 4.1. 2D Voronoi Principle

In the early research of two dimensional DSN coverage, nodes are randomly distributed in the plane and divided into the 2D Voronoi method. As shown in Figure5, given a set of sensor nodes si=s1,s2,⋯,sn, the bounded plane is divided into polygonal cells Ki=K1,K2,⋯,Kn, such that each cell Ki contains exactly one of the sensor nodes si, where si is called the Ki-divided generation node [14, 30]. Furthermore, according to the partitioning property of the Voronoi diagram, the distance Dsi,T from any point T in cell Ki to si is shorter than the distance Dsj,T between the point T and the neighbour nodes of si.Figure 5
2D Voronoi diagram.As shown in Figure6, there are 70 sensor nodes in the plane and the grey area represents the coverage of each node. After division, each Voronoi unit corresponds to a single node.Figure 6
2D Voronoi node coverage.


## 4.2. 3D Voronoi Partition Principle

After reviewing the related 2D Voronoi research in the previous section, we extend it to divide three-dimensional volumes. The volume is divided into polyhedral Voronoi units called V-body units; each is an irregular, multifaceted, closed, convex body according to the literature [14]. Meanwhile, each unit Vi∈V1,V2,⋯,Vn contains a unique node si. Hence, according to the property of 2D-Voronoi, the 3D Voronoi partitioning definition satisfies
(5)QVi=Vi∈L3∣dT,si≤dT,sj,j=1,2,⋯,n−1,∀j≠i.It can be concluded from the aforementioned results that the number of nodesNsi is equal to the number of Voronoi units NVi after division; that is, Nsi=NVi,i=1,2,⋯,n. Thus, this paper first uses this important neighbouring property to divide and study the 3D coverage problem.


## 5. VFA Analysis and 3D-DAOA

As discussed earlier, directional sensor network nodes can be separated into a unique set of nonoverlapping V-body units by the 3D Voronoi partitioning method after an initial, random deployment. We know a target may not be detected by a given node, and each target could be located in any V-body unit. Additionally, according to the Voronoi partitioning property, we will first consider nodes preferentially covering targets in that node’s V-body unit, for which we need to design related node rotation and movement algorithms to achieve coverage.


### 5.1. Definitions of VFA

In sensor network coverage, the VFA (virtual force algorithm) [31] algorithm has enabled nodes deployed in the monitoring environment to be redeployed by different virtual field forces. The concept of a virtual force first came from physics; that is, when the distance between two atoms is too small, they are separated by the repulsion between them. When the distance between two atoms is too large, gravity is generated, bringing them closer to each other [14, 32]. In this article, we need to redesign an improved 3D-VFA to solve the following problems:
(i)
Redeploying a node in a 3D Voronoi partition to accurately cover uncovered targets
(ii)
Quantifying the node’s rotation angle and the unity of the node’s coordinate system
(iii)
Defining the virtual forces—those generated between nodes (e.g., mutual attraction and repulsion) and obstacle repulsion between the forces—to move the directional nodes to complete the coverage


### 5.2. Improved 3D-VFA Analysis

Through the above definition of virtual forces, we mainly address directional node mobility. During optimisation, nodes move under a total resultant forceFA, thereby achieving node balance and uniform target coverage. In the monitoring region, we assume that a sensor node is subject to a gravitational force Fa from neighbouring nodes, an interaction force Fij from nodes, and a force Fo between the node and the boundary of the target region L. The total force FA is therefore
(6)FA=∑j=1,j≠inFij+Fa+Fo.We further constrain our virtual forces to prevent the node from running out of energy prematurely due to excessive node movement. We introduce two distance thresholds:rmin represents the minimum safe distance between nodes and rb represents the distance beyond which the interaction force between the nodes is zero. According to the literature [14, 33], equation (7) defines the interaction force Fij between the nodes as
(7)Fij=+∞,0<dsi,sj≤rmin,k1mimjdsi,sja1,rmin<dsi,sj<rb,0,dsi,sj=rb,−k2mimjdsi,sja2,rb<dsi,sj≤Rc,0,dsi,sj>Rc.Here,k1, k2, a1, and a2 represent gain coefficients and mi and mjrepresent the node quality factor (typically with value of 1). When the distance between two nodes dsi,sj satisfies the condition rmin<dsi,sj<rb, the nodes are mutually exclusive.To enable the node to perform motion detection on targets that are far away, we set the targetTi as the attraction source for the node. In addition, we consider the problem of incompleteness of the node-aware signals as mentioned in [34]. Therefore, we establish the force between the sensing model’s centre of gravity and the target. In this paper, the centre of gravity of the spherical fan is at Gi and the centre of gravity of the spherical sector is
(8)Gi=382r−h,where r represents the length of the spherical sector busbar (i.e., r=Rs) and h represents the length of the point F and the vertex C′ in the plane sector, as shown in Figure 4(e), then h=FC1=r1−cosθ. Therefore, we can calculate the centre of gravity Gi for the node model (i.e., Gi=3/82r−h=3/8r1+cosθ). The gravitational pull of the target on the node’s centre of gravity can be calculated as
(9)Fa=−k3mGimTidGi,Tiae,j∈QT,0,otherwise,where k3 and ae represent the gain coefficient and dGi,Ti represents the Euclidean distance from the node’s centre of gravity Gi to target Ti. Additionally, mTi and mGi represent quality factors of target Ti and node model Gi, respectively. QT represents the force generated by the target set T in the region of action.Additionally, to avoid collisions between nodes and obstacles during movement, we must add a boundary repulsionFo—this ensures the distance between nodes is in the optimal range. According to [14], boundary repulsion is calculated as
(10)Fo=k4mimjdsi,sjab,0<dsi,sj≤L,0,dsi,sj>L,where k4 and ab are the gain coefficients and dsi,sj is the distance between node si and the obstacle. When the distance between the node and the obstacle is within L, the node is repelled by the obstacle.


### 5.3. 3D-DAOA

We design related algorithms to solve two core issues encountered with directional sensor nodes: node rotation and mobility in [29]. We now describe a dynamic adjustment optimisation algorithm for 3D DSNs based on spherical sector coverage models: 3D-DAOA. Meanwhile, to address the issues encountered with the original VFA approach, we designed the dynamic coverage adjustment strategy and combined it with 3D-VFA shown below. If the deployed sensor node can cover the target by rotating, rotation takes priority, and we reduce the activity of the node’s mobility coverage method. Therefore, we present the design steps and pseudocode of the algorithm in this paper.Step 1.
Deploy the numbern of sensor nodes si in the monitoring area L.Step 2.
The 3D Voronoi method is used to divide the regionL where the sensor nodes si are located, leaving each node is in its own Voronoi unit vi.Step 3.
For each directional sensor, we set its coordinate system origin to the sensor’s position and define the central angle2θ of the node’s sensing model, where2θ≥2arcsin6/3≈109.5∘.Step 4.
Assuming that the position information of the target pointTj is known, we test the conditions dsi,Tj≤Rs and φ≤θ. If both are true, we store the number of targets that have been covered NTk and the number of nodes that are covering the target NSk and execute Step 5; otherwise, we execute Step 13.Step 5.
Evaluatedsi,Tj≤Rs again. If it is true, we calculate the number of target points NTf and proceed to Step 7; otherwise, we execute Step 12.Step 6.
Calculate the set of anglesσ between each target that has been covered Tk and the main direction axis w→ and find the smallest angle σmin among them.Step 7.
Calculate the numberNTs of remaining targets Ts; that is,NTs=NTf−NTk.Step 8.
Determine whether the angleξ between Ts and w→ satisfies the conditions ξ<θ+σmin or ξ<θ−σmin.Step 9.
If one of the above conditions is satisfied, the main direction axis of the node is rotated byθ+σmin or ξ<θ−σmin toward the target point Ts. Otherwise, the target that is not currently covered Ta is marked, and we execute Step 10.Step 10.
The remaining nodes are retained, rotation is stopped, and the number of nodesN2 is calculated.Step 11.
The resultant forceFa of the idle neighbour node and Ta is introduced to move the idle neighbour node SI to cover Ta.Step 12.
Calculate the total number of remaining nodesNsc and the number of targets that are not covered NTc.Step 13.
We use the resultant forceFA to move the remaining nodes Sc to Tc.Step 14.
Repeat Steps4, 5, 6, 7, 8, 9, 10, 11, 12 and 13 a set number of iterations until all nodes move to the optimal position and complete the final coverage.In this paper, the 3D Voronoi method is first used to divide the space in which the nodes are located, allowing us to determine whether a target is located inside a Voronoi unit—though a target might not be contained in any units. As the number of nodes increases, so does the density of the increasingly compact V-body units; therefore, with a large number of nodes and events, our method can more accurately divide the space for target detection. However, this paper aims to use algorithms to improve network coverage ratios and increase average node residual energy. Our main goal is to find a better balance between the node utilisation and remaining energy to extend the network lifetime. To achieve this, we design the node’s coverage rotation mechanism, priority coverage mechanism, and movement mechanism. We first design the discriminant condition of the algorithm by combining the 3D Voronoi partitioning method with an optimised core adjustment mechanism. The pseudocode of 3D-DAOA is shown in Algorithm1.Algorithm 1: Dynamic adjustment optimisation algorithm (3D-DAOA).
1 Input1: The total numbern of sensor nodes si and the perceived radius of the nodes Rs
2 Input2:Ti  // The area of the targets
3 // Randomly generate the numbern of nodes si in the area L of 100m3 size
4L = Polyhedron ([0 0 0;1 0 0;1 1 0;0 1 0;0 0 1;1 0 1;1 1 1;0 1 1] ∗ 100)
5si=gallery′unformdata′,3,n,0 ∗ 100
6 Maxiter = 50   // Set the maximum number of iterations
7 Max_Step = 0~10 // Set the maximum moving step size of the node
8θi=2θ    // Set the initial angle of all directional nodes
9Pi=Locationsi // Get location information for all nodes six,y,z
10vi,L=VoronoiPi,R3  // Divide V-body units ∈ vi, vi=v1,v2,⋯,vn
11if dsi,Tj≤Rs && φ≤θ
12Tk=SizeNTk && Sk=SizeNSk
13 // Calculate the number of targets that have been coveredNTk
14 // Calculate the number nodes that are covering the targetNSk
15while i≤Num do
16if dsi,Tj≤Rs then
17NTf=SizeTf && σi=Sizeθmin
18 // Calculate the number of target pointsNTf and the minimum angle σmin
19 // Calculate the number of target points covered by the same nodeNTs
20else
21  Select the free neighbour nodesNTsNTs=NTf−NTk to move to cover Ta
22if ξ<θ+σminξ<θ−σmin then
23  Rotate the main direction axisw→ by θ±σmin
24else
25NTs=SizeTs
26// Calculate the number of target points that are currently not covered NTs
27FA=∑j=1,j≠inFa+Fij+Fo    // Calculate the total force FA
28  MoveSc→Tc
29end if
30  Set the number of iterations and repeat lines 12-29 until coverage is complete
31end if
32end while


## 5.1. Definitions of VFA

In sensor network coverage, the VFA (virtual force algorithm) [31] algorithm has enabled nodes deployed in the monitoring environment to be redeployed by different virtual field forces. The concept of a virtual force first came from physics; that is, when the distance between two atoms is too small, they are separated by the repulsion between them. When the distance between two atoms is too large, gravity is generated, bringing them closer to each other [14, 32]. In this article, we need to redesign an improved 3D-VFA to solve the following problems:
(i)
Redeploying a node in a 3D Voronoi partition to accurately cover uncovered targets
(ii)
Quantifying the node’s rotation angle and the unity of the node’s coordinate system
(iii)
Defining the virtual forces—those generated between nodes (e.g., mutual attraction and repulsion) and obstacle repulsion between the forces—to move the directional nodes to complete the coverage


## 5.2. Improved 3D-VFA Analysis

Through the above definition of virtual forces, we mainly address directional node mobility. During optimisation, nodes move under a total resultant forceFA, thereby achieving node balance and uniform target coverage. In the monitoring region, we assume that a sensor node is subject to a gravitational force Fa from neighbouring nodes, an interaction force Fij from nodes, and a force Fo between the node and the boundary of the target region L. The total force FA is therefore
(6)FA=∑j=1,j≠inFij+Fa+Fo.We further constrain our virtual forces to prevent the node from running out of energy prematurely due to excessive node movement. We introduce two distance thresholds:rmin represents the minimum safe distance between nodes and rb represents the distance beyond which the interaction force between the nodes is zero. According to the literature [14, 33], equation (7) defines the interaction force Fij between the nodes as
(7)Fij=+∞,0<dsi,sj≤rmin,k1mimjdsi,sja1,rmin<dsi,sj<rb,0,dsi,sj=rb,−k2mimjdsi,sja2,rb<dsi,sj≤Rc,0,dsi,sj>Rc.Here,k1, k2, a1, and a2 represent gain coefficients and mi and mjrepresent the node quality factor (typically with value of 1). When the distance between two nodes dsi,sj satisfies the condition rmin<dsi,sj<rb, the nodes are mutually exclusive.To enable the node to perform motion detection on targets that are far away, we set the targetTi as the attraction source for the node. In addition, we consider the problem of incompleteness of the node-aware signals as mentioned in [34]. Therefore, we establish the force between the sensing model’s centre of gravity and the target. In this paper, the centre of gravity of the spherical fan is at Gi and the centre of gravity of the spherical sector is
(8)Gi=382r−h,where r represents the length of the spherical sector busbar (i.e., r=Rs) and h represents the length of the point F and the vertex C′ in the plane sector, as shown in Figure 4(e), then h=FC1=r1−cosθ. Therefore, we can calculate the centre of gravity Gi for the node model (i.e., Gi=3/82r−h=3/8r1+cosθ). The gravitational pull of the target on the node’s centre of gravity can be calculated as
(9)Fa=−k3mGimTidGi,Tiae,j∈QT,0,otherwise,where k3 and ae represent the gain coefficient and dGi,Ti represents the Euclidean distance from the node’s centre of gravity Gi to target Ti. Additionally, mTi and mGi represent quality factors of target Ti and node model Gi, respectively. QT represents the force generated by the target set T in the region of action.Additionally, to avoid collisions between nodes and obstacles during movement, we must add a boundary repulsionFo—this ensures the distance between nodes is in the optimal range. According to [14], boundary repulsion is calculated as
(10)Fo=k4mimjdsi,sjab,0<dsi,sj≤L,0,dsi,sj>L,where k4 and ab are the gain coefficients and dsi,sj is the distance between node si and the obstacle. When the distance between the node and the obstacle is within L, the node is repelled by the obstacle.


## 5.3. 3D-DAOA

We design related algorithms to solve two core issues encountered with directional sensor nodes: node rotation and mobility in [29]. We now describe a dynamic adjustment optimisation algorithm for 3D DSNs based on spherical sector coverage models: 3D-DAOA. Meanwhile, to address the issues encountered with the original VFA approach, we designed the dynamic coverage adjustment strategy and combined it with 3D-VFA shown below. If the deployed sensor node can cover the target by rotating, rotation takes priority, and we reduce the activity of the node’s mobility coverage method. Therefore, we present the design steps and pseudocode of the algorithm in this paper.Step 1.
Deploy the numbern of sensor nodes si in the monitoring area L.Step 2.
The 3D Voronoi method is used to divide the regionL where the sensor nodes si are located, leaving each node is in its own Voronoi unit vi.Step 3.
For each directional sensor, we set its coordinate system origin to the sensor’s position and define the central angle2θ of the node’s sensing model, where2θ≥2arcsin6/3≈109.5∘.Step 4.
Assuming that the position information of the target pointTj is known, we test the conditions dsi,Tj≤Rs and φ≤θ. If both are true, we store the number of targets that have been covered NTk and the number of nodes that are covering the target NSk and execute Step 5; otherwise, we execute Step 13.Step 5.
Evaluatedsi,Tj≤Rs again. If it is true, we calculate the number of target points NTf and proceed to Step 7; otherwise, we execute Step 12.Step 6.
Calculate the set of anglesσ between each target that has been covered Tk and the main direction axis w→ and find the smallest angle σmin among them.Step 7.
Calculate the numberNTs of remaining targets Ts; that is,NTs=NTf−NTk.Step 8.
Determine whether the angleξ between Ts and w→ satisfies the conditions ξ<θ+σmin or ξ<θ−σmin.Step 9.
If one of the above conditions is satisfied, the main direction axis of the node is rotated byθ+σmin or ξ<θ−σmin toward the target point Ts. Otherwise, the target that is not currently covered Ta is marked, and we execute Step 10.Step 10.
The remaining nodes are retained, rotation is stopped, and the number of nodesN2 is calculated.Step 11.
The resultant forceFa of the idle neighbour node and Ta is introduced to move the idle neighbour node SI to cover Ta.Step 12.
Calculate the total number of remaining nodesNsc and the number of targets that are not covered NTc.Step 13.
We use the resultant forceFA to move the remaining nodes Sc to Tc.Step 14.
Repeat Steps4, 5, 6, 7, 8, 9, 10, 11, 12 and 13 a set number of iterations until all nodes move to the optimal position and complete the final coverage.In this paper, the 3D Voronoi method is first used to divide the space in which the nodes are located, allowing us to determine whether a target is located inside a Voronoi unit—though a target might not be contained in any units. As the number of nodes increases, so does the density of the increasingly compact V-body units; therefore, with a large number of nodes and events, our method can more accurately divide the space for target detection. However, this paper aims to use algorithms to improve network coverage ratios and increase average node residual energy. Our main goal is to find a better balance between the node utilisation and remaining energy to extend the network lifetime. To achieve this, we design the node’s coverage rotation mechanism, priority coverage mechanism, and movement mechanism. We first design the discriminant condition of the algorithm by combining the 3D Voronoi partitioning method with an optimised core adjustment mechanism. The pseudocode of 3D-DAOA is shown in Algorithm1.Algorithm 1: Dynamic adjustment optimisation algorithm (3D-DAOA).
1 Input1: The total numbern of sensor nodes si and the perceived radius of the nodes Rs
2 Input2:Ti  // The area of the targets
3 // Randomly generate the numbern of nodes si in the area L of 100m3 size
4L = Polyhedron ([0 0 0;1 0 0;1 1 0;0 1 0;0 0 1;1 0 1;1 1 1;0 1 1] ∗ 100)
5si=gallery′unformdata′,3,n,0 ∗ 100
6 Maxiter = 50   // Set the maximum number of iterations
7 Max_Step = 0~10 // Set the maximum moving step size of the node
8θi=2θ    // Set the initial angle of all directional nodes
9Pi=Locationsi // Get location information for all nodes six,y,z
10vi,L=VoronoiPi,R3  // Divide V-body units ∈ vi, vi=v1,v2,⋯,vn
11if dsi,Tj≤Rs && φ≤θ
12Tk=SizeNTk && Sk=SizeNSk
13 // Calculate the number of targets that have been coveredNTk
14 // Calculate the number nodes that are covering the targetNSk
15while i≤Num do
16if dsi,Tj≤Rs then
17NTf=SizeTf && σi=Sizeθmin
18 // Calculate the number of target pointsNTf and the minimum angle σmin
19 // Calculate the number of target points covered by the same nodeNTs
20else
21  Select the free neighbour nodesNTsNTs=NTf−NTk to move to cover Ta
22if ξ<θ+σminξ<θ−σmin then
23  Rotate the main direction axisw→ by θ±σmin
24else
25NTs=SizeTs
26// Calculate the number of target points that are currently not covered NTs
27FA=∑j=1,j≠inFa+Fij+Fo    // Calculate the total force FA
28  MoveSc→Tc
29end if
30  Set the number of iterations and repeat lines 12-29 until coverage is complete
31end if
32end while


## 6. Experiment Simulation and Discussion

### 6.1. Simulation Environment and Results

In this section, we use MATLAB (2015b) to perform simulation experiments to verify the performance of the proposed algorithm. Initially, we randomly deploy the sensor nodes into a 100 m3 cube to test the target points of the deployment. According to [35], when node deployment is low, the optimal node distance to ensure network connectivity is Rc=2Rs. When the number of nodes is large, the optimal distance for network connectivity is Rc=3Rs. The simulation parameters are listed in Table 1.Table 1
Parameter settings.
Name
Value
Simulation area size,L
100 m3
Total number of targets,Noi
25
Number of nodes,n
60/100
Sensing radius,Rs
10~60 m
Node communication radius,Rc
Rc=2Rs
Initial residual energy,E
30 J
rmin
Rs×3%~7%
α
0.5
β
0.5
Angle of view,θ
10∘≤θ≤90∘We first deploy the nodes, as shown in Figure7(a), where the blue cone represents the directional nodes. In the first set of experiments shown in Figure 7, 60 directional sensor nodes were randomly deployed in a 100 m3 space. During the algorithm, the 3D Voronoi partitioning method is used to divide the space into 60 different V-body units using the number and positions of the nodes, such that each node si is located in the respective unit vi, as shown in Figure 7(b). As shown in Figure 7(c) a red dot represents a target to be covered and a blue cone represents the node of the target covered by the algorithm movement adjustment. The black cone indicates the node’s change of the position toward a target that is not within the coverage range of the algorithm. The simulation results show that when the position coordinates of 25 targets are known, the number of targets covered by nodes is firstly calculated under the adjustment of the algorithm. When the target is not within the node’s coverage, the algorithm selects some of the nodes to move.Figure 7
Simulation experiment diagrams: (a) initial node deployment; (b) experimental simulation process; (c) experimental simulation result.
(a)
(b)
(c)


### 6.2. Algorithm Analysis and Contrast Experiment

To further verify the accuracy of the experiment, we compared the 3D-DAOA with the random algorithm (RA) and the improved VFA algorithm [36]. In Experiment 1, we set the number of nodes N=25, the node’s angle of view AOV=55∘, and the number of target points T=60 to verify the relationship between the node’s detection radius and the coverage ratio. As shown in Figure 8, as the detection radius increases, the coverage ratio of the three algorithms also increases. However, the coverage of the proposed algorithm is significantly higher than that of the other two algorithms. It can also be seen from Figure 8 that the coverage ratio of the algorithm first reaches full coverage when the sensing radius is 60 m, because the algorithm can reasonably divide the node position from the beginning, and it can achieve precise coverage through rotation or movement by setting the priority adjustment strategy. Therefore, the proposed algorithm can reduce coverage redundancy and greatly improve the coverage ratio of the overall network.Figure 8
Coverage ratio with increasing sensing ratio.In Experiment 2, we verified the effect on the coverage ratio of changing the node’s viewing angle as shown in Figure9, where we see that the coverage of the three algorithms increases as the viewing angle increases; however, this increase is less than that caused by increasing the detection radius, because different fields of view (FOV) of the same node have different effects on the coverage ratio. Therefore, having a larger FOV achieves a larger coverage range; that is, the probability of covering a target also increases. The advantage of the proposed algorithm is that it can better determine the current location of nodes and targets, and it uses the priority coverage mechanism or idle nodes to achieve a higher coverage ratio.Figure 9
Coverage ratio with increasing field of view.Sensor nodes typically carry a power source with limited energy, and it is difficult to replenish this energy. Therefore, we need to use energy reasonably. In this experiment, the node’s rotational and mobile energy consumption make up a large portion of its total energy consumption. According to [13, 37], a single directional node rotating 180° consumes 1.52 J of energy; this means a single node rotating 1 degree consumes 0.009 J. However, each node consumes 3.6 J per 1 m of movement.In Experiment 3, we assume the number of nodesN=25, the angle of view θ=55°, and that the initial energy of each node is 30 J to verify the relationship between the average residual energy and the coverage ratio in the three algorithms. As shown in Figures 10 and 11, when the viewing angles of the nodes are the same, in each algorithm, the average residual energy decreases as the angle increases, while the coverage ratio of the nodes increases as the angle increases. The improved VFA algorithm has the lowest average residual energy, because it does not dynamically adjust the coverage mechanism, which leads to too many mobile nodes. Therefore, the VFA algorithm has the largest average node energy consumption. 3D-DAOA reasonably reduces unnecessary energy consumption to achieve a better balance while ensuring a high coverage ratio.Figure 10
Index values of each algorithm whenθ=45∘.Figure 11
Index values of each algorithm whenθ=55∘.We now compare the residual energy of a single node in the three algorithms with the total coverage ratio when the angles take different values, as shown in Table2. From this, we conclude that the total value of the two index values for the proposed algorithm is greatest when the angle of view is 55°, because 3D-DAOA can appropriately balance the network coverage and energy consumption. Furthermore, it comprehensively considers a variety of factors and indicators to achieve better detection results.Table 2
Average node residual energy and coverage ratio values for the three algorithms.
Angle of view,θ
Random algorithm
Improved VFA
3D-DAOA
Residual energy
Coverage ratio (%)
Total value
Residual energy
Coverage ratio (%)
Total value
Residual energy
Coverage ratio (%)
Total value
45°
29.71
34
63.71
17.06
43
60.06
24.51
52
76.51
55°
29.35
37
66.35
14.31
48
62.31
22.46
61
83.46
60°
29.17
39
68.17
11.52
53
64.52
20.33
63
83.33Combining the data in Figures10 and 11 with Table 2, we conclude that the node’s residual energy after the random algorithm has almost no change and the coverage rate is the lowest, because this algorithm does not cause the node to rotate or move based on the target’s position. Under the same evaluation index conditions, the proposed algorithm has obvious advantages over the improved VFA algorithm: the algorithm’s priority coverage mechanism achieves accurate target coverage, the dynamic adjustment mechanism avoids invalid node movement, and the algorithm’s coverage strategy is better when the angle of view is 55°.In Experiments 4 and 5, we verified the relationship between the number of nodes and the coverage ratio. In Experiment 4, we setN=25, θ=55°, T=60, and Rs=30m, as shown in Figure 12. We conclude that as the number of nodes increases, the overall coverage ratio of the three algorithms increases. Figure 12 also shows that when there are fewer nodes, the coverage ratio of the three algorithms is lower. The coverage of the random algorithm and the improved VFA algorithm is lower than that of 3D-DAOA, especially when the number of nodes exceeds 30.Figure 12
The effect of changes in the number of nodes on the coverage ratio (when the number of the targets is small).In Experiment 5, settingT=100 does not change other indicators, as shown in Figure 13. Additionally, when the number of target points is large, the proposed algorithm has a higher coverage ratio. Therefore, under the same conditions, the proposed algorithm is more suitable for large-scale target detection, because the adjustment mechanism of 3D-DAOA enables the node to accurately cover the target.Figure 13
The effect of changes in the number of nodes on the coverage ratio (when the number of the target points is large).


## 6.1. Simulation Environment and Results

In this section, we use MATLAB (2015b) to perform simulation experiments to verify the performance of the proposed algorithm. Initially, we randomly deploy the sensor nodes into a 100 m3 cube to test the target points of the deployment. According to [35], when node deployment is low, the optimal node distance to ensure network connectivity is Rc=2Rs. When the number of nodes is large, the optimal distance for network connectivity is Rc=3Rs. The simulation parameters are listed in Table 1.Table 1
Parameter settings.
Name
Value
Simulation area size,L
100 m3
Total number of targets,Noi
25
Number of nodes,n
60/100
Sensing radius,Rs
10~60 m
Node communication radius,Rc
Rc=2Rs
Initial residual energy,E
30 J
rmin
Rs×3%~7%
α
0.5
β
0.5
Angle of view,θ
10∘≤θ≤90∘We first deploy the nodes, as shown in Figure7(a), where the blue cone represents the directional nodes. In the first set of experiments shown in Figure 7, 60 directional sensor nodes were randomly deployed in a 100 m3 space. During the algorithm, the 3D Voronoi partitioning method is used to divide the space into 60 different V-body units using the number and positions of the nodes, such that each node si is located in the respective unit vi, as shown in Figure 7(b). As shown in Figure 7(c) a red dot represents a target to be covered and a blue cone represents the node of the target covered by the algorithm movement adjustment. The black cone indicates the node’s change of the position toward a target that is not within the coverage range of the algorithm. The simulation results show that when the position coordinates of 25 targets are known, the number of targets covered by nodes is firstly calculated under the adjustment of the algorithm. When the target is not within the node’s coverage, the algorithm selects some of the nodes to move.Figure 7
Simulation experiment diagrams: (a) initial node deployment; (b) experimental simulation process; (c) experimental simulation result.
(a)
(b)
(c)


## 6.2. Algorithm Analysis and Contrast Experiment

To further verify the accuracy of the experiment, we compared the 3D-DAOA with the random algorithm (RA) and the improved VFA algorithm [36]. In Experiment 1, we set the number of nodes N=25, the node’s angle of view AOV=55∘, and the number of target points T=60 to verify the relationship between the node’s detection radius and the coverage ratio. As shown in Figure 8, as the detection radius increases, the coverage ratio of the three algorithms also increases. However, the coverage of the proposed algorithm is significantly higher than that of the other two algorithms. It can also be seen from Figure 8 that the coverage ratio of the algorithm first reaches full coverage when the sensing radius is 60 m, because the algorithm can reasonably divide the node position from the beginning, and it can achieve precise coverage through rotation or movement by setting the priority adjustment strategy. Therefore, the proposed algorithm can reduce coverage redundancy and greatly improve the coverage ratio of the overall network.Figure 8
Coverage ratio with increasing sensing ratio.In Experiment 2, we verified the effect on the coverage ratio of changing the node’s viewing angle as shown in Figure9, where we see that the coverage of the three algorithms increases as the viewing angle increases; however, this increase is less than that caused by increasing the detection radius, because different fields of view (FOV) of the same node have different effects on the coverage ratio. Therefore, having a larger FOV achieves a larger coverage range; that is, the probability of covering a target also increases. The advantage of the proposed algorithm is that it can better determine the current location of nodes and targets, and it uses the priority coverage mechanism or idle nodes to achieve a higher coverage ratio.Figure 9
Coverage ratio with increasing field of view.Sensor nodes typically carry a power source with limited energy, and it is difficult to replenish this energy. Therefore, we need to use energy reasonably. In this experiment, the node’s rotational and mobile energy consumption make up a large portion of its total energy consumption. According to [13, 37], a single directional node rotating 180° consumes 1.52 J of energy; this means a single node rotating 1 degree consumes 0.009 J. However, each node consumes 3.6 J per 1 m of movement.In Experiment 3, we assume the number of nodesN=25, the angle of view θ=55°, and that the initial energy of each node is 30 J to verify the relationship between the average residual energy and the coverage ratio in the three algorithms. As shown in Figures 10 and 11, when the viewing angles of the nodes are the same, in each algorithm, the average residual energy decreases as the angle increases, while the coverage ratio of the nodes increases as the angle increases. The improved VFA algorithm has the lowest average residual energy, because it does not dynamically adjust the coverage mechanism, which leads to too many mobile nodes. Therefore, the VFA algorithm has the largest average node energy consumption. 3D-DAOA reasonably reduces unnecessary energy consumption to achieve a better balance while ensuring a high coverage ratio.Figure 10
Index values of each algorithm whenθ=45∘.Figure 11
Index values of each algorithm whenθ=55∘.We now compare the residual energy of a single node in the three algorithms with the total coverage ratio when the angles take different values, as shown in Table2. From this, we conclude that the total value of the two index values for the proposed algorithm is greatest when the angle of view is 55°, because 3D-DAOA can appropriately balance the network coverage and energy consumption. Furthermore, it comprehensively considers a variety of factors and indicators to achieve better detection results.Table 2
Average node residual energy and coverage ratio values for the three algorithms.
Angle of view,θ
Random algorithm
Improved VFA
3D-DAOA
Residual energy
Coverage ratio (%)
Total value
Residual energy
Coverage ratio (%)
Total value
Residual energy
Coverage ratio (%)
Total value
45°
29.71
34
63.71
17.06
43
60.06
24.51
52
76.51
55°
29.35
37
66.35
14.31
48
62.31
22.46
61
83.46
60°
29.17
39
68.17
11.52
53
64.52
20.33
63
83.33Combining the data in Figures10 and 11 with Table 2, we conclude that the node’s residual energy after the random algorithm has almost no change and the coverage rate is the lowest, because this algorithm does not cause the node to rotate or move based on the target’s position. Under the same evaluation index conditions, the proposed algorithm has obvious advantages over the improved VFA algorithm: the algorithm’s priority coverage mechanism achieves accurate target coverage, the dynamic adjustment mechanism avoids invalid node movement, and the algorithm’s coverage strategy is better when the angle of view is 55°.In Experiments 4 and 5, we verified the relationship between the number of nodes and the coverage ratio. In Experiment 4, we setN=25, θ=55°, T=60, and Rs=30m, as shown in Figure 12. We conclude that as the number of nodes increases, the overall coverage ratio of the three algorithms increases. Figure 12 also shows that when there are fewer nodes, the coverage ratio of the three algorithms is lower. The coverage of the random algorithm and the improved VFA algorithm is lower than that of 3D-DAOA, especially when the number of nodes exceeds 30.Figure 12
The effect of changes in the number of nodes on the coverage ratio (when the number of the targets is small).In Experiment 5, settingT=100 does not change other indicators, as shown in Figure 13. Additionally, when the number of target points is large, the proposed algorithm has a higher coverage ratio. Therefore, under the same conditions, the proposed algorithm is more suitable for large-scale target detection, because the adjustment mechanism of 3D-DAOA enables the node to accurately cover the target.Figure 13
The effect of changes in the number of nodes on the coverage ratio (when the number of the target points is large).


## 7. Conclusions

In this paper, we studied target coverage in 3D DSNs. First, we improved the traditional 3D directional sensing model and proposed a spherical sector model that is more suitable for 3D directional sensor nodes. Next, we unified the coordinate system of the nodes and rotated them to achieve coverage using the spherical sector model. We then quantified the sensing model’s perspective to provide an effective detection scheme for directional node coverage. We proposed a correlation algorithm and combined node rotation and mobility to achieve priority coverage effectively, enabling our algorithm to achieve a higher coverage ratio while reducing network energy consumption. Finally, we verified and compared 3D-DAOA with other algorithms to prove its reliability and accuracy. In future efforts, we will further study the algorithm’s actual test environment and target mobility.



---

*Source: 1018434-2019-10-07.xml*