A survey on mobile anchor assisted localization techniques in wireless sensor networks

Abstract

Identifying locations of sensor nodes in wireless sensor networks (WSNs) is significant for both network operations and most application level tasks. Although, geographical positioning system (GPS) based localization schemes are used for determining node locations but the cost of GPS devices and non-availability of GPS signals in indoor environments prevent their use in large scale WSNs. A substantial amount of research work exist that intend at obtaining precise and relative spatial locations of sensor nodes without requiring large amount of specialized hardware. Mobile anchor assisted localization is one typical approach that significantly reduces the implementation cost by using limited number of mobile anchors. In this survey, we present key issues and inherent challenges faced by the mobile anchor assisted localization techniques in WSNs. We take a closer look at the algorithmic approaches of various important fine-grained mobile anchor assisted localization techniques applicable in WSNs. In addition, we highlight the error refinement mechanisms adopted by the state-of-the-art works associated with their approaches. Well known mobile anchor trajectories presented in existing works are also reviewed. Finally, open research issues are discussed for future research scope in this field.

1 Introduction

Wireless sensor network (WSN) consists of a large number of energy-constrained, low-cost and low-power sensor nodes. Each sensor node is a device, equipped with multiple on-board sensing elements, wireless transceiver modules and power supply elements. They are characterized by limited computational and communication capabilities. In WSNs, identifying locations of sensor nodes is important for both network operations and most application level tasks. This is because sensory data without spatial and temporal coordination is of very limited use [1, 2]. Determining the physical location of sensor nodes after they are deployed is known as localization [3]. Location aware sensor nodes may help in enhancing the performance of routing protocols [4–6], target tracking techniques [7, 8], disaster response system [9, 10] etc. The node (henceforth, we use the terms ‘sensor node’, ‘sensor’ and ‘node’ interchangeably) localization problem has received tremendous attention from the research community because accuracy in sensor node locations is an absolute necessity for correct operation of the system. The importance of the precise location information in different applications are elaborated below:

• In events including disaster relief, forest fire, failure of structure etc., early location prediction of such events helps in planning adequate response system that may either prevent those events from occurring or mitigate the consequential damages. The response system is dependent on accurate location information. Therefore, accurate localization scheme based response system may prevent such calamities.

• Navigation and vehicle tracking is another area where accurate location estimation scheme using WSNs may be extremely useful. Vehicle tracking with autonomous interception mechanism can be deployed in an outdoor area. It senses entry as well as movement of an offending evader in the area. A cooperative mobile agent is dispatched for intercepting the evader as soon as it gets detected before any damage is done. The successful realization of such a tracking and interception system is dependent on accurate location information.

• The topology of WSNs is highly dynamic in nature. This is because some sensor nodes die if they drain out their energy faster compared to other sensor nodes leading to coverage and connectivity disruptions in the network. In such scenarios, in order to reestablish coverage and connectivity, new sensor nodes may be injected into the network. Here, geography routings are found to be more efficient than topology based routing schemes. The basic issue that should be addressed in a geography routing scheme is its ability to gather location information and to have a location tracking mechanism for establishing connectivity before routing data. So, localization or finding locations of sensor nodes is a fundamental step in routing or transmission of data in WSNs.

Global Positioning System (GPS) is the most commonly used and precise method for sensor node localization. Unfortunately, the GPS solution does not always performs well because of cost, limited power supply etc. in WSNs. Additionally, the deployment-ability of sensor nodes which are equipped with GPS may be reduced due to the increased size. Finally, these GPS equipped sensor nodes have limited applicability because GPS works only in an open field [6]. A more reasonable solution to the problem is to allow small proportions of sensor nodes with known location information (either equipped with GPS or installed at a fixed position) available at all times. The sensor nodes with known coordinates are called seeds or anchors. These anchors help the location-unaware sensor nodes (these nodes are called unknown) to become localized by exchanging messages.

A compendium of knowledge representing rich collection on localization issues and their solutions in WSNs for diverge applications can be found in the recent past literatures [11–14]. The existing localization schemes proposed for sensor nodes in WSNs are classified into two main groups, (1) range-based or fine-grained and (2) range-free or coarse-grained [12, 15]. Range-based techniques generally use distance or angle estimates for localization whereas range-free techniques use connectivity information for localization. Although, it is a comprehensive categorization of localization algorithms, but in the presence of mobile anchors and/or mobile sensor nodes it is not distinct enough. In a wide range of applications, a fully static node in WSNs is not practical [16]. One important factor is to introduce node mobility in the localization algorithms. To capture this possibility, localization methods are reclassified with respect to the mobility state of anchors and sensor nodes into four groups [16, 17], as shown in Fig. 1. The groups of localization methods are as follows: (1) static anchors and static nodes like the methods proposed by Grribben and Boukerche [18], Simonetto and Leus [19], and Zhao et al. [20], (2) static anchors and mobile nodes such as the schemes in [21, 22], and [23], (3) mobile anchors and static nodes (simply “mobility-assisted” henceforth) such as the methods proposed by Chen et al. [24], Cui and Wang, [25], and Guo et al. [26], and (4) mobile anchors and mobile nodes like the methods proposed in [27], [28], and [29]. The common feature of the four categories is that they all need anchors to locate the unknown node. In this survey, we restrict ourselves on the category of mobile anchors with static sensor nodes, since this kind of localization promises a wide variety of application scenarios. An example can be a military application or a monitoring task like forest fire detection, where sensor nodes are dropped usually from a helicopter on land, and transmitters are attached to soldiers or animals acting as mobile anchors. Generally, mobile anchor based localization works focus on two major issues, either proposing an efficient localization algorithm or devising an optimum mobile anchor movement strategy.

Fig. 1

Classification of localization schemes in WSNs

In this survey, we provide key issues and inherent challenges faced by mobility-assisted localization techniques in WSNs. In addition, we attempt to review the existing state-of-the-art fine-grained mobility-assisted localization methods with emphasis on algorithmic approaches. Review of WSN localization techniques can be found in [12–15, 30]. In [30], the researchers provide a comprehensive survey on the mobile beacon trajectories. Precisely, they evaluate the performance of five static trajectories of mobile beacon namely, Random Way Point (RWP) [31], SCAN [17], HILBERT [17], CIRCLES [32] and Localization algorithm with a Mobile Anchor node based on Trilateration (LMAT) [33]. It is revealed that among the five trajectories, LMAT offers the best performance regarding the localization success, ineffective position rate and localization accuracy. In [14, 15], authors review and analyze existing localization techniques. Amundson and Koutsoukos [13] present a survey on localization methods for mobile wireless sensor networks. In particular, they provide taxonomies for mobile wireless sensors and localization, including common architectures, measurement techniques, and localization algorithms. Mao et al. [12] present a survey on the challenges faced by the localization algorithms in various applications. More specifically, the survey describes the challenges faced by a localization method due to non-line-of-sight ranging error, criteria for selecting node to become active or remain passive, scheduling the sensor node to optimize the tradeoff between localization performance and energy consumption. Our review in contrast focuses on the measurement techniques and localization algorithms applicable for mobility-assisted localization techniques in WSNs. In addition, we highlight the error refinement mechanisms adopted by the state-of-the-art works associated with their approaches. Furthermore, well known mobile anchor trajectories presented in existing works are reviewed.

The rest of the paper is organized as follows. We briefly discuss about the different categories of localization techniques in Sect. 2. In Sect. 3, we explain the generic approach, key issues and main challenges faced by the mobility-assisted localization techniques. In Sect. 4, we study existing algorithmic aspects of different mobility-assisted localization techniques. Section 5, provides summary of existing trajectory used in mobility-assisted localization techniques. Section 6 talks about open issues in mobility-assisted sensor node localization. Finally, Sect. 7 concludes this survey.

2 Localization techniques in WSNs

As mentioned in the earlier section, based on the mobility state of anchors and sensors, the existing localization schemes are broadly categorized into four groups: (1) static anchors and static sensors, (2) static anchors and mobile sensors, (3) mobile anchors and static sensors, and (4) mobile anchors and mobile sensors. In this section, we briefly survey representative schemes in each category.

2.1 Static anchors and static sensors based techniques

In WSNs localization, static anchors and static sensors based methods are more mature than the other three categories. In this category, localization algorithms estimate the locations of static unknown sensors by using knowledge of the absolute positions of a few static anchors and inter-sensor measurements such as distance and bearing measurements, connectivity information. Distance and bearing measurement techniques can be roughly classified into three categories (1) Angle-of-Arrival (AoA) measurements, (2) distance related measurements, and (3) Received Signal Strength (RSS) profiling techniques [12]. In the existing works, AoA measurements rely on a direct Line-of-Sight (LoS) path from the transmitter to the receiver. Due to this fact, the accuracy of AoA measurements is limited by the directivity of the antenna, by shadowing and by multipath reflections. On the contrary, distance related measurements include propagation time based measurements, i.e., one-way propagation time measurements, roundtrip propagation time measurements, Time-Difference-of-Arrival (TDoA) measurements etc. In one-way propagation time measurements technique, the time difference between sending a signal at the transmitter and receiving of the same signal at the receiver is measured. In this technique, for precise measurement of time difference or propagation time, the local time at both the transmitter and the receiver need to be synchronized accurately. To alleviate the synchronization problem, in roundtrip propagation time measurements, the same clock is used to compute the roundtrip propagation time. Here, the time difference between the time when a signal is sent by a sensor and the time when the signal returned by a second sensor is received at the original sensor is determined. However, in this measurement technique, the main error source is the delay required for handling the signal in the second sensor. One of the most commonly used distance measurement method in this category is TDoA measurement, since it free from both synchronization and delay problems. Here, TDoA measurements of the transmitter’s signal at a number of receivers with known location information are done for distance measurement. In this technique, the accuracy in distance measurement depends on the separation between receivers. Precisely, as the separation between receivers increases, the TDoA measurement provides more accurate distance measurement. Another category of distance measurement technique is RSS profiling. Initially, in this technique, a map of the signal strength behaviour in the coverage area is formed either by offline through a priori measurements or online via sniffing devices [34] deployed at predetermined locations. This technique is more popular for location estimation in WLANs than WSNs.

Unlike distance and bearing measurement techniques, connectivity information based localization algorithms do not rely on any of the measurement techniques mentioned earlier. Instead they use the connectivity information, i.e., ‘‘who is within the communications range of whom’’ [35] to estimate the locations of the unknown sensors. One of the popular connectivity information based localization algorithm is DV (distance vector)-hop [18]. The principle of this algorithm is that, initially, all the unknown sensors exchange the distance vector packets to collect hop distance information and the coordinates of all anchors. Then, each anchor floods its average distance of each hop with data packets. When an unknown sensor receives the average distance of each hop, it estimates the distance to each anchor according to the recorded hop information. The inaccuracy of the DV-hop algorithm is high due to the accumulated error that results from averaging of the hop distance between two neighbouring sensors. Unlike DV-hop, recently, a limited flooding based Lightweight Iterative Positioning (LIP) [36] algorithm is proposed for WSN localization. The proposed LIP algorithm works in two phases. In first phase, the unknown sensors collect information about the coordinates of anchors; based on that information, they come to an initial, rough estimate of their positions. In second phase, the sensors iteratively refine their position estimates, after having learned the position estimates of their immediate neighbors and measured ranges between the sensors.

In summary, several distance and bearing measurement techniques, connectivity information based schemes are available for WSN localization where static anchors and static sensors are used. The localization accuracy of each of these technique depends on number of factors such as the anchor density, application environment etc. In existing works, it has been observed that distance and bearing measurements based localization algorithm requires more complex equipment and consume significant amount of computation and communication energy to obtain a relatively accurate location. On the contrary, it has been observed that the localization accuracy of connectivity information based algorithms is average and do not need additional equipment. Nevertheless, the requirement of anchor density is smaller but the sensor density is greater.

2.2 Static anchors and mobile sensors based techniques

In this approach, small number of static anchors is used to localize a set of mobile sensors. Here, typically, anchors are placed at an unobtrusive location like a ceiling or wall, and periodically transmits beacons with its coordinates. An unknown mobile sensor that listens to messages from beacon uses these messages to infer its own present location. Most popular works in this category are RADAR [21], Dynamic Triangular (DTN) [22]. Roughly, all these schemes based on historical information consist of two phases: an offline phase and online localization phase. In offline phase, a database of RSS at different locations with respect to anchor locations is built whereas in online localization phase, a mobile sensor compares the received signal strength values it received from different anchor locations with the stored values in the database, and the best fit gives an estimate of its location. Different from [21, 22], in both [23] and [37], the authors proposed a localization scheme based on Received Signal Strength Indicator (RSSI) and Link Quality Indicator (LQI). To reduce the location error, in [23] authors developed artificial neural network based training method, whereas in [37], artificial neural networks is used to establish a relationship between the patterns of RSSI and location coordinates. Similar to [23], authors in [38], also developed an artificial neural network based approach to reduce the effect of the various noise sources and harsh factory conditions on the localization algorithm. Unlike [21–23], Chen et al. [39] proposed an algorithm based on hop distance measurement and particle filtering. Similar to [18], they used same technique to measure hop distance. However, during the hop distance information collection stage a correction process is introduced by the authors to reduce the number of message transmissions.

In summary, a number of localization techniques are available where researchers use static anchors to localize a set of mobile sensors. However, most of these schemes are popular for indoor location systems, where many unknown sensors are mobile such as monitoring the living of human or animal. Typically, localization algorithms based on historical information are able to achieve better accuracy than localization algorithms based on hop distance measurements. However, that accuracy is achieved at the expense of higher energy consumption.

2.3 Mobile anchors and static sensors based techniques

To reduce the number of expensive GPS enabled anchors, mobile anchor based localization technique is evolving as a promising approach. It is well understood that a moving anchor with guided mobility can cover a small area within a reasonable time. On the contrary, a few moving anchors are sufficient to cover a large area. Considering this fact, in this approach, a small number of moving anchors are deployed in order to localize a set of static sensors [13, 16]. The anchor traverses the deployment area and periodically transmits beacons with its coordinates to help unknown sensors to estimate their positions. The use of such approaches leads to double impact of mobility of anchors on the localization process. On one hand, the localization difficulty is increased due to uncertainty of anchor movements while on the other hand these mobile anchors are responsible for providing additional measurements to the mobility-assisted localization schemes. Since in this survey, our focus is to provide a comprehensive discussion on mobility-assisted localization approaches and therefore, in subsequent sections existing works are discussed in details.

2.4 Mobile anchors and mobile sensors based techniques

In this category, mobile anchor is used to localize a set of mobile sensors. Since both anchors and sensors are mobile, the techniques used in this category gave fairly accurate location estimation at the cost of additional energy consumption due to increase of computational load in unknown sensors. Typical application areas where such type of localization technique is preferred are urban cities [40], mine sweeping [27] etc. Monte Carlo Localization (MCL) is one of the most popular methods in this category. In [41, 42], researchers proposed localization technique based on Monte Carlo approach. Typically, MCL is based on the Monte Carlo method which has been used for robot localization [27]. In MCL, possible locations of a mobile sensor are represented using a set of weighted samples and which are updated recursively in time using the Monte Carlo approach. Although, Monte Carlo method based localization technique gives acceptable accuracy, but it requires a significant number of mobile anchors. Other than MCL, in [28] and [29], researchers proposed RSSI-based and Fuzzy logic-based localization techniques, respectively where both anchors and sensors are mobile.

3 Design issues and challenges

In this section, we first describe the essential background of mobility-assisted localization techniques for WSNs. We mention key issues of location discovery, which are very essential aspects in any localization technique including mobility-assisted ones. Finally, the inherent challenges incurred by the mobility-assisted localization techniques are also discussed.

3.1 Background

In WSNs, a sensor can determine whether it is in the radio range of an anchor according to a beacon received from the one-hop anchor. Considering this capability, in mobility-assisted localization scheme, mobile anchors broadcast beacons at regular intervals that contain their coordinates as shown in Fig. 2. If a sensor node receives beacon broadcast multiple times from different positions, it is more or less similar to receiving beacons from multiple anchors. A sensor node obtains its location relative to the mobile anchor based on RSS of the beacons through Bayesian inference [14]. The accuracy of location estimation in mobility-assisted localization scheme depends on the distribution of anchor locations used by the mobile anchor. Main drawback associated with mobility-assisted localization scheme is significant localization delay. It is because sensor nodes are localized only when they are in direct contact with the mobile anchors and receive sufficient signals from them.

Fig. 2

Localization using a mobile anchor

In presence of several categories of mobility-assisted localization schemes, similar to [25], we broadly classify the existing mobility-assisted localization schemes into two classes- distance-based or range-based and connectivity-based or range-free. In range-based schemes, sensor nodes estimate their distances from mobile anchors using some specialized hardware. These measurements are used in methods like multilateration, which is based on the idea that a sensor node’s location is uniquely specified when at least the distances or angles of three or more reference points are available for a sensor node. A special case of multilateration is trilateration [43]. Although the use of range measurements results in a fine-grained localization scheme, range-based algorithms require sensor nodes containing hardware for making range measurements. Range-free schemes do not use radio signal strengths, angle of arrival of signals or distance measurements and do not need any special hardware. Range-free algorithms require that each sensor node knows: (1) nodes that are within radio range, (2) their location estimates and (3) the (ideal) radio range of sensor nodes. No other information is used for localization. Thus, range-free schemes are more cost-effective because they do not require sensor nodes to be equipped with any special hardware. Also, it requires less information than range-based schemes. Moreover, range-free schemes can only provide a coarse-grained estimate of each sensor node’s location, which means that they are only suitable for applications requiring an approximate location.

3.2 Key issues

The particular requirements for localization schemes for WSNs generally depend on the nature of applications, constraints imposed by hardware and network infrastructure. Based on these, some of the specific issues concerning the design of mobility-assisted localization scheme are as follows:

• Accuracy and precision of localization: Accuracy refers to how much correct is the location estimation relative to the actual location and precision describes the consistency of the estimates [44]. Each system contains granularity of measurements that refer to the smallest measurable distance. The granularity of measurements range from few inches or bigger depending on the used equipment and technique. Similar to the previous, the required granularity of localization that is required in WSNs is also application dependent.

• Absolute versus relative locations: GPS devices in localization systems help in determining the absolute location in terms of latitude, longitude and altitude with respect to the earth’s coordinates [44]. On the other hand, locations may be obtained with respect to a given frame of reference, such as the location of a mobile anchor. Based on the application requirement, locations can be either absolute or relative. It is noted that a relative location can always be transformed to an absolute location if the absolute location of the reference point is known.

• Communication requirements: Communication between a sensor node and a mobile anchor or other sensor nodes can provide significant benefits such as time synchronization and improvements in accuracy and precision. However, a fundamental issue in WSNs is the minimization of communication requirements in the sensor nodes to conserve energy. This introduces unique considerations for designing the localization scheme as well.

• Cost: As cost is an important factor, so the design requirements of large scale sensor networks are: (1) to minimize the cost of sensor nodes, and (2) take the benefit of combined sensing and computational abilities of many nodes in the network [44]. Therefore, the localization system should not consists of expensive hardware. The cost involved in building external infrastructure for providing localization is also one factor but it is not that much considerable as it does not increase with network size.

3.3 Inherent challenges

Localization plays a significant role in many applications, few of which are briefed in Sect. 1. However, mobility-assisted localization itself is a complex problem to be solved because of the demanding requirements for low cost, high energy efficiency, and scalability for any network size, as well as practical issues associated with sensor node deployment. Herein, we sum up some major challenges specially faced by mobility-assisted localization approaches to obtain accurate location information.

• Anchor trajectory In mobility-assisted localization, unknown sensors can be localized only when they are in direct contact with the mobile anchor and receive sufficient signals from it. Anchor trajectory thus has to be properly planned so as to be shortest in length as well as it should be quick and full so as to provide accurate localization. Huge localization delay along with low localization ratio and high localization error occur if the trajectory is of poor form [45]. As sensor nodes are dropped randomly, their placement pattern cannot be known beforehand. If the initial pattern is known in a dynamic environment, the final sensor node distribution may vary due to movement of wind or other factors. Therefore, the key challenge for mobility-assisted localization is the beacon trajectory that should be planned instantly instead of beforehand.

• Sensor node density Mobility-assisted localization approaches very rarely deal with varying node densities. If the network is a dense one having enough number of mobile anchors, accurate localization result is achievable with minimum movement of mobile anchor [46]. In contrast, for sparse networks, mobile anchor may require traversing more distance within the network area to localize sensor nodes. Therefore, for a sparse network having limited number of anchors, the main challenge for the localization problem is to obtain maximum location accuracy using optimal path movement.

• Noisy measurements Mobility-assisted localization approaches are required to face noisy measurements as proximity, range and angle measurements deal with noises as wireless signals are uncertain in nature. So for the success of mobility-assisted localization methods, modeling the noises and lessening the impacts on localization performance are very much necessary.

• Infrastructure-less environment Sensors are generally deployed in some inaccessible terrain or areas where infrastructures are very less. In order to estimate the sensor node’s relative location to the moving anchor using the received signal strength, it is necessary to calibrate the system, for obtaining the propagation characteristic of the beacon in the air. Hence, the design of mobility-assisted localization schemes should be automatic without human calibration and extensive environment profiling.

• Obstacles and terrain irregularities Obstacles and terrain irregularities jointly can also cause devastation on mobility-assisted localization process. Large rocks can occlude line of sight, prevent measuring range, or interfere with radios, introduce errors in range measurement and produce incorrect location information. In indoor environment, natural features like walls can hinder measurements as well. All these challenges are likely to come up in real life implementations, so mobility-assisted localization schemes should be able to cope up with these.

• Resource constraints Cooperation among sensor nodes in mobility-assisted localization process is done by exchanging information between neighbouring sensor nodes. For example, as in centralized localization algorithms [14], cooperation is achieved using a central node (usually the base station/sink). Additional communication cost results due to collecting and forwarding the measurements to the base stations and sending the localization information to the nodes.

4 Mobility-assisted localization approaches

It has been seen that mobility of sensor nodes has double impact on the localization process. On the flip side, the uncertainty of sensor node movements leads to increased difficulty in localization. While on the contrary, mobile anchors provide additional measurements to the mobility-assisted localization schemes. In mobility-assisted localization, many approaches for obtaining per-node location knowledge have been explored. Based on the type of knowledge used in localization, we divided localization approaches into two categories: range-based and range-free. In rest of this section, we survey the algorithmic approaches used for each of these two categories.

4.1 Range-based localization approaches

Range measurement and geometric computations enable geometric techniques to estimate the locations of the sensor nodes. The basic idea that is used is that Euclidean distance between two sensor nodes can be measured with their radio signals by Time-of-Arrival (ToA), TDoA, RSSI etc. [46]. After obtaining at least three different Euclidean distances of mobile anchors, the unknown sensor node applies either trilateration or multilateration algorithm to find out its own location. In this section, we have reviewed few popular and innovative range-based techniques for measuring distances between mobile anchors and unknown sensor node. We have discussed how measured distances have been used by the unknown sensor node to estimate its own location. In addition, we have provided an overview on how the existing techniques deal with the location estimation error that occurs mainly due to noises. Pros and cons of each technique are also discussed in this section.

4.1.1 Localization based on ToA measurement

Sensor node localization using ToA technique [24, 47–49] measures the time a signal takes to arrive at several number of sensor nodes. ToA measurement requires knowing the time when the signal was transmitted. Therefore, in most cases time synchronization between sender and receiver is needed. However, there are existing works where ToA measurement is done without time synchronization [24]. Next, we have discussed about the algorithmic approach of sensor node localization based on ToA measurement.

Let X, be an arbitrarily positioned unknown sensor. Mobile anchor moves from one direction to another direction while transmitting beacon, as shown in Fig. 3. ToA measurement is performed in two steps. In the first step, mobile anchor broadcasts a beacon or a ranging request which is received by all the unknown sensor nodes in the radio range. In the next step, each unknown sensor node sends an acknowledgement (ACK) to the mobile anchor for responding to the request. In order to prevent collision, the unknown sensor performs a random or schedule back-off before sending the ACK.

Fig. 3

An example of basic ToA ranging scheme

Now, ToA measurement obtains the distance in the following way: Distance between mobile anchor and unknown sensor node X is $d_{A}^{X} = c\left( {T_{X}^{1} - T_{A}^{1} } \right)$, where c is the speed of light, $T_{A}^{1}$ is the time when mobile anchor broadcasts beacon and $T_{X}^{1}$ is the time when X receives beacon. Similarly, distance between unknown sensor node X and mobile anchor is $d_{X}^{A} = c\left( {T_{A}^{2} - T_{X}^{2} } \right)$ where $T_{X}^{2}$ and $T_{A}^{2}$ are the times when X sends ACK and mobile anchor receives ACK respectively. As $\left( {T_{A}^{2} - T_{A}^{1} } \right)$ and $\left( {T_{X}^{2} - T_{X}^{1} } \right)$ are the elapsed times at mobile anchor and unknown sensor node X respectively, they are calculated using local clock of mobile anchor and unknown sensor node.

Therefore, calculated distance between mobile anchor and unknown sensor node X is

$$\frac{{d_{A}^{X} + d_{X}^{A} }}{2} = \frac{c}{2}\left[ {\left( {T_{A}^{2} - T_{X}^{2} } \right) - \left( {T_{X}^{1} - T_{A}^{1} } \right)} \right] .$$

(1)

The major challenge facing ToA based ranging techniques is the difficulty in accurately measuring when the signal was transmitted, since the propagation speed could be extremely high compared to the distance to be measured.

In [24, 47–49], ToA based ranging technique as discussed above has been used to measure distance between mobile anchor and unknown sensor node [using (1)]. Due to noises and propagation in environment, ToA based ranging techniques suffer from Non-Line-of-Sight (NLoS) error. The presence of NLoS error in range measurement degrades the location estimation performance and linearly increases the mean location error. Several NLoS error mitigation techniques have been proposed such as the maximum likelihood estimator, root-mean-square technique, least square technique to solve the location estimation problem in the NLoS scenario [50]. In [24], Chen et al. [24] considered root-mean-square technique to mitigate the effect of NLoS error in the range measurement. Unlike, Wen and Chan [48] considered AoA/ToA hybid self-positioning scheme to alleviate NLoS error. Further, an adaptive fuzzy control based location adjustment algorithm has been proposed in [48] in order to improve the location estimation accuracy.

4.1.2 Localization based on TDoA measurement

TDoA based range measurement techniques improve upon the ToA based range measurement technique by eliminating the need to know the exact time when the signal was transmitted. In TDoA based approach, range is measured in the following way:

The mobile anchor periodically transmits RF and ultrasonic signals. Initially, the mobile anchor transmits the RF signal. After a very short time interval a narrow ultrasonic signal is transmitted. An unknown sensor node listens to mobile anchor transmissions (i.e., RF and ultrasonic signals) and computes the distance to nearby mobile anchor using the time-difference-of-arrival of RF and ultrasonic signals.

As shown in Fig. 4, a mobile anchor transmits RF and ultrasonic signals one after another. An unknown sensor X receives those signals and computes the time-difference-of-arrived signals i.e. δ. Finally distance between the mobile anchor and unknown node is obtained by multiplying δ and the speed of the ultrasonic signal (about 1.13 ft/ms at room temperature).

Fig. 4

An example of time-difference-of-arrival

Even though computing the distance between each pair of node’s locations e.g., mobile anchor and unknown sensor node is a trivial problem, the inverse problem, which tries to find locations of the nodes given the Euclidean distances between each pair of nodes is far from trivial problem. This problem can be formulated as a graph realization problem, aiming at mapping the nodes in the graph to points in the plane so that the Euclidean distances between nodes equal the respective edge weights. Priyantha et al. [51] proposed a localization scheme using mobile nodes based on TDoA measurement. As finding the location from Euclidean distances between each pair of nodes is non-trivial, therefore, in [52] authors provided a novel solution by designing a movement strategy that produces a global rigid graph (shown in Fig. 5) of known distances among the static sensor nodes. Using those known distances, finally unknown sensor nodes calculate their own locations.

Fig. 5

Examples of graphs a locally rigid but not globally rigid, b globally rigid

Since mobile anchor transmits both RF and ultrasonic signals, therefore, there is every possibility of occurence of collision and interference among each other which may introduce error in the range measurement. To minimize the errors, a decentralized randomized transmission algorithm is proposed in [51] where signal transmission times are chosen randomly with a uniform distribution within an interval. Thus, the broadcast of different signals are statistically independent, which avoid repeated synchronization and prevent collisions. Further, for reducing the location estimation error, three distance measurement error filtering algorithms viz. Majority, MinMean and MinMode are proposed in [51]. Among these three algorithms, Majority is simplest to implement whereas reduced location estimation error is produed by both MinMean and MinMode. Priyantha et al. [52] considered Majority algorithm for reducing the location estimation error.

4.1.3 Localization based on RSSI measurement

Another category of range measurement techniques estimate the distances between mobile anchor and sensor node from the RSS measurements. Since the sensor nodes are equipped with radios to perform communication, the distance estimation by measuring the RSS requires no additional hardware, and is unlikely to significantly impact local power consumption, sensor size and hence cost. A simplified model for RSSI based range measurement is given by the following:

$$RSSI \propto d^{ - \alpha }$$

(2)

where d is the distance between mobile anchor and unknown sensor node and α is a constant relevant to the atmosphere. Given a RSSI value measured [using (2)] by the radio of unknown sensor node, the unknown sensor node is able to calculate its distance from the mobile anchor.

In [26, 53–56], authors proposed an energy efficient localization scheme based on mobile anchor where distance between mobile anchor and unknown sensor node is calculated by RSSI measurement. After obtaining such distances from three reference locations, an unknown sensor node calculates its own location using trilateration. To improve the location accuracy, in [56], Kim and Lee proposed a trajectory planning for the mobile anchor with an objective of minimizing the movement energy consumption per unit distance and transmission energy consumption per beacon. This is done as RSSI based range measurement is extremely susceptible to multipath fading, variations in temperature and humidity. Therefore, localization scheme based on RSSI range measurement is prone to errors. To mitigate the erroneous range measurement, profiling [57] is used in which a map of RSS values is constructed during an initial training phase. Sensor nodes then estimate their positions by matching observed RSS values with the training data. Further, a novel mobile-assisted localization scheme called Perpendicular Intersection (PI) is proposed in [26]. Instead of directly mapping RSSI values into physical distances, PI utilizes the geometric relationship of a perpendicular intersection for computing the sensor nodes positions. Through real life implementation using TelosB motes it has been shown that PI achieves high location accuracy and low overhead. A robust extended Kalman Filter based state estimator is proposed in [53], for node localization. It is computationally more efficient and robust compared to the extended Kalman Filter [58]. A statistical technique is considered in [53] to reduce location estimation error.

4.1.4 Localization based on network density clustering

A novel mobile anchor-assisted localization algorithm based on Network Density Clustering (NDC) for WSNs is proposed in [59]. Initially, authors proposed a network density based clustering scheme. The clustering scheme chooses a sensor as the cluster head with the highest local core density. After choosing the cluster head, based on the density-reachable principle, member nodes of the cluster are chosen. After forming cluster, the scheme uses Multi-Dimensional Scaling map (MDS-MAP) [60] to obtain the initial coordinates of all the cluster heads. The MDS approach includes three steps. The first step is to form the distance matrix with distances between all pairs of sensor nodes in the network by measuring either RSS or ToA. In the second step, singular vector decomposition is performed to determine an initial relative map of the sensor nodes on the plane. The last step performs the necessary flip, rotation and scaling according to the distances between mobile anchors. After knowing the coordinates, the cluster head becomes the anchor. Now, both cluster head and mobile anchor help the unknown member node in becoming a localized node. Authors considered trajectory planning of the mobile anchor as a traveling salesman problem, in which the mobile anchor traverses all the cluster heads. Since the traveling salesman problem, is an NP-complete problem, in order to reduce computational complexity, authors adopted a heuristic method e.g. genetic algorithm for obtaining sub-optimal solution for path planning of mobile anchor. As in the proposed localization technique, the localization progress propagates from the high-density region to the low-density region in the network, which facilitates reducing the accumulation of positioning errors and improves localization accuracy. Even though the proposed technique improves both the utilization rate of the mobile anchor and localization accuracy with reduced anchor movement length, but the time complexity of the proposed scheme is considerably high and it is about $O\left( {n^{3} } \right)$, where n is the number of sensor nodes in the network.

The existing works discussed above considered different noisy range measurement tolerating techniques to improve the accuracy of position estimation. Apart from the discussed techniques, rich collections of noisy range measurement tolerating techniques exist such as Bayesian Filter [61], Monte Carlo method [45], Metropolis–Hastings algorithm [62], Markov Chain Monte Carlo [63] etc.

4.2 Range-free based localization approaches

Range measurements, often, may not be obtainable due to various constraints e.g. cost. Under these circumstances, proximity information provided by the radios attached to the sensor nodes could lead to adequate solutions for the localization problem. In this section, we discuss about the underline idea of few popular range-free methods used in mobility-assisted localization techniques.

4.2.1 Localization based on Monte Carlo method

One of the well known range-free techniques specially used in mobility-assisted localization technique is Sequential Monte Carlo (SMC) method. In SMC based localization technique [64–66], possible locations of a sensor node are represented with a set of sample locations, which are updated when mobile anchors move. They provide the coordinate of a new location using the SMC approach. Location estimation using SMC method is performed in the following way:

Let t be the discrete time, l _t denotes the position distribution of the sensor node at time t, $l_{t}^{i}$ denotes the ith sample of the location of a sensor node at time t, and o _t denotes the observations from mobile anchors received between time (t − 1) and t. A transition equation $p\left( {l_{t} |l_{t - 1} } \right)$ describes the prediction of sensor node’s current position based on previous position, and an observation equation $p\left( {l_{t} |o_{t} } \right)$ describes the likelihood of the sensor node being at location l _t given the observations.

Eventually, from the above discussion, the Monte Carlo method based localization techniques require quite a number of steps in order to compute location of sensor node. The main steps of the SMC method based localization techniques are as follows-

Initialization The sensor node has no knowledge about its position at time 0, so the initial samples are selected randomly from all possible locations:

$$\left\{ {l_{0}^{i} |1 \le i \le N} \right\}\mathop{\leftarrow}\limits^{Initialize}Random\;positions.$$

Prediction At time t, the sensor node uses the transition distribution $p\left( {l_{t} |l_{t - 1} } \right)$ to predict its possible locations based on previous samples and its variation at time (t − 1):

$$\left\{ {l_{t}^{i} |1 \le i \le N} \right\}\mathop{\leftarrow}\limits^{{p\left( {l_{t} |l_{t - 1} } \right)}}\left\{ {l_{t - 1}^{i} |1 \le i \le N} \right\}.$$

Filtering At time t, the sensor node uses new information received to eliminate predicted locations that are inconsistent with observations:

$$\left\{ {l_{t}^{{{\prime }i}} |1 \le i \le N} \right\}\mathop{\leftarrow}\limits^{{p\left( {l_{t} |o_{t} } \right)}}\left\{ {l_{t}^{i} |1 \le i \le N} \right\},$$

where $l_{t}^{{{\prime }i}}$ denotes the ith sample of the location of a sensor node after filtering step.

Re-sampling The purpose of re-sampling step is to gradually remove samples with lower weights and keep those with higher weights:

$$\left\{ {l_{t}^{{{\prime \prime }i}} |1 \le i \le N} \right\}\mathop{\leftarrow}\limits^{{{\text{Re}}-sampling}}\left\{{l_{t}^{{{\prime }i}} |1 \le i \le N} \right\},$$

where $l_{t}^{{{\prime \prime }i}}$ denotes the ith sample of the location of a sensor node after re-sampling step.

The main drawbacks of SMC are that it needs a high density of mobile anchor and the sampling technique it uses to generate probable locations is very slow and computation-intensive. In [64], Rudafshani and Datta presented a mobile-assisted localization for sensor networks based on SMC method. In order to converge the localization error, in the proposed scheme, each unknown sensor uses the weights of its neighbours (rather than weights of samples of neighbours) to weigh its samples. Evaluation results of this scheme confirm improved localization accuracy and low dependency on the number of mobile anchors.

4.2.2 Localization based on convex method

Presence of obstacles such as mountains or buildings in the node deployment area, impose huge challenge in localizing the sensor nodes for mobility-assisted localization techniques. One such scheme is proposed in [67], where authors considered the presence of obstacles during localizing the sensor nodes. The working principle of the proposed technique is elaborated below.

Let us consider that the current position of the mobile anchor is a and its lower and upper bounds of transmission radii are r and R, respectively, as shown in Fig. 6. If the unknown position sensor node (triangle in Fig. 6), at position x, receives the beacon signal, it is concluded that the distance between the mobile anchor and sensor node satisfies either $\left\| {x - a} \right\| \le R\,{\text{or}},\;\left\| {x - a} \right\| > r.$

Fig. 6

The single constraint case

Hence, for single constraint case, the estimated position is found by minimizing the expression given in (3)

$$\left( {\left\| {x - a} \right\| - r} \right)^{2} + \left( {\left\| {x - a} \right\| - R} \right)^{2} .$$

(3)

Similarly, for the inequalities under multiple constraints, optimal position of sensor node is obtained by solving the following problem:

$$\mathop {\hbox{max} }\limits_{x} \sum\limits_{t} {\left[ {\left( {\left\| {x - a_{t} } \right\| - r_{t} } \right)^{2} + \left( {\left\| {x - a_{t} } \right\| - R} \right)^{2} } \right]} , \quad {\text{for}}\,t = 1,2, \ldots ,K$$

(4)

where a _t is the position of the mobile anchor at time t, r _t and R _t denote the lower and upper bounds of the transmission radii of mobile anchor at position a _t in time t. It is evident from (4) that the problem is non-convex.

As the above problem is non-convex and cannot be directly approximated by using convex relaxation techniques, therefore, it is transformed into the equivalent following convex problem

$${\text{Find}}\quad \mathop {\hbox{max} }\limits_{x,y} \sqrt {\sum\limits_{t} {\left[ {\left( {y - 2a_{t}^{T} x + \left\| {a_{t} } \right\|^{2} - r_{t}^{2} } \right)^{2} + \left( {y - 2a_{t}^{T} x + \left\| {a_{t} } \right\|^{2} - R_{t}^{2} } \right)^{2} } \right]} }$$

(5)

such that $\left\| x \right\|^{2} \le y$

By solving the above [see (5)] convex problem using interior-point algorithms [67], sensor node obtains its own location. The benefit of the proposed localization technique is that it can provide accurate location for both feasible and infeasible cases [67]. However, as the location calculation involves solving several problems, the computation cost of each sensor node increases significantly.

4.2.3 Localization based on geometric constraints

The geometric measurement based localization technique involves three steps in localizing the unknown sensor nodes. The steps are as follows: (1) select three anchor points from among the received beacons; (2) obtain the intersection area with two anchor points using geometric constraints; and (3) calculate the location with the third anchor point.

Three beacon points selection It is assumed that a mobile anchor moves around the deployed area of the sensor nodes at a constant speed and broadcasts a beacon that includes its own absolute location information after every d distance intervals, called beacon distance. Now, if a sensor node receives a beacon it concludes that mobile anchor is located within the communication circle of its own. This is referred as the beacon point for location of mobile anchor.

A sensor node on receiving the first beacon from a mobile anchor, selects that location as a beacon point, e.g. B ₁, B ₂ etc., as shown in Fig. 7. If no beacons are received by a node during a predefined time after receiving its last beacon, this beacon is selected as a beacon point; i.e., B ₄ in Fig. 7. Every time the mobile anchor moves across the communication circle of the sensor node, the above process is repeated; i.e. B ₁, B ₄, and B ₅ are ultimately finalized as the three beacon points.

Fig. 7

Location estimation using geometric constraint method [68]

The intersection area Since each sensor node receives a beacon at every beacon point d and communication/radio range of a mobile anchor is r, so, the beacon points are located between the distances (r − d) and r from the sensor node. Therefore, based on geometric constraints, the sensor node must be located in the ring area that is defined by two circles with radii r and (r − d) from a beacon point. On obtaining the first beacon point, sensor node position within the ring area is made by the beacon point. After obtaining the second beacon point, the sensor node is placed within the second ring area.

So, it is concluded that the location of the sensor node is within the intersection area of the two ring areas, as shown in Fig. 7; if one piece of intersection area consists of vertices P ₁, P ₂, P ₃ and P ₄ be A _P and the other has A _Q , the sensor node is located within $A_{P} \cup A_{Q}$.

Location calculation The midpoints P _m and Q _m of the intersections points P ₁ and P ₃, and Q ₁ and Q ₃respectively are calculated after finding the intersection area $A_{P} \cup A_{Q}$. The probable locations of the unknown node are the midpoints P _m and Q _m . Two circles with a radius of (r − d) have no intersection points (P ₃ and Q ₃) if the distance between the two beacon points is more than 2(r − d). For this scenario, P ₃ and Q ₃ are designated as the midpoints of the two beacon points.

The performance of the geometric constraint based location estimation method exhibits enhanced location accuracy [68]. Further, Lee et al. [68] analyzed the localization error and found that it can be reduced by decreasing the communication range or the anchor distance. Here, by anchor distance authors mean the interval distance at which a mobile anchor broadcast a beacon.

4.2.4 Localization based on perpendicular bisector of a chord

The mechanism proposed in [69, 70] localize a sensor node using mobile anchor based on a geometry conjecture, named Perpendicular Bisector of a Chord (PBC), which states that a perpendicular bisector of a chord passes through the center of the circle.

A sensor node’s location can be calculated by observing the movement of the mobile anchor with the help of the given conjecture on PBC. A visited mobile anchor’s list is kept that helps in determining the beacons sent by the mobile anchor while it is coming and leaving within the radio range of the sensor node. The sensor node positions itself as the center of the circle by selecting beacons that are responsible for creating chords of the radio range of the node, as shown in Fig. 8. Fine-grained location information is obtained using mobile anchor’s location broadcast in range-free localization for the geometry conjecture based approach.

Fig. 8

Localization using intersection of perpendicular bisectors of two chords

The success of the developed localization mechanism based on a geometry conjecture depends on the accurate construction of the chord. Ssu et al. [69] observed that when the length of the chord is too short, the probability of unsuccessful localization increases rapidly. However, by decreasing the beacon interval or moving speed of mobile anchor can significantly reduce the maximal location error. Further, authors observed that if radio range is enlarged, the maximum location error gradually diminishes.

4.3 Summary

In this section, we summarize the evaluation of existing mobility-assisted localization schemes. The ability to fix the location of a sensor node in terms of fine-grain location would determine the usefulness of a particular mobility-assisted localization scheme. The three basic metrics used for evaluation of existing schemes are: localization accuracy, computation and communication costs, and number of mobile anchors.

4.3.1 Localization accuracy

The localization accuracy of a solution is usually quantified using the average Euclidean distance between the estimated locations and the true locations normalized to the communication range or other system parameters. Localization accuracy relies mainly on the physical sources of localization errors. The physical sources are represented by a wide range of noises and quantization losses of range measurements. In mobility-assisted localization, mobility of the anchor has severe impact on the signal compared to the static anchor. For example, the frequency of the signal may undergo a Doppler shift or introduce errors in the range measurement. Doppler shifts occur when the mobile anchor is moving relative to the unknown sensor node. The resulting shift in frequency is related to the positions and relative speed of the mobile anchor and unknown sensor node.

In mobility-assisted localization, one can achieve fine-grained localization but in exchange of increased localization delay. This is because sensor nodes can only be localized when they are in direct touch with the mobile anchor and receive adequate signals from it. Therefore, proper planning of anchor trajectory is needed for obtaining shortest length and good coverage of every sensor for fast and accurate localization.

4.3.2 Computation and communication costs

As energy is one of the scarcest resources in WSNs, it is necessary to consider the computation and communication costs of the localization process in the evaluation of mobility-assisted localization schemes. In mobility-assisted localization schemes, localization accuracy is improved by mobility of the anchor at the expense of significant amount of energy consumption. Moreover, all unknown sensor nodes are needed to provide range measurements to algorithms like MDS-MAP (see Sect. 4.1.4). This incurs the expense of forwarding the measurements to the processing point and solving the high dimension matrix. On the contrary, for distributed algorithm, multihiop localization deals with the tradeoff between the communication cost involved in propagating the mobile anchor locations and accuracy degree. The number of iterations needed in a localization process depends on the energy consumption involved in improving localization results and how much accuracy is obtained through refining.

4.3.3 Number of mobile anchors

It is important to note that mobility-assisted localization techniques constantly need an assured level of connectivity. The discussions on the different mobility-assisted localization algorithms suggest that more number of mobile anchors in the network area lead to better localization performance. However, more number of mobile anchors in the network area does not necessarily guarantee high accuracy in location estimations. It is due to the fact that increase in mobile anchor leads to increase in collision of beacons. So there is also need of careful planning for anchor trajectory otherwise collisions of beacons may occur.

4.3.4 Summary of performance

In earlier sections, existing mobility-assisted localization schemes under various scenarios were discussed. In this section, we summarize the performance of those schemes with respect to location accuracy, communication/computation costs, and number of nodes (sensors and anchors).

Generally, the localization accuracy of a solution is measured from the average Euclidean distance between the estimated locations and the actual locations that are normalized to the radio range or other system parameters [14]. The impact of sensor node density is not of much importance for mobility-assisted localization, as in static localization scenarios. Also, the importance of the communication or computation costs is not same for off-line simulations and the real implementations. The simulation results of various existing mobility-assisted localization schemes are given in Table 1. Here, the location accuracy is examined through the tradeoffs between accuracy and measurement performance, radio range, number of mobile anchors, trajectory of anchors etc. Table 1 shows typical values for the parameters when various tradeoffs for one solution are reported in the literature. For the sake of conciseness, radio range, velocity of the mobile anchor and beacon broadcast frequency are denoted by R, V and F respectively in the table, while h, l and N represent height, width of the network area and number of samples respectively.

Table 1 Summary of simulation results for existing schemes

5 Trajectory planning of mobile anchor

The anchor trajectories are categorized into two classes based on the actual distribution of sensor nodes as: static trajectory and dynamic trajectory. In case of static trajectory or static path planning the mobile anchor follows the predefined and deterministic trajectory. On the other hand, the dynamic or real time trajectory takes into consideration the real distribution of the sensor nodes in the sensing field [71]. Figure 9 represents an overview on the existing trajectories. Finding the optimal trajectory of the mobile anchor for sensor node localization is a very challenging problem. Fundamentally, trajectory planning for a particular application has two goals: (a) to offer network coverage and (b) to provide good quality beacons. Compared to the first goal, the second goal of path planning, which is unique in the sensor network localization problem, is much more challenging. This work investigates both the classes of anchor trajectories in this section.

Fig. 9

Classification of mobile anchor trajectories

5.1 Static path planning

To improvise the accuracy and coverage factors of localization schemes that depend on mobile anchor with optimum trajectory, the mobility advantage can be taken into consideration for such schemes. One work [3] addressed the basic properties of optimum path anchor such as fully covering the area of interest considering a shortest path, the movement of the mobile anchor should be such that it passes in close proximity to maximum possible unknown nodes as well as provide minimum three non-collinear anchor positions etc. Another work [17] proposed three common trajectories of SCAN, DOUBLE SCAN, and HILBERT space filling curve for mobile beacon movement. The accuracy of these three trajectories depends on the resolution of the trajectory. In [32], CIRCLES and S-CURVES were proposed for minimizing the number of straight lines and to avoid the problem of collinearity of path planning methods. A spiral trajectory, similar to the CIRCLES, proposed in [72] efficiently eliminated the collinear problem and the localization accuracy. A path planning mechanism for localization based on trilateration was provided in [33] where the movement of the mobile anchor is in accordance with an equilateral triangle for broadcasting its present location. Here, a brief review is presented on each category of the existing static mobile anchor trajectories for localization.

5.1.1 Random planning

5.1.1.1 RWP

The RWP mobility model [31] is a widely used model mostly due to its simplicity. A random destination is chosen by the mobile anchor and it travels towards the newly chosen location. In one work [69], the authors used the RWP mobility model for facilitating the localization of static nodes. The anchor’s positional message is transmitted by the mobile anchor at every destination. The primary disadvantage of the RWP mobility model is the non-uniform coverage of the network field. It is quite evident that while some points may be visited repeatedly by the mobile anchor while some points may never be visited by the same. It is highly difficult for determining the path length traveled by the anchor as the movement of the anchor may be stopped after a certain time interval or predefined path length.

5.1.1.2 GM

In [73], the authors use the Gauss-Markov (GM) mobility model for proposing an adaptive localization approach for WSNs. Three strategies namely perpendicular bisector strategy, the virtual repulsive strategy and the velocity adjustment strategy are combined for increasing the localization efficiency. The velocity adjustment strategy is responsible for ensuring that the mobile anchor is able to adjust its velocity automatically. The perpendicular bisector strategy adjusts the trajectory for the mobile anchor that helps the unknown nodes to obtain sufficient non-collinear anchor coordinates. The virtual repulsive strategy takes care of the fact that the mobile anchor leaves the communication range of location-aware nodes or returns back to the surveillance area. The mobile anchor adaptively adjusts its velocity and direction based on the three strategies mentioned above. The mobile anchor lowers its speed and its movement depends on the perpendicular bisector strategy after it receives acknowledgement packets. Other than this, the mobile anchor increases its speed for shifting to other areas of the surveillance region. This mobility model provided movement patters similar to that in the real world for mobile anchor. Both theoretical analysis and simulation results show that the proposed model enhances the localization accuracy with lesser energy requirement as well as covers more surveillance region with respect to virtual anchors-energy ratios localization scheme.

5.1.2 Static planning

5.1.2.1 SCAN

A simple and easily implementable mobile anchor trajectory planning scheme named SCAN proposed in [17] uniformly covers the network field. The uniform coverage of the network field helps in ensuring low localization error and receiving of beacons by all the unknown sensor nodes. SCAN divides the square deployment area into m × m sub-squares and connects their centers using straight lines. In SCAN, the mobile anchor traverses the network area along one dimension either along the x axis or y axis. The resolution of the trajectory is defined by the distance between two successive trajectory segments parallel to the y axis while the mobile anchor travels along the y axis. To guarantee that the sensor node receives the beacons, the maximum resolution should be 2R’ if the communication range of the sensor node is R’. SCAN is beneficial for use as it provides uniform network coverage, and guarantees that beacons are received by all sensor nodes from the mobile anchor using a correct resolution. However, the imperative weakness associated with SCAN is collinearity of beacons. In particular, for large resolution, many sensor nodes receive beacons only from one line segment and one direction, which create uncertainty and prevent them from obtaining a good estimate along the x axis. To evade this problem, the trajectory must be adequately dense for the sensor nodes so that sensor node will be able to hear the mobile landmark when it moves on two successive segments along the y axis.

5.1.2.2 HILBERT

In order to reduce the collinearity without significantly increasing the path length, Hilbert curve based technique, namely HILBERT, is proposed in [17]. In [17], the Hilbert curve is proposed to handle the localization as well the coverage tasks, whereas in [74] the main aim of studying the Hilbert curve is to solve the collinearity problem of localization by making the mobile anchor to take more turns. Authors in [74] realized that when the mobile anchor moves on the Hilbert curve, the sensors have the chance of receiving non-collinear beacons and a good estimate for their locations. Similar to SCAN, HILBERT divides the two dimensional square deployment area into square cells and connects their centers using straight lines. For example, a level-m Hilbert curve divides the two dimensional space into 4^m square cells and centers of those cells are connected using 4^m line segments, each of length equal to the length of the side of a square cell. Therefore, the resolution of HILBERT is the length of the side of a square cell. As the Hilbert curve based trajectory planning ensures more path turns compared to SCAN, therefore, sensor nodes receive non-collinear beacons and obtain a good estimate of their positions. Since Hilbert curve always connects the centers of two successive square cells, the mobile anchor never moves on the border of the deployed area. Thus, in HILBERT, sensor nodes near the border possibly receive beacons only from one direction and their location estimates are not accurate.

5.1.2.3 CIRCLES

Since the straight line based trajectories of mobile anchor perpetually introduce collinearity, a circular trajectory called CIRCLES is proposed in [32]. CIRCLES consists of a sequence of concentric circles centered within the deployment area. In CIRCLES, the resolution (R) is half of the radius of the innermost circle, and it sequentially increases the radius by R at each outer circle. The main benefit of using CIRCLES is that collinearity is not introduced and thereby every sensor node located within the circles becomes localized. If the deployment area is square, all the four corners cannot be covered by using CIRCLES until and unless larger circles are added. Now, if large circle is added in order to cover four corners, then basically the path length of mobile anchor is increased. There is also a problem of scalability if CIRCLES is used. To be more specific, on increase of the deployment area, anchor path is required by CIRCLES to accommodate larger circles. This reduces the localization accuracy as the amount of non-collinearity reduces with increase in size of the circles.

5.1.2.4 LMAT

The idea of equilateral triangle configuration idea was initially proposed in [75] for the anchors placement to help localize the mobile sensors. Based on this idea, the LMAT algorithm is proposed in [33] where optimal anchor positions for the mobile anchor are used for obtaining better localization accuracy and coverage. In this work it is considered that the mobile anchor moves along an equilateral triangle trajectory and transmits the beacons including the anchor position information at regular intervals. A node is able to formulate its coordinates using the trilateration method where the distance between an unknown sensor and the mobile anchor is measured using RSSI. The objective of this scheme is to design the optimal traveling trajectory of mobile anchor assisted localization.

5.1.2.5 Z-curve

Recently, in [16], authors proposed a path planning technique called as Z-curve. The proposed trajectory has the ability to successfully localize all the nodes with high precision and in shortest time. Here, the basic curve of the trajectory is built based on the Z shape. The reason for choosing this shape is that such a trajectory has short jumps to overcome the collinear problem. Also a path is provided for transmitting three consecutive non-collinear beacons with the objective of reducing the localization time. Here, a two dimensional network area is considered that is divided into four sub-squares and the mobile anchor is responsible for connecting the centers of the cells for setting up the Z-curve. The proposed path planning mechanism is comprised of four phases. The first phase is responsible for finding out the relation between the communication range and localization of unknown sensors. In the second phase the communication range of the mobile anchor is adjusted that is traversed by the Z-curve while the third phase provides the shortest path traversed by the mobile anchor based on the Z-curve. The final phase illustrates that the three anchor positions collected via the shortest path provided by the Z-curve are non-collinear. The authors compared the proposed mechanism with existing five strategies and results demonstrate the efficiency of the Z-curve in terms of accuracy, time, success and ineffective position rate.

5.2 Dynamic path planning

Real time or dynamic path planning involves collection of neighbourhood information by every sensor node that is done through message exchange and is further provided to the mobile anchor. The main objective of such type of path planning is to work out an anchor mobility scheduling algorithm with the help of which the mobile anchor is able to dynamically decide its trajectory. The main disadvantage of real time path planning is the high number of message exchanges involved leading to increased energy consumption.

5.2.1 MALS

In one work [76], the authors considered the shortest path traversed as the trajectory of the mobile anchor. The trajectory is designed by using the information of network topology. The network is initially divided into localization units termed as localizable subnets or orphan nodes. The shortest path passing through all localization units is chosen as the trajectory of the mobile. The authors proposed the scheme named as MALS (mobile assisted localization by stitching) with the objective of designing the trajectory where nodes are deployed in non-uniform and irregular manner. The trajectory here is obtained by stitching all the localization units in the shortest path to be traversed and blank areas are discarded. An anchor enters a localization unit along its path to be traversed and moves in a half circle. The anchor broadcasts positions in three different locations. After receiving the anchor positions, the nodes compute their positions in a distributed way. The mobile anchor moves further along the path based on the geographical positions of the nodes in the present unit and the edges connecting to the next unit. After the anchor finishes traveling along its assigned trajectory, the nodes in the network get localized and the localization units are combined together. Simulation results demonstrate that the proposed scheme avoids unwanted movements in the blank areas with much less trajectory paths as compared to existing works under various non-uniform and irregular deployment scenarios.

5.2.2 APP

In [77], Kim et al. proposed an Adaptive Path Planning (APP) scheme where the authors considered the path movement length and the number of anchors for determining the trajectory. This work is different from existing works that use mobile anchors in the sense that it provides adaptive path movement construction in an energy efficient manner with less computational complexity. The path constitutes a regular triangle with the length being the communication range. Here, the mobile anchor obtains its next destination adaptively while analyzing the request messages received from unknown sensor nodes. The positions of the anchor are contained in the path movement where the mobile anchor broadcasts beacons consisting of its present location. This adaptive scheme is designed keeping in mind randomly deployed sensor networks. Here, candidate areas are chosen where mobile anchors can transmit their beacons. The candidate areas are considered for ensuring receiving of beacons irrespective of the actual position of the sensor node. For both ground and aerial anchor types, the candidate areas are obtained. The mobile anchor is responsible for choosing the nearest location in the candidate area as the next anchor location iteratively. This scheme minimizes the energy consumed by reducing the number of beacons and the movement distance. Here bilateration and two-hop neighbour information are utilized for deriving the exact position. The distance between the sensor nodes as well as that between a sensor node and a mobile anchor is obtained using the RSS technique. The authors compared their work with existing works to show their aim for minimizing the energy consumption is satisfied.

5.2.3 AGM

In [78], the authors developed an Anchor Guiding Method (AGM) for obtaining better location accuracies and lessening the length traversed by the mobile anchor. The nodes deployed statically estimate their positions using previous range-free localization algorithms having different location inaccuracies. The estimated region’s size provides a guideline for the mobile anchor for efficient building of the path. Here, the authors observed that the improvement in the nodes’ location inaccuracies is mainly dependent on the location of the anchors that further define the path of movement of the mobile anchor. In the users monitoring region a large number of nodes are deployed for event detection and the sensed information is sent back using multi-hop routing. While the existing localization schemes are performed, the mobile anchor gathers the information of the estimative regions of the nodes. It is assumed that every static node has an initial estimative region in the form of a rectangle at a particular time. The mobile anchor knows its own location information using GPS or other location support system. The communication ranges of the mobile anchor and the static nodes are same. Experimental study demonstrates that the proposed scheme outperforms other existing schemes in terms of the parameters mean location error, localization efficiency and balance index.

5.2.4 DREAMS

To obtain the most suitable anchor trajectory, the authors in [45] proposed a DeteRministic dynamic bEAcon Mobility Scheduling (DREAMS) scheme. In this work, the trajectory is determined dynamically on the lines of the Depth-First Traversal (DFT) of the network graph. Here no prior knowledge about the deployed area is needed. The anchor trajectory is defined by the track of DFT of the network graph and so it is deterministic. The mobile anchor performs DFT dynamically, under the instruction of nearby sensor nodes on the fly. The mobile anchor at first visits a sensor node by moving randomly and then performs a DFT on the network graph based on the instruction of the present visited sensor node. It stops moving once it returns to the first sensor node and the sensor node has no unvisited neighbours. During DFT, the anchor performs intelligent distance-based heuristic movement from node to node following RSS, and sensor nodes run the built-in localization procedure to self-localize using received beacon signals. To shorten the anchor trajectory, DFT may be performed using a local minimum spanning tree subgraph, whose edges are weighed by RSS. Also unvisited, but localized, sensor nodes may be excluded from DFT if the exclusion does not affect discovery of unknown sensors. Real life implementation of DREAMS shows that it produces accurate location estimation.

6 Open issues

There has been extensive research on mobility-assisted sensor node localization, nevertheless, there are several important open issues especially relevant to mobility-assisted localization in a WSN which either remain unsettled or unexplored comprehensively. Some of these issues are listed below.

• Energy consumption The problem of minimizing energy consumption of the mobility-assisted localization process deserves more attention. Even though, energy consumption issues are addressed in the existing mobility-assisted localization techniques, the energy efficiency goal still remains challenging.

• Design complexity The moving trace of mobile anchor must be optimized since mobile anchors are only capable of low-speed and short-distance mobility in real environment due to high power consumption of locomotion. Since the distribution of mobile anchors can affect location performance in static WSNs, therefore, efficient trajectory planning for mobile anchors can further increase location accuracy for target estimation.

• Non-convex topologies Localizing the sensor nodes located in the boundary is a problem because less information is available about them and that too of lower quality. This problem is exacerbated when a node deployment area has a non-convex shape. Sensor nodes outside the main convex body of the deployment area can often prove to be unlocalizable. Even when locations are found, the results tend to feature disproportionate error. Further, an efficient trajectory planning for mobile anchors can increase location accuracy in such situation.

• Cost Several existing works show that, using mobile anchors for localization of sensor node is beneficial, as extra measurements on spatial relationships are provided along their corresponding trajectories. But, a mobile anchor, having more resources compared to an ordinary sensor node, is expensive. So, for localization, only a small number of mobile anchors can be actually used. Also, small numbers of mobile anchors must effectively cooperate with sensor nodes to obtain maximum utility.

• Three-dimension localization In the existing scenario, sensor node localization is typically used for finding out the location of nodes in a two dimensional network area. However, in real life application, sensor nodes are usually deployed in a three dimensional space, which leads to differences on both ranging results and localization schemes. Investigation on mobility-assisted localization schemes focusing on three dimensional space is of particular interests to real life applications of WSNs. In [25, 79], an attempt is made to localize the sensor nodes in a three dimensional network. However, the existing localization schemes in three dimensional space are not completely examined.

7 Conclusion

Discovering accurate locations of sensor nodes in WSNs is decisive to both network functions and most application level tasks. In this survey, we presented key issues and inherent challenges faced by mobility-assisted localization techniques in WSNs. We discussed the algorithmic approaches of various important fine-grained mobility-assisted localization techniques. In this survey, mobility-assisted localization techniques are usually referred to as either range-based or range-free. However, such a wide categorization is grossly insufficient, because it restricts categorization for hardware requirements of the localization schemes. In order to validate the proposed line of investigation, we reviewed existing solutions, discussed the difficulties of using range measurements and proximity information in details for mobility-assisted localization techniques. In addition, well-known mobile anchor trajectories presented in existing works are also reviewed. A summary on simulation results of important mobility-assisted localization techniques is also presented on the basis of location accuracy, computation/communication costs and number of nodes including mobile anchor. Several open issues for further research have also been included.