# Online Sequential DV-Hop Localization Algorithm for Wireless Sensor Networks

Authors: Sana Messous; Hend Liouane
Journal: Mobile Information Systems
 (2020)

---

## Abstract

One of the main issues of wireless sensor networks is localization. Besides, it is important to track and analyze the sensed information. The technique of localization can calculate node position with the help of a set of designed nodes, denoted as anchors. The set density of these anchors may be incremented or decremented because of many reasons such as maintenance, lifetime, and breakdown. The well-known Distance Vector Hop (DV-Hop) algorithm is a suitable solution for localizing nodes having few neighbor anchors. However, existing DV-Hop-based localization methods have not considered the problem of anchor breakdown which may happen during the localization process. In order to avoid this issue, an Online Sequential DV-Hop algorithm is proposed in this paper to sequentially calculate positions of nodes and improve accuracy of node localization for multihop wireless sensor networks. The algorithm deals with the variation of the number of available anchors in the network. We note that DV-Hop algorithm is used in this article to process localization of nodes by a new optimized method for the estimation of the average distance of hops between nodes. Our proposed localization method is based on an online sequential computation. Compared with the original DV-Hop and other localization methods from the literature, simulation results prove that the proposed algorithm greatly minimizes the average of localization error of sensor nodes.


---

## Body

## 1. Introduction

Wireless sensor network (WSN) is a network of multihop wireless communication system and is consisting of huge number of small size and battery-powered microsensor nodes deployed over the application field [1]. Each sensor node is composed of a wireless communication module, a sensing module, a processing unit, and storage unit [2]. Sensor nodes can sense and detect information within its sensing range using their sensing module [3]. The sensed data is communicated and routed from sensor node to another until arriving to a central node known as base station [4]. Recently, a WSN can be applied in various applications, such as rescue, health surveillance, battle field surveillance, environmental monitoring, disaster management [5], coverage, routing, location service, security [6–8], and target tracking systems [9].In many Internet of Things (IoT) and sensor applications, the collected information of sensors nodes, which are randomly deployed in inaccessible terrain by the vehicle robots or aircrafts, is of limited use without the knowledge of its locations [10]. Besides, it is mandatory to know the location of nodes collecting data from its sensing field. To determine an absolute location of each node in the network, Global Positioning System (GPS) is the well-known solution. However, this solution is not feasible as GPS is still relatively expensive and power hungry and has degraded performance in indoor places and dense urban areas, while sensors have limited processing capability, store space, and low power [11] and most of applications use hundreds or up to thousands of sensor nodes. Recently, owing to the high cost of GPS equipment, the researcher proposed a novel solution to this positioning problem, where only a few sensor nodes are enabled with GPS capability and enough battery power to assist other sensors to find their locations. These sensor nodes with GPS are designed as anchor nodes while the rest of nodes as unknown nodes [12–14]. By this way, anchor nodes broadcast beacon messages in the network to help other nodes computing its positions. In the literature, many localization schemes have been proposed aiming to achieve energy efficiency and accuracy such as [15–19]. Thus, obtaining an accurate localization with respect to low cost of sensor deployment is a very critical requirement for any WSN [20].Localization algorithm is designed to calculate the coordinates of the unknown node with the assistance of anchor nodes. This technique determines how the information concerning distances and positions is manipulated allowing unknown nodes to estimate their positions [21]. A summarized survey of localization methods in the literature is available in [22, 23].Multihop wireless localization method can calculate the node location with the assistance of anchor nodes by using the features of wireless network, such as multihop and connectivity [24]. If the distance between nodes is estimated between 100 meters and 2000 meters, the multihop localization is adopted; i.e., count the number of hops and convert it to calculate average physical distance of hops [25].Based on hardware requirement and according to the manner of the use of the location information, multihop wireless localization methods can be divided into two categories: range-based and range-free localization. Range-based localization algorithms utilize exact measurements based techniques, mainly the Receiver Signal Strength Indicator (RSSI) [26], Time of Arrival (ToA) [27], the Angle of Arrival (AoA) of signals [28], and packet Time Difference of Arrival (TDoA) [29] to compute an estimated distance between sensor nodes and to determine location information with high accuracy. Although these techniques provide high estimation accuracy, they are expensive and require costly equipment for the estimation of node’s location [30].The range-free localization schemes, such as Centroid [31], APIT [32], DV-Hop [28, 33], Convex [34], and CAB [35], are based on hop distance and hop count between anchors and sensor nodes. These algorithms are commonly known in the literature as connectivity-based algorithms. Contrary to the range-based schemes, range-free based schemes are simple, cost-effective, and energy-efficient by exploiting internode communication and the communication range of the node to estimate node positions [36]. As mentioned in the survey on range-free techniques in [37], these algorithms are divided, based on the deployment scenarios, into four groups: (1) static sensor nodes and static anchor nodes [38, 39]; (2) static sensor nodes and mobile anchor nodes [31, 40]; (3) mobile sensor nodes and static anchor nodes [41, 42]; and (4) mobile sensor nodes and mobile anchor nodes [43, 44].Although there are various localization techniques for WSNs available in the literature, there are practical limits on these techniques such as localization accuracy, as well as on the problem of the number of anchor nodes that can be used as reference of unknown nodes localization. For example, in many scenarios, only one or two anchors are able to communicate with the sensor nodes that need to be localized for the reason of remoteness from these unknown nodes [45]. As localization is one of the most fundamental tasks for WSNs, we propose in this paper a novel online sequential localization algorithm based on the well-known DV-Hop algorithm. Our algorithm is range-free and does not need any additional piece of hardware for ranging. The main contributions of this work are the following.(1)
Find a new formulation to calculate the average hop distance between nodes(2)
Convert the original DV-Hop algorithm to an online sequential localization algorithm(3)
Calculate the position of nodes in the network using a sequential method with the help of a predefined set of candidate anchorsThe algorithm is sequential in the sense that it can handle localization with varying anchor size and it does not require storage of estimated measurements where each node maintains only the latest estimate of its own position for more simplicity of computation and better estimation accuracy.The remaining partitions of this paper are as follows: Section2 shows a short presentation of previous localization algorithms for sensor networks in the literature. Section 3 describes the network model used in our proposed method. Section 4 gives brief review of the original DV-Hop algorithm to which we contribute our work and the new formulation of average hop distance computation, as well as the presentation of our proposed online sequential DV-Hop localization algorithm. Section 5 describes the performance evaluation of our algorithm. Finally, we conclude in Section 6.


## 2. Related Works

Currently, there exist many localization algorithms for WSNs of which we can mention mainly the centroid algorithm [31], APIT [32], DV-Hop localization algorithm [33, 46], and Convex [34].The DV-Hop algorithm is the most popular localization algorithm thanks to its simplicity, feasibility, and good coverage quality. The estimation of the unknown position of nodes in the sensor network by the DV-Hop algorithm is done by the help of a set of anchor nodes that know their location by GPS. Nevertheless, the estimated distance between anchor nodes and unknown nodes is prone to be erroneous due to error in the distance hop estimation of anchor node and many other causes. So, the DV-Hop algorithm suffers from a poor localization accuracy. Therefore, many improved DV-Hop localization algorithms have been proposed in the literature, such as [47], to enhance the localization accuracy of DV-Hop algorithm for wireless sensor networks. However, these proposed improvements of DV-Hop also have some drawbacks in terms of localization accuracy [48].Some improvements of the DV-Hop algorithm are classified into the range-based algorithms. Authors in [49] proposed two Nature Inspired Algorithms based on improved variants to optimize the problem of the localization error in WSNs. The first proposed algorithm aims to determine an accurate estimation of average distance per hop using grey wolf optimization (GWO-DV-Hop). The second algorithm proposed by authors in [49], named weighted grey wolf optimization (Weighted GWO-DV-Hop), consists of finding the average distance per hop using grey wolf algorithm and then getting a weighted average distance per hop to consider impact of all types of beacons by using a weighted approach. The simulation results prove the efficiency of the proposed localization methods in comparison with the traditional DV-Hop in terms of localization error. In [50], the estimation of the distance between nodes is done by using the Received Signal Strength Indicator (RSSI) to minimize the ranging error. However, authors in [51] affirm that RSSI is not an efficient distance measurement technique in case of a noisy environment. Besides, the accuracy of this technique is very sensitive to multipath, fading, and other sources of interference, in addition to the additional hardware requirement. In [52], authors proposed a selective 3-anchor DV-Hop algorithm to calculate the position of unknown node based on each group of 3 anchors. The proposed approach is as follows: the unknown node selects a set of three anchors to form a 3-anchor group; then, it calculates its position by trilateration based on the 3-anchor group and finally, according to the relation between its position and the minimum hop counts to anchors, the unknown node chooses the best candidate position. The proposed algorithm showed a good performance compared to the original DV-Hop, but it has a big calculation complexity due to the fact that authors considered having m anchors in the wireless network and the total number of 3-anchor groups is Cm3, so the calculation complexity of the algorithm is Om3. Authors in [6] have secured the solution of localization in WSN using a public ledger (Blockchain) which contains the position of each node and the list of their neighbors.Authors in [48] proposed a novel DV-Hop (NDV-Hop) localization algorithm for WSNs. Their proposed method allows reducing the time of localization and energy consumption of nodes by reducing the communication between nodes in the network. In addition, it also aims to improve the localization accuracy. Unknown node estimates its location with minimizing the error in estimated distance by using unconstrained optimization. The work in [48] comes as an improvement of the improved DV-Hop algorithm (IDV-Hop) [53] in which the communication cost of the algorithm is increased. Another improved DV-Hop algorithm with reduced node location error (RNLE DV-Hop) is proposed in [54]. This algorithm performs better in terms of localization accuracy than the original DV-Hop algorithm, but it has a complexity computational work because of the complexity of computation of the covariance matrix of range estimation error. Two novel DV-Hop localization algorithms for randomly deployed wireless sensor networks are proposed in [55]: hyperbolic DV-Hop localization algorithm and improved weighted centroid DV-Hop localization algorithm (IWC-DV-Hop). In these enhanced algorithms, authors replaced the average distance of hops (i.e., the HopSize) of anchor node nearest to the unknown node with the average of average HopSizes of all anchors, as the average HopSize of the unknown node, because they believed that the use in the original DV-Hop of the average HopSize of anchors nearest to the unknown node is the reason leading to large errors and bad localization accuracy. Compared to the original DV-Hop algorithm, the localization accuracy is improved by both algorithms.Many other improvements of DV-Hop algorithm have been proposed in the literature such as in [56] where authors proposed a novel improved DV-Hop algorithm based on iterative computation. The improved algorithm tries to find the best global average HopSize by iterative computation to minimize the localization error caused by the average HopSize of that unknown node received from the nearest anchor node to estimate its position.Range-free localization algorithms are well developed in the literature. As in [57], authors proposed a range-free parallel efficient projection algorithm (PEPA). The localization process of a single unknown node consists of, firstly, constructing the estimative region where the unknown node resides by using the hop connectivity information from its neighboring anchors and setting up an optimization problem in order to calculate the Chebyshev center of this estimative region. Secondly, authors proposed an efficient iterative algorithm (PEPA) to solve the optimization problem and then get an accurate localization result. The algorithm shows better localization accuracy compared with the original DV-Hop algorithm.In the context of range-free algorithms, the notion of recursivity is well exploited in localization problems. As an example, authors in [58] proposed a recursive shortest path routing algorithm with application for wireless sensor network localization. The proposed recursive algorithm allowed estimating distances between any couple of sensors in multihop wireless sensor networks. It consisted of using a global table search of sensor edges and recursive functions to compute all possible paths between a source sensor designed as the unknown node and a destination sensor designed as the anchor node with the minimum number of hops. Then, by using a distance matrix, the algorithm computed the average of all paths to estimate the distance between both nodes. However, the proposed algorithm is only useful in the realm of centralized range-based localization schemes.As well as the algorithms cited above, in [59], authors proposed a novel localization technique based on location sequences called sequence-based localization (SBL). In this algorithm, location sequences are used to estimate positions of unknown nodes using RSS measurements of RF signals between the unknown node and the anchor nodes which are designed as references. To the best of our knowledge, no localization range-free algorithm using both an online sequential method and DV-Hop algorithm has been proposed in the literature. In this paper, we propose an online sequential DV-Hop localization algorithm where the sequential approach serves as reference point to other nodes in the network for more simplicity of computation and better estimation accuracy.


## 3. Review of the Original DV-Hop Algorithm

Among range-free localization algorithms, the DV-Hop algorithm was developed by Niculescu and Nath [46]. It can be summarized in three steps.In Step 1, every anchor in the network broadcasts information of its location and its hop count value initialized to 1 via a beacon packet. After receiving beacon packets, each unknown node maintains a table containing received information of every anchor nodexi,yi,hi, where xi,yi is the coordinate of anchor i and hi is the minimum number of hops from anchor i . To obtain minimum hop count value from unknown nodes to all anchors in the network, the hop count value hi of the table is replaced with hop count value of another received packet that contains the lesser hop count value to a particular anchor node. Then, the cited received packet is forwarded within the network with increased hop count value by 1 at every intermediate hop. If this packet did not contain the lesser hop count value, it will be discarded by the destination node. By this way, the minimum hop count value from all anchor nodes is obtained by all unknown nodes in the network.In Step 2, every anchor calculates its average distance of hop (i.e., one-hop-size) from another anchor in the network by the following equation:(1)HopSizei=∑i≠jnxi−xj2+yi−yj2∑i≠jnhij,where (xi, yi) and (xj, yj) are i’s and j’s anchor coordinates, respectively, hij is the minimum hop counts between anchor i and j, and n presents the number of anchors.In the third step, each unknown node uses the least square (LS) technique [1] for trilateration of its position, noting that, in basic trilateration, unknown sensors use only three distances from anchors to estimate their positions.In the DV-Hop algorithm, it is assumed that the path of hops between nodes is in the form of a straight line. However, in real applications, this assumption is not always valid. And as the average distance of hop is used to estimate the distance between anchors and unknown nodes, this assumption generates an error in localization results of the DV-Hop algorithm. Also, in the DV-Hop algorithm, the communication range of each node in the network is assumed as a standard circle, but it is not true in case of real environment because of noise. These drawbacks generate errors in localization results of the DV-Hop algorithm.


## 4. Proposed Algorithm: Online Sequential DV-Hop Localization Algorithm

### 4.1. Average Distance of Hop Calculation

The average distance of hop calculated by every anchor (i.e., one-hop-size) from another anchor in the network is used to calculate unknown nodes positions. The more this estimated distance is precise, the more the estimated positions are accurate. In Step 2 of the DV-Hop algorithm, we define a new formulation to calculate the average hop distance between anchors instead of the traditional method. So we propose to use the polynomial approximation in order to minimize the error of estimated positions and improve localization accuracy.We define the estimated distance of hop between anchorsi and other anchors n by the following polynomial:(2)din=α0+α1hin+α2hin2,where α0,α1, and α2 are the polynomial coefficients.We get a matrix form as follows:(3)hi12hi11hi22hi11...hin2hin1α2α1α0=di1di2...din,where h is the hop count between beacon nodes.We aim to determine the best value ofα by using the least square method. To find the polynomial function of approximation of distance between nodes, we solve the following equation:(4)α=HTH−1HTD.Then, each anchor broadcasts a packet containing its calculated average hop distance value in the network. When an unknown node receives this packet from its nearest anchor (i.e., the first arrived packet) which has the minimum number of hops to this unknown node, it transmits to its neighbor nodes, as its average hop distance. Then, every unknown node calculates the distance between itself and the anchor node by(5)dij=α0+α1hij+α2hij2,where dij and hij are the distance and the minimum number of hops between the i’th unknown node and j’th anchor node, respectively.In Step 3, each unknown node calculates its location by multilateration method [1]. Let dn be the estimate distance between unknown node and anchor node n. (x, y) is the coordinate of the unknown node, and (x1, y1), (x2, y2)…(xn, yn) are the coordinates of the anchor node. We obtain the following set of equations:(6)x−x12+y−y12=d12,x−x22+y−y22=d22,...x−xn2+y−yn2=dn2.Then, (6) can be transformed by(7)AX=B.We assume that M2=x2+y2, and Qi=xi2+yi2. X, A, and B are presented as follows:(8)X=xyM2,A=−2x1−2y11−2x2−2y21...−2xn−2yn1,B=d12−Q12d22−Q22...dn2−Qn2.By using the method of least square [1], we solve (7) and obtain an estimation of the unknown node coordinates by the following equation:(9)X=ATA−1ATB.Then, we get(10)x=X1,y=X2.The following example shows the correction benefits of our proposed technique. We suppose a set of sensor networks, as in Figure 1, composed of anchors a1, a2, a3, and a4, designed with red square symbols, and unknown nodes, designed with black square symbols. These sensor nodes are randomly deployed within a 20×20 meters sensing area with a communication range of 10 meters. Anchors know their positions, their distances, and the number of hops from each other. Tables 1 and 2 show the minimal number of hops between anchors and the real distances between them. MATLAB 2015a is used to perform all the following computations.Figure 1
DV-Hop error analysis.Table 1
Minimal hop count between anchors.
Hop counta1a2a3a4a10455a24053a35506a45360Table 2
Real distance between anchors.
Distance (meters)a1a2a3a4a10202028.28a220028.2820a32028.28020a428.2820200The proposed optimization concerns the HopSize calculation. Using (1) of the original DV-Hop algorithm, we determine the estimated hop distances (HopSize) of anchors in the proposed network of this example. Results are shown in Table 3.Table 3
HopSize of anchors.
Anchora1a2a3a4HopSize4.875.694.264.87Now, applying our proposed optimization, we aim to determine estimated distances between anchors using the polynomial approximation in (5). Real distances between anchors can be expressed as follows:(11)20=α0+4α1+16α2,20=α0+5α1+25α2,28.28=α0+5α1+25α2,28.28=α0+5α1+25α2,20=α0+3α1+9α2,20=α0+6α1+36α2.Then, (11) can be transformed as follows:(12)202028.2828.282020=14161525152515251391636α0α1α2.Coefficientsα0, α1, and α2 are calculated using the least square approximation as in (4):(13)α0=−19.034,α1=18.531,α2=−1.971.After calculating coefficients of the polynomial approximation and HopSize of anchors, we determine estimated distances between anchors. Tables4 and 5 show results using the DV-Hop, dDV−Hopest, and the proposed method, dproposedest, respectively. One can see from these tables that estimated distances resulting from our proposed approach are closer to the real distance than that by applying the DV-Hop method. It can be concluded that HopSize values are erroneous, so the DV-Hop method will not give accurate estimated locations of unknown nodes.Table 4
Estimated distances between anchors by DV-Hop method.
dDV−Hopesta1a2a3a4a1019.5021.324.35a219.50021.314.61a321.321.3029.22a424.3514.6129.220Table 5
Estimated distances between anchors by the proposed method.
dproposedesta1a2a3a4a1023.5524.3524.35a223.55024.3518.82a324.3524.35021.19a424.3518.8221.190The estimation error of distance between anchori and anchor j, which is the absolute value of the difference between estimated distance and real distance as written in (14), is evaluated in Table 6.(14)errorij=dijest−dijreal.Table 6
Comparison of the average distance estimation error.
errora1a2a3a4DV-Hop method3.674.164.716.18Proposed method3.942.883.152.1As can be seen from Table6, the average distance estimation error achieved by the proposed method is lesser when compared with that of DV-Hop method. Accordingly, our proposed technique outperforms in precision its counterpart, which will be well proved by simulation results.In real applications, anchor may not be available to perform continuously the localization process for many reasons such as maintenance, lifetime, and breakdown. Despite its performance for position estimation, the traditional DV-Hop algorithm does not take into account the problem when considering a variation of anchors in the network for the localization of unknown nodes. For that, we propose an online sequential DV-Hop localization algorithm for large scale WSNs.


### 4.2. Online Sequential Computation Algorithm

We propose a new improved DV-Hop algorithm. The proposed approach puts forward a new formulation of the DV-Hop based localization algorithm using an online sequential method that deals with the variation of anchor population candidates to the localization process. We consider having a population of anchors in the network. The estimated positionX of unknown node is, as solution of (7) defined as in (9), X=ATA−1ATB.Initially, we suppose having a set of anchors candidate for the localization process. So we have(15)A0X0=B0.Then, its solution becomes X0=K0−1A0TB0, where K0=A0TA0.Suppose we are given another set of anchors in the network. Then, we have(16)A0A1X=B0B1.So, the following equation denotes the new solution of (16):(17)X1=K1−1A0A1TB0B1,where(18)K1=A0A1TA0A1.For sequential computing, we aim to expressX1 as a function of X0, K1, A1, and B1.Now,K1 can be written as(19)K1=A0TA1T∗A0A1=A0TA0+A1TA1=K0+A1TA1,and then(20)A0A1TB0B1=A0TB0+A1TB1=K0K0−1A0TB0+A1TB1=K0X0+A1TB1=K1X0−A1TA1X0+A1TB1.This is becauseK0=K1−A1TA1.Then, by combining (17) and (20), we get(21)X1=K1−1A0A1TB0B1=K1−1K1X0−A1TA1X0+A1TB1=K1−1K1X0−K1−1A1TA1X0+K1−1A1TB1=X0+K1−1A1TB1−A1X0,where K1=K0+A1TA1.Now, we generalize the previous steps, as new set of anchors is considered in the population. A sequential implementation for updating the least squares solution, which is similar to the recursive least squares (RLS) algorithm [60], is as follows.Kk+1−1 is used to compute Xk+1 from Xk rather than Kk+1. The update formula for Kk+1−1 is derived using the Woodbury formula [61]:(22)Kk+1−1=Kk+Ak+1TAk+1−1=Kk−1−Kk−1Ak+1TI+Ak+1TAk+1Kk−1−1Ak+1TKk−1,where I is the identity matrix.As a second sequential implementation, letSk+1=Kk+1−1.Then, the equations for updatingXk+1 can be written as(23)Sk+1=Sk−PkAk+1TI+Ak+1TAk+1Sk−1Ak+1TSk.So we obtain the equation for updatingXk+1:(24)Xk+1=Xk+Sk+1Ak+1TBk+1−Ak+1Xk.From equation (24), the sequential implementation of the least squares solution is similar to RLS algorithm.Let(25)Xk+1=Xk+Wk+1θk,where Xkis a vector of estimated coordinates of the unknown nodes with n anchors, Wk+1is a scaling factor known as the Kalman Gain [62], θk is error estimation/difference between the real position and the estimated position with n anchors.The matrixS is proportional to the covariance matrix of the estimate; thus it is called the covariance matrix.The algorithm is initialized withX0=0 and S0=λI, where I is the identity matrix and λ is a very large positive number. The confidence of the initial estimate of Xk decreases with the increase of λ’s value. So choosing a very large λ is equivalent to considering the initial estimation of Xk as very uncertain and the RLS algorithm will diverge very rapidly from the initialization X0=0.Our proposed improved DV-Hop algorithm based on online sequential computation is as follows: the algorithm starts creating a set ofnc candidate anchors for the localization process iteratively and randomly selected according to the disponibility of anchors in the population. The initial position of each other node (unknown node) is X0=0. Then, it performs position estimation of nodes by using the DV-Hop algorithm with the proposed average hop distance correction. A sequential formula for calculating an estimated position of unknown node using (25) is updated.The pseudocode of our localization algorithm is presented in Algorithm 1.Algorithm 1:Proposed algorithm.
Input:WSN; Anchor nodes and their coordinates (xi, yi) where i=1..Na, Na :  Anchors Population size;Output: Position estimate Xm of m unknown sensor nodes(1)
Begin /∗initialization(2)
Xm0=0/∗ initial position of unknown node to estimate(3)
S=λ∗I/∗ covariance matrix S, where I is the identity matrix and λ is a very large positive number;(4)
Detect a population of anchor nodes candidates for the position estimation process.(5)
While (at least one of nodes is not localized) Do5.1
Computation of the minimal hop count between selected anchors available for localization5.2
Apply the Least Square Method to transform the minimum hop count into optimized distance by the polynomial approximation5.3
Computation of the minimal hop count between selected anchors and unknown nodes5.4
Apply the polynomial approximation to estimate the distance between anchors (i) and unknown nodes (j): dij=α0+α1hij+α2hij25.5
Positions estimationXm of unknown nodes using the update sequential formula Xk+1=Xk+Sk+1Ak+1TBk+1−Ak+1Xk(6)
end While;(7)
Xm /∗ Estimated position of all unknown nodes m(8)
end;


## 4.1. Average Distance of Hop Calculation

The average distance of hop calculated by every anchor (i.e., one-hop-size) from another anchor in the network is used to calculate unknown nodes positions. The more this estimated distance is precise, the more the estimated positions are accurate. In Step 2 of the DV-Hop algorithm, we define a new formulation to calculate the average hop distance between anchors instead of the traditional method. So we propose to use the polynomial approximation in order to minimize the error of estimated positions and improve localization accuracy.We define the estimated distance of hop between anchorsi and other anchors n by the following polynomial:(2)din=α0+α1hin+α2hin2,where α0,α1, and α2 are the polynomial coefficients.We get a matrix form as follows:(3)hi12hi11hi22hi11...hin2hin1α2α1α0=di1di2...din,where h is the hop count between beacon nodes.We aim to determine the best value ofα by using the least square method. To find the polynomial function of approximation of distance between nodes, we solve the following equation:(4)α=HTH−1HTD.Then, each anchor broadcasts a packet containing its calculated average hop distance value in the network. When an unknown node receives this packet from its nearest anchor (i.e., the first arrived packet) which has the minimum number of hops to this unknown node, it transmits to its neighbor nodes, as its average hop distance. Then, every unknown node calculates the distance between itself and the anchor node by(5)dij=α0+α1hij+α2hij2,where dij and hij are the distance and the minimum number of hops between the i’th unknown node and j’th anchor node, respectively.In Step 3, each unknown node calculates its location by multilateration method [1]. Let dn be the estimate distance between unknown node and anchor node n. (x, y) is the coordinate of the unknown node, and (x1, y1), (x2, y2)…(xn, yn) are the coordinates of the anchor node. We obtain the following set of equations:(6)x−x12+y−y12=d12,x−x22+y−y22=d22,...x−xn2+y−yn2=dn2.Then, (6) can be transformed by(7)AX=B.We assume that M2=x2+y2, and Qi=xi2+yi2. X, A, and B are presented as follows:(8)X=xyM2,A=−2x1−2y11−2x2−2y21...−2xn−2yn1,B=d12−Q12d22−Q22...dn2−Qn2.By using the method of least square [1], we solve (7) and obtain an estimation of the unknown node coordinates by the following equation:(9)X=ATA−1ATB.Then, we get(10)x=X1,y=X2.The following example shows the correction benefits of our proposed technique. We suppose a set of sensor networks, as in Figure 1, composed of anchors a1, a2, a3, and a4, designed with red square symbols, and unknown nodes, designed with black square symbols. These sensor nodes are randomly deployed within a 20×20 meters sensing area with a communication range of 10 meters. Anchors know their positions, their distances, and the number of hops from each other. Tables 1 and 2 show the minimal number of hops between anchors and the real distances between them. MATLAB 2015a is used to perform all the following computations.Figure 1
DV-Hop error analysis.Table 1
Minimal hop count between anchors.
Hop counta1a2a3a4a10455a24053a35506a45360Table 2
Real distance between anchors.
Distance (meters)a1a2a3a4a10202028.28a220028.2820a32028.28020a428.2820200The proposed optimization concerns the HopSize calculation. Using (1) of the original DV-Hop algorithm, we determine the estimated hop distances (HopSize) of anchors in the proposed network of this example. Results are shown in Table 3.Table 3
HopSize of anchors.
Anchora1a2a3a4HopSize4.875.694.264.87Now, applying our proposed optimization, we aim to determine estimated distances between anchors using the polynomial approximation in (5). Real distances between anchors can be expressed as follows:(11)20=α0+4α1+16α2,20=α0+5α1+25α2,28.28=α0+5α1+25α2,28.28=α0+5α1+25α2,20=α0+3α1+9α2,20=α0+6α1+36α2.Then, (11) can be transformed as follows:(12)202028.2828.282020=14161525152515251391636α0α1α2.Coefficientsα0, α1, and α2 are calculated using the least square approximation as in (4):(13)α0=−19.034,α1=18.531,α2=−1.971.After calculating coefficients of the polynomial approximation and HopSize of anchors, we determine estimated distances between anchors. Tables4 and 5 show results using the DV-Hop, dDV−Hopest, and the proposed method, dproposedest, respectively. One can see from these tables that estimated distances resulting from our proposed approach are closer to the real distance than that by applying the DV-Hop method. It can be concluded that HopSize values are erroneous, so the DV-Hop method will not give accurate estimated locations of unknown nodes.Table 4
Estimated distances between anchors by DV-Hop method.
dDV−Hopesta1a2a3a4a1019.5021.324.35a219.50021.314.61a321.321.3029.22a424.3514.6129.220Table 5
Estimated distances between anchors by the proposed method.
dproposedesta1a2a3a4a1023.5524.3524.35a223.55024.3518.82a324.3524.35021.19a424.3518.8221.190The estimation error of distance between anchori and anchor j, which is the absolute value of the difference between estimated distance and real distance as written in (14), is evaluated in Table 6.(14)errorij=dijest−dijreal.Table 6
Comparison of the average distance estimation error.
errora1a2a3a4DV-Hop method3.674.164.716.18Proposed method3.942.883.152.1As can be seen from Table6, the average distance estimation error achieved by the proposed method is lesser when compared with that of DV-Hop method. Accordingly, our proposed technique outperforms in precision its counterpart, which will be well proved by simulation results.In real applications, anchor may not be available to perform continuously the localization process for many reasons such as maintenance, lifetime, and breakdown. Despite its performance for position estimation, the traditional DV-Hop algorithm does not take into account the problem when considering a variation of anchors in the network for the localization of unknown nodes. For that, we propose an online sequential DV-Hop localization algorithm for large scale WSNs.


## 4.2. Online Sequential Computation Algorithm

We propose a new improved DV-Hop algorithm. The proposed approach puts forward a new formulation of the DV-Hop based localization algorithm using an online sequential method that deals with the variation of anchor population candidates to the localization process. We consider having a population of anchors in the network. The estimated positionX of unknown node is, as solution of (7) defined as in (9), X=ATA−1ATB.Initially, we suppose having a set of anchors candidate for the localization process. So we have(15)A0X0=B0.Then, its solution becomes X0=K0−1A0TB0, where K0=A0TA0.Suppose we are given another set of anchors in the network. Then, we have(16)A0A1X=B0B1.So, the following equation denotes the new solution of (16):(17)X1=K1−1A0A1TB0B1,where(18)K1=A0A1TA0A1.For sequential computing, we aim to expressX1 as a function of X0, K1, A1, and B1.Now,K1 can be written as(19)K1=A0TA1T∗A0A1=A0TA0+A1TA1=K0+A1TA1,and then(20)A0A1TB0B1=A0TB0+A1TB1=K0K0−1A0TB0+A1TB1=K0X0+A1TB1=K1X0−A1TA1X0+A1TB1.This is becauseK0=K1−A1TA1.Then, by combining (17) and (20), we get(21)X1=K1−1A0A1TB0B1=K1−1K1X0−A1TA1X0+A1TB1=K1−1K1X0−K1−1A1TA1X0+K1−1A1TB1=X0+K1−1A1TB1−A1X0,where K1=K0+A1TA1.Now, we generalize the previous steps, as new set of anchors is considered in the population. A sequential implementation for updating the least squares solution, which is similar to the recursive least squares (RLS) algorithm [60], is as follows.Kk+1−1 is used to compute Xk+1 from Xk rather than Kk+1. The update formula for Kk+1−1 is derived using the Woodbury formula [61]:(22)Kk+1−1=Kk+Ak+1TAk+1−1=Kk−1−Kk−1Ak+1TI+Ak+1TAk+1Kk−1−1Ak+1TKk−1,where I is the identity matrix.As a second sequential implementation, letSk+1=Kk+1−1.Then, the equations for updatingXk+1 can be written as(23)Sk+1=Sk−PkAk+1TI+Ak+1TAk+1Sk−1Ak+1TSk.So we obtain the equation for updatingXk+1:(24)Xk+1=Xk+Sk+1Ak+1TBk+1−Ak+1Xk.From equation (24), the sequential implementation of the least squares solution is similar to RLS algorithm.Let(25)Xk+1=Xk+Wk+1θk,where Xkis a vector of estimated coordinates of the unknown nodes with n anchors, Wk+1is a scaling factor known as the Kalman Gain [62], θk is error estimation/difference between the real position and the estimated position with n anchors.The matrixS is proportional to the covariance matrix of the estimate; thus it is called the covariance matrix.The algorithm is initialized withX0=0 and S0=λI, where I is the identity matrix and λ is a very large positive number. The confidence of the initial estimate of Xk decreases with the increase of λ’s value. So choosing a very large λ is equivalent to considering the initial estimation of Xk as very uncertain and the RLS algorithm will diverge very rapidly from the initialization X0=0.Our proposed improved DV-Hop algorithm based on online sequential computation is as follows: the algorithm starts creating a set ofnc candidate anchors for the localization process iteratively and randomly selected according to the disponibility of anchors in the population. The initial position of each other node (unknown node) is X0=0. Then, it performs position estimation of nodes by using the DV-Hop algorithm with the proposed average hop distance correction. A sequential formula for calculating an estimated position of unknown node using (25) is updated.The pseudocode of our localization algorithm is presented in Algorithm 1.Algorithm 1:Proposed algorithm.
Input:WSN; Anchor nodes and their coordinates (xi, yi) where i=1..Na, Na :  Anchors Population size;Output: Position estimate Xm of m unknown sensor nodes(1)
Begin /∗initialization(2)
Xm0=0/∗ initial position of unknown node to estimate(3)
S=λ∗I/∗ covariance matrix S, where I is the identity matrix and λ is a very large positive number;(4)
Detect a population of anchor nodes candidates for the position estimation process.(5)
While (at least one of nodes is not localized) Do5.1
Computation of the minimal hop count between selected anchors available for localization5.2
Apply the Least Square Method to transform the minimum hop count into optimized distance by the polynomial approximation5.3
Computation of the minimal hop count between selected anchors and unknown nodes5.4
Apply the polynomial approximation to estimate the distance between anchors (i) and unknown nodes (j): dij=α0+α1hij+α2hij25.5
Positions estimationXm of unknown nodes using the update sequential formula Xk+1=Xk+Sk+1Ak+1TBk+1−Ak+1Xk(6)
end While;(7)
Xm /∗ Estimated position of all unknown nodes m(8)
end;


## 5. Simulation and Results

A localization algorithm should be accurate following the requirement of various location-aware applications such as target tracking, rescue, and fire relief. The extent of matching between the position estimated by the localization algorithm and the real positions defined the term of localization accuracy. As the estimate position is close to the real position, the localization algorithm is as good. As in [63], the requirement on the resolution of the positional accuracy depends on applications. In this section, we discuss the performance of our proposed algorithm and compare it with the original DV-Hop algorithm—literatures [57, 64, 65] algorithms.We assume that all nodes in the network are static, and the location of the anchor node has no deviation. Anchors are equipped with a GPS and thus they are aware of their positions, while the other sensor nodes are not localized. The evaluation of the proposed localization algorithm is performed through simulation using MATLAB R2015a. We randomly deploy different number of sensor nodes in an isotropic 100×100 meters sensing field with a uniform distribution. As shown in Figure 2, red square symbols indicate the anchors, and unknown nodes are marked with black asterisk symbols ∗. We aim to determine an estimated position of the unknown node making it as close as possible to its real position.We assume that every node in the network communicates with each other by the DV-Hop routing protocol in a multihop fashion. The computation of the physical distance from node i to node j can be as follows:(26)dij=xi−xj2+yi−yj2.Figure 2
Network model.The metric that we use to evaluate localization algorithms is the average localization error as in the following equation:(27)Error=∑i=1uxie−xi2+yie−yi2u×R×100%,where xi,yi are real coordinates and xie,yie are estimated coordinates of the i′th unknown sensor node. R is the communication range of nodes in the network and u is the number of unknown nodes. For better results, every data point of all graphs in this paper represents the average value of 100 redeployment experiments (i.e., simulation rounds) with different random topology of sensor network.


### 5.1. Localization Results

Figures3 and 4 exhibit the final estimation results of the sensor nodes by the original DV-Hop algorithm and the proposed localization algorithm, respectively. In the two figures, symbol “∗” denotes the real location of the unknown node. The obtained estimated location by using anchor nodes is presented by the blue symbol “△”. The true node location and its estimation are connected by the red straight line which represents the estimation error.Figure 3
Localization results of DV-Hop algorithm.Figure 4
Localization results of the proposed algorithm.


### 5.2. Analysis of Localization Accuracy

In this section, we present a comparison of our proposed algorithm with the traditional DV-Hop [46], the CC-DV-Hop [64], and the algorithm [65]. On the other hand, we present a second comparison with the parallel efficient projection algorithm (PEPA) [57]. A set of different experiments was done to evaluate and prove the performance of our proposed localization algorithm.


#### 5.2.1. Experiment A: Varying the Number of Anchor Nodes

We randomly deploy 300 nodes in the sensing field. The communication radius of nodes is set to be 20 m. The ratio of anchors is varied from 0.05 to 0.45. Figure5 shows the performance comparison with some localization algorithms from the literature. One can see from this figure that the average of localization errors of the different compared algorithms cited above tends to decrease progressively when the ratio of anchors is between 5% and 25% and it becomes stable over 25% of anchor ratio because the increase of number of anchors helps to reduce the distance between nodes and anchors; thus the information loss will decrease and so it leads to a more precise localization. As observed in Figure 5, the proposed algorithm has the lowest average localization error compared to other localization methods. In fact, the average localization error of CC-DV-Hop is about 35% lower than DV-Hop, and that of the proposed algorithm is 15% lower than CC-DV-Hop.Figure 5
Comparison with different ratios of anchor.Considering a WSN consisting on 200 sensor nodes randomly deployed in a 100× 100 meters square field, each node has a communication range of 6 meters. In this experiment, the number of anchor nodes is varied from 20 to 100. Figure 6 shows the resulted localization error with the variation of anchor node of the DV-Hop algorithm, the parallel efficient projection algorithm (PEPA) [57], and our proposed algorithm. One can see from this figure that the proposed algorithm achieves the lowest localization error when compared with its counterparts.Figure 6
Comparison with different ratios of anchor.


#### 5.2.2. Experiment B: Varying the Number of Deployed Nodes

In this experiment, the percentage of anchor is set to be 30% and the number of deployed nodes is varied from 100 to 400. The communication range of all nodes is about 20 m. Figure7 exhibits a comparison between 4 different localization methods with different number of nodes. We observe that the localization accuracy of CC-DV-Hop in Wang and Nie [64] and the algorithm in Xiao and Liu [65] is improved compared with that of the DV-Hop algorithm. Besides, the proposed algorithm achieves the best accuracy which is about 10% higher than that of CC-DV-Hop, about 16% higher than that of literature [65] algorithm, and about 33% higher than that of the DV-Hop. As a conclusion, our proposed algorithm achieves the best localization accuracy for different network topologies compared with the other three methods.Figure 7
Comparison with different number of nodes.Now, considering a WSN composed of 40 anchor nodes randomly deployed in a 50×50 sensing field, where the communication range of each sensor node is 3 meters, we vary the total amount of sensor nodes from 200 to 1000, and the localization errors of the DV-Hop algorithm, the parallel efficient projection algorithm (PEPA) [57], and our proposed algorithm are shown in Figure 8. As seen from this figure, the localization accuracy of the proposed algorithm is about 58% higher than that of the DV-Hop and about 35% higher than that of the PEPA. Besides, the best localization accuracy is done by the proposed algorithm.Figure 8
Comparison with different number of nodes.


#### 5.2.3. Experiment C: Varying the Communication Radio of Nodes

The third experiment consists of changing the radio range of sensor nodes from 15 m to 55 m. We deployed 300 nodes in the sensing field with a ratio of 30% of anchors. We observe from Figure9 that the average localization error of DV-Hop decreases with the increase of the communication radio, while that of the proposed algorithm is progressively decreasing and that of the other algorithms is practically maintained stable. We can conclude from this observation that the variation of the communication radius has a minimal impact on the proposed algorithm, CC-DV-Hop, and literature [65] algorithm compared with DV-Hop. Moreover, the localization accuracy of the proposed algorithm improves the accuracy of other algorithms. Besides, the average localization error of the proposed method is approximately 30% lower than that of the DV-Hop, approximately 5% lower than that of literature [65] algorithm, and approximately 10% lower than that of CC-DV-Hop.Figure 9
Comparison with different radio range of nodes.Now, we consider 100 sensor nodes randomly distributed in a 50×50 sensing region with a ratio of 15% of anchors. Results are shown in Figure 10. It is so clear that our proposed algorithm is always on the top of localization accuracy when compared with the DV-Hop algorithm and the PEPA.Figure 10
Comparison with different radio range of nodes.


### 5.3. Effect of DOI

In the real WSN deployment scenarios, radio signals are influenced by many facts in the environment such as the noise. As a result, radio communication of sensor nodes does not take the form of standard circle, but rather an anomalous polygon. The degree of irregularity (DOI) model is an irregular radio model proposed by Tian He et al. [32] to characterize the radio signal transmission irregularity. DOI presents the maximal variation of radio range per unit degree change in different radio propagation’s directions. As seen in Figure 11, the transmission range change with the value of DOI. If DOI = 0, the transmission range is an ideal circle. However, when the value of DOI increases, the transmission range irregularity becomes more and more important.Figure 11
Irregular radio patterns for different values of DOI. (a) DOI = 0.01. (b) DOI = 0.07. (c) DOI = 0.1.
(a)(b)(c)The probability of communication established between two nodes separated with a distanced is as follows [11]:(28)Pd=1,dR<1−DOI,12DOIdR−1+12,1−DOI≤dR≤1+DOI,0,dR>1+DOI.To reveal the impact of radio range irregularity on our proposed DV-based localization algorithm and find the relationship between the degree of irregularity (DOI) and the localization accuracy, we realized some simulation experiments, in which we implement our localization algorithm with radio range irregular model.In this experiment, we randomly deploy 100 nodes in an area of100×100 meters. We consider the effect of DOI during simulation; thus nodes are assumed to have different transmission range of radius R. The percentage of anchors is about 5 to 30%. We vary DOI from 0 to 0.07. Figure 12 shows the average localization error of the proposed algorithm for different numbers of anchor nodes and DOI. We can observe from this figure that, with the increase of DOI, i.e., the increase of radio propagation irregularities, the localization error increases. The higher values of DOI lead to making the network less connected. Note that confident estimation is highly reliant on the uniformity of anchors.Figure 12
Comparison of localization errors with different radio range of nodes and different degrees of radio propagation irregularity DOI.


## 5.1. Localization Results

Figures3 and 4 exhibit the final estimation results of the sensor nodes by the original DV-Hop algorithm and the proposed localization algorithm, respectively. In the two figures, symbol “∗” denotes the real location of the unknown node. The obtained estimated location by using anchor nodes is presented by the blue symbol “△”. The true node location and its estimation are connected by the red straight line which represents the estimation error.Figure 3
Localization results of DV-Hop algorithm.Figure 4
Localization results of the proposed algorithm.


## 5.2. Analysis of Localization Accuracy

In this section, we present a comparison of our proposed algorithm with the traditional DV-Hop [46], the CC-DV-Hop [64], and the algorithm [65]. On the other hand, we present a second comparison with the parallel efficient projection algorithm (PEPA) [57]. A set of different experiments was done to evaluate and prove the performance of our proposed localization algorithm.


### 5.2.1. Experiment A: Varying the Number of Anchor Nodes

We randomly deploy 300 nodes in the sensing field. The communication radius of nodes is set to be 20 m. The ratio of anchors is varied from 0.05 to 0.45. Figure5 shows the performance comparison with some localization algorithms from the literature. One can see from this figure that the average of localization errors of the different compared algorithms cited above tends to decrease progressively when the ratio of anchors is between 5% and 25% and it becomes stable over 25% of anchor ratio because the increase of number of anchors helps to reduce the distance between nodes and anchors; thus the information loss will decrease and so it leads to a more precise localization. As observed in Figure 5, the proposed algorithm has the lowest average localization error compared to other localization methods. In fact, the average localization error of CC-DV-Hop is about 35% lower than DV-Hop, and that of the proposed algorithm is 15% lower than CC-DV-Hop.Figure 5
Comparison with different ratios of anchor.Considering a WSN consisting on 200 sensor nodes randomly deployed in a 100× 100 meters square field, each node has a communication range of 6 meters. In this experiment, the number of anchor nodes is varied from 20 to 100. Figure 6 shows the resulted localization error with the variation of anchor node of the DV-Hop algorithm, the parallel efficient projection algorithm (PEPA) [57], and our proposed algorithm. One can see from this figure that the proposed algorithm achieves the lowest localization error when compared with its counterparts.Figure 6
Comparison with different ratios of anchor.


### 5.2.2. Experiment B: Varying the Number of Deployed Nodes

In this experiment, the percentage of anchor is set to be 30% and the number of deployed nodes is varied from 100 to 400. The communication range of all nodes is about 20 m. Figure7 exhibits a comparison between 4 different localization methods with different number of nodes. We observe that the localization accuracy of CC-DV-Hop in Wang and Nie [64] and the algorithm in Xiao and Liu [65] is improved compared with that of the DV-Hop algorithm. Besides, the proposed algorithm achieves the best accuracy which is about 10% higher than that of CC-DV-Hop, about 16% higher than that of literature [65] algorithm, and about 33% higher than that of the DV-Hop. As a conclusion, our proposed algorithm achieves the best localization accuracy for different network topologies compared with the other three methods.Figure 7
Comparison with different number of nodes.Now, considering a WSN composed of 40 anchor nodes randomly deployed in a 50×50 sensing field, where the communication range of each sensor node is 3 meters, we vary the total amount of sensor nodes from 200 to 1000, and the localization errors of the DV-Hop algorithm, the parallel efficient projection algorithm (PEPA) [57], and our proposed algorithm are shown in Figure 8. As seen from this figure, the localization accuracy of the proposed algorithm is about 58% higher than that of the DV-Hop and about 35% higher than that of the PEPA. Besides, the best localization accuracy is done by the proposed algorithm.Figure 8
Comparison with different number of nodes.


### 5.2.3. Experiment C: Varying the Communication Radio of Nodes

The third experiment consists of changing the radio range of sensor nodes from 15 m to 55 m. We deployed 300 nodes in the sensing field with a ratio of 30% of anchors. We observe from Figure9 that the average localization error of DV-Hop decreases with the increase of the communication radio, while that of the proposed algorithm is progressively decreasing and that of the other algorithms is practically maintained stable. We can conclude from this observation that the variation of the communication radius has a minimal impact on the proposed algorithm, CC-DV-Hop, and literature [65] algorithm compared with DV-Hop. Moreover, the localization accuracy of the proposed algorithm improves the accuracy of other algorithms. Besides, the average localization error of the proposed method is approximately 30% lower than that of the DV-Hop, approximately 5% lower than that of literature [65] algorithm, and approximately 10% lower than that of CC-DV-Hop.Figure 9
Comparison with different radio range of nodes.Now, we consider 100 sensor nodes randomly distributed in a 50×50 sensing region with a ratio of 15% of anchors. Results are shown in Figure 10. It is so clear that our proposed algorithm is always on the top of localization accuracy when compared with the DV-Hop algorithm and the PEPA.Figure 10
Comparison with different radio range of nodes.


## 5.2.1. Experiment A: Varying the Number of Anchor Nodes

We randomly deploy 300 nodes in the sensing field. The communication radius of nodes is set to be 20 m. The ratio of anchors is varied from 0.05 to 0.45. Figure5 shows the performance comparison with some localization algorithms from the literature. One can see from this figure that the average of localization errors of the different compared algorithms cited above tends to decrease progressively when the ratio of anchors is between 5% and 25% and it becomes stable over 25% of anchor ratio because the increase of number of anchors helps to reduce the distance between nodes and anchors; thus the information loss will decrease and so it leads to a more precise localization. As observed in Figure 5, the proposed algorithm has the lowest average localization error compared to other localization methods. In fact, the average localization error of CC-DV-Hop is about 35% lower than DV-Hop, and that of the proposed algorithm is 15% lower than CC-DV-Hop.Figure 5
Comparison with different ratios of anchor.Considering a WSN consisting on 200 sensor nodes randomly deployed in a 100× 100 meters square field, each node has a communication range of 6 meters. In this experiment, the number of anchor nodes is varied from 20 to 100. Figure 6 shows the resulted localization error with the variation of anchor node of the DV-Hop algorithm, the parallel efficient projection algorithm (PEPA) [57], and our proposed algorithm. One can see from this figure that the proposed algorithm achieves the lowest localization error when compared with its counterparts.Figure 6
Comparison with different ratios of anchor.


## 5.2.2. Experiment B: Varying the Number of Deployed Nodes

In this experiment, the percentage of anchor is set to be 30% and the number of deployed nodes is varied from 100 to 400. The communication range of all nodes is about 20 m. Figure7 exhibits a comparison between 4 different localization methods with different number of nodes. We observe that the localization accuracy of CC-DV-Hop in Wang and Nie [64] and the algorithm in Xiao and Liu [65] is improved compared with that of the DV-Hop algorithm. Besides, the proposed algorithm achieves the best accuracy which is about 10% higher than that of CC-DV-Hop, about 16% higher than that of literature [65] algorithm, and about 33% higher than that of the DV-Hop. As a conclusion, our proposed algorithm achieves the best localization accuracy for different network topologies compared with the other three methods.Figure 7
Comparison with different number of nodes.Now, considering a WSN composed of 40 anchor nodes randomly deployed in a 50×50 sensing field, where the communication range of each sensor node is 3 meters, we vary the total amount of sensor nodes from 200 to 1000, and the localization errors of the DV-Hop algorithm, the parallel efficient projection algorithm (PEPA) [57], and our proposed algorithm are shown in Figure 8. As seen from this figure, the localization accuracy of the proposed algorithm is about 58% higher than that of the DV-Hop and about 35% higher than that of the PEPA. Besides, the best localization accuracy is done by the proposed algorithm.Figure 8
Comparison with different number of nodes.


## 5.2.3. Experiment C: Varying the Communication Radio of Nodes

The third experiment consists of changing the radio range of sensor nodes from 15 m to 55 m. We deployed 300 nodes in the sensing field with a ratio of 30% of anchors. We observe from Figure9 that the average localization error of DV-Hop decreases with the increase of the communication radio, while that of the proposed algorithm is progressively decreasing and that of the other algorithms is practically maintained stable. We can conclude from this observation that the variation of the communication radius has a minimal impact on the proposed algorithm, CC-DV-Hop, and literature [65] algorithm compared with DV-Hop. Moreover, the localization accuracy of the proposed algorithm improves the accuracy of other algorithms. Besides, the average localization error of the proposed method is approximately 30% lower than that of the DV-Hop, approximately 5% lower than that of literature [65] algorithm, and approximately 10% lower than that of CC-DV-Hop.Figure 9
Comparison with different radio range of nodes.Now, we consider 100 sensor nodes randomly distributed in a 50×50 sensing region with a ratio of 15% of anchors. Results are shown in Figure 10. It is so clear that our proposed algorithm is always on the top of localization accuracy when compared with the DV-Hop algorithm and the PEPA.Figure 10
Comparison with different radio range of nodes.


## 5.3. Effect of DOI

In the real WSN deployment scenarios, radio signals are influenced by many facts in the environment such as the noise. As a result, radio communication of sensor nodes does not take the form of standard circle, but rather an anomalous polygon. The degree of irregularity (DOI) model is an irregular radio model proposed by Tian He et al. [32] to characterize the radio signal transmission irregularity. DOI presents the maximal variation of radio range per unit degree change in different radio propagation’s directions. As seen in Figure 11, the transmission range change with the value of DOI. If DOI = 0, the transmission range is an ideal circle. However, when the value of DOI increases, the transmission range irregularity becomes more and more important.Figure 11
Irregular radio patterns for different values of DOI. (a) DOI = 0.01. (b) DOI = 0.07. (c) DOI = 0.1.
(a)(b)(c)The probability of communication established between two nodes separated with a distanced is as follows [11]:(28)Pd=1,dR<1−DOI,12DOIdR−1+12,1−DOI≤dR≤1+DOI,0,dR>1+DOI.To reveal the impact of radio range irregularity on our proposed DV-based localization algorithm and find the relationship between the degree of irregularity (DOI) and the localization accuracy, we realized some simulation experiments, in which we implement our localization algorithm with radio range irregular model.In this experiment, we randomly deploy 100 nodes in an area of100×100 meters. We consider the effect of DOI during simulation; thus nodes are assumed to have different transmission range of radius R. The percentage of anchors is about 5 to 30%. We vary DOI from 0 to 0.07. Figure 12 shows the average localization error of the proposed algorithm for different numbers of anchor nodes and DOI. We can observe from this figure that, with the increase of DOI, i.e., the increase of radio propagation irregularities, the localization error increases. The higher values of DOI lead to making the network less connected. Note that confident estimation is highly reliant on the uniformity of anchors.Figure 12
Comparison of localization errors with different radio range of nodes and different degrees of radio propagation irregularity DOI.


## 6. Conclusion

In this paper, a new improved algorithm has been proposed to optimize the localization accuracy of DV-Hop for random topology networks. Our proposed algorithm is an improvement of DV-Hop algorithm by a localization estimation based on an online sequential position computation and an optimized computation of the average hop distance of nodes. The performance of the proposed algorithm is well proved through simulation results comparing with DV-Hop, CC-DV-Hop, literature [65] algorithm, and the parallel efficient projection algorithm (PEPA) [57]. Besides, the localization precision of our proposed algorithm is better than that of the other four compared localization techniques at various random topologies of WSN.For future work, noting that network lifetime is a very important issue in WSN, we plan to find a trade-off between localization accuracy and energy consumption for our proposed algorithm.



---

*Source: 8195309-2020-10-20.xml*