# Multiagent Minimum Risk Path Intrusion Strategy with Computational Geometry

Authors: Jianguo Sun; Zining Yan; Sizhao Li
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

In wireless sensor networks (WSNs), inefficient coverage does affect the quality of service (QoS), which the minimum exposure path (MEP) is traditionally used to handle. But intelligent mobile devices are generally of limited computation capability, local storage, and energy. Present methods cannot meet the demand of multiple target intrusion, lacking the consideration of energy consumption. Based on the Voronoi diagram in computational geometry, this paper proposed an invasion strategy of minimum risk path (MRP) to such a question. MRP is the path considered both the exposure of the moving target and energy consumption. Federated learning is introduced to figure out how to find the MRP, expressed asCti,tj=fE,e. The value of Cti,tj can measure the success of an invasion. At the time when a single smart mobile device invades, horizontal federated learning is taken to partition the path feature, and a single target feature federated (SPF) algorithm is for calculating the MRP. Moreover, for multi smart mobile device invasion, it has imported the time variable. Vertical federated learning can partition the feature of multipath data, and the multi-target feature federated (MFF) algorithm is for solving the multipath MRP dynamically. The experimental results show that the SPF and MFF have the dominant advantage over traditional computational performance and time. It primarily applies the complex conditions of a massive amount of sensor nodes.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) composed of many sensors are widely used in many fields, such as building monitoring, intelligent transportation system (ITS), and enemy status report [1, 2]. What mainly affects network quality is coverage, especially the WSN barrier coverage problem [3]. According to the coverage classification, barrier coverage is one of the three coverage strategies to detect unauthorized intruding behaviour in monitored areas. Moreover, its quality measurement factors are mainly breaching, supporting, or exposure of the penetration path [4]. To reduce the risks of being found, invaders can make effective path planning and minimize the exposure [5] through intelligent algorithm.Minimum exposure path (MEP) [6] is a significant way that assesses the coverage effect of WSN to optimize the management of WSN. By finding out the MEP, the defender can estimate where the sensor network coverage is weak because the invader crossed the sensing field along this path is the most difficult to detect [7]. Therefore, this paper will study how to find an optimal invasion path from the perspective of intruders.Meguerdichian et al. [8] put forward the Voronoi diagram numerical solution combined with WSN and solved the MEP problem by the shortest path algorithm. Chechik et al. [9] defined the exposure by the number of nodes adjacent to the moving target, considering single-path connectivity to solve the MEP problem.In this paper, considering the perspective from invaders, the monitoring area is modelled by the Voronoi diagram that divided the field into undirected graphs that are a set of segmented linear components to limit the optimal searching space.Previous studies have shown that for intruders, the threat can be viewed as the probability of being detected by the sensor nodes when passing through the WSN, namely, the exposure. Exposure is the expected average ability of intrusion targets moved in the monitored area. Mathematically, the invader’s exposure time and sensor field intensity should be taken into account when calculating the exposure degree. Exposure can be formulated as a path integral when the sensor field intensity is accumulated along a path from the source point to the destination point during a time interval.According to the Cannikin Law [10], the reliability of the penetration path depends not only on its total exposure degree but also on the exposure of the discrete edges that make up the path. And when the invader passes through the monitoring area in some circumstances, it will be limited by time, distance, exposure, and energy consumption. Therefore, it is not accurate to find the path with the minimum total exposure degree. It is necessary to find an approach that is more in line with actual needs. The minimum risk path (MRP) is called to sum up the above paths in this paper.However, most of the researchers consider only one single intruder when solving the intrusion path. In actual situations, such as the Underwater Listening Network, a system collects underwater sounds and tracks and monitors the Navy’s passing ships and submarines. Underwater listeners are installed on the seafloor and act as sensor nodes. The moving target is an autonomous underwater vehicle (AUV) that needs to pass through the monitoring area. Multiple AUV intruders cross the sensing field simultaneously and cooperate with each other, as shown in Figure1. Invader 1 and invader 2 need to walk along two different paths to collect more information as far as possible, which will add to the complexity of path planning.Figure 1
Multitargets: AUVs.By contrast with the traditional method, federated learning allows multiple data owners to establish a shared model [11] with the protection of local data. It is conducive for updating the global data model dynamically to path planning. Yang et al. [12] introduced a federated learning framework of comprehension and security in 2019. Zhu and Jin [13] optimized the structure of neural network models by multiobjective evolutionary algorithms while minimizing communication costs and global model testing errors. Sodhro et al. [14] proposed a dynamic method of forward-center by adjusting the running time of the sensing and transmission process in the Internet of Things devices, which allocates resources with effectiveness and fairness.The horizontal federated learning applies to that the data features of participants overlap more, and the sample IDs are less. For a single intrusive target, the edges of the Voronoi diagram generated of WSN can be seen as a data set. The evaluation indicators of exposure and energy consumption can be regarded as a feature space. The intersection of the feature space is massive between the data sets. Hence, a data set can be divided into horizontal sections. It aggregates different data in the same feature space to train a model for the ideal path of the moving target. The above single intrusion target pathfinding algorithm combined with federated learning is called SPF.The vertical federated learning is suitable to the case of the ID of the training samples of participants overlap more and the data features less. Moving intrusion targets can be considered as data sets of this time. The feature space is the exposure and the energy consumption, which is the current position of the moving target location at the moment. Consequently, the different features of the common samples of multiple participants (intrusion targets) can be trained by vertical federated learning, which increased the feature dimensions of samples to build a multiobjective path planning model. The dynamic pathfinding algorithm for multiple intrusion targets based on federated learning is called MFF.In summary, the main contributions of this paper are as follows.(1)
Considering the influence of various factors on the path, propose the concept of a minimum risk path(2)
Innovatively combine federated learning with path planning to build an intrusion algorithm and find out the MRP(3)
The optimal path is worked out through a dynamically segmented solution of the generated model. Experimental results show that the SPF algorithm can reduce computational complexity and improve performance(4)
Based on the vertical federated learning, it established a dynamic path planning model and MFF algorithm for multiple intrusion targets that make full use of multiobjective programming characteristics. Augmenting additional requirements can work out diverse path combinationsThe rest part of this paper is as follows. The second part is the model building process. The detail of the proposed algorithm is described in the third section. In the fourth section, the experimental results are discussed. We formulate the evaluation indexes of the intrusion path planning algorithm in the fifth section. The final part is the summary of the whole paper.


## 2. Model Aggregation Based on Feature-Partitioned

### 2.1. Preliminaries

The sensing model determines the scope, and monitoring capability can be a usage of abstracting the sensing range of the same class nodes. In a bounded regionF, presumed n active sensor nodes s1,s2,⋯,sn would be deployed in predetermined locations. They can detect the target T appearing in any point within the sensing field. The detected sensing signal attenuates with the increasing Euclidean distance between the sensor node sii=1,⋯,n and the target T. The specific sensing model for detecting the target T signal can determine the exposure of the target which moves along the path.With the increasing transmission distance, the practically environmental noise interference and signal strength will attenuate. The detection probability of the node tapers as the distance grows between the moving target and the sensor node [15]. The detection capability of sensor nodes shows the uncertainty that attenuated disk perception model reflected.On this basis, Rai and Daruwala [16] studied the coverage problem under the attenuated disk perception model. The detection probability pu,si of si against the point u in region F can be expressed as in equation (1). In this paper, we selected the order type attenuated disk perception model.(1)pu,si=λ⋅du,si−K.Euclidean distance betweenu and si is dsi,u. λ and K are the positive parameters relevant to the sensing capability. λ depicts the energy factor transmitted or reflected by the target, and K represents the path attenuation exponent. In standard conditions, the value of K is in a range of constant between 2 and 5.In regionF, u is at any point, and sm is the sensor node with the shortest Euclidean distance to point u. The maximum-sensor intensity function ICF,u indicates the effective sensing measurement of sm to u. Function IC value of point P can be expressed as in (2) while the freely moving target P runs to the situation of u.(2)smin=sm∈Sdsm,u≤ds,u∀s∈S,ICF,u=pu,smin.t is the time variable. When the target P is moving at a constant speed v, (2) can be converted into(3)Eti,tj=v⋅∫titfIF,udt.Exposure is a quantitative expression of network coverage performance, and the definition varies with the changing of application environments. Binh et al. [17] reckoned that exposure is the ability of WSN to detect objects passing through the sensing region. Aravinth et al. [18] defined exposure as the probability of detecting a target in the sensing region.This paper endues two factors to explicate exposure: target moving time and induction intensity. It is noticeable that time accumulation affects induction intensity as the target passing through the sensor area. In the sensor regionF, targets moving along the path over a while, its exposure degree can be described as (4).(4)Eti,tj=∫titjIF,ududtdt.The threat model in this paper is a quantitative description of the optimal invasion path for intruders. The model can analyze the situation of the WSN, quantify the capability of the sensor nodes, and plan the invasion path of the adversary to the whole WSN reasonably. Specifically speaking, we firstly simulate the distribution of sensor network nodes to generate the network topology, and then, the intrusion path is planned according to the quantized threat data. A definition for the threat model is determined.Definition 1.
Given the overwhelming probability that an intruder can successfully penetrate the entire network if the value ofEti,tj is as small as possible.
The concept of the Voronoi diagram is derived from computational geometry. It divides a plane into multiple regions by a collection of points called generators [19]. Considering a convex Euclidean domain F and a set Q of points q0,q1,⋯,qn in F, Voronoi regions related to set Q are defined as (5) where dp,q is the Euclidean distance between p and q.
Equation (5) means that a point p∈F belongs to the Voronoi region Vqi, if the distance between p and qi is the shortest distance between p and any other point qj∈Q. The point qj∈Q is generating points or generators of the Voronoi partition.(5)Vqi=∩j≠ip∈Fdp,qi<dp,qj,∀qj∈Q,∀qi∈Q.
In this paper, specific partitions (Voronoi diagram) can be produced according to the position of generating points (sensor nodes) in mission space (WSN) which separates sensor regionF into multiple convex polygons. Each one contains a sensor node that its edge is called the Voronoi edge, and the intersection of Voronoi edge is the Voronoi vertex.
The characteristics of the Voronoi diagram played a key role. As a result, the minimum exposure path is right on theVoronoi edge precisely, under the maximum-sensor intensity. The Voronoi diagram or Voronoi partition that was generated via WSN consists of all the Voronoi cells of sensors.
Two types of methods can generate the Voronoi diagram. One is direct method that Voronoi diagram is generated from a set of points, such as half plane method, incremental construction method, divide and conquer method, plane scanning line method. Another is indirect which it takes the relationship between Voronoi diagram and the dual diagram of Delaunay triangle network. The point set is firstly subdivided to generate Delaunay triangle network and then to construct the Voronoi diagram.
If the corresponding Voronoi cells of sensorqi and qj have a same boundary, they become Delaunay neighbours and all the ones gathered to be an edge set of the Delaunay graph. Delaunay graph is dual to the Voronoi diagram, and consequently, one graph can be drawn from its dual counterpart. According to Table 1, triangulation generation method is at the lowest time efficiency, point-by-point insertion method the middle, and divide-and-conquer algorithm the highest. The point-by-point insertion algorithm that owned high time efficiency can implement simply, occupying less space in operation.Table 1
Comparison of Delaunay generation algorithms.
AlgorithmGeneral conditionWorst conditionLewis and RobinsonOnlognOn2Lee and SchachterOnlognOnlognDwyerOnloglognOnlognChewOnlognOnlognLawsonOn4/3On2Lee and SchachterOn3/2On2BowyerOn3/2On2WatsonOn3/2On2SloanOn5/4On2Green and SibsonOn3/2On2Brassel and ReifOn3/2On2McCullagh and RossOn3/2On2Improved point-by-point insertion method (IPI)OnlognOnlognThe first part of the table from top to bottom is divide-and-conquer algorithm, the second part is point-by-point insertion algorithm, and the third part is triangulation generation method. This paper considering time and space efficiency, with the improved point-by-point insertion method (IPI), constructs Delaunay triangulation. The Voronoi diagram is structured upon the Delaunay triangle. By contrast to the point-by-point insertion algorithm, it can diminish the number of relevant point judgment and the computational complexity by arranging points firstx and then y.The specific construction process is shown in Algorithm1.Algorithm 1: IPI algorithm.
Input: Vertex list (Vertices)Output: A list of determined triangles (Triangles)1: Initialise theVertices2: Create an index listindices3: Sort theindices bases on the x-coordinates of Vertices4: Get the super triangle (A super triangle means that the triangle contains all the points in the point set)5: Save the duper triangle to thetemp triangles list6: Push the super triangles intoTriangles list7: for Each sample point in theVertices list sorted by indices do8: Initialize theedge buffer9: for Each triangle intemp triangles do10:  Calculate the center and radius of the triangle11:  if The point is on the right side of the circumcircle then12:   This triangle is a Delaunay triangle, save it inTriangles13:   Remove the triangle fromtemp triangles list14:   Skip15:  else if The point is outside the circumcircle then16:   This triangle is uncertain17:   Skip18:  else The point lies on the inside of the circumcircle19:   This triangle is not a Delaunay triangle, add the three triangle edges toedge buffer20:   Remove the triangle fromtemp triangles list21:  end if22: end for23: Delete all repetitive edges inedge buffer24: Combine the edges in the edge buffer with the current point, and save these triangles intotemp triangles25: end for26: Combine thetemp triangles and Triangles27: Remove triangles associated with super triangles vertices fromTriangles listV(WSN) is specific Voronoi diagram generated upon sensor network node distribution. Vertex corresponding of V(WSN) has a one-to-one relationship to each Voronoi vertex of the general Voronoi diagram V(A). Vertexes in V(WSN) include the vertexes of V(A) and other points intersected the edges of V(A) and boundary of region F, as shown in Figure 2. The process of constructing V(WSN) is shown in Algorithm 2.Figure 2
Voronoi diagram of WSN.
(a)
V(A)(b)
V(WSN)Algorithm 2: Construction of V(WSN).
Input: Vertex list (Vertices), Region FOutput:V(WSN)1: Initialize theVertices2: Create an edge listVoronoi edge3: Use IPI algorithm to construct Delaunay triangular network based on Vertices4: Number the discrete points and formed them into triangles. Then record three discrete points composed of each triangle5: Calculate the center of each circumcircle of triangle and record it6: for Thetriangle list do Find adjacent triangles TriA, TriB, and TriC that share side with the current triangle tempTri7: if Three adjacent triangles are found then8:  Connect the outer center ofTriA, TriB, and TriC to the outer center of tempTri. Put the connected edge into Voronoi edge list9: elseThree adjacent triangles are not found10:  Find the outermost midperpendicular ray and put it intoVoronoi edge list11: end if12: end for13: Calculate the point of intersection betweenVoronoi edge and region F14: Connectintersection point according to F (acquire line of intersection)15:V(WSN) is constructed by Voronoi edge and line of intersection


### 2.2. Parameter Calculation

The network flow is a specific flow solution that is closely related to linear programming [20]. This paper presents a new idea that edges have been defined as Voronoi edges and the flow as the moving target passed by this edge. The capacity can be considered as the maximum number of moving targets that each Voronoi edge can hold. Each node (not a source point or a sink point) is like an analogy to a Voronoi vertex, while the capacity is not limited.Definition 2.
The capacity networkD=V,A (V is the vertex of an undirected graph and A is the arc), and each arc Vi,Vj endues the transmission cost per unit moving bij≥0, denoted as(6)D=V,A,B,bij∈B.
The maximum flow from source to sink can be found in the cost networkD, and the total transfer cost of the stream is at a minimum.Definition 3.
If the moving target velocity was a constantv, the time increment dt would have a significant linear correlation between the unit length ds defined as(7)ds=v⋅dt.The energy consumption is defined below.Definition 4.
Supposingq is the energy consumption of unit length while target moving, the time variable is t and the time interval from Vi to Vj is ti,tj. In the sensor region F, the energy consumption of the target which moves along the path rt at a constant speed v, is defined as(8)eti,tj=∫titjvqdt.
The analytic discrete method can work out this problem, using a variational method to obtain the analytical solution to the risk optimization problem. Such a method simplifies original question to a set of differential equations about the optimal trajectory coordinates. How the trajectory is defined will make the complexity of the system.
Presuming the coordinate ofVoronoi vertexVk is xVk,yVk, and tp is the path crossing time. The length of the edge Vi,Vj is expressed as lViVj.
The travel time along the edgeVi,Vj of the moving target is indicated by tViVj. IViVj is the induction intensity of the nearest sensor nodes s1s2 when the target moves along the edge. dsi,Vk is the distance from the sensor node s1s2 to the point Vk, and θsi,ViVj is the angle of ∠Vis1Vj. The coordinates of s1 is x1,y1; hence, tViVj can be expressed as(9)tViVj=lViVjv=xVj−xVi2+yVj−yVi2v.
Analyzing the cost solution, suppose a sensor of Voronoi cells located in the coordinate system origin point, using the polar coordinate system. The relationship between Cartesian coordinatex, y, polar radius ρ, and polar angle Ψ is as in (10).(10)xs=ρscosΨs,ys=ρssinΨs.
For pointsVi and Vj, polar radius ρ and angle θ can be expressed as in (11) and (12)(11)ρi=xi2+yi2,ρj=xj2+yj2,(12)θ=arccosxixj+yiyjρiρj.
To derive the formula for the exposure index, it calculates the cumulative exposure of a moving target affected bys1 from Vi to Vj. λ is the induction parameter determined by the sensor node hardware, and K is the distance impact factor with its value in common between 2 and 5. It has presumed λ=1,K=2 and induction intensity expressed as in (13)(13)v⋅∫tVatVbd−2dpdtdt=∫VaVbd−2dp=∫xVaxVb1+y′xx−ai2+y−bi2dx=arctanyVb−bi/xVb−ai−arctanyVa−bi/xVa−ai⋅lVaVbxVa−aiyVb−bi−xVb−aiyVa−bi.
VectorxVk−x1,yVk−y1 can be indicated by ds,Vk, and the angle between vector ds,Vi and ds,Vj can be indicated by θs,ViVj that meets the condition 0≤θs,ViVj≤π. So, it can be simplified to (14)(14)v⋅∫tVitVjd−2dsdtdt=θs,ViVjsinθs,ViVj⋅lViVjdi,Vi⋅di,Vj.
The induction intensity is transformed into (15). The exposure can be calculated by (16), and the target moving total exposure Ep is (17).(15)Is,ViVj=θs,ViVjsinθs,ViVj⋅ds,Vi−1ds,Vj−1,(16)Es,ViVj=Is,ViVj·lViVj,(17)Ep=∑i=cj=fEViVj.


## 2.1. Preliminaries

The sensing model determines the scope, and monitoring capability can be a usage of abstracting the sensing range of the same class nodes. In a bounded regionF, presumed n active sensor nodes s1,s2,⋯,sn would be deployed in predetermined locations. They can detect the target T appearing in any point within the sensing field. The detected sensing signal attenuates with the increasing Euclidean distance between the sensor node sii=1,⋯,n and the target T. The specific sensing model for detecting the target T signal can determine the exposure of the target which moves along the path.With the increasing transmission distance, the practically environmental noise interference and signal strength will attenuate. The detection probability of the node tapers as the distance grows between the moving target and the sensor node [15]. The detection capability of sensor nodes shows the uncertainty that attenuated disk perception model reflected.On this basis, Rai and Daruwala [16] studied the coverage problem under the attenuated disk perception model. The detection probability pu,si of si against the point u in region F can be expressed as in equation (1). In this paper, we selected the order type attenuated disk perception model.(1)pu,si=λ⋅du,si−K.Euclidean distance betweenu and si is dsi,u. λ and K are the positive parameters relevant to the sensing capability. λ depicts the energy factor transmitted or reflected by the target, and K represents the path attenuation exponent. In standard conditions, the value of K is in a range of constant between 2 and 5.In regionF, u is at any point, and sm is the sensor node with the shortest Euclidean distance to point u. The maximum-sensor intensity function ICF,u indicates the effective sensing measurement of sm to u. Function IC value of point P can be expressed as in (2) while the freely moving target P runs to the situation of u.(2)smin=sm∈Sdsm,u≤ds,u∀s∈S,ICF,u=pu,smin.t is the time variable. When the target P is moving at a constant speed v, (2) can be converted into(3)Eti,tj=v⋅∫titfIF,udt.Exposure is a quantitative expression of network coverage performance, and the definition varies with the changing of application environments. Binh et al. [17] reckoned that exposure is the ability of WSN to detect objects passing through the sensing region. Aravinth et al. [18] defined exposure as the probability of detecting a target in the sensing region.This paper endues two factors to explicate exposure: target moving time and induction intensity. It is noticeable that time accumulation affects induction intensity as the target passing through the sensor area. In the sensor regionF, targets moving along the path over a while, its exposure degree can be described as (4).(4)Eti,tj=∫titjIF,ududtdt.The threat model in this paper is a quantitative description of the optimal invasion path for intruders. The model can analyze the situation of the WSN, quantify the capability of the sensor nodes, and plan the invasion path of the adversary to the whole WSN reasonably. Specifically speaking, we firstly simulate the distribution of sensor network nodes to generate the network topology, and then, the intrusion path is planned according to the quantized threat data. A definition for the threat model is determined.Definition 1.
Given the overwhelming probability that an intruder can successfully penetrate the entire network if the value ofEti,tj is as small as possible.
The concept of the Voronoi diagram is derived from computational geometry. It divides a plane into multiple regions by a collection of points called generators [19]. Considering a convex Euclidean domain F and a set Q of points q0,q1,⋯,qn in F, Voronoi regions related to set Q are defined as (5) where dp,q is the Euclidean distance between p and q.
Equation (5) means that a point p∈F belongs to the Voronoi region Vqi, if the distance between p and qi is the shortest distance between p and any other point qj∈Q. The point qj∈Q is generating points or generators of the Voronoi partition.(5)Vqi=∩j≠ip∈Fdp,qi<dp,qj,∀qj∈Q,∀qi∈Q.
In this paper, specific partitions (Voronoi diagram) can be produced according to the position of generating points (sensor nodes) in mission space (WSN) which separates sensor regionF into multiple convex polygons. Each one contains a sensor node that its edge is called the Voronoi edge, and the intersection of Voronoi edge is the Voronoi vertex.
The characteristics of the Voronoi diagram played a key role. As a result, the minimum exposure path is right on theVoronoi edge precisely, under the maximum-sensor intensity. The Voronoi diagram or Voronoi partition that was generated via WSN consists of all the Voronoi cells of sensors.
Two types of methods can generate the Voronoi diagram. One is direct method that Voronoi diagram is generated from a set of points, such as half plane method, incremental construction method, divide and conquer method, plane scanning line method. Another is indirect which it takes the relationship between Voronoi diagram and the dual diagram of Delaunay triangle network. The point set is firstly subdivided to generate Delaunay triangle network and then to construct the Voronoi diagram.
If the corresponding Voronoi cells of sensorqi and qj have a same boundary, they become Delaunay neighbours and all the ones gathered to be an edge set of the Delaunay graph. Delaunay graph is dual to the Voronoi diagram, and consequently, one graph can be drawn from its dual counterpart. According to Table 1, triangulation generation method is at the lowest time efficiency, point-by-point insertion method the middle, and divide-and-conquer algorithm the highest. The point-by-point insertion algorithm that owned high time efficiency can implement simply, occupying less space in operation.Table 1
Comparison of Delaunay generation algorithms.
AlgorithmGeneral conditionWorst conditionLewis and RobinsonOnlognOn2Lee and SchachterOnlognOnlognDwyerOnloglognOnlognChewOnlognOnlognLawsonOn4/3On2Lee and SchachterOn3/2On2BowyerOn3/2On2WatsonOn3/2On2SloanOn5/4On2Green and SibsonOn3/2On2Brassel and ReifOn3/2On2McCullagh and RossOn3/2On2Improved point-by-point insertion method (IPI)OnlognOnlognThe first part of the table from top to bottom is divide-and-conquer algorithm, the second part is point-by-point insertion algorithm, and the third part is triangulation generation method. This paper considering time and space efficiency, with the improved point-by-point insertion method (IPI), constructs Delaunay triangulation. The Voronoi diagram is structured upon the Delaunay triangle. By contrast to the point-by-point insertion algorithm, it can diminish the number of relevant point judgment and the computational complexity by arranging points firstx and then y.The specific construction process is shown in Algorithm1.Algorithm 1: IPI algorithm.
Input: Vertex list (Vertices)Output: A list of determined triangles (Triangles)1: Initialise theVertices2: Create an index listindices3: Sort theindices bases on the x-coordinates of Vertices4: Get the super triangle (A super triangle means that the triangle contains all the points in the point set)5: Save the duper triangle to thetemp triangles list6: Push the super triangles intoTriangles list7: for Each sample point in theVertices list sorted by indices do8: Initialize theedge buffer9: for Each triangle intemp triangles do10:  Calculate the center and radius of the triangle11:  if The point is on the right side of the circumcircle then12:   This triangle is a Delaunay triangle, save it inTriangles13:   Remove the triangle fromtemp triangles list14:   Skip15:  else if The point is outside the circumcircle then16:   This triangle is uncertain17:   Skip18:  else The point lies on the inside of the circumcircle19:   This triangle is not a Delaunay triangle, add the three triangle edges toedge buffer20:   Remove the triangle fromtemp triangles list21:  end if22: end for23: Delete all repetitive edges inedge buffer24: Combine the edges in the edge buffer with the current point, and save these triangles intotemp triangles25: end for26: Combine thetemp triangles and Triangles27: Remove triangles associated with super triangles vertices fromTriangles listV(WSN) is specific Voronoi diagram generated upon sensor network node distribution. Vertex corresponding of V(WSN) has a one-to-one relationship to each Voronoi vertex of the general Voronoi diagram V(A). Vertexes in V(WSN) include the vertexes of V(A) and other points intersected the edges of V(A) and boundary of region F, as shown in Figure 2. The process of constructing V(WSN) is shown in Algorithm 2.Figure 2
Voronoi diagram of WSN.
(a)
V(A)(b)
V(WSN)Algorithm 2: Construction of V(WSN).
Input: Vertex list (Vertices), Region FOutput:V(WSN)1: Initialize theVertices2: Create an edge listVoronoi edge3: Use IPI algorithm to construct Delaunay triangular network based on Vertices4: Number the discrete points and formed them into triangles. Then record three discrete points composed of each triangle5: Calculate the center of each circumcircle of triangle and record it6: for Thetriangle list do Find adjacent triangles TriA, TriB, and TriC that share side with the current triangle tempTri7: if Three adjacent triangles are found then8:  Connect the outer center ofTriA, TriB, and TriC to the outer center of tempTri. Put the connected edge into Voronoi edge list9: elseThree adjacent triangles are not found10:  Find the outermost midperpendicular ray and put it intoVoronoi edge list11: end if12: end for13: Calculate the point of intersection betweenVoronoi edge and region F14: Connectintersection point according to F (acquire line of intersection)15:V(WSN) is constructed by Voronoi edge and line of intersection


## 2.2. Parameter Calculation

The network flow is a specific flow solution that is closely related to linear programming [20]. This paper presents a new idea that edges have been defined as Voronoi edges and the flow as the moving target passed by this edge. The capacity can be considered as the maximum number of moving targets that each Voronoi edge can hold. Each node (not a source point or a sink point) is like an analogy to a Voronoi vertex, while the capacity is not limited.Definition 2.
The capacity networkD=V,A (V is the vertex of an undirected graph and A is the arc), and each arc Vi,Vj endues the transmission cost per unit moving bij≥0, denoted as(6)D=V,A,B,bij∈B.
The maximum flow from source to sink can be found in the cost networkD, and the total transfer cost of the stream is at a minimum.Definition 3.
If the moving target velocity was a constantv, the time increment dt would have a significant linear correlation between the unit length ds defined as(7)ds=v⋅dt.The energy consumption is defined below.Definition 4.
Supposingq is the energy consumption of unit length while target moving, the time variable is t and the time interval from Vi to Vj is ti,tj. In the sensor region F, the energy consumption of the target which moves along the path rt at a constant speed v, is defined as(8)eti,tj=∫titjvqdt.
The analytic discrete method can work out this problem, using a variational method to obtain the analytical solution to the risk optimization problem. Such a method simplifies original question to a set of differential equations about the optimal trajectory coordinates. How the trajectory is defined will make the complexity of the system.
Presuming the coordinate ofVoronoi vertexVk is xVk,yVk, and tp is the path crossing time. The length of the edge Vi,Vj is expressed as lViVj.
The travel time along the edgeVi,Vj of the moving target is indicated by tViVj. IViVj is the induction intensity of the nearest sensor nodes s1s2 when the target moves along the edge. dsi,Vk is the distance from the sensor node s1s2 to the point Vk, and θsi,ViVj is the angle of ∠Vis1Vj. The coordinates of s1 is x1,y1; hence, tViVj can be expressed as(9)tViVj=lViVjv=xVj−xVi2+yVj−yVi2v.
Analyzing the cost solution, suppose a sensor of Voronoi cells located in the coordinate system origin point, using the polar coordinate system. The relationship between Cartesian coordinatex, y, polar radius ρ, and polar angle Ψ is as in (10).(10)xs=ρscosΨs,ys=ρssinΨs.
For pointsVi and Vj, polar radius ρ and angle θ can be expressed as in (11) and (12)(11)ρi=xi2+yi2,ρj=xj2+yj2,(12)θ=arccosxixj+yiyjρiρj.
To derive the formula for the exposure index, it calculates the cumulative exposure of a moving target affected bys1 from Vi to Vj. λ is the induction parameter determined by the sensor node hardware, and K is the distance impact factor with its value in common between 2 and 5. It has presumed λ=1,K=2 and induction intensity expressed as in (13)(13)v⋅∫tVatVbd−2dpdtdt=∫VaVbd−2dp=∫xVaxVb1+y′xx−ai2+y−bi2dx=arctanyVb−bi/xVb−ai−arctanyVa−bi/xVa−ai⋅lVaVbxVa−aiyVb−bi−xVb−aiyVa−bi.
VectorxVk−x1,yVk−y1 can be indicated by ds,Vk, and the angle between vector ds,Vi and ds,Vj can be indicated by θs,ViVj that meets the condition 0≤θs,ViVj≤π. So, it can be simplified to (14)(14)v⋅∫tVitVjd−2dsdtdt=θs,ViVjsinθs,ViVj⋅lViVjdi,Vi⋅di,Vj.
The induction intensity is transformed into (15). The exposure can be calculated by (16), and the target moving total exposure Ep is (17).(15)Is,ViVj=θs,ViVjsinθs,ViVj⋅ds,Vi−1ds,Vj−1,(16)Es,ViVj=Is,ViVj·lViVj,(17)Ep=∑i=cj=fEViVj.


## 3. Find the MRP Using Dynamic Programming and Federated Leaning

For the intrusion path selected, the primary goal is to avoid being detected by WSN. It is essential of thinking about how to select a path according to topology of WSN that meets the demands of the actual path seeking process. Therefore, the network topology data preprocessing is a very critical step. We can learn from federated learning, divide, and conquer.The main idea of federated learning is to build machine-learning models based on data sets distributed over multiple devices [21]. Hao et al. [22] proposed an efficient scheme to solve sensitive data-driven industrial scenarios, and Lu et al. [23] formulate the data-sharing problem into a machine-learning problem via incorporating privacy-preserved federated learning. WSN can generate a significant amount of data [24]. According to the federated learning framework, we can perform data preprocessing on the WSN network topology. It should be noted that the research object of this paper is the static network, only using federated learning methodology, and there is no actual learning process.Compared to the traditional method, federated learning is beneficial for dynamically updating the global data model on path planning. Thus, federated learning can deal with the MRP problem.


### 3.1. Single Mobile Device

#### 3.1.1. The Calculation Model Established by Feature-Partitioned

Let matrixDi denote data onto each Voronoi edge. Each row of the matrix represents a sample, and every column marks a feature. The feature space X includes exposure (E) and energy consumption (e), defining I the sample ID space (Voronoi edge number). The feature FE and sample Ids SI constitute the entire training data set SI,FE.Horizontal federated learning, also sample-based federated learning, was introduced in that data sets shared the same space in feature but distinct space in samples [25]. Horizontal federated learning is summarized as(18)FEi=FEj,SIi≠SIj,∀Di,Dj,i≠j.The intersection of feature space is enormous between the data set ofVoronoi edges. Then, the data set can be horizontally segmented, and varied data onto the same feature space can be aggregated. Consequently, it trains the model to solve a selection of the optimal path while the target is moving.Step 1.
Participants compute exposure locally with encryption and send results to the server.Step 2.
The server performs secure aggregation without learning information about any participant and calculates the average value of exposure.Step 3.
The server sends back the aggregated results to participants.Step 4.
Participants update their respective model with the decrypted results.The primary goal of intrusion path is avoiding detection by WSN and then considering over the influence of energy consumption. In Step 2, the method of calculating the average exposure value of the entire network is as shown in (19), and lall is the length of path.(19)E′=E1+E2+⋯+Enlall.Therefore, the predicted exposure valueEpreVi,Vj from point Vi to point Vj can be expressed as (20)(20)EpreViVj=dViVj⋅E′.Because the length is the fundamental dimension of quantity, we can describe them by lengthL. According to (15) and (16), E is dimensionless parameter because the dimension of I is 1/L and the dimension of lVi,Vj is L. So, the dimension of Epre is L. The dimension of e can be computed according to (8) in the same way. L is the dimension of e, too.The time complexity of Voronoi graph generation wasOnlogn [26]. With Voronoi diagram 3n−6 edges, accordingly it takes no more than On to calculate the exposure of all Voronoi edges. Based on dimensional analysis, the judgment function Cti,tj can be defined as shown in (21). The value of Cti,tj can measure the successfulness of an invasion.(21)Cti,tj=∫titjE′dpdtdt+∫titjqdpdtdt.


#### 3.1.2. The Flow of Algorithm and the Procedure of Realization

In actual path planning, combinations of edges that are possibly feasible flows can be various. Hence, it has to dynamically update the priority to the selected edges keeping the searching direction under control in planning an optimal path. Furthermore, the cost is optimal for each extended path. The valuation function of moving target from the starting nodes via current node Xx,y to the end node f can be defined.Definition 5.
GX is the total exposure value from the start node to the current node, which can be obtained by adding up the weights of any neighboring edge of the path that traveled. HX is the heuristic estimated cost function (included exposure and energy consume) which is only as a judgment, not as a part of cost calculation. The total cost value FX can be expressed as(22)FX=GX+HX.
Considering an ideal condition that the target in motion is supposed to be increasingly closer towards the destination, according to the feature-partitioned of federated learning,HX could be accordingly expressed as(23)HX=E′⋅dY,f+etX,tY.
Y is the antecedent node of X. dY,f is the Euclidean distance from Y to the end node s, and E′∗dY,f expressed the exposure estimation from Y to f.
Define an empty table namedNotVis and another BeenVis: nodes that have not been visited (need to be examined) are stored in the NotVis table, and nodes that have been visited are stored in the BeenVis table. The single intrusion target pathfinding algorithm combined with federated learning (SPF algorithm) is as Algorithm 3.Algorithm 3: SPF algorithm.
Input:Graph V(WSN); s; fOutput:optimal path1:NotVis=s; BeenVis=[];2: while TheNotVis table is not empty do3: SelectVi with the lowest total proxy value F from NotVis. Then delete Vi from NotVis and insert Vi into BeenVis.4: ifVi is the end node f then5:  Return path6: else7:  Extend nodeVi8:  for Each adjacent nodeVj of Vi do9:   Calculate the exposureEViVj.10:   ifVj is not in neither the NotVis or BeenVis table then11:    CalculateF(Vj)12:    InsertVj into the NotVis table. And add it a pointer variable pointing to node Vi.13:   else ifVj is in the NotVis table then14:    ifF(Vj) is less that the estimated value F′Vj in NotVis table then15:     UpdateF′VjF′Vj=FVj.16:     Change the node pointer in theNotVis table to point to the current node Vi17:    else18:     ifF(Vj) is less than the estimates value F′Vj in BeenVis table then19:      UpdateF′VjF′Vj=FVj.20:      DeleteVj from BeenVis table and insert Vj into NotVis table21:     end if22:    end if23:   end if24:   InsertVi into BeenVis table25:  end for26: end if27: end while28: Fromf backtrack to s. Return path.The SPF algorithm can output an optimal path by inputting theV(WSN) generated by the Voronoi diagram that contains the connected edges and the position coordinates of each node and the point identifier from the source point s to final point f.


### 3.2. Multiple Mobile Devices

#### 3.2.1. The Calculation Model Established by Feature-Partitioned

It is sometimes a practical demand to transfer multiple moving targets over a time interval. The vertical federated learning is suitable for the ID of the training samples of participants overlap more and the data features less. The moving target is deemed to be a sample setSI. The feature space FE is formed into the moving target position, the moment of the current position, and exposure degree. Vertically federated learning is a process aggregating different features above, in which a model can be built with data from moving targets in cooperation. Under such assumption, (24) can be got.(24)FEi≠FEj,SIi=SIj,∀Di,Dj,i≠j.Training the model can solve the multioptimal path of the moving target. Specific steps are as follows.Step 1.
Participants locally compute exposure and time and send masked results to the server.Step 2.
The server performs secure aggregation without learning information about any participant.Step 3.
The server sends back the aggregated results to participants.Step 4.
Participants update their respective model with the decrypted results.Whereas varied positions of moving targetA as time running would decide the direction of moving target B, time variable was imported over multiobjective path judgment. The probability of being detected by the sensor would be increasing (like a traffic problem [27]) as two moving targets on the same Voronoi edge. The presumption is that when target A is at Voronoi edgeViVj, if target B passing by edge ViVj, the heuristic estimated cost HB of target B would be H′B.(25)H′B=k⋅HBk>1.The Underwater Sensor Network is a system that collects underwater sounds and tracks and monitors the Navy’s passing ships and submarines. The underwater acoustic detectors (UADs) are installed on the seafloor and act as sensor nodes. The moving target is an autonomous underwater vehicle (AUV) that needs to pass through the monitoring area. For more information gathering and security reasons, it is a method to keep the AUV from going the same path as much as possible by adjusting thek value in (25).


#### 3.2.2. The Algorithm Flow and the Procedure of Realization

When multiple intrusion targets need to be transmitted, a time-variable is introduced in this paper to conduct dynamic pathfinding of multiple intrusion targets based on federated learning feature (MFF). Assuming that multiple moving targetsM1,M2,⋯,Mn start from s every time interval T, the HX value is updated according to the formula (25) and the location of the moving target at different times. Based on the SPF algorithm, we need to create some new data structures to store variables in the MFF algorithm, as shown in Table 2.Table 2
Comparison of Delaunay generation algorithms.
DetCost_LinesThe exposure value of eachVoronoi edgeDetTime_LinesThe time required for the moving target to move along eachVoronoi edge (ViVj)Path_CostThe respective cost and total cost of all departing moving targets at a given timePath_FCostThe respective projected cost values of all departing moving targets at a given timePath_Record _CurrentPointThe name of the current pointPath_Record _PreviouPointThe previous node nameThe specific algorithm flow is as Algorithm4. By contrast to the SPF algorithm for a single intrusion target, the MFF algorithm sets a time variable to record the positions of distinct targets moving every period, which position relationship can update data onto the model.Algorithm 4: MFF algorithm.
Input:Graph V(WSN)Output:optimal path1:NotVis=[s]; BeenVis=[]2: while TheNotVis table is not empty do3: Select the path with the lowest total proxy valueF from NotVis. And record the corresponding moving target serial number i.4: if All moving targets are the end nodef then5:  Returnpath6: end if7: Update DetCost_line according to (25) and path8: Sort Path_Time_CurrentPoint in ascending order, and record the moving targer serial number respectively. (Determine the moving targetMj that reaches the next Voronoi vertex first)9: for All moving targets do10:  ifMi reaches the end point then11:   Calculate path ofMj12:  elseBreak;13:  end if14: end for15: Make path prediction forMi which has minimum value of Path_Time_CurrentPoint by SPF algorithm16: Update Path_Record_CurrentPoint17: Update Path_Time_CurrentPoint18: Goto line 719: end while


## 3.1. Single Mobile Device

### 3.1.1. The Calculation Model Established by Feature-Partitioned

Let matrixDi denote data onto each Voronoi edge. Each row of the matrix represents a sample, and every column marks a feature. The feature space X includes exposure (E) and energy consumption (e), defining I the sample ID space (Voronoi edge number). The feature FE and sample Ids SI constitute the entire training data set SI,FE.Horizontal federated learning, also sample-based federated learning, was introduced in that data sets shared the same space in feature but distinct space in samples [25]. Horizontal federated learning is summarized as(18)FEi=FEj,SIi≠SIj,∀Di,Dj,i≠j.The intersection of feature space is enormous between the data set ofVoronoi edges. Then, the data set can be horizontally segmented, and varied data onto the same feature space can be aggregated. Consequently, it trains the model to solve a selection of the optimal path while the target is moving.Step 1.
Participants compute exposure locally with encryption and send results to the server.Step 2.
The server performs secure aggregation without learning information about any participant and calculates the average value of exposure.Step 3.
The server sends back the aggregated results to participants.Step 4.
Participants update their respective model with the decrypted results.The primary goal of intrusion path is avoiding detection by WSN and then considering over the influence of energy consumption. In Step 2, the method of calculating the average exposure value of the entire network is as shown in (19), and lall is the length of path.(19)E′=E1+E2+⋯+Enlall.Therefore, the predicted exposure valueEpreVi,Vj from point Vi to point Vj can be expressed as (20)(20)EpreViVj=dViVj⋅E′.Because the length is the fundamental dimension of quantity, we can describe them by lengthL. According to (15) and (16), E is dimensionless parameter because the dimension of I is 1/L and the dimension of lVi,Vj is L. So, the dimension of Epre is L. The dimension of e can be computed according to (8) in the same way. L is the dimension of e, too.The time complexity of Voronoi graph generation wasOnlogn [26]. With Voronoi diagram 3n−6 edges, accordingly it takes no more than On to calculate the exposure of all Voronoi edges. Based on dimensional analysis, the judgment function Cti,tj can be defined as shown in (21). The value of Cti,tj can measure the successfulness of an invasion.(21)Cti,tj=∫titjE′dpdtdt+∫titjqdpdtdt.


### 3.1.2. The Flow of Algorithm and the Procedure of Realization

In actual path planning, combinations of edges that are possibly feasible flows can be various. Hence, it has to dynamically update the priority to the selected edges keeping the searching direction under control in planning an optimal path. Furthermore, the cost is optimal for each extended path. The valuation function of moving target from the starting nodes via current node Xx,y to the end node f can be defined.Definition 5.
GX is the total exposure value from the start node to the current node, which can be obtained by adding up the weights of any neighboring edge of the path that traveled. HX is the heuristic estimated cost function (included exposure and energy consume) which is only as a judgment, not as a part of cost calculation. The total cost value FX can be expressed as(22)FX=GX+HX.
Considering an ideal condition that the target in motion is supposed to be increasingly closer towards the destination, according to the feature-partitioned of federated learning,HX could be accordingly expressed as(23)HX=E′⋅dY,f+etX,tY.
Y is the antecedent node of X. dY,f is the Euclidean distance from Y to the end node s, and E′∗dY,f expressed the exposure estimation from Y to f.
Define an empty table namedNotVis and another BeenVis: nodes that have not been visited (need to be examined) are stored in the NotVis table, and nodes that have been visited are stored in the BeenVis table. The single intrusion target pathfinding algorithm combined with federated learning (SPF algorithm) is as Algorithm 3.Algorithm 3: SPF algorithm.
Input:Graph V(WSN); s; fOutput:optimal path1:NotVis=s; BeenVis=[];2: while TheNotVis table is not empty do3: SelectVi with the lowest total proxy value F from NotVis. Then delete Vi from NotVis and insert Vi into BeenVis.4: ifVi is the end node f then5:  Return path6: else7:  Extend nodeVi8:  for Each adjacent nodeVj of Vi do9:   Calculate the exposureEViVj.10:   ifVj is not in neither the NotVis or BeenVis table then11:    CalculateF(Vj)12:    InsertVj into the NotVis table. And add it a pointer variable pointing to node Vi.13:   else ifVj is in the NotVis table then14:    ifF(Vj) is less that the estimated value F′Vj in NotVis table then15:     UpdateF′VjF′Vj=FVj.16:     Change the node pointer in theNotVis table to point to the current node Vi17:    else18:     ifF(Vj) is less than the estimates value F′Vj in BeenVis table then19:      UpdateF′VjF′Vj=FVj.20:      DeleteVj from BeenVis table and insert Vj into NotVis table21:     end if22:    end if23:   end if24:   InsertVi into BeenVis table25:  end for26: end if27: end while28: Fromf backtrack to s. Return path.The SPF algorithm can output an optimal path by inputting theV(WSN) generated by the Voronoi diagram that contains the connected edges and the position coordinates of each node and the point identifier from the source point s to final point f.


## 3.1.1. The Calculation Model Established by Feature-Partitioned

Let matrixDi denote data onto each Voronoi edge. Each row of the matrix represents a sample, and every column marks a feature. The feature space X includes exposure (E) and energy consumption (e), defining I the sample ID space (Voronoi edge number). The feature FE and sample Ids SI constitute the entire training data set SI,FE.Horizontal federated learning, also sample-based federated learning, was introduced in that data sets shared the same space in feature but distinct space in samples [25]. Horizontal federated learning is summarized as(18)FEi=FEj,SIi≠SIj,∀Di,Dj,i≠j.The intersection of feature space is enormous between the data set ofVoronoi edges. Then, the data set can be horizontally segmented, and varied data onto the same feature space can be aggregated. Consequently, it trains the model to solve a selection of the optimal path while the target is moving.Step 1.
Participants compute exposure locally with encryption and send results to the server.Step 2.
The server performs secure aggregation without learning information about any participant and calculates the average value of exposure.Step 3.
The server sends back the aggregated results to participants.Step 4.
Participants update their respective model with the decrypted results.The primary goal of intrusion path is avoiding detection by WSN and then considering over the influence of energy consumption. In Step 2, the method of calculating the average exposure value of the entire network is as shown in (19), and lall is the length of path.(19)E′=E1+E2+⋯+Enlall.Therefore, the predicted exposure valueEpreVi,Vj from point Vi to point Vj can be expressed as (20)(20)EpreViVj=dViVj⋅E′.Because the length is the fundamental dimension of quantity, we can describe them by lengthL. According to (15) and (16), E is dimensionless parameter because the dimension of I is 1/L and the dimension of lVi,Vj is L. So, the dimension of Epre is L. The dimension of e can be computed according to (8) in the same way. L is the dimension of e, too.The time complexity of Voronoi graph generation wasOnlogn [26]. With Voronoi diagram 3n−6 edges, accordingly it takes no more than On to calculate the exposure of all Voronoi edges. Based on dimensional analysis, the judgment function Cti,tj can be defined as shown in (21). The value of Cti,tj can measure the successfulness of an invasion.(21)Cti,tj=∫titjE′dpdtdt+∫titjqdpdtdt.


## 3.1.2. The Flow of Algorithm and the Procedure of Realization

In actual path planning, combinations of edges that are possibly feasible flows can be various. Hence, it has to dynamically update the priority to the selected edges keeping the searching direction under control in planning an optimal path. Furthermore, the cost is optimal for each extended path. The valuation function of moving target from the starting nodes via current node Xx,y to the end node f can be defined.Definition 5.
GX is the total exposure value from the start node to the current node, which can be obtained by adding up the weights of any neighboring edge of the path that traveled. HX is the heuristic estimated cost function (included exposure and energy consume) which is only as a judgment, not as a part of cost calculation. The total cost value FX can be expressed as(22)FX=GX+HX.
Considering an ideal condition that the target in motion is supposed to be increasingly closer towards the destination, according to the feature-partitioned of federated learning,HX could be accordingly expressed as(23)HX=E′⋅dY,f+etX,tY.
Y is the antecedent node of X. dY,f is the Euclidean distance from Y to the end node s, and E′∗dY,f expressed the exposure estimation from Y to f.
Define an empty table namedNotVis and another BeenVis: nodes that have not been visited (need to be examined) are stored in the NotVis table, and nodes that have been visited are stored in the BeenVis table. The single intrusion target pathfinding algorithm combined with federated learning (SPF algorithm) is as Algorithm 3.Algorithm 3: SPF algorithm.
Input:Graph V(WSN); s; fOutput:optimal path1:NotVis=s; BeenVis=[];2: while TheNotVis table is not empty do3: SelectVi with the lowest total proxy value F from NotVis. Then delete Vi from NotVis and insert Vi into BeenVis.4: ifVi is the end node f then5:  Return path6: else7:  Extend nodeVi8:  for Each adjacent nodeVj of Vi do9:   Calculate the exposureEViVj.10:   ifVj is not in neither the NotVis or BeenVis table then11:    CalculateF(Vj)12:    InsertVj into the NotVis table. And add it a pointer variable pointing to node Vi.13:   else ifVj is in the NotVis table then14:    ifF(Vj) is less that the estimated value F′Vj in NotVis table then15:     UpdateF′VjF′Vj=FVj.16:     Change the node pointer in theNotVis table to point to the current node Vi17:    else18:     ifF(Vj) is less than the estimates value F′Vj in BeenVis table then19:      UpdateF′VjF′Vj=FVj.20:      DeleteVj from BeenVis table and insert Vj into NotVis table21:     end if22:    end if23:   end if24:   InsertVi into BeenVis table25:  end for26: end if27: end while28: Fromf backtrack to s. Return path.The SPF algorithm can output an optimal path by inputting theV(WSN) generated by the Voronoi diagram that contains the connected edges and the position coordinates of each node and the point identifier from the source point s to final point f.


## 3.2. Multiple Mobile Devices

### 3.2.1. The Calculation Model Established by Feature-Partitioned

It is sometimes a practical demand to transfer multiple moving targets over a time interval. The vertical federated learning is suitable for the ID of the training samples of participants overlap more and the data features less. The moving target is deemed to be a sample setSI. The feature space FE is formed into the moving target position, the moment of the current position, and exposure degree. Vertically federated learning is a process aggregating different features above, in which a model can be built with data from moving targets in cooperation. Under such assumption, (24) can be got.(24)FEi≠FEj,SIi=SIj,∀Di,Dj,i≠j.Training the model can solve the multioptimal path of the moving target. Specific steps are as follows.Step 1.
Participants locally compute exposure and time and send masked results to the server.Step 2.
The server performs secure aggregation without learning information about any participant.Step 3.
The server sends back the aggregated results to participants.Step 4.
Participants update their respective model with the decrypted results.Whereas varied positions of moving targetA as time running would decide the direction of moving target B, time variable was imported over multiobjective path judgment. The probability of being detected by the sensor would be increasing (like a traffic problem [27]) as two moving targets on the same Voronoi edge. The presumption is that when target A is at Voronoi edgeViVj, if target B passing by edge ViVj, the heuristic estimated cost HB of target B would be H′B.(25)H′B=k⋅HBk>1.The Underwater Sensor Network is a system that collects underwater sounds and tracks and monitors the Navy’s passing ships and submarines. The underwater acoustic detectors (UADs) are installed on the seafloor and act as sensor nodes. The moving target is an autonomous underwater vehicle (AUV) that needs to pass through the monitoring area. For more information gathering and security reasons, it is a method to keep the AUV from going the same path as much as possible by adjusting thek value in (25).


### 3.2.2. The Algorithm Flow and the Procedure of Realization

When multiple intrusion targets need to be transmitted, a time-variable is introduced in this paper to conduct dynamic pathfinding of multiple intrusion targets based on federated learning feature (MFF). Assuming that multiple moving targetsM1,M2,⋯,Mn start from s every time interval T, the HX value is updated according to the formula (25) and the location of the moving target at different times. Based on the SPF algorithm, we need to create some new data structures to store variables in the MFF algorithm, as shown in Table 2.Table 2
Comparison of Delaunay generation algorithms.
DetCost_LinesThe exposure value of eachVoronoi edgeDetTime_LinesThe time required for the moving target to move along eachVoronoi edge (ViVj)Path_CostThe respective cost and total cost of all departing moving targets at a given timePath_FCostThe respective projected cost values of all departing moving targets at a given timePath_Record _CurrentPointThe name of the current pointPath_Record _PreviouPointThe previous node nameThe specific algorithm flow is as Algorithm4. By contrast to the SPF algorithm for a single intrusion target, the MFF algorithm sets a time variable to record the positions of distinct targets moving every period, which position relationship can update data onto the model.Algorithm 4: MFF algorithm.
Input:Graph V(WSN)Output:optimal path1:NotVis=[s]; BeenVis=[]2: while TheNotVis table is not empty do3: Select the path with the lowest total proxy valueF from NotVis. And record the corresponding moving target serial number i.4: if All moving targets are the end nodef then5:  Returnpath6: end if7: Update DetCost_line according to (25) and path8: Sort Path_Time_CurrentPoint in ascending order, and record the moving targer serial number respectively. (Determine the moving targetMj that reaches the next Voronoi vertex first)9: for All moving targets do10:  ifMi reaches the end point then11:   Calculate path ofMj12:  elseBreak;13:  end if14: end for15: Make path prediction forMi which has minimum value of Path_Time_CurrentPoint by SPF algorithm16: Update Path_Record_CurrentPoint17: Update Path_Time_CurrentPoint18: Goto line 719: end while


## 3.2.1. The Calculation Model Established by Feature-Partitioned

It is sometimes a practical demand to transfer multiple moving targets over a time interval. The vertical federated learning is suitable for the ID of the training samples of participants overlap more and the data features less. The moving target is deemed to be a sample setSI. The feature space FE is formed into the moving target position, the moment of the current position, and exposure degree. Vertically federated learning is a process aggregating different features above, in which a model can be built with data from moving targets in cooperation. Under such assumption, (24) can be got.(24)FEi≠FEj,SIi=SIj,∀Di,Dj,i≠j.Training the model can solve the multioptimal path of the moving target. Specific steps are as follows.Step 1.
Participants locally compute exposure and time and send masked results to the server.Step 2.
The server performs secure aggregation without learning information about any participant.Step 3.
The server sends back the aggregated results to participants.Step 4.
Participants update their respective model with the decrypted results.Whereas varied positions of moving targetA as time running would decide the direction of moving target B, time variable was imported over multiobjective path judgment. The probability of being detected by the sensor would be increasing (like a traffic problem [27]) as two moving targets on the same Voronoi edge. The presumption is that when target A is at Voronoi edgeViVj, if target B passing by edge ViVj, the heuristic estimated cost HB of target B would be H′B.(25)H′B=k⋅HBk>1.The Underwater Sensor Network is a system that collects underwater sounds and tracks and monitors the Navy’s passing ships and submarines. The underwater acoustic detectors (UADs) are installed on the seafloor and act as sensor nodes. The moving target is an autonomous underwater vehicle (AUV) that needs to pass through the monitoring area. For more information gathering and security reasons, it is a method to keep the AUV from going the same path as much as possible by adjusting thek value in (25).


## 3.2.2. The Algorithm Flow and the Procedure of Realization

When multiple intrusion targets need to be transmitted, a time-variable is introduced in this paper to conduct dynamic pathfinding of multiple intrusion targets based on federated learning feature (MFF). Assuming that multiple moving targetsM1,M2,⋯,Mn start from s every time interval T, the HX value is updated according to the formula (25) and the location of the moving target at different times. Based on the SPF algorithm, we need to create some new data structures to store variables in the MFF algorithm, as shown in Table 2.Table 2
Comparison of Delaunay generation algorithms.
DetCost_LinesThe exposure value of eachVoronoi edgeDetTime_LinesThe time required for the moving target to move along eachVoronoi edge (ViVj)Path_CostThe respective cost and total cost of all departing moving targets at a given timePath_FCostThe respective projected cost values of all departing moving targets at a given timePath_Record _CurrentPointThe name of the current pointPath_Record _PreviouPointThe previous node nameThe specific algorithm flow is as Algorithm4. By contrast to the SPF algorithm for a single intrusion target, the MFF algorithm sets a time variable to record the positions of distinct targets moving every period, which position relationship can update data onto the model.Algorithm 4: MFF algorithm.
Input:Graph V(WSN)Output:optimal path1:NotVis=[s]; BeenVis=[]2: while TheNotVis table is not empty do3: Select the path with the lowest total proxy valueF from NotVis. And record the corresponding moving target serial number i.4: if All moving targets are the end nodef then5:  Returnpath6: end if7: Update DetCost_line according to (25) and path8: Sort Path_Time_CurrentPoint in ascending order, and record the moving targer serial number respectively. (Determine the moving targetMj that reaches the next Voronoi vertex first)9: for All moving targets do10:  ifMi reaches the end point then11:   Calculate path ofMj12:  elseBreak;13:  end if14: end for15: Make path prediction forMi which has minimum value of Path_Time_CurrentPoint by SPF algorithm16: Update Path_Record_CurrentPoint17: Update Path_Time_CurrentPoint18: Goto line 719: end while


## 4. Experiment

In this section, the performance of the SPF and MFF algorithm is validated through simulation experiments. It analyzed the condition that finding MRP was influenced by distinct node quantities and various distributed modes in the sensing area and whether the algorithms are effective against different network topologies.It is assumed that the network topology application scenario is an Underwater Sensor Network in this paper. The experimental environment is in an ideal state, as shown in Figure3. The UADs are deployed on the seabed to form a monitoring area, and the AUVs move at a uniform speed in the same horizontal plane. From the starting point, the AUVs pass through the monitoring area to the endpoint to perform the underwater penetration mission of the submarine.Figure 3
Underwater Sensor Network.We plan to use underwater acoustic communication technology to solve information transmission and sharing among unmanned underwater clusters. In a multiagent case, clock synchronization between two agents is generally calculated by multiround communication to calculate the deviation and offset rate between clocks. According to the research of Liu et al. [28], several particular nodes named anchors are selected among all moving targets in this paper to aid the localization process.The anchors are clock synchronized that the moving target achieves clock synchronization by communicating with anchors and estimating the message propagation time. The targeted target broadcasts the location demand, and the anchor reveals the location message containing the sending time and location information after receiving the location request. When the targeted target receives the location message, the transmission delay of the message can be calculated based on the local clock and the sending time in the news. Then, the distance to the anchor can be estimated [29].


### 4.1. Single Mobile Device

To verify the accuracy of the model and algorithm, we can figure out the minimum exposure path via the topology in [6]. The data manifested in Table 3 are the parameters in the experiment. And the results can be found in Figure 4. The number of sensor nodes is expressed by variable n.Table 3
Experimental parameters (1).
ParameterValueMonitoring area300∗300λ1K2q0k2n32Starting point(0,120)Ending point(300,195)Figure 4
Minimum exposure path.
(a)
MEP based on [6](b)
MRP based on SPFThirty-two sensors are deployed on a300∗300 monitoring field. We used the HGA-NFE method [6] and SPF algorithm in this paper for path planning, respectively, as shown in Figure 4. Figure 4(a) reveals the MEP found based on the HGA-NFE method in [6]. The Voronoi nodes of the path passed are [50,4,6,14,13,23,22,28,32,35,45,44,60], and the exposure value of this path is 104.1807. Figure 4(b) displays the MRP found based on the SPF algorithm. The Voronoi nodes of the path passed are [50,4,6,14,13,23,22,28,32,37,39,44,60], and the exposure value of this path is 104.1459. The lengths of MRP and MEP are both 379.07, but MRP has a smaller exposure value than the MEP, which is computed by the HGA-NFE method. It indicates that the SPF algorithm is more accurate than the HGA-NFE method [6].Network topologies can be divided into three different network types according to the deployment of sensors. They are the uniform distribution method, Gaussian distribution method, and exponential distribution method [17]. We limited the distance relationship between nodes in the experiment to achieve all kinds of distribution. For studying the efficiency of the SPF, topologies were randomly generated according to the three network types mentioned. The calculation time of SPF under different topologies is shown in Figure 5.Figure 5
Computing time of MRP in 3 topologies.
(a)
Uniform distribution(b)
Gaussian distribution(c)
Exponential distribution(d)
Total computing timeThe total computation time of MRP falls into two parts. One is the time to construct the Voronoi diagram, and the other is the time to find the path. We can find that the total computation time of MRP increases as the number of nodes increases because the time complexity of constructing the Voronoi diagram is related to the number of nodes. The total computation time comparison of the SPF algorithm under the three topologies is shown in Figure5(d). It is no doubt that the SPF algorithm is more efficient under the topology of uniform distribution.Binh et al. [17] proposed the GA-MEP algorithm for intrusion path planning. It is difficult to compare the time complexity of the SPF algorithm with the genetic algorithm GA-MEP [17] because the complexity of GA-MEP is not related to the number of sensor nodes. Hence, to test the efficiency of SPF, the calculation time of SPF and GA-MEP was compared. Figure 6 displays the results.Figure 6
Comparison between SPF and GA-MEP.
(a)
Uniform distribution(b)
Gaussian distribution(c)
Exponential distributionThe computing time of the SPF algorithm grows slowly with the increase of sensor nodes in this area, which is better than the GA-MEP algorithm. It indicates that the SPF algorithm is more suitable for the condition of a large number of sensors. The calculation time of SPF is shorter than that of GA-MEP, and the SPF algorithm is more stable for different network topologies. In the case of the same intrusion path exposure, the efficiency of the algorithm proposed in this paper is far better than the GA-MEP algorithm [17].To explore path-finding law limited by various constraints, experiments have been done on the uniform distribution network topology wheren=20 and n=40, respectively. The selected parameters are put in Table 4. The results are shown in Figure 7. To explore path-finding law limited by various constraints, experiments have been done on the uniform distribution network topology where n=20 and n=40, respectively.Table 4
Experimental parameters (2).
ParameterValueMonitoring area300∗300λ1K2q0,50k2Number of sensor nodes20,40Starting point(0,300)Ending point(300,0)Figure 7
Different paths whenn=20 and n=40.
(a)
n=20 (MEP)(b)
n=20 (minimal path)(c)
n=20 (MRP)(d)
n=40 (MEP)(e)
n=40 (minimal path)(f)
n=40 (MRP)Figure7 illustrates three simulation scenarios. The first one is only considering the impact of exposure on the path (as explicated in Figures 7(a) and 7(d)), which is transformed into find the minimum exposure path. The second solely thinks about the impact of the moving target energy consumption on the path (as shown in Figures 7(b) and 7(e)). Thus, it is equivalent to solving the minimal path problem. Thirdly, we consider both the exposure and energy consumption of the moving target (as revealed in Figures 7(c) and 7(f)).We calculated the path exposure value and path length under three simulation conditions. The experimental results in Table5 show that when only considering the effect of exposure on the path, the total exposure value of the path is the lowest. However, the length of path is the longest, which means that the invader has the highest energy consumption. When only considering the effect of energy consumption on the path, the length is the lowest, which means energy consumption is the lowest. However, the exposure degree increases accordingly. When considering both exposure and energy consumption, the relevant parameters of the path in the data model generated by federated learning are between the above two results. It conforms to the hypothesis, proving that the SPF algorithm proposed can calculate the path according to different requirements.Table 5
Experimental results.
ExposureLength of pathn=20 (MEP)91.42557.31n=20 (minimal path)156.70536.49n=20 (MRP)94.72551.91n=40(MEP)183.93616.32n=40 (minimal path)244.53498.75n=40 (MRP)200.96535.20The quality of MRP relates to the path’s exposure, and it was affected by the amount of sum and various parts composed. Thus, we compared the maximum exposure value of partsEmax of the path, and the results can be found in Table 6.Table 6
Experimental results.
Emax(exposure)Length of pathn=2019.9021.62n=4036.9336.93It can be seen in the column that the maximum exposure value of part of MRP obtained by the SPF algorithm is the same as that of MEP. But it takes less time and energy when an invader moves along MRP. To test the universality of this circumstance, we also calculated MRP with different node numbers. Relevant experimental data is in Table7.Table 7
Exposure and length of path.
Emax(exposure)Emax(both)l(exposure)l(both)n=6037.5637.56505.6500.55n=8031.0743.10524.55510.60n=10045.0845.08534.84523.86n=12043.2747.76563.91539.76According to Tables6 and 7, we can get a conclusion. When calculating MRP by SPF algorithm, there is a 42.86% probability of getting a path with the same maximum exposure value of MEP but shorter travel time and less energy consumption. The simulation test was carried out under the parameter settings displayed in Table 4.Figure8 describes the relationship between MRP exposure (travel time) and the number of sensor nodes with different q values. With the augmentation of sensor nodes, the exposure degree keeps an upward trend and the intrusion time has a specific change.Figure 8
Exposure and travel time of different sensor nodes.
(a)
Exposure(b)
TimeIn the identical topologies, we can adjust the model created by federated learning to get the path (MRP) with less exposure and shorter intrusion time. It is conductive to save the energy consumption and reduce the probability of being detected by the sensor nodes.


### 4.2. Multi Mobile Devices

In terms of multi-objective, a simulation was made for the verification of MFF performance. The valuek represents the change of the edge when two moving targets are on the same edge. In the tangible situation, k can be adjusted according to different requirements for obtaining different path combinations.Assume that there are four intruders with the same starting point (0,300) and the same ending point (300,0). Each moving target sets off every 0.6 seconds andk=2. The results are shown in Figure 9, which show the four paths found when 40 nodes distributed evenly in F. The four intruders took a total of 12.32 seconds to travel from starting point to the ending point, with a total exposure degree of 678.58. And the exposure of each path is 162.13, 176.27, 162.13, and 178.05. It can be found that the trajectory of the third target moving coincides with the first as time going by. The result is identical when n equals 60.Figure 9
Paths for four intruders whenn=40 and T=0.6.
(a)
Target 1(b)
Target 2(c)
Target 3(d)
Target 4What can be explained is that the first moving target starts first and moves farther during the same period without affecting the path planning of subsequent moving targets. Therefore, whenk=2, the first moving target trajectory is likely to be the same as the trajectory of the third moving target.The experiment is carried out in this section whenn=40 so as to study the influence of departure time interval of moving targets on multiobjective path planning. Each intruder sets off at a time interval of 0.4, 0.6, 0.8, and 1.0, and the relevant experimental data are shown in Table 8. The maximum and minimum intrusion time of a single target is Time(max) and Time(min), the maximum exposure of a single target is Exp(max), and the minimum exposure of a target is Exp(min).Table 8
Exposure and length of path.
T=0.4T=0.6T=0.8T=1.0Travel time11.8512.3213.3813.56Total exposure727.35716.35677.08815.96Time(max)11.0411.111.0111.13Time(min)10.1410.1710.1710.17Exp(max)206.26232.68214.01217.18Exp(min)127.01127.01122.01189.54It can be seen from Table8 that with the increase of the time interval of sending moving target, the total travel time increases continuously. But the total exposure decreases continuously until a minimum value and then increases accordingly. This is because the longer a target stays in the WSN region, the greater the risk probability detected by the sensor. When the time interval reaches a certain peak, cross-path interference factors are excluded, and the greater the total exposure. The minimum exposure and time consumption of a single target do not change with a time interval because the MRP of a single target is the path obtained by the SPF algorithm.


## 4.1. Single Mobile Device

To verify the accuracy of the model and algorithm, we can figure out the minimum exposure path via the topology in [6]. The data manifested in Table 3 are the parameters in the experiment. And the results can be found in Figure 4. The number of sensor nodes is expressed by variable n.Table 3
Experimental parameters (1).
ParameterValueMonitoring area300∗300λ1K2q0k2n32Starting point(0,120)Ending point(300,195)Figure 4
Minimum exposure path.
(a)
MEP based on [6](b)
MRP based on SPFThirty-two sensors are deployed on a300∗300 monitoring field. We used the HGA-NFE method [6] and SPF algorithm in this paper for path planning, respectively, as shown in Figure 4. Figure 4(a) reveals the MEP found based on the HGA-NFE method in [6]. The Voronoi nodes of the path passed are [50,4,6,14,13,23,22,28,32,35,45,44,60], and the exposure value of this path is 104.1807. Figure 4(b) displays the MRP found based on the SPF algorithm. The Voronoi nodes of the path passed are [50,4,6,14,13,23,22,28,32,37,39,44,60], and the exposure value of this path is 104.1459. The lengths of MRP and MEP are both 379.07, but MRP has a smaller exposure value than the MEP, which is computed by the HGA-NFE method. It indicates that the SPF algorithm is more accurate than the HGA-NFE method [6].Network topologies can be divided into three different network types according to the deployment of sensors. They are the uniform distribution method, Gaussian distribution method, and exponential distribution method [17]. We limited the distance relationship between nodes in the experiment to achieve all kinds of distribution. For studying the efficiency of the SPF, topologies were randomly generated according to the three network types mentioned. The calculation time of SPF under different topologies is shown in Figure 5.Figure 5
Computing time of MRP in 3 topologies.
(a)
Uniform distribution(b)
Gaussian distribution(c)
Exponential distribution(d)
Total computing timeThe total computation time of MRP falls into two parts. One is the time to construct the Voronoi diagram, and the other is the time to find the path. We can find that the total computation time of MRP increases as the number of nodes increases because the time complexity of constructing the Voronoi diagram is related to the number of nodes. The total computation time comparison of the SPF algorithm under the three topologies is shown in Figure5(d). It is no doubt that the SPF algorithm is more efficient under the topology of uniform distribution.Binh et al. [17] proposed the GA-MEP algorithm for intrusion path planning. It is difficult to compare the time complexity of the SPF algorithm with the genetic algorithm GA-MEP [17] because the complexity of GA-MEP is not related to the number of sensor nodes. Hence, to test the efficiency of SPF, the calculation time of SPF and GA-MEP was compared. Figure 6 displays the results.Figure 6
Comparison between SPF and GA-MEP.
(a)
Uniform distribution(b)
Gaussian distribution(c)
Exponential distributionThe computing time of the SPF algorithm grows slowly with the increase of sensor nodes in this area, which is better than the GA-MEP algorithm. It indicates that the SPF algorithm is more suitable for the condition of a large number of sensors. The calculation time of SPF is shorter than that of GA-MEP, and the SPF algorithm is more stable for different network topologies. In the case of the same intrusion path exposure, the efficiency of the algorithm proposed in this paper is far better than the GA-MEP algorithm [17].To explore path-finding law limited by various constraints, experiments have been done on the uniform distribution network topology wheren=20 and n=40, respectively. The selected parameters are put in Table 4. The results are shown in Figure 7. To explore path-finding law limited by various constraints, experiments have been done on the uniform distribution network topology where n=20 and n=40, respectively.Table 4
Experimental parameters (2).
ParameterValueMonitoring area300∗300λ1K2q0,50k2Number of sensor nodes20,40Starting point(0,300)Ending point(300,0)Figure 7
Different paths whenn=20 and n=40.
(a)
n=20 (MEP)(b)
n=20 (minimal path)(c)
n=20 (MRP)(d)
n=40 (MEP)(e)
n=40 (minimal path)(f)
n=40 (MRP)Figure7 illustrates three simulation scenarios. The first one is only considering the impact of exposure on the path (as explicated in Figures 7(a) and 7(d)), which is transformed into find the minimum exposure path. The second solely thinks about the impact of the moving target energy consumption on the path (as shown in Figures 7(b) and 7(e)). Thus, it is equivalent to solving the minimal path problem. Thirdly, we consider both the exposure and energy consumption of the moving target (as revealed in Figures 7(c) and 7(f)).We calculated the path exposure value and path length under three simulation conditions. The experimental results in Table5 show that when only considering the effect of exposure on the path, the total exposure value of the path is the lowest. However, the length of path is the longest, which means that the invader has the highest energy consumption. When only considering the effect of energy consumption on the path, the length is the lowest, which means energy consumption is the lowest. However, the exposure degree increases accordingly. When considering both exposure and energy consumption, the relevant parameters of the path in the data model generated by federated learning are between the above two results. It conforms to the hypothesis, proving that the SPF algorithm proposed can calculate the path according to different requirements.Table 5
Experimental results.
ExposureLength of pathn=20 (MEP)91.42557.31n=20 (minimal path)156.70536.49n=20 (MRP)94.72551.91n=40(MEP)183.93616.32n=40 (minimal path)244.53498.75n=40 (MRP)200.96535.20The quality of MRP relates to the path’s exposure, and it was affected by the amount of sum and various parts composed. Thus, we compared the maximum exposure value of partsEmax of the path, and the results can be found in Table 6.Table 6
Experimental results.
Emax(exposure)Length of pathn=2019.9021.62n=4036.9336.93It can be seen in the column that the maximum exposure value of part of MRP obtained by the SPF algorithm is the same as that of MEP. But it takes less time and energy when an invader moves along MRP. To test the universality of this circumstance, we also calculated MRP with different node numbers. Relevant experimental data is in Table7.Table 7
Exposure and length of path.
Emax(exposure)Emax(both)l(exposure)l(both)n=6037.5637.56505.6500.55n=8031.0743.10524.55510.60n=10045.0845.08534.84523.86n=12043.2747.76563.91539.76According to Tables6 and 7, we can get a conclusion. When calculating MRP by SPF algorithm, there is a 42.86% probability of getting a path with the same maximum exposure value of MEP but shorter travel time and less energy consumption. The simulation test was carried out under the parameter settings displayed in Table 4.Figure8 describes the relationship between MRP exposure (travel time) and the number of sensor nodes with different q values. With the augmentation of sensor nodes, the exposure degree keeps an upward trend and the intrusion time has a specific change.Figure 8
Exposure and travel time of different sensor nodes.
(a)
Exposure(b)
TimeIn the identical topologies, we can adjust the model created by federated learning to get the path (MRP) with less exposure and shorter intrusion time. It is conductive to save the energy consumption and reduce the probability of being detected by the sensor nodes.


## 4.2. Multi Mobile Devices

In terms of multi-objective, a simulation was made for the verification of MFF performance. The valuek represents the change of the edge when two moving targets are on the same edge. In the tangible situation, k can be adjusted according to different requirements for obtaining different path combinations.Assume that there are four intruders with the same starting point (0,300) and the same ending point (300,0). Each moving target sets off every 0.6 seconds andk=2. The results are shown in Figure 9, which show the four paths found when 40 nodes distributed evenly in F. The four intruders took a total of 12.32 seconds to travel from starting point to the ending point, with a total exposure degree of 678.58. And the exposure of each path is 162.13, 176.27, 162.13, and 178.05. It can be found that the trajectory of the third target moving coincides with the first as time going by. The result is identical when n equals 60.Figure 9
Paths for four intruders whenn=40 and T=0.6.
(a)
Target 1(b)
Target 2(c)
Target 3(d)
Target 4What can be explained is that the first moving target starts first and moves farther during the same period without affecting the path planning of subsequent moving targets. Therefore, whenk=2, the first moving target trajectory is likely to be the same as the trajectory of the third moving target.The experiment is carried out in this section whenn=40 so as to study the influence of departure time interval of moving targets on multiobjective path planning. Each intruder sets off at a time interval of 0.4, 0.6, 0.8, and 1.0, and the relevant experimental data are shown in Table 8. The maximum and minimum intrusion time of a single target is Time(max) and Time(min), the maximum exposure of a single target is Exp(max), and the minimum exposure of a target is Exp(min).Table 8
Exposure and length of path.
T=0.4T=0.6T=0.8T=1.0Travel time11.8512.3213.3813.56Total exposure727.35716.35677.08815.96Time(max)11.0411.111.0111.13Time(min)10.1410.1710.1710.17Exp(max)206.26232.68214.01217.18Exp(min)127.01127.01122.01189.54It can be seen from Table8 that with the increase of the time interval of sending moving target, the total travel time increases continuously. But the total exposure decreases continuously until a minimum value and then increases accordingly. This is because the longer a target stays in the WSN region, the greater the risk probability detected by the sensor. When the time interval reaches a certain peak, cross-path interference factors are excluded, and the greater the total exposure. The minimum exposure and time consumption of a single target do not change with a time interval because the MRP of a single target is the path obtained by the SPF algorithm.


## 5. Performance Evaluation

Well-defined evaluation criteria and adversary models put the pathfinding schemes on common WSN topology, making it possible to assess the scenarios fairly and comprehensively [30–32]. The adversary model in this paper refers to different types of WSN topologies. Sensor nodes can detect moving targets but will not attack them. Invaders require finding one or more paths through the sensor area. Security, availability, efficiency, and deployability are important evaluation indexes for intrusion detection systems [33–36]. Similarly, we select some evaluation properties [34, 35] as the evaluation indexes of the intrusion path planning algorithm.(A)
Security(i)
S1 Exposure. For an intruder, its security is reflected in the exposure of the invasion path mostly. Lower exposure means a safer moving target.(ii)
S2 Energy Consumption. An ideal invasion path for an intruder requires low exposure and minimal energy consumption as the intruder moves along the trail. Otherwise, the moving target is likely to run out of energy on the way so that it cannot fulfill the task.(B)
Availability(i)
A1. It can be used in WSN with a Boolean disk perception model.(ii)
A2. It can be used in WSN, whose perception model is the probabilistic perception model.(iii)
A3. It can be used in WSN with an attenuated disk perception model.(C)
Deployability(i)
D1. Whether it is suitable for large-scale networks. In actual application scenarios, the scale of WSN is often large, so if we want to expand the application algorithm, it is imperative to apply it to large-scale networks.(ii)
D2. Whether it considered multiple moving targets. The “moving target” is not only a single target. When the intrusion of a single target expands to multiple target intrusion, whether the algorithm is still effective also needs to be included in the evaluation.(iii)
D3. Whether multiple sensor network topologies are considered.(iv)
D4. Algorithmic efficiency, which is mainly compared from the time complexity and running time. It is divided into two levels, “excellent” and “good.”(v)
According to the above criteria, we evaluate the algorithm proposed in this paper and the existing methods. The results are summarized in Table9.Table 9
Measuring security, availability, and deployability of algorithm.
SchemeNo.SecurityAvailabilityDeployabilityS1S2A1A2A3D1D2D3D4Meguerdichian et al.2001[8]✓✗○○✓✗✗✗☆Song et al.2014[37]✓✗○○✓✗✗✓☆Ye et al.2016[6]✓✗○✓○✓✗✗☆Binh et al.2019[17]✓✗○✓○✓✗✓★Aravinth et al.2021[18]✓✓✓○○✓✗✗★Our scheme✓✓○○✓✓✓✓★Note: ✓ means achieving the corresponding goal, while ✗ not. ○ does not mean anything. ☆ means “good,” and ★ means “excellent.”.


## 6. Conclusions

This paper built a data model of the dynamic-planning algorithm to keep the risk of multi-intrusion targets minimized, which utilizes computational geometry methods amalgamated with federated learning features. The experiment results show that the algorithm that introduced time variables can actualize the global optimization. By contrast with traditional planning ways, its computational performance prevails in complexity and time.Hx weights by Cti,tj can be adjusted to meet various demands of path selection.The MRP exposure of all the discrete paths distinctly declined in comparison with MEP. MRP can markedly lower the energy consumption without being detected by the sensor nodes as much as possible. Consequently, the algorithm accurately satisfies the real-life conditions, such as the battlefield crossing scenarios. The model has an inspired significance to the sensor network deployment.The common application of multiple types of sensors in WSN becomes increasingly popular, which increases the path analysis complexity. Hence, it is necessary to analyze more actual models of WSN deployment to explore further. Besides, fulfilling federal learning in three-dimensional space to make path planning is a new direction.



---

*Source: 9974279-2021-07-09.xml*