INTRODUCTION
Target localization has been a key application in elders/children guarding,
hospital patients care, indoor searching and rescuing for trapped and so on
Wang et al. (2011). It is also a crucial issue
for different applications in wireless sensor networks (Wu
et al., 2011), which attracts many researchers interests. Indoor
localization of WSNs has been a hot research topic for the last several years.
Up to now, two kind of indoor localization algorithms have been proposed: Rangebased
and rangefree (Wu et al., 2011). In practical
applications, since Rangebased algorithms can usually provide higher accuracy
then rangefree algorithms, it is often used in many positioning systems such
as RADAR (Bahl and Padmanabhan, 2000), Cricket (Priyantha
et al., 2000) and so on.
Rangebased localization algorithms usually use some ranging methods to estimate
the actual distances or orientation. These ranging methods include ToA (Time
of Arrival), TDOA (Time Difference on Arrival), AoA, RSSI (Received Signal Strength
Indicator) and so on Wu et al. (2011) and Chen
et al. (2011). In indoor environment, RSSIbased algorithms have
certain advantages because RSSI ranging technique has the least requirement
for hardware and most radio chips of current sensor nodes have function of reading
RSSI value. After doing RSSI ranging, these algorithms usually use leastsquares
trilateration or some other methods to determine the final positions of target
nodes. However, due to the unpredictable signal propagation such as reflection,
refraction, shadowing and scattering of signal, RSSI ranging is extremely inaccurate
which results in the bad performance of RSSbased algorithms. Rahman
et al. (2012) proposed a flexible location estimation algorithm for
WSNs localization. In their study, Generalized Regression Neural Network (GRNN)
and Weighted Centroid Localization (WCL) were used. However, the algorithm needed
a large number of training, which is not suitable for actual applications. Yang
and Chen (2009) first used linear regression to get a better fit of signal
propagation model between RSSI and distance, and then used correlationbased
method to obtain the more accurate signal propagation. The accuracy can be improved
to some extent by this way, but it can’t adjust RSSI to environment change
adaptively.
Cooperative localization, which is also called cooperative group localization,
was firstly put forward by Zhang et al. (2009).
It usually used to solve the illconditioned localization problem in mobile
communication networks. It can be also used for group localization in wireless
sensor networks. In Cui et al. (2011), in order
to solve the accuracy and cost problem, the authors proposed a new cooperative
localization algorithm for long range flight formations. In their study, they
supposed that the master vehicle equipped with high precision Inertial Navigation
System (INS) and the slave vehicles are equipped without INS or with low precision
and inexpensive INS. However, this method is not suitable for indoor cooperative
localization. Wang et al. (2008) proposed an
improved algorithm for multirobot cooperative localization based on relative
bearing. After analyzing the relative positions and motion trajectories of the
robots, the algorithm can get the localization results. Some results may be
not good because of some different trajectories. An improved approach was proposed
to solve this problem in this study. However, this algorithm is not suitable
for indoor cooperative localization either.
All of these cooperative localization algorithms require some additional equipment,
which is not suitable for amount actual applications. In this study, based on
simulated annealing approach, an adaptive RSSI compensation strategy in cooperative
localization (called SAARCCL algorithm) is proposed. Firstly, we built cooperative
localization model and then extract the localization problem according this
model. The core problem is to find the right RSSI compensation of each Access
Point (AP). After that, an improved simulated annealing approach is proposed
to solve this problem, in which some new rules are proposed to make this solution
more effective. Finally, based on RSSI compensation, WCL algorithm is used to
obtain the final position of each UN. Simulation results show that the proposed
algorithm performs better than WCL algorithm with only a few APs. It also can
adjust the complicated indoor environment applications adaptively using adaptive
RSSI compensation.
RELATED WORKS
RSSI ranging: RSSIbased localization algorithms are usually used in
indoor target localization. The most important step of RSSIbased localization
algorithms is RSSI ranging. The measured RSSI readings and distances are usually
used to fit the signal propagation model and the signaltodistance relationship
is derived by Rahman et al. (2012):
where, R represents the transmitting power of a wireless device at the reference
distance d_{0}. RSSI(d) is the transmitting power of a wireless device
at the distance d. d is the distance between the target node and the access
point (AP). n is the path loss exponent and ξ_{σ} is the shadow
fading which follows zero mean Gaussian distribution with σ standard deviation.
Sometimes, it is different for ξ_{σ} to describe the effect
of indoor obstacles on signal propagation. Another signal propagation model
is more suitable for indoor localization when come to consider indoor obstacles
(Yang and Chen, 2009):
where, e_{t} is the RSSI compensation between the tth AP and any unknown
node (UN). e_{t} is usually determined by indoor environmental factors,
among which some obstacles like walls and doors are the most powerful factor.
Weighted centroid localization algorithm: Weighted Centroid Localization
(WCL) algorithm was improved from Centroid Localization (CL) algorithm, which
estimates the position of the target node as (Blumenthal
et al., 2007):
where, d_{t} is the distance between the target and the tth AP (A_{t}),
estimated through RSSI. The exponent η>0 determines the weight of the
contribution of each AP to the location estimation. If η = 0 then is simply
the sample mean of the A_{t} and the WCL reduces to the CL approach.
η reflects the “attraction”
capability between the APs and target nodes. The bigger the η, the smaller
the “attraction”
capability and the greater the weight of the contribution to the nearest APs.
In an ideal environment, or in an environment with rare signal interference,
WCL has a good ability to keep UNs’
relative positions unchanged. Figure 1 shows that the relative
positions of UNs are almost unchanged after localization. This is a very important
feature which will be used in the proposed algorithm.
Simulated annealing algorithm: Simulated Annealing (SA) (EscalonaVargas
et al., 2011) algorithm is one kind of common heuristic algorithms
such as genetic algorithm (GuerraGomez et al., 2012;
TleloCuautle et al., 2010a), swarm algorithm
(PolancoMartagon et al., 2012), evolutionary
algorithm (PolancoMartagon et al., 2012; TleloCuautle
et al., 2010b) Particle Swarm Optimization (PSO) algorithm (De
la Fraga et al., 2012; TleloCuautle et al.,
2010c) and so on.

Fig. 1: 
One example of WCL localization results 
SA algorithm is based on the physical processing of annealing in metallurgy.
It is very useful for solving complex combinatorial optimization problems. The
main features of this algorithm are as follows (EscalonaVargas
et al., 2011):
• 
Selection of initial temperature T_{0}: T_{0}
affects the trade off of the computational cost and the possibility of finding
a global optimum 
• 
Temperature decrement rule: In order to avoid an impractically long time
of computation, the temperature decrement should not be too slow. The following
rule is usually used 
where, T_{l} is the lth temperature and α<1 controls
the decrease in temperature.
• 
New status acceptance rule: This rule shows the algorithm
accept new status with possibility P. In SA algorithm, P is usually derived
by Geng et al. (2007) 
where, k is the Boltzmann constant, T is the current temperature, ΔE is
the energy change of annealing process.
SAARCCL ALGORITHM
Localization scenario and assumptions: In this study, we considered
a cooperative localization model for indoor targetgroup localization in 2D
indoor environment, as shown in Fig. 2. A few APs are deployed
in indoor environment. A group of targets (UNs) are randomly deployed in a 2D
indoor environment and surrounded by all APs. Some other assumptions are as
follows:
• 
All devices have the ability to do RSSI ranging if they can
communicate with each other 
• 
Each UN can communicate with every AP 
• 
All APs’ positions are already known 
• 
We only considered the RSSI compensation between APs and UNs. That’s
to say, we use formula (1) to do RSSI ranging between APs and UNs and when
come to do RSSI ranging among different UNs, formula (2) will be used 

Fig. 2: 
Cooperative localization model 

Fig. 3: 
Localization problem description 
Problem formulation: According to the previous analysis, the localization
problem can be formulated as shown in Fig. 3.
R and n can be measured by some indoor experiment or determined according to
experience. The values of R and n obtained by this manner are only approximation
environment parameters. It needed to be compensated when doing RSSI ranging.
e is exactly that kind of RSSI compensation. So the localization problem turned
to be: input e, get the output. e can be expressed as:
where, e_{i} is the RSSI compensation when UN communicated with the
ith AP.
In indoor environment, signal propagation is effected by some unpredictable
factors such as reflection, refraction, shadowing and scattering. These may
caused by people, desks, doors, walls and some other indoor stuffs, among which
doors and walls are most influential. Furthermore, the network is usually heterogeneous
due to transmission power difference, device hardware difference and so on.
All of these could make RSSI compensation very difficult to be determined and
hard to improve localization accuracy.
However, some useful information in cooperative localization model will be
very helpful to improve localization accuracy if it is be used. According to
some traditional approaches such as MLE (Chan et al.,
2006), WCL and so on, we can obtain the position of each UN in cooperative
localization model. This result is obtained only used a part of the useful informationthe
information between APs and UNs. The information among UNs is always failed
to be considered.
Let us use weight graph G = (V, E) to represent the topology structure of cooperative
localization. The vertices (V) in graph G represent UN or AP. The numbers of
UN and AP are α and β, respectively. There is an edge (E) between
two vertices if the Euclidean distance can be determined and the edge is weighted
by the corresponding Euclidean distance. We use a subgraph G_{UN} =
(V_{UN}, E_{UN}) to represent the topology structure of all
UNs.
After positioning is completed, an adjacency matrix (G^{(1)}_{UN})
of graph G_{UN} can be obtained:
where, d_{ij} is the Euclidean distance between UN_{i} and
UN_{j}, that is:
where,
is the localization result of UN_{i}. As WCL algorithm has the ability
to keep relative positions of UNs almost unchanged, So, in this study, we use
WCL algorithm go obtain ,
as formula (3) shows.
Similarly, we can get another adjacency matrix G^{(2)}_{UN}
of G_{UN} using formula (1).
where, d_{ij} is another Euclidean distance derived by formula (1).
G^{(2)}_{UN} contains some information of UNs, which can be
considered as a constraint matrix of G^{(1)}_{UN}. G^{(1)}_{UN}
and G^{(2)}_{UN }can be regarded as functions of e. According
to communication theory and mathematical derivation, we known that the more
pure the environment is, the more accurate the measurement are and final the
higher the similarity of G^{(1)}_{UN} and G^{(2)}_{UN}
will be. So, we can get the following objective function:
And finally, the localization problem of cooperative localization can be transferred
to: How to choose the right e to make F minimum and then to get the final position
of each UN with e and WCL algorithm.
This is a typical Combinatorial Optimization Problem (COP) (Aydin
and Fogarty, 2004). Some researchers proposed some kind of problem solving
methods. In this study, we use Simulated Annealing (SA) algorithm to solve this
and proposed SAARCCL localization algorithm at last.
RSSI compensation strategy based on simulated annealing: SA algorithm
is a random search algorithm that simulates physical processing of annealing
in metallurgy. It searches through the total solution space and can find the
optimal solution globally over a domain. SA algorithm uses a mode of openloop
control, which is very suitable to solve the above problem. However, there are
also some drawbacks:
• 
Initial temperature T_{0} is hard to be determined:
The initial temperature setting is one of the important factors that affect
the performance of simulated annealing algorithm for searching globally
optimal solution. If T_{0} is set too high, the computing time will
be very long but the possibility of finding the globally optimal solution
will be large. Conversely, you can save time, but the possibility will be
reduced 
• 
Temperature decrement rule is hard to be determined: This rule related
to the speed of annealing, which is another important factor about computational
time and searching capability 
In this study, temperature control method for SA will be abandon. Some new
rules for SA algorithm will be proposed to avoid the above disadvantage.
Rule 1: 
Limit the scope of the solution space. Based on actual experience,
we can roughly determine the range of each e_{i}: 
Rule 2: 
Search strategy of solution space. The core point of this
rule is: avoid repeating search. During the solution searching, if two solutions
are equal to each other, we thought that these two solutions are repeating.
Then the algorithm will skip this step and continue to search the next solution.
However, the possibility of two solutions that equaled to each other was
small when use random solution searching. Therefore, we proposed the following
strategy to judge whether two solutions equals to each other approximately 
Let us use e and e' to represent two different vectors in solution space. e_{i}
and e'_{i} are the component of e and e', respectively. If all component
of these two vectors are satisfied the following condition, then e and e' can
be considered as the approximate solutions in the solution space.
Rule 3: 
Perturbation rule: during every status update, we use the
following rule to update solution searching: 
where, Δe is perturbation value. Each component of Δe obeys uniform
distribution on the solution space.
Rule 4: 
Status update rule: every new status will be accepted with
possibility P if ΔF>0: 
where, ⌊•⌋ denote taking integer, F^{(t) }and F^{(t1)}
are calculated with function (10) in the (t)th and (t1)th localization, ΔF
can simulate the energy change of annealing process, like ΔE. r_{0}
is a constant which is used to simulate the initial temperature T_{0}.
φ is the number of solutions which are already calculated; Φ denote
the total solution number in solution space.
The SAARCCL algorithm is comprised of the following steps:
SIMULATION ANALYSIS
Extensive simulation runs have been used to evaluate the performance of the
proposed algorithm carried out using MATLAB. Node deployment has been showed
in Fig. 4 and 6. Four APs were placed in
the four corners. Suppose that there are some walls between AP1, AP2 and UNs.
We use the following function to simulate RSSI observations:
where, D_{ij} is the distance between APi and UNj, rand_num is a random
number uniformly distributed on interval [0.8, 1.2]. wallrand_{ij}
is a random RSSI compensation between APi and UNj, which uniformly distributed
on interval [20, 30] (dBm). In the simulation, we assume that wall_rand_{ij}
exist only between AP1, AP2 and UNs. Some other parameters are shown in Table
1.
In this study, one evaluation metrics, the average localization error (ave_loc_err),
is described as:
where, X_{i} is the actual coordinate of the UN_{i}, σ_{i}
is the calculated coordinate of the UN_{i} using the proposed localization
algorithm. X_{i}, σ_{i} represents the localization
error of UN_{i}.
Table 1: 
Simulation parameters 


Fig. 4(ab): 
Simulation results comparison of (a) Proposed algorithm and
(b) WCL algorithm with respect to one group needed to be located 

Fig. 5(ab): 
Localization error comparison of (a) Proposed algorithm and
(b) WCL algorithm with respect to one group needed to be located 

Fig. 6(ab): 
Simulation results comparison of (a) Proposed algorithm and
(b) WCL algorithm with respect to three groups needed to be located 

Fig. 7(ab): 
Localization error comparison of (a) Proposed algorithm and
(b) WCL algorithm with respect to three groups needed to be located 
NUM is the number of UNs. The smaller the ave_loc_err, the better performance
the algorithm. The simulation results are as follows.
Figure 4 and 5 are the simulation results
of the proposed algorithm and WCL algorithm with respect to one group needed
to be located. In this simulation, 100 UNs are random deployed in a ‘group
box’. Simulation results show that the proposed algorithm whose average
localization error is 2.6940 m has a better accuracy than WCL algorithm whose
average localization error is 4.3752 m. Furthermore, we did some other simulations
with three groups as Fig. 6 and 7 show.
In each ‘group box’, there are 40 UNs are randomly deployed. Simulation
results show that proposed algorithm performs better than WCL algorithm.
We also did some other simulations to evaluate the adaptive ability of the
proposed algorithm. We ‘changed’
the indoor environment by changing RSSI compensation (wall_rand_{ij})
between UNs and different APs. We can get the same result that the proposed
algorithm performs better than WCL algorithm. Furthermore, there are some performance
values showed in these figures, the proposed algorithm can be compared to any
other algorithms directly. In this study, we did not describe these comparisons.
Above all, the proposed algorithm can provide high localization accuracy with
only a few APs been used. Moreover, the proposed algorithm can adjust the complicated
indoor environment applications adaptively using adaptive RSSI compensation,
which is more suitable for indoor target localization applications than other
approaches.
CONCLUSION
In this study, an adaptive RSSI compensation strategy based on simulated annealing
for indoor cooperative localization are proposed and analyzed. At beginning,
a cooperative localization model was built and the localization problem based
on this model was represented. Then, an improved simulated annealing algorithm
with some new rules was used to solve this localization problem. At last, based
on the solve resultthe result of RSSI compensation, WCL algorithm is used to
obtain the final position. Simulation results showed the effective of the proposed
algorithm.
ACKNOWLEDGMENTS
This study was supported by the National Key Technology R&D Program (2011BAK07B03),
National Science and Technology Major Project (2009ZX0752800309), Chongqing
Key Project of Science and Technology of China (cstc2012ggyyjs40008) and the
2011 Internet of Things Development Special Fund.