Algorithms for Finding Vulnerabilities and Deploying Additional Sensors in a Region with Obstacles

: Consider a two-dimensional rectangular region guarded by a set of sensors, which may be smart networked surveillance cameras or simpler sensor devices. In order to evaluate the level of security provided by these sensors, it is useful to ﬁnd and evaluate the path with the lowest level of exposure to the sensors. Then, if desired, additional sensors can be placed at strategic locations to increase the level of security provided. General forms of these two problems are presented in this paper. Next, the minimum exposure path is found by ﬁrst using the sensing limits of the sensors to compute an approximate “feasible area” of interest, and then using a grid within this feasible area to search for the minimum exposure path in a systematic manner. Two algorithms are presented for the minimum exposure path problem, and an additional subsequently executed algorithm is proposed for sensor deployment. The proposed algorithms are shown to require signiﬁcantly lower computational complexity than previous methods, with the fastest proposed algorithm requiring O ( n 2.5 ) time, as compared to O ( mn 3 ) for a traditional grid-based search method, where n is the number of sensors, m is the number of obstacles, and certain assumptions are made on the parameter values.


Introduction
A wireless sensor network (WSN) can be used for various tasks such as monitoring the environment and industrial facilities. Each generation of sensors tends to be smaller, more energy efficient, and less expensive than the previous generation. These trends have permitted the development of systems with an extremely large number of sensors. Management of such large networks entails solving problems related to how sensors are deployed, interconnected, and communicate with each other [1].
An important application of sensor networks and WSNs is surveillance [1], which can be conducted using smart networked surveillance cameras (a type of expensive networked sensor device) or simple sensor devices (such as heat, sound, or range sensors). For this type of application, the degree of security provided by the WSN is determined mainly by the positioning of the sensors. A common method for evaluating the adequacy of this type of WSN is to compute the minimum exposure path, which is a path that traverses the guarded region with the lowest level of exposure (Section 3.2) to the sensors. Then, if the resulting level of security is deemed to be insufficient, the existing sensors can be repositioned, additional sensors can be deployed, or both. This paper targets the problem of WSN surveillance in a rectangular region with obstacles and sensors that have sensitivities that vary depending on the distance to the target being detected [2][3][4][5][6][7][8]. The level of security provided by the sensors can be evaluated by finding the minimum exposure path in this target region. This paper proposes a general model and solution for this problem. In the proposed method, the outer limits of the sensing ranges of the sensors and a segment tree data structure are used to compute a feasible area, within which the minimum exposure path must reside. Then, a grid is used within this feasible area to search for the minimum exposure path. Given n sensors, m obstacles, and a few practical assumptions on model parameter values, the computational complexity of the proposed algorithm is O(n 2.5 ), which is a significant improvement over previous approaches, with computational complexity O(mn 3 ).
In addition to computing the minimum exposure path, the proposed algorithm can be used to determine the location (and pointing direction, if appropriate) where an additional sensor can be placed to reduce the vulnerability of the target region. This can easily be done since the process for computing the minimum exposure path includes the determination of the feasible area for this minimum exposure path, and the feasible area is the most vulnerable area [9][10][11]. The main contributions of this paper are as follows. • A general model, which encompasses most of the previously proposed models, is proposed for the minimum exposure problem. • A new algorithm is proposed for the minimum exposure problem. For large n and m values, the proposed algorithm is a significant improvement over previous approaches. • A new near-optimal algorithm is proposed for proper sensor deployment.
The rest of this paper is organized as follows. Section 2 reviews previous related research work. In Section 3, the problem being addressed in this paper is formally modeled and the proposed solution approach is described. In Section 4, the proposed solution and previous possible solutions are compared analytically, and an efficient sensor deployment algorithm is presented. Finally, concluding remarks are provided in Section 5.

Voronoi Diagram and Delaunay Triangulation
The Voronoi diagram [12] is a graph consisting of edges created by drawing dividing lines between each pair of adjacent sensors such that each line is equidistant to the two sensors that it separates, with the line being terminated when it intersects with another line or the outer boundary of the region being monitored. The Delaunay triangulation is the dual graph of a Voronoi diagram. These two graph theory concepts have been found to be useful for computing minimum and maximum exposure paths given certain assumptions on the sensitivities of the sensor used.
Marengoni et al. [1] describe research work on surveillance in a given area referred to as an art gallery. Given that the entire art gallery should be covered by at least one sensor, the authors address the problem of the minimum number of sensors that need to be deployed. The sensors are modeled as disks with infinite ranges. Even though it only considers a two-dimensional (2-D) area, if there are Steiner points, the coverage problem becomes NP-hard [1]. Otherwise, it is NP-complete. To solve the same problem in a 3-D space, the authors of [1] suggest the use of a polynomial approximation solution, which adopts a greedy approach using Delaunay triangulation and graph coloring concepts [12].
Meguerdichian et al. [13,14] suggest an approach that applies a geometrical algorithm to the coverage problem. They assume all n sensors are modeled with identical disks in which the sensitivity decreases as the distance between a point and a sensor increases. They define a maximal breach path as a path in which the distance from the closest sensor and itself is kept at a maximum. They also define a maximal support path as a path in which the distance from the closest sensor and itself is kept at a minimum value. To find the maximal breach path, they construct the Voronoi diagram [12]. After that, they set the weight of an edge in the Voronoi diagram to be the distance between that edge and the nearest sensor. Finally, they find the maximal breach path using a binary search process.
The key value used is the arithmetic average of the biggest and smallest values of the edges. The edges with weights over the key value are inserted in G , and Breadth-First-Search (BFS) is conducted on G . If BFS is successful, the key value is increased following the binary search. Otherwise, the key value is decreased following the binary search. After renewal of the key value, G is reinitialized and edges that are bigger than the key value are inserted in G . This process is continued until the difference between two consecutive key values is less than a tolerance value. The maximal support path is found in a similar manner but with a Delaunay triangulation graph. The maximal breach path can be found by first constructing the Voronoi diagram in O(n log n) time. The number of nodes and edges of the Voronoi diagram is O(n), so each BFS takes O(n) time and the binary search performs BFS in log(n) time. Therefore, the total time complexity becomes O(n log n).
Later, using similar definitions and assumptions, Li et al. [15] suggested computing the shortest path using the sums of the weights of the edges, not the minimum weights of edges as in a maximal breach path. To find the shortest path, they used the Bellman-Ford algorithm. However, if the edge values are nonnegative, Dijkstra's algorithm [16], with computational complexity O(n log n), is faster than the Bellman-Ford algorithm, with computational complexity O(n 2 ).
Hou et al. [17] suggested another method that produces both the maximal breach and maximal support paths using the Gabriel graph [12] and Dijkstra's algorithm. A mathematical proof was introduced to show the correctness of their result.
Mehta et al. [18] defined a breach number tree and introduced Kruskal's algorithm [12] to compute the maximal breach path and maximal support path. Using their method, if the Voronoi diagram with weight edges is constructed first, the paths can be computed in O(|P|), where |P| is the number of edges of the paths, and the values of the paths can be computed in O(1).
In general, given n sensors, the computation of the Voronoi diagram itself can be completed in O(n log n) time because the x and y coordinates of all sensors can be sorted first to determine the pairs of sensors to consider in the creation of the Voronoi diagram. The number of vertices |V| and edges |E| in the Voronoi diagram are O(n), so a shortest-path search algorithm, such as Dijkstra's algorithm, could be used to compute the maximal breach path in time O(|V| 2 ) or O(|E| + |V| log |V|) time using a min-priority queue implemented by a Fibonacci heap [16]. Thus, the overall time complexity for the computation of the maximal breach path using a Voronoi diagram is O(n log n).

Effect of Multiple Sensors Along a Path
Although the Voronoi diagram and Delaunay triangulation are useful concepts, they are found to be insufficient for the computation of the exact minimum exposure paths when the combined effect of multiple sensors are considered. For example, Figure 1 shows that if multiple sensors are clustered together in the lower region of an area while only one sensor is located in the upper region, then the minimum exposure path will be above the set of edges in the Voronoi diagram for this area. A detailed description of this effect is shown in Section 3.2 with an experiment based on the formal definitions of sensors, discover function, and exposure function. For more accurate path computation, the authors of [18][19][20][21] suggested a k-support path problem, and the authors of [19][20][21] solved this problem by implementing a k-th Voronoi diagram that includes the effect of the first to k-th nearest sensors. The authors of [19][20][21] defined the k-th nearest point Voronoi diagram (KNP-Voronoi diagram). Constructing the KNP-Voronoi diagram takes O(k 2 n log n) time and computing the minimum k-support path using Dijkstra's algorithm takes O(k 2 n log n) time. The authors of [22] found the maximal support path in the map, including the effect of not only the n sensors but also m obstacles. The authors of [22] suggested the use of the Constrained and Weighted Voronoi diagram (CW-Voronoi diagram). According to [23], the CW-Voronoi diagram has O(m 2 n 2 + n 4 ) vertices and edges, and constructing the CW-Voronoi diagram takes O(m 2 n 2 + n 4 ) time.
A discover function can be defined as or as a circle with decreasing sensitivity as distance increases, so the discover value is usually defined as discover(x, y) = max s∈S distance(s, (x, y)).
The maximum covered-distance of a path is defined with the definition of a path in Section 3.1, and the path p that maximizes the discover value is called the best coverage path or the best support path. Similarly, the minimum covered-distance can be defined as cover2(p) = min discover(p.x, p.y) and the path p that minimizes the cover value is called the minimum coverage path or the maximal breach path. The authors of [2,3] defined a sensor as a circle and found an optimal path based on intensity and exposure. The authors defined a discover function as the sum of all sensitivity potential function values at (x,y) for all sensors, and an optimal path is the path that minimizes the exposure value. The authors first found an optimal path with one sensor. If the starting point is (1, 0), the goal is (0, 1), there is a sensor s = (0, 0, 1 √ x 2 +y 2 , f s ), and f s is the same as Equation (5) with d = (1, 0) and θ = 2π, then the optimal path is (cos π 2 t, sin π 2 t) and the exposure along this path is π 2 . Based on the optimal path for a single sensor, they suggested a heuristic method for finding an optimal path with several sensors by running the Dijkstra algorithm map divided into horizontal, vertical, and diagonal grid lines. The authors of [4] defined a sensor as a cone and proposed a heuristic optimal path search method with several sensors by running Dijkstra's algorithm in a map divided into horizontal and vertical grid lines.
Later, approaches were proposed for finding an optimal exposure path. In [24,25], for a single sensor map, an optimal exposure path was calculated by solving the Euler-Lagrangian equation in polar coordinates, while setting ρ and φ as independent variables. The result is exactly the same as [2,3]. The authors of [26] used a similar method, but the optimal exposure path was calculated by solving the Euler-Lagrangian equation in Euclidian coordinates with x and y used as independent variables. For a map with multiple sensors, the authors of [24][25][26] used timing segmentation. They calculated the optimal direction for a specific position for an object, moved it slightly, calculated it again, moved it slightly, and so on until the object arrived at the goal. The authors of [27] set y as a function of x and solved the Euler-Lagrangian equation with x used as an independent variable. For multiple sensors, the authors of [27] considered only neighboring sensors and found an approximated path, which was a localized minimum exposure path.
The sensitivity potential function can be modeled as varying according to the target velocity, d dt p(t) = ( dx dt , dy dt ) [24][25][26]. In addition, the probability of detection will decrease if the target accelerates. Consider a sensor modeled as s = (0, 0, where f s is the sensitivity of the sensor, which varies depending on the sensing location and the velocity of the target. Then the exposure can be modeled as follows.
and the Euler-Lagrangian equation becomes and the solution is which is not feasible. Moreover, the Euler-Lagrangian equation does not provide a solution when the discover function does not have a continuous first partial derivative. Creating a grid on the map and running the Dijkstra algorithm with that grid is an alternative practical solution for general maps. The authors of [5] divided a map with square grids and introduced Gaussian noise in grid edges. After the values of grid edges were set, they found an optimal path with the Dijkstra algorithm. The authors of [28] defined a mathematical model of physarum, used physical features of physarum and found a path using these features. The authors of [6][7][8] not only set the value of grid edges as probabilistic values but also defined an exposure value in a probabilistic manner as follows.
discover : Furthermore, the multiplications can be changed to additions by converting the values to their logarithms. Then, additions can be used to calculate the grid edge values in the integral.
After that, they used the Dijkstra algorithm to find the shortest path. The authors of [29] use both the Voronoi diagram and the exposure concept. They used the Voronoi diagram but then corrected the path by considering the exposure to neighboring sensors. The authors of [30] then proposed an improvement by defining intensity as the sensing value of the nearest sensor and then integrating the effect of all sensors.

Sensor Deployment
The authors of [2,3,6,8,13,14,17,[30][31][32] defined sensors that have circle-shaped sensitivity functions. The authors of [13,17] deployed sensors in the middle of the least weighted edge of the Voronoi diagram. The authors of [2,3] conducted an experiment that compared random deployment and deterministic deployment. In deterministic deployment, they deployed sensors in the middle sections of their grid edges, which can be formed into triangle or hexagon shapes by changing the definitions of sensors and the discover value. Reference [13] also divided the target map into grids and formulated the one-level coverage problem, and then proposed a heuristic algorithm called Tabu Search (TS). The authors of [30] deployed sensor networks based on Average Linear Uncovered Length (ALUL) and Minimum Linear Uncovered Length (MLUL) definitions. They divided the map of grid edges and selected the position of the additional sensor that set the ALUL or MLUL to be the maximum. For MLUL, they used the Voronoi diagram. The authors of [6,8] deployed some of the sensors randomly and checked whether the minimum exposure satisfied the desired level. If not, more sensors were added and the previous step was repeated. This was continued until the minimum exposure satisfied the desired level. Reference [14] deployed an additional sensor in the middle of the grid edge square in which the summation of the edges was the smallest. Reference [31] deployed sensors randomly the first time and then let each sensor have a virtual repulsive force to other sensors so that they pushed each other apart. The authors of [33] also deployed sensors with the virtual force for minimizing the required number of mobile sensors in sweep coverage under the energy constraint. The authors of [32] presented an algorithm for finding locally-optimal coverage in the minimum unit-disk cover problem through a Lagrangian minimum approach with O(ln 4 ), where l is the number of iterations and n is the number of locations that must be included.
The authors of [9][10][11][34][35][36][37] defined sensors that have cone shaped sensitivity functions, which is a more general form than a circle. The authors of [34][35][36][37] deployed sensors in a region with obstacles. The authors defined a mathematical model for sensors in which the sensitivity extends to the boundary of the region or obstacles. The authors of [34,35] deployed sensors with a greedy algorithm. Reference [36] divided a region into grids and suggested a solution based on solving the integer nonlinear programming problem. As this becomes more difficult when the problem size gets larger, the authors of [37] suggested an immune-based algorithm. The authors of [38] suggested a barrier sweep coverage problem for covering not a whole area but finite critical curves with sector type sensors. They proved the barrier sweep coverage problem is an NP-hard problem and proposed an approximate algorithm.
The authors of [9,10] defined the most general form of the sensor, which has its own sensing radius and directional vector. They used virtual repulsive force and calculated the directional vector by virtual force. The authors of [11,39] applied Particle Swarm Optimization (PSO) to the coverage problem with this sensor model, and Reference [40] suggested Hybrid Genetic Particle Swarm Optimization (H-GPSO), which is a mixing model of the models in Reference [28] and [11]. The region considered in [9][10][11] does not include obstacles.

System Model
A general model is presented for the computation of the minimum exposure path problem. This model will attempt to encompass almost all of the previous models used while addressing their shortcomings.
We assume that the region to be guarded is a 2-D rectangle of dimensions B X and B Y . n sensors s i ∈ S are positioned within this region to detect trespassers, but the approach used here can easily be extended to a 3-D arbitrarily-shaped guarded region by replacing 2-D vectors to 3-D vectors. Each sensor s i ∈ S is positioned at s i,pos = (x i , y i ) and has a sensitivity potential function f s i ( x pos ) that denotes the strength of the signal detected at sensor s i due to a trespasser located at x pos = (x, y). Depending on the function f s i ( x pos ), we can model a sensor for which an event within a radius of (x i , y i ) is always detected whereas all events farther than the radius from s i remain undetected (the commonly-used solid disk model). More realistically, an f s i ( x pos ) function that decreases with the distance to x pos = (x, y) can be used to model a sensor in which the sensitivity to an event diminishes as the distance to the event is increased. Finally, this type of general definition for f s i ( x pos ) can also be used to model a sensor that can monitor events within a cone shape, such as would be the case with a camera with a limited field of view.
The presence of a set W of impassable obstacles is assumed, such as pillars, facilities in a factory, or a great pile of luggage. For an obstacle w ∈ W, a function f w exists that describes the obstacle as w = {(x, y) (x, y) ∈ X × Y and f w ( x pos ) > 0}. The function Boundary(area) is used to denote the boundary of a given area. For example, given f w as below, obstacle w is a rectangular area (Section 3.3). Thus, If the sensing area occupies the back of the obstacle, it means that the sensor has a field of view on the back of the obstacle, so it implies the situation should be a 3-D model rather than a 2-D model. Therefore, it is assumed that there is no field of view behind the obstacle from the 2-D sensor.
For example, Figure 2 shows a university dormitory area with four CCD (Charge Coupled Device) cameras and one dormitory building. A thief is at the start location, and the thief wants to get to the goal location while avoiding the sensing area of CCD cameras as much as possible. As the dormitory building is higher than any camera height, the camera's field of view cannot reach behind the building (Figure 2). The sensitivity potential function for a sensor s ∈ S is assumed to have the following general form, where η ∈ R is the noise potential, d s is a directional vector, and θ s 2 is the angle of the fieldof-view; K s , l 1 , and l 2 are sensor-dependent constants (Figure 3). The given coordinate x pos and position of sensor s i s i,pos are determined according to the dimension of the guaranteed region, which is (x, y) and (x i , y i ) for 2-D ( Figure 3a) and (x, y, z) and (x i , y i , z i ) for 3-D (Figure 3b).  In addition, we adopt the definitions for coverage and sensing area used in [41] and generalized the definitions with obstacles. To prevent a target from penetrating into obstacles, we define the sensitivity potential in obstacles to be positive infinity. In X × Y, we should construct the appropriate data structure using W and S. The appropriate data structure is one for which, when a coordinate is given, the information about which sensor functions or obstacles are covered is returned. We assume that sensors cannot see the target when it is obscured by obstacles. As an example, this assumption and Definition 1 results in sensing areas S1 to S11 when the sensors and an obstacle are arranged as in Section 3.3, which is geometrically simplified from the realistic scenario in Figure 2.
Finally, the area can be defined formally. The position where the target starts to move, or the entrance of the map, is denoted as (x in , y in ) ∈ X × Y, and the position where the target stops moving, or the exit point of the map, is denoted as (x out , y out ) ∈ X × Y. The map M is denoted formally as (X, Y, S, W, (x in , y in ), (x out , y out ), η), where η ∈ R is the noise potential.

Discover and Exposure Functions
The target wants to move from (x in , y in ) to (x out , y out ) with the least chance of being discovered by a sensor. To formally find the movement path of the target, we can consider a real analytic function p from the time interval to a specific point in the map, p : R → X × Y. However, the paths we consider start at (x in , y in ) and end at (x out , y out ). To avoid the infinite velocity value that results from the Euler-Lagrangian Equation (2), we set dp(t) dt = 1. Finally, the set of paths is formally denoted as P = {p , p is real analytic, the initial point of p is p start , and the final point of p is p goal }. A path p is an element of P.
The calculations using Equations (1) and (3) to set the optimal path are similar. Eventually they calculate the discover value by summing several functions and then calculate exposure as the integral of the discover function; the minimum paths are the same because the exponential function is increasing. For this reason we select Equation (1) for our target calculations.

Definition 2.
A discover value about specific position x pos is discover( x pos ) = ∑ s∈S f s ( x pos ). An exposure value about specific path p is exposure(p) = We also set the path that has the smallest exposure value of map M as p min (M). The exposure(p min (M)) is the degree of vulnerability of a region, which can be defined mathematically as shown below.
Although the Voronoi diagram and Delaunay triangulation are useful concepts, they are found to be insufficient for the computation of the exact minimal exposure paths when the combined effect of multiple sensors is considered. For example, if multiple sensors are clustered together in the corner of the map with weighted values (Figure 4), then the minimal exposure path from the Voronoi diagram is not actually the minimum. To verify that, we set an experiment. From the definition of the sensor (Equation (5)), we set θ s = 2π, K s = 10,000, l = 2, and set the noise η = 1. If the sensors are deployed following Figure 4, the resulted minimum exposure path from the Voronoi diagram usually represents more exposure value even than the 50 × 50 grids diagram ( Figure 5).

Feasible Paths and Areas
The proposed method reduces the time required to find the minimum exposure path. To accomplish this, we need to define additional sets and functions. Section 4 presents the actual algorithms and proofs that use these sets.
p min (N, A) is the path found by running the Dijkstra algorithm following N grid edges in area A.p min (N, A) approaches p min (M) as N goes to positive infinity, However, as N increases,p min (N, A) becomes more accurate but the number of computations increase. To reduce the number of computations with the same level of accuracy, we decided to limit the area of interest in the target map, and this area is called the feasible area,Ã. To findÃ, the skeleton of the feasible area, feasible paths, should be defined. A set of paths following the boundaries of sensing areas is denoted asP = {p(t) p ∈ P and p ∈ Boundary(whole sensing areas)}, and p min (M) = arg min p∈P exposure(p).

Minimum Exposure Path
Definitions for discover and exposure functions were presented in Section 2.2. References [2][3][4][5][6][7][8] tried to find p min (M) by partitioning the map area using edges and weighting each edge using the exposure value along the edge. Finally, they ran the Dijkstra algorithm while following the grid edges (Algorithm 1).
This paper proposes a new, more efficient method for finding the minimum exposure path, as shown in psuedocode format in Section 4.1. In the proposed method, we want to reduce the time consumption by reducing the time required to calculate each grid edge, and reducing the number of grid edges to be considered. To reduce the time required to calculate each grid edge, we added the step "Construct sensing area data structure" and set the grid edge values "based on an efficient data structure" (Algorithm 2). For additional time reduction, we added the step "MakeÃ" and "Run the Dijkstra algorithm with grid edges inÃ" (Algorithm 3). To "Run the Dijkstra algorithm withP" (Figure 8), the vertices and edges can be like those shown in Figure 8. The Dijkstra Algorithm can be used to find the shortest path using the vertices and edges shown. We will show that Algorithms 1 and 3 return the same result, but that Algorithm 3 is faster than Algorithm 1. Proof of Theorem 1. The sensing area data structure uses two concepts: a doubly-connected edge list and a segment tree. The doubly-connected edge list can be used to determine which sensors cover a specific region in O(d 1 ) time if a boundary edge is given, where d 1 is the maximum number of sensors in a sensing area. The segment tree can be used to find a boundary edge in O(log(m + n)) time if a point is given. When taken together, the list of sensors that cover a region can be found in O(log(m + n) + d 1 ) if a point is given. This is much faster than O(m + n).
When a sensor is included in the map, intersections and the leftmost point and the rightmost point become vertices. A single line segment bifurcates into two edges if they have different exposure values. This rule has two exceptions: when the line segment is outside the map boundary and when it is inside an obstacle, because a target cannot go outside the map boundary or inside an obstacle (Figure 9). The edges created in this manner are stored in a segment tree ( Figure 10). For each sensing area, information about edges, vertices, and the set of sensors that affect the sensitivity in that sensing area are stored.
The number of vertices, edges, and areas is O((m + n) 2 ). Therefore, the sensing data structure can be constructed in O((m + n) 2 log(m + n) 2 ) = O((m + n) 2 log(m + n)) time.  In Algorithm 3,Ã is the gray region in Figure 7. Grids are calculated only in the gray region in Figure 7. Let N X be the number of lines vertically, and N Y be the number of lines horizontally. The grid lines make a grid square. Then ) and the time complexity to calculate all edge values is O(N 2 X (d 2 + log(m + n) + d 1 )) and the time complexity to find the optimal path is O(N 2 X log N 2 X ) = O(N 2 X log N X ). Therefore, the total time complexity is = O((m + n) 2 log(m + n) + N 2 X (d 2 + log(m + n) + log N X + d 1 ). Furthermore, by applying 0 ≤ k ≤ d 1 ≤ n and 1 ≤ d 2 ≤ (m + n), the total time complexity of Algorithm 2 becomes O((m + n) 2 log(m + n) + N 2 X (m + n + log N X )) Now we show why the "Construct sensing area data structure" step should be included. Previous work [2,3,[24][25][26][27] did not include this step. If this step is ignored, all sensors and obstacles must be considered for all grid edges. The time complexity to cal-culate values for all edge values is O(N 2 X mn), and to findp min (N, . Therefore, the total time complexity of Algorithm 1 will be O(N 2 X mn + N 2 X log N X ) = O(N 2 X (mn + log N X )). This is obviously bigger than O(N 2 X (m + n + log N X )). To find a more accurate path than the path found with a Voronoi diagram, N X ≥ O(m + n). This makes O(N 2 X (mn + log N X )) > O((m + n) 2 log(m + n)). Therefore, including the "Construct sensing area data structure" step reduces the necessary time complexity. Proof of Theorem 3. At first, the path can be filtered if the sensitivity function of each sensor is convex downward. To simplify the proof, we consider a fractional sensitivity potential model modeled by Equation (5) (Figure 11). For an arbitrary convex downward function y = g(x), g (x) ≥ 0, and g (x + L) ≥ g (x) for all x and L > 0. We set h(x, L) = g(x + L) − (g(x) + Lg (x)), from which it follows that h(x,L) ∂x = g (x + L) − g (x) + Lg (x) ≥ 0 and h(x, 0) = 0. Therefore, h(x, L) ≥ 0 for all x and L > 0.
Next, in a map, if we apply For this reason, any sensitivity potential projected in any direction is convex downward.
No matter how many convex downward functions are added, the added function is also convex downward. For these two reasons, outside ofÃ, no path has an exposure value lower thanp min (N,Ã).Ã always containsp min (N, M). Moreover,Ã contains p min (M) because the maximum distance betweenp min (N, M) and p min (M) is less than the size of a side of a cell in the grid.  The number of areas is O((m + n) 2 ). Accordingly, the number of vertices and edges for "Run the Dijkstra algorithm with Boundary(sensing_areas) and configureÃ" are |V| = O((m + n) 2 ), |E| = O((m + n) 2 ). Then the Dijkstra algorithm takes O((m + n) 2 log(m + n) 2 ) = O((m + n) 2 log(m + n)) time. Each of the result paths is stored including the sensor information for the path. In step "DivideÃ with grid edges and set the values from sensing area data structure", grids can be configured through the sensor information. Therefore, those additional parts take O((m + n) 2 log(m + n)) time. This is the same as the step "Construct the sensing area data structure", so this step does not increase the time complexity. For those reasons, the additional computations used in Algorithm 3 do not increase the time complexity.
Although the above analysis has shown the time complexities of Algorithm 1 through Algorithm 3 in as exact a manner as possible, these time complexity equations can be expressed in simpler forms by adopting several practical assumptions.
First, for the reasonable coverage of the map, the number of sensors n should be more than the number of obstacles m, and sensors almost cover the whole map. Then, the time complexity of Algorithm 2 becomes O(n 2 log n + N 2 X (n + log N X )). Next, the shorter given path is, the smaller exposure of the path is. If a feasible path is about a straight line from the start in the lower left corner to the goal in the upper right, the area ratio ofÃ to whole map is about , where S av is the average sensing area of sensors ( Figure 7). According to the first assumption, nS av = N X B X N Y B Y . This induces the number of vertices and edges in "DivideÃ with grid edges and set the values from sensing area data structure" as Then, the time complexity to calculate all edge values is O( n) and the time complexity to find the optimal path is O( n log N X ). Therefore, the time complexity to find the optimal path is O(n 2 log n + N 2 n log N X ). Finally, by considering the computation limits, the number of vertical grid lines N X can be set to O(n), which derives the time complexity of Algorithms 1-3 as, respectively, O(mn 3 ), O(n 3 ), and O(n 2.5 ).

Deployment of Additional Sensors
Motivated byÃ, to handle the vulnerable area, additional sensors should be deployed in a manner that increases exposure(p min (M)) as much as possible. The candidate points are near the locally maximum curvature points due to the definition of the sensitivity potential function. The points at which the curvature are locally maximum are stored in the setL. An example of this set of points is shown asL = {(x 1 ,ỹ 1 ), (x 2 ,ỹ 2 ), (x 3 ,ỹ 3 ), (x 4 ,ỹ 4 ), (x 5 ,ỹ 5 )} in Figure 12.
For a point at which the curvature is a local maximum, such as (x j ,ỹ j ), where 0 ≤ j ≤ |L|, the normal vector − → N j can be computed. − → d j is set to the opposite direction of − → N j , so − → d j = − − → N j because the directional vector and normal vector are unit vectors. Let (x j ,ȳ j ) be the position of s for the outer curve of Boundary(Ã), with the sensing area of s being tangent to each other ( Figure 13).
To compare the points inL, the maximum increment coverage value should be selected. However, the increment value is only considered in the line between (x j ,ȳ j ) and (x j ,ỹ j ) because the error is not considerable. Let L j be the distance between (x j ,ȳ j ) and (x j ,ỹ j ) ( Figure 14). By following variable ξ j between [0, L j ], the position (x j , y j ) = (x j ,ȳ j ) + ξ j L j − → d j varies. The outer interval of [0, L j ] is not considered because the area of (Ã ∩ sensing area of s) by setting (x s , y s ) = (x j , y j ) becomes smaller in the outer of the interval of the position of s. Therefore, the approximate maximum increment coverage value for (x j ,ỹ j ) is denoted as incr j , and the corresponding ξ j is denoted as ξ j,max . incr j = max 0≤ξ j ≤L j Ã ∩sensing area of s, where (xs,ys )=(x j ,y j ) f s (x, y)dxdy, ξ j,max = arg max 0≤ξ j ≤L j Ã ∩sensing area of s, where (xs,ys )=(x j ,y j ) f s (x, y)dxdy.
For each (x j ,ỹ j ), incr j is calculated and all locally maximum curvature points are compared based on the incr j value. The index for which incr j is the maximum value is denoted as j max . j max = arg max 0≤j≤|L| incr j .
From j max , the undefined components of the additional sensor s are now defined, (x s , y s ) = (x j max , y j max ), and − → d s = − → d j max . After the sensor s is included in M, exposure(p min (M)) will be increased deterministically because the approximate position for the maximum increase is considered (Algorithm 4). Calculate (x j ,ȳ j ), and L j 7: Calculate incr j and ξ j,max 8: end for 9: Calculate j max , and fill the undefined components of s 10: Update sensing area with s 11: return M

Conclusions
This paper has addressed the general problem of WSN surveillance security by proposing a minimum exposure path search problem and a sensor deployment problem. Sensors, obstacles, and the target surveillance area have been modeled, and computationally efficient solutions have been proposed. For the minimum exposure path problem, the sensing limits of the sensors and the obstacle locations are used to form a "feasible area", within which the search is constrained. Vertical and horizontal grid lines are then used in this feasible area in order to search for the minimum exposure path in a computationally efficient manner. The proposed algorithm has computational complexity O(n 2.5 ), a significant improvement over previous approaches, with complexity O(mn 3 ), where m is the number of obstacles and n is the number of sensors.