1 Introduction

Wireless sensor networks (WSN) usually consist of a great number of randomly deployed nodes that communicate among themselves and gather information about the environment. In many applications, it is required to know the geographical location of the sensor which detected an event. Location information about sensor node is needed to identify the location of an event, since such information without geographical location is usually useless. Localization problem can be formulated in the following way. Given a small set of “location aware” sensor nodes (called anchors), calculate, as accurate as possible, the location of the node which detected an event.

Localization problem presents a great challenge due to limited resources (power and computation capability) of sensor nodes. WSN application examples that make use of the node position are target tracking [1], smart home applications [2], medical care [3, 4], position based routing [5], and others. The easiest way to determine node location is by using global positioning system (GPS). Manual localization requires human interaction, whereas GPS localization is done with the help of satellites. The limitations of GPS are that it cannot be implemented in dense areas (e.g., forests, mountains) where obstacles block the line-of-sight from GPS satellites. Due to the large number of nodes, limited energy and inaccuracy in indoor environment it is too expensive to be used in large scale WSN. All these factors limit the localization algorithm which is used to determine nodes position in the network.

Interest in WSN localization has increased in recent years and many algorithms are developed on this topic. The existing localization algorithms can be classified into two categories, range-free [6, 7] and range-based [8, 9], based on whether it is required to measure the actual distances between the nodes or the distance is approximated based on the connectivity information.

Range based localization utilizes distance estimation, angle information or received signal strength obtained by measuring techniques. The accuracy of such estimation is subject to the transmission medium, surrounding environment and usually relies on a complex hardware [9]. The range-based algorithms use trilateration to determine the location of the unknown node. Some well-known range-based algorithms are: received signal strength indicator [10] (RSSI), time of arrival [11] (ToA), angle of arrival [12] (AoA) and time difference on arrival [13, 14] (TDoA).

ToA measures the distance between nodes using the signal propagation time. In TDoA the inter-node distance is determined based on the difference in propagation times of radio and acoustic signals originated at the same point. AoA technique locates the position by estimating and mapping relative angles between neighbors using omni-directional antenna. Array of RF antennas at receiver node helps in determining AoA.

Range-free localization algorithms are based on the connectivity information of the nodes. A limited number of nodes, called anchors, have geographical location information since they are equipped with GPS. In such way, they provide a means for other nodes to position themselves based on the connectivity information with the anchor nodes. Anchors broadcast their location into the network, and other nodes can estimate self-position based on the hop counts from the anchors. The approximation of distance is critical in this method and it requires a dense and uniform network to be accurate. The higher the hop count and irregularity of the network, the higher the estimated distance error and thus the localization error. One of the most well-known range-free algorithms is DV-Hop [15].

The problem of range-free localization is further complicated by the diverse types of environments, where a WSN can be deployed. Outdoor, real deployment environments usually do not resemble typical lab environments. Hence, issues like calibration, mobility (if nodes are “moved” by the environment or the WSN is designed to be mobile), and the lack of line-of-sight, the existence of obstructions and multipath effects often arise in realistic, outdoor environments. An extensive survey of localization algorithms is given in [16].

The main contribution of this paper are three new improvements of DV-Hop algorithm, that improve localization accuracy by lowering localization error in various scenarios.

First algorithm, designated as iDV-Hop1 [17], is an add-on of additional steps to the original DV-Hop algorithm for the purpose of the localization error reduction. These additional steps consist of forming three reference points by choosing the nearest anchor node to the unknown node and solving circle-circle intersection equation. Coordinates of unknown node are taken as weight point of triangle that these three points form. Simulation results show that iDV-Hop can reduce localization error by up to 50 % compared to DV-Hop, when communication range and number of anchors are considered as parameter.

The second algorithm, named iDV-Hop2, is a modification of the previous one. Instead of using anchor location as the third reference point, the coordinates obtained by the original DV-Hop are used. Simulation results shown that iDV-Hop2 algorithm has up to three times lower localization error compared to DV-Hop.

Using the third algorithm, designated as Quad DV-Hop, a different approach is used to determine the unknown node location. In this algorithm node location is estimated by solving the bounded least squares problem. Simulations show that Quad DV-Hop improves localization accuracy compared to the original DV-Hop in all scenarios (in irregular types of topology for more than two times) at the cost of higher computational complexity.

To validate performances of our algorithms, four different types of network topologies are considered, gridy (i.e. it looks like grid topology, thus the term ‘gridy’), C shaped gridy, random uniform and C shaped random uniform placement.

The rest of the paper is organized as follows. In the Sect. 2, literature review is given. Section 3 describes the original DV-Hop algorithm followed by the algorithms proposed in this article. Before concluding remarks, simulation results and discussion are given in the Sect. 5 for each topology separately.

2 Literature review

This section presents related work focusing on the state of the art range-free algorithms related to the DV-Hop algorithm.

The original DV-Hop localization scheme proposed by Niculescu and Nath [15] is similar to the traditional routing schemes based on the distance vector. Each node first counts the minimum hop number to the anchor node and then computes the distance between the node and the anchor node by multiplying minimum hop number and average distance of each hop. The node estimates its position using triangulation algorithm or maximum likelihood estimators (MLE) [18, 19]. Numerous improvements of DV-Hop were proposed, such as [17, 20–22] etc. to lower localization error.

He et al. proposed an approximate point-in triangulation test (APIT) algorithm in [7]. Using three anchors, APIT employs area-based method to estimate node position. First, anchor nodes broadcast their information through the network, containing node ID, location and signal strength. Unknown nodes receive this information and exchange them with neighboring nodes. Second, the unknown nodes use approximate point in triangle test method to determine whether is inside or outside the triangle formed by three anchors. In triangle test method, a node chooses three anchors from which beacon information was first received and tests whether it is inside the triangle formed by connecting these three anchors. APIT repeats this point-in-triangulation test (PIT) with different anchor combinations until all combinations are exhausted or the required accuracy is achieved. At this point, APIT calculates the center of gravity (COG) of the intersection of all of the triangles in which a node resides to determine its estimated position. The accuracy of APIT algorithm largely depends on the average number of neighbor nodes.

Amorphous algorithm is similar to the DV-Hop, but it assumes that the network density is known in advance, and uses offline hop-distance estimations [23]. It proposed a generation of a relatively accurate coordinate system on distributed processors via local information. The hop distance can be calculated according to Kleinrock and Silvester formula [24]. Each node obtains the hop distance to anchors trough beacon propagation. Unknown node collects neighboring nodes hop distances and computes an average off all its neighbors’ values. After obtaining the estimated distances to three anchors, triangulation is used to estimate a node’s location.

Centroid algorithm is a simple range-free localization algorithm [25]. The node receives signals from anchors in its communication area and makes its coordinates as the centroid of anchors coordinates. Additional devices for localization are not required in this algorithm. Therefore, the hardware of the nodes can be simple. Centroid, as well as, DV-Hop, Amorphous, and APIT, is distributed algorithms.

Based on the properties of the DV-Hop, an improved scheme was proposed by Chen et al. [26]. Main proposed principle is to estimate distance of the hops according to the number of the neighbors in the same “block”. To reduce the localization error, it uses weighted node distances to compute the node’s final coordinates.

Yi et al. put forward an improved positioning algorithm based on the DV-Hop algorithm [27]. It features a differential error correction scheme, in which average per hop distance of the position network and modified value of distance error are introduced to reduce cumulative distance error and node location error accumulated over the multiple hops. The main drawback of this algorithm is high computation and communication overhead.

In [28] range-free localization scheme was proposed based on bilateration. This paper represents a low cost solution that uses only two anchor nodes and bilateration to estimate nodes position. Two anchors are deployed in the network corners, bottom left and bottom right. It is assumed that the network is squared shaped. This study was compared with DV-Hop and it is shown that outperforms it.

Ruiz et al. [29] uses distance estimates to anchors to solve a set of circle–circle intersection (CCI) problems. The resulting CCIs are processed to pick those that cluster together and then take the average to produce an initial node location. Results shown that the proposed algorithm is competitive compared with optimized localization algorithms.

Kumar in [21] proposed improved versions of DV-Hop designated as QDV-Hop and UDV-hop. The improvements are focused on the third step of DV-Hop. The communication range of each node in the network is not based on unit disk graph (UDG) (a standard circle), it is an irregular pattern. This is justified because it is not possible to obtain UDG model in the real environment due to the noise. The difference between the estimated and true distance is called ranging error. This leads to error in estimating the distance between the unknown node and the anchor node, calculated by hop-size and number of hops that affects the localization accuracy of DV-Hop algorithm. Error in estimating distance is also associated with the influence of network topology. In QDV-Hop algorithm, first error terms (correction factor in estimated distances) are separated from estimated distances between the unknown node and anchor nodes and then the effect of these error terms are minimized by using quadratic programming to obtain better localization accuracy. UDV-Hop is based on solving unconstrained optimization problem that results in solving a system of linear equations without significant increase in computational complexity. Simulation results showed that both of proposed methods are superior compared to DV-Hop.

In [20], an improved DV-Hop scheme (named NDV-Hop_Bon) is proposed. The main idea is to select a certain number of anchor nodes, instead of all. Due to the selection of the anchor nodes which are on a short distance, this new localization algorithm achieves a minimum positioning error by selecting the number of optimal anchor nodes. The performance evaluation is conducted on a medium scale WSN. It still has the limitation depending on the application. When the anchor node’s energy is too low, the positioning accuracy cannot meet the requirements. Communication cost is increased due to additional computation of the optimal number of anchor nodes.

In [30], another improvement of the DV-Hop is presented. It focuses on the correction of the hop-size. After calculating the hop-size, anchor node broadcasts it to the network with correction. Corrected hop-size is average of all anchor nodes hop-sizes. Instead of using the traditional triangulation, 2-D Hyperbolic localization algorithm is implemented for calculating the final position of the node. Simulation results showed that new algorithm can improve accuracy, but with less coverage.

In [22] a localization algorithm is proposed based on shuffled frog leaping algorithm (SFLA) and particle swarm optimization (PSO). SFLA is used to calculate the average distance per hop, then the location of unknown node is formulated as optimization problem and PSO is used to calculate unknown position. It is shown by simulation that proposed algorithm can improve location accuracy compared to DV-Hop algorithm. In the following section, description of original DV-Hop algorithm proposed by Niculescu and Nath [15] is given.

Ojha et al. [31] presents a three-dimensional distributed scheme for mobile underwater WSNs (MUSNs) named as mobility assisted localization scheme (MobiL). MobiL requires only three anchor nodes capable of providing the initial location beacon and all other nodes are ordinary sensor nodes. The spatially correlated mobility pattern of UWSNs is exploited and applied to localize the sensor nodes. The ‘silent’ listening of beacon messages, which enables MobiL to be energy-efficient. Simulations in NS-3 show that MobiL successfully localizes nearly 90 % of the total sensor nodes with localization error in the order of 25–30 % of the error threshold in highly mobile UWSNs.

Han et al. [32] exploits mobility of anchor nodes, three model of movement are used: random waypoint (RWP), random direction (RD) and reference point group mobility (RPGM). The three novel localization models are respectively added with three different mobility models. Localization performance of the DV-hop localization algorithm and these models are analyzed and the impact of mobility on DV-hop also is discussed. Performances in a static WSN are compared with localization performances in mobile WSN (MWSN). DV-hop + RD has higher accuracy, lower energy consumption and relatively higher localization success. DV-hop + RWP, performs a little better than DV-hop + RD when the number of unknown nodes and anchor nodes increases. Results show that the performance of DV-hop algorithm are greatly affected in terms of localization error reduction by mobility models.

In [33] Gui et al. presents two improved algorithms Checkout DV-hop and Selective 3-Anchor DV-hop. Checkout DV-hop algorithm estimates the mobile node position by utilizing the nearest anchor, while Selective 3-Anchor DV-hop algorithm chooses the best 3 anchors to improve localization accuracy. A novel DV-hop localization protocol is presented in detail, including the format of data payloads, the improved collision reduction method E-CSMA/CA, as well as parameters used in deciding the end of each DV-hop step. Performances of typical DV-hop algorithm and proposed improved algorithms are compared in terms of localization accuracy, mobility, synchronization and overhead. Simulation results prove that Selective 3-Anchor DV-hop algorithm offers the best performance compared to Checkout DV-hop and the original DV-hop algorithm.

3 Original dv-hop localization algorithm

One of the best-known range-free localization algorithms, DV-Hop algorithm, consists of the following three steps:

  1. (1)

    Each anchor node broadcasts packet with its location using flooding and hop count value initialized to 1. Each node that receives packet maintains a table for every anchor containing anchors locations and minimum number of hops. If a received packet has lower value of hops to particular anchor than current, a table is updated with this value and the packet is forwarded to network with hop count increased by one. Otherwise the packet is discarded. In such way all nodes obtain minimum number of hops to anchor nodes.

  2. (2)

    The average single hop distance is estimated to convert hop count value into physical distance. For the anchor node with \((x_{i}, y_{i})\) coordinates, the average distance per hop is estimated by the following equation:

    $$\begin{aligned} \hbox {HopSize}_i =\frac{\sum {\sqrt{{(x_i -x_j )}^{2} +{( y_i -y_j )}^{2}}} }{\sum h_{ij}}\left( {i\ne j} \right) , \end{aligned}$$
    (1)

    where \((x_{j}, y_{j})\), is the location of the anchor \(j\), \(\hbox {h}_{ij}\) is the number of hops between the anchor node \(i\) and the anchor node \(j\). Once calculated, the estimated HopSize\(_{i}\) information is broadcasted into the network.

  3. (3)

    The unknown node location can be estimated by the multilateration method when unknown nodes have the distance estimations to at least three anchors. Given a set of reference nodes \(\hbox {N}_{i}\, (x_{i}, y_{i}), i = 1{\ldots } \hbox {n}\), where n is the number of anchors, let the hop value between the unknown node X (x, y), and the i-th anchor is \(\hbox {K}_{i}\). Then the distance between the unknown node and i-th anchor node is given by \(\hbox {d}_{i }= K_{i} \times \, \hbox {HopSize}_{i}\). The unknown node distance estimation from anchor nodes is given by:

    $$\begin{aligned} \left\{ {{\begin{array}{c} {{\left( { x_1 -x} \right) }^{2} +{\left( {y_1 -y} \right) }^{2} =d_1^{2} } \\ {{\left( {x_{2} -x} \right) }^{2} +{\left( { y_{2} -y} \right) }^{2} = d_{2}^{2} } \\ {...} \\ {{\left( {x_n -x} \right) }^{2} +{\left( {y_n -y} \right) }^{2} =d_n^{2} }. \\ \end{array} }} \right. \end{aligned}$$
    (2)

Equation (2) can be written in matrix form AX = b by subtracting the last equation from previous n\(-\)1:

$$\begin{aligned} \hbox {A}= & {} \left[ {{\begin{array}{rl} {2\left( {x_1 -x_n } \right) }&{} {2\left( {y_1 -y_n } \right) } \\ {2\left( { x_2 - x_n } \right) }&{} {2\left( { y_2 - y_n } \right) } \\ {...}&{}{...} \\ {2\left( { x_{n-1} - x_n } \right) }&{} {2\left( { y_{n-1} - y_n } \right) }\\ \end{array}}} \right] \end{aligned}$$
(3)
$$\begin{aligned} \hbox {b }= & {} \left[ {{\begin{array}{c} { x_1^2 - x_n^2 + y_1^2 - y_n^2 + d_n^2 - d_1^2 } \\ { x_2^2 - x_n^2 + y_2^2 - y_n^2 + d_n^2 - d_2^2 } \\ {...} \\ { x_{n-1}^2 - x_n^2 + y_{n-1}^2 - y_n^2 + d_n^2 - d_{n-1}^2 } \\ \end{array} }} \right] \end{aligned}$$
(4)
$$\begin{aligned} \hbox {X }= & {} \left[ {{\begin{array}{c} x \\ y \\ \end{array} }} \right] . \end{aligned}$$
(5)

Applying least square method, location of unknown node is obtained by: \(\hbox {X} = (\hbox {A}^\mathrm{T}\, \hbox {A})^{-1}\, \hbox {A}^\mathrm{T}\,\hbox {b}\).

Main disadvantage of the traditional DV-Hop algorithm is that the accuracy is affected by the distances between the unknown nodes and the anchor nodes, and variations of anchor placement. It performs well only in case of dense and uniform network topologies. As mentioned in the Sect. 2, distance estimation leads to high localization error as number of hop counts increase or with the rise of the network irregularity, which makes each hop distance different from others.

C-shaped, L-shaped and ring-shaped topologies are typical irregular topology examples. In these cases, due to the unconnected regions, the shortest path between anchor and unknown node can make a large detour around unconnected regions, which leads to higher hops number, and estimated distance becomes longer thus making localization error higher.

Therefore, if the average distance is used for each hop to estimate the distance between nodes, the error will increase with increase in number of hops, due to accumulated error. As distance between the unknown node and anchor nodes increases, the localization error will get higher.

The number of anchor nodes and their placement is one of the major parameters influencing the localization accuracy. Generally, the nearest anchor to a unknown node has the most accurate estimated distance compared with other anchors. In case of uniform random distribution, average distance for each node do not deviate a lot. When irregular topologies are considered (e.g. C-shaped topology), anchor distribution can be very sparse in some areas, and lack of enough number of anchors leads to error increase in estimation of average value of one hop. This is one of the main drawbacks of DV-Hop algorithm.

In wireless systems signal are sometimes corrupted by non-line-of-sight (NLOS) errors due to multipath propagation. This is the most critical error source in ranging and results in poor location accuracy. Another main drawback of DV-Hop algorithm is due to irregular radio pattern [34].

4 Improved algorithms

In this section, three new algorithms (iDV-Hop1, iDV-Hop2 and Quad DV-Hop), based on the original DV-Hop algorithm, are proposed.

4.1 iDV-Hop1 algorithm

We use the original DV-Hop algorithm to calculate the initial node position, and propose to use the following additional steps, added in order to improve localization error accuracy, forming iDV-Hop1 algorithm:

Step (1) For unknown node \(\hbox {X}_{j}\) with estimated coordinates \(\hbox {x}_{j}, \hbox {y}_{j}\) in the final step of the DV-Hop, choose an anchor that is minimum number of hops away, denoted as \(\hbox {A}_{i }\,(\hbox {x}_{i}, \hbox {y}_{i})\).

Step (2) Form two circles, one around anchor \(\hbox {A}_{i}\) and other around node \(\hbox {X}_{j}\), denoted as \(\hbox {C}_{i}\) and \(\hbox {C}_{j}\), respectively. Radius \(\hbox {R}_{j}\) is equal to the distance between the node \(\hbox {X}_{j}\) and the anchor \(\hbox {A}_{i}\), (see 6). If \(\hbox {HopSize}_{i}\), obtained by the) is average per-hop distance, then the radius \(\hbox {R}_{i}\) of the second circle is calculated by (7). Here, \(\hbox {hop}_{ij }\) is minimum number of hops between the anchor \(\hbox {A}_{i}\) and the unknown node \(\hbox {X}_{j}\).

$$\begin{aligned} R_j^2= & {} {( x_i - x_j )}^2 + {( y_i - y_j )}^2, \end{aligned}$$
(6)
$$\begin{aligned} R_i= & {} {HopSize}_i \times {hop}_{ij}. \end{aligned}$$
(7)

Step (3) Find the intersection points of these two circles \((\hbox {C}_{i }\cap \, \hbox {C}_{j})\). These points are denoted as \(\hbox {S}_{i}\, (\hbox {x}_{si}, \hbox {y}_{si})\) and \(\hat{\hbox {S}}_{i} \,(\hbox {x}_{\hat{s}i}, \hbox {y}_{\hat{s}i})\). Finally, the unknown node coordinates are calculated according to the following centroid formula:

$$\begin{aligned} X_i^T ( x_T , y_T )=\left( {\frac{ x_i + x_{si} + x_{\hat{{s}}i} }{3},\frac{ y_i + y_{si} + y_{\hat{{s}}i} }{3}} \right) . \end{aligned}$$
(8)

Equation (8) basically represents centroid of the triangle that forms the anchor and the two intersection points (see Fig. 1).

Fig. 1
figure 1

Localization method used in iDV-Hop1 algorithm

Full size image

4.2 iDV-Hop2 algorithm

In iDV-Hop2 algorithm, first and second steps from iDV-Hop1 algorithm are kept, and modification is introduced in the third step. First reference point is taken as coordinates obtained by original DV-Hop algorithm, and triangle is then formed between that point and two circle-circle intersection points. This algorithm is named iDV-Hop2 and illustration of node localization using this method is given in Fig. 2. Equation in the third step of iDV-Hop1 becomes:

$$\begin{aligned} X_j^T ( x_T , y_T )=\left( {\frac{ x_i + x_{si} + x_{\hat{{s}}i} }{3},\frac{ y_i + y_{si} + y_{\hat{{s}}i} }{3}} \right) , \end{aligned}$$
(9)

where \(\hbox {x}_{j}, \hbox {y}_{j}\) are coordinates obtained by original DV-Hop algorithm.

Fig. 2
figure 2

Localization method used in iDV-Hop2 algorithm

Full size image

4.3 Discussion regarding intersection points existence

Depending on the values of radius \(\hbox {R}_{i}\) and \(\hbox {R}_{j}\), several cases are considered and discussed regarding the existence of intersection points \(\hbox {S}_{i}\) and \(\hat{\hbox {S}}_{i}\). As long as both intersection points exist, previously mentioned triangle can be formed, either taking anchor as third reference point (as in iDV-Hop1) or location obtained by DV-Hop algorithm (as in iDV-Hop2). The following observations are valid for algorithms, iDV-Hop1 and iDVHop2.

(1) Case R\(_{i }\)= R\(_{j}\)

In case when radius of both circles are the same, intersection points are equally distanced from the anchor and coordinates obtained by DV-Hop (Fig. 3).

Fig. 3
figure 3

Illustration of circle–circle intersection when \(\hbox {R}_{i}=\hbox {R}_{j}\)

Full size image

(2) Case \(\hbox {R}_{i }> \hbox {R}_{j}\)

As radius \(\hbox {R}_{i}\) increase (i.e. number of hops), intersection points move on along circle \(\hbox {C}_{j}\) in such way that distance from the anchor is increasing (illustrated with dotted gray arrow line on Fig. 4a. When \(\hbox {R}_{i}\) equals \(\hbox {2R}_{j}\), there is no two intersection points (i.e. \(\hbox {S}_{i }= \hat{\hbox {S}}_{i})\). When this special case occurs, circles intersect in a single degenerate point, and mentioned triangle cannot be formed. This is depicted in Fig. 4b. As long as the following condition is satisfied, \(0 < \hbox {R}_{i}< \hbox {2R}_{j}\), the unknown node can be located by using this method (Fig. 4b).

Fig. 4
figure 4

a Illustration of circle–circle intersection when \({\hbox {R}}_{i}> {\hbox {R}}_{j}\), b Illustration of circle–circle intersection when \({\hbox {R}}_{i}= 2{\hbox {R}}_{j}\)

Full size image

(3) Case \(\hbox {R}_{i }< \hbox {R}_{j}\)

As radius \(\hbox {R}_{i}\) decrease, intersection points move on along circle \(\hbox {C}_{i}\) approaching to the anchor. This is illustrated with dotted gray arrow line in Fig. 5. If condition \(\hbox {R}_{i }> 0\) is satisfied, there will be always intersection points, and referent triangle can be formed to obtain nodes coordinates. Based on the previous discussions and the fact that according to (7), \(\hbox {R}_{i }>\) 0 is always satisfied, the following Lemma can be formulated.

Fig. 5
figure 5

Illustration of circle–circle intersection when \(\hbox {R}_{i }< \hbox {R}_{j}\)

Full size image

Lemma

The two intersection points \(\hbox {S}_{i}\) and \(\hat{\hbox {S}}_{i}\) always exists if and only if \(\hbox {R}_{i}< \hbox {2R}_{j}\).

The condition \(\hbox {R}_{i} < \hbox {2R}_{j}\) can be used at the beginning of algorithms iDV-Hop1 and iDV-Hop2 in order to check for the intersection points existence.

4.4 Quad DV HOP algorithm

In the DV-Hop algorithm, it is assumed that the minimum hop path between nodes is similar to a straight line, but in practical applications, it is not the case. The accuracy of distance measurements may be degraded by noise, which introduces error in estimating the distance between the unknown node and the anchor node, calculated by the hop-size and number of hops that affects the localization accuracy of DV-Hop algorithm. In this algorithm, focus is given on the third step of DV-Hop, particularly on solving matrix given by equation (2). The most basic convex optimization problem, least-squares, is first considered.

Given \(\hbox {A}^{m,n}\) and \(\hbox {b}\in \hbox {R}^{m}\) with m \(\ge \) n, the problem is to find \(\hbox {x} \in \hbox {R}^{n}\), that minimizes \({\vert }{\vert }\hbox {Ax} - \hbox {b}{\vert }{\vert }_{2}\), where \(\hbox {A} \in \hbox {R}^{m,n }\) [35]. Suppose we wish to add some simple upper and lower bounds to the least-squares problem. It can be transformed into a quadratic program (QP), which can be solved by some quadratic programming solver [35].

The problem to be solved is the following:

$$\begin{aligned} \begin{array}{cc} \hbox {Minimize}:\quad &{} \left| {\left| {\hbox {Ax}-\hbox {b}} \right| } \right| _{2} \\ \hbox {Subject to}:\quad &{} l\le x\le u \\ &{} l=\left[ {\hbox {x}_{\hbox {min}} ,\hbox { y}_{\hbox {min}} } \right] , \\ &{} u=\left[ {\hbox {y}_{\hbox {max}} ,\hbox { y}_{\hbox {max}} } \right] . \\ \end{array} \end{aligned}$$
(10)

Figure 6 illustrates how boundaries are defined. Anchor with the smallest number of hops from the unknown node is selected to be the center of circle which radius is defined by following formula:

$$\begin{aligned} R_a =k\times {HopSize}_{ave}, \end{aligned}$$
(11)

where \(k\) is minimum number of hops between anchor and the unknown node, \(\hbox {HopSize}_{ave}\) is average of all anchor nodes hop-sizes. Since the coordinates of anchor are known, boundaries in which unknown node is located can be computed. They are defined by a square, with center in anchor with minimum number of hops from unknown node. In some corner cases, when boundaries are beyond network monitoring area, then initial region boundaries must be revised. Corners of monitoring area which is illustrated in Fig. 7, presents limits that unknown node is located, basically a rectangular region is formed that defines an area in which unknown nodes is assumed to be.

Fig. 6
figure 6

Localization method using Quad DV-Hop algorithm

Full size image
Fig. 7
figure 7

Corner case in determining region boundaries

Full size image

5 Simulation results and discussion

To demonstrate the effectiveness of the proposed algorithms, simulation experiments are performed using the four different scenarios. Performance of our algorithms is compared to the DV-Hop [15] and Improved DV-Hop [26] algorithms, by thorough simulations. The simulation results are given as average localization error of 100 experiments with statistical 95 % confidence intervals added. A series of simulation results are used to evaluate the performance of the proposed scheme in isotropic and anisotropic WSNs. Four different topologies are considered: random, C shaped random, gridy, and C shaped gridy which are illustrated in the Fig. 8. Most commonly used random uniform placement scheme is considered where nodes are randomly deployed and respectively its C shaped form (irregularly shaped network topology), with an empty area on one side, as shown in Fig. 8. Gridy topology represents a node position that deviates from the exact position in the orthogonal grid, anchors and nodes are uniformly distributed (with some random placement error). Also, corresponding C shaped gridy scheme is considered. Region is assumed to be a square area of fixed size 100\(\times \)100m. Every node has the same communication range. The localization error is defined by the following equation:

$$\begin{aligned} L_E =\frac{ \sum \limits _{i=1}^{N-M} {\sqrt{ {( x_i^{\prime } - x_i )}^2 - {( y_i^{\prime } - y_i )}^2 }} }{R\times (N-M)}, \end{aligned}$$
(12)

where \((x_{i}, y_{i})\) are the actual coordinates of unknown \(\hbox {node}\, i\) \( ( x_i^{\prime } , y_i^{\prime } )\) are estimated coordinates, N is total number of nodes, M is number of anchors, R is communication range.

Fig. 8
figure 8

Network topologies, a random deployment, b C shaped random deployment, c gridy deployment, d C shaped gridy deployment (number of unknown nodes is 200, 10 % anchor nodes, R = 15 m)

Full size image

Simulation results are analyzed by varying the following three parameters:

  1. 1.

    Number of anchors

  2. 2.

    Communication range

  3. 3.

    The number of nodes with unknown location

In the next sections, the simulation results are given separately for each topology.

5.1 Simulation results for the uniform random network

As depicted in Fig. 9, with the increase of the communication range, localization error tends to decrease for all algorithms. With the increase of the communication range (the network connectivity rises), the estimated hop-distance is closer to the Euclidean distance between two sensor nodes, thus lowering the localization error. Compared to DV-Hop, iDV-Hop1 has higher localization accuracy in this scenario, but iDV-Hop2 has about 11 % lower average localization error. With communication range R = 15 m, iDV-Hop2 has around 0.38R localization error while DV-Hop has around 0.45R. Quad DV-HOP also shows better performance on average than DV-Hop (it has around 0.34R localization error). As the communication range increases the network connectivity increases. The number of anchor nodes per unknown node increase, therefore the localization error decrease. iDV-Hop2 has about the same average localization error as Improved DV-Hop around 0.31R.

Fig. 9
figure 9

Communication range impact on the localization error for uniform random network (10 % anchor nodes, 200 unknown nodes)

Full size image

In Fig. 10, simulation results are presented by varying number of anchor nodes, while communication range is fixed to 15 m, and number of unknown nodes is 200. The average localization error of iDV-Hop2 and Quad DV-Hop are about 0.48R and 0.46R, respectively, and for DV-Hop 0.47R on average. Quad DV-Hop has the lowest localization error compared to other algorithms for scenario with five anchors (localization error is around 0.6R while error for DV-Hop is around 0.75R).With the increase of anchor nodes for fixed communication range and number of nodes, the number of hops between anchors and nodes decrease. Thus, distance estimation between anchors and nodes is less erroneous and closer to the real distance. Hence, the localization accuracy increases.

Fig. 10
figure 10

Ratio of anchor nodes impact on the localization error for uniform random network (communication range R = 15 m, 200 unknown nodes)

Full size image

In results shown in Fig. 11, number of unknown nodes in network is varied from 200 to 500, and communication range is fixed to 15 m, while number of anchor nodes is 10 % of total nodes. With increasing number of nodes, the average number of neighbors of each node is increased (i.e. the density of the network is increased), and the network gets well connected. The shortest hop path has lesser deviation from straight line between anchors and unknown nodes, which imply that average hop size is more accurate, therefore the localization error tends to decrease. Best performance is shown by the iDV-Hop2, having the lowest average localization error—around 0.28R. Compared to Improved DV-Hop algorithm [26], average localization error is lower by around 3 % and around 15 % lower on average compared to DV-Hop. In Table 1, average values of localization errors are given for each algorithm.

Fig. 11
figure 11

Number of nodes impact on the localization error for uniform random network (communication range R= 15 m, 10 % anchor nodes)

Full size image
Table 1 Average values of localization errors for the uniform random network
Full size table

5.2 Simulation results for the C shaped random network

In C shaped network the same number of nodes is considered and communication range is varied. As depicted in Fig. 12, all proposed algorithms in this paper performed better in terms of lower localization error compared to DV-Hop and Improved DV-Hop. However, the DV-Hop method yields high localization errors in anisotropic networks, where the existence of holes breaks the proportionality between the distance and hop count and thus leads to inaccurate location estimation.

Fig. 12
figure 12

Communication range impact on the localization error for C shaped random network (communication range R = 15 m, 200 unknown nodes)

Full size image

For example, if communication range is 15m, iDV-Hop1, iDV-Hop2 and Quad DV-Hop have around 0.7R, 0.8R and 0.82R localization error, respectively, while DV-Hop and Improved DV-Hop has around 1.7R and 1.9R respectively. Average localization errors for iDV-Hop1, iDV-Hop2 and Quad DV-Hop are 0.54R, 0.64R, and 0.53R, respectively.

In Fig. 13, simulation results for C shaped random network are presented by varying the number of anchor nodes, while maintaining fixed communication range and number of unknown nodes. In this scenario, the proposed algorithms outperform DV-Hop and Improved DV-Hop. With minimum number of anchors—5, iDV-Hop1 and Quad DV-Hop has for around 0.7R and 0.5R lower localization error, respectively, compared to DV-Hop, and for around 0.65R lower localization error compared to Improved DV-Hop. iDV-Hop2 has around 40 % lower error on average compared to DV-Hop, and almost 50 % lower compared to Improved DV-Hop.

Fig. 13
figure 13

Ratio of anchor nodes impact on the localization error for C shaped random network (communication range R = 15 m, 200 unknown nodes)

Full size image

Figure 14 illustrates results for C shaped random network when number of unknown nodes is varied. Proposed algorithms, achieved lower localization error compared to DV-Hop and Improved DV-Hop. Average localization error is 0.62R, 0.81R, 0.74R for iDV-Hop1, iDV-Hop2 and Quad DV-Hop respectively, while for DV-Hop and Improved DV-Hop are 1.6R, 1.8R, respectively. In Table 2, average values of localization errors are given for the C shaped random network.

Fig. 14
figure 14

Number of nodes impact on the localization error for C shaped random network (communication range R = 15 m, 10 % anchor nodes)

Full size image
Table 2 Average values of the localization errors for the C shaped random network
Full size table

5.3 Simulation results for the gridy network

For gridy deployment, same number of unknown nodes is considered (200 nodes), while transmission range is varied. As depicted in Fig. 15 iDV-Hop2 and Quad DV-Hop shows better performance in terms of lower localization error compared to DV-Hop. As in uniform random deployment scenario, iDV-Hop1 shows no improvement. Average localization error for Quad DV-Hop and iDV-Hop2 are 0.33R and 0.31R, respectively, while DV-Hop achieves about 0.35R.

Fig. 15
figure 15

Communication range impact on the localization error for gridy network (10 % anchor nodes, 200 unknown nodes)

Full size image

As depicted in Fig. 16, when number of anchor nodes is increased the localization error of all algorithms decreases. Again, iDV-Hop2 has lowest localization error compared to other proposed algorithms in this paper. For example, with 5 anchors in the network, the localization error is around 0.65R while for DV-HOP is 0.7R. On average, iDV-Hop2 has around 4 % lower localization error compared to DV-Hop.

Fig. 16
figure 16

Number of anchors impact on the localization error for gridy network (communication range R = 15 m, 200 unknown nodes)

Full size image

When number of unknown nodes in gridy network is varied from 200 to 500, for iDV-Hop1 the localization error decreases from around 0.63 to around 0.43R, while for DV-Hop error slowly decreases from around 0.41 to around 0.36R which is depicted in Fig. 17. Average localization error for Quad DV-HOP and iDV-Hop2 are 0.37R and 0.34R respectively. iDV-Hop2, has around 10 % lower localization error on average compared to DV-Hop. With 500 nodes it has the lowest localization error compared to all algorithms in this paper—around 0.3R. In Table 3, average values of localization error are shown for the gridy network.

Fig. 17
figure 17

Number of nodes impact on the localization error for gridy network (communication range R = 15 m, 10 % anchors)

Full size image
Table 3 Average localization errors for the gridy network
Full size table

5.4 Simulation results for the C shaped gridy network

C shaped gridy topology is also considered, and results for varying transmission range are depicted in Fig. 18. For range R = 15 m, proposed algorithms have around 0.8R lower localization error compared to DV-Hop and Improved DV-Hop. Increasing the communication range leads to localization error decrease slowly from around 0.7R to 0.4R, 0.8R to 0.35R, 0.81R to 0.52R for iDV-Hop1, iDV-Hop2 and Quad DV-HOP, respectively. Improved DV-Hop at 35 m communication range has the same localization error as DV-Hop, which is for around 0.2R higher compared to iDV-Hop2. With minimal communication range 15 m, iDV-Hop1 has localization error for more than 50 % lower compared to DV-Hop.

Fig. 18
figure 18

Communication range impact on the localization error for C shaped gridy network (10 % anchors, 200 unknown nodes)

Full size image

Simulation results for scenario where the number of anchors is varied are shown in Fig. 19. Again, it can be observed that for irregular network patterns iDV-Hop1 and iDV-Hop2 are more suitable than DV-Hop and Improved DV-Hop. Average localization error for iDV-Hop1 is around 44 % lower compared to DV-Hop, and around 50 % lower compared to Improved DV-Hop. For DV-Hop and Improved DV-Hop the localization error never drops below 1.5R, while for iDV-Hop1, iDV-Hop2 and Quad DV-Hop after 10 anchors the error decreases to range between 1R and 0.7R.

Fig. 19
figure 19

Number of anchors impact on the localization error for C shaped gridy network (communication range R = 15 m, 200 unknown nodes)

Full size image

In Fig. 20, results are shown for C shaped gridy network when number of unknown nodes is varied in the same manner as in previous scenarios, around 1.7R, while for example, iDV-Hop1 around 0.6R. DV-Hop shows localization error increase for range of 200–400 nodes, and Improved DV-Hop also has no effect in lowering localization error for this type of network. Table 4, represents average values of localization error for C shaped gridy topology.

Fig. 20
figure 20

Number of nodes versus localization error for C shaped gridy network (communication range R = 15 m, 10 % anchors)

Full size image
Table 4 Average values of the localization errors for the C shaped gridy network
Full size table

6 Conclusion

In this article, three new algorithms are proposed, iDV-Hop1, iDV-Hop2 and Quad DV-Hop, as improvements of the original DV-Hop algorithm and simulation results are given for four different scenarios (uniform random, C shaped random, gridy and C shaped gridy topology). The iDV-Hop1 and iDV-Hop2 algorithms have additional steps added to the original DV-Hop in order to reduce the localization error. Quad DV-Hop algorithm improves the localization accuracy by solving the bounded least squares problem.

In general, iDV-Hop2 shows the best overall performance, since it has lower localization error compared to DV-Hop and Improved DV-Hop in all scenarios. It is also better compared to iDV-Hop1 and Quad DV-Hop in two scenarios (uniform random and gridy), but in other two scenarios it is not significantly worse than iDV-Hop1 which showed the best performance in those scenarios. The iDV-Hop1 has advantages in scenarios with irregular topologies. For the C shaped random uniform topology, this algorithm reduces localization error for up to three times compared to DV-Hop and Improved DV-Hop. Quad DV-Hop showed better performance compared to the original DV-Hop algorithm in all scenarios. However, in the uniform random and gridy topology scenarios it shows no significant improvement (improvements are up to 11 %, and in some cases there are no improvement) which would justify the higher computational complexity of Quad DV-Hop algorithm.

Future directions for this work may include reducing computational complexity for Quad DV-Hop which is the main downside of that algorithm. In this article we have not investigated anchor mobility impact on the localization error. This is another future research direction. Furthermore, upgrading proposed algorithms to the 3D localization is the next goal in our research.