Detecting unauthorized activities using a sensor network.
Sensing devices can be deployed to form a network for monitoring a region of interest. This chapter investigates the detection of a target in the region being monitored by using collaborative target detection algorithms among the sensors. The objective is to develop a low cost sensor deployment strategy to meet a performance criteria. A path exposure metric is proposed to measure the goodness of deployment. Exposure can be defined and efficiently computed for various target activities, targets traveling at variable speed and in the presence of obstacles in the region.Using exposure to evaluate the detection performance, the problem of random sensor deployment is formulated. The problem defines cost functions that take into account the cost of single sensors and the cost of deployment. A sequential sensor deployment approach is then developed. The chapter illustrates that the overall cost of deployment can be minimized to achieve a desired detection performance by appropriately choosing the number of sensors deployed in each step of the sequential deployment strategy.
Introduction
Recent advances in computing hardware and software are responsible
for the emergence of sensor networks capable of observing the en-
vironment, processing the data and making decisions based on the ob-
servations. Such a network can be used to monitor the environment,
detect, classify and locate specific events, and track targets over a specific
region. Examples of such systems are in surveillance, monitoring
of pollution, tra#c, agriculture or civil infrastructures [15]. The deployment
of sensor networks varies with the application considered. It can
be predetermined when the environment is su#ciently known and under
control, in which case the sensors can be strategically hand placed.
In some other applications when the environment is unknown or hostile,
the deployment cannot be a priori determined, for example if the sensors
are air-dropped from an aircraft or deployed by other means, generally
resulting in a random placement.
This chapter investigates the deployment of sensor networks performing
target detection over a region of interest. In order to detect a target
moving in the region, sensors make local observations of the environment
and collaborate to produce a global decision that reflects the status of
the region covered [3]. In general, this collaboration requires local processing
of the observations, communication between di#erent nodes, and
information fusion [16]. Since the local observations made by the sensors
depend on their position, the performance of the detection algorithm is a
function of the deployment, i.e. the number of sensors and their location.
Recently, several studies have addressed the problem of deployment with
the goal of determining the performance of a given deployment of sensors
or determining an optimal deployment to achieve a desired coverage of
the monitored region. The analysis of the sensor network performance
relies on the model chosen for the detection capacity of the sensors. This
chapter presents several models that di#er in their level of abstraction.
Then, it focuses on a formulation that models the energy measured by
the sensors as a function of the distance from the target to the sensors.
Detection algorithms using these energy values for decision making are
developed and their performance is analyzed in terms of false alarm and
detection probability. A probabilistic measure of the goodness of deployment
for target detection, called path exposure, is then defined. It is
a measure of the likelihood of detecting a target traveling in the region
using a given path. The higher the exposure of a path, the better the
deployment is to detect that path. A set of possible paths can be associated
to a given target activity, for example the traversal of the region
from one end to another is one such activity. The deployment performance
for detecting an activity is measured by the minimum exposure
over all possible paths. In this chapter, methods to e#ciently determine
the least exposed path are derived for three di#erent target activities,
namely unauthorized traversing, reaching and idling. The evaluation of
exposure in the presence of obstacles and for variable speed target is
also considered. Finally, this chapter presents a deployment strategy to
Detecting unauthorized activities using a sensor network 3
achieve a given detection performance. The deployment is assumed to
be random which corresponds to many practical applications where the
region to be monitored is not accessible for precise placement of sensors.
The tradeo#s of deployment lie between the network performance, the
cost of the sensors deployed, and the cost of deploying the sensors.
This chapter is organized as follows. In Section 2, models for target
detection and associated problems are presented. In Section 3, two
algorithms for distributed detection, namely value and decision fusion,
are proposed and analyzed. In Section 4, a definition for path exposure
is proposed and a method to evaluate the exposure of a given path is
developed for various applications. In Section 5, the problem of random
deployment is formulated and a solution using exposure is presented.
The chapter concludes with Section 6.
2. Various models for detection and associated
problems
In this section, a literature survey is conducted and various detection
sensor network models are presented. These models capture the ease for
sensors to detect a target, and they di#er in their level of abstraction.
Both sensor models and target models have been considered. Sensor
models directly consider the sensors individual detection performance
using sensing range or detection probability. Target models considers
the signal emitted by the target and measured by the sensors.
Models on individual sensor performance
A property common to most studies on deployment is that sensing
ability decreases with distance between the sensor and the phenomenon
observed. Relying merely on this assumption, the study presented in [12]
relates the detectability of a path P to the distance from P to the sensors.
Two paths of interest are identified. The maximal breach path is defined
as a path from which the closest distance to any of the sensors is as large
as possible, hence it is the path hardest to detect. The maximal support
path is defined as a path for which the farthest distance from the closest
sensor is as small as possible, hence it is the path easiest to detect.
In [9], authors propose a probabilistic model for the detection capability
of individual sensors. They assume that the probability of a sensor
detecting a target decreases exponentially with the distance between the
target and the sensor, and this probability can also be altered by the
possible presence of obstacle between the target and the sensor. Instead
of considering the detection of target following paths, the study considers
that the sensors have to fully cover the region in which they are
deployed. The problem is to reach a desired average coverage as well as
to maximize the coverage of the most vulnerable points of the region.
Under these assumptions, they propose algorithms for placing sensors on
grid points to maximize the average or minimum detection probability
of a target that could be located at any grid point. An extension of that
study developed similar algorithm considering that part of the sensors
can fail [8]. Also, using the same model but assuming that the sensors
can move, an algorithm for finding the optimal motion of the sensors to
cover the region after being randomly deployed is developed in [17].
In [4], a model is developed that assumes that each sensor has a sensing
range in which it is guaranteed to detect any target. This is similar to
the probabilistic model developed in [9] assuming that the detection
probability of a target is 1 (resp. 0) whenever the distance between
the target and the sensor is less (resp. higher) than the sensing range.
Again, the goal of deployment is to fully cover the region of interest.
The study develops an algorithm based on integer linear programming
that minimizes the cost of sensors when requiring complete coverage of
the sensor field.
Target signal model
In [13], the authors model the signal intensity and assume it decays
as a power of the distance from the target to the sensor. The goal of
the deployment is to prevent targets from traversing a monitored region
without being detected. The measure of exposure of a path P is defined
as the total signal intensity emitted by the target moving through the
field following P and measured by the closest or all the sensors. The
smaller this signal intensity, the lesser the likelihood of detecting the
target, thus the coverage provided by a deployment is measured by the
minimum exposure when considering all possible paths across the region.
Model used in this chapter
Now, the model used for the remaining of this chapter is presented.
Sensor nodes with possibly di#erent sensing modalities are deployed over
a region R to perform target detection. Sensors measure signals at a
given sampling rate to produce time series that are processed by the
nodes. The nodes fuse the information obtained from every sensor accordingly
to the sensor type and location to provide an answer to a detection
query. The nodes are assumed to have the ability to communicate
to each other. However this work is not concerned with communication
issues and therefore the peer to peer communication among nodes is
Detecting unauthorized activities using a sensor network 5
assumed to be reliable through the use of appropriate communication
techniques [1, 14].
In this chapter, the sensor nodes are assumed to obtain a target energy
measurement every T seconds that accounts for the behavior of the
target during time T . The detection algorithm consists of exchanging
and fusing the energy values produced by the sensor nodes to obtain a
detection query answer.
A target at location u emits a signal which is measured by the sensors
deployed at locations s i , . The strength of the signal S
emitted by the target decays as a power k of the distance. Energy
measurements at a sensor are usually corrupted by noise. If N i denotes
the noise energy at sensor i during a particular measurement, then the
total energy measured by sensor i at location s i when the target is at
location u is given by
where K is the energy emitted by the target and ||u - s i || is the geometric
distance between the target and the sensor. Depending on the
environment the value k typically ranges from 2.0 to 5.0 [11].
Although any noise distribution can be chosen in this model, simulations
performed in this chapter makes the conservative assumption that
the signals measured by the sensors are corrupted by Gaussian noise.
Therefore, the noise energy has a Gaussian square distribution or chi-square
distribution of degree 1.
3. Detection algorithms
Using the energy model described in the previous section, the detection
probability of targets can be derived for a given detection algorithm
used by the sensors. This section develops two detection algorithms,
namely value and decision fusion, and evaluates their performance.
Algorithms
The algorithms considered are non parametric detection algorithms
that let the nodes share their information and use a fusion rule to arrive
at a decision. Di#erent fusion algorithms can be derived by varying
the size of the information shared between sensor nodes. Two cases are
explored: 1) value fusion where the nodes exchange their raw energy
measurements and 2) decision fusion where the nodes exchange local
detection decisions based on their energy measurement [6]. Both algorithms
are described in Figure 1.1.
Value Fusion Decision Fusion
at each node: at each node:
1. obtain energy from every node 1. obtain local decision from every node
2. compute average of values 2. compute average of local decisions
3. compare average to threshold
for final decision
3. compare average to threshold for final
decision

Figure

1.1. Value and decision fusion algorithms
Analytical evaluation of the algorithms performance
False alarm and detection probability are now derived for value and
decision fusion. The false alarm probability is the probability to conclude
that a target is present given that the target is absent. The detection
probability is the probability to conclude that a target is present given
that a target is actually present. False alarm and detection probability
are determined by the threshold defined in the algorithms, the noise
level, the target position and the sensor deployment.
Let N be the total number of sensors, # v and # d be the thresholds for
value and decision fusion, # be the second threshold for decision fusion,
and FA v,d and D v,d denote the false alarm and detection probabilities
of value and decision fusion. f X (x) is the probability density function
(pdf) of noise energy that is assume to be # 2
(chi-square with one degree
of freedom) [10]. FX (x) is the cumulative distribution function (cdf) of
noise x]). Furthermore, the noise at di#erent sensors
is assumed to be independent.
Value fusion. False alarms occur when the average of the N values
measured by the sensors is above the threshold # v in the absence of
target. The measured values contain only noise, and the false alarm
probability is given by:
degrees of freedom with a cumulative
distribution function F # 2
(x). Therefore equation 1.2 becomes:
Detections occur when the average of the N values measured by the
sensors is above the threshold # v in the presence of a target. The values
Detecting unauthorized activities using a sensor network 7
measured consist of energy (function of the distance from the target to
the sensor) plus noise, and the detection probability for a given position
of target u is given by:
For varying position of target, the average detection probability is
given by:
where #f(u)# denotes the average of f over di#erent positions u of the
target in the region considered.
Decision fusion. For decision fusion, false alarms occur when more
than #N sensors have a value above the threshold # d in the absence of
target, where # is the threshold used in step 3 of the decision fusion
algorithm. The probability that i sensors have a value above # d is (1 -
and the probability that the remaining N - i sensors have a
value below # d is FX (# d ) N-i . Since there are # N
of choosing the
sensors among N sensors, and i can vary from #N# to N for a false
alarm to occur, the false alarm probability is given by the following
Detections occur when i #N# sensors have a value above the
threshold # d in the presence of a target. For a given set of detecting
sensors defined by the permutation h (such that the set {h(j), 1 # j # i}
are the indices of detecting sensors), the probability of detection is
(see [5] for de-
tails). The detection probability for a given position of target is the
sum of these terms for di#erent combinations h and di#erent number of
detecting sensors (from #N# to N ). The detection probability is the
average of this expression over di#erent position u of the target in the
region:
Y
Y
FX (#d -E h(j) (u))
(1.
4. Exposure
This section proposes a probabilistic definition of exposure to evaluate
the quality of sensor deployments. A general formulation is first
developed. Then, several problems are formulated and solved to derive
the minimum exposure of sensor deployments for the various target
activities, variable speed targets, and sensor fields with obstacles.
Definition
The notion of path exposure introduced in the Section 1.2 measures
the ease of detecting a target traveling along a given path, which is
referred as "detecting the path". Therefore, the minimum exposure
when considering all possible paths in the region is a measure of the
quality of a deployment. The probabilistic exposure is now defined to
directly measure the likelihood of detecting a path.
Let P denote a path in the sensor field. A target that follows P is
detected if and only if it is detected at any time while it is on that path.
The exposure of path P is defined as the net probability of detecting a
target that travels along the path P . First, only the west-east unauthorized
traversal problem is addressed. The target is assumed to be
crossing the region from west to east following any path through the
sensor field. The problem is to find the path P with the least exposure.
Solution to the west-east unauthorized traversing
problem
Let P denote a path from the west to the east periphery through the
sensor field. Since detection attempts by the sensor network occur at
a fixed frequency, each detection attempt can be easily associated with
a point u # P when assuming that the target traverses the field at a
constant speed. The detection attempts are based on energy measured
over a period of time T during which the target is moving. There-
fore, the detection probability associated with each point u reflects the
measurements performed during time T . Considering the path, the net
probability of not detecting a target traversing the field using P is the
product of the probabilities of not detecting it at any point u # P .
These "point detection" probabilities depend on the algorithm used for
distributed detection. Algorithms presented in Section 1.3, namely value
or decision fusion can be used, and the corresponding detection probabilities
when a target is at position u are denoted as D v (u) and D d (u)
respectively. Closed form expressions for D v (u) and D d (u) can be found
in Section 1.3. To account for the movement of the target, the energy
Detecting unauthorized activities using a sensor network 9
used to compute D v (u(i)) and D d (u(i)) is the average energy measured
as the target travels from u(i - 1) to u(i). Note that other algorithms
for collaborative target detection can be used by the sensors. Finding
the exposure of a path requires knowing the detection probability D(u)
when the sensors collaborate to detect a target located at a given point
u in the region. If G(P ) denotes the net probability of not detecting a
target as it traverses through path P , then,
log G(P
u#P
log(1 -D(u)),
Since the exposure of P is (1 - G(P )), the problem is to find the path
which minimizes (1 - G(P )) or equivalently the path that minimizes
| log G(P )| (Note that, G(P ) lies between 0 and 1 and thus log G(P ) is
negative).
In general, the path P that minimizes | log G(P )| can be of fairly
arbitrary form. The proposed solution does not exactly compute this
path. Instead, it relies on the following approximation: the sensor field is
divided into a fine grid and the target is assumed to only move along this
grid. The problem then is to find the path P on this grid that minimizes
| log G(P )|. Clearly, the finer the grid the closer the approximation.
For the target not to be detected at any point u # P , it must not be
detected at any point u between two adjacent grid points of P . There-
fore, path P is divided as a chain of grid segments. Let v 1 and v 2 be
two adjacent points on the grid. Let l denote the line segment between
l denote the probability of not detecting a target
traveling between v 1 and v 2 on the line segment l. Then, from the
log
log(1 -D(u)), (1.8)
where D(u) is either D v (u) or D d (u) depending on whether the sensors
are using value or decision fusion. The probability m l can be evaluated
by finding the detection probability D(u) at each point u # l. Note that,
l lies between 0 and 1 and, therefore, log m l is negative.
To find the least exposed path, a non-negative weight equal to | log m l |
is assigned to each segment l on this grid. Also, a fictitious point a is
created and a line segment is added from a to each grid point on the
west periphery of the sensor field. A weight of 0 is assigned to each of
these line segments. Similarly, a fictitious point b is created and a line
segment is added from b to each grid point on the east periphery of the
sensor field and a weight of 0 is assigned to each of these line segments.
The problem of finding the least exposed path from west periphery
to east periphery is then equivalent to the problem of finding the least
1. Generate a suitably fine rectangular grid.
2. For each line segment l between adjacent grid points
3. Compute | log m l | using Equation 1.8
4. Assign l a weight equal to | log m l |
5. Endfor
6. Add a link from virtual point a to each grid point on the west
7. Add a link from virtual point b to each grid point on the east
8. Assign a weight of 0 to all the line segments from a and b
9. Find the least weight path from a to b using Dijkstra's algorithm
10. Let w equal the total weight of P .
11. Return P as the least exposure path with an exposure of 10 -w .

Figure

1.2. Pseudo-code of the proposed solution for the UT problem.
Fictitious Fictitious
Detection Probability of the
Point A Point B0.921.610.080.3544.90.801.361.053.4480.01.420.630.040.326.830.242.010.030.030.060.040.100.010.050.050.450.040.030.040.050.040.010.010.010.310.040.000.000.010.420.240.000.010.010.480.060.012.240.161.5443.41.060.041.180.073.450.200.740.330.050.050.060.020.010.020.030.070.050.010.010.000.060.520.030.010.000.020.490.020.010.010.010.280.250.010.001.120.2440.20.291.002.290.831.8944.91.050.530.390.121.360.270.530.490.931.130.060.970.040.43
Sensor
Edge Weight1.38

Figure

1.3. Illustration of the proposed solution for an example UT problem.
weight path from a to b on this grid. Such a path can be e#ciently
determined using the Dijkstra's shortest path algorithm [2]. A pseudo-code
of the overall algorithm is shown in Figure 1.2.
Example: Figure 1.3 shows a sensor field with eight sensors at locations
marked by dark circles. Assume the noise process at each sensor is
Additive White Gaussian with mean 0 and variance 1. Further assume
that the sensors use value fusion to arrive at a consensus decision. Then,
from Equation 1.3, a threshold is chosen to achieve a false alarm
probability of 0.187%. The field has been divided into a
The target emits an energy and the energy decay factor is 2.
Detecting unauthorized activities using a sensor network 11
The figure shows the weight assigned to each line segment in the grid as
described above. The least exposure path found by the Dijkstra's algorithm
for this weighted grid is highlighted. The probability of detecting
the target traversing the field using the highlighted path is 0.926.
Comparison of intensity and probabilistic exposure. The
probabilistic exposure defined here is similar to the intensity exposure
defined in [13]. In general, the higher the energy measured by the sensors
the higher the probability of detecting the target. Therefore, the
two metrics measure the same e#ect of energy decreasing with distance
from the target. However, a given total target signal energy measured
by the sensors as the target travels along a path can correspond to di#er-
ent probabilities of detecting the path depending on the energy profile
along the path. If one can derive the probability of detection of tar-
gets, the probabilistic exposure has the advantage to directly measure
the performance of the sensor deployment.
Nevertheless, according to the method for finding least exposed paths
developed in this section, probabilistic exposure remains limited in its
accuracy. Indeed, the method presented in this section relies on the
assumption that paths lie on a square grid and the grid size has to
be a multiple of the distance covered by a target in T seconds. The
method for finding intensity exposure developed in [13] proposes to use
higher order grids instead of the rectangular grid used here to improve
the accuracy of the measure. However such grids cannot be used to
derive probabilistic exposure because the grid size is not constant and
it is in general not a multiple of the distance covered by a target in T
seconds assuming targets travels at a constant speed. So far, the e#cient
method for determining minimum exposure across a region developed in
this section can only consider coarse approximations of the possible paths
because of the incompatibility of finer grids.
Exposure of di#erent target activities
In the previous subsection, the problem of finding the minimum exposure
of targets traversing the region from west to east is solved. Here,
other target activities are considered.
Unauthorized traversing problem. The problem is to find the
minimum exposure of targets that are expected to traverse the sensor
field from one side to the opposite side. Two cases need to be consid-
ered, namely west to east traversing, which is equivalent to traversing
from east to west, and north to south traversing, which is equivalent to
traversing from south to north.
Solution. A method to solve the west-east unauthorized traversal
problem was proposed in the previous subsection. A similar method
can be applied to find the least exposed path from north periphery to
the south periphery of the sensor field by connecting fictitious points
to the north and south peripheries. Also, if either of these activities is
expected, the minimum exposure is determined by finding the minimum
of the two exposures.
Unauthorized reaching problem. The problem is to find the
minimum exposure of targets that are expected to enter the sensor field
through any point of the periphery, reach a specific point of interest
in the region and then leave the sensor field through any point of the
periphery.
Solution. The least exposed path to reach the point of interest B
from the periphery can be found by connecting a fictitious point A to
all the grid points of the periphery with a segment weight of 0 and use
Dijkstra's shortest path algorithm to find the least weighted path from
A to B. That path only accounts for half of the target activity since
the target has to leave the region. However, the least exposed path for
leaving the region is the same as the least exposed path to enter the
region. If the exposure of the path to reach the point of interest is e in ,
then the total path exposure is given by 1 - (1 - e in ) 2 .
Unauthorized idling problem. For unauthorized idling activity,
the target is expected to remain at a fixed point u in the sensor field
and observe a point of interest for a given duration of T i # T so that it
is detectable for T i attempts by the sensors. Assuming a sensing range
model, the target is assumed to be able to observe the point of interest
only if it lies within a given distance d i to the point of interest.
Solution. The minimum exposure in this scenario is the minimum
of considering all the grid point positions u that
are less than d i away from the point of interest.
Algorithm complexity
The actual implementation of the algorithm of Figure 1.2 can be tailored
to reduce the complexity of finding the least exposed path. Considering
computation cost, computing the weight of each line segment
and finding the least exposed path using Dijkstra's algorithm are the
most expensive operations of the algorithm. Computing the weight for
an edge in the graph requires finding the distance from the edge to ev-
Detecting unauthorized activities using a sensor network 13
ery sensor. Actually, the energy associated with several points lying on
the edge is calculated and averaged to estimate the energy measured
by the sensors as a target travels along the edge. To account for the
presence of obstacles, it must be checked for every point if an obstacle
lies between the point and the sensor considered (as will be explained in
Section 1.4.0). Dijkstra's algorithm is an e#cient minimum weight path
search algorithm with complexity O(mlogn) where m is the number of
edges and n the number of vertices in the graph.
When specifying a source vertex v, Dijkstra's algorithm finds the minimum
distance from every other vertex in the graph. When searching for
the least exposed path traversing a region from west to east, Dijkstra's
algorithm can be stopped as soon as a vertex on the east side of the region
is reached. Therefore, not all the vertices need to be visited by the
algorithm to find the minimum weight path in general. A consequence
of this observation is that Dijkstra's algorithm does not need to know
all the segment weights initially to find the shortest path between two
points. Therefore, the computation cost can be reduced by computing
the segment weights dynamically, as needed by the Dijkstra's algorithm.
Simulations show that 50% to 80% of the weights need to be computed
when finding the least exposed path for traversing activity, while 20%
to 45% of the weights need to be computed for reaching activity. These
results vary with the number of sensors deployed, the energy level of the
signal emitted by the target and the size of the region.
Exposure of variable speed targets
The method proposed above to solve the unauthorized traversing
problem assumed that targets cross the region at a constant speed. That
assumption is not valid in many applications, for example when the targets
are vehicles driving on a road. Below, a method for determining
the minimum exposure of variable speed targets is developed.
Problem formulation. Assume that the target can travel with
variable speed v, v min # v # v max . Traveling at a faster speed reduces
the amount of time the target spends crossing the region and therefore
reduces the number of times the sensors have to detect the target. If the
energy emitted by the target is independent of the velocity of the target,
it can be argued that the least exposed path is obtained when the target
travels at maximum speed. However, the energy emitted by the target is
expected to be an increasing function of its speed. Thus, as the energy
emitted by the target increases, the probability that the sensors detect
the target increases and the exposure of the target increases. Therefore,
there is a tradeo# between detectability and speed when considering the
speed of the target. This tradeo# depends on the energy model as a
function of the speed and the sensors topology. In general, the speed
along the least exposed path is not expected to be constant.
Multiple speed solution. In order to find the least exposed
path across the region, the variable speed problem is transformed into
a multiple speed problem. The target is assumed to be traveling at
discrete speeds v i , Note that this approximation can be
made arbitrarily fine by increasing the number of speeds, I, to achieve
desired accuracy. For speed v i , the region can be divided into a grid
with grid size so that each segment corresponds to a detection
attempt by the sensors. The solution consists in constructing a graph
with all vertices on a fine grid and the edges connecting vertices that
are apart from each other. Let the speeds considered be
are integers and v 0 is a unit speed. Note that this is
possible in general by making v 0 small and v 0 defines the granularity of
speeds for all practical purposes. Let p 0 be the greatest common divider
of I and let the grid size be so that all the
points of the grid can be reached (except certain points close to the
region boundaries). Each grid point is connected to other grid points
that are p i away and each edge is given a weight of value | log(1 -D(u))|
where the detection probability D(u) depends on the energy emitted
by the target on the segment, and therefore on the target speed. Note
that it is assumed that, during a period T , the target travels in one
direction only (east, west, north or south). This assumption simplifies
the problem by reducing the number of edges in the graph. Once the
graph is constructed, the least exposed path is found using the same
approach as in the constant speed problem. The higher the number of
speeds, I, considered, the higher the complexity of building the graph
and finding the shortest path.
Demonstration. A simulator implementing the algorithm described
in the previous section was developed to solve the problem for
variable number of sensors, speeds and target energies.
The simulator assumes that value fusion is used for collaboration
among the sensors and the threshold of value fusion can be chosen to obtain
a desired false alarm probability for each detection attempt [7]. For
the simulation performed, it was assumed that the detection attempts
occur every seconds and the false alarm probability is chosen so
that the expected number of false alarms is one per hour. The energy
emitted by the target, i.e. coe#cient K in Equation 1.1, was assumed
proportional to the square root of the speed. This assumption used in
Detecting unauthorized activities using a sensor network 15
region monitored
deployment region
nodes
lep west-east
segment number
speed
factor

Figure

1.4. Shape and speed profile of the least exposed path (lep) through a region
with 25 sensors and for speeds
the experiment can be easily replaced if one knows the characteristics
of the target that is expected to cross the region. An example of least
exposed path through a region of size 20 - 20 with 25 sensors deployed
is shown in Figure 1.4. Both the shape and the speed profile of the least
exposed path are presented. In that example, the target is assumed to
have three di#erent possible speeds,
and the energy parameters are set to
(decay coe#cient). The minimum exposure was found to be 36%.
The example in Figure 1.4 exhibits a general trend of least exposed paths
that was observed throughout simulations: the least exposed path corresponds
to high speeds when the target crosses parts of the region with
low sensor density and low speed when it crosses parts of the region
with high sensor density. The proximity of sensors to the path make
high speed targets (i.e. high energy) easy to detect.
To compare the multi-speed results with constant speed results, the
minimum exposure was found for the same sensor deployment as in Figure
1.4 but when assuming the target can only travel at a constant
speed . The minimum exposures found
are respectively 38%, 49% and 64%. It is expected that the minimum
exposure for constant speed targets is greater than for multiple speeds
because constant speed paths are a special case of the multiple speed
problem. Another observation made during the simulation is that the
least exposed path can be substantially di#erent in shape when considering
variable or constant speed. Figure 1.5 shows the least exposed path
for a target traveling at constant speed which is di#erent from
the least exposed path for variable speed shown in Figure 1.4.
region monitored
deployment region
nodes
lep west-east

Figure

1.5. Least exposed path (lep) for constant speed 2.
Minimum exposure in the presence of obstacles
Problem formulation in the presence of obstacles. The presence
of obstacles in the sensor field impacts the minimum exposure in
two ways. First, the obstacles modify the propagation of the signal emitted
by the target and this is modeled by a coe#cient # i in the equation
for the energy measured by each node (S i
). Second, the
obstacles are assumed to completely obstruct the motion of the target,
i.e., paths intersecting the obstacles need not be considered. The coe#-
cients # i are dependent on the nature, size and position of the obstacles
in the sensor field. It is assumed that an array is given that specifies the
values of # i for each sensor and for every possible position of the target.
It is also assumed that the position and size of the obstacles is given so
that only paths not intersecting the obstacles are considered.
The solution consists of modifying the energy measured by the sensor
with the obstacle coe#cient # i and ignoring the paths that cross over
obstacles. The general methods developed to find the least exposed path
for each target activity remain unchanged.

Figure

1.6 shows the same node deployment as in figure ?? with five
obstacles present in the region. Obstacles are assumed to have a circular
shape of radius 1 and the obstacle coe#cients # i associated with a node
at position s i when a target is present at grid point u is set as follows:
whenever the line (s i , u) intersects with the obstacle, #
whenever the distance between the line (s i , u) and the obstacle is more
Detecting unauthorized activities using a sensor network 17
region monitored
deployment region
nodes
obstacles
lep west-east

Figure

1.6. Least exposed paths (lep) for traversing the region horizontally (mini-
mum exposure=.84) with nodes deployed and 5 obstacles.
than twice the radius of the obstacle, and 0 < # i < 1 and grows linearly
with the distance between the line (s i , u) and the obstacle. Comparing

Figure

1.6 with Figure ?? shows that the least exposed path for east-west
traversal changes when obstacles are present in the region. In this
example, the minimum exposure decreases from .87 to .84 due to the
fact that some path segments are hidden from some sensors. It is also
possible that the minimum exposure increases when obstacles are added
in the region as shown in Figure 1.7. This is due to extra constraints
added by the presence of obstacles that prevent targets from using some
paths across the region since targets are assumed not to be able to cross
over the obstacles. In the example of Figure 1.7, the least exposed
path for east-west traversal identified in Figure ?? is not a valid path
in the presence of an obstacle on that path. As a result, the exposure
of the least exposed path increases from .87 to .93 for the same node
deployment.
5. Deployment
In this section, the problem of sensor deployment for unauthorized
traversal detection is formulated and solutions are identified.
Problem formulation
Consider a region to be monitored for unauthorized traversal using a
sensor network. The energy level K emitted by a target of interest and
region monitored
deployment region
nodes
obstacles
lep west-east

Figure

1.7. Least exposed paths (lep) for traversing the region horizontally (mini-
mum exposure=.93) with nodes deployed and 5 obstacles.
the noise statistics in the region are known. The sensors are to be deployed
over the region in a random fashion where the sensors locations in
the region cannot be determined a priori and only the number or density
of sensors can be chosen. The problem is to find a deployment strategy
that results in a desired performance level in unauthorized traversal
monitoring of the region.
The performance is measured by the false alarm probability and the
path exposure defined in Section 1.4. The false alarm probability is assumed
to be fixed in this study so that the problem consists of maximizing
the exposure at constant false alarm rate. Since targets can traverse
the region through any path, the goal of deployment is to maximize the
exposure of the least exposed path in the region.
In most cases, the minimum exposure in the region increases (if false
alarm rate is kept constant) as more sensors are deployed in the region
[5]. However, since the deployment is random, there are no guarantees
that the desired exposure level is achieved with a given number of
sensors. A study of the statistical distribution of exposure for varying
sensor placement for a given number of sensors can provide a confidence
level that the desired detection level is achieved. In practical situations,
only a limited number of sensors are available for deployment and only a
limited detection level with associated confidence level is achievable for
a fixed false alarm rate.
Detecting unauthorized activities using a sensor network 19
Solution
Based on the above discussion, a solution method is developed to solve
the deployment problem when a maximum of M sensors can be used.
Deploying the M sensors results in the maximum achievable detection
level but this is not optimal when considering the cost of sensors. To
reduce the number of sensors deployed, only part of the available sensors
should be deployed first and the sensors can then report their position.
The random sensor placement obtained can be analyzed to determine
if it satisfies the desired performance level. If it does not, additional
sensors can be deployed until the desired exposure level is reached or
until all M available sensors are deployed.
The number of sensors used in this strategy can be minimized by
deploying one sensor at a time. However, a cost is usually associated
with each deployment of sensors and deploying one sensor at a time may
not be most cost e#ective if the cost of deployment is su#ciently large
with respect to the cost of single sensors. By assigning distinct costs to
both single sensors and deployment, the optimal number of sensors to
be deployed at first and thereafter can be determined. Below, analytical
expressions are developed for finding the optimal solution. In general,
the optimal cost solution is neither deploying one sensor at a time nor
deploying all the sensors at once.
Analytical solution
Let e d be the desired minimum exposure for the sensor network to be
deployed when a maximum of M sensors are available for deployment.
The position of sensors are random in the region of interest R and for
a given number of sensors n, the least exposure e is a random variable.
Let F n (x) denote the cumulative distribution function of e, i.e. the
probability that e is less than x, when n sensors are deployed.
As the minimum exposure e is a random variable, the cost of deploying
the sensors in steps until the desired exposure is reached is also a
random variable C. The expression for the expected value of C is now
derived. To evaluate the probability that the exposure e d is reached after
additional sensor deployment, the following approximation is made:
the distribution of exposure for n sensors is independent of the exposure
corresponding to k of these n sensors, 1 # k # n- 1. Let n i be the total
number of sensors deployed after step i. Let S be the maximum number
of steps so that n . Note that n i - n i-1 is the number of sensors
deployed at step i. Also let C d be the cost of deploying the sensors at
each step and C s be the cost of each sensor. If the desired exposure is
obtained after the first step, the total cost of deployment is C d
and this event happens with probability 1-F n 1
Considering all the
possible events, the expected cost is given by
Note that a di#erent expression is needed for the cost of step S since
no additional sensors are deployed after this step even when the desired
exposure is not achieved.
Simulation
This section presents results of simulations that were performed to
collect the exposure distribution function of the number of sensors deployed

Method. The exposure distribution is obtained by collecting statistics
on the exposure when deploying sensors randomly in a predefined
region. The region monitored is of size 20 - 20 and the random deployment
is assumed to be Gaussian, centered at the center of the region
monitored and with standard deviation 10. In the simulation conducted,
the deployment region has dimensions 33% larger than the monitored
region, i.e. size 26.6 - 26.6.
For every deployment, the minimum exposure is found using a simulator
implementing the algorithm presented in Section 1.4. A decay
factor of maximum energy of are chosen to model
the energy emitted by targets (cf Equation 1.1). The sensors use value
fusion to collaborate when making a common decision on the presence
of a target in the region. The noise # N
in the sum of energies from
sensors, computed in value fusion and appearing in Equation 1.4, is
from a Chi-square distribution with N degrees of freedom. The threshold
for detection is chosen as a function of the number of sensors to give
a constant false alarm probability. The false alarm probability for each
detection attempt is chosen so that the expected number of false alarms
is one per hour, assuming that detection attempts occur every 2 seconds.
Distribution of minimum exposure. The distribution of minimum
exposure were found for the number of sensor deployed varying
from 1 to 100. To illustrate the results, the probability density functions
for 15, sensors are shown in Figure 1.8.
Detecting unauthorized activities using a sensor network 21
sensors
Minimum exposure
Density
sensors
Minimum exposure
Density
50 sensors
Minimum exposure
Density

Figure

1.8. Probability density function for the distribution of minimum exposure
for deployments of 15, sensors.
1000.10.30.50.70.9Number of sensors
P(minimum
exposure>e d
e d
=80%
e d
=85%
e d
=90%
e d =95%

Figure

1.9. Probability that the minimum exposure is above ed for varying number
of sensors and ed=80%,85%,90% and 95%.
Cost for Cd=0 and Cs=1
Expected
cost
10080120160200Cost for Cd=5 and Cs=1
Expected
cost
100100300500700Cost for Cd=100 and Cs=1
Expected
cost

Figure

1.10. Expected cost of achieving minimum exposure of 90% as function of
the number of sensors for three di#erent cost assignments.
For sensors deployed, the minimum exposure has zero density for
values less than the false alarm probability of .02. The highest density
is obtained for values around .08 and then drops exponentially towards
zero for higher values of exposure. For deployment of 30 sensors, the
minimum exposure has zero density for values below .02, then increases
and has the shape of a bell curve centered around .4. For deployment of
50 sensors, densities start at zero for small values and remain very small
for most values of minimum exposure. The density slowly increases and
has a large peak for minimum exposure of 1.
As expected, the minimum exposure increases on average as the number
of sensors deployed increases. When randomly deploying 15 sensors,
it is very unlikely to obtain a placement providing a desirable minimum
exposure. When deploying sensors, most of the exposure levels are
equally likely and only poor confidence is given to obtain a desirable exposure
level. When deploying 50 sensors, it is very likely that the sensor
placement will give good exposure and this likelihood keeps increasing
with the number of sensors deployed.
The cumulative distribution function obtained from the statistics collected
was used to evaluate the likelihood that the desired level of exposure
e d is obtained for varying number of sensors. The graph of Figure
1.9 shows the probability that the minimum exposure is above e d
as a function of the number of sensors deployed for e
and 95%. These values can be used to evaluate the cost expressed in
Equation 1.9. The graph shows that the confidence level to obtain a
given minimum exposure level e d increases with the number of sensors
deployed. The confidence for e d when deploying 100 sensors is above
.999, which is su#cient for most applications, and therefore the distri-
Detecting unauthorized activities using a sensor network 23
bution of exposure was not evaluated when deploying more than 100
sensors.
Results
The expected cost of deploying sensors is now evaluated using the
simulation results and assuming that the number of sensors deployed at
every step is constant so that n i - n S. The
expected cost as a function of n was evaluated for three di#erent cost
assignments with a desired exposure of e 90%. The three corresponding
graphs are shown in Figure 1.10. The first cost assignment is
so that the expected cost is the expected number of
sensors to be used to achieve an exposure of 90%. Since C the
number of steps used to deploy the sensors doesn't a#ect the cost and it
is therefore optimal to deploy one sensor at a time until the minimum
exposure e d is reached, as shown on the graph. Overall, the expected
number of sensor to be deployed increases with n but there is a local
minimum for that can be explained by the following analysis.
The expected number of sensors is a weighted sum of i.n, 1 # i # S that
are the di#erent number of sensors than can be deployed at a time when
deploying n sensors at each step. For n around 50, the probability that
the minimum exposure is above e d varies a lot as shown in Figure 1.9
and the weight associated with the first term of the sum (n) increases
rapidly while the weights associated with higher number of sensors de-
crease. This is the cause of the local minimum and the cost starts to
increase again when the increase in n compensates for the decrease in
weights. In other words, the probability to achieve the desired exposure
is much higher when deploying sensors randomly than when deploying
sensors randomly. Therefore, it is less costly to deploy 55 sensors
at every step since one deployment is likely to be su#cient whereas two
or more deployments, and thus a total of 80 or more sensors, are most
likely to be needed when deploying 40 sensors at every step.
The second cost assignment is (C so that the cost of a
deployment is equal to the cost of five sensors (note that only the relative
cost of C d /C s determines the shape of the graphs). In this case,
deploying one sensor at a time is prohibited by the cost of deployment
and the optimal number of sensors to deploy at every step is 22. Again,
the curve presents a local minimum for that is due to the variations
in weights. The last cost assignment is (C
the minimum cost is achieved when deploying sensors at every step.
These results are specific to the region and the parameters characterizing
the signal emitted by the target that were chosen for the simulation.
Similar results can be derived for other parameters, most of the e#ort
residing in finding the exposure distributions through simulation.
6. Conclusion
This chapter addressed the problem of sensor deployment in a region
to be monitored for target intrusion. Several models for target detection
were presented with corresponding problem formulations. For a model
considering target energy, algorithms for sensor collaboration to perform
target detection were proposed. False alarm and detection probability of
these algorithms were derived. The chapter then proposed a probabilistic
definition of path exposure that measures the likelihood for a target to
be detected as it travels along a path. The minimum exposure is used as
a measure of the quality of deployment to detect a given target activity,
the goal being to maximize the exposure of the least exposed path in
the region.
A Method was developed to evaluate the exposure of paths in the
region. Also, algorithms for determining the least exposed path in a
region are proposed for di#erent target activities, targets with variable
speed and when obstacles are present in the monitored region. In the
case where sensors are randomly placed in a region to be monitored, a
mechanism for sequential deployment in steps is developed. The strategy
consists of deploying a limited number of sensors at a time until
the desired minimum exposure is achieved. The cost function used in
this study depends on the number of sensors deployed in each step and
the cost of each deployment. Through simulation, the distribution of
minimum exposure obtained by random deployment was evaluated for
varying number of sensors deployed. These results were used to evaluate
the cost of deployment for varying number of sensors deployed in each
step.



--R

"A survey on sensor networks,"
Computer algorithms: Introduction to design and analysis
Fundamentals and Applications with Software
"Grid coverage for surveillance and target location in distributed sensor networks,"
"Deployment of fault-tolerant sensor networks for target detection,"
"Value-Fusion versus Decision-Fusion for Fault-tolerance in Collaborative Target Detection in Sensor Networks,"
"Fault tolerance in collaborative sensor networks for target detection,"
"A fault-tolerant approach to sensor deployment in distributed sensor networks,"
"Sensor placement for e#ective grid coverage and surveillance,"
Probability and Random Processes
"Empirical formula for propagation loss in land mobile radio services,"
"Coverage problems in wireless ad-hoc sensor networks,"
"Ex- posure in wireless ad-hoc sensor networks,"
"Survey on sensor networks,"
Sensor Information Technology Website
Distributed Detection and Data Fusion
"A practical sensor deployment strategy based on virtual forces,"
--TR
Multi-sensor fusion
Exposure in wireless Ad-Hoc sensor networks
Distributed Detection and Data Fusion
Computer Algorithms
Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks
Fault Tolerance in Collaborative Sensor Networks for Target Detection
Deployment of fault tolerant sensor networks for target detection
exposure;sensor networks;deployment;collaborative target detection;value fusion