In the absence of calibrated data for the timeout parameters, we repeated the above set of experiments for different values of the parameters. The details are not listed here due to reasons of conciseness. We obtained similar experimental results in all cases.

2.2.7 Conclusion

We have presented a new scalable algorithm, termed SCARE, for self-configuration and adaptive reconfiguration in dense sensor networks. The proposed approach distributes the set of nodes into subsets of coordinator and noncoordinator nodes. It exploits the redundancy inherent in these networks to maintain coverage in the presence of node failure, as well as to prolong the network lifetime. We have presented a novel node replacement strategy that allows SCARE to use noncoordinator nodes to replace coordinator nodes that fail. We have presented simulation results to highlight the advantages of SCARE over a previously proposed topology management scheme Span for ad hoc networks.

2.3 ROBUST SENSOR POSITIONING IN WIRELESS AD HOC SENSOR NETWORKS

Xiang Ji and Hongyuan Zha

Wireless ad hoc sensor networks are being developed to collect data across the area of deployment. It is necessary to identify the position of each sensor to stamp the collected data or facilitate communication protocols. Most existing localization algorithms make use of trilateration or multilateration based on range measurements obtained from the received signal strength indicator (RSSI), the time of arrival (TOA), the time difference of arrival (TDoA), and angle of arrival (AoA). In this section, we first study some situations that most existing sensor positioning methods fail to perform well. An example of such situations is when the topology of a sensor network is anisotropic. We propose a distributed sensor positioning method with an estimation–comparison–correction paradigam to address these conditions. In detail, multidimensional scaling (MDS) technique is applied to recovering a series of local maps for adjacent sensors in two- (or three-) dimensional space. These maps are then stitched together to form a global map marking all sensors’ locations. Then, the estimated positions of anchor sensors are compared with their physical positions, to calculate adjustment parameters, with which sensors’ locations are calibrated by iterative process of estimation, comparison and correction. The method avoids measurement errors caused by anisotropic network topology and complex terrain, which previous research fail to address. We also study the application of MDS to centralized position estimation and present some related heuristic principles for collecting pairwise distances between sensors.

2.3.1 Background Information

Wireless ad hoc sensor networks have recently attracted much interest in the wireless research community as a fundamentally new tool for a wide range of monitoring and data-gathering applications. Many applications with sensor networks are proposed, such as habitat monitoring [24–27], health care [28, 29], battle-field surveillance and enemy tracking [30, 31], and environment observation and forecasting [32–34]. A general setup

36 SENSOR DEPLOYMENT, SELF-ORGANIZATION, AND LOCALIZATION

of a wireless sensor network consists of a large number of sensors randomly and densely deployed in a certain area. Each compact sensor usually is capable of sensing, processing data at a small scale, and communicating through omnidirectional radio signal [28, 35]. Because omnidirection radio signal attenuates with a distance, only sensors within a certain range can communicate with each other. This range is called hop distance R. Wireless sensor networks significantly differ from classical networks on their strict limitations on energy consumption, the simplicity of the processing power of nodes, and possibly high environmental dynamics.

Determining the physical positions of sensors is a fundamental and crucial problem in wireless ad hoc sensor network operation for several important reasons. We briefly list two of them in the following: First, in order to use the data collected by sensors, it is often necessary to have their position information stamped. For example, in order to detect and track objects with sensor networks, the physical position of each sensor should be known in advance for identifying the positions of detected objects. In addition, many communication protocols of sensor networks are built on the knowledge of the geographic positions of sensors [36–38]. However, in most cases, sensors are deployed without their position information known in advance, and there is no supporting infrastructure available to locate them after deployment. Although it is possible to find the position of each sensor in a wireless sensor network with the aid of Global Positioning System (GPS) installed in all sensors, it is not practical to use GPS due to its high power consumption, expensive price, and line-of-sight conditions. Thus, it is necessary to find an alternative approach to identify the position of each sensor in wireless sensor networks after deployment. In the general model of wireless ad hoc sensor network, there are usually some landmarks or nodes, called anchor nodes, whose position information is known, within the area to facilitate locating all sensors in a sensor network.

In the section, we first analyze some challenges of the sensor positioning problem in real applications. The conditions that most existing sensor positioning methods fail to perform well are the anisotropic topology of the sensor networks and complex terrain where the sensor networks are deployed. Moreover, cumulative measurement error is a constant problem of some existing sensor positioning methods [37, 39, 40]. In order to accurately position sensors in anisotropic network and complex terrain and avoid the problem of cumulative errors, we propose a distributed method that consists of iterations of estimation– comparison–correction. In detail, a series of local maps of adjacent sensors along the route from an anchor (starting anchor) to another anchor (ending anchor) are computed. We apply MDS, a technique that has been successfully used to capture the intercorrelation of high dimensional data at low dimension in social science, to compute the local maps (or relative positions) of adjacent sensors with high errortolerance. These local maps are then pieced together to get the approximation of the physical positions of the sensor nodes. Because the position information of the starting anchor is known, with the stitched maps, the position of the ending anchor can be estimated, which may be different from the true position of the ending anchor. When aligning the calculated position and the true position of ending anchor, the positions of sensors in the stitched maps will approximate their true positions effectively. With very few anchors (≥3), our approach usually generates more accurate sensor position information in a network with anisotropic topology and complex terrain than any other positioning method. The method is also efficient in eliminating cumulative measurement errors. At last, we also study the position estimation based on MDS in centralized paradigm and propose several heuristic models to efficiently collect pairwise distances in a wireless sensor network.

2.3.3 Challenges

Considering the real sensor network application scenario, there are several challenges in designing positioning algorithm. Since a large number (up to thousands) of sensors are usually used when they are densely deployed across a given area, we hope to achieve good position estimation as well as keep the hardware design of sensors simple and cheap. In many circumstances it is impossible to get a large number of anchor nodes deployed densely and uniformly to assist position estimation of nonanchor nodes. Thus, it is desirable to design a sensor positioning method that is able to generate accurate position estimation with as few anchors as possible. Third, sensors may be deployed in battle fields or urban areas with complex terrain and vegetation (Figs. 2.19 and 2.20). The sensor network may be badly anisotropic (Fig. 2.21). However, most existing research explored sensor positioning algorithms based on isotropic network topology in a square area. Neither their algorithms nor their experimental environment dealt with sensor network with anisotropic topology such as shown in Figures 2.19, 2.20, and 2.21. Finally, most of the previous methods estimate an average hop distance and broadcast it to the whole network. In many cases, sensors may be deployed on an area with anisotropic vegetation and terrain condition (Fig. 2.21). Thus, sensors at different portions of the area can have different hop distances, and a uniform hop distance in calculation will lead to nonnegligible errors [39, 41, 46] and serious cumulative errors [37, 40].

2.3.4 Calculating Relative Positions with Multidimensional Scaling

Multidimensional scaling (MDS), a technique widely used for the analysis of dissimilarity of data on a set of objects, can disclose the structure in the data [47–50]. We use it as a data-analytic approach to discover the dimensions that underlie the judgments of distance and model data in geometric space. The main advantage in using the MDS for position estimation is that it can always generate high accurate position estimation even based on limited and error-prone distance information. There are several varieties of MDS. We focus on classical MDS and the iterative optimization of MDS, the basic idea of which is to assume that the dissimilarity of data are distances and then deduce their coordinates. More details about comprehensive and intuitive explanation of MDS are available in [47–50].

Classical Multidimensional Scaling We will use T = [ti j ]2×n to record the physical positions of the n sensors deployed, each in two-dimensional space. The term di j (T ) represents the Euclidean distance between sensor i and j based on their positions in T , and we have

a=1

The collected distance between node i and j is denoted as δi j . If we ignore the errors in distance measurement, δi j is equal to di j (T ). We will discuss the error effects to position estimation caused by the differences between δi j and di j (T ) later. The expression X = [xi j ]2×n denotes the estimated positions of the set of n sensor nodes in two-dimensional (2D) space.

40 SENSOR DEPLOYMENT, SELF-ORGANIZATION, AND LOCALIZATION

If all pairwise distances of sensors in T are collected, we can use the classical multidimensional scaling algorithm to estimate the positions of sensors:

1.Compute the matrix of squared distance D2, where D = [di j ]n×n .

2.Compute the matrix J with J = I − e(eT /n), where e = (1, 1, . . . , 1).

3.Apply double centering to this matrix with H = − 12 J D2 J .

4.Compute the eigen-decomposition H = U V U T .

5.Suppose we want to get the i dimensions of the solution (i = 2 in the 2D case), we

denote the matrix of largest i eigenvalues by Vi and Ui the first i columns of U . The coordinate matrix of classical scaling is X = Ui Vi1/2.

Iterative Multidimensional Scaling In many situation, the distances between some pairs of sensors in the local area are not available. When this happens, the iterative MDS is employed to compute the relative coordinates of adjacent sensors. It is an iterative algorithm based on multivariate optimization for sensor position estimation in 2D space. Since only a portion of the pairwise distances are available, δi j is undefined for some i, j . In order to assist computation, we define weights wi j with value 1 if δi j is known and 0 if δi j is unknown and assume

δi j = di j (T )

in the following induction, where X is randomly initialized as X [0] and will be updated into X [1], X [2], X [3] . . . to approximate T with our iterative algorithm.

We hope to find the position matrix X to approximate T by minimizing

<

This is a quadratic function without containts. The minimum value of such functions is reached when its gradient is equal to 0. The update formula for the iterative algorithm is thus induced to

V = i < j wi j Ai j . If V −1 does not exist, we replace it with the Moore–Penrose inverse of

Vgiven by V − = (V + 11 )−1 − n−211 [47]. We summarize the iteration steps as:

1. Initialize X [0] as random start configuration, set T = X [0] and k = 0, and compute

σ (X [0]).

2.Increase the k by 1.

3.Compute X [k] with the above update formula and σ (X [k]).

4.If σ (X [k−1]) − σ (X [k]) < , which is a small positive constant, then stop; Otherwise set T = X [k] and go to step 2.

42 SENSOR DEPLOYMENT, SELF-ORGANIZATION, AND LOCALIZATION

adjacent group of sensors, at least three sensors’ physical positions are required in order to identify the physical positions of remaining nodes in the group in the 2D case. Thus, each group of adjacent sensors must contain at least three nodes with physical positions known, which can be anchors or nodes with physical positions calculated previously.

The alignment usually includes shift, rotation, and reflection of coordinates. R = [ri j ]2×n = (R1, R2, . . . , Rn ) denotes the relative positions of the set of n sensor nodes in two-dimensional space. T = [ti j ]2×n = (T1, T2, . . . , Tn ) denotes the true positions of the set

of n sensor nodes in two-dimensional space. In the following explanation, we assume the nodes 1, 2, and 3 are anchors. A vector Ri may be shifted to Ri(1) by Ri(1) = Ri + X , where X = Ri(1) − Ri . It may be rotated counterclockwise through an angle α to Ri(2) = Q1 Ri ,

where

S =

cos(β/2) sin(β/2)

to Ri(3) = Q2 Ri , where

Before alignment, we only know R and three or more anchor sensors’ physical positions T1, T2, T3. Based on them, we computer T4, T5, . . . , Tn . Based on the above rules, we have

(T4, T5, . . . , Tn ) = Q(R4 − R1, R5 − R1, . . . , Rn − R1) + (T1, T1, . . . , T1).

(2.7)

Distributed Physical Position Estimation An anchor node called starting anchor initializes flooding to the whole network. When other anchor nodes, called ending anchors, get the flooding message, they pass their positions back to the starting anchor along with the reverse routes from starting anchor to each of them. Then the starting anchor knows the positions of ending anchors and routes to each of them. Starting anchor estimates the positions of those sensors that are on these routes and one hop away from it. Figure 2.23