Localization in Wireless Sensor Networks Using Rigid Graphs: A Review

Abstract

The applications of wireless senor networks (WSN) vary in diversified field, at different geographic locations. Location aware computing is the key for the success of such applications. Henceforth, there is a need of efficiently estimating the location of individual WSN nodes deployed in the remote geographic locations. Manually estimating the locations of these densely deployed nodes is impossible, therefore the WSN nodes must be able to localize themselves collecting local information from its neighboring nodes, which is called as the localization technique. The information used for localization is generally distance and bearing information obtained from the ranging techniques which are not accurate and are prone to error. Therefore there is a need for techniques which can cope up with this perturbed distance information. Rigid graphs have the property of sustaining various kind of deformations due to translation, rotation and reflection. Hence, it is more fruitful using the concepts of rigid graphs, for estimating accurate location coordinates from error prone distance measurements. In this paper we will scrutinize the sound theoretical background which defines the need of rigid graph based localization and different localization techniques, with associated algorithms which uses the concepts of rigid graphs.

1 Introduction

The manual configuration of WSN nodes is not feasible because the number of WSN nodes deployed will be always huge in number and deployment will be in human unattended geographic regions [1], while even GPS cannot be installed in every WSN node because it is costly hardware and it does not support indoor localization [19]. These limitations lead to developing of localization algorithms where certain nodes known as anchor nodes know its position and the remaining nodes estimate positions based on those nodes that have position information. These localization techniques are termed as cooperative localization or in-network localization or self localization [7]. Usually, geographical localization methods use various information from the deployed WSN, such as ranging information like inter sensor distances, inter sensor angle (bearings), and neighbor information. Table 1 gives the information list classified as range based and connectivity based. The main reason why ranging based distance information is used for localization is due to the fact that range based measurements does not need extra hardware which makes it cost effective and also because WSN node is a tiny device and adding extra hardware into it is not feasible.

The localization algorithms are classified into the following classes [19]:

• 1. Anchor-based and Anchor-less In the Anchor-based localization schemes few WSN nodes will be positioned in known coordinates manually or using a GPS. The anchor nodes are also alternatively called as landmarks. The percentage of anchor nodes to be deployed depends on the localization algorithm designed. The Anchor-less localization methods as termed will not have any nodes with known position coordinates. They must utilize the local distance or angle information between the neighboring nodes to estimate the positions of nodes.

• 2. Fine-grained and coarse grained The WSN nodes will be communicating each other with its neighboring nodes and exchanging some information. This type of classification is based on the granularity of this information obtained during exchange. Fine grained algorithms use exact information like distance or angle using RSSI estimation or TOA methods. The coarse grained algorithms tend to use less accurate information like proximity to estimate the location information

• 3. Centralized and distributed algorithms These algorithms are based on where exactly the location estimation computation takes place. In the Centralized method a single node will be performing the computations required for estimating location coordinates. In the Distributed method every node takes part in location estimation computation and then exchanges obtained result with its neighboring nodes.

Table 1 Classification of localization techniques

Table 2 Classification of different information used in localization

All the above three classified localization algorithms use different information metrics which is highlighted in Table 2. There was high motivation for using graph theory based localization techniques, where estimating the positions of vertices is called as graph realization problem. WSN nodes are modeled as the vertices of the graph and the error prone distances are the length of the edges. Because of error in distances the position estimation will be ambiguous. Therefore, the concepts of rigid graphs are used to solve this kind of problems. Non rigid graphs will be prone to deformations and hence will generate multiple ambiguous realizations. Rigid graphs have specific properties which makes them non-deformable and hence more suitable for for efficient localization.

2 Preliminaries

2.1 Graph Theoretical Framework for Localization

Fig. 1

Depicts a rigid WSN graph framework in a 2-d coordinate system with vertices as WSN nodes and the edges between them as the communication links

In [6, 14] authors have considered a d-dimension point formation at $\widehat{p}$=column{$p_1$, $p_2$, ..., $p_n$}, usually denoted as F(p), which is the Euclidean coordinate system, consisting of a set of n number of points $p_1$, $p_2$, ..., $p_n$in $R^d$, where d represents 2 or 3 dimension. In terms of WSN, the points $p_i$ corresponds to the positions of WSN nodes in forming the network. The communication link is the inter sensor node distance. In this coordinate of points we deduce communication links between points $p_i$ and $p_j$ , where i and j are integers of set $i=(1,2, \ldots ,n)$. Length of the communication link is the Euclidean distance between the points $p_i$ and $p_j$. Figure 1 shows a 2-dimensional point formation of WSN graph with vertices as the WSN nodes and edges between vertices as communication links.

A WSN graph N(S, D), where S represents the WSN nodes and D the distance between WSN nodes, can be represented by a graph $G=$ (V, E) with a vertex set V and a edge set E, where each vertex $i\in V$ is related with a sensor node $S_i$ in the network graph and each edge $(i,j)\in E$ relates to a sensor pair $S_i$, $S_j$ for which the inter sensor distances $d_{ij}$ are known [19]. We call $G=(V, E)$ the underlying graph of the sensor network N(S, D). A d-dimensional $(d\in {2, 3})$ representation of graph is mapping of a graph $G=(V, E)$ to the point formations $\widehat{p}:V\rightarrow R^d$ [19]. Given graph $G=(V,E)$ and a d-dimensional $(d\in {2, 3})$ representation of it, the pair (G, p) is termed as a d-dimensional framework. A distance set $\widehat{D}$ for G is set of distances $\widehat{d}_{ij}>0$ defined for all edges $(i, j)\in E$. Given the distance set D for the graph G, a d-dimensional $(d \in {2,3})$ representation $\widehat{p}$ of G is a realization if it results in $||\widehat{p} (s_i)- \widehat{p} (s_j)||= d_{ij}$ for all pairs of i, j where $(i, j)\in V$. We call a d-dimensional realization of $(G, \widehat{D})$ and (G, p) a d-dimensional realization framework.

Some basic definitions related to rigid graphs defined below:

Definition 1

Rigid and Flexible A framework is called flexible if we have a continuous deformation starting from the known configuration to another, such that edge lengths are preserved. If no such deformation exists, then it is called rigid.

Definition 2

A rigid framework is minimally rigid if it becomes flexible after an edge is removed.

Definition 3

A rigid framework is redundantly rigid , if it remains rigid upon the removal of any edge.

Figure 2 shows the flexible and rigid frameworks.

In $R^2$, the rigidity test of a graph can be done by using the combinatorial necessary and sufficient condition given by [3]

Theorem 1

Let $G=(V,E)$ be a graph in $R^2$, where $|V|>1$, is generically rigid if and only if there exists a subset $E'\subseteq E$ such that $|E'|=2|V|-3$ and for subset $E''\subseteq E'$, $|E''|\le 2|V(E'')-3$.

2.2 Localizability Analysis

The process of localization is a costly affair as it consumes lot of resources like energy, computational time etc. Therefore in the recent years research is carried on finding out first whether the given WSN graph is able to be localized based on certain graphical properties and theorems [18]. In WSN graph $G = (V,E)$, every node is realized as a point formation. If there is a unique location $( \widehat{p}):V\rightarrow R^d$ for every node belonging to the node set V such that $\widehat{d}_{ij}=||\widehat{p}(i)- \widehat{p} (j)||$ for all the edges, then we say that such a graph is LOCALIZABLE. Thus, localizability deals with unique realization of a WSN graph. Some class of graphs called as rigid graphs are analyzed in recent research to carry out unique localization. Localizabilty testing of the whole network is termed as network localizability and of individual WSN node is termed as node localizabilty [25].

Fig. 2

In (a), a flexible framework is depicted. In (b) Flexible framework whose edge length is varied is shown. In (c) a rigid framework is shown. In (d) a redundantly rigid framework is shown

Based on k-connected graph property and redundantly rigid graph following necessary and sufficient condition was gven by [15].

Theorem 2

A graph $G=(V,E)$ in $R^2$ with $|V|\ge 4$ is generically globally rigid if and only if it is 3-connected and redundantly rigid.

2.3 Trilaterations and Quadrilaterations

Generically globally rigid (GGR) graphs are labeled by using the notions of trilateration and quadrilateration graphs. Consider a graph G(V, E) in $R^2$, applying trialteration on the GGR graph G is nothing but addition of new vertex v to G. Then there should be at least three edges joining v to the vertices in V. A trilateration graph G(V, E) in $R^2$ is set of ordered pair of vertices $\{(v_1,v_2, \ldots , v_n)\}$ such that the edges $(v_1,v_2), (v_1,v_3 ), (v_2,v_3)$ are all present in edge set E and each vertex $v_i$ for i varying from {$i=$ 4, 5, ..., n} remains connected to three of the vertices $\{v_1,v_2, \ldots ,v_{i-1}\}$. The trilaterartion graph can be obtained by using consecutive $n-3$ trialetration procedure for the graph of vertices $\{v_1,v_2, \ldots , v_3\}$ and the edges between them and adding 3 vertices to $v_i$ at {$i=$ 1,2, ..., $n-3$}.

Quadrilateration is a procedure on GGR graphs G(V, E) in $R^3$ where new vertex v is added to G. In this case should be at least four edges joining v to the vertices in V. A quadrilateration graph G(V, E) in $R^3$ is set of ordered pair of vertices {($v_1$,$v_2$, ...,$v_n$)} such that the edges $(v_1,v_2)$, $(v_1,v_3 )$, $(v_1,v_4 )$, $(v_2,v_3 )$, $(v_2,v_4 )$, $(v_3,v_4)$ are all present in edge set E and each vertex $v_i$ for i varying from {$i=$ 5, 6, ..., n} remains connected to three of the vertices {$v_1$,$v_2$, ..., $v_{i-1}$}. The quadrlateration graph can be obtained by using consecutive $n-4$ quadrilateration procedure for the graph of vertices $v_1, v_2,v_3, v_4$ and the edges between them and adding four vertices to $v_i$ at {$i=$ 1, 2, ..., $n-4$}. The graphs and sub graphs which have these trilateration and quadrilateration ordering will reduce the computational complexity of localization by greater margin. There are certain classes of graph which can be brought under the classification of trilateration and quadrilateration graphs by using various mechanisms. GGR graphs of trilateration and quadrilateration can be obtained by addition of extra edges [2]. Adding extra edges in sensor network localization means increase of the communication radius by varying the antenna transmission power. This mechanism will allow the sensor nodes to determine the distances not only to 1-hop neighbour also to 2-hop, 3-hop and so on neighbors.

Consider a network topology with a communication radius R. If we double the communication radius R by 2R, then all the 2-hop neighbors when communication radius was R will become the 1-hop neighbor when communication radius is 2R. Going on in similar fashion by increasing the communication radius to 3R then we can make the 3-hop neighbor of R as 1-hop neighbor of 3R.

3 Rigid Graph Localization: Theory and Formal Analysis

A strong theoretical and formal background about rigid graphs is provided by authors in literature [14, 17, 29]. Rigid graphs graphical properties are best suited for the connectivity properties in WSN localization, which in turn incurred applying of the rigid graph theory into WSN localization. A formal and theoretical analysis of WSN localization using rigid graphs is dealt extensively in literature [3, 4, 8,9,10] respectively. The different conditions for unique localization of WSN was found and certain theorems were developed.

3.1 Formal Analysis of WSN Localization Using Distance Information

In [4], the authors have extensively dealt with the theoretical aspects of WSN localization. The anchor nodes priory knows their locations and the non-anchor nodes estimate their position information based on calculating the distance to its neighboring nodes. The paper mainly deals with following aspects:

• The WSN localization problem is modeled using grounded graphs (where edges are added from anchor nodes to the remaining anchor nodes) and rigid graph theory is used to examine the unique localizability conditions and build uniquely localizable networks.

• The computational complexity of WSN localization is examined.

• Localization for randomly deployed WSN nodes is examined.

The localization problem is summarized by [7] as follows:

Theorem 3

[7] Let N(S, D) be a sensor network graph in d dimension. Let (G, p) be the realization framework for the underlying graph N(S, D). Then the sensor network localization problem is solvable only if (G, p) is Generically Globally Rigid (GGR).

The authors remark that many localization techniques and algorithms have been developed, but those pose problems in the following areas:

• 1. What are the properties defining unique localizability?. In other terms, when localization problem can be solved uniquely?

• 2. What will be the computational complexity to solve WSN localization?

• 3. The deployment of WSN nodes will be usually done in random dense way. Therefore, proper computational complexity estimation of such random deployments has to be studied.

In this paper authors suggested possible solution to all the above mentioned problems. The unique localizability properties are addressed using the concepts of grounded graphs. In grounded graphs, every vertex will represent a WSN node and there will be an edge connecting two neighboring nodes if their distance is available (either by calculating using RSSI or by measuring between two anchor nodes). The WSN unique localization is achievable if and only if the constructed grounded graph is generically globally rigid (GGR). Following Checks validates that WSN is uniquely localizable:

• Grounded Graph must be 3-connected.

• Grounded Graphs must be redundantly rigid.

• In case of 2-connected GG 2-hop neighbors must be connected which can be done by doubling the communication radius of the WSN nodes.

To analyze the computational complexity of random deployment, the density of nodes is varied and average case approximation is done by making use of sub graphs that falls in to the category of trilateration graphs. By splitting the WSN graph into sub-graph of trilateration graph has the following advantages:

• It is uniquely localizable.

• Precise Localization of WSN nodes can be performed.

• The random WSN graph is trilateration graphs with specific level of node density and communication radius.

The authors deal about solving WSN localization problem in a generic way- which means the localization will not only be solved for given exact data, but also for little perturbed consistent data.

In [10], the computational complexity of WSN localization was analyzed. In this paper, the WSN localization problem is defined by the authors in the following way: in WSN n number of WSN nodes will be forming a network, which communicate with each other, with a communication radius of r, which is the distance used to estimate the positions of nodes. Therefore, localization is a process of estimating the position estimates of WSN nodes using the inter node communication radius. The communication radius r is considered to be as unit disk graph, because the unit disk graph sensing model of WSN [16] is considered. In the WSN few of the nodes are called anchor nodes, which have priory location information, and it assist in localization. The important problem addressed here is deciding localization problem using Unit Graph Reconstruction. In Unit Graph reconstruction the estimated edge lengths of the WSN nodes are used to realize the nodes physically as unit disk graphs. Here, points in $2-d$ must be found whose distance is the edge length of the nodes and must verify that the square of radius must be equal to square the edge length. It is proved that Unit Graph Reconstruction is NP-hard. In case of sparse graphs the WSN localization is a NP hard problem in the worst case. But, in case of high node density (dense graph) the localization problem is solvable. The authors concluded by posing the following important questions to be answered for efficient localization:

• 1. If there are few deviations in the measured distance can an efficient localization algorithm for sparse graphs be developed?

• 2. Localization problem accuracy varies with the node density, so can a minimal density of nodes be specified in order to solve the localization problem?

• 3. What will be the effect of communication range on localization?

• 4. How many anchor nodes have to be deployed for the precise location estimation?

3.2 Formal Analysis of WSN Localization Using Distance and Bearing Information

In [7], graphical properties of of uniquely localizable networks using both distance and bearing information is dealt in detail. Spanning tree used for distance and bearing information makes the computational complexity linear in this approach. The complexity turns to be of polynomial time if distance information is affected by noise. The bearing information is depicted in Fig. 3 and by referring to this bearing and heading is defined below.

Fig. 3

Depicts bearing information between $P_1$ and $P_2$

Definition 4

Bearing: the bearing information is nothing but the angle between x-axis in the local coordinate system of WSN node $P_1$ and the edge line joining $P_1$ and $P_2$ which represents the communication link between the two WSN nodes. The bearing information is measured in anti clockwise direction from the x-axis of the WSN nodes local coordinate system.

Definition 5

Heading: the heading information is the angle measured in anti-clockwise direction between x-axis of WSN nodes local coordinate system and the y-axis of the global coordinate system . Let us suppose that $\phi _1$ be the heading for the WSN node $P_1$. Now, the node $P_1$ has to pass its heading information $\phi _1$ and bearing information $\theta _{12}$ to its neighboring node $P_2$ so that it can compute its heading information. Upon receiving the heading information and bearing information from the WSN node $P_1$, the WSN node $P_2$ computes its heading information.

Based on the distance and bearing constraints following theorem were proved by the author:

Lemma 1

Distance and bearing constraints between two nodes $P_1$ and $P_2$ provides unique positions between them.

Lemma 2

The spanning tree used for distances and next for bearings, is a globally rigid set of $2|V|-2$ constraints.

Thus, in this in this literature it is proved that a network is uniquely localization if the associated graph is rigid both for distance and bearing constraints. The spanning tree generated reduces the computational complexity because it yields lesser number of communication links.

Table 3 Summary of literature indicating theoretical aspects of rigid graph localization in WSN

The literature dealing with formal analysis of rigid graphs based localization are summarized in Table 3.

Fig. 4

Depicts two rigid patches ABCD and BDCE merged and forming larger rigid patch ABCDE

4 Rigid Graph Localization: Methods and Algorithms

In this section we will discuss the different methods and associated algorithms used to localize the networks using rigid graphs.

4.1 Robust Quads Based Coordinate Stitching

In [11, 28], coordinate System Stitching based localization techniques were introduced. In this technique, the network graph is split into patches, where each patch will constitute a node and its associated neighbors. These patches are then mapped into its local coordinate system. Then these patches undergo rigid transformations, which make the points to be mapped into another coordinate system and are then merged, finally the whole WSN is localized to a global coordinate system. Figure 4 illustrates the process of merging of patches.

Fig. 5

The RobustQuad ABCD and the associated angles in the sub-triangles of RobustQuad

Moore et al. [20], introduced a distributed, linear time algorithm which will localize the WSN nodes; even if range measurement error exists. This distributed localization algorithm tends to localize those WSN nodes, which are in the region that satisfies the robust quadrilaterals property. The robust quad based localization is depicted in Fig. 5. Here, the starting nodes for map are the vertices of the robust quadrilateral. A robust quad contains four sub-triangles i.e. $\triangle ABC$, $\triangle ADC$, $\triangle ABD$, $\triangle BCD$ as shown in Fig. 5. The sub-triangles must satisfy following condition:

$$\begin{aligned} b\times \sin ^2\theta =d_{min} \end{aligned}$$

(1)

where b is the measured shortest length of the robust quad.

$\theta$ is the smallest angle.

$d_{min}$ is a predetermined constant based on average measurement error.

This distributed algorithm is designed such that: “it can localize those WSN nodes which estimates the distance to its neighbouring WSN nodes”. The only issue here is that the measured distance is not accurate because of the noisy environments where ranging techniques are used. They have made a cricket platform and demonstrated the algorithm in physical network. The graph realization problem over here is posed with following problems:

• Noisy distance measurements

• Lack of enough data values to compute the true positions of every WSN nodes.

• There is no use of anchor nodes which can be a base for starting localization algorithm.

• The amount of WSN nodes can scale to any amount, thus the algorithm must be scalable to any size of network.

4.2 Component Based Localization Algorithm (CALL)

For a WSN graph Ga component is set of nodes (vertices in terms of graph theory) that can have different realizations. The CALL algorithm is divided into following phases [21, 22]:

• Component generation In this phase, the WSN graph is divided into rigid components. At the end of this phase all nodes must belong to any of the one different components or must be an isolated node Initially, a triangle component will be formed and other nodes join this by trilateration, any number of nodes can join and make a big component but it must be globally rigid. A local coordinate system of the component will be formed accordingly as the nodes join the component. Once component is formed, it checks whether it can be realized. If it is not realizable then the component will merge with other components.

• Component merging In this phase non-realizable components can merge together to form a large component. The merger larger one must satisfy global rigidity condition.The local coordinate system of merged components must be This process is recursive and stops when all merging is over or when the component becomes realizable.

• Component realization The uniquely realizable components are mapped from local coordinate system to physical coordinates in this phase. All the components are merged and realized at once. WSN nodes pertaining to same component are localized together.

The CALL algorithm component generation phase with common edge is shown in Fig. 6.

Fig. 6

Component based: rigid components ABCD, ADEF, ABDE, AGHI, AEHI of the graph G is depicted here

4.3 Unique Anchor Free Localization (UAFL)

In [28] authors have developed an Unique Anchor free localization scheme for WSN. In this paper, the authors have used the concepts of rigid graph theory and combinatorial theory and applied it for WSN node localization. Both, the distance metric and the bearing metric are used to uniquely localize the WSN nodes. The range between two neighboring WSN nodes is estimated using the distance information and its associated direction in the plane is also found. The WSN localization problem here is defined as: “estimating the position coordinates using the distance and bearing information obtained from neighboring WSN nodes”. The authors have proposed an algorithm called Unique Anchor-Free Localization algorithm (UAFL) which has the following four processes:

• Node initialization In this phase every WSN node exchanges a beacon packet, which thereby determines its 1-hop neighbors. The beacon packet will be having information about the sender ID, sequence ID and neighbours of that node. Then the beacon will be lost for nodes more than 2-hop. All neighbors those obtain this beacon save the information of neighbour list and sender ID. Duplicate beacon checking is also done. Now, every neighboring node will estimate its distance and angle (using AOA). Finally, all the 1-hop neighbors will exchange their distance, angle and neighbor information with each other in order to compute positions of neighbors effectively.

• Local coordinate system In this phase all WSN nodes will get its relative coordinates by making itself as the origin of coordinate system and maintaining axes. For a WSN node i to to construct local coordinate system it should have minimum two 1-hop neighbors j and k such that they should not be collinear and the distance values between each nodes must be greater than zero and the distance values should be known to node?.

• Local position computation As represented in Fig. 7a, the Local Position Computation of a arbitrary WSN node i will be initiated by using the WSN nodes j and k which were in the process of making the local coordinate system of step 2. From Fig. 7b we can write following equations:

  $$\begin{aligned} j_x &= d_{ij},j_y=0 \end{aligned}$$

  (2)
  $$\begin{aligned} k_x &= d_{ik } \cdot cos\theta _k,k_y=d_{ik} \cdot sin\theta _k \end{aligned}$$

  (3)

  where $\theta _k$ is obtained by cosine law.

  $$\begin{aligned} \theta _k=arccos \frac{(d_{ik}^2+d_{ij}^2 )-d_{jk}^2)}{(2d_{ik} d_{ij})} \end{aligned}$$

  (4)

  To estimate the position of WSN node u wrt to WSN node i can be calculated as shown in Fig. 7b.

  $$\begin{aligned} u_x=d_{iu} \cdot cos\theta _u,u_y=d_{iu} \cdot sin\theta _u \end{aligned}$$

  (5)

• Global position computation The step 3 was estimating positions of a WSN node relative to its local coordinates, but when WSN network is setup as a whole we need to have a global position estimation. This can be done by using the sink node as a base for Global Position estimation. The sink node will have to first find its local coordinates and then estimate the position of its neighbors, which will be the final coordinates of those nodes. The global coordinates remaining WSN nodes, which are not neighbors of sink node by using a transformation matrix which will change the local coordinates of the WSN nodes to global coordinates w.r.t to the sink node.

  $$\begin{aligned} P_{final}=[T] \cdot P_{local} \end{aligned}$$

  (6)

  $P_{final}$ is the final global coordinates of the WSN node wrt sink.

  T is the transformation matrix.

  $P_{local}$ is the local coordinates as estimated in step 3.

Fig. 7

In (a) the local position computation with respect to xy-axis is shown. In (b) the position of node u with respect to nodei in xy-plane is shown

4.4 Iterative Localization

In this method an ordinary nodes first find its position based on its neighbor using trilateration or multilateration. Once it estimates its location then it will act as a anchor node to neighboring ordinary nodes and this process continues till all ordinary nodes get localized. In Fig. 8 where ordinary nodes are marked by small circles and anchor nodes by small rectangles; each of the ordinary node is iteratively localized with respect to the anchor nodes.

4.4.1 Sweeps

The “sweeps” algorithm is capable of localizing larger network without using trilateration or multilateration techniques [16]. “Sweeps” localization is applicable for sparse networks and in this technique two node positions are estimated as location estimate which is called as the candidate positions. It applies the bilateration technique to estimate the candidate positions, making use of two range estimates. The “sweeps” algorithm works as follows:

• In the beginning, set of three nodes are fixed nodes with known positions. Therefore, always there will be two set of nodes in sweeps algorithm i.e. set of localized and set un-localized. The localized set of WSN nodes are called as the swept nodes.

• The unlocalized WSN node measures distance to any two localized WSN nodes then it will estimate all possible candidate positions.

The amount of candidate positions will increase rapidly in case of simple “sweeps” algorithm. Therefore, it is minimized by using “shell sweeps” algorithm in which sweep is done by following a particular order, making use of breadth first search based sweep for minimum of two of those nodes which have distance information to the currently swept nodes. This ordering will reduce the number of candidate potions to be selected.

Fig. 8

Illustrates iterative based localization

4.5 Outlier Rejection Based Localization

The distance information which is used for localization might be severely erroneous due to these possible reasons [27]:

• Malfunctioning in the hardware: Hardware that effects RSSI are the transmitter, receiver and clock synchronization RSSI based distance will also be affected by the environmental factors like interference, reflection, noisy channel etc.

• Signals are also time varying due to the effect of temperature and humidity

• Outliers may also be generated by an adversary attack because location based applications are gaining importance.

In [24], authors dealt with the concepts of edge verifiability for solving the outliers. The edge verifiability is based on removing the redundant edges, comparing it with the ground truth distance in a WSN graph, but making sure that the edge removed graph is globally rigid. Finally all the edges of the Whole WSN graph is verified.

In [23], authors proposed the RobustLoc algorithm, an patch merging algorithm, which will be effectively discarding the outliers in sparse WSN. In earlier literature, if there were no redundant links during patch merging, then outliers were not rejected. But RobustLoc makes sure that even such links are removed. RobustLoc even identifies and removes outlier anchor nodes which might be infused by adversary.

The different localization methods and algorithms using rigid graphs are summarized in Table 4.

Table 4 Summary of literature indicating the algorithms and techniques of rigid graph localization in WSN

5 Performance Evaluation Parameter: Average Node Degree

The average node degree i.e the number of neighboring nodes link a WSN node is having is one of the prime parameter to estimate the running of WSN localization methods. This parameter is largely varying based on the WSN nodes deployment, which is either sparse or dense based on the application. Sparse deployments will have usually lower average node degree as compared to that of dense networks. The algorithm efficiency depends on $\mathcal {O}(\delta ^3)$ , where $\delta$ is the average node degree. Therefore, lesser the value of $\delta$ better is the efficiency of the algorithm. The localization algorithms developed using Rigid Graphs can be either centralized or distributed. Centralized algorithms provide accurate location estimates, but are having issues related to scalability, large amount of computational complexity due to number of message exchanges, and low reliability. Even though their average node degree is less it is not best suited because the number of message exchanges increases the complexity. Table 5 depicts the average node degree required by different rigid graph based localization algorithms based on their deployment and algorithm type. It can be observed from the Table 5 that sparse algorithms gets localized with smaller value of $\delta$, whereas dense networks need larger value of $\delta$.

Table 5 Average node degree of different rigid graph based localization methods

6 Conclusion

The theoretical aspects of unique WSN localization using the concepts of rigid graph theory is dealt in depth. The different conditions under which a WSN graph can be localized and the computational complexity of localizing large number of WSN nodes is found out. The ranging information distance is taken as a parameter to estimate the WSN nodes, and in some techniques both distance and bearing information is used to localize the WSN nodes. Some techniques also dealt with the erroneous distance caused due to the measurement noise which occurs in the ranging methods. To overcome the shortcomings of trilateration graphs which sometimes wrongly identifies localizable WSN nodes as unlocalizable WHEEL graphs, which falls into rigid graph category is proposed. To cope up with the varying network density Sweeps localization technique was introduced for localizing randomly deployed WSN nodes. Partially localizable networks is thoroughly analyzed using the edges in error length, which may lead to erroneous location estimates.