Localization Context-Aware Models for Wireless Sensor Network

Abstract

Wireless sensor networks (WSNs) are emerging as the key technology to support the Internet of Things (IoT) and smart objects. Small devices with low energy consumption and limited computing resources have wide use in many applications and different fields. Nodes are deployed randomly without a priori knowledge of their location. However, location context is a fundamental feature necessary to provide a context-aware framework to information gathered from sensors in many services such as intrusion detection, surveillance, geographic routing/forwarding, and coverage area management. Nevertheless, only a little number of nodes called anchors are equipped with localization components, such as Global Positioning System (GPS) chips. Worse still, when sensors are deployed in an indoor environment, GPS serves no purpose. This chapter surveys a variety of state-of-the-art existing localization techniques and compares their characteristics by detailing their applications, strengths, and challenges. The specificities and enhancements of the most popular and effective techniques are as well reported. Besides, current research directions in localization are discussed.

1. Introduction

The popularity of wireless sensor networks (WSNs) is taking advantages of advances in wireless communication and digital electronics [1]. WSN have become an important and interesting subject of research. It is composed of small devices equipped with a microcontroller, a low-power radio, and a number of sensors to observe the environment. The Internet of Things (IoT) is defined as “Simply, the Internet of Things is made up of devices – from simple sensors to smartphones and wearables connected together,” Matthew Evans, the IoT program head at techUk, says [2]. Hence, localization-based services are the most important issues related to the IoT.

Smart environments constitute an evolutionary development step in many applications and fields, such as tracking, environmental monitoring, disaster management, climate control, health care, human monitoring, and underground mining. Node localization is essential to provide a physical context to sensor readings for services such as intrusion detection, surveillance, geographic routing, and coverage area management [3].

Localization, also known as positioning problem, is a one-time detection technique, where the position or the location of the unknown sensor is estimated. The closeness of the estimated location to the real value presents the accuracy of the technique, and the consistency of the estimated location presents the precision of the technique. However, a sensor location can be global or relative. A global position is provided by a global reference such as the Global Positioning System (GPS) or the Universal Transverse Mercator (UTM) coordinate system. On the other hand, relative position is based on an arbitrary coordinate system, for instance, a sensor’s location is obtained as distances to other sensors. Tracking is an on-time method where the trajectory of an unknown sensor is estimated in real-time applications [4], also known as connectivity, which indicates whether two sensors can communicate between them through one hop, that is, a packet transmitted by one sensor can be received by the other sensor. Reference nodes, also known as anchor nodes, are aware of their positions in the network, they are used by unknown nodes in the localization process. Techniques based on anchors are anchor-based, the estimated positions are global metrics, otherwise, the technique is anchor-free. Localization techniques based on measurements such as distances or angles between sensors are called range-based techniques, as opposed to the range-free techniques [3]. This chapter will discuss all these different techniques as well as their concepts, drawbacks, and advantages, as well as presenting briefly localization applications.

2. Global positioning system localization

The GPS is one of the well-known and used among global navigation satellite systems (GNSS). Owned and operated by the U.S. government, GPS provides global coverage. Using this system and with respect to a reference in time and space, users estimate accurately and in real time their three-dimensional (3D) position, velocity, and time [5]. It consists of at least 24 satellites, arranged in six orbital planes with four satellites per plane, orbiting the earth at altitudes of approximately 11,000 miles. An unlimited number of users can be positioned by GPS, by using the concept of a one-way time of arrival (TOA) ranging. The distribution of satellites ensures that at least eight satellites can be seen simultaneously from almost anywhere on the planet. Each satellite broadcasts waves containing information on its identity, its location, and the date and time the signal has been sent. These waves propagate at the known speed of light. The GPS receiver receives the information transmitted by the satellites and determines the time difference between the code generation time and the reception time. Then, the distance separating the satellite to the receiver can be calculated by a simple relation between speed and time $\left(\text{distance}=\text{speed}\times \text{time}\right).$Using this distance, the receiver is said to be located on a sphere centered on the satellite with a radius equal to the computed distance. This process is repeated with two more satellites, then the position of the receiver is estimated as the intersection of three spheres [3].

However, in WSNs fully GPS-based solution is impractical, since not each sensor can have its own GPS receiver. This is due to many constraints such as cost, high-power consumption, and the need for line-of-sight between GPS and satellites. Also, GPS performance will deteriorate considerably when deployed in hostile or very severe environments [5]. In addition, if indoor scenarios are considered, the GPS signal will become even worse and therefore unreliable for location. To locate nodes in networks of mobile sensors in larger and/or mobile networks, various techniques and localization algorithms have been proposed.

3. Localization context-aware applications

The increasingly reduced size of sensors, their low cost, the wide range of types of available sensors, as well as the wireless communication medium used allow WSN to quickly invade several fields of application. The diversity of applications is remarkable, among the fields where they can offer the best contributions, we can cite the following fields: military, environmental, health, security, underground mining, etc.

3.1 Military application

WSN can rapidly be deployed and used for military applications such as battlefield surveillance, combat monitoring, and intruder detection [6]. The main advantage of using WSN is their capacity to be spontaneously positioned since the terrain of the battlefield is variable [6]. In addition, enemy location can be expected to use WSN in combat monitoring, which is the most critical information to detect intruders [3].

3.2 Health application

Using WSN in the healthcare domain allows providing real-time positioning of patients (patients with Parkinson’s disease, epilepsy, patients with heart disease, and the elderly) in a hospital or their homes by using wearable hardware for example [7].

3.3 Environmental application

Air monitoring, water monitoring, and emergency alerts are subcategories of environmental applications. An important aspect is proactive monitoring of common disastrous causes in real time to lower or prevent damage [6]. For example, the integration of sensors in the walls promotes the detection of alterations in the structure of a building following an earthquake or aging, and the monitoring of movements in order to constitute a system of detection of distributed intrusions.

3.4 Underground mining application

The underground mining environment is one of the most dangerous working environments. Many accidents occur in mines causing death and loss of several people, and this is due to a lack of surveillance and detection of danger. WSNs make working conditions easier and safer, and also facilitate rescue operations. In fact, sensors are deployed to locate people in normal or abnormal situations such as accidents. Moreover, sensors can be used to locate holes that cause collapses [3]. However, the mining environment is hostile for radio communications, which cause several challenges during the deployment of the WSNs in underground mines; also, the signals reach the destination after having undergone several physical phenomena, such as reflection, refraction, and dispersion. Besides, due to the high percentage of relative humidity, signal absorption and attenuation are extremely high. Therefore, the deployment of WSNs in an underground mine must take into account a compromise between the contradictory requirements [3].

4. System model

Consider a WSN with $N$nodes randomly deployed. Each node $i,i\in \left\{1,2,\dots ,N\right\}$is characterized by its physical position $p_i$given by:

$$p_i=\left\{\begin{array}{c}\left[x_i\right]\left(1\mathrm{D}\right)\\ {\left[x_i,y_i\right]}^T\left(2\mathrm{D}\right)\\ {\left[x_i,y_i,z_i\right]}^T\left(3\mathrm{D}\right)\end{array}\right.i=\left\{1,2,\dots ,N\right\}$$E1

The purpose of the localization is to compute the unknown vector $p_i$. A WSN can be modeled as a graph $G$:

$$\begin{array}{c}G=\left(V,E\right)\end{array}$$E2

where $V=\left\{1,2,\dots ,N\right\}$is a set of vertexes that contains an element for each node, while the set $E$contains an edge $\left\{i,j\right\}$, where $i$and $j$are neighbors, that is, they can exchange radio messages within one hop [8]. Hence, the localization problem is analog to the problem of embedding a graph in a Euclidean space, and that by finding a mapping function $f$such that:

$$\begin{array}{c}f:V\to {\mathbb{R}}^d\end{array}$$E3

This function uses constraints derived from the edge to assign each vertex to a position in ${\mathbb{R}}^d$, with $d$the dimensionality of the embedding space [8].

4.1 Embedding with known edge lengths

Measurements $m_{\mathit{ij}}$are available and are estimates of the distance between two nodes $i$and $j,$when some of the inter-node distances are known. Thus, the embedding problem searches a mapping f compatible with the obtained data:

$$\begin{array}{c}‖f\left(i\right)-f\left(j\right)‖=m_{\mathit{ij}},\forall \left\{i,j\right\}\in E\end{array}$$E4

where $‖.‖$denotes the Euclidean norm. This approach is used in case of range-based techniques.

4.2 Embedding using connectivity information

A different approach is used by range-free schemes that only rely on connectivity information. The model of a network with connectivity constraints can be represented as an idealized wireless network, where two nodes are neighbors if and only if their distance is less than the communication range R of nodes.

5. Range-based localization

Range-based schemes are derived from distance and angle estimation techniques. They use the distance/angle between sensors to estimate the location. The technique accuracy depends on the quality of signal measurements. However, range-free techniques are based on the connectivity to estimate the position of a sensor relative to other sensor nodes. Range-free techniques are cost-effective solutions; however, the accuracy is lower than the accuracy of range-based techniques.

5.1 Ranging techniques

Information on distances or angles can be obtained using many techniques, such as the received signal strength (RSS) [9, 10], the ToA [11, 12], the time difference of arrival (TDoA) [13, 14], and the angle of arrival (AoA) [15, 16]. Range-based techniques have a high accuracy range compared to range-free techniques. However, they require additional hardware making them expensive for large systems. Table 1 summarizes some range-based algorithms as well as their pros and cons.

Method	Pros	Cons
AHLoS	Acceptable accuracy in small-scale networks.	Poor accuracy in large-scale networks
TPS	Independent TDoA measurements required.	Powerful anchors required (may not be valid in WSN).
MAL	Simple computation. No additional distance measurements required.	Large latency in large networks.

Table 1.

Range-based algorithms.

5.1.1 Time of arrival

Also called time of flight, ToA is a timing-based technique that depends on accurate measurements of transmitting and receiving time of signals between two nodes. Based on the known speed of the signal (acoustic signal travels at a velocity of 343 m/s and radio signal at a velocity of 300 km/s) and on propagation time obtained from these measurements, the distance separating these nodes is calculated [1]. ToA requires highly accurate synchronization of the clocks of the sender and receiver at the microsecond level. All signals transmitted must incorporate a timestamp to accurately estimate the distance traveled. There exist two types of ToA techniques [3]. The one-way ToA method measures the difference between the sending time and the signal arrival time. It requires highly accurate synchronization of the clocks of the sender and receiver (Figure 1a). The distance between two nodes i and j can be calculated as:

Figure 1.

Ranging techniques: (a) one-way ToA, (b) two-ways ToA, (c) TDoA, and (d) AoA.

$$\begin{array}{c}{d}_{\mathit{ij}}=\tau \times v\end{array}$$E5

where $\tau =t_2-t_1$, $t_1$and $t_2$are the sending and receiving times of the signal respectively, and $v$is the signal velocity.

The two-way ToA method is preferred, where the round-trip time of a signal is measured at the sender device (Figure 1b). The distance is calculated as:

$$\begin{array}{c}{d}_{\mathit{ij}}=\frac{{\tau }_1-{\tau }_2}{2}\times v\end{array}$$E6

With ${\tau }_1=t_4-t_1$and ${\tau }_2=t_3-t_2$, $t_3$and $t_4$are the sending and receive times of the response signal, respectively. ToA techniques require very accurate hardware to measure the actual received time of the signal by the nodes. Since the propagation velocity of RF signals is high, any small error in the time measurement results in a large distance estimate error. Thus, ToA techniques are not practical for traditional WSNs [1, 3].

5.1.2 Time difference of arrival

TDoA technique is also a timing-based technique that uses two separate signals traveling with different velocities (like radio/ultrasound or radio/acoustic). The difference between their receive times can be used to estimate the distance between nodes. This approach defines a hyperbolic area where a target is possibly located with two paired sensors as foci [17]. Each node is equipped with a microphone and a speaker. The transmitter (anchor node) sends a radio message and waits some fixed interval of time $t_{\text{delay}}$.

Then, it produces a fixed pattern of “chirps” on its speaker. When a node receives the radio signal, it notes the current time ($t_{\text{radio}}$) and turn on its microphone. When this latter detects the chirp, the node notes again the current time ($t_{\text{acoustic}}$) (Figure 1c). Knowing $t_{\text{radio}}$, $t_{\text{delay}}$, and $t_{\text{acoustic}}$and given that radio waves (with velocity $v_{\text{radio}}$) travel faster than sound in air (with velocity $v_{\text{acoustic}}$), distance $d_{\mathit{ij}}$between two nodes can be calculated as in [18] by Eq. (7).

$$\begin{array}{c}{d}_{\mathit{ij}}=\left(v_{\text{radio}}-v_{\text{acoustic}}\right)\left(t_{\text{acoustique}}-t_{\text{radio}}-t_{\text{delay}}\right)\end{array}$$E7

TDoA based approaches do not require synchronization between the clocks of the sender and the receiver. However, it needs additional hardware (i.e., microphone, speaker, etc.) [1, 3].

5.1.3 Angle of arrival

The direction of the received signal can also be used for localization. The AoA is defined as the angle between the propagation direction and some reference direction known as orientation (Figure 1d) [19]. Data is collected using radio or microphone arrays. The AoA of the signal $\left({\alpha }_i\right)$is calculated by studying the time difference or the phase between the signal’s arrivals at different microphones. The relationship between coordinates of an unlocalized sensor $\left(x,y\right)$, anchors’ coordinates $\left(x_i,y_i\right),\left(i=1,2,\dots ,n\right)$and angles of arrival ${\alpha }_i$can be expressed by Eq. (8).

$$\begin{array}{c}{d}_{\mathit{ij}}=\left(v_{\text{radio}}-v_{\text{acoustic}}\right)\left(t_{\text{acoustic}}-t_{\text{radio}}-t_{\mathrm{d}\acute{\mathrm{e}}\mathrm{lai}}\right).\end{array}$$E8

Knowing the angles of arrival from two or more anchors, sensor’s location can be estimated using a standard least-squares approach.

$$\begin{array}{c}\mathit{AX}=b,X=\left[\begin{array}{c}x\\ y\end{array}\right].\end{array}$$E9

$$\begin{array}{c}A=\left(\begin{array}{cc}1& -tan{\alpha }_1\\ 1& -tan{\alpha }_2\\ ⋮& ⋮\\ 1& -tan{\alpha }_n\end{array}\right)b=\left(\begin{array}{c}{x}_1-y_{1}tan{\alpha }_1\\ x_2-y_{2}tan{\alpha }_2\\ ⋮\\ x_n-y_{n}tan{\alpha }_n\end{array}\right)\end{array}$$E10

Hence, estimated location, $\widehat{X}$is calculated by:

$$\begin{array}{c}\widehat{X}={\left(A^{T}A\right)}^{-1}{A}^{T}b\end{array}$$E11

Depending on the measurements, AoA techniques, directionally based techniques, provide high localization accuracy. Nevertheless, higher complexity antenna arrays are essential for measurement, increasing thus the cost of WSN. Moreover, to offer spatial diversity and to measure accurately the AoA, a space is required; however, it may not be possible in WSN, considering the size of sensor nodes. Besides, these techniques suffer from multipath and scattering as well as NLoS conditions.

5.1.4 Received signal strength indicator

The most used range-based technique is based on RSS measurements. Each node is equipped with a radio. Based on theoretical or empirical models, the distance between two nodes is estimated based on the power of the received signal [1]. Wireless network card drivers export received signal strength indicator (RSSI) values, but the relationship between RSSI values and the signal’s power levels differ from brand to brand [3]. In theory, the energy of a radio signal decays with the square of the distance from the signal’s source [20]. The signal strength measured by a receiver at a given distance $d$can be calculated as in Eq. (12).

$$\begin{array}{c}{P}_r\left(d\right)=P_t+G_t+G_r-\overline{\mathit{PL}}\left(d_0\right)-10nlog\left(\raisebox{1ex}{$d$}\!\left/ \!\raisebox{-1ex}{$d_0$}\right.\right)+X_{\sigma }\end{array}$$

$$=P_0-10nlog\left(d/d_0\right)+X_{\sigma }$$E12

$P_r\left(d\right)$represents the RSS, $P_t$the transmitted power, and $G_{\mathrm{t}}$and $G_{\mathrm{r}}$the gain of the transmitter and receiver antenna, respectively. The constant term $P_0$represents in fact the RSS measured at a distance $d_0$(reference distance), $n$is the path loss exponent, and $X_{\sigma }$is the uncertainty factor due to multipath and shadowing [1]. Whereas, the accuracy of this ranging technique is limited since the RSSI measurements contain noise on the order of several meters due to the effects of shadowing and multipath. Another major challenge is in estimating the propagation model parameters, and the variability of the path loss exponent depending on the environment [1].

5.2 Nodes’ position estimation

Having enough information (distance and/or angles), a node can compute its position using one of the nodes’ position estimation techniques, such as trilateration/multilateration, triangulation, and bounding box.

5.2.1 Trilateration/multilateration

The trilateration technique is the most basic technique. Using the positions of three neighbor anchors, and the distances separating them from these three nodes, the unknown node estimates its position (Figure 2a).

Figure 2.

Estimation nodes’ position: (a) trilateration, (b) triangulation, and (c) bounding box method.

In fact, a node must be positioned someplace along the periphery of a circle centered at the anchor’s position with a radius equal to the distance separating sensor and anchor [3]. Hence, the node’s position is estimated using the intersection of three circles formed by the anchors’ positions and anchor-node distances. A simple system of three equations is built to compute $\left(x,y\right)$the unknown node’s position.

5.2.1.1 Atomic multilateration

On the other hand, when the number of reference points (anchors) is more than three ($n$), the multilateration technique is called atomic multilateration. However, the system of equations presented by Eq. (13) is an overdetermined one and it does not have a unique solution. Assuming $n$anchors of locations $\left(x_i,y_i\right)\left(i=1,2,\dots ,n\right)$, the system of equations is represented as:

$$\begin{array}{c}\left\{\begin{array}{c}{\left(x_1-x\right)}^2+{\left(y_1-y\right)}^2=d_1^2\\ {\left(x_2-x\right)}^2+{\left(y_2-y\right)}^2=d_2^2\\ ⋮\\ {\left(x_n-x\right)}^2+{\left(y_n-y\right)}^2=d_n^2\end{array}\right.\end{array}$$E13

By making some arrangements, the relation above yields:

$$\begin{array}{c}A\mathbf{x}=b\end{array}$$E14

with

$$\begin{array}{c}A=\left[\begin{array}{cc}2\left(x_n-x_1\right)& 2\left(y_n-y_1\right)\\ 2\left(x_n-x_2\right)& 2\left(y_n-y_2\right)\\ ⋮& ⋮\\ 2\left(x_n-x_{n-1}\right)& 2\left(y_n-y_{n-1}\right)\end{array}\right]\end{array}$$E15

$$\begin{array}{c}b=\left[\begin{array}{c}{d}_1^2-d_n^2-x_1^2-y_1^2+x_n^2+y_n^2\\ d_2^2-d_n^2-x_2^2-y_2^2+x_n^2+y_n^2\\ ⋮\\ d_{n-1}^2-d_n^2-x_{n-1}^2-y_{n-1}^2+x_n^2+y_n^2\end{array}\right]\end{array}$$E16

This linear system is solved easily (least square approach) as shown below:

$$\begin{array}{c}\mathbf{x}={\left(A^{\mathrm{T}}A\right)}^{-1}{A}^{\mathrm{T}}b\end{array}$$E17

However, assuming perfect measurements, this technique fails when the distance measurements are noisy.

5.2.1.2 Iterative and collaborative multilateration

Once a node has estimated its position, it becomes an anchor and broadcasts messages containing its estimated position to other nearby nodes. This process called iterative multilateration repeats until all nodes have been localized [21]. However, this technique accumulates localization error with each iteration.

Although it is possible that a node does not have three neighboring anchor nodes. Hence, a method called collaborative multilateration is used [22] by using location information obtained over multiple hops. This is done by constructing a graph of participating nodes that are anchors or have at least three participating neighbors. It estimates its position by solving a corresponding system of quadratic equations relating the distances between the node and its neighbors [3] as presented in Eq. (18).

$$\begin{array}{c}f\left(x,y\right)=d_i-\sqrt{{\left(x_i-x\right)}^2+{\left(y_i-y\right)}^2}\end{array}$$E18

where $X=\left(x,y\right)$is the position of the unknown node, $\left(x_i,y_i\right)$is the positions of anchor $i$, and $d_i$is the estimated distance between an unknown node and anchor $i$.

5.2.2 Triangulation

Based on information on angles instead of distance, the triangulation technique is used to determine the position of a node by using the geometric properties of triangles and trigonometric laws (Figure 2b). The distance to the anchor nodes is estimated using the AoA measurements.

Let $\alpha ={\left[{\alpha }_1,\dots ,{\alpha }_n\right]}^{\mathrm{T}}$. The bearing measurements from $n$anchor nodes. In fact, due to Gaussian noise, $\mathit{\delta \theta }$, with zero mean the relationship between measured and actual bearing is:

$$\begin{array}{c}\alpha =\theta \left(X\right)+\mathit{\delta \theta }\end{array}$$E19

with $\theta \left(X\right)={\left[{\theta }_1\left(X\right),\dots ,{\theta }_n\left(X\right)\right]}^{\mathrm{T}}$actual bearings.

The relationship between the bearings of anchors and their locations can be expressed in Eq. (20).

$$\begin{array}{c}tan{\theta }_i\left(x\right)=\frac{y_i-y}{x_i-x}\end{array}$$E20

To estimate a sensor’s location, different statistical methods can be applied, such as the maximum likelihood (ML) estimator.

5.2.3 Bounding box

Another type of position estimation is called bounding box (min-max algorithm). It was proposed in [23], it uses squares, instead of circles as in trilateration, to bound the possible positions of a node. This is done by constructing a bounding box for each anchor using its position and estimated distance, then determining the intersection of these boxes (Figure 2c). By taking the maximum of the low coordinates and the minimum of high coordinates of all bounding boxes, the shaded area (Figure 2c) is expressed by Eq. (21).

$$\begin{array}{c}\left(\widehat{x},\widehat{y}\right)=\left[max\left(x_i-d_i\right),max\left(y_i-d_i\right)\right]\times \left[min\left(x_i+d_i\right),min\left(y_i+d_i\right)\right]\end{array}$$E21

The final position of the unknown node is then computed as the center of the intersection of all bounding boxes [24, 25].

5.3 Range-based protocols

5.3.1 Ad hoc localization system

Using either RSS or ToA measurement, the ad hoc localization system (AHLoS) provides localization service [21]. Ranging measurements are executed by each node and then position estimation technique (discussed in Section 5.2) is used to estimate the location of unknown nodes in the network [21].

In fact, AHLoS aims to provide a distributed localization in WSNs. Moreover, it does not rely on a single type of ranging technique [1]. Localization accuracy in the range of tens of centimeters in small-scale networks is obtained while using iterative multilateration. However, in large-scale networks, using iterative multilateration leads to inaccurate results since the initial estimation errors are propagated through the net [1].

5.3.2 Time-based positioning scheme

The time-based positioning scheme (TPS) is a distributed range-based protocol, which exploits the TDoA ranging technique [26]. Three noncollinear powerful anchor nodes are deployed around the sensor network and can reach all the nodes in the network. Each anchor node periodically broadcasts a beacon message. An unknown node receives messages from anchors and tries to estimate its location through TDoA measurements. Likewise, it consists of two steps: range detection (TDoA measurements) and location computation, where trilateration is used [1]. The accuracy of this localization scheme depends on the accuracy of the TDoA measurements. Anchors are not required to be synchronized and the beacon messages can be transmitted at different times. However, the requirement of having powerful anchor nodes is not always valid for WSN architectures.

5.3.3 Mobile-assisted localization

Uniform network deployment is not feasible in practice; hence, the localization accuracy is basically limited depending on the network topology and the deployment strategy. Mobile-assisted localization (MAL) [27] uses mobile agents to improve the localization accuracy in WSNs [28, 29], it travels throughout the network to estimate the distance between sensor nodes and itself as well as between these sensors. MAL localizes the nodes using multilateration techniques.

Sensor nodes do not need to perform additional distance measurements or solve complex localization equations. However, the mobile agent required to perform localization tasks may not be available for most applications making the MAL limited in many applications [1]. In addition, the performance is highly dependent on the measurements performed at each single node; hence, any errors in the measuring algorithm affect the whole network. Moreover, in large networks, the localization latency may be meaningfully large because only one mobile agent is used making the time to navigate the whole network long time [1].

6. Range-free localization

Range-free techniques estimate location based techniques since they do not require additional hardware. Table 2 summarizes some range-free algorithms as well as their pros and cons. Similar to the range-based protocols, anchor nodes may also be used to provide a reference for localization.

Method	Pros	Cons
DV-Hop	Simple implementation.	Low accuracy in a non-uniform sensor’s distribution.
APIT	Low complexity. Applicable to scenarios where high localization accuracy is not required.	Low accuracy. Accuracy proportional to the number of anchors.
Centroid	Simple and basic method.	Heavily affected by the number of anchors.
MDS	Ability to locate the positions of more than one node simultaneously. Ability to have the network topology diagram in the absence of anchors.	High traffic. High consumption of energy. Low accuracy in large networks.

Table 2.

Range-free algorithms.

6.1 DV-Hop

DV-Hop localization scheme proposed by Niculescu and Nath [30] is similar to the traditional routing schemes based on the distance vector. The algorithm can be described in three steps. First, each anchor node floods a beacon message including its position and an initial value of hop field equal to zero. Neighbor nodes receive beacons and record the minimum hops to each anchor node and ignore the message with larger hops from the same anchor node [31].

Then, beacons are flooded again to their neighbor nodes with one hop increased. At the end of this step, each node in the network will eventually be able to compute the shortest path distance (in terms of hop count) from any anchor in the network [32]. When an anchor node obtains hop counts to other anchors, it estimates an average distance for one hop, which is subsequently flooded to the entire network [31]. In the second step, after obtaining hop counts to other anchors, each anchor calculates the average one-hop size, called the correction factor (e.g., anchor $i$).

$$\begin{array}{c}\text{Hopsiz}{\mathrm{e}}_i=\frac{{\sum }_{i\ne j}\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}}{{\sum }_{i\ne j}{h}_{i,j}}\end{array}$$E22

where $\left(x_i,y_i\right)$and $\left(x_j,y_j\right)$are the coordinates of anchor $i$and anchor $j$, respectively, $h_{\mathit{ij}}$is the number of hops between anchor $i$and anchor $j,$each anchor node broadcasts its hop-size to network by using controlled flooding. Unknown nodes receive the information of hop-size and preserve the one received from the nearest anchor. Simultaneously, they transmit the hop-size to their neighbor nodes. After all, unknown nodes have received the hop-size from anchor nodes; they compute their distances to the anchor nodes (Figure 3), with $h_{\mathrm{c}}$the minimum hop count as:

Figure 3.

DV-Hop.

$$\begin{array}{c}{d}_i=h_{\mathrm{c}}\times \text{hopsiz}{\mathrm{e}}_i\end{array}$$E23

Finally, after receiving three or more distance information, unknown nodes estimate their positions using multilateration or ML estimation [27]. The distribution of sensor nodes plays a role in the accuracy of the DV-Hop algorithm, that is, if the inter-node distances are nearly equal, the estimated average hop-size will be accurate resulting in a low localization error. However, if the node distribution is uneven, the algorithm’s accuracy is poor [33]. Many improvements are proposed in the literature to reduce errors introduced in the average hop distance calculation and multilateration. An improved DV-Hop is presented in [34], where only the third phase of DV-Hop was altered by making the unknown sensors that need to trilaterate themselves use, the 2D hyperbolic trilateration. Simulation results showed that the proposed algorithm can improve location accuracy and coverage than the original DV-Hop algorithm. Also, it showed that the more regular placement of anchors, the lower the error and higher location coverage. Work in [35] designed as well an improved DV-Hop localization algorithm, which can satisfy the node randomly distribution and heterogeneous network. In the nonuniform network distribution, the algorithm uses the weighted average to reduce the location error; the less hop-count gives great weight and the more hop-count gives small weights. Simulation and experiment results showed that the improved DV-Hop has higher positioning accuracy. A various average hop distance algorithm VAH-DV-hop is proposed in [36], it can reduce power consumption and omit any extra hardware. The principle behind this algorithm is using the angle method to reduce the harm caused by routing void (qualified anchors would execute the calculation) and applying various average hop distances (AHD) to improve the accuracy of distance estimation. The simulation results showed that VAH-DV-Hop can apparently improve the positioning accuracy, especially in uneven networks. In DV-Hop method, straight-line hop distance is substituted by hop distance. However, the path between the anchor node and unknown nodes is not a straight line in a practical network. Authors of [37] improved the accuracy of DV-Hop method by adding a correction to the distance between the anchor nodes and unknown nodes, to reduce localization errors introduced by DV-Hop.

The work in [38] proposes to use a threshold value of distance or hop count to optimize the calculation, and that to protect the dying nodes from energy drain. Moreover, authors in [39] present an algorithm to select a reasonable maximum hop count by hop-size comparison, and that by using a single-hop average error function and a sub-error estimation function to adjust the average hop distance from the source node. The error generated by using all anchors is reduced; nevertheless, the process attains a high amount of online and offline calculation.

Multilateration usually causes errors in the last phase of DV-hop. Hence, a differential evolution (DE) algorithm to rectify the accuracy is proposed in [40]. The DE algorithm uses stochastic search, which demands a highly complex operation.

The inverse distance weighting (IDW) correction method to obtain a more accurate average hop distance is applied in [41]. It is conducted by giving different weights to anchors based on the distances. In fact, the nearby anchors are assigned high weights and further away ones with lighter weights.

6.2 Approximate point-in-triangulation protocol

The approximate point-in-triangulation (APIT) protocol proposed in [42] relies on a network that consists of wireless sensor nodes as well as anchors. It consists of four phases:

1. Beacon exchange: Each node is informed about the connectivity of each of its neighbors to the anchors, and it builds up a table and broadcasts it to its neighbors.

2. PIT test: A node is determined to be inside/outside a triangle formed by three anchor nodes. It is considered outside the triangle if the distances to the vertexes of the triangle increase or decrease simultaneously when it moves along any direction. Otherwise, it is considered inside the triangle.

3. APIT aggregation: This test determines the triangles in which the unknown node exists. Then, an aggregation is performed to constrain the location and that by calculating the maximum overlapping area of these triangles.

4. COG: The node estimates its location as the center of gravity of the overlapping area.

The complexity of the protocol is significantly low compared to range-based algorithms. However, the localization accuracy of the algorithm is also low and is proportional to the number of nonlinear anchors connected to unknown nodes. Consequently, the APIT protocol is applicable to scenarios where high localization accuracy is not required [1].

An algorithm based on energy threshold (ET-APIT) is proposed in [43] to reduce the probabilities of In-to-Out error and Out-to-In error in APIT localization algorithm. By introducing a certain energy threshold, the unknown nodes that are too close to the anchor node triangles causing an error in estimation are removed, and by using iteration, the located unknown nodes are seen as anchor nodes to locate more unknown nodes.

Moreover, when the location of the unknown node is near the edge, the accuracy of the APIT is low; hence, a work in [44] is proposed to eliminate the edge error effect by applying the Barycentric Coordinate Technique.

6.3 Multidimensional scaling

Multidimensional scaling (MDS) is a technique that has its origins in psychometrics and psychophysics [45]. MDS technique, applied to solve localization problems in WSN, displays the structure of distance-like data as a geometrical picture [3]. Its goal is to implement a projection technique capable of preserving the similarities present in the original data set. Hence, the network can be recreated in the multidimensional space. As a result of MDS algorithm, the network layout will be an arbitrarily rotated and flipped version of the original one [3].

The MDS map [46] is a proposed localization method based on MDS technique, which provides both relative and absolute maps. It uses the connectivity information to derive the location of the nodes in the network. Initially, using inter-node distances of all nodes, it constructs the relative map. Then, using enough anchors, it can estimate absolute coordinates by transforming relative maps into absolute map. Since MDS-MAP uses the length of the shortest path as Euclidian distance between the nodes, it is sensitive to the shape of the network. Thus, it presents poor performance on irregular networks, since the difference between shortest path distance and actual Euclidian distance causes large error [47]. An improvement of MDS-MAP is presented in [47], where the last step is different than the original approach in order to solve the problem of irregular networks by dividing the irregular network into several sub-networks. For each sub-network, distribution of the nodes is relatively uniform. Therefore, individual linear transformation can be employed to separately map the coordinates of each set of nodes from the relative map to their absolute coordinates.

Classical MDS localization algorithm has a low accuracy in large-scale sensor network with a lot of nodes. For this defect, the authors of [48] proposed an improved algorithm based on fuzzy-c means. This is done by splitting the network by using a fuzzy c-means clustering algorithm and then applying an MDS localization algorithm in sub-networks.

6.4 Centroid

One of the simplest solutions in range-free localization is the centroid [49]. Its scheme is mainly based on anchors. All anchors send their positions to all nodes within their communication radius. These latter determine their locations by computing the average value of the anchor coordinates heard, that is, the center of gravity, of a system of masses placed in correspondence of the anchor nodes heard [32] calculated as:

$$\begin{array}{c}\left(x=\frac{{\sum }_{i=1}^M{x}_i}{M},y=\frac{{\sum }_{i=1}^M{y}_i}{M}\right)\end{array}$$E24

with $\left(x,y\right)$the unknown node’s location, $\left(x_i,y_i\right)$the anchor’s $i$location, and $M$the number of anchors. The centroid localization algorithm is simple, but it is heavily affected by the number of anchor nodes used. It fits for high anchor density homogenous networks.

6.4.1 Improved centroid: Weighted centroid

The work in [50] proposed a weighted centroid algorithm. The reference node is the nearest to the unknown node. Also, the nodes localized (position estimated) are called upgrade anchor nodes. We summarize this algorithm in 5 steps:

1. The weight is calculated based on the distance between the reference anchor node and other anchor nodes.

2. A number of triangles are formed between the reference anchor node and other anchor nodes.

3. The centroid of these triangles is calculated, then the weight value calculated above is used to weight the group’s centroid, and then calculate the weighted centroid.

4. Finally, the node is localized and upgraded to anchor nodes.

5. This algorithm is applied to all unknown remaining unknown nodes.

7. Centralized versus distributed paradigm

In a centralized algorithm, all sensor nodes in the network send their data to the central receiver and receive their computed locations. It requires plenty of computational power in order to run their operations on central machines enabling the algorithms to execute complex mathematical operations (order of $O\left(n^2\right)$and $O\left(n^3\right)$) [51], which results in a high precision localization, high energy consumption, and a robust scaling effect. It requires that a powerful base station can be deployed among the nodes. However, this process leads to a high communication cost.

On the other hand, in a distributed algorithm, operations are processed using the computational power of each node. Thus, massive inter-node communication and parallelism are required to be able to perform similar to centralized systems [51]. Besides, it is a low-energy consumer, and a robust algorithm when scaling. However, it presents a limited precision due to noncomplex mathematical operations used.

8. Mobile versus static sensors

According to the application and the field of sensor nodes in which they are deployed, sensor nodes are either static and fixed at one place or mobile. A WSN is considered mobile when nodes can move and leave their position to another one, hence, WSN topology changes. Localization in this case is performed to track them, or for navigational purposes. In fact, four combinations of mobility can be discussed:

1. Static sensor nodes and static anchor nodes

2. Static sensor nodes and mobile anchor nodes

3. Mobile sensor nodes and static anchor nodes

4. Mobile sensor nodes and mobile anchor nodes

Three categories discuss the mobility in a WSN:

1. Random mobility: where the sensors move randomly in the area of deployment.

2. Predictable mobility: where the motion of sensors is known but cannot be changed.

3. Controlled mobility: where the sensors move to definite destinations following defined mobility outlines.

Many mobility models are proposed to describe a node’s movement, such as Random Way (RW) [52], Random WayPoint mobility (RWP) model [53], Gauss-Markov (GM) [54], and Boundless Mobility model [55].

In fact, localization techniques can vary the anchor node density. Hence, mobile anchor nodes collaborate with the static sensor nodes to make up the constraint of localization in static WSNs. Work done in [56] reviewed most MANAL (Mobile Anchor Node Assisted Localization) algorithms. It divides the movement trajectories into two types: the first where the anchors move with some already existing mobility models without considering network parameters and localization, and the second one where they move with some path scheduling outlines designed for WSN localization. However, when sensors move additional challenges are encountered such as localization latency. If the time to estimate the position of the node is too long, the sensor will have changed its position. Also, mobility may impact the localization signal; the frequency of the signal may experience a Doppler shift which occurs when the transmitter of a signal is moving relative to the receiver. This shift in frequency is correlated to the positions of the two nodes [57]. Work in [58] took this Doppler effect into account and uses it to improve the estimated position.

Sensor’s mobility causes distance variations and environmental interference. However, a well-designed localization technique can reduce the number of reference anchors required. Also, the network performance is enhanced in terms of packet delay, coverage (better deployment) [59], and connectivity [60]. Moreover, the communication overhead is reduced as well as the energy consumption, which increases the durability of the whole network. However, the localization estimation error is a function of the speed of the anchor nodes and sensor nodes.

9. Fingerprinting technique

Another category of localization techniques is fingerprinting technique or scene analysis. It uses the signatures or fingerprints and is based on a study campaign conducted in the environment where the location system is deployed. It consists of two phases: the off-line phase where a signature database is built and the real-time phase where the location of the node is estimated by comparing the current signature with those cataloged previously. Several types of signatures [61] can be used: the power of the received signal, the AoA, the arrival time, the delay spread, or the number of reflected paths of received signals. A pattern-matching algorithm is used such as K-Nearest-Neighbor, KNN [62], Kernel-based [63], histogram method, support vector machines (SVM) [64], smallest M-vertex polygon (SMP), random forest [65], decision trees [66], and artificial neural networks [67]. Database building is a relatively simple process: (1) It does not require the receiver to connect to the transmitter and exchange messages. (2) It is not necessary to know the transmitters’ position information. However, this technique suffers from noise, and any change in the environment decreases localization accuracy. However, the requirement for generating a signal signature database makes this technique unachievable for the most scenarios of the WSNs, especially in complex environments.

The level of obtained accuracy depends on how many access points and reference points are used. Localization accuracy is enhanced with access points number, also, the resolution is enhanced with reference nodes number; however, this will cost more labor work. Another known drawback of this approach is the need for regular updates for the collected data as well as the built map [68].

10. Three-dimensional localization aspect additional challenges

The majority of localization techniques have been proposed considering only two-dimensional (2D) networks. Henceforth, localization in 3D is an interesting problem in the research community. Landscape-3D [69] is one of the first proposed techniques for 3D localization, where unknown nodes measure a set of distances to mobile location assistants (LAs) using RSSI, then they use unscented Kalman filter to estimate their own position. Also, in [70], RSSI is used for distance measurements while particle filter is used for node positioning. On the other hand, an improved centroid localization method is presented in [71], where each unknown node randomly chooses four anchor nodes in range to form a sequence of tetrahedrons used to calculate its position. In [72], a range-free algorithm is proposed based on flying anchors. In fact, mobile anchor nodes keep transmitting a beacon message along with their location information to unknown nodes and choose three further anchor nodes to form a triangle. Then, the distance is calculated by the link quality induction against each anchor node. Finally, a centroid algorithm is used to estimate the node’s position.

However, some difficulties are faced in 3D localization algorithms [73] such as:

• More anchor nodes are needed for localization; in fact, at least three anchor nodes are required in a 2D space, whereas, in a 3D space, it needs at least four anchor nodes to locate the unknown nodes. Hence, the node density increases as well as the complexity of the algorithm.

• Transmitted signals are affected by the terrain obstacles, affecting the distance estimation between nodes, which will affect the positioning accuracy.

11. Fundamental limitations impacting localization

11.1 Number of anchors

It has been shown that the localization accuracy increases with the number of anchors [74, 75]. Nevertheless, in some scenarios the number of available anchors is low for different reasons such as battery exhaustion or limited communication range [76]. Hence, the localization is limited in these cases.

11.2 Distribution of anchors

The distribution and deployment of anchor nodes play an important role in the localization algorithm. If the anchors are placed only in some portion of the area of interest, it does not guarantee that all unknown nodes reside inside the convex hull formed by the anchors resulting in a low localization accuracy [76]. The geometric dilution of precision (GDOP) is a parameter used to interpret the relation between anchor distribution and accuracy which increases as the value of GDOP decreases [77]. The GDOP is used in optimizing the deployment of the sensors.

11.3 Nonline of sight

The nonline of sight is defined when the propagation path, between the transmitter and receivers, is obstructed. Hence, the communication between nodes may be lost, limiting the localization accuracy. The effects of this phenomenon are more important when the elements in the environment are regularly changing. If there exists information on the NLOS links, it can be used to improve the localization accuracy [76].

11.4 Multipath propagation

Multipath propagation occurs when the transmitted signal arrives at the receiver by two or more paths. It causes constructive and destructive interferences, altering the signal-related measurements and hence affecting the localization accuracy. For example, in the RSS-based localization; the transmitter sensor seems to be farther away than where it is in reality. An Optimal Multi-Channel Trilateration positioning algorithm (OMCT) is presented in [78]. It first uses an adaptive Kalman filter to remove the RSS measurement noise and the optimal node position estimates are obtained from a multiobjective evolutionary algorithm.

12. Localization performance indicator

12.1 Accuracy of localization

The error of localization defined as the Euclidean distance between the real and estimated positions of nodes is the most important feature in localization evaluation. To increase the accuracy of the localization, algorithm has to minimize this error. However, factors affecting the hardware, the processor, and the energy (such as size and cost) must be taken into consideration.

12.2 Complexity

A localization algorithm must be fast, noncomplex, and its development does not require large calculations and large memory storage capacity. For instance, if the complexity is the major property to take into consideration in a localization algorithm, the trilateration method is suitable; however, it is susceptible to inaccurate distances’ estimations.

12.3 Energy constraints

The only energy source of a sensor node is its battery. Hence, careful energy management is required in a WSN to avoid wasting it, it is necessary that the algorithm communicates the least possible via radio. Schemes based on hop-count require high communication cost. Thus, the localization scheme should minimize the amount of node-to-node communication.

12.4 Scalability

Localization technique must ensure appropriate estimation of position when WSN deployment gets larger. In fact, when the distance between nodes increases, the performance of range-based techniques decreases. Moreover, in dense network signals are subject to congestion requiring complex infrastructure.

13. Research directions and challenges

In order to obtain more accurate and better performance of localization algorithms, multimodal localization is more investigated, where, multiple localization techniques are used simultaneously. Work in [79] exploited a hybrid TOA/RSS range estimator combined with an iterative least-squares procedure to localize nodes. The proposed hybrid approach outperformed state-of-the-art techniques. Another hybrid approach is proposed in [80], where a localization based on TOA/AOA techniques is presented. Elevation AoA estimations are combined with ToA measurements, then applied to a weighted least square algorithm to solve the nonlinear problem. Simulation results show that the proposed method outperforms the conventional methods, by adjusting different parameters such as transmit power, signal bandwidth, and the number of anchors. Authors in [81] proposed an approach using hybrid RSS and AOA to resolve a source localization problem in a 3D WSN. RSS model integrates the Gaussian-shaped radiation pattern, and the technique adopts the second-order cone relaxation and alternating optimization techniques. Simulation results demonstrate the efficacy of the presented algorithm.

Another aspect of research directions is the heterogenous WSN. The work in [82] proposed a fault filtering method used with an existing hop-based algorithm. First, it normalizes the distance estimations using the communication radius of nodes and then uses the Jenks Natural Breaks algorithm for filtering out the nodes producing unreliable distance estimations. The approach is tested in 2D/3D, isotropic/anisotropic networks. Localization accuracy shows an improvement of 14 and 52% when tested with DV-Hop, Weighted DV-Hop. Another approach [83] is a priority-based algorithm, which gives priority to a few anchors based on their AHD. Unknown nodes are then localized with weighted centroid method using high priority anchors. Results show that algorithm outperforms existing weighted centroid methods in anisotropic fields.

An additional research direction considered localization in irregular field. Irregularities present challenges in nodes localization, and they can be signified in terms of irregular radio propagation pattern of nodes, noisy environment, network holes, and irregular fields [84]. It is useful and important in environmental applications such as forest fire monitoring, however, forest areas are usually not plain uniform fields. Hence, considering irregularities increase localization accuracy [85]. In fact, RSS-based localization techniques are affected by irregularities, since RSS values between a pair of transmitters and receivers at fixed distance varied when the receiver was placed at different propagation directions from the transmitter [86]. Hence, a novel technique where node segmentation with improved particle swarm optimization (NS-IPSO) is proposed in [87]. It divides sensor nodes into segments to improve the accuracy of the estimated distances between pairs of anchor nodes and unknown nodes. Similarly, irregularities add a positive bias for the TOA and TDOA measurements [88], resulting in overestimation of distance between nodes and higher localization errors. A neural network-based localization algorithm called LPSONN was described in [89], it is a centralized algorithm implemented and simulated in isotropic networks with and without coverage holes or shadowing zones, and anisotropic networks. A neural network using the received information is trained. Results show that the proposed algorithm has less localization error rate and storage requirements than the analogous methods.

14. Future scopes

The evolution of WSN, technologies, as well as localization applications create the necessity of more advanced research exploiting intelligent surfaces as well as advanced millimeter-wave systems. Future scopes and studies are concerned by a new concept that emerged recently called Reconfigurable Intelligent Surfaces (RISs). In fact, future WSN will not only allow people and devices localization but will be turned into a distributed intelligent communication, sensing, and computing platform [90].

RIS may be able to propose dense networks for sensing the environment and to offer a platform that provides highly accurate localization services in outdoor and indoor scenarios, by taking advantages of realizing large-size smart surfaces. Also, RISs can offer a possibility to acquire a fully electromagnetic-based computing platform and that thanks to the possibility of performing algebraic operations and functions directly on the incident radio waves [90]. In addition, RIS can present important advantages in terms of performance, energy consumption, and cost for localization and mapping [91].

Besides, systems where antenna arrays, are deployed as a large intelligent surface (LIS) are a prospective field for positioning and coverage enlargement of wireless networks [92].

More interesting future scopes and studies will be based on the joint usage of RISs and millimeter wave MIMO systems for the fifth generation (5G) [93], where evaluation of the impact of the number of LIS elements are studied and the theoretical performance for localizing are compared to the conventional scheme with one direct link and one non-line-of-sight path [93].

Hence, several researchers have started investigating several scopes and opportunities offered by RIS as well as the envisioned 6G platform, which is expected to sense the environment, store and process information to provide network applications.

15. Conclusion

Localization in WSN is an important and challenging task, it is essential for many applications and network management. This chapter surveys the most popular range-based and range-free techniques. It presents the basics of each one as well as the research directions. Readers can profit from this chapter to well understand the concepts of localization in WSN. Different works are summarized in this work, allowing readers and researchers to be positioned with respect to enhancements and ideas presented in the literature.

Nevertheless, localization and mapping algorithms discussed and detailed in this chapter can benefit from using RIS facilities, in which position and orientation are known a priori [91], improving, hence, the accuracy and extending radio coverage.

Moreover, this concept has high potential approaches for next-generation localization, and more importantly when investigations consider beyond 5G localization.