Abstract: Node localization is a fundamental problem in many wireless sensor networks applications. In this study, based on simulated annealing approach, an adaptive RSSI compensation strategy in cooperative localization (called SA-ARC-CL algorithm) is proposed. Firstly, we built cooperative localization model and then extract the localization problem based on 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 using only a few APs and has a good RSSI adaptive ability in indoor localization applications.
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: Range-based and range-free (Wu et al., 2011). In practical applications, since Range-based algorithms can usually provide higher accuracy then range-free algorithms, it is often used in many positioning systems such as RADAR (Bahl and Padmanabhan, 2000), Cricket (Priyantha et al., 2000) and so on.
Range-based 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, RSSI-based 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 least-squares 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 RSS-based 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 correlation-based 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 ill-conditioned 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 multi-robot 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 SA-ARC-CL 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: RSSI-based localization algorithms are usually used in indoor target localization. The most important step of RSSI-based localization algorithms is RSSI ranging. The measured RSSI readings and distances are usually used to fit the signal propagation model and the signal-to-distance relationship is derived by Rahman et al. (2012):
| (1) |
where, R represents the transmitting power of a wireless device at the reference distance d0. 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):
| (2) |
where, et is the RSSI compensation between the tth AP and any unknown node (UN). et 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):
|
|
(3) |
where, dt is the distance between the target and the tth AP (At), 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 At 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) (Escalona-Vargas et al., 2011) algorithm is one kind of common heuristic algorithms such as genetic algorithm (Guerra-Gomez et al., 2012; Tlelo-Cuautle et al., 2010a), swarm algorithm (Polanco-Martagon et al., 2012), evolutionary algorithm (Polanco-Martagon et al., 2012; Tlelo-Cuautle et al., 2010b) Particle Swarm Optimization (PSO) algorithm (De la Fraga et al., 2012; Tlelo-Cuautle 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 (Escalona-Vargas et al., 2011):
| • | Selection of initial temperature T0: T0 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 |
| (4) |
where, Tl 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) |
| (5) |
where, k is the Boltzmann constant, T is the current temperature, ΔE is the energy change of annealing process.
SA-ARC-CL ALGORITHM
Localization scenario and assumptions: In this study, we considered a cooperative localization model for indoor target-group localization in 2-D 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 2-D 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:
| (6) |
where, ei 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 information-the 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 sub-graph GUN = (VUN, EUN) to represent the topology structure of all UNs.
After positioning is completed, an adjacency matrix (G(1)UN) of graph GUN can be obtained:
| (7) |
where, dij is the Euclidean distance between UNi and UNj, that is:
| (8) |
where,
Similarly, we can get another adjacency matrix G(2)UN of GUN using formula (1).
| (9) |
where, dij 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:
| (10) |
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 SA-ARC-CL 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 open-loop control, which is very suitable to solve the above problem. However, there are also some drawbacks:
| • | Initial temperature T0 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 T0 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 ei: |
| (11) |
| 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. ei 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.
| (12) |
| Rule 3: | Perturbation rule: during every status update, we use the following rule to update solution searching: |
| (13) |
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: |
| (14) |
where, ⌊•⌋ denote taking integer, F(t) and F(t-1) are calculated with function (10) in the (t)th and (t-1)th localization, ΔF can simulate the energy change of annealing process, like ΔE. r0 is a constant which is used to simulate the initial temperature T0. φ is the number of solutions which are already calculated; Φ denote the total solution number in solution space.
The SA-ARC-CL 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:
| (15) |
where, Dij is the distance between APi and UNj, rand_num is a random number uniformly distributed on interval [0.8, 1.2]. wall-randij is a random RSSI compensation between APi and UNj, which uniformly distributed on interval [20, 30] (dBm). In the simulation, we assume that wall_randij 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:
| (16) |
where, Xi is the actual coordinate of the UNi, σi is the calculated coordinate of the UNi using the proposed localization algorithm. ||Xi, σi|| represents the localization error of UNi.
| Table 1: | Simulation parameters |
| Fig. 4(a-b): | Simulation results comparison of (a) Proposed algorithm and (b) WCL algorithm with respect to one group needed to be located |
| Fig. 5(a-b): | Localization error comparison of (a) Proposed algorithm and (b) WCL algorithm with respect to one group needed to be located |
| Fig. 6(a-b): | Simulation results comparison of (a) Proposed algorithm and (b) WCL algorithm with respect to three groups needed to be located |
| Fig. 7(a-b): | 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_randij) 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 result-the 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 (2009ZX07528-003-09), Chongqing Key Project of Science and Technology of China (cstc2012gg-yyjs40008) and the 2011 Internet of Things Development Special Fund.