# A Connectivity Weighting DV_Hop Localization Algorithm Using Modified Artificial Bee Colony Optimization

Authors: Tianfei Chen; Lijun Sun
Journal: Journal of Sensors
 (2019)

---

## Abstract

Node localization is a fundamental issue in wireless sensor network (WSN), as many applications depend on the precise location of the sensor nodes (SNs). Among all localization algorithms, DV_Hop is a typical range-free localization algorithm characterized by such advantages as simple realization and low energy cost. From detailed analysis of localization error for the basic DV_Hop algorithm, we propose a connectivity weighting DV_Hop localization algorithm using modified artificial bee colony optimization. Firstly, the proposed algorithm calculates the average hop distance (AHD) of anchor nodes in terms of the minimum mean squared distance error between the estimated distances of anchor nodes and the corresponding actual distances from them. After that, a connectivity weighting method, considering the influence from both local network properties of anchor nodes and the distances from anchor nodes to unknown nodes, is designed to obtain the AHD of unknown nodes. In addition, we set up the weighting calculation proportion of anchor nodes at the same time. Finally, a modified artificial bee colony algorithm which enlarges searching space is used to optimize the execution of multilateral localization. The experimental results demonstrate that the connectivity weighting approach has better localization effect, and the AHD of unknown nodes close to true value can be obtained at a relatively large probability. Moreover, the modified artificial bee colony algorithm can reduce the probability of premature convergence, and thus the localization accuracy is further improved.


---

## Body

## 1. Introduction

WSN, bred by low-power embedded technology, wireless communication technology, microelectromechanical systems, and other related technologies, is a technological revolution on information sensing technology [1]. It consists of plenty of static and mobile SNs having the capability of sensing, computation, and wireless communication in the self-organizing manner to realize the functions of acquisition, monitoring in the coverage area of network, and owing to the characteristics of low cost, low power consumption, flexible organization, and rapid deployment, it provides great convenience for human production and life. Up to present, it has been widely used in environmental monitoring, national defense, target tracking, and other fields [2, 3].Generally, the position information of SNs is indispensable, and monitoring without position information may not be useful. Hence, node localization is one of the most critical issues for WSN [4]. One of the simplest solutions to localize SNs is using the GPS or BeiDou, but it is not possible to equip with them on all SNs especially for the large-scale WSN, because of some constraints like cost, energy, and volume. Therefore, one effective solution is to equip only a small number of SNs with location hardware known as anchor nodes (ANs), and the other SNs are called as unknown nodes (UNs). Accordingly, node localization refers to estimating the positions of UNs with the help of the distance and connectivity of SNs, when the positions of ANs are already given.Recently, many localization algorithms can be broadly categorized as range-based and range-free localization [5]. The range-based localization algorithms need additional hardware to measure the absolute distance or angle between adjacent SNs and use this information to determine the coordinates of UNs. Some of the common ranging approaches include time of arrival (TOA) [6], time difference of arrival (TDOA) [7], angle of arrival (AOA) [8], and received signal strength indicator (RSSI) [9]. In contrast, the range-free algorithms are just dependent on connectivity of SNs and network topology, and some typical range-free algorithms are APIT [10], Amorphous [11], Centroid [12], MDS-MAP [13], and DV_Hop [14]. Because of their simplicity in implementation and low power consumption, more attentions have been attracted. However, their results are less precise than range-based algorithms. Therefore, many researchers devoted their energies to improving the localization accuracy of range-free methods.DV_Hop, firstly proposed by Niculescu, is a distributed localization method using distance vector routing principle and is the most popular among range-free algorithm because of its facility and feasibility. Nevertheless, a major drawback of DV_Hop algorithm is that the estimated distances between ANs and UNs are to be erroneous, which is the main cause of poor localization accuracy, and thus some various improvements in DV_Hop algorithm have been put forward. Considering the close relationship between the localization accuracy and the deployment of ANs, Poggi [15] has deeply analyzed the influence from collinearity of ANs. Based on that, [16] adds the detection steps to select suitable ANs so that localization accuracy can be improved. Through global and local parts of hop distance, a new AHD suitable to network topology is acquired by Liu [17]. Meanwhile, Bing [18] introduced a correction parameter to compute the AHD of ANs according to the inconsistency of the estimated distance error, but the setting for the correction parameter has greatly depended on the network environment. From the inherent information of WSN, [19–21] propose a kind of weighted localization algorithms, in which part of ANs are utilized and different weights are given to the selected one. In order to further optimize the execution of multilateral localization at the final step, some scholars take advantage of evolutionary algorithms, such as genetic algorithm [22], particle swarm optimization [23], cuckoo search algorithm [24], and so forth.In this paper, a connectivity weighting DV_Hop localization algorithm using modified artificial bee colony optimization is proposed to improve localization accuracy. Our main contributions are delineated as follows:(i)
We comprehensively take into account the influence from several ANs near to the UN. Besides that, some experimental analysis and demonstrations for the different proportion of ANs participating in the calculation have been carried out so as to compute the AHD of UNs more accurately.(ii)
A method for calculating the weight of ANs based on connectivity is designed. In this method, not only the distances from UNs to ANs are useful, but also the connectivity of ANs is employed to measure their local network attributes, and the AHD of UNs can be finally obtained after weighting normalization.(iii)
A modified artificial bee colony algorithm is used to further improve the localization accuracy. The core evolution equation for the modified artificial bee colony algorithm takes a random individual as the search center, which can enlarge the searching space and reduce the probability of premature convergence at the same time.The remaining paper is structured as follows. The related works are introduced in Section2. Section 3 describes the basic DV_Hop algorithm, the analysis of localization error, and some typical improvement methods. Section 4 illustrates our proposed DV_Hop localization method in detail. In Section 5, simulation results are shown and localization performances are discussed. Finally, we conclude the paper in Section 6.


## 2. Related Works

On the premise of maintaining the original advantage of basic DV_Hop algorithm, various improvements are mainly involved in three aspects; they are, respectively, the calculation for the AHD of ANs, the weighting calculation for the AHD of UNs, and the optimization for multilateral localization.Because of the randomness deployment of SNs, the AHD of the whole network is proposed by Peng [19], in which information from all ANs are used. It firstly computes the AHD for each AN, and then all the ANs broadcast their AHD to the network; after that the AHD of the whole network can be obtained after averaging all the AHD of ANs; however, the AHD of the whole network cannot display the difference among all the ANs. Therefore, Bing [18] revised the AHD of the whole network using correction parameter, and the corresponding distance error for each AN should be computed and sent to every node in the network; then the correction parameter that highly depend on the network environment is used to balance the AHD of the whole network. According to the criterion of the minimum mean square error, a novel method for calculating the AHD of ANs was proposed by Ji [25] considering error is usually subject to Gaussian distribution, so it is more reasonable to use the mean square error. At the same time, [26] has further pointed out that the distance error based on the above criterion is the smallest. Because the AHD of the nearest AN cannot be accurately regarded as the actual AHD of UNs, more ANs have been employed by Liu [20] to assign different weight value according to the hop numbers. The weight value should increase with the corresponding hop number, and then the final AHDs of UNs are obtained after weighting normalization so as to further improve localization precision. In the same way, a weighting calculation method based on the different distance error of ANs is proposed by Zhao [21] after considering the situation that the localization error will be serious if some ANs having larger distance error are selected, so the weight value of the selected ANs should be large when their corresponding average distance error is small. For the optimization of multilateral localization, a weighted linear least square algorithm is used in [27], but the linear least square method has great dependency of the solution on the accuracy of any equation. Due to the accuracy loss caused by linearization with the method of the linear least square, Lin [28] proposed a nonlinear least square method based iterative calculation using Taylor’s expansion after directly calculating the sum of squared errors, and the threshold for iteration termination is set at the same time. Nowadays, the bioinspired mechanisms have been currently applied in many research areas especially in the field of WSN [29, 30]. A two-stage localization algorithm is presented by Kannan [31] using simulated annealing algorithm. In the first phase, simulated annealing is used to obtain an accurate estimate of location, and then a second phase of optimization is performed only on those nodes that are likely to have flip ambiguity problem. Besides that, Gopakumar [23] uses particle swarm optimization (PSO) to execute the multilateral localization, the PSO is a high-performance stochastic optimization tool, and the mean squared range error of all neighboring ANs is taken as the objective function for this nonlinear optimization problem. Moreover, differential evolution algorithm is also adopted in [32] to optimize the weighted square of distance error, and the value of hop number is ameliorated by the number of common one-hop nodes between adjacent SNs, which convert the discrete value of hop number to more accurate continuous values. As a new potential heuristic optimization algorithm, Cheng [24] has successfully applied the cuckoo search (CS) algorithm in the node localization, and this approach can enable the population to approach global optimal solution rapidly based on the modification of step size. Further, it restricts the population in the certain range so that it can prevent the energy consumption caused by insignificant search. In like manner, Mehrabi [33] combines genetic algorithm, leapfrog algorithm, and PSO algorithm and has successfully applied them into different stages of DV_Hop; the leapfrog algorithm is used to get more accurate AHD, and the hybrid genetic-PSO algorithm is employed to solve the problem of greater error of multilateral localization.From the above review, we can conclude that in DV_Hop algorithm the calculation for the AHD of UNs and the optimization for multilateral localization are two important factors to improve the performance of localization. Up to now, reported literature provides several weighting methods to compute the AHD of UNs; however, there is no analysis in experiments that how many ANs participated in the weighting calculation can get better localization accuracy. Furthermore, most weighting methods depend on the hop number and distance error of ANs; the connectivity of ANs reflecting the attributes of local network has not been regarded which can also cause more errors. In the literature, localization of UNs is formulated as optimization problem; although many optimization techniques have been applied to optimize the localization error, we are encouraged to propose a modified artificial bee colony optimization algorithm, which can enlarge the searching space and reduce the probability of premature convergence.


## 3. Theoretical Background

In this section, we first describe the localization principle of the basic DV_Hop algorithm. On its basis, the reasons causing localization error are analyzed and some corresponding typical improvement methods are briefly introduced.


### 3.1. Basic DV_Hop Algorithm

The core theoretical basis of DV_Hop is to estimate the distance from UNs to ANs by the product of the AHD and the corresponding hop number, rather than by using ranging methods, and the implementation of this algorithm consists of three steps as follows.First Step. ANs broadcast their message packets to obtain the minimum hop numbers from ANs to all the other SNs.During the first step, all the ANs broadcast their message packets to neighbor SNs by the method of flooding. Figure1 illustrates the structure of message packet; it contains the coordinates of the AN and the hop number that is initially set to 0; the hop number will be increased by 1 when the message packet is rebroadcasted by other SNs. If a SN receives another message from the same AN but with larger hop number compared to what have been saved, that message should be ignored. Therefore, all the SNs can get the position of each AN and the minimum hop numbers from themselves to every AN.Figure 1
Structure of message packet.Second Step. Calculating the AHD for all ANs and broadcasting them to the network.When the ANi gets the position of other ANs and the corresponding minimum hop numbers, the AHD of the ANi, denoted asAHDi, can be calculated using the following equation: (1)AHDi=∑j=1,j≠iNxi-xj2+yi-yj2∑j=1,j≠iNhijwhere N is the total number of ANs. (xi,yi) and (xj,yj), respectively, indicate the coordinates of the ANi and the ANj andhij represents the minimum hop number from the ANi to the ANj.The AHD of all ANs should also be broadcasted in the network by flooding, and then all the UNs only save the AHD firstly received; the remaining AHD subsequently received are chosen to be discarded. By using this method, the UNs can receive the AHD from their nearest AN.Third Step. Executing multilateral localization.The estimated distances from UNs to ANs are equivalent to the product of the minimum hop number and the AHD obtained in second step, and subsequently the multilateral localization can be carried out to get the coordinates of UNs.Let (xu,yu) represent the coordinate of the UNu, anddui shows the estimated distance from the UNu to the ANi by the following equation:(2)dui=AHDu×huiwherehui is the minimum hop number from the UNu to the ANi andAHDu indicates the saved AHD of the UN u.Up to now, the system of equations can be formed by considering the coordinates of all ANs and their estimated distances to the UNu as follows: (3)xu-x12+yu-y12=du1xu-x22+yu-y22=du2⋮xu-xN2+yu-yN2=duNThen, equation (3) can be transformed into the matrix form like AX=B, where A, B, and X are given as(4)X=xuyu;A=2x1-xN2y1-yN2x2-xN2y2-yN⋮⋮2xN-1-xN2yN-1-yN;B=x12-xN2+y12-yN2-du12+duN2x22-xN2+y22-yN2-du22+duN2⋮xN-12-xN2+yN-12-yN2-duN-12+duN2By calculating this matrix equation with the least square method (LS), the estimated location of the UNu can be determined: (5)X=ATA-1ATB


### 3.2. Analysis of Localization Error and Some Typical Improvement Methods

From the execution process of DV_Hop algorithm, it is known that the error mainly comes from the following three aspects.(  1) Accuracy of the AHD of ANs and the Value of the Minimum Hop Numbers. In basic DV_Hop, the estimated distance is the product of the AHD and the minimum hop number, so the accuracy of the AHD can directly affect the distance estimation. Besides that, due to the randomly distribution of SNs in WSN, it is difficult to guarantee that the minimum hop path between SNs is similar to a straight line. Therefore, the error between the estimated and true distance may be larger when the minimum hop number is higher.(  2) Calculation for the AHD of UNs. In basic DV_Hop, the AHD from the nearest AN is regarded as the AHD of UNs, but the network topology of WSN is complex and various; the single AHD from the nearest AN can hardly reflect the network properties around UNs, which may even lead to a large localization error. Accordingly, the calculation for the AHD of UNs is also an effective way to improve localization accuracy.To solve this problem, information from more ANs should be used, and the estimation for the AHD of UNs can be more accurate. Reference [19] proposed the average weighting (AW) method, and the AHD of UNs is the average of the AHD from several ANs:(6)AHDu=∑inAHDinwhere n is the number of ANs which a UN receives information from, n⩽N. It can be seen that each AN has the same weight value.Liu [20] designed the hop weighting (HW) method, which is based on the hypothesis that an AN closer to the UN may have the similar local network properties to that of the UN at a large probability:(7)AHDu=∑inωi·AHDi(8)ωi=1/hui∑jn1/hujwherehui is the minimum hop number from the UNu to the ANi.The distance error for ANs is inconsistent, and the distance error with a smaller value shows that the AHD of the AN may be more accurate. Therefore, an error weighting (EW) method is proposed by Zhao [21], and the weight values are calculated as follows: (9)ωi=1/εi∑jn1/εj(10)εi=∑i≠jN-1dij-Dij/hijN-1wheredij andDij are, respectively, the estimated distance and the actual distance from the ANi to the ANj.N is the total number of ANs in WSN, andn represents the number of ANs which a UN receives information from. Moreover, the equation for calculating the AHD of a UN is the same as equation (7).(  3) Optimization for Multilateral Localization. The estimated distances from UNs to ANs inevitably contain error, which will have direct impact on the calculation of coordinates X. On the other hand, it can be seen from the composition of matrix B that the solution of LS also depends on the estimation accuracy ofduN; if the deviation ofduN is large, the error for X will also increase.Lin [28] designed an iterative method using nonlinear least square (INLS).fi(x,y) is defined as (11)fix,y=xi-x2+yi-y2So the first-order Taylor series expansionfi(x,y) on initial position (x0,y0) is as follows:(12)fix,y=fix0+h,y0+k≈x0-xi2+y0-yi2+x0-xix0-xi2+y0-yi2h+y0-yix0-xi2+y0-yi2kwhere i=1,2,…,N;(h,k) indicates the step size. Let(13)Oi=x0-xi2+y0-yi2Mi=x0-xix0-xi2+y0-yi2Ni=y0-yix0-xi2+y0-yi2Therefore,(14)fix,y=Oi+Mix-x0+Niy-y0=Oi+Mih+NikWe can introduce equation (14) into equation (3) to solve the system of equations, and the step size (h,k) can be obtained. Then the iteration termination condition is defined as follows:(15)h2+k2<ηtwhereηt is the threshold of step size.If the above condition is satisfied, the iterative calculation stops; otherwise, the initial position should be updated as follows:(16)x0=x0+h2y0=y0+k2(x0,y0) should be replaced by the updated position until the termination condition is met. Finally, the position of the last iteration is regarded as the coordinate of the UN.


## 3.1. Basic DV_Hop Algorithm

The core theoretical basis of DV_Hop is to estimate the distance from UNs to ANs by the product of the AHD and the corresponding hop number, rather than by using ranging methods, and the implementation of this algorithm consists of three steps as follows.First Step. ANs broadcast their message packets to obtain the minimum hop numbers from ANs to all the other SNs.During the first step, all the ANs broadcast their message packets to neighbor SNs by the method of flooding. Figure1 illustrates the structure of message packet; it contains the coordinates of the AN and the hop number that is initially set to 0; the hop number will be increased by 1 when the message packet is rebroadcasted by other SNs. If a SN receives another message from the same AN but with larger hop number compared to what have been saved, that message should be ignored. Therefore, all the SNs can get the position of each AN and the minimum hop numbers from themselves to every AN.Figure 1
Structure of message packet.Second Step. Calculating the AHD for all ANs and broadcasting them to the network.When the ANi gets the position of other ANs and the corresponding minimum hop numbers, the AHD of the ANi, denoted asAHDi, can be calculated using the following equation: (1)AHDi=∑j=1,j≠iNxi-xj2+yi-yj2∑j=1,j≠iNhijwhere N is the total number of ANs. (xi,yi) and (xj,yj), respectively, indicate the coordinates of the ANi and the ANj andhij represents the minimum hop number from the ANi to the ANj.The AHD of all ANs should also be broadcasted in the network by flooding, and then all the UNs only save the AHD firstly received; the remaining AHD subsequently received are chosen to be discarded. By using this method, the UNs can receive the AHD from their nearest AN.Third Step. Executing multilateral localization.The estimated distances from UNs to ANs are equivalent to the product of the minimum hop number and the AHD obtained in second step, and subsequently the multilateral localization can be carried out to get the coordinates of UNs.Let (xu,yu) represent the coordinate of the UNu, anddui shows the estimated distance from the UNu to the ANi by the following equation:(2)dui=AHDu×huiwherehui is the minimum hop number from the UNu to the ANi andAHDu indicates the saved AHD of the UN u.Up to now, the system of equations can be formed by considering the coordinates of all ANs and their estimated distances to the UNu as follows: (3)xu-x12+yu-y12=du1xu-x22+yu-y22=du2⋮xu-xN2+yu-yN2=duNThen, equation (3) can be transformed into the matrix form like AX=B, where A, B, and X are given as(4)X=xuyu;A=2x1-xN2y1-yN2x2-xN2y2-yN⋮⋮2xN-1-xN2yN-1-yN;B=x12-xN2+y12-yN2-du12+duN2x22-xN2+y22-yN2-du22+duN2⋮xN-12-xN2+yN-12-yN2-duN-12+duN2By calculating this matrix equation with the least square method (LS), the estimated location of the UNu can be determined: (5)X=ATA-1ATB


## 3.2. Analysis of Localization Error and Some Typical Improvement Methods

From the execution process of DV_Hop algorithm, it is known that the error mainly comes from the following three aspects.(  1) Accuracy of the AHD of ANs and the Value of the Minimum Hop Numbers. In basic DV_Hop, the estimated distance is the product of the AHD and the minimum hop number, so the accuracy of the AHD can directly affect the distance estimation. Besides that, due to the randomly distribution of SNs in WSN, it is difficult to guarantee that the minimum hop path between SNs is similar to a straight line. Therefore, the error between the estimated and true distance may be larger when the minimum hop number is higher.(  2) Calculation for the AHD of UNs. In basic DV_Hop, the AHD from the nearest AN is regarded as the AHD of UNs, but the network topology of WSN is complex and various; the single AHD from the nearest AN can hardly reflect the network properties around UNs, which may even lead to a large localization error. Accordingly, the calculation for the AHD of UNs is also an effective way to improve localization accuracy.To solve this problem, information from more ANs should be used, and the estimation for the AHD of UNs can be more accurate. Reference [19] proposed the average weighting (AW) method, and the AHD of UNs is the average of the AHD from several ANs:(6)AHDu=∑inAHDinwhere n is the number of ANs which a UN receives information from, n⩽N. It can be seen that each AN has the same weight value.Liu [20] designed the hop weighting (HW) method, which is based on the hypothesis that an AN closer to the UN may have the similar local network properties to that of the UN at a large probability:(7)AHDu=∑inωi·AHDi(8)ωi=1/hui∑jn1/hujwherehui is the minimum hop number from the UNu to the ANi.The distance error for ANs is inconsistent, and the distance error with a smaller value shows that the AHD of the AN may be more accurate. Therefore, an error weighting (EW) method is proposed by Zhao [21], and the weight values are calculated as follows: (9)ωi=1/εi∑jn1/εj(10)εi=∑i≠jN-1dij-Dij/hijN-1wheredij andDij are, respectively, the estimated distance and the actual distance from the ANi to the ANj.N is the total number of ANs in WSN, andn represents the number of ANs which a UN receives information from. Moreover, the equation for calculating the AHD of a UN is the same as equation (7).(  3) Optimization for Multilateral Localization. The estimated distances from UNs to ANs inevitably contain error, which will have direct impact on the calculation of coordinates X. On the other hand, it can be seen from the composition of matrix B that the solution of LS also depends on the estimation accuracy ofduN; if the deviation ofduN is large, the error for X will also increase.Lin [28] designed an iterative method using nonlinear least square (INLS).fi(x,y) is defined as (11)fix,y=xi-x2+yi-y2So the first-order Taylor series expansionfi(x,y) on initial position (x0,y0) is as follows:(12)fix,y=fix0+h,y0+k≈x0-xi2+y0-yi2+x0-xix0-xi2+y0-yi2h+y0-yix0-xi2+y0-yi2kwhere i=1,2,…,N;(h,k) indicates the step size. Let(13)Oi=x0-xi2+y0-yi2Mi=x0-xix0-xi2+y0-yi2Ni=y0-yix0-xi2+y0-yi2Therefore,(14)fix,y=Oi+Mix-x0+Niy-y0=Oi+Mih+NikWe can introduce equation (14) into equation (3) to solve the system of equations, and the step size (h,k) can be obtained. Then the iteration termination condition is defined as follows:(15)h2+k2<ηtwhereηt is the threshold of step size.If the above condition is satisfied, the iterative calculation stops; otherwise, the initial position should be updated as follows:(16)x0=x0+h2y0=y0+k2(x0,y0) should be replaced by the updated position until the termination condition is met. Finally, the position of the last iteration is regarded as the coordinate of the UN.


## 4. Our Proposed DV_Hop Algorithm

After analyzing the reason of localization error for the basic DV_Hop algorithm, this paper improves the algorithm from various aspects to promote the localization accuracy. The main contents are as follows: the calculation for the AHD of ANs based on the minimum mean square distance error, calculation for the AHD of UNs using connectivity weighting, and optimization of multilateral localization using modified artificial bee colony algorithm.


### 4.1. Calculation for the AHD of ANs Based on the Minimum Mean Square Distance Error

The unbiased estimation criterion is employed in the basic DV_Hop algorithm; that is to say, the average distance error for the AHD of ANs, calculated using equation (1), is zero. But it is more reasonable to take the minimum mean square distance error as cost function compared with the unbiased criterion, because of that error is generally subject to Gaussian distribution.Assuming that∆ij indicates the distance error between the estimated distance from the ANi to the ANj and the corresponding actual distance, thus the total distance error is (17)∑i≠jΔij2=∑i≠jDij-AHDi·hij2=∑i≠jDij2-2·Dij·AHDi·hij+AHDi2·hij2Let(18)∂∑i≠jΔij2∂AHDi=0We can deduce the equation for calculating the AHD of ANs as follows:(19)AHDi=∑i≠jhij·Dij∑i≠jhij2


### 4.2. Calculation for the AHD of UNs Using Connectivity Weighting

In the basic DV_Hop, all the UNs take the AHD from the nearest AN as their AHD. However, owing to the random distribution of SNs in WSN, the distance error for each AN is inconsistent, and the AHD of a single AN cannot be sufficient to reflect the properties of the whole network, which will bring about the error of estimated distance. In order to obtain the AHD of UNs more accurately, we comprehensively take into account the influence from several ANs near to the UN. When a UN has gotten some AHDs, different weight value should be assigned, and normalization for the weight value will be carried out to compute the final AHD of UNs. In summary, the design of weight value is mainly based on the following two aspects:(1) For a UN, the influence from ANs having different distance to the UN is inconsistent, the AHD of the AN closer to the UN may be similar to the actual AHD of the UN at a larger probability.(2) The local network properties of each AN is inconsistent, and the number of UNs which actually participate in the calculation for the AHD of ANs is not the same; that is, the total number of UNs on the shortest path from one AN to the remaining ANs is different. If an AN has more number of UNs on the shortest path, it will have stronger connectivity, and thus its impact on the AHD of UNs should also be greater.We now introduce the connectivity weighting calculation method for the AHD of UNs in detail. Based on both the local network properties of ANs and the distance from ANs to UNs, the weight value is defined as follows:(20)ωi=∑j≠iNhij-1huiwhereN is the total number of ANs,hui indicates the minimum hop number from the UNu to the ANi, and its small value shows that the ANi is close to the UNu, and thus the weight value of the ANi should be large. On the other side,hij represents the minimum hop number from the ANi to the ANj, and ∑j≠iN(hij-1) is consequently the total number of UNs on the shortest path from the ANi to the remaining ANs. The connectivity of an AN will be greater when it has more number of UNs on the shortest path, and thus the corresponding weight value should be set up larger at the same time.Before calculating the AHD of UNs, a unified criterion should be employed, and the weight value for different ANs must be normalized to make sure that the sum of all weight value is 1. Therefore, the normalized weight value is as follows:(21)ωi¯=ωi∑j=1nωjwheren represent the number of ANs that a UN has get message from, and it also is the number of ANs participating in the calculation of the AHD of UNs. Then, the AHD of the UNu is defined as (22)AHDu=∑inωi¯·AHDiThe estimated distance in basic DV_Hop also depends on the minimum hop number between SNs, and the error of estimated distance may be greater when the minimum hop number is larger. Therefore, good solution cannot be obtained at the situation that ANs far from the UN participate in the above calculation for the AHD of UNs. In contrast, the small number of ANs participated in the calculation is not a good choice as well. Whenn = 1, it becomes the basic DV_Hop algorithm, the AHD of the UN is equal to the AHD of the nearest AN, and it is not enough to show the local network properties of the UN. Consequently, we set the weighting calculation proportion of ANspr as follows: (23)pr=nNAn appropriate proportion should be set so that the calculation for the AHD of UNs can take into account information from more ANs, and then the AHD of UNs may be closer to its true value.


### 4.3. Optimization of Multilateral Localization Using Modified Artificial Bee Colony Algorithm

In the step of multilateral localization, the performance of LS in the basic DV_Hop algorithm heavily relies on the accuracy of distance estimation [34], and the INLS algorithm needs to set the initial value of iteration at first; if the initial value is not appropriate, the final localization accuracy will be influenced. In this paper, a modified artificial bee colony algorithm is proposed to optimize the multilateral localization, and it can not only reduce the sensitivity to the error of the estimated distance, but also avoid the dependence on the initial value.The basic artificial bee colony algorithm (ABC) is developed to find the optimal solution through the cooperation of individuals in the population, and it is a global convergence algorithm demonstrated in [35]. In ABC, the artificial bee colony consists of three groups of bees: employed bees, onlooker bees, and scout bees. The employed bees are conducted to exploit food source, the onlooker bees randomly choose a food source depending on probability to continue to exploit, and the primary task of scout bees is to find a new food source after the search is trapped in a local optimum. A location of a random food source corresponds to a stochastic solution of the optimization problem, and the nectar quantity of the food source represents the fitness value. The employed bees correspond to food source one to one, and the number of employed bees is the same as that of onlooker bees; the number of the scout bees is only one. Suppose that in D-dimensional space,SN is the number of food sources, and the location of the ith food source is represented by Xi=(xi1,xi2,…,xiD),i⩽SN. The process of searching for the optimal food source by artificial bee colony includes the following steps.(1)Employed Bees Phase. Employed bees conduct neighborhood searching around the current food source to produce a new food source, and then the better one should be selected based on the greedy criterion.(2)Onlooker Bees Phase. According to the information shared by the employed bees, onlooker bees choose a food source depending on the probability proportional to the quality of that food source to carry on the neighborhood searching. Similarly, a new food source should be produced and greedily select a better one compared with the old food source.(3)Scout Bees Phase. If a food source cannot be improved further through a predetermined number of cycleslimit, it indicates that the food source has been exhausted, and then the current employed bee become scout bee and the scout bee will produce a new food source.In basic ABC algorithm, each employed bee and onlooker bee generates a new food source in the neighborhood of its present position by using the following search equation:(24)vij=xij+φijxij-xkjwhere j∈{1,2,…,D}; i,k∈{1,2,…,SN} and i≠k; φij is a random number in the range [-1,1].During the search process, an looker bee chooses a food source based on the scheme of roulette wheel selection, after employed bees share information about food sources. The probability value associated with food source is(25)Pi=Fiti∑j=1SNFitjwhereFiti is the fitness value of the food sourcei; the equation for calculating fitness is as follows:(26)Fiti=11+FiFi≥01+absFiFi<0whereFi is the value of the objective function corresponding to the food source i.If a food source is not updated afterlimit times, the scout bee will generate a new food source using the following equation:(27)xij=lj+rand⁡0,1uj-ljwherelj anduj are the upper and lower bounds for dimensionj, respectively.When ABC algorithm is employed to execute the node localization, the objective function can be defined using equation (3) and (11) as follows:(28)Fi=∑i=1Nfi-dui2ABC algorithm is an iterative algorithm to search for the optimal solution in the solution space, and it can get rid of the dependence on the initial value when optimizing the problem of node localization. However, similar to other evolutionary algorithms, ABC also faces up some challenging problems, like slow convergence and prematurity, and it is difficult to get the global optimal solution. We can see from (24) that local search is carried out taking the current location as the search center. In order to enhance the global search ability, we put forward the modified ABC algorithm with random location updating (RABC), and it takes the position of a random individual as the search center; the modified search equation is as follows: (29)vij=xrj+φijxij-xrjwhere i,r∈{1,2,…,SN} and r≠i.The difference of searching area between (24) and (29) can be intuitively shown in Figure 2. For example, in the plane coordinate systemO-XY, the coordinates of pointsA,B, andC are, respectively, (1,0), (3,1), and (0,2). We take the pointA as the current food source, and thus Figure 2(a) shows the searching area of (24); the searching area of (29) is shown in Figure 2(b). The comparison shows that (29) has a larger searching space, and it can be intuitively seen that RABC has better global searching ability.Figure 2
Searching space analysis.
(a) (b)The flow chart of optimization of multilateral localization using RABC is shown in Figure3, and the termination condition of the iteration is set as follows: the maximum iteration number is MaxIt, or the step size of the optimal value of the population is less than the threshold ηt.Figure 3
Flow chart of optimization of multilateral localization using RABC.


## 4.1. Calculation for the AHD of ANs Based on the Minimum Mean Square Distance Error

The unbiased estimation criterion is employed in the basic DV_Hop algorithm; that is to say, the average distance error for the AHD of ANs, calculated using equation (1), is zero. But it is more reasonable to take the minimum mean square distance error as cost function compared with the unbiased criterion, because of that error is generally subject to Gaussian distribution.Assuming that∆ij indicates the distance error between the estimated distance from the ANi to the ANj and the corresponding actual distance, thus the total distance error is (17)∑i≠jΔij2=∑i≠jDij-AHDi·hij2=∑i≠jDij2-2·Dij·AHDi·hij+AHDi2·hij2Let(18)∂∑i≠jΔij2∂AHDi=0We can deduce the equation for calculating the AHD of ANs as follows:(19)AHDi=∑i≠jhij·Dij∑i≠jhij2


## 4.2. Calculation for the AHD of UNs Using Connectivity Weighting

In the basic DV_Hop, all the UNs take the AHD from the nearest AN as their AHD. However, owing to the random distribution of SNs in WSN, the distance error for each AN is inconsistent, and the AHD of a single AN cannot be sufficient to reflect the properties of the whole network, which will bring about the error of estimated distance. In order to obtain the AHD of UNs more accurately, we comprehensively take into account the influence from several ANs near to the UN. When a UN has gotten some AHDs, different weight value should be assigned, and normalization for the weight value will be carried out to compute the final AHD of UNs. In summary, the design of weight value is mainly based on the following two aspects:(1) For a UN, the influence from ANs having different distance to the UN is inconsistent, the AHD of the AN closer to the UN may be similar to the actual AHD of the UN at a larger probability.(2) The local network properties of each AN is inconsistent, and the number of UNs which actually participate in the calculation for the AHD of ANs is not the same; that is, the total number of UNs on the shortest path from one AN to the remaining ANs is different. If an AN has more number of UNs on the shortest path, it will have stronger connectivity, and thus its impact on the AHD of UNs should also be greater.We now introduce the connectivity weighting calculation method for the AHD of UNs in detail. Based on both the local network properties of ANs and the distance from ANs to UNs, the weight value is defined as follows:(20)ωi=∑j≠iNhij-1huiwhereN is the total number of ANs,hui indicates the minimum hop number from the UNu to the ANi, and its small value shows that the ANi is close to the UNu, and thus the weight value of the ANi should be large. On the other side,hij represents the minimum hop number from the ANi to the ANj, and ∑j≠iN(hij-1) is consequently the total number of UNs on the shortest path from the ANi to the remaining ANs. The connectivity of an AN will be greater when it has more number of UNs on the shortest path, and thus the corresponding weight value should be set up larger at the same time.Before calculating the AHD of UNs, a unified criterion should be employed, and the weight value for different ANs must be normalized to make sure that the sum of all weight value is 1. Therefore, the normalized weight value is as follows:(21)ωi¯=ωi∑j=1nωjwheren represent the number of ANs that a UN has get message from, and it also is the number of ANs participating in the calculation of the AHD of UNs. Then, the AHD of the UNu is defined as (22)AHDu=∑inωi¯·AHDiThe estimated distance in basic DV_Hop also depends on the minimum hop number between SNs, and the error of estimated distance may be greater when the minimum hop number is larger. Therefore, good solution cannot be obtained at the situation that ANs far from the UN participate in the above calculation for the AHD of UNs. In contrast, the small number of ANs participated in the calculation is not a good choice as well. Whenn = 1, it becomes the basic DV_Hop algorithm, the AHD of the UN is equal to the AHD of the nearest AN, and it is not enough to show the local network properties of the UN. Consequently, we set the weighting calculation proportion of ANspr as follows: (23)pr=nNAn appropriate proportion should be set so that the calculation for the AHD of UNs can take into account information from more ANs, and then the AHD of UNs may be closer to its true value.


## 4.3. Optimization of Multilateral Localization Using Modified Artificial Bee Colony Algorithm

In the step of multilateral localization, the performance of LS in the basic DV_Hop algorithm heavily relies on the accuracy of distance estimation [34], and the INLS algorithm needs to set the initial value of iteration at first; if the initial value is not appropriate, the final localization accuracy will be influenced. In this paper, a modified artificial bee colony algorithm is proposed to optimize the multilateral localization, and it can not only reduce the sensitivity to the error of the estimated distance, but also avoid the dependence on the initial value.The basic artificial bee colony algorithm (ABC) is developed to find the optimal solution through the cooperation of individuals in the population, and it is a global convergence algorithm demonstrated in [35]. In ABC, the artificial bee colony consists of three groups of bees: employed bees, onlooker bees, and scout bees. The employed bees are conducted to exploit food source, the onlooker bees randomly choose a food source depending on probability to continue to exploit, and the primary task of scout bees is to find a new food source after the search is trapped in a local optimum. A location of a random food source corresponds to a stochastic solution of the optimization problem, and the nectar quantity of the food source represents the fitness value. The employed bees correspond to food source one to one, and the number of employed bees is the same as that of onlooker bees; the number of the scout bees is only one. Suppose that in D-dimensional space,SN is the number of food sources, and the location of the ith food source is represented by Xi=(xi1,xi2,…,xiD),i⩽SN. The process of searching for the optimal food source by artificial bee colony includes the following steps.(1)Employed Bees Phase. Employed bees conduct neighborhood searching around the current food source to produce a new food source, and then the better one should be selected based on the greedy criterion.(2)Onlooker Bees Phase. According to the information shared by the employed bees, onlooker bees choose a food source depending on the probability proportional to the quality of that food source to carry on the neighborhood searching. Similarly, a new food source should be produced and greedily select a better one compared with the old food source.(3)Scout Bees Phase. If a food source cannot be improved further through a predetermined number of cycleslimit, it indicates that the food source has been exhausted, and then the current employed bee become scout bee and the scout bee will produce a new food source.In basic ABC algorithm, each employed bee and onlooker bee generates a new food source in the neighborhood of its present position by using the following search equation:(24)vij=xij+φijxij-xkjwhere j∈{1,2,…,D}; i,k∈{1,2,…,SN} and i≠k; φij is a random number in the range [-1,1].During the search process, an looker bee chooses a food source based on the scheme of roulette wheel selection, after employed bees share information about food sources. The probability value associated with food source is(25)Pi=Fiti∑j=1SNFitjwhereFiti is the fitness value of the food sourcei; the equation for calculating fitness is as follows:(26)Fiti=11+FiFi≥01+absFiFi<0whereFi is the value of the objective function corresponding to the food source i.If a food source is not updated afterlimit times, the scout bee will generate a new food source using the following equation:(27)xij=lj+rand⁡0,1uj-ljwherelj anduj are the upper and lower bounds for dimensionj, respectively.When ABC algorithm is employed to execute the node localization, the objective function can be defined using equation (3) and (11) as follows:(28)Fi=∑i=1Nfi-dui2ABC algorithm is an iterative algorithm to search for the optimal solution in the solution space, and it can get rid of the dependence on the initial value when optimizing the problem of node localization. However, similar to other evolutionary algorithms, ABC also faces up some challenging problems, like slow convergence and prematurity, and it is difficult to get the global optimal solution. We can see from (24) that local search is carried out taking the current location as the search center. In order to enhance the global search ability, we put forward the modified ABC algorithm with random location updating (RABC), and it takes the position of a random individual as the search center; the modified search equation is as follows: (29)vij=xrj+φijxij-xrjwhere i,r∈{1,2,…,SN} and r≠i.The difference of searching area between (24) and (29) can be intuitively shown in Figure 2. For example, in the plane coordinate systemO-XY, the coordinates of pointsA,B, andC are, respectively, (1,0), (3,1), and (0,2). We take the pointA as the current food source, and thus Figure 2(a) shows the searching area of (24); the searching area of (29) is shown in Figure 2(b). The comparison shows that (29) has a larger searching space, and it can be intuitively seen that RABC has better global searching ability.Figure 2
Searching space analysis.
(a) (b)The flow chart of optimization of multilateral localization using RABC is shown in Figure3, and the termination condition of the iteration is set as follows: the maximum iteration number is MaxIt, or the step size of the optimal value of the population is less than the threshold ηt.Figure 3
Flow chart of optimization of multilateral localization using RABC.


## 5. Experimental Results and Discussion

In this section, we describe the results of some experimental test to evaluate the performance of our proposed algorithm compared with some variants discussed in Section3. The influence of connectivity weighting method is firstly analyzed, and then we demonstrate the performance of RABC algorithm in terms of accuracy (normalized average localization error of the network) and precision (cumulative distribution function).


### 5.1. Simulation Environment

The simulation experiments are carried out using the software Matlab R2013 on the computer platform in which the memory is 8G, CPU is the Inter Core i7 processor, and the operating system is Windows 7. The simulation area is set as[0,100m] × [0,100m], and we randomly generate and deploy all the SNs, and part of SNs are randomly selected to be regarded as ANs at the same time. In order to evaluate the performance of our proposed algorithm objectively, 200 independent simulations at the same experimental environment are conducted.Letxutrue,yutrue be the actual coordinate of an UN, and xuest,yuest is the corresponding estimated position, R is the maximum communication radius of sensor nodes,num is the total number of UNs, and then the normalized average localization error of the network for one simulation is expressed as follows:(30)εnetwork=∑u=1numxutrue-xuest2+yutrue-yuest2/RnumSimilarly,AHDutrue indicates the actual AHD of the UN u, and AHDuest is the corresponding estimated AHD, and then the average error of the estimated AHD of UNs for one simulation is defined as(31)δnetwork=∑u=1numAHDutrue-AHDuestnumTable1 shows the detailed parameter settings of the RABC algorithm. In addition, we set the threshold of step size for INLS to be consistent with that of RABC; that is to say, ηt in (15) also is 0.5m.Table 1
Parameter settings of RABC.
Parameters Value The maximum number of iterationsMaxIt 100 The total number of individuals in the populationPop 50 The dimension of node localizationNdim 2 The predetermined number of cycles for RABClimit 0.1 ×Ndim × Pop The threshold for the step size of the optimal solutionηt 0.5 m


### 5.2. Results and Analysis

#### 5.2.1. The Influence Analysis of Connectivity Weighting

The calculation for the AHD of UNs is one of the important factors that affect the localization accuracy. When the number of ANs involved in the calculation is only one, the algorithm is the same as the basic DV_Hop algorithm, and a single AN is not sufficient to reflect the local network properties of UNs. On the contrary, if all ANs take part in the calculation, an AN far from the UN will make the estimated distance error greater. Therefore, when the weighting calculation proportion of ANspr is fixed, we will compare the influence of AW, HW, EW, and our proposed connectivity weighting (CW) method on the localization accuracy.In the simulation area, the total number of SNs is 150, the maximum communication radius is 30m; besides that, the AHD of ANs is computed using (19), and LS is used to execute multilateral localization. Figure 4 shows the curve of localization error, the abscissa shows the different value ofpr, and the ordinate is the mean value of εnetwork for 200 independent simulations. Figure 4(a) shows the result of the situation that the total number of ANs is 30, and in Figure 4(b), the total number of ANs is 50. We can see that the localization accuracy of CW is the best, which is significantly better than that of other weighting methods. In addition, no matter which weighting method is used, the variation law of the localization error curve is almost the same. The localization error is relatively small whenpr is 0.05 or 0.1, and the localization error will increase whenpr gradually increases. This part of experimental results can provide guidance for the setting ofpr.Figure 4
The curve of localization error with differentpr.
(a) (b)Based on the above experimental results in Figure4, we set the parameterpr as 0.1, the total number of SNs is still 150, and the maximum communication radius is set as 30m. In the simulation experiment, we also calculate the actual AHD of UNs using (19). Figure 5 shows the accuracy analysis for the estimated AHD of UNs, and it gives the results of various weighting methods compared with the basic DV_Hop algorithm. Figure 5(a) is the distribution of δnetwork under 200 simulations when the total number of ANs is 30, and accordingly Figure 5(b) is the proportion graph of various weighting methods having the minimum δnetwork. Similarly, Figures 5(c) and 5(d) correspond to the results when the total number of ANs is 50. From Figures 5(a) and 5(c), we can see that the average error for the estimated AHD of UNs in basic DV_Hop algorithm is obviously the largest, and thus the weighting methods can improve the estimation accuracy of the AHD of UNs. Besides that, both Figures 5(b) and 5(d) demonstrate that the proportion for CW is higher than that of other weighting methods, which indicates that the estimated AHD of UNs calculated using CW could be close to the real value at a large probability.Figure 5
Accuracy analysis diagram of the estimated AHD of UNs.
(a) (b) (c) (d)


#### 5.2.2. The Influence Analysis of RABC

Compared with LS, INLS, and ABC algorithm, this part of experiments is used to test the performance of RABC algorithm for multilateral localization. For INLS algorithm, initial value of iteration must be given at first, so we can take the solution of LS as its initial value, which is denoted as “INLS1.” Similarly, the centroids of polygons composed by several ANs around the UN can also be treated as initial value, and we define this situation as “INLS2.” At last, “INLS3” indicates the case that a random position in the monitoring area is regarded as the initial value. Besides that, the AHD of UNs should be calculated using the method of CW according to the experiment conclusion in above subsection; furthermore, the weighting calculation proportionpr is still set as 0.1. After that, we compare and analyze the performance from the three aspects including the total number of SNs, the total number of ANs, and the maximum communication radius. The values for variation parameters are shown in Table 2. When the total number of SNs changes, the total number of ANs is set to 30 and the maximum communication radius is fixed at 30m. If the total number of ANs changes, the total number of sensor nodes and the maximum communication radius are, respectively, set to 150 and 30m. At the situation that the maximum communication radius changes, the total number of SNs is 150 and the total number of ANs is 30. In addition, the parameter setting of ABC algorithm is the same as that of RABC, and the threshold of step size ηt for INLS algorithms is the same as that of ABC and RABC.Table 2
The value of variation parameters.
Variable Value The total number of SNs 100, 120, 140, 160, 180, 200 The total number of ANs 20, 25, 30, 35, 40, 45, 50 The maximum communication radius/m 20, 25, 30, 35, 40, 45, 50Figures6–8, respectively, show the curve of the mean value of εnetwork under 200 simulations relative to the total number of SNs, the total number of ANs, and the maximum communication radius. Among which, Figures 6(a), 7(a), and 8(a) show the results of all the compared algorithms. From them, we can see that the performances of INLS, ABC, and RABC algorithms are obviously better than that of LS. In order to see the performance of INLS, ABC, and RABC algorithms more clearly, Figures 6(b), 7(b), and 8(b) display the results only from them except LS. In Figure 6(a), when the total number of SNs increases, the mean value of εnetwork for LS increases overall, but that of INLS, ABC, and RABC algorithm shows a slight downward trend, which indicates that the increase of the total number of sensor nodes has a great influence on LS algorithm. In Figure 7(a), the mean value of εnetwork of all compared algorithms decreases as the total number of ANs increases, which demonstrates that increasing the total number of ANs is conducive to improving the location accuracy of UNs. Figure 8 shows the curve of the mean value of εnetwork with the maximum communication radius. It can be seen that the curves of INLS, ABC, and RABC show the same variation law; the location error will increase when the maximum communication radius is too small or too large. When the maximum communication radius is too small, the minimum hop number between SNs will increase, which may indirectly lead to a large estimation error for the AHD of ANs. On the other hand, when the maximum communication radius is too large, all ANs perhaps can communicate with each other directly; the computed AHD of ANs is not suitable for the cases where the SNs cannot communicate with each other, and thus a larger localization error comes out.Figure 6
The curve of the mean value ofεnetwork with the total number of sensor nodes.
(a) (b)Figure 7
The curve of the mean value ofεnetwork with the total number of ANs.
(a) (b)Figure 8
The curve of the mean value ofεnetwork with the maximum communication radius.
(a) (b)From the results of Figures6(b), 7(b), and 8(b), it can be seen that the localization performance of RABC algorithm is the best, which is also better than that of INLS and ABC. Besides that, we can also see that the performance of INLS is greatly influenced by the initial value of iteration, if the initial value for INLS is not reasonable, its localization error will also increase. Because the result of INLS1 is better than that of INLS2 and INLS3, the solution of LS algorithm may be a good choice, and its localization effect is the further optimization of LS algorithm. In addition, the localization performance of INLS1 is still better than that of ABC algorithms; the reason is that ABC is easier to be trapped in premature convergence which results in the best result cannot be obtained. The localization performance of RABC proposed in this paper is the best; this algorithm searches the optimal solution through the cooperation of individuals, and its core searching equation takes a random individual in the population as the center, which expands the searching space and the probability of premature convergence can also be reduced.The results in Figures6–8 only show the accuracy behavior of the analyzed algorithms. In order to evaluate the precision performance of the compared algorithms further, the cumulative probability is calculated under the situation that the total numbers of SNs and ANs are, respectively, 150 and 30, and the maximum communicate radius is 30m. Besides that, 200 independent simulations at the same experimental condition are carried out as well. Figure 9 shows the cumulative distribution function (CDF) of the normalized localization error. Similarly, Figure 9(a) is the result of all analyzed results, and Figure 9(b) is the local enlarged drawing of Figure 9(a) among the analyzed algorithms except LS. As it can be noticed in Figure 9(a), the precision of the localization for INLS, ABC, and RABC is obviously better than that of LS. Again, we can also observe from Figure 9(b) that the RABC algorithm has the best localization precision. In summary, the RABC algorithm proposed in this paper shows a good performance on both localization accuracy and localization precision.Figure 9
Cumulative distribution function of the normalized localization error.
(a) (b)


## 5.1. Simulation Environment

The simulation experiments are carried out using the software Matlab R2013 on the computer platform in which the memory is 8G, CPU is the Inter Core i7 processor, and the operating system is Windows 7. The simulation area is set as[0,100m] × [0,100m], and we randomly generate and deploy all the SNs, and part of SNs are randomly selected to be regarded as ANs at the same time. In order to evaluate the performance of our proposed algorithm objectively, 200 independent simulations at the same experimental environment are conducted.Letxutrue,yutrue be the actual coordinate of an UN, and xuest,yuest is the corresponding estimated position, R is the maximum communication radius of sensor nodes,num is the total number of UNs, and then the normalized average localization error of the network for one simulation is expressed as follows:(30)εnetwork=∑u=1numxutrue-xuest2+yutrue-yuest2/RnumSimilarly,AHDutrue indicates the actual AHD of the UN u, and AHDuest is the corresponding estimated AHD, and then the average error of the estimated AHD of UNs for one simulation is defined as(31)δnetwork=∑u=1numAHDutrue-AHDuestnumTable1 shows the detailed parameter settings of the RABC algorithm. In addition, we set the threshold of step size for INLS to be consistent with that of RABC; that is to say, ηt in (15) also is 0.5m.Table 1
Parameter settings of RABC.
Parameters Value The maximum number of iterationsMaxIt 100 The total number of individuals in the populationPop 50 The dimension of node localizationNdim 2 The predetermined number of cycles for RABClimit 0.1 ×Ndim × Pop The threshold for the step size of the optimal solutionηt 0.5 m


## 5.2. Results and Analysis

### 5.2.1. The Influence Analysis of Connectivity Weighting

The calculation for the AHD of UNs is one of the important factors that affect the localization accuracy. When the number of ANs involved in the calculation is only one, the algorithm is the same as the basic DV_Hop algorithm, and a single AN is not sufficient to reflect the local network properties of UNs. On the contrary, if all ANs take part in the calculation, an AN far from the UN will make the estimated distance error greater. Therefore, when the weighting calculation proportion of ANspr is fixed, we will compare the influence of AW, HW, EW, and our proposed connectivity weighting (CW) method on the localization accuracy.In the simulation area, the total number of SNs is 150, the maximum communication radius is 30m; besides that, the AHD of ANs is computed using (19), and LS is used to execute multilateral localization. Figure 4 shows the curve of localization error, the abscissa shows the different value ofpr, and the ordinate is the mean value of εnetwork for 200 independent simulations. Figure 4(a) shows the result of the situation that the total number of ANs is 30, and in Figure 4(b), the total number of ANs is 50. We can see that the localization accuracy of CW is the best, which is significantly better than that of other weighting methods. In addition, no matter which weighting method is used, the variation law of the localization error curve is almost the same. The localization error is relatively small whenpr is 0.05 or 0.1, and the localization error will increase whenpr gradually increases. This part of experimental results can provide guidance for the setting ofpr.Figure 4
The curve of localization error with differentpr.
(a) (b)Based on the above experimental results in Figure4, we set the parameterpr as 0.1, the total number of SNs is still 150, and the maximum communication radius is set as 30m. In the simulation experiment, we also calculate the actual AHD of UNs using (19). Figure 5 shows the accuracy analysis for the estimated AHD of UNs, and it gives the results of various weighting methods compared with the basic DV_Hop algorithm. Figure 5(a) is the distribution of δnetwork under 200 simulations when the total number of ANs is 30, and accordingly Figure 5(b) is the proportion graph of various weighting methods having the minimum δnetwork. Similarly, Figures 5(c) and 5(d) correspond to the results when the total number of ANs is 50. From Figures 5(a) and 5(c), we can see that the average error for the estimated AHD of UNs in basic DV_Hop algorithm is obviously the largest, and thus the weighting methods can improve the estimation accuracy of the AHD of UNs. Besides that, both Figures 5(b) and 5(d) demonstrate that the proportion for CW is higher than that of other weighting methods, which indicates that the estimated AHD of UNs calculated using CW could be close to the real value at a large probability.Figure 5
Accuracy analysis diagram of the estimated AHD of UNs.
(a) (b) (c) (d)


### 5.2.2. The Influence Analysis of RABC

Compared with LS, INLS, and ABC algorithm, this part of experiments is used to test the performance of RABC algorithm for multilateral localization. For INLS algorithm, initial value of iteration must be given at first, so we can take the solution of LS as its initial value, which is denoted as “INLS1.” Similarly, the centroids of polygons composed by several ANs around the UN can also be treated as initial value, and we define this situation as “INLS2.” At last, “INLS3” indicates the case that a random position in the monitoring area is regarded as the initial value. Besides that, the AHD of UNs should be calculated using the method of CW according to the experiment conclusion in above subsection; furthermore, the weighting calculation proportionpr is still set as 0.1. After that, we compare and analyze the performance from the three aspects including the total number of SNs, the total number of ANs, and the maximum communication radius. The values for variation parameters are shown in Table 2. When the total number of SNs changes, the total number of ANs is set to 30 and the maximum communication radius is fixed at 30m. If the total number of ANs changes, the total number of sensor nodes and the maximum communication radius are, respectively, set to 150 and 30m. At the situation that the maximum communication radius changes, the total number of SNs is 150 and the total number of ANs is 30. In addition, the parameter setting of ABC algorithm is the same as that of RABC, and the threshold of step size ηt for INLS algorithms is the same as that of ABC and RABC.Table 2
The value of variation parameters.
Variable Value The total number of SNs 100, 120, 140, 160, 180, 200 The total number of ANs 20, 25, 30, 35, 40, 45, 50 The maximum communication radius/m 20, 25, 30, 35, 40, 45, 50Figures6–8, respectively, show the curve of the mean value of εnetwork under 200 simulations relative to the total number of SNs, the total number of ANs, and the maximum communication radius. Among which, Figures 6(a), 7(a), and 8(a) show the results of all the compared algorithms. From them, we can see that the performances of INLS, ABC, and RABC algorithms are obviously better than that of LS. In order to see the performance of INLS, ABC, and RABC algorithms more clearly, Figures 6(b), 7(b), and 8(b) display the results only from them except LS. In Figure 6(a), when the total number of SNs increases, the mean value of εnetwork for LS increases overall, but that of INLS, ABC, and RABC algorithm shows a slight downward trend, which indicates that the increase of the total number of sensor nodes has a great influence on LS algorithm. In Figure 7(a), the mean value of εnetwork of all compared algorithms decreases as the total number of ANs increases, which demonstrates that increasing the total number of ANs is conducive to improving the location accuracy of UNs. Figure 8 shows the curve of the mean value of εnetwork with the maximum communication radius. It can be seen that the curves of INLS, ABC, and RABC show the same variation law; the location error will increase when the maximum communication radius is too small or too large. When the maximum communication radius is too small, the minimum hop number between SNs will increase, which may indirectly lead to a large estimation error for the AHD of ANs. On the other hand, when the maximum communication radius is too large, all ANs perhaps can communicate with each other directly; the computed AHD of ANs is not suitable for the cases where the SNs cannot communicate with each other, and thus a larger localization error comes out.Figure 6
The curve of the mean value ofεnetwork with the total number of sensor nodes.
(a) (b)Figure 7
The curve of the mean value ofεnetwork with the total number of ANs.
(a) (b)Figure 8
The curve of the mean value ofεnetwork with the maximum communication radius.
(a) (b)From the results of Figures6(b), 7(b), and 8(b), it can be seen that the localization performance of RABC algorithm is the best, which is also better than that of INLS and ABC. Besides that, we can also see that the performance of INLS is greatly influenced by the initial value of iteration, if the initial value for INLS is not reasonable, its localization error will also increase. Because the result of INLS1 is better than that of INLS2 and INLS3, the solution of LS algorithm may be a good choice, and its localization effect is the further optimization of LS algorithm. In addition, the localization performance of INLS1 is still better than that of ABC algorithms; the reason is that ABC is easier to be trapped in premature convergence which results in the best result cannot be obtained. The localization performance of RABC proposed in this paper is the best; this algorithm searches the optimal solution through the cooperation of individuals, and its core searching equation takes a random individual in the population as the center, which expands the searching space and the probability of premature convergence can also be reduced.The results in Figures6–8 only show the accuracy behavior of the analyzed algorithms. In order to evaluate the precision performance of the compared algorithms further, the cumulative probability is calculated under the situation that the total numbers of SNs and ANs are, respectively, 150 and 30, and the maximum communicate radius is 30m. Besides that, 200 independent simulations at the same experimental condition are carried out as well. Figure 9 shows the cumulative distribution function (CDF) of the normalized localization error. Similarly, Figure 9(a) is the result of all analyzed results, and Figure 9(b) is the local enlarged drawing of Figure 9(a) among the analyzed algorithms except LS. As it can be noticed in Figure 9(a), the precision of the localization for INLS, ABC, and RABC is obviously better than that of LS. Again, we can also observe from Figure 9(b) that the RABC algorithm has the best localization precision. In summary, the RABC algorithm proposed in this paper shows a good performance on both localization accuracy and localization precision.Figure 9
Cumulative distribution function of the normalized localization error.
(a) (b)


## 5.2.1. The Influence Analysis of Connectivity Weighting

The calculation for the AHD of UNs is one of the important factors that affect the localization accuracy. When the number of ANs involved in the calculation is only one, the algorithm is the same as the basic DV_Hop algorithm, and a single AN is not sufficient to reflect the local network properties of UNs. On the contrary, if all ANs take part in the calculation, an AN far from the UN will make the estimated distance error greater. Therefore, when the weighting calculation proportion of ANspr is fixed, we will compare the influence of AW, HW, EW, and our proposed connectivity weighting (CW) method on the localization accuracy.In the simulation area, the total number of SNs is 150, the maximum communication radius is 30m; besides that, the AHD of ANs is computed using (19), and LS is used to execute multilateral localization. Figure 4 shows the curve of localization error, the abscissa shows the different value ofpr, and the ordinate is the mean value of εnetwork for 200 independent simulations. Figure 4(a) shows the result of the situation that the total number of ANs is 30, and in Figure 4(b), the total number of ANs is 50. We can see that the localization accuracy of CW is the best, which is significantly better than that of other weighting methods. In addition, no matter which weighting method is used, the variation law of the localization error curve is almost the same. The localization error is relatively small whenpr is 0.05 or 0.1, and the localization error will increase whenpr gradually increases. This part of experimental results can provide guidance for the setting ofpr.Figure 4
The curve of localization error with differentpr.
(a) (b)Based on the above experimental results in Figure4, we set the parameterpr as 0.1, the total number of SNs is still 150, and the maximum communication radius is set as 30m. In the simulation experiment, we also calculate the actual AHD of UNs using (19). Figure 5 shows the accuracy analysis for the estimated AHD of UNs, and it gives the results of various weighting methods compared with the basic DV_Hop algorithm. Figure 5(a) is the distribution of δnetwork under 200 simulations when the total number of ANs is 30, and accordingly Figure 5(b) is the proportion graph of various weighting methods having the minimum δnetwork. Similarly, Figures 5(c) and 5(d) correspond to the results when the total number of ANs is 50. From Figures 5(a) and 5(c), we can see that the average error for the estimated AHD of UNs in basic DV_Hop algorithm is obviously the largest, and thus the weighting methods can improve the estimation accuracy of the AHD of UNs. Besides that, both Figures 5(b) and 5(d) demonstrate that the proportion for CW is higher than that of other weighting methods, which indicates that the estimated AHD of UNs calculated using CW could be close to the real value at a large probability.Figure 5
Accuracy analysis diagram of the estimated AHD of UNs.
(a) (b) (c) (d)


## 5.2.2. The Influence Analysis of RABC

Compared with LS, INLS, and ABC algorithm, this part of experiments is used to test the performance of RABC algorithm for multilateral localization. For INLS algorithm, initial value of iteration must be given at first, so we can take the solution of LS as its initial value, which is denoted as “INLS1.” Similarly, the centroids of polygons composed by several ANs around the UN can also be treated as initial value, and we define this situation as “INLS2.” At last, “INLS3” indicates the case that a random position in the monitoring area is regarded as the initial value. Besides that, the AHD of UNs should be calculated using the method of CW according to the experiment conclusion in above subsection; furthermore, the weighting calculation proportionpr is still set as 0.1. After that, we compare and analyze the performance from the three aspects including the total number of SNs, the total number of ANs, and the maximum communication radius. The values for variation parameters are shown in Table 2. When the total number of SNs changes, the total number of ANs is set to 30 and the maximum communication radius is fixed at 30m. If the total number of ANs changes, the total number of sensor nodes and the maximum communication radius are, respectively, set to 150 and 30m. At the situation that the maximum communication radius changes, the total number of SNs is 150 and the total number of ANs is 30. In addition, the parameter setting of ABC algorithm is the same as that of RABC, and the threshold of step size ηt for INLS algorithms is the same as that of ABC and RABC.Table 2
The value of variation parameters.
Variable Value The total number of SNs 100, 120, 140, 160, 180, 200 The total number of ANs 20, 25, 30, 35, 40, 45, 50 The maximum communication radius/m 20, 25, 30, 35, 40, 45, 50Figures6–8, respectively, show the curve of the mean value of εnetwork under 200 simulations relative to the total number of SNs, the total number of ANs, and the maximum communication radius. Among which, Figures 6(a), 7(a), and 8(a) show the results of all the compared algorithms. From them, we can see that the performances of INLS, ABC, and RABC algorithms are obviously better than that of LS. In order to see the performance of INLS, ABC, and RABC algorithms more clearly, Figures 6(b), 7(b), and 8(b) display the results only from them except LS. In Figure 6(a), when the total number of SNs increases, the mean value of εnetwork for LS increases overall, but that of INLS, ABC, and RABC algorithm shows a slight downward trend, which indicates that the increase of the total number of sensor nodes has a great influence on LS algorithm. In Figure 7(a), the mean value of εnetwork of all compared algorithms decreases as the total number of ANs increases, which demonstrates that increasing the total number of ANs is conducive to improving the location accuracy of UNs. Figure 8 shows the curve of the mean value of εnetwork with the maximum communication radius. It can be seen that the curves of INLS, ABC, and RABC show the same variation law; the location error will increase when the maximum communication radius is too small or too large. When the maximum communication radius is too small, the minimum hop number between SNs will increase, which may indirectly lead to a large estimation error for the AHD of ANs. On the other hand, when the maximum communication radius is too large, all ANs perhaps can communicate with each other directly; the computed AHD of ANs is not suitable for the cases where the SNs cannot communicate with each other, and thus a larger localization error comes out.Figure 6
The curve of the mean value ofεnetwork with the total number of sensor nodes.
(a) (b)Figure 7
The curve of the mean value ofεnetwork with the total number of ANs.
(a) (b)Figure 8
The curve of the mean value ofεnetwork with the maximum communication radius.
(a) (b)From the results of Figures6(b), 7(b), and 8(b), it can be seen that the localization performance of RABC algorithm is the best, which is also better than that of INLS and ABC. Besides that, we can also see that the performance of INLS is greatly influenced by the initial value of iteration, if the initial value for INLS is not reasonable, its localization error will also increase. Because the result of INLS1 is better than that of INLS2 and INLS3, the solution of LS algorithm may be a good choice, and its localization effect is the further optimization of LS algorithm. In addition, the localization performance of INLS1 is still better than that of ABC algorithms; the reason is that ABC is easier to be trapped in premature convergence which results in the best result cannot be obtained. The localization performance of RABC proposed in this paper is the best; this algorithm searches the optimal solution through the cooperation of individuals, and its core searching equation takes a random individual in the population as the center, which expands the searching space and the probability of premature convergence can also be reduced.The results in Figures6–8 only show the accuracy behavior of the analyzed algorithms. In order to evaluate the precision performance of the compared algorithms further, the cumulative probability is calculated under the situation that the total numbers of SNs and ANs are, respectively, 150 and 30, and the maximum communicate radius is 30m. Besides that, 200 independent simulations at the same experimental condition are carried out as well. Figure 9 shows the cumulative distribution function (CDF) of the normalized localization error. Similarly, Figure 9(a) is the result of all analyzed results, and Figure 9(b) is the local enlarged drawing of Figure 9(a) among the analyzed algorithms except LS. As it can be noticed in Figure 9(a), the precision of the localization for INLS, ABC, and RABC is obviously better than that of LS. Again, we can also observe from Figure 9(b) that the RABC algorithm has the best localization precision. In summary, the RABC algorithm proposed in this paper shows a good performance on both localization accuracy and localization precision.Figure 9
Cumulative distribution function of the normalized localization error.
(a) (b)


## 6. Conclusions

A connectivity weighting DV_Hop localization algorithm using modified artificial bee colony optimization is proposed in this paper. In this algorithm, the AHD of ANs is calculated based on the minimum mean square distance error. On this basis, the AHD of UNS is computed using connectivity weighting method considering not only the distance from ANs to UNs but also the local network properties of each AN. In addition, a weighting calculation proportion is defined, and the appropriate value is obtained according to the experimental method. In the final step, a modified artificial bee colony algorithm with random location updating is used to optimize the multilateral localization, and searching space is expanded to reduce the probability of premature convergence. The experimental results demonstrate that the performance of connectivity weighting approach is better than that of the other weighting methods, and it can get the real average hop distance of unknown nodes at a larger probability. Besides that, the modified artificial bee colony algorithm can also improve the location accuracy. As a future work, we will analyze the impact of localization algorithms described in this article on a real environment and extend the localization of nodes in WSN applications.



---

*Source: 1464513-2019-06-10.xml*