TMCnet News

Weighted Centroid Localization Algorithm Based on Least Square for Wireless Sensor Networks [Sensors & Transducers (Canada)]
[September 23, 2014]

Weighted Centroid Localization Algorithm Based on Least Square for Wireless Sensor Networks [Sensors & Transducers (Canada)]


(Sensors & Transducers (Canada) Via Acquire Media NewsEdge) Abstract: Localization algorithm is an important and challenging topic in today's wireless sensor networks (WSNs). In order to improve the localization accuracy, a weighted centroid localization algorithm based on least square to predict the location of any sensor in WSNs is proposed in this paper. The proposed algorithm proposes a Least-Square-based weight model which can reasonably weigh the proportion of each anchor node in the unknown node. In the weight model, we utilize least square method to compute the weight. Then, we increase the weight of anchor nodes closer to the unknown node, introduce the parameter k into the proposed likelihood model, and we determine the optimal value of the parameter k through our real experiments. Simulation and experimental results show that the proposed weighted centroid algorithm is better than Weighted Centroid Localization (WCL) and Anchor-optimized Modified Weighted Centroid Localization based on RSSI (AMWCL-RSSI) in terms of the localization accuracy. Copyright © 2014 IFSA Publishing, S. L.



Keywords: Localization, RSS, Wireless sensor networks, Least square, Weight.

(ProQuest: ... denotes formulae omitted.) 1. Introduction Recent advancements in the wireless communications and hardware technology field have facilitated the development of wireless sensor networks (WSNs) for a wide variety of real-world applications, including environmental monitoring, disaster relief, site security, medical diagnostics, battlefield surveillance, home automation, assisted living, and so on [1-6].


A recent outdoor application for WSNs is the localization of moving targets. This application is motivated primarily by the low cost of this solution and the lack of effective positioning and tracking systems working inside buildings. Indeed, the global positioning system solves many localization problems outdoor, where the devices can receive the signals coming from satellites. Moreover, wireless nodes show some advantages in terms of system miniaturization, scalability, quick and easy network development, cost, and lower energy consumption.

Most of the proposed localization algorithms rely on received-signal-strength (RSS) measurements. In fact, RSS can be used to estimate the distance between an unknown node (called a target node) and a number of anchor nodes with known coordinates. The location of the target node is then determined by multilateration [7-9].

Unfortunately, due to the degrading effects of reflections, shadowing, and fading of radio waves, some studies have shown the large variability of RSS [10-12]. As a result, localization methods using RSS are affected by large errors and lack of accuracy. However, RSS-based techniques remain an appealing approach [13]. This is mainly due to the fact that RSS measurements can be obtained with minimal effort and do not require extra circuitry, with remarkable savings in cost and energy consumption of a sensor node. In fact, most of WSN transceiver chips have a built-in RSS indicator (RSSI), which provides RSS measurement without any extra cost.

There exist several algorithms that can be used to determine the position of a target through RSS measurements. Some of them are geometric methods, such as lateration or a minimum-maximum method, whereas some others are based on statistical approaches, such as maximum likelihood.

Alippi et al. have tested an RSS-based outdoor localization methodology exploiting a minimum least square (LS) algorithm, after modeling a propagation channel [14]. The deployment of anchors has a density of one node over 25 m2 on an area of 500 m2. The average distance error obtained is about 3 m.

In [15], an extensive indoor RSS measurement campaign is carried out in order to tune the parameters of the assumed channel model. Then, the collected RSS data have been used offline as inputs for two localization methods, i.e., the min-max and Bayesian filtering algorithms. A distance error of the order of 5 and 2 m is achieved for the two algorithms, respectively.

Centroid localization (CL) and weighted centroid localization [16-22], have attracted a lot of interest because of their simplicity and robustness to changes in wireless propagation properties such as path loss. This characteristic makes them suitable candidates for systems requiring coarse grained, but reliable and cost-effective techniques. Strictly speaking, weighted centroid localization is not an entirely range-free technique because it requires additional information aside from simple connectivity.

Recently many proposed approaches on weighted centroid localization focused more on error control and management. Weighted centroid localization (WCL) is firstly proposed in [23]. In order to avoid the creation of RSS maps, complicate probability models, or high-computational-effort algorithms, Reichenbach and Timmermann proposes approximated indoor localization based on a weighted centroid approach combined with RSS measurements in an IEEE 802.15.4 sensor network [24]. The weights are defined as inversely proportional to the RSS values measured between the target and each anchor node. The solution is tested in a square room with a side length of 3 m, using four anchor nodes displaced at the comers and one target node located in 13 different positions. The obtained relative localization error varies between 7.8 % and 26 %. In [25], Hongyu et al. proposes an anchoroptimized modified weighted centroid localization algorithm based on RSSI (AMWCLRSSI). Other schemes are to discuss inexact position problems [26], or analyze the performance of weighted centroid localization algorithm [27], or enhance its performance for specific scenarios [28-29].

The aim of this paper is to improve the localization accuracy of weighted centroid localization, and we propose a weighted centroid localization algorithm based on least square for WSNs. We compare our proposed scheme with some existing solutions via simulations and experiments.

The rest of this paper is organized as follows. Section 2 presents proposed localization algorithm, followed by Performance evaluation in Section 3. We conclude the paper in Section 4.

2. Proposed Localization Algorithm 2.1. Overview of Localization System The aim of the RSS-based localization is to seek a mapping between the measurements to a physical location. One of the most important mapping functions is the probabilistic model finding the weight p(i) [30, 31]. Then, the location can be regarded as a regression problem [30] as (x,y) = YJ(li-p(0) > where n is the number of anchor nodes, h represents the coordinate of the ith anchor node and (x,y) represents the estimated result. This paper adopts a novel approach to compute the weight.

2.2. RSS Model RSS model can be expressed as RSS = PLO-lOßloglo(d/d0) + Na, (1) where d is the real distance, PL0 is the received signal strength at reference distance d0 (d0=\ m), ß is the path loss exponent, and Na is a zero-mean Gaussian noise with standard deviation ce.

2.3. Weighted Centroid Localization Algorithm Based on Least Square (WCLLS) In this section, we will introduce the proposed weighted centroid Localization Algorithm for location estimation. Let di denote the Euclidean distance between the coordinator of anchor i and the coordinate (x,y) for a specific unknown node. We assume that each unknown node can hear at least n anchor nodes. The variables D = (dx,d2,d3,___,dn) represent the set of measured distances to anchor nodes 1,2,3,___,« from the unknown node. The coordinate (x,y) is an estimated position of an unknown node. The coordinate (x,y) is the position of each anchor node. According to [30] and [31], the estimated position (x,y) can be expressed by ...(2) where Ii represents the ith anchor node location, and Ii=(xi,yi).

...(3) With the geometric relationships, the measured distances di can be expressed by ...(4) ...(5) With (2) and (5), we can get ...(6) According to (3) and (6), we can get ...(7) ...

By using least square method, p(i) can be expressed as: ...(8) p(i) is as the weight of anchor node i ( i = l,2,-,n ), but p(i) can't fully reflect the binding on the estimated position of the unknown node due to the interference of external environment. To this problem, we propose a novel weight model. In the novel weight model, we increase the weight of anchor node closer to the unknown node. Because the closer anchor node gets to the unknown node, the greater weight anchor node has [23]. Meantime, we introduce the parameter k into the weight model. The reasonable parameter k can further weigh the proportion of each anchor node in the unknown node.

p(i) is the improved weight model, and Pd) * > p(0 ( n is the number of anchor nodes, k is a parameter, and 0<k<n ). Here, we consider the impact of the number of anchor nodes to localization accuracy in p{0 (^)p(,).

After p(i) * (.-~)P>'1> normalization, the weight can be expressed as: ... (9) ...(10) 2.4. The Optimal Value of the Parameter k In this section, we obtain the optimal value of the parameter k through the real experiment. A wireless node is based on a MSP430 microprocessor and equipped with an IEEE 802.15.4 compliant Chipcon CC2500 radio module. The antenna is a 2.4 GHz planar inverted-F antenna. In our experiments, anchor nodes are randomly distributed ina50mx50 m region. The position of an unknown node is randomly deployed in this region. Here, we choose the number of anchor nodes n = 4,5,6 respectively for our experiment, and all nodes are able to communicate with each other.

Fig. 1, Fig. 2 and Fig. 3 show the average localization error when k chooses a different value.

From Fig. 1, when the number of anchor nodes n = 4 and the parameter k = 4 , WCLLS has a significant change in the localization accuracy. Clearly, it can be seen that when the number of anchor nodes n = 4 , k should be closer to 4, but not equal to 4.

From Fig. 2, when the number of anchor nodes n = 5 and the parameter k = 5 , WCLLS has a significant change in the localization accuracy. Clearly, it can be seen that when the number of anchor nodes n = 5 , k should be closer to 5, but not equal to 5.

From Fig. 3, when the number of anchor nodes n = 6 and the parameter k = 6 , WCLLS has a significant change in the localization accuracy. Clearly, it can be seen that when the number of anchor nodes n = 6 , k should be closer to 6, but not equal to 6.

From the analysis above, it can be seen that k should be closer to n , but not equal to n, and k <n . Hence, we assume k = n-b as the value of the parameter k , where k <n , 0 <b<n . Next, we determine the value of the parameter b through MATLAB simulation.

We assume that an unknown node and 8 anchor nodes are randomly deployed in a 50m x 50m region, and the unknown node is randomly placed in 10000 different positions. We set PL0 = -60dB and choose ß = 2,2.5,3,3.5,4,4.5 , the zero-mean Gaussian noise Na has a standard deviation of 3dB . The simulation results are as shown in Table 1. From Table 1, we can choose n-O.1 as the optimal value of the parameter k.

Therefore, the weight model w(i) in Eq. (9) can be expressed as follows: ... (11) 2.5. Process of Localization Algorithm The algorithm process of the proposed localization algorithm is as follows: Step 1: Beacon nodes periodically transmit information of themselves which include node ID and position information of themselves; Step 2: After unknown node receives signals, it records RSS values which come from beacon nodes; Step 3: Compute the measured distance di ; Step 4: Compute the weight p(i) and the improved weight ...

Step 5: Compute the weight ... through n - 0.1 n- 0.1 7=1 Eq. (11); Step 6: Compute the estimated position ...

3. Performance Evaluation In this section, we analyze the performance of the studied localization schemes through simulations and experiments. We compare the proposed weighted centroid localization algorithm with WCL [23] and AMWCL-RSSI [25]. We set the degree g = l in all experiments.

3.1. Localization Error Versus the Number of Anchor Nodes In this experiment we evaluate the effect that the number of anchors has on the location accuracy. Fig. 3 depicts the effect on localization error when varying the number of anchors. All nodes are deployed in an 100m x 100m area. Anchor nodes are randomly deployed at the edge of the selected area, 1000 sensor nodes are randomly placed in the region. We assume that PL0 = -60dB and the zero-mean Gaussian noise Na has a standard deviation of 3dB . We set ß = 2 .

From Fig. 4, it can be observed that WCLLS outperforms AMWCL-RSSI and WCL in localization accuracy. The explanation is that WCLLS increases the weights of anchors closer to the unknown node. It is also shown that the increase of the number of anchor nodes can reduce the localization error of WCLLS. When the number of anchor nodes is 8, the average localization error of WCLLS is approximately 0.6 m which is significantly lower than the average localization error of AMWCL-RSSI and WCL.

3.2. Localization Error Versus the Path Loss Exponent In this experiment we evaluate the effect that the pass loss exponent has on the location accuracy. Fig. 5 depicts the effect on localization error when varying the pass loss exponent. All nodes are deployed in a 100m x 100m area. Four anchors are respectively placed in four comers, 1000 sensor nodes are randomly placed in the region. We assume that PL0 = -60dB and the zero-mean Gaussian noise Na has a standard deviation of 3dB .

From Fig. 5, it can be observed that as the pass loss exponent increases, the error in location estimation increases for WCLLS. When ß>2. \, the average localization error of WCLLS is greater than the average localization error of WCL. So, we can see that the pass loss exponent has an important impart on the localization error of WCLLS. Clearly, it is shown that when ß is about 2, WCLLS can obtain relative comparison small localization error. When the pass loss exponent ß = 2. , the average localization error of WCLLS is about 0.54 m.

3.3. Localization Error Versus the Standard Deviation In this experiment we evaluate the effect that the standard deviation has on the location accuracy. Fig. 5 depicts the effect on localization error when varying the standard deviation. All nodes are deployed in an 100m x 100m area. Four anchors are respectively placed in four comers, 1000 sensor nodes are randomly placed in the region. We assume that PL0 = -60dB and ß = 2 .

From Fig. 6, it can be observed that as the standard deviation increases, the error in location estimation increases for WCLLS. Obviously, the standard deviation has an impact on the localization error of WCLLS. Additionally, WCLLS obviously outperforms WCL and AMWCL-RSSI in localization error.

3.4. Localization Error Versus Network Size In this Simulation, we evaluate the effect the size of the network has on the location error. We simulated three network sizes: 50m x 50m , 100m x 100m and 200m x 200m. Four anchors are respectively placed in four comers, 1000 sensor nodes are randomly placed in the region. We assume that PL0 = -60dB and ß = 2 , and the zero-mean Gaussian noise Na has a standard deviation of 3dB .

From Table 2, it can be observed that as the network size increases, the localization error increases for all three localization algorithms. The explanation is that the error of the RSS measurement increases as the network size increases. It also can be observed that WCLLS outperforms AMWCL-RSSI and WCL in localization accuracy. From Table 2, we can clearly know that the average localization errors of WCLLS in three network sizes are respectively about 0.2 m, 0.53 m and 1 m.

3.5. Experiments In this section, we analyze the performance of the studied localization schemes through experiments. We compare the proposed algorithm with WCL and AMWCL-RSSI. In this experiment, the proposed algorithm is tested in a 200 m x 200 m region of our University's campus lawn, 10 anchors are randomly placed in the region and an unknown node is placed in 50 different positions. Fig. 7, a wireless node is based on a MSP430 microprocessor and equipped with a compliant Chipeon CC2500 wireless module. We obtain the measured distance by (1).

Table 3 shows the localization error of three localization algorithms in real experiment. In Table 3, the localization error of WCLLS is 1.2 m which is lower than that of AMWCL-RSSI and WCL. Clearly, WCLLS outperforms WCL and AMWCL-RSSI in the localization accuracy.

4. Conclusions Many weighted centroid localization schemes have been widely used for WSNs. However, these schemes do not help, since the localization errors are high in practical deployments. To solve these problems, in this paper we have researched and analyzed many weighted centroid localization algorithms and RSS-based localization algorithms, and we have proposed a localization scheme, called Weighted Centroid Localization Algorithm Based on Least Square. WCLLS presents a Least-Square-based weight model which can reasonably weigh the proportion of each anchor node in the unknown node. In the proposed weight model, firstly, we utilize least square method to compute the weight. Secondly, the proposed weight model increases the weight of anchor node closer to the unknown node to estimate the location. Thirdly, the parameter is introduced into the proposed weight model, and we get the optimal value of through our real experiments. We have analyzed the performance of WCLLS through the network size, the number of anchor nodes, the standard deviation and the path loss exponent. All the experimental results demonstrate that WCLLS is superior to WCL and AMWCL-RSSI in the localization accuracy. From the experimental results, we can see that WCLLS is also suitable for an outdoor environment. More importantly, WCLLS has a lower localization error.

Acknowledgements The work is supported by National 863 Project (2013AA041101) and the 211 Project of Anhui University.

References [1]. D. Debashis, An Integrated Method for Location Registration of Mobile Terminals Based on Time, Distance and Zone, Journal of Computational Intelligence and Electronic Systems, Vol. 2, No. 1, 2013, pp. 20-28.

[2] . R. Anindita, D. Debashis, Intelligent Body Sensor Network for Pervasive Health Monitoring: A Survey, Journal of Computational Intelligence and Electronic Systems, Vol. 1, No. 1, 2012, pp. 67-81.

[3] . V. Ranga, M. Dave, A. K. Verma, MFZLP: Multihop Far Zone Leach Protocol for WSNs, Journal of Computational Intelligence and Electronic Systems, Vol. 2, No. 1,2013, pp. 45-49.

[4] . L. Mo, Y. He, Y. Liu, J. Zhao, S. Tang, X. Li, G. Dai, Canopy closure estimates with GreenOrbs: Sustainable sensing in the forest, in Proceedings of the Conference on ACM Sensor Systems, 2009, pp. 99-112.

[5] . I. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, A survey on sensor networks, IEEE Communications Magazine, Vol. 40, No. 8, August 2002, pp. 102-114.

[6] . F. Salvadori, M. D. Campos, P. Sausen, R. D. Camargo, C. Gehrke, C. Rech, M. Spohn, A. Oliveira, Monitoring in industrial systems using wireless sensor network with dynamic power management, IEEE Transactions on Instrumentation and Measurement, Vol. 58, No. 9, Sep. 2009, pp. 3104-3111.

[7] . H. Liu, H. Darabi, P. Baneijee, J. Liu, Survey of wireless indoor positioning techniques and systems, IEEE Transactions on Systems, Man, and Cybernetics, Part B, Cybernetics, Vol. 37, No. 6, Nov. 2007, pp. 1067-1080.

[8] . J. Zhao, W. Xi, Y. He, Y. Liu, L. Mo, Z. Yang, Localization of Wireless Sensor Networks in the Wild: Pursuit of Ranging Quality, IEEE/ACM Transactions on Networking, Vol. 21, No. 1, 2013, pp. 311-323.

[9] . W. Y. Chiu, B. S. Chen, C. Y. Yang, Robust Relative Location Estimation in Wireless Sensor Networks with Inexact Position Problems, IEEE Transactions on Mobile Computing, Vol. 11, No. 6, 2012, pp. 935-946.

[10] . K. Langendoen, N. Reijers, Distributed localization in wireless sensor networks: A quantitative comparison, Computer Networks, Vol. 43, No. 4, Nov. 2003, pp. 499-518.

[11] . E. Elnahrawy, X. Li, R. Martin, The limits of localization using signal strength: A comparative study, in Proceedings of the 1st Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, Oct. 2004, pp. 406-414.

[12] . D. Lymberopoulos, Q. Lindsey, A. Savvides, An empirical characterization of radio signal strength variability in 3-D IEEE 802.15.4 networks using monopole antennas, Wireless Sensor Networks, 2006, pp. 326-341.

[13] . G. Chandrasekaran, M. Ergin, J. Yang, S. Liu, Y. Chen, M. Gruteser, R. Martin, Empirical evaluation of the limits on localization using signal strength, in Proceedings of the 6th Annu, IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, Jun. 2009, pp. 1-9.

[14] . T. Pavani, G. Costa, M. Mazzotti, A. Conti, D. Dardari, Experimental results on indoor localization techniques through wireless sensors network, in Proceedings of the IEEE 63rd Vehicular Technology Conference-Spring, Vol. 2, May 2006, pp. 663-667.

[15] . C. Zhao, M. Liu, Y. J. Jia, T. Zhang, Weighted Centroid Localization Algorithm Based on Link Quality, in Proceedings of the International Conference on Computer Distributed Control and Intelligent Environmental Monitoring, 2012, pp. 840-843.

[16] . H. Q. Cheng, H. Wang, H. K. Wang, An improved centroid localization algorithm based on weighted average in WSN, in Proceedings of the 3rd International Conference on Electronics Computer Technology, Vol. 4,2011, pp. 258-262.

[17] . X. Q. Su, Z. M. Lei, Node Localization in WSN Based on Weighted Vectors Centroid Algorithm, in Proceedings of the 4th International Conference on Intelligent Networks and Intelligent Systems, 2011, pp.109-112.

[18] . X. Q. Su, Z. M. Lei, Improved Centroid Algorithm Localization for WSN Based on Particle Swarm Optimization, in Proceedings of the 4th International Symposium on Computational Intelligence and Design, Vol. 1,2011, pp. 139-142.

[19] . W. K. Chen, W. F. Li, S. Heng, Y. Bing, Weighted centriod localization algorithm based on RSSI for wireless sensor networks, Journal of Wuhan University of Technology, 2006, pp. 30-32.

[20] . R. Behnke, D. Timmermann, AWCL: Adaptive Weighted Centroid Localization as an efficient improvement of coarse grained localization, in Proceedings of the 5th Workshop on Positioning, Navigation and Communication, 2008, pp.243-250.

[21] . P. Pivato, L. Palopoli, D. Petri, Accuracy of RSSBased Centroid Localization Algorithms in an Indoor Environment, IEEE Transactions on Instrumentation and Measurement, Vol. 60, No. 10, 2011, pp. 3451-3460.

[22] . J. Blumenthal, R. Grossmann, F. Golatowski, D. Timmermann, Weighted Centroid Localization in Zigbee-based Sensor Networks, in Proceedings of the IEEE International Symposium on Intelligent Signal Processing, October 2007, pp. 1-6.

[23] . F. Reichenbach, D. Timmermann, Indoor localization with low complexity in wireless sensor networks, in Proceeding of the IEEE International Conference on Industrial Informatics, Aug. 2006, pp. 1018-1023.

[24] . H. Y. Shi, A new weighted centroid localization algorithm based on RSSI, in Proceeding of the International Conference on Information and Automation, 2012, pp. 137-141.

[25] . L. S. Xu, K. Wang, Y. Q. Jiang, F. F. Yang, Y. H. Du, Q. C. Li, A study on 2D and 3D weighted centroid localization algorithm in Wireless Sensor Networks, in Proceeding of the 3rd International Conference on Advanced Computer Control, 2011, pp. 155-159.

[26] . H. Q. Cheng, H. K. Wang, H. Wang, Research on Centroid Localization Algorithm That Uses Modified Weight in WSN, in Proceeding of the International Conference on Network Computing and Information Security, Vol. 2,2011, pp. 287-291.

[27] . M. Chen, H. Liu, Enhance Performance of Centroid Algorithm in Wireless Sensor Networks, in Proceeding of the 4th International Conference on Computational and Information Sciences, 2012, pp.1066-1068.

[28] . J. Li, H. P. Liu, A new weighted centroid localization algorithm in coal Mine wireless sensor networks, in Proceeding of the 3rd International Conference on Computer Research and Development, Vol. 3, 2011, pp. 106-109.

[29] . K. Azadeh, P. Konstantinos N., A. N. Venetsanopoulos, Kernel-Based Positioning in Wireless Local Area Networks, IEEE Transactions on Mobile Computing, Vol. 6, No. 6, 2006, pp. 689-705.

[30]. S. H. Fang, T. N. Lin, Cooperative multi-radio localization in heterogeneous wireless networks, IEEE Transactions on Wireless Communications, Vol. 9, No. 5,2010, pp. 1547-1551.

[31]. M. Sugano, T. Kawazoe, Y. Ohta, M. Murata, Indoor localization system using RSSI measurement of wireless sensor network based on ZigBee standard, Wireless Sensor Networks, 2006, pp. 1-6.

1 Shaoguo Xie,2 Yanjun Hu, 3 Yi Wang, 4 Yingguan Wang 1,2,3 Key Laboratory of Intelligent Computing & Signal Processing, Ministry of Education, Anhui University, Hefei Anhui 230039, China 4 Key Laboratory of Wireless Sensor Network & Communication, Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences, 865 Changning Road, Shanghai 200050 China 1 Tel: 65107154, fax: 65107154 1 E-mail: [email protected] Received: 12 March 2014 /Accepted: 31 July 2014 /Published: 31 August 2014 (c) 2014 IFSA Publishing, S.L.

[ Back To TMCnet.com's Homepage ]