1.2.1 Measurement Stage

In this stage, the distance measured between different nodes is considered to be an important parameter, including angle measurement, and their own connectivity between them is considered. These techniques are classified into five main categories described as follows:

1. 1. Strength of the received signal.
2. 2. Arrival of the signal at a particular time or the difference in their arrival times.
3. 3. Angle of arrival.
4. 4. Proximity, based on the network connectivity.
5. 5. Picture/scene analysis.

Each category will be described in some detail.

Received Signal Strength Indication (RSSI): This is used basically to observe the received incoming signal. On the arrival of the received signal, the task of RSSI is to calculate the distance on the basis of the incoming signal. Distance calculations are performed, using the received signal strength of the incoming signal [13, 14].

In Eq. (1.1) and (1.2), P _trans and P _receive represent the transmitted power and the received power, respectively, and α represents the path loss coefficient. In this equation, d represents the distance between transmitter (Tx) and receiver (Rx) and is calculated using the received signal power. Only minimal hardware is needed to calculate the received signal strength, which is the main advantage of this method. But its limitation is that the measured values are going to change in the case of mobility, environmental conditions, path loss, or fading.

• ToA: It finds the distance and time at which the incoming signal is received, as the speed of propagation information is already available. Both the transmitter and the receiver end are synchronized and the start time of transmission is known. The parameter c (speed of the light) is known and distance calculation is done, based on the time of the incoming signal’s arrival at the receiver end [15, 16]. In this method, synchronization must be required between the transmitter and the receiver clocks for accuracy, which leads to additional hardware requirements at both units, and increases complexity. Fig. 1.1 illustrates the concept of ToA.
• TDoA: In this scheme, the medium used for transmission gives a different speed. As shown in Fig. 1.2, the radio and the ultrasound signals are transmitted from the transmitter end. The arrival of any signal at the receiver end is used to measure the arrival of the other signal. The distance is calculated based on the arrival time of these two transmitted signals. This method provides accuracy under line of sight (LOS) conditions but, if certain disturbances occur in the environmental conditions, it leads to the failure of LOS conditions. Also, with the change in environmental conditions, these arrival times are going to vary from their actual values which leads to incorrect distance measurements.
• Angle of Arrival (AoA): The distance calculation between the anchor and the target nodes is also calculated using the Angle of Arrival method. In this method, an angle is made between the two lines, where the first line connects the transmitting and receiving ends and second line is between the receiver and the other direction, taken as a reference, as shown in Fig. 1.3. The distance measured through this technique is more accurate than the distance calculated using the RSSI method mentioned above [17].
• Proximity: This is the simplest and cheapest method available for calculating the distance between the nodes because it measures distances only between those nodes which are inter-connected and within range. The hardware configuration required is simplest under this scheme [18].
• Picture Analysis: This technique behaves in a different manner from the above-mentioned techniques. In this, the distance calculations are carried out using a picture or on the basis of scene analysis. In this technique, additional hardware is required which leads to complexity and is the main drawback of this technique.

1.2.2 Computational Stage

In the second, computational stage, the estimations done on determining the distance and angles in the previous stage are collated for calculating the positions of the unknown nodes. These methods, which work on computational analysis, are discussed as follows.

• Trilateration: In this scheme the estimated coordinates of the target node is determined with the help of three anchor nodes, and the location of the tracking nodes is calculated [19]. As shown in Fig. 1.4, the determination of the target nodes coordinates is obtained from the coincidence of consecutive circles. In the case of determining the 2-D coordinates, at least three anchor nodes are required.
• Triangulation: Geometrically, the triangulation technique is used to obtain the information of 2-D coordinates on the basis of angles calculated between the nodes and the reference points. By using mathematical sine and cosine rules, the position of the target nodes can be calculated [20]. Fig. 1.5 shows this technique.
• Multilateration: In the trilateration approach, the calculated distance is not perfect because the joining of the three circles does not correspond to a single point. In order to cope with this limitation, at least three anchor nodes are required, a process termed multilateration [21]. The results of this technique are much more efficient than those from trilateration. Fig. 1.6 represents this concept.

Three anchor nodes are assumed with their known position, i.e., (x _i, y _i) for i = 1,2,3 and the unknown position of the target nodes (x _t, y _t) is calculated by using the equation as given:

where d _i,t represents the distance between the target nodes and the anchor nodes.

1.3.1 Localization Based on Hop Counts

In single-hop localizations, the unknown nodes, called target nodes, are localized in that they are only one hop away from the known positions of the anchor nodes, whereas, in the case of multiple hop schemes, the unknown nodes and the known anchor nodes are more than one hop count apart; multiple hop counts are those which connect the two nodes. The methods used for single-hop counts are Angle of Arrival, Time of Arrival, Time Difference of Arrival, and Received Signal Strength Indicator, whereas the multi-hop method covers Distance Vector Hopping scheme, Approximation of Points Residing in the Triangles, and Multidimensional Scaling. Fig. 1.8 represents this concept. In these methods, additional numbers of anchor nodes are required, which is the major drawback [22 –25].

A matrix, symmetric in nature, is applied as an input to the multi-hop WSN localization method. In this, hop counts on the basis of distance between the nodes are calculated and used. The techniques used under this scheme are referred to as range-based and range-free localizations.

1.3.2 Localization Based on Range-based and Range-free Techniques

Localization algorithms are divided into two categories, namely range-based and range-free techniques. In range-based localization techniques, the anchor node’s range information is required, but, in the second method, information relevant to range is not required. By using some specialized hardware, the distances between the nodes is calculated precisely. The main issue arising from this technique is accuracy degradation taking place in case of mobility scenario and of various noises taking place in the environment.

A network formation in the case of the range-free technique is that in which the hop count is directly proportional to the distance between them. In case of range-free techniques, the coordinates are calculated on the basis of radio connectivity information among their available neighboring nodes. This technique is more efficient, in terms of simplicity and cost- effectiveness, than the range-based localization techniques. Several approaches related to range-free techniques are given below [26, 27].

1. 1. Based on the Centroid method: This method was developed by Blusu et al. [28]. In this algorithm, at least three anchor nodes are required in order to locate the position of the unknown node, which are in its neighborhood position. Eq. (1.4) represents the method of calculating the centroid, where $x_1+x_2+\cdots x_N$ and $y_1+y_2+\cdots y_N$ represent the x and y coordinates of the anchor nodes and x _est, y _est represents the estimated positions of the unknown node, referred to as the target node.

2. $$x_{\text{est}},y_{\text{est}}=\frac{x_1+x_2+\cdots x_N}{N}+\frac{y_1+y_2+\cdots y_N}{N}$$

   (1.4)

3. 2. DV-Hop method: In the DV-Hop method, the hop count between two anchor nodes is calculated and, from this information obtained, the length of each hop is calculated. The information gathered by every anchor node is floated or shared into the sensing field area. This information will help locate the target nodes by estimating the multi-hop range [26, 29, 30].
4. 3. Approximating Point in Triangular method (APIT): In this technique, the area under investigation is segregated into triangular regions. A node lying near or far from the triangular region resides in the corresponding triangle by narrowing down its area [11].
5. 4. Multi-dimensional scaling (MDS): In this method, again on the basis of distance, all nodes will maintain a distance matrix. After estimating the distance matrix, Dijkstra’s algorithm for finding the shortest path is used to design a complete matrix. When the observation accuracy of a sensor becomes worse, this technique is not efficient during that time, then a hybrid technique, in which this method is used in combination with trilateration, can provide the efficient results [31].

1.3.3 Localization Based on Anchor-based and Anchor-free Techniques

These are the two techniques available on which the location of unknown nodes is relied upon. In the first (anchor-based) method, the information on the anchor node is required in order to calculate the coordinates of the unknown node; in the case of anchor-free techniques, no such information about the anchor is required. In the deployment stage the position of a few nodes, known as anchor nodes, are known, as they include a GPS feature, whereas, in the case of the anchor-free method, localization is achieved, using the information of the relative coordinates [32, 33]. The main motive behind the use of anchor-based method is the calculation of the distance from the unknown nodes to the known nodes; after the calculation on this basis is carried out between them, then, by using localization algorithms, the unknown node determines its coordinates in space, as, for determining 2-D coordinates, at least three anchor nodes are required and, for determining 3-D coordinates, four anchor nodes at least are required.

In cases where no anchor node is available, there are two important steps to be followed for determining or localizing the unknown nodes.

By the use of different localization methods available, every node in the sensing field computes the distance between them and their neighboring nodes.

Then, on the basis of distance, every node in the sensing field determines its coordinates itself.

1.3.4 Centralized and Distributed Localization

A central processor is responsible for computing all the computations by the centralized method, but, in the latter method, the computations are performed using the inner sensor measurements. The main advantage of using the centralized method is that each node does not need to perform the computations. The major drawback of using this technique is that all the nodes send their data back to the base station. Simulated annealing and RSSI-based localization come under the classification of centralized localization algorithms. These algorithms are better in terms of localization accuracy because complete information about the connectivity and distance is available between the deployed sensor nodes and their neighbors [34].

In the case of distributed localization algorithms, the sensors deployed in the field compute the required information in terms of either connectivity or distance on an individual basis. In this method, each node communicates with them or with their neighbors, in order to determine their own position in the network. Beacon-based, coordinate system-based and hybrid localizations are some of the examples of distributed localization algorithms. In this method, many iterations are required to achieve stability, resulting in the technique being a little slow, which leads to a drawback of this method [35].

1.3.5 Static and Dynamic Localization

In the static algorithms, once the nodes are deployed in the region of interest, they will not move; the dynamic method nodes deployed in the sensing field have some mobility and will move accordingly [36 –38]. In static algorithms, the coordinates of unknown nodes are determined during the set-up of static WSNs. But in the case of the dynamic method, a continuous tracking of sensor nodes is required as they are moving and changing their coordinate values. A little extra time is required to determine the coordinates of the moving nodes; for tracking the position of moving nodes, a fast localization feature is required, using this procedure. In the case of static algorithms, the convergence rate is fast. There are many range-based techniques available, like approximate point in triangulation and lateration, multilateration, and the modified centroid method, which are some of the static localization techniques.

It is very difficult to track the location of moving target nodes because it has to be determined periodically. There are various techniques available in the literature, of which the Kalman filter is one which works well in noisy environments. Road navigation in the absence of GPS features is a property of Kalman Filters [39, 40]. In order to predict the system’s future states, the Kalman filter is one of the useful techniques.

These issues are described in the following section.

1.4.1 Energy of the node

The sensor nodes deployed in the sensing field in the area of WSNs have non-replaceable and limited-energy battery units for performing the operations, such as sensing and reporting. The whole system becomes worse if special care is not taken with regard to battery units. A lot of research has been conducted in order to improve the energy of the node [41].

1.4.2 Node Mobility

In order to maintain the node’s connectivity in the mobility scenario is quite a challenging task in localization. In the case of static WSNs, the node, once estimated, is not going to change its position as it is fixed, but, in the case of dynamic WSNs, the nodes periodically shift from one position to another position, and the deployed sensor node has to determine and estimate the position periodically [36, 38]. So, localization is becoming a major source of interest amongst researchers.

1.4.3 Transmission Range of Node

In most of the localization techniques, a beacon signal is required for determining the locations of unknown nodes. Beacon nodes are equipped with a GPS feature which helps these nodes to be placed at a position with known coordinates, and, with this feature, one can obtain a proper connectivity in between the beacon and the target nodes. So, the transmission range of a node plays a key role in estimating the locations of unknown nodes.

1.4.4 Localization Security

As in WSNs, most of the times this set-up is installed in unfriendly locations. Some of the problems that occur in localization are overshadowing and distance away from attack [42]. So, researchers are showing interest in improving the security of localization.

1.4.5 Localization Accuracy

Accuracy is determined by calculating the difference between the actual and the estimated position of the sensor node. It is a difficult task to obtain the accurate location of the sensor node by applying localization algorithms. So, by using available or new localization algorithms, it is possible to obtain optimum results [43, 44].

1.4.6 Multi-Dimensional Localization

Basically, in order to obtain the coordinates of unknown nodes (target nodes), localization algorithms are used. Some of the applications require knowledge of 2D and 3D coordinates [36].

1.5.1 Determination of 2-D Coordinates

Bulusu et al. [28], in their research, investigated localization in outdoor conditions without using GPS features. They used the centroid method for calculating the coordinates of the unknown nodes. Lee et al. [45] represented their work on localization by using very few anchors in the field. Their work presented and claimed a higher accuracy in estimating the distance by finding the shortest path. Awad et al. [46] presented two ways for estimating the distance; the first way was to use the available statistical methods and the other one was to use the concepts of neural networks for computing the distance. Their conclusions were based on the parameters which degrade the quality of distance measurements, such as transmitted power, RF frequencies, mobility of nodes, and localization algorithms. Savvides et al. [47], in their work, discussed the use of the multilateration technique. The authors presented a distributive approach in that sensor nodes were collectively going to solve an optimization problem, which a single sensor could not solve. Three state problems are discussed in this paper. In state-1, a combined approach was taken, the second state represents the computation of starting estimates, and, in the final state, again, reframing of positions was carried out. Savvides et al. [48] presented an approach to localizing sensors in a temporary network that allows the deployed sensors in the field to find their locations using distributive methods. Although location estimates are more accurate by using centralized methods, by using a distributive approach, the system is more robust and will result in an effective distribution of power consumption in the network. Sumathi and Srinivasan [49] used the least squares method for estimating the locations of static target nodes by the use of single anchor nodes, on the basis of RSSI measurements.

Guo et al. [50] presented a different approach in which there is no relation or mapping of estimating distances based on RSSI values, using the method named as the Perpendicular Intersection method. Using this geometric relationship, the positions of the nodes are computed. Kim and Lee [51] presented a localization technique that is range based and in which the movement of the mobile anchor node is based on some strategy, known as MBAL (Mobile Beacon-Assisted Localization). Their scheme provided the best selection of the path, with fewer complexities.

In their conclusions, Karim et al. [52] discussed the range-free techniques that are efficient in terms of energy with the use of fewer anchor nodes. They claimed that their technique is less complex and more accurate by using very few anchor nodes. Li et al. [53] proposed a method that provides efficient and robust localization in real-time scenarios. The techniques used are named the Breadth-First (BRF) and Backtracking Greedy (BTG) algorithms. Chen et al. [54] presented an approach that is classified under the range-free methods. Their work stated that their scheme is simple and practical, in which a comparison among the nodes is based on RSSI values and this consumes much less energy and shows great accuracy, while using the concepts of mobile anchors. Khelifi et al. [55] proposed two different localization algorithms, namely time-driven and event-driven for mobile WSNs. Stone and Camp [56] discussed the localization algorithms that use the information of anchors, and computed the performance and accuracy of localization relative to anchor mobility and target nodes. There is much more research which we have not mentioned, and conclusions are available in the literature [57 –63].

1.5.2 Determination of 3-D Coordinates

Shi et al. [64] presented Ultra-Wide Band, a Time of Arrival method determining the 3-D coordinates required for localization. They discussed that distance calculation, using their technique between the anchor node and the unknown node, can be more precise than other techniques. Wang et al. [65] presented a scheme based on the Distance Vector hopping algorithm, that can localize 3-D coordinates of a sensor node more precisely and effectively, but its complexity and huge deployment cost are its major limitations. Xu et al. [66] discussed a hybrid method by using Distance Vector hopping combined with the Newton method for optimization. The authors considered two parameters, one of which is coverage and the other accuracy, for their proposed algorithm. Li et al. [67] developed a model for determining 3-D coordinates in a WSN environment on the basis of the RSSI model. They proposed a model for obtaining relevance between the Degree of Irregularity and variation in the ranges of the transmitted signal. Ahmad et al. [68] developed an algorithm for the determination of 3-D coordinates, using a parametric method. In their algorithm, very few anchor nodes are available for localization and will provide better results because the network is shrinking towards a common point known as the central point. Zhang et al. [69] proposed a localization algorithm that depended upon an expensive beacon signal. MDS-MAP, DVHOP, and the Centroid method are methods modified from 2-D coordinates to 3-D coordinates, which are available in the literature [71 –75]. In obtaining the 3-D coordinates in applications deployed in an underwater network [76], Cheng et al. [77], and Zhou et al. [78] surveyed this application. In these methods, localization is achieved using information based on connectivity and the number of anchors. Tomic et al. [79] presented a hybrid method in developing 3-D WSNs. In this scheme, an estimate on the basis of least squares criterion is used. Chan et al. [80] proposed a method for solving a problem based on transmission power as some 3-D localization methods require specific directional information, by implementing a directional antenna on anchor nodes [81, 82].

1.6.1 Services Based on Location

Through mobile networks and/or the internet, the information about the location is provided to end users. Applications based on navigational services can provide the connectivity to link the position of the mobile user, with geographical locations tracked by mobile users. These services are essential in both indoor and outdoor environments. These types of services are required for guiding the users to a particular area of interest. Also, they are used in a public place, e.g., in railway stations or bus stations, to direct the passengers to a particular desired place.

1.6.2 Health and Smart Living Applications

Localization in the indoor environments plays a great role for these types of applications. These types of applications are helpful for determining and monitoring the health of elderly people [83].

1.6.3 Robotics

Robotics is one of the important applications in the field of localization. There is much research going on for the development of these types of applications. The cooperation between the installed robots in the field is required for certain applications like surveillance and for the tracking of other unknown areas [84].

1.6.4 Cellular Technology

Many challenges and issues about the accurate determination of location are determined by cellular technology [85], as the growth in the mobile generation leads to an improvement in the accuracy.

1.7.1 Features of Optimization Techniques

The features of optimization techniques are listed below.

1.7.2 Genetic Algorithms (GA)

This is a technique based on search and optimization and is used for finding the estimated results. It begins its search with random solutions and these solutions are assigned a fitness function that is relative to their objective function. Then, a set of new populations is formed by using three genetic operators, named as reproduction, cross-over and mutation [86]. An iterative operation in GA takes place using all three operators until a terminated criterion is not reached. For decades, GA has been used in a wide variety of applications, because of its simplicity. The basic flow of genetic algorithms is given in Fig. 1.10.

1.7.3 Particle Swarm Optimization (PSO)

A technique developed by Kennedy and Eberhart is known as PSO [87], based on the behavior of birds. It is an efficient algorithm and its implementation stage is easier. A random number of particles is deployed in the search space and the objective function is calculated accordingly. Then, the movement is applied to the particles deployed in the search space [88]. A particle moving in the search space collects ‘pbest’ and ‘gbest’ positions in the space. The idea is illustrated in Fig. 1.11.

1.7.4 Biogeography Based Optimization (BBO)

In BBO, the term HIS (Habitat Suitability Index) represents the fitness function. The higher the value of HIS, the better the place is for the species to live, whereas lower HIS values indicate an inappropriate place for the species to live. The basic idea about the BBO algorithm is shown in Fig. 1.12.

1.7.5 Firefly Algorithm

The firefly algorithm was proposed by Yang [89]. The behavior of fireflies is used in this algorithm and the rules followed by the fireflies are as follows:

1. All fireflies are unisex as they move from one place to another notwithstanding of sex [90].
2. The parameter which attracts the fireflies towards each other is attractiveness, which is directly proportional to the glowing nature of the fireflies, and, as they move a certain distance apart, their brightness is reduced. So, fireflies will not follow each other in that particular case. If there is no brighter firefly found, then this event is random in nature. The fitness function in this case is represented by the glowing nature of fireflies. Then, according to these rules, the firefly algorithm is represented in Fig. 1.13.

According to the Free Lunch theory, no single algorithm is best-suited to each optimization problem. There are many more types of optimization algorithms that are reported in the literature, which can be applied to localization problems to check their performance.

1.8.1 Parameter Calculations on the Basis of Accuracy

The accuracy term is used to match the positions of the actual and the estimated target nodes. The difference between the two positions leads to errors and these errors are named the Mean Absolute Error and the Root Mean Square Error.

Mean Absolute Error (MAE): MAE is basically calculated with respect to the continuous variables and it is an important parameter for finding out the accuracy of a localization algorithm used in a specified application. The equation for MAE is Eq. (1.5), where (x _t, y _t, z _t) is the current position, (x _e, y _e, z _e) is the calculated position, and N _t represents the total number of sensor nodes deployed.

Root Mean Square Error (RMSE): This parameter also represents a measure of accuracy and is given by Eq. (1.6),

1.8.2 Evaluation on the basis of cost metrics

In almost every application, cost factor determination plays an important role. In the context of localization, the parameters which contribute to the cost are power consumed during the set-up stage, how many anchor nodes are required for this process, and the total time required to localize all the nodes in the network. If lifetime enhancement of the network is important at the same time, cost management also plays an equal role. There is a trade-off between these two. The ratio of known positions of the anchor nodes to the unknown positions, power consumed, and time taken by the localization algorithm to localize all the nodes play important roles in determining cost metrics.

• Anchor to Target Ratio: In terms of cost metrics, anchor nodes are the ones which are deployed in the sensing field with GPS features enabled in them. In order to save the cost, we need to install only a few anchor nodes in the field as they are expensive, and, in order to localize the target nodes, this terminology is used. It is defined as the number of anchor nodes required to localize the target nodes.
• Overhead during Communication: As the number of sensor nodes deployed in the sensor field increases, the communication overhead also increases to a greater extent. The overhead can be calculated by finding out the total number of packets sent.
• Convergence Time: The time taken by the localization algorithm to collect all the information regarding localizing all the nodes present in the network represents the convergence time. As the network size increases, this parameter is affected.
• Algorithmic Complexity: Algorithmic complexity is always defined with some standard notions (O), where the higher the order, like O(n ³) and O(n ²), the longer time it will take to converge, with this parameter representing the complexity.
• Power Consumed: This parameter is important in terms of cost as it calculates the power consumed in a localization process.