Sensor Deployment Strategy for Target Detection  Thomas Clouqueur, Veradej Phipatanasuphorn, Parameswaran Ramanathan and  Kewal K. Saluja  University of Wisconsin-Madison  1415 Engineering Drive  Madison, WI 53706  clouqueu@ece.wisc.edu  ABSTRACT  In order to monitor a region for traffic traversal, sensors  can be deployed to perform collaborative target detection.  Such a sensor network achieves a certain level of detection  performance with an associated cost of deployment. This  paper addresses this problem by proposing path exposure  as a measure of the goodness of a deployment and presents  an approach for sequential deployment in steps. It illustrates  that the cost of deployment can be minimized to achieve the  desired detection performance by appropriately choosing the  number of sensors deployed in each step.  Categories and Subject Descriptors  C.2.4 [Computer-Communication Networks]: Distributed  Systems-distributed applications; C.3 [Special-purpose  and Application-based Systems]: [signal processing   systems]    1. INTRODUCTION  Recent advances in computing hardware and software are  responsible for the emergence of sensor networks capable of  observing the environment, processing the data and making  decisions based on the observations. 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, traffic, agriculture or civil infrastructures [6]. The  deployment of sensor networks varies with the application  considered. It can be predetermined when the environment  is sufficiently known and under control, in which case the  sensors can be strategically hand placed. The deployment  can also be a priori undetermined when the environment is  unknown or hostile in which case the sensors may be   airdropped from an aircraft or deployed by other means,   generally resulting in a random placement.  This paper investigates deployment strategies for sensor  networks performing target detection over a region of   interest. In order to detect a target moving through the region,  sensors have to make local observations of the environment  and collaborate to produce a global decision that reflects the  status of the region covered [2]. This collaboration requires  local processing of the observations, communication between  different nodes, and information fusion [7]. Since the local  observations made by the sensors depend on their position,  the performance of the detection algorithm is a function of  the deployment. One possible measure of the goodness of  deployment for target detection is called path exposure. It is  a measure of the likelihood of detecting a target traversing  the region using a given path. The higher the path   exposure, the better the deployment. The set of paths to be  considered may be constrained by the environment. For   example, if the target is expected to be following a road, only  the paths consisting of the roads need to be considered.  In this study, 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 focus of this paper is to determine the  number of sensors to be deployed to carry out target   detection in a region of interest. The tradeoffs lie between the  network performance, the cost of the sensors deployed, and  the cost of deploying the sensors. This paper is organized  as follows. In section 2, a definition for path exposure is  proposed and a method to evaluate the exposure of a given  path is developed. In section 3, the problem of random   deployment is formulated and several solutions are presented.  An analytical study of these solutions is given in section 4  and section 5 presents simulation results that are used in  section 6 to determine the optimum solution for a given   environment. The paper concludes with section 7.  2. PATH EXPOSURE  In this section, a model for sensor network target detection  is proposed, a definition of path exposure is presented and  expressions for evaluating this path exposure are developed.  2.1 Model  Consider a rectangular sensor field with n sensors   de42  ployed at locations si, i = 1, . . . , n. A target at location  u emits a signal which is measured by the sensors. The   signal from the target decays as a polynomial of the distance.  If the decay coefficient is k, the signal energy of a target at  location u measured by the sensor at si is given by  Si(u) =  K  ||u − si||k  (1)  where K is the energy emitted by the target and ||u − si||  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 [4].  Energy measurements at a sensor are usually corrupted  by noise. If Ni denotes the noise energy at sensor i during a  particular measurement, then the total energy measured at  sensor i, when the target is at location u, is  Ei(u) = Si(u) + Ni =  K  ||u − si||k  + Ni.  The sensors collaborate to arrive at a consensus decision as  to whether a target is present in the region. We consider two  basic approaches for reaching this consensus: Value fusion  and Decision fusion [3]. In value fusion, one of the sensors  gathers the energy measurements from the other sensors,  totals up the energy and compares the sum to a threshold  to decide whether a target is present. If the sum exceeds  the threshold, then the consensus decision is that a target  is present. In contrast, in decision fusion, each individual  sensor compares its energy measurement to a threshold to  arrive at a local decision as to whether a target is present.  The local decisions (1 for target present and 0 otherwise)  from the sensors are totaled at a sensor and the sum is   compared to another threshold to arrive at the consensus   decision. In some situations, value fusion outperforms decision  fusion and vice versa.  2.1.1 Value Fusion.  The probability of consensus target detection when the  target is at location u is  Dv(u) = Prob  n  i=1  K  ||u − si||k  + Ni ≥ η  = Prob  n  i=1  Ni ≥ η −  n  i=1  K  ||u − si||k  ,  where η is the value fusion threshold. If the noise processes  at the sensors are independent, then the probability density  function of n  i=1 Ni equals the convolution of the   probability density function of Ni, i = 1, . . . , n. In particular, if  the noise process at each sensor is Additive White Gaussian  Noise (AWGN), then n  i=1 Ni has a Chi-square distribution  of degree n.  Due to the presence of noise, the sensors may incorrectly  decide that a target is present even though there is no   target in the field. The probability of a consensus false target  detection is  Fv = Prob  n  i=1  Ni ≥ η . (2)  As above, if the noise processes at the sensors are   independent and AWGN, then the false alarm probability can be  computed from the Chi-square distribution of degree n.  2.1.2 Decision Fusion.  For decision fusion, the probability of consensus target  detection when the target is located at u is  Dd(u) = Prob  n  i=1  hd,i(u) ≥ η2  =  n  j=η2  n  j  · P1  j  · P0  (n−j)  where  P1 = Prob [hd,i(u) = 1]  = Prob Ni ≥ η1 −  K  ||u − si||k  and  P0 = Prob [hd,i(u) = 0]  = 1 − Prob [hd,i(u) = 1] .  can be computed from Chi-square distribution of degree 1  for AWGN noise process.  The probability of false target detection at sensor i is  Prob[gd,i = 1] = Prob[Ni ≥ η1] and  Prob[gd,i = 0] = 1 − Prob[gd,i = 1].  Therefore, the probability of consensus false target detection  is  Fd = Prob  n  i=1  gd,i ≥ η2  =  n  j=η2  n  j  · (Prob [gd,i = 1])j  · (Prob [gd,i = 0])(n−j)  The above equations serve as an analytic basis for   evaluating exposure as defined in the following subsection.  Note that in value and decision fusion the knowledge of the  sensors location can be used to make the detection decision.  For example, a sensor can report values that differ   substantially from its neighbors values. This discrepancy can be  analyzed to avoid false alarms or misses and therefore   improve the detection performance. However, such algorithms  are not considered in this paper.  2.2 De£nition of exposure  We define exposure to be the probability of detecting the  target or an intruder carrying out the unauthorized activity,  where the activity depends on the problem under   consideration. In this paper, the activity considered is the   Unauthorized Traversal (UT) as defined below.  Unauthorized Traversal (UT) Problem: We are given  a sensor field with n sensors at locations s1, s2, . . . , sn (see  Figure 1). We are also given the stochastic characterization  of the noise at each sensor and a tolerable bound, α, on the  false alarm probability. Let P denote a path from the west to  the east periphery of the sensor field. A target traversing the  sensor field using path P is detected if it is detected at some  point u ∈ P. The exposure of path P is the net probability  of detecting a target that traverses the field using P. The  target is assumed to be able to follow any path through the  field and the problem is to find the path P with the least  exposure.  43  Sensor  Figure 1: Example sensor fields for UT problem.  2.3 Solution to the UT problem  Let P denote a path from the west to the east   periphery through the sensor field. A target that traverses the  field using P is not detected if and only if it is not detected  at any time while it is on that path. Since detection   attempts by the sensor network occur at a fixed frequency, we  can associate each detection attempt 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. Therefore, 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 no detection at each point u ∈ P.  That is, if G(P) denotes the net probability of not detecting  a target as it traverses over path P, then,  log G(P) =  u∈P  log(1 − D(u))du,  where D(u) is either Dv(u) of Dd(u) depending on whether  the sensors use value or decision fusion to arrive at a   consensus decision. 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)|1  .  In general, the path P that minimizes | log G(P)| can be  fairly arbitrary in shape. The proposed solution does not  exactly compute this path. Instead, we rely on the following  approximation. We first divide the sensor field into a fine  grid and then assume that the target only moves along this  grid. The problem then is to find the path P on this grid  that minimizes | log G(P)|. Note that, the finer the grid the  closer the approximation. Also, one can use higher order  grids such as in [5] instead of the rectangular grid we use  in this paper. The higher order grids change the runtime  of the algorithm but the approach is the same as with the  rectangular grid.  For the target not to be detected at any point u ∈ P,  1  Note that, G(P) lies between 0 and 1 and thus log G(P) is  negative.  1. Generate a suitably fine rectangular grid.  2. For each line segment l between adjacent grid points  3. Compute | log ml| using Equation 3  4. Assign l a weight equal to | log ml|  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. Compute the least weight path P 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 equal to 10−w  .  Figure 2: Pseudo-code of the proposed solution for  the UT problem.  it need not be detected at any point u lying between any  two adjacent grid points of P. We therefore subdivide any  path P as a chain of grid segments. Let us consider two  adjacent points, say v1 and v2 on the grid. Let l denote  the line segment between v1 and v2. Also, let ml denote  the probability of not detecting a target traveling between  v1 and v2 on the line segment l. Then, from the discussion  above,  log ml =  u∈l  log(1 − D(u))du (3)  The probability ml can be evaluated by finding the detection  probability D(u) at each point u ∈ l. Note that, ml lies  between 0 and 1 and, therefore, log ml is negative.  To find the least exposed path, a non-negative weight  equal to | log ml| 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 equal to 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. A weight equal to 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 weight path from a to b on this grid. Such  a path can be efficiently determined using the Dijkstra"s  shortest path algorithm [1]. A pseudo-code of the overall  algorithm is shown in Figure 2.  Example: Figure 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 2, we chose a threshold η = 3.0 to achieve a false alarm  probability of 0.187%. The field has been divided into a  10 × 10 grid. The target emits an energy K = 12 and the  energy decay factor is 2. 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   de44  Fictitious Fictitious  Threshold = 3.0, Detection Probability of the Path = 0.926  Point A Point B0.090.921.651.610.860.08  0.860.355.1744.9  0.03  0.800.821.3640.5  1.051.503.4442.580.041.41.420.17  0.63  3.36  0.04  1.48  0.323.596.833.600.240.11  2.01  1.88  0.030.030.030.050.060.070.040.020.100.03  0.010.010.050.060.05  0.540.45  0.050.040.020.03  1.14  0.040.020.050.070.040.020.010.02  0.010.010.010.040.31  0.05  0.040.010.000.01  0.000.010.010.220.420.440.240.020.000.00  0.010.010.010.050.480.490.060.010.010.01  2.24  3.00  0.16  0.12  1.54  43.4  43.4  2.69  1.06  0.98  0.040.01  1.18  0.06  0.07  0.21  3.45  3.44  0.20  0.14  0.74  0.31  0.33  0.09  0.05  0.02  0.05  0.06  0.06  0.06  0.02  0.02  0.01  0.01  0.02  0.04  0.03  0.04  0.07  0.03  0.05  0.04  0.01  0.01  0.01  0.01  0.00  0.02  0.06  0.32  0.52  0.02  0.03  0.01  0.01  0.01  0.00  0.00  0.02  0.25  0.49  0.24  0.02  0.01  0.01  0.00  0.01  0.00  0.01  0.02  0.28  0.65  0.25  0.02  0.01  0.01  0.00  0.89  1.12  0.85  0.24  1.60  40.2  5.01  0.29  0.25  1.00  0.65  2.29  2.55  0.83  0.17  1.89  80.0  44.9  2.75  1.05  1.32  0.53  0.850.390.190.120.361.361.210.270.610.53  0.07  0.49  0.19  0.93  1.89  1.13  0.16  0.06  0.17  0.97  1.26  0.04  1.10  0.43  Sensor  0.00 Edge Weight  0.05  1.38  Figure 3: Illustration of the proposed solution for an example UT problem.  tecting the target traversing the field using the highlighted  path is 0.926.  3. DEPLOYMENT  In this section, the problem of sensor deployment for   unauthorized traversal detection is formulated and solutions are  identified.  3.1 Problem formulation  Consider a region to be monitored for unauthorized   traversal using a sensor network. The target to traverse the sensor  field emits a given energy level K and the stochastic of the  noise in the region is known. The sensors are to be deployed  over the region in a random fashion where the sensors   locations in the region are a priori undetermined 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.  This performance is measured by the false alarm   probability and the path exposure defined in section 2. The false  alarm probability does not depend on the sensor placement  and is only determined by the number of sensors deployed  and the thresholds used in the detection algorithms. It 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.  Obviously, the minimum exposure in the region increases  (if false alarm rate is kept constant) as more sensors are  deployed in the region. However, since the deployment is  random, there are no guarantees that the desired exposure  level is achieved for a given number of sensors. Indeed some  sensor placements can result in very poor detection ability,  in particular when the sensors are all deployed in the same  vicinity. 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  at a given false alarm rate.  3.2 Solution  Based on the above discussion, we develop a solution method  to the deployment problem when a maximum of M sensors  can be used. Deploying the M sensors results in the   maximum achievable detection level but is not optimal when  considering the cost of sensors. To reduce the number of  sensors deployed, only part of the available sensors can 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 the 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 cost effective if the  cost of deployment is sufficiently large with respect to the  cost of single sensors. By assigning a cost to both single   sensors and deployment, the optimal number of sensors to be  deployed at first and thereafter can be determined. In the  next section, we develop analytical expressions 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 a time.  4. ANALYTICAL SOLUTION  In this section, we derive an analytical model for the cost  of deployment. Let ed 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   num45  0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1  0  0.05  0.1  0.15  0.2  Minimum exposure  Density  0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1  0  0.01  0.02  0.03  0.04  Minimum exposure  Density  0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1  0  0.1  0.2  0.3  0.4  Minimum exposure  Density  5 sensors  10 sensors  15 sensors  Figure 4: Probability density function for the   distribution of minimum exposure for deployments of  5, 10 and 15 sensors.  ber of sensors n, the least exposure e is a random variable.  Let Fn(x) denote the cumulative distribution function of e,  that is the probability that e is less than x, when n sensors  are deployed.  As mentioned in the previous section, there is no a priori  guarantee that the exposure ed will be obtained when   deploying the sensors. If M is the maximum number of sensors  available, the confidence of obtaining a least exposure of ed  or more is 1−FM (ed). For the proposed solution, we assume  that the position of the sensors obtained after a deployment  is known so that additional sensors can be deployed if the  minimum exposure ed is not reached. To evaluate the   probability that the exposure ed is reached after additional sensor  deployment, we make the following approximation: the   distribution of exposure for n sensors is independent of the   exposure corresponding to k of these n sensors, 1 ≤ k ≤ n − 1.  This is an approximation since the exposure obtained with  n sensors is always higher than the exposure obtained with  only k of these n sensors, 1 ≤ k ≤ n − 1. We observed  that the re-deployment of just a few sensors can   substantially modify the coverage of the region, for example when  filling empty spaces. The approximation is also justified by  the loose relation between exposure and sensors positions.  Indeed, a given minimum exposure can correspond to many  different deployment positions, some of which can be easily  improved by deploying a few additional sensors (e.g. when  there is a empty space in the region coverage), some of which  can only be improved by deploying many additional sensors  (e.g. when the sensors are evenly distributed on the region).  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. We now derive the  expression for the expected value of C. Let ni be the total  number of sensors deployed after each step i for a maximum  number of steps S so that nS = M. Note that ni − ni−1  is the number of sensors deployed at step i. Also let Cd be  the cost of deploying the sensors at each step and Cs be the  cost of each sensor. If the desired exposure is obtained after  the first step, the cost of deployment is Cd + n1Cs, and this  0 5 10 15 20 25 30 35 40  0  0.1  0.2  0.3  0.4  0.5  0.6  0.7  0.8  0.9  1  Number of sensors  Probability  ed  =95%  ed  =90%  ed  =85%  ed  =80%  Figure 5: Probability that the minimum   exposure is above ed for varying number of sensors and  ed=80%,85%,90% and 95%.  event happens with probability 1 − Fn1 (ed). Considering all  the possible events, the expected cost is given by  E{C} =  S−1  i=1  (i.Cd + ni.Cs)  i−1  j=1  Fnj (ed) (1 − Fni (ed))  + (S.Cd + M.Cs)  S−1  j=1  Fnj (ed) (4)  Note that a different 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 obtained.  5. SIMULATION  In this section, we present results of simulations that were  conducted to collect the exposure distribution function of  the number of sensors deployed.  5.1 Method  The exposure distribution is obtained by collecting   statistics on the exposure when deploying sensors randomly in a  predefined region. The random deployment is assumed to  be uniformly distributed over the region, which is a local   approximation. For every deployment, the minimum exposure  is found using a simulator implementing the algorithm   presented in section 2. A decay factor of k = 2 and maximum  energy of K = 60 are chosen to model the energy emitted  by targets (cf Equation 1). The region monitored is of size  20×20 with a noise (AWGN) of variance 1, so that the signal  coming from the target is covered by noise when the target is  8 or more units length away from a sensor. The sensors use  value fusion to collaborate when making a common decision  on the presence of a target in the region. 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  probability to get one or more false alarm along a path of  length 20 units (corresponding to 20 detection attempts by  the sensors) is 5%.  46  0 20 40  10  15  20  25  30  35  40  Cost for Cd=0 and Cs=1  n  Expectedcost  0 20 40  20  30  40  50  60  70  80  Cost for Cd=5 and Cs=1  n  Expectedcost  0 20 40  0  200  400  600  800  1000  1200  1400  Cost for Cd=100 and Cs=1  n  Expectedcost  Figure 6: Expected cost of achieving minimum exposure of 95% as function of the number of sensors for  three different cost assignments.  5.2 Distribution of minimum exposure  The distribution of minimum exposure were found for the  number of sensor deployed varying from 1 to 40. To   illustrate our results, the probability density functions for 5, 10  and 15 sensors are shown in Figure 4.  We observe that for 5 sensors deployed, the minimum   exposure has zero density for values less than the false alarm  probability of .04. The highest density is obtained for   values around .07 and then drops exponentially towards zero  for higher values of exposure. For deployment of 10 sensors,  we find again that the minimum exposure has zero density  for values below .04, then increases and has about constant  density for values lying between .1 and .98. We also observe  a peak of density around 1. For deployment of 15 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 5 sensors, it is very unlikely to obtain a  placement providing a desirable minimum exposure. When  deploying 10 sensors, most of the exposure levels are equally  likely and only poor confidence is given to obtain a   desirable exposure level. When deploying 15 sensors, it is very  likely that the sensor placement will give good exposure and  this likelihood keeps increasing with the number of sensors  deployed.  We use the cumulative distribution function obtained from  the statistics collected to evaluate the likelihood that the   desired level of exposure ed is obtained for varying number of  sensors. The graph of Figure 5 shows the probability that  the minimum exposure is above ed as a function of the   number of sensors deployed for ed = 80%, 85%, 90% and 95%.  These values can be used to evaluate the cost expressed in  Equation 4. The graph shows that the confidence level to  obtain a given minimum exposure level ed increases with the  number of sensors deployed. The confidence for ed when   deploying 40 sensors is above .999, which is sufficient for most  applications, and therefore we did not evaluate the   distribution of exposure when deploying more than 40 sensors.  6. RESULTS  In this section, we evaluate the expected cost of deploying  sensors using the simulation results. The optimal number  of sensor to deploy at first and in the succeeding steps can  be derived from these results.  For this cost analysis, the region parameters and signal  model are the same as specified in section 5. We further  assume that the number of sensors deployed at every step  is constant so that ni − ni−1 = n for all 1 ≤ i ≤ S. In this  case, Equation 4 reduces to  E{C} = (Cd + n.Cs)  S−1  i=1  i.  i−1  j=1  Fj.n(ed) (1 − Fi.n(ed))  + (S.Cd + M.Cs)  S−1  j=1  Fj.n(ed) (5)  We evaluated the expected cost as a function of n for  three different cost assignments with a desired exposure of  ed = 95%. The three corresponding graphs are shown in  Figure 6. The first cost assignment is (Cd = 0, Cs = 1) so  that the expected cost is the expected number of sensors to  be used to achieve an exposure of 95%. Since Cd = 0, the  number of steps used to deploy the sensors doesn"t affect the  cost and it is therefore optimal to deploy one sensor at a time  until the minimum exposure ed is reached, as we observe on  the graph. Overall, the expected number of sensor to be  47  deployed increases with n but we observe a local minimum  for n = 16 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 different number of sensors than can  be deployed at a time when deploying n sensors at each  step. For n around 16, the probability that the minimum  exposure is above ed varies a lot as shown in Figure 5 and the  weight associated with the first term of the sum (n) increases  rapidly while the weights associated with higher number of  sensors decrease. 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.  The second cost assignment is (Cd = 5, Cs = 1) so that  the cost of a deployment is equal to the cost of five sensors  (note that only the relative cost of Cd/Cs 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 19. Again, we  find that the curve presents a local minimum for n = 9 that  is due to the variations in weights. The last cost assignment  is (Cd = 100, Cs = 1) and the minimum cost is achieved  when deploying 27 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 effort residing in finding the  exposure distributions through simulation.  7. CONCLUSION  This paper addresses the problem of sensor deployment  in a region to be monitored for target intrusion. A   mechanism for sensor collaboration to perform target detection  is proposed and analyzed to evaluate the exposure of paths  through the region. The minimum exposure is used as a  measure of the goodness of deployment, the goal being to  maximize the exposure of the least exposed path in the   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.  We found that the optimal number of sensors deployed in  each step varies with the relative cost assigned to   deployment and sensors. The results of this study can be extended  to larger regions with different target parameters. The   solution proposed in this paper can also be improved by   considering deploying variable number of sensors at each step  and this multiple variables problem requires further   investigation.  8. ACKNOWLEDGMENTS  This work was supported in part by the Defense Advanced  Research Projects Agency (DARPA) and the Air Force   research Laboratory, Air Force Material Command, USAF,  under agreement number F30602-00-2-055. The U.S.   Government is authorized to reproduce and distribute reprints  for Governmental purposes notwithstanding any copyright  annotation thereon.  9. REFERENCES  [1] S. Baase and A. V. Gelder. Computer algorithms:  Introduction to design and analysis. Addison-Wesley,  2000.  [2] R. R. Brooks and S. S. Iyengar. Multi-Sensor Fusion:  Fundamentals and Applications with Software. Prentice  Hall, 1998.  [3] T. Clouqueur, P. Ramanathan, K. K. Saluja, and K.-C.  Wang. Value-fusion versus decision-fusion for  fault-tolerance in collaborative target detection in  sensor networks. In Proceedings of Fourth International  Conference on Information Fusion, Aug. 2001.  [4] M. Hata. Empirical formula for propagation loss in  land mobile radio services. IEEE Transactions on  Vehicular Technology, 29:317-325, Aug. 1980.  [5] S. Meguerdichian, F. Koushanfar, G. Qu, and  M. Potkonjak. Exposure in wireless ad-hoc sensor  networks. In Proceedings of MOBICOM, pages 139-150,  July 2001.  [6] Sensor Information Technology Website,.  http://www.darpa.mil/ito/research/sensit/index.html.  [7] P. Varshney. Distributed Detection and Data Fusion.  Springer-Verlag New-York, 1996.  48