2010 Third International Joint Conference on Computational Science and Optimization

An Optimization Algorithm for Wireless Sensor Networks Localization Using

Multiplier Method

Caixia Li, Yuanjie Li, Yu Shen, Linlang Liu, Qiying Cao*

College of Information Science and Technology, Donghua University, Shanghai, 201620, China
E-mail: li-cx2@[Link], caoqiying@[Link]

Abstract—One of the main problems facing sensor localization performance of our method is better than traditional TOA
in wireless communication systems is accuracy. In this paper, method.
we propose an optimization algorithm for wireless sensor The paper is organized as follows: section II summarizes
networks localization based on time-of-arrival (TOA) related work in the area; section III describes our proposed
technique. The optimal points are determined by the iteration CoTOA approach where subsection A introduces equality
process of multiplier method, and the unknown positions are constrained optimization theory, subsection B presents a
gotten. Simulation results show that the optimization method brief overview of the CoTOA localization model and
can improve the localization accuracy of traditional time-of- subsection C introduces the multiplier method based
arrival TOA locating method. The optimization localization
resolution for the CoTOA localization model; section IV
algorithm for wireless sensor networks using multiplier
method can effectively minus the sum of errors and thus
presents simulation results. We conclude this paper in
achieve the objective of high locating accuracy for wireless section V, together with intended future work.
sensor networks localization.
II. RELATED WORK
Keywords-wireless sensor networks; localization; time-of- Due to constraints on the cost and complexity, most
arrival (TOA); constrained optimization; multiplier method nodes’ locations are unknown in wireless sensor networks.
Generally, it is assumed that there are a number of nodes in
I. INTRODUCTION the sensor network have known their locations. They are
used to fix the coordinate system and estimated the other
With the rapid progress of the theory and technology of nodes’ locations. Many researchers have developed different
ubiquitous computing, the information space is merging to locating technologies. Here we focus on localization
people life. The wireless sensor network nodes play methods based on distance measurements, which is used by
important roles in sensing physical environment [1, 2, 3, 4]. this paper.
The sensor data come from where is very important. Distance measurements may be obtained by measuring
Therefore knowledge of the nodes’ positions becomes signal propagation time information. Distance related
imperative. If equipping GPS model for every node, the cost measurements include propagation time measurements, i.e.,
is too expensive. Instead, people develop some techniques to one-way propagation time measurements, roundtrip
estimate other nodes’ positions just depending on some propagation time measurements, time-of-arrival (TOA) and
anchor nodes (known position). time-difference-of-arrival (TDOA) measurements [7]. In the
Measurement techniques in wireless sensor network following paragraph we provide further detail of the TOA
localization can be broadly classified into categories: angle- technique.
of-arrival(AOA) measurements, distance related In the Cartesian system, the distance between anchor
measurements (e.g. time-of-arrival (TOA) [5]) and RSS node i and the unknown node A is given by
profiling techniques[6]. This paper proposes a constrained
optimized TOA (CoTOA) localization algorithm using ( x − xi )2 + ( y − yi )2 = c( ti − t0 ),i = 1, 2 ,3 (1)
multiplier method. We convert the locating process to a
finding minimal error sum process. By resolving the Where ( x, y ) is the position coordinate of the
constrained optimization problem, the minimal point will be unknown node A , and ( xi , yi ) is the coordinate of known
the optimal resolution. The proposed algorithm is
anchor node i . c is the speed of signal propagating
implemented in a centralized architecture. All nodes send
their measurements to a central station for localization. In medium, such as UWB, ultrasonic. ti is the signal time-of-
some applications such as monitoring patients and assisting arrival(TOA) at anchor i to be estimated, and t0 is the
disabled patients, monitoring bush fire and water quality in
the environment, there are already a centralized architecture, transmit time at the node A . By resolving the equation set
and demand high accuracy. The centralized localization (1), the position coordinates of the unknown node A are
algorithm will be the best fitting. Simulating results show the obtained.
A great deal of algorithms has been done on the topic of
position estimation in sensor networks [8, 9, 10]. These
techniques differ in their performance in terms of accuracy
∗
Corresponding author. Tel.: +8621 67792141; fax: +8621 67792141.
E-mail: li-cx2@[Link] (C. Li), Caoqiying@[Link] (Q. Cao).

978-0-7695-4030-6/10 $26.00 © 2010 IEEE 337

DOI 10.1109/CSO.2010.187
or implementation complexity. They also have different x1 − x 2 ≤R (2)
advantages in applications. 2

III. OPTIMIZATION ALGORITHM FOR LOCALIZATION

The distance-based localization problem can be
formulated as an optimization problem. Firstly, we introduce R
equality constrained optimization theory. Next, we propose a x1 x2
constrained optimized TOA (CoTOA) locating model. Then
we resolve the optimization localization problem by
multiplier method.
A. Constrained optimization theory Figure 1. Two nodes within communication range

Constrained optimization models are based on a set of In the situation of Fig. 1, if both the two neighbor nodes’
underlying assumptions. The main assumption is that most, positions are unknown, we use d̂ ij denotes the exact
if not all, of the various constraints in the model are static.
The general idea is to find the optimum solution given a set distance. If one node’s position is known, and the other node
of static constraints. The standard form of the equality is an anchor node, their distance is d̂ kj .There are constrains:
constrained optimization problem is as follows:
minimize f ( x ) ⎧ x − x 2 = ( dˆ ) 2
⎪ i j ij

subject to h j ( x ) = 0 , j = 1,… ,m ⎪ 2
⎨ x k − x j = ( dˆ kj ) (3)
2

Where x has dimensions n × 1 , f ( x ) is the objective ⎪

function to be minimized, and h( x ) are a set of equality ⎪∀ (i , j ) ∈ N 1 , ( k , j ) ∈ N 2
⎩
constraints. Equality constrained optimization problems are Because of existing distance measurement error, the
generally solved by the penalty function method, which locating problem can be view as an optimization problem.
includes the interior point penalty function method, the
We use α ij denotes the measure error between node x i and
exterior penalty function method and the multiplier penalty
function method etc[11]. For the interior point penalty and x j . The locating model would be to choose α s such that
exterior penalty function methods, the optimal resolution of
the target function could be got just when the penalty factor the sum of errors is minimized. Thus, our CoTOA locating
approaches infinity. In order to avoid this defect, we chose model can be expressed as:
the multiplier method to resolve our localization problem. min ∑ i , j∈N1 ,i < j
α ij + ∑ k , j∈N α kj
2
B. Constrained optimization locating model 2
It will be helpful to first introduce some notations. In this xi − x j = ( dˆ ij )2 + α i j ,∀( i, j ) ∈ N 1 ,
paper, the sensor localization problem is in fact a two-
dimensional case of general distance geometry problems. i < j,
2
The algorithms we propose are not restricted in R , but for 2

illustration all our work are chosen from the localization

ak − x j = ( dˆ kj )2 + α kj ,∀( k , j ) ∈ N 2 ,
2 s.t. (4)
problem in R . 2

We assume sensors can measure the distance between

xi − x j ≥ R 2 , for the rest i < j ,
two nodes. Suppose we have m known nodes (anchors) 2
2 ak − x j ≥ R 2 , for the rest k , j,
ak ∈ R , k = 1,2, , m , and n unknown nodes (sensors)
2 α ij ≥ 0,α kj ≥ 0
x j ∈ R , j = 1, 2, , n . We use N1 denotes the set of
Let X = [ x1 x 2 x n ] be the 2 × n matrix which
sensors which positions are unknown and N 2 denotes the set
needs to be determined. Then the problem can be written as
of sensors, there has one known node in it. e ij is the vector matrix form:
2
with 1 at the i th position, -1 at the j th position and zero xi − x j = eijT X T Xeij ,
everywhere else; and ej is the vector of all zero except -1 at 2
ai − x j = (ai ; e j ) T [ I X ]T [ I X ](ai ; e j )
the j th position.
Suppose two nodes x1 and x 2 are within radio range R Let Y = X T X . Then the problem can be rewritten as:
and have same measurement ability, the proximity constraint
can be represented as the form
min ∑ i, j∈N1,i< j
αij + ∑k, j∈N αkj
2

338
 eijTYeijT = ( dˆ ij )2 + αij ,∀(i, j ) ∈ N1 ,i < j, ( x1 − x4 )2 + ( y1 − y4 )2 + α14 = d142
⎛I X ⎞ s.t. ( x2 − x4 )2 + ( y2 − y4 )2 + α 24 = d 242 (6)
( ak ;e j )T ⎜ T ⎟ ( a k ;e j ) = ( dˆ kj )2 + αkj ,
⎝X Y ⎠ ( x3 − x4 )2 + ( y3 − y4 )2 + α 34 = d342
For convenience, the problem can be written as:
∀( k, j ) ∈ N2 ,
s.t. (5) min α 142 + α 24
2
+ α 342
eijTYeij ≥ R2 ,∀i < j ∉ N1 ,
( x1 − x 4 ) 2 + ( y1 − y 4 ) 2 + α 14 = d142
⎛I X ⎞ s.t. ( x 2 − x 4 ) 2 + ( y 2 − y 4 ) 2 + α 24 = d 242 (7)
( ak ;e j )T ⎜ T ⎟ ( a k ;e j ) ≥ R2 ,∀k, j ∉ N2 ,
⎝X Y ⎠ ( x3 − x 4 ) + ( y 3 − y 4 ) + α 34 = d
2 2 2
34
Y = X T X ,αij ≥ 0,αkj ≥ 0 Let X = (α 14 α 24 α 34 x 4 y 4 ) .
T
If N1 is sufficiently large and all distance measures are
The objective function:
perfect, there is an unique optimal solution.
f ( X ) = α 142 + α 24
2
+ α 342 (8)
C. Multiplier method locating procedure
Equation Constrained functions:
According to the characteristics of wireless sensor
networks and what our paper focusing on, we give bellow h1 ( X ) = ( x1 − x 4 ) 2 + ( y1 − y 4 ) 2 + α 14 − d 142
assumptions for the localization model:
(1) All nodes are deployed in two-dimensional field. If
h2 ( X ) = ( x 2 − x 4 ) 2 + ( y 2 − y 4 ) 2 + α 24 − d 242 (9)
in three-dimensional field, four anchors are need, and only h3 ( X ) = ( x3 − x 4 ) 2 + ( y 3 − y 4 ) 2 + α 34 − d 342
three anchors are necessary in two-dimensional field. Augmented objective function:
(2) The range of sensor node signal wave propagation
is a circle.
(3) All nodes have same communicating ability. μ
F( X ,v, μ ) = f ( X ) − vT h( X ) + h( X )T h( X )
(4) All messages can be received successfully. 2
(5) Sensor nodes can find their neighbors (10)
automatically. And neighbors can communicate freely each
other.
(6) Sensor nodes have measurement ability such as F( X ,v, μ ) = A2 + B 2 + C 2 − [ v1h1( X ) + v2 h2 ( X )
getting signal arriving time. Suppose the measure errors μ
follow the normal distribution. + v3 h3 ( X )] + [ h12 ( X ) + h22 ( X ) + h32 ( X )]
(7) Some sensor nodes know their positions. 2
Fig. 2 shows the location relationship about four nodes (11)
approximately. Where the measurement errors α14 ,α 24 ,α 34 are
represented by A,B,C . We use classical Multiplier method
1 to solve the resolution. Details of the multiplier method
computing procedure are described below:
2 (1) Given the initial point X
(0)
, the initial multiplier
4
vectors v(v1 , v2 , v3 ) , the penalty factor μ > 0 , the
amplifying coefficient γ > 1 , and the accuracy ε > 0 , the
3 parameter θ ∈ ( 0 ,1 ) , and let k = 1 ;
(2) Construct a target function:
Figure 2. Unknown node neighboring to 3 anchor nodes μ
F( X ,v,μ ) = f ( X ) − vT h( X ) + h( X )T h( X ) (12)
2
The anchor nodes’ coordinates are known as 1( x1 , y1 ) , ( k −1 )
(3) Set the X as the initial point, and resolve the
2( x2 , y2 ) and 3( x3 , y3 ) . They are neighboring to the min F( X ,λk , μ ) by an unconstrained non-linear
node 4, which position is unknown. Let the unknown node’s
programming technology. Suppose the x (k ) is the optimal
coordinate be ( x4 , y4 ) which is to be determined. The solution;
problem can be expressed as:
(4) If h( x (k ) ) < ε , stop the iteration and output
min α14 + α 24 + α 34

339
x (k ) , otherwise turn to (5); simulation. Fig. 4 shows a graphical result generated by our
2
(k )
(5) If h( x ) / h( x
( k −1 )
) ≥ θ , let μ = γμ , else CoTOA method with nf = 0.1 . We can see that the
estimated node positions are closely to its exact positions.
turn to (6); The mean absolute location error meet the accuracy
(6) Let vi = vi − μ hi ( x( k ) ),i = 1, 2 , ,m , and set requirement of most applications.
To evaluate the improved performance of the CoTOA,
k = k + 1 , turn to (2). We compared our CoTOA method with the traditional TOA
In the process of solving the locating model for each method. We used the mean error between the estimated and
unknown node, we suppose all nodes can communicate each the true physical location of non-anchor nodes in the
other. In other words, every unknown node has at least three
network, where nf 2 = 0 .01, 0 .02 , , 0 .1 . The performance
anchor neighbors. We use MATLAB software to compute all
unknown positions and plot the true position and estimated is demonstrated in Fig. 5. The CoTOA has improved the
position for every node. accuracy of traditional TOA method. The advantage
becomes more obvious with the increasing of noise factor
IV. SIMULATION RESULTS value.
Simulations were performed on networks of 10 anchor
nodes and 100 non-anchor nodes randomly placed in a
square region of size 100m*100m at the origin. The
distances between the nodes were calculated. All test
problems are solved by Matlab7.1. The purpose of this
section is to evaluate the performance of our CoTOA method
and compare it to the traditional TOA method. For the
localization problem with measurement noises, we assume
the distances noises are randomly generated according to the
following formula,
d ij = dˆ ij ( 1 + ρ ) (13)
Here, d̂ij represents the exact distance between nodes i
and j , ρ ∈ N( 0 ,nf 2 ) is a random variable which follows
Gaussian distribution, and nf (noisy factor) is used to adjust
the variance of the distance uncertainty. Fig. 3 shows the
mean absolute position error per five points with different
nf values. The localization error become smaller with the
smaller noise factor. If the noise factor is enough small, the
location error of CoTOA algorithm tends to zero. This also
Figure 4. Results of CoTOA with nf2=0.1
proves the correctness of our CoTOA locating algorithm.

Figure 3. Absolute location error with different nf2

In order to test our algorithm’s high localization
Figure 5. Mean absolute location error versus nf2
accuracy, we chose the largest nf value among the above

340
 V. CONCLUSIONS
Many applications of wireless sensor networks depend on
accurate positions determination of all network nodes. In this
paper we have developed a new TOA localization technique
(CoTOA) using multiplier method. The technique optimizes
the TOA solution by iterative process. The approximate
optimality of the proposed positioning algorithm is
demonstrated via computer simulations. It is shown that
CoTOA method is better than traditional TOA algorithm in
terms of accuracy. However the computation complexity is
higher. And the CoTOA accuracy is low when the anchor
nodes symmetrically distribute to the unknown node. These
are part of our future work. The scalability is also our future
work.
ACKNOWLEDGMENT
The authors would like to thank anonymous referees for
their useful comments. This work is supported by the Special
Research Funds of Chinese Ministry of Education(No.
104086) and the Key grant Project of Chinese Ministry of
Education(No. CNGI2008-092).
REFERENCES
[1] E. Biagioni, and K. Bridges, “The application of remote sensor
technology to assist the recovery of rare and endangered species,” In
Special issue on Distributed Sensor Networks for the International
Journal of High Performance Computing Applications, vol. 16, no. 3,
Aug. 2002.
[2] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A
survey on sensor networks,” IEEE Communications Magazine, vol.40,
no. 8, pp.102-114, Aug. 2002.
[3] E. Howden, “Networked sensors for the objective force,” In
Proceedings of SPIE 47th Annual Meeting, 2002.
[4] ALERT Systems,[Link]
[5] K. Yu, J.-P. Montillet, A. Rabbachin, P. Cheong, and I. Oppermann,
“UWB location and tracking for wireless embedded networks,”
Signal Processing, vol. 86, no. 9, p. 482, Sept. 2006.
[6] G. Mao, B. Fidan and B.D.O. Anderson, “Wireless sensor network
localization techniques,” Computer Networks, vol. 51, no. 10, Jul.
2007, pp. 2529-2553.
[7] M. Vossiek, L. Wiebking, P. Gulden, J. Wieghardt, C. Hoffmann, and
P. Heide, “Wireless local positioning,” IEEE Microwave Magazine,
vol. 4, no. 4, pp. 77-86, Dec. 2003.
[8] K. Lui, F. Chan, H. So, “Accurate time delay estimation based
passive localization,” Signal Processing, vol. 89, 2009, pp. 1835-
1838.
[9] K. Romer, “The lighthouse location system for smart dust,” In
Proceedings of MobiSys 2003 (ACM/USENIX Conference on
Mobile Systems, Applications, and Services), 2003, pp. 15-30.
[10] S. Venkatraman, J. Caffery, Y. Heung-Ryeol, “A novel TOA location
algorithm using LoS range estimation for NLOS environments,”
IEEE Transactions on Vehicular Technology, vol. 53, no. 5, Sep.
2004, pp. 1515-1524.
[11] M. R. Hestenes, “Multiplier and gradient methods,” Computing
Methods in Optimization Problems, Academic Press, New York,
1969, pp. 143-163.

341