Sage Journals: Discover world-class research

Abstract

We simulated a sensor network that detects and tracks the release of harmful airborne contaminants in an urban environment. The simulation determines sensor placement in that environment. The effort required integration of models from computational fluid dynamics (CFDs), combinatorial optimization, and population mobility dynamics. These CFD models, coupled with population mobility models, facilitate estimation of the effect of released contaminant on civilian populations. We studied the effects of a contaminant, chlorine gas, as a function of urban environment, prevailing winds, and likely attack locations. The models predictions optimized sensor node locations, providing mitigation of contaminant effects on human population. Results show that higher fidelity dispersal predictions increase sensor placement effectiveness. Incorporation of civilian evacuation models helps to minimize the overall impact of an attack when compared to a static population. Moreover, results show the benefits of using seasonal sensor configurations to maximize detection capabilities, taking into account prevailing seasonal wind conditions.

1. Introduction

Security concerns (e.g., [1–3]) focused attention on techniques that detect, localize, and respond to nuclear, biological, and chemical (NBC) agent attacks in dense urban population centers. One of the objectives of these techniques is to provide accurate predictions of agent dispersion at the onset of an attack so that rescue and evacuation efforts can be coordinated. Another objective is to determine sensor placement to provide optimal mitigation (e.g., minimize detection time and contaminant effect on human population). This research uses dispersion prediction techniques to optimize NBC sensor placement.

A powerful tool for dispersal prediction is computational fluid dynamics (CFDs) [4–9], which provide a family of models to conduct “what if” analysis. Detection of NBC threats benefits from the large number of sensing mechanisms and sensor systems that have been studied recently (i.e., [10–12]). Still, design and deployment of a reliable and accurate network of these sensors over a large area remains a challenge [13, 14]. Such a network would minimize the delay between the onset of a threat and its detection under specified tradeoff between the (high) probability of detection and the (low) probability of false alarm.

The design of an effective sensor network depends upon the sensor type, physical parameters of the environment (e.g., the speed and direction of the wind causing agent dispersal), and civilian response (e.g., crowd dynamics during evacuation). One of the practical considerations of our design is the use of “point sensors,” which require the agent to physically pass through the sensing mechanism. This sensor characteristic is reemphasized in Section 2.1. Ideally, the network will be able to provide reliable detection of the threat, allowing optimal mitigation and neutralization [13]. The challenge is to integrate all the pertinent factors (physical constraints, threat assessment, sensor capabilities, and human factors) into a system that provides a good compromise between the multiple performance indices that the system is expected to meet.

Since the focus of this paper is optimizing NBC sensor placement, we do not consider a specific networking technology that could be used to interconnect our sensors. However, given the proliferation of wireless devices and networks and assuming urban infrastructure, the NBC sensors could be networked through a variety of techniques including telephone lines, fiber optic networks, mobile broadband networks, urban Wi-Fi, power lines, or a combination of any of the aforementioned systems. For example, in [15] the authors describe an NBC sensor communication network that would be suitable for deploying our sensor network. The authors also claim that the network can be ported from one city to another if implemented correctly, thus reducing the amount of network redesign to deploy in a variety of urban environments.

The following conceptual example (see Figure 1) illustrates how the technologies developed in this paper apply in the event of an NBC attack. Consider the release of a harmful agent in a highly populated region within a dense urban area. A network of sensor nodes, distributed throughout the environment, on rooftops, sides of buildings, and other fixtures, detects the release of the agent. The placements of the sensor nodes were optimized prior to system deployment through techniques that take into account expected attacks, typical environmental conditions, and population distributions. Specifically, CFD modeling of the airflow through the environment was performed, given the prevailing winds; an inventory of potential targets was collected to determine which ones are likely to be chosen by an adversary. The sensor nodes perform distributed signal processing and data fusion calculations to monitor contaminant propagation in the environment. Results are communicated to the municipal command center and to rescue and first-responder organizations. Based on population density data and road conditions, plans for evacuation and contaminant countermeasures are recommended. This paper describes simulation and optimization techniques to design the sensor network needed for such scenarios (i.e., select sensor locations). The sensor framework is based on work done by Berry et al. [16]. We used the Fire Dynamics Simulator (FDS) [17] for NBC fallout dispersion simulations. The civilian evacuation model we employed is based on the cellular automata model developed by Burstedde et al. [18].

Figure 1

3D Illustration of an example NBC sensor network.

In Section 2, we discuss sensor network design and provide background material on our simulation efforts. In Section 3, we develop the system models for selecting the placement of sensors from a set of candidate locations and civilian evacuation. Section 4 presents the CFD dispersion modeling and civilian evacuation simulations. In Section 5, we discuss fallout dispersion, the effect of additional sensors in the network, civilian evacuation, and sensor placement optimization based on static and variable population. Finally, in Section 6, we present our conclusions.

2. Background

2.1. Sensor Network Design

Design of sensor networks for homeland security was the focus of studies by several U.S. government agencies, most notably the Defense Threat Reduction Agency of the U.S. Army Nuclear and Chemical Agency [19]. These efforts resulted in the development of several tools including SAFE (Sensor Analysis and Fusion Environment) and REASON (Response and Effects Analysis System for Operational Needs) [19].

A considerable amount of work was done on grid-based methods [20–24]. These methods often assume that each sensor has a known detection radius (area sensors) and seek to provide complete coverage in the sense that each point in regions under surveillance is covered by at least one sensor. Some of the issues that were studied are the effects of sensor positioning accuracy, imprecise sensing, terrain, and cost. In [24], Zou and chakrabarty focus sensor placement on a cluster-based distributed sensor network and use a virtual force algorithm to place sensors after an initial random deployment. This method attempts to localize detection using a given number of sensors within the distributed network. Another topic of interest is preferential coverage, taking into account tactical considerations and security [21]. This method also relies on area sensors. Most detectors available for NBC agent detection are, however, “point sensors,” that can only detect a threat at a single point in space [12]. Point sensors provide more reliable detection when compared to area sensors, which have higher false alarm rates due to environmental conditions. A typical NBC sensor requires an agent to attach physically or chemically to the surface area of the sensor, employing chemical processes or infrared spectroscopy for accurate detection [10, 11]. The design described in this paper employs the use of point sensors.

Characteristics of a sensor network can drive the sensor placement formulation as well. For example, in [25–30], a wireless sensor network model drives node placement with respect to communication constraints such as power consumption, uncertainty, and failure analysis. While these parameters are important, our work does not focus on a specific type of network communication and excludes those constraints (i.e., wired versus wireless). Other placement strategies base arrangement on optimization techniques such as genetic algorithms [31, 32] or simulated annealing [22, 33] with objectives ranging from emergency networks [34] to habitat monitoring [25] to surveillance detection [35]. Genetic algorithms and simulated annealing techniques can be prohibitive for complex problems while requiring significant time to compute solutions.

A previous study of great relevance to our objectives was published by Berry et al. [16] in 2004. They developed an efficient integer programming-based technique for detecting attacks on urban water distribution networks and minimizing contaminant delivery to consumers. The goal was to place a number of “perfect” sensors in pipes or junctions of a water network, and the technique decoupled the contaminant transportation problem from sensor placement decisions. While the underlying application and contamination propagation mechanisms in [16] are different from those needed for sensor placement in urban NBC attack scenarios, the mathematical framework can still be used. In our study we apply the framework of [16] to urban airborne contaminant networks that take into consideration the effects of wind, topography, population density, and civilian evacuation dynamics.

The inputs of the sensor placement algorithm we develop here are threat simulation results, population evacuation simulation results, a set of candidate sensor locations (including a detection threshold), and a total cost constraint (i.e., maximum number of sensors to be placed). The states of the sensor placement algorithm are binary variables which represent whether a sensor is placed (1) or not (0). The output of the sensor placement algorithm is the optimal configuration of sensors which minimizes the network's total threat consumption which is defined in Section 3.1.

2.2. Computational Fluid Dynamics

In order to make good decisions on sensor placement in a given three-dimensional environment, a database of fallout dispersion for various attack scenarios in that environment is needed. Here, we use simulation techniques based on computational fluid dynamics (CFDs) and meteorological forecasting models to develop this database for urban environments.

CFD techniques are now widely used in the prediction of complex flow processes in reactive systems [4, 5, 36], fire prediction [5, 6, 37], plasma processing [7, 8], and high-speed flow systems. The application of CFD models in chemical/biological transport problems for an urban setting is new [9, 38] and requires considerably more computer resources than traditional models [39].

The Department of Defense has funded the development of the FAST3D [40], FEFLO [41], and FEM3C [42]. These models are 3-dimensional CFD solvers explicitly developed for urban plume dispersion and transport modeling in complex geometries. The Department of Homeland Security's Urban Dispersal Program [3, 43] aims to improve and validate computer models that simulate the atmospheric movement of contaminants within cities and around, into, and within building interiors [3, 9, 43].

In this paper, we use the Fire Dynamics Simulator (FDS) [17], a CFD program developed by the National Institute of Standards and Technology (NIST). FDS is a multispecies, multivariable, boundary condition CFD program for the three-dimensional simulation of fires and smoke transport based on the Large Eddy Simulation (LES) technique [44–46]. For more information regarding CFD modeling and parameter tuning, see [9, 39, 47–49], and for information pertaining to FDS validation and applicability, see [6, 37, 46, 47, 50–55].

The inputs to the CFD simulations are the terrain where the dispersion will be modeled (i.e., the city model), physical parameters of the NBC agent (i.e., the molecular weight of chlorine), the prevailing wind condition, mesh size, simulation time, location of agent release, and data collection points (i.e., candidate sensor locations). The basic assumptions made by the simulator are (1) prior to agent release—the environment is uncontaminated; (2) during the agent release—the environment becomes contaminated; (3) after the release ends—the agent disperses throughout the environment until it is no longer detectable. The outputs of the simulations are the simulated concentration data at each candidate sensor location versus time and an animation file that illustrates the simulation.

2.3. Assumed Threat

In this study the contaminant gas is chlorine (Cl₂). The widespread availability of chlorine and usage in both commercial applications (i.e., water treatment and sanitation of sewage) and in chemical warfare motivates its use in this paper. Exposure to high concentrations of chlorine gas can be fatal to humans. If there was a chlorine gas leak or accident in an urban environment, many people could be at risk of high exposure and consequently severe injury or death. (Chlorine gas can cause pulmonary edema. When inhaled, Cl₂ reacts with lung water to produce hydrochloric acid (HCL) [56]. Chlorine gas can be fatal after a few breaths at 1000 parts per million (ppm) [57]. As little as 2.5 mg per liter (approximately 0.085 percent by volume) in the atmosphere can cause death in minutes [57].)

The density of air is 0.00128 g/mL, and chlorine gas is 2.5 times heavier than air (e.g., 0.0032 g/mL) [58, 59]. When chlorine gas is compared to carbon dioxide, chlorine is about 1.6 times heavier than carbon dioxide (smoke). Since chlorine gas is heavier than smoke, we assume that chlorine gas stays closer to ground level and propagates at a slower rate than smoke.

We use the following chlorine gas parameters as inputs to FDS: a molecular weight of 70.9 atomic mass units and a mass fraction of 0.4 (40% chlorine and 60% air). For the purposes of detecting chlorine-based attacks, we assume that available sensor technology allows the detection of chlorine concentrations at 1 ppm which approximates to a concentration threshold of 10⁻⁶ Kg/Kg.

2.4. Pedestrian Evacuation

In the event of an attack on an urban area, the distribution of humans in the attack area is of central importance in modeling the overall effect of a released contaminant. Assuming that the attack is apparent (i.e., accompanied by a loud explosion), it is natural to assume that pedestrians would quickly flee from the area of perceived danger. The dynamics of this crowd movement will help estimate the number of individuals exposed to the threat. Applying this model of pedestrian movement over the entire population in an area under attack allows for the calculation of the population density of different areas of a map as a function of time.

For simulating civilian flow, three main models emerge: the fluid approach, flow modeling, and discrete distributed modeling. The fluid flow regards the group of civilians as a single, consistent mass. However, taking into account human behaviors, the forces acting on a fluid would not match that of a crowd of civilians. The flow modeling approach, which is the newest method and still in development, is a derivative of the fluid approach but takes into account the different forces and behaviors that guide crowds. The discrete modeling approach [60, 61] is the most established method of modeling crowds. In this approach, crowd modeling consists of a group of individuals, each with his/her own movement behavior rather than a single mass. Helbing and Molnár present the social force model [60], which shapes particle movement by social rules where the environment and individual behaviors influence crowd dynamics. Reynolds' results [61] show that individuals move in crowd like behaviors with simple rules in place. A majority of discrete distributed modeling [62–64] are based on the work of Helbing and Reynolds.

We considered a number of existing models of population evacuation [60, 61, 64–70]. Most were confined to evacuations of a single building and depended on movement restrictions and behavioral assumptions that may not fit our scenario. We elected to use a discrete distributed model based upon the principles of Cellular Automata (CA), which have been extensively researched in crowd modeling [70–72] and vehicular traffic modeling [73]. There have been several attempts to model the movement of pedestrians based on CA, notably those described in [18, 66, 67, 70–73]. CA modeling is simple and computationally efficient and can reproduce several behaviors exhibited in pedestrian dynamics [18, 72, 73].

CA models are discrete models based on the concept of cells, each one defined with a finite number of possible states. The CA model we employed divided the environment into cells, based on the two-dimensional automata schemes developed by Burstedde et al. [18]. Burstedde's model is arranged such that each cell has eight neighbors (see Figure 2). Each cell is either occupied by a pedestrian or vacant. The state of a cell at any moment in time is determined by the previous state of that cell, the previous states of neighboring cells, and the cell transition functions. The transition functions determine which neighboring cell has the highest probability of being occupied by a pedestrian at the next time step.

Figure 2

Illustration of neighboring cell locations.

The inputs to our civilian evacuation simulations are the initial density of human occupancy in the environment (person/meters²), the attack location, and the values for influence variables, $J_{s}$ and $J_{d}$ . The output is the population density versus time around each candidate sensor location for the entire simulation. Prior to the attack the human population is assumed to be distributed uniformly throughout the environment.

3. System Model

In the following section, we develop the two key components to our system model: sensor placement and civilian evacuation.

3.1. Sensor Placement Optimization

We build upon the mathematical framework provided by Berry et al. [16]. See Table 1 for a list of symbols and their definitions. Consider a set of “candidate” sensor locations in an urban sensor network, $V = {v_{1}, v_{2}, \dots, v_{N}}$ where each candidate location is defined as a tuple, $v_{i} = {x_{i}, y_{i}}$ , of the location horizontal (x) and vertical (y) coordinates (meters) with respect to the center of the modeled environment and N is the number of candidate sensor locations in the network. In the case of an urban environment, preference is given to intersections and midway points of streets. The maximum number of sensors allowed to be placed is $S_{MAX}$ . Consider the set of attack locations, $Π = {π_{1}, π_{2}, \dots, π_{M}}$ , where each attack location is defined as a tuple, $π_{i} = {x_{i}, y_{i}}$ , and M is the number of attack locations. $d \in D$ where $D = {N, S, E, W, NW, NE, SW, SE}$ is the prevailing wind condition for a given set of CFD simulations. $A_{d}$ is a set of attacks with wind condition d. $a_{(d, π_{i})} \in A_{d}$ is an attack originating at location $π_{i}$ with prevailing wind condition $d \in D$ . $α_{a_{(d, π_{i})}}$ is the probability of attack $a_{(d, π_{i})}$ where $\sum_{π_{i} \in Π} α_{a_{(d, π_{i})}} = 1$ . $L_{a} \subseteq V$ is the set of “contaminated” locations in $V$ by attack a. $d_{v_{i}} (t_{1}, t_{2})$ is the total amount of contaminant delivered to node $v_{i} \in V$ from time $t_{1}$ to time $t_{2}$ . $γ_{a_{(d, π_{i})}, v_{i}} (t)$ represents the concentration of the contaminating agent, found by the CFD simulations, in the computational cell (described in Section 2.2 around node $v_{i} \in V$ during attack $a_{(d, π_{i})} \in A_{d}$ . $ρ (v_{i}, t)$ is the human population density (persons/m²) as a function of time (t) in a 1 meter by 1 meter box centered at each candidate sensor location $(v_{i})$ in the network, found using the Burstedde CA model [18]. The set of contaminated locations (i.e., those locations where the concentration of the threat has surpassed a given threshold) is determined from CFD simulations by monitoring NBC agent concentration around the locations in the set $V$ . We can use this concentration data to determine the consumption, $ω_{a_{(d, π_{i})}, v_{j}}$ , which is the amount of NBC agent delivered by attack $a_{(d, π_{i})} \in A_{d}$ to the rest of the network (i.e., $\forall v_{i} \in V$ ) before detection occurs, assuming that a sensor placed at node $v_{j} \in L_{a}$ is the first sensor to signal an alarm. To compute $ω_{a_{(d, π_{i}}), v_{j}}$ , we use the initial time of attack $a_{(d, π_{i})} \in A_{d}$ , denoted by $t_{a_{(d, π_{i})}, 0}$ and the time $t_{a_{(d, π_{i})}, v_{j}}$ , at which the attack is detected at node $v_{j} \in L_{a}$ . The first detector index $b_{a_{(d, π_{i})}, v_{i}}$ is 1 if a sensor at node $v_{i}$ is the first sensor to detect attack $a_{(d, π_{i})} \in A_{d}$ and 0 otherwise. Specifically, we define

\begin{matrix} ω_{a_{(d, π_{i})}, v_{j}} & = \sum_{v_{i} \in V} d_{v_{j}} (t_{a_{(d, π_{i})}, 0}, t_{a_{(d, π_{i})}, v_{j}}) \\ = \sum_{v_{i} \in V} \int_{t_{a_{(d, π_{i})}, 0}}^{t_{a_{(d, π_{i})}, v_{j}}} ρ (v_{i}, t) γ_{a_{(d, π_{i})}, v_{j}} (t) d t . \end{matrix}

(1)

We use information on time-varying population density to account for civilian evacuation and weigh contaminant “intake” so that regions of high pedestrian occupancy and low pedestrian mobility are more likely to have sensors placed near them.

Table 1

Symbol table for sensor placement optimization.

Symbol	Definition
$v_{i} = {x_{i}, y_{i}}$	Candidate sensor location $v_{i}$ at position ${x_{i}, y_{i}}$ , where $i = {1, \dots, N}$ (ℤ)
$V = {v_{1}, v_{2}, \dots, v_{N}}$	Set of candidate sensor locations
$π_{i} = {x_{i}, y_{i}}$	Attack location $π_{i}$ at position ${x_{i}, y_{i}}$ , where $i = {1, \dots, M}$ (ℤ)
$Π = {π_{1}, π_{2}, \dots, π_{M}}$	Set of attack locations
$D \in {N, S, E, W, NW, NE, SW, SE}$	Prevailing wind conditions
$d \subseteq D$	Prevailing wind conditions used in CFD simulations
$a_{(d, π_{i})}$	Attack under wind condition d at location $π_{i}$
$A_{d} = {a_{(d, π_{1})}, a_{(d, π_{2})}, \dots, a_{(d, π_{M})}}$	Set of attacks under wind condition d
$α_{a_{(d, π_{i})}}$	Probability of attack $a_{(d, π_{i})} \in A_{d}$ with $\sum_{π_{i} \in Π} α_{a_{(d, π_{i})}} = 1$ (ℝ)
$L_{a} \subseteq V$	Set of contaminated locations within $V$ due to attack a
$S_{MAX}$	Maximum number of sensors allowed to be placed (ℤ)
$d_{v_{i}} (t_{1}, t_{2})$	Total amount of contaminant delivered to node $v_{i} \in V$ from time $t_{1}$ to time $t_{2}$ (ℝ)
$ρ (v_{i}, t)$	Human population density (persons/ $m^{2}$ ) as a function of location index $(v_{i})$ and time $(t)$ (ℝ)
$ω_{a_{(d, π_{i})}, v_{j}}$	Consumption of the network as a function of attack $a_{(d, π_{i})} \in A_{D}$ and the first node to sound the alarm $v_{j} \in V$ (ℝ)
$γ_{a_{(d, π_{i})}, v_{i}} (t)$	Concentration of the contaminating agent (ℝ)
$t_{a_{(d, π_{i})}, 0}$	Initial time of attack $a_{(d, π_{i})} \in A_{d}$ (ℝ)
$t_{a_{(d, π_{i})}, v_{j}}$	Time attack is detected at node $v_{j} \in L_{a}$ (ℝ)
$s_{v_{i}}$	Sensor placement index, which is 1 if a sensor is placed at node $v_{i}$ and 0 otherwise
$b_{a_{(d, π_{i})}, v_{i}}$	First detector index, which is 1 if a sensor at node $v_{i}$ is the first sensor to react to attack $a_{(d, π_{i})} \in A_{d}$ and 0 otherwise

The decision variable for our optimization problem is the sensor placement index $s_{v_{i}}$ which is 1 if a sensor is placed at node $v_{i} \in V$ and 0 otherwise.

Given the above formulation, the objective function for sensor placement becomes

\begin{matrix} \min \sum_{a_{(d, π_{i})} \in A_{d}} \sum_{v_{j} \in L_{a}} α_{a_{(d, π_{i})}} ω_{a_{(d, π_{i})}, v_{j}} b_{a_{(d, π_{i})}, v_{j}} . \end{matrix}

(2)

subject to the following constraints:

\begin{gathered} \sum_{v_{j} \in L_{a}} b_{a_{(d, π_{i})}, v_{j}} = 1 \forall a_{(d, π_{i})} \in A_{d}, \end{gathered}

(3)

\begin{matrix} b_{a_{(d, π_{i})}, v_{j}} \leq s_{v_{j}} \forall a_{(d, π_{i})} \in A_{d}, v_{j} \in L_{a}, \end{matrix}

(4)

\begin{gathered} \sum_{v_{i} \in V} s_{v_{i}} \leq S_{MAX} . \end{gathered}

(5)

The objective function (2) minimizes network “consumption” of NBC contaminant averaged over a set of attacks. The constraint in (3) enforces that there is exactly one best sensor for each attack. The constraint in (4) enforces that a sensor cannot be the best sensor for an attack if it is not installed, and the constraint in (5) enforces that at most $S_{MAX}$ sensors are used.

3.2. Population Evacuation

We use a simplified version of the Burstedde cellular automata (CA) model [18] to quantify civilian population density throughout an urban environment during an NBC attack. Only bordering cells (see Figure 2) may cause a transition from vacant to occupied, and a pedestrian may only move in eight directions (N, S, E, W, NW, NE, SW, and SE).

The model works as follows. The map of the area to be studied is divided into a two-dimensional (x-location by y-location) grid of 40 cm × 40 cm cells. The cell size was chosen to correspond to the amount of space occupied by an average-sized adult. Only one pedestrian may occupy a cell at any given time t. The state of cell $(i, j)$ at time t is denoted by $N_{(i, j)} (t)$ , which takes value of 1 (occupied) or 0 (vacant) at time t. In our evacuation model, time is measured in discrete steps ( $Δ t$ ), where $Δ t = 3$ seconds. The state of a cell at time $t + Δ t$ is determined by the state of the cell and its neighbors at time t.

Floor fields are variables associated with each cell that are used by pedestrians to assist in determining their next move. These variables mediate long-range interactions between cells and constrain pedestrian transitions to neighboring cells only. Two different types of floor fields, static (sField) and dynamic (dField), are used to model movement during an emergency. Simulation wide constants are used to determine the level of influence that the sField and dField values have on pedestrian movement.

sFields correspond to movement based on a pedestrian's knowledge of the topology of an area and, therefore, model “intelligent” movement behavior. If a pedestrian knows that a certain direction leads to an exit, the sField value, $τ_{s}$ , for cells along that exit route will be increased. The sField is computed at the beginning of the simulation, and its value stays constant throughout the entire simulation.

dFields correspond to “herding” movement behavior. When a pedestrian is ignorant of the topology of an area, he/she is likely to base his/her movement on the movement of other pedestrians. The dField value of a cell, $τ_{d}$ , plays the role of recording the number of people that have recently visited the cell. The dField of cell $(i, j)$ increments up by 1 for each pedestrian that enters the cell $(i, j)$ . As pedestrians do not occupy a cell, the dField value will decrement by 1 at each time step, unless a pedestrian enters the cell. If $τ_{d}$ equals zero, the dField will have no influence on the pedestrian movement. A dField would also be used in the situation where the pedestrian's visibility is impeded and he/she must rely on the movement of others for guidance.

A cell $(i, j)$ occupied during time t ( $N_{(i, j)} (t) = 1$ ) will remain occupied or become vacant at time $t + Δ t$ . To determine intercell mobility for a pedestrian between cells $(i, j)$ and $(k, l)$ , where $k \in {i - 1, i, i + 1}$ and $l \in {j - 1, j, j + 1}$ , we apply the following equation that determines the weight, $W_{(k, l)}$ , of potential moves. This weight determines the most preferred direction of movement (e.g., the direction with the highest weight) among the eight neighboring cells,

\begin{matrix} W_{(k, l)} = e^{τ_{s} (k, l) - τ_{s} (i, j)} (1 - N_{(k, l)} (t)), \end{matrix}

(6)

where

τ_{s} (k, l)

and

τ_{s} (i, j)

are the static floor fields (sFields) of their respective cells.

Once the weights are determined, the variable $M_{(i, j)}$ is used to determine the next transition. $M_{(i, j)}$ is a score assigned to cell $(i, j)$ that indicates the desirability of moving into this cell at the next step. The value of $M_{(i, j)}$ is influenced by the sField and dField values. The cell corresponding to the highest $M_{(i, j)}$ value is the cell the pedestrian wants to move into at the next time step. If multiple cells have the highest value of $M_{(i, j)}$ , the cell with the highest weight will be chosen from among them.

In these calculations, i and j are relative to the cell in which the pedestrian currently resides (see Figure 2) and k and l are relative to the cell that the pedestrian might move into. $M_{(i, j)}$ is calculated using

\begin{matrix} M_{(i, j)} = e^{J_{s} D_{s} (i, j)} e^{J_{d} D_{d} (i, j)} (1 - N_{(i, j)} (t)), \end{matrix}

(7)

where

\begin{gathered} \begin{matrix} D_{s} (i, j) = τ_{s} (k, l) - τ_{s} (i, j), \end{matrix} \\ D_{d} (i, j) = τ_{d} (k, l) - τ_{d} (i, j) . \end{gathered}

(8)

Here

τ_{s} (i, j)

is the value of the sField for cell

(i, j)

and

τ_{d} (i, j)

is the value of the dField for cell

(i, j)

$J_{s}$ and $J_{d}$ are constants used to determine the level of influence which sField and dField values, respectively, have on pedestrian movement. The values given to $J_{s}$ and $J_{d}$ with respect to each other determine the level of knowledge expected from pedestrians in the simulation. Instances when $J_{s}$ is higher than $J_{d}$ will lead pedestrians to favor using their knowledge of the area over blindly following the movement of other pedestrians and vice versa. For outdoor areas, $J_{s}$ should usually dominate $J_{d}$ because visibility is likely to be good and the grid-like nature of city streets makes it easier for a pedestrian to use available knowledge to move away from a threat. For this reason, floor field influencing values were set as $J_{s} = 1.0$ and $J_{d} = 0.1$ in our simulations.

4. Simulations

4.1. Fallout Dispersal Prediction

Fire Dynamics Simulator (FDS) was used to obtain simulated data for contaminant dispersal in a three-dimensional domain, which can be seen in Figure 1. Figure 3 shows the computational domain in two dimension: several city blocks in the downtown area of a generic urban environment.

Figure 3

Generic urban environment used for fds simulations shown in 2D.

The urban environment included a city hall, an area of high concentration of humans, with political and symbolic significance. Second, a park (shown in green) was included to show the effect of an open area within an urban canyon on contaminant flow. Also, a central business district consisting of four skyscrapers in one block of the model near the city hall was created. The rest of the model was filled with generic buildings of varying dimensions. The streets, alleys, and other areas of open space between buildings add another realistic feature to the model. The combination of these features allows us to investigate dispersion characteristics of the urban environment, such as the trapping of contaminant in specific areas due to the geometric layout of the environment.

Figure 3(a) displays the thirty-three numbered candidate sensor locations ( $V = {v_{1}, v_{2}, \dots, v_{N}}$ with $N = 33$ ) in red. The candidate locations are at all intersections and points midway between intersections. They are laid out consistent with potential placement on traffic and street lights. All candidate sensor locations are 1.5 meters above ground so that we can calculate the concentration levels at the average height of a human.

Figure 3(b) displays the thirty-three numbered attack locations, $Π = {π_{1}, π_{2}, \dots, π_{M}}$ , in blue. The attack locations are spread throughout the urban environment with more attacks taking place in areas of high profile (i.e., city hall or the park). There is also a higher density of attacks around the central business district. By adjusting the values of the probabilities of attack, $α_{a_{(d, π_{i})}}$ , we can simulate the propensity of attacks to focus on high profile targets.

There are thirty-three simulated attacks per attack simulation set $A_{d}$ . Each simulated attack describes agent dispersal propagation over approximately 8 minutes. Attacks in the Northwest set ( $A_{NW}$ ) have prevailing winds with constant direction and velocity originating from the northwest and blowing towards the southeast. Similarly, attacks in the Southwest set ( $A_{SW}$ ) have prevailing winds with constant direction and velocity originating from the southwest and blowing towards the northeast (Summer). In the Random attack simulation set (e.g., $A_{RD}$ ), each attack has a random, constant wind direction and velocity (Fall and Spring).

4.2. Human Evacuation

In the evacuation simulator we assumed that the only barriers pedestrian movement were other pedestrians and buildings. We initialized the occupancy of cells in the CA civilian mobility simulation ( $N_{(i, j)} (0)$ for all $(i, j)$ ) by assuming that cells outside of buildings had a 1% chance of being occupied. This leads to approximately 2,500 pedestrians to be simulated in our model. The concentration of humans exiting a building during the simulation was zero. These assumptions would correspond to a daytime weekend distribution of pedestrians.

Our algorithm for determining the sField value of a cell works in two steps. First, we determine which cell was the origin of the attack and assign it the cell location $(i_{0}, j_{0})$ . For each cell in the map, $(i, j)$ , we find

τ_{s} (i, j) = \sqrt{{(i - i_{0})}^{2} + {(j - j_{0})}^{2}} .

(9)

In Figure 4(a), we illustrate contours of constant sField values as concentric circles about the origin of attack. These concentric rings create a movement gradient such that pedestrians will flee directly away from an attack, where the blue rings correspond to low values of $τ_{s}$ and the red correspond to very high values of $τ_{s}$ . However, these movement gradients often lead pedestrians to walk directly into the side of buildings. It also tends to force pedestrians into cramped alleyways, creating unrealistic bottlenecks to movement.

Figure 4

2D illustration of sField calculation for attack location using.

sField computation is modified to eliminate these undesired behaviors using a technique called striping. Allowed movement paths are divided crosswise into stripes. For each stripe, each 1 cell wide, we locate the cell with the largest sField value and assign all the cells within the stripe with that value. Striping warps the concentric rings formed by the first step of the algorithm as illustrated in Figure 4(b). This warping retains the general trend of moving pedestrians away from the center of an attack and enforces practical constraints on the avenues of evacuation.

5. Results

We present the results below in the following organization. First, the fallout dispersion results are presented. Next, we describe the effect of sensors on “Network Consumption.” Then we present the results of civilian evacuation. Finally, the sensor placement results are described, such that, first we discuss the sensor placement against static population and then against a variable population.

5.1. Fallout Dispersion Results

Figure 5, which is a two-dimensional snapshot of our three-dimensional urban terrain, illustrates the dispersal of the chlorine gas during $a_{(SW, π_{4})} \in A_{SW}$ . In this attack chlorine gas is released slightly south of the center of the environment. Agent dispersal data were collected as a function of time at all candidate sensor locations (see Figure 3(a)). The color bar located to the right of the snapshots is an agent concentration scale expressed in units of Kg/Kg (Kg of agent/Kg of air) with red being the highest concentration and dark blue being the lowest. Figure 5 shows how the agent disperses through the urban environment (with snapshots at $t = 11$ seconds, $t = 65$ seconds, $t = 113$ seconds, and $t = 302$ seconds) with wind originating from the southwest. While much of the initial plume from the attack proceeds northeast, as expected by the direction of the wind, an appreciable concentration of the chemical agent collects in the east and southeast sections due to urban geometry. The simulation thus is able to predict zones of heightened danger. Figure 6 shows the concentration of the simulated chlorine ( $γ_{a_{(SW, π_{4})}, v_{3}}$ and $γ_{a_{(SW, π_{4})}, v_{17}}$ ) at two candidate sensor locations, $v_{3}$ and $v_{17}$ , for attack $a_{(SW, π_{4})}$ , illustrated in Figure 5. This figure also illustrates the agent concentration threshold required for the sensor to detect an attack, as well as the time (beginning at the initiation of the attack at which chlorine gas would be detected at the respective candidate sensor locations, $v_{3}$ and $v_{17}$ ).

Figure 5

2D Illustration of chemical agent propagation in urban environment during attack $a_{(SW, π_{4})}$ , simulation set $A_{SW}$ at time.

Figure 6

Chemical agent concentration data versus time with detection time and sensor detection threshold during attack 4, ( $a_{4}$ ), simulation Set $A_{SW}$ at candidate sensor location.

In Figure 6(a), the contaminant concentration fluctuates as a result of the urban terrain and the prevailing wind. The product of the concentration data shown in Figure 6 and the population density, $ρ (v_{i}, t)$ , can be integrated from the start of the attack to the time of attack detection (by the respective candidate sensor) to find the consumption of contaminants, $ω_{a_{(SW, π_{4})}, v_{3}}$ and $ω_{a_{(SW, π_{4})}, v_{17}}$ at the respective location in the network using (1).

5.2. Effect of Sensors on Network Consumption

We performed mathematical optimization to solve the problem using the AMPL Modeling Language for Mathematical Programming [74] in concert with the linear solver, LP_SOLVE [74] (collectively referred to as AMPL), to solve the optimization problem formulated in (2)–(5). In doing so, we calculate the optimal placement of sensors for networks containing up to $S_{MAX} = 20$ sensors. Every attack in each simulation set is assumed to be equiprobable (i.e., $α_{a_{(d, π_{i})}} = 1 / | A_{d} |$ ).

Figure 7 shows the change (lower is better) in network chemical agent consumption versus $S_{MAX}$ , the total number of sensors that can be placed. Network consumption is normalized by the maximum consumption obtained over all attack simulation sets (both static and variable population results). Figure 7(a) is the result of the optimization when a static population ( $ρ (v_{i}, t)$ in (1) is constant) is assumed. Figure 7(b) shows the result of the optimization when $ρ (v_{i}, t)$ is computed using the population evacuation process (described in Section 3.2). In both, there is an exponential decrease in the network consumption as additional sensors are made available. For all three attack simulation sets there is no significant decrease (the change in consumption is below a detectable threshold) in contaminant consumption after ten sensors are placed. A significant reduction in the network consumption is seen when the population evacuation process is taken into account (cF. Figures 7(a) and 7(b)). This results of course from the removal of pedestrians from contaminated areas, preventing contaminant consumption*.

Figure 7

Total consumption of contaminants in the network (prior to attack detection) versus the total number of available sensors ( $S_{MAX}$ ) for.

Detailed tables showing the various configurations and consumption values for the three scenarios and for configurations containing up to twenty sensors can be found at [75].

5.3. Civilian Evacuation Effects

Figure 8 shows the graphical output of our population evacuation simulation for the attack pictured in Figure 5. Here, the red dot indicates the origin of the attack and black dots indicate individual pedestrians. Figure 8(a) shows the initial distribution of pedestrians, distributed randomly along roads and in the park, at the start of the attack. Figure 8(b) shows the evacuation of the population after 150 seconds with pedestrians scattering away from the source of the attack. The results of this simulation were used to calculate $ρ (v_{i}, t)$ in (1) for all $v_{i} \in V$ during $a_{(SW, π_{4})} \in A_{SW}$ . Please refer to Table 2 for a detailed description of all civilian evacuation related variables. Figure 9 shows a plot of the population density versus time at $v_{17}$ (see Figure 3(a) for sensor locations) during the attack shown in Figure 5. $v_{17}$ is the closest sensor to $π_{4}$ and it takes approximately three minutes to completely evacuate from that location.

Table 2

Symbol table for population evacuation.

Symbol	Definition
$ρ (v_{i}, t)$	Human population density (persons/ $m^{2}$ ) as a function of time $(t)$ and location index $(v_{i})$ (ℝ)
$(i, j)$	i is the x-location of a cell in the modeled area, and j is the y-location of the same cell
$(k, l)$	k is the x-location of another cell such that $i \neq k$ and l is the y-location of the same cell such that $j \neq l$
$N_{(i, j)} (t)$	Binary variable which takes value of 1 (occupied cell) or 0 (vacant cell) at time t
$W_{(k, l)}$	Preference weight of potential pedestrian movement decisions (ℝ)
$τ_{s}$	Static floor field value (ℝ)
$τ_{d}$	Dynamic floor field value (ℝ)
$M_{(i, j)}$	Desirability of cell $(i, j)$ for a pedestrians next move (ℝ)
$D_{s}$	Difference of $τ_{s}$ between cell location $(k, l)$ and $(i, j)$
$D_{d}$	Difference of $τ_{d}$ between cell location $(k, l)$ and $(i, j)$
$J_{s} and J_{d}$	Constants used to determine the level of influence that sField and dField values, respectively, have on pedestrian movement (ℝ)

Figure 8

Simulation of population evacuation during the attack illustrated in Figure 5 at.

Figure 9

Graph of population density versus time for $a_{(SW, y_{4})}$ (shown in Figure 8) at $v_{17}$ .

5.4. Sensor Placement Results

5.4.1. Optimal Sensor Placement for Static Population Density

The consumption values, along with the configuration of placed sensors, are shown for each attack simulation set ( $A_{NW}$ , $A_{SW}$ , and $A_{RD}$ ) in Table 3, where all the attacks were assumed to be equiprobable and the maximum number of sensors, $S_{MAX}$ , was set to 10. Table 3 shows a list of candidate sensor locations in which the algorithm placed a sensor to minimize network consumption for the three attack simulation sets. We refer to this set of sensor configurations as $Υ_{NW}$ , $Υ_{SW}$ , and $Υ_{RD}$ , respectively, for the three attack simulation sets. The value of the sum of normalized consumptions over the three simulation sets is 0.983. Please refer to Table 1 for a detailed description of all sensor placement variables.

Table 3

Configurations of sensors for a static population: $S_{MAX} = 10$ .

Simulation set	Wind direction	Sensor configuration	Consumption value
$Υ_{NW}$	NW	$v_{5}$ , $v_{12}$ , $v_{13}$ , $v_{14}$ , $v_{19}$ , $v_{22}$ , $v_{24}$ , $v_{26}$ , $v_{29}$ , $v_{31}$	0.392
$Υ_{SW}$	SW	$v_{2}, v_{5}, v_{9}, v_{10}, v_{12}, v_{18}, v_{20}, v_{27}, v_{29}, v_{33}$	0.153
$Υ_{RD}$	RD	$v_{3}, v_{5}, v_{9}, v_{12}, v_{17}, v_{19}, v_{21}, v_{23}, v_{26}, v_{29}$	0.438

Common sensors	$v_{5}$ , $v_{12}$ , $v_{29}$

It is noted that there are relatively few sensors that are common to the optimal configuration of sensors for all three attack simulation sets (i.e., $Υ_{NW} \cap Υ_{SW} \cap Υ_{RD} = {v_{5}, v_{12}, v_{29}}$ ).

Sensors would have to be moved based on the predicted long-term wind patterns to achieve optimal performance. Seasonal movement of sensors is consistent with the military strategy known as “Sense-and-Respond” logistics [76, 77]. If the set of sensors in $Υ_{NW}$ is used in all three scenarios, the sum of normalized consumptions becomes 4.083, approximately four times higher than the combined value we achieved by optimizing for each season. Similarly, the sum of normalized consumptions when using $Υ_{SW}$ and $Υ_{RD}$ across all scenarios is high, 5.775 and 1.922, respectively. Using $Υ_{RD}$ across all scenarios leads to the smallest mean total consumption value, yet it is still nearly twice the value we find when moving the sensors each season.

As shown in Figure 7, it is desirable to have at least ten sensors placed in the network. By merging all three sets of attacks together and optimizing our network configuration, for a set of 10 sensors, a year-long configuration shown in Table 4 was found. The consumption for this yearlong configuration, 1.602, is significantly lower than the sum of consumptions for $Υ_{NW}$ , $Υ_{SW}$ , and $Υ_{RD}$ when each of these configurations is used across the merged set of attacks. In this case a configuration calculated from the merged set of attacks is significantly better than any of the individual configurations when moving the sensors is not possible. Unfortunately the consumption is still 1.5 times as great as the best value obtained by reconfiguring the sensors each season.

Table 4

Yearlong configuration of 10 sensors for a static population.

Wind direction	Sensor configuration	Consumption value
$A_{NW} \cup A_{SW} \cup A_{RD}$	$v_{5}$ , $v_{9}$ , $v_{12}$ , $v_{17}$ , $v_{19}$ , $v_{21}$ , $v_{23}$ , $v_{26}$ , $v_{29}$ , $v_{33}$	1.602

5.4.2. Optimal Sensor Placement for Variable Population Density

Up to this point, we assumed that the population density, $ρ (v_{i}, t)$ , remained constant during the attacks. We now integrate the population density data determined by the civilian evacuation simulations into the optimization of sensor placement. Using the sets $Υ_{NW}$ , $Υ_{SW}$ , and $Υ_{RD}$ with the population density results estimated by our simulations, the total consumptions were recalculated. The sum of normalized consumptions for the attack sets, replacing the static population results with variable population results, was found to be 0.628.

Next, rather than using the sensor configurations found in Section 5.4.1 we used AMPL to solve our constrained placement equations taking into account variable population results. Table 5 shows the sensor arrangements as given by AMPL for $S_{MAX}$ set equal to 10.

Table 5

Configurations of 10 sensors for a variable population.

Simulation set	Wind direction	Sensor configuration	Consumption value
$Υ_{NW}$	NW	1 3 5 7 12 22 23 26 29 33	0.0021
$Υ_{SW}$	SW	2 5 12 17 19 23 24 27 29 33	0.0024
$Υ_{RD}$	RD	2 5 12 17 19 23 24 25 26 29	0.0028

Common sensors	5 12 23 29

The sum of normalized consumptions for the configurations calculated using the variable population results was 0.0455. This value is less than one tenth of what we found by simply using a static population model.

This difference underscores the importance of taking into account pedestrian movement. The evacuation of pedestrians in our simulation resulted in a considerably lower consumption, and the methodology allows for comparison of different evacuation regimes and demonstrates the effect of a moving population when placing sensors. Table 6 shows sensor placements common between the two population models. While eight out of ten sensors are in common under the random wind scenario, only about half of the sensors coincide between the two sets of data in the other two scenarios.

Table 6

Common sensor configurations between the static and variable population types.

Wind direction	Common sensors
NW	$v_{5}$ , $v_{12}$ , $v_{22}$ , $v_{26}$ , $v_{29}$
SW	$v_{2}$ , $v_{5}$ , $v_{12}$ , $v_{27}$ , $v_{29}$ , $v_{33}$
RD	$v_{2}$ , $v_{5}$ , $v_{12}$ , $v_{17}$ , $v_{19}$ , $v_{23}$ , $v_{26}$ , $v_{29}$

Common sensors	$v_{5}$ , $v_{12}$ , $v_{29}$

6. Conclusions

We have quantified the benefit of additional sensors on the population and threat response time in an urban center and found that detailed modeling and monitoring of the prevailing winds in the urban area can greatly improve the effectiveness of the sensor placement algorithm. Our results indicate that sensors may have to be moved from location to location, based on seasonal wind patterns, in order to achieve optimal performance. Seasonal movement of sensors is consistent with the military strategy known as “Sense-and-Respond” logistics.

By incorporating pedestrian evacuation simulations based on CA into our problem formulation, a significant reduction in the value of consumption was achieved. More importantly, evacuation models changed the way we placed our sensors and improved overall performance (i.e., reduced contaminant consumption).

The most important observation made by this paper is that modeling of threats and population evacuation has a significant effect on the design of an effective sensor network. Urban NBC sensor network design is also sensitive to wind direction and details of the urban environment.

Footnotes

Acknowledgment

An earlier version of this work appeared in the Proceedings of the 2006 IEEE International Workshop on Measurement Systems for Homeland Security, Contraband Detection and Personal Safety.

References

Onion

Considering the Unthinkable: Is the U.S. Ready to Handle Widespread Biological or Chemical Attacks?

2001

JAMA

Journal of American Medical Association: On-line Collection of Papers on Bio-terrorism

2004

Urbina

Antiterror test to follow winds and determine airborne paths

The New York Times February 2005 B1 B4

Anderson

D. A.

Tannehill

J. C.

Pletcher

R. H.

Computational Fluid Mechanics and Heat Transfer 1997

Washington, DC, USA

Hemisphere Publishing Company

Oran

E. S.

Boris

J. P.

Numerical Simulation of Reactive Flows 2000

Cambridge, UK

Cambridge University Press

Baum

McGrattan

K. B.

Rehm

R. G.

Three dimensional simulations of fire plume dynamics

Proceedings of the 5th International Symposium on Fire Safety Science

1997

511 522

Bera

Farouk

Lee

Y. H.

Simulation of thin carbon film deposition in a radio-frequency methane plasma reactor

Journal of the Electrochemical Society 1999 146 9 3264 3269

2-s2.0-0033360166

10.1149/1.1392465

Bera

Farouk

Vitello

Inductively coupled radio frequency methane plasma simulation

Journal of Physics D 2001 34 10 1479 1490

2-s2.0-0035926706

10.1088/0022-3727/34/10/308

Sohn

C. W.

Solberg

Gonsoulin

Analysis of numerical models for dispersion of chemical/biological agents in complex building environments

2004

Construction Engineering Research Laboratory

10.

Longsworth

T. K.

Testing of commercially available detectors against chemical warfare agents

Soldier and Biological Chemical Command 1999 1

AMSSB-REN, Aberdeen Proving Ground

11.

Murray

G. M.

Southard

G. E.

Sensors for chemical weapons detection

IEEE Instrumentation and Measurement Magazine 2002 5 4 12 21

2-s2.0-0036912647

10.1109/MIM.2002.1048978

12.

Army-Tech

NBC Sensor Equipment

Army Technology, 2006

13.

Hills

Sensing for danger: correlated sensor networks

Lawrence Livermore National Laboratory

2001

11 17

14.

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

A survey on sensor networks

IEEE Communications Magazine 2002 40 8 102 114

2-s2.0-0036688074

10.1109/MCOM.2002.1024422

15.

Dickey

Franklin

Harmon

Jeanings

Zimmerer

Nuclear, Biological, and Chemical (NBC) Communications Network

Proceedings of IEEE Systems and Information Engineering Design Symposium 2004 49 54

2-s2.0-3543068289

16.

Berry

Hart

Phillips

Uber

A general integer-programming-based framework for sensor placement in municipal water networks

Proceedings of the 6th Annual Symposium on Water Distribution Systems Analysis

2004

17.

NIST

NIST Special Publication 1018: Fire Dynamics Simulator

2005

NIST

Version 4

18.

Burstedde

Klauck

Schadschneider

Zittartz

Simulation of pedestrian dynamics using a two-dimensional cellular automaton

Physica A 2001 295 3-4 507 525

2-s2.0-0035876651

10.1016/S0378-4371(01)00141-8

19.

DTRA

Defense Threat Reduction Agency

2005

20.

Dhillon

S. S.

Chakrabarty

Ivengar

S. S.

Sensor placement for grid coverage under imprecise detections

Proceedings of the 5th International Conference on Information Fusion

September 2002

8 11

21.

Dhillon

S. S.

Chakrabarty

Sensor placement for effective coverage and surveillance in distributed sensor networks

IEEE Wireless Communications and Networking 2003 3 1609 1614

22.

Chiu

P. L.

Lin

F. Y. S.

A simulated annealing algorithm to support the sensor placement fot target location

Proceedings of the Canadian Conference on Electrical and Computer Engineering

May 2004

867 870

2-s2.0-5044238414

23.

Chakrabarty

Iyengar

S. S.

Cho

Grid coverage for surveillance and target location in distributed sensor networks

IEEE Transactions on Computers 2002 51 12 1448 1453

2-s2.0-0036933529

10.1109/TC.2002.1146711

24.

Zou

Chakrabarty

Sensor deployment and target localization based on virtual forces

Proceedings of the 22nd Annual Joint Conference on the IEEE Computer and Communications Societies

April 2003

1293 1303

2-s2.0-0042014539

25.

Szewczyk

Mainwaring

Polastre

Anderson

Culler

An analysis of a large scale habitat monitoring application

Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys ′04)

November 2004

214 226

2-s2.0-27644494768

26.

Suomela

Relay Placement in Sensor Networks

2005

27.

Arora

Dutta

Bapat

Kulathumani

Zhang

Naik

Mittal

Cao

Demirbas

Gouda

Choi

Herman

Kulkarni

Arumugam

Nesterenko

Vora

Miyashita

A line in the sand: a wireless sensor network for target detection, classification, and tracking

Computer Networks 2004 46 5 605 634

2-s2.0-6444240823

10.1016/j.comnet.2004.06.007

28.

Jaimes

Tweedie

Mago

Kreinovich

Ceberio

Optimal Sensor Placement in Environmental Research: Designing a Sensor Network under Uncertainty

29.

Maquin

Luong

Ragot

Observability analysis and sensor placement

Proceedings of IFAC/IMACS Symposium on Fault Detection, Supervision and Safety for Technical Processes (Safeprocess ′94)

1994

13 15

30.

Chen

Chuah

C. N.

Zhao

Network configuration for optimal utilization efficiency of wireless sensor networks

Ad Hoc Networks 2008 6 1 92 107

2-s2.0-34548841088

10.1016/j.adhoc.2006.09.001

31.

Bhondekar

A. P.

Vig

Lal Singla

Ghanshyam

Kapur

Genetic Algorithm Based Node Placement Methodology for Wireless Sensor Networks

32.

Spanache

Escobet

Travé-massuyès

Sensor placement optimisation using genetic algorithms

Proceedings of the 15th International Workshop on Principles of Diagnosis (DX ′04)

2004

179 183

33.

Shang

Wang

A wireless sensor network location algorithm based on simulated annealing

Proceedings of the 2nd International Conference on Biomedical Engineering and Informatics (BMEI ′09)

October 2009

2-s2.0-74049111335

10.1109/BMEI.2009.5304995

34.

Ray

Ungrangsi

De Pellegrini

Trachtenberg

Starobinski

Robust location detection in emergency sensor networks

Proceedings of the 22nd Annual Joint Conference on the IEEE Computer and Communications Societies

April 2003

1044 1053

2-s2.0-0041939727

35.

Litvak

Altaf

M. U.

Barbu

A. L.

Bokhove

Hurink

J. L.

Meinsma

Stolk

C. C.

Vellekoop

M. H.

Increasing detection performance of surveillance sensor networks

Proceedings of the 63rd European Study Group Mathematics with Industry

2008

Amsterdam, The Netherlands

85 115 CWI Syllabi

36.

Tezduyar

T. E.

CFD methods for three-dimensional computation of complex flow problems

Journal of Wind Engineering and Industrial Aerodynamics 1999 81 97 116

2-s2.0-0032846096

37.

McGrattan

K. B.

Baum

H. R.

Rehm

R. G.

Large Eddy simulations of smoke movement

Fire Safety Journal 1998 30 2 161 178

2-s2.0-0032026040

38.

Coirier

W. J.

Kim

Modeling for urban area contaminant transport and dispersion: model description and data requirements

Proceedings of the 6th American Meteorological Society Symposium on the Urban Environment

2006

39.

Peltier

L. J.

Haupt

S. E.

Wyngaard

J. C.

High fidelity modeling of urban features

J2.5

Proceedings of the 14th Joint Conference on the Applications of Air Pollution Meteorology with the Air and Waste Management Association AMS Forum: Environmental Risk and Impacts on Society: Successes and Challenges

January 2006

40.

FAST3D

Naval Research Laboratory

Laboratory for Computational Physics and Fluid Dynamics, 2006

41.

FEFLO

Naval research laboratory

Laboratory for Computational Physics and Fluid Dynamics, 2006

42.

Chan

S. T.

A three-dimensional model for simulating atmospheric dispersion of heavy-gases over complex terrain

Proceedings of the 10th Joint Conference on the Applications of Air Pollution Meteorology with the Air and Waste Management Association

1998

43.

Bengtson

Urban Dispersion Program

Pacific Northwest Laboratory, 2004

44.

Sagaut

Large Eddy Simulations for Incompressible Flows 1998

Berlin, Germany

Springer

45.

Kanda

Atmospheric boundary layer and scalar dispersion with explicit resolved urban geometries using Large Eddy Simulation for City (LES-CITY)

Proceedings of the 6th AMS Symposium on the Urban Environment

January-February 2006

J8.3

46.

Rehm

R. G.

McGrattan

K. B.

Baum

H. R.

Simiu

Efficient large Eddy simulation algorithm for computational wind engineering: application to surface pressure computations on a single building

1999 5490

NISTIR

47.

McGrattan

K. B.

Fire dynamics simulator (version 4) technical reference guide

July 2004 1018

NIST SP

48.

Huber

Freeman

Spencer

Schwarz

Bell

Kuehlert

Development and applications of CFD simulations supporting urban air quality and homeland security

Proceedings of the 6th AMS Symposium on the Urban Environment,

January-February 2006

J7.4

49.

Arya

S. A.

Air Pollution Meteorology and Dispersion 1999

Oxford, UK

Oxford University Press

50.

Trelles

McGrattan

K. B.

Baum

H. R.

Smoke transport by sheared winds

Combustion Theory and Modelling 1999 3 2 323 341

2-s2.0-0033150839

10.1088/1364-7830/3/2/307

51.

Forney

G. P.

Madryzkowski

McGrattan

K. B.

Sheppard

Understanding fire and smoke movement flow through modeling and visualization

IEEE Computer Graphics and Applications 2003 23 4 6 13

52.

Hamins

Maranghides

K. B.

McGrattan

Report on experiments to validate fire dynamics and thermal-structural models for use in the world trade center investigation

Sepember 2004

NIST

53.

McGrattan

K. B.

Baum

H. R.

Rehm

R. G.

Numerical simulation of smoke plumes from large oil fires

Atmospheric Environment 1996 30 24 4125 4136

2-s2.0-0030303639

10.1016/1352-2310(96)00151-3

54.

Rehm

R. G.

McGrattan

K. B.

Baum

H. R.

Large eddy simulation of flow over a wooded building complex

Wind and Structures 2002 5 2–4 291 300

2-s2.0-0036503181

55.

Gann

R. G.

Hamins

McGrattan

K. B.

Reconstruction of the fires in the world trade center towers. Federal building and fire safety investigation of the world trade center disaster

NIST NCSTAR September 2005 1–5

56.

Bania

T. C.

Chu

Effect of Intravenous HaHCO3 on toxicity from inhaled chlorine gas in an animal model

Society for Academic Emergency Medicine Annual Meeting

2006

57.

StarTec

Chlorine Properties

2006

58.

OSHA

Occupational Safety and Health Guideline for Chlorine

59.

Ophardt

C. E.

Virtual Chembook 2006

Elmhurst College

60.

Helbing

Molnár

Social force model for pedestrian dynamics

Physical Review E 1995 51 5 4282 4286

10.1103/PhysRevE.51.4282

61.

Reynolds

C. W.

Flocks, herds and schools: a distributed behavioral model

Computer Graphics 1987 21 4 25 34

2-s2.0-0023379184

62.

Sung

Gleicher

Chenney

Scalable behaviors for crowd simulation

Computer Graphics Forum 2004 23 3 519 528

2-s2.0-4644288155

10.1111/j.1467-8659.2004.00783.x

63.

Brogan

D. C.

Hodgins

J. K.

Group behaviors for systems with significant dynamics

Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems

August 1995

528 534

2-s2.0-0029206012

64.

Olfati-Saber

Flocking for multi-agent dynamic systems: algorithms and theory

IEEE Transactions on Automatic Control 2006 51 3 401 420

2-s2.0-33644997478

10.1109/TAC.2005.864190

65.

Still

G. K.

Crowd dynamics, Ph.D. thesis August 2000

University of Warwick

66.

Blue

V. J.

Adler

J. L.

Cellular automata microsimulation for modeling bi-directional pedestrian walkways

Transportation Research Part B 2001 35 3 293 312

2-s2.0-0035263565

10.1016/S0191-2615(99)00052-1

67.

Weifeng

Lizhong

Weicheng

Simulation of bi-direction pedestrian movement using a cellular automata model

Physica A 2003 321 3-4 633 640

2-s2.0-0037446075

10.1016/S0378-4371(02)01732-6

68.

Helbing

Tilch

Generalized force model of traffic dynamics

Physical Review E 1998 58 1 133 138

2-s2.0-0000217715

69.

Brenner

Wijermans

Nüssle

De Boer

Simulating and Controlling Civilian Crowds in Robocup Rescue

2005

70.

Bandini

Vizzari

Federici

M. L.

A Methodology for Crowd Modeling with Situated Cellular Agents

2005

71.

Bandini

Manzoni

Vizzari

Situated Cellular Agents for Crowd Simulation and Visualization

2004

72.

Schadschneider

Kirchner

Nishinari

CA Approach to Collective Phenomena in Pedestrian Dynamics

2002

73.

Schadschneider

Cellular automaton approach to pedestrian dynamics

Pedestrian and Evacuation Dynamics 2002

Berlin, Germany

Springer

75 84

74.

AMPL

AMPL Optimization LLC

2005

75.

Dandekar

Hamel

NBC Research Data

2004, http://wireless.ece.drexel.edu/research/homeland_sec.php

76.

Lin

G. Y.

Luby

R. E.

Wang

K.-Y.

New model for military operations

OR/MS Today 2004 31, article 2

77.

Jakobson

Lewis

Matheus

C. J.

Kokar

M. M.

Buford

Overview of situation management at SIMA 2005

Proceedings of the Military Communications Conference (MILCOM ′05)

October 2005

Atlantic city, NJ, USA

2-s2.0-33847359966

10.1109/MILCOM.2005.1605908

Sensor Placement for Urban Homeland Security Applications

Abstract

1. Introduction

2. Background

2.1. Sensor Network Design

2.2. Computational Fluid Dynamics

2.3. Assumed Threat

2.4. Pedestrian Evacuation

3. System Model

3.1. Sensor Placement Optimization

3.2. Population Evacuation

4. Simulations

4.1. Fallout Dispersal Prediction

4.2. Human Evacuation

5. Results

5.1. Fallout Dispersion Results

5.2. Effect of Sensors on Network Consumption

5.3. Civilian Evacuation Effects

5.4. Sensor Placement Results

5.4.1. Optimal Sensor Placement for Static Population Density

5.4.2. Optimal Sensor Placement for Variable Population Density

6. Conclusions

Footnotes

Acknowledgment

References