Sage Journals: Discover world-class research

Abstract

Multi-hop wireless sensor networks are widely used in many location-dependent applications. Most applications assume the knowledge of geographic location of sensor nodes; however, in practical scenarios, the high accuracy on position estimates of sensor nodes is still a great challenge. In this research, we propose a hop-weighted scheme that can be useful in distance-based distributed multi-hop localization. The hop-weighted localization approach generates spatial locations around position estimates of unknown sensors and computes local functions that minimize distance errors among hop-weighted and static neighboring sensors. The iterative process of each unknown sensor to re-estimate its own location allows a significant reduction of initial position estimates. Simulations demonstrate that this weighted localization approach, when compared with other schemes, can be suitable to be used as a refinement stage to improve localization in both isotropic and anisotropic networks. Also, under rough initial position estimates, the proposed algorithm achieves root mean square error values less than the radio range of unknown sensors, in average, with only a few iterations.

Keywords

Multi-hop localization weighted function wireless sensor network routing algorithm

Introduction

Wireless sensor networks (WSNs) are emerging as monitoring systems that can take control over large geographical areas. They have become a reality due to recent advances in micro-electromechanical systems (MEMs), embedded processing, and wireless communications allowing that many deployed sensor nodes can communicate among them over the wireless medium. Sensor nodes (e.g. smart devices) are autonomous in the sense that they have the ability to acquire, store, process, and transmit over short distances physical or chemical phenomenon quantities. However, in most cases, sensor nodes are equipped with batteries without rechargeable and replaceable nature, which force minimizing the energy wastage.

Detecting physical or chemical events from the environment is an important and common task in many research areas. Such events become relevant if they are wireless-stamped with parameters such as time of occurrence and spatial location. A WSN is aimed to correlate these parameters with sensor data, where time and space have been discussed recently.^1–3 Thus, accurate location of sensor nodes plays a fundamental role to figure out where the sensed data are coming from. Moreover, the position information of sensor nodes is crucial in location-aware applications like wildlife tracking, search and rescue, traffic management, military affair, and disaster areas to mention a few.

Locating sensor nodes can be trivially solved by adding a GPS (or other schemes to self-localize) into each sensor node; however, this technique has been blamed for the nature such as costly and energy-consuming which hinders the application in practice. In many situations, a WSN is deployed in a structured manner where sensor nodes are placed by hand or via autonomous robots. In this case, the location sensor problem represents a minimum challenge since the location of sensor nodes could be known $a priori$ . However, when there are location constraints (e.g. remote or inaccessible areas like battlefield or disaster regions), sensor nodes could be dropped from an aircraft for environmental monitoring, that is, in an ad hoc manner where there is not information about sensor node locations $a priori$ . However, due economic constraints, only a small fraction of the randomly deployed sensors can often be equipped with GPS systems. These sensor nodes are called beacons or anchor nodes (ANs), and the rest of sensors, called non-anchors nodes or unknown sensors (USs), must estimate their locations using the known positions of ANs and radio-frequency (RF) transmissions with neighboring sensors.^4,5 The last approach, which relies on ANs to localize, is named anchor-based localization that indirectly produces absolute positions in USs. Also, when the localization technique is based on inter-sensor measurements, it is commonly called a range-based localization technique. In range-based schemes, there are some measurements—like time of arrival (ToA), time difference of arrival (TDoA), received signal strength (RSS), angle of arrival (AoA), or combination of them—that can be employed to estimate distances among neighboring sensors.^6,7

Due sensor nodes communicate over short distances, data are transmitted from sensor nodes to a gateway node (i.e. sink node) using multi-hop routing protocols. To self-localize, in range-based multi-hop networks, every US must estimate its distance to at least three non-collinear ANs (in a two-dimensional (2D) scenario). Thus, once an US has obtained its initial position estimate (e.g. using trilateration or any other scheme), a refinement stage can be carried out in order to improve its own position estimation using information collected from one-hop neighboring sensors.

Once deployed, wireless connections among sensor nodes determine the type of network topology, and it basically depends on factors such as the number and radio-range of sensors, environmental conditions, geographic structures, and how sensor nodes are distributed. For instance, Figure 1(a) shows an anisotropic network where the estimated distance between two sensor nodes (e.g. those located around the circle in opposite directions) tends to be a curved line and generates large errors since it is proportional to the hop-count between them. However, Figure 1(b) shows a connected network (i.e. non-isolated sensor nodes) where approaches like DV-hop, Euclidean-propagation, DV-distance, and their variants can be used for inter-node distances.⁸ Here, for high density and uniform distribution, the estimated distance between two non-neighboring sensors tends to be a straight line. Figure 1(c) depicts an ill-connected network that shows that there are no paths between every pair of sensor nodes (a path is a route that joints two non-neighboring sensors with inter-node wireless connections).

Figure 1.

Multi-hop wireless networks: (a) a connected network with a circular uniform distributed topology. It contains 100 sensors distributed over a 2D square area of 200 m × 200 m. (b) A connected network with uniformly randomly distributed sensor nodes. It contains 100 sensors placed over a 2D square area of 200 m × 200 m. (c) A partial connected network with a uniform distributed topology. It contains 100 sensors distributed over a 2D square area of 200 m × 200 m.

As can be seen, localization algorithms in multi-hop networks are highly dependent on topologies and errors on distance estimates. In view of this problem, some research works have proposed robust schemes that help to reduce errors on distance estimates for multi-hop networks considering irregular topologies.^9–16 For instance, Zheng et al.¹⁶ propose a regularized extreme learning machine method (RELM) for multi-hop localization. This scheme is composed of three stages: training, modeling, and locating the nodes. The method creates a model with inter-node anchor information. Finally, distance estimations between USs and ANs are computed using the network model. Even though this methodology can be suitable to be implemented over irregular network topologies, the model is highly dependent on both the number and the position of the anchors. Also, Akbas et al.¹⁷ presents a methodology to estimate distances between USs and ANs, which is based on the minimum number of hops between a set of stationary ANs and a set of USs floating over a river. This approach requires a manual positioning of the ANs alongside the river, and the radio range of the ANs must be larger than the USs. Another approach to estimate distances between ANs and USs is introduced in Cota-Ruiz et al.¹⁸ This scheme finds out all possible routes with the minimum number of hops between an AN and an US using a recursive shortest path algorithm (RSPA); for each found route, an estimated distance is calculated based on the sum of inter-node RSS measurements, and the final estimate is calculated by averaging all distance routes. The drawback of this approach is the time-computation to calculate all possible routes between two non-neighboring sensors whose complexity increases for dense networks of sensor nodes. Another scheme to estimate distances between two non-neighboring sensor nodes is addressed in Chen et al.¹⁹ This approach, signal similarity-based localization method (SSLM), generates a numerical value that relates the RSS similarity between two neighboring sensors. This process is applied to each pair of connected sensor nodes to finally estimate the distance between ANs and USs using the shortest path routing algorithm.

Commonly, the mathematical formulation of the node placement problem requires to solve a non-linear and non-convex optimization problem, and iterative algorithms must be applied in order to minimize errors on position estimates.^20–24 For instance, in Cota-Ruiz et al.,²⁴ a distributed iterative localization algorithm is used as a refinement stage where each US must compute a local objective function, composed by a constrained set of position estimates equally spaced, in order to minimize the sum of error distances with one-hop neighboring sensors using the l₁-norm. This scheme is suitable to be implemented with resource-limited devices since it is a derivative-free and a low-complexity refinement method.

In this research, we modify the algorithm presented in Cota-Ruiz et al.²⁴ to create a distributed weighted-hop localization (DWHL) algorithm that can be useful as a refinement stage for static multi-hop localization. This scheme uses hops proximity between USs and ANs to improve position estimates. As a result, USs nearer to ANs will have more weight than those located far away from anchors. After initial estimates are solved by USs, they can apply the proposed approach to improve their position estimates. Results show that errors in the initial position estimates (i.e. obtained from approaches like RELM, SSLM, RSPA, DV-hop, and DV-distance) are greatly reduced after using this approach even for anisotropic network topologies.

The rest of the work is organized as follows. Section “The power observation: a common range-based measurement used in wireless sensor network localization” explains the RSS technique. Section “The range-based multi-hop localization” describes the problem formulation in multi-hop network localization. Section “The distributed weighted-hop localization algorithm” details the proposed algorithm. Section “Performance of the proposed localization scheme in multi-hop networks” shows experimental results, and section “Conclusion” concludes the research.

The power observation: a common range-based measurement used in wireless sensor network localization

Even though the RSS technique suffers from fading and shadowing, it is a low-cost and a common method used in range-based WSN localization. The received signal strength indicator (RSSI) technology is a common feature integrated into most wireless devices and does not require special hardware support to estimate a distance between two sensor nodes. The RSS technique uses the concept that the power of a transmitted RF signal diminishes with the distance traveled; and if two sensor nodes are within a detecting range, the signal strength can be measured by an RSSI. As a first approximation, the noise-free case, suppose that at a unit distance $d_{0}$ and a $d$ distance from a transmitter, the signal has a strength $P^{r} (d_{0})$ and $P^{r} (d)$ , respectively. Then using

$P^{r} (d) = \frac{P^{r} (d_{0})}{d^{η_{p}}}$ (1)

the distance $d$ can be deduced from $P^{r} (d)$ if the path loss coefficient $η_{p}$ of the environment is known. Commonly, power measurements are mostly represented in logarithmic scale, then equation (1) is stated as

$P_{dB}^{r} (d) = P_{dB}^{r} (d_{0}) - 10 η_{p} \log_{10} (\frac{d}{d_{0}})$ (2)

However, a more realistic model frequently used for wireless radio propagation is represented by the ideal received power + noise power as follows

${\hat{P}}_{dB}^{r} (d) = P_{dB}^{r} (d) + X_{σ_{SH}}$ (3)

and the noisy measured power ${\hat{P}}_{dB}^{r}$ can be represented in a logarithmic form as

${\hat{P}}_{dB}^{r} (d) = (P_{dB}^{r} (d_{0}) - 10 η_{p} \log_{10} (\frac{d}{d_{0}})) + X_{σ_{SH}}$ (4)

where $X_{σ_{SH}}$ is a log-normal random variable with standard deviation $σ_{SH}$ that accounts for environmental and shadowing effects. As aforementioned, if the $η_{p}$ of the environment is known, the estimated distance $\hat{d}$ can be deduced from equation (4) as

$\hat{d} = d_{0} \cdot 10^{\frac{P_{dB}^{r} (d_{0}) - {\hat{P}}_{dB}^{r} (d)}{10 \cdot η_{p}}}$ (5)

$\hat{d} = d_{0} (10^{\frac{P_{dB}^{r} (d_{0}) - P_{dB}^{r} (d)}{10 \cdot η_{p}}} \cdot 10^{\frac{- X_{σ_{SH}}}{10 \cdot η_{p}}}) = d \cdot e$ (6)

where the error $e$ is directly affected by $X_{σ_{SH}}$ . As can be observed from equation (6), this estimated distance can be expressed in additive form as shown in equation (7) considering $d_{0} = 1 m$

$\hat{d} = d + d (10^{\frac{- X_{σ_{SH}}}{10 \cdot η_{p}}} - 1)$ (7)

The range-based multi-hop localization

Assuming that all sensor nodes have been randomly positioned over a large and inaccessible terrain, have the same circular radio range R, communicate over short distances, and a few of them have been $a priori$ identified (called ANs), the remaining sensor nodes (called USs) can be localized using wireless communications with other sensor nodes.⁵ Also, considering that all sensor nodes are statics and have an integrated hardware to estimate their distances from neighboring sensors, it can be stated that multiple hops between an US and an AN would commonly be presented,⁴ leading to a multi-hop network construction. The performance of a localization process is closely related to three important stages, described below.

Ranging: how to estimate distances between neighboring sensors and non-neighboring sensors (e.g. USs and ANs).

Initial positioning: how to estimate locations of USs given some noisy pairwise distance measurements between USs and ANs and a trilateration method.

Final positioning: how to improve locations of USs given some noisy pairwise distance measurements among one-hop neighboring sensors.

This research limits the discussion to two dimensions. The sensor field is formed by $N$ sensor nodes $S = {s_{1}, s_{2}, \dots, s_{N}}$ , randomly deployed in a 2D area. There is a set of $M$ unknown sensors $P = {p_{1}, p_{2}, \dots, p_{M}}$ with true positions $T = {t_{1}, t_{2}, \dots, t_{M}}$ to be located with position estimates $p_{i} = [x_{i}, y_{i}]^{T}$ and $N - M$ anchor nodes $A = {a_{1}, a_{2}, \dots, a_{N - M}}$ , with reference positions $a_{j} = [x_{j}, y_{j}]^{T}$ that know $a priori$ their locations. Consider the ratio between unknown sensors and anchor nodes as 20:1 or $M > > (N - M)$ . Furthermore, all sensor nodes (i.e. ANs and USs) have the same radio area coverage R, considered circular. Thus, due to the limited range of coverage in each sensor, any sensor $s_{i}$ (or anchor $a_{i}$ ) will have a restricted number of neighboring sensors defined by the set

$α_{i} = {j | d_{ij} < R}$ (8)

where ‖·‖ denotes the Euclidean norm, and $d_{ij} = ‖ t_{i} - t_{j} ‖ = ‖ a_{i} - t_{j} ‖$ is the true distance between the unknown sensor $s_{i}$ (or anchor $a_{i}$ ) and all its neighboring sensors $j$ . If there is a link between two neighboring sensors, we can assume that they can estimate their distances with techniques like the RSS (or any other schemes).⁶ Thus, we can describe

$r_{ij} = d_{ij} + e_{ij} \forall j \in α_{i}$ (9)

as the noisy range measurement between the sensor $s_{i}$ (or anchor $a_{i}$ ) and its neighboring sensor $s_{j}$ , where $e_{ij}$ represents a distance error caused by environmental conditions.⁴ Clearly, partial connectivity among sensor nodes is present, and distance estimates between unknown sensors and anchors might be multiple hops. For range-based localization methods, it is necessary that each unknown sensor knows the estimated distances to at least three non-collinear anchors in order to calculate its own initial location using trilateration or any other localization technique.²⁵ A variety of methods to estimate distances between two non-neighboring sensors are achieved by routing algorithms.^{12,16,18,19,26}

The combination ${network, sensor nodes, links}$ can be represented in a mathematical form as ${G, V, L}$ , respectively, where $G = (V, L)$ is the graph. $V = {v_{1}, v_{2}, \dots, v_{N}}$ represents the set of vertices, and $L$ is the set of edges. Let $L_{i} = {ℓ_{i n_{1}}, ℓ_{i n_{2}}, \dots, ℓ_{i n_{k}}}$ be the set of edges that the vertex $v_{i}$ has to other vertices, and the cardinality of $L_{i}$ is known as the degree of $v_{i}$ . Thus, if an edge $ℓ_{ij}$ joints two vertices $v_{i}$ and $v_{j}$ where both belong to $V$ , then $v_{i}$ is incident with $v_{j}$ and vice versa. In this way, if $ℓ_{ij}$ can be associated with a weight (e.g. the distance $r_{ij}$ ), we can define $R$ as the abutment matrix of the weighted graph. Also, it is common to denote $A$ as the adjacency matrix of $G$ .

A path in a graph (or network) is conformed by linking two non-incident vertices (or non-neighboring sensor nodes) with an alternating sequence of $n$ distinct vertices (or sensor nodes) where consecutive vertices are incident with each other as shown the next equation

$P_{uk} = {ℓ_{s_{0} s_{1}}, ℓ_{s_{1} s_{2}}, ℓ_{s_{2} s_{3}}, \dots, ℓ_{s_{n - 1} s_{n}}}$ (10)

where $s_{0} = s_{u}$ and $s_{n} = a_{k}$ . Clearly, $P_{uk}$ represents a path between the non-incident vertices $v_{u}$ and $v_{k}$ . For unweighted networks, the length of the path corresponds to the number of links (or hops). However, most of the network systems tend to be weighted, and the estimated distance between two non-neighboring sensor nodes is a challenging concept in many applications. Thus, in weighted networks, the elements of the adjacency matrix $A$ take the weight of each link to become $R$ , as before described.

Without loss of generality, consider $R (P_{uk})$ as the noisy estimated distance between two non-neighboring sensors $s_{u}$ and $a_{k}$ (i.e. an unknown sensor and an anchor node, respectively), separated by $n$ hops, where such distance is computed as

$R (P_{uk}) = \overset{n - 1}{\sum_{i = 0}} r_{s_{i} s_{i + 1}}$ (11)

where $s_{0} = s_{u}$ and $s_{n} = a_{k}$ . Here, the estimated distance $R (P_{uk})$ can be obtained from methods as those mentioned in previous works.^{8,12,16,19,27} In case there is not a path between $s_{u}$ and $a_{k}$ , the estimated distance $R (P_{uk})$ is defined as $R (P_{uk}) = \infty$ .

Similarly to equation (8), let us define the set of k anchors with known distances to a sensor $s_{i}$ as follows

$β_{i} = {k | R (P_{ik}) < \infty}$ (12)

Then, to get initial estimates for each unknown sensor in the network $P = {p_{1}, p_{2}, p_{3}, \dots, p_{M}}$ , the next optimization problem (13) must be solved

$min_{\begin{matrix} P \end{matrix}} \sum_{i = 1}^{M} (\sum_{k \in β_{i}} | ‖ p_{i} - a_{k} ‖ - R (P_{ik}) |)$ (13)

which minimizes range estimates between unknown sensors and anchor nodes. Once initial estimates are calculated, a refinement stage can be applied in order to improve position estimates. The mathematical formulation for the refinement stage can be stated as follows

$min_{\begin{matrix} P \end{matrix}} \sum_{i = 1}^{M} (\sum_{j \in α_{i}} | ‖ p_{i} - p_{j} ‖ - r_{ij} |)$ (14)

which minimizes range estimates among one-hop neighboring sensors. Basically, the range-based multi-hop localization problem requires two set of range measurements for each $s_{i} : α_{i}$ and $β_{i}$ , where the set $β_{i}$ is commonly used for initial estimates and the set $α_{i}$ is used in the refinement process. As can be observed, equations (13) and (14) become a non-linear and NP-hard problems,^20,21,24 and iterative optimization algorithms must be employed to minimize errors on position estimates.

The distributed weighted-hop localization algorithm

The non-linear global optimization problem of equation (14) cannot be solved efficiently in a central node for practical situations due the computational complexity and wireless packet requirements to be re-transmitted toward the central sensor node for processing. Instead, this problem is divided and solved in sub-optimization problems (i.e. a divide and conquer scheme) in a distributed way.^20,21,23,28 Thus, once a sensor $s_{i}$ obtains its initial estimate, with a trilateration scheme, it performs a distributed process using equation (14) as follows

The sensor node $s_{i}$ waits to receive position updates from its neighboring sensors $s_{j}, \forall j \in α_{i}$ .

Upon receiving the neighboring sensor packet, the sensor $s_{i}$ updates its own position using a weighted constrained-local search area, and it obtains a new position that minimizes error distances with its neighboring sensors.

The sensor node $s_{i}$ broadcasts its new position estimates to its neighboring sensors.

The last and current position estimates are evaluated with a metric for criterion stopping. If the process continues, it will return to the first step; otherwise, it leaves of transmitting its position. This iterative process is detailed in the next paragraphs.

Given a position estimation $p_{i}$ for a sensor $s_{i}$ , it requires a new search region $A$ in order to reduce error distances with its neighboring sensors $α_{i}$ . The sum of error distances of $s_{i}$ with its neighboring sensors can be stated as

$E (p_{i}) = \sum_{j \in α_{i}} | ‖ p_{i} - p_{j} ‖ - r_{ij} |$ (15)

The scalar value obtained in equation (15) constraints the search region $A$ as shown in Figure 2, where $N_{i}$ is the cardinality of the set $α_{i}$ .

Figure 2.

A constrained-discrete region of unknown sensor $s_{i}$ composed by 25 candidates centered in its current position $p_{i}$ .

As can be observed from Figure 2, the search region area is located in the middle of the actual position $p_{i}$ of the sensor $s_{i}$ , and it is a set of 25 candidates that must be evaluated with the aim of reducing error distances with neighboring sensors. The weighted-local optimization function is described in equation (16)

$min_{p_{i} \in A} (\sum_{j \in α_{i}} | ‖ p_{i} - p_{j} ‖ - r_{ij} | w_{ij})$ (16)

where $w_{ij}$ is a weighted value of the sensor $s_{i}$ regarding to its neighboring sensor $s_{j}$ , and its value can be derived as follows. Let us to consider $H_{i} = {h_{j} | j \in α_{i}}$ , where $h_{j}$ is the minimum number of hops between the sensor $s_{j}$ and its nearest anchor. Thus, $w_{ij}$ can be computed as

$w_{ij} = \frac{max (H_{i}) + 1 - h_{j}}{\sum_{j \in H_{i}} (max (H_{i}) + 1 - h_{j})} \forall h_{j} \in H_{i}$ (17)

To describe graphically the last procedure, Figure 3 shows a small network conformed by three anchor nodes (i.e. red points with letter A) and 13 unknown sensors (i.e. blue points with letter S). Wireless connectivity among sensor nodes is shown with dashed lines, and anchor nodes have the maximum hierarchical level of one. Sensor nodes that are at one-hop of distance of any anchor will receive the next higher priority level of two, and so on; therefore, the unknown sensor $s_{12}$ has the hierarchical level of four since it is far away three hops of the nearest anchor $A_{3}$ . These priority levels can be derived by each sensor node in a distributed way using the well-known DV-hop algorithm.⁸

Figure 3.

Typical network connectivity where the hierarchical levels are assigned to each unknown sensor.

Clearly, n-hops are required to reach the three anchors from any unknown sensor. In Figure 3, if we consider the set vector of neighboring sensors of $s_{6}$ , then $α_{6} = {s_{2}, s_{3}, s_{5}, s_{8}}$ and $H_{i} = {2, 2, 3, 3}$ , respectively, so the weighted-set vector of $s_{6}$ becomes ${w_{62}, w_{63}, w_{65}, w_{68}} = {\frac{2}{6} \frac{2}{6} \frac{1}{6} \frac{1}{6}}$ . Clearly, sensors $s_{2}$ and $s_{3}$ which are nearer to anchors than sensors $s_{5}$ and $s_{8}$ have more weight. In this manner, sensor nodes that have high-priority levels tend to pull sensor nodes with low-priority levels avoiding large errors on initial position estimates.

Performance of the proposed localization scheme in multi-hop networks

As before described, a range-based localization algorithm faces the first challenge problem in how estimate distances between USs and ANs that are commonly separated by several hops; good initial estimates for USs are highly dependent on factors like the network topology, the accuracy of estimated distances between sensor nodes, and the localization algorithm. However, large errors on initial estimates can be present in multi-hop localization. In the next sections, the proposed weighted algorithm is evaluated under two different scenarios: isotropic and anisotropic networks as shown Table 1. The root mean square error (RMSE) evaluates the errors of position estimates. The metric is shown in equation (18)

$RMSE = \sqrt{\frac{1}{N} \overset{N}{\sum_{i = 1}} {‖ p_{i} - t_{i} ‖}^{2}}$ (18)

Here, ‖·‖ is the Euclidean norm, $p_{i}$ and $t_{i}$ represent the position estimation of sensor $s_{i}$ and its true position, respectively; and N is the number of USs in the network. Also, the localization process uses the Levenberg–Marquardt (LM) method described in Cota-Ruiz et al.²⁵ to obtain initial estimates.

Table 1.

Setup of networks to evaluate the accuracy performance of the proposed refinement localization algorithm where the estimation distance between USs and ANs are calculated under different schemes like DV-hop, DV-distance, RELM, RSPA, and SSLM methods.

Topology	Isotropic network		Anisotropic network
Number of networks	10		10
USs:ANs ratio	100:5		100:5
Area deployment	200 m × 200 m		200 m × 200 m
Ranging errors	$σ_{SH} = 1 dB$	$σ_{SH} = 3 dB$	$σ_{SH} = 1 dB$	$σ_{SH} = 3 dB$
Range of sensor nodes (meters)	35, 40, 45	35, 40, 45	35, 40, 45	35, 40, 45

US: unknown sensors; AN: anchor nodes.

To analyze the accuracy performance of the proposed algorithm, 10 different sensor networks are created for each topology as shown in Table 1.

Specific changes in US parameters like varying the size of radio range and the magnitude-error in range measurements are carried out to analyze the performance of the proposed scheme. Each sensor $s_{i}$ computes the sum of error distances with neighboring anchors as

$E (p_{i}) = \sum_{k \in β_{i}} | ‖ p_{i} - a_{k} ‖ - R (P_{ik}) |$ (19)

where $R (P_{ik})$ represents the estimated distance between the sensor $s_{i}$ and the anchor $a_{k}$ obtained by techniques like DV-hop, DV-distance, RELM, SSLM or RSPA. Next, the sensor $s_{i}$ using reference positions $a_{k}$ and range estimates $R (P_{ik})$ for ${k = 1, 2, \dots, (N - M)}$ computes its initial position using a lateralization method (e.g. LM algorithm). As final step and using equation (20), the sensor $s_{i}$ finds a position that minimizes the error distance with its reference positions as

$min_{p_{i} \in A} (\sum_{k \in β_{i}} | ‖ p_{i} - a_{k} ‖ - R (P_{ik}) |)$ (20)

where the size of the searching area $A$ of Figure 2 is calculated using equation (19) and the value $N_{i}$ , the cardinality of $β_{i}$ . The next sections analyze the accuracy performance of the proposed approach under isotropic and anisotropic networks.

Range-based multi-hop localization over randomly and uniformly distributed sensor networks

In this section, we test the proposed DWHL algorithm under different WSN scenarios. In the first part, we create 10 multi-hop networks in MATLAB (2010, ver. 7.10) as shown in Figure 1(b). Each network consists of N = 100 sensor nodes, and each sensor node is considered with a fixed circular radio range R. The sensor nodes are uniformly and randomly distributed over a 200 m × 200 m area, and only 5% of the total deployed sensor nodes acts as reference or ANs. Noisy range measurements among sensors are generated under the RSS technique.^19,24 To calculate the distance estimates between USs and ANs, the next approaches are considered in this research: DV-hop, DV-distance, RSPA, SSLM, and RELM. Also, it is assumed that in all multi-hop networks there is at least one path between any unknown sensor $s_{i}$ to any anchor node $a_{k}$ . Thus, each unknown sensor in the network is able to compute its initial position estimation with a trilateration method (i.e. the LM method in this research).²⁵ Once the initialization stage is achieved, the DWHL refinement algorithm is run in each unknown sensor to improve position estimates.

For each network, five non-collinear anchors are chosen and radio ranges of R = 35 m, R = 40 m, and R = 45 m are programmed in order to generate multi-hop isotropic networks. To generate errors in distance estimates, under the RSS ranging technique,²⁴ it is using an attenuation factor of $η_{p} = 2.6$ with different standard deviations $σ_{SH} = 1 dB$ and $σ_{SH} = 3 dB$ as shown in Table 1.

Figure 4 depicts two important parameters obtained from the 10 isotropic networks. For instance, in the right side of Figure 4, the degree of a node, taken as the average of the 10 networks, is shown at different radio ranges. In a similar way, the left side of the figure shows the hierarchical level of nodes also considering the average of the 10 networks.

Figure 4.

Network parameters, the degree of nodes and the hierarchical level of unknown sensors, are extracted from 10 isotropic networks at different radio ranges.

The right side of Figure 4 highlights that increasing the radio range also increases the degree of each node in the network while the left side of the figure presents an opposite behavior by decreasing the hierarchical level of nodes (i.e. the minimum number of hops to the closest anchor node plus one as is shown in Figure 3). Thus, increasing the radio range of sensor nodes helps the localization process.

In the first test, we consider that both USs and ANs have a radio range of R = 35 m, and distance measurements among neighboring sensors are corrupted according to $σ_{SH} = 1 dB$ . In this way, the 10 multi-hop networks are generated. For each network, USs must estimate distances to ANs using the aforementioned range-based schemes to obtain their initial position estimates using the LM method.²⁵ Next, each unknown sensor $s_{i}$ runs the DWHL algorithm to refine initial estimates during 15 iterations. This procedure is repeated for each one of the 10 multi-hop networks and the average RMSE at each iteration, marked as “ $◇$ ,” is plotted in Figure 5(a).

Figure 5.

Combination of [initial-estimates] + (the refinement algorithm DWHL) at 15 iterations to improve position estimates for unknown sensors distributed over isotropic networks at different radio ranges: (a) R = 35 m (b) R = 40 m (c) R = 45 m. Noisy Distance measurements with Gaussian distribution and 1 dB of standard deviation. Initial-estimates: “♦” = [DV-DISTANCE with LM] + (DWHL), “•” = [DV-HOP with LM] + (DWHL), “▸” = [RELM with LM] + (DWHL), “*” = [RSPA with LM] + (DWHL), “▴” = [SSLM with LM] + (DWHL).

Even though, there are isotropic networks for these experiments, a radio range of R = 35 m increases the number of hops between ANs and USs generating large errors on distance measurements (e.g. affecting initial position estimates). The best accuracy performance is obtained by the combination of DV-distance and DWHL schemes, marked with “♦,” starting with 24.5 m and finishing with 18.9 m of error, respectively. The worst accuracy performance is registered by the combination of RELM and DWHL schemes, marked with “▸,” with initial and final values of 26.7 and 24.1 m, respectively. However, the refinement algorithm presents a good performance reducing initial errors in all cases.

However, as expected, increasing the radio range in each sensor node $s_{i}$ to R = 40 m and R = 45 m produces better initial and final position estimates as depicted Figure 5(b) and (c), respectively, where the best accuracy performance in both cases is provided by the combination of DV-distance and DWHL methods, while the worst case is also presented by the RELM and DWHL approaches; but as mentioned before, DWHL has a great performance reducing initial errors in all cases.

Another interesting analysis consists of increasing errors in range measurements. Keeping both, the position set of unknown sensors and anchors positions for each one of the 10 benchmark networks, the distance estimation errors among neighboring sensors is increased to $σ_{SH} = 3 dB$ instead of $σ_{SH} = 1 dB$ . Thus, for a radio range of R = 35 m, distance estimates between ANs and USs are computed by the methods DV-distance, DV-hop, RELM, RSPA, and SSLM, and initial estimates are calculated in every case using the LM algorithm. For each case, the refinement algorithm is run during 15 iterations, and the average of the 10 benchmark networks are plotted in Figure 6(a). Clearly, initial and final errors on position estimates increase as a consequence of also increasing error distances among neighboring sensors when compared with Figure 5(a), and a similar behavior is exhibited by the combination of DV-distance with DWHL showing the best performance, and RELM with DWHL methods ending up with the worst performance. Finally, as expected in uniform and randomly distributed WSNs, increasing the radio range in each sensor node $s_{i}$ to R = 40 m and R = 45 m produces better initial and final position estimates as reveled by Figure 5(b) and (c), respectively.

Figure 6.

Combination of [initial-estimates] + (the refinement algorithm DWHL) at 15 iterations to improve position estimates for unknown sensors distributed over isotropic networks at different radio ranges: (a) R = 35 m (b) R = 40 m (c) R = 45 m. Noisy Distance measurements with Gaussian distribution and $3 dB$ of standard deviation. Initial-estimates: “♦” = [DV-DISTANCE with LM] + (DWHL), “•” = [DV-HOP with LM] + (DWHL), “▸” = [RELM with LM] + (DWHL), “*” = [RSPA with LM] + (DWHL), “▴” = [SSLM with LM] + (DWHL).

Comparing initialization stages between Figures 5(a) and 6(a), 5(b) and 6(b), and 5(c) and 6(c), we can observe that methods based in the hop-count to estimate distances among non-neighboring sensors like the DV-hop and the RELM approaches produce similar initial estimates in both cases. The reason is that these schemes do not depend on errors in distance measurements; they use the average-hop between anchor positions. Conversely, range-based distance schemes like RSPA, SSLM, and DV-distance are highly dependent on the accuracy in distance estimates. Whatever the case, in the refinement stage, the DWHL algorithm achieves to decrease the RMSE in all tests.

Evidently, the DV-distance in combination with the proposed algorithm provides the best accuracy performance than the other schemes, and better results are obtained by increasing the radio range of sensor nodes. This combination can be implemented in a distributed way with a low complexity and computational cost. However, the RELM approach in combination with the proposed algorithm indicates the worst accuracy performance under this type of network distribution. However, the RELM method is suitable to be implemented over irregular network topologies as those analyzed in the next section.

Range-based multi-hop localization over irregular topologies of sensor networks

This section analyzes the accuracy performance of the proposed DWHL scheme under anisotropic networks. We consider that all deployed networks are of the form of these ones presented in Figure 1(a), where there is a path between every pair of nodes, and five of the 100 sensor nodes are anchors distributed around the circle. The tests for this section run also of the same form as the described in last section “Range-based multi-hop localization over randomly and uniformly distributed sensor networks,” where 10 anisotropic networks with noisy range measurements among neighboring sensors are created. Figure 7 shows two important parameters of the evaluated anisotropic networks: the degree of nodes and the hierarchical level of unknown sensors.

Figure 7.

Network parameters, the degree of nodes and the closeness to anchor nodes, are extracted from 10 circular-shape networks at different radio ranges.

Similar to isotropic networks, the concentration of neighboring nodes per sensor, considering the same deployed area and the same number of sensor nodes, increases accordingly with the increment of the radio range and the hierarchical level also decreases. However, an important behavior must be taken into account for this kind of circular-shape topology; the degree of nodes is bigger than the isotropic one since most unknown sensors are concentrated in small area around the boundary of the circle.

The first test consists of evaluating the accuracy performance of the proposed refinement DWHL algorithm at different initial estimates. Initial estimates are computed using the range-based schemes (i.e. RELM, RSPA, SSLM, DV-hop, and DV-distance) to estimate distances between USs and ANs; and the method LM provides the initial position estimate for each US. Ranging error among neighboring sensors, with the RSS technique, is $σ_{SH} = 1 dB$ .²⁴ Thus, the initialization stage (i.e. range-based method and LM scheme) followed by the refinement algorithm (i.e. the DWHL algorithm at 15 iterations) is applied for each one of the 10 networks and the average is taken as the estimator. This procedure is repeated for R = 35 m, R = 40 m, and R = 45 m. Figure 8(a) shows results with R = 35 m. Clearly, algorithms based on hops like RELM and DV-hop present better initial estimates (i.e. 27.1 and 23.3 m, respectively) over range-based approaches like RSPA, SSLM, and DV-distance schemes (i.e. 58.9, 54.9, and 49 m, respectively) when irregular network topologies are considered. In average, the refinement algorithm brings off better results for range-based methods than hop-based methods. However, the best accuracy performance results of the combination DV-hop and DWHL approaches.

Figure 8.

Combination of [initial-estimates] + (the refinement algorithm DWHL) at 15 iterations to improve position estimates for unknown sensors distributed over anisotropic networks at different radio ranges: (a) R = 35 m (b) R = 40 m (c) R = 45 m. Noisy Distance measurements with Gaussian distribution and 1 dB of standard deviation. Initial-estimates: “♦” = [DV-DISTANCE with LM] + (DWHL), “•” = [DV-HOP with LM] + (DWHL), “▸” = [RELM with LM] + (DWHL), “*” = [RSPA with LM] + (DWHL), “▴” = [SSLM with LM] + (DWHL).

Figure 8(b) shows accuracy results on position estimates when the radio range of every sensor node is increased to R = 40 m. In this case, only the range-based schemes improve their initial position estimates as expected. However, the combination DV-hop with DWHL still provides the best accuracy results over these irregular topologies. This starts at 22.5 m of error and finishes with 17.4 m of error. Also, it can be seen that the refinement algorithm achieves a substantial error reduction in all cases, least with the RELM approach, which practically remains with the same error (i.e. around 28 m) after 15 iterations. Finally, using a radio range of R = 45 m in all sensor nodes, the position estimates are improved in all cases as depicted Figure 8(c). However, it must be remarked that the refinement algorithm provides the best improvement on reducing position errors when the DV-hop scheme is used as initialization stage reaching a final RMSE of 12.6 m. Then, even though the RELM method is aimed to be used over irregular topologies, the proposed scheme achieves better results in combination with the others initialization stages.

However, increasing errors on distance estimates among neighboring sensors over the 10 benchmark networks to $σ_{SH} = 3 dB$ seems that position estimates also would increase the error. Nevertheless, it has the opposite effect as shown Figure 9.

Figure 9.

Combination of [initial-estimates] + (the refinement algorithm DWHL) at 15 iterations to improve position estimates for unknown sensors distributed over anisotropic networks at different radio ranges: (a) R = 35 m (b) R = 40 m (c) R = 45 m. Noisy Distance measurements with Gaussian distribution and 3 dB of standard deviation. Initial-estimates: “♦” = [DV-DISTANCE with LM] + (DWHL), “•” = [DV-HOP with LM] + (DWHL), “▸” = [RELM with LM] + (DWHL), “*” = [RSPA with LM] + (DWHL), “▴” = [SSLM with LM] + (DWHL).

For instance, for R = 35 m of Figure 9(a), initialization stages present an error of 28.7 m in average, while for R = 35 m of Figure 8(a), initialization stages yield an error of 42.6 m in average. Also, final position estimates of Figure 9(a) yield an error of 19.9 m in average, and final position estimates of Figure 8(a) provide an error of 25.4 m in average. Similar behaviors are presented when the radio range of sensor nodes is increased to R = 40 m and R = 45 m as depicted Figure 9(b) and (c), respectively. As expected, the proposed weighted localization algorithm has the capacity to provide low errors on position estimates in a distributed manner with a low computational cost, and it has the ability to be implemented in a sensor node with low computational capabilities. Moreover, it can be used as a refinement stage after simple and easily implementable schemes like DV-hop or DV-distance schemes.

As final test, the proposed algorithm is analyzed with random initial positions for each unknown sensor. For each unknown sensor, it is defined a circular area with radio range R and centered at the true position. Then, a random position is generated inside of it, which is used as an initial estimate. Once all unknown sensors have initial random estimates, the DWHL algorithm is performed at 15 iterations in a distributed way to improve position estimates. The process, the initial random estimates and refinement stages, is recreated 10 times for each one of the 10 benchmark networks to finally be averaged. Also, to test robustness and accuracy of the proposed approach under rough initial estimates, the circular area is increased according to $CA = κ \cdot R$ , where $κ = 1, 2, \dots, 6$ .

In the case of the 10 isotropic networks with $σ_{SH} = 1 dB$ (i.e. the error introduced in distance measurements among neighboring sensors). Figure 10 shows the error in the position estimates using the RMSE metric at different radio ranges and initial estimates. Figure 10(a) depicts how initial estimates increase in average 20 m when the CA increases by R = 35 m. Thus, for a CA = 6·R = 210 m, the process generates an initial RMSE of 121 m and a final RMSE of 27.2 m after 15 iterations, which is lower than the radio range of sensor nodes. Moreover, Figure 10(b) and (c) shows a similar behavior for R = 40 m and R = 45 m when increasing the CA, used to generate random initial estimates; however, even when there are high errors on initial estimates, the final RMSE values are lower than the former ones since the hierarchical level of nodes decreases and the degree of nodes increases when R increases as shown Figure 4, which helps to the refinement algorithm to reduce errors on position estimates.

Figure 10.

RMSE behavior of the proposed algorithm (DWHL) with 15 iterations at different initial estimates [random values inside of a circle area] using radio ranges of (a) R = 35 m, (b) R = 40 m and (c) R = 45 m. “♦” = [CA = R] + (DWHL), “•” = [CA = 2 ·R]+ (DWHL), “▸” = [CA = 3 ·R] + (DWHL), “*” = [CA = 4 ·R] + (DWHL), “▴” = [CA = 5 ·R] + (DWHL), “+” = [CA = 6 ·R]+ (DWHL). All distance estimates among sensor nodes consider a standard deviation $σ_{SH} = 1 dB$ of error and sensor nodes have an isotropic distribution.

In addition, the DWHL algorithm is tested with the same set of the 10 isotropic networks, but now using a $σ_{SH} = 3 dB$ . As can be observed in Figure 11, RMSE results are very similar to the last one using $σ_{SH} = 1 dB$ , but due to higher errors on distance estimates, the proposed method produces, in general, slightly higher RMSE values than the previous one. However, in all cases, the RMSE value is lower than the radio range of sensor nodes.

Figure 11.

RMSE behavior of the proposed algorithm (DWHL) with 15 iterations at different initial estimates [random values inside of a circle area] using radio ranges of (a) R = 35 m, (b) R = 40 m and (c) R = 45 m. “◆” = [CA = R] + (DWHL), “•” = [CA = 2 ·R]+ (DWHL), “▶” = [CA = 3 ·R] + (DWHL), “*” = [CA = 4 ·R] + (DWHL), “▲” = [CA = 5 ·R] + (DWHL), “+” = [CA = 6 ·R]+ (DWHL). All distance estimates among sensor nodes consider a standard deviation $σ_{SH} = 3 dB$ of error and sensor nodes have an isotropic distribution.

Figure 12 shows the accuracy performance of the DWHL algorithm using the set of the 10 anisotropic networks, described at the beginning of this section, with $σ_{SH} = 1 dB$ . In spite of the irregular network topologies, RMSE results do not show a drawback of this topology with respect to isotropic networks depicted in Figure 10. Moreover, when sensor nodes have a radio range of R = 35 m, accuracy on position estimates from irregular topologies achieves better results than isotropic networks. However, increasing $σ_{SH}$ from 1 to 3 dB over the same set of the 10 anisotropic networks, the position error estimates also increase as can be visualized in Figure 13; however, even in the worst scenario with $σ_{SH} = 3 dB$ , R = 35 m, and an initial estimate of 121.5 m, observed in Figure 13(a), the final RMSE after 15 iterations yields a high error reduction reaching a value of 27.5 m, lower than the radio range R.

Figure 12.

RMSE behavior of the proposed algorithm (DWHL) with 15 iterations at different initial estimates [random values inside of a circle area] using radio ranges of (a) R = 35 m, (b) R = 40 m and (c) R = 45 m. “◆” = [CA = R] + (DWHL), “•” = [CA = 2 ·R]+ (DWHL), “▶” = [CA = 3 ·R] + (DWHL), “*” = [CA = 4 ·R] + (DWHL), “▲” = [CA = 5 ·R] + (DWHL), “+” = [CA = 6 ·R]+ (DWHL). All distance estimates among sensor nodes consider a standard deviation $σ_{SH} = 1 dB$ of error and sensor nodes have a circular-shape distribution.

Figure 13.

RMSE behavior of the proposed algorithm (DWHL) with 15 iterations at different initial estimates [random values inside of a circle area] using radio ranges of (a) R = 35 m, (b) R = 40 m and (c) R = 45 m. “◆” = [CA = R] + (DWHL), “•” = [CA = 2 ·R]+ (DWHL), “▶” = [CA = 3 ·R] + (DWHL), “*” = [CA = 4 ·R] + (DWHL), “▲” = [CA = 5 ·R] + (DWHL), “+” = [CA = 6 ·R]+ (DWHL). All distance estimates among sensor nodes consider a standard deviation $σ_{SH} = 3 dB$ of error and sensor nodes have a circular-shape distribution.

Although the topologies are irregular, the estimating positions after 15 iterations show similar accuracy results from those ones obtained with regular topologies at different radio ranges, which indicates that the proposed approach is not sensitive of the network topology; however, it must be remarked that anchor nodes are uniformly randomly distributed in each network. As expected, initial position estimates yield very similar results for both regular and irregular network topologies at any radio range since initial estimates do not depend on neither the topology nor error distances between sensor nodes.

As can be observed from Figures 10 –13, for connected networks with regular or irregular distribution of sensor nodes, the proposed localization scheme would represent a good option when an accurate distributed node localization algorithm with low computational complexity should be a priority. As final remark, it is important to observe how the refinement algorithm only requires around five iterations, in average, to reach the lowest RMSE value for any test, which shows that the speed of convergence can be suitable in distributed iterative localization algorithms.

Conclusion

In this research, we propose a weighted method useful for localization in static multi-hop networks. The proposed scheme represents an improvement of that presented in Cota-Ruiz et al.²⁴ This approach introduces spatial locations and local functions to minimize errors of distance estimates among neighboring sensors using a weighted-hop function. To test the accuracy performance of the proposed algorithm, initial estimates are generated in a variety of forms like random values inside of a circular area or by classical methods as RELM, RSPA, SSLM, DV-hop, and DV-distance algorithms in combination with the LM method. The improvement if initial position estimates is carried out iteratively by the weighted-hop localization algorithm. Localization tests realized over multi-hop isotropic and anisotropic networks demonstrate that the proposed approach, in combination with range-based or hop-based methods, can provide sufficient accuracy in position estimates with low-complexity computation to be considered in most location-dependent applications. Moreover, given rough initial estimates, the proposed algorithm is able to reduce high errors less than the radio range of sensor nodes with a few iterations. Also, the accuracy performance of the proposed algorithm does not show dependence with the network topology; however, we must remark that anchor positions also play an important role in the accuracy performance of the proposed scheme.

Footnotes

Handling Editor: Christos Anagnostopoulos

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research,authorship,and/or publication of this article.

Funding

The author(s) received no financial support for the research,authorship,and/or publication of this article.

ORCID iD

Juan Cota-Ruiz

References

Nagireddy

Parwekar

A survey on range-based and range-free localization techniques. Int J Innov Adv Comput Sci 2017; 6(11): 2181–2191.

Harsimran

Rohit

. Review on localization techniques in wireless sensor networks. Int J Comput Appl 2015; 116(2): 4–7.

Zhu

Wei

Localization algorithm for large-scale wireless sensor networks based on FCMTSR-support vector machine. Int J Distrib Sens N 2016; 12(10): 1550147716674010.

Tomic

Beko

Dinis

Distributed RSS-based localization in wireless sensor networks based on second-order cone programming. Sensors 2014; 14(10): 18410–18432.

Ilçi

Çizmeci

Alkan

et al . RSS-based indoor positioning with weighted iterative nonlinear least square algorithm. ICWMC 2016; 2016: 117.

Rappaport

TS.

Wireless communications: principles and practice. 2nd ed. Upper Saddle River, NJ: Prentice Hall PTR, 1996.

Wang

Cheng

Han

et al . RSS localization algorithm based on nonline of sight identification for wireless sensor network. Int J Distrib Sens N 2014; 10(7): 213198.

Niculescu

Nath

DV based positioning in ad hoc networks. Telecommun Syst 2003; 22(1–4): 267–280.

Kaur

Kumar

Gupta

. A novel DV-hop algorithm based on Gauss-Newton method. In: Proceedings of the IEEE fourth international conference on parallel, distributed and grid computing (PDGC), Waknaghat, India, 22–24 December 2016, pp.625–629. New York: IEEE.

10.

Cheng

Lui

Tam

. Hybrid approach for localization in anisotropic sensor networks. In: Proceedings of the IEEE 63rd vehicular technology conference, Melbourne, VIC, Australia, 7–10 May 2006, Vol. 1, pp.344–348. New York: IEEE.

11.

Lim

Hou

. Localization for anisotropic sensor networks. In: Proceedings of the IEEE 24th annual joint conference of the IEEE computer and communications societies, Miami, FL, 13–17 March 2005, Vol. 1, pp.138–149. New York: IEEE.

12.

Fan

Chen

Wang

et al . Removing heavily curved path: improved DV-hop localization in anisotropic sensor networks. In: Proceedings of the IEEE seventh international conference on mobile ad-hoc and sensor networks (MSN), Beijing, China, 16–18 December 2011, pp.75–82. New York: IEEE.

13.

Shang

Ruml

Improved MDS-based localization. In: Proceedings of the IEEE INFOCOM, Hong Kong, China, 7–11 March 2004, Vol. 4, pp.2640–2651. New York: IEEE.

14.

Shang

Ruml

Zhang

et al . Localization from mere connectivity. In: Proceedings of the 4th ACM international symposium on mobile ad hoc networking & computing, Annapolis, MD, 1–3 June 2003, pp.201–212. New York: ACM.

15.

Ahmed

Shi

Shang

SHARP: a new approach to relative localization in wireless sensor networks. In: Proceedings of the IEEE international conference on distributed computing systems workshops, Columbus, OH, 6–10 June 2005, pp.892–898. New York: IEEE.

16.

Zheng

Yan

Zhao

et al . A large-scale multi-hop localization algorithm based on regularized extreme learning for wireless networks. Sensors 2017; 17(12): 2959.

17.

Akbas

Brust

Turgut

. Local positioning for environmental monitoring in wireless sensor and actor networks. In: Proceedings of the IEEE 35th conference on local computer networks (LCN), Denver, CO, 10–14 October 2010, pp.806–813. New York: IEEE.

18.

Cota-Ruiz

Rivas-Perea

Sifuentes

et al . A recursive shortest path routing algorithm with application for wireless sensor network localization. IEEE Sens J 2016; 16(11): 4631–4637.

19.

Chen

Gao

et al . SSL: signal similarity-based localization for ocean sensor networks. Sensors 2015; 15(11): 29702–29720.

20.

Biswas

Liang

Toh

et al . Semidefinite programming approaches for sensor network localization with noisy distance measurements. IEEE T Autom Sci Eng 2006; 3(4): 360–371.

21.

Nie

Sum of squares method for sensor network localization. Comput Optim Appl 2009; 43(2): 151–179.

22.

Tomic

Beko

Dinis

et al . Distributed RSS-based localization in wireless sensor networks using convex relaxation. In: Proceedings of the IEEE international conference on computing, networking and communications (ICNC), Honolulu, HI, 3–6 February 2014, pp.853–857. New York: IEEE.

23.

Hendrickson

The molecule problem: exploiting structure in global optimization. SIAM J Optim 1995; 5(4): 835–857.

24.

Cota-Ruiz

Rosiles

Rivas-Perea

et al . A distributed localization algorithm for wireless sensor networks based on the solutions of spatially-constrained local problems. IEEE Sens J 2013; 13(6): 2181–2191.

25.

Cota-Ruiz

Rosiles

Sifuentes

et al . A low-complexity geometric bilateration method for localization in wireless sensor networks and its comparison with least-squares methods. Sensors 2012; 12(1): 839–862.

26.

Dijkstra

EW.

A note on two problems in connexion with graphs. Numer Math 1959; 1(1): 269–271.

27.

Zhang

Xie

Zhao

XJ.

Improved DV-hop localization algorithm for wireless sensor networks. J Comput Appl 2007; 27(11): 2672–2674.

28.

Aspnes

Eren

Goldenberg

et al . A theory of network localization. IEEE T Mobile Comput 2006; 5(12): 1663–1678.