Critical Analysis of Distributed Localization Algorithms for Wireless Sensor Networks

Published Online July 2016 in MECS DOI: 10.5815/ijwmt.2016.04.07

Recent advancement in wireless communication and low-cost sensor technology has enabled the emergence and evolution of wireless sensor networks (WSNs) as new paradigm of computer networking [1], [2]. A wireless sensor network is poised of huge number of low-cost, tiny sensor nodes enabled with sensing, processing and transmitting capabilities [3], [4]. A simple wireless sensor network is shown in fig. 1.

* Corresponding author. Tel.: +91-9897858828; Fax: +91-132-2714310

For this Procedia the files must be in MS Word format only and should be formatted for direct printing.

Fig.1.A simple wireless sensor network (Source: [8])

The wireless sensor networks were initially motivated by military applications but nowadays, WSNs are used in various civilian application areas like: monitoring, tracking, control, automation and healthcare applications. In many applications, the location information of sensor node is of much importance. Location of sensor node is crucial to find. Localization is a method of determining the position on a node. The localization schemes can be categorized on the basis of various parameters like availability of GPS, presence of anchors, computation model, range measurements etc [5],[6],[7],[33]. On the basis of computation model, the localization approaches can be classified into two categories: centralized and distributed localization techniques. In centralized model, all the measurements are collected and processed at central base station while in distributed model, computation take place at every node. Due to hardware restrictions of sensors, solutions in distributed schemes are being considered as cost effective solutions. In this paper, various distributed localization schemes have been discussed. The rest of the paper is organized as follows. Section 2, describes the overview of localization process and the taxonomy of localization algorithms. Section 3, describes the distributed localization algorithms and its variants. Section 4 covers the analysis and discussion. Section 5 concludes the paper.

• 2.    Localization Overview

• 2.1.    Localization Process

• 2.2.    Localization Algorithms

Localization is anticipated through the communication between localized or known node and unlocalized node for obtaining their geometrical situation or position [9],[10]. The localization overview contains the brief overview of localization process and the taxonomy of the localization scheme.

Localization process situates sensor nodes on the basis of input data. The common inputs are the anchor positions (if anchor available), connectivity information, distance or angle between nodes. The measurement techniques can be proximity based, distance based or angle based. The proximity based techniques are based on radio or acoustic waves. Localization algorithm is executed in an important step in the localization process. A localization process objective varies accordingly. The overview of a localization process is shown in fig 2.

Fig.2.Overview of a localization process

On the basis of input data, a localization algorithm determines the nodes location in the network. The Inputs be the range estimates with or without the position of beacons or access point. The localization algorithms are classified on the basis of various parameters like availability of GPS, presence of anchors, computation model, range measurements etc [6],[7],[34]. The taxonomy of localization techniques is shown in fig. 3.

Fig.3.Taxonomy of localization schemes in WSNs

On the basis of computation model, the localization approaches can be categorized into two types: centralized and distributed localization schemes [11], [35]. In continuation, the localization algorithms are broadly classified into two types given as:

• •    Centralized localization algorithms

• •    Distributed localization algorithms

• 3.    Distributed Localization Algorithms

• 3.1.    Beacon based distributed localization algorithms

In distributed techniques, each sensor node gives restricted communication with nearer nodes to obtain the position information [11],[12]. In distributed localization, sensor nodes perform the required computation themselves and communicate with each other to get their own location in network. There is no clustering in distributed schemes. The taxonomy of distribute localization is shown in fig.4.

Fig.4.Taxonomy of distributed localization algorithms in WSNs

Beacon based localization algorithms [13],[14],[15],[16] begin with group of beacons and unknown nodes to obtain measurement to a less number of sensor After that measurements are used to find out their own locations. These algorithms can be classified into diffusion and gradients algorithms. In diffusion, node’s most probable location is at the centroid of its nearby recognized nodes. The popular algorithms in this category are:

> Approximate Point in Triangle (APIT)

APIT is an area based range free scheme which assumes that some of nodes those are aware of their positions outfitted with high powered transmitters. APIT [13] is located in area to carry out position estimation by separating the area into triangular zones between anchors. Each node’s presence inside or outside the triangle regions allows declining the viable location until and unless every possible sets have reached to an acceptable accuracy. The flowchart representation of APIT algorithm is shown in fig. 5.

In gradient algorithm, unknown nodes obtain their locations through multilateration. It hop count which is initially set to zero and incremented as it pass on to other nearby nodes. This algorithm follows certain steps such as:

• •    In the first step, anchor nodes broadcasts a message carrying it’s coordinated and hop count value.

• •    In the second step, unknown node determines the shortest path between itself and anchor node from

which it receives beacon message [17]. The estimated distance can be calculated by following equation:

“ji — ^j.Ai ^hop

• •    In the third step, minimum error in which node calculate its coordinate is computed by following equation:

  

• 3.2.    Relaxation based distributed localization algorithms

• 3.3.    Relaxation based distributed localization algorithms

• 3.4.    Hop based distributed localization algorithms

Where dji is gradient propagation based estimated distance.

The relaxation based algorithms can be classified on basis of two approaches: spring model approach and cooperative ranging approach. Anchor free localization algorithms [18] (AFL) are based on spring model approach. The assumption based coordinate system (ABC) are based on cooperative ranging [19], exploits the soaring network connectivity. The benefit of this approach is that there is no need of global resource or communication.

Coordinate system stitching based techniques divides the whole network into small and overlapping sub regions, all of them construct an optimal local map. After that those local maps are merged into a single large map known as global map. The coordinate system stitching based distributed algorithms are generally based on two approaches: cluster based and inter node distance based approach. In the cluster based distributed algorithm [20], the node have distance estimation ability in close proximity. Cluster based distributed localization is mainly consists of two phases. First one is cluster localization phase and second one is cluster transformation phase. The benefit of this approach is that it supports lively node inclusion and mobility. The inter node distance approach based distributed localization algorithm [21] construct a map along with distance matrix. This approach possibly curtails the differences among them by some transformations. The benefit of this approach is that it is anchor free localization.

Hop based localization techniques works on the basis of the hop based connectivity range between the anchor nodes and nearby nodes. Hop based techniques are categorized as: one hop and multi hop localization techniques. The popular hop based techniques are given as:

> DV-Hop

DV-Hop localization [13] uses a mechanism similar to the classical distance vector routing method. One anchor node broadcasts a message which contains the anchors’ positions with hop count. Each receiving node keeps the minimum value, which it receives. After that it ignores the other message with higher values [22,23]. Messages broadcasted out with hop count values incremented at every middle hop. In this scheme, all nodes in the network and other anchors obtain the shortest distance in hops. On the whole single hop distance in anchor i can be computed as:

Hop Sizet =

2 hj

Where anchor j is at location (x i , y j ) and h j is the distance in hops from j to i. The triangulation is used location estimation of unknown nodes. In this algorithm for two dimensional deployment of network, minimum 3 anchor’s locations are used as shown by symbol A in fig.6.

Multi Hop techniques are able to compute a connectivity graph. The multi dimensional scaling (MDS) uses connectivity information considering the nodes range. This scheme has following steps [14] given as:

• •   In first step, the distance estimation between each viable pair of nodes is done.

• •   In second step, MDS is used for deriving the locations to fit the estimated distance.

• •    Finally in last step, optimization is done by putting the known locations into account.

• 3.5.    Interferometric ranging based distributed localization algorithms

• 3.6.    Error propagation aware distributed localization algorithms

• 3.7.    Hybrid distributed localization algorithms

• 4.    Analysis and Discussion

• 4.1.    Comparison

In large scale sensor networks, there are several kind of MDS methods are used such as metric, non metric, classical, weighted. The multi hop based process allows multi hop nodes to collaborate in finding better position estimates [24].

The radio interferometric positioning system (RIPS) [25],[26],[27] exploits interfering RF signal emitted from two locations to obtain the essential ranging information. The synchronization problems cause relative phase offset of the signal. Relative offset is utility of the comparative positions of the involved sensor nodes and the carrier frequency.

Error propagation aware (EPA) algorithm [28] integrates the path loss and measurement error model. Initially, beacon nodes disseminate their information that contains their IDs, global coordinates, and the error variance. After that, node positions are computed by integrating its weight matrix into weighted least square (WLS) algorithm [29]. After obtaining its own position the node becomes beacon and start broadcasting its ID, global coordinates, and ranging variance. This method is repetitive and continues until and unless each node obtains its positions.

Hybrid localization can be depicted with the combination of two or more localization techniques. In [30] the authors’ presents a scheme composed of two techniques: multidimensional scaling (MDS) and proximity based distance mapping (PDM). Initially a few anchors are deployed as primary anchors. In the first phase, some anchors are chosen as secondary anchors those are localized through MDS. In the second phase, the normal sensors are localized through PDM.

WSNs have many constraints such as node size, energy, and cost etc. It is indeed necessary to consider these constraints before designing any localization mechanism. Node communication and data transmission take much power and consume more energy. Many localization algorithms have been proposed; however most of them are application specific. So the comparison of various localization algorithms and some open issues in localization schemes are discussed in this section.

All localization techniques have their own merits and limitations, making them appropriate for diverse applications. In this paper, we have performed comprehensive review on various localization techniques and compare them. After that we summarized then comparison in tabular form. The comparison between centralized and distributed localization is summarized in table 1. The comparison of some distributed localization schemes is summarized in table 2. The summary of comparison between distributed localization is shown in table 3.

Table 1.Comparison between centralized and distributed techniques

Techniques   -----► Factors	Centralized Techniques	Distributed Techniques
Cost	More	Less
Power consumption	More	Less
Accuracy	70-75%	75-90%
Dependency       on additional hardware	No	Yes
Deployability	Hard	Easy

Table 2. Comparison between some distributed localization schemes

Parameter Technique	Node         Cost          Accuracy     Overhead      Scalability density
APIT	>16         Low          Good        Small         Yes
DV-Hop	>8          Medium       Good        Largest        No
Multi-Hop	>12         High         Good        Large         No
Gradient	>6          Low          Average      Large         Yes

Table 3. Summary of comparison between distributed localization schemes in WSNs

Schemes	Objective	Computation model	Cost (communicati on & computation)	Accurac y	Scalability
T. He et al. [13]	Present a algorithm to make cost effective schemes	Distributed	Low	Low	Yes
A. Savvides et al. [14]	Present a collaborative multilateration approach to enable nodes for accurate estimation of locations via beacon	Distributed	Low	Low	Yes
S. Simic et al. [15]	Present a decentralized approach for node localization in wireless network	Distributed	Low	Low	Yes
J. Bachrach et al. [16]	Present an approach to find out the position of network when the nodes have been scattered over harsh environment	Distributed	Low	Low	Yes
N. Priyantha et al. [18]	Present an anchor free approach for localization where node start from casual initial assignments and converge to consistent solution	Distributed	Low	Low	Yes
C. Savarese et al. [19]	Present a cooperative ranging approach to get rid of burden due to beacons	Distributed	Low	Low	Yes
David Moore et al. [20]	Present a scheme that localize sensor nodes in a region by use of robust quadrilaterals	Distributed	Low	Low	Yes
Lambert Meertens et al. [21]	Present an approach that construct a global coordinate system in network	Distributed	Low	Low	Yes
M. Maroti et al. [25]	Present a algorithm on the basis of Interferometric ranging	Distributed	High	High	Yes
N. Patwari et al. [26]	Present a technique based on Interferometric ranging	Distributed	High	High	Yes
Rui. Huang et al. [27]	Present a localization algorithm based on Interferometric ranging for larger networks	Distributed	Low	High	Yes
N. A. Alsindi et al. [28]	Present an error aware algorithms for localization in WSNs	Distributed	Low	High	Yes
King-Yip Cheng et al. [30]	Presents a distributed algorithms composed of MDS and PDM	Distributed	Low	High	Yes
Jaime Lloret et al. [31]	Present a localization algorithm by using inductive and deductive approach	Distributed	Low	High	Yes
A .A. Ahmad et al. [32]	Present a localization algorithm composed of MDS and APS	Distributed	Low	High	Yes

• 4.2.    Issues in localization techniques

Sensor network localization is an active research area and has numerous issues so still has a lot of scope for research community. Some of the issues need to be addressed are:

• •    Cost effective algorithms: During the design of localization algorithm, designer must keep in mind the cost incurred in hardware and deployment. GPS is not suitable because of its cost and size of hardware.

• •    Robust algorithms for mobile sensor networks: Mobile sensors are much useful in some environments because of mobility and coverage facility. Hence, development of new algorithms is needed to accommodate these mobile nodes.

• •    Algorithms for 3 Dimensional spaces: For many WSN applications, accurate location information is crucial. The most of the reported algorithms are pertinent to 2D space. On the other hand, some the application needs 3 D positioning of WSNs.

• •    Accuracy: If there is incorrect estimation of node position, then localization accuracy is compromised. Designer must keep in mind that accuracy is very much important factor in sensor localization.

• •    Scalability: In large scale deployment, it is generally desirable to enlarge the monitoring area amid nodes. So careful observations are required to check the scalability of localization techniques.

• •    Security: localization accuracy of algorithms is of much importance. Some algorithms have very good localization accuracy. But, at real time usage they are prone to attacks. Hence, the security of node localization is crucial.

• 5.    Conclusions

Wireless sensor network localization has gain lot of attention of research community. This concern is likely to grow further with the rise in WSN based applications. This paper had performed a review of various distributed localization techniques and their corresponding localization algorithms for sensor network. In this paper, the taxonomy of localization techniques has been discussed. In this work, we compare the different localization techniques and represent that comparison in tabular form. This paper reported the classification of distributed localization algorithms on the basis of various measurements. Among all reported schemes, the comparative analysis done by us to conclude that each algorithm has its own features and none is absolutely best. On the whole, the centralized techniques are either expensive or susceptible to network dynamics. However, the distributed techniques are imprecise and easily affected by node density. Regardless of significant research development in this area, some unsolved problems are still there. At the end, we focused on the certain issues need to be addressed. This paper is very useful for the research group those are interested in development, modification and optimization of localization algorithms for wireless sensor networks.

The authors would like to thanks the ministry of human resource development (MHRD) for providing financial support for this work under research scholar’s grant.

• [1]    Akyildiz, I.F., Su, W., Sankarasubramaniam, y., Cyirci, E.: Wireless sensor networks: a survey.Computer Networks 38(4), 393--422, 2002.

• [2]    Romer, K., Friedemann, M.: The Design Space of Wireless Sensor Networks. IEEE Wireless Communications 11 (6), 54--61, 2004.

• [3]    Sohraby, K., Minoli, D., Znati,T.: Wireless Sensor Networks: Technology. Protocols, and Applications, John wiley & sons, 2007.

• [4]    Yick, J., Biswanath, M., Ghosal, D.: Wireless Sensor Network Survey. Computer Networks 52(12), 2292-2330, 2008.

• [5]    Mao, G., Fidan, B., Anderson, B. D..: Wireless sensor networks localization techniques. Computer Networks 51(10), 2529--2553, 2007.

• [6]    Samira A.: A Review of Localization Techniques for wireless sensor networks . J .Basic Appl.Sci.Res 2(8), 795--7801, 2012.

• [7]    Jing W., Gosh, R.K., Das,S.K.: A survey on sensor localization. J Control Theory Appl 8(1), 2--11, 2010.

• [8]     http://mdpi.com/1424-8220/9/11/8399.

• [9]    Langerdoen, K., Reijers, N.: Distributed localization in wireless sensor networks: a quantative comparison. Computer Networks 43(4), 499--518, 2003.

• [10]    Yunhao, L., Zeng, Y., Xiaoping, W., Lirong J.: A Location, localization and localizability.,Journal of Computer Science and Technology 25(2),274--297, 2010.

• [11]    Tareq, A. A., Shuang H. Y: A survey: localization and tracking mobile targets through wireless sensor networks. ISBN:1-9025-6016-7@PGNet, 2007.

• [12]    Stojmenovic, I., Bachrach, J., Taylor, C.:Localization in Sensor Network. In: Handbook of Sensor Networks: Algorithms and Architecture s , pp.277--310, 2005 .

• [13]    He, T., Huang, C., Blum, B., Stankovic, J., Abdelzaher,T.:Range-free localization schemes in large scale sensor networks In: Ninth Annual International Conference on Mobile Computing and Networking (MobiCom'03 ), pp.81--95, San Diego, CA, USA, 2003.

• [14]    Savvides, A., Park, H., Srivastava, M.: The bits and flops of the n-hop multilateration primitive for node localization problems. In: 1st ACM international Workshop on Wireless Sensor Networks and Applications (WSNA'02) , pp.112--121, Atlanta, USA, 2002.

• [15]    S. Simic and S. Sastry, “Distributed localization in wireless ad hoc networks”, Technical Report UCB/ERL M02/26, UC Berkeley, 2002

• [16]    Bachrach, J., Nagpal, R., Salib, M., Shrobe, H.: Experimental Results and Theoritical Analysis of a SelfOrganizing a Global Coordinate System from Ad Hoc Sensor Networks. Telecommunications System Journal 26(2-4), 213--233, 2004.

• [17]    Tanvir, S., Jabeen, F., Khan, M.I., Ponsard, B.:On propagation properties of beacon based localization protocols for wireless sensor networks. Middle East Journal of Scientific Research 12(2), 131--140, 2012.

• [18]    Priyantha, N., Balakrishnan, H., Demaine, E., Teller, S.: Anchor free distributed localization in sensor networks. MIT laboratory for computer science, Technical Report.

• [19]    C. Savarese, J. Rabaey, and J. Beutel.: Locationing in distributed ad-hoc wireless sensor networks. In: Proceedings of IEEE International conference on acoustics, speech, and signal processing (ICASSP),Salt lake city, Utah, USA, pp.2037-2040, 2001

• [20]    Moore ,D., Leonard, J., Rus, D.,Teller, S.: Robust distributed network localization with noisy range measurements. In: Second ACM Conference on Embedded Networked Sensor Systems (SenSys), Baltimore, MD, 2004.

• [21]    Meertens, L., Fitzpatrick, S.: The distributed construction of a global coordinate system in a network of static computational nodes from inter node distances. Kestrel Institute Technical Report KES . U.04.04,

  Kestrel Institute, Palo Alto, 2004.

• [22]    Brito,, L.M.P.L., Peralta, L.M.R.: An analysis of localization problems and solutions in wireless sensor networks. Tekhne Revista de Estudos politecnicos Polytechnical Studies Review 6, 2008.

• [23]    Labraoui, N., Gueroui, M., Aliouat, M.: Secure DV-hop localization schemes against wormhole attacks in Wireless sensor networks. Transactions on Emerging Telecommunication Technologies 23(4), 303--312, 2012.

• [24]    Pal, A.: Localization algorithms in wireless sensor networks: current approaches and future challenges. Network Protocols and Algorithms (2), 45--73, 2010.

• [25]    Maroti, M., Kusy, B., Balogh, G., Olgyesi, P.V., Nadas, A, Molnar,K., Dora, S., Ledeczi,, A.: Radio Interferometric Geolocation. In: 3^rd International Conference on Embedded Networked Sensor Systems (Sensys), San Diego, California, USA, pp.1--12, 2005.

• [26]    Patwari, N., Hero, A.A.: Indirect Radio Interferometric Localization via Pairwise Distances. In: 3^rd International Workshop on Embedded Networked Sensor Systems (Emnets 2006 ) , Bostan, MA , 2006.

• [27]    Huang, R., Gergley, V. Z., Huber,M.: Complexity and Error Propagation of Localization using Interferometric Ranging. In: IEEE International Conference on Communications (ICC 2007), Glassgow, Scotland, pp.3063--3069, 2007.

• [28]    Alsindi, N.A., Pahlavan, K., Alavi, B.:An Error Propagation Aware Algorithms for Precise Cooperative Indoor Localization. In: IEEE Military Communication Conference (MILCOM 2006), Washington DC, USA, pp.1--7, 2006.

• [29]    Kim, E., Kim, K.: Distributed estimation with weighted least squares for mobile beacon based localization in wireless sensor networks. IEEE Signal Processing Letters 7(6), 559--562, 2010.

• [30]    Cheng, K.Y., Lui, K.S., Tam, V.: Localization in Sensor Networks with Limited number of anchors and Clustered Placement. In: wireless communication and Networking Conference, 2007 (IEEE WCNC), pp.4425--4429 (2007).

• [31]    Lloret, J., Tomas, J., Garcia, M. Canovas, A.: A hybrid stochastic approach for self location of wireless sensors in indoor environments. Sensors 9(5), 3695-3712, 2009.

• [32]    Ahmad, A.A., Shi, H.. Shang, Y.: Sharp: A new approach to relative localization in wireless sensor networks. In:  IEEE International Conference on Distributed Computing Systems (ICDCS), 2005,

  Columbia, USA (2005).

• [33]    Santar Pal Singh, S. C. Sharma.: Range Free Localization Techniques in Wireless Sensor Networks: A Review. Procedia Computer Science 57, pp.7-16, 2015.

• [34]    L. H. Zhao, W. Liu, H. Lei, R. Zhang, and Q. Tan.: The detection of boundary nodes and coverage holes in wireless sensor networks. Mobile Information Systems, 2016.

• [35]    Guangjie Ha n , Huihui Xu, Trung Q.Duong, Jinfang Jiang, Takahiro Hara.: Localization algorithms of Wireless Sensor Networks: a survey. Telecommunication Systems, April 2013.

Santar Pal Singh received his B.Tech. degree in Computer Sc. & Engineering from Kamla Nehru Institute of Technology, Sultanpur (U.P.) in 2001 and the M.Tech. degree in Computer Sc. & Engineering from Samrat Ashok Technological Institute, Vidisha (M.P.) in 2006. Now he is student of Ph.D. degree in Computer Sc. & Engineering discipline, DPT, Indian Institute of Technology Roorkee (India). His research interest includes data mining, data security and wireless sensor networks.

ProfessoS. C. Sharma received his M.Sc.(Electronics), M.Tech. (Electronics & Communication Engg.) and Ph.D. (Electronics & Computer Engg.) from IIT Roorkee (erstwhile University of Roorkee).He has published over two hundred research papers in national and international journals/conferences and supervised more  than  30

projects/dissertation of PG students. He has supervised 12 Ph.D. in the area of Computer Networking, Wireless Network, Computer Communication and continuing supervising Ph.D. students in the same area.

He has successfully completed several major research projects independently funded by various Govt. Agencies like AICTE, CSIR, MHRD, DST, and DRDO.