Int. J. Appl. Math. Comput. Sci., 2009, Vol. 19, No. 2, 291302 DOI: 10.

2478/v10006-009-0025-3

OPTIMIZATION SCHEMES FOR WIRELESS SENSOR NETWORK LOCALIZATION

E WA NIEWIADOMSKA-SZYNKIEWICZ , , M ICHA MARKS ,

Research and Academic Computer Network ul. Wawozowa 18, 02796 Warsaw, Poland

Institute of Control and Computation Engineering Warsaw University of Technology, ul. Nowowiejska 15/19, 00665 Warsaw, Poland e-mail: {ens,mmarks}@[Link]

Many applications of wireless sensor networks (WSN) require information about the geographical location of each sensor node. Self-organization and localization capabilities are one of the most important requirements in sensor networks. This paper provides an overview of centralized distance-based algorithms for estimating the positions of nodes in a sensor network. We discuss and compare three approaches: semidenite programming, simulated annealing and two-phase stochastic optimizationa hybrid scheme that we have proposed. We analyze the properties of all listed methods and report the results of numerical tests. Particular attention is paid to our techniquethe two-phase methodthat uses a combination of trilateration, and stochastic optimization for performing sensor localization. We describe its performance in the case of centralized and distributed implementations. Keywords: wireless sensor networks, localization, stochastic optimization, simulated annealing.

1. Introduction to localization techniques

Location awareness is required for many wireless sensor network applications, but it is often too expensive to include a GPS adapter in each sensor node. An approximated geographical location is needed for acquiring and managing data, geographic routing, geographic hash tables, energy conservation algorithms, and others. Hence, various localization schemes for assigning geographical coordinates to each node in a sensor network system are proposed. Localization methods should give a solution in a short time, achieve good accuracy even in the case of unevenly distributed nodes, and scale to large networks. A large number of research and commercial location systems have been developed over the past two decades. A general survey is found in (Hightower and Borriello, 2001; de Brito and Peralta, 2007). Recently, some localization techniques have been proposed to allow estimating node location using information transmitted by a set of anchor nodes. An anchor is dened as a node that is aware of its own location, either through a GPS adapter or manual deployment at a point with known position. The approaches to the localization differ in their as-

sumptions about network conguration and mobility, the distribution of the calculation process and, nally, hardware capabilities (Hu and Evans, 2004). We can distinguish four types of networks: static nodes, static anchor nodes and mobile non-anchors, mobile anchors and static non-anchors, mobile anchors and non-anchors. Location calculation can be conducted using one machine or calculations can be distributed. Centralized localization algorithms depend on sensor nodes transmitting data to a central computer, where calculation is performed to determine estimated location of each node. Distributed algorithms rely on self-organization of nodes in a sensor network. Each non-anchor node estimates its position based on the local data gathered from its neighbors. Requiring central computation involves high communication costs but, on the other hand, centralized methods are less complicated than distributed ones and they are likely to provide more accurate results. Considering hardware capabilities, we can distinguish two classes of available localization methods: distance-based (also called range-based) and connectivitybased (also called range-free). Distance-based techniques use inter-sensor distance or angle measurements in loca-

292 tion calculation. In accordance with the available hardware, they exploit received signal strength, time difference between arrival of two different signals, the time of arrival or the angle of arrival. Generally, the proposed solutions are based on signal processing and algorithms transforming measurements into the coordinates of the nodes in the network. The approaches for designing centralized distance-based algorithms provided in the literature include multidimensional scaling (MDS) (Shang et al., 2004; Ji and Zha, 2004), semidenite programming (SDP) (Biswas and Ye, 2004) and simulated annealing (Kannan et al., 2005; 2006). Connectivity-based algorithms use only the contents of the received messages to locate the entire sensor network. Popular connectivity-based algorithms are hop-counting techniques. Examples of connectivity-based methods are presented in (Niculescu and Nath, 2001; Doherty et al., 2001) and (Shang et al., 2004). Both distance-based and connectivity-based approaches have some weaknesses. Distance-based algorithms require additional equipment but through that we can reach ne resolution. Connectivity-based ones are cost effective but their performance is usually worse. In this paper we compare four centralized distancebased localization algorithms: utilizing semidenite programming (SDP), simulated annealing (SA), and our two schemestrilateration and simulated annealing (TSA), and trilateration and genetic algorithm (TGA). TSA and TGA are hybrid techniques that use a combination of the geometry of triangles, and stochastic optimization. We discuss the properties of all listed approaches based on the results of simulation experiments. We present a localization performance as a function of several sensor network characteristics, such as network size, nodes density and deployment. In the nal part of the paper we compare the performance of centralized and distributed versions of the TSA method. ing sets:

E. Niewiadomska-Szynkiewicz and M. Marks

Nk = {(k, j) : dkj rk }, j = 1, . . . , n, Ni = {(i, j) : dij ri }, j = 1, . . . , n, (1) where rk and ri are parameters representing maximal transmission ranges of the k-th anchor node and the i-th non-anchor node, respectively. The measured values dkj and dij of true physical distances dkj and dij are produced by measurement methods described in the literature (Anderson et al., 2007). These methods involve measurement uncertainty, hence each distance value dkj and dij represents the true distance corrupted with noise describing the uncertainty of the distance measurement, dkj = dkj + kj , dij = dij + ij , (2)

where kj and ij denote measurement errors. Hence, the general localization problem statement is as follows: Given noisy distance measurements dkj , dij l and positions of anchor nodes ak R , k = 1, . . . , m, estimate the locations of all nodes xj Rl , j = 1, . . . , n with unknown positions. We can formulate the model of the optimization problem that minimizes the sum of errors in sensor positions for tting the distance measurements. In the next two sections, we present two approaches to the problem solution. For simplicity, we assume that all sensors are placed on a plane. 2.1. Formulation for semidenite programming. The distance-based localization problem can be formulated as a quadratic optimization problem, and then transformed to a standard semidenite programming problem (Boyd et al., 1994). Semidenite programs are a generalization of linear programs, so to solve the transformed problem we can use the existing linear solvers. Such formulation of the localization task is presented in (Biswas and Ye, 2004). Let us consider the network of n non-anchors and m anchors. For each pair of two nodes, we introduce (based on measurements) the upper bound dmax and lower bound kj min to the Euclidean distance between ak and xj , and dkj upper bound dmax and lower bound dmin to the Euclidean ij ij distance between xi and xj . Then, the model of the localization problem can be dened as
m n

2. Localization problem formulation

The mathematical model of the WSN localization problem can be described as follows: Assume we have a set of m sensors (anchor nodes), each with known position expressed as l-dimensional coordinates ak Rl , k = 1, . . . , m, and n sensors (non-anchor nodes) xj Rl , j = 1, . . . , n with unknown locations. For each pair of two nodes in the network, we introduce the Euclidean distance, i.e., dkj = ||ak xj || between anchors and nonanchors, and dij = ||xi xj || between two non-anchors, j = 1, . . . , n and i = j. In practical applications of distance-based methods, each sensor emits a known signal that allows the neighboring nodes to estimate their distances. We dene sets of neighboring nodes as collections of nodes located within transmission ranges (radio ranges) of given nodes. Hence, for all anchors and non-anchors we introduce the follow-

min JSDP =
x k=1 jNk

ekj +
i=1 jNi

eij

(3)

subject to (dmin )2 eij xi xj ij (dmin )2 ekj kj

2

(dmax )2 + eij , ij

i = j, j Ni , 2 ak xj (dmax )2 + ekj , kj k, j, j Nk

(4) (5)

Optimization schemes for wireless sensor network localization

where ekj 0 and eij 0 denote errors in sensor position estimates, xi and xj are estimated positions of nodes i and j, respectively, and Ni , Nk are sets of neighboring nodes dened in (1). Let X = [x1 , x2 , . . . , xn ] be the 2 n matrix that needs to be determined. Our problem may be transformed and formulated in matrix form. The following approach converts quadratic distance constraints into linear constraints by introducing a relaxation to remove the quadratic term in the formulation. Let Y = X T X. This constraint can be relaxed to Y X T X, which is equivalent to a linear matrix inequality (e.g., (Boyd et al., 1994)): Z= I XT X Y 0,

293 where xi and xj denote, respectively, estimated positions of nodes i and j, dkj and dij are measured distances between the pairs of nodes (k, j) and (i, j), and Ni , Nk are sets of neighboring nodes dened in (1). Three stochastic methods, SA, TSA and TGA, were used to solve the optimization problem (13). 2.2.1. Simulated annealing method. Simulated annealing is a well-known heuristic used to solve the localization problem (13) (Anderson et al., 2007; Kannan et al., 2005; 2006). It is implemented as a computer simulation of a stochastic process. It performs point-to-point transformation. For our research, we implemented the SA method similar to the algorithm presented in (Kannan et al., 2005). It is a classical version of SA with one modicationthe cooling process is slowed down. At each value of the coordinating parameter T (temperature), not one but P n non-anchor nodes are randomly selected for modication (where n denotes the number of sensors with unknown positions in the network and P is a reasonably large number to lead the system into thermal equilibrium). The SA algorithm is presented Algorithm 1 as below. In each iteration of the algorithm, a new solution, i.e., a vector of new nodes positions is calculated. A given node is randomly selected and is moved in random direction at distance d. The value of d depends on the control parameter T and is restricted by the shrinking factor < 1, dnew = d. A simple cooling scheme is proposed, Tnew = T , where T is the previous value of the temperature parameter. The coordinating parameters of the SA method, i.e., the initial temperature T0 , Tf , d0 , P , and have to be experimentally tuned. 2.2.2. TSA and TGA methods. The hybrid localization techniques TSA and TGA use a combination of the Algorithm 1 Simulated annealing algorithm
1: T = T0 , T0 initial temperature, Tf nal temperature 2: d = d0 , d0 initial move distance 3: while T > Tf do 4: for i = 1 to P n do 5: select a node to perturb 6: generate a random direction and move a node at distance d 7: evaluate the change in the cost function, JSO 8: if (JSO 0) then 9: //downhill move accept it 10: accept this perturbation and update the solution 11: else 12: //uphill move accept with probability 13: pick a random probability rp = uniform(0,1) 14: if (rp exp(JSO /T )) then 15: accept this perturbation and update the solution 16: else 17: reject this perturbation and keep the old solution 18: end if 19: end if 20: end for 21: change the temperature: Tnew = T , T = Tnew 22: change the distance dnew = d, d = dnew 23: end while

where the relation Z 0 means that Z is positive semidenite, i.e., y T Zy 0 for all y Rn . Then, the problem (3)(5) can be formulated as a standard SDP problem:
m n

min JSDP =
x k=1 jNk

ekj +
i=1 jNi

eij

(6)

subject to (1; 0; 0)T Z(1; 0; 0) = 1, (0; 1; 0) Z(0; 1; 0) = 1,

T T

(7) (8) (9) + eij ,

(1; 1; 0) Z(1; 1; 0) = 2, (dmin )2 ij eij (0; vij ) Z(0; vij )

T

(dmax )2 ij

(dmin )2 ekj kj

j Ni , (10) (ak ; vj )T Z(ak ; vj ) (dmax )2 + ekj , kj k, j, Z 0, j Nk , (11) (12)

i = j,

where vij is the vector with 1 in the i-th position, 1 in the j-th position and zero everywhere else; vj is the vector of zeros except 1 in the j-th position, eij 0 and ekj 0. The optimization problem (6)(12) can be effectively solved by interior point method based SDP solvers available for optimization research community, such as, for example, SeDuMI (Sturm, 1999) or CSDP (Borchers, 1999). 2.2. Formulation for stochastic optimization. Another approach is to formulate the optimization problem (13) with a nonlinear performance function and apply stochastic methods to solve it:
m

min JSO =
x k=1 jNk n

(||ak xj || dkj )2 (13)

2

+
i=1 jNi

(||i xj || dij ) x

294 trilateration method, and stochastic optimization (Marks and Niewiadomska-Szynkiewicz, 2007). The algorithms operate in two phases. In the rst phase, an auxiliary solution (initial localization) is provided. The solution of the rst phase is modied by applying stochastic optimization methods. Various techniques, such as simulated annealing (Dekkers and Aarts, 1991) or genetic algorithms (Goldberg, 1989), can be applied. In this paper we compare both of them. Additional functionality (correction) is introduced to the second phase of the algorithm to remove incorrect solutions involved by the distances measurement errors. Phase ITrilateration. In the rst phase a simple method of determining the relative positions of objects using the geometry of triangles is applied. Trilateration uses the known locations of anchor nodes ak , k = 1, . . . , m, and the measured distances between pairs of nodes. To accurately and uniquely determine relative location of a non-anchor on a 2D plane using trilateration alone, generally at least three neighbors with known positions are needed. Hence, all nodes are divided into two groups: group G1, containing m nodes with known location (at the beginning only the anchor nodes), and group G2, of n nodes with unknown location. In each step of the algorithm, node i, where i = 1, . . . , n from the group G2 is chosen. Next, the three nodes from the group G1 that are within node i radio range are randomly selected. If such nodes exist, the location of node i is calculated based on inter-nodes distances between three nodes selected from the group G1 and the measured distances between node i and these three nodes. The localized node i is moved to the group G1. Otherwise, another node from the group G2 is selected, and the operation is repeated. The rst phase stops when there are no more nodes that can be localized based on the available information about all nodes localization. It switches to the second phase. Phase IIStochastic optimization. Due to distance measurement uncertainty, the coordinates calculated in Phase I are estimated with non-zero errors. In addition, the position of nodes that have less than three localized neighbors cannot be estimated. In the second phase, stochastic optimization is applied to increase the accuracy of the location estimation calculated in Phase I. Two variants are proposedTSA utilizing the simulated annealing algorithm as presented in Algorithm 1, and TGA utilizing a genetic algorithm. In TGA, abstract representations of candidate solutions (chromosomes) are vectors of a random variablecoordinates of all non-anchor nodes, [x1 , y1 , x2 , y2 , . . . , xn , yn ], xi , yi R. The initial population consists of a set of such chromosomes. The tness function is dened in (13). At the reproduction (preselection) stage, tournament selection of size two is used.

E. Niewiadomska-Szynkiewicz and M. Marks

Fig. 1. Correct and incorrect node locations.

The crossover operator is dened as discrete recombination similar to elements exchanging applied to binary vectors. Both coordinates are recombined simultaneously. The mutation operator modies the components of a given chromosome by adding a vector of generated 2 n Gaussian random variables. The elitist succession model is chosen. Phase IICorrection. From the simulation experiments it was observed that the increased value of the location error is usually driven by incorrect location estimates calculated for a few nodes. Usually, the number of such incorrect results is not big, so the inuence on the cost function (13) is not very strong and it is ignored by the optimization algorithm. This phenomenon is depicted in Fig. 1. Let us consider three nodes, A, B, C, with known locations and measured distances between the node D to be localized and the nodes A, B, C. We can determine the coordinates of the nodes D and D based on the distances dAD and dBD . As a nal result, the location D should be selected, but in the case of non-zero measurement errors the incorrect location, i.e., D will be chosen. The low quality of measurements may involve inaccurate location estimates. To alleviate this phenomenon, new functionality is added to our algorithmthe correction operation performed during the second phase execution. Its objective is to make correction in the location estimates. The correction is triggered every iteration of the optimization process when the value of the performance function JSO dened in (13) is less than the assumed threshold value , and the following algorithm is performed. Three nodes from the group of neighbors of a given node i that violate a smaller number of the constraints (1) than the other nodes are randomly selected. The roulette selection algorithm is used. Next, the position of node i is calculated based on the selected nodes locations. If the new location is more accurate, i.e., it violates a smaller number of the constraints (1), it replaces the previous one. The correction operation is repeated until all constraints are fullled or the assumed number of iterations is achieved.

Optimization schemes for wireless sensor network localization

The threshold value used in the correction operation depends on the number of anchor nodes, the deployment of all nodes in the area, the power of radio devices and the expected noise measurement factor nf . It is calculated according to the following formula: = nf s2 , nf s2 ,
m n+m m n+m

295
Table 1. Assumed transmission ranges for different networks. Number of nodes Radio range (r) 200 0.18 500 0.12 1000 0.08 2000 0.06 4000 0.04 5000 0.04 10000 0.03

< , ,

(14)

where nf is a noise measurement factor, , and are experimentally tuned parameters. The variable s denotes the average number of neighbors of all nodes creating a network: n+m 1 cij , (15) s= n + m i=1
jNi

where cij =

1, j Ni , 0, j Ni , /

where m is the number of anchor nodes, n is the number of non-anchors, cij is the connectivity between i and j nodes, and Ni is a set of neighbors of node i. The SDP, SA, TSA and TGA schemes in their original versions require centralized computation. Namely, all nodes must transmit their destination information to a central computer to solve the optimization problems (3)(5) or (13). In this paper we focus on the location estimation task and no further consideration is given to communication aspects (protocols, bandwidth limitation, congestions, etc.).

We assumed the following values of the parameters used by the SA Algorithm 1: = 0.8, = 0.94, T0 = 0.1, Tf = 10e12, d0 = 0.1 and P = 4. The value of P was calculated as a solution of the two-criterion optimization problem. The obtained result was a trade off between the accuracy of location estimation and the time of calculation. The parameters , and in (14) used to calculate the threshold value in the correction operation were = 0.2, = 0.1 and = 0.05. For the purpose of simulation experiments, we need the values of measured distances between neighboring nodes i and j. To compare the performance of our twophase scheme with algorithms developed by other researchers, we assumed that the measurement errors kj and ij in (2) were independent zero-mean Gaussian random variables of unit variance. Such an approach is provided in most of the literature devoted to WSN localization (Anderson et al., 2007; Kannan et al., 2006). Hence, in our experiments the measured distances dkj and dij were assumed to be dkj = dkj (1 + randn() nf ), dij = dij (1 + randn() nf ), (16)

3. Numerical results
In order to evaluate the described approaches to sensor network localization, many numerical tests were performed for multihop network topologies. We compared the results obtained using semidenite programming, pure simulated annealing and our two-phase algorithmsthe TSA and TGA schemes. We performed a variety of simulation experiments to cover a wide range of network system congurations including the size of the network (number of nodes), the number of anchor nodes, anchor nodes deployment, the radio range, the distance measurement error and computation time. The key metric for evaluating all listed methods was the accuracy of the location estimates versus the deployment, equipment, communication and computation cost. 3.1. Simulation parameters. The sensor networks with 20010000 nodes with randomly generated positions in a square region [0, 1] [0, 1] were considered. The number of anchor nodes was 10% of all nodes. We assumed a xed transmission range r for all devices in each considered network, equal to that presented in Table 1.

where dkj and dij denote true physical distances between pairs of nodes, and nf is a noise factor. In most of the presented experiments, we assumed nf =10%. We realize that the uncorrelated-Gaussian measurement error does not capture all practical cases but it is a good starting point for exposing error trends in sensor networks. Due to measurement uncertainty, it is difcult to nd a good metric to compare the results obtained using different localization methods. To evaluate the performance of the tested algorithms, we used the mean error between the estimated and the true physical location of non-anchor nodes in the network, dened as follows: LE = 1 n
n i=1

(||i xi ||)2 x 100%, 2 ri

(17)

where LE denotes a localization error, xi is the true position of sensor node i in the network, xi is the estimated location of sensor node i, and ri is the radio transmission range of the node i. The localization error is expressed as a percentage error. It is normalized with respect to the

296

E. Niewiadomska-Szynkiewicz and M. Marks

Fig. 2. Inuence of correction on localization accuracy.

Fig. 3. Final network nodes localization (Phases I and II). Table 2. Localization errors in two phases of the TSA method. Phase Localization error (LE) [%] I 10.64 II 0.14

radio range to allow a comparison of results obtained for different size and range networks. The calculations were carried out using an Intel Core2 Duo E6600, 2.4GHz, 2GB RAM computer. The presented experimental results are the average of ve executions of each task. They are summarized in tables and gures. 3.2. Two-phase method evaluation. This section provides a detailed analysis of the performance of the twophase scheme for node localization. We analyze the properties of our technique and report the results of numerical tests performed for a wide range of network system congurations including the size of the network (number of nodes), the number of anchor nodes, the radio range, the distance measurement error and computation time. We present the results obtained for the TSA variant of the twophase technique. 3.2.1. TSA operation. The results of the rst series of simulations presented in Table 2 and Figs. 23 show the estimates of the positions of non-anchor nodes calculated

in both phases of the TSA method, and before and after correction operation. A sensor network consisting of 200 nodes20 anchor nodes (marked with diamonds) and 180 non-anchor nodes (marked with circles) was considered. The estimated positions of non-anchor nodes are marked with stars in the gure. The localization error as dened in (17) is denoted by lines connecting the real and estimated locations. As has been described, the TSA scheme consists of two phases and additional functionalitycorrection introduced to the second phase. The objective of the correction is to remove incorrect solutions involved by the distance measurement errors. Figure 2 presents the results of the correction operation. The coordinate estimats calculated at the rst iteration of the second phase, and before and after the correction are compared. From the simulation experiments we observed that the localization

Optimization schemes for wireless sensor network localization

297

Fig. 4. Impact of the network size on localization accuracy.

Fig. 6. Impact of distance measurement errors on localization accuracy. Table 3. Localization error and computation times for different network sizes. Number Localization Computation of nodes error (LE) [%] time [s] 200 0.16 0.44 500 0.11 2.44 1000 0.16 8.75

on the distance measurement (16) used in our simulations, and nally on the localization accuracy. The noise factor considered was from the range [0, 26%]. 3.2.5. Computation time and scalability. In the described variant of the TSA method, the whole computations are performed centrally on a single machine. In the case of a large scale network, computation time can limit the application of centralized localization techniques. We performed multiple tests of the TSA application for sensor networks with different numbers of nodes. Selected results are presented in Table 3. From the experimental results we observed that the computation time increased proportionally to the square of the number of nodes. 3.3. Comparison of localization techniques. 3.3.1. Localization accuracy and computation time. Next, the results obtained for the TSA and TGA schemes were compared with those obtained applying the SDP and SA methods. Table 4 presents the localization errors and computation times obtained for all methods considered. From this table, we can see that the TSA and TGA methods estimate the location of nodes quite accurately, with the localization error less than 3% (especially in the case of TSA, with the localization error equal to 0.16%). The localization errors for the SDP and SA algorithms and the same network are about 30%. In this experiment the positions of anchor nodes were generated randomly. The same WSN network was considered in the case of all tested methods. 3.3.2. Node deployment. Localization accuracy strongly depends on node location in the network. In

Fig. 5. Impact of the radio range on localization accuracy.

error was reduced from 6.25% to 3.04% after the correction operation. The value of reduction depends on nodes deployment. Figure 3 and Table 2 present the calculated positions of nodes the nal results of both phases. 3.2.2. Number of anchor nodes. We analyzed the effect of varying the number of anchors on the localization error (17). The results for the TSA method are summarized in Fig. 4. It shows that the localization error decreases as the number of anchor nodes increases. Increasing the density of anchors makes location easier, but it increases the network size and deployment costs. A trade off is necessary. 3.2.3. Radio range. The value of the transmission range r determines the number of neighbors of each node in the network. It has a substantial impact on localization accuracy depending on distance-based techniques. At a low level of r, the rst phase of the TSA algorithm may perform poorly. Figure 5 shows the impact of the value of r on the localization error. The radio range considered was from the interval [0.1, 0.24]. 3.2.4. Measurement uncertainty. The accuracy of localization techniques based on inter-node distance measurements strongly depends on measurement errors. Figure 6 shows the impact of the value of the noise factor nf

298

E. Niewiadomska-Szynkiewicz and M. Marks

Fig. 7. Network with evenly distributed anchors. Table 4. Computing time and localization errorsdifferent methods. Method Localization Computation error (LE) [%] time [s] SDP 32.04 6.21 SA 34.34 2.94 TSA 0.16 0.44 TGA 2.34 2.91 Table 5. Computing time and localization errorvarious deployment of anchor nodes. Task anchors evenly distributed Method SDP SA TSA TGA SDP SA TSA TGA SDP SA TSA TGA SDP SA TSA TGA Localization error [%] 0.18 2.76 0.13 3.80 174.91 233.89 1.78 20.61 330.56 293.01 1.81 56.06 434.83 446.13 433.09 133.78 Computation time [s] 6.95 3.04 0.46 2.85 5.51 2.85 0.44 2.34 6.25 3.06 0.47 2.90 8.95 3.84 0.61 3.46

the rst series of experiments we analyzed networks with evenly distributed non-anchor nodes, and evenly and unevenly distributed anchors in the square region considered. The performance differences between the SDP, SA, TSA and TGA methods were compared. If the anchor nodes are evenly distributed, then we obtain quite accurate solutions using all four methods (see Fig. 7), otherwise the results of location estimation are much worse and in some cases not satised (see Fig. 8). Table 5 and Fig. 8 show that the TSA method is much more robust with respect to the anchor distribution than the SDP and SA ones. In contrast to the SDP and SA methods, TSA gives satisfactory accuracy in location estimation for networks with anchor nodes deployed only in a part of the region to

anchors unevenly distributed

be covered by sensors, cf. Figs. 8(a) and 8(b) and evenly distributed non-anchors. Next, the experiments with both anchors and nonanchors only in some parts of the considered domain con-

Optimization schemes for wireless sensor network localization

299

Fig. 8. Network with unevenly distributed anchors.

300 centrated were performed. From Table 5 and Fig. 8 we see that TSA, similarly to SDP and SA, gives an unsatisfactory solution. As a nal result, we can say that it is not suggested to apply distance-based localization methods to networks with unevenly distributed non-anchor and anchor nodes.

E. Niewiadomska-Szynkiewicz and M. Marks

4. Distributed version of the two-phase scheme

4.1. Implementation. The centralized two-phase method provides quite accurate location estimates even in the case of unevenly distributed nodes with known positions. However, we have to gather measurements of distances between all pairs of network nodes in a single computer to solve the optimization problem (13). The data transmission to the central station involves time delays, high communication cost and high energy consumption. Because of these disadvantages, centralized techniques cannot be employed in many applications (e.g., mobile networks and large scale networks). In contrast to the centralized method, we proposed a fully distributed technique where all nodes are involved in the calculation process. Each node is responsible for determining its position using information about its neighbors. It offers a signicant reduction in computation requirements because usually the set of neighbors consists of several nodes, so the number of connections is usually a few orders of magnitude less. A fully distributed computation model is also tolerant to node failures, and it distributes the communication cost evenly across the nodes. On the other hand, in the case of a distributed variant of the algorithm, a loss of information may occur. There are two reasons for that: the loss of information due to parallel computation and the loss of information due to an incomplete network map. The loss of information due to parallel computation is connected with the way how optimization in the second phase of the method is performed. For example, in TSA, at each value of the coordinating parameter T (temperature), P times n non-anchor nodes are randomly selected for modication, i.e., coordinate estimates of chosen nodes are perturbed with a small distance d in a random direction. Modications are done in orderthe location of a current node is determined based on the previous transformations. In a distributed algorithm each node has to perform P small displacements. This is done in parallel and the information is exchanged between neighboring nodes every P iterations. An example is presented in Fig. 9. The node considered (marked with a square) updates the location using the information about previous positions of its neighbor nodes (lighter circles). Because all movements are done independently and simultaneously, there is no guarantee that the performance value is better after the iteration.
Fig. 9. Parallel node displacements. Table 6. Localization errors for one-hop and two-hop correctiondifferent deployment of anchors. Localization error (LE) [%] Task 1-hop 2-hop neighbor correction neighbor correction anchors evenly 0.34 0.31 distributed anchors unevenly 12.84 3.01 distributed

The loss of information due to an incomplete network map has a major impact on the correction. The correction operation depends on the neighborhood constraints (1) involved in the transmission range. In the centralized approach, a complete network state (location estimates of all nodes) is available. Due to this information, it is possible to detect the situation when the estimated distance between two neighbor nodes is greater than the transmission range. In the same way it can be detected that the estimated distance between two nodes is less than the transmission range, but due to the data of the whole network these nodes cannot be in neighborhood. In the distributed approach, the situation is different. Certainly, each node can detect the situation when the estimated distance between it and its neighbor is greater than the transmission range, but it is impossible to nd out that from the estimated location it appears that the node is close to another node which is not a true neighbor. In order to overcome this problem, we propose to modify the correction operation. In the centralized scheme all neighbors are considered. In the distributed one, we distinguish two versions: the basic oneonly one-hop neighbors are considered, and the extended oneboth, one-hop and two-hop neighbors are considered. In Table 6, the results obtained for networks with evenly and unevenly distributed anchors with one-hop neighbor and two-hop neighbor correction are presented. 4.2. Comparison of centralized and distributed TSA. Figure 10 presents the solution quality difference between

Optimization schemes for wireless sensor network localization

301 implementation improves scalability and reduces the calculation complexity, but it decreases location estimation accuracy, especially in the case of unevenly distributed nodes with known positions. There are several directions for future research. First, we plan to extend our technique to mobile networks (MANET). Second, we are going to perform experiments using software environments for sensor networks simulation and, nally, apply the two-phase method to a testbed network of sensors in the laboratory to verify its properties in real-life applications.

Fig. 10. Localization error for the centralized and distributed algorithms.

Acknowledgment
This work was partially supported by the Polish Ministry of Science and Higher Education under Grant No. NN514 416934.

the centralized and distributed TSA algorithms (using two-hop correction). The obtained results conrm that, from the perspective of location estimation accuracy, the centralized algorithm provides more accurate location estimates than the distributed one. As a nal result, we can say that for evenly distributed anchors we obtain quite accurate solutions using both methods, otherwise the results of location estimation are much worse in the case of the distributed version of our scheme.

References
Anderson, B. D. O., Mao, G. and Fidan, B. (2007). Wireless sensor network localization techniques, Computer Networks 51(10): 25292553. Biswas, P. and Ye, Y. (2004). Semidenite programming for ad hoc wireless sensor network localization, IPSN 04: Proceedings of the 3-rd International Symposium on Information Processing in Sensor Networks, Berkeley, CA, USA, ACM Press, New York, NY, pp. 4654. Borchers, B. (1999). CSDP, a C library for semidenite programming, Optimization Methods & Software 11(1-4): 613623. Boyd, S., Ghaoui, L. E., Feron, E. and Balakrishnan, V. (1994). Linear Matrix Inequalities in System and Control Theory, SIAM, Philadelphia, PA. de Brito, L. M. P. L. and Peralta, L. M. R. (2007). Collaborative localization in wireless sensor networks, SENSORCOMM 2007: Proceedings of the International Conference on Sensor Technologies and Applications, Valencia, Spain, IEEE Computer Society, pp. 94100. Dekkers, A. and Aarts, E. (1991). Global optimization and simulated annealing, Mathematical Programming 50(8): 367393. Doherty, L., Pister, K. and Ghaoui, L. E. (2001). Convex postion estimation in wireless sensor networks, INFOCOM 2001: Proceedings of the 20-th Annual Joint Conference of the IEEE Computer and Communications Societies, Anchorage, USA, pp. 16551663. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning, Studies in Applied Mathematics, Addison-Wesley, Boston, MA. Hightower, J. and Borriello, G. (2001). Localization systems for ubiquitous computing, Computer 34(8): 5766. Hu, L. and Evans, D. (2004). Localization for mobile sensor networks, MobiCom 2004: Proceedings of the 10-th Annual International Conference on Mobile Computing and Networking, Philadelphia, PA, USA, IEEE Computer Society, pp. 4557.

5. Summary and conclusions

Many applications of wireless sensor networks depend on accurate determination of the positions of all network nodes. The paper provides a review of more representative localization techniques based on measurements of inter-sensor distances. Two methodologies for formulating a sensor network position estimation problem as a linear and a nonlinear task and the application of linear programming and stochastic algorithms to solve them are presented. We describe and investigate novel distancebased methodstwo-phase TSA and TGA schemes that combine simple geometry of triangles and stochastic optimization algorithms to determine the location of nodes with unknown positions in the sensor network. The originality in our approach is the combination of deterministic and stochastic techniques and adding the additional operationcorrectionto simulated annealing and genetic algorithms. The simulation experiments demonstrate that our method gives accurate location estimates in sensible computing time even in the case of unevenly distributed nodes with known positions, and it outperforms localization schemes based on semidenite programming and pure simulated annealing under a wide range of conditions. Numerical results conrm that TSA and TGA are efcient and robust localization algorithms. Most works devoted to sensors localization describe techniques implemented a centralized manner. We compare the implementation of TSA both in a centralized and a distributed manner. The conclusion is that distributed

302
Ji, X. and Zha, H. (2004). Sensor positioning in wireless adhoc sensor networks with multidimensional scaling, INFOCOM 2004: Proceedings of the 23-rd Annual Joint Conference of the IEEE Computer and Communications Societies, Hong Kong, China, pp. 26522661. Kannan, A. A., Mao, G. and Vucetic, B. (2005). Simulated annealing based localization in wireless sensor network, LCN 05: Proceedings of the IEEE Conference on Local Computer Networks. 30-th Anniversary, Sydney, Australia, IEEE Computer Society, pp. 513514. Kannan, A. A., Mao, G. and Vucetic, B. (2006). Simulated annealing based wireless sensor network localization with ip ambiguity mitigation, Proceedings of the 63-rd IEEE Vehicular Technology Conference, Melbourne, Australia, pp. 10221026. Marks, M. and Niewiadomska-Szynkiewicz, E. (2007). Twophase stochastic optimization to sensor network localization, SENSORCOMM 2007: Proceedings of the International Conference on Sensor Technologies and Applications, Valencia, Spain, IEEE Computer Society, pp. 134 139. Niculescu, D. and Nath, B. (2001). Ad hoc positioning system (APS), GLOBECOM: Proceeding of the Global Telecommunications Conference, San Antonio, CA, USA, pp. 2926 2931. Shang, Y., Ruml, W., Zhang, Y. and Fromherz, M. (2004). Localization from connectivity in sensor networks, IEEE Transactions on Parallel and Distributed Systems 15(11): 961 974.

E. Niewiadomska-Szynkiewicz and M. Marks

Sturm, J. F. (1999). Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optimization Methods & Software 11(1-4): 625653.
Ewa Niewiadomska-Szynkiewicz received her Ph.D. degree in 1996 and her [Link]. degree in 2006 in control and computation engineering. Since 1987 she has been with the Warsaw University of Technology as the head of the Complex Systems Group and since 2000 with the Research and Academic Computer Network (NASK) as the head of the Network Modeling and Simulation Group. Her research interests focus on complex systems modeling and control, computer simulation, global optimization, parallel computations, and computer networks.

Micha Marks received his [Link]. degree in computer science from the Warsaw University of Technology, Poland, in 2007. Currently he is a Ph.D. student at the Institute of Control and Computation Engineering of the same University. Since 2007 he has been with the Research and Academic Computer Network (NASK). His research area focuses on global optimization, multiple criteria optimization, decision support, and machine learning.

Received: 3 July 2008 Revised: 15 February 2009