An Improved DV-Hop Localization Algorithm Based on Hop Distances Correction

Guiqi Liu,Zhihong Qian＊,Xue Wang

College of Communication Engineering,Jilin University,Changchun 130012,China

Abstract: DV-Hop localization algorithm has greater localization error which estimates distance from an unknown node to the different anchor nodes by using estimated average size of a hop to achieve the location of the unknown node.So an improved DV-Hop localization algorithm based on correctional average size of a hop,HDCDV-Hop algorithm,is proposed.The improved algorithm corrects the estimated distance between the unknown node and different anchor nodes based on fractional hop count information and relatively accurate coordinates of the anchor nodes information,and it uses the improved Differential Evolution algorithm to get the estimate location of unknown nodes so as to further reduce the localization error.Simulation results show that our proposed algorithm have lower localization error and higher localization accuracy compared with the original DV-Hop algorithm and other classical improved algorithms.

Keywords: WSN; DV-Hop localization algorithm; Hop Distance Correction; improved Differential Evolution algorithm

I.INTRODUCTION

In recent years,with the development of Internet of Things (IoT) [1],wireless network technology has unprecedented development,such as Wireless Sensor Networks (WSN) localization and routing technology [2-4],Radio Frequency Identification (RFID) anti-collision technology [5-7],OFDM technology [8-10]and so on.Due to large-scale,self-organization,reliability and other advantages,WSN have been proposed for numerous location-dependent applications.In many IoT and other applications,the information produced by an individual entity or node is generally meaningless without its location information.WSN with location information can be applied to geo-based routing protocols,location-aware services,target tracking,remote monitoring,search and rescue and intelligent environment [11-13].For a network with thousands of nodes,it is impossible to preconfigure the position of each node.Generally,we can get the position of node by equipping a global positioning system (GPS) for the node.But the embedded GPS module which is expensive and more energy consuming limits the application of GPS in WSN.So a more suitable method is proposed.In WSN,a small number of sensor nodes (called anchor nodes) are embedded GPS module in order to get nodes position information,and the remaining nodes without position coordinates information(called unknown nodes) can estimate their positions using the position information of the anchor nodes and the connectivity information between nodes.

Many localization algorithms for WSN have been proposed recently [14-20].These localization algorithms include two categories:range-based localization algorithm or rangefree localization algorithm [21-22].The rangebased localization algorithm gets the distance from sensor nodes to different sensor nodes using measuring information,such as Received Signal Strength Indicator (RSSI),Time of Arrival (TOA),Time Difference of Arrival(TDOA),and Angle of Arrival (AOA).Once the distance information is obtained,the location of unknown nodes can be estimated using the distance information.The measuring information can be affected by multipath and noise.And,range-based localization methods need additional hardware to get measure information.So,range-based localization methods are impractical for the resource-constrained WSN.For the disadvantage of range-based methods,many range-free localization methods have been researched,such as DV-Hop algorithm,APIT algorithm,Centroid algorithm and so on.The ranged-free methods estimate location of unknown nodes based on node connectivity and hop count information.The advantage is that the sensor nodes in WSN do not need to configure additional hardware.And the rangefree localization methods are more suitable for resource-constrained WSN.However,the major drawback of the ranged-free schemes is that localization error is large.

The DV-hop algorithm is one of the rangefree localization algorithms which use average size of a hop and minimum hop count for location estimation.Although it has a good feasibility and coverage,but it has the disadvantage of the larger localization error and lower localization accuracy.The error sources of the DV-hop algorithm mainly have three aspects:the localization error is introduced by the minimum hop count information; the localization error is introduced by the average size of a hop; the localization error is introduced by the calculation method of the unknown node coordinates.For these disadvantages,the researchers did a lot of research.In [23],they proposed the IDV-Hop,which averages whole of the hop-size of different anchor nodes in the network.Meanwhile,they used 2-D hyperbolic algorithm to solve the position coordinates of the unknown node instead of triangulation algorithm.In [24],authors used weighted least square (WLS) algorithm in position to solve the step of the original DV-Hop.In this way,distance estimated error from anchor node to unknown node is reduced.In [25],authors presented Checkout DV-hop algorithm and Selective 3-Anchor DV-hop algorithm.Checkout DV-hop algorithm get the node estimate coordinates by the nearest anchor nodes information,and Selective 3-Anchor DV-hop algorithm gets better localization accuracy by choosing the best 3 anchors.In [26],they merged a WDV-Hop localization algorithm with the WH(weighted hyperbolic) localization algorithm which gets better localization accuracy.

A new DV-Hop localization algorithm,HDCDV-Hop localization algorithm,is proposed to solve the problem that the original DVHop algorithm has high localization error and low localization accuracy.

In this paper,we focus on DV-Hop algorithm only,and propose an improved DVHop localization algorithm,HDCDV-Hop localization algorithm,based on hop distance correction.In this HDCDV-Hop algorithm,we focus on reducing the distance estimation error mainly,because it is the main error source of the DV-Hop algorithms.There are four main contributions in this paper.Firstly,The distributed DV-Hop algorithm is combined with the centralized processing DE algorithm,which makes full use of the flexibility,high efficiency of distributed processing and the powerful processing power of centralized processing.In the early stage of the positioning algorithm,the distributed processing method is used to obtain the distance from the unknown node to all the anchor nodes.In the later stage of the algorithm,the centralized node processing method is used to obtain the unknown node coordinates.Secondly,the wireless radiation range is divided into two segments by analyzing the wireless radio model,so fractional hop count was introduced.Thirdly,the correction factor is introduced to modify the average size of a hop to reduce the distance estimation er-ror further.Fourthly,the improved Differential Evolution algorithm (DE algorithm) is used to solve unknown node coordinates to reduce localization error and speed up convergence.The simulation results prove that the performance of our proposed algorithm offers a better performance compared to original DV-Hop algorithm and classical improved DV-Hop localization algorithm for WSN.

The rest of this paper is organized as follows.Section II illustrates original DV-Hop localization algorithms and the radio model.Section III describes the specific improvements for DV-Hop localization algorithm,and gives the specific steps of our improved algorithm.In Section IV,the feasibility of the proposed algorithm is verified,two parameters are simulated and analyzed,and the optimal solution is obtained.Then we compared the localization performances of different algorithms.Section V is our conclusions and future plan.

II.WIRELESS RADIATION MODEL

By analyzing the wireless radiation model,we give the RSS boundary value and the distance boundary value in order to further introduce the fractional hop count.

In natural environments environment,the radiation pattern is not a regular circle due to the presence of physical obstacles,multi-path fading and other environmental factors.Tian He[27]introduced a parameter DOI to denote the irregularity of a radio pattern.And Gang Zhou,Tian He[28]proposed a Radio Irregularity Model (RIM).The DOI parameter is defined as the maximum path loss percentage variation per unit degree change in the direction of radio propagation.When the DOI is set to 0,there is no range variation,and the communication range is a perfect sphere.However,with the constant increase of DOI value,the communication range becomes more and more.

We introduced the RIM model to analyze the radiation range of the sensor node.In general,the self-localization process of the sensor node occurs before the WSN performs the specifictasks.At this time,the hardware configuration of the sensor node is factory set.So,it can be considered that in the case of obtaining the same communication radius,the required transmission power is the same.

The RIM model adjusts the value of path loss models based on DOI value,which is represented as follows:

Where,RSSis the received signal strength,Psis the sending power,PLDOIis DOI adjusted path loss,Fadingis the fading exponent.AndKiis a coefficient to represent the difference in path loss in different directions.Specifically,Kiis thei-th degree coefficient,which is calculated as follows:

Where,|K0-K359|≤DOI.We can generate 360Kivalues for the 360 different directions,based on Equation (2).

Both theoretical analysis and actual measurement indicate that average received signal strength decreases logarithmically with distance.The path loss model is as follows:

wheredis the communication distance between the sender sensor and receiver sensor.PL(d) is the power loss corresponding tod.d0is a reference distance,andPL(d0) is the power loss corresponding tod0.ηis the path loss exponent.Xσindicates the logarithmic shadow effect,and obeys a Gaussian random variable,Xσ～N(0,σ2).

Thus,when the communication distance isd,the received signal strengthRSS(d) can is calculated as follows:

For the RIM model,parameters in the formula are set to some empirical values:PL(1)=50dbm,η=3,σ=4,DOI=0.02 and the receiving sensitivity of sensor nodes is set to-97dbm.Through a large number of simulation experiments,the radiation range of the RIM model is analyzed.We get the required sending power is about -3dbm,-1dbm,1dbm,3dbm,5dbm,when the radiation radius is 25m、30m、35m、40m、45m.Take the radiation radius = 30m as an example,the RSS changes are analyzed at different distances and in different directions.We have chosen 6 directions with an interval of 60 degrees,as shown in Figure 1.Other directions have also been simulated many times.The same result was obtained.

As can be seen from this figure 1,whenRSS≥ -85dbm,the size of the RSS value approximately satisfies the path loss model(Equation(3)),theRSSare exponentially attenuation with the increasing communication distanced.And there are few irregular fluctuations.WhenRSS＜ -85dbm,the received RSS value is unstable.A large number of irregular disturbances were found.And the path loss model is no longer satisfied.We introduce two symbols:RSS_BV andDist_BV.RSS_BVis used to represent this boundary value ofRSS.HereRSS_BV =-85dbm.Dist_BVrepresents distance boundary value corresponding to the boundary value of RSS.According to the path loss model and the RIM model,when the RSS value received by the node is -85dbm,the distance between the transmitting node and the receiving node is about 14 m.HereDist_BV=14m.A large number of simulation experiments show that this boundary value ofRSSis -85dbm in the case of different radiation radius,when DOI=0.02.

Fig.1.The RSS in different directions.

III.DETAILS OF HDCDV-HOP ALGORITHM

HDCDV-Hop algorithm mainly innovate the hop distance estimation stage and unknown node coordinate solving stage of the original algorithm.

3.1 DV-Hop localization algorithm

The classic DV-Hop algorithm [29]consists of the following three steps:

Step1:Through the typical distance vector protocols,all the unknown nodes get the minimum value of hop between itself and all anchor nodes in the network,and all the anchor nodes get the location information and the minimum value of hop between itself and all anchor nodes in the network.

Step2:After getting the location information and the minimum hop count to other anchor nodes,each anchor node calculates the average size of a hop,AvgHopDisti,by Ep.(5).

Where (xi,yi) and (xj,yj) are the coordinates of anchor nodeiand anchor nodej,andhijrepresents the minimum hop count between anchor nodeiandj.Then all the anchor nodes broadcast theAvgHopDistiin the entire network in the form of flooding.The unknown nodes only save theAvgHopDistireceived for the first time.And theAvgHopDistiis considered to be from the nearest neighbor anchor node.Then the unknown nodes calculate the distance to all the anchor nodes by Ep.(2).

WhereAvgHopDistpis the average size of a hop which is received by the unknown nodenfrom the nearest anchor nodep,andhniis the minimum hop count between unknown nodenand anchor nodei.

Step 3:After getting the distance to three or more anchor nodes,the unknown node calculates the coordinates of it using the trilateral measurement or the maximum likelihood estimation method.

3.2 Hop distance correction

In original DV-Hop localization algorithm,as long as two nodes are within the wireless transmission range of each other,the hop count is1and the distance between the two nodes is approximately1*R(Ris the node radiation radius).But this doesn't take into account the actual distance between the two nodes.If the two nodes are closer,a greater error will be generated.In order to make the hop distance estimation more reasonable,on the basis of keeping the original minimum hop count calculation method,we introduced the fractional hop count.

Through the analysis of the RIM model,there is always aRSS_BVand aDist_BVfor a given communication radius and DOI value.For this reason,the communication range is divided into two levels,and fractional hops are introduced.When the received RSS value is more than the boundary value of RSS,it is the first-level RSS.When the received RSS value is less than the boundary value of RSS,it is the second-level RSS.The sensor nodes obtain the fractional hop count by judging the signal strength of the received packet.In order to relief the instability of RSS,the averageRSSare obtained after receiving multiple packets from the same sensor node.When the average RSS ≥RSS_BV,the RSS meets the first-level RSS and the fractional hop value isDist_BV/R.When the averageRSS＜RSS_BV,the RSS meets the second-level RSS and the fractional hop value is 1.Figure 2 gives the fractional hop value when communication radius is 30m and DOI is 0.02.Blue spot represents the sensor node.The hop count from the nodenton1andn2is 14/30 and 1,respectively.

In the original DV-Hop algorithm,the unknown node uses the average size of a hop of the nearest anchor node as its own average size of a hop.At the same time,the average size of a hop is also used to solve the hop distance of the unknown node to other anchor nodes.This will ignore the differences between the anchor nodes in the network.The unknown node uses the same average size of a hop to solve the hop distance between the unknown node and the different anchor nodes,and this can't effectively reflect the overall situation of WSN.In general,the nearest neighbor node of unknown node can approximate the surrounding environment of this unknown node.Therefore,the position relation between the unknown node and the remaining anchor nodes can be approximated by the positional relationship between the nearest neighbor anchor node and the rest of the anchor nodes.For this reason,all the anchor nodes in the network are divided into two categories: the nearest neighbor anchor node and the remaining anchor nodes.If the anchor node is the nearest neighbor anchor node,the unknown node calculates the hop distance to this anchor node by using original method by Eq.(6).When the anchor node is not the nearest neighbor anchor node,the unknown node uses different average size of a hop to calculate the hop distance to anchor.The average size of a hop from unknown nodento anchor nodeiis calculated by Eq.(7).

Wheredpiis the distance between the nearest neighbor anchor nodepand a remaining nodei,andhpiis the minimum fractional hop count from the nodepto the nodei,andAvgHopDistpis the average size of a hop of this unknown node received for the first time,which we call the reference average size of a hop.Since the coordinates of anchor nodes are known,dpiis relatively accurate.Therefore,was introduced to correct the average size of a hop.Unknown nodes correct the hop distance of itself to different anchor nodes by getting the different average size of a hop,making them closer to the actual situation of WSN and reducing the error introduced by using hop distance instead of actual distance.

A parameterβis introduced,and named correction factor.It is calculated as follows:

An example of the average size of a hop for an unknown node to two different anchor nodes is shown in Figure 3,nis a unknown node,andpis the nearest neighbor anchor node of the noden,qis one of the remaining anchor nodes.For the nodep,theAvgHopDistpis done by Eq.(5).And the hop distance from the nodento the nodepis done by Eq.(6).But in the Eq.(5) and Eq.(6),thehijandhniare the minimum fractional hop count.

For the nodeq,the average size of a hop is done by Eq.(9).

Fig.2.The fractional hop count decision method.

Fig.3.An example of the AvgHopDist for an unknown node.

Wheredpqis the distance anchor nodepandq,andhpqis the minimum fractional hop count between nodepand nodeq.The hop distance from the nodento nodeqis done by Eq.(10).

3.3 Improvement of coordinate solution method

In the third stage of the HDCDV-Hop algorithm,an improved DE algorithm is adopted.Based on the corresponding relationship between population and sensor nodes,the DE algorithm can be used in WSN.The process of population evolution is the process of solving the optimal location of the unknown nodes.

The DE algorithm [30]regards the population as a whole.There are three crucial control parameters: Population sizeN,Scaling factorF,Crossover rateCR.Population sizeN,corresponding to the number of unknown nodes,is the number of individuals in the population.The individualgi(i=1,2,…,N),corresponding to the coordinates of unknown nodes,is a 2 dimensional vector.These two elements of this vector arexiandyi(i=1,2,…,N).In population,these two elements (xi,yi) are called two gene fragments,corresponding to the coordinates of unknown nodei.In this population,the individual 3 can be expressed asg3=(x3,y3).Scaling factorFis a control parameter for scaling the difference vector.By adjusting the size of the value,the scaling step size can be effectively controlled.Generally,the range of the scaling factor is [0.4,1].Crossover rateCRcontrols the crossover process.It controls the number of the gene fragment copied from the mutant vector to the trial vector.TheDEalgorithm has three basic operations: mutation,crossover and selection.Mutation is the process of obtaining the mutant vector.Crossover is the process of getting the trial vector.Gene fragments are randomly extracted from the target vector and mutation vector,and are recombined into trial vectors.Selection is the process of comparing the fitness of the trial vector with the target vector.And the individual with better fitness is retained.In DE algorithm,the target individual is the individual who is ready to perform evolution.The individual obtained by selection is the offspring individual.

Two problems need to be considered when the DE algorithm is applied to the WSN location problem.The first,since the scaling factorFis constant,so the DE algorithm is easy to fall into local optimum.The second,mapping an individual to an unknown node highlights the impact of the evolutionary process on the positioning results.For these two problems,the following improvements have been made to the DE algorithm:

1) The fixed scaling factorFis changed to the gradient value.Based on the range of empirical values of the scaling factor and the number of iterations of the DE algorithm,the attenuation law is as follows：

Where,Tis the total number of evolution,and is also the number of iterations.tindicates that the current evolutionary process is thet-th generation.When the scaling factor is large,the algorithm performs a global search.As the scaling factor gradually decreases,the algorithm slowly performs a partial search.

2) Assign three population individuals to one unknown node in WSN.If the number of unknown nodes isN,the population size should be3N.The three individuals perform DE separately and get three results.The average of these three results is the coordinates of the corresponding unknown node.

The application of DE algorithm in WSN location is shown in Figure 4.The location solution process of the unknown nodenis taken as an example.

Step1:Initialization

The number of unknown nodes in the network isN.The number of individuals in the population is 3N.One unknown node corresponds to three individuals.And the initial values of the three individuals are set to the coordinates of the anchor node closest to this unknown node.Other parameters are set,such asCR=0.5,F1=1,T=100.

Step2:Mutation operation

The purpose of the mutation is to obtain the mutant individual of the target individual.Fort-th generation individualgit=(xit,yit),two different individualsgijt=(xjt,yjt) andgikt=(xkt,ykt) (j≠k),are extracted randomly fromt-th generation population.The difference vector of individualgitis obtained by Eq.(11).

The mutant vectorVgitof individualgitis obtained by Eq.(12).

Step3:Crossover operation

The purpose of the crossover is to get the trial individualUgitof the target individualgit.Binomial crossover is used to obtain the trial vector.The gene fragments of individualgitarexitandyit.The gene fragments of mutant individualVgitarexit+F(xijt-xikt) andyit+F(yijt-yikt).These gene fragments are recombined to obtain the trial vectorUgit.Two gene fragments of this trial individual areugijt(j=1,2),and are obtained by Eq.(13).

Where,vgijtare gene fragments of the mutant vectorVgit,andvgi1t=xit+F(xijt-xikt),vgi2t=yit+F(yijt-yikt).xgijtare gene fragments of the target vectorgit.Andxgijt=xit,xgijt=yit.When determining each gene fragment of this trial individual,a random numberrandwas generated within the range [0,1].Whenrand≤CR,this gene fragment is copied from mutant vectorVgit,otherwise it comes from the target vectorgit.For example,forugi1t,ifrand≤CR,thenugi1t=vgi1t,otherwiseugi1t=xgijt.At the same time,in order to ensure the diversity of the population,a random integercrwithin [1,2]is generated,wherecr=1 or 2.Let thecr-th gene fragment of this trial vector be provided by the mutated vectorVgit.This means that at least one of the gene fragments in this trial individual is from a mutant vectorVgit.For example,ifcr= 2,ugi2t=vgi2t.

According to the principle of crossover,this trial vector has three possible:Vgit=(xit+F(xijt-xikt),yit+F(yijt-yikt)),u1=(xit+F(xijt-xikt),yit),u1’=(xit,yit+F(yijt-yikt)).The probability of the emergence of these three trial vectors is determined byCR.

Step4:Selection operation

The purpose of the selection is to select individuals with better fitness value as the next generation of the target individualgit.

In the localization algorithm,the smaller the localization error is,the better the fitness of the unknown node is obtained.However,since the actual location of the unknown node is unknown,the fitness function can't be expressed by the localization error.Therefore,for the HDCDV-Hop algorithm,fitness value of this trial vector is obtained by Eq.(14).

WhereMis the number of anchor nodes in the WSN,ugi1tandugi2tare gene fragments of trial vectorUgit.xBmandyBmrepresent the abscissa and ordinate of them-th anchor node.dgimrepresents the hop distance from the unknown node corresponding to the target individualgitto the anchor nodem,which is obtained in the second stage of the HDCDV-Hop algorithm.

Comparing the fitness function of the target vectorgitwith the trial vectorUgit,the individual vector with smaller fitness values are retained.A smaller fitness value means the distance from the vector to anchor nodes is closer the distance from the corresponding unknown node to these anchor nodes.For an individual vector with better fitness,it is assumed that its gene fragments are closer to the coordinates of the corresponding unknown node.So the individual vector is preserved to perform the (t+1)-th generation evolution.

Fig.4.The DE algorithm applied in WSN localization.

All 3Nindividuals in this population are performed mutation,crossover,and selection simultaneously.And the evolution process ends,when a given number of iterations is reached.When the evolution process is complete,3Noffspring individual vectors are obtained.One unknown node's coordinates are the average of the 3 offspring individual vectors corresponding to this unknown node.

3.4 HDCDV-Hop algorithm description

The steps of the improved algorithm are as follows:

Fig.5.An example for the step1.

Step1:Get the hop count information.The anchor node broadcasts the packet containing its own location coordinates and hop count information in a flooding manner,and the hop count contains integer hop count and fractional hop count.The packet structure is{ID,integer hop,fractional hop}.The initial value of the integer hop is 1,and the initial value of the fractional hop is 0.The unknown node receives the packet and judges whether or not the packet of the anchor node has been received and recorded.If it has already been received,the integer hop count is compared,and if the newly received integer value is greater than that has been recorded,the packet is discarded.Otherwise,the fractional hop count of the newly packet is calculated by using the RSSI and accumulated and recorded.And when the newly received integer value is equal to that which has been recorded,smaller fractional hop count is recorded.And when the newly received integer value is smaller than that which has been recorded,the integer hop count value and the fractional hop count value are updated together by newly value.Then the integer hop count plus 1 is forwarded.If the packet of the anchor node is not received,the fractional hop count is calculated and recorded,and the initial integer hop count is recorded for the first time,and then the initial integer hop count plus 1 is forwarded.Figure 5 shows an example for the step1.Here,we use numbers to represent ID of nodes.The fractional hop count is marked in Figure 5.

The unknown node 8 receives the packet from the anchor 1 by multi-hop approach.Suppose that there are three links to meet the network conditions,1-1-2-3-8,1-4-5-8,1-6-7-8,and the unknown 8 receives the packet from the link 1-4-5-8.The packet {1,3,58/30} is recorded.For the link 1-1-2-3-8,the integer hop count value is greater,so the packet from this link is discarded.For the link 1-6-7-8,the fractional hop count is greater,so the packet from this link is discarded.

Step2:Solve the hop distance from the unknown node to the anchor node.Each anchor node uses the fractional hops to solve the referenceAvgHopDistby Eq.(5).The unknown node saves theAvgHopDistof the nearest neighbor anchor nodes,and calculates theAvgHopDistfor the remaining anchor nodes by Eq.(7).Then the Eq.(6) and the Eq.(7)is used to calculate the distance from the unknown nodes to the anchor nodes,and the hop distance matrix is achieved.

Step3:The unknown node uses the improved DE algorithm to estimate its own coordinates.

IV.NUMERICAL SIMULATION AND ANALYSIS

4.1 Simulation setting

In order to verify the performance of HDCDV-Hop algorithm,the algorithm is simulated and compared with the original DV-Hop and the classical improved DV-Hop algorithm.Through the comparison and analysis of the simulation results,the simulation parameters can be selected so that the HDCDV-Hop algorithm can optimize the performance to a certain extent.The simulation software is MATLAB2010a.

Based on the characteristics of WSN sensor nodes randomly distributed,WSN nodes are randomly generated within the specified network,and Table1 gives the specificparameters for simulation.In the absence of special instructions,fractional hop counts are obtained when DOI=0.02.

The performance of the localization algorithm in WSN is mainly determined by the average localization error and the localization accuracy.The average localization error is the average of all unknown node errors in the network.The localization accuracy is the degree of approximation between the estimated coordinates and their true coordinates.Here,the localization accuracy is expressed by the average localization error divided by the radiation radius.The formulas are as follows:

WhereNis the number of unknown nodes in the WSN,(xi,yi),(xi’,yi’) represent the actual coordinates of the unknown nodes in the WSN and the estimated coordinates obtained by the algorithm respectively,and R is the radiation radius of the nodes.Through simulation analysis for the evaluation index,the performance ofthe algorithm can be judged more intuitively.

TableI.Parameters being used.

4.2 HDCDV-Hop feasibility veri fication

To verify the impact of fractional hop count on the DV-Hop algorithm,we compared the localization accuracy of the DV-Hop algorithm with fractional hop count (FDV-Hop) and the original DV-Hop algorithm.When DOI is 0.02 and the radiation radius of the node is 30m,the localization accuracy of the two algorithms is shown in the Figure 6.As can be seen from this figure,the introduction of fractional hop count can improve the localization accuracy.

When the DOI value is different,the division of the radiation range is different,and different fractional hop values are obtained.Figure 7 shows the variation of localization accuracy of the HDCDV-Hop with different DOI values.When DOI=0.02,the radiation range of the node is 30m.When DOI＜0.02,only the segmentation of radiation range is affected,which affects the fractional hop value.At this time,localization accuracy does not change significantly.However,when the DOI value is greater than 0.02,both the radiation range of the node and the segmentation of the radiation range are affected,and the localization accuracy changes significantly.

Figure 8 shows a comparison of the dv-hop algorithm with the correction factor (CDVHop) and the original dv-hop algorithm.When ratio of anchor node is small,become inaccurate,the introduction of the correction factor did not improve the localization accuracy.When ratio of anchor node exceeds 10%,CDV-Hop has better localization accuracy.

The effect of hop distance estimation error on localization results can be mitigated when the DE algorithm is applied in the localization phase.Add a certain error to the distance between the actual unknown node and the anchor node,observe the influence of maximum likelihood estimation method (MLE) and DE algorithm on localization accuracy.When the distance error increases,the positioning accuracy of both algorithms deteriorates,but the positioning accuracy of the DE algorithm changes slowly,as shown in Figure 9.

4.3 Algorithm performance

Fig.6.The effect of fractional hop count.

Fig.7.The effect of DOI.

Fig.9.The effect of distance error.

There are two important parameters in the WSN location algorithm: the ratio of the anchor nodes to the all the sensors nodes and the radiation radius of the nodes.The two parameters can directly affect the performance of the localization algorithm.In theory,the greater the proportion of anchor nodes,the better the positioning effect.However,due to the reason that the anchor node is embedded GPS device or other positioning equipment,it makes the cost of the anchor node greatly increased,and the cost of the entire WSN will greatly increase.So the appropriate proportion of anchor nodes should be set to improve the localization accuracy while ensuring network costs.When the radiation radius is small,the number of anchor nodes that the unknown node can receive is few.The coordinates of the unknown node are not easy to be determined.When the radiation radius is large,the localization error of the unknown node will be too large.Therefore,reasonable allocation of anchor node ratio and node radiation radius is an important means to get the advantages of the algorithm.In this paper,the simulation results are used to select the specificvalue of the two parameters,and the localization performance of the algorithm is optimized.

4.3.1 Set the anchor node ratio

Firstly,we observe the effect of different anchor nodes ratio on the localization error and localization accuracy.Set the radiation radius of the node to 25m and the anchor node ratio from 5% to 40%,with 5% as the interval.The simulation results show that the influence of the ratio of the anchor nodes on the performance of the HDCDV-Hop algorithm and the original DV-Hop algorithm,and consistent with the theoretical analysis,as shown in Figure 10 and Figure 11.When the proportion of the anchor nodes is increasing,the localization error of the two algorithms is reduced,while localization accuracy has improved.Through the analysis of multiple simulation experiments,when the ratio of anchor nodes is ≤25%,it is found that the localization error and the localization accuracy are greatly improved along with the increase of the ratio of anchor nodes.When the ratio of anchor nodes is ≥35%,increasing the ratio of anchor nodes,localization error and localization accuracy improvement is not obvious,but the localization system costs will increase significantly.Therefore,in the practical application,the ratio of anchor nodes configured [25%,35%]will be able to meet the localization accuracy and network cost requirements.It can be seen from the figures that the improved algorithm has better localization accuracy and lower localization error than the original DV-Hop algorithm.

Fig.11.Localization accuracy (R=25).

4.3.2 Set the radiation radius

Fig.10.Localization error (R=25).

Fig.12.Localization error.

Fig.13.Localization accuracy.

Fig.14.Localization accuracy.

Through the simulation analysis of localization error and localization accuracy for different radiation radius,the appropriate radiation radius is selected for the localization system,when the anchor node ratio is 30%.Figure 12 and Figure 13 show the localization error and localization accuracy of HDCDV-Hop when the radiation radius is 25m,30m,35m,40m,45m.From figure 13,when the node radiation radius increases,the localization accuracy increases.After the evolution is complete,the localization accuracy is 18.07%,14.93%,13.43%,12.30% and 11.79%,respectively,corresponding to the radiation radius of 25m,30m,35m,40m and 45m.From figure 12,when the radiation radius is small (25m-30m),the localization error decreases with the increase of the radiation radius.When the radiation radius increases (35m-45m),the localization error of the algorithm continues to increase.Because the localization error is the result of the combination of the localization accuracy and the radiation radius,when the radius is large,the influence of the radiation radius on the localization error occupies a major position.After the evolution is complete,the average localization error of the algorithm is 4.517m,4.478m,4.701m,4.921m and 5.304m,respectively,corresponding to the radiation radius of 25m,30m,35m,40m and 45m.Through the comprehensive analysis of figure 12 and figure 13,when the radiation radius of the node is set to 30-35m,the algorithm can obtain high localization accuracy and small localization error.

4.3.3 Algorithm comparison

Through the analysis of the simulation results,we set the node radiation radius to 30m.We compare the HDCDV-Hop algorithm with the DEDV-Hop localization algorithm and the classical improved DV-Hop algorithm in different anchor nodes ratio.The classical improved DV-Hop algorithm proposed in reference [23]corrects the average size of a hop by averaging the average size of a hop of different anchor nodes.DEDV-Hop algorithm applies the DE algorithm to the localization solving process.The localization accuracy of three algorithms is showed in Figure 14.When the ratio of anchor nodes is 30%,the localization accuracy of the HDCDV-Hop algorithm achieves 15.18%.HDCDV-Hop algorithm gets a better location effect.

V.CONCLUSION

A new DV-Hop localization algorithm,HDCDV-Hop localization algorithm,is proposed to solve the problem that the original DV-Hop algorithm has high localization error and low localization accuracy.The algorithm corrects the distance estimation from unknown nodes to anchor nodes by introducing fractional hops and correction factors.At the same time,in the localization stage,the improved DE algorithm is used to solve the unknown node location.In the case of selecting the appropriate parameters,by comparing the DEDV-Hop algorithm,and the classical improved DV-Hop algorithm,HDCDV-Hop can improve the localization accuracy by about 10%.And this algorithm also has the characteristics of low complexity and high efficiency,which can meet the limitation of WSN energy consumption.In the future,we will further improve our algorithm for the better performance.And we will further study the localization effect of the algorithm in the real environment.