62 SENSOR DEPLOYMENT, SELF-ORGANIZATION, AND LOCALIZATION

Figure 2.42 Position estimation based on signal strength ranging: (a) outside and (b) lab.

estimates obtained indoors are terribly inaccurate. In fact, MDS/TKCRand does worse than a simple position estimation algorithm that places all floating nodes at (2, 4), the center of all anchors.

Ultrasonic-Based Ranging The ranging data were collected in three different environments: grass, grasscups, and pavement. In the grasscups environment, nodes were placed on top of cups on the grass to increase the range area. The topologies were the same for all three experiments. We focus on four configurations, namely Grass Grasscups, Grass Pavement, Grasscups Grass, and Grasscups Pavement. Grass Grasscups were a set of distance measurements taken in the grass environment with calibration coefficients obtained from the grasscups environment. As shown in Figure 2.43, the accuracy of the acoustic-based estimation is significantly better than that of signal-strength-based ranging from the ChipCon CC1000 radio.

Table 2.3 summarizes the results for time difference of arrival based on a distance estimation technique using concurrent ultrasonic and RF signals. The posErr in Table 2.3 is obtained from MDS using the censored distance estimation algorithms with four corner nodes at (3.08, 2.88), (0.45, 0.11), (4.24, 3.95), and (4.08, 1.22) as anchor nodes. TKCRand, TKCEuclid, and Path all perform well with respect to posErr in the grasscups environment. However, TKCEuclid and Path do not do as well in the grass environment compared with TKCRand. This is due to increased error in the grasscups environment compared to the grass environment. In this example, TKCRand is more robust against ranging errors. Figure 2.44 shows placements obtained by TKCRand.

Figure 2.45 is a histogram of posErr divided by the corresponding disErr from all experimental results. It is apparent that there is a correlation between disErr and posErr. We make the cautious claim that disErr is a good performance metric for a censored distance estimation algorithm. The ultimate performance metric for a censored distance estimation algorithm, however, needs to be determined from a metric based on positional error. The choice of the localization algorithm and the choice of the performance metric for position estimation can affect the preference for the censored distance estimation performance metric.

Figure 2.43 Accuracy of acoustic ranging: (a) grass trained on grasscups, (b) grass trained on pavement, (c) grasscups trained on grass, and (d) grass trained on pavement.

Table 2.3 Acoustic-Based Ranging Experimental Results

64 SENSOR DEPLOYMENT, SELF-ORGANIZATION, AND LOCALIZATION

Figure 2.44 Position estimation based on acoustic ranging: (a) grass trained on grasscups, (b) grass trained on pavement, (c) grasscups trained on grass, and (d) grasscups trained on pavement.

posErr / disErr

Figure 2.45 disErr as a metric for censored distance estimation algorithm: histogram of posErr/disErr.

Figure 2.46 Modeling of ranging error: Variance of ranging error versus distance: (a) acoustic and (b) signal strength.

2.4.6 Simulation Results

Our simulation models are based on the experimental results in the previous section. In the case of acoustic ranging, we model the ranging error on a Gaussian random variable with variance proportional to the square of the distance. Given a distance estimate δ(i, j ), the variance of error DVAR is modeled as

To obtain the scaling constant α, we fit square curves to the sample variance curve obtained from acoustic ranging data, as shown in Figure 2.46.

As for the signal strength data, we assume the variance to be constant over the distance measurements up to 11 m. We assume that the ranging area is roughly symmetrical. Figure 2.47 plots the probability of reliable distance measurement as a function of distance. For

Figure 2.47 Modeling of ranging area: Successful ranging versus distance: (a) acoustic and (b) signal strength.

Figure 2.48 Distance estimations (8 × 8gvc: 8 × 8, variable spacing, ChipCon CC1000): (a) shortest hop, (b) shortest path, (c) TKC random, and (d) TKC Euclidean.

and 2.55), nodes are placed on a 8 × 8 grid with varied spacing. The anchors are located at (0, 0), (0, 5.6), (5.6, 0), and (5.6, 5.6). In this example, TKCEuclid and TKCRand perform well (Fig. 2.55) thanks to the superiority of acoustic ranging compared to signal-strength- based ranging. Path performs better than with signal-strength-based ranging because the error from its preference of negative error is reduced. However, TKCEuclid and TKCRand both outperform Path because the uneven density of nodes negatively affects the performance of Path.

The second experiment (Figs. 2.56 and 2.57), denoted by 10 × 10g1a, nodes are placed on 10 × 10 grid with 1-m spacing with anchors at (0,0), (0,8), (8,0), and (8,8). In this example, TKCEuclid is clearly the best, as plotted in Figure 2.57. The Euclidean method is superior to the random resolution method due to accuracy of measurements. Poorer performance of Path comes from its preference for negative error as shown in Figure 2.56. As the number of hops increases, error due to the negative bias also increases.

Figure 2.50 Distance estimations (9-5 × 9-5g1c: 9-5 × 9-5, 1-m spacing, ChipCon CC1000): (a) shortest hop, (b) shortest path, (c) TKC random, and (d) TKC Euclidean.

and defining the breach probability on a grid-modeled field. Using a graph model for the perimeter, Dijkstra’s shortest-path algorithm is used to find the weakest breach path. The breach probability is linked to parameters such as the false alarm rate, size of the data record, and the signal-to-noise ratio. Consequently, the required number of sensor nodes and the surveillance performance of the network are determined. The false alarm rate and the field width turn out to be the two most influential parameters on the breach probability.

2.5.1 Background Information

Wireless sensor networks (WSN) are appropriate tools to monitor an area for surveillance. The primary challenges in building a surveillance wireless sensor network (SWSN) pertain to the decisions to be considered while deploying the sensors. These decisions may consist of communication and sensing range of sensor nodes and density of the SWSN, deployment strategy to be applied (random, regular, planned, etc.), and sink deployment. Depending on the range and the number of sensors, the sensing coverage area of the SWSN may contain